Existence of (near) equidistant codewords

Question

My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.

Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ equipped with the Hamming distance. Is it true that there exists nearly equidistant $x_1,\dots,x_k\in\Sigma_n$ with pairwise Hamming distance of $\beta n$. More concretely, is it true that for any $\beta\in(0,1)$ and any $\gamma$ small enough, there is an $N^*$ such that for all $n\ge N^*$ there exists $x_1,\dots,x_k\in\Sigma_n$ such that $$ \bigl|n^{-1} d_H(x_i,x_j)-\beta\bigr|\le \gamma. $$

Thoughts. If $\beta \le \frac12$ then probabilistic method takes care of it: assign randomly each coordinate $x_i(k)$ ($1\le k\le n$) of $x_i$ so that $\mathbb{P}[x_i(k)=1]=p$, where $p$ satisfies $2p(1-p)=\beta$. Check that $\mathbb{E}[d_H(\sigma_i,\sigma_j)]=\beta n$. Setting $\mathcal{E}_{ij}$ to be the event that $n^{-1} d_H(x_i,x_j) \in[\beta-\eta,\beta+\eta]$ (which occurs with probability $o_n(1)$) simple union bound over $\binom{k}{2}$ events (which is of constant order in $n$) yields the conclusion for all $n$ large enough. But this argument fails if $\beta>\frac12$ as $\max_{p\in[0,1]} 2p(1-p)=1/2$.

Follow-up. Noam's bound is tight for $k$ even. For $k$ odd, we have $s_i = \sum_{1\le j\le k}v_j(i)\equiv 1\pmod{2}$ for each $1\le i\le n$ as $v_j(i)\in\{\pm 1\}$. Namely, the coordinates of sum $s=\sum_j v_j$ are odd, thus $\langle s,s\rangle \ge n$. Hence we get (after sending $\gamma\to 0$) $$ n\le kn\bigl(1+(k-1)(1-2\beta)\bigr). $$ Rearranging, we find $\beta\le (k+1)/2k$ for $k$ odd.

Existence. Now the existence. Fix coordinate $1\le j\le n$, generate $x_1,\dots,x_k$ randomly according to following distribution: $(x_i(j):1\le i\le k)$, $1\le j\le n$ is i.i.d. with $\mathbb{P}[x_i(j)=1]=1/2$ for all $i,j$ and $\mathbb{P}[x_i(j)=x_t(j)]=1-\beta$ for $1\le i<t\le k$. Now, Iosif Pinelis' answer here shows the existence of such a joint distribution. Under this, it is easily seen $\mathbb{E}[n^{-1}d_H(x_i,x_t)] = \beta$; the rest follows by a simple application of probabilistic method via Chebyshev's inequality.

Answer 1

$\beta$ cannot be too much larger than $1/2$; namely we must have $\beta \leq k/(2k-2)$.

To prove this, identify the $x_i$ with vectors $v_i \in {\bf R}^n$ each of whose coordinates is $1$ or $-1$, and consider these vectors' dot products. Clearly $v_i \cdot v_i = n$, and more generally $v_i \cdot v_j = n - 2 d(x_i,x_j)$, which for $i \neq j$ implies $v_i \cdot v_j \leq (1-2\beta') n$ where $\beta' = \beta - \gamma$ is arbitrarily close to $\beta$. On the other hand $s := \sum_{i=1}^k v_i$ must satisfy $s \cdot s \geq 0$. Thus $$ 0 \leq s \cdot s = k n + \sum_{i\neq j v_i \cdot v_j} \leq kn + (k^2-k) (1-2\beta') n = kn\left(1 + (k-1)(1-2\beta')\right), $$ whence $2\beta' - 1 \leq 1/(k-1)$. Therefore $\beta \leq k/(2k-2)$ as claimed.

Answer 2

Following up on Noam's answer: for $k = 3$ I think the bound is even tighter, $\beta \leq 2/3$.

If $d(x,y), d(y,z) > n(\frac{2}{3} + \epsilon)$, then if we define $A = \{i \ : \ x_i \neq y_i\}$ and $B = \{j \ : \ y_j \neq z_j\}$, then $|A \cap B| \geq |A| + |B| - n > n(\frac{1}{3} + 2\epsilon)$. For every $m \in A \cap B$, $x_m \neq y_m \neq z_m$, so $x_m = z_m$. This implies that $d(x,z) < n(\frac{2}{3} - 2\epsilon)$, and so precludes a `near-equidistant triple' for $\beta > \frac{2}{3}$.

Answer 3

The problem is more involved than I thought [deleted my non answer]. The comments below may or may not help you:

In the book Combinatorics of Symmetric Designs by Ionin and Shrikande, Binary equidistant codes are discussed in Section 4.7 [some of it is visible through google books to me]. The same authors also have a paper Equidistant Families of Sets, Linear Algebra and Its Applications 226-228:223-235 (1995).

Equidistant families of sets are the equivalent to binary equidistant codes, with the codeword support corresponding to a set in the family, with the universe being $[n]=\{1,2,\ldots,n\}.$

A result from the paper is that if $n=2d,$ there are connections to Hadamard designs. More generally given an equidistant $(n,m,d)$ code, results include:

• If $n\equiv 3 \pmod 4$ and $m=v+1,$ then $d=(v+1)/2$ and existence of the code is equivalent to the existence of a Hadamard matrix of order $v+1.$
• If $n\equiv 1 \pmod 4$ and $m=v$ then $d\leq (v-2)/2.$ An equidistant $(v,v,(v-2)/2)$ code exists if a related symmetric design exists.