on sum-product in finite fields via entropy

Overview

This post explores a recent proof of the sum-product estimate $|A+A|+|A\cdot A|\gtrsim |A{|}^{6/5}$ for $A\subset {\mathbb{F}}_p$ using an entropy-based framework. As discussed by Pohoata (2026), this approach bridges incidence geometry and Shannon entropy to recover classical bounds with a more flexible combinatorial toolkit.

🏷️ Introduction: The Sum-Product Problem

The sum-product phenomenon in finite fields states that a set $A\subset {\mathbb{F}}_p$ cannot be simultaneously structured under both addition and multiplication. Formally, for $|A|\le p^{1/2}$, one expects $|A+A|+|A\cdot A|$ to be significantly larger than $|A|$.

The exponent $6/5$ was first established by Roche-Newton, Rudnev, and Shkredov (Roche-Newton, Rudnev & Shkredov, 2016) using the Szemerédi-Trotter theorem (or its finite field variants). Pohoata’s recent exposition reformulates this using Entropy inequalities, following a strategy similar to Máthé and O’Regan (Máthé & O’Regan, 2025).

Fundamental Definitions

• Shannon Entropy: $H(X)=\sum p_i\log \frac{1}{p_i}$, representing the average surprise.
• Collision Entropy: $H_2(X)=-\log \sum p_i^2$, related to the probability that two independent samples collide.
• The Cardinality Link: For any discrete random variable $S$ taking values in a set $\mathcal{S}$, the entropy is maximized when $S$ is uniform, giving the fundamental bound $H(S)\le \log |\mathcal{S}|$. In this framework, we use entropy as a proxy for the “log-size” of sets.

The Entropy Inequality: $H\ge H_2$

By Jensen’s Inequality, since $f(x)=-\log x$ is convex, we have $\mathbb{E}[-\log p(X)]\ge -\log \mathbb{E}[p(X)]$, which yields:

$$H(X)\ge H_2(X)$$

This allows us to use energy bounds from incidence geometry (which naturally bound $H_2$) to provide lower bounds on Shannon entropy, where we can then apply the power of submodularity.

📉 Step-by-Step Breakdown

Step 1: The Geometric Floor

The first step is to establish that the “rectangular area” $\Delta (a_1,a_2,a_3,a_4)=(a_1-a_3)(a_2-a_4)$ takes many distinct values.

Lower Bound from Incidence Geometry

• Energy Definition: We define the Energy $E(A)$ as the number of “collisions” under the map $\Delta$ for quadruples $\mathbf{a}\in A^4$:

$$E(A)=|\{(\mathbf{a},{\mathbf{a}}^{\prime })\in A^4\times A^4:\Delta (\mathbf{a})=\Delta ({\mathbf{a}}^{\prime })\}|$$

• The Energy Link: We know from the Guth-Katz/Kollár framework that for $A\subset {\mathbb{F}}_p$, $E(A)\lesssim |A{|}^{5.5}$.
• Entropy Translation: By the relationship between Shannon entropy and collision entropy:

$$H(\Delta )\ge H_2(\Delta )=-\log \left(\frac{E(A)}{(|A{|}^4{)}^2}\right)=8\log |A|-\log E(A)$$

Substituting $E(A)\lesssim |A{|}^{5.5}$ yields $H(\Delta )\ge 2.5\log |A|$. This provides the geometric floor for the entropy.

Step 2: The Submodularity Gadget (Encoding)

To upper bound $H(\Delta )$, we define two different encodings of the 4-tuple $\mathbf{a}=(a_1,a_2,a_3,a_4)\in A^4$:

1. $U=(a_1+a_2,a_3+a_4,a_1{a}_3,a_2{a}_4)$
2. $V=(a_1+a_4,a_2+a_3,a_1{a}_2,a_3{a}_4)$

The Encoding Strategy

Injectivity: The tuple $(a_1,a_2,a_3,a_4)$ is uniquely determined by the pair $(U,V)$. In ${\mathbb{F}}_p$, this map is injective (up to a small set of degeneracies), meaning $H(a_1,a_2,a_3,a_4)=H(U,V)$. Submodularity: By Shannon’s inequality $H(U,V)\le H(U)+H(V)$.

Step 3: The Submodularity Gadget (Combinatorial Link)

To upper bound the entropy, we use a “submodularity gadget” involving four i.i.d. variables $X_1,X_2,X_3,X_4$ uniform on $A$.

