# Algèbre linéaire dédiée pour les algorithmes Scalar-FGLM et Berlekamp-Massey-Sakata

Vincent Guisse

► To cite this version:

Vincent Guisse. Algèbre linéaire dédiée pour les algorithmes Scalar-FGLM et Berlekamp-Massey-Sakata. Calcul formel [cs.SC]. 2016. hal-01516249

HAL Id: hal-01516249

https://inria.hal.science/hal-01516249v1

Submitted on 29 Apr 2017

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 CC BY 4.0 - Attribution - International License
Algèbre linéaire dédiée pour les algorithmes
Scalar-FGLM et Berlekamp-Massey-Sakata

Vincent GUISSE

Encadré par Jean-Charles FAUGÈRE
et Jérémy Berthomieu, UPMC-LIP6-POLSYS

17 août 2016

## Le contexte général

L'algorithm de Berlekamp-Massey ([1], [11]) a été inventé par Berlekamp pour décoder les codes BCH ([5]), puis Massey a montré qu'il permettait de résoudre le problème de devinette de récurrence linéaire pour les suites à un indice. Il a ensuite été étendu par Sakata ([13]) pour résoudre le même problème pour les suites à plusieurs indices (algorithme de Berlekamp-Massey-Sakata, ou BMS). La solution prend alors la forme d'une base de Gröbner de l'idéal des relations d'une table de valeurs de la suite. Il a enfin été légèrement adapté pour permettre le décodage des codes d'évaluations sur un domaine ordonné ([6]).

Récemment, dans [3], Faugère, Berthomieu et Boyer on présenté un al-
gorithme, Scalar-FGLM, généralisant la version matricielle de l'algorithme de
Berlekamp-Massey pour les suites à plusieurs indices. Cette dernière consiste
à résoudre un système linéaire de Hankel de taille *d*, l'ordre de la récurrence.
Ceci est possible en complexité en temps $O(M(d) \log d)$, où $M(d)$ est le coût
du produit de polynômes de degré *d* (voir [7]). Dans le cas de Scalar-FGLM,
on extrait une sous matrice de rang maximal d'une matrice multi-Hankel puis
on résout des systèmes faisant intervenir directement cette matrice. Cela est
possible en complexité $O(M(d) \log d)$ pour l'ordre lexicographique et dans le
cas générique (shape position). Cependant, sans cette hypothèse de généricité
on ne sait pas résoudre le système linéaire aussi efficacement.

Dans [4], les auteurs de Scalar-FGLM l'étendent aux suites linéaires récu-
rentes à coefficients polynomiaux, les suites P-récurrentes. Le problème ouvert
de savoir si certaines marches de l'espaces sont P-récurrentes ou non pourrait
se voir apporter des réponses en cas de progrès pratiques ou théoriques dans la
gestion des matrices générées par Scalar-FGLM.

## Le problème étudié

Un premier objectif du stage était d'obtenir une algèbre linéaire plus rapide en pratique ou en théorie pour Scalar-FGLM et ses dérivés. Un second était de rapprocher les descriptions de Scalar-FGLM et de BMS, puisque ces deux algorithmes ont des sorties équivalentes.
## La contribution proposée

Dans le but d'obtenir une algèbre linéaire plus rapide pour Scalar-FGLM et ses dérivés, nous avons tenté d'étendre l'algorithme du demi-PGCD en dimension supérieure. Ceci nous a amené à une formulation polynomiale de l'algèbre linéaire de Scalar-FGLM, mais qui n'a pas débouché sur un algorithme efficace.

Par ailleurs nous avons spécialisé la version de BMS qui est donnée dans [6] pour la localisation d'erreur des codes d'évaluation sur un domaine ordonné. Nous l'avons appliquée à la devinette de récurrence linéaire multidimensionnelle, ce qui revenait à se placer dans le cadre d'un anneau de polynômes multivariés muni d'un ordre du degré. Ce travail a été accompagné d'une implémentation en Maple, et il a permis d'identifier des différences fondamentales entre Scalar-FGLM et BMS.

## Les arguments en faveur de sa validité

Notre formulation polynomiale de l'algèbre linéaire de Scalar-FGLM est bien une généralisation directe de la formulation polynomiale en dimension 1, qui mène à une solution efficace avec l'algorithme du demi-PGCD.

Notre spécialisation de BMS a été implémentée et testée. Elle repose sur une présentation de BMS (dans [6]) de lecture probablement plus accessible que la version originale de Sakata, mais qui nécessitait une traduction dans le langage des polynômes pour être directement exploitée par les non spécialistes de la théorie des codes correcteurs.

## Le bilan et les perspectives

Nous n'avons pas trouvé d'algèbre linéaire dédiée efficace pour Scalar-FGLM et ses dérivés. Cependant nous proposons une formulation polynomiale de cette algèbre linéaire qui peut être un point de départ pour un tel algorithme, analogue au demi-PGCD.

Notre réécriture de BMS dans le langage des polynômes et son implémentation en Maple ont permis de rapprocher les descriptions de Scalar-FGLM et de BMS, la question reste cependant ouverte de savoir si ces algorithmes effectuent les mêmes calculs. Pour y répondre il est nécessaire d'expliciter une version itérative de Scalar-FGLM.
# 1 Problème, contexte

## 1.1 Suites récurrentes linéaires, tables

Nous présentons dans cette partie les suites récurrentes linéaires à coefficients constants à un ou à plusieurs indices, et les problèmes de devinette de récurrence sur des tables (finies) de valeurs de ces suites.

### 1.1.1 Suites unidimensionnelles

Dans un corps $\mathbb{K}$, une suite $u = (u_i)_{i \in \mathbb{N}} \in \mathbb{K}^{\mathbb{N}}$ est récurrente linéaire à coefficients constants si et seulement s'il existe un entier $d$ et des coefficients $(\alpha_k)_{k \in \{0, \dots, d-1\}}$ dans $\mathbb{K}$ tels que :

$$ \forall i \in \mathbb{N}, u_{d+i} + \sum_{k=0}^{d-1} \alpha_k u_{k+i} = 0. \qquad (1) $$

Ainsi, $(u_i)_{i \in \mathbb{N}}$ est déterminée par la donnée de ses $d$ premiers termes et la relation (1). Le plus petit $d$ satisfaisant la relation (1) est appelé l'ordre de la suite linéaire récurrente $u$.

Si on connaît seulement la table $(u_0, u_1, \dots, u_{N-1})$ des $N$ premiers termes de la suite $u$, on peut rechercher un entier $L_N$ et des coefficients $(\alpha_k)_{k \in \{0, \dots, L_N-1\}}$ tels que :

$$ \forall i \in \mathbb{N}, L_{N+i} \le N-1 \Rightarrow u_{L_N+i} + \sum_{k=0}^{L_N-1} \alpha_k u_{k+i} = 0. \qquad (2) $$

Formellement, il s'agit de résoudre le problème suivant :

**Problème 1.** Devinette de récurrence linéaire simple

*Entrées :* La table $(u_0, u_1, \dots, u_{N-1})$ des $N$ premiers termes d'une suite.

*Sorties :* Le plus petit entier $L_N$ et des coefficients $(\alpha_k)_{k \in \{0, \dots, L_N-1\}}$ vérifiant la relation (2).

Observons sur un exemple élémentaire différents cas de figure :

