Agrégation mathématiques externe 2020, épreuve 1Sujet et rapport du jury

Agrégation externe section mathématiques - Sujet de la première épreuve écrite de la session 2020

Pas encore noté

Réduction des endomorphismes (noyau, rang, valeurs propres, diagonalisation)
Polynômes et racines, inégalités de Cauchy et Hadamard
Orthogonalisation de Gram-Schmidt
Corps finis et arithmétique des polynômes
Systèmes linéaires
Réseaux euclidiens

Explorer les annales

BanqueAgrégation Année2020 FilièreExterne MatièreMathématiques

Annales Agrégation Externe Mathématiques Agrégation Externe 2020 Externe Mathématiques Mathématiques 2020

Téléchargements

Télécharger le sujet (PDF)

Rapport du jury Lire en ligne LaTeX Word

Corrigé : pas encore disponible

Source officielle : devenirenseignant.gouv.fr

Présentation du sujet

Difficile

Algorithmique de la factorisation des polynômes à coefficients rationnels (stratégie de Lenstra-Lenstra-Lovász)

Le sujet de mathématiques générales traite de l'algorithmique de la factorisation des polynômes à coefficients rationnels, en suivant une variante de la stratégie de Lenstra, Lenstra et Lovász. Il s'ouvre par quatre exercices préliminaires classiques (algèbre linéaire, borne de Cauchy, orthogonalisation de Gram-Schmidt, corps finis), avant cinq parties qui construisent progressivement l'algorithme, utilisant notamment la méthode de Cantor-Zassenhaus et une variante de l'algorithme de Gauss de réduction des formes quadratiques.

1Exercices 1 à 4 préliminairesÉtude explicite d'une matrice (noyau, rang, valeurs propres, diagonalisation), borne de Cauchy et lemme de Hadamard-Gershgorin, orthogonalisation de Gram-Schmidt et inégalité de Hadamard, décomposition de t^(p^n) - t sur les corps finis.
2Partie I : préparation de l'analyse de l'algorithmeRésultats préliminaires sur les suites de matrices et les systèmes d'équations linéaires servant de socle à l'algorithme.
3Partie II : borne sur les facteursJustification précise de la stratégie de reconnaissance des facteurs entiers via une borne sur les coefficients, en s'appuyant sur les exercices préliminaires.
4Partie III : factorisation modulo pUtilisation de la méthode de Cantor-Zassenhaus pour factoriser modulo p (méthode probabiliste).
5Partie IV : réduction des formes quadratiquesÉtude d'une variante dégradée de l'algorithme de Gauss de réduction des formes quadratiques binaires, écrite dans le langage des réseaux.
6Partie V : recherche de vecteurs courtsUtilisation de la méthode BKZ pour le calcul de vecteurs courts non nuls dans un réseau, à la place de l'algorithme LLL original.

Difficile. Le rapport indique que la grande majorité des candidats s'est cantonnée aux exercices et à la partie I, qu'aucun candidat n'est réellement rentré dans la partie V, et que même des exercices sans difficulté particulière n'ont été que moyennement réussis.

Ce qu'a observé le jury

6 erreurs relevées

Exercice 1 étonnamment mal réussi · Exercice 2 globalement mal traité · Changement de base mal compris

Le sujet était conçu pour permettre aux candidats ayant des connaissances solides en algèbre linéaire et précis dans leur rédaction de tirer leur épingle du jeu. La grande majorité des candidats s'est cantonnée aux exercices et à la partie I ; les toutes meilleures copies ont traité les quatre exercices et les deux premières parties, se sont parfois attaquées à la partie III voire IV, mais aucun candidat n'est réellement rentré dans la partie V.

Les erreurs les plus sanctionnées

1
Exercice 1 étonnamment mal réussiExercice 1
Cet exercice sans difficulté particulière n'a été que très moyennement réussi : moins de 20 % des candidats ont obtenu la totalité des points, et la moyenne n'était que d'environ 60 % des points.
« les candidats n'ont obtenu en moyenne que 60% des points environ »
2
Exercice 2 globalement mal traitéExercice 2, 2.1
Les trois quarts des candidats ayant abordé cet exercice n'ont obtenu que de l'ordre de 30 % des points en moyenne, et la question 2.1, pourtant au programme, n'a été correctement traitée que dans un quart des copies.
« les 3/4 des candidats l'ayant abordé n'ont obtenu que de l'ordre de 30% des points en moyenne »
3
Changement de base mal compris
L'opération de changement de base semble mal comprise par les candidats, qui la réduisent à un formulaire dans lequel on pioche de manière aléatoire sans revenir à l'objet mathématique représenté.
4
Équivalence des normes utilisée à tort de façon quantitative2.4
Certains candidats utilisent l'équivalence des normes en dimension finie comme un énoncé quantitatif pour remplacer une norme par une autre dans une inégalité, ce qui est erroné.
5
Raisonnements par récurrence imprécis3.1a, 3.1c
Le jury rappelle son attachement à ce qu'au moins un raisonnement par récurrence soit conduit rigoureusement, avec domaine, hypothèse, initialisation et hérédité clairement identifiés, ce qui est rarement le cas.
6
Démarche imposée de l'exercice 3 mal compriseExercice 3
L'exercice imposait un chemin précis pour construire la base de Gram-Schmidt, en étudiant d'abord la non-nullité des vecteurs dans un contexte abstrait, mais cette démarche a été mal comprise par les candidats.

