Erdős Problem #808

Let \(c,\epsilon>0\) and \(n\) be sufficiently large. If \(A\subset \mathbb{N}\) has \(\lvert A\rvert=n\) and \(G\) is any graph on \(A\) with at least \(n^{1+c}\) edges then \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \geq \lvert A\rvert^{1+c-\epsilon},\] where \[A+_GA = \{ a+b : (a,b)\in G\}\] and similarly for \(A\cdot_GA\). This strong conjecture of Erdős and Szemerédi [ErSz83] strengthens Erdős Problem 52 (`Erdos52.erdos_52`, the case of the complete graph). It was disproved by Alon, Ruzsa, and Solymosi [ARS20, Theorem 3]: for arbitrarily large \(m\) there are a set of integers \(A\) with \(\lvert A\rvert=m\) and a graph on \(A\) with \(\gg m^{5/3}/(\log m)^{1/3}\) edges such that \(\lvert A+_GA\rvert+\lvert A\cdot_GA\rvert \ll (m\log m)^{4/3}\). The statement below is the negation of the conjecture. A set \(A\) with a graph on it is given by a finite type `V`, a graph `G` on `V` and an injection `a : V ↪ ℕ` (so \(A\) is the image of `a` and \(n\) is `Fintype.card V`). Here `ℕ` contains \(0\); see `erdos_808.variants.positive` for positive integers.