Proving Combinatorial Identities

Solving Recurrence Equations

Buchberger's Algorithm

Solving Sudoku with Gröbner bases

Rothstein-Trager's Algorithm

Exponential Extension

Sister Celine's Algorithm

Harmonic Number Identities

Reduced Gröbner Bases

Integer Relation Algorithms

Resultants

Gosper's Algorithm

Polynomial Ideals

More on Buchberger's Algorithm

Online Mathematical Tools

Computing Resultants

Wilf-Zeilberger's Algorithm

Monomial Order

Applications of Gröbner bases in geometry

Differential Algebra

Sylvester Matrix

Zeilberger's Algorithm

Monomial Ideals

Lagrange Multipliers

Squarefree Factorization

Rioboo's Algorithm

Wolfram Language

Petkovsek's Algorithm

Gröbner Bases

Graph Coloring with Gröbner bases

Hermite-Ostrogradsky's Algorithm

Logarithmic Extension

15-355 Modern Computer Algebra Carnegie Mellon University Spring 2012 This course explores the relationship between algebra and computation, focusing on algorithms used for symbolic computation and modern algebra concepts. Subjects covered include proving combinatorial identities, Gröbner bases, symbolic integration, and experimental mathematics. Prerequisites suggest this is a mid-level course. The goal of this course is to investigate the relationship between algebra and computation. The course is designed to expose students (sophomore/junior cs and math majors) to algorithms used for symbolic computation, as well as to the concepts from modern algebra which are applied to the development of these algorithms. This course provides a hands-on introduction to many of the most important ideas used in symbolic mathematical computation, which involves sproving combinatorial identities, solving system of polynomial equations, analytic integration, and solving linear difference equations.

The appropriate use of computer algebra systems (Mathematica) to support the teaching and learning of mathematics, and in related assessments, is incorporated throughout the course. This includes the use of Mathematica to assist in the development of mathematical ideas and concepts, as well as a tool for analysis, problem-solving and modelling work.

The course covers the following topics:

- **Proving Combinatorial Identities**
    What do you get when you add a couple of math professors, a Roman Catholic nun, and a computer? Wilf and Zeilberger have shown that computers can prove a certain class of combinatorial identities instantly and infallibly.
- **Gröbner Bases**
    A Gröbner basis for a system of polynomials possesses a property that the set of polynomials in a Gröbner basis have the same collection of roots as the original polynomials. Therefore, Gröbner bases are very useful for solving polynomial equations by elimination of variables.
- **Symbolic Integration**
    We will describe algorithms to the problem of indefnite integration in finite terms. While the problem was formulated and studied by Abel and Liouville, only within the last 20 years the practical algorithms have been developed and implemented in the major computer algebra systems.
- **Experimental mathematics**
    We will start with an introduction to experimental mathematics and what it is role in modern applied mathematics. We will cover a few modern tools, techniques and algorithms including inverse symbolic calculator and lattice basis reduction algorithm. Learning Outcomes:

- understanding major algorithms of symbolic computation
- understanding some algorithms of experimental mathematics
- understanding main ideas of a computer-asisted proof
- understanding major algorithms for automated proving combinatorial identities
- understanding Groebner bases algorithms in the context of automated theorem provers
- understanding major tools for experimental mathematics and their use in modelling and discovery mathematical results [15-251](http://www.cs.cmu.edu/~15251/) Optional Textbook:
 
- J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2nd edition, 2003.
- M. Petkovsek, H. Wilf, D. Zeilberger, A = B, Algorithms and Computations in Mathematics, AK Peters, 1996.
- D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms, 2nd ed., Springer-Verlag, 1996.
- M. Bronstein, Symbolic Integration - Transcendental Functions, 2nd edition, Vol 1, Springer-Verlag, 2005.
- J. Borwein,D, Bailey, Mathematics by Experiment: Plausible Reasoning in the 21st Century, AK Peters Ltd, 2003.
- J. S. Cohen, Computer Algebra and Symbolic Computation: Mathematical Methods , AK Peters Ltd, 2003.

15-355 Modern Computer Algebra

Theoretical Computer Science

Combinatorial proof

Proving Combinatorial Identities

1 courses cover this concept

15-355 Modern Computer Algebra