Geodesic
A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space
Discrete analysis (2017) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

The Polynomial Freiman-Ruzsa conjecture is one of the central open problems in additive combinatorics. If true, it would give tight quantitative bounds relating combinatorial and algebraic notions of approximate subgroups. In this note, we restrict our attention to subsets of Euclidean space. In this regime, the original conjecture considers approximate algebraic subgroups as the set of lattice points in a convex body. Green asked in 2007 whether this can be simplified to a generalized arithmetic progression, while not losing more than a polynomial factor in the underlying parameters. We give a negative answer to this question, based on a recent reverse Minkowski theorem combined with estimates for random lattices.
Publié le : 
@article{DAS_2017_a12,
     author = {Shachar Lovett and Oded Regev},
     title = {A counterexample to a strong variant of the {Polynomial} {Freiman-Ruzsa} conjecture in {Euclidean} space},
     journal = {Discrete analysis},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2017_a12/}
}
TY  - JOUR
AU  - Shachar Lovett
AU  - Oded Regev
TI  - A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space
JO  - Discrete analysis
PY  - 2017
UR  - http://geodesic.mathdoc.fr/item/DAS_2017_a12/
LA  - en
ID  - DAS_2017_a12
ER  - 
%0 Journal Article
%A Shachar Lovett
%A Oded Regev
%T A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space
%J Discrete analysis
%D 2017
%U http://geodesic.mathdoc.fr/item/DAS_2017_a12/
%G en
%F DAS_2017_a12
Shachar Lovett; Oded Regev. A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space. Discrete analysis (2017). http://geodesic.mathdoc.fr/item/DAS_2017_a12/