1 Introduction

In the last fifty years, it became clear that multiarrays with more than two indices, known as tensors, are vital tools in data processing [19], mathematical biology [1], numerical linear algebra [29], quantum physics [4], theoretical computer science [5] and theoretical mathematics [18]. Formally, we define a d-tensor, as a multiarray with \(d\geqslant 3\) indices. One of the simple criteria of the complexity of a given tensor is its rank. (The concept of tensor rank has been introduced in the early twentieth century [16].) Recall that the rank of a nonzero tensor is the minimum number of terms in a decomposition of tensor as a sum of rank-one tensors. The famous Strassen algorithm for multiplication of two matrices of order two using seven multiplication [28] and not less is equivalent to the statement that the corresponding \(4 \times 4\times 4\) tensor has rank seven. The 3-satisfiability problem with n variables and m clauses can be stated if a given 3-tensor has a specific rank [15]. This result yields that the computation of the rank of tensor over any finite field is NP-complete, and is NP-hard over fields of rational, real and complex numbers.

On the other hand, the rank of a matrix is a well-understood notion, which has many equivalent definitions. The computation of the rank of matrix is usually obtained by applying the Gaussian elimination process. Namely, it is the number of nonzero rows in the row echelon form obtained from the Gaussian elimination process. See [11] for classical results on matrix rank.

The point of this note is the following statement. Suppose that \(\mathcal {T}\) is a d-tensor over a given field \(\mathbb {F}\). Denote its rank by rank\(_\mathbb {F}\mathcal {T}\). Assume that \(\mathbb {G}\) is an extension field of \(\mathbb {F}\). Then, rank\(_\mathbb {G}\mathcal {T}\leqslant\)rank\(_\mathbb {F}\mathcal {T}\), and strict inequality may hold [12]. Denote by \({\hat{\mathbb {F}}}\) the algebraic closure of \(\mathbb {F}\). Let \(k\geqslant 2\) be an integer. Then, rank\(_{{\hat{\mathbb {F}}}}\mathcal {T}>k\) if and only if certain systems of linear equations are solvable over \(\mathbb {F}\). Since rank\(_{{\hat{\mathbb {F}}}}\mathcal {T}\) is NP-hard to compute one expects the linear system is exponential in number of variables. Our techniques also apply to symmetric tensors and their symmetric rank [7]. Our main result is a consequence of an effective Nullstellensatz [17].

The main drawback of our approach is a huge number of variables and equations that one encounters in trying to apply an effective Hilbert Nullstellensatz. We hope that our approach can be further improved to a smaller number of variables and equations for the specific problem of tensor rank.

Over finite fields, one can study directly the problem of determining if the rank of a given tensor is at most k. A recent paper [20] gave a probabilistic algorithm to find solution of polynomial equations over a finite field with high probability. We will compare the complexity of our method with the above result.

2 Preliminary Results

Let \(\mathbb {F}\) be a field and \(d\in \mathbb {N}\). Denote

$$\begin{aligned}{}[d]= & {} \{1,\cdots ,d\},\mathbf {n}=(n_1,\cdots ,n_d)\in \mathbb {N}^d, [\mathbf {n}]=[n_1]\times \cdots \times [n_d], \\N(\mathbf {n})= & {} \prod _{j=1}^d n_j, L(\mathbf {n})=\sum _{j=1}^d n_i, \mathbb {F}^{\mathbf {n}}=\otimes _{j=1}^d \mathbb {F}^{n_j}. \end{aligned}$$

The entries of \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}\) are denoted by \(\mathcal {T}_{i_1,\cdots ,i_d}, i_j\in [n_j],j\in [d]\), and we view \(\mathcal {T}\) as \([\mathcal {T}_{i_1,\cdots ,i_d}]\). Then, \(\mathcal {T}\) is a matrix for \(d=2\) and a tensor for \(d\geqslant 3\). A tensor \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}{\setminus }\{0\}\) is called a rank-one tensor if \(\mathcal {T}=\otimes _{j=1}^d \mathbf {x}_j\) for \(\mathbf {x}_j\in \mathbb {F}^{n_j}{\setminus }\{\mathbf {0}\}, j\in [d]\). Recall that for a tensor \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}{\setminus }\{0\}\), the rank of \(\mathcal {T}\) is the minimal number of terms in the decomposition \(\mathcal {T}=\sum\limits _{i=1}^r \otimes _{j=1}^d \mathbf {x}_{j,i}\). (The rank of zero tensor is zero.)

