Upload
others
View
6
Download
0
Embed Size (px)
Citation preview
M�moire pr�sent� en vue de l�obtentionde l�Habilitation � Diriger des Recherches
Universit� de Toulon�Var
par
Alexis BONNECAZE
Arithm�tique et combinatoire des
codes lin�aires sur des anneaux �nis
Pr�sent�e le �� Decembre ����
Membres du Jury �
M� Eichi Bannai RapporteurM� Johny Bond ExaminateurM� Fran�ois Rodier RapporteurM� Sami Harari ExaminateurM� Tor Helleseth RapporteurM� Patrick Sol� DirecteurM� Jacques Wolfmann Examinateur
Universit� de Toulon � Var� Laboratoire SIS
�
�
Remerciements
Je voudrais exprimer toute ma reconnaissance aux membres du jury
tout d�abord � Patrick Sol� directeur de recherches au CNRS pour sonaide sa disponibilit� et son soutien constants malgr� des responsabilit�s im�portantes et un emploi du temps charg� c�est son enthousiasme toujoursaussi communicatif pour la recherche qui m�a permis de continuer ce m�tier
qu�il trouve ici l�expression de toute ma gratitude
� Messieurs Eichi Bannai Professeur � l�universit� de Kyushu �Japon�Tor Helleseth Professeur � l�universit� de Bergen �Norvge� et Fran�ois Ro�dier directeur de recherches au CNRS qui m�ont fait l�honneur d�accepterd�examiner mon travail et d�en �tre les rapporteurs en particulier Tor Hel�leseth a fait le voyage de Norvge pour assister � ma pr�sentation
� Messieurs Sami Harari et Jacques Wolfmann tous deux Professeurs �l�universit� de Toulon ainsi que Monsieur Johny Bond Professeur � l�univer�sit� de Nice �ESSI� qui ont �galement accept� de faire partie de mon jury�
Je tiens � remercier mes coauteurs avec qui j�ai eu beaucoup de plaisir �travailler � C� Bachoc S� Boztas J��C� Bermond C� Bonnecaze P� Gaborit R�Calderbank I� Duursma M� Harada M� Kitazume T� Kodate B� MourrainS� Perennes E� Rains P� Sol� et P� Udaya�
Mes remerciements vont �galement � Monsieur Claude Carlet Professeur� l�universit� de Paris � pour ses conseils qui me furent pr�cieux lors de lar�daction du document�
Je remercie les membres de l��quipe informatique du laboratoire SIS pourleur soutien amical et tout particulirement Monsieur Alban Gabillon� Jen�oublie pas non plus les membres du laboratoire GRIM avec qui j�ai eu desdiscussions fructueuses et anim�es�
Je remercie aussi mes nouveaux amis du projet SAGA � l�INRIA toujourspr�ts � rendre service et dont les discussions m�apportent beaucoup�
En�n je tiens � remercier Madame Elisabeth Elophe ainsi que MadameRemusat pour leur gentillesse et disponibilit��
�
Table des mati�res
� Introduction �
� Les codes quaternaires ��
��� Les codes binaires � � � � � � � � � � � � � � � � � � � � � � � � � ����� Relation entre un code et son dual � � � � � � � � � � � � � � � ����� Les codes de Kerdock et Preparata � � � � � � � � � � � � � � � ����� Les codes sur Z� � � � � � � � � � � � � � � � � � � � � � � � � � ����� Description par les anneaux de Galois � � � � � � � � � � � � � � ��
����� Le relvement de Hensel � � � � � � � � � � � � � � � � � ������� L�anneau de Galois R � GR��� m� � � � � � � � � � � � � ��
��� La bonne d��nition des codes de Kerdock et Preparata � � � � ��
� Les di��rents th�mes de recherche ��
��� Les codes d��nis sur Z� � � � � � � � � � � � � � � � � � � � � � � ������� Codes de type II binaires � � � � � � � � � � � � � � � � � ������� Th�orie des invariants � � � � � � � � � � � � � � � � � � ������� Codes auto�duaux et th�orie des invariants sur Z� � � � ������� R�seaux arithm�tiques � � � � � � � � � � � � � � � � � � ������� Translat�s des codes sur Z� � � � � � � � � � � � � � � � ��
��� Propri�t�s combinatoires des codes � � � � � � � � � � � � � � � ������� Le cas binaire � � � � � � � � � � � � � � � � � � � � � � � ������� Le cas quaternaire � � � � � � � � � � � � � � � � � � � � ������� Le cas Q�aire � � � � � � � � � � � � � � � � � � � � � � � ��
��� Codes sur F� � uF� � � � � � � � � � � � � � � � � � � � � � � � � ������� Codes cycliques sur Z� et F� � uF� � � � � � � � � � � � ������� Longueurs �� et �� � � � � � � � � � � � � � � � � � � � � ��
��� Une application � la th�orie des graphes � Di�usion dans l�hy�percube � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Chronologie scienti�que � � � � � � � � � � � � � � � � � � � � � ��
� Perspectives ��
��� Projets � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������� D�codage des codes g�om�triques � � � � � � � � � � � � ������� Etude et d�codage des codes quasi�cycliques � � � � � � ������� Projets et contrats � � � � � � � � � � � � � � � � � � � � ��
�
� TABLE DES MATI�RES
��� DESS S�curit� informatique � � � � � � � � � � � � � � � � � � � ��
� Curriculum vit publications et bibliographie ��
��� Curriculum vit� � � � � � � � � � � � � � � � � � � � � � � � � � ����� Titres universitaires fran�ais � � � � � � � � � � � � � � � � � � � ����� Parcours professionnel � � � � � � � � � � � � � � � � � � � � � � ��
����� Laboratoire d�informatique signaux et systme de Sophia�Antipolis � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Royal Melbourne Institute of Technology � � � � � � � � ������� Universit� de Toulon�Var � � � � � � � � � � � � � � � � � ������� D�l�gation � l�INRIA � � � � � � � � � � � � � � � � � � � ��
��� Publications � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Cadre g�n�ral
La th�orie des codes correcteurs d�erreurs est n�e � la �n des an�n�es quarante� A cette �poque Richard Hamming partageait son bureau duBell�Labs avec Claude Shannon� Il avait accs le week�end � un ordinateurpour faire ex�cuter ses programmes d�analyse num�rique� Malheureusementceux�ci �taient constamment interrompus par des perturbations d�tect�espar l�ajout de bits de parit�� Dans le m�me temps Claude Shannon montraitqu�un certain taux d�erreur dans une communication �tait in�vitable ind��pendamment de la qualit� du mat�riel� Hamming eut alors la re�exion sui�vante � Si l�ordinateur parvient � d�celer une erreur pourquoi ne parviendrait�il pas � corriger cette erreur �Ainsi naquit le code de Hamming un code qui permet de corriger une
erreur� Le message � transmettre �par exemple une suite de bits� est d�coup�en paquets �ou mots de code� de longueur n� Parmi ces n bits seulement kbits portent l�information �ce sont les bits d�information� les n � k restant�les bits de contr�le� sont utilis�s pour corriger les erreurs survenues dansles k bits d�information� L�ensemble des mots est appel� un code en bloc�Dans la pratique les bits de contr�le sont calcul�s de telle sorte que les motssoient trs distincts les uns des autres� Si les mots du code sont deux � deuxdistincts sur d � �t� positions un mot recu ayant au plus t erreurs pourraais�ment �tre corrig� en le mot de code le plus proche� Le code compos�des mots
et pourra par exemple corriger jusqu�� deux erreurspuisque ses deux mots sont distants de cinq bits�La th�orie des codes correcteurs d�erreurs est donc di��rente de la cryp�
tographie car il ne s�agit pas ici de se pr�munir contre un ennemi malveillantmais contre des perturbations naturelles lorsque l�on veut transmettre oustocker de l�information�Aussi surprenant que cela puisse para�tre lorsque l�on �tudie son principe
de base la th�orie des codes se trouve � l�intersection de nombreux domainesdes math�matiques comme l�algbre la g�om�trie la combinatoire ou lesmath�matiques discrtes� Ainsi des structures combinatoires int�ressantespeuvent �tre observ�es dans certains codes� C�est le cas du code de Hammingqui contient des systmes de Steiner ou des codes de Reed�Solomon qui sontreli�s aux carr�s latins� Dans le domaine de la th�orie des groupes le code deGolay lui sert � construire le r�seau arithm�tique de Leech dont on connaitl�importance dans la construction des grands groupes simples sporadiques�
�
� TABLE DES MATI�RES
Chapitre �
Introduction
Au d�but des ann�es �� certains chercheurs ont �t� amen�s � introduireun nouvel alphabet pour construire des codes� Contrairement � la traditioncet alphabet de quatre �l�ments admet une structure d�anneau et non decorps� C�est Z� l�anneau des entiers modulo quatre� L�introduction de cescodes dits aussi codes quaternaires a alors �t� per�u comme un �v�nementconsid�rable au sein de la communaut� des codeurs�J�ai d�but� mon travail de recherche dans cette mouvance en novembre �����Mon objectif �tait de construire et d��tudier de bons codes sur Z� et plus g��n�ralement sur des anneaux �nis� Certains codes r�vlent en e�et leur vraiestructure lorsqu�ils sont d��nis sur un alphabet appropri�� Avec mon direc�teur de thse P� Sol� nous nous sommes tout d�abord int�ress�s aux codesauto�duaux et � leurs liens avec les r�seaux arithm�tiques� L��tude des codesd��nis sur des anneaux �nis fait appel � de la th�orie de galois� Cependantin�uenc� par la lecture de livres traitant de combinatoire et fascin� par lec�lbre MOG de Curtis j�ai aussi souhait� orienter mes recherche sur lespropri�t�s combinatoires de ces codes� Je me suis alors appuy� sur le travailde Ozeki qui ds ���� s�int�resse aux polyn�mes de Jacobi� Coupl�s avecla th�orie des invariants nous avons utilis� ces polyn�mes pour obtenir desr�sultats int�ressants sur les propri�t�s des codes� La th�orie des invariantsn�est pas nouvelle � elle date du dix�neuvime sicle � mais l�utilisation quenous en avons faite nous semble innovante� L�association de ces deux outils�polyn�mes de Jacobi et th�orie des invariants� permet de calculer l��nu�m�rateur de poids des translat�s de codes binaires auto�duaux� Elle permetaussi de d�tecter la pr�sence d�objets combinatoires tels que des designs ou�group divisible designs� dans un code auto�dual q�aire� Les polyn�mes deJacobi sont aux codes ce que les formes modulaires sont aux r�seaux arith�m�tiques� Ici cependant nous cherchons � limiter le nombre d�invariants etnous consid�rons donc de gros groupes de substitutions� Paralllement je mesuis int�ress� � d�autres anneaux� Avec Udaya nous avons �tudi� les codescycliques d��nis sur R � F� � uF�� Dans le chapitre suivant j�explique l�in�t�r�t de cet anneau� Ce travail peut se g�n�raliser dans di��rentes directions�L�utilisation de nouveaux anneaux comme par exemple Z��uZ� est une voie
�
�� CHAPITRE �� INTRODUCTION
int�ressante et amne naturellement � l��tude des codes quasi�cycliques deLing San et Patrick Sol�� Le d�codage des ces codes est un important pro�blme que nous commen�ons � aborder�Le chapitre � pr�sente le travail de Hammons Kumar Calderbank Sloane etSol� qui est le point de d�part de mes recherches sur les codes quaternaires�Il apporte aussi les d��nitions et notations n�cessaires � la compr�hension dela suite�Le chapitre relatif aux thmes de recherches se compose de quatre parties�Je pr�sente en section � mes principaux r�sultats sur les codes quaternairesqui ont fait l�objet de quatre publications dans des journaux internationauxet qui sont pr�sent�s dans ma thse de doctorat� En section � je m�int��resse aux propri�t�s combinatoires des codes� Je d�cris les di��rents outilset m�thodes que nous utilisons pour �tudier ces codes� Ce travail e�ectu�en collaboration avec P� Sol� se compose de trois articles publi�s dans desjournaux internationaux� La troisime section pr�sente notre �tude avec P�Udaya des codes cycliques sur l�anneau F� � uF�� Il fait l�objet de deux ar�ticles dans IEEE�Information Theory� En�n je d�cris une jolie applicationde la th�orie des codes � la th�orie des graphes�
Actuellement la recherche en codage demande des comp�tences pratiques etth�oriques� Il est important de ne pas s�arr�ter � la th�orie puisque notrevocation est de construire et d�coder des codes objets bien r�els� Certainscalculs peuvent s�av�rer trs di ciles � implanter du fait de problmes decomplexit�� L�int�r�t des calculs est aussi d�un autre ordre � en permettantde mieux comprendre les problmes ils peuvent aider � la naissance d�id�esou de th�ories nouvelles� Le travail en �quipe me semble �tre la meilleuresolution pour une recherche e cace et enrichissante� Ma m�thode de travailsuit ces principes� J�ai en g�n�ral �crit mes articles avec un coauteur princi�pal �mes coauteurs principaux �tant jusqu�a pr�sent I� Duursma P� Udayaet P� Sol�� mais quelquefois nous avons eu besoin des comp�tences d�autreschercheurs pour r�soudre certains points particuliers�
Chapitre �
Les codes quaternaires
R�gulirement un �hot topic� �merge en th�orie des codes� Au d�but desann�es �� ce fut celui des codes sur Z� l�anneau des entiers modulo �� Lesnon�initi�s ont pu se demander si l�engouement provoqu� par cet anneau dequatre �l�ments �tait justi��� Ce chapitre ambitionne de r�pondre � leur at�tente� Il explique le cheminement qui amena certains chercheurs � consid�rercet anneau et �nalement r�soudre une conjecture vieille de plus de vingt ans�De par leurs propri�t�s souvent remarquables les codes sur Z� devinrentrapidement une nouvelle voie de recherche� Ils amenrent de nouvelles struc�tures combinatoires de nouvelles constructions de r�seaux arithm�tiques etdes algorithmes de d�codage utilisant par exemple les bases de Gr!bner� Lescodes sur Z� sont donc bien plus qu�une mode passagre�
��� Les codes binaires
Soit F un corps �ni� Un code C de longueur n est un sous�ensemble deF n� La m�trique la plus utilis�e est la m�trique de Hamming� Le poids deHamming d�un mot a � F n est le nombre de coordonn�es non nulles dans a�La distance de Hamming d�x� y� de deux �l�ments x� y � F n est d��nie par
d�x� y� � ��i j xi �� yi� i � � ��� n��
La distance minimale d du code C repr�sente la distance la plus petite entredeux mots distincts du code� Un code de longueur n de distance minimale det admettant M mots est not� un �n�M� d��code� Un des grands problmesde la th�orie des codes est de trouver de bons codes� Consid�rons les troisparamtres d�crits pr�c�demment� La longueur n du code sa cardinalit� Met sa distance minimale d� Lorsque deux des trois paramtres sont �x�sil existe une borne sur la valeur du troisime� Un bon code pourrait �tred��ni comme le code qui admet le plus grand nombre d��l�ments lorsque salongueur et sa distance minimale sont �x�es� En r�alit� les codeurs pr�frenttravailler avec des codes faciles � utiliser � les codes lin�aires� D��ni sur uncorps F un code lin�aire est un sous�espace vectoriel de dimension k sur F n
��
�� CHAPITRE �� LES CODES QUATERNAIRES
de paramtres �n� k� d� Un code lin�aire peut �tre d�crit par sa matrice decontr�le ou par sa matrice g�n�ratrice� Ce choix d�pend principalement dubut � atteindre� Prenons l�exemple du code de Hamming H� de longueur �de paramtres ��� �� �� Nous le d��nissons de la manire suivante �
H� � fc � F �� j H�cT � g� �����o" cT est la transpos�e de c et les colonnes de H� consistent en tous lesvecteurs non nuls de longueur � �
H� �
��
�A �
Cette matrice est appel�e matrice de contr�le de H�� Avec cette descriptionil est trs facile de d�coder le code� En e�et supposons que le mot re�u soity � � �� En utilisant ����� nous obtenons
H�yT �
��
�A �
qui se trouve �tre la sixime colonne de H�� Le sixime bit de y est doncerron� et y doit �tre corrig� en le mot c � � ��Pour de nombreuses applications il est souvent su sant de travailler �
�quivalence de codes prs� Deux codes sont dits �quivalents s�ils se d�duisentl�un de l�autre par une permutation de coordonn�es� La matrice suivanterepr�sente la matrice de contr�le d�un code equivalent � H� �
H� �
��
�A �
Elle peut se r��crire
H� �� � �� �� �� �� ��
��
o" � est une racine du polyn�me binaire f�x� � x� � x� de degr� m � ��Ainsi �� � � � �� � � � �� et d�une manire g�n�rale les �i s��criventdans la base � �� ��� Remarquons que � est une racine septime de l�unit�et donc que �� � � En identi�ant un mot du code �c�� c�� � � � � c�� avec lepolyn�me binaire c�x� �
P�i�� cix
i� nous obtenons une nouvelle descriptionde H� �
H� � fc�x� j c��� ��Xi��
ci�i � g�
Le d�codage se fait alors de la manire suivante � supposons que le messagere�u soit r�x� �
P�i�� rix
i� Si r��� � nous pouvons supposer que le message
���� RELATION ENTRE UN CODE ET SON DUAL ��
est correct� Dans le cas contraire il existe un i� � i � � tel que r��� � �iet nous en concluons que le mot de code correct est c�x� � r�x� � xi� Cettedernire description du code H� en amne une autre � H� est un id�al deF��x��x
��� engendr� par le polyn�me f�x� � x��x�� Les mots du codesont donc tous les multiples binaires de f�x� modulo �x� � �� Le polyn�mef�x� est appel� polyn�me g�n�rateur du code et on note
H� �� f�x� � �En rgle g�n�rale un id�al de F��x��x
n � � est appel� un code cycliquebinaire� Les codes de Hamming sont donc �quivalents � des codes cycliques�Les codes cycliques de longueur n peuvent �tre �tendus en codes de lon�
gueur n � en rajoutant � chaque mot un symbole de parit� cn �Pn��
i�� ci�La matrice de contr�le du code H� �tendu est alors
HE� �
� � �� �� �� �� ��
��
L�ajout du bit de parit� permet � la distance minimale du code de passer de� � �� Ce code �tendu est donc un ��� �� � code�Une autre fa�on de d�crire H� est d�exhiber une matrice �dite g�n�ratrice�
dont les lignes forment une base du code �H� est un sous�espace vectorielde F �� �� Cette description peut �tre utilis�e par exemple pour d�terminerl��num�rateur de poids WH��y�� y�� du code d��ni par �
WH��y�� y�� �Xc�H�
yn�� yn�� �
o" les ni repr�sentent le nombre de coordonn�es �gales � i dans le code� Ce po�lyn�me est homogne de degr� la longueur du code� Il donne des informationspr�cieuses sur la r�partition des poids et certaines propri�t�s combinatoiresdu code�
��� Relation entre un code et son dual
Nous introduisons maintenant la notion de dualit� qui est fondamentaledans notre �tude�
D��nition ��� Le code dual C� d�un code lin�aire C est d��ni par
C� � fu j hu� vi � � pour tout v � Cg�o� � u� v � repr�sente le produit scalaire usuel dans F��
L��num�rateur de poids d�un code binaire C et de son dual sont li�s parl�identit� de MacWilliams
WC��y�� y�� �
jCjWC�y� � y�� y� � y���
Deux codes dont les �num�rateurs de poids v�ri�ent cette identit� sont ditsformellement duaux �ils peuvent ne pas �tre lin�aires��
�� CHAPITRE �� LES CODES QUATERNAIRES
��� Les codes de Kerdock et Preparata
Les outils de l�algbre lin�aire facilitent l��tude l�encodage et le d�co�dage des codes lin�aires� Cependant ces codes n�admettent pas forc�mentun nombre optimal d��l�ments� Fixons par exemple une longueur n � � etune distance minimale d � �� Le code binaire lin�aire de cardinalit� optimaleadmet les paramtres ��� �� �� Il contient donc �� � �� mots� Pourtant ilexiste un code non lin�aire de ��� mots appel� code de Nordstrom�Robinson#NR��$� Ce code fut construit pour la premire fois en ���� � la suite d�unecollaboration fructueuse entre Nordstrom et un �tudiant de High�School Ro�binson� Sa cardinalit� est optimale compte tenu de la valeur des deux autresparamtres� Ce code de Nordstrom�Robinson fut g�n�ralis� plus tard dansdeux directions� La famille des codes de Preparata en ���� de paramtres��m� ��
m��m� �� m pair et la famille des codes de Kerdock en ���� de para�mtres ��m� ��
m
� �m����m����� m pair� Ces deux classes de codes admettentdes structures et propri�t�s particulirement int�ressantes� Nous en citonstrois �% Les mots d�un poids donn� dans chacun des codes forment les blocs d�un��design� Cela signi�e que lorsque l�on considre l�ensemble des motsd�un poids donn� w il existe une constante �w telle que pour tout ��uplet de coordonn�es il existe exactement �w mots qui admettent desvaleurs non nulles sur ces trois coordonn�es�
% Ces codes sont tous de distance invariante �par translation�� De plusleur nombre de mots est maximal au regard des deux autres paramtresn et d�
% Les codes de Kerdock et Preparata sont formellement duaux l�un del�autre et le code de Nordstrom�Robinson est dit formellement auto�dual car son �num�rateur de poids est laiss� invariant par l�identit� deMacWilliams�
Cette dernire propri�t� fut la plus fascinante au yeux des codeurs� Il �taiten e�et surprenant que les codes de Kerdock et de Preparata d�une lon�gueur donn�e soient formellement duaux l�un de l�autre sans que ces codesne soient ni duaux ni m�me lin�aires� Se pouvait�il que les codes de Pre�parata et de Kerdock fussent duaux dans un espace � d��nir � Les ann�esrecouvrant la p�riode ��������� furent riches en �tudes conjectures et autrescontre�conjectures� Il fut essay� de trouver une d��nition de produit scalairecompatible avec les codes non�lin�aires� Certains tentrent de d�terminerune nouvelle description des codes mettant en �vidence leur dualit� formelle�D�autres �tudirent leurs groupes d�automorphismes comme Kantor ou Car�let �#Kan��$#Kan��$#Car��$� sans plus de succs car il existe plusieurs codesnon equivalents ayant les paramtres du code de Preparata� La r�ponse futdonn�e en ���� dans #HKC��$ � lorsqu�ils sont d��nis sur Z� l�anneau desentiers modulo � les codes de Kerdock et de Preparata sont lin�aires et duauxl�un de l�autre�
���� LES CODES SUR Z� ��
��� Les codes sur Z�
La premire personne � s�int�resser aux codes d��nis sur des anneaux�nis fut peut��tre P� Udaya� Ces travaux ne d�passrent malheureusementpas les frontires de l�Inde� En ���� P� Sol� �I�S France� et ind�pendem�ment P�V� Kumar et ses �tudiants S� Boztas �USC� et R� Hammons �HughesAircraft Company� proposent des constructions de s�quences quadriphasesp�riodiques � faible autocorr�lation� Ces s�quences se construisent � par�tir d�un alphabet constitu� des racines quatrimes de l�unit�� Cependant ilest equivalent et plus simple d�utiliser l�anneau des entiers modulo quatreZ� � f� � �� �g� Les s�quences ainsi construites sont appel�es s�quencesquaternaires� Vijay Kumar et Hammons s�aper�oivent qu�ils peuvent fairecorrespondre � toute s�quence quaternaire de p�riode n une s�quence binairede p�riode �n� La m�trique naturelle sur Z� est la m�trique de Lee� Le poidsde Lee de x � Z� est par d��nition WLee�x� � minfx� ��xg� La fonction deGray � donn�e par
Z� � F��
�
� � � � �
peut s��tendre � des vecteurs de longueur n� Elle d��nit alors une isom�triede Zn� muni de la distance de Lee sur F
�n� muni de la distance de Hamming�
Soit c � �c�� � � � � cn��� � Zn� l�image de c par � est ���c� � ���c��� � � � � ��cn�����
Cette isom�trie permet de construire des codes binaires de longueur �n �partir de codes sur Z� de longueur n� Il est facile de v�ri�er que � ne conservepas la propri�t� de lin�arit� mais seulement celle de distance invariante� Ainsil�image par la fonction de Gray d�un code lin�aire sur Z� n�est en g�n�ral paslin�aire� De plus l�image inverse d�un code lin�aire binaire n�est pas forc�mentlin�aire sur Z�� Un code lin�aire sur Z� est un Z��module appel� aussi codequaternaire� Le produit scalaire sur ZN� est d��ni par �a� b� � a�b��� � ��aNbN�mod ��� Il nous permet de d��nir la notion de dualit� entre deux codesquaternaires �
C�� � fu j �u � v� � �mod �� �v � C�g�Puisque l�image binaire d�un code quaternaire ��C�� � C n�est pas toujourslin�aire elle n�admet pas de dual au sens alg�brique du terme� On d��nitalors le Z��dual de C par C� � ��C
�� �� Ainsi nous avons le diagramme
suivantC�
��� C � ��C��dual �
C����� C� � ��C�� ��
�� CHAPITRE �� LES CODES QUATERNAIRES
Il n�est pas possible de rajouter une �che not�e �dual� dans la partie droitedu diagramme� Cependant le th�orme suivant donne une propri�t� remar�quable de la Z��dualit� �
Th�or�me ��� Soit C� un code quaternaire et C�� son dual� Les distribu�
tions de poids de leurs images binaires C � ��C�� et C� � ��C�� � satisfont
la transformation de MacWilliams�
Ainsi les images par la fonction de Gray de deux codes duaux sur Z� sontdes codes formellement duaux�
��� Description par les anneaux de Galois
La th�orie des corps de Galois nous a permis de donner une descriptiond�un code binaire cyclique� Les codes cycliques quaternaires n�cessitent euxl�utilisation d�anneaux de Galois� Dans cette section nous montrons commentconstruire un code cyclique sur Z� � partir d�un code cyclique binaire�
����� Le rel�vement de Hensel
Consid�rons un polyn�me h��X� � Z��X de degr� m qui soit un facteurprimitif de xa � � a impair� Rappelons qu�un facteur primitif de xa � nedivise aucun xa
� � � avec a� � a� Alors le lemme de Hensel prouve qu�ilexiste un unique polyn�me unitaire h�X� � Z��X de degr� m tel que% h��X� � h�X� modulo ��% h�X� divise Xa � �mod ���
le polyn�me h�X� est appel� un b�polyn�me� La m�thode de Grae�e #Sol��$et #Usp��$ permet de d�terminer h�X� dont les racines sont les carr�s desracines de h��X�� Ecrivons h��X� � e�X�� d�X� o" e�X� est un polyn�mene contenant que des puissances paires et d�X� que des puissances impaires�Alors
h�X�� � �e��X�� d��X���Exemple Reprenons notre code de Hamming avec m � � et a � �� Lafactorisation de X� � modulo � donne
X� � � �X � ��X� �X� � ��X� �X � ��Le polyn�me h��X� � X
� �X � est le polyn�me g�n�rateur de H�� Nousavons e�X� � et d�X� � X� �X� Donc
e��X�� d��X� � �X� � �X� �X� � et
h�X� � X� � �X� �X � �Nous obtenons le polyn�me g�n�rateur du code de Hamming de longueur �sur Z�� Ce proc�d� est appel� �relvement de Hensel� car c�est Hensel qui
���� DESCRIPTION PAR LES ANNEAUX DE GALOIS ��
�labora un algorithme permettant non seulement de construire le polyn�merelev� mais aussi de prouver son unicit� �voir #Mig$�� Dans #CS��$ Calder�bank et Sloane proposent une autre preuve de l�existence et de l�unicit� dupolyn�me�Cette m�thode permet de relever des codes binaires pour obtenir un coded��ni sur Z��R�p�ter l�op�ration du relvement donne un unique polyn�me sur Z� Il estdonc possible de construire un polyn�me sur Z�a en utilisant �a � � rel�vements de Hensel� Cette m�thode permet de construire des codes sur Z�a�Calderbank l�appelle la �bottom up approach� qu�il oppose � la constructiondescendante ou �top down approach�� Cette dernire consistant � d�marreravec un code d��ni sur les entiers ��adiques puis � r�duire le polyn�me mo�dulo �a�
����� L�anneau de Galois R � GR���m�
D��nition ��� Soit f un b�polyn�me de degr� m sur Z�� L�anneau de GaloisR � GR��� m� est d��ni � un isomorphisme pr�s comme �tant Z��X��f��
Soit f�X� un facteur primitif de X�m�� � et � une racine primitive de
f�X�� L�anneau de Galois R � GR��� m� peut �tre d��ni comme l�extensionR � Z���� Contrairement au corps F� il n�est pas intgre et possde doncdes diviseurs de z�ro� L�ensemble des diviseurs de z�ro forme un sous�groupe�R d�ordre �m� Le groupe des inversibles R� � R n �R est constitu� des�l�ments qui ne sont pas diviseurs de z�ro� Les �l�ments de R admettentune repr�sentation unique &multiplicative� ou &additive�� Dans la premirerepr�sentation que l�on appelle aussi ��adique un �l�ment c � R s��critc � a � �b� o" a et b appartiennent � T � f� � � ��� � � � � ��m��g� Dans laseconde repr�sentation un �l�ment c � R s��crit
c �m��Xr��
br�r br � Z��
Il est facile de voir que cette �criture est unique� Elle donne �m �l�mentsdi��rents� Intuitivement elle permet de mieux comprendre la notation Z��� �il s�agit de tous les polyn�mes en � � coe cients dans Z� modulo le polyn�meminimal de ��Exemple Reprenons l�exemple pr�c�dent avec h�X� � X� � �X� �X � et � une racine de h� Alors
�� � ��� � �� � �� � ��� � �� � ��� � �� � �� � ��� � �� � �� � �� �
�� CHAPITRE �� LES CODES QUATERNAIRES
Ainsi un �l�ment s��crivant dans la repr�sentation multiplicative c � �����
s��crit dans la repr�sentation additive � � �� � ��� �
c � � � ���
� � ��� � �� � ���� � �� � ���
��� La bonne d��nition des codes de Kerdock
et Preparata
Ds ���� Nechaev montra que les codes de Kerdock pouvaient �tre d��niscomme des codes cycliques sur Z�� Cependant il ne pensa pas � �tudier le lienavec les codes de Preparata� Trois ans plus tard ce sont Hammons KumarKalderbank Sloane et Sol� qui prouvrent que les codes de Preparata etKerdock sont les images par fonction de Gray de codes quaternaires duauxl�un de l�autre �
Th�or�me ��� Soit f�x� un b�polyn�me de degr� m sur Z� et � une racineprimitive de f�x�� Le code quaternaire de matrice de contr�le
H �
� � � � � �� �� � � � ��
m��
�
admet une image binaire par fonction de Gray dont les param�tres sont lesm�mes que ceux du code de Preparata de m�me longueur�
L�image binaire du code engendr� par H admet les m�mes param�tres queceux du code de Kerdock de m�me longueur�
Il faut pr�ciser ici que Nechaev avait utilis� une fonction di��rente de celle deGray� Il lui �tait impossible avec cette fonction d�observer la dualit� formelledes codes de Kerdock et Preparata�Notons la similarit� entre la matrice H et la matrice de contr�le du code deHamming binaire �tendu�
Chapitre �
Les di��rents th�mes de recherche
��� Les codes d��nis sur Z�
Articles correspondants � ce thme �
�� Quaternary Quadratic Residue Codes and Unimodular Lat�tices A� Bonnecaze P� Sol� et A�R� Calderbank IEEE Transactionson Information Theory� �� ����� pp ��������
�� Type II Codes over Z� A� Bonnecaze P� Sol� C� Bachoc et B�Mourrain IEEE Transactions on Information Theory� VOL
� May����� pp ��������
�� Translates of Linear Codes over Z� A� Bonnecaze et I�M� DuursmaIEEE Transactions on Information Theory� VOL �� No� July �����pp ����������
�� Niemeier Lattices and Type II Codes over Z� A� Bonnecaze P�Gaborit M� Harada M� Kitazume P� Sol� Discrete Math� ��� ����
����
Ces articles � l�exception du dernier ont �t� �crits avant ���� et sont d�critsplus en detail dans ma thse de doctorat #Bon��$� Dans un premier tempsnotre but avec P� Sol� a �t� d��tudier les codes de r�sidus quadratiques surZ�� Puis nous nous sommes int�ress�s aux codes auto�duaux et iso�duaux surcet anneau� J�ai ensuite introduit la notion de code de type II quaternaire quinous a permis d�obtenir de nouvelles constructions de r�seaux arithm�tiques�
����� Codes de type II binaires
Rappelons qu�un code binaire de paramtres �n� k� d est dit auto�dual siil est �gal � son dual� Sa dimension est donc k � n��� Les codes auto�duauxsont int�ressants pour de multiples raisons� En voici trois �
� beaucoup de bons codes le sont� C�est le cas du code de Hamming��� �� � ou du code de Golay ���� �� ��
��
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
� Ils sont � la base de constructions de r�seaux arithm�tiques�
� Leur �num�rateur de poids est invariant par l�action d�un groupe �ni�que nous allons d�crire��
Un code binaire auto�dual est doublement pair �ou de type II� si le poids dechacun de ses mots est divisible par �� Le th�orme de Gleason ������ permetde conna�tre la forme g�n�rale de l��num�rateur de poids d�un code de typeII �
Th�or�me ��� L��num�rateur de poids d�un code de type II est un polyn�meen W��x� y� et W
���x� y�� o� W��x� y� est l��num�rateur de poids du code de
Hamming ��� �� �� et W��x� y� � x�y��x� � y����
L��num�rateur de poids est un polyn�me homogne de degr� n� Dans le casd�un code de type II il est invariant par l�action du groupe
GII � h p�
� �
��
�
i
�i
d�ordre ���� La premire matrice traduit l�identit� de MacWilliams et laseconde la propri�t� de double parit� sur les poids� Ce th�orme permet lecalcul de l��num�rateur de poids d�un code de type II sans avoir � �num�rerles mots du code� Il utilise une th�orie vieille de plus de cent ans � la th�oriedes invariants� La section suivante la d�crit brivement�
����� Th�orie des invariants
La th�orie des invariants concerne l��tude d�un groupe G agissant surun anneau R� Ici le groupe G est un groupe �ni inclus dans GL�m�C� etl�anneau R � C�x�� x�� � � � � xm� L�anneau des invariants est
RG � ff � R j f � f g� g � Gg�C�est l�anneau des polyn�mes homognes en m variables invariants par l�ac�tion de G� Chaque invariant possde une �criture unique� Celle�ci est donn�epar la d�composition de Hironaka �
RG �lM
i��
iC��� � � � � m�
o" � � et � � � � � l s�appellent les invariants secondaires et �� � � � � m lesinvariants primaires� La s�rie de Molien ������ compte le nombre d�invariantsNi lin�airement ind�pendants de degr� i �
S��� �
jGjXA�G
det�I � �A� � �����
o" jGj d�signe le nombre de matrices dans le groupe G et det le d�terminant�Cette s�rie peut s��crire sous la forme
N� �N���N��� � � � ��Ni�
i � � � � �
���� LES CODES D�FINIS SUR Z� ��
Notons que lors du calcul de cette s�rie il est inutile de consid�rer tous les�l�ments du groupeG� En e�et lorsque deux �l�ment A� et A� sont conjugu�son a det�I � �A�� � det�I � �A��� Cette remarque permet au systme decalcul symbolique MAGMA de gagner du temps en sommant sur chaquerepr�sentant de classes et en multipliant par le nombre d��l�ments de la classe�
����� Codes auto�duaux et th�orie des invariants sur Z�
Par analogie au cas binaire j�ai introduit la notion de code de type II surZ�� Ce sont des codes auto�duaux dont les poids euclidiens sont multiples de�� A l�origine j�avais ajout� la condition que le mot tout � un appartienne auxcodes pour limiter le nombre d�invariants lorsque l�on considre un �num��rateur de poids complet� J�ai caract�ris� les �num�rateurs de poids completset sym�triques de ces codes en utilisant la th�orie des invariants�
Les transformations de MacWilliams d�terminent un groupe de substitutionsqui laissent invariant l��num�rateur de poids d�un code de type II sur Z�� Cet�num�rateur de poids est appel� un invariant car il est invariant par l�actiondu groupe de substitution �ici d�ordre �����
Th�or�me ��� L��num�rateur de poids sym�trique d�un code de type II delongueur N sur Z� contenant un vecteur � appartient � l�anneau
S � ��So� S est l�anneau dont une base est donn�e par les polyn�mes suivants �
� � le swe de l�Octacode�
� le swe de Q���� � le swe du Golay quaternaire�
et o��� � le swe de RM�� �� � � RM��� ��
et la s�rie de Molien est
S��� � ����
��������������
� � �� � ���� � ���� � ���
����� � ��� � ����� � ���� � � �
Les matrices qui engendrent le groupe sont
M� �
�
�� � �
��
M� �
��
w
�
M� �
��
o" w est une racine huitime de l�unit��L�anneau des invariants peut s��crire en fonction d�invariants quelconques
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
mais j�ai pr�f�r� utiliser des �num�rateurs de poids de codes de type II bienconnus � l�Octacode de paramtre ��� �� � le code Q de paramtre ��� �� � etle code de Golay relev� ���� �� �� Notons que dans le cas binaire l�anneaus��crit en fonction de l��num�rateur de poids du code de Haming ��� �� � etde celui du code de Golay ���� �� ��Cette caract�risation de l�anneau m�a permis de calculer les �num�rateurs depoids des codes de r�sidus quadratiques en longueur �� et ���
���� R�seaux arithm�tiques
Les codes de type II sur Z� sont tout comme leur analogues binaires �la base de constructions de r�seaux arithm�tiques� Dans un premier tempsrappelons les de�nitions et propri�t�s essentielles des r�seaux arithm�tiques�L�id�e sous�jacente est que l�on veut empiler des sphres de telle manireque l�espace vide restant soit le plus petit possible� Ainsi en dimension �l�empilement des oranges sur les �tals des march�s parait optimal� La densit�de l�empilement de sphres est le rapport entre l�espace occup� par les sphreset l�espace total� Pour une dimension quelconque le problme de trouver unempilement de sphres dense est trs di cile� Un autre problme di cile estle �kissing number problem� � quel est le nombre maximum �N de sphres quipeuvent toucher une sphre donn�e de RN �toutes les sphres sont de m�metaille�� En dimension deux on constate que �� � � #Slo��$�Ici un empilement de sphres correspond � l�ensemble des di��rents centresdes sphres�Un r�seau arithm�tique est un empilement de sphres dont les centres formentun groupe additif�
D��nition ��� Un r�seau � de RN de dimension N est l�ensemble descombinaisons lin�aires enti�res de N vecteurs v�� � � � � vN lin�airement ind��pendants�
En dimension � c�est le r�seau hexagonal A� qui a la meilleure densit�� � ��
p� � ���� � � �� Pour des valeurs de dimension sup�rieures � �
la meilleure densit� n�est toujours pas connue� En dimensions � et �� lesr�seaux les plus denses connus sont E et ��� le r�seau de Gosset et le r�seaude Leech de kissing number respectifs ��� et ��� ���� Ces deux r�seaux sontprobablement les plus fascinants #CS��$ de par leurs propri�t�s et leurs liensavec la th�orie des groupes� Il existe plus d�une vingtaine de constructionsdu r�seau de Leech �cf� #CS�� Chapitre ��$�� Une d��nition standard de ���consiste � d�crire le r�seau comme une union d�un sous r�seau h��� avec untranslat� h��� � �� ��� �������� La partie h��� se construit � partir ducode de Golay binaire G�� par construction B et correspond � la moiti� despoints de ���� Cette construction correspond � doubler la densit� de h����L�utilisation d�une simple construction A � partir du code de Golay relev�sur Z� permet d��viter cette �tape� On obtient ainsi directement le r�seau deLeech�
���� LES CODES D�FINIS SUR Z� ��
Avant de d��nir la notion de r�seaux unimodulaires introduisons les notionsde s�rie theta et de dualit�� La s�rie theta ��q� d�un r�seau � est la s�rieformelle
��q� �Xx�
qx�x�
Le kissing number est le premier coe cient non trivial de la s�rie theta� Ledual d�un r�seau � de dimension N est not� �� et est donn� par
�� � fx � RN j �x� a� � Z� pour tout a � �g�Un r�seau est entier si le produit scalaire de � points quelconques du r�seauest entier ou d�une manire �quivalente si � � ��� Si � est un r�seau entieron a
� � �� � �� det�D��nition ��� Un r�seau unimodulaire � est un r�seau entier de d�termi�nant �
Remarque� Un r�seau � entier est unimodulaire si et seulement si � � ���Exemple Le r�seau de Gosset E est un r�seau unimodulaire� Il consisteen les points �x�� � � � � x� � coordonn�es entires ou demi�entires v�ri�antP
i�� xi � mod����D��nition ��� Un r�seau � est pair si pour tout x � �� le produit scalaire�x� x� est un entier pair�
Th�or�me ��� Bonnecaze et Sol�� ���� Soit C un code auto�dual de lon�gueur n sur Z� de poids euclidien minimum dE� Alors le r�seau
A��C� �
�fx � Zn j x � c �mod �� pour un c � Cg �
est un r�seau unimodulaire de dimension n� La norme minimale de A��C�est minf�� dE��g et la s�rie theta est
�A��C��q�� � sweC���Z�q����Z��q����Z��q���
Si C est de Type II� le r�seau A��C� est alors pair et unimodulaire�
Gr'ce � ce th�orme nous pouvons construire le r�seau de Leech qui est leseul r�seau unimodulaire pair de dimension �� de norme ��
Th�or�me ��� Bonnecaze Sol�� ���� Soit bQ����� le code de Golay qua�ternaire� Alors A�� bQ�������� est le r�seau de Leech ����Conway et Sloane �crivent dans #CS��$ que cette construction est probable�ment la plus simple connue � ce jour� Plus tard d�autres constructions dur�seau de Leech virent le jour utilisant des codes de type II sur Z� ayant lam�me distance minimale euclidienne que le code de Golay relev��
Tous les r�seaux que nous consid�rons sont unimodulaires car ils sont obte�nus � partir de codes auto�duaux� Le dictionnaire qui permet de passer dumonde des codes sur Z� � celui des r�seaux arithm�tiques est le suivant �
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
codes quaternaires r�seaux arithm�tiquesauto�dual unimodulairetype II pairtype I impair
La classe des r�seaux unimodulaires pairs inclut le r�seau de Gosset E ainsique le r�seau de Leech ���� Ce dernier admet une norme minimum �gale ��� Il existe d�aprs la classi�cation de Niemeier �� autres r�seaux unimo�dulaires pairs de dimension �� �mais ceux�ci ont pour norme ��� En ����nous avons prouv� que tous les r�seaux de Niemeier peuvent �tre obtenuspar construction A� � partir de codes de type II sur Z�� C�est aussi le cas detous les r�seaux unimodulaires extr�maux� Rappelons qu�un r�seau extr�malen dimension N doit satisfaire l��galit� norme��� � �N�� � �
En dimension �� j�ai obtenu deux r�seaux dont celui de Barnes�Wall etun nouveau r�seau BSBM��� Ce sont les deux seuls r�seaux unimodulairespairs de norme � contenant un automorphisme d�ordre �� #Que��$�
����� Translat�s des codes sur Z�
L��tude de la distribution de poids d�un code fournit une description deses propri�t�s combinatoires et aide � l�analyse de ses algorithmes de d�co�dage� La distribution de poids des translat�s du code est une donn�e encoreplus signi�cative� Mais peu de r�sultats ont �t� obtenus dans ce domaine�J�ai rencontr� I� Duursma en ���� lors d�un s�minaire du GECT et je luiai fait part de mon problme concernant les translat�s des codes quater�naires� Il proposa d�adapter � Z� les principes issus de la th�orie des sch�masd�association #BCN��$� Ainsi nous avons d�velopp� une m�thode permettantde d�terminer les �num�rateurs de poids complets des translat�s d�un codeC quaternaire libre� L�id�e sous�jacente est fortement inspir�e des travauxd�velopp�s par Delsarte #Del��$� Un sch�ma d�association g�n�ral est d��nicomme un graphe complet color� qui satisfait certains axiomes de r�gularit��Les ar�tes d�une couleur donn�e d�termine un sous�graphe� Les axiomes der�gularit� garantissent que les relations entre sous�graphes de couleurs dif�f�rentes peuvent �tre �tudi�es � partir des valeurs propres de leurs matricesd�adjacence� Les valeurs propres sont contenues dans deux matrices propresP et Q� La connaissance de ces matrices permet de d�terminer beaucoup depropri�t�s du sch�ma d�association� L�utilisation des sch�mas d�associationspour le calcul des distributions de distances de codes a �t� aussi �tudi�e dans#CCD��$ #CCK��$ ou #Sim��$� Mais dans tous les cas les r�sultats �taientformul�s pour la m�trique de Hamming� Nous avons adapt� ces techniquespour pouvoir consid�rer des codes quaternaires� Sur Z� nous avons consid�r�les poids complets car la m�trique de Hamming n�est plus assez pr�cise� Danscette section je pr�sente les grandes lignes de la m�thode que nous avons d��velopp�e�
Je d��nis le code C quaternaire libre par sa matrice de contr�le H� L�en�
���� LES CODES D�FINIS SUR Z� ��
semble des colonnes deH not� � engendre un groupe G� On a par d��nitionC � C��� � fc � cHT � g� Notons CG l�algbre de groupe complexe�Le groupe additif Z� est isomorphe au groupe multiplicatif hii des racinescomplexes de l�unit�� On peut ainsi introduire le caractre canonique
exp � Z� �� hii � C�� exp�� � i�
Le groupe des caractres �G de G est le groupe d�homomorphismes
� � G �� hii�
On peut supposer que � est de la forme � � exp �hh� �i�� Nous pouvonsd�crire le poids complet d�un mot en termes de sommes de caractres �
S��� �Xg��
exp�hh� gi� � C� �����
o" l�on note hh� gi le produit scalaire usuel�Pour c � �hh� gi�g�� de poids complet �n�� n�� n�� n�� nous avons
S��� � �n� � n�� � i�n� � n��S���� � �n� � n��� �n� � n���
Si la taille de � est N nous avons donc����n��c�n��c�n��c�n��c�
�� � �
����
�
� � ��
� ��
��
����
NS����ReS���ImS���
�� � �����
Notons que la somme de caractres S��� joue un r�le dans la th�orie dess�quences quaternaires o" elle est utilis�e pour d�crire la corr�lation entres�quences #Sol��$ #Boz��$ #BHK��$�
Pour obtenir les polyn�mes �num�rateurs des translat�s de C il convientd�exhiber une partition r�gulire de l�espace des syndromes �Z��
m dont l�undes �l�ments soit constitu� des colonnes de la matrice de parit� du code�
D��nition ��� Une partition �G��� est un groupe ab�lien �ni G muni d�unepartition � � f�� � � ��� � � � � �rg d��l�ments de G� pour r � Lesfonctions caract�ristiques
i �Xg��i
Ug � CG� i � � � � � � � r� �����
engendrent un espace vectoriel complexe V de dimension r�� Une partition�G��� est r�guli�re si
a � est invariant lorsque l�on prend l�inverse dans G�b V est clos par multiplication dans CG�
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
Lorsque la partition est r�guli�re� V satisfait les axiomes d�une alg�bre� Onl�appelle un anneau de Schur de dimension r � sur G� Il sera not� S�
Le r�sultat central de l�article est l�equivalence des deux problmes suivants ��a� Trouver l��num�rateur de poids complet de C��i�
�� pour i � � � � � � � r��b� Trouver les �num�rateurs de poids complet des translat�s de C�����
La preuve repose sur le fait que d�aprs le th�orme de Maschke CG estsemi�simple� Cela implique que l�anneau S l�est aussi et l��l�ment unit� peutse d�composer en une somme d�idempotents orthogonaux� Ainsi on a �e� � e� � � � �� en avec eiei � ei� eiej � � pour i �� j� et
CG � Ce� �Ce� � � � �Cen�
Les idempotents ei� i � � �� � � � � n sont appel�s primitifs� Les idempotentsprimitifs de CG peuvent �tre d�crits en termes de caractres� Le groupedes caractres �ou groupe dual� �G est isomorphe � G� La d�composition del��l�ment unit� dans S d��nit une partition � �G� E � fE� � � E�� � � � � Erg�sur le groupe dual tel que
ej �X��Ej
e�� j � � � � � � � r� �����
L�anneau de Schur admet donc deux bases partitions r�gulires sur respec�tivement G et �G� Le th�orme suivant permet de passer d�une base � l�autre�
Th�or�me ��� Soit fi � i � � � � � � � rg et fej � j � � � � � � � rg deux basespour l�anneau de Schur S � CG� Soit �Q le conjugu� de la matrice Q� Alors�
�� � �e�P � Pj�i �Xg��i
��g�� � � Ej �
�e� �
jGj���Q � Qi�j �
X��Ej
��g�� g � �i �
En particulier� P �Q � jGj I�
Nous d��nissons dans un premier temps l��num�rateur formel de poids com�plet puis nous montrons comment passer de l��num�rateur formel � l��num��rateur explicite� L�id�e est d�appliquer une transformation de MacWilliamsg�n�ralis�e faisant intervenir les matrices P et Q�
D��nition ��� Soit � � G un sous ensemble de taille N � pour G � �Z��m�m � � l��num�rateur formel de poids complet F ��� � CG de C��� est ainsid��ni �
F ��� �Yg��
�U�W � UgX � U�gY � U�gZ� � CG�W�X� Y� Z� �����
���� LES CODES D�FINIS SUR Z� ��
L��num�rateur formel de poids complet F ��� est un polyn�me homogne dedegr� N en W�X� Y� Z et � coe cients dans CG� Nous donnons dans lesdeux lemmes suivants deux interpr�tations de F ��� qui correspondent auxdeux di��rents choix de bases de CG�
Lemme ��� Soit
F ��� �Xh�G
FhUh� avec Fh � C�W�X� Y� Z�
Le coe�cient de W n�Xn�Y n�Zn� dans la fonction Fh �num�re les mots depoids complet �n�� n�� n�� n�� dans le translat� de C��� de syndrome h � G�Lemme ��� Soit
F ��� �X�� �G
�F�e�� avec �F� � C�W�X� Y� Z�
La fonction �F� d�crit le poids complet �n�� n�� n�� n�� du mot ���g� � g � �� �C�����
�F� � �Wn� �Xn� �Y n� �Zn� �
Ainsi F ��� donne suivant la bases choisie l��num�rateur de poids completde C� ou les �num�rateurs de poids complets des translat�s de C� Les ma�trices propres P et Q permettent de passer d�une interpr�tation � l�autre�
Th�or�me ��� Soit � une classe dans une partition r�guli�re �G��� avecpartition duale � �G� E� et matrices propres P�Q� On a
F ��� �rX
i��
Fii�
�rX
j��
�Fjej�
Pour i � � � � � � � r� et g � �i�
Fi � Fg �
jGjrX
j��
�Qi�j �Fj� �����
Pour j � � � � � � � r� soit � � Ej��Fj � �F� � �W
n� �Xn� �Y n� �Zn� �
De plus ����n�n�n�n�
�� � �
����
�
� � ��
� ��
��
����
NS����ReS���ImS���
�� �
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
o�S��� �
Xg��
exp���g�� � Pj�i�
pour � � Ej� � � �i�Pour illustrer notre m�thode nous consid�rons l�exemple suivant � Soit uncode quaternaire C de matrice g�n�ratrice �G et matrice de contr�le �H
�G �
�� �H �
�
�
��
Le code C est �quivalent � son dual� Les �num�rateurs de poids de C� sont
cweC� � �W� � Y � � �XZ�� �
� W � � Y � � �W �Y � � �W �XZ � �Y �XZ � �X�Z� �
sweC� � W� � Y � � �W �Y � � �W �X� � �Y �X� � �X� �
lweC� � W
�X � �W �X� � �W �X� � �W �X� �
On a C � C��� avec � � f�� �� �� �� ��� �� �� ��g � G � Z� � Z�� Lafonction caract�ristique se d��nit par
�Xg��
Ug � CG�
On peut alors d�crire les sommes de trois �par exemple� �l�ments de � par
� �
� �� � CG� �����o" � est la fonction caract�ristique de �� � f�� ��� ��� �� ��� ��� ��� ��g� Lesmultiplicit�s du c�t� droit de l��galit� traduisent le fait qu�un �l�ment h � Gpeut �tre d�crit par soit dix �h � �� six �h � ��� ou z�ro �tout autre h�fa�ons comme une somme de trois �l�ments de ��L�ensemble � � f�� �� �� �� ��� �� �� ��g � G � Z� � Z� est invariant
par les automorphismes �x� y� �� �y� x�� �x� y� �� ��x� y�� Les orbites souscette action sont
�� � f�� �g�� � f�� �� �� �� ��� �� �� ��g
���� � f��� �� �� ��g���� � f�� ��� ��� �� ��� ��� �� �g�� � f�� ��� ��� �� ��� ��� ��� ��g�� � f��� ��g�
Remarquons que l�espace lin�aire engendr� par les fonctions caract�ristiquesest clos par multiplication� L�equation ��� ne donne qu�un exemple et onpeut voir que la partition � de G est r�gulire avec r � �� A partir de
���� LES CODES D�FINIS SUR Z� ��
�� �� ���� ���� �� ��
E� W W � W � W � W � WE� W W �XZ WY X�Z� XY �Z YE��� W W �Y � W � Y � W �Y � WE��� W X�Z� Y � W �Y � X�Z� WE� W XY �Z WY X�Z� W �XZ YE� W Y � W � W � Y � W
Tab� ��� % Poids complets pour les codes C�����
cette partition on peut d�terminer les valeurs propres Pj�i� Une valeur proprePg��i
��g�� pour � � �G� est d�termin�e par le poids complet d�un mot deC��i�
�� La Table ��� montre les di��rents poids complets pour les codesC����� � � �� Dans cet exemple les partitions � et E co(ncident� Parexemple le message �� �� � E� � �� produit le mot
�h�� ��� gi � g � ��� � ����� � C�����
de poids complet XY �Z� Le poids complet est le m�me pour tous les mes�sages dans E�� Les poids complets peuvent �tre remplac�s par des sommes decaractres S���� On obtient alors la premire matrice propre
P �
��������
� � � � � �� � � �� �� �� � � �� � � ��
������
�
Pour des raisons de sym�trie �� � E� nous avons P � Q et P � � �I� Lesidempotents primitifs de l�anneau de Schur S deviennent
�e�� e�� e���� e���� e�� e�� �
���� �� ���� ���� �� ��P�
Le code C��� avec � � f�� �� �� �� ��� �� �� ��g � G � Z��Z� admet sixdi��rents �num�rateurs de poids complet de translat�s�
�F�� F�� F���� F���� F�� F�� �
�� �F�� �F�� �F���� �F���� �F�� �F�� �Q
t �
� �F�� �F�� �F���� �F���� �F�� �F�� � � �W�� �W � �X �Z� �W � �Y �� �X� �Z�� �X �Y � �Z� �Y �� �
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
En ordonnant les termes de chacun des six �num�rateurs par rapport � leurpoids de Lee �de � �� nous obtenons la matrice
������������
W� � �
� W�X �W�Z �
�W�X� � �W�Z� � �W�Y � �W�XZ
� W�XY �W�Y Z �WX� �WZ� �WX�Z �WXZ� �
�W�Y � � �X�Z� �X� � Z� � �X�Z � �XZ� � �WX�Y � �WYZ�
� X�Y � Y Z� �XYZ� �X�Y Z �WXY � �WY �Z �
�X�Y � � � Y �Z� � �XY �Z � �WY �
� XY � � Y �Z �
Y � � �
� � �
� � �
W�X� �W�Z� � �W�XZ � �
� �W�XY � �W�Y Z � �WX�Z � �WXZ� �
�WX�Y � �WY Z� � �WXYZ � �W�Y � � �X�Z� � �WXY Z
� �XY Z� � �X�Y Z � �WXY � � �WY �Z �
X�Y � � Y �Z� � �XY �Z � �
� � �
���������
�
Chaque colonne repr�sente l��num�rateur de poids complet d�un translat��Les lignes correspondent un poids de Lee �x�� La Table ��� donne l��num�ra�tion de poids de Lee� La di cult� majeure de cette m�thode est de d�terminer
� � � � � � � �
� � �
� � � � �
� � � �
� � � �
� � �
�
Tab� ��� % Enum�rateurs de poids de Lee des translat�s pour le code C�����
une bonne partition r�gulire� Une fois celle�ci trouv�e les calculs se font ra�pidement � condition tout de m�me que la taille du code dual soit petite�C�est justement le cas des codes de Preparata� Notons R � GR��� m� et Tl�ensemble des carr�s de R �aussi appel� Teichm)ller�� Le code de Preparatad�ordrem sur Z� est d��ni par �� � �T � G � Z���Z��m� Le code dual estle code de Kerdock� Les syndr�mes du code de Preparata forment le groupeadditif Z��R� Nous d��nissons une partition � f�� �� � � � � rg d��l�mentsde Z� � R de telle sorte que deux syndr�mes soient dans la m�me classe siet seulement si ils admettent la m�me distribution de poids de classes� Cettepartition r�gulire admet au plus dix �l�ments pour tous les codes de Prepa�rata� Elle peut �tre d��nie de la manire suivante �
���� LES CODES D�FINIS SUR Z� ���������
� R � �� � �� � ���� R � �� � ����� R � �� � �� � ����� R � �� � ��
�������
� �R � �� � ���� T � ����� �R � ������T � ���
Les vecteurs messages pour le code dual forment le m�me groupe Z��R� Nousd��nissons une partition � � f�� � � ��� � � � � �sg des �l�ments du groupe detelle sorte que deux vecteurs messages soient dans la m�me classe si et seule�ment si les mots de codes correspondants ont la m�me composition de poidscomplte� Pour m impair avec �m � � b� la matrice propre P est��������������������������������
� � b� � b� � b� � � b� � b� � b� � b� � b� � b� � b� � � b� � b� � � b� � b� � �
� b� ib b � ib � � ib� �ib� �b � ib �b� ib ��
� b � ib b� ib � � �ib� ib� �b� ib �b� ib ��
� � ib� �� ib� � b� � � b� �� b� �� b� � b� �� b� � b� � ib� � � ib� �� ib� � � ib� � b� � �
� �� ib� � ib� � b� � � b� �� b� �� b� � b� �� b� � b� �� ib� � � ib� � ib� � � ib� � b� � �
� � � �� b� � b� �b� �b� � � � b� � �
� � � �� b� �� b� b� b� � � � b� � �
� �b� ib �b � ib � � �ib� ib� b � ib b� ib ��
� �b � ib �b� ib � � ib� �ib� b� ib b� ib ��
� �� b� �� b� � b� � � b� � b� � b� � b� � b� � b� �� b��� � b� �� b� � � b� � b� � �
��������������������������������
Pour m � pair avec �m � � b� la matrice propre P est��������������������������������
� � b� � b� �� b� � � b� � b� � b� � � b� � b� � � b� �� b� � � b� �� b� � � b� � b� � �
� � b � b � � � b� �� b� �� b �� b ��
� � ib �� ib � � �� b� � b� �� ib � ib ��
� � ib� �� ib� �� b� � � b� �� b� �� b� � � b� �� b� � � b� �� ib� � � ib� ��� ib� � � ib� � b� � �
� �� ib� � ib� �� b� � � b� �� b� �� b� � � b� �� b� � � b� ��� ib� � � ib� �� ib� � � ib� � b� � �
� � � �� b� � b� �� b� �� b� � � � b� � �
� � � �� b� �� b� � b� � b� � � � b� � �
� �� ib � ib � � �� b� � b� � ib �� ib ��
� �� b �� b � � � b� �� b� � b � b ��
� �� b� �� b� �� b� � � b� � b� � b� � � b� � b� � � b� � b� � �� b� � b� � �� b� � b� � �
��������������������������������
La matrice P permet d�obtenir les �num�rateurs de poids complet e�ectifpour une une longueur donn�e� En longueur �� �m � �� par exemple nousobtenons l�Octacode� Si nous consid�rons maintenant la m�trique de Leela partition r�gulire ne fait plus que cinq classes et nous obtenons cinqdi��rents �num�rateurs de poids de Lee des translat�s de l�Octacode� Lespartitions r�gulires permettent de construire de nouveaux codes� A partirde chaque classe on peut construire un code dont la matrice g�n�ratrice apour colonnes les �l�ments de la classe� Certains de ces codes ont de bonsparamtres #BD$�De plus la partition r�vle de jolies propri�t�s combinatoires de l�anneau deGalois de caract�ristique quatre � le sous�ensemble des carr�s dans un anneaude Galois sur Z� d��nit un ensemble � di��rences relatif �RDS� de paramtres��m� �m� �m� �� Rappelons que un RDS �m�n� k� �� dans un groupe G d�ordremn admettant un sous groupe normal N d�ordre n est un k�sous�ensemble
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
� � � � � � � � � � � � �
� � � � �
� �� �� �� � � �
� � ��
� � �
� � �� � � � � �
� � �� � � � �
Tab� ��� % Enum�rateurs de poids de Lee des translat�s de l� Octacode�
D tel que tout �l�ment de G n N est repr�sent� � fois comme d � d� pourd� d� � D et aucun �l�ment de N di��rent du neutre ne peut admettre cetterepr�sentation� Ici le groupe G est R � GR��� m� le sous groupe normalest �R� Chaque inversible peut s��crire d�une manire unique comme unedi��rence de deux carr�s�
���� PROPRI�T�S COMBINATOIRES DES CODES ��
��� Propri�t�s combinatoires des codes
Articles correspondants � ce thme �
�� Jacobi Polynomials Type II Codes and Designs A� BonnecazeB� Mourrain et P� Sol� Designs Codes and Cryptography �� ��� �������� May �����
�� ��Colored ��Designs and Z��Codes A� Bonnecaze E� Rains et P�Sol� The Journal of Statistical Planning and Inference� Vol � �� Issue �� May � ���� pp� ��������
�� Tricolore ��designs in Type III Codes A� Bonnecaze P� Sol� and P�Udaya Discrete Math Special Volume � Tverberg Anniversary Volumeto appear�
Lorsque l�on veut d�coder un code il est souvent utile de l�analyser end�tail et de v�ri�er s�il admet des propri�t�s combinatoires� Le code de Golaypar exemple peut se d�coder facilement en utilisant le fait qu�il admet dessystmes de Steiner� En g�n�ral les codes poss�dant des designs ont de grosgroupes d�automorphismes et de bons paramtres� Nous nous sommes toutd�abord attaqu�s au cas des codes binaires auto�duaux� Pour arriver � nos�ns nous avons utilis� un outil introduit par Ozeki en ���� le polyn�mede Jacobi� Pour plus de clart� nous n�avons pas francis� tous les noms bienconnus des concepts introduits� Ainsi nous pourrons utiliser les termes cosetleader ou block divisible design�
����� Le cas binaire
Designs
La d��nition suivante de design est plus g�n�rale �et donc moins forte�que lors du chapitre I� Un design de paramtres t� �v� k� ��a�� � � � � � �aNN �� estune collection de k�ensembles appel�s blocs d�un ensemble de v �l�ments etune partition de l�ensemble de tous les t�uplets en N groupes tel que tout en�semble appartenant au i�eme groupe �comprenant ai t�ensembles� est contenudans exactement �i blocs� Lorsque l�on parle de t�design sans plus de pr��cision on considre que N � � Consid�rons par exemple l�ensemble despoints d�un plan projectif sur Fq� Alors les droites repr�sentent les blocsd�un � � �q� � q � � q � � � design� Le th�orme d�Assmus�Mattson reliecodes et designs � soit C un #nkd$ code� Si le code dual a au plus d� t poidsdistincts non nuls et inf�rieurs ou �gaux � n� t alors les supports des motsd�un poids donn� dans le code ou son dual forment un t�design� Un codeest dit t�homogne si les mots de n�importe quel poids donn� d��nissent unt�design�
Un packing �resp� covering� design de paramtres t � �v� k� �� est un de�sign dont maxi��i� � � �resp� mini��i� � ��� #JD�� Chap� �$� Le nombre
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
de blocs minimum �resp� maximum� d�un covering �resp� packing� design etnot� C��v� k� t� �resp� D��v� k� t��� Un group�divisible block design �ouGDD� #BCN��$ not� GD�k� g� N� ��� ��� est un ��design ayant des blocs detaille k et N groupes de taille g tel que deux �l�ments d�un m�me groupeapparaissent dans exactement �� blocs et deux �l�ments de deux groupesdi��rents apparaissent dans exactement �� blocs� Les matrices d�incidencedes GDD produisent des graphes distances r�guliers �DRG� de diamtre �#BCN�� *����$� On observe qu�un GDD est un �� �gN� k� ��a�� � �a�� �� designa� �tant le nombre de paires appartenant � un m�me bloc et a� le nombre depaires appartenant � deux blocs distincts�
Polyn�mes de Jacobi
La th�orie des invariants est utilis�e depuis bien longtemps pour l��tudedes �num�rateurs de poids des codes auto�duaux �#MS��$ chapitre ���� Ce�pendant elle n�a �t� introduite que r�cemment dans l��tude des cosets �outranslat�s� de codes auto�duaux �#Oze��$ #BO��$�� Dans ce contexte Ozeki#Oze��$ a introduit un autre outil � le polyn�me de Jacobi� Le polyn�mede Jacobi correspondant � un ensemble T de coordonn�es d�un code C delongueur n sur F� est un polyn�me en quatre variables
JC�T �w� z� x� y� ��Xc�C
wm��c�zm��c�xn��c�yn��c�
o" T � �n� et o"mi�c� est la composition de Hamming de c sur T et ni�c� estla composition de Hamming sur �n�T � Si T est vide alors JC�T � WC�x� y��Les polyn�mes de Jacobi sont aussi trs utiles pour �tudier les propri�t�scombinatoires des codes� Le th�orme de MacWilliams pour ces polyn�mesest
Th�or�me ��� Ozeki Soit C un code binaire lin�aire� alors
JC��T �w� z� x� y� �
jCjJC�T �w � z� w � z� x � y� x� y�
Si C est un code de type II alors JC�T est un invariant simultan� au sensde Schur #Sch��$� Le nombre d�invariants simultan�s est donn� par une s�riede Molien � deux variables�
Invariants simultan�s
Nous savons que l��num�rateur de poids d�un code de type II est laiss�invariant par le groupe GII d��ni pr�c�demment� Un polyn�me de JacobiJC�T �w� z� x� y� est un invariant simultan� pour le m�me groupe agissant si�multan�ment sur chaque paire de variables �w� z� et �x� y�� Cela signi�e que
JC�T
�GII
�wz
�� GII
�xy
��� JC�T �w� z� x� y��
���� PROPRI�T�S COMBINATOIRES DES CODES ��
Un invariant simultan� au sens de Schur est donc un polyn�me f invariantpar l�action �diagonale� de GII� Nous appelons index de f�w� z� x� y� le degr�de f en w� z�Il existe une s�rie de Molien B�u� v� en deux variables qui �numre les inva�riants par leurs degr�s homognes en w� z et x� y �
B�u� v� ��
jGIIjXg�GII
det�� ug� det�� vg��
Cette s�rie est souvent appel�e s�rie bimolien�
Polarisation
Problme � Comment obtenir un invariant simultan� � partir d�un inva�riant absolu � L�utilisation de l�op�rateur de polarisation d�Aronhold per�met de r�pondre � la question�Soit P �x �resp� P
�y � la d�riv�e partielle par rapport � la variable x �resp�
y�� Soit P �x� y� un polyn�me en deux variables� L�op�rateur de polarisationd�Aronhold est d��ni par
A�P �w� z� x� y� �� wP �x�x� y� � zP�y�x� y��
On a alors �
Lemme ��� Si P est un invariant pour G alors A�P est un invariant simul�tan� pour G� L�application P �� AP est injective� l�application inverse �tantdonn�e par
nP �x� y� � AP �x� y� x� y��
On peut remarquer que l�index t augmente de � � chaque polarisation� Leth�orme suivant permet de d�terminer le polyn�me de Jacobi �
Th�or�me ��� Si les mots de code d�un poids donn� dans C forment unt�design� alors
JC�T �w� z� x� y� �
n�n� � � � � �n� t� �AtWC�x� y��
avec jT j � t � d�La notion de polarisation d�un �num�rateur de poids peut s�interpr�ter dela manire suivante� Consid�rons un code C de longueur n binaire et uneplace de coordonn�e i� Notons C � i� �resp� C�i�� le code �punctured� �resp�shortened�� par rapport � cette coordonn�e� Le translat� de C�i dans C � iest not� C � i� Lorsque le code est t�homogne le polyn�me de Jacobi JC�Tne d�pend pas de T pour jT j � t� Ce polyn�me est alors not� JC�t et pourn�importe quelle valeur de i on a
JC�fig � wWC�i � zWCi�
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
Si C ne contient pas de mot de poids nous avons
AWC�x� y� � wnXi��
WC�i�x� y� � znXi��
WCi�x� y��
Si C est �homogne
JC�� �
nAWC �
La g�n�ralisation donne le th�orme pr�c�demment �nonc��
Distribution de poids des translat�s
Soit C un code binaire lin�aire� Rappelons que le poids d�un coset x�Cest le plus petit i � tel que Ai�x� � � Le rayon de recouvrement r estle poids le plus grand parmi tous les poids des cosets de C� On observefacilement que si T est le support d�un coset leader xT de xT � C alorsJC�T �y� x� x� y� est l��num�rateur de poids de xT�C� Introduisons maintenantles trois paramtres suivants �% at�C� qui repr�sente la dimension de l�espace des polyn�mes �num�ra�teurs de poids des cosets de poids minimum t�
% bt�C� qui repr�sente la dimension de l�espace des polyn�mes de Jacobid�index t�
% cnt �G� qui repr�sente la dimension de l�espace des invariants simultan�sf de G tel que degw�z�f� � t et degx�y�f� � n� t� �t � r�
On a alors l�encadrement suivant
at�C� � bt�C� � cnt �G��La s�rie Bimolien de G peut s��crire
B�u� v� ��Xt�n��
cnt �G� utvn�t�
Propri�t�s combinatoires des codes
Gr'ce � la remarque suivante les polyn�mes de Jacobi deviennent unoutil pour d�tecter la pr�sence de designs � si JC�T est constant pour tout Ttel que jT j � t alors les mots qui correspondent aux mon�mes ayant m� �
forment un t�design avec d��ventuelles r�p�titions de blocs�
Exemple Consid�rons le code de Hamming ��� �� �C�est un code de type II dont l��num�rateur de poids est invariant par l�actionde GII � La s�rie Bimolien est
B�u� v� � � u � u�v � u�v� � u�v� � �u�v� � � � �
Le coe cient de u�v� dans la s�rie est � Cela signi�e que
b��C� � c
��G� �
���� PROPRI�T�S COMBINATOIRES DES CODES ��
et que le polyn�me de Jacobi ne d�pend pas de T pour jT j � �� Les motsde poids � dans le code forment donc les blocs d�un ��design� Lorsque t � �le coe cient de la s�rie est c��G� � � et il n�est pas possible de pr�diredirectement la pr�sence de designs� Une �tude plus approfondie #BMS��$montre qu�il existe deux polyn�mes de Jacobi correspondant � deux groupesde supports� On obtient donc un analogue de GDD pour t � ��Lorsque la polarisation ne donne pas un polyn�me � coe cients entiers nousdisons que la polarisation n�est pas possible� Cela signi�e que le code n�estpas homogne� Pour trouver une base de l�espace des invariants simultan�son utilise alors l�op�rateur de Reynolds d��ni dans #MS�� p����$�Avec l�aide de ces outils j�ai �tudi� les codes de type II binaires en longueur� �� �� et ��� En longueur �� il est possible de polariser jusqu�� l�index�� Ce resultat est tout � fait normal puisque le th�orme d�Assmus Mattsonpr�dit l�existence de ��designs dans un code ayant ces paramtres� Ce codes�il existe est donc ��homogne�
����� Le cas quaternaire
�Coding theorists think in binary and write in Q�ary�
Toute cette machinerie pr�c�dente se g�n�ralise trs bien dans le �monde Z���Les polyn�mes de Jacobi sont des polyn�mes en six variables lorsque l�onconsidre la composition de Lee et huit variables avec la composition com�plte� Une autre m�trique est aussi utilis�e � la m�trique euclidienne� Le poidseuclidien de x � Zn� est WE�x� �� n��x�� �n��x�� o" ni repr�sente le nombrede i dans x� Cette m�trique est la m�trique naturelle si l�on �tudie les liensentre les codes et les r�seaux arithm�tiques� Les codes de type II sont auto�duaux et leurs poids euclidiens sont multiples de huit� L�Octacode ��� �� � etle code de Golay relev� ���� �� � font partie de cette classe de codes�
��designs et code de Golay quaternaire
Lorsque nous avons construit le code de Golay quaternaire avec P� Sol�en ���� nous avons aussi cherch� � savoir si ce code contenait des ��designscomme son homologue binaire� Malheureusement une erreur de calcul m�aamen� � une r�ponse n�gative� En ���� Masaaki Harada prouva par calculsd�ordinateurs qu�il existait bien des ��designs dans le code de Golay relev� surZ�� D�un point de vue th�orique la pr�sence de PSL��� ��� dans le grouped�automorphismes permet seulement de pr�voir l�existence de ��designs� L�in�troduction des polyn�mes de Jacobi et de la th�orie des invariants me donnaitles outils d�une preuve th�orique� En octobre ���� nous publions un rapportde recherche du RMIT �RR N�� ���� Melbourne� donnant la preuve th�o�rique de l�existence de ces designs� Dans le m�me temps Iwan Duursma mefait savoir que E� Rains de ATT research vient d�introduire la notion dedesigns color�s qui g�n�ralise ou plut�t a ne celle de t�designs lorsque l�on
�� CHAPITRE �� LES DIFF�RENTS TH�MES DE RECHERCHE
travaille sur des codes Q�aires� Chaque poids d�un �l�ment de l�alphabet estrepr�sent� par une couleur� Il existe donc trois couleurs si l�on considre lam�trique de Lee� L�ensemble � des mots d�une composition de poids �x�eadmet un t�design color� si le nombre de mots de � ayant t couleurs prescritessur t coordon�es ne d�pend pas du choix des coordonn�es� Lorsque les cou�leurs et les points sont ordonn�s on parle alors de design color� fort �strongen anglais�� Un t�design ordinaire est un t�design fort � deux couleurs� Si legroupe d�automorphismes du code est t�homogne alors les mots de codesd�un poids de Lee donn� portent des t�designs� Si le groupe est t�transitif lesdesigns sont forts �l�inverse n�est �videmment pas vrai��Aprs avoir �chang� nos travaux respectifs nous d�cidons de les poursuivreen commun�Sur Z� la polarisation se d��nit de manire similaire au cas binaire� Soitun polyn�me P �x�� x�� x�� y�� y�� y�� arbitraire en six variables� Notons P
�i la
d�riv�e partielle par rapport � la variable yi� i � � � �� L�op�rateur depolarisation A est d��ni par
A�P �x�� x�� x�� y�� y�� y�� ��X
i��
xiP�i �x�� x�� x�� y�� y�� y���
Notons qu�en appliquant les substitutions �xi � yi� �A�P �x�� x�� x�� y�� y�� y��on obtient le polyn�me P �x�� x�� x�� y�� y�� y��� J�ai �tudi� le cas de di��renteslongueurs de codes� En longueur � il existe deux codes de type II de longueur� � O et Q� La s�rie bimolien est
f �� � �u � �u�v � �u�v� � �u�v� � �u�v� � � � �
Une base des espaces pour les index � � �� � et � est donn� par% wO wQ
% JO�� JQ��% JO�� JQ�� JQ���% JO�� JQ�� JQ���% JO�� JO��� JQ�� JQ���o" wC repr�sente l��num�rateur de poids sym�trique de C� la s�rie bimo�
lien montre qu�il existe � polyn�mes lin�airement ind�pendants �correspon�dants au terme �u�v��� Comment trouver ces trois polyn�mes � Le premierJO��� est d�termin� en polarisant trois fois l��num�rateur de poids de O�L��num�rateur de poids de Q ne se polarise qu�une fois� Cela signi�e que lecode ne contient que des �designs� Pour obtenir les deux autres polyn�mesil faut utiliser l�op�rateur de Reynolds qui permet d�obtenir une base de l�es�pace des invariants� Notons qu�en appliquant les substitutions d�crites plushaut aux trois polyn�mes calcul�s nous nous apercevons que JO��� co