# Lattice points in cross-polytopes

Let $E\subset \mathbb{R}^n$ be a cross-polytope: $$E= \left\lbrace x : \frac{|x_1|}{q_1}+\cdots+\frac{|x_n|}{q_n}\leq 1 \right\rbrace,$$ where $q_1,\dots,q_n$ are positive integers. I am interested in estimating the number $L$ of lattice points in $E$.

Conjecture. $$L:=\# \left(E \cap \mathbb{Z}^n\right)>\mathrm{vol}(E)\,.$$

It's obviously true for $n=1$, and very easy to verify (using Pick's formula) for $n=2$. I don't know how to prove it for $n\geq 3$ without some additional constraints.

According to (generalized) Blichfeldt's theorem, there exists $x\in\mathbb{R}^n$ such that $E+x$ has more lattice points than $\mathrm{vol}(E)$. This suggests the following

Conjecture (strong version). For any $x\in\mathbb{R}^n$ $$L\geq \#\left((E+x)\cap\mathbb{Z}^n\right)\,.$$

I don't know how to prove (or disprove) this version even for $n=2$.

-

The conjecture fails for $n=3$ and $(q_1,q_2,q_3) = (9,10,10)$, when ${\rm vol}(E) = (2^3/3!) 9 \cdot 10 \cdot 10 = 1200$ but $\#(E \cap {\bf Z}^3) = 1199$. In general, if $(q_1,q_2,q_3) = (k,k+1,k+1)$ then $$\#(E \cap {\bf Z}^3) - {\rm vol}(E) = -\frac23 k^2 + \frac{16}{3} k + 5$$ which is negative for $k \geq 9$, and increasingly so as $k$ grows. This was found experimentally, but is not hard to prove: the integer points are those for which $\left| x_1 \right| + \left| x_2 \right| + \left| x_3 \right| \leq k$ (i.e. the lattice points inside the $(k,k,k)$ octahedron), together with the $4(k+1)$ points with $x_1=0$ and $\left| x_2 \right| + \left| x_3 \right| = k+1$. By a standard induction there are $\frac43 k^3 + 2k^2 + \frac83 k + 1$ integer solutions of $\left| x_1 \right| + \left| x_2 \right| + \left| x_3 \right| \leq k$, etc.

The other examples with $n=3$ and $q_1 \leq q_2 \leq q_3 \leq 20$ are $(6,17,18)$, $(7,13,14)$, $(8,15,16)$, $(9,17,18)$, $(9,19,19)$, $(10,19,20)$ with a shortfall of $-1$, $-17/3$, $-17$, $-31$, $-1$, $-143/3$ respectively, and suggesting similar generalizations, all with two of the $q_i$ related by a simple ratio. The OP commented "That is quite surprising. I assumed that is better to look for coprime $q_i$ for counterexamples", and I confess that this surprised me too (though the proof for $(k,k+1,k+1)$ explains the mechanism). Curiously the conjecture seems to be true when the $q_i$ are pairwise coprime; in fact an exhaustive search of the region $q_i \leq 256$ found no counterexamples to the stronger inequality $$\#(E \cap {\bf Z}^3) - {\rm vol}(E) > q_1.$$ It's not easy even to find examples where the two sides are nearly equal. The smallest ratios that the search turned up all fit the pattern $$(q_1,q_2,q_3) = (2n^2-3n, 2n^2-2n-1, 2n^2-n-1)$$ with $$\#(E \cap {\bf Z}^3) - {\rm vol}(E) = 2n^2-2n+5 = q_1 + O(q_1^{1/2})$$ (any $n>1$). I have not tried to prove that this persists for all $n$, though I guess it won't be too hard $-$ not as easy as the $(k,k+1,k+1)$ explanation but much easier than proving the inequality for all pairwise coprime $q_1,q_2,q_3$.

Still, even in the pairwise coprime case one soon find counterexamples with $n=3$ to the "Conjecture (strong version)" that $E$ has at least as many lattice points than $E+x$ for any $x \in {\bf R}^n$. We can even take $x = (\frac12, 0, 0)$, and then test the conjecture by comparing the count of integer points in the $(2q_1,q_2,q_3)$ octahedron with twice the $(q_1,q_2,q_3)$ count. If the former is larger then we have a counterexample, and this happens already for $(q_1,q_2,q_3) = (5,2,3)$, when $E$ has $49$ integral points but $E+(\frac12,0,0)$ has $50$. There are $30$ more such examples with $\max_i q_i \leq 16$. (As it happens $(2,3,5)$ is the $n=2$ case of $(2n^2-3n, 2n^2-2n-1, 2n^2-n-1)$, and larger $n$ account for some of the other counterexamples.)

In the previous edit of this answer I gave some needlessly convoluted gp code for computing the difference between the number $L$ of integral points in $E$ and the volume $\frac43 q_1 q_2 q_3$ of $E$. Here's a much simpler and faster program, which takes time about $q_1 q_2$ and negligible space, whereas the earlier code (using generating functions) took time and space $q_1 q_2 q_3$.

{
L3(q1,q2,q3) =
sum(x1=0,q1,if(x1>0,2,1) *
sum(x2=0,q2+(-q2*x1)\q1,if(x2>0,2,1) *
(1 + 2*(q3+(-q3*(q2*x1+q1*x2))\(q1*q2)))
)
)
}
d3(q1,q2,q3) = L3(q1,q2,q3) - (4/3)*q1*q2*q3

-
Great! That is quite surprising. I assumed, that is better to look for co-prime $q_i$ for counterexamples. – Oleg Eroshkin Jun 11 '13 at 20:09
You're welcome. I'll post the gp code before long. Meanwhile, To enumerate $E \cap {\bf Z}^3$ when $(q_1,q_2,q_3) = (k,k+1,k+1)$, observe that the integer points are those with $\left|x_1\right|+\left|x_2\right|+\left|x_3\right| \leq k$ together with the $4(k+1)$ points with $x_1=0$ and $\left|x_2\right|+\left|x_3\right| = k+1$. – Noam D. Elkies Jun 11 '13 at 20:15
@Elkies, I wonder if you saw this question from a couple of weeks ago, which also seems to be about intersection of cross polytopes with lattices: mathoverflow.net/questions/132165/… – Yoav Kallus Jun 11 '13 at 20:40
Yes I saw it, but had nothing to contribute. In large dimensions we don't know how to pack $l_1$ balls (hyperoctahedra / cross-polytopes) any more densely than $l_2$ (round/Euclidean) balls. – Noam D. Elkies Jun 15 '13 at 22:22