CS6842 - Algorithmic Algebra

Meetings  

• Theme 1 : Why this course? - 1 meetings

  • Meeting 01 : Tue, Jan 20, 11:00 am-11:50 am - Jayalal Sarma M N

  Motivation for Polynomial Identity Testing (PIT): Perfect matching problem and Primality testing

  References
  Exercises
  Reading

  Motivation for Polynomial Identity Testing (PIT): Perfect matching problem and Primality testing
  

  References:

  None

• Theme 2 : Gröbner bases - 17 meetings

  • Meeting 02 : Wed, Jan 21, 10:00 am-10:50 am - Jayalal Sarma M N

  Motivation for checking consistency of system of Polynomial equations: 3-coloring problem

  References
  Exercises
  Reading

  Motivation for checking consistency of system of Polynomial equations: 3-coloring problem
  

  References:

  None

  • Meeting 03 : Thu, Jan 22, 08:00 am-08:50 am - Harshil M.

  Fields, rings, polynomial rings, ideals

  References
  Exercises
  Reading

  Fields, rings, polynomial rings, ideals
  

  References:

  None

  • Meeting 04 : Fri, Jan 23, 02:00 pm-02:50 pm - Harshil M.

  Basis/Generating set of ideals, variety, Ideal membership problem and its relation with checking consistency of system of polynomial equations

  References
  Exercises
  Reading

  Basis/Generating set of ideals, variety, Ideal membership problem and its relation with checking consistency of system of polynomial equations
  

  References:

  None

  • Meeting 05 : Tue, Jan 27, 11:00 am-11:50 am - Harshil M.

  Gaussian elimination and Euclidean division algorithm for special cases of linear and univariate polynomials, and viewing them as producing a new basis, identifying common features like ordering on monomials and use of leading terms

  References
  Exercises
  Reading

  Gaussian elimination and Euclidean division algorithm for special cases of linear and univariate polynomials, and viewing them as producing a new basis, identifying common features like ordering on monomials and use of leading terms
  

  References:

  None

  • Meeting 06 : Wed, Jan 28, 10:00 am-10:50 am - Harshil M.

  Ideal membership problem for univariate polynomials, and an initial understanding of `nice' basis as a basis such that checking remainder upon division by its polynomials is enough to solve ideal membership problem

  References
  Exercises
  Reading

  Ideal membership problem for univariate polynomials, and an initial understanding of `nice' basis as a basis such that checking remainder upon division by its polynomials is enough to solve ideal membership problem
  

  References:

  None

  • Meeting 07 : Thu, Jan 29, 08:00 am-08:50 am - Harshil M.

  Understanding what form of expression should a multivariate multidivisor algorithm be expected to output, and accordingly understanding `nice' basis as one with unique r property (i.e., w.r.t. which, all such expressions of a polynomial share a certain common part)

  References
  Exercises
  Reading

  Understanding what form of expression should a multivariate multidivisor algorithm be expected to output, and accordingly understanding `nice' basis as one with unique r property (i.e., w.r.t. which, all such expressions of a polynomial share a certain common part)
  

  References:

  None

  • Meeting 08 : Fri, Jan 30, 02:00 pm-02:50 pm - Harshil M.

  Monomial ordering and examples, leading terms, multidegree and its behaviour w.r.t. addition and multiplication of polynomials

  References
  Exercises
  Reading

  Monomial ordering and examples, leading terms, multidegree and its behaviour w.r.t. addition and multiplication of polynomials
  

  References:

  None

  • Meeting 09 : Tue, Feb 03, 11:00 am-11:50 am - Harshil M.

  Understanding general form of single divisor univariate division, adapt it to work for multi-divisor multivariate setting, and showing that the algorithm terminates and returns correct output

  References
  Exercises
  Reading

  Understanding general form of single divisor univariate division, adapt it to work for multi-divisor multivariate setting, and showing that the algorithm terminates and returns correct output
  

  References:

  None

  • Meeting 10 : Wed, Feb 04, 10:00 am-10:50 am - Harshil M.

  Arbitrariness in choice of reducing divisor in division algorithm, its effect on remainder, uniqueness of remainder for nice basis. Setting up the plan: showing that monomial ideals are finitely generated, how it can be used to find a finite basis whose leading terms generate the same ideal that leading terms of polynomials from original ideal generate, showing that this basis has the desired unique-r property. Monomial ideals and its properties

  References
  Exercises
  Reading

  Arbitrariness in choice of reducing divisor in division algorithm, its effect on remainder, uniqueness of remainder for nice basis. Setting up the plan: showing that monomial ideals are finitely generated, how it can be used to find a finite basis whose leading terms generate the same ideal that leading terms of polynomials from original ideal generate, showing that this basis has the desired unique-r property. Monomial ideals and its properties
  

  References:

  None

  • Meeting 11 : Thu, Feb 05, 08:00 am-08:50 am - Harshil M.

  Dickson's lemma and its proof for n=2.

  References
  Exercises
  Reading

  Dickson's lemma and its proof for n=2.
  

  References:

  None

  • Meeting 12 : Fri, Feb 06, 02:00 pm-02:50 pm -

  Non-instructional day.

  References
  Exercises
  Reading

  Non-instructional day.
  

  References:

  None

  • Meeting 13 : Tue, Feb 10, 11:00 am-11:50 am - Harshil M.

  Proof of Dickson's lemma for general n.

  References
  Exercises
  Reading

  Proof of Dickson's lemma for general n.
  

  References:

  None

  • Meeting 14 : Wed, Feb 11, 10:00 am-10:50 am - Harshil M.

  Applying Dickson's lemma to get Hilbert's Basis theorem, defining Grobner basis, and showing that it's actually a basis and has unique r-property. Introducing S-polynomials, stating Buchberger's criterion, and showing easy direction of its proof.

  References
  Exercises
  Reading

  Applying Dickson's lemma to get Hilbert's Basis theorem, defining Grobner basis, and showing that it's actually a basis and has unique r-property. Introducing S-polynomials, stating Buchberger's criterion, and showing easy direction of its proof.
  

  References:

  None

  • Meeting 15 : Thu, Feb 12, 08:00 am-08:50 am - Harshil M.

  Starting proof of the other direction of Buchberger's critetion, proving a key lemma about writing expressions of a certain type as a combination of S-polynomials.

  References
  Exercises
  Reading

  Starting proof of the other direction of Buchberger's critetion, proving a key lemma about writing expressions of a certain type as a combination of S-polynomials.
  

  References:

  None

  • Meeting 16 : Fri, Feb 13, 02:00 pm-02:50 pm - Harshil M.

  Applying the lemma and finishing the proof of Buchberger's criterion. Informal description of Buchberger's algorithm and its run on an example.

  References
  Exercises
  Reading

  Applying the lemma and finishing the proof of Buchberger's criterion. Informal description of Buchberger's algorithm and its run on an example.
  

  References:

  None

  • Meeting 17 : Tue, Feb 17, 11:00 am-11:50 am - Harshil M.

  Discussion about Problem 2 from PS1.

  References
  Exercises
  Reading

  Discussion about Problem 2 from PS1.
  

  References:

  None

  • Meeting 18 : Wed, Feb 18, 10:00 am-10:50 am - Harshil M.

  Writing general form of Buchberger's algorithm, proving that it terminates in finitely many steps and returns correct output. Introducing Minimal Grobner bases, and an example to show their non-uniqueness.

  References
  Exercises
  Reading

  Writing general form of Buchberger's algorithm, proving that it terminates in finitely many steps and returns correct output. Introducing Minimal Grobner bases, and an example to show their non-uniqueness.
  

  References:

  None

