Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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 $ \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 [Enhancements On Off] (What's this?)

  • 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.

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: 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.

American Mathematical Society