# A sum-product estimate in Z/p^2Z

We are interested in a sum-product type estimate. Let $p$ be an odd prime, and let $A$ be the order $p-1$ subgroup of $(\mathbb{Z}/p^2\mathbb{Z})^\times$. That is, let $A = \langle g^p \rangle$, where $(\mathbb{Z}/p^2\mathbb{Z})^\times = \langle g \rangle$. We seek an estimate of the size of the sum set $$|A + A|.$$ The standard references, e.g. Additive Combinatorics by Tao & Vu, do not discuss this problem in the setting of $\mathbb{Z}/p^2\mathbb{Z}$, but instead focus on analogous results in finite fields. Similar estimates address situations where $|A + A|$ is small (e.g., on the order of $K|A|$), whereas in our situation, the product set $|A\cdot A|$ is very small, and we wish to show that $|A+A|$ must be large. Do results exist that address this problem more directly?

-
You are correct; my mistake. I have made the appropriate edit. –  Bob Lutz Jun 16 '13 at 7:58
It's not too hard to show that $A+A+A+A=\mathbb{Z}/p^2$. Experimentally, it appears that $A+A+A=\mathbb{Z}/p^2$ for $p>59$. I don't know how to prove that and that would be very nice. –  Felipe Voloch Jun 17 '13 at 1:26
@Felipe: if you could prove $3A={\mathbb Z}/p^2{\mathbb Z}$, then the desired conclusion would follow immediately. For, it is known that for any finite subset $A$ of an abelian group, the sequence $|A|,|2A|^{1/2},|3A|^{1/3},\ldots$ is decreasing and, in particular, $|2A|^{1/2}\ge|3A|^{1/3}$. Thus, in our case, $|3A|=p^2$ implies $|2A|\ge p^{4/3}>|A|^{4/3}$. Concerning your first remark ($4A={\mathbb Z}/p^2{\mathbb Z}$) -- could you kindly sketch the proof? –  Seva Jun 17 '13 at 11:44
I also think the result would follow from Felipe's claim via elementary sumset estimates. If $|A+A| \leq K |A|$ then from Lemma 2.2 of arxiv.org/pdf/math/0301343v3.pdf we have that $|A+A+A+A| \leq K^{c}|A|$ for some constant $c>0$. But since $|A| \sim p$, and $|4A| \sim p^2$ (by Felipe's claim) it follows that $|A+A| \geq |A|^{1 + c_2}$. –  Mark Lewko Jun 17 '13 at 15:03
Re $4A$: Bhaskaran, Acta Arith. 15 (1968/9) 217–219. –  Felipe Voloch Jun 17 '13 at 17:41

Heath-Brown and Konyagin stop just short of proving that $|A+A|\gg |A|^{3/2}$ in their paper on Gauss sums and Heilbronn's sum.

