# Distance of arbitrary vectors to Hadamard code

Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is straight forward to show that two different elements of the Hadamard code differ on exactly a fraction of $1/2$ of their values, e.g. their relative distance is exactly $1/2$.

What about the distance of arbitrary vectors to the Hadamard code? I've read in certain papers that this distance is also bounded by $1/2$ but other papers explicetely consider the case of vectors having distance $> 1/2$ to all elements of the code. Can anyone help me?

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ advantage over $\frac{N}{2}$ is optimal for any set of $O(N)$ points in $\{0, 1\}^N$.
The punctured Hadamard code maps $x \in \{0,1\}^n$ to the sequence $(\langle x, u\rangle\bmod 2)_{u \in \{1\}\times\{0, 1\}^{n-1}}$. It's not hard to see that the distance of the code is still $N/2$ as in the Hadamard code, but the number of codewords is $2N$. If we map each code word to a vector in $\{-1, 1\}^N$ by mapping $1$ to $-1$ and $0$ to $1$ we get vectors $v_1, \ldots, v_N, -v_1, \ldots, -v_N$ such that $\langle v_i, v_j \rangle = 0$ for any $i \neq j$. Taking any $x \in \{0, 1\}^N$ and mapping it to $u := 1 - 2x$ in the same way, we see that $x$ is Hamming distance $d$ away from a codeword if there exists an $i$ such that $|\langle v_i, u\rangle| = N-2d$. In other words, it's enough to show that for any $u \in \{-1, 1\}^N$ there exists an $i$ such that $|\langle v_i, u\rangle| \geq \sqrt{N}$. But this follows from the properties of the $v_i$: $$\max_i |\langle v_i, u\rangle|^2 \geq \frac{1}{N}\sum_{i = 1}^N{|\langle v_i, u\rangle|^2} = \sum_{i = 1}^N{u_i^2} = N.$$ The inequality is by averaging and the first equality is true because $\frac{1}{\sqrt{N}}v_1, \ldots, \frac{1}{\sqrt{N}}v_N$ is an orthonormal basis of $\mathbb{R}^N$.
The fact that no set of $O(N)$ points in $\{0, 1\}^N$ can cover $\{0, 1\}^N$ with radius $\frac{N}{2} - \omega(\sqrt{N})$ is equivalent to the fact that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$, $M = O(N)$, there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u\rangle| = O(\sqrt{N})$ for all $i$. This is a restatement of Spencer's "Six Standard Deviations Suffice" theorem from discrepancy theory.
• What if I'm okay with using $n^\alpha$ codewords? Are there any constructions which can then give me better (smaller) covering radius? – Thomas Ahle Mar 16 '16 at 15:08
• @ThomasAhle The general version of Spencer's result is that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$ there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u \rangle| = O(\sqrt{N\log(2M/N)})$. So the covering radius is at least $N/2 - O(\sqrt{N\log(2M/N)})$. This is tight for a random construction. Check this paper for explicit constructions: cs.tau.ac.il/~shpilka/publications/RabaniShpilka09.pdf – Sasho Nikolov Mar 17 '16 at 1:29