Xavier VIDAUX

PUBLICATIONS

(almost only preprints appear here, not the revised versions - hence they might contain some minor mistakes)


24. Existential decidability for addition and divisibility in holomorphy subrings of global fields, with Carlos Martinez Ranero and Javier Utreras, Submitted.
Abstract: We investigate the problem of deciding whether a system of linear equations, together with divisibility conditions on the variables, has a solution over holomorphy subrings of global fields. We obtain decidability results when we allow poles at a cofinite set of places, and undecidability results when at a finite set of places.
AMS Subject Classification: Primary 11U05, 03B25
Preprint: arXiv:2010.14024

23. The diophantine problem for rings of exponential polynomials, with Dimitra Chompitaki, Natalia Garcia-Fritz, Hector Pasten and Thanases Pheidas, To appear in Annali della Scuola Normale Superiore. Classe di Scienze.
Abstract: One of the main open problems regarding decidability of the existential theory of rings is the analogue of Hilbert's Tenth Problem (HTP) for the ring of entire holomorphic functions in one variable. In the direction of a negative solution, we prove unsolvability of HTP for rings of exponential polynomials. This provides the first known case of HTP for a ring of entire holomorphic functions in one variable strictly containing the polynomials. The technique of proof consists of an interaction between Arithmetic, Analysis, Logic, and Functional Transcendence.
AMS Subject Classification: Primary 11U05, 03B25, 11J81, Secondary 30D15
Preprint: arXiv:2004.00612

22. Dedekind criterion for the monogenicity of a number field versus Uchida's and Lüneburg's, with Carlos R. Videla, To appear in Tohoku Mathematical Journal.
Abstract: We compare three different characterizations, due respectively to R. Dedekind, K. Uchida, and H. Lüneburg, of when Z[θ] is the ring of integers of Q(θ), and apply our results to some concrete 2-towers of number fields.
AMS Subject Classification: Primary 11R04, 11U05
Preprint: arXiv: 1809.04122

21. Hilbert's tenth problem for complex meromorphic functions in seveeral variables, with T. Pheidas, Accepted in International Mathematics Research Notices.
Abstract: We prove that Hilbert's Tenth Problem for meromorphic functions and for entire functions in several variables is unsolvable over the language of rings, together with constant symbols for the variables and a predicate for a place.
AMS Subject Classification: Primary 03B25, Secondary 32A10, 32A20
Preprint: arXiv: 1711.09412

20. Büchi's problem in modular arithmetic for arbitrary quadratic polynomials, with P. Saez and M. Vsemirnov, Canadian Mathematical Bulletin 62-4, pp. 876-885 (2019).
Abstract: Given a prime p greater than or equal to 5 and an integer s greater than or equal to 1, we show that there exists an integer M such that for any quadratic polynomial f with coefficients in the ring of integers modulo p^s, such that f is not a square, if a sequence (f(1),...,f(N)) is a sequence of squares, then N is at most M. We also provide some explicit formulas for the optimal M.
AMS Subject Classification: Primary 11B50, 11B83
See final version
Note: The title in the arXiv version was: Optimal bounds for Büchi's problem in modular arithmetic II.

19. Julia Robinson numbers and arithmetical dynamic of quadratic polynomials, with M. Castillo F. and Carlos R. Videla, Indiana University Mathematics Journal 69-3, p. 873-885 (2020).
Abstract: For the ring of integers of a totally real field of algebraic numbers, J. Robinson defined a set which is always +∞ or of the form [λ,+∞) or (λ,+∞) for some real number λ≥4. All known examples give either {+∞} or [4,+∞). In this paper, we construct infinitely many fields such that the set is an interval, but not equal to [4,+∞).
AMS Subject Classification: Primary 11R04, 11R32, 11R80, 37P05, Secondary 11R09, 11R11
See preprint
or in arXiv: arXiv: 1711.00490

18. Positive existential definability of multiplication from addition and the range of a polynomial, with H. Pasten, Israel Journal of Mathemtatics 216-1, pp. 273-306 (2016). doi 10.1007/s11856-016-1410-x
Abstract: We consider the problem of recovering multiplication in the integers from enrichments of its additive structure, in the positive existential context. We prove that if a conjecture by Caporaso-Harris-Mazur holds, then for all integer-valued polynomials F of degree at least 2, multiplication is positive-existentially definable in (Z,0,1,+,RF,=), where RF is the unary relation F(Z). Similar results were only known for the polynomials F(t)=t² (under the Bombieri-Lang conjecture) and F(t)=tⁿ (under a generalization of the abc conjecture).
AMS Subject Classification: Primary 11U05, Secondary 03C40, 13F20

