Singleton bound linear
LinearCode.singleton_bound_linear
Plain-language statement
Singleton bound for linear codes
Exact Lean statement
theorem singleton_bound_linear [CommRing F] [StrongRankCondition F]
(LC : LinearCode ι F) :
Module.finrank F LC ≤ card ι - (Code.dist LC.carrier) + 1Formal artifact
Lean source
theorem singleton_bound_linear [CommRing F] [StrongRankCondition F] (LC : LinearCode ι F) : Module.finrank F LC ≤ card ι - (Code.dist LC.carrier) + 1 := by classical -- From the min-distance version and `Code.dist ≤ Code.minDist`. have h1 : Module.finrank F LC ≤ card ι - Code.minDist (LC : Set (ι → F)) + 1 := singletonBound (LC := LC) -- `dist ≤ minDist` since `= d` implies `≤ d` for witnesses have hdist_le_min : Code.dist LC.carrier ≤ Code.minDist (LC : Set (ι → F)) := by classical let S₁ : Set ℕ := {d | ∃ u ∈ LC, ∃ v ∈ LC, u ≠ v ∧ hammingDist u v ≤ d} let S₂ : Set ℕ := {d | ∃ u ∈ LC, ∃ v ∈ LC, u ≠ v ∧ hammingDist u v = d} have hsub : S₂ ⊆ S₁ := by intro d hd; rcases hd with ⟨u, hu, v, hv, hne, heq⟩; exact ⟨u, hu, v, hv, hne, by simp [heq]⟩ by_cases hne : (S₂ : Set ℕ).Nonempty · have hLB : ∀ m ∈ S₂, sInf S₁ ≤ m := fun m hm => Nat.sInf_le (s := S₁) (hsub hm) have := sInf.le_sInf_of_LB (S := S₂) hne hLB simpa [Code.dist, Code.minDist, S₁, S₂] using this · -- S₂ empty ⇒ S₁ empty as well have hS₂empty : S₂ = (∅ : Set ℕ) := (Set.not_nonempty_iff_eq_empty).1 (by simpa using hne) have hS₁empty : S₁ = (∅ : Set ℕ) := by apply (Set.eq_empty_iff_forall_notMem).2 intro m hm rcases hm with ⟨u, hu, v, hv, hne, hle⟩ have : hammingDist u v ∈ S₂ := ⟨u, hu, v, hv, hne, rfl⟩ simpa [hS₂empty, this] simp [Code.dist, Code.minDist, S₁, S₂, hS₁empty, hS₂empty, Nat.sInf_empty] -- Since a - b is antitone in b, add 1 afterwards have hmono' : card ι - Code.minDist (LC : Set (ι → F)) + 1 ≤ card ι - (Code.dist LC.carrier) + 1 := by simpa [Nat.add_comm, Nat.add_left_comm, Nat.add_assoc] using (Nat.add_le_add_right (Nat.sub_le_sub_left hdist_le_min _) 1) exact h1.trans hmono'- Project
- ArkLib
- License
- Apache-2.0
- Commit
- fad5cbf80877
- Source
- ArkLib/Data/CodingTheory/Basic/LinearCode.lean:581-613
Reuse this declaration
Bring the exact result into your workflow
The import identifies the source module. Your project still needs the pinned package dependency shown on this page.
What this badge means
This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.
Continue in this project
Related declarations
Affine gaps lifted to interleaved codes
affine_gaps_lifted_to_interleaved_codes
Project documentation
This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...
Source project: ArkLib
Person-level attribution pending.
Gadget Decompose coeff
ArkLib.Lattices.Ajtai.gadgetDecompose_coeff
Plain-language statement
The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.
Source project: ArkLib
Person-level attribution pending.
Gadget Decompose lawful
ArkLib.Lattices.Ajtai.gadgetDecompose_lawful
Plain-language statement
The base-b gadget decomposition is a lawful gadget decomposition.
Source project: ArkLib
Person-level attribution pending.