Corollary 1, p. 7 — if 𝒥(L, σ) and 𝒥(L⊥, σ) return index sets covering {1, …, n}, they are J(L), J(L⊥) and the outputs are maximum support points
ProvedProjRescale.MaxSupport.corollary_1Let be a linear subspace and . Suppose Algorithm 1 on input outputs and Algorithm 1 on input outputs , and that
Then , , is a maximum support point of and is a maximum support point of (a point of the cone whose support is the maximum support index set).
This is the stopping test of Algorithm 2: the covering condition, which the algorithm can check, certifies maximum support without knowing or .
Formalization Note "" is A1Halts L σ x J r: some execution of Algorithm 1 on , with any admissible behaviour of the basic procedure, halts with output after rescaling steps. Since the conclusion is drawn for every such pair of executions, it covers every implementation of the basic procedure.
Differences from the source:
- encoding: ", the output of Algorithm 1" → some execution of the transition relation
A1Step L σhalts with output , for any admissible basic-procedure answers; reason: the basic procedure is any procedure satisfying step 3, so every execution's output is an output of Algorithm 1. - reading: the corollary assumes , while is introduced (p. 7) and Algorithm 1 is stated (p. 6) for → hypothesis , with Algorithm 1's transition relation defined for every real ; reason: the page is ambiguous between the two ranges and the Lean takes the corollary's own, wider hypothesis (never the weaker reading); for it is exactly the paper's statement.
import Mathlib import Definitions.Def_ProjRescale_MaxSupport_Setting
namespace ProjRescale.MaxSupport
/-- Corollary 1, p. 7. Let `σ > 0`. If `(x, J) = 𝒥(L, σ)` and `(x̂, Ĵ) = 𝒥(L⊥, σ)` satisfy
`J ∪ Ĵ = {1, …, n}`, then `J = J(L)`, `Ĵ = J(L⊥)`, and `x`, `x̂` are maximum support points of
`L ∩ ℝⁿ₊` and `L⊥ ∩ ℝⁿ₊`. -/
theorem corollary_1 {n : ℕ} (L : Submodule ℝ (E n)) (σ : ℝ) (hσ : 0 < σ)
(x xh : E n) (J Jh : Finset (Fin n)) (r rh : ℕ)
(hx : A1Halts L σ x J r) (hxh : A1Halts Lᗮ σ xh Jh rh) (hcov : J ∪ Jh = Finset.univ) :
J = maxSupp L ∧ Jh = maxSupp Lᗮ ∧ IsMaxSupportPoint L x ∧ IsMaxSupportPoint Lᗮ xh := by sorry
end ProjRescale.MaxSupport
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.