AFTD Auto-Formalizing Theoretical Domains

is_joint_perfect_code

def

A 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| * ∑_{i=0}^c Nat.choose n i * (q - 1)^i + ∑_{j=c+1}^{c+c'} Nat.choose n j * (q - 1)^j = q^n.

Statement

def is_joint_perfect_code {n q : ℕ} (c c' : ℕ) (C : Finset (Fin n → Fin q)) : Prop
Defined in
arXiv:2611.18156 Section IV-B
Verified
16 Nov 2026
Axioms
none listed
Built on 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…
Used by 1

Read back from the Lean

Given implicit natural numbers n and q, explicit natural numbers c and c', and a code C : Finset (Fin n → Fin q), is_joint_perfect_code c c' C asserts that two conditions hold: 1. C is a joint error-correcting and error-detecting code with parameters c and c': (a) For all distinct codewords x₁, x₂ ∈ C (x₁ ≠ x₂), the Hamming balls of radius c centered at x₁ and x₂ are disjoint. (b) For all codewords x₁, x₂ ∈ C (including x₁ = x₂, though this is trivially disjoint), the Hamming ball of radius c centered at x₁ is disjoint from the Hamming ring of inner radius c + 1 and outer radius c + c' centered at x₂. 2. The following integer equality holds: |C| * (∑ i ∈ [0, c], Nat.choose n i * (q - 1)^i) + (∑ j ∈ [c + 1, c + c'], Nat.choose n j * (q - 1)^j) = q^n. That is, |C| times the volume of a Hamming ball of radius c in (Fin q)^n, plus the volume of a single Hamming ring with radii from c + 1 to c + c', equals q^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

/-- A code is a (c, c') joint perfect code if it is (c, c') joint error-correcting and detecting and achieves equality in the joint Hamming bound. -/
def is_joint_perfect_code {n q : ℕ} (c c' : ℕ) (C : Finset (Fin n → Fin q)) : Prop := is_joint_error_correcting_detecting c c' C ∧
    C.card * (∑ i ∈ Finset.range (c + 1), Nat.choose n i * (q - 1) ^ i) +
      ∑ j ∈ Finset.Icc (c + 1) (c + c'), Nat.choose n j * (q - 1) ^ j = q ^ n
See it in the graphDiscuss this resultChallenge it