For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid have length smaller than $1$?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Maybe, it is even true that the body does not contain a unit ball? $\endgroup$– Fedor PetrovCommented Nov 2, 2017 at 7:39
-
$\begingroup$ @FedorPetrov: You probably mean a ball of unit diameter, not radius. But then: The body contains an ellipsoid whose every axis is of length at least 1 if and only if it contains a ball of diameter 1. $\endgroup$– Wlodek KuperbergCommented Nov 5, 2017 at 2:06
-
$\begingroup$ @WlodekKuperberg Unit diameter, of course. I also used to think so. But John ellipdoid is not unique inclusion-maximal ellipsoid inside the ball. $\endgroup$– Fedor PetrovCommented Nov 5, 2017 at 7:38
-
$\begingroup$ @FedorPetrov Thanks, I stand corrected. Obviously, in a very tall isosceles triangle of base 1, the diameter of the inscribed circle is very close to 1, but the John ellipse's minor axis is just $\sqrt{3}/3$. $\endgroup$– Wlodek KuperbergCommented Nov 8, 2017 at 22:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
The answer is $no$.
In the plane, the circle of diameter $d$ greater than $1$ but smaller than $\sqrt2$ and centered at $({1\over2},{1\over2})$ contains no point with integer coordinates, and the square $K_2$ circumscribed about it with diagonals parallel to the coordinate axes contains no such point either. Let $K_3\subset\mathbb{R}^3$ be the Cartesian product $K_2\times[0,d]$. Then $K_3$ contains no lattice point, the $2$-sphere inscribed in $K_3$ is of diameter $d$, and the number of facets of $K_3$ is $6$, since, in general, the product $K\times[0,1]$ has two more facets than $K$. Iterating the product procedure, we get $K_n=K_2\times[0,d]^{n-2}\subset\mathbb{R}^n$ with $2n$ facets, containing no lattice point but containing a sphere of diameter $d>1$.
Similarly, a sequence of polytopes $K_{k,n}$ ($k$ fixed, $n=k, k+1, k+2, \ldots$) can be constructed that have the same properties as above, with $d$ arbitrarily close to $\sqrt k$. This shows that for any constant $d$ in place of $1$ in the question asked here, the answer is still in the negative. Namely, begin with $K_k$ to be the cross-polytope in $\mathbb{R}^k$ circumscribed about the $k$-sphere of diameter slightly smaller than $\sqrt k$ and centered at $({1\over2},{1\over2}, \ldots,{1\over2})$ and with main diagonals (the "cross") parallel to the coordinate axes, then proceed as above. The number of facets of $K_{k,n}$ will be $2^k + 2(n-k)$, which is $O(2n)$.
-
1$\begingroup$ $K_2\times [0,d]^{n-2}$ contains John's ellipsoid with smallest axis $\sqrt2$ (not sphere of radius $d$). $\endgroup$– TurboCommented Nov 2, 2017 at 14:39
-
$\begingroup$ @Turbo: Thanks for the correction. I changed "radius" to "diameter", which is what I meant. $\endgroup$ Commented Nov 2, 2017 at 14:42
-
$\begingroup$ yes... but my main argument was about smallest axis smaller than $1$ necessary which is disproved in your case with smallest axis $\sqrt 2$ or $\sqrt k$ in general. $\endgroup$– TurboCommented Nov 2, 2017 at 14:46
-
$\begingroup$ Right. The way the example is constructed, the John's e ellipsoid is a sphere. Of course, the product could use a line segment longer than $d$, in which case some of the axes of the ellipsoid could be arbitrarily long. $\endgroup$ Commented Nov 2, 2017 at 14:52
-
1$\begingroup$ I meant $\sqrt2-\epsilon$ at any $\epsilon\in(0,\sqrt2-1)$. $\endgroup$– TurboCommented Nov 2, 2017 at 15:00