Erdős problem #589 — wave w045

Date checked: 2026-07-31 UTC.

Claim labels used throughout:

• [a] elementary-rigorous: proved here directly from definitions.
• [b] rigorous-modulo-named-theorem: rigorous assuming the named

published theorem.

• [c] plausible/structural-unverified: a search conclusion, heuristic, or

unrefereed claim, not promoted to a theorem here.

• [d] computational-only/source-verified: an exact finite computation or

a direct observation from a fetched source.

0. Mandatory live-page gate

[d: live-page source check] I fetched <https://www.erdosproblems.com/589> through the Bright Data cloud-browser route on 2026-07-31. It rendered the actual page, not a Cloudflare challenge. I also fetched the LaTeX view, dynamic bibliography entries, history page, proof-claim count, and the complete discussion thread.

Verbatim current statement

Let \(g(n)\) be maximal such that in any set of \(n\) points in \(\mathbb{R}^2\) with no four points on a line there exists a subset on \(g(n)\) points with no three points on a line. Estimate \(g(n)\).

Status, claims, and participation markers

| live-page field | current value | |---|---:| | status badge | OPEN | | comments | 1 | | claimed proofs | 0 | | likes this problem | Aron | | interested in collaborating | None | | currently working on this problem | None | | looks difficult | None | | looks tractable | None | | results could be formalisable | None | | working on formalising the results | None |

[d] There is therefore no claimed proof, solved/falsified status, or current worker. The mandatory stop rule did not trigger.

The sole comment

[d] The only comment, by onetwothreefour at 00:38 on 24 July 2026, reports the spelling correction “Füeredi” to “Füredi”, discloses minor AI-assisted typo finding, and asks that the comment be deleted after the correction. It contains no mathematical claim or work announcement.

Known results displayed on the page

[d: page transcription] The page records:

1. the greedy lower bound \(g(n)\gg n^{1/2}\);
2. the analogous no-\(k\)/find-no-\(l\) problem for \(3\leq l<k\);
3. Erdős's former expectation \(g(n)\gg n\), and the contrary fact

\(g(n)=o(n)\) via the density Hales--Jewett theorem;

1. the displayed attribution

\[ n^{1/2}\log n\ll g(n)=o(n) \] to Füredi [Fu91b]; and

1. the Balogh--Solymosi upper bound

\(g(n)\ll n^{5/6+o(1)}\).

The dynamic bibliography gives:

• [Er84] P. Erdős, Research problems, Period. Math. Hungar. 15

(1984), 101--103;

• [FuKa91] H. Furstenberg and Y. Katznelson, *A density version of the

Hales-Jewett Theorem*, J. Analyse Math. 57 (1991), 64--119;

• [Fu91b] Z. Füredi, *Maximal independent subsets in Steiner systems and

in planar sets*, SIAM J. Discrete Math. 4 (1991), 196--199; and

• [BaSo18] J. Balogh and J. Solymosi, *On the number of points in general

position in the plane*, Discrete Analysis 2018:16, 20 pages.

Important source discrepancy

[d: primary-source check] The live page's literal \(n^{1/2}\log n\) lower bound does not match the cited primary source. The SIAM abstract for Füredi's paper states

not \(\Omega(\sqrt n\log n)\). The 2024 primary preprint discussed below also writes \(\Omega(\sqrt{n\log n})\). I preserve the live text above as required, but all deductions in this report use the result actually stated in the cited paper.

1. Primary-source and current-literature audit

1. [d] The original 1984 scan

exists. On page 102 Erdős defines \(g(n;k,l)\); the present problem is \(g(n;3,2)\). He records the greedy square-root bound and says he could not disprove a linear lower bound.

1. [b] Füredi's published abstract at

DOI 10.1137/0404019 proves, in the notation of this problem, \[ \Omega(\sqrt{n\log n})\leq g(n)=o(n). \] This simultaneously verifies the lower bound and the qualitative sublinear construction attributed to him.

1. [d] Furstenberg--Katznelson's cited paper exists at

