Erdős problem #883 — live audit, literature audit, and exact finite result
Date: 2026-07-27 (UTC)
Claim labels used below:
- [a] elementary-rigorous: proved in this report from definitions.
- [b] rigorous-modulo-named-theorem: a theorem checked in the cited primary source.
- [c] plausible/structural-unverified: a search conclusion, proposed route, or unproved structural assertion.
- [d] computational-only: an exhaustive finite result, with independently run source code.
0. Mandatory live-page and collision audit
I fetched both the live problem page, its
LaTeX-source route, and the separate
three-comment discussion route
through a Bright Data browser on 2026-07-27. Direct-page metadata was not used as
a substitute for this check.
The live page says:
- status OPEN;
- 0 claimed proofs;
- “Currently working on this problem: None”;
- “Interested in collaborating: None”;
- last edited 24 October 2025.
The three comments were also read. They say, in substance:
1. Mark Sellke points out that the second question was solved by Sárközy in
1999, with the sharper displayed scale
\(\ell\gtrsim \log n/\log\log\log n\); the comment says the site was updated.
2. Zach Hunter asks why the paper was described as “rather moving.”
3. Woett supplies the explanation from the exchange between Erdős's last
problem paper and Sárközy's memorial paper.
None of the comments claims a proof of the first question or announces current
work. Thus the mandatory stop condition does not apply.
Verbatim current statement
The following is verbatim from the live LaTeX-source route (only Markdown
display delimiters have been added):
> 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
> \[ > \lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor > \]
> then \(G(A)\) contains all odd cycles of length
> \(\leq \frac{n}{3}+1\)?
>
> Is it true that, for every \(\ell\geq 1\), if \(n\) is sufficiently large and
> \[ > \lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor > \]
> then \(G(A)\) must contain a complete \((1,\ell,\ell)\) triparite graph on
> \(2\ell+1\) vertices?
The page's listed known results are:
- Erdős and Sárközy prove the first conclusion for every odd length at most
\(cn\), for some absolute \(c>0\).
- The threshold is sharp, using the integers divisible by 2 or 3.
- Sárközy solved the second question.
The remainder of this report concerns the still-open first question.
1. Primary-source literature audit
Original results
1. [b] P. Erdős and G. N. Sárközy,
“On cycles in the coprime graph of integers”,
Electronic Journal of Combinatorics 4(2) (1997), R8,
DOI 10.37236/1323.
I downloaded and read the primary PDF. Its Theorem 1 proves that there are
constants \(c,n_0>0\) such that \(|A|>f(n,2)\) forces every
\(C_{2\ell+1}\) with \(\ell\leq cn\). Immediately after the theorem, the
authors ask for the best \(c\) and suggest \(c=1/6\). Since
\(2\ell+1\leq n/3+1\) is exactly \(\ell\leq n/6\), this is the first
question on the live page.
2. [b] G. N. Sárközy,
“Complete tripartite subgraphs in the coprime graph of integers”00359-8),
Discrete Mathematics 202 (1999), 227–238.
I downloaded and read the author-hosted primary PDF. Theorem 1 proves a
\(K(1,\ell,\ell)\) with
\[ \ell=\left\lfloor c\,\frac{\log n}{\log\log\log n}\right\rfloor . \]
This settles the second question (and is stronger than the weaker
\(\gg\log n/\log\log n\) consequence displayed in the main live-page
prose).
3. The page also cites P. Erdős, “Some of my new and almost new problems and
results in combinatorial number theory,” Number Theory (Eger, 1996)
(1998), 169–180, MR 1628841. The publisher's full chapter was paywalled.
I verified the bibliographic record, but make no theorem claim from an
unread copy. Sárközy's 1999 paper itself reproduces and answers the
tripartite question.
Search for later work
[c: search-negative, not a proof of nonexistence] I searched exact phrases
and formula fragments including “coprime graph” with “all odd cycles,”
“\(f(n,2)\),” “\(n/3+1\),” and “\(1/6\).” I also queried the DOI citation graph
in both OpenAlex and Semantic Scholar. Semantic Scholar returned 31 citing
records (including duplicate versions), while OpenAlex returned 20. I screened
all titles/metadata and opened the plausibly relevant primary texts. The
relevant-looking later items address different questions:
- J.-H. de Wiljes,
“Cycles in the coprime hypergraph of integers”
(2019), explicitly says its \(k\geq2\) hypergraph results do not imply the
Erdős–Sárközy graph findings.
- E. Berkove and M. Brilleslyper,
“Subgraphs of coprime graphs on sets of consecutive integers”
(2022), studies cliques and bicliques in consecutive intervals, not dense
induced subsets and their odd-cycle spectrum.
- S. Banerjee,
arXiv:2506.10583 (2025), studies
connectivity, crossing number, and adjacency spectrum of the full graph
on \([n]\).
- G. Batta and L. Hajdu,
“Minimal common factor graphs containing all graphs of order \(k\)”
(2026), studies universal induced representations in the complementary
common-factor graph.
- Z. Du, W. Xi, Z. Deng, and L. Ma,
“Prime Certificates for Exact Vertex-Coprime Ramsey Numbers,” arXiv:2605.26815
(2026), solves vertex/edge coloring Ramsey parameters. Its literature
section explicitly distinguishes those partition problems from extremal
questions about one large subset \(A\).
- A. Tonapi and D. Paquin,
arXiv:2603.22552 (2026), studies dynamic
coprime labelings of an externally given graph.
I found no primary source claiming the \(\ell\leq n/6\) conclusion, a
counterexample, or an improvement of the 1997 linear constant toward the
endpoint. This is an honest search result, not a claim that unindexed
literature cannot exist.
2. Exact finite reduction
Put
\[ f(n)=\left\lfloor\frac n2\right\rfloor+ \left\lfloor\frac n3\right\rfloor- \left\lfloor\frac n6\right\rfloor \]and
\[ L_n=\{k\geq3:k\text{ is odd and }k\leq n/3+1\}. \]For odd \(k\), let
\[ e_k(n)=\max\{|A|:A\subseteq[n]\text{ and }G(A)\text{ has no }C_k\}. \]Sharp lower bound
[a] Let
\[ B_n=\{m\leq n:2\mid m\text{ or }3\mid m\}. \]Inclusion–exclusion gives \(|B_n|=f(n)\). Partition \(B_n\) into the even
integers and the odd multiples of 3. No two vertices in the first class are
adjacent (they share 2), and no two in the second are adjacent (they share 3).
Thus \(G(B_n)\) is bipartite and contains no odd cycle of any length.
Consequently \(e_k(n)\geq f(n)\) for every odd \(k\).
Why checking one cardinality is sufficient
[a] It suffices to check every \(A\subseteq[n]\) of size exactly
\(f(n)+1\). Any larger \(A\) contains such an \(A'\), and every cycle in
\(G(A')\) is also a cycle in \(G(A)\).
Equivalently, if \(\mathcal C_{n,k}\) is the hypergraph whose edges are the
\(k\)-vertex sets supporting a \(C_k\) in the coprime graph on \([n]\), then
\[ e_k(n)=n-\tau(\mathcal C_{n,k}), \]where \(\tau\) is the transversal number. The conjectured finite assertion is
the sharp identity
\[ \tau(\mathcal C_{n,k})=n-f(n) \quad(k\in L_n). \]3. Exhaustive algorithm and correctness
The search implementation is
erdos883_fastcheck.cpp. It performs the following
steps for each \(n\):
1. Compute all coprime adjacencies using Euclid's algorithm.
2. Enumerate every complement \(D=[n]\setminus A\) with
\[ |D|=n-f(n)-1. \]
3. For every \(k\in L_n\), run an exhaustive simple-path DFS in \(G(A)\):
keep a bit mask of used vertices, extend only along coprime edges, and at
depth \(k\) require an edge back to the starting vertex.
4. Reject immediately if any pair \((A,k)\) lacks a cycle.
[a] The DFS is complete: any simple \(k\)-cycle has a least-numbered
vertex; traversing the cycle from that vertex in either direction is among the
DFS branches. The used mask enforces distinct vertices, and the closing-edge
test is exactly the last condition for a \(C_k\).
[a] The enumeration count is independently known:
\[ \#\{A:|A|=f(n)+1\}=\binom{n}{f(n)+1} =\binom{n}{n-f(n)-1}. \]Every observed count was checked against this exact integer.
No SAT/MILP result and no probabilistic sampling enters the claimed table.
4. Exact table
[d] + [a] The exhaustive upper bound and the bipartite lower construction
together prove, computationally, that
\[ \boxed{e_k(n)=f(n)\quad\text{for every }6\leq n\leq36 \text{ and every }k\in L_n.} \]For \(n\leq5\), \(L_n\) is empty, so the live-page assertion is vacuous.
| \(n\) | \(f(n)\) | boundary sets \(\binom n{f(n)+1}\) | every tested odd length |
|---:|---:|---:|:---|
| 6 | 4 | 6 | 3 |
| 7 | 4 | 21 | 3 |
| 8 | 5 | 28 | 3 |
| 9 | 6 | 36 | 3 |
| 10 | 7 | 45 | 3 |
| 11 | 7 | 165 | 3 |
| 12 | 8 | 220 | 3, 5 |
| 13 | 8 | 715 | 3, 5 |
| 14 | 9 | 1,001 | 3, 5 |
| 15 | 10 | 1,365 | 3, 5 |
| 16 | 11 | 1,820 | 3, 5 |
| 17 | 11 | 6,188 | 3, 5 |
| 18 | 12 | 8,568 | 3, 5, 7 |
| 19 | 12 | 27,132 | 3, 5, 7 |
| 20 | 13 | 38,760 | 3, 5, 7 |
| 21 | 14 | 54,264 | 3, 5, 7 |
| 22 | 15 | 74,613 | 3, 5, 7 |
| 23 | 15 | 245,157 | 3, 5, 7 |
| 24 | 16 | 346,104 | 3, 5, 7, 9 |
| 25 | 16 | 1,081,575 | 3, 5, 7, 9 |
| 26 | 17 | 1,562,275 | 3, 5, 7, 9 |
| 27 | 18 | 2,220,075 | 3, 5, 7, 9 |
| 28 | 19 | 3,108,105 | 3, 5, 7, 9 |
| 29 | 19 | 10,015,005 | 3, 5, 7, 9 |
| 30 | 20 | 14,307,150 | 3, 5, 7, 9, 11 |
| 31 | 20 | 44,352,165 | 3, 5, 7, 9, 11 |
| 32 | 21 | 64,512,240 | 3, 5, 7, 9, 11 |
| 33 | 22 | 92,561,040 | 3, 5, 7, 9, 11 |
| 34 | 23 | 131,128,140 | 3, 5, 7, 9, 11 |
| 35 | 23 | 417,225,900 | 3, 5, 7, 9, 11 |
| 36 | 24 | 600,805,296 | 3, 5, 7, 9, 11, 13 |
One run therefore examined exactly 1,383,685,174 boundary sets and made
7,499,965,908 set/length cycle-existence tests.
This includes the first nonvacuous cases for \(C_5,C_7,C_9,C_{11},C_{13}\),
at \(n=12,18,24,30,36\), respectively.
5. Independent re-verification
The required standalone checker is
erdos883_reverify.py. It contains a second
self-contained implementation and uses only the Python standard library plus
the system C++ compiler:
- it enumerates \(A\) directly by fixed-popcount masks rather than enumerating
complements;
- it uses Gosper's fixed-popcount successor rather than recursive combination
generation;
- its cycle DFS starts at every vertex and does not use the first program's
least-vertex canonicalization;
- Python separately recomputes \(f(n)\), every binomial count, the grand total,
and the bipartite lower witness.
Run:
python runs/erdos883_reverify.py --max-n 36
The independent run ended with:
n=36 f=24 subsets= 600805296 lengths=[3, 5, 7, 9, 11, 13] PASS
TOTAL subsets=1383685174 ALL_PASS
On one Intel Xeon Platinum 8259CL core:
- complement-enumerating search: 206.23 CPU-seconds, peak RSS 4,076 KiB;
- independent direct-\(A\) verifier: 178.50 CPU-seconds, peak RSS 82,924 KiB
(including Python and compilation).
Source hashes for the exact files used:
ddf452dfd8f95a73281500d0b4a6a7dd48f003828fb32f7131d5699a5a63a872 erdos883_fastcheck.cpp
d4269590176bf71f3a2af64e586c582eefacea7195d94fa303d2e353fb0d6e94 erdos883_reverify.py
6. What remains, and the exact obstruction to the 1997 machinery
Generic pancyclic graph theorems do not apply directly
[a] Qualifying graphs need not have useful minimum degree. For
\(A=B_n\cup\{1\}\) and \(n\geq30\), the vertex 30 has exactly one neighbor in
\(G(A)\), namely 1: it shares 2 with every even element of \(B_n\) and shares
3 with every odd element of \(B_n\). Thus Dirac/Bondy-type minimum-degree
pancyclicity cannot uniformly handle the problem.
A precise sufficient Hall lemma
The small-\(|A_{1\bmod6}|+|A_{5\bmod6}|\) construction in the 1997 paper can
be phrased as follows. Choose
\[ a\in A_{1\bmod6},\qquad b_1,\ldots,b_\ell\in A_{2\bmod6}, \qquad (a,b_1)=1, \]put \(b_{\ell+1}=a\), and define connector sets
\[ N_i=\{c\in A_{3\bmod6}:(c,b_i)=(c,b_{i+1})=1\} \quad(1\leq i\leq\ell). \][a] If
\[ \left|\bigcup_{i\in I}N_i\right|\geq |I| \quad\text{for every }I\subseteq[\ell], \tag{Hall} \]then Hall's theorem supplies distinct \(c_i\in N_i\), and
\[ a,b_1,c_1,b_2,c_2,\ldots,b_\ell,c_\ell,a \]is a \(C_{2\ell+1}\).
[b] Erdős–Sárközy obtain a fixed positive lower bound
\(|N_i|\geq\gamma n\) (after their totient/sieve selections) and then choose
the connectors greedily. This supports only \(\ell\leq\gamma n\), with
\(\gamma\) far from the endpoint \(1/6\). Their other density case uses three
pairwise-coprime residue classes modulo a primorial and encounters the same
fixed-density matching loss.
[c] Exact missing lemma (“endpoint connector expansion”). One needs either
to choose the \(b_i\)'s so that (Hall) holds all the way to
\(\ell\leq n/6\), even when \(|A_{3\bmod6}|\) is barely \(\ell\), and prove
the analogous primorial-class statement in the other density case; or replace
this alternating construction with a mechanism that gives an equally
near-spanning matching. Pointwise totient lower bounds do not give that
aggregate expansion. This is the precise place where the standard proof
stalls.
Sárközy's complete \(K(1,\ell,\ell)\) theorem supplies only
\(\ell\asymp\log n/\log\log\log n\), so it does not provide the required
linear-size matching.
Why extending the brute-force frontier is not a route to uniformity
[a] The boundary enumeration has
\(\binom{n}{n-f(n)-1}=\binom{n}{(1/3+o(1))n}\) cases, hence grows like
\(2^{H(1/3)n+o(n)}\), approximately \(1.89^n\) up to polynomial factors.
[d] At the measured \(n=36\) rate of about \(5.64\times10^6\) boundary
sets/second, optimistic single-core costs are:
- \(n=37\): 1,852,482,996 sets, about 0.091 core-hours;
- \(n=42\): 25,518,731,280 sets, about 1.26 core-hours;
- \(n=48\): 1,093,260,079,344 sets, about 53.8 core-hours.
These are optimistic because the required cycle length also grows. I did not
run those larger jobs. More finite cases would not supply the missing Hall
uniformity step.
7. Verified outcome
- [a] The threshold construction is actually free of every odd cycle, not
merely triangles.
- [d] + [a] The conjectured threshold is exactly sharp for every
nonvacuous \(n\leq36\) and every odd length demanded by the problem,
including \(C_{13}\).
- [c] No current primary source located in the literature audit resolves
the first question.
- No claim of a uniform proof or counterexample is made.
PARTIAL: 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-expansion lemma absent from the known sieve argument.