I'm trying to prove that for a $[2k, k, k]$-code, the Griesmer bound does not hold for $k > 4$.

Griesmer bound For any linear $[n, k, d]-$code over $\mathbb{F}^k_2$ the following holds: \begin{equation} n \ge \displaystyle\sum_{i=1}^{k}\left\lceil \frac{d}{2^{i-1}} \right\rceil. \end{equation}

$\lceil x \rceil$ is the ceiling function, so $\lceil x \rceil$ is the smallest integer $m$ with $m \ge x$.

So I'm trying to prove that for any $k > 4$ we have that \begin{equation} 2k < \sum_{i=1}^{k} \left\lceil \frac{k}{2^{i-1}} \right\rceil \end{equation}

I've tried doing it with induction, but this doesn't bring me very far. I'm puzzling with the fact that $\frac{k}{2^i} \le 1$ for a large $i$, but I can't quite seem to find anything helpful to give a definite proof.


Let us separate it into two cases :

Case 1 : $k$ is not the form $2^r$

Let us define $m:=\lceil\log_2(k)\rceil-1$ where we have $2^m\lt k\lt 2^{m+1}$.

Then, $$2^{m-i+1}\lt \frac{k}{2^{i-1}}\lt 2^{m-i+2}$$

So, $$\begin{align}\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil&=\sum_{i=1}^{m+1}\left\lceil\frac{k}{2^{i-1}}\right\rceil+\sum_{i=m+2}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil\\\\&\ge\sum_{i=1}^{m+1}(2^{m-i+1}+1)+\sum_{i=m+2}^{k}1\\\\&=2^{m+1}-1+m+1+k-(m+2)+1\\\\&=2^{m+1}-1+k\\\\&\gt 2k-1\end{align}$$ Since $\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil$ is an integer, we are done.

Case 2 : $k=2^m$

$$\begin{align}\sum_{i=1}^{k}\left\lceil\frac{k}{2^{i-1}}\right\rceil&=\sum_{i=1}^{m+1}\left\lceil\frac{2^m}{2^{i-1}}\right\rceil+\sum_{i=m+2}^{2^m}\left\lceil\frac{2^m}{2^{i-1}}\right\rceil\\\\&=\sum_{i=1}^{m+1}2^{m-i+1}+\sum_{i=m+2}^{2^m}1\\\\&=2^{m+1}-1+2^m-(m+2)+1\\\\&=2k+(k-\log_2k-2)\\\\&\gt 2k\end{align}$$ Here, we used $$k-\log_2k-2\gt 0\tag1$$ for $k\ge 5$.

Finally, let us prove $(1)$ for $k\ge 5$.

Let $f(k)=k-\log_2k-2$.

Then, $$f'(k)=1-\frac{1}{k\ln 2}=\frac{k\ln 2-1}{k\ln 2}\gt 0$$ So, $f(k)$ is increasing with $f(5)=3-\log_2(5)\gt 3-\log_2(8)=0$.

It follows from this that $f(k)\gt 0$ for $k\ge 5$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.