Explicit computation of the first étale cohomology on curves
Jinbi Jin
math.AG 14F20, 14Q05

STN-OCR: A single Neural Network for Text Detection and Text Recognition
    C. Conti^4,5
    December 30, 2023
========================================================================





  §.§.§ Abstract


In this paper, we describe an algorithm that, for a smooth connected curve X over a field k with normal completion having arithmetic genus p_a(X), a finite locally constant sheaf A on X_ of abelian groups of torsion invertible in k, represented by a smooth curve with normal completion having arithmetic genus p_a( A) and degree n over X, computes the first étale cohomology ^1(X_k^,, A) and the first étale cohomology with proper support ^1_c(X_k^,, A) as sets of torsors, in arithmetic complexity exponential in n^log n, p_a(X), and p_a( A).
This is done via the computation of a groupoid scheme classifying the relevant torsors (with extra rigidifying data).



  §.§.§ Acknowledgements


This paper is in part based on Chapter 3 of the author's dissertation, which was funded by the Netherlands Organisation for Scientific Research (project no. 613.001.110), and the author thanks his supervisors Bas Edixhoven and Lenny Taelman for their guidance during the author's PhD candidacy.
The author also thanks the Max-Planck-Institut für Mathematik in Bonn for their support during the production of this paper.



§ INTRODUCTION


The motivating question for this paper is the following;  this question is posed e.g. by Poonen, Testa, and van Luijk in <cit.>.

 
  Is there an algorithm that takes an algebraic variety X over a field k, and a positive integer n invertible in k, and computes (k^/k)-modules isomorphic to the étale cohomology groups ^q(X_k^,, Z/n  Z) for q=0,1,…,2 X?


We assume affine schemes of finite presentation over some base ring R to be given by generators and relations over R, and we assume X to be given by a gluing datum of affine varieties over k.
The output will be given as a pair (l,X) of a Galois extension l/k and a finite (l/k)-set X.
<cit.> guarantees that in the situation of this question, the groups ^q(X_k^,, Z/n  Z) are indeed finite.

The existence of an algorithm as in the question computing the étale cohomology groups in time polynomial in n for a fixed variety over Q implies, via the Lefschetz trace formula <cit.> and by the argument of <cit.>, the computation of the number of F_q-points of some fixed finite type scheme X (over Z) in time polynomial in log q.
Here, we note that the problem of computing #X( F_q) has many efficient solutions in practice, see e.g. <cit.>, <cit.>, and <cit.>;  however, none of them run in time polynomial in the characteristic of the finite field.
One other application of a positive answer to the question above is the computation of Néron-Severi groups by Poonen, Testa, and van Luijk in <cit.> using the computation of the étale cohomology groups.

<ref> is already known to have a positive answer.
In 2015, Poonen, Testa, and van Luijk, in the aforementioned article <cit.>, showed that the étale cohomology groups are computable if X is a smooth, projective, geometrically irreducible variety over a field of characteristic 0.
Later that year, Madore and Orgogozo <cit.> showed that they are computable for any variety over any field, and, assuming computations with constructible sheaves can be performed, with coefficient sheaf any constructible sheaf of abelian groups (of torsion invertible in the base field).
However, both of these results are fundamentally merely computability results, without any bounds on the complexity, even for a fixed instance.

So a natural extension of <ref> is (in addition to allowing more general coefficients) to also ask for explicit upper bounds for the complexity;  beyond the classical case of smooth curves with constant coefficients, the author doesn't know of any such result.
In this paper, we will describe an algorithm computing, for smooth connected curves, the first étale cohomology group (proper support or not) with coefficients in a finite locally constant sheaf of abelian groups (of torsion invertible in k), together with theoretical upper bounds for the complexity.

We will assume the field k is given together with black box field operations (see <ref> for more details) and we measure the complexity only in the number of field operations performed.
While this is a good approximation for the time complexity in case k is finite, for infinite k this is usually not the case because of coefficient size growth.
Algorithms will be deterministic (except for the use of the black boxes);  for an actual implementation of the algorithm to be presented, it may be more efficient in practice to use randomised algorithms.
Moreover, the choice of algorithms is motivated by their theoretical worst-case complexities;  for an actual implementation, it may be significantly more efficient in practice to use different algorithms than the ones used in this paper.

With this in mind, let us state this paper's main theorem, deferring the description of the in- and output mainly to <ref> and <ref>.

 
  There exist an algorithm that takes as input a smooth connected curve X over k, and a (curve representing a) finite locally constant sheaf A of abelian groups of degree n over X with n invertible in k, and return as output ^1(X_k^, A|_X_k^) (resp. ^1_c(X_k^, A|_X_k^)) as (k^/k)-modules in a number of field operations exponential in n^log n, p_a(X), and p_a( A), where p_a denotes the arithmetic genus of the normal completion.


More precise (and slightly more general) versions of this theorem will be given in <ref> and <ref>.



§ THE GEOMETRIC IDEA BEHIND THE ALGORITHM


Let X be a smooth connected curve over a field k, and let G be a finite locally constant sheaf of groups.
Then the set ^1(X_k^, G|_X_k^), resp. ^1_c(X_k^, G|_X_k^), is the set of isomorphism classes of G-torsors on X_k^, resp. the set of isomorphism classes of j_! G-torsors on X_k^.
Here, j  X →X is the open immersion of X into its normal completion X.


  If G is a sheaf of abelian groups, a priori we have two possible definitions of j_! G;  one arising from viewing j_! as the left adjoint of j_* on the category of sheaves of groups, and one arising from viewing j_! as the left adjoint of j_* on the category of sheaves of abelian groups.
  Let us call these j^G_!  G and j^A_!  G for now.
  There is a natural map j^G_!  G → j^A_!  G, which induces an isomorphism on stalks since j is an open immersion (and direct sums of zero, resp. one object in the category of groups and that of abelian groups have the same underlying sets).
  Hence j^G_!  G = j^A_!  G, so there is no confusion possible if we just write j_!  G in this case, like we did above.


Now, in short, the idea behind the algorithm is to compute a moduli scheme of torsors with some additional structure (which is to be specified) and use this moduli scheme to compute the first cohomology.
The moduli space in question is constructed in <ref>.

We describe this idea in some more detail below, using the language of stacks.

Let T be the stack on (/X)_ of G-torsors, resp. the stack on (/X)_ of j_! G-torsors;  note that this stack is presented by the group(oid) scheme G → X, resp. j_! G →X.
Let f be the structure morphism X → k, resp. the structure morphism X→ k, and let p denote the morphism from the big étale topos to the small étale topos for which p_* is the restriction to the small site.
Note that for this p, the functor p^-1 is the espace étalé functor.
Let f_,* and f_,* denote the big and small pushforward, respectively.

We then have a stack f_,*p_*  T = p_*f_,* T on ( k)_, to which we can attach the sheaf π_0(f_,*p_*  T) on ( k)_, and a morphism f_,*p_*  T →π_0(f_,*p_*  T) of stacks on ( k)_.
The Galois set to be computed now corresponds to the sheaf π_0(f_,*p_*  T) on ( k)_, or in other words, to the étale k-scheme p^-1π_0(f_,*p_*  T).

We show in <ref> that the diagonal of f_,* T is representable and finite étale, which simply means that for any k-scheme S and any two objects X,Y of f_,* T(S), the corresponding sheaf _f_,* T(S)(X,Y) on (/k)_ is representable by a finite étale S-scheme.

In <ref> we compute a groupoid scheme R ⇉ U with R and U affine schemes of finite type over k, together with an obvious (non-explicit) morphism [ U/ R] → f_,* T of stacks on (/k)_.
There, we also show that p^-1p_*[ U/ R] → p^-1f_,*p_*  T is an equivalence (after some purely inseparable base change, but we ignore this technical point for now), and that the morphisms R ⇉ U are smooth and have geometrically irreducible fibres.

Hence we are (after some purely inseparable base change) in the situation of the following proposition.

 
  Let T be a stack on (/k)_ of which the diagonal is representable and finite étale.
  Let R ⇉ U be a groupoid scheme such that both morphisms R → U are smooth and have geometrically connected fibres, and such that R and U are of finite type over k.
  Let [ U/ R] → T be a morphism of stacks on (/k)_ such that p^-1p_*[ U/ R] → p^-1p_*  T is an equivalence, or in other words, such that for each separable extension l/k, the functor [ U/ R](l) → T(l) is an equivalence.
  Then the map U(k^) →π_0( T)(k^) is a (k^/k)-equivariant surjection, and factors through an isomorphism π_0( U) →π_0( T).

  If in addition the morphisms R → U have geometrically irreducible fibres, then the connected components of U_k^ are irreducible.



  First note that the equivalence p^-1p_*[ U/ R] → p^-1p^*  T induces a surjective (k^/k)-equivariant map U(k^) →π_0( T)(k^).

  Let x ∈ U(k^) and let j  U → U_k^ be the open immersion of the connected component U containing x into U_k^.
  Moreover, let f  U → k^ denote the structure morphism, and let p  U_k^→ U be the projection morphism.
  Let Y ∈ U( U) denote the “universal object”; i.e. the object corresponding to the identity map on U.

  Define Y_1 = j^-1p^-1 Y, Y_2 = f^-1 x^-1 Y ∈ U(U), and consider their images in T(U).
  Then _ T(U)(Y_1,Y_2) is representable by a finite étale U-scheme by assumption.

  Moreover, it is surjective as by construction _ T(U)(Y_1,Y_2)( x) is non-empty and U is connected.
  Hence for any point x'∈ U(k^), the set _ T(U)(Y_1,Y_2)(x') is non-empty as well.
  Therefore the morphism U(k^) →π_0( T)(k^) factors through a surjective (k^/k)-equivariant map π_0( U)(k^) →π_0( T)(k^).
  In other words, the morphism π_0( U) →π_0( T) of sheaves on ( k)_ is surjective.

  Denote the morphisms R → U by α and ω.
  As α and ω have geometrically connected fibres, it follows that the morphism π_0( U) →π_0( T) is an isomorphism; if x,  x' ∈ U(k^) are isomorphic, then x' ∈α*[big]ω^-1( x), hence x,  x' lie in the same geometric connected component of U.

  Finally, if α and ω have geometrically irreducible fibres, then the same argument implies that every geometric connected component of U is irreducible.


As a corollary, we see that in <ref> any set X of points l_i → U (with l_i/k finite algebraic) such that every connected component of U contains a point X induces a finite cover of π_0( T).
We describe in <ref> how to use such a set X to compute π_0( T).



§ PRELIMINARIES
 

In this paper we will mainly consider generic field algorithms; i.e. algorithms that take a finite number of bits and a finite number of a field k, which are only allowed to operate on the field elements through a number of black box operations, and, aside from the black box operations, are deterministic.
The assumptions that follow here are essentially the assumptions as mentioned in <cit.>.

First, we assume the constants 0 and 1 (in k) and the characteristic exponent p (in Z) are given.
Moreover, we assume the imperfectness degree p^e of k to be finite, and that k^1/p/k is given explicitly as a finite k-algebra (i.e. as a k-vector space with given unit and multiplication table).

