Xavier VIDAUX

PUBLICATIONS

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

14. 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

13. 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

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

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

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

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

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

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

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

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.