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

arXiv:2610.39941 · cs.FL, math.CO · Submitted 2026-10-29 · Read on arXiv

cs.FL, math.CO

Submitted: 2026-10-29

Updated: 2026-11-10

Comments: 22 pages, 10 tables. Software and verification data: https://github.com/the-omega-institute/insertion-degree-descent/releases/tag/v1.0

Code: https://github.com/the-omega-institute/insertion-degree-descent

License: http://creativecommons.org/licenses/by/4.0/

The gist: For fixed nonempty words u,v, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations.

Abstract

For fixed nonempty words u,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 r, the minimum over masks with commuting source projections is exactly r-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.

Sources

Related papers