## What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I want to learn how to program from them, so we were planning on working on some computational algebraic geometry together. While there are several books which we could work through, I thought it might be more fun and productive if we had the goal of developing a usable new algorithm, or at least implementing an algorithm which no one has implemented before. I do not have any ideas, but I thought that some mathoverflowers might have had an idea for an algorithm they would like to see implemented but have never had the time to work through the details. Keep in mind that my wife and friend will have to learn any mathematics past a first course in topology and abstract algebra as we go.

So does anyone have any ideas for an algorithm they would like to use which is within the reach of my "team" to implement within a summer? We are planning on working on this stuff between 2 and 3 hours a day for about 3 months.

-
Fantastic question!!! – Kevin Lin Mar 17 2010 at 4:03
Did anything come out of this summer project? – jc May 26 2011 at 23:48

Just a thought, but maybe you should have a look at sage. It's a big open source project that is currently under very active development. If you're interested in contributing, I would suggest that you post to the sage-devel Google group with this same question. Some thoughts for things to do would be to improve the support for relative extensions of number fields and for function fields.

-
The only downside to going that route is that you'll then be forced into (a dialect of) Python or C as the programming languages. Which is like forcing a category theorist to make the choice between working in either an untyped HOL or 'raw' ZFC. – Jacques Carette Mar 17 2010 at 13:10
Now this is very cool! I love the idea of a high level open source mathematics program - I always thought a proof which was Mathematica assisted was slightly suspect because you can't check the code for errors. I am all for making high level mathematics more available to the public. So I think I have found where I should devote my energy. Thanks!!! – Steven Gubkin Mar 17 2010 at 13:13
@Jacques Ya, if only they supported Haskell... – Steven Gubkin Mar 17 2010 at 13:14
Another thing to look at might be contributing to Macaulay 2 ( math.uiuc.edu/Macaulay2 ) which is the go-to computation package for many algebraic geometers I know. – Charles Siegel Mar 17 2010 at 14:19
Doesn't SAGE just out-source most algebraic geometry to SINGULAR or Macaulay2? I personally would say that polyhedral homotopy continuation (PHoM, PHCPack, HOM4PS, Bertini) is the place to go, though it seems that the automotive industry (robotics) has been the leader in implementing much of it. – Junkie May 25 2010 at 4:49

My proposal: a usable tool for working with line bundles on toric varieties and their cohomology. There are some tools (Polymake, Latte) for working with polyhedra, but I haven't seen a library dedicated specifically to toric varieties.

For example, you could provide a GUI tool for working with toric surfaces, where you can e.g. blow a point up by a single click (as far as I remember, this corresponds to adding an edge), compute intersections of divisors and cohomology of line bundles.

Also: toric deformations and degenerations, action of the Frobenius morphism (there are two descriptions of Frobenius push-forwards of line bundles, due to Thomsen and Bondal), finding exceptional collections etc.

I think this could be really interesting and useful.

-
You may find this of interest: portal.acm.org/citation.cfm?id=1243161 – Steve Huntsman Mar 17 2010 at 0:05
Really cool suggestion! – Steven Gubkin Mar 17 2010 at 12:57

Faugère's F5 algorithm for computing Groebner bases. A huge number of algorithms in algebraic geometry rely on Groebner bases, and F5 is reputed to be "the best". But there is only one implementation, and it is not so widely available. The community could really benefit from a second, well-explained implementation.

This is more of a foundational'' answer that you might have wished for, I'm sure. But it seems that most algebraic geometry algorithms eventually rely on Groebner bases, so why not start there?

-
I have the impression that Gröbner basis algortihms are very tricky to implement efficiently and if so this may put too much emphasis on gory details. – Torsten Ekedahl Mar 17 2010 at 5:16
If you want an "application of Grobner bases" (which unfortunately would mean calculating over Z_2 (the 2-adic integers) rather than a field) then I'll remark that as far as I know it's still an open problem as to whether every group scheme of order 4 is killed by 4, and this always seems to me to be in the general ballpark of accessibility, it just needs a good algebraic geometer and a good programmer ;-) The alg geometer needs to translate the question into a ring theory one, using the programmer to guide them as to which variables to use to make things most efficient. – Kevin Buzzard Mar 17 2010 at 7:42
Cool. This does seem low enough to the ground that we could after a crash course in Groebner bases we could get started on it. If it is going to be really "gory" (as Torsten suggests) it might not be the best project though. @Kevin: That does seem doable! An option to keep in mind. – Steven Gubkin Mar 17 2010 at 12:53
@Torsten: extremely efficient versions are tricky, moderately efficient versions are not. Picking a reasonable language (like O'Caml) for the task would make it easier than the usual suspects. – Jacques Carette Mar 17 2010 at 13:04
I have heard that Allan Steel has a version of F5 in Magma, which works better than F4 in some specific examples, but it is not publically available. I definitely agree that GB algos are extremely tricky to implement well. My notion is that F4 has been tried by a few people (maybe 10 in all) to implement it, but only Faugere and Steel consistently can beat a souped-up version of the classical Buchberger. Another idea for GBs would be to take something already out there, and widen the set of base rings allowed. Inexact rings, are a real pain for correctness. but would be interesting. – Junkie May 25 2010 at 4:55

Steve, do you know about Macaulay 2? It's a computer algebra system designed for commutative algebra and algebraic geometry.

Moreover it has a fairly easy to use language and an easy way to create packages.

Probably if you would join the Google Group "Macaulay 2" and asked this same question you would get some offers.

-