\documentclass[11pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ \`a placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{14\baselineskip}
\topmargin=-6\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP21 Polyn\^omes et Codes 2 \hspace{1cm}}\hfill   agreg 2010 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
\exotitre{Codes de Golay; r\'esidus quadratiques}
\newcommand{\F}{{\rm I} \! {\rm F}}
\qu Nous allons \'etudier le code de Golay $G_{23}$, qui est un code cyclique en
caract\'eristique $2$, de longueur $23$. Il est de plus $3$ correcteur parfait.
\squ En factorisant $x^{23}-1$ dans $\rela/2\rela[x]$ on trouve deux facteurs
irr\'eductibles de degr\'e $11$. On en choisit un, not\'e $g$.
% Factor(x^23-1) mod 2;
\squ Comment peut on obtenir la liste des facteurs d'un polyn\^ome dans
$\rela/2\rela[x]$?  
% !s!<c>
%Astuce: pour recuperer directement le second facteur, on peut utiliser op, ou
%bien on utilise factors, mais
%il en faut la forme inerte pour travailler sur Z/2Z, d'ou les
%guillemets. Attention, ca ne marche pas toujours, par exemple si P:=x^23-1,
%'factors(P)' mod 2 ne marche pas. En revanche, on peut introduire les nombres
%modulaires comme en mode xcas grace a makemod, ou bien basculer en mode xcas,
%creer a:=1%2; et revenir en mode maple, puis utiliser a.
%!s!
% op(Factor(x^23-1) mod 2)
%g:= op(Factor(x^23-1) mod 2)[2]
%'factors(x^23-1)' mod 2)
%g:=('factors(x^23-1)' mod 2)[2][2,1];
%PP:=x^23-1;
%('factors(PP)' mod 2); # ne marche pas!
%a:=makemod(1,2);factors(x^23-a); #donne un resultat modulaire
\squ Pourquoi les racines de
$g$ sont elles  d'ordre 23? Combien y a t'il de carr\'es dans
$(\rela/23\rela)^\times$? Lesquels? En d\'eduire que $x^{23}-1$ avait forc\'ement
des diviseurs de degr\'e $11$ dans $\rela/2\rela[x]$. Exprimer les racines de $g$
en fonction d'une. (On prouvera ces r\'esultats de mani\`ere th\'eorique, en utilisant
le frobenius, et on illustrera ces r\'esultats en prenant une racine de $g$ dans
$\F_{2^{11}}$. 
%!s!<c>
%On ne peut pas creer F2[x]/g avec GF car les racines de g ne sont pas
%primitives dans (F_2^11) puisqu'elles sont d'ordre 23, et la commande GF veut
%un polynome irreductible dont les racines engendre le groupe multiplicatif du
%corps voulu. 
%!s!
%purge(a,FF); # pour eviter les Pb dans la ligne suivante.
%FF:=GF(2,11,['a','FF']);
%factor(g,FF(a));
%!s!<c>
%On note t la premiere racine de g trouvee dans F2048
%!s!
%t:=subs(x=0,factors(factor(g,FF(a)))[2][1,1]);
%!s!<c>
%On va maintenant comparer les racines de g avec les puissances de l'une d'entre
%elles: t. On va illustrer que ce sont les t^i ou i est un carre modulo
%23. On cree la liste des carres avec la fonction ensembles pour simplififer les
%doublons. 
%!s!
%carres:={seq(i^2 mod 23 ,i=1..22)};
%P:=1;for i in carres do P:=P*(x-t^i) od;
%normal(P);#On retrouve bien g
%g;
%!s!<c>
%On n'etait pasoblige de trouver une racine de g dans F2^11 defini par GF, on
%pouvait travailler modulo g.
%!s!
%purge(t);
%P:=1;for i in carres do P:=P*(x-t^i) od;
%Rem(P,subs(x=t,g),t) mod 2; #On travaille dans F2[t]/(g(t))
\qu On consid\`ere le code de Golay $G_{23}$ d\'efini par l'id\'eal  $(g)$ de
$\F_2[x]/(x^{23}-1)$ vu comme un $\F_2$ espace vectoriel. (Dans la suite, toutes les
coordonn\'ees seront prises dans la base $1,x,\dots,x^{22}$ ) Quel est le nombre
d'\'el\'ements de $G_{23}$? 
% !s!<c>
% G23 a 2^{23-deg(g)} elements. Le cardinal d'une boule de rayon 3 est la somme
% de C_23^i pour i allant de 0 \`a 3. L'annulation du terme suivant signifie que
% G23 a les invariants numeriques d'un code binaire 3 correcteur parfait de
% dimension 12 dans un espace vectoriel de dimension 23. 
% !s!
%normal(2^23-add(seq(binomial(23,i),i=0..3))*2^12);
\squ D\'eduire de la liste des carr\'es et du crit\`ere de minoration de la distance
d'un code cyclique (Cf cours) que $G_{23}$ est de distance au moins 5
% !s!<c>
% il y a 4 entiers consecutifs donc la distance est au moins 5
%!s!
% sort(op(carres));
\squ Donner une matrice g\'en\'eratrice\footnote{ie une base de l'espace
  vectoriel $G_{23}$} de $G_{23}$.
%G:=matrix(12,23,(i,j)->(coeff(Rem(x^(i-1)*g,x^23-1,x) mod 2,x,j-1)));
\qusqu Donner une matrice g\'en\'eratrice $GE$ du code \'etendu
$\widetilde{G_{23}}$\footnote{On ajoute un bit de   parit\'e} de $G_{23}$ 
%GE:=augment(G,transpose(G*[1$23]) mod 2); #le code etendu
\squ Trouver une matrice v\'erificatrice $VE$ de $\widetilde{G_{23}}$. On notera
$\widetilde{G_{23}}^\bot$ le code 
engendr\'e par $VE$. (Appel\'e code dual de $\widetilde{G_{23}}$).
%VE:=Nullspace(GE) mod 2;
\squ Montrer que $\widetilde{G_{23}}=\widetilde{G_{23}}^\bot$.
% !s!<c>
%Pour montrer que les espaces vectoriels engendr\'es par les lignes de GE et
%celles de VE sont les memes, on cree la matrice M suivante et l'on doit montrer
%qu'elle est de rang 12. On ne dispose pas d'une instruction de rang modulaire,
%on utilise donc Nullspace mod 2
%!s!
% M:=[op(GE),op(VE)];
% dim(Nullspace(M) mod 2);#c'est bien de rang 12
%%'rank(M)' mod 2;#ne marche pas. PB
\squ En d\'eduire que si $m$ et $m'$ sont des mots de $\widetilde{G_{23}}$ de
poids\footnote{c'est le nombre de coordonn\'ees non nulles} nul modulo $4$  alors
$m+m'$ aussi.\footnote{On remarquera que le produit scalaire $2(m.m')$ est dans
  $4\rela$} 
% !s!<c>
% puisque le code etendu est egal a son dual, on a:
% m.m'=0[2], et donc (m+m').(m+m')=m.m+m'.m' [4]
%Donc si les poids de m et m' sont multiples de 4, celui de m+m' aussi
%On en deduit que le code etendu a une distance multiple de 4, et comme elle
%vaut au moins 5, et qu'il y a des mots de poids 8, c'est 8. Donc celle de G23
%est 7 ou 8, et comme il y a des lignes de poids 7 dans G cette distance vaut 7
%!s! 
\squ Montrer que $\widetilde{G_{23}}$ est de distance $8$ et que $G_{23}$ est de
distance $7$. 
%!s!<c>
% ---------------------------------------------------------------------------------------------------------
%!s! 
\exotitre{Polyn\^ome orthogonaux; approximants}
(Cf matrices creuses ou d\'ecodage de codes cycliques). On consid\`ere un polyn\^ome $U=\sum_{i=0}^N u_i.x^i$ de terme constant non nul. On
note $(a_k,b_k,r_k)$ les 
coefficients de Bezout et le reste obtenus \`a l'\'etape $k$ de l'algorithme
d'Euclide \'etendu, de sorte que l'on ait: $a_k.x^{2n}+b_k.U=r_k$. On rappelle que
si l'on a une \'egalit\'e du type $$S.U=T+O(x^{2n})$$ o\`u $\deg S \leq n$ et $\deg T
<n$ alors il existe un unique entier $k$ tel que $\deg r_k \leq \deg T < \deg
r_{k-1}$, et il existe un polyn\^ome $W$  tel que $\deg W < \deg r_{k-1}-\deg r_k$
et $S=W.b_k, T=W.r_k$
\qu Cr\'eer une proc\'edure donnant $S$ et $T$ s'ils sont premiers  entre eux.
%!s!<p>
% ST:=proc(U,n)
% local a,aa,b,bb,r,rr,T,S,q;
% r:=U;rr:=x^(2*n);
% a:=1;b:=0;
% aa:=0;bb:=1;
% while (degree(r)>=n) do
% q:=quo(r,rr);
% tmp:=rr;rr:=normal(r-q*rr);r:=tmp;
% tmp:=aa;aa:=normal(a-q*aa);a:=tmp;
% tmp:=bb;bb:=normal(b-q*bb);b:=tmp;
% print("ca doit etre nul",normal(a*U+x^(2*n)*b-r));
% od;
% S:=a;T:=r;
% S,T;
% end;
% !s!
% normal( (x^3+1)*(x^3-1)*(x^2+x+1));
% !s!<c>
% on doit donc trouver S=x^3+1; T=-x^2-x-1 a facteur  pres 
%!s!
% ST((x^3-1)*(x^2+x+1),3);
\qusqu En utilisant une fonction d'orthogonalisation d\'ej\`a impl\'ement\'ee, appliqu\'ee au
produit scalaire de matrice $(u_{i+j})_{0\leq i,j\leq n}$ donner un orthogonalis\'e
de la famille $\{1,x,\dots,x^n\}$ pour quelques valeurs de $U$.
%!s!<m>
% MU:=proc(U,n)
% local PU;
% PU:=[seq(coeff(convert(series(U,x=0,2*n),polynom),x,i),i=0..2*n+1)];
% matrix(n+1,n+1,(i,j)->PU[i+j-1]);
% end;
% !s!
% !s!<m>
% scalU:=proc(p,q,n)
% local PU;
% ([seq(coeff(p,x,i),i=0..n)]*MU(U,n)*transpose([seq(coeff(q,x,i),i=0..n)]))[1];
% end;
% !s!
\squ Etudier le cas o\`u $U$ est le d\'eveloppement en s\'erie de
$${1\over {x+{1 \over {x^2+{1 \over {x^3+x+1+{1\over {x+2+{1\over x}}}}}}}}}$$
% purge(u):U:=add(u[i]*x^i,i=0..6);
% scalU(1,x,3);scalU(x^2,x^2,3);
% U:=1/(x+1/(x^2+1/(x^3+x+1+1/(x+2+1/x))));
% factor(gramschmidt([1,x,x^2,x^3,x^4],(p,q)->scalU(p,q,4)));
\squ Retrouver ces r\'esultats avec l'algorithme\footnote{On pourra introduire le
  polyn\^ome r\'eciproque de $S$ d\'efini par $\hat{S}(x)=x^{\deg S}S(\frac{1}{x})$}
pr\'ec\'edent.
%S:=[seq(pade(U,x,2*i-1,i),i=1..4)]
%!s!<c>
%On constate bien que les denominateurs des approximants de pade coincident a facteur
%pres avec les polyn\^omes reciproques des orthonormalises de schmidt
%(NB le polynome reciproque d'une polynome est le polynome cree a
%partir de la suite des coefficients pris dans l'ordre inverse. (Le
%facteur vient de la norme 1)
%!s!
%!s!<m>
%recip:=proc(P)
%normal(x^degree(P)*subs(x=1/x,P))
%end;
%!s!
%seq(recip(denom(i)),i=S); #donne bien les polyn\^omes obtenus par gramschmidt
%
\qu Matrices creuses; polyn\^ome minimal: On se donne une matrice $M$ de taille
$N$ ayant au plus $c$ termes non nuls par ligne.
\squ Etudier (dans la documentation de xcas) l'algorithme utilis\'e par xcas pour
calculer le polyn\^ome minimal d'une matrice. Motiver la m\'ethode probabiliste en
explicitant les mauvais cas.
\squ Si $M$ est inversible, expliquer comment r\'esoudre un syst\`eme $M.a=b$
lorsque l'on connait $P$. Calculer le nombre d'op\'erations sur le corps de base
si l'on connait $P$, et comparer le au cout du pivot de Gauss.
\squ On note $P_{u,v}$ un g\'en\'erateur de l'id\'eal $\{P, ^t v.P(M).u=0\}$. Montrer de
m\^eme qu'il existe des vecteurs $v,u$ tels que $P_{u,v}$ soit le polyn\^ome minimal
de $M$. Motiver le choix al\'eatoire de $u,v$.
\squ On note $u_l=^t v.M^l.u$ et $p_0,\dots,p_n$ les coefficients suivants de
$P_{u,v}(x)=\sum_{i=0}^n p_{n-i}x^i$. On pose $U=\sum\nolimits_{i=0}^{2n}u_i x^i $. On a alors
l'\'egalit\'e: $$P_{u,v}.U+x^{2n}Q=T$$
o\`u $\deg(T)<n$ et $\deg(P_{u,v}\leq n$. On peut donc trouver $P_{u,v}$ par la
m\'ethode pr\'ec\'edente.
\newpage
\end{multicols}

\end{document}

