Constructive Arithmetic Regularity for Abelian Groups

Introduction

Regularity lemmas are among the central tools of modern combinatorics and theoretical computer science. They decompose large combinatorial objects into a bounded number of pieces that behave almost randomly, thereby reducing global questions to the analysis of locally structured components. In the arithmetic setting, the fundamental result of this kind is Green’s arithmetic regularity lemma [Gre05]: an analogue of Szemerédi’s graph regularity lemma [Sze75] which asserts that every subset of a finite Abelian group can be partitioned into cosets of a suitable subgroup so that, on almost all cosets, the set is pseudorandom in the Fourier sense: after restricting the indicator function of the set to a typical coset, all of its non-trivial Fourier coefficients are uniformly small. This notion of pseudorandomness is captured by the following definition.

Green proved that such a decomposition always exists, with respect to a subgroup of bounded codimension:

Green’s lemma has found numerous applications in additive combinatorics [GT10a] and property testing [4]. However, Green’s proof, like the classical proof of Szemerédi’s lemma, is purely existential, whereas many algorithmic applications in learning theory, property testing, and approximate counting, require access to the regular decomposition itself. This raises the central question of this paper:

Can a regular decomposition be constructed efficiently, given only query access to the set?

De, Nadimpalli, and Servedio [4] answered this question affirmatively over $\mathbb{F}_2^n$, developing a query-efficient constructive regularity framework and applying it to approximate sumset-size estimation. In the same work [4], they explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups, identifying the lack of suitable implicit Fourier-analytic procedures as a central obstacle.

In this work, we resolve this open problem for finite Abelian groups of constant exponent. We develop a constructive arithmetic regularity algorithm whose query complexity depends only on the regularity parameters and the group exponent, and is independent of the size of the ambient group. Our framework also yields an approximate sumset estimator in this setting, together with more general algorithmic applications.

In general, extending a framework from $\mathbb{F}_2^n$ to arbitrary finite Abelian groups is far from routine. The vector-space setting of $\mathbb{F}_2^n$ benefits from an underlying field structure in which characters can be identified with linear forms and, the concept independence is simply the ordinary linear independence. For a group of torsion $\tau$, by contrast, the coefficient ring $\mathbb{Z}_\tau$ may contain zero divisors, characters may interact across cyclic components of different orders, and ordinary linear independence must be replaced by the more flexible notion of pseudo-independence (Definition A.17) defined in [2, 3].

There is, however, a more fundamental obstacle to extending the regularity algorithm from $\mathbb{F}_2^n$ to a general finite Abelian group $\mathcal{G}$. The difficulty is not merely that individual Fourier-analytic tools become more delicate. Green’s existential proof of the arithmetic regularity lemma relies crucially on the structure of Bohr neighbourhoods. In the vector-space setting, the relevant Bohr neighbourhoods coincide with subspaces and therefore admit an exact coset structure on which Fourier analysis can be performed directly. For a general Abelian group, positive-radius Bohr neighbourhoods need not be subgroups and do not partition the ambient group into cosets. This prevents a direct algorithmic translation of Green’s argument. Green overcomes this difficulty in the existential setting by working with nested and smoothed Bohr neighbourhoods; algorithmically, however, this would require efficient procedures for manipulating these additional objects and goes substantially beyond the direct use of first-order Fourier-analytic primitives.

We overcome these obstructions by developing an implicit subgroup-based regularity framework for finite Abelian groups. However, this raises a natural question: where does the subgroup structure come from, given that [Gre05] works with Bohr neighbourhoods? To address this, we work with subgroups arising as common kernels of characters, equivalently, zero-radius Bohr neighbourhoods. Each such neighbourhood is a normal subgroup of $\mathcal{G}$, a structural property that provides the first and most important step toward developing an efficient regularity algorithm for finite Abelian groups. We provide a more detailed exposition in Subsection 2.2.

