🔢 mathematics

Anticoncentration of Random Sums in $\mathbb{Z}_p$

This paper establishes explicit anticoncentration bounds for the sum of a small number of independent identically distributed random variables in $\mathbb{Z}_p$ , proving that the maximum probability of the sum is strictly less than the uniform bound of the individual variables and extending these non-asymptotic estimates to larger sums through iteration.

Original authors: Simone Costa

Published 2026-02-19

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Simone Costa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game with a giant, circular clock that has $p$ hours on it (instead of 12). This clock represents the mathematical world called $\mathbb{Z}_p$ .

You have a bag of special dice. Each die doesn't have numbers 1 through 6; instead, each die is "loaded" to land on specific hours on the clock, but with a rule: no single hour is too likely. If you roll one die, the chance of it landing on any specific hour is small (let's call this maximum chance $\lambda$ ).

Now, here is the game: You roll $\ell$ of these dice and add up the hours they land on. Because it's a clock, if you go past the last hour, you wrap around to the beginning. The question is: After rolling all these dice, is there any specific hour on the clock that is surprisingly likely to be the final result?

The Old Way of Thinking (The "Asymptotic" View)

For a long time, mathematicians studied what happens when you roll thousands of dice ( $\ell \to \infty$ ). They found that if you roll enough dice, the results spread out so evenly across the clock that the chance of landing on any specific hour becomes tiny and predictable. It's like pouring a bucket of sand on a beach; eventually, the sand covers everything evenly.

However, the paper by Simone Costa asks a different question: What happens if you only roll a few dice? Maybe just 3, 4, or 10?

In this "small number" regime, the old math breaks down. If you roll 3 dice, the sand hasn't spread out yet; it's still clumped in a few spots. The old formulas that work for thousands of dice actually say, "We can't tell you anything useful here," or they give an answer that is worse than just guessing.

The New Discovery (Anticoncentration)

Costa's paper proves that even with just a few dice, the results do not clump together dangerously. Even if you only roll 3 dice, the probability of landing on any single "lucky" hour is strictly smaller than the probability of landing on that hour with just one die.

Think of it like this:

One die: You have a small chance of hitting a specific hour.
Three dice: You might think, "If I add them up, maybe they will accidentally line up perfectly to hit the same hour more often?"
Costa's Result: "Nope! Adding them up actually makes it less likely to hit that specific hour than you'd expect. The sum 'spreads out' (anticoncentrates) much faster than the old math suggested."

The "Magic" of the Proof

How did he prove this? He used a clever trick involving symmetry and averaging.

The "Symmetry" Trick: He looked at the case where the dice are balanced (like a fair coin, but for many numbers). He showed that if the dice are balanced, the sums cancel each other out in a way that prevents any single number from winning.
The "Peeling the Onion" Method: For larger numbers of dice (like 9 or 27), he didn't try to solve it all at once. Instead, he treated groups of 3 dice as a single "super-die."
- He proved that 3 dice make the result safer (less likely to clump).
- Then he proved that if you take those 3 dice and add another 3, the result is even safer.
- By repeating this process, he showed that even if you don't roll thousands of dice, just rolling a moderate amount (like 10 or 20) is enough to guarantee the results are spread out nicely.

Why Does This Matter?

This isn't just a game of dice. This math is used in:

Computer Science: Designing algorithms that need to avoid "collisions" (where two different inputs accidentally produce the same output).
Cryptography: Ensuring that secret codes don't accidentally reveal patterns.
Randomness: Checking if a random number generator is actually random or if it's "cheating" by favoring certain numbers.

The Takeaway

Before this paper, if you asked a mathematician, "What's the chance of getting a specific sum if I only roll 5 random numbers?" they might have said, "We don't have a good answer for that; our formulas only work for millions of rolls."

Costa's paper says: "We do have an answer! Even with just a handful of rolls, the results are guaranteed to be spread out. The 'clumping' is much weaker than we thought."

It's like realizing that even if you only throw a few handfuls of confetti into the air, it won't land in a single pile; it will scatter nicely across the floor, even before you've thrown the whole bucket.

1. Problem Statement and Motivation

The paper investigates the Littlewood–Offord problem within the context of finite cyclic groups, specifically $\mathbb{Z}_p$ (integers modulo a prime $p$ ). The core question is to determine the anticoncentration properties of the sum $Y = \sum_{i=1}^\ell Y_i$ of $\ell$ independent random variables $Y_i$ taking values in $\mathbb{Z}_p$ .

The Regime: While asymptotic results (where $\ell \to \infty$ ) are well-established (e.g., by Lev), this paper focuses on the non-asymptotic regime where $\ell$ is small or moderate (specifically $\ell < 24$ ).
The Gap: Existing asymptotic bounds, such as those by Lev, often rely on constants that become trivial (larger than 1) for small $\ell$ , failing to provide meaningful estimates better than the trivial bound $1/p$ or $1/n$ .
The Goal: To provide explicit, non-trivial upper bounds on $\max_{x \in \mathbb{Z}_p} P[Y=x]$ for small $\ell$ , even when the distributions of $Y_i$ are not uniform but merely bounded by a parameter $\lambda < 1$ .

2. Methodology

The author employs a combination of probabilistic combinatorics, Fourier analysis, and inductive arguments.

A. The Integer Case ( $\mathbb{Z}$ )

Before tackling $\mathbb{Z}_p$ , the author revisits the integer case to establish baseline bounds.

