Erdős problem 535 — wave9p report
Date: 2026-07-28 UTC
Artifacts:
- Standalone verifier:
runs/erdos535_wave9p_reverify.py - This report:
runs/erdos535_wave9p.md
0. Mandatory page/status check
Live-origin warning
NOT LIVE-ORIGIN-VERIFIED BECAUSE THE SITE ITSELF WAS DOWN. I did use the required Bright Data browser route before doing any mathematics. Two independent Bright Data navigations to https://www.erdosproblems.com/535 (the second with a cache-busting query) both returned only:
Site down for planned maintenance... We'll be back soon!
The page title was Site down for planned maintenance. Thus the browser was available, but the authoritative origin content was not. I did not reconstruct the statement from the problem number or from memory.
The strongest accessible substitutes, all checked on 2026-07-28, were:
- The newest search-index copy of the problem/thread page,
crawled in June 2026 and identifying the page as last edited on 2026-04-29.
- The indexed LaTeX endpoint and
- The site's public database repository at current HEAD
2e7e7a630f9814f3df562bc1b207d9ad41451a55 (2026-07-28 07:39:21 UTC), whose entry 535 remains open. This is only corroboration because its status date is old.
- The indexed forum landing page, crawled about four weeks ago, which lists
thread 535's last activity as two months ago and does not include 535 in its “Solution Claims” list.
The accessible page copy says:
- status: OPEN, not resolvable by a finite computation;
- “Comment activity that has not yet been incorporated into the remarks”:
None / Partial Solution;
- “There are no solutions, partial or complete, claimed in the comments”;
Interested in collaborating: None;Currently working on this problem: None;- all other reaction/work/formalisation-work markers: None.
Consequently no stop condition was visible in the newest accessible page state. There remains a narrow, explicit caveat: an origin-only change after the last index crawl could not be excluded while planned maintenance was in progress.
Verbatim statement from the newest accessible page copy
Let \(r\geq 3\), and let \(f_r(N)\) denote the size of the largest subset of \(\{1,\ldots,N\}\) such that no subset of size \(r\) has the same pairwise greatest common divisor between all elements. Estimate \(f_r(N)\).
Listed results and comments
The current indexed remarks list:
- The page's source labels are
#535: [Er69][Er70][Er73]; the remarks also
cite the original [Er64] paper and Abbott–Hanson [AbHa70].
- Erdős [Er64]: \(f_r(N)\leq N^{3/4+o(1)}\).
- Abbott–Hanson [AbHa70]: \(f_r(N)\leq N^{1/2+o(1)}\).
- Erdős [Er64], in the page's current normalisation and for fixed \(r\):
\(f_r(N)>N^{c_r/\log\log N}\) for some \(c_r>0\).
- Erdős conjectured the matching-form upper bound
\(f_r(N)\leq N^{C_r/\log\log N}\).
- The recent sunflower bounds imply
\[ f_r(N)\leq \exp\!\left( O_r\!\left(\frac{\log N\log\log\log N}{\log\log N}\right) \right)=N^{o(1)}. \]
- A positive solution of the Erdős–Rado sunflower conjecture [problem 20]
would remove the \(\log\log\log N\) factor.
- See also problem 536.
The nine indexed comments, compressed without treating comments as proofs, are:
- Cong (2026-02-13) observed that an older auxiliary formulation with
\(\omega(n)=k\) is false: \(\{2,4,\ldots,2^m\}\) gives a \(k=1\) counterexample; squarefreeness was initially suggested as a repair.
- Cong (2026-04-16), after checking [Er73], corrected the intended stronger
auxiliary problem to \(\Omega(n)=k\), prime factors counted with multiplicity.
- Hrishi (2026-04-27), disclosing work with ChatGPT-5.5 Thinking, Sourish, and
Kireet, posted \[ f_r(N)\geq \exp\!\left((\log(r-1)+o(1))\frac{\log N}{\log\log N}\right) \] and the modern upper bound above. The post used prime-power divisibility layers \(S(n)=\{(p,j):1\leq j\leq v_p(n)\}\), a block lower construction, and a smooth/rough upper decomposition.
- Nat Sothanaphan reported that a standard check found no mathematical issue
but that ALWZ alone was not the exact theorem cited for the bound; Bell, Chueluecha, and Warnke, Theorem 1, supplies it.
- Hrishi posted a revision citing Bell–Chueluecha–Warnke and added the padding
argument from sets of size at most \(K\) to \(K\)-uniform sets.
- Terence Tao asked whether a positive solution of problem 20 removes the
final \(\log\log\log N\).
- Hrishi answered yes: with
\(K=\lfloor\log N/\log\log N\rfloor\), replacing \((C_r\log K)^K\) by \(c_r^K\) gives the conjectured exponential scale.
- Thomas Bloom noted that this implication was already in the remarks and in
[Er64].
- Thomas Bloom noted that the detailed calculation is useful but not new:
it is Erdős's sketched argument with today's sunflower estimate inserted.
No comment claimed a solution, and the site owner explicitly classified the commented asymptotic calculation as an already implicit partial result.
1. Primary-source/literature audit
I searched by exact title, formula, author, and problem wording. The following primary texts or publisher records were opened; the one unavailable full text is identified explicitly rather than silently inferred.
- [Erdős, *On a Problem in Elementary Number Theory and a Combinatorial
Problem*, Math. Comp. 18 (1964), 644–646](https://combinatorica.hu/~p_erdos/1964-10.pdf). The paper defines a threshold version (off by one from the site's maximum-avoiding-set normalisation), proves the \(3/4+\epsilon\) exponent, gives the block lower construction, and explains the conditional sunflower route.
- [Abbott and Gardner, An Extremal Problem in Number Theory, Canad. Math.
Bull. 10 (1967), 173–177](https://doi.org/10.4153/CMB-1967-015-8). This paper directly defines the maximum avoiding-set quantity and develops related lower bounds. The current page's string [AbHa67] has no resolved bibliography entry; the identifiable 1967 paper is Abbott–Gardner, not Abbott–Hanson. I therefore do not use [AbHa67] as an independently verified citation.
- [Abbott and Hanson, An Extremal Problem in Number Theory, Bull. London
Math. Soc. 2 (1970), 324–326](https://doi.org/10.1112/blms/2.3.324). DOI, authors, journal, year, and pages were verified. The full paper is paywalled, but its claimed \(1/2+\epsilon\) result was independently cross-checked in the next primary source.
- [Erdős, Some Extremal Problems in Combinatorial Number Theory, 1970,
pp. 123–133](https://combinatorica.hu/~p_erdos/1970-21.pdf), section 1. This is the page's [Er70]. It states the same maximum-avoiding-set problem, the lower exponential scale, the \(3/4+\epsilon\) upper bound, and the conjecture that the lower scale is correct.
- [Erdős, Problems and Results on Combinatorial Number Theory, 1973,
pp. 117–138](https://www.renyi.hu/~p_erdos/1973-21.pdf), section 4. Erdős explicitly records the Abbott–Hanson improvement to \(x^{1/2+\epsilon}\), restates the conjectural exponential scale, records Abbott's warning about the ordinary auxiliary formulation, and writes the strengthened multiplicity-counted formulation.
- [Alweiss–Lovett–Wu–Zhang, Improved bounds for the sunflower lemma,
arXiv:1908.08483](https://arxiv.org/abs/1908.08483), published in Annals of Mathematics 194 (2021), 795–815. The arXiv identifier exists and the paper proves a roughly \((\log k)^k\) sunflower bound.
Discrete Mathematics 344 (2021), 112367. Its Theorem 1 states \(\operatorname{Sun}(p,k)\leq(Cp\log k)^k\) for \(p,k\geq2\), exactly the clean bound needed in the indexed discussion.
was inspected only for statement consistency. Its research declarations contain sorry; they are formalised statements, not machine-checked proofs.
I found no primary source containing an exact small-\(N\) table for \(f_3(N)\). The page says only “OEIS: Possible”, with no assigned sequence. Exact-sequence and wording searches produced no match. This is an honest search miss, not a claim that the table below is historically new.
Claim labels for the known asymptotics
- (b) rigorous modulo named theorems/sources: all asymptotic bullets in
the page-results list above.
- (c) plausible/structural-unverified: historical novelty of the finite
table below. No novelty claim is made.
2. Exact finite reduction
For \(r=3\), define a 3-uniform hypergraph \(H_N\) on \([N]=\{1,\ldots,N\}\) by
Then \(f_3(N)=\alpha(H_N)\), the hypergraph independence number.
This equivalence is simply the definition, hence (a) elementary-rigorous. The checker separately verifies, for every \(a,b,c\leq100\), the known layer identity
and therefore also verifies that forbidden gcd triples are exactly 3-sunflowers in these layer sets. This identity is not needed for the search and acts as an arithmetic cross-check.
3. Exact result for \(1\leq N\leq100\)
The following is the exact table, compressed into maximal constant intervals. Every row includes a lower witness already contained in the first \(N\) of the interval.
| \(N\) | \(f_3(N)\) | explicit avoiding set at the left endpoint | |---:|---:|:---| | 1 | 1 | \(\{1\}\) | | 2–3 | 2 | \(\{1,2\}\) | | 4–7 | 3 | \(\{2,3,4\}\) | | 8 | 4 | \(\{1,4,6,8\}\) | | 9–15 | 5 | \(\{2,3,4,8,9\}\) | | 16–17 | 6 | \(\{3,4,8,9,14,16\}\) | | 18–26 | 7 | \(\{4,5,6,8,15,16,18\}\) | | 27–31 | 8 | \(\{6,9,10,12,20,24,25,27\}\) | | 32–44 | 9 | \(\{8,9,10,15,16,27,28,30,32\}\) | | 45–48 | 10 | \(\{8,12,14,15,16,32,35,36,42,45\}\) | | 49–53 | 11 | \(\{7,10,15,18,20,24,36,40,45,48,49\}\) | | 54–79 | 12 | \(\{7,12,15,18,20,24,40,45,48,49,50,54\}\) | | 80–95 | 13 | \(\{12,18,20,21,24,40,48,50,54,55,63,77,80\}\) | | 96–100 | 14 | \(\{10,12,13,15,18,20,24,40,48,54,75,80,91,96\}\) |
This table is (d) computational-only, with an elementary-rigorous certificate verifier. It does not make an asymptotic claim.
Why one lower and one upper certificate prove a whole row
Let a row be \([L,U]\) with displayed value \(k\).
- The listed \(k\)-set lies in \([L]\) and direct gcd enumeration finds no
forbidden triple, so \(f_3(N)\geq k\) for every \(N\geq L\).
- The complete search finds no independent \((k+1)\)-set in \([U]\), so
\(f_3(U)\leq k\).
- Monotonicity gives \(f_3(N)\leq f_3(U)\) for \(N\leq U\).
Thus \(f_3(N)=k\) throughout the row. Steps 1 and 3 are (a); the reported negative search outcome in step 2 is (d).
Completeness of the upper search
Fix a static order of the \(N\) vertices. A recursive state consists of an already chosen independent set \(S\), a bitset \(C\) of later candidates, and the number \(q\) still required. To choose \(v\in C\), the search removes every later \(w\) for which \(\{u,v,w\}\) is a forbidden triple for some \(u\in S\). It prunes only when \(|C|<q\).
For any independent target set \(T\), follow the elements of \(T\) in the fixed order. No element of \(T\) can be removed on that path: such a removal would exhibit a forbidden triple inside \(T\). The size prune also cannot fire on that path. Every target set has a unique increasing traversal. Hence returning UNSAT exhausts all target sets. This proof is (a) elementary-rigorous.
The degree-based vertex ordering affects runtime only, not the argument.
Reproduction output
Command:
python3 runs/erdos535_wave9p_reverify.py
Key deterministic lines from the observed output on this VM (the script also prints the expanded 100-term list represented by the plateau table):
range value target-at-end edges DFS-nodes result
1-1 1 2 0 1 UNSAT
2-3 2 3 1 3 UNSAT
4-7 3 4 20 19 UNSAT
8-8 4 5 27 19 UNSAT
9-15 5 6 187 153 UNSAT
16-17 6 7 297 194 UNSAT
18-26 7 8 1018 984 UNSAT
27-31 8 9 1802 1759 UNSAT
32-44 9 10 4998 14701 UNSAT
45-48 10 11 6410 18758 UNSAT
49-53 11 12 8867 22278 UNSAT
54-79 12 13 28959 558085 UNSAT
80-95 13 14 49615 1638802 UNSAT
96-100 14 15 56873 2277974 UNSAT
sha256(compact JSON table) = c8adee2f28fd55f68fee3d96609c80e3c2ea0012db7fe5759de3bde85d4e846a
total DFS nodes = 4533730
VERIFIED: exact f_3(N) for every 1 <= N <= 100
The run took about 5.7 seconds. During development, an independent OR-Tools CP-SAT model with one Boolean variable per integer and one \(x_a+x_b+x_c\leq2\) constraint per forbidden triple returned the same values. The delivered verifier does not depend on OR-Tools or on that cross-check.
The verifier additionally:
- recomputes every hyperedge directly with Euclid's gcd;
- directly checks every displayed witness;
- independently brute-forces the exact optimum, enumerating subsets in
decreasing cardinality, for every \(N\leq15\);
- checks all pair layer identities and all triple layer/gcd equivalences through
100;
- uses integer operations only.
4. Full verifier code
The complete executable core below is the code used by the adjacent standalone artifact; the .py adds documentation, type annotations, and a few redundant sanity assertions.
#!/usr/bin/env python3
from __future__ import annotations
import hashlib
import itertools
import json
import math
import time
PLATEAUS = [
(1, 1, 1, (1,)),
(2, 3, 2, (1, 2)),
(4, 7, 3, (2, 3, 4)),
(8, 8, 4, (1, 4, 6, 8)),
(9, 15, 5, (2, 3, 4, 8, 9)),
(16, 17, 6, (3, 4, 8, 9, 14, 16)),
(18, 26, 7, (4, 5, 6, 8, 15, 16, 18)),
(27, 31, 8, (6, 9, 10, 12, 20, 24, 25, 27)),
(32, 44, 9, (8, 9, 10, 15, 16, 27, 28, 30, 32)),
(45, 48, 10, (8, 12, 14, 15, 16, 32, 35, 36, 42, 45)),
(49, 53, 11, (7, 10, 15, 18, 20, 24, 36, 40, 45, 48, 49)),
(54, 79, 12, (7, 12, 15, 18, 20, 24, 40, 45, 48, 49, 50, 54)),
(80, 95, 13, (12, 18, 20, 21, 24, 40, 48, 50, 54, 55, 63, 77, 80)),
(96, 100, 14, (10, 12, 13, 15, 18, 20, 24, 40, 48, 54, 75, 80, 91, 96)),
]
def bad_triple(a: int, b: int, c: int) -> bool:
return math.gcd(a, b) == math.gcd(a, c) == math.gcd(b, c)
def is_independent(values: tuple[int, ...] | list[int]) -> bool:
return not any(bad_triple(*t) for t in itertools.combinations(values, 3))
def prime_power_layers(n: int) -> frozenset[tuple[int, int]]:
layers: set[tuple[int, int]] = set()
p, remaining = 2, n
while p * p <= remaining:
exponent = 0
while remaining % p == 0:
remaining //= p
exponent += 1
layers.add((p, exponent))
p += 1
if remaining > 1:
layers.add((remaining, 1))
return frozenset(layers)
def make_pair_masks(n: int) -> tuple[list[int], list[list[int]], int]:
triples: list[tuple[int, int, int]] = []
degrees = [0] * n
for a, b, c in itertools.combinations(range(n), 3):
if bad_triple(a + 1, b + 1, c + 1):
triples.append((a, b, c))
degrees[a] += 1
degrees[b] += 1
degrees[c] += 1
order = sorted(range(n), key=lambda v: (-degrees[v], v))
position = [0] * n
for i, vertex in enumerate(order):
position[vertex] = i
masks = [[0] * n for _ in range(n)]
for a, b, c in triples:
i, j, k = position[a], position[b], position[c]
masks[i][j] |= 1 << k
masks[j][i] |= 1 << k
masks[i][k] |= 1 << j
masks[k][i] |= 1 << j
masks[j][k] |= 1 << i
masks[k][j] |= 1 << i
return order, masks, len(triples)
def find_independent_set(n: int, target: int):
order, pair_masks, edge_count = make_pair_masks(n)
nodes = 0
def search(chosen: tuple[int, ...], candidates: int, needed: int):
nonlocal nodes
nodes += 1
if needed == 0:
return chosen
while candidates.bit_count() >= needed:
bit = candidates & -candidates
v = bit.bit_length() - 1
candidates ^= bit
next_candidates = candidates
for u in chosen:
next_candidates &= ~pair_masks[u][v]
answer = search(chosen + (v,), next_candidates, needed - 1)
if answer is not None:
return answer
return None
positions = search((), (1 << n) - 1, target)
if positions is None:
return None, nodes, edge_count
witness = tuple(sorted(order[i] + 1 for i in positions))
assert len(witness) == target and is_independent(witness)
return witness, nodes, edge_count
def brute_force_value(n: int) -> int:
for size in range(n, -1, -1):
for subset in itertools.combinations(range(1, n + 1), size):
if is_independent(subset):
return size
raise AssertionError
def verify_layer_encoding(limit: int = 100) -> None:
layers = [frozenset()] + [prime_power_layers(n) for n in range(1, limit + 1)]
for a in range(1, limit + 1):
for b in range(1, limit + 1):
assert layers[a] & layers[b] == layers[math.gcd(a, b)]
for a, b, c in itertools.combinations(range(1, limit + 1), 3):
same = (
layers[a] & layers[b]
== layers[a] & layers[c]
== layers[b] & layers[c]
)
assert bad_triple(a, b, c) == same
def main() -> None:
start = time.perf_counter()
expanded: list[int] = []
next_n = 1
for first, last, value, witness in PLATEAUS:
assert first == next_n
assert len(witness) == len(set(witness)) == value
assert 1 <= min(witness) and max(witness) <= first
assert is_independent(witness)
expanded.extend([value] * (last - first + 1))
next_n = last + 1
assert next_n == 101
assert [brute_force_value(n) for n in range(1, 16)] == expanded[:15]
verify_layer_encoding(100)
print("range value target-at-end edges DFS-nodes result")
total_nodes = 0
for first, last, value, _ in PLATEAUS:
found, nodes, edges = find_independent_set(last, value + 1)
assert found is None
total_nodes += nodes
print(
f"{first:>2}-{last:<3} {value:>2} {value + 1:>2} "
f"{edges:>6} {nodes:>9} UNSAT"
)
payload = json.dumps(expanded, separators=(",", ":")).encode()
print(f"f3(1..100) = {expanded}")
print(f"sha256(compact JSON table) = {hashlib.sha256(payload).hexdigest()}")
print(f"total DFS nodes = {total_nodes}")
print(f"elapsed seconds = {time.perf_counter() - start:.3f}")
print("VERIFIED: exact f_3(N) for every 1 <= N <= 100")
if __name__ == "__main__":
main()
5. What remains, and the exact wall
The exact table is finite progress only. It does not approach the quantifier “for all sufficiently large \(N\)” and cannot close an asymptotic problem.
The present named-theorem wall is precise. The Bell–Chueluecha–Warnke bound
contributes \(K\log\log K\) in the logarithm. With \(K\asymp\log N/\log\log N\), this is exactly the unwanted \(\log\log\log N\) factor. Closing the conjectured scale by this route needs either
the open Erdős–Rado sunflower conjecture, or an arithmetic-specific substitute that bounds every relevant rough fiber by \(C_r^K\) while retaining the \(\exp(O(\log N/\log\log N))\) smooth-part count. This diagnosis is (b) for the implication and (c) only as a statement that no presently known substitute was found.
The finite checker itself materialises \(O(N^3)\) triples and has an exponential DFS worst case. The certified \(N\leq100\) run costs under \(0.002\) core-hours here. No credible extrapolation to a substantially larger cutoff follows from one small benchmark, so I do not quote a fabricated core-hour estimate. More finite computation is also incapable of supplying the missing uniformity step.
PARTIAL: (d) A standard-library exhaustive certificate gives the exact table \(f_3(N)\) for every \(1\leq N\leq100\); the asymptotic problem remains open, with the precise missing uniform step an exponential sunflower bound or an arithmetic substitute.