Polynomial recurrences and cyclic resultants
Authors:
Christopher J. Hillar and Lionel Levine
Journal:
Proc. Amer. Math. Soc. 135 (2007), 16071618
MSC (2000):
Primary 11B37, 14Q99; Secondary 15A15, 20M25
Published electronically:
December 29, 2006
MathSciNet review:
2286068
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be an algebraically closed field of characteristic zero and let . The th cyclic resultant of is Res A generic monic polynomial is determined by its full sequence of cyclic resultants; however, the known techniques proving this result give no effective computational bounds. We prove that a generic monic polynomial of degree is determined by its first cyclic resultants and that a generic monic reciprocal polynomial of even degree is determined by its first of them. In addition, we show that cyclic resultants satisfy a polynomial recurrence of length . This result gives evidence supporting the conjecture of Sturmfels and Zworski that resultants determine . In the process, we establish two general results of independent interest: we show that certain Toeplitz determinants are sufficient to determine whether a sequence is linearly recurrent, and we give conditions under which a linearly recurrent sequence satisfies a polynomial recurrence of shorter length.
 1.
John
H. Conway and Richard
K. Guy, The book of numbers, Copernicus, New York, 1996. MR 1411676
(98g:00004)
 2.
David
Cox, John
Little, and Donal
O’Shea, Ideals, varieties, and algorithms, 2nd ed.,
Undergraduate Texts in Mathematics, SpringerVerlag, New York, 1997. An
introduction to computational algebraic geometry and commutative algebra.
MR
1417938 (97h:13024)
 3.
