We discuss algorithms for arithmetic properties of hypergeometric functions. Most notably, we are able to compute the p-adic valuation of a hypergeometric function on any disk of radius smaller than the p-adic radius of convergence. This we use, building on work of Christol, to determine the set of prime numbers modulo which it can be reduced. Moreover, we describe an algorithm to find an annihilating polynomial of the reduction of a hypergeometric function modulo p.

We introduce the first geometric construction of codes in the sum-rank metric, which we called linearized Algebraic Geometry codes, using quotients of the ring of Ore polynomials with coefficients in the function field of an algebraic curve. We study the parameters of these codes and give lower bounds for their dimension and minimum distance. Our codes exhibit quite good parameters, respecting a similar bound to Goppa’s bound for Algebraic Geometry codes in the Hamming metric. Furthermore, our construction yields codes asymptotically better than the sum-rank version of the Gilbert–Varshamov bound.

In this paper, we study ideals spanned by polynomials or overconvergent series in a Tate algebra. With state-of-the-art algorithms for computing Tate Gröbner bases, even if the input is polynomials, the size of the output grows with the required precision, both in terms of the size of the coefficients and the size of the support of the series.

Tate introduced in [18] the notion of Tate algebras to serve, in the context of analytic geometry over the p-adics, as a counterpart of polynomial algebras in classical algebraic geometry. In [6,7] the formalism of Gröbner bases over Tate algebras has been introduced and advanced signature-based algorithms have been proposed. In the present article, we extend the FGLM algorithm of [8] to Tate algebras. Beyond allowing for fast change of ordering, this strategy has two other important benefits. First, it provides an efficient algorithm for changing the radii of convergence which, in particular, makes effective the bridge between the polynomial setting and the Tate setting and may help in speeding up the computation of Gröbner basis over Tate algebras. Second, it gives the foundations for designing a fast algorithm for interreduction, which could serve as a basic primitive in our previous algorithms and accelerate them significantly.

Introduced by Tate in [Ta71], Tate algebras play a major role in the context of analytic geometry over the p-adics, where they act as a counterpart to the use of polynomial algebras in classical algebraic geometry. In [CVV19] the formalism of Gröbner bases over Tate algebras has been introduced and effectively implemented. One of the bottlenecks in the algorithms was the time spent on reduction, which are significantly costlier than over polynomials. In the present article, we introduce two signature-based Gröbner bases algorithms for Tate algebras, in order to avoid many reductions. They have been implemented in SageMath. We discuss their superiority based on numerical evidence.

Tate algebras are fundamental objects in the context of analytic geometry over the p-adics. Roughly speaking, they play the same role as polynomial algebras play in classical algebraic geometry. In the present article, we develop the formalism of Gröbner bases for Tate algebras. We prove an analogue of the Buchberger criterion in our framework and design a Buchberger-like and a F4-like algorithm for computing Gröbner bases over Tate algebras. An implementation in SageMath is also discussed.

We present a new package ZpL for the mathematical software system SageMath. It implements a sharp tracking of precision on p-adic numbers, following the theory of ultrametric precision introduced in a previous paper by the same authors. The underlying algorithms are mostly based on automatic differentiation techniques. We introduce them, study their complexity and discuss our design choices. We illustrate the benefits of our package (in comparison with previous implementations) with a large sample of examples coming from linear algebra, commutative algebra and differential equations.

We describe an algorithm for fast multiplication of skew polynomials. It is based on fast modular multiplication of such skew polynomials, for which we give an algorithm relying on evaluation and interpolation on normal bases. Our algorithms improve the best known complexity for these problems, and reaches the optimal asymptotic complexity bound for large degree. We also give an adaptation of our algorithm for polynomials of small degree. Finally, we use our methods to improve on the best known complexities for various arithmetics problems.

We analyze the precision of the characteristic polynomial XM of an nxn p-adic matrix M using differential precision methods developed previously. When M is an integral matrix whose entries are all given at the same precision O(pN), we give a criterion (checkable within Õ(nω) operations in Fp) for the existence of a coefficient of XM with more accuracy than O(pN). In general, we provide two algorithms for determining the optimal precision of the coefficients of XM and of M's eigenvalues. We provide evidence showing that classical algorithms do not reach this optimal precision in general.

The p-curvature of a system of linear differential equations in positive characteristic p is a matrix that measures how far the system is from having a basis of polynomial solutions. We show that the similarity class of the p-curvature can be determined without computing the p-curvature itself. More precisely, we design an algorithm that computes the invariant factors of the p-curvature in time quasi-linear in √ p. This is much less than the size of the p-curvature, which is generally linear in p. The new algorithm allows to answer a question originating from the study of the Ising model in statistical physics.

We study two important operations on polynomials defined over complete discrete valuation fields: Euclidean division and factorization. In particular, we design a simple and efficient algorithm for computing slope factorizations, based on Newton iteration. One of its main features is that we avoid working with fractional exponents. We pay particular attention to stability, and analyze the behavior of the algorithm using several precision models.

We design an algorithm for computing the p-curvature of a differential system in positive characteristic p. For a system of dimension r with coefficients of degree at most d, its complexity is O~ (p d rω) operations in the ground field (where ω denotes the exponent of matrix multiplication), whereas the size of the output is about p d r2. Our algorithm is then quasi-optimal assuming that matrix multiplication is (i.e. ω = 2). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.

Using the differential precision methods developed previously by the same authors, we study the p-adic stability of standard operations on matrices and vector spaces. We demonstrate that lattice-based methods surpass naive methods in many applications, such as matrix multiplication and sums and intersections of subspaces. We also analyze determinants, characteristic polynomials and LU factorization using these differential methods. We supplement our observations with numerical experiments.

We discuss theoretical and algorithmic questions related to the p-curvature of differential operators in characteristic p. Given such an operator L, and denoting by Ξ(L) the characteristic polynomial of its p-curvature, we first prove a new, alternative, description of Ξ(L). This description turns out to be particularly well suited to the fast computation of Ξ(L) when p is large: based on it, we design a new algorithm for computing Ξ(L), whose cost with respect to p is Õ(p0.5) operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the p-curvature, had merely slightly subquadratic complexity Õ(p1.79).