(Here $A$ is the same subgroup as above; since $A\cup\{0\}=\{0^p,\ldots,(p-1)^p\}$, we may write Heilbronn's sum as $H_p(a)=\sum_{n=0}^{p-1}e(an^p/p^2)=1+\sum_{x\in A}e(ax/p^2)$.)

By Cauchy-Schwarz, we have $|A\pm A|\geq |A|^4/E_+(A)$, where $E_+(A)$ is the cardinality of the set of "additive quadruples" $\{(a,b,c,d)\in A^4\colon a+b=c+d\}$.

Using Stepanov's method, Heath-Brown and Konyagin show that $E_+(A)\ll (p-1)^2+(p-1)p^{3/2}$. (This follows from their lemma 4 and the argument at the bottom of page 7.)

Combining the previous two results yields $|A\pm A|\gg |A|^{3/2}$, where the hidden constant is $1+o(1)$. In [http://arxiv.org/abs/math/0304217], Konyagin proves the same bound for multiplicative subgroups of $\mathbb{F}_p$ (see lemma 5).

Shkredov gives the improved bound $E_+(A)\ll |A|^{42/17}(\log|A|)^{10/17}$ in [http://arxiv.org/abs/1208.6124v1], and a further improvement $E_+(A)\ll |A|^{22/9}(\log|A|)^{2/3}$ in [S]. Thus up to logs, our additive energy argument gives $|A\pm A|\gg |A|^{3/2+1/18}$.

You can do better using an argument of Vyugin and Shkredov [VS] from [http://arxiv.org/abs/1102.1172]. Theorem 5.5 from [VS] shows that $|R\pm R|\gg |R|^{5/3}(\log|R|)^{-1/2}$, where $R$ is a multiplicative subgroup of $\mathbb{F}_p$ of size at most $p^{1/2}$. The proof relies on the following results from [VS]: Lemma 2.3 and Corollary 2.7, which are true for any finite abelian group, and Corollary 5.1 and Lemma 5.4, whose analogs in [S] are Proposition 8 and Corollary 9. Thus we have $|A\pm A|\gg |A|^{5/3}(\log|A|)^{-1/2}$.

Finally, you can apply Proposition 8 from [S] to get a lower bound on |A+A+A|.

Proposition 8 ([S]) Let $A$ be the multiplicative subgroup of $\mathbb{Z}_{p^2}$ of order $p-1$. Suppose that $Q_1,Q_2,Q_3$ are $A$-invariant subsets of $\mathbb{Z}_{p^2}$ and $|Q_1||Q_2||Q_3|\ll p^5$. Then

$\sum_{z\in Q_1}Q_2\ast (-Q_3)(z)\ll p^{-1/3}(|Q_1||Q_2||Q_3|)^{2/3}.$

(Note that Shkredov uses $\circ$ to denote convolution with $-B$; we're also using the convention that $B(x)$ is the indicator function of $B$.)

If $Q_1=Q_2-Q_3$, then the left hand side of the above equation is equal to $|Q_2||Q_3|$. Choosing $Q_1=A+A+A$, $Q_2=A$ and $Q_3=-(A+A)$, we get that

$|A+A+A|\gg p^{1/2}|A|^{1/2}|A+A|^{1/2}\gg p^{11/6}/(\log|A|)^{1/4}$.

-

Yes. Bourgain has a sum-product estimate for residues of a general modulus (although, the case of a composite modulus with few prime factors that covers your question was worked out prior by Bourgain and Chang to this). See:

J. Bourgain, Sum-product theorems and exponential sum bounds in residue classes for general modulus. C. R. Math. Acad. Sci. Paris 344 (2007), no. 6, 349–352

More precisely,

Theorem (Bourgain): Given a modulus $q$ and $\epsilon_1, \epsilon_2,\epsilon_{3} >0$, there exists a $\delta>0$ such that for any subset $A \subseteq Z_{q}$ one of the following holds:

i) $|A| \geq q^{1-\epsilon_1}$,

ii) one has the sum-product estimate: $$|A+A| + |A \cdot A| > q^{\delta}|A|,$$

iii) $\pi_{l}(A) < q^{\epsilon_{2}}$ where $\pi_{l} : Z_{l} \rightarrow Z_{p}$ is the quotient map and $l | q$ and $l > q^{\epsilon_{3}}$.

Taking $q=p^2$ and $|A| \sim p \sim q^{1/2}$ (which is the case in question) if we can prove that $\pi_{p}(A) > q^{\epsilon_{3}}$ for some absolute $\epsilon_3 >0$, then the sum-product estimate (case II) will apply. Since the $A$ given is a multiplicative subgroup, we have that $|A\cdot A| = |A|$. Thus the sum-produce estimate will imply that $|A+A| > q^{\delta}|A|$.

I now claim that $\pi_{p}(A) \geq p-1 \sim q^{1/2}$. This requires a bit of elementary number theory:

Claim: If $g$ is an integer that is a (multiplicative) generator mod $p^2$ then it is also a multiplicative generator mod $p$.

Proof: Assume that $g$ isn't a generator mod $p$, then $g^{x} = 1 \mod p$ for some $x \leq p$. Rewrite this as $g^x = cp+1$. But now $g^{xp} \mod p^2 \equiv (cp+1)^p \mod p^2 \equiv 1 \mod p^2$, but since $Z_{p^2}$ has cardinality $p(p-1)$ this would contradict that $g$ is a generator mod $p^2$.*

Let $g$ be a generator mod $p^2$. By the claim, $g^b \mod p$ for $0 \leq b \leq p-1$ is a complete set of residues mod $p$. On the other hand $g^{pb} \mod p^2$ for $0 \leq b \leq p-1$ is a subset of the set $A$. By Fermat's little theorem $g^{pb} \equiv g^{b} \mod p$. Thus, $g^{pb} \mod p$ for $0 \leq b \leq p-1$ is a complete set of residues mod $p$.

We conclude that $\pi_{p}(A) \geq p-1 \sim q^{1/2}$.

-