Further limitations of the known approaches for matrix multiplication

Introduction

One of the most fundamental questions in computer science asks how quickly one can multiply two matrices. Since the surprising subcubic algorithm for $n\times n\times n$ matrix multiplication by Strassen in 1969 [Str69], there has been a long line of work on improving and refining the techniques and speeding up matrix multiplication algorithms (e.g. [Pan78, Pan80, BCRL79, Str86, CW81, Sch81, Str87, CW90, DS13, Wil12, LG14]). Progress on this problem is typically measured in terms of $\omega$, the smallest constant such that, for any $\delta>0$, one can design an algorithm for $n\times n\times n$ matrix multiplication running in time $O(n^{\omega+\delta})$. The biggest open question is whether one can achieve $\omega=2$. The best bound we currently know, due to Le Gall [LG14], is $\omega\leq 2.3728639$.

A related line of work [CW90, Cop97, LG12, GU17] focuses on rectangular matrix multiplication instead of square matrix multiplication. Here, progress is measured in terms of $\alpha$, the largest constant such that for any $\delta>0$, one can design an algorithm for $n\times n^{\alpha}\times n$ matrix multiplication running in time $O(n^{2+\delta})$. Recent work [GU17] improved the best known bound to $\alpha>0.31389$. The two values $\omega$ and $\alpha$ are very related, as $\omega=2$ if and only if $\alpha=1$.

Our first result is a unifying approach to achieving all known bounds of $\omega$ ([Str86, CW90, DS13, LG14]) since Strassen’s 1986 proof that $\omega<2.48$.

A simple remark first pointed out to us by Michalek [Mic14] is that the so called Coppersmith-Winograd tensor used in the papers on matrix multiplication since 1990 [CW90, DS13, LG14], can be replaced with an equivalent tensor, rotating the original slightly in a certain way (see the Preliminaries), without changing any of the proofs, and thus yielding the same bounds on $\omega$.

For every $p$, and for every $\varepsilon\in(0,1]$, there is an explicit constant $\nu_{p,\varepsilon}>1$ such that any algorithm for $n\times n^{\varepsilon}\times n$ matrix multiplication designed in the above way using $T_{p}$, or a monomial degeneration of $T_{p}$, runs in time $\Omega(n^{(1+\varepsilon)\nu_{p,\varepsilon}})$. (See Theorem 6.1 below for the precise statement).

The constant $\nu_{p,\varepsilon}$ is defined as follows. Consider first when $p$ is a fixed prime or power of a prime. Let $z$ be the unique real number in $(0,1)$ such that $3\sum_{j=1}^{p-1}z^{j}=(p-1)(1-2z^{p})$; then

There is also a variant of Theorem 1.1 that holds for $T_{p}$ when $p$ is not necessarily a prime power, but the constant $\nu_{p,\varepsilon}>1$ is slightly different.

This approach yields a square matrix multiplication algorithm with runtime at best $\Omega(n^{2\nu_{p,1}})$, with exponent $2\nu_{p,1}>2$. Hence, this approach for a fixed $p$ cannot yield $\omega=2$.

Let $\varepsilon_{p}\in(0,1)$ be such that $(1+\varepsilon_{p})\nu_{p,\varepsilon}=2$. Then, this approach for a fixed $p$ cannot yield a value of $\alpha$ bigger than $\varepsilon_{p}$.

For modest values of $p$, the value $\nu_{p}:=\nu_{p,1}$ is a fair bit larger than $1$. For instance, $\nu_{7}\approx 1.07065$. As we will show shortly, the best known algorithms for matrix multiplications use the approach above with a (rotated) Coppersmith-Winograd tensor which is a monomial degeneration of $T_{7}$. Our theorem implies among other things that using the approach with $T_{7}$ as the starting tensor cannot yield a bound on $\omega$ better than $2.14$, no matter how one zeroes out the tensor powers of $T_{7}$ or its monomial degenerations. We plot the resulting bounds on $\omega$ and $\alpha$ for varying $p$, in Figures 1 and 2 (for technical reasons we discuss below, we get different bounds depending on whether $q$ is a power of a prime).

3 A potential idea for improving ω𝜔\omega.

