Measuring the Complexity of Countable Presburger Models

arXiv:2601.21118 · math.LO · Submitted 2026-01-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Measuring the Complexity of Countable Presburger Models".

Emmy: Here's the gist of the paper. Measuring the complexity of countable Presburger models investigates the possible Scott sentence complexities and degree spectra of models of Presburger arithmetic, which is just the first order theory of (Z, +,.

Ada: Scott Analysis and Complexity Bounds The paper examines the Scott rank and Scott sentence complexity of Presburger groups by investigating how a given linear order L can be used to construct a Presburger group PL that maintains much of the structure of L <ref:2601.21118#pg3>.

Emmy: The authors find that there exist Presburger groups with specific Scott sentence complexities, such as "Πα for all ordinals α > 1" and "d-Σα for all successor ordinals α > 1" <ref:2601.21118#pg10>.

Ada: Furthermore, they show that there is no Presburger group with Scott sentence complexity Σ3 <ref:2601.21118#pg9>.

Paper summary: Ada: Looking back at "Measuring the Complexity of Countable Presburger Models", we see that this work really maps out the landscape for describing these arithmetic models. The authors show how to use linear orders as a bridge to understand the Scott sentence complexities and degree spectra of Presburger groups.

Emmy: And they've given us some very specific examples, like those involving "Πα for all ordinals alpha greater than one," which tells us exactly what kinds of sentence complexities are achievable in this context.

Kolya: From a computational view, the link between the degree spectrum and linear orders is pretty solid, and their construction showing how to achieve any cone above a Turing degree c is quite powerful for understanding computability within these groups.

Ada: The implication for us is that we can systematically generate Presburger models with very precise complexity properties, allowing us to explore the relationship between descriptive set theory and computability in a way we haven't before.

Emmy: It really highlights how much structure is hidden in what looks like a simple additive group, showing that it's rich enough to support a wide range of mathematical behaviors depending on the underlying linear order you choose.

Kolya: The limitation they mention—that linear orders aren't universal for degree spectra—is important because it suggests that if we want to fully characterize these properties, we might need to look at broader classes of structures, like rings or fields.

Ada: So, in short, the paper gives us a detailed toolkit for measuring the complexity of countable Presburger models by connecting them back to linear orders and Turing degrees.

Emmy: It's a solid piece of work that shows how different mathematical concepts weave together when you look closely at structures like Presburger arithmetic.

Conclusion: Ada: So, this paper "Measuring the Complexity of Countable Presburger Models" is about figuring out how complex these arithmetic models are by looking at their Scott sentences and degree spectra.

Emmy: Basically, they use linear orders to build up Presburger groups and see what kind of complexity those groups can have.

Ada: They find that you can get specific sentence complexities, like "Πα for all ordinals alpha greater than one," but they also show there are limits, like no group with complexity sigma three.

Kolya: From a probabilistic standpoint, the work on degree spectra is interesting because they show we can construct Presburger groups whose degree spectrum matches any cone above a specific Turing degree c.

Emmy: That links the structure of these groups directly to computability in a way that seems very structured.

Ada: The authors use back-and-forth relations to connect the Scott analysis of linear orders directly to the complexity of these Presburger groups.

Kolya: The main takeaway is that linear orders aren't universal for degree spectra, which means we need broader structures, like rings or fields, if we want a complete picture.

Ada: It opens up questions about whether certain complexities exist and whether they can be achieved with different types of underlying structures.

Emmy: And they raise some big questions about the relationship between the degree spectra of a divisible group and its Presburger group version.

JASON BLOCK

math.LO

Submitted: 2026-01-28

Updated: 2026-06-16

Comments: Accepted to appear in ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik

Journal ref: ZML, vol. 72, 507-531 (2026)

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: Measuring the complexity of countable Presburger models investigates the possible Scott sentence complexities and degree spectra of models of Presburger arithmetic…

Key concepts

Scott Rank and Sentence Complexity
These measures quantify the logical complexity of mathematical structures. Scott rank relates to how hard it is to distinguish elements in a structure using first-order logic, while sentence complexity describes the complexity of a single sentence that uniquely defines the structure.
Degree Spectrum
This is the set of Turing degrees associated with all possible copies (isomorphic structures) of a given mathematical object. It tells us which computational levels are achievable when we consider different instances of that structure.
Presburger Groups (PL)
These are specific mathematical structures formed by combining linear orders and addition, which form the basis for Presburger arithmetic. The paper focuses on how these groups can be constructed from linear orders to achieve specific complexity results.
Linear Order L
A linear order is a set with a total ordering (like the natural numbers or real numbers). In this context, a specific linear order is used as the building block to construct Presburger groups and determine their properties.

