4
$\begingroup$

Does the positive constant $c_d$, depending only from dimension, with the following property exist?

Property: for every convex body $K\subset \mathbb R^d$ there exists parallelepiped $P\subset K$ so that $$ |P\cap \mathbb Z^d| \ge c_d |K\cap \mathbb Z^d|. $$

$\endgroup$
2
  • $\begingroup$ It may be useful to mention that this question is a discrete analogue of a theorem of Fritz John (from 1948), which states the following: For any convex set $K$ in $R^n$ with non-empty interior, there is an affine transformation $f$ and a constant $c(n)>0$ (i.e. dependent on the dimension but not $K$), such that $B_1 \subseteq f(K) \subseteq B_{c(n)}$. Here, $B_x$ is the ball around the origin of radius $x$. $\endgroup$ Commented Feb 27, 2014 at 15:07
  • $\begingroup$ Surely, your parallelepiped may be degenerate? $\endgroup$ Commented Feb 27, 2014 at 15:32

2 Answers 2

3
$\begingroup$

$\def\ZZ{\mathbb Z}\def\conv{\mathop{\rm conv}}\def\vol{\mathop{\rm Vol}}$Yes, such a constant exists. We prove just the existence, not trying to optimize it. When we mention a `xonstant' we mean the quantity dependent on $d$ only.

Set $D=d^2$, and let $\ZZ_D^d=(\ZZ/D\ZZ)^2$. To each point $a\in \ZZ^d$, let $a^*$ be its residue class in $\ZZ_D^d$. For every $z\in \ZZ_D^d$ and every $A\subset \ZZ^d$ set $A_z=\{a\in A\colon a^*=z\}$.

Let $K'=K\cap \ZZ^d$. One of the values $|K'_b|$ is at least $|K'|/D^d$, and we may pass from $K$ to $\conv K_b$, reducing the number of integer points in it by at most $D^d$ times (which is constant). Thus from now on we assume that $K$ is a polytope whise vertices lie in $(D\ZZ)^d$ (we have also applied a shift mapping one of the vertices into $0$).

Now take a simplex $S\subseteq K$ of maximal volume; its vertices $a_0,\dots,a_d$ are the vertices of $K$ and thus lie in $(D\ZZ)^d$. We may assume that $a_0=0$. Then $K$ lies in the simplex $S'$ bounded by the hyperplanes parallel to the hyperfaces of $S$ passing through their opposite vertices. The simplex $S'$ also has integer vertices, and its (linear) size is $d$ times the size of $S$.

Let $Q$ be the parallelepiped spanned by the vectors $a_1/D,\dots,a_d/D$ with $0$ as the common origin of these vectors (we assume that $Q$ is not a closed set: its hyperfaces not containing $a_0$ are removed); so $Q\subseteq S$. Then $S$ contains all translations of $Q$ by the vectors $\frac1D\sum_i \alpha_ia_i$ with $\alpha_i\in\{0,1,\dots,D-d\}$, and $S$ is covered by such translations for $\alpha_i\in\{0,1,\dots,D\}$. The ratio of quantities of such tuples $(\alpha_i)$ is constant, and each such translation contains the same number $q$ (dependent on $Q$!) of integer points. Thus the number of integer points in $S$ is approximated (up to a constant factor) by $\frac{\vol S}{\vol Q}q$.

Similarly, the number of integer points in $S'$ is approximated by $\frac{\vol S'}{\vol Q}q=d^d\cdot \frac{\vol S}{\vol Q}q$. Thus the number of integer points in $S$ is not smaller than a constant factor times such a number for $S'$, which is not smaller that such a number for $K$.

Finally, by similar reasons the parallelepiped $P=\frac{D}dQ$ contains at least a constant portion of the integer points in $S$, and thus at least a constant portion of those in $K$.

$\endgroup$
1
  • $\begingroup$ In fact, we may even set $D=d$... $\endgroup$ Commented Feb 27, 2014 at 17:36
1
$\begingroup$

[Edit: I fixed the claim in light of Bogdanov's comment below.]

If we make an additional assumption, we can construct an exponentially decaying upper bound on $c_d$ (as a function of $d$). This does not address the original poster's question, but seemed independently interesting.

We will additionally assume that the corners of $P$ lie in $\mathbb{Z}^d$.

To show the bound, consider the following construction: Let $S$ be the set of binary strings of length $d$ with even weight (so $(s_1,...,s_d)\in S$ iff $s_i\in \{0,1\}$ and $\sum_i s_i = 0 \bmod 2$.) Let $K$ be the convex hull of $S$ (where we interpret the binary vectors as their real counterpart).

Note that $|K\cap \mathbb{Z}^d|=2^{d-1}$, since half of all the vectors have even parity.

Let us consider any possible candidate for $P$. Assume that $P$ is nonempty. Note that by the symmetry of $K$, we can rotate $P$ so that one of the corners of its parallelepiped lies at the origin.

Now, suppose $P$ is an $n$-dimensional parallelepiped. Consider the $n$ corners on the parallelpiped that are adjacent to the origin, $b^1,...,b^n$. Note that $P\cap \mathbb{Z}^n$ consists precisely of the $2^n$ sums generated by adding different combinations of the $b^i$.

Note that if $(b^1_1,...,b^1_d)$ and $(b^2_1,...,b^2_d)$ are two distinct corners of the parallelepiped adjacent to the origin that are also in $\mathbb{Z}^d$, then their sum also falls in the parallelepiped. Therefore, their "1" entries must fall on a disjoint set of indices. Since the corners of $K$ have even parity, it follows that $b^1$ and $b^2$ must differ in at least two indices. Therefore, $n\leq d/2$.

It follows that $|P\cap \mathbb{Z}^d|\leq 2^{d/2}$, and hence that

$$c_d\leq 2^{-d/2 + 1}$$

$\endgroup$
1
  • 1
    $\begingroup$ But $c_d$ may depend on $d$... $\endgroup$ Commented Feb 27, 2014 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .