Convolution of finite measures I am puzzled by the following (maybe very stupid) question I stumble upon in the course of a project: let $p$ be a probability measure on some abelian group $E$ (actually, $E=\mathbb{Z}_n$ with its usual structure, but I don't think this changes anything), and assume the total variation distance between $p$ and the uniform measure $u$ is $\epsilon$ — so I can write
$$
 p = u + p^+-p^-
$$
where $p^+,p^-$ are two positive finite measures with $p^+(E)=p^-(E)=\epsilon$ (and with disjoint support, I reckon). If I'm not mistaken, it follows that
$$
 p\ast p = u+\underbrace{(p^+-p^-)\ast(p^+-p^-)}_{q}
$$
Now, I would like to lowerbound the TV distance from $p\ast p$ to $u$, which is equivalent (again, if I'm not misunderstanding the whole thing) to compute $q(E)$. Intuitively, my first guess would be to say that $q(E)\geq \epsilon^2$; however, I don't know whether it is actually true, nor how to prove — if it is.
Any answer or insight (or even pointer to relevant readings) would be welcome!
Thanks,
 A: Here is a very incomplete answer.
For any complex measure $\mu$ on $E$, you have the trivial estimate 
$$\Vert \mu\Vert_{TV}\geq \Vert\widehat\mu\Vert_\infty\, , $$
where $\widehat\mu$ is the Fourier transform of $\mu$. 
If you apply this with $\mu=q=(p^+-p^-)*(p^+-p^-)$, this gives
$$\Vert q\Vert_{TV}\geq \Vert\widehat{(p^+-p^-)}\Vert_\infty^2\, . $$
Now, assume that your group $E$ is finite, and that you don't care about its cardinality (I mean, it is fixed once an for all; $E$ itself is not a parameter in your problem). Then the space of all measures on $E$ is finite-dimensional, so all norms on it are equivalent. In particular, there is a constant $c_E>0$ such that $\Vert \widehat\nu\Vert_\infty\geq c_E\,\Vert\nu\Vert_{TV}$ for all measures $\nu$ on $E$. Since $\Vert p^+-p^-\Vert_{TV}=\varepsilon$, it follows that $\Vert q\Vert_{TV}\geq c_E^2\, \varepsilon^2$.
Of course, this is cheating (if correct) and presumably not at all what you wanted.
Edit. In fact, it is not true that $\Vert q\Vert_{TV}\geq \phi(\varepsilon)$, for some (positive) function $\phi$ which does not depend on $E$. A kind of proof follows.
Towards a contradiction, assume that such a function $\phi$ does exist. Then, by homogeneity, there exists some absolute constant $c>0$ (independent of the group $E$) such that $$\Vert \nu*\nu\Vert_{TV}\geq c\, \Vert\nu\Vert_{TV}^2$$ for every real measure $\nu=p^+-p^-$ on $E$.
Denoting by $\nu^k$ the convolution $\nu*\cdots *\nu$ ($k$ times), we get by induction that $$\Vert \nu^{2^n}\Vert\geq c^{1+2+\cdots +2^{n-1}}\,\Vert\nu\Vert^{2^n}$$
for all $n\in\mathbb N$. By the spectral radius formula, it follows that
$$r(\nu)\geq c\, \Vert\nu\Vert_{TV} $$
for every real measure $\nu$ on $E$, where $r(\nu)$ is the spectral radius of $\nu$ in the (convolution) algebra $M(E)$ of all complex measures on $E$.
If $E$ is finite, then $M(E)$ can be identified with $\ell_1(E)$, so the spectral radius of a measure $\nu$ on $E$ is equal to $\Vert\widehat\nu\Vert_\infty$, where $\widehat\nu$ is the Fourier transform of $\nu$. So we have
$$\Vert\widehat\nu\Vert_\infty\geq c\, \Vert\nu\Vert_{\ell_1(E)} $$
for every finite abelian group $E$ and any real-valued function $\nu$ on $E$.
Now, take $E=\Omega_N$, the group of all $N$-roots of $1$ in $\mathbb C$, for any given $N\in\mathbb N$. Set $\omega:=e^{2i\pi/N}$. Then the dual group can be "identified" with $\{ 0,\dots ,N-1\}$, and any $\nu\in\ell_1(E)=M(E)$ can be written as $\nu=\sum_{n=0}^{N-1} a_n \delta_{\omega^n}$. With these notations, the Fourier transform of $\nu$ is given by $\widehat\nu(k)=P(\omega^k)$, where $P(z)=\sum_n a_n z^n$. In particular, we have $$\Vert\widehat\nu\Vert_\infty\leq \Vert P\Vert_\infty:=\sup\{ \vert P(z)\vert;\; \vert z\vert=1\}\, .$$
Since the integer $N$ is arbitrary, we arrive at the following conclusion: for any polynomial $P(z)=\sum_n a_n z^n$ with real coefficients, we have 
$$\sum_n \vert a_n\vert\leq c^{-1}\, \Vert P\Vert_\infty\, . $$
It is well known that this is not true, so we have the required contradiction.
A: $q=p^+\ast p^++p^-\ast p^--2p^+\ast p^-$ where $p^+\ast p^++p^-\ast p^-$ and $2p^+\ast p^-$ are nonnegative measures, and $(2p^+\ast p^-)(E)=2\epsilon^2$ hence $\|p\ast p-u\|_{TV}\leqslant2\epsilon^2$.
