A tricky problem about matrices with no $\{-1,0,1\}$ vector in their kernel A Hankel matrix is a square matrix in which each ascending skew-diagonal from left to right is constant. Let us call a matrix partial Hankel if it is the first $m<n$ rows of some $n$ by $n$ Hankel matrix. I was posed this question by a mathematician a few years ago and I have been completely stuck on it ever since.   Let us assume all our partial Hankel matrices have elements which are chosen from $\{-1,1\}$.

Does there exist an $m$ by $n$ partial Hankel matrix $M$ such that it has $m < n/2$ rows and there is no non-zero vector $v\in\{-1,0,1\}^n$ in its kernel?

Such matrices certainly do exist for non-Hankel $m$ by $n$ $\{-1,1\}$-matrices.
Other that writing computer code to exhaustively explore small matrices I am not sure how to approach this question. 
I would be very grateful for any ideas at all.
 A: It appears completely equivalent to ask this question for Toeplitz matrices instead of Hankel matrices. The reason is that arranging the $m$ rows of any partial Hankel matrix simply in reverse order turns it into a rectangular Toeplitz matrix but doesn't affect its kernel. I will give an answer for Toeplitz matrices below. 
In another answer at MathOverflow I have argued that for "typical" $m$ by $n$ $\{0,1\}$-matrices $M$, regardless of whether they have Toeplitz (or circulant) form or not (in other words, they are chosen at random either among all $m$ by $n$ $\{0,1\}$-matrices, with uniform distribution, or within the subsets of Toeplitz or circulant matrices), the following holds: 

If $w \in \{-1,0,1\}^n$ is a random vector with i.i.d. components, distributed with probabilities $P(w_i = -1) = P(w_i = 1) = \frac14$ and $P(w_i=0) = \frac12$, then the probability of $w$ lying in the kernel of $M$ is asyptotically (for large $n$) given by 
  $$
P(Mw=0) \sim 
\begin{cases}
\quad 2^{-n} \ , \quad m > \frac{2n}{\log_2 ( \pi n/6)} \\
m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ , \quad m \leq \frac{2n}{\log_2 ( \pi n/6)} 
\end{cases} \ . 
\hspace{2cm} (1)
$$

An intermediate step of this argument effectively supports an even stronger claim, namely that for all $m$
$$
P(Mw=0) - 2^{-n} \sim m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ . 
\hspace{2cm} (2)
$$
Since $w=0$  is always a solution of $Mw=0$ and has probability $P(w=0) = 2^{-n}$, the right hand side is essentially the asymptotic probability that $Mw=0$ with some $w \neq 0$. Consequently, since by definition every vector $w \in \{-1,0,1\}^n$ has at least probability $4^{-n}$, the probability that there exists at least one $w \neq 0$ with $Mw=0$ must then, with some suitable constant $\alpha>1$ and for large enough $n$, obey the following inequality: 
$$
P(\exists w \neq 0 : Mw=0) \leq \alpha \, 4^n m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ . 
\hspace{2cm} (3)
$$
Again, this supposes that $M$ is a random matrix, with uniform distribution over the set of all $m$ by $n$ $\{0,1\}$-matrices, or over the subset of Toeplitz matrices. 
An adaptation of the above argument to $\{-1,1\}$-matrices $M$ is completely straightforward; the eigenvalues of $MM^{\rm T}$ are just scaled by a factor of $4$ (i.e. they asymptotically tend now to $n$ instead of $\frac n4$) and the single large eigenvalue $\sim \frac{mn}4$ disappears. The above inequality $(3)$ then becomes instead 
$$
P(\exists w \neq 0 : Mw=0) \leq \alpha \, 4^n \left( \frac{2\pi n}3 \right)^{-\frac m2} \ . 
\hspace{2cm} (4)
$$
The base 2 logarithm of the expression on the right hand side is $\log_2\alpha + 2n - \frac m2 \log_2 \left( \frac{2\pi n}3 \right)$, and so for $m > \beta \frac{4n}{\log_2 ( 2\pi n/3)}$ (with some constant $\beta>1$ of our choice) it will be bounded from above by $\alpha \, 4^{(1-\beta)n}$ and thus become arbitrarily small for large enough $n$. Recall that this is an upper bound on the probability that any randomly chosen $m$ by $n$ matrix $M$ (of the required form) will admit a nontrivial solution $w \in \{-1,0,1\}^n$ of the equation $Mw=0$. For given $n$ and $m$ there is a number $2^{n+m-1} \gg 1$ of such matrices of Toeplitz type (or $2^{nm} \gg 1$ of general form), so the probability that every single one of these will admit such a nontrivial solution must become overwhelmingly small for large $n$. 

