<figure><img src="image_1.png" /></figure>

HAL
open science

# An algorithm to compute Selmer groups via resolutions by permutations modules

Fabrice Etienne

► To cite this version:

Fabrice Etienne. An algorithm to compute Selmer groups via resolutions by permutations modules. 2025. hal-05038206

HAL Id: hal-05038206

https://hal.science/hal-05038206v1

Preprint submitted on 17 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An algorithm to compute Selmer groups via resolutions by permutations modules

Fabrice Etienne

## Abstract

Given a number field with absolute Galois group $\mathcal{G}$, a finite Galois module $M$, and a Selmer system $\mathcal{L}$, this article gives a method to compute $\text{Sel}_{\mathcal{L}}$, the Selmer group of $M$ attached to $\mathcal{L}$. First we describe an algorithm to obtain a resolution of $M$ where the morphisms are given by Hecke operators. Then we construct another group $H_S^1(\mathcal{G}, M)$ and we prove, using the properties of Hecke operators, that $H_S^1(\mathcal{G}, M)$ is a Selmer group containing $\text{Sel}_{\mathcal{L}}$. Then, we discuss the time complexity of this method.

## Introduction

Selmer groups, constructed from the Galois cohomology of number fields, are powerful tools in modern number theory. Introduced in the study of descent in elliptic curves ([12, Chapter X, §4]), they have been crucial for progress toward the BSD conjecture (see for example [9]) and arithmetic statistics on ranks of elliptic curves (see [1]), conjecturally predict the order of vanishing of L-functions (see [2]), control deformations of Galois representations (see [11, §1.10]) and therefore play an important role in modularity theorems (see [14]) and have many other applications, for instance in effective class field theory (see [5, §5.2.2]). It is therefore important to design efficient algorithms to compute Selmer groups.

Throughout the article, we will use the following definition of a Selmer group.

Let $K$ be a number field, $\bar{K}$ its algebraic closure, and $\mathcal{G}$ (or $\mathcal{G}_K$) its absolute Galois group. Let $M$ be a left $\mathcal{G}$-module. Given a finite place $v$ of $K$, let $G_v$ denote the decomposition group of $K$ at $v$, and $I_v$ the inertia group. Then,

* a *local condition* at $v$ is a subgroup $L_v \subset H^1(G_v, M)$,
• the unramified condition is the subgroup

$$H_{un}^{1}(G_{v}, M) = \ker \{H^{1}(G_{v}, M) \to H^{1}(I_{v}, M)\},$$

• a Selmer system for $M$ is a set $\mathcal{L}$ of local conditions $L_v$ at every finite place $v$ of $K$, such that all but finitely many of the $L_v$ are the unramified condition,

• given a Selmer system $\mathcal{L}$, the Selmer group attached to $\mathcal{L}$ is the subgroup of $H^1(\mathcal{G}_K, M)$ given by

$$\mathrm{Sel}_{\mathcal{L}} = \ker \left\{ H^1(\mathcal{G}_K, M) \to \prod_v \frac{H^1(G_v, M)}{L_v} \right\}.$$

Note that this definition of Selmer group is restricted to subgroups of the first cohomology group $H^1(\mathcal{G}_K, M)$, but we can give a similar definition for Selmer groups that would be subgroups of other cohomology groups. For future research, it might be interesting to try and adapt the method of this article to be able to compute Selmer groups contained in $H^2(\mathcal{G}_K, M)$.

Some methods already exist to compute Selmer groups. For Selmer groups of elliptic curves, Bruin lists some of these algorithms in [3, section 5.4] and gives a geometric interpretation, and we can also mention some more recent articles, like the article [10] by Maistret and Shukla. The method presented here is more general, since it allows one to compute Selmer groups in general and not only Selmer groups of elliptic curves. For future work, we think it would be interesting to compare the time complexity of all the existing methods.

The main result in this article will be the following.

**Theorem A.** Let $\mathcal{G}$ be the absolute Galois group of a number field $K$, and $M$ be a finite left $\mathcal{G}$-module. There exists an algorithm that on input

• the module $M$,

• the finite group $G$ that is the image of the action $\mathcal{G} \to \mathrm{Aut}(M)$,

• a Selmer system $\mathcal{L}$,

outputs the Selmer group $\mathrm{Sel}_{\mathcal{L}}$ attached to $\mathcal{L}$ for $M$. Moreover, every step of this algorithm is polynomial, except for the computation of subfields of $\overline{K}$ fixed by subgroups of $\mathcal{G}$, and the computation of the group of $S$-units and the class group of some field extensions of $K$.

We will describe this algorithm (see algorithm 4.3), and discuss the complexity in proposition 4.5.
We will use some properties of Hecke operators of finite groups. In section 1, we will give the definition of Hecke operators, as it was given for example in [15], and we will state some important properties that were proven in [6] (propositions 1.3 and 1.4).

In section 2, we will discuss a method to find a partial resolution of any finite Galois module $M$, of the form

$$0 \to M \to I_0 \xrightarrow{d_0} I_1 \xrightarrow{d_1} I_2$$

where the modules $I_i$ are duals of sums of permutation modules, and the morphisms $d_i$ are given by sums of Hecke operators. A more precise algorithm will be given in section 4 (algorithm 4.2).

Then, in section 3, we will introduce some special groups $H_S^1(\mathcal{G}, M)$ where $S$ is a set of prime numbers (see definition 3.1), and we will show that under some conditions on $S$, the group $H_S^1$ is the Selmer group attached to the Selmer structure where all the conditions at places outside of $S$ are unramified conditions and where there is no condition for the places in $S$.

Given a Selmer system $\mathcal{L}$, our method to compute $\mathrm{Sel}_{\mathcal{L}}$ will be to first compute $H_S^1$ for $S$ large enough, and then look for $\mathrm{Sel}_{\mathcal{L}}$ as a subgroup of $H_S^1$. In section 4, we will describe this method (see algorithm 4.3) and discuss its time complexity (see proposition 4.5). We leave the implementation of this method for future work.

**Notations and conventions** In all of the article, $K$ will be a field of characteristic zero. We will denote by $\overline{K}$ its algebraic closure and by $\mathcal{G}$ the Galois group $\mathrm{Gal}(\overline{K}/K)$.

All modules in this article will be left modules.

When $R$ is a ring and $M, N$ are left $R$-modules, we will denote $\mathrm{Hom}_R(M, N)$ the group of $R$-module homomorphisms from $M$ to $N$.

If $M$ is a $\mathcal{G}$-module, we will denote by $M^* := \mathrm{Hom}_{\mathcal{G}}(M, \overline{K}^*)$ the dual module of $M$, where $\overline{K}^*$ is viewed as an abelian group.

In a finite field extension $L/F$, we will denote by $N_{L/F}(x)$ the norm of $x \in L$.

Unless specified otherwise, the group laws of cohomology groups will always be denoted multiplicatively.

**Acknowledgements** I would like to thank A. Page for the initial idea behind this article and for his precious help and advice. This research was funded by the University of Bordeaux. It was also supported by the CIAO ANR (ANR-19-CE48-008) and the CHARM ANR (ANR-21-CE94-0003). It took place inside the CANARI team
(Cryptographic Analysis and Arithmetic) of the Institute of Mathematics of Bordeaux (IMB).

# 1 Properties of Hecke operators

The method will use some properties of Hecke operators, which were proven in [6]. In this section, $G$ will denote a finite subgroup of $G = \text{Gal}(\overline{K}/K)$.

**Definition 1.1.** Let $H$ be a subgroup of $G$, then the set $\mathbb{Z}[G/H]$ has a structure of $\mathbb{Z}[G]$-module. We call permutation modules the sums of modules of this form.

**Definition 1.2.** If $R$ is a ring and $V$ a $R[G]$-module, and $H, J$ two subgroups of $G$, then there is a morphism of $R$-modules

$$R[H \backslash G/J] \to \text{Hom}_R(V^H, V^J).$$

This isomorphism is described in [6, Fact 1.4]. The morphisms of $R$-modules associated with cosets of the form $HgJ$ for $g$ in $G$ by this isomorphism are called Hecke operators.

**Proposition 1.3.** Let $H_1, \dots, H_n$ and $J_1, \dots, J_m$ be subgroups of $G$. If $\Phi: \bigoplus_i \mathbb{Z}[G/H_i] \to \bigoplus_i \mathbb{Z}[G/J_i]$ is a morphism of $\mathbb{Z}[G]$-modules whose image is of finite index in $\bigoplus_i \mathbb{Z}[G/J_i]$, then there exists an injective morphism $\Psi: \bigoplus_i \mathbb{Z}[G/J_i] \to \bigoplus_i \mathbb{Z}[G/H_i]$ such that $\Phi \circ \Psi = k \cdot \text{id}$, where $k$ is a positive integer that divides $|G|^2$.

*Proof.* See [6, Proposition 2.13] for the existence of $\Psi$, and [6, Theorem 2.16] for the proof that $k$ divides $|G|^2$. $\square$

**Proposition 1.4.** Let $H, J$ be two subgroups of $G$, $L_1 = \overline{K}^H$ and $L_2 = \overline{K}^J$. Let $S$ be a set of prime numbers. If $\Phi: L_1^\times \to L_2^\times$ is defined by a sum of Hecke operators, then

$$\Phi(\mathbb{Z}_{S,L_1}^\times) \subset \mathbb{Z}_{S,L_2}^\times.$$

*Proof.* This is a direct consequence of [6, Theorem 1.18]. $\square$

<figure><img src="image_3.png" /></figure>

# 2 Finding a resolution with Hecke operators

In all of the article, $M$ will be a finite Galois module.
Let $G$ be the image of the action $\mathcal{G} \to \mathrm{Aut}(M)$. It is isomorphic to a finite quotient of $\mathcal{G}$. Note that the action of $\mathcal{G}$ over $M$ can be factorized to be seen as an action of $G$ over $M$.

**Remark 2.1.** If $\mathcal{N}$ denotes the kernel of the action $\mathcal{G} \to \mathrm{Aut}(M)$, then $G$ is the Galois group of the Galois extension $\overline{K}^{\mathcal{N}}/K$.

Suppose we have $\mathbb{Z}[G]$-modules $P_i$ for every integer $i$, which are permutation modules, as well as some morphisms of $G$-modules $s$ and $d_i^*$ such that the sequence

$$ \dots \xrightarrow{d_2^*} P_2 \xrightarrow{d_1^*} P_1 \xrightarrow{d_0^*} P_0 \xrightarrow{s} M^* \to 0 $$

is exact, where $M^*$ is the dual module of $M$.

We will see in section 4 that we can always find such an exact sequence, and we will give an algorithm (algorithm 4.2) to compute such $P_i$ and $d_i^*$ up to any integer $i$.

In this article, we will only need to compute such sequences up to $P_2$. We will denote by (1) an exact sequence of the form

$$ P_2 \xrightarrow{d_1^*} P_1 \xrightarrow{d_0^*} P_0 \xrightarrow{s} M^* \to 0. \qquad (1) $$

**Lemma 2.2.** The functor $P \mapsto P^* = \mathrm{Hom}_{\mathbb{Z}}(P, \overline{K}^*)$, on the category of $G$-modules that are finitely generated $\mathbb{Z}$-modules, is exact.

*Proof.* Let $A, B, C$ be $G$-modules such that there is an exact sequence

$$ 0 \to A \xrightarrow{i} B \xrightarrow{s} C \to 0. $$

Let $s^*$ be the map $C^* = \mathrm{Hom}(C, \overline{K}^*) \to \mathrm{Hom}(B, \overline{K}^*) = B^*; f \mapsto f \circ s$. Since $s$ is surjective, the map $s^*$ is injective.

