AFTD Auto-Formalizing Theoretical Domains

min_q_ary_deletion_collision_two_eq_min_binary

theoremverified

For all k and n, the minimum q-ary k-deletion collision sum over words of length n with q = 2 equals the minimum binary k-deletion collision sum over binary words of length n.

Statement

theorem min_q_ary_deletion_collision_two_eq_min_binary (k n : ℕ) :
    min_q_ary_deletion_collision 2 k n = min_binary_deletion_collision k n
Source
Helper for OP-1359: its q = 2 case is the k = 2 case of OP-1352.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • min_q_ary_deletion_collisionFor natural numbers q, k, and n, min_q_ary_deletion_collision q k n is the minimum over all q-ary words w of length n of the sum over all…
  • min_binary_deletion_collisionFor natural numbers k and n, min_binary_deletion_collision k n is the minimum over all binary words w of length n of…
  • binary_deletion_collision_eq_q_ary_twoFor every k, n and binary word w of length n, the binary k-deletion collision sum of w equals the q-ary k-deletion collision sum (q = 2)…
  • 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…
  • binary_deletion_collisionFor natural numbers k and n and a binary word w of length n, binary_deletion_collision k n w is the sum over all binary words u of length…
Used by 1

The proof, explained

For q = 2, the minimum q-ary k-deletion collision sum equals the minimum binary k-deletion collision sum because both are the minimums over the set of collision sums achieved by length-n words. Since the condition 0 < 2 holds, the q-ary definition simplifies to the minimum over words in Fin n → Fin 2. The canonical bijection between Fin 2 and Bool then induces an identity between the set of 2-ary collision values and the set of binary collision values, so their minimums coincide.

  1. The minimum 2-ary deletion collision sum simplifies to taking the minimum over the image of all words in Fin n → Fin 2.

    Unfolding the definitions of `min_q_ary_deletion_collision` and `min_binary_deletion_collision`, the q-ary definition has a guard condition 0 < q ∨ n = 0. For q = 2, the inequality 0 < 2 holds, so `dif_pos` together with `Or.inl` selects the "then" branch.

    lines 3–4

    uses dif_pos, Or.inl

      unfold min_q_ary_deletion_collision min_binary_deletion_collision
      rw [dif_pos (Or.inl (by norm_num))]
  2. It suffices to prove that the set of collision values achieved over all 2-ary words equals the set of collision values achieved over all binary words.

    The minimum values of two finite sets of natural numbers coincide if the underlying sets of values are equal (`congr 1`).

    line 5

      congr 1
  3. The set equality reduces to showing that any natural number c is achieved by a 2-ary word if and only if it is achieved by a binary word.

    By set extensionality (`ext c`), an element c belongs to the first set if and only if it belongs to the second. Using `Finset.mem_image` and `Finset.mem_univ`, and rewriting binary collision sums into 2-ary form via `binary_deletion_collision_eq_q_ary_two`, the goal becomes a two-way equivalence between the existence of a 2-ary witness and the existence of a binary witness. Splitting this equivalence (`constructor`) yields two directional implications.

    lines 6–8

    uses Finset.mem_image, Finset.mem_univ, true_and, binary_deletion_collision_eq_q_ary_two

      ext c
      simp only [Finset.mem_image, Finset.mem_univ, true_and, binary_deletion_collision_eq_q_ary_two]
      constructor
  4. Every collision sum attained by a 2-ary word is attained by a binary word.

    Given a 2-ary word w : Fin n → Fin 2, mapping each symbol across the bijection `finTwoEquiv` yields a binary word fun i => finTwoEquiv (w i). Inverting the bijection recovers w, so this binary word produces the exact same collision sum.

    lines 9–10

    uses finTwoEquiv

      · rintro ⟨w, rfl⟩
        exact ⟨fun i => finTwoEquiv (w i), by simp⟩
  5. Every collision sum attained by a binary word is attained by a 2-ary word.

    Given a binary word w : Fin n → Bool, the word fun i => finTwoEquiv.symm (w i) is an explicit 2-ary word that attains the required collision sum by definition.

    lines 11–12

      · rintro ⟨w, rfl⟩
        exact ⟨_, rfl⟩
dif_pos
A dependent if-then-else expression evaluates to its "then" branch whenever the condition holds.
Or.inl
If a proposition a holds, then the disjunction a ∨ b holds.
Finset.mem_image
An element belongs to the image of a finite set under a function if and only if it is the image of some element in that set.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
true_and
The conjunction of True with any proposition p is equivalent to p.
binary_deletion_collision_eq_q_ary_two
The binary k-deletion collision sum of a boolean word equals the 2-ary deletion collision sum of the corresponding word over Fin 2.
finTwoEquiv
The canonical equivalence (bijection) between Fin 2 and Bool.

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

theorem min_q_ary_deletion_collision_two_eq_min_binary (k n : ℕ) :    min_q_ary_deletion_collision 2 k n = min_binary_deletion_collision k n := by  unfold min_q_ary_deletion_collision min_binary_deletion_collision  rw [dif_pos (Or.inl (by norm_num))]  congr 1  ext c  simp only [Finset.mem_image, Finset.mem_univ, true_and, binary_deletion_collision_eq_q_ary_two]  constructor  · rintro ⟨w, rfl⟩    exact ⟨fun i => finTwoEquiv (w i), by simp⟩  · rintro ⟨w, rfl⟩    exact ⟨_, rfl⟩
See it in the graphDiscuss this resultChallenge it