4
$\begingroup$

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.

$\endgroup$

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – hookah
    Commented Apr 6, 2022 at 15:52
  • $\begingroup$ you are right, sorry this is a careless non-answer. will try to get back to it when I have a little more time. $\endgroup$
    – kodlu
    Commented Apr 6, 2022 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.