I wish to enumerate all lattice points contained in the intersection of three hyperplanes in the non-negative half-space. That is to say, I have three linear equations of d variables and I would like to find all non-negative integer solutions.

I would be happy if you could share your equations with us. I am currently working on an additional algorithm for such problems and could test it on your data.

Best regards,

Thomas

The equations are in fact of rather specific form. Namely, you consider a range of positive integers from \( i_{min} \) to \( i_{max} \), and positive integer constants \( N \), \( D \) and \( A \). Then you may write

\( m.x=b \),

where the rows of m are as follows. First row is \( i_{min}^2, (i_{min}+1)^2,...,i_{max}^2 \), second row is \( i_{min}, i_{min}+1,...,i_{max} \), and the final row is all 1s. Column vector \( x \) contains the variables and column vector \( b \) reads \( A \), \( D \), \( N \). I am looking for all non-negative integer solutions of \( m.x=b \).

For a small concrete example, consider \( i_{min}=1 \), \( i_{max}=3 \), and \( b=(70,32,15)^T \). In this particular case there is only one solution and it is non-negative, namely \( (3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)^T \).

Due to the peculiar form of matrix \( m \), one approach to enumerating the solutions is to find the integer partitions of \( A \) into exactly \( N \) elements using only \( i_{min}^2, (i_{min}+1)^2,...,i_{max}^2 \). Once you have the partititions, you can then take the element-wise square root of each and select the ones that add up to \( D \). This is not too bad, I have used it to solve cases where for example \( b=(1284,168,30)^T \), \( i_{min}=2 \), \( i_{max}=17 \). On the other hand, in this bigger example only 9 % of the found partitions add up to \( D \) so while this works it is wasteful, and so I have been looking for a more direct method.