The unfolded rank of \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}\) in mode \(j\in [d]\) denoted as \(r_j(\mathcal {T})\) is defined as follows. For simplicity of exposition, let us explain the notion \(r_1(\mathcal {T})\). View tensor \(\mathcal {T}\) as a matrix \(T\in \mathbb {F}^{n_1}\otimes (\otimes _{j=2}^d \mathbb {F}^{n_j})\). Then, \(r_1(\mathcal {T})\) is \({\text {rank}}\, T\). We denote by \(\mathbf {g}_{1,1},\cdots ,\mathbf {g}_{r_1(\mathcal {T}),1}\) a column basis of T. Clearly, \(r_1(\mathcal {T})\leqslant n_1\). Let \(\mathbf {V}_1=\) \(\text{span}(\mathbf {g}_{1,1},\cdots ,\mathbf {g}_{r_1(\mathcal {T}),1})\subseteq \mathbb {F}^{n_1}\). Similarly, we define the rank \(r_j(\mathcal {T})\), the column space \(\mathbf {V}_j\subseteq \mathbb {F}^{n_j}\), and a basis \(\mathbf {g}_{1,j},\cdots ,\mathbf {g}_{r_j(\mathcal {T}),j}\) in \(\mathbf {V}_j\). It is known that for \(d\geqslant 3\), it is possible that all \(r_j(\mathcal {T}), j\in [d]\) are different. Observe that \(\mathcal {T}\) can be viewed as a tensor in  \(\otimes _{j=1}^d \mathbf {V}_j\). Introduce a new basis in \(\mathbb {F}^{n_j}\), such that a basis of \(\mathbf {V}_j\) is part of this basis. Hence, we can convert the tensor \(\mathcal {T}\) to a “smaller” tensor \(\mathcal {T} '\in \mathbb {F}^{\mathbf {r}}, {\mathbf {r}}=(r_1(\mathcal {T}),\cdots ,r_d(\mathcal {T}))\). For simplicity of the exposition, we assume

$$\begin{aligned} 1\leqslant n_1\leqslant \cdots \leqslant n_d, \; r_j(\mathcal {T})=n_j \text { for }j\in [d]. \end{aligned}$$
(1)

It is well known that \(n_d\leqslant {\text {rank}}\,\mathcal {T}\leqslant \prod\limits _{i=1}^{d-1}n_i\) [9]. Thus, we are going to assume that

$$\begin{aligned} n_d\leqslant r\leqslant \prod _{i=1}^{d-1}n_i. \end{aligned}$$
(2)

Clearly, \({\text {rank}}\,\mathcal {T}>r\) if and only if the system

$$\begin{aligned} \sum _{i=1}^r \otimes _{j=1}^d \mathbf {x}_{j,i}-\mathcal {T}=0 \end{aligned}$$
(3)

is not solvable over \(\mathbb {F}\).

Assume that \(n_1=\cdots =n_d=n\). Denote \(n^{\times d}:=\mathbf {n}\). A tensor \(\mathcal {S}\in \mathbb {F}^{n^{\times d}}\) is called symmetric if \(\mathcal {S}_{i_1,\cdots ,i_d}=\mathcal {S}_{i_{\sigma (1)},\cdots ,i_{\sigma (d)}}\) for each \(i_1,\cdots ,i_d\in [n]\) and each bijection \(\sigma\! :[d]\rightarrow [d]\). We denote by \(\mathrm{S}^d\mathbb {F}^n\subset \mathbb {F}^{n^{\times d}}\) the subspace of symmetric tensors. It turns out that \(\dim \mathrm{S}^d\mathbb {F}^n={n+d-1\atopwithdelims ()d}\). As \(\mathrm{S}^d\mathbb {F}^n\subset \mathbb {F}^{n^{\times d}}\), it follows that \({n+d-1\atopwithdelims ()d}\leqslant n^d\). It is well known that a symmetric tensor has rank one if \(\mathcal {S}=a\otimes ^d\mathbf {x}\), where \(a\in \mathbb {F}{\setminus }\{0\}, \mathbf {x}\in \mathbb {F}^n{\setminus }\{\mathbf {0}\}\). Also if \(\mathbb {F}\) has at least d elements, then each \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n\) is a sum of rank-one symmetric tensors [13, Proposition 7.2]. (It is shown in [13, Proposition 7.1] that for a fixed finite field \(\mathbb {F}\) and \(n\geqslant 2\), there exist symmetric tensors which are not sum of rank-one symmetric tensors for sufficiently large d.) In the following passage, we assume that \(|\mathbb {F}|\geqslant d\). We define \({\text {srank}}\,\mathcal {S},\) the symmetric rank of \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n{\setminus }\{0\}\), as the minimal number in the decomposition of \(\mathcal {S}\) as a sum of rank-one symmetric tensors. For matrices over a field of characteristic \(\ne 2\), the symmetric rank of \(\mathcal {S}\in \mathrm{S}^2\mathbb {F}^n\) is equal to the (standard) rank of \(\mathcal {S},\) whereas for \(d\geqslant 3\) there are examples of 3-symmetric tensors whose symmetric rank is greater than their tensor rank [27]. Observe that for a symmetric \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n\) one has the equality \(r_j(\mathcal {S})=r(\mathcal {S})\) for each \(j\in [d]\). In this case, we assume that \(n=r_1(\mathcal {S})\) and \(n\leqslant r\).

