/- 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 Mathlib.Analysis.InnerProductSpace.Basic public import Mathlib.Data.Finset.Max public import Mathlib.Data.Set.Card public import Mathlib.LinearAlgebra.AffineSpace.FiniteDimensional public import Mathlib.Tactic.Abel public import Mathlib.Tactic.FieldSimp public import Mathlib.Tactic.FinCases public import Mathlib.Tactic.Linarith public import Mathlib.Tactic.Module public import Mathlib.Tactic.NormNum public import Mathlib.Tactic.Positivity public import Mathlib.Tactic.Ring

Ordinary lines and the Sylvester–Gallai theorem

An ordinary line meets a finite point set in exactly two points. Every finite noncollinear set in a real inner product space has an ordinary line.

The proof uses the minimum positive point-to-line distance argument.

Reference: [Mo51] Motzkin, T. S., The lines and planes connecting the points of a finite set. Transactions of the American Mathematical Society 70 (1951), 451–464.

@[expose] public sectionnamespace SylvesterGallaiopen RealInnerProductSpacevariable {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]private noncomputable def areaSq (u v : V) : ℝ := ‖u‖ ^ 2 * ‖v‖ ^ 2 - ⟪u, v⟫ ^ 2private lemma areaSq_nonneg (u v : V) : 0 ≤ areaSq u v := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:V⊢ 0 ≤ areaSq u v V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vh:|⟪u, v⟫| ≤ ‖u‖ * ‖v‖⊢ 0 ≤ areaSq u v V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vh:|⟪u, v⟫| ≤ ‖u‖ * ‖v‖this:|⟪u, v⟫| ^ 2 ≤ (‖u‖ * ‖v‖) ^ 2⊢ 0 ≤ areaSq u v V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vh:|⟪u, v⟫| ≤ ‖u‖ * ‖v‖this:|⟪u, v⟫| ^ 2 ≤ (‖u‖ * ‖v‖) ^ 2⊢ 0 ≤ ‖u‖ ^ 2 * ‖v‖ ^ 2 - ⟪u, v⟫ ^ 2 All goals completed! 🐙private lemma areaSq_comm (u v : V) : areaSq u v = areaSq v u := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:V⊢ areaSq u v = areaSq v u V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:V⊢ ‖u‖ ^ 2 * ‖v‖ ^ 2 - ⟪v, u⟫ ^ 2 = ‖v‖ ^ 2 * ‖u‖ ^ 2 - ⟪v, u⟫ ^ 2 All goals completed! 🐙private lemma areaSq_smul (u v : V) (t : ℝ) : areaSq (t • u) v = t ^ 2 * areaSq u v := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vt:ℝ⊢ areaSq (t • u) v = t ^ 2 * areaSq u v V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vt:ℝ⊢ t ^ 2 * ‖u‖ ^ 2 * ‖v‖ ^ 2 - t ^ 2 * ⟪u, v⟫ ^ 2 = t ^ 2 * (‖u‖ ^ 2 * ‖v‖ ^ 2 - ⟪u, v⟫ ^ 2) All goals completed! 🐙private lemma areaSq_shear (u v : V) (t : ℝ) : areaSq u (v + t • u) = areaSq u v := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vt:ℝ⊢ areaSq u (v + t • u) = areaSq u v V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vt:ℝ⊢ ‖u‖ ^ 2 * (‖v‖ ^ 2 + 2 * (t * ⟪v, u⟫) + t ^ 2 * ‖u‖ ^ 2) - (⟪v, u⟫ + t * ‖u‖ ^ 2) ^ 2 = ‖u‖ ^ 2 * ‖v‖ ^ 2 - ⟪v, u⟫ ^ 2 All goals completed! 🐙V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vhu:u ≠ 0hn:0 < ‖u‖ ^ 2h:areaSq u v = 0hz:‖v - (⟪u, v⟫ / ‖u‖ ^ 2) • u‖ ^ 2 = 0this:v - (⟪u, v⟫ / ‖u‖ ^ 2) • u = 0⊢ v = (⟪u, v⟫ / ‖u‖ ^ 2) • u All goals completed! 🐙 V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vv:Vhu:u ≠ 0hn:0 < ‖u‖ ^ 2⊢ (∃ t, v = t • u) → areaSq u v = 0 V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vhu:u ≠ 0hn:0 < ‖u‖ ^ 2t:ℝ⊢ areaSq u (t • u) = 0 V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vu:Vhu:u ≠ 0hn:0 < ‖u‖ ^ 2t:ℝ⊢ ‖u‖ ^ 2 * (t ^ 2 * ‖u‖ ^ 2) - t ^ 2 * (‖u‖ ^ 2) ^ 2 = 0 All goals completed! 🐙V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ r, (AffineMap.lineMap a b) r = x) ↔ ∃ t, x = a + t • (b - a) V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ r, r • (b - a) + a = x) ↔ ∃ t, x = a + t • (b - a) V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ r, r • (b - a) + a = x) → ∃ t, x = a + t • (b - a)V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ t, x = a + t • (b - a)) → ∃ r, r • (b - a) + a = x V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ r, r • (b - a) + a = x) → ∃ t, x = a + t • (b - a)V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:V⊢ (∃ t, x = a + t • (b - a)) → ∃ r, r • (b - a) + a = x V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:Vt:ℝht:x = a + t • (b - a)⊢ ∃ r, r • (b - a) + a = x V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:Vt:ℝht:t • (b - a) + a = x⊢ ∃ t, x = a + t • (b - a)V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:Vt:ℝht:x = a + t • (b - a)⊢ ∃ r, r • (b - a) + a = x exact ⟨t, V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vx:Vt:ℝht:x = a + t • (b - a)⊢ t • (b - a) + a = x All goals completed! 🐙⟩private noncomputable def heightSq (p a b : V) : ℝ := areaSq (b - a) (p - a) / ‖b - a‖ ^ 2V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vp:Va:Vb:Vhab:a ≠ bhp:p ∉ line[ℝ, a, b]h:0 = areaSq (b - a) (p - a)t:ℝht:p - a = t • (b - a)⊢ p = a + (p - a); All goals completed! 🐙⟩V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vp:Vx:Vy:Vhp:p ∉ line[ℝ, a, b]hx:x ∈ line[ℝ, a, b]hy:y ∈ line[ℝ, a, b]hxy:x ≠ yh:x ∈ line[ℝ, p, y]hc:Collinear ℝ {x, p, y}hp':p ∈ line[ℝ, x, y]⊢ False All goals completed! 🐙V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vp:Vx:Vy:Vh₁:x - p = x - y + (y - p)h₂:p - y = -(y - p)he:areaSq (y - p) (x - y + (y - p)) = areaSq (y - p) (x - y)⊢ areaSq (x - y) (y - p) = areaSq (x - y) (-(y - p)) All goals completed! 🐙

