\AtBeginEnvironment

algorithmic

Efficient computations in central simple algebras using Amitsur cohomology

Péter Kutas Faculty of Informatics, Eötvös Loránd University and School of Computer Science, University of Birmingham (https://sites.google.com/view/peterkutas89). The first author is supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Quantum Information National Laboratory Program, the János Bolyai Research Scholarship of the Hungarian Academy of Sciences and by the UNKP-22-5 New National Excellence Program. The first author is also partly supported by EPSRC through grant number EP/V011324/1. Mickaël Montessinos Institute of Mathematics, Faculty of Mathematics and Informatics, Vilnius University (http://mickael.montessinos.fr).

Abstract

We introduce a presentation for central simple algebras over a field $k$ using Amitsur cohomology. We provide efficient algorithms for computing a cocycle corresponding to any such algebra given by structure constants. If $k$ is a number field, we use this presentation to prove that the explicit isomorphism problem (i.e., finding an isomorphism between central simple algebras given by structure constants) reduces to $S$ -unit group computation and other related number theoretical computational problems. This also yields, conditionally on the generalised Riemann hypothesis, the first polynomial quantum algorithm for the explicit isomorphism problem over number fields.

1 Introduction

The explicit isomorphism problem is the algorithmic problem of, given a field $k$ and a $k$ -algebra $A$ isomorphic to $M_{d}(k)$ , constructing an explicit isomorphism $\varphi\colon A\to M_{d}(k)$ . The explicit isomorphism problem may be thought of as a natural problem in computational representation theory. Given a $k$ -algebra $A$ , one may wish to assay it. That is, compute the Jacobson radical of $A$ , and the decomposition of the semi-simple quotient of $A$ as a sum of simple $k$ -algebras, themselves identified to some $M_{d}(D)$ , for $D$ a division $k$ -algebra. In general, the hard part of this task is to find an isomorphism $A\to M_{n}(D)$ when $A$ is simple. A general recipe for solving this problem is to identify the Brauer class of $D$ over its centre $K/F$ , find structure constants for $M_{n}(D^{op})$ and then compute an explicit isomorphism $A\otimes M_{n}(D^{op})\simeq M_{m}(K)$ [37, 32, 20].

Applications of the explicit isomorphism problem go beyond the mere computational theory of finite-dimensional associative algebras. In arithmetic geometry, the problem is relevant for trivialising obstruction algebras in explicit descent over elliptic curves [16, 17, 18, 26] and computation of Cassel-Tate pairings [28, 49]. The problem is also connected to the parametrisation of Severi-Brauer surfaces [21]. Recent work in algebraic complexity theory reduced the determinant equivalence test to the explicit isomorphism problem [30]. Finally, the explicit isomorphism problem over the function field $\mathbb{F}_{q}(T)$ is also relevant to error correcting codes [32].

It is well known that the Brauer group of equivalence classes of central simple $k$ -algebras may be described as the second Galois cohomology group $H^{2}(k,k_{sep}^{\times})$ . The remarkable fact that these two groups are isomorphic may be seen as a consequence of the crossed-product presentation of central simple algebras containing a maximal commutative subalgebra which is a Galois extension of the base field.

When a cohomological presentation is known for a certain algebra, the explicit isomorphism problem translates into a multiplicative algebraic equation. Indeed, the algebra is represented by a cocycle, and since the algebra is split, the cocycle is a coboundary. Then, an explicit isomorphism to a matrix algebra may be computed using a cochain whose differential is this coboundary. When the base field is a number field and a presentation of the algebra (either a cyclic or a crossed product presentation) is known, the resulting equation may be solved by computing a certain group of $S$ -units [46, 25].

Before Noether introduced crossed-product algebras, Brauer had already introduced a factor set presentation which allowed to describe an algebra with the knowledge of any maximal commutative subalgebra, not necessarily a Galois extension of the base field. We refer the reader to [38] for a modern description of presentations introduced in the works of Brauer and Noether. It is interesting to note that Adamson developed a cohomology theory for non-Galois field extensions which describes Brauer factor sets as cocycles [1], much like classical Galois cohomology describes Noether factor sets as cocycles.

A line of work introduced Azumaya algebras, which generalise the notion of central simple algebra (and therefore of the Brauer group) over arbitrary rings [4, 3], and then later over schemes (see [15] for a modern treatment). While trying to connect the usual Galois cohomological description of the Brauer group and another description introduced by Hochschild, Amitsur came upon an exact complex which yields a cohomology theory suitable to classify central simple algebras, the so-called Amitsur cohomology. As the complex he defined may be constructed over arbitrary rings, a line of work generalised his classification result to Azumaya algebras over increasingly general classes of ring extensions [2, 45, 12].

Cohomological presentations have the potential of being used both for a computational representation of a central simple algebra and for solving the explicit isomorphism problem. For instance, in the computer algebra system PARI/GP [47], central simple algebras over a number field may be represented as cyclic algebras. While the already existing constructions relying on Amitsur cohomology are abstract and do not lend themselves easily to a practical implementation, the crossed product and cyclic presentations have the inconvenient that one is required to know a Galois, or even cyclic, maximal subfield in order to convert a given algebra into these presentations. While such a subfield always exists for algebras over global fields (as per the Brauer-Hasse-Noether theorem), there is no known efficient algorithm to find one (except for quaternion and degree 3 central simple algebras) to the best of our knowledge. The presentation using Brauer factor sets may be constructed using an arbitrary maximal commutative subalgebra, which is easy to find, but factor sets take value in a normal splitting field of the subalgebra used. Results in arithmetic statistics [23] suggest that a random element of such an algebra will generate a maximal subfield whose Galois group is the full symmetric group, and hence will have a Galois closure of degree $n!$ (where $n$ is the degree of the algebra), preventing it to be used efficiently in a computation.

1.1 Our contributions

In Section 3, we give a presentation for central simple algebras over a field using Amitsur cocycles. Our presentation only requires knowledge of a separable maximal commutative subalgebra, which may be found efficiently in deterministic polynomial time [22]. Furthermore, multiplication in our representation may be computed using $O(n^{3})$ base field multiplications, making it as efficient as the naive representation using structure constants. In Section 3.1 we construct a central simple algebra from an Amitsur $2$ -cocycle. In Section 3.2, we discuss the computational representation of Amitsur cocycles and related algebras. Finally, in Section 3.3 we give an efficient algorithm for computing a cocycle representing a given central simple algebra.

In Section 4, we prove that over a number field, an Amitsur $1$ -cochain whose differential is a given $2$ -coboundary may be found within a certain group of $S$ -units. We then prove that, assuming the generalised Riemann hypothesis (henceforth denoted by GRH), the explicit isomorphism problem is solved by a polynomial quantum algorithm.

1.2 Related works

Below, we review existing classical algorithms for solving the explicit isomorphism problem over various fields.

In the case of a finite base field, a polynomial-time algorithm was introduced by Ronyai in [44].

Instances of the problem for $\mathbb{Q}$ -algebras isomorphic to $M_{n}(\mathbb{Q})$ were first treated separately for small values of $n$ . When $n=2$ , the problem reduces to finding a rational point on a projective conic [48, Theorem 5.5.4], which is solved for instance in [19]. Then, [21] presented a subexponential algorithm when $n=3$ by finding a cyclic presentation and solving a cubic norm equation. The case $n=4$ is tackled in [43] by reducing to the case of quaternion algebras over $Q$ and $\mathbb{Q}(\sqrt{d})$ and solving a norm equation.

In [18] an algorithm was given and studied mostly for the cases $n=3$ and $n=5$ . It was then generalised in [37, 36] to a $K$ -algebra isomorphic to $M_{n}(K)$ , where $n$ is a natural number and $K$ is a number field. The complexity of this last algorithm is polynomial in the size of the structure constants of the input algebra, but depends exponentially on $n$ , the degree of $K$ and the size of the discriminant of $K$ .

In 2018, [34] exhibited a polynomial-time algorithm for algebras isomorphic to $M_{n}(\mathbb{F}_{q}(T))$ .

For the case of fixed $n$ and varying base field, [27, 39] independently gave an algorithm for an algebra isomorphic to $M_{2}(\mathbb{Q}(\sqrt{d}))$ with complexity polynomial in $\log(d)$ . A similar algorithm for quadratic extensions of $\mathbb{F}_{q}(T)$ was given in [35] for the case of odd $q$ . The case of even $q$ was then treated in [40].

2 Preliminaries

2.1 Algorithmic preliminaries

2.1.1 Computational model

The theoretical results of Section 3 are valid for any base field $k$ . In order to translate them into efficient algorithms, it is necessary to have an encoding of the elements of $k$ , for which the usual field operations and linear algebraic tasks may be performed efficiently. Following [22], we say that such a field admits efficient linear algebra. It is well known that finite fields and global fields, among others, admit efficient linear algebra.

2.1.2 Computational representations of algebras

A $k$ -algebra may be given as input to a program in the form of a table of structure constants. Let $A$ be a finite dimensional $k$ -algebra of dimension $n$ , let $V$ be the underlying vector space of $A$ and let $(e_{1},\ldots,e_{n})$ be a basis of $V$ . Multiplication in $A$ is a bilinear map which may be represented as a tensor $\lambda\in V^{\vee}\otimes V^{\vee}\otimes V$ . The table of structure constants of $A$ for the basis $(e_{1},\ldots,e_{n})$ is then the coordinates of $\lambda$ in the basis $\left(e_{i}^{\vee}\otimes e_{j}^{\vee}\otimes e_{k}\right)$ of $V^{\vee}\otimes V^{\vee}\otimes V$ , where $\left(e_{i}^{\vee}\right)$ is the basis of $V^{\vee}$ dual to $(e_{i})$ .

An $F$ -algebra $A\cong M_{d}(k)$ may be presented as a cyclic algebra [31, Section 2.5] or as a crossed-product algebra [38, Section 2.6]. It follows readily from the algebraic constructions that, computationally, knowing a cyclic (resp. crossed-product) presentation of a central simple $F$ -algebra $A$ of degree $d$ is equivalent to knowing an embedding $F\to A$ , where $F/k$ is a cyclic (resp. Galois) extension of $k$ of degree $d$ .

Field extensions and étale algebras admit a presentation as a quotient ring $k[x]/(P(x))$ , for some $P\in k[x]$ . As a result, their elements are represented as residue classes of polynomials. The question of tensor products of such algebras is discussed below in Section 3.2.

2.1.3 Computing rings of integers and factoring ideals

The ability to factor integers in polynomial time yields polynomial quantum algorithms for several tasks of computational number theory. We list some auxiliary results that will be needed later on:

Fact 2.1.

There exists a polynomial-time quantum algorithm for computing the maximal order in number fields.

Proof.

Zassenhaus’ round 2 algorithm [13, Algorithm 6.1.8] computes the maximal order of a number field in polynomial time, provided an oracle for factoring. Thus, one may deduce a polynomial quantum algorithm for computing maximal orders in number fields.

∎

Fact 2.2.

There exists a polynomial-time quantum algorithm [14, Algorithm 2.3.22] for factoring ideals in number fields.

2.1.4 A polynomial quantum algorithm for computing class groups and groups of $S$ -units in number fields

The class group of $L$ , denoted by $Cl(L)$ is the group of fractional ideals modulo principal ideals. The units in $\mathbb{Z}_{L}$ form a group which is called the unit group and is denoted by $U_{L}$ . All these are important objects in number theory and they motivate the following three algorithmic problems:

1.

Compute generators of $Cl(L)$ and their relations,
2.

Compute generators of $U_{L}$ ,
3.

Given a principal ideal $I$ , find a generator element of $I$ .

To the best of our knowledge, there only exist polynomial-time classical algorithms for these problems in very special cases. In [7] the authors propose a subexponential heuristic algorithm for computing class groups and unit groups for arbitrary degree number fields. In [6] and [8] the authors propose subexponential heuristic algorithms for the principal ideal problem for a certain subclass of number fields (multiquadratic extensions of $\mathbb{Q}$ and power-of-two cyclotomic fields).

Hallgren [33] first proposed a polynomial-time quantum algorithm for computing the class group and unit group for bounded degree number fields, where GRH is assumed for computing generators of the class group. Later, polynomial-time algorithms were proposed (under GRH for the computation of the class group) for these tasks for arbitrary number fields [24],[9]. Furthermore, [9] also provides a polynomial-time quantum algorithm for computing generators of principal ideals (dubbed the principal ideal problem). In the class group computation, GRH is required to provide a polynomially sized generating set of the class group. Bach [5] proved that, assuming GRH, the class group can be generated by prime ideals whose norm is at most $48\log^{2}|\Delta_{K}|$ where $\Delta_{K}$ is the discriminant of the number field. We summarise this discussion into the following facts:

Fact 2.3 ([9, Fact 4.1]).

Let $K$ be a number field and $\Delta_{K}$ its discriminant. Under GRH, there exists a polynomial-time algorithm computing a generator set of $Cl(K)$ of size polynomial in $\log(|\Delta_{K}|)$ .

Proof.

Using the Bach bound one simply enumerates all prime ideals of norm bounded by $12\log^{2}(|\Delta_{K}|)$ . The number of such prime ideals is polynomial in $\log(|\Delta_{K}|)$ . ∎

Fact 2.4.

Assuming GRH, there exists a polynomial-time quantum algorithm [9] for computing the class group of a number field.

Fact 2.5.

[[9, Theorem 1.1]] Let $S$ be a set of prime ideals of a number field $K$ . There exists a polynomial-time quantum algorithm for computing generators of the group of $S$ -units (polynomial in the size of $S$ ).

One application of $S$ -unit computation (mentioned in [9] and [46]) is that one can compute solutions to norm equations in Galois extensions. Let $L|K$ be a Galois extension of number field and let $a\in K$ . Then one would like to find a solution to $N_{L|K}(x)=a$ (or show that it does not exist). The main result by Simon is the following:

Fact 2.6.

([46, Theorem 4.2]) Let $L|K$ be a Galois extension of number fields. Let $S_{0}$ be a set of primes generating the relative class group $Cl_{i}(L|K)$ . Let $S$ be a set of primes containing $S_{0}$ and let us denote the set of $S$ -units in $L$ by $U_{L,S}$ and the set of $S$ -units in $K$ by $U_{K,S}$ . Then one has that:

N_{L|K}(U_{L,S})=N_{L|K}(L^{*})\cap U_{K,S}

Informally, this means that for Galois extensions one can search for $x$ in the group of $S$ -units. Then by factoring $S$ and computing the class group of $L$ one can turn finding $x$ into solving a system of linear equations. Thus, computing $S$ -units implies a polynomial quantum algorithm for solving norm equations in Galois extensions. One important issue though is that the size of $S_{0}$ has to polynomially bounded as the complexity could explode if $S_{0}$ was too large. If one assumes GRH, then [5] implies that the size of $S_{0}$ is not too large.

We summarise this discussion into the following theorem:

Theorem 2.7.

Let $L|K$ be a Galois extension of number fields and let $S$ be a set of primes of $L$ . Then there exists a polynomial-time quantum algorithm that computes a set of generators for the group of $S$ -units of $L$ . Furthermore, let $a\in K$ . Then there exists a polynomial-time quantum algorithm (assuming GRH) for solving the norm equation $N_{L|K}(x)=a$ .

2.2 Brauer factor sets and central simple algebras

For the remainder of this section, we fix a field $k$ , a separable polynomial $P\in k[X]$ of degree $d$ and an étale algebra $F=k[X]/P$ over $k$ . We let $K$ be the smallest Galois extension of $k$ which splits $F$ , and set $G=\operatorname{Gal}(K/k)$

We will introduce definitions that are equivalent to those of Adamson cohomology [1] with values in the multiplicative group. However, while Adamson cohomology is normally defined for separable field extensions, we extend our definitions to étale algebras. One difference is that cochains are indexed by $k$ -algebra morphisms which are not necessarily injective. We may then use well-known results on Brauer factor sets to establish a cohomological description of the Brauer group (see [38, Chapter 3] for a modern reference).

Let $\Phi$ be the set of $k$ -algebra morphisms from $F$ to $K$ .

Lemma 2.8.

The map $\varphi\mapsto\varphi(X)$ is a bijection between $\Phi$ and the set of roots of $P$ in $K$ . In particular, the set $\Phi$ has $d$ elements.

Proof.

If $\varphi\in\Phi$ , it is clear that $\varphi(X)$ is a root of $P$ in $K$ . Now, the morphism $\varphi$ is entirely determined by $\varphi(X)$ so the map $\varphi\mapsto\varphi(X)$ is injective.

Let $r\in K$ be a root of $P$ . Then, let $Q$ be the unique irreducible factor of $P$ such that $Q(r)=0$ . Then, $F\simeq k[X]/Q\oplus k[X]/(P/Q)$ and we have a map from $k[X]/Q\oplus k[X]/(P/Q)$ to $k[X]/Q$ sending $(A(X),B(X))$ to $A(r)$ . This maps precomposed with the isomorphism defined above sends $X$ to $r$ . ∎

We may then index the maps from $F$ to $K$ , so that $\Phi=\{\varphi_{1},\ldots,\varphi_{d}\}$ . If $i\in[d]$ and $g\in G$ , we write $gi$ for the index of $g\varphi_{i}$ .

Definition 2.9.

Let $n\in\mathbb{N}$ . An $n$ -cochain is a map

a:\begin{array}[]{ccl}\Phi^{n+1}&\to&K^{\times}\\ (\varphi_{i_{0}},\ldots,\varphi_{i_{n}})&\mapsto&a_{i_{0},\ldots,i_{n}}\end{array}

which satisfies the following homogeneity condition: for $i_{0},\ldots,i_{n}\in[d]$ , for $g\in G$ ,

ga_{i_{0},\ldots,i_{n}}=a_{gi_{0},\ldots,gi_{n}}

(1)

A cochain $a$ may be denoted as the family $(a_{i_{0},\ldots,i_{n}})_{i_{0},\ldots,i_{n}\in[d]}$ of values that it takes over $\Phi^{n+1}$ .

A cochain is said to be reduced if $a_{i,\ldots,i}=1$ for all $i\in[d]$ . Under pointwise multiplication, the $n$ -cochains form a group which we denote by $C^{n}(k,F)$ . Then, the reduced cochains form a subgroup denoted by $C^{\prime n}(k,F)$ .

If $a\in C^{n}(k,F)$ and $i_{0},\ldots,i_{n+1}\in[d]$ , we set

a_{i_{0},\ldots,\widehat{i_{k}},\ldots,i_{n+1}}\coloneqq a_{i_{0},\ldots,i_{k-1},i_{k+1},\ldots,i_{n+1}}.

For $n\in\mathbb{N}$ , there is a group homomorphism $\Delta^{n}\colon C^{n}(k,F)\to C^{n+1}(k,F)$ defined as follows: if $a\in C^{n}(k,F)$ ,

\Delta^{n}(a)_{i_{0},\ldots,i_{n+1}}=\prod_{k=0}^{n+1}a_{i_{0},\ldots,\widehat{i_{k}},\ldots,i_{n}}^{(-1)^{k}}.

We set $Z^{n}(k,F)=\operatorname{Ker}(\Delta^{n})$ and call elements of this subgroup $n$ -cocycles. We write $Z^{\prime n}(k,F)$ for the group of reduced cocycles. For $n$ positive, we also set $B^{n}(k,F)=\operatorname{Im}(\Delta^{n-1})$ and call its elements $n$ -coboundaries. We note that $B^{n}(k,F)$ is a subgroup of $Z^{n}(k,F)$ . For completeness, we let $B^{0}(k,F)$ be the trivial subgroup of $Z^{0}(k,F)$ . Finally, we set $H^{n}(k,F)=Z^{n}(k,F)/B^{n}(k,F)$ .

Two cocycles $c_{1},c_{2}\in Z^{n}(k,F)$ are called associated, denoted by $c_{1}\sim c_{2}$ , if they have the same class in $H^{n}(k,F)$ . If $b\in B^{n+1}(k,F)$ , a preimage of $b$ by $\Delta^{n}$ is called a trivialisation of $b$ .

Remark 2.10.

The cochain $(1)_{i,j,k\in[d]}$ is always a cocycle and is a coboundary for $n\geq 1$ . It is called the trivial cocycle.

Proposition 2.11.

For $n$ positive, every $n$ -cocycle is associated to a reduced cocycle.

Proof.

Let $c\in Z^{n}(k,F)$ , and consider the cochain $a\in C^{n-1}(k,F)$ defined by $a_{i,\ldots,i}=c_{i,\ldots,i}^{-1}$ and $a_{i_{0},\ldots,i_{n-1}}=1$ if the $i_{k}$ are not all equal to one another. Then, the cocycle $c\Delta^{n-1}(a)$ is reduced and associated to $c$ . ∎

We may now recall the explicit description of the isomorphism $H^{2}(k,F)\simeq Br(F/k)$ (that is, the group of Brauer classes of central simple $k$ -algebras that are split by $F$ ), as exposed in [38, Chapter 2]. Using Lemma 2.8, we observe that what is called a Brauer factor set there is a $2$ -cocycle in our notation.

Definition 2.12.

Let $c\in Z^{\prime 2}(k,F)$ . Let $B(F,c)$ be the $k$ -vector space of $G$ -homogeneous maps from $\Phi^{2}$ to $K$ . We turn $B(F,c)$ into a $k$ -algebra using the following definition. If $\ell,\ell^{\prime}\in B(F,c)$ , we set $\ell\ell^{\prime}=\ell^{\prime\prime}$ such that for all $i,j\in[d]$ ,

\ell^{\prime\prime}_{i,j}=\sum_{k=1}^{d}\ell_{i,k}c_{i,k,j}\ell^{\prime}_{k,j}.

Fact 2.13.

If $c$ is a $2$ -cocycle, the $k$ -algebra $B(F,c)$ is a central simple $k$ -algebra. Furthermore, if $c_{1}$ and $c_{2}$ are associated cocycles, and $a$ is a $1$ -cochain such that $c_{2}=\Delta^{1}(a)c_{1}$ , then the map

\begin{array}[]{ccl}B(F,c_{1})&\to&B(F,c_{2})\\ (m_{i,j})_{i,j\in[d]}&\mapsto&(m_{i,j}a_{i,j}^{-1})_{i,j\in[d]}\end{array}

is an isomorphism. Conversely, if $A$ is a central simple $k$ -algebra split by $F$ , then there exists a cocycle $c\in Z^{2}(k,F)$ such that $A\simeq B(F,c)$ If $c_{1},c_{2}\in Z^{\prime 2}(k,F)$ are such that $B(F,c_{1})$ and $B(F,c_{2})$ are isomorphic algebras, then the cocycles $c_{1}$ and $c_{2}$ are associated.

Proof.

This is essentially the content of [38, Theorem 2.5.6]. While the result is stated in the source for reduced factor sets, we note that the isomorphism constructed in [38, Theorem 2.3.21] is valid even for non-reduced associated cocycles. Then, the results stated here extend to non-reduced cocycle by 2.11. ∎

Remark 2.14.

We note that if $c_{1},c_{2}\in Z^{\prime n}(k,F)$ are associated and both reduced, then a cochain $a\in C^{n-1}(k,F)$ such that $c_{1}=\Delta^{n-1}(a)c_{2}$ must be reduced as well.

We refer the reader to [38, Section 2.3] for the detailed construction of a Brauer factor-set associated to a given central simple algebra, and we give a brief description below: Let $A$ be a central simple $k$ -algebra, and let $F$ be a separable maximal commutative subalgebra of $A$ . Then, there exists $v\in A$ such that $A=FvF$ . Furthermore, letting $K$ be a Galois extension of $k$ which splits $F$ , there is a map $A\to M_{d}(K)$ such that every $u\in F$ is mapped to $\operatorname{Diag}(\phi_{1}(x),\ldots,\phi_{d}(x))$ . Let $(v_{ij})_{i,j\in[d]}$ be the image of $v$ in $M_{d}(K)$ . Then, every element $uvu^{\prime}$ of $A$ becomes a matrix of the form $(\ell_{ij}v_{ij})_{i,j\in[d]}$ , where $\ell_{ij}=\phi_{i}(u)\phi_{j}(u^{\prime})$ . The map $uvu^{\prime}\mapsto(\ell_{ij})_{i,j\in[d]}$ gives an isomorphism from $A$ to $B(F,c)$ , where $c_{ijk}\coloneqq v_{ik}v_{kj}v_{ij}^{-1}$ .

3 Explicit computations with Amitsur cohomology

In this section, we recall the basic definitions of Amitsur cohomology and then use them to get efficient representations of cocycles as introduced in Section 2.2. We also keep notations as they were in Section 2.2.

Although the Amitsur complex and its cohomology are defined for general commutative rings, we will only need to state the definitions over fields and étale algebras. We refer to [29, Chapter 5] for more general definitions and results.

Unless specified otherwise, all tensor products are taken over $k$ , and by $F^{\otimes n}$ we mean the tensor product of $n$ copies of the $k$ -algebra $F$ .

Definition 3.1.

An $n$ -cochain in the sense of Amitsur is an invertible element in the $k$ -algebra $F^{\otimes n+1}$ , and we write $C_{Am}^{n}(k,F)$ for the group of $n$ -cochains.

For $n\in\mathbb{N}$ and $0\leq i\leq n+1$ , we define a $k$ -algebra homomorphism $\varepsilon_{i}^{n}$ from $F^{\otimes n+1}$ to $F^{\otimes n+2}$ . The map $\varepsilon_{i}^{n}$ is defined on the simple tensor elements as follows:

\varepsilon_{i}^{n}(f_{0}\otimes\ldots\otimes f_{n})=f_{0}\otimes\ldots\otimes f_{i-1}\otimes 1\otimes f_{i}\otimes\ldots\otimes f_{n}.

We then define the group homomorphism

\Delta_{Am}^{n}\colon\begin{array}[]{ccl}C_{Am}^{n}(k,F)&\to&C_{Am}^{n+1}(k,F)\\ a&\mapsto&\prod_{i=0}^{n+1}\varepsilon_{i}^{n}(a)^{(-1)^{i}}\end{array}.

Define the subgroup $Z_{Am}^{n}(k,F)=\operatorname{Ker}(\Delta_{Am}^{n})$ of $C_{Am}^{n}(k,F)$ , and its elements are called $n$ -cocycles in the sense of Amitsur.

If $n$ is positive, we also define the subgroup $B_{Am}^{n}(k,F)=\operatorname{Im}(\Delta_{Am}^{n-1})$ of $Z_{Am}^{n}(k,F)$ and its elements are $n$ -coboundaries in the sense of Amitsur. Then, the $n$ th Amitsur cohomology group $H_{Am}^{n}(k,F)$ is defined as the quotient group $Z_{Am}^{n}(k,F)/B_{Am}^{n}(k,F)$ .

Two $n$ -cocycles $c_{1}$ and $c_{2}$ are called associated if they have the same class in $H_{Am}^{n}(k,F)$ . If $b\in B^{n}_{Am}(k,F)$ , a cochain $a\in C^{n-1}_{Am}(k,F)$ such that $\Delta_{Am}^{n-1}(a)=c$ is called a trivialisation of $c$ .

3.1 Amitsur cohomology and central simple algebras

The first result we need to leverage Amitsur cohomology in representing Brauer factor sets is the following

Lemma 3.2.

Consider the map $\Psi_{n}$ from $F^{\otimes n+1}$ to the algebra of $G$ -homogeneous maps from $\Phi^{n+1}$ to $K$ , which is defined over simple tensors by

f_{0}\otimes\ldots\otimes f_{n}\mapsto\left(\begin{array}[]{ccl}\Phi^{n+1}&\to&K\\ (\varphi_{i_{0}},\ldots,\varphi_{i_{n}})&\mapsto&\prod_{j=0}^{n}\varphi_{i_{j}}(f_{j})\end{array}\right).

The map $\Psi$ is an isomorphism of $k$ -algebras, which also sends the unit group $C_{Am}^{n}(k,F)$ onto the unit group $C^{n}(k,F)$ . Furthermore, $\Psi_{n+1}\circ\Delta_{Am}^{n}=\Delta^{n}\circ\Psi_{n}$ , and it follows that cocycle and coboundaries subgroup are also isomorphic to one another, and so are cohomology groups.

Proof.

If $F$ is a separable field extension of $k$ , this is the content of [45, Section 2]. However, the proof given there readily generalises to the case that $F$ is an étale $k$ -algebra. ∎

If $(\varphi_{i_{0}},\ldots,\varphi_{i_{n}})\in\Phi^{n+1}$ , we get a homomorphism of $k$ -algebras

\begin{array}[]{ccc}F^{\otimes n+1}&\to&K\\ a_{0}\otimes\ldots\otimes a_{n}&\mapsto&\prod_{j=0}^{n}\varphi_{i_{j}}(a_{j})\end{array}

By the construction of $\Psi$ , if $a\in F^{\otimes n+1}$ and $(\varphi_{i_{0}},\ldots,\varphi_{i_{n}})\in\Phi^{n+1}$ , then we get

\Psi_{n}(a)_{i_{0},\ldots,i_{n}}=(\varphi_{i_{0}},\ldots,\varphi_{i_{n}})(a).

(2)

Adapting Definition 2.12 to Amitsur cohomology, we get:

Definition 3.3.

Let $c\in Z_{Am}^{2}(k,F)$ be a cocycle. The $k$ -algebra $A(F,c)$ is defined as follows:

As a $k$ -vector space, $A(F,c)$ is $F^{\otimes 2}$ . We see $F^{\otimes 3}$ as a $F^{\otimes 2}$ -algebra via the embedding $\varepsilon_{1}^{1}\colon F^{\otimes 2}\to F^{\otimes 3}$ . Then, multiplication in $A(F,c)$ is defined by

aa^{\prime}=\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}\left(\varepsilon_{2}^{1}(a)c\varepsilon_{0}^{1}(a^{\prime})\right).

