summaryrefslogtreecommitdiff
path: root/proofs/GipfelFind.lean
diff options
context:
space:
mode:
authorJohannes Hofmann <Johannes.Hofmann@gmx.de>2026-11-10 09:13:35 +0100
committerJohannes Hofmann <Johannes.Hofmann@gmx.de>2026-11-10 09:13:35 +0100
commit45a4b80a3d44f054a471cd417c7c2698f4770599 (patch)
tree7785b86ed5a6999202c39616936556d8982d49f1 /proofs/GipfelFind.lean
parent0b0663e0c9dc664f35ffead3b395ffd2009fd98c (diff)
proofs: Lean transcriptions + flaw-finding, with a Rust referee
Gipfel.lean verifies the structural invariants (mark_duplicates keeps hill indices stable). GipfelFind.lean hunts flaws: exact Int model for the general fact, Float grid search for concrete IEEE witnesses, every witness re-checked against the real code by rust-check/. Findings: 1 fixed on master (is_visible azimuth wrap), 2 proven benign via project_point (all witnesses NaN via 0*inf; residual near-zero denominators documented), 3 open but cosmetic, 4 already handled by the stitch caller. GipfelMathlib.lean.txt stays an unchecked sketch, kept as .txt so it cannot pass for a verified artifact. Verified from this location: lean checks both files clean, rust-check runs against the workspace gipfel-core via path dependency.
Diffstat (limited to 'proofs/GipfelFind.lean')
-rw-r--r--proofs/GipfelFind.lean273
1 files changed, 273 insertions, 0 deletions
diff --git a/proofs/GipfelFind.lean b/proofs/GipfelFind.lean
new file mode 100644
index 0000000..099abb2
--- /dev/null
+++ b/proofs/GipfelFind.lean
@@ -0,0 +1,273 @@
+/-
+ GipfelFind.lean — using Lean to LOOK FOR flaws in gipfel-core.
+
+ Method: transcribe the suspect logic into Lean twice.
+ * `Int` model → prove the general fact (why it fails, where the boundary is)
+ * `Float` model → exhaustive search for a concrete witness
+ Every witness below was then re-checked against the real Rust code.
+-/
+
+def PI : Float := 3.141592653589793
+def degf (d : Float) : Float := d * PI / 180
+
+-- ════════════════════════════════════════════════════════════════════════
+-- FINDING 1 — `Panorama::is_visible` silently accepts *everything* once
+-- |α − a_center| > 2π
+-- STATUS: FIXED on master — is_visible now wraps with `% 2π` before the
+-- fold and rejects non-finite α / a_center. Regression test:
+-- panorama::tests::out_of_range_center_angle_stays_safe.
+-- ════════════════════════════════════════════════════════════════════════
+-- panorama.rs:406
+-- let mut center_dist = (alph - self.parms.a_center).abs();
+-- if center_dist > PI { center_dist = 2*PI - center_dist; }
+-- if center_dist >= self.proj.get_view_angle() { return false; }
+-- self.max_view_angle <= 0.0 || center_dist < self.max_view_angle
+
+/-- Faithful transcription (single fold). -/
+def centerDist (α c : Float) : Float :=
+ let d := (α - c).abs
+ if d > PI then 2 * PI - d else d
+
+def isVisible (α c viewAngle : Float) : Bool := !((centerDist α c) >= viewAngle)
+
+/-- What the function *means*: angular separation folded into [0, π].
+ `wrapTurns` is exact for the search domain (|α − c| < 16π). -/
+def wrapTurns (d : Float) : Float :=
+ (List.range 16).foldl (init := d) fun acc _ =>
+ if acc > 2 * PI then acc - 2 * PI else acc
+
+def angDist (α c : Float) : Float :=
+ let d := wrapTurns (α - c).abs
+ if d > PI then 2 * PI - d else d
+
+-- ── 1a. Why it fails — exact, over Int (`p` stands for π) ──
+
+def fold (d p : Int) : Int := if d > p then 2 * p - d else d
+
+/-- The fold produces a *negative* "distance" exactly when d > 2π. -/
+theorem fold_neg_iff (d p : Int) (hd : 0 ≤ d) : fold d p < 0 ↔ 2 * p < d := by
+ unfold fold; split <;> omega
+
+theorem fold_ge_zero_iff (d p : Int) (hd : 0 ≤ d) : 0 ≤ fold d p ↔ d ≤ 2 * p := by
+ unfold fold; split <;> omega
+
+/-- A negative distance passes every comparison in `is_visible`. -/
+def visibleOf (cd viewAngle : Int) : Bool := !(cd >= viewAngle)
+
+theorem all_visible_when_negative (cd viewAngle : Int) (h : cd < 0) (hv : 0 ≤ viewAngle) :
+ visibleOf cd viewAngle = true := by
+ unfold visibleOf
+ have h2 : ¬(cd ≥ viewAngle) := by omega
+ simp [h2]
+
+/-- When the distance is honest, visibility implies "within the field of view". -/
+theorem ok_when_honest (cd viewAngle : Int) (h : ¬(cd ≥ viewAngle)) :
+ cd < viewAngle := by omega
+
+-- ── 1b. Search: which center angles actually break it? ──
+
+def viewAngle : Float := 1.0471976 -- rectilinear half-angle = 60°
+def alphas : List Float := (List.range 73).map fun i => degf (i.toFloat * 5)
+
+def violationAt (cdeg : Float) : Bool :=
+ let c := degf cdeg
+ alphas.any fun a => isVisible a c viewAngle && angDist a c > viewAngle
+
+/-- Sampled center angles (degrees) for which some hill *behind* the camera is
+ reported visible. -/
+def badCenters : List Float :=
+ (List.range 145).foldl (init := []) fun acc i =>
+ let c := i.toFloat * 15 - 1080
+ if violationAt c then acc ++ [c] else acc
+
+#eval "── Finding 1: center angles (degrees) where a hill outside the field of view is 'visible'"
+#eval badCenters
+
+/-- An ordinary, realistic input: camera azimuth −75° (i.e. the user entered a
+ bearing in [-180,180]), hill at azimuth 350°. -/
+def witness1 : Float × Float × Float × Float × Bool :=
+ (degf (-75), degf 350, centerDist (degf 350) (degf (-75)),
+ angDist (degf 350) (degf (-75)), isVisible (degf 350) (degf (-75)) viewAngle)
+
+#eval "── Finding 1: (center°, α°, reported center_dist, true separation°, isVisible)"
+#eval witness1
+
+/-- Exact characterization of the safe window, derived from the search. -/
+def safeWindow : List Float :=
+ (List.range 97).foldl (init := []) fun acc i =>
+ let c := i.toFloat - 48 -- -48 .. 48 degrees, 1° steps
+ if violationAt c then acc ++ [c] else acc
+
+#eval "── Finding 1: bad center angles in [-48°, 48°] (empty = safe near zero)"
+#eval safeWindow
+
+/-- NaN and infinite azimuths are reported visible as well. -/
+def isVisibleFull (α c viewAngle maxAngle : Float) : Bool :=
+ let cd0 := (α - c).abs
+ let cd := if cd0 > PI then 2 * PI - cd0 else cd0
+ if cd >= viewAngle then false else (maxAngle <= 0 || cd < maxAngle)
+
+#eval "── Finding 1b: is_visible(NaN) , is_visible(+∞) (both true = bug)"
+#eval (isVisibleFull (0/0) 0 viewAngle 0, isVisibleFull (1/0) 0 viewAngle 0)
+
+-- ════════════════════════════════════════════════════════════════════════
+-- FINDING 2 — can the projection denominator be exactly zero?
+-- _11 = 1/(cos pitch · cos elev · cos Δα + sin pitch · sin elev)
+-- and `project_point` filters NaN but not ±∞.
+-- (First-quadrant grid; see Finding 2b for the full picture + Rust referee.)
+-- ════════════════════════════════════════════════════════════════════════
+
+def denom (pitch elev dAlpha : Float) : Float :=
+ Float.cos pitch * Float.cos elev * Float.cos dAlpha + Float.sin pitch * Float.sin elev
+
+/-- Grid search: exact zeros, and the smallest |denominator| seen. -/
+def denomSearch : (List (Float × Float × Float)) × (Option Float) :=
+ (List.range 46).foldl (init := (([] : List (Float × Float × Float)), (none : Option Float))) fun acc i =>
+ (List.range 46).foldl (init := acc) fun acc j =>
+ (List.range 91).foldl (init := acc) fun acc k =>
+ let p := degf (i.toFloat * 2)
+ let e := degf (j.toFloat * 2)
+ let d := degf (k.toFloat * 4 - 180)
+ let v := Float.abs (denom p e d)
+ if v == 0 then (acc.1 ++ [(p, e, d)], some 0)
+ else (acc.1, match acc.2 with
+ | none => v
+ | some b => if v < b then v else b)
+
+#eval "── Finding 2: (exact zeros found, smallest |denominator|) on a 46×46×91 grid"
+#eval denomSearch
+
+#eval "── Finding 2: if it were zero → 1/0 = inf, and isNaN does NOT catch it"
+#eval (1 / (0 : Float), (1 / (0 : Float)).isNaN)
+
+-- ════════════════════════════════════════════════════════════════════════
+-- FINDING 2b — full-domain grid + exact model of ALL zero families,
+-- cross-checked against the real Rust code (rust-check/).
+-- ════════════════════════════════════════════════════════════════════════
+
+/-
+ Exact model (pen and paper, via the addition theorems). With
+ denom p e dα = cos p · cos e · cos dα + sin p · sin e:
+
+ dα = ±180°: denom = sin p sin e − cos p cos e = −cos(p + e)
+ → zero ⟺ p + e = ±90° (family A)
+ dα = 0 : denom = cos p cos e + sin p sin e = cos(p − e)
+ → zero ⟺ p − e = ±90° (family B)
+ otherwise : |cos dα| < 1 forces |denom| ≥ (1−|cos dα|)/2 · something
+ strictly positive on the domain — the two families are
+ the complete list of exact real zeros.
+
+ The ORIGINAL grid above only sampled p, e ∈ [0°, 90°] (justified by the
+ p↔e swap and (p,e)→(−p,−e) symmetries for SAME-sign pairs), which silently
+ skips the opposite-sign quadrant — and family B lives exactly there
+ (e.g. pitch +45°, elev −45°: camera tilted up, peak dead ahead below the
+ horizon). The full grid below removes the reduction.
+
+ Whether the *Float* implementation actually reaches 0.0 at a mathematical
+ zero is libm-dependent — the audit below answers that empirically, and
+ rust-check/ re-checks every witness against the real generated Rust.
+
+ Rust referee (rust-check/, 2024-11, x86_64 glibc):
+ * 84 exact zeros on the full grid — 56 family A, 28 family B, 0 outside
+ the two predicted families (the exact model is confirmed complete).
+ * All four original Lean witnesses ((6,84,±180) etc.) are exact zeros
+ in Rust too — the two libms agree here.
+ * Pushing every witness through the real mac_x/mac_y yields NaN, never
+ ±inf: the zero denominator makes some factor inf but another factor
+ exactly 0 (sin 0 or sin ±π_float), and 0·inf = NaN poisons the sum.
+ So `project_point`'s NaN guard DOES filter all of them — the feared
+ "inf passes the guard" does NOT reproduce on this path.
+ * The residual hazard is NEAR-zero denominators instead: smallest
+ nonzero |denom| on the grid = 3.7e-33 (p=−90°, e=0°, dα=−90°), giving
+ finite coordinates ~1e32 px that pass every guard.
+-/
+
+/-- Full-domain grid: pitch, elev over [−90°, 90°] step 1°, Δα over
+ [−180°, 180°] step 2° — no symmetry reduction. sin/cos are precomputed
+ per axis so the inner loop is pure multiplication. -/
+def denomZerosFull : List (Float × Float × Float) :=
+ let ps := (List.range 181).map fun i =>
+ let p := degf (i.toFloat - 90); (p, Float.sin p, Float.cos p)
+ let es := (List.range 181).map fun j =>
+ let e := degf (j.toFloat - 90); (e, Float.sin e, Float.cos e)
+ let ds := (List.range 181).map fun k =>
+ let d := degf (k.toFloat * 2 - 180); (d, Float.cos d)
+ ps.foldl (init := ([] : List (Float × Float × Float))) fun acc (p, sp, cp) =>
+ es.foldl (init := acc) fun acc (e, se, ce) =>
+ ds.foldl (init := acc) fun acc (d, cd) =>
+ if cp * ce * cd + sp * se == 0 then acc ++ [(p, e, d)] else acc
+
+/-- Integer-degree pairs (p, e) in [−90, 90]² that the exact model says are
+ zeros of family A (p + e = ±90°) / family B (p − e = ±90°). -/
+def famAPairs : List (Int × Int) := Id.run do
+ let mut acc : List (Int × Int) := []
+ for i in List.range 181 do
+ for j in List.range 181 do
+ let p : Int := (i : Int) - 90
+ let e : Int := (j : Int) - 90
+ if Int.natAbs (p + e) == 90 then acc := acc ++ [(p, e)]
+ return acc
+
+def famBPairs : List (Int × Int) := Id.run do
+ let mut acc : List (Int × Int) := []
+ for i in List.range 181 do
+ for j in List.range 181 do
+ let p : Int := (i : Int) - 90
+ let e : Int := (j : Int) - 90
+ if Int.natAbs (p - e) == 90 then acc := acc ++ [(p, e)]
+ return acc
+
+/-- Of those mathematical zeros, which ones does THIS libm actually round to
+ exactly 0.0? (Compare with the Rust referee output.) -/
+def famAExact : List (Int × Int) :=
+ famAPairs.filter fun (p, e) => denom (degf p.toFloat) (degf e.toFloat) (degf 180) == 0
+
+def famBExact : List (Int × Int) :=
+ famBPairs.filter fun (p, e) => denom (degf p.toFloat) (degf e.toFloat) 0 == 0
+
+#eval "── Finding 2b: exact zeros on the full 181×181×181 grid (Lean's libm)"
+#eval denomZerosFull.length
+
+#eval "── Finding 2b: family A (math pairs, exact-Float pairs)"
+#eval (famAPairs.length, famAExact.length)
+
+#eval "── Finding 2b: family B (math pairs, exact-Float pairs)"
+#eval (famBPairs.length, famBExact.length)
+
+#eval "── Finding 2b: family B exact witnesses in Lean's libm (pitch, elev)"
+#eval famBExact
+
+-- ════════════════════════════════════════════════════════════════════════
+-- FINDING 3 — `mark_hidden`: 0/0 gives NaN, which passes both guards
+-- h = (elev_n − elev_m)/|α_m − α_n| ; guarded by is_infinite and `>`
+-- ════════════════════════════════════════════════════════════════════════
+
+def hideQuotient (elevM elevN alphM alphN : Float) : Float :=
+ (elevN - elevM) / (alphM - alphN).abs
+
+def finding3 : Float × Bool × String :=
+ let h := hideQuotient 0.5 0.5 0.3 0.3
+ (h, h.isNaN, if h > 1.2 then "hidden" else "not hidden")
+
+#eval "── Finding 3: (h, isNaN, guard verdict) — NaN ⇒ neither guard fires"
+#eval finding3
+
+-- ════════════════════════════════════════════════════════════════════════
+-- FINDING 4 — how far does `interp_cubic` overshoot? (caller must clamp)
+-- ════════════════════════════════════════════════════════════════════════
+
+def interpCubic (x x2 x3 v0 v1 v2 v3 : Float) : Float :=
+ let a0 := v3 - v2 - v0 + v1
+ let a1 := v0 - v1 - a0
+ let a2 := v2 - v0
+ let a3 := v1
+ a0 * x3 + a1 * x2 + a2 * x + a3
+
+def spikeOvershoot : List (Float × Float) :=
+ (List.range 101).foldl (init := []) fun acc i =>
+ let x := i.toFloat / 100
+ let v := interpCubic x (x * x) (x * x * x) 0 0 1 0
+ if v < 0 || v > 1 then acc ++ [(x, v)] else acc
+
+#eval "── Finding 4: bicubic single-spike samples outside [0,1] (caller must clamp)"
+#eval spikeOvershoot