Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5.2 — three-bit rank gain: at most three of the eight maps C+∑εiBiC+\sum\varepsilon_iB_iC+∑εi​Bi​ have rank below r/4r/4r/4 (odd characteristic)

Proved
AlgCoverage.OddOrder.three_bit_rank_gain

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-matrices

Let FFF be a field of odd characteristic, WWW a finite-dimensional FFF-vector space, C:W→FdC:W\to F^dC:W→Fd a linear map and B1,B2,B3:W→FdB_1,B_2,B_3:W\to F^dB1​,B2​,B3​:W→Fd linear maps of rank at least rrr. For ε∈{0,1}3\varepsilon\in\{0,1\}^3ε∈{0,1}3 put Vε=C+ε1B1+ε2B2+ε3B3V_\varepsilon=C+\varepsilon_1B_1+\varepsilon_2B_2+\varepsilon_3B_3Vε​=C+ε1​B1​+ε2​B2​+ε3​B3​. Then at most three of the eight maps VεV_\varepsilonVε​ have rank strictly below r/4r/4r/4:

#{ε∈{0,1}3:rank⁡Vε<r/4}≤3.\#\{\varepsilon\in\{0,1\}^3 : \operatorname{rank}V_\varepsilon<r/4\}\le3 .#{ε∈{0,1}3:rankVε​<r/4}≤3.

Consequently, for uniform fresh bits ε\varepsilonε, the new kernel ker⁡Vε⊆W\ker V_\varepsilon\subseteq WkerVε​⊆W loses at least r/4r/4r/4 dimensions with probability at least 5/85/85/8:

#{ε:dim⁡W−dim⁡ker⁡Vε≥r/4}8≥58.\frac{\#\{\varepsilon : \dim W-\dim\ker V_\varepsilon\ge r/4\}}{8}\ge\frac58 .8#{ε:dimW−dimkerVε​≥r/4}​≥85​.

In the paper WWW is the current left kernel, BaB_aBa​ is the contribution of row aaa to the next constraint, and CCC 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
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me