X Maths PC 2006

Thème de l'épreuve Polynômes à coefficients 1 ou -1
Principaux outils utilisés arithmétique, récurrences d'ordre 1 et 2, calcul algébrique, équivalents de fonctions, séries entières

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2006 FILIÈRE PC

COMPOSITION DE MATHÉMATIQUES

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

***

Polynômes à coefficients 1 ou --1

Les polynômes étudiés dans ce problème ont été introduits lors de recherches 
sur la spectroscopie
multi--fentes. Ils ont donné lieu à des développements mathématiques en 
combinatoire, théorie
des codes, analyse harmonique, et a de très nombreuses applications en optique,
télécommunications, théorie des radars et acoustique.

Toute affirmation devra être soigneusement justifiée. La précision, la clarté
et la concision des raisonnements seront particulièrement appréciées.

Soit EUR un entier au moins égal à. 1. Dans ce problème, un vecteur @ de Re 
sera appelé séquence
de longueur EUR si chacune de ses EUR coordonnées vaut 1 ou ----1. Les 
coordonnées d'une séquence _a_

de longueur EUR seront numérotées de 0 à EUR -- 1, a = (ao, a1, . . . ,ag_1). 
On notera 8g l'ensemble des
séquences de longueur 6. On appellera simplement séquence, tout vecteur qui est 
une séquence

de longueur 6, pour un certain entier EUR > 1.

On dira que des séquences a et Q forment une paire complémentaire si elles ont 
même longueur
K (qui sera appelée dorénavant longueur de la paire) et si elles vérifient, 
dans le cas où EUR > 1,
pour tout entier j tel que 1 < j { EUR -- 1, la j--ième condition de 
corrélation :

Æ--1--j

z (az--a...-- + b,--b,--+j) = @.
i=0

Par convention, tout couple de séquences de longueur 1 est une paire 
complémentaire. Ainsi,
pour tout entier EUR > 1, la complémentarité d'une paire de longueur EUR 
implique EUR -- 1 conditions

de corrélation.

Première partie

On désigne par E l'ensemble des entiers EUR pour lesquels il existe au moins 
une paire complé--
mentaire de longueur EUR . Autrement dit, L est l'ensemble des longueurs de 
paires complémentaires.
Dans cette partie, on se propose d'étudier certaines propriétés de l'ensemble £.

1. Montrer que 2 appartient a £ et que 3 n'appartient pas a [...

Soit EUR un entier au moins égal à 1. Pour toute séquence, Q = (cm, (il, . .. 
,ag_1), de longueur
EUR, on définit le polynôme Pg_ par la formule

ê--1
PQ(X) = z a,;X' .
i=0
Un tel polynôme est appelé polynôme séquentiel.

2.3) Soient g,_ et Q des séquences. On considère la fonction définie pour au 
réel, a: # 0, par
50 '--> Pg(OE)Pg_(OE_1) + PQ(OE)Pg(OE_1) -

Montrer que si g_ et Q ne sont pas deux séquences de même longueur, cette 
fonction n'est pas
bornée sur ]0, +oo[.

Montrer que deux séquences _C_L_ et Q de même longueur forment une paire 
complémentaire si
et seulement si cette fonction est constante. Exprimer cette constante en 
fonction de la longueur

EUR de la paire complémentaire _a_, Q.

2.b) Montrer que si Q et Q sont des séquences de même longueur, PQ (1) et Pg(1) 
sont des
entiers de même parité. En déduire que tout élément de £ peut s'écrire comme la 
somme de deux
carrés d'entiers.

2.c) Montrer que le complémentaire de E dans N est un ensemble infini [on 
pourra étudier
le reste de la division par 4 d'un carré d'entier].

3.a) Soient Q et Q des séquences de même longueur. On pose U = %(ngPg) et V = 
%(PQ--PQ).
Montrer que Q et Q forment une paire complémentaire si et seulement si la 
fonction

oe +----> U(æ)U(oe"') + V(oe)V(af')

est constante sur son domaine de définition.

3.b) Les séquences, de longueur 10,
g = (1,1,-1,1,-1,1,-1,-1,1,1)

et
Q = (1,1,--1,1,1,1,1,1,--1,--1)

forment--elles une paire complémentaire ?

4. Démontrer, pour toute séquence @ de longueur paire 2m (m E N, non nul), 
l'équivalence
des assertions suivantes :

(i) 4 divise la somme % + m + ' - - + v2m_1,

(ii) le nombre de coordonnées de @ égales à --1 a la même parité que m,

