PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Haobo Ma, Wenlin Zhang, Charles E. Hughes

arXiv:2610.39941v1cs.FLmath.CO

TL;DR

The paper asks when minimum insertion degrees of shuffle outputs admit exact one-step descent, a route to the Singleton No-Gap property. It characterizes the obstruction through commuting source projections and proves special-case and bounded results, while the general descent and Singleton No-Gap questions remain open.

  • Problem

    For fixed nonempty words, the paper asks whether block exchanges can always produce a shuffle of degree exactly one less, yielding consecutive attainable minimum degrees.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes source masks and characterizes exact exchange descent by whether alternative source projections commute.

    Source: §1 · p. 2

  • Results

    Minimum iteration depths have no gaps for arbitrary source languages, and every exchange from every minimum mask is exact when either source is unary.

    Source: §1 · p. 2, §5 · p. 7

  • Takeaways & Limitations

    For a fixed exchange, commuting representations bottom out at r−1 runs, so any larger degree drop must come from a noncommuting representation.

    Source: §1 · p. 2

    General block-exchange descent and Singleton No-Gap remain open; the finite results do not establish the unbounded existence step.

    Source: §10 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

The paper studies the minimum number of inserted-source blocks needed to produce a shuffle and whether attainable minimum degrees have gaps. It characterizes when a block exchange descends exactly, proves several special-case and bounded results, and leaves general block-exchange descent and Singleton No-Gap open.

1 Introduction

  • The minimum insertion degree is the least number of inserted blocks over all representations of an output, since source letters can have ambiguous origins.For sources 00 and 11, 0011 has degree 1 while 0110 has degree 2.Source: §1 · p. 1
  • The Singleton No-Gap question asks whether the degrees attained by shuffle outputs contain every positive integer up to their maximum.An exact predecessor at each degree would give repeated descent through those degrees.Source: §1 · p. 2
  • For a minimum mask of degree r, exchanging a separating base block with a neighboring inserted run yields a representation with r−1 runs, but another representation may lower the output’s minimum degree further.The paper asks whether some minimum mask always gives an exact degree-(r−1) predecessor.Source: §1 · p. 2
  • The exact obstruction is a noncommuting mask: among masks whose source projections commute, the exchanged output has minimum run count exactly r−1.A larger decrease in minimum insertion degree must come from a noncommuting mask.Source: §1 · p. 2
  • Every block exchange from every minimum mask is exact when either source is unary, and an explicit repair is proved for an infinite periodic family of degree-three obstructions.Counterexamples show that arbitrary, lexicographically first, and lexicographically last minimum masks cannot always be selected.Source: §1 · p. 2
  • Minimum iteration depths have no gaps for arbitrary source languages, but general block-exchange descent and Singleton No-Gap remain open.Iteration depth counts successive insertion steps, unlike insertion degree, which counts blocks within one step.Source: §1 · p. 2

2 Related work

Related work treats insertion, shuffle, and deletion through language operations, bounded factorizations, trajectories, and shuffle decomposition. This paper instead minimizes inserted-source runs for an output of two fixed source words, using source-grid dynamic programming and word commutation to study descent.

2 Related work

  • Earlier insertion and deletion studies focus on language generation, preservation, or closure, whereas this paper minimizes inserted blocks for an output from fixed sources.The cited works include Haussler, Kari, Kari and Thierrin, and Ito, Kari, and Thierrin.Source: §2 · p. 3
  • The n-insertion framework and bounded-shuffle closure connect to few-block interleavings, but count paired factors rather than the paper’s maximal inserted-source runs.A mask with k inserted runs corresponds to a paired factorization with k + 1 pairs, allowing an empty endpoint factor.Source: §2 · p. 3
  • Trajectory constraints encode interleavings with at most k inserted runs, while distinct trajectories can emit the same word and make minimum-degree descent nontrivial.In trajectory terminology, the minimum degree is the least k whose regular trajectory language represents the output.Source: §2 · p. 3
  • Shuffle decomposition studies recovering language factors, unlike this paper’s minimization over representations of fixed words; the source-grid dynamic program computes membership and minimum degree.The paper uses a weighted grid for exchange formulas and symbolic equality-partition tests.Source: §2 · p. 3
  • Classical word commutation and periodicity results inform the obstruction analysis, while Hughes [7, Sections 10–11] posed the motivating spectrum questions.Hughes proved iteration-depth No-Gap for finite languages and the unary-source singleton degree spectrum; this paper extends the former to arbitrary languages and strengthens the latter’s exchange conclusion.Source: §2 · p. 3

3 Preliminaries

The preliminaries define shuffle masks, insertion degree, and block exchange for fixed nonempty ordered sources. These definitions turn the descent question into minimizing the number of maximal inserted-source runs over all representations.

