Freiman's theorem in finite fields via extremal set theory

Details Freiman's theorem in finite fields via extremal set theory Freiman's theorem in finite fields via extremal set theory

2007-03-22

arxiv.org/abs/math/0703668v1

Mathematics

Combinatorics

18 pages

Scientific paper

Using various results from extremal set theory (interpreted in the language of additive combinatorics), we prove an asyptotically sharp version of Freiman's theorem in F_2^n: if A in F_2^n is a set for which |A + A| <= K|A| then A is contained in a subspace of size 2^{2K + O(\sqrt{K}\log K)}|A|; except for the O(\sqrt{K} \log K) error, this is best possible. If in addition we assume that A is a downset, then we can also cover A by O(K^{46}) translates of a coordinate subspace of size at most |A|, thereby verifying the so-called polynomial Freiman-Ruzsa conjecture in this case. A common theme in the arguments is the use of compression techniques. These have long been familiar in extremal set theory, but have been used only rarely in the additive combinatorics literature.

Affiliated with

Also associated with

No associations

Rating

Freiman's theorem in finite fields via extremal set theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Freiman's theorem in finite fields via extremal set theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Freiman's theorem in finite fields via extremal set theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-168517