ag14:start

**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?
- 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.

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

- 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\).
- 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.

- [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\).

- [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;

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

ag14/start.txt · Last modified: 2015/01/21 00:13 by Simons Admin