The diophantine problem for addition and divisibility for subrings of rational functions over finite fields
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-03-0045Keywords:
Positive-existential definability, Finite field of odd characteristicAbstract
It is shown that the positive existential theory of the structure ℱS = (S−1F[t];=,F, 0, 1,+, |, f ↦ tf), where f ↦ tf is the multiplication by t map, S is non-empty a finite set of irreducible polynomials, and F is a finite field of odd characteristic, is undecidable.
References
A. P. Beltyukov, “Decidability of the universal theory of natural numbers with addition and divisibility”, Journal of soviet mathematics, vol. 14, no. 5, pp. 1436–1444, Nov. 1980, doi: 10.1007/BF01693974
L. Cerda-Romero and C. Martínez-Ranero, “The diophantine problem for addition and divisibility over subrings of the rationals”, The journal of symbolic logic, vol. 82, no. 3, pp. 1140–1149, Sep. 2017, doi: 10.1017/jsl.2016.64
A. C. Pheidas, “The diophantine problem for addition and divisibility in polynomial rings (Decidability, undecidability)”, Ph. D. Thesis, Purdue University, 1985. [On line]. Available: https://bit.ly/3cruCUp
T. Pheidas, “Diophantine undecidability for addition and divisibility in polynomial rings”, Fundamenta mathematicae, vol. 182, no. 3, pp. 205–220, 2004, doi: 10.4064/fm182-3-2
H. Kornblum and E. Landau, “Über die primfunktionen in einer arithmetischen progression”, Mathematische zeitschrift, vol. 5, no. 1-2, pp. 100–111, Mar. 1919, doi: 10.1007/BF01203156
H. W. Lenstra, “On Artins conjecture and Euclids algorithm in global fields”, Inventiones mathematicae, vol. 42, no. 1, pp. 201–224, 1977, doi: 10.1007/BF01389788
L. Lipshitz, “Undecidable existential problems for addition and divisibility in algebraic number rings. II”, Proceedings of the American Mathematical Society, vol. 64, no. 1, pp. 122–128, Jan. 1977, doi: 10.1090/S0002-9939-1977-0536659-5
L. Lipshitz, “The Diophantine problem for addition and divisibility”, Transactions of the American Mathematical Society, vol. 235, pp. 271–283, 1978, doi: 10.1090/S0002-9947-1978-0469886-1
L. Lipshitz, “Undecidable existential problem for addition and divisibility in algebraic number rings”, Transactions of the American Mathematical Society, vol. 241, pp. 121-128, 1978, doi: 10.1090/S0002-9947-1978-0536658-9
J. Robinson, “Definability and decision problems in arithmetic”, Journal of symbolic logic, vol. 14, no. 2, pp. 98–114, Jun. 1949, doi: 10.2307/2266510
Published
How to Cite
Issue
Section
Copyright (c) 2020 Leonidas Antonio Cerda-Romero, Carlos Martínez-Ranero
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
