🔢 mathematics

The Entropic Sum-Product Phenomenon

This paper establishes an entropic sum-product phenomenon by proving that for independent and identically distributed discrete real-valued random variables with finite Shannon entropy, the maximum of the entropies of their sum and product is at least $\frac{8}{7}$ times the original entropy (up to a logarithmic correction), thereby answering a question posed by Goh and improving upon previous bounds through novel uniformization techniques adapted from Solymosi's combinatorial work.

Original authors: Rupert Li

Published 2026-08-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Rupert Li

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 a detective trying to solve a mystery about how things mix. In the world of mathematics, there is a famous puzzle called the "sum-product phenomenon." It asks a simple question: If you have a collection of numbers, can you arrange them so that when you add them together, you get very few unique results, and when you multiply them together, you also get very few unique results? The answer, discovered by mathematicians decades ago, is a resounding "no." You can't be good at both. If your numbers are arranged to be easy to add (like a neat row of steps), they become chaotic when multiplied. If they are easy to multiply (like powers of a single number), they become chaotic when added. It's like trying to be a perfect square and a perfect circle at the same time; the universe just won't allow it.

Now, imagine we swap these rigid numbers for "fuzzy" clouds of probability. Instead of a fixed list of numbers, imagine a bag of marbles where some colors are more common than others. This is what mathematicians call a "random variable." Instead of counting how many unique sums or products exist, we measure the "entropy" of the result. Think of entropy as a measure of surprise or messiness. High entropy means the outcome is unpredictable and spread out (very messy); low entropy means the outcome is predictable and concentrated (very tidy). The big question for modern mathematicians was: Does this "no free lunch" rule still hold for fuzzy clouds? If you have a random cloud that is surprisingly tidy when you add two of them together, does that force the product cloud to be messy? And if so, just how messy? This paper dives into that question, proving that yes, the rule holds, and quantifying exactly how much messiness is forced upon you.

The Entropic Sum-Product Phenomenon: A Tale of Two Mixes