Kelly's strict inequality for two points on the same side of the perpendicular foot.

V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Va:Vb:Vp:Vx:Vy:Vhab:a ≠ bhp:p ∉ line[ℝ, a, b]hx:x ∈ line[ℝ, a, b]hy:y ∈ line[ℝ, a, b]hs:0 ≤ ⟪x - p, b - a⟫ * ⟪y - p, b - a⟫ho:⟪x - p, b - a⟫ ^ 2 ≤ ⟪y - p, b - a⟫ ^ 2s:ℝhx':x = a + s • (b - a)t:ℝhy':y = a + t • (b - a)v:V := b - aA:ℝ := areaSq v (p - a)X:ℝ := ⟪x - p, v⟫Y:ℝ := ⟪y - p, v⟫hv:0 < ‖v‖ ^ 2hA:0 < Ahy₀:y - p ≠ 0hypos:0 < ‖y - p‖ ^ 2hd:Y - X = (t - s) * ‖v‖ ^ 2ha:areaSq (y - p) (x - p) = (s - t) ^ 2 * Ahn:‖y - p‖ ^ 2 * ‖v‖ ^ 2 = A + Y ^ 2hXY:X ^ 2 ≤ X * Yhstrict:(Y - X) ^ 2 < A + Y ^ 2heq:areaSq (y - p) (x - p) * ‖v‖ ^ 2 * ‖v‖ ^ 2 = A * (Y - X) ^ 2hmul:areaSq (y - p) (x - p) * ‖v‖ ^ 2 * ‖v‖ ^ 2 < A * (‖y - p‖ ^ 2 * ‖v‖ ^ 2)⊢ areaSq (y - p) (x - p) * ‖v‖ ^ 2 < areaSq (b - a) (p - a) * ‖y - p‖ ^ 2 All goals completed! 🐙f:Fin 3 → ℝhsign:0 ≤ f 0 * f 1 ∨ 0 ≤ f 1 * f 2 ∨ 0 ≤ f 0 * f 2hpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2 f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 1⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 1 * f 2⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 2⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2 f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 1⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2 exact hpair 0 1 (f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 1⊢ 0 ≠ 1 All goals completed! 🐙) h f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 1 * f 2⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2 exact hpair 1 2 (f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 1 * f 2⊢ 1 ≠ 2 All goals completed! 🐙) h f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 2⊢ ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2 exact hpair 0 2 (f:Fin 3 → ℝhpair:∀ (i j : Fin 3), i ≠ j → 0 ≤ f i * f j → ∃ i j, i ≠ j ∧ 0 ≤ f i * f j ∧ f i ^ 2 ≤ f j ^ 2h:0 ≤ f 0 * f 2⊢ 0 ≠ 2 All goals completed! 🐙) hV:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sh:∀ p ∈ s, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → p ∈ line[ℝ, a, b]a:Vha:a ∈ sb:Vhb:b ∈ shba:b ≠ a⊢ ∃ v, ∀ p ∈ ↑s, ∃ r, p = r • v +ᵥ a V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sh:∀ p ∈ s, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → p ∈ line[ℝ, a, b]a:Vha:a ∈ sb:Vhb:b ∈ shba:b ≠ a⊢ ∀ p ∈ ↑s, ∃ r, p = r • (b - a) +ᵥ a V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sh:∀ p ∈ s, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → p ∈ line[ℝ, a, b]a:Vha:a ∈ sb:Vhb:b ∈ shba:b ≠ ap:Vhp:p ∈ ↑s⊢ ∃ r, p = r • (b - a) +ᵥ a V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sh:∀ p ∈ s, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → p ∈ line[ℝ, a, b]a:Vha:a ∈ sb:Vhb:b ∈ shba:b ≠ ap:Vhp:p ∈ ↑st:ℝht:p = a + t • (b - a)⊢ ∃ r, p = r • (b - a) +ᵥ a exact ⟨t, V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sh:∀ p ∈ s, ∀ a ∈ s, ∀ b ∈ s, a ≠ b → p ∈ line[ℝ, a, b]a:Vha:a ∈ sb:Vhb:b ∈ shba:b ≠ ap:Vhp:p ∈ ↑st:ℝht:p = a + t • (b - a)⊢ p = t • (b - a) +ᵥ a All goals completed! 🐙⟩

