# Spreading $n$ points in $\{0,1\}^n$ as far as possible

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

• 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. – Gerhard Paseman Dec 31 '18 at 0:42

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 which eventually yields $$d\leq \frac{n}{2}\frac{m}{(m-1)}.$$ Letting $$m=n$$ proves the claim.

• Very nice answer, and it's great that you prove the bound is $1/2$! – Dominic van der Zypen Dec 31 '18 at 8:12
• 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.$ – Aaron Meyerowitz Dec 31 '18 at 8:41
• 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. – Andreas Blass Jan 1 at 3:24
• you are right I started letting $m=n$ and changed later. thanks – kodlu Jan 1 at 4:09