In the sequel, we use the same embedding whenever we write $\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}$ .

Observe that the algebra $F^{\otimes 3}/F^{\otimes 2}$ may be seen as the extension of scalars to $F^{\otimes 2}$ of the $k$ -algebra $F$ . Since we make the choice of seeing $F^{\otimes 3}$ as a $F^{\otimes 2}$ -algebra via the mapping $\varepsilon_{1}^{2}$ , the relevant injection $F\to F^{\otimes 3}$ sends an element $a\in F$ to $1\otimes a\otimes 1$ . Then, by [10, Section III.9.3], for $a\in F$ , we have

\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(1\otimes a\otimes 1)=\operatorname{Tr}_{F/k}(a)(1\otimes 1).

By linearity of the trace, if $a=\sum_{i\in I}a_{i0}\otimes a_{i1}\otimes a_{i2}\in F^{\otimes 3}$ , we get

\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(a)=\sum_{i\in I}\operatorname{Tr}_{F/k}(a_{i1})(a_{i0}\otimes a_{i2}).

Proposition 3.4.

Let $c\in Z_{Am}^{2}(k,F)$ . The map $\Psi_{1}$ is a $k$ -algebra isomorphism from $A(F,c)$ to $B(F,\Psi_{2}(c))$ .

Proof.

