Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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$).