It should be noted that, despite our lower bounds, not all hope is lost for achieving $\omega=2$ using $T_{q}$ tensors. Indeed, in the limit as $q\to\infty$, our $\omega$ lower bound approaches $2$, and our $\alpha$ upper bound approaches $1$ (see Lemma A.1 in Appendix A for a proof). Hence, our lower bound does not rule out achieving a runtime for $n\times n\times n$ matrix multiplication of $O(n^{2+\delta})$ for all $\delta>0$ by using bigger and bigger values of $q$. We find this approach very exciting.

4 Tri-Colored Sum-Free Sets

For any integer $q\geq 2$ which is a power of a prime, let $\rho$ be the unique number in $(0,1)$ satisfying

For notational simplicity in our main results in Section 6, define $\gamma_{q}:=(1-\kappa/q)\log(q)$ when $q\geq 2$ is not a power of a prime.

5 Proof Outline

In Section 3, we give a simple rank expression for $T_{q}$, and show that the rotated Coppersmith-Winograd tensor can be found as a simple monomial degeneration of $T_{q}$.

In Section 4, we show that every matrix multiplication tensor has a zeroing out into a large number of independent triples. This generalizes a classical result that matrix multiplication tensors have monomial degenerations into a large number of independent triples.

In Section 5, we show that if tensor $A$ is a monomial degeneration of tensor $B$, and large powers of $A$ can be zeroed out into many independent triples, then large powers of $B$ can as well.

6 Comparison with Past Work

There are two papers which have proved lower bounds on the value of $\omega$ that one can achieve using certain techniques.

The second prior work is by Blasiak et al. [BCC+17]. Like us, the authors also use recent bounds on the size of certain tri-colored sum-free sets in order to prove lower bounds. However, rather than the tensor-based approach to matrix multiplication algorithms which we have been discussing, and which has been used in all of the improvements to $\omega$ and $\alpha$ to date, they instead focus on the ‘group-theoretic approach’ to matrix multiplication [CU03, CKSU05]. This approach has been designed around formulating approaches that would imply $\omega=2$ rather than on attempting any small improvement to the bounds on $\omega$, and this paper refutes some earlier conjectures along these lines. The work of Blasiak et al. implies that certain approaches to achieving $\omega=2$ are impossible, similar to our work here.

Preliminaries

In this section we introduce all the notions related to tensors which are used in the rest of the paper.

Let $X=\{x_{1},\ldots,x_{n}\}$, $Y=\{y_{1},\ldots,y_{m}\}$, and $Z=\{z_{1},\ldots,z_{p}\}$ be three sets of formal variables. A tensor over $X,Y,Z$ is a trilinear form

For any positive integer $q$, the $q$th Coppersmith-Winograd tensor Cq [CW90] is given by $x_{0}y_{0}z_{q+1}+x_{0}y_{q+1}z_{0}+x_{q+1}y_{0}z_{0}+\sum_{i=1}^{q}(x_{0}y_{i}z_{i}+x_{i}y_{0}z_{i}+x_{i}y_{i}z_{0})$. It is not hard to verify that using the Coppersmith-Winograd approach, one can obtain exactly the same values for $\omega$ from the following rotated Coppersmith-Winograd tensor $CW_{q}$, given by

The main reason why CWq works just as well as the original Coppersmith-Winograd tensor Cq is because they both have border rank $q+2$ and because of the following other structural reason which is what is used in the prior work on fast matrix multiplication:

Let $X_{0}=\{x_{0}\}$, $X_{1}=\{x_{1},\ldots,x_{q}\}$, $X_{2}=\{x_{q+2}\}$. Similarly, let $Y_{0}=\{y_{0}\}$, $Y_{1}=\{y_{1},\ldots,y_{q}\}$, $Y_{2}=\{y_{q+2}\}$, and $Z_{0}=\{z_{0}\}$, $Z_{1}=\{z_{1},\ldots,z_{q}\}$, $Z_{2}=\{z_{q+2}\}$. When you restrict Cq and CWq to $X_{0}\times Y_{2}\times Z_{0}$, or $X_{2}\times Y_{0}\times Z_{0}$, or $X_{0}\times Y_{0}\times Z_{2}$, both of them are isomorphic to $\langle 1,1,1\rangle$. When you restrict them to $X_{0}\times Y_{1}\times Z_{1}$, both are isomorphic to $\langle 1,1,q\rangle$, when you restrict them to $X_{1}\times Y_{0}\times Z_{1}$, both are isomorphic to $\langle q,1,1\rangle$, and when you restrict them to $X_{1}\times Y_{1}\times Z_{0}$, both are isomorphic to $\langle 1,q,1\rangle$. The Coppersmith-Winograd approach only looks at products of these blocks in higher tensor powers, which are hence isomorphic to the same matrix multiplication tensors and give the same bounds on $\omega$.

