Constructive arithmetic regularity algorithm for finite abelian groups
Constructive Arithmetic Regularity for Abelian Groups
Data Structures and Algorithms
Summary
Finding hidden patterns in large groups of numbers is a common problem in math and computer science. Green's arithmetic regularity lemma helps by breaking these groups into simpler, random-like parts, but the original proof only showed this was possible without a way to find the parts efficiently. The authors developed a new algorithm that can quickly find these parts for a wide variety of groups, extending previous work beyond just binary groups. This makes it possible to solve related counting and removal problems in these groups with much better computational efficiency.
What this means in practice
- •For theoretical computer scientists: Efficiently remove specified linear patterns from subsets of finite abelian groups with constant torsion using the new constructive method.
- •For algorithm designers: Approximate counting of linear images and weighted sumsets in finite abelian groups, aiding the design of algorithms dealing with algebraic structures beyond binary fields.
Authors
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
Abstract
The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over $\mathbb{F}_2^n$ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's {\em Arithmetic Regularity Lemma} in this general setting. Given oracle access to a subset of the group, our algorithm computes an implicit description of a regular decomposition together with an oracle representation of a structured subset satisfying the guarantees of Green's lemma. The algorithm runs in time and query complexity polynomial in the regularity parameters and the tower bound, while remaining independent of the size of the ambient group. As applications, we obtain efficient algorithms for removing linear configurations and approximately counting linear images, including weighted sumsets and suitable matrix systems of Cauchy--Schwarz complexity one, over finite Abelian groups of constant torsion. Our results provide a unified algorithmic framework extending dimension-independent constructive arithmetic regularity and its applications beyond $\mathbb{F}_2^n$.