Although these subgroups provide an exact coset partition, the main algorithmic challenge is to construct and refine this partition implicitly, without explicitly identifying the defining characters. Several fundamental Fourier-analytic tools for finite Abelian groups have been developed in [2, 3], which we use in our proofs. However, these tools alone are insufficient for our purposes. For example, our regularity algorithm constructs a character decision tree in the spirit of [4], but each node now involves randomized implicit procedures and must operate over a much more complicated character group.

A further ingredient is therefore a precise relation between the Fourier coefficients of restricted and truncated functions (Definitions 3.2 and 3.3). In the vector-space setting this relationship is essentially transparent, whereas for general Abelian groups it is obscured by the presence of cyclic components of different orders and by zero divisors in $\mathbb{Z}_\tau$. Nevertheless, using the dual-group structure of $\widehat{\mathcal{G}}$, we establish a clean correspondence between the restricted and truncated Fourier spectra (Theorem 3.6). This correspondence is what allows the algorithm to detect local non-regularity using global Fourier-analytic subroutines, while keeping its query complexity independent of $|\mathcal{G}|$.

Conceptually, this viewpoint reveals that regularity in general finite Abelian groups can still be organized through exact subgroup fibres, despite the loss of the vector-space structure available over $\mathbb{F}_2^n$. Thus, beyond its algorithmic role, our approach provides a concrete way to understand how an arbitrary subset of a bounded-torsion Abelian group decomposes into structured cosets on which its Fourier behaviour is pseudorandom. In place of positive-radius Bohr neighbourhoods, the subgroup–coset structure becomes the basic object underlying our constructive decomposition.

Having established the constructive regularity theorem, we demonstrate its versatility through two algorithmic applications. Although regularity decompositions often reduce global problems to the analysis of structured local pieces, extending the corresponding applications from $\mathbb{F}_2^n$ to general finite Abelian groups will introduce additional obstructions due to the missing vector space structure and the zero-divisor problem. In particular, multiplication by nonzero coefficients need not be invertible, while general matrix systems require additional determinantal non-degeneracy and torsion-compatible Cauchy–Schwarz complexity conditions. Establishing the corresponding counting and covering lemmas therefore requires additional arguments beyond those used over $\mathbb{F}_2^n$. We use these ingredients to obtain efficient algorithms for the following two problems.

Removal of linear configurations. One of the most celebrated consequences of Szemerédi’s graph regularity lemma is the graph removal lemma of Ruzsa and Szemerédi [RS78]: a graph containing few copies of a fixed subgraph can be made entirely free of that subgraph by deleting a small fraction of its edges. Removal lemmas have since become a cornerstone of extremal graph theory, additive combinatorics, and property testing [FL17, GS17]. Green’s arithmetic regularity lemma yields an analogous arithmetic removal lemma, in which graphs are replaced by subsets of finite Abelian groups and forbidden subgraphs by solutions to homogeneous systems of linear equations; removing triangles from a graph becomes a special instance of removing solutions to a linear configuration from a set. We give an query-efficient, randomized algorithm for this task. For a single linear equation, and more generally for any system of Cauchy–Schwarz complexity one (the class studied structurally by Green and Tao [GT10b]), our algorithm extracts a large configuration-free subset by deleting only a small fraction of the original set, with complexity independent of the ambient group size. We describe in more detail in § 2.

Approximate image counting. Our second application concerns estimating the size of additive images of a set. The prototypical problem is sumset-size estimation: given query access to $A \subseteq\mathcal{G}$, estimate the density of $A+A$. Sumsets and their structure are a classical theme in additive combinatorics [Ruz09, GR07], and the exact computational problem is intractable: even recognizing sumsets is NP-complete [1]. De, Nadimpalli, and Servedio [4] showed that, over $\mathbb{F}_2^n$, the constructive regularity lemma yields an efficient estimator for the density of the sumset of a slight, density-preserving perturbation of $A$ (a relaxation that is necessary, as they also prove a matching lower bound for the exact problem). The same framework also extends to $A+B$, given query access to both $A$ and $B$, and to $kA$ for any fixed $k$. Note that such approximate counting becomes significantly more challenging and inherently different when moving from $\mathbb{F}_2^n$ to a general finite Abelian group $\mathcal{G}$ because of the group structure. This is also why [4] left this task as an open problem.