**Exemple 1.** Soit $(u_i)_{i \in \mathbb{N}}$ la suite de Fibonacci, définie par $u_0 = 0$, $u_1 = 1$ et pour tout $i \in \mathbb{N}$, $u_{i+2} = u_{i+1} + u_i$. Alors on a :

- Pour $N = 1$ et la table $(0)$, $L_1 = 0$ et il n'y a pas de coefficients.

- Pour $N = 2$ et la table $(0, 1)$, $L_2 = 2$ et tous les couples $(\alpha_0, \alpha_1)$ de coefficients conviennent.

- Pour $N = 3$ et la table $(0, 1, 1)$, $L_3 = 2$ et on peut prendre $\alpha_0$ arbitraire pourvu que $\alpha_1 = -1$.

- Pour $N = 4$ et la table $(0, 1, 1, 2)$, $L_4 = 2$ et les seuls coefficients possibles sont $\alpha_0 = -1$ et $\alpha_1 = -1$. De même pour tout $N > 4$.

On remarque dans cet exemple que contrairement à $L_N$, les coefficients $(\alpha_k)$ ne sont pas nécessairement uniques (par exemple pour $N = 3$). En particulier dans le cas $L_N = N$, tous les coefficients conviennent et d'une certaine façon « il n'y a pas de relation de récurrence » pour lier les termes connus de la suite.
### 1.1.2 Suites multidimensionnelles

On va généraliser ce qui précède aux suites à plusieurs indices. Soit $n \ge 1$, on note $\mathbf{i} = (i_1, \dots, i_n) \in \mathbb{N}^n$. Soit $u = (u_i)_{i \in \mathbb{N}^n}$ une suite à $n$ indices d'éléments de $\mathbb{K}$. S'il existe une partie finie $\mathcal{K} \subset \mathbb{N}^n$ et des coefficients non tous nuls $(\alpha_k)_{k \in \mathcal{K}}$ tels que

$$ \forall \mathbf{i} \in \mathbb{N}^n, \sum_{k \in \mathcal{K}} \alpha_k u_{\mathbf{k}+\mathbf{i}} = 0, \qquad (3) $$

alors la relation (3) est appelée une relation de récurrence linéaire multidimensionnelle de support $\mathcal{K}$.

**Exemple 2.** La suite $b = \left(\binom{i}{j}\right)_{(i,j)\in\mathbb{N}^2}$ des coefficients binomiaux vérifie la relation de Pascal :

$$ \forall (i, j) \in \mathbb{N}^2, b_{i+1,j+1} - b_{i,j+1} - b_{i,j} = 0. $$

Ces relations permettent de définir les suites linéaires récurrentes multidimensionnelles à coefficients constants par analogie avec ce qui se passe en dimension 1 (voir $[3]$) :

**Définition 1.** La suite $(u_i)_{i \in \mathbb{N}^n}$ est récurrente linéaire n-dimensionnelle à coefficients constants lorsqu'on peut calculer sans contradiction tous les termes de la suite à partir d'un nombre fini de termes initiaux et d'un nombre fini de relations de récurrence linéaire multidimensionnelles à coefficients constants.

La suite des coefficients binomiaux de l'exemple 2 n'est pas récurrente linéaire à coefficients constants car malgré la relation de Pascal, on ne peut pas déduire toutes les relations $b_{i,0} = \binom{0}{i} = 0$ pour $i \ge 1$ et $b_{0,j} = \binom{j}{0} = 1$ avec un nombre fini de conditions initiales. Elle est cependant P-récurrente, c'est à dire récurrente linéaire à coefficients polynomiaux.

**Exemple 3.** La suite $u$ définie sur $\mathbb{N}^2$ par $u_{i,j} = 2^i \cdot 3^j$ vérifie les relations $u_{i+1,j} - 2u_{i,j} = 0$ et $u_{i,j+1} - 3u_{i,j} = 0$. La donnée de $u_{0,0} = 1$ permet avec ces deux relations de calculer sans contradiction tous les termes de la suite $u$, comme on le voit en raisonnant par récurrence sur $i + j$.

Quand on connaît seulement la table constituée des termes $u_i$ tels que $|i| = i_1 + i_2 + \dots + i_n \le 2d+1$, on peut rechercher une partie $S \in \mathbb{N}^n$ et des relations de récurrence permettant de générer cette table.

**Problème 2.** Devinette de récurrence linéaire multidimensionnelle

**Entrées :** Une borne $d \in \mathbb{N}$ et la table $(u_i)_{|i| \le 2d+1}$ des $(2d+1)^n$ « premiers » termes d'une suite multidimensionnelle.

**Sorties :** Une partie $S \subset \mathbb{N}^n$ d'indices de termes initiaux à connaître et des relations permettant de générer toute la table sans contradiction.
La définition 1 suggère deux difficultés par rapport au cas unidimensionnel.

La première, rencontrée pour l'exemple 2 de la suite des coefficients bino-
miaux, est la possibilité de calculer tous les termes à partir d'un nombre finis
de conditions initiales et de relations toutes données au départ.

La seconde est la non contradiction des calculs et peut être discutée sur
l'exemple suivant, traité dans [14] page 147 et repris dans [3].

**Exemple 4.** Soit $u = (u_{i,j})_{(i,j)\in\mathbb{N}^2}$ définie par la donnée des termes initiaux
$S = \{u_{0,0}, u_{0,1}, u_{1,0}\}$ et les relations, pour tous $(i,j) \in \mathbb{N}^2$, $\{u_{i+2,j} + u_{i,j} = 0, u_{i+1,j+1} + u_{i,j} = 0, u_{i,j+2} + u_{i,j} = 0\}$.

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

Si on se donne un ordre $<$ de parcours des indices $(i,j) \in \mathbb{N}^2$, par exemple

$$
(i,j) < (i',j') \Leftrightarrow i + j < i' + j' \text{ ou } (i + j = i' + j' \text{ et } i < j),
$$

il est clair qu'on peut parcourir les termes dans cet ordre et les calculer successivement : avec la première relation si l'on se trouve sur le bord inférieur de la table, avec la dernière si l'on se trouve sur le bord latéral gauche, et avec n'importe laquelle des trois sinon. Par contre rien ne garantit a priori que dans ce dernier cas les trois calculs donneront la même valeur. En particulier, on peut combiner la première et la troisième relation pour obtenir successivement, pour tous (i,j) ∈ N² : uᵢ₊₂,ⱼ₊₁ + uᵢ,ⱼ₊₁ = 0 par translation de la première relation, et uᵢ₊₂,ⱼ₊₁ + uᵢ₊₁,ⱼ = 0 par translation de la troisième, donc uᵢ,ⱼ₊₁ - uᵢ₊₁,ⱼ = 0 par soustraction de ces deux dernières relations. On en déduit que si u₀,₁ - u₁,₀ ≠ 0, les calculs donnent des contradictions.

Pour « réparer » l'exemple précédent, il suffit de restreindre S en prenant
S = {u₀,₀, u₀,₁}, et l'ensemble de relations {uᵢ₊₂,ⱼ₊₁ + uᵢ,ⱼ₊₁ = 0, uᵢ,ⱼ₊₁ -
uᵢ₊₁,ⱼ = 0}. Le problème venait du fait que l'ensemble des relations permettait,
par combinaison, de générer une relation de support « trop petit » par rapport
au support S des conditions initiales, choisi de manière trop hâtive par rapport
au support des relations.

