Sum-product theorem for finite fields

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 resultmax{|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 δ.

.

. More details

Leave a Reply