Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-180 | 21st December 2012 04:58

#### The Freiman-Ruzsa Theorem in Finite Fields

TR12-180
Authors: Chaim Even-Zohar, Shachar Lovett
Publication: 21st December 2012 14:28
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