Thinking In Structure

Tag: integer linear-constraint loops

  • Fixed-Start Nontermination in Homogeneous Nonnegative Equality Loops

    Download paper (pdf)

    Fixed-Start Nontermination in Homogeneous Nonnegative Equality Loops: Continuation Cores, Arithmetic Obstructions, and Decidable Frontiers develops a structural and arithmetic theory for deciding whether a prescribed initial state in a homogeneous nonnegative equality loop can generate an infinite integer trajectory. The problem arises naturally from balance-loop representations in numeration systems, but also belongs to the broader theory of integer linear-constraint loops and termination.

    The paper introduces a span-relaxed continuation core, an effectively computable rational polyhedral cone that contains every infinite real or integer trajectory and stabilizes after at most rank(A) + 1 iterations. Within this core, failure of an exact integer successor is classified into three distinct mechanisms: a positive-cone obstruction, a lattice obstruction, or an affine-semigroup hole. A Hilbert-basis formulation also gives finite certificates for total viability of the continuation core.

    The principal decidability result proves fixed-start nontermination decidable whenever the intrinsic physical continuation rank is at most one, regardless of the ambient matrix dimensions. In the difficult expanding case, a maximal-slope Apéry construction gives uniformly efficient predecessors; once the viability gcd stabilizes, numerical-semigroup conductors become uniformly bounded, forcing exact finite stabilization of the integer viability filtration. The paper also proves decidability whenever the coefficient continuation dimension is at most two.

    Deterministic continuation cores are further connected to the Positivity Problem for integer linear recurrence sequences through an invariant orbit lattice. The resulting framework separates linear consistency, positive geometry, lattice congruences and semigroup holes, and identifies the first genuinely relational untreated case as a two-dimensional physical continuation core with one rational factorization degree of freedom.

  • Nonnegative Positionality in Regular Abstract NumerationSystems: Balance-Loop Normal Forms and Viability Filtrations

    Download paper (pdf)

    Let L ⊆ {0, 1, …, c}* be an infinite regular language, ordered genealogically, and let GL(w) denote the genealogical rank of w ∈ L. We ask whether there exists a sequence of nonnegative integer weights U = (Un)n≥0 such that

    GL(a1⋯am) = ∑i=1m aiUm−i   (a1⋯am ∈ L).

    The companion paper [5, Theorem 6.1] proves that, after an effectively computable support preperiod τ and period p, the periodic tail can be stacked into a macrostate Xk ∈ ℤD satisfying

    𝒜Xk + ℬXk+1 = 0.

    It also shows that the nonnegative problem already contains the Positivity Problem for linear recurrence sequences. Here we identify an exact normal form for that remaining nonnegative problem.

    We define a proper homogeneous balance loop to be a system

    Bλn = Aλn+1,    λn ∈ ℕr,

    where A and B are nonnegative integer matrices and every column ai of A is nonzero, together with a fixed initial vector λ0. Properness gives ‖ai‖1 ≥ 1, which in turn makes the successor relation effectively finitely branching.

    Our main theorem proves an effective equivalence between nonnegative positionality for infinite regular languages and nontermination of proper homogeneous balance loops. The forward reduction passes from the periodic descriptor relation to its nonnegative integer transition monoid, uses a Hilbert basis, and adds a budget coordinate to remove zero-source generators. The reverse reduction is constructive: a regular language built from radix fillers and finitely many repeated lexicographic equality gadgets realizes any balance loop.

    The normal form has immediate consequences. Proper balance loops are effectively finitely branching, every trajectory has an effective exponential envelope, and nontermination is equivalent to survival at every finite horizon. Consequently, non-positionality of a regular abstract numeration system is recursively enumerable.

    The result isolates the positivity barrier as an infinite nonnegative integer viability problem within a restricted homogeneous class of linear-constraint loops.