Notes on the decidability of addition and the Frobenius map for polynomials and rational functions

Let pbe a prime number, Fp a finite field with pelements, Fan algebraic extension of Fp and z a variable. We consider the structure of addition and the Frobenius map (i.e., x →x^p) in the polynomial rings F[z] and in fields F(z) of rational functions. We prove that any question about F[z] in the structure of addition and Frobenius map may be effectively reduced to questions about the similar structure of the field F. Furthermore, we provide an example which shows that a fact which is true for addition and the Frobenius map in the polynomial rings F[z] fails to be true in F(z). As a consequence, certain methods used to prove model completeness for polynomials do not suffice to prove model completeness for similar structures for fields of rational functions F(z), a problem that remains open even for F= Fp.

Primary 03B25, 12L05, Secondary 03C10, 03C60, 13A35, 13L05.

[1] L. Cerda-Romero and C. Martinez-Ranero, The diophantine problem for addition and divisibility for subrings of rational functions over finite fields, Proyecciones 39:3 (2020), 721-736.

[2] G. L. Cherlin, Undecidability of rational function fields in nonzero characteristic, in: Logic Colloquium '82, ser. Studies in Logic and the Foundations of Mathematics vol. 112, G. Lolli, G. Longo, and A. Marcja (Eds.), Elsevier, 1984, pp. 85-95.

[3] Y. Ershov, Undecidability of certain fields, Dokl. Akad. Nauk SSSR 161 (1965), 27-29.

[4] E. Hrushovski, The elementary theory of the Frobenius automorphisms, arXiv math/0406514, 2004.

[5] J. Koenigsmann, Decidability in local and global fields, in: Proceedings of the International Congress of Mathematicians (ICM 2018), World Scientific Publishers, 2018, pp. 45-59.

[6] C. Martinez-Ranero, J. Utreras, and X. Vidaux, Existential decidability for addition and divisibility in holomorphy subrings of global fields, arXiv 2010.14024, 2020.

[7] G. Onay, Fp((x)) is decidable as a module over the ring of additive polynomials, arXiv 1806.03123, 2018.

[8] Y. G. Penzin, The undecidability of fields of rational functions over fields of characteristic 2, Algebra and Logic 12 (1973), 205-210.

[9] T. Pheidas, The diophantine problem for addition and divisibility in polynomial rings (decidability, undecidability), Ph.D. dissertation, Purdue University, 1985.

[10] T. Pheidas, Hilbert's tenth problem for fields of rational functions over finite fields, Inventiones mathematicae 103:1 (1991), 1-8.

[11] T. Pheidas, Endomorphisms of elliptic curves and undecidability in function fields of positive characteristic, Journal of Algebra 273:1 (2004), 395-411.

[12] T. Pheidas and K. Zahidi, Undecidability of existential theories of rings and fields: a survey, Contemporary mathematics - American Mathematical Society 270 (2000), 49-105.

[13] T. Pheidas and K. Zahidi, Elimination theory for addition and the Frobenius map in polynomial rings, Journal of Symbolic Logic 69:4 (2004), 1006-1026.

[14] T. Pheidas and K. Zahidi, Decision problems in algebra and analogues of hilbert's tenth problem, in: Model theory with Applications to Algebra and Analysis, Cambridge University Press, 2008, pp. 207-236.

[15] B. Poonen, Undecidability in number theory, Notices of the American Mathematical Society 55 (2008), 344-350.

[16] A. Shlapentokh, Hilbert's tenth problem for rings of algebraic functions in one variable over fields of constants of positive characteristic, Transactions of the American Mathematical Society 333:1 (1992), 275-298.

[17] A. Sirokofrkich, On an exponential predicate in polynomials over finite fields, Proceedings of the American Mathematical Society 138:7 (2010), 2569-2583.

[18] C. Videla, Hilbert's tenth problem for rational function fields in characteristic 2, Proceedings of the American Mathematical Society 120:1 (1994), 249-253.