17. A note on the Northcott property and undecidability, with C. R. Videla, Bulletin of the LMS 48, pp. 58-62 (2015). doi 10.1112/blms/bdv089
Abstract: We uncover a natural relationship between the Northcott property for sets of algebraic numbers and the Julia Robinson number associated to sets of algebraic integers. This implies, in particular, that any subring of a ring of totally real integers having the Northcott property has undecidable first-order theory. Combining this theorem with previous results by the second author, we prove that the compositum of all totally real abelian extensions of Q of bounded degree d has undecidable first-order theory.
AMS Subject Classification: Primary 03B25, 11U05, Secondary 11R80

16. Definability of the natural numbers in totally real towers of nested square roots, with C. R. Videla, Proceedings of the AMS 143-10, pp. 4463-4477 (2015). doi 10.1090/S0002-9939-2015-12592-0
Abstract: For the ring of integers O of a totally real algebraic field, Julia Robinson defines a set A(O) such that either A(O)={+∞} or it is an interval in R. She then proves that if this set has a minimum, then the natural numbers can be defined in O, and hence O has undecidable first-order theory. All known examples are such that A(O) has a minimum which is either 4 or +∞. In this work, we construct two infinite families of sub-rings of such rings for which inf(A(O)) is strictly between 4 and +∞. In one family, the infimum is a minimum, whereas in the other family it is not, but we can still define the natural numbers in this case.
AMS Subject Classification: Primary 03B25, Secondary 11U05, 11R80

15. Optimal bounds for Büchi's problem in modular arithmetic, with P. Saez and M. Vsemirnov, Journal of Number Theory 149, pp. 368-403 (2014). doi 10.1016/j.jnt.2014.10.008
Abstract: We study the second order analogue of the problem of finding optimal lower and upper bounds for the length of sequences of squares in arithmetic progression modulo a prime, and some connections with the computational problem of finding a quadratic non-residue modulo a prime. More precisely, we work modulo an integer and our objects of study are those sequences of squares whose the second difference is an invertible constant. The main results of our work is a number of exact formulae that allow to reduce the problem to prime moduli. We also observe several phenomena which are supported by extensive numerical computations.
AMS Subject Classification: 11B50, 11T99, 12Y05, 68Q17

14. Uniform existential interpretation of arithmetic in rings of functions of positive characteristic, with H. Pasten and T. Pheidas, Inventiones Mathematicae 196-2, pp. 453-484 (2014). doi 10.1007/s00222-013-0472-1
Abstract: We show that first order integer arithmetic is uniformly positive-existentially interpretable in large classes of (subrings of) function fields of positive characteristic over some languages that contain the language of rings. One of the main intermediate results is a positive existential definition (in these classes), uniform among all characteristics p, of the binary relation 'y=x^p^s or x=y^p^s for some non-negative integer s'. A natural consequence of our work is that there is no algorithm to decide whether or not a system of polynomial equations over Z[z] has solutions in all but finitely many polynomial rings F_p[z]. Analogous consequences are deduced for the rational function fields F_p(z), over languages with a predicate for the valuation ring at zero.
AMS Subject Classification: 03B25, 11U05, 12L05

Preprint of an older version of this article : arXiv: 1012.0960

