12
$\begingroup$

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

$\endgroup$
9
+100
$\begingroup$

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

$\endgroup$

Your Answer

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