pith. sign in

arxiv: 2508.04851 · v2 · pith:AECX3NFXnew · submitted 2025-08-06 · 🧮 math.LO · cs.FL

A Dichotomy for k-automatic expansions of Presburger Arithmetic

Jason Bell , Alexi Block Gorman , Chris Schulz This is my paper

Pith reviewed 2026-05-19 00:48 UTC · model grok-4.3

classification 🧮 math.LO cs.FL
keywords k-automatic setsPresburger arithmeticfirst-order definabilitydichotomyexpansions of arithmeticmodel theoryautomatic sequences
0
0 comments X

The pith

For any non-eventually-periodic k-automatic set X, either adjoining X to Presburger arithmetic defines every k-automatic subset or the definable sets coincide exactly with those of the structure expanded by the powers of k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a clean split for structures obtained by expanding Presburger arithmetic with one additional predicate X. When X is k-automatic and not eventually periodic, the first-order definable sets in the resulting structure fall into one of two exhaustive cases. In the first case every other k-automatic subset becomes definable from addition and X. In the second case the definable sets are identical to those obtained simply by adding the sparse set of all powers of k. A reader interested in the boundary between arithmetic and automata theory would care because the result supplies a uniform classification that decides, for any such X, how much new definable content it contributes.

Core claim

Let k ≥ 2 and let X be a k-automatic subset of the natural numbers that is not eventually periodic. Then either every k-automatic subset of the natural numbers is first-order definable in the expansion (N, +, X), or the first-order definable sets of (N, +, X) are precisely the first-order definable sets of (N, +, k^N).

What carries the argument

The dichotomy that forces any such expansion to be either maximally rich (defining all k-automatic sets) or equivalent to the geometrically sparse powers-of-k expansion.

If this is right

  • Under the first alternative, every k-automatic predicate becomes first-order expressible using only addition and the single predicate X.
  • Under the second alternative, adjoining X introduces no definable sets beyond those already present when the powers of k are adjoined.
  • The dichotomy therefore partitions all non-periodic k-automatic sets into two exhaustive classes with respect to the definable content they generate.
  • The result applies uniformly for every k ≥ 2 and every qualifying X, supplying a complete case division rather than isolated examples.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same partition may be worth testing for other automatic or morphic predicates to see whether analogous splits appear outside the k-automatic case.
  • One could attempt to decide algorithmically, for a given explicit automatic set, which of the two branches holds by checking definability of a few known automatic sequences such as the Thue-Morse sequence.
  • The classification suggests that questions about decidability or quantifier elimination in these expansions can be reduced to the two known cases.

Load-bearing premise

X is required to be k-automatic yet not eventually periodic.

What would settle it

Any concrete k ≥ 2 together with a k-automatic non-periodic X such that the definable sets of (N, +, X) properly contain those of (N, +, k^N) but still omit at least one k-automatic set would refute the dichotomy.

Figures

Figures reproduced from arXiv: 2508.04851 by Alexi Block Gorman, Chris Schulz, Jason Bell.

Figure 1
Figure 1. Figure 1: An automaton with cycle language at q2 having F(22) = 3. Then if we take n = [211]3 = 22, F(n) = 3. To see this, notice that if r ≥ 0 and v is a word with length at most r + 1 with |v| = r + 1, then 3rn − [1|v|−r0 r ]3 + [v]3 has ternary expansion 21v, which is in the cycle language of the state q2 if and only if v is. If |v| ≤ r, then 3 rn + [1r−j v]k has ternary expansion 212+r−|v|v, which is again in th… view at source ↗
read the original abstract

Let $k\ge 2$ and let $X$ be a subset of the natural numbers that is $k$-automatic and not eventually periodic. We show that the following dichotomy holds: either all $k$-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate $X$, or $(\mathbb{N},+,X)$ has the same definable sets as $(\mathbb{N},+,k^{\mathbb{N}})$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves a dichotomy for expansions of Presburger arithmetic: for any integer k ≥ 2 and any k-automatic subset X ⊆ ℕ that is not eventually periodic, either every k-automatic subset of ℕ is definable in the structure (ℕ, +, X), or the definable sets of (ℕ, +, X) coincide exactly with those of (ℕ, +, k^ℕ).

Significance. If the result holds, the dichotomy cleanly classifies the model-theoretic strength of adjoining a single non-periodic k-automatic predicate to Presburger arithmetic, distinguishing expansions that recover all automatic sets from those that remain as weak as the standard k-power structure. This advances the study of automatic structures and definability in arithmetic by providing a precise alternative with no free parameters or ad-hoc cases beyond the stated hypothesis on X.

minor comments (3)
  1. [§1] §1 (Introduction): the statement of the main theorem could include a one-sentence pointer to the key technical tool (e.g., the automaton-to-formula translation or the pumping argument) used in the case distinction.
  2. [§2.2] §2.2 (Preliminaries): the definition of k-automatic sets via automata is standard, but an explicit example of a non-eventually-periodic k-automatic set (such as the set of powers of k itself) would help readers verify the boundary condition before the proof begins.
  3. [§4] §4 (Proof of the dichotomy): several cross-references to lemmas in §3 are given only by number; adding a short descriptive phrase (e.g., “by the synchronization lemma”) would improve readability without lengthening the text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our main result and for highlighting its significance in classifying the model-theoretic strength of adjoining a single non-periodic k-automatic predicate to Presburger arithmetic. We appreciate the recommendation of minor revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states an explicit dichotomy theorem whose hypothesis (X is k-automatic and not eventually periodic) is given as an input assumption rather than derived from the conclusion. The two cases in the dichotomy are distinguished by whether adjoining X makes all k-automatic sets definable or restricts definable sets exactly to those of (N,+,k^N); this case split is presented as a logical consequence of automata-theoretic properties and model-theoretic definability, without any reduction of a 'prediction' to a fitted parameter, self-definition of X in terms of the target definable sets, or load-bearing reliance on a prior result by the same authors. No equations or steps in the abstract or stated claim collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definitions of k-automatic sets, first-order definability, and the structure of Presburger arithmetic; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math k-automatic sets are closed under Boolean operations and projections in the expected way
    This background fact from automata theory is presupposed by any such definability argument.
  • domain assumption Definability is first-order definability in the language of addition plus the new predicate
    The entire dichotomy is phrased in terms of first-order definable sets.

