Sum-product theorem for finite fields
A week ago I wrote about using some Python code to play with the sum-product theorem of ErdAs and Szemeri(C)di and its conjectured refinement. This morning I learned that the ErdAs-Szemeri(C)di theorem has been extended to finite fields.
David Johnston left a comment saying that he and his colleagues used this extension to finite fields as part of the construction of I1/4RNG, a remarkably efficient true random number generator. The finite field version of ErdAs-Szemeri(C)di leads to a way to combine three physical but non-uniform sources of randomness into a uniformly distributed stream of bits.
Bourgain, Katz, and Tao proved that the result
max{|A+A|, |A*A|} a c|A|1+I
extends to subsets A from a finite field F with conditions on the field F and the size of A relative to F.
It suffices for F to have prime order. More generally, and importantly for applications, it also holds for fields of order 2p for prime p.
Given a constant I > 0, if the size of the set A satisfies
|F|I < |A| < |F|1-I
then the theorem holds where the constant c depends on I.