GPT-5.6 Sol · elicited by @eternalism_4eva

What is matrix mortality?#

For fixed positive integers d and k, Md(k) asks: given at most k integer d × d matrices, does some nonempty product equal the zero matrix?

Ai1 Ai2 ⋯ Ain = 0, n≥1.

The matrix entries and witness length are unbounded. Multiplication retains the order of the selected generators, so a product is a word over a finite noncommutative alphabet.

Mortality is semidecidable: enumerate products by length and stop when zero appears. Decidable means that an algorithm also terminates correctly when no zero product exists. An undecidability theorem rules out such an algorithm for all inputs; it does not say that each individual input is difficult.

Two related problems retain only one scalar coefficient. Zd(k) supplies a row L and column C and asks whether LYC = 0 for some nonempty product Y of at most k integer d × d matrices. Rd(k) fixes the coefficient to one matrix corner. The structured form Z̊ additionally requires every generator to have first column e1.

The table records what is settled. The module graph gives the constructions and proofs behind those entries; the glossary defines their vocabulary. A reduction from one problem to another transfers undecidability toward the target and decidability back toward the source.

Decidability table#

Undecidability is monotone in both parameters. Extra generators may be ignored, and dimension padding preserves mortality:

A↦A⊕0.

Combining these constructions with the established reductions of Cassaigne, Halava, Harju, and Nicolas, the coordinatewise-minimal undecidable points (none follows from another just by increasing parameters) are

Z: Z3(4),Z4(3),Z6(2); R: R3(5),R4(4),R5(3),R7(2); M: M3(5),M4(4),M6(3),M8(2).
Decidability of Md(k): literature audited through 24 July 2026; repository results through 5 September 2026
d \ k 1 2 3 4 5 ≥6
1DDDDDD
2DD????
3D???U★U
4D??U★U★U
5D??UUU
6–7D?U★UUU
8DU★U★UUU
9DU★UUUU
10–11DU★UUUU
12–14DU★UUUU
≥15DUUUUU

D means decidable, ? unresolved, and U undecidable. U★ marks cells first resolved by this series; each star links to the earliest article establishing the cell, directly or as a corollary. The remaining U entries follow from earlier work or monotonicity. Question marks report literature status; they encode no proposed method or prognosis.

Reference#

Modules#

The constructions have two tasks. Source recognition encodes a halting computation as equality of words, then as a zero scalar coefficient. Target compression turns that test into mortality with fewer generators or coordinates. The arithmetic modules instead analyze particular families without settling their open table entries.

For the basic reduction, start with the four word pairs and their five matrices. Each card links to the relevant statement or construction, not necessarily the beginning of its article. Requires links give mathematical prerequisites, not a mandatory reading order.

Kind
What the box states: a definition, a construction, a lemma, a reduction (a correctness-preserving translation), a theorem (a principal conclusion), an obstruction (a proved limit), or a witness.
Edges
Requires and Used by are the proof dependencies; other named links, such as Instantiates and Strengthens, are cross-references, not dependencies.

Foundations#

The mortality problem and the matrix language every construction is written in.

  1. Definition

    Matrix mortality

    Nonempty zero products in a finite family of integer matrices, with dimension and generator count fixed.

  2. Definition

    Word-pair representation

    A three-dimensional matrix morphism that records two ternary words and detects their equality in one coefficient.

  3. Definition

    Two-generator projective incidence

    Given two invertible rational 2 × 2 matrices, a source column and a target row, ask whether some word moves the column into the row’s kernel.

  4. Definition

    Shortcut-Collatz reachability

    Finite reachability of 1 under halving on even integers and (3n+1)/2 on odd integers.

Source Recognition#

The undecidable source problem and the four-dimensional scalar series that later constructions reuse.

  1. Theorem

    Fixed-boundary correspondence

    Four nonerasing word pairs recognize restricted tag halting when the terminal marker is fixed rather than selectable.

  2. Reduction

    Paired-role compression

    Two phase copies share an agreement subspace, replacing four linear actions by two data controls and a toggle.

  3. Construction

    Paired scalar series

    The four source roles are encoded by two data controls and one toggle; their four-dimensional scalar coefficient detects the decoded word equality.

Target Compression#

Reductions that turn scalar or interface zeros into unrestricted matrix products.

  1. Reduction

    Interface compression

    Partitioning an ordinary generator family into transitions and factored cuts reduces its cut-containing products exactly to paths of interface bridges; transition-only products remain a separate branch.

    Requires
    Matrix mortality

  2. Reduction

    Rank-one separator

    One repeated outer product turns a vanishing scalar coefficient into a matrix zero; the converse accounts for arbitrary products.

    Requires
    Matrix mortality
    Instantiates
    Interface compression

  3. Reduction

    Singular-return compression

    When no transition power vanishes, mortality of one transition and one cut is equivalent to mortality of their complete return family.

  4. Reduction

    Common-image restriction

    A decoder family is restricted to its common invariant image, with an appended-letter converse excluding new zero products.

  5. Lemma

    Effective denominator clearing

    Independent nonzero generator scalings convert a rational family to integer matrices while preserving and reflecting every zero product.

    Requires
    Matrix mortality

