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](https://mathoverflow.net/questions/419600/existence-of-a-joint-distribution-on-bernoulli-variables-with-same-probability-o) 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.



Existence of (near) equidistant codewords
$\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.