Ce qui a été bien réussi

Les exercices, proches du cours (Hadamard-Gershgorin, Gram-Schmidt, construction des corps finis) ou de développements d'oral classiques, étaient largement accessibles aux candidats bien préparés.
Les toutes meilleures copies ont montré une maîtrise solide et une vraie élégance dans le raisonnement algébrique, saluées par le jury.
La question 3.3 a été souvent bien traitée par ceux qui s'y sont essayés.

Conseils du jury

Soigner particulièrement la rédaction des premières questions ou des premiers exercices, qui met le correcteur dans de bonnes dispositions pour la suite de la copie.
Pointer clairement les théorèmes utilisés et vérifier systématiquement toutes leurs hypothèses, ainsi que les résultats des questions précédentes réutilisés.
Ne pas se précipiter sur les parties avancées au détriment des exercices préliminaires : une rédaction irréprochable sur les premières questions permet de faire le plein de points.
Argumenter proprement par double inclusion ou double inégalité plutôt que d'affirmer péremptoirement un résultat, notamment quand un sens semble évident.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Description

Sujet officiel Agrégation externe en mathématiques, session 2020.

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

EAE MAT 1

SESSION 2020

AGREGATION
CONCOURS EXTERNE

Section : MATHÉMATIQUES

COMPOSITION DE MATHÉMATIQUES GÉNÉRALES

Durée : 6 heures

L'usage de tout ouvrage de référence, de tout dictionnaire et de tout matériel électronique (y compris la calculatrice) est rigoureusement interdit.

Si vous repérez ce qui vous semble être une erreur d'énoncé, vous devez le signaler très lisiblement sur votre copie, en proposer la correction et poursuivre l'épreuve en conséquence. De même, si cela vous conduit à formuler une ou plusieurs hypothèses, vous devez la (ou les) mentionner explicitement.

NB : Conformément au principe d'anonymat, votre copie ne doit comporter aucun signe distinctif, tel que nom, signature, origine, etc. Si le travail qui vous est demandé consiste notamment en la rédaction d'un projet ou d'une note, vous devrez impérativement vous abstenir de la signer ou de l'identifier.

Les calculatrices, téléphones, tablettes, ordinateurs, montres connectées et tous appareils électroniques de communication ou de stockage, ainsi que les documents sont interdits.

La qualité de la rédaction est un facteur important d'appréciation des copies. Les candidats sont donc invités à produire des raisonnements clairs, complets et concis.

Les candidats peuvent utiliser les résultats énoncés dans les questions ou parties précédentes, en veillant dans ce cas à préciser la référence du résultat utilisé.

Notations et rappels.

-Si $ℰ$ est un ensemble fini, on note $#ℰ$ son cardinal.
-Si $x$ est un nombre réel, on note $E(x)$ sa partie entière.
-Si K désigne le corps des nombres réels R ou le corps des nombres complexes C, pour tous entiers naturels non nuls $d, e$ , on note $M_(d, e)(K)$ le $K$ -espace vectoriel des matrices à $d$ lignes et $e$ colonnes à coefficients dans K; lorsque $d = e$ , on note aussi $M_d(K)$ la K-algèbre des matrices à $d$ lignes et $d$ colonnes à coefficients dans K, $GL_d(K)$ le groupe des matrices inversibles, et $I_d$ la matrice identité dans $M_d(K)$ .
-Si $M = (m_(ij))_(i, j ∈ {1, …, d}) ∈ M_d(K)$ , on note $^t M = (m_(ji))_(i, j ∈ {1, …, d}) ∈ M_d(K)$ sa transposée.
-Une matrice $M$ de $M_d(K)$ définit un endomorphisme sur $K^d$ , endomorphisme qui envoie un vecteur $V$ de $K^d$ sur le vecteur $MV$ . Cet endomorphisme est aussi noté $M$ .
-Si $v = (v_1, \dots, v_d) \in K^d$ , on note $‖v‖_2 = (\sum_(i = 1)^d|v_i|^2)^(1/2)$ et $‖v‖_∞ = max_(i ∈ {1, …, d})|v_i|$ . Pour tout entier $k \geq 0$ , si $g = \sum_(i = 0)^k g_i t^i \in K[t]$ est un polynôme de degré au plus $k$ , on note $‖g‖_2 = (\sum_(i = 0)^k|g_i|^2)^(1/2)$ et $‖g‖_∞ = max_(i ∈ {0, …, k})|g_i|$ .
-Si $p$ est un nombre premier, on note $π_p$ la projection canonique sur $Z/pZ$ , c'est-à-dire le morphisme d'anneaux qui envoie un entier sur sa classe modulo $p$ . Cette projection canonique s'étend en une application, notée elle aussi $π_p$ , sur l'algèbre des polynômes $Z[t]$ , ainsi définie : si $P = \sum_(i = 0)^d a_i t^i \in Z[t]$ est un polynôme, on note $π_p(P)$ le polynôme $\sum_(i = 0)^d π_p(a_i)t^i \in Z/pZ[t]$ .
-On rappelle que l'anneau $Z[t]$ est un anneau factoriel. On pourra utiliser sans démonstration le fait que deux polynômes $f$ et $g$ à coefficients entiers dont l'un est unitaire ont un unique $pgcd$ unitaire qu'on notera $pgcd(f, g)$ . Ce pgcd est aussi l'unique $pgcd$ unitaire de $f$ et $g$ considérés dans $Q[t]$ .
-Soit $f = t^d + \sum_(i = 0)^(d - 1)f_i t^i \in C[t]$ un polynôme unitaire de degré $d \geq 1$ . On lui associe la

