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

CC BY-SA 3.0
2013-04-19T17:17:26.510Z
2013-04-19T17:17:26.510Z
domotorp
<p>Just to add to Domotor's answer, any hyperplane whose normal vector has polynomially bounded coefficients (in fact bounded by $2^{o(n)}$) contains <em>an entire face</em> (i.e. subcube) of the cube of dimension $n - o(n)$. This follows from the <a href="http://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/" rel="nofollow">Sauer-Shelah lemma</a>. </p>

<p>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$).</p>

CC BY-SA 3.0
2013-04-20T00:29:39.460Z
2013-04-21T19:05:14.623Z
2013-04-21T19:05:14.623Z
Sasho Nikolov
<p>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.</p>

<p>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?</p>

<co.combinatorics><cg.comp-geom>
Hyperplanes not intersecting points on a cube
Aaron Schild
# Hyperplanes not intersecting points on a cube

(Asked by: username_0 on 2013-04-19)

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?

**Tags:** co.combinatorics, cg.comp-geom

---

## 2 answers

### Answer by username_1 on 2013-04-19. Score: 8 | Accepted answer

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


---

### Answer by username_2 on 2013-04-20. Score: 3

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](http://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/).

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


---

