Hamming codes from overlapping vectors

Question

I am interested in whether the following problem is known.

For a given binary vector $V$ of length $n\geq m$, let $S$ be a subset of the possible subvectors of $V$ of length $m$ and say that the size of $S$ is simply the number of subvectors it contains.

For fixed $n$ and $m$ and maximising over all possible binary vectors of length $n$, what is the maximum size $S$ that has the property that the Hamming distance between all pairs $v_1,v_2 \in S$ is at least $d$?

If subvectors were not allowed to overlap then this would be a basic coding theory question.

(Clarification: A subvector has consecutive coordinates.)

Examples.

Let us simplify by setting n = 2m-1 so there are $m$ subvectors of a fixed $V$ each with length $m$.

Set $n = 7$, $m = 4$ and $d=2$. The vector $(1, 0, 1, 0, 0, 1, 1)$ has subvectors $(1,0,1,0), (0,1,0,0), (1,0,0,1)$ and $(0,0,1,1)$ which all have pairwise Hamming distance at least $2$. So for these values the answer is in fact $4$ which is as high as it can be.

Set $n = 7$, $m = 4$ and $d=3$. Over all vectors $V$ of length $7$, the largest set $S$ of subvectors of length $4$ all of which have pairwise distance $3$ from each other is $2$.

Set $n=9$, $m=5$ and $d=3$. Vector $V=(0, 0, 0, 1, 1, 0, 1, 0, 0)$ gives you the answer $4$ and is the maximum possible for these values of $n,m,d$.

Set $n=11$, $m=6$ and $d=3$. Vector $V=(0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1)$ gives you the answer $6$ which is as high as it can be.

Set $n=13$, $m=7$ and $d=4$. Vector $V=(0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1)$gives you the answer $7$ which is as high as it can be.

Clarification II. I would be happy with bounds rather than exact answers. Is there, for example, an equivalent of the Hamming bound for this setup?

Answer 1

Special case. There are wonderful (I am very sorry, I don't remember the name of their discoverer) binary sequences $(x_n)_{n\in \mathbb Z}$, which have period $2^m$, and such that the consecutive $2^m$ subvectors of length $m$ are all different (hence they exhaust all binary vectors of length $m$). Thus you may consider the induced sequence of length $n:=2^m$, with indices ordered cyclically, or you may consider an ordinary subvector of the length equal to $n:=2^m + m -1$. For such special $n$ your question now is reduced to the most fundamental question of the theory of the error correcting codes, where you simply (:-) ask about the maximal size of codes of length $m$ and distance $d$.

Answer 2

As pointed out by Gerry Myerson, this has a lot to do with autocorrelation of a sequence. More specifically incomplete (or aperiodic) autocorrelation.

What I say below will give something non-trivial only when $m$ is relatively large in comparison to $n$.

As a typical example (also of a De Bruijn sequence as recalled by Gerhard Paseman) consider the so called $m$-sequence. Let $\alpha$ be a generator (aka a primitive element) of the multiplicative group of the finite field $GF(2^\ell)$. Let $tr$ be the trace function from $GF(2^\ell)$ to $GF(2)$. Then an $m$-sequence $s$ of length $n=2^\ell-1$ is gotten by the recipe $$ s(i)=tr(\alpha^i), i=0,1,\ldots,n-1. $$ As $\alpha$ is of order $n$, the sequence starts repeating periodically, so we don't need to be too picky about where we start.

As is commonly done here, we map the bits to real numbers $0\mapsto+1, 1\mapsto -1$, so that we can apply the techniques of character sums. In other words, let's denote by $e(x)=(-1)^{tr(x)}$ the resulting (additive) character of $GF(2^\ell)$.

Two subvectors of length $m$ are just initial fragments of various cyclic shifts of $s$. If we start two subvectors from indices $a$ and $b$ respectively, then their Hamming distance is $$ d(s_a,s_b)=\frac12\sum_{i=0}^{m-1}\left(1+(-1)^{s(a+i)+s(b+i)}\right)=\frac{m}2+\frac12\sum_{i=0}^{m-1}e((\alpha^a+\alpha^b)\alpha^i). $$ As $a\neq b$, here the constant (=independent of $i$) $\alpha^a+\alpha^b\neq0$.

To cut a long story short this is a type of an incomplete exponential sum, where the (Polya-)Vinogradov method works splendidly. This is largely because the DFT of the sequence $s$ consists of Gauss sums, so they are well bounded. The end result is that we get estimates of the order $O(\sqrt n \log n)$ for the incomplete sums. So if $m$ is large in comparison $\sqrt n\log n$, we get the result that the Hamming distances between the two is "about" $m/2$.

I had the (unfortunately somewhat questionable) pleasure of extending this type of results to larger families of Kasami sequences. Other similar extensions to e.g. 4-phase sequences and their binary Grey-image sequences have also been carried out. A group of coding theorists enjoyed a field day or three with these problems in the 90s.

The Vinogradov-method is not expected to give a very sharp bound. IIRC Philippe Langevin from Toulon, France, has collected a lot of numerical data on these incomplete sums.