Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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) $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.