Joint Advanced Student School - JASS'2007

Polynomials: Their Power and How to Use Them

St. Petersburg, 25.3 - 4.4. 2007

Within the scope of the "Joint Advanced Student School -  JASS'2007" in St. Petersburg (March 25 - April 4), we offer the course "Polynomials: Their Power and How to Use Them".


Prof. Dr. Yu. V. Matiyasevich (Steklov Institute, St. Petersburg)

Prof. Dr. E. W. Mayr (TU München)



D. Chibisov



The course addresses highly motivated and interested students. Active preparation and contribution of the participants will be required. The course language is English. Expenses for travel, board and lodging of german participants are covered by the school.


Application deadline for GERMAN applicants: January 29, 2007. 

Application form: PDF .


German applicants should send their applications to D. Chibisov.
Russian applicants should send their applications to Prof. Dr. Yu. V. Matiyasevich.



Every participant is expected to give a talk and to prepare a paper on the topic of his/her talk. Some help is provided on the organizational stuff page

Course Description:

Constructions in polynomial rings with several variables and coefficients from a field like the rationals or GF(2) play an important role in mathematics, computer science, and engineering. Especially algorithmic questions about polynomials, their roots, and polynomial ideals is an important issue for various applications in cryptography, geometry, robotics, etc. The course is devoted, besides the fundamentals of algorithmic algebra and algorithmic number theory, to decidability and complexity questions in an algebraic setting as well as to recent applications of algorithmic algebra in mathematics and computer science.




Maximilian Butz

Basics about polynomials:

arithmetics with polynomials; complex and real roots of univariate polynomials; field extensions; counting, approximation and isolating of real roots

[1] Chapters 3, 5, 7; [2] Chapters 1, 2, 8, 10; [3] Chapters 1, 2; [6]

Kirill Shmakov

Tarski algorithm with application to  elementary geometry and theorem Proving

[27]; [28]

Anton Bankevich

Cheneralized Chebyshev polynomials:
history and applications of classical  Chebyshev polynomials, generation of tree images on complex plane by generalized  Chebyshev polynomials

[29]; [30]; [31]; [32]

Daria Romanova

Integer Relations among Real Numbers:
LLL algorithm, PSLQ algorithm, and applications of integer relations

[16]; [17]; [18]; [19]; [20]

Lukas Bulwahn

Computing with Polynomials: Hensel Constructions
calculations in Q[x_1, ..., x_n] and Z[x_1, ..., x_n] by inverting morphisms Z[x_1, ..., x_n] -> Z_p[x] via Chinese Remainder Theorem and Hensel lifting, complexity issues

[5] Chapters 5, 6; [4] Chapter 15

Rosa Freund

GCD and factorization of multivariate polynomials

[5] Chapters 7, 8

Johannes Mittmann

Computational problems for polynomial ideals:
Hilbert's Nullstellensatz, Dickson's Lemma, term orderings and reductions,Groebner bases, ideal membership, union and intersection of ideals, common zeros and radical ideals, complexity issues, etc.

[8]; [4] Chapter 21; [5] Chapter 10; [9]

Andreas Würfl

Basic concepts of differential algebra and applicaiton to indefinite integration and solving ODE's with constant coefficients:
differential fields and ideals, field extensions; decidability, connection to Diophantine equations; Risch Algorithm, Louiville Theorem, etc.

[5] Chapters 11, 12; [4] Chapters 22, 23; [25]

Anton Sadovnikov

Polynomials and computers: What we cannot do with polynomials

[26]; [33]; [34]; [35]; [36]

Stephan Ritscher

Computational problems for differential ideals:
infinitness and nonrecursivity of ideals; finitely generated ideals, ideals with finite basis like [x^p], differential orederings and differential reductions; Lee-Brackets, Hall bases for Lee Algebras, Frobenius Theorem and applicaiton to motion controllability

[11]; [12]; [13]; [14]; [15]

Alexey Bogatov

Polynomials in Graph Theory
coloring and counting with polynomials

[37]; [38]; [39];[40];[41]

Inna Lukyanenko

Cryptography and elliptic curves

[22]; [23]; [24]; ...


