3
$\begingroup$

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$.

$\endgroup$

1 Answer 1

10
$\begingroup$

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
$\endgroup$
4
  • $\begingroup$ Great! That is quite surprising. I assumed, that is better to look for co-prime $q_i$ for counterexamples. $\endgroup$ Jun 11, 2013 at 20:09
  • $\begingroup$ 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$. $\endgroup$ Jun 11, 2013 at 20:15
  • $\begingroup$ @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/… $\endgroup$ Jun 11, 2013 at 20:40
  • $\begingroup$ 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. $\endgroup$ Jun 15, 2013 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.