Erdős Problem #827

Erdős Problem 827 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/827

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/827.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/827.tex.

FORMAL RESTATEMENT

Ambiguity note. The phrase "points in general position" is not defined in the excerpt. In planar combinatorial geometry it often means "no three collinear"; sometimes, in circle-related problems, it also includes "no four concyclic". I treat both:

• Literal (minimal) convention: general position means no three points are collinear.
• Stronger convention: no three collinear and no four points lie on a common circle.

Given $k\ge 3$, define $n_k$ to be the smallest integer $N$ (if it exists) such that every set of $N$ points in $\mathbb{R}^2$ in general position contains a subset $S$ of $k$ points with the property:

For all distinct triples $T\subset S$ with $|T|=3$, the circumradius of the circle through $T$ is different for different $T$.

(Each triple is non-collinear under both conventions, so it determines a unique circumcircle and circumradius.)

The problem asks to determine $n_k$.

QUICK LITERATURE/CONTEXT CHECK

The excerpt states: Erdős asked whether $n_k$ exists, claimed an argument giving $n_k\le k+2\binom{k-1}{2}\binom{k-1}{3}$, but this was incorrect; Martinez--Roldán-Pensado gave a corrected argument proving $n_k\ll k^9$.

Below I prove exact $n_3$ and give explicit lower-bound constructions for $n_4$ by counterexamples, using exact computations of circumradii.

ATTACK PLAN

• Small $k$ exact values: Determine $n_3$ directly. For $k=4$, try to decide $n_4$ by explicit counterexamples for $N=4,5$ and then look for a proof for $N=6$ (not achieved here).
• General $k$: Without reproducing the Martinez--Roldán-Pensado argument, I will not claim a full existence proof; I only record the bound stated in the excerpt as context.

WORK

FAST REALITY CHECK (circumradius computation formulas).

For a non-collinear triangle with side lengths $a,b,c$ and area $\Delta$, its circumradius is \[ R = \frac{abc}{4\Delta}. \] For explicit integer-coordinate examples, I compute $R^2$ exactly via \[ R^2 = \frac{a^2 b^2 c^2}{16\Delta^2} = \frac{a^2 b^2 c^2}{4\,\operatorname{Area2}^2}, \] where $\operatorname{Area2}=2\Delta$ is the doubled signed area.

Lemma (Exact value of $n_3$). Under either convention of general position, $n_3=3$.

Proof. We must find the minimal $N$ such that any $N$ points in general position contain $3$ points whose $\binom{3}{3}=1$ triple has "all circumradii distinct".

If $N=3$, any 3 points in general position are non-collinear, hence determine a unique circle with some radius $R$. Since there is only one triple, the set of circumradii has size 1 and is vacuously pairwise distinct. Thus every 3-point set in general position contains a good 3-subset (itself).

If $N<3$, no $k=3$ subset exists at all. Therefore the minimal such $N$ is $3$. $\square$

Lemma (A 4-point counterexample: $n_4>4$). Under the minimal convention (no three collinear), $n_4>4$.

Proof. Take four points on a common circle, e.g. \[ A=(1,0),\;B=(0,1),\;C=(-1,0),\;D=(0,-1). \] No three of these are collinear, so this set is in general position under the minimal convention.

Any triple among $\{A,B,C,D\}$ lies on the same circle $x^2+y^2=1$, so every triangle has circumradius $1$. Therefore, for the only 4-point subset (the full set), the four triples determine circles of the same radius, hence not all radii are distinct. Thus $N=4$ does not guarantee a good 4-subset, so $n_4>4$. $\square$

Lemma (A stronger 5-point counterexample: $n_4\ge 6$ even with no four concyclic). Consider the five points \[ P_1=(-2,-2),\;P_2=(-2,-1),\;P_3=(-1,1),\;P_4=(-1,2),\;P_5=(0,0). \] Then:

1. No three of these points are collinear.
2. No four of these points are concyclic (equivalently: for each 4-subset, not all four triangle circumradii coincide).
3. Every 4-subset of $\{P_1,\dots,P_5\}$ contains two distinct triangles with the same circumradius.

Consequently, $n_4\ge 6$ under either convention of general position.

