Institut de Mathématiques de Luminy

THÈSES 2012-2013


Dates soutenances Noms et titres thèmes Photos
14 décembre
2012
Hamish IVEY-LAW
Algorithmic aspects of hyperelliptic curves
and their Jacobians
ATI Hamish Ivey-Law
12 décembre
2012
Julia PIELTANT
Tours de corps de fonctions algébriques et
rang de tenseur de la multiplication
dans les corps finis
ATI  
13 novembre
2012
Thomas SEILLER
Logique dans le facteur hyperfini :
géométrie de l'interaction et complexité
LDP Thomas Seiller



Hamish IVEY-LAW
(thème ATI)

Titre : Algorithmic aspects of hyperelliptic curves and their Jacobians

Directeurs de thèse : David Kohel, Claus Fieker

Rapporteurs : Kamal Khuri-Makdisi, Michael Stoll.

Jury : Claus Fieker, Florian Hess, David Kohel, David Lubicz, Christophe Ritzenthaler, Michael Stoll.

Date : 14 décembre 2012

Universités d'inscription : Aix-Marseille II, Université de Sydney (Australie)

Résumé : Ce travail se divise en deux parties.
Dans la première partie, nous généralisons le travail de Khuri-Makdisi qui décrit des algorithmes pour l'arithmétique des diviseurs sur une courbe sur un corps. Nous montrons que les analogues naturelles de ses résultats se vérifient pour les diviseurs de Cartier relatifs effectifs sur un schéma projectif, lisse et de dimension relative un sur un schéma affine noetherien quelconque, et que les analogues naturelles de ses algorithmes se vérifient pour une certaine classe d’anneaux de base. Nous présentons un formalisme pour tels anneaux qui sont caractérisés par l'existence d'un certain sous-ensemble des opérations standards de l’algèbre linéaire pour les modules projectifs sur ces anneaux.
Dans la deuxième partie de ce travail, nous considérons un type de problème de Riemann-Roch pour les diviseurs sur certaines surfaces algébriques. Plus précisément, nous analysons les surfaces algébriques qui émanent d'un produit ou d'un produit symétrique d'une courbe hyperelliptique de genre supérieur à un sur un corps (presque) arbitraire. Les résultats principaux sont une décomposition des espaces de sections globales de certains diviseurs sur telles surfaces et des formules explicites qui décrivent les dimensions des espaces de sections de ces diviseurs. Nous nous concluons en présentant un algorithme qui produit une base pour l'espace de sections globales d'un tel diviseur.

Abstract: The contribution of this thesis is divided naturally into two parts.
In Part I we generalise the work of Khuri-Makdisi on algorithms for divisor arithmetic on curves over fields to more general bases. We prove that the natural analogues of the results of Khuri-Makdisi continue to hold for relative effective Cartier divisors on projective schemes which are smooth of relative dimension one over an arbitrary affine Noetherian base scheme and that natural analogues of the algorithms remain valid in this context for a certain class of base rings. We introduce a formalism for such rings, which are characterised by the existence of a certain subset of the usual linear algebra operations for projective modules over these rings.
Part II of this thesis is concerned with a type of Riemann-Roch problem for divisors on certain algebraic surfaces. Specifically we consider algebraic surfaces arising as the square or the symmetric square of a hyperelliptic curve of genus at least two over an (almost) arbitrary field. The main results are a decomposition of the spaces of global sections of certain divisors on such surfaces and explicit formulæ for the dimensions of the spaces of sections of these divisors. We conclude by presenting an algorithm which generates a basis for the space of global sections of such a divisor.

Fichier / File

( 799 Ko )





Julia PIELTANT
(thème ATI)

Titre : Tours de corps de fonctions algébriques et rang de tenseur de la multiplication dans les corps finis

Directeur de thèse : Stéphane Ballet.

Rapporteurs : Reynald Lercier, Ferruh Özbudak.

Jury : Daniel Augot, Stéphane Ballet, Gilles Lachaud, Reynald Lercier, Traian Muntean (invité), Ferruh Özbudak, François Rodier, Robert Rolland, Serge Vladut.

Date : 12 décembre 2012

Université d'inscription : Aix-Marseille II

Résumé : On s'intéresse dans cette thèse à la détermination du rang de tenseur de la multiplication dans $\F_{q^n}$, l'extension de degré n du corps fini $\F_q$ ; ce rang de tenseur correspond en particulier à la complexité bilinéaire de la multiplication dans $\F_{q^n}$ sur $\F_q$.
Dans cette optique, on présente les différentes évolutions de l'algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky et qui a permis d'établir que le rang de tenseur de la multiplication dans $\F_{q^n}$ était linéaire en n. Cet algorithme en fournit désormais les meilleures bornes connues dans le cas d'extensions de degré grand relativement au cardinal du corps de base — le cas des petites extensions étant bien connu.
Afin d'obtenir des bornes uniformes en le degré de l'extension, il est nécessaire, pour chaque n, de déterminer un corps de fonctions algébriques qui convienne pour appliquer l'algorithme pour $\F_{q^n}$, c'est-à-dire qui ait suffisamment de places de petit degré relativement à son genre g et pour lequel on puisse établir l'existence de diviseurs ayant certaines propriétés, notamment des diviseurs non-spéciaux de degré g-1 ou de dimension nulle et de degré aussi près de g-1 que possible ; c'est pourquoi les tours de corps de fonctions sont d'un intérêt considérable. En particulier, on s'intéresse ici à l'étude des tours de Garcia-Stichtenoth d'extensions d'Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vladut. En dégageant des propriétés de ces tours, notamment par l'utilisation de techniques de descente du corps de définition associées à l'utilisation de développements locaux selon un élément primitif de places de petit degré, on obtient, à partir d'une méthode générale formalisée ici, de nouvelles bornes uniformes, symétriques et asymétriques, pour les extensions finies de $\F_{q^2}$, $\F_q$, $\F_{p^2}$, $\F_p$, et notamment les meilleures bornes actuellement connues pour le rang de tenseur de la multiplication dans $\F_{2^n}$. On déduit alors de certaines d'entre elles de bonnes bornes asymptotiques.

