SUR UN THÉORÈME DE DELSARTE ET MCELIECE

PHILIPPE LANGEVIN

Version du 24–9–1998

Table des matières

1. Résumé 1 2. Le théorème de McEliece 2 3. Le théorème de Delsarte-McEliece 3 4. Représentation trace 5 5. Caractères d’une algèbre semi-simple 5 6. Congruences de Stickelberger 6 7. Divisibilité 7 8. Application 8 9. Code cyclique sur ℤ/4ℤ 10 Références 10

1. Résumé

Le théorème d’Ax donne la valuation p-adique du nombre de solution d’une équation en fonction du degré. Une application directe de ce théorème fournit la divisibilité des poids des mots dans les codes de Reed-Muller. On sait que les codes de Reed-Muller peuvent être interprétés de deux façons : codes cycliques ou codes idéaux d’une algèbre non semi-simple, et cela suggère deux prolongements différents. La divisibilité des poids des mots dans le cas semi-simple est étudiée par R. McEliece et P. Delsarte [2][3][8]. Pour le cas non semi-simple dont il ne sera pratiquement pas question ici, je renvoie le lecteur à l’article de H.N. Ward [10]. Dans l’article weight congruences of p-ary cyclic codes [8] R. McEliece donne la divisibilité des poids d’un code cyclique p-aire. Dans Weights of p-ary abelian codes [2], P. Delsarte donne celle des poids des codes abéliens. Les ingrédients utilisés dans leurs preuves sont : les congruences de Stickelberger, et la transformée de Mattson-Solomon. Ils adaptent leurs démonstrations au cas général des codes abéliens q-aires dans Zeros of Functions in Finite Abelian Group Algebras [3]. Le cheminement de leurs preuves est comparable à celui utilisé par Ax. Dans cette note, je montre comment utiliser les conguences de Stickelberger, les sommes de Gauss sur les algèbres semisimple et la représentation trace des codes abéliens , exposée dans mon article Weights of Abelian Codes [6], pour aboutir à des résultats similaires. Pour conclure le rapport, je donne une application du théorème de McEliece dans la théorie des séquences.

2. Le théorème de McEliece

Soit K un corps fini de cardinal q et de caractéristique p. Soit n un entier naturel, sauf mention contraire, nous supposerons que n est premier avec p. Un code cyclique de longueur n est un idéal de l’algèbre K[X]/(X^{n} − 1). Si C est un code cyclique de longueur n, il existe un et un seul polynôme unitaire g(X) diviseur de X^{n} − 1 tel que C soit l’idéal engendré par la classe de g(X); c’est le polymôme générateur de C. Désignons par L le corps de décomposition de X^{n} − 1. L’ensemble des racines de g(X) est une partie de L^{×}: c’est l’ensemble des zéros du code C, qu’on note Z(C). Le complémentaire de Z(C) dans l’ensemble des racines n-ième de l’unités s’appelle le spectre de C, on le note S(C). Le quotient de X^{n} −1 par g(X) est noté h(X), pour mémoire, le polynôme réciproque de h(X) engendre le code orthogonal à C, c’est le polynôme de contrôle de C. Le code C est formé des polynômes c(X) = c_{0} + c_{1}X + ⋯ + c_{n_{1}}X^{n−1} qui sont multiples de g(X) modulo X^{n} − 1. L’ensemble Z(C) caractérise le code C: le polynôme c(X) de degré inférieur à n est dans le code C si et seulement si c(β) = 0, quelque soit β dans Z(C), ou encore, si et seulement si c(X)h(X) = 0. Rappelons que le poids du mot c(X) désigne le nombre de coefficients non nuls de c(X). Un code est dit d divisible si les poids de ses mots sont tous divisibles par d. On sait que la somme des poids des mots d’un code projectif de dimension k et de longueur n vaut : (q −1)q^{k−1}n, ce qui donne une première contrainte sur les valeurs possibles de d.Le théorème qui suit, prouvé par McEliece dans [8] donne une information sur la divisibilité d’un code cyclique p-aire.

