Number of words within Hamming distance $\delta$

Question

This is a problem I'm having reading Arora & Barak's book, page 378-379. They define:

For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the fraction of bits on which they differ, i.e. $\frac{1}{m} \cdot |\{i : x_i \neq y_i\}|$, where the $x_i$ refers to the $i$-th bit of $x$ (same for $y_i$).

Now, in the proof of Lemma 18.9, they use the fact that

for every string $y_i$ of $m$ bits, the number of strings that are of distance at most $\delta$ to it is ${m \choose \lceil \delta m \rceil}$

meaning that there are ${m \choose \lceil \delta m \rceil}$ words that disagree on not more than a $\delta$ fraction of bits.

But, I can't convince myself of that. Suppose for simplicity that $y_i = 0000 \ldots 000$. Here are the words that are of distance at most $\delta m$: all the words that have exactly one $1$, or two, or three, up to $\lfloor \delta m \rfloor$ of bits set to $1$. Thus I rather think that this number is

$$ \sum_{k = 1}^{\lfloor \delta m \rfloor} {m \choose k} $$

Can anyone explain?

Answer 1

That's an inaccuracy. If $\delta < 1/2$ is constant then it is the case that $\sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on $\delta$. (When $\delta$ is close to $1/2$ this doesn't hold: for example, $\sum_{k=0}^{m/2} \binom{m}{k} = 2^{m-1}$ for even $m$, while $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right)$.)

At any rate, what they are interested in really is the estimate $\sum_{k=0}^{\delta m} \binom{m}{k} \leq (1-\epsilon) 2^{H(\delta)m}$, which holds for every $\epsilon > 0$ and large enough $m$ (depending on $\epsilon,\delta$).