Abstract
In 1983, Erdős and Szemerédi demonstrated that any set of $n$ distinct integers produces either $n^{1+\epsilon}$ distinct sums or $n^{1+\epsilon}$ distinct products, conjecturing a lower bound of $n^{2-o(1)}$. This work explores a generalization of this problem where sums and products are restricted to the edges of a graph $G$. We focus on sparse graphs, specifically matchings, and show that lower bounds in this restricted setting have profound implications for the original conjecture. By reducing the sum-product of a matching to the number of translates of a set into perfect squares—a problem dating back to Euler—we utilize elliptic curve analysis to provide new lower and upper bounds. Additionally, we establish tight bounds for sum-sets along expander graphs.
Introduction
The Erdős-Szemerédi sum-product conjecture is a cornerstone of additive combinatorics, asserting that a set of numbers cannot be simultaneously well-structured under both addition and multiplication. While the "dense" version (considering all pairs in a set) has seen significant progress, the "sparse" version—where operations are performed only along the edges of a graph $G$—remains less understood.
This paper investigates the behavior of sums and products along sparse graphs, particularly matchings (sets of $n/2$ disjoint edges). We demonstrate that the integers $\mathbb{Z}$ exhibit unique properties in this context that do not exist in the real numbers $\mathbb{R}$, where the minimal sum-product for a matching is a trivial $\Theta(\sqrt{n})$.
The Matching-to-Dense Link
A central contribution of this research is the formalization of the relationship between sparse and dense graphs. We prove that the matching is essentially a bottleneck for the entire sum-product problem. Specifically, Theorem 1 establishes that: $$SP_{\mathbb{Z}}(M) = O\left(\frac{SP_{\mathbb{Z}}(K_n)}{\sqrt{n}}\right)$$ This implies that any improvement in the lower bound for a matching of $n$ edges (of the form $n^{1/2+\delta}$) directly translates to an improved lower bound for the original Erdős-Szemerédi conjecture ($n^{1+\delta}$). Thus, sparse graphs serve as a "magnifying glass" for the broader problem.
Arithmetic Geometry and Euler’s Square Translates
To analyze the sum-product of matchings, we reduce the problem to a question in classical number theory: how many integers $x$ can shift a fixed set $A$ into the set of perfect squares? This problem was originally studied by Leonhard Euler.
Using modern tools from arithmetic geometry, specifically the Mordell-Weil Theorem and the analysis of the rank of elliptic curves, we extend Euler's observations. We show that for certain sets of three integers, there exist infinitely many such translates. Furthermore, by invoking the Bombieri-Lang conjecture, we derive a conditional lower bound for the sum-product of a matching at $\Omega(n^{4/7})$, which would imply a sum-product exponent of $1 + 1/14$ for the complete graph.
The Expander Paradox
Expander graphs are typically associated with high connectivity and rapid "mixing." One might expect that sums along the edges of an expander would necessarily result in a large set. However, we provide a surprising counter-result. Using the probabilistic method and Cayley sum graphs, we prove that it is possible to assign integers to the vertices of an expander such that the resulting sum-set is remarkably small—only $\Theta(\log n)$. This result provides a tight bound and highlights the limits of expansion properties in preventing additive structure.
Conclusion and Future Directions
This work bridges the gap between discrete mathematics and algebraic geometry, showing that the complexity of integer sum-products is deeply tied to the distribution of perfect squares. While the "ultimate" conjecture—that the sum-product of a matching should be nearly linear ($n^{1-o(1)}$)—remains open, this paper provides a new framework for progress.
A significant remaining challenge is the "finiteness of $F_k$": determining if there is a fixed set size $k$ beyond which no two sets $X, Y$ can satisfy $x+y \in \text{Squares}$ for all pairs. Solving this would likely require new insights into incidence geometry and the arithmetic of higher-genus curves.
Summary updated