AFTD Auto-Formalizing Theoretical Domains

word_block_exchange_b

def

The noncommuting minimum degree word_block_exchange_b E u v is the infimum in WithTop Nat of mask_u_runs N over all noncommuting masks N of the exchanged word word_block_exchange_after E satisfying is_word_mask u v (word_block_exchange_after E) N and ¬ word_block_exchange_is_commuting E N.

Statement

noncomputable def word_block_exchange_b {α : Type*} (E : WordBlockExchange α) (u v : List α) : WithTop ℕ
Defined in
arXiv:2610.39941, Section 4, equation (2)
Verified
31 Oct 2026
Axioms
none listed
Built on 5
  • mask_u_runsThe number of maximal nonempty U-runs in a binary mask M is defined by mask_u_runs M = mask_u_runs_aux false M, counting contiguous blocks…
  • 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…

Read back from the Lean

For a type α, a block exchange configuration E : WordBlockExchange α (with components X, A, B, Y : List α), and two lists u, v : List α, word_block_exchange_b E u v is defined as the infimum in WithTop ℕ of the set of run counts mask_u_runs N over all boolean lists N : List Bool satisfying: 1. N is a mask that decomposes word_block_exchange_after E (which is E.X ++ E.B ++ E.A ++ E.Y) into u (the elements at indices where N is true) and v (the elements at indices where N is false); and 2. N is not commuting with respect to E, meaning that it is not the case that both: - the projection of E.A onto true under the slice of N corresponding to E.A commutes (under concatenation) with the projection of E.B onto true under the slice of N corresponding to E.B, and - the projection of E.A onto false under the slice of N corresponding to E.A commutes (under concatenation) with the projection of E.B onto false under the slice of N corresponding to E.B. If no such mask N exists, the infimum is ⊤ (infinity).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Minimum run count over all noncommuting masks of XBAY for exchange E, or top if none exists. -/
noncomputable def word_block_exchange_b {α : Type*} (E : WordBlockExchange α) (u v : List α) : WithTop ℕ :=
  sInf { (mask_u_runs N : WithTop ℕ) | (N : List Bool) (_ : is_word_mask u v (word_block_exchange_after E) N) (_ : ¬ word_block_exchange_is_commuting E N) }
See it in the graphDiscuss this resultChallenge it