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?
Number of words within Hamming distance $\delta$
combinatorics;coding theory;word combinatorics
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$).