Proof. Step 1: no three collinear. The set has two points with $x=-2$ ($P_1,P_2$), two points with $x=-1$ ($P_3,P_4$), and one point with $x=0$ ($P_5$), so no vertical line contains three points. A direct check of the remaining potential collinearities can be done by verifying that for each triple $(P_i,P_j,P_k)$ the doubled area \[ \operatorname{Area2}(P_i,P_j,P_k)=(x_j-x_i)(y_k-y_i)-(y_j-y_i)(x_k-x_i) \] is nonzero. In fact, a direct computation gives the 10 doubled areas: \[ \operatorname{Area2}(P_1,P_2,P_3)=-1,\;\operatorname{Area2}(P_1,P_2,P_4)=-1,\;\operatorname{Area2}(P_1,P_2,P_5)=-2,\;\operatorname{Area2}(P_1,P_3,P_4)=1,\;\operatorname{Area2}(P_1,P_3,P_5)=-4,\;\operatorname{Area2}(P_1,P_4,P_5)=-6,\;\operatorname{Area2}(P_2,P_3,P_4)=1,\;\operatorname{Area2}(P_2,P_3,P_5)=-3,\;\operatorname{Area2}(P_2,P_4,P_5)=-5,\;\operatorname{Area2}(P_3,P_4,P_5)=-1. \] None of these is $0$, so no three points are collinear.

Step 2: compute circumradii squared for each 4-subset. For each 4-subset, there are 4 triangles. I list the four values of $R^2$ (as exact rationals) computed via $R^2=\frac{a^2b^2c^2}{4\,\operatorname{Area2}^2}$.

(a) Quadruple $\{P_1,P_2,P_3,P_4\}$: \[ R^2\in\left\{\frac{25}{2},\frac{85}{2},\frac{85}{2},\frac{25}{2}\right\}. \] Thus at least two circumradii coincide (in fact two pairs coincide), and not all four coincide.

(b) Quadruple $\{P_1,P_2,P_3,P_5\}$: \[ R^2\in\left\{\frac{25}{2},\frac{5}{2},\frac{5}{2},\frac{25}{18}\right\}. \] Thus there is a repeated value $5/2$, and not all four coincide.

(c) Quadruple $\{P_1,P_2,P_4,P_5\}$: \[ R^2\in\left\{\frac{85}{2},\frac{5}{2},\frac{85}{18},\frac{5}{2}\right\}. \] Thus there is a repeated value $5/2$, and not all four coincide.

(d) Quadruple $\{P_1,P_3,P_4,P_5\}$: \[ R^2\in\left\{\frac{85}{2},\frac{5}{2},\frac{85}{18},\frac{5}{2}\right\}. \] Again there is a repeated value $5/2$, and not all four coincide.

(e) Quadruple $\{P_2,P_3,P_4,P_5\}$: \[ R^2\in\left\{\frac{25}{2},\frac{25}{18},\frac{5}{2},\frac{5}{2}\right\}. \] Again there is a repeated value $5/2$, and not all four coincide.

In each case, the list of four radii contains a repeat, so no 4-subset has all four circumradii distinct.

Step 3: conclude. Since this 5-point configuration is in general position under either convention (Steps 1 and the "not all equal" part of Step 2), but contains no good 4-subset, it follows that $n_4\ge 6$. $\square$

VERIFICATION

• Lemma (Exact value of $n_3$): The vacuity for $k=3$ is correct because there is exactly one triple.
• Lemma (A 4-point counterexample: $n_4>4$): The 4 points are concyclic and non-collinear in triples, so it is a valid counterexample under the minimal convention. Under the stronger convention (excluding 4 concyclic) this example is not allowed, which is why the 5-point counterexample lemma was given.
• Lemma (A stronger 5-point counterexample: $n_4\ge 6$ even with no four concyclic): The radii-squared lists were computed exactly (rational arithmetic) for each 4-subset; each list contains a duplicate, so each 4-subset fails the distinctness requirement. Also no list is constant, so no 4-subset is concyclic.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. Exact value $n_3=3$; and an explicit 5-point configuration in strong general position with no good 4-subset, implying $n_4\ge 6$.
2. (ii) First gap. Decide whether $n_4=6$ (i.e. prove or disprove that every 6-point set in general position contains a 4-point subset with all four triangle circumradii distinct), and more generally determine $n_k$ for $k\ge 4$.
3. (iii) Top 3 next moves.
   1. Computational search over integer-coordinate point sets with $N=6$ to try to find a counterexample to $n_4\le 6$ (i.e. a 6-point set with no good quadruple), which would show $n_4\ge 7$.
   2. Prove a structural lemma: if in a 6-point set every quadruple has two equal circumradii, then some four points must be concyclic (contradicting strong general position). This would establish $n_4=6$ under the stronger convention.
   3. For general $k$, model the problem as an anti-Ramsey problem in a 3-uniform hypergraph where triples are colored by circumradius; seek a general anti-Ramsey bound tailored to the geometric constraints of circumradii.
4. (iv) Minimal counterexample structure (if small $n_4$ conjectures fail). A minimal counterexample to $n_4=6$ would be 6 points in (strong) general position such that every 4-subset has a repeated circumradius among its 4 triangles. The 5-point example above suggests a counterexample may feature near-parallel pairs and repeated local distance patterns causing two triangles to share the same $R^2$ value (e.g. repeated rational values like $5/2$).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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

