The sum-product problem for small sets II

This paper extends previous results on the sum-product problem by proving that any set of 10 or 11 natural numbers must generate at least 30 or 34 distinct pairwise sums or products, respectively, while providing a classification of extremal sets and analyzing additive structures in small subsets of generalized geometric progressions.

The Gist

Imagine you have a small group of friends, and you want to see how "social" they are in two different ways:

1. The Sum Party: You pair everyone up and add their ages together. How many different total ages do you get?
2. The Product Party: You pair everyone up and multiply their ages. How many different total products do you get?

In the world of math, there's a famous puzzle called the Sum-Product Problem. The big question is: Can a group of numbers be "boring" in both parties at the same time?

Mathematicians have long suspected that the answer is no. If your group is arranged in a way that creates very few different sums (like a neat line of numbers: 1, 2, 3, 4...), then the products will explode into a huge variety. Conversely, if the products are few and neat (like a geometric line: 1, 2, 4, 8...), the sums will be huge and messy.

This paper is the latest chapter in a story about finding the exact "tipping point" for small groups of numbers.

The Story So Far

Previous researchers had figured out the rules for groups of 2 to 9 people. They knew exactly how many different sums or products you must have. But when they got to 10 people, the math got messy.

The best example they had for a group of 10 was:
{1, 2, 3, 4, 6, 8, 9, 12, 16, 18}

If you add these up in pairs, you get 30 different sums.
If you multiply them in pairs, you get 29 different products.
The "worst-case scenario" (the most boring party possible) was 29. So, the big question was: Is it possible to find a group of 10 numbers that is even more boring, with only 29 sums AND 29 products?

The Detective Work: How They Solved It

The authors of this paper acted like digital detectives. They didn't just guess; they built a computer program to hunt down every possible "boring" group of numbers.

Here is how they did it, using a simple analogy:

1. The "Logarithm" Translation
Multiplication is hard to visualize. Addition is easy. The researchers used a mathematical trick (logarithms) to turn the "Product Party" into a "Sum Party."

• Analogy: Imagine you have a secret code where multiplying numbers is actually just adding their "code values." Now, instead of looking for groups with few products, they just looked for groups with few sums in this new code world.

2. The "Shape" Hunt
They knew from previous math that if a group has very few sums, the numbers must be arranged in a very specific shape.

• Analogy: Think of the numbers as dots on a grid. If the dots are boring (few sums), they must form a straight line, or a very specific "L" shape, or a "T" shape. They can't be scattered randomly.
• The researchers wrote a computer algorithm (called WinnersSearch) to generate every single possible shape a group of 10 or 11 dots could take without being too "noisy."

3. The "Collision" Check
Once they had the shapes, they had to check if the numbers inside those shapes could actually exist in the real world.

• Analogy: Imagine you are building a tower of blocks. Sometimes, two different ways of stacking blocks result in the exact same height. In math, this is called a "collision" (e.g., $2 + 6 = 3 + 5$).
• The researchers used a super-computer to check every possible "collision" for every possible shape. They asked: "If we pick these specific numbers, do we accidentally create too many sums?"

4. The Verdict
After running millions of calculations, they found the answer:

• For 10 numbers: It is impossible to have fewer than 30 sums or 30 products. The group {1, 2, 3, 4, 6, 8, 9, 12, 16, 18} is the only way (up to scaling) to get as low as 30. You cannot get down to 29.
• For 11 numbers: The limit is 34. The group {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24} is the unique champion of boredom.

Why This Matters

This isn't just about counting numbers. It's about understanding the fundamental structure of numbers.

• The "Uniqueness" Factor: The paper proves that the "boring" groups aren't just random accidents. There is a very specific, unique architecture to them. If you want to be as boring as possible, you must build your group exactly like {1, 2, 3, 4, 6, 8, 9, 12, 16, 18}. There is no other way.

The Future: The "Breaking Point"

The paper ends with a cliffhanger. They tried to do this for 12 numbers, and it got much harder. The "shapes" of the numbers started getting complicated in 3 dimensions (like a cube instead of a flat sheet).

• Analogy: For 10 and 11 people, the party was happening on a 2D dance floor. For 12 people, the party moved into a 3D room, and the math got so complex that their current tools couldn't solve it yet.

In a Nutshell

This paper is a victory for computational mathematics. It proves that for small groups of numbers, there is a strict limit to how "uninteresting" they can be. If you try to make a group of 10 numbers that is boring in both addition and multiplication, you will fail—you are forced to have at least 30 distinct results. And if you do manage to hit that limit, your group of numbers will look exactly like the one the authors found, and no other.

It's like saying: "If you try to build the quietest possible house, you can only build it in one specific blueprint. Any other blueprint will be too noisy."

Technical Summary

Here is a detailed technical summary of the paper "The Sum-Product Problem for Small Sets II" by Antis et al.

1. Problem Statement

The paper addresses the Sum-Product Problem in additive combinatorics, specifically focusing on small finite sets of natural numbers ($A \subseteq \mathbb{N}$). The central question is to determine the minimum possible value of the maximum of the size of the sumset ($A+A$) and the product set ($AA$).

The quantity of interest is defined as:
$$SP(k) = \min_{A \subseteq \mathbb{N}, |A|=k} \left( \max \{ |A+A|, |AA| \} \right)$$

