Existence of (near) equidistant codewords

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

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

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

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.
• Dear kodlu: I didn't get how $d_H(x_i,x_j)$ is constant. Imagine for a second $n=5$ and $w=2$. Consider $11000,10100,00011$. Pairwise Hamming distances in this setting is clearly not constant. Hope I'm not missing sth real trivial. Commented Apr 6, 2022 at 15:52