A finite noncollinear subset of a real inner product space has an ordinary line.

V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sT:Finset (V × V × V) := {q ∈ s ×ˢ s ×ˢ s | q.2.1 ≠ q.2.2 ∧ q.1 ∉ line[ℝ, q.2.1, q.2.2]}hT:∀ (p a b : V), (p, a, b) ∈ T ↔ p ∈ s ∧ a ∈ s ∧ b ∈ s ∧ a ≠ b ∧ p ∉ line[ℝ, a, b]p✝:Vhp✝:p ∈ sa✝:Vha✝:a ∈ sb✝:Vhb✝:b ∈ shab✝:a ≠ bhpab✝:p ∉ line[ℝ, a, b]hne:T.Nonemptyp:Va:Vb:Vhmem:(p, a, b) ∈ Thmin:∀ x' ∈ T, heightSq (p, a, b).1 (p, a, b).2.1 (p, a, b).2.2 ≤ heightSq x'.1 x'.2.1 x'.2.2hp:p ∈ sha:a ∈ shb:b ∈ shab:a ≠ bhpab:p ∉ line[ℝ, a, b]c:Vhc:c ∈ shcL:c ∈ line[ℝ, a, b]h:c ≠ a ∧ c ≠ bq:Fin 3 → V := ![a, b, c]hqS:∀ (i : Fin 3), q i ∈ shqL:∀ (i : Fin 3), q i ∈ line[ℝ, a, b]hq:Function.Injective q⊢ False V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sT:Finset (V × V × V) := {q ∈ s ×ˢ s ×ˢ s | q.2.1 ≠ q.2.2 ∧ q.1 ∉ line[ℝ, q.2.1, q.2.2]}hT:∀ (p a b : V), (p, a, b) ∈ T ↔ p ∈ s ∧ a ∈ s ∧ b ∈ s ∧ a ≠ b ∧ p ∉ line[ℝ, a, b]p✝:Vhp✝:p ∈ sa✝:Vha✝:a ∈ sb✝:Vhb✝:b ∈ shab✝:a ≠ bhpab✝:p ∉ line[ℝ, a, b]hne:T.Nonemptyp:Va:Vb:Vhmem:(p, a, b) ∈ Thmin:∀ x' ∈ T, heightSq (p, a, b).1 (p, a, b).2.1 (p, a, b).2.2 ≤ heightSq x'.1 x'.2.1 x'.2.2hp:p ∈ sha:a ∈ shb:b ∈ shab:a ≠ bhpab:p ∉ line[ℝ, a, b]c:Vhc:c ∈ shcL:c ∈ line[ℝ, a, b]h:c ≠ a ∧ c ≠ bq:Fin 3 → V := ![a, b, c]hqS:∀ (i : Fin 3), q i ∈ shqL:∀ (i : Fin 3), q i ∈ line[ℝ, a, b]hq:Function.Injective qf:Fin 3 → ℝ := fun i ↦ ⟪q i - p, b - a⟫⊢ False V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sT:Finset (V × V × V) := {q ∈ s ×ˢ s ×ˢ s | q.2.1 ≠ q.2.2 ∧ q.1 ∉ line[ℝ, q.2.1, q.2.2]}hT:∀ (p a b : V), (p, a, b) ∈ T ↔ p ∈ s ∧ a ∈ s ∧ b ∈ s ∧ a ≠ b ∧ p ∉ line[ℝ, a, b]p✝:Vhp✝:p ∈ sa✝:Vha✝:a ∈ sb✝:Vhb✝:b ∈ shab✝:a ≠ bhpab✝:p ∉ line[ℝ, a, b]hne:T.Nonemptyp:Va:Vb:Vhmem:(p, a, b) ∈ Thmin:∀ x' ∈ T, heightSq (p, a, b).1 (p, a, b).2.1 (p, a, b).2.2 ≤ heightSq x'.1 x'.2.1 x'.2.2hp:p ∈ sha:a ∈ shb:b ∈ shab:a ≠ bhpab:p ∉ line[ℝ, a, b]c:Vhc:c ∈ shcL:c ∈ line[ℝ, a, b]h:c ≠ a ∧ c ≠ bq:Fin 3 → V := ![a, b, c]hqS:∀ (i : Fin 3), q i ∈ shqL:∀ (i : Fin 3), q i ∈ line[ℝ, a, b]hq:Function.Injective qf:Fin 3 → ℝ := fun i ↦ ⟪q i - p, b - a⟫i:Fin 3j:Fin 3hij:i ≠ jhsign:0 ≤ f i * f jhorder:f i ^ 2 ≤ f j ^ 2⊢ False V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sT:Finset (V × V × V) := {q ∈ s ×ˢ s ×ˢ s | q.2.1 ≠ q.2.2 ∧ q.1 ∉ line[ℝ, q.2.1, q.2.2]}hT:∀ (p a b : V), (p, a, b) ∈ T ↔ p ∈ s ∧ a ∈ s ∧ b ∈ s ∧ a ≠ b ∧ p ∉ line[ℝ, a, b]p✝:Vhp✝:p ∈ sa✝:Vha✝:a ∈ sb✝:Vhb✝:b ∈ shab✝:a ≠ bhpab✝:p ∉ line[ℝ, a, b]hne:T.Nonemptyp:Va:Vb:Vhmem:(p, a, b) ∈ Thmin:∀ x' ∈ T, heightSq (p, a, b).1 (p, a, b).2.1 (p, a, b).2.2 ≤ heightSq x'.1 x'.2.1 x'.2.2hp:p ∈ sha:a ∈ shb:b ∈ shab:a ≠ bhpab:p ∉ line[ℝ, a, b]c:Vhc:c ∈ shcL:c ∈ line[ℝ, a, b]h:c ≠ a ∧ c ≠ bq:Fin 3 → V := ![a, b, c]hqS:∀ (i : Fin 3), q i ∈ shqL:∀ (i : Fin 3), q i ∈ line[ℝ, a, b]hq:Function.Injective qf:Fin 3 → ℝ := fun i ↦ ⟪q i - p, b - a⟫i:Fin 3j:Fin 3hij:i ≠ jhsign:0 ≤ f i * f jhorder:f i ^ 2 ≤ f j ^ 2hpj:p ≠ q j⊢ False V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sT:Finset (V × V × V) := {q ∈ s ×ˢ s ×ˢ s | q.2.1 ≠ q.2.2 ∧ q.1 ∉ line[ℝ, q.2.1, q.2.2]}hT:∀ (p a b : V), (p, a, b) ∈ T ↔ p ∈ s ∧ a ∈ s ∧ b ∈ s ∧ a ≠ b ∧ p ∉ line[ℝ, a, b]p✝:Vhp✝:p ∈ sa✝:Vha✝:a ∈ sb✝:Vhb✝:b ∈ shab✝:a ≠ bhpab✝:p ∉ line[ℝ, a, b]hne:T.Nonemptyp:Va:Vb:Vhmem:(p, a, b) ∈ Thmin:∀ x' ∈ T, heightSq (p, a, b).1 (p, a, b).2.1 (p, a, b).2.2 ≤ heightSq x'.1 x'.2.1 x'.2.2hp:p ∈ sha:a ∈ shb:b ∈ shab:a ≠ bhpab:p ∉ line[ℝ, a, b]c:Vhc:c ∈ shcL:c ∈ line[ℝ, a, b]h:c ≠ a ∧ c ≠ bq:Fin 3 → V := ![a, b, c]hqS:∀ (i : Fin 3), q i ∈ shqL:∀ (i : Fin 3), q i ∈ line[ℝ, a, b]hq:Function.Injective qf:Fin 3 → ℝ := fun i ↦ ⟪q i - p, b - a⟫i:Fin 3j:Fin 3hij:i ≠ jhsign:0 ≤ f i * f jhorder:f i ^ 2 ≤ f j ^ 2hpj:p ≠ q jhnew:(q i, p, q j) ∈ T⊢ False All goals completed! 🐙end SylvesterGallainamespace EuclideanGeometryvariable {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]