In this paper these black box operations are:

  
  * =, which takes x,y ∈ k, and returns 1 if x=y, and 0 if x ≠ y;
  
  * -, which takes x ∈ k, and returns -x;
  
  * ·^-1, which takes x ∈ k, and returns nothing if x=0, and x^-1 if x ≠ 0;
  
  * +, which takes x,y ∈ k, and returns x+y;
  
  * ×, which takes x,y ∈ k, and returns xy;
  
  * ·^1/p, which takes x ∈ k, and returns x^1/p∈ k^1/p;
  
  * F, which takes a polynomial f ∈ k[x], and returns its factorisation into irreducibles in k[x].



  For any field finitely generated over a finite field or Q, there are algorithms for each of the above black box operations, however, the most efficient implementations of the factorisation algorithm for finite fields are randomised.


To such a generic field algorithm we attach a number of functions (from the set of inputs to N).

  
  * The bit-complexity N_; for an input I, the number N_(I) is the number of bit-operations the algorithm performs when given I.
  
  * The arithmetic complexity N_; for an input I, the number N_(I) is the number of black box operations the algorithm performs when given I.

We will usually not mention the bit-complexity of the algorithms in this paper;  in all cases, the bit-complexity will be small compared to the arithmetic complexity.
As is customary, as a measure of size for inputs, we take the pair (b,f), where b is the number of bits in the input, and f is the number of field elements in the input;  so for Φ a function from the set of inputs to N, we will denote by Φ(b,f) the maximum of the Φ(I) with I ranging over all the inputs with at most b bits and f field elements.

We note that a lot of linear algebraic operations, like matrix addition, matrix multiplication, computation of characteristic polynomial, and by extension, reduced row echelon form, rank, kernels, images, quotients, etc. can all be performed in arithmetic complexity polynomial in the size of the input.

By <cit.>, the primary decomposition of a finite k-algebra A can also be computed in arithmetic complexity polynomial in [A:k], and if k is perfect, the same holds for the computation of nilradicals.
In fact, in our case <cit.> computes an l-basis (and therefore a k-basis) for the nilradical of A ⊗_k l (where l = k^1/p^*log_p [A:k]), and therefore also a k-basis for the nilradical of A, in arithmetic complexity polynomial in [A:k]^e+1.

Moreover, using the criteria that a reduced finite k-algebra A is separable if [A:k] < p, and if and only if A is spanned over k by t_i^p for t_i any k-basis for A, one can compute separable closures of k in finite field extensions l in arithmetic complexity polynomial in [l:k], using the obvious recursive algorithm.

By <cit.> we have algorithms which compute for a finite field extension l/k the extension l^1/p/l and the operations listed above; aside from the computation of l^1/p/l, that of characteristic roots, which have arithmetic complexity polynomial in [l:k]^e+1, and that of factorisation, which has arithmetic complexity polynomial in [l:k]^e+1 and the degree of the polynomial to be factored, every operation has arithmetic complexity polynomial in [l:k].
Moreover, l has the same characteristic exponent and imperfectness degree as k.

Now consider the purely transcendental extension k(x)/k.
We present its elements by pairs of polynomials;  for f,g ∈ k[x] we set the height of f/g to be h(f/g) = max( f, g).
Then note that for k(x)/k, we have k(x)^1/p = k^1/p(x^1/p) and therefore an obvious k(x)-basis for k(x)^1/p, and we can compute the listed operations for elements of k(x) of height at most h in arithmetic complexity polynomial in h(x).
(Again, with the exceptions of characteristic roots, which has arithmetic complexity polynomial in h(x)^e+2 and polynomial factorisation, which has arithmetic complexity polynomial in h(x)^e+2 and the degree of the polynomial to be factored, see e.g. <cit.>.)

As is customary, we will use the standard big-oh notation when bounding complexities; moreover, we will use O(x,y) as a shorthand for O*[big]max(x,y).



§ PARAMETRISING MORPHISMS OF MODULES
 

We will use the following characterisation of isomorphism classes of vector bundles over P^1_k with k a field.


  Let k be a field, and let E be a vector bundle on P^1_k.
  Then there exists an up to permutation unique finite sequence (a_i)_i=1^s of integers such that
  
    E ⊕_i=1^s  O_ P^1_k(a_i).



This motivates the following definition.


  Let S be a scheme, and let a be a finite sequence of integers of length s.
  The standard module of type a on S is the O_ P^1_S-module
  
    O_ P^1_S(a) = ⊕_i=1^s  O_ P^1_S(a_i).



So every vector bundle E over P^1_k is isomorphic to a standard module over k, say of type a; in this case, we simply say that E has type a.

Let, for finite sequences a,b of integers, of lengths s,t, respectively, H_a,b define the functor ^→ sending S to _ O_ P^1_S*[big] O_ P^1_S(b), O_ P^1_S(a).
Moreover, let N(a,b) = ∑_i=1,j=1^s,tmax(a_i-b_j+1,0).

Then the functor H_a,b is representable by A^N(a,b):  in fact, as

    _ O_ P^1_S*[big] O_ P^1_S(b_j), O_ P^1_S(a_i) =  O(S)[x,y]_a_i-b_j

functorial in S, we get an identification

    _ O_ P^1_S*[big] O_ P^1_S(b), O_ P^1_S(a) = *[Big]M ∈_s × t*[big] O(S)[x,y] : M_ij∈ O(S)[x,y]_a_i - b_j,

and under this identification, all the relevant operations on morphisms of standard modules (i.e. identity map, composition, direct sum, tensor product, dual, exterior powers) correspond to their usual counterparts on matrices.
In particular, if these operations are viewed as operations on the representing scheme A^N(a,b), then the degrees of the polynomials defining them are as expected.

To an element of H_a,b(S), one way to give its fibre at 0 ∈ P^1_S is by substituting (0,1) for (x,y), and one way to give its fibre at ∞∈ P^1_S is by substituting (1,0) for (x,y).
Moreover, a way to give the first infinitesimal neighbourhood at ∞∈ P^1_S is by substituting x = 1 and setting y^2 = 0.



§ TORSORS
 

A curve over a field k in this paper is a separated k-scheme of finite type, of pure dimension 1 over k.

Consider the following situation.

Let k be a field, let f  X → k be a smooth connected curve, let i  Z → X be a closed immersion, let j  U → X be its open complement, and let G be a finite locally constant sheaf of groups on U_.
We wish to compute R^1f_*j_!  G (or equivalently, ^1(X_k^,,j_! G) as a Galois set) under some minor conditions, and as stated before, we will do this by reduction to a computation with standard modules.



 §.§ j_! G-torsors and recollement