matrice

A_f = (0, 0, 0, \dots, 0, 0, - f_0; 1, 0, 0, \dots, 0, 0, - f_1; 0, 1, 0, \dots, 0, 0, - f_2; ⋮, ⋱, ⋱, ⋮, ⋮; ⋮, ⋱, ⋱, ⋮, ⋮; 0, 0, 0, \dots, 1, 0, - f_(d - 2); 0, 0, 0, \dots, 0, 1, - f_(d - 1)) \in M_d(C).

On rappelle que le polynôme caractéristique de

A_f

est

f

.
Les questions préliminaires des différentes parties ont été rassemblées, sous forme d'exercices, au début du sujet; il est vivement conseillé de les traiter en priorité.

Exercice 1

On considère la matrice

A = (1/2, 1/2, 0, 0; 1/4, 1/4, 1/2, 0; 1/8, 1/8, 1/4, 1/2; 1/8, 1/8, 1/4, 1/2) \in M_4(R).

1.Déterminer la dimension du noyau de la matrice $A$ .
2.Quel est le déterminant de $A$ ? Préciser le rang de $A$ .
3.Déterminer les valeurs propres de la matrice $A$ .
Indication : on pourra calculer $A(1; 1; 1; 1)$ et $A(2; 0; - 1; - 1)$ .
La matrice $A$ est-elle diagonalisable ?

Exercice 2

Soit

f = t^d + \sum_(i = 0)^(d - 1)f_i t^i \in R[t]

un polynôme unitaire de degré

d \geq 1

à coefficients réels.

1.Soit $A = (a_(ij))_(i, j ∈ {1, …, d}) ∈ M_d(C)$ une matrice. Montrer que si $λ \in C$ est tel que, pour tout $i, |a_(ii) - λ| > \sum_(j \neq i)|a_(ij)|$ , alors $A - λI_d$ est inversible.
2.Soit $λ$ une racine de $f$ : montrer que la matrice $A_f - λI_d$ , avec la définition (1), n'est pas inversible.
3.Soit $μ$ dans C tel que $|μ| > 1 + max_(i ∈ {0, …, d − 1})|f_i|$ ; montrer que la matrice $A_f - μI_d$ est inversible. En déduire que toutes les racines $ρ$ de $f$ vérifient $|ρ| \leq 1 + ‖f‖_\infty$ .
4.Soit $g = t^k + \sum_(j = 0)^(k - 1)g_j t^j \in C[t]$ un polynôme unitaire divisant $f$ , où $k \geq 1$ . Montrer que
$‖g‖_\infty \leq (2 + 2‖f‖_\infty)^k.$

Exercice 3

Pour

u

v

deux vecteurs de

R^n

, on note

(u|v) = \sum_(i = 1)^n u_i v_i

leur produit scalaire usuel. Soit

(b_1, \dots, b_d)

une famille de

d

vecteurs linéairement indépendants de

R^n

1.On se propose de démontrer qu'il existe une famille de $d$ vecteurs $(b_1^*, \dots, b_d^*)$ vérifiant les propriétés :
- $[P1]b_1^* = b_1$ .
- [P2] pour $i ∈ {2, …, d}, b_i^∗ = b_i − ∑_(j < i)μ_(ij)b_j^∗$ , avec pour tout $j$ dans ${1, .., i − 1}, μ_(ij) = ((b_i|b_j^∗))/((b_j^∗|b_j^∗))$ .
- $[P3](b_i^*|b_j^*) = 0$ pour tous $i, j$ dans ${1, \dots, d}$ tels que $i \neq j$ .
- (a)Soient $(b_1^♯, \dots, b_d^♯)$ des vecteurs de $R^n$ tels que $b_1^♯ = b_1$ et, pour tout $i$ dans ${2, \dots, d}$ , il existe des nombres réels $(α_(ij))_(1 \leq j \leq i)$ tels que $b_i^♯ = b_i - \sum_(j < i)α_(ij)b_j^♯$ . Démontrer que, pour tout $i$ dans ${1, \dots, d}$ , $Vect(b_1, \dots, b_i) = Vect(b_1^♯, \dots, b_i^♯)$ et en déduire que $b_i^♯$ est non nul.
- (b)Construire par récurrence une famille de $d$ vecteurs $(b_1^*, \dots, b_d^*)$ vérifiant les propriétés [P1] et [P2].
- (c)Démontrer que la famille de vecteurs ainsi construite vérifie la propriété [P3].

