7
$\begingroup$

Consider the set of points in $\mathbb{R}^n$ with coordinates in $\{-1, 0, 1\}$. Find a hyperplane passing through the origin that contains no points in the set besides the origin.

This is simple if we don't give any constraints on the hyperplane. Even if define the hyperplane by a normal vector in $\mathbb{Z}^n$, it is simple. However, what if we require every coordinate of the normal vector to be an integer bounded in absolute value by some polynomial in $n$? Does such a hyperplane exist?

$\endgroup$
7
$\begingroup$

No. Let the normal vector be $(a_1,\ldots, a_n)$. If these numbers are $poly(n)$ small integers, then there is an $I$ and $J$ such that $\sum_{i\in I} a_i=\sum_{j\in J} a_j$ by the pigeon hole principle. But then we have $\sum_{i=1}^n \varepsilon_i a_i=0$ for some $\varepsilon \in \{-1,0,1\}^n$.

$\endgroup$
3
$\begingroup$

Just to add to Domotor's answer, any hyperplane whose normal vector has polynomially bounded coefficients (in fact bounded by $2^{o(n)}$) contains an entire face (i.e. subcube) of the cube of dimension $n - o(n)$. This follows from the Sauer-Shelah lemma.

To be precise, say each $|a_i| \leq n^c$. Then for any $I \subseteq [n]$, $\sum_{i \in I}{a_i} \in \mathbb{Z} \cap [-n^{c+1}, n^{c+1}]$. So by averaging there exists some integer $b: |b| \leq n^{c+1}$, for which $\mathcal{I}_b = |\{I: \sum_{i \in I}{a_i} = b\}| \geq 2^{n-1} n^{-c - 1} = 2^{n - o(n)}$. Then according to Sauer-Shelah, there exists a set $S \subseteq [n]$ of size $n - o(n)$ shattered by $\mathcal{I}_b$, i.e. for each $T \subseteq S$ there exists $I \in \mathcal{I}_b$ such that $I \cap S = T$. This means that for any $\epsilon \in \{-1, 0, 1\}^S$, there exists a $\delta \in \{-1, 0, 1\}^n$ such that $\sum{\delta_i a_i} = 0$ and $\forall i\in S: \delta_i = \epsilon_i$. In other words, the hyperplane normal to $a_1, \ldots, a_n$ contains the entire subcube corresponding to $S$ (i.e. the projection of the full dimensional cube onto the coordinate subspace corresponding to $S$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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