J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique Fondamentale (Maths Info) MP PC 2006

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2006
Filière
MP/PC
Matière
Maths Info
X-ENS MP/PCX-ENS 2006MP/PC Maths InfoMaths Info 2006
2025_08_29_e1d9fafda88dd43b6c2dg

Filière MP (groupe I)

Épreuve commune aux ENS de Paris, Lyon et Cachan
Filière PC (groupe I)

Épreuve commune aux ENS de Paris et Lyon

MATHÉMATIQUES - INFORMATIQUE

Durée : 4 heures
L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Préambule

La simplification automatique d'intégrales est une fonctionnalité appréciée des utilisateurs de logiciels de calcul formel. Par exemple, pour intégrer les fractions rationnelles, les "recettes" bien connues (décomposition en éléments simples, changement de variable trigonométrique) se transforment aisément en des algorithmes qui sont implantés dans tous les logiciels du marché. La plupart des logiciels vont bien plus loin et même si l'on ne peut pas espérer disposer d'un algorithme qui simplifie toutes les intégrales, de nombreuses familles d'intégrales peuvent actuellement être traitées.
Dans ce problème on s'intéresse à la famille des intégrales dites hyperelliptiques, c'est-àdire celles qui sont de la forme , où et sont des polynômes. Certaines de ces intégrales peuvent se réécrire sous la forme , où et sont des polynômes. Dans ce cas, on parle d'intégrale pseudo-hyperelliptique.
Le but du problème est de comprendre une version simplifiée d'un algorithme qui permet de calculer et lorsqu'une telle forme existe. L'algorithme repose sur l'utilisation de fractions continues de polynômes. L'étude des propriétés mathématiques et algorithmiques de celles-ci constitue une part importante du problème.
Les parties 1 et 2 sont complètement indépendantes. La partie 4 s'appuie sur la partie 3 qui utilise les notions introduites dans les deux premières parties.

1 Séries de Laurent formelles

Soit un corps commutatif que l'on suppose de caractéristique différente de 2 .
Une série de Laurent formelle sur est une suite d'éléments de indexée par , telle qu'il existe un entier (positif ou négatif) vérifiant : si , alors . Si la suite n'est pas identiquement nulle, quitte à changer , on peut supposer que est non nul, ce qu'on fera toujours par la suite. L'entier est alors appelé la valuation de la série formelle. Par convention, la série nulle a pour valuation .
Une telle série de Laurent formelle est notée , où est une indéterminée. On insiste sur le fait que ceci n'est qu'une notation : même si les sont des réels ou des complexes, on ignore totalement les questions de rayon de convergence. Si est une série de Laurent formelle, on note val(a(z)) sa valuation.
Soient et deux séries de Laurent formelles. On définit pour tout dans et .

Question 1.1

  1. Montrer que est une série de Laurent formelle et que , , avec égalité si . On dit alors que est la somme de et et on note .
  2. Montrer que, pour tout est en fait défini par une somme finie. Quel est le nombre maximal de termes non nuls dans cette somme? Montrer que est une série de Laurent formelle et que . On dit alors que est le produit de et et on note .
  3. Montrer que toute série de Laurent formelle non identiquement nulle est produit d'une série de la forme et d'une série de valuation nulle.
Question 1.2 Montrer que les séries de Laurent formelles munies de cette addition et ce produit forment un anneau commutatif (ayant un élément unité). On notera 0 le neutre pour l'addition, 1 le neutre pour la multiplication, et par extension on notera l'élément répété fois.
Question 1.3 Montrer qu'une série de Laurent formelle non nulle est inversible et que . L'ensemble des séries de Laurent formelles est donc un corps. On notera classiquement l'inverse de .
Question 1.4 Écrire dans un pseudo-langage de haut niveau une fonction qui prend en entrée les premiers coefficients d'une série formelle , de valuation nulle, et retourne les premiers coefficients de l'inverse de . On supposera que les opérations élémentaires (additions, soustractions, multiplications, inverses) dans le corps font partie intégrante du langage.
Soit une série de Laurent formelle non nulle, de valuation paire, et dont le premier terme non nul vaut 1 . Ainsi s'écrit , où est dans . On définit les suites et de séries de Laurent formelles par , puis
(La division par 2 est possible car est de caractéristique différente de 2 .)
Question 1.5 Montrer que, pour tout et sont bien définies, que la valuation de est 0 et que celle de vaut au moins .
Question 1.6 Montrer que, pour tout entier , il existe un indice à partir duquel tous les ont les mêmes premiers termes. En déduire qu'il existe une série de Laurent formelle telle que . On note alors une telle série dont le premier terme non nul vaut 1 .
Dans la situation où une suite de séries de Laurent formelles est telle que tend vers l'infini, on dira que la suite tend vers 0 . Plus généralement, s'il existe une série de Laurent formelle telle que val tend vers l'infini, on dira que la suite tend vers . On a ainsi montré dans les questions précédentes que la suite tend vers 0 et que la suite tend vers .