Likewise, let $i^*$ be the map $B^* \to A^*, f \mapsto f \circ i$. Again, since $i$ is injective, the map $i^*$ is surjective.

Since we know that $i \circ s = 0$, we have $\mathrm{Im}(s^*) \subseteq \mathrm{Ker}(i^*)$. We also need to show that $\mathrm{Ker}(i^*) \subseteq \mathrm{Im}(s^*)$.

Let $f$ be an element of $\mathrm{Ker}(i^*)$. That is to say $f \circ i = 1$. Then that means $\mathrm{Ker}(f) \subset \mathrm{Im}(i) = \mathrm{Ker}(s)$. So, by the structure of finitely generated abelian groups, there exists $g \in C^*$ such that $f = g \circ s$.

In conclusion, the short sequence

$$ 0 \to C^* \xrightarrow{s^*} B^* \xrightarrow{i^*} A^* \to 0 $$

is exact.

□
Once we obtain an exact sequence of the form (1), by lemma 2.2, we can take the dual and get an exact sequence of the form

$$0 \to M \to I_0 \xrightarrow{d_0} I_1 \xrightarrow{d_1} I_2 \qquad (2)$$

where $I_i = P_i^*$ for all $i$.

Consider an exact sequence of the form (2) obtained with the construction described above. The modules $P_0, P_1, P_2$ are permutations modules. In the rest of the section, let us denote $P_i = \bigoplus_j \mathbb{Z}[G/H_{i,j}]$ for $i \in \{1, 2, 3\}$. And for every pair $(i, j)$, let us define $L_{i,j} := \overline{K}^{H_{i,j}}$.

**Proposition 2.3.** With the above notations, for $i \in \{1, 2, 3\}$, we have

$$I_i = \bigoplus_j \mathrm{Ind}_{G/G_{L_{i,j}}} \overline{K}^{\times} = \bigoplus_j \overline{L_{i,j}}^{\times}$$

where $G_{L_{i,j}}$ is the absolute Galois group of $L_{i,j}$. And

$$I_i^G = \bigoplus_j L_{i,j}^\times.$$

*Proof.* See [13, Section 3.12, Example 19]. □

<figure><img src="image_4.png" /></figure>

The morphisms $d_0: I_0 \to I_1$ and $d_1: I_1 \to I_2$ induce some morphisms respectively from $I_0^G$ to $I_1^G$ and from $I_1^G$ to $I_2^G$, that we will denote $d_0^G$ and $d_1^G$.

**Proposition 2.4.** With the above notations, we have

$$H^1(\mathcal{G}, M) = \frac{\mathrm{Ker}(d_1^G: I_1^G \to I_2^G)}{\mathrm{Im}(d_0^G: I_0^G \to I_1^G)}.$$

*Proof.* Let $J \subset I_1$ be the image of $d_0$. Then we have a short exact sequence

$$0 \to M \to I_0 \xrightarrow{d_0} J \to 0.$$

The associated long exact sequence starts with

$$0 \to M^G \to I_0^G \xrightarrow{d_0} J \to H^1(\mathcal{G}, M) \to H^1(\mathcal{G}, I_0)$$

and $H^1(\mathcal{G}, I_0) = \bigoplus_j H^1(G_{L_{0,j}}, \overline{L}_{0,j}^\times)$ by Shapiro's lemma, and $H^1(G_{L_{0,j}}, \overline{L}_{0,j}^\times) = 0$ by Hilbert 90th theorem.

This last exact sequence allows us to deduce that

$$H^1(\mathcal{G}, M) = \frac{J^G}{\mathrm{Im}(d_0^G: I_0^G \to I_1^G)} \quad (*)$$
What's more, by definition of $J$, we also have an exact sequence

$$0 \to J \to I_1 \xrightarrow{d_1} I_2.$$

Hence the exact sequence

$$0 \to J^G \to I_1^G \xrightarrow{d_1} I_2^G$$

from which we can deduce that

$$J^G = \mathrm{Ker}(d_1^G : I_1^G \to I_2^G).$$

Combining that result with $(*)$, we get

$$H^1(\mathcal{G}, M) = \frac{\mathrm{Ker}(d_1^G : I_1^G \to I_2^G)}{\mathrm{Im}(d_0^G : I_0^G \to I_1^G)}.$$

<figure><img src="image_5.png" /></figure>

**Proposition 2.5.** For every subgroup $\mathcal{H} < \mathcal{G}_K$, the map

$$\mathrm{Res} : H^1(\mathcal{G}_K, M) \to H^1(\mathcal{H}, M)$$

is the natural restriction

$$H^1(\mathcal{G}, M) = \frac{\mathrm{Ker}(d_1^G : I_1^G \to I_2^G)}{\mathrm{Im}(d_0^G : I_0^G \to I_1^G)} \to H^1(\mathcal{H}, M) = \frac{\mathrm{Ker}(d_1^\mathcal{H} : I_1^\mathcal{H} \to I_2^\mathcal{H})}{\mathrm{Im}(d_0^\mathcal{H} : I_0^\mathcal{H} \to I_1^\mathcal{H})}$$

*Proof.* Let $J \subset I_1$ be the image of $d_0$. Then we have a short exact sequence

$$0 \to M \to I_0 \xrightarrow{d_0} J \to 0.$$

The associated long exact sequence starts with

$$0 \to M^G \to I_0^G \to J_1^G \to H^1(\mathcal{G}, M).$$

We can then apply the restriction map to obtain

<figure><img src="image_6.png" /></figure>

Moreover, for every field $F$ such that $K \subset F$, and for all $i$, we have $I_i^G = L_i^\times$ and $I_i^{\mathrm{Gal}(F/F)} = (L_i \otimes_K F)^\times$. So $I_i^\mathcal{H} = \overline{L_i}^\mathcal{H}$, hence the conclusion.