The map $\Psi_{1}$ is already known to be an isomorphism of vector space between $A(F,c)$ and $B(F,\Psi_{2}(c))$ , as the underlying vector spaces of these algebras are respectively $F^{\otimes 2}$ and the space of $G$ -homogeneous maps from $\Phi^{2}$ to $K$ . We therefore only need to check that the map $\Psi_{1}$ is a homomorphism of $k$ -algebras.

It is well known that if $a\in F$ , $\operatorname{Tr}_{F/k}(a)=\sum_{\ell\in[d]}\varphi_{\ell}(a)$ . Then, if $a=a_{0}\otimes a_{1}\otimes a_{2}\in F^{\otimes 3}$ and $i,j\in[d]$ , we get:

	$\displaystyle(\varphi_{i},\varphi_{j})\left(\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(a)\right)$	$\displaystyle=(\varphi_{i},\varphi_{j})\left(\operatorname{Tr}_{F/k}(a_{1})(a_{0}\otimes a_{2})\right)$
		$\displaystyle=(\varphi_{i},\varphi_{j})\left(\sum_{\ell\in[d]}\varphi_{\ell}(a_{1})(a_{0}\otimes a_{2})\right)$
		$\displaystyle=\sum_{\ell\in[d]}\varphi_{i}(a_{0})\varphi_{\ell}(a_{1})\varphi_{j}(a_{2})$
		$\displaystyle=\sum_{\ell\in[d]}(\varphi_{i},\varphi_{\ell},\varphi_{j})(a_{0}\otimes a_{1}\otimes a_{2}).$

Extending this result by linearity, we get that

(\varphi_{i},\varphi_{j})\circ\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}=\sum_{\ell\in[d]}(\varphi_{i},\varphi_{\ell},\varphi_{j}).

We also note that if $a\in F^{\otimes 2}$ , then by Equation 2 we get

(\varphi_{i},\varphi_{\ell},\varphi_{j})(\varepsilon_{2}^{1}(a))=(\varphi_{i},\varphi_{\ell})(a)=\Psi_{1}(a)_{i,\ell}.

Likewise,

(\varphi_{i},\varphi_{\ell},\varphi_{j})(\varepsilon_{0}^{1}(a))=\Psi_{1}(a)_{\ell,j}.

Now, using Equation 2 again, we get that if $a,a^{\prime}\in A(F,c)$ and $i,j\in[d]$ ,

	$\displaystyle\Psi_{1}(aa^{\prime})_{i,j}$	$\displaystyle=(\varphi_{i},\varphi_{j})\left(\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}\left(\varepsilon_{2}^{1}(a)c\varepsilon_{0}^{1}(a^{\prime})\right)\right)$
		$\displaystyle=\sum_{\ell\in[d]}(\varphi_{i},\varphi_{\ell},\varphi_{j})\left(\varepsilon_{2}^{1}(a)c\varepsilon_{0}^{1}(a^{\prime})\right)$
		$\displaystyle=\sum_{\ell\in[d]}(\varphi_{i},\varphi_{\ell},\varphi_{j})(\varepsilon_{2}^{1}(a))(\varphi_{i},\varphi_{\ell},\varphi_{j})(c)(\varphi_{i},\varphi_{\ell},\varphi_{j})(\varepsilon_{0}^{1}(a^{\prime}))$
		$\displaystyle=\sum_{\ell\in[d]}\Psi_{1}(a)_{i,\ell}\Psi_{2}(c)_{i,\ell,j}\Psi_{1}(a^{\prime})_{\ell,j}$
		$\displaystyle=\Psi_{1}(a)\Psi_{1}(a^{\prime}),$

where the multiplication in the last line is meant to be in $B(F,\Psi_{2}(c))$ . ∎

Remark 3.5.

Let $\mathbf{1}\in F^{\otimes 3}$ be the trivial cocycle. There is an explicit isomorphism between $A(F,\mathbf{1})$ and $M_{d}(k)$ . Indeed, the algebra $M_{d}(k)$ is isomorphic to the algebra $F\otimes F^{\vee}$ of $k$ -linear endomorphisms of $F$ , where $F^{\vee}$ is the dual $k$ -vector space of $F$ . In fact, the map $a\mapsto\operatorname{Tr}_{F/k}(a\cdot)\coloneq\left(b\mapsto\operatorname{Tr}_{F/k}(ab)\right)$ gives a $k$ -linear isomorphism from $F$ to its dual space $F^{\vee}$ , so we may see $M_{d}(k)$ as the algebra $F\otimes F$ with the following multiplication law:

(a\otimes a^{\prime})(b\otimes b^{\prime})=\operatorname{Tr}_{F/k}(a^{\prime}b)a\otimes b^{\prime}.

