🔢 mathematics

A note on The asymptotic uniform distribution of subset sums

This paper demonstrates that the main result of "The asymptotic uniform distribution of subset sums" can be proven more simply by applying an explicit formula developed by Li and Wan.

Original authors: Yilong Hu

Published 2026-04-28

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Yilong Hu

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

The Great Cookie Jar Mystery: A Simple Guide to "The Asymptotic Uniform Distribution of Subset Sums"

Imagine you have a giant cookie jar filled with $n$ different types of cookies. Each cookie has a specific "value" written on it (like 1, 2, 3, etc.), and these values belong to a mathematical system called a "finite abelian group."

Now, imagine you reach into the jar and grab exactly $k$ cookies. You add up all the values on those cookies to get a Total Sum.

The Big Question

If you were to repeat this process millions of times, would certain sums appear much more often than others? For example, would you get a total sum of "10" all the time, while a sum of "50" almost never happens?

The original researchers (in the paper being discussed) wanted to prove that as the jar gets bigger and bigger ( $n$ goes to infinity), the sums become perfectly fair. This means every possible sum becomes equally likely to occur. In math terms, they say the distribution becomes "uniform."

The "Shortcut" Discovery

The author of this note, Yilong Hu, isn't trying to solve a new mystery. Instead, he is saying: "Hey, everyone, we don't need to take the long, winding mountain path to prove this. There is a secret tunnel!"

He uses a mathematical "cheat code" (an explicit formula) provided by other mathematicians (Li and Wan). This formula acts like a high-powered microscope that lets him see exactly how much the sums deviate from being perfectly equal.

The Mathematical Metaphor: The "Noise" vs. The "Signal"

Think of the total number of ways to pick cookies as a Signal. If everything were perfectly equal, the signal would be a smooth, flat line.

However, because of the way numbers work, there is some "Noise"—tiny fluctuations that make some sums slightly more common than others.

To prove the theorem, Hu only had to do one thing: Prove that the "Noise" eventually becomes invisible compared to the "Signal."

The Signal: This is the massive number of ways to pick $k$ cookies out of $n$ . As the jar grows, this number explodes toward infinity.
The Noise: This represents the mathematical "errors" or variations.

Hu uses some calculus (the part with $D^2L_n/Dk^2$ ) to show that even in the "worst-case scenarios"—when you pick very few cookies (like 4) or almost all the cookies—the Noise is so tiny compared to the Signal that it effectively vanishes.

The Conclusion

By showing that the ratio of Noise / Signal drops to zero as the jar gets larger, he proves that the sums become perfectly balanced.

In plain English: If you have a massive collection of items with mathematical values, and you pick a decent-sized handful of them, the total sum you get is essentially a random roll of the dice where every possible outcome is equally likely. The "unfairness" of the numbers gets swallowed up by the sheer scale of the possibilities.

Technical Summary: "A note on ‘The asymptotic uniform distribution of subset sums’"

Author: Yilong Hu (Shanghai Jiao Tong University)

1. Problem Statement

The paper addresses a problem in additive combinatorics concerning the distribution of subset sums within a finite abelian group $G$ of order $n$ . Specifically, it investigates the behavior of $N(k, b)$ , which denotes the number of $k$ -element subsets of $G$ whose elements sum to a specific element $b \in G$ .

The central objective is to provide a simplified proof for a theorem established in previous literature (referenced as [2]), which states that as the group order $n$ approaches infinity, the subset sums become uniformly distributed across all elements of the group for a specific range of $k$ . Formally, the theorem asserts:
$\lim_{n \to \infty} \frac{\min_{b \in G} |N(k, b)|}{\max_{b \in G} |N(k, b)|} = 1 \quad \text{for all } 4 \leq k \leq \lfloor n/2 \rfloor + 1$

2. Methodology

The author’s approach shifts away from the potentially complex original proof methods used in [2] and instead utilizes an explicit combinatorial formula for $N(k, b)$ proposed by Li and Wan.

The Explicit Formula: The author employs the identity:
$N(k, b) = \frac{1}{n} \sum_{r|(n,k)} (-1)^{k + \frac{k}{r}} \binom{n/r}{k/r} \Phi(r, b)$
where $\Phi(r, b)$ is a term involving the Möbius function $\mu$ and the structure of the group $G$ .
Asymptotic Analysis: The proof strategy relies on isolating the dominant term of the summation.
- The term for $r=1$ is identified as $\frac{1}{n} \binom{n}{k}$ , which represents the "average" number of subsets summing to any $b$ .
- The remaining terms ( $r > 1$ ) are treated as error terms. The author establishes a trivial upper bound for these error terms as $k \binom{n/2}{k/2}$ (assuming $n$ and $k$ are even for simplicity).
Convergence Proof: To prove the limit equals 1, the author demonstrates that the ratio of the error terms to the main term vanishes as $n \to \infty$ . This is achieved by analyzing the function:
$L_n(k) = \log\left(n k^2 \left(\frac{k}{n}\right)^{k/2}\right)$
By calculating the second derivative $D^2 L_n(k) / Dk^2$ , the author proves the function is convex for $k \geq 4$ , meaning its maximum must occur at the boundaries of the interval ( $k=4$ or $k = n/2 + 1$ ).

3. Key Contributions

Simplification of Proof: The primary contribution is not a new theorem, but a significantly more efficient and "shorter" proof of an existing result. By leveraging the Li-Wan formula, the author bypasses the complexities of the original derivation.
Analytical Bound Verification: The author provides a rigorous check of the boundary conditions ( $k=4$ and $k \approx n/2$ ) to ensure that the error terms do not grow fast enough to disrupt the uniform distribution as $n \to \infty$ .

4. Results

The author successfully confirms that:

The error terms in the explicit formula for $N(k, b)$ are negligible compared to the main term $\frac{1}{n} \binom{n}{k}$ as $n \to \infty$ .
The limit of the ratio between the minimum and maximum number of subset sums is indeed $1$ for the range $4 \leq k \leq \lfloor n/2 \rfloor + 1$ .

5. Significance

This note is significant for the field of additive combinatorics and probabilistic group theory. It demonstrates that complex distribution problems in finite abelian groups can be reduced to manageable asymptotic analysis using known explicit formulas. It provides a streamlined pedagogical path for researchers studying the subset sum problem and the equidistribution of sums in algebraic structures.