Let \(f(\mathbf {x})\) be a homogeneous polynomial of degree d in n variables:

$$\begin{aligned} f(\mathbf {x})= & {} \sum _{ j_k+1\in [d+1],k\in [n], j_1+\cdots +j_n=d} \frac{d!}{j_1!\cdots j_n!} f_{j_1,\cdots ,j_n} x_1^{j_1}\cdots x_n^{j_n}\\= & {} \sum _{\mathbf {j}\in J(d,n)} c(\mathbf {j})f_{\mathbf {j}}\mathbf {x}^{\mathbf {j}}, \quad \mathbf {x}^{\mathbf {j}}=x_1^{j_1}\cdots x_n^{j_n}, c(\mathbf {j})=\frac{d!}{j_1!\cdots j_n!},f_{\mathbf {j}}=f_{j_1,\cdots ,j_n},\\ J(d,n)= & {} \{\mathbf {j}=(j_1,\cdots ,j_n)\in \mathbb {Z}_+^n,\; j_1+\cdots +j_n=d\}. \end{aligned}$$

Every symmetric tensor \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n\) defines a homogeneous polynomial of degree d in n-variables, which is given by the scalar product of \(\mathcal {S}\) and \(\otimes ^d \mathbf {x}\). Conversely, a homogeneous polynomial \(f(\mathbf {x})\) of degree d in n variables defines a unique symmetric \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n\), such that \(f(\mathbf {x})\) is given by the scalar product of the symmetric tensors \(\mathcal {S}\) and \(\otimes ^d \mathbf {x}\). (See part (4) of Lemma 1 in [14].) Denote by \(\mathrm{P}(d,n,\mathbb {F})\) the space of all homogeneous polynomials of degree d in n variables over \(\mathbb {F}\).

A polynomial in n variables of degree at most d has the representation

$$\begin{aligned} f(\mathbf {x})=\sum _{ j_k+1\in [d+1],k\in [n], j_1+\cdots +j_n\leqslant d} \frac{d!}{j_1!\cdots j_n!} f_{j_1,\cdots ,j_n} x_1^{j_1}\cdots x_n^{j_n}. \end{aligned}$$
(4)

Let \(\mathbf {x}'=(x_1,\cdots ,x_{n+1})=(\mathbf {x},x_{n+1})\). Then, \(f(\mathbf {x})\) of the above form is \(g(\mathbf {x},1)\) for a unique \(g(\mathbf {x}')\in \mathrm{P}(d,n+1,\mathbb {F})\).

Assume that \(\mathbb {G}\) is an extension field of \(\mathbb {F}\). Given \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}{\setminus }{0}\), one can ask what the rank of \(\mathcal {T}\) over \(\mathbb {G}\) is? That is, what is the minimum number of terms in a decomposition of \(\mathcal {T}\) as a sum of rank-one tensor, where each rank-one tensor is in \(\mathbb {G}^{\mathbf {n}}\). We denote this rank by rank\(_\mathbb {G}\mathcal {T}\). (When no ambiguity arises we denote rank\(_\mathbb {F}\mathcal {T}\) by \({\text {rank}}\,\mathcal {T}\).) Clearly, rank\(_\mathbb {G}\mathcal {T}\leqslant\)rank\(_\mathbb {F}\mathcal {T}\). It is well known that in some cases strict inequality holds [12]. Similar results hold for symmetric rank of symmetric tensors.

3 Outline of Our Approach

