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$
  • $\begingroup$ Why "isoperimetric inequality"? This looks like something that should follow from the concentration of measure phenomenon. Why are you interested in this? $\endgroup$ – Benoît Kloeckner May 6 '15 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$ – Yoav Kallus May 6 '15 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 '15 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$ – Christian Remling May 6 '15 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$ – Benoît Kloeckner May 6 '15 at 21:03
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

| cite | improve this answer | |
$\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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If you replace $0.8$ by any larger number, the conjecture becomes weaker. $\endgroup$ – Christian Remling May 6 '15 at 20:39
  • $\begingroup$ Oops, yes. So the conjecture is false. $\endgroup$ – Robert Israel May 6 '15 at 20:45
  • $\begingroup$ No, really: radius $m/4$, diameter $m/2$. $\endgroup$ – Robert Israel May 6 '15 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$ – Christian Remling May 6 '15 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 '15 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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