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?
Best Answer
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. 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): 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.