AFTD Auto-Formalizing Theoretical Domains

view_obstruction_offset_le_ray_dist

theoremverifiedformalization

Offset lower bound: for any linear subspace U ⊆ ℝ^n and any integer direction vector v ∈ ℤ^n orthogonal to U (v ∈ U^⊥), the view-obstruction squared distance d_n(v) is at least the offset δ_U^2 of U.

Statement

open Submodule in
theorem view_obstruction_offset_le_ray_dist
    (n : ℕ) (U : Submodule ℝ (EuclideanSpace ℝ (Fin n))) (v : Fin n → ℤ)
    (hv : int_to_euclidean n v ∈ Uᗮ) :
    view_obstruction_offset n U ≤ view_obstruction_ray_dist n v
Formalizes
arXiv:2610.37711 Lemma 3.2
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • view_obstruction_offsetThe offset δ_U^2 of a linear subspace U in ℝ^n, defined as the infimum over integer vectors z ∈ ℤ^n of the squared norm of the orthogonal…
  • view_obstruction_ray_distThe view-obstruction squared distance d_n(v) for an integer direction vector v, defined as the infimum over t ∈ ℝ of the squared distance…
  • int_to_euclideanThe canonical embedding of an integer vector z ∈ ℤ^n into the Euclidean space ℝ^n.
  • view_obstruction_centerThe center point c = (1/2, ..., 1/2) of the shifted lattice in Euclidean space ℝ^n.

Read back from the Lean

For any natural number $n$, any $\mathbb{R}$-submodule $U$ of $\mathbb{R}^n$ (equipped with the Euclidean inner product, i.e., EuclideanSpace ℝ (Fin n)), and any integer vector $v \in \mathbb{Z}^n$ (represented as Fin n → ℤ), if the image of $v$ under the canonical map into Euclidean space belongs to the orthogonal complement $U^\perp$, then view_obstruction_offset n U is less than or equal to view_obstruction_ray_dist n v.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that the offset δ_U^2 is a lower bound for the ray distance d_n(v) = ⨅_{t, z} ‖t v - (c + z)‖^2, it suffices to prove δ_U^2 ≤ ‖t v - (c + z)‖^2 for arbitrary t ∈ ℝ and z ∈ ℤ^n. Because v is orthogonal to U, projecting t v - (c + z) onto U annihilates the t v term, giving ‖π_U(t v - (c + z))‖ = ‖π_U(c + z)‖. Since orthogonal projections are non-expansive, this norm squared is bounded above by ‖t v - (c + z)‖^2. Finally, rewriting c + z = c - (-z) shows that ‖π_U(c + z)‖^2 is a member of the family defining the infimum δ_U^2, completing the chain δ_U^2 ≤ ‖π_U(c + z)‖^2 ≤ ‖t v - (c + z)‖^2.

  1. To bound the ray distance from below, it suffices to show that δ_U^2 ≤ ‖t • v - (c + z)‖^2 for arbitrary t ∈ ℝ and z ∈ ℤ^n.

    We synthesize the orthogonal projection instance on U and unfold the definitions of view_obstruction_offset and view_obstruction_ray_dist. Because the ray distance is defined as the infimum over t ∈ ℝ and z ∈ ℤ^n, bounding the infimum from below reduces (via le_ciInf) to proving the lower bound for an arbitrary fixed t ∈ ℝ and z ∈ ℤ^n. We fix t and z, denoting their Euclidean embeddings by vE and zE and the center point (1/2, ..., 1/2) by c.

    lines 7–15

    uses le_ciInf

      haveI : U.HasOrthogonalProjection := inferInstance
      simp only [view_obstruction_offset, view_obstruction_ray_dist]
      set c := view_obstruction_center n
      apply le_ciInf
      intro t
      apply le_ciInf
      intro z
      set vE := int_to_euclidean n v
      set zE := int_to_euclidean n z
  2. The Euclidean embedding of the negated integer vector -z equals -zE.

    The embedding int_to_euclidean maps integer tuples to Euclidean space componentwise by casting integers to real numbers. Since integer negation commutes with real negation on each coordinate, the embedding of -z is -zE.

    lines 16–18

      have hneg : int_to_euclidean n (fun i => -z i) = - int_to_euclidean n z := by
        ext i
        simp [int_to_euclidean]
  3. The orthogonal projection of t • vE - (c + zE) onto U simplifies to -π_U(c + zE).

    By linearity of the orthogonal projection (map_sub, map_smul), π_U(t • vE - (c + zE)) = t • π_U(vE) - π_U(c + zE). Since vE ∈ Uᗮ by assumption, π_U(vE) = 0 (orthogonalProjectionOnto_apply_of_mem_orthogonal), leaving 0 - π_U(c + zE) = -π_U(c + zE).

    lines 19–22

    uses map_sub, map_smul, orthogonalProjectionOnto_apply_of_mem_orthogonal, smul_zero, zero_sub

      have hproj : U.orthogonalProjectionOnto (t • vE - (c + zE)) =
          - U.orthogonalProjectionOnto (c + zE) := by
        rw [map_sub, map_smul, orthogonalProjectionOnto_apply_of_mem_orthogonal hv, smul_zero,
          zero_sub]
  4. The offset δ_U^2 is at most ‖π_U(c + zE)‖^2.

    Writing c + zE = c - (-zE), the quantity ‖π_U(c + zE)‖^2 equals ‖π_U(c - int_to_euclidean(-z))‖^2, which is an element of the family over which the offset infimum is taken. Because squared norms are non-negative (sq_nonneg), the set is bounded below by 0, so the infimum δ_U^2 is at most this value (ciInf_le).

    lines 23–29

    uses sub_neg_eq_add, ciInf_le, sq_nonneg

      have hδ : view_obstruction_offset n U ≤ ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 := by
        have key : ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 =
            ‖U.orthogonalProjectionOnto (c - int_to_euclidean n (fun i => -z i))‖ ^ 2 := by
          rw [hneg, sub_neg_eq_add]
        rw [key]
        simp only [view_obstruction_offset]
        exact ciInf_le ⟨0, by rintro _ ⟨w, rfl⟩; exact sq_nonneg _⟩ _
  5. ‖π_U(c + zE)‖^2 ≤ ‖t • vE - (c + zE)‖^2.

    Using the identity from Step 3 and norm_neg, we have ‖π_U(c + zE)‖ = ‖π_U(t • vE - (c + zE))‖. Because orthogonal projection does not increase norm (norm_orthogonalProjectionOnto_apply_le), this is at most ‖t • vE - (c + zE)‖. Squaring both sides preserves the inequality (pow_le_pow_left₀).

    lines 30–36

    uses norm_neg, pow_le_pow_left₀, norm_nonneg, norm_orthogonalProjectionOnto_apply_le

      have hle : ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 ≤
          ‖t • vE - (c + zE)‖ ^ 2 := by
        have h1 : ‖U.orthogonalProjectionOnto (c + zE)‖ =
            ‖U.orthogonalProjectionOnto (t • vE - (c + zE))‖ := by
          rw [hproj, norm_neg]
        rw [h1]
        exact pow_le_pow_left₀ (norm_nonneg _) (U.norm_orthogonalProjectionOnto_apply_le _) 2
  6. The offset δ_U^2 is bounded above by ‖t • vE - (c + zE)‖^2, concluding the theorem.

    Chaining the inequalities δ_U^2 ≤ ‖π_U(c + zE)‖^2 and ‖π_U(c + zE)‖^2 ≤ ‖t • vE - (c + zE)‖^2 by transitivity (le_trans) establishes the lower bound for all t and z, completing the proof.

    line 37

    uses le_trans

      exact le_trans hδ hle
