# Combinatorics of Serre weights in the potentially Barsotti-Tate setting

Xavier Caruso, Agnès David, Ariane Mézard

► To cite this version:

Xavier Caruso, Agnès David, Ariane Mézard. Combinatorics of Serre weights in the potentially Barsotti-Tate setting. Moscow Journal of Combinatorics and Number Theory, 2023, 12 (1), pp.1 - 56. 10.2140/moscow.2023.12.1. hal-03221168v3

HAL Id: hal-03221168

https://cnrs.hal.science/hal-03221168v3

Submitted on 5 Nov 2021

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
COMBINATORICS OF SERRE WEIGHTS IN THE
POTENTIALLY BARSOTTI-TATE SETTING

by

Xavier Caruso, Agnès David & Ariane Mézard

**Abstract.** — Let $F$ be a finite unramified extension of $\mathbb{Q}_p$ and $\bar{\rho}$ be an absolutely irreducible mod $p$ 2-dimensional representation of the absolute Galois group of $F$. Let $t$ be a tame inertial type of $F$. We conjecture that the deformation space parametrizing the potentially Barsotti-Tate liftings of $\bar{\rho}$ having type $t$ depends only on the Kisin variety attached to the situation, enriched with its canonical embedding into $(\mathbb{P}^1)^f$ and its shape stratification. We give evidences towards this conjecture by proving that the Kisin variety determines the cardinality of the set of common Serre weights $\mathcal{D}(t, \bar{\rho}) = \mathcal{D}(t) \cap \mathcal{D}(\bar{\rho})$. Besides, we prove that this dependance is nondecreasing (the smaller is the Kisin variety, the smaller is the number of common Serre weights) and compatible with products (if the Kisin variety splits as a product, so does the number of weights).

Contents

<table><tr><td>Introduction</td><td>1</td></tr><tr><td>1. Representations, types, weights and genes</td><td>4</td></tr><tr><td>2. Combinatorial weights of a gene</td><td>12</td></tr><tr><td>3. Applications to deformations spaces</td><td>19</td></tr><tr><td>4. The bijection between W(X) and D(t, p)</td><td>30</td></tr><tr><td>Appendix A. The case of degenerated genes</td><td>41</td></tr><tr><td>Appendix B. Algorithms</td><td>45</td></tr><tr><td>References</td><td>55</td></tr></table>

Introduction

Let $p > 2$ be a prime number. For a finite extension $K$ of $\mathbb{Q}_p$, we let $\mathcal{O}_K$ denote its ring of integers, $\pi_K$ an uniformizer and $k_K$ its residue field. Let $E$ and $F$ be two extensions of $\mathbb{Q}_p$ with $E$ large enough. We set $G_F = \text{Gal}(\overline{\mathbb{Q}}_p/F)$ and fix a continuous absolutely irreducible representation $\bar{\rho} : G_F \to \text{GL}_2(k_E)$ together with a lift $\psi : G_F \to \mathcal{O}_E^\times$ of $\det \bar{\rho}$. Let $R^\psi(\bar{\rho})$ denote the universal lifting ring of $\bar{\rho}$ over $\mathcal{O}_E$ with fixed determinant $\psi$.

Given in addition a Hodge type $\lambda$ and an inertial type $t$, Kisin [Kil] has constructed a quotient $R^\psi(\lambda, t, \bar{\rho})$ of $R^\psi(\bar{\rho})$ whose $E$-rational points parametrize the potentially crystalline lifts of $\bar{\rho}$ having Hodge type $\lambda$ and inertial type $t$. The central ingredient in Kisin's argument is the construction of a scheme $\mathcal{G}R^\psi(\lambda, t, \bar{\rho})$ which is a moduli space for the
so-called Breuil-Kisin modules. This scheme is equipped with a morphism to $\text{Spec } R^\psi(\bar{\rho})$ whose schematic image is, by definition, the spectrum of $R^\psi(\lambda, t, \bar{\rho})$.

These deformation rings $R^\psi(\lambda, t, \bar{\rho})$ play a pivotal role in many deep contemporary arithmetical subjects. Understanding their structure is then a challenging question, which have been and continue to have many outstanding applications. The Breuil-Mézard conjecture [BM1, EmGe] describes the special fibre of $R^\psi(\lambda, t, \bar{\rho})$ in terms of the representation theory of $\text{GL}_2(\mathcal{O}_F)$. In its geometrical form, it predicts the following coincidence of cycles in $\text{Spec } R^\psi(\bar{\rho})$:

$$ (1) \qquad \text{Spec} \left( R^\psi(\lambda, t, \bar{\rho}) / (\pi_E) \right) = \sum_{\sigma \in \mathcal{D}} \mu_{\lambda,t}(\sigma) Z_{\bar{\rho}}(\sigma). $$

We recall briefly what are the terms in the right hand side of the above equality. The set $\mathcal{D}$ over which the sum runs is the set of Serre weights, which are by definition the irreducible representations of $\text{GL}_2(k_F)$ with coefficients in $k_E$. The factor $\mu_{\lambda,t}(\sigma)$ is the multiplicity of $\sigma$ in the Jordan-Hölder decomposition of a $\text{GL}_2(\mathcal{O}_F)$-lattice of $W_\lambda \otimes \sigma(t)$ where $W_\lambda$ is the algebraic representation of $\text{GL}_2(\mathcal{O}_F)$ associated to $\lambda$ and $\sigma(t)$ denotes the Bushnell-Kutzko type associated to $t$ (see [He]). Finally, $Z_{\bar{\rho}}(\sigma)$ is a certain cycle in $\text{Spec } R^\psi(\bar{\rho})$ which depends only on $\bar{\rho}$ and $\sigma$.

The Breuil-Mézard conjecture has been proved for $F = \mathbb{Q}_p$ by Kisin [Kil] using the $p$-adic local Langlands correspondence for $\text{GL}_2(\mathbb{Q}_p)$ and the (global) Taylor-Wiles-Kisin patching argument (without assumption of irreducibility of $\bar{\rho}$). Sander [Sa] and Paškūnas [Pa] gave a purely local alternative proof which has been extended later on by Hu and Tan to nonscalar split residual representations [HuTa]. The case where $\lambda = 0$ (which corresponds to potentially Barsotti-Tate deformations) is easier to handle. In this case, the Breuil-Mézard conjecture was established by Gee and Kisin [GeKi] (see also [CEGS, Appendix C]), who then deduced from it the weight part of the Serre's conjecture when $F/\mathbb{Q}_p$ is unramified and the Buzzard-Diamond-Jarvis conjecture [BDJ]. Some extensions of the Breuil-Mézard conjecture to 3-dimensional representations have also been considered by Le, Le Hung, Levin and Morra [LLHLM1, LLHLM2]. In all cases, the Breuil-Mézard conjecture is one of the most concrete and general statement relating representations of $G_F$ and representations of $p$-adic reductive groups and hence it paves the way towards a $p$-adic Langlands correspondence beyond the case of $\text{GL}_2(\mathbb{Q}_p)$.

In [CDM1, CDM2], we addressed the question of the effective computation of the deformation ring $R^\psi(\lambda, t, \bar{\rho})$ and considered the simplest—but already very rich and interesting—case where $F = \mathbb{Q}_{p^f}$, $\lambda = 0$ and $t$ is tame. From now, we always make these hypothesis and then omit the $\lambda$ in the notations. Our strategy for carrying out the computation of $R^\psi(t, \bar{\rho})$ was to come back to Kisin's construction and consider the scheme $\mathcal{G}\mathcal{R}^\psi(t, \bar{\rho})$. We first studied its special fibre—which is known as the *Kisin variety* associated to $(t, \bar{\rho})$—and determined explicit equations of it. In order to write them down, we associated to $(t, \bar{\rho})$ a simple combinatorial datum (it is a sequence of length $2f$ assuming values in the finite set $\{A, B, AB, O\}$) that we called the *gene*, and gave a totally explicit recipe for finding the equations of the Kisin variety by looking at the gene. Moreover, given a gene $X$ satisfying mild assumptions, we constructed a rigid space $D(X)$ and conjectured that:

$$ \text{Spm} \left( R^\psi(t, \bar{\rho}) \left[ \frac{1}{p} \right] \right) \simeq D(X) $$

as soon as $X$ is the gene of $(t, \bar{\rho})$ ([CDM2, §5.4]). In other words, we conjectured that the gene determines the generic fibre of $R^\psi(t, \bar{\rho})$. We observed in addition that our conjecture is compatible with the computations of [BM2] (which covers all the generic cases) and proved that it holds true when $f = 2$.
**Presentation of the results.** — We write $\overline{\mathcal{GR}}(t, \bar{\rho})$ for the Kisin variety attached to $(t, \bar{\rho})$; it comes equipped with a canonical embedding into $(\mathbb{P}^1)^f$ and a stratification (the so-called shape stratification). Concretely, the stratification is defined by a upper semi-continuous shape function $g: \overline{\mathcal{GR}}(t, \bar{\rho})(\mathbb{F}_p) \to \{I, II\}^f$ where I and II are two new symbols with $I \le II$. Let SEKV (for “Stratified Embedded Kisin Varieties”) be the set of subvarieties $\mathcal{V}^s$ of $(\mathbb{P}^1)^n$ (for some varying integer $n$) equipped with a upper semi-continuous shape function $g: \mathcal{V}^s(\mathbb{F}_p) \to \{I, II\}^n$. The product of varieties defines a structure of multiplicative monoid on SEKV. With these notations, we propose the following conjecture.

**Conjecture 1.** — There exists a morphism of monoids:

$$R : \mathrm{SEKV} \to \{ \text{complete noetherian } \mathcal{O}_E\text{-algebras} \}$$

(where the multiplicative structure on the codomain is given by the completed tensor product) with the property that $R^\psi(t, \bar{\rho}) \simeq R(\overline{\mathcal{GR}}(t, \bar{\rho}))$ for all absolutely irreducible Galois representation $\bar{\rho}: G_K \to \mathrm{GL}_2(k_E)$ and all nondegenerate$^{(1)}$ tame inertial type.

Conjecture 1 can be seen as a refinement of the conjectures of [CDM2], in the sense that it concerns the entire deformation space $R^\psi(t, \bar{\rho})$ and not only its generic fibre. Moreover, its formulation is more intrinsic in that it only involves Kisin varieties and avoids the use of genes.

In the present paper, we provide evidences towards Conjecture 1 at the level of the special fibre; our results are then orthogonal to that of [CDM2], the latter being uniquely concerned with the generic fibre. By the Breuil–Mézard conjecture, the special fibre of $R^\psi(t, \bar{\rho})$ is described by the quantities $\mu_t(\sigma)$ and $Z_{\bar{\rho}}(\sigma)$ appearing in Eq. (1). Since in our particular setting, $\mu_t(\sigma)$ is either 0 or 1 and $Z_{\bar{\rho}}(\sigma)$ is conjecturally either empty or isomorphic to $\mathrm{Spec} \mathcal{O}_E[[I]]$, it is sufficient to work with the following sets of Serre weights:

$$\mathcal{D}(t) = \{ \sigma \in \mathcal{D} \text{ s.t. } \mu_t(\sigma) \neq 0 \},$$

$$\mathcal{D}(\bar{\rho}) = \{ \sigma \in \mathcal{D} \text{ s.t. } Z_{\bar{\rho}}(\sigma) \neq \emptyset \},$$

$$\mathcal{D}(t, \bar{\rho}) = \mathcal{D}(t) \cap \mathcal{D}(\bar{\rho}).$$

With these notations, the $\sigma$'s in $\mathcal{D}(t, \bar{\rho})$ are exactly those that contribute to the sum in the right hand side of (1). Our main results are summarized by Theorem 2 below which can be considered as a numerical version of Conjecture 1.

**Theorem 2 (cf Theorem 3.2.1 and Corollary 3.2.8).** — There exists a nondecreasing morphism of monoids $c: \mathrm{SEKV} \to (\mathbb{N}, \times)$ with the property that $\mathrm{Card} \mathcal{D}(t, \bar{\rho}) = c(\overline{\mathcal{GR}}(t, \bar{\rho}))$ for all $\bar{\rho}$ and $t$ as in Conjecture 1.

Although the formulation of Theorem 2 again does not involve genes, its proof makes a decisive use of this notion. Precisely, we first attach to each gene $X$ a set of so-called combinatorial weights, denoted by $\mathcal{W}(X)$. These weights are simply elements of $\{0, 1\}^f$, i.e. sequences of length $f$ with values in $\{0, 1\}$. The construction of $\mathcal{W}(X)$ is purely combinatorial and elementary. We then prove the following theorem (for which we underline that the degeneracy assumption is not required).

**Theorem 3 (cf Theorems 2.3.1 and A.4.2).** — Let $\bar{\rho}: G_K \to \mathrm{GL}_2(k_E)$ be an absolutely irreducible Galois representation and $t$ be a tame inertial type. If the gene of $(t, \bar{\rho})$ is $X$, there is a canonical bijection $\mathcal{W}(X) \xrightarrow{\sim} \mathcal{D}(t, \bar{\rho})$.

<footnote>$^{(1)}$Nondegeneracy is a mild assumption; we refer to [CDM2, Definition 1.1.1] for the definition.</footnote>
Once this has been achieved, we use the results of [CDM2] (and complete them in several places) in order to relate the gene X with the Kisin variety $\overline{GR}(t, \bar{p})$ and eventually show that the cardinality of $\mathcal{D}(t, \bar{p})$ depends only on $\overline{GR}(t, \bar{p})$. Finally, the monotony property and the compatibility with products follow by examining closely the construction of $W(X)$.

**Some perspectives.** — Theorem 3 is much finer that Theorem 2 in the sense that it not only provides a formula for the cardinality of $\mathcal{D}(t, \bar{p})$ but it establishes a bijection between the latter set and an auxiliary set of weights. This observation leads us to our first vague question: can we attach to any $\mathcal{V}^s \in \text{SEKV}$ a set of weights $W(\mathcal{V}^s)$ and, given $(t, \bar{p})$ as before, construct a canonical bijection:

$$ \mathcal{D}(t, \bar{p}) \xrightarrow{\sim} W(\overline{GR}^{\psi}(t, \bar{p})) $$

in line with Theorem 2? It is worth noticing that the set $W(X)$ does not make the job because it does not only depend on $\overline{GR}(t, \bar{p})$. However, beyond this obvious obstruction, we really want elements of $W(\mathcal{V}^s)$ to be intrinsic objects with a deep arithmetical meaning (e.g. modular representations of some group) and not simply sequences of integers. A new approach is then definitely needed.

Another striking fact, we think, is that most of the combinatorial constructions and arguments we shall develop in this article are completely independent of $p$. Basically, the notion of gene, and consequently all its derivations, do not involve any prime number. In particular, the fact that the equations of $\overline{GR}(t, \bar{p})$ are explicitely given by the gene shows that the Kisin varieties themselves are mostly independant from $p$; to be precise, they are defined over $\mathbb{F}_1$, the field with one element. This strong uniformity with respect to $p$ might suggest that, at least in the particular case we are looking at (i.e. 2-dimensional potentially Barsotti-Tate representations with tame inertial type), the $p$-adic Langlands correspondence could be “defined over” a common base for all the $\mathbb{Z}_p$'s, e.g. $\mathbb{Z}$ or, maybe, the speculative ring of Witt vectors over $\mathbb{F}_1$ [Co]. Could we dream of a 1-adic Langlands correspondence whose purpose would be to summarize in a nice and uniform way all the combinatorial parts of the $p$-adic Langlands correspondence?

**Organization of the paper.** — In §1, we introduce the notations and the main objects of this article: Galois representations, inertial type, Serre weights and genes. In §2, we construct the set $W(X)$ and state a precise version of Theorem 3 under a mild nondenegaracy assumption on the gene X. Several results about the cardinality of $W(X)$ are discussed. In §3, we clarify the relationships between genes and Kisin varieties and prove Theorem 2. For the convenience of the reader, the proof of Theorem 3, which is long and intricate, is postponed to §4. The article is supplemented with two appendices. Appendix A is of technical nature and aims at removing the aforementioned nondegenaracy assumption. In Appendix B, we design efficient algorithms for counting and enumerating weights. An implement of these algorithms in SageMath is also presented.

*Grants.* — The three authors are supported by the ANR project CLap-CLap (ANR-18-CE40-0026-01).

# 1. Representations, types, weights and genes

The aim of this introductory section is to present the panel of objects we work with in this article. These are Galois representations, inertial types (§1.1), Serre weights (§1.2) and
genes (§1.3-1.4). We recall the classification of 2-dimensional irreducible modular Galois representations and tame inertial types and the definition by Breuil and Paškūnas [BP] of the set of Serre weights associated to these objects (§1.2). We recall, from [CDM2], the definition of the gene and give its first properties.

Throughout this paper, we fix a prime number $p > 2$ together with an algebraic closure $\overline{\mathbb{Q}}_p$ of $\mathbb{Q}_p$. All the algebraic extensions we consider in this article live inside $\overline{\mathbb{Q}}_p$. We consider an integer $f \ge 2$ and set $q = p^f$. We let $F$ be the unique unramified extension of $\mathbb{Q}_p$ of degree $f$. We denote its ring of integers by $\mathcal{O}_F$; it is a local ring with maximal ideal $(p)$ and residue field of cardinality $q$. Let $G_F = \text{Gal}(\overline{\mathbb{Q}}_p/F)$ be the absolute Galois group of $F$.

We fix a finite extension $E$ of $\mathbb{Q}_p$ and denote its ring of integers $\mathcal{O}_E$ and its residue field by $k_E$. This extension $E$ is the field of coefficients of our representations. Actually, if it had been possible, it would have been easier to work with representations with coefficients in $\overline{\mathbb{Q}}_p$; however, finiteness assumptions are needed in several places, which discards this option. It is the reason why we introduce $E$; nevertheless, we constantly allow ourselves to enlarge $E$ if needed.

