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?
What is the tensor rank (or border rank) of the \(3\times 3\) matrix multiplication tensor?
[Umans] Is the \(S\)-rank (the support rank) of the \(2\times 2\) matrix multiplication tensor 6 or 7?
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.
[Ikenmeyer & Hüttenhain] What is the binary determinantal complexity of the \(4\times 4\) permanent?
What is the Waring rank of the \(3\times 3\) determinant and permanent?
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?
[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]
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\).
[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}\).
[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
[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}$.