Plus généralement, une interprétation polynomiale des relations va per-
mettre de ramener les difficultés de la définition 1 aux notions de base de
Gröbner et d'escalier d'une base de Gröbner d'un idéal zéro dimensionnel.

1.2 Interprétation polynomiale, idéal des relations

On va associer à une suite multidimensionnelle un ensemble de polynômes
multivariés correspondant aux relations de récurrence linéaire vérifiées par la
suite.
**Définition 2.** Soit $f(\mathbf{x}) = \sum_{\mathbf{k} \in \mathcal{K}} \alpha_{\mathbf{k}} \mathbf{x}^{\mathbf{k}} \in \mathbb{K}[\mathbf{x}]$. On note $[f]_u = \sum_{\mathbf{k} \in \mathcal{K}} \alpha_{\mathbf{k}} u_{\mathbf{k}}$ de sorte que

$$ \forall \mathbf{i} \in \mathbb{N}^n, [\mathbf{x}^\mathbf{i} f]_u = 0 \Leftrightarrow \forall \mathbf{i} \in \mathbb{N}^n, \sum_{\mathbf{k} \in \mathcal{K}} \alpha_{\mathbf{k}} u_{\mathbf{k}+\mathbf{i}} = 0. $$

Lorsque cela a lieu, on dit que $f$ est le polynôme de la relation $(\alpha_{\mathbf{k}})_{\mathbf{k} \in \mathcal{K}}$ pour la suite $u$.

Ainsi pour l'exemple 2, le polynôme de la relation $b_{i+1,j+1} - b_{i,j+1} - b_{i,j} = 0$ est $P(x, y) = xy - y - 1$.

Dans la suite et en suivant [14] on identifiera un polynôme et la relation correspondante.

**Proposition 1.** L'ensemble $\mathcal{I}_u$ des polynômes de relations de la suite $u$ est un idéal de $\mathbb{K}[\mathbf{x}]$.

**Démonstration.** Soit $\mathcal{A}$ l'ensemble des suites $n$-dimensionnelles, alors

$$ \Phi_u : \begin{array}{ccc} \mathbb{K}[\mathbf{x}] & \to & \mathcal{A} \\ P & \mapsto & (\mathbf{x}^\mathbf{i} P)_u \quad_{\mathbf{i} \in \mathbb{N}^n} \end{array} $$

est un morphisme de $\mathbb{K}$-espaces vectoriels, de noyau $\mathcal{I}_u$ qui est donc un sous espace de $\mathbb{K}[\mathbf{x}]$. De plus, pour $P \in \mathbb{K}[\mathbf{x}]$ il est clair que pour tout $\mathbf{i} \in \mathbb{N}^n$, si $\Phi_u(P) = 0_{\mathcal{A}}$ alors $\Phi_u(x^\mathbf{i}P) = 0_{\mathcal{A}}$, ce qui donne par linéarité que $\mathcal{I}_u$ est bien un idéal de $\mathbb{K}[\mathbf{x}]$. $\square$

On a de plus une caractérisation simple des suites récurrentes linéaires multidimensionnelles à coefficients constants telles que nous les avons définies en suivant [3].

**Proposition 2.** La suite $u$ est récurrente linéaire multidimensionnelle à coefficients constants si et seulement si son idéal des relations est zéro dimensionnel. Dans ce cas, les relations permettant de calculer tous les termes de la suite peuvent correspondre à une base de Gröbner de l'idéal des relations $\mathcal{I}_u$ pour un ordre monomial donné, et les termes initiaux à connaître peuvent correspondre à l'escalier fini de cette base.

**Démonstration.** Si $u$ est récurrente linéaire multidimensionnelle, soit $F$ la partie finie de $\mathbb{K}[\mathbf{x}]$ telle que $\mathcal{I}_u = (F)$ et $S \subset \mathbb{N}^n$ le support fini de ses conditions initiales. Soit $\mathbf{i} \in \mathbb{N}^n$, comme on peut calculer $u_{\mathbf{i}}$ en utilisant seulement les relations de $F$ et les conditions initiales de support $S$, alors on a des coefficients $(\alpha_{\mathbf{k}})_{\mathbf{k} \in S}$ tels que $x^\mathbf{i} = \sum_{\mathbf{k} \in S} \alpha_{\mathbf{k}} x^\mathbf{k}$ mod $\mathcal{I}_u$, ainsi $\mathbb{K}[\mathbf{x}]/\mathcal{I}_u$ est de dimension finie inférieure à $|S|$ et $\mathcal{I}_u$ est bien zéro dimensionnel.

Réciproquement si $\mathcal{I}_u$ est zéro dimensionnel, soit $G$ une base de Gröbner de $\mathcal{I}_u$ pour un ordre monomial $<$ et soit $S \in \mathbb{N}^n$ le support fini de son escalier. Prenons les valeurs de $u$ sur $S$ comme conditions initiales, et les éléments de $G$ comme relations. Alors pour $\mathbf{i} \in \mathbb{N}^n$, on peut calculer la forme normale de $\mathbf{x}^\mathbf{i}$ par rapport à $G$ et $<$, ce qui nous donne des coefficients $(\alpha_{\mathbf{k}})_{\mathbf{k} \in S}$ tels que
$\mathbf{x}^i = \sum_{\mathbf{k} \in S} \alpha_{\mathbf{k}} \mathbf{x}^\mathbf{k}$ mod $\mathcal{I}_u$, on en déduit que $u_i = \sum_{\mathbf{k} \in S} \alpha_{\mathbf{k}} u_{\mathbf{k}}$ peut être calculé. Il reste à montrer que ces calculs ne mènent pas à des contradictions. Par l'absurde, supposons que l'on puisse combiner les relations de $G$ de deux manières différentes pour le calcul de $u_i$, c'est à dire que l'on ait

$$ \mathbf{x}^i = \sum_{\mathbf{k} \in S} \alpha_{\mathbf{k}} \mathbf{x}^\mathbf{k} = \sum_{\mathbf{k} \in S} \beta_{\mathbf{k}} \mathbf{x}^\mathbf{k} \quad \mod \mathcal{I}_u, $$

avec $(\alpha_{\mathbf{k}})_{\mathbf{k} \in S} \neq (\beta_{\mathbf{k}})_{\mathbf{k} \in S}$. Alors $\sum_{\mathbf{k} \in S} (\alpha_{\mathbf{k}} - \beta_{\mathbf{k}}) \mathbf{x}^\mathbf{k} \in \mathcal{I}_u$ est non nul et de support inclus dans $S$, son monôme de tête est donc dans $\mathbf{x}^S$ ce qui contredit le fait que $S$ est le support de l'escalier de $G$. $\square$

On peut revenir sur l'exemple 4 pour illustrer la partie finale de cette preuve. Les relations étaient $F = \{x^2+1=0, y^2+1=0, xy+1=0\}$, et le support des conditions initiales $S = \{(0,0), (1,0), (0,1)\}$. En prenant par exemple l'ordre $<$ du degré lexicographique avec $x < y$, $S$ est bien le support de l'escalier correspondant aux monômes de tête des éléments de $F$. Mais en calculant le S-polynôme de deux éléments de $F$ :

$$ y(x^2 + 1) - x(xy + 1) = y - x, $$

on voit que $F$ n'est pas une base de Gröbner pour $<$, donc $S$ est trop grand et peut donner lieu à des contradictions dans le calcul des termes.