Let $a,a^{\prime},b,b^{\prime}\in F$ , we compute the following multiplication in $A(F,\mathbf{1})$ :

	$\displaystyle(a\otimes a^{\prime})(b\otimes b^{\prime})$	$\displaystyle=\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}\left(\varepsilon_{2}^{1}(a\otimes a^{\prime})\varepsilon_{0}^{1}(b\otimes b^{\prime})\right)$
		$\displaystyle=\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(a\otimes a^{\prime}b\otimes b^{\prime})$
		$\displaystyle=\operatorname{Tr}_{F/k}(a^{\prime}b)a\otimes b^{\prime}.$

It follows that if $\mathcal{B}$ is a basis of $F$ and we identify elements of $F$ with the column vectors of their components in basis $\mathcal{B}$ , and for $a\in F$ , we set $\varphi(a)$ to be the row matrix of the linear form $b\mapsto\operatorname{Tr}_{F/k}(ab)$ , then an isomorphism from $A(F,\mathbf{1})$ to $M_{d}(k)$ is given by

a\otimes a^{\prime}\mapsto a\varphi(a^{\prime}).

Theorem 3.6.

Let $A$ be a central simple $k$ -algebra, let $F\subset A$ be a separable maximal commutative subalgebra, and let $v\in A$ be such that $A=FvF$ . Then, there is a cocycle $c\in Z^{2}_{Am}(k,F)$ such that the map

\begin{array}[]{rlcl}\Phi_{v}\colon&F^{\otimes 2}&\to&A\\ &r_{1}\otimes r_{2}&\mapsto&r_{1}vr_{2}\end{array}

is an isomorphism of $k$ -algebras from $A(F,c)$ to $A$ (which makes sense as $F^{\otimes 2}$ is the underlying $k$ -vector space of $A(F,c)$ ). Furthermore, $c$ is the unique element of $F^{\otimes 3}$ with this property (if we extend the definition of the multiplication in $A(F,c)$ to non-cocycle elements).

Proof.

Let $c^{\prime}\in B^{2}(k,F)$ be the Brauer factor set constructed from the data of $F,A$ and $v$ as in the discussion at the end of Section 2.2, and let $\theta_{v}$ be the isomorphism from $A$ to $B(F,c^{\prime})$ constructed there. We also let $c=\Psi_{2}^{-1}(c^{\prime})$ . The fact that $\Phi_{v}$ is an isomorphism of $k$ -algebras follows from the observation that $\theta_{v}\circ\Phi_{v}=\Psi_{1}$ and from 3.4.

The cocycle $c$ is a solution to the system of $F^{\otimes 2}$ -linear equations

\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}\left(\varepsilon_{2}^{1}(u)c\varepsilon_{0}^{1}(u^{\prime})\right)=\Phi_{v}^{-1}\left(\Phi_{v}(u)\Phi_{v}(u^{\prime})\right)

for all $u,u^{\prime}\in F^{\otimes 2}$ . Observe that $\varepsilon_{2}^{1}(u)\varepsilon_{0}^{1}(u^{\prime})$ ranges over $F^{\otimes 3}$ as $u,u^{\prime}$ range over $F^{\otimes 2}$ . Then, the uniqueness of $c$ follows from the fact that the map $c\mapsto\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(c\cdot)$ is an isomorphism from $F^{\otimes 3}$ to its dual as a $F^{\otimes 2}$ -module.

This last fact, in turn, follows from [29, Corollary 4.6.8 and Proposition 4.6.1]. Indeed, $F^{\otimes 3}\simeq F^{\otimes 2}[X]/P$ , and $P\in k[X]\subset F^{\otimes 2}[X]$ is a separable polynomial, so $F^{\otimes 3}$ is a separable $F^{\otimes 2}$ -algebra. ∎

Corollary 3.7.

Let $c,c^{\prime}\in Z_{Am}^{2}(k,F)$ be associated cocycles, and let $a\in C_{am}^{2}(k,F)$ be such that $c^{\prime}=c\Delta_{Am}^{1}(a)$ . Then, the map $m\mapsto ma^{-1}$ , where the multiplication used is the natural one in $F^{\otimes 2}$ , is an isomorphism from $A(F,c)$ to $A(F,c^{\prime})$ .

Proof.

This is just a consequence of the analogous property for Brauer factor sets (2.13), pulled back through the isomorphisms $\Psi_{i}$ . ∎

Remark 3.8.

For the sake of efficiency, we use already proven results on Brauer factor-sets and the isomorphisms $\Psi_{1}$ and $\Psi_{2}$ to describe the isomorphism between the groups $H^{2}_{Am}(k,F)$ and $\operatorname{Br}(F/k)$ . However, the simplicity of the isomorphism $\Phi_{c}$ described in Theorem 3.6 suggests that Amitsur cohomology is a natural setting for giving an algebraic description of $\operatorname{Br}(F/k)$ and that direct proofs of these facts may be given without using references to Brauer factor-sets.

3.2 Computational representation of Amitsur cohomology

Once a field $k$ and an étale $k$ -algebra $F=k[X]/P$ are fixed, for $n\in\mathbb{N}$ , we have an isomorphism

\Xi_{n}\colon F^{\otimes n+1}\to R_{n}\coloneqq k[X_{0},\ldots,X_{n}]/I_{n},

where $I_{n}$ is the ideal generated by the polynomials $P(X_{i})$ for $0\leq i\leq n$ . Furthermore, an element of $R_{n}$ admits a unique lift in $k[X_{0},\ldots,X_{n}]$ such that the individual degrees in $X_{0},X_{1},\ldots,X_{n}$ are all lesser or equal to $d-1$ . If $Q\in k[X_{0},\ldots,X_{n}]$ , we denote by $\widetilde{Q}$ the lift of $Q\mod I$ as described above. There is an obvious polynomial algorithm which, given some $Q\in k[X_{0},\ldots,X_{n}]$ , computes $\widetilde{Q}$ . Indeed, one may simply reduce $Q$ modulo $P(X_{0})$ , then modulo $P(X_{1})$ , and so on… This allows us to represent an element $Q\in R_{n}$ as its lift $\widetilde{Q}$ , and in general we get $Q_{1}+Q_{2}=\widetilde{Q_{1}}+\widetilde{Q_{2}}\mod I_{n}$ and $Q_{1}Q_{2}=\widetilde{Q_{1}}\widetilde{Q_{2}}\mod I_{n}$ .

In this setting, the map $\varepsilon_{i}^{n}$ becomes the map

Q\mod I_{n}\mapsto\widetilde{Q}(X_{0},\ldots,X_{i-1},X_{i+1},\ldots,X_{n})\mod I_{n+1}.

That is, we define a map

\nu_{i}^{n}(X_{j})=\begin{cases}X_{j}\quad\text{if }j<i\\ X_{j+1}\quad\text{otherwise.}\end{cases}

from $k[X_{0},\ldots,X_{n}]$ to $k[X_{0},\ldots,X_{n+1}]$ , and we define

\begin{array}[]{rccc}\varepsilon_{i}^{n}\colon&R_{n}&\to&R_{n+1}\\ &Q\mod I_{n}&\mapsto&\nu_{i}^{n}(\widetilde{Q})\mod I_{n+1}.\end{array}

The maps defined above are compatible with the eponymous maps from the Amitsur complex. That is, we have $\varepsilon_{i}^{n}\circ\Xi_{n}=\Xi_{n+1}\circ\varepsilon_{i}^{n}$ .

Now, the trace map of $R_{2}$ as an $R_{1}$ algebra (via the morphism $\varepsilon_{1}^{1}$ ) may easily be computed in the $R_{1}$ -basis $(X_{1}^{i})_{0\leq i<d}$ of $R_{2}$ . Let $c\in Z^{2}_{Am}(k,F)$ , $Q=\Xi_{2}(c)$ , $a,a^{\prime}\in A(F,c)$ , $T=\Xi_{1}(a)$ and $T^{\prime}=\Xi_{1}(a^{\prime})$ . We set $T^{\prime\prime}=\Xi_{1}^{-1}(aa^{\prime})$ , and we have

T^{\prime\prime}=\operatorname{Tr}_{R_{2}/R_{1}}\left(\varepsilon_{2}^{1}(T)Q\varepsilon_{0}^{1}(T^{\prime})\right).

That is,

\Xi_{1}(aa^{\prime})=\operatorname{Tr}_{R_{2}/R_{1}}\left(\varepsilon_{2}^{1}(\Xi_{1}(a))\Xi_{2}(c)\varepsilon_{0}^{1}(\Xi_{1}(a^{\prime}))\right).

For the remainder of this work, elements of algebras of the form $F^{\otimes n+1}$ , when $F\simeq k[X]/(P(X))$ is an étale $k$ -algebra, are represented algorithmically as their images by $\Xi_{n}$ in $R_{n}$ .

3.3 Representing central simple algebras as Amitsur algebras

We may now give an algorithm for finding a representation of a central simple algebra $A$ over any field of sufficiently large size where linear algebra tasks may be performed efficiently.

Input: A field

k

Input: A central simple

k

-algebra

A

such that

|k|>\dim_{k}A

Output:

u\in A

such that

F=k(u)

is a maximal commutative subalgebra of

A

Output:

P\in k[X]

, the minimal polynomial of

u

Output:

c\in Z_{Am}^{2}(k,F)

Output: A linear map

e\colon F^{\otimes 2}\to A

that is an isomorphism from

A(F,c)

A

1 Find

u\in A

such that

F\coloneqq k[u]

is a maximal separable commutative subalgebra of

A

;

2 Compute

P

, the minimal polynomial of

u

;

3 Find

v\in A

such that

A=FvF

;

4 Compute the

k

-vector space isomorphism

e:F^{\otimes 2}\to A

sending

u^{i}\otimes u^{j}

u^{i}vu^{j}

;

5 Compute

c\in F^{\otimes 3}

such that for

0\leq i,j,i^{\prime},j^{\prime}\leq d-1

e(u^{i}\otimes u^{j})e(u^{i^{\prime}}\otimes u^{j^{\prime}})=\operatorname{Tr}_{F^{\otimes 3}/F^{\otimes 2}}(\varepsilon_{2}^{1}(u^{i}\otimes u^{j})c\varepsilon_{0}^{1}(u^{i^{\prime}}\otimes u^{j^{\prime}}))

;

return $(u,P,c,e)$

Algorithm 1 Computing a presentation of a central simple algebra as an Amitsur algebra

Before we prove the correctness and efficiency of Algorithm 1, we need a lemma:

Lemma 3.9.

Let $k$ be a field and let $A$ be a central simple $k$ -algebra. Assume that $|k|>\dim_{k}A$ . Let $u\in A$ be such that $F\coloneqq k[u]$ is a maximal commutative subalgebra of $A$ . Then an element $v\in A$ such that $A=FvF$ may be found in probabilistic polynomial time.

Proof.

For $v$ in $A$ , by an argument of dimensions over $k$ , we observe that $A=FvF$ if and only if the map

e\colon\begin{array}[]{ccl}F\otimes F&\to&A\\ f_{1}\otimes f_{2}&\mapsto&f_{1}vf_{2}\end{array}

is injective.

The family $(u^{i}\otimes u^{j})_{0\leq i,j\leq\deg A-1}$ is a basis of $F^{\otimes 2}$ . Let $B=(b_{1},\ldots,b_{\dim A})$ be the input basis of $A$ (that is, the basis for which the structure constants of $A$ are expressed). Then, identifying $e$ with its matrix in the bases written above, the determinant of $e$ is a homogeneous polynomial on the coordinates of $v$ in basis $B$ of degree bounded by $\dim A$ . Furthermore, $A=FvF$ if and only if $v$ is not a zero of this polynomial. We note that by [38, Theorem 2.2.2], this polynomial is nonzero.

Letting $S$ be a finite subset of $k$ , the Schwartz-Zippel lemma ensures that a random $v$ in $Sb_{1}\oplus\ldots\oplus Sb_{\dim A}$ satisfies this condition with probability larger than $1-\frac{\dim A}{|S|}$ .

Therefore, if $|k|>\dim A$ , we may pick $S$ large enough that $v$ has the desired property with positive probability, and small enough that we may draw a random element of $S$ efficiently. For instance, take $|S|=\dim A+1$ . Then, $v$ has the desired property with probability larger than $\frac{1}{\dim A+1}$ . In this case, it is expected to take less than $\dim A+1$ attempts to find a suitable element $v\in A$ . ∎

