A Valuation Guard in M₃(2)

In the open cell M₃(2), a four-parameter family of integer pairs is mortal exactly when a deterministic orbit of rational numbers, governed by a p-adic valuation, reaches 1.

Each pair consists of an invertible transition and a rank-two cut. Their returns act on the projective line: the return after no transition is a rank-one separator that tests for the point 1 and resets to a fixed point, and every longer return is a Möbius map that admits exactly one wait, determined by the valuation of the current point, and sends every other wait into a trap from which 1 is unreachable. The equivalence covers every product of the two matrices. The return series has exact dimension three.

Parity, Smith-form, and valuation arguments prove large parameter regions immortal, and a two-step orbit shows that four natural measures of progress fail. None of this decides M₃(2): no universal computation has been compiled into the orbit, and no decision procedure for the orbit is known.

Known Stuff#

The cell M₃(2)#

M₃(2) asks whether some nonempty product of two given 3 × 3 integer matrices is zero. Two 2 × 2 matrices are decidable [Bournez–Branicky 2002], so M₃(2) is the smallest open two-generator cell in the decidability table.

The cell splits by the ranks of the two generators. A zero generator is mortal and two invertible generators are not. A pair with a rank-one generator reduces to zeros of scalar linear recurrences of order at most three, which are decidable; this reduction is audited in the repository but not formalized. The open part of the cell therefore consists of the rank profiles (3, 2) and (2, 2); the second contains shortcut-Collatz incidence. This page studies the profile (3, 2): an invertible generator A and a rank-two generator C.

Return compression#

A split rank-two cut#

Over ℚ, factor the rank-two matrix through a two-dimensional interface:

C = U O, U : ℚ^{2} \to ℚ^{3}, O : ℚ^{3} \to ℚ^{2} .

A block beginning and ending with C then collapses to the interface. Define the return after n transition steps by

Γ_{n} = O A^{n} U \in ℚ^{2 \times 2} .

Return products#

For any waits n₁, …, n_k,

C A^{n_{1}} C A^{n_{2}} C \dots A^{n_{k}} C = U Γ_{n_{1}} Γ_{n_{2}} \dots Γ_{n_{k}} O .

Since A is invertible, no power of A vanishes, and singular-return compression shows that the pair {A, C} is mortal exactly when the infinite family {Γ_n} is.

The entries of Γ_n are linear recurrence sequences in n, but the problem is not a recurrence problem: a word chooses a different, unbounded n at every return and multiplies the resulting matrices. Linear recurrence automata provide nearby vocabulary for this controlled setting [Hirvensalo et al. 2024].

Two arithmetic languages#

The projective line#

A nonzero column (x,y)^T determines the projective point z = x/y. Columns differing by a nonzero scalar represent the same point; y = 0 represents infinity. An invertible 2 × 2 matrix acts by a Möbius transformation.

Projectivization forgets scale but preserves exactly the information needed by a rank-one separator. If the separator’s terminal row is (1,−1), it kills precisely the projective point z = 1.

The p-adic valuation#

Fix a prime p. For a nonzero rational number, v_p records the exponent of p in its reduced factorization. For example, at p = 5,

v_{5} (5^{3} \cdot \frac{7}{11}) = 3 .

A rational is a p-adic unit when its valuation is zero. The ultrametric law makes unequal valuations rigid:

v_{p} (x) \neq v_{p} (y) \Rightarrow v_{p} (x - y) = \min (v_{p} (x), v_{p} (y)) .

The guard uses this law to compare an arbitrarily selected wait against an unbounded integer stored in the current projective point.

New Stuff#

Result#

Valuation guard. Fix a prime p, a depth s ≥ 2, a center α, and a reset ρ. Assume α and α−1 are p-adic units and ρ has positive valuation. The two rational 3 × 3 matrices constructed below are mortal exactly when the deterministic guarded orbit starting at ρ reaches 1.

The returns are 2 × 2 matrices, and a product of returns acts on the projective line, one Möbius map per return, with a freely chosen wait n each time. Products of invertible matrices never vanish, so a zero product needs a singular return. The design makes Γ₀ the only singular return, a rank-one separator that tests whether the current point is 1 and resets it to ρ. Mortality then asks whether some sequence of positive waits moves ρ to 1.

