I heard in a talk today that the problem of tensor rank over $\mathbb{Q}$ is not even known to be decidable and it is equivalent to the existential theory of over that field. Did not interrupt the speaker since I thought this should be an easy exercise. However I'm finding it quite hard to construct such a formula explicitly.
For matrix rank, I thought I could use the definition that a matrix is of rank $r$ if and only if it can be written as a sum of $r$ rank 1 matrices (which again can be decomposed as $vw^T$ for vectors $v$ and $w$). Now I can set up a system of quadratic equations and quantify over the variables inside. Is this correct?
How would one go about writing such a formula for tensors? The naive way seems to require for a tensor $T:[n]^d \to \mathbb{F}$, something like $n^d$ variables and an equal number of degree $d$ polynomial equations, which seems a little large to me. I heard in the talk that over $\mathbb{R}$, one can then use Tarksi's existential theory of reals (or one of its many efficient implementations) to decide the truth of the formula.
Can someone provide an explicit first order formula for Tensor rank?