DOI 10.1007/BF03041066, with the stated title, journal, volume, year, and pages.

1. [b] Balogh and Solymosi's

published paper and arXiv:1704.05089 state the \(n^{5/6+o(1)}\) construction with no four collinear.

1. [d] Balogh, Clemen, Dumitrescu, and Liu,

Subset selection problems in planar point sets (2024), explicitly writes for fixed \(s\geq3\) \[ \Omega(\sqrt{n\log n})\leq f(n,s)\leq f(n,3) \leq n^{5/6+o(1)}. \] Its new bounds concern nonconstant \(s\); at \(s=3\) it does not improve the exponent for #589.

1. [d: especially recent source check] Oliver Roche-Newton,

A general-position problem for planar line arrangements (submitted 28 July 2026), proves a claimed \(4/5+\delta\) exponent for an affine line-concurrency dual. The paper itself explicitly says this does not improve the original point problem: its construction has large parallel subfamilies, which become large collinear point sets after dualisation. Thus I do not transfer its \(4/5\) exponent to \(g(n)\).

1. [c: honest search miss] Exact-statement, title, forward-reference,

arXiv, general-position-subset, and no-four-collinear searches found no primary source improving the constant-\(s=3\) bounds after Balogh and Solymosi. This is a search result, not a theorem that no such paper exists.

The source-verified asymptotic bracket used here is therefore

2. Exact hypergraph reduction

Given an admissible point set \(P\), define a 3-uniform hypergraph \(H(P)\) on vertex set \(P\), with an edge for every collinear triple.

Lemma 2.1 [a]. \(H(P)\) is linear: two distinct edges meet in at most one vertex.

Proof. If two distinct collinear triples shared two points, their common two points would determine one line containing the union of the triples, which has at least four points. This is forbidden. \(\square\)

Lemma 2.2 [a]. A subset of \(P\) is in general position exactly when it is independent in \(H(P)\). Consequently

Lemma 2.3 [a]. \(g(n+1)\geq g(n)\).

Proof. Delete any point from an admissible \((n+1)\)-point set and apply the definition of \(g(n)\) to the remaining \(n\) points. \(\square\)

The subtle part of (2) is real representability. At eight vertices, the minimum independence number among abstract linear triple systems differs from the minimum among systems realizable by real points. That difference drives the finite result below.

3. Main finite result

Theorem 3.1 [d+a, computer-assisted finite classification].

The only nontrivial computer-assisted lower-bound step is the transparent eight-vertex isomorphism enumeration in Section 5.2. The upper witnesses also use exhaustive subset checks. All coordinates are rational and checked with exact arithmetic; the real nonrepresentability obstruction is the elementary quadratic calculation in Section 5.3.

| \(n\) | \(g(n)\) | lower-bound reason | exact upper witness | |---:|---:|---|---| | 1 | 1 | definition [a] | one point [a] | | 2 | 2 | every pair is independent [a] | two points [a] | | 3 | 2 | every pair is independent [a] | three collinear points [a] | | 4 | 3 | linearity [a] | one collinear triple plus one point [a] | | 5 | 4 | Section 4 [a] | nested rational configuration [d] | | 6 | 4 | Section 4 [a] | nested rational configuration [d] | | 7 | 4 | Section 4 [a] | non-Fano rational configuration [d] | | 8 | 5 | Sections 5.1--5.3 [d+a] | rational configuration [d] | | 9 | 5 | monotonicity from \(n=8\) [a+d] | rational configuration [d] |

4. Elementary lower bounds through seven points

Let \(H\) be a linear 3-graph on \(n\) vertices.

Lemma 4.1 [a]. A vertex has degree at most \(\lfloor(n-1)/2\rfloor\), since the pairs of other vertices used by edges through it are disjoint. Hence

Lemma 4.2 [a]. Three distinct edges of a linear 3-graph have union of size at least six.

Proof. Inclusion--exclusion gives

If there is no common vertex, the right side is at least \(9-3=6\). If all three share a vertex, it is at least \(9-3+1=7\). \(\square\)

