Query complexity and the polynomial Freiman-Ruzsa conjecture

From MaRDI portal

Query complexity and the polynomial Freiman-Ruzsa conjecture (scientific article)

Jump to:navigation, search

DOI10.1016/J.AIM.2021.108043MaRDI QIDQ6336453arXivWikidataFDO

Authors Dmitry Zhelezov, Dömötör Pálvölgyi

Publication date 10 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.AIM.2021.108043

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30)

arXiv classification

Abstract: We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any

e p s i l o n > 0

, a set

A s u b s e t m a t h b b Z^{d}

with doubling

K

has a subset of size at least

K^{- f r a c 4 e p s i l o n} | A |

with coordinate query complexity at most

e p s i l o n l o g_{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.

This page was built for publication: Query complexity and the polynomial Freiman-Ruzsa conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6336453)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Query_complexity_and_the_polynomial_Freiman-Ruzsa_conjecture_(scientific_article)&oldid=95044868"