4
$\begingroup$

Suppose $X \subseteq \lbrace 0 , 1 \rbrace ^{m}$ such that $|X| \geq 2^{0.8m}$, and $m \geq 2$, then prove that there exists $x,y \in X$ with $||x - y||_{1} \geq m/2$.

My approach to prove this was if there is no such $x,y$, then $X$ is inside a Hamming ball of radius $m/2$ . But this does not give me a tight enough inequality on the size of $X$.

$\endgroup$
6
  • $\begingroup$ Why "isoperimetric inequality"? This looks like something that should follow from the concentration of measure phenomenon. Why are you interested in this? $\endgroup$ May 6, 2015 at 19:04
  • 1
    $\begingroup$ Did you try the following: Let $D$ be the diameter of $X$, i.e., $\max_{x,y\in X} ||x-y||$, then $X$ is in the intersection of two Hamming balls of radius $D$ with centers a distance $D$ apart. Does this give you a tight enough bound? $\endgroup$ May 6, 2015 at 19:25
  • $\begingroup$ @BenoîtKloeckner : I found this stated without a proof in a paper. math.washington.edu/~rothvoss/publications/… $\endgroup$
    – rajatsen91
    May 6, 2015 at 20:05
  • $\begingroup$ @YoavKallus: I think this gets you to about (not quite) $D=m/3$, but it doesn't seem good enough for the full claim. $\endgroup$ May 6, 2015 at 20:36
  • $\begingroup$ @rajatsen91: did you have a look at the cited reference (Kleitman 1966)? Moreover, reading below the lemma it is written that other factors than $1/2$ in the distance lower bound would do for that paper, and the choice cited is $1/10$. Given Robert Israel's answer, I would bet that the $1/2$ in the paper is a typo. $\endgroup$ May 6, 2015 at 21:03

2 Answers 2

6
$\begingroup$

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lfloor(\lceil m/2\rceil-1)/2\rfloor$ (I hope I got this right now), then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

$\endgroup$
5
$\begingroup$

For small $m$, I've computed the cardinality $s(m)$ of the largest subset of $\{0,1\}^m$ of Hamming diameter $< m/2$, as follows:

$$\matrix{m & s(m)\cr 1 & 1\cr 2 & 1\cr 3 & 2\cr 4 & 2\cr 5 & 6\cr 6 & 7\cr 7 & 14\cr 8 & 16\cr}$$ The sequence does not appear to be in the OEIS. Clearly this is much too small for asymptotics (and with the methods I'm using it's going to be hard to get results for much larger $m$), but some of the sets returned seem to have a rather interesting structure. For example, for $m=8$ here is a set of size $16$ that has diameter $3$:

$$ \matrix{00000001\cr 00000010\cr 00000011\cr 00000101\cr 00000110\cr 00000111\cr 00001011\cr 00001111\cr 00010011\cr 00010111\cr 00100011\cr 00100111\cr 01000011\cr 01000111\cr 10000011\cr 10000111\cr }$$

EDIT: One lower bound of $s(m)$ is the cardinality of a ball of radius $\lfloor (m-1)/4 \rfloor$. This is $2^{m} \mathbb P(S_m \ge m - \lfloor (m-1)/4 \rfloor)$ where $S_m$ is the number of heads in $m$ independent fair coin flips. By Cramér's theorem from Large Deviations theory, as $m \to \infty$ this is roughly $ 2^m \exp(-m I(3/4)) = 2^{-km}$ where $k = 2 - (3/4) \log_2(3) \approx 0.811278$. Thus if $m$ is sufficiently large, a ball of radius $\lfloor (m-1)/4 \rfloor$ provides a counterexample.

Numerically, $377$ seems to be the least $m$ for which this works. That is, a ball of radius $94$ in $\{0,1\}^{377}$ has diameter $188 < 377/2$ and cardinality approximately $6.315655200 \times 10^{90} $, which is more than $2^{0.8 \times 377} \approx 6.175138852 \times 10^{90}$.

Just to show this isn't an artifact of roundoff error, the precise cardinality in this case is $$ \sum_{i=0}^{94} {377 \choose i} = 6315655199547126133494801496762823097854137171340937564314538960656350969227380734836894104$$

$\endgroup$
6
  • $\begingroup$ If you replace $0.8$ by any larger number, the conjecture becomes weaker. $\endgroup$ May 6, 2015 at 20:39
  • $\begingroup$ Oops, yes. So the conjecture is false. $\endgroup$ May 6, 2015 at 20:45
  • $\begingroup$ No, really: radius $m/4$, diameter $m/2$. $\endgroup$ May 6, 2015 at 21:00
  • $\begingroup$ That's right: $4^{1/4}(4/3)^{3/4}>2^{0.8}$, so the $m/4$ balls become too large by Stirling's formula. I actually did the same evaluation for myself a while ago, but then got the interpretation backwards apparently. $\endgroup$ May 6, 2015 at 21:12
  • $\begingroup$ I think we have to use Harper's theorem somehow, because the upper-bound we are looking for on $|X|$, is same as the cardinality of a sphere of radius $m/4$ that is less than $2^{0.81m}$ $\endgroup$
    – rajatsen91
    May 6, 2015 at 21:23

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.