Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ space whether $m\cdot n=p$. I wonder whether one can prove that it isn't possible to check in $O(\log N)$ space3 whether $m\cdot n=p$. On the other hand, are there any known non-trivial upper bounds on the space complexity of this problem, like $O(N/\log N)$?
The problem described above is a simplified version of the "Multiplication decision problem: Is the $k$th bit of the product of $m$ and $n$ a one?" Since this problem is more "powerful" (and also better known), I wonder whether one can show that this problem can't be decided in $O((\log N)^2)$ space.
1. The interleaved binary encoding starts with the lowest significant bit, and allows "leading" zeros for the most significant bits.
2. The proof idea I have in mind would use such an algorithm as building block for a decision procedure of Robinson arithmetic. I call this less obvious, because the fact that Robinson arithmetic is undecidable may be well known, but still remains non-trivial.
3. Here $N$ is the length of the input $m$, $n$ and $p$ in binary encoding.