Theorem 6 — a strictly self-complementary solution of (HLP) in predictor–corrector iterations
DisprovedSelfDualLP.Complexity.theorem_6Let (LP) and (LD) have integer data , , with and bit length . There is an absolute constant such that there is a finite predictor–corrector run under the choice (7) ending at an iteration
at which the termination projection has an output, and every termination output at , rescaled to the normalization (9), is a strictly self-complementary solution of (HLP).
That is, the predictor–corrector algorithm, coupled with the termination technique, generates a strictly self-complementary solution for (HLP) in iterations.
Formalization Note is pinned as with absolute, chosen before and the data. The algorithm is a relation on finite runs: a Newton solution and the attained predictor maximum are required for steps before the termination iterate. Existence of a successful finite run is asserted, so the theorem remains substantive when an infinite run cannot be extended. The hypothesis is implicit in the paper. The rescaling by is needed because the projection imposes only the homogeneous rows of (HLP).
import Mathlib import Definitions.Def_SelfDualLP_Complexity_LPData import Definitions.Def_SelfDualLP_Complexity_HLP import Definitions.Def_SelfDualLP_Complexity_Neighborhood import Definitions.Def_SelfDualLP_Complexity_PCSequence import Definitions.Def_SelfDualLP_Complexity_Termination import Definitions.Def_SelfDualLP_Complexity_BitLength open Matrix
namespace SelfDualLP.Complexity
/-- Theorem 6 (p. 61), with `O(√n L)` pinned as `C·√n·L` for an absolute constant `C > 0`. Let
(LP) and (LD) have integer data `(A, b, c)` with `n ≥ 1` and bit length `L`. For every sequence of
iterates of the predictor–corrector algorithm applied to (HLP) under (7), there is a finite
run ending at iteration `k ≤ C√n L` at which the termination projection has an output, and every termination
output at `zᵏ`, rescaled to (9), is a strictly self-complementary solution of (HLP). -/
theorem theorem_6 :
∃ C : ℝ, 0 < C ∧ ∀ (m n : ℕ), 1 ≤ n →
∀ (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ) (c : Fin n → ℤ),
∃ (k : ℕ) (z : ℕ → HLPPoint m n),
IsPCSequence (castMat A) (castVec b) (castVec c) z k ∧
(k : ℝ) ≤ C * Real.sqrt (n : ℝ) * (bitLength A b c : ℝ) ∧
(∃ u, IsTerminationOutput (castMat A) (castVec b) (castVec c) (z k) u) ∧
∀ u, IsTerminationOutput (castMat A) (castVec b) (castVec c) (z k) u →
StrictlySelfComplementary7 (castMat A) (castVec b) (castVec c) (rescaleOutput u) := by sorry
end SelfDualLP.Complexity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.