Primitive recursive categoricity spectra

This paper investigates the primitive recursive analogue of computable categoricity spectra, demonstrating that these notions coincide for several natural classes of structures, including relatively $\Delta_{2}^{0}$-categorical equivalence structures and linear orders, relatively $\Delta_{3}^{0}$-categorical Boolean algebras, and computably categorical trees as partial orders.

The Gist

Imagine you are a master architect designing a city. In the world of mathematics, this city is a structure (like a line of people, a family tree, or a set of rules for a game).

Usually, mathematicians ask: "Can we build two different versions of this city that look exactly the same, and can we draw a map between them using a computer program?" If the answer is yes, the city is called computably categorical. It means the map is "computable"—you can write a computer script to find the path from one version to the other.

But this paper asks a much stricter question: Can we build that map instantly?

The Core Concept: "Punctual" vs. "Computable"

Think of Computable as a standard delivery truck. It can deliver a package, but it might have to stop at traffic lights, wait for a red light to turn green, or search for an address. It uses "unbounded search." It will eventually get there, but it might take a while.

Think of Punctual (Primitive Recursive) as a high-speed drone. It has a pre-programmed flight path. It cannot stop to search for a traffic light or wait for a signal. It must know exactly where to go at every single second, without ever getting stuck in an infinite loop of "waiting."

The paper investigates: If two cities are isomorphic (identical in structure), can we always find a "drone" (a punctual map) to connect them?

The Big Discovery: The "Speed Limit" of Math

The authors studied several types of mathematical structures (like lines of people, logic blocks, and family trees) and found a fascinating pattern.

They discovered that for many natural types of structures, the "difficulty" of connecting two copies of the city using a drone is exactly the same as the difficulty of connecting them using a truck, provided the truck isn't too slow.

Here is the breakdown of their findings using simple analogies:

1. The Equivalence Structures (The "Grouping Game")

Imagine you have a room full of people, and you are told to group them into circles based on a secret rule (e.g., "people who like the same color").

• The Finding: If you can group these people using a standard computer (a truck), you can also do it with a drone, unless the grouping is incredibly simple (like everyone is in their own circle).
• The Analogy: If the grouping rule is complex enough to require a computer to figure out, it turns out a drone can also figure it out just as fast. The "speed limit" for the drone is the same as the "speed limit" for the truck.

2. The Linear Orders (The "Line of People")

Imagine people standing in a single file line.

• The Finding: If the line is finite, a drone can map it instantly. But if the line is infinite (like the counting numbers 1, 2, 3...), the drone hits a wall.
• The Analogy: To map an infinite line, the drone needs to know the "next" person. Sometimes, figuring out who is next requires a "wait and see" approach (searching). The paper shows that for certain complex infinite lines, the drone cannot do the job instantly. It needs the "truck" (the computer) to do the searching. The complexity of the drone's job matches the complexity of the truck's job exactly.

3. The Boolean Algebras (The "Logic Blocks")

Imagine a set of Lego blocks that can be combined, split, and negated (turned inside out).

• The Finding: Similar to the lines, if the structure of these blocks is complex enough to require a computer to map, the drone's difficulty level is identical to the computer's.
• The Analogy: It's like trying to solve a puzzle. If the puzzle is simple, you can solve it instantly. If it's complex, you need a computer. The paper proves that for these specific puzzles, there is no "middle ground" where a computer can solve it but a drone cannot. They are either both easy or both hard.

4. The Trees (The "Family Trees")

Imagine a family tree where one person has infinitely many children.

• The Finding: If the tree is "finite height" (not infinitely tall), but has a node with infinite branches, the drone can handle it. However, if the tree is too complex, the drone struggles.
• The Analogy: Think of a tree where one branch splits into infinite twigs. The drone can handle the "padding" (the extra twigs) easily. But if the tree's structure is tricky, the drone needs the same level of computational power as the truck to navigate it.

The "Spine" of the Research

The authors introduce a concept called the Spectrum. Think of this as a "difficulty rating" or a "speed limit sign" for a specific type of mathematical structure.

• Old View: We knew that some structures are easy to map (computable).
• New View: This paper asks, "What is the minimum speed required to map these structures if we ban all 'waiting' and 'searching'?"

They found that for many natural structures, the answer is: "The speed limit is exactly the same as the standard computer speed limit."

