Vectors with $\pm 1$-s and the Combinatorial Nullstellensatz Let $S$ be a set of $k < n$ vectors of length $n$, each having each entry equal to $1$ or $(-1)$. Prove that there is a vector of length $n$ with each entry $1$ or $(-1)$ which is not orthogonal to any of the vectors in $S$.
The idea is to use the Combinatorial Nullstellensatz but I cannot find a suitable polynomial - it should contain something like $\prod_{i=1}^k (x \cdot v_i)$, where $x = (x_1,\ldots,x_n)$ are the variables and $v_1,\ldots, v_k$ are the given vectors, but I cannot think of an additional suitable term.
Any help appreciated!
 A: It seems that you are using the wrong kind of combinatorial nullstellensatz here.
The original paper showing the result, which was linked in Vezen BU's answer, and which can be found on Noga Alon's web page, uses a more refined form of combinatorial nullstellensatz (Lemma 2.1. in the paper), not on $\lbrace \pm 1\rbrace^n$ as would be expected, but on "halves" of it. For the sake of being self-contained, I reproduce this original proof here, slightly adapted.
Let $U=\lbrace \pm 1\rbrace^n$. First of all, if $n$ is odd then the scalar product of any two vectors in $U$ is always odd, so no two vectors in $U$ are orthogonal, and we are done. So we may assume without loss of generality that $n$ is even.
We will show the contraposite of the statement in the OP, namely that if $V\subseteq U$ is such that any $u\in U$ is orthogonal to at least one $v\in V$, then $|V|\geq n$.
For a sign $\varepsilon \in \lbrace \pm 1\rbrace$, let
$$
U_{\varepsilon} = \bigg\lbrace (x_1,x_2,\ldots,x_n)\in \lbrace\pm 1\rbrace ^ n \ \bigg| \  x_1x_2\ldots x_n = \varepsilon \bigg\rbrace \tag{1}
$$
Then $U_{-1}\cup U_1$ is a partition of $U$. The revelance of this partition comes from the following lemma :
Lemma. A vector $v\in U$ cannot be orthogonal to both a vector in $U_{-1}$ and a vector in $U_1$.
Proof of lemma. Suppose not, and that $v\cdot a = v\cdot b=0$ for some $a\in U_{-1},b\in U_1$. Write $v=(v_1,\ldots,v_n), a=(a_1,\ldots,a_n)$ and $b=(b_1,\ldots,b_n)$ Let $C=\lbrace k \ | \ a_k=b_k \rbrace$ and $D=\lbrace k \ | \ a_k \neq b_k \rbrace$, so that $C\cup D$ is a partition of $[|1..n|]$. If we put $c=\sum_{k\in C} v_ka_k$, and $d=\sum_{k\in C} v_ka_k$, then we have $v\cdot a = c+d$ and $v\cdot b = c-d$, and therefore $c=d=0$. Now, a sum of signs equaling zero must have an even numbers of terms, so $|C|$ and $|D|$ are even. But then $\prod_{k=1}^n a_k = \prod_{k=1}^n b_k$ which contradicts the initial hypothesis that $a\in U_{-1}$ and $b\in U_1$. This finishes the proof of the lemma.
Because of the lemma, if we put
$$
V_{\varepsilon} = \bigg\lbrace v \in V \ \bigg| \ \exists u \in U_{\varepsilon}, u \cdot v = 0 \bigg\rbrace \tag{2}
$$
Then $V_{-1}$ and $V_1$ must partition $V$, and we have separately that for any $u\in U_{\varepsilon}$ there is a $v\in V_{\varepsilon}$ orthogonal to $u$.
Say that a polynomial $P$ is multilinear iff all the monomials appearing in $P$ are of degree at most $1$ in all their variables (thus $x_1x_2x_3$ is multilinear but $x_4^2$ is not). Then we have :
Variant combinatorial nullstellensatz Suppose $P$ is a multilinear polynomial in $x_1,x_2,\ldots,x_n$ with degree $\lt \frac{n}{2}$, such that $P=0$ on $U_{\varepsilon}$. Then $P$ is the zero polynomial.
Proof of the variant combinatorial nullstellensatz. Clearly the statement for $\epsilon=1$ is equivalent to the statement for $\epsilon=-1$, using the transformation $P\mapsto P(x_1,x_2,\ldots,x_{n-1},-x_n)$. So it will suffice to show the statement for $\varepsilon=1$.
Denote by ${\cal P}_n$ the power set of $[|1..n|]$ and by ${\cal P}'_n$ the subset of ${\cal P}_n$ consisting of the even-sized subsets.
Let $I\in {\cal P}_n$ and $J\in {\cal P}'_n$. Let $M_I$ be the monomial defined by $M_I=\prod_{i\in I} x_i$, and let $u_J$ be the element of $U_1$ whose coordinates are $-1$ when the index is in $J$ and $+1$ otherwise. Then, $M_I(u_J)=(-1)^{|I\cap J|}$. The goal is then to show that the matrix $M=(M_{I}(u_J))_{I\in {\cal P}_n,J\in {\cal P}'_n}$ has full rank, but a well-known equivalent condition for that is that $M^{T}M$ be invertible. But it is straightforward to see that $M^{T}M$ is $2^{n-1}$ times the identity, so this finishes the proof of the variant combinatorial nullstellensatz.
Returning to our main proof, for $\varepsilon \in \lbrace \pm 1 \rbrace$, put
$$
F_{\varepsilon}(x)=\prod_{v\in V_{\varepsilon}} v \cdot x 
$$
Then $F_{\varepsilon}$ is zero everywhere on $U_{\varepsilon}$, nonzero everywhere on $U_{-\varepsilon}$, and has degree exactly $|V_{\varepsilon}|$. Now, let $G_{\varepsilon}$ be the polynomial obtained from $F_{\varepsilon}$ by replacing each monomial $x_1^{m_1}\ldots x_n^{m_n}$ with $x_1^{r_1}\ldots x_n^{r_n}$ where $r_j$ is the remainder of $m_i$ divided by $2$.
Then $G_{\varepsilon}$ is zero everywhere on $U_{\varepsilon}$, nonzero everywhere on $U_{-\varepsilon}$, and has degree at most $|V_{\varepsilon}|$.
By the variant combinatorial nullstellensatz above, the degree of $G_{\varepsilon}$ must be at least $\frac{n}{2}$.
Then
$$
|V|=|V_{-1}|+|V_1| \geq \frac{n}{2}+\frac{n}{2} = n,
$$
which finishes the proof.
A: Theorem
Let $F$ be an arbitrary field, and let $f = f(x_1, \ldots, x_n)$ be a polynomial in $F[x_1, \ldots, x_n]$. Suppose that the $deg(f) = \sum_{i \in [n]}t_i$ where each $t_i \in \{0, 1,2,3, \ldots\}$ with the coefficient of $\prod_{i \in [n]} x_i^{t_i}$ nonzero.
Then if $S_1, \ldots, S_n$ are subset of $F$ with $|S_i| > t_i$, there are $s_i \in S_i$, for each $i \in [n]$ s.t.
$$f(s_1, \ldots, s_n) \neq 0.$$

