Skip to main content
added 1826 characters in body
Source Link
Mark Lewko
  • 13k
  • 1
  • 55
  • 87

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

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

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

added 73 characters in body
Source Link
Mark Lewko
  • 13k
  • 1
  • 55
  • 87

Yes. Bourgain has a sum-product estimate for residues of a general modulus (although, I believe 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

Yes. Bourgain has a sum-product estimate for residues of a general modulus (although, I believe the case of a composite modulus with few prime factors that covers your question was worked out prior 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

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

Source Link
Mark Lewko
  • 13k
  • 1
  • 55
  • 87

Yes. Bourgain has a sum-product estimate for residues of a general modulus (although, I believe the case of a composite modulus with few prime factors that covers your question was worked out prior 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