Théorème 2.1. Si w désigne le plus petit entier multiple de p − 1 tel qu’il existe une séquence de w éléments dans S(C) : γ_{1}, γ_{2}, …, γ_{s} vérifiant 1 = ∏_{i=1}^{s} γ_{i} alors les poids des mots du code C sont tous de valuation p-adique supérieure ou égale à λ(C) : = \frac{w}{p−1} − 1. De plus, si h(1) ≠ 0 alors il existe un mot de valuation exactement égale à λ(C).

Ce théorème a été étendu a la classe des codes abéliens p-aire par Delsarte dans [2], puis à la classe des codes abéliens q-aire dans [3]. Plus récemment [1], A.R. Calderbank, W.-C. W. Li et B. Poonen ont donnés des résultats sur la divisibilité de certains codes cycliques construits sur des anneaux de Galois. Cet article suggère l’étude p-adique des sommes de Gauss sur un anneau de Galois, c’est un des objets de mon prochain rapport [5].

SUR UN THÉORÈME DE DELSARTE ET MCELIECE 3

3. Le théorème de Delsarte-McEliece

Désignons par f la dimension de K sur son corps premier 𝔽_{p}. Soit G un groupe abélien fini d’ordre n. L’algèbre des fonctions de G dans K est notée K^{G}, et la K-algèbre du groupe G est notée K[G]. Le produit de K^{G} est le produit terme à terme, alors que celui de K[G] est le produit de convolution : si F et F′ désignent deux fonctions de K[G] alors leur produit de convolution vaut :

F ∗ F′(t) = ∑_{x+y=t} F (x)F′(y) = ∑_{x∈G} F (x)F′(t − x)

L’ensemble des fonctions qui s’annulent partout sauf en un point de G forme un groupe isomorphe à G que nous identifions à G. Si g désigne un élément de G alors g désigne la fonction :

g(x) = \begin{cases}1, & si g = x; \\ 0, & sinon. \end{cases}

Un code abélien q-aire est un idéal de la K-algèbre de groupe K[G]. La notion de code abélien généralise la notion de code cyclique puisque l’algèbre K[ℤ/nℤ] est isomorphe à l’algèbre K[X]/(X^{n} − 1). L’algèbre K[G] est semi-simple, rappellons la construction d’un isomorphisme entre K[G] et un produit de corps, pour les détails voir [3]. On sait que le groupe G est isomorphe à un produit de m groupes cycliques Z/(n_{1}) × Z/(n_{2}) × ⋯ × Z/(n_{m}), où pour chaque i inférieur à m, n_{i} divisise n_{i+1}. Notons e_{1}, e_{2}, …, e_{m} une base de G pour laquelle chaque élément x de G se décompose d’une et une seule fao̧n comme une somme x_{1}e_{1} + x_{2}e_{2} + ⋯ + x_{m}e_{m}, les entiers x_{i} compris entre 0 et n_{i} − 1. Soit L le corps des racines de X^{n_{s}} − 1. Pour chaque i, choisissons un élément ζ_{n_{i}} d’ordre n_{i} dans L^{×} et considérons l’application de G × G dans L définie par :

< x, y >= ∏_{i=1}^{m} ζ_{n_{i}}^{x_{i}y_{i}}

La transformée de Fourier envoie K[G] dans L^{G}. L’image de F est la fonction de G dans L définie par F̂(z) = ∑_{g∈G} f(g) < g, z >. Elle satisfait :

{ \atop F ∗ F′} = F̂F̂′ (1)

La transformation de Fourier est inversible à gauche. On retrouve la fonction F par :

F (z) = \frac{1}{n} ∑_{g∈G} F̂(g) < g, −z > .

Maintenant, caractérisons l’image de K[G]. Soient S_{1}, S_{2}, …, S_{s} les orbites de G sous l’action de la permutation g ↦ qg, notons f_{j} le cardinal de S_{j} et notons K_{j} l’extension de degré f_{j} de K dans L. L’image de K[G] par cette transformée de Fourier est formée des applications F de G dans L vérifiant la condition :

F (g)^{q} = F (qg), ∀g ∈ G. (2)

En particulier : si g ∈ S_{j} alors F (g) ∈ K_{j}. Pour chaque entier j, 1 ≤ j ≤ s, faisons le choix d’un élément a^{(j)} dans S_{j}. Soit F ∈ K[G]. La transformée de Fourier de F est complètement déterminé par le s-uplet

