view_obstruction_offset_le_ray_dist
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.
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.
uses
le_ciInfhaveI : 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
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.
have hneg : int_to_euclidean n (fun i => -z i) = - int_to_euclidean n z := by ext i simp [int_to_euclidean]
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).
uses
map_sub,map_smul,orthogonalProjectionOnto_apply_of_mem_orthogonal,smul_zero,zero_subhave 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]
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).
uses
sub_neg_eq_add,ciInf_le,sq_nonneghave 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 _⟩ _
‖π_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₀).
uses
norm_neg,pow_le_pow_left₀,norm_nonneg,norm_orthogonalProjectionOnto_apply_lehave 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
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.
uses
le_transexact 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.
- In finite-dimensional Euclidean space, every subspace admits an orthogonal projection; line 7 infers this instance (U.HasOrthogonalProjection) so the projection operator can be formed.
- In Step 4 (line 29), Lean requires an explicit proof that the set of squared norms is bounded below by 0 before applying the infimum bound ciInf_le.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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