Theorem 3.10.

If $k$ is a field over which linear algebra may be performed efficiently, and $A$ is a central simple $k$ -algebra such that $|k|>\dim_{k}A$ , then Algorithm 1 is correct and runs in probabilistic polynomial time.

Proof.

We first prove the correctness of the algorithm. The first 3 steps compute $u,v\in A$ , as well as $P\in k[X]$ , the minimal polynomial of $u$ . We obtain a subalgebra $F=k[u]\simeq k[X]/P$ of $A$ and $v\in A$ such that $A=FvF$ . Then, by Theorem 3.6, there exists a cocycle $c\in Z_{Am}^{2}(k,F)$ such that $e\colon a\otimes b\mapsto avb$ is an isomorphism from $A(k,F)$ to $A$ , and such a $c$ is unique in $F^{\otimes 3}$ . The equation solved in Algorithm 1 finds a representation of this $c$ .

Now we consider the complexity of the algorithm:

The element $u\in A$ in Algorithm 1 may be found using the polynomial algorithm given in [22].

Then, $v$ in Algorithm 1 may be found in probabilistic polynomial time using the algorithm of Lemma 3.9.

Then, the remaining lines involve arithmetic in the $k$ -algebras $A$ , $R_{1}$ and $R_{2}$ , as well as the computation of the solution of a system of linear equations.

All in all, this makes Algorithm 1 a polynomial probabilistic algorithm. ∎

4 Trivialisation of Amitsur cocycles

In this section, we present an algorithm for computing a trivialisation of a coboundary using $S$ -unit group computation. For this purpose, we prove Theorem 4.11, which states that a trivialisation of a coboundary may be found in an appropriate group of $S$ -units. This result is to be compared with 2.6 and [25, Theorem 7]. Then, we may state Algorithm 2 which computes a trivialisation of a given coboundary by solving the related equation in an appropriate group of $S$ -units. Furthermore, we get Theorem 4.13 which, assuming GRH, solves the explicit isomorphism problem in quantum polynomial time.

The technical part of this section is devoted to proving Theorem 4.11. The strategy we employ is similar to the proof of [25, Theorem 7]. That is, we prove Lemma 4.10, which is a generalisation to divisors of Hilbert’s Theorem 90 on the vanishing of the first cohomology group. While [25, Lemma 9] is stated for fractional ideals of a number field, our setting requires us bring this machinery to the setting of étale algebras. We therefore first introduce definitions and basic results for the divisors of an étale algebra over a global field in Section 4.1.

4.1 Divisors of étale algebras

Let $k$ be a global field. Then, recall that a commutative $k$ -algebra $F$ is étale if and only if it satisfies the following equivalent conditions:

1.

The algebra $F$ factors as a direct product $F\simeq F_{1}\times\ldots\times F_{r}$ of finite separable extensions of $k$ .
2.

The algebra $F$ is isomorphic to an algebra of the form $k[X]/(P(X))$ , where $P\in k[X]$ is a separable polynomial (that is, $P$ has no multiple root in an algebraic closure of $k$ ).

Remark 4.1.

If $F$ is an étale $k$ -algebra, the isomorphism $F\simeq F_{1}\times\ldots\times F_{r}$ discussed above is unique up to reindexing and automorphism of the factors. In fact, the factors identify with the minimal ideals of $F$ . Therefore, we usually identify an étale algebra $F$ with the product $F_{1}\times\ldots\times F_{r}$ . We will also denote by $\pi_{i}$ the projection map $F\to F_{i}$ .

If $F$ is a global field, we write $\operatorname{Pl}(F)$ for the set of non-archimedean places of $F$ . Then, recall that the divisor group $\operatorname{\mathcal{D}}(F)$ is the free abelian group on the set $\operatorname{Pl}(F)$ , that an element $a\in F$ has an associated divisor $\operatorname{\mathcal{D}}(a)=\sum_{P\in\operatorname{Pl}(F)}\operatorname{ord}_{P}(a)P$ , and that if $\operatorname{\mathcal{P}}(F)=\{\operatorname{\mathcal{D}}(a)\colon a\in F\}$ is the group of principal divisors, then the class group $\operatorname{Cl}(F)=\operatorname{\mathcal{D}}(F)/\operatorname{\mathcal{P}}(F)$ of $F$ is finite. When $F$ is a number field, the divisor group is isomorphic to the group of fractional ideals of $F$ , and the class group in terms of divisors is then isomorphic to the ideal class group.

Definition 4.2.

Let $F=F_{1}\times\ldots\times F_{r}$ be an étale $k$ -algebra factored as above. The set of non-archimedean places of $F$ is the disjoint union $\operatorname{Pl}(F)=\bigsqcup_{i\in[r]}\operatorname{Pl}(F_{i})$ . The divisor group $\operatorname{\mathcal{D}}(F)$ of $F$ is the free abelian group on $\operatorname{Pl}(F)$ . The divisor $\operatorname{\mathcal{D}}(a)$ of an invertible element $a\in F^{\times}$ is defined as the sum of the divisors of its projections in the factors $F_{i}$ of $F$ , and the groups $\operatorname{\mathcal{P}}(F)$ and $\operatorname{Cl}(F)$ are defined by analogy with their definitions for global fields. If $D\in\operatorname{\mathcal{D}}(F)=\sum_{P\in\operatorname{Pl}(F)}n_{P}P$ , we let $\operatorname{Supp}(D)=\{P\in\operatorname{Pl}(F)\colon n_{P}\neq 0\}$ be the support of $D$ .

An immediate consequence of this definition is that the class group of an étale $k$ -algebra is finite.

If $F=F_{1}\times\ldots\times F_{r}$ and $F^{\prime}=F^{\prime}_{1}\times\ldots\times F^{\prime}_{r^{\prime}}$ are two étale $k$ -algebras, and $f\colon F\to F^{\prime}$ is a homomorphism of $k$ -algebras, it decomposes as a matrix $(f_{ij})_{\begin{subarray}{c}i\in[r]\\ j\in[r^{\prime}]\end{subarray}}$ , where $f_{ij}\colon F_{i}\to F_{j}^{\prime}$ , and each $f_{ij}$ is either the zero map or an embedding of field extensions of $k$ (depending on whether the unit of $F_{i}$ is mapped to $0$ or to the unit of $F_{j}$ ). That is, if $a\in F$ and $j\in[r^{\prime}]$ ,

\pi^{\prime}_{j}(f(a))=\sum_{i\in[r]}f_{ij}(\pi_{i}(a)),

where the $\pi_{i}$ are the projections $F\to F_{i}$ and the $\pi^{\prime}_{j}$ are the projections $F^{\prime}\to F^{\prime}_{j}$ .

We may then define a map $\operatorname{\mathcal{D}}(f)\colon\operatorname{\mathcal{D}}(F)\to\operatorname{\mathcal{D}}(F^{\prime})$ the following way: let $i\in[r]$ and $P\in\operatorname{Pl}(F_{i})$ , we set $\operatorname{\mathcal{D}}(f)(P)=\sum_{j\in[r^{\prime}]}\operatorname{\mathcal{D}}(f_{ij})(P)$ , where $\operatorname{\mathcal{D}}(f_{ij})$ is the usual map on divisors of global fields if $f_{ij}$ is an embedding of fields and is zero if $f_{ij}=0$ . One may check that this definition makes $\operatorname{\mathcal{D}}$ into a functor from the category of étale $k$ -algebras to the category of abelian groups. Furthermore, the map $\operatorname{\mathcal{D}}\colon F^{\times}\to\operatorname{\mathcal{D}}(F)$ is a natural transformation of the multiplicative group functor into the functor $\operatorname{\mathcal{D}}$ sending an étale algebra to its divisor group. That is, if $a\in F^{\times}$ , then $\operatorname{\mathcal{D}}(f)(\operatorname{\mathcal{D}}(a))=\operatorname{\mathcal{D}}(f(a))$ .

As is the case for global fields, if $Q\in M_{F^{\prime}}$ , there is at most one place $P\in\operatorname{Pl}(F)$ such that $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ . To prove this, we first need a lemma:

Lemma 4.3.

Let notations be as above and let $j\in[r^{\prime}]$ . Then there is at most one $i\in[r]$ such that $f_{ij}$ is nonzero.

Proof.

Let $i_{1},i_{2}\in[r]$ and $j\in[r^{\prime}]$ , and let $e_{1},e_{2}$ be the units respectively of $F_{i_{1}}$ and $F_{i_{2}}$ . We then have $\pi^{\prime}_{j}(f(e_{1}))=f_{i_{1}j}(1)\in F_{j}$ and $\pi^{\prime}_{j}(f(e_{2}))=f_{i_{2}j}(1)\in F_{j}$ . Now, since $e_{1}e_{2}=0$ , we have $f_{i_{1}j}(1)f_{i_{2}j}(1)=0$ . That is, either $f_{i_{1}j}(1)=0$ or $f_{i_{2}j}(1)=0$ . It follows that either $f_{i_{1}j}$ or $f_{i_{2}j}$ is the zero map. ∎

Now, we prove the following:

Proposition 4.4.

Let notations be as above, and let $Q\in\operatorname{Pl}(F^{\prime})$ . Then there is at most one place $P\in\operatorname{Pl}(F)$ such that $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ .

Proof.

Let $j\in[r^{\prime}]$ be such that $Q\in\operatorname{Pl}(F_{j})$ . Then, by Lemma 4.3, there is at most one value $i\in[r]$ such that $f_{ij}\neq 0$ . If there is no such $i$ , then no divisor of $F$ has an image by $\operatorname{\mathcal{D}}(f)$ with $Q$ in its support. Otherwise, if $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ , it follows that $P\in\operatorname{Pl}(F_{i})$ . Then, the usual theory of divisors of global fields ensures that there is only one $P\in\operatorname{Pl}(F_{i})$ such that $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ . ∎

If $j\in[r^{\prime}]$ is such that $f_{ij}$ is nonzero for some $i\in[r]$ , and if $Q\in\operatorname{Pl}(F^{\prime}_{j})$ , we write $Q_{f}$ for the unique $P\in\operatorname{Pl}(F)$ such that $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ . We note that if $f$ is an inclusion of the form $F\hookrightarrow F\otimes_{k}F^{\prime}$ , $a\mapsto a\otimes 1$ , then $Q_{f}$ exists for all $Q\in\operatorname{Pl}(F\otimes_{k}F^{\prime})$ .

Let $Q\in\operatorname{Pl}(F^{\prime})$ such that $Q_{f}$ is well defined. We let $e_{Q,f}$ be the coefficient of $Q$ in the expansion of the divisor $\operatorname{\mathcal{D}}(f)(Q_{f})$ . Let $P\in\operatorname{Pl}(F)$ , if $e_{Q,f}\neq 1$ for some $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ , we say that the place $P$ ramifies through $f$ . This is equivalent to saying that, if $i\in[r]$ is such that $P\in\operatorname{Pl}(F_{i})$ , then for some $j\in[r^{\prime}]$ such that $f_{ij}$ is nonzero, the place $P$ ramifies in $F_{j}$ .

In order to prove some facts about the behaviour of places in étale algebras, we will need to use local fields. For this purpose, we make the following definition:

Definition 4.5.

Let $F$ be as above. Let $i\in[r]$ and let $P\in\operatorname{Pl}(F_{i})\subset\operatorname{Pl}(F)$ . Then the local completion $F_{P}$ of $F$ at $P$ is the completion of the global field $F_{i}$ at the place $P$ . This completion is an $F$ -algebra via the composite map

F\xrightarrow{\pi_{i}}F_{i}\rightarrow F_{P}.

As in the case of extensions of global fields, the places of $F^{\prime}$ lying above a place of $F$ may be classified as the direct factors of a tensor product.

Proposition 4.6.

Let notations be as above, let $i\in[r]$ and $P\in\operatorname{Pl}(F_{i})\subset\operatorname{Pl}(F)$ . Let $J=\{j\in[r^{\prime}]\colon f_{ij}\neq 0\}$ . Then, we have