La notion d'idéal des relations permet de reformuler le problème 2 en utilisant la notion de base de Gröbner.

**Problème 3.** *Devinette de récurrence linéaire multidimensionnelle, version polynomiale*

*Entrées* : Une borne $d \in \mathbb{N}$, la table $(u_i)_{i \leq 2d+1}$ des $(2d+1)^n$ « premiers » termes d'une suite multidimensionnelle, et un ordre monômial $<$.

*Sorties* : Une partie $S \in \mathbb{N}^n$ d'indices de termes initiaux à connaître et une base de Gröbner de $\mathcal{I}_u$ pour $<$, d'escalier $S$.

## 1.3 Interprétation matricielle

En dimension 1, dire que la suite $u = (u_i)_{i \in \mathbb{N}}$ est récurente d'ordre $d$ peut s'écrire matriciellement :

$$ \begin{pmatrix} u_0 & u_1 & u_2 & \dots & u_{d-1} \\ u_1 & u_2 & u_3 & \dots & u_d \\ u_2 & u_3 & u_4 & \dots & u_{d+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{pmatrix} \begin{pmatrix} -\alpha_0 \\ -\alpha_1 \\ -\alpha_2 \\ \vdots \\ -\alpha_{d-1} \end{pmatrix} = \begin{pmatrix} u_d \\ u_{d+1} \\ u_{d+2} \\ \vdots \\ \end{pmatrix}, \quad (4) $$

le fait que $u$ soit d'ordre $d$ donnant aussi qu'aucune des colonnes infinies de la matrice à gauche ne soit liée à celles qui la précèdent. On en déduit qu'on peut
jouent un rôle déterminant, elles sont exploitées dans [10] pour proposer une interprétation de l'algorithme de Berlekamp-Massey, comme on le verra dans la section 2.3.

Dans le cas multidimensionnel, on peut de manière analogue utiliser comme dans [3] des matrices $H_{T,S}$ formées à partir de deux ensembles de monômes $T$ et $S$ de $K[x]$ selon

$$H_{T,S} = \mathbf{x}^i \in T \quad \left( \begin{array}{ccc} \dots & \mathbf{x}^j \in S & \dots \\ \vdots & \vdots & \vdots \\ \dots & [\mathbf{x}^i \mathbf{x}^j]_u & \dots \\ \vdots & \vdots & \vdots \end{array} \right)$$

dont le rang sera utile dans l'algorithme Scalar -FGLM.

# 2 Solutions en Dimension 1

## 2.1 Demi-PGCD

Si on note $H(x) = \sum_{i \in \mathbb{N}} u_i x^i$ la série génératrice de la suite linéaire récurrente $u$ d'ordre $d$ et de relation

$$\forall i \in \mathbb{N}, u_{d+i} + \sum_{k=0}^{d-1} \alpha_k u_{k+i} = 0,$$

en notant $C(x) = 1 + \sum_{k=0}^{d-1} \alpha_k x^{d-k}$ le polynôme réciproque du polynôme de la relation, on observe que

$$\begin{align*} H(x)C(x) &= \left(\sum_{i \in \mathbb{N}} u_i x^i\right)\left(1 + \sum_{k=0}^{d-1} \alpha_k x^{d-k}\right) \\ &= u_0 + \cdots + \left(u_{d-1} + \sum_{k=1}^{d-1} \alpha_k u_{d-1-k}\right)x^{d-1} + \sum_{i \ge d} \left(u_i + \sum_{k=0}^{d-1} \alpha_k u_{i-d+k}\right)x^i \\ &= u_0 + \cdots + \left(u_{d-1} + \sum_{k=1}^{d-1} \alpha_k u_{d-1-k}\right)x^{d-1} \\ &= R(x), \text{ avec } \deg(R(x)) \le d-1. \end{align*}$$

Autrement dit, on a $H(x) = \frac{R(x)}{C(x)}$, avec $C$ de degré inférieur à $d$ et $R$ de degré inférieur à $d-1$.

En notant $H_N(x) = \sum_{i=0}^{N-1} u_i x^i$ pour tenir compte des données du problème 1, on est amené à chercher à résoudre

$$H_N(x)C_N(x) = R_N(x) \quad \mod x^N \qquad (7)$$
avec $L_N = \max\{\deg(C_N(x)), \deg(R_N(x)) + 1\}$ minimal.

Dans [12] il est montré que toutes les solutions de (7) avec $\deg(C_N) + \deg(R_N) < N$ sont obtenues avec les cofacteurs successifs de l'algorithme d'Euclidean étendu. Ainsi, pour résoudre le problème (1), il suffit de calculer les cofacteurs du demi-PGCD de $H_N(x)$ et de $x^N$.

Lors de ce stage, nous avons tenté, sans succès, d'étendre cette solution en dimension supérieure, comme nous le verrons à la section 3.3.

## 2.2 Berlekamp Massey

L'algorithme de Berlekamp-Massey ([2], [11]) a été initialement inventé par Berlekamp pour décoder les codes BCH. Massey a ensuite montré qu'il permettait de résoudre le problème 1 de devinette de récurrence linéaire, et il s'avère qu'il est équivalent à l'algorithme du demi-PGCD présenté dans la section précédente (voir [8]). Il s'agit de déterminer la longueur $L_N$ et des coefficients $(\alpha_k)_{k \in \{0, \dots, N-1\}}$ d'une relation de récurrence permettant de générer les $N$ premiers termes de manière itérative (on itère sur le nombre de termes connus de la suite $(u_i)_{i \in \mathbb{N}}$).

Dans [11], Lemma 1, il est d'abord établi la proposition suivante.

**Proposition 3.** Si une relation de longueur $L_N$ génère la table $(u_i)_{i \in \{0, \dots, N-1\}}$ mais pas la table $(u_i)_{i \in \{0, \dots, N\}}$, alors on a

$$L_{N+1} \geq \max\{L_N, N + 1 - L_N\}. \qquad (8)$$

L'égalité dans (8) est ensuite obtenue effectivement par le pas d'itération de l'algorithme de Berlekamp-Massey, qui combine la solution connue au rang $N$ et qui échoue à générer aussi $u_N$ avec une solution « auxiliaire » du plus grand problème de rang inférieur et dont la longueur de la solution est inférieure à $L_N$, pour obtenir une relation de longueur optimale $\max\{L_N, N + 1 - L_N\}$ générant la table $(u_i)_{i \in \{0, \dots, N\}}$. Nous ne le présentons pas en détail car il a déjà été généralisé par Sakata dans [13] pour résoudre le cas multidimensionnel (problème 3). Nous renvoyons plutôt à la description de la section 3.1, où la quantité $N + 1 - L_N$ est généralisée sous le nom de *span*.

## 2.3 Interprétation matricielle de Berlekamp Massey

Dans [10], l'algorithme de Berlekamp-Massey est interprété dans le point de vue matriciel présenté à la section 1.3. Autrement dit, il s'agit de résoudre le problème 4. L'égalité $L_N = \max\{L_N, N + 1 - L_N\}$ dans (8) est obtenue cette fois ci indépendemment du pas d'itération de l'algorithme de Berlekamp-Massey, par des considérations sur le rang de matrices de Hankel.
# 3 Solutions en dimensions supérieures

## 3.1 Berlekamp Massey Sakata

Dans le but de rapprocher les descriptions de Scalar-FGLM et de BMS, nous spécialisons à $\mathbb{K}[\mathbf{x}]$ la version de BMS donnée dans [6] dans le cadre plus général des domaines ordonnés.

Il s'agit de résoudre le problème 3. On se donne donc un entier $d$, la table $(u_i)_{|i|\le 2d+1}$ et un ordre monômial du degré total $<$. On note $T_0 = \{\mathbf{x}^i, i \in \mathbb{N}^n\} \cup \{0\}$ et on prolonge l'ordre total $<$ (qu'on continue de noter $<$) sur $T_0$ en convenant que $0 < 1$.

On va itérer sur les monômes $m \in \{\mathbf{x}^i, |i| < 2d+1\}$, en ne considérant à chaque étape que la table $([\mathbf{x}^i]_u)_{\mathbf{x}^i \le m}$. On est donc amené à définir des notions tenant compte du caractère partiel de notre connaissance de $u$ à l'étape $m$.

**Définition 3.** Soit $m \in T_0$. Soit $f \in \mathbb{K}[\mathbf{x}]$, lorsque

$$ \forall t \in T_0, LT(tf) \leq m \Rightarrow [tf]_u = 0, \qquad (9) $$

on dit que la relation $f$ est vraie jusqu'à $m$. Sinon, lorsque

$$ \forall t \in T_0, tf < m \Rightarrow [tf]_u = 0 \text{ et } \left[ \frac{m}{LT(f)} \right]_u \neq 0, $$

on dit que la relation $f$ échoue en $m$ et on définit

$$ \text{fail}(f) = m \qquad (10) $$

$$ \text{span}(f) = \frac{m}{LT(f)} \qquad (11) $$

$$ \text{disc}(f) = [\text{span}(f)f]_u. \qquad (12) $$

Enfin, si $f$ est une relation de $I_u$ on convient que $\text{fail}(f) = +\infty$.

Par linéarité, on obtient facilement les caractérisations suivantes :

**Proposition 4.** Avec les notations de la définition 3, on a :

$$ \text{fail}(f) > m \Leftrightarrow \forall g \in \mathbb{K}[\mathbf{x}], \text{LT}(gf) \leq m \Rightarrow [gf]_u = 0 \qquad (13) $$

$$ \text{span}(f) = s \Leftrightarrow \forall g \in \mathbb{K}[\mathbf{x}], \left\{ \begin{array}{l} \text{LT}(g) < s \Rightarrow [gf]_u = 0 \\ \text{LT}(g) = s \Rightarrow [gf]_u \neq 0 \end{array} \right. \qquad (14) $$

*Démonstration.* Pour montrer (13), supposons que $\text{fail}(f) > m$. Si $\text{fail}(f) = +\infty$, alors $f \in I_u$ et on a pour tout $g \in \mathbb{K}[\mathbf{x}]$ que $[gf]_u = 0$. Sinon, soit $m' = \text{fail}(m) > m$ et $g = \sum_{\mathbf{x}^i \le \text{LT}(g)} g_i \mathbf{x}^i \in \mathbb{K}[\mathbf{x}]$ avec $\text{LT}(gf) < m'$, alors $[gf]_u =$

$$ \sum_{\mathbf{x}^i \le \text{LT}(g)} g_i [\mathbf{x}^i f]_u = 0, \text{ car pour } \mathbf{x}^i \le \text{LT}(g), \text{LT}(\mathbf{x}^i f) < m'. \text{ La réciproque est directe en prenant } g = \mathbf{x}^i. \text{ Pour (14), supposons que } \text{span}(f) = s. \text{ Alors pour tout } \mathbf{x}^i < s, [\mathbf{x}^i f]_u = 0 \text{ et par linéarité on a que pour tout } g \in \mathbb{K}[\mathbf{x}] \text{ avec } \text{LT}(g) < s, [gf]_u = 0. \text{ Soit à présent } g \in \mathbb{K}[\mathbf{x}] \text{ tel que } \text{LT}(g) = s, \text{ toujours par linéarité on obtient } [gf]_u = \text{LC}(g)[sg]_u \neq 0. \text{ La réciproque est claire.} \quad \square $$
Le résultat suivant montre qu'on peut combiner des relations de même span pour obtenir une relation de span plus grand.

**Proposition 5.** Si $f$ et $f'$ sont deux relations telles que $\mathrm{span}(f) = \mathrm{span}(f')$,
alors $\mathrm{span}(f - \frac{\mathrm{disc}(f)}{\mathrm{disc}(f')}) > \mathrm{span}(f)$.

*Démonstration.* Pour tout $\alpha \in \mathbb{K}$ et pour toute relation $g$ avec $\mathrm{LT}(g) \prec \mathrm{span}(f) = \mathrm{span}(f')$ on a par linéarité $[g(f + \alpha f')]_u = 0$, de sorte que $\mathrm{span}(f + \alpha f') \succeq \mathrm{span}(f)$. Le choix de la valeur $\alpha = -\frac{\mathrm{disc}(f)}{\mathrm{disc}(f')}$ donne $[\mathrm{span}(f)(f + \alpha f')]_u = 0$, donc $\mathrm{span}(f - \frac{\mathrm{disc}(f)}{\mathrm{disc}(f')}f') \neq \mathrm{span}(f)$ et la conclusion. $\square$

On définit également les ensembles :

**Définition 4.** Avec les notations de la définition 3,

$$
\begin{align*}
I_m &= \{f \in \mathbb{K}[\mathbf{x}], m \prec \mathrm{fail}(f)\} \\
\Sigma_m &= \mathrm{LT}(I_m) \\
\sigma_m &= \min_{\prec} (\Sigma_m) \\
\Delta_m &= \mathcal{T}_0 \setminus \Sigma_m \\
\delta_m &= \max_{\prec} (\Delta_m)
\end{align*}
$$

**Exemple 5.** Revenons sur l'exemple 2 de la suite $u = \left( \begin{smallmatrix} i \\ j \end{smallmatrix} \right)_{(i,j) \in \mathbb{N}^2}$. Prenons
dans $\mathbb{K}[x,y]$ l'ordre DRL avec $x \prec y$, et $m = x^2$. On a alors :

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

En effet, il n'y a pas de relation de terme de tête 1 valide jusqu'à $x^2$ car la table n'est pas identiquement nulle. Donc $1 \notin \Sigma_{x^2}$, donc $1 \in \Delta_{x^2}$. On a aussi $y \in \Delta_{x^2}$, car les seules relations possibles de terme de tête y et valides jusqu'à y sont de la forme ky avec $k \neq 0$, et ces relations échouent en $xy \preceq x^2$ (autrement dit fail(ky) = xy). Enfin $x \in \Delta_{x^2}$, car les seules relations possibles de terme de tête x et valides jusqu'à x sont de la forme $kx + ly - k$ avec $k \neq 0$ et on a fail(kx + ly - k) = xy \preceq x^2$. Ainsi $\{1, y, x\} \subseteq \Delta_{x^2}$.

Comme par ailleurs on a les relations $y^2$, $xy - y - 1$ et $x^2 - x$ qui sont
vraies jusqu'à $x^2$, on a que $\Delta_{x^2} = \{1, y, x\}$, puis que $\delta_{x^2} = \{y, x\}$ et que $\sigma_{x^2} = \{y^2, xy, x^2\}$.
Pour $m = x^3$ on obtient :

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

car les relations $y^2$ et $xy - y - 1$ sont valides jusqu'à $x^3$, et bien qu'on ait
$fail(x^2 - x) = x^2y < x^3$, on trouve avec $x^2 - 2x + 1$ une autre relation de
monôme de tête $x^2$ valide jusqu'à $x^3$.

On remarque avec cet exemple que si $x^2 - x$ et $x^2 - 2x + 1$ sont dans $I_{x^2}$, la combinaison linéaire $x^2 - x - (x^2 - 2x + 1) = x - 1$ qui vérifie $fail(x - 1) = xy$ ne l'est pas. Ainsi $I_{x^2}$ n'est pas un idéal de $\mathbb{K}[x, y]$.

Il est cependant clair que $(I_m)_{m \in \mathcal{T}_0}$ décroît et que $\mathcal{I}_u = \bigcap_{m \in \mathcal{T}_0} I_m$. Il en résulte que $(\Delta_m)_{m \in \mathcal{T}_0}$ croît et a pour limite $\mathbf{x}^S$ l'escalier cherché, qui est fini. Ainsi pour $m$ assez grand, $\Delta_m$ donnera l'escalier cherché ce qui justifie son calcul.

On a de plus les résultats immédiats suivants :

**Proposition 6.** *Avec les notations des définitions 3 et 4, on a que*

1. $I_m$ est stable par multiplication par des éléments de $\mathbb{K}[\mathbf{x}]$,

2. pour tous $\mathbf{i}, \mathbf{j} \in \mathbb{N}^n$ tels que $\mathbf{x}^{\mathbf{i}} | \mathbf{x}^{\mathbf{j}}$,

(a) si $\mathbf{x}^i \in \Sigma_m$, alors $\mathbf{x}^j \in \Sigma_m$,

(b) si $\mathbf{x}^j \in \Delta_m$, alors $\mathbf{x}^i \in \Delta_m$.

*Démonstration.* Pour 1, soit $f \in I_m$, et $g \in \mathbb{K}[\mathbf{x}]$, alors avec (13) il est clair que $gf \in I_m$. On en déduit 2a qui est une conséquence directe, et sa contraposée 2b. $\square$

Le résultat suivant donne une caractérisation intrinsèque de $\Delta_m$ et est cru-
cial dans l'itération de BMS.

**Proposition 7.** *Pour tout monôme $m \in \mathcal{T}_0$, on a $\Delta_m = \{\operatorname{span}(f), f \notin I_m\}$. De plus, si $m \neq 0$ et si $m' \in \mathcal{T}_0$ est le prédécesseur immédiat de $m$ pour $\prec$, $\delta \in \Delta_m \setminus \Delta_{m'}$ si et seulement si $\delta | m$ et $\frac{m}{\delta} \in \Delta_m \setminus \Delta_{m'}$.*

*Démonstration.* L'inclusion $\{\operatorname{span}(f), f \notin I_m\} \subseteq \Delta_m$ est claire du fait que si $s = \operatorname{span}(f)$, alors pour tout $g \in \mathbb{K}[\mathbf{x}]$ tel que $\mathrm{LT}(g) = s$, on a d'après (14) que $\mathrm{fail}(g) \preceq m$, et donc que $s \notin I_m$, soit $s \in \Delta_m$.

Pour l'inclusion inverse $\Delta_m \subseteq \{\operatorname{span}(f), f \notin I_m\}$, raisonnons par induction sur $m \in (\mathcal{T}_0, \prec)$.

Pour $m = 0$, on a $I_0 = \mathbb{K}[\mathbf{x}]$ donc $\Delta_0 = \emptyset$.
Soit $m \ge 1$, supposons l'inclusion vraie pour tout $n < m$ et notons $m'$
le prédécesseur immédiat de $m$ pour $<$. Soit $\delta \in \Delta_m$. Si $\delta \in \Delta_{m'}$, alors par
hypothèse d'induction on a que $\delta \in \{\operatorname{span}(f), f \notin I_{m'}\}$, et comme $I_m \subseteq I_{m'}$,
on a bien $\delta \in \{\operatorname{span}(f), f \notin I_m\}$. Supposons à présent que $\delta \in \Delta_m \setminus \Delta_{m'}$. Alors
il existe une relation $f \in \mathbb{K}[\mathbf{x}]$ avec $\mathrm{LT}(f) = \delta$, et $m' < \mathrm{fail}(f) \le m$, donc
$\mathrm{fail}(f) = m$. Donc pour toute relation $g$ de terme de tête $\frac{m}{\delta}$, on a $[gf]_u = 0$ et
donc $\mathrm{fail}(g) \le m$. S'il existe une telle relation $g$ telle que de plus $\mathrm{fail}(g) = m$,
alors on aura bien $\mathrm{span}(g) = \mathrm{LT}(f) = \delta$ et donc $\delta \in \{\operatorname{span}(f), f \notin I_m\}$, avec
l'implication $\delta \in \Delta_m \setminus \Delta_{m'} \Rightarrow \delta \mid m$ et $\frac{m}{\delta} \in \Delta_m \setminus \Delta_{m'}$, qui implique sa
réciproque.

Par l'absurde, supposons que pour toute relation $g \in \mathbb{K}[\mathbf{x}]$ de terme de tête $\frac{m}{\delta}$ on ait $\mathrm{fail}(g) < m$. Alors $\frac{m}{\delta} \in \Delta_{m'}$ et par hypothèse d'induction il existe $h \notin I_{m'}$ tel que $\mathrm{span}(h) = \frac{m}{\delta}$. Avec $\mathrm{span}(f) = \frac{m}{\delta}$ et la proposition 5, on a que $\mathrm{span}(f - \frac{\mathrm{disc}(f)}{\mathrm{disc}(h)}) > \frac{m}{\delta}$. Comme $\mathrm{LT}(h) = \frac{\mathrm{fail}(h)}{\mathrm{span}(h)} = \frac{m}{\delta}$ avec $\mathrm{fail}(h) \le m' < m$, on a $\mathrm{LT}(h) \le \delta$ donc $\mathrm{LT}(f - \frac{\mathrm{disc}(f)}{\mathrm{disc}(h)}) = \delta$, donc $\mathrm{fail}(f - \frac{\mathrm{disc}(f)}{\mathrm{disc}(h)}) > \frac{m}{\delta}m = m$, ce qui contredit que $\delta \in \Delta_m$. $\square$

On en déduit que si $m \in \mathcal{T}_0$ et si $m' < m$ le précède immédiatement on a :

$$
\delta_m = \max_{<} \left( \delta_{m'} \cup \left\{ \frac{m}{s}, s \in \sigma_{m'} \cap \Delta_m \right\} \right) \quad (15)
$$

Avec cette relation, on peut construire de manière itérative un ensemble $S_m$
de relations indexées par leurs monômes de tête décrivant $\sigma_m$ et un ensemble
$D_m$ de relations indexées par leurs spans décrivant $\delta_m$.

On a vu que pour $m$ assez grand, $\Delta_m$ est l'escalier cherché. La proposition suivante quantifie cela.

**Proposition 8.** *Soit $d_{\max}$ le plus grand monôme de $\mathbf{x}^S$. Alors pour $m \succeq (d_{\max})^2$, $\Delta_m = \mathbf{x}^S$.*

Démonstration. Soit $m$ le plus petit monôme tel que $d_{\max} \in \Delta_m$, et $m' < m$
son prédécesseur immédiat. Alors $d_{\max} \in \Delta_m \setminus \Delta_{m'}$ et d'après la proposition 7,
on a $\frac{m}{d_{\max}} \in \Delta_m$, donc $\frac{m}{d_{\max}} \le d_{\max}$ et $m \le (d_{\max})^2$. $\square$

Il s'ensuit que $\mathbf{x}^S = \{\operatorname{span}(f), f \notin \mathcal{I}_u\}$. En effet d'après (14) on a $\{\operatorname{span}(f), f \notin \mathcal{I}_u\} \subseteq \mathbf{x}^S$, et d'après ce qui précède pour $m = (d_{\max})^2$, $\mathbf{x}^S = \Delta_m = \{\operatorname{span}(f), f \notin I_m\} \supseteq \{\operatorname{span}(f), f \notin \mathcal{I}_u\}$.

On peut enfin obtenir une borne pour la correction de BMS :

**Proposition 9.** *Soit $s_{\max}$ le plus grand monôme de tête des éléments de $G$ et soit $M = d_{\max} \cdot \max\{d_{\max}, s_{\max}\}$. Pour tout $m \ge M$, $S_m$ est une base de Gröbner de $\mathcal{I}_u$.*
**Algorithm 1 BMS**

**Entrée** : La table $(u)_{i_1, \dots, i_n}$, le monôme d'arrêt $m_a$, l'ordre $<$.

$m \leftarrow 1, D_m \leftarrow \emptyset, S_m \leftarrow \{1\}$

**Tant que** $m \leq m_a$ **Faire**

$D'_m \leftarrow D_m$

**Pour** $s \in S_m$ **Faire**

Si $\text{lt}(s)|m$ et $d_m^s := [\frac{m}{\text{ht}(s)}s]_u \neq 0$ alors

$D'_m(\frac{m}{\text{ht}(s)}) \leftarrow \frac{s}{d_m^s}$

$D'_m \leftarrow$ éléments de span max pour la divisibilité de $D'_m$

$T \leftarrow \min\{\mathbf{x}^i \text{ tq } \mathbf{x}^i \nmid \text{span}(D'_m)\}$

$S'_m \leftarrow \emptyset$

**Pour** $t \in T$ **Faire**

Soient $s \in S_m$ et $a$ tels que $t = sa$

Si $t \nmid m$ alors

$S'_m(t) \leftarrow \frac{t}{s}S_m(s)$

Sinon, si $\frac{m}{t} | \text{span}(D_m)$ alors

Soit $c \in D_m$ tel que $\frac{m}{t}b = \text{span}(c)$

$S'_m(t) \leftarrow S_m(s)a - [S_m(s)a\frac{m}{t}]_u bc$

Sinon

$S'_m(t) \leftarrow S_m(s)$

$S_m \leftarrow S'_m$

$D_m \leftarrow D'_m$

$m \leftarrow$ suivant de $m$ pour l'ordre

**Sortie** : $S_m$
Démonstration. D'après la proposition précédente, $\Delta_m = \mathbf{x}^S$ et donc $\sigma_m$ est bien l'ensemble des monômes de tête d'une base de Gröbner de $\mathcal{I}_u$. Il ne reste plus qu'à montrer que les éléments de $S_m$ sont bien dans $\mathcal{I}_u$. Par l'absurde, supposons que pour un certain $s \in \sigma_m$, on ait $f_s = S_m(s) \notin \mathcal{I}_u$. Alors $\mathrm{span}(f_s) \in \mathbf{x}^S$ et $\mathrm{fail}(f_s) = s \cdot \mathrm{span}(f_s) \le s_{\max} \cdot d_{\max}$, donc $f_s \notin I_m$, contradiction. $\square$

## 3.2 Scalar-FGLM

Nous décrivons ici l’algorithme Scalar-FGLM introduit dans [3], dans le but de rapprocher sa description de celle de BMS.

Comme pour BMS il s'agit de calculer une solution pour une instance du problème 3, mais cette fois ci en utilisant le point de vue matriciel déjà évoqué en 1.3 et une construction de la base de Gröbner analogue à celle de l'algorithme FGLM (voir [9]).

On ne connaît q'un nombre fini de termes de la suite $u$, on va donc devoir définir une notion de relation vraie jusqu'à un certain point.

**Définition 5.** Soit $f \in \mathbb{K}[\mathbf{x}]$ et $T$ un ensemble de monômes de $\mathbb{K}[\mathbf{x}]$, lorsque

$$ \forall \mathbf{x}^i \in T, [\mathbf{x}^i f]_u = 0, \qquad (16) $$

on dit que la relation $f$ est valide sur $T$.

Cette définition est à rapprocher de la définition 3 pour BMS, elle correspond à une inégalité sur le *fail*. Dans le cas où $T$ est un ensemble de monômes de la forme $T_m = \{t \in \mathcal{T}, t \preceq m\}$, on a en effet que $f$ est valide sur $T_m$ si et seulement si $\mathrm{fail}(f) \succ \mathrm{LT}(f)m$.

Pour $T$ et $S$ deux ensembles de monômes de $\mathbb{K}[\mathbf{x}]$ tels que $|T| \ge |S|$, la matrice

$$ H_{T,S} = \mathbf{x}^i \in T \quad \left( \begin{array}{cccc} \cdots & \mathbf{x}^j \in S & \cdots & \cdots \\ \vdots & \vdots & \ddots & \vdots \\ \cdots & [\mathbf{x}^i \mathbf{x}^j]_u & \cdots & \cdots \\ \vdots & \vdots & \ddots & \vdots \end{array} \right) $$

est de rang plein égal à $|S|$ si et seulement si ses colonnes sont indépendantes, et donc si et seulement s'il n'existe pas de relation de support $S$ qui soit valide sur $T$.

Si $S$ est maximale pour cette propriété, alors c'est un plus petit ensemble pour lequel on peut trouver des relations de supports de la forme $S \cup \{m\}$, avec $m \prec$ juste au dessus » de $S$.

C'est donc un bon candidat pour jouer le rôle de l'ensemble $\Delta$ dans BMS.

**Définition 6.** Soit $T$ une partie finie de $\mathcal{T}$, le usefull staircase $S \subseteq T$ relative à $T$ et $\prec$ est défini par :

$$ S = \min_{\prec} \left\{ \max_{\subseteq} \{S, H_{T,S} \text{ est de rang } |S|\} \right\} $$

où le minimum est pris en voyant les parties $S$ comme des $|S|$-uples à coordonnées croissantes pour $\prec$, ordonnés par l'ordre lexicographique induit par $\prec$.
Il est à noter que le usefull staircase n'est pas nécessairement stable par division, contrairement à l'escalier d'un base de Gröbner pour un ordre donné.

**Exemple 6.** Pour la suite $(0,0,1,0,...)$, pour $T = \{1,x\}$ et l'ordre du degré, on a

$$H_T = H_{T,T} = \begin{array}{c@{\;}c@{\;}c@{\;}c@{\;}c@{\;}c} & & & & & \\ & \mathbf{1} & \mathbf{x} & & & \\ & & \mathbf{0} & \mathbf{0} & & \\ & & & \mathbf{0} & \mathbf{1} & \\ & & & & \mathbf{1} & \end{array},$$

et le useful staircase est $S = \{x\}$, et ne contient pas 1. Cependant pour $T = \{1,x,x^2\}$ on a

$$H_T = H_{T,T} = \begin{array}{c@{\;}c@{\;}c@{\;}c@{\;}c@{\;}c} & & & & & \\ & \mathbf{1} & \mathbf{x} & \mathbf{x}^2 & & \\ & & \mathbf{0} & \mathbf{0} & \mathbf{1} & \\ & & \mathbf{0} & \mathbf{1} & \mathbf{0} & \\ & & & \mathbf{1} & \mathbf{0} & \mathbf{0} \\ & & & & & \end{array},$$

et on retrouve $S = \{1,x,x^2\}$ qui est l'escalier de la base de Gröbner $G = \{x^3\}$ de l'idéal des relations.

**Proposition 10.** Si $S$ est le usefull staircase relativement à la partie finie $T$ de $\mathcal{T}$ et à $\prec$, alors pour tout $m$ appartenant à la frontière de $S$, il existe une relation de support $S \cup \{m\}$ valide sur $T$.

*Démonstration.* Comme le rang de $H_{T,S \cup \{m\}}$ n'est pas $|S| + 1$ et que celui de $H_{T,S}$ est $|S|$, la dernière colonne de cette première matrice est une combinaison linéaire des précédentes et il existe donc bien une relation de support $S \cup \{m\}$ valide sur $T$. $\square$

Pour trouver cette relation, il suffit de résoudre le système linéaire non dégénéré $H_S \alpha = -H_{T,\{m\}}$.

On obtient ainsi l'algorithme 2.

**Algorithm 2 Scalar FGLM**

**Entrée :** La table $(u)_{i_1,...,i_n}$, une borne $d \in \mathbb{N}$, un ordre du degré $\prec$.

Construire $H_{T_d}$

Déterminer $S$ en extrayant une sous matrice de rang maximal

$L \leftarrow T_{d+1} \setminus \{s \in T_d, s \text{ divise un élément de } S\}$

$G \leftarrow \emptyset$

**Tant que** $L \neq \emptyset$ **Faire**

$$m \leftarrow \min_{\prec} L$$

Résoudre $H_S \alpha = -H_{T,\{m\}}$

$$G \leftarrow G \cup \{m + \sum_{s \in S} \alpha_s s\}$$

Supprimer de $L$ les multiples de $LT(G)$

**Sortie :** $G$

C'est pour l'étape de résolution du système linéaire multi-Hankel $H_S \alpha = -H_{T,\{m\}}$ que nous avons tenté d'obtenir une algèbre linéaire dédiée rapide, par le biais d'une interprétation polynomiale que nous présentons dans la partie suivante.
<figure><img src="image_5.png" /><figcaption>FIGURE 1 – interprétation polynomiale</figcaption></figure>

**Exemple 7.** En deux indices, trouver une relation de récurrence peut par exemple revenir à résoudre :

$$
\mathbf{1} \quad \begin{pmatrix} 1 & y & x & y^2 & xy \\ [1]_u & [y]_u & [x]_u & [y^2]_u & [xy]_u \\ [y]_u & [y^2]_u & [xy]_u & [y^3]_u & [xy^2]_u \\ [x]_u & [xy]_u & [x^2]_u & [xy^2]_u & [x^2y]_u \\ [y^2]_u & [y^3]_u & [xy^2]_u & [y^4]_u & [xy^3]_u \end{pmatrix} \quad \begin{pmatrix} xy^2 & c_{xy}^2 & c_{xy} & c_{xy}^2 \\ xy & c_{xy} & c_{xy}^2 & c_{xy} \\ y^2 & c_{x} & c_{x}^2 & c_{x} \\ x & c_{x} & 1 & c_{x} \end{pmatrix} = \begin{pmatrix} xy^2 & 0 & 0 & 0 \\ xy^3 & 0 & 0 & 0 \\ x^2y^2 & 0 & 0 & 0 \\ xy^4 & 0 & 0 & 0 \end{pmatrix} \quad (25)
$$

pour l'escalier $S = \{1, y, x, y^2\}$, et $m = xy$ le monôme avec lequel on cherche
une relation.

Sur la figure 1 on peut visualiser l'escalier, le monôme m à lier par la relation
à déterminer, le ppcm a_m de S ∪ {m}, le translaté de S par le facteur a_m, a_mS,
qui correspond aux termes annulés dans le second membre. Le support de C_m est
inclus dans {a_m / t ∈ S ∪ {m}}. On peut visualiser cet ensemble comme S ∪ {m}
vu depuis le repère d'origine a_m et d'axes inversés. Le support de R_m est inclus
dans les monômes diviseurs stricts de l'escalier translaté.

Cette interprétation polynomiale ne nous a pas permis d'obtenir un calcul efficace de $C_m$, les différentes tentatives échouant toutes sur des exemples élémentaires.
Références

[1] E. Berlekamp. Nonbinary bch decoding (abstr.). *IEEE Transactions on Information Theory*, 14(2):242-242, March 1968.

[2] E.R. Berlekamp. *Algebraic Coding Theory*. McGraw-Hill series in systems science. Aegean Park Press, 1984.

[3] Jérémy Berthomieu, Brice Boyer, and Jean-Charles Faugère. Linear algebra for computing gröbner bases of linear recursive multidimensional sequences. In *Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation*, ISSAC '15, pages 61–68, New York, NY, USA, 2015. ACM.

[4] Jérémy Berthomieu and Jean-Charles Faugère. Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra. In *41st International Symposium on Symbolic and Algebraic Computation*, page 8, Waterloo, ON, Canada, July 2016.

[5] R.C. Bose and D.K. Ray-Chaudhuri. On a class of error correcting binary group codes. *Information and Control*, 3(1):68–79, 1960.

[6] Maria Bras-Amorós and Michael E. O'Sullivan. The correction capability of the berlekamp-massey-sakata algorithm with majority voting. *Applicable Algebra in Engineering, Communication and Computing*, 17(5):315–335, 2006.

[7] Richard P Brent, Fred G Gustavson, and David YY Yun. Fast solution of toeplitz systems of equations and computation of padé approximants. *Journal of Algorithms*, 1(3):259–295, 1980.

[8] Jean Louis Dornstetter. On the equivalence between berlekamp's and euclid's algorithms. *IEEE Trans. Inf. Theor.*, 33(3):428–431, May 1987.

[9] Jean-Charles. Faugère, Patrizia Gianni, Daniel Lazard, and Teo Mora. Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering. *Journal of Symbolic Computation*, 16(4):329–344, 1993.

[10] Edmund Jonckheere and Chingwo Ma. A simple hankel interpretation of the berlekamp-massey algorithm. *Linear Algebra and its Applications*, 125:65–76, 1989.

[11] J. Massey. Shift-register synthesis and bch decoding. *IEEE Transactions on Information Theory*, 15(1):122–127, Jan 1969.

[12] Robert J. McEliece and James B. Shearer. A property of euclid's algorithm and an application to padé approximation. *SIAM Journal on Applied Mathematics*, 34(4):611–615, 1978.

[13] Shojiro Sakata. Extension of the berlekamp-massey algorithm to n dimensions. *Inf. Comput.*, 84(2):207–239, February 1990.

[14] M. Sala, T. Mora, L. Perret, S. Sakata, and C. Traverso. *Gröbner Bases, Coding, and Cryptography*. Springer Berlin Heidelberg, 2009.