If a structure requires a "Level 2" computer to map, it also requires a "Level 2" drone. There is no structure where a computer can map it, but a drone cannot (unless the structure is trivially simple).

Why Does This Matter?

In the real world, "unbounded search" (waiting for a signal, searching a database) is slow and sometimes impossible to predict. "Primitive recursive" functions are like hard-coded, instant instructions.

This paper tells us that for many fundamental mathematical structures, there is no hidden efficiency to be gained by removing the "wait and search" steps. If a structure is complex enough to need a computer, it is complex enough to need a computer even if you ban searching. The complexity is inherent to the structure itself, not just the method of calculation.

Summary in One Sentence

The paper proves that for many common mathematical shapes, the "instant" way to map them is just as hard as the "standard" way, meaning you can't cheat the complexity by removing the "waiting" steps in your algorithm.

Technical Summary

Here is a detailed technical summary of the paper "Primitive Recursive Categoricity Spectra" by Nikolay Bazhenov, Heer Tern Koh, and Keng Meng Ng.

1. Problem Statement and Motivation

The paper investigates the primitive recursive analogue of computable categoricity spectra. In classical computable structure theory, a structure is computably categorical if any two computable presentations are isomorphic via a computable isomorphism. The "degree of categoricity" measures the algorithmic complexity required to compute such isomorphisms.

The authors shift the focus from general computable functions to primitive recursive (PR) functions. This shift is motivated by the observation that "efficient" presentations of mathematical structures often avoid unbounded search (a hallmark of general computability).

• Punctual Structures: Structures with domain $\omega$ where all functions and relations are uniformly primitive recursive.
• Punctual Isomorphism: A primitive recursive isomorphism with a primitive recursive inverse.
• The Core Question: For various natural classes of structures, does the property of being "relatively $\Delta^0_n$-categorical" (in the computable sense) coincide with the property that the PR-categoricity spectrum ($PRCatSpec$) is exactly the cone of degrees above $\Delta^0_n$ functions?

Specifically, the authors ask: If a structure $A$ is relatively $\Delta^0_n$-categorical, is it true that $PRCatSpec(A) = \text{Cone}(\Delta^0_n)$? Here, $\text{Cone}(\Delta^0_n)$ is the set of PR-degrees that can compute any total $\Delta^0_n$ function.

2. Methodology

The authors employ a combination of construction techniques and coding strategies within the framework of primitive recursive functions.

• PR-Degrees: They utilize the reduction $f \leq_{PR} g$, meaning $f$ can be obtained from $g$ via a primitive recursive scheme. This measures the "primitive recursive content" of functions.
• Coding via Delay: A central technique involves constructing two punctual presentations, $A$ (the "fast" or standard copy) and $B$ (the "delayed" copy). The construction of $B$ is designed to delay the enumeration of certain elements or the growth of certain substructures until a specific computable function $g$ converges.
  • Since $B$ must remain punctual (primitive recursive), the delay cannot be infinite. Instead, the construction encodes the stabilization stage of a $\Delta^0_n$ approximation into the structural properties of $B$ (e.g., the size of equivalence classes, the length of intervals in linear orders, or the depth of generators in Boolean algebras).
• Recovery via Isomorphism: The proofs demonstrate that any isomorphism $h: A \to B$ (and its inverse) must "reveal" the encoded information. By computing $h$ on specific elements in $A$, one can primitive-recursively recover the stabilization stages of the approximating functions, thereby computing the target $\Delta^0_n$ function.
• Priority Arguments: For higher complexity classes (specifically $\Delta^0_3$), the authors employ sophisticated priority arguments and "nesting" strategies to encode multiple stabilization stages simultaneously without violating the punctual nature of the structures.

3. Key Contributions and Results

The paper establishes that for several major classes of structures, the primitive recursive categoricity spectrum coincides exactly with the cone of degrees corresponding to the relative categoricity level in the computable setting.

A. Equivalence Structures

• Result: For equivalence structures that are relatively $\Delta^0_1$-categorical (but not punctually categorical), $PRCatSpec(E) = \text{Cone}(\Delta^0_1)$. For those relatively $\Delta^0_2$-categorical (but not $\Delta^0_1$), $PRCatSpec(E) = \text{Cone}(\Delta^0_2)$.
• Mechanism: The authors encode the halting times of computable functions into the sizes of equivalence classes or the number of classes of a specific size. By delaying the enumeration of classes of size $k$ until a function $g(x)$ converges, they force any isomorphism to reveal the convergence stage.

