Sums and products along sparse graphs

Noga Alon, Omer Angel, Itaï Benjamini, Eyal Lubetzky

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})$.

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

Abstract

In their seminal paper from 1983, Erdős and Szemerédi showed that any $n$ distinct integers induce either $n^{1+ε}$ distinct sums of pairs or that many distinct products, and conjectured a lower bound of $n^{2-o(1)}$. They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given graph $G$ on $n$ labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least $n^{1+ε}$ edges. In this work, we consider sum-product theorems for sparse graphs, and show that this problem has important consequences already when $G$ is a matching (i.e., $n/2$ disjoint edges): Any lower bound of the form $n^{1/2+δ}$ for its sum-product over the integers implies a lower bound of $n^{1+δ}$ for the original Erdős-Szemerédi problem. In contrast, over the reals the minimal sum-product for the matching is $Θ(\sqrt{n})$, hence this approach has the potential of achieving lower bounds specialized to the integers. We proceed to give lower and upper bounds for this problem in different settings. In addition, we provide tight bounds for sums along expanders. A key element in our proofs is a reduction from the sum-product of a matching to the maximum number of translates of a set of integers into the perfect squares. This problem was originally studied by Euler, and we obtain a stronger form of Euler's result using elliptic curve analysis.
BibTeX
@inproceedings{alon2011sums,
  author = {Noga Alon and Omer Angel and Itaï Benjamini and Eyal Lubetzky},
  title = {{Sums and products along sparse graphs}},
  booktitle = {Israel},
  year = {2011},
  doi = {10.1007/s11856-011-0170-x},
}

Loading related content...

Figure