§5.2 — three-bit rank gain: at most three of the eight maps have rank below (odd characteristic)
ProvedAlgCoverage.OddOrder.three_bit_rank_gainlinear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-matrices
Let be a field of odd characteristic, a finite-dimensional -vector space, a linear map and linear maps of rank at least . For put . Then at most three of the eight maps have rank strictly below :
Consequently, for uniform fresh bits , the new kernel loses at least dimensions with probability at least :
In the paper is the current left kernel, is the contribution of row to the next constraint, and collects the other fresh bits; this rank gain drives the scalar dependency bound (Lemma 5.2).
Differences from the source:
- generalization: W the current kernel, B_a the contributions of three rows (kernels {α : α_a = 0}) and C the contribution of the other fixed bits → W any finite-dimensional F-vector space and C, B₁, B₂, B₃ any linear maps W → F^d with rank B_i ≥ r; reason: the claim uses only the ranks; the source's maps are a special case
- encoding: field F of odd characteristic → Odd (ringChar F); reason: the characteristic of a field is 0 or a prime; Odd excludes 0 and 2, leaving exactly the odd primes
- encoding: with probability at least 5/8 over the three fresh fair bits, the kernel loses at least r/4 dimensions → #{ε ∈ {0,1}³ : dim W − dim ker V_ε ≥ r/4}/8 ≥ 5/8; reason: fresh fair bits are uniform on {0,1}³, and the next kernel is ker V_ε ⊆ W
- encoding: ranks compared with r/4 → Module.finrank of the range, compared in ℝ with r/4; reason: r/4 need not be an integer
Preamble
import Mathlib
Formal statement
namespace AlgCoverage.OddOrder
/-- §5.2 (three-bit rank gain), Lin, printed p. 19 / PDF 20. Over a field of odd characteristic, let
`B₁, B₂, B₃ : W → F^d` be linear maps of rank at least `r` and `C : W → F^d` any linear map. Among the
eight maps `V_ε = C + ε₁B₁ + ε₂B₂ + ε₃B₃`, `ε ∈ {0,1}³`, at most three have rank strictly below `r/4`;
consequently, for uniform fresh bits `ε`, the kernel `ker V_ε ⊆ W` has at least `r/4` fewer dimensions
than `W` with probability at least `5/8`. -/
theorem three_bit_rank_gain {F : Type*} [Field F] (hF : Odd (ringChar F))
{W : Type*} [AddCommGroup W] [Module F W] [FiniteDimensional F W] (d r : ℕ)
(C : W →ₗ[F] (Fin d → F)) (B : Fin 3 → W →ₗ[F] (Fin d → F))
(hB : ∀ i, r ≤ Module.finrank F (LinearMap.range (B i))) :
Nat.card {ε : Fin 3 → Bool //
(Module.finrank F (LinearMap.range (C + ∑ i, if ε i then B i else 0)) : ℝ) < (r : ℝ) / 4}
≤ 3 ∧
(5 : ℝ) / 8 ≤
(Nat.card {ε : Fin 3 → Bool //
(r : ℝ) / 4 ≤ (Module.finrank F W : ℝ) -
Module.finrank F (LinearMap.ker (C + ∑ i, if ε i then B i else 0))} : ℝ) / 8 := by sorry
end AlgCoverage.OddOrder
Source
Lin, Sharp Second-Order Thresholds for Random Algebraic Coverage, STOC 2027 submission (manuscript sha256 9db96430…), p. 19 (PDF 20), §5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.