<figure><img src="image_7.png" /></figure>
### 3 A remarkable Selmer group

Let $M$ be a finite Galois module, suppose we have the Galois modules $I_0$, $I_1$, $I_2$ and the morphisms of $G$-modules $d_0$ and $d_1$ obtained as in section 2, such that the sequence

$$0 \to M \to I_0 \xrightarrow{d_0} I_1 \xrightarrow{d_1} I_2$$

is exact. By proposition 2.4, we have

$$H^1(\mathcal{G}, M) = \frac{\mathrm{Ker}(d_1^G : I_1^G \to I_2^G)}{\mathrm{Im}(d_0^G : I_0^G \to I_1^G)}.$$

where for all $i \in \{0, 1, 2\}$, $I_i^G$ is of the form $\bigoplus_j L_{i,j}^\times$ and the $L_{i,j}$ are intermediary fields between $K$ and $\overline{K}$.

In the rest of the article, we will denote by $L_i$ the étale algebra $\prod_j L_{i,j}$. We will allow ourself to extend to étale algebras the notions of class groups and $S$-unit groups.

**Definition 3.1.** Let $S$ be a set of prime numbers. Let us define the group $H_S^1(\mathcal{G}, M) := \frac{\mathrm{Ker}(d_1^G : \bigoplus_j \mathbb{Z}_{L_{1,j},S}^\times \to \bigoplus_j \mathbb{Z}_{L_{2,j},S}^\times)}{\mathrm{Im}(d_0^G : \bigoplus_j \mathbb{Z}_{L_{0,j},S}^\times \to \bigoplus_j \mathbb{Z}_{L_{1,j},S}^\times)}$.

By proposition 1.4, the images of $S$-units by $d_1^G$ and $d_0^G$ are $S$-units, so the group $H_S^1(\mathcal{G}, M)$ is well defined.

When the context is clear, we will also allow ourself to write $H^1$ and $H_S^1$ instead of $H^1(\mathcal{G}, M)$ and $H_S^1(\mathcal{G}, M)$.

The goal of this section will be to prove that $H_S^1(\mathcal{G}, M)$ is a Selmer group. We will use the following notations:

* $Z^1 := \mathrm{Ker}(d_1^G : I_1^G \to I_2^G)$

* $B^1 := \mathrm{Im}(d_0^G : I_0^G \to I_1^G)$

* $Z_S^1 := \mathrm{Ker}(d_1^G : \bigoplus_j \mathbb{Z}_{L_{1,j},S}^\times \to \bigoplus_j \mathbb{Z}_{L_{2,j},S}^\times)$

* $B_S^1 := \mathrm{Im}(d_0^G : \bigoplus_j \mathbb{Z}_{L_{0,j},S}^\times \to \bigoplus_j \mathbb{Z}_{L_{1,j},S}^\times)$.

**Proposition 3.2.** We have an injection $H_S^1(\mathcal{G}, M) \hookrightarrow H^1(\mathcal{G}, M)$

*Proof.* We have trivially $Z_S^1 \subset Z^1$. So in order to prove the proposition, it is enough to show that $B^1 \cap \mathbb{Z}_{L_{1,j},S}^\times \subset B_S^1$. In other words, we need to show that if an element $y$ in the image of $d_0^G$ is an $S$-unit, then there exists an $S$-unit $x$ in $I_0^G = L_0^\times$ such that $d_0^G(x) = y$.

If we take the tensor product of the exact sequence (2) with $\mathbb{Q}$, we obtain

$$0 \to I_0 \otimes \mathbb{Q} \xrightarrow{d_0} I_1 \otimes \mathbb{Q} \xrightarrow{d_1} I_2 \otimes \mathbb{Q}$$
because $M$ is finite, so that $M \otimes \mathbb{Q} = 0$.

Then, by proposition 1.3, there exists a surjective morphism of $G$-modules $f: I_1 \to I_0$ such that $f \circ d_0 = k \cdot \text{id}$, with $k$ dividing $|G|^2$.

Now, let $y$ be an element of $B^1 \cap \mathbb{Z}_{L_1,S}^\times$. Since $x$ is in $B^1$, there exists $x \in L_0^\times$ such that $d_0^G(x) = y$. So $s \circ d_0^G(x) = k \cdot x$ (or $x^k$ in multiplicative notation). But $d_0^G(x) = y$ is an $S$-unit, so its image by $f$ is also an $S$-unit by 1.4. Hence $k \cdot x$ is an $S$-unit. And since $\mathbb{Z}_{S,L_0}^\times$ is saturated as a subgroup of $L_0^\times$, that means $x$ is also an $S$-unit.

So $y$ is the image of an $S$-unit by $d_0^G$, ie $y \in B_S^1$. Hence $B_S^1 \subset B^1 \cap \mathbb{Z}_{L_1,S}^\times$.

□

**Definition 3.3.** In the rest of the section, if $v$ is a finite place of $K$, we will use the following notations:

• $Z_{\text{units},v}^1 = \text{Ker}(\mathbb{Z}_{L_1,v}^\times \xrightarrow{d_1} \mathbb{Z}_{L_2,v}^\times)$,

• $B_{\text{units},v}^1 = \text{Im}(\mathbb{Z}_{L_0,v}^\times \xrightarrow{d_0} \mathbb{Z}_{L_1,v}^\times)$,

• $H_{\text{units},v}^1 = \frac{Z_{\text{units},v}^1}{B_{\text{units},v}^1}$,

• $K_v^{\text{ur}}$ the largest unramified extension of $K_v$, and $I_{K_v} = \text{Gal}(\overline{K_v}/K_v^{\text{ur}})$ the inertia group, and $\mathcal{G}_{K_v} = \text{Gal}(\overline{K_v}/K)$.

• $Z_{\text{ram},v}^1 = \text{Ker}((L_0 \otimes K_v^{\text{ur}})^\times \xrightarrow{d_1} (L_1 \otimes K_v^{\text{ur}})^\times)$,

