On an exponential predicate in polynomials over finite fields

Sirokofskich, Alla

doi:10.1090/S0002-9939-10-10258-5

On an exponential predicate in polynomials over finite fields
HTML articles powered by AMS MathViewer

by Alla Sirokofskich

Proc. Amer. Math. Soc. 138 (2010), 2569-2583

DOI: https://doi.org/10.1090/S0002-9939-10-10258-5

Published electronically: February 18, 2010

PDF | Request permission

Abstract:

We show that the theory of the set of polynomials in $\mathbb {F}_q[t]$, where $\mathbb {F}_q$ is a finite field, in a language including addition and a predicate for the relation “$x$ is a power of $t$” is model-complete and therefore decidable.

References

Martin D. Davis, Ron Sigal, and Elaine J. Weyuker, Computability, complexity, and languages, 2nd ed., Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1994. Fundamentals of theoretical computer science. MR 1257183
J. Denef, The Diophantine problem for polynomial rings and fields of rational functions, Trans. Amer. Math. Soc. 242 (1978), 391–399. MR 0491583, DOI 10.1090/S0002-9947-1978-0491583-7
J. Denef, The Diophantine problem for polynomial rings of positive characteristic, Logic Colloquium ’78 (Mons, 1978) Studies in Logic and the Foundations of Mathematics, vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 131–145. MR 567668
L. Lipshitz, The Diophantine problem for addition and divisibility, Trans. Amer. Math. Soc. 235 (1978), 271–283. MR 469886, DOI 10.1090/S0002-9947-1978-0469886-1
Thanases Pheidas and Karim Zahidi, Undecidability of existential theories of rings and fields: a survey, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999) Contemp. Math., vol. 270, Amer. Math. Soc., Providence, RI, 2000, pp. 49–105. MR 1802009, DOI 10.1090/conm/270/04369
Thanases Pheidas and Karim Zahidi, Elimination theory for addition and the Frobenius map in polynomial rings, J. Symbolic Logic 69 (2004), no. 4, 1006–1026. MR 2135654, DOI 10.2178/jsl/1102022210
Zoé Chatzidakis, Dugald Macpherson, Anand Pillay, and Alex Wilkie (eds.), Model theory with applications to algebra and analysis. Vol. 2, London Mathematical Society Lecture Note Series, vol. 350, Cambridge University Press, Cambridge, 2008. MR 2446305
Bjorn Poonen, Undecidability in number theory, Notices Amer. Math. Soc. 55 (2008), no. 3, 344–350. MR 2382821
Raphael M. Robinson, Undecidable rings, Trans. Amer. Math. Soc. 70 (1951), 137–159. MR 41081, DOI 10.1090/S0002-9947-1951-0041081-0
A. L. Semenov, On the definability of arithmetic in its fragments, Dokl. Akad. Nauk SSSR 263 (1982), no. 1, 44–47 (Russian). MR 647548
A. Semenov, Logical theories of one-place functions on the set of natural numbers, Math. USSR Izvestija 22 (1984), 587-618.
A. Sirokofskich, Decidability of Sub-theories of Polynomials over a Finite Field, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, Springer (2009), 437-446.