AFTD Auto-Formalizing Theoretical Domains

word_block_exchange_transport_back_is_mask_iff

theoremverifiedformalization

For an exchange E and a mask N satisfying is_word_mask u v (word_block_exchange_after E) N, the backward-transported mask word_block_exchange_transport_back E N is a valid mask of word_block_exchange_before E for sources u and v if and only if N commutes for E: is_word_mask u v (word_block_exchange_before E) (word_block_exchange_transport_back E N) ↔ word_block_exchange_is_commuting E N.

Statement

theorem word_block_exchange_transport_back_is_mask_iff {α : Type*}
    (E : WordBlockExchange α) (u v : List α) (N : List Bool)
    (hN : is_word_mask u v (word_block_exchange_after E) N) :
    is_word_mask u v (word_block_exchange_before E) (word_block_exchange_transport_back E N) ↔
      word_block_exchange_is_commuting E N
Formalizes
arXiv:2610.39941, Lemma 2
Verified
31 Oct 2026
Axioms
Quot.soundpropext
Built on 7
  • word_block_exchange_transport_backGiven a block exchange E = (X, A, B, Y) and a binary mask N of type List Bool, word_block_exchange_transport_back E N is the binary mask…
  • is_word_maskA binary mask of a word with respect to sources u and v has the same length as the word and projects to u on true and to v on false.
  • word_block_exchange_afterThe word after a block exchange is the concatenation XBAY.
  • WordBlockExchangeA word block exchange consists of four words X, A, B, Y over an alphabet.
  • word_block_exchange_is_commutingA mask N of XBAY is commuting for exchange E if its U-projections and V-projections on the exchanged blocks satisfy A_U B_U = B_U A_U and…
  • word_projThe projection of a word under a binary mask keeps only the letters at positions where the mask equals a given target boolean.
  • word_block_exchange_beforeThe word before a block exchange is the concatenation XABY.

Read back from the Lean