J.
J. Duistermaat and V.
W. Guillemin, The spectrum of positive elliptic operators and
periodic bicharacteristics, Invent. Math. 29 (1975),
no. 1, 39–79. MR 0405514
(53 #9307)
 4.
Saber
N. Elaydi, An introduction to difference equations, 2nd ed.,
Undergraduate Texts in Mathematics, SpringerVerlag, New York, 1999. MR 1711587
(2001g:39001)
 5.
Graham
Everest and Thomas
Ward, Heights of polynomials and entropy in algebraic
dynamics, Universitext, SpringerVerlag London, Ltd., London, 1999. MR 1700272
(2000e:11087)
 6.
David
Fried, Cyclic resultants of reciprocal polynomials,
Holomorphic dynamics (Mexico, 1986) Lecture Notes in Math.,
vol. 1345, Springer, Berlin, 1988, pp. 124–128. MR 980956
(90h:57004), http://dx.doi.org/10.1007/BFb0081399
 7.
Victor
Guillemin, Wavetrace invariants, Duke Math. J.
83 (1996), no. 2, 287–352. MR 1390650
(97f:58131), http://dx.doi.org/10.1215/S0012709496083118
 8.
Christopher
J. Hillar, Cyclic resultants, J. Symbolic Comput.
39 (2005), no. 6, 653–669. MR 2167674
(2006h:12001), http://dx.doi.org/10.1016/j.jsc.2005.01.001
 9.
A.
Iantchenko, J.
Sjöstrand, and M.
Zworski, Birkhoff normal forms in semiclassical inverse
problems, Math. Res. Lett. 9 (2002), no. 23,
337–362. MR 1909649
(2003f:35284), http://dx.doi.org/10.4310/MRL.2002.v9.n3.a9
 10.
Kiran
S. Kedlaya, Quantum computation of zeta functions of curves,
Comput. Complexity 15 (2006), no. 1, 1–19. MR 2226067
(2007b:14042), http://dx.doi.org/10.1007/s0003700602047
 11.
C.
Krattenthaler, Advanced determinant calculus, Sém.
Lothar. Combin. 42 (1999), Art. B42q, 67 pp. (electronic).
The Andrews Festschrift (Maratea, 1998). MR 1701596
(2002i:05013)
 12.
Ezra
Miller and Bernd
Sturmfels, Combinatorial commutative algebra, Graduate Texts
in Mathematics, vol. 227, SpringerVerlag, New York, 2005. MR 2110098
(2006d:13001)
 13.
K. Purbhoo, A Nullstellensatz For Amoebas, preprint.
 14.
W. H. Stevens, Recursion formulas for some abelian knot invariants, Journal of Knot Theory and Its Ramifications, Vol. 9, No. 3 (2000) 413422.
 15.
D. Zeilberger, Dodgson's determinantevaluation rule proved by twotiming men and women, Elec. J. Comb. 4(2), 1997.
 1.
 J. H. Conway and R. Guy, The Book of Numbers, SpringerVerlag, 1996. MR 1411676 (98g:00004)
 2.
 D. Cox, J. Little, and D. O'Shea, Ideals, varieties, and algorithms, second ed., Undergraduate Texts in Mathematics, SpringerVerlag, New York, 1997.MR 1417938 (97h:13024)
 3.
 J.J. Duistermaat and V. Guillemin, The spectrum of positive elliptic operators and periodic bicharacteristics, Inv. Math. 25 (1975) 3979.MR 0405514 (53:9307)
 4.
 S. Elaydi, An Introduction to Difference Equations, Springer, 1999.MR 1711587 (2001g:39001)
 5.
 G. Everest and T. Ward. Heights of Polynomials and Entropy in Algebraic Dynamics. SpringerVerlag London, Ltd., London, 1999. MR 1700272 (2000e:11087)
 6.
 D. Fried, Cyclic resultants of reciprocal polynomials, in Holomorphic Dynamics (Mexico 1986), Lecture Notes in Math. 1345, SpringerVerlag, 1988, 124128. MR 0980956 (90h:57004)
 7.
 V. Guillemin, Wave trace invariants, Duke Math. J. 83 (1996), 287352.MR 1390650 (97f:58131)
 8.
 C. Hillar, Cyclic resultants, J. Symb. Comp. 39 (2005), 653669; erratum 40 (2005), 11261127.MR 2167674
 9.
 A. Iantchenko, J. Sjöstrand, and M. Zworski, Birkhoff normal forms in semiclassical inverse problems, Math. Res. Lett. 9 (2002), 337362.MR 1909649 (2003f:35284)
 10.
 K. Kedlaya, Computational Complexity 15 (2006), 119. MR 2226067
 11.
 C. Krattenthaler, ``Advanced Determinant Calculus,'' Sem. Lothar. Combin. 42 (1999), Art. B42q. MR 1701596 (2002i:05013)
 12.
 E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Springer, 2004.MR 2110098 (2006d:13001)
 13.
 K. Purbhoo, A Nullstellensatz For Amoebas, preprint.
 14.
 W. H. Stevens, Recursion formulas for some abelian knot invariants, Journal of Knot Theory and Its Ramifications, Vol. 9, No. 3 (2000) 413422.
 15.
 D. Zeilberger, Dodgson's determinantevaluation rule proved by twotiming men and women, Elec. J. Comb. 4(2), 1997.
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
11B37,
14Q99,
15A15,
20M25
Retrieve articles in all journals
with MSC (2000):
11B37,
14Q99,
15A15,
20M25
Additional Information
Christopher J. Hillar
Affiliation:
Department of Mathematics, Texas A & M University, College Station, TX 77843
Email:
chillar@math.tamu.edu
Lionel Levine
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720
Email:
levine@math.berkeley.edu
DOI:
http://dx.doi.org/10.1090/S0002993906086722
PII:
S 00029939(06)086722
Keywords:
Cyclic resultants,
linear recurrence,
polynomial recurrence,
semigroup algebra,
Toeplitz determinant,
topological dynamics,
Vandermonde determinant
Received by editor(s):
November 23, 2004
Received by editor(s) in revised form:
February 8, 2006
Published electronically:
December 29, 2006
Additional Notes:
Both authors were supported under a NSF Graduate Research Fellowship.
Communicated by:
Bernd Ulrich
Article copyright:
© Copyright 2006
American Mathematical Society