On note

B

la matrice de

M_(n, d)(R)

dont les colonnes sont les vecteurs

b_1, \dots, b_d

dans cet ordre.

2.Montrer que $\prod_(i = 1)^d‖b_i^*‖_2 = (det^t BB)^(1/2)$ .
3.En déduire que, si $d = n$ , $|detB| \leq \prod_(i = 1)^d‖b_i‖_2$ .

Exercice 4

Soit

p

un nombre premier. Si

n

est un entier naturel, on définit

P_n \in Z[t]

par

P_n = t^(p^n) - t

1.Soient $r$ et $n$ deux entiers naturels, avec $r > 0$ ; on note $n = qr + k, 0 \leq k < r$ , la division euclidienne de $n$ par $r$ . Montrer qu'il existe un polynôme $Q \in Z[t]$ tel que $P_n = QP_r + P_k$ .
2.En déduire que $pgcd(P_n, P_r) = P_(pgcd(n, r))$ .
3.Soit $f \in Z/pZ[t]$ un polynôme irréductible de degré $r$ ; on note $(f)$ l'idéal $fZ/pZ[t]$ . Montrer que l'anneau $F = Z/pZ[t]/(f)$ est un corps fini de cardinal $p^r$ . En déduire que $f$ divise $π_p(P_r)$ .

Soit

I_n

l'ensemble des polynômes irréductibles unitaires de degré divisant

n

dans

Z/pZ[t]

. On considère le polynôme :

Q = \prod_(φ \in I_n)φ.

4.Démontrer que $Q$ divise $π_p(P_n)$ .

Dans la suite du problème, on admettra l'égalité

Q = π_p(P_n)

Préambule au problème

L'objet de ce problème est de développer un ensemble d'outils permettant de calculer la décomposition en produit de puissances de polynômes irréductibles d'un polynôme unitaire de

Z[t]

, en la déduisant d'un procédé analogue dans

Z/pZ[t]

.
La stratégie est de construire, étant donné un nombre premier

p

assez grand, un polynôme

g \in Z[t], degg < degf

, ayant de "petits" coefficients et tel que

pgcd(π_p(f), π_p(g)) \neq 1

.
Le problème s'organise de la manière suivante :

-La première partie étudie une suite matricielle de type arithmético-géométrique; elle établit des résultats qui seront utiles dans la dernière partie.
-La deuxième partie établit que la stratégie est fondée, c'est-à-dire que si $g$ est comme ci-dessus, alors $pgcd(f, g) \notin {1, f}$ dans $Z[t]$ .
-La troisième partie propose une méthode de factorisation dans $Z/pZ[t]$ .
-Les deux dernières parties décrivent un procédé qui peut être utilisé pour construire le polynôme $g$ , ou a contrario prouver l'irréductibilité de $f$ .

Partie 1

Dans cette partie,

d

est un entier naturel

\geq 2

. On note

- $H$ l'hyperplan de $R^d$ défini par $H = {(x_1, …, x_d)$ tel que $\sum_(i = 1)^d x_i = 0}$ ,
- $E$ le vecteur de $R^d$ dont toutes les coordonnées sont égales à 1.

Pour

k \in {1, \dots, d - 1}

, on introduit les matrices

M_k \in M_d(R)

définies par

