On an exponential predicate in polynomials over finite fields
Author:
Alla Sirokofskich
Journal:
Proc. Amer. Math. Soc. 138 (2010), 25692583
MSC (2000):
Primary 03C10, 03B25, 12L05
Published electronically:
February 18, 2010
MathSciNet review:
2607887
Fulltext 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 modelcomplete 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
(94j:03001)
 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
(58 #10809), 10.1090/S00029947197804915837
 3.
J.
Denef, The Diophantine problem for polynomial rings of positive
characteristic, Logic Colloquium ’78 (Mons, 1978) Stud. Logic
Foundations Math., vol. 97, NorthHolland, AmsterdamNew York, 1979,
pp. 131–145. MR 567668
(81h:03090)
 4.
L.
Lipshitz, The Diophantine problem for addition
and divisibility, Trans. Amer. Math. Soc.
235 (1978),
271–283. MR 0469886
(57 #9666), 10.1090/S00029947197804698861
 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
(2002a:03085), 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
(2006c:03020), 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
(2009e:03006)
 8.
Bjorn
Poonen, Undecidability in number theory, Notices Amer. Math.
Soc. 55 (2008), no. 3, 344–350. MR 2382821
(2008m:11238)
 9.
Raphael
M. Robinson, Undecidable rings, Trans. Amer. Math. Soc. 70 (1951), 137–159. MR 0041081
(12,791b), 10.1090/S00029947195100410810
 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
(84a:03074)
 11.
A. Semenov, Logical theories of oneplace functions on the set of natural numbers, Math. USSR Izvestija 22 (1984), 587618.
 12.
A. Sirokofskich, Decidability of Subtheories of Polynomials over a Finite Field, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, Springer (2009), 437446.
 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), 391399. MR 0491583 (58:10809)
 3.
 J. Denef, The diophantine problem for polynomial rings of positive characteristic, Logic Colloquium '78, North Holland (1984), 131145. MR 567668 (81h:03090)
 4.
 L. Lipshitz, The diophantine problem for addition and divisibility, Transactions of the American Mathematical Society 235 (1978), 271283. 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), 49106. 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), 10061026. 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), 207236. MR 2446305 (2009e:03006)
 8.
 B. Poonen, Undecidability in number theory, Notices of the American Mathematical Society 55 (2008), no. 3, 344350. MR 2382821 (2008m:11238)
 9.
 R. Robinson, Undecidable rings, Transactions of the American Mathematical Society 70 (1951), 137159. MR 0041081 (12:791b)
 10.
 A. Semenov, On the definability of arithmetic in its fragments, Soviet Math. Dokl. 25 (1982), 300303. MR 647548 (84a:03074)
 11.
 A. Semenov, Logical theories of oneplace functions on the set of natural numbers, Math. USSR Izvestija 22 (1984), 587618.
 12.
 A. Sirokofskich, Decidability of Subtheories of Polynomials over a Finite Field, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, Springer (2009), 437446.
Similar Articles
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:
http://dx.doi.org/10.1090/S0002993910102585
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.
