Speaker : Elena Berardini (CNRS, Université de Bordeaux)
Title : Algebraic Geometry codes in the sum-rank metric over cyclic division algebras
Abstract : Linear codes in the Hamming metric have played a central role in error correction since the 1950s and have been studied extensively. In contrast, the theory of codes in the sum-rank metric is still in its early stages, with only a few known constructions. A cornerstone of coding theory in the Hamming metric is the family of Reed–Solomon (RS) codes, constructed by evaluating univariate polynomials at distinct elements of a finite field $\mathbb{F}_q$. These codes have optimal parameters but are inherently limited in length by the size of $\mathbb{F}_q$. A classical approach to overcoming this limitation, while retaining good parameters, is to evaluate rational functions at points on algebraic curves, leading to the construction of Algebraic Geometry (AG) codes. The sum-rank analogue of RS codes is the family of linearized Reed–Solomon (LRS) codes [2], which also achieve optimal parameters but face the same length restriction as RS codes. In this talk, inspired by the parallels between RS and LRS codes, we introduce analogues of AG codes in the sum-rank metric, which we call linearized Algebraic Geometry (LAG) codes [1].
We will begin by reviewing the essential background on sum-rank metric codes and univariate Ore polynomials. We then extend this framework by working over an Ore algebra with coefficients in the function field of a curve, defining the relevant evaluation morphisms and the spaces of functions to be evaluated. Building on this foundation, we construct linearized AG codes and establish lower bounds on their dimension and minimum distance. If time permits, we will also discuss examples and highlight recent progress on decoding LAG codes.
This is based on a joint work with X. Caruso, and on ongoing works with X. Caruso and F. Drain, and with P. Beelen, A. Gruica, and M. Montanucci.
[1] E. Berardini and X. Caruso. Algebraic Geometry codes in the sum-rank metric. IEEE Transactions on Information Theory, Volume 70, Issue 5, May 2024, pp 3345 – 3356.
[2] U. Martínez-Peñas. Skew and linearized Reed–Solomon codes and maximum sum rank distance codes over any division ring. In: Journal of Algebra 504 (2018), pp. 587–612.
Speaker : Clemens Hofstadler (Johannes Kepler University, Linz)
Title : Algebraic Automated Theorem Proving
Abstract : Algebraic techniques, such as Gröbner bases, have a long and successful history in automatic geometric theorem proving. Recently, these methods have found a promising new area of application: proving first-order formulas involving identities of matrices and, more generally, of linear operators. Such statements,called operator statements, appear in various branches of mathematics, such aslinear algebra, geometry, and functional analysis, as well as in related disciplineslike signal processing or quantum physics.In this talk, we present how the correctness of an operator statement canbe translated into an algebraic statement about noncommutative polynomials,which can then be verified automatically using computer algebra. Moreover, wediscuss how this framework can be used to compute short (and even minimal)proofs of operator statements and how it allows to certify the invalidity of falsestatements by constructing explicit counterexamples.
Speaker : Philippe Moustrou (IMT, Université Toulouse Jean Jaures)
Title : Effective aspects of point configurations in discrete geometry
Abstract : Several problems in discrete geometry consist in finding an optimal way of distributing points in a given space with respect to certain properties. For instance, the famous sphere packing problem asks for the greatest proportion of the Euclidean space that can be filled with non-overlapping balls of the same radius. In low dimensions, specific, highly structured configurations are often the best candidates, but proving that they are the unique optimal configurations might be a very challenging task.
In this talk, after introducing the sphere packing problem and related questions in discrete geometry, we will discuss a general method to obtain good bounds for such problems via linear and semi-definite programming. While this approach can provide good numerical bounds, further work is typically necessary to obtain exact optimality results. This gives rise to challenging questions at the intersection of analysis, geometry, optimization, and computer algebra, such as interpolation problems for families of functions, or obtaining an exact solution for large semi-definite programs. The aim of the talk is to give an overview of these challenges and the recent methods developed to address them.
Speaker : Lucas Pannier (Univ. Versailles Saint-Quentin-en-Yvelines)
Title : An effective proof of the p-curvature conjecture for first-order differential equations with rational coefficients
Abstract : In 1974, Honda proved the p-curvature conjecture for order one differential equations with rational coefficients over a number field. He demonstrated that in this setting, the p-curvature conjecture was equivalent to a theorem due to Kronecker, providing a local-global criterion for the splitting of polynomials over the rational numbers.
In 1985 the Chudnovskys published another proof of Honda's theorem (and of Kronecker's theorem) by means of Padé approximation and elementary number theory, thus paving the way to an effective version of these results. Here, by "effective" we mean that we wish to obtain an explicit finite bound on the number of p-curvatures to be computed in order to decide the algebraicity of the solution of the differential equation. In this talk, I will explain how to obtain such a bound, and how this compares both in theory and practice to other methods that solve the same problem, mainly finding rational roots of univariate polynomials. This is joint work with Florian Fürnsinn (University of Vienna).
Speaker : Weijia Wang (Sorbonne Université)
Title : Solving Parametric Linear Matrix Inequalities and Convergence Analysis in Optimization
Abstract : We consider linear matrix inequalities (LMIs) A = A₀ + x₁A₁ + ... + xₙAₙ ≥ 0 with the Aᵢ's being m×m symmetric matrices, with entries in a ring R. When R = ℝ, the feasibility problem consists in deciding whether the xᵢ's can be instantiated to obtain a positive semidefinite matrix. When R = ℚ[y₁, ..., yₜ], the problem asks for a formula on the parameters y₁, ..., yₜ, which describes the values of the parameters for which the specialized LMI is feasible. This problem can be solved using general quantifier elimination algorithms, with a complexity that is exponential in n. In our paper, we leverage the LMI structure of the problem to design an algorithm that computes a formula Φ describing a dense subset of the feasible region of parameters, under genericity assumptions. The complexity of this algorithm is exponential in n, m and t but becomes polynomial in n when m and t are fixed. We apply the algorithm to a parametric sum-of-squares problem and to the convergence analyses of certain first-order optimization methods, which are both known to be equivalent to the feasibility of certain parametric LMIs, hence demonstrating its practical interest.
Speaker : Camille Garnier (XLIM, Université de Limoges)
Title : Locally testable codes in rank metric
Abstract : Error correcting codes are techniques designed to detect or correct errors that can occur during data transmission or storage. The idea is the following: instead of directly storing or sending the data (called the "message"), we transform it into a "codeword", by adding extra structured information to it, called "redundancy". With this redundancy, we want to be able to detect or correct errors in order to recover the original message. Retrieving the message from the received or stored word is known as "decoding". An error correcting code is a set of codewords.
In this work we consider linear codes, represented as vector spaces over finite fields. The most famous metric for error correcting codes is the Hamming metric. The Hamming distance between two vectors is the number of coordinates in which they differ. The Hamming weight of a vector is the number of its nonzero coordinates.
In this work we focus on locally testable codes (LTCs). Such codes satisfy the property that we can decide whether a vector is a codeword or not by inspecting only a small part of its coordinates. More precisely, a code is said to be locally testable if there exists an efficient algorithm that, given a vector, selects only a few of its coordinates (called "queries") and decides whether the vector belongs to the code. This algorithm must accept every valid codeword, and should not accept vectors outside the code at certain distance, with some error probability. This definition is the one of locally testable codes in Hamming metric: using only a few coordinates means the algorithm uses information of low Hamming weight. We aim to extend this notion to the rank metric, a well-known alternative to the Hamming metric in coding theory. The rank metric plays a central role in various cryptographic protocols .
In this framework we need to revise the notion of locally testable codes. Indeed, in rank metric, even an error of rank weight one can have maximum Hamming weight. This means that even if a vector is at rank distance one from a certain code, all of its coordinates can be corrupted.
In this work, we introduce a new definition of locally testable codes in rank metric, and we present examples of codes satisfying this definition.
Speaker : Jade Nardi (CNRS, IRMAR, Université de Rennes)
Title : Maximum number of zeroes of polynomials on weighted projective spaces over a finite field
Abstract : This talk is dedicated to the study of the maximum number of rational points at which a homogeneous polynomial can vanish on a weighted projective space over a finite field, provided that the first weight is equal to one. We solve a conjecture by Aubry, Castryck, Ghorpade, Lachaud, O'Sullivan and Ram, which stated a Serre-like bound that holds with equality when the first weight is one, and when considering polynomials whose degree is divisible by the least common multiple of the weights. We refine this conjecture by lifting the restriction on the degree and we prove it using footprint techniques from Groebner basis theory and Serre's classical bound.
Joint work with Rodrigo San-José, preprint ArXiv 2507.22597.
Speaker : Christophe Levrat (Inria Saclay)
Title : Effective Artin-Schreier-Witt theory for curves
Abstract : Let X be a smooth projective curve defined over the finite field with $p$ elements, and $n$ be a positive integer. Finding a cyclic cover of degree $p^n$ of X is an easy task: picking (almost) any $n$-truncated Witt vector with coefficients in the function field of X yields such a cover. However, if we moreover ask the cover to be unramified, the problem becomes much more difficult. We present an algorithm which, given a Hasse–Witt matrix for X, computes all such unramified cyclic covers. This is joint work with Rubén Muñoz--Bertrand.
Speaker : Ruben Muñoz--Bertrand (Inria Saclay)
Title : Faster Computation of Witt Vectors Ring Laws
Abstract : Witt vectors are a useful tool in arithmetic geometry. They have applications in error correcting codes and cryptography. We will recall their definition, and see why operations in the ring of Witt vectors are expensive. Until now, only Finotti’s algorithm, introduced in 2014, has managed to improve upon the direct computation of the polynomials with integer coefficients defining the ring laws. We will see how applying an isomorphism of Illusie yields a new algorithm for Witt vectors with polynomial coefficients, which is more efficient than Finotti's.
Speaker : Adya Musson-Leymarie (XLIM, Université de Limoges)
Title : From Gröbner bases to standard bases: a rewriting-theoretic perspective
Abstract : Gröbner bases are characterised in terms of a notion called confluence of multivariate polynomial division, which is a property that implies that, no matter what the sequence of divisions, the end result (called normal form) is always the same. Together with the notion of strong normalisation, this gives what the classical rewriting theory and its historical applications are mostly concerned about. However, those properties can be too restrictive for other objects of study, e.g. commutative formal power series. In this talk, we will consider a syntactically equivalent concept of Gröbner but for formal power series (originally called standard bases) and, by extending the classical notions of confluence and normalisation by utilising the underlying topology, we will recover characterisations of standard bases which are very analogous as for Gröbner bases.
Speaker : Romaric Neveu (XLIM, Université de Limoges)
Title : The matrix subcode equivalence problem, or how to make a polynomial system harder to solve
Abstract : In cryptography, the security of public-key cryptosystems always relies on the capacity of an attacker to solve a hard problem.A wide variety of such problems exist, such as the factoring of an integer for RSA, the discrete logarithm problem for Diffie-Hellman, or finding short vectors in a lattice.In code-based cryptography, a problem has recently been used with much success: the code equivalence problem.This problem asks, given two codes $\mathcal{C}$ and $\mathcal{D}$, to find an isometry that links the two of them.In this talk, we will focus on algebraic methods used for solving equivalence problems in the setting of matrix codes, where isometries correspond to multiplication by invertible matrices.Such methods rely on modeling the problem to obtain a multivariate polynomial system and then computing a Gröbner basis.In particular, we will show how slight modifications of the problem lead to much harder instances, notably by considering isometries between subcodes.
