On an exponential predicate in polynomials over finite fields

Author:
Alla Sirokofskich

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

MSC (2000):
Primary 03C10, 03B25, 12L05

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

Published electronically:
February 18, 2010

MathSciNet review:
2607887

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the theory of the set of polynomials in , where is a finite field, in a language including addition and a predicate for the relation `` is a power of '' is model-complete and therefore decidable.

**1.**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****2.**J. Denef,*The Diophantine problem for polynomial rings and fields of rational functions*, Trans. Amer. Math. Soc. 242 , posted on (1978), 391–399. MR**0491583**, https://doi.org/10.1090/S0002-9947-1978-0491583-7**3.**J. Denef,*The Diophantine problem for polynomial rings of positive characteristic*, Logic Colloquium ’78 (Mons, 1978) Stud. Logic Foundations Math., vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 131–145. MR**567668****4.**L. Lipshitz,*The Diophantine problem for addition and divisibility*, Trans. Amer. Math. Soc.**235**(1978), 271–283. MR**0469886**, https://doi.org/10.1090/S0002-9947-1978-0469886-1**5.**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**, https://doi.org/10.1090/conm/270/04369**6.**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**, https://doi.org/10.2178/jsl/1102022210**7.**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****8.**Bjorn Poonen,*Undecidability in number theory*, Notices Amer. Math. Soc.**55**(2008), no. 3, 344–350. MR**2382821****9.**Raphael M. Robinson,*Undecidable rings*, Trans. Amer. Math. Soc.**70**(1951), 137–159. MR**0041081**, https://doi.org/10.1090/S0002-9947-1951-0041081-0**10.**A. L. Semenov,*On the definability of arithmetic in its fragments*, Dokl. Akad. Nauk SSSR**263**(1982), no. 1, 44–47 (Russian). MR**647548****11.**A. Semenov,*Logical theories of one-place functions on the set of natural numbers*, Math. USSR Izvestija**22**(1984), 587-618.**12.**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.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
03C10,
03B25,
12L05

Retrieve articles in all journals with MSC (2000): 03C10, 03B25, 12L05

Additional Information

**Alla Sirokofskich**

Affiliation:
Department of Mathematics, University of Crete, 714 09 Heraklion, Greece

Email:
asirokof@math.uoc.gr

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

Received by editor(s):
May 6, 2009

Received by editor(s) in revised form:
October 19, 2009

Published electronically:
February 18, 2010

Additional Notes:
This work was supported by the Trimester Program on Diophantine Equations, January–April 2009, at the Hausdorff Research Institute for Mathematics, Bonn, Germany

Communicated by:
Julia Knight

Article copyright:
© Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.