13. A short state of the art of Büchi's problem, Séminaire de Structures Algébraiques Ordonnées 86 (2010-2011).
Abstract: Büchi's problem is a general problem of arithmetical flavor that can be asked in any ring with unit A, and that, if solved positively, can be used as a tool to obtain very strong undecidability results, as it (often) implies that the problem (or some slight modification of it) of representation of an arbitrary vector of elements of A by a system of diagonal forms (quadratic, or of any fixed order) over the prime subring of A is undecidable when the positive existential theory of the ring A is known to be undecidable. This was the original motivation of J. R. Büchi in the 70's, but since then Büchi's problem has been found to be relevant in various other contexts. Firstly, in 1999, P. Vojta found a connexion with Bombieri-Lang's conjecture on the locus of rational points on varieties of general type. Secondly, new applications to logic have been found recently, giving rise to quite general undecidability results, through existential definitions which are uniform among rings of different characteristics. Thirdly, H. Pasten recently found some connection with a special case of a conjecture by Vojta. We will make some of these statements a bit more precise in the text, but for an extensive discussion and bibliography on Büchi's problem, we refer to the survey by Pasten, Pheidas and myself (9 in this list), our objective being to make an updated and somewhat compact presentation of the state of the art on Büchi's problem and some problems in logic that are intrinsically linked to it. For that reason, we will try to concentrate on the qualitative aspects of the existing results.
AMS Subject Classification: 11D09

Preprint of this article : pdf

12. Polynomial parametrizations of length 4 Büchi sequences, Acta Arithmetica 150-3, pp. 209-226 (2011).
Abstract: Büchi's problem asks whether there exists a positive integer M such that any sequence (x_n) of at least M integers, whose second difference of squares is the constant sequence (2), satisifies x_n^2=(x+n)^2 for some integer x. A positive answer to Büchi's problem would imply that there is no algorithm to decide whether or not an arbitrary system of quadratic diagonal forms over the integers can represent an arbitrary given vector of integers. We give an explicit infinite family of polynomial parametrizations of non-trivial 4-terms Büchi sequences of integers. In turn, these parametrizations give an explicit infinite family of curves with the following property: any (non-trivial) integral point on one of these curves would give a length 5 non-trivial Büchi sequence of integers (it is not known whether any such sequence exists). Finally, we prove that infinitely many 4 terms non-trivial Büchi sequences do not extend to a 5-terms Büchi sequence.
AMS Subject Classification: 11D09

Preprint of (an old version of) this article : arXiv:1008.2994

11. A characterization of Büchi's integer sequences of length 3, with P. Saez, Acta Arithmetica 149-1, pp. 37-56 (2011).
Abstract: We give a new characterization of Büchi sequences (sequences whose sequence of squares has constant second difference (2)) of length 3 over the integers. Known characterizations of integer Büchi sequences of length 3 are actually characterizations over Q, plus some divisibility criterions that keep integer sequences.
AMS Subject Classification: 11D09

Preprint of this article : arXiv:1011.2251

10. The analogue of Büchi's problem for function fields, with A. Shlapentokh (East Carolina University), Journal of Algebra 330-1, pp. 482-506 (2011).
Abstract: Büchi's n Squares Problem asks for an integer M such that any sequence (x_0,...,x_{M-1}), whose second difference of squares is the constant sequence (2) (i.e. x_n^2-2x_{n-1}^2+x_{n-2}^2=2 for all n), satisfies x_n^2=(x+n)^2 for some integer x. Hensley's problem for r-th powers (where r is an integer >1) is a generalization of Büchi's problem asking for an integer M such that, given integers \nu and a, the quantity (\nu+n)^r-a cannot be an r-th power for M or more values of the integer n, unless a=0. The analogues of these problems for rings of functions consider only sequences with at least one non-constant term.
Let K be a function field of a curve of genus g. We prove that Hensley's problem for r-th powers has a positive answer for any r if K has characteristic zero, improving results by Pasten and Vojta. In positive characteristic p we obtain a weaker result, but which is enough to prove that Büchi's problem has a positive answer if p>312g+168 (improving results by Pheidas and the second author).
AMS Subject Classification: 03B25, 11D41, 11U05

Preprint of this article : arXiv:1004.0731

9. A survey on Büchi's problem: new presentations and open problems, with H. Pasten and T. Pheidas, Zapiski POMI 377, pp. 111-140 (2010).
Abstract: In any commutative ring A with unit, Büchi sequences are those sequences whose second difference of squares is the constant sequence (2). Sequences of elements x_n satisfying x_n^2=(x+n)^2 for some fixed x are Büchi sequences that we call trivial. Since we want to study sequences whose elements do not belong to certain subrings (e.g. for fields of rational functions F(z) over a field F we are interested in sequences that are not over F) the concept of trivial sequences may vary. Büchi's Problem for a ring A asks whether there exists a positive integer M such that any Büchi sequence of length M or more is trivial.
We survey the current status of knowledge for Büchi's problem and its analogues for higher-order differences and higher powers. We propose several new and old open problems. We present a few new results and various sketches of proofs of old results (in particular: Vojta's conditional proof for the case of integers and a quite detailed proof for the case of polynomial rings in characteristic zero), and present a new and short proof of the positive answer to Büchi's problem over finite fields with p elements (originally proved by Hensley). We discuss applications to Logic (which were the initial aim for solving these problems).
AMS Subject Classification: 11D09