le_ciInf
A value c is a lower bound for an infimum if it is bounded above by each element of the family.
map_sub
An additive group homomorphism respects subtraction: f(a - b) = f(a) - f(b).
map_smul
A module homomorphism respects scalar multiplication: f(c • x) = c • f(x).
orthogonalProjectionOnto_apply_of_mem_orthogonal
The orthogonal projection of any vector in the orthogonal complement Uᗮ onto U is zero.
smul_zero
Multiplying zero by any scalar yields zero: a • 0 = 0.
zero_sub
Subtracting an element from zero gives its negation: 0 - a = -a.
sub_neg_eq_add
Subtracting a negation is equivalent to addition: a - (-b) = a + b.
ciInf_le
For any set bounded below, its infimum is less than or equal to any element in the set.
sq_nonneg
The square of any real number is non-negative: 0 ≤ a^2.
norm_neg
The norm of a vector equals the norm of its negation: ‖-a‖ = ‖a‖.
pow_le_pow_left₀
For non-negative numbers, a ≤ b implies a^n ≤ b^n.
norm_nonneg
The norm of any vector is non-negative: 0 ≤ ‖a‖.
norm_orthogonalProjectionOnto_apply_le
Orthogonal projection onto a subspace is non-expansive: ‖π_U(v)‖ ≤ ‖v‖.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Submodule in/-- Lemma 3.2: the offset δ_U^2 is a lower bound for d_n(v) whenever v ∈ U^⊥. -/theorem view_obstruction_offset_le_ray_dist    (n : ℕ) (U : Submodule ℝ (EuclideanSpace ℝ (Fin n))) (v : Fin n → ℤ)    (hv : int_to_euclidean n v ∈ Uᗮ) :    view_obstruction_offset n U ≤ view_obstruction_ray_dist n v := by  haveI : U.HasOrthogonalProjection := inferInstance  simp only [view_obstruction_offset, view_obstruction_ray_dist]  set c := view_obstruction_center n  apply le_ciInf  intro t  apply le_ciInf  intro z  set vE := int_to_euclidean n v  set zE := int_to_euclidean n z  have hneg : int_to_euclidean n (fun i => -z i) = - int_to_euclidean n z := by    ext i    simp [int_to_euclidean]  have hproj : U.orthogonalProjectionOnto (t • vE - (c + zE)) =      - U.orthogonalProjectionOnto (c + zE) := by    rw [map_sub, map_smul, orthogonalProjectionOnto_apply_of_mem_orthogonal hv, smul_zero,      zero_sub]  have hδ : view_obstruction_offset n U ≤ ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 := by    have key : ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 =        ‖U.orthogonalProjectionOnto (c - int_to_euclidean n (fun i => -z i))‖ ^ 2 := by      rw [hneg, sub_neg_eq_add]    rw [key]    simp only [view_obstruction_offset]    exact ciInf_le ⟨0, by rintro _ ⟨w, rfl⟩; exact sq_nonneg _⟩ _  have hle : ‖U.orthogonalProjectionOnto (c + zE)‖ ^ 2 ≤      ‖t • vE - (c + zE)‖ ^ 2 := by    have h1 : ‖U.orthogonalProjectionOnto (c + zE)‖ =        ‖U.orthogonalProjectionOnto (t • vE - (c + zE))‖ := by      rw [hproj, norm_neg]    rw [h1]    exact pow_le_pow_left₀ (norm_nonneg _) (U.norm_orthogonalProjectionOnto_apply_le _) 2  exact le_trans hδ hle
See it in the graphDiscuss this resultChallenge it