AIS/IST Gröbner Bases and their Applications (2017)

A Gr ̈obner basis is a set of multivariate polynomials that has several algorithmic properties. Any set of polynomials can be transformed into a Gr ̈obner basis. Gr ̈obner bases have been used in several ap-
plications such as solving equations, graph theory, optimization, cryptography, coding theory, robotics,control theory, statistics and automatic geometric theorem proving, to name a few. This workshop aims
to introduce some of these applications after covering basics of this beautiful theory. The pre-requisites are linear algebra and a basic course in abstract algebra.

Syllabi of Courses of Lectures and Lab Sessions

1. Dilip Patil : Basic Algebraic Geometry: Affine and projective varieties, Hilbert’s Nullstel-lensatz, Noether Normalisation, dimension theory of graded rings and projective and affine varieties and their computation using Gr ̈obner bases.
   Reference: Chapter 1, 8 and 9 of Cox-Little-O’Shea: Ideals, Varieties and Algorithms
2. H. Ananthnarayan : Basics of Gr ̈obner bases: monomial orders and initial ideals in the polynomial ring S = k[x₁ , . . . , x_n ], where k is a field, important examples of monomial orderings and their basic properties, Dickson’s Lemma and Hilbert basis Theorem, using initial ideals to find k-basis for S/I, where I is an ideal in S, division algorithm in S, and Buchberger’s algorithm,reduced Gr ̈ obner bases.
   Reference: Chapter 2 of Cox-Little-O’Shea: Ideals, varieties and Algorithms
3. Indranath Sengupta : First applications of Gr ̈obner Bases: Elimination, computing kernel and image of a polynomial map of affine algebras, resultants, computation of radicals, intersection,colon and saturation of ideals, geometric meaning of elimination, minimal polynomials of algebraic elements over a field.
   Reference: Chapter 2 and 3 of Cox-Little-O’Shea: Ideals, Varieties and Algorithms
4. Manoj Kummini: Multivariate polynomial splines: Recent applications of Gr ́obner bases to the problem of construction and anaysis of piecewise polynomial splines with specified degree of smoothness. Gr ̈obner bases of modules over polynomial rings will be used in these applications. In particular Schreyer’s algorithm will be discussed for computing syzygies. A conjecture of Strang about dimension of the vector space of C r functions on polyhedral complexes will be discussed.
   Reference: D. Cox, J. Little and D. O’Shea: Using Algebraic Geometry.
5. Sudhir R. Ghorpade : Gr ̈obner bases and coding theory: Basics of error-correcting codes,cyclic codes, Reed-Solomon code, Reed-Muller codes, Applications of Gr ̈obner bases to determining the minimum distance of Reed-Muller type codes, Footprint bound, Some recent results.
   References:
   • C. Carvalho, Applications of results from commutative algebra to the study of certain evaluation codes, Lecture notes of CIMPA Research School on Algebraic Methods in Coding Theory,Sao Paulo, Brazil, July 2017. https : //www.ime.usp.br/ cimpars/notes/sc40 1.pdf
   • D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, 3rd ed., Springer, 2007.
   • D. Cox, J. Little, D. O’Shea,Using Algebraic Geometry, 2nd ed., Springer, 2006.
   • M. Sala et al (Eds), Gr ̈obner Bases, Coding, and Cryptography, Springer 2009.
6. A. V. Jayanthan: Solving polynomial equations : Checking consistency of a system of polynomial equations using constructive Nullstellensatz, bounding number of solutions, multivariate Lagrange interpolation, eigenvector theorems, Stickelberger’s Theorem, counting real solutions using quadratic forms.
   Reference: Chapter 2 of Cox-Little-O’Shea: Using Algebraic Geometry
7. R. Balasubramanian: Introduction to cryptography: Introduction to cryptography, symmetric key: block and stream ciphers, public key: elliptic curve based systems, multivariate cryptosystems, hard problems
8. M. Prem Laxman Das: Gr ̈obner bases in cryptography: Algebraic attacks on block and stream ciphers, attacks on HFE and multivariate cryptosystems, index calculus attacks on elliptic curves
9. Anurag Singh: Computation of integral closure of ideals: An algorithm for computation of integral closure of ideals will be explained.
   Reference: Anurag K. Singh and Irena Swanson, An algorithm for computing the integral closure.Algebra and Number Theory 3 (2009), no. 5, 587–595.
10. First Week: Laboratory sessions: Computing Gr ̈obner basis, elimination, saturation, computing kernel and image of algebra homomorphisms, division algorithm, computing basis of a zero-dimensional affine algebra, computation of radicals, colons and intersection of ideals, calculation of Hilbert series and Hilbert polynomial of a graded algebra, minimal polynomial of algebraic elements, resultants and discriminants via elimination.
11. Second Week: Laboratory sessions: Solving polynomial equations, computing integral closure of ideals, computing splines, computing sygygies and free resolutions, cryptosystems, construction
    of codes using Gr ̈obner bases.

 
Time Table

How to reach

Indraprastha Institute of Information Technology, Delhi (IIIT-Delhi) campus is located in Okhla, near Nehru Place, New Delhi.

To reach the campus, coming from Nehru Place on outer ring road, follow these directions:

• After about half KM, turn Right from under the first flyover (it is oneway).
• After about 300 m, turn Left from under the Govind Puri Metro station (there is a IIITD sign at this turn).
• After about 300 m, there will be a 'Y' - take the left road of the 'Y'.
• Follow signs for IIIT-D - the main gate is after about 500 m.