The distinct ordinary lines of a finite point set. The image removes duplicate lines.

noncomputable def ordinaryLines (s : Finset V) : Finset (AffineSubspace ℝ V) := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset V⊢ Finset (AffineSubspace ℝ V) classical All goals completed! 🐙open scoped Classical in

Membership records two distinct points generating a line with exactly two incidences.

theorem mem_ordinaryLines {s : Finset V} {L : AffineSubspace ℝ V} : L ∈ ordinaryLines s ↔ (∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L) ∧ (s.filter fun p => p ∈ L).card = 2 := V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset VL:AffineSubspace ℝ V⊢ L ∈ ordinaryLines s ↔ (∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L) ∧ {p ∈ s | p ∈ L}.card = 2 classical V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset VL:AffineSubspace ℝ V⊢ (∃ a, ((a.1 ∈ s ∧ a.2 ∈ s) ∧ a.1 ≠ a.2) ∧ line[ℝ, a.1, a.2] = L) ∧ {p ∈ s | p ∈ L}.card = 2 ↔ (∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ line[ℝ, a, b] = L) ∧ {p ∈ s | p ∈ L}.card = 2 All goals completed! 🐙

Every line counted by ordinaryLines is one-dimensional.

V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Va:Vleft✝¹:a ∈ sb:Vleft✝:b ∈ shab:a ≠ bhL:line[ℝ, a, b] ∈ ordinaryLines sright✝:{p ∈ s | p ∈ line[ℝ, a, b]}.card = 2⊢ Module.finrank ℝ ↥(ℝ ∙ (a -ᵥ b)) = 1 All goals completed! 🐙

