Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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