**1.1. Representations and types.** — The first objects of interest we study in this paper are Galois representations of $G_F$. Precisely, we consider a continuous 2-dimensional absolutely irreducible representation $\bar{\rho} : G_F \to \text{GL}_2(k_E)$. Such a representation actually admits a very concrete description. Indeed, let $F'$ be the unique unramified extension of $F$ of degree 2 and set $G_{F'} = \text{Gal}(\overline{\mathbb{Q}}_p/F')$. Assuming that $E$ contains $F'$, there exists an integer $h$ and an element $\theta \in k_E^\times$ such that $\bar{\rho}$ takes the form:

$$ (2) \qquad \bar{\rho} \simeq \text{Ind}_{G_{F'}}^{G_F} \left( \omega_{2f}^h \cdot \text{nr}'(\theta) \right) $$

where $\omega_{2f}$ is the fundamental character of $G_{F'}$ of level $2f$ and $\text{nr}'(\theta)$ denotes the unique unramified character of $G_{F'}$ sending the arithmetic Frobenius to $\theta$. In what precedes, $h$ must be not divisible by $q+1$ (in order to guarantee that $\bar{\rho}$ is absolutely irreducible). Moreover, it is uniquely determined modulo $q^2-1$ and modulo the transformation $h \mapsto qh$.

The second objects we are interested in are inertial types. Let $I_F$ denote the inertial subgroup of $G_F$. By definition, an inertial type (or simply a type) is a representation of $I_F$ which admits a prolongation to $G_F$. In the present article, we only work with 2-dimensional tame types, that are types which factor through the tame inertia. Like Galois representations, those types admit very concrete descriptions as they all take the form:

$$ (3) \qquad t = \omega_f^\gamma \oplus \omega_f^{\gamma'} $$

where $\omega_f$ denotes (the restriction to $I_F$ of) the fundamental character of $G_F$ of level $f$ and $\gamma$ and $\gamma'$ are integers, which are uniquely defined modulo $q-1$.

To those data, one can associate deformation spaces. For this, we fix in addition a character $\psi : G_F \to \mathcal{O}_E^\times$ lifting $\det \bar{\rho}$. We let $R^\psi(\bar{\rho})$ denote the universal deformation ring parametrizing the liftings of $\bar{\rho}$ having determinant $\psi$. From [Ki3], we know that there exists a unique reduced quotient $R^\psi(t, \bar{\rho})$ of $R^\psi(\bar{\rho})$ whose $E$-rational points parametrize the representations $\rho : G_F \to \text{GL}_2(E)$ of determinant $\psi$ and semi-simplification $\bar{\rho}$, exhibiting in addition the two following extra properties:

(1) $\rho$ is potentially crystalline of type $t$;

(2) the Hodge-Tate weights of $\rho$ are $\{0, 1\}$ for each embedding $F \hookrightarrow E$.
In order to have a chance that $R^\psi(t, \bar{\rho})$ does not vanish, one has to impose a compatibility condition on the determinants. It reads:

$$ (4) \qquad \det \bar{\rho}|_{I_F} = \varepsilon \cdot \det t $$

where $\varepsilon$ denotes the cyclotomic character mod $p$. Coming back to the explicit descriptions of $\bar{\rho}$ and $t$, this condition translates to a numerical congruence connecting the parameters $h, \gamma$ and $\gamma'$, namely:

$$ (5) \qquad h \equiv \gamma + \gamma' + \frac{q-1}{p-1} \pmod{q-1}. $$

**Definition 1.1.1.** — A coherent triple is a triple

$$ (h, \gamma, \gamma') \in \mathbb{Z}/(q^2-1)\mathbb{Z} \times \mathbb{Z}/(q-1)\mathbb{Z} \times \mathbb{Z}/(q-1)\mathbb{Z} $$

such that $h$ is not divisible by $q+1$ and the congruence (5) holds.

A coherent triple then encodes a pair $(\bar{\rho}|_{I_F}, t)$ with $\bar{\rho}$ absolutely irreducible and condition (4) satisfied. We underline that this encoding is surjective but not injective. Precisely, two triples $(h_1, \gamma_1, \gamma'_1)$ and $(h_2, \gamma_2, \gamma'_2)$ correspond to isomorphic $(\bar{\rho}|_{I_F}, t)$ when $h_1 \equiv qh_2 \pmod{q^2-1}$ or $(\gamma_1, \gamma'_1) = (\gamma'_2, \gamma_2)$. In what follows, we often work with coherent triples instead of pairs $(t, \bar{\rho})$ because they are more suitable for the combinatorial constructions we develop in this paper.

**1.2. Serre weights.** — In this subsection, we recall the notation for Serre weights and the definitions of the sets of Serre weights associated to an irreducible 2-dimension representation $\bar{\rho}$ and a tame inertial type $t$.

**1.2.1. Definition of Serre weights.** — A Serre weight is an (isomorphism class of an) absolutely irreducible $k_E$-representation of the group $\text{GL}_2(k_F)$. Again, one has a concrete description of Serre weights. Before giving it, we need to introduce further notations. First, we let $\tau_0$ denote the inclusion $F \hookrightarrow E$ and, for each integer $i$, we set $\tau_i = \tau_0^{p_i^{-i}}$. The $\tau_i$'s then exhaust all the field embeddings from $F$ into $E$. Second, given a positive integer $r$ and an embedding $\tau : F \to E$, we let $(\text{Sym}^r k_E^2)^\tau$ denote the space of homogeneous bivariate polynomials over $k_E$ of degree $r$ and endow it with the action of $\text{GL}_2(k_F)$ defined by:

$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot P(X, Y) = P(\tau(a)X + \tau(b)Y, \tau(c)X + \tau(d)Y). $$

With these notations, one proves that any Serre weight takes the following form:

**Proposition 1.2.1.** — Any Serre weight can be written as

$$ (6) \qquad \sigma_{s, \underline{r}} \simeq (\tau_0 \circ \det^s) \otimes \bigotimes_{i=0}^{f-1} (\text{Sym}^{r_i} k_E^2)^{\tau_i} $$

where $s$ is an integer modulo $q-1$ and the $r_i$'s are integers in the range $\{0, 1, \dots, p-1\}$ with $\underline{r} = (r_0, \dots, r_{f-1}) \neq (p-1, \dots, p-1)$. Moreover, in the above writing, both $s$ and $\underline{r}$ are uniquely determined.
Serre weights associated to Galois representation and inertial type. — To each Galois representation $\bar{\rho}$ (resp. inertial type t) as in §1.1, one associates a set of Serre weights, which is denoted by $\mathcal{D}(\bar{\rho})$ (resp. by $\mathcal{D}(t)$). The construction of these sets is given by a combinatorial recipe that we recall now.

Let $\bar{\rho}$ be the 2-dimensional absolutely irreducible Galois representation associated with the parameters $h$ and $\theta$ thanks to Eq. (2). We consider the following equation:

$$ (7) \qquad h \equiv \sum_{i=0}^{f-1} (-1)^{\varepsilon_i} p^i (1+r_i) \pmod{q+1} $$

whose unknowns are $\varepsilon = (\varepsilon_0, \dots, \varepsilon_{f-1})$ and $\underline{r} = (r_0, \dots, r_{f-1})$. Precisely we seek solutions of this equation with $\varepsilon_i \in \{0, 1\}$ and $r_i \in \{0, \dots, p-1\}$ for all $i$. To each such solution, one associates the Serre weight $\sigma_{s,\underline{r}}$ where $s$ is defined by:

$$ (8) \qquad s \equiv \frac{1}{q+1} \left( h - \sum_{i=0}^{f-1} (-1)^{\varepsilon_i} p^i (1+r_i) \right) - \sum_{i=0}^{f-1} \varepsilon_i p^i (1+r_i) \pmod{q-1}. $$

**Definition 1.2.2.** — The set $\mathcal{D}(\bar{\rho})$ is defined as the set of Serre weights associated to solutions of (7).

Let $t = \omega_f^\gamma \oplus \omega_f^{\gamma'}$ be an inertial type and let $c_0, \dots, c_{f-1} \in \{0, 1, \dots, p-1\}$ be the integers defined by the following congruence:

$$ \gamma - \gamma' \equiv \sum_{i=0}^{f-1} c_i p^i \pmod{q-1}. $$

When $\gamma \equiv \gamma' \pmod{q-1}$, then $c_0 = \dots = c_{f-1} = 0$. Given $\varepsilon_0', \dots, \varepsilon_{f-1}' \in \{0, 1\}$, we form the tuple $\underline{r} = (r_0, \dots, r_{f-1})$ defined by the rules summarized in the following table (see [BP, Da]):

$$ (9) \qquad \begin{array}{c|cc} r_i & \varepsilon_{i-1}' = 0 & \varepsilon_{i-1}' = 1 \\ \varepsilon_i' = 0 & c_i & c_i - 1 \\ \varepsilon_i' = 1 & p - 2 - c_i & p - 1 - c_i \end{array} $$

where we have set $\varepsilon_{-1}' = \varepsilon_{f-1}'$. When all the $r_i$'s lie in $\{0, \dots, p-1\}$, we further form the Serre weights $\sigma_{s,\underline{r}}$ where $s \in \mathbb{Z}/(q-1)\mathbb{Z}$ is given by the formula:

$$ (10) \qquad s \equiv \gamma' + \frac{1}{2} \left( \varepsilon_{f-1}'(q-1) + \sum_{i=0}^{f-1} (c_i - r_i) p^i \right) \pmod{q-1}. $$

If one of the $r_i$'s falls outside the interval $[0, p-1]$, the procedure fails and does not produce a Serre weight.

**Definition 1.2.3.** — The set $\mathcal{D}(t)$ is the collection of all the Serre weights obtained by Table (9) when the family $(\varepsilon_i')_{i \in \mathbb{Z}/f\mathbb{Z}}$ varies in $\{0, 1\}^f$.

**Lemma 1.2.4.** — With the above notations, the integer $s$ is alternatively given by:

$$ s \equiv \gamma' + \sum_{i=0}^{f-1} \varepsilon_i' (p-1-r_i) p^i \pmod{q-1}. $$
Moreover, for any integer $i_0 \in \{0, \dots, f-1\}$, we have the formula:

$$s \equiv \gamma' + \frac{1}{2} \left( \varepsilon'_{i_0} (q-1) + \sum_{i=0}^{f-1} \lambda_{i+i_0} (c_i - r_i) p^i \right) \pmod{q-1}$$

where, by definition, $\lambda_j = q$ if $j < f-1$ and $\lambda_j = 1$ otherwise.

**Proof.** — It follows by inspection that $c_i - r_i = \varepsilon'_i (p - 2 - 2r_i) - \varepsilon'_{i-1}$ for all $i$. Injecting this relation and reorganizing terms, we obtain:

$$\sum_{i=0}^{f-1} (c_i - r_i) p^i = \varepsilon'_{f-1} (1-q) + 2 \sum_{i=0}^{f-1} \varepsilon'_i (p-1-r_i) p^i.$$

Plugging this in Eq. (10), we get the first part of the lemma. The second part is proved similarly. □

**Remark 1.2.5.** — Lemma 1.2.4 shows that the datum of a type t and a weight $\sigma_{s,\bar{r}} \in \mathcal{D}(t)$ uniquely determines the $\varepsilon'_i$'s since any single $\varepsilon'_{i_0}$ can be recovered from $s, \bar{r}$ and the $c_i$'s thanks to second formula of Lemma 1.2.4.

*Common weights.* — Given $\bar{p}$ and t as above, we define the set of common weights as

**Definition 1.2.6.** — The set of common Serre weights of $\bar{p}$ and t is

$$\mathcal{D}(t, \bar{p}) = \mathcal{D}(\bar{p}) \cap \mathcal{D}(t).$$

If we fix in addition a character $\psi : G_F \to \mathcal{O}_E^\times$ lifting det $\bar{p}$, the Breuil–Mézard conjecture (which is a theorem in this setting, [GeKi]) relates the set $\mathcal{D}(t, \bar{p})$ to the special fibre of the deformation space Spec $R^\psi(t, \bar{p})$. More precisely, its geometric version states that there is an equality of cycles in Spec($k_E \otimes_{\mathcal{O}_E} R^\psi(\bar{p})$):

$$\mathrm{Spec} (k_E \otimes_{\mathcal{O}_E} R^\psi(t, \bar{p})) = \sum_{\sigma \in \mathcal{D}(t, \bar{p})} Z(\sigma)$$

where $Z(\sigma)$ depends only on $\sigma$. In our context, it is moreover expected that the $Z(\sigma)$'s are all smooth but, to the best of our knowledge, this has not been proved yet. In this article, we give an explicit combinatorial description of the set $\mathcal{D}(t, \bar{p})$ (Theorem 2.3.1) and, consequently, shed new lights on the description of special fibre of $R^\psi(t, \bar{p})$.

**1.3. The gene of $(h, \gamma, \gamma')$.** — In [CDM2], with the perspective of writing down explicit equations of the deformation rings $R^\psi(t, \bar{p})$, we have associated to each pair $(t, \bar{p})$ a combinatorial data that we called the *gene*. We have conjectured (see [CDM2, Conjecture 5.1.6]) that the gene determines the generic fibre of $R^\psi(t, \bar{p})$ (by an explicit recipe) and, as a first step in this direction, we have shown that it actually determines the Kisin variety associated to $(t, \bar{p})$ (see §3.1.1 for more details).

In this subsection, we recall the definition of the gene and prove some additional combinatorial facts about it. We fix a coherent triple $(h, \gamma, \gamma')$ and consider the integers $h_0, \dots, h_{f-1}$ in $\{0, \dots, p-1\}$ uniquely defined by the congruence:

$$(11) \qquad h \equiv 1 + \sum_{i=0}^{f-1} h_i p^{f-1-i} \pmod{q+1}.$$

We set $h_i = p-1 - h_{i-f}$ for $i \in \{f, f+1, \dots, 2f-1\}$ and $h_i = h_i \pmod{2f}$ for all $i \in \mathbb{Z}$. By construction, the sequence $(h_i)_{i \in \mathbb{Z}}$ is periodic with period $2f$.

**Definition 1.3.1.** — Let $\nu = p^{f-1} + \dots + p$. For $i \in \mathbb{Z}$, we define:
(1) the integer $\alpha_i$ as the unique integer in $\{0, \dots, q-2\}$ satisfying the congruence:

$$ \alpha_i \equiv \left\lfloor \frac{p^i h}{q+1} \right\rfloor - p^i \gamma' \pmod{q-1} $$

(2) the symbol $X_i \in \{\text{A}, \text{B}, \text{AB}, \text{O}\}$ by:

$$ \begin{align*} X_i &= \text{A} & \text{if } \alpha_i \in [0, \frac{1}{p} \nu + \iota_{i+f}] \\ &= \text{AB} & \text{if } \alpha_i \in [\frac{1}{p} \nu + \iota_{i+f}, \frac{p-1}{p} \nu - \iota_i] \\ &= \text{B} & \text{if } \alpha_i \in [\frac{p-1}{p} \nu - \iota_i, \nu] \\ &= \text{O} & \text{if } \alpha_i \in [\nu, e] \end{align*} $$

where $\iota_i = 1$ if $h_i = p-1$ and $\iota_i = 0$ otherwise.

The sequence $\mathbb{X} = (X_i)_{i \in \mathbb{Z}}$ is called the gene of $(h, \gamma, \gamma')$.

As we did in [CDM2], we will always picture a gene on two rows, writing down the $f$ first symbols $X_0, \dots, X_{f-1}$ on the top row and the others on the bottom one (this is justified by the fact that the pair $(X_i, X_{i+f})$ plays a quite important role). For example, the gene of length 7

$$ \mathbb{X} = (\dots, X_0, \dots, X_{13}, \dots) = (\dots, \mathbf{O}, \text{A}, \text{B}, \text{A}, \text{AB}, \mathbf{O}, \text{A}, \text{B}, \text{A}, \text{AB}, \mathbf{O}, \mathbf{O}, \text{B}, \text{AB}, \dots) $$

is drawn as follows:

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

The next proposition is proved in [CDM2, Lemme 2.1.4].

**Proposition 1.3.2.** — Let $\mathbb{X} = (X_i)_{i \in \mathbb{Z}}$ be the gene of $(h, \gamma, \gamma')$. Then:

(i) if $X_i = \text{AB}$ for some integer $i$, then $X_{i+1} = \mathbf{O}$;

(ii) if $X_i = \mathbf{O}$ for some integer $i$, then $X_{i-1} \in \{\text{AB}, \mathbf{O}\}$.

Given a coherent triple $(h, \gamma, \gamma')$, we let $v_0, \dots, v_{2f-1}$ be the unique integers in the range $[0, p-1]$ such that:

$$ (12) \quad h - (q+1)\gamma' \equiv p^{2f-1}v_0 + p^{2f-2}v_1 + \dots + pv_{2f-2} + v_{2f-1} \pmod{q^2-1}. $$

We extend the definition of the $v_i$'s to all indices $i \in \mathbb{Z}$ by letting $v_i = v_i \bmod{2f}$. It turns out that the $v_i$'s are closely related to the gene of $(h, \gamma, \gamma')$. The next lemma, which we use repeatedly in this article, makes these relationships precise.

**Lemma 1.3.3.** — Let $\mathbb{X} = (X_i)_{i \in \mathbb{Z}}$ be the gene of $(h, \gamma, \gamma')$ and $(v_i)_{i \in \mathbb{Z}}$ defined by Eq. (12). For all integers $i \in \mathbb{Z}$, the following holds:

(a) if $X_i = \text{A}$, then $v_i = 0$;

(ab) if $X_i = \text{AB}$, then $v_i = 0$;

(b) if $X_i = \text{B}$, then $v_i = 1$;

(o) if $X_i = \mathbf{O}$, then $v_i \ge 1$.
*Proof.* — Write $v = h - (q+1)\gamma'$. A direct computation shows that $p^i v \equiv a_i q + a_{i+f}$ where the $a_i$'s are defined by $a_i = p^{f-1}v_i + p^{f-2}v_{i+1} + \cdots + v_{i+f-1}$. Moreover, we have:

$$ \alpha_i = \left\lfloor \frac{p^i v}{q+1} \right\rfloor \mod (q-1) = \left\lfloor a_i + \frac{a_{i+f} - a_i}{q+1} \right\rfloor = \begin{cases} a_i & \text{if } a_{i+f} \ge a_i \\ a_i - 1 & \text{otherwise.} \end{cases} $$

Let us now assume that $X_i = A$. By definition, we then have

$$ \alpha_i \le 1 + p + p^2 + \cdots + p^{f-2} < p^{f-1} - 1. $$

Thus $a_i \le \alpha_i + 1 < p^{f-1}$ and, coming back to the definition of the $a_i$'s, we deduce $v_i = 0$. We have proved (a). Similarly, if $X_i = 0$, we obtain $a_i \ge p + p^2 + \cdots + p^{f-1}$ and then deduce $v_i \ge 1$, which proves (o).

Let us now consider the case where $X_i = AB$. Then $\alpha_i \le p^{f-1} - 1$ and so $a_i \le p^{f-1}$. We deduce from this that $v_i = 0$ except maybe in the very special case where $a_i = p^{f-1}$. However, if this happens, we deduce in addition that $v_{i+1} = \cdots = v_{i+f-1} = 0$. This implies in particular that $X_{i+1} \ne 0$, which is a contradiction. Consequently, $v_i = 0$ in all cases and we have proved (ab).

Finally, if $X_i = B$, we get the estimation:

$$ p^{f-1} - 1 \le a_i \le p + p^2 + \cdots + p^{f-1}. $$

Therefore $v_i = 1$ except maybe in the particular case where $a_i = p^{f-1} - 1$. However, in this case, we also have $v_{i+1} = \cdots = v_{i+f-1} = p-1$. From (a) and (ab), we deduce that $X_{i+1}$ cannot be $A$ nor $AB$. It cannot also be $B$ by what we have just done. Therefore $X_{i+1}$ must be $0$, which contradicts the fact that $X_i = B$. $\square$

**Corollary 1.3.4.** — Let $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ be the gene associated to a coherent triple $(h, \gamma, \gamma')$. Then there exists an integer $i$ such that $X_i = 0$ or $X_i \ne X_{i+f}$.

*Proof.* — We argue by contradiction and assume that $X_i = X_{i+f} \in \{A, B\}$ for all $i$. Note that it is safe to assume $X_i \ne AB$ because otherwise, we would have $X_{i+1} = 0$, which we exclude. Let $v_0, \dots, v_{2f}$ be the integers introduced above. From Lemma 1.3.3, we know that $v_i = 0$ if $X_i = A$, and $v_i = 1$ if $X_i = B$. From our assumption, we then derive that $v_i = v_{i+f}$ for all $i$. Plugging this in the congruence (12), we find that $h$ is divisible by $q+1$, which contradicts the fact that $\bar{\rho}$ is absolutely irreducible. $\square$

**Remark 1.3.5.** — We prove in §B.1 several refined versions of Lemma 1.3.3 and Corollary 1.3.4 (see for instance Proposition B.1.7).

**1.4. Abstract genes.** — For the purpose of this article, it is relevant to introduce an abstract definition of a gene; it is the aim of this subsection. Our definition is simply obtained by gathering the properties enlightened in Proposition 1.3.2 and Corollary 1.3.4.

**Definition 1.4.1.** — A gene of length $f$ is a $(2f)$-periodic sequence $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ assuming values in the finite set $\{A, B, AB, 0\}$ and satisfying the following conditions:

(i) if $X_i = AB$ for some integer $i$, then $X_{i+1} = 0$;

(ii) if $X_i = 0$ for some integer $i$, then $X_{i-1} \in \{AB, 0\}$;

(iii) there exists an integer $i$ such that $X_i = 0$ or $X_i \ne X_{i+f}$.

A gene $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ is said degenerate if $X_i \ne 0$ for all $i$; other it is nondegenerate.

**Remark 1.4.2.** — In [CDM2, Lemme 2.1.6], the case where $\{X_i, X_{i+f}\} = \{A, B\}$ for all index $i$ is also excluded because it corresponds to a type with $\gamma = \gamma'$. In the current paper, we do not want to discard such types; it is the reason why we have not incorporated this condition in Definition 1.4.1.
**Remark 1.4.3.** — By [CDM2, Lemme 2.1.5], we know that such degenerate genes correspond to very special representations, which are called degenerate in loc. cit. (see [CDM2, Definition 1.1.1]). The terminology is then coherent.

The next proposition shows that Definition 1.4.1 exactly captures the genes we are interested in.

**Proposition 1.4.4.** — We assume $p > 3$. Given a gene $\mathcal{X}$, there exists a coherent triple $(h, \gamma, \gamma')$ whose associated gene is $\mathcal{X}$.

*Proof.* — Let $(v_i)_{i \in \mathbb{Z}}$ be a sequence of integers such that:

$$ 
\begin{array}{ll}
v_i = 0 & \text{if } X_i \in \{\mathbf{A}, \mathbf{AB}\}, \\
v_i = 1 & \text{if } X_i = \mathbf{B}, \\
2 \le v_i \le p-1 & \text{if } X_i = \mathbf{0}
\end{array}
$$

and $v_i \ne v_{i+f}$ for at least one index $i$. The condition (iii) of Definition 1.4.1 guarantees that such a sequence always exists.

We set $h = p^{2f-1}v_0 + p^{2f-2}v_1 + \cdots + v_{2f-1}$ and $\gamma' = 0$. We let $\gamma$ be an integer for which the compatibility relation (5) holds. Let us first check that $h$ is not divisible by $q+1$. A simple calculation shows that $q+1$ divides $h$ if and only if

$$ \sum_{i=0}^{f-1} p^{f-1-i} v_{i+f} \equiv \sum_{i=0}^{f-1} p^{f-1-i} v_i \pmod{q+1}. $$

Since the $v_i$'s are between 0 and $p-1$, this can only occur if $v_i = v_{i+f}$ for all $i$, which does not hold by construction.

Let $(\alpha'_i)_{i \in \mathbb{Z}}$ and $(v'_i)_{i \in \mathbb{Z}}$ be the sequences of integers associated to $(h, \gamma, \gamma')$ (see §1.3) and $\mathcal{X}' = (X'_i)_{i \in \mathbb{Z}}$ be the corresponding gene. It is clear from the construction of $h$ and $\gamma'$ that $v'_i = v_i$ for all $i$. We have to show that this implies $\mathcal{X} = \mathcal{X}'$.

For this, we consider an integer $i$. If $X_i = \mathbf{0}$, then $v'_i > 1$ and Lemma 1.3.3 ensures that $X'_i = \mathbf{0}$ as well. If $X_i = \mathbf{AB}$, then $X_{i+1} = \mathbf{0}$. By what we have done before, we find $X'_{i+1} = \mathbf{0}$ as well. Hence $X'_i \in \{\mathbf{AB}, \mathbf{0}\}$. Since $v'_i = 0$, Lemma 1.3.3 then guarantees that $X'_i$ cannot be $\mathbf{0}$. Therefore $X'_i = \mathbf{AB}$. If $X_i = \mathbf{B}$, Lemma 1.3.3 shows that $X'_i \in \{\mathbf{B}, \mathbf{0}\}$, which is a priori not enough to conclude. However, coming back to the proof of Lemma 1.3.3 and setting

$$ a'_i = p^{f-1}v'_i + p^{f-2}v'_{i+1} + \cdots + v'_{i+f-1} $$

we find $a'_i \le p + p^2 + \cdots + p^{f-1}$. Thus $\alpha'_i \le p + p^2 + \cdots + p^{f-1}$ as well, which discards the option $X'_i = \mathbf{0}$. Finally, if $X_i = \mathbf{A}$, applying Lemma 1.3.3, we obtain $X'_i \in \{\mathbf{A}, \mathbf{AB}\}$. But $X'_i = \mathbf{AB}$ would imply that $X'_{i+1} = \mathbf{0}$, which is impossible because $X_{i+1} \in \{\mathbf{A}, \mathbf{B}, \mathbf{AB}\}$. $\square$

To conclude this section, we recall the definition of viability.

**Definition 1.4.5.** — Let $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ be a gene. We say that $\mathcal{X}$ is not viable if there exists $i$ such that $X_i = X_{i+1} = \mathbf{0}$. It is viable otherwise.

It has been shown in [CDM2, Proposition 4.1.3] that the gene of $(h, \gamma, \gamma')$ is viable if and only if the corresponding deformation space is not zero.
## 2. Combinatorial weights of a gene

In this section, we first associate to a gene $\mathcal{X}$ a set of *combinatorial weights*, denoted by $\mathcal{W}(\mathcal{X})$. For this, we decompose the gene $\mathcal{X}$ into fragments and work on each fragment separately. The set $\mathcal{W}(\mathcal{X})$ is defined as the product of sets of weights associated to each fragment. Then, we give several properties of $\mathcal{W}(\mathcal{X})$; we prove in particular that $\mathcal{W}(\mathcal{X})$ is not empty if and only if the gene is viable (see Theorem 2.2.1) and give general upper bounds on the cardinality of $\mathcal{W}(\mathcal{X})$ in terms of Fibonacci numbers (see Theorem 2.2.4). Finally, we formulate a precise statement of Theorem 3 of the introduction.

For the convenience of the readers, we always assume in this section that the gene $\mathcal{X}$ is nondegenerate. The constructions in the general case follows the same pattern but are much more technical; they are presented in Appendix A.

**2.1. Construction of $\mathcal{W}(\mathcal{X})$.** — We begin with the definition of the combinatorial weights.

**Definition 2.1.1.** — A *combinatorial weight* of length $f$ is a $f$-periodic sequence assuming values in $\{0, 1\}$.

By definition, a combinatorial weight of length $f$ is determined by its values on $\{0, 1, \dots, f-1\}$. We then can alternatively think of it as a subset of $\{0, 1, \dots, f-1\}$. In any case, there are exactly $2^f$ combinatorial weights of length $f$.

When the gene $\mathcal{X}$ is not viable, we just set $\mathcal{W}(\mathcal{X}) = \emptyset$. The rest of this subsection is devoted to the construction of $\mathcal{W}(\mathcal{X})$ when $\mathcal{X}$ is viable. From now on, we pick a nondegenerate gene $\mathcal{X}$ (in the sense of Definition 1.4.1) and assume that it is viable.

To start with, we decompose $\mathcal{X}$ into fragments $\underline{F}$ by cutting vertically the gene before each occurrence of $0$. Before giving formal definitions, it is enlighting to visualize the constructions on a simple example.

**Example 2.1.2.** — The following gene:

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

has four fragments $\underline{F}$, which are:

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

Formally, a *fragment* can be defined as follows.

**Definition 2.1.3.** — A *fragment* $\underline{F}$ of length $\ell$ is a tuple $(F_0, F_1, \dots, F_{\ell-1})$ where each $F_i$ is a pair $(F_i^\uparrow, F_i^\downarrow) \in \{\text{A}, \text{B}, \text{AB}, \text{O}\}^2$ satisfying the following requirements:

(L) $F_0^\uparrow = 0$ or $F_0^\downarrow = 0$, but $(F_0^\uparrow, F_0^\downarrow) \neq (0, 0)$,

(C) $F_i^\uparrow \neq 0$ and $F_i^\downarrow \neq 0$ for $i > 0$,
$F_i^\uparrow \neq \text{AB}$ and $F_i^\downarrow \neq \text{AB}$ for $i < \ell-1$,
(R) if $\ell > 1$: $F_{\ell-1}^{\uparrow} = AB$ or $F_{\ell-1}^{\downarrow} = AB$, but $(F_{\ell-1}^{\uparrow}, F_{\ell-1}^{\downarrow}) \neq (AB, AB)$.

To a fragment $\underline{F}$ of length $\ell$, we associate a set $W(\underline{F})$ of fragmentary combinatorial weights, which are tuples $(w_0, \dots, w_{\ell-1})$ in $\{0, 1\}^\ell$. In order to handle smoothly corner cases, it is convenient to introduce the equivalence relation $\sim$ on $\{A, B, AB, O\}$ whose two equivalence classes are $\{A, AB\}$ and $\{B, O\}$.

**Definition 2.1.4.** — Let $\underline{F} = (F_0, \dots, F_{\ell-1})$ be a fragment of length $\ell$ and write $F_i = (F_i^{\uparrow}, F_i^{\downarrow})$. We define three sequences $(W_i^{(b,a)})_{0\le i<\ell}$, $(W_i^{(a,b)})_{0\le i<\ell}$, $(W_i^{(b,a)})_{0\le i<\ell}$ by:

* $W_0^{(b,b)} = \emptyset$ if $\ell=1$ and $(F_0^{\uparrow} \in \{A, B\}$ or $F_0^{\downarrow} \in \{A, B\})$ \\
$= \{1\}$ otherwise

* $W_0^{(a,b)} = \emptyset$ if $F_0^{\uparrow} = 0$ \\
$= \{0\}$ otherwise

* $W_0^{(b,a)} = \emptyset$ if $F_0^{\uparrow} = 0$ \\
$= \{0\}$ otherwise

and the following recurrence formulas (for $1 \le i \le \ell - 1$):

* $W_i^{(b,b)} = (W_{i-1}^{(a,b)} \cup W_{i-1}^{(b,a)}) \times \{1\}$ if $F_{i-1}^{\uparrow} \sim F_{i-1}^{\downarrow}$ \\
$= W_{i-1}^{(b,b)} \times \{1\}$ otherwise

* $W_i^{(a,b)} = W_{i-1}^{(a,b)} \times \{0\}$ if $F_i^{\uparrow} \sim F_{i-1}^{\downarrow}$ \\
$= (W_{i-1}^{(b,a)} \cup W_{i-1}^{(b,b)}) \times \{0\}$ otherwise

* $W_i^{(b,a)} = W_{i-1}^{(b,a)} \times \{0\}$ if $F_i^{\uparrow} \sim F_{i-1}^{\downarrow}$ \\
$= (W_{i-1}^{(a,b)} \cup W_{i-1}^{(b,b)}) \times \{0\}$ otherwise.

We then set:

$$ 
\begin{align*}
W(\underline{F}) &= W_{\ell-1}^{(b,b)} \cup W_{\ell-1}^{(a,b)} & \text{if } F_{\ell-1}^{\uparrow} = AB \\
&= W_{\ell-1}^{(b,b)} \cup W_{\ell-1}^{(b,a)} & \text{if } F_{\ell-1}^{\uparrow} = AB \\
&= W_0^{(b,b)} \cup W_0^{(a,b)} \cup W_0^{(b,a)} & \text{otherwise.}
\end{align*}
$$

Notice that the last case can only show up when $\ell = 1$.

**Example 2.1.5.** — Let us compute the set of combinatorial weights associated to the fragments of Example 2.1.2. For the first one, following the definitions, we get:
$$ [i=0] : W_0^{(b,b)} = \{1\} ; W_0^{(a,b)} = \{0\} ; W_0^{(b,a)} = \emptyset $$

$$ [i=1] : W_1^{(b,b)} = (W_0^{(a,b)} \cup W_0^{(b,a)}) \times \{1\} = \{(0,1)\} $$

$$ W_1^{(a,b)} = (W_0^{(b,a)} \cup W_0^{(b,b)}) \times \{0\} = \{(1,0)\} $$

$$ W_1^{(b,a)} = (W_0^{(a,b)} \cup W_0^{(b,b)}) \times \{0\} = \{(0,0), (1,0)\} $$

$$ [i=2] : W_2^{(b,b)} = (W_1^{(a,b)} \cup W_1^{(b,a)}) \times \{1\} = \{(0,0,1), (1,0,1)\} $$

$$ W_2^{(a,b)} = (W_1^{(b,a)} \cup W_1^{(b,b)}) \times \{0\} = \{(0,0,0), (1,0,0), (0,1,0)\} $$

$$ W_2^{(b,a)} = W_0^{(b,a)} \times \{0\} = \{(0,0,0), (1,0,0)\} $$

and therefore:

$$ W\begin{pmatrix} 0 & A & B \\ B & A & AB \end{pmatrix} = W_2^{(b,b)} \cup W_2^{(a,b)} = \{(0,0,1), (1,0,1), (0,0,0), (1,0,0), (0,1,0)\}. $$

Similarly, we obtain:

$$ W\begin{pmatrix} A \\ 0 \end{pmatrix} = \{0\} ; W\begin{pmatrix} AB \\ 0 \end{pmatrix} = \{0,1\} ; W\begin{pmatrix} 0 & A \\ B & AB \end{pmatrix} = \{(0,1), (1,0)\}. $$

We now come to the definition of the set of combinatorial weights of a gene.

**Definition 2.1.6.** — We set:

$$ W(\mathcal{X}) = \prod_{\mathcal{F}} W(\mathcal{F}) $$

where the product runs over all fragments $\mathcal{F}$ of $\mathcal{X}$ (and the coordinates of the fragmentary combinatorial weights go at the corresponding positions).

**Example 2.1.7.** — After Example 2.1.5, the gene of Example 2.1.2 has $5 \times 1 \times 2 \times 2 = 20$ combinatorial weights, which are:

*(0, 0, 1, 0, 0, 0, 1), (0, 0, 1, 0, 0, 1, 0), (0, 0, 1, 0, 1, 0, 1), (0, 0, 1, 0, 1, 1, 0), (1, 0, 1, 0, 0, 0, 1), (1, 0, 1, 0, 0, 1, 0), (1, 0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 1, 0), (0, 0, 0, 0, 0, 0, 1), (0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 1, 0, 1), (0, 0, 0, 0, 1, 1, 0), (1, 0, 0, 0, 0, 0, 1), (1, 0, 0, 0, 0, 1, 0), (1, 0, 0, 0, 1, 0, 1), (1, 0, 0, 0, 1, 1, 0), (0, 1, 0, 0, 0, 0, 1), (0, 1, 0, 0, 0, 1, 0), (0, 1, 0, 0, 1, 0, 1), (0, 1, 0, 0, 1, 1, 0).*

**2.2. On the number of combinatorial weights.** — The viability of the gene and the non-emptiness of the set of combinatorial weights are closely related.

**Theorem 2.2.1.** — Let $\mathcal{X}$ be a nondegenerate gene. Then $W(\mathcal{X})$ is not empty if and only if $\mathcal{X}$ is viable.

*Proof.* — If $\mathcal{X}$ is not viable, the set $W(\mathcal{X})$ is empty by definition. It is then enough to prove that $W(\mathcal{X})$ is not empty as soon as $\mathcal{X}$ is viable, which amounts to proving that $W(\mathcal{F}) \neq \emptyset$ for any fragment $\mathcal{F}$. The latter assertion is easily checked by hand when $\mathcal{F}$ has length 1 by examining all cases. We now assume that $\mathcal{F}$ has length $\ell \ge 2$. An easy induction on $i$ shows that $W_i^{(b,b)}$ and $W_i^{(a,b)} \cup W_i^{(b,a)}$ are always not empty for $i \in \{0, \dots, \ell-1\}$. Since $W(\mathcal{F})$ contains $W_{\ell-1}^{(b,b)}$, it is also not empty. $\square$
Beyond the emptiness characterization of Theorem 2.2.1, one can count the number of combinatorial weights of $W(\mathcal{X})$ without having to write them down all explicitly. The cardinality of $W(\mathcal{X})$ is the product of the cardinality of $W(\underline{F})$ for $\underline{F}$ the fragments of $\mathcal{X}$. Moreover, it turns out that the cardinality of $W(\underline{F})$ are given by simple recursive formulas. Here is the key lemma allowing for deriving them.

**Lemma 2.2.2.** — Let $\underline{F}$ be a fragment of length $\ell$ and let $(W_i^{(\mathbf{b},\mathbf{b})})_{0\le i<\ell}$, $(W_i^{(\mathbf{a},\mathbf{b})})_{0\le i<\ell}$, $(W_i^{(\mathbf{b},\mathbf{a})})_{0\le i<\ell}$ be the sequences defined in Definition 2.1.4. Then, for all $i \in \{0, \dots, \ell-1\}$, we have:

$$ (i) \ W_i^{(\mathbf{a},\mathbf{b})} \cap W_i^{(\mathbf{b},\mathbf{b})} = \emptyset, $$

$$ (ii) \ W_i^{(\mathbf{b},\mathbf{a})} \cap W_i^{(\mathbf{b},\mathbf{b})} = \emptyset, $$

$$ (iii) \ W_i^{(\mathbf{a},\mathbf{b})} \subset W_i^{(\mathbf{b},\mathbf{a})} \text{ or } W_i^{(\mathbf{b},\mathbf{a})} \subset W_i^{(\mathbf{a},\mathbf{b})}. $$

*Proof.* — The two first assertions are obvious since the last coordinate of an element of $W_i^{(\mathbf{a},\mathbf{b})}$ (resp. $W_i^{(\mathbf{b},\mathbf{a})}$) is always 0 whereas the last coordinate of an element of $W_i^{(\mathbf{b},\mathbf{b})}$ is always 1.

We prove the assertion (iii) by induction on $i$. For $i=0$, it follows immediately from the definition. Let us now assume that (iii) holds for the index $i-1$. We distinguish between four cases.

If $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$ and $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$, then:

$$ W_i^{(\mathbf{a},\mathbf{b})} = W_{i-1}^{(\mathbf{a},\mathbf{b})} \times \{0\} \ ; \ W_i^{(\mathbf{b},\mathbf{a})} = W_{i-1}^{(\mathbf{b},\mathbf{a})} \times \{0\} $$

and the conclusion follows directly by induction.

If $F_i^{\downarrow} \not\sim F_{i-1}^{\downarrow}$ and $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$, then:

$$ W_i^{(\mathbf{b},\mathbf{a})} = W_{i-1}^{(\mathbf{b},\mathbf{a})} \times \{0\} \subset (W_{i-1}^{(\mathbf{b},\mathbf{a})} \cup W_{i-1}^{(\mathbf{b},\mathbf{b})}) \times \{0\} = W_i^{(\mathbf{a},\mathbf{b})}. $$

If $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$ and $F_i^{\downarrow} \not\sim F_{i-1}^{\downarrow}$, then:

$$ W_i^{(\mathbf{a},\mathbf{b})} = W_{i-1}^{(\mathbf{a},\mathbf{b})} \times \{0\} \subset (W_{i-1}^{(\mathbf{a},\mathbf{b})} \cup W_{i-1}^{(\mathbf{b},\mathbf{b})}) \times \{0\} = W_i^{(\mathbf{b},\mathbf{a})}. $$

If $F_i^{\downarrow} \not\sim F_{i-1}^{\downarrow}$ and $F_i^{\downarrow} \not\sim F_{i-1}^{\downarrow}$, then:

$$ W_i^{(\mathbf{a},\mathbf{b})} = (W_{i-1}^{(\mathbf{a},\mathbf{b})} \cup W_{i-1}^{(\mathbf{b},\mathbf{b})}) \times \{0\} \ ; \ W_i^{(\mathbf{b},\mathbf{a})} = (W_{i-1}^{(\mathbf{b},\mathbf{a})} \cup W_{i-1}^{(\mathbf{b},\mathbf{b})}) \times \{0\} $$

and the conclusion again follows by induction (the order is reversed). $\square$

For $0 \le i < \ell$ and $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$, we set $c_i^{\square} = \text{Card } W_i^{\square}$. Definition 2.1.4 and Lemma 2.2.2 together show that the $c_i^{\square}$'s are subject to the following recurrence relations:

* $c_i^{(\mathbf{b},\mathbf{b})} = \max(c_{i-1}^{(\mathbf{a},\mathbf{b})}, c_{i-1}^{(\mathbf{b},\mathbf{a})})$ if $F_{i-1}^{\downarrow} \sim F_{i-1}^{\downarrow}$
  otherwise

* $c_i^{(\mathbf{a},\mathbf{b})} = c_{i-1}^{(\mathbf{a},\mathbf{b})}$ if $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$
  otherwise

* $c_i^{(\mathbf{b},\mathbf{a})} = c_{i-1}^{(\mathbf{b},\mathbf{a})}$ if $F_i^{\downarrow} \sim F_{i-1}^{\downarrow}$
  otherwise

and that the cardinality we are looking for is finally given by:

**Corollary 2.2.3.** — The cardinality of the set of combinatorial weights associated to a fragment $\underline{F}$ is given by:
$$
\begin{align*}
\text{Card } \mathcal{W}(\underline{F}) &= c_{\ell-1}^{(\mathbf{b},\mathbf{b})} + c_{\ell-1}^{(\mathbf{a},\mathbf{b})} & \text{if } F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B}, \\
&= c_{\ell-1}^{(\mathbf{b},\mathbf{b})} + c_{\ell-1}^{(\mathbf{b},\mathbf{a})} & \text{if } F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B}.
\end{align*}
$$

Beyond the fact that these recursive formulas are well suited for a direct and simple computation of Card W(F), they have interesting corollaries. In order to state them, let us call (Fibᵢ)ᵢ≥₀ the Fibonacci sequence defined by Fib₀ = 0, Fib₁ = 1 and Fibᵢ = Fibᵢ₋₁ + Fibᵢ₋₂ for i ≥ 2.

**Theorem 2.2.4.** — Let $\underline{F}$ be a fragment of length $\ell \ge 2$. Then $\text{Card } \mathcal{W}(\underline{F}) \le \text{Fib}_{\ell+2}$ and equality occurs if and only if $\underline{F}$ is the following fragment:

if $\ell$ is even:

0 A B ... A B AB
B A B ... A B A

if $\ell$ is odd:

0 A B ... A B A B
B A B ... A B A AB

or the fragment obtained from the above one by interverting the letters A and B.

*Proof.* — We keep the notations introduced above the statement of the theorem. We are going to prove by induction on *i* that:

$$
c_i^{(\mathbf{b},\mathbf{b})} \le \mathrm{Fib}_{i+1}, \quad c_i^{(\mathbf{a},\mathbf{b})} \le \mathrm{Fib}_{i+2} \quad \text{and} \quad c_i^{(\mathbf{b},\mathbf{a})} \le \mathrm{Fib}_{i+2}.
$$

The statement is clearly true for $i=0$. For $i>0$, we have:

$$
\begin{align*}
c_i^{(\mathbf{b},\mathbf{b})} &= \max(c_{i-1}^{(\mathbf{a},\mathbf{b})}, c_{i-1}^{(\mathbf{b},\mathbf{a})}) \le \mathrm{Fib}_{i+1} & \text{if } F_{i-1}^{\dagger} \sim F_{i-1}^{\dagger} \\
&= c_{i-1}^{(\mathbf{b},\mathbf{b})} \le \mathrm{Fib}_i \le \mathrm{Fib}_{i+1} & \text{otherwise}
\end{align*}
$$

$$
\begin{align*}
c_i^{(\mathbf{a},\mathbf{b})} &= c_{i-1}^{(\mathbf{a},\mathbf{b})} \le \mathrm{Fib}_{i+1} \le \mathrm{Fib}_{i+2} & \text{if } F_i^\dagger \sim F_{i-1}^\dagger \\
&= c_{i-1}^{(\mathbf{b},\mathbf{a})} + c_{i-1}^{(\mathbf{b},\mathbf{b})} \le \mathrm{Fib}_{i+1} + \mathrm{Fib}_i = \mathrm{Fib}_{i+2} & \text{otherwise}
\end{align*}
$$

$$
\begin{align*}
c_i^{(\mathbf{b},\mathbf{a})} &= c_{i-1}^{(\mathbf{b},\mathbf{a})} \le \mathrm{Fib}_{i+1} \le \mathrm{Fib}_{i+2} & \text{if } F_i^\dagger \sim F_{i-1}^\dagger \\
&= c_{i-1}^{(\mathbf{a},\mathbf{b})} + c_{i-1}^{(\mathbf{b},\mathbf{b})} \le \mathrm{Fib}_{i+1} + \mathrm{Fib}_i = \mathrm{Fib}_{i+2} & \text{otherwise.}
\end{align*}
$$

We finally conclude that:

$$
\begin{align*}
\text{Card } \mathcal{W}(\underline{F}) &= c_{\ell-1}^{(\mathbf{b},\mathbf{b})} + c_{\ell-1}^{(\mathbf{a},\mathbf{b})} \le \text{Fib}_{\ell} + \text{Fib}_{\ell+1} = \text{Fib}_{\ell+2} && \text{if } F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B} \\
&= c_{\ell-1}^{(\mathbf{b},\mathbf{b})} + c_{\ell-1}^{(\mathbf{b},\mathbf{a})} \le \text{Fib}_{\ell} + \text{Fib}_{\ell+1} = \text{Fib}_{\ell+2} && \text{if } F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B}.
\end{align*}
$$

The first assertion of the theorem is then proved.

Let us now study the case of equality. It holds if and only all inequalities encountered along the way are equalities. Let us assume first that $F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B}$. We then derive that $c_{\ell-1}^{(\mathbf{b},\mathbf{b})}$ and $c_{\ell-1}^{(\mathbf{a},\mathbf{b})}$ must be equal to $\text{Fib}_{\ell}$ and $\text{Fib}_{\ell+1}$ respectively. Noticing that $\text{Fib}_{i} < \text{Fib}_{i+1}$ as soon as $i \ge 2$, these equalities imply by descending induction that $c_{i}^{(\mathbf{b},\mathbf{b})} = \text{Fib}_{i}$ for all $i \in \{0, \dots, \ell-1\}$ and that:

$$
- \text{ if } \ell-i \text{ is odd, then } c_i^{(\mathbf{a},\mathbf{b})} = \text{Fib}_{i+2} \text{ and } F_i^\dagger \not\sim F_{i-1}^\dagger,
$$

$$
- \text{ if } \ell - i \text{ is even, then } c_i^{(\mathbf{b},\mathbf{a})} = \text{Fib}_{i+2} \text{ and } F_i^\dagger \not\sim F_{i-1}^\dagger.
$$

Similarly, the equality $c_i^{(\mathbf{b},\mathbf{b})} = \text{Fib}_i$ is only possible if $F_{i-1}^{\dagger} \sim F_{i-1}^{\dagger}$ for all $i \ge 2$. The two possible shapes of $\underline{F}$ given in the statement of the theorem follow from these observations.

Finally, the case where $F_{\ell-1}^{\dagger} = \mathbf{A}\mathbf{B}$ is treated similarly. $\square$

<figure><img src="image_5.png" /></figure>
In Theorem 2.2.4, we have intentionally discarded the fragments with $\mathbf{0}$ of length 1. It is actually not difficult to handle these fragments by hand. Precisely, there are exactly six such segments, which are:

A ; O ; B ; O ; AB ; O
O A O B O AB

Their number of fragmentary combinatorial weights are 1, 1, 1, 1, 2 and 2 respectively. The upper bound of Theorem 2.2.4 is then correct for the four first fragments (with equality) but it is not for the two last ones.

**Remark 2.2.5.** — Numerical experimentations show that almost—but not all—integers between 1 and $\text{Fib}_{\ell+2}$ can show up as the number of fragmentary combinatorial weights of a fragment of length $\ell$. Exceptions are large integers which are rather close to the upper bound $\text{Fib}_{\ell+2}$; for example, when $\ell = 10$ (so that $\text{Fib}_{\ell+2} = 144$), they are 113, 114, 118, 120, 126, 127, 130 and all the integers in the interval $[132, 142]$. We notice that $\text{Fib}_{\ell+2} - 1$ always appear for the following fragment:

if $\ell$ is even:

0 A B ... A B A
B A B ... A B AB

if $\ell$ is odd:

0 A B ... A B A AB
B A B ... A B A B

**2.3. From combinatorial weights to Serre weights.** — In this subsection, we explain how combinatorial weights defined in §2.1 are related to Serre weights. We give a precise statement of Theorem 3 of the introduction which provides an explicit bijection between the set of common weights of $\mathfrak{t}$ and $\bar{\mathfrak{p}}$ and the set of combinatorial weights of their gene.

We consider an absolutely irreducible representation

$$ \bar{\rho} = \text{Ind}_{G_F'}^{G_F} (\omega_{2f}^h \otimes \text{nr}'(\theta)) $$

together with a tamely ramified Galois type $t = \omega_f^\gamma \oplus \omega_f^{\gamma'}$. We let $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ denote the gene associated to $(h, \gamma, \gamma')$. As in §1.2, we define the integers $c_0, \dots, c_{f-1}$ in $\{0, \dots, p-1\}$ by the relation $\gamma' - \gamma = \sum_{i=0}^{f-1} c_i p^i \pmod{q-1}$. As in §1.3, we introduce the $(2f)$-periodic sequence $(v_i)_{i \in \mathbb{Z}}$ defined by the fact that $0 \le v_i \le p-1$ for all $i$ and the congruence (12), namely:

$$ h - (q+1)\gamma' \equiv p^{2f-1}v_0 + p^{2f-2}v_1 + \dots + pv_{2f-2} + v_{2f-1} \pmod{q^2-1}. $$

We define an equivalence relation $\sim$ on $\{\text{A}, \text{B}, \text{AB}, \mathbf{0}\}$ by $\text{A} \sim \text{AB}$ and $\text{B} \sim \mathbf{0}$. For $i$ in $\mathbb{Z}$, we set $\delta_i = 1$ if $X_i \sim X_{i+f}$ and $\delta_i = 0$ otherwise. This defines a $f$-periodic sequence $(\delta_i)_{i \in \mathbb{Z}}$ with values in $\{0, 1\}$.

After these preparations, we are ready to explain the recipe to construct a Serre weight $S(\underline{w})$ from the datum of a combinatorial weight $\underline{w} = (w_i)_{i \in \mathbb{Z}}$ in $W(\mathcal{X})$. We continue to assume that $\mathcal{X}$ is nondegenerate. For this, we need to describe its parameters $s$ and $\underline{r} = (r_0, \dots, r_{f-1})$. For $i$ in $\{0, \dots, f-1\}$, we let $r_{f-i-1}$ be the integer defined in the table of Figure 1. Defining $s$ is a bit more painful. Eq. (10) tells us that we have to choose $s$
<table><caption>FIGURE 1. Table giving the values of $r_{f-1-i}$</caption><thead><tr><th>r<sub>f-1-i</sub></th><th>w<sub>i-1</sub> = δ<sub>i-1</sub></th><th>w<sub>i-1</sub> ≠ δ<sub>i-1</sub></th></tr></thead><tbody><tr><td>X<sub>i</sub> = 0</td><td>v<sub>i</sub> - 1 - w<sub>i</sub></td><td>p - 1 - v<sub>i</sub> + w<sub>i</sub></td></tr><tr><td>X<sub>i+f</sub> = 0</td><td>v<sub>i+f</sub> - 1 - w<sub>i</sub></td><td>p - 1 - v<sub>i+f</sub> + w<sub>i</sub></td></tr><tr><td>otherwise</td><td>w<sub>i</sub> · (p - 1)</td><td>p - 2 + w<sub>i</sub></td></tr></tbody></table>

with the property that:

$$2s \equiv \gamma + \gamma' - \sum_{i=0}^{f-1} r_i p^i \pmod{q-1}.$$

However, this leaves us with two possibilities between them we have to decide. In order to do so, we distinguish between two cases:

(1) if there exists an integer $i_0$ such that $c_{i_0} \neq \frac{p-1}{2}$, we set $\varepsilon'_{i_0} = 0$ if $r_{i_0} \in \{c_{i_0}, c_{i_0} - 1\}$ and $\varepsilon'_{i_0} = 1$ otherwise;

(2) if $c_i = \frac{p-1}{2}$ for all $i$, we consider an integer $i_0$ such that $X_{f-1-i_0} = 0$ and set $\varepsilon'_{i_0} = 0$ if $w_{f-2-i_0} = \delta_{f-2-i_0}$ and $\varepsilon'_{i_0} = 1$ otherwise.

Then, for this particular choice of $i_0$, we define:

$$s = \gamma' + \frac{1}{2} \left( \varepsilon'_{i_0} (q-1) + \sum_{i=0}^{f-1} \lambda_{i+i_0} (c_i - r_i) p^i \right) \in \mathbb{Z}/(q-1)\mathbb{Z}$$

where, by definition, $\lambda_j = q$ if $j < f-1$ and $\lambda_j = 1$ otherwise.

**Theorem 2.3.1.** — If $\mathbb{X}$ is nondegenerate, the construction $S$ induces a bijection $W(\mathbb{X}) \xrightarrow{\sim} \mathcal{D}(t, \bar{p})$.

The proof of Theorem 2.3.1 is entirely of combinatorial nature; however, it is not easy and requires the introduction of several new combinatorial objects. In order to avoid interrupting the ongoing discussion, we prefer deriving just consequences of 2.3.1 and postponing its proof until §4.

**Example 2.3.2.** — We take $p = 5$, $f = 7$, and:

$$h = (3 + 4p + 3p^3 + 4p^4 + 4p^5 + 3p^6)(q+1) + (1 + 3p + p^2 + 4p^3 + 4p^4 + 4p^5 + p^6)$$

$$\gamma = 3 + 4p + p^2 + p^3 + 4p^4 + 3p^5 + 3p^6$$

$$\gamma' = 3 + p + 3p^3 + 3p^4 + 4p^5 + 4p^6.$$

A straightforward computation shows that the gene associated to these data is the one considered in Example 2.1.2 (see also Example B.1.6). Its combinatorial weights are then those enumerated at the end of Example 2.1.7. Besides, the $\delta_i$'s are given $(\delta_0, \dots, \delta_7) = (1, 1, 0, 0, 0, 1, 1)$. Moreover, we find $(v_0, \dots, v_{13}) = (4, 0, 1, 0, 0, 3, 0, 1, 0, 0, 4, 2, 1, 0)$.

Applying the recipe described above, we find that the Serre weights associated to the combinatorial weights listed in Example 2.1.7 are respectively:

$$(\tau_0 \circ \det^{77758}) \otimes \mathrm{Sym}^{[4,2,1,0,4,3,3]} k_E^2 \ ; \ (\tau_0 \circ \det^{140262}) \otimes \mathrm{Sym}^{[0,1,1,0,4,3,0]} k_E^2$$

$$(\tau_0 \circ \det^{77773}) \otimes \mathrm{Sym}^{[4,1,0,0,4,3,3]} k_E^2 \ ; \ (\tau_0 \circ \det^{140272}) \otimes \mathrm{Sym}^{[0,2,0,0,4,3,0]} k_E^2$$
$$
\begin{align*}
(\tau_0 \circ \det^{90258}) \otimes \mathrm{Sym}^{[4,2,1,0,4,0,2]} k_E^2 &; \quad (\tau_0 \circ \det^{137137}) \otimes \mathrm{Sym}^{[0,1,1,0,4,0,1]} k_E^2 \\
(\tau_0 \circ \det^{90273}) \otimes \mathrm{Sym}^{[4,1,0,0,4,0,2]} k_E^2 &; \quad (\tau_0 \circ \det^{137147}) \otimes \mathrm{Sym}^{[0,2,0,0,4,0,1]} k_E^2 \\
(\tau_0 \circ \det^{77883}) \otimes \mathrm{Sym}^{[4,2,1,3,3,3,3]} k_E^2 &; \quad (\tau_0 \circ \det^{140387}) \otimes \mathrm{Sym}^{[0,1,1,3,3,3,0]} k_E^2 \\
(\tau_0 \circ \det^{77898}) \otimes \mathrm{Sym}^{[4,1,0,3,3,3,3]} k_E^2 &; \quad (\tau_0 \circ \det^{140397}) \otimes \mathrm{Sym}^{[0,2,0,3,3,3,0]} k_E^2 \\
(\tau_0 \circ \det^{90383}) \otimes \mathrm{Sym}^{[4,2,1,3,3,0,2]} k_E^2 &; \quad (\tau_0 \circ \det^{137262}) \otimes \mathrm{Sym}^{[0,1,1,3,3,0,1]} k_E^2 \\
(\tau_0 \circ \det^{90398}) \otimes \mathrm{Sym}^{[4,1,0,3,3,0,2]} k_E^2 &; \quad (\tau_0 \circ \det^{137272}) \otimes \mathrm{Sym}^{[0,2,0,3,3,0,1]} k_E^2 \\
(\tau_0 \circ \det^{77258}) \otimes \mathrm{Sym}^{[4,2,1,3,0,4,3]} k_E^2 &; \quad (\tau_0 \circ \det^{139762}) \otimes \mathrm{Sym}^{[0,1,1,3,0,4,0]} k_E^2 \\
(\tau_0 \circ \det^{77273}) \otimes \mathrm{Sym}^{[4,1,0,3,0,4,3]} k_E^2 &; \quad (\tau_0 \circ \det^{139772}) \otimes \mathrm{Sym}^{[0,2,0,3,0,4,0]} k_E^2
\end{align*}
$$

where $\mathrm{Sym}^{[r_0, r_1, \dots, r_6]} k_E^2$ is a shortcut for $\bigotimes_{i=0}^6 (\mathrm{Sym}^{r_i} k_E^2)^{r_i}$.

Note that, in this particular example, $\mathcal{D}(\bar{\rho})$ has cardinality 96 and $\mathcal{D}(t)$ has cardinality 60. If one wants to calculate $\mathcal{D}(t, \bar{\rho})$, it is then much faster to use the previous techniques than to compute the intersection naively. We will make the latest assertion more rigourous in §B.

### 3. Applications to deformations spaces

The aim of this section is to relate Theorem 2.3.1 to the results of [CDM2], with the objective to provide new evidences supporting the conjectural description of the deformations rings $R^\psi(t, \bar{\rho})$ we made in [CDM2, §5].

Indeed, these conjectures suggest that the deformation ring $R^\psi(t, \bar{\rho})$ is determined by the gene associated to $(t, \bar{\rho})$ and, more precisely, that it can be obtained as a completed tensor product of some rings associated to each fragment of the gene. A way to support this conjectural fragmentation is to consider its implications in terms of special fibres. Following the Breuil–Mézard conjecture, proved in [CEGS] in the considered case, the number of irreducible components of the special fiber of a deformation ring $R^\psi(t, \bar{\rho})$ is closely related to the number of common weights. If our conjectures are true, the number of common weights should reflect the fragmentation phenomena. Theorem 2.3.1 is a first enlighting result in this perspective as it shows that $\mathcal{D}(t, \bar{\rho})$ splits canonically as a direct product indexed by the fragments of the associated gene.

In this section, we do a thorough study of these phenomena. Precisely, our intention is to go beyond the fragmentation of the gene and to relate (the cardinality of) $\mathcal{D}(t, \bar{\rho})$ to a more intrinsic object attached to the situation, namely the Kisin variety. We will notably show that the Kisin variety equipped with some extra structures (which are its canonical embedding into $(\mathbb{P}^1)^f$ and its so-called shape stratification) entirely determines Card $\mathcal{D}(t, \bar{\rho})$ and that the latter appears as a product as soon as the Kisin variety itself splits a direct product (Theorem 3.2.1). This will allow us to formulate refinements of the conjectures of [CDM2] (Conjecture 3.1.2) and give convincing evidences towards them.

**3.1. From genes to Kisin varieties.** — Given $\psi$, $t$ and $\bar{\rho}$ as in the previous sections, we recall from §1.1 that Kisin constructed in [Ki3] a ring $R^\psi(t, \bar{\rho})$ parametrizing the potentially Barsotti–Tate deformations of $\bar{\rho}$ with Hodge–Tate weights $\{0, 1\}$ at all embeddings, determinant $\psi$ and inertial type $t$. The key ingredient in Kisin’s argument is the construction of an auxiliary scheme $\mathcal{GR}^\psi(t, \bar{\rho})$ parametrizing the Breuil–Kisin modules of
type t inside the étale $\varphi$-module associated to $\bar{\rho}$ by Fontaine and Wintenberger's theory$^{(2)}$. This scheme comes equipped with a canonical morphism $\mathcal{GR}^{\psi}(t, \bar{\rho}) \to \text{Spec } R^{\psi}(\bar{\rho})$ whose schematic image is, by definition, the spectrum of the deformation ring $R^{\psi}(t, \bar{\rho})$ we want to construct. One then gets for free a morphism:

$$ \mathcal{GR}^{\psi}(t, \bar{\rho}) \to \text{Spec } R^{\psi}(t, \bar{\rho}) $$

which is sometimes considered as a partial resolution of singularities. Indeed, Kisin notably proves that the above morphism induces an isomorphism in generic fibre. The special fibre of $\mathcal{GR}^{\psi}(t, \bar{\rho})$, namely

$$ \overline{\mathcal{GR}}^{\psi}(t, \bar{\rho}) = \text{Spec } k_E \times_{\text{Spec } R^{\psi}(t, \bar{\rho})} \mathcal{GR}^{\psi}(t, \bar{\rho}). $$

is the so-called *Kisin variety*; it is not smooth in general but its structure is much easier to describe than that of the special fibre of the deformation ring $R^{\psi}(t, \bar{\rho})$ itself.

**3.1.1. Review of previous results.** — The first important result of [CDM2] is Theorem 2.2.1 which gives an entirely explicit description of the Kisin variety $\overline{\mathcal{GR}}^{\psi}(t, \bar{\rho})$ in terms of the gene $X$ associated to $(t, \bar{\rho})$. Let us recall briefly what it is when $X = (X_i)_{i \in \mathbb{Z}}$ is nondegenerate (which is the only case we will work with later on).

By definition, we say that the letter **A** (resp. **B**) is *dominant* at position $i$ if it appears more often than **B** (resp. **A**) in $\{X_i, X_{i+f}\}$ or, in case of equality, if **A** (resp. **B**) is dominant at position $i+1$. The fact that $X$ is nondegenerate ensures that the definition is not circular and, consequently, that each position has a well-defined dominant letter; we will denote it by $\text{Dom}_i(X)$ in what follows. For $i \in \mathbb{Z}$, we set $\lambda_i = 1$ if $X_i = \text{Dom}_i(X)$ and $\lambda_i = 0$ otherwise. Then, the variety $\overline{\mathcal{GR}}^{\psi}(t, \bar{\rho})$ is isomorphic to the closed subscheme of $(\mathbb{P}^1)^f$, with projective coordinates $[x_i : x_{i+f}]$ on the $i$-th factor ($0 \le i < f$), defined by the following equations:

* for $0 \le i < 2f$, if $X_i = 0$, then $x_i = 0$;

* for $0 \le i < f$, if $\text{Dom}_i(X) = \text{Dom}_{i+1}(X)$, then $\lambda_i x_i x_{i+1+f} = \lambda_{i+f} x_{i+f} x_{i+1}$.

Besides, the Kisin variety is equipped with a so-called *shape stratification* which can be read off on the gene too (see [CDM2, Proposition 5.2.5]). This stratification is materialized by the datum of a shape function in the sense of the following definition.

**Definition 3.1.1.** — Let $\mathcal{V}$ be a subvariety of $(\mathbb{P}^1)^f$. A *shape function* of $\mathcal{V}$ is an upper semi-continuous function $g : \mathcal{V}(\overline{\mathbb{F}}_p) \to \{\text{I, II}\}^f$ where I and II are two new symbols subject to the inequality $\text{I} < \text{II}$.

We say that $\mathcal{V}$ is *shape-stratified* if it is equipped with a shape function.

In what follows, we use the notation $\overline{\mathcal{GR}}^{\mathcal{S}}(X)$ to denote the Kisin variety associated to $X$, viewed as a closed subscheme of $(\mathbb{P}^1)^f$ and equipped with its shape function. In particular, equalities between various $\overline{\mathcal{GR}}^{\mathcal{S}}(X)$ will always mean equalities inside $(\mathbb{P}^1)^f$ and equalities of the shape functions.

For a fixed gene $X$, let $S$ be the set of indices $i$ in $\{0, \dots, f-1\}$ for which the $i$-th projection map $\text{pr}_i : (\mathbb{P}^1)^f \to \mathbb{P}^1$ is constant (necessarily equal to $[0:1]$ or $[1:0]$) on $\overline{\mathcal{GR}}^{\mathcal{S}}(X)$. Since $X$ is nondegenerate, it is clear that $S$ is nonempty. Without loss of generality, one

<footnote>$^{(2)}$We refer to [CDM2, §2] for a more detailed exposition of Kisin's construction in the setting of this article.</footnote>
may further assume that $0 \in S$. Write $S = \{i_0, \dots, i_{r-1}\}$ with $0 = i_0 < i_1 < \dots < i_{r-1}$ and set $i_r = f$. By [CDM2, §5.2.3], $\overline{GR^s}(\mathbb{X})$ splits as a direct product:

$$ (13) \qquad \overline{GR^s}(\mathbb{X}) = \mathcal{V}_0^s \times \mathcal{V}_1^s \times \dots \times \mathcal{V}_{r-1}^s $$

where $\mathcal{V}_j^s$ is a shape-stratified closed subscheme of $(\mathbb{P}^1)^{i_{j+1}-i_j}$ corresponding to the portion of the gene located between the columns $i_j$ (included) and $i_{j+1}$ (excluded). We insist on the fact that (13) respects the stratification and the embedding into $(\mathbb{P}^1)^f$.

After this result, we conjectured (under mild assumptions on the inertial type) that the generic fibre $D^\psi(t, \bar{\rho})$ (viewed as a rigid space) of $R^\psi(t, \bar{\rho})$ splits as a direct product

$$ D^\psi(t, \bar{\rho}) = D(\mathcal{V}_1^s) \times \dots \times D(\mathcal{V}_{r-1}^s) $$

where $D(\mathcal{V}_j^s)$ is a rigid space which depends only on $\mathcal{V}_j^s$ (see [CDM2, Conjecture 5.2.7]) and we gave a geometrical construction (in terms of blow-ups and formal completions) of a candidate for $D(\mathcal{V}_j^s)$. Unfortunately, regarding the deformation ring $R^\psi(t, \bar{\rho})$ itself, we cannot expect it to be simply the ring of power-bounded functions on $D^\psi(t, \bar{\rho})$ in general. Indeed, in [CDM2, §5.3.2], we exhibited an example where, conjecturally:

$$ D^\psi(t, \bar{\rho}) \simeq \text{Spm} \left( \frac{\mathcal{O}_E[[T_1, T_2, U, V]]}{UV+p^2} [1/p] \right) $$

but where the set of Serre weights $\mathcal{D}(t, \bar{\rho})$ has cardinality 3. By the Breuil–Mézard conjecture, we cannot then have $R^\psi(t, \bar{\rho}) = \frac{\mathcal{O}_E[[T_1, T_2, U, V]]}{UV+p^2}$ in this case.

Nevertheless, we propose the following weaker conjecture which looks plausible.

**Conjecture 3.1.2.** —

(1) We have:

$$ R^\psi(t, \bar{\rho}) \simeq R(\mathcal{V}_0^s) \hat{\otimes}_{\mathcal{O}_E} R(\mathcal{V}_1^s) \hat{\otimes}_{\mathcal{O}_E} \dots \hat{\otimes}_{\mathcal{O}_E} R(\mathcal{V}_{r-1}^s) $$

where $R(\mathcal{V}_j^s)$ is a local noetherian complete $\mathcal{O}_E$-algebra depending only on $\mathcal{V}_j^s$.

(2) The deformation ring $R^\psi(t, \bar{\rho})$ is the ring of power-bounded functions on $D^\psi(t, \bar{\rho})$ if there is no index $i$ with $X_i = X_{i+f} = \text{Dom}_{i+1}(\mathbb{X})$.

In what follows, we establish several results relating $\mathcal{D}(t, \bar{\rho})$ and $\overline{GR^s}(\mathbb{X})$ which, combined with the Breuil–Mézard conjecture, will eventually give some evidences towards the above conjecture (see Theorems 3.2.1, 3.2.6 and 3.3.1).

**3.1.2. Fragmentation.** — In order to define the factor varieties $\mathcal{V}_j^s$, we have divided the gene $\mathbb{X}$ into parts. Of course, this division is related to the fragmentation introduced in §2.1 but one needs to be careful that they are not exactly the same. In order to clarify the relationships between these two splittings, we remember that, by definition, $[x_i : x_{i+f}]$ is constantly equal to $[0 : 1]$ on the Kisin variety as soon as $X_i = 0$. Hence each fragment in the sense of Definition 2.1.3 corresponds to a slice of indices $j$ but, in full generality, this slice can have cardinality larger than 1.

In order to study in more details this phenomenon, it is convenient to associate a shape-stratified Kisin variety $\overline{GR^s}(\underline{F}) \subset (\mathbb{P}^1)^\ell$ to any fragment $\underline{F}$ of length $\ell$. This can be done simply by copying the rules we detailed previously in the case of genes. Concretely, if $[x_i : y_i]$ are the coordinates on the $i$-th factor, $\overline{GR^s}(\underline{F})$ is defined by the equations:

* $x_0 = 0$ if $F_0^\dagger = 0$ (resp. $y_0 = 0$ if $F_0^\dagger = 0$),

* for $0 \le i < \ell - 1$, if $\text{Dom}_i(\underline{F}) = \text{Dom}_{i+1}(\underline{F})$, then $\lambda_i x_i y_{i+1} = \mu_i y_i x_{i+1}$.

where $\lambda_i$ (resp. $\mu_i$) is 1 if $F_i^\dagger = \text{Dom}_i(\underline{F})$ (resp. $F_i^\dagger = \text{Dom}_i(\underline{F})$) and 0 otherwise.
The Kisin variety of a gene is obviously equal to the product of the Kisin varieties of its fragments. It may happen that the Kisin variety of a given fragment splits further as a product of smaller Kisin varieties. For instance, if $\underline{F}$ is a fragment of the form:

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

where the letter A is dominant in all positions between 0 and $n-1$, the rules giving the equations of the Kisin variety imply that $pr_0, \dots, pr_{n-1} : \overline{\mathcal{GR}}^s(\underline{F}) \to \mathbb{P}^1$ are all constant equal to $[0:1]$. The next lemma shows that all the examples are of this type.

**Lemma 3.1.3.** — Let $\underline{F}$ be a fragment of length $\ell > 1$ such that $F_0^\dagger = \mathbf{0}$ and $F_0^\dagger = A$. Let $n$ be the largest integer for which $F_i^\dagger = A$ for $i < n-1$ and A is dominant in all positions $i < n$. Then, the map $pr_i : \overline{\mathcal{GR}}^s(\underline{F}) \to \mathbb{P}^1$ is constant if $i < n$ and surjective if $i \ge n$.

*Proof.* — We have already seen that $pr_i$ is constant equal to $[0:1]$ for $i < n$. Let us now prove that $pr_n$ is surjective. For this, the key is to observe that if we are given $[x_i : y_i] \in \mathbb{P}^1$, there always exists $[x_{i+1} : y_{i+1}] \in \mathbb{P}^1$ satisfying the equation $\lambda_i x_i y_{i+1} = \mu_i y_i x_{i+1}$.

Now we argue as follows. If B is dominant at position $n$, then there is no equation relating $[x_{n-1} : y_{n-1}]$ and $[x_n : y_n]$. We can then choose $[x_n : y_n]$ arbitrarily and complete the family into an actual point of the Kisin variety by using repeatedly the observation we made above. On the contrary, if A is dominant at position $n$, it follows from the definition of $n$ that $F_{n-1}^\dagger = B$ and then that $\mu_{n-1} = 0$. The equation $\lambda_{n-1} x_{n-1} y_n = \mu_{n-1} y_{n-1} x_n$ is then trivially satisfied since $x_{n-1} = 0$ as well. Therefore, as in the first case, we can choose $[x_n : y_n]$ arbitrarily and conclude as before.

The surjectivity of $pr_i$ for $i > n$ follows by induction on $i$ using a similar argument. $\square$

Lemma 3.1.3 tells us that we have a decomposition of the form:

$$ \overline{\mathcal{GR}}^s(\underline{F}) = \{[0:1]\}^n \times \mathcal{V}^s $$

where $\mathcal{V}^s$ is some shape-stratified subvariety of $(\mathbb{P}^1)^{\ell-n}$ and the shape of the prefactor $\{[0:1]\}^n$ is (I, ..., I). It is actually possible to go further and make the factor $\mathcal{V}^s$ explicit. Let us first consider the case where $F_{n-1}^\dagger = A$ which is the easiest one. Under this assumption, one can check that $\mathcal{V}^s = \overline{\mathcal{GR}}^s(\underline{F}')$ where $\underline{F}'$ is the fragment:

$$ \begin{array}{lclcl} \mathbf{0} & F_n^\dagger & F_{n+1}^\dagger & \cdots & F_{\ell-1}^\dagger \\ \mathbf{A} & F_n^\dagger & F_{n+1}^\dagger & \cdots & F_{\ell-1}^\dagger \end{array} $$

When $F_{n-1}^\dagger = B$, it is still true that $\mathcal{V}^s = \overline{\mathcal{GR}}^s(\underline{F}')$ as subvarieties of $(\mathbb{P}^1)^{\ell-n}$ but the shape stratification does not agree. Actually, in this situation, $\mathcal{V}^s$ does not appear as the Kisin variety of a smaller fragment. However we can write:

$$ \overline{\mathcal{GR}}^s(\underline{F}) = \{[0:1]\}^{n-1} \times \overline{\mathcal{GR}}^s(\underline{F''}) $$

where $\underline{F}''$ is the following fragment:

$$ \begin{array}{lclcl} \mathbf{0} & \mathbf{A} & F_n^\dagger & F_{n+1}^\dagger & \cdots & F_{\ell-1}^\dagger \\ \mathbf{A} & \mathbf{B} & F_n^\dagger & F_{n+1}^\dagger & \cdots & F_{\ell-1}^\dagger \end{array} $$
(Notice that, in this case, we necessarily have $F_{n-1}^{\dagger} = A$ because otherwise B would be dominant in position $n-1$, which contradicts the definition of $n$.)

**Remark 3.1.4.** — In what precedes, we have assumed that $F_0^\dagger = 0$ and $F_0^\dagger = A$. Of course, there are similar statements where A is replaced by B and where the roles of $F_0^\dagger$ and $F_0^\dagger$ are exchanged. All fragments of length at least 2 are covered by these variants.

**3.1.3. Reduced fragments.** — After [CDM2, Theorem 2.2.1], the Kisin variety of a pair $(t, \bar{\rho})$ is entirely determined by the gene. Conversely, one may wonder if the Kisin variety determines the gene. Lemma 3.1.3 shows that this too naive question has a negative answer; indeed, if $n$ is the integer defined in the statement of this lemma, the values of $F_i^\dagger$ for $1 \le i < n$ do not have any influence on $\overline{GR^s}(F)$. Besides, one easily checks that if $F$ is any segment and $F'$ is the segment deduced from $F$ by flipping the letters A and B, we have $\overline{GR^s}(F) = \overline{GR^s}(F')$. Nonetheless, beyond these two “trivial” obstructions, one can prove injectivity results about $\overline{GR^s}$.

**Definition 3.1.5.** — Let $F$ be a fragment of length $\ell$. We say that $F$ is top-reduced if $F_0^\dagger = 0$, $F_0^\dagger \in \{A, AB\}$ and:

(i) either $\ell = 1$,

(ii) or $\ell > 1$ and B is dominant at position 1,

(iii) or $\ell > 2$, $F_1^\dagger = A$, $F_1^\dagger = B$ and A is dominant at position 2.

We say that $F$ is bottom-reduced if the fragment deduced from $F$ by swapping its top row and its bottom row is top-reduced.

We say that $F$ is reduced if it is either top-reduced or bottom-reduced.

If $F$ is reduced, we set $\widetilde{GR}^s(F) = \overline{GR}^s(F)$ in cases (i) and (ii) whereas, in case (iii), we define $\widetilde{GR}^s(F)$ by the equality $\overline{GR}^s(F) = \{[0:1]\} \times \widetilde{GR}^s(F)$.

It is easy to check that any fragment $F$ can be related to a reduced fragment $F^{\text{red}}$ by flipping letters and/or performing the transformation presented at the end of §3.1.2. We then have the relation:

$$ \overline{GR}^s(F) = \{[0:1]\}^n \times \widetilde{GR}^s(F^{\text{red}}) $$

where $n$ is the integer defined in Lemma 3.1.3.

**Proposition 3.1.6.** — The function $\widetilde{GR}^s$ is injective on the set of reduced fragments.

*Proof.* — Let $F$ be a reduced fragment of length $\ell > 1$. It is easy to see on the Kisin variety $\overline{GR}^s(F)$ if $F$ is top-reduced or bottom-reduced since the function $\text{pr}_1 : \overline{GR}^s(F) \to \mathbb{P}^1$ is constant equal to $[0:1]$ in the first case and constant equal to $[1:0]$ in the second case.

We then assume that $F_0^\dagger = 0$, $F_0^\dagger = A$ and first consider the case where $\text{Dom}_1(F) = B$. Let $i$ be in $\{1, \dots, \ell-1\}$. From the proof of Lemma 3.1.3, we deduce that, for $0 < i < \ell-1$, the map $\pi_i = (\text{pr}_i, \text{pr}_{i+1}) : \overline{GR}^s(F) \to \mathbb{P}^1 \times \mathbb{P}^1$ is surjective if and only if $\text{Dom}_i(F) \neq \text{Dom}_{i+1}(F)$. Therefore, the values of $\text{Dom}_i(F)$ can be reconstructed from the datum of $\overline{GR}^s(F)$. When $\text{Dom}_i(F) \neq \text{Dom}_{i+1}(F)$, this is enough to reconstruct $F_i^\dagger$ and $F_i^{\dagger}$ because we need to have $F_i^\dagger = F_i^{\dagger} = \text{Dom}_i(F)$. On the contrary, when $\text{Dom}_i(F) = \text{Dom}_{i+1}(F)$, we note that the image of $\pi_i$ is:

- the subscheme of equation $xt = 0$ if $F_i^\dagger = \text{Dom}_i(F)$ and $F_i^{\dagger} \neq \text{Dom}_i(F)$,

- the subscheme of equation $yz = 0$ if $F_i^\dagger \neq \text{Dom}_i(F)$ and $F_i^{\dagger} = \text{Dom}_i(F)$,

- the subscheme of equation $xt = yz$ if $F_i^\dagger = F_i^{\dagger} = \text{Dom}_i(F)$,
where $[x : y]$ are the coordinates on the first copy of $\mathbb{P}^1$ and $[z : t]$ are the coordinates on the second copy. (We notice that the case $F_i^\dagger = F_i^\dagger \neq \text{Dom}_i(F)$ cannot occur.) As a consequence, one can reconstruct $F_i^\dagger$ and $F_i^\dagger$ in this case as well.

In a similar fashion, we prove that $F$ is determined by $\overline{GR}^s(F)$ when $\ell > 2$, $F_1^\dagger = A$, $F_1^\dagger = B$ and $A$ is dominant at position 2. It then remains to check that we can see on $\overline{GR}^s(F)$ if we are in the case (i), (ii) or (iii) of Definition 3.1.5. Recognizing case (i) is trivial. Finally, distinguishing between the cases (ii) and (iii) can be done by looking at the shape stratification (see [CDM2, Proposition 5.2.5]). □

**Corollary 3.1.7.** — Given a fragment $F$, there exists a unique nonnegative integer $n$ and a unique reduced fragment $F^{\text{red}}$ such that

$$ \overline{GR}^s(F) = \{[0:1]\}^n \times \overline{GR}^s(F^{\text{red}}) $$

where the shape of the prefactor $\{[0:1]\}^n$ is $(I, \dots, I)$.

*Proof.* — Existence have been already discussed. Unicity follows from Proposition 3.1.6 after having noticed that there is a unique way to obtain $n$ and $F'$ for $F$ by flipping letters and performing the transformation of §3.1.2. □

Another byproduct of the proof of Proposition 3.1.6 is the following proposition which underlines the particular interest of the factorisation given by Eq. (13).

**Proposition 3.1.8.** — Let $X$ be a gene. If $\overline{GR}^s(X)$ splits as a product $A^s \times B^s$, then there exists an integer $k$ such that

$$ A^s = V_0^s \times V_1^s \times \dots V_{k-1}^s \\ \text{and } B^s = V_k^s \times V_{k+1}^s \times \dots V_{r-1}^s $$

where the $V_j^s$'s are those defined by Eq. (13).

*Proof.* — It is enough to prove that if $F$ is a reduced fragment, then the variety $\overline{GR}^s(F)$ cannot be decomposed as a product. For this, using the notations of the proof of Proposition 3.1.6, it suffices to show that the image of each function $\pi_i$ cannot be written as a product of shape-stratified varieties (the shape stratification descends to the image of $\pi_i$ thanks to [CDM2, Proposition 5.2.5]). When $\text{Dom}_i(F) = \text{Dom}_{i+1}(F)$, this directly follows for the explicit equations of the image of $\pi_i$ we have obtained. On the contrary, when $\text{Dom}_i(F) = \text{Dom}_{i+1}(F)$, we use [CDM2, Proposition 5.2.5] which teaches us that the subvariety of $(\mathbb{P}^1)^2$ of equation $xz = yt$ is a stratum of the shape stratification. Hence $\pi_i$ cannot be decomposed as a product of shape-stratified varieties of dimension 1 and the proof of Proposition 3.1.8 is complete. □

**3.2. Weights and Kisin variety.** — In this subsection, we study the relationships between the Kisin variety of a gene $X$ and its set of combinatorial weights. We are particularly interested in the cardinality of $W(X)$. Indeed, this numerical invariant has a huge arithmetical meaning since the Breuil–Mézard conjecture relates it directly to the number of irreducible components of the special fibres of deformation rings.

**3.2.1. Behaviour of weights under gene transformations.** — In §3.1, we have seen a couple of transformations of a fragment $F$ that preserve the associated Kisin varieties. To begin with, we would like to study how these transformations affect the set of fragmentary combinatorial weights $W(F)$ of $F$ and its cardinality. Eventually, we aim at proving the following theorem which, in some sense, can be seen as a numerical version of the first part of Conjecture 3.1.2 and then provides some support to it.
**Theorem 3.2.1.** — Let $\mathbb{X}$ be a gene containing at least an instance of the letter 0. Then the cardinality of $W(\mathbb{X})$ depends only on the Kisin variety $\overline{GR}^s(\mathbb{X})$. More precisely, if

$$ \overline{GR}^s(\mathbb{X}) = V_0^s \times V_1^s \times \cdots \times V_{r-1}^s $$

is the canonical decomposition of $\overline{GR}^s(\mathbb{X})$ given by Eq. (13), we have:

$$ \mathrm{Card} W(\mathbb{X}) = c(V_0^s) \cdot c(V_1^s) \cdots c(V_{r-1}^s) $$

where $c(V_j^s)$ is an integer depending only on $V_j^s$ (as suggested by the notation).

**Remark 3.2.2.** — After Proposition 3.1.8, we see that Theorem 3.2.1 can be rephrased as follows. Let SEKV$_0$ be the set of all shape-stratified subvarieties of $(\mathbb{P}^1)^n$ (for varying $n$) that can be written as a product of the form $\overline{GR}^s(F_0) \times \cdots \times \overline{GR}^s(F_{r-1})$ for some reduced fragments $F_0, \dots, F_{r-1}$. Theorem 3.2.1 then tells that there exists a *multiplicative function* $c: \mathrm{SEKV}_0 \to \mathbb{N}$ such that $\mathrm{Card} W(\mathbb{X}) = c(\overline{GR}^s(\mathbb{X}))$ for all gene $\mathbb{X}$ with $X_0 = 0$. Moreover, it will follow from Theorem 3.2.6 of §3.2.2 below that $c$ is nondecreasing. Furthermore, we note that the function $c$ can be prolonged to the set SEKV defined in the introduction while preserving the previous properties; for instance, for $W^s \in \mathrm{SEKV}$, one can define $c(W^s)$ as the maximum of the $c(V^s)$'s for $V^s \in \mathrm{SEKV}_0$ with $V^s \subset W^s$.

The easiest transformation considered in §3.1 consists in flipping the letters A and B. If $F$ is a fragment, we denote by $F^\tau$ the fragment obtained by performing this transformation. We have already said that $\overline{GR}^s(F) = \overline{GR}^s(F^\tau)$. Similarly, it turns out that the sets $W(F)$ and $W(F^\tau)$ are closely related. Precisely, if $w = (w_0, \dots, w_{\ell-1}) \in \{0, 1\}^\ell$ is a fragmentary combinatorial weight, we set $w^\tau = (1-w_0, w_1, \dots, w_{\ell-1})$. Similarly, if $W$ is a subset of $\{0, 1\}^\ell$, we define $W^\tau$ as the subset of $\{0, 1\}^\ell$ obtained by applying the transformation $w \mapsto w^\tau$ to each element of $W$.

**Lemma 3.2.3.** — For any fragment $F$ of length $\ell > 1$, we have $W(F^\tau) = W(F)^\tau$.

*Proof.* — We directly check from the definition (see Definition 2.1.4) that the set of associated fragmentary combinatorial weights is unaffected if we exchange the top row and the bottom row of a fragment. Hence, we may assume without loss of generality that $F$ is top-reduced, i.e. $F_0^\dagger = 0$ and $F_0^\dagger = A$. Coming back to the definition of $W(F)$, we find:

$$ \bullet W_1^{(b,b)}(F) = \{(0,0)\} $$

$$ \bullet W_1^{(a,b)}(F) = \begin{cases} \{ (1,0) \} & \text{if } F_1^\dagger \sim A \\ \{ (0,0) \} & \text{otherwise} \end{cases} $$

$$ \bullet W_1^{(b,a)}(F) = \begin{cases} \{ (0,0), (1,0) \} & \text{if } F_1^\dagger \sim A \\ \emptyset & \text{otherwise} \end{cases} $$

and similarly:

$$ \bullet W_1^{(b,b)}(F^\tau) = \{(1,0)\} $$

$$ \bullet W_1^{(a,b)}(F^\tau) = \begin{cases} \{ (0,0) \} & \text{if } F_1^\dagger \sim A \\ \{ (1,0) \} & \text{otherwise} \end{cases} $$

$$ \bullet W_1^{(b,a)}(F^\tau) = \begin{cases} \{ (0,0), (1,0) \} & \text{if } F_1^\dagger \sim A \\ \emptyset & \text{otherwise.} \end{cases} $$

Therefore, one checks that $W_1^{\square}(F^\tau) = W_1^{\square}(F)^\tau$ for any $\square \in \{(a, b), (b, a), (b, b)\}$. By induction, this equality extends to all indices $i$ between 1 and $\ell-1$ and the proposition follows. $\square$
**Remark 3.2.4.** — If $\underline{F}$ is a fragment of length 1, one can verify by hand that $W(\underline{F}^\tau) = W(\underline{F})$, i.e. the weights are not twisted in this case. In particular, in all cases, we conclude that $W(\underline{F})$ and $W(\underline{F}^\tau)$ have the same cardinality.

We now focus on the transformation reported at the end of §3.1.2.

**Lemma 3.2.5.** — Let $\underline{F}$ be a fragment of length $\ell > 1$. We assume that $F_0^\dagger = 0$ and $F_0^\dagger = F_1^\dagger = \cdots = F_{n-1}^\dagger = \mathbf{A}$ for some integer $n \le \ell$. Let $\underline{F}'$ be the following truncated fragment:

$$ \begin{array}{c} \mathbf{0} \\ \mathbf{A} \end{array} \quad \begin{array}{c} F_n^\dagger \\ F_n^\dagger \end{array} \quad \begin{array}{c} F_{n+1}^\dagger \\ F_{n+1}^\dagger \end{array} \quad \cdots \quad \begin{array}{c} F_{\ell-1}^\dagger \\ F_{\ell-1}^\dagger \end{array} $$

Then $\text{Card} W(\underline{F}) = \text{Card} W(\underline{F}')$.

*Proof.* — For $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$, set $c_i^\square = \text{Card} W_i^\square(\underline{F})$ and $c_i'^{\square} = \text{Card} W_i^\square(\underline{F}')$. Using the recursive formulas of §2.2, one checks by induction on $i$ that $c_i^{(\mathbf{a}, \mathbf{b})} = 1$, $c_i^{(\mathbf{b}, \mathbf{a})} = 0$, $c_i^{(\mathbf{b}, \mathbf{b})} = 1$ for $i < n$ and then, that:

$$ c_n^{(\mathbf{a}, \mathbf{b})} = c_1'^{(\mathbf{a}, \mathbf{b})} = 1, \quad c_n^{(\mathbf{b}, \mathbf{b})} = c_1'^{(\mathbf{b}, \mathbf{b})}, \quad c_n^{(\mathbf{b}, \mathbf{b})} = c_1'^{(\mathbf{b}, \mathbf{b})} = 1. $$

(Note that the common value of $c_n^{(\mathbf{b}, \mathbf{b})}$ and $c_1'^{(\mathbf{b}, \mathbf{b})}$ can be either 0 or 2 depending on $F_n^\dagger$.)
By a second induction, we finally find that

$$ c_i^{(\mathbf{a}, \mathbf{b})} = c_{i-n+1}^{(\mathbf{a}, \mathbf{b})}, \quad c_i^{(\mathbf{b}, \mathbf{b})} = c_{i-n+1}^{(\mathbf{b}, \mathbf{b})}, \quad c_i^{(\mathbf{b}, \mathbf{b})} = c_{i-n+1}^{(\mathbf{b}, \mathbf{b})} $$

for all $i < \ell$. After this, the lemma follows from Corollary 2.2.3. $\square$

*Proof of Theorem 3.2.1.* — If $\mathcal{V}^s$ is a shape-stratified subvariety of $(\mathbb{P}^1)^\ell$ of the form $\overline{\mathcal{G}\mathcal{R}}^s(\underline{F})$ for some reduced fragment $\underline{F}$, let us set $c(\mathcal{V}^s) = \text{Card} W(\underline{F})$. Proposition 3.1.6 ensures that this definition is nonambiguous. Let $\bullet$ be the Kisin variety of the unique reduced fragment of length 1 (namely $F_0^\dagger = 0$ and $F_0^\dagger = \mathbf{A}$). Concretely it is the subvariety $\{[0:1]\}$ of $\mathbb{P}^1$ with shape function equal to I. Moreover we obtain from the definition that $c(\bullet) = 1$.

We fix a gene $\mathcal{X}$ with $X_0 = 0$. The Kisin variety associated to $\mathcal{X}$ decomposes as:

$$ \overline{\mathcal{G}\mathcal{R}}^s(\mathcal{X}) = \prod_{\underline{F}} \overline{\mathcal{G}\mathcal{R}}^s(\underline{F}) $$

where the product runs over all the fragments of $\mathcal{X}$. Besides, by Corollary 3.1.7, for each such fragment $\underline{F}$, we have a second decomposition:

$$ \overline{\mathcal{G}\mathcal{R}}^s(\underline{F}) = \bullet^n \times \overline{\mathcal{G}\mathcal{R}}^s(\underline{F}^{\text{red}}) $$

where $n$ is an integer and $\underline{F}^{\text{red}}$ is a reduced fragment canonically attached to $\underline{F}$. Putting together all the above decompositions, we end up with the decomposition of Eq. (13). Moreover, we deduce from Lemmas 3.2.3 and 3.2.5 that $\underline{F}$ and $\underline{F}^{\text{red}}$ share the same number of weights. We can then write:

$$ \text{Card} W(\mathcal{X}) = \prod_{\underline{F}} \text{Card} W(\underline{F}) = \prod_{\underline{F}} \text{Card} W(\underline{F}^{\text{red}}) = \prod_{\underline{F}} c(\overline{\mathcal{G}\mathcal{R}}^s(\underline{F}^{\text{red}})). $$

As $c(\bullet) = 1$, we obtain the product formula of Theorem 3.2.1. $\square$
**3.2.2. A monotony result.** — In the construction of [CDM2, §5.4], the candidate $D(\mathcal{V}^s)$ for the rigid space associated to a Kisin variety $\mathcal{V}^s$ is obtained by taking the formal completing of a certain space along $\mathcal{V}^s$ (which naturally appears as a subscheme of the special fibre). Hence, one may expect to some extent that the deformation ring $R^\psi(t, \bar{\rho})$ becomes more intricated as the underlying Kisin variety gets larger. Since, by the Breuil–Mézard conjecture, the number of common Serre weights of $t$ and $\bar{\rho}$ is a direct measure of the complexity of $R^\psi(t, \bar{\rho})$, one may expect that this number increases when the Kisin variety gets larger. It turns out that this rough intuition is indeed correct as shown by the next theorem.

**Theorem 3.2.6.** — (1) Let $\underline{F}$ and $\underline{F}'$ be two fragments such that $\overline{\mathcal{G}\mathcal{R}^s}(\underline{F}) \subset \overline{\mathcal{G}\mathcal{R}^s}(\underline{F}')$. Then $\text{Card} \mathcal{W}(\underline{F}) \le \text{Card} \mathcal{W}(\underline{F}')$.

(2) Let $\underline{F}_1, \underline{F}_2$ and $\underline{F}'$ be three fragments such that $\overline{\mathcal{G}\mathcal{R}^s}(\underline{F}_1) \times \overline{\mathcal{G}\mathcal{R}^s}(\underline{F}_2) \subset \overline{\mathcal{G}\mathcal{R}^s}(\underline{F}')$. Then $\text{Card} \mathcal{W}(\underline{F}_1) \cdot \text{Card} \mathcal{W}(\underline{F}_2) \le \text{Card} \mathcal{W}(\underline{F}')$.

In order to prove the theorem, we need some preparatory results. In what follows, for $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$, we will denote the cardinality of $\text{Card} W_i^\square(\underline{F})$ by $c_i^\square$ and that of $\text{Card} W_i^\square(\underline{F}')$ by $c_i'^\square$ as we already did in the proof of Lemma 3.2.5.

**Lemma 3.2.7.** — Let $\underline{F}$ be a fragment of length $\ell$.

(1) For all $i$ in $\{0, \dots, \ell-1\}$, we have $|c_i^{(\mathbf{a},\mathbf{b})} - c_i^{(\mathbf{b},\mathbf{a})}| \le c_i^{(\mathbf{b},\mathbf{b})}$.

(2) We assume that there exists $s$ and $t$ with $0 < s < t \le \ell$ and $F_s^\dagger = \mathbf{A}$, $F_s^\dagger = \mathbf{B}$, $\{F_i^\dagger, F_i^\dagger\} = \{\mathbf{A}, \mathbf{B}\}$ for $s < i < t$ and $F_i^\dagger = F_i^\dagger \in \{\mathbf{A}, \mathbf{AB}\}$. Then there exist nonnegative integers $n$ and $m$ such that:

$$c_t^{(\mathbf{a},\mathbf{b})} = c_s^{(\mathbf{a},\mathbf{b})} + n \cdot c_s^{(\mathbf{b},\mathbf{b})},$$

$$c_t^{(\mathbf{b},\mathbf{a})} = c_s^{(\mathbf{a},\mathbf{b})} + m \cdot c_s^{(\mathbf{b},\mathbf{b})},$$

$$\text{and } c_t^{(\mathbf{b},\mathbf{b})} = c_s^{(\mathbf{b},\mathbf{b})}.$$

*Proof.* — It is an easy checking using the recursive formulas of §2.2. $\square$

*Proof of Theorem 3.2.6.* — We first prove the statement (1) of the theorem under the additional assumption that there exists an integer $s$ such that:

- for $0 \le i < s-1$, we have $F_i^\dagger = F_i'^\dagger$ and $F_i^\dagger = F_i'^\dagger$,

- $F_{s-1}^\dagger = \mathbf{A}$, $F_{s-1}^\dagger = \mathbf{B}$ and $F_{s-1}^\dagger = \mathbf{A}$, $F_{s-1}^\dagger = \mathbf{A}$,

- $\mathbf{A}$ is dominant in $\underline{F}$ at position $s$,

- for $s \le i < \ell$, we have $F_i^\dagger = \tau(F_i'^\dagger)$ and $F_i^\dagger = \tau(F_i'^\dagger)$

where $\tau$ denotes the transposition exchanging the letters $\mathbf{A}$ and $\mathbf{B}$. In this particular situation, the equations defining $\overline{\mathcal{G}\mathcal{R}^s}(\underline{F})$ are exactly those defining $\overline{\mathcal{G}\mathcal{R}^s}(\underline{F}')$ plus the equation $x_{s-1}y_s = 0$. Moreover the shape functions agree on the smallest variety. Therefore, the inclusion $\overline{\mathcal{G}\mathcal{R}^s}(\underline{F}) \subset \overline{\mathcal{G}\mathcal{R}^s}(\underline{F}')$ holds and we have to prove that $\text{Card} \mathcal{W}(\underline{F}) \le \text{Card} \mathcal{W}(\underline{F}')$.

Since the fragments $\underline{F}$ and $\underline{F}'$ agree up to position $s-2$, we have $c_i^\square = c_i'^\square$ for all $i < s-1$ and all $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$. Besides, one also checks that $c_{s-1}^{(\mathbf{a},\mathbf{b})} = c_{s-1}^{(\mathbf{b},\mathbf{a})}$ and $c_{s-1}^{(\mathbf{b},\mathbf{b})} = c_{s-1}^{(\mathbf{b},\mathbf{b})}$. Now, we use the hypothesis that $\mathbf{A}$ is dominant in $\underline{F}$ at position $s$. It implies that $\mathbf{A} \in \{F_s^\dagger, F_s'^\dagger\}$. Let us first assume that $F_s^\dagger = \mathbf{A}$ and $F_s'^\dagger = \mathbf{B}$. In this case, we find:

$$c_s^{(\mathbf{a},\mathbf{b})} = c_{s-1}^{(\mathbf{a},\mathbf{b})},$$

$$c_s^{(\mathbf{b},\mathbf{b})} = c_{s-1}^{(\mathbf{b},\mathbf{b})},$$
$$c'_{s}^{(a,b)} = c'_{s-1}^{(a,b)} + c'_{s-1}^{(b,b)} = c_{s-1}^{(a,b)} + c_{s-1}^{(b,b)}, \\ c'_{s}^{(b,b)} = \max(c'_{s-1}^{(a,b)}, c'_{s-1}^{(b,a)}) = \max(c_{s-1}^{(a,b)} + c_{s-1}^{(b,a)}).$$

From the first part of Lemma 3.2.7, we deduce that $c_s^{(a,b)} \le c_s^{(a,b)}$ and $c_s^{(b,b)} \le c_s^{(b,b)}$. Using again that $\mathbf{A}$ is dominant in $\underline{F}$ at position $s$, we deduce that there exists a position $t > s$ with the property that $F_t^\uparrow = F_t^\downarrow \in \{\mathbf{A}, \mathbf{AB}\}$. We can then apply the second part of Lemma 3.2.7 with $\underline{F}$ and $\tau(\underline{F}')$ and conclude that $c_t^\square \le c_t'^\square$ for all $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$. By induction, we finally find that $c_i^\square \le c_i'^\square$ for all $i \ge t$ and, in particular, for $i = \ell-1$. Corollary 2.2.3 allows us to conclude in this case. The other cases where $(F_s^\uparrow, F_s^\downarrow)$ is equal to $(\mathbf{A}, \mathbf{A})$ or $(\mathbf{B}, \mathbf{A})$ are handled similarly.

We now consider general $\underline{F}$ and $\underline{F}'$. The assumption $\overline{\mathcal{GR}}^s(\underline{F}) \subset \overline{\mathcal{GR}}^s(\underline{F}')$ means that the set of equations defining $\overline{\mathcal{GR}}^s(\underline{F}')$ is included in the one defining $\overline{\mathcal{GR}}^s(\underline{F})$. Besides, the particular choices of fragments we have considered earlier correspond exactly to the case where one equation is removed (up to exchanging rows and flipping letters). One can then go from $\underline{F}$ to $\underline{F}'$ by applying these particular transformations and removing the equations one by one. The first part of Theorem 3.2.6 then follows by transitivity of inequality.

The second part is proved in a similar fashion and left to the reader. $\square$

**Corollary 3.2.8.** — Let $\mathcal{X}$ and $\mathcal{X}'$ be two genes such that $\overline{\mathcal{GR}}^s(\mathcal{X}) \subset \overline{\mathcal{GR}}^s(\mathcal{X}')$. Then $\mathrm{Card}\,\mathcal{W}(\mathcal{X}) \subset \mathrm{Card}\,\mathcal{W}(\mathcal{X}')$.

*Proof.* — It follows from the assumption that if the $i$-th projection map $\mathrm{pr}_i : (\mathbb{P}^1)^f \to \mathbb{P}^1$ is constant on $\overline{\mathcal{GR}}^s(\mathcal{X}')$, it needs to be constant on $\overline{\mathcal{GR}}^s(\mathcal{X})$ as well. We can then conclude by applying Theorem 3.2.6 to each reduced fragment $\underline{F}'$ of $\mathcal{X}'$. $\square$

**3.3. Effect of crosses.** — We now discuss the second part of Conjecture 3.1.2. Following [CDM2], when a fragment $\underline{F}$ and integer $i$ are such that $F_i^\uparrow = F_i^\downarrow = \mathrm{Dom}_{i+1}(\underline{F})$, we will say that $\underline{F}$ exhibits a cross at position $i$. It turns out that the presence of crosses has only a very limited impact on the associate candidate $D(-)$. Precisely, if $\underline{F}$ is a fragment exhibiting a cross at position $i$ and $\underline{F}^{(i)}$ is the fragment obtained by deleting the $i$-th column in $\underline{F}$, we have by construction:

$$D(\underline{F}) \approx D(\underline{F}^{(i)}) [[T]].$$

where $T$ is a new variable. Nevertheless, we cannot expect that $R(\underline{F}) \approx R(\underline{F}^{(i)})[[T]]$ because, thanks to the Breuil–Mézard conjecture, this would imply that $\underline{F}$ and $\underline{F}^{(i)}$ have the same number of weights, which is not true in general.

In what follows, we prove that when a cross is deleted, the number of weights always decreases and, in most cases, it strictly decreases. Hence, it is minimal when the fragment does not exhibit any crosses. This observation supports Conjecture 3.1.2 as the subring of power-bounded functions is the integral model of $D(\underline{F})$ with the smallest Hilbert–Samuel multiplicity.

**Theorem 3.3.1.** — Let $\underline{F}$ be a fragment on length $\ell$ and $i$ be index at which $\underline{F}$ exhibits a cross. We set $\delta_{i-1} = 1$ if $F_{i-1}^\uparrow \sim F_{i-1}^\downarrow$, and $\delta_{i-1} = 0$ otherwise.

(i) For any combinatorial weight $w = (w_0, \dots, w_{\ell-1})$ in $\mathcal{W}(\underline{F})$, we have $w_i = 0$.

(ii) For $w_0, \dots, w_{\ell-2} \in \{0, 1\}$, we have $(w_0, \dots, w_{\ell-2}) \in \mathcal{W}(\underline{F}^{(i)})$ if and only if $(w_0, \dots, w_{i-1}, 0, w_i, \dots, w_{\ell-2}) \in \mathcal{W}(\underline{F})$ and $(w_{i-1}, w_i) \ne (\delta_{i-1}, 1)$.

*Proof.* — Without loss of generality, we may assume $F_i^\uparrow = F_i^\downarrow = \mathrm{Dom}_{i+1}(\underline{F}) = \mathbf{A}$. First of all, we observe that it follows directly from Definition 2.1.4 that the last coordinate of all
weights in $W_i^{(\text{a,b})}(\underline{F})$ and in $W_i^{(\text{b,a})}(\underline{F})$ is 0. Besides, we have:

$$W_{i+1}^{(\text{a,b})}(\underline{F}) = W_i^{(\text{a,b})}(\underline{F}) \times \{0\} \quad \text{if } F_{i+1}^{\dagger} = \mathbf{A},$$

$$W_{i+1}^{(\text{b,a})}(\underline{F}) = W_i^{(\text{b,a})}(\underline{F}) \times \{0\} \quad \text{if } F_{i+1}^{\dagger} = \mathbf{A},$$

$$W_{i+1}^{(\text{b,b})}(\underline{F}) = (W_i^{(\text{a,b})}(\underline{F}) \cup W_i^{(\text{b,a})}(\underline{F})) \times \{1\}.$$

Hence, the $i$-th coordinate of the elements of $W_{i+1}^{(\text{b,b})}(\underline{F})$ is always equal to 0 and similarly, the $i$-th coordinate of the elements of $W_{i+1}^{(\text{a,b})}(\underline{F})$ (resp. of $W_{i+1}^{(\text{b,a})}(\underline{F})$) is 0 provided that $F_{i+1}^{\dagger} = \mathbf{A}$ (resp. $F_{i+1}^{\dagger} = \mathbf{A}$). Moreover, a variant of Lemma 3.2.7.(2) shows that the map $(w_0, \dots, w_{\ell-1}) \mapsto (w_0, \dots, w_i)$ takes $\mathcal{W}(\underline{F})$ to

$$\tilde{W}_{i+1}^{(\text{a,b})}(\underline{F}) \cup \tilde{W}_{i+1}^{(\text{b,a})}(\underline{F}) \cup W_{i+1}^{(\text{b,b})}(\underline{F})$$

where $\tilde{W}_{i+1}^{(\text{a,b})}(\underline{F}) = W_{i+1}^{(\text{a,b})}(\underline{F})$ if $F_{i+1}^{\dagger} = \mathbf{A}$ and $\emptyset$ otherwise, and similarly $\tilde{W}_{i+1}^{(\text{b,a})}(\underline{F}) = W_{i+1}^{(\text{b,a})}(\underline{F})$ if $F_{i+1}^{\dagger} = \mathbf{A}$ and $\emptyset$ otherwise. As a consequence, we conclude that the $i$-th coordinate of the elements of $\mathcal{W}(\underline{F})$ are all 0, which proves (i).

We now move to (ii). In order to save space, we only consider the case where $F_{i+1}^{\dagger} = \mathbf{A}$ and $F_{i-1}^{\dagger} = F_{i+1}^{\dagger} = \mathbf{B}$ (the other cases are treated similarly). Since $\underline{F}$ and $\underline{F}^{(i)}$ agree up to position $i-1$, we certainly have $W_{i-1}^{\square}(\underline{F}) = W_{i-1}^{\square}(\underline{F}^{(i)})$ for all $\square \in \{(\text{a}, \text{b}), (\text{b}, \text{a}), (\text{b}, \text{b})\}$, so we can use the shorter notation $W_{i-1}^{\square}$ to refer to this set. A direct computation then gives:

$$W_{i+1}^{(\text{a,b})}(\underline{F}) = W_{i-1}^{(\text{a,b})} \times \{(0,0)\}$$

$$W_{i+1}^{(\text{b,b})}(\underline{F}) = (W_{i-1}^{(\text{a,b})} \cup W_{i-1}^{(\text{b,b})}) \times \{(0,1)\}$$

$$W_i^{(\text{a,b})}(\underline{F}^{(i)}) = W_{i-1}^{(\text{a,b})} \times \{0\}$$

$$W_i^{(\text{b,b})}(\underline{F}^{(i)}) = W_{i-1}^{(\text{b,b})} \times \{1\}$$

from what the assertion (ii) follows. $\square$

The second part of Theorem 3.3.1 tells us that there is an injection

$$\iota_i : \begin{array}{ccc} \mathcal{W}(\underline{F}^{(i)}) & \hookrightarrow & \mathcal{W}(\underline{F}) \\ (w_0, \dots, w_{\ell-2}) & \mapsto & (w_0, \dots, w_{i-1}, 0, w_i, \dots, w_{\ell-2}). \end{array}$$

For the cardinalities, this implies that $\text{Card}\,\mathcal{W}(\underline{F}^{(i)}) \le \text{Card}\,\mathcal{W}(\underline{F})$, i.e. the number of weights decreases when a cross is removed as we claimed earlier. In general, $\iota_i$ is not surjective, however. The next proposition shows that it actually occurs quite rarely.

**Proposition 3.3.2.** — We keep the above notations and assume that $\underline{F}$ is reduced (see Definition 3.1.5). The mapping $\iota_i$ is a bijection if and only if $\underline{F}$ exhibits another cross at position $i-1$ or at position $i+1$ (or both).

*Proof.* — Throughout the proof, we assume that $\underline{F}$ is top-reduced, the bottom-reduced case being totally similar.

If $\underline{F}$ exhibits a cross at position $i+1$, it follows from Theorem 3.3.1.(i) that the $(i+1)$-th coordinate of the weights of $\underline{F}$ is always 0. The surjectivity of $\iota_i$ then follows from Theorem 3.3.1.(ii). A similar argument shows that $\iota_i$ is surjective if $\underline{F}$ exhibits a cross at position $i-1$.

We now assume that there is no crosses at position $i-1$ and $i+1$ and we want to prove that $\iota_i$ is not surjective. For this, it is enough to check that $\text{Card}\,\mathcal{W}(\underline{F}) > \text{Card}\,\mathcal{W}(\underline{F}^{(i)})$. We first remark that, given that $\underline{F}$ is top-reduced, we have $c_0^{(\text{a,b})} = 1$ and $c_0^{(\text{b,b})} = 1$. By
induction, this implies that $c_j^{(\mathbf{a},\mathbf{b})}$ and $c_j^{(\mathbf{b},\mathbf{b})}$ are both strictly positive for all $j$. Regarding $c_j^{(\mathbf{b},\mathbf{a})}$, the only possibility to make it vanish is to have $F_0^\dagger = F_1^\dagger = \cdots = F_j^\dagger = \mathbf{A}$.

After these preparations, we need to distinguish between several cases according to the values of $F_j^\dagger$, $F_j^\dagger$ for $j \in \{i-1, i, i+1\}$. As in the proof of Theorem 3.3.1, we only treat the case where $F_{i-1}^\dagger = F_{i+1}^\dagger = F_i^\dagger = F_{i+1}^\dagger = \mathbf{A}$ and $F_{i-1}^\dagger = F_{i+1}^\dagger = \mathbf{B}$, the other ones being similar. In this case, we have $c_{i+1}^{(\mathbf{b},\mathbf{b})}(\underline{F}) = c_i^{(\mathbf{b},\mathbf{b})}(\underline{F}^{(i)}) + c_{i-1}^{(\mathbf{a},\mathbf{b})}(\underline{F}) > c_i^{(\mathbf{b},\mathbf{b})}(\underline{F}^{(i)})$. Using Lemma 3.2.7.(2), we deduce that there exists $t > i$ such that $c_{t+1}^\square(\underline{F}) > c_t^\square(\underline{F}^{(i)})$ for $\square \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a}), (\mathbf{b}, \mathbf{b})\}$. By induction, these inequalities continue to hold for all $j \ge t$, which eventually implies that $\text{Card} \mathcal{W}(\underline{F}) > \text{Card} \mathcal{W}(\underline{F}^{(i)})$ as wanted. $\square$

**Remark 3.3.3.** — The hypothesis that $\underline{F}$ is reduced is necessary because there might exist crosses in the initial “reducible” part of a fragment and, of course, those crosses have no influence on the number of weights since it is the case of the whole reducible part.

In a more crude language, Proposition 3.3.2 says that the effect of two (or more) consecutive crosses is the same than that a unique cross. On the contrary, a unique cross cannot be deleted innocently. This suggests that the second part of Conjecture 3.1.2 could be an equivalence provided that we restrict ourselves to the crosses located in the nonreducible parts of the gene.

### 4. The bijection between $\mathcal{W}(\mathcal{X})$ and $\mathcal{D}(t, \bar{\rho})$

This section is devoted to the proof of Theorem 2.3.1. The general plan of the proof goes as follows. Given a coherent triple $(h, \gamma, \gamma')$ parametrizing the datum of $\bar{\rho}$ and $t$, we start by constructing in §4.1 a surjection $S_\Sigma : \Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')} \to \mathcal{D}(t, \bar{\rho})$ where $\Sigma^{\text{ac}}$ and $\Sigma^{(h,\gamma,\gamma')}$ are two sets of $(2f)$-periodic sequences of integers. It then remains to study the default of injectivity of $S_\Sigma$. For this, we first reinterpret in §4.2 the elements in the intersection $\Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')}$ thanks to a new combinatorial datum, that we call enriched weights. We finally relate in §4.3 those enriched weights to the combinatorial weights we have already introduced in §2.1 and measure the default of injectivity of $S_\Sigma$ at this level.

#### 4.1. Description of common weights.
In what follows, we constantly work with $(2f)$-periodic sequences of integers. We denote their set by $\Sigma$ and introduce two definitions on these sequences.

**Definition 4.1.1.** — A pair of integers $(x, y)$ is active if the three following conditions are fulfilled:

(i) $0 \le x, y \le p$;

(ii) $x \in \{0, p\}$ or $y \in \{0, p\}$;

(iii) $x \neq y$.

A sequence $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$ in $\Sigma$ is active if $(\sigma_i, \sigma_{i+f})$ is active for all $i$ in $\mathbb{Z}$. We denote $\Sigma^{\text{ac}}$ the subset of $\Sigma$ consisting of active sequences.

**Definition 4.1.2.** — We say that $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$ in $\Sigma$ is $(h, \gamma, \gamma')$-compatible if, for all $i$ in $\mathbb{Z}$, we have:

$$ (14) \qquad \sum_{i=0}^{2f-1} \sigma_i p^{2f-1-i} \equiv h - (q+1)\gamma' \pmod{q^2-1}. $$
We let $\Sigma^{(h,\gamma,\gamma')}$ denote the set of $(h, \gamma, \gamma')$-compatible sequences.

**4.1.1.** *From sequences to weights.* — Active sequences are closely related to Serre weights. Indeed, to any active sequence $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$, we associate the tuple

$$S_{\Sigma}(\underline{\sigma}) = (s, \underline{r}) \in (\mathbb{Q}/(q-1)\mathbb{Z}) \times \{0, \dots, p-1\}^f$$

defined as follows. Given an index $i \in \{0, \dots, f-1\}$, we set:

$$ (15) \qquad \begin{aligned} r_{f-1-i} &= \sigma_i - 1 & \text{if } \sigma_{i+f} &= 0, \\ r_{f-1-i} &= p - 1 - \sigma_i & \text{if } \sigma_{i+f} &= p, \\ r_{f-1-i} &= \sigma_{i+f} - 1 & \text{if } \sigma_i &= 0, \\ r_{f-1-i} &= p - 1 - \sigma_{i+f} & \text{if } \sigma_i &= p \end{aligned} $$

and $\underline{r} = (r_0, \dots, r_{f-1})$. We observe that the activity condition ensures that the above definition covers all cases and is not ambiguous. We further set $\varepsilon_{f-1-i} = 0$ if $\sigma_i < \sigma_{i+f}$ and $\varepsilon_{f-1-i} = 1$ otherwise. We finally put:

$$ (16) \qquad s = \frac{1}{q+1} \left( h - \sum_{i=0}^{f-1} (-1)^{\varepsilon_i} (1+r_i)p^i \right) - \sum_{i=0}^{f-1} \varepsilon_i (1+r_i)p^i \in \mathbb{Q}/(q-1)\mathbb{Z}. $$

When $s$ is an integer, we will slightly abuse notations and identify the pair $(s, \underline{r})$ with the corresponding Serre weight without further discussion.

**Proposition 4.1.3.** — The function $S_{\Sigma}$ induces a mapping $\Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')} \to \mathcal{D}(t, \bar{p})$.

*Proof.* — We consider $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$ in $\Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')}$ and write $S_{\Sigma}(\underline{\sigma}) = (s, \underline{r})$ with $\underline{r} = (r_0, \dots, r_{f-1})$. By definition, the $r_i$'s and $s$ are given by the formulas (15) and (16) where we recall that $\varepsilon_{f-1-i} = 0$ if $\sigma_i < \sigma_{i+f}$ and $\varepsilon_{f-1-i} = 1$ otherwise. It follows from the fact that $\underline{\sigma}$ is $(h, \gamma, \gamma')$-compatible that:

$$ (17) \qquad h \equiv \sum_{i=0}^{2f-1} \sigma_i p^{2f-1-i} \equiv \sum_{i=0}^{f-1} (\sigma_{i+f} - \sigma_i) p^{f-1-i} \pmod{q+1}. $$

Observe that if $\sigma_i < \sigma_{i+f}$, the activity condition implies that $\sigma_i = 0$ or $\sigma_{i+f} = p$. In the first case, $r_{f-1-i} = \sigma_{i+f} - 1$, from what we derive $\sigma_{i+f} - \sigma_i = 1 + r_{f-1-i}$. A similar calculation shows that the last equality holds in the second case as well. If $\sigma_i > \sigma_{i+f}$, one finds $\sigma_i - \sigma_{i+f} = 1 + r_{f-1-i}$. Therefore, in all cases, we have the relation:

$$ (18) \qquad \sigma_{i+f} - \sigma_i = (-1)^{\varepsilon_{f-1-i}} (1 + r_{f-1-i}). $$

Plugging this in Eq. (17), we find that:

$$ h \equiv \sum_{i=0}^{f-1} (-1)^{\varepsilon_i} (1 + r_i) p^i \pmod{q+1}. $$

Hence $s$ is an integer (see 16) and we can see the pair $(s, \underline{r})$ as a Serre weight. Moreover, the congruences (16) and (17) show that it lies in $\mathcal{D}(\bar{p})$. In order to prove that it lies also in $\mathcal{D}(t)$, we have to construct $\varepsilon'_0, \dots, \varepsilon'_{f-1}$ exhibiting the two following properties: first, the $r_i$'s and the $c_i$'s have to be related by the rules of the table (9) (page 7) and, second, the congruence:

$$ (19) \qquad s \equiv \gamma' + \sum_{i=0}^{f-1} \varepsilon'_{i} (p - 1 - r_{i}) p^{i} \pmod{q-1} $$
must hold (see Lemma 1.2.4). Here the $c_i$'s are the integers introduced in §1.2; we recall that they all belong to $\{0, \dots, p-1\}$ and that they satisfy the relation:

$$ \gamma' - \gamma \equiv \sum_{i=0}^{f-1} c_i p^i \pmod{q-1}. $$

The definition of the $\varepsilon'_i$'s goes as follows: for those indices $i$ for which $\{\sigma_i, \sigma_{i+f}\} \neq \{0, p\}$, we set $\varepsilon'_{f-1-i} = 0$ if $\sigma_i = 0$ or $\sigma_{i+f} = 0$, and $\varepsilon'_{f-1-i} = 1$ if $\sigma_i = p$ or $\sigma_{i+f} = p$. Note that this dichotomy covers all cases thanks to the activity condition. We then complete the sequence of $\varepsilon'_i$'s by setting $\varepsilon'_{f-1-i} = \varepsilon'_{f-2-i}$ (where the indices are considered modulo $f$) when $\{\sigma_i, \sigma_{i+f}\} = \{0, p\}$. This definition is not ambiguous except in the situation where $\{\sigma_i, \sigma_{i+f}\} = \{0, p\}$ for all $i$; in this case, we agree to define $\varepsilon'_i = 1$ for all $i$.

In order to prove that the $\varepsilon'_i$'s are convenient, we first observe that the equality:

$$ \sigma_i + \sigma_{i+f} = p - (-1)^{\varepsilon'_{f-1-i}} (p - 1 - r_{f-1-i}) $$

holds in all cases. Reducing the congruence (16) modulo $q-1$ and using the fact that the triple $(h, \gamma, \gamma')$ is coherent, a simple calculation leaves us with the relation:

$$ \sum_{i=0}^{f-1} c_i p^i \equiv \sum_{i=0}^{f-1} (-1)^{\varepsilon'_{i}} (p-1-r_i) p^i \pmod{q-1}. $$

We set $s_i = p-1-r_i$ if $\varepsilon'_i = 0$ and $s_i = r_i+1$ otherwise. An easy computation then shows that $(-1)^{\varepsilon'_{i}}(p-1-r_i) = s_i - p\varepsilon'_{i}$, from what we finally deduce:

$$ (20) \qquad \sum_{i=0}^{f-1} c_i p^i \equiv \sum_{i=0}^{f-1} (s_i - \varepsilon'_{i-1}) p^i \pmod{q-1}. $$

An interesting feature of the latest equality is that $s_i - \varepsilon'_{i-1}$ is in the range $\{0, \dots, p-1\}$ for all $i$. Indeed, consider first the case where $\varepsilon'_{i} = 1$. With this additional assumption, we have $1 \le s_i \le p$ and the equality $s_i = p$ holds if and only if $\{\sigma_{f-1-i}, \sigma_{2f-1-i}\} = \{0, p\}$. However, in this case, we know that $\varepsilon'_{i-1} = \varepsilon'_{i}$, i.e. $\varepsilon'_{i-1} = 1$. In all cases, we can then conclude that $0 \le s_i - \varepsilon'_{i-1} \le p-1$. The case where $\varepsilon'_{i} = 0$ is treated similarly.

From Eq. (20), we then deduce that $c_i = s_i - \varepsilon'_{i-1}$ for all $i$ except possibly if $c_i = 0$ for all $i$ (i.e. $\gamma = \gamma'$), in which case the option $s_i - \varepsilon'_{i-1} = p-1$ for all $i$ is left open. On the one hand, when $c_i = s_i - \varepsilon'_{i-1}$, we check by inspection that $c_i$ are $r_i$ are related by the rules of the table (9) as expected. On the other hand, when $c_i = 0$ and $s_i - \varepsilon'_{i-1} = p-1$ for all $i$, one proves by induction that either $r_i = \varepsilon'_{i} = 0$ for all $i$, or $r_i = p-1$ and $\varepsilon'_{i} = 1$ for all $i$. In both cases, we verify that the rules of the table (9) are respected.

It remains to check that Eq. (19) holds. For this, we observe that the congruence defining the $(h, \gamma, \gamma')$-compatibility of $\sigma$ can be rewritten as follows:

$$ \frac{1}{q+1} \left( h - \sum_{i=0}^{f-1} (\sigma_{i+f} - \sigma_i) p^{f-1-i} \right) \equiv \gamma' + \sum_{i=0}^{f-1} \sigma_i p^{f-1-i} \pmod{q-1}. $$

Noticing in addition that

$$ \sigma_{i+f} - \sigma_i = (-1)^{\varepsilon_{f-1-i}} \cdot (1 + r_{f-1-i}) \\ \text{and} \\ \sigma_i = \varepsilon_{f-1-i} \cdot (1 + r_{f-1-i}) + \varepsilon'_{f-1-i} \cdot (p-1-r_{f-1-i}) $$
for all $i \in \{0, \dots, f-1\}$, we end up with the relation:

$$ (21) \qquad \begin{aligned} s &\equiv \frac{1}{q+1} \left( h - \sum_{i=0}^{f-1} (-1)^{\varepsilon_i} (1+r_i) p^i \right) - \sum_{i=0}^{f-1} \varepsilon_i (1+r_i) p^i \\ &\equiv \gamma' + \sum_{i=0}^{f-1} \varepsilon'_i (p-1-r_i) p^i \quad (\text{mod } q-1) \end{aligned} $$

which is exactly what we had to prove.

**Proposition 4.1.4.** — The mapping $S_\Sigma : \Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')} \to \mathcal{D}(t, \bar{p})$ is surjective.

*Proof.* — Let $(s, \underline{r})$ be the parameters of a Serre weight in $\mathcal{D}(t, \bar{p})$ and write $\underline{r} = (r_0, \dots, r_{f-1})$. By definition of $\mathcal{D}(\bar{p})$ and $\mathcal{D}(t)$, there exists $\varepsilon_0, \dots, \varepsilon_{f-1}, \varepsilon'_0, \dots, \varepsilon'_{f-1}$ in $\{0, 1\}$ satisfying the congruences (21). For $i$ in $\{0, \dots, f-1\}$, we set $\varepsilon_{i+f} = 1 - \varepsilon_i$ and $\varepsilon'_{i+f} = \varepsilon_i$. We further extend the sequences $(\varepsilon_i)_i$ and $(\varepsilon'_i)_i$ to all $i$ in $\mathbb{Z}$ by $(2f)$-periodicity. For all $i \in \mathbb{Z}$, we put:

$$ \sigma_i = \varepsilon_{f-1-i} \cdot (1+r_{f-1-i}) + \varepsilon'_{f-1-i} \cdot (p-1-r_{f-1-i}). $$

Obviously the sequence $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$ lies in $\Sigma$. We claim that it is actually an element of $\Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')}$, whose image under $S_\Sigma$ equals $\sigma_{s,\underline{\sigma}}$. The fact that $\underline{\sigma}$ is $(h, \gamma, \gamma')$-compatible is proved by doing in the reverse direction the final computation of the proof of Proposition 4.1.3. In order to check that $\underline{\sigma}$ is active, we build the following table in which we record the values of the pair $(\sigma_i, \sigma_{i+f})$ depending on the values of $\varepsilon_{f-1-i}$ and $\varepsilon'_{f-1-i}$.

<table><thead><tr><th>(<i>σ</i><sub><i>i</i></sub>, <i>σ</i><sub><i>i</i>+<i>f</i></sub>)</th><th><i>ε</i><sub><i>f</i>-1-i</sub> = 0</th><th><i>ε</i><sub><i>f</i>-1-i</sub> = 1</th></tr></thead><tbody><tr><td><i>ε</i>'<sub><i>f</i>-1-i</sub> = 0</td><td>(0, 1+r<sub><i>f</i>-1-i</sub>)</td><td>(1+r<sub><i>f</i>-1-i</sub>, 0)</td></tr><tr><td><i>ε</i>'<sub><i>f</i>-1-i</sub> = 1</td><td>(<i>p</i>-1-r<sub><i>f</i>-1-i</sub>, <i>p</i>)</td><td>(<i>p</i>, <i>p</i>-1-r<sub><i>f</i>-1-i</sub>)</td></tr></tbody></table>

We observe that, for each case, both coordinates are between 0 and $p$, they cannot be equal and one of them is equal to 0 or $p$. Hence the pair $(\sigma_i, \sigma_{i+f})$ is active in the sense of Definition 4.1.1. Since this holds for all $i$, we conclude that $\underline{\sigma} \in \Sigma^{\text{ac}}$.

Finally, looking again at the above table, we deduce that the values of $r_{f-1-i}$ and $\varepsilon_{f-1-i}$ can be recovered from the pair $(\sigma_i, \sigma_{i+f})$ thanks to the formulas (15) on the one hand and the fact that $\varepsilon_{f-1-i} = 0$ if and only if $\sigma_i < \sigma_{i+f}$ on the other hand. This observation eventually ensures that $S_\Sigma$ takes $\underline{\sigma}$ to the Serre weight with parameters $(s, \underline{r})$ we started with. □

**4.1.2. Nonviable genes.** — As a first application of Propositions 4.1.3 and 4.1.4, we prove that if $\mathcal{X}$ is not viable (see Definition 1.4.5), then the set of common Serre weights is empty. We start by recording a lemma that we shall use several times in what follows.

**Lemma 4.1.5.** — Let $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}}$ be in $\Sigma^{\text{ac}} \cap \Sigma^{(h,\gamma,\gamma')}$ and $i$ be in $\mathbb{Z}$. We assume $\sigma_i \in \{0, p\}$. Then $X_i \neq 0$.

*Proof.* — The compatibility condition tells us that $\alpha_i \equiv \beta_i \pmod{q-1}$ where $\beta_i$ is defined by:

$$ \beta_i = \left\lfloor \sum_{j=1}^{f} \frac{q\sigma_{i+j} + \sigma_{i+j+f}}{q+1} p^{f-1-j} \right\rfloor. $$

From the activity condition, we deduce that $q\sigma_{i+j} + \sigma_{i+j+f} < p \cdot (q+1)$ for all $j$. We then find $0 \le \beta_i < 1 + p + \dots + p^{f-1}$, from what it follows $X_i \neq 0$. □
**Corollary 4.1.6.** — If the gene $\mathbb{X}$ is not viable, then $\mathcal{D}(t, \bar{p})$ is empty.

*Proof.* — By Proposition 4.1.4, it is enough to prove that $\Sigma^{ac} \cap \Sigma^{(h,\gamma,\gamma')} = \emptyset$. Arguing by contradiction, let us consider $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}} \in \Sigma^{ac} \cap \Sigma^{(h,\gamma,\gamma')}$. From our assumption, we know that there exists an index $i$ such that $X_i = X_{i+f} = 0$. From Lemma 4.1.5, it then follows that both $\sigma_i$ and $\sigma_{i+f}$ do not belong to $\{0, p\}$, which contradicts the definition of activity. $\square$

Theorem 2.3.1 follows from Corollary 4.1.6 when $\mathbb{X}$ is not viable (since $\mathcal{W}(\mathbb{X})$ is then empty by definition). The case of viable genes is more complicated; it is covered in the next subsections.

**4.2. Description of $\Sigma^{ac} \cap \Sigma^{(h,\gamma,\gamma')}$.** — In this subsection, we give a complete description of the set $\Sigma^{ac} \cap \Sigma^{(h,\gamma,\gamma')}$ in terms of a novel combinatorial datum, that we call enriched weights. The link between enriched weights and combinatorial weights as defined in §2.1 is precised in §4.3.

**4.2.1. Mutations.** — We recall that to any coherent triple $(h, \gamma, \gamma')$, we have associated in §1.3 a sequence $\underline{v} = (v_i)_{i \in \mathbb{Z}} \in \Sigma$ such that:

$$h - (q+1)\gamma' \equiv \sum_{i=0}^{2f-1} v_i p^{2f-1-i} \pmod{q^2-1}$$

In other words, $\underline{v}$ is $(h, \gamma, \gamma')$-compatible. Even better, it is the unique sequence in $\Sigma^{(h,\gamma,\gamma')}$ assuming values in $\{0, \dots, p-1\}$. In order to describe all sequences in $\Sigma^{(h,\gamma,\gamma')}$, we introduce the mutation operators. Given $\underline{\chi} = (\chi_i)_{i \in \mathbb{Z}}$ in $\Sigma$, we define:

$$\begin{array}{rcl} \underline{\mu}_{\underline{\chi}} & : & \Sigma \longrightarrow \Sigma \\ (\sigma_i)_{i \in \mathbb{Z}} & \mapsto & (\sigma_i - \chi_i + p\chi_{i-1})_{i \in \mathbb{Z}} \end{array}$$

One readily checks that $\underline{\mu}_{\underline{\chi}} \circ \underline{\mu}_{\underline{\chi}'} = \underline{\mu}_{\underline{\chi}+\underline{\chi}'}$ for all $\underline{\chi}, \underline{\chi}' \in \Sigma$. In other words, the association $\underline{\chi} \mapsto \underline{\mu}_{\underline{\chi}}$ defines a group homomorphism. In particular, the $\underline{\mu}_{\underline{\chi}}$'s pairwise commute.

**Proposition 4.2.1.** — A sequence $\underline{\sigma}$ in $\Sigma$ lies in $\Sigma^{(h,\gamma,\gamma')}$ if and only if there exists $\underline{\chi}$ in $\Sigma$ such that $\underline{\sigma} = \underline{\mu}_{\underline{\chi}}(\underline{v})$. Moreover, when this occurs, $\underline{\chi}$ is uniquely determined.

*Proof.* — We consider $\underline{\sigma} \in \Sigma$. Solving a linear system, we find that $\underline{\sigma} = \underline{\mu}_{\underline{\chi}}(\underline{v})$ is equivalent to:

$$\chi_i = \frac{1}{q^2-1} \sum_{j=0}^{2f-1} (\sigma_{i+j} - v_{i+j}) p^{2f-1-j} \quad (i \in \mathbb{Z}).$$

The proposition follows easily from this. $\square$

We aim at describing all the sequences $\underline{\sigma}$ which are at the same time $(h, \gamma, \gamma')$-compatible and active. By Proposition 4.2.1, this amounts to characterize the $\underline{\chi}$'s such that $\underline{\mu}_{\underline{\chi}}(\underline{v})$ is active. The starting point is the following simple lemma that narrows the field of possibilities.

**Lemma 4.2.2.** — If $\underline{\mu}_{\underline{\chi}}(\underline{v})$ is active, then $\underline{\chi}$ assumes values in $\{0, 1\}$.

*Proof.* — Set $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}} = \underline{\mu}_{\underline{\chi}}(\underline{v})$. By assumption, $\sigma_i = v_i - \chi_i + p\chi_{i-1} \in [0, p]$ for all $i$. Let $i_0$ be the index for which $\chi_i$ is maximal. Then:

$$p \ge \sigma_{i_0+1} = v_{i_0+1} - \chi_{i_0+1} + p\chi_{i_0} \ge v_{i_0} + (p-1)\chi_{i_0} \ge (p-1)\chi_{i_0}.$$
We deduce that $\chi_{i_0} \le 1$ and then, that $\chi_i \le 1$ for all $i$. We prove similarly that $\chi_i$ is always nonnegative, showing the lemma. $\square$

**4.2.2. Enriched weights.** — Instead of working with the sequence $\chi$, it is convenient to slightly re-encode it. For this, we introduce the notion of *enriched weights*.

**Definition 4.2.3.** — An enriched weight of length $f$ is a periodic sequence of period $2f$ assuming values in the finite set $\{\mathbf{a}, \mathbf{b}\}$.

We introduce the function $\lambda : \{\mathbf{A}, \mathbf{B}, \mathbf{AB}, \mathbf{O}\} \to \{\mathbf{a}, \mathbf{b}\}$ defined by $\lambda(\mathbf{A}) = \lambda(\mathbf{AB}) = \mathbf{a}$ and $\lambda(\mathbf{B}) = \lambda(\mathbf{O}) = \mathbf{b}$. Notice that the equality $\lambda(X) = \lambda(Y)$ is equivalent to $X \sim Y$ where $\sim$ is the equivalence relation introduced in §2.3. To a numerical sequence $\chi = (\chi_i)_{i \in \mathbb{Z}}$ assuming values in $\{0, 1\}$, we associate the enriched weight $\hat{w} = (\hat{w}_i)_{i \in \mathbb{Z}}$ which is uniquely determined by the following condition: for all $i \in \mathbb{Z}$, $\chi_i = 1$ if and only if $\hat{w}_i = \lambda(X_i)$. More concretely, the following table shows what is the value of $\hat{w}_i$ in terms of $\chi_i$ and $X_i$:

$$ (22) \qquad \begin{array}{|c|c|c|} \hline \chi_i \in \{\mathbf{A}, \mathbf{AB}\} & X_i \in \{\mathbf{B}, \mathbf{O}\} & X_i \in \{\mathbf{A}, \mathbf{B}\} \\ \hline \chi_i = 0 & \mathbf{b} & \mathbf{a} \\ \hline \chi_i = 1 & \mathbf{a} & \mathbf{b} \\ \hline \end{array} $$

There is obviously a bijection between the set of enriched weights and the set of $\chi$'s. We are now going to translate the activity condition (introduced in Definition 4.1.1) at the level of enriched weights. For convenience, we introduce the following definition.

**Definition 4.2.4.** — An enriched weight $\hat{w}$ is called $(h, \gamma, \gamma')$-active (or just active if no confusion may arise) if the sequence $\mu_{\chi}(\underline{v})$ lies in $\Sigma^{ac}$ (where $\chi$ denotes as usual the numerical sequence associated to $\hat{w}$).

We denote by $\hat{W}(h, \gamma, \gamma')$ the set of $(h, \gamma, \gamma')$-active enriched weights.

Our goal is now to characterize active enriched weights.

**Lemma 4.2.5.** — Let $\hat{w}$ be an enriched weight and let $\chi$ be the numerical sequence associated to it. Set $\underline{\sigma} = (\sigma_i)_{i \in \mathbb{Z}} = \mu_{\chi}(\underline{v})$. Then, for all $i$ in $\mathbb{Z}$, the following holds:

(i) if $\hat{w}_i = \mathbf{a}$, then $p$ does not divide $\sigma_i$;

(ii) if $\hat{w}_i = \mathbf{b}$ and $X_i \neq \mathbf{0}$, then $\sigma_i \in \{0, p\}$.

*Proof.* — We assume $\hat{w}_i = \mathbf{a}$. Looking up at the above table, we deduce that either $\chi_i = 0$ and $X_i \in \{\mathbf{B}, \mathbf{O}\}$ or $\chi_i = 1$ and $X_i \in \{\mathbf{A}, \mathbf{AB}\}$. In the first case, from Lemma 1.3.3, we find that $v_i \in \{1, \dots, p-1\}$. In the second case, we obtain $v_i = 0$. In both cases, it turns out that $v_i - \chi_i$ cannot be divisible by $p$. Hence $\sigma_i = v_i - \chi_i + p\chi_{i-1}$ is not divisible by $p$ either. This proves (i).

Let us now assume $\hat{w}_i = \mathbf{b}$ and $X_i \neq \mathbf{0}$. Then looking up again at the table, we are faced to the following alternative: either $\chi_i = 0$ and $X_i \in \{\mathbf{A}, \mathbf{AB}\}$ or $\chi_i = 1$ and $X_i = \mathbf{B}$. In both cases, Lemma 1.3.3 shows that $\chi_i = v_i$. Hence $\sigma_i = p\chi_{i-1}$, from which (ii) follows. $\square$

After Lemma 4.2.5, we have:

**Corollary 4.2.6.** — If $\hat{w}$ is an active enriched weight, then $(\hat{w}_i, \hat{w}_{i+f}) \neq (\mathbf{a}, \mathbf{a})$ for all $i$.

We now come to the core proposition which characterizes active enriched weights “outside $\mathbf{O}$”.
**Proposition 4.2.7.** — Let $\hat{w} = (\hat{w}_i)_{i \in \mathbb{Z}}$ be an enriched weight with $(\hat{w}_i, \hat{w}_{i+f}) \neq (\mathbf{a}, \mathbf{a})$ for all $i$. Let $\chi$ be the numerical sequence associated to it and set $\sigma = (\sigma_i)_{i \in \mathbb{Z}} = \mu_{\chi}(\underline{v})$. Let $i$ be an integer with $X_i \neq 0$ and $X_{i+f} \neq 0$. Then the pair $(\sigma_i, \sigma_{i+f})$ is active if and only if the following holds:

(bb1) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{b})$ and $\lambda(X_{i-1}) = \lambda(X_{i-1+f})$, then $\hat{w}_{i-1} \neq \hat{w}_{i-1+f}$;

(bb2) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{b})$ and $\lambda(X_{i-1}) \neq \lambda(X_{i-1+f})$, then $\hat{w}_{i-1} = \hat{w}_{i-1+f}$;

(ab1) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{a}, \mathbf{b})$ and $\lambda(X_i) = \lambda(X_{i-1})$, then $\hat{w}_{i-1} = \mathbf{a}$;

(ab2) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{a}, \mathbf{b})$ and $\lambda(X_i) \neq \lambda(X_{i-1})$, then $\hat{w}_{i-1} = \mathbf{b}$;

(ba1) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{a})$ and $\lambda(X_{i+f}) = \lambda(X_{i-1+f})$, then $\hat{w}_{i-1+f} = \mathbf{a}$;

(ba2) if $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{a})$ and $\lambda(X_{i+f}) \neq \lambda(X_{i-1+f})$, then $\hat{w}_{i-1+f} = \mathbf{b}$.

**Proof.** — We first assume that $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{b})$. It then follows from Lemma 4.2.5 that both $\sigma_i$ and $\sigma_{i+f}$ lie in $\{0, p\}$. As a consequence, the pair $(\sigma_i, \sigma_{i+f})$ is active if and only if $\sigma_i \neq \sigma_{i+f}$, which is further equivalent to $\chi_{i-1} \neq \chi_{i-1+f}$. Looking up at table (22), we finally obtain the necessary and sufficient conditions (bb1) and (bb2).

Let us now assume $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{a}, \mathbf{b})$. From Lemma 4.2.5, we deduce that $\sigma_{i+f} \in \{0, p\}$ whereas $p$ does not divide $\sigma_i$. Consequently, the pair $(\sigma_i, \sigma_{i+f})$ is active if and only if $1 \le \sigma_i \le p$ regardless the value of $\sigma_{i+f}$. Since $\sigma_i = v_i - \chi_i + p\chi_{i-1}$ and $v_i \in \{0, 1\}$ (by Lemma 1.3.3), this happens if and only if $\chi_{i-1} = \chi_i$, which is further equivalent to the conditions (ab1) and (ab2) thanks to the records of table (22).

Finally, the case $(\hat{w}_i, \hat{w}_{i+f}) = (\mathbf{b}, \mathbf{a})$ is handled similarly. $\square$

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

It now remains to understand the activity condition at positions where the letter 0 appears in the gene. This is the content of the following proposition.

**Proposition 4.2.8.** — Let $\hat{w} = (\hat{w}_i)_{i \in \mathbb{Z}}$ be an enriched weight. Let $\chi$ be the numerical sequence associated to it and set $\sigma = (\sigma_i)_{i \in \mathbb{Z}} = \mu_{\chi}(\underline{v})$. Then $\hat{w}$ is active if and only if:

(a) for all $i$ such that $X_i \neq 0$ and $X_{i+f} \neq 0$, the pair $(\sigma_i, \sigma_{i+f})$ is active, and

(b) for all $i$ such that $X_i = 0$, we have $\hat{w}_{i-1} \neq \lambda(X_{i-1})$ and $\hat{w}_{i+f} = \mathbf{b}$.

**Proof.** — We first assume that $\hat{w}$ is active. Then (a) is clearly true. We now consider an index $i$ such that $X_i = 0$. From Lemma 4.1.5, we deduce that both $v_i$ and $\sigma_i$ are different from 0 and $p$, i.e. $v_i, \sigma_i \in [1, \dots, p-1]$. It follows that $|\sigma_i - v_i| \le p-2$. Since we have the equality $\sigma_i = v_i - \chi_i + p\chi_{i-1}$, we deduce that:

$$|p\chi_{i-1}| \le |\sigma_i - v_i| + |\chi_i| \le p-1.$$

Therefore $\chi_{i-1}$ has to vanish, implying by definition that $\hat{w}_{i-1} \neq \lambda(X_{i-1})$. Moreover, from the activity of the pair $(\sigma_i, \sigma_{i+f})$, we derive that $\sigma_{i+f} = v_{i+f} - \chi_{i+f} + p\chi_{i+f-1} \in \{0, p\}$. Hence $\chi_{i+f} \equiv v_{i+f} \pmod{p}$, which gives $\chi_{i+f} = v_{i+f}$ since both $\chi_{i+f}$ and $v_{i+f}$ are in the range $[0, p-1]$. Looking up at table (22), we finally deduce that $\hat{w}_{i+f} = \mathbf{b}$. We have then proved (b).

Conversely, let us assume the conditions (a) and (b). We need to prove that the pair $(\sigma_i, \sigma_{i+f})$ is active as soon as $X_i = 0$ or $X_{i+f} = 0$. Since replacing $i$ by $i+f$ leaves unchanged the activity condition, we may assume without loss of generality that $X_i = 0$. Combining the assumption (b) with Lemma 1.3.3, we derive $\chi_{i-1} = 0$ and $\chi_{i+f} = v_{i+f}$. Thus $\sigma_i = v_i - \chi_i$ and $\sigma_{i+f} = p\chi_{i+f-1}$. Hence $0 \le \sigma_i \le p-1$ and $\sigma_{i+f} \in \{0, p\}$. It is enough to exclude the option $\sigma_i = 0$. For this, we cannot apply directly Lemma 4.1.5 because we do not know that $\sigma$ is active (it is actually what we want to prove); however we can mostly reuse the same argument. Indeed, looking at the proof of Lemma 4.1.5, we see that the conclusion follows if we can ensure that $q\sigma_{i+j} + \sigma_{i+j+f} < p \cdot (q+1)$ for all integer $j$. If $X_{i+j} \neq 0$ and $X_{i+j+f} \neq 0$, this is a consequence of the activity condition (as already
noticed in the proof of Lemma 4.1.5). If $X_{i+j} = 0$, we have just proved that $\sigma_{i+j} < p$ and $\sigma_{i+j+f} = p\chi_{i+j+f-1} \le p$. Hence $q\sigma_{i+j} + \sigma_{i+j+f} < p \cdot (q+1)$ as wanted. Similarly if $X_{i+j+f} = 0$, we have $\sigma_{i+j} = p\chi_{i+j-1} \le p$ and $\sigma_{i+j+f} < p$, so the same conclusion follows. $\square$

**4.2.3. Fragmentation and description of active enriched weights.** — Propositions 4.2.7 and 4.2.8 together entirely elucidate the activity condition for enriched weights. Besides, Proposition 4.2.8 shows that the activity condition can be checked independently on each fragment of the gene as defined in §2.1. In order to be more precise, we introduce the following definition.

**Definition 4.2.9.** — A fragmentary enriched weight of length $\ell$ is a tuple $\hat{w} = (\hat{w}_0, \dots, \hat{w}_{\ell-1})$ with $\hat{w}_i = (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) \in \{\mathbf{a}, \mathbf{b}\}^2$ for all $i \in \{0, 1, \dots, \ell-1\}$.

Let $\underline{F} = (F_0, \dots, F_{\ell-1})$ be a fragment of length $\ell$ with $F_i = (F_i^\uparrow, F_i^\downarrow)$. We say that $\hat{w}$ is a fragmentary enriched weight of $\underline{F}$ if

$$ (L) \text{ if } F_0^\uparrow = 0 \text{ (resp. } F_0^\downarrow = 0\text{), then } \hat{w}_0^\uparrow = \mathbf{b} \text{ (resp. } \hat{w}_0^\downarrow = \mathbf{b}) $$

$$ \begin{array}{l} \text{(R) if } F_{\ell-1}^\uparrow = \mathbf{AB} \text{ (resp. } F_{\ell-1}^\downarrow = \mathbf{AB}\text{), then } \hat{w}_{\ell-1}^\uparrow = \mathbf{b} \text{ (resp. } \hat{w}_{\ell-1}^\downarrow = \mathbf{b}) \\ \text{if } \ell = 1 \text{ and } F_0^\uparrow \in \{\mathbf{A}, \mathbf{B}\} \text{ (and thus } F_0^\uparrow = 0\text{), then } \hat{w}_0^\uparrow = \mathbf{a} \\ \text{if } \ell = 1 \text{ and } F_0^\downarrow \in \{\mathbf{A}, \mathbf{B}\} \text{ (and thus } F_0^\downarrow = 0\text{), then } \hat{w}_0^\downarrow = \mathbf{a} \end{array} $$

and, for all $i \in \{1, \dots, \ell-1\}$:

$$ (aa) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) \neq (\mathbf{a}, \mathbf{a}) $$

$$ (bb_1) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{b}, \mathbf{b}) \text{ and } \lambda(F_{i-1}^\uparrow) = \lambda(F_{i-1}^\downarrow), \text{ then } \hat{w}_{i-1}^\uparrow \neq \hat{w}_{i-1}^\downarrow, $$

$$ (bb_2) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{b}, \mathbf{b}) \text{ and } \lambda(F_{i-1}^\uparrow) \neq \lambda(F_{i-1}^\downarrow), \text{ then } \hat{w}_{i-1}^\uparrow = \hat{w}_{i-1}^\downarrow, $$

$$ (ab_1) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{a}, \mathbf{b}) \text{ and } \lambda(F_i^\uparrow) = \lambda(F_{i-1}^\uparrow), \text{ then } \hat{w}_{i-1}^\uparrow = \mathbf{a}, $$

$$ (ab_2) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{a}, \mathbf{b}) \text{ and } \lambda(F_i^\uparrow) \neq \lambda(F_{i-1}^\uparrow), \text{ then } \hat{w}_{i-1}^\uparrow = \mathbf{b}, $$

$$ (ba_1) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{b}, \mathbf{a}) \text{ and } \lambda(F_i^\uparrow) = \lambda(F_{i-1}^\uparrow), \text{ then } \hat{w}_{i-1}^\uparrow = \mathbf{a}, $$

$$ (ba_2) \text{ if } (\hat{w}_i^\uparrow, \hat{w}_i^\downarrow) = (\mathbf{b}, \mathbf{a}) \text{ and } \lambda(F_i^\uparrow) \neq \lambda(F_{i-1}^\uparrow), \text{ then } \hat{w}_{i-1}^\uparrow = \mathbf{b}. $$

We denote by $\hat{W}(\underline{F})$ the set of all fragmentary enriched weights of $\underline{F}$.

After Propositions 4.2.7 and 4.2.8, we obtain:

**Proposition 4.2.10.** — We have:

$$ \hat{W}(h, \gamma, \gamma') \approx \prod_{\underline{F}} \hat{W}(\underline{F}) $$

where the product runs of all fragments $\underline{F}$ of $\underline{X}$.

Proposition 4.2.10 shows in particular that the set $\hat{W}(h, \gamma, \gamma')$ depends only on the gene $\underline{X}$. In what follows, we will often denote it by $\hat{W}(\underline{X})$. Besides, describing $\hat{W}(\underline{X})$ reduces to compute the sets $\hat{W}(\underline{F})$. This can actually be easily achieved by induction on $i$ as stated in the following proposition.
and 2.1.6. Precisely, we are going to prove that the map $\mathcal{S}$ considered in Theorem 2.3.1 and the map $\hat{\mathcal{S}}$ introduced above sit in a commutative diagram of the form:

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

where $\mathcal{X}$ denotes the gene of $(h, \gamma, \gamma')$. The vertical map $\Delta$ is defined as follows: it takes an enriched weight $\hat{w} = (\hat{w}_i)_{i \in \mathcal{Z}}$ to the combinatorial weight:

$$ \Delta(\hat{w}) = (\delta(\hat{w}_i, \hat{w}_{i+f}))_{i \in \mathcal{Z}} $$

where the $\delta$ function is defined by:

$$ \delta(x, y) = 1 \quad \text{if } x = y $$

$$ \delta(x, y) = 0 \quad \text{otherwise.} $$

The fact that $\Delta$ takes $\hat{W}(h, \gamma, \gamma')$ to $W(\mathcal{X})$ follows from Propositions 4.2.10 and 4.2.11. Moreover, we deduce from the constructions that $\Delta$ is surjective.

Before getting to the heart of the matter, we underline that the $\delta$ notation allows us to write down a simple formula summarizing the table (22), that is:

$$ (23) \qquad \chi_i = \delta(\hat{w}_i, \lambda(X_i)) $$

where $(\hat{w}_i)_{i \in \mathcal{Z}}$ is an enriched weight and $(\chi_i)_{i \in \mathcal{Z}}$ is its associated numerical sequence. Similarly, the parameter $\delta_i$, which appears in the table of Figure 1, is simply equal to $\delta(\lambda(X_i), \lambda(X_{i+f}))$. Another useful remark on the $\delta$ function is given by the next lemma.

**Lemma 4.3.1.** — If $E$ is a set with two elements and $x_1, x_2, y_1$ and $y_2$ are elements of $E$, we have the identity:

$$ (24) \qquad \delta(\delta(x_1, x_2), \delta(y_1, y_2)) = \delta(\delta(x_1, y_1), \delta(x_2, y_2)). $$

*Proof.* — Without loss of generality, we may take $E = \{0, 1\}$. With this further assumption, the congruence $\delta(x, y) = x + y + 1 \pmod 2$ holds for all $x, y$ in $E$. Therefore, the left hand side and the right hand side of (24) are both congruent to $x_1 + x_2 + y_1 + y_2 + 1 \pmod 2$. Since they both belong to $E$, they need to be equal. $\square$

**Proposition 4.3.2.** — We have $\hat{\mathcal{S}} = \mathcal{S} \circ \Delta$.

*Proof.* — Let $\hat{w} = (\hat{w}_i)_{i \in \mathcal{Z}}$ be an enriched weight in $\hat{W}(h, \gamma, \gamma')$, let $(\chi_i)_{i \in \mathcal{Z}}$ be the associated sequence and set $\underline{\sigma} = (\sigma_i)_{i \in \mathcal{Z}} = \mu_{\underline{\chi}}(\underline{v})$. Let further $(s, \underline{r})$ be the parameters of the Serre weight $\hat{\mathcal{S}}(\hat{w})$. As usual, we write $\underline{r} = (r_0, \dots, r_{f-1})$ and define $r_i = r_i \bmod f$ for $i$ in $\mathcal{Z}$. We let $\varepsilon'_0, \dots, \varepsilon'_{f-1}$ in $\{0, 1\}$ be the parameters describing the Serre weight $\hat{\mathcal{S}}(\hat{w})$ inside $\mathcal{D}(\mathcal{T})$ (see §1.2 for more details). By Remark 1.2.5, we know that they are uniquely determined. By the proof of Proposition 4.1.3, we even have a formula for their values. In particular, when $\{\sigma_i, \sigma_{i+f}\} \neq \{0, p\}$, we have $\varepsilon'_{f-1-i} = 0$ if $\sigma_i = 0$ or $\sigma_{i+f} = 0$ and $\varepsilon'_{f-1-i} = 1$ otherwise.

We first focus on the parameter $\mathcal{Z}$: we fix an index $i$ in $\{0, \dots, f-1\}$ and aim at proving that $r_{f-1-i}$ is given by the rules of the table of Figure 1. To start with, we consider the case where $X_i = 0$. By Proposition 4.2.8, we know that $\hat{w}_{i-1} \neq \lambda(X_{i-1})$ and $\hat{w}_{i+f} = \mathfrak{b}$. These properties allow us to find the values of $\chi_{i-1}$ and $\chi_i$. Indeed, after (23), it is clear that the former one means that $\chi_{i-1} = 0$ whereas the latter one gives $\chi_i = w_i$ since $\hat{w}_{i+f} = \lambda(X_i) = \mathfrak{b}$. Consequently $\sigma_i = v_i - w_i$. Besides, since $X_{i+f} \neq 0$ and $\hat{w}_{i+f} = \mathfrak{b}$, the proof of Lemma 4.2.5 indicates that $\sigma_{i+f} = p\chi_{i+f-1}$. Applying Lemma 4.3.1 with the inputs $x_1 = \hat{w}_{i+f-1}$, $x_2 = \lambda(X_{i+f-1})$, $y_1 = \hat{w}_{i-1}$ and $y_2 = \lambda(X_{i-1})$, we find moreover that
the condition $\chi_{i+f-1} = 0$ is equivalent to $w_{i-1} = \delta_{i-1}$. Putting all together and coming back to the definition of $S_\Sigma$ (see in particular Eq. (15), page 31), we find that:

$$r_{f-1-i} = v_i - w_i - 1 \quad \text{if } w_{i-1} = \delta_{i-1},$$

$$r_{f-1-i} = p - 1 - v_i + w_i \quad \text{if } w_{i-1} \neq \delta_{i-1}$$

as recorded in the table of Figure 1. We have then proved that the value of $r_{f-1-i}$ is correct when $X_i = 0$. In this setting, we can moreover determine the value of $\epsilon'_{f-1-i}$ (which will be useful for later use). Indeed, from Lemma 4.1.5, we deduce that $\sigma_i \notin \{0, p\}$. As a consequence, we can find the value of $\epsilon'_i$ using the recipe we have recalled earlier; in our setting, we obtain $\epsilon'_{f-1-i} = \chi_{i+f-1}$, that is:

$$\epsilon'_{f-1-i} = 0 \quad \text{if } w_{i-1} = \delta_{i-1},$$

$$\epsilon'_{f-1-i} = 1 \quad \text{if } w_{i-1} \neq \delta_{i-1}.$$

The case where $X_{i+f} = 0$ is treated similarly. We then move to the case where $X_i \neq 0$ and $X_{i+f} \neq 0$. If $w_i = 1$, we must have $\hat{w}_i = \hat{w}_{i+f} = b$ thanks to Corollary 4.2.6. From Lemma 4.2.5, it then follows that $\{\sigma_i, \sigma_{i+f}\} = \{0, p\}$ and hence $r_{f-1-i} = p-1$. This again agrees with the table of Figure 1. It remains to examine the case where $w_i = 0$. By symmetry, one may assume that $\hat{w}_i = a$ and $\hat{w}_{i+f} = b$. In this setting, we have $\sigma_i = v_i - \chi_i + p\chi_{i-1}$ and $\sigma_{i+f} = p\chi_{i+f-1}$. Moreover $v_i$ and $\chi_i$ are both in $\{0, 1\}$ (see Lemma 1.3.3) and $v_i - \chi_i$ is not divisible by $p$ (see Lemma 4.2.5). Hence, we must have $v_i = 1 - \chi_i$ and we get $\sigma_i = 1 - 2\chi_i + p\chi_{i-1}$. Since $\sigma_i$ must be in addition between 0 and $p$, we find that $\chi_i = \chi_{i-1}$ necessarily. So $\sigma_i = 1 + (p-2)\chi_{i-1}$. A simple calculation then shows that $r_{f-1-i} = 0$ if $\chi_{i-1} = \chi_{i+f-1}$ and $r_{f-1-i} = p-2$ otherwise. Finally, applying Lemma 4.3.1 with the inputs $x_1 = \hat{w}_{i+f-1}$, $x_2 = \lambda(X_{i+f-1})$, $y_1 = \hat{w}_{i-1}$ and $y_2 = \lambda(X_{i-1})$, we find that the condition $\chi_{i+f-1} = \chi_{i-1}$ is equivalent to $w_{i-1} = \delta_{i-1}$. The result of our computations then again agrees with the table of Figure 1.

To summarize, we have proved the tuple $\underline{r}$ is correct in all cases. It remains to prove that $s$ is correct, i.e. that it is given by the recipe presented at the beginning of §2.3. By the second part of Lemma 1.2.4, it is sufficient to show that $\epsilon_{i_0}$ is correct. This follows from the computation we have carried out earlier when $X_{i_0} = 0$. When $c_{i_0} \neq \frac{p-1}{2}$, this follows by looking at the table of Figure 1. $\square$

Proposition 4.3.2 shows that $S$ takes its values in $\mathcal{D}(t, \bar{p})$ (since $\Delta$ is surjective) on the one hand, and that $S$ is surjective onto $\mathcal{D}(t, \bar{p})$ (since $S_{\mathcal{W}}$ is surjective) on the other hand. It then only remains to prove that $S$ is injective. It is the content of the next proposition, which concludes the proof of Theorem 2.3.1.

**Proposition 4.3.3.** — The mapping $S: W(\mathbb{X}) \to \mathcal{D}(t, \bar{p})$ is injective.

*Proof.* — We consider $\underline{w} = (w_i)_{i \in \mathbb{Z}}$ and $\underline{w}' = (w'_i)_{i \in \mathbb{Z}}$ in $W(\mathbb{X})$ and assume that $S(\underline{w}) = S(\underline{w}')$. We denote by $s$ and $\underline{r} = (r_0, \dots, r_{f-1})$ the parameters of this Serre weight. Let $i$ be in $\{0, \dots, f-1\}$. If $X_i = 0$ then it follows from the definition of $S$ that:

$$r_{f-1-i} = v_i - w_i - 1 \quad \text{if } w_{i-1} = \delta_{i-1},$$

$$r_{f-1-i} = p - 1 - v_i + w_i \quad \text{if } w_{i-1} \neq \delta_{i-1}$$

where we recall that $\delta_{i-1} = \delta(\lambda(X_{i-1}, X_{i+f-1}))$. Of course, the same result holds when $w_{i-1}$ and $w_i$ are replaced by $w'_{i-1}$ and $w'_i$ respectively. Examining all options, we find that, if $w_i \neq w'_i$, we must have $v_i = \frac{p+1}{2}$ and $w_{i-1} \neq w'_{i-1}$ as well. Coming back to the proof of Proposition 4.3.2, we realize that the latter condition implies that the $\epsilon'_{f-1-i}$ associated to $w$ and $w'$ differ. This contradicts the fact that $S(\underline{w})$ and $S(\underline{w}')$ share the same $s$. Hence $w_i = w'_i$ when $X_i = 0$.
Obviously, the assumption $X_{i+f} = 0$ leads to the same conclusion that $w_i = w'_i$. To finish with, we need to examine the case where $X_i \neq 0$ and $X_{i+f} \neq 0$. In this situation we have $r_{f-1-i} \in \{w_i(p-1), p-2+w_i\}$ and similarly $r_{f-1-i} \in \{w'_i(p-1), p-2+w'_i\}$. These two sets must then meet, which is only possible when $w_i = w'_i$.

In conclusion, we have shown that $w_i = w'_i$ in all cases. Hence $\underline{w} = \underline{w}'$ and injectivity is established. $\square$

# Appendix A

## The case of degenerated genes

The object of this first appendix is to extend the results of §2 (including Theorem 2.3.1) to the case where the gene $X = (X_i)_{i \in \mathbb{Z}}$ is degenerate, i.e. when $X_i \ge 0$ for all $i$.

**A.1. Set of combinatorial weights associated to a gene.** — In this new setting, fragmentation no longer makes sense and the definition of $W(\mathbb{X})$ needs to be adapted. Precisely, we now need to define nine recursive sequence $(W_i^{\square, \square'})_{-1 \le i \le f-1}$ for $\square$ and $\square'$ varying in $\{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$. The initial values of these sequences are given by:

$$ \bullet \quad W_{-1}^{\square, \square'} = \emptyset \quad \text{if } \square \neq \square' \\ = \{(\, )\} \quad \text{otherwise} $$

where $(\,)$ denotes the empty tuple (which is the unique element of $\{0, 1\}^0$). The next values (for $0 \le i \le f-1$) are given by the formulas:

$$ \bullet \quad W_i^{\square, (\mathbf{b}, \mathbf{b})} = (W_{i-1}^{\square, (\mathbf{a}, \mathbf{b})} \cup W_{i-1}^{\square, (\mathbf{b}, \mathbf{a})}) \times \{1\} \quad \text{if } X_{i-1} = X_{i-1+f} \\ = W_{i-1}^{\square, (\mathbf{b}, \mathbf{b})} \times \{1\} \quad \text{otherwise} $$

$$ \bullet \quad W_i^{\square, (\mathbf{a}, \mathbf{b})} = W_{i-1}^{\square, (\mathbf{a}, \mathbf{b})} \times \{0\} \quad \text{if } X_i = X_{i-1} \\ = (W_{i-1}^{\square, (\mathbf{b}, \mathbf{a})} \cup W_{i-1}^{\square, (\mathbf{b}, \mathbf{b})}) \times \{0\} \quad \text{otherwise} $$

$$ \bullet \quad W_i^{\square, (\mathbf{b}, \mathbf{a})} = W_{i-1}^{\square, (\mathbf{b}, \mathbf{a})} \times \{0\} \quad \text{if } X_{i+f} = X_{i-1+f} \\ = (W_{i-1}^{\square, (\mathbf{a}, \mathbf{b})} \cup W_{i-1}^{\square, (\mathbf{b}, \mathbf{b})}) \times \{0\} \quad \text{otherwise.} $$

The set of combinatorial weights of $\mathbb{X}$ is finally defined by:

$$ W(\mathbb{X}) = W_{f-1}^{(\mathbf{b}, \mathbf{b}), (\mathbf{b}, \mathbf{b})} \cup W_{f-1}^{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})} \cup W_{f-1}^{(\mathbf{b}, \mathbf{a}), (\mathbf{a}, \mathbf{b})}. $$

**Example A.1.1.** — Let us consider the following simple gene:

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

The values of the sequences $(W_i^{\square, \square'})$ are recorded in the tables of Figure 2. From this calculation, we find that our gene has 2 combinatorial weights, which are $(0, 0)$ and $(1, 0)$ (both coming from $\square = (\mathbf{b}, \mathbf{a})$ and $\square' = (\mathbf{a}, \mathbf{b})$).
<table><thead><tr><th>W<sup>□,□'</sup><sub>-1</sub></th><th>□' = (b, b)</th><th>□' = (a, b)</th><th>□' = (b, a)</th></tr></thead><tbody><tr><th>□ = (b, b)</th><td>{()}</td><td>ø</td><td>ø</td></tr><tr><th>□ = (a, b)</th><td>ø</td><td>{()}</td><td>ø</td></tr><tr><th>□ = (b, a)</th><td>ø</td><td>ø</td><td>{()}</td></tr></tbody></table>

<table><thead><tr><th>W<sup>□,□'</sup><sub>0</sub></th><th>□' = (b, b)</th><th>□' = (a, b)</th><th>□' = (b, a)</th></tr></thead><tbody><tr><th>□ = (b, b)</th><td>ø</td><td>{(0)}</td><td>ø</td></tr><tr><th>□ = (a, b)</th><td>{(1)}</td><td>ø</td><td>ø</td></tr><tr><th>□ = (b, a)</th><td>{(1)}</td><td>{(0)}</td><td>{(0)}</td></tr></tbody></table>

<table><caption>FIGURE 2. Computation of a set of combinatorial weights step by step</caption><thead><tr><th>W<sup>□,□'</sup><sub>1</sub></th><th>□' = (b, b)</th><th>□' = (a, b)</th><th>□' = (b, a)</th></tr></thead><tbody><tr><th>□ = (b, b)</th><td>ø</td><td>ø</td><td>ø</td></tr><tr><th>□ = (a, b)</th><td>{(1, 1)}</td><td>{(1, 0)}</td><td>ø</td></tr><tr><th>□ = (b, a)</th><td>{(1, 1)}</td><td>{(0, 0), (1, 0)}</td><td>{(0, 0)}</td></tr></tbody></table>

**Example A.1.2.** — The set of combinatorial weights of the fragment $F$:

B B B A

A B A A

is $W(F) = \{(0, 0, 0, 0), (0, 0, 1, 0), (0, 0, 1, 1), (1, 0, 1, 0), (1, 1, 0, 0)\}$.

**A.2. Viability and non-emptiness.** — Theorem 2.2.1 extends to degenerate genes without any modification.

**Theorem A.2.1.** — Let $X$ be a degenerate gene. Then $W(X)$ is not empty if and only if $X$ is viable.

The rest of this subsection is devoted to the proof of Theorem A.2.1. We argue by contradiction, assuming that $W(X) = \emptyset$. Then:

$$W_{f-1}^{(b,b),(b,b)} = W_{f-1}^{(a,b),(b,a)} = W_{f-1}^{(b,a),(a,b)} = \emptyset.$$

Moreover, by the third condition of Definition 1.4.1, the sequence $(X_i)_{i \in \mathbb{Z}}$ cannot be constant. As a consequence, there exists an index $i \in \{0, \dots, f-1\}$ for which $X_{i-1} \neq X_i$ or $X_{i-1+f} \neq X_{i+f}$. Let $j$ be the maximal such index. For all $i$ between $j+1$ and $f-1$, we then have $W_i^{(a,b),(b,a)} = W_{i-1}^{(a,b),(b,a)}$ and $W_i^{(b,a),(a,b)} = W_{i-1}^{(b,a),(a,b)}$. Hence:

$$W_j^{(a,b),(b,a)} = W_j^{(a,b),(b,a)} = \emptyset.$$
**Claim A.2.2.** — There exists $\square' \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$ such that $W_j^{\square, \square'} = \emptyset$ for all $\square \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$.

In order to prove this claim, we distinguish between two cases.

**First case.** — We assume that $X_{i-1} \neq X_{i-1+f}$ for all $i \in \{j+1, \dots, f-1\}$. Under this additional assumption, we have:

$$W_{j+1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = \dots = W_{f-2}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = \dots = W_{f-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = \emptyset.$$

If $X_{j-1} \neq X_j$ but $X_{j-1+f} = X_{j+f}$, we get $X_{j-1} = X_{j-1+f}$. Therefore:

$$\emptyset = W_j^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = (W_{j-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{a},\mathbf{b})} \cup W_{j-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a})}) \times \{1\}$$

$$\emptyset = W_j^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a})} = W_{j-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a})} \times \{0\}$$

$$\emptyset = W_j^{(\mathbf{b},\mathbf{a}), (\mathbf{a},\mathbf{b})} = (W_{j-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{a})} \cup W_{j-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b})}) \times \{0\}$$

In particular, we deduce that $W_{j-1}^{\square, (\mathbf{b},\mathbf{a})} = \emptyset$ for all $\square \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$ and our claim is proved. Similarly, if $X_{j-1} = X_j$ but $X_{j-1+f} \neq X_{j+f}$, we find that $W_{j-1}^{\square, (\mathbf{a},\mathbf{b})} = \emptyset$ for all $\square \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$, which proves the claim as well.

Let us now examine the situation where both $X_{j-1} \neq X_j$ and $X_{j-1+f} \neq X_{j+f}$. In this case, we have $X_{j-1} \neq X_{j-1+f}$ and thus:

$$\emptyset = W_j^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = W_{j-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} \times \{1\}$$

$$\emptyset = W_j^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a})} = (W_{j-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{a},\mathbf{b})} \cup W_{j-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b})}) \times \{0\}$$

$$\emptyset = W_j^{(\mathbf{b},\mathbf{a}), (\mathbf{a},\mathbf{b})} = (W_{j-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{a})} \cup W_{j-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b})}) \times \{0\}$$

