# The entropy of a convolution over the hypercube

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural to define the entropy of such a function as follows: $$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x)^2 \log \left( f(x)^2 \right) .$$

Now, consider the convolution of $f$ with itself: $$[ f*f] (x) = \sum_{y \in \mathbb{Z}_2^n}f(y)f(x+y) .$$ (Note that since we are dealing with $\mathbb{Z}_2^n$, then $x+y=x-y$)

Is it possible to upper bound the entropy of $f*f$ (normalized in its $L_2$-norm, in order for it to be a distribution) by the entropy of $f$? Formally, is there any constant $C$ such that $$H \left( \frac{f*f}{\|f*f\|_2} \right) \le C \cdot H(f)$$

• This question was posted to mathoverflow on the first of August: mathoverflow.net/questions/103668/… (it's usually fine to crosspost with a delay like this, but you should say what you're doing). Aug 21 '12 at 18:16
• Sorry, I wasn't aware of this policy.
– user887
Aug 21 '12 at 21:18
• The entropy power inequality might be useful for you: en.wikipedia.org/wiki/Entropy_power_inequality Aug 21 '12 at 23:01

There is no such $C$. Define $g\colon\mathbb{Z}_2^n\to\mathbb{R}$ by $$g(x_1,\dots,x_n)=\begin{cases} 2^{2n/3}&\text{ if x_1=\dots=x_n=0}\\ 1&\text{ otherwise.}\end{cases}$$
Then $g*g$ satisfies $$(g*g)(x_1,\dots,x_n)=\begin{cases} 2^{4n/3}+2^n-1&\text{ if x_1=\dots=x_n=0}\\ 2^{2n/3}\cdot 2+2^n-2&\text{ otherwise.}\end{cases}$$
Let $f=g/\|g\|_2$. Then $H(f)=H(g/\|g\|_2)$ is $o(1)$ (in fact it's exponentially small in $n$), while $H(g*g/\|g*g\|_2)$ is about $n$.