op_1534_constant_word_deletion_envelope_eq
For integers t ≥ 1, q ≥ 2, and n ≥ 1, and any threshold r, the t-deletion hinge sum of the all-zero word qary_all_zero_word q n (by omega) equals the closed-form upper envelope qary_constant_word_deletion_envelope t q n r.
Statement
theorem op_1534_constant_word_deletion_envelope_eq (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n) (r : ℕ) : qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) = qary_constant_word_deletion_envelope t q n r
- Formalizes
- arXiv:2407.10026 "Conditional entropies of k-deletion/insertion channels"
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- qary_multiple_deletion_hingeFor natural numbers t, q, n, and r, and a q-ary word y of length n (y : Fin n → Fin q), the t-deletion hinge sum is the sum over all words…
- qary_all_zero_wordFor an alphabet size q with 1 ≤ q and length n, the all-zero word is the word in Fin n → Fin q taking constant value 0 (represented by ⟨0,…
- qary_constant_word_deletion_envelopeFor deletion radius t, alphabet size q, length n, and threshold r, the explicit upper envelope for the constant-word deletion hinge sum is…
- q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For all natural numbers $t \ge 1$, $q \ge 2$, $n \ge 1$, and $r \ge 0$, the $q$-ary multiple deletion hinge quantity qary_multiple_deletion_hinge t q n r evaluated at the all-zero word of length $n$ over alphabet size $q$ is equal to the deletion envelope qary_constant_word_deletion_envelope t q n r.
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 computes the t-deletion hinge sum of the all-zero word by classifying words x of length n + t according to their number of zeros z. First, it shows that any embedding of the length-n all-zero word into x corresponds bijectively to choosing an n-element subset of the positions where x is zero, giving z.choose n embeddings. Next, it determines that the number of words of length n + t with exactly z zeros is (n + t).choose z * (q - 1)^(n + t - z), by establishing a bijection between words with a fixed zero set and choices of non-zero symbols outside it. Finally, grouping the total sum by z ∈ {0, ..., n + t} and observing that terms with z < n vanish because z.choose n = 0 (and 0 - r = 0 in natural number arithmetic), the sum reduces to z ∈ [n, n + t], matching the deletion envelope definition.
The forward map toFun and inverse map invFun between words with zero-set S and functions from Sᶜ into non-zero symbols are well-defined.
For a word x whose zero-set is S, any index j ∉ S satisfies x(j) ≠ z0 by definition of the zero-set, so restricting x to Sᶜ gives a well-defined function into the non-zero symbols. Conversely, given a function g from Sᶜ to non-zero symbols, extending it by setting x(j) = z0 for j ∈ S and x(j) = g(j) for j ∉ S produces a word whose zero-set is exactly S, verified by checking the two cases j ∈ S and j ∉ S.
uses
op_1534_constant_word_deletion_envelope_eq_zset,dif_pos,iff_of_true,dif_neg,iff_of_falseopen Finset private def op_1534_constant_word_deletion_envelope_eq_zset {N q : ℕ} (x : Fin N → Fin q) (z0 : Fin q) : Finset (Fin N) := Finset.univ.filter (fun j => x j = z0) private noncomputable def op_1534_constant_word_deletion_envelope_eq_zset_equiv {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) : {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} ≃ ({j : Fin N // j ∉ S} → {v : Fin q // v ≠ z0}) where toFun x := fun j => ⟨x.1 j.1, by intro h have hj : j.1 ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by simp [op_1534_constant_word_deletion_envelope_eq_zset, h] rw [x.2] at hj exact j.2 hj⟩ invFun g := ⟨fun j => if h : j ∈ S then z0 else (g ⟨j, h⟩).1, by ext j simp only [op_1534_constant_word_deletion_envelope_eq_zset, mem_filter, mem_univ, true_and] by_cases h : j ∈ S · rw [dif_pos h]; exact iff_of_true rfl h · rw [dif_neg h] exact iff_of_false (g ⟨j, h⟩).2 h⟩
The forward and inverse maps are mutual inverses, establishing an equivalence between words with zero-set S and functions from Sᶜ into non-zero symbols.
Evaluating the round-trip of a word x at index j reproduces x(j): if j ∈ S then x(j) = z0, which matches the value assigned by the inverse map; if j ∉ S, the inverse map directly returns the restricted value x(j). In the other direction, evaluating the round-trip of a function g at j ∉ S immediately returns g(j) since j ∉ S triggers the else-branch of the definition.
uses
op_1534_constant_word_deletion_envelope_eq_zset,dif_negleft_inv := by intro x ext j by_cases h : j ∈ S · have hx : x.1 j = z0 := by have : j ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by rw [x.2]; exact h simpa [op_1534_constant_word_deletion_envelope_eq_zset] using this simp [h, hx] · simp [h] right_inv := by intro g ext j simp only [dif_neg j.2]
The number of words x : Fin N → Fin q whose zero-set is S equals (q - 1)^(N - |S|).
Using the equivalence op_1534_constant_word_deletion_envelope_eq_zset_equiv, the number of such words equals the number of functions from Sᶜ to {v : Fin q // v ≠ z0}. The domain has cardinality |Sᶜ| = N - |S| by set complementation in Fin N, and the codomain has cardinality q - 1 by removing the single element z0 from Fin q. The number of functions is therefore (q - 1)^(N - |S|).
uses
Fintype.card_congr,op_1534_constant_word_deletion_envelope_eq_zset_equiv,Fintype.card_fun,Fintype.card_subtype,Finset.card_compl,Fintype.card_fin,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univprivate theorem op_1534_constant_word_deletion_envelope_eq_card_zset_fiber {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) : Fintype.card {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} = (q - 1) ^ (N - S.card) := by rw [Fintype.card_congr (op_1534_constant_word_deletion_envelope_eq_zset_equiv z0 S), Fintype.card_fun] have h1 : Fintype.card {j : Fin N // j ∉ S} = N - S.card := by rw [Fintype.card_subtype] have hh : ({x : Fin N | x ∉ S} : Finset (Fin N)) = Sᶜ := by ext x; simp rw [hh, Finset.card_compl, Fintype.card_fin] have h2 : Fintype.card {v : Fin q // v ≠ z0} = q - 1 := by rw [Fintype.card_subtype] have hh : ({v : Fin q | v ≠ z0} : Finset (Fin q)) = (univ : Finset (Fin q)).erase z0 := by ext v; simp rw [hh, Finset.card_erase_of_mem (Finset.mem_univ z0), Finset.card_univ, Fintype.card_fin] rw [h1, h2]
The set of words with exactly z zeros maps into the collection of z-element subsets of Fin N, partitioning the count fiberwise.
The map sending a word x to its zero-set maps every word with z zeros to a subset of Fin N of size z (an element of powersetCard z univ). By fiberwise decomposition of finset cardinality (Finset.card_eq_sum_card_fiberwise), the total count of words with z zeros is the sum over all z-element subsets b of the number of words having zero-set equal to b.
uses
Finset.mem_powersetCard,Finset.subset_univ,Finset.card_eq_sum_card_fiberwiseprivate theorem op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber {N q : ℕ} (z0 : Fin q) (z : ℕ) : (Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)).card = N.choose z * (q - 1) ^ (N - z) := by have hmap : Set.MapsTo (fun x : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset x z0) ↑(Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)) ↑((univ : Finset (Fin N)).powersetCard z) := by intro x hx simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hx rw [Finset.mem_coe, Finset.mem_powersetCard] exact ⟨Finset.subset_univ _, hx⟩ rw [Finset.card_eq_sum_card_fiberwise hmap]
The number of words x : Fin N → Fin q with exactly z zeros is N.choose z * (q - 1)^(N - z).
For every z-element subset b, the fiber of words whose zero-set is b has cardinality (q - 1)^(N - z) by op_1534_constant_word_deletion_envelope_eq_card_zset_fiber. Since this fiber size is constant across all b in powersetCard z univ, the sum equals the number of such subsets, which is N.choose z, multiplied by (q - 1)^(N - z).
uses
Finset.mem_powersetCard,Fintype.card_subtype,op_1534_constant_word_deletion_envelope_eq_card_zset_fiber,Finset.sum_congr,Finset.sum_const,Finset.card_powersetCard,Finset.card_univ,Fintype.card_fin,Nat.nsmul_eq_mulhave hterm : ∀ b ∈ (univ : Finset (Fin N)).powersetCard z, {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}.card = (q - 1) ^ (N - z) := by intro b hb rw [Finset.mem_powersetCard] at hb obtain ⟨-, hbc⟩ := hb have heq : {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b} = Finset.univ.filter (fun a : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset a z0 = b) := by ext a simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨-, h⟩; exact h · intro h; exact ⟨by rw [h]; exact hbc, h⟩ rw [heq, ← Fintype.card_subtype, op_1534_constant_word_deletion_envelope_eq_card_zset_fiber, hbc] rw [Finset.sum_congr rfl hterm, Finset.sum_const, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]
Subsequence embeddings of the constant word of length n map to n-element subsets of the zero-positions via their image.
A subsequence embedding of the all-z0 word into x is a strictly increasing map f : Fin n → Fin N whose values all equal z0. The image of f is a subset of the zero-positions of x. Because f is strictly monotonic, it is injective, so its image has size |Fin n| = n, yielding a well-defined map into the n-element subsets of the zero-positions.
uses
q_ary_subsequence_num_embeddings,Finset.card_powersetCard,Finset.card_bij,Finset.mem_powersetCard,Finset.mem_image,op_1534_constant_word_deletion_envelope_eq_zset,Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finprivate theorem op_1534_constant_word_deletion_envelope_eq_card_embeddings {n N q : ℕ} (z0 : Fin q) (x : Fin N → Fin q) : q_ary_subsequence_num_embeddings q n N (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := by rw [q_ary_subsequence_num_embeddings] rw [← Finset.card_powersetCard] apply Finset.card_bij (fun f _ => Finset.image f Finset.univ) · intro f hf simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf obtain ⟨hmono, hval⟩ := hf rw [Finset.mem_powersetCard] refine ⟨?_, ?_⟩ · intro j hj rw [Finset.mem_image] at hj obtain ⟨i, -, rfl⟩ := hj simp only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] exact hval i · rw [Finset.card_image_of_injective _ hmono.injective, Finset.card_univ, Fintype.card_fin]
The image map is a bijection, so the number of embeddings of the length-n constant word into x is |zset(x, z0)|.choose n.
If two strictly monotonic maps f1, f2 from Fin n have the same image S, they are both order embeddings onto S; by uniqueness of order embeddings from Fin n (Finset.orderEmbOfFin_unique), f1 = f2, proving injectivity. Conversely, given any n-element subset S of the zero-positions, the canonical order embedding of S gives a strictly increasing map from Fin n into the zero-positions with image S, proving surjectivity. Thus embeddings are in bijection with n-element subsets of the zero-positions, whose count is |zset(x, z0)|.choose n.
uses
Finset.card_image_of_injective,Finset.card_univ,Fintype.card_fin,Finset.orderEmbOfFin_unique,Finset.mem_image_of_mem,Finset.mem_powersetCard,Finset.image_orderEmbOfFin_univ,op_1534_constant_word_deletion_envelope_eq_zset,Finset.orderEmbOfFin_mem· intro f1 hf1 f2 hf2 heq simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf1 hf2 have hc : (Finset.image f1 Finset.univ).card = n := by rw [Finset.card_image_of_injective _ hf1.1.injective, Finset.card_univ, Fintype.card_fin] have e1 := Finset.orderEmbOfFin_unique hc (fun i => Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf1.1 have e2 := Finset.orderEmbOfFin_unique hc (fun i => by rw [heq]; exact Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf2.1 exact e1.trans e2.symm · intro S hS rw [Finset.mem_powersetCard] at hS obtain ⟨hsub, hcard⟩ := hS refine ⟨⇑(S.orderEmbOfFin hcard), ?_, Finset.image_orderEmbOfFin_univ S hcard⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨(S.orderEmbOfFin hcard).strictMono, fun i => ?_⟩ simpa only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] using hsub (Finset.orderEmbOfFin_mem S hcard i) /-- The multiple-deletion hinge sum of the all-zero word matches the explicit upper envelope. -/
The hinge sum is rewritten with embeddings expressed as binomial coefficients, and every zero-count lies in {0, ..., n + t}.
The all-zero word is identified with the constant word with value z0 = 0. By op_1534_constant_word_deletion_envelope_eq_card_embeddings, the number of embeddings into any word x of length n + t is |zset(x, z0)|.choose n. Since the zero-set of x is a subset of Fin (n + t), its cardinality is at most n + t, so it belongs to Finset.range (n + t + 1).
uses
qary_multiple_deletion_hinge,qary_constant_word_deletion_envelope,op_1534_constant_word_deletion_envelope_eq_card_embeddings,Finset.mem_range,Finset.filter_subset,Finset.card_le_card,Finset.card_univ,Fintype.card_fintheorem op_1534_constant_word_deletion_envelope_eq (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n) (r : ℕ) : qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) = qary_constant_word_deletion_envelope t q n r := by rw [qary_multiple_deletion_hinge, qary_constant_word_deletion_envelope] set z0 : Fin q := ⟨0, by omega⟩ with hz0 have hzw : qary_all_zero_word q n (by omega) = (fun _ : Fin n => z0) := rfl rw [hzw] have hstep : ∀ x : Fin (n + t) → Fin q, q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := fun x => op_1534_constant_word_deletion_envelope_eq_card_embeddings z0 x have hmap : ∀ x ∈ (Finset.univ : Finset (Fin (n + t) → Fin q)), (op_1534_constant_word_deletion_envelope_eq_zset x z0).card ∈ Finset.range (n + t + 1) := by intro x _ rw [Finset.mem_range] have h1 : op_1534_constant_word_deletion_envelope_eq_zset x z0 ⊆ (Finset.univ : Finset (Fin (n + t))) := Finset.filter_subset _ _ have h2 := Finset.card_le_card h1 rw [Finset.card_univ, Fintype.card_fin] at h2 omega
Partitioning words by their zero-count z expresses the hinge sum as ∑_{z=0}^{n+t} (n + t).choose z * (q - 1)^(n + t - z) * (z.choose n - r).
Replacing the embeddings count with |zset(x, z0)|.choose n and regrouping the sum fiberwise by the zero-count z ∈ range (n + t + 1) using Finset.sum_fiberwise_of_maps_to', each fiber has constant summand z.choose n - r. Multiplying by the fiber size (n + t).choose z * (q - 1)^(n + t - z) gives the double sum evaluated as a single sum over z.
uses
Finset.sum_congr,Finset.sum_fiberwise_of_maps_to',Finset.sum_const,op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber,Nat.nsmul_eq_mulcalc ∑ x : Fin (n + t) → Fin q, (q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x - r) = ∑ x : Fin (n + t) → Fin q, ((op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n - r) := by apply Finset.sum_congr rfl intro x _ rw [hstep x] _ = ∑ z ∈ Finset.range (n + t + 1), ∑ x ∈ Finset.univ.filter (fun x : Fin (n + t) → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z), (z.choose n - r) := by exact (Finset.sum_fiberwise_of_maps_to' hmap (fun z => z.choose n - r)).symm _ = ∑ z ∈ Finset.range (n + t + 1), (((n + t).choose z * (q - 1) ^ (n + t - z)) * (z.choose n - r)) := by apply Finset.sum_congr rfl intro z _ rw [Finset.sum_const, op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber, Nat.nsmul_eq_mul]
The summation index restricts from {0, ..., n + t} to [n, n + t], completing the proof.
For any z < n, the binomial coefficient z.choose n is 0 by Nat.choose_eq_zero_of_lt. In natural number arithmetic, 0 - r = 0, so the entire summand vanishes for all z < n. By Finset.sum_subset, the sum over Finset.range (n + t + 1) reduces to the sum over Finset.Icc n (n + t), which is exactly the definition of qary_constant_word_deletion_envelope.
uses
Finset.sum_subset,Finset.mem_Icc,Finset.mem_range,Nat.choose_eq_zero_of_lt_ = ∑ z ∈ Finset.Icc n (n + t), ((n + t).choose z * (q - 1) ^ (n + t - z) * (z.choose n - r)) := by refine (Finset.sum_subset ?_ ?_).symm · intro z hz rw [Finset.mem_Icc] at hz rw [Finset.mem_range] omega · intro z hz hznot rw [Finset.mem_range] at hz rw [Finset.mem_Icc] at hznot have hlt : z < n := by omega rw [Nat.choose_eq_zero_of_lt hlt] simp
op_1534_constant_word_deletion_envelope_eq_zset- the set of coordinate indices j where a word x equals a specified symbol z0
dif_pos- the value of a dependent if-then-else when the condition is true
iff_of_true- an equivalence between two propositions holds if both propositions are true
dif_neg- the value of a dependent if-then-else when the condition is false
iff_of_false- an equivalence between two propositions holds if both propositions are false
op_1534_constant_word_deletion_envelope_eq_zset_equiv- words whose zero-set equals S are in canonical bijection with functions from the complement of S into the non-zero alphabet symbols
Fintype.card_congr- equivalent finite types have the same cardinality
Fintype.card_fun- the number of functions from a finite type α to a finite type β is |β|^|α|
Fintype.card_subtype- the cardinality of a subtype {x // p x} equals the cardinality of the filtered finset {x | p x}
Finset.card_compl- the cardinality of the complement of a subset S in a finite universe is the universe cardinality minus |S|
Fintype.card_fin- the finite set Fin n of integers {0, ..., n - 1} has cardinality n
Finset.card_erase_of_mem- removing an element from a finset decreases its cardinality by 1
Finset.mem_univ- every element of a finite type belongs to the universal finset
Finset.card_univ- the cardinality of the universal finset of a finite type equals the type's cardinality
Finset.mem_powersetCard- a subset belongs to powersetCard n t if and only if it is a subset of t and has cardinality n
Finset.subset_univ- every finset of elements from a finite type is a subset of the universal finset
Finset.card_eq_sum_card_fiberwise- the cardinality of a set s equals the sum of the cardinalities of its fibers over a target finset t under a map f
op_1534_constant_word_deletion_envelope_eq_card_zset_fiber- the number of q-ary words of length N whose zero-set is a given subset S is (q - 1)^(N - |S|)
Finset.sum_congr- two sums over equal index sets are equal if their terms agree at every index
Finset.sum_const- the sum of a constant value b over a finset s equals |s| • b
Finset.card_powersetCard- the number of subsets of size n of a finset s is |s|.choose n
Nat.nsmul_eq_mul- scalar multiplication of natural numbers m • n equals their product m * n
q_ary_subsequence_num_embeddings- the number of strictly increasing embedding maps from word u into word w matching symbols at all positions
Finset.card_bij- two finsets have the same cardinality if there is a function between them that is well-defined, injective, and surjective
Finset.mem_image- an element belongs to the image of a finset under f if and only if it is f(a) for some element a in the finset
Finset.card_image_of_injective- the image of a finset under an injective map has the same cardinality as the finset
Finset.orderEmbOfFin_unique- a strictly monotonic map from Fin k onto a finset of size k is the unique order embedding from Fin k to that set
Finset.mem_image_of_mem- the image of an element of a finset under f belongs to the image finset
Finset.image_orderEmbOfFin_univ- the image of Fin k under the canonical order embedding of a size-k finset s is s itself
Finset.orderEmbOfFin_mem- the canonical order embedding of a finset s maps every element into s
qary_multiple_deletion_hinge- the sum over all words x of length n + t of the hinge quantity (embeddings(y, x) - r)
qary_constant_word_deletion_envelope- the explicit upper envelope sum over z from n to n + t of (n + t).choose z * (q - 1)^(n + t - z) * (z.choose n - r)
op_1534_constant_word_deletion_envelope_eq_card_embeddings- the number of subsequence embeddings of the constant word of length n into x equals |zset(x, z0)|.choose n
Finset.mem_range- a natural number m belongs to Finset.range n if and only if m < n
Finset.filter_subset- filtering a finset by a predicate yields a subset of the original finset
Finset.card_le_card- if s is a subset of t, then the cardinality of s is at most that of t
Finset.sum_fiberwise_of_maps_to'- a sum over s can be rewritten by partitioning into fibers over the values of a map g into t
op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber- the number of q-ary words of length N containing exactly z occurrences of symbol z0 is N.choose z * (q - 1)^(N - z)
Finset.sum_subset- a sum over a smaller finset equals a sum over a larger finset if the summand vanishes outside the smaller finset
Finset.mem_Icc- an element x belongs to the closed interval Icc a b if and only if a ≤ x and x ≤ b
Nat.choose_eq_zero_of_lt- the binomial coefficient n.choose k is zero whenever n < k
- In step 10, natural number subtraction truncation (0 - r = 0) is essential: for z < n, z.choose n = 0, so the hinge factor (z.choose n - r) evaluates to 0, causing all terms with z < n to vanish.
- Line 114 contains an inline proof `(by omega)` in the theorem statement to verify 1 ≤ q, which is a precondition for constructing `qary_all_zero_word`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetprivate def op_1534_constant_word_deletion_envelope_eq_zset {N q : ℕ} (x : Fin N → Fin q) (z0 : Fin q) : Finset (Fin N) := Finset.univ.filter (fun j => x j = z0)private noncomputable def op_1534_constant_word_deletion_envelope_eq_zset_equiv {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) : {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} ≃ ({j : Fin N // j ∉ S} → {v : Fin q // v ≠ z0}) where toFun x := fun j => ⟨x.1 j.1, by intro h have hj : j.1 ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by simp [op_1534_constant_word_deletion_envelope_eq_zset, h] rw [x.2] at hj exact j.2 hj⟩ invFun g := ⟨fun j => if h : j ∈ S then z0 else (g ⟨j, h⟩).1, by ext j simp only [op_1534_constant_word_deletion_envelope_eq_zset, mem_filter, mem_univ, true_and] by_cases h : j ∈ S · rw [dif_pos h]; exact iff_of_true rfl h · rw [dif_neg h] exact iff_of_false (g ⟨j, h⟩).2 h⟩ left_inv := by intro x ext j by_cases h : j ∈ S · have hx : x.1 j = z0 := by have : j ∈ op_1534_constant_word_deletion_envelope_eq_zset x.1 z0 := by rw [x.2]; exact h simpa [op_1534_constant_word_deletion_envelope_eq_zset] using this simp [h, hx] · simp [h] right_inv := by intro g ext j simp only [dif_neg j.2]private theorem op_1534_constant_word_deletion_envelope_eq_card_zset_fiber {N q : ℕ} (z0 : Fin q) (S : Finset (Fin N)) : Fintype.card {x : Fin N → Fin q // op_1534_constant_word_deletion_envelope_eq_zset x z0 = S} = (q - 1) ^ (N - S.card) := by rw [Fintype.card_congr (op_1534_constant_word_deletion_envelope_eq_zset_equiv z0 S), Fintype.card_fun] have h1 : Fintype.card {j : Fin N // j ∉ S} = N - S.card := by rw [Fintype.card_subtype] have hh : ({x : Fin N | x ∉ S} : Finset (Fin N)) = Sᶜ := by ext x; simp rw [hh, Finset.card_compl, Fintype.card_fin] have h2 : Fintype.card {v : Fin q // v ≠ z0} = q - 1 := by rw [Fintype.card_subtype] have hh : ({v : Fin q | v ≠ z0} : Finset (Fin q)) = (univ : Finset (Fin q)).erase z0 := by ext v; simp rw [hh, Finset.card_erase_of_mem (Finset.mem_univ z0), Finset.card_univ, Fintype.card_fin] rw [h1, h2]private theorem op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber {N q : ℕ} (z0 : Fin q) (z : ℕ) : (Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)).card = N.choose z * (q - 1) ^ (N - z) := by have hmap : Set.MapsTo (fun x : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset x z0) ↑(Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z)) ↑((univ : Finset (Fin N)).powersetCard z) := by intro x hx simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hx rw [Finset.mem_coe, Finset.mem_powersetCard] exact ⟨Finset.subset_univ _, hx⟩ rw [Finset.card_eq_sum_card_fiberwise hmap] have hterm : ∀ b ∈ (univ : Finset (Fin N)).powersetCard z, {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b}.card = (q - 1) ^ (N - z) := by intro b hb rw [Finset.mem_powersetCard] at hb obtain ⟨-, hbc⟩ := hb have heq : {a ∈ Finset.univ.filter (fun x : Fin N → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z) | op_1534_constant_word_deletion_envelope_eq_zset a z0 = b} = Finset.univ.filter (fun a : Fin N → Fin q => op_1534_constant_word_deletion_envelope_eq_zset a z0 = b) := by ext a simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨-, h⟩; exact h · intro h; exact ⟨by rw [h]; exact hbc, h⟩ rw [heq, ← Fintype.card_subtype, op_1534_constant_word_deletion_envelope_eq_card_zset_fiber, hbc] rw [Finset.sum_congr rfl hterm, Finset.sum_const, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]private theorem op_1534_constant_word_deletion_envelope_eq_card_embeddings {n N q : ℕ} (z0 : Fin q) (x : Fin N → Fin q) : q_ary_subsequence_num_embeddings q n N (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := by rw [q_ary_subsequence_num_embeddings] rw [← Finset.card_powersetCard] apply Finset.card_bij (fun f _ => Finset.image f Finset.univ) · intro f hf simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf obtain ⟨hmono, hval⟩ := hf rw [Finset.mem_powersetCard] refine ⟨?_, ?_⟩ · intro j hj rw [Finset.mem_image] at hj obtain ⟨i, -, rfl⟩ := hj simp only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] exact hval i · rw [Finset.card_image_of_injective _ hmono.injective, Finset.card_univ, Fintype.card_fin] · intro f1 hf1 f2 hf2 heq simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hf1 hf2 have hc : (Finset.image f1 Finset.univ).card = n := by rw [Finset.card_image_of_injective _ hf1.1.injective, Finset.card_univ, Fintype.card_fin] have e1 := Finset.orderEmbOfFin_unique hc (fun i => Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf1.1 have e2 := Finset.orderEmbOfFin_unique hc (fun i => by rw [heq]; exact Finset.mem_image_of_mem _ (Finset.mem_univ i)) hf2.1 exact e1.trans e2.symm · intro S hS rw [Finset.mem_powersetCard] at hS obtain ⟨hsub, hcard⟩ := hS refine ⟨⇑(S.orderEmbOfFin hcard), ?_, Finset.image_orderEmbOfFin_univ S hcard⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨(S.orderEmbOfFin hcard).strictMono, fun i => ?_⟩ simpa only [op_1534_constant_word_deletion_envelope_eq_zset, Finset.mem_filter, Finset.mem_univ, true_and] using hsub (Finset.orderEmbOfFin_mem S hcard i)/-- The multiple-deletion hinge sum of the all-zero word matches the explicit upper envelope. -/theorem op_1534_constant_word_deletion_envelope_eq (t : ℕ) (ht : 1 ≤ t) (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n) (r : ℕ) : qary_multiple_deletion_hinge t q n r (qary_all_zero_word q n (by omega)) = qary_constant_word_deletion_envelope t q n r := by rw [qary_multiple_deletion_hinge, qary_constant_word_deletion_envelope] set z0 : Fin q := ⟨0, by omega⟩ with hz0 have hzw : qary_all_zero_word q n (by omega) = (fun _ : Fin n => z0) := rfl rw [hzw] have hstep : ∀ x : Fin (n + t) → Fin q, q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x = (op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n := fun x => op_1534_constant_word_deletion_envelope_eq_card_embeddings z0 x have hmap : ∀ x ∈ (Finset.univ : Finset (Fin (n + t) → Fin q)), (op_1534_constant_word_deletion_envelope_eq_zset x z0).card ∈ Finset.range (n + t + 1) := by intro x _ rw [Finset.mem_range] have h1 : op_1534_constant_word_deletion_envelope_eq_zset x z0 ⊆ (Finset.univ : Finset (Fin (n + t))) := Finset.filter_subset _ _ have h2 := Finset.card_le_card h1 rw [Finset.card_univ, Fintype.card_fin] at h2 omega calc ∑ x : Fin (n + t) → Fin q, (q_ary_subsequence_num_embeddings q n (n + t) (fun _ => z0) x - r) = ∑ x : Fin (n + t) → Fin q, ((op_1534_constant_word_deletion_envelope_eq_zset x z0).card.choose n - r) := by apply Finset.sum_congr rfl intro x _ rw [hstep x] _ = ∑ z ∈ Finset.range (n + t + 1), ∑ x ∈ Finset.univ.filter (fun x : Fin (n + t) → Fin q => (op_1534_constant_word_deletion_envelope_eq_zset x z0).card = z), (z.choose n - r) := by exact (Finset.sum_fiberwise_of_maps_to' hmap (fun z => z.choose n - r)).symm _ = ∑ z ∈ Finset.range (n + t + 1), (((n + t).choose z * (q - 1) ^ (n + t - z)) * (z.choose n - r)) := by apply Finset.sum_congr rfl intro z _ rw [Finset.sum_const, op_1534_constant_word_deletion_envelope_eq_card_zcount_fiber, Nat.nsmul_eq_mul] _ = ∑ z ∈ Finset.Icc n (n + t), ((n + t).choose z * (q - 1) ^ (n + t - z) * (z.choose n - r)) := by refine (Finset.sum_subset ?_ ?_).symm · intro z hz rw [Finset.mem_Icc] at hz rw [Finset.mem_range] omega · intro z hz hznot rw [Finset.mem_range] at hz rw [Finset.mem_Icc] at hznot have hlt : z < n := by omega rw [Nat.choose_eq_zero_of_lt hlt] simp