Notes on the decidability of addition and the Frobenius map for polynomials and rational functions
Choose format
RIS BIB ENDNOTENotes on the decidability of addition and the Frobenius map for polynomials and rational functions
Publication date: 28.11.2022
Reports on Mathematical Logic, 2022, Number 57, pp. 53-60
https://doi.org/10.4467/20842589RM.22.004.16661Authors
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 →xp) 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.
[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.
Information: Reports on Mathematical Logic, 2022, Number 57, pp. 53-60
Article type: Original article
University of Crete, Department of Mathematics & Applied Mathematics
University of Crete, Department of Mathematics & Applied Mathematics
University of Crete, Department of Mathematics & Applied Mathematics
Published at: 28.11.2022
Received at: 09.12.2021
Article status: Open
Licence: CC BY
Percentage share of authors:
Classification number:
Article corrections:
-Publication languages:
EnglishView count: 780
Number of downloads: 445