# Characterizing normal vectors of affinely independent subsets of the hypercube

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?

• 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. – user35593 Mar 1 '16 at 13:00
• 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. – Kevin P. Costello Mar 1 '16 at 23:50