|
On an exponential predicate in polynomials over finite fields
Author(s):
Alla
Sirokofskich
Journal:
Proc. Amer. Math. Soc.
138
(2010),
2569-2583.
MSC (2000):
Primary 03C10, 03B25, 12L05
Posted:
February 18, 2010
MathSciNet review:
2607887
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show that the theory of the set of polynomials in ![$ \mathbb{F}_q[t]$](/proc/2010-138-07/S0002-9939-10-10258-5/gif-abstract0/img1.gif) , 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.
References:
-
- 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:
10.1090/S0002-9939-10-10258-5
PII:
S 0002-9939(10)10258-5
Received by editor(s):
May 6, 2009,
Received by editor(s) in revised form:
October 19, 2009
Posted:
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
Copyright of article:
Copyright
2010,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