A free choice of wait at every step is what prevents such a family from following a computation. The guard removes it: at a live point z, the valuation v_p(z) is the only wait that keeps 1 reachable, and every other wait sends the point into a trap. The surviving dynamics is a single deterministic orbit.

The theorem does not decide whether that orbit reaches 1. It removes the matrix-semigroup freedom around the orbit: separator placement, arbitrary words, wrong waits, poles, and the point at infinity are all covered by the equivalence.

The three-mode family#

Transition matrix and cut#

The design has two requirements. A zero-length return must be a rank-one test-and-reset map; every positive return must be invertible and reject all but one wait at a live point. Three distinct powers in A provide the constant, contracting and expanding terms needed for those identities. The maps U and O combine them into a two-dimensional return.

Put δ = ρ−α. The hypotheses imply that δ is also a p-adic unit. Take

A = [\begin{matrix} 1 & 0 & 0 \\ 0 & p^{- 1} & 0 \\ 0 & 0 & p^{s - 1} \end{matrix}], U = [\begin{matrix} 0 & 1 \\ 1 & 0 \\ 1 & - 1 \end{matrix}],

O = [\begin{matrix} - α & α & δ \\ - 1 & 1 & 0 \end{matrix}], C = U O = [\begin{matrix} - 1 & 1 & 0 \\ - α & α & δ \\ 1 - α & α - 1 & δ \end{matrix}] .

The transition matrix has three distinct arithmetic modes: constant, contracting by p, and expanding by p^s−1. The cut C has rank exactly two.

Return matrices#

The return Γ_n = OAⁿU is

Γ_{n} = [\begin{matrix} α p^{- n} + δ p^{(s - 1) n} & - α - δ p^{(s - 1) n} \\ p^{- n} & - 1 \end{matrix}] .

At zero wait,

Γ_{0} = [\begin{matrix} ρ \\ 1 \end{matrix}] [\begin{matrix} 1 & - 1 \end{matrix}], Γ_{0}^{2} = (ρ - 1) Γ_{0} .

It is a nonnilpotent rank-one separator: it resets every non-kernel projective point to ρ and tests whether the incoming point is 1. Every positive return is invertible because

\det (Γ_{n}) = δ p^{(s - 2) n} (1 - p^{n}) \neq 0 (n \geq 1) .

The physical separator is already the word C² = UΓ₀O. No third generator is added.

The projective guard#

The defect identity#

Multiplying Γ_n by the nonzero scalar pⁿ does not change its projective action. In affine coordinate z, the resulting map is

Φ_{n} (z) = \frac{(α + δ p^{s n}) z - α p^{n} - δ p^{s n}}{z - p^{n}} .

Its numerator and denominator satisfy the cross-multiplied identity

Φ_{n} (z) - α = δ p^{s n} \frac{z - 1}{z - p^{n}} .

This identity compares the current valuation, the chosen wait, and the terminal defect z−1. The formal proof uses the cross-multiplied form, so the pole z = pⁿ is not silently discarded.

The permanent trap#

The live region consists of finite nonzero points of positive p-adic valuation. The target 1 is admitted separately. Define

Live = {z \in ℚ : z \neq 0, v_{p} (z) > 0}, Trap = ℙ^{1} (ℚ) ∖ (Live \cup {1}) .

For every positive wait, the trap maps into itself. Negative-valuation points, zero, infinity, and nonterminal units all enter the residue ball $v_{p} (z - α) > 0$ around α. Since α−1 is a unit, that ball excludes the target 1. The same argument applies again at every later step.

Forced computation#

Wrong waits#

Suppose the current point is live and put a = v_p(z) > 0. Then z−1 is a unit. If the word chooses n ≠ a, unequal valuations give

v_{p} (z - p^{n}) = \min (a, n) .

The defect identity then yields

v_{p} (Φ_{n} (z) - α) = s n - \min (a, n) > 0 .

The output is therefore a nonterminal unit in the trap. Every successful physical word must choose the unique wait

n = v_{p} (z) .

Carry depth#

