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. 

Before proving this identity, let us recall a similar and better-known identity. Let {L^+(n,m)} denote the number of points {x\in \mathbb{Z}^n} with {\sum_{i=1}^n x_i \leq m} where each {x_i\geq 0}.  Then we have: {L^+(n,m) = L^+(m,n) = {{m+n}\choose{n}}}.  The reader might recognize this as the standard argument for counting the number of homogeneous polynomials of degree m in n variables.

 Theorem 1 L^{+} (n,m) = L^{+} (m,n) = {m+n\choose n}.

 Proof: We note that an {x\in L^+(n,m)} can be represented as follows: we take {m} 1’s and place {n} dividers anywhere among them.  Each divider represents the end of a term: so {x_i} will equal the number of 1’s between divider {i-1} and {i} (this can be zero).  For example, when {n = 6} and {m= 8},

\displaystyle | | 1 1 | 1 1 1 ||1 1 | 1

corresponds to

\displaystyle x = (0,0,2,3,0,2).

(Note that 1’s occurring after the last divider are not included in any term. This accounts for the fact that the sum of the {x_i}‘s can be strictly less than {m}.)  Each arrangement of dividers and 1’s corresponds uniquely to an {x\in L^+(n,m)}.  We have {{{m+n}\choose{n}} = {{m+n}\choose{m}}} such arrangements, because we can think of choosing the {n} places to put dividers out of {m+n} total places to put dividers and 1’s.  This shows that {L^+(n,m) = L^+(m,n)} since {{{m+n}\choose{n}} = {{m+n}\choose{m}}}, but it also yields a nice bijection. We can map an {x\in L^+(n,m)} to a {y\in L^+(m,n)} by simply interchanging dividers and 1’s.  For example, the {x} above is mapped to:

\displaystyle | | 1 1 | 1 1 1 ||1 1 | 1 \mapsto 1 1 | | 1 | | | 1 1 | | 1 |

\displaystyle x = (0,0,2,3,0,2) \mapsto y = (2,0,,1,0,0,2,0,1).

This is clearly a bijection, and in fact it is an involution. \Box

One might hope to adapt this map into a bijection between {L(n,m)} and {L(m,n)} by somehow mapping signs of terms as well, but this approach can quickly be shown to fail.  In the  example above, an {x} with 3 non-zero terms is mapped to a {y} with 4 non-zero terms.  Hence there are 8 different signed versions of {x} and 16 signed versions of {y}.  This rules out any possibility of mapping the signed versions of {x} bijectively to the signed versions of {y}.  To overcome this difficulty, we instead find a map which sends {x}‘s with {k} non-zero terms to {y}‘s with {k} non-zero terms.

 Theorem 2 {L(n,m) = L(m,n)}. 

 Proof: If {x\in L(n,m)} has {k} non-zero terms, then we must have {k\leq \min\{ n, m\}}.  Such an {x} has {n-k} zero’s, and there are {{n \choose n-k} = {n \choose k}} ways to place them among the {n} coordinates.  If we restrict the non-zero {x_i}‘s to be positive, then we can form an ordered set of {k} non-zero {x_i}‘s whose sum is {\leq m} by again considering 1’s and dividers.  This time we have {m} 1’s and after each is a single slot where a divider may be placed (so we no longer allow dividers to be placed before all of the ones or adjacent to other dividers, since these situations correspond to 0’s).  For example, when {k = 4, m=8},

\displaystyle 1 | 1 1 | 1| 1 1 1| 1

represents {1, 2, 1, 3, 1}.  Again, 1’s which appear after the last divider are not included.  Each of these valid arrangements of 1’s and dividers corresponds uniquely to an ordered set of {k} positive terms with sum at most {m}.  There are {m} possible places for dividers and we must choose {k} of them, so there are {{m \choose k}} possibilities.  There are {2^k} ways to set the signs of {k} non-zero terms, so when we put everything together we have:

\displaystyle L(n,m) = \sum_{k=0}^{\min\{n,m\}} 2^k {n\choose k} {m\choose k}.

This formula gives the same value if we interchange {m} and {n}, so we have shown that {L(n,m)= L(m,n)}.  But this reasoning also yields an explicit bijection. We consider {x \in L(n,m)} with {k} non-zero, positive terms.  We will map this to {y\in L(m,n)} with {k} non-zero, positive terms.  We consider the {n} coordinates of {x} as {n} slots and we place {k} stars in the slots for each non-zero term of {x}.  Then we can represent the (ordered) {k} non-zero coordinates of {x} as {m} 1’s with {k} dividers in single slots following each 1.  Returning to our example {n = 6, m=8, k = 3, x = (0,0,2,3,0,2)}, we see that we can represent {x} by the following diagram:

\displaystyle \underline{0} \hspace*{.5cm} \underline{0} \hspace*{.5cm} \underline{\bigstar} \hspace*{.5cm} \underline{\bigstar} \hspace*{.5cm} \underline{0} \hspace*{.5cm} \underline{\bigstar}

\displaystyle 1 1 | 1 1 1 | 1 1 | 1.

We map this to a diagram representing {y\in L(m,n)} as follows: we change the {n} slots in the top to {n} 1’s, each followed by a slot for a possible divider and we place dividers where the stars used to be.  This now represents the {k} positive terms of {y} with a sum at most {n}.  In the lower diagram, we change 1’s to slots and we place stars above slots for 1’s which were immediately followed by a divider.  This now represents the locations of the non-zero coordinates of y.  The resulting diagram is:

\displaystyle 1 1 1 | 1 | 1 1|

\displaystyle \underline{0} \hspace*{0.5cm} \underline{\bigstar} \hspace*{0.5cm} \underline{0} \hspace*{0.5cm} \underline{0} \hspace*{0.5cm} \underline{\bigstar} \hspace*{0.5cm} \underline{0} \hspace*{0.5cm} \underline{\bigstar} \hspace*{0.5cm} \underline{0}.

So {x} is mapped to {y = (0,3,0,0,1,0,2,0)}.  We have assumed here that non-zero coordinates are positive, but since our map preserves the number of non-zero coordinates, we can simply declare that the sign pattern of non-zero terms in the image will match the sign pattern of non-zero terms in the pre-image.  This completes our bijection from {L(n,m)} to {L(m,n)}.  Again, it is also an involution. \Box

 

Advertisements
Tagged with:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: