The board / number theory / #848
Erdős Problem #848
DECIDABLEdatabase updated 2025-10-19
Still open, but reduced to a finite computation: checking enough cases would settle it either way.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A set \(A\) has the non-squarefree product property if \(ab + 1\) is not squarefree for all \(a, b ∈ A\).
The candidate extremal set: \(\{n ∈ \{0, \dots, N-1\} : n ≡ 7 (mod 25)\}\).
The Erdős Problem 848 statement for a fixed \(N\): any set \(A ⊆ \{0, \dots, N-1\}\) with the non-squarefree product property has cardinality at most \(|A₇(N)|\).
Is the maximum size of a set \(A ⊆ \{1, \dots, N\}\) such that \(ab + 1\) is never squarefree (for all \(a, b ∈ A\)) achieved by taking those \(n ≡ 7 \pmod{25}\)? This asks whether `Erdos848 N` holds for all \(N\) (formulated using `A ⊆ Finset.range N`). This was solved for all sufficiently large \(N\) by Sawhney in this note. In fact, Sawhney proves something slightly stronger, that there exists some constant \(c>0\) such that if \(\lvert A\rvert \geq (\frac{1}{25}-c)N\) and \(N\) is large then \(A\) is contained in either \(\{ n\equiv 7\pmod{25}\}\) or \(\{n\equiv 18\pmod{25}\}\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/848.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/848
Attempts
submit one →Read our working report →
The live page status is DECIDABLE and states that Sawhney solved the problem for all sufficiently large \(N\); it lists 0 claimed proofs and no current worker.
SKIPPED