[1] A. Akritas "Elements of Computer Algebra with Applications ", John Wiley & Sons, 1989
[2] S. Basu, R. Pollack, M.-F. Roy “Algorithms in Real Algebraic Geometry”,  Springer-Verlag, 2003
[3] M. Mignotte, D. Stefanescu “Polynomials. An Algorithmic Approach” , Springer-Verlag, 1999
[4] J. von zur Gathen, J. Gerhard "Modern Computer Algebra", Cambridge Universtiy Press, 1999
[5] K. O. Geddes, S. R. Czapor, G. Labahn "Algorithms for Computer Algebra", Kluwer Academic Publishers, 1992
[6] N. Obreschkoff  “Verteilung und Berechnung der Nullstellen Reeller Polynome”, Berlin, 1963
[7] B. Buchberger, G. E. Collins, R. Loos (eds) "Computer Algebra: Symbolic and Algebraic Computation", Springer-Verlag, 1982
[8] D. A. Cox, J. B. Little, D. O'Shea "Ideals, Varieties, and Algorithms", Springer-Verlag, 1996
[9] E. W. Mayr, A. R. Meyer "The complexity of word problems for commutative semigroups and polynomial ideals", Adv. in Mathematics. 1982
[10] M. Bronstein "Symbolic Integration", Springer-Verlag, 1997
[11] F. Ollivier "Standard bases for differential ideals", LNCS 508, 1990
[12] G. Gallo, B. Mishra, F. Ollivier "Some constructions in rings of differential polynomials", LNCS 539, 1994
[13] G. Carra Ferro "Differential Groebner bases in one variable and in thepartial case", Math. Comput. Modelling, 1997
[14] A. Zobnin "On standard bases in rings of differential polynomials", Journal of Mathematical Sciences, 2006
[15] S. LaValle "Planning Algorithms", Cambridge University Press, 2006
[16] Hastad, Just, Lagarias, Schnorr "Polynomial Time Algorithms for Finding Integer Relations among Real Numbers", SIAM J. Comput., 18 (5), 1989
[17] Lenstra, Lenstra Jr., Lovasz "Factoring Polynomials with Rational Coefficients", Math. Ann. 261, 1982
[18] Helaman, Ferguson, Bailey, Arno "Analysis of PSLQ, An Integer Relation Finding Algorithm", Mathematics of Computation, 69, 1999
[19] D. H. Bailey, J.M. Borwein, N. J. Calkin, R. Girgensohn,  D. R. Luke, and V. H. Moll "Integer Relation Detection." §2.2 in Experimental Mathematics in Action. Natick, MA: A. K. Peters, pp. 29-31, 2006.
[20] Borwein, Lisonek "Applicationos of Integer Relation Algorithms",
[21] Bailey "Integer Relation Detection and Lattice Reduction",
[22] I. Blake, G. Seroussi, N. Smart "Elliptic Curves in Cryptography", CUP, Cambridge, 1999
[23] N. Koblitz "A Course in Number Theory And Cryptography", Springer-Verlag, Berlin, 1994
[24] J. Silverman "The Arithmetic of Elliptic Curves", Springer-Verlag,  Berlin, 1986
[25] M. Rosenlicht "Integration in Finite Terms", Amer. Math. Monthly (79), 1972, pp. 963-972
[26] Yu. Matiyasevich "Enumerable sets are Diophantine", Soviet Math. Dokl. (11), 1970, pp. 279-282
[27] H. Hong "A Simple Algorithm for Real Quantifier Elimination"; http:://
[28] J. H. Davenport, J. Heintz "Real quantifier elimination is doubly exponential", 1998, J. Symb. Comput. 5, 29-35
[29] Shabat, George; Zvonkin, Alexander: "Plane trees and algebraic numbers", in Barcelo, Helene (ed.) et al., Proc. Jerusalem combinatorics '93;
[30] Yu.Matiyasevich "Generalized Chebyshev polynomials";
[31] Yu.Matiyasevich "How to draw a tree correctly";
[32] Pastor, A.V  "Generalized Chebyshev polynomials and Pell-Abel equation", Fundam. Prikl. Mat. 7, No.4, 1123-1145, 2001:
[33] Matiyasevich, Yuri V. Hilbert's tenth problem. With a foreword by Martin Davis. (English), MIT Press Series in the Foundations of Computing. Cambridge, MA: MIT Press. xxii, 264 p.;
[34] Matiyasevich, Yuri V. On Hilbert's 10th Problem;
[35] J.Denef and L.Lipshitz, Power series solutions of algebraic differential equations}, Mathematische Annalen,{ 267}(2), pp.~213--238, 1984.
[36] J. Denef and L. Lipshitz, Decision problems for differential equations, Journal of Symbolic Logic,{\bf 54}(3), pp.~941--950, 1989
[37] Alon, Noga; Tarsi, Michael: A note on graph colorings and graph polynomials. (English), J. Comb. Theory, Ser. B 70, No.1, 197-201 (1997)
[38] Alon, N.; Tarsi, M.: Colorings and orientations of graphs. (English), Combinatorica 12, No.2, 125-134 (1992)
[39] Alon, Noga: Combinatorial Nullstellensatz. (English), J. Comb. Probab. Comput. 8, No.1-2, 7-29 (1999)
[40] Matiyasevich, Yuri: Some probabilistic restatements of the four color conjecture. (English), J. Graph Theory 46, No. 3, 167-179 (2004).
[41] Matiyasevich, Yuri. A Polynomial related to Colorings of Triangulation of Sphere;