Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 25 — exact composition under independent concatenation

Proved
SpaceReset.Hardness.proposition_25

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1trellis

Let Gi∈F2ki×niG_i\in\mathbb F_2^{k_i\times n_i}Gi​∈F2ki​×ni​​, i=1,…,mi=1,\dots,mi=1,…,m, be ordered sources of full row rank kik_iki​ with invariants (ci,Πi)(c_i,\Pi_i)(ci​,Πi​). Their direct-sum code, in that block order, satisfies

c=max⁡ici,Π=max⁡{∑iki, max⁡iΠi}.c=\max_ic_i,\qquad \Pi=\max\Big\{\sum_ik_i,\ \max_i\Pi_i\Big\}.c=imax​ci​,Π=max{i∑​ki​, imax​Πi​}.

Appending an independent coordinate to a source therefore leaves ccc unchanged and raises Π\PiΠ only up to the total rank; Theorem 2's yes case uses this.

Differences from the source:

  • encoding: maxima over an index set of blocks → Finset.sup over Fin m (value 0 for m = 0); reason: the empty family has c = Π = 0, which the formula gives
Preamble
import Mathlib
import Definitions.Def_SpaceReset_Hardness_Trellis

set_option autoImplicit false
Formal statement
namespace SpaceReset.Hardness

/-- Proposition 25 (Exact composition under independent concatenation), App. B.1, p. 38. -/
theorem proposition_25 {m : ℕ} {k n : Fin m → ℕ}
    (G : (i : Fin m) → Matrix (Fin (k i)) (Fin (n i)) F2) (hG : ∀ i, FullRowRank (G i)) :
    cInv (directSum G) = Finset.univ.sup (fun i => cInv (G i)) ∧
    PiInv (directSum G) = max (∑ i, k i) (Finset.univ.sup (fun i => PiInv (G i))) := by sorry

end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), Proposition 25, App. B.1, p. 38
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 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