# Bounding the entropy of a convolution

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 function $f$ 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) .$$ (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)? Formally, is there any constant $C$ such that $$H \left( \frac{f*f}{\|f*f\|_2} \right) \le C \cdot H(f)$$

Note: This question was later posted to cstheory.stackexchange.com: cstheory.stackexchange.com/q/12343/636, where it was answered by Colin McQuillan.

-
Usually when you convolve measures, the entropy tend to grow, because the measure gets smoother (and in many occasions, smoother means also more spread-out). –  Asaf Aug 1 '12 at 12:55
That's not convolution, it's correlation. –  Kevin O'Bryant Aug 1 '12 at 14:08
Why is this not (also) a convolution? We are in $\mathbb{Z}_2^n$. This might be a silly question because I did not think about this question yet, but are you looking for a constant $C$ independent of $n$? –  Tapio Rajala Aug 1 '12 at 15:58
Oups - all elements have order 2 so that +=-. –  R W Aug 1 '12 at 17:08
This question was later posted to cstheory.stackexchange.com: cstheory.stackexchange.com/q/12343/636 –  Colin McQuillan Aug 21 '12 at 18:18
Just a question/remark: Presumably you want $f$ to be nowhere zero otherwise I'm not sure what you mean by $f^2(x) \text{log} f^2(x)$ when $f(x) = 0$. Perhaps by fiat, and with the ghost of L'Hôpital's rule in the background, you simply declare $f^2(x) \text{log} f^2(x)$ to be zero whenever $f(x)$ is ?
@Adrian, in entropy theory, $0 \log(0)\equiv 0$, you can justify that either by l'Hopital (when appropriate) or just take that as a definition. In any case, Colin already answered the question in stackexchange –  Asaf Sep 18 '12 at 18:21