Erdős Problem #831

Erdős Problem 831 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/831.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT

Let $P$ be a set of $n$ points in $\mathbb{R}^2$ such that (a) no three points of $P$ are collinear, and (b) no four points of $P$ are concyclic. For each 3-element subset $\{A,B,C\}\subset P$, let $R(A,B,C)>0$ be the circumradius of the unique circle passing through $A,B,C$. Let \[ \mathcal{R}(P)=\{R(A,B,C): \{A,B,C\}\subset P\} \] be the set of distinct radii realized by triangles from $P$. Define \[ h(n)=\min_{P\subset\mathbb{R}^2:\ |P|=n,\ P\ \text{satisfies (a),(b)}} |\mathcal{R}(P)|. \] The problem asks for estimates/asymptotics of $h(n)$.

QUICK LITERATURE/CONTEXT CHECK

No quantitative bounds are stated in the problem text beyond the definition. We therefore treat this as a purely geometric extremal question about the number of distinct circumradii determined by $n$ points in general position.

ATTACK PLAN

Proof track: $1$ Prove general lower bounds on $|\mathcal{R}(P)|$ that hold for every admissible $P$. $2$ Seek constructions with few distinct radii to upper bound $h(n)$.

Disproof track: Not applicable (this is an estimation problem, not a yes/no statement).

WORK

Lemma 1 (pair-based lower bound). For every admissible point set $P$ of size $n\ge 3$, one has \[ |\mathcal{R}(P)|\ge \left\lceil\frac{n-2}{2}\right\rceil. \] In particular, $h(n)\ge \lceil (n-2)/2\rceil$.

Proof. Fix two distinct points $A,B\in P$. For each $C\in P\setminus\{A,B\}$, let $R_C:=R(A,B,C)$ be the circumradius of triangle $ABC$. We show that any value $r>0$ can occur among the multiset $\{R_C: C\ne A,B\}$ at most twice.

Fix $r>0$. A circle of radius $r$ passing through $A$ and $B$ must have its center at distance $r$ from both $A$ and $B$. Thus its center lies in the intersection of the two circles of radius $r$ centered at $A$ and at $B$. Two circles in the plane intersect in at most two points, hence there are at most two distinct circles of radius $r$ that pass through both $A$ and $B$. Geometrically, if there are two, their centers lie on opposite sides of the line $AB$.

Now suppose $C_1,C_2\in P\setminus\{A,B\}$ satisfy $R_{C_1}=R_{C_2}=r$. Then $A,B,C_1$ lie on some circle of radius $r$ through $A,B$, and likewise $A,B,C_2$ lie on some circle of radius $r$ through $A,B$. If $C_1$ and $C_2$ lie on the same side of line $AB$, then both must lie on the same one of the at most two circles of radius $r$ through $A,B$, so $A,B,C_1,C_2$ are concyclic. This contradicts the assumption (b) that no four points are concyclic. Therefore, for a fixed $r$, there is at most one $C$ on each side of $AB$ with $R_C=r$, so at most two points $C$ total.

Since there are $n-2$ points $C$ and each radius value appears at most twice, the number of distinct values among the $R_C$ is at least $\lceil (n-2)/2\rceil$. Because these radii are a subset of $\mathcal{R}(P)$, we obtain $|\mathcal{R}(P)|\ge \lceil (n-2)/2\rceil$. $\square$

Lemma 2 (radius-multiplicity bound). Fix $r>0$. For any admissible point set $P$ of size $n$, the number of triangles $\{A,B,C\}\subset P$ with circumradius exactly $r$ is at most $\frac{n(n-1)}{3}$. Consequently $|\mathcal{R}(P)|\ge \lceil (n-2)/2\rceil$.