2 Subsets and Degenerations

we have $a(x_{i})+b(y_{j})+c(z_{k})\geq 0$, and

furthermore, $a(x_{i})+b(y_{j})+c(z_{k})=0$ if and only if $A_{ijk}\neq 0$ as well.

We note that in prior work, degenerations are defined via polynomials in a variable $\varepsilon$, however when the degenerations are single monomials, the above definition is equivalent, where $a,b,c$ give the corresponding exponents of $\varepsilon$.

Finally, we say that $A$ is a zeroing out of $B$ if $A$ is a monomial degeneration of $B$ such that $a(x)\geq 0$ for all $x\in X$, $b(y)\geq 0$ for all $y\in Y$, and $c(z)\geq 0$ for all $z\in Z$. One can think of this as substituting for any variable which $a,b$, or $c$ maps to a positive value.

3 Tensor Product

Let $X,X^{\prime},Y,Y^{\prime},Z,Z^{\prime}$ be sets of formal variables. If $A$ is a tensor over $X,Y,Z$, and $B$ is a tensor over $X^{\prime},Y^{\prime},Z^{\prime}$, then the tensor product of $A$ and $B$, denoted $A\otimes B$, is a tensor over $X\times X^{\prime},Y\times Y^{\prime},Z\times Z^{\prime}$ given by

The $n$th tensor power of a tensor $A$, denoted $A^{\otimes n}$, is the result of tensoring $n$ copies of $A$ together. In other words, $A^{\otimes 1}=A$, and $A^{\otimes n}=A\otimes A^{\otimes n-1}$.

Tensor products preserve many key properties of tensors. For instance, if $A\subseteq C$ and $B\subseteq D$, then $A\otimes B\subseteq C\otimes D$, and this is also true if subset is replaced by monomial degeneration, or by zeroing out.

For a nonnegative integer $k$, if $A$ is a tensor over $X,Y,Z$, and if $X_{1},\ldots,X_{k}$ are $k$ disjoint copies of $X$, and similar for $Y$ and $Z$, then $k\odot A$ denotes the (disjoint) sum of $k$ copies of $A$, one over $X_{i},Y_{i},Z_{i}$ for each $1\leq i\leq k$.

4 Independent Triples

Two triples $(x,y,z),(x^{\prime},y^{\prime},z^{\prime})\in X\times Y\times Z$ are independent if $x\neq x^{\prime}$, $y\neq y^{\prime}$, and $z\neq z^{\prime}$. A tensor $A$ is independent if, whenever $A_{ijk}\neq 0$ and $A_{i^{\prime}j^{\prime}k^{\prime}}\neq 0$, and $(i,j,k)\neq(i^{\prime},j^{\prime},k^{\prime})$, then the triples $(x_{i},y_{j},z_{k})$ and $(x_{i^{\prime}},y_{j^{\prime}},z_{k^{\prime}})$ are independent.

5 Tensor Rank

More generally, $T$ is a rank-$k$ tensor if it can be written as the sum of $k$ rank-one tensors. The rank of $T$, denoted $R(T)$, is the smallest $k$ such that $R$ is a rank-$k$ tensor.

is expanded as a polynomial in $\varepsilon$ whose coefficients are tensors over $X,Y,Z$, then $T$ is the coefficient of $\varepsilon^{h}$, and the coefficient of $\varepsilon^{h^{\prime}}$ is for all $0\leq h^{\prime}<h$. Similarly, the border rank $\underline{R}(T)$ of $T$ is the smallest number of expressions of the form (1) whose sum, when written as a polynomial in $\varepsilon$, has $T$ as its lowest order coefficient.

It is not hard to see that if $A$ is a monomial degeneration of $B$, then $\underline{R}(B)\leq\underline{R}(A)\leq R(A)$.

6 Matrix Multiplication Tensor and Algorithms

