Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-180 | 21st December 2012 04:58

The Freiman-Ruzsa Theorem in Finite Fields

RSS-Feed




TR12-180
Authors: Chaim Even-Zohar, Shachar Lovett
Publication: 21st December 2012 14:28
Downloads: 4253
Keywords: 


Abstract:

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.
The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$
then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was conjectured by Ruzsa that the subgroup size can be reduced to $r^{CK}$ for some absolute constant $C \geq 2$.
This conjecture was verified for $r=2$ in a sequence of recent works,
which have, in fact, yielded a tight bound. In this work, we establish the same conjecture for any prime torsion.



ISSN 1433-8092 | Imprint