I just found this problem. If you try the matrix $A^nB^m$, then your question for such matrices is equivalent to this number theory question: Can
$9^n+2cdot 9^ncdot 2^m-12cdot 3^ncdot 2^m+2cdot 3^n+4^{m}cdot 9^n+4^{m}+2cdot 2^m+9$
be a square provided $m,nne 0$. Note that if we denote $3^n$ by $x$, $2^m$ by $y$, we get a quartic polynomial in $x,y$. I hope number theorists here can say something about this exponential Diophantine equation.
The answer to problem with question mark is "obviously NO". To be undecidable, you should have a mass problem. For given $A,B$, you have the following problem:
given a product $W(A,B)$ is it true that the matrix has an integer eigenvalue. That problem is obviously decidable. The question of whether this is true for every word $W$ requires answer "yes" or "no" and is not a mass problem. You can still ask whether it is independent from ZF or even ZFC (or unprovable in the Peano arithmetic). What Bjorn had in mind is a completely different and much harder problem when you include $A, B$ in the input and ask if for this $A$, $B$ some product $W(A,B)$ not of the form $A^n, B^m$ has an integer eigenvalue. This is a mass problem which could be undecidable (although he, of course, did not prove it). But this has nothing to do with the original question.
No comments:
Post a Comment