<p>What you are asking is the <em>covering radius</em> of the Hadamard code. I am not sure what the answer is but the covering radius of the <em>punctured Hadamard code</em> 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$.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-14T23:11:27.737Z
Thank you for this answer. I really thought the answer is trivial but a lookup on the coverage radius tells me this is not the case ...
SpaceMonkey
CC BY-SA 3.0
2016-03-16T15:08:04.180Z
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
CC BY-SA 3.0
2016-03-17T01:29:55.650Z
@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: https://www.cs.tau.ac.il/~shpilka/publications/RabaniShpilka09.pdf
Sasho Nikolov
CC BY-SA 3.0
2015-01-12T19:45:26.933Z
2015-01-12T19:45:26.933Z
Sasho Nikolov
<p>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$.</p>

<p>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 $&gt; 1/2$ to all elements of the code. Can anyone help me?</p>

<coding-theory><property-testing>
Distance of arbitrary vectors to Hadamard code
SpaceMonkey
# Distance of arbitrary vectors to Hadamard code

(Asked by: username_0 on 2015-01-12)

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?

**Tags:** coding-theory, property-testing

---

## 1 answers

### Answer by username_1 on 2015-01-12. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you for this answer. I really thought the answer is trivial but a lookup on the coverage radius tells me this is not the case ...  
> **username_2**: What if I'm okay with using $n^\alpha$ codewords? Are there any constructions which can then give me better (smaller) covering radius?  
> **username_1**: @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: https://www.cs.tau.ac.il/~shpilka/publications/RabaniShpilka09.pdf  

---