Proof. Let $T_r$ be the set of unordered triangles $\{A,B,C\}\subset P$ whose circumradius equals $r$. Fix an unordered pair of points $\{A,B\}\subset P$. As in Lemma 1, there are at most two circles of radius $r$ passing through $A$ and $B$. Each such circle can contain at most one additional point $C\in P\setminus\{A,B\}$, because if it contained two distinct points $C_1,C_2$ then $A,B,C_1,C_2$ would be four concyclic points, forbidden by (b). Therefore, the pair $\{A,B\}$ is contained in at most $2$ triangles from $T_r$.

Double-count incidences between pairs and triangles: Each triangle in $T_r$ contains exactly $3$ unordered pairs. Hence \[ 3|T_r| = \sum_{\{A,B\}\subset P} \#\{\text{triangles in }T_r\text{ containing }\{A,B\}\} \le 2\binom{n}{2}. \] Thus $|T_r|\le \frac{2}{3}\binom{n}{2}=\frac{n(n-1)}{3}$.

If $m=|\mathcal{R}(P)|$ is the number of distinct radii, then the total number of triangles satisfies \[ \binom{n}{3} \le \sum_{\rho\in\mathcal{R}(P)} |T_{\rho}| \le m\cdot \frac{n(n-1)}{3}. \] Rearranging gives $m\ge \frac{3\binom{n}{3}}{n(n-1)}=\frac{n-2}{2}$, hence $m\ge \lceil (n-2)/2\rceil$. $\square$

Fast reality check (computation; exact arithmetic on integer points). For random integer point sets satisfying (a),(b), we computed the number of distinct circumradii among all $\binom{n}{3}$ triangles using the exact rational formula for $R^2$. One sample output was: \[ \begin{array}{r|r|r} n & \binom{n}{3} & |\mathcal{R}(P)| \\\hline 3 & 1 & 1\\ 4 & 4 & 4\\ 5 & 10 & 10\\ 6 & 20 & 20\\ 7 & 35 & 32\\ 8 & 56 & 48 \end{array} \] In each case the lower bound $\lceil (n-2)/2\rceil$ was satisfied. These computations do not estimate $h(n)$ (which is a minimum over configurations) but serve as a sanity check for Lemmas 1--2.

VERIFICATION

$1$ Both lemmas rely crucially on the geometric fact: for fixed $A,B$ and fixed radius $r$, there are at most two circles of radius $r$ through $A,B$. This follows because possible centers are intersections of two radius-$r$ circles. $2$ The use of the “no four concyclic” hypothesis is explicit: it ensures a fixed circle contains at most three points, hence at most one triangle for each fixed pair and fixed circle. $3$ Quantifiers: Lemma 1 gives a bound for every admissible $P$, hence it bounds $h(n)$ from below.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved the linear lower bound \[h(n)\ge \left\lceil\frac{n-2}{2}\right\rceil\] for all $n\ge 3$ (Lemmas 1--2).

(ii) First gap (crisp statement). Find a matching upper bound up to constants: does there exist a construction of admissible $P$ with $|\mathcal{R}(P)|\le Cn$ for an absolute constant $C$? Equivalently, is $h(n)=\Theta(n)$?

(iii) Top 3 next moves. 1. Construction attempt: explicitly build point sets where many triangles share circumradius values, while maintaining “no four concyclic”; try to achieve $|\mathcal{R}(P)|=O(n)$. 2. Improve the lower bound: prove $h(n)\ge c n$ with $c>1/2$ (or superlinear) using incidence geometry or additive combinatorics on the circumradius formula $R=\frac{abc}{4\Delta}$. 3. Computational search for small $n$: restrict to small integer grids, enumerate admissible point sets, and compute the exact minimum of $|\mathcal{R}(P)|$ for $n\le 8$ to guess the true growth.

(iv) Minimal counterexample structure. A near-extremal configuration (achieving $|\mathcal{R}(P)|\approx (n-2)/2$) would require that for some fixed pair $A,B$, almost every radius value among triangles $ABC$ is used exactly twice (once on each side of $AB$), and that triangles not involving $A,B$ introduce very few new radii; this suggests a highly constrained, symmetric arrangement.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Let $P$ be a set of $n$ points in $\mathbb{R}^2$ such that (a) no three points of $P$ are collinear, and (b) no four points of $P$ are concyclic. For each 3-element subset $\{A,B,C\}\subset P$, let $R(A,B,C)>0$ be the circumradius of the unique circle passing through $A,B,C$. Let \[ \mathcal{R}(P)=\{R(A,B,C): \{A,B,C\}\subset P\} \] be the set of distinct radii realized by triangles from $P$. Define \[ h(n)=\min_{P\subset\mathbb{R}^2:\ |P|=n,\ P\ \text{satisfies (a),(b)}} |\mathcal{R}(P)|. \] The problem asks for estimates/asymptotics of $h(n)$.

QUICK LITERATURE/CONTEXT CHECK

No quantitative bounds are stated in the problem text beyond the definition. We therefore treat this as a purely geometric extremal question about the number of distinct circumradii determined by $n$ points in general position.

ATTACK PLAN

Proof track: $1$ Prove general lower bounds on $|\mathcal{R}(P)|$ that hold for every admissible $P$. $2$ Seek constructions with few distinct radii to upper bound $h(n)$.

Disproof track: Not applicable (this is an estimation problem, not a yes/no statement).

WORK

Lemma 1 (pair-based lower bound). For every admissible point set $P$ of size $n\ge 3$, one has \[ |\mathcal{R}(P)|\ge \left\lceil\frac{n-2}{2}\right\rceil. \] In particular, $h(n)\ge \lceil (n-2)/2\rceil$.

Proof. Fix two distinct points $A,B\in P$. For each $C\in P\setminus\{A,B\}$, let $R_C:=R(A,B,C)$ be the circumradius of triangle $ABC$. We show that any value $r>0$ can occur among the multiset $\{R_C: C\ne A,B\}$ at most twice.

Fix $r>0$. A circle of radius $r$ passing through $A$ and $B$ must have its center at distance $r$ from both $A$ and $B$. Thus its center lies in the intersection of the two circles of radius $r$ centered at $A$ and at $B$. Two circles in the plane intersect in at most two points, hence there are at most two distinct circles of radius $r$ that pass through both $A$ and $B$. Geometrically, if there are two, their centers lie on opposite sides of the line $AB$.

Now suppose $C_1,C_2\in P\setminus\{A,B\}$ satisfy $R_{C_1}=R_{C_2}=r$. Then $A,B,C_1$ lie on some circle of radius $r$ through $A,B$, and likewise $A,B,C_2$ lie on some circle of radius $r$ through $A,B$. If $C_1$ and $C_2$ lie on the same side of line $AB$, then both must lie on the same one of the at most two circles of radius $r$ through $A,B$, so $A,B,C_1,C_2$ are concyclic. This contradicts the assumption (b) that no four points are concyclic. Therefore, for a fixed $r$, there is at most one $C$ on each side of $AB$ with $R_C=r$, so at most two points $C$ total.

Since there are $n-2$ points $C$ and each radius value appears at most twice, the number of distinct values among the $R_C$ is at least $\lceil (n-2)/2\rceil$. Because these radii are a subset of $\mathcal{R}(P)$, we obtain $|\mathcal{R}(P)|\ge \lceil (n-2)/2\rceil$. $\square$

Lemma 2 (radius-multiplicity bound). Fix $r>0$. For any admissible point set $P$ of size $n$, the number of triangles $\{A,B,C\}\subset P$ with circumradius exactly $r$ is at most $\frac{n(n-1)}{3}$. Consequently $|\mathcal{R}(P)|\ge \lceil (n-2)/2\rceil$.

Proof. Let $T_r$ be the set of unordered triangles $\{A,B,C\}\subset P$ whose circumradius equals $r$. Fix an unordered pair of points $\{A,B\}\subset P$. As in Lemma 1, there are at most two circles of radius $r$ passing through $A$ and $B$. Each such circle can contain at most one additional point $C\in P\setminus\{A,B\}$, because if it contained two distinct points $C_1,C_2$ then $A,B,C_1,C_2$ would be four concyclic points, forbidden by (b). Therefore, the pair $\{A,B\}$ is contained in at most $2$ triangles from $T_r$.

Double-count incidences between pairs and triangles: Each triangle in $T_r$ contains exactly $3$ unordered pairs. Hence \[ 3|T_r| = \sum_{\{A,B\}\subset P} \#\{\text{triangles in }T_r\text{ containing }\{A,B\}\} \le 2\binom{n}{2}. \] Thus $|T_r|\le \frac{2}{3}\binom{n}{2}=\frac{n(n-1)}{3}$.

If $m=|\mathcal{R}(P)|$ is the number of distinct radii, then the total number of triangles satisfies \[ \binom{n}{3} \le \sum_{\rho\in\mathcal{R}(P)} |T_{\rho}| \le m\cdot \frac{n(n-1)}{3}. \] Rearranging gives $m\ge \frac{3\binom{n}{3}}{n(n-1)}=\frac{n-2}{2}$, hence $m\ge \lceil (n-2)/2\rceil$. $\square$

Fast reality check (computation; exact arithmetic on integer points). For random integer point sets satisfying (a),(b), we computed the number of distinct circumradii among all $\binom{n}{3}$ triangles using the exact rational formula for $R^2$. One sample output was: \[ \begin{array}{r|r|r} n & \binom{n}{3} & |\mathcal{R}(P)| \\\hline 3 & 1 & 1\\ 4 & 4 & 4\\ 5 & 10 & 10\\ 6 & 20 & 20\\ 7 & 35 & 32\\ 8 & 56 & 48 \end{array} \] In each case the lower bound $\lceil (n-2)/2\rceil$ was satisfied. These computations do not estimate $h(n)$ (which is a minimum over configurations) but serve as a sanity check for Lemmas 1--2.

VERIFICATION

$1$ Both lemmas rely crucially on the geometric fact: for fixed $A,B$ and fixed radius $r$, there are at most two circles of radius $r$ through $A,B$. This follows because possible centers are intersections of two radius-$r$ circles. $2$ The use of the “no four concyclic” hypothesis is explicit: it ensures a fixed circle contains at most three points, hence at most one triangle for each fixed pair and fixed circle. $3$ Quantifiers: Lemma 1 gives a bound for every admissible $P$, hence it bounds $h(n)$ from below.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved the linear lower bound \[h(n)\ge \left\lceil\frac{n-2}{2}\right\rceil\] for all $n\ge 3$ (Lemmas 1--2).

(ii) First gap (crisp statement). Find a matching upper bound up to constants: does there exist a construction of admissible $P$ with $|\mathcal{R}(P)|\le Cn$ for an absolute constant $C$? Equivalently, is $h(n)=\Theta(n)$?

(iii) Top 3 next moves. 1. Construction attempt: explicitly build point sets where many triangles share circumradius values, while maintaining “no four concyclic”; try to achieve $|\mathcal{R}(P)|=O(n)$. 2. Improve the lower bound: prove $h(n)\ge c n$ with $c>1/2$ (or superlinear) using incidence geometry or additive combinatorics on the circumradius formula $R=\frac{abc}{4\Delta}$. 3. Computational search for small $n$: restrict to small integer grids, enumerate admissible point sets, and compute the exact minimum of $|\mathcal{R}(P)|$ for $n\le 8$ to guess the true growth.

(iv) Minimal counterexample structure. A near-extremal configuration (achieving $|\mathcal{R}(P)|\approx (n-2)/2$) would require that for some fixed pair $A,B$, almost every radius value among triangles $ABC$ is used exactly twice (once on each side of $AB$), and that triangles not involving $A,B$ introduce very few new radii; this suggests a highly constrained, symmetric arrangement.