{"items":[{"id":2,"title":"Covering-system min-modulus record (>42)","prize":"$1000","statement":"Erdős's \"favourite problem\": can the smallest modulus of a covering system (distinct moduli covering all integers) be arbitrarily large? DISPROVED (Hough 2015: ≤10^16; BBMST 2022: ≤616000). Remaining finite sub-problem: the lower-bound record — a covering system whose smallest modulus exceeds the current best of 42.","finite_object":"A covering system (finite set of congruences a_i mod m_i) with distinct moduli all ≥ 43 that covers every integer. \"Finite\" only nominally: Nielsen's min-40 witness already has >10^50 congruences; a min-43+ witness is comparably or vastly more astronomical.","current_record":"Smallest modulus = 42, Tyler Owens, MSc thesis, BYU, 2014 (improving Pace Nielsen's 40, 2009; Krukenberg/Choi/Gibson chain before that). Upper bound side: Hough 2015 (≤10^16), Balister–Bollobás–Morris–Sahasrabudhe–Tiba 2022 (≤616000), Cummings–Filaseta–Trifonov (≤118 for squarefree moduli).","beatable":"WALL","beatable_reason":"The witness is not an explicitly-enumerable finite list: Nielsen's min-modulus-40 system already exceeds 10^50 congruences, defined recursively (Filaseta-school hierarchy: admit multiples of prime p only after exhausting moduli with all prime factors <p). A min-43 witness would be super-astronomically larger. It cannot be represented in a SAT/ILP/MIS instance at all — the variable/clause count exceeds atoms in the universe — so exhaustion/local-search/annealing are categorically inapplicable. The record (18→…→40→42 over 50 years) was set by bespoke number-theoretic recursion, precisely the method we have no edge in, and each +1 increment explodes the LCM and congruence count super-exponentially. Even the verifier is not our poly-time enumerate-residues checker. This is the R(5,5)-witness situation: computational-looking, actually a wall.","fit_score":2,"impact_score":4,"impact_reason":"Famous ($1000, Erdős's self-described favourite problem) but the headline is already resolved (DISPROVED), so a lower-bound record bump from 42→43 is a niche footnote, not a prize claim and not field-reshaping. Real-world relevance ~nil (pure number theory). Significance concentrated in the (now-closed) asymptotic question, not the record we could nominally target.","verifier":"Checking a covering system covers Z = verifying it covers all residues mod L (L = lcm of moduli). But L is a product of primes far beyond enumeration (astronomically large), so verification is NOT clean poly-time residue-enumeration — it requires a structured CRT/inclusion-exclusion/recursion argument. Cost: intractable to enumerate; only structured symbolic verification works, and only because the object is recursively defined.","attack":"No viable finite-search attack. A generic SAT/ILP \"select congruences to cover residues mod L\" formulation is dead on arrival because L and the required number of congruences are astronomical (>10^50 for the WEAKER 40 record), exceeding any solver's representable instance size by dozens of orders of magnitude. A structured recursive construction (extending Nielsen/Owens) is a pure number-theory research program, not a verifier-first CPU-farm search — no amount of ~100-core compute or DRAT certification bears on it. Rough compute to beat 42: not a compute question; it is an open construction-theory problem.","our_edge":"none beyond generic compute — and generic compute is inapplicable here since the object cannot be represented for search.","verdict":"PARTIAL — headline conjecture is asymptotic and already DISPROVED (not finite-computable), but a genuine finite sub-problem exists (push the min-modulus lower-bound record above 42). That sub-problem is a hard WALL for our verifier-first search farm: the witness has >10^50 recursively-defined congruences and is not representable in any SAT/ILP/MIS/exhaustion instance, the verifier is not clean poly-time residue enumeration, and the record was set by bespoke number-theoretic recursion we hold no edge in. Do not attack.","lane":"wall","board_class":"NONE","board_class_reason":"witness not representable: a min-modulus-40+ covering system already has > 10^50 recursively-defined congruences; no flat poly-time check","wall_reason":"witness not representable: a min-modulus-40+ covering system already has > 10^50 recursively-defined congruences; no flat poly-time check","erdos_url":"https://www.erdosproblems.com/2","links":{"oeis":[],"arxiv":[]}},{"id":27,"title":"ε-almost covering systems with moduli in [N, CN]","prize":"$100","statement":"Is there a constant C>1 such that for every ε>0 and N≥1 there is an ε-almost covering system (congruences a_i mod n_i, distinct moduli, density of uncovered integers ≤ ε) with all moduli in [N, CN]? Headline answer: NO.","finite_object":"A covering system (or ε-almost covering system) of Z with distinct moduli, congruences a_i mod n_i, with all moduli ≥ N; the \"record\" instance is the largest achievable minimum modulus.","current_record":"Headline #27: DISPROVED (Filaseta, Ford, Konyagin, Pomerance, Yu, 2007). Related finite frontier — largest known minimum modulus of a distinct covering system = 42 (D. Owens, 2014 BYU MS thesis, structured construction), improving Nielsen's 40 (2009); Krukenberg/Gibson before. Upper bound on any covering's min modulus: ≤ 616000 (Balister, Bollobás, Morris, Sahasrabudhe, Tiba, 2022, \"distortion method\"), improving Hough's 10^16 (2015). The 42→616000 gap is closed by neither construction nor search today.","beatable":"WALL","beatable_reason":"The headline (a uniform constant C for all ε,N) is DISPROVED by Filaseta–Ford–Konyagin–Pomerance–Yu (2007) via an asymptotic density theorem — pure analysis, no finite witness, nothing for a farm to push. The only genuinely finite sub-problem in-class is the covering-system minimum-modulus construction record, and that is itself a wall for our specific machinery: (a) the record was set by structured algebraic (prime-power tower / Krukenberg–Gibson distributed-covering) constructions plus human insight, not flat combinatorial search; (b) the witness is not a tractable object — a covering system with minimum modulus 42 already has well over 10^50 distinct moduli and an LCM period that is astronomically large, so there is NO flat poly-time \"enumerate a period and check every residue is hit\" verifier (verification is done by recursive distributed-covering structure, not enumeration); (c) you cannot even encode the search as a SAT/ILP instance — that would need >10^50 variables. This is the R(5,5)-upper-bound situation, not the R(5,5)-witness situation: the frontier is bounded by a theorem (min modulus ≤ 616000, BBMST 2022) but the practical construction ceiling is a combinatorial-explosion wall, not a compute wall we can climb.","fit_score":2,"impact_score":3,"impact_reason":"$100 prize is already claimed (disproved 2007). Field significance of the residual finite frontier (min-modulus record 42) is a niche number-theory curiosity; nudging it to 43 would be a cute non-prize milestone with little downstream or real-world relevance, and the deep questions (true threshold in [42, 616000]) are theorem-shaped, not witness-shaped.","verifier":"Checking that a proposed system covers Z (or leaves density ≤ ε). But the natural extremal object has >10^50 moduli and an astronomically large LCM period, so there is no flat enumerable poly-time checker over a period; verification requires the recursive distributed-covering structure of the construction itself. This absence of a clean small-object exact verifier is the disqualifier for our verifier-first farm.","attack":"No viable attack for our tools. A flat SAT/ILP/MIS encoding is impossible (witness has >10^50 moduli). Structured local-search over Krukenberg–Gibson building blocks to nudge the min-modulus record 42→43 is conceivable but is exactly the algebraic-construction game where humans have been stuck since 2014, not a CPU-farm-shaped problem, and success is not certifiable by a cheap exact verifier. A tractable but non-record-bearing exercise would be: exhaustively compute, for tiny N and modest C, the minimal C(N) admitting an ε-almost cover with moduli in [N,CN] (ILP over LCM(N..CN) for small N where the period is enumerable) — genuine PARTIAL-exploratory work, but no established record to beat and no prize.","our_edge":"None beyond generic compute. This class rewards algebraic/analytic construction (distortion method, prime-power towers), which is orthogonal to our verifier-first witness-search precedents (kissing, R(5,5), LP/SDP bounds). We have no exact small-object verifier here, which is the one asset our farm is built around.","verdict":"WALL / NONE for our machinery. The $100 headline is an already-disproved asymptotic theorem (no finite witness). The one in-class finite frontier — the covering-system minimum-modulus construction record (42, Owens 2014) — fails our fit test on every axis: no tractable exact verifier (witness >10^50 moduli, LCM period astronomically large), no SAT/ILP-encodable search space, and a record set by structured algebraic construction rather than flat search. Analogous to the R(5,5) UPPER bound (NONE), not the R(5,5) witness (STRONG). Recommend PASS. The only honest computational contribution available (small-N exact ε-almost-cover thresholds) is exploratory, record-free, and low-value.","lane":"wall","board_class":"NONE","board_class_reason":"headline DISPROVED (Filaseta-Ford-Konyagin-Pomerance-Yu 2007); extremal witnesses not finitely representable","wall_reason":"headline DISPROVED (Filaseta-Ford-Konyagin-Pomerance-Yu 2007); extremal witnesses not finitely representable","erdos_url":"https://www.erdosproblems.com/27","links":{"oeis":[],"arxiv":[]}},{"id":43,"title":"Disjoint-difference Sidon set pairs","prize":"$100 (already effectively claimed via disproof)","statement":"For Sidon sets A,B ⊆ {1,...,N} with (A-A)∩(B-B)={0}: (Q1) is C(|A|,2)+C(|B|,2) ≤ C(f(N),2)+O(1), where f(N) is the max Sidon set size? (Q2) if |A|=|B|, can this be improved to ≤ (1-c+o(1))C(f(N),2)?","finite_object":"Pairs of Sidon sets in {1,...,N} with disjoint nonzero difference sets; the finite quantity is max of C(|A|,2)+C(|B|,2) at fixed small N.","current_record":"Problem DISPROVED. Q1: negative, follows from the resolution of Erdős #42. Q2: negative, Barreto construction gives |A|=|B| Sidon pairs with disjoint difference sets and C(|A|,2)+C(|B|,2) ≥ (1-o(1))C(f(N),2); Tao supplied the matching upper bound (no -c). Both parts settled ~2022-2025; $100 effectively claimed. No small-N record table for disjoint pairs exists.","beatable":"WALL","beatable_reason":"Headline is asymptotic AND already fully resolved: Q1 disproved via the problem-#42 construction (|A|=f(N), |B|→∞); Tao proved the clean upper bound; Barreto disproved Q2 (pairs reaching (1-o(1))C(f(N),2) for infinitely many N). No conjecture stands for a witness to refute. The only in-class finite object — small-N record disjoint Sidon pairs — has no established record ladder to beat, and the adjacent single-Sidon-set tables (A003022 Golomb rulers) are already at the exhaustive-search feasibility wall with records held by the same SAT/exhaustion tools we would use. No concrete number for compute to push.","fit_score":3,"impact_score":2,"impact_reason":"Problem is DISPROVED and the $100 effectively claimed; both questions answered by Tao and Barreto. No prize to win, no open conjecture, purely settled additive-combinatorics result. Sidon sets are a respectable area but this specific problem contributes nothing further.","verifier":"Poly-time exact: verify each set is Sidon (all C(n,2) pairwise differences distinct, O(n^2)); verify (A-A)∩(B-B)={0} by hashing difference multisets and intersecting, O(n^2). Cheap. But no target record to certify against.","attack":"N/A — no movable frontier. In principle one could ILP/SAT-search max C(|A|,2)+C(|B|,2) over disjoint Sidon pairs for small N (~minutes/core up to N~few hundred), but there is no published record to beat and the asymptotic question is closed, so any witness is a non-contribution.","our_edge":"none beyond generic compute; clean verifier is the only structural fit, but it points at no beatable target","verdict":"PARTIAL by taxonomy (a genuine in-class finite sub-problem — small-N record disjoint Sidon pairs — exists and has a clean poly-time verifier), but the frontier is a WALL: the headline is asymptotic and already fully resolved (Q1 via #42, Q2 via Barreto + Tao upper bound), there is no established record number to push, and the adjacent single-Sidon tables are already at the exhaustion wall held by our own tools. Skip.","lane":"wall","board_class":"NONE","board_class_reason":"problem DISPROVED (both questions resolved negatively); no movable number","wall_reason":"problem DISPROVED (both questions resolved negatively); no movable number","erdos_url":"https://www.erdosproblems.com/43","links":{"oeis":[],"arxiv":[]}},{"id":52,"title":"Erdős–Szemerédi sum-product","prize":"$250","statement":"For a finite set of integers A, is max(|A+A|,|AA|) ≫_ε |A|^{2-ε} for every ε>0? (The sum-product conjecture.)","finite_object":"A finite set A ⊂ ℤ_{>0} of size n minimizing the sum-product functional — either R(A)=|A+A ∪ AA| (OEIS A263996) or max(|A+A|,|AA|). The verifiable witness is the explicit n-element set.","current_record":"TWO distinct frontiers. (1) ASYMPTOTIC (the actual $250 problem): max(|A+A|,|AA|) ≫ |A|^{1270/951 − o(1)}, 1270/951 ≈ 1.3354, Bloom [Bl25] — a theorem, NOT a finite computation. (2) FINITE small-case table: OEIS A263996 = smallest |A+A ∪ AA| over n positive integers; b-file gives every term to n≈205 (a(7)=26 via {1,2,3,4,6,8,12}, etc.). Best-known constructions for n up to 1000 were produced by Al Zimmermann's Programming Contest \"Sums and Products\" (Nov 2015–Feb 2016, 1,639 entries), a distributed heuristic-optimization competition. No finite-side movement found 2023–2026.","beatable":"WALL","beatable_reason":"The headline is explicitly asymptotic and self-declares \"cannot be resolved with a finite computation\" — no witness touches the $250 exponent (a single better construction cannot change an ε-exponent claim; that needs an infinite family + proof). The genuine finite sub-problem (extend/beat A263996) is real but sits on a wall: the mid-range records were set by exactly the tools we'd bring — simulated annealing / local search on a large distributed compute pool across 1,639 contest entries specifically tuned for \"sophisticated heuristics.\" That is the R(5,5)-witness situation inverted: the record-holder already ran our attack, harder and longer, and the optimal sets are highly structured smooth-number sets ({2^a·3^b·5^c…}) where the search is well-understood and saturated. Worse for a certified-optimality angle: the domain is unbounded integers, so proving a(n) exactly (the DRAT-nonexistence analog) requires first bounding the largest element of an optimal set — a mini-theorem, not clean finite exhaustion/SAT/MIS. Residual movability only on soft, non-contest intermediate terms, at negligible payoff.","fit_score":4,"impact_score":3,"impact_reason":"Sum-product is a marquee problem (huge field significance, $250 prize), but the ONLY finite-computable output — nudging one OEIS A263996 term — is a b-file edit that does not move the asymptotic exponent, is not prize-eligible, and carries little citable weight. High topic fame, near-zero achievable-contribution significance.","verifier":"Trivial exact checker: given A, compute the multiset of pairwise sums and products, dedupe, take union cardinality. O(n^2) integer arithmetic (bignum since products blow up), microseconds even for n in the thousands. Perfect poly-time exact verifier — the strongest part of the fit.","attack":"If attempted (not recommended): seed from published contest optima, run SA / large-neighborhood local search over sets of smooth numbers {2^a 3^b 5^c 7^d}, perturbing by element swap/rescale with the exact O(n^2) objective; and an ILP over a fixed smooth-number support (binary select n of them, minimize |sum-set ∪ product-set| via indicator constraints) for exact small-n confirmation. ~100-core farm, days per n-band. Realistic outcome: reproduce, not beat, the 2016 contest values.","our_edge":"None beyond generic compute. The verifier is trivially cheap (our usual moat), but the record was set by our exact search paradigm at larger scale by a motivated field, and there is no exact-certification hook (unbounded integer domain) the way there was for R(5,5)/kissing on a fixed lattice.","verdict":"PARTIAL — confirms triage. Headline conjecture is asymptotic/analytic = NONE for finite computation (self-declared unresolvable by finite means; current exponent 1.335 vs target 2). A genuine in-class finite sub-problem exists (minimize |A+A ∪ AA| / max(|A+A|,|AA|), extend OEIS A263996) with an ideal cheap exact verifier, but the frontier is a WALL: the record is held by the same SA/local-search tools we'd deploy, run at contest scale (Al Zimmermann 2016), over an unbounded domain with no exact-nonexistence certificate hook. Not worth a farm; any win is a low-impact OEIS nudge, not the $250 result. Do not pursue.","lane":"exact-backtracking","board_class":"NONE","board_class_reason":"no concrete n, authoritative seed witness, or tracked per-n record is identified; the asymptotic headline is not advanced by an unscoped finite score (R2 fails)","wall_reason":null,"erdos_url":"https://www.erdosproblems.com/52","links":{"oeis":["A263996"],"arxiv":[]},"frontier":{"summary":"A263996 small-case table (smallest |A+A u AA| over n-sets); contest-set records"}},{"id":77,"title":"lim R(k)^{1/k} (diagonal Ramsey growth constant)","prize":"$250","statement":"Determine lim_{k→∞} R(k)^{1/k}, where R(k)=R(k,k) is the diagonal Ramsey number. Currently only known to lie in [√2, <3.8-base]; the limit is not even proven to exist.","finite_object":"A 2-coloring of K_n with no monochromatic K_k (Ramsey graph) certifying a lower bound at a specific order — the finite witness object. But no such object at any single order n moves the asymptotic base, which is the prize.","current_record":"liminf R(k)^{1/k} ≥ √2 ≈ 1.4142 (Erdős 1947 probabilistic lower bound, still the diagonal base); limsup ≤ 3.8^{1+o(1)} base (Gupta-Ndiaye-Norin-Wei, refining Campos-Griffiths-Morris-Sahasrabudhe 2023 \"book algorithm\" — first exponential improvement over Erdős-Szekeres 4^k since 1935). Existence of the limit is OPEN. Feeding small case: R(5,5) ∈ [43 (Exoo 1989), 46 (Angeltveit-McKay 2024)].","beatable":"WALL","beatable_reason":"Headline is a pure asymptotic constant — no finite object determines it; even proving the limit exists needs a new theorem. The only in-class finite sub-problem (exact small R(k,k) / Ramsey-graph constructions) is (a) analytically disconnected from the asymptotic base — pinning R(5,5) or R(6,6) contributes zero digits to the limit, as Erdős himself noted — and (b) itself at the wall: R(5,5) lower bound 43 (Exoo 1989) has stood 37 years, our own R(5,5) witness campaign closed with no witness (42 DRAT-certified asymmetry certs), and the recent upper-bound motion came from LP+casework in the same McKay nauty/SAT ecosystem we'd use. Record set by our own class of tools = classic feasibility-limit signature.","fit_score":3,"impact_score":3,"impact_reason":"The headline is one of the most famous constants in combinatorics (huge field significance), but the prize is only $250 AND is unclaimable by finite computation; the finite contribution we could actually make (an incremental small-Ramsey bound) is low-value and, in the R(5,5) case, already exhausted by us. Real-world relevance nil.","verifier":"O(n^k) / clique-check on a fixed graph: verifying a candidate Ramsey graph of order n has no monochromatic K_k is polynomial in n for fixed k (enumerate k-subsets). Exact and cheap per-order; this is exactly our R(5,5) verifier. But it certifies one small value, not the limit.","attack":"If one wanted the finite slice: SAT/CDCL search for a Ramsey graph beating the current R(k,k) lower bound (e.g. order-43 K5-free symmetric coloring), with DRAT nonexistence certs for the negative direction — precisely our R(5,5) pipeline on a ~100-core farm. But we already ran this: no witness at 43, wall confirmed. Higher k is exponentially further out. Nothing here claims the $250 prize regardless of compute.","our_edge":"Perfect mechanism match to our R(5,5) SAT+DRAT/MIS farm — but no advantage that matters, because the movable-frontier-that-would-count does not exist and the finite sub-frontier is one we already found closed. None beyond generic compute for the prize.","verdict":"PARTIAL-but-WALL. Headline lim R(k)^{1/k} is NONE — a pure asymptotic constant not known to exist, needing a new theorem (√2 ≤ L ≤ 3.8-base). The genuine in-class finite sub-problem (exact small Ramsey numbers / clique-free graph witnesses) maps perfectly to our SAT+DRAT farm but is (1) analytically disconnected from the $250 prize and (2) already at the feasibility wall — our own R(5,5) campaign closed with no witness (42 DRAT asymmetry certs), Exoo's 43 lower bound is 37 years old, and recent motion came from the same McKay tooling we'd use. Do not attack for the prize; the finite slice is a solved/closed wall for us. Skip.","lane":"wall","board_class":"NONE","board_class_reason":"asymptotic limit only; the finite R(5,5) frontier object is carried by #1029 (R4 dedupe)","wall_reason":"asymptotic limit only; the finite R(5,5) frontier object is carried by #1029 (R4 dedupe)","erdos_url":"https://www.erdosproblems.com/77","links":{"oeis":[],"arxiv":[]}},{"id":83,"title":"EKR t=2 intersecting family bound on [4n]","prize":"$500 (already awarded/solved)","statement":"For a family F of 2n-subsets of [4n] with pairwise intersection ≥ 2, |F| ≤ (1/2)(C(4n,2n) − C(2n,n)²). Conjectured by Erdős–Ko–Rado (1961); the t=2 case of the complete intersection theorem.","finite_object":"Per fixed n, the extremal family: all 2n-subsets of [4n] containing ≥ n+1 of the first 2n elements. It is an explicit named construction, NOT the output of any search.","current_record":"PROVED — Ahlswede & Khachatrian, Eur. J. Combin. 18 (1997), resolving Frankl's conjecture; #83 is the t=2/k=2n/m=4n case, RHS = OEIS A071799 (closed form).","beatable":"WALL","beatable_reason":"The headline is a proved theorem with an EXPLICIT extremal construction and a CLOSED-FORM value (A071799). There is no open number to push, no record to beat, and no nonexistence to certify — the maximum and its maximizers are known for all n simultaneously. The imagined \"finite sub-problem\" (small-case exact values / extremal family per n) is already fully determined analytically; a max-independent-set or exhaustion run would only re-derive a theorem for a handful of tiny n before hitting the combinatorial wall, contributing nothing publishable. This is the opposite of the R(5,5) lower-bound witness case: there the extremal object was unknown and searchable; here it is a named formula.","fit_score":2,"impact_score":2,"impact_reason":"Central, celebrated result in extremal set theory (complete intersection theorem), but it is fully solved — no prize is claimable and no frontier remains. A closed sub-problem offers zero marginal contribution.","verifier":"Poly-time count-and-check of a candidate family (verify sizes, pairwise intersections ≥ 2, count). Exact maximality would need max-independent-set on the conflict graph (vertices = 2n-subsets, edges = intersection ≤ 1). Cost blows up: n=3 → 924 vertices, n=4 → 12870 vertices; and the answer is already a proved theorem, so the MIS solve certifies nothing new.","attack":"None worthwhile. The only computational task — MIS/exhaustion on the intersection-conflict graph to reconfirm |F_max| for n=1,2,3 — is a redundant sanity check of a solved theorem, feasible only up to ~n=3–4 and yielding no new value. No SAT/ILP/DRAT deliverable exists because there is no contested boundary.","our_edge":"none beyond generic compute","verdict":"NONE — PROVED theorem (Ahlswede–Khachatrian 1997) with explicit extremal family and closed-form value (A071799). No record to beat, no nonexistence to certify, no movable number. The finite object per n is a named construction, not a search target. Not attackable by our verifier-first farm.","lane":"wall","board_class":"NONE","board_class_reason":"proved theorem (Ahlswede-Khachatrian 1997); a MIS solve certifies nothing new","wall_reason":"proved theorem (Ahlswede-Khachatrian 1997); a MIS solve certifies nothing new","erdos_url":"https://www.erdosproblems.com/83","links":{"oeis":["A071799"],"arxiv":[]}},{"id":90,"title":"Unit distance problem — max unit pairs (A186705)","prize":"$500 (headline) — already effectively resolved: DISPROVED in the negative, Lean-verified, by an OpenAI internal model. Earlier $300/$250 sub-offers were for the asymptotic n^{1+o(1)} bound, now settled. No prize attaches to the finite OEIS-extension sub-problem.","statement":"Erdős #90: does every set of n distinct points in R^2 have at most n^{1+O(1/loglog n)} pairs at distance exactly 1? Headline asymptotic conjecture (best classical upper bound O(n^{4/3}), Spencer–Szemerédi–Trotter 1984). Finite sub-problem: OEIS A186705, u(n) = max number of unit-distance pairs among n points.","finite_object":"A 22-point configuration in R^2 maximizing the number of unit-distance pairs (equivalently, the abstract maximally-dense unit-distance graph on 22 vertices), which would establish u(22) and extend the OEIS A186705 exact table by one term.","current_record":"Exact values u(n) proven for n ≤ 21 (u(21)=57); Alexeev, Mixon, Parshall, arXiv:2412.11914 (2024/2025), via forbidden-subgraph filtering + totally-unfaithful-graph elimination + custom embeddability solver, ~6,100 CPU-hours. Prior: n≤14 (Schade 1993), n=15 (Ágoston–Pálvölgyi), n=16–17 extended. Next open value: u(22). Densest-known lower bounds up to n=100 via diverse beam search, arXiv:2406.15317 (2024), 60M-UDG database. Headline asymptotic conjecture DISPROVED (negative, Lean-verified) by an OpenAI internal model.","beatable":"WALL","beatable_reason":"Two decisive blocks against our verifier-first farm. (1) The exact-value verifier is not poly-time: deciding graph→unit-distance-realizability in R^2 is ∃R-hard, violating our core precondition; the specialists' own solver is incomplete (aborts on girth-≥5 non-UDGs, which dominate at n≥22). (2) Already at feasibility limit set by the same class of tools: n=22 needs ~15,000 CPU-hours (compute within reach) but the binding constraint is the realizability oracle, not cycles — our generic SAT/ILP/MIS/SA toolbox supplies no such certificate, and we'd have to out-engineer the specialists' incomplete geometric solver. The one movable sub-lane (beat a densest-known lower bound for some 30<n≤100 via SA/local-search + exact counting) is a saturated beam-search arms race with no proven-optimality prize.","fit_score":3,"impact_score":4,"impact_reason":"Celebrated Erdős problem, but the only remaining finite contribution is extending the A186705 exact table by one term (u(22)); the prize is gone (disproved), real-world relevance is nil, and field significance is modest/incremental — a cited-but-minor OEIS extension, not a frontier result.","verifier":"Two directions, asymmetric cost. LOWER bound: given explicit (rational/algebraic) coordinates, count pairs at distance exactly 1 — poly-time O(n^2), clean fit. EXACTNESS/upper: decide whether an abstract candidate graph is realizable as a unit-distance graph in R^2 — this is ∃R-hard (existential theory of the reals), NOT poly-time. The specialists use a custom, incomplete embeddability solver that returns 'I don't know' for girth-≥5 non-UDGs. This realizability oracle is the true cost and the wall.","attack":"For u(22): compute-only estimate ~15,000 CPU-hours for complete enumeration (~6 days on 100 cores) — but infeasible for us because the pipeline requires certifying non-realizability of girth-≥5 candidate graphs, an ∃R-hard step where the field's best custom solver returns 'I don't know'. No SAT/ILP/MIS reduction supplies this. Only genuinely-fit lane: local-search/simulated-annealing over coordinate configs with exact O(n^2) unit-pair counting to beat densest-known lower bounds for some 30<n≤100 — cheap (hours on a few cores) but competes against an already-tuned diverse-beam-search pipeline and yields non-prize, low-impact incremental records.","our_edge":"None beyond generic compute. The hard part (deciding unit-distance realizability of a graph in R^2, ∃R-hard) is specialized computational geometry where we have no tooling advantage; the config-search lower-bound lane is already saturated by a dedicated ML beam-search effort with a 60M-graph database.","verdict":"PARTIAL — headline conjecture is asymptotic and already DISPROVED, so no prize path. A genuine finite sub-problem exists in-class (extend OEIS A186705 exact table, u(22)), but it maps poorly to our machinery: the exact-value verifier is ∃R-hard (not poly-time), and the specialists just set n≤21 with a custom solver that hits a fundamental incompleteness wall at n=22. Beatability WALL; the only movable lane (densest-known lower bounds) is a saturated, non-prize ML-search arms race. Recommend NO attack.","lane":"wall","board_class":"NONE","board_class_reason":"exact-value verifier is ExistsR-hard (unit-distance realizability); witness side requires algebraic coordinates - equality constraint makes the rational restriction lossy (R3 fails)","wall_reason":"exact-value verifier is ExistsR-hard (unit-distance realizability); witness side requires algebraic coordinates - equality constraint makes the rational restriction lossy (R3 fails)","erdos_url":"https://www.erdosproblems.com/90","links":{"oeis":["A186705"],"arxiv":["2406.15317","2412.11914"]}},{"id":92,"title":"Max-equidistance-count planar point sets (Erdős–Fishburn table)","prize":"$500 (disproved upper bound) / $50 (counterexample, per ErFi97) — both effectively resolved/dead","statement":"f(n) = max over n-point sets A in R^2 of min_{x in A}(number of points of A equidistant from x). Conjecture: f(n) <= n^{o(1)} (even n^{O(1/loglog n)}). Finite sub-problem: g(k) = smallest n with f(n)=k.","finite_object":"A planar point set of n points in which every point has >= k of the others equidistant from it (i.e. lying on a common circle centered at that point). Minimal such n is g(k); the extremal table {g(3)=6, g(4)=8, g(5)=?} is the finite record.","current_record":"Headline f(n)<=n^{o(1)}: DISPROVED (negative) — it strengthens the unit-distance conjecture #90, so the 2026 disproof of #90 disproves it; $500 was for the now-false upper bound, $50/$100 for the counterexample. Finite table: g(3)=6, g(4)=8, computed by Fishburn (Erdős–Fishburn, \"Minimum planar sets with maximum equidistance counts,\" Comput. Geom. 7(4):207–218, 1997). No extension to g(5) in ~30 years; no 2023–2026 movement found.","beatable":"WALL","beatable_reason":"The exact-value record g(5) is a real-algebraic wall, not a discrete search. The construction (upper-bound) side has a trivial verifier but lives in continuous R^{2n}, so our SAT/ILP/MIS/exhaustion farm only applies under a lattice/algebraic restriction, yielding non-rigorous best-known constructions — not the exact value, and not a prize (prize is dead). The nonexistence direction (\"no (n-1)-point set achieves f=k\") is a statement over the reals: realizability of a point/circle incidence structure in the plane is ER-complete, with no finite discrete/DRAT encoding; CAD is the honest tool and does not scale. This is the R(5,5)-upper-bound-style machinery mismatch, and Fishburn's own computation stalled at k=4 for 30 years.","fit_score":2,"impact_score":3,"impact_reason":"Prize is effectively dead: the $500 upper-bound conjecture is disproved and the counterexample bounty ($50) is subsumed by the #90 disproof. Distance problems are central Erdős combinatorics, but this specific max-equidistance-count table is a footnote that has drawn no activity in 30 years. No real-world relevance.","verifier":"Construction side only: given exact rational/algebraic coordinates of n points, compute all C(n,2) squared distances and check each point has some distance value with multiplicity >= k. O(n^2) exact, trivial. This verifies UPPER bounds on g(k) (constructions). NO finite verifier exists for the nonexistence/exact-value direction.","attack":"Only the soft side is tractable: ILP/local-search/SA to select subsets of triangular or square lattices (or small algebraic point families) maximizing the min equidistance count, with exact rational snapping, giving improved CONSTRUCTIONS = upper bounds on g(k) / lower bounds on f(n) for specific n. Modest CPU (single node, hours). But this cannot certify an exact g(5): ruling out all real (n-1)-point configs needs cylindrical algebraic decomposition over R, which is infeasible past tiny n. No DRAT-style nonexistence certificate is possible.","our_edge":"None beyond generic compute. Our verifier-first discrete farm has no purchase on the ER-complete nonexistence direction, and the construction side is a continuous-geometry optimization where our tooling offers no specific advantage over standard geometric search.","verdict":"PARTIAL classification, but WALL for the movable record. Headline is a disproved asymptotic conjecture (NONE for finite computation). The genuine finite sub-problem is the Erdős–Fishburn table g(k) = smallest n with f(n)=k (g(3)=6, g(4)=8). Its exact-value frontier (g(5)) is unreachable by our SAT/ILP/MIS/DRAT farm: the nonexistence direction is ER-complete over the reals with no discrete certificate, and the only tool-tractable side (lattice construction search) yields non-rigorous, non-prize best-known bounds. Poor fit; do not pursue.","lane":"wall","board_class":"NONE","board_class_reason":"headline disproved with #90; exact-value direction has no finite verifier; equality-constrained coordinates (R3 fails)","wall_reason":"headline disproved with #90; exact-value direction has no finite verifier; equality-constrained coordinates (R3 fails)","erdos_url":"https://www.erdosproblems.com/92","links":{"oeis":[],"arxiv":[]}},{"id":97,"title":"Convex polygon: every vertex has 4 equidistant others","prize":"$100","statement":"Does every convex polygon have a vertex with no other 4 vertices equidistant from it? A counterexample is a convex polygon where every vertex has >=4 other vertices at a common distance (>=4 others on a circle centered at it). Erdos conjectured yes (some vertex always fails); disproof = one finite counterexample.","finite_object":"A convex polygon (point set in the plane, ideally exact rational/algebraic coords) in which every vertex has at least 4 other vertices at a single common distance.","current_record":"k=3 fully achieved (conjecture false at 3): Danzer convex 9-gon (per-vertex varying distance) and Fishburn-Reeds 1992 convex 20-gon (uniform unit distance). k=4: NO example of any size known; open. AlphaEvolve (Google DeepMind, arXiv:2511.02864, Nov 2025) attacked this exact problem with an exact/interval-arithmetic verifier and reproduced only k=3, failing to reach k=4.","beatable":"WALL","beatable_reason":"The applicable search is continuous/algebraic local search over real vertex coordinates, and the SOTA instance of exactly that tool class (AlphaEvolve: exact verifier + Google-scale evolutionary/LLM search) targeted this precise problem in 2025 and failed to exceed the already-known k=3. It does NOT reduce to our discrete farm: no size parameter to exhaust, so SAT/ILP/max-independent-set/exhaustion don't apply; a k=4 witness lies on a measure-zero algebraic variety (many exact concyclic-equal-distance quadruples + convexity at once) reachable only by a symbolic/structural construction (a new idea, not more CPU). And Erdos's conjecture direction (nonexistence) is uncertifiable by finite computation -- unbounded vertex count, continuous coords, no DRAT/finite-size analogue -- so the R(5,5)-style certify-no-witness route is structurally unavailable.","fit_score":3,"impact_score":3,"impact_reason":"Only a $100 prize; a genuine but minor Erdos problem in combinatorial geometry. Mild field interest, some visibility from the AlphaEvolve case study, but no real-world relevance and low mathematical stakes relative to Ramsey/kissing records.","verifier":"Given rational vertex coords: (a) verify convex position (O(n) orientation checks) and (b) for each vertex, group squared distances to others and check some value has multiplicity >=4 (sort per vertex). Exact, O(n^2 log n). Cheap and clean.","attack":"If it were movable: simulated annealing / evolutionary search over vertex coords minimizing per-vertex max equidistance error, normalized by min side length, then snap to exact algebraic coordinates. This IS AlphaEvolve's approach and it failed at scale. The only credible route is symbolic -- pick a combinatorial concyclic-quadruple incidence pattern, set up the polynomial system for exact equal distances + convexity, and solve via Groebner bases / CAD -- which is symbolic algebra, not our SAT/MIS/SA farm, with severe combinatorial blowup and no success guarantee. Rough compute: unbounded / no bounded search space.","our_edge":"None beyond generic compute -- and generic verifier-first evolutionary compute (AlphaEvolve-class) already ran this exact problem at Google scale in 2025 and could not exceed k=3. Our SAT/ILP/MIS/DRAT edge (discrete, bounded-size, certifiable-nonexistence) does not transfer to this continuous/algebraic unbounded-size existence question.","verdict":"PARTIAL-leaning-NONE, WALL. Falsifiable finite existence with a clean exact poly-time verifier (the only axis that fits), but NOT our machinery: the witness hunt is continuous/algebraic with no numeric frontier to push and no bounded size, SAT/ILP/MIS/exhaustion don't apply, the nonexistence direction is uncertifiable by finite computation, and the SOTA verifier-first search (AlphaEvolve, 2025) already tried this exact problem and failed to beat the known k=3. Not STRONG. Recommend DROP -- no compute lever we own moves this frontier.","lane":"wall","board_class":"NONE","board_class_reason":"existence bounty with no numeric frontier, and the defining condition (4 equidistant points) is equality-constrained real geometry (R3 fails: rational restriction lossy)","wall_reason":"existence bounty with no numeric frontier, and the defining condition (4 equidistant points) is equality-constrained real geometry (R3 fails: rational restriction lossy)","erdos_url":"https://www.erdosproblems.com/97","links":{"oeis":[],"arxiv":["2511.02864"]}},{"id":101,"title":"Erdős #101 — 4-point lines o(n²), orchard A006065","prize":"$100","statement":"Given n points in R² with no five collinear, the number of lines containing exactly four points is o(n²). Asymptotic upper-bound conjecture; $100. Associated finite object: OEIS A006065, max number of 4-point lines (orchard, 4-per-row).","finite_object":"A point configuration of n points in R² (rational coords), no 5 collinear, maximizing the count of lines with exactly 4 points — OEIS A006065 (real) / A172992 (integer-coordinate variant).","current_record":"Exact optimal proven to n=20, a(20)=23 (Zhao Hui Du, exhaustive search, 2008–2010). Lower bounds beyond: a(22)≥28 (Du); Ed Pegg n=22 construction (2020); integer variant A172992 to n=27 (Kamenetsky, 2012). No exact-value progress since 2010.","beatable":"WALL","beatable_reason":"The prize headline is asymptotic (o(n²), no 5 collinear) — not finite-resolvable; a single config can't disprove it. The genuine finite frontier — extending exact/optimal A006065 values past n=20 — requires enumerating super-exponentially many order types AND certifying geometric realizability in R² (pseudoline stretchability, ∃R-complete/NP-hard). That is a real-algebraic realizability oracle, NOT a Boolean UNSAT/DRAT problem, so it does not map to our SAT/ILP/DRAT farm; it is the R(5,5)-upper-bound analog and has been stuck 16 years. The only tool-fittable crack — bumping a b-file lower bound (integer-grid SA/ILP, e.g. A172992) — is low-significance (integer optima are provably below the real optimum for several n), already worked by hobbyist grid search with no headroom, and the strong large-n records are algebraic (cubic-curve group law) that generic continuous/discrete search cannot out-produce.","fit_score":3,"impact_score":3,"impact_reason":"$100 prize attaches only to the asymptotic headline we cannot touch. The orchard 4-point variant is a classic, cute, OEIS-\"nice\" combinatorial-geometry object but niche; no real-world relevance. A b-file/OEIS lower-bound extension would be a minor, non-prize contribution.","verifier":"Exact rational determinant collinearity checker: for a candidate n-point set compute all C(n,4) collinearity tests (or sort slopes per point), count size-exactly-4 lines, assert no line has ≥5. O(n^4), microseconds for n≤30. Poly-time, cheap.","attack":"Exact-value direction (the real record): infeasible — order-type enumeration ~10^13+ by n≈13 and worse at n=21, plus a real-realizability oracle per type; DRAT-style nonexistence certs do not apply to ∃R. Lower-bound direction: SA/ILP over an integer grid maximizing exactly-4-point lines subject to no-5-collinear, seeded from cubic-curve constructions; cheap (~100 core-hours) but very unlikely to beat algebraic records and would only nudge a b-file, not claim the prize or an optimality record.","our_edge":"None beyond generic compute. Our cheap exact verifier is well-suited, but the movable side needs a realizability certificate (∃R), which our SAT+DRAT / MIS machinery does not produce; the record constructions are algebraic-geometry-driven.","verdict":"PARTIAL — genuine finite in-class sub-problem (A006065 exact values, an OEIS hard/nice/more extension target) exists, but for OUR toolkit it is a WALL: exact-value extension is a geometric-realizability (∃R) problem unsuited to SAT/ILP/DRAT and stuck since 2010; the only tool-fittable direction (lower-bound b-file bumps) is low-value and already at its feasibility limit against algebraic records. Recommend PASS.","lane":"wall","board_class":"NONE","board_class_reason":"collinearity is an equality constraint: optimal configurations may require irrational coordinates (ExistsR realizability gap), so a rational-witness board is not lossless (R3 fails); nonexistence side has no DRAT route","wall_reason":"collinearity is an equality constraint: optimal configurations may require irrational coordinates (ExistsR realizability gap), so a rational-witness board is not lossless (R3 fails); nonexistence side has no DRAT route","erdos_url":"https://www.erdosproblems.com/101","links":{"oeis":["A006065","A172992"],"arxiv":[]}},{"id":114,"title":"Erdős–Herzog–Piranian lemniscate max length","prize":"$250 (Erdős); falsification-only prize (disprove by counterexample).","statement":"Is the arc length of the lemniscate {z∈ℂ:|p(z)|=1} over monic degree-n polynomials maximized by p(z)=z^n−1?","finite_object":"None in our sense. The \"object\" is a monic polynomial in continuous coefficient space ℂ^{n−1}; the frontier is a transcendental arc-length functional, not a discrete combinatorial witness.","current_record":"Conjecture PROVEN for all sufficiently large n (Terence Tao, arXiv 2512.12455, Dec 2025), via Stokes/area-integral analysis; asymptotic bound ℓ ≤ 2n+4log2+o(1). z^n−1 proven a LOCAL maximum (Fryntov–Nazarov). n=2 (Bernoulli lemniscate) proven maximal (Eremenko–Hayman). n=3, n=4 remain OPEN. Conjectured max = B(1/2,n/2)=2n+4log2+O(1/n).","beatable":"WALL","beatable_reason":"Three independent walls. (1) No exact verifier: arc length of {|p|=1} is transcendental (elliptic integrals / beta function); a candidate can only be scored by high-precision numerical curve-tracing, never exactly or DRAT-certified — the core requirement of our farm is absent. (2) The counterexample is essentially ruled out: z^n−1 is a proven local maximum (kills local-search/annealing near the optimum) AND Tao proved the full conjecture for all large n (confines any counterexample to small n where the theory is strongest); AlphaEvolve's own search rapidly reconverged to z^n−1 with no counterexample. (3) The genuine open sub-problems (rigorous n=3, n=4; explicit large-n threshold) are continuous global-optimization/validated-numerics or hard-analysis problems — interval-arithmetic branch-and-bound over coefficient space or new theorems — not SAT/ILP/MIS/exhaustion. Every record here was set by hard analysis, not by tools we would use.","fit_score":2,"impact_score":4,"impact_reason":"Classical, famous Erdős problem freshly in the spotlight (Tao Dec 2025), so field significance is real, but prize is small ($250) and payable only by a counterexample that the strongest available theory says almost certainly does not exist; zero real-world relevance.","verifier":"Compute arc length of the level set {|p(z)|=1}: trace the (possibly multi-oval) curve and integrate ds numerically. NOT poly-time-exact — it is transcendental; rigorous certification would need interval-arithmetic enclosures of an elliptic-type integral over the whole level set. Cost: cheap for a heuristic float estimate, expensive and non-standard for a certified enclosure; no DRAT analog exists.","attack":"The only in-family attack is SA/local-search over monic coefficients maximizing numerically-estimated lemniscate length per small degree (n=3,4,5), hoping to beat ℓ(z^n−1). Rough compute: trivial (hours on a few cores) to run, but near-zero expected value — the objective's global max is a proven local max and the conjecture is proven for large n, so a \"hit\" is a lottery; and any numerical hit could not be exactly certified, only motivate a separate validated-numerics proof (branch-and-bound with rigorous integral enclosures over ℂ^{n−1}), which is a different discipline from our exact-witness farm.","our_edge":"None beyond generic compute. Our exact-verifier-first, discrete-witness/DRAT machinery does not apply to a transcendental continuous-optimization objective; the relevant tooling (validated numerics, complex analysis) is outside our precedent set (kissing/Ramsey/LP-SDP certificates).","verdict":"WALL / poor-fit. Genuinely open at small n (n=3,4) and at the explicit large-n threshold, so not pure-NONE in the abstract, but there is NO exact poly-time verifier (arc length is transcendental), the counterexample the $250 rewards is essentially precluded (z^n−1 is a proven local maximum and Tao proved the conjecture for all large n), and the real open sub-problems require validated numerics or new hard analysis — outside our SAT/ILP/MIS/exhaustion/DRAT precedent. Do not attack: near-zero EV, no certifiable witness path, no edge beyond generic compute.","lane":"wall","board_class":"NONE","board_class_reason":"transcendental objective (elliptic-integral arc length); no exact/DRAT verifier exists; Tao proved the conjecture for large n (Dec 2025)","wall_reason":"transcendental objective (elliptic-integral arc length); no exact/DRAT verifier exists; Tao proved the conjecture for large n (Dec 2025)","erdos_url":"https://www.erdosproblems.com/114","links":{"oeis":[],"arxiv":["2512.12455"]}},{"id":128,"title":"Erdős Sparse Half Conjecture (triangle-free)","prize":"$250","statement":"Must a graph G on n vertices in which every induced subgraph on ≥⌊n/2⌋ vertices has > n²/50 edges contain a triangle? Contrapositive of the Sparse Half Conjecture: every triangle-free graph on n vertices has a ⌊n/2⌋-vertex induced subgraph (\"half\") with ≤ n²/50 edges.","finite_object":"A putative counterexample: a single finite triangle-free graph on n vertices whose SPARSEST ⌊n/2⌋-vertex induced subgraph has strictly > n²/50 edges.","current_record":"Theorem side: Razborov (2021, \"More about sparse halves in triangle-free graphs\", flag-algebra/SDP) proved every triangle-free graph has a half with ≤ (27/1024)n² ≈ 0.02637 n² edges. Erdős-conjectured constant 1/50 = 0.02 n². Proven exactly in special cases: girth ≥5, independence number ≥2n/5 (Krivelevich), strongly regular graphs, and min-degree > 10n/29 / ≥5n/14 (Keevash–Sudakov and successors). Extremal tight examples: uniform blowup of C₅ and blowup of the Petersen graph, each hitting exactly n²/50 in the sparsest half. $250 prize.","beatable":"WALL","beatable_reason":"Three independent walls. (1) NON-POLY VERIFIER: certifying a candidate is a counterexample requires proving its sparsest ⌊n/2⌋-vertex induced subgraph has > n²/50 edges — that is exact Sparsest-k-Subgraph, NP-hard, a min over C(n,n/2) subsets. This directly fails the STRONG poly-time-verifier criterion; SAT/ILP can do it only for tiny n, which is exactly the uninteresting regime. (2) ZERO SLACK + object almost certainly nonexistent: the conjecture is widely believed TRUE, and the known tight constructions (C₅/Petersen blowups) hit the boundary EXACTLY (=n²/50), so a counterexample must strictly beat the best tight construction with no margin — decades of effort plus Razborov's flag-algebra evidence say none exists. (3) WRONG FRONTIER FOR A FARM: the live frontier is closing the analytic gap 27/1024 → 1/50, an SDP/flag-algebra THEOREM problem Razborov already pushed with heavy machinery; the extremal templates are known and a naive CPU-farm search over small weighted triangle-free templates just reproduces the flag-algebra LP, which certifies 27/1024, not 1/50. Small-n exhaustive/SAT search would only re-confirm no counterexample where results already guarantee it.","fit_score":2,"impact_score":5,"impact_reason":"Famous named Erdős conjecture (Sparse Half), a driver of the flag-algebra program and studied for ~50 years, so field significance is real. But the prize is tiny ($250), there is no real-world relevance, and a finite counterexample (which almost certainly does not exist) would upend belief rather than incrementally advance — the credible progress is theorem-side, not witness-side.","verifier":"Exact sparsest-half check = minimize induced edge count over all ⌊n/2⌋-subsets (NP-hard Sparsest-k-Subgraph). Cost: ILP/SAT feasible only for n≲40–60 per candidate; the meaningful regime is asymptotic blowups where the \"verifier\" becomes a fractional quadratic minimization over vertex weights (flag-algebra SDP).","attack":"If one insisted: enumerate triangle-free graphs / weighted triangle-free templates on ≤15–20 vertices, and for each optimize vertex blow-up weights to maximize the min fractional half density, seeking any template with min-half > 1/50 (LP/SDP inner problem per template, ILP for the discrete min-half). Rough compute: hours-to-days on ~100 cores. Expected outcome: NEGATIVE — reproduces C₅/Petersen at exactly 1/50 and Razborov's 27/1024 certified ceiling; no counterexample. Not worth farm time.","our_edge":"None beyond generic compute. Our exact-verifier + CPU-farm edge is neutralized because the verifier is itself NP-hard and the real object is a fractional/analytic extremum where flag-algebra SDP (Razborov) already dominates brute force.","verdict":"WALL / PARTIAL-at-best. The \"FALSIFIABLE by finite counterexample\" tag is technically true but misleading for our farm: (a) the verifier is NP-hard (sparsest-half), violating the poly-time-verifier requirement of STRONG; (b) the target object almost certainly does not exist — the conjecture is believed true, proven in many cases, and the tight examples hit the boundary EXACTLY with zero slack; (c) the genuine live frontier is the analytic gap 27/1024 → 1/50, an SDP/flag-algebra theorem Razborov already advanced, which brute force cannot match. A small-n SAT/ILP counterexample sweep would only re-confirm non-existence. Not a fit for verifier-first witness farming. Recommend PASS.","lane":"wall","board_class":"NONE","board_class_reason":"verifier is NP-hard (Sparsest-k-Subgraph); meaningful regime is flag-algebra SDP blowups, not finite witnesses","wall_reason":"verifier is NP-hard (Sparsest-k-Subgraph); meaningful regime is flag-algebra SDP blowups, not finite witnesses","erdos_url":"https://www.erdosproblems.com/128","links":{"oeis":[],"arxiv":[]}},{"id":142,"title":"Asymptotic formula for r_k(N), largest k-AP-free subset of [1,N]","prize":"$10,000 (Erdős) — for the asymptotic formula only; unclaimable by any finite computation (the problem page states this explicitly).","statement":"Let r_k(N) be the largest size of a subset of {1,...,N} with no non-trivial k-term arithmetic progression. Prove an asymptotic formula for r_k(N). (Erdős, $10,000.)","finite_object":"A k-AP-free subset S ⊆ [1,N] of a given size K (existence witness), or a DRAT/LRAT proof that no K-element k-AP-free subset of [1,N] exists (nonexistence certificate). Together they pin one exact table value r_k(N)=K. Targets: OEIS A003002 (k=3), A003003 (k=4), A003004 (k=5), A003005 (k=6).","current_record":"Prize headline (asymptotic formula) OPEN and explicitly \"cannot be resolved by finite computation\" — best asymptotics are Kelley–Meka upper bound (2023) and Behrend's 1946 lower bound for k=3; no matching formula. Finite table frontier: r_3 known exactly to N=211 (r_3(211)=43, Cariboni OEIS b-file). r_3(212) is an OPEN unit gap ∈ {43,44}: Ergezer, arXiv:2606.04016 (submitted 31 May 2026) found a 43-witness and ran CP-SAT + HiGHS MIP + CDCL/SAT, DRAT/LRAT-certifying 18 of 20 subproblem chunks, but two \"hard-pocket\" (T1c) chunks resisted 8-hour MIP audits and SAT re-attacks — so r_3(212)≤43 is NOT proven. Sibling frontiers: r_4 exact to N=142 (=58), r_5 to N=115 (=67), r_6 to N=147 (=95), tables largely from Gasarch-era small-n searches.","beatable":"WALL","beatable_reason":"The confirmed, most-studied frontier value r_3(212) was attacked in 2026 with exactly our toolkit — CP-SAT + MIP + CDCL/SAT + DRAT/LRAT — and walled: two chunks survived 8-hour MIP + SAT budgets. That is the R(5,5)-upper-bound situation (record set by the same tools we'd use, recent dedicated failure); brute compute alone almost certainly won't close it — it needs a new additive-combinatorial bound or custom branch-and-bound, i.e. a theorem, not a farm. The one genuinely MOVABLE-but-marginal opening: the stale r_4/r_5/r_6 tables (A003003/4/5, N≈115–147) predate modern CP-SAT+symmetry-breaking+DRAT and have seen no recent assault, so a few new exact OEIS terms are plausibly reachable — untested, and low-value (no prize, modest citation). Net: primary frontier walled; secondary opening speculative and marginal.","fit_score":9,"impact_score":3,"impact_reason":"The $10k and the field significance attach entirely to the asymptotic formula, which is pure analysis (Kelley–Meka / Behrend territory) — no finite witness touches it. The reachable finite contribution is extending an OEIS table by a term or two: real, publishable, citable, but not field-changing, not prize-bearing, no real-world use. r_k(N) is a marquee additive-combinatorics object, which lifts this above a 1–2, but the deliverable we could actually produce is marginal.","verifier":"Trivial and exact: given S ⊆ [1,N], check no 3 members form an AP by scanning all (a,d) pairs — O(N^2) or O(|S|^2) — and compare |S| to K. Nonexistence side verified by an external DRAT/LRAT checker on the UNSAT certificate. This is a textbook poly-time exact verifier, cost negligible relative to search.","attack":"Model [1,N] as 3-uniform-hypergraph independent set: Boolean x_i, clause (¬x_a∨¬x_b∨¬x_c) per k-AP, maximize Σx_i. Lower bound (witness): CP-SAT/local-search/SA maximize — cheap, finds K quickly. Upper bound (the hard part): assert Σx_i ≥ K+1 and prove UNSAT with Kissat/CaDiCaL, chunked by fixing a prefix + dihedral symmetry-breaking (S↔N+1−S), each chunk DRAT→LRAT certified. For r_3(212),K=44: two residual chunks estimated well beyond 8 core-hours each and resisted SAT+MIP — realistically 10^4–10^6 core-hours or a smarter bound = wall. For the next 1–3 terms of r_4/r_5/r_6 (N≈115–150, ~10^3 clauses, ~150 vars): modern solver + DRAT plausibly 10^2–10^4 core-hours on a 100-core farm — worth a cheap probe but no prize on offer.","our_edge":"Concentrated DRAT/LRAT-certified UNSAT on the last hard chunks is precisely the R(5,5) playbook we already ran. But on r_3(212) our edge over Ergezer is essentially none — same solvers, same certificates, he already spent the budget. The only real edge is venue timing: nobody has pointed a 2026-grade CP-SAT + symmetry-breaking + DRAT stack at the decade-stale r_4/r_5/r_6 tables. That is \"modern solver on an old table,\" not a structural advantage.","verdict":"PARTIAL. Headline is asymptotic/analytic — NONE for the prize (the page itself says finite computation cannot resolve it). But the in-class finite sub-problem — exact values r_k(N), the OEIS A003002–A003005 tables — is a flawless fit for our verifier-first, witness-or-DRAT farm: the checker is a trivial O(N^2) exact test and the search is hypergraph-MIS/SAT, identical in shape to R(5,5). The catch on beatability: the flagship movable number, r_3(212), was walled in 2026 (arXiv:2606.04016) by exactly our SAT+MIP+DRAT stack — two hard-pocket chunks resisted 8-hour budgets — so it is an R(5,5)-style wall, not a farmable number. The only honest opening is a low-value, untested probe: modern CP-SAT+DRAT on the stale r_4/r_5/r_6 tables for a few new terms. Recommend LOW priority — perfect machinery fit, but no prize on the finite side and the one prestigious frontier already at the wall.","lane":"wall","board_class":"NONE","board_class_reason":"asymptotic formula; the prize headline explicitly 'cannot be resolved by finite computation'; the finite r_k table object is carried by #140","wall_reason":"asymptotic formula; the prize headline explicitly 'cannot be resolved by finite computation'; the finite r_k table object is carried by #140","erdos_url":"https://www.erdosproblems.com/142","links":{"oeis":[],"arxiv":["2606.04016"]}},{"id":146,"title":"Erdős–Simonovits degenerate bipartite Turán conjecture","prize":"$500","statement":"If H is bipartite and r-degenerate (every subgraph has a vertex of degree ≤ r), then ex(n;H) ≪ n^{2−1/r} as n→∞.","finite_object":"None. A disproof requires an r-degenerate bipartite H plus a sequence of H-free graphs on arbitrarily large n with >Cn^{2−1/r} edges (an infinite construction + asymptotic lower bound); a proof requires an asymptotic upper bound over an infinite graph class. Neither is a finite witness.","current_record":"Open. Best partial results: Füredi (1991) and Alon–Krivelevich–Sudakov (2003, dependent random choice) proved the one-sided special case — H bipartite with max degree ≤ r on one side ⇒ ex(n;H)=O(n^{2−1/r}). For general r-degenerate bipartite H the best known is the weaker AKS bound ex(n;H)=O(n^{2−1/(4r)}). No 2023–2026 resolution of the full conjecture found.","beatable":"WALL","beatable_reason":"Pure asymptotic/analytic conjecture. Progress means improving the exponent bound (a theorem) over an infinite class; there is no record number to push, no finite object beating a threshold, and no exact verifier for ≪. This is the exponent-improvement analogue of an upper-bound wall (like R(5,5)'s upper bound = NONE), with no witness side to attack.","fit_score":1,"impact_score":5,"impact_reason":"Central, named conjecture in degenerate extremal graph theory (Erdős–Simonovits), but modest $500 prize and essentially zero real-world relevance; would be a significant theoretical result if resolved.","verifier":"No poly-time exact verifier for the ≪ claim; the only checkable object (exact ex(n;H₀) at small n via ILP/SAT, cost exponential in n) is disconnected from the conjecture.","attack":"No viable finite-computation attack. Small exact ex(n;H) via ILP/SAT is feasible but does not bear on the asymptotic exponent (the superlinear regime lies far beyond computable n), so it yields no contribution to #146. Any real move is a dependent-random-choice / algebraic-construction theorem — not our farm's shape.","our_edge":"none beyond generic compute","verdict":"NONE — downgrade from the PARTIAL triage. The headline is a universal asymptotic upper bound with a hidden constant; no finite witness, no exact verifier for ≪, and the proposed \"small exact Turán numbers\" sub-problem does not inform the asymptotic exponent, so it is not genuine in-class progress on this conjecture. A new theorem (exponent improvement via DRC/algebraic constructions) is the only path. Zero fit for our verifier-first CPU farm.","lane":"wall","board_class":"NONE","board_class_reason":"no poly-time exact verifier for the asymptotic claim; small-n ex(n;H0) values are disconnected from the conjecture","wall_reason":"no poly-time exact verifier for the asymptotic claim; small-n ex(n;H0) values are disconnected from the conjecture","erdos_url":"https://www.erdosproblems.com/146","links":{"oeis":[],"arxiv":[]}},{"id":161,"title":"Continuity/jumps of hypergraph discrepancy function F^{(t)}(n,α)","prize":"$500","statement":"F^{(t)}(n,α) is the smallest m such that the edges of the complete t-uniform hypergraph on n vertices can be 2-colored so that every X⊆[n] with |X|≥m contains ≥α·C(|X|,t) t-subsets of EACH color. Question ($500): for fixed n,t, as α goes from 0 to 1/2, does F^{(t)}(n,α) increase continuously or with jumps — and is there only one jump (at α=0)?","finite_object":"For fixed small n,t and rational α, F^{(t)}(n,α) is an exact finite quantity: a min over 2-colorings (for t=2, over graphs on n vertices up to iso) of the largest 'unbalanced' subset size + 1. Exhaustive-up-to-iso is feasible to ~n=11–12 for t=2 (12,346 graphs at n=8, ~12M at n=10).","current_record":"No numeric record exists — the frontier is a growth RATE, not a value. Best known: Erdős–Hajnal bounds giving F^{(t)}(n,α) growing from an iterated logarithm (small α) to a power of log n (α→1/2), the upper regime conditional on the Erdős–Hajnal–Rado conjecture. The continuity/jump question is fully OPEN; Erdős conjectured the only jump is at α=0. No 2023–2026 resolution found.","beatable":"WALL","beatable_reason":"The $500 frontier is asymptotic (growth-order of F as n→∞ across a continuum of α) — no finite witness, no record number, only a new theorem resolves it; the problem's own metadata says resolvable_by_finite_computation=False. The genuine in-class finite sub-problem (exact small-case F-tables) is computationally trivial but doubly non-illuminating: (1) the phenomenon is iterated-logarithmic, so log*n / log n / (log n)^c are indistinguishable order-1 constants at any reachable n (≤~12); (2) at finite n, F(n,α) is trivially a step function in α (jumps at every achievable rational density j/C(k,2)) — an integrality artifact unrelated to the asymptotic growth-order jump the conjecture is about. So the finite table would mislead, not help, and there is no established record it beats.","fit_score":3,"impact_score":4,"impact_reason":"$500 prize (small). Field significance moderate: classical Erdős discrepancy/Ramsey theory, tied to tower-type Erdős–Hajnal–Rado growth questions. Real-world relevance nil. But entirely out of reach for our method, so realizable impact for us is ~0.","verifier":"Poly-time exact checker: for a given coloring, over all 2^n subsets X compute minority-color density min(e_red,e_blue)/C(|X|,t); the condition fails at m iff some |X|≥m has density<α. O(2^n · poly) per coloring — trivial for small n. Verifier is clean; the object it verifies is just worthless toward the prize.","attack":"MOVABLE only in the vacuous sense: exhaustive-up-to-iso enumeration of graphs (nauty/geng) for t=2, n≤11–12, and t=3 for tiny n, computing α↦F^{(t)}(n,α) step functions via a 2^n-subset density scan per coloring. ~hours on a few cores; no SAT/DRAT needed. But this produces a table (absent from OEIS) that cannot see the iterated-log regimes and whose 'jumps' are integrality artifacts — it does not touch the $500 question. Not worth farm time.","our_edge":"None beyond generic compute. Our verifier-first exact-witness machinery maps mechanically onto the small-case checker, but the prize is an asymptotic growth-order theorem where witnesses/records don't exist. Unlike R(5,5) (where the lower-bound witness was a concrete finite graph) or kissing (a concrete config beating a number), there is no finite object here whose discovery constitutes progress on the stated question.","verdict":"PARTIAL-in-class but WALL-for-us. There IS a genuine finite sub-problem — exact 2-coloring search over the complete t-uniform hypergraph with a poly-time checker to tabulate small-n,t exact values of F^{(t)}(n,α) — so it is not NONE. But the $500 headline is asymptotic (growth-order continuity/jumps as n→∞) and explicitly not finite-computable; the finite sub-problem is both computationally trivial AND non-illuminating (iterated-log scale invisible at reachable n; finite 'jumps' are integrality artifacts distinct from the asymptotic jump). There is no numeric record to beat. Do not attack — no farm advantage, no prize-relevant witness. Class: PARTIAL; beatability: WALL.","lane":"wall","board_class":"NONE","board_class_reason":"no numeric record exists - the frontier is a growth rate, not a value","wall_reason":"no numeric record exists - the frontier is a growth rate, not a value","erdos_url":"https://www.erdosproblems.com/161","links":{"oeis":[],"arxiv":[]}},{"id":182,"title":"Max edges without a k-regular subgraph (Erdős–Sauer)","prize":"$100 (offered by Erdős for k=3) — effectively resolved; not collectible via finite computation.","statement":"Let k≥3. What is the maximum number of edges f_k(n) that an n-vertex graph can have without containing a k-regular subgraph? Erdős–Sauer asked (with a $100 prize for k=3) whether it is n^{1+o(1)}.","finite_object":"A finite object exists only in the (untracked) sub-problem: an n-vertex extremal graph with f_k(n) edges and no k-regular subgraph, plus a certificate that every graph with f_k(n)+1 edges contains one. No such small-n table is published or maintained.","current_record":"Headline PROVED: f_k(n)=Θ_k(n log log n). Upper bound O(n log log n) with C(k)≪k^2 by Chakraborti–Janzer–Methuku–Montgomery (arXiv 2411.11785, 2024), following Janzer–Sudakov's resolution (Forum Math Pi 11 e19, 2023) that settled the $100 k=3 case; matching lower-bound construction by Pyber–Rödl–Szemerédi (1995). No published or OEIS small-n exact table for f_k(n).","beatable":"WALL","beatable_reason":"The asymptotic answer is a THEOREM (Janzer–Sudakov 2023, tightened 2024) — no computation touches it and the $100 prize is effectively resolved. The only finite angle is exact small-n f_k(n), but (1) there is NO record to beat: no OEIS entry, no published small-n table, no community-tracked frontier — we would be minting an uncited curiosity, not moving a recognized number; (2) the verifier is NP-complete, so this fails the STRONG poly-time-verifier bar; (3) fixing f_k(n) is a two-level (Σ₂-shaped) search — construct a no-k-regular graph AND prove every (m+1)-edge graph forces one — requiring canonical-graph exhaustion (nauty) that blows up past n≈10–12. Unlike R(5,5)/kissing, there is no clean single witness-or-DRAT target and no held record whose defeat would count.","fit_score":3,"impact_score":2,"impact_reason":"The $100 prize question is PROVED (asymptotically tight, 2023–2024); no open prize remains. Exact small-n values are not a tracked target (no OEIS, no published table), have no downstream or real-world relevance, and would be an uncited exercise. Field significance of any small computation here is negligible.","verifier":"\"Contains a k-regular subgraph?\" is NP-COMPLETE for every k≥3 (Chvátal/Garey–Johnson; cubic-subgraph NP-c even on bipartite max-deg-4). So there is NO poly-time exact verifier. Existence of a k-regular subgraph has a trivial poly certificate (exhibit it); NON-existence needs a SAT-UNSAT/DRAT proof. Determining f_k(n) additionally requires the ∀-over-all-graphs upper bound (a second, harder exhaustion). Cost: per-graph SAT is cheap for n≲12 but the outer max-edge + all-graph search explodes.","attack":"If pursued anyway (low value): CEGAR loop — outer ILP/SAT maximizes edge count on n labeled vertices; inner oracle SAT-checks for a k-regular subgraph and, when found, adds a blocking/forbidding clause; iterate to the max-edge no-k-regular graph. Pair with nauty canonical enumeration to certify the +1-edge upper bound. Feasible only to n≈10–12 on a ~100-core farm (hours–days); DRAT-certifiable per instance but no external record to validate against. Beyond n≈12 the labeled-graph search and NP-complete inner checks become infeasible.","our_edge":"None beyond generic compute. Our SAT+DRAT nonexistence machinery fits the \"no k-regular subgraph\" leg, but there is no target record, the prize is claimed, and the upper-bound exhaustion is outside our verifier-first witness-or-nothing sweet spot.","verdict":"PARTIAL problem-class, WALL for our farm — PASS. The headline Erdős–Sauer question is a proved theorem (Θ_k(n log log n), Janzer–Sudakov 2023 / CJMM 2024), immovable by computation. The one finite sub-problem — exact small-n f_k(n) — is well-defined and in-class but has no published record/OEIS table to beat, an NP-complete verifier (fails the poly-time-verifier bar), and a doubly-quantified graph-exhaustion that explodes past n≈12. There is no witness-or-DRAT target whose defeat would register as progress. Recommend no attack; impact and fit are both low.","lane":"wall","board_class":"NONE","board_class_reason":"'contains a k-regular subgraph' is NP-complete for k >= 3: no poly-time exact verifier","wall_reason":"'contains a k-regular subgraph' is NP-complete for k >= 3: no poly-time exact verifier","erdos_url":"https://www.erdosproblems.com/182","links":{"oeis":[],"arxiv":["2411.11785"]}},{"id":211,"title":"Erdős #211 — Beck/Szemerédi-Trotter (finite residue: orchard 3-point lines)","prize":"$100 (Erdős #211, but problem is SOLVED — not claimable). Orchard sub-problem carries no formal prize.","statement":"Let 1≤k<n. Given n points in R² with at most n-k on any line, there are ≫ kn lines containing at least two points (in particular 2n points, ≤n on a line ⇒ ≫n² lines). PROVED by Beck 1983 and Szemerédi–Trotter 1983. Erdős's constant-1/6 speculation ((1+o(1))kn/6) ties to the finite orchard-planting problem: maximize t3(n) = lines through exactly 3 of n points with no 4 collinear (~n²/6).","finite_object":"A set of n real-plane points (rational/algebraic coords) with no 4 collinear, maximizing the number of exactly-3-point lines. Concrete open targets: a 32-line witness at n=15, a 42-line witness at n=17, or improved lower bounds for n=18–25.","current_record":"Orchard t3(n) (OEIS A003035, updated Sep 2025): exact proven only through n=14 (a(14)=26). OPEN: a(15)∈{31,32}, a(17)∈{40,41,42}; a(16)=37 known. Green–Tao 2013 (arXiv:1208.4714): a(n)=⌊n(n-3)/6⌋+1 for sufficiently large n (ineffective threshold; gives 31 at n=15). Lower bounds to n=25 in Erich Friedman's table. Constructions: Burr–Grünbaum–Sloane 1974 (elliptic functions), Pegg/Zhao Hui Du (Mathematica), Padmanabhan–Shukla 2020 (elliptic curves over F_p). Headline #211 itself is SOLVED (Beck; Szemerédi–Trotter 1983), $100 prize not claimable.","beatable":"WALL","beatable_reason":"Continuous real-plane extremal problem, wall on both sides. Witness side: extra 3-point lines require exact algebraic alignment (collinearity is measure-zero), so blind SA/MIS/exhaustion on a CPU farm essentially never lands them — record configs live on cubics/elliptic curves and expert algebraic search already sits at these values. Nonexistence side (certify a(15)≤31): needs rank-3 oriented-matroid / order-type enumeration on 15 elements (complete enumeration exists only to n≈11–12) AND realizability over R is the existential-theory-of-reals, so non-realizable matroids produce false witnesses and there is NO clean DRAT certificate — the fatal difference from R(5,5)'s faithful pure-graph SAT. Only enumerable lane is the Padmanabhan–Shukla elliptic-curve-over-F_p family (clean verifier) but it has already resisted this exact approach.","fit_score":3,"impact_score":3,"impact_reason":"Headline #211 is fully solved (no claimable prize; nominal $100). The classic orchard sub-problem is well-known and touched by Green–Tao, giving moderate field significance, but open small cases (a(15), a(17)) and n=18–25 lower bounds are niche recreational/discrete-geometry records with essentially no real-world relevance.","verifier":"Exact and cheap: for a candidate point set, test every one of the C(n,3) triples for collinearity via an integer/rational 3×3 determinant, reject if any line holds ≥4 points, count exactly-3-point lines. O(n³) = 455 determinant checks at n=15 — trivial, fully exact. (Verifier is clean; it's the SEARCH/nonexistence-certificate that is the wall.)","attack":"Only viable lane: enumerate structured algebraic families with rational/finite-field incidences rather than blind coordinate search. Concretely, search Padmanabhan–Shukla-style configs — n-point subsets of elliptic curves over F_p (or torsion/group-law patterns on plane cubics) — for a 32-line arrangement at n=15 or lower-bound improvements at n=18–25, each candidate exact-verified by the determinant checker. Compute is modest (single machine, hours) because the family is parametrized; the CPU farm adds little since the bottleneck is finding the right algebraic structure, not raw enumeration. Nonexistence (a(15)≤31) is out of reach: no faithful DRAT route past the realizability gap.","our_edge":"None beyond generic compute. Our clean exact verifier is real but not the binding constraint; our SAT/DRAT/MIS farm is mismatched to a real-plane, realizability-gapped, measure-zero-incidence problem. No specific edge over the algebraic-construction expertise (Pegg, Du, Padmanabhan–Shukla) that already holds these records.","verdict":"PARTIAL-but-poor-fit. Headline is a proved asymptotic theorem (NONE). The orchard finite sub-problem has genuinely open exact values (a(15)∈{31,32}, a(17)∈{40,41,42}) and open lower bounds to n=25, so it is PARTIAL not NONE — a real in-class finite target. But beatability is a WALL for our verifier-first farm: the clean determinant verifier does not help because (a) witnesses demand exact algebraic alignment that blind SA/exhaustion cannot produce, and (b) nonexistence requires infeasible order-type enumeration with an existential-theory-of-reals realizability gap that blocks DRAT certification. Only the narrow elliptic-curve construction lane is UNKNOWN, and it has already resisted the same approach. Recommend PASS.","lane":"wall","board_class":"NONE","board_class_reason":"same ExistsR/collinearity obstruction as #101 - orchard-type equality-constrained geometry (R3 fails)","wall_reason":"same ExistsR/collinearity obstruction as #101 - orchard-type equality-constrained geometry (R3 fails)","erdos_url":"https://www.erdosproblems.com/211","links":{"oeis":["A003035"],"arxiv":["1208.4714"]}},{"id":500,"title":"Turán tetrahedron K_4^3 extremal number","prize":"$500 (Erdős — for the asymptotic density of any single K_ℓ^r, ℓ>r≥3; unclaimed)","statement":"Determine ex_3(n, K_4^3): the maximum number of triples on n vertices such that no 4 vertices span all 4 of their triples (tetrahedron-free). Turán (1961) conjectured the extremal density is 5/9.","finite_object":"A K_4^3-free 3-uniform hypergraph on n vertices with MORE than A140462(n) triples (would disprove Turán), OR a DRAT certificate that none exists with A140462(n)+1 triples (exact upper bound at that specific n).","current_record":"Finite lower bound = Turán's construction = A140462(n), a closed-form polynomial (a(3k)=5/2 k^3-3/2 k^2, etc.), believed exact; multiple extremal families by Brown, Kostochka, Fon-der-Flaass, Frohmader, Razborov. Asymptotic upper bound on the density π(K_4^3) ≤ 0.561666 (Razborov 2010, flag-algebra SDP; earlier Chung–Lu 0.5936). Conjectured density 5/9 ≈ 0.5556. NO published table of exact small-n ex_3(n,K_4^3) values exists (confirmed across searches). No movement 2023–2026 on the exact-value or asymptotic front via combinatorial search; only ℓ_2-norm variants (Balogh et al. 2022, 2025) and flag-algebra refinements.","beatable":"WALL","beatable_reason":"Three-way wall. (1) The headline $500 is the ASYMPTOTIC density (conjectured 5/9) — pure analytic, needs a theorem, no finite witness. (2) The finite lower-bound \"record\" IS a closed-form formula (A140462, Turán's construction), believed tight; beating it = disproving Turán's 1961 conjecture, astronomically unlikely at small n. (3) The finite upper-bound (prove no K_4^3-free graph on n vertices exceeds the formula) is exponentially degenerate: Frohmader proved Ω(6^{n/3}) non-isomorphic conjectured-extremal hypergraphs exist — the literature names this exact degeneracy as WHY the problem is hard, and it makes DRAT-UNSAT proofs blow up past tiny n.","fit_score":4,"impact_score":3,"impact_reason":"Famous problem, real $500 prize, high field significance in extremal combinatorics — but ALL of that attaches to the asymptotic 5/9 conjecture, which finite computation cannot touch. The only thing our farm could realistically produce (one more small-n exact value) is a curiosity with zero bearing on the prize or the frontier, which is precisely why no such table has ever been published. Realistic achievable impact ≈ nil.","verifier":"K_4^3-free check: for every one of the C(n,4) 4-subsets, at least one of its 4 triples is absent. O(n^4), exact, poly-time — an excellent cheap verifier. (Cost is trivial; it's the search/UNSAT-proof side that walls out.)","attack":"ILP: binary x_T per triple; for each 4-set, sum of its 4 triples ≤ 3; maximize sum(x). Or SAT: C(n,3) vars, C(n,4) tetrahedron clauses + a cardinality constraint ≥ formula+1, prove UNSAT with DRAT, plus S_n symmetry-breaking. Rough compute: n≤10 minutes; n=11–13 hours-to-hard even with aggressive symmetry breaking; the Ω(6^{n/3}) near-extremal degeneracy walls it beyond that. A ~100-core farm does not change the exponential, and even a success only CONFIRMS ex(n)=formula for one more n — a curiosity that (by the same degeneracy) tells you nothing about the asymptotic frontier.","our_edge":"None beyond generic compute. The one competitive frontier — the asymptotic UPPER bound — lives in SDP/flag-algebra machinery (Razborov, Baber–Talbot, Vaughan), not our SAT/ILP/MIS farm; we have no edge there. The \"extend A140462\" hook is a mirage (it's a formula, not computed data).","verdict":"SKIP. PARTIAL by the letter — a genuine in-class finite sub-problem exists (exact ex_3(n,K_4^3) via ILP/SAT with an O(n^4) exact verifier) — but beatable = WALL and impact ≈ nil. This is R(5,5) inverted: there the movable computational part was the witness/lower bound and the upper bound was NONE; here the lower bound is a tight closed formula (A140462) and only the exponentially-degenerate upper bound is computational. The triage's \"extend OEIS A140462\" premise is a miscategorization: A140462 is Turán's conjectured construction value in closed form (known to n=10000), not a table of computed extremal numbers — there is nothing to extend. The $500 is asymptotic and untouchable by our tools; the asymptotic upper-bound frontier is SDP/flag-algebra where we have no edge. Do not attack.","lane":"wall","board_class":"NONE","board_class_reason":"finite lower bound is a closed-form construction (A140462) believed exact, not an open tracked frontier; density side carried by #712","wall_reason":"finite lower bound is a closed-form construction (A140462) believed exact, not an open tracked frontier; density side carried by #712","erdos_url":"https://www.erdosproblems.com/500","links":{"oeis":["A140462"],"arxiv":[]}},{"id":548,"title":"Erdős–Sós conjecture (trees in dense graphs)","prize":"$100","statement":"Every graph on n vertices with at least (k-1)/2·n + 1 edges contains every tree on k+1 vertices (k edges); equivalently average degree > k-1 forces every k-edge tree. Open, $100, believed TRUE.","finite_object":"A single counterexample graph G plus a specific (k+1)-vertex tree T: e(G) ≥ (k-1)/2·|V(G)| + 1 yet T ⊄ G. Finite and cheaply checkable, but almost certainly nonexistent and unbounded in n/k.","current_record":"No numeric record — open conjecture. Best-known frontier: proven for large k (Ajtai–Komlós–Simonovits–Szemerédi, ~1990s announcement); large trees with near-spanning host (Reed–Stein, arXiv:2405.15733, 2024 rev. 2025); spiders (Fan–Sun, all leg lengths; Woźniak legs≤2); caterpillars (Perles, 2017); bounded-degree trees + dense hosts (1906.10219); near-diagonal k=n-1,n-2,n-3 (Woźniak), n-4 (Tiner), n=k+4 (Wang/Li 2014). No counterexample known or expected.","beatable":"WALL","beatable_reason":"Two-direction split. Positive direction (conjecture true) is NOT finitely certifiable: for fixed k the host size n is unbounded and no absolute bound reduces it to a finite check — needs a theorem, not compute. Counterexample direction is the only finite-witness path, but the object is believed not to exist: AKSS proved ES for all large k (so any counterexample is small-k), and small k is exactly where it is most verified (paths, spiders incl. k≤10, caterpillars, bounded-degree+dense hosts, n=k+O(1), Reed–Stein 2024 near-spanning). A witness hunt here is R(5,5)-witness-style: overwhelming expert belief and proof progress say the object isn't there.","fit_score":3,"impact_score":5,"impact_reason":"Famous, long-standing named conjecture (high field significance); disproof would be a major result. But only a $100 prize, near-zero realistic success probability (conjecture believed and largely proven), and no real-world relevance. Our realistically achievable contribution is null.","verifier":"Exact and cheap for a CLAIMED counterexample: edge-count check (trivial) + subgraph-isomorphism T↪G for a fixed (k+1)-vertex tree T, poly in n via color-coding / bounded-pattern search (O(n^{O(k)}) naive, FPT in k). The verifier is fine; the problem is there is no bounded search space to run it over (n unbounded) and the positive direction has no finite certificate.","attack":"Only conceivable attack: SAT/ILP or exhaustive counterexample hunt — for small trees T (small k) encode \"G on n vertices, e(G) ≥ (k-1)/2·n+1, and G avoids T\" and search over n up to feasibility (~n≤20–25, k≤~8) on the CPU farm; verify any hit with the exact subgraph-iso checker. Rough compute: modest (hours–days on ~100 cores). Expected outcome: UNSAT everywhere reachable (region already covered by AKSS + small-case theorems), producing no new result. No positive-direction certificate is possible (unbounded n). Recommend NOT pursuing.","our_edge":"None beyond generic compute. Our exact-verifier moat doesn't help: the verifier is the easy part; the hard part (bounded search domain / positive certificate) does not exist for this problem.","verdict":"PARTIAL — a genuine finite sub-problem exists (exhaustive small-(n,k) verification / bounded SAT counterexample search with a clean exact poly verifier), so not NONE; but not STRONG: no numeric record to push and the positive direction is not finitely certifiable (unbounded n). Beatable status is WALL: the only finite object (a counterexample) is nearly certainly nonexistent, ruled out at large k by AKSS and at small k by extensive theorems.","lane":"wall","board_class":"NONE","board_class_reason":"no finite search space (n unbounded) and no numeric record; positive direction has no finite certificate","wall_reason":"no finite search space (n unbounded) and no numeric record; positive direction has no finite certificate","erdos_url":"https://www.erdosproblems.com/548","links":{"oeis":[],"arxiv":["2405.15733"]}},{"id":588,"title":"Erdős #588 — f_k(n)=o(n²) for k≥4 (orchard-type k-rich lines)","prize":"$100 (Erdős, [Er84])","statement":"Let f_k(n) be minimal such that any n points in R² with no k+1 collinear span at most f_k(n) lines containing ≥k points. Is f_k(n)=o(n²) for k≥4? ($100, open.) Finite in-class sub-problem: exact small-n orchard-type extremal values — max lines of exactly k points with no k+1 collinear (OEIS A006065 for k=4, A008997 for k=5).","finite_object":"A point configuration in R² (equivalently an incidence/line-arrangement structure) of n points, no k+1 collinear, maximizing the count of lines with exactly k points — the orchard-type extremal config for a given (n,k).","current_record":"Headline conjecture OPEN (no proof either way); best construction n^{2-c/√log n} collinear k-tuples, Solymosi–Stojaković 2013 (still o(n²), so consistent with conjecture). Finite tables: A006065 (k=4) proven optimal up to n=20, value 23 — Zhao Hui Du, distributed exhaustive incidence enumeration + Gröbner realizability, ~2010; lower-bound constructions to n=25 (Friedman; Ed Pegg n=22, 2020). A008997 (k=5) sparse, Friedman bounds to n=21.","beatable":"WALL","beatable_reason":"Continuous-geometry extremal problem, not a SAT/ILP/MIS instance. Upper-bound frontier (n≥21, k=4) is bottlenecked by abstract line-incidence enumeration + Gröbner-basis realizability — the exact specialized comp-alg-geom pipeline the record-holder already built and optimized, explicitly prohibitive beyond n≈20; our farm doesn't do this and has no edge. Lower-bound/witness direction is killed by measure-zero collinearity: float SA/local-search cannot land on exact k-fold incidences, and record configs require algebraic (cubic-curve/group-law) coordinates. Grid restriction (A172992) is SAT/ILP-able but yields strictly weaker-than-record configs. Same posture as R(5,5)'s upper-bound side: computational-looking but at the feasibility wall for the tools we own.","fit_score":3,"impact_score":4,"impact_reason":"Classic, charming Erdős problem but only $100; asymptotic headline is a niche incidence-geometry question with essentially no real-world relevance. Extending an orchard table by one term (n=21, k=4) would be a real but small, non-prize-claiming contribution to the sibling problem #669, not to #588's headline.","verifier":"Given n points with exact rational/algebraic coordinates: check every pair-generated line hits ≤k points (no k+1 collinear) and count lines with ≥k points. O(n²log n)–O(n³), trivially cheap. Poly-time exact — fits verifier-first, but only verifies; it does not constrain the continuous search.","attack":"Two candidate lines, both walled. (a) Upper bounds n≥21,k=4: exhaustively enumerate combinatorial line-arrangements, prune by projective symmetry (nauty), test real/complex realizability via Gröbner bases (Maxima/PARI). This replicates the 2010 record tool; compute grows super-exponentially, no advantage from a 100-core SAT/MIS farm. (b) Lower-bound witness: optimize over R^{2n} for more k-lines than Friedman's best (n=21–25 k=4; n=16–21 k=5). Requires exact algebraic coordinates — SA/MIS/ILP over floats or a bounded grid give weaker configs than existing algebraic constructions. No realistic compute path to a new record with our toolkit.","our_edge":"None beyond generic compute. Our SAT/DRAT/MIS/SA/LP farm does not map to Gröbner-realizability enumeration (the record pipeline) nor to exact-algebraic construction (the record constructions). We hold no comp-alg-geom instrument that beats Zhao Hui Du's 2010 stack.","verdict":"PARTIAL headline (asymptotic o(n²), inherently non-finite — Solymosi–Stojaković construction stays o(n²) so the conjecture is still open, not computationally decidable), WITH a genuine finite in-class sub-problem: the orchard-type exact tables A006065/A008997. But that sub-problem is a WALL for our machinery — the verifier is cheap and clean, yet the search is continuous-coordinate comp-alg-geom (Gröbner realizability for upper bounds; exact algebraic constructions for witnesses), not SAT/ILP/MIS/SA. Measure-zero collinearity defeats float search; grid restriction is strictly weaker than standing records; the record pipeline is precisely the specialized tool we lack. No edge. Do not attack.","lane":"wall","board_class":"NONE","board_class_reason":"same ExistsR/collinearity obstruction as #101 (R3 fails); the continuous search is unconstrained by the verifier","wall_reason":"same ExistsR/collinearity obstruction as #101 (R3 fails); the continuous search is unconstrained by the verifier","erdos_url":"https://www.erdosproblems.com/588","links":{"oeis":["A006065","A008997"],"arxiv":[]}}],"total":24,"limit":20,"next_cursor":"YXRsYXMtdjE6b0Y0WlRzbWlDN3dKRzJLdToyMA"}