Algorithmic Polynomial Freiman-Ruzsa Theorems

2025/09/02 by Srinivasan Arunachalam, Arunachalam, Srinivasan, Davi Castro-Silva +5 · 1 voice
#math.CO

paper · pdf · doi:10.48550/arxiv.2509.02338

Abstract

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for A ⊆ \mathbbF₂ⁿ with doubling constant K, learn an explicit description of a subspace V ⊆ \mathbbF₂ⁿ of size |V| ≤ |A| such that A can be covered by K^C translates of V, for a universal constant C>1.

Discussions

• New arXiv preprint: we show algorithmic versions of the polynomial Freiman–Ruzsa (PFR) theorem of Gowers, Green, Manners, and Tao. Interestingly, our proof draws on quantum information and stabilizer [bsky, 27 points, 2 comments]

Related

• An algorithmic Polynomial Freiman-Ruzsa theorem
• A polynomial Freiman-Ruzsa inverse theorem for function fields
• Freiman's theorem in finite fields via extremal set theory
• Equivalence of polynomial conjectures in additive combinatorics
• Locality in Sumsets