# Using Haskell to Count Lattice Points

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 `(a,b,c,d)` where `a` and `b`run 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 `or` .

To find the number of four-tuples, we do this:

`Prelude> length m21`

And to list the tuples, we do this:

`Prelude> m[(0,0,0,2),(0,0,5,0),(0,1,2,1),(0,2,4,0),(0,3,1,1),(0,5,0,1),(0,10,0,0),(1,0,2,1),(1,1,4,0),(1,2,1,1),(1,4,0,1),(1,9,0,0),(2,0,4,0),(2,1,1,1),(2,3,0,1),(3,0,1,1),(3,2,0,1),(4,1,0,1),(5,0,0,1),(9,1,0,0),(10,0,0,0)]`

That’s it!

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.

Written by