It is well understood that matrices are closely related to linear transformations, while tensors are closely related to polynomial maps [9]. More precisely, as we have mentioned, it is a classical result that the rank of a matrix is polynomially computable, using the Gauss elimination. In contrast to matrix rank, the tensor rank is unfortunately NP-hard to compute, as proven by Hastad [15]. Later, Schaefer and Stefankovic [24] showed that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of the field, which implies Hastad’s NP-hardness results. Another result of Hastad states that the rank decomposition problem is NP-complete in the case of finite fields. Recently, Shitov [26] showed that rank over a field \(\mathbb {F}\) is complete for the existential theory of \(\mathbb {F}\) and is also uncomputable over \(\mathbb {Z}\).

Let \(\mathbb {F}\) be a given field and \({\hat{\mathbb {F}}}\) be its algebraic closure. Let \(d\geqslant 3.\) We aim to find the upper bounds for the bit complexities for the following problems:

  1. (i)

    for a tensor \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}},\) to determine if \({\text {rank}}\,\mathcal {T}\) over the field \({\hat{\mathbb {F}}}\) is \(\leqslant r,\) for a fixed integer \(r \geqslant 2;\)

  2. (ii)

    for a symmetric tensor \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^n\), to determine if \({\text {srank}}\,\mathcal {S}\) over \({\hat{\mathbb {F}}}\) is \(\leqslant r,\) for a fixed integer \(r \geqslant 2\).

We start with the following obvious lemma.

Lemma 1

Let \(3 \leqslant d\) and \(2\leqslant n_1\leqslant \cdots \leqslant n_d\) be integers. Assume that \(\mathcal {T}\in \mathbb {F}^{\mathbf {n}}\). Then \(r<{\text {rank}}\,\mathcal {T}\) if and only if the system of \(N(\mathbf {n})\) polynomial equations (3) in rd vector variables \(\mathbf {x}_{1,1},\cdots , \mathbf {x}_{d,1},\cdots ,\mathbf {x}_{1,r},\cdots ,\mathbf {x}_{d,r}\), with a total number of \(rL(\mathbf {n})\) variables, of degree d is not solvable.

Note that to decide the rank of 3-mode tensor \(\mathcal {T}\) over \(\mathbb {C}\) is an NP-hard problem, while deciding the rank of 3-mode tensor over \(\mathbb {F}=\mathbb {Z}/(p\mathbb {Z})\) is an NP-complete problem.

Over an algebraically closed field, this statement is equivalent to the fact that the ideal generated by \(N(\mathbf {n})\) polynomials which are entries of the left-hand side of (3) contains the constant function 1. Thus, for a given \(r\geqslant n_d\), the system (3) reduces to \(N(\mathbf {n})\) equations, with \(M(r)=rL(\mathbf {n})\) variables. Note that \(M(r,\mathbf {n})\leqslant dr^2\) variables. For simplicity of the exposition, we are going to assume that r is small enough so that the number of variables is less than or equal to the number of equations:

$$\begin{aligned} M(r,\mathbf {n})=rL(\mathbf {n})\leqslant N(\mathbf {n}). \end{aligned}$$

We now recall an efficient version of Hilbert Nullstellensatz [17, 1.9. Corollary]. (See [2, 3, 8] for recent improvements on Hilbert’s Nullstellensatz.) Assume first that \(\mathbb {F}=\mathbb {C}\). Denote by \(\mathbb {Z}[\mathbf {i}]\) the Gaussian integers.

Lemma 2

Let \(\mathcal {T}\in \mathbb {Z}[\mathbf {i}]^{\mathbf {n}}\) be given. Then, the complexity of deciding if \({\text {rank}}\,\mathcal {T}> r\) is at most the complexity of finding if the linear system in the coefficients of polynomials \(g_1,\cdots ,g_{N(\mathbf {n})}\)