and the claim holds with $\square' = (\mathbf{b}, \mathbf{b})$.

**Second case.** — Here, we assume that there exists an integer $j' \in \{j+1, \dots, f-1\}$ such that $X_{j'-1} = X_{j'-1+f}$. We choose $j'$ maximal. Then:

$$W_{j'+1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = \dots = W_{f-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = \emptyset$$

and:

$$W_{j'+1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} = (W_{j'}^{(\mathbf{b},\mathbf{b}), (\mathbf{a},\mathbf{b})} \cup W_{j'}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a})}) \times \{1\}.$$

Consequently $W_{j'}^{(\mathbf{b},\mathbf{b}), (\mathbf{a},\mathbf{b})} = W_{j'}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a})} = \emptyset$, from what we deduce by decreasing induction that:

$$W_j^{(\mathbf{b},\mathbf{b}), (\mathbf{a},\mathbf{b})} = W_j^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a})} = \emptyset.$$

Now, as in first case, we examine the three subcases depending on the truth values of the assertions “$X_{j-1} = X_j$” and “$X_{j-1+f} = X_{j+f}$” and conclude in all settings that our claim indeed holds.

**End of the proof.** — We observe that, if Claim A.2.2 holds for the index $j$, then it also holds for the index $j-1$. Indeed, either it holds for the same $\square'$ if $W_j^{\square, \square'} = W_{j-1}^{\square, \square'} \times \{\star\}$, or it holds for $\square'_1$ and $\square'_2$ if $W_j^{\square, \square'} = (W_{j-1}^{\square, \square'_1} \cup W_{j-1}^{\square, \square'_2}) \times \{\star\}$ with $\{\square', \square'_1, \square'_2\} = \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$.

By descending induction we deduce that Claim A.2.2 holds with $j = -1$, which contradicts the definition of the $W_{-1}^{\square, \square'}$'s. Theorem A.2.1 is proved.
**A.3. Counting weights.** — We now aim at extending Corollary 2.2.3 to degenerate genes. Let then $\mathbb{X}$ be a degenerate gene and define $c_i^{\square, \square'} = \text{Card} W_i^{\square, \square'}$ when $\square$ and $\square'$ are elements of $\{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$. As in §2.2, we have recurrence relations from which we easily derive the values of the $c_i^{\square, \square'}$'s. Unfortunately, this is not sufficient to calculate the cardinality of $W(\mathbb{X})$ because the union defining it, namely

$$W(\mathbb{X}) = W_{f-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} \cup W_{f-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a})} \cup W_{f-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{a},\mathbf{b})}.$$

