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

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 applications 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.

Eligibility: The school will admit 30 outstation and 10 local participants. Research scholars and Net qualified teachers pursuing Ph. D. in algebra are eligible.

Resource person Affiliation Topics
H. Ananthnarayan (HA) IIT Bombay Introduction to Gr ̈obner bases
Indranath Sengupta (IS) IIT Gandhinagar First applications of Gr ̈obner bases
Dilip Patil (DP) IISc, Bangalore Algebraic varieties and and dimension theory
Manoj Kummini (MK) CMI, Chennai Gr ̈obner bases and multivariate splines
S. R. Ghorpade (SRG) IIT Bombay Gr ̈obner bases and coding theory
A. V. Jayanthan (AVJ) IIT Madras Solving polynomial equations using Gr ̈ obner bases
R. Balasubramanian (RB) IIT Bombay Introduction to Cryptography
M. Prem Laxman Das (PLD) SETS, Chennai Gr ̈obner bases and cryptography
Anurag Singh (AS) University of Utah Computation of integral closure of an ideal
Vivek Mukundan (VM) Univ. of Virginia Lab/Tutorial sessions
Clare D’Cruz (SM) CMI, Chennai Lab/Tutorial sessions
Shreedevi Masuti (SM) Univ. of Genoa Lab/Tutorial sessions
Jugal Verma (JKV) IIT Bombay Tutorial sessions
Shameek Paul Ramakrishna Mission Vivekananda Univerisity Labs/Tutorial

  Syllabi of Courses of Lectures and Lab Sessions

Name Lecture Reference
Dilip Patil Basic Algebraic Geometry : Affine and projective varieties, Hilbert’s Nullstellensatz, Noether Normalisation, dimension theory of graded rings and projective and affine
varieties and their computation using Gr ̈obner bases.
 Chapter 1, 8 and 9 of Cox-Little-O’Shea: Ideals, Varieties and Algorithms
  H. Ananthnarayan  Basics of Gr ̈obner bases: monomial orders and initial ideals inthe polynomial ring S = k[x1 , . . . , xn], 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 Buch berger’s algorithm, reduced Gr ̈obner bases.  Chapter 2 of Cox-Little-O’Shea: Ideals, varieties and Algorithms
 
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.  Chapter 2 and 3 of Cox-Little-O’Shea: Ideals, Varieties and Algorithms
 
  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.   D. Cox, J. Little and D. O’Shea: Using Algebraic Geometry.
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. (a) 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/sc401.pdf
(b) D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, 3rd ed.,Springer,2007.
(c) D. Cox, J. Little, D. O’Shea,Using Algebraic Geometry, 2nd ed., Springer,2006.
(d) M. Sala et al (Eds), Gr ̈obner Bases, Coding, and Cryptography, Springer 2009.
 A. V. Jayanthan Solving polynomial equations : Checking consistency of a system of polynomial equations using constructive Nullstellensatz, bounding number of solutions, multi variate Lagrange interpolation, eigenvector theorems, Stickelberger’s Theorem, counting real solutions using quadratic forms.  Chapter 2 of Cox-Little-O’Shea: Using Algebraic Geometry
R. Balasubramanian Introduction to cryptography: Introduction to cryptography, symmetric key: block and stream ciphers, public key: elliptic curve based systems, multivariate cryptosystems, hard problems  
M. Prem Laxman Da Gr ̈obner bases in cryptography: Algebraic attacks on block and stream ciphers, attacks on HFE and multivariate cryptosystems, index calculus attacks on elliptic curves  
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.
First Week:  Laboratory sessions: Computing Gr ̈obner basis, elimination, saturation, com-
puting kernel and image of algebra homomorphisms, division algorithm, computing basis of a
zero-dimensional affine algebra, computation of radicals, colons and intersection of ideals, calcula-
tion of Hilbert series and Hilbert polynomial of a graded algebra, minimal polynomial of algebraic
elements, resultants and discriminants via elimination.
 
 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.  

 Schedule of Lectures and Tutorials

Day Dec 9.00 10.15 11.30 11.45 1.00 2.30 (Tutorial ) 3.30 4.00 Comp. Lab
Mon 11 DP HA Tea IS Lunch

1 (DP, JKV, SM)   2 (HA, IS, SM)
Tue 12 DP HA   IS 3 (HA, JKV, SM) 4 (IS, HA, SM)
Wed 13 DP HA   IS 5 (IS, JKV, SM) 6 (HA, IS, SM)
Thu 14 DP HA   IS 7 (DP, JKV, SM) 8 (IS, HA, SM)
Fri 15 DP HA   IS 9 (HA, JKV, SM) 10 (HA, IS, SM)
Sat 16 DP MK   MK 11 (IS, JKV, SM) 12 (IS, HA, SM)
Sun 17 Delhi Darshan
Mon 18 AVJ MK   RB 13 (MK, HA, AVJ)   14 (MK, CD, AVJ)
Tue 19 AVJ MK   RB 15 (AVJ, HA, MK) 16 (AVJ, CD, MK)
Wed 20 AVJ SRG   RB, PLD, SP) 17 (MK, HA, VM) 18 (MK, CD, VM)
Thu 21 AVJ SRG   PLD 19 (AVJ, HA, VM) 20 (AVJ, CD, VM)
Fri 22 AS SRG   (PLD, CD, SP) 21 (SRG, CD, SP) 22 (SRG, CD, SP)
Sat 23 AS SRG   PLD 23 (AS, JKV, VM) Val function.