3 Preliminaries

  • A mask labels each output position by its source, and its U- and V-projections must recover the inserted word u and base word v.The shuffle preserves each source’s internal order.Source: §3 · p. 4
  • The insertion degree d(w) is the minimum number of maximal U-runs among masks of w, and D(u, v) collects these degrees over all shuffles.A k-insertion factorization gives the same least positive k as the mask definition.Source: §3 · p. 4
  • A block exchange swaps a separating V-block with a neighboring U-run, merging two U-runs and giving a successor of degree at most r−1.The exchange is exact when the successor’s minimum degree is r−1; a mask is bad if none of its exchanges is exact.Source: §3 · p. 4
  • A word is primitive when it is not a proper power, and every nonempty word has a unique primitive root.A primitive word cannot be fixed by a nontrivial cyclic rotation through fewer than its length’s full period.Source: §3 · p. 4

4 The exchange and its exact obstruction

The exchange theorem identifies commuting source projections as the exact boundary between the guaranteed r−1-run representation and any further decrease. The section also gives source-grid and prefix-bound methods for testing the obstruction and certifying some swaps.

4 The exchange and its exact obstruction

  • A block exchange changes the run count of any transported binary labeling by at most one, and the source projections transport back to the original sources exactly when the exchanged factors commute.For each source, the condition is that its projections of the exchanged factors commute; empty projections commute with every word.Source: §4 · pp. 4–5
  • Among masks of the exchanged output whose source projections commute, the minimum run count is r−1; the output degree is min(r−1, bE(z)), where bE(z) is the least run count among noncommuting masks.Thus the exchange is exact iff bE(z) ≥ r−1, and only a shorter noncommuting representation can cause a larger decrease.Source: §4 · p. 5
  • For an adjacent swap, commuting masks assign the unequal letters to different sources; assigning both to one source cannot satisfy commutation.This specializes the general criterion to the different-source and same-source minimum formula.Source: §4 · p. 5

4.1 A source-grid formula

  • The source-grid formula tests the noncommuting minimum by splitting paths at three block boundaries and minimizing run costs over compatible boundary states.The test accounts for alternative masks with different source consumptions at those boundaries.Source: §4.1 · pp. 5–6
  • The weighted source grid uses states recording consumed letters and the previous source, charging one when a U-run starts and zero for a V step.Segment path costs can be combined across the exchanged factors and surrounding prefix and suffix.Source: §4.1 · p. 5

4.2 Prefix lower bounds

  • Prefix lower bounds combine the least prefix run count with the least suffix completion cost at a shared source state, including constrained minima for specified labels.For a profile-certified swap, the bound implies the swapped word’s degree is at least the original degree minus one.Source: §4.2 · p. 6

5 Cases in which every exchange is exact

Every block exchange from a minimum mask is exact when either source is unary. Exactness also holds for disjoint source alphabets and for every exchange at degree two.

5 Cases in which every exchange is exact

  • If either source is unary, every block exchange from a minimum mask of degree r > 1 produces degree exactly r −1.For u = a^m, each occupied gap requires one U-run, and an exchange empties exactly one occupied gap; for v = a^n, the minimum degree is one plus the number of positive internal gaps, and an exchange removes exactly one such gap.Source: §5 · pp. 6–7
  • The first pointwise formula follows Hughes’s unary-source spectrum theorem [7, Section 11, Theorem 9]; the second formula and both exact-exchange conclusions follow from the minimum-mask structure proved here.Source: §5 · p. 7
  • D(a^m, v) = {1, . . . , min(m, s(v) + 1)} and D(u, a^n) = {1, . . . , 1 + min(n, max(0, s(u) −1))}.The constructions distribute inserted letters among gaps in the first case and occupy internal gaps while placing remaining base letters at an outer end in the second.Source: §5 · p. 7
  • With disjoint source alphabets, letters uniquely determine every mask, so the intended exchanged mask is the only mask and the exchange is exact.For arbitrary sources, every exchange at degree two is also exact: it has a one-run mask, and nonempty u forces degree at least one.Source: §5 · p. 7

6 Why the minimum mask and separator matter

Examples show that arbitrary, first, and last minimum masks—and simple separator rules—cannot guarantee an exact one-degree block-exchange descent. The counterexamples motivate searching among alternative masks and separators, with a further example showing that local label-shift restrictions do not characterize the obstruction.