In conclusion, what the above argument tells us is that if we choose some $\beta>1$ and consider the $m$ by $n$ $\{-1,1\}$-matrices $M$, with sufficiently large $n$ and any $m$ obeying 
  $$
m > \beta \frac{4n}{\log_2 \left( \frac{2\pi n}3 \right)} \ , 
\hspace{2cm} (5)
$$
  then with overwhelming probability there will be at least one among these matrices which has the wanted property (i.e. at least one $M$ which does not admit any nontrivial solution of $Mw=0$). This holds independently of whether we require in addition that $M$ has a Toeplitz, Hankel or circulant form. Moreover, not just one but probably the majority of all matrices of the specified form will have the wanted property.  

Note that the condition $(5)$ is asymptotically weaker than $m>n/c$ for any real constant $c>1$, which implies that for any such $c$ and sufficiently large $n$ there should exist $n$ by $m$ Toeplitz (Hankel, ...) matrices with $m<n/c$ which have the wanted property. In the Question, $c=2$ was chosen. 
A final note: Of course, in the present form the entire argument is not mathematically rigorous, since it relies on several uncontrolled approximations. I believe, however, that with a little effort these holes can be filled. 
A: This is a comment on Dierk Bormann's answer with roughly the same estimate.
The case $m< c\frac{n}{\log n}$ can be done using the pigeonhole principle.
For every vector $\mathbf{x}\in\{0,1\}^n$, take the $m$-vector $M\mathbf{x}$.
Every coordinate of $M\mathbf{x}$ is some integer in the interval $[-n,n]$. So there are $2^n$ choices for the vector $\mathbf{x}$, and at most $(2n+1)^m$ possible results for $M\mathbf{x}$. If $2^n>(2n+1)^m$ then there are some vectors $\mathbf{x},\mathbf{y}\in \{0,1\}^n$ such that 
$M\mathbf{x}=M\mathbf{y}$. Then $v=\mathbf{x}-\mathbf{y}$ satisfies the requred properties.
So a suitable vector $v$ exists if $2^n>(2n+1)^m$, or equivalently $m<\frac{n}{\log_2(2n+1)}$.
This works for all $m\times n$ matrices with entries from a fixed set of integers, so it does not use the special form of $M$.

Another approach is applying Minkowski's theorem. I did not have time to work it out for this case, it requires some unpleasant estimates, but it is clear to me that the same $m<c\frac{n}{\log n}$ can be achieved, and perhaps it is possible improve the estimate using the stucture of $M$.
The idea is as follows.
We need a vector $v$ from the kernel of $M$, such that every $v_i$ is an integer, lying in the interval $(-2,2)$.
The kernel $\mathrm{ker}\,M = \{x\in\mathbb{R}^n: Mx=0\}$ is a subspace of $\mathbb{R}^n$ with dimension $d$; obviosly $d\ge n-m$.
The integer vectors in this subspace form a lattice. We need an upper bound on the $d$-volume of the lattice parallelepiped.
We need a suitable lower bound on the $d$-volume of the set 
$K = (-2,2)^n \cap \mathrm{ker}\,M$ which is convex and symmetric wrt. the origin.
If the ratio of the two volumes is high enoough, we can apply Minkowski's theorem.