Binary and Return Constructions#

Realizations that reach fewer generators or lower dimension, built on the source series and the interface reduction.

  1. Construction

    Six-dimensional scalar compiler

    Two-bit codewords select the four source roles. Sharing the unfinished upper-word coordinates gives two matrices in dimension six.

  2. Reduction

    Generator packing

    A general alphabet reduction trades generator count for additional coordinate blocks, preserving mortality in both directions.

    Requires
    Matrix mortality

  3. Construction

    Binary prefix decoder

    A complete binary code represents the five source matrices on four three-dimensional decoder blocks; a synchronizing word handles every starting block.

    Instantiates
    Generator packing

  4. Construction

    Tilted separator

    An injective length-tilted ternary code changes the nonzero coefficients needed by the realization while preserving the complete zero language.

  5. Construction

    Nine-dimensional return realization

    Two length-three nilpotent chains, one length-two chain, and one eigenline realize three exceptional moments and a geometric tail.

    Requires
    Tilted separator

  6. Construction

    Valuation guard

    A three-mode return family forces one legal wait by a p-adic valuation and sends every wrong wait into a permanent trap.

  7. Lemma

    Periodic-prefix exclusion

    The compiler's bcb prefix and lower-tile grammar exclude every competing capped period, ruling out all asymmetric wrong-phase zeros.

  8. Construction

    Asymmetric separator

    Only erase-phase equalities remain zero; a leading toggle recovers every discarded witness. Existence is preserved, not the pointwise zero language.

  9. Construction

    Eight-dimensional return realization

    Two length-three nilpotent chains, one static coordinate, and one eigenline realize a rescaled toggle, two data roles, and the asymmetric separator tail.

Arithmetic Incidence#

Where two-generator projective incidence meets arithmetic dynamics, including its shortcut-Collatz instance.

  1. Reduction

    Shortcut-Collatz incidence

    Two fixed fractional-linear maps recognize exactly those supplied integers that reach 1 under shortcut Collatz, by a scalar-zero test.

  2. Reduction

    Rank-two projective-incidence compiler

    Every generic two-generator projective-incidence instance compiles to two rational 3 × 3 matrices of rank exactly two, with mortality equivalent to incidence zero.

    Instantiates
    Interface compression

Established Obstructions#

Limits proved for specified constructions, not impossibility results for the unresolved table entries.

  1. Obstruction

    Tilted-geometric rank floor

    One fixed source instance requires nine dimensions throughout the stated tilted geometric-tail family; the bound concerns exact realizations of those returns.

    Requires
    Tilted separator

  2. Obstruction

    Valuation barriers

    Parity and prime-divisibility conditions prove that specified guarded families have no zero product.

    Requires
    Valuation guard

Frontier Constructions#

Constructions establishing current frontier bounds. Consequences obtained only by applying an existing transport are listed separately below.

  1. Theorem

    M₃(5) is undecidable

    Four fixed-boundary payload matrices and one repeated rank-one separator give five 3 × 3 integer matrices.

  2. Theorem

    M₄(4) is undecidable

    Paired-role compression gives three 4 × 4 scalar controls; one rank-one separator converts their zero coefficient to mortality.

  3. Theorem

    M₈(2) is undecidable

    Existential phase selection and an eight-dimensional return realization give a primitive-recursive pair of integer matrices, mortal exactly when its source program halts.

  4. Theorem

    Z₆(2) is undecidable

    The shared-partial compiler preserves the paired coefficient under every binary word in dimension six.

Subsumed Constructions#

Mortality constructions whose endpoint now follows from a sharper frontier theorem, retained for their distinct mechanisms.

  1. Theorem

    M₉(2) is undecidable

    A zero-language-equivalent separator and a nine-dimensional return realization give a primitive-recursive pair of integer matrices.

  2. Theorem

    M₁₀(2) is undecidable

    A complete binary prefix decoder followed by common-image restriction gives two 10 × 10 integer matrices.

Transported Bounds#

Corollaries of existing packing or scalar-to-corner reductions, not separate constructions. A transported bound may still lie on the numerical frontier.

  1. Theorem

    M₆(3) is undecidable

    Applying generator packing to M₃(5) gives M₆(3). This is a frontier bound, not a separate construction.

  2. Theorem

    R₇(2) is undecidable

    The scalar-to-corner transport converts the six-dimensional two-generator scalar theorem to a seven-dimensional corner theorem.

  3. Theorem

    M₁₂(2) is undecidable

    Applying generator packing to M₃(5) gives M₁₂(2). The bound is now subsumed by M₈(2).