Pith. sign in

REVIEW 2 major objections 6 minor 32 references

This paper shows that countable models of Presburger arithmetic realize nearly every Scott sentence complexity, including all Π_α, d-Σ_α, and Σ_α above 4, while never achieving Σ3, and transfers degree spectra from linear orders via a one-j

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-03 07:07 UTC pith:YSZAGM2J

load-bearing objection Genuinely useful transfer method and broad classification, but Lemma 3.17 is false, so the full equivalence in Corollary 3.19 is unproved; the main existence results appear to survive because they use only the forward direction. the 2 major comments →

arxiv 2601.21118 v3 pith:YSZAGM2J submitted 2026-01-28 math.LO

Measuring the Complexity of Countable Presburger Models

Jason Block This is my paper
classification math.LO MSC 03C5703D4503C62
keywords Presburger arithmeticScott sentence complexityScott rankdegree spectralinear ordersdivisible ordered abelian groupscomputable structure theoryback-and-forth relations
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Countable models of Presburger arithmetic—the theory of (Z,+,<,0,1)—form a rich but tractable class. This paper shows how to build, from any countable linear order L, a Presburger group P_L that inherits L's structural complexity. As a result, Presburger groups attain Scott sentence complexity Π_α for every countable α>1, d-Σ_α for every successor α>1, and Σ_α for every successor α>4, with no group at Σ3. The same construction yields an exact degree-spectrum identity: the Turing degrees of copies of P_L are exactly those degrees whose jump computes a copy of L. These results give Presburger arithmetic a complete Scott spectrum, distinguishing it from arithmetic with multiplication, and leave open a single gap at Σ4.

Core claim

The central discovery is a transfer principle: every countable linear order L can be embedded into a Presburger group P_L = V_L × Z, where V_L is the divisible ordered abelian group whose Archimedean rank is exactly L. The paper proves that Scott-sentence complexity passes from L to P_L (with a shift by one in finite cases, and exactly for infinite indices), and that the degree spectrum of P_L is precisely {d : d' ∈ DgSp(L)}. On the Scott-complexity side, this yields the near-complete classification of Theorem 3.1: all Π_α for α>1, all d-Σ_α for successor α>1, all Σ_α for successor α>4, and no Σ3. The no-Σ3 result is proved separately for all Presburger groups, not just those of the form P_L

What carries the argument

The construction P_L = V_L × Z, where V_L = ⊕_{l∈L} Q is the divisible ordered abelian group with Archimedean rank L; the embedding π : L → P_L sends each l to the basis vector f_l. Back-and-forth relations and Karp's theorem lift Scott-sentence complexity from L to P_L, while a stage construction shows DgSp(P_L) = {d : d' ∈ DgSp(L)}. The no-Σ3 result relies on a finite-basis characterization of ordered abelian groups with Σ3 Scott sentences, together with an explicit isomorphism built from dependence equations.

Load-bearing premise

The transfer from linear orders to Presburger groups rests on Lemma 3.17, which asserts that any positive non-integer element of P_L outside the rational span of fixed basis elements can be moved by an automorphism to a single basis element while fixing those basis elements; if that automorphism claim fails, the back-and-forth equivalence and most of the Scott-complexity results for P_L do not follow.

What would settle it