6 Why the minimum mask and separator matter

  • A degree-four word has a minimum mask whose six exchanges all yield degree two, although another minimum mask has an exact degree-three exchange.This shows that an arbitrary minimum-mask choice can fail even when a suitable mask exists.Source: §6 · p. 7
  • For k = ℓ = 2, a degree-three periodic example has a minimum mask whose first-separator exchanges all yield degree one, while its first minimum mask has an exact degree-two exchange.The construction has twelve masks, each with three U-runs.Source: §6 · p. 8
  • At total length seventeen, a degree-three example has a first minimum mask whose six exchanges all yield degree two, while another minimum mask gives an exact degree-two predecessor.The arbitrary-mask failure persists at every binary length at least seventeen.Source: §6 · pp. 8–10
  • In degree-three examples, shortest- and longest-separator choices from the first minimum mask can both fail, even though another separator gives an exact degree-two predecessor.The table’s position checks allow ties among shortest and longest separators.Source: §6 · p. 9, Table 2 · p. 9
  • At length twenty, the last minimum mask of a degree-four word has six degree-two exchanges, but the first minimum mask has an exact degree-three exchange.The exhaustive mask check confirms the distinct successor degrees; neither extremal minimum mask is a universal choice.Source: §6 · p. 10
  • A degree-seven example defeats both end-separator moves of its first minimum mask, with each producing degree five.Disjoint left and right gadgets each have degree three and end moves of degree one; the forced markers isolate one extra U-run, making the global degree the sum of local degrees plus one before and after the moves.Source: §6 · p. 10

6.1 Label shifts and a further counterexample

  • Whole-factor label shifts are absent in a packed example, yet its selected minimum mask still has six degree-two exchanges.The example’s three internal separator/run pairs and leading pair fail the stated suffix or prefix conditions for those shifts.Source: §6.1 · p. 11, Table 5 · p. 11
  • The packed example’s first minimum mask has an exact degree-three exchange, whose degree is verified by enumerating all twenty-one masks of its successor.This shows that excluding the described label shifts does not characterize the obstruction.Source: §6.1 · p. 11

7 A periodic repair at degree three

A common-period structure permits a label shift that preserves the source words and run count; for an explicit infinite periodic degree-three family, the shifted mask has an exact descent exchange. The repair also covers a family with larger non-A blocks by contracting those blocks to single letters.

7.1 A label shift under a common-period hypothesis

  • Under the common-period hypothesis, a label shift preserves both source projections and the three-run count, but does not by itself establish an exact exchange.The shifted mask is earlier under U < V.Source: §7.1 · p. 12

7.2 Exact repair for an infinite family

  • For the explicit family, the shifted mask’s 1L exchange produces an output of minimum insertion degree two.The proof rules out a one-run mask for that output.Source: §7.2 · pp. 12–13
  • A finite search found 371 degree-three instances among 2,401 parameter tuples and no exception to the stated parameter criterion, but that evidence does not prove it generally.The theorem retains its explicit condition that du,v(w) = 3.Source: §7.2 · p. 13
  • For h = j = 1 and k, ℓ ≥ 2, the shifted alternative minimum mask has an exchange producing degree two from degree three.The construction therefore repairs every bad mask in this family without choosing an extremal mask.Source: §7.2 · pp. 12–13
  • The repair extends to any nonempty word S containing no A by contracting each pure S-block to a single letter.This includes T = ABCA when S = BC.Source: §7.2 · p. 13

8 Computational results

The computational results combine exhaustive numerical and symbolic searches to test exact block-exchange descent across bounded domains. They establish several all-alphabet bounds and a uniform repair for degree-three failures through length thirty, while leaving general descent open.

8 Computational results

  • Table 6 organizes computational claims by their scope and evidence type; the section reports exhaustive searches, certificate checks, and independent regeneration as distinct evidence.Length denotes the combined source length, and all-alphabet claims use symbolic equality-pattern enumeration.Source: §8 · p. 13, Table 6 · p. 13

8.1 Numerical enumeration

  • In Proposition 10’s exhaustive domains, every degree-greater-than-one output has an exact exchange from both its first and last minimum masks, implying Singleton No-Gap there.The enumerations test both extremal masks, and repeated exact descent yields each lower degree with the same sources.Source: §8.1 · p. 14, Table 7 · p. 14

8.2 Symbolic enumeration and completeness

  • The symbolic search is complete for its tested lengths and degrees: surviving leaves represent counterexamples, and every counterexample is covered by a surviving equality partition or its coarsening.Independent checking verified 1,512 archived tuples, 896 source/output/mask instances, and 41,244 identification cuts through length thirty; higher-degree bounds rely on completed production searches and the reduction.Source: §8.2 · p. 15

8.3 Uniform repair of degree-three bad masks

  • Every degree-three minimum mask of combined length at most thirty with four degree-one exchanges has the stated common-period structure and a shift with successor degrees (2, 1, 1, 2).The period equations and shifted-degree vector persist under further letter identifications that preserve original degree three.Source: §8.3 · pp. 15–16