Ambiguity note. The phrase "points in general position" is not defined in the excerpt. In planar combinatorial geometry it often means "no three collinear"; sometimes, in circle-related problems, it also includes "no four concyclic". I treat both:

• Literal (minimal) convention: general position means no three points are collinear.
• Stronger convention: no three collinear and no four points lie on a common circle.

Given $k\ge 3$, define $n_k$ to be the smallest integer $N$ (if it exists) such that every set of $N$ points in $\mathbb{R}^2$ in general position contains a subset $S$ of $k$ points with the property:

For all distinct triples $T\subset S$ with $|T|=3$, the circumradius of the circle through $T$ is different for different $T$.

(Each triple is non-collinear under both conventions, so it determines a unique circumcircle and circumradius.)

The problem asks to determine $n_k$.

QUICK LITERATURE/CONTEXT CHECK

The excerpt states: Erdős asked whether $n_k$ exists, claimed an argument giving $n_k\le k+2\binom{k-1}{2}\binom{k-1}{3}$, but this was incorrect; Martinez--Roldán-Pensado gave a corrected argument proving $n_k\ll k^9$.

Below I prove exact $n_3$ and give explicit lower-bound constructions for $n_4$ by counterexamples, using exact computations of circumradii.

ATTACK PLAN

• Small $k$ exact values: Determine $n_3$ directly. For $k=4$, try to decide $n_4$ by explicit counterexamples for $N=4,5$ and then look for a proof for $N=6$ (not achieved here).
• General $k$: Without reproducing the Martinez--Roldán-Pensado argument, I will not claim a full existence proof; I only record the bound stated in the excerpt as context.

WORK

FAST REALITY CHECK (circumradius computation formulas).

For a non-collinear triangle with side lengths $a,b,c$ and area $\Delta$, its circumradius is \[ R = \frac{abc}{4\Delta}. \] For explicit integer-coordinate examples, I compute $R^2$ exactly via \[ R^2 = \frac{a^2 b^2 c^2}{16\Delta^2} = \frac{a^2 b^2 c^2}{4\,\operatorname{Area2}^2}, \] where $\operatorname{Area2}=2\Delta$ is the doubled signed area.

Lemma (Exact value of $n_3$). Under either convention of general position, $n_3=3$.

Proof. We must find the minimal $N$ such that any $N$ points in general position contain $3$ points whose $\binom{3}{3}=1$ triple has "all circumradii distinct".

If $N=3$, any 3 points in general position are non-collinear, hence determine a unique circle with some radius $R$. Since there is only one triple, the set of circumradii has size 1 and is vacuously pairwise distinct. Thus every 3-point set in general position contains a good 3-subset (itself).

If $N<3$, no $k=3$ subset exists at all. Therefore the minimal such $N$ is $3$. $\square$

Lemma (A 4-point counterexample: $n_4>4$). Under the minimal convention (no three collinear), $n_4>4$.

Proof. Take four points on a common circle, e.g. \[ A=(1,0),\;B=(0,1),\;C=(-1,0),\;D=(0,-1). \] No three of these are collinear, so this set is in general position under the minimal convention.

Any triple among $\{A,B,C,D\}$ lies on the same circle $x^2+y^2=1$, so every triangle has circumradius $1$. Therefore, for the only 4-point subset (the full set), the four triples determine circles of the same radius, hence not all radii are distinct. Thus $N=4$ does not guarantee a good 4-subset, so $n_4>4$. $\square$

Lemma (A stronger 5-point counterexample: $n_4\ge 6$ even with no four concyclic). Consider the five points \[ P_1=(-2,-2),\;P_2=(-2,-1),\;P_3=(-1,1),\;P_4=(-1,2),\;P_5=(0,0). \] Then:

1. No three of these points are collinear.
2. No four of these points are concyclic (equivalently: for each 4-subset, not all four triangle circumradii coincide).
3. Every 4-subset of $\{P_1,\dots,P_5\}$ contains two distinct triangles with the same circumradius.

Consequently, $n_4\ge 6$ under either convention of general position.

