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