# 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 m`

21

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.