is usually not a disjoint union. To tackle this issue, we introduce more sequences: given $\square, \square', \Delta, \Delta' \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$, we set:

$$c_i^{\square, \square', \Delta, \Delta'} = \text{Card} (W_i^{\square, \square'} \cup W_i^{\Delta, \Delta'}).$$

It then turns out that the following set of 14 sequences:

$$(c_i^{\square, \square'})_{-1 \le i \le f-1} \quad \text{for } \square, \square' \in \{(\mathbf{b}, \mathbf{b}), (\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$$

$$(c_i^{(\mathbf{a},\mathbf{b}), \square', (\mathbf{b},\mathbf{a}), \Delta'})_{-1 \le i \le f-1} \quad \text{for } \square', \Delta' \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$$

$$(c_i^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})})_{-1 \le i \le f-1}$$

satisfy a full collection of recurrence relations, allowing for their complete determination. For example, from the equalities:

$$W_i^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b})} \cup W_i^{(\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})} = (W_{i-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{a},\mathbf{b})} \cup W_{i-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a})} \\ \cup W_{i-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{a},\mathbf{b})} \cup W_{i-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{a})}) \times \{1\} \quad \text{if } X_{i-1} = X_{i-1+f}$$

$$= (W_{i-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b})} \cup W_{i-1}^{(\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})}) \times \{1\} \quad \text{if } X_{i-1} \neq X_{i-1+f}.$$