$$\left\{\begin{array}{lll}\sum\limits _{i=1}^{N(\mathbf {n})}g_i(\mathbf {z})f_i(\mathbf {z})=1,\\ g_i(\mathbf {z})\in \mathbb {C}[\mathbb {C}^{M(r,\mathbf {n})}], \; \deg g_i\leqslant d^{M(r,\mathbf {n})-1}, \;i\in [N(\mathbf {n})] \end{array}\right.$$
(5)

is solvable over \(\mathbb {Q}[\mathbf {i}]\) in precise arithmetic.

Proof

Lemma 1 yields that the system of \(N(\mathbf {n})\) polynomial equations (3) is not solvable if and only if \({\text {rank}}\,\mathcal {T}>r\). As \(\mathbb {C}\) is algebraically closed the assumption that \({\text {rank}}\,\mathcal {T}>r\) yields that there exist \(N(\mathbf {n})\) polynomials \(g_1,\cdots ,g_{N(\mathbf {n})}\) such that the system (5) is solvable. The efficient version of Hilbert Nullstellensatz [17, 1.9. Corollary] yields that the degree of each \(g_i\) is at most \(d^{M(r,\mathbf {n})-1}\). Write each \(g_i(\mathbf {z})\) in the form (4) of degree \(d^{M(r,\mathbf {n})-1}\), where the monomial coefficients of each \(g_i(\mathbf {z})\) are unknown variables. Then, the existence of \(g_1,\cdots , g_{N(\mathbf {n})}\) of degrees at most \(d^{M(r,\mathbf {n})-1}\) that satisfy (5) is equivalent to the solvability of the system of linear equations in the monomial coefficients of each \(g_i(\mathbf {z})\) induced by (5).

Thus, for a fixed r, the complexity of determining the solvability of this system of linear equations is as follows.

One can view a polynomial \(p(\mathbf {z})\) of degree \(d^{M(r,\mathbf {n})-1}\) in \(M(r,\mathbf {n})\) variables as a homogeneous polynomial of degree \(d^{M(r,\mathbf {n})-1}\) with \(M(r,\mathbf {n})+1\) variables, where the variable \(x_0\) has value 1. Hence, the number of monomials appearing in \(p(\mathbf {z})\) is \({M(r,\mathbf {n})+d^{M(r,\mathbf {n})-1}\atopwithdelims ()d^{M(r,\mathbf {n})-1}}={M(r,\mathbf {n})+d^{M(r,\mathbf {n})-1}\atopwithdelims ()M(r,\mathbf {n})}\). As we observed,

$$\begin{aligned} {M(r,\mathbf {n})+d^{M(r,\mathbf {n})-1}\atopwithdelims ()M(r,\mathbf {n})}= & {} {(d^{(M(r,\mathbf {n})-1}+1)+M(r,\mathbf {n})-1\atopwithdelims ()M(r,\mathbf {n})}\leqslant (d^{(M(r,\mathbf {n})-1}+1)^{M(r,\mathbf {n})}\\= & {} (1+d^{-(M(r,\mathbf {n})-1)})^{M(r,\mathbf {n})} d^{(M(r,\mathbf {n})-1)M(r,\mathbf {n})}\\\leqslant & {} (1+1/M(r,\mathbf {n}))^{M(r,\mathbf {n})}d^{(M(r,\mathbf {n})-1)M(r,\mathbf {n})}\\\leqslant & {} \text{e}d^{(M(r,\mathbf {n})-1)M(r,\mathbf {n})}. \end{aligned}$$

Here \(\text{e}=\lim\limits _{m\rightarrow \infty }(1+1/m)^m=2.718\cdots\). Hence, the total number of coefficients of monomials in each \(g_i(z)\) is bounded above by \(\text{e}d^{(M(r,\mathbf {n})-1)M(r,\mathbf {n})}\). We call these coefficients linear variables. Thus, the total number of linear variables is bounded above by \(\text{e} N(\mathbf {n})d^{M(r,\mathbf {n})(M(r,\mathbf {n})-1)}\). The number of equations is the number of monomials which is bounded above by \(\text{e}d^{M(r,\mathbf {n})(M(r,\mathbf {n})-1)}\). Thus, if we use the Gauss elimination to determine if this system of linear equations is solvable or not, we need \(O(N(\mathbf {n})d^{3M(r,\mathbf {n})(M(r,n)-1)})\) flops. Ignoring the factor \(N(\mathbf {n})\), we will need \(O(d^{3M(r,\mathbf {n})(M(r,n)-1)})\) flops. To estimate the computational complexity, we also need to take into account the storage space in terms of the entries of \(\mathcal {T}\). This is done in the next section.

It seems that in some cases, it would be beneficial to reduce the number of variables as follows. Note that the number of variables for rank-one tensor \(\mathbf {x}_1\otimes \cdots \otimes \mathbf {x}_d\) is \(-d+1+\sum\limits _{i=1}^d n_i\). Indeed, we can always assume that for \(i<d\), one of the coordinates of \(\mathbf {x}_i\) is 1. However, we do not know which coordinate is 1. Therefore, we need to choose the place of this coordinate. There are \(n_i\) choices. Hence, we need to take \(N(\mathbf {n}')=n_1\cdots n_{d-1}\) choices for each rank-one tensor. (Here \(\mathbf {n}'=(n_1,\cdots , n_{d-1})\).) Thus, for rank r, we have \(N(\mathbf {n}')^r\) choices to consider. Hence, we can replace our complexity estimate \(O(d^{3M(r,\mathbf {n})(M(r,n)-1)})\) by \(O(N(\mathbf {n}')^rd^{3(M(r,\mathbf {n})-d+1)(M(r,n)-d)})\).

Assume that \(\mathbb {G}\) is algebraically closed. A rank-one symmetric tensor in \(\mathrm{S}^d\mathbb {G}^n\) is of the form \(\mathbf {x}^{\otimes d}=\mathbf {x}\otimes \cdots \otimes \mathbf {x}, \mathbf {x}\in \mathbb {G}^n\). A Waring decomposition of \(\mathcal {S}\in \mathrm{S}^d\mathbb {G}^n{\setminus }\{0\}\) is \(\mathcal {S}=\sum \limits _{i=1}^r \mathbf {x}_i^{\otimes d}\) [22]. Since every algebraically closed field has an infinite number of elements, it follows that every symmetric tensor has a Waring decomposition [13]. The minimal number of rank-one symmetric tensors in the decomposition of \(\mathcal {S}\) is called a symmetric rank and is denoted as \({\text {srank}}\,\mathcal {S}\). Clearly, \({\text {rank}}\,\mathcal {S}\leqslant {\text {srank}}\,\mathcal {S}\). It is shown in [10, 30] that in certain cases, one has an equality \({\text {rank}}\,\mathcal {S}={\text {srank}}\,\mathcal {S}\). However, even for \(d=3\), one can have an inequality \({\text {rank}}\,\mathcal {S}<{\text {srank}}\,\mathcal {S}\) [27].

Hence, an analog of Lemma 1 is

Lemma 3

Let \(3 \leqslant d\) and \(2\leqslant n\) be integers. Assume that \(\mathcal {S}\in \mathbb {G}^{\mathbf {n}}\), where \(\mathbb {G}\) is an algebraically closed field. Then, \(r<{\text {srank}}\,\mathcal {S}\) if and only if the following system of \(n+d-1\atopwithdelims ()d\) polynomial equations

$$\begin{aligned} \sum _{i=1}^r \mathbf {x}_i^{\otimes d}-\mathcal {S}=0 \end{aligned}$$
(6)

is not solvable.

Assume that \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}^{n}\). Thus, \({\text {srank}}\,\mathcal {S}>r\) over \({\hat{\mathbb {F}}}\) if the above system is not solvable over \({\hat{\mathbb {F}}}\). Let \(f_{i_1,\cdots ,i_d}(\mathbf {x}_1,\cdots ,\mathbf {x}_r)\) be the left-hand side of \((i_1,\cdots ,i_d)\in [n]^d\) entry. Since we are dealing with symmetric tensors, we can assume that \(1\leqslant i_1\leqslant \cdots \leqslant i_d\leqslant n\). Hence, the unsolvability of (6) is equivalent to