• $B_{\text{ram},v}^1 = \text{Im}((L_1 \otimes K_v^{\text{ur}})^\times \xrightarrow{d_0} (L_2 \otimes K_v^{\text{ur}})^\times)$,

• $H_{\text{ram},v}^1 = \frac{Z_{\text{ram},v}^1}{B_{\text{ram},v}^1}$.

When the context is clear, we will allow ourself to write $H_{\text{ram}}^1$, $Z_{\text{ram}}^1$ and $B_{\text{ram}}^1$.

For every place $v$ of $K$, we also denote:

• $Z_v^1 = \text{Ker}(L_{1,v}^\times \xrightarrow{d_{1,v}} L_{2,v}^\times)$

• $B_v^1 = \text{Im}(L_{0,v}^\times \xrightarrow{d_{0,v}} L_{1,v}^\times)$

• $H_v^1 = \frac{Z_v^1}{B_v^1}$.

where $d_{0,v}$ and $d_{1,v}$ are defined respectively by the two following commutative diagrams

<figure><img src="image_8.png" /></figure>
**Proposition 3.4.** With the notations of definition 3.3, we have $H_v^1 = H^1(G_{K_v}, M)$ and $H_{\text{ram}}^1 = H^1(I_{K_v}, M)$.

*Proof.* We can do the same construction as in section 2, with $K_v$ (respectively $K_v^{\text{ur}}$) instead of $K$. The same resolution

$$0 \to M \to I_0 \xrightarrow{d_0} I_1 \xrightarrow{d_1} I_2$$

also works in these cases, since the $I_i$ are also both $G_{K_v}$-modules and $I_{K_v}$ modules. Moreover, for all $i$, we have $I_i^{G_{K_v}} = L_{i,v}^{\times}$ and $I_i^{I_{K_v}} = (L_i \otimes K_v^{\text{ur}})^{\times}$. Hence the conclusion. □

Note that, by proposition 2.5, the map $\text{Res}_v : H^1(G_K, M) \to H_{1,v}$ is the natural restriction $\frac{Z_1}{B_1} \to \frac{Z_{1,v}}{B_{1,v}}$.

**Lemma 3.5.** Let $v \notin S$ be a place of $K$, then we have

$$\text{Res}_v(H_S^1(G, M)) \subseteq H_{\text{units},v}^1.$$

*Proof.* Let $v$ be a place not in $S$. Let $\bar{x}$ be a class in $H_S^1$, $x \in Z_S^1$ a representative of $\bar{x}$, and $x_v$ the localisation of $x$ at $v$. Since $v \notin S$, we have $x_v \in Z_{L_1,v}^{\times}$. And since the diagram (★) commutes, we have $x_v \in Z_v^1$. So $x_v \in \text{Ker}(Z_{L_1,v}^{\times} \xrightarrow{d_{1,v}} Z_{2,v}^{\times})$. And if $x_2 = x \cdot b$ is another representative of $\bar{x}$, with $b \in B_S^1$, then it is easy to check that $b_v \in \text{Im}(Z_{L_0,v}^{\times} \to Z_{L_1,v}^{\times})$. Hence $\text{Res}_v(\bar{x}) \in H_{\text{units},v}$.

**Proposition 3.6.** If $S$ is a set of primes such that the class group $\text{Cl}(L_0)$ is spanned by ideals above all primes in $S$, then we have

$$H_S^1 = \{x \in H^1 \mid \forall v \notin S, \text{Res}_v(x) \in H_{\text{units},v}^1\}.$$

*Proof.* By lemma 3.5, we already have the inclusion $H_S^1 \subseteq \{x \in H^1 \mid \forall v \notin S, \text{Res}_v(x) \in H_{\text{units},v}^1\}$.

Now, let $\bar{x}$ be a class in $H^1(G, M)$ such that for all place $v \notin S$, we have $\text{Res}_v(x) \in H_{\text{units},v}^1$. By definition, for all $v$, there exists $z_v$ in $L_{0,v}^{\times}$ such that $\text{Res}_v(x) \cdot d_{0,v}(z_v) \in Z_{L_1,v}^{\times}$.

We want to show that there exists $z \in L_0^{\times}$ such that for all $v \notin S$, $z \cdot z_v^{-1} \in Z_{L_0,v}^{\times}$. This problem is equivalent to taking a fractional ideal $\mathfrak{a}$ of $L_0$, and deciding whether there exists $\mathfrak{p}$ a product of prime ideals in $S$ such that $\mathfrak{a}\mathfrak{p}$ is principal. But since $S$ spans the class group of $L_0$, we know it is possible. □

**Proposition 3.7.** For every place $v$ of $K$ such that $v$ does not divide $|M|$, we have $H_{\text{units},v}^1 = \text{Ker}(\text{Res} : H^1 \to H_{\text{ram}}^1)$.
Proof. First let us show the inclusion $H_{\text{units},v}^1 \subseteq \text{Ker}(\text{Res}: H^1 \to H_{\text{ram}}^1)$.

We have the following diagram:

<figure><img src="image_9.png" /></figure>

where the three vertical sequences are exact, and where val denotes the valuation morphisms. What's more, the morphism $d_0: \mathbb{Z}^{\text{Hom}(L_0, K_v^{\text{ur}})} \to \mathbb{Z}^{\text{Hom}(L_1, K_v^{\text{ur}})}$ is injective because the kernel of $d_0: (L_0 \otimes K_v^{\text{ur}})^\times \to (L_1 \otimes K_v^{\text{ur}})^\times$ is torsion, so its image under val is 0.

Let $x \in Z_{\text{units}}^1 \subset \mathcal{O}_{L_1}^\times$. That is to say $d_1(x) = 1 \in \mathcal{O}_{L_2}^\times$. We want to show that $\text{Res}(x) = x \otimes 1 \in (L_1 \otimes K_v^{\text{ur}})^\times$ is in $B_{\text{ram}}^1 = d_0((L_0 \otimes K_v^{\text{ur}})^\times)$.

