Corollary 6.8 — tree-incidence transport: integral with
ProvedInfoLossLAR.WorstCase.corollary_6_8determinantincidence-matrixlatticesp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an odd prime, and the matrix of Definition 6.3. Let be any oriented spanning tree on , , and with . Define
Let with , and set , . Then , and ; consequently and , with
Every gives and . If , then .
Differences from the source:
- encoding: the column order of (edges, then ) → an arbitrary bijection from (edges one extra column) to , with reindexed by the same on rows and columns; reason: the paper does not order the edges; is the paper's matrix with columns permuted, and every clause is invariant
- encoding: → indexed by the edge set; reason: its rows and columns are the edge coordinates
- encoding: ", " → there are integer whose casts are the rational , and invertibility mod is stated for ; reason: is taken over
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_Rounding import Definitions.Def_InfoLossLAR_WorstCase_FixedT set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Corollary 6.8 (General tree-incidence transport), p. 29. `q` an odd prime, `d ≥ q`, `T` of
Definition 6.3, `𝒯` any oriented spanning tree on `Fin d`, `R_edge ∈ ℤ^{(d−1)×(d−1)}` (indexed
by the edges), `v ∈ ℤ^d` with `1ᵀv = q`, `z_0 ∈ ℤ^d` with `1ᵀz_0 ≡ 0 (mod q)`; the `d` columns
are ordered by `σ` (edges, then the extra column). With `D̄_𝒯 = [D_𝒯 | v]`,
`R̄ = diag(R_edge, 1)`, `D_T = D̄_𝒯 R̄`, `Q = T^{-1} D_T` and `β = T^{-1} z_0` (over `ℚ`):
`|det D̄_𝒯| = q`, `D_T ℤ^d ⊆ L(T)`, `z_0 ∈ L(T)`, `Q` and `β` are integral,
`det D_T = ±q det R_edge`, `det Q = det D̄_𝒯 det R̄ / det T = ±det R_edge`, every `x ∈ ℤ^d`
gives `w = D̄_𝒯 R̄ x + z_0 ∈ L(T)` with `w mod q ∈ H_0`, and if `det R_edge ≢ 0 (mod q)` then
`Q mod q ∈ GL_d(𝔽_q)`. -/
theorem corollary_6_8 (q d : ℕ) (hq : q.Prime) (hq2 : q ≠ 2) (hdq : q ≤ d)
(𝒯 : OrientedTree d) (Redge : Matrix 𝒯.G.edgeSet 𝒯.G.edgeSet ℤ)
(v : Fin d → ℤ) (hv : ∑ i, v i = (q : ℤ))
(z₀ : Fin d → ℤ) (hz₀ : (q : ℤ) ∣ ∑ i, z₀ i)
(σ : 𝒯.G.edgeSet ⊕ Unit ≃ Fin d) :
let Dbar : Matrix (Fin d) (Fin d) ℤ := (𝒯.extended v).submatrix id σ.symm
let Rbar : Matrix (Fin d) (Fin d) ℤ :=
(Matrix.fromBlocks Redge 0 0 (1 : Matrix Unit Unit ℤ)).submatrix σ.symm σ.symm
let DT : Matrix (Fin d) (Fin d) ℤ := Dbar * Rbar
let Q : Matrix (Fin d) (Fin d) ℚ := TinvQ q d * DT.map (Int.cast : ℤ → ℚ)
let β : Fin d → ℚ := (TinvQ q d).mulVec (fun i => (z₀ i : ℚ))
|Dbar.det| = (q : ℤ) ∧
(∀ x : Fin d → ℤ, DT.mulVec x ∈ imageLattice (TDef63 q d)) ∧
z₀ ∈ imageLattice (TDef63 q d) ∧
(DT.det = (q : ℤ) * Redge.det ∨ DT.det = -((q : ℤ) * Redge.det)) ∧
Q.det = ((Dbar.det * Rbar.det : ℤ) : ℚ) / (((TDef63 q d).det : ℤ) : ℚ) ∧
(Q.det = (Redge.det : ℚ) ∨ Q.det = -(Redge.det : ℚ)) ∧
(∃ Qz : Matrix (Fin d) (Fin d) ℤ, Qz.map (Int.cast : ℤ → ℚ) = Q ∧
(¬ (q : ℤ) ∣ Redge.det → IsUnit (matModq q Qz).det)) ∧
(∃ βz : Fin d → ℤ, (fun i => (βz i : ℚ)) = β) ∧
(∀ x : Fin d → ℤ, DT.mulVec x + z₀ ∈ imageLattice (TDef63 q d) ∧
modq q (DT.mulVec x + z₀) ∈ H0 q d) := 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. 29, Corollary 6.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.