F̃ = (F̂(a^{(1)}), F̂(a^{(2)}), …, F̂(a^{(s)}))

du produit K_{1} × K_{2} × ⋯ × K_{s}. La formule de trivialisation (1) montre que F ↦ F̃ est un isomorphisme de algèbre K[G] sur l’algèbre produit K_{1} × K_{2} × ⋯ × K_{s}.

Soit g un élément de G, g̃ vaut :

( < g, a^{(1)} >, < g, a^{(2)} >, …, < g, a^{(s)} > )

Et plus particulièrement :

ẽ_{i} = (ζ_{n_{j}}^{a_{i}^{(j)}})_{1≤j≤s}, ∀i, 1 ≤ i ≤ m. (3)

Chaque idéal I du produit direct K_{1} × K_{2} × ⋯ × K_{s} est caractérisé par son support supp(I); c’est l’ensemble formé des indices i tels que la projection y ↦ y_{i} restereinte à I n’est pas la forme nulle. L’ensemble des zéros d’un code abélien C est :

Z(C) = ∪_{i∉supp(Ĉ)}S_{i}

c’est une partie de G, son complémentaire dans G est noté S(C); c’est le spectre de C. Bien entendu, lorsque G est cyclique , ces définitions coincident avec celles de la section précédente.

Soit C un idéal de K[G], notons w la valeur du plus petit entier w tel qu’il existe, d’une part, des éléments a_{1}, a_{2}, …,a_{w} non tous nuls dans S(C), et d’autre part, des entiers naturels t_{1},t_{2}, …,t_{w} strictement inférieur à f vérifiant :

\begin{aligned}∑_{i=1}^{w} p^{t_{i}} & ≡ 0 (mod q − 1) \\ ∑_{i=1}^{w} p^{t_{i}}a_{i} & = 0. \end{aligned} (4)

A cause de la première condition, un tel entier est nécessairement multiple de p−1, on note λ(C) : = \frac{w}{p−1} −1. Nous pouvons énoncer le théorème de Delsarte-McEliece. Leur preuve [3] est basée sur la transformée de Mattson-Solomon. Dans les sections 4 à 7, je prouve ce théorème en utilisant la représentation trace des codes abéliens, les congruences de Stickelberger, et les sommes de Gauss dans les algèbres semi-simples.

Théorème 3.1. Il existe un polynôme R dans 𝔽_{p}[X_{1}, X_{2}, …, X_{d}] qui envoie K_{i_{1}} × K_{i_{2}} × ⋯ × K_{i_{d}} dans 𝔽_{p} qui n’est pas nul sur K_{i_{1}} × K_{i_{2}} × ⋯ × K_{i_{d}} et tel que pour chaque F ∈ C:

Z(F) ≡ f_{0}n + p^{λ}R(x_{1}, x_{2}, …, x_{d}) (mod p^{λ+1}), (5)

où f_{0} vaut 1 si ∑_{g∈G} f(g) = 0 et 0 sinon.

4. Représentation trace

Soit ann(C) l’annulateur du code abélien C. Notons A l’algèbre quotient k[G]/ann(C). A partir de la forme trace de A sur K, notée Tr_{A/K}, nous construisons un encodeur μ_{G,A} qui envoie A dans K[G] de la façon suivante :

a ⟶^{μ_{G,A}} ∑_{g∈G} Tr_{A/K}(ag)g^{−1} (6)

Cet encodeur, bien connu dans le cas des codes cycliques irréductibles, est présenté dans mon article weight of abelian codes [6]. On constate que si l’annulateur de C est sans élément nilpotent, on dit aussi que C est dans le socle de k[G], alors l’algèbre A est semi-simple, et l’image de A par μ_{G,A} est exactement égal au code C, que l’algèbre K[G] soit semisimple ou pas. C’est ce que j’appelle une représentation trace du code C. Cette approche, nous conduit au problème suivant. Etant donné , une algèbre semi-simple A, un sous-groupe G de A^{×}, un élément a de A et un élément b ∈ K; Quel est le nombre N(a, G, b) de solutions g de l’équation

Tr_{A/K}(ag) = b, g ∈ G (7)