Let $N$ be an integer such that the module $M$ is annihilated by $N$, and such that $N$ does not divide the characteristic of the residue field of $\mathcal{O}_K$. Then $H_{\text{ram}}^1$ is $N$-torsion.

So there exists $y \in (L_0 \otimes K_v^{\text{ur}})^\times$ such that $\text{Res}(x)^N = d_0(y)$.

Since $x \in \mathcal{O}_{L_1}^\times$, then $\text{val}(\text{Res}(x)) = 0$, so $\text{val}(y) = 0$, so $y \in (\mathcal{O}_{L_0}^\times \otimes \mathcal{O}_{K_v^{\text{ur}}}^\times)^\times$. And $(\mathcal{O}_{L_0}^\times \otimes \mathcal{O}_{K_v^{\text{ur}}}^\times)^\times$ is $N$-divisible, so there exists $z \in (\mathcal{O}_{L_0}^\times \otimes \mathcal{O}_{K_v^{\text{ur}}}^\times)^\times$ such that $z^N = y$.

Hence $d_0(z)^N = d_0(y) = x^N$. This proves that $d_0(z) = \zeta_N x$, with $\zeta_N$ a $N$-th root of unity.

Now let us prove that for the $N$-th roots of unity, $\text{Im}(d_0) = \text{Ker}(d_1)$, which would imply the conclusion.

With the notation of section 2, we have an exact sequence

$$P_2 \xrightarrow{d_1^*} P_1 \xrightarrow{d_0^*} P_0 \xrightarrow{s} M^* \to 0.$$

Consider the modules $P_2' = \text{Im}(d_1^*)$ and $P_0' = \text{Im}(d_0^*)$. Then, by definition, we have the short exact sequence

$$0 \to P_2' \to P_1 \to P_0' \to 0.$$

By properties of Tor functors (see for example [4, chapter VI]), and because the modules $P_1, P_0', P_2'$ are $N$-torsion free, we have the
short exact sequence

$$0 \to P'_2/N \to P_1/N \to P'_0/N \to 0.$$

By taking the dual, we then get precisely that $\mathrm{Im}(d_0) = \mathrm{Ker}(d_1)$ for the $N$-th roots of unity, because for every $i$, we have $(P_i/N)^* = I_i[N]$, and $I_i[N]$ is the set of $N$-th roots of unity of $\overline{L}_i$.

Now let us show the second inclusion: $H_{\mathrm{units},v}^1 \supseteq \mathrm{Ker}(\mathrm{Res}: H^1 \to H_{\mathrm{ram}}^1)$.

Let $x$ be an element of $\mathrm{Ker}(\mathrm{Res}: H^1 \to H_{\mathrm{ram}}^1)$, that is to say an element of $L_1^\times$ such that $\mathrm{Res}(x) \in B_{\mathrm{ram}}^1$. We want to show that there exists $z \in B^1$ such that $x \cdot z^{-1} \in \mathcal{O}_{L_1}^\times$.

As $\mathrm{Res}(x)$ is in $B_{\mathrm{ram}}^1$, there exists $y \in (L_0 \otimes K_v^{\mathrm{ur}})^\times$ such that $d_0(\mathrm{val}(y)) = \mathrm{val}(\mathrm{Res}(x))$. Besides, since $x$ is in $L_1^\times$, then $\mathrm{val}(\mathrm{Res}(x))$ is invariant by the action of $\mathrm{Gal}(K_v^{\mathrm{ur}}/K)$.

So for all $g \in \mathrm{Gal}(K_v^{\mathrm{ur}}/K)$, $g \cdot d_0(\mathrm{val}(y)) = d_0(\mathrm{val}(y)) = d_0(g \cdot \mathrm{val}(y))$. Since $d_0: \mathbb{Z}^{\mathrm{Hom}(L_0, K_v^{\mathrm{ur}})} \to \mathbb{Z}^{\mathrm{Hom}(L_1, K_v^{\mathrm{ur}})}$ is injective, that means $\mathrm{val}(y)$ is also invariant by the action of $\mathrm{Gal}(K_v^{\mathrm{ur}}/K)$.

Therefore, $\mathrm{val}(y)$ is in $(\mathbb{Z}^{\mathrm{Hom}(L_0, K_v^{\mathrm{ur}})})(\mathrm{Gal}(K_v^{\mathrm{ur}}/K))$, so there exists $z \in L_0^\times$ such that $\mathrm{val}(z) = \mathrm{val}(y)$.

And thus $\mathrm{val}(\mathrm{Res}(d_0(z))) = d_0(\mathrm{val}(z)) = d_0(\mathrm{val}(y)) = \mathrm{val}(\mathrm{Res}(x))$, hence $\mathrm{val}(\mathrm{Res}(d_0(z)x^{-1})) = 0$.

So, again by injectivity, $d_0(z) = x$, hence the conclusion.

□

**Theorem 3.8.** If all prime ideals above $S$ span $\mathrm{Cl}(L_0)$ and $S$ contains all primes that divide $|M|$, then $H_S^1$ is a Selmer group. More precisely, it is the Selmer group attached to the Selmer structure where all the conditions at places outside of $S$ are unramified conditions and where there is no condition for the places in $S$.

*Proof.* The theorem is a direct consequence of proposition 3.6 and proposition 3.7.

□

**Remark 3.9.** Since every Selmer group is contained in a $H_S^1$ for some finite set of places $S$, this gives another proof that Selmer groups are finitely generated.

# 4 Algorithm and complexity

In this section, we will explain the algorithmic method to obtain a partial resolution of a finite Galois module $M$, with permutation modules,
as discussed in section 2 (See algorithm 4.2). Then, we will describe
the algorithm to compute Selmer groups, (see algorithm 4.3) and dis-
cuss its complexity (see proposition 4.5).