Proof
Let $S = \{v_1, \ldots, v_k\}$ be the set of the $k$ vectors.
Define $f(x = (x_1, \ldots, x_n)) = (\sum_{i = 1}^{n}x_i + 1)^{n-k} \prod_{i = 1}^{k} (x \cdot v_i)$ if $n$ even and $f(x = (x_1, \ldots, x_n)) = (\sum_{i = 1}^{n}x_i)^{n-k} \prod_{i = 1}^{k} (x \cdot v_i)$ if $n$ odd.
Clearly, $f(x) \neq 0$ iff $\prod_{i = 1}^{k} (x \cdot v_i) \neq 0$ iff $x$ is not orthogonal to any of the vectors in $S$.
The degree of $f$ is $n = \sum_{i \in [n]} 1$.
We need to show that the coefficient of $\prod_{i = 1}^{n} x_i$ is nonzero but honestly I cannot have a rigorous proof for that currently.
Let $S_1 = \cdots = S_n = \{-1, 1\}$ with $|S_i| = 2 > 1, \forall i \in [n]$.
By the theorem, there are $s_i \in S_i$, for each $i \in [n]$ s.t.
$f(s_1, \ldots, s_n) \neq 0$, completing the proof.

Ref: Alon, Noga. "Combinatorial nullstellensatz." Combinatorics, Probability and Computing 8.1-2 (1999): 7-29. (https://www.cs.tau.ac.il/~nogaa/PDFS/null2.pdf)

See also
Alon, Noga. "Tools from higher algebra." Handbook of combinatorics 2 (1995): 1749-1783. (http://www.cs.tau.ac.il/~nogaa/PDFS/tools1.pdf, page 25)
Alon, Noga, et al. "Balancing sets of vectors." IEEE Transactions on Information Theory 34.1 (1988): 128-130.
