# Cyclic error correcting code

Notation: I denote the field with $2$ elements by $\mathbb{F}_2$. For a vector $u\in\mathbb{F}_2^m$, I write $w(u)$ for the Hamming weight of $u$ (the number of components equal to $1$ in $u$).

Problem: I am looking for a pair $(n,v)$, where $n$ is a positive integer and $v$ is a vector in $\mathbb{F}_2^n$, such that:

every vector $u\in\mathbb{F}_2^n$ with $w(u)\leq\lceil\sqrt{2n}\rceil$ is not-orthogonal to at least $\lceil\sqrt{2n}\rceil+1-w(u)$ cyclic shifts of the vector $v$.

Motivation: This is related to coding theory. In particular, for such pair $(n,v)$, the subspace of $\mathbb{F}_2^n$ of all vectors orthogonal to all cyclic shifts of $v$, is a cyclic code with distance at least $\lceil\sqrt{2n}\rceil$ (but it is more than that).

Attempt: Since what I'm looking for induces a cyclic code, I looked a little into the theory of such codes. In particular, I considered BCH codes. These codes allow control of the distance of a code by choosing a generating polynomial in a certain way (every cyclic code can be defined in terms of a generating polynomial). Now, the orthogonal complement of a cyclic code is itself a cyclic code and we can find a generating polynomial for it and take $v$ to be the vector corresponding to the coefficients of this generating polynomial. I am not claiming that this method always solves my problem, but I'm trying to see if maybe it solves my problem for one particular choice of $n$ and a BCH code of length $n$.

• Have you checked words of weight $7$ (as candidates for $v$) in the binary Golay code of length 23? That would be my first guess. Or may be the dual Hamming code of length 7? Commented Jul 31, 2013 at 11:41
• The (dual) Hamming code of length 7 and minimum distance 4 does not work. I guess I try the Golay code next. Commented Jul 31, 2013 at 19:09

Unless I committed a Mathematica-programming error, a brute force check tells me that the combination $n=23$, $$v=(1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)$$ works. This vector and its cyclic shifts span the famous binary Golay of code of length $23$, dimension $12$ and minimum distance $7$. It is contained in its dual code (= the standard coding theory term for what you call the orthogonal complement).
Meanwhile, does this help you? Do double-check my claim that this actually works! AFAICT all the words of length $23$ and weight $\le 7$ are non-orthogonal to at least five cyclic shifts of $v$.
• Specifically, there are two things that could help me: The first is more control over $n$. I would probably want $n-1$ to be a prime power. The second is a stronger requirement. Instead of just requiring that all sparse enough vectors are orthogonal to enough cyclic shifts, consider the following requirment: Look at the directed graph on vertices $0,\dotsc,n-1$ where vertex $i$ has outgoing edges to vertices $i+u \pmod{n}$ for each $u$ in $U$. ($U$ is what we're looking for and corresponds to $v$ in the original question). (contd) Commented Aug 2, 2013 at 13:10