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

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?

share|improve this question
    
You are correct; my mistake. I have made the appropriate edit. –  Bob Lutz Jun 16 '13 at 7:58
2  
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
2  
@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
2  
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
1  
Re $4A$: Bhaskaran, Acta Arith. 15 (1968/9) 217–219. –  Felipe Voloch Jun 17 '13 at 17:41
show 4 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.