(iii) 'U() 111 ° ° ' Uzm_1 = (_1)m_

5. Soit EUR E E, EUR > 2, et soient g et Q des séquences qui forment une paire 
complémentaire de
longueur EUR. Pour tout entier i, 0 { i EUR EUR -- 1, on pose oe,-- = a,b,--.

5.a) Montrer que, pour tout entier j , 1 { j { EUR -- 1,

Ë--1--j
,_.
H OEkOEk+j = (--1) ?
k=0
[considérer la somme des coordonnées de la séquence (ago,--, . . . , ag_1_ 
jag_1, bobj, . . . , bg_1_ jbg_1)].

5.b) En déduire que, pour tout entier j, 0 < j EUR EUR -- 1,
OEjOEg_1_j = ----1 .

5.0) Montrer que tout élément EUR de £, EUR > 2, est pair.

Deuxième partie

Si deux polynômes séquentiels sont associés à des séquences qui forment une 
paire complé--
mentaire, on dit qu'ils forment une paire complémentaire de polynômes. Cette 
partie est consacrée
à l'étude de certaines paires complémentaires de polynômes, dites paires de 
Rudin-Shapim.

On définit deux suites de polynômes (Pn)neN et (Qn)nEURN par les conditions 
initiales
P0(X) = Q0(X) = 1
et les relations de récurrence

Pn+1(X) : Pn(X) + X2nQn(--X)v (1)

Qn+1(X) = P,,(X) --X2nQn(X)- (2)
6.21) Calculer P1 et Q1, puis P2 et Q2.

6.b) Calculer les valeurs respectives de P,,(1), Q,,(1), P,,(--1) et Q,,(--l) 
en fonction de
l'entier n.

7. Démontrer que, pour tout entier positif n, les polynômes P,, et Q,, sont des 
polynômes
séquentiels et qu'ils forment une paire complémentaire. Qu'en déduire 
vis--à--vis de l'appartenance
des entiers de la forme 2h, pour k entier positif ou nul, à l'ensemble £ ?

8. Démontrer, pour tout entier positif ou nul n et tout nombre complexe non nul 
2 E C,
l'égalité
Qn(z) = (--1)"z2n_an(--z_l).

_ 9.a) Soit T un polynôme quelconque de C[X], de degré exactement d, d > 1, 
qu'on écrit
T (X ) = to +t1X +- - -+thd (avec td non nul). Montrer que les racines de T 
sont toutes majorées
en module par la quantité 1 + sup0
			

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Maths PC 2006 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a
été relu par Walter Appel (Professeur en CPGE) et Tristan Poullaouec (Professeur
agrégé).

Le sujet de l'École Polytechnique de cette année est particulièrement original.
On aurait tendance à dire qu'il s'agit d'algèbre, et pourtant pratiquement 
aucune
connaissance de cours n'est nécessaire à part quelques outils d'analyse ! Comme 
bien
souvent dans ce genre de cas, la difficulté est élevée en grande partie à cause 
de
l'originalité des questions.
Le sujet est composé de deux parties qui sont dans une très large mesure 
indépendantes. Il traite de vecteurs et de polynômes à coefficients dans 
l'ensemble {-1, 1}.
On cherche des couples de tels objets satisfaisant certaines conditions dites 
de complémentarité. L'ensemble des entiers  pour lesquels il existe deux 
vecteurs de taille 
(respectivement deux polynômes de degré -1) satisfaisant ces conditions est 
noté L.
· La première partie s'attache à trouver des conditions nécessaires pour qu'un
entier  soit un élément de L. À part une brève utilisation des équivalents de
fonctions et un tout petit peu d'arithmétique, on peut la traiter sans aucune
connaissance de cours.
· La deuxième partie est un peu plus proche de ce qui peut être demandé 
habituellement. On montre un certain nombre de propriétés portant sur deux
familles de polynômes. Naturellement, il faut utiliser à de nombreuses reprises
le raisonnement par récurrence (certaines preuves sont relativement longues à
rédiger). Les séries entières font leur apparition en toute fin de sujet et ce 
pour
deux petites questions.
Il ne s'agit certainement pas d'un sujet destiné à contrôler la maîtrise des 
connaissances du cours. En revanche, c'est sûrement un très bon test pour 
vérifier que vous
savez produire des raisonnements moins classiques, ce qui est nécessaire pour 
présenter les concours de l'École Polytechnique et des Écoles Normales 
Supérieures.

