# Lower bound on the covering radius of a code

Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$.

Could you give me a hint how we could show this?

## 1 Answer

The idea is to use a sphere packing argument, only for covering. Let $V_q(\rho)$ be the volume of a Hamming ball of radius $\rho$. The Hamming balls around all codewords cover the entire space, so $V_q(\rho) q^k \geq q^n$, or $V_q(\rho) \geq q^{n-k}$. To deduce the bound, use an approximation for $V_q(\rho)$.

• I'm afraid your formula is incorrect. For example, $V_q(1) = 1 + n(q-1)$. The value depends on $n$. – Yuval Filmus Mar 25 '16 at 0:06
• You'll have to work that out. There are many approximations out there, then you can find in any textbook, or online. You can also work back and see what approximation gives the required bound, and then try to prove it or to look it up. Good luck! – Yuval Filmus Mar 25 '16 at 0:15
• You tell me. Good luck! – Yuval Filmus Mar 27 '16 at 14:25
• There are standard bounds, and one of them probably works. You can look at the list as well as I can. – Yuval Filmus Mar 27 '16 at 21:40
• The same book where this exercise is taken from. – Yuval Filmus Mar 27 '16 at 21:46