we derive using a straightforward analogue of Lemma 2.2.2:

$$c_i^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})} = \max_{i-1} c_{i-1}^{(\mathbf{a},\mathbf{b}), \square', (\mathbf{b},\mathbf{a}), \Delta'} \quad \text{if } X_{i-1} = X_{i-1+f}$$

$$= c_{i-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})} \quad \text{if } X_{i-1} \neq X_{i-1+f}.$$

where the maximum is taken over $\square$ and $\Delta$ varying in $\{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$. In a similar fashion, we obtain recurrence relations for the 13 other sequences. Note that for $c_i^{(\mathbf{a},\mathbf{b}), \square', (\mathbf{b},\mathbf{a}), \Delta'}$, we have to distinguish between four cases depending on the values of $X_i, X_{i-1}, X_{i+f}$ and $X_{i-1+f}$. The cardinality of $W(\mathbb{X})$ is finally given by the formula:

$$(25) \qquad \text{Card} W(\mathbb{X}) = c_{f-1}^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} + c_{f-1}^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{a}), (\mathbf{a},\mathbf{b})}$$

since the two corresponding set of weights are now disjoint.

As a summary, although the computation becomes more sophisticated and unpleasant, it remains possible to have access to the cardinality of $W(\mathbb{X})$ without computing the set $W(\mathbb{X})$ itself. This conclusion will be important when we will design fast algorithms for enumerating and counting elements of $W(\mathbb{X})$ in §B.2.2.

