2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Jul 31 '13 at 11:41
  • 1
    $\begingroup$ The (dual) Hamming code of length 7 and minimum distance 4 does not work. I guess I try the Golay code next. $\endgroup$ – Jyrki Lahtonen Jul 31 '13 at 19:09
1
$\begingroup$

Progress report:

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).

I have this vague notion that this might always work similarly for self-orthogonal cyclic codes of a high enough minimum distance, but I need to jump start my brain to see, if that goes through. Anyway, there aren't very many such codes. Quadratic residue codes are probably worth checking, Golay code is an example of those.

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Unless I committed a Python-programming error, a brute force check tells me that this works. $\endgroup$ – user3533 Aug 2 '13 at 12:59
  • $\begingroup$ This helps me to a certain extent. I am not yet sure that this is exactly what I need, but by making up this simplified question I hoped to learn relevant techniques and ideas. $\endgroup$ – user3533 Aug 2 '13 at 13:02
  • $\begingroup$ 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) $\endgroup$ – user3533 Aug 2 '13 at 13:10
  • $\begingroup$ Now we want each sparse enough set of vertices to have a neighbor outside the set which an odd number of incoming edges. $\endgroup$ – user3533 Aug 2 '13 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.