Article on line : pdf

8. Corrigendum - The analogue of Büchi's problem for rational functions, with T. Pheidas, Journal of the London Mathematical Society 82-1, pp. 273-278 (2010).
AMS Subject Classification: 03C60; 12L05

Preprint of this article : pdf

7. The analogue of Büchi's problem for cubes in polynomials rings, with T. Pheidas (University of Crete-Heraklion), Pacific Journal of Mathematics 238-2, pp. 349-366 (2008).
Abstract: Let F be a field of zero characteristic. We give the following answer to a generalization of a problem of Büchi over F[t]: A sequence of 92 or more cubes in F[t], not all constant, with third difference constant and equal to 6, is of the form (x+n)^3, n=0,...,91, for some polynomial x in F[t] (cubes of successive elements). We use this, in conjunction to the negative answer to the analogue of Hilbert's Tenth Problem for F[t] in order to show that the solvability of systems of degree-one equations, where some of the variables are assumed to be cubes and (or) non-constant, is an unsolvable problem over F[t].
AMS Subject Classification: 03C60, 12L05, 11U05, 11C08

Preprint of this article : pdf

6. The analogue of Büchi's problem for rational functions, with T. Pheidas (University of Crete-Heraklion), Journal of The London Mathematical Society, 74-3, pp. 545-565 (2006).

(this article contains a mistake for positive characteristic - see corrigendum above)

Abstract : Büchi's problem asked whether there exists an integer M such that the surface defined by a system of equations of the form
x_{n}^2+x_{n-2}^2=2x_{n-1}^2+2, n=2,..., M-1,
has no integer points other than those that satisfy |x_n|=|x_0|+n. If answered positively, it would imply that there is no algorithm which decides, given an arbitrary system Q=(q_1,...,q_r) of integral quadratic forms and an arbitrary r-tuple B=(b_1,...,b_r) of integers, whether Q represents B - see T. Pheidas and X. Vidaux, Fund. Math. 185, pp. 171-194 (2005). Thus it would imply the following strengthening of the negative answer to Hilbert's tenth problem: the positive-existential theory of the rational integers in the language of addition and a predicate for the property "x is a square" would be undecidable. Despite some progress, including a conditional positive answer (depending on conjectures of Lang), Büchi's problem remains open.
In this paper we prove the following:
an analogue of Büchi's problem in rings of polynomials of characteristic either 0 or p>16 and for fields of rational functions of characteristic 0; and
an analogue of Büchi's problem in fields of rational functions of characteristic p>18, but only for sequences that satisfy a certain additional hypothesis.
As a consequence we prove the following result in logic.
Let F be a field of characteristic either 0 or at least 17 and let t be a variable. Let L_{t} be the first order language which contains symbols for 0 and 1, a symbol for addition, a symbol for the property "x is a square" and symbols for multiplication by each element of the image of Z[t] in F[t]. Let R be a subring of F(t), containing the natural image of Z[t] in F(t). Assume that one of the following is true:
R is a subset of F[t];
the characteristic of F is either 0 or p>18.
Then multiplication is positive-existentially definable over the ring R, in the language L_t. Hence the positive-existential theory of R in L_{t} is decidable if and only if the positive-existential ring-theory of R in the language of rings, augmented by a constant-symbol for t, is decidable. (Received February 25 2005) (Revised February 13 2006)
AMS Subject Classification: 03C60; 12L05

Preprint of this article : pdf

