Louis Van

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive programwhere rem is the remainder in the division of a by b, the unique natural number r such that for some natural number q,It is an algorithm from the remainder function rem, meaning that in computing its time complexity function cε, we assume that the values rem are provided on demand by some “oracle” in one “time unit”. It is easy to prove thatMuch more is known about cε, but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's optimality among its peers—algorithms from rem:Conjecture. If an algorithm α computes gcd from rem with time complexity cα, then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα > r log2a.

Let T be a complete o-minimal extension of the theory of real closed fields. We characterize the convex hulls of elementary substructures of models of T and show that the residue field of such a convex hull has a natural expansion to a model of T. We give a quantifier elimination relative to T for the theory of pairs (R, V) where $\mathscr{R} \models T$ and V ≠ R is the convex hull of an elementary substructure of R. We deduce that the theory of such pairs is complete and weakly o-minimal. We also give a quantifier elimination relative to T for the theory of pairs (R, N) with R a model of T and N a proper elementary substructure that is Dedekind complete in R. We deduce that the theory of such "tame" pairs is complete.

I solve here some problems left open in “T-convexity and Tame Extensions” [9]. Familiarity with [9] is assumed, and I will freely use its notations. In particular,Twill denote a completeo-minimal theory extending RCF, the theory of real closed fields. Let (,V) ⊨Tconvex, let=V/m(V)be the residue field, with residue class mapx↦:V↦, and let υ:→ Γ be the associated valuation. “Definable” will mean “definable with parameters”.The main goal of this article is to determine the structure induced by(,V)on its residue fieldand on its value group Γ. In [9] we expanded the ordered fieldto a model ofTas follows. Take a tame elementary substructure′ ofsuch thatR′ ⊆VandR′maps bijectively ontounder the residue class map, and make this bijection into an isomorphism′ ≌ofT-models. (We showed such′ exists, and that this gives an expansion ofto aT-model that is independent of the choice of′.).

Van den Dries, L. and J. Holly, Quantifier elimination for modules with scalar variables, Annals of Pure and Applied Logic 57 161–179. We consider modules as two-sorted structures with scalar variables ranging over the ring. We show that each formula in which all scalar variables are free is equivalent to a formula of a very simple form, uniformly and effectively for all torsion-free modules over gcd domains . For the case of Presburger arithmetic with scalar variables the result takes a still simpler form, and we derive in this way the polynomial-time decidability of the sets defined by such formulas

We extend the field of Laurent series over the reals in a canonical way to an ordered differential field of “logarithmic-exponential series” , which is equipped with a well behaved exponentiation. We show that the LE-series with derivative 0 are exactly the real constants, and we invert operators to show that each LE-series has a formal integral. We give evidence for the conjecture that the field of LE-series is a universal domain for ordered differential algebra in Hardy fields. We define composition of LE-series and establish its basic properties, including the existence of compositional inverses. Various interesting subfields of the field of LE-series are also considered

This article is essentially a commentary on a little-known text by `Alain' (whose real name was Emile-Auguste Chartier), successively entitled Les marchands de sommeil and Vigiles de l'esprit. This piece of work, initially a prize-giving speech to students in a Parisian lycée, was rewritten by Alain many years later during the Second World War. It describes with acute intelligence and in a splendid metaphoric language the enduring and compelling proposition that the formation of critical judgement should be the ultimate purpose of all teaching