# How many hyper-rectangle-like objects are intersecting a hyperplane?

Let $A\in \mathbb R^{n\times n},\ b\in \mathbb R^n$ such that $\forall x\in \{-1,1\}^n : Ax\ne b$.

Let us denote: $S=\{x\in\mathbb R^n|Ax=b\}$ ('S' for solution set).

Is $\ \#\Big\{H\in\big\{ \{-1\}, \{1\}, (-1,1)\big\}^n \ \Big|\ H\cap S\ne\emptyset\ \Big\} = O(n)$?

where '#' denotes the cardinality of the set.

My intuition tells me that this should be true, but I can't figure out how to prove or disprove it.

So far, I've done many trial and error "experiments" that also support my conjecture, but I am stuck in proving/ disproving it in the general case.

By the way, it is easy to see that WLOG the solution set is a hyper-plane. So, we can modify $S$ to be $S=\{x\in\mathbb R^n|a^T x=b\}$ for $a\in\mathbb R^n, b\in\mathbb R$ such that $\forall x\in \{0,1\}^n:a^T x\ne b$.

• I think you mean certain equivalence classes of points. Are you asking how many faces intersect a solution set? By the way, if b is zero and A is zero, the answer is probably "No", so you should expect an answer conditional on the real rank of A. Gerhard "Unsure Which Grouping Is Used" Paseman, 2018.09.19. – Gerhard Paseman Sep 19 '18 at 18:07
• @GerhardPaseman I edited my question and added some more essential requirement: that $\forall x\in \{0,1\}^n : Ax\ne b$. – Dudi Frid Sep 19 '18 at 20:11
• @DudiFrid: I believe that you may drop the corners $\{-1\}^n$ and $\{1\}^n$, because they are always just two points, and this does not change the asymptotics. – Alex M. Sep 19 '18 at 20:12
• @AlexM. My bad, it was just a typo. Thanks for pointing it out – Dudi Frid Sep 19 '18 at 20:15
• @DudiFrid: Notice that I have made a change in the definition of the set that you are describing, please check whether it conveys what you meant to say. – Alex M. Sep 19 '18 at 20:19

Just take $\sum x_i=n-1$ and you get $O(n\cdot2^n)$ instead of $O(n)$.