Unifying Boolean and Algebraic Descriptive Complexity

Chanus, Baptiste; Mazza, Damiano; Rogers, Morgan

doi:10.4230/LIPIcs.FSCD.2025.13

Unifying Boolean and Algebraic Descriptive Complexity

Baptiste Chanus

Université Sorbonne Paris Nord, LIPN, CNRS, Villetaneuse, France Damiano Mazza

CNRS, LIPN, Université Sorbonne Paris Nord, Villetaneuse, France Morgan Rogers

Université Sorbonne Paris Nord, LIPN, CNRS, Villetaneuse, France

Abstract

We introduce ultrarings, which simultaneously generalize commutative rings and Boolean lextensive categories. As such, they allow to blend together standard algebraic notions (from commutative algebra) and logical notions (from categorical logic), providing a unifying descriptive framework in which complexity classes over arbitrary rings (as in the Blum, Schub, Smale model) and usual, Boolean complexity classes may be captured in a uniform way.

Keywords and phrases:

Descriptive complexity theory, Categorical logic, Blum-Shub-Smale complexity

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Complexity theory and logic ; Theory of computation

\rightarrow

Complexity classes ; Theory of computation

\rightarrow

Finite Model Theory

DOI:

10.4230/LIPIcs.FSCD.2025.13

Event:

10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)

Editors:

Maribel Fernández

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Descriptive complexity measures the difficulty of computational problems in terms of the expressiveness that a logical language needs to describe them, rather than in terms of the power that a machine needs to solve them. Initiated in the 1970s with Fagin’s theorem [14], which provides a characterization of the class $\mathsf{NP}$ , it has since been extended to capture virtually every other so-called “syntactic” complexity class [17].

Computational problems are usually defined as sets of finite objects (graphs, numbers, programs…) encoded as binary strings. Descriptive complexity regards such objects as totally ordered finite structures of a first-order language $\mathfrak{S}$ . A formula $\varphi$ over an extension $\mathfrak{T}$ of $\mathfrak{S}$ plays the role of a machine, accepting a finite structure $s$ of $\mathfrak{S}$ if $s$ is a model of $\varphi$ . The more expressive $\mathfrak{T}$ is, the more powerful the corresponding machine. Notice that $\mathfrak{T}$ is typically not a first-order extension: for example, $\mathsf{NP}$ corresponds to allowing second-order existential quantifiers [14], and $\mathsf{P}$ corresponds to allowing fixpoint operators [16].

Computability and complexity may be meaningfully extended beyond finite objects. An interesting, well-known example is Blum, Shub and Smale’s (BSS) model of computation over the real numbers [5]. Rather than having a tape whose cells contain either $0$ or $1$ , BSS machines have a “tape” whose cells contain arbitrary real numbers. Usual Boolean operations are replaced by field operations, and testing the order relation $\leq$ plays the role of a conditional. Problems become sets of finite sequences of real numbers, and complexity may be developed in the usual way, including a definition of $\mathsf{P}$ , $\mathsf{NP}$ and complete problems.

Grädel and Meer [15] showed how the descriptive approach may be applied to the BSS model. The idea is to introduce a kind of hybrid finite structure, part logical and part algebraic. The algebraic part takes care of the data manipulated by the machine (real numbers and field operations), the logical part describes the discrete steps of the BSS machine, allowing the transfer of Fagin’s [14] and Immerman’s [16] logical characterizations of $\mathsf{P}$ and $\mathsf{NP}$ to the BSS setting.

We provide a framework in which descriptive complexity may be uniformly formulated over Booleans and over real numbers (or other commutative rings) using a single logico-algebraic language. This language arises from a combination of categorical logic and commutative algebra, taking the form of ultrarings, a new algebraic object whose introduction is the main contribution of this paper.

To understand ultrarings, one may start from categorical logic. This is a vast subject [21, 18, 19], so we concentrate on what is relevant for our purposes. Define a Boolean lextensive category to be a category with finite limits and finite pullback-stable disjoint coproducts in which every subobject has a complement. A primordial example is $\mathbf{Fin}$ , the category of finite sets. Call a functor preserving finite limits and finite coproducts logical. Categorical logic gives us a correspondence between Boolean lextensive categories and classical finite-limit theories (or cartesian theories in Johnstone’s terminology [19]). These are theories of first-order classical logic whose axioms are closed formulas of the form $\forall x_{1}\ldots\forall x_{n}.\varphi$ with $\varphi$ quantifier-free.¹¹1Actually, $\varphi$ may contain provably unique existentials, but this is irrelevant at the present level of detail. The correspondence is as follows:

$\blacksquare$

from a classical finite-limit theory $\mathfrak{T}$ one can construct a small Boolean lextensive category $\mathrm{Syn}(\mathfrak{T})$ , the syntactic category of $\mathfrak{T}$ ;
$\blacksquare$

each small Boolean lextensive category $\mathcal{B}$ induces a classical finite-limit theory $\mathrm{Lang}(\mathcal{B})$ such that $\mathrm{Syn}(\mathrm{Lang}(\mathcal{B}))$ is equivalent to $\mathcal{B}$ ;
$\blacksquare$

one may define models of $\mathfrak{T}$ in any Boolean lextensive category $\mathcal{K}$ , and models of $\mathfrak{T}$ in $\mathcal{K}$ correspond to logical functors $\mathrm{Syn}(\mathfrak{T})\to\mathcal{K}$ .

In the last point, taking $\mathcal{K}=\mathbf{Fin}$ yields finite models in the usual sense, which suggests a categorical approach to descriptive complexity. In fact, there is a classical finite-limit theory $\mathfrak{Str}$ such that its finite models, modulo isomorphism, are exactly binary strings. Moreover, an extension $\mathfrak{T}$ of $\mathfrak{Str}$ induces a logical functor $\mathrm{Syn}(\mathfrak{Str})\to\mathrm{Syn}(\mathfrak{T})$ (intuitively, an injection), so if we have a binary string seen as a functor $s:\mathrm{Syn}(\mathfrak{Str})\to\mathbf{Fin}$ , we may ask whether it factors through $\mathrm{Syn}(\mathfrak{T})$ , which is to say whether $s$ may be extended to a model of $\mathfrak{T}$ . This means that extensions of $\mathfrak{Str}$ express computational problems (i.e., subsets of $\{0,1\}^{\ast}$ ). The results of §4.2 capture the classes $\mathsf{P}$ and $\mathsf{NP}$ as certain forms of extensions.

The above framework only expresses Boolean computation. However, the fact that classical finite-limit theories may be regarded as presentations for their Boolean lextensive syntactic categories is analogous to the presentation of a ring by a set $X$ equipped with a set $S$ of integer polynomials with variables in $X$ . The analogy is as follows:

$\blacksquare$

each presentation $(X,S)$ induces a commutative ring $\mathbb{Z}[X]/\langle S\rangle$ ;
$\blacksquare$

each commutative ring $R$ admits a presentation $(X_{R},S_{R})$ such that $\mathbb{Z}[X_{R}]/\langle S_{R}\rangle\cong R$ ;
$\blacksquare$

given a commutative ring $k$ , a solution in $k$ of the system $\{p=0\}_{p\in S}$ is the same thing as a ring homomorphism $\mathbb{Z}[X]/\langle S\rangle\to k$ .

Notice how finding a model of a theory whose set of (closed) axioms is $S$ may be seen as “solving the system” $\{\lnot\varphi=0\}_{\varphi\in S}$ , where $0$ is false, so the last point still fits the analogy.

Ultrarings turn the above analogy into two instances of a common construction. That is, ultrarings simultaneously generalize Boolean lextensive categories and commutative rings, and we have a notion of annular theory of which classical finite-limit theories and ring presentations are special cases. An annular theory is given by (possibly empty) sets of sorts, generators over the sorts, and equations. The latter are formulated using polynomials, which are a generalization of first-order formulas. Commutative rings are special “sortless” ultrarings: in case the are no sorts, a polynomial is exactly a polynomial in the usual algebraic sense. So ultrarings generalize commutative rings by adding sorts, and they generalize first-order logic by allowing ring operations on truth values.

Technically, an ultraring is a certain kind of small category (Definition 3), and the categories of commutative rings and of small Boolean lextensive categories are full subcategories of the category of ultrarings: to see a commutative ring $R$ as an ultraring, we take the category of free $R$ -modules of finite rank; to see a Boolean lextensive category $\mathcal{B}$ as an ultraring, we take the Kleisli category of the partiality monad over $\mathcal{B}$ (see §2.2).

In particular, there is an ultraring $\mathbb{R}$ corresponding to the field of real numbers and an ultraring $\mathbb{F}_{1}$ corresponding to the category of finite sets ( $\mathbb{F}_{1}$ is in fact the initial ultraring). Let $\mathbb{K}$ be either $\mathbb{R}$ or $\mathbb{F}_{1}$ . We will show that there is an annular theory $\mathfrak{Str}$ and an associated ultraring $\mathbb{K}[\mathfrak{Str}]$ such that, modulo isomorphism, a morphism $\mathbb{K}[\mathfrak{Str}]\to\mathbb{K}$ is a finite sequence of real numbers if $\mathbb{K}=\mathbb{R}$ , or a binary string if $\mathbb{K}=\mathbb{F}_{1}$ . The former is a typical input of a BSS machine over $\mathbb{R}$ , the latter of a Turing machine. This gives a first idea of how both algebraic and Boolean data may be treated uniformly.

Computability and complexity may be expressed in ultrarings by means of algebras: given an ultraring $\mathcal{R}$ , an $\mathcal{R}$ -algebra is (roughly) an ultraring $\mathcal{A}$ together with a morphism $\mathcal{R}\to\mathcal{A}$ . A $\mathbb{K}[\mathfrak{Str}]$ -algebra $\mathcal{A}$ expresses a computational problem $\Gamma_{\mathbb{K}}(\mathcal{A})$ as follows: a string $\mathbb{K}[\mathfrak{Str}]\to\mathbb{K}$ is in $\Gamma_{\mathbb{K}}(\mathcal{A})$ iff it factors through $\mathcal{A}$ . Our main result (Theorem 22) identifies classes of $\mathbb{K}[\mathfrak{Str}]$ -algebras whose associated problems yield the standard classes $\mathsf{RE}$ (recursively-enumerable), $\mathsf{NP}$ and $\mathsf{P}$ defined either in terms of BSS machines over $\mathbb{R}$ or in terms of Turing machines, depending on how $\mathbb{K}$ is instantiated.

In logical terms, a $\mathbb{K}[\mathfrak{Str}]$ -algebra $\mathcal{A}$ may be presented by an extension $\mathfrak{T}$ of the theory $\mathfrak{Str}$ , and $x\in\Gamma_{\mathbb{K}}(\mathcal{A})$ is equivalent to the fact that $x$ , seen as a model of $\mathfrak{Str}$ in $\mathbb{K}$ , may be extended to a model of $\mathfrak{T}$ . This highlights a shift with respect to descriptive complexity: rather than changing logical language for each complexity class, we fix one language (in the Boolean case, what categorical logicians would call “finite-limit logic”) and express complexity by means of logical extensions of $\mathfrak{Str}$ in this same language.

The rest of the paper introduces ultrarings (§2), how they may be presented by annular theories in the above sense (§3), and how they may be used to uniformly formulate complexity classes over both Booleans and real numbers (§4). We conclude with some perspectives (§5).

2 Ultrarings

2.1 Main Definitions

In what follows, we often abbreviate composition of arrows $f\circ g$ by $f g$ . If $(\mathcal{C},\otimes,I,\gamma)$ is a symmetric monoidal category, where $\gamma$ is its symmetry, we denote by $\beta:I\otimes I\to I$ the canonical isomorphism. By “symmetric monoidal functor” we will always mean strong symmetric monoidal functor (i.e., tensor and unit are preserved up to iso).

