Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
By subvector do you mean consecutive coordinates or any subset of the coordinate indices? –  Felipe Voloch Apr 27 '13 at 16:54
    
Consecutive coordinates. Added to question. Thanks. –  user32786 Apr 27 '13 at 16:55
1  
Sounds like a question about autocorrelation of a sequence. –  Gerry Myerson Apr 27 '13 at 23:22
    
Makes me think of the sliding window in symbolic dynamics, à la Lind and Marcus An Introduction to Symbolic Dynamics and Coding, Cambridge 1995. And also that application of Euler paths to recombining fragments of RNA, Tucker "A new applicable proof of the Euler circuit theorem" American Mathematical Monthly 83 (1976) 638-640. –  Brian Hopkins Apr 28 '13 at 20:42

2 Answers 2

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

share|improve this answer
2  
DeBruijn is the name. Gerhard "And Sequence Packing's The Game" Paseman, 2013.04.28 –  Gerhard Paseman Apr 28 '13 at 20:54
1  
Thank you Gerhard "elephant memory" Paseman. –  Włodzimierz Holsztyński Apr 28 '13 at 21:28

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.

share|improve this answer
    
OOPSIE! Just noticed that we get to choose a collection of subvectors. For some reason I thought we would be forced to take all of them :-) –  Jyrki Lahtonen Jun 1 '13 at 12:42

Your Answer

 
discard

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