Le nombre N(a, G, b) s’exprime en termes de sommes de Gauss dont les développement P -adiques sont bien connus depuis Stickelberger, d’où l’on tire la divisibilité d’un code abélien.

5. Caractères d’une algèbre semi-simple

Soit A une K-algèbre semi-simple et soit G un sous-groupe quelconque du groupe des inversible de A. Il existe s extensions K_{1}, K_{2}, …, K_{s} du corps K telles que A soit isomorphe au produit direct K_{1} × K_{2} × … × K_{s}. Les caractères multiplicatifs et additifs de A sont les caractères produits. En particulier, le produit des caractères canoniques est noté μ_{A} et si χ désigne un caractère multiplicatif de A alors nous notons G_{A}(χ) la somme de Gauss :

G_{A}(χ) = ∑_{a∈A^{×}} χ(a)μ_{A}(a) = ∏_{i=1}^{s} G_{K_{i}}(χ_{i})

L’intérêt de ces sommes de Gauss est de donner une formule sur le nombre, N(a, G, b), de composantes égales à b dans le mot μ_{G,A}(a) lorsque a est inversible dans A.

Proposition 5.1. Soit A une K-algèbre commutative semi-simple, et soit a un élément inversible de A. Le nombre d’éléments g du groupe G de solution de l’equation Tr_{A/K}(ag) = b est donné par :

N(a, G, A, 0) = \frac{n}{q} + \frac{n(q − 1)}{q|A^{×}|} ∑_{χ∈(GK^{×})^{⊥}} G_{A}(χ, μ_{A})χ̄(a) (8)

et pour c ≠ 0,

N(a, G, A, c) = \frac{n}{q} + \frac{n}{|A^{×}|} ∑_{χ∈G^{⊥}} G_{A}(χ, μ_{A})χ̄(a) (9)

Démonstration. C’est une application des sommes d’Eisenstein, et de la formule de Poisson. Voir mon article [6].

Si a est non-inversible, mais non nul, alors on se ramène à la proposition précédente. Tout d’abord, notons S le support de a, c’est l’ensemble {i | a_{i} ≠ 0}, et notons A_{S} l’algèbre support : A_{S} = ⊕_{i∈S}K_{i}. L’image de G par la surjection canonique est notée G_{S}, celle de a est notée a_{s}. Avec ces notations, le mot μ_{G,A}(a) apparaît comme une répétition du mot μ_{G_{S},A_{S}}(a_{S}). Le facteur de répétitions est égal à l’indice de G_{S} dans G.

6. Congruences de Stickelberger

Désignons respectivement par ℤ_{p} et par ℚ_{p} l’anneau des entiers et le corps des nombres p-adique. Dans la clôture algébrique de ℚ_{p}, faisons le choix d’une racine primitive n-ième de l’unité ξ, ainsi que le choix d’une racine π de l’ équation X^{p−1}+p = 0. Par caractère de G, nous entendons homomorphisme de G dans le groupe multiplicatif du corps ℚ_{p}(ξ, π). Les relations d’orthogonalités montrent que si l’ordre de G est premier avec p, ce que nous supposerons implicitement, alors les caractères de G sont indépendants modulo (π), dans l’anneau ℤ_{p}[ξ, π]. Soit f l’ordre multiplicatif de p modulo n. L’anneau quotient ℤ_{p}[ξ]/(p) est un corps à p^{f} éléments, notons le L. A ce stade, nous pouvons construire deux caractères canoniques de L. Le caractère additif canonique μ_{L}(x) = ζ^{Tr_{L/𝔽p}(x)}, où ζ est l’unique racine p-ième de l’unité telle que ζ ≡ 1 + π modulo π^{2}. Le caractère multiplicatif de Teichmuller qui envoie la classe de ξ sur ξ, que nous noterons ω. Pour chaque caractère multiplicatif χ de L notons G_{L}(χ) la somme de Gauss :

∑_{x∈L^{×}} χ(x)μ_{L}(x).

Théorème 6.1 (Stickelberger). Soit a un entier, 0 ≤ a ≤ q − 1 :

G_{L}(ω^{a}) = −\frac{π^{S(a)}}{ρ(a)} (mod π^{S(a)+1})

