# Number of words within Hamming distance $\delta$

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?

• you are correct, it looks like a mistake. – Ran G. Dec 23 '15 at 17:23

## 1 Answer

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

• Thanks for the answer. I get the idea. Do you, by any chance, have an idea on how to prove the two assertions you mention (that $\sum_{k = 0}^{\delta m} {m \choose k} = O( {m \choose k} )$ and the last estimate) ? Not asking for the details, just the idea if you have it. Otherwise that's fine. – Manuel Lafond Dec 24 '15 at 1:55
• @ManuelLafond Take a look at their appendix or the Wikipedia article on binomial coefficients. – Yuval Filmus Dec 24 '15 at 9:27