For \(n=5\), Lemma 4.2 implies \(|E(H)|\leq2\). If \(\alpha(H)\leq3\), all five 4-subsets would have to contain an edge, but each edge is contained in only two 4-subsets. Two edges cover at most four of them, a contradiction.

For \(n=6\), (4) gives at most four edges. Each edge is contained in three 4-subsets, so at most \(12<\binom64=15\) 4-subsets can contain edges. Thus \(\alpha(H)\geq4\).

For \(n=7\), (4) gives at most seven edges. Each lies in four 4-subsets, so at most \(28<\binom74=35\) 4-subsets can contain edges. Again \(\alpha(H)\geq4\).

These prove the lower entries through \(n=7\). The exact search independently rechecks all three nonexistence statements.

5. Why eight points force a non-realizable configuration

5.1 Counting forces an \(8_3\) configuration

Assume for contradiction that a real admissible eight-point set has \(\alpha(H)\leq4\). Then every one of its \(\binom85=56\) five-subsets contains an edge.

Let \(m=|E(H)|\), let \(d_v\) be the vertex degrees, and put

By Lemma 4.2, a five-set contains at most two edges. Every edge occurs in \(\binom52=10\) five-sets. Two edges occur in a common five-set exactly when they intersect, in which case their union is that unique five-set. Therefore the exact number \(U\) of five-sets containing an edge is

Every \(d_v\leq3\) and \(\sum_vd_v=3m\). Convexity of \(\binom d2\) gives:

• if \(m\leq5\), then \(U\leq50<56\);
• if \(m=6\), the minimum possible \(I\) is

\(2\binom32+6\binom22=12\), so \(U\leq48\);

• if \(m=7\), the minimum possible \(I\) is

\(5\binom32+3\binom22=18\), so \(U\leq52\).

Thus \(m\geq8\). On the other hand, \(3m=\sum d_v\leq8\cdot3\), so \(m=8\) and every vertex has degree three.

Each vertex is paired in an edge with six of the other seven vertices and has one unique non-neighbour. The four non-edge pairs therefore form a perfect matching. All other \(28-4=24\) pairs occur exactly once among the \(8\cdot3=24\) edge-pairs. Hence \(H\) is a triangle decomposition of \(K_8\) minus a perfect matching.

5.2 Exhaustive isomorphism classification

[d] Relabel the missing matching as

There are 24 required pairs and 32 candidate triples avoiding these four pairs. The verifier recursively chooses the lexicographically first uncovered pair, tries every candidate triangle containing it whose three pairs remain uncovered, and continues until all 24 pairs are covered.

The complete search returns exactly eight labelled decompositions for this fixed matching. A direct loop over all \(8!\) point permutations verifies that all eight are one isomorphism class. In the following labelling that class is

Its independence number is four. This is the Möbius--Kantor \(8_3\) incidence system; the name is not used as an external theorem.

5.3 Elementary obstruction over \(\mathbb R\)

Lemma 5.1 [a]. The incidence system (6) has no realization by distinct points in \(\mathbb{RP}^2\), and hence none in \(\mathbb R^2\).

Proof. Points \(0,1,2,3\) contain no listed triple, so in a realization with exactly the incidences (6) they form a projective frame. Normalize

The incidences \(024\), \(036\), and \(126\) force

for some real \(u\). The incidences \(145\) and \(235\) then force

while \(017\) and \(347\) force

The remaining incidence \(567\) requires

Equivalently \(u^2-u+1=0\), whose discriminant is \(-3\). There is no real \(u\). \(\square\)

Combining Sections 5.1--5.3 proves \(g(8)\geq5\). The explicit eight-point witness below has independence number five, so \(g(8)=5\). Monotonicity immediately gives \(g(9)\geq5\).

6. Exact rational upper-bound configurations

6.1 A nested family through eight points

Let

The exact collinear triples on these seven points are

The verifier uses the following nested subsets:

| \(n\) | point indices/addition | exact \(\alpha\) | |---:|---|---:| | 1 | \(0\) | 1 | | 2 | \(0,1\) | 2 | | 3 | \(0,1,3\) | 2 | | 4 | \(0,1,2,3\) | 3 | | 5 | \(0,1,2,3,4\) | 4 | | 6 | \(0,1,2,3,4,5\) | 4 | | 7 | \(0,1,2,3,4,5,6\) | 4 | | 8 | all seven plus \((2,3)\) | 5 |

[d] Fraction arithmetic over all triples verifies (9), verifies that \((2,3)\) creates no new collinear triple, rejects every collinear 4-subset, and checks all \(2^n\) subsets for the displayed independence numbers.

6.2 A nine-point configuration with independence number five

Take

[d] Exact determinant enumeration finds precisely

as the collinear triples. No four are collinear. Exhaustion of all \(2^9=512\) subsets gives \(\alpha=5\). Thus \(g(9)\leq5\), which together with monotonicity and \(g(8)=5\) proves the last entry of (3).

7. Standalone from-scratch verification

The complete verifier is erdos589_wavew045_reverify.py. It uses only the Python standard library and contains no solver calls or stored certificates.

Run from the repository root:

python runs/erdos589_wavew045_reverify.py

It independently performs:

1. exact Fraction determinant tests for every explicit configuration;
2. brute-force independence-number calculations;
3. a direct recursive nonexistence search for linear triple systems with

too-small independence number on \(n\leq7\);

1. the complete \(K_8\) minus a matching triangle-decomposition search;
2. all-\(8!\)-permutations isomorphism checks; and
3. polynomial-arithmetic recomputation of determinant (7) and its

discriminant; and

1. an explicit abstract ten-vertex linear triple system with independence

number five.

The run completed in 0.18 seconds on this VM and ended with:

fixed missing matching: 8 labelled exact decompositions; all 8 are
isomorphic to Möbius--Kantor
final determinant = -u^2+u-1; equivalently u^2-u+1=0 has discriminant -3
explicit linear 3-graph: 10 vertices, 12 edges, alpha=5
ALL CHECKS PASSED
Exact table g(1..9) = 1,2,2,3,4,4,4,5,5

8. What remains and why the standard machinery stalls

The exact table does not close the asymptotic problem.

[d: source-derived obstruction] Roche-Newton's 2026 ambient line family is

It has \(r\) parallel classes of size \(r^7\). To dualise without creating four collinear points, one may retain at most three lines from each parallel class, leaving at most \(3r\) lines. But that paper's supersaturation lemma only starts for subfamilies of size at least \(8r^7\). Thus simple trimming destroys the scale on which its container argument operates.

[c: precise missing lemma] A \(4/5\)-type improvement for #589 along that route would need a parallel-free replacement family that simultaneously has:

1. at most three lines in every parallel class and at most three through

every finite point after the random deletion step;

1. the same strong triple-concurrency supersaturation in every large

subfamily; and

1. few enough quadruple concurrencies for deletion to preserve the family

size.

No such replacement is supplied by the paper or found in the search.

[c: second precise wall] The same 2026 preprint claims that the Balogh--Solymosi three-dimensional-grid supersaturation exponent is optimal up to logarithmic factors. If correct, merely sharpening that one lemma cannot improve the \(5/6\) exponent; a different ambient geometry or a new structural input is required.

For the finite problem, \(n=10\) is the next genuine representability barrier. [d] For example, the verifier checks that the 12 triples

form a linear triple system on ten vertices with independence number five. One must classify which such incidence patterns are realizable over \(\mathbb R\). An abstract combinatorial witness alone cannot decide this, just as the abstract eight-vertex witness was invalid over \(\mathbb R\).

PARTIAL: Exact computer-assisted determination \(g(1),\ldots,g(9)=1,2,2,3,4,4,4,5,5\), with rational witnesses and a real nonrepresentability proof at \(n=8\); the verified asymptotic gap \(\Omega(\sqrt{n\log n})\) to \(n^{5/6+o(1)}\) remains open.