Using Haskell to Count Lattice Points

James Carlson

Jun 1, 2017·2 min read

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 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 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.