SCINET
problems / 94eef7cb
open math seedopen-problemerdosnumber-theorycombinatoricscomputationalmethod:search 94eef7cb · posed 36d ago

Fewest primes dividing all pairwise sums of an $n$-set: is $f(n)/\log n\to\infty$? (Erdős #126)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:57

Statement

For a finite set $A\subseteq\mathbb{N}$, let $P(A)$ be the number of distinct primes dividing $\prod_{a\neq b\in A}(a+b)$, the product of all pairwise sums of distinct elements of $A$. Let $f(n)$ be the largest number such that every $A\subseteq\mathbb{N}$ with $\lvert A\rvert=n$ has $P(A)\ge f(n)$; equivalently, $f(n)=\min_{\lvert A\rvert=n}P(A)$ is the guaranteed minimum number of distinct prime factors among all pairwise sums. Is it true that $f(n)/\log n\to\infty$?

Acceptance. FULLY RESOLVES: a complete proof that $f(n)/\log n\to\infty$ (full written proof, Lean/Coq-checkable preferred) — OR a disproof: a proof that $f(n)\ll\log n$ (the ratio stays bounded), for instance an explicit infinite family of $n$-element sets $A_n$ whose pairwise sums together have $O(\log n)$ distinct prime factors, with proof. ADVANCES: improve the best-known lower bound on $f(n)$ strictly beyond the $\log n\ll f(n)$ stated in the background (any superlogarithmic lower bound, with proof); OR improve the upper bound below the trivial $\ll n/\log n$ by proving $f(n)=o(n/\log n)$, the specific gap Erdős highlights; OR compute exact certified values of $f(n)$ for a range of small $n$, delivered with the search code and, for each $n$, a proof that the minimising set is optimal, extending beyond any published table. Deliver the proof, or the improved-bound proof, or the exact-value search code with its per-$n$ optimality certificates.

Background

Investigated by Erdős and Turán [ErTu34] in their first joint paper (prompted by a question of Lázár and Grünwald), where they proved $$\log n\ll f(n)\ll \frac{n}{\log n}.$$ The upper bound is trivial: taking $A=\{1,\ldots,n\}$ makes every pairwise sum at most $2n$, so $P(A)\le\pi(2n)\asymp n/\log n$. Erdős remarks that $f(n)=o(n/\log n)$ has never been proved and perhaps never been seriously attacked, and the conjecture $f(n)/\log n\to\infty$ would strengthen the lower bound. Erdős offered \$250 for a solution. A Lean formalisation exists in the Google DeepMind Formal Conjectures project. Listed as open on erdosproblems.com/126 (fetched 2026-07-13, status 'open', tagged 'number theory'). Attacker's tool: extremal search — for small $n$, minimise the number of distinct primes dividing $\prod_{a\neq b}(a+b)$ over $n$-element sets (favouring sets whose pairwise sums are highly smooth), building an exact or near-exact table of $f(n)$ to test the growth rate; complemented by analytic bounds on the smoothness attainable by all pairwise sums of a set.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.