Proof. Step 1: no three collinear. The set has two points with $x=-2$ ($P_1,P_2$), two points with $x=-1$ ($P_3,P_4$), and one point with $x=0$ ($P_5$), so no vertical line contains three points. A direct check of the remaining potential collinearities can be done by verifying that for each triple $(P_i,P_j,P_k)$ the doubled area \[ \operatorname{Area2}(P_i,P_j,P_k)=(x_j-x_i)(y_k-y_i)-(y_j-y_i)(x_k-x_i) \] is nonzero. In fact, a direct computation gives the 10 doubled areas: \[ \operatorname{Area2}(P_1,P_2,P_3)=-1,\;\operatorname{Area2}(P_1,P_2,P_4)=-1,\;\operatorname{Area2}(P_1,P_2,P_5)=-2,\;\operatorname{Area2}(P_1,P_3,P_4)=1,\;\operatorname{Area2}(P_1,P_3,P_5)=-4,\;\operatorname{Area2}(P_1,P_4,P_5)=-6,\;\operatorname{Area2}(P_2,P_3,P_4)=1,\;\operatorname{Area2}(P_2,P_3,P_5)=-3,\;\operatorname{Area2}(P_2,P_4,P_5)=-5,\;\operatorname{Area2}(P_3,P_4,P_5)=-1. \] None of these is $0$, so no three points are collinear.

Step 2: compute circumradii squared for each 4-subset. For each 4-subset, there are 4 triangles. I list the four values of $R^2$ (as exact rationals) computed via $R^2=\frac{a^2b^2c^2}{4\,\operatorname{Area2}^2}$.

(a) Quadruple $\{P_1,P_2,P_3,P_4\}$: \[ R^2\in\left\{\frac{25}{2},\frac{85}{2},\frac{85}{2},\frac{25}{2}\right\}. \] Thus at least two circumradii coincide (in fact two pairs coincide), and not all four coincide.

(b) Quadruple $\{P_1,P_2,P_3,P_5\}$: \[ R^2\in\left\{\frac{25}{2},\frac{5}{2},\frac{5}{2},\frac{25}{18}\right\}. \] Thus there is a repeated value $5/2$, and not all four coincide.

(c) Quadruple $\{P_1,P_2,P_4,P_5\}$: \[ R^2\in\left\{\frac{85}{2},\frac{5}{2},\frac{85}{18},\frac{5}{2}\right\}. \] Thus there is a repeated value $5/2$, and not all four coincide.

(d) Quadruple $\{P_1,P_3,P_4,P_5\}$: \[ R^2\in\left\{\frac{85}{2},\frac{5}{2},\frac{85}{18},\frac{5}{2}\right\}. \] Again there is a repeated value $5/2$, and not all four coincide.

(e) Quadruple $\{P_2,P_3,P_4,P_5\}$: \[ R^2\in\left\{\frac{25}{2},\frac{25}{18},\frac{5}{2},\frac{5}{2}\right\}. \] Again there is a repeated value $5/2$, and not all four coincide.

In each case, the list of four radii contains a repeat, so no 4-subset has all four circumradii distinct.

Step 3: conclude. Since this 5-point configuration is in general position under either convention (Steps 1 and the "not all equal" part of Step 2), but contains no good 4-subset, it follows that $n_4\ge 6$. $\square$

VERIFICATION

• Lemma (Exact value of $n_3$): The vacuity for $k=3$ is correct because there is exactly one triple.
• Lemma (A 4-point counterexample: $n_4>4$): The 4 points are concyclic and non-collinear in triples, so it is a valid counterexample under the minimal convention. Under the stronger convention (excluding 4 concyclic) this example is not allowed, which is why the 5-point counterexample lemma was given.
• Lemma (A stronger 5-point counterexample: $n_4\ge 6$ even with no four concyclic): The radii-squared lists were computed exactly (rational arithmetic) for each 4-subset; each list contains a duplicate, so each 4-subset fails the distinctness requirement. Also no list is constant, so no 4-subset is concyclic.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. Exact value $n_3=3$; and an explicit 5-point configuration in strong general position with no good 4-subset, implying $n_4\ge 6$.
2. (ii) First gap. Decide whether $n_4=6$ (i.e. prove or disprove that every 6-point set in general position contains a 4-point subset with all four triangle circumradii distinct), and more generally determine $n_k$ for $k\ge 4$.
3. (iii) Top 3 next moves.
   1. Computational search over integer-coordinate point sets with $N=6$ to try to find a counterexample to $n_4\le 6$ (i.e. a 6-point set with no good quadruple), which would show $n_4\ge 7$.
   2. Prove a structural lemma: if in a 6-point set every quadruple has two equal circumradii, then some four points must be concyclic (contradicting strong general position). This would establish $n_4=6$ under the stronger convention.
   3. For general $k$, model the problem as an anti-Ramsey problem in a 3-uniform hypergraph where triples are colored by circumradius; seek a general anti-Ramsey bound tailored to the geometric constraints of circumradii.
4. (iv) Minimal counterexample structure (if small $n_4$ conjectures fail). A minimal counterexample to $n_4=6$ would be 6 points in (strong) general position such that every 4-subset has a repeated circumradius among its 4 triangles. The 5-point example above suggests a counterexample may feature near-parallel pairs and repeated local distance patterns causing two triangles to share the same $R^2$ value (e.g. repeated rational values like $5/2$).