où S(a) = ∑_{i=0}^{f−1} a_{i}, ρ(a) = ∏_{i=0}^{f−1} a_{i}!, avec a = ∑_{i=0}^{f−1} a_{i}p^{i}.

Ce sont les fameuses congruences de Stickelberger [9].

7. Divisibilité

Soit a un élément de support S. Notons Γ_{S} l’orthogonal du groupe G_{S}K^{×}. Désignons par Ω_{S} l’ensemble des caractères non triviaux de Γ_{S} dont la somme de Gauss est de valution π-adique minimale, et notons ν_{S} cette valeur. De la proposition (5.1), on tire sur le champ :

N(a, G, 0) = \frac{n}{q}[1 + \frac{(q − 1)(−1)^{s}}{|A_{S}^{×}|} + π^{ν_{S}} ∑_{χ∈Ω_{S}} a(χ)χ̄(a) + O(π^{ν_{S}})] (10)

Où les a(χ) sont des inversibles dans ℤ_{p} qu’il est inutile de préciser. Posons w : = inf_{S}{ν_{S}}, c’est un entier inférieur au produit (p − 1)f.f_{j} quelque soit j. Le poids de du mot μ_{G,A} s’écrit :

W (a, G) = \frac{n}{q}[C(S) − π^{ν_{S}} ∑_{χ∈Ω_{S}}a(χ)χ̄(a) + O(π^{ν_{S}})] (11)

où C(S) est un entier de valuation π-adique supérieure ou égale à min_{j∈S}{(p − 1)ff_{j}}, donc supérieure à w.

Théorème 7.1. Tout les poids du code C sont de valuation p-adique supérieure ou égale à celle de n augmentée de \frac{w}{p−1} − f. Et si n est premier avec p alors il existe un mot dont le poids est de valuation \frac{w}{p−1} − f

Démonstration. La première partie est évidente. Pour la seconde partie, rappellons que si n est premier avec p alors les caractères de G sont indépendants modulo p.

Reste à déterminer la valeur de w. Pour chaque entier j, χ_{j} désigne le caractère de Teichmuller du corps 𝔽_{q_{j}}. Le caractère ×_{j∈S}χ_{j}^{α_{j}} est dans Γ_{S} si et seulement si :

\begin{aligned}∑_{j∈S} α_{j}a^{(j)} & = 0, \\ et \\ ∑_{j∈S} α_{j} & ≡ 0 (mod q − 1). \end{aligned} (12)

En effet. La congruence caractérise l’orthogonalité du caractère ×_{j∈S}χ_{j}^{α_{j}} par rapport à K^{×}. Nous pouvons choisir les ζ_{n_{j}} de sorte que χ_{j}(ζ_{n_{j}}) = exp(\frac{2iπ}{n_{j}}). Le caractère ×_{j∈S}χ_{j}^{α_{j}} est dans l’orthogonal de G_{S} si et seulement si :

∀i, ×_{j∈S}χ_{j}^{α_{j}}(e_{i}) = 1 ⟺ ∀i, ∑_{j∈S} \frac{α_{j}a_{i}^{(j)}}{n_{j}} ∈ ℤ ⟺ ∑_{j∈S} α_{j}a^{(j)} = 0.

Il résulte des congruences de Stickelberger (6.1) et des conditions (12) que l’entier w du théorème est :

min_{S} min_{α} ∑_{j∈S} S(α_{j}). (13)

où S varie dans l’ensemble des parties de {1, 2, …, s}, et où pour chaque S, α décrit l’ensemble des vecteurs non nuls satisfaisant les conditions (12) .

Théorème 7.2 (Delsarte). Soit C un code cyclique projectif de dimension k et de longueur n. Si tous les poids des mots de C sont divisibles par 2^{r} alors on a l’alternative : r = k −1 et le code est un code simplexe de longueur (p^{k} − 1), ou bien, r ≤ [\frac{k}{2} − \frac{1}{p−1}].

8. Application

Je propose de donner une application, due à G. McGuire et A.R. Calderbank [4], du théorème de McEliece à la théorie des m-séquences. Il s’agit de prouver la proposition suivante, conjecturée par D.V. Sarwate et M.B. Pursley dans [7]

