binary_repetition_code_is_joint_perfect_code
theoremverifiedformalization
For an explicit natural number n with 2 ≤ n and natural numbers c, c' such that 2 * c + c' + 1 = n, the binary repetition code of length n is a (c, c') joint perfect code, that is, is_joint_perfect_code c c' (binary_repetition_code n) holds.
Statement
theorem binary_repetition_code_is_joint_perfect_code (n c c' : ℕ) (hn : 2 ≤ n)
(h_dim : 2 * c + c' + 1 = n) :
is_joint_perfect_code c c' (binary_repetition_code n)- Formalizes
- arXiv:2611.18156 Theorem IV.3
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- binary_repetition_codeFor an explicit natural number n, the binary repetition code
binary_repetition_code nis theFinset (Fin n → Fin 2)containing the… - is_joint_perfect_codeA code C ⊆ (Fin n → Fin q) is a (c, c') joint perfect code if it is a (c, c') joint error-correcting and detecting code and satisfies |C|…
- binary_repetition_code_cardFor an explicit natural number n with 1 ≤ n, the cardinality of the finite set
binary_repetition_code nis 2. - binary_repetition_code_is_joint_error_correcting_detectingFor an explicit natural number n with 2 ≤ n and natural numbers c, c' such that 2 * c + c' + 1 = n,
binary_repetition_code nis a (c,… - sum_choose_joint_bound_binaryFor all natural numbers n, c, c' such that 2 * c + c' + 1 = n, 2 * (∑ i ∈ Finset.range (c + 1), Nat.choose n i) + ∑ j ∈ Finset.Icc (c + 1)…
- is_joint_error_correcting_detectingGiven implicit parameters n and q, a code C : Finset (Fin n → Fin q) is a (c, c') joint error-correcting and detecting code if distinct…
- binary_repetition_codeFor an explicit natural number n, the binary repetition code
Read back from the Lean
Let $n, c, c' \in \mathbb{N}$. Assume that $2 \le n$ and $2c + c' + 1 = n$. Then the binary repetition code of length $n$ is a joint $(c, c')$-perfect code (is_joint_perfect_code c c' (binary_repetition_code n)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Binary repetition codes of length n ≥ 2 are (c, c') joint perfect codes for all c, c' with 2c + c' + 1 = n (Theorem IV.3). -/ theorem binary_repetition_code_is_joint_perfect_code (n c c' : ℕ) (hn : 2 ≤ n) (h_dim : 2 * c + c' + 1 = n) : is_joint_perfect_code c c' (binary_repetition_code n) := by refine ⟨binary_repetition_code_is_joint_error_correcting_detecting n c c' hn h_dim, ?_⟩ simp only [binary_repetition_code_card n (by omega), show (2 - 1 : ℕ) = 1 from rfl, one_pow, mul_one, sum_choose_joint_bound_binary n c c' h_dim]