Séminaire de géométrie et algèbre effectives

  1. Exposés à venir
  2. Exposés passés
  3. Archives du séminaires

Le séminaire est organisé par Xavier Caruso et Elisa Lorenzo García.

Les exposés ont lieu le vendredi à 10h30 dans la salle 016 du bâtiment 22-23.

Exposés à venir

Exposés passés

  • Vendredi 15 septembre 2017
    Victor Cauchois (IRMAR)
  • Vendredi 6 octobre 2017
    Journée de rentrée de l'équipe
    10h45 – 11h30, Codes correcteurs d'erreur (par P. Loidreau)
    13h15 – 14h00, Géométrie algébrique réelle (par M.-F. Roy)
    14h15 – 15h00, Courbes algébriques (par C. Ritzenthaler)
    15h15 – 16h00, Précision p-adique (par X. Caruso)
  • Vendredi 13 octobre 2017
    Johannes Hoffmann (RWTH Aachen University)
    A Constructive Approach to Arithmetics in Ore Localizations
    Classical results of Ore from the 1930's tell, that for a domain R, a localization with respect to a multiplicatively closed set S exists if S satisfies left Ore property. We investigate the arithmetics of the localized ring S^{-1}R from both theoretical and practical points of view. We show that effective computations in S^{-1}R require a specialization of the type of S and distill three most frequently occuring types of Ore sets. We provide an implementation of arithmetics over ubiquitous G-algebras in Singular:Plural and discuss algorithmic and theoretic questions in this context.
  • Vendredi 20 octobre 2017
    Peter Stevenhagen (Université de Leiden)
    Ellpitic primitive Roots
  • Vendredi 27 octobre 2017
    Vincent Neiger (Université de Limoges)
    Efficient algorithms for computing univariate relations
    In this talk, we will present recent results about the fast computation of univariate relations, including in particular rational interpolants and Hermite-Padé approximants. Such relations are a central tool in computer algebra, arising in situations such as the guessing of linear differential equations, the list-decoding of Reed-Solomon codes, or the computation of normal forms of polynomial matrices. After giving an overview of the problem and of existing fast algorithms, the emphasis will be placed on the main ideas behind the recent algorithmic improvements.
    This talk involves joint work with Claude-Pierre Jeannerod, Johan Rosenkilde, Eric Schost, Grigory Solomatov, Gilles Villard, and Vu Thi Xuan.
  • Vendredi 10 novembre 2017
    Everett Howe (Center for Communications Research)
    Constructions of curves of medium genus over F_q with many points
  • Vendredi 17 novembre 2017
    André Leroy (Université d'Artois)
    Sur les factorisations dans les extensions de Ore
    On commencera par définir une notion d'évaluation pour les polynômes de Ore à coefficients dans un anneau. On introduira ensuite les transformations pseudo linéaires et on définira les notions de polynômes de Wedderburn et de polynômes complètement réductibles. Après avoir donné plusieurs caractérisations de ces polynômes on s'intéressera à leurs factorisations en particulier dans le cas ou l'anneau de base est un anneau à division. On présentera aussi le comptage des racines généralisant et précisant le résultat de Gordon-Motzkin. On abordera la question de factorisation dans des anneaux généraux et on introduira la notion d'anneaux de polynômes de Ore libre qui semble être le bon moyen d'aborder l'évaluation à plusieurs variables gauches.
  • Vendredi 24 novembre 2017
    Beth Malmskog (Colorado College)
    Locally Recoverable Codes with Many Recovery Sets from Fiber Products of Curves
    An error-correcting code is said to be locally recoverable if any symbol in a code word can be recovered by accessing a subset of the other symbols. This subset is known as the helper or recovery set for the given symbol. Locally recoverable codes (LRCs) have benefits for distributed storage applications. It may be desirable to have many disjoint recovery sets for each symbol, in case of multiple server failures or to provide many options for recovery. Barg, Tamo, and Vladut recently constructed LRCs with one and two disjoint recovery sets from algebraic curves. This talk presents a generalization of this construction to three or more recovery sets using iterated fiber products of curves. The construction is applied to give including the Suzuki and generalized Giulietti-Korchmaros curves. Codes with arbitrarily many recovery sets are constructed, employing maximal curves from fiber products devised by Van der Geer and Van der Vlugt. This is joint work with Kathryn Haymaker and Gretchen Matthews.
  • Vendredi 1er décembre 2017
    Ignacio García Marco (I2M, Université d'Aix-Marseille)
    Noether Resolutions
    Let \(R := K[x_1,\ldots,x_n]\) be a polynomial ring over an infinite field \(K\), and let \(I \subset R\) be a graded ideal. We say that \(A := K[x_1,\ldots,x_d]\) is a Noether normalization of \(R/I\) if \(A \hookrightarrow R/I\) is an integral extension. Whenever \(A\) is a Noether normalization of \(R/I\), then \(R/I\) is a finitely generated \(A\)-module and, thus, it has a finite minimal graded free resolution as \(A\)-module. In this talk we will study this resolution, which we call the Noether resolution of \(R/I\). When the Krull dimension of \(R/I\) is 1 or 2 we provide an algorithm for obtaining this resolution that involves the computation of a particular Gröbner basis of \(I\). When \(R/I\) is a semigroup ring we will also explain how one can replace the Gröbner basis computation by computations in the underlying semigroup.
  • Vendredi 15 décembre 2017
    Adrien Poteaux (Université de Lille)
    A dichotomic Newton-Puiseux algorithm using dynamic evaluation.
    Puiseux series (generalisation of Taylor series above critical points) are a fundamental object in the theory of plane algebraic curves. This talk will focus on the arithmetic complexity of the well-known Newton Puiseux algorithm and its variants. Denoted \(D\) the total degree of the input bivariate polynomial, Duval proved a \(O(D^8)\) complexity result. This has been improved to \(\tilde O(D^5)\) by truncating powers of \(X\) during the computation and introducing fast multiplication.
    After providing the tools of the Newton-Puiseux algorithm, we will first present some results that enable to reduce the total number of recursive calls of the algorithm from \(O(D^2)\) to \(\tilde O(D)\), leading to a complexity in \(\tilde O(D^4)\). Finally, we will present a new divide and conquer algorithm that reduces the complexity to \(\tilde O(D^3)\).
    This work begun during my PhD, under the supervision of Marc Rybowicz; the recent ameliorations started from a collaboration with Marc in 2011. The new divide and conquer algorithm is a collaboration with Martin Weimann. This paper is dedicated to Marc Rybowicz, who sadly passed away in November 2016.
  • Vendredi 19 janvier 2018
    Enrique González Jiménez (Universidad Autónoma de Madrid)
    Growth of torsion of elliptic curves.
    One of the main goals in the theory of elliptic curves is to characterize the possible torsion structures over a given number field, or over all number fields of a given degree. One of the milestone in this subject was the characterization of the rational case given by Mazur in 1978. Later, the quadratic case was obtained by Kamienny, Kenku and Momose in 1992. For greater degree a complete answer for this problem is still open, although there have been some advances in the last years.
    The purpose of this talk is to shed light on how the torsion group of an elliptic curve defined over the rationals grows upon base change.
    This is an ongoing project partially joint with A. Lozano-Robledo, F. Najman and J. M. Tornero.
  • Vendredi 26 janvier 2018
    Chloe Martindale (Technical University of Eindhoven)
    Isogeny graphs of abelian varieties and applications to the discrete logarithm problem.
    An isogeny graph is a graph whose vertices correspond to abelian varieties (with some structure) and whose edges correspond to isogenies of a certain degree. The structure of isogeny graphs for elliptic curves was first studied by David Kohel in his PhD thesis and has since been an essential tool in algorithmic number theory (for example to compute the endomorphism ring of an ordinary elliptic curve over a finite field) and cryptography (for example in the post-quantum cryptographic protocol SIDH). We present a structure theorem for isogeny graphs of ordinary abelian varieties, and explain how, under some heuristic assumptions, this can be applied to attacking the discrete logarithm problem for genus 3 curves and possibly some families of elliptic curves.
  • Vendredi 2 février 2018
    Marius Vuille (École Polytechnique Fédérale de Lausanne)
    Computing cyclic isogenies between principally polarized abelian varieties over finite fields.
    The explicit computation of isogenies between abelian varieties over finite fields is an interesting problem that finds its applications not only in transporting instances of the Discrete Logarithm Problem, but can also be used to compute endomorphism rings or even in point counting. So far, only isogenies with kernel a maximal isotropic subgroup of the \ell - torsion have been described and implemented. We describe an algorithm to compute isogenies with cyclic kernels, provided they exist.
  • Vendredi 9 février 2018
    Frédéric Bihan (Université de Savoie)
    Croissance du volume mixte pour les polytopes convexes et une règle de Cramer pour les systèmes polynomiaux.
    Si P_1,...,P_n, Q_1,...,Q_n sont des polytopes convexes à sommets dans le réseau des points entiers de R^n et que P_i est inclus dans Q_i pour tout i, alors le volume mixte de (P_1,...,P_n) est majoré par celui de (Q_1,...,Q_n). Dans un travail récent avec Ivan Soprunov (Cleveland University), nous caractérisons les paires de n-uplets de polytopes pour lesquelles cette inégalité est stricte. Le lien entre volume mixte et systèmes polynomiaux est le théorème de Bernstein-Kouchnirenko qui prédit que le nombre de solutions dans le tore complexe d'un système polynomial de polytopes de Newton P_1,...,P_n est génériquement égal au volume mixte de ces polytopes. On utilise un de nos critères pour obtenir une règle de Cramer pour les systèmes polynomiaux qui généralise celle connue dans le cas linéaire.
  • Vendredi 16 février 2018
    Fabien Pazuky (Université de Copenhagen)
    Courbes elliptiques et isogénies.
    Deux courbes elliptiques E et E' définies sur un corps de nombres K sont isomorphes sur la clôture algébrique de K si et seulement si elles ont le même j-invariant. On se pose la question suivante : comment est-ce que ce j-invariant varie dans les classes d'isogénies ? On montre une majoration de la différence des hauteurs des j-invariants de courbes elliptiques isogènes et on en déduit plusieurs conséquences, notamment une borne explicite sur la hauteur des polynômes modulaires et un contrôle des formules de Vélu. Si le temps le permet, on fera de plus une remarque sur les rangs de Mordell-Weil des courbes elliptiques.
  • Du lundi 19 au vendredi 23 février 2018
    Conférence : Méthodes numériques pour les courbes algébriques
  • Vendredi 16 mars 2018
    Joelle Saade (Université de Limoges)
    A new approach for Formal Reduction of Singular Linear Differential Systems Using Eigenrings
    In this talk, we will present a new algorithm for the formal reduction of linear differential systems with Laurent series coefficients. We show how to obtain a decomposition of Balser, Jurkat and Lutz using eigenring techniques. We establish structural information on the obtained indecomposable subsystems and retrieve information on their invariants such as ramification. We show why Barkatou's algorithm then perform well on these subsystems. We also give precise estimates of the precision on the power series which is required in each step of the algorithm. We give some examples computed in Maple.
  • Vendredi 23 mars 2018
    Elif Saçıkara (Sabanci University)
    Concatenated Structure of Quasi-Abelian Codes and a Resulting Minimum Distance Bound
    For a positive integer l and a group algebra Fq[H], a quasi-abelian(QA)code of index l is a Fq[H]-submodule of Fq[H]^l, where H is an abelian group of order m. The special case H := Z_m, where Z_m is a cyclic group of order m, gives a quasi-cyclic (QC) code of index l and length ml. So, QA codes are natural generalization of QC codes. Ling and Sole showed that QC codes can be decomposed as a direct sum of certain linear codes of length l by applying the Chinese Remainder Theorem, such a method is called the CRT decomposition. Jensen represented a concatenated structure of QC codes and later Guneri-Ozbudak showed that these decompositions are equivalent. In this talk, we present a concatenated structure of QA codes by using the CRT decomposition of QA codes introduced by Jitman and Ling, and we show that both decompositions are equivalent. Concatenated structure also leads to asymtotical goodness and provides a general minimum distance bound, extending the analogue bound for QC codes due to Jensen.
  • Vendredi 30 mars 2018
    Ivan Pogildiakov (Université de la Polynésie Française et IRMAR)
    On the existence of hyperelliptic curves over finite fields and linear binary codes
    Given integers q, N, and g, does there exist a (non-singular irreducible) genus g curve over F_q having presicely N rational points? Statistics on the distribution of the number of rational points were studied during the last decade for various families of curves. However, we know how to answer this question in several special cases only. In this talk we will discuss the question in the case of hyperelliptic curves. Given q and N, new bounds on the genera will be presented. Several problems in the theory of (linear binary) error correcting codes will naturally arise. We will consider, if time permits, the practical side of this question and the superelliptic case of the question as well.
  • Vendredi 6 avril 2018
    John Cremona (University of Warwick)
    Black Box Galois Representations.
    The Serre-Faltings-Livne method concerns the comparison of two 2-dimensional p-adic Galois representations of the absolute Galois group G_K of a number field K in the case p=2. Assuming that both are known to be unramified outside the same set S of primes of K and that they have the same determinant, the method provides a finite set T of primes of K, disjoint from S and depending only on K and S, such that if the two representations have the same trace at the Frobenius elements of all the primes in T then they are isomorphic. When we describe a Galois representation with data (K, S, p) as a a "Black Box", we mean that the only information we know about it is the trace and determinant of Frobenius at any given prime not in S; in these terms, the SFL method allows us to determine whether two 2-adic black box representations are isomorphic. In this talk we consider black box representations from a slightly wider perspective, and consider how much information we can obtain about such a representation by asking only a finite number of questions, such as residual reducibility, the determinant character, and the size and structure of the isogeny class of the representation. This is joint work with Alejandro Argaez (p=2) and Mattia Sanna (p=3).
  • Vendredi 6 avril 2018
    David Lubicz (DGA et IRMAR)
    Quelques améliorations à l'algorithme AGM et ses généralisations en genre plus grand.
    Nous décrivons des améliorations à l'algorithme de comptage de points AGM et ses généralisation en genre plus grand. Nous décrivons plus précisément un algorithme qui permet de retrouver efficacement la classe de similitude de l'action du morphisme de Frobenius (ou son dual) sur l'espace cotangent du relevé canonique de la variété abélienne de départ (définie sur un corps fini). Cet algorithme a un intérêt indépendamment de l'AGM.
  • Vendredi 13 avril 2018
    Jade Nardi (Institut de Mathématiques de Toulouse)
    Paramètres des codes correcteurs sur les surfaces de Hirzebruch.
    Les surfaces de Hirzeburch forment une famille de surfaces réglées au-dessus de \(\mathbb P^1\) paramétrée par les entiers naturels. Leur structure de variétés toriques les munit chacunes d'un anneau gradué de polynômes très facile à manier, l'anneau de Cox. En se fixant un degré \(s\) (i.e. une composante homogène de l'anneau), on peut définir l'évaluation des polynômes de degré \(s\) en les points \(\mathbb F_q\)-rationnels de la surface et ainsi définir le codes d'évaluation associé à la manière des codes de Reed-Muller sur \(\mathbb P^n\). Le but de cet exposé est de déterminer explicitement les paramètres [n,k,d] de tels codes. La distance minimale, obtenue grâce à des outils de bases de Gröbner, nous permet de déduire une majoration du nombre de points \(\mathbb F_q\)-rationnels d'une courbe sur une surface de Hirzebruch en fonction de sa classe de Picard et même une forme des courbes qui atteignent ce majorant.
  • Vendredi 20 avril 2018
    Pierre Loidreau (IRMAR)
    Quoi de neuf en cryptographie post-quantique ?
    Retour sur les propositions de systèmes de chiffrements post-quantiques candidats à la standarditsation par le NIST.
  • Vendredi 18 mai 2018
    Aurel Page (INRIA, Bordeaux)
    Algorithmes pour la topologie des variétés arithmétiques compactes et les opérateurs de Hecke
    Un groupe arithmétique est un groupe commensurable aux points entiers d'un groupe algébrique linéaire défini sur les rationnels. D'après un théorème classique de Borel et Harish-Chandra, de tels groupes admettent une présentation finie; leur preuve a été rendue algorithmique par Grunwald et Segal, mais sans analyse de complexité de l'algorithme obtenu. Depuis quelques années, on s'intéresse beaucoup à des invariants plus profonds des groupes arithmétiques : leurs groupes de cohomologie, munis de l'action des opérateurs de Hecke. Je présenterai un travail en cours avec Michael Lipnowki : nous décrivons un algorithme qui, étant donné un groupe arithmétique \(\Gamma\) dont la variété arithmétique associée est compacte, calcule la cohomologie de \(\Gamma\) munie de l'action des opérateurs de Hecke, et nous analysons sa complexité.
  • Vendredi 25 mai 2018 — exceptionnellement à 14h
    Alain Couvreur (INRIA, École Polytechnique)
    Sur les récentes soumissions au NIST basées sur des codes algébriques
    On présentera différents schémas de chiffrement basés sur des codes algébriques et ayant donné lieu à une soumission au NIST. On présentera également une attaque d'un type nouveau impactant la sécurité du schéma de chiffrement appelé DAGS. L'attaque est issue d'un travail en collaboration avec Élise Barelli.
  • Vendredi 8 juin 2018
    Gilles Villard (CNRS, ÉNS de Lyon)
    Computation of the resultant of two generic bivariate polynomials over a field
    An algorithm is presented for computing the resultant of two generic bivariate polynomials over a field \(K\). For such \(p\) and \(q\) in \(K[x,y]\) of degree \(d\) in \(x\) and \(n\) in \(y\), the algorithm computes the resultant with respect to \(y\) using \((n^{2–\frac 1 \omega} d)^{1+o(1)}\) arithmetic operations in \( K\), where two \(n\times n\) matrices are multiplied using \(O(n^\omega)\) operations. Previous algorithms from the early 1970’s required time \((n^2 d)^{1+o(1)}\). We also discuss some extensions of the approach to the computation of characteristic polynomials of generic structured matrices and in univariate quotient algebras.
  • Vendredi 29 juin 2018
    Vivien Beraud, Elie Eid, Fabien Narbonne (Univeriste de Rennes 1)
    Soutenance de stage de M2

Archives du séminaires

Voir par ici.