Previous constructions are also important for deriving the next theorem.

**Theorem A.3.1.** — Let $\mathbb{X}$ be a gene of length $f$ without any occurrence of $\emptyset$. Then $\text{Card} W(\mathbb{X}) < \text{Fib}_{f+2}$.

*Proof.* — One checks by induction on $i$ that:

$$c_i^{\square, (\mathbf{b},\mathbf{b})} \le \text{Fib}_{i+1} \quad ; \quad c_i^{(\mathbf{b},\mathbf{b}), \square'} \le \text{Fib}_{i+1} \quad ; \quad c_i^{(\mathbf{a},\mathbf{b}), (\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{a}), (\mathbf{b},\mathbf{b})} \le \text{Fib}_{i+1}$$

$$c_i^{(\mathbf{b},\mathbf{b}), (\mathbf{b},\mathbf{b})} \le \text{Fib}_{i+2} \quad ; \quad c_i^{\square, \square'} \le \text{Fib}_{i+2} \quad ; \quad c_i^{(\mathbf{a},\mathbf{b}), \square', (\mathbf{b},\mathbf{a}), \Delta'} \le \text{Fib}_{i+2}$$

for $i \in \{-1, 0, \dots, f-1\}$ and $\square, \square', \Delta' \in \{(\mathbf{a}, \mathbf{b}), (\mathbf{b}, \mathbf{a})\}$. Knowing this, we deduce that $\text{Card} W(\mathbb{X}) \le \text{Fib}_{f+1} + \text{Fib}_f = \text{Fib}_{f+2}$. The fact that the inequality is strict is proved by driving out the equality cases; we left it to the reader. $\square$
**A.4. Combinatorial weights and Serre weights.** — We fix an irreducible representation $\bar{\rho} : G_F \to \text{GL}_2(k_E)$ and a tame inertial type $t : I_F \to \text{GL}_2(\mathcal{O}_E)$ and choose a coherent triple $(h, \gamma, \gamma')$ parametrizing them (see Definition 1.1.1). We let $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ be the gene associated to $(h, \gamma, \gamma')$. In what follows, we do not make any assumption on $\mathcal{X}$; it can be degenerate or not.

To any combinatorial weight $w \in W(\mathcal{X})$, one can associate a Serre weight $S(w)$ as in §2.3. For this, we follow exactly the same recipe; the only difference is that we now need to pay attention to the fact that the two cases we have considered for defining $s$ exhaust all possibilites. This is the content of the following lemma.

**Lemma A.4.1.** — With the notations of §2.3, if $c_i = \frac{p-1}{2}$ for all $i$, the gene $\mathcal{X}$ is nondegenerate.

*Proof.* — The assumption means that $\gamma' = \gamma + \frac{q-1}{2}$. Using in addition that the triple $(h, \gamma, \gamma')$ is coherent, we deduce that:

$$h - (q+1)\gamma' \equiv \frac{q-1}{2} + \frac{q-1}{p-1} \pmod{q-1}.$$

Moreover, we derive from the definition of the $v_i$'s that:

$$(26) \qquad h - (q+1)\gamma' \equiv \sum_{i=0}^{f-1} (v_i + v_{i+f}) p^{f-1-i} \pmod{q-1}.$$

If the gene $\mathcal{X}$ did not contain any occurrence of $0$, we would derive from Lemma 1.3.3 that $v_i \in \{0, 1\}$ for all $i$. Therefore, comparing the two congruences above, we would get $v_i + v_{i+f} = \frac{p+1}{2}$ for all $i$. Using again that $v_i \in \{0, 1\}$ for all $i$, we would deduce that $p=3$ and $v_i = 1$ for all $i$. Applying Lemma 1.3.3 again, we would finally find that $X_i = \mathbf{B}$ for all $i$, which contradicts the definition of a gene. $\square$

After this remark, Theorem 2.3.1 extends verbatim.

**Theorem A.4.2.** — The construction $S$ induces a bijection $W(\mathcal{X}) \xrightarrow{\sim} \mathcal{D}(t, \bar{\rho})$.

*Proof.* — It is exactly the same that that of Theorem 2.3.1 (see §4), except that, when $\mathcal{X}$ is degenerate, the developments carried out in §4.2.3 are no longer needed (actually, they do not make sense) and we need to invoke Proposition 4.2.7 instead of Propositions 4.2.10 and 4.2.11 in order to guarantee that $\Delta$ maps $\hat{W}(h, \gamma, \gamma')$ to $W(\mathcal{X})$. $\square$

# Appendix B

## Algorithms

In this appendix, we discuss algorithmical solutions for manipulating the mathematical objects considered in this article: irreducible 2-dimensional mod $p$ Galois representations, tamely ramified Galois types, Serre weights and, of course, genes and combinatorial weights.

We always encode a Galois representation

$$\bar{\rho} \approx \text{Ind}_{G_F'}^{G_F} (\omega_{2f}^h \otimes \text{nr}'(\theta))$$

by the tuple $(p, f, h, \theta)$ with $0 \le h < q^2-1$. Although the tuples $(p, f, h, \theta)$ and $(p, f, p^f h, \theta)$ correspond to isomorphic Galois representations, we make the distinction between them.
The main reason is that the definition of the gene is sensible to the choice of $h$. In what follows, we shall always assume that $h$ is given by its sequence of digits in base $p$.

In the same fashion, we encode a Galois type $t = \omega_f^\gamma \oplus \omega_f^{\gamma'}$ by the quadruple $(p, f, \gamma, \gamma')$. As before, we make the distinction between $(p, f, \gamma, \gamma')$ and $(p, f, \gamma', \gamma)$ and we assume that $\gamma$ and $\gamma'$ are given by their sequences of digits in radix $p$.

In what follows, we estimate the efficiency of our algorithms by bounding their bit complexity defined as the number of operations on bits they perform. For example, the bit complexity of an addition on integers less than $p$ is $O(\log p)$. For integers written in base $p$ with at most $n$ digits, it is $O(n \log p)$.

**B.1. About genes.** — In this first subsection, we focus on genes. We give fast algorithms for computing the gene associated to a pair $(t, \bar{p})$ and conversely, given a gene $X$, we design an algorithm that samples a uniformly distributed pair $(t, \bar{p})$ having gene $X$.

**B.1.1. Preliminaries.** — We consider a coherent triple in the sense of Definition 1.1.1 and denote by $X = (X_i)_{i \in \mathbb{Z}}$ its associated gene. We let $(v_i)_{i \in \mathbb{Z}}$ be the sequence introduced at the end of §1.3. We recall that it is defined by the fact that it is $(2f)$-periodic, takes values in $\{0, \dots, p-1\}$ and makes the congruence (12) hold.

We have already seen in Lemma 1.3.3, that the $v_i$'s are closely related to the gene $X$. In what follows, we make these relationships even tighter. The forthcoming results are the key for designing our algorithms.

**Lemma B.1.1.** — For an integer $i \in \mathbb{Z}$, we have $X_i = 0$ if and only if:

$$ \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} \geq \frac{q^2-1}{p-1}. $$

*Proof.* — From the definition of the $v_i$'s and the $\alpha_i$'s, we derive that

$$ \alpha_i = \left\lfloor \frac{1}{q+1} \cdot \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} \right\rfloor. $$