5. The analogue of Büchi's problem for polynomials, with T. Pheidas (University of Crete-Heraklion), Lecture Notes in Computer Science ISSU 3526, pp. 408-417 (2005).
Abstract: Résumé : Büchi's problem asked whether a surface of a specific type, defined over the rationals, has integer points other than some known ones. A consequence of a positive answer would be the following strengthening of the negative answer to Hilbert's tenth problem: the positive existential theory of the rational integers in the language of addition and a predicate for the property `x is a square' would be undecidable. Despite some progress, including a conditional positive answer (pending on conjectures of Lang), Büchi's problem remains open. In this article we prove an analogue of Büchi's problem in rings of polynomials of characteristic either 0 or p>12. As a consequence we prove the following result in Logic: Let F be a field of characteristic either 0 or >16 and let t be a variable. Let R be a subring of F[t], containing the natural image of Z[t] in F[t]. Let L_{t} be the first order language which contains a symbol for addition in R, a symbol for the property `x is a square in F[t]' and symbols for multiplication by each element of the image of Z[t] in F[t]. Then multiplication is positive-existentially definable over the ring R, in the language L_t. Hence the positive-existential theory of R in L_{t} is decidable if and only if the positive-existential ring-theory of R in the language of rings, augmented by a constant-symbol for t, is decidable.
AMS Subject Classification: 03C60; 12L05

4. Extensions of Büchi's problem : Questions of decidability for addition and “k-th powers”, with T. Pheidas (University of Crete-Heraklion), Fundamenta Mathematicae 185, pp. 171-194 (2005).
Abstract : We generalize a question of Büchi. Let R be an integral domain, C a subring and k>1 an integer. Is there an algorithm to decide the solvability in R of any given system of polynomial equations, each of which is linear in the k−th powers of the unknowns, with coefficients in C?
We state a number-theoretical problem, depending on k, a positive answer to which would imply a negative answer to the question for R = C = Z (where Z stands for the ring of integers).
  We reduce a negative answer for k = 2 and for R = F(t), a field of rational functions of zero characteristic, to the undecidability of the ring theory of F(t).
  We address the similar question, where we allow, along with the equations, also conditions of the form “x is a constant” and “x takes the value 0 at t=0”, for k = 3 and for function fields R = F(t) of zero characteristic, with C = Z[t]. We prove that a negative answer to this question would follow from a negative answer for a ring between Z and the extension of Z by a primitive cube root of unity.
AMS Subject Classification: 03C60; 12L05

Preprint of this article : pdf

3. An analogue of Hilbert's tenth problem for fields of meromorphic functions over non-Archimedean valued fields, Journal of Number Theory 101, Issue 1, pp. 48-73 (2003).
Abstract : Let K be a complete and algebraically closed valued field. We prove that the set of rational integers is positive existentially definable in the field M of meromorphic functions on K in the language L of rings augmented by a constant symbol for the independent variable z and by a symbol for the unary relation “the function x takes the value 0 at 0”. Consequently, we prove that the positive existential theory of M in the language L is undecidable. In order to obtain these results, we obtain a complete characterization of all analytic projective maps (over K) from an elliptic curve E minus a point to E, for any elliptic curve defined over the field of constants.

Preprint of this article : pdf

2. Multiplication complexe et équivalence élémentaire dans le langage des corps, Journal of Symbolic Logic 67 n°2, pp. 635-648 (2002).
Résumé : Soit K et K' deux corps elliptiques avec multiplication complexe sur un corps algébriquement clos k de caractéristique 0, non k-isomorphes, et soit C et C' deux courbes ayant pour corps de fonctions K et K' respectivement. Nous démontrons que si les anneaux d'endomorphismes de C et de C' ne sont pas isomorphes, alors K et K' ne sont pas élémentairement équivalents dans le langage des corps enrichi d'une seule constante (l'invariant modulaire). Ce travail fait suite à un travail de David A. Pierce qui se place dans le langage des k-algèbres.

Preprint of this article : pdf

1. Équivalence élémentaire de corps elliptiques, Comptes Rendus de l'Académie des Sciences de Paris, Série I 330, pp. 1-4 (2000).
Résumé : Il s'agit de démontrer une partie de la conjecture suivante : deux corps elliptiques sur un corps algébriquement clos k sont k-isomorphes si et seulement s'ils sont élémentairement équivalents dans le langage des corps enrichi d'une constante (l'invariant modulaire). C'est une extension des résultats de Duret sur l'équivalence élémentaire des corps de fonctions.

Preprint of this article : pdf


Last time modified : 10th of July, 2021