Proposition 8.1. Il n’existe pas de bonne paire de m-séquences lorsque m multiple de 4.

Commençons par expliquer le vocabulaire. Soit m un entier, et soit α une racine primitive du corps 𝔽_{2^{m}}. Pour chaque entier t premier avec 2^{m} − 1, on définit une m-séquence binaire S_{t} en posant :

S_{t}(i) = (−1)^{Tr_{𝔽_{2^{m}}/𝔽_{2}}(α^{it})}

Rappelons que l’intercorrélation de deux séquences S et S′ de période n est la fonction S × S′ définie en τ par :

S × S′(τ) = ∑_{i=0}^{n−1} S(i)S′(i + τ)

où la somme de i et τ est calculée modulo n. Par définition, une bonne paire de m-séquences, est un couple de m-séquences (S, S′) dont la fonction d’intercorrélation prend les trois valeurs −1, −1 + ±2^{⌊ \frac{m+2}{2} ⌋}. Pour m impair, ou bien pour m congru à 3 modulo 4, il existe des bonnes paires de m-séquences. Et la proposition 8.1 affirme que pour m multiple de 4 il n’ existe pas de bonne paire de m-séquences. Pour le démontrer, il suffit de considérer un entier t premier avec 2^{m} − 1, et de montrer qu’il n’existe pas de bonne paire de la forme : S_{1}, S_{t}. Notons que les valeurs de l’intercorrélation des séquences S_{1} et S_{t} sont de la forme :

2^{m} − 1 − 2wt(c)

SUR UN THÉORÈME DE DELSARTE ET MCELIECE 9

où c décrit l’orthogonal du code cyclique C engendré par le produit des polynômes minimaux de α et α^{t}. En particulier, la paire de séquences est bonne si et seulement si les poids du codes C sont de la forme :

2^{m−1} − 2^{\frac{m}{2}} , 2^{m−1}, 2^{m−1} + 2^{\frac{m}{2}} .

En particulier, la valuation 2-adique mimimale du poids d’un mot de C est supérieure ou égale à ⌊\frac{m}{2}⌋.

L’entier t inversible modulo q − 1 est a fortiori inversible modulo 15. Dans la table ci-dessous, on donne pour chaque inversible t l’entier v tel que tv = −1 modulo 15 :

\begin{matrix}t & 1 & 2 & 4 & 7 & 8 & 11 & 13 & 14 \\ v & 14 & 7 & 11 & 2 & 13 & 4 & 8 & 1 \end{matrix}

• Premier cas : t ∈ {7, 11, 13, 14}. On a :

\begin{aligned}1 + tv & = 0 (mod 15) \\ \frac{2^{m}}{15} + tv \frac{2^{m}}{15} & = 0 (mod 2^{m} − 1) \end{aligned}

Il existe un mot c dont le poids est de valuation 2-adique exactement égale à :

wt(\frac{2^{m}}{15} ) + wt(v \frac{2^{m}}{15} ) − 1 = \frac{m}{2} − 1;

et donc la paire ne peut pas être bonne.

• Deuxième cas : t ∈ {7, 11, 13, 14}. On ne peut plus procéder comme précédemment. La preuve repose sur une élégante application des formule de MacWilliams. Le nombre de mots de poids 3 dans C^{⊥} est donné par les formules de MacWilliams : c’est \frac{2^{m}−1}{3}. Par ailleurs, la matrice ci-dessous est une matrice de contrôle de C:

(\begin{matrix}1 & α & α^{2} & … & α^{2^{m}−1} \\ 1 & α^{t} & α^{2t} & … & α^{(2^{m}−1)t} \end{matrix})

Le nombre de mot de poids 3 de support {0, i, j} est égal au nombre de solutions du système :

x^{t} + y^{t} = 1; x + y = 1; x ≠ y; x ∈ 𝔽_{2^{m}} − {0, 1}

dont la résolution est équivalente à l’équation :

(x + 1)^{t} + x^{t} = 1, x ∈ 𝔽_{2^{m}} − {0, 1}.

Or l’hypothèse faite sur t montre que tous les éléments de 𝔽_{16} sont solutions de cette équation, et donc le nombre de mot de poids 3 est supérieur à 14(\frac{2^{m}−1}{3}) ce qui est contradictoire.