Abstract: In this thesis, we focus on the determination of the tensor rank of multiplication in $\F_{q^n}$, the degree $n$ extension of the finite field $\F_q$, which corresponds to the bilinear complexity of multiplication in $\F_{q^n}$ over $\F_q$. To this end, we describe the various successive improvements to the evaluation-interpolation algorithm introduced in 1987 by D.V. and G.V. Chudnovsky which shows the linearity of the tensor rank of multiplication in $F_{q^n}$ with respect to n. This algorithm gives the best known bounds for large degree extensions relative to the cardinality of the base field (the case when the degree of the extension is small is well known).
In order to obtain uniform bounds, we need to determine, for each n, a suitable algebraic function field for the algorithm on $\F_{q^n}$, namely a function field with sufficiently many places of small degree relative to its genus g and for which we can prove the existence of divisors with some good properties such as non-special divisors of degree g-1 or zero-dimensional divisors with degree as close to g-1 as possible; these conditions lead us to consider towers of algebraic function fields. In particular, we are interested in the study of Garcia-Stichtenoth towers of Artin-Schreier and Kummer extensions which attain the Drinfeld-Vladut bound. By establishing some properties on these towers, and using field definition descent techniques and local expansion of functions at places of relatively small degree, we obtain, from a general method which is described here, new symmetric and asymmetric uniform bounds for finite extensions of $\F_{q^2}$, $\F_q$, $\F_{p^2}$, $\F_p$ ; in particular, we obtain the best actual known bounds for the tensor rank of multiplication in $\F_{2^n}$. We also deduce from this some good asymptotic bounds.

Fichier / File

( 1,06 Mo )





Thomas SEILLER
(thème LDP)

Titre : Logique dans le facteur hyperfini : géométrie de l'interaction et complexité

Directeurs de thèse : Jean-Yves Girard, Laurent Regnier

Rapporteurs : Pierre-Louis Curien, Martin Hyland.

Jury : Pierre-Louis Curien, Jean-Yves Girard, Martin Hyland, Olivier Laurent, Laurent Regnier, Philip Scott.

Date : 13 novembre 2012

Université d'inscription : Aix-Marseille II

Résumé : Cette thèse est une étude de la géométrie de l’interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisissant une fonction qui mesure les cycles, d’obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d’une adjonction numérique, une géométrie de l’interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre afin d’interpréter les exponentielles et le second ordre.
Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l’étude de deux cas particuliers. Le premier s’avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l’orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l’interaction, où l’orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l’interaction, et d’en déduire que les deux adjonctions — qui semblent à première vue si différentes — sont des conséquences d’une même identité géométrique.
Nous étudions ensuite la notion de vérité subjective. Nous commençons par considérer une version légèrement modifiée de la GdI5 avec une notion de vérité dépendant du choix d’une sous-algèbre maximale commutative (masa). Nous montrons qu’il existe une correspondance entre la classification des masas introduite par Dixmier (regulière, semi-régulière, singulière) et les fragments de la logique linéaire que l’on peut interpréter dans cette géométrie de l’interaction. Nous étudions alors la vérité subjective de la GdI5, qui dépends du choix d’une représentation du facteur hyperfini de type II1, à la lumière de ce résultat.
Finalement, nous détaillerons une proposition de Girard pour étudier les classes de complexité et détaillons la caractérisation obtenue par ce dernier de la classe de complexité co-NL, en montrant comment coder un problème complet pour cette classe à l’aide d’opérateurs.

Abstract: This work is a study of the geometry of interaction in the hyperfinite factor introduced by Jean-Yves Girard, and of its relations with ancient constructions.
We start by showing how to obtain purely geometrical adjunctions as an identity between sets of cycles appearing between graphs. It is then possible, by chosing a function that measures those cycles, to obtain a numerical adjunction. We then show how to construct, on the basis of such a numerical adjunction, a geometry of interaction for multiplicative additive linear logic where proofs are interpreted as graphs. We also explain how to define from this construction a denotational semantics for MALL, and a notion of truth. We extend this setting in order to deal with exponential connectives and show a full soundness result for a variant of elementary linear logic (ELL).
Since the constructions on graphs we define are parametrized by a function that measures cycles, we then focus our study to two particular cases. The first case turns out to be a combinatorial version of GoI5, and we thus obtain a geometrical caracterisation of its orthogonality which is based on Fuglede-Kadison determinant. The second particular case we study will give us a refined version of older constructions of geometry of interaction, where orthogonality is based on nilpotency. This allows us to show how these two versions of GoI, which seem quite different, are related and understand that the respective adjunctions are both consequences of a unique geometrical property.
In the last part, we study the notion of subjective truth. We first define a slightly modified version of GoI5 where the notion of subjective truth is dependent on the choice a maximal abelian subalgebra (masa). We can show in this setting that there is a correspondance between Dixmier’s classification of masas (regular, semi-regular, singular) and the fragments of linear logic one can interpret. We then explain how this notion of truth related to the notion of truth of GoI5, which depends on a choice of representation for the hyperfinite factor of type II∞.
Finally, we study a proposition made by Girard to study complexity classes through the geometry of interaction in the hyperfinite factor. In particular, we detail Girard’s caracterisation of the co-NL complexity class by showing how to encode by operators a problem which is complete for this complexity class.

Fichier / File

( 1,33 Mo )

Site web (webpage)



Last update : june 7, 2013, EL.