Simons Institute Program on Algorithms in Complexity and Algebraic Geometry

If you had a large, but finite, black box computer, what problem would you solve with it?

1. What is the tensor rank (or border rank) of the \(3\times 3\) matrix multiplication tensor?
2. [Umans] Is the \(S\)-rank (the support rank) of the \(2\times 2\) matrix multiplication tensor 6 or 7?

1. What is the determinantal complexity of the \(3\times 3\) permanent?
   • Recall for a polynomial \(f(\vec x)\), the determinantal complexity \(\textsf{dc}( f) \) is the minimum size of a matrix \(X\), whose entries are affine linear functions in \(\vec x\) such that \(\det X = f(\vec x)\).
   • We know the answer is either 5,6,7, and we have an explicit matrix for the upper bound on \(\textsf{dc}(\textrm{perm}_3)\). For the other sizes, either exhibit a new matrix whose determinant is equal to the permanent, or show that the system of polynomial equations is has no solution.
2. [Ikenmeyer & Hüttenhain] What is the binary determinantal complexity of the \(4\times 4\) permanent?
   • The binary determinantal complexity of a polynomial with integer coefficients is the smallest size \(n\) of a matrix \(A\) whose entries are only variables, 0s, and 1s, such that \(\textrm{det}(A)=f\). The binary determinantal complexity of the \(3 \times 3\) permanent is 7 (see arxiv:1410.8202).
   • We have an eplicit construction that shows that the binary determinantal complexity of the \(4\times 4\) permanent is at most 15.
3. What is the Waring rank of the \(3\times 3\) determinant and permanent?
   • Recall that the Waring rank is the minimal number of summands needed to express a given polynomial as a sum of powers of linear forms.

1. Strassen's additivity conjecture for \(4\times 4\times 4\times 4\) tensors: That is, is tensor rank additive over direct sums for this format?
2. [Umans] Address the CW90 Asymptotic Rank Conjecture in the case that \(n=2\). Consider the CW90 tensor \(T\) (which has rank 4), and determine whether the border rank of \(T^{\otimes 2}\) is 15 or 16. [if anyone copied the CW90 tensor T please add here]
3. Pavel Hrubes' question. For each \(n\), let \(S(n)\) be the minimal number k in a sum of squares representation of \((x_1^2+\dotsb+x_n^2)(y_1^2+\dotsb+y_n^2) = f_1^2+\dotsb+f_k^2\).
   • First question: For each small \(n\) describe the set of such minimal representations.
   • Second question: Determine \(S(n)\) for all \(n\) for which this is feasible.

1. [J. Maurice Rojas]: What is the least prime \(p\) such that some trinomial \(c_1+c_2 x^{e_2} + c_3 x^{e_3}\) (with \(c_1,c_2,c_3\in F_p\), \(0<e_2<e_3<p-1\), and \(gcd(e_2,e_3,p-1)=1\)) has at least 14 roots in \(F_p\)? More generally, gather as much data as reasonably possible for the growth of \(p_k\), where \(p_k\) is the least prime such that some trinomial over \(F_{p_k}\) (with nonzero constant term, and exponents sharing no common divisor with p-1) has exactly k roots in \(F_{p_k}\).
   • Comment: The answer for 13 roots appears to be p=10867. There is currently no solid evidence for or against \(p_k\) growing exponentially in \(k\).
2. [Isabel Herrero] Let \(K\) be an algebraically closed field of characteristic 0. Let \(S_n\) be the Zariski closure of the set of all univariate polynomials over \(K\) of degree \(n\) and two double roots, that is of the set

\begin{equation} \{ (c_0, \dots, c_n) \in (K^*)^{n+1} \mid f(x) = c_0 + c_1x+ \cdots + c_nx^n \quad \text{ has two double roots}\}. \end{equation} We want to compute the homogeneous ideal of all polynomials that vanishes over \(S_8\) and, if possible, a reduced Groebner basis of that ideal. Can it be done for \(n=9\) or even \(10\)?

Example: For \(S_6\), thinking of \(f\) as \(f(x) = c_0 + c_1x+ \ldots + c_6x^6 = C_6(x-a)^2(x-b)^2(x-c)(x-d)\), I computed the reduced Groebner basis using SINGULAR with this code:

ring R = 0,(a,b,c,d,x,C5,C4,C3,C2,C1,C0), dp;
ideal I =
   C6*x^6 + C5*x^5 + C4*x^4 + C3*x^3 + C2*x^2 + C1*x + C0,
   C5 + C6*2*a + C6*2*b + C6*c + C6*d,
   C4 - C6*a^2 - C6*4*a*b - C6*b^2 - C6*2*a*c - C6*2*b*c - C6*2*a*d -
C6*2*b*d - C6*c*d,
   C3 + C6*2*a^2*b + C6*2*a*b^2 + C6*a^2*c + C6*4*a*b*c + C6*b^2*c +
C6*a^2*d + C6*4*a*b*d + C6*b^2*d + C6*2*a*c*d + C6*2*b*c*d,
   C2 - C6*a^2*b^2 - C6*2*a^2*b*c - C6*2*a*b^2*c - C6*2*a^2*b*d -
C6*2*a*b^2*d - C6*a^2*c*d - C6*4*a*b*c*d - C6*b^2*c*d,
   C1 + C6*a^2*b^2*c + C6*a^2*b^2*d + C6*2*a^2*b*c*d + C6*2*a*b^2*c*d,
   C0 - C6*a^2*b^2*c*d;
ideal k = eliminate( I, a * b * c * d * x);
groebner(k);
exit;

1. [Jamshidi] Let $H$ be a positive semi-definite $n \times n$ matrix over $\mathbb{C}$. Does there exist an ideal of invariant polynomials over the entries of $H$ that determine if the eigenvector $v$ corresponding to the lowest eigenvalue of $H$ can be expressed a particular tensor decompositions? For example, $\mathscr{F}$ is such that if $\forall f \in\mathscr{F}$, $f(H) = 0$, then $v = v_{abc} = A_{a}^{\beta} B_{\beta\gamma b} C^{\gamma}_{d}$.