2 Fractions continues

Une fraction continue sur un corps commutatif est une suite d'éléments tels que si . La fraction continue étant donnée, on s'intéresse à l'expression
Plus précisément, on note la valeur de l'expression
que l'on appelle convergent d'ordre , ou -ème convergent de . De manière plus formelle, pour on a , puis on définit un convergent d'ordre à partir d'un convergent d'ordre par
Question 2.1 Montrer que pour toute fraction continue , pour tout , le -ème convergent peut s'écrire où les suites et sont définies par , et pour tout ,
Question 2.2 Écrire un programme (dans un pseudo-langage de haut niveau) qui, étant donnés les premiers termes d'une fraction continue , calcule la valeur de son -ème convergent en effectuant une unique inversion. On supposera que les opérations élémentaires dans le corps font partie intégrante du langage. Évaluer le nombre d'additions et de multiplications dans effectuées lors d'une exécution du programme.
Question 2.3 Soit une fraction continue et soit son -ème convergent. Montrer que pour tout , où la suite est définie comme à la question 2.1.
Question 2.4 Dans cette question (et uniquement dans cette question), on suppose que le corps est le corps des rationnels . On suppose de plus que les sont des entiers strictement positifs. Montrer que la suite des convergents tend vers une limite réelle.

3 Fractions continues de polynômes

Dorénavant, on prend comme corps le corps des fractions rationnelles à coefficients dans le corps .
On s'intéresse aux fractions continues sur d'une forme particulière : on considère uniquement les fractions continues telles que pour tout , le terme est un polynôme et de plus, si , alors ce polynôme est de degré au moins 1 . Une telle fraction continue est appelée fraction continue de polynômes sur . Ses convergents sont donc des fractions rationnelles à coefficients dans .
Dans la suite, afin d'alléger les notations, il nous arrivera de noter simplement un polynôme appartenant à . De même, on notera couramment une série de Laurent formelle .
À tout polynôme appartenant à , on peut associer une série de Laurent formelle notée , définie de la manière suivante : si , alors
L'opérateur est clairement un morphisme injectif d'anneau, et on peut donc l'étendre en un morphisme injectif du corps des fractions rationnelles dans le corps des séries de Laurent formelles comme suit : si et sont deux polynômes avec , alors . Insistons sur le fait que ce dernier quotient est à comprendre comme le produit de la série de Laurent formelle avec l'inverse de la série de Laurent formelle (cela n'a rien à voir avec une fraction rationnelle).
On définit aussi un opérateur qui à toute série de Laurent formelle associe un polynôme : si est de valuation strictement positive, alors , et si est de valuation négative ou nulle, avec , alors . Ainsi pour tout polynôme à coefficients dans , on a .

Question 3.1 Propriétés élémentaires de et .

  1. Si est un polynôme de degré , quelle est la valuation de ?
  2. Si et sont des séries de Laurent formelles, vérifier que . Donner un exemple de séries de Laurent formelles et telles que . Ainsi est un morphisme additif mais pas multiplicatif des séries de Laurent formelles vers les polynômes.
  3. À quelle condition une série de Laurent formelle vérifie-t-elle ?
Question 3.2 Soit une fraction continue de polynômes. Montrer qu'il existe une série de Laurent formelle telle que les images par des convergents de tendent vers au sens défini à la fin de la partie 1 : si est le -ème convergent, alors la valuation de tend vers l'infini lorsque tend vers l'infini. On pourra s'aider de la question 2.3.
Réciproquement, à toute série de Laurent formelle qui n'est pas l'image par d'une fraction rationnelle, on souhaite associer une fraction continue dont les images par des
convergents tendent vers . Pour cela, on introduit les suites suivantes : on pose , puis pour tout ,
Question 3.3 Montrer que la suite est bien définie et que pour tout , le degré de est au moins 1 . La suite est donc une fraction continue de polynômes. Montrer que les images par de ses convergents tendent vers . Pour cela, on pourra démontrer que, pour tout , on a
où les suites et sont définies à partir de la suite comme dans la question 2.1.

Question 3.4 Lemme de meilleure approximation.

Soit une série de Laurent formelle qui n'est pas l'image par d'une fraction rationnelle. On considère sa fraction continue associée et et les suites définies à partir de cette fraction continue comme dans la question 2.1.
  1. Montrer que, pour tout , on a
  1. Soient et deux polynômes et un entier. Montrer qu'il existe deux polynômes et tels que
  1. On suppose que et sont premiers entre eux, que , et que n'est pas proportionnel à (c'est-à-dire qu'il n'existe pas de tel que ). Montrer que et sont non nuls puis que .
  2. En déduire le lemme de meilleure approximation : si et sont deux polynômes premiers entre eux tels que , alors est un convergent de la fraction continue associée à .
