More Asymmetry Yields Faster Matrix Multiplication
Josh Alman Ran Duan Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou









centercolon










]}

algocfAlgorithmAlgorithms
algocfAlgorithmAlgorithms
claimClaimClaims










decorations.pathreplacing
calc

positioning
arrows.meta

plain
probProblem
openOpen Question
theoremTheorem[section]
lemma[theorem]Lemma
fact[theorem]Fact
observation[theorem]Observation
prop[theorem]Proposition
cor[theorem]Corollary
claim[theorem]Claim
definition
definition[theorem]Definition
remark[theorem]Remark
property[theorem]Property



proofof[1]
proofsketch
proofsketchof[1]



‖‖

















































































































@mathaccentsingle[3]
  0"0362#1^H
  2"03620pt#1^H
  0=2 #3#2
kern[1]#1@kerna

bar[2]@single#1@bar@#1#21@bar@#1#22
bar@[3]
  ##1##2
    @mathaccent
    #32 @nucleus@char @@style@nucleus_
    @@style@nucleus_
    @@
    @-@
    @ 3
    tempdima@
    tempdima-tempdima 10
    @-tempdima
    @>@ @0pt@kern0.6-@
    #31
      @kern-0.6@@nucleus@kern0.4@
      @0.4@kerna
      @kern#2
      @<@ @kern1@kern1 -@@kern-0.6@#1
    
  @depthne
  @bgroupempty @egroup@set@skewchar
  @ @everymath@group
  @set@skewchar@nested@a
  #31
    @nested@a111#1
  @till@marker##1
    @char@till@marker#1@char A@char
    @nested@a111@char
  




@restatable
#2xanx#1nx[#1]
@thisistheone
#2xanx#1nx[#1]#2xa[Restated]



































  





















  







































































=10000








gobble 
More Asymmetry Yields Faster Matrix Multiplication
    
  
  Josh AlmanColumbia University. . Supported in part by NSF Grant CCF-2238221 and a grant from the Simons Foundation (Grant Number 825870 JA).
  Ran DuanInstitute for Interdisciplinary Information Sciences, Tsinghua University. .
  Virginia Vassilevska WilliamsMassachusetts Institute of Technology. . Supported by NSF Grant CCF-2330048, BSF Grant 2020356 and a Simons Investigator Award. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  
  
  Yinzhan XuMassachusetts Institute of Technology. . Partially supported by NSF Grant CCF-2330048, BSF Grant 2020356 and a Simons Investigator Award. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  Zixuan XuMassachusetts Institute of Technology. .
  Renfei ZhouInstitute for Interdisciplinary Information Sciences, Tsinghua University. .
  

    
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent

    ω<2.371339,

improved from the previous bound of ω<2.371552. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.






arabic



§ INTRODUCTION

Multiplication of matrices is a fundamental algebraic primitive with applications throughout computer science and beyond. The study of its algorithmic complexity has been a vibrant area in theoretical computer science and mathematics ever since Strassen's <cit.> 1969 discovery that the rank of 2 by 2 matrix multiplication is 7 (and not 8), leading to the first truly subcubic, O(n^2.81)  time algorithm for multiplying n× n matrices.
Fifty-five years later, researchers are still attempting to lower the exponent ω, defined as the smallest real number for which n× n matrices can be multiplied in O(n^ω+) time for all >0. 

After many decades of work (e.g. <cit.>), 
the current best bound ω<2.371552 was given by <cit.> optimizing a recent approach by Duan, Wu and Zhou <cit.>.