Now that we have defined tensor rank, we can define $\omega$ as the infimum over all reals so that $R(\langle n,n,n\rangle)\leq O(n^{\omega+\varepsilon})$ for all $\varepsilon>0$. Similarly, for any $\varepsilon\in(0,1)$, define $\omega_{\varepsilon}$ to be the smallest real such that an $n\times n^{\varepsilon}$ matrix can be multiplied by an $n^{\varepsilon}\times n$ matrix in $n^{\omega_{\varepsilon}+o(1)}$ time.

We present a useful Lemma that follows from the work of Schönhage, which shows how the tensor rank notions we have been discussing can give bounds on $\omega_{\varepsilon}$.

If $R(f~{}\odot\langle n,n^{\varepsilon},n\rangle)\leq g$, then $\omega_{\varepsilon}\leq\log_{n}(\lceil g/f\rceil)$.

By Schönhage [Sch81] (see also [Blä13, Lemma 7.7]), we have that $R(f~{}\odot\langle n,n^{\varepsilon},n\rangle)\leq g$ implies that for all integers $s\geq 1$, $R(f~{}\odot\langle n^{s},n^{s\varepsilon},n^{s}\rangle)\leq f\lceil g/f\rceil^{s}$. Hence, multiplying an $n^{s}\times(n^{s})^{\varepsilon}$ by an $(n/s)^{\varepsilon}\times n^{s}$ matrix can be done in $O(f\lceil g/f\rceil^{s})$ time. Thus $\omega_{\varepsilon}\leq\lim_{s\rightarrow\infty}\log(f\lceil g/f\rceil^{s})/\log(n^{s})=\log_{n}(\lceil g/f\rceil)$. ∎

We can also define $\alpha$ as the largest real such that $R(\langle n,n^{\alpha},n\rangle)\leq n^{2+o(1)}$. It is known that $\alpha\in[0.31,1]$, and clearly $\alpha=1$ if and only if $\omega=2$.

The mod-p tensor and its degenerations

In this section, we give a rank expression for $T_{p}$, and then a monomial degeneration of $T_{q+2}$ into $CW_{q}$.

Let us consider the tensor $T_{p}$ of addition modulo $p$ for any integer $p\geq 2$; recall that in trilinear notation, $T_{p}$ is defined as

𝑞2T_{q+2} into $CW_{q}$ Here we will show that the rotated CW tensor $CW_{q}$ for integer $q\geq 1$ is a degeneration of $T_{q+2}$. Recall that

For ease of notation, we will change the indexing of the $z$ variables in $T_{q+2}$ (i.e. rename the variables) from our original definitionFor every index $k\in\{0,1,\ldots,q+1\}$, we will rename $z_{k}$ to $z_{k-1\pmod{q+2}}$. to write

In this form, one can see that $CW_{q}$ is the subset of $T_{q+2}$ consisting of all the terms containing at least one of $x_{0}$, $y_{0}$, or $z_{0}$. With this in mind, our degeneration of $T_{q+2}$ is as follows. We will pick:

$a(x_{0})=0$, $a(x_{q+1})=2$, and $a(x_{i})=1$ for $1\leq i\leq q$, similarly,

$b(y_{0})=0$, $b(y_{q+1})=2$, and $b(y_{j})=1$ for $1\leq j\leq q$, and,

$c(z_{0})=-2$, $c(z_{q+1})=0$, and $c(z_{k})=-1$ for $1\leq k\leq q$.

We need to verify that for every term $x_{i}y_{j}z_{k}$ in (3) we have $a(x_{i})+b(y_{j})+c(z_{k})\geq 0$, and moreover that for such $x_{i}y_{j}z_{k}$, $a(x_{i})+b(y_{j})+c(z_{k})=0$ if and only if $x_{i}y_{j}z_{k}$ also appears in (2). This is quite straightforward, but we do it here for completeness. Consider any term $x_{i}y_{j}z_{k}$ in (3). We consider three cases based on $k$:

If $k=0$, then our term is of the form $x_{i}y_{q+2-i}z_{0}$ for $0\leq i\leq q+2$. This term always appears in (2) as well, and we can see that we always have $a(x_{i})=2-b(y_{q+2-i})$, and so $a(x_{i})+b(y_{q+2-i})+c(z_{0})=0$.

