Lewko's blog

Lattice points in l^{1} balls

Posted in math.CO, math.NT by Mark Lewko on July 31, 2009

For positive integers {n} and {m}, let {L(n,m)} denote the number of points {x = (x_1, \ldots, x_n) \in \mathbb{Z}^n} such that {\sum_{i=1}^n |x_i| \leq m}.  In other words, {L(n,m)} is the number of lattice points in an n-dimensional l^1-ball of radius mBump, Choi, Kurlberg and Vaaler have observed that the function {L(n,m)} enjoys the following symmetry

\displaystyle {L(n,m) = L(m,n)}

This is to say that the n-dimensional l^1-ball of radius m contains exactly the same number of lattice points as the m-dimensional l^1-ball of radius n.  The original proof follows from establishing the generating function identity

\displaystyle \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}L(m,n)x^m y^n = (1-x-y-xy)^{-1}

and noting that it is symmetric in x and y.  Some time ago Jeff Vaaler mentioned to me that it would be nice to find a bijective proof of this fact.  In this post I will give a simple bijective proof that Allison Bishop and I found. 


Tagged with: