AFTD Auto-Formalizing Theoretical Domains

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 n is the Finset (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 n is 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 n is 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…

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]
See it in the graphDiscuss this resultChallenge it