F_{P}\otimes_{F}F^{\prime}\simeq F_{P}\otimes_{F_{i}}\prod_{j\in J}F^{\prime}_{j}.

The usual bijections between the places of $F^{\prime}_{j}$ above $P$ and the direct factors of $F_{P}\otimes F^{\prime}_{j}$ give a bijection between the direct factors of $F_{P}\otimes F^{\prime}$ and $\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P))$ . Furthermore, for $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(f)(P)$ , we have $e_{Q,f}\neq 1$ if and only if the corresponding factor is a ramified extension of $F_{P}$ .

Proof.

We have

F_{P}\otimes_{F_{i}}\prod_{j\in J}F^{\prime}_{j}\simeq F_{P}\otimes_{F_{i}}(F_{i}\otimes_{F}F^{\prime})\simeq F_{P}\otimes_{F}F^{\prime}.

Then, the rest of the results follows directly from the definition of $\operatorname{\mathcal{D}}(f)$ and the equivalent results for extensions of global fields (see e.g [11, Sections II.10 and II.19]). ∎

Finally, we also prove a result about ramification and tensor products:

Proposition 4.7.

Let $F$ and $G$ be étale $k$ -algebras, and let $P\in\operatorname{Pl}(k)$ be a place that ramifies neither in $F$ nor in $G$ . Then, $P$ does not ramify in $F\otimes_{k}G$ either.

Proof.

Let $k_{P}$ be the completion of $k$ at $P$ . By 4.6, it is enough to prove that the direct factors of $k_{P}\otimes_{k}F\otimes_{k}F^{\prime}$ are unramified extensions of $k_{P}$ . Now, since

k_{P}\otimes_{k}F\otimes_{k}F^{\prime}\simeq(k_{P}\otimes_{k}F)\otimes_{k_{P}}(k_{P}\otimes_{k}F^{\prime}),

the result will follow from the fact that if $K,K^{\prime}$ are unramified finite extensions of $k_{P}$ , then the direct factors of $K\otimes_{k_{P}}K^{\prime}$ are themselves unramified extensions of $k_{P}$ .

This, in turns, follows from [11, Proposition I.7.1]. Indeed, by the proposition, we know that there are polynomials $g,g^{\prime}\in R[X]$ (where $R$ is the valuation ring of $k_{P}$ ) such that $K\simeq k_{P}[X]/(g(X))$ , $K^{\prime}\simeq k_{P}[X]/g^{\prime}(X)$ and whose residues $\overline{g}$ and $\overline{g^{\prime}}$ are irreducible and separable in $\kappa_{P}[X]$ , where $\kappa_{P}$ is the residue field of $k_{P}$ . Now, we have $K\otimes_{k_{P}}K^{\prime}\simeq K[X]/(g^{\prime}(X))$ . A direct factor of this algebra is of the form $K[X]/(h(X))$ , where $h$ is an irreducible factor of $g^{\prime}$ in $\mathcal{O}[X]$ , where $\mathcal{O}$ is the valuation ring of $K$ . Since $\overline{h}$ is a factor of the separable polynomial $\overline{g^{\prime}}$ , it is itself separable as a polynomial in $\mathfrak{k}[X]$ , where $\mathfrak{k}$ is the residue field of $K$ . Since the polynomial $h$ is irreducible in $\mathcal{O}[X]$ and its residue is separable, this residue $\overline{h}$ is irreducible in $\mathfrak{k}[X]$ by Hensel’s lemma. By the proposition cited above, the field extension $K[X]/(h(X))$ is unramified over $K$ , and therefore over $k_{P}$ . It follows that the direct factors of $K\otimes_{k_{P}}K^{\prime}$ are unramified over $k_{P}$ . ∎

4.2 An algorithm for trivialising Amitsur coboundaries over a number field

Let $k$ be a number field, and let $F$ be an étale $k$ -algebra. The Amitsur complex for $F$ yields a complex

\ldots\to\operatorname{\mathcal{D}}(F^{\otimes n+1})\xrightarrow{\operatorname{\mathcal{D}}(\Delta_{Am}^{n})}\operatorname{\mathcal{D}}(F^{\otimes n+2})\to\ldots.

of abelian groups, where we define $\operatorname{\mathcal{D}}(\Delta_{Am}^{n})$ as $\sum_{0\leq i\leq n}(-1)^{i}\operatorname{\mathcal{D}}(\varepsilon^{n}_{i})$ .

We give a precise description of the map $\operatorname{\mathcal{D}}(\Delta_{Am}^{n})$ . Let $Q\in\operatorname{Pl}(F^{\otimes n+2})$ . Then, for any $0\leq i\leq n+1$ , we set $Q_{i}=Q_{\varepsilon_{i}^{n}}$ and $e_{Q,i}=e_{Q,\varepsilon_{i}^{n}}$ . Then, if $P\in\operatorname{Pl}(F^{\otimes n+1})$ , we get

\operatorname{\mathcal{D}}(\varepsilon_{i}^{n})(P)=\sum_{\begin{subarray}{c}Q\in\operatorname{Pl}(F^{\otimes n+2})\\ Q_{i}=P\end{subarray}}e_{Q,i}Q,

and it follows that

\operatorname{\mathcal{D}}(\varepsilon_{i}^{n})\left(\sum_{P\in\operatorname{Pl}(F^{\otimes n+1})}n_{P}P\right)=\sum_{Q\in\operatorname{Pl}(F^{\otimes n+2})}e_{Q,i}n_{Q_{i}}Q

and

\operatorname{\mathcal{D}}(\Delta_{Am}^{n})\left(\sum_{P\in\operatorname{Pl}(F^{\otimes n+1})}n_{P}P\right)=\sum_{Q\in\operatorname{Pl}(F^{\otimes n+2})}\left(\sum_{0\leq i\leq{n+1}}(-1)^{i}e_{Q,i}n_{Q_{i}}\right)Q.

We first need two lemmas:

Lemma 4.8.

Let $Q,Q^{\prime}$ be places of $F^{\otimes 2}$ such that $Q_{0}=Q^{\prime}_{0}=P$ . Then there exists a place $R\in\operatorname{Pl}(F^{\otimes 3})$ such that $R_{1}=Q$ and $R_{0}=Q^{\prime}$ .

Proof.

We let $\alpha$ be a defining polynomial of $F$ . That is, $F\simeq k[X]/(\alpha(X))$ , with $\alpha\in k[X]$ separable. We may then identify $F^{\otimes 2}$ with $F[X]/(\alpha(X))$ , where $\varepsilon_{0}^{0}$ maps $F$ into the ring of scalars in $F[X]/(\alpha(X))$ and $\varepsilon_{1}^{0}$ is the map

\begin{array}[]{ccc}k[X]/(\alpha(X))&\to&F[X]/(\alpha(X))\\ X&\mapsto&X.\end{array}

Likewise, we identify $F^{\otimes 3}$ with $F[X,Y]/(\alpha(X),\alpha(Y))$ . Then, the descriptions of the maps $\varepsilon_{0}^{1}$ and $\varepsilon_{1}^{1}$ become:

\begin{array}[]{rccc}\varepsilon_{0}^{1}\colon&F[X]/(\alpha(X))&\to&F[X,Y]/(\alpha(X),\alpha(Y))\\ &X&\mapsto&Y\\ \varepsilon_{1}^{1}\colon&F[X]/(\alpha(X))&\to&F[X,Y]/(\alpha(X),\alpha(Y))\\ &X&\mapsto&X\end{array}

These identifications are coherent with the maps of the Amitsur complex. In particular, we note that $\varepsilon_{0}^{1}\circ\varepsilon_{0}^{0}=\varepsilon_{1}^{1}\circ\varepsilon_{0}^{0}$ . With this in place, let $P\in\operatorname{Pl}(F)$ . By 4.6, the support of $\operatorname{\mathcal{D}}(\varepsilon_{0}^{0})(P)$ is in bijection with the direct factors of $F_{P}[X]/(\alpha(X))$ . That is, it is in bijection with the irreducible factors of $\alpha(X)$ in $F_{P}[X]$ . Likewise, the support of $\operatorname{\mathcal{D}}(\varepsilon_{0}^{1}\circ\varepsilon_{0}^{0})(P)$ is in bijection with the irreducible factors of $F_{P}[X,Y]/(\alpha(X),\alpha(Y))$ . That is, it is in bijection with the maximal ideals that contain the ideal $(\alpha(X),\alpha(Y))$ .

Now, if $Q\in\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{0}^{0})(P))$ , we let $\alpha_{Q}(X)$ be the irreducible factor of $\alpha(X)$ corresponding to $Q$ . Likewise, if $R\in\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{0}^{1}\circ\varepsilon_{0}^{0})(P)$ , we let $\mathfrak{m}_{R}$ be the maximal ideal of $F_{P}[X,Y]$ corresponding to $R$ . Observe that $R\in\operatorname{Supp}(\varepsilon_{0}^{1})(Q)$ if and only if $\alpha_{Q}(Y)\in\mathfrak{m}_{R}$ and $R\in\operatorname{Supp}(\varepsilon_{1}^{1})(Q)$ if and only if $\alpha_{Q}(X)\in\mathfrak{m}_{R}$ . Then, the result simply follows from the observation that the ideal $(\alpha_{Q^{\prime}}(X),\alpha_{Q}(Y))$ contains $(\alpha(X),\alpha(Y))$ and is contained in some maximal ideal of $F_{P}[X,Y]$ . Such a maximal ideal then corresponds to a place $R\in M_{F^{\otimes 3}}$ such that $R_{1}=Q$ and $R_{0}=Q^{\prime}$ . ∎

For $n\geq 0$ and $S\subset\operatorname{Pl}(k)$ , we let $S^{(n)}$ be the subset of $\operatorname{Pl}(F^{\otimes n+1})$ of places lying above some $P\in S$ . We let $S_{r}$ be the set of places of $k$ that ramify in $F$ . Applying 4.7 by induction, we get the following:

Lemma 4.9.

Let $Q\in\operatorname{Pl}(F^{\otimes n+1})\setminus S_{r}^{(n)}$ . Then for $0\leq i\leq n+1$ , we have $e_{Q,i}=1$ .

We may now prove the following generalisation of Hilbert’s Theorem 90:

Lemma 4.10.

Let $D=\sum_{Q\in\operatorname{Pl}(F^{\otimes 2})}n_{Q}Q\in\operatorname{Ker}\operatorname{\mathcal{D}}(\Delta_{Am}^{1})$ be supported by places outside of $S_{r}^{(1)}$ . Then, there exists $E\in\operatorname{\mathcal{D}}(F)$ such that $D=\operatorname{\mathcal{D}}(\Delta_{Am}^{0})(E)$ .

Proof.

We set

E=\sum_{P\in\operatorname{Pl}(F)}\left(\min_{\begin{subarray}{c}Q\in\operatorname{Pl}(F^{\otimes 2})\\ Q_{0}=P\end{subarray}}n_{Q}\right)P.

Then, by Lemma 4.9, we get

\operatorname{\mathcal{D}}(\varepsilon_{0}^{0})(E)=\sum_{Q\in\operatorname{Pl}(F^{\otimes 2})}\left(\min_{\begin{subarray}{c}Q^{\prime\prime}\in\operatorname{Pl}(F^{\otimes 2})\\ Q^{\prime\prime}_{0}=Q_{0}\end{subarray}}n_{Q^{\prime\prime}}\right)Q

and

\operatorname{\mathcal{D}}(\varepsilon_{1}^{0})(E)=\sum_{Q\in\operatorname{Pl}(F^{\otimes 2})}\left(\min_{\begin{subarray}{c}Q^{\prime}\in\operatorname{Pl}(F^{\otimes 2})\\ Q^{\prime}_{0}=Q_{1}\end{subarray}}n_{Q^{\prime}}\right)Q

It follows that

