Measuring the Complexity of Countable Presburger Models
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 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).Where the paper says it
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 Furthermore, we show in Theorem 4. 7 that there is no Presburger group with Scott
sentence complexity Σ3. 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. 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. 1Where the paper says it
Where the paper says it
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 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. Proposition 2. Given any Turing degree c, there exists a Presburger group whose
degree spectrum is {d : c ≤ d}. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 Furthermore, we show in Theorem 4. 7 that there is no Presburger group with Scott
sentence complexity Σ3. □
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.Where the paper says it
Where the paper says it
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) = 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.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. 3Where the paper says it
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 Observation 2. Let P be a Presburger group, and let V be a divisible ordered
abelian group. 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.Where the paper says it
Where the paper says it
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 □
We will also see by Theorem 3. 34 that if SC(L) = Γα, then SC(PL) ≤ Γ1+α (for
Γ = Π, Σ or d-Σ). 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). 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.Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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).
-
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.
-
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).
-
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
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- Indiscernible Extraction in Theories with Bounded k-splitting
- A non-trivially non-trivial automorphism at an inaccessible cardinal
- The Ordering Principle and Higher Dependent Choice
- On separable pairs of fields and beautiful pairs of separably closed valued fields