9. Code cyclique sur ℤ/4ℤ

Soit C un code cyclique binaire. Un relèvement de C est un code sur l’alphabet ℤ/2^{ℓ}ℤ dont la restriction modulo 2 est égale à C. Le procédé immédiat qui consiste à prendre la même matrice génératrice ne conserve pas la cyclicité. A cause de cela, on utilise le relèvement de Hensel.

Soit f et g deux polynômes de 𝔽_{2}[X] unitaires tel que f(x)g(x) = X^{n}−1. A l’aide du lemme d’Hensel, on construit une suite de couples de polynômes unitaires (f_{l}(X), g_{l}(X)) à coefficients dans l’anneau quotient ℤ/2^{ℓ}ℤ tel que :

f_{ℓ}(X) ≡ f(X) (mod 2), g_{ℓ}(X) ≡ g(X) (mod 2),
f_{ℓ}(X)g_{ℓ}(X) ≡ X^{n} − 1 (mod 2^{ℓ}).

Le ℓ-ième relevé du cyclique C engendré par g(X) est le code cyclique à composante dans ℤ/2^{ℓ}ℤ engendré par f_{ℓ}(X). Notons le C(ℓ). Les suites f_{ℓ}(X) et g_{ℓ}(X) convergent dans ℤ_{2}[X] respectivement vers f_{∞} et g_{∞}. La limite projective C(∞) des C(ℓ) est égale au code cyclique engendré par g_{∞}(X).

GR(2^{ℓ}, f)
↓
ℤ_{2}[X]/(h_{∞}(X)) ⟶ ℤ[X]/(2^{ℓ}, h_{ℓ}(X)) ⟶ 𝔽_{2}[X]/(h(X))
↓  ↓  ↓
C(∞)  ⟶  C(ℓ)  ⟶  C

où les flèches horizontales sont des réductions et les flèches verticales des encodeurs.

Théorème 9.1. Avec les notations du théorème 1. Soit a ∈ ℤ/2^{ℓ}ℤ. Le nombre de composantes égale à a dans un mot du code C(ℓ) est divisible par 2^{⌈ \frac{w}{2^{ℓ−1}} ⌉−2}.

Dans leur article Calderbank, Li et Poonen utilisent une transformation de Mattson à valeurs dans l’anneau de Galois GR(2^{ℓ}, f) et des ingrédients d’analyse p-adique. On peut sans aucun doute démontrer ce théorème par une méthode analogue à celle que j’ai présentée ici dans le cas des corps finis. Il faut définir des sommes de Gauss sur les anneaux de Galois et etudier leur divisibilité. C’est l’objet d’un travail en cours [5]

Références

[1] W.-C. W. Li et B. Poonen A.R. Calderbank. A 2-adic approach to the analysis of cyclic codes. IEEE trans. Inf. th., 43(3):977–986, 1997.

[2] P. Delsarte. Weight of p-ary abelian codes. Philips Res. Rep., 26:145–153, 1971.

[3] P. Delsarte et R.J. McEliece. Zeros of functions in finite abelian group algebras. Amer. Journal of Math., 98:197–224, 226.

[4] A.R. Calderbank G. McGuire. Proof of a conjecture of sarwate and pursley regarding pairs of binary m-sequence. IEEE transactions on Inf. Theory, 41(4):1153–1155, 1995.

[5] P. Langevin. Sommes de gauss sur un anneau local. Em preparation, 1998.

[6] P. Langevin. Weight of abelian codes. Designs Codes Cryptography, 1998.

[7] D.V. Sarwate M.B. Pursley. Cross correlation properties of pseudo-random and related sequences. Proc. IEEE, 68:593–619, 1980.

[8] R.J. McEliece. Weight congruences for p-ary cyclic codes. Discr. Math., 3:177– 192, 1972.

[9] J. Stickelberger. Uber eine verallgemeinerung der kreistheilung. Math. Ann., 37:321–367, 1890.

[10] H. N. Ward. Divisors of codes of reed-muller type. Discrete Math., 131:311–323,

12 PHILIPPE LANGEVIN

I3S, 250 Av. A. Einstein, 06560 Valbonne, France.