By definition, $X_i = 0$ if and only if $\alpha_i \ge \frac{q-1}{p-1}$. Plugging the value of $\alpha_i$ and noticing that $\frac{q-1}{p-1}$ is an integer, we find that $X_i = 0$ if and only if

$$ \frac{1}{q+1} \cdot \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} \ge \frac{q-1}{p-1}. $$

which proves the lemma.

□

**Corollary B.1.2.** — We assume that $v_i \in \{0, 1\}$ for all $i$. Then $X_i \ne 0$ for all $i$.

*Proof.* — We fix an index $i$. It follows from the assumption that:

(27) $$ \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} \le \frac{q^2-1}{p-1}. $$

Besides, the equality case occurs if and only if $v_i = 1$ for all $i$. But this cannot happen because if would imply that $h$ is divisible by $q+1$, which is assumed to be false. Therefore, the inequality (27) is always strict and we conclude by Lemma B.1.1. □

**Lemma B.1.3.** — For any integer $i$ in $\mathbb{Z}$, the following holds:
(0a) if $v_i = 0$ and $X_{i+1} = 0$, then $X_i = AB$;

(0b) if $v_i = 0$ and $X_{i+1} \neq 0$, then $X_i = A$;

(1a) if $v_i = 1$ and $X_{i+1} = 0$, then $X_i = 0$;

(1b) if $v_i = 1$ and $X_{i+1} \neq 0$, then $X_i = B$;

(2) if $v_i \ge 2$, then $X_i = 0$.

*Proof.* — We first assume $v_i = 0$. From Lemma 1.3.3, we deduce that $X_i \in \{A, AB\}$. Moreover, if $X_{i+1} = 0$, we know that $X_i \in \{AB, 0\}$; hence $X_i = AB$ and we have proved (0a). Conversely, from $X_i = AB$ we deduce $X_{i+1} = 0$, which proves (0b).

We assume $v_i = 1$ and $X_{i+1} = 0$. By Lemma 1.3.3, we find $X_i \in \{B, 0\}$. However $X_i = B$ is not compatible with $X_{i+1} = 0$. Therefore $X_i = 0$, which proves (1a).

We consider the case where $v_i = 1$ and $X_{i+1} \neq 0$. As before, we have $X_i \in \{B, 0\}$. Applying Lemma B.1.1 with $i+1$, we obtain:

$$ \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j+1} \geq \frac{q^2-1}{p-1}. $$

A simple computation using the fact that $v_i = 1$ gives:

$$ \begin{aligned} p \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} &= q^2 - 1 + \sum_{j=0}^{2f-1} p^{2f-1-j} v_{i+j} \\ &\geq q^2 + 1 + \frac{q^2 - 1}{p-1} = p \cdot \frac{q^2 - 1}{p-1}. \end{aligned} $$

Applying again Lemma B.1.1, we find $X_i \neq 0$. Therefore $X_i = B$ and (1b) is proved.

Finally, the last assertion follows directly from Lemma 1.3.3. $\square$

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

**B.1.2. Computation of the gene.** — As above, we consider a coherent triple $(h, \gamma, \gamma')$ and aim at designing a fast algorithm for computing its associated gene. Before proceeding, let us observe that the naive algorithm (consisting in computing the $\alpha_i$'s and spotting in which intervals they fall) has quadratic complexity in $f$. Indeed the computation of a single $\alpha_i$ requires $O(f)$ operations on integers less than $p$ and this calculation needs to be repeated $f$ times. However, after Lemma B.1.3, it becomes possible to significantly speed up this computation.

**Theorem B.1.4.** — There exists an algorithm that takes as input a coherent triple $(h, \gamma, \gamma')$ (with $h, \gamma$ and $\gamma'$ written in base $p$) and outputs its gene ($X_0, \dots, X_{2f-1}$) for a cost of $O(f \log p)$ bit operations.

**Remark B.1.5.** — If the inputs $h, \gamma$ and $\gamma'$ are not written in base $p$, it is of course always possible to compute these writings as a preliminary. However this calculations requires a number of bit operations which does not stay in $O(f \log p)$, although fast multiplication techniques allow for quasi-linear algorithms in $f \log p$.

*Proof of Theorem B.1.4.* — The main ingredients of our algorithm are the formulas of Corollary B.1.2 and Lemma B.1.3, which connect the $X_i$'s to the values of the $v_i$'s.

As a first step, we then compute the $v_i$'s. For this, it is enough to compute

$$ (h - q\gamma' - \gamma') \mod q^2 - 1 $$

and observe its digits in base $p$. We claim that, if we put all operations in base $p$, the whole computation can be achieved for a cost of $O(f \log p)$ bit operations. Indeed, additions can be done with this complexity (using the naive algorithm), whereas reduction modulo $q^2-1$ and multiplication boils down to reorganizing the digits.
Once the $v_i$'s have been computed, the second step of our algorithm consists in checking if all of them are in $\{0,1\}$ (which can be obviously done in the desired complexity). If this occurs, we know from Corollary B.1.2, that the $X_i$'s are all different from 0. Applying now Lemma B.1.3, we find that $X_i = A$ when $v_i = 0$ and $X_i = B$ when $v_i = 1$. This completes the computation of the gene.