We generalize this in two directions at once. For an Abelian group $\mathcal{G}$ of constant torsion, integers $a_1,\ldots,a_m$, and the linear form $L(x)=\sum_{j=1}^{m}a_jx_j$, consider the image set

which recovers the sumset $A+A$ when $m=2$ and $a=(1,1)$. We show that, given only query access to $A$, one can efficiently approximate the density of $L(A^m)$ for a density-preserving perturbation $A'\subseteq A$. We further extend this result to suitable matrix images $M(A^{m})$, under determinantal non-degeneracy and torsion-compatible complexity-one assumptions, while keeping the query complexity independent of $|\mathcal{G}|$. We give a furture detailed Definition and exposition in § 2.

Thus, beyond resolving the open problem of De, Nadimpalli, and Servedio [4], our framework substantially generalizes the original sumset application to general linear images and to suitable systems of linear equations over finite Abelian groups.

Our Results

We first introduce some notation. $\mathcal{G}$ denotes a finite Abelian group $\mathbb{Z}_{p_1}^{m_1} \times\cdots\times\mathbb{Z}_{p_T}^{m_T}$, where $p_i$ are primes for all $i \in[T]$ and may not be distinct, and $\omega_\tau$ denotes a primitive $\tau^{\mathrm{th}}$ root of unity, where $\tau= LCM\{p_1^{m_1},\ldots,p_T^{m_T}\}$. Throughout this article we assume $\mathcal{G}$ is an Abelian group with constant torsion/constant exponent that is $\tau$ is constant. $\operatorname{Tower}(\tau,t)$ denotes the tower of $\tau$ of height $t$. $\mathbf{1}_A:\mathcal{G}\to\{0,1\}$ denotes the Indicator function of the set $A\subseteq\mathcal{G}$.

An Overview of Our Results

Before diving into the statements let us describe some basic definitions that we will be using:

Given arbitrary subsets $A,B\subseteq\mathcal{G}$ of some abelian group $\mathcal{G}$, we denote the following:

and

where $|\cdot|$ denotes the size of the set. Let $f:\mathcal{G}\to\{0,1\}$. A randomized algorithm $\mathcal{O}$ with query access to $f$, is said to be a probabilistic oracle machine for $g:\mathcal{G}\to\{0,1\}$ if for any input $x\in\mathcal{G}$, the algorithm $\mathcal{O}^f$ outputs a bit $\mathcal{O}^f(x)$ such that

where the probability is over internal randomness of $\mathcal{O}^f$. The query complexity of the machine is the number of oracle calls made by $\mathcal{O}$ to $f$, and the running time of the machine is the number of time steps it takes in the worst case. Let $f:\mathcal{G}\to\{0,1\}$ and $g:\mathcal{G}\to\{0,1\}$ be two functions. An algorithm $\mathcal{A}$ with query access to $f$ is said to output a $(\delta,q,T)$-oracle $\mathcal{O}^f_g$ for the function $g$ if it outputs a representation of a probabilistic oracle machine $\mathcal{O}^f_g:\mathcal{G}\to\mathbb{R}$ such that the following holds:

where the query complexity of $\mathcal{O}^f_g$ is at most $q$ and the running time is at most $T$. If $\delta=0$ we call $\mathcal{O}^f_g$ to be an exact oracle.

The Regularity Lemma is one of the central tools in extremal combinatorics and additive combinatorics, with numerous applications in property testing, learning theory, and approximation algorithms. Green proved an arithmetic regularity lemma for finite Abelian groups [Gre05]. However, many algorithmic applications, such as learning and property testing, require a constructive version. [4] gave an efficient constructive regularity lemma over $\mathbb{F}_2^n$, and left open the problem of obtaining an efficient algorithm for general finite Abelian groups. Our first and main contribution resolves the open problem posed by De, Nadimpalli, and Servedio [4]: we obtain a query-efficient constructive version of Green’s arithmetic regularity lemma for finite Abelian groups of constant torsion, with complexity independent of the size of the ambient group. This structural result forms the basis for the more general algorithmic applications developed below.