While the asymptotic behavior of $SP(k)$ is a major open conjecture (Erdős–Szemerédi conjecture: $SP(k) = k^{2-o(1)}$), this paper focuses on determining the exact values of $SP(k)$ for small integers $k$, specifically extending previous work from $k \le 9$ to $k=10$ and $k=11$.

2. Methodology

The authors employ a hybrid approach combining structural classification theorems from additive number theory with extensive computational enumeration using Python.

A. Structural Classification (Freiman's Theorems)

The proof relies on Freiman's inverse theorems, which describe the structure of sets with small doubling (few distinct sums).

• Theorem 1.2 & 1.3: If a set has a small sumset, it is either contained in a short arithmetic progression (AP) or is a union of two APs with the same step size.
• Logarithmic Transformation: By taking logarithms, the product set problem is transformed into a sumset problem. A set with few products corresponds to a set $L = \{\log_r(a) : a \in A\}$ with few sums.
• Reduction to 2D Structures: If a set does not contain a large subset in a single geometric progression (GP), the logarithmic image $L$ must have a specific 2-dimensional structure. The authors classify these structures as subsets of:
  • $G_1 = \{r^m s^n : 0 \le m \le 7, n \in \{0, 1\}\}$ (Two rows)
  • $G_2 = \{r^m s^n : 0 \le m \le 3, 0 \le n \le 2\}$ (Three rows)
    where $r, s > 1$ and $\log_r(s) \notin \mathbb{Q}$.

B. Computational Algorithms

The authors developed custom algorithms to handle the combinatorial explosion of possibilities:

1. WinnersSearch Algorithm: A recursive backtracking algorithm that constructs sets $P \subseteq \mathbb{Z}^2$ (representing exponents of $r$ and $s$) element by element. It enforces constraints on the number of distinct sums ($|P+P|$) to prune the search space. This classifies all possible structural forms of sets with small product sets.
2. CollisionCheck Algorithm: To bound the size of the sumset $|A+A|$ for sets in $G_1$ or $G_2$, the authors analyze "collisions" (additive quadruples where $a+b=c+d$).
   • They formulate collisions as polynomial equations in $r$ and $s$ (e.g., $r^a + r^b = s(r^c + r^d)$).
   • Using resultants and GCDs, they identify "exceptional pairs" $(r, s)$ where the number of collisions is higher than the generic case.
   • They distinguish between single collisions (one family of solutions) and double collisions (two families, e.g., $1+r^3 = s+rs$and$1+r^2 = r+s$).

3. Key Contributions and Results

A. Exact Values for $SP(10)$ and $SP(11)$

The paper establishes the following exact values:

• $SP(10) = 30$
• $SP(11) = 34$

B. Uniqueness of Extremal Sets

The authors prove that the sets achieving these bounds are unique up to scaling (multiplication by a constant):

• For $k=10$: The unique set is $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18\}$.
  • $|A+A| = 30$
  • $|AA| = 29$
• For $k=11$: The unique set is $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24\}$.
  • $|A+A| = 34$
  • $|AA| = 32$

C. Classification of "Near-Miss" Sets

The paper provides a rigorous classification of sets that almost minimize the sum-product:

• Real Numbers: They classify sets of 10 real numbers with at most 29 sums that do not contain 8 elements in an AP. These sets must be subsets of specific 2D geometric progressions.
• Exceptional Pairs: The computation identified 155 exceptional pairs $(r, s)$ for the 2-row case ($G_1$) and 75 exceptional pairs for the 3-row case ($G_2$) where the standard collision bounds do not hold. The authors verified that even for these exceptional pairs, the sumset size remains above the threshold unless the set is a scaling of the unique extremal examples.

D. Extension to $k=12$ and $k=13$

• $k=12$: The authors conjecture $SP(12) = 41$, based on the set $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32\}$. They prove that any set with $|A|=12$ and $|AA| \le 41$ must be contained in a 1D or 2D geometric progression structure.
• $k=13$: They note a structural shift. The best example for $k=13$ involves a 3-dimensional structure (union of three GPs with AP starting points), suggesting that 2D methods are insufficient for $k \ge 13$.

4. Significance

• Resolution of Small Cases: This work closes the gap for $k=10$ and $k=11$, which were previously open despite the resolution of $k \le 9$. It confirms the conjecture that the "greedy" construction of sets based on small integers yields the optimal sum-product behavior.
• Methodological Advancement: The paper demonstrates the power of combining deep structural theorems (Freiman) with computer-assisted proofs. The use of resultants to isolate exceptional algebraic cases and the recursive search for structural forms provides a template for solving similar extremal problems in additive combinatorics.
• Sharpness and Classification: Unlike asymptotic results which provide bounds, this paper provides sharp results with a complete classification of the extremal sets, offering insight into the specific algebraic structures (2D geometric progressions) that minimize the sum-product function.
• Limit of Current Techniques: The discussion on $k=13$ highlights the limitations of 2D geometric progression analysis, pointing toward the need for higher-dimensional structural theorems for larger sets.

5. Conclusion

The paper successfully proves that for sets of size 10 and 11, one cannot simultaneously have fewer than 30 and 34 distinct sums/products, respectively. The extremal sets are unique and possess a specific structure derived from the union of geometric progressions. The work serves as a bridge between classical additive combinatorics and modern computational verification, setting the stage for future investigations into larger $k$ where higher-dimensional structures become dominant.