If $k=q+1$, then $c(z_{q+1})=0$, and we always have $a,b\geq 0$, so we definitely have that $a(x_{i})+b(y_{j})+c(z_{k})\geq 0$. Moreover, we can only achieve when $a=b=0$, with the term $x_{0}y_{0}z_{q+1}$, which is the only term with $z_{q+1}$ which appears in (2).

If $1\leq k\leq q$, then since $x_{0}y_{0}z_{k}$ is not a term in (3), we must have that $a(x_{i})+b(y_{j})\geq 1$, and so $a(x_{i})+b(y_{j})+c(z_{k})\geq 0$. Moreover, we only achieve $a(x_{i})+b(y_{j})+c(z_{k})=0$ when $(a,b)=(0,1)$ or $(1,0)$, which correspond to the terms of the form $x_{0}y_{k}z_{q+1-k}$ or $x_{k}y_{0}z_{q+1-k}$ in (2).

𝑞1T_{q+1} into Strassen’s 1986 tensor. Strassen’s 1986 tensor is defined for any integer $q\geq 1$ and is given by $S_{q}:=\sum_{i=1}^{q}x_{0}y_{i}z_{q+1-i}+x_{i}y_{0}z_{q+1-i}$.

Similar to before, we will show that $S_{q}$ is a degeneration of $T_{q+1}$, which we can write as

Our degeneration is as follows: $a(x_{0})=b(x_{0})=0$, $a(x_{i})=b(y_{i})=1$ for all $i\geq 1$, $c(z_{q})=0$ and $c(z_{k})=-1$ for all $k\geq 1$. Simple casework shows again that the possible values for $a(x_{i})+b(y_{j})+c(z_{k})$ are $0,1,2$, and that is only achieved for the terms in $S_{q}$. Among other things, this degeneration gives a simple proof that the border rank of $S_{q}$ is $q+1$.

Since a monomial degeneration of a rank expression gives a border rank expression, this shows in particular that the border rank of CWq is $q+2$. Furthermore, it shows that the best known bounds for $\omega$ [CW90, Wil12, LG14] can be obtained from $T_{7}$. Finally, since we only used monomial degenerations, we will be able to obtain lower bounds on what bounds on $\omega$ one can achieve via zeroing out powers of the CWq tensor.

Independent Triples in Matrix Multiplication Tensors

In this section we show that there is a zeroing out of any matrix multiplication tensor into a fairly large independent tensor. This strengthens a classic result (see eg. [Blä13, Lemma 8.6]) that any matrix multiplication tensor has a monomial degeneration into a fairly large independent tensor.

For every positive integer $q$, and $\varepsilon\in(0,1]$, there is a zeroing out of $\langle q,q^{\varepsilon},q\rangle^{\otimes n}$ into $q^{(1+\varepsilon)n-o(n)}$ independent triples.

Recall that $\langle q,q^{\varepsilon},q\rangle=\sum_{i=1}^{q}\sum_{j=1}^{q^{\varepsilon}}\sum_{k=1}^{q}x_{ij}y_{jk}z_{ki}$. Hence,

We will zero out variables in three phases, and after the third phase we will have a sufficiently large independent tensor as desired.

For vectors ${\vec{i}},{\vec{k}}\in[q]^{n}$, and values $a,b\in[q]$, let $t_{ab}({\vec{i}}{\vec{k}})$ denote the number of $1\leq\alpha\leq n$ such that ${\vec{i}}_{\alpha}=a$ and ${\vec{k}}_{\alpha}=b$. We say that ${\vec{i}}{\vec{k}}$ is balanced if, for all $a,b,c,d\in[q]$, we have $t_{ab}({\vec{i}}{\vec{k}})=t_{cd}({\vec{i}}{\vec{k}})$. We similarly say that ${\vec{i}}{\vec{j}}$ is balanced if $t_{ab}({\vec{i}}{\vec{j}})=t_{cd}({\vec{i}}{\vec{j}})$ for every $a,c\in[q]$ and $b,d\in[q^{\varepsilon}]$, and say that ${\vec{j}}{\vec{k}}$ is balanced similarly. In the first phase, we zero out every variable $x_{{\vec{i}}{\vec{j}}}$ such that ${\vec{i}}{\vec{j}}$ is not balanced. We similarly zero out $y_{{\vec{j}}{\vec{k}}}$ such that ${\vec{j}}{\vec{k}}$ is not balanced, and $z_{{\vec{k}}{\vec{i}}}$ such that ${\vec{k}}{\vec{i}}$ is not balanced.

