Today I needed to work out a little example in algebraic geometry. It is explained below if you are interested, or if you have a taste for jargon in foreign technical languages. But the underlying problem is a simple one related integer programming. Such problems are of wider interest, and it turns out that Haskell is a good tool for solving small versions of them. Best of all, the solution of our little problem is a one-liner!
The problem. Enumerate all four-tuples of non-negative integers
(a,b,c,d) satisfying the equation
a + b + 2c + 5d = 10 and at least one of the inequalities
a > 8, b > 8, c > 3, d > 0 . You can think of this as finding the number of lattice points in 4-space which lie on a certain hyperplane
(a + b + 2c + 5d = 10)and which also lie in the union of various half-spaces
(a > 8, etc.) Thus the problem is really a geometric one, albeit stated algebraically.
Below is the Haskell code (I am running
ghci ). Notice that it is almost a transliteration of the problem statement. Cool! You can’t be more efficient than this.
Prelude> m = [(a,b,c,d) | a <- [0..10], b <- [0..10], c <- [0..5], d <- [0..2], a + b + 2*c + 5*d == 10, (a > 8) || (b > 8) || (c > 3) || (d > 0)]
Notes on the code. We use a list comprehension, which generates all tuples
brun from 0 through 10,
c runs from 0 through 5, etc. and where the equation is satisfied as well as the long expression
(a> 8) || (b >> 8) ... Here
|| stands for the logical operator
To find the number of four-tuples, we do this:
Prelude> length m
And to list the tuples, we do this:
The problem behind the problem
Find the dimension of the Jacobian ideal in degree 10 of the Fermat hypersurface of degree 10 in a weighted homogeneous space with weights 1, 1, 2, 5, and list monomials that give a basis for that space.
Reference on real integer programming. Pssst! It’s hard, as in NP-hard.