AFTD Auto-Formalizing Theoretical Domains

krawtchouk_sum_eval

theoremverifiedformalization

Total sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the sum of the binary Krawtchouk polynomials sum_{j=0}^n K_j^{(n)}(x) equals 2^n if x = 0, and equals 0 if x > 0.

Statement

theorem krawtchouk_sum_eval (n x : ℕ) (hx : x ≤ n) :
    ∑ j ∈ Finset.range (n + 1), krawtchouk n j x = if x = 0 then (2 : ℝ) ^ n else 0
Formalizes
MacWilliams & Sloane, The Theory of Error-Correcting Codes (1977), Ch. 5
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • krawtchouk_generating_functionGenerating function of the Krawtchouk polynomials. Let $n$ and $x$ be natural numbers with $x \le n$, and let $K_j^{(n)}(x)$ denote the…
  • krawtchoukFor naturals $n$, $j$, $x$, \[ K_j^{(n)}(x) \;=\; \sum_{i=0}^{j} (-1)^i \binom{x}{i}\binom{n-x}{j-i}, \] where the subtraction $n-x$ is…

Read back from the Lean

For all natural numbers $n$ and $x$ satisfying $x \le n$, the sum over $j \in \{0, \ldots, n\}$ of $\operatorname{krawtchouk}(n, j, x)$ is equal to $2^n$ (as a real number) if $x = 0$, and is equal to $0$ if $x \ne 0$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof specializes the generating function identity ∑_{j=0}^n K_j^{(n)}(x) z^j = (1 - z)^x (1 + z)^(n - x) at z = 1, reducing the sum of the binary Krawtchouk polynomials to 0^x · 2^(n - x). A case split on whether x = 0 concludes the argument: if x = 0, then 0^0 · 2^n = 2^n, whereas if x > 0, the factor 0^x is 0, making the sum vanish.

  1. The sum of the Krawtchouk polynomials reduces to 0^x * (1 + 1)^(n - x).

    Specializing the generating function identity ∑_{j=0}^n K_j^{(n)}(x) z^j = (1 - z)^x (1 + z)^(n - x) (`krawtchouk_generating_function`) at z = 1, each 1^j term becomes 1 via `one_pow` and cancels out via `mul_one`, while 1 - 1 simplifies to 0 via `sub_self`. Rewriting the goal with this identity replaces the left-hand sum with 0^x * (1 + 1)^(n - x).

    lines 4–6

    uses krawtchouk_generating_function, one_pow, mul_one, sub_self

      have h := krawtchouk_generating_function n x hx 1
      simp only [one_pow, mul_one, sub_self] at h
      rw [h]
  2. It suffices to verify the equality separately in the cases x = 0 and x ≠ 0.

    A case split (`split_ifs`) on the condition x = 0 from the if-then-else expression yields two goals: showing 0^x * (1 + 1)^(n - x) = 2^n when x = 0, and showing 0^x * (1 + 1)^(n - x) = 0 when x ≠ 0.

    line 7

      split_ifs with hx0
  3. When x = 0, the expression evaluates to 2^n.

    Substituting x = 0 (`subst`), the expression becomes 0^0 * (1 + 1)^(n - 0). Because 0^0 = 1, 1 + 1 = 2, and n - 0 = n, standard arithmetic simplification (`norm_num`) evaluates the product to 2^n.

    lines 8–9

      · subst hx0
        norm_num
  4. When x ≠ 0, the expression evaluates to 0.

    Because x ≠ 0, 0^x equals 0 by `zero_pow`. Multiplying 0 by (1 + 1)^(n - x) then yields 0 by `zero_mul`.

    line 10

    uses zero_pow, zero_mul

      · rw [zero_pow hx0, zero_mul]
krawtchouk_generating_function
The generating function identity for binary Krawtchouk polynomials: for x ≤ n and any real z, ∑_{j=0}^n K_j^{(n)}(x) z^j = (1 - z)^x (1 + z)^(n - x).
one_pow
In any monoid, 1 raised to any natural power n equals 1: 1^n = 1.
mul_one
Multiplying any element by 1 on the right leaves it unchanged: a * 1 = a.
sub_self
Subtracting an element from itself yields zero: a - a = 0.
zero_pow
In a monoid with zero, zero raised to any non-zero natural power is zero: 0^n = 0 for n ≠ 0.
zero_mul
Multiplying zero by any element on the right yields zero: 0 * a = 0.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Sum of all binary Krawtchouk polynomials: evaluates to 2^n when x = 0 and to 0 when x > 0. -/theorem krawtchouk_sum_eval (n x : ℕ) (hx : x ≤ n) :    ∑ j ∈ Finset.range (n + 1), krawtchouk n j x = if x = 0 then (2 : ℝ) ^ n else 0 := by  have h := krawtchouk_generating_function n x hx 1  simp only [one_pow, mul_one, sub_self] at h  rw [h]  split_ifs with hx0  · subst hx0    norm_num  · rw [zero_pow hx0, zero_mul]
See it in the graphDiscuss this resultChallenge it