Note that if ${\vec{i}}{\vec{k}}$ is balanced, then for each $a,b\in[q]$, we have $({\vec{i}}_{\alpha},{\vec{k}}_{\alpha})=(a,b)$ for exactly $n/q^{2}$ choices of $\alpha\in[n]$. Hence, the number of choices of ${\vec{i}},{\vec{k}}\in[q]^{n}$ such that ${\vec{i}}{\vec{k}}$ is balanced is exactly $L_{2}:=\binom{n}{\frac{n}{q^{2}},\frac{n}{q^{2}},\ldots,\frac{n}{q^{2}}}=q^{2n-o(n)}$. If ${\vec{i}}{\vec{k}}$ is balanced, then notice that the number $K_{\varepsilon}$ of choices of ${\vec{j}}\in[q^{\varepsilon}]^{n}$ such that ${\vec{i}}{\vec{j}}$ and ${\vec{j}}{\vec{k}}$ are also balanced is independent of what ${\vec{i}}$ and ${\vec{k}}$ are, and satisfies $K_{\varepsilon}=q^{O(n)}$.

Similarly, the number of choices of ${\vec{i}}\in[q]^{n}$ and ${\vec{j}}\in[q^{\varepsilon}]^{n}$ such that ${\vec{i}}{\vec{j}}$ is balanced is $L_{1+\varepsilon}:=\binom{n}{\frac{n}{q^{1+\varepsilon}},\frac{n}{q^{1+\varepsilon}},\ldots,\frac{n}{q^{1+\varepsilon}}}=q^{(1+\varepsilon)n-o(n)}$. Moreover, when ${\vec{i}}{\vec{j}}$ is balanced, the number $K_{1}$ of choices of ${\vec{k}}$ such that ${\vec{i}}{\vec{k}}$ and ${\vec{j}}{\vec{k}}$ are balanced satisfies $K_{1}=q^{O(n)}$. Note that $L_{2}K_{\varepsilon}=L_{1+\varepsilon}K_{1}$, since both count the number of triples remaining after phase one, and in particular, $K_{1}\geq K_{\varepsilon}$.

2 Phase two

Let $M$ be an odd prime number to be determined. Pick $w_{0},w_{1},\ldots,w_{n}\in[M]$ independently and uniformly at random, then define the hash functions $h_{X}:X\to[M]$, $h_{Y}:Y\to[M]$, and $h_{Z}:Z\to[M]$, by:

${\vec{i}}{\vec{j}}$, ${\vec{j}}{\vec{k}}$, and ${\vec{k}}{\vec{i}}$ are balanced, and

$h_{X}(x_{{\vec{i}}{\vec{j}}})=h_{Y}(y_{{\vec{j}}{\vec{k}}})=h_{Z}(z_{{\vec{k}}{\vec{i}}})$.

3 Phase three

In the third phase we zero out some remaining variables to ensure that our resulting tensor is independent. First, however, we will compute some expected values.

We now do our final zeroing out. If there are any distinct terms $x_{{\vec{i}}{\vec{j}}}y_{{\vec{j}}{\vec{k}}}z_{{\vec{k}}{\vec{i}}}$ and $x_{{\vec{i}}^{\prime}{\vec{j}}^{\prime}}y_{{\vec{j}}^{\prime}{\vec{k}}^{\prime}}z_{{\vec{k}}^{\prime}{\vec{i}}^{\prime}}$ remaining in our tensor such that ${\vec{i}}={\vec{i}}^{\prime}$ and ${\vec{j}}={\vec{j}}^{\prime}$, then we zero out $x_{{\vec{i}}{\vec{j}}}$. We similarly zero out any variables $y_{{\vec{j}}{\vec{k}}}$ or $z_{{\vec{k}}{\vec{i}}}$ which appear in multiple terms. As a result, our final tensor is definitely independent.

It remains to show that it has enough terms remaining. Since each pair of terms left from phase two which share a variable is removed in phase three, we see that the number of terms remaining is at least

Let us pick $M$ to be an odd prime number in the range $[12K_{1},24K_{1}]$. Hence, using our expected value calculations from before, we see that the expected number of remaining terms is at least

