Return to Answer

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, $401$ seems to be the least $m$ for which this works. That is, a ball of radius $100$ in $\{0,1\}^{401}$ has diameter $200 < 401/2$ and cardinality approximately $4.451044858 \times 10^{96}$, which is more than $2^{0.8 \times 401} \approx 3.718969435 \times 10^{96}$.

Just to show this isn't an artefact of roundoff error, the precise cardinality in this case is $$ \sum_{i=0}^{100} {401 \choose i} = 4451044857989361860971781711838050061594238007627359390463621910156920521123421259901477392651224$$

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

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, $401$ seems to be the least $m$ for which this works. That is, a ball of radius $100$ in $\{0,1\}^{401}$ has diameter $200 < 401/2$ and cardinality approximately $4.451044858 \times 10^{96}$, which is more than $2^{0.8 \times 401} \approx 3.718969435 \times 10^{96}$.

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, $401$ seems to be the least $m$ for which this works. That is, a ball of radius $100$ in $\{0,1\}^{401}$ has diameter $200 < 401/2$ and cardinality approximately $4.451044858 \times 10^{96}$, which is more than $2^{0.8 \times 401} \approx 3.718969435 \times 10^{96}$.

Just to show this isn't an artefact of roundoff error, the precise cardinality in this case is $$ \sum_{i=0}^{100} {401 \choose i} = 4451044857989361860971781711838050061594238007627359390463621910156920521123421259901477392651224$$

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$. This would (just barely) fit with your conjecture: if you replaced $0.8$ by $0.813$ the conjecture would be false.

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, $401$ seems to be the least $m$ for which this works. That is, a ball of radius $100$ in $\{0,1\}^{401}$ has diameter $200 < 401/2$ and cardinality approximately $4.451044858 \times 10^{96}$, which is more than $2^{0.8 \times 401} \approx 3.718969435 \times 10^{96}$.