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.**M. Davis, R. Sigal, and E. J. Weyuker,*Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.)*, Academic Press Professional, Inc. (1994). MR**1257183 (94j:03001)****2.**J. Denef,*The diophantine problem for polynomial rings and fields of rational functions*, Transactions of the American Mathematical Society**242**(1978), 391-399. MR**0491583 (58:10809)****3.**J. Denef,*The diophantine problem for polynomial rings of positive characteristic*, Logic Colloquium '78, North Holland (1984), 131-145. MR**567668 (81h:03090)****4.**L. Lipshitz,*The diophantine problem for addition and divisibility*, Transactions of the American Mathematical Society**235**(1978), 271-283. MR**0469886 (57:9666)****5.**T. Pheidas and K. Zahidi,*Undecidability of existential theories of rings and fields: A survey*, Contemporary Mathematics, 270, Amer. Math. Soc. (2000), 49-106. MR**1802009 (2002a:03085)****6.**T. Pheidas and K. Zahidi,*Elimination theory for addition and the Frobenius map in polynomial rings*, Journal of Symbolic Logic**69**, no. 4 (2004), 1006-1026. MR**2135654 (2006c:03020)****7.**T. Pheidas and K. Zahidi,*Analogues of Hilbert's tenth problem*, Model Theory with Applications to Algebra and Analysis, Vol. 2 (Eds. Zoe Chatzidakis, Dugald Macpherson, Anand Pillay, Alex Wilkie), London Math Soc. Lecture Note Series, 350, Cambridge University Press (2008), 207-236. MR**2446305 (2009e:03006)****8.**B. Poonen,*Undecidability in number theory*, Notices of the American Mathematical Society**55**(2008), no. 3, 344-350. MR**2382821 (2008m:11238)****9.**R. Robinson,*Undecidable rings*, Transactions of the American Mathematical Society**70**(1951), 137-159. MR**0041081 (12:791b)****10.**A. Semenov,*On the definability of arithmetic in its fragments*, Soviet Math. Dokl.**25**(1982), 300-303. MR**647548 (84a:03074)****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.