$$\begin{aligned} \sum _{1\leqslant i_1\leqslant \cdots \leqslant i_d\leqslant n} g_{i_1,\cdots ,i_d}(\mathbf {x}_1,\cdots ,\mathbf {x}_r)f_{i_1,\cdots ,i_d}(\mathbf {x}_1,\cdots ,\mathbf {x}_r)=1. \end{aligned}$$
(7)

Note that the total number of variables is rn. The efficient Nullstellensatz [17] gives an upper bound on \(\deg g_{i_1,\cdots ,i_d}f_{i_1,\cdots ,i_d}\leqslant d^{rn}\). The arguments above yield that the number of monomials of degree at most \(d_i=\deg g_{i_1,\cdots ,i_d}\) is less than \(\text{e}d^{(rn)(rn-1)}\). Viewing the coefficients of \(g_{i_1,\cdots ,i_d}\) as linear variables, we deduce that the total number of linear variables in all \(g_{i_1,\cdots ,i_d}\) is at most \({n+d-1\atopwithdelims ()d}d^{(rn)(rn-1)}\). In Sect. 2, we showed that \({n+d-1\atopwithdelims ()d}\leqslant n^d\). Observe next

$$\begin{aligned} {n+d-1\atopwithdelims ()d}={n+d-1\atopwithdelims ()n-1}={d+1+(n-1)-1\atopwithdelims ()n-1}\leqslant (d+1)^{n-1}. \end{aligned}$$