Soit un polynôme unitaire, de degré pair , qui n'est pas le carré d'un polynôme. Alors son image par est une série de Laurent formelle de valuation paire dont le premier terme non nul vaut 1, et d'après la question 1.6, il existe une série formelle dont le carré est . Par abus de notation, on omet le , et l'on note simplement cette série formelle. On vérifie alors sans difficultés que n'est pas l'image par d'une fraction rationnelle.
Question 3.5 Écrire une fonction qui prend en entrée un polynôme comme ci-dessus et qui retourne le polynôme . On pourra s'inspirer des suites et introduites en fin de partie 1. On suppose donnée une bibliothèque pour les opérations élémentaires sur les polynômes de (mais pas sur les séries formelles qui sont des objets potentiellement de taille infinie). Quel est le degré maximal des polynômes manipulés?
Afin d'étudier la fraction continue associée à , on introduit les suites définies de la manière suivante. Soient , puis pour tout est le quotient dans la division euclidienne de par , et
Question 3.6 Le but de cette question est de démontrer que la suite donne la fraction continue de polynômes associée à .
  1. Montrer que et sont des polynômes et que pour tout .
  2. Soit une série de Laurent formelle et un polynôme non nul. Montrer que est égal au quotient dans la division euclidienne de par . Pour cela, on pourra commencer par écrire comme la somme de et d'une série de valuation strictement positive. En déduire que
  1. Soit la suite correspondant à la fraction continue associée à , définie comme avant la question 3.3. Pour tout , montrer que et , par récurrence sur .

4 Application aux intégrales pseudo-hyperelliptiques

Dans cette partie, le corps de base est le corps des réels. On considère les intégrales de la forme
où est un polynôme non nul et un polynôme unitaire de degré pair, qui n'est pas un carré. On suppose (ici et partout dans cette section) que est strictement positif sur l'intervalle fermé d'intégration, si bien que la fonction à intégrer est continue, et même .
Si le degré de est 2 , un changement de variables permet toujours de se ramener à l'intégration d'une fraction rationnelle, si bien que l'intégrale est facilement exprimable à l'aide des fonctions usuelles.
Si le degré de est au moins 4, ce que l'on supposera désormais, il n'y a en général pas moyen d'exprimer une telle intégrale à l'aide des fonctions usuelles. Cependant, il existe des cas particuliers. Lorsque cette intégrale est égale à une expression de la forme ) où et sont des polynômes, on dit qu'on a affaire à une intégrale pseudohyperelliptique (ou intégrale pseudo-elliptique, si ).
La formule suivante
montre que de telles intégrales existent (il n'est pas demandé de refaire les calculs pour vérifier cette égalité).
Le but de cette partie est de montrer que, s'ils existent, les polynômes et peuvent être calculés à l'aide de la fraction continue de la série de Laurent formelle (qui n'a a priori rien à voir avec la fonction qui intervient dans l'intégrale).
Question 4.1 Montrer que si l'on a une intégrale pseudo-hyperelliptique
alors il existe une constante non nulle telle que . (On pourra utiliser le fait que la fonction n'est pas égale à une fraction rationnelle.)
Question 4.2 En utilisant le lemme de meilleure approximation (question 3.4), montrer que est, au signe près, un convergent de la fraction continue de la série de Laurent formelle .
Question 4.3 Montrer que pour tout , on a , où les polynômes et sont définis à partir de la fraction continue de comme dans les questions 2.1 et 3.6. Pour cela on pourra écrire de deux manières différentes à l'aide des questions 3.3 et 3.6.3. En déduire qu'il existe un indice tel que le polynôme est constant, puis que la fraction continue associée à est quasi-périodique à partir d'un certain rang, c'est-à-dire périodique à partir d'un certain rang, modulo la multiplication des polynômes par des scalaires.
Question 4.4 Donner les principes d'un algorithme qui prend deux polynômes et en entrée, qui retourne et si l'intégrale est pseudo-hyperelliptique et vaut , et qui ne termine pas s'il n'existe pas de solution. On suppose donnée une bibliothèque qui permet de calculer sur les polynômes réels (et on ignore les problèmes d'arrondis).
ENS Informatique Fondamentale (Maths Info) MP PC 2006 - Version Web LaTeX | WikiPrépa | WikiPrépa