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)$$

  • $\begingroup$ 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). $\endgroup$ Aug 21, 2012 at 18:16
  • $\begingroup$ Sorry, I wasn't aware of this policy. $\endgroup$
    – user887
    Aug 21, 2012 at 21:18
  • $\begingroup$ The entropy power inequality might be useful for you: en.wikipedia.org/wiki/Entropy_power_inequality $\endgroup$
    – Or Meir
    Aug 21, 2012 at 23:01

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.