A friend of mine and I were talking about computable algebra, and this question came up. The answer may already be known, but I couldn't find it with Google:

Suppose I have a countable field, $k$. Then the Brauer group of $k$, $Br(k)$, is also countable. This means that I can talk about the computability-theoretic complexity of $Br(k)$. Specifically, we can define the spectrum of $Br(k)$, denoted $Sp(Br(k))$, to be the set of degrees computing copies of $Br(k)$: $$Sp(Br(k))=\{X: \exists G\le_T X(G\cong Br(k))\}.$$ My question is, how does the complexity of $Br(k)$ in this sense relate to the complexity of $k$? Specifically:

(1) If $k$ has a computable copy, does $Br(k)$ have a computable copy?

A second question, pointing in the opposite direction:

(2) Is there a field $k$ with a computable copy, such that $Sp(Br(k))$ has a least element which is nonzero?

EDIT: I should point out that this is a strengthening of "has no computable copy": in particular, there are structures with no computable copy, but such that for every noncomputable set $X$, there is a copy $\mathcal{A}$ which does not compute $X$! (This is the "Slaman-Wehner theorem.")

A positive answer to (2) would be a strong negative answer to (1): it would mean that not only does $Br(k)$ not always have to be computable, but we can code some specific non-computable set into $Br(k)$.

Okay, so why would anyone care?

Well, besides just being generally interested in computable algebra, I'm intrigued by the specific obstacles this question faces. Prima facie, the Brauer group $Br(k)$ is quite complicated: its elements are equivalence classes of central simple algebras. This raises a pair of questions, right off the bat:

  • How hard is it to tell that a given (finitely presented) algebra over $k$ is central simple?

  • How hard is it to tell that two central simple algebras are Brauer equivalent?

On the face of it, both of these questions are $\Sigma^1_1$: the former quantifies over ideals, and the latter over isomorphisms. This complexity seems to block any easy approach to getting a positive answer to (1). In fact, my suspicion is that both of these questions are $\Sigma^1_1$-complete, when phrased appropriately.

EDIT: Actually, I overestimated the complexity of the first question: "centrality" is at worst $\Pi^0_2$ ("is there an element not in the field which commutes with everything?"), and "simplicity" is also at worst $\Pi^0_2$ ("is there a nonzero $a$ such that there is no witness to $(a)$ containin 1?"). So "is a (code for a) central simple algebra" is at worst $\Pi^0_2$. Still pretty bad, but vastly better. I suspect now that Brauer equivalence may also be substantially simpler than $\Sigma^1_1$. . .

However, even knowing that each question is as complicated as possible, we would still not have a negative answer to (1); this is because a presentation of $Br(k)$ is just a presentation of $Br(k)$ as an abstract group, and doesn't tell us anything about which elements correspond to what algebras. So conceivably, identifying central simple algebras is $\Sigma^1_1$-complete, but every computable field has a computable Brauer group.

Given that, it seems the best way to get a negative answer to (1) would be to get a positive answer to (2), by coding some specific noncomputable set (let's face it, probably $0'$) into the Brauer group of a computable field. This is the part where, for me, things get really interesting: my limited understanding of algebra suggests that this approach would be extremely difficult. So, in addition to some computability theory and some descriptive set theory, this problem seems to really interact with algebra in a serious way. In particular, to the best of my knowledge computability theory hasn't really been "pointed at" cohomology in a serious way; and this problem looks like a good candidate for that to happen.

  • $\begingroup$ One issue, which may be relevant but which I don't have the necessary background to understand, is that there is a great deal of work around computing various things about Brauer groups; e.g., Kim Nguyen's thesis (duepublico.uni-duisburg-essen.de/servlets/DerivateServlet/…). $\endgroup$ – Noah Schweber May 1 '14 at 19:24
  • $\begingroup$ Does there exist a definition of "a computable copy"? does it mean anything else than, say for an infinite countable field $K$, a structure of field on the positive integers with computable laws, isomorphic to $K$? $\endgroup$ – YCor May 1 '14 at 19:34
  • $\begingroup$ That's it exactly - except (very minor point) it's better to ask for the domain to be an initial segment of the naturals, to allow for finite structures. (And the term is the standard one in the field.) $\endgroup$ – Noah Schweber May 1 '14 at 20:46
  • 2
    $\begingroup$ Your second bullet point includes a subproblem which is much simpler to state, that of deciding which quaternion algebras over the field are isomorphic to matrix algebras, which is equivalent to a certain simple-to-state problem about quadratic bilinear forms having non-trivial zeroes. Surely people know how hard it is to do this computably? $\endgroup$ – Mariano Suárez-Álvarez May 1 '14 at 22:01
  • 2
    $\begingroup$ John Voight studied computational problems for quaternion algebras over number fields in his thesis math.dartmouth.edu/~jvoight/articles/thesis.pdf. He showed for example that deciding whether a given quaternion algebra over $\mathbb{Q}$ is isomorphic to a matrix algebra, is equivalent (in a suitable sense) to the problem of factorisation of integers. So in particular an algorithm does exist, though it is a hard problem in general. $\endgroup$ – Daniel Loughran May 7 '14 at 10:17