But first, we have to explain how to represent in bits all the math-
ematical objects involved.

Let $M$ be a finite Galois module, and $G$ be the image of the action
$G \to \mathrm{Aut}(M)$. It is a finite group, so we can represent it as a subgroup
of a permutation group. We can also suppose that we have a list
$[g_1, \cdots, g_r]$ of generators.

Since $M$ is a finite module, we can represent it as a list $[m_1, \cdots, m_s]$ of generators of $M$ as an abelian group, and a list of relations, as well as a list of matrices giving the actions of the generators of $G$ on the $m_i$.

We can represent a Selmer system $\mathcal{L}$, with a set of primes, indi-
cating the places where the local conditions are not the unramified
condition, a basis of the local cohomology groups at these places and
the generators of the subgroups in $\mathcal{L}$.

As for the Selmer group Sel<sub>ℓ</sub>, since it is a finitely generated group,
we can represent it as a list of generators and a list of relations, or by
its decomposition in cyclic factors, with the theorem of structure of
finitely generated abelian groups.

**Algorithm 4.1.**

input: A finite group $G$ and a finitely generated $G$-module $N$.

output: A permutation module $P$ and a surjective morphism of $G$-modules $s: P \to N$.

• Let $(x_1, \cdots, x_r)$ be a generating sequence of elements of $N$.

• For every element $x$ in $\{x_1, \cdots, x_r\}$,

- compute $H_x = \mathrm{Stab}_G(x)$ the stabilizer of $x$ under the action of $G$.

- Compute $f_x: \mathbb{Z}[G/H_x] \to N$, $1 \cdot H_x \mapsto x$.

• Return $P = \bigoplus_{i=1}^{r} \mathbb{Z}[G/H_{x_i}]$ and $s = \sum_{i=1}^{r} f_{x_i}$.

**Algorithm 4.2.**

input: A finite Galois module $M$, of Galois group $G$, and $G$ the image
of the action $G \to \mathrm{Aut}(M)$.

output: Permutation modules $P_i$ and morphisms of $G$-modules $s$ and $d_i^*$ such that the sequence

$$
\dots \xrightarrow{d_2^*} P_2 \xrightarrow{d_1^*} P_1 \xrightarrow{d_0^*} P_0 \xrightarrow{s} M^* \to 0
$$

is exact.
1. Compute $M^*$, take $(x_1, \cdots, x_r)$ a finite generating sequence of elements of $M^*$.

2. Using algorithm 4.1, compute a permutation module $P_0$ as well as a surjective morphism of $\mathcal{G}$-module $s: P_0 \to M^*$

3. Compute the kernel $K_0$ of $s$.

4. Use algorithm 4.1 again, on $K_0$, to obtain $P_1$ and $d_0^*$.

5. Repeat the same process again to obtain all the $P_i$ and the $d_i^*$.

Suppose we have a Selmer system $\mathcal{L}$, and we want to compute $\text{Sel}_{\mathcal{L}}$, the Selmer group attached to $\mathcal{L}$ for $M$. Using the results in part 2 and 3, we deduce the following algorithm.

**Algorithm 4.3.**

input: A finite Galois module $M$, of Galois group $\mathcal{G}$, and $G$ the image of the action $\mathcal{G} \to \text{Aut}(M)$. A Selmer system $\mathcal{L}$.

output: The Selmer group $\text{Sel}_{\mathcal{L}}$

* Use algorithm 4.2 to compute a resolution of $M$ as in section 2.

* Let $S$ be the smallest set of primes such that all conditions in $\mathcal{L}$ outside of $S$ are the unramified condition and such that $S$ spans the class group $\text{Cl}(L_0)$ and $S$ contains all the primes that divide $|M|$.

* Compute $H_S^1(G, M)$.

* Look for $\text{Sel}_{\mathcal{L}}$ as a subgroup of the finitely generated group $H_S^1(G, M)$.

**Theorem 4.4.** *The algorithms 4.1, 4.2 and 4.3 are correct.*

*Proof.* The correctness of algorithms 4.1 and 4.2 are self explanatory, and the correctness of algorithm 4.3 is a consequence of theorem 3.8. $\square$

**Proposition 4.5.** *If we suppose that we have an oracle that can give us the $S$-units and the class group of any number fields, and another that can compute the fixed field of a subgroup of a Galois group, then the algorithm 4.3 as a time complexity polynomial in the size of the input and in $|M|$.*

*Proof.* First, let us prove that algorithm 4.2 has a time complexity polynomial in the size of $M$ and $G$.

* If we have a finite $G$-module $M$ given by a list of generators $[m_1, \cdots, m_s]$ and a list of matrices $[M_1, \cdots, M_r]$, as described above, then we can represent the dual module $M^*$ by taking the
inverse transpose of all the matrices, twisted by the cyclotomic character $\chi_{|M|}$.

Indeed, all elements of $M$ are $|M|$-torsion, so $\operatorname{Hom}_{\mathbb{Z}}(M, \overline{K}^{\times}) = \operatorname{Hom}_{\mathbb{Z}}(M, \mu_{|M|})$ where $\mu_{|M|}$ is $\mathbb{Z}/|M|\mathbb{Z}$ as a $\mathcal{G}$-module where the action of $\mathcal{G}$ is given by the cyclotomic character $\chi_{|M|}$. So

$$ \operatorname{Hom}_{\mathbb{Z}}(M, \overline{K}^{\times}) = \operatorname{Hom}_{\mathbb{Z}}(M, \mathbb{Z}/|M|\mathbb{Z}) \otimes \chi_{|M|}, $$

and the dual module $M^*$ is computed in polynomial time.

* We can compute the stabilizers $\operatorname{Stab}_{\mathcal{G}}(x)$ in time polynomial in the size of $M$, using the method described in [8, Chapter 4.1].

