Theorem 1.2 — conditional rank and invertibility reductions
OpenZamirInversion581.Mult.Supplement.theorem_1_2Fix a finite field and a trapdoored-matrix family as in §3.1. There are and , depending only on this field and family, with the following property. Let and let be one polynomial-time field-RAM program whose every run on an input takes at most field operations. Assume, for every sufficiently large , either of the following alternatives (one alternative holds throughout those dimensions):
- Its invertibility-bit success on a uniform matrix is at least , where is the singularity probability.
- Its exact-rank success on a uniform matrix is at least .
For each there are finite programs for worst-case invertibility and exact rank, with dimension thresholds, such that on every matrix above the corresponding threshold all runs halt within the respective bounds
and their correct-output probabilities are at least . Here and . The constants precede ; the programs and thresholds may depend on them. No monotonicity of is assumed.
This companion theorem establishes both worst-case consequences from either advantage over the best constant predictor.
Differences from the source:
- reading: algorithms and running times count field operations → one finite oracle-free randomized field-RAM program, with all supported runs bounded; reason: the source specifies field operations on p.11; one common model makes the polynomial-time pseudorandomness hypothesis applicable
- reading: asymptotic Õ_q(ε⁻²(T(n)+n²)) and rank cost at 2n → c ε⁻²(T(n)+n²) log(2nEK)^a and the corresponding T(2n) bound, with c,a after the field and family but before ε,A,T,κ; reason: explicit uniform constants and dimension thresholds express the asymptotic statement without adding conditions on T
- reading: with high probability → each failure target 0<κ≤1/2, with K=ceil(1/κ) supplied as an index input; reason: pp.17–18 give logarithmic statistical amplification; inverse-polynomial failure is included
- encoding: uniform n by n matrices and bit or rank answers → Fin n rows and columns, integer bits 0/1 and integer ranks, with all other outputs incorrect; reason: these are the same finite objects and success events
- reading: hypothesis (i) or (ii) at dimension n, range of n unstated → (i) for every n ≥ N₀, or (ii) for every n ≥ N₀; reason: this is the stronger of the two readings (it is implied by the every-n reading), matching the base goal's 'for all sufficiently large m'; the Õ conclusions are asymptotic and are claimed for n ≥ n₀
- reading: a trapdoored-matrix family of samplers indexed by n with Õ(n²) sampling and Õ(n) action (p.11) → one sampler program and one action program of the field RAM taking n as input, with constants C, b of the family, and c, a allowed to depend on the family; reason: the reductions are uniform algorithms that draw trapdoored matrices at every dimension (pp.17–19), and the polylogarithmic exponents of the family enter the Õ_q bound
import Mathlib import Definitions.Def_ZamirInversion581_Mult_Supplement_Reductions set_option autoImplicit false
namespace ZamirInversion581.Mult.Supplement
/-- Theorem 1.2, p.3. Constants may depend only on the fixed field and trapdoor family.
Both alternative average-case hypotheses and both worst-case conclusions are retained. -/
theorem theorem_1_2 (F : Type*) [Field F] [Fintype F] [DecidableEq F]
(𝒯 : TrapdoorPrograms F) (h𝒯 : IsTrapdoored 𝒯) :
∃ (c : ℝ) (a : ℕ), 0 < c ∧
∀ (ε : ℝ), 0 < ε → ∀ (A : Program F) (T : ℕ → NNReal) (N₀ : ℕ),
PolyTime A → TimeBound A T → AboveBaseline A ε N₀ →
∀ κ : ℝ, 0 < κ → κ ≤ 1 / 2 → RankAndInvertibility (F := F) c a ε κ T := by sorry
end ZamirInversion581.Mult.Supplement