At least for a perfect field that is computable and admits a factorization algorithm (i.e., we have an algorithm to factor polynomials over this field), the Brauer group is computable (in the sense that we can compute with its elements — I'm not claiming to know how to compute, e.g., whether it's trivial or not, only whether a given element is trivial or not).

This follows from the fact that every element of the Brauer group of $k$ is torsion, and the $m$-torsion part, for $m$ prime to the characteristic of $k$ (say, $p$), coincides with the Galois cohomology group $H^2(k, \mu_m)$ where $\mu_m$ is the group of $m$-th roots, whereas, if $k$ is perfect, there is no $p$-torsion (where $p$ is the characteristic). For a reference and a proof of these statements, see, for example, Gille & Szamuely's excellent book, Central Simple Algebras and Galois Cohomology, specifically around theorem 4.4.7 and its corollaries (page 99).

So now we can represent an element of the Brauer group by an integer $m$, a Galois extension $K$ of $k$ (the Galois group is then computable: see., e.g., Fried & Jarden, Field Arithmetic, lemma 19.3.2), and a 2-cocycle of the Galois group with values in the $m$-th roots of unity, the latter being a finitary object. Such an object can always be lifted to a bigger (i.e., multiple) $m$ or a larger $K$, and if we have two of them, we can find a common $m$ and $K$ for them. (Also, we can dispense with the $m$ and take the degree $[K:k]$ for it, see corollary 4.4.8 in Gille & Szamuely's book.) For a given level, we can take the product (it is simply the product in the $m$-th roots of unity) and test for triviality (everything is finite, so we just test over the finitely many 1-cochains to see whether the given element is a coboundary; the key point here is that triviality can be tested at the level at which the object is given, because the relative Brauer group $H^2(\mathrm{Gal}(K/k), K^\times)$ of $k \subseteq K$ injects in the absolute Brauer group $H^2(k, k^{\mathrm{sep}\times})$: depending on the definition used for the Brauer group, this is either a triviality or a consequence of the inflation-restriction exact sequence and Hilbert's theorem 90 (3.3.14 and 4.3.7 in Gille & Szamuely)).

Now in the case of a nonperfect field (of characteristic $p$), concerning the $p$-torsion part of the Brauer group, I'm a bit confused as to what happens. From the long exact sequence in cohomology associated to $1 \to k^{\mathrm{sep}\times} \to k^{\mathrm{sep}\times} \to k^{\mathrm{sep}\times}/(k^{\mathrm{sep}\times})^p \to 1$, the $p$-torsion part of the Brauer group coincides with $H^1(k, k^{\mathrm{sep}\times}/(k^{\mathrm{sep}\times})^p)$. Again, we can represent elements of this profinite group cohomology by seeing them at a finite level (given by a separable extension $K$ of $k$), but now the group $k^{\mathrm{sep}\times}/(k^{\mathrm{sep}\times})^p$ (nonzero elements of the separable closure modulo $p$-th powers) is no longer finite. However, because the theory of separably closed fields of given characteristic and given imperfection degree (=Eršov invariant, =cardinality of a $p$-basis) is complete hence decidable (Marker, Messmer & Pillay, Model Theory of Fields, §3 of Messmer's chapter), I suspect that under some reasonable mild assumptions (perhaps "being given a finite p-basis", see prop. 12.4 in this paper by Fabrice Orgogozo and myself) it is possible to decide whether a 1-cocycle is trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.