Query complexity and the polynomial Freiman-Ruzsa conjecture

Abstract

We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any $\epsilon >0$, a set $A\subset {\mathbb{Z}}^d$ with doubling $K$ has a subset of size at least $K^{-\frac{4}{\epsilon }}|A|$ with coordinate query complexity at most $\epsilon {\log }_2|A|$. We apply this structural result to give a simple proof of the "few products, many sums" phenomenon for integer sets. The resulting bounds are explicit and improve on the seminal result of Bourgain and Chang.

Restructured the paper for a more coherent exposition and extended the proofs

References in corpus (2)

• On higher energy decompositions and the sum-product phenomenon
• A Weighted Prékopa-Leindler inequality and sumsets with quasicubes

Cited by in corpus (1)

• The sum-product problem for integers with few prime factors