ag14:start

# Algorithms and Complexity in Algebraic Geometry, Fall 2014

## Computational Open Questions

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;

## General Open Questions

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}$. 