{
  "id": "1911.07981",
  "version": "v1",
  "published": "2019-11-18T22:18:34.000Z",
  "updated": "2019-11-18T22:18:34.000Z",
  "title": "New lower bounds for matrix multiplication and the 3x3 determinant",
  "authors": [
    "Austin Conner",
    "Alicia Harper",
    "J. M. Landsberg"
  ],
  "comment": "23 pages",
  "categories": [
    "math.AG",
    "cs.CC",
    "math.RT"
  ],
  "abstract": "Let $M_{\\langle u,v,w\\rangle}\\in C^{uv}\\otimes C^{vw}\\otimes C^{wu}$ denote the matrix multiplication tensor (and write $M_n=M_{\\langle n,n,n\\rangle}$) and let $det_3\\in ( C^9)^{\\otimes 3}$ denote the determinant polynomial considered as a tensor. For a tensor $T$, let $\\underline R(T)$ denote its border rank. We (i) give the first hand-checkable algebraic proof that $\\underline R(M_2)=7$,(ii) prove $\\underline R(M_{\\langle 223\\rangle})=10$, and $\\underline R(M_{\\langle 233\\rangle})=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M_2$,(iii) prove $\\underline R( M_3)\\geq 17$, (iv) prove $\\underline R( det_3)=17$, improving the previous lower bound of $12$, (v) prove $\\underline R(M_{\\langle 2nn\\rangle})\\geq n^2+1.32n$ for all $n\\geq 25$ (previously only $\\underline R(M_{\\langle 2nn\\rangle})\\geq n^2+1$ was known) as well as lower bounds for $4\\leq n\\leq 25$, and (vi) prove $\\underline R(M_{\\langle 3nn\\rangle})\\geq n^2+2 n+1$ for all $ n\\geq 21$, where previously only $\\underline R(M_{\\langle 3nn\\rangle})\\geq n^2+2$ was known, as well as lower boundsfor $4\\leq n\\leq 21$. Our results utilize a new technique initiated by Buczy\\'{n}ska and Buczy\\'{n}ski, called border apolarity. The two key ingredients are: (i) the use of a multi-graded ideal associated to a border rank $r$ decomposition of any tensor, and (ii) the exploitation of the large symmetry group of $T$ to restrict to $B_T$-invariant ideals, where $B_T$ is a maximal solvable subgroup of the symmetry group of $T$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-18T22:18:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower bound",
      "3x3 determinant",
      "border rank",
      "nontrivial matrix multiplication tensor",
      "first hand-checkable algebraic proof"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}