The correct wait survives only when the state has the required p-adic precision. Write z = p^au, where u is a unit, and put h = v_p(u−1). For u ≠ 1,

v_{p} (Φ_{a} (z) - α) = (s - 1) a - h .

If the right side is positive, the output is a trapped unit; if negative, the output has negative valuation; if z = p^a, the output is infinity. Survival forces the exact ready condition

v_{p} (z) = a, v_{p} (z - p^{a}) = s a .

The tail recurrence#

Ready coordinates#

Every ready point has a unique p-adic unit tail X:

E (a, X) = p^{a} + \frac{p^{s a}}{X}, v_{p} (X) = 0 .

The visible valuation a selects the only legal wait. The tail X measures the residual displacement after subtracting the leading prime power; it is still rational and need not be bounded. Substitution into the legal return gives the deterministic update

Φ_{a} (E (a, X)) = α + δ (p^{s a} + (p^{a} - 1) X) .

The next valuation and next tail are recovered from this rational output. If the output is neither the target nor ready, no further positive return can reach the target.

Inverse grammar#

Given positive valuations a, b and any unit target tail X′, define

I_{a, b} (X') = \frac{p^{b} + p^{s b} / X' - α - δ p^{s a}}{δ (p^{a} - 1)} .

This predecessor tail is always a unit and satisfies

