Institut de Mathématiques de Luminy

THÈSES 1998-1999


Dates soutenances Noms et titres Équipes
22 octobre 1998 Antoine EDOUARD
Formules explicites et nombre de points des courbes sur les corps finis :
le théorème d'Oesterlé
(Explicit formula and the number of points of curves over finite fields :
Oesterlé's theorem)
ATI
2 novembre 1998 Stéphane BALLET
Étude de la complexité bilinéaire de la multiplication dans les corps finis
par interpolation sur des courbes algébriques
(On the bilinear complexity of multiplication in finite fields
by interpolation on algebraic curves)
ATI
22 janvier 1999 Patrick BAILLOT
Approches dynamiques en sémantique de la logique linéaire :
jeux et géométrie de l'interaction
LDP
3 février 1999 Pierre TISSEUR
Aspects ergodiques des automates cellulaires
(Some results on the ergodic theory of cellular automata)
DAC
13 juin 1999 Jérôme CHABERT
La conjoncture de Baum-Connes pour le groupe SL3 (Qp)
GNC


Antoine EDOUARD

(équipe ATI)

Titre : Formules explicites et nombre de points des courbes sur les corps finis : le théorème d'Oesterlé.

Directeur de thèse : Gilles LACHAUD

Jury : Jean-Pierre Cherdieu (MC Univ. Antilles-Guyane), Gilles Lachaud (DR CNRS IML), Ousseynou Nakoulima (Prof. Univ. Antilles-Guyane), Joseph Oesterlé (Prof. Univ. Paris VI), Robert Rolland (MC Univ. Aix-Marseille II), Mikhaïl Tsfasman (DR IPPI Moscou), Serguei Vladuts (Prof. Univ. Aix-Marseille II).

Date : 22 octobre 1998

Université d'inscription : Aix-Marseille II

Résumé : En analyse indéterminée, les équations de congruence définies par les courbes algébriques sur un corps fini, étudiées depuis Diophante d'Alexandrie, sont maintenant utilisées systématiquement dans le traitement de l'information. A. Weil a donné une formule fondamentale pour le nombre de points de ces courbes, qui permet de majorer ce nombre en fonction de leur genre, un entier mesurant sa complexité. On peut préciser les résultats de Weil afin d'obtenir des inégalités plus fines, comme l'ont montré S. Vladuts, V. Drinfiel'd et J.-P. Serre. On obtient une famille infinie d'identités, les formules explicites, qui sont analogues à celles introduites en théorie des nombres. On peut alors se poser la question de la recherche des inégalités optimales. L'objet de cette thèse est de donner des démonstrations complètes de la solution explicite de cette question. Cette solution a été donnée par J. Oesterlé, mais il n'a pas publié les démonstrations de ses résultats. On traduit d'abord cette question en un d'optimisation en analyse fonctionnelle, en utilisant des espaces de mesures et de séries de Fourier sur le cercle unité. La recherche de la borne optimale revient alors à un problème de programmation linéaire. Ensuite, pour la recherche des solutions admissibles, on est conduit à introduire de nouvelles approximations de l'unité, les noyaux de Féjer déployés. Il faut enfin vérifier que les inégalités obtenues à partir de ces noyaux sont bien optimales, ce qui est le cas (sauf quelquefois en caractéristique 2). Pour terminer, on fournit des tableaux de bornes optimales pour de petites valeurs du genre de la courbe et du nombre d'éléments du corps.

Mots-clés : corps finis, théorème de Weil, formules explicites, optimisation linéaire et convexe, courbes algébriques, borne de Weil, théorème d'Oesterlé, noyau de Féjer déployé.

Title : Explicit formula and the number of points of curves over finite fields : Oesterlé's theorem.

Abstract : In indeterminate analysis, congruence equations defined from algebraic curves over finite fields have been studied since Diophante of Alexandria. Now, these equations are systematically used for information processing. A. Weil has given a fundamental formula for the number of points of such an algebraic curve, which provides an upper bound of this number with respect to its genus, an integer reflecting the complexity of the curve. It is possible to improve Weil's result in order to obtain lesser upper-bounds, as shown by S. Vladut, V. Drinfield et J.P. Serre. In fact we have an infinite family of identities called explicit formulas, which are similar to those introduced in number theory. The question is to find the optimal associated inequalities. The aim of this thesis is to give full proofs concerning the explicit solution of this problem. This solution was given by J. Oesterlé, but he never published proofs of his results. We first reformulate the problem within the framwork of optimisation in functional analysis, by using spaces of measures and Fourier series on the unit circle. Therefore looking for optimal bound is equivalent to a linear programming problem. Secondly, we introduce new approximations of unity, the split Féjer kernels, in order to get feasible solutions. Then it is necessary to check whether inequalities obtained from these kernels are optimal. This is the case except sometimes in characteristic 2. Finally, optimal bound tables are provided for small values of the curve genus and the field cardinality.

Keywords : Finite fields, Weil's theorem, explicit formulas, convex and linear optimisation, algebraic curves, Weil's bound, Oesterlé's theorem, split Féjer kernels.



Stéphane BALLET

(équipe ATI)

Titre : Étude de la complexité bilinéaire de la multiplication dans les corps finis par interpolation sur des courbes algébriques.

Directeur de thèse : Robert ROLLAND

Jury : Jean-Marc Couveignes, Gilles Lachaud, Ruud Pellikaan, François Rodier, Robert Rolland, Mikhaïl Tsfasman, Serguei Vladuts, Jacques Wolfmann.

Date : 2 novembre 1998

Université d'inscription : Aix-Marseille II

Résumé : Soit n, le corps fini à qn éléments. Il est connu qu'asymptotiquement, la complexité bilinéaire de la multiplication est linéaire par rapport au degré n de l'extension. Ce résultat découle de l'existence de méthodes interpolatoires sur des courbes algébriques définies sur 2 ayant de bonnes propriétés. Se pose alors le problème de la détermination de la complexité pour des extensions d'un degré n fixé. Après avoir caractérisé certaines propriétés permettant l'obtention d'algorithmes d'interpolation, nous prouvons l'existence de courbes les vérifiant. Plus précisément, nous montrons que ces bonnes courbes existent pour tout n lorsque q 9 est un carré et pour des extensions assez grandes lorsque q 9 est non premier. Nous en déduisons des bornes supérieures de la complexité dans toute extension de q est quelconque. Nous montrons ainsi que la complexité bilinéaire de la multiplication est linéaire uniformément en q par rapport au degré n de l'extension. D'autre part, en précisant la notion de supercode, nous caractérisons certaines conditions nécessaires d'optimalité pour certaines classes d'algorithmes d'interpolation.

Mots-clés : complexité bilinéaire, corps finis, corps de fonctions algébriques.

Title : On the bilinear complexity of multiplication in finite fields by interpolation on algebraic curves.

Abstract : Let n be the finite field with qn elements. It is known that the asymptotic bilinear complexity of multiplication is linear with respect to the extension degree n. This result follows from the existence of interpolation methods on algebraic curves having good properties. But then apppears the problem of the determination of complexity for any extension with a fixed degree n. In this purpose, we first caracterize certain properties which enable us to obtain interpolation algorithms. Later, we prove the existence of curves satisfying those properties. More precisely, we show those good curves exist for any integer n provided q 9 is a square and for some large enough extensions provided q 9 is not a prime number. We deduce new upper bounds in any extension of with q an arbitrary prime power. So we prove the bilinear complexity of multiplication in the finite fields n is linear uniformly in q with respect to the degree n. Moreover, by refining the supercode notion, we caracterize certain optimality necessary conditions for some classes of interpolation algorithms.

Keywords : bilinear complexity, finite fields, algebraic function fields.



Patrick BAILLOT

(équipe LDP)

Titre : Approches dynamiques en sémantique de la logique linéaire : jeux et géométrie de l'interaction.

Directeur de thèse : Jean-Yves GIRARD

Jury : Pierre-Louis Curien, Vincent Danos, Jean-Yves Girard, Jean-Louis Krivine, Laurent Regnier.

Date : 22 janvier 1999

Université d'inscription : Aix-Marseille II

Résumé : .

Mots-clés : .

Title : .

Abstract : .

Keywords : .



Pierre TISSEUR

(équipe DAC)

Titre : Aspects ergodiques des automates cellulaires.

Directeur de thèse : François BLANCHARD

Jury : Blanchard François, Durand Bruno, Liardet Pierre, Maass Alejandro, Mauduit Christian.

Date : 3 février 1999

Université d'inscription : Aix-Marseille II

Résumé : Dans cette thèse, nous étudions deux aspects ergodiques de la dynamique des automates cellulaires unidimensionnels et bilatères.
Dans la première partie nous chercherons à affiner la notion d'exposant de Lyapounov pour ces automates. Une première proposition de définition de ces exposants a été réalisée pae M. Shereshevsky et parut dans J. Nonlinear Sci. en 1992. Ces exposants (droits et gauches) notés +µ + -µ sont définis relativement à une mesure ergodique pour l'automate cellulaire. Nous montrons qu'en prenant les mêmes définitions pour ces exposants mais en posant comme condition que la mesure soit invariante par l'automate et que cette mesure soit ergodique pour le shift noté il est possible de prouver l'existence de ces exposants et de montrer une inégalité entre d'une part l'entropie métrique de l'automate cellulaire notée hµ(F) et d'autre part le produit de l'entropie métrique du shift par la somme des exposants de Lyapounov droit et gauche :

hµ(F) h µ()(+µ + -µ).

Il est à remarquer que l'on dispose de beaucoup plus d'exemples de couples (automates cellulaires, mesures) pour lesquels la mesure est invariante par l'automate et ergodique pour le shift que de mesure ergodique pour l'automate cellulaire et invariante par le shif. Ensuite, tout en conservant les mêmes conditions sur la mesure, nous introduisons des exposants de Lyapounov (droits et gauches) notés I+µ + I-µ et dénommés moyens car ils se définissent à partir de moyennes ergodiques et non pas comme des valeurs maximales sur l'orbite du shift des points. On montre que ces nouveaux exposants sont plus petits ou égaux aux premiers exposants que l'on peut qualifier de maximaux et que le produit de la somme de ces deux exposants par l'entropie métrique du shift est encore un majorant de l'entropie métrique de l'automate cellulaire :

hµ(F) h µ()(I+µ + I-µ).

Une propriété remarquable des exposants moyens est de s'annuler lorsqu'il existe des points d'équicontinuité dans le support de la mesure. Les exposants de Lyapounov maximaux ne partagent pas cette propriété comme nous le montrons dans deux exemples. Puis, remarquant qu'il est toujours possible de définir les exposants de Lyapounov maximaux pour la mesure uniforme notée µu nous montrons que le produit de ces exposants par l'entropie du shift sur Az est un majorant de l'entropie topologique de l'automate cellulaire :

hµ(F) log # A(+µu + -µu).

La seconde partie est une étude des liens existant entre la notion d'équicontinuité et l'existence de mesures invariantes par l'automate cellulaire. Le résultat principal est le suivant : si une mesure est ergodique pour le shift et qu'un automate cellulaire possède des points d'équicontinuité dans le support topologique de cette mesure alors la suite des mesures images par l'automate cellulaire de cette mesure est convergente. Nous donnons une expression asymptotique de cette mesure limite. Ensuite nous terminons par une étude du support topologique de la mesure limite.

Mots-clés : automates cellulaires, dynamique symbolique, théorie ergodique, exposants de Lyapounov.

Title : Some results on the ergodic theory of cellular automata.

Abstract : .

Keywords : cellular automata, symbolic dynamics, ergodic theory, Lyapounov exponents.



Jérôme CHABERT

(équipe GNC)

Titre : La conjoncture de Baum-Connes pour le groupe SL3 (Qp).

Directeur de thèse : Guennadi KASPAROV et Richard ZEKRI

Jury : Joachim Cuntz, Guennadi Kasparov, Eberhard Kirchberg, Georges Skandalis, Richard Zekri.

Date : 13 juin 1999

Université d'inscription : Aix-Marseille II

Résumé : .

Mots-clés : .

Title : .

Abstract : .

Keywords : .




Last update : february 15, 2002, EL.