skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, December 13 until 2:00 AM ET on Saturday, December 14 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: New lower bounds for matrix multiplication and
Abstract

Let$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$denote the matrix multiplication tensor (and write$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$), and let$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$denote the determinant polynomial considered as a tensor. For a tensorT, let$\underline {\mathbf {R}}(T)$denote its border rank. We (i) give the first hand-checkable algebraic proof that$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$, (ii) prove$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$and$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$M_{\langle 2\rangle }$, (iii) prove$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$, (iv) prove$\underline {\mathbf {R}}(\operatorname {det}_3)=17$, improving the previous lower bound of$12$, (v) prove$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$for all$\mathbf {n}\geq 25$, where previously only$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$was known, as well as lower bounds for$4\leq \mathbf {n}\leq 25$, and (vi) prove$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$for all$\mathbf {n} \ge 18$, where previously only$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors.

The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, calledborder apolaritydeveloped by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorTand an integerr, in a finite number of steps, either outputs that there is no border rankrdecomposition forTor produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenThas a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory.

  more » « less
Award ID(s):
2203618
PAR ID:
10486993
Author(s) / Creator(s):
; ;
Publisher / Repository:
Cambridge University Press
Date Published:
Journal Name:
Forum of Mathematics, Pi
Volume:
11
ISSN:
2050-5086
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , Nagoya Mathematical Journal)
    Abstract

    We investigate a novel geometric Iwasawa theory for${\mathbf Z}_p$-extensions of function fields over a perfect fieldkof characteristic$p>0$by replacing the usual study ofp-torsion in class groups with the study ofp-torsion class groupschemes. That is, if$\cdots \to X_2 \to X_1 \to X_0$is the tower of curves overkassociated with a${\mathbf Z}_p$-extension of function fields totally ramified over a finite nonempty set of places, we investigate the growth of thep-torsion group scheme in the Jacobian of$X_n$as$n\rightarrow \infty $. By Dieudonné theory, this amounts to studying the first de Rham cohomology groups of$X_n$equipped with natural actions of Frobenius and of the Cartier operatorV. We formulate and test a number of conjectures which predict striking regularity in the$k[V]$-module structure of the space$M_n:=H^0(X_n, \Omega ^1_{X_n/k})$of global regular differential forms as$n\rightarrow \infty .$For example, for each tower in a basic class of${\mathbf Z}_p$-towers, we conjecture that the dimension of the kernel of$V^r$on$M_n$is given by$a_r p^{2n} + \lambda _r n + c_r(n)$for allnsufficiently large, where$a_r, \lambda _r$are rational constants and$c_r : {\mathbf Z}/m_r {\mathbf Z} \to {\mathbf Q}$is a periodic function, depending onrand the tower. To provide evidence for these conjectures, we collect extensive experimental data based on new and more efficient algorithms for working with differentials on${\mathbf Z}_p$-towers of curves, and we prove our conjectures in the case$p=2$and$r=1$.

     
    more » « less
  2. ( , Forum of Mathematics, Pi)
    Abstract

    Define theCollatz map${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$on the positive integers$\mathbb {N}+1 = \{1,2,3,\dots \}$by setting${\operatorname {Col}}(N)$equal to$3N+1$whenNis odd and$N/2$whenNis even, and let${\operatorname {Col}}_{\min }(N) := \inf _{n \in \mathbb {N}} {\operatorname {Col}}^n(N)$denote the minimal element of the Collatz orbit$N, {\operatorname {Col}}(N), {\operatorname {Col}}^2(N), \dots $. The infamousCollatz conjectureasserts that${\operatorname {Col}}_{\min }(N)=1$for all$N \in \mathbb {N}+1$. Previously, it was shown by Korec that for any$\theta> \frac {\log 3}{\log 4} \approx 0.7924$, one has${\operatorname {Col}}_{\min }(N) \leq N^\theta $for almost all$N \in \mathbb {N}+1$(in the sense of natural density). In this paper, we show that foranyfunction$f \colon \mathbb {N}+1 \to \mathbb {R}$with$\lim _{N \to \infty } f(N)=+\infty $, one has${\operatorname {Col}}_{\min }(N) \leq f(N)$for almost all$N \in \mathbb {N}+1$(in the sense of logarithmic density). Our proof proceeds by establishing a stabilisation property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a$3$-adic cyclic group$\mathbb {Z}/3^n\mathbb {Z}$at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency.

     
    more » « less
  3. ( , Bulletin of the Australian Mathematical Society)
    Abstract

    Let$\varphi _1,\ldots ,\varphi _r\in {\mathbb Z}[z_1,\ldots z_k]$be integral linear combinations of elementary symmetric polynomials with$\text {deg}(\varphi _j)=k_j\ (1\le j\le r)$, where$1\le k_1. Subject to the condition$k_1+\cdots +k_r\ge \tfrac {1}{2}k(k-~1)+2$, we show that there is a paucity of nondiagonal solutions to the Diophantine system$\varphi _j({\mathbf x})=\varphi _j({\mathbf y})\ (1\le j\le r)$.

     
    more » « less
  4. ; ; ( , Forum of Mathematics, Sigma)
    Abstract

    We prove that the rational cohomology group$H^{11}(\overline {\mathcal {M}}_{g,n})$vanishes unless$g = 1$and$n \geq 11$. We show furthermore that$H^k(\overline {\mathcal {M}}_{g,n})$is pure Hodge–Tate for all even$k \leq 12$and deduce that$\# \overline {\mathcal {M}}_{g,n}(\mathbb {F}_q)$is surprisingly well approximated by a polynomial inq. In addition, we use$H^{11}(\overline {\mathcal {M}}_{1,11})$and its image under Gysin push-forward for tautological maps to produce many new examples of moduli spaces of stable curves with nonvanishing odd cohomology and nontautological algebraic cycle classes in Chow cohomology.

     
    more » « less
  5. ; ; ( , Forum of Mathematics, Pi)
    Abstract

    Letfbe an$L^2$-normalized holomorphic newform of weightkon$\Gamma _0(N) \backslash \mathbb {H}$withNsquarefree or, more generally, on any hyperbolic surface$\Gamma \backslash \mathbb {H}$attached to an Eichler order of squarefree level in an indefinite quaternion algebra over$\mathbb {Q}$. Denote byVthe hyperbolic volume of said surface. We prove the sup-norm estimate$$\begin{align*}\| \Im(\cdot)^{\frac{k}{2}} f \|_{\infty} \ll_{\varepsilon} (k V)^{\frac{1}{4}+\varepsilon} \end{align*}$$

    with absolute implied constant. For a cuspidal Maaß newform$\varphi $of eigenvalue$\lambda $on such a surface, we prove that$$\begin{align*}\|\varphi \|_{\infty} \ll_{\lambda,\varepsilon} V^{\frac{1}{4}+\varepsilon}. \end{align*}$$

    We establish analogous estimates in the setting of definite quaternion algebras.

     
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email