Thinking In Structure

Tag: semilinear sets

  • Arithmetic Completeness for Two-Dimensional Cone-Monotone Integer Relations

    Download paper (pdf)
    Download validation code (zip)

    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

  • Beyond Finite Kleene Convergence: Integral Cores and a Collatz Barrier for Cone-Monotone Integer Relations

    Download paper (pdf)
    Download verification code (zip)

    Beyond Finite Kleene Convergence: Integral Cores and a Collatz Barrier for Cone-Monotone Integer Relations

    This paper studies exact weakest nontermination for homogeneous nondeterministic integer relations of the form Bλ = Aλ′ under a cone-monotonicity condition.

    A companion paper characterized exactly when the descending predecessor sequence stabilizes after finitely many steps. Paper XI goes beyond that boundary. It identifies a strictly larger, effectively recognizable class for which the exact weakest nontermination set remains computable even when finite Kleene convergence fails.

    The main construction is a canonical core-face decomposition. When the full-cone deterministic quotient is nonintegral, the relation is compressed to its exact forward-integral coefficient core, retaining the lattice congruences required by infinite computations while strictly reducing physical dimension. When the ambient quotient is integral but nonintegral proper closed faces remain, shadow-free bad faces are isolated recursively and finite convergence is restored on their complement.

    For every core-face-decomposable system, the recursion terminates after at most the physical dimension and flattens to a finite exact normal form. The weakest nontermination precondition is therefore effectively definable in existential Presburger arithmetic and is effectively semilinear. The earlier finite-Kleene class appears exactly as the depth-zero case.

    The paper also develops explicit quantitative bounds for the size of the decomposition tree, the number and size of Hilbert-basis generators introduced during core reduction, and the syntactic size of the resulting Presburger formulas. An exhaustive exact census of 4,608 small two-dimensional systems shows that the new core-reduction and shadow-free mechanisms solve 646 of the 1,320 systems rejected by finite Kleene convergence, reducing the unresolved fraction by 48.94%.

    The boundary of the method is arithmetically significant. In physical dimension two, a shadowed bad face can already realize the integer map n ↦ floor(4n/3) on the first adjacent lattice layer. Exact nontermination for a specific explicit relation is thereby equivalent to an unresolved generalized-Collatz reachability problem. Physical dimension two is minimal for this obstruction.

    Main results:

    • canonical finite core-face decomposition;
    • exact dimension-reducing integral-core compression preserving lattice congruences;
    • relative finite convergence outside shadow-free bad faces;
    • finite exact normal form for the weakest nontermination set;
    • effective existential-Presburger and semilinear representation;
    • explicit decomposition-tree, Hilbert-basis and formula-size bounds;
    • complete classification in physical dimension one;
    • exhaustive 4,608-system computational census;
    • a dimensionally minimal generalized-Collatz barrier in physical dimension two.

    Verification material: The accompanying repository contains the exact-arithmetic verifier used to reproduce the 4,608-system census reported in Section 15. The computational results are validation data only; no theorem depends on the census.

  • Minimal Kernel Dimension for Fixed-Control Balance-Loop Realizations of Rational Floor Maps

    Download paper (pdf)
    Download verification code (zip)

    Paper XII. Minimal Kernel Dimension for Fixed-Control Balance-Loop Realizations of Rational Floor Maps. Preprint, August 2026.

    This paper introduces the minimal kernel dimension of an exact fixed-control balance-loop realization of a rational floor map. For the partial map x ↦ floor(Qx/d), defined on integers not divisible by d, the invariant κ(d,Q) measures the least relation-lattice dimension, equivalently the least toric codimension, required by any proper realization.

    The paper first proves a rigidity theory for minimal presentations. Every zero-control column is forced to lie in the bulk direction (d,Q), and every kernel-minimal realization contains exactly one bulk column. This reduces the infinite arithmetic realization problem to a finite selector-fibre problem.

    For coprime parameters the invariant is classified completely. Kernel dimension 2 occurs exactly when Q is congruent to +1 or −1 modulo d; every other coprime case has kernel dimension 3.

    The noncoprime case exhibits genuinely new behaviour. In particular, κ(8,2) = 3 while κ(12,3) = 4, even though both maps have the same reduced slope 1/4. The scaling family (d,q) = (mg,g), with m ≥ 3 and g ≥ 2, is classified completely: the kernel dimension is 3 when m = 3 or g = 2, and 4 when m ≥ 4 and g ≥ 3.

    The paper then proves a general kernel-4 realization theorem for arbitrary noncoprime parameters d = gm and q = gn with gcd(m,n) = 1. Combined with the coprime classification and the scaling constructions, this yields the sharp universal bound

    κ(d,Q) ≤ 4

    for every d ≥ 2 and every positive numerator Q. Since κ(12,3) = 4, the universal bound is best possible.

    The lower bounds combine lattice saturation, signed-residual arguments, residue replacement, numerical semigroups, Apéry coordinates and rational mechanical words. The upper bounds are supplied by explicit fixed-control constructions. The results show that minimal factorization complexity is universally bounded, but is not determined by reduced rational slope alone; it also depends on the arithmetic structure of the excluded congruence class.

    The paper also identifies a toric interpretation of the invariant: κ(d,Q) is the minimum height of the toric ideal associated with the source matrix, taken over all exact fixed-control realizations of the prescribed floor map.