An Application of Ramsey Theory to Coding for the Optical Channel
Navin Kashyap, Paul H. Siegel, Alexander Vardy · SIAM Journal on Discrete Mathematics · 2005
In this paper, we analyze bi-infinite sequences over the alphabet $\{0,1,\ldots,q-1\}$, for an arbitrary $q \geq 2$, that satisfy the q-ary ghost pulse (qGP) constraint. A sequence $\x = {(x_k)}_{k \in \Z} \in \{0,1,\ldots,q-1\}^{\Z}$ satisfies the qGP constraint if for all $k,l,m \in \Z$ such that $x_k$, $x_l$ and $x_m$ are nonzero and equal, $x_{k+l-m}$ is also nonzero. This constraint arises in the context of coding for communication over a fiber optic medium. We show, using techniques from Ramsey theory, that if $\x$ satisfies the qGP constraint, then the set $\supp(\x) = \{l \in \Z:\ x_l eq 0\}$ is the disjoint union of cosets of some subgroup, $k\Z$, of $\Z$, and a set of zero density. We provide much sharper results in the special cases of $q = 2$ and $q=3$. In the former case, we show that the corresponding binary ghost pulse constraint has zero capacity, and based on our results for the latter case, we conjecture that the capacity of the ternary ghost pulse constraint is also zero.