D+\operatorname{\mathcal{D}}(\varepsilon_{1}^{0})(E)=\sum_{Q\in\operatorname{Pl}(F^{\otimes 2})}\left(\min_{\begin{subarray}{c}Q^{\prime}\in\operatorname{Pl}(F^{\otimes 2})\\ Q^{\prime}_{0}=Q_{1}\end{subarray}}n_{Q}+n_{Q^{\prime}}\right)Q.

We introduce the following automorphisms:

\begin{array}[]{rccc}\sigma\colon&F^{\otimes 2}&\to&F^{\otimes 2}\\ &a\otimes b&\mapsto&b\otimes a;\\ \tau\colon&F^{\otimes 3}&\to&F^{\otimes 3}\\ &a\otimes b\otimes c&\mapsto&a\otimes c\otimes b.\end{array}

Observe that we have the following equalities:

$\displaystyle\tau\circ\varepsilon_{0}^{1}$	$\displaystyle=\varepsilon_{0}^{1}\circ\sigma$	(3)
$\displaystyle\tau\circ\varepsilon_{2}^{1}$	$\displaystyle=\varepsilon_{1}^{1}$	(4)
$\displaystyle\varepsilon_{1}^{0}$	$\displaystyle=\sigma\circ\varepsilon_{0}^{0}.$	(5)

If $Q\in\operatorname{Pl}(F^{\otimes 2})$ (resp. $R\in\operatorname{Pl}(F^{\otimes 3})$ ), we write $Q^{\sigma}$ (resp. $R^{\tau}$ ) for the unique place in the support of $\operatorname{\mathcal{D}}(\sigma)(Q)$ (resp. $\operatorname{\mathcal{D}}(\tau)(R)$ ).

Now, let $Q,Q^{\prime}\in\operatorname{Pl}(F^{\otimes 2})$ such that $Q^{\prime}_{0}=Q_{1}$ . By Equation 5, we have $Q^{\prime}_{0}=Q_{0}^{\sigma}$ . Applying Lemma 4.8 to $Q^{\sigma}$ and $Q^{\prime}$ , we get $R\in\operatorname{Pl}(F^{\otimes 3})$ such that $R_{1}=Q^{\prime}$ and $R_{0}=Q^{\sigma}$ . By Equation 4, we have $R^{\tau}_{2}=R_{1}=Q^{\prime}$ and by Equation 3, we get $R^{\tau}_{0}=(R_{0})^{\sigma}=Q$ . We set $Q^{\prime\prime}=R_{1}^{\tau}$ . Now, the coefficient of $R^{\tau}$ in $\operatorname{\mathcal{D}}(\Delta^{1}_{Am})(D)$ is $n_{Q}+n_{Q^{\prime}}-n_{Q^{\prime\prime}}$ , and since this divisor is zero by hypothesis, we get $n_{Q^{\prime\prime}}=n_{Q}+n_{Q^{\prime}}$ (note that $R\notin S_{r}^{(2)}$ , so $e_{R,i}=1$ for $0\leq i\leq 2$ ). Observe that we have

	$\displaystyle R$	$\displaystyle\in\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{0}^{1})(Q))$
		$\displaystyle\subset\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{0}^{1}\circ\varepsilon_{0}^{0})(Q_{0}))$
		$\displaystyle=\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{1}^{1}\circ\varepsilon_{0}^{0})(Q_{0}))$

and

R\in\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{1}^{1})(Q^{\prime\prime}))\subset\operatorname{Supp}(\operatorname{\mathcal{D}}(\varepsilon_{1}^{1}\circ\varepsilon_{0}^{0})(Q^{\prime\prime}_{0})).

By 4.4, it follows that $Q_{0}=Q^{\prime\prime}_{0}$ . That is, we proved that there exists $Q^{\prime\prime}\in\operatorname{Pl}(F^{\otimes 2})$ such that $Q^{\prime\prime}_{0}=Q_{0}$ and $n_{Q}+n_{Q^{\prime}}=n_{Q^{\prime\prime}}$ .

Conversely, let $Q,Q^{\prime\prime}\in\operatorname{Pl}(F^{\otimes 2})$ such that $Q_{0}=Q^{\prime\prime}_{0}$ . Then by Lemma 4.8, there is $R\in\operatorname{Pl}(F^{\otimes 3})$ such that $R_{0}=Q$ and $R_{1}=Q^{\prime\prime}$ . Set $Q^{\prime}=R_{2}$ and, as above, we get $n_{Q}+n_{Q^{\prime}}=n_{Q^{\prime\prime}}$ . As above, we use the fact that $\varepsilon_{0}^{1}\circ\varepsilon_{1}^{0}=\varepsilon_{2}^{1}\circ\varepsilon_{0}^{0}$ to prove that $Q_{1}=Q^{\prime}_{0}$ .

Putting things together, we have proved that for $Q\in\operatorname{Pl}(F^{\otimes 2})\setminus S_{r}^{(1)}$ ,

\min_{\begin{subarray}{c}Q^{\prime}\in\operatorname{Pl}(F^{\otimes 2})\\ Q^{\prime}_{0}=Q_{1}\end{subarray}}n_{Q}+n_{Q^{\prime}}=\min_{\begin{subarray}{c}Q^{\prime\prime}\in\operatorname{Pl}(F^{\otimes 2})\\ Q^{\prime\prime}_{0}=Q_{0}\end{subarray}}n_{Q^{\prime\prime}}.

It follows directly that $D+\operatorname{\mathcal{D}}(\varepsilon_{1}^{0})(E)=\operatorname{\mathcal{D}}(\varepsilon_{0}^{0})(E)$ . ∎

We now get our main theorem for this section:

Theorem 4.11.

Let $b\in B_{Am}^{2}(k,F)$ be a coboundary. Let $S$ be a set of non-archimedean places of $k$ such that:

•

$S_{r}\subset S$ . That is, $S$ contains the places of $k$ that ramify in $F$ .
•

The finite places of $S^{(0)}$ generate the class group $\operatorname{Cl}(F)$ .
•

$\operatorname{Supp}(\operatorname{\mathcal{D}}(b))\subset S^{(2)}$ .

Then there exists a cochain $a$ in the group of $S^{(2)}$ -units of $F^{\otimes 2}$ such that $b=\Delta_{Am}^{1}(a)$

Proof.

Let $\alpha\in(F^{\otimes 2})^{\times}$ be such that $\Delta_{Am}^{1}(\alpha)=b$ . We consider the divisor $D=\operatorname{\mathcal{D}}(\alpha)=\sum_{Q\in\operatorname{Pl}(F^{\otimes 2})}n_{Q}Q$ of $\alpha$ . We set $D_{S}=\sum_{Q\in S^{(1)}}n_{Q}Q$ and $D^{\prime}_{S}=\sum_{Q\notin S^{(1)}}n_{Q}Q$ . Now we get $\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(D)=\operatorname{\mathcal{D}}(b)$ and therefore it is supported by $S^{(2)}$ . Observe that if $Q\in S^{(1)}$ , then $\operatorname{Supp}(\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(Q))\subset S^{(2)}$ and conversely, if $\operatorname{Supp}(\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(Q))\subset S^{(2)}$ and $\operatorname{\mathcal{D}}(\Delta_{Am}^{1})^{1}(Q)\neq 0$ , then $Q\in S^{(1)}$ . It follows that $\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(D^{\prime}_{S})=\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(D)-\operatorname{\mathcal{D}}(\Delta_{Am}^{1})(D_{S})=0$ .

The support of $D^{\prime}_{S}$ is disjoint from $S_{r}^{(1)}$ . We may therefore apply Lemma 4.10 and get a divisor $E\in\operatorname{\mathcal{D}}(F)$ such that $D^{\prime}_{S}=\Delta_{Am}^{0}(E)$ . Now, as $S^{(0)}$ generates the class group of $F$ , there exists $E^{\prime}\in\operatorname{\mathcal{D}}(F)$ with support in $S^{(0)}$ and $\gamma\in F^{\times}$ such that $E=\operatorname{\mathcal{D}}(\gamma)+E^{\prime}$ . Then, we get that

\operatorname{\mathcal{D}}(\Delta_{Am}^{0})(\operatorname{\mathcal{D}}(\gamma))+\operatorname{\mathcal{D}}(\Delta_{Am}^{0})(E^{\prime})=D-D_{S}

and therefore

\operatorname{\mathcal{D}}(\Delta_{Am}^{0})(E^{\prime})+D_{S}=\operatorname{\mathcal{D}}(\alpha\Delta_{Am}^{0}(\gamma^{-1})).

Now, since $\operatorname{\mathcal{D}}(\Delta_{Am}^{0})(E^{\prime})+D_{S}$ has support in $S^{(1)}$ , this shows that $\alpha\Delta_{Am}^{0}(\gamma^{-1})$ is a $S^{(1)}$ -unit. Furthermore,

\Delta_{Am}^{1}(\alpha\Delta_{Am}^{0}(\gamma^{-1}))=\Delta_{Am}^{1}(\alpha)=b,

and $\alpha\Delta_{Am}^{0}(\gamma^{-1})$ is a cochain with the required properties. ∎

From Theorem 4.11 we directly get an algorithm for computing a trivialisation of a $2$ -coboundary:

Input: A number field

k

Input: An étale

k

-algebra

F

defined by a separable polynomial

P\in k[X]

Input: A coboundary

b\in B_{Am}^{2}(k,F)

Output: A cochain

a\in C_{Am}^{0}(k,F)

such that

\Delta_{Am}^{1}(a)=c

1 Compute

S_{1}

, the set of places of

k

that ramify in

F

;

2 Compute

S_{2}

, a set of places of

k

such that

S_{2}^{(0)}

generates the class group

\operatorname{Cl}(F)

;

3 Compute

\operatorname{\mathcal{D}}(b)

. Let

S_{3}

be the set of places of

k

below the places in the support of

\operatorname{\mathcal{D}}(b)

;

4 Set

S=S_{1}\cup S_{2}\cup S_{3}

;

5 Compute the sets

S^{(2)}

and

S^{(3)}

;

6 Compute an isomorphism

\phi

from the group of

S^{(2)}

-units of

F^{\otimes 2}

\mathbb{Z}^{r}\oplus\mathbb{Z}/m\mathbb{Z}

;

7 Compute an isomorphism

\psi

from the group of

S^{(3)}

-units of

F^{\otimes 3}

\mathbb{Z}^{r^{\prime}}\oplus\mathbb{Z}/m^{\prime}\mathbb{Z}

;

8 Solve the linear equation

(\psi\circ\Delta_{Am}^{1}\circ\phi^{-1})(a)=\psi(b)

;

return $a$

Algorithm 2 Computing a trivialisation of a

2

-coboundary

Theorem 4.12.

Given a number field $k$ , a separable polynomial $P\in k[X]$ and a coboundary $b\in B^{2}_{Am}(k,F)$ , where $F=k[X]/P$ , Algorithm 2 outputs the representation of a cochain $\alpha\in C^{1}(k,F)$ such that $\Delta_{Am}^{1}(\alpha)=b$ . Furthermore, assuming GRH, Algorithm 2 is a polynomial quantum algorithm.

Proof.

Using a polynomial-time algorithm for factoring polynomials over number fields [41], one may compute splittings of $F$ , $F^{\otimes 2}$ and $F^{\otimes 3}$ as direct products of number fields. Set $F^{\otimes n+1}=F^{(n)}_{1}\times\ldots\times F_{r_{n}}^{(n)}$ .

The set $S_{1}$ may be computed by factoring the discriminants of the extensions $F^{(0)}_{i}/k$ , which may be done in polynomial time by 2.1. Then, by 2.3, one may compute in polynomial time a set of polynomial size of places of $F$ that generate the class group $\operatorname{Cl}(F)$ , and the set $S_{2}$ of places of $k$ lying below them. In practice, one may set $S_{2}$ to be the set of prime ideals $\mathfrak{p}$ of $k$ such that $N(\mathfrak{p})\leq 12\log^{2}(\max_{i\in[r]}|\Delta_{F_{i}}|)$ . We may then take the image $(b_{1},\ldots,b_{r_{2}})$ of $b$ in the product $F^{(2)}_{1}\times\ldots\times F^{(2)}_{r_{2}}$ and factor the principal ideals $(b_{i})$ in $F^{(2)}_{i}$ into a product $\mathfrak{p}_{i,1}\ldots\mathfrak{p}_{i,s_{i}}$ , which may be done in polynomial time by 2.2. We may then set $S_{3}=\{\mathfrak{p}_{i,j}\cap k,i\in[r_{2}],j\in[s_{i}]\}\subset\operatorname{Pl}(k)$ .