Φ_{a} (E (a, I_{a, b} (X'))) = E (b, X') .

For every prescribed positive input and output valuation, this formula supplies a suitable ready predecessor. That is a local existence result: it does not show that the fixed reset has such a predecessor tail, or that one initial rational realizes a whole prescribed computation.

Arbitrary physical words#

The free semigroup may place A and C in any order. The proof first fractures a zero product at occurrences of the internal separator C². Positive returns between separators act on projective states from right to left, matching matrix multiplication on columns.

Trap invariance propagates through every suffix of a successful bridge. A suffix cannot reach 1 early, because another positive return sends 1 into the trap. Every intermediate state is therefore live, and the forcing theorem makes its selected wait equal its valuation and its carry depth exact. Thus every successful arbitrary word is a legal path.

Conversely, every legal path is represented by its sequence of positive waits. The resulting equivalence is

\begin{array}{c} the physical pair {A,B} is mortal \\ \Leftrightarrow \\ some positive-return projective orbit sends ρ to 1 \\ \Leftrightarrow \\ the functional legal-step relation reaches 1 from ρ. \end{array}

A 3 × 3 section of the Hankel matrix of the return sequence has nonzero determinant, so no two-dimensional transition realizes the same returns.

Concrete pairs#

Take p = 5, s = 2, ρ = 30, and α = 869/28. The reset is ready and its unique legal wait one reaches the target. Clearing denominators gives

A = [\begin{matrix} 5 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 25 \end{matrix}], C = [\begin{matrix} - 28 & 28 & 0 \\ - 869 & 869 & - 29 \\ - 841 & 841 & - 29 \end{matrix}] .

C^{2} A C^{2} = 0 .

The guard does not force termination. At p = 5, s = 2, ρ = 5/6, and α = 2, the ready reset is a nonterminal fixed point.

Immortality certificates#

By the orbit equivalence, a property that holds at the reset, survives every legal step, and fails at 1 proves that the pair is immortal. Two such certificates follow: an odd reset-defect numerator, and a valuation wall at the primes dividing p − 1. For the even case at depth two, steps of maximal cancellation are shown never to occur twice in a row. The last subsection shows that four natural local measures of progress fail. These divisibility arguments move the target from 1 to 0 and write orbit points as coprime integer pairs; that changes coordinates, not the dynamics.

Terminal-centered coordinates#

Choose integers N, D, L with nonzero L such that $α = N / L, δ = D / L$ . For an original orbit point x, the terminal-centered coordinate is

z = L (x - 1) = \frac{r}{t}, x = 1 + \frac{r}{L t} .

Take $\gcd (r, t) = 1$ . The reset becomes $R = L (ρ - 1) = N + D - L$ , represented by (R,1), and the target becomes zero. A step produces a new primitive pair (r′,t′); h records the signed common factor removed. The next equations retain it, so no divisibility information is lost.

Odd reset-defect numerator immortality#

With the terminal-centered coordinates just defined, recall

R = N + D - L .

The adjacent unit assumptions on α and α−1 force p to be odd. In primitive terminal-endpoint coordinates, one legal wait a and its removed content h obey

\begin{array}{rcl} p^{s a} h t^{'} & = & r - L (p^{a} - 1) t, \\ h r^{'} & = & D r + (N - L) h t^{'} . \end{array}

If r is odd, the first equation makes h and t′ odd. If R is odd, the second then makes r′ odd. The reset endpoint numerator is R, whereas the canonical physical target has endpoint numerator zero. Induction through the checked decoded-to-primitive lift therefore proves that odd R is a physical immortality certificate.

Maximal steps are isolated#

Only even R remains. At depth s = 2, put $q = p^{a}$ . The signed forward content h has a complementary factor k with $h k = D L (q - 1)$ . The Smith split separates the fixed factors η, θ from the positive wait-dependent factors u, v:

h = η u, k = θ v, η θ = D L, u v = q - 1 .

In the associated integer decoder, every allocation with v ≥ 2 contracts a fixed weighted norm. The exceptional case v = 1 assigns all of the moving factor $q - 1$ to the forward content; this is what “maximal cancellation” means here. Substituting it into the step equations gives

r^{'} = θ t + (D q^{2} + N - L) t^{'} .

Here t and θ are odd, while the second coefficient is even. Thus r′ is odd and the maximal step cannot terminate. If another primitive step follows, its Smith coordinate v is even and therefore lies on the v ≥ 2 side. Maximal steps cannot occur consecutively.

Universal-boundary wall#

At depth two, let $q = p^{a}$ , and let F_q be the old guard map expressed in the terminal-centered coordinate: $φ_{q} (z) = L (Φ_{a} (1 + z / L) - 1)$ . It obeys the exact reset-defect factorization

(φ_{q} (z) - R) (z - L (q - 1)) = D (q - 1) ((q + 1) z + L) .

For any auxiliary prime ℓ, write

\begin{array}{rcl} λ_{L} & = & v_{ℓ} (L), & λ_{R} & = & v_{ℓ} (R), & λ_{D} & = & v_{ℓ} (D), \\ e & = & v_{ℓ} (p - 1), & ε & = & v_{ℓ} (2) . \end{array}

If R ≠ 0 and

\begin{array}{rcl} λ_{R} & < & λ_{L} + e, \\ 2 λ_{R} & < & λ_{D} + e + \min {λ_{L}, λ_{R} + ε}, \end{array}

then every positive branch preserves the strict ℓ-adic ball around reset:

B_{ℓ} = {R} \cup {z : z \neq R, λ_{R} < v_{ℓ} (z - R)} .

Reset lies inside and terminal zero lies outside. If the final numerator factor in the factorization vanishes, the branch returns exactly to reset; the formal proof isolates this case before taking finite valuations. The arbitrary-word equivalence therefore makes the two inequalities a physical immortality certificate.

In particular, every prime dividing the universal boundary p−1 must divide the reset-defect numerator of a mortal law:

ℓ ∣ p - 1 \Rightarrow ℓ ∣ R, rad (p - 1) ∣ R .

Here $rad (m)$ is the product of the distinct prime factors of m. The full valuation wall is stronger than this squarefree sieve: it can still exclude a law after every boundary prime has entered R.

Four failed progress measures#

The preceding theorem uses primes dividing $p - 1$ , which divide every positive-wait factor. A prime dividing only selected factors might seem to give a finer invariant. The next example shows why preservation can fail at the first wait outside its multiplicative order, even though the next orbit point is still ready. At depth two, take

p = 3, N = R = 249398, D = L = 1 .

In the original projective coordinate, the checked orbit prefix is (arrow labels are waits)

249399 \overset{4}{\to} \frac{4863261}{19} \overset{1}{\to} \frac{67384284465}{270178} .

The final point is itself ready at wait one. The prime 5 is a primitive divisor of 3⁴−1, so the second step breaks exact order four. In endpoint coordinates, it ejects the strict reset ball:

v_{5} (R) = 0, v_{5} (z_{1} - R) = 1, v_{5} (z_{2} - R) = 0 .

The raw endpoint pair after the two steps has gcd 18, coprime to 5, and its primitive denominator has grown from 19 to 270178. Thus this first order-breaking transition preserves neither the strict reset ball nor a decreasing denominator; it removes no factor of the auxiliary prime and does not repeat a state. None of these four local criteria can measure progress on every ready orbit.

Bookkeeping#

Verification and provenance#

Return compiler

Lean checks the split finite-rank return normal form and the complete mortality equivalence for a rank-one zero return with invertible positive returns.

Three-mode algebra

Lean checks the explicit matrices, return formula, ranks, determinants, projective defect identity, separator, and exact dimension-three Hankel lower bound.

Guarded dynamics

Lean checks the total projective action, p-adic trap, wait and carry-depth forcing, ready-tail grammar, functional reachability relation, and arbitrary-word converse.

Parity obstruction

Lean checks that adjacent units force an odd prime and that an odd reset-defect numerator excludes physical mortality through the decoded-to-primitive execution lift.

Smith isolation

Lean checks the exact maximal-cancellation identity, its odd target numerator, and the even Smith coordinate forced on every following step.

Universal-boundary wall

Lean checks the depth-two reset-defect factorization, prime-adic ball invariance, physical immortality below the valuation wall, and primewise reset-defect necessity.

Exact examples

Lean checks the rational parameters, denominator-cleared integer zero product, ready nonterminal fixed point, and ready order-breaking reset-ball ejection.

Transitive axioms

Publication-facing declarations use only propext, Classical.choice, and Quot.sound. The project contains no admitted proof or project axiom.

Foundational audit

The audit reconstructs the multiplication order, affine poles, trap cases, inverse grammar, concrete certificates, and exact unresolved boundary.

Parity audit

The audit reconstructs the parity and Smith claims and rejects an antichain overclaim.

Universal-boundary audit

The audit repairs the zero-blade proof branch, rejects unconditional tail trapping, and validates the coefficient sieve.

Order-breaking bridge audit

The audit repairs a trap-target gap and verifies a ready-target counterexample to a uniform local charge.

Formal scope#

The matrix identities, rank statements, complete physical mortality equivalence, total projective semantics, p-adic forcing theorems, tail grammar, concrete examples, and exact state lower bound are machine-checked over ℚ. Independent nonzero scaling clears the two physical generators to integer matrices without changing zero products.

The formal result does not prove M₃(2) decidable or undecidable. It proves an exact equivalence for the displayed parametric family, physical immortality for every odd reset-defect numerator, maximal-step isolation at depth two, physical immortality below the universal-boundary valuation wall, and failure of every uniform first order-breaking bridge charge listed above. In particular, every prime divisor of p−1 divides the reset-defect numerator of a mortal depth-two guard. No universal computation has been compiled into the deterministic orbit, and no decision procedure for that orbit is claimed.

The hypotheses are stated at their exact formal strength. The prime need not be separately assumed odd; requiring both α and α−1 to be p-adic units formally excludes residue characteristic two.

Priority#

To our knowledge, after searches through 28 July 2026, the nearest published framework is recurrence-controlled matrix reachability [Hirvensalo et al. 2024]. No located source gives this three-mode return family, its internal separator, the exact valuation trap, or the mortality-to-functional-orbit equivalence. The foundational low-dimensional mortality decomposition and bounded mortality notation are prior art [Bournez–Branicky 2002] [Cassaigne et al. 2014]. “No located source” is limited to publicly discoverable work.

References#

Olivier Bournez and Michael S. Branicky, The Mortality Problem for Matrices of Low Dimensions, Theory of Computing Systems 35(4):433–448, 2002. Low-dimensional mortality and singular-endpoint structure.
Julien Cassaigne, Vesa Halava, Tero Harju, and François Nicolas, Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More, 2014. Bounded mortality notation and neighboring undecidability bounds.
Mika Hirvensalo, Akitoshi Kawamura, Igor Potapov, and Takao Yuyama, Reachability in Linear Recurrence Automata, Reachability Problems, 2024. Comparative framework for recurrence-indexed matrix reachability.