A Frobenius sesquimonoid in a symmetric monoidal category is an object $A$ equipped with arrows $\delta:A\to A\otimes A$ , $\varepsilon:A\to I$ , $\delta^{\ast}:A\otimes A\to A$ such that $(A,\delta,\varepsilon)$ is a commutative comonoid, $\delta^{\ast}$ is commutative ( $\delta^{\ast}\gamma_{A,A}=\delta^{\ast}$ ), associative ( $\delta^{\ast}(\mathrm{id}\otimes\delta^{\ast})=\delta^{\ast}(\delta^{\ast}% \otimes\mathrm{id})$ , left inverse to $\delta$ ( $\delta^{\ast}\delta=\mathrm{id}_{A}$ ) and verifies the Frobenius law $(\mathrm{id}_{A}\otimes\delta^{\ast})(\delta\otimes\mathrm{id}_{A})=\delta% \delta^{\ast}=(\delta^{\ast}\otimes\mathrm{id}_{A})(\mathrm{id}_{A}\otimes\delta)$ .

Initial objects will be denoted by $0$ . Recall that a (binary) coproduct diagram over an object $A$ is a pair of arrows $\iota_{1}:A_{1}\to A$ , $\iota_{2}:A_{2}\to A$ , called injections, such that, for every $f_{1}:A_{1}\to B$ , $f_{2}:A_{2}\to B$ there is a unique arrow $[f_{1},f_{2}]:A\to B$ such that $[f_{1},f_{2}]\iota_{i}=f_{i}$ . In that case, we write $A=A_{1}\oplus A_{2}$ .

A distributive monoidal category is a symmetric monoidal category with finite coproducts such that, for all objects $A, B, C$ , $A\otimes 0$ is initial and the arrow $\chi_{A,B,C}:=[\mathrm{id}_{A}\otimes\iota_{1},\mathrm{id}_{A}\otimes\iota_{2}% ]:(A\otimes B)\oplus(A\otimes C)\to A\otimes(B\oplus C)$ is an isomorphism.

Recall that an initial object which is also terminal is called a zero object and that any category with a zero object has, for any pair of objects $A, B$ , a zero morphism $0_{A,B}:A\to B$ obtained by composing the terminal and initial arrows $A\to 0\to B$ . Also, for any pair of objects $A_{1},A_{2}$ , the category has coinjections²²2We refer to these as coinjections rather than projections to avoid the reader assuming that the coproducts are also products. defined by:

\displaystyle\iota_{1}^{\ast}

\displaystyle:=[\mathrm{id}_{A_{1}},0_{A_{2},A_{1}}]:A_{1}\oplus A_{2}\to A_{1},

\displaystyle\iota_{2}^{\ast}

\displaystyle:=[0_{A_{1},A_{2}},\mathrm{id}_{A_{2}}]:A_{1}\oplus A_{2}\to A_{2}.

It immediately follows that these verify

\iota^{\ast}_{i}\iota_{j}=\left\{\begin{array}[]{ll}\mathrm{id}_{A_{i}}&\text{% if }i=j\\ 0_{A_{j},A_{i}}&\text{if }i\neq j.\end{array}\right.

(1)

Definition 1.

A $\delta^{\ast}$ -category is a distributive monoidal category $(\mathcal{C},\otimes,I,\gamma)$ with a zero object such that each object $A$ is equipped with a Frobenius sesquimonoid structure $\delta_{A},\varepsilon_{A},\delta_{A}^{\ast}$ satisfying, for every objects $A,B,A_{1},A_{2}$ ,

$\displaystyle\delta_{A\otimes B}$	$\displaystyle=(\mathrm{id}_{A}\otimes\gamma_{A,B}\otimes\mathrm{id}_{B})(% \delta_{A}\otimes\delta_{B})$	$\displaystyle\varepsilon_{A\otimes B}$	$\displaystyle=\beta(\varepsilon_{A}\otimes\varepsilon_{B})$	$\displaystyle\delta_{I}$	$\displaystyle=\beta^{-1},$
$\displaystyle\delta^{\ast}_{A\otimes B}$	$\displaystyle=(\delta^{\ast}_{A}\otimes\delta^{\ast}_{B})(\mathrm{id}_{A}% \otimes\gamma_{A,B}\otimes\mathrm{id}_{B})$	$\displaystyle\varepsilon_{I}$	$\displaystyle=\mathrm{id}_{I}$	$\displaystyle\delta^{\ast}_{I}$	$\displaystyle=\beta,$
$\displaystyle\hskip-15.0pt\delta^{\ast}_{A_{1}\oplus A_{2}}(\iota_{i}\otimes% \iota_{j})$	$\displaystyle=\left\{\begin{array}[]{ll}\iota_{i}\delta^{\ast}_{A_{i}}&\text{% if }i=j\\ 0_{A_{i}\otimes A_{j},A_{1}\oplus A_{2}}&\text{if }i\neq j\end{array}\right.$	$\displaystyle\delta_{A_{1}\oplus A_{2}}\iota_{i}$	$\displaystyle=(\iota_{i}\otimes\iota_{i})\delta_{A_{i}}$	$\displaystyle\varepsilon_{A_{1}\oplus A_{2}}\iota_{i}$	$\displaystyle=\varepsilon_{A_{i}},$

and such that, for all $f,g:A\rightrightarrows B$ , $\delta^{\ast}_{B}(f\otimes\mathrm{id})=\delta^{\ast}_{B}(g\otimes\mathrm{id})$ implies $f=g$ .

A morphism $F:\mathcal{C}\to\mathcal{D}$ of $\delta^{\ast}$ -categories is a finite-coproduct-preserving symmetric monoidal functor with structural isomorphisms $\varphi_{A,B}:FA\otimes FB\to F(A\otimes B)$ and $\psi:I\to FI$ such that, for each object $A$ of $\mathcal{C}$ , $F\delta_{A}=\varphi_{A,A}\delta_{FA}$ , $F\delta^{\ast}_{A}=\delta^{\ast}_{FA}\varphi^{-1}_{A,A}$ and $F\varepsilon_{A}=\psi\varepsilon_{FA}$ .

In the sequel, subscripts such as those in $\mathrm{id}_{A},\delta_{A},\varepsilon_{A}\ldots$ will be dropped when unambiguously retrievable from the context.

Lemma 2.

In a $\delta^{\ast}$ -category, coinjections are jointly monic.

Proof.

See §A.1. $\hfill\blacktriangleleft$

By the above lemma, for every arrows $f_{1}:B\to A_{1}$ , $f_{2}:B\to A_{2}$ of a $\delta^{\ast}$ -category, there is at most one arrow $\langle f_{1},f_{2}\rangle:B\to A_{1}\oplus A_{2}$ , which we call pairing, such that $\iota^{\ast}_{i}\langle f_{1},f_{2}\rangle=f_{i}$ . Some pairings automatically exist. For instance, by (1), $\iota_{1}:A_{1}\to A_{1}\oplus A_{2}$ is the pairing $\langle\mathrm{id}_{A_{1}},0_{A_{1},A_{2}}\rangle$ and dually for $\iota_{2}$ . The pairing $\langle 0_{B,A_{1}},0_{B,A_{2}}\rangle$ is simply $0_{B,A_{1}\oplus A_{2}}$ . More subtly, the inverse $\chi^{-1}_{A,B_{1},B_{2}}$ of the distributivity isomorphism is the pairing $\langle\mathrm{id}_{A}\otimes\iota^{*}_{1},\mathrm{id}_{A}\otimes\iota^{*}_{2}\rangle$ , which can be deduced using the fact that injections into a coproduct are jointly epic.

Definition 3.

An ultraring is a small $\delta^{\ast}$ -category such that:

1.

disjoint pairings: for every $f:C\to A$ and $g:C\to B$ , if $(f\otimes g)\delta=0$ then their pairing $\langle f,g\rangle$ exists;
2.

complements: for every $p:A\to I$ such that $(p\otimes p)\delta=p$ , there exist a unique $\overline{p}:A\to I$ such that $(p\otimes\overline{p})\delta=0$ and $\nabla\langle p,\overline{p}\rangle=\varepsilon$ , where $\nabla:I\oplus I\to I$ is the codiagonal.

A morphism of ultrarings is just a morphism of $\delta^{\ast}$ -categories. We denote by $\mathbf{URing}$ the strict $2$ -category whose objects are ultrarings, whose arrows are morphisms between them and whose $2$ -cells are monoidal natural transformations.

2.2 Examples of Ultrarings

Let $R$ be a commutative ring. We denote by $\mathcal{U}R$ the category of free $R$ -modules of finite rank, and linear maps between them. This may be equivalently described as the category whose objects are natural numbers and whose arrows $n\to m$ are $m\times n$ matrices ( $m$ rows, $n$ columns) with coefficients in $R$ , and where composition is matrix multiplication.

This category is distributive monoidal: the (strict) monoidal structure is given by multiplication of natural numbers for objects and by the standard tensor product of matrices (also known as Kronecker product) for morphisms. Coproduct is addition and $0$ is easily seen to be a zero object. The Frobenius sesquimonoid structure is as follows: $\delta_{n}$ is the $n^{2}\times n$ matrix whose $i$ -th column has the element $1$ at position $n(i-1)+i$ and is zero everywhere else; $\varepsilon_{n}$ is the row matrix $(1\ldots 1)$ ; and $\delta^{\ast}_{n}$ is the transpose of $\delta_{n}$ .

Under matrix addition, $\mathcal{U}R$ is actually an additive category, which means it has biproducts, so point (1) of Definition 3 is immediate. For what concerns point (2), any $p:n\to 1$ is a row matrix $(p_{1}\ldots p_{n})$ , and the condition $(p\otimes p)\delta=p$ amounts to $p_{i}^{2}=p_{i}$ for all $i$ . It is then a matter of elementary calculations to show that $\overline{p}:=(1-p_{1}\ldots 1-p_{n})$ is the unique morphism $n\to 1$ verifying $(p\otimes\overline{p})\delta=0$ and $\nabla\langle p,\overline{p}\rangle=\varepsilon$ . So $\mathcal{U}R$ is an ultraring.

A ring homomorphism $h:R\to S$ induces a morphism of ultrarings $\mathcal{U}h:\mathcal{U}R\to\mathcal{U}S$ by applying $h$ pointwise to matrices. It is well known (see for instance [7]) that every symmetric monoidal, finite-coproduct-preserving functor $\mathcal{U}R\to\mathcal{U}S$ is monoidally isomorphic to a functor of the form $\mathcal{U}h$ for some $h:R\to S$ . Therefore, if we consider the category of commutative rings $\mathbf{CRing}$ to be a $2$ -category in which every hom-category is discrete, this defines a $2$ -functor $\mathcal{U}:\mathbf{CRing}\to\mathbf{URing}$ , and we have:

Proposition 4.

$\mathcal{U}:\mathbf{CRing}\hookrightarrow\mathbf{URing}$ is fully faithful.

Let $\mathbf{Fin}_{\ast}$ be the category of finite sets and partial functions. Observe that the cartesian product induces a symmetric monoidal structure on $\mathbf{Fin}_{\ast}$ (which is not a categorical product), whose unit is the singleton set $\{\ast\}$ , and that $\mathbf{Fin}_{\ast}$ is obviously distributive (coproducts are disjoint unions) and has a zero object (the empty set). A Frobenius sesquimonoid structure may be defined by letting $\delta_{A}:A\to A\times A$ be the diagonal, $\varepsilon_{A}:A\to\{\ast\}$ be the unique total function and $\delta^{\ast}_{A}:A\times A\to A$ be the function which is defined on $(a,a^{\prime})$ exactly when $a=a^{\prime}$ .

We invite the reader to check that, if $f:C\to A$ and $g:C\to B$ are partial functions, the condition $(f\otimes g)\delta=0$ amounts to the domains of $f$ and $g$ being disjoint. In that case, the pairing $\langle f,g\rangle:C\to A\oplus B$ is the evident partial function whose domain is the union of the domains of $f$ and $g$ . Furthermore, observe that any partial function $p:A\to\{\ast\}$ satisfies $(p\otimes p)\delta=p$ , and corresponds to a subset $P\subseteq A$ . The partial function $\overline{p}:A\to\{\ast\}$ corresponding to the complement of $P$ is easily seen to be the unique one verifying the desired properties of point (2) of Definition 3.

The above shows that $\mathbf{Fin}_{\ast}$ has the structure of an ultraring, except that it is not small. This is easily fixed: let $\mathbb{F}_{1}$ be the category whose objects are natural numbers and whose arrows $n\to m$ are partial functions $\{1,\ldots,n\}\to\{1,\ldots,m\}$ , or equivalently, $m\times n$ matrices with coefficients in $\{0,1\}$ such that $1$ appears at most once in each column. As a skeleton of $\mathbf{Fin}_{\ast}$ , $\mathbb{F}_{1}$ is an ultraring. In fact, it is the initial ultraring: since $\mathbb{F}_{1}$ is generated under finite coproducts by the monoidal unit $1$ and its identity arrow, any finite-coproduct-preserving functor $F:\mathbb{F}_{1}\to\mathcal{R}$ with $\mathcal{R}$ an ultraring is determined by the image of $1$ ; since morphisms of ultrarings are monoidal, $F1\cong I$ and $\mathbf{URing}(\mathbb{F}_{1},\mathcal{R})$ is equivalent to the terminal category.

Observe that $\mathbf{Fin}_{\ast}$ is the Kleisli category of the partiality monad $-+\{\ast\}$ over the category $\mathbf{Fin}$ of finite sets and total functions. This is a special case of a more general situation. A category is lextensive if it has finite limits and disjoint, pullback-stable finite coproducts. A lextensive category is called Boolean if every subobject has a complement; see [8]. A primordial example is $\mathbf{Fin}$ . In fact, for what concerns finite limits and finite coproducts, the objects of Boolean lextensive categories may be thought of as sets and their arrows as total functions. In particular, if $\mathcal{B}$ is a Boolean lextensive category whose terminal object is $1$ , the endofunctor $-+1$ is a monad and the Kleisli category $\mathcal{B}_{\ast}$ may again be seen as a category of “sets and partial functions”. The Kleisli categories of the partiality monad on small Boolean lextensive categories may be characterized as certain ultrarings, which we introduce below.

Definition 5.

An ultraring is Boolean if every arrow $f$ satisfies $\delta f=(f\otimes f)\delta$ and if for every $p:A\to I$ there exists a unique coproduct diagram $(\iota_{p},\overline{\iota}_{p})$ over $A$ such that $p=\varepsilon\iota_{p}^{\ast}$ , $\overline{\iota}_{p}=\iota_{\overline{p}}$ and, for every arrow $f$ , $\iota_{\varepsilon f}=(\mathrm{id}\otimes\varepsilon)\iota_{\varepsilon\delta^% {\ast}(f\otimes\mathrm{id})}$ .

In the following, we denote by $\mathbf{BoolURing}$ the full sub- $2$ -category of $\mathbf{URing}$ on Boolean ultrarings, and by $\mathbf{BoolLext}$ the $2$ -category of small Boolean lextensive categories, finitely continuous functors which preserve finite coproducts, and natural transformations.

Proposition 6.

The categories $\mathbf{BoolURing}$ and $\mathbf{BoolLext}$ are equivalent.

Proof.

We omit this proof due to space constraints. $\hfill\blacktriangleleft$

3 Annular Theories and Models

3.1 Presentations of Ultrarings

Having introduced the motivating examples of ultrarings, we now wish to provide presentations of these objects, which will subsequently enable us to perform essential constructions on them, as well as providing the basis for a syntax having a natural semantics in ultrarings.

Definition 7.

A signature $\mathfrak{S}$ is a pair $(\mathrm{Sort}(\mathfrak{S}),\mathrm{Gen}(\mathfrak{S}))$ such that:

$\blacksquare$

$\mathrm{Sort}(\mathfrak{S})$ is a set of sorts. A tensor of arity $n$ is a sequence of $n$ sorts $A_{1}\otimes\cdots\otimes A_{n}$ . The unique tensor of arity $0$ is denoted by $I$ .
$\blacksquare$

$\mathrm{Gen}(\mathfrak{S})$ is a set of generators, each with a type $g:T\to\bigoplus_{j=1}^{k}U_{j}$ where $T,U_{j}$ are tensors.

We fix a countably infinite set of variables, ranged over by $x, y, z$ … and we use $\vec{x},\vec{y}$ ,…to denote finite sequences of variables. Given a signature $\mathfrak{S}$ , the monomials over $\mathfrak{S}$ are defined as follows:

p,q::=(x=_{A}y)\mathrel{|}(g^{j}(\vec{x})=\vec{y})\mathrel{|}1\mathrel{|}% \overline{p}\mathrel{|}pq\mathrel{|}{\smallint\!}_{x}p,

where $A$ ranges over $\mathrm{Sort}(\mathfrak{S})$ , $g:T\to\bigoplus_{j=1}^{k}U_{j}$ ranges over $\mathrm{Gen}(\mathfrak{S})$ , $1\leq j\leq k$ and the length of $\vec{x}$ and $\vec{y}$ matches that of $T$ and $U_{j}$ , respectively. We write $g^{j}(\vec{x})$ , $(g^{j}=\vec{y})$ and $g^{j}$ rather than $(g^{j}(\vec{x})=)$ , $(g^{j}()=\vec{y})$ and $(g^{j}()=)$ , respectively. We abbreviate $(x_{1}=_{A_{1}}y_{1})\cdots(x_{n}=_{A_{n}}y_{n})$ to $(\vec{x}=_{\vec{A}}\vec{y})$ . The notation ${\smallint\!}_{x}a$ is a binder: $x$ is bound in $a$ and is subject to the usual renaming conventions. If $\vec{x}=x_{1},\ldots,x_{n}$ , we write ${\smallint\!}_{\vec{x}}a$ for ${\smallint\!}_{x_{1}}\cdots{\smallint\!}_{x_{n}}a$ . When $\vec{x}$ is empty, ${\smallint\!}_{\vec{x}}a$ is just $a$ . We call a monomial positive if it contains no instances of the negation operator $\overline{p}$ .

Monomials generalize logical formulas. Intuitively, in the Boolean case, the monomials $1$ , $\overline{p}$ , $p q$ and ${\smallint\!}_{x}p$ could be written $\top$ , $\lnot p$ , $p\land q$ , $\exists x.p$ , and the monomial $(g^{j}(\vec{x})=\vec{y})$ corresponds to a relation symbol $g^{j}(\vec{x},\vec{y})$ satisfying that $g^{j}(\vec{x},\vec{y})\land g^{j}(\vec{x},\vec{z})$ implies $\vec{y}=\vec{z}$ , i.e., a functional relation. The equality monomial $(x=_{A}y)$ is already a standard Boolean formula.

A pre-polynomial is a formal finite sum of monomials, with $0$ representing the empty sum. We can extend the operations of multiplication and integration in the definition of monomials (the last two operations) to pre-polynomials by assuming distributivity and linearity, respectively.

A context is a finite list of type assignments of the form $x : A$ where $x$ is a variable and $A$ a sort, such that no variable appears twice. If $\vec{x}=x_{1},\ldots,x_{n}$ is repetition-free and $T=\bigotimes_{i=1}^{n}A_{i}$ , we also write the context $x_{1}:A_{1},\ldots,x_{n}:A_{n}$ as $\vec{x}:T$ . In particular, in $\vec{x}:I$ the sequence $\vec{x}$ is empty. If $\Gamma$ and $\Delta$ are contexts, $\Gamma,\Delta$ denotes their concatenation (the variables appearing in each are assumed disjoint).

Figure 1: Monomials in context. We omit a rule allowing to permute type assignments in contexts.

A monomial-in-context is an expression of the form $\Gamma\vdash p::\Delta$ , where $p$ is a monomial and $\Gamma$ and $\Delta$ are contexts, which is derivable by means of the inductive rules of Fig. 1. If $\Gamma\vdash p::\Delta$ is derivable, we say that $p$ is well-typed, that $\Gamma$ is a domain for $p$ and that the context $\Gamma,\Delta$ matches $p$ . Note that, thanks to the penultimate rule of Fig. 1, any context matching $p$ is also a domain for it. Pre-polynomials-in-context are defined similarly, adding a rule to derive $\Gamma\vdash\sum_{i\in I}p_{i}::\Delta$ whenever $\Gamma\vdash p_{i}::\Delta$ is derivable for all $i\in I$ (in particular, $\Gamma\vdash 0::\Delta$ is derivable for any $\Gamma,\Delta$ ). From now on, we will only consider well-typed monomials and pre-polynomials.

$\displaystyle{\smallint\!}_{x}{\smallint\!}_{y}p$	$\displaystyle\approx_{\Gamma}{\smallint\!}_{y}{\smallint\!}_{x}p$	$\displaystyle{\smallint\!}_{y}(x=y)$	$\displaystyle\approx_{\Gamma,x:A}1$
$\displaystyle(x=_{A}y)p$	$\displaystyle\approx_{\Gamma,x:A,y:A}(x=_{A}y)p[x/y]$	$\displaystyle(x=_{A}x)$	$\displaystyle\approx_{\Gamma,x:A}1$
$\displaystyle(x=_{A}y)$	$\displaystyle\approx_{\Gamma,x:A,y:A}(y=_{A}x)$	$\displaystyle p+\overline{p}$	$\displaystyle\approx_{\Gamma}1$
$\displaystyle{\smallint\!}_{x}pq$	$\displaystyle\approx_{\Gamma}p{\smallint\!}_{x}q\quad\text{if $x$ is not free % in $p$}$

Figure 2: Basic equations for congruences on pre-polynomials.

p[x/y]

denotes usual substitution.

A congruence is a context-indexed family of equivalence relations $\approx\ :=(\approx_{\Gamma})_{\Gamma}$ on pre-polynomials matching $\Gamma$ , closed under associativity and commutativity of multiplication $p q$ , neutrality of $1$ , every equation of Fig. 2 and such that:

$\blacksquare$

$p\approx_{\Gamma}q$ implies $\overline{p}\approx_{\Gamma}\overline{q}$ , $pr\approx_{\Gamma}qr$ for all $r$ matching $\Gamma$ and $p\approx_{\Gamma^{\prime}}q$ for every context $\Gamma^{\prime}$ including the assignments of $\Gamma$ , possibly in a different order;
$\blacksquare$

$p\approx_{\Gamma,x:A}q$ implies ${\smallint\!}_{x}p\approx_{\Gamma}{\smallint\!}_{x}q$ ;
$\blacksquare$

$p\approx_{\Gamma}q$ iff $p+r\approx_{\Gamma}q+r$ for any $r$ matching $\Gamma$ (we call this cancellativity).

Given a set $S$ of equations of the form $p\approx_{\Gamma}q$ where $p, q$ are pre-polynomials matching $\Gamma$ , the congruence generated by $S$ is the smallest congruence containing the equations of $S$ .

In the sequel, if $\approx$ is a congruence and we write $p\approx q$ , we mean $p\approx_{\Gamma}q$ for every $\Gamma$ matching both $p, q$ .

Lemma 8.

For any congruence $\approx$ and any pre-polynomial $p$ , $p^{2}\approx p$ iff $p\overline{p}\approx 0$ . Moreover, either condition implies $\overline{p}^{2}\approx\overline{p}$ .

Proof.

See §A.1. $\hfill\blacktriangleleft$

Figure 3: Compatibility of pre-polynomials. The side condition

(*)

is:

\Gamma,\vec{y}:U,\vec{z}:V

(for some

U, V

) are domains for

r, s, t

, respectively, and

\vec{x}

are the outputs of

r

.

Given a congruence $\approx$ over a signature $\mathfrak{S}$ , we define $\approx$ -compatibility to be the context-indexed family of smallest symmetric relations $\frown_{\Gamma}$ on monomials of $\mathfrak{S}$ closed under the rules of Fig. 3 such that $p\frown_{\Gamma}q$ implies that $\Gamma$ is a domain for both $p$ and $q$ . We write $p\frown q$ to mean $p\frown_{\Gamma}q$ for every $\Gamma$ which is a domain for both $p$ and $q$ .

A $\approx$ -polynomial (or simply polynomial when this is unambiguous) is a pre-polynomial $p$ such that there exists $\Gamma$ such that $q\frown_{\Gamma}r$ for all monomials $q, r$ of $p$ and such that, whenever the expression $\overline{q}$ appears in $p$ , we have $q^{2}\approx q$ .

Definition 9.

An annular theory $\mathfrak{T}$ (which we abbreviate to theory in the remainder) is a triple $(\mathrm{Sort}(\mathfrak{T}),\mathrm{Gen}(\mathfrak{T}),\mathrm{Eq}(\mathfrak{% T}))$ where $(\mathrm{Sort}(\mathfrak{T}),\mathrm{Gen}(\mathfrak{T}))$ is a signature and $\mathrm{Eq}(\mathfrak{T})$ is a well-founded set of equations of the form $p\approx_{\Gamma}q$ where $p, q$ are pre-polynomials matching $\Gamma$ , such that, calling such an equation $e$ , we have that $p$ and $q$ are $\approx$ -polynomials with $\approx$ the congruence generated by the equations of $\mathrm{Eq}(\mathfrak{T})$ strictly below $e$ in the order. We denote by $\approx^{\mathfrak{T}}$ the congruence generated by $\mathrm{Eq}(\mathfrak{T})$ .

Definition 10.

A $\approx$ -matrix (or simply matrix) of type $\bigoplus_{k\in K}\vec{x}^{k}:T_{k}\to\bigoplus_{j\in J}\vec{y}^{j}:U_{j}$ consists of a $(J\times K)$ -indexed family of $\approx$ -polynomials-in-context $\left(\vec{x}^{k}:T_{k}\vdash p_{jk}::\vec{y}^{j}:U_{j}\right)_{(j,k)\in J% \times K}$ which we abbreviate to $(p_{jk})$ , such that,

\text{for every $j\neq j^{\prime}\in J$, $k\in K$, and monomials $r$ in $p_{jk% }$ and $r^{\prime}$ in $p_{j^{\prime}k}$, $r\frown_{\vec{x}^{k}:T_{k}}r^{% \prime}$.}\hfill({\dagger})

We always identify $\approx$ -matrices whose entries are equal modulo $\approx$ .

Lemma 11.

Let $(p_{jk})$ and $(q_{hj})$ be $\approx$ -matrices of type $\bigoplus_{k\in K}\vec{x}^{k}:T_{k}\to\bigoplus_{j\in J}\vec{y}^{j}:U_{j}$ and $\bigoplus_{j\in J}\vec{y}^{j}:U_{j}\to\bigoplus_{h\in H}\vec{z}^{h}:V_{h}$ , respectively. Then, the family of pre-polynomials-in-context indexed by $H\times J$ defined by

(q\circ p)_{hk}:=\left(\vec{x}^{k}:T_{k}\vdash\sum_{j\in J}{\smallint\!}_{\vec% {y}^{j}}q_{hj}p_{jk}::\vec{z}^{h}:V_{h}\right)_{(h,k)\in H\times K}

is a $\approx$ -matrix of type $\bigoplus_{k\in K}\vec{x}^{k}:T_{k}\to\bigoplus_{h\in H}\vec{z}^{h}:V_{h}$ .

Proof.

See §A.1. $\hfill\blacktriangleleft$

Let $\mathfrak{T}$ be a theory. We define a category $\mathbb{F}_{1}[\mathfrak{T}]$ as follows:

$\blacksquare$

the objects are formal finite coproducts $\bigoplus_{j\in J}\vec{x}^{j}:T_{j}$ of contexts of $\mathfrak{T}$ , modulo injective renaming of variables.
$\blacksquare$

If $A:=\bigoplus_{k\in K}\vec{x}^{k}:T_{k}$ and $B:=\bigoplus_{j\in J}\vec{y}^{j}:U_{j}$ , $\mathbb{F}_{1}[\mathfrak{T}](A,B)$ is the set of $\approx^{\mathfrak{T}}$ -matrices of type $A\to B$ .
$\blacksquare$

Composition is given by Lemma 11, and $\mathrm{id}_{A}$ is the diagonal matrix indexed by $K\times K$ which, at position $(k,k)$ , is equal to $(\vec{x}^{k}=_{T_{k}}\vec{z}^{k})$ , where we used the fact that, since objects are defined up to variable renaming, by renaming each $x^{k}_{h}$ to $z^{k}_{h}$ , we may write $A$ as $\bigoplus_{k\in K}\vec{z}^{k}:T_{k}$ .

As defined, $\mathbb{F}_{1}[\mathfrak{T}]$ is not small, because the finite sets indexing the objects are arbitrary. This may be circumvented by restricting to finite subsets of a fixed, countably infinite set of indices. We leave this implicit for notational convenience, but treat $\mathbb{F}_{1}[\mathfrak{T}]$ as a small category.

Proposition 12.

$\mathbb{F}_{1}[\mathfrak{T}]$ is an ultraring.

Proof.

We spell out the required structures and properties, without entering into the details. Here “polynomial”, “matrix”, etc. mean $\approx^{\mathfrak{T}}$ -polynomial, $\approx^{\mathfrak{T}}$ -matrix, etc.

Let $A:=\bigoplus_{j\in J}\vec{x}^{j}.T_{j}$ and $B:=\bigoplus_{k\in K}\vec{y}^{k}.U_{k}$ be generic objects of $\mathbb{F}_{1}[\mathfrak{T}]$ . The (strict) symmetric monoidal structure of $\mathbb{F}_{1}[\mathfrak{T}]$ is given by $A\otimes B:=\bigoplus_{(j,k)\in J\times K}\vec{x}^{j}\vec{y}^{k}.T_{j}\otimes U% _{k}$ on objects, with $I$ as unit. On morphisms, tensor is matrix product, valid by a similar argument to the proof of Lemma 11, but without the integrals. The empty sum $0$ is a zero object, the all-zero matrix of suitable size is the zero morphism between any two objects. The coproduct of $A$ and $B$ (where we may suppose $J\cap K=\emptyset$ and $\vec{x}^{j},\vec{y}^{k}$ to be disjoint) is given by $\bigoplus_{l\in J\cup K}\vec{z}^{l}.V_{l}$ , where $\vec{z}^{l}$ and $V_{l}$ are equal to $\vec{x}^{j}$ and $T_{j}$ (resp. $\vec{y}^{k}$ and $U_{k}$ ) if $l\in J$ (resp. $l\in K$ ). This obviously satisfies strict distributivity. The injections $\iota_{1},\iota_{2}$ are the block column matrices $\left(\begin{array}[]{c}\mathrm{id}\\ 0\end{array}\right)$ and $\left(\begin{array}[]{c}0\\ \mathrm{id}\end{array}\right)$ , respectively, whereas the copairing of two matrices $P, Q$ is the block row matrix $(P\ Q)$ .

For what concerns the Frobenius sesquimonoid structure, $\delta_{A}$ is the matrix indexed over $J^{2}\times J$ whose column for $j\in J$ has the element $(\vec{x}^{j}=\vec{y}^{j})(\vec{x}^{j}=\vec{z}^{j})$ at position $(j,j)$ and is zero everywhere else, where we are renaming variables so that $A\otimes A=\bigoplus_{j,j^{\prime}\in J}\vec{y}^{j}\vec{z}^{j^{\prime}}.T_{j}% \otimes T_{j^{\prime}}$ . $\varepsilon_{A}$ is the row matrix which is equal to the monomial $1$ everywhere. $\delta^{\ast}_{A}$ is the transpose of $\delta_{A}$ .

Thanks to the above definition, elementary calculations show that, if $P=(p_{kj})_{j\in J,k\in K}$ and $Q=(q_{lj})_{j\in J,l\in L}$ are matrices corresponding to morphisms $A\to B$ and $A\to C$ for some other object $C$ (indexed by $L$ , which we may supposed to be disjoint from $K$ even if $C=B$ ), then $(P\otimes Q)\delta_{A}\approx^{\mathfrak{T}}0$ is equivalent to asking that, for all $j\in J$ , $k\in K$ and $l\in L$ , we have $p_{kj}q_{lj}\approx^{\mathfrak{T}}0$ , which implies $p_{kj}\frown q_{lj}$ , so we may form the block column matrix $R:=\left(\begin{array}[]{c}P\\ Q\end{array}\right)$ (with $K\cup L$ rows and $J$ columns). The reader may check that the coinjections are the block row matrices $(\mathrm{id}\ 0)$ and $(0\ \mathrm{id})$ , so $R$ is the (unique) pairing of $P, Q$ , as desired.

Let now $P=(p_{k})_{k\in K}$ be a matrix of type $A\to I$ . This means that $P$ is a row matrix, and elementary calculations show that $(P\otimes P)\delta\approx^{\mathfrak{T}}P$ is equivalent to asking that $p_{k}^{2}\approx^{\mathfrak{T}}p_{k}$ for all $k\in K$ , so we are allowed to consider the polynomials $\overline{p_{k}}$ and define $\overline{P}:=(\overline{p_{k}})_{k\in K}$ . We need to show that $(P\otimes\overline{P})\delta\approx^{\mathfrak{T}}0$ . By similar calculations as above, this is equivalent to $p_{k}\overline{p_{k}}\approx^{\mathfrak{T}}0$ for all $k\in K$ , which holds by Lemma 8. We are left with proving that $\nabla\langle P,\overline{P}\rangle\approx^{\mathfrak{T}}\varepsilon$ . Notice that, in general, $\nabla\langle Q,R\rangle=Q+R$ as matrices. This sum exists because, as shown above, $\langle Q,R\rangle$ is the block column matrix $\left(\begin{array}[]{c}Q\\ R\end{array}\right)$ . So we need to show that $p_{k}+\overline{p_{k}}\approx^{\mathfrak{T}}1$ for all $k\in K$ , but this is one of the equations of Fig. 2. $\hfill\blacktriangleleft$

3.2 Models and the Canonical Theory

The term “annular theory” in Definition 9 is not merely an analogy with logic: it is chosen so that ultraring morphisms out of $\mathbb{F}_{1}[\mathfrak{T}]$ become models of $\mathfrak{T}$ , in a sense that we now establish.

Definition 13.

Given a signature $\mathfrak{S}$ and an ultraring $\mathcal{A}$ , an $\mathfrak{S}$ -structure in $\mathcal{A}$ consists of:

$\blacksquare$

An assignment $M_{0}:\mathrm{Sort}(\mathfrak{S})\to\mathrm{ob}(\mathcal{A})$ . This extends to an assignment on tensors given by $M_{0}(\bigotimes_{i}A_{i}):=\bigotimes_{i}M_{0}(A_{i})$ .
$\blacksquare$

An assignment $M_{1}:\mathrm{Gen}(\mathfrak{S})\to\mathrm{mor}(\mathcal{A})$ such that if $g:T\to U$ then $M_{1}(g):M_{0}(T)\to M_{0}(U)$ .

For $\mathfrak{S}$ -structures $M,M^{\prime}$ in $\mathcal{A}$ , a homomorphism $m:M\to M^{\prime}$ consists of a collection of morphisms $m_{X}:M_{0}(X)\to M^{\prime}_{0}(X)$ in $\mathcal{A}$ indexed by $X\in\mathrm{Sort}(\mathfrak{S})$ such that for each $g:\bigotimes_{i}A_{i}\to\bigotimes_{j}B_{j}\in\mathrm{Gen}(\mathfrak{S})$ , $M_{1}(g);\bigotimes_{j}m_{B_{j}}=\bigotimes_{i}m_{A_{i}};M^{\prime}_{1}(g)$ .

Given a theory $\mathfrak{T}$ over a signature $\mathfrak{S}$ and a $\mathfrak{S}$ -structure $M$ , we can define an interpretation over $M$ of any $\approx^{\mathfrak{T}}$ -polynomial-in-context, as detailed in §A.2. The notion of model is then defined in the expected way:

Definition 14.

Let $\mathfrak{T}$ be a theory over signature $\mathfrak{S}$ and $\mathcal{A}$ an ultraring. A model of $\mathfrak{T}$ in $\mathcal{A}$ is a $\mathfrak{S}$ -structure $M$ in $\mathcal{A}$ such that for each equation $p\approx_{\Gamma,\Delta}q$ of $\mathfrak{T}$ , we have $M(\Gamma\vdash p::\Delta)=M(\Gamma\vdash q::\Delta)$ .

For models $M,M^{\prime}$ of $\mathfrak{T}$ in $\mathcal{A}$ , a homomorphism $M\to M^{\prime}$ is simply a homomorphism of $\mathfrak{S}$ -structures. We denote by $\mathfrak{T}\text{-}\mathrm{Mod}(\mathcal{A})$ the category of models of $\mathfrak{T}$ in $\mathcal{A}$ and homomorphisms between them.

Proposition 15.

Let $\mathfrak{T}$ be a theory. There is an $\mathcal{A}$ -natural equivalence of categories $\mathfrak{T}\text{-}\mathrm{Mod}(\mathcal{A})\simeq\mathbf{URing}(\mathbb{F}_{% 1}[\mathfrak{T}],\mathcal{A}).$

Proof.

See §A.2. $\hfill\blacktriangleleft$

Proposition 15 implies in particular the existence of a generic model of any annular theory $\mathfrak{T}$ , corresponding to the identity functor on $\mathbb{F}_{1}[\mathfrak{T}]$ , of which a model in any ultraring is an image by naturality.

If Proposition 12 shows us that we can generate ultrarings from theories, it may not be a surprise that every ultraring arises in this way up to equivalence.

Definition 16.

We define the canonical theory of an ultraring $\mathcal{R}$ to be the theory $\mathfrak{T}$ where:

$\blacksquare$

$\mathrm{Sort}(\mathfrak{T})=\mathrm{ob}(\mathcal{R})$ , where we denote the sort corresponding to $A$ by $\ulcorner A\urcorner$ ;
$\blacksquare$

$\mathrm{Gen}(\mathfrak{T})$ has a generator $\ulcorner g\urcorner:\bigotimes_{j\in J}\ulcorner A_{j}\urcorner\to\bigoplus_{% k\in K}\bigotimes_{l\in L_{k}}\ulcorner B_{k,l}\urcorner$ for each morphism $g:\bigotimes_{j\in J}A_{j}\to\bigoplus_{k\in K}\bigotimes_{l\in L_{k}}B_{k,l}$ in $\mathcal{R}$ ,³³3This is a mild abuse of notation, since the name $\ulcorner g\urcorner$ can refer to multiple generators depending on how the domain and codomain are decomposed. When not specified, the type will be the one with the minimal decomposition.
$\blacksquare$
$\mathrm{Eq}(\mathfrak{T})$ consists of equations:
- –
  
  $\left(\ulcorner\mathrm{id}\urcorner(\vec{x})=\vec{y}\right)\approx(\vec{x}=% \vec{y})$ for $\ulcorner\mathrm{id}\urcorner:\bigotimes_{j\in J}\ulcorner A_{i}\urcorner\to% \bigotimes_{j\in J}\ulcorner A_{i}\urcorner$ ,
- –
  
  $\int_{\vec{y}}(\ulcorner f\urcorner(\vec{x})=\vec{y})(\ulcorner g\urcorner(% \vec{y})=\vec{z})\approx(\ulcorner gf\urcorner(\vec{x})=\vec{z})$ for composable $f, g$ in $\mathcal{R}$ (with no coproduct decomposition of the codomains).
- –
  
  $(\ulcorner\iota^{*}_{j}g\urcorner(\vec{x})=\vec{y})\approx(\ulcorner g% \urcorner^{j}(\vec{x})=\vec{y})$ .
- –
  
  $(\ulcorner f\otimes g\urcorner(\vec{x},\vec{u})=\vec{y},\vec{v})\approx(% \ulcorner f\urcorner(\vec{x})=\vec{y})(\ulcorner g\urcorner(\vec{u})=\vec{v})$ .
- –
  
  $(\ulcorner 0\urcorner(\vec{x})=\vec{y})\approx_{\vec{x}:T,\vec{y}:U,\Gamma}0$ , for any typing of $\ulcorner 0\urcorner$ .
- –
  
  $(\ulcorner\delta\urcorner(\vec{x})=\vec{x_{1}},\vec{x_{2}})\approx(\vec{x}=% \vec{x}_{1})(\vec{x}=\vec{x}_{2})$
- –
  
  $\ulcorner\varepsilon\urcorner(\vec{x})\approx_{\vec{x}:T,\Gamma}1$
- –
  
  $(\ulcorner\delta^{*}\urcorner(\vec{x_{1}},\vec{x_{2}})=\vec{x})\approx(\vec{x}% _{1}=\vec{x})(\vec{x}_{2}=\vec{x})$ .

Theorem 17.

Let $\mathcal{R}$ be an ultraring and $\mathfrak{T}$ its canonical theory, as defined in Definition 16. Then $\mathcal{R}\simeq\mathbb{F}_{1}[\mathfrak{T}]$ .

Proof.

See §A.2. $\hfill\blacktriangleleft$

3.3 Examples of Annular Theories

In what follows, we let $\mathbb{K}$ denote either $\mathbb{F}_{1}$ or the ultraring corresponding to a commutative ring $R$ with no non-trivial idempotent, i.e., in which $r^{2}=r$ implies $r\in\{0,1\}$ for all $r\in R$ . Examples include any field or, more generally, any integral domain such as $\mathbb{Z}$ .

We define a predicate of a theory $\mathfrak{T}$ to be a $\approx^{\mathfrak{T}}$ -polynomial $p:T\to I$ such that $p^{2}\approx_{\vec{x}:T}^{\mathfrak{T}}p$ . Observe that, if $M$ is a model of $\mathfrak{T}$ in $\mathbb{K}$ , then $M(p)$ must be a row vector of zeros and ones: the equation $p^{2}\approx_{\vec{x}:T}^{\mathfrak{T}}p$ becomes $(M(p)\otimes M(p))\delta_{T}=M(p)$ , and we already observed that this is equivalent to all entries of $M(p)$ being idempotent. Furthermore, $M(T)=I^{\oplus n}$ for some $n$ (all objects of $\mathbb{K}$ are of this form). If we see $M(T)$ as the set $\{1,\ldots,n\}$ , $M(p)$ may be identified with the subset of $M(T)$ of all $i$ such $M(p)_{i}=1$ , justifying the terminology.

Predicates are closed under Boolean logic: $0$ and $1$ are predicates; if $p$ and $q$ are predicates, then $p q$ and $\overline{p}$ are predicates (Lemma 8). Also, by the second row of Fig. 2, $(x=_{A}y)$ is always a predicate: $(x=_{A}y)^{2}\approx_{x:A,y:A}(x=_{A}y)(x=_{A}x)\approx_{x:A,y:A}(x=y)$ . Moreover, models in $\mathbb{K}$ are consistent with Boolean logic: if $M$ and $p$ are as above, $M(0)=\emptyset$ , $M(1)=M(T)$ , $M(pq)=M(p)\cap M(q)$ , $M(\overline{p})=M(T)\setminus M(p)$ and $M(\vec{x}=_{T}\vec{y})$ is the diagonal of $M(T)\times M(T)$ .

In the sequel, when we say that a generator $P$ is a predicate over $T$ , we mean that $P:T\to I$ and that the equation $P^{2}\approx_{\vec{x}:T}^{\mathfrak{T}}P$ is added to the theory. By the above, a monomial $\varphi$ consisting entirely of generators which are predicates is like a Boolean formula and, if $\vec{x}:T$ matches $\varphi$ , we may impose that $\forall\vec{x}.\varphi$ holds by adding the equation $\varphi\approx_{\vec{x}:T}1$ .

For example, we define the theory $\mathfrak{Ord}$ with one sort $N$ and one predicate $\leq$ over $N\otimes N$ with equations making $\leq$ is a total order. We write $(x\leq y)$ rather than $\mathop{\leq}(x,y)$ . A model of $\mathfrak{Ord}$ in $\mathbb{K}$ is precisely a finite total order; modulo iso, we may assume it to be of the form $[n]:=\{1<\cdots<n\}$ . The theory $\mathfrak{Str}$ is obtained from $\mathfrak{Ord}$ by adding a generator $X:N\to I$ with no further equations. A model $s$ of $\mathfrak{Str}$ in $\mathbb{K}$ is a finite total order indexing a row vector $s(X)$ of zeros and ones if $\mathbb{K}=\mathbb{F}_{1}$ , or of elements of $R$ otherwise. In other words, $s$ represents a binary string when $\mathbb{K}=\mathbb{F}_{1}$ , or a string of elements of $R$ otherwise. We denote the $i$ -th bit/element by $s(X)_{i}$ .

4 Computation

4.1 Computability over Ultrarings

Let $\mathbb{K}$ be as in §3.3. A $\mathbb{K}$ -string is a binary string if $\mathbb{K}=\mathbb{F}_{1}$ , or a string over elements of $R$ otherwise. A $\mathbb{K}$ -problem is a set of $\mathbb{K}$ -strings.

We define $\mathbb{K}$ -operations to be the following functions $R\times R\to R$ , where $R$ is $\{0,1\}$ if $\mathbb{K}=\mathbb{F}_{1}$ or the underlying ring of $\mathbb{K}$ otherwise: $\mathbb{F}_{1}$ -operations are conjunction, the constant function $1$ and the function negating the first bit and discarding the second; otherwise, $\mathbb{K}$ -operations are constant functions, addition and multiplication of $R$ and, in case $R$ is a field, also division (the value of a division by zero is chosen arbitrarily). We also define $\mathrm{Test}_{\mathbb{K}}\subseteq R$ to be the set of non-negative elements when $R$ is $\mathbb{Z}$ , $\mathbb{Q}$ or $\mathbb{R}$ , or $\{0\}$ otherwise.

Definition 18.

A $\mathbb{K}$ -RAM, where RAM stands for random access machine, is a (possibly empty) list $I_{0},\ldots,I_{m-1}$ of instructions, $m\in\mathbb{N}$ , chosen among: $\mathsf{comp}(\mathrm{op})$ where $\mathrm{op}$ is a $\mathbb{K}$ -operation (a computation); $\mathsf{zeror}$ , $\mathsf{zerow}$ , $\mathsf{incr}$ or $\mathsf{incw}$ (an update); $\mathsf{branch}(l)$ where $0\leq l\leq m+1$ ; and $\mathsf{copy}$ .

A configuration of the machine is a tuple $(i,s,r,w)$ where $0\leq i\leq m+1$ , $s$ is a $\mathbb{K}$ -string, whose $j$ -th element is denoted by $s_{j}$ and said to be the content of register $j$ , and $r,w\in\mathbb{N}$ . The initial configuration is $(0,s,0,0)$ , where $s$ is the input of the machine. On configuration $(i,s,r,w)$ , the machine acts as follows. If $0\leq i\leq m-1$ , then the next configuration $c$ is determined according to $I_{i}$ (the string $s$ is considered to be padded with infinitely many $0$ ’s on the right, so $s_{j}$ is defined for all $j\in\mathbb{N}$ ):

$\blacksquare$

$I_{i}=\mathsf{comp}(\mathrm{op})$ : $c$ is $(i+1,s^{\prime},r,w)$ , where $s^{\prime}_{0}=\mathrm{op}(s_{0},s_{1})$ , and $s^{\prime}_{j}=s_{j}$ for all $j>0$ ;
$\blacksquare$

$I_{i}=\mathsf{branch}(l)$ : $c$ is $(l,s,r,w)$ if $s_{0}\in\mathrm{Test}_{\mathbb{K}}$ or $(i+1,s,r,w)$ otherwise;
$\blacksquare$

$I_{i}=\mathsf{copy}$ : $c$ is $(i+1,s^{\prime},r,w)$ where $s^{\prime}_{w}=s_{r}$ and $s^{\prime}_{j}=s_{j}$ for all $j\neq w$ ;
$\blacksquare$

$I_{i}=\mathsf{zeror}$ , $\mathsf{zerow}$ , $\mathsf{incr}$ or $\mathsf{incw}$ : $c$ is $(i+1,s,0,w)$ , $(i+1,s,r,0)$ , $(i+1,s,r+1,w)$ or $(i+1,s,r,w+1)$ , respectively.

Otherwise, the machine accepts if $i=m$ and rejects if $i=m+1$ .

It is immediate to see that a $\mathbb{K}$ -RAM with $\mathbb{K}$ one of $\mathbb{Z}$ , $\mathbb{Q}$ or $\mathbb{R}$ is equivalent to a BSS machine [5] over those rings, modulo a polynomial slowdown (because computation steps of BSS machines are rational functions of arbitrary finite arity). On the other hand, an $\mathbb{F}_{1}$ -RAM is obviously equivalent to a deterministic Turing machine on the alphabet $\{0,1\}$ .

The notion of acceptance/decision of a $\mathbb{K}$ -problem by a $\mathbb{K}$ -RAM is as usual. A polytime $\mathbb{K}$ -RAM is a $\mathbb{K}$ -RAM which always terminates in polynomially many steps in the size of the input. We denote by $\mathsf{RE}_{\mathbb{K}}$ the class of $\mathbb{K}$ -problems accepted by a $\mathbb{K}$ -RAM, by $\mathsf{P}_{\mathbb{K}}$ the class of $\mathbb{K}$ -problems decided by a polytime $\mathbb{K}$ -RAM, and by $\mathsf{NP}_{\mathbb{K}}$ the class of $\mathbb{K}$ -problems which are projections over the first component of a $\mathbb{K}$ -problem in $\mathsf{P}_{\mathbb{K}}$ whose $\mathbb{K}$ -strings encode pairs $(s_{1},s_{2})$ such that the length of $s_{2}$ is polynomially bounded by the length of $s_{1}$ . By the above observations, $\mathsf{RE}_{\mathbb{F}_{1}}$ , $\mathsf{P}_{\mathbb{F}_{1}}$ and $\mathsf{NP}_{\mathbb{F}_{1}}$ are the usual classes $\mathsf{RE}$ , $\mathsf{P}$ and $\mathsf{NP}$ , whereas $\mathsf{RE}_{\mathbb{R}}$ , $\mathsf{P}_{\mathbb{R}}$ and $\mathsf{NP}_{\mathbb{R}}$ are the usual classes defined using the BSS model [5].

By contrast, $\mathsf{P}_{\mathbb{Z}}$ and $\mathsf{NP}_{\mathbb{Z}}$ do not coincide with the corresponding BSS classes. Indeed, BSS sort of “tweak” their definition of computability over $\mathbb{Z}$ in order to recover the usual, Boolean $\mathsf{P}$ and $\mathsf{NP}$ : they consider an integer to have size equal to its representation as a binary string. We do not need to do this, as we use $\mathbb{F}_{1}$ to capture Boolean computation.

4.2 Capturing Complexity Classes

Let $\mathcal{R}$ be an ultraring. We define an $\mathcal{R}$ -algebra to be an ultraring $\mathcal{A}$ equipped with a structure map $\mathcal{R}^{\prime}\to\mathcal{A}$ and an equivalence $\mathcal{R}^{\prime}\simeq\mathcal{R}$ . Typical examples are given by extensions of theories: if $\mathfrak{T}$ is defined by adding sorts and/or generators and/or equations to a theory $\mathfrak{S}$ , then there is an obvious inclusion functor $\mathbb{F}_{1}[\mathfrak{S}]\to\mathbb{F}_{1}[\mathfrak{T}]$ , mapping every object and morphism of $\mathbb{F}_{1}[\mathfrak{S}]$ to “itself”, making $\mathbb{F}_{1}[\mathfrak{T}]$ into an $\mathbb{F}_{1}[\mathfrak{S}]$ -algebra, with equality as equivalence. In general, if $\mathcal{R}$ is presented by $\mathfrak{S}$ with a chosen equivalence $e:\mathbb{F}_{1}[\mathfrak{S}]\simeq\mathcal{R}$ , and if $\mathfrak{T}$ extends $\mathfrak{S}$ , to make it clear that we are viewing $\mathbb{F}_{1}[\mathfrak{T}]$ as an $\mathcal{R}$ -algebra with inclusion as structure map and equivalence $e$ , we write $\mathcal{R}[\mathfrak{T}\setminus\mathfrak{S}]$ rather than $\mathbb{F}_{1}[\mathfrak{T}]$ .

For example, if $\mathbb{K}$ is as in §3.3, we may fix a presentation $\mathfrak{T}_{\mathbb{K}}$ of $\mathbb{K}$ and an equivalence $\mathbb{F}_{1}[\mathfrak{T}_{\mathbb{K}}]\simeq\mathbb{K}$ (taking $\mathfrak{T}_{\mathbb{F}_{1}}$ to be the empty theory), and add to $\mathfrak{T}_{\mathbb{K}}$ the sort, generators, and equations of $\mathfrak{Str}$ , obtaining a theory $\mathfrak{Str}_{\mathbb{K}}$ (so $\mathfrak{Str}_{\mathbb{F}_{1}}=\mathfrak{Str}$ ) and a $\mathbb{K}$ -algebra that we denote by $\mathbb{K}[\mathfrak{Str}]$ , which is equal to $\mathbb{F}_{1}[\mathfrak{Str}_{\mathbb{K}}]$ with structure map the inclusion of $\mathbb{F}_{1}[\mathfrak{T}_{\mathbb{K}}]\simeq\mathbb{K}$ .

Definition 19.

Let $\mathcal{A}$ be an $\mathbb{F}_{1}[\mathfrak{Str}]$ -algebra with structure map $f:\mathcal{S}\to\mathcal{A}$ and equivalence $e:\mathcal{S}\to\mathbb{F}_{1}[\mathfrak{Str}]$ . We say that $\mathcal{A}$ accepts a $\mathbb{K}$ -string $s$ if any morphism $\mathbb{F}_{1}[\mathfrak{Str}]\to\mathbb{K}$ corresponding to $s$ as a model of $\mathfrak{Str}$ in $\mathbb{K}$ (via Proposition 15) factors through $f$ , modulo isomorphism. That is, given a morphism $g:\mathbb{F}_{1}[\mathfrak{Str}]\to\mathbb{K}$ representing $s$ , there exists a morphism $h:\mathcal{A}\to\mathbb{K}$ and a monoidal natural isomorphism between $g\circ e$ and $h\circ f$ . We denote by $\Gamma_{\mathbb{K}}(\mathcal{A})$ the set of $\mathbb{K}$ -strings accepted by $\mathcal{A}$ .

Notice that the above definition does not depend on the choice of $g$ representing $s$ : if $h$ exists for some $g$ , then it exists for all $g^{\prime}$ representing $s$ , because in that case $g^{\prime}\cong g$ and therefore $g^{\prime}\circ e\cong g\circ e\cong h\circ f$ as well.

Also observe that, by initiality of $\mathbb{F}_{1}$ , every $\mathbb{K}[\mathfrak{Str}]$ -algebra is an $\mathbb{F}_{1}[\mathfrak{Str}]$ -algebra. Moreover, if $\mathbb{K}$ has no non-identity endomorphism (for instance, if $\mathbb{K}$ is $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{R}$ or $\mathbb{F}_{p}$ with $p$ prime or $1$ ), $\mathbb{K}$ -strings still correspond to morphisms $\mathbb{K}[\mathfrak{Str}]\to\mathbb{K}$ . In this case, the above definition may be equivalently formulated by speaking of $\mathbb{K}[\mathfrak{Str}]$ -algebras. Concretely, if $\mathcal{A}=\mathbb{K}[\mathfrak{T}]$ , a $\mathbb{K}$ -string $s$ , seen as a model of $\mathfrak{Str}$ in $\mathbb{K}$ , is in $\Gamma_{\mathbb{K}}(\mathcal{A})$ iff we may extend it to a model in $\mathbb{K}$ of $\mathfrak{Str}$ augmented with the extra sorts, generators and equations of $\mathfrak{T}$ . This is how the definition is applied in the statement of Theorem 22 below. The above definition is more general because, if $\mathbb{K}$ has non-trivial endomorphisms (for example $\mathbb{K}=\mathbb{C}$ ), a morphism $\mathbb{K}[\mathfrak{Str}]\to\mathbb{K}$ may not correspond to a $\mathbb{K}$ -string, but a morphism $\mathbb{F}_{1}[\mathfrak{Str}]\to\mathbb{K}$ always does.

We say that an $\mathcal{R}$ -algebra of the form $\mathcal{R}[\mathfrak{T}]$ is

$\blacksquare$

of finite presentation if $\mathfrak{T}$ is finite (finitely many sorts, generators and equations are added);
$\blacksquare$

plain if $\mathfrak{T}$ has no sorts (no sorts are added).

The latter terminology is justified by the fact that plain $\mathcal{R}$ -algebras are algebras in the usual sense when $\mathcal{R}$ is a commutative ring.

Let $T$ be a tensor of a theory $\mathfrak{T}$ . We say that is it a chain if there exist a predicate (as defined in §3.3) $\leq_{\mathfrak{T}}$ over $T\otimes T$ and $\approx^{\mathfrak{T}}$ -polynomials $\mathrm{Z}_{T},\mathrm{Max}_{T}:I\to T$ and $\mathrm{Succ}_{T}:T\to T$ such that, with respect to $\approx^{\mathfrak{T}}$ , $\leq_{T}$ is a total order, $\mathrm{Z}_{T}$ and $\mathrm{Max}_{T}$ are functions identifying the minimum and maximum element w.r.t. $\leq_{\mathfrak{T}}$ , and $\mathrm{Succ}_{T}$ is the successor function (every element has a unique successor and predecessor, except zero and max, which have no predecessor and successor, respectively). Notice that, if $T$ and $U$ are chains, the so is $T\otimes U$ via the lexicographic order (it is not hard to see that this is definable in annular theories). Whenever $p$ is a polynomial matching a context $\Gamma,\vec{t}:T$ , we will write $p(0)$ , $p(\mathrm{max})$ and $p(\vec{t}_{+1})$ to mean ${\smallint\!}_{\vec{t}}\mathrm{Z}_{T}(\vec{t})p(\vec{t})$ , ${\smallint\!}_{\vec{t}}\mathrm{Max}_{T}(\vec{t})p(\vec{t})$ and ${\smallint\!}_{\vec{t}^{\prime}}\mathrm{Succ}_{T}(\vec{t},\vec{t}^{\prime})p(% \vec{t}^{\prime})$ , respectively.

Definition 20.

Let $\mathcal{R}$ be an ultraring and $\mathcal{A}=\mathcal{R}[\mathfrak{T}]$ a plain $\mathcal{R}$ -algebra, whose underlying equivalence is $\mathbb{F}_{1}[\mathfrak{S}]\simeq\mathcal{R}$ . We say that $\mathcal{A}$ is inductive if there exists a tensor $T$ of $\mathfrak{S}$ which is a chain in $\mathfrak{T}$ such that every added generator $g\in\mathrm{Gen}(\mathfrak{T})$ is either making $T$ into a chain or has type $T\otimes U\to V$ for some $U$ and $V$ and belongs to one of the following classes:

$\blacksquare$
inductive generators: generators with equations of the form
- –
  
  initialization: $\sum_{i}\varphi_{i}g(0)\approx_{\Gamma}\sum_{i}\varphi_{i}c_{i}$ ,
- –
  
  induction: $\sum_{i}\psi_{i}(\vec{t})g(\vec{t}_{+1})\approx_{\Gamma,\vec{t}:T}\sum_{i}\psi% _{i}(\vec{t})f_{i}(\vec{t})$ ,
and, possibly, equations stating that $g$ is a predicate and/or final value equations of the form $\sum_{i}\varphi_{i}^{\prime}g(\mathrm{max})\approx_{\Gamma}\sum_{i}\varphi_{i}% ^{\prime}c_{i}^{\prime}$ , where $c_{i},c_{i}^{\prime},f_{i}$ are polynomials and $\varphi_{i},\varphi^{\prime}_{i},\psi_{i}$ are predicates such that, for all $i\neq j$ , $\varphi_{i}\varphi_{j}\approx_{\Gamma}^{\mathfrak{T}}0$ , $\varphi^{\prime}_{i}\varphi^{\prime}_{j}\approx_{\Gamma}^{\mathfrak{T}}0$ and $\psi_{i}\psi_{j}\approx_{\Gamma,\vec{t}:T}^{\mathfrak{T}}0$ ;
$\blacksquare$
harmless predicates and ancillary generators: predicates $P$ over $T$ coming with their ancillary generators $X^{P}_{1},\ldots,X^{P}_{k}:T\to I$ and their defining equations $Pp\approx_{\vec{t}:T}0$ and $\overline{P}q_{i}\approx_{\vec{t}:T}0$ for $1\leq i\leq k$ , where $p$ and $q_{i}$ are polynomials such that:
- –
  
  the degree of $p$ in the ancillary generators of $P$ is at most $2$ ;
- –
  
  no harmless predicate appears in $p$ or any $q_{i}$ ;
- –
  
  in any model $M$ of $\mathfrak{S}$ in $\mathbb{K}$ , the equation $M(p)=0$ has a solution in $\mathbb{K}$ (with respect to the ancillary generators) iff the system $(M(q_{i})=0)_{i=1}^{k}$ has no solution in $\mathbb{K}$ .
Moreover, the ancillary generators of $P$ do not appear in any equation of $\mathfrak{T}$ except the defining equations of $P$ .

Inductive algebras are inspired by fixed point operators in logic [16, 15]. Let $\mathbb{K}$ be an integral domain or $\mathbb{F}_{1}$ . The idea is that, given a model $M$ in $\mathbb{K}$ of the base theory $\mathfrak{S}$ (i.e., a morphism $f:\mathcal{R}\to\mathbb{K}$ ), finding whether $M$ may be extended to a model $M^{\prime}$ of $\mathfrak{S}$ plus the generators and equations of $\mathfrak{T}$ (i.e., whether $f$ factors via the inclusion $\mathcal{R}\to\mathcal{A}$ ) may be done inductively on $T$ , which is like a time parameter. Indeed, to build $M^{\prime}$ one must find an interpretation in $\mathbb{K}$ for the generators of $\mathfrak{T}$ . For an inductive generator, the initialization equation gives the value when $\vec{t}=0$ and, once the value at $\vec{t}$ is known, the induction equation gives the value for $\vec{t}_{+1}$ . For a harmless predicate $P$ with defining equations involving $p$ and $(q_{i})$ , one may know whether $P$ holds at time $\vec{t}$ by testing whether $p=0$ has a solution in $\mathbb{K}$ . This may be done efficiently (at least for certain $\mathbb{K}$ of interest, such as $\mathbb{R}$ and $\mathbb{F}_{1}$ ) because $p$ has degree at most two (it involves something like computing a discriminant, or solving a 2-CNF). The definition guarantees that, if $p=0$ has a solution, then one of the $q_{i}=0$ does not, therefore $\overline{P}(\vec{t})=0$ (because $\mathbb{K}$ has no zero divisor) hence $P$ is true at time $\vec{t}$ . Otherwise, if $p=0$ has no solution, then $P$ must be false at time $\vec{t}$ .

The following results hold more generally than stated (for example, they also hold for $\mathbb{Q}$ , $\mathbb{Z}$ and $\mathbb{F}_{p}$ with $p$ prime), but for succinctness we prove them only for $\mathbb{F}_{1}$ and $\mathbb{R}$ .

Lemma 21.

Let $\mathbb{K}$ be $\mathbb{F}_{1}$ or $\mathbb{R}$ . For any polytime $\mathbb{K}$ -RAM $M$ there exists a finite extension $\mathfrak{X}$ of $\mathfrak{Str}$ such that:

$\blacksquare$

$\mathbb{K}[\mathfrak{X}]$ is an inductive $\mathbb{K}[\mathfrak{Str}]$ -algebra of finite presentation;
$\blacksquare$

a model of $\mathfrak{X}$ in $\mathbb{K}$ is an accepting run of $M$ , and its restriction to $\mathfrak{Str}$ is the input of $M$ for that run.

Proof.

Let the running time of $M$ be bounded by $n^{k}$ , with $n$ the input length and $k$ a constant. The theory $\mathfrak{X}$ adds a chain structure on $N$ (the sort of $\mathfrak{Str}$ ), so that $T:=N^{k}$ is also a chain, which will play the role of the time parameter. Then, $\mathfrak{X}$ adds the inductive generators $\mathrm{Reg}:T\otimes N^{k}\to I$ (the work tape, which is of length at most $n^{k}$ because it cannot be longer than the running time of $M$ ), $\mathrm{P}_{r},\mathrm{P}_{w}:T\to N^{k}$ (the values of $r$ and $w$ ), and the inductive predicates $\mathrm{In}_{0},\ldots,\mathrm{In}_{m}$ over $T$ (where $\mathrm{In}_{i}(t)$ holds iff instruction $i$ is executed at time $t$ ). If $\mathbb{K}=\mathbb{R}$ , $\mathfrak{X}$ also adds the harmless predicate $\mathrm{Gez}$ over $T$ , with ancillary generators $\mathrm{Pos},\mathrm{Neg},\mathrm{Neg}^{-1}:T\to I$ (for the $\mathrm{Test}_{\mathbb{K}}$ relation), and the harmless predicate $\mathrm{Div}$ over $T$ , with ancillary generator $\mathrm{Quo}:T\to I$ (for division).

The equations added by $\mathfrak{X}$ are as follows (we will explain them momentarily):

	$\displaystyle{\mathrm{In}_{0}(0)\approx 1,\quad\mathrm{In}_{k}(0)\approx 0\ % \mathrm{for}\ k\not=0}\quad{\mathrm{max}(t)\approx\mathrm{In}_{m}(t)}\quad{% \mathrm{In}_{i}(t)\mathrm{In}_{j}(t)\approx 0\ \mathrm{for\ all}\ i\not=j}$		(2)
	$\displaystyle{\mathrm{Gez}(t)(\mathrm{Pos}(t)^{2}-\mathrm{Reg}(t,0))\approx 0}% \quad{\overline{\mathrm{Gez}(t)}(\mathrm{Neg}(t)^{2}+\mathrm{Reg}(t,0))\approx 0% }\quad\ {\overline{\mathrm{Gez}(t)}(\mathrm{Neg}(t)\mathrm{Neg}^{-1}(t)-1)% \approx 0}$		(3)
	$\displaystyle\mathrm{Div}(t)(\mathrm{Reg}(t,0)-\mathrm{Reg}(t,1)\mathrm{Quo}(t% ))\approx 0\quad\overline{\mathrm{Div}(t)}\mathrm{Reg}(t,0)\approx 0$		(4)
	$\displaystyle(\mathrm{P}_{w}(0)=0)\approx 1\quad(\mathrm{P}_{r}(0)=0)\approx 1$		(5)
	$\displaystyle{\smallint\!}_{x}\mathrm{In}_{k}(t)(\mathrm{P}_{i}(t)=x)\overline% {(\mathrm{P}_{i}({t_{+1}})={x_{+1}})+(\mathrm{P}_{i}({t_{+1}})=0)}\approx 0\ % \mathrm{with}\ i\in\{r,w\}$		(6)
	$\displaystyle{\smallint\!}_{x}\mathrm{In}_{k}(t)(\mathrm{P}_{i}(t)=x)\overline% {(\mathrm{P}_{i}(t_{+1})=x)}\approx 0$		(7)
	$\displaystyle{\mathrm{In}_{0}(t)\overline{\mathrm{In}_{1}(t_{+1})}+\cdots+% \mathrm{In}_{k}(t)\mathrm{Gez}(t)\overline{\mathrm{In}_{l}(t_{+1})}+\mathrm{In% }_{k}(t)\overline{\mathrm{Gez}(t)}\overline{\mathrm{In}_{k+1}(t_{+1})}+\cdots+% \mathrm{In}_{m-1}(t)\overline{\mathrm{In}_{m}(t_{+1})}\approx 0}$		(8)
	$\displaystyle\mathrm{In}_{k}(t)\mathrm{Reg}(t_{+1},0)\approx\mathrm{In}_{k}(t)% (\mathrm{Reg}(t,0)\mathrm{Reg}(t,1))\ \mathrm{where}\ \in\{+,-,\times\}$		(9)
	$\displaystyle\mathrm{In}_{k}(t)\mathrm{Reg}({t_{+1}},0)\approx\mathrm{In}_{k}(% t)\mathrm{Div}(t)(\mathrm{Reg}(t,1)/\mathrm{Reg}(t,0))+\mathrm{In}_{k}(t)% \overline{\mathrm{Div}(t)}$		(10)
	$\displaystyle{\smallint\!}_{x}\mathrm{In}_{k}(t)(\mathrm{P}_{w}(t)=x)\mathrm{% Reg}({t_{+1}},x)\approx{\smallint\!}_{y}\mathrm{In}_{k}(t)(\mathrm{P}_{r}(t)=y% )\mathrm{Reg}(t,y)$		(11)
	$\displaystyle{\overline{(\sum_{i\in I}\mathrm{In}_{i}(t))+(\sum_{j\in C}% \mathrm{In}_{j}(t))(\mathrm{P}_{w}(t)=0)}\mathrm{Reg}(t,0)\approx\overline{(% \sum_{i\in I}\mathrm{In}_{i}(t))+(\sum_{j\in C}\mathrm{In}_{j}(t))(\mathrm{P}_% {w}(t)=0)}\mathrm{Reg}({t_{+1}},0)}$		(12)
	$\displaystyle{{\smallint\!}_{s}(\sum_{i\in C}\mathrm{In}_{i}(t))(\mathrm{P}_{w% }(t)\not=s)(s\not=0)\mathrm{Reg}(t,s)\approx{\smallint\!}_{s}(\sum_{i\in C}% \mathrm{In}_{i}(t))(\mathrm{P}_{w}(t)\not=s)(s\not=0)\mathrm{Reg}({t_{+1}},s)}$		(13)
	$\displaystyle(i<_{T}\mathrm{max_{N}})\mathrm{Reg}(0,i)+\overline{(i<_{T}% \mathrm{max_{N}})}\mathrm{Reg}(0,i)\approx(i<_{T}\mathrm{max_{N}})X(i)$		(14)

Equations (2) state that the first (resp. last) instruction is the instruction of index $0$ (resp. $m$ ) and that only one instruction is executed at a time; (3) define the predicates $\mathrm{Gez}$ (which is true iff $s_{0}\geq 0$ , where $s_{0}$ is the content of register $0$ , as in Definition 18), $\mathrm{Pos}$ (resp. $\mathrm{Neg}$ and $\mathrm{Neg}^{-1}$ ) which is a witness of positivity (resp. negativity); (4) define the predicates $\mathrm{Div},\mathrm{Quo}$ which are witnesses of divisibility and the quotient; (5) and (6) state that $\mathrm{P}_{w}$ and $\mathrm{P}_{r}$ are initialized to $0$ and how they are updated, note that, due to the chain structure of $N^{k}$ , ${x_{+1}}\not=0$ and thus $(\mathrm{P}_{i}(t)=x_{+1})(\mathrm{P}_{i}(t)=0)\approx 0$ so the sum is well defined; (7) states that when $\mathrm{In}_{k}$ is not an update( $i$ ) the $\mathrm{P}_{i}$ addresses is not modified; (8) defines the jump instructions, (9) and (10) the operations and (11) the copy instructions; (12) states that the first cell of the tape is only modified by computations and copies, where $I$ is the set of indices of computation and $C$ the one of copy instructions, also, note that the sets $I$ and $C$ are disjoints which is important for summability; (13) states that the other cells can only change if the instruction is a copy and the writing register is the right one; (14) states that the work tape initially contains the input and is filled with zeros after that, note that $\mathrm{max_{N}}$ is the maximum of the sort $N$ (which $\mathfrak{X}$ equips with a chain structure), whereas $<_{T}$ is the strict order on the tensor $T=N^{k}$ (which is lexicographically ordered from the order on $N$ ).

By definition, $\mathfrak{X}$ adds no sorts and is finite. Towards proving the second point of the statement, we observe that a finite model of $\mathfrak{X}$ consists of a $\mathbb{K}$ -string $x$ of length $|N|$ (the underlying model of $\mathfrak{Str}$ in $\mathbb{K}$ ), where $|N|$ is the interpretation of $N$ , plus seven additional functions and $m+3$ predicates.

Let us prove the second point of the statement by induction on $|N|^{k}$ : if this is $1$ (i.e., there is only one time step), then by equations 1 and 2 we have that $m=0$ , so the machine has only one state, which is accepting. Therefore, any model is an accepting run of the machine. If $|N|^{k}=\{t_{0},\cdots,t_{n+1}\}$ (note that, by definition, $(t_{n})_{+1}=t_{n+1}$ ), by induction all the functions and predicates are defined at time $t_{n}$ , then, for some $i$ we have that $\mathrm{In}_{i}(t_{n})$ is defined. Also, $i$ cannot be $m$ by equation 2. This means that the current instruction is either a branch, an update, a copy or a computation.

First, if it is a branch( $l$ ), then, since we supposed that $\mathrm{Gez}(t_{n})$ is defined, by equation 9 we have that either $\mathrm{In}_{l}(t_{n+1})$ or $\mathrm{In}_{i+1}(t_{n+1})$ is defined, in any of those cases, $\mathrm{In}_{j}(t_{n+1})$ is also defined by equation 3. By equations 13 and 14 we have that $\mathrm{Reg}(t_{n+1},s)$ is also defined for any $s$ . Axioms 4 and 5 ensure that $\mathrm{Gez},\mathrm{Pos},\mathrm{Neg},\mathrm{Neg}^{-1},\mathrm{Div}$ and $\mathrm{Quo}$ are defined at time $t_{n+1}$ , and equation 8 gives us that $\mathrm{P}_{r}(t_{n+1})$ and $\mathrm{P}_{w}(t_{n+1})$ are both defined.

Then, if the instruction is an update, again, equations 13 and 14 ensure the definition of $\mathrm{Reg}(t_{n+1},s)$ for any $s$ , equations 4 and 5 for the definitions of $\mathrm{Gez},\mathrm{Pos},\mathrm{Neg},\mathrm{Neg}^{-1},\mathrm{Div}$ and $\mathrm{Quo}$ , equation 7 for $\mathrm{P}_{j}(t_{n+1})$ and 8 for $\mathrm{P}_{j^{\prime}}(t_{n+1})$ , with $j,j^{\prime}\in\{r,w\}$ and $j\neq j^{\prime}$ .

If the instruction is a copy, since $\mathrm{P}_{r}(t_{n})$ and $\mathrm{P}_{w}(t_{n})$ are defined we have that, for some $s\in N^{k}$ , $\mathrm{Reg}({t_{n+1}},s)$ is defined by equation 12, if $s\not=0$ then $\mathrm{Reg}(t_{n+1},0)$ is defined thanks to equation 13 and for all other $y\in N^{k}$ $\mathrm{Reg}(t_{n+1},y)$ is defined by equation 14. Again all other functions and predicates are defined by the same equations as before.

Finally, if the instruction is a computation, then either it is a division and $\mathrm{Reg}(t_{n+1},0)$ is defined by equation 11 ( $\mathrm{Reg}(t,0)$ is divisible by $\mathrm{Reg}(t,1)$ , if not then the behavior of the machine is not defined) either it is not a division and $\mathrm{Reg}(t_{n+1},0)$ is defined by equation 10. For all $s\not=0,\mathrm{Reg}(t_{n+1},s)$ is defined by equation 14 and the other functions and predicates are still defined as before.

We have thus proved that, at any given $t\leq|N|^{k}$ , if $i$ is the unique element of $\{0,\ldots,m\}$ such that $\mathrm{In}_{i}(t)$ holds, $(i,\mathrm{Reg}(t),\mathrm{P}_{r}(t),\mathrm{P}_{w}(t))$ is the configuration obtained by running $M$ for $t$ steps from the initial configuration on input $x$ . Equation 2 guarantees that this is an accepting run, as the machine must have entered instruction $m$ at some point before time $|N|^{k}$ (after which it stays there).

We are left with checking that the resulting algebra is inductive. The inductive generators are clearly of the right form, so we just need to check that the other predicates are indeed harmless: for $\mathrm{Gez}$ , in any model, at any time $t$ either $\mathrm{Reg}(t,0)$ is positive and there exists a real number $\mathrm{Pos}(t)$ such that $\mathrm{Pos}(t)^{2}-\mathrm{Reg}(t,0)=0$ either it is negative and there exists $\mathrm{Neg}(t)$ and $\mathrm{Neg}^{-1}(t)$ such that $\mathrm{Neg}(t)\mathrm{Neg}^{-1}(t)=1$ and $\mathrm{Neg}^{2}+\mathrm{Reg}(t,0)=0$ , in any case $(\mathrm{Pos}(t)^{2}-\mathrm{Reg}(t,0))(\mathrm{Neg}^{2}+\mathrm{Reg}(t,0))$ and $(\mathrm{Pos}(t)^{2}-\mathrm{Reg}(t,0))(\mathrm{Neg}\mathrm{Neg}^{-1}-1)$ have a solution. The same is true for $\mathrm{Div}$ , either $\mathrm{Reg}(t,0)$ is $0$ , either is not and there is a real number $\mathrm{Quo}(t)$ such that $(\mathrm{Reg}(t,0)-\mathrm{Reg}(t,1)\mathrm{Quo}(t))=0$ , in any case $\mathrm{Reg}(t,0)(\mathrm{Reg}(t,0)-\mathrm{Reg}(t,1)\mathrm{Quo}(t))$ has a solution. Hence, the theory is inductive. $\hfill\blacktriangleleft$

Theorem 22.

Let $\mathbb{K}$ be $\mathbb{F}_{1}$ or $\mathbb{R}$ and let $L$ be a $\mathbb{K}$ -problem. Then:

1.

$L\in\mathsf{RE}_{\mathbb{K}}$ iff $L=\Gamma_{\mathbb{K}}(\mathcal{A})$ with $\mathcal{A}$ a $\mathbb{K}[\mathfrak{Str}]$ -algebra of finite presentation;
2.

$L\in\mathsf{NP}_{\mathbb{K}}$ iff $L=\Gamma_{\mathbb{K}}(\mathcal{A})$ with $\mathcal{A}$ a plain $\mathbb{K}[\mathfrak{Str}]$ -algebra of finite presentation;
3.

$L\in\mathsf{P}_{\mathbb{K}}$ iff $L=\Gamma_{\mathbb{K}}(\mathcal{A})$ with $\mathcal{A}$ an inductive $\mathbb{K}[\mathfrak{Str}]$ -algebra of finite presentation.

Proof.

For (1), consider an arbitrary $\mathbb{K}$ -RAM $M$ . We slightly modify the proof of Lemma 21: rather than using $N^{k}$ as chain, we introduce a new sort $T$ , with the structure of a chain, and reproduce the proof with $T$ instead of $N^{k}$ . The theory thus obtained is no longer inductive but is still of finite presentation, and its models are accepting runs of $M$ , with the interpretation of $T$ giving its running time, which may now be arbitrary.

Conversely, if we are given an algebra $\mathbb{K}[\mathfrak{T}]$ with $\mathfrak{T}$ finitely extending $\mathfrak{Str}$ and a $\mathbb{K}$ -string $s$ , we have that a model of $\mathfrak{T}$ extending $s$ has finitely more data than $s$ , namely the data interpreting the additional sorts and generators of $\mathfrak{T}$ . Given such extra data, checking whether it verifies the additional equations of $\mathfrak{T}$ , of which there are finitely many, is certainly doable in a finite time (in fact, in polynomial time) on a $\mathbb{K}$ -RAM.

For (2), let $L\in\mathsf{NP}_{\mathbb{K}}$ . This means that there exists a polytime $\mathbb{K}$ -RAM $M$ and a constant $c$ such that, for every $\mathbb{K}$ -string $s$ , $s\in L$ iff there exists a string $s^{\prime}$ of length at most $|s|^{c}$ such that $M$ accepts the pair $(s,s^{\prime})$ . We let $k$ be the maximum between $c$ and the exponent of the polynomial bound on the running time of $M$ , and construct a $\mathbb{K}[\mathfrak{Str}]$ -algebra just like in the proof of Lemma 21, expect that we do not initialize the work tape beyond the input length. The algebra thus obtained is still plain (no sort is added) of finite presentation, but it is no longer inductive because the generator $\mathrm{Reg}$ now is missing some initialization equations. The models of the resulting theory are still accepting runs of $M$ , on which the tape is now initialized non-deterministically beyond the input $s$ . In particular, it may be initialized with the witness $s^{\prime}$ , which is small enough to fit in $N^{k}$ .

The converse is much like point (1), except that this time we only need to account for the interpretation of the extra generators, which are of polynomial size (because these have types of the form $N^{k}\to\bigoplus_{j}N^{k_{j}}$ with $k$ and $k_{j}$ constants) and may therefore be guessed and then checked with a polytime $\mathbb{K}$ -RAM.

For (3), the implication from left to right is Lemma 21. For the converse, if we have an inductive algebra $\mathbb{K}[\mathfrak{T}]$ with $\mathfrak{T}$ finitely extending $\mathfrak{Str}$ , and we have a $\mathbb{K}$ -string $s$ , we check whether $s$ may be extended to a model of $\mathfrak{T}$ as outlined after Definition 20. The only thing left to verify is that computing harmless generators takes no more than polynomial time.

Let us start with the case $\mathbb{K}=\mathbb{R}$ . For each harmless predicate $P$ we have an equation of the form $P(t)\varphi(t)\approx_{\Gamma}0$ , so for each $t$ , to know whether $P(t)$ is true in a given model in $\mathbb{R}$ we just need to check whether the interpretation of $\varphi(t)$ has a root in $\mathbb{R}$ . The idea here is to generalize the discriminant to multivariate polynomials of degree two. See the appendix for details (Lemma 24).

When $\mathbb{K}=\mathbb{F}_{1}$ , the truth of a harmless generator at time $t$ is controlled by a polynomial $\varphi(t)$ of degree two. In $\mathbb{F}_{1}$ , this is interpreted as a $2$ -DNF. Therefore, testing the equation $\varphi(t)=0$ is testing whether a $2$ -DNF is falsifiable, which is well-known to be polytime [20]. $\hfill\blacktriangleleft$

Let us conclude with a few words about when $\mathbb{K}=\mathbb{Z}$ . In this case, Lagrange’s four square theorem may be used to implement $\mathrm{Test}_{\mathbb{Z}}$ . Moreover, combined with the Davis-Putnam-Robinson-Matiyasevich theorem, Theorem 22 implies that $\mathsf{RE}_{\mathbb{Z}}=\mathsf{NP}_{\mathbb{Z}}$ .

5 Discussion and Perspectives

As implicitly shown in §2.2, ultrarings generalize commutative rings by generalizing their categories of modules (free of finite rank). This is not a new idea: it has already been mentioned or directly used in at least a few attempts to generalize algebraic geometry beyond commutative rings [13, 10, 6, 4]. What is new in ultrarings is the emphasis on presenting such generalized algebraic objects by means of a language which is directly derived from first-order logic and which still captures all ring presentations.

Speaking of algebraic geometry, it is very interesting to point out that the ultraring $\mathbb{F}_{1}$ has some of the properties typically expected of the “field with one element”. In fact, the full subcategory of ultrarings which are plain $\mathbb{F}_{1}$ -algebras (i.e., of the form $\mathbb{F}_{1}[\mathfrak{T}]$ with $\mathfrak{T}$ sortless) may be fully and faithfully embedded in the category of generalized commutative rings studied by Durov [12]. Under this embedding, $\mathbb{F}_{1}$ is mapped to Durov’s version of the “field with one element”.

The reader may have observed that the field $\mathbb{F}_{2}$ could also have been used capture Boolean computation: $\mathbb{F}_{2}$ -strings are just binary strings and $\mathsf{RE}_{\mathbb{F}_{2}}$ , $\mathsf{NP}_{\mathbb{F}_{2}}$ and $\mathsf{P}_{\mathbb{F}_{2}}$ coincide with the usual Boolean classes. We contend that this is sort of an accident, and that Boolean computability is really over $\mathbb{F}_{1}$ . Indeed, any $\mathbb{K}$ -RAM may be restricted to operate only on $\{0,1\}$ , simulating a Boolean machine. This is routinely used in BSS or algebraic complexity to define the “Boolean part” of the language decided by a machine. Our approach nicely explains this by the existence of a unique morphism $\mathbb{F}_{1}\to\mathbb{K}$ saying that “Booleans are everywhere”. By contrast, there is no morphism $\mathbb{F}_{2}\to\mathbb{K}$ unless $\mathbb{K}$ has characteristic $2$ .

In this paper, we have not developed the theory of ultrarings to the extent necessary to give a technical content to the above statement, but to the acquainted reader we may say that the above observation becomes a change of base along $\mathbb{F}_{1}\to\mathbb{K}$ . In fact, the definition of ultraring in this paper has been intentionally restricted to give “logical-looking” presentations. We already know that ultrarings may be given a more liberal definition, still allowing presentations, but of a different flavor than the ones introduced here. Modules for these ultrarings may open interesting perspectives in terms of computational complexity: at least in the plain case (i.e., for the class $\mathsf{NP}$ and below), modules generalize algebras and could potentially be used to give finer characterizations of complexity classes.

In a different direction, if we restrict to Boolean lextensive categories (which, as §2.2 shows, are special cases of ultrarings) we know that more Boolean complexity classes may be captured by adapting ideas from descriptive complexity. These include deterministic and nondeterministic logarithmic space, the logtime hierarchy and the polynomial hierarchy, as well as non-uniform complexity classes, and will be the subject of another paper [9].

Finally, let us mention that descriptive complexity has well-known tools, taking the form of various pebble games [17], allowing one to establish lower bound results. These have been reformulated categorically [1, 3, 11, 2, 22]. Knowing if and how these reformulations interface with our work is an interesting question for the future.

References

[1] Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Proceedings of LICS, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005129.
[2] Samson Abramsky and Luca Reggio. Arboreal categories: An axiomatic theory of resources. Log. Methods Comput. Sci., 19(3), 2023. doi:10.46298/LMCS-19(3:14)2023.
[3] Samson Abramsky and Nihil Shah. Relating structure and power: Comonadic semantics for computational resources. J. Log. Comput., 31(6):1390–1428, 2021. doi:10.1093/LOGCOM/EXAB048.
[4] John C. Baez, Joe Moeller, and Todd Trimble. 2-rig extensions and the splitting principle. arXiv:2410.05598 [math.CT], 2024.
[5] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers. Bulletin of the American Mathematical Society, 21(1):1–46, 1989.
[6] Martin Brandenburg. Tensor categorical foundations of algebraic geometry. Ph.d. thesis, University of Münster, 2014.
[7] Martin Brandenburg and Alexandru Chirvasitu. Tensor functors between categories of quasi-coherent sheaves. Journal of Algebra, 399:675–692, 2014.
[8] Aurelio Carboni, Stephen Lack, and R.F.C. Walters. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra, 84(2):145–198, 1993.
[9] Baptiste Chanus and Damiano Mazza. A categorical approach to describing complexity classes. In preparation. Available on the authors’ web page, 2024.
[10] Alexandru Chirvasitu and Theo Johnson-Freyd. The fundamental pro-groupoid of an affine 2-scheme. Appl. Categ. Structures, 21(5):469–522, 2013. doi:10.1007/S10485-011-9275-Y.
[11] Anuj Dawar, Tomás Jakl, and Luca Reggio. Lovász-type theorems and game comonads. In Proceedings of LICS, pages 1–13. IEEE, 2021. doi:10.1109/LICS52264.2021.9470609.
[12] Nikolai Durov. New Approach to Arakelov Geometry. arXiv 0704.2030 [math.AG], 2007.
[13] Nikolai Durov. Classifying vectoids and operad kinds. Proc. Steklov Inst. Math., 273:48–63, 2011.
[14] Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proccedings, volume 7, pages 43–73, 1974.
[15] Erich Grädel and Klaus Meer. Descriptive complexity theory over the real numbers. In Proceedings of STOC, pages 315–324. ACM Press, 1995. doi:10.1145/225058.225151.
[16] Neil Immerman. Relational queries computable in polynomial time. Information and Control, 68(1):86–104, 1986. doi:10.1016/S0019-9958(86)80029-8.
[17] Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. doi:10.1007/978-1-4612-0539-5.
[18] Bart P. F. Jacobs. Categorical Logic and Type Theory, volume 141 of Studies in logic and the foundations of mathematics. North-Holland, 2001.
[19] Peter T. Johnstone. Sketches of en Elephant. A Topos Theory Compendium. Volume 2. Oxford University Press, 2002.
[20] Melven R. Krom. The decision problem for a class of first-order formulas in which all disjunctions are binary. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 13(1–2):15–20, 1967.
[21] Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic. Springer, 1994.
[22] Yoàv Montacute and Glynn Winskel. Concurrent games over relational structures: The origin of game comonads. In Proceedings of LICS, pages 58:1–58:14. ACM, 2024. doi:10.1145/3661814.3662075.

Appendix A Appendix

A.1 Proofs of Some Lemmas

Proof of Lemma 2.

We start by observing that, if $\iota_{i}:B_{i}\to B_{1}\oplus B_{2}$ are injections, then $\iota_{i}\delta^{\ast}_{B_{i}}(\iota^{\ast}_{i}\otimes\mathrm{id}_{B_{i}})=% \delta^{\ast}_{B_{1}\oplus B_{2}}(\mathrm{id}_{B_{1}\oplus B_{2}}\otimes\iota_% {i})$ . We prove this for $i=1$ , the other case is essentially identical. We omit obvious subscripts for identity arrows. Let $\chi=[\iota_{1}\otimes\mathrm{id},\iota_{2}\otimes\mathrm{id}]:(B_{1}\otimes B% _{1})\oplus(B_{2}\otimes B_{1})\to(B_{1}\oplus B_{2})\otimes B_{1}$ be the distributivity isomorphism. We have, using (1), $\iota_{1}\delta^{\ast}_{B_{1}}(\iota^{\ast}_{1}\otimes\mathrm{id})\chi=\iota_{% 1}\delta^{\ast}_{B_{1}}[\iota^{\ast}_{1}\iota_{1}\otimes\mathrm{id},\iota^{% \ast}_{1}\iota_{2}\otimes\mathrm{id}]=\iota_{1}\delta^{\ast}_{B_{1}}[\mathrm{% id},0]=[\iota_{1}\delta^{\ast}_{B_{1}},0]=[\delta^{\ast}_{B_{1}\oplus B_{2}}(% \iota_{1}\otimes\iota_{1}),\delta^{\ast}_{B_{1}\oplus B_{2}}(\iota_{2}\otimes% \iota_{1})]=\delta^{\ast}_{B_{1}\oplus B_{2}}(\mathrm{id}\otimes\iota_{1})\chi$ , which proves the claim because $\chi$ is invertible. We will also need that, if $\kappa_{i}:A\otimes B_{i}\to(A\otimes B_{1})\oplus(A\otimes B_{2})$ are injections and $\chi^{\prime}:(A\otimes B_{1})\oplus(A\otimes B_{2})\to A\otimes(B_{1}\oplus B% _{2})$ another instance of distributivity, then $\chi^{\prime}\kappa_{i}=\mathrm{id}\otimes\iota_{i}$ , which holds by definition of $\chi^{\prime}$ .

Suppose now that we have $f,g:A\rightrightarrows B_{1}\oplus B_{2}$ with $\iota_{i}^{*}f=\iota_{i}^{*}g$ for $i=1,2$ . Using the above observations, we have $\delta^{\ast}_{B_{1}\oplus B_{2}}(f\otimes\mathrm{id})\chi^{\prime}\kappa_{i}=% \delta^{\ast}_{B_{1}\oplus B_{2}}(f\otimes\iota_{i})=\iota_{i}\delta^{\ast}_{B% _{i}}(\iota^{\ast}_{i}f\otimes\mathrm{id})=\iota_{i}\delta^{\ast}_{B_{i}}(% \iota^{\ast}_{i}g\otimes\mathrm{id})$ , from which, applying the first two equalities in reverse order, we obtain $\delta^{\ast}_{B_{1}\oplus B_{2}}(f\otimes\mathrm{id})\chi^{\prime}\kappa_{i}=% \delta^{\ast}_{B_{1}\oplus B_{2}}(g\otimes\mathrm{id})\chi^{\prime}\kappa_{i}$ for $i=1,2$ . Since injections are jointly epic and $\chi^{\prime}$ is invertible, we infer $\delta^{\ast}_{B_{1}\oplus B_{2}}(f\otimes\mathrm{id})=\delta^{\ast}_{B_{1}% \oplus B_{2}}(g\otimes\mathrm{id})$ , from which we conclude $f=g$ by definition $\delta^{\ast}$ -category. $\hfill\blacktriangleleft$

Proof of Lemma 8.

We start by observing that cancellativity implies $\overline{\overline{p}}\approx p$ , as well as $\overline{1}\approx 0$ . Next, we claim that, whenever $q$ matches the same contexts as $p$ and $q^{2}\approx q$ , we have $\overline{pq}\approx\overline{p}q+p\overline{q}+\overline{p}\,\overline{q}$ . Indeed, $pq+\overline{pq}\approx 1\approx(p+\overline{p})(q+\overline{q})\approx pq+% \overline{p}q+p\overline{q}+\overline{p}\,\overline{q}$ , so we conclude by cancellativity.

Suppose that $p\overline{p}\approx 0$ . Then, $p\approx p(p+\overline{p})\approx p^{2}+p\overline{p}\approx p^{2}$ . For the converse, if $p^{2}\approx p$ , then using the above claim we have $\overline{p\overline{p}}=p^{2}+\overline{p}^{2}+\overline{p}p=p+\overline{p}(% \overline{p}+p)=p+\overline{p}=1$ , so $p\overline{p}=0$ by the first two observations. Finally, we have $\overline{p}\approx\overline{p^{2}}\approx p\overline{p}+\overline{p}p+% \overline{p}^{2}\approx\overline{p}^{2}$ . $\hfill\blacktriangleleft$

Proof of Lemma 11.

For indices $h,j,j^{\prime},k$ , let $r,r^{\prime},s,s^{\prime}$ be monomials in $p_{j}k,p_{j^{\prime}k},q_{hj},q_{hj^{\prime}}$ , respectively. We need to check that each $(q\circ p)_{hk}$ is a polynomial by verifying that, when $j\neq j^{\prime}$ we have ${\smallint\!}_{\vec{y}^{j}}sr\frown_{\vec{x}^{k}:T_{k}}{\smallint\!}_{\vec{y}^% {j^{\prime}}}s^{\prime}r^{\prime}$ . By hypothesis, $r\frown_{\vec{x}^{k}:T_{k}}r^{\prime}$ , so we conclude by the last rule of Fig. 3. We must also check that the context is valid. By hypothesis, $q_{hj}p_{jk}$ is matched by $\vec{x}^{k}:T_{k},\vec{y}^{j}:U_{j},\vec{z}^{h}:V_{h}$ , with $\vec{y}^{j}$ and $\vec{z}^{h}$ being outputs, hence each monomial ${\smallint\!}_{\vec{y}^{j}}rs$ is well-typed and matched by $\vec{x}^{k}:T_{k},\vec{z}^{h}:V_{h}$ , as required. Finally, we must check condition ( ${\dagger}$ ) of Definition 10. Given $h\neq h^{\prime}$ , we require ${\smallint\!}_{\vec{y}^{j}}sr\frown_{\vec{x}^{k}:T_{k}}{\smallint\!}_{\vec{y}^% {j^{\prime}}}t^{\prime}r^{\prime}$ , where $t^{\prime}$ is a monomial of $q_{h^{\prime}j^{\prime}}$ . If $j\neq j^{\prime}$ , we conclude as above. If $j=j^{\prime}$ , by hypothesis we have $s\frown_{\vec{y}^{j}:U_{j}}t^{\prime}$ , so we conclude by applying the last rule of Fig. 3 to these instead. $\hfill\blacktriangleleft$

A.2 Interpreting Polynomials in a $\mathfrak{S}$ -structure

Let $M$ be a $\mathfrak{S}$ -structure. We start by inductively defining an interpretation over $M$ for positive monomials-in-context, following Fig. 1.

$\blacksquare$
As a base case, we interpret monomials over $\mathfrak{S}$ with the maximal codomain context of all outputs and the minimal domain of all remaining free variables, for each of the basic constructions of monomials:
- –
  
  $M\left(x:A\vdash(x=_{A}y)::y:A\right)$ is $\mathrm{id}_{M_{0}(A)}$ ,
- –
  
  $M\left(\vec{x}:T\vdash(g^{j}(\vec{x})=\vec{y})::\vec{y}:U\right)$ is $M_{1}(g);\iota^{*}_{j}$ ,
- –
  
  $M\left(\vdash 1::\right)$ is $\varepsilon_{I}=\mathrm{id}_{I}$ ,
$\blacksquare$
Next, we describe the effect of expanding and reorganizing contexts.
- –
  
  Given $f:=M(\Gamma\vdash p::\Delta,x:A)$ , let $M(\Gamma,x:A\vdash p::\Delta):=\varepsilon_{M_{0}(A)}\delta^{*}_{M_{0}(A)}(f% \otimes\mathrm{id}_{A})$ .
- –
  
  Relatedly, given $f:=M(\Gamma\vdash p::\Delta)$ , we define $M(x:A,\Gamma\vdash p::\Delta)$ to be $\beta(\varepsilon_{M_{0}(A)}\otimes f)$ , (recalling that $\beta:I\otimes I\to I$ is the canonical isomorphism).
- –
  
  Given $M(\Gamma\vdash p::\Delta)$ , permutations of $\Gamma$ and $\Delta$ are interpreted by pre- or post-composing with the corresponding symmetry morphisms.
$\blacksquare$
Finally, we specify how monomials combine.
- –
  
  Given $f:=M(\Gamma\vdash p::\Delta,\vec{x}:T)$ and $g:=M(\vec{x}:T,\Gamma^{\prime}\vdash q::\Delta^{\prime})$ we can define $M\left(\Gamma,\Gamma^{\prime}\vdash\int_{\vec{x}:T}pq::\Delta,\Delta^{\prime}\right)$ to be $(\mathrm{id}\otimes g)(f\otimes\mathrm{id})$ ; to recover an interpretation of $\int_{\vec{x}}p$ , we identify this with $\int_{\vec{x}}p1$ .
- –
  
  Given $f:=M(x_{1}:A,x_{2}:A,\Gamma\vdash p::\Delta)$ and a variable $x$ not appearing in $p$ , we define $M(x:A,\Gamma\vdash p[x_{1}/x][x_{2}/x]::\Delta)$ to be $f(\delta_{M_{0}(A)}\otimes\mathrm{id})$ .
- –
  
  Dually, given $f:=M(\Gamma\vdash p::x_{1}:B,x_{2}:B,\Delta)$ and a variable $x$ not appearing in $p$ , we define $M(\Gamma\vdash p[y_{1}/y][y_{2}/y]::y:B,\Delta)$ to be $(\delta^{*}_{M_{0}(B)}\otimes\mathrm{id})f$ .

Let us check that the above interpretations are well-defined. The first set of rules give unambiguous interpretations. For the second set, there is exactly one way to arrive a given context using these rules up to reordering, so it suffices to check that the order of operations does not affect the result; this is straightforward, relying on the fact that $\delta^{*}$ is symmetric.

The only place where ambiguity is introduced in the third set of rules, where the interpretation ostensibly depends on how the domain and codomain contexts are partitioned. We take these case by case.

$\blacksquare$

Consider $M\left(\Gamma,\Gamma^{\prime}\vdash\int_{\vec{x}:T}pq::\Delta,\Delta^{\prime}\right)$ . By disjointness, $\Delta$ and $\Delta^{\prime}$ must respectively contain only outputs of $p$ and $q$ , so this is unambiguous; the remaining free variables of $p$ and $q$ must respectively go into $\Gamma$ and $\Gamma^{\prime}$ . Any remaining free variables, whether assigned to $\Gamma$ or $\Gamma^{\prime}$ , must be interpreted by $\varepsilon$ , which eliminates any remaining ambiguity.
$\blacksquare$

In $M(x:A,\Gamma\vdash p[x_{1}/x][x_{2}/x]::\Delta)$ , there is formally a choice to make about how to assign the instances of $x$ to $x_{1}$ or $x_{2}$ ; however, since the inductive construction will eventually disambiguate between any pair of repeated instances, commutativity and associativity of $\delta$ guarantee that any such choice will result in the same interpretation (considering also that the interpretation is invariant under $\alpha$ -equivalence).
$\blacksquare$

Similarly, distinguishing duplicates of variables in the codomain produces a well-defined result by commutativity and associativity of $\delta^{*}$ , so we are done.

Next, given $f:=M\left(\Gamma\vdash p::\right)$ , we have that $M\left(\Gamma\vdash p^{2}::\right)$ is exactly $(f\otimes f)\delta$ . As such, when these interpretations are equal, we may take $M\left(\Gamma\vdash\overline{p}::\right)$ to be $\overline{f}$ provided by Definition 3, thus extending the above to monomials featuring $\overline{p}$ .

Finally, we define $M\left(\Gamma\vdash 0::\Delta\right)$ to be the zero morphism of the appropriate type.

Lemma 23.

Suppose we are given a theory $\mathfrak{T}$ over a signature $\mathfrak{S}$ and a $\mathfrak{S}$ -structure $M$ in $\mathcal{A}$ . Suppose that whenever we have positive monomials-in-context $\Gamma\vdash p::\Delta$ and $\Gamma\vdash q::\Delta$ such that $p\approx_{\Gamma,\Delta}q$ , it is the case that $M(\Gamma\vdash p::\Delta)=M(\Gamma\vdash q::\Delta)$ , so that in particular $M$ can interpret all monomials which are $\approx$ -polynomials. Suppose further that $M$ identifies $p$ and $q$ whenever $p\approx q$ when $p$ and $q$ are either monomials or $0$ . Then $p\frown_{\mathfrak{T}}q$ implies the pairing $\langle p,q\rangle$ exists in $\mathcal{A}$ .

Proof.

It suffices to check the axioms of Fig. 3 which determine the compatibility relation. Indeed, $pq\approx 0$ guarantees that if $M$ respectively interprets $p, q$ as $f, g$ in a given context then the first axiom of ultrarings Definition 3 ensures that the pairing exists.

The pairing of two components $j,j^{\prime}$ of (the interpretation of) a generator $g$ is the result of coinjecting $g$ onto the coproduct of their codomains.

If $p\frown q$ and $\langle p,q\rangle$ exists, we can obtain the pairing of the interpretations of ${\smallint\!}_{\vec{x},\vec{y}}spr$ and ${\smallint\!}_{\vec{x},\vec{z}}tqr$ by precomposing with $r$ and postcomposing with $s\oplus t$ .

The existence of pairings in the last instance is immediate, so we are done. $\hfill\blacktriangleleft$

As such, given $\mathfrak{T}$ and a model $M$ satisfying the conditions of Lemma 23, $M$ has a well-defined interpretation of any $\approx$ -polynomial-in-context $\Gamma\vdash p::\Delta$ as the joint pairing of the monomials appearing in $p$ (with the same context), followed by the codiagonal map.

Proposition 15. [Restated, see original statement.]

Let $\mathfrak{T}$ be a theory. There is an $\mathcal{A}$ -natural equivalence of categories $\mathfrak{T}\text{-}\mathrm{Mod}(\mathcal{A})\simeq\mathbf{URing}(\mathbb{F}_{% 1}[\mathfrak{T}],\mathcal{A}).$

Proof.

We have thus far shown that a $\mathfrak{T}$ -model $M$ in $\mathcal{A}$ uniquely determines interpretations of $\approx^{\mathfrak{T}}$ -polynomials-in-context. To produce a functor $\mathbb{F}_{1}[\mathfrak{T}]\to\mathcal{A}$ , we need to extend this to $\approx^{\mathfrak{T}}$ -matrices. Each entry of a matrix $(p_{jk})$ determines a morphism $M_{0}(T_{k})\to M_{0}(U_{j})$ . Condition ( ${\dagger}$ ) of Definition 10 ensures that for fixed $k$ , the interpretations of $p_{jk}$ can be paired to give a morphism $M_{0}(T_{k})\to\bigoplus_{j\in J}M_{0}(U_{j})$ ; via the universal property of the coproduct, these produce a morphism $\bigoplus_{k\in K}M_{0}(T_{k})\to\bigoplus_{j\in J}M_{0}(U_{j})$ . This extended construction ensures that the monoidal product and coproduct, as well as $\delta$ , $\delta^{*}$ and $\epsilon$ , are preserved.

Conversely, a morphism of ultrarings $F:\mathbb{F}_{1}[\mathfrak{T}]\to\mathcal{A}$ defines a model $M$ by its restriction to the sorts and generators. The equations of $\mathfrak{T}$ necessarily hold because they correspond to morphisms forced to be equal in $\mathbb{F}_{1}[\mathfrak{T}]$ , so are mapped by $F$ to the equal morphisms in $\mathcal{A}$ .

It is straightforward to verify that a model morphism uniquely determines a monoidal natural transformation, and conversely, since the latter are determined by their components at objects which generate the category under monoidal products and coproducts.

Finally, naturality in $\mathcal{A}$ follows from the fact that morphisms of ultrafunctors preserve the required structure: composing with an ultraring morphism $\mathcal{A}\to\mathcal{B}$ turns a $\mathfrak{T}$ -model in $\mathcal{A}$ into one in $\mathcal{B}$ . $\hfill\blacktriangleleft$

Theorem 17. [Restated, see original statement.]

Let $\mathcal{R}$ be an ultraring and $\mathfrak{T}$ its canonical theory, as defined in Definition 16. Then $\mathcal{R}\simeq\mathbb{F}_{1}[\mathfrak{T}]$ .

Proof.

We have a functor $\ulcorner-\urcorner:\mathcal{R}\to\mathbb{F}_{1}[\mathfrak{T}]$ sending each object $X$ to the sort $\ulcorner X\urcorner$ and each morphism $g:X\to Y$ to the corresponding generator (with no decomposition of $X$ and $Y$ as tensors or coproducts). We show that $\ulcorner-\urcorner$ is an equivalence of ultrarings.

Consider the generators (which we distinguish by a subscript) $\ulcorner\mathrm{id}\urcorner_{1}:\ulcorner\bigotimes_{j\in J}A_{j}\urcorner% \to\bigotimes_{j\in J}\ulcorner A_{j}\urcorner$ and $\ulcorner\mathrm{id}\urcorner_{2}:\bigotimes_{j\in J}\ulcorner A_{j}\urcorner% \to\ulcorner\bigotimes_{j\in J}A_{j}\urcorner$ . By the second and first equations, these are mutual inverses in $\mathbb{F}_{1}[\mathfrak{T}]$ . Moreover, naturality of these morphisms follows from the fourth axiom (applied inductively), so $\ulcorner-\urcorner$ preserves the monoidal product.

Consider the generator $\ulcorner\mathrm{id}\urcorner:\ulcorner\bigoplus_{j\in J}A_{j}\urcorner\to% \bigoplus_{j\in J}\ulcorner A_{j}\urcorner$ . By the third equation, we have that $\left(\ulcorner\mathrm{id}\urcorner^{j}(\vec{x})=\vec{y}\right)\approx(% \ulcorner\iota^{*}_{j}\urcorner(\vec{x})=\vec{y}),$ so this is equal to the row vector $(\ulcorner\iota^{*}_{j_{1}}\urcorner,\dotsc,\ulcorner\iota^{*}_{j_{n}}\urcorner)$ .

Dually, we have generators $\ulcorner\iota_{i}\urcorner:\ulcorner A_{i}\urcorner\to\bigoplus_{j\in J}% \ulcorner A_{j}\urcorner$ . By the third, first and fifth equations, we have $\left(\ulcorner\iota_{i}\urcorner^{j}(\vec{x})=\vec{y}\right)\approx\left(% \ulcorner\iota^{*}_{j}\iota_{i}\urcorner(\vec{x})=\vec{y}\right)$ which gives $(\vec{x}=\vec{y})$ if $i=j$ and $0$ otherwise. Thus $\ulcorner-\urcorner$ preserves the coproduct injections; in particular, these morphisms are compatible, so we can construct the column vector $(\ulcorner\iota_{j_{1}}\urcorner,\dotsc,\ulcorner\iota_{j_{n}}\urcorner)^{t}$ . We can use the second and third axioms to conclude that this column vector is the inverse to $\ulcorner\mathrm{id}\urcorner$ , so $\ulcorner-\urcorner$ preserves coproducts. Formally, we must also check that the universal morphisms are respected by this isomorphism, in the sense that $\int_{\vec{y}}\left(\ulcorner[f_{1},\dotsc,f_{n}]\urcorner(\vec{x})=\vec{y}% \right)(\ulcorner\mathrm{id}\urcorner(\vec{y})=\vec{z})\approx\int_{\vec{y}^{% \prime}}(\ulcorner\mathrm{id}\urcorner(\vec{x})=\vec{y}^{\prime})\left(\left(% \ulcorner f_{1}\urcorner,\dotsc,\ulcorner f_{n}\urcorner\right)(\vec{y}^{% \prime})=\vec{z}\right).$ It suffices to check this componentwise by composing with $\iota_{i}$ , which works by the preceding observations and the second axiom.

For the $\delta^{*}$ -category structure, we observe that the sixth, seventh and eighth axioms directly ensure that these are preserved up to the isomorphisms constructed above. With this, we have shown that $\ulcorner-\urcorner$ is a valid morphism of ultrarings.

Conversely, there is a canonical model of the canonical theory $\mathfrak{T}$ in $\mathcal{R}$ , given by interpreting $\ulcorner A\urcorner$ as $A$ and $\ulcorner g\urcorner$ as $g$ (with the relevant typing). The claim that this $\mathfrak{S}$ -structure is indeed a model amounts to saying that the interpretations of the monomials appearing in the axioms of Definition 16 are equal in $\mathcal{R}$ , which is straightforward to check.

Finally, to see that $\ulcorner-\urcorner$ is an equivalence, we simply observe on the one hand that the induced model in $\mathbb{F}_{1}[\mathfrak{T}]$ is isomorphic to that corresponding to the identity functor and on the other that the induced endofunctor of $\mathcal{R}$ is naturally isomorphic to the identity. The involved natural isomorphisms are the structural ones constructed above. $\hfill\blacktriangleleft$

A.3 Harmless Predicates Over the Real Numbers

Lemma 24.

In the case $\mathbb{K}=\mathbb{R}$ , the truth value of a harmless predicate may be computed in constant time on a $\mathbb{R}$ -RAM.

Proof.

For each harmless predicate $P$ we have an equation of the form $P(t)\varphi(t)\approx_{\Gamma}0$ , so for each $t$ , to know whether $P(t)$ is true in a given model in $\mathbb{R}$ we just need to check whether the interpretation of $\varphi(t)$ has a root in $\mathbb{R}$ . The idea here is to reduce this problem as a series of positivity tests that can be done in constant time by generalizing the idea of the discriminant for $n$ variate polynomials of degree two. Let us give some details about this generalization.

If the polynomial is of degree zero the test is trivial because it has no roots. If it is of degree one, since every polynomial of $\mathbb{R}$ of odd degree have a root in $\mathbb{R}$ , we know that there is a root in $\mathbb{R}$ . The only non trivial case is the degree two. Since we work in $\mathbb{R}$ the polynomial has a root in $\mathbb{R}$ iff it is reducible. First, let us do the special case of an homogeneous polynomial. A quadratic form $q$ can be written as a matrix multiplication $x^{T}Ax$ , where $A$ is the Kronecker matrix of the quadratic form and is a symmetric matrix. We now show that $A$ has rank one iff $q$ is reducible. First if $q$ is reducible then we can write the $q$ as $(\sum_{i}b_{i}x_{i})(\sum_{i}c_{i}x_{i})$ , by rewriting it with matrices multiplication $q=x^{T}\Big{(}\begin{smallmatrix}b_{0}&&\\ &\cdots&\nobreakspace\\ &&b_{n}\end{smallmatrix}\Big{)}\Big{(}\begin{smallmatrix}1&1&1\\ 1&1&1\\ 1&1&1\end{smallmatrix}\Big{)}\Big{(}\begin{smallmatrix}c_{0}&&\\ &\cdots&\nobreakspace\\ &&c_{n}\end{smallmatrix}\Big{)}x$ so $A$ is of rank $1$ . Conversely if $A$ is of rank one, since we know that $A$ is a real symmetric matrix, it is diagonalizable. Hence, $A$ is similar to $\Big{(}\begin{smallmatrix}0&0&0\\ 0&0&0\\ 0&0&1\end{smallmatrix}\Big{)}$ which is also similar to $\Big{(}\begin{smallmatrix}1&1&1\\ 1&1&1\\ 1&1&1\end{smallmatrix}\Big{)}$ thus we can rewrite $q$ as a product of two degree one polynomials. Moreover $A$ is of rank one iff it has exactly one non-zero eigenvalue. Hence, we need $0$ to be root of its characteristic polynomial with multiplicity $m-1$ , $m$ being the number of variables, we can then rewrite the general form of the characteristic polynomial as $\lambda^{m-1}((-1)^{m}\lambda+(-1)^{m-1}\mathrm{Tr}(A))$ . By identifying with the formula $\mathrm{det}(A-\lambda I_{m})$ we are given a set of constraint on the coefficients of the quadratic form for it to be reducible. Let us now consider a general multivariate polynomial of degree two. We can write it as $p=\sum_{i,j}a_{i,j}x_{i}x_{j}+\sum_{i}a^{\prime}_{i}x_{i}+\sum_{i}a^{\prime% \prime}_{i}$ the $x_{i}$ being variables taken in a set $X$ . The following polynomial $q=\sum_{i,j}a_{i,j}x_{i}x_{j}+y(\sum_{i}a^{\prime}_{i}x_{i})+y^{2}(\sum_{i}a^{% \prime\prime}_{i})$ is a quadratic form. We need to show that $q$ is reducible iff $p$ is. This comes from the fact that if we note $x^{\prime}:=(x_{0},\cdots,x_{m},1)$ we have $p=x^{\prime}Ax^{\prime T}$ where $A$ is the Kronecker matrix of $q$ . To go from a factorisation of $q$ to one of $p$ is simply to replace $y$ by $1$ and the other way is only multiplying constant terms of each factor by $y$ .

To conclude, we need to show that these constraints we exhibited are fixed by the theory $\mathfrak{T}$ and can be hardcoded as a sequence into the code of the machine for each harmless predicate in $\mathfrak{T}$ . This means the machine doesn’t have to compute the characteristic polynomial each time but only compute the set of constraint we can deduce of it, this can be done in constant time. Since the polynomial might depend on non-harmless generators they should all be computed by the machine before the harmless predicate, which can be done because, by definition, non-harmless generators only depends on $t-1$ generators. $\hfill\blacktriangleleft$

[bib.bib1] [1] Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Proceedings of LICS, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005129.

[bib.bib2] [2] Samson Abramsky and Luca Reggio. Arboreal categories: An axiomatic theory of resources. Log. Methods Comput. Sci., 19(3), 2023. doi:10.46298/LMCS-19(3:14)2023.

[bib.bib3] [3] Samson Abramsky and Nihil Shah. Relating structure and power: Comonadic semantics for computational resources. J. Log. Comput., 31(6):1390–1428, 2021. doi:10.1093/LOGCOM/EXAB048.

[bib.bib4] [4] John C. Baez, Joe Moeller, and Todd Trimble. 2-rig extensions and the splitting principle. arXiv:2410.05598 [math.CT], 2024.

[bib.bib5] [5] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers. Bulletin of the American Mathematical Society, 21(1):1–46, 1989.

[bib.bib6] [6] Martin Brandenburg. Tensor categorical foundations of algebraic geometry. Ph.d. thesis, University of Münster, 2014.

[bib.bib7] [7] Martin Brandenburg and Alexandru Chirvasitu. Tensor functors between categories of quasi-coherent sheaves. Journal of Algebra, 399:675–692, 2014.

[bib.bib8] [8] Aurelio Carboni, Stephen Lack, and R.F.C. Walters. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra, 84(2):145–198, 1993.

[bib.bib9] [9] Baptiste Chanus and Damiano Mazza. A categorical approach to describing complexity classes. In preparation. Available on the authors’ web page, 2024.

[bib.bib10] [10] Alexandru Chirvasitu and Theo Johnson-Freyd. The fundamental pro-groupoid of an affine 2-scheme. Appl. Categ. Structures, 21(5):469–522, 2013. doi:10.1007/S10485-011-9275-Y.

[bib.bib11] [11] Anuj Dawar, Tomás Jakl, and Luca Reggio. Lovász-type theorems and game comonads. In Proceedings of LICS, pages 1–13. IEEE, 2021. doi:10.1109/LICS52264.2021.9470609.

[bib.bib12] [12] Nikolai Durov. New Approach to Arakelov Geometry. arXiv 0704.2030 [math.AG], 2007.

[bib.bib13] [13] Nikolai Durov. Classifying vectoids and operad kinds. Proc. Steklov Inst. Math., 273:48–63, 2011.

[bib.bib14] [14] Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proccedings, volume 7, pages 43–73, 1974.

[bib.bib15] [15] Erich Grädel and Klaus Meer. Descriptive complexity theory over the real numbers. In Proceedings of STOC, pages 315–324. ACM Press, 1995. doi:10.1145/225058.225151.

[bib.bib16] [16] Neil Immerman. Relational queries computable in polynomial time. Information and Control, 68(1):86–104, 1986. doi:10.1016/S0019-9958(86)80029-8.

[bib.bib17] [17] Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. doi:10.1007/978-1-4612-0539-5.

[bib.bib18] [18] Bart P. F. Jacobs. Categorical Logic and Type Theory, volume 141 of Studies in logic and the foundations of mathematics. North-Holland, 2001.

[bib.bib19] [19] Peter T. Johnstone. Sketches of en Elephant. A Topos Theory Compendium. Volume 2. Oxford University Press, 2002.

[bib.bib20] [20] Melven R. Krom. The decision problem for a class of first-order formulas in which all disjunctions are binary. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 13(1–2):15–20, 1967.

[bib.bib21] [21] Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic. Springer, 1994.

[bib.bib22] [22] Yoàv Montacute and Glynn Winskel. Concurrent games over relational structures: The origin of game comonads. In Proceedings of LICS, pages 58:1–58:14. ACM, 2024. doi:10.1145/3661814.3662075.

Unifying Boolean and Algebraic Descriptive Complexity

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Ultrarings

2.1 Main Definitions

Definition 1.

Lemma 2.

Proof.

Definition 3.

2.2 Examples of Ultrarings

Proposition 4.

Definition 5.

Proposition 6.

Proof.

3 Annular Theories and Models

3.1 Presentations of Ultrarings

Definition 7.

Lemma 8.

Proof.

Definition 9.

Definition 10.

Lemma 11.

Proof.

Proposition 12.

Proof.

3.2 Models and the Canonical Theory

Definition 13.

Definition 14.

Proposition 15.

Proof.

Definition 16.

Theorem 17.

Proof.

3.3 Examples of Annular Theories

4 Computation

4.1 Computability over Ultrarings

Definition 18.

4.2 Capturing Complexity Classes

Definition 19.

Definition 20.

Lemma 21.

Proof.

Theorem 22.

Proof.

5 Discussion and Perspectives

References

Appendix A Appendix

A.1 Proofs of Some Lemmas

Proof of Lemma 2.

Proof of Lemma 8.

Proof of Lemma 11.

A.2 Interpreting Polynomials in a 𝕾-structure

Lemma 23.

Proof.

Proposition 15. [Restated, see original statement.]

Proof.

Theorem 17. [Restated, see original statement.]

Proof.

A.3 Harmless Predicates Over the Real Numbers

Lemma 24.

Proof.

A.2 Interpreting Polynomials in a $\mathfrak{S}$ -structure