• Theme 3 : Factorization - 18 meetings

  • Meeting 19 : Thu, Feb 19, 09:00 am-09:50 am - Harshil M.

  Introducing Reduced Grobner basis. Converting minimal Grobner basis to reduced Grobner basis

  References
  Exercises
  Reading

  Introducing Reduced Grobner basis. Converting minimal Grobner basis to reduced Grobner basis
  

  References:

  None

  • Meeting 20 : Fri, Feb 20, 02:00 pm-02:50 pm - Harshil M.

  Uniqueness of Reduced Grobner basis.

  References
  Exercises
  Reading

  Uniqueness of Reduced Grobner basis.
  

  References:

  None

  • Meeting 21 : Tue, Feb 24, 11:00 am-11:50 am - Harshil M.

  Factor theorem describing relationship between monic linear factors and roots of univariate polynomials over commutative ring. Units, irreducible elements, integral domain.

  References
  Exercises
  Reading

  Factor theorem describing relationship between monic linear factors and roots of univariate polynomials over commutative ring. Units, irreducible elements, integral domain.
  

  References:

  None

  • Meeting 22 : Wed, Feb 25, 10:00 am-10:50 am - Harshil M.

  Unique factorization domain. Prime elements of a commutative ring.

  References
  Exercises
  Reading

  Unique factorization domain. Prime elements of a commutative ring.
  

  References:

  None

  • Meeting 23 : Thu, Feb 26, 08:00 am-08:50 am - Harshil M.

  Example of irreducible element which is not prime. Example of prime element which is not irreducible. All primes are irreducible in integral domains. All irreducibles are prime in UFDs.

  References
  Exercises
  Reading

  Example of irreducible element which is not prime. Example of prime element which is not irreducible. All primes are irreducible in integral domains. All irreducibles are prime in UFDs.
  

  References:

  None

  • Meeting 24 : Fri, Feb 27, 02:30 pm-03:20 pm - Harshil M.

  Principal ideal domains. Showing that ring of integers and fields are examples of PIDs. Towards showing that every PID is a UFD: Proving the simpler lemma that every non-zero non-unit in a PID has some irreducible factor.

  References
  Exercises
  Reading

  Principal ideal domains. Showing that ring of integers and fields are examples of PIDs. Towards showing that every PID is a UFD: Proving the simpler lemma that every non-zero non-unit in a PID has some irreducible factor.
  

  References:

  None

  • Meeting 25 : Tue, Mar 03, 11:00 am-11:50 am - Harshil M.

  Using the above lemma to show that every non-zero non-unit can be factorized as a product of irreducibles in a PID. Then, showing uniqueness of this factorization upto order and associates by first proving the lemma that every irreducible is a prime in a PID.

  References
  Exercises
  Reading

  Using the above lemma to show that every non-zero non-unit can be factorized as a product of irreducibles in a PID. Then, showing uniqueness of this factorization upto order and associates by first proving the lemma that every irreducible is a prime in a PID.
  

  References:

  None

  • (Upcoming) Meeting 26 : Thu, Mar 05, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 27 : Tue, Mar 10, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 28 : Wed, Mar 11, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 29 : Thu, Mar 12, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 30 : Fri, Mar 13, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 31 : Tue, Mar 17, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 32 : Wed, Mar 18, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 33 : Thu, Mar 19, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 34 : Fri, Mar 20, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 35 : Tue, Mar 24, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 36 : Wed, Mar 25, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 4 : PIT and Algebraic complexity theory - 19 meetings

  • (Upcoming) Meeting 37 : Thu, Mar 26, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 38 : Fri, Mar 27, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 39 : Wed, Apr 01, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 40 : Thu, Apr 02, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 41 : Tue, Apr 07, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 42 : Wed, Apr 08, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 43 : Thu, Apr 09, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 44 : Fri, Apr 10, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 45 : Wed, Apr 15, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 46 : Thu, Apr 16, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 47 : Fri, Apr 17, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 48 : Tue, Apr 21, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 49 : Wed, Apr 22, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 50 : Thu, Apr 23, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 51 : Fri, Apr 24, 02:00 pm-02:50 pm -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 52 : Tue, Apr 28, 11:00 am-11:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 53 : Wed, Apr 29, 10:00 am-10:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 54 : Thu, Apr 30, 08:00 am-08:50 am -

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • (Upcoming) Meeting 55 : Tue, May 05, 11:00 am-11:50 am -

  T

  References
  Exercises
  Reading

  T
  

  References:

  None