We first recall recollement.


  Let X be a scheme, let i  Z → X be a closed immersion, and let j  U → X be its open complement.

  Define the category _Z,U(X_) as follows.
  The set of objects of _Z,U(X_) is the set of triples ( F_Z, F_U,ϕ) of a sheaf F_Z on Z_, a sheaf F_U on U_, and a morphism ϕ F_Z → i^-1j_*  F_U.
  For objects ( F_Z, F_U,ϕ) and ( F'_Z, F'_U,ϕ') of _Z,U(X_), the set of morphisms from ( F_Z, F_U,ϕ) to ( F'_Z, F'_U,ϕ') is the set of pairs (f_Z,f_U) of a morphism f_Z  F_Z → F'_Z and a morphism f_U  F_U → F'_U such that the following diagram commutes.
  
    F_Z [d,"ϕ"'] [r,"f_Z"]     F'_Z [d,"ϕ'"] 
    
          i^-1j_*  F_U [r,"i^-1j_*(f_U)"']     i^-1j_*  F'_U




  Let X be a scheme, let i  Z → X be a closed immersion, and let j  U → X be its open complement.

  Then the functor (X_) →_Z,U(X_) sending F to *[big]i^-1 F,j^-1 F,i^-1(υ), where υ F → j_*j^-1 F is the unit map of the adjoint pair (j^-1,j_*) of functors, is an equivalence of categories, and a quasi-inverse _Z,U(X_) →(X_) is given by sending ( F_Z, F_U,ϕ) to i_* F_Z ×_i_*(ϕ),i_*i^-1j_*  F_U,υ j_*  F_U, where υ j_*  F_U → i_* i^-1 j_*  F_U is the unit map of the adjoint pair (i^-1,i_*) of functors.


Note that the functor i^-1j_* is left exact, hence commutes with finite limits.
Let T denote the category of j_! G-torsors on X_, and let T_Z,U denote the category of which the objects are pairs ( F,s) of a G-torsor F on U_, and a section s ∈ i^-1j_* F(Z), and in which the morphisms ( F,s) → ( F',s') are the morphisms f  F → F' such that i^-1j_*(f) sends s to s'.


  Let X be a scheme, let i  Z → X be a closed immersion, and let j  U → X be its open complement.
  Let G be a sheaf of groups on U_.
  The rule attaching to a j_! G-torsor F on X_ the pair *[big]j^-1 F,i^-1(υ), where υ F → j_*j^-1 F denotes the unit map of the adjoint pair (j^-1,j_*) of functors, defines an equivalence T → T_Z,U of categories.



  First, note that the sheaf j_!  G is under recollement equivalent to the triple (1, G,1).

  Now giving a j_! G-action ρ on a sheaf F on X_ is equivalent to giving (i^-1 F,j^-1 F,i^-1(υ)) together with an action of G on j^-1 F; the commutativity of
  
    1 × i^-1 F [d,"1 ×i^-1(υ)"'] [r,"ρ_Z"]     i^-1 F [d,"i^-1(υ)"] 
    
          i^-1j_*  G × i^-1j_*j^-1 F [r,"i^-1j_*(ρ_U)"']     i^-1j_*j^-1 F

  is automatic since both ρ_Z and i^-1j_*(ρ_U) are group actions.
  (Of course, one can also deduce this equivalence by noting that a morphism j_! G →( F) is equivalent to a morphism G → j^-1( F) = ( F_U).)

  Now F is a j_! G-torsor if and only if the map j_! G × F → F × F given on local sections by (g,s) ↦ (s,gs) is an isomorphism, and F locally has a section.
  This is equivalent to the following.
  
    
  * i^-1 F is the terminal sheaf on Z_; therefore i^-1(υ) is an element of i^-1j_*  F(Z), and it follows that the given rule indeed defines a functor;
    
  * j^-1 F is a G-torsor on U_,
  
  so the given rule defines an equivalence, as desired.




 §.§ Pushforward and normalisation


Next, we consider a description of the pushforward of a finite locally constant sheaf along certain open immersions.
This is mostly well-known, but the author doesn't know of a reference, so proofs are included here for completeness.

Recall that, for a scheme X, the category of sheaves on X_ is equivalent to that of algebraic spaces étale over X.
Quasi-inverses are given by the functor sending an algebraic space étale over X to its functor of points, and the functor sending a sheaf on X_ to its espace étalé.
By descent, finite locally constant sheaves on X_ are precisely those of which the espace étalé is a finite étale X-scheme.

 
  Let X be a scheme, and let j  U → X be a quasi-compact open immersion such that the normalisation of X in U is X.
  Let F be a finite locally constant sheaf on U_, or equivalently, a finite étale U-scheme.
  Let F be the normalisation of X in F.
  Then for all étale X-schemes T, we have j_* F(T) =  F(T) functorial in T.



  First of all, note that we may restrict ourself to étale X-schemes T that are affine, and therefore to quasi-compact separated étale X-schemes T.
  So let T be an étale quasi-compact separated X-scheme.
  Let T be the normalisation of X in T, and let U ×_X T be the normalisation of X in U ×_X T.
  Then j_* F(T) =  F(U ×_X T), and we have a map F(U ×_X T) → F(U ×_X T).
  Since for every Y-morphism U ×_X T→ F, the composition with U ×_X T →U ×_X T factors through F (as F is a finite étale X-scheme), it follows that F(U ×_X T) =  F(U ×_X T).

  Now note that since normalisation commutes with smooth base change (see e.g. <cit.>), it follows that the normalisation of T in U ×_X T is simply T.
  Therefore U ×_X T→ T is an isomorphism, and we have F(U ×_X T) =  F(T) =  F(T), as desired.



  Let X be a scheme, and let j  U → X be a quasi-compact open immersion such that the normalisation of X in U is X.
  Then for all finite sets F, we have j_* F = F.



  Let k be a field, let X be a k-scheme of finite type, and let j  U → X be an open immersion such that the normalisation of X in U is X.
  Let F be a finite locally constant sheaf on U_, or equivalently, a finite étale U-scheme.
  Then j_*  F is representable by an étale, quasi-compact, separated X-scheme.



  First note that by <cit.> j_*  F is constructible, i.e. of finite presentation as an X-space.

  Note that F is finite locally constant, so F × F is the disjoint union of the diagonal and its complement, inducing a morphism F × F → Z/2  Z such that the equaliser with the constant map with value 0 is the diagonal.
  Applying the left exact functor j_* to this gives a morphism j_*  F × j_*  F → j_* ( Z/2  Z) =  Z/2  Z such that the equaliser with the constant map with value 0 is the diagonal.
  Therefore j_*  F is separated as an X-space.

  It follows by <cit.> that j_*  F is representable by an étale, quasi-compact, separated X-scheme.



  Let k be a field, let X be a k-scheme of finite type, and let j  U → X be an open immersion such that the normalisation of X in U is X.
  Let F be a finite locally constant sheaf on U_, or equivalently, a finite étale U-scheme.
  Let F be the normalisation of X in F.
  Then F is the normalisation of X in j_*  F.



  First note that we have a canonical morphism j_* F → F corresponding to the identity section of j_* F.
  Let j_* F → Y → X be a factorisation with Y → X integral.
  As F is the normalisation of X in F, it follows that there exists a unique morphism F→ Y such that the diagram
  
    F [d] [r]     F[d] [dl] 
    
          Y [r]     X

  commutes.
  We show that this morphism also makes the diagram
  
    j_*  F [r] [d]     F[dl] 
    
          Y

  commute.
  Let T be an étale quasi-compact separated X-scheme, and consider the following diagram.
  
    j_*  F(T) [r] [d]     F(T) [dl] 
    
          Y(T)

  As the normalisations of X in T and U ×_X T are equal, as in the proof of <ref>, the commutativity of this diagram is equivalent to the commutativity of the following one.
  
    F(U ×_X T) [r] [d]     F(U ×_X T) [dl] 
    
          Y(U ×_X T)

  It follows that the commutativity of (<ref>) holds when restricted to X_.

  Therefore, applying this to the identity section on j_*  F, it follows that (<ref>) itself commutes.


By Zariski's Main Theorem, we have the following.


  The canonical morphism j_* F → F is an open immersion identifying j_*  F with the étale locus of F over X.



  The étale locus V of F over X is open in F and étale over X, therefore factors through j_*  F.
  By maximality of V we get j_*  F = V.




 §.§ Galois actions on finite locally constant sheaves


Let X be a scheme, and let Γ be a group acting on X.
Then recall that a Γ-sheaf on X_ is a sheaf F on X_ of which the espace étalé is a Γ-equivariant X-space.

Let X be a connected scheme, let Γ be a finite group, and let f  Y → X be a finite étale connected Galois cover with Galois group Γ.
Note that pullback of sheaves defines an equivalence from the category of sheaves on X_ to that of Γ-sheaves on Y_.
A quasi-inverse is given in terms of sheaves by sending F to the sheaf of Γ-invariants of f_*  F; in terms of espaces étalés, it sends an algebraic space Z étale over Y to the quotient Γ\ Z.

If G is a finite locally constant sheaf of groups on X_ such that f^-1 G is constant, let G be the group of connected components of f^-1 G, and note that Γ acts on G by automorphisms.
Therefore we see that a finite locally constant sheaf on X_ with G-action corresponds to a Γ- and G-equivariant finite étale Y-scheme.

Let us now apply this to the following situation.

 
  Let k be a field.
  Suppose we have a finite group Γ, and a diagram of schemes of finite type over k
  
    V [d,"g"'] [r,"j'"]     Y [d,"f"]     W [d,"h"] [l,"i'"'] 
    
          U [r,"j"']     X     Z [l,"i"]

  where U and X are connected, g is finite étale Galois with Galois group Γ, Y is the normalisation of X in V, W = Y ×_X Z, and j is the open complement of i.
  Let G be a finite locally constant sheaf of groups on U such that g^-1 G is constant, say with group of connected components G.


Let T_Z,U be as in the previous section, and let T_W,Y^Γ be the category of which the objects are pairs ( F,s) of a Γ-equivariant G-torsor F on Y_, and a Γ-equivariant section s ∈ (i')^-1 F(W), and in which the morphisms ( F,s) → ( F',s') are the Γ-equivariant morphisms f  F → F' such that (i')^-1(f) sends s to s'.

 
  In <ref>, the rule attaching to a pair ( F,s) of a G-torsor F and a section s ∈ i^-1j_* F(Z) the pair (j'_*g^-1 F,s) defines an equivalence T_Z,U→ T_W,Y^Γ of categories.



  First note that giving a G-torsor F on U_ is equivalent to giving the Γ-equivariant G-torsor g^-1 F on V_.
  Moreover, giving the section s  Z → i^-1j_*  F is the same as giving a Γ-invariant section Z → i^-1j_* g_* g^-1 F = i^-1f_*j'_*g^-1 F = h_* (i')^-1 j'_* g^-1 F, where the last step uses proper base change.
  This is the same as giving a Γ-equivariant section W → (i')^-1 j'_* g^-1 F.

  Now j'_*g^-1 F is a Γ-equivariant G-pseudotorsor which étale locally has a section, i.e. a Γ-equivariant G-torsor.
  Therefore giving the pair (g^-1 F,s) is equivalent to giving (j'_*g^-1 F,s), as desired.

 


 §.§ Stacks of torsors


Let S be a scheme.
A topologically finite étale S-scheme T is a morphism T → S that factors as a composition T → T' → S with T' → S finite étale and T → T' a universal homeomorphism.

Let f  X → S be a proper smooth curve, let i  Y → X be a closed immersion, topologically finite étale over S, and let j  U → X denote its open complement.
Write h = fi and g = fj.
Let G be a finite group; if Y is non-empty, we also assume that the order of G is invertible on S.

Let T denote the fppf stack of G-torsors on U_; i.e. its objects are pairs (T, F) of an S-scheme T and a G-torsor F on (U ×_S T)_, and the morphisms (T, F) → (T',  F') are the pairs of a morphism ϕ T → T' and an isomorphism ϕ^-1 F' → F.
We show that T has a representable and finite étale diagonal, or equivalently, the relevant Isom-sheaves are representable by finite étale schemes.

Without loss of generality, and to ease notation a bit, we will only consider the Isom-sheaves on S.
More precisely, let F and F' be G-torsors on U_, and let I denote the sheaf on U_ sending ϕ T → U to the set _T(ϕ^-1 F,ϕ^-1F') of isomorphisms of G-torsors.
We denote by g_,* the big pushforward functor U_→ S_.


  The sheaf g_,* I on S_ is representable by a finite étale S-scheme.



  By the theory of Hilbert schemes, the fppf sheaf g_big,* I is representable by an algebraic space, locally of finite presentation over S, since both F and F' are representable by finite étale algebraic spaces over U.
  Moreover, we easily see that it is formally étale over S, therefore étale over S.
  Hence it is representable by the espace étalé of (g_big,* I)|_S_ = g_*( I|_U_).

  Now we note that I|_U_ is a G-torsor on U_, so its pushforward under g is finite locally constant by <cit.>; this uses the additional assumption on the order of G if Y is non-empty.
  Hence g_big,* I is representable by a finite étale S-scheme.


In addition, let Γ be a finite group acting on G, and on X over S, such that Y (and therefore U) is stable under Γ, and let k  Z → U be a closed immersion stable under Γ, and let l  V → U be its open complement.

Let T' denote the fppf stack of Γ-equivariant l_!G-torsors on U_; i.e. its objects are pairs (T, F) of an S-scheme T and a Γ-equivariant l_!A-torsor F on (U ×_S T)_, and the morphisms (T, F) → (T',  F') are the pairs of a morphism ϕ T → T' and a Γ-equivariant isomorphism ϕ^-1 F' → F.
We show that T' too has a representable and finite étale diagonal.

Again, without loss of generality, we will only consider the relevant Isom-sheaves on S.
Let F and F' be Γ-equivariant l_! G-torsors on U_, and let I' denote the sheaf on U_ sending ϕ T → U to the set of Γ-invariant isomorphisms ϕ^-1 F →ϕ^-1 F' of l_!G-torsors.


  The sheaf g_,* I' on S_ is representable by a finite étale S-scheme.



  By the last step in the proof of <ref>, we see that we can write g_,* I' as a finite limit of finite étale S-schemes, which therefore is finite étale over S as well.


Finally, let k be a field, let f  X → k be a smooth connected curve, let i  Z → X be a closed immersion, and let j  U → X denote its open complement.
Let G be a finite locally constant sheaf of groups on U_, let g  V → U be a finite étale Galois cover with finite Galois group Γ such that g^-1 G is constant, say with Γ-module of connected components G, and let Y be the normal completion of V; by replacing k by a finite purely inseparable extension if necessary, we may assume Y is smooth over k.
Let i'  W → Y be the base change of i to Y, let j'  V → Y be the canonical open immersion, and note that Z and W are automatically topologically finite étale over k.

Now in <ref>, under the additional assumption that X and Y are curves that have smooth normal completions, we see that the stack of j_! G-torsors is equivalent to that of Γ-equivariant j'_! G-torsors by <ref>, which satisfies the condition of <ref> by the above.
We will take this as the starting point of our computation in the next section.



§ COMPUTATION OF A GROUPOID SCHEME
 

We will consider the following situation.

 
  Let k be a field.
  Suppose we have a finite group Γ, and a diagram of connected curves over k
  
    V [r] [d,"g"']     Y [r] [d,"f"]    Y[d] 
    
          U [r] [d]     X [r] [d]    X[d] 
     P^1_k - S_0 - S_∞[r]     P^1_k - S_∞[r]     P^1_k

  in which:
  
    
  * S_0 ∈*0,∅; S_∞∈*∞,∅;
    
  * all squares are cartesian;
    
  * X→ P^1_k is finite locally free;
    
  * V → U is finite étale Galois with Galois group Γ;
    
  * Y is the normal completion of V.
  
  Assume that X and Y are smooth over k.

  Let G be a finite locally constant sheaf of groups on U_ such that g^-1 G is constant, say with group of connected components G.


We assume the situation above is given by the smooth curves X and Y given using the description in <ref>, the finite group Γ and its action on Y/X, the group G with Γ-action, and the choice of sets S_0 and S_1;  note that we haven't explained yet how to decide whether such an input is valid, but the characterisations in this section and the introduction of the next section will allow us to do so.
We wish to compute the Galois set ^1(X,j_! G), keeping <ref> in mind (after base change to k^).
We therefore would like to give a description of, for every perfect field extension l of k, the category T(l) of j_! G-torsors on (X_l)_, purely in terms of (commutativity relations between) morphisms of vector bundles over P^1_l and free modules over l, and we can use <ref> to construct a groupoid with the desired properties.

By <ref>, T(l) is equivalent to that of Γ-equivariant G-torsors on (Y_l)_, together with a Γ-equivariant section from Y_l×_ P^1_l S_0.
(We note that in case S_0 = ∅, the empty morphism is Γ-equivariant.)
By taking normal completions, we obtain the following.


  Let l be a perfect field extension of k.
  Then the category T(l) is equivalent to that of finite locally free P^1_l-schemes T, smooth over l, together with a Γ-equivariant G-action, a Γ-equivariant morphism T →Y_l and a Γ-equivariant section Y_l×_ P^1_l S_0 → T ×_ P^1_l S_0, such that T ×_ P^1_l ( P^1_l - S_∞) is a G-torsor on (Y_l)_; here, the morphisms are the Γ-equivariant, G-equivariant morphisms of Y_l-schemes.


So aside from the conditions “smooth over l” and “T ×_ P^1_l ( P^1_l - S_∞) is a G-torsor on (Y_l)_”, the data in the description above can easily be expressed in terms of morphisms of vector bundles on P^1_l, and the relations in the description above can be easily expressed in terms of commutativity relations between these morphisms.



 §.§ Torsors
 

Let us first consider the condition “T ×_ P^1_l ( P^1_l - S_∞) is a G-torsor on (Y_l)_”.
To this end, we first express the condition “T is finite locally free over P^1_l of constant rank”, using the fibre of Y_l above 0 ∈ P^1_l; this is not automatic as we didn't assume Y to be geometrically connected.


  Let S be a scheme, let X be a finite locally free P^1_S-scheme that is smooth over S.
  Let Y be an X-scheme that is finite locally free over P^1_S, such that Y ×_ P^1_S 0 is finite locally free over X ×_ P^1_S 0 of constant rank n.
  Then Y is a finite locally free X-scheme of constant rank n.



  We can check fibrewise on S that X ×_ P^1_S 0 intersects all components of X, from which our claim follows.


Since finite locally free modules over an Artinian ring are free, we have the following.


  Let l be a perfect field extension of k.
  Then the category of finite locally free Y_l-schemes of constant rank is equivalent to that of finite locally free P^1_l-schemes T together with a morphism T →Y_l and an O(Y_l×_ P^1_l 0)-basis for O(T ×_ P^1_l 0) (morphisms in this category are simply morphisms of Y_l-schemes).


Next, we want to express the condition “T ×_ P^1_l ( P^1_l - S_∞) is étale over Y_l” in terms of vector bundles on P^1_l.
To this end, we will use the transitivity of the discriminant.

First, we recall the definitions of the discriminant and the norm of a finite locally free morphism Y → X.
Recall that, for a finite locally free morphism Y → X of schemes, we view O_Y as a (finite locally free) O_X-algebra.


  Let f  Y → X be a finite locally free morphism of schemes of constant rank, and let μ be the multiplication map O_Y ⊗_ O_X O_Y → O_Y.
  The trace form τ_f of f is the morphism O_Y →_ O_X( O_Y,  O_X) corresponding to the composition _f μ O_Y ⊗_ O_X O_Y → O_X.
  The discriminant Δ_f of f is the determinant (over O_X) of the trace form τ_f.



  Let f  Y → X be a finite locally free morphism of schemes of constant rank, and let L be a line bundle on Y.
  The norm _f  L of L is the line bundle
  
    _ O_X(_ O_X f_*  O_Y, _ O_X f_*  L).



Let f  Y → X be a finite locally free morphism of schemes of constant rank, and let E and F be finite locally free O_Y-modules of the same constant rank.
By <cit.> and the fact that norms (of line bundles) commute with tensor products and duals (see <cit.> and <cit.>), we see that there is a unique isomorphism

    _ O_X(_ O_X E, _ O_X F) = _ O_X(_f _ O_Y E, _f _ O_Y F)

satisfying the following properties.

  
  * It is compatible with base change by open immersions.
  
  * For any isomorphism α F → E, we have induced isomorphisms
    
    _ O_X(_ O_X E, _ O_X F) →_ O_X(_ O_X E)

    and
    
    _ O_X(_f _ O_Y E, _f _ O_Y F) →_ O_X(_f _ O_Y E).

    Therefore they induce isomorphisms
    
    _ O_X(_ O_X E, _ O_X F) →_ O_X(_ O_X E) =  G_m,X

    and
    
    _ O_X(_f _ O_Y E, _f _ O_Y F) →_ O_X(_f _ O_Y E) =  G_m,X.

    These isomorphisms are equal under the given identification.


Therefore, we have the following.

  Let f  Y → X be a finite locally free morphism of schemes of constant rank, and let E be a finite locally free O_Y-module of constant rank r.
  Then
  
    _ O_X E    = _f _ O_Y E ⊗_ O_X (_ O_X O_Y)^⊗ r
    _ O_X(_ O_X E, O_X)    = _f _ O_Y_ O_Y( E,  O_Y) ⊗_ O_X*[big]_ O_X(_ O_X O_Y,  O_X)^⊗ r



Using the two identifications above, we may now state the transitivity of the discriminant.
A proof can be found in e.g. <cit.>.


  Let f  Y → X and g  Z → Y be finite locally free morphisms of schemes of constant rank, and suppose that g has rank r.
  Then
  
    Δ_fg = _f Δ_g ⊗Δ_f^⊗ r.



 
  Let f  Y → X and g  Z → Y be finite locally free morphisms of schemes of constant rank, and suppose that g has rank r.
  Then g is étale if and only if we have _ O_X O_Z  (_ O_X O_Y)^⊗ r and Δ_fg and Δ_f^⊗ r differ by a unit.


Therefore we have the following.


  Let l be a perfect extension of k.
  Then the category of finite étale Y_l-schemes is equivalent to the full subcategory of that of finite locally free Y_l-schemes T of constant rank (say r) such that _ O_ P^1_l O_T  (_ O_ P^1_l O_Y_l)^⊗ r and Δ_T/ P^1_l and Δ_Y_l/ P^1_l^⊗ r differ by a unit.


Note that the condition on the determinants is simply a condition on the types of the standard modules over l isomorphic to O_T and O_Y_l, so if S_∞ = ∅, this gives an expression of the desired form.
If S_∞ = ∞, then we use the following instead.


  Let l be a perfect extension of k, and assume that S_∞ = ∞.
  Then the category of finite locally free Y_l-schemes étale over Y_l is equivalent to the full subcategory of that of finite locally free Y_l-schemes T of constant rank (say r) such that Δ_T/ P^1_l and Δ_Y_l/ P^1_l^⊗ r differ by a unit times a power of y.



  It suffices to show that for integers a,b, a map ϕ O_ P^1_l(b) → O_ P^1_k(a) is an isomorphism when restricted to A^1_l if and only if it is given by multiplication by s y^a-b with s ∈ l^×.
  Since y becomes invertible after restricting to A^1_l, it follows that if ϕ is multiplication by s y^a-b, then ϕ|_ A^1_l is an isomorphism.
  Conversely, ϕ is multiplication by some f ∈ l[x,y]_a-b, which after restriction becomes the multiplication by f(x,1) map l[x] → l[x].
  Since this map is an isomorphism, f(x,1) must be an invertible constant in l[x], i.e. f = s y^a-b for some s ∈ l^×.


We are almost ready to express the condition “T ×_ P^1_l ( P^1_l - S_∞) is a G-torsor on (Y_l)_” in terms of vector bundles on P^1_l.

 
  Let f  Y → X be a morphism of schemes, and let G be a finite group acting on Y/X.
  Then Y is a G-torsor on X if and only if f is flat, surjective, locally of finite presentation, and G acts freely and transitively on geometric fibres.



  The necessity of the condition is clear.
  Hence suppose that f is flat, surjective, locally of finite presentation, and G acts freely and transitively on geometric fibres.
  Then for any geometric point x of S, Y_ x is the trivial G-torsor, hence étale.
  As the property of being étale is fpqc local on the base, it follows that all fibres of f are étale, and since f is flat and locally of finite presentation, it follows that f is finite étale.

  Now consider the morphism ϕ G × Y → Y ×_X Y of finite étale Y-schemes given on the functor of points by (g,y) ↦ (gy,y), where the occurring schemes are viewed as Y-schemes via the projection on the second coordinate.
  Then ϕ is itself finite étale surjective, and as G × Y and Y ×_X Y have the same rank over Y, it follows that ϕ is an isomorphism.
  After base change with itself, it admits a section, so as f is finite étale, it also follows that Y is a G-torsor, as desired.


 
  Let f  Y → X be a finite étale morphism of schemes of constant rank n, and let G be a finite group of order n acting on Y/X.
  Then the locus in X where f is a G-torsor is open and closed in X.



  Consider the locus U in Y ×_X Y on which the morphism G × Y → Y ×_X Y given on the functor of points by (g,y) ↦ (gy,y) is an isomorphism (i.e. where the rank is equal to 1).
  It is an open and closed subset of Y ×_X Y as this morphism is finite étale.
  As the rank of f is equal to n, the X-locus where the same morphism is an isomorphism is the image of U in X, and hence is open and closed as well.
  This locus equals the X-locus where f is a G-torsor, as desired.


Therefore we have the following.


  Let l be a perfect extension of k.
  Then the category of finite locally free G-equivariant Y_l-schemes T such that T ×_ P^1_l ( P^1_l - S_∞) is a G-torsor on (Y_l)_ is equivalent to the category of finite locally free G-equivariant Y_l-scheme T such that T ×_ P^1_l ( P^1_l - S_∞) is étale, and such that T ×_ P^1_l 0 is a G-torsor on (Y_l×_ P^1_l 0)_.


Since in the description of finite locally free Y_l-schemes T, an O(Y_l×_ P^1_l 0)-basis for O(T ×_ P^1_l 0) occurred, in terms of which we can express the condition that T ×_ P^1_l 0 is a G-torsor on (Y_l×_ P^1_l 0)_.



 §.§ Smoothness at ∞
 

Finally, we consider the condition “T is smooth over l”.
If S_∞ = ∅, then this follows automatically from T having to be étale over Y_l, so assume that S_∞ = ∞.
As T ×_ P^1_l A^1_l has to be étale over Y_l, it suffices to consider the condition “T is smooth over l at T ×_ P^1_l∞”.

To this end, assume that we have a scheme S, a positive integer r, and the structure of an algebra A on O_S^r, given by, for the standard basis e_1,…,e_r on O_S^r, e_ie_i' = ∑_j μ_jii' e_j and 1 = ∑_j ϵ_j e_j.
Then the relative differentials Ω_ A/ O_S over S are generated by the e_j, with relations e_i'e_i + e_ie_i' - ∑_j μ_jii'e_j = 0 for all i,i' and ∑_j ϵ_j e_j = 0.
Therefore we get a canonical presentation ω_ A/ O_S A^r^2+1→ A^r of the A-module Ω_ A/ O_S, which is compatible with base change.


  Let l be any extension of k.
  The category of finite locally free P^1_l-schemes T smooth over l at T ×_ P^1_l∞ is equivalent to that of finite locally free P^1_l-schemes T, together with morphisms
  
    i  O_T ×_ P^1_l∞^(2)→ O_T ×_ P^1_l∞^(2)^2r,      j  O_T ×_ P^1_l∞^(2)^2r→ O_T ×_ P^1_l∞^(2)^(2r)^2+2

  of O_T ×_ P^1_l∞^(2)-modules such that (ω_O_T ×_ P^1_l∞^(2)/l⊕ i)j is the identity on O_T ×_ P^1_l∞^(2)^2r;
  the morphisms in the latter category are simply the morphisms of P^1_l-schemes.



  We will first show that T is smooth over l at T ×_ P^1_l∞ if and only there exist i and j as in the proposition.

  Write B for the ring of global sections of T ×_ P^1_l ( P^1_l - 0), and note that it is a finite locally free l[y]-algebra.
  Then T ×_ P^1_l∞^(2) =  B/y^2B.
  First suppose that there exist morphisms 
  
    i  (B/y^2B) → (B/y^2B)^2r,      j  (B/y^2B)^2r→ (B/y^2B)^(2r)^2+2

  such that for the canonical presentation ω_(B/y^2B)/l (B/y^2B)^(2r)^2+1→ (B/y^2B)^2r of Ω_(B/y^2B)/l as a (B/y^2B)-module, we have (ω_(B/y^2B)/l⊕ i) j = 𝕀.
  It immediately follows that Ω_(B/y^2B)/l is generated by one element as B/y^2B-module.

  Conversely, if Ω_(B/y^2B)/l is generated by one element, we let i be a morphism from (B/y^2B) to (B/y^2B)^2r sending 1 to (a lift of) a generator of Ω_(B/y^2B)/l.
  Hence (ω_(B/y^2B)/l⊕ i) is a surjective morphism to a free B/y^2B-module, so it has a section j, as desired.

  It remains to show that Ω_(B/y^2B)/l is generated as a B/y^2B-module by one element if and only if T is smooth over l at all points lying over ∞∈ P^1_l.
  Note that 
  we have an isomorphism
  
    Ω_B/l⊗_B (B/yB) →Ω_(B/y^2B)/l⊗_B/y^2B (B/yB),

  and that by Nakayama's lemma, the right hand side (and therefore the left hand side) is generated as a B/yB-module by one element if and only if Ω_(B/y^2B)/l is generated as a B/y^2B-module by one element.
  Therefore, again by Nakayama's lemma, there exists some f ∈ 1+yB such that Ω_B/l⊗_B B_f is generated as a B_f-module by one element.
  So the left hand side is a B/yB-module generated by one element if and only if there exists a neighbourhood of T ×_ P^1_l∞ that is smooth over l, which holds if and only if T is smooth over l at all points lying over ∞∈ P^1_l.

  So now we have a forgetful functor from the category of finite locally free P^1_l-schemes T together with morphisms i and j as in the proposition, to that of finite locally free P^1_l-schemes T smooth over l at T ×_ P^1_l∞, which is essentially surjective by the above, and fully faithful by construction.




 §.§ Bounds on types


In order to construct a groupoid scheme with the desired properties using the above, we first need to bound the number of possible types.

 
  Let S be a scheme, let a be a finite sequence of integers, let X be a finite locally free P^1_S-scheme of which the underlying O_ P^1_S-modules is standard of type a, and suppose that X has geometrically reduced fibres over S.
  Then a is non-positive (i.e. all of its elements are non-positive). 



  By taking a geometric fibre if necessary, we assume without loss of generality that S is the spectrum of an algebraically closed field k.
  Let X_1, …, X_t be the connected components of X.
  Then there exist finite sequences a_1,…,a_t such that for all i, the algebra O_X_i is of type a_i.
  These have the property that their concatenation is equal to a up to a permutation.
  Hence we assume without loss of generality that X is connected.
  In this case X is a reduced curve over S, so O_X( P^1_S) =  O_X(X) =  O_S(S) = k, where π is the structure morphism of X, so we deduce that a is non-positive.



  Of course, the converse is not true; a counterexample is the  O_ P^1_k⊕ O_ P^1_k(-1) ϵ with multiplication given by ϵ^2 = 0.


In <ref>, let l be a perfect extension of k, and let T be the normal completion of a j'_!G-torsor on (Y_l)_.
Let a be the type of O_Y, let b be the type of O_T, and let s,t be their respective lengths.
Then by the above, both a and b are non-negative.
As the degree of the finite locally free morphism T → Y_l is equal to #G, we see that t = s ·#G.
Moreover, if S_∞ = ∅, then by <ref>, we have ∑_j b_j = #G ·∑_i a_i; so up to permutation, we only have finitely many possibilities for b.
So suppose that S_∞ = ∞.

 
  Let S be a scheme, let a be a finite sequence of integers, and let X be finite locally free P^1_S-scheme such that O_X is a standard module over S of type a, where a has length s, and such that X is smooth over S.
  Then X is a family of curves over S of Euler characteristic s + ∑_i a_i.



  It suffices to check this on geometric fibres, so we may assume that S is the spectrum of an algebraically closed field k.
  Then
  
    _k ^0(X, O_X) - _k ^1(X, O_X)    = _k ^0*[big] P^1_k, O_ P^1_k(a) - _k ^1*[big] P^1_k, O_ P^1_k(a)
       = ∑_i (1+a_i) 
       = s + ∑_i a_i.



 
  Let S be a scheme, and let Y → X be a morphism of finite locally free P^1_S-schemes, with O_X and O_Y standard modules over S of respective types a and b, which have respective lengths s,t.
  Let G be a finite group of order invertible in S acting on Y over X, such that Y ×_ P^1_S A^1_S is a G-torsor over X ×_ P^1_S A^1_S.
  Then
  
    ∑_j b_j ≥#G ∑_i a_i - 12 t.




  It suffices to check this on geometric fibres, so we may assume that S is the spectrum of an algebraically closed field k.
  As G acts transitively on Y over X, and the order of G is invertible in k, it follows that Y is tamely ramified over X.
  Therefore the ramification degree of Y over X is at most t, as Y ×_ P^1_k A^1_k is étale over X ×_ P^1_k A^1_k, and Y has degree t over P^1_k.
  So by the Riemann-Hurwitz formula, we have
  
    -2t - 2∑_j b_j ≤ -2 ts s - 2 ts ∑_i a_i + t,

  as desired (note that t = s ·#G).


So therefore, also in the case that S_∞ = ∞, we see that there are only finitely many possibilities for the type b of T.



 §.§ Computation of the groupoid scheme


Now we see that, in <ref>, the description of the category of j_! A-torsors on X_ in terms of vector bundles on P^1_k gives, for each of the (finitely many) possibilities for the type b, a groupoid scheme R_b ⇉ U_b of which R_b and U_b are (explicitly given) closed subschemes of some A^N_k.
Let R = ∐_b  R_b and U = ∐_b  U_b.


  The groupoid scheme R ⇉ U satisfies the conditions of <ref>.
  Moreover, for fixed b, every isomorphism class in U_b,k^ has the same dimension.



  By construction, it remains to check that the isomorphism classes in U_b are irreducible for all finite sequences b of integers.
  So let a be the type of the underlying P^1_k-vector bundle of Y, and s its length, and let b be a finite sequence of integers, and t its length.
  Denote the morphisms R_b ⇉ U_b by α_b, ω_b, with α_b sending a morphism to its source, and with ω_b sending a morphism to its target.
  For this, it suffices to show that for all x ∈ U_b(k^), the geometric fibre H of α_b above x is irreducible, since the image ω_b(H) in U_b,k^ is by definition the isomorphism class of x.

  Note that, for any k^-scheme S, giving an isomorphism with fixed source (say with underlying Y_S-scheme T) in the groupoid R_b(S) ⇉ U_b(S) is, by transport of structure, the same as giving:
  
    
  * an O_ P^1_S-linear automorphism of O_ P^1_S(b);
    
  * an O_Y_S ×_ P^1_S 0-linear automorphism of O_Y_S ×_ P^1_S 0^#A;
    
  * if S_∞ = ∞, morphisms 
      
    i  O_T ×_ P^1_S∞^(2)→ O_T ×_ P^1_S∞^(2)^2#A,      j  O_T ×_ P^1_S∞^(2)^2#A→ O_T ×_ P^1_S∞^(2)^(2#A)^2+2

      such that (ω_T ×_ P^1_S∞^(2)/S⊕ i)j = 𝕀.
  

  In case S_∞ = ∅, we obtain an obvious isomorphism H → H_1 × H_2, and in case S_∞ = ∞, we obtain an obvious map H → H_1 × H_2 × H_3, where
  
    
  * H_1 is the functor sending a k^-scheme S to _ O_ P^1_S*[big] O_ P^1_S(b);
    
  * H_2 is the functor sending a k^-scheme S to _ O_Y_S ×_ P^1_S 0*[big] O_Y_S ×_ P^1_S 0^#G;
    
  * H_3 is the functor sending a k^-scheme S to the subset of
      
    _ O_T ×_ P^1_S∞^(2)( O_T ×_ P^1_S∞^(2), O_T ×_ P^1_S∞^(2)^2#G)

      of i such that ω_T ×_ P^1_S∞^(2)⊕ i is surjective.
  

  First note that using the description of standard modules, we easily see that H_1 is representable by a finite product of factors of the form G_m,k and A^1_k, so therefore by a smooth, irreducible k^-scheme.
  Moreover, note that H_2 is isomorphic to the functor sending a k^-scheme S to _S(Y_S ×_ P^1_S 0, _#G,S), which, as O_Y_S ×_ P^1_S 0 is finite free over O_S with a given basis functorial in S, is representable by a non-empty open subscheme of A^s(#G)^2_k^.
  Hence H_2 is a smooth, irreducible k^-scheme as well.
  Similarly, we see that H_3 is representable by a non-empty open subscheme of A^4t#G_k^, and therefore by a smooth, irreducible k^-scheme.

  Finally, we show that H is a smooth, irreducible k^-scheme.
  We do this by showing that H is Zariski locally on H_1 × H_2 × H_3 isomorphic to H_1 × H_2 × H_3 × A^N_k^ for some fixed N.

  First note that we have a morphism H_3 → A^M_k^ of k^-schemes, which is given on the functor of points by sending i ∈ H_3(S) to the corresponding 4t#G ×*[big]2t(2#G)^2+4t-matrix with coefficients in O(S), with respect to the basis subordinate to both the standard bases and the given k-basis of T ×_ P^1_k∞^(2), so that M = 4t^2*[big](2#G)^3+4#G.
  So let i ∈ H_3(k^), and view it as a 4t#G ×*[big]2t(2#G)^2+4t-matrix over k^.
  As this matrix corresponds to a surjective map of k^-vector spaces, there is a 4t#G × 4t#G-minor which is invertible.
  Let U  A^M_k^ be the locus on which this minor is invertible, and let V be the inverse image of U in H_3; V is an open neighbourhood of i.

  Now let j ∈ H_3(V) be the open inclusion. 
  By construction, the kernel of ω_T ×_ P^1_V∞^(2)⊕ j is free over O_V.
  Since an O_T ×_ P^1_V∞^(2)-linear section of this map is well-defined up to a unique tuple of elements from this kernel, it follows that the inverse image of H_1 × H_2 × V in H is isomorphic to H_1 × H_2 × V × A^N_k^ for some fixed N that is independent of the choices made.
  Hence H is a smooth, irreducible k^-scheme, as desired.

  Finally note that the dimension of H only depends on the type b, and that the induced morphism H → U_b,k^ has finite fibres, so every isomorphism class in U_b,k^ has the same dimension.



  There is a canonical bijection from π_0( U_k^) to the set of isomorphism classes of G-torsors on X_k^.
  Moreover, all U_b are equidimensional.


Next, note that we now have an obvious algorithm which, given a diagram as in <ref>, computes R and U; the remainder of this section will be devoted to bounding the complexity of this algorithm.
We will in the following restrict ourselves to the case in which S_0 = 0 and S_∞ = ∞; the bounds we obtain in this case will also hold in the other cases.

Let a be the type of Y, say of length s, and write γ = ∑_i -a_i.
Note that by <ref>, γ = s - 1 + p_a(Y), where p_a denote the arithmetic genus.
Also note that #Γ≤ s, so by <ref> below, the number of field elements needed to give <ref> is polynomial in s, γ, and #G.

First, let us bound the number of possible types b that can occur as the type of an object of U.


  The logarithm of the number of b that can occur as the type of an object of U is O*[big]s#G log(sγ#G).



  For convenience, write N = *#G*12s + γ.

  By <ref>, a possible type b must be non-positive.
  By <ref>, a possible type b must satisfy ∑_j -b_j ≤#G*[big]1/2s + γ.
  Such a type corresponds to a unique tuple (c_0,…,c_N) of non-negative integers with ∑_k=0^N c_k = t and ∑_k=0^N kc_k ≤ N by setting c_k to be the number of -b_j equal to k.
  The number of tuples satisfying the first of these conditions is N+tt≤ (N+t)^t.


Next, we will bound the size of R_b, i.e. for the given closed immersion R_b → A^N_k, the number N, the number of polynomials generating the defining ideal, and the degree of these polynomials.
Note that bounds for R_b will also hold for U_b.
To this end, note that we have the following trivial bound.


  Let a and b be finite sequences of non-positive integers, of lengths s and t, respectively.
  Then _k _ O_ P^1_k( O_ P^1_k(a), O_ P^1_k(b)) ≤ st + t ∑_i -a_i.


 
  Let a be a finite sequence of non-positive integers, of length s.
  Then
  
    _k _ O_ P^1_k*[big] O_ P^1_k, O_ P^1_k(a)   ≤ s + ∑_i -a_i 
    _k _ O_ P^1_k*[big] O_ P^1_k(a), O_ P^1_k(a)   ≤ s^2 + s∑_i -a_i 
    _k _ O_ P^1_k*[big] O_ P^1_k(a)^⊗ 2, O_ P^1_k(a)   ≤ s^3 + 2s^2∑_i -a_i 
    _k _ O_ P^1_k*[big] O_ P^1_k(a)^⊗ 3, O_ P^1_k(a)   ≤ s^4 + 3s^3∑_i -a_i.



Therefore, working out everything, which is straightforward but tedious, gives the following.

 
  For the given closed immersion R_b → A^N_k, we have N = O*[big]s^4(#G)^4γ, its defining ideal is given by O*[big]s^4(#G)^4γ polynomials, which have degree at most s#G.


Note that a polynomial ring in N variables has N+dd monomials of degree at most d; so by the proposition above, we see that the size of the output is

    *[Big]O*[big]s#G log(sγ#G).


Now that we have bounds for the sizes of R and U, we now turn to the degrees of the defining polynomials of the morphisms defining the structure of a groupoid scheme.

Recall for this that points of R_b are given by two objects of U_b, together with an O_ P^1-linear map connecting the two objects.
So the source and target maps R_b → U_b are induced by projections between their ambient affine spaces.
Therefore the affine k-scheme R_b ×_ U_b R_b of finite type is given by O*[big]s^4(#G)^4γ variables, O*[big]s^4(#G)^4γ relations of degree at most s#G.
Moreover, the composition map R_b ×_ U_b R_b → R_b forgets the middle object and composes the two O_ P^1-linear maps, so it is given by polynomials of degree at most 2.


  The obvious algorithm computes the groupoid scheme R ⇉ U given <ref> as input, and has arithmetic complexity 
  
    *[Big]O*[big]s#Glog(sγ#G).




  Simply note that every individual coefficient can be computed in arithmetic complexity bounded by a fixed polynomial in s,γ,#G.




§ GEOMETRIC POINTS AND FIRST COHOMOLOGY
 

Next, we will use the groupoid scheme R ⇉ U to compute ^1(X_,j_! G).
We will do this in a slightly more general situation, namely the following (compare with the conditions of <ref>).

 
  Let k be a field, let R ⇉ U be a groupoid scheme in which the morphisms R → U are smooth with geometrically irreducible fibres, and with R,  U affine and equidimensional, given by at most r polynomials – which are of degree at most d – in at most N variables.
  Let T be a stack on (/k)_ with representable and finite étale diagonal, and let [ U/ R] → T be a morphism such that p^-1p_* [ U_k^/ R_k^] → p^-1p_*  T_k^ is an equivalence.
  Here, for any field k, p  (/k)_→ ( k)_ denotes the change-of-site morphism for which p_* is the restriction.


Let us, for a finite reduced k-algebra A, denote by A^† the separable closure of k in A.
Moreover, if A is a finite product ∏_i k_i of fields, denote by A^ the product ∏_i k_i^.
Suppose we are in <ref>.
Then to any morphism x  l → U with l/k finite, we can attach an induced morphism l^→ U.
This in turn induces a morphism l^→ p^-1p_* T_k^, which is étale as both l^ and p^-1p_* T_k^ are étale over k^.
We hence get a morphism l^†→ p^-1p_* T.

We prove a couple of lemmas regarding this construction.

 
  In <ref>, let *x_i  l_i → U be a family of points on U.
  Then the image of ∐_i  l_i → U intersects every geometric connected component of U if and only if ∐_i  l_i^†→ p^-1p_* T is surjective.



  We note that the image of ∐_i  l_i → U intersects every geometric connected component if and only if the image of ∐_i  l_i^→ U does so.
  This is equivalent to ∐_i  l_i^→ p^-1p_* T_k^ being surjective, i.e. to ∐_i  l_i^†→ p^-1p_*  T being surjective.


 
  In <ref>, let x  l → U and y  m → U be two points on U.
  Let A be the coordinate ring of α^-1x ×_ Rω^-1y.
  Then A^† is the coordinate ring of l ×_p^-1p_* T m.



  Let x'  l^→ U and y'  m^→ U.
  Then A^ is the coordinate ring of α^-1x' ×_ Rω^-1y' =  l^×_p^-1p_* T_k^ m^, so A^† is the coordinate ring of l^†×_p^-1p_* T m^†, being the unique finite k-subalgebra of A^ of which the base change to k^ is A^.


So in <ref>, by finding enough points on U, one can construct a presentation of the stack p^-1p_*  T, which then can be used to compute π_0 of this.
Let us do so explicitly below.

 
  <ref> takes as input <ref> and computes a finite set X of morphisms x_i  l_i → U with l_i/k finite, such that the induced map ∐_i  l_i →π_0(p_*  T) is surjective.
  Moreover, it does so in arithmetic complexity
  
    *[Big]O*[big] N^2 log(d), e N log(d), log(r)



 
  Compute a Noether normalisation ν U → A^ U using e.g. <cit.>.
  Note that this also works for finite fields, but only after a base change to a finite field extension;  so for finite fields, one needs to keep track of the Galois action as well.

  Then set R =  O*[big]ν^-1(0).
  Compute a k-basis for R using a Gröbner basis computation for the ideal defining R.
  Compute the primary decomposition of R and for each local factor S of R, compute the composition of O( U) → R, R → S, and S → S^.



  First note that, as U is equidimensional, every geometric connected component maps surjectively to A^ U.
  Hence R is the ring of global sections of a closed subscheme of U that intersects every geometric connected component, so this procedure indeed computes a set X as desired.
  It remains to prove the claims on the arithmetic complexity.

  By <cit.> (for Noether normalisation and the zero-dimensional Gröbner basis computation, respectively), R can be computed as finite k-algebras in arithmetic complexity
  
    *[Big]O*[big] N^2 log(d), log(r) .


  Let us bound the k-vector space dimension of the R.
  First note that U ≤ N.
  Therefore R is given by at most N generators, and by relations that are of degree at most d.
  Hence 
  
    _k R = *[Big]O*[big] N log(d) .

  So by the methods of <cit.>, we see that the primary decomposition of R can be computed in arithmetic complexity
  
    *[Big]O*[big] N log(d) .

  
  Moreover, for each of the local factors, the degree of the purely inseparable extension l/k to be taken doesn't exceed (_k R)^e, as the degree of the polynomials to be factored doesn't exceed _k R.
  It then follows by that the maps R → S^ can be computed in arithmetic complexity
  
    *[Big]O*[big] (e+1)Nlog(d) .

  as _k (S ⊗_k l) ≤ (_k R)^e+1.


 
  <ref> takes as input <ref>, x  l → U, and y  m → U and computes the finite k-scheme α^-1 x ×_ Rω^-1 y in arithmetic complexity
  
    *[Big]O*[big] N_x,y^2 log(d_x,y), log(r) ,

  where N_x,y = max(N,log [l:k],log [m:k]) and d_x,y = max(d,[l:k],[m:k]).


 
  We first compute for l and m a “small” set of generators.
  Start by setting X = F = ∅.
  For s in a k-basis for l, compute k[X][s]  l and the minimal polynomial f of s over k[X]  l, and then, if f is linear, do nothing, otherwise add s to X and f to F.
  Write l = k[X]/(F) afterwards, and repeat this for m.

  Now compute x, y in terms of the “small” descriptions of l and m obtained above, and compute α^-1 x ×_ Rω^-1 y.
  Finally, compute a k-basis for its coordinate ring via Gröbner bases, and the unit and multiplication table with respect to this basis.



  Note that in the first step, we write l (resp. m) using O(log [l:k]) (resp. O(log [m:k])) generators and relations, of degree at most [l:k] (resp. [m:k]).
  Moreover, U and R are given by at most N generators and r relations, of degree at most d.
  Therefore α^-1 x ×_ Rω^-1 y is given by O*[big]log [l:k], log [m:k], N generators, O*[big]log [l:k], log [m:k], N, r relations, of degree at most max*[big][l:k],[m:k],d.
  Hence the arithmetic complexity follows from <cit.> in the same way as before.


As a corollary, using <ref> and <ref>, we have the following.


  There exists an algorithm that takes <ref> as input and computes a diagram
  
    Y^†[r,shift left] [r,shift right]     X^†
        X [u] [d] 
        U

  with X^†, Y^† finite étale over k, Y^†⇉ X^† a presentation for p^-1p_* T, X → X^† a finite purely inseparable morphism between finite k-schemes, and X → U having image intersecting every geometric connected component of U, in arithmetic complexity
  
    *[Big]O*[big] (e+1)N^3log(d)^3, log(r) .



In the corollary above, we can assume that if U, V are two distinct connected components of X^†, then α^-1U ×_Y^†ω^-1V is empty, since whenever we encounter distinct connected components U, V for which α^-1U ×_Y^†ω^-1V is not empty, then we may simply omit one of U, V.
It follows that the groupoid scheme Y^†⇉ X^† is a finite disjoint union of groupoid schemes Y_i^†⇉ X_i^† with finite étale arrows in which each X_i is the spectrum of a finite separable field extension of k.
Therefore the problem of computing π_0(p^-1p_* T) reduces to computing π_0 of each of these groupoid schemes.

The following lemma suggests how to compute π_0 in this case.


  Let S be a connected scheme, and let Y ⇉ X be groupoid scheme over S with X and Y finite étale S-schemes.
  Then the image R of Y → X ×_S X is an étale equivalence relation on X, and π_0([X/Y]) = X/R.



  This is trivial once we view X and Y as finite π_1(S)-sets.


 
  <ref> takes a groupoid scheme Y ⇉ X over k with X and Y finite étale k-schemes, and outputs π_0([X/Y]) in arithmetic complexity polynomial in the degrees of X and Y over k.


 
  Let l, B be the respective coordinate rings of X, Y, and let A = l ⊗_k l.
  Let A = ∏_i A_i be the primary decomposition of A; since A is separable over k, all A_i are fields.

  Compute the morphism A → B, and compute the set I of indices i for which the induced map A_i → B is non-zero.
  Set A_I = ∏_i ∈ I A_i.
  Compute the morphisms l → A_I sending s ∈ l to s ⊗ 1 and 1 ⊗ s, respectively, and return their equaliser k'.



  Note that, since A_I is the image of Y in X ×_ k X by construction, k' is the coequaliser of the two morphisms A_I → X constructed, in other words, it is the quotient of X by the étale equivalence relation A_i on X, as desired.


Applying the above to the groupoid scheme obtained in <ref>, we get the following.


  There exists an algorithm that takes as input <ref> and computes a finite étale k-scheme representing ^1(X_k^,,j_! G) in arithmetic complexity
  
    *[Big]O*[big] (e+1)s^12(#G)^12γ^3 log(s#G)^3 .



In order to be able to compute additional structures on ^1(X_k^,,j_! G), it will turn out to be useful to compute this set as a finite (k^/k)-set, together with some additional structure.
The first step in this is to compute a finite Galois extension l/k such that the Galois action on ^1(X_k^,,j_! G) factors through (l/k).
This is done in the standard recursive way.

 
  <ref> takes as input a finite separable k-algebra A, and computes the minimal Galois extension l/k such that A ⊗_k l is a product of copies of l, in arithmetic complexity polynomial in (_k A)!.
  If A is the underlying scheme of a group scheme over k, then the arithmetic complexity is
  
    *[Big]O*[big]log (_k A)^2 .



 
  Set A' = A, and compute a primary decomposition A' = ∏_i A'_i.
  Set l = k.
  While the number of factors is not _k A, choose A'_i of maximal dimension, and set A' = A' ⊗_l A'_i, l = A'_i, and compute a primary decomposition A' = ∏_i A'_i.
  Return l.



  There exists an algorithm that takes as input a finite separable k-algebra A, and computes the corresponding finite (k^/k)-set in arithmetic complexity polynomial in (_k A)! (or
  
    *[Big]O*[big]log (_k A)^2

  if A is the underlying scheme of a group scheme over k).


Now by base change to l, we get the following.

 
  There exists an algorithm that takes as input <ref> and computes:
  
    
  * a finite Galois extension l/k such that the (k^/k)-action on the finite set ^1(X_k^,,j_! G) factors through (l/k),
    
  * the finite (l/k)-set ^1(X_k^,,j_! G),
    
  * for each h ∈^1(X_k^,, j_! G), a finite extension l_h/l and a morphism l_h → U representing h,
  
  in arithmetic complexity
  
    *[Big]O*[big] (e+1)s^12(#G)^12γ^3 log(s#G)^3, (e+1) log [l:k] .





§ REDUCTIONS AND APPLICATIONS
 

In the previous sections, we assumed normal proper curves to be presented as finite locally free P^1_k-schemes as described in <ref>.
Alternatively, normal proper connected curves can be presented using their function fields, as a finite extension of k(x), and in this case, we will present morphisms between normal proper connected curves by morphisms between their function fields.

Passing from the presentation as finite locally free P^1_k-scheme to that as a finite extension of k(x) is simple:  given a finite locally free P^1_k-scheme X with type a of length s, one can compute the finite k(x)-algebra k(X) corresponding to it in arithmetic complexity polynomial in s and ∑_i -a_i, simply by, in the conventions of <ref>, substituting y=1 in the multiplication table and unit defining O_X;  this computation is functorial in X.

Conversely, given a finite field extension A of k(x) of degree d defined by elements of height at most h, one can compute α_1,…,α_n ∈ A such that A = k(x,α_1,…,α_n), and minimal polynomials for α_i+1 over k(x,α_1,…,α_i) in arithmetic complexity polynomial in d, h, using the methods of <cit.>;  note that n ≤log_2 d, and the minimal polynomials have degree at most d, and their coefficients have height at most d^3h.
By multiplying by suitable polynomials in k[x], one can make each α_i+1 have a minimal polynomial of which the coefficients lie in k[x,α_1,…,α_i], in arithmetic complexity polynomial in d, h;  the minimal polynomials in this case will have x-degree at most d^5h.
Therefore we obtain a k[x]-order in A consisting of products of the α_i.
Similarly, we can compute a k[x^-1]-order in A, in arithmetic complexity polynomial in d and h.

Then, by <cit.> (which we can apply since we are able to compute nilradicals of finite k-algebras) one can compute the corresponding maximal orders over k[x] and k[x^-1] in arithmetic complexity polynomial in d^e+1 and h.
Moreover, they define the same k[x,x^-1]-submodule of A, so it follows from <cit.> that one can compute a sequence (a_i) of integers, and bases (b_i) and (c_i) of the respective maximal orders such that b_i = x^a_i c_i for all i, and therefore a presentation of the normal proper connected curve as a finite locally free P^1_k-scheme, in arithmetic complexity polynomial in d^e+1 and h as well.

In fact, as the computation of nilradicals of finite k-algebras as described in <ref> proceeds by first computing the nilradical of the base change to k^, it follows that one can compute a purely inseparable extension l of k and a smooth proper connected curve with function field k(x)l in arithmetic complexity polynomial in d^e+1 and h;  we will refer to this as the construction of a smooth completion.

As for functoriality, given a morphism K → L of function fields, with K given as a finite k(x)-algebra, and L as a finite k(y)-algebra, one can compute a k(x)-basis of L (and therefore a K-basis of L) by successively computing a k(x)-basis of k(x,y) and a k(x,y)-basis of L;  with respect to this k(x)-basis of L, the computation given above is functorial.


  The above gives us an algorithm for the computation of the normalisation (over k and over k^) of a finite locally free P^1_k-scheme of type a of length s, in arithmetic complexity polynomial in s^e+1 and ∑_i -a_i;  for the type a' (of length s') of the resulting normal proper curve, we have s = s' and ∑_i -a'_i ≤∑_i -a_i.
  


To present divisors on proper normal curves, we will mainly use the so-called free ideal presentation.
Roughly speaking, in this presentation, divisors on a proper normal curve X are given as formal sums of closed points of X, which in turn are given by maximal ideals of O_X.
For more details on this and other related presentations, see e.g. <cit.>, or <cit.> for a more detailed exposition.
For the purposes of this paper, we simply note that we can compute images and pre-images of closed points of a morphism of proper normal curves in arithmetic complexity polynomial in the size of the input.

Now an arbitrary normal curve X will be presented by the product of the function fields of its connected components, and the finite complement of X in its normal completion X;  as a measure for the size of an affine curve, we take the k(x)-degree of the corresponding k(x)-algebra, an upper bound h for the height of the elements of k(x) defining this algebra, the number of closed points in X - X, and the maximum degree of these closed points over k.
Morphisms Y → X between normal curves will be presented by morphisms between their normal completions, such that for every closed point in the complement of X in X there is a closed point of Y in Y lying over it.



 §.§ Topological invariance of the small étale site


In our reduction to <ref>, we will make use of finite locally free, purely inseparable morphisms between normal proper curves and the topological invariance of the small étale site, which states that for a universal homeomorphism f  Y → X, the functors f_* and f^-1 are quasi-inverse functors between (X_) and (Y_).
Given a finite locally free, purely inseparable morphism f  Y → X between normal proper connected curves, we will make this explicit for étale sheaves representable by étale separated X-schemes (resp. Y-schemes), i.e. by normal curves.

For F an étale sheaf representable by an étale and separated X-scheme, the pullback is simply Y ×_X  F, which clearly can be computed in arithmetic complexity polynomial in the size of the input.

 
  <ref> takes a finite locally free, purely inseparable morphism f  Y → X between normal proper connected curves, and a normal curve F, étale over Y, and computes f_*  F, in arithmetic complexity polynomial in the size of the input.


 
  Write K, L, for the function fields of X, Y, respectively, let F be an étale and separated Y-scheme (with normal completion F), and let B denote its corresponding L-algebra.
  Let A be the Weil restriction of B from L to K.
  Compute the L-algebra isomorphism A ⊗_K L → B, and therefore a morphism A → B.
  Let F' denote the corresponding normal proper curve, and F→ F' be the corresponding morphism.
  Output F' together with the image of the complement of F in F.



  The output is correct since the output F' needs to satisfy F' ×_X Y =  F, and since taking Weil restrictions sends finite separable L-algebras to finite separable K-algebras, and is left adjoint to base changing from K to L.




 §.§ Presentation of torsors


Now note that in <ref>, we have a second presentation of a j_! G-torsor on X_k^, (the first being as a geometric point on the groupoid scheme R ⇉ U constructed in the previous section).
First, any j_! G-torsor is representable by an étale separated X-scheme and therefore by a normal curve, so we can present a j_! G-torsor T by a normal curve together with the group action j_! G ×_X T → T.
In fact, j_! G is representable by the disjoint union of X (acting as the zero section) and G - 1 (which is finite étale over U).
We indicate how to pass between these presentations.

Starting with x ∈ U(l), we let k' be the separable closure of k in l.
Note that x defines a Γ-equivariant A-torsor T on Y_l, together with a Γ-equivariant section Y×_ P^1_k S_0 →T.
Using the function field presentations, one can then compute quotients under Γ using linear algebra, which gives us a j_! G-torsor T on X_l,.
Therefore we can compute the corresponding j_! G-torsor on X_k', in arithmetic complexity polynomial in s^e+1, (#G)^e+1, γ^e+1, [l:k]^e+1.

Conversely, let T be a j_! G-torsor on X_k', with k'/k separable.
Pull T back to a Γ-equivariant G-torsor on Y_k',, together with Γ-equivariant section Y_k'×_ P^1_k S_0 → Y_k', and compute a smooth completion.
Now some linear algebra suffices to compute the additional data (see <ref> and <ref>) required to obtain a point of U(k^) in arithmetic complexity polynomial in s^e+1, (#G)^e+1, γ^e+1, [k':k]^e+1.

Therefore, using this, <ref> and <ref>, we have the following.

 
  <ref> takes as input <ref> (but with A =  G a sheaf of abelian groups, so A = G is abelian) and computes the (k^/k)-module ^1(X_k^,,j_! A) in arithmetic complexity
  
    *[Big]O*[big](e+1)^3s^16(#A)^16γ^4 log(s#A)^3.



 
  It remains to compute addition of classes of j_! A-torsors on X_k^,.
  For this, it suffices to note that if T_1, T_2 are j_! A-torsors on X_k', with k'/k separable, then the sum of the classes of T_1 and T_2 in ^1(X_k^,,j_! A) is given by the quotient of T_1 ×_X_k' T_2 by the j_! A-action given by a(t_1,t_2) = (at_1,a^-1t_2);  compute this using linear algebra over k'(x), and find the element in ^1(X_k^,,j_! A) isomorphic to it using <ref>.



  It remains to find an upper bound for log[l:k].
  Note that the cardinality of the set ^1(X_k^,,j_! A) is
  
    *[Big]O*[big]s^8(#A)^8γ^2 log(s#A),es^4(#A)^4γlog(s#A)

  by <ref>.
  As this set is an abelian group, it follows that 
  
    log[l:k] = O*[big](e+1)^2s^16(#A)^16γ^4 log(s#A)^2,

  from which the arithmetic complexity follows.




 §.§ Reduction to <ref>


We will now indicate how to reduce to <ref> for “most” smooth connected curves X over k, non-empty open subschemes U of X, and finite locally constant sheaves A on U_.
We would like to use explicit computation of Riemann-Roch spaces as in <cit.> to compute a suitable cover of X over P^1_k, however, this requires the curve to be given as a generically étale finite locally free P^1_k-scheme (or equivalently, a separating element for the function field of X must be given).

 
  <ref> takes as input a normal proper connected curve X over k of type a, and computes a finite purely inseparable extension l/k, a finite locally free purely inseparable morphism X' → X of degree at most [X: P^1_k]^e+2, and a generically étale finite locally free morphism X' → P^1_l of degree at most [X: P^1_k], in arithmetic complexity polynomial in ∑_i -a_i and [X: P^1_k]^e+2.


 
  By computing the separable closure K' of k(x) in K, compute the minimal p-power q such that f^q ∈ K' for all f ∈ K.
  Let L = K · k^1/q(x^1/q), which is the reduction of K ⊗_k(x) k^1/q(x^1/q), and output l = k^1/q and x^1/q, together with a K-basis of L.



  We note that q is bounded from above by [K:k(x)], and that therefore L can be computed in arithmetic complexity polynomial in ∑_i -a_i and [K:k(x)]^e+2.


 
  <ref> takes as input a smooth connected curve X generically étale over P^1_k, given by its normal completion X, a finite set *Q_1,…,Q_t of closed points of X, and an open immersion j  U → X, given by a finite set *P_1,…,P_s of closed points of X, and computes a finite locally free morphism π X → P^1_k with π^-1(∞) = *Q_1,…,Q_t and π^-1(0) *P_1,…,P_s in arithmetic complexity polynomial in the size of the input.


 
  Write Z_0 = ∑_i=1^s P_i, Z_∞ = ∑_j=1^t Q_j, and let g be the genus of X.
  Let m be the smallest integer such that m(t-1) - s > 2g - 2 and 2^m > t.
  Using <cit.>, compute a k-basis B for O_X(-Z_0 + mZ_∞), and compute the subspaces O_X(-Z_0 + mZ_∞ - mQ_j) for j=1,…,t.
  Find a linear combination f = ∑_b ∈ Bϵ_b b with ϵ_b ∈*0,1 for all b ∈ B such that f is not in any of the O_X(-Z_0 + mZ_∞ - mQ_j) for j=1,…,t.

  Compute a minimal polynomial for f over k(x), and write it as a minimal polynomial for x over k(f), and compute successively a k(f)-basis for k(x,f) and a k(f)-basis for k(X).
  Output the corresponding map X → P^1_k.



  Note that by choice of m, we see that O_X(-Z_0 + mZ_∞ - mQ_j) has dimension #B - m, so f ranges over a set of 2^#B elements, of which at most t2^#B-m lie in one of the given subspaces.
  By choice of m, we have t2^#B-m < 2^#B, so there exists such f not lying in any of the given subspaces.


In particular, if either U = X or X = X, then we can get a finite locally free morphism X→ P^1_k with U and X inverse images of P^1_k, P^1_k - 0, or P^1_k - ∞.
Therefore, using smooth completions, we now have an obvious reduction to <ref>, and therefore the following corollary, which in turn implies <ref>.


  Let S_0 ∈*[big]∅,0 and S_∞∈*[big]∅,∞.
  There is an algorithm that takes a finite locally free P^1_k - S_∞-scheme X, smooth over k, and a finite étale commutative group scheme A over U = X ×_ P^1_k ( P^1_k - S_0 - S_∞), and computes the (k^/k)-module ^1(X_k^,,j_! A) in arithmetic complexity exponential in e, [X: P^1_k - S_∞], [ A:U]^log [ A:U], γ_X, and γ_ A.
  Here, γ_X (resp. γ_ A) is ∑_i -a_i, where a is the type of the normal completion of X (resp. A).



  We need to prove that the size of the cover Y constructed is polynomial in [X: P^1_k - S_∞], [ A:U]^log [ A:U], γ_X, and γ_ A.
  Recall that Y is constructed by setting X' = X, A' =  A and then repeatedly base changing A'/X' to a non-trivial connected component of A'.

  For each such base change, let a be the type of A', let a' be the type of the chosen connected component of A', and let a” be the type of their fibre product A” over X.
  Note that as then O_ P^1_k(a') is a direct summand of O_ P^1_k(a), we have max_j -a'_j ≤max_i -a_i.
  Moreover, as O_ P^1_k(a) ⊗_ O_ P^1_k O_ P^1_k(a') surjects onto O_ P^1_k(a”), it follows that max_k -a”_k ≤max_i,j -a_i-a'_j ≤ 2 max_i -a_i.
  Since log_2 [ A:U] such base changes suffice for the construction of a finite locally free X-scheme of which the normalisation is Y, it follows that for the type b of Y, its length t is at most [X: P^1_k - S_∞][ A:U]^log_2 [ A:U], and ∑_j -b_j ≤ t max_j b_j ≤ t [ A:U] γ_ A.

  The result now follows from <ref>.




 §.§ Application to computation for constructible sheaves


In this section, we will indicate how to compute ^1(X_k^,, A) for X a smooth connected curve and A an arbitrary constructible sheaf of abelian groups, of torsion invertible in k, under the following assumptions.
We will assume a presentation of constructible sheaves (and morphisms between them) to be given, with respect to which one can perform certain operations.
These operations are:

  
  * one can compute finite direct sums of constructible sheaves;
  
  * one can compute kernels and cokernels of morphisms;
  
  * for a constructible sheaf A, one can compute a non-empty open subscheme U of X such that A|_U is finite locally constant;
  
  * for a closed immersion i  Z → X and its open complement j  U → X, one can compute the functors i^-1, i_*, i^!, j_!, j^-1, j_* and the corresponding units and counits of adjunction; given A_Z on Z_, A_U on U_, and ϕ A_Z → i_* j^-1 A_U, one can compute the corresponding constructible sheaf on X_.


In theory, one should be able to give such a presentation using recollement (as done in <ref> for j_! A-torsors), but we will not work this out in this paper.

So suppose X is a smooth connected curve, and A is a constructible sheaf of abelian groups on X_, of torsion invertible in k.
Let U be a non-empty open subscheme for which A|_U is finite locally constant.
Use <ref> and <ref> to find l/k finite purely inseparable, V  U_l open and a finite locally free morphism X_l → P^1_l such that V and X_l are finite locally free over their images in P^1_l.
Write j  V → X_l for the inclusion, and write i  Z → X_l for its closed complement.

Compute the canonical short exact sequence 0 → j_!j^-1 A → A → i_*i^-1 A → 0, and the morphism δ(i,j) ^0(X_k^,,i_*i^-1 A) →^1(X_k^,,j_!j^-1 A) which sends a section of i^-1 A to the constructible sheaf defined by j^-1 A on V_, 0 on Z_, and the section of i^-1j_*j^-1 A obtained from the given section of i^-1 A by composition with i^-1 A → i^-1j_*j^-1 A.
Then, as ^1(X_k^,,i_*i^-1 A) = 0, we see that ^1(X_k^,, A) = δ(i,j).

This is independent of the choice of (i,j) in the following sense.
If j'  V' → X_l and i'  Z' → X_l are given, with V'  V and a given morphism Z → Z' over X_l, then we can compute a commutative diagram

    0 [r]     j'_!(j')^-1 A [r] [d]     A [r] [d,equals]     i'_*(i')^-1 A [r] [d]     0 
    
        0 [r]     j_!j^-1 A [r]     A [r]     i_*i^-1 A [r]     0

a commutative diagram

    ^0(X_k^,,i'_*(i')^-1 A) [r] [d]    ^1(X_k^,,j'_!(j')^-1 A) [d] 
    ^0(X_k^,,i_*i^-1 A) [r]    ^1(X_k^,,j_!j^-1 A)

and therefore the morphism δ(i',j') →δ(i,j) corresponding to the identity map on ^1(X_k^,, A).

In the same way, we see that for constructible sheaves A, B on X_, and a morphism A → B, we can compute the induced morphism ^1(X_k^,, A) →^1(X_k^,, B), and that for a morphism f  Y → X of smooth connected curves, we can compute the pullback ^1(X_k^,, A) →^1(Y_k^,,f^-1 A).

abbrvnat


