krawtchouk
defimported Lean
For 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 natural-number subtraction; the definition gives the intended values for $x \le n$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in set_option maxHeartbeats 800000 in noncomputable def krawtchouk (n j x : ℕ) : ℝ
- Defined in
- TCSlib, `krawtchouk`
- Lean proof
- By Frederick Dehmel, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.krawtchouk← krawtchouk (TCSlib/ErrorCorrectingCodes/MRRW.lean:95): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 6
- krawtchouk_sporadic_zero_five_five_three_fiveThe binary Krawtchouk polynomial P_4^8 evaluated at 3 equals 0, verifying that the quadruple (m, n, k, ℓ) = (5, 5, 3, 5) satisfies the…
- krawtchouk_oneValue of the first Krawtchouk polynomial. Let $n$ and $x$ be natural numbers with $x \le n$. Then the first binary Krawtchouk polynomial…
- krawtchouk_zeroValue of the zeroth Krawtchouk polynomial. For all natural numbers $n$ and $x$, the degree-zero binary Krawtchouk polynomial is…
- krawtchouk_sum_evalTotal sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the sum of the binary Krawtchouk polynomials…
- krawtchouk_alternating_sum_evalAlternating sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the alternating sum sum_{j=0}^n (-1)^j…
- 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…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in set_option maxHeartbeats 800000 in /-- **Definition 4 (binary Krawtchouk polynomials, integer arguments)** from the source file. For `0 ≤ j ≤ n`, the binary Krawtchouk polynomial `K_j^{(n)}(x)` evaluated at `x ∈ {0,1,...,n}` is given by `K_j^{(n)}(x) = ∑_{i=0}^{j} (-1)^i · C(x,i) · C(n-x, j-i)`. This definition uses natural number subtraction; it gives the correct values for `x ≤ n`. -/ noncomputable def krawtchouk (n j x : ℕ) : ℝ := ∑ i ∈ Finset.range (j + 1), (-1 : ℝ) ^ i * (Nat.choose x i : ℝ) * (Nat.choose (n - x) (j - i) : ℝ)