This paper develops an exact structural theory of weakest nontermination for the full class of two-dimensional cone-monotone homogeneous integer equality relations of the form Bλ = Aλ′, with nonnegative integer coefficient states, pointed source cone and nonzero source columns.
The full canonical deterministic quotient gives the first structural dichotomy. If it is nonintegral, an exact integral-core compression preserves weakest nontermination while strictly reducing physical dimension. In physical dimension two, this reduces the problem to dimension at most one, where weakest nontermination is effectively Presburger-definable. Nonintegral full quotients therefore create no genuinely new two-dimensional arithmetic obstruction.
For the remaining integral-full-quotient branch, the paper removes the nonnegativity constraint and studies the resulting signed predecessor sequence as the forward-domain sequence of an additive linear relation on Zn. Finite attainment is characterized exactly: the signed sequence stabilizes after finitely many steps if and only if the canonical rational deterministic quotient is integral over Z. In the integral case, the stable signed lattice is effectively computable.
Intersecting this stable lattice with the nonnegative orthant produces an affine semigroup. Normalization and conductor theory, combined with cone monotonicity, then give an exact deep-interior saturation theorem: beyond an effectively computable translated cone, weakest nontermination is precisely membership in the stable signed lattice. The entire deep interior is therefore effectively Presburger-definable.
In physical dimension two, the complement of the conductor region decomposes into two bounded facet strips and a finite corner. Good strips have effectively Presburger weakest-nontermination sets. Every remaining bad strip reduces exactly, after a finite prefix, to a finite-branch guarded residue-affine system with one common expanding multiplier:
d n′ = m n + c
where m > d ≥ 2 and m and d are coprime.
This yields an unconditional arithmetic reduction for the entire two-dimensional cone-monotone equality class. Every weakest-nontermination set is a finite union of effectively Presburger pieces and inverse images of survivor sets for guarded common-multiplier residue-affine systems. Conversely, every system in this residual arithmetic class is realized exactly on a forward-invariant first-layer tail of a two-dimensional cone-monotone equality relation with integral full canonical quotient.
Consequently, universal semilinearity and effective Presburger synthesis for two-dimensional geometric weakest-nontermination sets are equivalent to the corresponding problems for the residual arithmetic survivor class. Pointwise membership is mutually reducible by finite disjunctive reductions.
The result isolates the complete residual source of non-Presburger complexity in physical dimension two. Nonintegral ambient quotients collapse to lower-dimensional Presburger cases; the deep interior and all good boundary regions are tame; and every remaining arithmetic obstruction is forced onto a bad shadowed face and reduces to one-dimensional guarded common-multiplier dynamics. Within the stated cone-monotone equality class, no further two-dimensional geometric case remains to be classified.
Paper XVIII of the Cone-Monotone Integer Relations research programme.
Related companion papers:
- Closed-Face Integrality and Exact Conditional Termination for Cone-Monotone Integer Equality Relations
- Beyond Finite Kleene Convergence: Integral Cores and a Collatz Barrier for Cone-Monotone Integer Relations
- Shadowed Faces and Residue-Affine Dynamics in Cone-Monotone Integer Relations: Global Shadow Normal Forms, Kleene Conjugacy, and a Lagarias-Sloane Barrier
Leave a Reply