The Strong Erdős–Szemerédi conjecture for sums and products along graph edges

About 8 years old · traced to 2018

Let $G_n$ be a graph on $n$ vertices, and let $\mathcal{A}\subset\mathbb{R}$ be an $n$ -element set. Define the sumset and product set along $G_n$ by

\mathcal{A}+_{G_n}\mathcal{A}=\{a_i+a_j:(i,j)\in E(G_n)\},

and

\mathcal{A}\cdot_{G_n}\mathcal{A}=\{a_i a_j:(i,j)\in E(G_n)\}.

Strong Erdős–Szemerédi conjecture. For every $c>0$ and $\varepsilon>0$ , there is a threshold $n_0$ such that, if $n\geq n_0$ , then for every $n$ -element set of reals $\mathcal{A}$ and every graph $G_n$ with at least $n^{1+c}$ edges,

|\mathcal{A}+_{G_n}\mathcal{A}|+|\mathcal{A}\cdot_{G_n}\mathcal{A}|\geq |\mathcal{A}|^{1+c-\varepsilon}.

This conjecture was refuted by Alon, Ruzsa, and Solymosi, so it is no longer open.

References

Primary source

Noga Alon, Imre Ruzsa and Jozsef Solymosi, “On sums and products along the edges, II”, arXiv:2007.12970 (2023).

Additional references

2 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1802.06405.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A construction by Alon, Ruzsa, and Solymosi shows that the conjecture is false, while later work improves the counterexample and leaves only quantitative questions open.

The conjecture proposed a universal lower bound for the combined number of edge-sums and edge-products in sufficiently dense graphs. Alon, Ruzsa, and Solymosi refuted it by constructing arbitrarily large integer sets and graphs with many edges but substantially smaller combined sum-product sets.

Known results

The graph generalization and conjectural framework were recorded in 2009.
For every $0<c<1$ , Alon, Ruzsa, and Solymosi constructed arbitrarily large examples with $\Omega(n^{1+c})$ edges and combined size $O(n^{1+c-\delta})$ , for some $\delta>0$ (2018).
Their construction uses integer sets, hence directly refutes the real-set formulation.
A 2020 follow-up improved the constructions and gave corresponding lower bounds, while leaving a gap between the bounds.

2020 follow-up

The paper On sums and products along the edges, II explicitly records that the Strong Erdős–Szemerédi conjecture was refuted and develops sharper constructions. The remaining gap concerns optimal quantitative bounds, not the truth of the stated conjecture.

arxiv.org · raco.cat · cs.tau.ac.il · en.wikipedia.org · www-cdn.anthropic.com · comptes-rendus.academie-sciences.fr · quantamagazine.org · quantamagazine.org · renyi.hu · ar5iv.labs.arxiv.org · arxiv.org · quantamagazine.org · www-cdn.anthropic.com · mathstodon.xyz · mathstodon.xyz · quantamagazine.org · quantamagazine.org · www-cdn.anthropic.com · quantamagazine.org · quantamagazine.org · quantamagazine.org

Current status (as of September 2026): The conjecture is refuted by the reported Alon–Ruzsa–Solymosi constructions; subsequent work concerns sharper bounds rather than the conjecture’s validity.

Sources

No solutions have been posted yet.