Suppose we are looking at the hypercube in $\mathbb{R}^n$. I tend to the think of the cube with vertex coordinates 0 or 1, but maybe this is easier for the $\pm1$ cube.

Now suppose we have an affine hyperplane that intersects at least $n$ points of the hypercube. Is there any condition on the coordinates of the normal vector? Are they bounded in some way?

  • 1
    $\begingroup$ Trivially the normal vector $v=(v_1,\dots,v_n)$ is such that there exist $c\in \mathbb{R}$ and at least $n$ subsets $A\subset \{1,\dots,n\}$ with $\sum_{i\in A} v_i=c$. I doubt that there is an easier condition for that. Examples are vectors where at least $\lceil \log_2(n)\rceil$ entries are equal. $\endgroup$ – user35593 Mar 1 '16 at 13:00
  • 2
    $\begingroup$ If $n$ is large, $A$ is fixed, and the hyperplane intersects $n^{-A} 2^{n}$ points, then we have a great deal of structural information about the coordinates of the normal vector. This is studied under the name of "Inverse Littlewood-Offord Theory"; look in particular at the work of Tao-Vu, Nguyen-Vu, and Rudelson-Vershynin. For the range you're looking at, I think (as user35593 suggests), there will not be much of a condition. As another example, if all coordinates are at most $2^n n^{-2}$, then some affine plane in that direction hits $n$ points by Pigeonhole alone. $\endgroup$ – Kevin P. Costello Mar 1 '16 at 23:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.