Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 LatticeSum

Source Notebook

Compute a lattice sum

Contributed by: Xiangdong Wen using code by Jon Lee and Daphne Skipper

ResourceFunction["LatticeSum"][monomial,constraints]

gives the sum of monomial over all integer lattice points satisfying the constraints.

Details

The input monomial is of the form w1f1 w2f2 … wnfn, where w1,w2,…,wn are variables and f1,f2,…,fn are linear functions of another set of variables in the constraints—that is, of the integer grid (lattice points) inferred from the constraints.
The constraints must all be linear with integer or rational coefficients. Or and Unequal constraint expressions are not supported. It supports And inequalities with Greater (>), Less (<), GreaterEqual (>=), LessEqual (<=), and Equal (==).
ResourceFunction["LatticeSum"] uses the algebraic-perturbation Barvinok algorithm, a variant of Barvinok's algorithm for computing a short rational generating function for the integer points P in (x∈Rn:Ax≤b).

Examples

Basic Examples (2) 

Sum xt for t from 0 to infinity:

In[1]:=
ResourceFunction["LatticeSum"][\!\(TraditionalForm\` \*SuperscriptBox[\(x\), \(t\)]\), t >= 0]
Out[1]=

Sum rxsy for all integer lattice points satisfying x ⩾ 0, y ⩾ 0 and x +y ⩽ 5:

In[2]:=
sum = ResourceFunction["LatticeSum"][r^x s^y , x + y <= 5 && x >= 0 && y >= 0]
Out[2]=

Count the number of integer lattice points satisfying x ⩾ 0, y ⩾ 0 and x + y ⩽ 5:

In[3]:=
Limit[sum, {r -> 1, s -> 1}]
Out[3]=

Compute the number directly:

In[4]:=
ResourceFunction["LatticeSum"][1 , x + y <= 5 && x >= 0 && y >= 0]
Out[4]=

Scope (3) 

Compute the sum of xaybzc over non-negative integers satisfying x + y + z ⩽ 5:

In[5]:=
ResourceFunction["LatticeSum"][\!\(TraditionalForm\` \*SuperscriptBox[\(x\), \(a\)] \*SuperscriptBox[\(y\), \(b\)] \*SuperscriptBox[\(z\), \(c\)]\), a + b + c <= 5 && a >= 0 && b >= 0 && c >= 0]
Out[5]=

Count the total number of non-negative lattice points satisfying x + y + z ⩽ 5:

In[6]:=
ResourceFunction["LatticeSum"][\!\(TraditionalForm\`1\), a + b + c <= 5 && a >= 0 && b >= 0 && c >= 0]
Out[6]=

Visualize these lattice points. Here, we use FindInstance to obtain all the points:

In[7]:=
ListPointPlot3D[ Table[{x, y, z} /. u, {u, FindInstance[ x + y + z <= 5 && x >= 0 && y >= 0 && z >= 0, {x, y, z}, Integers, 10000]}], AxesLabel -> {"x", "y", "z"}, PlotStyle -> {Blue, PointSize[0.03]}, Boxed -> True, BoxRatios -> {1, 1, 1}]
Out[7]=

A complicated example, the algorithm gets the result instantly:

In[8]:=
ResourceFunction["LatticeSum"][ x0^h x1^(1 + 2 f + k) x2^(5 + e + f + h + 3 j) x3^( 2 + e + 2 f + k + n - t) x4^(5 + e + f + h + 3 j + t) x5^e x6^( 4 + 2 f + h + 2 j + k), t >= 1 && t <= 2 + 2 f + k + n && n >= 4 + e + 3 f + j + k && h >= 0 && e >= 0 && f >= 0 && j >= 0 && k >= 0]
Out[8]=

Properties & Relations (2) 

LatticeSum[monomial, constraints] returns Indeterminate if the constraints are not bounded:

In[9]:=
ResourceFunction["LatticeSum"][1, r > 10]
Out[9]=

Here z+w is treated as a base of the monomial:

In[10]:=
ResourceFunction["LatticeSum"][x^r y^s (z + w)^t, t > 2]
Out[10]=

Possible Issues (3) 

The first input should be a monomial:

In[11]:=
ResourceFunction["LatticeSum"][x^r y^s z^t + 2, r > 10]
Out[11]=

Constraint variables cannot be the same as the base variables of the monomial:

In[12]:=
ResourceFunction["LatticeSum"][x^r y^s z^t, z > 10]
Out[12]=

All constraints should be linear and have integer or rational coefficients:

In[13]:=
ResourceFunction["LatticeSum"][x^r y^s z^t, t > Sqrt[2]]
Out[13]=

Publisher

Xiangdong Wen

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 11 March 2026

Source Metadata

  • Citation:
    • Jon Lee, Daphne Skipper, Computing with an algebraic-perturbation variant of Barvinok's algorithm, Discrete Applied Mathematics, Volume 240,2018,Pages 63-77,ISSN 0166-218X

Related Resources

Author Notes

It supports only linear constraints.

License Information