For any type α, any block exchange record E : WordBlockExchange α (with list components E.X, E.A, E.B, E.Y), any lists u, v : List α, and any boolean mask N : List Bool, assuming hN that N is a valid word mask decomposing word_block_exchange_after E (E.X ++ E.B ++ E.A ++ E.Y) into u (for true) and v (for false): The transported mask word_block_exchange_transport_back E N is a valid word mask decomposing word_block_exchange_before E (E.X ++ E.A ++ E.B ++ E.Y) into u and v if and only if word_block_exchange_is_commuting E N holds (that is, the projections of E.A and E.B under their respective submasks commute under list concatenation for both the true projection and the false projection).

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 backward-transported mask rearranges the sub-masks of the exchange blocks A and B from their order in the word after the exchange (X B A Y) back to their original order before the exchange (X A B Y). Because list projection along a mask distributes over concatenation, the projections of X A B Y along the transported mask equal the concatenation of the individual block projections with the A and B components swapped. Comparing these projections to the source words u and v and cancelling the outer invariant blocks X and Y on both sides reduces the validity of the transported mask directly to the condition that the projections of blocks A and B commute.

  1. Word projection distributes over list concatenation when the first mask has the same length as the first word (word_block_exchange_transport_back_is_mask_iff_word_proj_append).

    The lemma is proved by induction on the list w₁, generalizing the mask m₁. If w₁ is empty, the length equality forces m₁ to be empty, and both sides evaluate to the projection of w₂ along m₂. If w₁ = x :: xs, then m₁ must be non-empty with equal tail length; expanding the definition of word_proj and case-splitting on whether the head boolean matches b, the inductive hypothesis applies to the tails in both branches.

    lines 4–15

    uses List.length_cons

      induction' w1 with x xs ih generalizing m1
      · cases m1
        · simp [word_proj]
        · cases h
      · cases m1
        · cases h
        · simp only [List.length_cons] at h
          injection h with h'
          dsimp [word_proj]
          split_ifs with heq
          · simp [ih _ h']
          · exact ih _ h'
  2. Word projection distributes over four concatenated blocks when the corresponding mask and block lengths match (word_block_exchange_transport_back_is_mask_iff_word_proj_four).

    Using List.length_append and linear arithmetic, the composite prefixes (m₁ ++ m₂) and (m₁ ++ m₂ ++ m₃) have the same lengths as (w₁ ++ w₂) and (w₁ ++ w₂ ++ w₃). Three successive applications of word_block_exchange_transport_back_is_mask_iff_word_proj_append then split the four-block projection into the concatenation of the four individual block projections.

    lines 23–29

    uses List.length_append, word_block_exchange_transport_back_is_mask_iff_word_proj_append

      have l12 : (m1 ++ m2).length = (w1 ++ w2).length := by simp [h1, h2]
      have l123 : (m1 ++ m2 ++ m3).length = (w1 ++ w2 ++ w3).length := by
        repeat rw [List.length_append]
        omega
      rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b (w1 ++ w2 ++ w3) w4 (m1 ++ m2 ++ m3) m4 l123]
      rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b (w1 ++ w2) w3 (m1 ++ m2) m3 l12]
      rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b w1 w2 m1 m2 h1]
  3. Two four-block lists differing only in the order of their middle two blocks are equal if and only if the middle two blocks commute (word_block_exchange_transport_back_is_mask_iff_append_four_cancel).

    For the forward direction, cancelling the suffix y from x ++ a ++ b ++ y = x ++ b ++ a ++ y using List.append_cancel_right and then cancelling the prefix x using List.append_cancel_left leaves a ++ b = b ++ a. The reverse direction substitutes a ++ b = b ++ a inside the expression and reassociates.

    lines 33–40

    uses List.append_cancel_right, List.append_assoc, List.append_cancel_left

      constructor
      · intro h
        have h1 := List.append_cancel_right h
        rw [List.append_assoc, List.append_assoc] at h1
        exact List.append_cancel_left h1
      · intro h
        congr 1
        rw [List.append_assoc, h, ← List.append_assoc]
  4. Any list of length n₁ + n₂ + n₃ + n₄ decomposes into four consecutive slices of lengths n₁, n₂, n₃, n₄ whose concatenation equals the original list (word_block_exchange_transport_back_is_mask_iff_list_split_four).

    The four slices are defined by taking and dropping prefixes of lengths n₁, n₂, n₃, and n₄. Their lengths are verified using List.length_take and List.length_drop together with linear arithmetic (omega). The identity l = p₁ ++ p₂ ++ p₃ ++ p₄ is established by repeatedly applying List.take_append_drop to decompose remaining suffixes, combining nested drops with List.drop_drop, and reassociating concatenations.

    lines 50–74

    uses List.length_take, List.length_drop, List.take_append_drop, List.drop_drop, List.append_assoc

      dsimp
      have h1 : (l.take n1).length = n1 := by
        rw [List.length_take]
        omega
      have h2 : ((l.drop n1).take n2).length = n2 := by
        rw [List.length_take, List.length_drop]
        omega
      have h3 : ((l.drop (n1 + n2)).take n3).length = n3 := by
        rw [List.length_take, List.length_drop]
        omega
      have h4 : (l.drop (n1 + n2 + n3)).length = n4 := by
        rw [List.length_drop]
        omega
      refine ⟨h1, h2, h3, h4, ?_⟩
      have eq1 : l = l.take n1 ++ l.drop n1 := (List.take_append_drop n1 l).symm
      have eq2 : l.drop n1 = (l.drop n1).take n2 ++ (l.drop n1).drop n2 :=
        (List.take_append_drop n2 (l.drop n1)).symm
      have eq3 : (l.drop (n1 + n2)) = (l.drop (n1 + n2)).take n3 ++ (l.drop (n1 + n2)).drop n3 :=
        (List.take_append_drop n3 (l.drop (n1 + n2))).symm
      rw [List.drop_drop] at eq2
      rw [eq3] at eq2
      rw [List.drop_drop] at eq2
      rw [eq2] at eq1
      rw [List.append_assoc, List.append_assoc]
      exact eq1
  5. The mask N splits into four parts p₁, p₂, p₃, p₄ with lengths matching the blocks E.X, E.B, E.A, E.Y of the exchange.

    From the assumption that N is a mask for word_block_exchange_after E (X B A Y), the length of N equals |X| + |B| + |A| + |Y|. Applying word_block_exchange_transport_back_is_mask_iff_list_split_four partitions N into four sublists p₁, p₂, p₃, p₄ of lengths |X|, |B|, |A|, |Y| such that N = p₁ ++ p₂ ++ p₃ ++ p₄.

    lines 82–92

    uses List.length_append, word_block_exchange_transport_back_is_mask_iff_list_split_four

      rcases hN with ⟨hlenN, huN, hvN⟩
      have hlenN' : N.length = E.X.length + E.B.length + E.A.length + E.Y.length := by
        rw [hlenN]
        dsimp [word_block_exchange_after]
        repeat rw [List.length_append]
      have hsplit := word_block_exchange_transport_back_is_mask_iff_list_split_four N E.X.length E.B.length E.A.length E.Y.length hlenN'
      rcases hsplit with ⟨h1, h2, h3, h4, hN_eq⟩
      set p1 := N.take E.X.length
      set p2 := (N.drop E.X.length).take E.B.length
      set p3 := (N.drop (E.X.length + E.B.length)).take E.A.length
      set p4 := N.drop (E.X.length + E.B.length + E.A.length)
  6. The backward-transported mask has length equal to the word before exchange (word_block_exchange_before E).

    By definition, the transported mask is p₁ ++ p₃ ++ p₂ ++ p₄, and the word before exchange is E.X ++ E.A ++ E.B ++ E.Y. Distributing lengths over concatenation via List.length_append, the sums of lengths coincide by linear integer arithmetic (omega).

    lines 93–97

    uses List.length_append

      have htb_len : (word_block_exchange_transport_back E N).length =
          (word_block_exchange_before E).length := by
        change (p1 ++ p3 ++ p2 ++ p4).length = (E.X ++ E.A ++ E.B ++ E.Y).length
        repeat rw [List.length_append]
        omega
  7. The projections of the word before exchange under the transported mask and of the word after exchange under N decompose into four individual block projections.

    Applying word_block_exchange_transport_back_is_mask_iff_word_proj_four to the decompositions N = p₁ ++ p₂ ++ p₃ ++ p₄ and word_block_exchange_transport_back E N = p₁ ++ p₃ ++ p₂ ++ p₄, the projections along both true and false distribute across the four blocks X, B, A, Y and X, A, B, Y respectively.

    lines 98–119

    uses word_block_exchange_transport_back_is_mask_iff_word_proj_four

      have hu_proj : word_proj true (word_block_exchange_after E) N =
          word_proj true E.X p1 ++ word_proj true E.B p2 ++ word_proj true E.A p3 ++ word_proj true E.Y p4 := by
        have : word_block_exchange_after E = E.X ++ E.B ++ E.A ++ E.Y := rfl
        rw [this, hN_eq]
        exact word_block_exchange_transport_back_is_mask_iff_word_proj_four true E.X E.B E.A E.Y p1 p2 p3 p4 h1 h2 h3
      have hv_proj : word_proj false (word_block_exchange_after E) N =
          word_proj false E.X p1 ++ word_proj false E.B p2 ++ word_proj false E.A p3 ++ word_proj false E.Y p4 := by
        have : word_block_exchange_after E = E.X ++ E.B ++ E.A ++ E.Y := rfl
        rw [this, hN_eq]
        exact word_block_exchange_transport_back_is_mask_iff_word_proj_four false E.X E.B E.A E.Y p1 p2 p3 p4 h1 h2 h3
      have hu_tb : word_proj true (word_block_exchange_before E) (word_block_exchange_transport_back E N) =
          word_proj true E.X p1 ++ word_proj true E.A p3 ++ word_proj true E.B p2 ++ word_proj true E.Y p4 := by
        have : word_block_exchange_before E = E.X ++ E.A ++ E.B ++ E.Y := rfl
        have htb_eq : word_block_exchange_transport_back E N = p1 ++ p3 ++ p2 ++ p4 := rfl
        rw [this, htb_eq]
        exact word_block_exchange_transport_back_is_mask_iff_word_proj_four true E.X E.A E.B E.Y p1 p3 p2 p4 h1 h3 h2
      have hv_tb : word_proj false (word_block_exchange_before E) (word_block_exchange_transport_back E N) =
          word_proj false E.X p1 ++ word_proj false E.A p3 ++ word_proj false E.B p2 ++ word_proj false E.Y p4 := by
        have : word_block_exchange_before E = E.X ++ E.A ++ E.B ++ E.Y := rfl
        have htb_eq : word_block_exchange_transport_back E N = p1 ++ p3 ++ p2 ++ p4 := rfl
        rw [this, htb_eq]
        exact word_block_exchange_transport_back_is_mask_iff_word_proj_four false E.X E.A E.B E.Y p1 p3 p2 p4 h1 h3 h2
  8. The transported mask is a valid mask for u, v on the word before exchange if and only if N commutes for E.

    Unfolding is_word_mask and word_block_exchange_is_commuting, the length condition is satisfied by htb_len and eliminated via true_and. Substituting the block decompositions into the projections, the condition that they equal u and v becomes an equality of four-block concatenations with outer blocks X and Y. Applying word_block_exchange_transport_back_is_mask_iff_append_four_cancel cancels the outer blocks for both boolean values, leaving exactly the commutation relations AU ++ BU = BU ++ AU and AV ++ BV = BV ++ AV.

    lines 120–127

    uses true_and, word_block_exchange_transport_back_is_mask_iff_append_four_cancel

      rw [huN] at hu_proj
      rw [hvN] at hv_proj
      dsimp [is_word_mask, word_block_exchange_is_commuting]
      simp only [htb_len, true_and]
      rw [hu_tb, hv_tb]
      rw [hu_proj, hv_proj]
      rw [word_block_exchange_transport_back_is_mask_iff_append_four_cancel,
          word_block_exchange_transport_back_is_mask_iff_append_four_cancel]
