## Lattice points in l^{1} balls

For positive integers and , let denote the number of points such that . In other words, is the number of lattice points in an -dimensional -ball of radius . Bump, Choi, Kurlberg and Vaaler have observed that the function enjoys the following symmetry

.

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

and noting that it is symmetric in and . 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 denote the number of points with where each . Then we have: . The reader might recognize this as the standard argument for counting the number of homogeneous polynomials of degree in variables.

**Theorem 1** *.*

*Proof:* We note that an can be represented as follows: we take 1’s and place dividers anywhere among them. Each divider represents the end of a term: so will equal the number of 1’s between divider and (this can be zero). For example, when and ,

corresponds to

(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 ‘s can be strictly less than .) Each arrangement of dividers and 1’s corresponds uniquely to an . We have such arrangements, because we can think of choosing the places to put dividers out of total places to put dividers and 1’s. This shows that since , but it also yields a nice bijection. We can map an to a by simply interchanging dividers and 1’s. For example, the above is mapped to:

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

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

**Theorem 2** *.** *

*Proof:* If has non-zero terms, then we must have . Such an has zero’s, and there are ways to place them among the coordinates. If we restrict the non-zero ‘s to be positive, then we can form an ordered set of non-zero ‘s whose sum is by again considering 1’s and dividers. This time we have 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 ,

represents . 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 positive terms with sum at most . There are possible places for dividers and we must choose of them, so there are possibilities. There are ways to set the signs of non-zero terms, so when we put everything together we have:

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

We map this to a diagram representing as follows: we change the slots in the top to 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 positive terms of with a sum at most . 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:

So is mapped to . 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 to . Again, it is also an involution.

* *

leave a comment