<p>By Proposition 13 in <a href="https://arxiv.org/abs/2304.09231" rel="noreferrer">Benedikt and Hrushovski</a>, the theory of finite fields has nonelementary complexity (it is harder than <span class="math-container">$k$</span>-times iterated exponential time for all constants <span class="math-container">$k$</span>).</p>
<p>Apparently, the theory is primitive recursive by results of Fried and Sacerdote, <em>Solving diophantine problems over all residue class fields of a number field and all finite fields</em>, Annals of Mathematics 104 (1976), no. 2, 203–233.</p>

CC BY-SA 4.0
2024-06-19T09:26:19.930Z
Thanks. The paper mentions that the problem has a primitive recursive decision procedure. This is of course not a sharp upper bound, but since the paper you mentioned is very recent, I suspect that sharper upper bounds (or lower bounds) are not known.
Reijo Jaakkola
CC BY-SA 4.0
2024-06-19T09:27:04.210Z
Ah, I missed that.
Emil Jeřábek
CC BY-SA 4.0
2024-06-19T09:14:28.277Z
2024-06-19T09:39:01.153Z
2024-06-19T09:39:01.153Z
Emil Jeřábek
<p>Let <span class="math-container">$T_f$</span> denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, <span class="math-container">$T_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}$</span>. It is known that <span class="math-container">$T_f$</span> is decidable. Is anything non-trivial known about its computational complexity?</p>
<p>I know that every non-trivial first-order theory is PSPACE-hard, so the same holds also for <span class="math-container">$T_f$</span>. But I do wonder whether <span class="math-container">$T_f$</span> is known to be harder than this.</p>

CC BY-SA 4.0
2024-06-18T20:44:36.443Z
For a fixed finite field, the existential part of the theory is already NP-complete, and I would guess that the whole FO theory gives you PH. When you say "the first-order theory of finite fields" do you have in mind "for any fixed finite field" or "for any fixed characteristic" or something else?
Joshua Grochow
CC BY-SA 4.0
2024-06-19T04:24:43.057Z
@JoshuaGrochow The theory of any specific finite structure (with more than 2 elements) is PSPACE-complete, see [this old post of mine](https://math.stackexchange.com/questions/3797767/how-complicated-is-the-theory-of-2). The argument [here](https://math.stackexchange.com/a/4176417/28111) shows that we also get PSPACE-complete as a lower bound for the theory of finite fields; I suspect it's not hard to show that that's exact, but I don't immediately see the details.
Noah Schweber
CC BY-SA 4.0
2024-06-19T04:39:15.553Z
Oh yeah, you'd get PH by restricting the number of quantifier alternations in the FO formulae. Makes sense that for unbounded alternations you'd get PSPACE. And for a fixed finite field, it's easy to see that deciding any FO formula is in PSPACE.
Joshua Grochow
CC BY-SA 4.0
2024-06-19T07:47:12.233Z
@JoshuaGrochow I tried to clarify the question. I was indeed thinking about the set of FO sentences true in every finite field (as opposed to the set of FO sentences true in some fixed finite field).
Reijo Jaakkola
CC BY-SA 4.0
2024-06-19T22:08:50.057Z
@ReijoJaakkola Josh's initial comment is still relevant, since $Th(\mathbb{K})$ is at least as complicated as $Th(\mathcal{M})$ for every class of finite structures $\mathcal{K}$ and every $\mathcal{M}\in\mathbb{K}$; the point being that each such $\mathcal{M}$ is pinned down up to isomorphism by a single sentence $\varphi_\mathcal{M}$, and so we can reduce $Th(\mathcal{M})$ to $Th(\mathbb{K})$ via $$\psi\mapsto (\varphi_\mathcal{M}\rightarrow\psi).$$ Of course in this particular case this lower bound happens to be non-optimal (to put it mildly) but that's nontrivial (again, to put it mildly).
Noah Schweber
CC BY-SA 4.0
2024-06-20T07:03:07.683Z
@NoahSchweber But this never gives any nontrivial lower bound, does it? Every theory consistent with $\exists x,y\,x\ne y$ is PSPACE-hard by a direct argument (an obvious reduction from QBF). Since the theory of any finite structure is in PSPACE, the only lower bound it gives is what we already know from the start.
Emil Jeřábek
CC BY-SA 4.0
2024-06-20T09:08:04.240Z
Though this is essentially an instance of a fact that *can* have nontrivial consequences, namely that if a theory $T$ faithfully interprets a theory $S$ in a finite language, then (the set of theorems of) $S$ polynomially reduces to (the set of theorems of) $T$.
Emil Jeřábek
<reference-request><lo.logic>
Computational complexity of the elementary theory of finite fields
Reijo Jaakkola
# Computational complexity of the elementary theory of finite fields

(Asked by: username_0 on 2024-06-18)

Let $T\_f$ denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, $T\_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}$. It is known that $T\_f$ is decidable. Is anything non-trivial known about its computational complexity?

I know that every non-trivial first-order theory is PSPACE-hard, so the same holds also for $T\_f$. But I do wonder whether $T\_f$ is known to be harder than this.

**Tags:** reference-request, lo.logic

> **Comments:**
> **username_1**: For a fixed finite field, the existential part of the theory is already NP-complete, and I would guess that the whole FO theory gives you PH. When you say "the first-order theory of finite fields" do you have in mind "for any fixed finite field" or "for any fixed characteristic" or something else?  
> **username_2**: @JoshuaGrochow The theory of any specific finite structure (with more than 2 elements) is PSPACE-complete, see [this old post of mine](https://math.stackexchange.com/questions/3797767/how-complicated-is-the-theory-of-2). The argument [here](https://math.stackexchange.com/a/4176417/28111) shows that we also get PSPACE-complete as a lower bound for the theory of finite fields; I suspect it's not hard to show that that's exact, but I don't immediately see the details.  
> **username_1**: Oh yeah, you'd get PH by restricting the number of quantifier alternations in the FO formulae. Makes sense that for unbounded alternations you'd get PSPACE. And for a fixed finite field, it's easy to see that deciding any FO formula is in PSPACE.  
> **username_0**: @JoshuaGrochow I tried to clarify the question. I was indeed thinking about the set of FO sentences true in every finite field (as opposed to the set of FO sentences true in some fixed finite field).  
> **username_2**: @ReijoJaakkola Josh's initial comment is still relevant, since $Th(\mathbb{K})$ is at least as complicated as $Th(\mathcal{M})$ for every class of finite structures $\mathcal{K}$ and every $\mathcal{M}\in\mathbb{K}$; the point being that each such $\mathcal{M}$ is pinned down up to isomorphism by a single sentence $\varphi_\mathcal{M}$, and so we can reduce $Th(\mathcal{M})$ to $Th(\mathbb{K})$ via $$\psi\mapsto (\varphi_\mathcal{M}\rightarrow\psi).$$ Of course in this particular case this lower bound happens to be non-optimal (to put it mildly) but that's nontrivial (again, to put it mildly).  
> **username_3**: @NoahSchweber But this never gives any nontrivial lower bound, does it? Every theory consistent with $\exists x,y\,x\ne y$ is PSPACE-hard by a direct argument (an obvious reduction from QBF). Since the theory of any finite structure is in PSPACE, the only lower bound it gives is what we already know from the start.  
> **username_3**: Though this is essentially an instance of a fact that *can* have nontrivial consequences, namely that if a theory $T$ faithfully interprets a theory $S$ in a finite language, then (the set of theorems of) $S$ polynomially reduces to (the set of theorems of) $T$.  

---

## 1 answers

### Answer by username_3 on 2024-06-19. Score: 6 | Accepted answer

By Proposition 13 in [Benedikt and Hrushovski](https://arxiv.org/abs/2304.09231), the theory of finite fields has nonelementary complexity (it is harder than $k$-times iterated exponential time for all constants $k$).

Apparently, the theory is primitive recursive by results of Fried and Sacerdote, *Solving diophantine problems over all residue class fields of a number field and all finite fields*, Annals of Mathematics 104 (1976), no. 2, 203–233.

> **Comments:**
> **username_0**: Thanks. The paper mentions that the problem has a primitive recursive decision procedure. This is of course not a sharp upper bound, but since the paper you mentioned is very recent, I suspect that sharper upper bounds (or lower bounds) are not known.  
> **username_3**: Ah, I missed that.  

---

