/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 1086
References:
[ErPu71] Erdős, P. and Purdy, G., Some extremal problems in geometry. J. Combinatorial Theory Ser. A 10 (1971), 246-252.
[RaSh17] Raz, O. E. and Sharir, M., The number of unit-area triangles in the plane: theme and variations. Combinatorica 37 (2017), 1221-1240. arXiv:1501.00379
@[expose] public sectionopen Filter Asymptoticsopen scoped EuclideanGeometrynamespace Erdos1086open scoped Classical in
The number of triangles with vertices in P and area a: the 3-element subsets of P
whose vertices p, q, r satisfy |triangle_area p q r| = a.
noncomputable def triangleAreaCount (P : Finset ℝ²) (a : ℝ) : ℕ :=
((P.powersetCard 3).filter fun T =>
∃ p q r : ℝ², T = {p, q, r} ∧ |EuclideanGeometry.triangle_area p q r| = a).card
$g(n)$: the maximum, over all sets of $n$ points in the plane and all areas $a > 0$, of the
number of triangles of area $a$ with vertices in the set. Only positive areas count, since every
collinear triple has area $0$. The set of values is nonempty and bounded by $\binom{n}{3}$, so
sSup is a true maximum.
noncomputable def g (n : ℕ) : ℕ :=
sSup {m : ℕ | ∃ (P : Finset ℝ²) (a : ℝ), P.card = n ∧ 0 < a ∧ triangleAreaCount P a = m}
A set of n points has at most $\binom{n}{3}$ triangles of any given area.
@[category API, AMS 52]
theorem triangleAreaCount_le (P : Finset ℝ²) (a : ℝ) :
triangleAreaCount P a ≤ P.card.choose 3 := P:Finset ℝ²a:ℝ⊢ triangleAreaCount P a ≤ P.card.choose 3
classical
P:Finset ℝ²a:ℝ⊢ {T ∈ Finset.powersetCard 3 P | ∃ p q r, T = {p, q, r} ∧ |EuclideanGeometry.triangle_area p q r| = a}.card ≤
P.card.choose 3
All goals completed! 🐙
A set of points has at most g n triangles of any given positive area.
@[category API, AMS 52]
theorem triangleAreaCount_le_g (P : Finset ℝ²) {a : ℝ} (ha : 0 < a) :
triangleAreaCount P a ≤ g P.card := P:Finset ℝ²a:ℝha:0 < a⊢ triangleAreaCount P a ≤ g P.card
P:Finset ℝ²a:ℝha:0 < a⊢ P.card.choose 3 ∈ upperBounds {m | ∃ P_1 a, P_1.card = P.card ∧ 0 < a ∧ triangleAreaCount P_1 a = m}
P:Finset ℝ²a:ℝha:0 < aQ:Finset ℝ²b:ℝhQ:Q.card = P.card⊢ triangleAreaCount Q b ≤ P.card.choose 3
All goals completed! 🐙def erdos_1086.answer : ℕ → ℝ := sorryLet $g(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^2$ contains the vertices of at most $g(n)$ many triangles with the same area. Estimate $g(n)$.
Only triangles of positive area are counted.
@[category research open, question value, AMS 52]
theorem erdos_1086 : (fun n : ℕ ↦ (g n : ℝ)) =Θ[atTop] erdos_1086.answer := ⊢ (fun n ↦ ↑(g n)) =Θ[atTop] erdos_1086.answer
All goals completed! 🐙Erdős and Purdy [ErPu71] proved $$n^2\log\log n \ll g(n) \ll n^{5/2}.$$
This is the lower bound.
@[category research solved, AMS 52]
theorem erdos_1086.variants.erdos_purdy_lower :
(fun n : ℕ ↦ (n : ℝ) ^ 2 * Real.log (Real.log n)) =O[atTop] fun n : ℕ ↦ (g n : ℝ) := ⊢ (fun n ↦ ↑n ^ 2 * Real.log (Real.log ↑n)) =O[atTop] fun n ↦ ↑(g n)
All goals completed! 🐙The upper bound of Erdős and Purdy [ErPu71] has been improved a number of times. The best known bound is $g(n) \ll n^{20/9}$ by Raz and Sharir [RaSh17].
@[category research solved, AMS 52]
theorem erdos_1086.variants.raz_sharir :
(fun n : ℕ ↦ (g n : ℝ)) =O[atTop] fun n : ℕ ↦ (n : ℝ) ^ (20 / 9 : ℝ) := ⊢ (fun n ↦ ↑(g n)) =O[atTop] fun n ↦ ↑n ^ (20 / 9)
All goals completed! 🐙end Erdos1086