Reduction: Using a theorem by Leader and Radcliffe, the problem is reduced to the case where variables are uniformly distributed on a symmetric interval $\{-(n-1)/2, \dots, (n-1)/2\}$ .
Large $\ell$ : For large $\ell$ , the Berry-Esseen theorem is used to approximate the sum distribution by a normal distribution, yielding a bound of order $O(1/(n\sqrt{\ell}))$ .
Small $\ell$ ( $\ell=3$ ): The author provides a direct combinatorial proof for $\ell=3$ , calculating the exact number of triples summing to the mode. This yields an explicit bound:
$\max_{x \in \mathbb{Z}} P[Y=x] \leq \frac{3 + 1/n^2}{4n}$
This is non-trivial for all $n \geq 2$ .

B. Transfer to $\mathbb{Z}_p$

Freiman Isomorphism: For groups $\mathbb{Z}_k$ with large prime factors, the author notes that a Freiman isomorphism of order $\ell$ allows transferring integer bounds to the group setting. However, this requires strong assumptions on the prime factors of $k$ .
Direct Fourier Analysis: To avoid assumptions on prime factors, the paper utilizes Discrete Fourier Transforms (DFT) directly on $\mathbb{Z}_p$ $Z_{p}$ .
- The probability $P[Y_1 + Y_2 = x]$ is expressed via the inverse DFT of the square of the characteristic function.
- The proof involves partitioning the set of possible sums based on the magnitude of their probabilities and analyzing the "concentration" of the set $A$ around specific values.

C. Inductive Argument for General $\ell$

The core innovation is an inductive step that builds bounds for larger $\ell$ based on the $\ell=3$ case.

Base Case ( $\ell=3$ ): The author proves that if the individual distributions are bounded by $\lambda$ , the sum of three variables is bounded by $C_3 \lambda$ where $C_3 < 1$ .
Iteration: By grouping variables into blocks of three, the bound is iterated. If $Y = \sum_{i=1}^{3k} Y_i$ , the maximum probability is bounded by $(C_3)^k \lambda$ .
General $\ell$ : For arbitrary $\ell$ , the result is extended by considering the largest power of 3 less than or equal to $\ell$ .

3. Key Contributions and Results

A. Explicit Bounds for $\ell=3$

The paper establishes that for independent variables $Y_1, Y_2, Y_3$ in $\mathbb{Z}_p$ with distributions uniformly bounded by $\lambda$ :
$\max_{x \in \mathbb{Z}_p} P[Y_1 + Y_2 + Y_3 = x] \leq C_3 \lambda$
where $C_3$ is an absolute constant strictly less than 1.

Explicit Value: Through computational verification (using Mathematica), the author shows $C_3 < 1 - 1.3 \times 10^{-12}$ (specifically $C_3 < 0.9999999999987$ ).
Condition: This holds provided $p > 2/\lambda$ and $\lambda \leq 9/10$ (the restriction on $\lambda$ is to ensure an explicit constant; the result holds for $\lambda < 1$ with a $\lambda$ -dependent constant).

B. General Bounds for $\ell \geq 3$

By iterating the $\ell=3$ result, the paper derives a bound for any $\ell \geq 3$ .
Let $\ell_0 = 3^k$ be the largest power of 3 such that $\ell_0 \leq \ell$ . The main theorem states:
$\max_{x \in \mathbb{Z}_p} P[Y = x] \leq \lambda \left( \frac{3}{\ell_0} \right)^\nu$
where $\nu = -\log_3(C_3)$ is a positive absolute constant.

Significance: This provides a decay rate for the maximum probability as $\ell$ increases, even for small $\ell$ .
Comparison: Unlike Lev's asymptotic bounds which are trivial for $\ell < 24$ , this bound is non-trivial for $\ell \geq 3$ .

C. Handling Non-Uniform Distributions

A significant departure from classical Littlewood–Offord results (which often assume uniform distribution on a set) is that this work handles arbitrary distributions provided they are pointwise bounded by $\lambda$ . This makes the results applicable to a wider range of probabilistic structures.

4. Significance and Impact

Bridging the Small- $\ell$ Gap: The paper addresses a specific gap in the literature where asymptotic tools fail. It provides the first effective, explicit anticoncentration bounds for small numbers of summands in finite cyclic groups.
Applications to Set Sequenceability: The results are motivated by the set sequenceability problem, where one needs to ensure that partial sums of a sequence do not concentrate too heavily on any single element. The non-asymptotic nature of these bounds is crucial for finite combinatorial constructions.
Explicit Constants: Unlike many probabilistic existence proofs, this paper provides explicit constants ( $C_3$ , $\nu$ ) and conditions ( $p > 2/\lambda$ ), making the results potentially usable for concrete algorithmic or combinatorial applications.
Methodological Rigor: The proof combines Fourier analysis with careful combinatorial partitioning (Case 1 vs. Case 2 in the proofs) to handle the modular arithmetic constraints of $\mathbb{Z}_p$ without relying on Freiman isomorphisms that require large prime factors.

Summary Conclusion

Simone Costa's paper successfully extends the Littlewood–Offord theory to the non-asymptotic regime in $\mathbb{Z}_p$ . By proving that the maximum probability of a sum of $\ell$ bounded random variables decays exponentially with $\ell$ (specifically related to powers of 3), the author provides a powerful tool for analyzing random walks and combinatorial structures in finite groups where traditional asymptotic approximations are insufficient. The work is notable for its explicit constants and its applicability to non-uniform distributions.