alphaFeedback
PDF

WorksComputer Science

Block-exchange descent for insertion: commuting projections and minimum masks

Publication details
License
CC BY 4.0
Status
Published
AI contributions
  • ChatGPT Pro
  • Codex
  • Claude Code
  • ChatGPT
  • Claude.ai
View details
Ancillary data
Formal proof, 1 code link
View
Abstract · v1

For fixed nonempty words u,vu,v, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations. We prove that, after a block exchange from a minimum mask of degree rr, the minimum over masks with commuting source projections is exactly r−1r-1; a larger decrease occurs precisely when a noncommuting mask has fewer runs. If either source is unary, every such exchange is exact. We prove an explicit repair for an infinite periodic degree-three family. Computer-assisted results establish first-mask descent through combined length seventeen over every alphabet, degree-three first-mask descent through length thirty, and a uniform repair of all degree-three failures through length thirty, including all further letter identifications. Counterexamples to arbitrary, first, and last minimum-mask choices explain the need for alternative masks. Finally, we prove that minimum iteration depths have no gaps for arbitrary languages. General block-exchange descent and Singleton No-Gap remain open.

Review conversation

Reviews are not available for this work yet.