The Rigorous Ceiling

For $Z=(X_1+X_2)(X_3+X_4)$ and $W=(X_1,X_2,X_3,X_4)$, the submodularity lemma $H(Z)+H(W)\le H(U)+H(V)$ implies:

$$H(Z)+4\log |A|\le 2\log |A+A|+3\log |A\cdot A|$$

Here $U=(X_1+X_2,X_3+X_4)$ and $V=(X_1{X}_3,X_1{X}_4,X_2{X}_3)$. Since $X_2{X}_4=(X_1{X}_4\cdot X_2{X}_3)/(X_1{X}_3)$, $Z$ is a function of $V$.

Step 4: The End-Game Calculation

The final step is to combine the “geometric floor” and the “combinatorial ceiling.”

The 6/5 Result

Substituting the entropy floor into the submodularity gadget:

1. Floor: $H(Z)\ge 2\log |A|$ (from the point-plane incidence bound on the number of collisions for $(X_1+X_2)(X_3+X_4)$ being $O(|A{|}^6)$).
2. Combine: $(2\log |A|)+4\log |A|\le 2\log |A+A|+3\log |A\cdot A|⟹6\log |A|\le 2\log |A+A|+3\log |A\cdot A|$.
3. The Exponent: Assuming the balanced case $|A+A|\approx |A\cdot A|\approx |A{|}^{1+k}$:

$$6\log |A|\le 5(1+k)\log |A|⟹1+k\ge \frac{6}{5}$$

This recovers the landmark $6/5$ exponent for the sum-product problem in finite fields.

🛠️ Technical Note: The Guth-Katz/Kollár Framework

Geometric Foundations

• Guth-Katz (2015): Proved that $N$ lines in ${\mathbb{R}}^3$ (with no more than $\sqrt{N}$ in a plane) have at most $O(N^{3/2})$ intersections.
• Kollár (2015): Translated this result to finite fields using algebraic geometry (specifically the arithmetic genus of curves), bypassing the need for the topological methods used in the real-field proof.
• In this proof: The energy of $\Delta$ is bounded by treating the tuples as a configuration of lines in ${\mathbb{F}}_p^3$. The bound $E(A)\lesssim |A{|}^{11/2}$ is the finite-field analog of the Guth-Katz bound, providing the necessary entropy “spread.”

📊 Numerical Verification

• Simulation Code: [[codes/2026 Spring/sum_product_entropy.py]] To visualize the sum-product phenomenon, we can simulate the growth of $|A+A|$ and $|A\cdot A|$ in ${\mathbb{F}}_p$ for various set structures.

Mass Empirical Search (Verified Primes)

To establish a definitive empirical floor, we performed a high-intensity search across 60 strictly verified primes ($p\approx 10^6-2\times 10^6$) where $p-1$ is highly composite. We analyzed thousands of multiplicative subgroups within the sum-product regime ($|A|\le p^{1/2}$).

• Result: The absolute minimum exponent found across all verified subgroups is $\alpha \approx 1.81$ (at $p=1532161$).

Analysis: The result $\alpha \approx 1.81$ represents a stable empirical floor for generic, large primes. This value is nearly $1.5\times$ the theoretical world record of $1.25$. This suggests that while analytical constructions exist that achieve slower growth (often using specifically aligned subsets of integers), for the vast majority of sets and field structures, the additive and multiplicative operations are almost entirely uncorrelated, leading to growth much closer to quadratic than the theoretical minimum. (Note: Apparent ratios significantly below $1.5$ in earlier tests were identified as artifacts of composite moduli or non-unique element counting).

📝 Notes

• Optimal Bounds: The current record is $5/4=1.25$ (Mohammadi-Stevens). Translating that proof into the entropy framework remains an open problem.
• Continuous Analogs: This entropy method is particularly robust when moving to continuous settings (e.g., discretized sets in $\mathbb{R}$) where classical counting often becomes messy.

🔗 See Also

• on the lower bound of Ramsey number --- Both explore the “geometry of information,” using geometric configurations (spheres vs. finite field incidences) to bound combinatorial expansion.

📚 References

🐻  Máthé, A. & O’Regan, W. 2025. Discretised sum-product theorems by Shannon-type inequalities. Journal of the London Mathematical Society 112(6), e70389.

🐻  Roche-Newton, O., Rudnev, M. & Shkredov, I.D. 2016. New sum-product type estimates over finite fields. Advances in Mathematics 293, 589–605.