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 2^{p} 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 δ.