A week ago I wrote about using some Python code to play with the sum-product theorem of Erdős and Szemerédi and its conjectured refinement. This morning I learned that the Erdős-Szemeré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 μRNG, a remarkably efficient true random number generator. The finite field version of Erdős-Szemeré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|} ≥ c|A|1+ε
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 δ > 0, if the size of the set A satisfies
|F|δ < |A| < |F|1-δ
then the theorem holds where the constant c depends on δ.