In this paper, author Rupert Li tackles a problem that sits at the intersection of two massive fields: combinatorics (the study of counting and arranging) and information theory (the study of data and uncertainty). The story begins with a simple setup: take a random variable $X$ (a cloud of numbers with probabilities) and create a copy of it, $X'$ . Now, mix them up in two ways: add them ( $X + X'$ ) and multiply them ( $X \times X'$ ).

The central mystery is this: Can you design a cloud $X$ such that both the sum and the product remain surprisingly tidy (low entropy)? The paper proves that you cannot. No matter how you arrange your cloud, at least one of the two mixes must become significantly messier than the original.

The Big Discovery
The paper establishes a precise mathematical rule for this messiness. It proves that the larger of the two entropies (either the sum or the product) must be at least $8/7$ times the entropy of the original cloud, minus a small correction term that grows very slowly (logarithmically) as the cloud gets bigger.

In plain English: If your original cloud has an entropy of $H$ , then the messiest of the two new clouds (sum or product) will have an entropy of at least roughly $1.14 \times H$ . This is a strict "no free lunch" guarantee. You cannot keep both the sum and the product tidy; one of them is forced to expand by about 14%.

Why This Was Hard to Prove
Previous attempts to prove this had hit a wall. Earlier work could only show that the messiness increased by a tiny, almost negligible amount, or it relied on a specific type of "messiness" (called min-entropy) that didn't always match the general "messiness" (Shannon entropy) mathematicians care about. There were tricky examples where the cloud looked tidy in one way but was actually a trap, causing previous formulas to fail.

The author's breakthrough was a clever trick called dyadic decomposition. Imagine your cloud of numbers is a jumbled pile of sand. Instead of trying to analyze the whole pile at once, the author sorts the sand grains into buckets based on their size (probability). Then, they treat each bucket as if it were a perfectly uniform pile of sand. This "uniformization" technique allowed the author to bypass the tricky traps that had stumped previous researchers.

The Two-Part Strategy
To get the $8/7$ result, the paper splits the problem into two scenarios, like a detective checking two different alibis:

The "Small Doubling" Case: This happens when the sum of the clouds is only slightly messier than the original. The author uses a technique inspired by a famous mathematician named Solymosi to show that if the sum is tidy, the product must be very messy. This part of the proof is the heavy lifter that pushes the coefficient up to the $8/7$ mark.
The "Large Doubling" Case: This happens when the sum is already quite messy. Here, the author uses a different set of tools (involving geometry and points on a plane) to show that even in this scenario, the product still has to be messy enough to satisfy the rule.

By combining these two cases, the author covers all possibilities, proving that the rule holds no matter how the cloud is arranged.

What the Paper Rules Out
The paper explicitly rules out the idea that the coefficient could be 1 (meaning no increase in messiness at all). It also clarifies that while a coefficient of $1/3$ (or $4/3$ in the formula) was the theoretical limit for a specific type of example, the general rule is slightly weaker, settling firmly at $1/7$ (or $8/7$ in the final formula). The author also corrects a few errors found in previous papers, showing that some earlier formulas were slightly off because they didn't account for the possibility of a number being exactly zero.

How Sure Are We?
This is not a guess or a simulation. The paper provides a rigorous, step-by-step mathematical proof. The result is a theorem, meaning it is logically certain within the rules of mathematics. The author even provides specific numbers for the "correction terms" (constants like 18 and 63) that appear in the formula, ensuring the result is concrete and usable.

The Bottom Line
Rupert Li has successfully answered a question that had been open for some time: Yes, the sum-product phenomenon exists in the world of probability clouds. If you try to keep your numbers tidy when adding them, multiplication will force them to scatter. The paper quantifies this scattering, proving that the messiness must increase by a factor of at least $8/7$ . It's a victory for the idea that in mathematics, you can't have your cake and eat it too—especially when it comes to mixing numbers.

Technical Summary: The Entropic Sum-Product Phenomenon

Problem Statement
This paper addresses the existence of an "entropic sum-product phenomenon," a probabilistic analog to the celebrated combinatorial sum-product conjecture of Erdős and Szemerédi. In the combinatorial setting, the conjecture asserts that a finite set $A$ of real numbers cannot simultaneously have a small sumset $A+A$ and a small product set $A \cdot A$ . Specifically, $\max\{|A+A|, |A \cdot A|\} \ge |A|^{1+\epsilon}$ for some $\epsilon > 0$ .

The paper investigates the corresponding question for discrete real-valued random variables $X$ with finite Shannon entropy $H(X)$ . Let $X'$ be an independent copy of $X$ . The central question, posed by Goh, is whether there exists a constant $\delta > 0$ such that:
$\max\{H(X + X'), H(XX')\} \ge (1 + \delta - o(1))H(X)$
as $H(X) \to \infty$ . Previous work by Gavalakis, Goh, and Kontoyiannis established bounds involving min-entropy ( $H_\infty$ ), which failed to yield a strictly positive $\delta$ because min-entropy can remain bounded while Shannon entropy grows arbitrarily large. This paper aims to prove the conjecture with an explicit $\delta > 0$ using only Shannon entropy.

Methodology
The author employs a multi-stage approach combining information-theoretic inequalities with combinatorial incidence geometry techniques, adapted for the entropic setting.

Dyadic Uniformization: To overcome the limitation of min-entropy, the author utilizes a dyadic decomposition of the random variable's probability mass function. By partitioning the support into "flat" pieces (sets where probabilities are roughly uniform), they approximate the distribution as a mixture of uniform distributions. This process incurs an entropy cost of $O(\log H(X))$ , which is negligible for the asymptotic result. This technique allows the application of tools requiring uniformity without being hindered by heavy atoms in the original distribution.
Zero-Free Reduction: The analysis is first conducted on "zero-free" random variables (where $P(X=0)=0$ ). The author derives bounds for these variables and then reincorporates the possibility of an atom at zero using a truncation and conditioning argument, showing that the presence of zero does not destroy the sum-product gain, provided the entropy is sufficiently large.
Small-Doubling vs. Large-Doubling Regimes: The proof splits into two cases based on the "additive doubling" ratio $e_u = \frac{H(X+X')}{H(X)} - 1$ :
- Small-Doubling ( $e_u \le 1/7$ ): The author adapts Solymosi's combinatorial argument, which bounds multiplicative energy using sumset cardinalities. They translate this into an entropic inequality (Theorem 1.6), establishing a linear lower bound on the product entropy $e_m = \frac{H(XX')}{H(X)}$ in terms of $e_u$ . This relies on a new "linear entropic Elekes–Ruzsa" theorem.
- Large-Doubling ( $e_u \ge 1/7$ ): For cases where the sumset entropy is large, the author utilizes a point-plane incidence bound (Rudnev's bound) adapted to entropy. They establish a lower bound on $H(X(Y+Z))$ for uniform variables and extend it to general variables via the uniformization technique. This yields a different linear bound (Theorem 1.7) which is superior when $e_u$ is large.
Correction of Previous Errors: The author identifies and corrects errors in the upper bounds used in prior work (specifically in M´ath´e and O'Regan and Gavalakis et al.) regarding the entropy of products of sums $H(X(Y+Z))$ . They provide a corrected functional submodularity inequality that accounts for atoms at zero, which is crucial for the rigorous derivation of the large-doubling bound.

Key Contributions and Results

Proof of the Conjecture: The main result (Theorem 1.5) confirms the existence of such a $\delta$ , proving that for sufficiently large $H(X)$ :
$\max\{H(X + X'), H(XX')\} \ge \frac{8}{7}H(X) - O(\log H(X))$
This establishes $\delta = 1/7$ .
Optimal Coefficient for Zero-Free Laws: The paper proves that for zero-free laws, the bound holds with $\delta = 1/7$ (Theorem 1.5). However, the author notes that without the "Solymosi half" (the small-doubling argument), the result would only yield $\delta = 1/9$ .
Linear Entropic Elekes–Ruzsa Theorems: The paper introduces two new theorems (Theorems 1.6 and 1.7) that provide linear lower bounds on the product entropy relative to the sum entropy. These are described as having independent interest.
Generalization to Arbitrary Fields: The author notes that their arguments for the large-doubling case extend to arbitrary fields of characteristic 0, yielding $\delta = 1/9$ in those settings.

Significance and Claims
The paper claims to answer a specific open question posed by Goh regarding the existence of a coefficient strictly larger than 1 in the entropic sum-product phenomenon. The significance lies in:

Bridging Combinatorics and Information Theory: It successfully translates deep combinatorial results (Solymosi's bound on multiplicative energy) into the entropic domain, despite the lack of direct analogs for certain combinatorial tools in the entropy setting.
Overcoming Min-Entropy Limitations: By introducing a dyadic uniformization technique, the author bypasses the dependency on min-entropy that plagued previous attempts, allowing the result to hold for general discrete distributions with finite Shannon entropy.
Tightness and Future Directions: The author acknowledges that the optimal $\delta$ is likely $1/3$ , matching the combinatorial bound and the known upper bound from a specific counterexample. They conjecture that the entropic analog of Solymosi's inequality (Conjecture 1.10) holds, which would imply $\delta = 1/3$ . The paper frames the current result ( $\delta = 1/7$ ) as a significant step toward this optimal bound, achieved by combining two distinct linear bounds that cover different regimes of additive doubling.

The paper does not claim to solve the full conjecture ( $\delta = 1/3$ ) but establishes the first quantitative result with a strictly positive $\delta$ that depends only on Shannon entropy, thereby confirming the existence of the entropic sum-product phenomenon.

The Entropic Sum-Product Phenomenon: A Tale of Two Mixes

More like this