# sum-product theorem

Suppose $\mathrm{\u0e50\x9d\x94\u0e1d}$ is a finite field^{}. Then given a subset $A$ of $\mathrm{\u0e50\x9d\x94\u0e1d}$
we define the *sum* of $A$ to be the set

$$A+A=\{a+b:a,b\u0e42\x88\x88A\}$$ |

and the product to be the set

$$A\u0e42\x8b\x85A=\{a\u0e42\x8b\x85b:a,b\u0e42\x88\x88A\}.$$ |

We concern ourselves with estimating the size of $A+A$ and $A\u0e42\x8b\x85A$ relative to the size of $A$, and ultimately also to the size of $\mathrm{\u0e50\x9d\x94\u0e1d}$.

If $A$ is empty then $A+A$ is empty as is $A\u0e42\x8b\x85A$ and so $|A|=|A+A|=|A\u0e42\x8b\x85A|$. Now suppose $A$ is non-empty then let $a\u0e42\x88\x88A$. Then

$$a+A=\{a+b:b\u0e42\x88\x88A\}\u0e42\x8a\x82A+A$$ |

so $|A|\u0e42\x89\u0e04|A+A|$. If $A=\{0\}$ then $A\u0e42\x8b\x85A=A$ so finally assume $a\u0e42\x88\x88A$, $a\u0e42\x890$. Then we have

$$a\u0e42\x8b\x85A=\{a\u0e42\x8b\x85b:b\u0e42\x88\x88A\}\u0e42\x8a\x82A\u0e42\x8b\x85A$$ |

so in any case it always follows that

$$|A|\u0e42\x89\u0e04|A+A|,|A\u0e42\x8b\x85A|.$$ | (1) |

Now if $\mathrm{\u0e50\x9d\x94\u0e1d}$ has a proper subfield ${\mathrm{\u0e50\x9d\x94\u0e1d}}_{0}$ โ for instance
$\mathrm{\u0e50\x9d\x94\u0e1d}=G\u0e42\x81\u0e02F\u0e42\x81\u0e02({p}^{2})$ and ${\mathrm{\u0e50\x9d\x94\u0e1d}}_{0}=G\u0e42\x81\u0e02F\u0e42\x81\u0e02(P)$ โ then setting $A={\mathrm{\u0e50\x9d\x94\u0e1d}}_{0}$
makes $A=A+A=A\u0e42\x8b\x85A$ and so in this situation the bound in (1)
is tight, that is, $|A|=|A+A|=|A\u0e42\x8b\x85A|$. So we insist now that $\mathrm{\u0e50\x9d\x94\u0e1d}$
is a prime field^{}, so it has no proper subfields.

We would like to understand what size $A$ must have to ensure that either $A+A$ or $A\u0e42\x8b\x85A$ is larger than $A$. (Note this is not the same as asking if $A\u0e42\x89A+A$ or $A\u0e42\x8b\x85A$ as we are concerned only with growth in size not the change in the elements of the set.) Clearly $A=\{0\}$ fails, as does $A=\mathrm{\u0e50\x9d\x94\u0e1d}$ and with some intuition as guidance it is safe to presume that $A$ must be large enough to have enough elements to produce many elements as a sum or product but also small enough that these these new elements outgrow the size of $A$. This is the content of the following important result.

###### Theorem 1 (Sum-Product estimate:Bourgain-Katz-Tao (2003)).

Let $\mathrm{F}\mathrm{=}{\mathrm{Z}}_{p}$ be the field of prime order $p$. Let $A$ be any subset of $\mathrm{F}$ such that

$$ |

for some $\mathrm{\u0e2e\u0e14}\mathrm{>}\mathrm{0}$. Then

$$\mathrm{max}\u0e42\x81\u0e01\{|A+A|,|A\u0e42\x8b\x85A|\}\u0e42\x89\u0e05C\u0e42\x81\u0e02{|A|}^{1+\mathrm{\u0e2e\u0e15}}$$ |

for some $\mathrm{\u0e2e\u0e15}\mathrm{>}\mathrm{0}$ which depends on $\mathrm{\u0e2e\u0e14}$ and some constant $C$ which also depends on $\mathrm{\u0e2e\u0e14}$.

The proof is non-trivial. Jean Bourgain was awarded the Fieldsโ medal in 1994,
Terence Tao in 2006 with the prize in part due to his various contributions in additive number theory.

http://www.arxiv.org/abs/math/0301343
Bourgain, Katz, and Tao, *A Sum-Product estimate in finite fields, and applications*, (preprint) arXiv:math/CO/0301343 v2, 2003.

Title | sum-product theorem |
---|---|

Canonical name | SumproductTheorem |

Date of creation | 2013-03-22 16:54:48 |

Last modified on | 2013-03-22 16:54:48 |

Owner | Algeboy (12884) |

Last modified by | Algeboy (12884) |

Numerical id | 8 |

Author | Algeboy (12884) |

Entry type | Theorem |

Classification | msc 11T99 |

Classification | msc 05B25 |

Synonym | Sum-product estimate |