List.length_cons
The length of a list with an element prepended is one plus the length of the tail.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
word_block_exchange_transport_back_is_mask_iff_word_proj_append
Projection of a concatenated word along a concatenated mask splits into the concatenation of the projections, provided the first mask and word have equal length.
List.append_cancel_right
If two concatenated lists with identical suffixes are equal, their prefixes are equal.
List.append_assoc
List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
List.append_cancel_left
If two concatenated lists with identical prefixes are equal, their suffixes are equal.
List.length_take
Taking i elements from a list yields a list whose length is the minimum of i and the length of the list.
List.length_drop
Dropping i elements from a list yields a list whose length is the original length minus i.
List.take_append_drop
For any index i, concatenating the first i elements of a list with the remainder reconstructs the original list.
List.drop_drop
Dropping i elements after dropping j elements is equivalent to dropping j + i elements.
word_block_exchange_transport_back_is_mask_iff_list_split_four
A list whose length is n₁ + n₂ + n₃ + n₄ partitions into four contiguous sublists of lengths n₁, n₂, n₃, n₄ that concatenate to the original list.
word_block_exchange_transport_back_is_mask_iff_word_proj_four
Projection of a four-block concatenation along a four-block mask splits into the concatenation of the four individual projections when corresponding block lengths match.
true_and
A conjunction True ∧ p simplifies to p.
word_block_exchange_transport_back_is_mask_iff_append_four_cancel
Two four-block lists differing only in the order of their middle two blocks are equal if and only if the middle two blocks commute under concatenation.

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