To conclude with, we have to consider the case where we have found an index $i_0$ with $v_{i_0} \ge 2$. In this situation, it follows from Lemma B.1.3 that $X_{i_0} = 0$. Then, applying again Lemma B.1.3, we can deduce the value of $X_{i_0-1}$: it is $AB$ if $v_{i_0-1}$ vanishes and $0$ otherwise. Repeating this procedure again and again, we find iteratively all the values of the $X_i$'s for a cost which remains in $O(f \log p)$ bit operations. $\square$

**Example B.1.6.** — We use the algorithm described above to compute the gene of the triple $(h, \gamma, \gamma')$ of Example 2.3.2. As seen in this example, the values of the $v_i$'s are $(v_0, \dots, v_{13}) = (4, 0, 1, 0, 0, 3, 0, 1, 0, 0, 4, 2, 1, 0)$. We observe that there do exist indices $i_0$ with $v_{i_0} \ge 2$, e.g. $i_0 = 0$. We thus have $X_0 = 0$. Now, applying Lemma B.1.3 with $i = 13$, we obtain $X_{13} = AB$. Continuing this way, we find $X_{12} = B$, $X_{11} = 0$, $X_{10} = 0$, $X_9 = AB$, $X_8 = A$, etc. Finally, we discover the gene of $(h, \gamma, \gamma')$ which is:

0 A B A AB 0 A
B A AB 0 0 B AB

that is exactly the gene of Example 2.1.2 as we claimed.

**B.1.3. Sampling $(h, \gamma, \gamma')$ with a prescribed gene.** — Conversely, Lemmas 1.3.3 and B.1.3 allows for finding all the coherent triples $(h, \gamma, \gamma')$ associated to a given gene $\mathcal{X}$. Indeed, they together readily imply the following proposition.

**Proposition B.1.7.** — Let $(h, \gamma, \gamma')$ be a coherent triple and let $(v_i)_{i \in \mathbb{Z}}$ be its associated sequence. Then, the gene of $(h, \gamma, \gamma')$ is $\mathcal{X} = (X_i)_{i \in \mathbb{Z}}$ if and only if the following conditions hold for all $i$:

(a) if $X_i = A$, then $v_i = 0$;

(ab) if $X_i = AB$, then $v_i = 0$;

(b) if $X_i = B$, then $v_i = 1$;

(oo) if $X_i = 0$ and $X_{i+1} = 0$, then $1 \le v_i \le p-1$;

(o★) if $X_i = 0$ and $X_{i+1} \ne 0$, then $2 \le v_i \le p-1$.

**Theorem B.1.8.** — There exists a Las Vegas algorithm that takes as input a gene $\mathcal{X}$ and outputs a coherent triple $(h, \gamma, \gamma')$, uniformly distributed among all possibilities, with gene $\mathcal{X}$. This algorithm fails with probability at most $\frac{1}{p^f} + \min(\frac{1}{2}, \frac{1}{p-2})$ and performs at most $O(f \log p)$ bit operations.

*Proof.* — We start by sampling a sequence $v_0, \dots, v_{2f-1}$ satisfying the requirements of Proposition B.1.7. We then sample an integer $\gamma'$, uniformly distributed in the range $\{0, 1, \dots, q-2\}$, by sampling independently its $f$ digits in base $p$ and rejecting the value if all digits are $p-1$.

If the integer $v = \sum_{i=0}^{2f-1} v_i p^{2f-1-i}$ is divisible by $q+1$, we reject the value and the algorithm fails, except if there was only one possibility for the $v_i$'s in which case the algorithm raises an error and answers that there is no coherent triple whose gene is $\mathcal{X}$. (By Proposition 1.3.2, this case can show up only when $p = 3$.)
If $v$ is not divisible by $q+1$, the algorithm computes:

$$h = v - (q+1)\gamma' \mod q^2 - 1$$
and $$\gamma = (1 + p + \dots + p^{f-1}) - \gamma' - h \mod q - 1$$

and outputs $(h, \gamma, \gamma')$. All the previous computations can be done for a cost of $O(f \log p)$ bit operations (by writing down all operations in base $p$). Moreover, it is clear after Proposition B.1.7 that the output is a coherent triple with gene $\mathbb{X}$ and that it is uniformly distributed.

It then only remains to bound the probability of failure of our algorithm. Note that failures can happen in two places. First, it happens if all the digits of $\gamma'$ are $p-1$; this case occurs with probability $\frac{1}{p^f}$.

The second source of failure occurs when $h$ is divisible by $q+1$, which is equivalent to the fact that $v_i = v_{i+f}$ for all $i$. Remember that, in this special situation, we know moreover that there are multiple choices for the $v_i$'s. This means that there exists a particular index $i_0$ for which $v_{i_0}$ can take at least two values. Coming back to the definition, we find more precisely that it can take at least $n$ values with $n = \max(2, p-2)$. Since modifying the value of $v_{i_0}$, while keeping the $v_i$'s unchanged for all $i \neq i_0$, leads to another acceptable set of values of the $v_i$'s, we conclude that the probability to have $v_i = v_{i+f}$ for all $i$ is at most $\frac{1}{n}$. The probability of rejection at this second place is then at most $\frac{1}{n}$.

Adding to it the first probability of rejection we found, we deduce that our algorithm fails with probability at most $\frac{1}{p^f} + \frac{1}{n} = \frac{1}{p^f} + \min(\frac{1}{2}, \frac{1}{p-2})$, as wanted. $\square$

**B.2. About combinatorial weights.** — In this subsection, we assume that we are given a gene $\mathbb{X}$ and we aim at designing efficient algorithms for describing its set of combinatorial weights $W(\mathbb{X})$. Combining this with Theorem B.1.4 and the recipe of §2.3, we end up with fast algorithms for the computation of $D(t, \bar{p})$.

**B.2.1. Computing and enumerating weights.** — The first question we address is the complete computation of the set $W(\mathbb{X})$. In what follows, we shall prove the following theorem.

**Theorem B.2.1.** — There exists an algorithm which takes as input a gene $\mathbb{X}$ of length $f$ and outputs the set $W(\mathbb{X})$ for a cost of $O(f + f \cdot \text{Card } W(\mathbb{X}))$ bit operations.

Given that the bit size of $W(\mathbb{X})$ is obviously $f \cdot \text{Card } W(\mathbb{X})$ (since each combinatorial weight consists of $f$ bits), the complexity announced in Theorem B.2.1 is optimal up to a constant factor.

We now concentrate on the proof of Theorem B.2.1 and the description of the underlying algorithm. One first checks whether the input gene $\mathbb{X}$ is viable or not, which can obviously be done in $O(f)$ bit operations. If $\mathbb{X}$ is not viable we output the empty set. From now on, we then assume that $\mathbb{X}$ is viable. For the sake of simplicity, we only consider the case where $\mathbb{X}$ is nondegenerate, the opposite case being similar (but more technical). Keeping in mind the definition of $W(\mathbb{X})$ (see Definition 2.1.6), it is enough to explain how to compute $W(\underline{F})$ for a fragment $\underline{F}$.

For this, we rely on the definitions and on Lemma 2.2.2 which guarantees that the unions appearing in the definition of the $W_i^{(a,b)}$'s and $W_i^{(b,a)}$'s are all disjoint unions, whereas the unions of type $W_i^{(a,b)} \cup W_i^{(b,a)}$ are in fact supremums. Looking at the proof of this lemma, one can even figure out for which indices $i$, one has $W_i^{(a,b)} \subset W_i^{(b,a)}$ (and so $W_i^{(a,b)} \cup W_i^{(b,a)} = W_i^{(b,a)}$) and for which indices $i$, the inclusion goes in the reverse direction.
<caption>**Algorithm 1:** Computation of combinatorial weights</caption>

**Global variable:** Wxy
**combinatorial_weights (F)**
**Input:** A fragment F
**Output:** The set W(F)
**則:** length of F
**if** F₀ = 0 **then** Wxy ← [ Wab ]
**if** F₀ = 0 **then** Wxy ← [ Wba ]
**for** i = 1, 2, ..., ℓ−1 **do**
> **if** Fᵢ⁻¹ ~ Fᵢ↑ and Fᵢ⁻₁ ~ Fᵢ↑ **then** Wxy[i] ← Wxy[i−1]
> **if** Fᵢ⁻¹ ~ Fᵢ↑ and Fᵢ⁻₁ ≁ Fᵢ↑ **then** Wxy[i] ← Wba
> **if** Fᵢ⁻₁ ≁ Fᵢ↑ and Fᵢ⁻₁ ~ Fᵢ↑ **then** Wxy[i] ← Wab
> **if** Fᵢ⁻₁ ≁ Fᵢ↑ and Fᵢ⁻₁ ≁ Fᵢ↑ **then** Wxy[i−1] ← Wab
**则:** Wxy[i] ← Wba
**则:** Wxy[i] ← Wab
**if** Fᵢ⁻₁ = AB **then** return Wab(F, ℓ−1) + Wbb(F, ℓ−1)
**if** Fᵢ⁻₁ = AB **then** return Wba(F, ℓ−1) + Wbb(F, ℓ−1)
**return** [ (0) ]

**Wab (F, i)**
**则:** i = 0 **then**
> **if** F₀ = 0 **then** return []
> **else** return [ (0, 0, ..., 0) ]
**则:** Fᵢ⁻₁ ~ Fᵢ↑ **then** return Wab(F, i−1)
**则:** Fᵢ⁻₁ ≁ Fᵢ↑ **then** return Wba(F, i−1) + Wbb(F, i−1)

**Wba (F, i)**
**则:** i = 0 **then**
> **if** F₀ = 0 **then** return []
> **else** return [ (0, 0, ..., 0) ]
**则:** Fᵢ⁻₁ ~ Fᵢ↑ **then** return Wba(F, i−1)
**则:** Fᵢ⁻₁ ≁ Fᵢ↑ **then** return Wab(F, i−1) + Wbb(F, i−1)

**Wbb (F, i)**
**则:** i = 0 **then** return [ (1, 0, ..., 0) ]
**则:** Fᵢ⁻₁ ~ Fᵢ⁻₁ **then** W ← Wxy[i−1](F, i−1)
**则:** Fᵢ⁻₁ ≁ Fᵢ⁻₁ **then** W ← Wbb(F, i−1)
**for** w ∈ W **do** w[i] ← 1
**return** W

Translating these definitions and observations into algorithms, we end up with the procedure **combinatorial_weights**, which calls the recursive subroutines **Wab**, **Wba**, **Wbb** presented in Algorithm 1. In this implementation, the sets of weights are represented by lists and the addition of lists means concatenation. The notation `[ ]` refers to the empty list.

The correction of the algorithm is easily proved. Indeed, if $\ell$ denotes the length of the fragment $\underline{F}$, one checks by induction on $i$ that a call to $\underline{Wab}(\underline{F}, i)$ returns the set
$W_i^{(a,b)} \times \{0\}^{\ell-i}$ (represented by its list of elements), and similarly for $W_{ba}$ and $W_{bb}$. Regarding the complexity, we first observe that the preparation part of the algorithm **combinatorial weights** (consisting of the 9 first lines) requires no more than $O(\ell)$ bit operations. Now, for $i$ in $\{0, \dots, \ell-1\}$ and $\Box$ in $\{(a, b), (b, a), (b, b)\}$, we set $c_i^\Box = \text{Card } W_i^\Box$. In order to bound the complexity of the recursive part of the algorithm, the key observation is that there exists an absolute constant $C$ such that the following holds: when they are called on the input $(\underline{E}, i)$, the routines $Wab$, $Wba$ and $Wbb$ perform at most $C \cdot (\ell+i) \cdot c_i^\Box$ bit operations with $\Box = (a, b), (b, a)$ and $(b, b)$ respectively. This fact is proved by induction on $i$ without difficulty. Besides, it readily implies that the bit complexity of the recursive part of **combinatorial weights** is bounded by $2C \cdot \ell \cdot \text{Card } W(\underline{E})$. This finally establishes the complexity bound announced in Theorem B.2.1.

**Remark B.2.2.** — One can also design an iterative version of Algorithm 1 by running over the integers $i$ between 0 and $\ell-1$ and computing, for each new value of $i$, the sets $W_i^{(a,b)}$, $W_i^{(b,a)}$ and $W_i^{(b,b)}$ taking advantage of the previous calculations. However, proceeding this way, it is quite possible to perform useless computations. For example, if $F_{i-1}^\dagger = F_i^\dagger = F_{i-1}^\dagger = F_i^\dagger$, we observe that $W_i^{(a,b)}$, $W_i^{(b,a)}$ and $W_i^{(b,b)}$ depend only on $W_{i-1}^{(a,b)}$ and $W_{i-1}^{(b,a)}$ but not on $W_{i-1}^{(b,b)}$; therefore, the computation of $W_{i-1}^{(b,b)}$ is not needed in this case. Algorithm 1 does see this fact, while its iterative counterpart does not. Nevertheless, it is true that the bit complexity of the iterative version of Algorithm 1 stays within $O(\ell + \ell \cdot \text{Card } W(\underline{X}))$. This result is obtained by noticing that, for each $i$, at most one set among $W_i^{(a,b)}$, $W_i^{(b,a)}$ and $W_i^{(b,b)}$ can be discarded and then by proving by induction on $i$ that the three inequalities

$$c_i^{(a,b)} \le c_i^{(b,a)} + c_i^{(b,b)} \quad ; \quad c_i^{(b,a)} \le c_i^{(a,b)} + c_i^{(b,b)} \quad ; \quad c_i^{(b,b)} \le c_i^{(a,b)} + c_i^{(b,a)}$$

hold for all $i$ in $\{0, \dots, \ell-1\}$.

**Remark B.2.3.** — A slight modification of Algorithm 1 provides an algorithm that enumerates the elements of $W(\underline{X})$ in such a way that each new weight is generated for a cost of $O(f)$ bit operations. This modification can be interesting when $W(\underline{X})$ is large but we are only interested in computing a small number of weights.

**B.2.2. Counting weights.** — Another related interesting question is the calculation of the cardinality of $W(\underline{X})$. A naive solution for this consists in generating the set $W(\underline{X})$ and then counting its elements; however, this is far for being optimal. In this subsection, we rely on the techniques introduced in §2.2 (see also §A.3) to design fast algorithms for performing this task. Precisely, we shall prove the following theorem.

**Theorem B.2.4.** — There exists an algorithm which takes as input a gene $\underline{X}$ of length $f$ and outputs the cardinality of $W(\underline{X})$ for a cost of $O(f^2)$ bit operations.

Since the cardinality of $W(\underline{X})$ is generally much bigger than $f$ (it could even be $2^f$), the complexity announced in Theorem B.2.4 is in general much better than that of Theorem B.2.1: counting weights can be done more efficiently that enumerating them, which is of course not surprising.

We move to the proof of Theorem B.2.4. Again, we give it only in the case where the gene $\underline{X}$ is viable and nondegenerate. In the opposite case, the proof follows the same pattern but it is more technical as it uses all the material introduced in §A.3.

To begin with, we consider Algorithm 2 that takes as input a fragment of length $\ell$ and computes the cardinality of $W(\underline{E})$ for a cost of $O(\ell^2)$ bit operations. It actually follows closely the formulas of §2.2. We notice that, contrary to what we did in §B.2.1, it is more
<caption>**Algorithm 2:** Computation of the number of combinatorial weights</caption>

number_of_combinatorial_wights (F)
| Input : A fragment F
| **Output:** The cardinality of W(F)
| if $F_0^\dagger = 0$ then cab[0] $\leftarrow$ 0 else cab[0] $\leftarrow$ 1
| if $F_0^\dagger = 0$ then cba[0] $\leftarrow$ 0 else cba[0] $\leftarrow$ 1
| cbb[0] $\leftarrow$ 1
| $\ell$ $\leftarrow$ length of F
| **for** i = 1, ..., $\ell$-1 **do**
| > if $F_{i-1}^\dagger \sim F_i^\dagger$ then cab[i] $\leftarrow$ cab[i-1]
| > if $F_{i-1}^\dagger \not\sim F_i^\dagger$ then cab[i] $\leftarrow$ cba[i-1] + cbb[i-1]
| > if $F_{i-1}^\dagger \sim F_i^\dagger$ then cba[i] $\leftarrow$ cba[i-1]
| > if $F_{i-1}^\dagger \not\sim F_i^\dagger$ then cba[i] $\leftarrow$ cab[i-1] + cbb[i-1]
| > if $F_{i-1}^\dagger \sim F_{i-1}^\dagger$ then cbb[i] $\leftarrow$ max(cab[i-1], cba[i-1])
| > if $F_{i-1}^\dagger \not\sim F_{i-1}^\dagger$ then cbb[i] $\leftarrow$ cbb[i-1]
| > if $F_{\ell-1}^\dagger = AB$ then return cab[\ell-1] + cbb[\ell-1]
| > if $F_{\ell-1}^\dagger = AB$ then return cba[\ell-1] + cbb[\ell-1]
| return 1

pleasant here to work iteratively (otherwise, we have to implement a cache in order to
guarantee that the complexity is the correct one).

The fact that Algorithm 2 is correct is clear after the results of §2.2. Moreover, we readily see that it performs $O(\ell)$ additions and comparisons on integers of the form `cab[i]`, `cba[i]` or `cbb[i]`. Besides, we know from Theorem 2.2.4 and its proof that `cab[i]` ≤ `Fib[i+2]`, `cba[i]` ≤ `Fib[i+2]` and `cbb[i]` ≤ `Fib[i+1]`. Consequently `cab[i]`, `cba[i]` and `cbb[i]` have at most $O(\ell)$ digits in their writings in base 2. Adding and comparing them can then be achieved for a cost of $O(\ell)$ bit operations. Putting all together, we find that the bit complexity of Algorithm 2 is within $O(\ell^2)$ as wanted.

To complete the computation of the cardinality of W($\mathbb{X}$), it only remains to combine
all the contributions of the fragments. If $\ell_1, \dots, \ell_m$ denote the respective lengths, this
amounts to multiply integers whose bitsizes are $O(\ell_i)$. Using the naive multiplication
algorithm, this can be done for a cost of $O(\sum_{i \neq j} \ell_i \ell_j)$ bit operations. Adding to this the
cost of the computation of the cardinality of the fragments, which is $O(\sum_i \ell_i^2)$, we find
that the complete algorithm runs within

$$
O\left(\sum_{i=1}^{m} \sum_{j=1}^{m} \ell_i \ell_j\right) \subset O\left((\sum_{i=1}^{m} \ell_i)^2\right) \subset O(f^2)
$$

bit operations. Theorem B.2.4 is then proved.

**B.3. About Serre weights.** — After Theorem 2.3.1, the results of the previous sub-
section have direct consequences on the enumeration and the counting of common Serre
weights.

*Theorem B.3.1.* —

(1) There exists an algorithm that takes as input a coherent triple $(h, \gamma, \gamma')$ with $h, \gamma$ and $\gamma'$ written in base $p$ and outputs the set $\mathcal{D}(t, \bar{p})$ for a cost of

$$
O(f \log p + f \cdot \text{Card} \, \mathcal{D}(t, \bar{p}) \cdot \log p)
$$
bit operations.

(2) There exists an algorithm that takes as input a coherent triple $(h, \gamma, \gamma')$ with $h, \gamma$ and $\gamma'$ written in base $p$ and outputs the cardinality of the set $\mathcal{D}(t, \bar{\rho})$ for a cost of $O(f \log p + f^2)$ bit operations.

*Proof.* — Given a coherent triple $(h, \gamma, \gamma')$, one can compute its gene $\mathbb{X}$ using the algorithm of Theorem B.1.4 for a cost of $O(f \log p)$ bit operations. After this, one can use Algorithm 1 to compute the set $\mathcal{W}(\mathbb{X})$ of combinatorial weights of $\mathbb{X}$ for a supplementary cost of:

$$O(f + f \cdot \text{Card} \mathcal{W}(\mathbb{X})) = O(f + f \cdot \text{Card} \mathcal{D}(t, \bar{\rho}))$$

bit operations. It then remains to transform those combinatorial weights into actual Serre weights using the recipe of §2.3. Looking at it, we find that each such transformation requires $O(f)$ operations on integers less than $p$, corresponding to $O(f \log p)$ bit operations. Since this operation has to be repeated for each combinatorial weight, the total complexity of this part amounts to

$$O(f \cdot \text{Card} \mathcal{W}(\mathbb{X}) \cdot \log p) = O(f \cdot \text{Card} \mathcal{D}(t, \bar{\rho}) \cdot \log p)$$

bit operations. Putting all these inputs together, we deduce the first point of the theorem.

The second point is proved in a similar fashion except that we refer to Algorithm 2 instead of Algorithm 1 (and Theorem B.2.4 instead of Theorem B.2.1 for the complexity analysis). □

**B.4. Implementation.** — All the algorithms presented in the previous subsections have been implemented in the SageMath package `pbtdef` [CDM3]. Below, we present an overview of the capabilities of this package. First of all, we need to import the package. This is done as follows (after having installed the package, of course):

In [1]: from pbtdef.all import *

We can now create a 2-dimensional absolutely irreducible Galois representation by passing in the relevant parameters:

In [2]: p = 5; f = 7
h = 4865171564
rhobar = IrreducibleRepresentation(p, f, h); rhobar

Out[2]: Ind(\omega_{14}^{4865171564})

The method `weights` returns the set of weights of $\bar{\rho}$ (in order to save space, the output has been voluntarily truncated in the cell below; the complete set of weights has 96 elements):

In [3]: rhobarweights()

Out[3]:
{ Sym[3,3,3,4,3,3,2] ⊗ det^{46544}, Sym[0,2,0,3,0,4,0] ⊗ det^{61648}, ..., 
  Sym[4,0,1,3,3,0,2] ⊗ det^{12264}, Sym[3,0,1,0,4,3,0] ⊗ det^{62139} }

Similarly, one can manipulate types:

In [4]: gamma = 58923; gammap = 77258
t = Type(p, f, gamma, gammap); t

Out[4]: ω_{7}^{58923} ⊕ ω_{7}^{77258}
In [5]: G = Gene(rhobar,t); G

Out[5]:

{ Sym[0,2,0,3,0,4,0] ⊗ det^61648, Sym[3,1,0,3,3,0,0] ⊗ det^62274, ..., 
Sym[0,2,0,0,4,0,1] ⊗ det^59023, Sym[3,1,0,3,3,0,1] ⊗ det^59149 }

One can easily compute the gene associated to the above inputs, by using the constructor Gene as follows:

In [6]: G = Gene(rhobar,t); G

Out[6]:

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

The colors in the output indicate the dominant letter at each position (blue for A and red for B), while the lines drawn between the nucleotides above correspond to the so-called decorations; they has been introduced in [CDM2] and are useful to read the equation of the associated Kisin variety and those of its shape stratification.

We can now ask for the combinatorial weights of the gene using the method weights :

In [7]: Gweights()

Out[7]:

{ (0,0,1,0,1,0,1), (1,0,0,0,0,1,0), (1,0,1,0,0,0,1), (0,1,0,0,1,0,1), 
(0,0,1,0,0,1,0), (1,0,0,0,1,1,0), (0,0,0,0,0,0,1), (1,0,1,0,1,1,0), 
(0,1,0,0,0,1,0), (0,0,1,0,1,1,0), (1,0,0,0,0,0,1), (0,0,0,0,1,1,0), 
(1,0,1,0,0,1,0), (0,1,0,0,1,1,0), (0,0,1,0,0,0,1), (0,0,0,0,0,1,0), 
(1,0,1,0,1,0,1), (0,1,0,0,0,0,1), (1,0,0,0,1,0,1), (0,0,0,0,1,0,1) }

We can verify that the weights computed by the software are exactly those we computed by hand in Example 2.1.7 (except that they do not appear in the same order).

If we are only interested in the number of combinatorial weights of a given gene, one should use preferably the method number_of_weights , which implements Algorithm 2 and is then much faster than computing the set of weights in full.

In [8]: G.number_of_weights()

Out[8]: 20

One can ask for the computation of the set of common Serre weights of $\overline{\rho}$ and t as follows:

In [9]: rhobarweights(t) # or equivalently tweights(rhobar)

Out[9]:

{ Sym[0,2,0,3,0,4,0] ⊗ det^61648, Sym[0,1,1,0,4,3,0] ⊗ det^62138, ..., 
Sym[4,2,1,0,4,3,3] ⊗ det^77758, Sym[0,2,0,0,4,0,1] ⊗ det^59023 }

It is possible to create a gene by passing in its sequence of nucleotides. For example, the following creates the “Fibonacci gene” which appears in Theorem 2.2.4:
In [10]: `FibG = Gene([ 'O', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'AB' ])`
FibG

Out[10]:

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

We can compute its number of combinatorial weights and check that it is indeed in the Fibonacci sequence:

In [11]: `FibG.number_of_weights()`

Out[11]: 89

Finally, one can generate a pair $(t, \bar{p})$ exhibiting this particular gene using the method `randomalli` (and providing a value of $p$):

In [12]: `FibG.randomalli(p=5)`

Out[12]: `(Ind(\omega_{18}^{1136706441368}), \omega_{9}^{500613} \oplus \omega_{9}^{956342})`

Notice that the output is not deterministic; more precisely, it is uniformly distributing among all possibilities.

In [13]: `FibG.randomalli(p=5)`

Out[13]: `(Ind(\omega_{18}^{654399553802}), \omega_{9}^{253672} \oplus \omega_{9}^{709401})`

## References

[BDJ] Buzzard K., Diamond F., Jarvis F., On Serre's conjecture for mod $\ell$ Galois representations over totally real fields, Duke Math. J. 155, 2010, 105-161.

[BM1] Breuil C., Mézard A., Multiplicités modulaires et représentations de $GL_2(\mathbb{Z}_p)$ et de Gal$(\mathbb{Q}_p/\mathbb{Q}_p)$ en $l = p$, Duke Math. J. 115, 2002, no.2, 205-310.

[BM2] Breuil C., Mézard A., Multiplicités modulaires raffinées, Bull. Soc. Math. France 142, 2014, 127-175.

[BP] Breuil C., Paškūnas V., Towards a modulo $p$ Langlands correspondence for $GL_2$, Memors of A.M.S. 216, 2012.

[CDM1] Caruso X., David A., Mézard A., Calculs d'anneaux de déformations potentiellement Barsotti-Tate, Transactions of the American Mathematical Society, American Mathematical Society 370 (9), 2018, 6041-6096.

[CDM2] Caruso X., David A., Mézard A., Variétés de Kisin stratifiées et déformations potentiellement Barsotti-Tate, Journal of the Institute of Mathematics of Jussieu, Cambridge University Press (CUP) 15 (5), 2018, 1019-1064.

[CDM3] Caruso X., David A., Mézard A., `pbtdef`: Potentially Barsotti-Tate deformations, SageMath package, available at https://plmlab.math.cnrs.fr/caruso/pbtdef/

[CEGS] Caraiani A., Emerton M., Gee T., Savitt D., Moduli stacks of two-dimensional Galois representations, Preprint 2019, 123p.

[Co] Connes A., The Witt construction in characteristic one and quantization, Noncommutative geometry and global analysis 546 (2011), 83-113.

[Da] David A., Poids de Serre dans la conjecture de Breuil-Mézard, Contemporary Math. 691, 2017, 133-156.
[EmGe] Emerton M., Gee T., *A geometric perspective on the Breuil-Mézard conjecture*, J. Inst. Math. Jussieu **13**, 2014, no.1, 183-223.

[GeKi] Gee T., Kisin M., *The Breuil-Mézard conjecture for potentially Barsotti-Tate representations*, Forum of Mathematics, Pi, 2014, 56p.

[He] Henniart G., *Sur l'unicité des types pour GL₂*, Appendice of [BM1], Duke Math J. **115**, 2002, no.2, 298-310.

[HuTa] Hu Y., Tan F., *The Breuil-Mézard conjecture for non-scalar split residual representations*, Annales Scientifiques de l'École Normale Supérieure **48** (6), 2013.

[Ki1] Kisin M., *The Fontaine-Mazur conjecture for GL₂*, J. Amer. Math. Soc. **22**, 2009, no.3, 641-690.

[Ki2] Kisin M., *The structure of potentially semi-stable deformation rings*, Proceedings of the International Congress of Mathematics. Vol. II, 2010, 294-311.

[Ki3] Kisin M., *Moduli of finite flat group schemes and modularity*, Ann. of Math. **107**, 2009, 1085-1180.

[LLHLM1] Le D., Le Hung B., Levin B., Morra S., *Serre weights and Breuil's lattice conjecture in dimension three*, Forum of Math. Pi **8**, 2020, 135p.

[LLHLM2] Le D., Le Hung B., Levin B., Morra S., *Local models for Galois deformation rings and applications*, Preprint 2020, 101p.

[Pa] Paškūnas V., *On the Breuil-Mézard conjecture*, Duke Math. J. **164** (2), 2015, 297-359.

[Sa] Sander F., *A local proof of the Breuil-Mézard conjecture in the scalar semi-simplification case*, J. Lond. Math. Soc. **94**(2), 2016, 447-461.

X. CARUSO, CNRS; IMB, Université de Bordeaux, 351 cours de la Libération, 33405 Talence, France
*E-mail : xavier.caruso@normalesup.org*

A. DAVID, LMB, Université de Franche-Comté, 16 route de Gray, 25030 Besançon Cedex, France;
IRMAR, Université de Rennes I, Campus de Beaulieu, 35042 Rennes Cedex, France
*E-mail : agnes.david@math.cnrs.fr*

A. MÉZARD, DMA, École Normale Supérieure PSL, 45 rue d'Ulm, 75005 Paris, France
*E-mail : ariane.mezard@ens.fr*