where the last step follows since $L_{1+\varepsilon}=q^{(1+\varepsilon)n-o(n)}$ and $K_{1}=q^{O(n)}$. By the probabilistic method, there is a choice of hash functions which achieves this expected number of independent triples, as desired. ∎

Monomial Degenerations

Suppose $A$ and $B$ are two tensors over $X,Y,Z$ such that $A$ is a monomial degeneration of $B$. Further suppose that $A^{\otimes n}$ has zeroing out into $f(n)$ independent triples. Then, $B^{\otimes n}$ has a zeroing out into $\Omega(f(n)/n^{2})$ independent triples.

$a(x_{i})+b(y_{j})+c(z_{k})\geq 0$ for all $x_{i}y_{j}z_{k}\in B$, and

furthermore $a(x_{i})+b(y_{j})+c(z_{k})=0$ if and only if $x_{i}y_{j}z_{k}\in A$.

$a^{n}(x_{i_{1}},\ldots,x_{i_{n}})+b^{n}(y_{j_{1}},\ldots,y_{j_{n}})+c^{n}(z_{k_{1}},\ldots,z_{k_{n}})\geq 0$ for all $x_{i_{1}}\cdots x_{i_{n}}y_{j_{1}}\cdots y_{j_{n}}z_{k_{1}}\cdots z_{k_{n}}\in B^{\otimes n}$, and

furthermore $a^{n}(x_{i_{1}},\ldots,x_{i_{n}})+b^{n}(y_{j_{1}},\ldots,y_{j_{n}})+c^{n}(z_{k_{1}},\ldots,z_{k_{n}})=0$ if and only if $x_{i_{1}}\cdots x_{i_{n}}y_{j_{1}}\cdots y_{j_{n}}z_{k_{1}}\cdots z_{k_{n}}\in A^{\otimes n}$.

The range of $a^{n}$ is integers in $[a^{-}n,a^{+}n]$. For each integer $p$ in that range, let $X^{n}_{p}$ be the set of $x_{i_{1}}\cdots x_{i_{n}}\in X^{n}$ such that $a^{n}(x_{i_{1}}\cdots x_{i_{n}})=p$. Define $Y^{n}_{q}$ for integers $q\in[b^{-}n,b^{+}n]$, and $Z^{n}_{r}$ for integers $r\in[c^{-}n,c^{+}n]$, similarly. Now, for $(p,q,r)\in[a^{-}n,a^{+}n]\times[b^{-}n,b^{+}n]\times[c^{-}n,c^{+}n]$, let $B^{\otimes n}_{p,q,r}$ be the tensor one gets from $B^{\otimes n}$ by zeroing out all the $X^{n}$ variables not in $X^{n}_{p}$, all the $Y^{n}$ variables not in $Y^{n}_{q}$, and all the $Z^{n}$ variables not in $Z^{n}_{r}$. Then, letting $W$ be the set of triples of integers in $[a^{-}n,a^{+}n]\times[b^{-}n,b^{+}n]\times[c^{-}n,c^{+}n]$, we see that

and each term of $A^{\otimes n}$ appears in exactly one of the summands. Now, let $A^{\otimes n\prime}$ be the zeroing out of $A^{\otimes n}$ into $f(n)$ independent triples. Let $B^{\otimes n\prime}_{p,q,r}$ be the zeroing out of $B^{\otimes n}_{p,q,r}$ in which we zero out those same variables. Hence,

where the sum is hence a disjoint sum of independent triples. The number of terms on the right is $O(n^{2})$, and so at least one of the terms on the right must have size at least $|A^{\otimes n\prime}|/O(n^{2})=\Omega(f(n)/n^{2})$, as desired. ∎

Main Theorem

In this section, we will combine our results above with the bounds on the sizes of tri-colored sum-free sets from past work in order to prove our main theorem. Recall the definition of $\gamma_{p}$ from Section 1.4, and define $c_{p}:=e^{\gamma_{p}}$.