pith-pipeline@v0.9.0 · 5594 in / 1294 out tokens · 52377 ms · 2026-05-19T00:48:15.620831+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    The ring of k-regular sequences.Theor

    Jean-Paul Allouche and Jeffrey Shallit. The ring of k-regular sequences.Theor. Comput. Sci., 98:163–197, 1992

    work page 1992

  2. [2]

    Cambridge University Press, Cambridge, 2003

    Jean-Paul Allouche and Jeffrey Shallit.Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003

    work page 2003

  3. [3]

    A new dp-minimal expansion of the integers.J

    Eran Alouf and Christian d’Elb´ ee. A new dp-minimal expansion of the integers.J. Symbolic Logic, 84(2):632–663, 2019

    work page 2019

  4. [4]

    k-regular power series and Mahler-type functional equations.J

    Paul-Georg Becker. k-regular power series and Mahler-type functional equations.J. Number Theory, 49:269–286, 1994

    work page 1994

  5. [5]

    Bell, Kathryn Hare, and Jeffrey Shallit

    Jason P. Bell, Kathryn Hare, and Jeffrey Shallit. When is an automatic set an additive basis?Proc. Amer. Math. Soc. Ser. B, 5:50–63, 2018

    work page 2018

  6. [6]

    Bell and Rahim Moosa

    Jason P. Bell and Rahim Moosa. F -sets and finite automata.J. Th´ eor. Nombres Bordeaux, 31(1):101–130, 2019

    work page 2019

  7. [7]

    Undecidable extensions of B¨ uchi arithmetic and Cobham-Semenov theorem.J

    Alexis B` es. Undecidable extensions of B¨ uchi arithmetic and Cobham-Semenov theorem.J. Symbolic Logic, 62(4):1280–1296, 1997

    work page 1997

  8. [8]

    Entiers et automates finis.M´ emoir de fin d’´ etudes, 1985

    V´ eronique Bruy` ere. Entiers et automates finis.M´ emoir de fin d’´ etudes, 1985

    work page 1985

  9. [9]

    Logic andp-recognizable sets of integers.J

    V´ eronique Bruy` ere, Georges Hansel, Christian Michaux, and Roger Villemaire. Logic andp-recognizable sets of integers.J. Montoises, 1:191–238, 1994

    work page 1994

  10. [10]

    Richard B¨ uchi

    J. Richard B¨ uchi. Weak second-order arithmetic and finite automata.Z. Math. Logik Grundlagen Math., 6:66–92, 1960

    work page 1960

  11. [11]

    Richard B¨ uchi

    J. Richard B¨ uchi. On a decision method in restricted second order arithmetic. InLogic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pages 1–11, Stanford, 1962. Stanford University Press

    work page 1960

  12. [12]

    On the base-dependence of sets of numbers recognizable by finite automata.Math

    Alan Cobham. On the base-dependence of sets of numbers recognizable by finite automata.Math. Syst. Theory, 3(2):186––192, 1969

    work page 1969

  13. [13]

    Seymour Ginsburg and Edwin H. Spanier. Semigroups, Presburger formulas, and languages.Pacific J. Math., 16(2):285–296, 1966

    work page 1966

  14. [14]

    Automata and tame expansions of (Z,+).ArXiv Mathematics e-prints, 2019

    Christa Hawthorne. Automata and tame expansions of (Z,+).ArXiv Mathematics e-prints, 2019

    work page 2019

  15. [15]

    On expansions of (Z, +, 0).Ann

    Quentin Lambotte and Fran¸ coise Point. On expansions of (Z, +, 0).Ann. Pure Appl. Logic, 171(8):102–809, 2020

    work page 2020

  16. [16]

    ¨Uber die vollst¨ andigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt.C

    Mojzesz Presburger. ¨Uber die vollst¨ andigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt.C. R. I congr` es Math. Pays Slaves, Warszawa:92–101, 1929

    work page 1929

  17. [17]

    Undefinability of multiplication in Presburger arithmetic with sets of powers.J

    Chris Schulz. Undefinability of multiplication in Presburger arithmetic with sets of powers.J. Symbolic Logic, 90(2):872–886, 2025

    work page 2025

  18. [18]

    Alexei L. Semenov. On certain extensions of the arithmetic of addition of natural numbers.Izv. Math., 15(2):401– 418, 1980

    work page 1980

  19. [19]

    The theory of (N,+, V k, Vℓ) is undecidable.Theoret

    Roger Villemaire. The theory of (N,+, V k, Vℓ) is undecidable.Theoret. Comput. Sci., 106(2):337–349, 1992. A DICHOTOMY FORk-AUTOMATIC EXPANSIONS OF PRESBURGER ARITHMETIC 23 University of W aterloo, Department of Pure Mathematics, W aterloo, Ontario, N2L 3G1, Canada Email address:jpbell@uwaterloo.ca McMaster University, Department of Mathematics and Statis...

    work page 1992