Suppose is a finite field. Then given a subset of we define the sum of to be the set
and the product to be the set
We concern ourselves with estimating the size of and relative to the size of , and ultimately also to the size of .
If is empty then is empty as is and so . Now suppose is non-empty then let . Then
so . If then so finally assume , . Then we have
so in any case it always follows that
Now if has a proper subfield – for instance and – then setting makes and so in this situation the bound in (1) is tight, that is, . So we insist now that is a prime field, so it has no proper subfields.
We would like to understand what size must have to ensure that either or is larger than . (Note this is not the same as asking if or as we are concerned only with growth in size not the change in the elements of the set.) Clearly fails, as does and with some intuition as guidance it is safe to presume that 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 . This is the content of the following important result.
Theorem 1 (Sum-Product estimate:Bourgain-Katz-Tao (2003)).
Let be the field of prime order . Let be any subset of such that
for some . Then
for some which depends on and some constant which also depends on .
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.
|Date of creation||2013-03-22 16:54:48|
|Last modified on||2013-03-22 16:54:48|
|Last modified by||Algeboy (12884)|