In L = {0 < 1} take a = (1) and p = f_0 + f_1; any order-preserving automorphism fixing f_1 must send f_0 to a positive multiple of f_0, so p maps to c f_0 + f_1, never to f_0 or f_1. Checking this case decides whether Lemma 3.17, and thus the reverse direction of Proposition 3.18, holds.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Presburger arithmetic has complete Scott spectrum: every countable ordinal occurs as the Scott rank of some countable Presburger group.
  • There is a sharp complexity gap: no Presburger group has Scott sentence complexity Σ3, even though Σ4 remains open; this mirrors a known gap for linear orders.
  • The degree spectrum of P_L is exactly the one-jump inversion of the degree spectrum of L, so computing a copy of P_L is never harder than computing the jump of a copy of L.
  • Presburger groups can have degree spectra of the form {d : S is c.e. or computable in d^(α)} for any S and many computable ordinals α, including the one-jump spectra {d : S c.e. in d'}.
  • The construction yields plain Presburger groups with every upper cone of Turing degrees as their degree spectrum.

Where Pith is reading between the lines

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

  • If Lemma 3.17 fails, the back-and-forth equivalence of Proposition 3.18 needs an additional hypothesis, so the full transfer of Scott complexity from arbitrary linear orders to P_L may require a modified construction or an extra definability condition.
  • The one-jump degree-spectrum identity suggests a general pattern: P_L acts as a 'jump-inverting' functor on linear orders, which might be iterated to build Presburger groups with more complex spectra, possibly resolving whether Presburger groups are universal for degree spectra.
  • The Σ3 gap hints at a dichotomy: Presburger groups with finite basis (equivalently, with a Σ3 Scott sentence) collapse to lower complexity, so the only way to reach Σ4 or above is through infinite-dimensional or non-plain groups.
  • Since the paper leaves Σ4 open, a natural test is whether any non-plain Presburger group (e.g., Z[ˆr] with a carefully chosen residue sequence) can achieve Σ4, which would separate plain and non-plain constructions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies Scott sentence complexities and degree spectra of countable models of Presburger arithmetic. The main technical device is a construction P_L = V_L × Z associated to a countable linear order L, and the paper proves (or claims) transfer results between the back-and-forth relations, Scott ranks, and degree spectra of L and P_L. On this basis it claims existence of Presburger groups with Scott complexities Π_α for all α>1, d-Σ_α for all successor α>1, and Σ_α for all successor α>4, plus nonexistence of Σ_3; it also derives degree-spectrum identities, in particular DgSp(P_L) = DgSp(V_L) = {d : d′ ∈ DgSp(L)}, and constructs Presburger groups with spectra of the form {d : S is c.e./computable in d^(α)}.

Significance. If the main results hold, the paper makes a substantial contribution: it transfers a large body of linear-order Scott analysis to a number-theoretically natural class of ordered abelian groups, gives the complete Scott spectrum for Presburger arithmetic, and yields new degree spectra. The constructions are explicit and the paper makes systematic and mostly careful use of ordinal back-and-forth relations and of known results on linear orders and ordered abelian groups. The main classification statements appear plausible and are likely repairable, because the affected applications seem to use only the forward direction of the key transfer, but the paper currently contains a false lemma and at least one unjustified lower-bound step. These issues block acceptance in the present form.

major comments (2)
  1. [§3.1, Lemma 3.17] Lemma 3.17 is false as stated. Counterexample: let L = {0 < 1}, a = (1), and p = π(0) + π(1) in P_L. Then p is positive, has residue sequence 0, and is not a Q-linear combination of π(1). But no order-preserving Q-linear automorphism of P_L fixing π(1) can send p to a basis element π(l). Indeed, if H fixes f_1 = π(1) and H(f_0) = c f_0 + b f_1 with b ≠ 0, then H(n f_0 + f_1) has f_1-coefficient nb + 1, which is negative for a suitably chosen integer n, contradicting order preservation; hence b = 0 and H(p) = c f_0 + f_1, never f_0 or f_1. This lemma is exactly what is used in the reverse direction of Proposition 3.18 (second paragraph of the inductive step) and hence in Corollary 3.19. The forward direction appears to be proved without Lemma 3.17, and the later applications seem to use only that direction, but the stated equivalence A ≤_α B ⇔ P_A ≤_{1+α} P_B is not established. The lemma
  2. [§3.2, Proposition 3.34] The lower-bound step is missing. The proof says: 'Since SC(L) = Σ_{λ+1}, L has no Π_{λ+1} Scott sentence. Thus, SR(L) = λ+1 and so SR(P_L) = λ+1 by Lemma 3.4.' Lemma 3.4 only gives SR(P_L) ≤ 1 + SR(L); to conclude SR(P_L) = λ+1 one needs the opposite inequality SR(L) ≤ SR(P_L), which is Lemma 3.5. Without that lower bound one cannot rule out that P_L has a Π_{λ+1} Scott sentence, so the claimed Σ_{λ+1} complexity is not proved. This is load-bearing for Theorem 3.1, though it is a local fix: cite Lemma 3.5 for the lower bound and Lemma 3.4 for the upper bound.
minor comments (6)
  1. [§4, Theorem 4.7] There is a typo in the displayed definition of Φ: 'cut(1, p_1, ..., n)' should be 'cut(1, p_1, ..., p_n)'.
  2. [§4, Proposition 4.1] The notation 'Π^0_1 formulas' is confusing in the infinitary context; it should presumably be Π_1 (or Π^in_1) formulas in the L_{ω1,ω} hierarchy.
  3. [§2, Definition 2.6] The construction A[hat r] is very hard to parse: the displayed notation involving 'X−r_n/n z' and the equivalence relation should be rewritten. This definition is not used heavily afterward, but as written it will confuse readers.
  4. [§5.2, Corollary 5.10] The proof cites 'Proposition 5.8' but the intended reference is Theorem 5.8 (or Proposition 5.7 for V_L). Please correct the cross-reference.
  5. [§3.2, Lemma 3.31] The translations x <* y and x =* y are defined for positive elements, and a guard is introduced in the Π_1 step. The proof should state explicitly how the translation behaves for arbitrary tuples, since the atomic case as written appears to presuppose positivity.
  6. [§3.2, Proposition 3.24] The notation Z_n · Q is used without definition. Please define the intended linear order or give a reference.

Circularity Check

0 steps flagged

No significant circularity: the paper transfers external linear-order results to Presburger groups via explicit, proven constructions.

full rationale

The paper's central strategy is to transfer known Scott-complexity and degree-spectrum facts about countable linear orders L to the constructed Presburger groups P_L = V_L x Z (Definitions 2.12 and 2.14). No step fits a parameter to data and then calls the consequence a prediction; the only parameters are the linear order L and residue sequences. The transfer results (Lemmas 3.4-3.6, Proposition 3.18, Theorem 3.33, Proposition 5.7, Theorem 5.8) are proved from the definition of P_L, back-and-forth relations, and cited external theorems (Karp, Montalban, Goncharov-Lempp-Solomon, Ash-Knight-Downey, etc.). These citations are to prior work by other authors and are not supplying the paper's conclusions by self-citation: [10] and [12] supply the achievable linear-order complexities, while the paper proves the P_L analogues. The no-Sigma-3 result (Theorem 4.7) reduces to the external finite-basis criterion and then gives a direct uniform-Delta-0-2-categoricity argument; it is not assumed. The paper also explicitly flags its open cases (Questions 6.1, 6.2, 6.4). The reader's counterexample to Lemma 3.17 would be a correctness gap in the reverse direction of Proposition 3.18 if sustained, but a false lemma is not a circular definition or a fitted-input prediction; it does not make the derivation equivalent to its inputs. Hence no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

The central results rest on standard theorems of infinitary logic, back-and-forth relations, and known classifications for linear orders and ordered abelian groups. No free parameters are fitted. The suspicious internal claim is Lemma 3.17, which is not an external theorem but a stated internal result that is false as written.

axioms (7)
  • standard math Montalbán's Scott-rank and parameterized-Scott-rank equivalence theorems (Theorems 1.1 and 1.2)
    Used throughout to convert between Scott ranks, Scott sentence complexities, and uniform Δ^0_α-categoricity.
  • standard math Karp's theorem: (A,a)≤_α(B,b) iff every Π_α formula true of a in A is true of b in B
    Foundation for all back-and-forth computations in Section 3.
  • domain assumption Known Scott sentence complexity classifications for countable linear orders ([10], [12], [27])
    The Presburger results are mostly obtained by transferring these external classifications to P_L.
  • domain assumption Finite basis ⇔ computable categoricity on a cone for countable ordered abelian groups (Theorem 4.3, from [8])
    Basis for Corollary 4.4 and the no-Σ3 theorem. The paper states this is 'essentially' Theorem 1.8 of [8]; a full proof is not included.
  • domain assumption Known degree-spectrum facts for linear orders with prescribed jumps ([2], [3], [6], [23])
    Used to realize degree spectra of the form {d: S is computable/c.e. in d^(α)} via V_L.
  • standard math Hölder's theorem: every Archimedean ordered abelian group embeds into R
    Used in Proposition 5.13 to encode subsets S into divisible closures C({1,√p_n}).
  • domain assumption Presburger arithmetic has quantifier elimination after adding divisibility predicates, and residue sequences determine divisibility type
    Used in Lemma 3.12 and Theorem 4.7.

reviewed 2026-08-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Measuring the Complexity of Countable Presburger Models." pith.science (2026). https://pith.science/paper/YSZAGM2J

@misc{pith2026260121118,
  author       = {Pith},
  title        = {Pith review of: Measuring the Complexity of Countable Presburger Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YSZAGM2J}},
  note         = {Machine review of arXiv:2601.21118}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We take two approaches to classifying the complexity of Presburger models: Scott analysis and degree spectra. In particular, we investigate the possible Scott sentence complexities and possible degree spectra of models of Presburger arithmetic. Many of our results will be achieved by showing how given a linear order $\mathcal{L}$, we can construct a Presburger group $P_\mathcal{L}$ that maintains much of the structure of $\mathcal{L}$.

discussion (0)

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

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [1]

    Alvir, N

    R. Alvir, N. Greenberg, M. Harrison-Trainor, and D. Turetsky. Scott complexity of countable structures.Journal of Symbolic Logic, 86(4):1706–1720, 2021

    2021

  2. [2]

    C. Ash, C. Jockusch, and J. Knight. Jumps of orderings.Transactions of the American Mathematical Society, 319:573–599, 1990

    1990

  3. [3]

    Ash and J

    C. Ash and J. Knight. Pairs of recursive structures.Annals of Pure and Applied Logic, 46(3):211–234, 1990

    1990

  4. [4]

    Ash and J

    C. Ash and J. Knight.Computable Structures and the Hyperarithmetical Hierarchy. Elsevier, New York, 2000

    2000

  5. [5]

    Cooper.Computability Theory

    S.B. Cooper.Computability Theory. Taylor & Francis, 2003

    2003

  6. [6]

    Downey and J

    R. Downey and J. Knight. Orderings withαth jump degree0(α).Proceedings of the American Mathematical Society, 114(2):545–552, 1992

    1992

  7. [7]

    K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.Monatshefte für Mathematik und Physik, 38(1):173–198, 1931. 30 JASON BLOCK

    1931

  8. [8]

    Goncharov, S

    S. Goncharov, S. Lempp, and R. Solomon. The computable dimension of ordered abelian groups.Advances in Mathematics, 175(1):102–143, 2003

    2003

  9. [9]

    Gonzalez and M

    D. Gonzalez and M. Harrison-Trainor. Scott spectral gaps are bounded for linear orderings. To appear, available at arXiv:2411.12084

    Pith/arXiv arXiv

  10. [10]

    Gonzalez, M

    D. Gonzalez, M. Harrison-Trainor, and M.-C. “Turbo” Ho. Scott analysis, linear orders, and almost periodic functions.Bulletin of the London Mathematical Society, 57(4):1118–1139, 2025

    2025

  11. [11]

    Gonzalez, M

    D. Gonzalez, M. Łełyk, D. Rossegger, and P. Szlufik. Classifying the complexities of models of arithmetic.To appear

  12. [12]

    Gonzalez and D

    D. Gonzalez and D. Rossegger. Scott sentence complexities of linear orderings.To appear

  13. [13]

    C. Haase. A survival guide to Presburger Arithmetic. 5(3):67–82, 2018

    2018

  14. [14]

    Harison-Trainor

    M. Harison-Trainor. An introduction to the scott complexity of countable structures and a survey of recent results.The Bulletin of Symbolic Logic, 28(1):71–103, 2022

    2022

  15. [15]

    Hirschfeldt, B

    D. Hirschfeldt, B. Khoussainov, R. Shore, and A. Slinko. Degree spectra and computable dimensions in algebraic structures.Annals of Pure and Applied Logic, 115(1):71–113, 2002

    2002

  16. [16]

    O. Hölder. Die Axiome der Quantität und die Lehre vom Maß.Berichte über die Verhand- lungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 53:1–64, 1901

    1901

  17. [17]

    C. Karp. Finite quantifier equivalence.Journal of Symbolic Logic, 36(1):407–412, 1965

    1965

  18. [18]

    J. Knight. Degrees coded in jumps of orderings.Journal of Symbolic Logic, 51(4):1034–1042, 1986

    1986

  19. [19]

    Lipshitz and M.E

    L. Lipshitz and M.E. Nadel. The additive structure of models of arithmetic. InProceedings of the American Mathematical Society, volume 68, 1978

    1978

  20. [20]

    Llewellyn-Jones.Presburger Arithmetic and pseudo-recursive saturation

    D. Llewellyn-Jones.Presburger Arithmetic and pseudo-recursive saturation. PhD thesis, The University of Birmingham, 2001

    2001

  21. [21]

    Marker.Model Theory: An Introduction

    D. Marker.Model Theory: An Introduction. Graduate Texts in Mathematics. Springer New York, 2002

    2002

  22. [22]

    A. Miller. On the Borel classification of the isomorphism class of a countable model.Notre Dame Journal of Formal Logic, 24(1):22–34, 1983

    1983

  23. [23]

    R. Miller. The∆0 2-spectrum of a linear order.Journal of Symbolic Logic, 66(2):470–486, 2001

    2001

  24. [24]

    Miller, B

    R. Miller, B. Poonen, H. Schoutens, and A. Shlapentokh. A computable functor from graphs to fields.Journal of Symbolic Logic, 83(1):326–348, 2018

    2018

  25. [25]

    Montalbán

    A. Montalbán. A robuster Scott rank.Proceedings of the American Mathematical Society, 143(12):5427–5436, 2015

    2015

  26. [26]

    Montalbán.Computable Structure Theory: Within the Arithmetic

    A. Montalbán.Computable Structure Theory: Within the Arithmetic. Perspectives in Logic. Cambridge University Press, 2021

    2021

  27. [27]

    Montalbán.Computable Structure Theory: Beyond the Arithmetic.Draft, 2022

    A. Montalbán.Computable Structure Theory: Beyond the Arithmetic.Draft, 2022

    2022

  28. [28]

    Montalbán and D

    A. Montalbán and D. Rossegger. The structural complexity of models of arithmetic.The Journal of Symbolic Logic, 89(4):1703–1719, 2024

    2024

  29. [29]

    Presburger

    M. Presburger. Uber die Vollstandigkeiteines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt.Comptes-Rendus du ler Congres des Mathematiciens des Pays Slavs, 1929

    1929

  30. [30]

    L.J. Richter. Degrees of structures.Journal of Symbolic Logic, 46(4):723–731, 1981

    1981

  31. [31]

    D. Scott. Logic with denumerably long formulas and finite strings of quantifiers.Journal of Symbolic Logic, 36(1):1104–329, 1965

    1965

  32. [32]

    Tennenbaum

    S. Tennenbaum. Non-archimedean models for arithmetic.Notices of the American Mathe- matical Society, 6(270):44, 1959. Department of Mathematics, College of William & Mary Email address:jeblock@wm.edu URL:https://sites.google.com/view/jasonblockmath/

    1959

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.