Let $A$ be a non-zero symmetric $n \times n$-matrix with integer entries and suppose that $\det(A) =0$.



> 
> **Question:** How long is the shortest non-zero integer vector in the kernel of $A$?
> 
> 
> 


Example: If $A$ has non-zero eigenvalues $\xi\_1,\dots,\xi\_k$ (not necessarily counting with multiplicities), then the polynomial $p(t) = (\xi\_1-t) \cdots (\xi\_k -t)$ has integer coefficients. Hence, $p(A) \in M\_n {\mathbb Z}$ and at the same time $Ap(A)=0$. Clearly, 
$$p(A) = {\rm det}'(A) \cdot Q\_{\ker(A)},$$
where $\det'(A) := \xi\_1 \cdots \xi\_k$ and $Q\_{\ker(A)}$ denotes the orthogonal projection onto the kernel of $A$. Hence, we get for the operator norm $\|p(A)\| = |\det'(A)|$. Now, there exists an index $1 \leq i \leq n$, such that $v:=p(A)e\_i \neq 0$ and one gets $\|v\| \leq \det'(A)$. At the same time $v$ has integer entries and lies in the kernel of $A$.


In many examples one can do much better. I would hope someone is able to bound the length in terms of the operator norm of $A$ alone. Is that possible? 


The problem can also be phrased in terms of additive combinatorics. Indeed, if one identifies the image of ${\mathbb Z}^n$ under $A$ with ${\mathbb Z}^{k}$ for some $k < n$, then injectivity of $A$ on the set $X=\lbrace-m,\dots,m\rbrace ^n$ implies that $X$ can be embedded in ${\mathbb Z}^k$ preserving the addition whenever it made sense on $X$. This alone seems to require a lot of distortion, i.e. a large operator norm of $A$.


What kind of literature can be recommended?



Integer vectors in the kernel of an integer matrix

> 
> I would hope someone is able to bound the length in terms of the operator norm of alone. Is that possible? 
> 
> 
> 


This is not possible. Consider the group ring $\mathbb ZC\_k$ of the cyclic group $C\_k$ of order $k$. 
Consider $1-t\in \mathbb ZC\_k$. As an operator on $l^2C\_k$ it has 1-dimensional kernel generated by $v\_k:=1+t+\ldots +t^{k-1}$. Vector $v\_k$ has arbitrary large length, yet the oeprator $1-t$ has a bounded norm.


If you want to get a symmetric operator use the standard trick, i.e. take $(1-t^{-1})(1-t)$ which has the same kernel and only slightly bigger norm.


I also thought about this question in relation to [my recent question](https://mathoverflow.net/questions/40465/regular-languages-of-matrices-and-their-generating-functions). I don't know what application do you have in mind, but maybe what you're looking for is a statement like this (using notation from [my question](https://mathoverflow.net/questions/40465/regular-languages-of-matrices-and-their-generating-functions)): let $\mathcal M$ be a regular family of matrices recognized by an automaton $A$. Suppose there exists $M\in \mathcal M$ such that $\det M=0$. Then there exists a matrix $N\in \mathcal M$ and a vector $v\in \mathbb Z^{\dim N}$ such that $Nv=0$ and the length of $v$ can be bounded by "size of $A$".


"Size of $A$" is some function which depends only on number of letters in the alphabet of $A$ and number of states of $A$. I'm not sure yet the above statement is true but, well, I'm "convinced" it is :-).


The family of operators $1-t$ above gives rise to a regular family of matrices if we allow finite automata which work with a circular tape.


