# Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think.

I am interested in anything (ideas, references) related to the following problem:

Suppose that $A \subset \mathbb{Z}_p$ is a set of size $\delta p$ for $\delta > \frac{1}{2}$ (i.e. relatively big). What is known about the distribution of $\mu_A*\mu_A$ compared to $\mu_A$? In particular, what is known about $$\left\|\mu_A - \mu_A*\mu_A \right\|_{\ell_1(G)}$$

Taking $A = \left(\frac{p}{3},\frac{2p}{3}\right)$ we obtain that $A+A$ could be almost completely disjoint with $A$. This is however only possible if $\delta < \frac{1}{3}$ in view of the Cauchy-Davenport Theorem.

But even for $\delta>\frac{1}{3}$, it might still happen that $\mu_A*\mu_A$ puts a lot of its mass outside of $A$ and the distance is large even if $A+A$ intersects $A$. Do you know any concrete quantitative bounds?

Motivation: The upper bound would give us the bound on the rate of convergence of $n$-fold convolution of every measure on $\mathbb{Z}_p$, that has is $\delta$-close to the uniform measure in the total variational distance.

-
In other words, denoting by $r(g)$ the number of representations of an element $g\in{\mathbb Z}_p$ as a sum of two elements of $A$, you are asking how small can the sum $\sum_{a\in A} r(a)$ be. I do not think this has ever been studied. It seems natural to expect that the sum is minimized when $A$ is an interval, centered around $p/2$. Could you describe briefly the context in which this problem arose? (It does not look related to Markov chains.) – Seva Nov 15 '13 at 16:18
But it is:-). I am asking in fact for the speed of convergence of $n$-fold convolution of $\mu_A$. If you look at this as the Markov chain, the process has the transition matrix $Q(x,y) = \mu(y-x)$. It only $\delta<1$ every state will be eventually visited (because there is a positive mass on of of the generators), thus the proces converges. By some convexity considerations we expect the worst case to be the mass $\delta$ on $0$ and $1-\delta$ on some set $A$ of size $(1-\delta)p$. With probability $\delta$ the process doesn't change the state and otherwise shifts by a random element of $A$. – Maciej S. Nov 15 '13 at 16:39
Decomposing this measure as $\mu = \mu_U + (\delta-1/p)\delta_{0} - \delta\frac{1}{|A|}\mathbb{1}_{A}$ after some calculations leads to the problem of minimizing $\left|\delta - 2\mu_A +\mu_A*\mu_A\right|_{\ell_1}$ where $\mu_A$ is uniform on $A$. For better convergence we hope that $\mu_A*\mu_A$ kills the mass on $\mu_A$, then we can improve the rate. But what if it puts lot of mass outside? – Maciej S. Nov 15 '13 at 16:40

I assume you use the counting norm to define the convolution, as otherwise the $\ell_1$-norms of $\mu_A$ and $\mu_A\ast\mu_A$ are just of different order of magnitude. Thus, $(\mu_A\ast\mu_A)(g)=|A|^{-2}r(g)$, where $r(g)$ is the number of representations of $g$ as a sum of two elements of $A$. We therefore have $$\|\mu_A-\mu_A\ast\mu_A\|_{\ell_1} = \sum_{g\in G} \big|1_A(g)/|A|-r(g)/|A|^2\big|,$$ and an easy computation shows that this is equal to $$2-\frac2{|A|^2}\sum_{a\in A}r(a).$$ You thus ask how small can the sum $\sum_{a\in A} r(A)$ be.

As you remarked, if $\delta<1/3$, then $2A$ can be disjoint with $A$, in which case the sum vanishes. If $\delta>1/3$ then taking $A$ to be the interval of length $\delta p$ centered around $p/2$ makes the intersection of $A$ and $2A$ to be of size about $(3\delta-1)p$, and the sum in question about $2(1+2+\dotsb+((3\delta-1)/2)p)\approx\frac14(3\delta-1)^2p^2$. Here is an argument showing that this is the worst-case scenario; that is, our sum is always at least as large as $\sim\frac14(3\delta-1)^2p^2$.

For each $i\ge 1$, let $S_i:=\{g\in G\colon r(g)\ge i\}$, and fix an integer $k\ge 2|A|-p$. We have then $$\sum_{a\in A} r(a) = \sum_{i\ge 1} |S_i\cap A| \ge \sum_{i=1}^k (|S_i|+|A|-p) = \sum_{i=1}^k |S_i| - k(p-|A|).$$ Now, a well-known theorem of J. Pollard (incidentally, the uncle of J. Pollard serving his life sentence in a North Carolina prison for passing classified information to Israel) says that the sum in the right-hand side is at least $k(2|A|-k)$. It follows that $$\sum_{a\in A} r(a) \ge k(3|A|-k-p),$$ and to complete the proof we just choose $k\approx(3|A|-p)/2$.

-
Nice. Thanks a lot! – Maciej S. Nov 16 '13 at 0:02

It means that in some sense, the Polard inequality is a quantiative estimate on the following behavior:

Qualitative Statement. If $A,B\subset \mathbb{Z}_p$ are big enough, then the convolution $\mu_{A}*\mu_{B}$ is (in some sense) not heavily-tailed.

Quantitative Statement. Let $|A|=|B|=\delta$ be subset of $\mathbb{Z}_p$. Then

$$\mathbf{E}_{x\sim\mu}r(x)\mathbf{1}_{r(x) \geqslant t}(x) \leqslant \psi(t) := \delta^2 p - t \left(2\delta-\frac{t}{p}\right) \xrightarrow{t\to \delta p} 0 \quad (\star)$$ This is equivalent to the inequality in the Pollard Theorem.

Having such an estimate, for every $C\subset \mathbb{Z}_p$ big enough should be (with good constant) $$\mathbf{E}_{x\sim\mu_C} r(x) \approx \mathbf{E}_{x\sim\mu} r(x)$$

And to finish, we use the following simple estimate

$$\mathbf{E}_{x\sim\mu} r(x)\mathbf{1}_{C}(x) \geqslant \mathbf{E}_{x\sim\mu} r(x) - \psi(t)-t\cdot \mathbf{P}(C^c)$$

with suitably chosen $t$. In our case this is $t\left(3\delta-1-\frac{t}{p}\right) +t(1-\delta)$

-