Terminology

Summary

Measuring the complexity of countable Presburger models investigates the possible Scott sentence complexities and degree spectra of models of Presburger arithmetic, which is just the first order theory of (Z, +,. p. 0

Where the paper says it

Given a countable structure A, we define the degree spectrum of A to be the set of Turing degrees of copies of A. In this article we examine the possible Scott ranks, Scott sentence complexities and degree spectra of models of Presburger arithmetic, which is just the first order theory of (Z, +, <, 0, 1).

Scott Analysis and Complexity Bounds

The paper examines the Scott rank and Scott sentence complexity of Presburger groups by investigating how a given linear order L can be used to construct a Presburger group PL that maintains much of the structure of L <ref:2601.21118#pg3>. The authors find that there exist Presburger groups with specific Scott sentence complexities, such as "Πα for all ordinals α > 1 and d-Σα for all successor ordinals α > 1" <ref:2601.21118#pg10>. Furthermore, they show that there is no Presburger group with Scott sentence complexity Σ3 <ref:2601. p. 1

Where the paper says it

Furthermore, we show in Theorem 4. 7 that there is no Presburger group with Scott sentence complexity Σ3.

21118#pg9>. This implies that Presburger arithmetic has a complete Scott spectrum, meaning its Scott spectrum contains all countable positive ordinals <ref:2601. p. 0
Where the paper says it

That is, its Scott spectrum contains all countable positive ordinals. Further Scott analysis was done for Peano arithmetic by Gonzalez, Łełyk, Rossegger and Szlufik in [11] where they found the 1 arXiv:2601.

21118#pg4>.

Degree Spectra and Computability

The degree spectrum of a structure A is defined as the set of Turing degrees of copies of A <ref:2601.21118#pg5>. The paper shows that for Presburger groups, specifically those of the form PL, the degree spectrum DgSp(PL) = DgSp(L) where L is a linear order <ref:2601. p. 1

Where the paper says it

8 that DgSp(PL) = {d : d ′ ∈ DgSp(L)}. Thus, we may make use of past results about the degree spectra of linear orders to find degree spectra for Presburger groups.

21118#pg6>. They also establish that given any Turing degree c, there exists a Presburger group whose degree spectrum is exactly the cone above c <ref:2601. p. 5
Where the paper says it

Proposition 2. Given any Turing degree c, there exists a Presburger group whose degree spectrum is {d : c ≤ d}.

21118#pg8>. This demonstrates that Presburger groups can realize many types of degree spectra based on computable ordinals and sets S <ref:2601. p. 0
Where the paper says it

In contrast, there are many nonstandard models of Presburger arithmetic with computable copies (e. Thus, although degree spectra can distinguish the standard model of Peano arithmetic, it fails to do so for Presburger arithmetic.

21118#pg6>.

Structural Results for Linear Orders

The analysis utilizes back-and-forth relations to establish relationships between the Scott analysis of linear orders and Presburger groups <ref:2601.21118#pg10>. They prove that for any countable linear order A and B, (A, ⃗a) ≤α (B, ⃗b) if and only if (PA, π(⃗a)) ≤1+α (PB, π(⃗b)) <ref:2601. p. 0

Where the paper says it

That is, its Scott spectrum contains all countable positive ordinals. Further Scott analysis was done for Peano arithmetic by Gonzalez, Łełyk, Rossegger and Szlufik in [11] where they found the 1 arXiv:2601.

21118#pg4>. This result allows them to translate complexity results from linear orders to Presburger groups <ref:2601. p. 1
Where the paper says it

In particular, the authors of [10] and [12] were able to find all the possible Scott complexities of linear orders. We are able to carry over many of their results to Presburger groups of the form PL.

21118#pg10>.

Characterization of Non-Plain Groups

The paper addresses non-plain Presburger groups, noting that recursively saturated Presburger groups all have Scott rank 2 <ref:2601.21118#pg9>. They also provide a proof that there is no Presburger group with Scott sentence complexity Σ3 by considering the dimension of the group <ref:2601. p. 1

Where the paper says it

Furthermore, we show in Theorem 4. 7 that there is no Presburger group with Scott sentence complexity Σ3.

21118#pg10>. This shows that a structure having a finite basis implies it has a Σ in 3 Scott sentence <ref:2601. p. 2
Where the paper says it

□ It should be noted that a Scott rank will always be a countable ordinal. A structure A is uniformly ∆0 α-categorical if there is a Turing operator Ψ along with an oracle S ⊆ N such that for all structures B, C ∼= A, Ψ (D(B)⊕D(C)⊕S) (β) is an isomorphism from B to C, where β = α if infinite and β = α−1 if finite.

21118#pg10>.

Degree Spectrum Construction via Divisible Groups

The paper constructs Presburger groups with specific degree spectra by leveraging divisible ordered abelian groups <ref:2601.21118#pg6>. They show that for any set S ⊆ N, there exists a Presburger group P = V × Z such that DgSp(V) = DgSp(P) = d: S is c.e. in d'(α) <ref:2601.21118#pg6>. This construction relies on the fact that the degree spectrum of a divisible ordered abelian group can be related to the Turing degrees of sets computable in certain jumps <ref:2601. p. 3

Where the paper says it

None of the structures discussed in this paper are automorphically trivial, and so all degree spectra discussed will be upwards closed. Note that if P is a Presburger group with a computable copy (such as Z or Q×Z) then DgSp(P) is just the set of all Turing degrees.

21118#pg6>.

Universal Properties and Open Questions

The paper concludes by posing several open questions regarding Scott analysis, such as whether Presburger groups with Scott sentence complexity Σ4 exist <ref:2601.21118#pg7>. It also raises questions about the relationship between the degree spectra of a divisible ordered abelian group V and its Presburger group P = V × Z <ref:2601. p. 6

Where the paper says it

Observation 2. Let P be a Presburger group, and let V be a divisible ordered abelian group.

21118#pg6>. The authors suggest that linear orders are not universal for degree spectra, necessitating looking beyond structures of the form PL to fully characterize these properties <ref:2601. p. 1
Where the paper says it

In particular, the authors of [10] and [12] were able to find all the possible Scott complexities of linear orders. We are able to carry over many of their results to Presburger groups of the form PL.

21118#pg7>.

Further Questions

The paper outlines several further questions, including whether SR(PL) must equal 1 + SR(L) for all linear orders L <ref:2601.21118#pg10>, and whether SC(PL) must equal Γ1+α if SC(L) = Γα <ref:2601. p. 8

Where the paper says it

□ We will also see by Theorem 3. 34 that if SC(L) = Γα, then SC(PL) ≤ Γ1+α (for Γ = Π, Σ or d-Σ).

21118#pg10>. These questions relate to the properties of automorphism orbits and the complexity of embedding structures <ref:2601. p. 3
Where the paper says it

4 JASON BLOCK permutation of A that fixes this subset is an automorphism. Such structures are called automorphically trivial (not to be confused with having a trivial automorphism group).

21118#pg10>. It also questions whether Presburger groups are universal for degree spectra, suggesting that classes like rings or fields might be more appropriate for this characterization <ref:2601. p. 0
Where the paper says it

We refer to models of this theory as Presburger groups. Questions regarding degree spectra and Scott analysis have long been asked about Peano arithmetic, the much studied sub-theory of Th(N, +, ·, <, 0, 1), which includes multiplication.

21118#pg10>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI systems can determine if a given countable structure has a specific Scott sentence complexity by analyzing its Scott rank and parameterized Scott rank using formulas like SC(A) = d-Σα if and only if pSR(A) = α + 1 and SR(A) = α + 2.

  2. Improved AI systems can compute the degree spectrum of Presburger groups, specifically determining DgSp(PL) as the set of Turing degrees of linear orders DgSp(L), where L is a linear order, by leveraging Theorem 5.8: DgSp(PL) = DgSp(VL) = opset d' in DgSp(L).

  3. Improved AI systems can construct Presburger groups with specific degree spectra, such as those corresponding to the cone above a Turing degree d, by using the construction in Proposition 5.4: Given any Turing degree d, there exists a divisible ordered abelian group whose degree spectrum is the cone above d.

  4. Improved AI systems can distinguish between different types of Presburger groups based on their Scott sentence complexity by checking properties derived from back-and-forth relations, such as Lemma 3.12: If two tuples p and r satisfy the same Π0 formulas, and ρ(p) = ρ(r) for each i, then (R, r) ≤1 (P, p).

  5. Improved AI systems can identify whether a Presburger group is plain by checking if every element has the same residue sequence as an integer: "A structure A is a Presburger group if and only if A is a discretely ordered abelian group (with the constant 1 defined as the successor of 0) that models the following sentence for all integers n ≥ 2: (∀x)(∃y)[ny = x ∨ ny + 1 = x ∨ · · · ∨ ny + (n − 1) = x]."

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 L, we can construct a Presburger group P L that maintains much of the structure of L.

Sources

Related papers