lemma word_block_exchange_transport_back_is_mask_iff_word_proj_append {α : Type*} (b : Bool)    (w1 w2 : List α) (m1 m2 : List Bool) (h : m1.length = w1.length) :    word_proj b (w1 ++ w2) (m1 ++ m2) = word_proj b w1 m1 ++ word_proj b w2 m2 := by  induction' w1 with x xs ih generalizing m1  · cases m1    · simp [word_proj]    · cases h  · cases m1    · cases h    · simp only [List.length_cons] at h      injection h with h'      dsimp [word_proj]      split_ifs with heq      · simp [ih _ h']      · exact ih _ h'lemma word_block_exchange_transport_back_is_mask_iff_word_proj_four {α : Type*} (b : Bool)    (w1 w2 w3 w4 : List α) (m1 m2 m3 m4 : List Bool)    (h1 : m1.length = w1.length) (h2 : m2.length = w2.length)    (h3 : m3.length = w3.length) :    word_proj b (w1 ++ w2 ++ w3 ++ w4) (m1 ++ m2 ++ m3 ++ m4) =      word_proj b w1 m1 ++ word_proj b w2 m2 ++ word_proj b w3 m3 ++ word_proj b w4 m4 := by  have l12 : (m1 ++ m2).length = (w1 ++ w2).length := by simp [h1, h2]  have l123 : (m1 ++ m2 ++ m3).length = (w1 ++ w2 ++ w3).length := by    repeat rw [List.length_append]    omega  rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b (w1 ++ w2 ++ w3) w4 (m1 ++ m2 ++ m3) m4 l123]  rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b (w1 ++ w2) w3 (m1 ++ m2) m3 l12]  rw [word_block_exchange_transport_back_is_mask_iff_word_proj_append b w1 w2 m1 m2 h1]lemma word_block_exchange_transport_back_is_mask_iff_append_four_cancel {α : Type*} (x a b y : List α) :    x ++ a ++ b ++ y = x ++ b ++ a ++ y ↔ a ++ b = b ++ a := by  constructor  · intro h    have h1 := List.append_cancel_right h    rw [List.append_assoc, List.append_assoc] at h1    exact List.append_cancel_left h1  · intro h    congr 1    rw [List.append_assoc, h, ← List.append_assoc]lemma word_block_exchange_transport_back_is_mask_iff_list_split_four {α : Type*} (l : List α) (n1 n2 n3 n4 : ℕ)    (h : l.length = n1 + n2 + n3 + n4) :    let p1 := l.take n1    let p2 := (l.drop n1).take n2    let p3 := (l.drop (n1 + n2)).take n3    let p4 := l.drop (n1 + n2 + n3)    p1.length = n1 ∧ p2.length = n2 ∧ p3.length = n3 ∧ p4.length = n4 ∧    l = p1 ++ p2 ++ p3 ++ p4 := by  dsimp  have h1 : (l.take n1).length = n1 := by    rw [List.length_take]    omega  have h2 : ((l.drop n1).take n2).length = n2 := by    rw [List.length_take, List.length_drop]    omega  have h3 : ((l.drop (n1 + n2)).take n3).length = n3 := by    rw [List.length_take, List.length_drop]    omega  have h4 : (l.drop (n1 + n2 + n3)).length = n4 := by    rw [List.length_drop]    omega  refine ⟨h1, h2, h3, h4, ?_⟩  have eq1 : l = l.take n1 ++ l.drop n1 := (List.take_append_drop n1 l).symm  have eq2 : l.drop n1 = (l.drop n1).take n2 ++ (l.drop n1).drop n2 :=    (List.take_append_drop n2 (l.drop n1)).symm  have eq3 : (l.drop (n1 + n2)) = (l.drop (n1 + n2)).take n3 ++ (l.drop (n1 + n2)).drop n3 :=    (List.take_append_drop n3 (l.drop (n1 + n2))).symm  rw [List.drop_drop] at eq2  rw [eq3] at eq2  rw [List.drop_drop] at eq2  rw [eq2] at eq1  rw [List.append_assoc, List.append_assoc]  exact eq1/-- Lemma 2: Transporting a mask N of XBAY back to XABY preserves source projections iff N commutes. -/theorem word_block_exchange_transport_back_is_mask_iff {α : Type*}    (E : WordBlockExchange α) (u v : List α) (N : List Bool)    (hN : is_word_mask u v (word_block_exchange_after E) N) :    is_word_mask u v (word_block_exchange_before E) (word_block_exchange_transport_back E N) ↔      word_block_exchange_is_commuting E N := by  rcases hN with ⟨hlenN, huN, hvN⟩  have hlenN' : N.length = E.X.length + E.B.length + E.A.length + E.Y.length := by    rw [hlenN]    dsimp [word_block_exchange_after]    repeat rw [List.length_append]  have hsplit := word_block_exchange_transport_back_is_mask_iff_list_split_four N E.X.length E.B.length E.A.length E.Y.length hlenN'  rcases hsplit with ⟨h1, h2, h3, h4, hN_eq⟩  set p1 := N.take E.X.length  set p2 := (N.drop E.X.length).take E.B.length  set p3 := (N.drop (E.X.length + E.B.length)).take E.A.length  set p4 := N.drop (E.X.length + E.B.length + E.A.length)  have htb_len : (word_block_exchange_transport_back E N).length =      (word_block_exchange_before E).length := by    change (p1 ++ p3 ++ p2 ++ p4).length = (E.X ++ E.A ++ E.B ++ E.Y).length    repeat rw [List.length_append]    omega  have hu_proj : word_proj true (word_block_exchange_after E) N =      word_proj true E.X p1 ++ word_proj true E.B p2 ++ word_proj true E.A p3 ++ word_proj true E.Y p4 := by    have : word_block_exchange_after E = E.X ++ E.B ++ E.A ++ E.Y := rfl    rw [this, hN_eq]    exact word_block_exchange_transport_back_is_mask_iff_word_proj_four true E.X E.B E.A E.Y p1 p2 p3 p4 h1 h2 h3  have hv_proj : word_proj false (word_block_exchange_after E) N =      word_proj false E.X p1 ++ word_proj false E.B p2 ++ word_proj false E.A p3 ++ word_proj false E.Y p4 := by    have : word_block_exchange_after E = E.X ++ E.B ++ E.A ++ E.Y := rfl    rw [this, hN_eq]    exact word_block_exchange_transport_back_is_mask_iff_word_proj_four false E.X E.B E.A E.Y p1 p2 p3 p4 h1 h2 h3  have hu_tb : word_proj true (word_block_exchange_before E) (word_block_exchange_transport_back E N) =      word_proj true E.X p1 ++ word_proj true E.A p3 ++ word_proj true E.B p2 ++ word_proj true E.Y p4 := by    have : word_block_exchange_before E = E.X ++ E.A ++ E.B ++ E.Y := rfl    have htb_eq : word_block_exchange_transport_back E N = p1 ++ p3 ++ p2 ++ p4 := rfl    rw [this, htb_eq]    exact word_block_exchange_transport_back_is_mask_iff_word_proj_four true E.X E.A E.B E.Y p1 p3 p2 p4 h1 h3 h2  have hv_tb : word_proj false (word_block_exchange_before E) (word_block_exchange_transport_back E N) =      word_proj false E.X p1 ++ word_proj false E.A p3 ++ word_proj false E.B p2 ++ word_proj false E.Y p4 := by    have : word_block_exchange_before E = E.X ++ E.A ++ E.B ++ E.Y := rfl    have htb_eq : word_block_exchange_transport_back E N = p1 ++ p3 ++ p2 ++ p4 := rfl    rw [this, htb_eq]    exact word_block_exchange_transport_back_is_mask_iff_word_proj_four false E.X E.A E.B E.Y p1 p3 p2 p4 h1 h3 h2  rw [huN] at hu_proj  rw [hvN] at hv_proj  dsimp [is_word_mask, word_block_exchange_is_commuting]  simp only [htb_len, true_and]  rw [hu_tb, hv_tb]  rw [hu_proj, hv_proj]  rw [word_block_exchange_transport_back_is_mask_iff_append_four_cancel,      word_block_exchange_transport_back_is_mask_iff_append_four_cancel]
See it in the graphDiscuss this resultChallenge it