Hence, the number of linear variables is bounded above by \(O(\min (n^d,(d+1)^{n-1})d^{(nr)(nr-1)})\). The number of equations is as the number of monomials which is bounded above by \(d^{(nr)(nr-1)}\). Thus, if we use the Gauss elimination to determine if this system of linear equations is solvable or not, we need \(O\left({n+d-1\atopwithdelims ()d}d^{3(nr)(nr-1)}\right)\) flops.

A complementary question is: suppose that we know that rank\(_{{\hat{\mathbb {F}}}}\mathcal {T}=r\) using the above approach. Does the complexity of finding its rank decomposition in some explicit way have roughly the same complexity as finding that rank\(_{{\hat{\mathbb {F}}}}\mathcal {T}=r\)? This is a much harder problem discussed in [14]. In [21] Nie gave an algorithm on finding solvability of such a decomposition for symmetric tensor over \(\mathbb {C}\). No complexity analysis is investigated though.

4 Complexity of Solvability of Linear Systems Over Integers

We provide a simple complexity result on the solvability of nonhomogeneous linear system of equations

$$\begin{aligned} A\mathbf {x}=\mathbf {b}, \quad A\in \mathbb {Q}^{m\times n},\,\mathbf {b}\in \mathbb {Q}^m{\setminus }\{\mathbf {0}\}. \end{aligned}$$
(8)

We represent each rational number by p/q, where \(p\in \mathbb {Z}\) and \(q\in \mathbb {N}\). We do not assume that p, q are coprime. The storage for p/q that can be also written as (p, q) is

$$\begin{aligned} h(p/q)=\lceil \log _2 q\rceil +\max (1,\lceil \log _2(2|p|)\rceil ). \end{aligned}$$

We denote by H the maximum height of the augmented matrix \({\hat{A}}=[A\,\mathbf {b}]\).

The system is solvable if and only if one does not have pivots in the last column of \({\hat{A}}\). Equivalently, the Kronecker-Capelli theorem claims that the system is solvable if and only if \({\text {rank}}\, A={\text {rank}}\,{\hat{A}}\). The number of operations that one needs is \(O(mn^2)\). However, if \(n> m\), then one can compute \({\text {rank}}\, A\) and \({\text {rank}}\,{\hat{A}}\) using the equalities \({\text {rank}}\, A={\text {rank}}\, A^{\text{T}}\) and \({\text {rank}}\,{\hat{A}}={\text {rank}}\,{\hat{A}}^{\text{T}}\). This will give the number of operations \(O(nm^2)\). Hence, the number of flops we need to carry out is \(O(\min (mn^2,nm^2))\). We need to address the storage of the entries, whose h function is growing when we perform the Gauss elimination.

Recall the complexity of computation of the product of two positive integers p and q. The standard algorithm would take O(h(p)h(q)). However, there are better algorithms: Karatsuba algorithm, Toom-Cook multiplication algorithm, and Schonhage-Strassen algorithm. Basically, if one assumes the Schonhage-Strassen algorithm, it follows that the number of operations for the product of two numbers of height at most H is \(O(H\log H\log \log H)\). For simplicity of notation, we will ignore the logarithmic factors by denoting the complexity of the Schonhage-Strassen algorithm as O(H).

Proposition 1

Consider the system of linear equations (8). Then, the complexity of determining the solvability of this system is \(O(\max (m,n)\min (m,n)^4H)\), where the logarithmic terms taking into account the Schonhage-Strassen algorithm are suppressed. If A and \(\mathbf {b}\) are integers, then the complexity of determining the solvability of this system is \(O(\max (m,n)\min (m,n)^3(H+\log _2\min (m,n)))\).

Proof

We first assume that A and \(\mathbf {b}\) have integer entries. We compute ranks of A and \({\hat{A}}\) and use the Kronecker-Capelli theorem. By considering \(A^{\text{T}}, {\hat{A}}^{\text{T}}\), if needed, we will assume that \(n\geqslant m\). We perform the standard Gauss elimination on A, without normalizing the pivots, as in [6, 25, §3.3] or [11, §1.3.2]. Let \(D_k\) be the determinant of the \(k\times k\) submatrix of A that contains the k pivots. Then, \(|D_k|\leqslant 2^{kH} k!\). Hence, \(\log _2 |D_k|=O(k(H+\log _2 k))\). The main observation is that the value of k-th pivot is the ratio of the corresponding \(D_k/D_{k-1}\), where \(D_0=1\). Hence, the height of k-th pivot is \(O(k(H+\log k))\). The Schonhage-Strassen algorithm for multiplying two integers by this height is \(O(k(H+\log _2k))\). As \(k\leqslant m\), we get that the storage of all entries is \(O(nm^2(H+\log _2 m))\). As we need \(O(nm^2)\) flops, we deduce that the total complexity is \(O(nm^3(H+\log _2 m))\).

