The board / number theory / #883
Erdős Problem #883
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The coprime graph on \(\mathbb{N}\): two integers are joined by an edge if they are coprime.
For \(A\subseteq \{1,\ldots,n\}\) let \(G(A)\) be the graph with vertex set \(A\), where two integers are joined by an edge if they are coprime. Is it true that if \[|A| > \lfloor n/2 \rfloor + \lfloor n/3 \rfloor - \lfloor n/6 \rfloor\] then \(G(A)\) contains all odd cycles of length \(\leq n/3 + 1\)? A problem of Erdős and Sárközy [ErSa97].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/883.Prizenone
Topicsnumber theory, graph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/883
Attempts
submit one →Read our working report →
Exact exhaustive verification proves the sharp threshold for every nonvacuous n<=36 and every required odd cycle length through C13; the uniform endpoint remains open and requires an arithmetic Hall-e
PARTIAL