Having Fun with Groebner Basis and Algebraic Geometry

1015 0

Paraphrasing Bertrand Russell from In Praise of Idleness:

The wise use of leisure is a product of civilization and education with a view towards mental enjoyment and the direct use of technical knowledge.

I took an instant liking to Algebraic Geometry (and Groebner Basis) as soon as I chanced upon it, by accident, as a PhD student sometime during 1988-1990.

This is intellectual enjoyment to me.

My work in this area may turn to be useful, but if not, that is okay too.

Groebner bases are for systems of polynomial equations what triangular matrices are for systems of linear equations.

Consider the set of the two polynomials

(1)   \begin{equation*} \mathcal I = <x^3y - 2x^2y^2 + x,\, 3x^4 - y>. \end{equation*}

Its Groebner basis with respect to monomial ordering

    \[ x >  y \]

is the  triangular system

(2)   \begin{equation*} \mathcal B= \{-9y +48y^{10}-49y^7 +6y^4,  252x-624y^7 +493 y^4-3y\}. \end{equation*}

The systems

    \[ \mathcal I \]


    \[ \mathcal B \]

have the same solutions i.e., they define same variety. The number of solutions (number of points of the variety) can be read off from the elements of Groebner basis starting from the first, which has only one variable, y. For every one of the values of y, you can then find the values of x.

How do you find the Groebner Basis? Using Buchberger’s algorithm. See this wonderful book for an excellent introduction.

For fun, I wrote a paper on this (Mathematical Programming, 1995) with Rekha Thomas and Natraj, and presented it at a MIT OR Center Seminar.

Dimitris Bertsimas then invited me to MIT, and so I did a sabbatical there in 1997. I met Georgia Perakis there.

I had a great apartment near Harvard Square and took the T (Red Line) between Harvard and Kendall every day.

On weekends, enjoyed Challah bread at the Cambridge Hi-Rise Bread Company.

A major highlight was that I discovered Kendall Square Cinema when I was looking for a theater to see The Full Monty.

It was also the time when Tomorrow Never Dies came out, whose opening sequence I liked so much that I saw it twice in a theater. (The only movie that I have done this ever.)

Dimitris, Georgia and I then wrote this cute paper (Management Science, 2000) that uses Grobner Basis to solve Integer Programs.

Of course, I then went off to do practical things (that had nothing to do with Algebraic Geometry) with:

McKinsey, as a Consultant to the Firm out of their Detroit office, in lean manufacturing (and JIT) in automotive supply chains.

Caterpillar, designing a rapid response supply chain for their new P2000 product line that was featured in Fortune.

SmartOps, a enterprise software company, that created the market for Enterprise Inventory Optimization (EIO), of which I was the Founder and CEO.

Then in 2017, years after selling SmartOps to SAP (in 2013), and after many years of doing work in Organ Transplantation including founding OrganJet (in 2011), I decided, on a whim, for the fun of it,  to see if I could revisit Algebraic Geometry in the context of Quantum Computing.

Yes, I could!

Here is our paper that uses Algebraic Geometry in the context of Adiabatic Quantum Computing.





Leave a Reply