Erdős problem #506 — wave w041

Date: 2026-07-31 UTC

Claim labels

• (a) elementary-rigorous: proved here from explicit algebra, counting, or

elementary Euclidean/projective geometry.

• (b) rigorous-modulo-named-theorem/source: a faithful statement from the

live page or a named primary source, or a deduction conditional on it.

• (c) plausible/structural-unverified: a search boundary, novelty statement,

or cost estimate, not a theorem.

• (d) computational-only: established by the exact checker but not used as

the sole proof of a theorem.

Step 0: mandatory live-page audit

(b) I fetched the rendered live page and its discussion thread through the Bright Data browser path on 2026-07-31. The page badge is DECIDABLE. It reports 0 claimed proofs, “Currently working on this problem: None,” “Interested in collaborating: None,” and two comments. Thus none of the mandatory stop conditions applies. The page says it was last edited on 2026-02-01.

The live statement, verbatim, is:

What is the minimum number of circles determined by any \(n\) points in \(\mathbb{R}^2\), not all on a circle?

(b) The same page says that a nondegeneracy condition is clearly missing, probably either “not all on a line” or the stronger “no three on a line.” Under the former convention, it reports Elliott’s claimed bound \(\binom{n-1}{2}\) for \(n>393\), and the Purdy–Smith correction

It says this is sharp, using \(n-1\) points on a circle and one point off it. It also says the problem remains open for small \(n\), and records Segre’s projected-cube counterexample to Elliott’s uncorrected expression at \(n=8\).

(b) The newest comment, by Yuriy Peysakhov on 2026-06-11, gives

and reports exactly 18 circles: ten 4-point circles and eight 3-point circles, with eight collinear triples. The older comment, by Lewys on 2026-01-30, explains the Purdy–Smith correction and is marked by the site as incorporated into the description. The site expressly says comments are not verified.

(a,d) The standalone checker independently verifies the entire \(S_8\) count: its two 4-point lines contain eight triples, its ten 4-point circles contain forty, and its eight 3-point circles contain eight; \(8+40+8=56\). Thus the comment’s upper bound \(f(8)\leq18\) does not depend here on trusting the comment.

Live sources:

• problem page
• discussion thread
• text/LaTeX endpoint

The ambiguity is substantive

(a) Read literally, the answer is zero for every \(n\geq3\): take \(n\) distinct collinear points. No proper Euclidean circle contains three collinear points, so the set is not all on a circle and determines no circle. This is not the intended problem, but it is the exact answer to the displayed sentence.

(a) For the rest of this report I use the convention actually used by Elliott and the later sources:

Points are distinct. There is no admissible set for \(n=3\); the first case is \(n=4\). The stronger “no three collinear” interpretation is a different problem, and the constructions below do not address it.

Primary-source check

(b) I obtained and text-checked the following primary sources, including the page ranges cited below.

1. Erdős, Some Unsolved Problems (1961), pp. 221–254.

Page 245 asks exactly for the minimum number of circles from \(n\) points “not all on a circle”; it does not add the needed line exclusion.

