Proposition 1, p. 6 — Algorithm 1 halts with a partial-support solution, J = J(L) when σ ≤ σ(L) (corrected: ≤ n(⌊log₂(1/σ)⌋ + 1) rescalings; J_σ(L) ⊆ J only for σ ≤ σ(L))
ProvedProjRescale.MaxSupport.proposition_1Let , let be a linear subspace and let . Consider Algorithm 1 (Partial support) on input , with any admissible behaviour of the basic procedure and any choice of the maximizer in step 5. Then:
- (progress) every non-halted state reachable by the algorithm has an admissible next step;
- (termination) there is no infinite execution;
- (rescaling count) every execution performs at most
rescaling steps; 4. (partial support) whenever the algorithm halts with output , we have , for every , and ; 5. (maximum support for a small guess) if , then every output has , and the number of rescaling steps of that execution satisfies
This is the analysis of Algorithm 1 that Theorem 1 runs twice in each main iteration of Algorithm 2.
Formalization Note Algorithm 1 is the transition relation A1Step L σ started at A1Init n (, ); every statement quantifies over all executions. The counter rescalings of a state is the number of rescaling steps performed so far; clause 3 bounds it at every reachable state. and are Nat.floor and Nat.ceil, whose arguments here are .
Differences from the source:
- correction: the right-hand side of (5), → ; reason: an index is trimmed once , i.e. after rescalings; counterexample , , : forces twice (: ), 2 rescaling steps, while (5) gives .
- correction: "for some in at most rescaling steps" for every → for every , and with the count when (where , p. 5); reason: for an index of can be trimmed; counterexample , , , : the admissible answers trim index 2, then forces twice, and the run ends with , after 4 rescaling steps (the printed bound gives 1).
- encoding: implicit → hypothesis ; reason: for , and Algorithm 1 cannot run, so the case is undefined on the page.
- encoding: "Algorithm 1 finds … in at most … rescaling steps" → progress, no infinite execution, and the bound at every reachable state of the transition relation, over every admissible answer of the basic procedure; reason: the basic procedure is any procedure satisfying step 3, so the claim is about every execution.
import Mathlib import Definitions.Def_ProjRescale_MaxSupport_Setting
namespace ProjRescale.MaxSupport
/-- Proposition 1, p. 6, corrected. For `σ ∈ (0, 1)`, every execution of Algorithm 1 on `(L, σ)`
can always continue until it halts, no execution is infinite, every execution performs at most
`n(⌊log₂(1/σ)⌋ + 1)` rescaling steps, and on halting it outputs `x ∈ L ∩ ℝⁿ₊` with `x_J > 0` for
some `J ⊆ J(L)`. If moreover `σ ≤ σ(L)`, then `J = J(L)` and the number of rescaling steps is at most
`∑_{i ∈ J(L)} ⌈log₂(1/σ_i(L))⌉ + (n − |J(L)|)(⌊log₂(1/σ)⌋ + 1)`. -/
theorem proposition_1 (n : ℕ) (hn : 0 < n) (L : Submodule ℝ (E n)) (σ : ℝ)
(hσ0 : 0 < σ) (hσ1 : σ < 1) :
(∀ s, Relation.ReflTransGen (A1Step L σ) (A1Init n) s → s.IsRun →
∃ s', A1Step L σ s s') ∧
(¬ ∃ f : ℕ → A1State n, f 0 = A1Init n ∧ ∀ t, A1Step L σ (f t) (f (t + 1))) ∧
(∀ s, Relation.ReflTransGen (A1Step L σ) (A1Init n) s →
s.rescalings ≤ n * (⌊Real.logb 2 (1 / σ)⌋₊ + 1)) ∧
(∀ x J r, A1Halts L σ x J r →
x ∈ L ∧ x ∈ nonneg n ∧ (∀ j ∈ J, 0 < x j) ∧ J ⊆ maxSupp L) ∧
(σ ≤ condMeasure L → ∀ x J r, A1Halts L σ x J r →
J = maxSupp L ∧
r ≤ ∑ j ∈ maxSupp L, ⌈Real.logb 2 (1 / sigmaI L j)⌉₊ +
(n - (maxSupp L).card) * (⌊Real.logb 2 (1 / σ)⌋₊ + 1)) := by sorry
end ProjRescale.MaxSupport
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.