Let ${O(m,r)}$ be the number of integral points in the ${m}$-dimensional octahedron of radius ${r}$:

$\displaystyle O(m,r)= \Bigl|\{(x_1,\ldots, x_m)\in {\mathbb Z}^m: |x_1|+\cdots+|x_m|\le r\}\Bigr|.$

A standard combinatorial argument shows that for positive integers ${m}$ and ${n}$

$\displaystyle O(m,n)=\sum_{k=0}^{\min\{m,n\}} 2^k \binom mk \binom nk,$

and, in particular,

$\displaystyle O(m,n)=O(n,m). \ \ \ \ \ (1)$

Is it possible to give a “geometric” interpretation (or any other “conceptual” interpretation) of identity (1)?

Update
A satisfactory answer was given by Allison and Mark Lewko, see the comments.

2 Responses to “radius-dimension symmetry for octahedra”

1. Mark Lewko Says:

I wrote a blog entry about this identity some time ago (see: http://lewko.wordpress.com/2009/07/31/lattice-points-in-l1-balls/). There I gave a bijective proof of the fact that O(m,n)=O(n,m). This, however, is little more than a reinterpretation of the identity you give for O(m,n) above. This relation can also be seen via the symmetry of the generating function:

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

I first learned of this identity from a 2000 paper of Bump, Choi, Kurlberg and Vaaler (see: http://www.ams.org/mathscinet-getitem?mr=1738343), where the proof of the generating relation is given. Are you aware of an earlier appearance of this identity?

• vieuxgirondin Says:

Dear Mark,

many thanks!

I learned on this identity from the article

P. Kirschenhofer, A. Pethő, R.F. Tichy, On
analytical and Diophantine properties of a family of counting
polynomials, Acta Sci. Math. (Szeged) 65 (1999), 47-59,

but I do not think it was discovered therein. I believe it was known long ago.