论文标题
查询复杂性和多项式Freiman-Ruzsa猜想
Query complexity and the polynomial Freiman-Ruzsa conjecture
论文作者
论文摘要
我们证明了以下形式的弱多项式Freiman-Ruzsa猜想的查询复杂性变体。对于任何$ε> 0 $，A集成$ A \ subset \ Mathbb {z}^d $带dumping $ k $具有至少$ k^{ - \ frac { - \ frac {4}ε} | 我们将这种结构结果应用于整数集的“少数产品，许多总和”现象的简单证明。最终的界限是明确的，并在波尔加因和张的开创性结果上得到了改善。
We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any $ε> 0$, a set $A \subset \mathbb{Z}^d$ with doubling $K$ has a subset of size at least $K^{-\frac{4}ε}|A|$ with coordinate query complexity at most $ε\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.