Isomorphisms $\phi$ and $\psi$ are computed using 2.5 and [42, Algorithm 8.4]. Finally, the last step is the computation of a solution of a system of linear equations over $\mathbb{Z}$ .

The correctness of the algorithm relies on the fact that a cochain $a$ such that $b=\Delta_{Am}^{1}(a)$ exists and may be found in the group of $S^{(1)}$ -units of $F^{\otimes 2}$ , which is the content of Theorem 4.11. ∎

Theorem 4.13.

Assuming GRH, there exists a polynomial quantum algorithm which, give a number field $k$ and an algebra $A\simeq M_{n}(k)$ , computes an explicit algorithm from $A$ to $M_{n}(k)$ .

Proof.

This is simply a combination of Theorems 3.10 and 4.12. Indeed, using Algorithm 1, one may compute an étale $k$ algebra $F=k[X]/P$ , a cocycle $c\in\mathbb{Z}^{2}(k,F)$ and an isomorphism $A\simeq A(F,c)$ . Since $A$ is isomorphic to $M_{n}(k)$ , the cocycle $c$ is in fact a coboundary. Then, a trivialisation of $c$ may be computed using Algorithm 2. Applying 3.7, we obtain an explicit isomorphism $A(F,c)\simeq A(F,\mathbf{1})$ . Finally, an isomorphism $A(F,\mathbf{1})\simeq M_{n}(k)$ may easily be computed using Remark 3.5. ∎

References

[1] Adamson, I. T. Cohomology theory for non-normal subgroups and non-normal fields. Glasg. Math. J. 2, 2 (1954), 66–76.
[2] Amitsur, S. A. Simple algebras and cohomology groups of arbitrary fields. Trans. Amer. Math. Soc. 90 (1959), 73–112.
[3] Auslander, M., and Goldman, O. The brauer group of a commutative ring. Trans. Amer. Math. Soc. 97, 3 (1960), 367–409.
[4] Azumaya, G. On maximally central algebras. Nagoya Math. J. 2 (1951), 119–150.
[5] Bach, E. Explicit bounds for primality testing and related problems. Math. Comp. 55, 191 (1990), 355–380.
[6] Bauch, J., Bernstein, D. J., de Valence, H., Lange, T., and Van Vredendaal, C. Short generators without quantum computers: the case of multiquadratics. In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part I (2017), Springer, pp. 27–59.
[7] Biasse, J.-F. Subexponential time relations in the class group of large degree number fields. Adv. Math. Commun. 8, 4 (2014), 407–425.
[8] Biasse, J.-F., Espitau, T., Fouque, P.-A., Gélin, A., and Kirchner, P. Computing generator in cyclotomic integer rings. In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part I (Cham, 2017), Springer, pp. 60–88.
[9] Biasse, J.-F., and Song, F. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (USA, 2016), SODA ’16, Society for Industrial and Applied Mathematics, p. 893–902.
[10] Bourbaki, N. Algebra I. Chapters 1–3. Elements of Mathematics (Berlin). Springer-Verlag, Berlin, 1998.
[11] Cassels, J. W. S., and Fröhlich, A., Eds. Algebraic number theory (1967), Academic Press, London; Thompson Book Co., Inc., Washington, DC.
[12] Chase, S. U., and Rosenberg, A. Amitsur cohomology and the brauer group. In Galois theory and cohomology of commutative rings, vol. 1 of Memoirs of the Americam Mathematical Society. American Mathematical Society, 1965, pp. 20–65.
[13] Cohen, H. A course in computational algebraic number theory, vol. 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.
[14] Cohen, H. Advanced topics in computational number theory, vol. 193. Springer, New-York, NY, 2012.
[15] Colliot-Thélène, J.-L., and Skorobogatov, A. N. The Brauer-Grothendieck Group. Springer Cham, 2021.
[16] Cremona, J., Fisher, T., O’Neil, C., Simon, D., and Stoll, M. Explicit n-descent on elliptic curves, i. algebra. J. Reine Angew. Math. 2008, 615 (2008), 121–155.
[17] Cremona, J., Fisher, T., O’Neil, C., Simon, D., and Stoll, M. Explicit n-descent on elliptic curves, ii. geometry. J. Reine Angew. Math. 2009, 632 (2009), 63–84.
[18] Cremona, J., Fisher, T., O’Neil, C., Simon, D., and Stoll, M. Explicit n-descent on elliptic curves iii. algorithms. Math. Comp. 84, 292 (2015), 895–922.
[19] Cremona, J., and Rusin, D. Efficient solution of rational conics. Math. Comp. 72, 243 (2003), 1417–1441.
[20] Csahók, T., Kutas, P., Montessinos, M., and Zábrádi, G. Explicit isomorphisms of quaternion algebras over quadratic global fields. Research in Number Theory 8, 4 (2022), 77.
[21] De Graaf, W. A., Harrison, M., Pílniková, J., and Schicho, J. A lie algebra method for rational parametrization of severi–brauer surfaces. J. Algebra 303, 2 (2006), 514–529.
[22] de Graaf, W. A., and Ivanyos, G. Finding splitting elements and maximal tori in matrix algebras. In Interactions Between Ring Theory and Representations of Algebras, F. van Oystaeyen and M. Saorin, Eds. CRC Press, 2000, ch. 7, pp. 95–105.
[23] Eberhard, S. The characteristic polynomial of a random matrix. Combinatorica 42, 4 (2022), 491–527.
[24] Eisenträger, K., Hallgren, S., Kitaev, A., and Song, F. A quantum algorithm for computing the unit group of an arbitrary degree number field. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, NY, USA, 2014), STOC ’14, Association for Computing Machinery, p. 293–302.
[25] Fieker, C. Minimizing representations over number fields ii: Computations in the brauer group. J. Algebra 322, 3 (2009), 752–765.
[26] Fisher, T. Explicit 5-descent on elliptic curves. Open Book Ser. 1, 1 (2013), 395–411.
[27] Fisher, T. Higher descents on an elliptic curve with a rational 2-torsion point. Math. Comp. 86, 307 (2017), 2493–2518.
[28] Fisher, T., and Newton, R. Computing the cassels-tate pairing on the 3-selmer group of an elliptic curve. Int. J. Number Theory 10, 07 (2014), 1881–1907.
[29] Ford, T. J. Separable Algebras, vol. 183. American Mathematical Society, 2017.
[30] Garg, A., Gupta, N., Kayal, N., and Saha, C. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Dagstuhl, Germany, 2019), C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, Eds., vol. 132 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 62:1–62:15.
[31] Gille, P., and Szamuely, T. Central simple algebras and Galois cohomology, vol. 165. Cambridge University Press, Cambridge, 2017.
[32] Gómez-Torrecillas, J., Kutas, P., Lobillo, F. J., and Navarro, G. Primitive idempotents in central simple algebras over fq (t) with an application to coding theory. Finite Fields Appl. 77 (2022), 101935.
[33] Hallgren, S. Fast quantum algorithms for computing the unit group and class group of a number field. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (New York, NY, 2005), STOC ’05, Association for Computing Machinery, p. 468–474.
[34] Ivanyos, G., Kutas, P., and Rónyai, L. Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_{q}(x)$ . Found. Comput. Math. 18 (2018), 381–397.
[35] Ivanyos, G., Kutas, P., and Rónyai, L. Explicit equivalence of quadratic forms over $\mathbb{F}_{q}(t)$ . Finite Fields Appl. 55 (2019), 33–63.
[36] Ivanyos, G., Lelkes, Á., and Rónyai, L. Improved algorithms for splitting full matrix algebras. JP J Algebra, Number Theory Appl. 28, 2 (2013), 141–156.
[37] Ivanyos, G., Rónyai, L., and Schicho, J. Splitting full matrix algebras over algebraic number fields. J. Algebra 354 (2012), 211–223.
[38] Jacobson, N. Finite-dimensional division algebras over fields. Springer-Verlag, Berlin, 1996.
[39] Kutas, P. Splitting quaternion algebras over quadratic number fields. J. Symbolic Comput. 94 (2019), 173–182.
[40] Kutas, P., Montessinos, M., Zábrádi, G., and Csahók, T. Finding nontrivial zeros of quadratic forms over rational function fields of characteristic 2. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2022), ISSAC ’22, Association for Computing Machinery, p. 235–244.
[41] Lenstra, A. K. Factoring polynomials over algebraic number fields. In Computer Algebra: EUROCAL’83, European Computer Algebra Conference London, England, March 28–30, 1983 Proceedings (Berlin, Heidelberg, 1983), Springer, pp. 245–254.
[42] Lenstra, Jr., H. W., and Silverberg, A. Algorithms for commutative algebras over the rational numbers. Found. Comput. Math. 18, 1 (2018), 159–180.
[43] Pílniková, J. Trivializing a central simple algebra of degree 4 over the rational numbers. J. Symbolic Comput. 42, 6 (2007), 579–586.
[44] Rónyai, L. Computing the structure of finite algebras. J. Symbolic Comput. 9, 3 (1990), 355–373.
[45] Rosenberg, A., and Zelinsky, D. On amitsur’s complex. Trans. Amer. Math. Soc. 97 (1960), 327–356.
[46] Simon, D. Solving norm equations in relative number fields using $S$ -units. Math. Comp. 71, 239 (2002), 1287–1305.
[47] The PARI Group. PARI/GP version 2.15.5. Univ. Bordeaux, 2023. available from http://pari.math.u-bordeaux.fr/.
[48] Voight, J. Quaternion algebras. Springer, Cham, 2021.
[49] Yan, J. Computing the Cassels-Tate Pairing for Jacobian Varieties of Genus Two Curves. PhD thesis, Apollo - University of Cambridge Repository, 2021.

Efficient computations in central simple algebras using Amitsur cohomology

Abstract

1 Introduction

1.1 Our contributions

1.2 Related works

2 Preliminaries

2.1 Algorithmic preliminaries

2.1.1 Computational model

2.1.2 Computational representations of algebras

2.1.3 Computing rings of integers and factoring ideals

Fact 2.1.

Proof.

Fact 2.2.

2.1.4 A polynomial quantum algorithm for computing class groups and groups of SS-units in number fields

Fact 2.3 ([9, Fact 4.1]).

Proof.

Fact 2.4.

Fact 2.5.

Fact 2.6.

Theorem 2.7.

2.2 Brauer factor sets and central simple algebras

Lemma 2.8.

Proof.

Definition 2.9.

Remark 2.10.

Proposition 2.11.

Proof.

Definition 2.12.

Fact 2.13.

Proof.

Remark 2.14.

3 Explicit computations with Amitsur cohomology

Definition 3.1.

3.1 Amitsur cohomology and central simple algebras

Lemma 3.2.

Proof.

Definition 3.3.

Proposition 3.4.

Proof.

Remark 3.5.

Theorem 3.6.

Proof.

Corollary 3.7.

Proof.

Remark 3.8.

3.2 Computational representation of Amitsur cohomology

3.3 Representing central simple algebras as Amitsur algebras

Lemma 3.9.

Proof.

Theorem 3.10.

Proof.

4 Trivialisation of Amitsur cocycles

4.1 Divisors of étale algebras

Remark 4.1.

Definition 4.2.

Lemma 4.3.

Proof.

Proposition 4.4.

Proof.

Definition 4.5.

Proposition 4.6.

Proof.

Proposition 4.7.

Proof.

4.2 An algorithm for trivialising Amitsur coboundaries over a number field

Lemma 4.8.

Proof.

Lemma 4.9.

Lemma 4.10.

Proof.

Theorem 4.11.

Proof.

Theorem 4.12.

Proof.

Theorem 4.13.

Proof.

References

2.1.4 A polynomial quantum algorithm for computing class groups and groups of $S$ -units in number fields