Assume now that A and \(\mathbf {b}\) have rational entries. Then, we multiply each nonzero column of A by the product of the numerators of the entries of this column to obtain \(A_1\in \mathbb {Z}^{m\times n}\). Similarly we obtain \(\mathbf {b}_1\in \mathbb {Z}^m\). Clearly, \({\text {rank}}\, A_1={\text {rank}}\, A\) and \({\text {rank}}\,{\hat{A}}_1={\text {rank}}\,{\hat{A}}\). Observe that \(H_1\), the height of \({\hat{A}}_1\) is O(mH). Hence, the complexity of determining the solvability of (8) is \(O(nm^3(mH+\log _2 m))=O(nm^4 H)\).

5 Polynomial Equations of Finite Field

Let \(\mathbb {F}_q\) be a finite field with \(q=p^l\) elements, where p is a prime number and l a positive integer. Assume that \(\mathcal {T}\in \mathbb {F}_q^{\mathbf {n}}\). Then, \(r\geqslant {\text {rank}}\,\mathcal {T}\) over \(\mathbb {F}_q\) if and only if the system of polynomial equations (3) is solvable. A brute force method by checking all possible values of \(M(r,\mathbf {n})\) variables is \(O(q^{M(r,\mathbf {n})})\). In a recent paper [20], a somewhat better result is given. Namely, there is a randomized algorithm of running time \(O(q^{(1-\delta (r,p,l))M(r,\mathbf {n})})\) with high  probability of finding a solution of the system if it is solvable. For \(q=2\) one has that \(\delta (r,2,1)\approx 0.113\,5\). For \(q\leqslant 2^{4\text{e}rl}\) one has that \(\delta (r,p,l)=O(1/r)\). Otherwise, \(\delta (r,p,l)=\frac{l\log (\log (q/4\text{e}rl))}{\log q}\).

Note that for our method, we need to determine the solvability of the system of linear equations over \(\mathbb {F}_q\). Thus, the storage needed for each entry is \(O(\log _2 q)\). The complexity of multiplying using two elements in \(\mathbb {F}_q\) is O(q) ignoring the logarithmic factors. Hence, the complexity for determining the solvability of system of m equations in n unknowns using the Gauss elimination is \(O(\max (m,n)\min (n,m)^2 q)\). Thus, for \(q>d^{3M(r,\mathbf {n})}\), our complexity for finding if rank\(_{{\hat{\mathbb {F}}}}\mathcal {T}>r\) is comparable or better than the complexity of finding if rank\(_{\mathbb {F}_q}\mathcal {T}>r\).

Similar results hold for symmetric tensors. Assume that \(\mathcal {S}\in \mathrm{S}^d\mathbb {F}_q^n\). Then, srank\(_{\mathbb {F}_q}\mathcal {S}>r\) if and only if the following system of \({n+d-1\atopwithdelims ()d}\) polynomial equations is not solvable over \(\mathbb {F}_q\):

$$\begin{aligned} \sum _{i=1}^r t_i\mathbf {x}_i^{\otimes d}-\mathcal {S}=0, \end{aligned}$$
(9)

where \(t_i\in \mathbb {F}_q, \mathbf {x}_i\in \mathbb {F}_q^n\) for \(i\in [r]\). Note that the total number of variables is \((r+1)n\).

6 Open Problems

The first major problem is whether we can reduce the number of monomials appearing in \(g_{i_1,\cdots ,i_d}\). The insight behind this problem is that each \(f_{i_1,\cdots ,i_d}\) consists of a constant term and \(-\mathcal {T}_{i_1,\cdots ,i_d}\) and sum of r multilinear monomials which are invariant under the permutation of the r vectors \(\{\mathbf {x}_{j,1},\cdots ,\mathbf {x}_{j,r}\}\rightarrow \{\mathbf {x}_{j,\sigma (1)},\cdots ,\mathbf {x}_{j,\sigma (r)}\}\) for \(j\in [d]\), and \(\sigma :[d]\rightarrow [d]\). The second problem: is it true that each monomial of \(g_{i_1,\cdots ,i_d}\) is a monomial in the entries of rank-one tensors \(\otimes _{j=1}^d x_{j,i}\)? Further investigation along those lines could prove to be worthwhile.