Lemma 6.2 — the incidence matrix of an oriented tree is an integral basis of
ProvedInfoLossLAR.WorstCase.lemma_6_2graph-theoryincidence-matrixlatticesp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a tree on the vertex set with an arbitrary orientation and signed incidence matrix ( at the tail, at the head of each edge column). Then has edges, and the columns of form an integral basis of the zero-sum lattice : they are linearly independent over and span . In particular
Differences from the source:
- encoding: "a tree on vertices with an arbitrary orientation" → a
SimpleGraphonFin dwithIsTreeand a tail/head choice for each edge; reason: same objects - encoding: "integral basis" → -linear independence plus span equal to ; reason: definition of a basis
- encoding: columns indexed → columns indexed by the edge set; reason: the paper's order of edges is arbitrary
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding import Definitions.Def_InfoLossLAR_WorstCase_FixedT set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 6.2 (Tree incidence basis), p. 26: an oriented tree `𝒯` on the `d` vertices `Fin d`
has `d − 1` edges, and the columns of its signed incidence matrix `D_𝒯` form an integral basis
of `A_{d−1} = {z ∈ ℤ^d : 1ᵀz = 0}`: they are `ℤ`-linearly independent and span `A_{d−1}`; in
particular `D_𝒯 ℤ^{d−1} = A_{d−1}` and `rank_ℝ(D_𝒯) = d − 1`. -/
theorem lemma_6_2 (d : ℕ) (𝒯 : OrientedTree d) :
Fintype.card 𝒯.G.edgeSet = d - 1 ∧
LinearIndependent ℤ (fun e : 𝒯.G.edgeSet => fun i : Fin d => 𝒯.incidence i e) ∧
Submodule.span ℤ (Set.range fun e : 𝒯.G.edgeSet => fun i : Fin d => 𝒯.incidence i e) =
zeroSumLattice d ∧
LinearMap.range (Matrix.mulVecLin 𝒯.incidence) = zeroSumLattice d ∧
(𝒯.incidence.map (Int.cast : ℤ → ℝ)).rank = d - 1 := by sorry
end InfoLossLAR.WorstCase
Source
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, arXiv:2611.05136 (held version, sha256 2ebdfbf3…), p. 26, Lemma 6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.