* With the notations of section 2, the $P_i$ are all free, finitely generated, $\mathbb{Z}$-modules, they can be represented as in [8, section 7.4.1]. If $[g_1, \cdots, g_r]$ is a list of generators of $\mathcal{G}$, let $i$ be an integer, and let us fix $(p_{i,1}, \cdots, p_{i,d_i})$ be a $\mathbb{Z}$-basis of $P_i$. Then we can represent $P_i$ as a list $[\alpha_1, \cdots, \alpha_r]$ where the $\alpha_j$ are the $(d_i \times d_i)$-matrices of the actions of the $g_i$ on the basis $(p_{i,1}, \cdots, p_{i,d_i})$. So their size is still polynomial in the size of the input.

And the morphisms of $\mathcal{G}$-modules $d_0$ and $d_1$ can be represented as a list of co-sets, corresponding to their decompositions in Hecke operators (see definition 1.2).

Once we apply algorithm 4.2, we obtain an exact sequence of the form

$$ P_2 \xrightarrow{d_1} P_1 \xrightarrow{d_0} P_0 \xrightarrow{s} M^* \to 0 $$

and we represent $d_0$ and $d_1$ as a sum of cosets corresponding to Hecke operators. Then, with the notations of proposition 2.3, we can compute the number fields $L_{i,j} = \overline{K}^{H_{i,j}}$ thanks to the oracle.

Then, assuming the oracle gives us the $S$-units of all the $L_{i,j}$, with $S$ easily accessible from the representation of the Selmer system $\mathcal{L}$ and from our oracle, computing the group $H_S^1(\mathcal{G}, M)$ boils down to computing the actions of Hecke operators on $S$-units, which takes polynomial time (see [6, Theorem 1.18]).

Finally, all there is left to do is to find a basis of $\operatorname{Sel}_{\mathcal{L}}$ as a subgroup of $H_S^1(\mathcal{G}, M)$. This comes down to computing the kernel of the map

$$ H_S^1(\mathcal{G}, M) \to \prod_v \frac{H^1(G_v, M)}{L_v}. $$

□

**Remark 4.6.** To compute the fixed fields $L_{i,j} = \overline{K}^{H_{i,j}}$, one can use [7, algorithm 1]. However, the author of the present paper was unable to find a result in the literature about the complexity of this algorithm.
References

[1] Manjul Bhargava and Wei Ho. *On average sizes of Selmer groups and ranks in families of elliptic curves having marked points*. Preprint, arXiv:2207.03309 [math.NT] (2022). URL: https://arxiv.org/abs/2207.03309.

[2] Spencer Bloch and Kazuya Kato. *L-functions and Tame-gawa numbers of motives*. English. The Grothendieck Festschrift, Collect. Artic. in Honor of the 60th Birthday of A. Grothendieck. Vol. I, Prog. Math. 86, 333-400 (1990). 1990.

[3] Peter Bruin. *Extensions and torsors for finite group schemes*. 2022. arXiv: 2207.11289 [math.AG]. URL: https://arxiv.org/abs/2207.11289.

[4] Henri Cartan and Samuel Eilenberg. *Homological algebra*. English. Paperback ed. Princeton, NJ: Princeton University Press, 1999. ISBN: 0-691-04991-2.

[5] Henri Cohen. *Advanced topics in computational number theory*. English. Vol. 193. Grad. Texts Math. New York, NY: Springer, 2000. ISBN: 0-387-98727-4. DOI: 10.1007/978-1-4419-8489-0.

[6] Fabrice Etienne. *Computing class groups by induction with generalised norm relations*. 2025. arXiv: 2411.13124v2 [math.NT]. URL: https://arxiv.org/abs/2411.13124v2.

[7] Claus Fieker and Nicole Sutherland. *Constructions using Galois Theory*. 2022. arXiv: 2010.01281 [math.NT]. URL: https://arxiv.org/abs/2010.01281.

[8] Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien. *Handbook of computational group theory*. English. Discrete Math. Appl. (Boca Raton). Boca Raton, FL: Chapman & Hall/CRC Press, 2005. ISBN: 1-58488-372-3.

[9] Victor Alecsandrovich Kolyvagin. "On the Mordell-Weil group and the Shafarevich-Tate group of modular elliptic curves". English. In: *Proceedings of the international congress of mathematicians (ICM), August 21-29, 1990, Kyoto, Japan. Volume I*. Tokyo etc.: Springer-Verlag, 1991, pp. 429-436. ISBN: 4-431-70047-1.

[10] Céline Maistret and Himanshu Shukla. *On the factorization of twisted L-values and 11-descents over $C_5$-number fields*. 2025. arXiv: 2501.09515 [math.NT]. URL: https://arxiv.org/abs/2501.09515.
[11] B. Mazur. *Deforming Galois representations*. English. Galois groups over $\mathbb{Q}$, Proc. Workshop, Berkeley/CA (USA) 1987, Publ., Math. Sci. Res. Inst. 16, 385-437 (1989).

[12] Joseph H. Silverman. *The arithmetic of elliptic curves*. English. Vol. 106. Grad. Texts Math. Springer, Cham, 1986.

[13] V. E. Voskresenskiǐ. *Algebraic groups and their birational invariants*. *Transl. from the original Russsian manuscript by Boris Kunyavskii*. English. Rev. version of ‘Algebraic tori’, Nauka 1977. Vol. 179. Transl. Math. Monogr. Providence, RI: American Mathematical Society, 1998. ISBN: 0-8218-0905-9.

[14] Andrew Wiles. “Modular Elliptic Curves and Fermat’s Last Theorem”. In: *Annals of Mathematics* 141.3 (1995), pp. 443–551. ISSN: 0003486X, 19398980. URL: http://www.jstor.org/stable/2118559 (visited on 04/04/2025).

[15] Tomoyuki Yoshida. “On G-functors. II: Hecke operators and G-functors”. English. In: *J. Math. Soc. Japan* 35 (1983), pp. 179–190. ISSN: 0025-5645. DOI: 10.2969/jmsj/03510179.