There is a straightforward lower bound of ω≥ 2 since the output size is n^2. 
No larger lower bound is known, leading many to optimistically conjecture that ω=2.
Unfortunately, several papers <cit.> prove significant limitations to all known approaches for designing matrix multiplication algorithms. The most general limitations <cit.> say that even big generalizations of the known approaches cannot prove ω=2. The most restricted limitation <cit.> focuses on the laser method defined by Strassen <cit.> and applied to the powers of a very particular tensor _5 defined by Coppersmith and Winograd <cit.>. This is the method that all the best results[Coppersmith and Winograd's paper <cit.> technically used _6 instead of _5, but the limitation of <cit.> on _6 is actually worse than those for _5.] from the last 38 years have used. The limitation says that the laser method on _5 cannot prove that ω<2.3078. All papers on matrix multiplication algorithms from the last 10 years or so have been focused on bringing the ω upper bound closer to this 2.3078 lower bound.



The main contribution of this paper is a new improvement over the laser method when applied to the powers of _5. The new method builds upon work of <cit.> and <cit.>  and yields new improved bounds on ω and several rectangular matrix multiplication exponents[
  The constraint programs that our new method leads to are significantly larger and more complex than in prior work. The nonlinear solver we are using struggles, and it can take many days for it to get a solution for any fixed ω(1,k,1). Unfortunately, 
  we were not able to solve the constraint program for the value α studied by Coppersmith <cit.> defined as the largest number such that n by n^α by n matrix multiplication can be done in O(n^2+) time for all >0. 
] ω(1,k,1) defined as the smallest real value for which n× k by k× n matrix multiplication can be done in O(n^ω(1,k,1)+) time for all >0; the previous best bounds for rectangular matrix multiplication were by <cit.>.

Our results are summarized in <ref>.
Our new bound on ω is 

    ω<2.371339,

improved from the previous bound by <cit.> of ω<2.371552, inching towards the lower bound of 2.3078.

As a specific example for a rectangular matrix multiplication exponent, we obtain a new bound for the exponent μ satisfying the equation ω(1,μ,1)=1+2μ. The previous bound from <cit.> was μ<0.527661 and we improve it to μ<0.5275. The value μ is a key part of the best known running times of several important problems, including All-Pairs Shortest Paths (APSP) in unweighted directed graphs <cit.>, computing minimum witnesses of Boolean Matrix Multiplication <cit.>, and All-Pairs Bottleneck Paths in node-weighted graphs <cit.>. Our new bound implies 
that all the aforementioned problems can be solved in O(n^2.5275) time, improving on the previous known running time of O(n^2.527661).



M[1]>m#1







§ TECHNICAL OVERVIEW


In this section, we give a high-level overview of recent algorithms for matrix multiplication and the new ideas we introduce in this paper for further improvement. We assume familiarity with notions related to tensors and matrix multiplication; the unfamiliar reader may want to read the preliminaries in Section <ref> below first. Afterward, in Section <ref>, we give a more detailed overview of how we design our new algorithm.




 §.§ The Laser Method and Asymptotic Sum Inequality


In order to design a matrix multiplication algorithm, using Schönhage's asymptotic sum inequality <cit.>, it suffices to give an upper bound on the asymptotic rank of a direct sum of matrix multiplication tensors. However, directly bounding the rank of a matrix multiplication tensor is quite difficult (for example, even determining the rank of the tensor for multiplying 3 × 3 matrices is still an open problem today), and so algorithms since the work of Coppersmith and Winograd <cit.> have used an indirect approach:

    
  * Start with the Coppersmith-Winograd tensor _q, which is known to have minimal asymptotic rank.
    
  * Take a large Kronecker power _q^⊗ n, which must therefore also have a small (asymptotic) rank.
    
  *  Use the laser method to show that _q^⊗ n has a zeroing out[If T is a tensor over X,Y,Z, a zeroing out of T is a tensor gotten by picking subsets X' ⊆ X, Y' ⊆ Y, Z' ⊆ Z, and restricting T to only those subsets.] to a large direct sum S of matrix multiplication tensors.
    
  * Since zeroing out cannot increase the tensor rank, this shows that S has a small (asymptotic) rank, and then we can apply Schönhage's asymptotic sum inequality.

The laser method in step <ref> is a tool introduced by Strassen <cit.> for converting Kronecker powers of tensors into direct sums of matrix multiplication tensors. All improvements since Coppersmith and Winograd's algorithm have used this approach <cit.>, focusing on improving the use of the laser method to yield a larger direct sum S of larger matrix multiplication tensors, and this is the step which we improve here as well.
The laser method is a general tool which applies to any tensor T that has been partitioned in a particular way. Let us first introduce some relevant notations.

Suppose T is a tensor over X,Y,Z, and we partition X = _i X_i, Y = _j Y_j, and Z = _k Z_k and define the subtensor T_i,j,k as T restricted to X_i, Y_j, Z_k. Thus, T is partitioned as T = ∑_i,j,k T_i,j,k. The laser method requires this partition to have additional structure[Namely, there must be an integer p such that T_i,j,k = 0 whenever i+j+k ≠ p. In the case of _q, we will use a partition with p=2.] which we will not focus on in this overview. Notably, when we take a Kronecker power T^⊗ n, which is a tensor over X^n, Y^n, Z^n, this can also be partitioned as T^⊗ n = ∑_I,J,K T_IJK where I,J,K are vectors of length n, and T_IJK⊗_ℓ=1^n T_I_ℓ J_ℓ K_ℓ is a tensor over X_I := ∏_ℓ=1^n X_I_ℓ, Y_J := ∏_ℓ=1^n Y_J_ℓ, Z_K := ∏_ℓ=1^n Z_K_ℓ.

Consider a probability distribution α on the subtensors of T, which assigns probability α_ijk to subtensor T_ijk. In the Kronecker power T^⊗ n, we can zero out according to the marginals of α. For instance, we zero out X_I ⊂ X^n unless, for all i, we have 1/n· |{ℓ∈ [n] | I_ℓ = i}| = ∑_j,kα_ijk. Assuming α is uniquely determined by its marginals (which is often not the case, as we will discuss more later), this means T^⊗ n has been zeroed out so that every remaining T_IJK is a copy (up to permutation of indices) of the tensor B = ⊗_i,j,k T_i,j,k^⊗α_ijk· n.

Summarizing, we have so far zeroed out T^⊗ n into a sum of many copies of the tensor B. However, this is not a direct sum. Indeed, for example, there can be many remaining T_IJK and T_I'J'K' with I = I', which both use X_I. 

The main result of the laser method is that a further, carefully-chosen zeroing out can result in a direct sum of copies of the tensor B, where each two remaining T_IJK and T_I'J'K' have I ≠ I', J ≠ J', and K ≠ K'. Moreover, this further zeroing out only removes a small number of X_I, Y_J, Z_K, so that a large number of copies of B remain. (The exact number is a combinatorial expression in terms of the marginals of α which we will discuss in more detail in later sections.)

When this method is applied to _q, each subtensor is in fact a matrix multiplication tensor, so B is also a matrix multiplication tensor. Thus, the output of the laser method can be directly given to the asymptotic sum inequality.



 §.§ Recursive Applications of the Laser Method to Tensor Powers of CWq


Coppersmith and Winograd <cit.> then noticed that the laser method can yield improved results when applied to the Kronecker square, _q^⊗ 2. 

Roughly speaking, the intuition is that the square gives us more freedom to pick the partition that is needed to apply the laser method, since partitions of _q correspond to only a subset of the possible partitions of _q^⊗ 2.  
Coppersmith and Winograd take advantage of this, and pick a partition of _q^⊗ 2 which allows the tensors T_IJK to become larger. 
In fact, compared to the partition obtained from analyzing  _q^⊗ 2n, the partition from analyzing  (_q^⊗ 2)^⊗ n is a coarsening of the previous partition (where, for instance, each X_I now is a union of possibly multiple previous X_I's). Thus, T_IJK, which is a tensor over the variable blocks X_I, Y_J, Z_K, is now larger. 
If the tensors T_IJK's were all matrix multiplication tensors, then the asymptotic sum inequality tends to give better bounds when they are larger. 
However, in this new partition, it is no longer the case that each subtensor is a matrix multiplication tensor. In other words, the laser method still yields a direct sum of copies of B = ⊗_i,j,k T_i,j,k^⊗α_ijk· n, but B is not a matrix multiplication tensor, so the asymptotic sum inequality cannot be directly applied. 

Coppersmith and Winograd solved this by applying the laser method recursively. They first applied the laser method to each subtensor T_i,j,k which is not a matrix multiplication tensor, showing that T_i,j,k^⊗ m for large m can zero out into direct sums of matrix multiplication tensors. Then, since the tensor B is a Kronecker product of such powers, this can be used to zero out into a direct sum of matrix multiplication tensors.

The next few improvements to ω <cit.> applied this recursive laser method approach to _q^⊗ 2^-1 for larger and larger integers ≥ 1. Similar to before, there is a natural partition X = _i X_i, Y = _j Y_j, and Z = _k Z_k of the variables from the base tensor _q^⊗ 2^-1, and products of X_i's, Y_j's or Z_k's form subsets of variables X_I's, Y_J's, or Z_K's in (_q^⊗ 2^-1)^⊗ n. We will call each subset of variables X_I, Y_J, Z_K a level- variable block and we call a subtensor obtained from restricting to some level-ℓ variable blocks a level-ℓ subtensor. Since the level-ℓ partition is a coarsening of the level-(ℓ-1) partition, each level- variable block is the union of possibly many level-(-1) variable blocks induced by the natural partition of _q^⊗ 2^-2, and consequently each level-ℓ subtensor is the sum of many level-(ℓ-1) subtensors.
As  increases, the task of applying the laser method to increasingly more intricate subtensors becomes more difficult, and significant algorithmic and computational challenges arise. 

The next improvement <cit.> focused on the case when the marginals of α do not uniquely determine α. In this case, there is a corresponding penalty that reduces the number of copies of B the laser method can achieve, and <cit.> showed a new approach to reduce this penalty.




 §.§ Asymmetry and Combination Loss


All improvements to the laser method thus far would apply equally well to any tensor with an appropriate partition. 
The next, recent improved algorithm <cit.> focused on improving the recursive use of the laser method specifically when it is applied to the Coppersmith-Winograd tensor _q in the recursive fashion described above.

The key observation, referred to as “combination loss” in their paper, is as follows. Above, in order to ensure that the laser method gave a direct sum of copies of B, previous works ensured that any two remaining level-ℓ subtensors do not share any level-ℓ variable blocks X_I, Y_J or Z_K. For ℓ = 1, namely when the laser method is applied to the first power of _q, this is both necessary and sufficient, because the level-1 subtensors are matrix multiplication tensors which use the entire level-1 variable blocks, so any two sharing an I, J, or K must intersect.



However, for ℓ > 1, the laser method needs to be applied recursively to every level-k subtensor for k = ℓ, ℓ-1,…, 1. This means that by the end of the algorithm, we are potentially only using a small fraction of the variables in the level-ℓ subtensor rather than the entire subtensor. So it is possible that even if two level-ℓ subtensors T_IJK and T_I'J'K share the same level-ℓ Z-variable block Z_K in the beginning, after recursive applications of the laser method, the subtensors of T_IJK and T_I'J'K which remain after zeroing out into matrix multiplication tensors may use disjoint subsets of Z_K, i.e., they may be independent. In this case, we could keep both T_IJK and T_I'J'K when we apply the laser method to _q^⊗ 2^ℓ-1 and still have a direct sum of subtensors, contrary to what was done in the previous algorithms where only one could be kept.



In order to benefit from this observation, one major issue is that when T_IJK and T_I'J'K are each zeroed out to their desired subtensors via the recursive applications of the laser method, they may each zero out parts of Z_K that are meant to be used by the other. Thus it is unclear how to control and analyze the recursive procedure so that we maximize the number of these subtensors remaining in the end while ensuring that they are indeed independent.

However, for the _q tensor, Duan, Wu and Zhou in <cit.> observed that the issue can be partially overcome. In particular, they were able to allow two level-ℓ subtensors to share level-ℓ variable blocks in the Z-dimension as long as they had the guarantee that any two level-ℓ subtensors do not share any level-ℓ blocks in the X- or Y-dimension. Due to the special structure of the _q tensor, it turns out that by ensuring independence among level-ℓ X- and Y-blocks, we can obtain sufficient information about the level-(ℓ-1) structure of Z-blocks in level-ℓ subtensors.
Therefore, by introducing asymmetry via treating the Z-variables differently from the X- and Y-variables, <cit.> obtained a procedure that obtains a collection of level-ℓ subtensors that do not share any level-(ℓ-1) Z-variable blocks, so they are independent. The follow-up work <cit.> further generalized the techniques presented in <cit.> and allowed the sharing of level-(ℓ-1) Z-variable blocks. In fact, their approach only requires that each level-1 Z-variable block belongs to a unique remaining level-ℓ subtensor T_IJK. This allowed them to obtain an improvement since each subtensor T_IJK can use a more “fine-grained” subset of Z-variables.









A priori, it's perhaps surprising that such an asymmetric approach, applied to the very symmetric Coppersmith-Winograd tensor, leads to an improved algorithm. In previous work, much effort was devoted to ensuring that the algorithm was entirely symmetric with respect to the X,Y,Z-dimensions. For instance, many intermediate steps of the laser method require taking the minimum of three quantities depending separately on X,Y,Z (like the entropies of the three marginal distributions of α), and picking a symmetric distribution prevents losses in these steps. Similarly, in the design of algorithms for rectangular matrix multiplication using the laser method <cit.>, one seems to truly suffer a penalty due to the necessary asymmetry. (For a rough comparison, symmetrizing the best rectangular matrix multiplication algorithms leads to a substantially worse square matrix multiplication algorithm.) However, the gains from the approach above ultimately outweigh the losses from asymmetry.



 §.§ Our Contributions: More Asymmetry


Following from the sequence of improvements obtained by <cit.>, the natural end goal for this line of work is to allow different remaining subtensors to share level- variable blocks in all three dimensions, and only require level-1 variable blocks to belong to unique remaining level-ℓ subtensors. However, it is unclear how one may achieve this goal since the algorithms of both  <cit.> and <cit.> crucially use the fact that different remaining level-ℓ subtensors use unique level- X- and Y-variable blocks. In this work, we make substantial progress toward this goal by allowing different remaining subtensors to share level- variable blocks in both the Y- and Z-dimensions.

In this work, we give a new approach in which we only require that any two level-ℓ subtensors do not share level-ℓ X-blocks. In particular, two level-ℓ subtensors can share the same level-ℓ Y-variable block or Z-variable block, but cannot share the same level-1 Y-variable block or Z-variable block, strengthening ideas in <cit.>. In this way, we are able to keep a larger number of level-ℓ subtensors and thus zero out the input _q^⊗ 2^ℓ-1 into more matrix multiplication tensors. This is achieved by introducing more asymmetry into our procedure: we now give a different zeroing-out procedure for each of the X,Y,Z-dimensions. This is perhaps unexpected, because in the end goal all X-, Y-, Z-dimensions have the same requirement that every level-1 variable block belongs to unique remaining level-ℓ subtensors. One might expect that a more symmetric implementation of the ideas of prior work would help towards the goal, but we instead use more asymmetry to get around a major limitation of the prior work.

Compared to the prior works, which use constrained information from both the X- and Y-dimensions to control the Z-dimension, we first use just the X-dimension to partially control the Y-dimension, and then use both the fully-controlled X-dimension and partially-controlled Y-dimension to control the Z-dimension. More specifically, by utilizing more structure specific to the  _q tensor, combined with the requirement that each level-ℓ subtensor T_IJK uses a unique level-ℓ X-block, we find that this already constrains T_IJK to use a smaller and more structured subset of level-1 Y-blocks, which is sufficient to perform zero-outs over level-1 Y-blocks so that each of them is contained in a unique level-ℓ subtensor. After obtaining a set of level-ℓ subtensors that do not share any level-ℓ X-blocks or level-1 Y-blocks, we then have enough information to do zero-outs over level-1 Z-blocks so that each of them are contained in a unique level-ℓ subtensor. See <ref> for a more detailed overview of our algorithm.













Similar to recent prior matrix multiplication algorithms, we need to solve a large, non-convex optimization problem in order to determine parameters for the laser method to achieve the best exponent. 
That said, we can already see that our new approach could potentially lead to an improvement without solving the optimization program to get the final bound for ω. A key parameter that reflects the effectiveness of the laser method is the hash modulus being used in the hashing step standard to all applications of the laser method, which determines the number of remaining level-ℓ subtensors we are able to keep in expectation. Minimizing the value of this hash modulus can give an improvement to the bound we are able to obtain for ω. The new hash modulus we use in this work is taken to be (ignoring low-order terms)

    max{/,  
    ·/, 
    ·/},

in comparison with the following value (similarly without low-order terms) used in <cit.>

    max{/,  
    /, 
    ·/}.

The definitions of all the variables in these expressions are not important for the purpose of this overview, and we focus instead on their structure.  
Two out of the three terms in the two bounds are the same, but we have improved the middle term from / to ·/, where  is a variable between 0 and 1 which we can pick in our optimization problem. In fact, even in the worst case = 1, we improve the second term by a factor of /, which is guaranteed to be at least 1 and is exactly the penalty term studied by <cit.>.  Thus, even if we pick = 1, we would at least recover the modulus of prior work. That said, since the modulus is defined by taking the maximum over the three values, it is not immediately clear that our approach uses a strictly smaller modulus. 
However, by solving the new constraint program,
one can verify that even in _q^⊗ 2, the optimal parameters use a smaller value of , which leads to a better bound on ω. Indeed, our new approach gives a better analysis of _q^⊗ 2 than prior work, improving from the bound ω < 2.374399 achieved by <cit.>[The subsequent work <cit.> improves the analysis of higher powers of _q but not the square.] to  ω < 2.37432. 








 §.§ Limitations to Our Techniques



In our approach, we successfully allow all obtained level-ℓ subtensors to share level-k variable blocks for any 1<k≤ℓ in both the Y- and Z-dimensions, as long as they are independent with respect to the level-1 blocks. However, we still require that none of them share  level-ℓ X-blocks. In an ideal approach, to truly maximize the number of independent tensors, the subtensors should also be allowed to share level-ℓ X-blocks as long as they do not share level-1 X-blocks. 
However, there does not seem to be a way to continue our approach to also allow the X blocks to share level-ℓ-blocks. Our approach crucially uses the fact that a level-ℓ X-block uniquely determines the level-ℓ subtensor that it belongs in, to control the structure of level-1 blocks in level-ℓ subtensors. It seems that a truly new idea is needed to be able to control this structure without making the level-ℓ subtensors to have unique level-ℓ variable blocks in one of the dimensions. In other words, we believe that we have reached the limit of generalizing the techniques introduced in <cit.>.





Second, as in all recent improvements, determining the final running time of our matrix multiplication algorithm requires solving a non-convex optimization problem to determine the best choice of the probability distribution α to use in the laser method. Since we can no longer use a symmetry between the X- and Y-dimensions, our new optimization problem has more variables and appears to be considerably harder to solve to high precision than the problems in prior work. It would be particularly exciting to find an approach to improving ω which does not escalate the need for powerful optimization software and computing systems.




§ PRELIMINARIES



We use by now standard notation as in <cit.>. The experienced reader may skip this section, as the definitions and notation are the same as in prior work.



 §.§ Tensors and Tensor Operations





  
Tensors. 
We deal with tensors of order 3 which can be viewed as either 3-dimensional arrays or as trilinear polynomials. We consider the latter representation:

A tensor T over variable sets X = x_1, …, x_|X|, Y = y_1, …, y_|Y|, Z = z_1, …, z_|Z| and field  is a trilinear form

    T = ∑_i=1^|X|∑_j=1^|Y|∑_k=1^|Z| a_i,j,k· x_i y_j z_k,

where all a_i,j,k are from . 



All tensors in this paper have all their entries a_i,j,k∈0, 1.
As any field  has a 0 and a 1, all tensors in the paper can be considered to be over any . 


In the following, assume T is a tensor over X = x_1, …, x_|X|, Y = y_1, …, y_|Y|, Z = z_1, …, z_|Z| and T' is a tensor over X' = x'_1, …, x'_|X'|, Y' = y'_1, …, y'_|Y'|, Z' = z'_1, …, z'_|Z'|, written as

    T = ∑_i=1^|X|∑_j=1^|Y|∑_k=1^|Z| a_i,j,k· x_i y_j z_k,     
      T' = ∑_i=1^|X'|∑_j=1^|Y'|∑_k=1^|Z'| b_i,j,k· x'_i y'_j z'_k,



  
Tensor Operations. 
We define the sum, direct sum and Kronecker product of two tensors T and T':


  * The sum T + T' is only defined when both tensors are over the same variable sets (X, Y, Z) = (X', Y', Z'). T+T' is the tensor defined by the sum of the two polynomials defining T and T':
  
    T + T' = ∑_i=1^|X|∑_j=1^|Y|∑_k=1^|Z| (a_i,j,k + b_i,j,k) · x_i y_j z_k.


  * The direct sum T ⊕ T' is the sum T+T' when the variable sets of T and T' are disjoint. In this case, T' and T' are said to be independent.

If T and T' share variables, we first relabel their variables so that the variable sets are disjoint and then T ⊕ T' is the sum of the two polynomials over new variables.






We write T^⊕ nT ⊕ T ⊕⋯⊕ T_n to denote the sum of n independent copies[This is often written as n⊙ T.] of T.


  * The Kronecker product is defined as the tensor
  
    T ⊗ T' = ∑_i=1^|X|∑_j=1^|Y|∑_k=1^|Z|∑_i'=1^|X'|∑_j'=1^|Y'|∑_k'=1^|Z'| a_i,j,k· b_i', j', k'· (x_i, x'_i') · (y_j, y'_j') · (z_k, z'_k')

  over variable sets X × X', Y × Y', and Z × Z'. We write T^⊗ nT ⊗ T ⊗⋯⊗ T_n to denote the n-th tensor power of T.

  * We say T and T' are isomorphic[Note that in the literature, a more general type of isomorphism is considered, where T and T' can be transformed into one another under arbitrary linear transformations between X and X', Y and Y' and Z and Z', or even more generally under degenerations.], denoted by T ≡ T', if |X| = |X'|, |Y| = |Y'|, |Z| = |Z'|, and there are permutations π_X, π_Y, π_Z over [|X|], [|Y|], [|Z|] respectively, such that a_i,j,k = b_π_X(i), π_Y(j), π_Z(k) for all i, j, k. In other words, both tensors are equivalent up to a relabeling of the variables. 





 §.§ Tensor Rank

A tensor T over X, Y, Z has rank 1 if there are some vectors a,b,c of length |X|,|Y|,|Z|, respectively so that 

    T=∑_i = 1^|X| a_i· x_i ∑_j = 1^|Y| b_j· y_j ∑_k = 1^|Z| c_k· z_k.


For a tensor T over X, Y, Z, the tensor rank R(T) is defined to be the minimum integer r≥ 0 such that T can be written as the sum of r rank 1 tensors.
The corresponding sum is called the rank decomposition of T.


Tensor rank satisfies subadditivity and submultiplicativity:


    
  * R(T+T')≤ R(T) + R(T').
    
  * R(T⊕ T')≤ R(T) + R(T').
    
  * R(T⊗ T')≤ R(T)· R(T').


The third item above implies that for all m, R(T^⊗ n)≤ R(T)^m, and for many tensors (e.g. 2× 2 matrix multiplication) the inequality is strict. Due to Fekete's lemma, the following
 asymptotic rank R(T) is well-defined for every tensor T: 

    R(T) := lim_n→∞R(T^⊗ n)^1/n.

The asymptotic rank is upper bounded by R(T^⊗ m)^1/m for any fixed integer m > 0.



 §.§ Degenerations, Restrictions, Zero-outs

Let T and T' be tensors over a field , T is over X, Y, Z and T' is over X', Y', Z'. 



  
Degeneration.
Let [λ] be the ring of polynomials of the formal variable λ. We say that T' is a degeneration of T, written as T  T', if there exists [λ]-linear maps 

    ϕ_X    : _[λ](X)→_[λ](X'),
    ϕ_Y    : _[λ](Y)→_[λ](Y'),
    ϕ_Z    : _[λ](Z)→_[λ](Z'),

and d∈ such that  

    T' = λ^-d∑_i = 1^|X|∑_j = 1^|Y|∑_k = 1^|Z|a_i,j,k·ϕ_X(x_i) ·ϕ_Y(y_j) ·ϕ_Z(z_k) + O(λ).


If T' T, then R(T')≤R(T).



  
Restriction.
Restriction is a special type of degeneration for the case where the maps ϕ_X,ϕ_Y, ϕ_Z are -linear maps. More specifically, T' is a restriction of T if there exist -linear maps

    ϕ_X    : _(X)→_(X'),
    ϕ_Y    : _(Y)→_(Y'),
    ϕ_Z    : _(Z)→_(Z'),

such that

    T' = ∑_i = 1^|X|∑_j = 1^|Y|∑_k = 1^|Z|a_i,j,k·ϕ_X(x_i) ·ϕ_Y(y_j) ·ϕ_Z(z_k).

If T' is a restriction of T, R(T')≤ R(T) and consequently R(T')≤R(T).




  
Zero-out.

The laser method utilizes a limited type of restriction called zero-out, namely the maps ϕ_X, ϕ_Y, ϕ_Z set some variables to zero. More specifically, for subsets X'⊆ X, Y'⊆ Y, Z'⊆ Z we define the maps as 

    ϕ_X(x_i) = x_i    If x_i∈ X',
     0    otherwise,

and similarly for ϕ_Y, ϕ_Z. The resulting tensor 

    T' = ∑_i = 1^|X|∑_j = 1^|Y|∑_k = 1^|Z|a_i,j,k·ϕ_X(x_i) ·ϕ_Y(y_j) ·ϕ_Z(z_k) = ∑_x_i∈ X'∑_y_j∈ Y'∑_z_k∈ Z'a_i,j,k· x_iy_jz_k

is called a zero-out of T. Throughout this paper, we use the notation T' = T|_X',Y',Z' to denote the tensor T' obtained from T by setting the variables in X∖ X', Y∖ Y', Z∖ Z' to zero. In this case, we also call T' the subtensor of T over X', Y', Z'.



 §.§ Matrix Multiplication Tensors


For positive integers a,b,c, the a× b × c matrix multiplication tensor a,b,c is a tensor over the variable sets {x_ij}_i∈ [a], j∈ [b], {y_jk}_j∈ [b],k∈[c], {z_ki}_i∈ [a],k∈ [c] defined as the tensor computing the a× c (transpose of the) product matrix
{z_ki}_i∈ [a], k∈ [c]
of an a× b matrix {x_ij}_i∈ [a], j∈ [b] and b× c matrix {y_jk}_j∈ [b], k∈ [c]. Specifically, 

    a,b,c = ∑_i∈ [a]∑_j∈ [b]∑_k∈ [c] x_ij y_jk z_ki.

Notice that the coefficient in front of z_ki is the (i,k) entry of the product of x with y.
It is not hard to check that a,b,c⊗d,e,f≡ad, be, cf.

Following from the recursive approach introduced by Strassen in <cit.>, for any integer q ≥ 2, if R(q,q,q)≤ r, then one can use the rank decomposition of q,q,q to design an arithmetic circuit of size O(n^log_q(r)) to multiply two n × n matrices. This motivates the definition of the matrix multiplication exponent ω as follows:

    ω := inf_q ∈,   q ≥ 2log_q (R(q,q,q)).

Namely, for every > 0, there exists an arithmetic circuit of size O(n^ω + ) that computes the multiplication of two n× n matrices. Since q,q,q^⊗ n≡q^n, q^n, q^n, equivalently ω can be written in terms of the asymptotic rank of q,q,q as 

    ω = log_q (R(q,q,q)).


We also consider the arithmetic complexity of multiplying rectangular matrices of sizes n^a× n^b and n^b× n^c where a,b,c ∈_≥ 0. We define ω(a,b,c) as 

    ω(a,b,c) = log_qR(q^a,q^b,q^c)

where q ≥ 2 is a positive integer. This means that for any > 0, there exists an arithmetic circuit of size O(n^ω(a,b,c) + ) that computes the multiplication of an n^a× n^b matrix with an n^b× n^c matrix. 

It is known that ω(a,b,c)=ω(a,c,b)=ω(c,a,b) so that the value remains the same for any permutation of the dimensions a,b,c.
In this paper, we focus on bounds for ω(1,κ,1) for κ > 0. 



 §.§ Schönhage's Asymptotic Sum Inequality


From a bound r on the rank of any a,b,c tensor, one can obtain an upper bound ω≤ 3log_abc(r).
 Schönhage <cit.> extended this fact by showing that one can obtain an upper bound on ω using any upper bound on the asymptotic rank of a direct sum of matrix multiplication tensors:


For positive integers r > m and a_i, b_i,c_i for i∈ [m], if 

    R⊕_i = 1^m a_i,b_i,c_i≤ r,

then ω≤ 3τ where τ∈ [2/3,1] is the solution to the equation

    ∑_i = 1^m (a_i· b_i· c_i)^τ = r.



Analogously, the asymptotic sum inequality can also be used to obtain bounds on the rectangular matrix multiplication as follows.


    Let t,   q > 0 be positive integers and a,b,c ≥ 0 , then
    
    t· q^ω(a,b,c)≤R⊕_i = 1^t q^a, q^b,q^c.






 §.§ The Coppersmith-Winograd Tensor


For a nonnegative integer q≥ 0, the Coppersmith-Winograd tensor _q over the variables X = {x_0,…, x_q+1}, Y = {y_0,…, y_q+1}, Z = {z_0,…, z_q+1} is defined as

    _q := x_0y_0z_q+1 + x_0y_q+1z_0 + x_q+1y_0z_0 + ∑_i = 1^q x_0y_iz_i + x_iy_0z_i + x_iy_iz_0.


Coppersmith and Winograd <cit.> showed that R(_q) ≤ q+2.

Observe that 

    CW_q ≡1,1,q + q,1,1 + 1,q,1 + 1,1,1+1,1,1+1,1,1,

where unfortunately + is a sum and not a direct sum, so that Schönhage's theorem doesn't immediately apply.

The goal of the laser method is to zero out variables in CW_q^⊗ n so that Schönhage's theorem can be applied.



 §.§ Base Leveled Partition of CWq


Consider the 2^-1-th tensor power of _q for ≥ 1. For convenience, denote T^() := _q^⊗ 2^-1. 

Coppersmith and Winograd <cit.>
defined a partitioning of the variables of _q which is used in all following works including <cit.>. 
We call this the level-1 partition. More generally, we
describe the leveled partition of T^() which also comes from <cit.> and the subsequent works.




  
Level-1 Partition. For T^(1) = _q, its variable sets X^(1), Y^(1), Z^(1) are partitioned into three parts

    X^(1)   = X^(1)_0 ⊔ X^(1)_1 ⊔ X^(1)_2 = {x_0}⊔{x_1,…, x_q}⊔{x_q+1},
    
        Y^(1)   = Y^(1)_0 ⊔ Y^(1)_1 ⊔ Y^(1)_2 = {y_0}⊔{y_1,…, y_q}⊔{y_q+1},
    
        Z^(1)   = Z^(1)_0 ⊔ Z^(1)_1 ⊔ Z^(1)_2 =  {z_0}⊔{z_1,…, z_q}⊔{z_q+1}.

We  denote the subtensor T^(1)|_X_i,Y_j,Z_k by T_i,j,k^(1) and we call it a level-1 constituent tensor. Note that T^(1)_i, j, k is nonzero if and only if i+j+k = 2. In particular, we can write _q as a sum of constituent tensors as follows

    T^(1) = _q = ∑_i,j,k≥ 0
     i+j+k = 2 T_i,j,k^(1).




  
Level- Partition. For T^()=_q^⊗ 2^-1 with variable sets X^(), Y^(), Z^(), the above level-1 partition on T^(1) induces a natural partition on the variable sets X^(), Y^(), Z^() 
where parts are indexed by {0, 1, 2}-sequences of length 2^-1. Specifically, for the X variables we get the partition

    X^() = _(î_1, î_2, …, î_2^-1) ∈{0, 1, 2}^2^-1X^(1)_î_1⊗  X^(1)_î_2⊗⋯⊗ X^(1)_î_2^-1.

The partitions for Y- and Z-variables are analogous. 


Prior work starting with <cit.> used partitions obtained from the above induced partitions by merging parts whose sequences indices sum to the same number.


    X^() = _i = 0^2^ X_i^(),
            
      X_i^()_(î_1, î_2, …, î_2^-1) ∈{0, 1, 2}^2^-1
    ∑_t î_t = iX^(1)_î_1⊗  X^(1)_î_2⊗⋯⊗ X^(1)_î_2^-1.

This above partition of T^() is called the level- partition.
One can also view this partition as a coarsening of the level-(-1) partition via merging, i.e.,
 
    X_i^() = _0 ≤ i' ≤ i 
     0 ≤ i', i - i' ≤ 2^X^(-1)_i'⊗ X^(-1)_i-i'.

The variable sets Y^() and Z^() are partitioned similarly. 
 
 Under the level- partition, denote the subtensor T^()|_X_i^(), Y_j^(), Z_k^() by T^()_i, j, k and call it a level- constituent tensor.
 Call X^()_i, Y^()_j, Z^()_k level- variable blocks. We omit the superscript () when  is clear from context.
 
 Note that T^()_i, j, k≠ 0 if and only if i+j+k = 2^. Thus:
 
 
    T^() = _q^⊗ 2^-1= ∑_i,j,k≥ 0
     i+j+k = 2^ T_i,j,k^().




 §.§ Leveled Partition for Large Tensor Powers of CWq


In the laser method, we focus on a tensor power of _q in the form (T^())^⊗ n = (_q)^⊗ n· 2^-1. We set N := n· 2^-1 and note that the leveled partition of T^() induces a partition on (T^)^⊗ n. We recall some basic terminology and notation with respect to the leveled-partition of (T^)^⊗ n.



  
Level-1 partition of (_q)^⊗ N.
In level-1, we view (_q)^⊗ N as the tensor (T^(1))^⊗ N and consider the partition induced by the level-1 partition on T^(1). Each level-1 X-variable block X_Î is indexed by a sequence Î = (Î_1,…, Î_N) of length N in {0,1,2}^N. The variable block X_I is defined as 

    X_Î := X_Î_1^(1)⊗…⊗ X_Î_N^(1),

where X_I_t^(1) for t∈ [N] is the level-1 partition of T^(1). We call X_Î a level-1 variable block and Î its level-1 index sequence. The level-1 Y- and Z-variable blocks Y_Ĵ and Z_K̂ are defined similarly for level-1 index sequences Ĵ, K̂∈{0,1,2}^N. Then notice that X_Î, Y_Ĵ, Z_K̂ form a nonzero subtensor of (T^(1))^⊗ N if Î_t + Ĵ_t + K̂_t = 2 for all t∈ [N]. Thus we write (T^(1))^⊗ N as a sum of subtensors

    (T^(1))^⊗ N = ∑_Î, Ĵ, K̂∈{0,1,2}^N
    Î_t + Ĵ_t + K̂_t = 2  ∀ t∈ [N] (T^(1))^⊗ N|_X_Î, Y_Ĵ, Z_K̂.

For convenience, we use X_ÎY_ĴZ_K̂ to denote the subtensor (T^(1))^⊗ N|_X_Î, Y_Ĵ, Z_K̂ and we call X_ÎY_ĴZ_K̂ a level-1 triple.



  
Level- partition of (_q)^⊗ N.
In level-, we view (_q)^⊗ N as the tensor (T^())^⊗ n where n = N / 2^ - 1 and consider the partition induced by the level- partition on T^(). Each level-1 X-variable block X_I is indexed by a sequence I∈{0,1,…, 2^}^n of length n. The variable block X_I is defined as 

    X_I :=  X_I_1^()⊗…⊗ X_I_n^()

where X_i^() (0 ≤ i ≤ 2^) is the i-th part in the level- partition of T^(). We call X_I a level- variable block and I its level- index sequence. The level- Y- and Z-variable blocks Y_J and Z_K are defined similarly for level- index sequences J,K∈{0,1,…, 2^}^n. Similarly, the level- variable blocks X_I, Y_J, Z_K form a nonzero subtensor of (T^())^⊗ n when I_t + J_t + K_t = 2^ for all t∈ [n]. So we can write

    (T^())^⊗ n = ∑_Î, Ĵ, K̂∈{0,1,2^}^n
     I_t+J_t +K_t = 2^  ∀ t∈ [N](T^())^⊗ n|_X_I, Y_J, Z_K.

As in the level-1 partition, for convenience, we use the notation X_IY_JZ_K to denote the subtensor (T^())^⊗ n|_X_I, Y_J, Z_K and we call such X_IY_JZ_K a level- triple.

In addition, note that since the level- partition of T^() is a coarsening of the partition induced by the level-1 partition of T^(1), a level-1 variable block X_Î is contained in a level- variable block X_I if the sequence I' = (I'_1,…, I'_n) formed by taking I'_t = ∑_i = 1^2^-1Î_(t-1)· 2^-1 + i satisfies I'_t = I_t for all t∈ [n]. Namely, if taking the sum of consecutive length-2^-1 subsequences in Î yields the sequence I, then X_Î is contained in X_I. In this case, we use the notation Î∈ I and X_Î∈ X_I.



 §.§ Distributions and Entropy

We only consider distributions with a finite support. Let α be a distribution supported on a set S, i.e. we have α(s)≥ 0 for all s∈ S and ∑_s∈ Sα(s) = 1. The entropy of α, denoted as H(α), is defined as
    H(α)  - ∑_s∈ S
    α(s) > 0α(s)logα(s),

where the log has base 2. 
We use the following well-known combinatorial fact.

  Let α be a distribution over the set [s] = {1,…, s}. Let N > 0 be a positive integer, then we have
  
    Nα(1)N,…, α(s)N= 2^N(H(α) ± o(1)).



 For two distributions α and β over the sets S and S' respectively, we define the joint distribution α×β as the distribution over S× S' = {(s,s') | s∈ S, s'∈ S'} such that
 
    (α×β) (s,s') = α(s)·β(s').

  When S and S' are sets of integer sequences, we will instead define α×β as a distribution over all integer sequences that can be obtained by concatenating one sequence in S and one sequence in S', such that 

    (α×β)(s ∘ s') = α(s) ·β(s'),

where s ∘ s' denotes the concatenation of s and s'. 



 §.§ Complete Split Distributions


Motivated by the leveled partition of tensor powers of _q, the complete split distribution is defined to characterize the level-1 variable blocks contained in level- variable blocks. (Complete split distributions were first defined and used by <cit.>.)


    A complete split distribution for a level- constituent tensor T_i,j,k with i+j+k=2^ is a distribution on all length 2^-1 sequences (î_1, î_2, …, î_2^-1) ∈{0, 1, 2}^2^-1. 


For a level-1 index sequence Î∈{0, 1, 2}^2^-1· n, we say that it is consistent with a complete split distribution  if the proportion of any  index sequence (î_1, î_2, …, î_2^-1) in

    {Î_(t-1)· 2^ - 1+p_p=1^2^-1 |  t ∈ [n] }

equals (î_1, î_2, …, î_2^-1). Namely, for every (î_1,…, î_2^-1)∈{0,1,2}^2^-1, we have

    t ∈ [n] Î_(t-1)· 2^ - 1+p_p=1^2^ - 1 = (î_1,…, î_2^-1)  = (î_1, î_2, …, î_2^-1) · n.


Notice that any level-1 index sequence Î∈{0,1,2}^2^ - 1· n defines a complete split distribution by computing the proportion of each type of length-2^-1 consecutive chunks present in Î. More specifically, we have the following definition.


    Given a level-1 index sequence Î∈{0,1,2}^2^ - 1· n, its complete split distribution over (î_1,…, î_2^-1)∈{0,1,2}^2^ - 1 is defined as
    
    Îî_1,…, î_2^-1 = 1/n·t ∈ [n] Î_(t-1)· 2^ - 1+p_p=1^2^ - 1 = î_1,…, î_2^-1.

    Given a subset S⊆ [n], we can define the complete split distribution over (î_1,…, î_2^-1)∈{0,1,2}^2^ - 1 given by Î restricted to the subset S as 
    
    Î, Sî_1,…, î_2^-1 = 1/|S|·t ∈ S Î_(t-1)· 2^ - 1+p_p=1^2^ - 1 = î_1,…, î_2^-1.



Given two complete split distributions _1 and _2 over the length-2^-1 index sequences {0,1,2}^2^ - 1, the L_∞ distance between _1 and _2 is defined to be 

    _1 - _2_∞ = max_σ∈{0,1,2}^2^-1|_1(σ) - _2(σ)|.

For any constant > 0 and a fixed complete split distribution , we say that a level-1 index sequence Î∈{0,1,2}^2^ - 1· n is consistent with  up to  error if  (Î) - _∞≤. When the  is clear from context, we say that Î is approximately consistent with  if it is consistent with  up to  error.


    For a level- constituent tensor T_i,j,k, an integer exponent N, a constant ≥ 0, and three complete split distributions _X, _Y, _Z for the X-, Y-, Z-variables respectively, we define
    
    T_i,j,k^⊗ N[_X, _Y, _Z,] := ∑_level-1  triple  X_ÎY_ĴZ_K̂ T_i,j,k^⊗ N
    Î approximately consistent with _X 
    Ĵ approximately consistent with _Y 
    K̂ approximately consistent with _Z X_Î Y_Ĵ Z_K̂.

    It is a subtensor of T_i,j,k^⊗ N over all level-1 X-, Y-, Z-variable blocks that are approximately consistent with , , , respectively. When = 0, we will simplify the notation to T_i,j,k^⊗ N[_X, _Y, _Z].




 §.§ Salem-Spencer Sets

In the hashing step of the laser method, we make use of the existence of a large dense subset of _M that avoids 3-term arithmetic progressions, as given by Salem and Spencer <cit.> and Behrend <cit.>.



 For every positive integer M > 0, there exists a subset B⊆_M of size 
 
    |B|≥ M· e^-O(√(log M)) = M^1-o(1)

 that contains no nontrivial 3-term arithmetic progressions. Specifically, any a,b,c∈ B satisfy a+b ≡ 2c  M if and only if a = b = c.





§ ALGORITHM OUTLINE





Our high-level framework is similar to previous works <cit.>, and we borrow definitions such as interface tensors, compatibility, and usefulness. 
We begin by defining the notion of interface tensors, which captures the structure of the intermediate tensors we obtain from different stages of our algorithm and pass to the next stages.


  For a positive integer ≥ 1 and any constant 0≤≤ 1, a level- -interface tensor ^* with parameter list 
  
    {(n_t, i_t, j_t, k_t, , , )}_t ∈ [s]

  is defined as
  
    ^* ⊗_t = 1^s T_i_t, j_t, k_t^⊗ n_t[, , , ],

  where i_t+j_t+k_t = 2^ for every t∈ [s] (i.e., T_i_t, j_t, k_t is a level- constituent tensor) and  , , are level- complete split distributions for X-, Y-, Z-variables respectively. We call each T_i_t, j_t, k_t^⊗ n_t[, , , ] a term of ^*. When = 0, we will simply call ^* a level- interface tensor. 


Our algorithm takes _q^⊗ 2^^*-1^⊗ n as input, and applies the global stage of the algorithm described in <ref> to degenerate it into independent copies of a  level-^* _^*-interface tensor. For every ∈ [^*], we will have a parameter _ controlling the error margin of level- interface tensors. Then for = ^*, ^* - 1, …, 2, we apply the constituent stage of the algorithm described in <ref> to degenerate a level- _-interface tensor into a tensor product between independent copies of level-(-1) _-1-interface tensors and a matrix multiplication tensor. Eventually, we obtain a tensor product between independent copies of level-1 _1-interface tensors and a matrix multiplication tensor, which can then be degenerated into independent copies of matrix multiplication tensors. Thus, the overall algorithm degenerates _q^⊗ 2^^*-1^⊗ n into independent copies of matrix multiplication tensors as desired. 









 §.§ Algorithm Outline


The framework for the constituent stage is similar to the framework for the global stage.
For simplicity, we only present the outline of our global stage algorithm for = 0 as it captures the main ideas of our algorithm and illustrates the main differences between our algorithm and <cit.>'s. A high-level comparison between our algorithm and <cit.>'s is provided in <ref>. 



As mentioned earlier, the goal of the global stage is to take _q^⊗ 2^-1^⊗ n as input (for convenience, we will use  to denote ^*), and output a set of level-1-independent level- interface tensors. Since our algorithm treats the X, Y, Z dimensions asymmetrically and there are six permutations of the X, Y, Z dimensions, we can essentially apply our algorithm in six different ways. As a result, we will split _q^⊗ 2^-1^⊗ n into ⊗_r ∈ [6]_q^⊗ 2^-1^⊗ A_r · n for some A_1, …, A_6 ≥ 0  and ∑_r = 1^6 A_r = 1, where we call each _q^⊗ 2^-1^⊗ A_r · n a region. We apply our algorithm for each permutation of the X, Y, Z dimensions on one of the regions. We note that in <cit.>, two of the three dimensions are treated symmetrically, so they only need to split the input tensor into 3 regions instead of 6. For simplicity, we outline each step of our algorithm on a fixed permutation without splitting _q^⊗ 2^-1^⊗ n into regions in the following.





  * Zero out according to α. This is a standard first step present in all previous applications of the laser method. For some distribution α over level- constituent tensors, let , , be the marginal distributions of α on the X-, Y-, Z-dimensions respectively. We zero out X-, Y-, Z-variable blocks that are not consistent with , , respectively. 


  * Asymmetric hashing. Similar to <cit.>, we then apply asymmetric hashing. Unlike previous works, where after the asymmetric hashing each level- X-variable block X_I or Y-variable block Y_J is contained in a unique level- triple X_I Y_J Z_K, we only require each level- X-block to be contained in a unique triple. Moreover, the number of triples containing each level- Y-block is at most the number of triples containing each level- Z-block. 



  * Y-compatibility zero-outs. In <cit.>, the next step is to do some zeroing outs based on a notion of compatibility defined for level-1 Z-blocks, provided that every level-1 X- and Y-block is contained in a unique block triple. So in our algorithm, we first need to ensure that each level-1 Y-block is contained in a unique block triple by performing the following sub-steps. 

Note that our goal is to obtain an interface tensor with  {_X, i, j, k, _Y, i, j, k, _Z, i, j, k}_i+j+k = 2^ as its complete split distributions. Since each level- X-block is contained in a unique block triple, we are already able to identify the subset of indices t with X_t = i, Y_t = j, Z_t = k for every i, j, k. This means that we can compute the complete split distributions for each level-1 X-block with respect to these indices, and zero out any level-1 X-block that is not consistent with {_X, i, j, k}_i+j+k = 2^. 



    
  * Y-compatibility zero-out I. Then we define a notion of compatibility for a level-1 Y-block with respect to a level- block triple containing it. We say a level-1 Y-block is compatible with a level- block triple if they satisfy the compatibility conditions. We zero out all level-1 Y-blocks that are not compatible with any triple. 
    
  * Y-compatibility zero-out II. In this step, we zero out the level-1 Y-blocks that are compatible with more than one triple. After this step, we can ensure that each level-1 Y-block is contained in a unique level- block triple and it is compatible with that triple. 
    
  * Y-usefulness zero-out. At this point, each level-1 Y-block is contained in a unique triple, so we can zero out a level-1 Y-block if it is not consistent with {_Y, i, j, k}_i+j+k = 2^, similar to what we did to the level-1 X-blocks. 




  * Z-compatibility zero-outs. Although after the more asymmetric hashing step, we only have X-blocks in a unique triple, notice that after Y-compatibility zero-outs, we achieve the property that now every level-1 X- and Y-block is compatible with a unique level-ℓ triple. This property is weaker than the property achieved in <cit.> after their original asymmetric hashing steps, but this is sufficient for later steps. In particular, in our Z-compatibility zero-out, we can perform essentially the same procedure as in <cit.> to achieve the property that every level-1 Z-block is compatible with a unique level- triple.


  * Fixing holes. Now every level-1 block is contained in a unique level-ℓ triple, but some of the level-1 blocks we zeroed out in Y-compatibility zero-out and Z-compatibility zero-out become holes, i.e., the copies of the interface tensors we obtain miss some variables due to the compatibility zero-outs. We use the following result to fix these holes.


    Let T be a level-ℓ interface tensor with parameter list
    
    {(n_t, i_t, j_t, k_t, , , )}_t ∈ [s].

    Let N = 2^ℓ-1·∑_t∈ [s] n_t. Suppose T_1, …, T_r are broken copies of T where ≤1/8N fraction of level-1 X-, Y- and Z-blocks are holes. If r ≥ 2^C_1 N / log N for some large enough constant C_1>0, the direct sum ⊕_i = 1^r T_i can degenerate into an unbroken copy of T.










§ GLOBAL STAGE



For our global stage algorithm, the input is the tensor _q^⊗ N where N = n· 2^^*-1. The algorithm will output a set of independent copies of level-^* interface tensors that is degenerated from the input tensor. For convenience, we use  to denote ^* in the rest of this section.

Given a distribution α over the set {(i, j, k) ∈ℤ_≥ 0^3 | i + j + k = 2^} and level- complete split distributions _X, i, j, k, _Y, i, j, k, _Z, i, j, k we define the quantities listed in <ref>.





In particular, our notations follow the general rules below:


    
  * Given a function f(i,j,k), we may replace any of the input by the symbol * or . If an input coordinate is a *, then it means the sum over f evaluated at all the inputs that are ≥ 0 in this input coordinate; if an input coordinate is a , then it means the sum over  f evaluated at all the inputs that are > 0 in this input coordinate. For example, f(*, j,k) = ∑_i≥ 0 f(i,j,k) and f(*,,k) = ∑_i≥ 0, j>0 f(i,j,k).

    We will also use f̅, together with the symbols  * or  to denote a weighted average. Typically, we use this notation on the complete split distributions β, and the average is weighted by α. For instance, _X, *, , k = 1/α(*, , k)∑_i≥ 0, j>0α(i, j, k) ·_X, i, j, k. 
    
    
  * Given a family of sets S_i,j,k, we may replace any of the subscripts by the symbol * or . If any coordinate of the subscript is a *, then it means the union over S_i,j,k with subscript ≥ 0 on this coordinate; if any coordinate of the subscript is a , then it means the union over S_i,j,k with subscript > 0 on this coordinate. For example, S_*,j,k = ⋃_i≥ 0 S_i,j,k and S_*,,k= ∑_i≥ 0, j>0 S_i,j,k.



 In the following proposition, for every r∈ [6], we have the distirbutions α^(r), _X, i, j, k^(r), _Y, i, j, k^(r), _Z, i, j, k^(r) correspondingly and we use the superscript (r) on variables obtained from α^(r), _X, i, j, k^(r), _Y, i, j, k^(r), _Z, i, j, k^(r). 




    _q^⊗ 2^-1^⊗ n can be degenerated into a direct sum of 2^(∑_r=1^6 A_r E_r) n - o(n) copies of a level- interface tensor with parameter list 
    
    { n · A_r ·α^(r)(i, j, k), i, j, k, _X, i, j, k^(r), ^(r)_Y, i, j, k, ^(r)_Z, i, j, k}_r ∈ [6],   i + j + k = 2^

    where
    
        
  * 0 ≤ A_r ≤ 1, ∑_r=1^6 A_r = 1;
        
  * α^(r) for every r ∈ [6] is a  distribution over {(i, j, k) ∈ℤ_≥ 0^3 | i + j + k = 2^};
        
  * For every W ∈{X, Y, Z}, _W, i, j, k^(r) for r ∈ [6], i + j + k = 2^ is a level- complete split distribution;
        
  * For each r ∈ [6], define π_r: {X, Y, Z}→{X, Y, Z} as the r-th permutation in the lexicographic order. Then 
        
    E_r min{H(α_π_r(X)^(r)) - P_α^(r), H(π_r(Y)^(r)) - η_π_r(Y)^(r),  H(π_r(Z)^(r)) - λ_π_r(Z)^(r)}.

    


The following remark illustrates some simple relationships between the complete split distributions for the X-,Y-,Z-dimensions that we can assume without loss of generality, which will be useful in our algorithms. 




Without loss of generality, we can assume that, for every r, i, j, k, and every L ∈{0, 1, 2}^2^-1, 

    ^(r)_X, i, 0, k(L) = ^(r)_Z, i, 0, k(2⃗-L),   ^(r)_Z, 0, j, k(L) = ^(r)_Y, 0, j, k(2⃗-L),   ^(r)_Y, i, j, 0(L) = ^(r)_X, i, j, 0(2⃗-L),

where 2⃗ denotes the length-(2^-1) vector whose coordinates are all 2, 
and 

    ^(r)_X, i, j, k(L) = 0  if ∑_t L_t  i,   ^(r)_Y, i, j, k(L) = 0  if ∑_t L_t  j,   ^(r)_Z, i, j, k(L) = 0  if ∑_t L_t  k,

because otherwise, the level- interface tensor will be the zero tensor and the lemma will follow trivially. 


The following is a corollary of <ref>. We omit its proof as it is similar to the proof of <cit.>. 



For any > 0, 2^o(n) independent copies of (_q^⊗ 2^-1)^⊗ n can be degenerated into 
    
    2^(∑_r=1^6 E_r A_r - o_1/(1)) n - o(n)

    independent copies of a level- -interface tensor with parameter list 
    
    { n · A_r ·α^(r)(i, j, k), i, j, k, _X, i, j, k^(r), ^(r)_Y, i, j, k, ^(r)_Z, i, j, k}_r ∈ [6], i + j + k = 2^

    where the constraints are the same as those in <ref>.[(1) denotes a function f() where f() → 0 as → 0. We also use (n) to denote (1) · n.]


In the remainder of this section, we prove <ref>. 





 §.§ Dividing into Regions



As in previous works <cit.>, we partition the n-th tensor power of _q^⊗ 2^-1 into several “regions”. For each different region, we use a different permutation for the roles of the X-, Y-, Z-dimensions. In <cit.>, they partition (_q^⊗ 2^-1)^⊗ n into three regions due to the fact that two out of the three dimensions are treated symmetrically in their algorithms. Since our method is more asymmetric, we need to partition (_q^⊗ 2^-1)^⊗ n into six regions instead. More specifically, we consider 

    _q^⊗ 2^-1^⊗ n≡⊗_r=1^6 _q^⊗ 2^-1^⊗ A_r· n

for A_1, …, A_6 ≥ 0 and A_1 + ⋯ + A_6 = 1, and we denote the r-th region by ^(r). 

In the following, we will focus on the analysis for ^(1), as the analysis for the other regions follows identically. For simplicity, we will drop the superscript (1). 





 §.§ More Asymmetric Hashing


This hashing step is standard in all previous literature on applications of the laser method, but we repeat the description of the hashing procedure for completeness. 

Let α be a distribution on {(i, j, k) ∈ℤ_≥ 0^3| i + j + k = 2^}, and let , , be the marginal distributions of α on the three dimensions respectively. 

First, in , we zero out the level-ℓ X-blocks that are not consistent with , the level-ℓ Y-blocks that are not consistent with , and the level-ℓ Z-block that are not consistent with . Let , , be the number of remaining X-, Y-, Z-blocks respectively,  be the number of remaining block triples, and  be the number of remaining block triples consistent with α. These values can be approximated in the standard way: 


    = 2^H() · A_1 n ± o(n),    = 2^H() · A_1 n ± o(n),    = 2^H() · A_1 n ± o(n), 
     = 2^H(α) · A_1 n ± o(n),    = 2^(H(α) + P_α) · A_1 n ± o(n).




Let 

    M_0 ≥ 8 ·/

be an integer yet to be fixed, and let M ∈ [M_0, 2M_0] be a prime number (its existence is guaranteed by Bertrand's postulate). For random b_0, {w_t}_t=0^n ∈_M, we define three hash functions h_X, h_Y, h_Z : {0, …, 2^}^n →_M as:

    h_X(I)    = b_0 + (∑_t=1^n w_t · I_t )  M,
    
        h_Y(J)    = b_0 + (w_0 + ∑_t=1^n w_t · J_t )  M,
    
        h_Z(K)    = b_0 + 1/2(w_0+∑_t=1^n w_t · (2^ - K_t) )  M.

Let B be the Salem-Spencer subset of _M of size M^1-o(1) from <ref> that contains no three-term arithmetic progressions. Then we zero out all the level-ℓ X-blocks X_I where h_X(I) ∉B, all the level-ℓ Y-blocks Y_I where h_Y(J) ∉B, and all the level-ℓ Z-blocks X_K where h_Z(K) ∉B. 

Note that by definition of the hash functions, we have  h_X(I) + h_Y(J) = 2 h_Z(K) for any block triple X_I Y_J Z_K (as h_X(I), h_Y(J), h_Z(K) ∈ Z_M, this equation holds modulo M if we view them as integers in ). Therefore, since we only keep blocks whose hash values belong to the Salem-Spencer set B, all remaining block triples X_I Y_J Z_K must have h_X(I) = h_Y(J) = h_Z(K) = b for some b ∈ B. Now for every b ∈ B, if there are two blocks triples X_I Y_J Z_K and X_I Y_J' Z_K' that are both hashed to b and share the same X-block X_I, we zero out X_I. 

We call the tensor after this zeroing out  and note that every level-ℓ X-block is in a unique level-ℓ block triple in . We highlight the fact that this is the start of the main deviation from previous works. In comparison with previous works, in <cit.>, after this step all level-ℓ X-blocks and Y-blocks are in unique blocks triples; in earlier works <cit.>, all level-ℓ blocks are in unique block triples. 


We summarize the properties of this hashing procedure and  in the following lemma.



The above described procedure and its output  satisfy the following:


    
  *  For any level- block triple X_I Y_J Z_K∈ and every bucket b∈_M, we have 
    
    h_X(I) = h_Y(J) = h_Z(K) = b = 1/M^2.

    Furthermore, for any b ∈_M we have that any two different block triples X_I Y_J Z_K,  X_I Y_J' Z_K'∈ that share the same X-block satisfy
    
    h_X(I) = h_Y(J') = h_Z(K') = b  |  h_X(I) = h_Y(J) = h_Z(K) = b = 1/M.

    The same holds for different blocks that share the same Y-block or Z-block.

    
  * 
     For every b ∈ B and every level- block triple X_I Y_J Z_K ∈ consistent with α, we have
    
    X_IY_JZ_K∈ |  h_X(I) = h_Y(J) = h_Z(K) = b≥3/4.


    
  *  
    [] ≥· M_0^-1-o(1).


    







 §.§ Y-Compatibility Zero-Out


Let 

    S^(I, J, K)_i, j, k{t ∈ [n]| I_t = i, J_t = j, K_t = k}

and 

    S^(J)_*, j, *{t ∈ [n] | J_t = j},     S^(K)_*, *, k{t ∈ [n] | K_t = k}.

We will drop the superscripts if the context is clear.[If we follow our general rules for notation described at the beginning of <ref> strictly, S_*,j,*^(J) and S_*,*,k^(K) would be denoted as S_*,j,*^(I, J, K) and S_*,*,k^(I, J, K), but notice that the extra superscripts can be dropped as they do not affect the values of S_*,j,*^(I, J, K) and S_*,*,k^(I, J, K).
]


Recall that in , every level-ℓ X-block is in a unique block triple, so given a level-ℓ block X_I, we can uniquely determine the level-ℓ block triple X_I Y_J Z_K containing it. For any i, j, k, and any level-1 block X_Î∈ X_I, if (Î, S_i, j, k) _X, i, j, k, we zero out X_Î. 

The overall goal of this step is to zero out some level-1 Y-blocks, so that each remaining level-1 Y-block belongs to a unique level-ℓ block triple as well. 



  §.§.§ Y-Compatibility Zero-Out I


Given any level-1 Y-block Y_Ĵ, if there exists a j such that (Ĵ, S_*, j, *) _Y, *,j,*, then we zero out Y_Ĵ. Eventually, the goal is to obtain independent copies of the interface tensor with complete split distributions {_X, i, j, k, _Y, i, j, k, _Z, i, j, k}_i+j+k = 2^. For any Y_Ĵ∈ Y_J, if Y_Ĵ belongs to such an interface tensor, then we must have (Ĵ, S_*, j, *) = _Y, *,j,* for every j. This is because if there exist X_Î∈ X_I and Z_K̂∈ Z_K such that X_Î Y_Ĵ Z_K̂∈ X_I Y_J Z_K, where X_Î Y_Ĵ Z_K̂ is consistent with the complete split distributions and X_I Y_J Z_K is consistent with α, then one can verify that (Ĵ, S_*, j, *) = _Y, *,j,* for every j regardless of what X_Î and Z_K̂ are. So it does not hurt to zero out these Y_Ĵ blocks. We call the tensor obtained after this zero-out . 

Next, we define the notion of compatibility for level-1 Y-blocks, which is similar to the definition of compatibility in <cit.>. 



  
Given a level-ℓ triple X_I Y_J Z_K and a level-1 Y-block Y_Ĵ∈ Y_J, we say that Y_Ĵ is compatible with X_I Y_J Z_K if the followings hold:
  
  
  *  For every (i, j, k) ∈ℤ_≥ 0^3 with i + j + k = 2^ and k = 0,  (Ĵ, S_i,j,k) = _Y,i,j,k.
  
  * 
    For every index j ∈{0, 1, …, 2^},  (Ĵ, S_*,j,*) = _Y, *,j,*.
  



  
  In , for every level-1 block triple X_ÎY_ĴZ_K̂ and the level- block triple X_I Y_J Z_K that contains it, Y_Ĵ is compatible with X_I Y_J Z_K.



    It is easy to see that <ref> is satisfied by our procedure since we will zero out all the level-1 Y_Ĵ block if there exists j∈{0, …, 2^ℓ} such that (Ĵ, S_*, j, *) _Y, *,j,*. So it suffices to show <ref>.

    Note that all the remaining level-1 X-blocks X_Î satisfy (Î, S_i,j,k) = _X,i,j,k for all (i,j,k)∈_≥ 0^3 with i+j+k = 2^ℓ due to the first zero-out in <ref> on level-1 X-blocks. Now consider (i,j,k)∈_≥ 0^3 with k = 0 and i+j+k = 2^ℓ. In a remaining level-1 triple X_ÎY_ĴZ_K̂, we must have (Î, S_i,j,k) = _X, i,j,k. Then since k = 0, we have K_t = 0 for all t∈ S_i,j,k, i.e. (K̂_(t-1)· 2^ℓ-1+1,K̂_(t-1)· 2^ℓ-1+2, …, K̂_t· 2^ℓ-1) = 0⃗. Since we have for each t̂∈{(t-1)· 2^ℓ-1+1,…, t· 2^ℓ-1}, Î_t̂ + Ĵ_t̂ + K̂_t̂ = 2, we have for all t∈ S_i,j,k,
    
    Ĵ_(t-1)· 2^ℓ-1+1,Ĵ_(t-1)· 2^ℓ-1+2, …, Ĵ_t· 2^ℓ-1 = 2⃗ - Î_(t-1)· 2^ℓ-1+1,Î_(t-1)· 2^ℓ-1+2, …, Î_t· 2^ℓ-1.

    So for every length 2^ℓ-1 tuple L∈{0,1,2}^2^ℓ-1 we must have 
    
    (Ĵ,S_i,j,k)(L) = (Î, S_i,j,k)(2⃗-L) = _X,i,j,k(2⃗ - L).

    By <ref>, we have that (Ĵ,S_i,j,k)(L) = _X,i,j,k(2⃗ - L) = _Y,i,j,k(L) as desired.
    




  §.§.§ Y-Compatibility Zero-Out II


After the previous step, it is guaranteed that every remaining level-1 Y-block Y_Ĵ is compatible with all the level- block triples containing it by <ref>. In order to ensure that each remaining Y_Ĵ belongs to a unique triple after further zero-outs, it suffices to guarantee that Y_Ĵ belongs to a unique triple that it is compatible with. Therefore, given any Y_Ĵ that is compatible with more than one triple, we zero it out. 

After this step, each remaining Y_Ĵ belongs to a unique triple, and additionally Y_Ĵ is compatible with this triple. 



  §.§.§ Y-Usefulness Zero-Out


At this point, each remaining level-1 block Y_Ĵ belongs to a unique triple X_I Y_J Z_K. So now we can check whether (Ĵ, S_i, j, k) = _Y, i, j, k for all i, j, k, and zero out Y_Ĵ if there exists some i,j,k such that the equality does not hold. 

For convenience, we define the following notion of usefulness. 


    Given a level- triple X_I Y_J Z_K and a level-1 block Y_Ĵ∈ Y_J, we say Y_Ĵ is useful for X_I Y_J Z_K if (Ĵ, S_i, j, k) = _Y, i, j, k for every i, j, k. 


Using the above definition, this step is equivalent to zeroing out every level-1 block Y_Ĵ that is not useful for the unique triple containing it. We call the remaining tensor after this step . 



 §.§ Z-Compatibility Zero-Out


After Y-compatibility zero out, every level-1 Y-block Y_Ĵ∈ Y_J must be in a unique level- triple X_IY_JZ_K and the same holds for every level-1 X-block X_Î as well. The goal of this step is to zero out some level-1 Z-blocks Z_K̂ so that every level-1 Z-block is also in a unique level-ℓ triple. We note that this step is similar to the compatibility zero-out and usefulness zero-out steps in <cit.> and <ref> are identical to the definition of compatibility and usefulness respectively in <cit.>.



  §.§.§ Z-Compatibility Zero-Out I


Given any level-1 block Z_K̂∈ Z_K, we zero out Z_K̂ if there exists a k such that (K̂, S_*,*,k) _Z, *,*,k. We call the obtained tensor .

Next, we are ready to define compatibility for level-1 Z_K̂ blocks.



  
  Given a level-ℓ triple X_I Y_J Z_K and a level-1 Z-block Z_K̂∈ Z_K, we say that Z_K̂ is compatible with X_I Y_J Z_K if the followings hold:
  
  
  *  For every (i, j, k) ∈ℤ_≥ 0^3 with i + j + k = 2^, i = 0  or  j = 0,  (K̂, S_i,j,k) = _Z,i,j,k.
  
  * 
    For every index k ∈{0, 1, …, 2^},  (K̂, S_*,*,k) = _Z, *,*,k.
  




[<cit.>]

  In , for every level-1 block triple X_ÎY_ĴZ_K̂ and the level- block triple X_I Y_J Z_K that contains it, Z_K̂ is compatible with X_I Y_J Z_K.





  §.§.§ Z-Compatibility Zero-Out II: Unique Triple




Now in , every level-1 Z-block Z_K̂ is compatible with the level- triple X_I Y_J Z_K containing it, but there can be multiple level- triples containing the level-1 block Z_K̂. So in this step, we zero out Z_K̂ if it is compatible with more than one level- triple. Then the remaining tensor satisfies the property that every level-1 Z_K̂ is contained in a unique level- triple, and Z_K̂ is compatible with that triple.



  §.§.§ Z-Usefulness Zero-Out


For convenience, we also define the notion of usefulness for Z-blocks. 



Given a level- triple X_I Y_J Z_K and  a level-1 block Z_K̂∈ Z_K, we say that Z_K̂ is useful for X_I Y_J Z_K if (K̂, S_i,j,k) = _Z,i,j,k for every i, j, k. 


We zero out every level-1 blocks Z_K̂ that is not useful for the unique triple containing it and call the remaining tensor .



 §.§ Fixing Holes



At this stage, the subtensor of the remaining tensor  over X_I Y_J Z_K is a subtensor of the following tensor 

    𝒯^* = ⊗_i+j+k = 2^ T_i,j,k^⊗ A_1 ·α(i, j, k) · n [_X, i, j, k, _Y, i, j, k, _Z, i, j, k],

i.e., it is the level- interface tensor with parameter list 

    { A_1 ·α(i, j, k) · n, i, j, k, _X, i, j, k, _Y, i, j, k, _Z, i, j, k}_i + j + k = 2^.

More precisely:




  
  For any level- block triple X_I Y_J Z_K contained in , the subtensor of  restricted to the level-ℓ blocks X_I, Y_J, Z_K is a subtensor of ^*, where the missing variables in this subtensor are exactly those level-1 blocks Y_Ĵ that are compatible with multiple level- triples in  and level-1 blocks Z_K̂ that are compatible with multiple level- triples in .




We first show that for any level-ℓ block triple X_IY_JZ_K in , |_X_IY_JZ_K is a subtensor of T^*. Note that we already have 

    |_X_IY_JZ_K≡⊗_i+j+k = 2^ℓ T_i,j,k^⊗ A_1·α(i,j,k)· n,

so it suffices to show that all the level-1 triples X_Î Y_Ĵ Z_K̂ remaining in  satisfy the followings for all i,j,k:

    
  * (Î, S_i,j,k) = _X, i,j,k, 
    
  * (Ĵ, S_i,j,k) = _Y, i,j,k, 
    
  * (K̂, S_i,j,k) = _Z, i,j,k. 

Note that <ref> is automatically satisfied due to the step in Y-compatibility zero-out since we zero out any level-1 X_Î∈ X_I with i,j,k such that (Î, S_i,j,k) _X,i,j,k. <ref> is satisfied due to Y-usefulness zero-out and <ref> is satisfied due to Z-usefulness zero-out. Thus, |_X_IY_JZ_K is a subtensor of T^*.

Now we first analyze what the missing Y variables are. Note that for level-1 Y_Ĵ blocks, we have enforced the following conditions:

    
  * In Y-compatibility zero-out I, we enforce that (Ĵ, S_*,j,*) = _Y,*,j,*.
    
  * In Y-compatibility zero-out II, we enforce that each Ĵ is compatible with a unique level-ℓ triple.
    
  * In Y-usefulness zero-out, we enforce that (Ĵ, S_i,j,k) = _i,j,k for every i,j,k.

We claim that condition (3) is strictly stronger than condition (1) because by definition, given (3) we have

    (Ĵ, S_*,j,*) 
           = 1/∑_i,kα(i,j,k)∑_i+j = 2^ℓ - kα(i,j,k)·(Ĵ, S_i,j,k)
       = 1/∑_i,kα(i,j,k)∑_i+j = 2^ℓ - kα(i,j,k)·_Y, i,j,k
       = _Y,*,j,*.

Also, enforcing condition (3) does not create missing Y variables, as it is enforcing the necessary complete split distribution condition in the definition of ^*. Thus, the missing variables are exactly due to enforcing condition (2), i.e. the level-1 Y_Ĵ blocks that are compatible with more than one level-ℓ triples. Similarly, the missing Z variables are exactly those level-1 Z_K̂ blocks that are compatible with more than one level-ℓ triples.






Furthermore, observe that |_X_I Y_J Z_K is level-1-independent for different block triples X_I Y_J Z_K: the X-blocks are level--independent after the zero-out in the asymmetric hashing step; for Y- and Z-blocks, by <ref>, each level-1 block is compatible with all the level- triples containing it, and we zeroed out all level-1 Y- and Z-blocks that are compatible with multiple level- triples, so the remaining level-1 Y- and Z-blocks belong to unique level- triples. As a result, 

    = ⊕_X_I Y_J Z_K  |_X_I Y_J Z_K

is a direct sum of broken copies of ^*.


To fix the holes, we need to first bound the fraction of holes in the broken copies of ^* contained in . Similar to the analysis in <cit.>, we introduce the notion of typicalness for level-1 Y-blocks and Z-blocks and define the values  and  respectively. Previously, the notion of typicalness and  were only defined with respect to level-1 Z_K̂ blocks. This is because previously only level-1 Z_K̂ blocks could become holes in the remaining tensor. However, in our case both level-1 Y_Ĵ blocks and Z_K̂ blocks can become holes, so we need to define similar notions for Y_Ĵ blocks accordingly. 





  A level-1 Y-block Y_Ĵ in a level- Y-block Y_J is typical if (Ĵ, S_*,j,*) = _Y,*,j,* for every j. When Y_J is consistent with , this condition is equivalent to (Ĵ, [A_1 n]) = Y.




  A level-1 Z-block Z_K̂ in a level- Z-block Z_K is typical if (K̂, S_*,*,k) = _Z,*,*,k for every k. When Z_K is consistent with , this condition is equivalent to (K̂, [A_1 n]) = Z.


Then we can define the values  and  as the probability of a typical level-1 Y_Ĵ-block (resp. Z_K̂-block) being compatible with a random level-ℓ triple X_IY_JZ_K where Ĵ∈ J (resp. K̂∈ K).



For a fixed Y_J and a fixed typical Y_Ĵ∈ Y_J,  is the probability of Y_Ĵ being compatible with a uniformly random block triple X_I Y_J Z_K consistent with α.



For a fixed Z_K and a fixed typical Z_K̂∈ Z_K,  is the probability of Z_K̂ being compatible with a uniformly random block triple X_I Y_J Z_K consistent with α.


For any two different typical level-1 blocks Y_Ĵ∈ Y_J and Y_Ĵ '∈ Y_J', their level-1 complete split distributions are the same. It is not difficult to see that  defined using Y_Ĵ is the same as  defined using Y_Ĵ'. This implies that the definition of  is not dependent on the choice of the level-1 block Y_Ĵ, so it is well-defined. The same holds for  due to the same reasoning.



The value of  is 

    2^(η_Y - H(_Y, *, *, *) + H(α_Y)) · A_1 n ± o(n) ,

where we recall 

    η_Y = ∑_i,j,k: k =0α(i,j,k)· H(_Y, i,j,k) + ∑_jα(*,j,)· H(_Y,*,j,).




We define the following two quantities:


    
  (P) The number of tuples (I, J, K, Ĵ) where X_I Y_J Z_K is consistent with α, Y_Ĵ∈ Y_J and Y_Ĵ is typical. 
    
    
    
  (Q) The number of tuples (I, J, K, Ĵ) where X_I Y_J Z_K is consistent with α, Y_Ĵ∈ Y_J and Y_Ĵ is typical, and additionally Y_Ĵ is compatible with the triple X_I Y_J Z_K. 


Notice that by definition and by symmetry of different choices of Y_Ĵ and Y_J, = Q/P. 

The quantity P is simple to calculate, as it is the number of block triples X_I Y_J Z_K consistent with α (this quantity is 2^H(α) · A_1 n ± o(n)) times the number of typical Y_Ĵ contained in every Y_J. The total number of typical Y_Ĵ that is contained in some Y_J consistent with α_Y is 2^H(_Y, *,*,*) · A_1 n ± o(n). These Y_Ĵ are evenly distributed among all Y_J consistent with α_Y, so each Y_J contains 2^(H(_Y, *,*,*) - H(α_Y)) · A_1 n ± o(n) typical Y_Ĵ. Overall, 

    P = 2^(H(α) + H(_Y, *,*,*) - H(α_Y)) · A_1 n ± o(n).



Next, we consider how to compute Q. Similar to the alternative definition of compatibility in the proof of Claim 5.14 in <cit.>, we have the following claim:

    Given a level-ℓ triple X_IY_JZ_k that is consistent with α, a level-1 block Y_Ĵ with Ĵ∈ J is compatible with X_IY_JZ_K if and only if the following holds:

    
        
  * For every (i,j,k)∈_≥ 0^3 satisfying i+j+k = 2^ℓ and k = 0, (Ĵ, S_i,j,k) = _Y,i,j,k.

        
  * For j∈{0,…, 2^ℓ}, (Ĵ, S_*,j,+) = _Y,*,j,+ where S_*,j,+ = ⋃_i ≥ 0, k>0S_i,j,k.
    

We omit the proof, since it is similar to the proof of the equivalence between two definitions of compatibility in the proof of Claim 5.14 in <cit.>.

Fix some X_I Y_J Z_K that is consistent with α, {S_i, j, 0}_i, j∪{S_*, j, }_j is a partition of [A_1 n], and we can consider the possibilities of Ĵ on each of these parts. For S_i, j, 0, the number of possibilities of Ĵ is 2^H(_Y, i, j, 0) ·α(i, j, 0) · A_1 n ± o(n), as we must have (Ĵ, S_i,j,0) = _Y,i,j,0. For S_*, j, +, the number of possibilities of Ĵ is 2^H(_Y, *, j, +) ·α(*, j, ) · A_1 n ± o(n), as we must have (Ĵ, S_*,j,+) = _Y,*,j,+. Clearly, by combining each set of possibilities from each part, the resulting Ĵ is typical. The total number of possible Ĵ for a fixed triple X_I Y_J Z_K is thus

    2^(∑_i, j, k: k = 0 H(_Y, i, j, 0) ·α(i, j, 0) + ∑_j H(_Y, *, j, ) ·α(*, j, ) ) A_1 n ± o(n) = 2^η_Y A_1 n ± o(n).

Therefore, 

    Q = 2^(H(α) + η_Y) A_1 n± o(n).

Finally, 

    = Q / P = 2^(η_Y - H(_Y, *, *, *) + H(α_Y)) · A_1 n ± o(n) .



    


[<cit.>]
  The value of  is
  
    2^(λ_Z - H(Z) + H()) A_1 · n ± o(n),

  where we recall that 
  
    λ_Z = ∑_i, j, k: i = 0  j = 0α(i, j, k) · H(_Z, i, j, k) + ∑_k α(, , k) · H(_Z, , , k).



[Essentially <cit.>]
  
  For every b ∈ B, every level- block triple X_I Y_J Z_K consistent with α, and every typical Z_K̂∈ Z_K, the probability that Z_K̂ is compatible with multiple triples in  is at most
  
    ·/· M_0,

  conditioned on h_X(I) = h_Y(J) = h_Z(K) = b.

  Similarly,  for every b ∈ B, every level- block triple X_I Y_J Z_K consistent with α, and every typical Y_Ĵ∈ Y_J, the probability that Y_Ĵ is compatible with multiple triples in  is at most
  
    ·/· M_0,

  conditioned on h_X(I) = h_Y(J) = h_Z(K) = b.




Initially, in <ref> we required M_0 ≥ 8·/. Now we finalize all constraints on M_0, and set 

    M_0     = max{8·/,  
    ·/· 80 N, 
    ·/· 80 N}
        = 2^max{H(α)+P_α - H(α_X), η_Y - H(_Y, *, *, *) + H(α), λ_Z - H(_Z, *, *, *) + H(α) }· A_1 n ± o(n).

For every b ∈ B and every level- block triple X_I Y_J Z_K consistent with α that is hashed to bucket b in asymmetric hashing, we consider the probability that it remains in  and |_X_I Y_J Z_K is a copy of ^* with a small number of holes. 

First, by <ref> in <ref>, the level- block X_I Y_J Z_K remains with probability at least 3/4. By <ref>, the expected fractions of holes for level-1 Z-blocks is at most ·/· M_0≤1/80 N. By Markov's inequality, this fraction exceeds 1/8N with probability ≤ 1/10. The same applies to the fraction of holes of Y-variables. Therefore, by union bound, with constant probability, the level- block X_I Y_J Z_K remains and |_X_I Y_J Z_K is a broken copy of ^* whose fraction of holes is ≤1/8N in all three dimensions. The expected number of such X_I Y_J Z_K is · M^-1 - o(1), so in expectation, we obtain · M^-1 - o(1) independent broken copies of ^* with ≤1/8N fraction of holes, and by <ref>, we can degenerate them into · M^-1 - o(1) unbroken copies of ^*. 



 §.§ Summary

In conclusion, the above algorithm degenerates 
_q^⊗ 2^ - 1^⊗ A_1 · n into 

    · M_0^-1-o(1)≥ 2^A_1 n ·minH(^(1)) - P_α^(1),   H(Y^(1)) - η_Y^(1),    H(Z^(1)) - λ_Z^(1) - o(n)

independent copies of a level- interface tensor ^* with parameter list

    { n · A_1 ·α^(1)(i, j, k), i, j, k, ^(1)_X, i, j, k, ^(1)_Y, i, j, k, ^(1)_Z, i, j, k}_i + j + k = 2^.



In region r∈ [6], let π_r: {X,Y,Z}→{X,Y,Z} be the r-th permutation in the lexicographic order and we perform the same procedure with π_r(X)-blocks in place of  X-blocks, π_r(Y)-blocks in place of  Y-blocks and π_r(Z)-blocks in place of Z-blocks. Note that we have described the procedure in the first region which corresponds to the identity permutation. In the end, we take the tensor product over the output tensor of the algorithm over all 6 regions.






§ CONSTITUENT STAGE






The framework for our constituent stage algorithm is almost identical to the framework for our global stage algorithm, but for the sake of rigor and notations we present these two stages separately. 


In the level- constituent stage, the algorithm takes as input a collection of level- -interface tensors, and degenerates them into the tensor product between a matrix multiplication tensor (obtained from the parts of the interface tensor where i_t = 0, j_t = 0 or k_t = 0) and a collection of independent copies of level-(-1) '-interface tensors for some ' > 0 (obtained from the other parts). 

More specifically, given an -interface tensor with parameters

    {(n_t, i_t, j_t, k_t, , , )}_t ∈ [s],

we use the notation n := ∑_t n_t and N := 2^-1· n. 



We can assume without loss of generality that the parameters additionally satisfy the following:

    
  * For every t ∈ [s] with j_t = 0, and every L ∈{0, 1, 2}^2^-1, 
    
    (L) = (2⃗ - L).

  The same holds between  and  when k_t = 0, and between  and  when i_t = 0.
  
  * For every t ∈ [s] and every L ∈{0, 1, 2}^2^-1, (L) = 0 if ∑_q L_q  i_t. The same holds for , with respect to j_t, k_t correspondingly. 





To obtain matrix multiplication tensors from the parts of the interface tensors where i_t = 0 or j_t = 0 or k_t = 0, we invoke the following theorem. 


  
  If k_t=0, then
  
    T_i_t,j_t,k_t^⊗ n_t[, , , ] ≡1, M, 1,

  where
  
    M = 2^n_t (H() ± o_1/(1)) ± o(n)· q^n_t∑_(î_1, î_2, …, î_2^-1)(î_1, î_2, …, î_2^-1) ∑_p=1^2^-1 [î_p = 1].

  Similar results hold for the case when i_t = 0 or j_t = 0.



We use <ref> to degenerate the terms t ∈ [s] where i_t = 0 or j_t = 0 or k_t = 0 into matrix multiplication tensors, and we can take their product to obtain a single matrix multiplication tensor. So now we are left with the remaining terms t∈ [s] where i_t 0, j_t 0, k_t 0. Without loss of generality, we can reorder the terms so that the remaining terms are the first s' ≤ s terms. 

For every t ∈ [s'], we have a triple of level- complete split distributions (, , ) associated with the n_t-th tensor power of the constituent tensor T_i_t,j_t,k_t. We define a distribution  on {0, …, 2^-1}^2 as follows: for l_X, r_X∈{0, …, 2^-1},

    (l_X, r_X) ∑_(î_1, î_2, …, î_2^ - 1):
    î_1 + ⋯ + î_2^ - 2 = l_X, 
    î_2^-2+1 + ⋯ + î_2^ - 1 = r_X(î_1, î_2, …, î_2^-1).

The distribution  specifies how a level- index sequence i_t splits into two level-( - 1) index sequences. We define  and  similarly.

Let α_t be a distribution on possible combinations of (l_X, l_Y, l_Z)∈{0, …, 2^-1}^3 such that the marginals of α_t are consistent with (l_X, i-l_X), (l_Y, j-l_Y), (l_Z, k-l_Z). Moreover, let [t, i', j', k'], [t, i', j', k'], [t, i', j', k'] be level-(-1) complete split distributions. Given t∈ [s'], we define the following quantities in <ref>.



Our notations satisfy the following general rules:



    
  * Given t∈ [s'], when we refer to values in the the distribution α_t(i',j',k'), we may replace any of the input by the symbol  or . If an input coordinate is a , then it means the sum over α evaluated at all the inputs that are > 0 in this input coordinate; if an input coordinate is a , then it means the sum over α evaluated at all the inputs that are < the t-th coordinate of the corresponding index sequence i,j,k in this input coordinate. See examples in <ref>.
    
    
  * Given t∈ [s'], when we refer to values in the complete split distribution _X,t,i',j',k', we may replace any of the input by the symbol  or *. If an input coordinate is a , then it means the sum over _X,t evaluated at all the inputs that are > 0 in this input coordinate; if an input coordinate is a *, then it means the sum over _X,t evaluated at all the inputs in this input coordinate. Similar as before, we use _X,t, i',j',k' with i',j',k' replaced by either * or  to denote the weighted average of the corresponding values with respect to the distribution α_t. See examples in <ref>.
    
    
    
  * For some t ∈ [s'], when given a family of sets S_t, i,j,k, we may replace any of the subscripts i, j, k by the symbol * or . If any coordinate of the subscript is a *, then it means the union over S_t, i,j,k with subscript ≥ 0 on this coordinate; if any coordinate of the subscript is a , then it means the union over S_t, i,j,k with subscript > 0 on this coordinate. As an example S_t, *,j,k = ⋃_i≥ 0 S_t, i,j,k, S_t, *,,k= ∑_i≥ 0, j>0 S_t, i,j,k.





In the following proposition, we will use the above definitions for different t ∈ [s'] and r ∈ [6]. We will use t in the subscripts and (r) in the superscripts on variables to specify that they are computed from values of α_t^(r), _X, t^(r), _Y, t^(r), _Z, t^(r), {[t, i', j', k']^(r)}_i',j',k', {[t, i', j', k']^(r)}_i',j',k', {[t, i', j', k']^(r)}_i',j',k'. 


  
  For > 0, an s'-term level- -interface tensor with parameters
  
    {(n_t, i_t, j_t, k_t, , , )}_t ∈ [s']

  for i_t, j_t, k_t > 0  ∀  t ∈ [s'] can be degenerated into
  
    2^(∑_r=1^6 E_r) - o(n) - (n)

  independent copies of a level-(-1) interface tensor with parameter list
  
    { n_t · A_t,r·α_t^(r)(i', j', k')+α_t^(r)(i_t-i', j_t-j', k_t-k'), i', j', k', [t, i', j', k']^(r), [t, i', j', k']^(r), [t, i', j', k']^(r)}

  with t ∈ [s'], r ∈ [6], i' + j' + k' = 2^-1, 0 ≤ i' ≤ i_t, 0 ≤ j' ≤ j_t, 0 ≤ k' ≤ k_t such that
  
  
  * 0 ≤ A_t,r≤ 1 for every t ∈ [s'], r ∈ [6] and ∑_r=1^6 A_t, r=1 for every t ∈ [s'];
  
  * For every t, and for every W ∈{X, Y, Z}, ∑_r=1^6 A_t,r_W, t^(r) = _W, t (the _W, t^(r)'s are intermediate variables that will be used later); 
  
  * For every W ∈{X, Y, Z},  r ∈ [6] and i' + j' + k' = 2^ - 1, _W, t, i', j', k'^(r) is a level-(-1) complete split distribution;
  
  * For every W ∈{X, Y, Z}, t ∈ [s'] and r ∈ [6],
    
    _W, t^(r) = ∑_i', j', k'α_t^(r)(i', j', k') ·(_W, t, i', j', k'^(r)×_W, t,  i_t - i', j_t - j', k_t - k'^(r));

  
  * For each r ∈ [6], define π_r: {X, Y, Z}→{X, Y, Z} as the r-th permutation in the lexicographic order. Then
  
    E_r min{   ∑_t ∈ [s'] A_t,r· n_t ·( H(γ_π_r(X), t^(r)) - P_α, t^(r)), 
       ∑_t ∈ [s'] A_t,r· n_t ·( H(_π_r(Y), t^(r)) - η_π_r(Y), t^(r)), 
       ∑_t ∈ [s'] A_t,r· n_t ·(H(_π_r(Z), t^(r)) - λ_π_r(Z), t^(r)) }.

  




  
  For > 0, we can degenerate 2^o(n) independent copies of s'-term level- 3-interface tensor with parameters
  
    {(n_t, i_t, j_t, k_t, , , )}_t ∈ [s']

  where i_t, j_t, k_t > 0 ∀ t ∈ [s'] into
  
    2^(∑_r=1^6 E_r) - o(n) - (n)

  independent copies of a level-(-1) -interface tensor with parameter list
  
    { n_t · A_t,r·α_t^(r)(i', j', k')+α_t^(r)(i_t-i', j_t-j', k_t-k'), i', j', k', [t, i', j', k']^(r), [t, i', j', k']^(r), [t, i', j', k']^(r)}

  for t ∈ [s'], r ∈ [6], i' + j' + k' = 2^-1, 0 ≤ i' ≤ i_t, 0 ≤ j' ≤ j_t, 0 ≤ k' ≤ k_t satisfying the same properties as in <ref>.


The proof of <ref> assuming <ref> is the same as the proof of <cit.>, so we omit the proof here. We prove <ref> in the remainder of this section. 



 §.§ Dividing into Regions


For every t ∈ [s'], we divide the t-th term to 6 regions. More specifically, we pick A_t, r≥ 0 for r ∈ [6] such that ∑_r A_t, r = 1, where A_t,r denotes the proportion of the r-th region inside the t-th term. For each region r, we pick complete split distributions ^(r), ^(r), ^(r) for the X-, Y-, Z-dimensions respectively, so that  

    ∑_r=1^6 ^(r) A_t,r= ,   ∑_r=1^6 ^(r) A_t,r= , 
      ∑_r=1^6 ^(r) A_t,r= .

These complete split distributions also need to satisfy conditions in <ref>. 


Then we only keep level-1 blocks that are consistent with these complete split distributions. More specifically, we keep a level-1 X-block only if for all t ∈ [s'], r ∈ [6], its corresponding portion in the r-th region of the t-th part is -approximate consistent with ^(r). We similarly zero out level-1 Y- and Z-blocks. 

The following claim shows the structure of the remaining tensor. We omit its proof as it is simple and similar to <cit.>. 


  
  After the above zeroing-out, we obtain a tensor that is isomorphic to
  
    ⊗_r=1^6 ⊗_t = 1^s' T_i_t, j_t, k_t^⊗ A_t,r n_t[^(r), ^(r), ^(r), ].




In the remainder of this section, we will focus on the first region of the tensor, which we denote as 

    ^(1)⊗_t = 1^s' T_i_t, j_t, k_t^⊗ A_t,1 n_t[^(1), ^(1), ^(1), ].

We will omit the superscript (1) from now on. 



 §.§ More Asymmetric Hashing


Next, we apply more asymmetric hashing. Recall that for each t∈ [s'], α_t is a distribution over the set {(i', j', k') ∈ℤ_≥ 0^3: i' + j' + k' = 2^-1} with marginal distributions on the X,Y,Z-dimensions equal to (i', i_t - i'), (j', j_t - j'), (k', k_t - k') respectively. We zero out X-, Y-, Z-blocks that are not consistent with the distributions {γ_X, t}_t, {γ_Y, t}_t, {γ_Z, t}_t. That is, if there exists some t ∈ [s'] where the t-th part of the level-( - 1) index sequence of some X-block is not consistent with γ_X, t, we zero out this X-block. We zero out Y- and Z-blocks similarly with respect to γ_Y,t and γ_Z,t. 

We define the following quantities:

    
  * , ,: the number of remaining level-(-1) X-, Y-, Z-blocks respectively.

    
  * : the number of remaining block triples  consistent with {α_t}_t ∈ [s'].

    
  * : the number of remaining level-(-1) block triples.


These quantities can be approximated as in the following claim:



    = 2^∑_t H() · A_t,1 n_t ± o(n),    = 2^∑_t H() · A_t,1 n_t ± o(n),    = 2^∑_t H() · A_t,1 n_t ± o(n).


    = 2^∑_t H(α_t) · A_t,1 n_t ± o(n),    = 2^∑_t (H(α_t) + P_α, t) · A_t,1 n_t ± o(n)



Now we apply the standard hashing procedure first used in <cit.>. Let M ∈ [M_0, 2M_0] be a prime number for some integer M_0  satisfying

    M_0 ≥ 8·/.


We pick independent elements b_0, {w_p}_p=0^2n∈_M uniformly at random, and use the hash functions h_X, h_Y, h_Z : {0, …, 2^-1}^n →_M defined as:

    h_X(I)    = b_0 + (∑_p=1^2n w_p · I_p )  M,
    
        h_Y(J)    = b_0 + (w_0 + ∑_p=1^2n w_p · J_p )  M,
    
        h_Z(K)    = b_0 + 1/2(w_0+∑_p=1^2n w_p · (2^-1 - K_p) )  M.


Then let B⊆_M be the Salem-Spencer set without any 3-term arithmetic progressions from <ref>, where |B| = M^1-o(1). We zero out all the level-(-1) blocks X_I with h_X(I) ∉ B, Y_J with h_Y(J) ∉ B, and Z_K with h_Z(K) ∉ B. Similar as before, now all the remaining block triples X_I Y_J Z_K must have h_X(I) = h_Y(J) = h_Z(K) = b for some b ∈ B. 

If there are two remaining level-(-1) triples X_I Y_J Z_K and X_I Y_J'Z_K' sharing the same X-block that are hashed to the same hash value b ∈ B, we zero out X_I. Then for every level-(-1) block X_I, we check whether the unique triple containing it is consistent with {α_t}_t ∈ [s']; if not, we zero out X_I. So every level-(ℓ-1) X-block is contained in a unique level-(-1) triple X_I Y_J Z_K that is consistent with {α_t}_t ∈ [s']. We call the tensor after this step .

The procedure we described above satisfies the following properties.



The above described procedure and its output  satisfy the following:


    
  * 
     For any level-(-1) block triple X_I Y_J Z_K∈ and every bucket b∈{0,…, M-1}, we have 
    
    h_X(I) = h_Y(J) = h_Z(K) = b = 1/M^2.

    Furthermore, for any b ∈{0, …, M - 1} we have that any two different block triples X_I Y_J Z_K,  X_I Y_J' Z_K'∈ that share the same X-block satisfy
    
    h_X(I) = h_Y(J') = h_Z(K') = b  |  h_X(I) = h_Y(J) = h_Z(K) = b = 1/M.

    The same holds for different blocks that share the same Y-block or Z-block.

    
  * 
     For every b ∈ B and every level-(-1) block triple X_I Y_J Z_K ∈ consistent with α, we have
    
    X_IY_JZ_K∈ |  h_X(I) = h_Y(J) = h_Z(K) = b≥3/4.


    
  * 
     
    [] ≥· M_0^-1-o(1).


    







 §.§ Y-Compatibility Zero-Out

Let

    S^(I, J, K)_t, i', j', k'{p | I_p = i', J_p = j', K_p = k'},

and

    S^(J)_t, *, j', * := {p | J_p = j'},    S^(K)_t, *, *, k' := {p | K_p = k'}.

If clear from the context, we will drop the superscript (I, J, K) or (K).[If we follow our general rules for notation described at the beginning of <ref> strictly, S_t,*,j',*^(J) and S_t,*,*,k'^(K) would be denoted as S_t,*,j',*^(I, J, K) and S_t,*,*,k'^(I, J, K), but notice that the extra superscripts can be dropped as they do not affect the values of S_t,*,j',*^(I, J, K) and S_t,*,*,k'^(I, J, K).
]


Recall that in , every X-block X_I is in a unique block triple. Thus, given X_I, we can uniquely determine a block triple X_I Y_J Z_K containing it. 
So we can zero out a level-1 block X_Î∈ X_I if there exist t, i', j', k' such that (Î, S_t, i',j',k') _X, t, i', j', k'.

The goal of the Y-compatibility zero-out step is to ensure each level-1 Y-block belongs to a unique block triple. 



  §.§.§ Y-Compatibility Zero-Out I


For every level-1 Y-block Y_Ĵ, if there is some j' where (Ĵ, S_t, *, j', *) _Y, t, *,j',*, then we zero out Y_Ĵ. We call the tensor after this zeroing out . 

Next, we define the notion of compatibility for level-1 Y-blocks.



  
  Given a level-(-1) block triple X_IY_J Z_K and a level-1 block Y_Ĵ∈ Y_J, we say Y_Ĵ is compatible with X_IY_J Z_K if
  
  
  *  
    
    For every t ∈ [s'] and every (i', j', k') ∈^3_≥ 0∩ ([0, i_t] × [0, j_t] × [0, k_t]) with i' + j' + k'=2^ - 1 and k' = 0, (Ĵ, S_t, i',j',k') = _Y,t, i',j',k'.
  
  * 
    For every t ∈ [s'] and j ∈{0, 1, …, min{2^-1, j_t}},  (Ĵ, S_t, *,j,*) = _Y,t,  *,j,*.
  



  
  In , for every level-1 block triple X_ÎY_ĴZ_K̂ and the level- block triple X_I Y_J Z_K that contains it, Y_Ĵ is compatible with X_I Y_J Z_K.


The proof is similar to the proof of <ref>. 



  §.§.§ Y-Compatibility Zero-Out II


After the previous step, every remaining level-1 Y-block Y_Ĵ is compatible with all the level-(-1) block triples containing it. In this step, if Y_Ĵ is compatible with more than one level-(-1) block triple, we zero it out. At this point, every level-1 Y-block is compatible with a unique level-(-1) block triple. 




  §.§.§ Y-Usefulness Zero-Out




After the previous step, each remaining level-1 block Y_Ĵ will belong to a unique block triple X_I Y_J Z_K, so given Y_Ĵ, S_t, i', j', k' is well-defined for every t, i', j', k'. Hence, we can zero out Y_Ĵ such that there exist some t, i', j', k' where (Ĵ, S_t, i', j', k') _Y, t, i', j', k'.

Similar as before, we define the following notion of usefulness. 


For a level-(-1) block triple X_I Y_J Z_K and a level-1 block Y_Ĵ∈ Y_J, we say Y_Ĵ is useful for X_I Y_J Z_K if (Ĵ, S_t, i', j', k') = _Y, t, i', j', k' for every t, i', j', k'. 


Using the above definition, the zero-out in this step can be equivalently described as follows: We zero out all level-1 block Y_Ĵ that is not useful for the unique triple containing it. 

After this step, we call the tensor . 



 §.§ Z-Compatibility Zero-Out



Similar as before, now we perform compatibility zero-outs for Z-blocks. 



  §.§.§ Z-Compatibility Zero-Out I




 For every level-1 block Z_K̂∈ Z_K, we zero out Z_K̂ if there exist t, k' where (K̂, S_t, *,*,k') _Z, t, *,*,k'.
We call the remaining tensor .

Now we are ready to define the notion of compatibility for level-1 Z-blocks which remains identical to the definition in <cit.>. 



  

  For a level-(-1) block triple X_IY_J Z_K and a level-1 block Z_K̂∈ Z_K, we say Z_K̂ is compatible with X_IY_J Z_K if
  
  
  *  For every t and every (i', j', k') ∈ℤ_≥ 0^3 ∩ [0, i_t] × [0, j_t] × [0, k_t] with i' + j' + k' = 2^-1, i' = 0  or  j' = 0, there is (K̂, S_t, i',j',k') = _Z,t, i',j',k'.
  
  * 
    For every t and every index k' ∈{0, 1, …, min{2^-1, k_t}},  (K̂, S_t, *,*,k') = _Z,t,  *,*,k'.
  



  
  In , for every remaining level-1 block triple X_ÎY_ĴZ_K̂ and the level-(-1) block triple X_I Y_J Z_K that contains it, Z_K̂ is compatible with X_I Y_J Z_K.



The proof of this claim is the same as the proof of Claim 6.10 in <cit.>. 



  §.§.§ Z-Compatibility Zero-Out II: Unique Triple


In this step, we zero out every level-1 Z-block Z_K̂ that is compatible with more than one level-(-1) block triples and they become holes. After this step, each remaining level-1 Z-block Z_K̂∈ Z_K is compatible with a unique level-(-1) triple X_I Y_J Z_K containing it.



  §.§.§ Z-Usefulness Zero-Out


Next, we further zero out some level-1 Z-blocks using the following definition of usefulness.


For a level-(-1) block triple X_I Y_J Z_K and a level-1 block Z_K̂∈ Z_K, we say Z_K̂ is useful for X_I Y_J Z_K if for every t, i', j', k', we have (K̂, S_t, i',j',k') = _Z,t, i',j',k'.


For each Z_K̂, it appears in a unique triple X_I Y_J Z_K by the previous zero-out. If Z_K̂ is not useful for this triple, we zero out Z_K̂. We call the current tensor .



 §.§ Fixing Holes


Eventually, we want to ensure that the subtensor of  restricted to each level-(-1) block triple X_I Y_J Z_K is isomorphic to 

    𝒯^* = ⊗_t ∈ [s'] ⊗_i'+j'+k' = 2^-1 T_i',j',k'^⊗ A_t,1· (α_t(i', j', k')+α_t(i_t-i', j_t-j', k_t-k')) · n_t [_X, t, i', j', k', _Y, t, i', j', k', _Z, t, i', j', k'].



Similar as before, there are some holes caused by our degeneration process. The three types of holes are the followings: 

    
  * The input of the constituent stage does not include all level-1 blocks, as we enforce some -approximate complete split distribution on the input. As analyzed in the previous work <cit.>, the fraction of this type of holes can be upper bounded by 1/n^2 in all three dimensions. The high level intuition is that, if we take a random level-1 block from 𝒯^*, it will likely be -approximate consistent with the complete split distribution in the input. Thus, most level-1 block from 𝒯^* should appear in the input, which imply the fraction of this type of holes is small.
    
  * The holes on Y-blocks caused by Y-compatibility zero-outs. These holes were not considered before, so the main focus of the analysis will be this case. 
    
  * The holes on Z-blocks caused by Z-compatibility zero-outs. The analysis of these holes are similar as the previous work <cit.>, so we will omit most proofs of this case in the following. 





Next, we focus on holes on level-1 blocks caused by compatibility zero-outs. These are the fractions of (typical) Y_Ĵ and  Z_K̂ that are compatible with multiple level-(-1) triples. Similar as before, we define typicalness,  and . 


  A level-1 Y-block Y_Ĵ in some level- Y-block Y_J is typical if |(Ĵ, S_t, *,*,*) - _Y,t, *,*,*|_∞≤ for every t ∈ [s']. 




  A level-1 Z-block Z_K̂ in some level- Z-block Z_K is typical if |(K̂, S_t, *,*,*) - _Z,t, *,*,*|_∞≤ for every t ∈ [s']. 



  For fixed Y_Ĵ and Y_J where Y_Ĵ∈ Y_J and Ĵ has level- complete split distributions _t ∈ [s'], we define ^*(_t ∈ [s']) as the probability that a uniformly random level-(-1) block triple X_I Y_J Z_K consistent with {α_t}_t ∈ [s'] is compatible with Y_Ĵ. We further define 
  
    max__t ∈ [s'] : 
     - _∞≤ ∀ t^*(_t ∈ [s']).

  



  For fixed Z_K̂ and Z_K where Z_K̂∈ Z_K and K̂ has level- complete split distributions _t ∈ [s'], we define ^*(_t ∈ [s']) as the probability that a uniformly random level-(-1) block triple block triple X_I Y_J Z_K consistent with {α_t}_t ∈ [s'] is compatible with Z_K̂. We further define 
  
    max__t ∈ [s'] : 
     - _∞≤ ∀ t^*(_t ∈ [s']).



Similar as before,  does not depend on the choice of Y_Ĵ and Y_J by symmetry, so it is well-defined. It is also the case for  .

Next, we upper bound the value of . 


  The value of ^*(_t ∈ [s']) is at most
  
    2^∑_t ∈ [s']( η_Y,t - H() + H(γ_Y, t) ) A_t,1· n_t ± o(n).

  Furthermore,
  
    ≤  2^∑_t ∈ [s']( η_Y,t - H() + H(γ_Y, t) + (1) ) A_t,1· n_t + o(n).










We define the following two quantities:


    
  (P) The number of tuples (I, J, K, Ĵ) where X_I Y_J Z_K is consistent with {α_t}_t ∈ [s'], Y_Ĵ∈ Y_J and Ŷ has complete split distributions _t.
    
    
    
  (Q) The number of tuples (I, J, K, Ĵ) where X_I Y_J Z_K is consistent with {α_t}_t ∈ [s'], Y_Ĵ∈ Y_J, Ŷ has complete split distributions _t, and additionally Y_Ĵ is compatible with the triple X_I Y_J Z_K. 


Notice that by definition and by symmetry (_t ∈ [s']) = Q/P. 


We first compute the simpler quantity P, which is the number of level-(-1) block triples X_I Y_J Z_K consistent with {α_t}_t ∈ [s'] (this quantity is = 2^∑_t (H(α_t) · A_t, 1· n_t) ± o(n)), times the number of Y_Ĵ∈ Y_J that is consistent with _t (this quantity is 2^(H()-H())) · A_t, 1· n_t ± o(n)). Overall, 

    P = 2^∑_t (H(α_t) + H()-H()) · A_t, 1· n_t ± o(n).










Next, we consider how to compute Q. In fact, we will show an upper bound on Q (as we only need an upper bound on (_t ∈ [s'])) by dropping the condition that “Ŷ has complete split distributions _t”.


Similar as before, we have the following claim (whose proof we omit):

    Given a level-ℓ triple X_IY_JZ_k that is consistent with {α_t}_t ∈ [s'], a level-1 block Y_Ĵ with Y_Ĵ∈ Y_J is compatible with X_IY_JZ_K if and only if the followings hold:

    

    
  * For every t ∈ [s'] and every (i', j', k') ∈^3_≥ 0∩ ([0, i_t] × [0, j_t] × [0, k_t]) with i' + j' + k'=2^ - 1 and k' = 0, (Ĵ, S_t, i',j',k') = _Y,t, i',j',k'.
  
  * For every t ∈ [s'] and j' ∈{0, …, j_t},  (Ĵ, S_t, *,j',+) = _Y,t,  *,j',+, where S_t, *,j',+ = ⋃_i' ≥ 0, k' > 0 S_t, i', j', k'. 
    



The benefit of the above claim is that {S_t, i',j',0}_t, i', j'∪{S_t, *, j', +}_t, j' forms a partition of all the indices in the first region of the t-th part of the interface tensor, after we fix some X_I Y_J Z_K that is consistent with {α_t}_t ∈ [s']. Thus, we can compute the possibilities of Ĵ on each of these subsets. 

For S_t, i',j',0, the number of possibilities of Ĵ is 
    2^H(_Y, t, i', j', 0) · (α_t(i', j', 0) + α_t(i_t - i', j_t - j', k_t - k')) · A_t, 1· n_t ± o(n).

For S_t, *, j', +, the number of possibilities of Ĵ is 
    2^H(_Y, t, *, j', +) · (α_t(*, j', +) + α_t(*, j_t - j', <)) · A_t, 1· n_t ± o(n).

Thus, The total number of possible Ĵ for a fixed triple X_I Y_J Z_K is 

    2^∑_t (∑_i', j' H(_Y, t, i', j', 0) · (α_t(i', j', 0) + α_t(i_t - i', j_t - j', k_t - k')) 
    + 
    ∑_j' H(_Y, t, *, j', +) · (α_t(*, j', +) + α_t(*, j_t - j', <))
    ) · A_t, 1· n_t ± o(n)
    
    =     2^∑_t η_Y, t· A_t, 1· n_t ± o(n).

Multiplying the above with the number of triples X_I Y_J Z_K, we get 

    Q ≤ 2^∑_t (H(α_t) + η_Y, t) · A_t, 1· n_t ± o(n).

Finally, 

    ^*(_t ∈ [s']) = Q / P ≤ 2^∑_t (η_Y, t - H() + H()) · A_t, 1· n_t ± o(n)


The bound (<ref>) on  follows because the L_∞ distance between _t and _t is at most . 





The following upper bound of  is the same as that in <cit.>, so we omit its proof. 


[<cit.>]
  The value of ^*(_t ∈ [s']) is at most
  
    2^∑_t ∈ [s']( λ_Z,t - H() + H(γ_Z, t) ) A_t,1· n_t ± o(n).

  Furthermore,
  
    ≤  2^∑_t ∈ [s']( λ_Z,t - H() + H(γ_Z, t) + (1) ) A_t,1· n_t + o(n).




The proof of the following claim is essentially the same as that of <ref>.

  
  For every b ∈ B, every level-(-1) block triple X_I Y_J Z_K consistent with {α_t}_t ∈ [s'], and every typical Z_K̂∈ Z_K, the probability that Z_K̂ is compatible with multiple level-(-1) block triples in  is at most
  
    ·/· M_0,

  conditioned on h_X(I) = h_Y(J) = h_Z(K) = b.

  Similarly for every b ∈ B, every level-(-1) block triple X_I Y_J Z_K consistent with {α_t}_t ∈ [s'], and every typical Y_Ĵ∈ Y_J, the probability that Y_Ĵ is compatible with multiple level-(-1) block triples in  is at most
  
    ·/· M_0,

  conditioned on h_X(I) = h_Y(J) = h_Z(K) = b.



Recall that we first require M_0 to be ≥ 8 ·/. Now, we finalize our choice of M_0 as:


    M_0 = max{8/,  ·/· n^2,  ·/· n^2}
    ≤ 2^max{∑_t (H(α_t) - P_α, t - H(γ_X, t)) A_t,1· n_t,   ∑_t (H(α_t) + η_Y, t - H()) A_t,1· n_t,   ∑_t (H(α_t) + λ_Z,t - H()) A_t,1· n_t} + o(n).




We consider the fraction of holes in Y-variables caused by Y-compatibility zero-outs. By <ref> and by the upper bound on M_0, the probability that each typical Y_Ĵ is compatible with multiple triples is at most 1/n^2; the same also holds for typical level-1 Z-blocks. As discussed earlier at the beginning of this subsection, there is another type of holes caused by the input complete split distributions, whose fraction is O(1/n^2). Overall, we expect to get · M^-1-o(1) copies of ^* whose fraction of holes is O(1/n^2). By <ref>, we can degenerate them into · M^-1-o(1) independent copies of unbroken ^*. 



 §.§ Summary


In conclusion, the above algorithm degenerates ⊗_t = 1^s' T_i_t, j_t, k_t^⊗ A_t,1 n_t^(1), ^(1), ^(1), into 

    · M_0^-1-o(1)
    ≥      2^min{∑_t ∈ [s'] A_t,1· n_t ·( H([t]^(1)) - P_α, t^(1)),   ∑_t ∈ [s'] A_t,1· n_t ·(H(_Y, t^(1)) - η_Y, t^(1)),   ∑_t ∈ [s'] A_t,1· n_t ·(H(_Z, t^(1)) - λ_Z, t^(1))} - (n) - o(n)

independent copies of a level-(-1) interface tensor ^* with parameter list

    {(
        A_t,1· n_t ·α^(1)_t(i', j', k')+α^(1)_t(i_t-i', j_t-j', k_t-k'),    
    
        i',   j',   k',  ^(1)_X, t, i', j', k',  ^(1)_Y, t, i', j', k',  ^(1)_Z, t, i', j', k'   ) } _t ∈ [s'], i' + j' + k' = 2^-1.




The above algorithm was described for the first region; the algorithm for other regions is identical except that we permute the roles of the X-, Y-, Z-dimensions. In the end, we take the tensor product over the output tensor of the algorithm over all 6 regions.









§ NUMERICAL RESULT



The way we combine theorems from previous sections to obtain numerical bounds on ω(1, κ, 1) is similar to previous works (e.g., <cit.>). Let ł^* > 0 be an integer denoting the highest level we hope to analyze, and let N = 2^ł^* - 1· n. We repeatedly apply <ref> to degenerate a direct sum of 2^o(n) copies of _q^⊗ N≡_q^⊗ 2^ł^* - 1^⊗ n into a direct sum of matrix multiplication tensors a, a^κ, a, shown in <ref>.





Every step of degeneration in <ref> takes a set of parameters, which includes the distribution α over constituent tensors, the fractions of tensor powers A_1, …, A_6 assigned to six regions, etc. Given an assignment to these parameters, we can calculate

    lim_→ 0lim_n →∞^1/n,   lim_→ 0lim_n →∞ a_ł^1/n,   lim_→ 0lim_n →∞ b_ł^1/n,   lim_→ 0lim_n →∞ c_ł^1/n

by <ref>. One can substitute them into (<ref>) to verify a claimed bound on ω(1, κ, 1).



  
Optimization.

Finding the set of parameters that leads to the best bound for ω(1, κ, 1) can be formulated as an optimization problem:

    [                                                                                                                      ω';                                                                                                                        ;                                                             lim_→ 0lim_n →∞^1/n·minA, B^1/κ, C^ω'/n≥ (q + 2)^2^ł^* - 1. ]

To optimize (<ref>), we utilize the software package SNOPT <cit.>, which employs a sequential quadratic programming (SQP) algorithm. Although SNOPT does not guarantee finding the optimal solution of the optimization problem, any feasible solution that provides a reasonably good bound on ω(1, κ, 1) is acceptable.

<cit.> mentioned several tricks in the optimization, including setting specific initial points, using the exponential form of Lagrange multiplier constraints, and transforming minimum functions into linear inequalities. We use all of them in the same way. See <cit.> for details.



  
Numerical results.

We wrote a MATLAB <cit.> program which uses SNOPT <cit.> to solve the optimization problem (<ref>). By executing the program with various κ values, we derived upper bounds for ω(1, κ, 1), as listed in <ref>. All these bounds were derived by analyzing _5^⊗ 4, the fourth power[We have no doubt that analyzing the eigth power and beyond would yield further improvements. However, the optimization solvers are already very slow in solving our program for the 4th power, so that solving the 8th power program seems infeasible, at least with the current solver.] of the CW tensor with q = 5. In particular, we showed that ω≤ 2.371339 and μ≤ 0.527500.[Unfortunately, we could not obtain a bound on α via SNOPT, as it crashed due to potential numerical instabilities: the number of parameters in the optimization problem is significantly larger than in previous works, hence the numerical errors accumulated more and crashed a subroutine in SNOPT.] The code and the sets of parameters are available at <https://osf.io/mw5ak/?view_only=5769f03789354793b61e11aac4dd85dd>.



alpha