Let $\varepsilon\in(0,1]$. Let T be a tensor that is a monomial degeneration of $T_{p}$ and suppose that $T^{\otimes N}$ can be zeroed out into $F~{}\odot\langle G,G^{\varepsilon},G\rangle$, giving a bound $\omega_{\varepsilon}\leq\omega^{\prime}_{\varepsilon}$ where $G^{\omega^{\prime}_{\varepsilon}}=\lceil p^{N}/F\rceil$. Then $\omega^{\prime}_{\varepsilon}\geq(1+\varepsilon)\log_{c_{p}}p$.

Let $g=G^{1/N}$ so that $G=g^{N}$, and let $f=F^{1/N}$ so that $F=f^{N}$. Since $T^{\otimes N}$ can be zeroed out into $F~{}\odot\langle G,G^{\varepsilon},G\rangle$, via Lemma 4.1, $T^{\otimes N}$ can be zeroed out into $f^{N}\cdot g^{(1+\varepsilon)N-o(N)}$ independent triples. Due to Lemma 5.1 this means that $T_{p}^{\otimes N}$ can also be zeroed out into $D=f^{N}\cdot g^{(1+\varepsilon)N-o(N)}/N^{2}$ independent triples.

Now, let $S=\{(a_{1},b_{1},c_{1}),\ldots,(a_{D},b_{D},c_{D})\}$ be the indices of the $D$ independent triples obtained from $T_{p}^{\otimes N}$. Because they are obtained by zeroing out $T_{p}^{\otimes N}$, for every $i$, $a_{i}+b_{i}+c_{i}\equiv 0$ in $Z_{p}^{N}$. Now suppose that for some $i,j,k$, $a_{i}+b_{j}+c_{k}\equiv 0$ in $Z_{p}^{N}$. If $i,j,k$ are not all the same, then $(a_{i},b_{j},c_{k})$ cannot be in $S$ as the triples in $S$ are independent. However, the only way for a triple of $T_{p}^{\times N}$ to be removed is if $X_{a_{i}}$ or $Y_{b_{j}}$ or $Z_{c_{k}}$ is set to zero. Suppose that $X_{a_{i}}$ is set to (the other two cases are symmetric). Then there can be no triple in $S$ sharing $a_{i}$ as its first index. Thus in fact $S$ forms a tri-colored sum-free set. Hence $D\leq c_{p}^{N}$.

From our earlier bound on $D$ we get that $f^{N}\cdot g^{(1+\varepsilon)N-o(N)}/N^{2}\leq c_{p}^{N}$, and taking the $N$th root of both sides yields $fg^{1+\varepsilon-o(1)}/N^{2/N}\leq c_{p}$.

Recall that $G^{\omega^{\prime}_{\varepsilon}}=\lceil p^{N}/F\rceil$, so that $g=(\lceil p/f\rceil)^{1/\omega^{\prime}_{\varepsilon}}$. Plugging in above, we get that $f(\lceil p/f\rceil)^{(1+\varepsilon)/\omega^{\prime}_{\varepsilon}-o(1)}\leq c_{p}.$ Hence, $f^{1-(1+\varepsilon)/\omega^{\prime}_{\varepsilon}+o(1)}p^{(1+\varepsilon)/\omega^{\prime}_{\varepsilon}-o(1)}\leq c_{p}.$ Since $\omega^{\prime}_{\varepsilon}\geq(1+\varepsilon)$, we have that $f^{1-(1+\varepsilon)/\omega^{\prime}_{\varepsilon}+o(1)}\geq 1$. We obtain that $(1+\varepsilon)/\omega^{\prime}_{\varepsilon}\leq\log_{p}c_{p}+o(1)$ and

As a corollary we obtain the following upper bound on what $\alpha$ can be achieved by zeroing out.

Let $T$ be a tensor that is a monomial degeneration of $T_{p}$. If one can prove $\alpha\leq\alpha^{\prime}$ using the zeroing-out approach then, $\alpha^{\prime}\leq\frac{2}{\log_{c_{p}}p}-1$.

References

Appendix A Supporting Calculations

We recall some definitions from earlier in the paper. For any integer $q\geq 2$, let $\rho$ be the unique number in $(0,1)$ satisfying

$\lim_{q\to\infty}\frac{\gamma_{q}}{\ln(q)}=1$.

Rearranging, we see that $\rho>1-3/(q-1)$. Hence,

As $q\to\infty$, we have that $\ln_{q}((q-1)/3)\to 1$ and $(q-1)\ln_{q}(1-3/(q-1))\to 0$, as desired. ∎