g_expansion
Expansion of the operator count $g(S,M)$. Fix a prime $p$ and equip $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ with the symplectic form $\omega\big((x,z),(x',z')\big) = \sum_{i=0}^{n-1}\big(x_i z'_i - z_i x'_i\big)$. For a set of coordinates $M \subseteq \{0,\dots,n-1\}$, let $V_M \le V$ be the subspace of vectors supported on $M$, and for a subspace $W \le V$ write $W_M = W \cap V_M$. Let $S \le V$ be isotropic, meaning $\omega(u,v) = 0$ for all $u,v \in S$, let $S^{\perp}$ denote its symplectic orthogonal complement, and set $g(S,M) = \dim_{\bbf_p}\!\big(S^{\perp}\cap V_M\big) - \dim_{\bbf_p}(S_M)$. Then, writing $M^c$ for the complementary set of coordinates, \[ g(S,M) \;=\; 2\,\abs{M} + \dim_{\bbf_p}\!\big(S_{M^c}\big) - \dim_{\bbf_p}(S) - \dim_{\bbf_p}(S_M). \]
Statement
open scoped BigOperators in set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in set_option linter.unnecessarySimpa false in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in lemma g_expansion (S : Submodule (F p) (V n p)) (hS : IsIsotropic S) (M : Finset (Fin n)) : g S M = 2 * M.card + Module.finrank (F p) (S_M S (E_c M)) - Module.finrank (F p) S - Module.finrank (F p) (S_M S M)
- Source
- TCSlib, `g_expansion`
- Lean proof
- By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.g_expansion← g_expansion (TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:768): adapted
What was changed in
g_expansion--- TCSlib/ErrorCorrectingCodes/QuantumSingleton.lean:768 (g_expansion) +++ as compiled here @@ -1 +1,37 @@ +open scoped BigOperators in +set_option linter.mathlibStandardSet false in +open scoped BigOperators in +open scoped Real in +open scoped Nat in +open Classical in +open scoped Pointwise in +set_option maxRecDepth 4000 in +set_option synthInstance.maxHeartbeats 20000 in +set_option synthInstance.maxSize 128 in +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +set_option linter.unnecessarySimpa false in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in +variable {n : ℕ} {p : ℕ} [Fact p.Prime] in lemma g_expansion (S : Submodule (F p) (V n p)) (hS : IsIsotropic S) (M : Finset (Fin n)) : @@ -8,2 +44,3 @@ convert dim_map_r_E S M using 1; + rfl rw [ h_g, h_dim_map, tsub_tsub ]; @@ -24,2 +61,3 @@ convert dim_orth_inter M S using 1; + rfl refine' h_dim_S_M ▸ Submodule.finrank_mono _; - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 15
- E_c$E^c = \mathrm{Fin}\,n \setminus E$, the complement finset of $E$.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod. - IsIsotropic$S$ is isotropic if $S \le S^{\perp_\omega}$, i.e.\ $\omega(u,v) = 0$ for all $u,v \in S$.
- S_MFor a submodule $S \le V$ and $M \subseteq \mathrm{Fin}\,n$, the submodule $S_M = S \cap V_M$.
- S_perp_MThe submodule $S^{\perp}_M = S^{\perp_\omega} \cap V_M$.
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
- V_subFor $C \subseteq \mathrm{Fin}\,n$, the support submodule $V_C = \{v \in V \mid \mathrm{supp}(v) \subseteq C\}$.
- dim_V_subDimension of the support submodule. Fix a prime $p$ and an integer $n$, and let $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ be the space of…
- dim_map_r_ERank of a restricted subspace of $\mathbb{F}_p^n \times \mathbb{F}_p^n$. Fix a prime $p$ and an integer $n \ge 0$, and let…
- dim_orth_interDimension of the orthogonal intersection over a coordinate set. Fix a prime $p$, an integer $n$, and work in the symplectic space…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- r_EThe linear map $r_E : V \to V_E$ that zeroes out the coordinates of a vector outside $E$, keeping those in $E$ unchanged.
- sym_orthFor a submodule $S \le V$, $S^{\perp_\omega} = \{v \in V \mid \forall s \in S,\; \omega(v,s) = 0\}$.
- symB_applyEvaluation of the bundled symplectic form. Fix a prime $p$ and an integer $n$, and set $V = \bbf_p^n \times \bbf_p^n$, equipped with the…
- sym_form_sub_applyEvaluation of the restricted symplectic form. Fix a prime $p$ and let $\omega$ denote the symplectic form on…
- Used by 1
- g_formulaDimension formula for the operator count of an isotropic subspace. Let $p$ be prime, and equip the symplectic space…
Lean source view module on GitHub
open scoped BigOperators in set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in set_option linter.unnecessarySimpa false in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in lemma g_expansion (S : Submodule (F p) (V n p)) (hS : IsIsotropic S) (M : Finset (Fin n)) : g S M = 2 * M.card + Module.finrank (F p) (S_M S (E_c M)) - Module.finrank (F p) S - Module.finrank (F p) (S_M S M) := by have h_g : g S M = 2 * M.card - Module.finrank (F p) (S.map (r_E M)) - Module.finrank (F p) (S_M S M) := by unfold g; rw [ show S_perp_M S M = sym_orth S ⊓ V_sub ( p := p ) M from rfl, dim_orth_inter ]; -- By definition of $r_E$, we know that have h_dim_map : Module.finrank (F p) (S.map (r_E M)) = Module.finrank (F p) S - Module.finrank (F p) (S_M S (E_c M)) := by convert dim_map_r_E S M using 1; rfl rw [ h_g, h_dim_map, tsub_tsub ]; rw [ tsub_tsub, add_comm ]; rw [ tsub_eq_of_eq_add ]; rw [ tsub_add_eq_add_tsub ]; · rw [ Nat.sub_eq_of_eq_add ]; rw [ ← add_assoc, add_comm ]; rw [ tsub_add_eq_add_tsub ]; · exact Nat.sub_eq_of_eq_add <| by ring; · exact Submodule.finrank_mono <| inf_le_left; · have h_dim_S_map : Module.finrank (F p) (S.map (r_E M)) ≤ 2 * M.card := by have h_dim_S_map : Module.finrank (F p) (S.map (r_E M)) ≤ Module.finrank (F p) (V_sub (p:=p) M) := by apply_rules [ Submodule.finrank_le ]; exact h_dim_S_map.trans ( by rw [ dim_V_sub ] ); have h_dim_S_M : Module.finrank (F p) (S_M S M) ≤ 2 * M.card - Module.finrank (F p) (S.map (r_E M)) := by have h_dim_S_M : Module.finrank (F p) (S_perp_M S M) = 2 * M.card - Module.finrank (F p) (S.map (r_E M)) := by convert dim_orth_inter M S using 1; rfl refine' h_dim_S_M ▸ Submodule.finrank_mono _; exact fun x hx => ⟨ hS hx.1, hx.2 ⟩; omega /- The complement of the complement is the original set. -/