word_block_exchange_transport_back_is_mask_iff
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.
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.
uses
List.length_consinduction' 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'
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.
uses
List.length_append,word_block_exchange_transport_back_is_mask_iff_word_proj_appendhave 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]
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.
uses
List.append_cancel_right,List.append_assoc,List.append_cancel_leftconstructor · 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]
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.
uses
List.length_take,List.length_drop,List.take_append_drop,List.drop_drop,List.append_assocdsimp 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
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₄.
uses
List.length_append,word_block_exchange_transport_back_is_mask_iff_list_split_fourrcases 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)
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).
uses
List.length_appendhave 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
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.
uses
word_block_exchange_transport_back_is_mask_iff_word_proj_fourhave 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
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.
uses
true_and,word_block_exchange_transport_back_is_mask_iff_append_four_cancelrw [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
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.
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]