The counted lines are precisely the geometric lines meeting the point set in two points.

V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset VL:AffineSubspace ℝ Vhcard:(↑s ∩ ↑L).ncard = {p ∈ s | p ∈ L}.cardhline:Module.finrank ℝ ↥L.direction = 1h:{p ∈ s | p ∈ L}.card = 2a:Vb:Vhab:a ≠ bhabs:{p ∈ s | p ∈ L} = {a, b}ha:a ∈ s ∧ a ∈ Lhb:b ∈ s ∧ b ∈ Lthis:FiniteDimensional ℝ ↥L.directionheq:line[ℝ, a, b] = L⊢ L ∈ ordinaryLines s All goals completed! 🐙

Sylvester–Gallai supplies an ordinary line for every noncollinear finite set.

V:Type u_1inst✝¹:NormedAddCommGroup Vinst✝:InnerProductSpace ℝ Vs:Finset Vhs:¬Collinear ℝ ↑sa:Vha:a ∈ sb:Vhb:b ∈ shab:a ≠ bh:∀ p ∈ s, p ∈ line[ℝ, a, b] → p = a ∨ p = bheq:{p ∈ s | p ∈ line[ℝ, a, b]} = {a, b}⊢ {p ∈ s | p ∈ line[ℝ, a, b]}.card = 2 All goals completed! 🐙end EuclideanGeometry