1. [Elliott, On the number of circles determined by \(n\) points (1967),

DOI 10.1007/BF02020972](https://doi.org/10.1007/BF02020972). Theorem 2 assumes the points are not all on a circle or line and states the uncorrected \(\binom{n-1}{2}\) bound for \(n>393\). The proof’s final \(n-1\)-concyclic case is where the missing collinear-pair subtraction matters. I checked the paper in the Hungarian Academy volume scan, pp. 181–188.

1. [Jucovič, Beitrag zur kombinatorischen Inzidenzgeometrie (1967),

DOI 10.1007/BF02280283](https://doi.org/10.1007/BF02280283). Satz 3 and Lemma 2 give the small-case lower bound

\[ f(n)\geq 8+2k+\frac{5(n-k-6)}3 \quad(n\geq6,\ k\in\{0,1,2\},\ n\equiv k\pmod3), \]

with equality possible at \(n=6\). Remark 3 states \(f(4)=3\) and \(f(5)=5\). This gives \(f(6)=8\), \(f(7)\geq10\), and \(f(8)\geq12\). The paper is pp. 255–259 of the same Academy volume scan.

1. [Bálintová–Bálint, *On the number of circles determined by \(n\) points in

the Euclidean plane* (1994), DOI 10.1007/BF01874133](https://doi.org/10.1007/BF01874133). Its Theorem 2.4 gives, for \(n\geq6\), \[ f(n)\geq\frac{15n(n-1)+1678}{266}, \] interpreted integrally. It also restates the corrected-shaped large-\(n\) estimate. I checked pp. 283–289 in the Academy volume scan.

1. [Purdy–Smith, Lines, Circles, Planes and Spheres,

arXiv:0907.0724](https://arxiv.org/abs/0907.0724), §2.1, pp. 7–8, explicitly identifies Elliott’s error, gives \(G(n)\), and says Elliott’s proof can be modified with the same threshold \(n\geq394\).

1. [Lin–Makhul–Mojarrad–Schicho–Swanepoel–de Zeeuw, *On Sets Defining Few

Ordinary Circles* (2018), DOI 10.1007/s00454-017-9885-8](https://doi.org/10.1007/s00454-017-9885-8) determines a different parameter: circles containing exactly three points. It does not determine the total number of distinct circles in problem #506.

(c) Searches by exact title, problem wording, citation chains, DOI, and the small values \(f(7)\), “seven points,” and “11 circles” found no primary source giving the value below. This is a report of the search, not a claim of literature novelty.

(d) The checker’s optional --online mode queried Crossref for all five DOIs above and rechecked the Erdős Problems text endpoint and the Hungarian Academy record. All checks passed on 2026-07-31.

Verified result

Under convention (E), this run obtains:

| \(n\) | verified state | label | |---:|---:|:---| | 4 | \(f(4)=3\) | (a), classical | | 5 | \(f(5)=5\) | (a), classical | | 6 | \(f(6)=8\) | (a), Jucovič already proved it | | 7 | \(f(7)=11\) | (a), proved below | | 8 | \(12\leq f(8)\leq18\) | lower (b), upper (a) | | \(n>393\) | \(f(n)=G(n)\) | (b), Elliott + Purdy–Smith |

The value \(f(7)=11\) improves the Jucovič lower bound 10 and the generic \(n-1\)-concyclic upper bound \(G(7)=13\).

An exact seven-point construction

(a) Let

Its six lines containing three points are:

| line | incident indices | |---|---| | \(x-2y-7=0\) | \(1,5,7\) | | \(x-y-1=0\) | \(1,4,6\) | | \(x+y-1=0\) | \(3,6,7\) | | \(x+3y+3=0\) | \(2,4,7\) | | \(2x+y+1=0\) | \(3,4,5\) | | \(3x-y+9=0\) | \(1,2,3\) |

Its eleven determined circles are:

| circle equation | incident indices | |---|---| | \(x^2+y^2-6x-6y-7=0\) | \(3,4,7\) | | \(x^2+y^2-3x+3y+2=0\) | \(4,5,6,7\) | | \(x^2+y^2-x-y-12=0\) | \(2,3,5,7\) | | \(x^2+y^2+12y+11=0\) | \(1,4,7\) | | \(x^2+y^2+2x-2y-3=0\) | \(2,3,4,6\) | | \(x^2+y^2+2x+3y-3=0\) | \(2,5,6\) | | \(x^2+y^2+2x+8y-3=0\) | \(1,2,6,7\) | | \(x^2+y^2+4x+4y-17=0\) | \(1,3,7\) | | \(x^2+y^2+5x+7y+6=0\) | \(1,2,4,5\) | | \(x^2+y^2+7x+3y-8=0\) | \(1,3,5,6\) | | \(x^2+y^2+10x+2y+1=0\) | \(1,3,4\) |

(a) There are six 3-point lines, six 4-point circles, and five 3-point circles. Their triple sets are disjoint, and

Thus every triple is accounted for, and the list of eleven circles is complete. In fact, the six 4-point circle sets are precisely the complements of the six 3-point line sets. Hence \(f(7)\leq11\).

(d) The checker recomputes this without using the displayed lists. For every triple it takes the alternating \(3\times3\) minors of

primitive-normalizes the resulting integer circle equation, and independently cross-checks it by solving for the rational circumcenter and squared radius.

Lower bound for seven points

All claims in this section are (a) elementary-rigorous.

1. A large line already gives at least 12 circles

Suppose a line \(\ell\) contains \(r\geq4\) of the seven points; let \(s=7-r\) points be off \(\ell\). For every off-line point \(q\) and every pair \(\{a,b\}\subset\ell\), the triple \(q,a,b\) gives a circle. The \(\binom r2\) circles obtained from a fixed \(q\) are distinct, since their intersection with \(\ell\) is the defining pair.

For two off-line points \(q,q'\), a circle can be counted in both families only for the same pair \(\{a,b\}\). Such pairs form a matching among the \(r\) on-line points: two pairs sharing \(a\) would give two circles through \(q,q',a\), hence the same circle, which would then contain three collinear points. Therefore there are at most \(\lfloor r/2\rfloor\) coincidences for each pair \(q,q'\). Bonferroni’s union bound gives

For \(r=4,5,6\), these values are respectively \(12,18,15\).

2. A large circle already gives at least 13 circles

Suppose a circle \(\Gamma\) contains \(r\geq5\) points and \(s=7-r\) lie off it. For a fixed outside point \(q\), at most \(\lfloor r/2\rfloor\) pairs on \(\Gamma\) are collinear with \(q\), since such pairs are disjoint secants through \(q\). Every other pair gives a distinct circle with \(q\). As above, two outside-point families have at most \(\lfloor r/2\rfloor\) coincidences. Including \(\Gamma\), the count is at least

For \(r=5,6\), this is respectively \(15,13\).

It remains to consider configurations with no four collinear and no five concyclic.

3. The six-point obstruction

Lemma. Six real planar points cannot simultaneously have:

1. three 4-point circles whose omitted 2-point sets partition the six points;
2. four 3-point lines, each choosing one point from each omitted pair.

Proof. Two of the four 3-point lines share at most one point. A point lies on at most two of the four lines, because \(d\) such lines through it require \(2d\) distinct other points. The twelve line-point incidences therefore force every point to lie on exactly two lines. Thus the six points are the six vertices of a complete quadrilateral formed by the four lines. The three omitted pairs are its three pairs of opposite vertices.

Any two of the three circles share the opposite pair omitted by the third. Consequently, their three pairwise radical axes are exactly the three lines joining opposite vertices. Three circles’ radical axes are concurrent in the real projective completion: after normalizing the circle equations to have quadratic part \(x^2+y^2\), the three difference equations telescope.

But the three diagonal lines of a real complete quadrilateral are not concurrent. Dually, normalize four points in general position to

Their three diagonal points are \((1,1,0),(1,0,1),(0,1,1)\), whose determinant is \(-2\neq0\); hence they are not collinear. This dual contradiction proves the lemma. \(\square\)

4. At most six 3-point lines

Let \(L\) be the number of 3-point lines. Each consumes three distinct pairs, so \(L\leq7\). Equality would make the seven line triples a Steiner triple system on seven points, uniquely the Fano system up to relabeling. In the labeling

the four points \(1,2,4,7\) form a complete quadrangle whose diagonal points are \(3,5,6\); the Fano incidences demand that those three diagonal points be collinear. The determinant calculation in the preceding lemma says this is impossible over \(\mathbb R\). Hence \(L\leq6\).

5. At most six 4-point circles

Let \(c_4\) be the number of 4-point circles. Two distinct such circles share at most two of the seven points. Their 3-point complements consequently share at most one point, so their three internal pairs are disjoint across complements. Pair counting gives \(3c_4\leq\binom72=21\), hence \(c_4\leq7\).

If \(c_4=7\), the seven complementary triples form the Fano triple system: every pair occurs exactly once and every point occurs in three complements. Invert about any point \(p\). Four of the 4-circles contain \(p\) and become four 3-point lines. The other three stay 4-point circles; their omitted pairs partition the remaining six points. Each new 3-point line is a transversal of those pairs, since a line and circle cannot share three points. This is exactly the forbidden six-point pattern above. Therefore \(c_4\leq6\).

6. Triple count

Let \(c_3\) count the 3-point circles. Every triple is either one of the \(L\) collinear triples or lies on its unique circle, so

Writing \(m=c_3+c_4\), we get

Together with construction (1), this proves

The neighboring exact cases

(a) For \(n=4\), three collinear points plus one off their line determine exactly three circles. If there is no collinear triple and the four points are not concyclic, their four triples give four distinct circles. Thus \(f(4)=3\).

(a) For \(n=5\), take four points on a circle and put the fifth point at the intersection of two disjoint chords. The base circle and the four noncollinear fifth-point/pair triples give five circles. Conversely, four collinear points give six circles; four concyclic points give at least \(1+\binom42-2=5\); and if neither occurs, at most three of the ten triples are collinear, giving at least seven circles. Thus \(f(5)=5\).

(a) Deleting \(P_1\) from (1) leaves six points with exactly eight circles: three 4-point and five 3-point circles. Here is the matching lower bound in full. Five points on a line or circle force at least 10 or 9 circles, and four on a line force at least 10 by the matching argument above. In the remaining case, let \(L\) count 3-point lines and \(c_4\) count 4-point circles. Then \(L\leq4\): pair counting gives \(L\leq5\), while equality would require each point’s five partners to split into pairs on 3-point lines, which is impossible. Also \(c_4\leq3\), because the 2-point complements of distinct 4-circles are disjoint. If there were at most seven circles, then

Equality everywhere would give three 4-circles with complementary pairs partitioning the set and four transversal 3-lines—the forbidden six-point pattern. Hence \(f(6)=8\), agreeing with Jucovič.

The corrected extremal construction

(a) The page’s general construction can be checked directly. Put \(n-1\) points on a circle \(\Gamma\), paired along \(\lfloor(n-1)/2\rfloor\) secants through an off-circle point \(q\), with one unpaired point if necessary. Of the \(\binom{n-1}{2}\) pairs on \(\Gamma\), exactly \(\lfloor(n-1)/2\rfloor\) give collinear triples with \(q\). Every other pair gives a different circle, and \(\Gamma\) contributes one. The count is exactly \(G(n)\). This proves the upper bound \(f(n)\leq G(n)\) for every \(n\geq4\); Elliott/Purdy–Smith prove equality for \(n>393\).

Exact reduction for \(n=8\), and what remains

(a) For an arbitrary \(n\)-point set, let

and let \(c_j\) be the number of circles containing exactly \(j\) points. Partitioning triples gives the exact identity

Therefore proving \(f(8)\geq18\) is equivalent to proving the realizability inequality

for every admissible eight-point set. The live-page cube configuration attains equality in (3): its two 4-point lines contribute \(8\), and its ten 4-point circles contribute \(10(4-1)=30\).

(a) Thus the exact present small-case state established here is

where the lower bound is Jucovič’s named theorem and the upper bound is an exact coordinate certificate. The missing lemma is precisely (3), not merely a better count of line blocks or circle blocks separately: non-realizable Fano incidence systems already show why independent packing bounds lose geometric information.

(c) A computational route to (3) would first SAT-enumerate labeled line/circle block systems on eight vertices satisfying exact triple coverage, then quotient by isomorphism, and finally certify each survivor’s real realizability or non-realizability using determinant equations and strict non-incidence inequalities. The combinatorial layer should be below one core-hour. The exact real-algebraic layer is the expensive part; at a plausible \(10^3\)–\(10^4\) survivors and \(0.01\)–\(1\) core-hour per survivor, the campaign is roughly \(10\)–\(10^4\) core-hours (about USD 0.50–500 at USD 0.05/core-hour). This estimate is deliberately broad and was not run.

Reproduction

The standalone checker is runs/erdos506_wavew041_reverify.py.

Run:

python runs/erdos506_wavew041_reverify.py
python runs/erdos506_wavew041_reverify.py --online

The offline run takes under a second on this VM and prints:

S6: circles=8, circle sizes=3^5 4^3, line sizes=2^6 3^3
S7: circles=11, circle sizes=3^5 4^6, line sizes=2^3 3^6
S8 cube projection: circles=18, circle sizes=3^8 4^10, line sizes=2^16 4^2
Incidence reduction: 30 labelled Fano systems checked; each would invert to the forbidden 4-line/3-circle six-point pattern
Large-line bounds: {4: 12, 5: 18, 6: 15}
Large-circle bounds: {5: 15, 6: 13}
Main-regime arithmetic: 35 - 6 - 3*6 = 11
ALL EXACT OFFLINE CHECKS PASSED

PARTIAL: Under Elliott’s intended “not all collinear or concyclic” convention, \(f(7)=11\) is proved with an exact integer construction and a from-scratch lower bound; also \(12\leq f(8)\leq18\), with the exact missing \(n=8\) inequality isolated in (3).