B. Linear Orders

• Result:
  • Relatively $\Delta^0_1$-categorical linear orders (not punctually categorical): $PRCatSpec(L) = \text{Cone}(\Delta^0_1)$.
  • Relatively $\Delta^0_2$-categorical linear orders (not $\Delta^0_1$): $PRCatSpec(L) = \text{Cone}(\Delta^0_2)$.
  • Specific structures like $\omega * \eta$ and $Shuffle(\{\omega\} \cup F)$ (where $F$ is a computable family of finite orders) are shown to have $PRCatSpec = \text{Cone}(\Delta^0_3)$.
• Mechanism:
  • For $\Delta^0_1$: Encoding is done by "densifying" intervals (inserting copies of $\eta$) only after a function converges.
  • For $\Delta^0_3$: The authors use a complex "nesting" strategy. They encode stabilization stages $s_x$ and $t_{x,s}$ by manipulating the structure of $\omega$-chains and $\eta$-intervals. They utilize a "true path" argument (reminiscent of $\emptyset''$-priority arguments) to separate the $\omega$ and $\eta$ parts of the order, allowing the recovery of $\Delta^0_3$ information.

C. Boolean Algebras

• Result:
  • Relatively computably categorical (infinite): $PRCatSpec(B) = \text{Cone}(\Delta^0_1)$.
  • Relatively $\Delta^0_2$-categorical: $PRCatSpec(B) = \text{Cone}(\Delta^0_2)$.
  • Relatively $\Delta^0_3$-categorical (specifically involving $Int(\omega * \eta)$ and $Int(\omega + \eta)$): $PRCatSpec(B) = \text{Cone}(\Delta^0_3)$.
• Mechanism: The authors use the tree of generators for Boolean algebras.
  • For $\Delta^0_1$ and $\Delta^0_2$: They encode information by splitting atoms or controlling the number of atoms below specific generators.
  • For $\Delta^0_3$: They construct a "nested" tree of generators where the depth of the tree corresponds to the stabilization stages of a $\Delta^0_3$ function. They carefully manage the number of atoms to ensure that isomorphisms must map to generators of sufficient "depth" to recover the information.

D. Trees as Partial Orders

• Result:
  • Every computable tree with at least one node having infinitely many successors has a punctual presentation (Theorem 5.1).
  • For punctual trees of finite height with specific infinite branching properties, if the tree is computably categorical but not punctually categorical, then $PRCatSpec(T) = \text{Cone}(\Delta^0_1)$.
• Mechanism: The construction uses a "padding" node with infinitely many successors to absorb delays. The width or height of subtrees is controlled to encode the convergence of computable functions.

4. Significance and Implications

1. Bridging Complexity Classes: The paper successfully bridges the gap between classical computable categoricity (Turing degrees) and primitive recursive categoricity (PR-degrees). It demonstrates that for "natural" classes of structures, the algorithmic complexity of isomorphisms in the primitive recursive setting mirrors the complexity in the computable setting, provided one looks at the correct level of the arithmetical hierarchy ($\Delta^0_n$).
2. Limits of Punctuality: The results highlight that structures requiring unbounded search for categoricity (like the countable dense linear order or random graphs) generally do not admit punctually categorical presentations. The "finitistic" nature of punctual categoricity (Theorem 1.2) is reinforced, showing that infinite structures with non-trivial categoricity spectra inherently require unbounded search to classify.
3. Counterexamples: The authors note that while the coincidence holds for the classes studied, it is not universal. In a companion paper ([BKN]), they provide counterexamples where the notions diverge, suggesting that the coincidence observed here is a specific feature of these well-behaved natural classes.
4. Methodological Advancement: The techniques developed, particularly the "nesting" of strategies for $\Delta^0_3$ structures and the manipulation of generator trees in Boolean algebras, provide new tools for analyzing the fine-grained complexity of isomorphisms in restricted computability models.

In conclusion, the paper establishes a robust correspondence between the relative categoricity of computable structures and the PR-categoricity spectra of their punctual counterparts for equivalence structures, linear orders, Boolean algebras, and trees, confirming that the "primitive recursive content" of isomorphisms is precisely captured by the $\Delta^0_n$ hierarchy in these contexts.