∀i, j ∈ {1, …, d}, (M_k)_(ij) = {δ_(ij), si i ∉ {k, k + 1}; 1/2, si (i, j) ∈ {k, k + 1}^2; 0, sinon

où

δ_(ij) = 1

i = j

δ_(ij) = 0

sinon.

1.Soit $k$ dans ${1, \dots, d - 1}$ .
- (a)Démontrer que $R^d = Vect(E) \oplus H$ , que $E$ est un vecteur propre de $M_k$ associé à la valeur propre 1, et que $H$ est stable par l'endomorphisme associé à $M_k$ dans la base canonique de $R^d$ .
- (b)Montrer que pour tout $x \in R^d, ‖M_k x‖_2 \leq ‖x‖_2$ . Etudier le cas d'égalité.

On pose

A = M_(d - 1) \cdot M_(d - 2)\dots\dotsM_2 \cdot M_1

2.Démontrer que $E$ est un vecteur propre de $A$ associé à la valeur propre 1, et que $H$ est stable par l'endomorphisme associé à $A$ dans la base canonique de $R^d$ .
3.Montrer que si $x \notin Vect(E)$ , alors $‖Ax‖_2 < ‖x‖_2$ . En déduire que le sous-espace propre associé à la valeur propre 1 est $Vect(E)$ .
4.Soit $A_H$ l'endomorphisme induit par $A$ sur $H$ . Justifier que la limite de la suite $(A_H^k)_(k \in N)$ est l'endomorphisme nul.

On note

Π

la projection sur

Vect(E)

parallèlement à

H

5.Démontrer que la suite $(A^k)_(k \in N)$ converge vers $Π$ .

Soit

G

un vecteur dans

H

6.Démontrer que l'équation $X = AX + G$ admet une unique solution dans $H$ , qui sera notée $Z$ . En déduire l'ensemble des solutions de l'équation $X = AX + G$ d'inconnue $X \in R^d$ .
7.Soit $X_0 \in R^d$ un vecteur et $(X_ℓ)_(ℓ \in N)$ la suite d'éléments de $R^d$ définie par récurrence par
$X_(ℓ + 1) = AX_ℓ + G, ℓ \in N.$
Démontrer que la suite $(X_ℓ)_(ℓ \in N)$ converge vers le vecteur
$lim_(ℓ \to \infty)X_ℓ = Π(X_0) + Z,$

Partie 2

Soit

f = t^(degf) + \sum_(j = 0)^(degf - 1)f_j t^j

un polynôme unitaire de

Z[t]

non constant.

1.Soit $g = \sum_(j = 0)^(degg)g_j t^j$ un polynôme de $Z[t]$ , qu'on suppose premier avec $f$ .
- (a)Justifier l'existence de $u = \sum_(j = 0)^(degg - 1)u_j t^j$ et $v = \sum_(j = 0)^(degf - 1)v_j t^j$ dans $Q[t]$ tels que
  $uf + vg = 1.$

Pour

i \in {0, \dots, degg - 1}

j \in {0, \dots, degf - 1}

, on introduit les vecteurs

w_i

z_j deR^(degf + degg)

définis par

w_i = (0; ⋮; 0; f_0; f_1; ⋮; f_(degf); 0; ⋮; 0)}}}{{z_j = (0; ⋮; 0; g_0; g_1; ⋮; g_(degg); 0; ⋮; 0)}}}{{jdegg − 1 − i degf − 1 − j

et la matrice

M(f, g)

dont les colonnes sont

w_0, \dots, w_(degg - 1), z_0, \dots, z_(degf - 1)

, de sorte que l'identité

uf + vg = 1, u = \sum_(i = 0)^(degg - 1)u_i t^i, v = \sum_(i = 0)^(degf - 1)v_i t^i

se réécrit sous la forme du système linéaire suivant :

M(f, g)(u_0; u_1; ⋮; u_(degg - 1); v_0; v_1; ⋮; v_(degf - 1)) = (1; 0; ⋮; 0).

- (b)Montrer que | $detM(f, g)|$ est un entier naturel inférieur ou égal à $‖f‖_2^(degg)‖g‖_2^(degf)$ . On admet que $0 \neq detM(f, g)$ .
- (c)Soit $r = |detM(f, g)|$ . Démontrer que les polynômes $u~$ et $v~$ définis par $u~ = ur$ et $v~ = vr$ sont dans $Z[t]$ et vérifient $u~f + v~g = r$ .
- (d)Soit $p$ un nombre premier tel que $π_p(f)$ et $π_p(g)$ ne sont pas premiers entre eux dans $Z/pZ[t]$ .
  - i.Montrer que $p$ divise $detM(f, g)$ .
  - ii.En déduire que $p \leq ‖f‖_2^(degg)‖g‖_2^(degf)$ .
2.On suppose que le polynôme $f$ est sans facteur carré c'est-à-dire que la décomposition en produit de facteurs irréductibles de $f$ s'écrit sous la forme $f = \prod_(i = 1)^t f_i$ , où les $f_i$ sont irréductibles et deux-à-deux distincts. Soit $p$ un nombre premier tel que
$p > (degf)^(degf/2)‖f‖_2^(degf - 1)(2 + 2‖f‖_\infty)^(degf(degf - 1)).$
Soit $h \in Z[t]$ unitaire, $h \neq 1, h \neq f$ , et tel que $π_p(h)$ est un diviseur irréductible de $π_p(f)$ dans $Z/pZ[t]$ . On note
$L_p(h) = {h ⋅ h_1 + ph_2, h_1, h_2 ∈ Z[t], deg(hh_1) ≤ degf − 1, degh_2 ≤ degf − 1}.$
- (a)Montrer qu'il existe un polynôme irréductible $g \in Z[t]$ tel que $π_p(h)$ divise $π_p(g)$ et $g$ divise $f$ .
- (b)Montrer que $f$ n'est pas irréductible dans $Z[t]$ si et seulement s'il existe $u \in L_p(h)$ non nul avec
  $‖u‖_\infty \leq (2 + 2‖f‖_\infty)^(degf - 1)$
  et que dans ce cas $pgcd(u, f)$ est un diviseur non trivial de $f$ (c'est-à-dire que $pgcd(u, f) \notin {1, f})$ .
  Indication : on pourra remarquer que si $f$ n'est pas irréductible dans $Z[t]$ , alors $g \in L_p(h)$ , et exploiter les rappels faits en préambule sur $Z[t]$ .

Partie 3

Dans toute cette partie,

p

est un nombre premier différent de

2, f

est un polynôme unitaire, non constant, de

Z/pZ[t]

de degré

n

sans facteur carré, et on note

f = f_1\dotsf_r

la décomposition de

f

en produit de facteurs irréductibles unitaires dans

Z/pZ[t]

.
On définit deux suites de polynômes

(u_i)_(i ∈ N∖{0})

(g_i)_(i ∈ N∖{0})

Z/pZ[t]

par

u_1 = pgcd(f, t^p - t), g_1 = f/u_1 et, pour tout i \geq 2, u_i = pgcd(g_(i - 1), t^(p^i) - t), g_i = g_(i - 1)/u_i.

Les pgcd utilisés pour cette définition sont tous choisis unitaires.

1.(a) Montrer que $\prod_(i = 1)^n u_i = f$ .
- (b)Montrer que tous les facteurs irréductibles de $u_i$ sont de degré $i$ .
- (c)Montrer que $f$ est irréductible sur $Z/pZ[t]$ si et seulement si $f = g_(E(n/2) + 1)$ .

On fait maintenant l'hypothèse que

f = f_1\dotsf_r

, avec

r \geq 2

, les

f_i

irréductibles, deux à deux distincts et de même degré

d

. Soit

C

l'application

C : Z/pZ[t], ⟶ Z/pZ[t]; h(t), ⟼ h(t)^((p^d - 1)/2)

En notant

ω

la projection canonique de

Z/pZ[t]

sur

Z/pZ[t]/(f)

, l'application

C

définit par factorisation une application

C¯

(on ne demande pas de vérifier cela) :

C¯ : Z/pZ[t]/(f), ⟶ Z/pZ[t]/(f); ω(h), ⟼ ω(h)^((p^d - 1)/2).

Soit $h$ dans $Z/pZ[t]$ premier avec $f$ . Montrer que $C¯(ω(h))^2 = 1$ .
Montrer que $#C¯^(− 1)({1}) = #C¯^(− 1)({ − 1}) = ((p^d − 1)/2)^r$ .
On note $Z/pZ[t]_(rd)$ le sous-espace vectoriel de $Z/pZ[t]$ de dimension $rd$ constitué des éléments dont le degré est strictement inférieur à $rd$ .

(a)Soit $U$ une variable aléatoire de loi uniforme à valeurs dans $Z/pZ[t]_(rd)$ . On note $A$ l'événement ${pgcd(U, f) \notin {1, f}}$ et $B$ l'événement ${pgcd(C(U) - 1, f) \notin {1, f}}$ . Montrer que, pour $r \geq 2, p \geq 3$ et tout $d$ ,
$Pr(A \cup B) = 1 - 1/(p^(rd)) - 2((p^d - 1)/(2p^d))^r \geq 1/2.$
(b)Soit $(U_i)_(i \in N)$ une suite de variables aléatoires indépendantes de loi uniforme à valeurs dans $Z/pZ[t]_(rd)$ , et $S$ la variable aléatoire à valeurs dans $N \cup { + \infty}$ définie par
$S = min{i ∈ N tel que pgcd(U_i, f) ∉ {1, f} ou pgcd(C(U_i) − 1, f) ∉ {1, f}}$
avec la convention que le minimum de l'ensemble vide est $+ \infty$ . On note $E(S)$ son espérance. Montrer que $E(S) \leq 2$ .

Partie 4

Pour tout nombre réel

α

, on note

[α]

la partie entière de

α

α - 1/2

est un entier, et l'entier le plus proche de

α

sinon.
Pour tous vecteurs

u, v \in Q^d

avec

v

non nul, on pose

Q(u, v) = [((u|v))/(‖v‖_2^2)].

On note

M(u, v) \in M_(d, 2)(R)

la matrice dont la première colonne est

u

et la seconde colonne est

v

1.Montrer que $‖u - qv‖_2 \geq ‖u - Q(u, v)v‖_2$ , pour tout entier $q$ .
2.Montrer que $|(u - Q(u, v)v|v)| \leq ‖v‖_2^2/2$ .

À partir de maintenant, on suppose donnés deux vecteurs

u, v \in Q^d

linéairement indépendants dans

R^d

, et on pose

L(u, v) = {au + bv, (a, b) ∈ Z^2}

.
On construit deux suites

(u_n)_(n \in N), (v_n)_(n \in N)

de vecteurs de

Q^d

par :

u_0 = u, v_0 = v, (u_(n + 1), v_(n + 1)) = {(u_n, v_n) si ‖v_n‖_2 ≥ (‖u_n‖_2)/(√2) et n > 0,; (v_n, u_n − q_n v_n) avec q_n = Q(u_n, v_n) sinon.

3.Montrer que, pour tout $n$ , il existe $Γ_n(u, v) \in M_2(Z)$ , avec $|detΓ_n(u, v)| = 1$ , tel que $M(u_n, v_n) = M(u, v)Γ_n(u, v)$ .
4.Montrer que, pour tout $n, L(u_n, v_n) = L(u, v)$ .
5.Montrer qu'il existe $λ \in N∖{0}$ tel que, pour tout $x \in L(u, v), λx \in Z^d$ .
6.Montrer qu'il existe $k$ tel que $(u_(k + 1), v_(k + 1)) = (u_k, v_k)$ .
7.Pour cet entier $k$ on note $w$ le projeté de $v_k$ orthogonalement à $Vect(u_k)$ . Montrer que $‖w‖_2 \geq ‖u_k‖_2/2$ .

On désigne par

Γ~

l'application qui à (

u, v

) associe la matrice

Γ_k(u, v) = Γ~(u, v)

, où

k

est l'entier exhibé à la question 6.

Partie 5

On suppose dans cette partie que

(b_1, \dots, b_d)

sont des vecteurs de

Z^n

linéairement indépendants. On leur associe la famille

(b_1^*, \dots, b_d^*)

définie dans l'Exercice 3 (ce sont alors des vecteurs de

Q^n

). Pour

i \in {2, \dots, d}

, on note

ω_i

la projection orthogonale

surVect(b_i^*, \dots, b_d^*)

. Enfin, on pose

L(b_1, …, b_d) = {∑_(i = 1)^d x_i b_i, (x_1, …, x_d) ∈ Z^d}.

1.Montrer que $inf_(x ∈ L(b_1, …, b_d)∖{0})‖x‖_2 = min_(x ∈ L(b_1, …, b_d)∖{0})‖x‖_2$ .
2.Montrer que $min_(x ∈ L(b_1, …, b_d)∖{0})‖x‖_2 ≥ min_(i ∈ {1, …, d})‖b_i^∗‖_2$ .
3.Soit $k \in {2, \dots, d - 1}$ . Étant donnés $(b_1, \dots, b_d)d$ vecteurs de $Z^n$ , on pose
$T_k(b_1, \dots, b_d) = (b_1, \dots, b_(k - 1), b_k^', b_(k + 1)^', b_(k + 2), \dots, b_d),$
où
$M(b_k^', b_(k + 1)^') = M(b_k, b_(k + 1))Γ~(ω_k(b_k), ω_k(b_(k + 1))).$
Montrer que $L(T_k(b_1, \dots, b_d)) = L(b_1, \dots, b_d)$ .

(u_1, \dots, u_d)

est une famille de vecteurs linéairement indépendants de

R^n

(u_1^*, \dots, u_d^*)

la famille orthogonale associée définie dans l'Exercice 3, on introduit le vecteur

V(u_1, \dots, u_d) \in R^d

dont les coordonnées sont données par

(log‖u_i^∗‖_2 − 1/d∑_(k = 1)^d log‖u_k^∗‖_2), i ∈ {1, …, d}.

On définit les vecteurs

C_1, \dots, C_(d - 1)

R^d

suivants :

C_k

est le vecteur dont les coordonnées sont

(C_k)_i = {0, si i ∉ {k, k + 1},; 1, si i = k,; − 1, si i = k + 1.

On pose

γ = log(2)/2

. Enfin, on introduit les vecteurs définis par les relations

g_1 = γC_1, g_(k + 1) = M_(k + 1)g_k + γC_(k + 1) pour k ∈ {1, …, d − 2}, G = g_(d − 1),

où les matrices

M_k

sont définies par (2) dans la Partie 1. On va aussi utiliser la matrice

A = M_(d - 1)\dotsM_1

.
On définit un ordre partiel sur

R^d

: avec

u = (u_1, \dots, u_d)

v = (v_1, \dots, v_d)

dans

R^d

, on a

u⪯v

si et seulement si

u_i \leq v_i

pour tout

i \in {1, \dots, d}

4.Soit $M \in M_d(R)$ une matrice dont tous les coefficients sont positifs ou nuls. Montrer que pour tous $u, v$ dans $R^d$ tels que $u⪯v$ , on a $Mu⪯Mv$ .

On définit la matrice

P \in M_d(R)

dont les coefficients sont

P_(ij) = 1 si i ≥ j, P_(ij) = 0 sinon, pour i, j ∈ {1, …, d}.

On admet que les résultats de la Partie 4 se réécrivent sous la forme

PV(T_k(b_1, \dots, b_d))⪯P(M_k V(b_1, \dots, b_d) + γC_k),

pour tout

k \in {1, \dots, d - 1}

et pour toute famille

(b_1, \dots, b_d)

de vecteurs linéairement indépendants de

Z^n

5.En déduire qu'en définissant $T(b_1, \dots, b_d) = T_(d - 1)(T_(d - 2)(\dots(T_1(b_1, \dots, b_d))))$ , on a
$PV(T(b_1, \dots, b_d))⪯P(AV(b_1, \dots, b_d) + G).$
Indication : on pourra remarquer que $P$ est inversible et $PAP^(- 1)$ est une matrice à coefficients positifs ou nuls.
6.On pose $Z = γ(d - 1; d - 3; ⋮; 3 - d; 1 - d) \in R^d$ (la $è k^(ème)$ coordonnée est donc $d - (2k - 1)$ ). Montrer que $M_k Z = Z - γC_k$ . En déduire que $Z = AZ + G$ et que $Z \in H$ , l'hyperplan défini en Partie 1.
7.(a) On considère la suite de vecteurs définie par
$X_0 = V(b_1, \dots, b_d), X_(ℓ + 1) = AX_ℓ + G.$
En exploitant les résultats de la Partie 1, analyser le comportement de $X_ℓ$ quand $ℓ \to \infty$ .

(b)Établir que, pour tout $ℓ \in N$ , on a $PV(T^ℓ(b_1, \dots, b_d))⪯PX_ℓ$ .
(c)Soit $ε > 0$ fixé. Montrer qu'il existe un entier $N_0(ε)$ tel que si $N \geq N_0(ε)$ et $(c_1, \dots, c_d) = T^N(b_1, \dots, b_d)$ alors on a
$‖c_1‖_2 \leq 2^((d - 1)/2)exp(ε)(\prod_(i = 1)^d‖b_i^*‖_2)^(1/d) \leq 2^(d - 1)exp(dε)‖c_d^*‖_2$

On note

c_i^((0)) = c_i

pour

i \in {1, \dots, d}

. En reproduisant la même manipulation que précédemment sur

(c_1, \dots, c_(d - 1))

, on obtient

(c_1^((1)), \dots, c_(d - 1)^((1)))

; puis de nouveau sur

(c_1^((1)), \dots, c_(d - 2)^((1)))

on obtient

(c_1^((2)), \dots, c_(d - 2)^((2)))

, etc. jusqu'à obtenir

c_1^((d - 1))

. On pose

β_i = c_i^((d - i))

pour

i \in {1, \dots, d}

.
8. Montrer que

L(β_1, \dots, β_d) = L(b_1, \dots, b_d)

, et que

min_(i ∈ {1, …, d})‖c_1^((i))‖_2 ≤ 2^(d − 1)exp(dε)min_(x ∈ L(b_1, …, b_d)∖{0})‖x‖_2.

Les techniques de cette partie permettent donc de trouver un élément « presque minimal » de

L_p(h)

au sens de la norme euclidienne. En les combinant avec les techniques de la Partie 2, on peut construire un algorithme de factorisation de polynômes unitaires de

Z[t]

INFORMATION AUX CANDIDATS

Vous trouverez ci-après les codes nécessaires vous permettant de compléter les rubriques figurant en en-tête de votre copie.

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Questions fréquentes

4 questions

Sur quels chapitres porte la première épreuve écrite de l'agrégation externe de maths 2020 ?

Le sujet porte sur la réduction des endomorphismes, les polynômes, l'orthogonalisation de Gram-Schmidt et les corps finis, mobilisés pour construire un algorithme de factorisation des polynômes à coefficients rationnels.

Cette épreuve de maths générales de l'agrégation externe 2020 est-elle faisable en entier ?

Non, le rapport indique que même les meilleures copies n'ont traité en général que les exercices et les deux premières parties, et qu'aucun candidat n'est réellement rentré dans la partie V.

Quelles erreurs le jury a-t-il le plus relevées sur cette épreuve d'agrégation externe de maths 2020 ?

Un changement de base mal compris, une équivalence des normes utilisée à tort comme un énoncé quantitatif, et des raisonnements par récurrence menés de façon imprécise, sans hypothèse ni hérédité clairement posées.

Faut-il bien réussir les exercices préliminaires de cette épreuve d'agrégation externe de maths 2020 ?

Oui, le rapport souligne que le soin apporté aux exercices et aux premières questions a réellement fait la différence entre candidats admis et les autres, certains ayant fait le plein de points sur cette seule base grâce à une rédaction irréprochable.

Pas de description pour le moment

Commentaires• Agrégation mathématiques externe 2020, épreuve 1

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

Ce qu'a observé le jury

Les erreurs les plus sanctionnées

Ce qui a été bien réussi

Conseils du jury

Description

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

AGREGATION CONCOURS EXTERNE

Notations et rappels.

Exercice 1

Exercice 2

Exercice 3

Exercice 4

Préambule au problème

Partie 1

Partie 2

Partie 3

Partie 4

Partie 5

INFORMATION AUX CANDIDATS

Questions fréquentes

Sur quels chapitres porte la première épreuve écrite de l'agrégation externe de maths 2020 ?

Cette épreuve de maths générales de l'agrégation externe 2020 est-elle faisable en entier ?

Quelles erreurs le jury a-t-il le plus relevées sur cette épreuve d'agrégation externe de maths 2020 ?

Faut-il bien réussir les exercices préliminaires de cette épreuve d'agrégation externe de maths 2020 ?

Commentaires• Agrégation mathématiques externe 2020, épreuve 1

Commentaires• Agrégation mathématiques externe 2020, épreuve 1

AGREGATION
CONCOURS EXTERNE