Indications
1 Pour montrer que 3 n'appartient pas à L, montrer que si la deuxième condition
de complémentarité est satisfaite, alors la première ne peut pas l'être.
2.a Déterminer les équivalents en + des fonctions
x 7- Pa (x)Pa (x-1 ) et

2.b

2.c
3.a
3.b
4

Pour la deuxième partie de la question, développer l'expression Pa (x)Pa (x-1 ),
puis regrouper dans la double somme obtenue les termes suivant l'exposant de x.
Si Pa (1) et Pb sont de même parité, il existe un entier m  Z tel que Pa (1) 
soit
égal à Pb (1) + 2m. Utiliser alors des identités remarquables pour écrire comme
somme de deux carrés l'entier (Pa (1)2 + Pb (1)2 )/2.
Montrer qu'un entier de la forme 4k + 3 ne peut s'écrire comme somme de deux
carrés d'entiers.
Développer l'expression U(x)U(x-1 ) + V(x)V(x-1 ) et l'exprimer en fonction
de Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 ).
Calculer les fonctions U(x) et V(x) pour ces séquences, puis utiliser le 
résultat
de la question précédente.
Introduire les ensembles
I = {i  [[ 0 ; 2m - 1 ]],

5.a

5.b
5.c
6.b
7

x 7- Pb (x)Pb (x-1 )

vi = 1}

et

J = {i  [[ 0 ; 2m - 1 ]],

vi = -1}

puis exprimer la somme et le produit des éléments v0 , . . . , v2m-1 en 
fonction du
cardinal de J.
Introduire la séquence proposée par l'énoncé et remarquer que la somme de
ses termes est nulle (donc multiple de 4) en raison de la j-ième condition de
complémentarité.
Considérer le quotient de deux relations consécutives obtenues à la question
précédente.
Si  est impair, regarder ce que donne la relation précédente avec un choix de j
judicieux.
Utiliser les formules de récurrence (1) et (2) du problème pour en déduire une
relation de récurrence entre ces suites. Interpréter matriciellement cette 
relation.
Montrer par récurrence que les polynômes Pn et Qn sont à coefficients entiers,
de degré 2n - 1 et que la fonction de la variable réelle
x 7- Pn (x)Pn (x-1 ) + Qn (x)Qn (x-1 )

est constante.
8 Raisonner une nouvelle fois par récurrence.
9.a Considérer une racine z de T. Traiter dans un premier temps le cas |z| 6 1.
d
Pour l'autre cas, commencer par majorer grossièrement |z| en utilisant le fait
que z est racine de T.
9.b Utiliser le fait que Pn et Qn sont à coefficients dans {-1, 1} et le 
résultat de la
question précédente.
10.a Remarquer que les 2n premiers coefficients de Pn sont les mêmes que les 2n
premiers de Pn+1 .
10.b Considérer une racine de S de module strictement inférieur à 1/2. Utiliser 
le
fait que S est à coefficients dans {-1, 1} et l'inégalité triangulaire pour 
minorer
le module de S(z).

Première partie
1 Considérons une paire de séquences a et b de longueur 2. Pour une telle 
longueur
de séquence, il n'y a qu'une seule condition de corrélation qui s'écrit
a0 a1 + b 0 b 1 = 0
Il suffit donc de prendre a = (1, 1) et b = (-1, 1) pour la satisfaire. Par 
conséquent,
L'entier 2 est un élément de L.
Considérons maintenant des séquences a et b de longueur 3. Il y a alors deux
conditions de corrélation qui sont données par
a0 a2 + b0 b2 = 0 et a0 a1 + a1 a2 + b0 b1 + b1 b2 = 0
Supposons la première condition satisfaite. Puisque les quatre coefficients a0 
, a2 , b0 , b2
sont des éléments de {-1, 1}, alors celle-ci impose que
a0 a2 = -1 et b0 b2 = 1

ou

a0 a2 = 1 et

b0 b2 = -1

Quitte à échanger les rôles de a et b, on peut supposer que ce sont a0 et a2 
qui sont
opposés et que b0 = b2 = +
- 1. Dans ce cas, il vient
a0 a1 + a1 a2 = a1 (a0 + a2 ) = 0
ce qui entraîne

|a0 a1 + a1 a2 + b0 b1 + b1 b2 | = |b1 | |b0 + b2 | = 2 6= 0

