5
$\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$?

Improve this question
$\endgroup$
1
  • 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
    Commented Dec 31, 2018 at 0:42

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Very nice answer, and it's great that you prove the bound is $1/2$! $\endgroup$
    – Dominic van der Zypen
    Commented Dec 31, 2018 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
    Commented Dec 31, 2018 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
    Commented Jan 1, 2019 at 3:24
  • $\begingroup$ you are right I started letting $m=n$ and changed later. thanks $\endgroup$
    – kodlu
    Commented Jan 1, 2019 at 4:09
  • $\begingroup$ Is this (incredible) answer entirely new to you, or is there a reference? Thanks. $\endgroup$
    – BD107
    Commented Dec 19, 2020 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .