4
$\begingroup$

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$ We say that a positive integer $s$ is $n$-spreadable if there is $T\subseteq \{0,1\}^n$ with $|T|=n$ and for $x\neq y\in T$ we have $d_H(x,y) \geq s$. For any integer $n\geq 1$ let $m_n$ be the largest $n$-spreadable number less or equal to $n$.

Question. Do we have $\lim \sup_{n\to\infty}\frac{m_n}{n} = 1$?

$\endgroup$
  • 1
    $\begingroup$ No. By flipping all bits on a single coordinate, you can assume 0 in T. If there are two other vectors in T, the least Hamming distance between the three of them is at most 2n/3. I suspect the lim sup of your quantity is zero and not one, but I have not thought it through. Gerhard "The More Hamming, The Merrier" Paseman, 2018.12.30. $\endgroup$ – Gerhard Paseman Dec 31 '18 at 0:42
10
$\begingroup$

If I understood the question correctly, what you're asking is related to the maximum distance of binary codes with large minimum distance $d\geq s$.

In coding theory, $A_q(n,d)$ is defined as the maximum cardinality of a $q-$ary code with length $n$ and minimum distance $d.$

You can never have more than 2 codewords at full distance by binary geometry. In fact, the Plotkin bound for high distance binary codes states:

If $d$ is even (thus $n$ even for your case) and $2d>n\geq d,$ then $$ A_2(n,d)\leq 2\left\lfloor \frac{d}{2d-n}\right\rfloor, $$ which will give $A_2(n,d)\leq 2,$ for your case. Take any vector and it's bitwise complement.

The $d$ odd case is similar, see for Example Roman's book on Coding and Information Theory.

Of course you only want a lim sup tending to 1, and you can get it to tend to $1/2$ by using the rows of Hadamard matrices for $n$ a power of 2, but I doubt that any value larger than $1/2$ in your expression is achievable (see update below).

Edit: Thanks to Aaron Meyerowitz for clarifying the finite odd length case.

Proposition: The lim sup is actually $1/2.$

Assume that a value $d$ larger than $n/2$ is achievable. Map the codewords to $\pm 1$ vectors by writing $((-1)^{x_1},\ldots,(-1)^{x_n}).$ The inner product pf two $\pm 1$ valued vectors at hamming distance $d$ from each other is $\delta=n-2d.$ Therefore, if a collection of $m$ distinct $\pm 1$ vectors have minimum distance $d,$ we can write $$ 0\leq \left| \sum_{i=1}^m u_i \right|^2 = \langle \sum_i u_i , \sum_i u_i\rangle = \sum_i |u_i|^2 + 2 \sum_{i<j} \langle u_i,u_j \rangle \leq mn + m(m-1) (n-2d), $$ which eventually yields $$ d\leq \frac{n}{2}\frac{m}{(m-1)}. $$ Letting $m=n$ proves the claim.

$\endgroup$
  • $\begingroup$ Very nice answer, and it's great that you prove the bound is $1/2$! $\endgroup$ – Dominic van der Zypen Dec 31 '18 at 8:12
  • 1
    $\begingroup$ So $d \leq \frac{n^2}{2(n-1)}=\frac{n+1}2+\frac1{2n-2}$ and, being an integer, for $n \gt 2 $ even, $d=\frac{n}2$ can't be beat. To achieve that (getting a Haddamard code) requires $n$ to be a multiple of $4.$ That may well be sufficient, but is open. For odd $n$ one can't beat $\frac{n+1}2.$ In fact one can , for $n=4m-1$, acheive that with $n+1$ vectors, provided that there is a Haddamard code for $4m:$ puncture it by removing a coordinate where all the words agree. Example: for $n=4,d=2$ use $0000,0011,0101,0110$ for $n=3,d=2$ use $000,011,101,110.$ $\endgroup$ – Aaron Meyerowitz Dec 31 '18 at 8:41
  • 1
    $\begingroup$ As far as I can see, the $m^2$ in the rightmost part of the long displayed formula should be $mn$, since each $|u_i|^2$ is $n$, not $m$. Apparently this was just a typo, since the final upper bound on $d$ looks correct. $\endgroup$ – Andreas Blass Jan 1 at 3:24
  • $\begingroup$ you are right I started letting $m=n$ and changed later. thanks $\endgroup$ – kodlu Jan 1 at 4:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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