Les deux conditions de corrélation ne peuvent ainsi être simultanément 
satisfaites.
Il n'existe donc aucune paire de séquences complémentaires de longueur 3, ce qui
veut dire que
L'entier 3 n'est pas un élément de L.
2.a Soit a une séquence de longueur 1 et Pa le polynôme séquentiel associé.
Pour simplifier, on note également Pa sa fonction polynomiale associée. Cette 
fonction est alors continue et équivalente en l'infini à son terme de plus haut 
degré. Or,
celui-ci est le terme de degré 1 - 1, puisque a1 -1 est non nul car il 
appartient à
l'ensemble {-1, 1}. On a ainsi
Pa (x)

x+

a1 -1 x1 -1

et

lim Pa (x-1 ) = Pa (0) = a0

x+

ce qui donne par conséquent l'équivalent
Pa (x)Pa (x-1 )

x+

a0 a1 -1 x1 -1

Rappelons que les produits de ces équivalents ne sont valides que parce que
a0 n'est pas nul (il appartient lui aussi à l'ensemble {-1, 1}). Nous nous
permettrons de ne plus refaire ce type de justification dans tout le corrigé,
en particulier de mentionner à chaque instant que les éléments d'une séquence
sont non nuls (pour des divisions par exemple).
Soit maintenant b une seconde séquence de longueur 2 différente de 1 . Quitte
à échanger les séquences, on peut supposer que 2 est strictement inférieur à 1 
et
donc 1 > 2, puisque 2 est par définition supérieur à 1. Le même raisonnement
que précédemment montre que la fonction polynomiale associée à Pb admet en +
l'équivalent

Pb (x)Pb (x-1 )  b0 b2 -1 x2 -1 = o x1 -1
x+

On a donc l'équivalent suivant en +
Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 )

x+

a0 a1 -1 x1 -1

ce qui montre que la fonction tend vers + ou - en + (selon le signe de a0 a1 )
et n'est en particulier pas bornée. Par conséquent,
Si a et b ne sont pas des séquences de même longueur, la fonction
x 7- Pa Pa (x-1 ) + Pb (x)Pb (x-1 ) n'est pas bornée sur ] 0 ; + [.
Considérons maintenant deux séquences a et b de même longueur  et un réel x
non nul. Le réel Pa (x)Pa (x-1 ) peut s'écrire en fonction des coefficients de a
 -1
 -1

P
P
P
Pa (x)Pa (x-1 ) =
ak xk
ai x-i =
ak ai xk-i
(a)
i=0

k=0

06k,i6-1

Regroupons maintenant dans cette double somme les termes suivant l'exposant de 
x.
· Les termes d'exposant 0 sont ceux pour lesquels i = k, avec i  [[ 0 ;  - 1 ]].
Il y en a ainsi  et le coefficient de x0 dans (a) est donné par
-1
P 2
ai = 
i=0

puisque les éléments a0 , . . . , a-1 sont dans l'ensemble {-1, 1}.
· Pour chaque j  [[ 1 ;  - 1 ]], pour avoir k - i = j, l'indice i peut varier 
entre 0
et  - 1 - j, et alors k = i + j. Le coefficient de xj dans la somme (a) est donc
-1-j
P
ai+j ai
i=0

· Enfin, la fonction x 7 Pa (x)Pa (x-1 ) est symétrique par l'opération x 7 x-1 
:
on a donc les mêmes valeurs pour les puissances négatives de x (c'est-à-dire en
regroupant les termes pour lesquels k - i = j < 0).
Le réel Pa (x)Pa (x-1 ) s'écrit donc finalement
!
-1 -1-j
X

P
Pa (x)Pa (x-1 ) =  +
ai ai+j
xj + x-j
i=0

j=1

En effectuant les mêmes calculs pour le terme Pb (x-1 )Pb (x), on obtient ainsi
!
-1 -j-1
X

P
-1
-1
Pa (x)Pa (x ) + Pb (x)Pb (x ) = 2 +
ai ai+j + bi bi+j
xj + x-j
j=1

i=0

ce qui montre que si a et b sont deux séquences complémentaires, alors la 
fonction
est constante égale à 2.
Réciproquement, supposons qu'il existe au moins un entier j > 1 tel que la
j
P
somme
ai ai+j + bi bi+j soit non nulle. Soit j0 le plus grand d'entre eux. Alors,
i=0

Pa (x)Pa (x

-1

) + Pb (x)Pb (x

-1

)

x+

-1-j
P 0

ai ai+j0 + bi bi+j0

i=0

!

xj0 -1

ce qui montre que la fonction n'est pas bornée et donc pas constante. Par 
conséquent,
Deux séquences a et b de même longueur  sont complémentaires
si et seulement si la fonction x 7 Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 )
est constante. Elle est alors égale à 2.