Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two binary vectors $V_1$, $V_2$ of length $\ell$, say that the distance between $V_1$ and $V_2$ is the number of positions in the vectors that don't match. So the distance between $001$ and $101$ is $1$. We also define rotations of $V$ so that if $V$ is $01011$, for example, the five rotations are $01011$, $10110$, $01101$, $110101$ and $10101$.

For a fixed $V_1$, call $c(V_1)$ the number of vectors $V_2$ such that $V_1$ is close to all rotations of $V_2$. Say that close means distance at most $k$. How can you find a $V_1$ which maximises $c(V_1)$?

If $V_1 =11111\dots$ then any vector $V_2$ with at most $\ell-k$ ones will do and so I think $c(V_1) = \sum_{i=0}^{k} \binom{\ell}{i}$. Can it be any larger and if not, how can you prove it?

share|improve this question
1  
Your distance is what is called the "Hamming distance," and your question is related to what is known as "cyclic codes." I suggest you read the corresponding Wiki article. –  Anon Jan 31 '13 at 20:56

1 Answer 1

up vote 0 down vote accepted

Let $N(V)$ be the set of vectors close to $V$, and $n=\lvert N(V)\rvert=\sum_{i=0}^k\binom\ell i$ independent of $V$. Denote the rotations of $V$ by $V_0,V_1,\ldots,V_{\ell-1}$, with $V_0=V$.

Let $c(V)=\lvert C(V)\rvert$, where $C(V)$ is the set of vectors close to all rotations $V_i$. Then $$C(V)=N(V_0)\cap N(V_1)\cap \cdots\cap N(V_{\ell-1}) \subseteq N(V).$$ Observe that $N(A)\not\subseteq N(B)$ for any pair of distinct binary vectors $A\ne B$. In particular, $N(V)\not\subseteq N(V_i)$ for $i\ne0$ unless $V_i=V$. So, $c(V)=\lvert C(V)\rvert\le\lvert N(V)\rvert=n$, with equality holding if and only if all rotations of $V$ are the same.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.