8.4 All-alphabet descent bounds

  • Through combined length seventeen, first-minimum-mask descent holds over every alphabet, and length eighteen is the smallest first-mask failure.The degree-three bound extends through length thirty; degree-four last-mask descent holds through length nineteen, with one failure at length twenty whose first mask descends.Source: §8.4 · p. 16
  • The all-alphabet bounds also show that at degree four and length eighteen the first-mask failure is unique up to renaming, while degree-five first-mask descent holds through length eighteen.At degree four, some minimum mask has an exact exchange at each degree 2 through 5 through length eighteen; no No-Gap assertion is made for degrees 6 through 9 at length eighteen.Source: §8.4 · p. 16

8.5 A structured binary domain

  • For all 70,710 pairs in the specified structured binary domain, each degree-greater-than-one output has exact exchanges from both extremal masks, and every degree-three minimum mask has at least one.The conclusion covers 20,001,166 outputs, including 8,861,068 of degree three, and is specific to that domain.Source: §8.5 · p. 17

8.6 The prefix test

  • Among labeled binary source pairs of combined length eight or nine, 168 degree-three triples have an eligible swap whose output has degree one, each at exactly one failed position.Of 116 triples with another eligible degree-two swap, 94 have one certified by the prefix test and 22 do not; for the remaining 52, it certifies an ordinary degree-two swap.Source: §8.6 · p. 17

9 Iteration depth for arbitrary languages

For arbitrary languages, iteration-depth spectra have no gaps: if a reachable word has minimum depth r, every depth from 0 through r is attained. The proof pads histories to a common insertion degree and shows a final predecessor has the preceding minimum depth.

9 Iteration depth for arbitrary languages

  • For arbitrary languages, a reachable word of minimum depth r implies reachable words at every depth q from 0 through r.This proves the Iteration-Depth No-Gap Conjecture without requiring monotonicity between successive iteration stages.Source: §9 · pp. 17–18
  • Padding empty source and base factors synchronizes insertion degrees, forcing the final predecessor of a depth r + 1 word to have minimum depth r.If its minimum depth were s < r through degree j, padding to K = max(j, k) would produce the final word at depth s + 1, contradicting minimality.Source: §9 · p. 18
  • The theorem is formalized in Lean 4 for arbitrary languages over arbitrary alphabet types, with no finiteness or countability assumptions.The formalized result uses one fixed positive insertion degree throughout each history.Source: §9 · p. 18

10 Conclusion and open problems

The paper establishes exact block-exchange results in specified settings but leaves general descent and Singleton No-Gap unresolved. It also proves a no-gap theorem for iteration depths of arbitrary languages, using a separate padding argument.

10 Conclusion and open problems

  • Commuting successor representations have minimum degree r −1; any further decrease comes from a noncommuting representation.Unary-source formulas remove that obstruction for every minimum mask, and an explicit label shift gives exact exchange for an infinite periodic degree-three family.Source: §10 · p. 18
  • General block-exchange descent remains open: whether every degree-r shuffle admits an exchange with no noncommuting representation of at most r−2 runs.An affirmative answer would prove Singleton No-Gap; finite results establish the conclusion through combined length seventeen, with larger bounds at selected degrees.Source: §10 · p. 18
  • At degree three, the open questions concern common primitive periods for bad masks and whether the proposed shift has an exact 1L exchange under arbitrary outer contexts.Theorem 9 proves the repair for its infinite family, while Proposition 11 answers both questions through length thirty.Source: §10 · p. 18
  • For arbitrary languages, iteration-depth No-Gap follows by padding histories to a common insertion degree, which makes the final predecessor attain the preceding minimum depth.This argument needs no assumption that successive iteration stages are monotone; language spectra still require a separate argument because competing source pairs can lower degrees.Source: §10 · p. 18

A Complete finite mask lists

The appendix records complete finite mask lists used in the paper’s completeness arguments. The lists cover all representations for specified sources and include examples where a first-mask successor has a lower minimum than the original word.

A Complete finite mask lists

Use of AI tools

The authors report using AI tools for literature search, computation, mathematical discussion, proof checking, and exposition. They state that the proofs can be checked by hand and computations reproduced from the verification package.

Use of AI tools

  • Ma and Zhang used AI tools for literature search, computation, double-checking, and Lean formal verification; Hughes used them for mathematical discussions, proof examination, and exposition.All authors state they take responsibility for the final manuscript; proofs can be checked by hand and computations reproduced from the verification package.Source: Use of AI tools · p. 21

Related papers

Loading 2610.39941v1…