The main result was obtained by ChatGPT 6 Pro. The full chat is available at
https://chatgpt.com/share/6acf869d-a8f0-83ea-a00d-35492f5a3af5
Introduction
One of the most striking algorithms avoiding exhaustive search is the n ω + o ( 1 ) ≤ n 2.25 + o ( 1 ) n^{\omega+o(1)} \le n^{2.25+o(1)} n ω + o ( 1 ) ≤ n 2.25 + o ( 1 ) [44 ] time algorithm for detecting (and finding) a triangle in an n n n [33 ] . Taking A A A n × n n \times n n × n tr ( A 3 ) \operatorname{tr}(A^3) tr ( A 3 ) O ( n 3 ) O(n^3) O ( n 3 ) many other improvements in graph algorithms have been powered by fast matrix multiplication, such as transitive closure, shortest paths, matching, cycle and subgraph detection, and many others; see the surveys and lecture notes of Zwick [59 ] and Vassilevska Williams [57 , 58 ] .
It is natural to ask whether similar algorithmic improvements are possible for problems on generalizations of graphs, such as 3-uniform hypergraphs whose edge sets are 3-sets of vertices, or more generally k k k k ≥ 3 k \ge3 k ≥ 3 k k k ( k − 1 ) (k-1) ( k − 1 ) k ≥ 3 k \ge3 k ≥ 3 [55 ] raised the problem for k = 4 k = 4 k = 4 k k k [37 ] : faster ( k + 1 ) (k+1) ( k + 1 ) k k k k k k k k k
Hypothesis 1 (k k k For every k ≥ 4 k \ge4 k ≥ 4 there is no ε > 0 \varepsilon> 0 ε > 0 such that k k k ( k − 1 ) (k-1) ( k − 1 ) O ( n k − ε ) O(n^{k-\varepsilon}) O ( n k − ε )
As evidence for their hypothesis, they proved that unlike matrix multiplication which famously has subcubic tensor rank (starting with Strassen [50 ] ), the tensor rank of the natural ( k − 1 ) (k-1) ( k − 1 ) k k k § 1.1 for a definition) is Θ ( n k ) \Theta(n^k) Θ ( n k ) [37 ] to conclude that radically different algorithmic techniques would be needed to refute the k k k [40 , 9 , 24 , 17 , 3 , 29 FKRS25, 23 BKW26, 10 ] . Notably, [23 ] recently showed that if the k k k k k k A ⊆ { 0 , 1 , 2 , … , n } A \subseteq\{0,1,2,\ldots,n\} A ⊆ { 0 , 1 , 2 , … , n } O ( n 2 − ε ) O(n^{2-\varepsilon}) O ( n 2 − ε ) ε > 0 \varepsilon> 0 ε > 0
By the work of [55 , 37 ] mentioned above, the k k k k k k
Hypothesis 2 (Max-k k k For every k ≥ 3 k \ge3 k ≥ 3 there is no ε > 0 \varepsilon> 0 ε > 0 such that Max-k k k n n n O ( 2 ( 1 − ε ) n ) O(2^{(1-\varepsilon)n}) O ( 2 ( 1 − ε ) n )
This hypothesis had a vast literature as well, with a body of work studying algorithms and hardness for Max-k k k [54 DW06, 35 , 31 , 48 , 49 , 22 , 2 , 1 , 12 , 11 , 6 , 34 , 9 BKM+24, 47 , 36 , 18 ] . There was also a “sparse” version of the Max-k k k O ( n ) O(n) O ( n ) [6 ] .
Our Results. We prove that the k k k k ≥ 3 k \ge3 k ≥ 3 ε > 0 \varepsilon> 0 ε > 0 k k k k k k [15 Section 5.1] ) can be computed on Boolean matrices in O ( n k + 1 − ε ) O(n^{k+1-\varepsilon}) O ( n k + 1 − ε ) k k k k k k 2 ( 1 − ε k ) n 2^{(1-\varepsilon_k)n} 2 ( 1 − ε k ) n ε k > 0 \varepsilon_k > 0 ε k > 0
Our main technical result is that the natural polynomial for enumerating hypercliques (a sum over all possible hypercliques which takes the product of all hyperedges in the hyperclique, see § 1.1 for a definition) has uniform arithmetic circuits that are significantly smaller than n k n^k n k
Theorem 1. For every fixed k ≥ 3 k \ge3 k ≥ 3 k k k Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) O ( n k − ε k ) O(n^{k-\varepsilon_k}) O ( n k − ε k ) ε k = 2 − Θ ( 2 k ) \varepsilon_k = 2^{-\Theta(2^k)} ε k = 2 − Θ ( 2 k ) Z [ 1 / 2 ] \mathbb{Z}[1/2] Z [ 1/2 ] ( 1 n , 1 k ) (1^n,1^k) ( 1 n , 1 k ) O ( n k − ε k ) O(n^{k-\varepsilon_k}) O ( n k − ε k ) n k − ε k + o ( 1 ) n^{k-\varepsilon_k+o(1)} n k − ε k + o ( 1 )
Many interesting consequences follow. First of all, we can easily count the number of hypercliques in a hypergraph, by evaluating such a polynomial.
Theorem 2. For every fixed k ≥ 3 k \ge3 k ≥ 3 ( k − 1 ) (k-1) ( k − 1 ) H H H n n n k k k H H H n k − ε k + o ( 1 ) n^{k-\varepsilon_k+o(1)} n k − ε k + o ( 1 ) ε k \varepsilon_k ε k
Furthermore, applying the Baur–Strassen Theorem (Lemma 3), we can compute the natural k k k k k k
Theorem 3. For every k ≥ 3 k \ge3 k ≥ 3 ε > 0 \varepsilon> 0 ε > 0 MP k ( A 1 , … , A k ) \operatorname{MP}_k(A_1,\ldots,A_k) MP k ( A 1 , … , A k ) A 1 , … , A k A_1,\ldots,A_k A 1 , … , A k n k n^k n k O ( n k + 1 − ε ) O(n^{k+1-\varepsilon}) O ( n k + 1 − ε )
Applying these results, we can refute a much weaker hypothesis than just the Max-k k k k k k [37 ] . A Boolean function on n n n degree-k k k if it has degree at most k k k { 0 , 1 } \{0,1\} { 0 , 1 } k k k k k k k k k k k k n n n
Theorem 4. For every k ≥ 3 k \ge3 k ≥ 3 δ k > 0 \delta_k > 0 δ k > 0 k k k n n n m m m 2 ( 1 − δ k ) n poly ( n , m ) 2^{(1-\delta_k)n}\operatorname{poly}(n,m) 2 ( 1 − δ k ) n poly ( n , m )
Our results also refute a recently proposed hypothesis on the difficulty of finding short arithmetic progressions in a set of numbers. The k k k [23 Hypothesis 1.3] (see also [27 ] ) states that for every k ≥ 4 k \ge4 k ≥ 4 ε > 0 \varepsilon> 0 ε > 0 { 0 , 1 , … , n } \{0,1,\ldots,n\} { 0 , 1 , … , n } k k k O ( n 2 − ε ) O(n^{2-\varepsilon}) O ( n 2 − ε ) k = 3 k=3 k = 3 k = 4 k=4 k = 4
Theorem 5. For every fixed k ≥ 4 k \ge4 k ≥ 4 A ⊆ { 0 , … , n } A \subseteq\{0,\ldots,n\} A ⊆ { 0 , … , n } k k k O ( n 2 − 2 ε k / k ) O(n^{2-2\varepsilon_k/k}) O ( n 2 − 2 ε k / k )
Finally, our results also have bearing on a well-known problem in database theory. The k k k LM k \operatorname{LM}_k LM k k k k ( k − 1 ) (k-1) ( k − 1 ) Boolean version is exactly k k k ( k − 1 ) (k-1) ( k − 1 ) counting version is the polynomial Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) [4 ] shows that the output of L M k \mathrm{LM}_k LM k m m m m k / ( k − 1 ) m^{k/(k-1)} m k / ( k − 1 ) [42 ] can list all answers in O ~ ( m k / ( k − 1 ) ) \widetilde{O}(m^{k/(k-1)}) O ( m k / ( k − 1 ) ) [38 Theorem 3.5] , who shows that the k k k O ( m k / ( k − 1 ) − ε ) O(m^{k/(k-1)-\varepsilon}) O ( m k / ( k − 1 ) − ε ) [8 ] , we can also obtain that for every k k k ε > 0 \varepsilon> 0 ε > 0 O ( m k / ( k − 1 ) − ε ) O(m^{k/(k-1)-\varepsilon}) O ( m k / ( k − 1 ) − ε ) m m m 1
Why ¬ETH does not affect our results. Very recently, OpenAI [45 ] and Anthropic [Cla26] announced a refutation of the Exponential Time Hypothesis, showing that 3SAT on n n n exp ( n poly ( log log n ) / log n ) \exp(n\operatorname{poly}(\log\log n)/\sqrt{\log n}) exp ( n poly ( log log n ) / log n ) k k k n n n c n cn c n 2 o ( n ) 2^{o(n)} 2 o ( n ) [6 ] ), it evidently says nothing about the full Max-k k k k k k Θ ( n k ) \Theta(n^k) Θ ( n k ) all known reductions from Max-k k k m m m Ω ( m ) \Omega(m) Ω ( m ) [32 ] is known for Max-k k k k k k exp ( n 1 / k ) \exp(n^{1/k}) exp ( n 1/ k ) k k k k k k k k k
Intriguingly, our algorithm for finding hypercliques faster does share one ingredient with the OpenAI refutation of ETH [45 ] : namely, they both rely on an interesting new decomposition of the identity matrix. See Remark 1 and the discussion before it.
The algebraic approach to hyperclique
As mentioned earlier, the case of the k k k k = 3 k = 3 k = 3 tr ( A 3 ) \operatorname{tr}(A^3) tr ( A 3 ) X X X n × n n \times n n × n x i , j x_{i,j} x i , j
Δ n ( 3 ) = ∑ i , j , k ∈ [ n ] x i , k x k , j x i , j \Delta_n^{(3)} = \sum_{i,j,k \in[n]} x_{i,k}x_{k,j}x_{i,j} Δ n ( 3 ) = i , j , k ∈ [ n ] ∑ x i , k x k , j x i , j on an appropriate 0/1 input.
This leaves the tantalizing possibility of tackling the hyperclique problem via a similar algebraic approach, which is usually formulated as the problem of evaluating the hyperclique polynomial .
The hyperclique polynomial. Let k > 2 k > 2 k > 2 k k k α ∈ [ n ] k \alpha\in[n]^k α ∈ [ n ] k j ∈ [ k ] j \in[k] j ∈ [ k ] α − j \alpha_{-j} α − j [ n ] k − 1 [n]^{k-1} [ n ] k − 1 j j j α \alpha α hyperclique polynomial is defined by
Δ n ( k ) ( X ) : = ∑ α ∈ [ n ] k ∏ j = 1 k x α − j ( j ) \Delta_n^{(k)}(X) := \sum_{\alpha\in[n]^k} \prod_{j=1}^{k} x_{\alpha_{-j}}^{(j)} Δ n ( k ) ( X ) := α ∈ [ n ] k ∑ j = 1 ∏ k x α − j ( j ) This is a multilinear polynomial of degree k k k k k k n k − 1 n^{k-1} n k − 1
X ( j ) = { x β ( j ) , β ∈ [ n ] k − 1 } . X^{(j)} = \{x_{\beta}^{(j)}, \beta\in[n]^{k-1}\}. X ( j ) = { x β ( j ) , β ∈ [ n ] k − 1 } . Given a ( k − 1 ) (k-1) ( k − 1 ) k k k H = ⨆ i = 1 k H i H = \bigsqcup_{i=1}^{k} H_i H = ⨆ i = 1 k H i H i = [ n ] H_i = [n] H i = [ n ] x α − j ( j ) = 1 x_{\alpha_{-j}}^{(j)} = 1 x α − j ( j ) = 1 H H H ( k − 1 ) (k-1) ( k − 1 ) α − j \alpha_{-j} α − j j j j 0 0 0 Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) X X X k k k H H H
For example, when k = 2 k = 2 k = 2 Δ n ( 2 ) = ∑ i , j x i ( 1 ) x j ( 2 ) \Delta_n^{(2)} = \sum_{i,j} x_i^{(1)}x_j^{(2)} Δ n ( 2 ) = ∑ i , j x i ( 1 ) x j ( 2 ) k = 3 k = 3 k = 3 Δ n ( 3 ) = ∑ i , j , k x j k ( 1 ) x i k ( 2 ) x i j ( 3 ) \Delta_n^{(3)} = \sum_{i,j,k} x_{jk}^{(1)}x_{ik}^{(2)}x_{ij}^{(3)} Δ n ( 3 ) = ∑ i , j , k x j k ( 1 ) x ik ( 2 ) x ij ( 3 ) matrix multiplication tensor :
tr ( X Y Z ) = ∑ i , j , k x i j y j k z k i . \operatorname{tr}(XYZ) = \sum_{i,j,k} x_{ij}y_{jk}z_{ki}. tr ( X Y Z ) = i , j , k ∑ x ij y j k z k i . It is clear that Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) O ( n k ) O(n^k) O ( n k ) n k n^k n k k = 2 k = 2 k = 2 k = 3 k = 3 k = 3 Δ n ( 2 ) \Delta_n^{(2)} Δ n ( 2 ) O ( n ) O(n) O ( n ) k = 3 k = 3 k = 3 n 3 − ε n^{3-\varepsilon} n 3 − ε [50 ] . Theorem 1 gives polynomial improvements over the trivial bound for all k k k
Arithmetic circuits and tensor ranks
Before proceeding to our improvement for the hyperclique polynomials, we discuss why people had believed the hyperclique conjecture even though there are nontrivial algorithms for matrix multiplication. We begin by reviewing the high-level approach of fast matrix multiplication algorithms.
Tensor rank and its “barrier”. A fundamental measure of a tensor is the tensor rank R ( f ) R(f) R ( f ) f f f R ( f ) R(f) R ( f ) r r r
f ( X ) = ∑ i = 1 r ℓ i ( 1 ) ( X ( 1 ) ) ⋯ ℓ i ( k ) ( X ( k ) ) , (1) f(X) = \sum_{i=1}^{r} \ell_i^{(1)}(X^{(1)}) \cdots\ell_i^{(k)}(X^{(k)}), \tag*{(1)} f ( X ) = i = 1 ∑ r ℓ i ( 1 ) ( X ( 1 ) ) ⋯ ℓ i ( k ) ( X ( k ) ) , (1) where ℓ i ( j ) \ell_i^{(j)} ℓ i ( j ) X ( j ) X^{(j)} X ( j )
The importance of tensor rank is twofold.
On one hand, in the world of 3-mode tensors, Strassen [51 ] proved that tensor rank characterizes the multiplicative complexity , which is the number of nonscalar multiplications required to evaluate the tensor. It thus provides a lower bound for the circuit complexity.
On the other hand, tensor rank upper bounds can be generally turned into algorithms. In fact, the seminal algorithm for matrix multiplication due to Strassen [50 ] can be seen as finding a 7-term rank decomposition for 2 × 2 2 \times2 2 × 2 O ( n log 2 7 ) O(n^{\log_2 7}) O ( n l o g 2 7 ) n × n n \times n n × n
One might hope to generalize Strassen’s approach to higher-order tensors. The trivial rank decomposition of the hyperclique tensor Δ n ( k ) \Delta^{(k)}_n Δ n ( k ) n k n^k n k r r r q q q r < q k r < q^k r < q k O ( n log q r ) O(n^{\log_q r}) O ( n l o g q r ) [37 Theorem 8.1] pointed out that when k ≥ 4 k \ge4 k ≥ 4 n k n^k n k Δ n ( k ) \Delta^{(k)}_n Δ n ( k )
Partitions and ranks. However, a lower bound on tensor rank doesn’t rule out the possibility of having small arithmetic circuits for higher modes. A folklore example is known as the product of inner products tensor:
PIP n ( X , Y , Z , W ) = ( ∑ i = 1 n x i z i ) ( ∑ j = 1 n y j w j ) . (2) \operatorname{PIP}_n(X,Y,Z,W) = \left(\sum_{i=1}^{n} x_i z_i\right)\left(\sum_{j=1}^{n} y_j w_j\right). \tag*{(2)} PIP n ( X , Y , Z , W ) = ( i = 1 ∑ n x i z i ) ( j = 1 ∑ n y j w j ) . (2) It is clear from the definition that PIP n \operatorname{PIP}_n PIP n O ( n ) O(n) O ( n ) n 2 n^2 n 2 flattening which we demonstrate here to give insight into the limitation of tensor rank.
We can expand the expression of the PIP tensor
PIP n ( X , Y , Z , W ) = ∑ i , j = 1 n x i y j ⋅ z i w j , (3) \operatorname{PIP}_n(X,Y,Z,W) = \sum_{i,j=1}^{n} x_i y_j \cdot z_i w_j, \tag*{(3)} PIP n ( X , Y , Z , W ) = i , j = 1 ∑ n x i y j ⋅ z i w j , (3) which is naturally an n 2 n^2 n 2 n 2 n^2 n 2 flatten the tensor: think of this tensor as an n 2 × n 2 n^2 \times n^2 n 2 × n 2 X , Y X,Y X , Y Z , W Z,W Z , W (1) would be a rank-1 matrix after flattening; this means if a tensor has rank r r r r r r n 2 n^2 n 2 n 2 n^2 n 2
Besides the concrete example above, let’s again consider another argument which is a structural view of arithmetic circuits. For a tensor, we can actually assume2
Tensor rank can be thought of as corresponding to a restricted class of circuits of the form “Σ Π Σ \Sigma\Pi\Sigma ΣΠΣ k k k Σ Π Σ Π Σ \Sigma\Pi\Sigma\Pi\Sigma ΣΠΣΠΣ Π Σ Π \Pi\Sigma\Pi ΠΣΠ
That said, the k = 3 k = 3 k = 3 [51 ] proved that tensor rank provides a lower bound on circuit size, works merely because in this regime every arithmetic circuit necessarily has the form Σ Π Σ \Sigma\Pi\Sigma ΣΠΣ
What, then, is the correct notion of rank that can provide useful information for circuit complexity? A natural approach is to make the required terms in a rank decomposition more flexible, so that it’s possible to charge each term to a specific product gate. For example, one might consider the partition rank defined by Naslund [41 ] : PR ( f ) \operatorname{PR}(f) PR ( f ) r r r f f f
f = ∑ i = 1 r u i ⋅ v i f = \sum_{i=1}^{r} u_i \cdot v_i f = i = 1 ∑ r u i ⋅ v i where each u i u_i u i S i S_i S i k k k v i v_i v i [ k ] ∖ S i [k]\setminus S_i [ k ] ∖ S i Figure 1 shows how to turn a circuit evaluating the (small) Coppersmith–Winograd tensor c w q = ∑ i = 1 q ( x 0 y i z i + x i y 0 z i + x i y i z 0 ) \mathrm{cw}_q = \sum_{i=1}^{q}(x_0y_iz_i+x_iy_0z_i+x_iy_iz_0) cw q = ∑ i = 1 q ( x 0 y i z i + x i y 0 z i + x i y i z 0 )
Figure 1. Turn a Σ Π Σ Π \Sigma\Pi\Sigma\Pi ΣΠΣΠ
The partition rank is actually a poor measure of circuit complexity — one can always write a tensor as f = ∑ i x i ( 1 ) ⋅ f i f = \sum_i x_i^{(1)} \cdot f_i f = ∑ i x i ( 1 ) ⋅ f i f i f_i f i x i ( 1 ) x_i^{(1)} x i ( 1 ) 3 ^{3} 3 S i S_i S i
These kinds of partition ranks appear to admit interesting upper bounds and further guide genuine circuit construction. For example, the study of Hrubeš [30 ] on sum-of-squares identities can be interpreted as bounding the restricted partition rank of the PIP tensor: One can decompose P I P n \mathrm{PIP}_n PIP n O ( n 1.62 ) O(n^{1.62}) O ( n 1.62 ) ( X Y ∣ Z W ) (XY\mathbin{|}ZW) ( X Y ∣ Z W ) ( X W ∣ Y Z ) (XW\mathbin{|}YZ) ( X W ∣ Y Z ) 4 noncommutative circuit, of size only O ( n 1.96 ) O(n^{1.96}) O ( n 1.96 ) P I P n \mathrm{PIP}_n PIP n (3) with noncommuting variables.
Our presentation of the circuit for the hyperclique polynomial will follow a similar route: We will first explain how to obtain a certain kind of partition rank of Δ n ( k ) \Delta_n^{(k)} Δ n ( k )
We also remark that recently, Brand, Kaski and Wang [BKW26] proposed another modification of partition ranks, which aims to generalize Strassen’s lower bound to higher modes. They define the ( k − 2 , 1 , 1 ) (k-2,1,1) ( k − 2 , 1 , 1 ) ( k − 2 ) (k-2) ( k − 2 ) R k − 2 , 1 , 1 ( f ) R_{k-2,1,1}(f) R k − 2 , 1 , 1 ( f ) ( k − 2 , 1 , 1 ) (k-2,1,1) ( k − 2 , 1 , 1 )
A partition rank decomposition
In this subsection, we will focus on the k = 4 k=4 k = 4 O ( n 4 − ϵ ) O(n^{4-\epsilon}) O ( n 4 − ϵ )
Merely below brute-force. We first begin with a “baby step,” finding a decomposition with fewer than n 4 n^4 n 4
For convenience, we will relabel the variables in the following way:
Δ n ( 4 ) ( X , Y , Z , W ) = ∑ i , j , k , ℓ = 1 n x j k ℓ y i k ℓ z i j ℓ w i j k . \Delta_n^{(4)}(X,Y,Z,W)=\sum_{i,j,k,\ell=1}^{n}x_{jk\ell}y_{ik\ell}z_{ij\ell}w_{ijk}. Δ n ( 4 ) ( X , Y , Z , W ) = i , j , k , ℓ = 1 ∑ n x j k ℓ y ik ℓ z ij ℓ w ij k . We strategically first pair the variable set into groups X Z XZ X Z Y W YW Y W
Δ n ( 4 ) ( X , Y , Z , W ) = ∑ i , j , k , ℓ = 1 n x j k ℓ z i j ℓ ⋅ y i k ℓ w i j k . \Delta_n^{(4)}(X,Y,Z,W)=\sum_{i,j,k,\ell=1}^{n}x_{jk\ell}z_{ij\ell}\cdot y_{ik\ell}w_{ijk}. Δ n ( 4 ) ( X , Y , Z , W ) = i , j , k , ℓ = 1 ∑ n x j k ℓ z ij ℓ ⋅ y ik ℓ w ij k . then we artificially add and then subtract a term x i k ℓ z j i ℓ x_{ik\ell}z_{ji\ell} x ik ℓ z j i ℓ i i i j j j x j k ℓ z i j ℓ x_{jk\ell}z_{ij\ell} x j k ℓ z ij ℓ
Δ n ( 4 ) ( X , Y , Z , W ) = ∑ i , j , k , ℓ = 1 n ( x j k ℓ z i j ℓ − x i k ℓ z j i ℓ + x i k ℓ z j i ℓ ) ⋅ y i k ℓ w i j k = ∑ i , j , k , ℓ = 1 n ( x j k ℓ z i j ℓ − x i k ℓ z j i ℓ ) y i k ℓ w i j k + ∑ i , j , k , ℓ = 1 n x i k ℓ z j i ℓ ⋅ y i k ℓ w i j k = : T 0 + T 1 . (4) \begin{aligned}
\Delta_n^{(4)}(X,Y,Z,W)=\sum_{i,j,k,\ell=1}^{n}(x_{jk\ell}z_{ij\ell}-x_{ik\ell}z_{ji\ell}+x_{ik\ell}z_{ji\ell})\cdot y_{ik\ell}w_{ijk} \\
&=\sum_{i,j,k,\ell=1}^{n}(x_{jk\ell}z_{ij\ell}-x_{ik\ell}z_{ji\ell})y_{ik\ell}w_{ijk}+\sum_{i,j,k,\ell=1}^{n}x_{ik\ell}z_{ji\ell}\cdot y_{ik\ell}w_{ijk} \\
&=:T_0+T_1. \tag*{(4)}
\end{aligned} Δ n ( 4 ) ( X , Y , Z , W ) = i , j , k , ℓ = 1 ∑ n ( x j k ℓ z ij ℓ − x ik ℓ z j i ℓ + x ik ℓ z j i ℓ ) ⋅ y ik ℓ w ij k = i , j , k , ℓ = 1 ∑ n ( x j k ℓ z ij ℓ − x ik ℓ z j i ℓ ) y ik ℓ w ij k + i , j , k , ℓ = 1 ∑ n x ik ℓ z j i ℓ ⋅ y ik ℓ w ij k =: T 0 + T 1 . (4) The advantage comes from analyzing each of T 0 T_0 T 0 T 1 T_1 T 1 T 0 T_0 T 0 x j k ℓ z i j ℓ − x i k ℓ z j i ℓ x_{jk\ell}z_{ij\ell}-x_{ik\ell}z_{ji\ell} x j k ℓ z ij ℓ − x ik ℓ z j i ℓ antisymmetric with respect to i i i j j j
T 0 = ∑ 1 ≤ i < j ≤ n k , ℓ = 1 n ( x j k ℓ z i j ℓ − x i k ℓ z j i ℓ ) ( y i k ℓ w i j k − y j k ℓ w j i k ) , T_0=\sum_{\substack{1\le i<j\le n\\ k,\ell=1}}^{n}(x_{jk\ell}z_{ij\ell}-x_{ik\ell}z_{ji\ell})(y_{ik\ell}w_{ijk}-y_{jk\ell}w_{jik}), T 0 = 1 ≤ i < j ≤ n k , ℓ = 1 ∑ n ( x j k ℓ z ij ℓ − x ik ℓ z j i ℓ ) ( y ik ℓ w ij k − y j k ℓ w j ik ) , which only has ( n 2 ) n 2 ≈ n 4 / 2 \binom{n}{2}n^2\approx n^4/2 ( 2 n ) n 2 ≈ n 4 /2 n 4 n^4 n 4
The saving for T 1 T_1 T 1 which indices each variable depends on . Looking at the indices of the four variables in
T 1 = ∑ i , j , k , ℓ = 1 n x i k ℓ z j i ℓ ⋅ y i k ℓ w i j k , T_1=\sum_{i,j,k,\ell=1}^{n}x_{ik\ell}z_{ji\ell}\cdot y_{ik\ell}w_{ijk}, T 1 = i , j , k , ℓ = 1 ∑ n x ik ℓ z j i ℓ ⋅ y ik ℓ w ij k , we see that compared to Δ n ( 4 ) \Delta_n^{(4)} Δ n ( 4 ) z z z j , i , ℓ j,i,\ell j , i , ℓ x x x i , k , ℓ i,k,\ell i , k , ℓ j , k , ℓ j,k,\ell j , k , ℓ i i i
T 1 = ∑ i = 1 n ∑ j , k , ℓ = 1 n ( x i k ℓ ⋅ y i k ℓ ) z j i ℓ w i j k = ∑ i = 1 n Δ n ( 3 ) ( { x i k ℓ ⋅ y i k ℓ } k ℓ , { z j i ℓ } j ℓ , { w i j k } j k ) , \begin{aligned}
T_1=\sum_{i=1}^{n}\sum_{j,k,\ell=1}^{n}(x_{ik\ell}\cdot y_{ik\ell})z_{ji\ell}w_{ijk} \\
&=\sum_{i=1}^{n}\Delta_n^{(3)}\left(\{x_{ik\ell}\cdot y_{ik\ell}\}_{k\ell},\{z_{ji\ell}\}_{j\ell},\{w_{ijk}\}_{jk}\right),
\end{aligned} T 1 = i = 1 ∑ n j , k , ℓ = 1 ∑ n ( x ik ℓ ⋅ y ik ℓ ) z j i ℓ w ij k = i = 1 ∑ n Δ n ( 3 ) ( { x ik ℓ ⋅ y ik ℓ } k ℓ , { z j i ℓ } j ℓ , { w ij k } j k ) , which becomes a sum of n n n Δ n ( 3 ) \Delta_n^{(3)} Δ n ( 3 ) Δ n ( 3 ) \Delta_n^{(3)} Δ n ( 3 ) n ω + o ( 1 ) n^{\omega+o(1)} n ω + o ( 1 ) ω < 3 \omega<3 ω < 3 x ⋅ y , z , w x\cdot y,z,w x ⋅ y , z , w ( X Y ∣ Z ∣ W ) (XY|Z|W) ( X Y ∣ Z ∣ W )
Putting these decompositions together, we now have a way to rewrite Δ n ( 4 ) \Delta_n^{(4)} Δ n ( 4 ) T 0 + T 1 T_0+T_1 T 0 + T 1
T 0 T_0 T 0 n 4 / 2 n^4/2 n 4 /2 X Z ∣ Y W XZ|YW X Z ∣ Y W
T 1 T_1 T 1 n ω + 1 + o ( 1 ) n^{\omega+1+o(1)} n ω + 1 + o ( 1 ) X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W
Because ω < 3 \omega<3 ω < 3 n 4 / 2 n^4/2 n 4 /2
We can sanity check this decomposition by comparing it with the rank lower bound from flattening that we discussed in § 1.2 above. That argument gives an n 4 n^4 n 4 ( X Z ∣ Y W ) (XZ|YW) ( X Z ∣ Y W ) ( X Z ∣ Y W ) (XZ|YW) ( X Z ∣ Y W ) ( X Y ∣ Z ∣ W ) (XY|Z|W) ( X Y ∣ Z ∣ W ) k ≥ 4 k \ge4 k ≥ 4 n k n^k n k
Tensor up? A common strategy to boost a nontrivial bound to a larger polynomial saving is through taking tensor powers . Let f , g f,g f , g k k k
f = ∑ i 1 , … , i k f i 1 , … , i k x i 1 ( 1 ) ⋯ x i k ( k ) , g = ∑ j 1 , … , j k g j 1 , … , j k x j 1 ( 1 ) ⋯ x j k ( k ) . f = \sum_{i_1,\ldots,i_k} f_{i_1,\ldots,i_k} x_{i_1}^{(1)} \cdots x_{i_k}^{(k)}, \qquad g = \sum_{j_1,\ldots,j_k} g_{j_1,\ldots,j_k} x_{j_1}^{(1)} \cdots x_{j_k}^{(k)}. f = i 1 , … , i k ∑ f i 1 , … , i k x i 1 ( 1 ) ⋯ x i k ( k ) , g = j 1 , … , j k ∑ g j 1 , … , j k x j 1 ( 1 ) ⋯ x j k ( k ) . Their tensor product (also called Kronecker product ) is defined as
f ⊗ g = ∑ i 1 , … , i k j 1 , … , j k f i 1 , … , i k g j 1 , … , j k x i 1 j 1 ( 1 ) ⋯ x i k j k ( k ) . f \otimes g = \sum_{\substack{i_1,\ldots,i_k\\j_1,\ldots,j_k}} f_{i_1,\ldots,i_k}g_{j_1,\ldots,j_k} x_{i_1j_1}^{(1)} \cdots x_{i_kj_k}^{(k)}. f ⊗ g = i 1 , … , i k j 1 , … , j k ∑ f i 1 , … , i k g j 1 , … , j k x i 1 j 1 ( 1 ) ⋯ x i k j k ( k ) . A notable property of tensor rank is its submultiplicativity R ( f ⊗ g ) ≤ R ( f ) ⋅ R ( g ) \mathrm{R}(f \otimes g) \le\mathrm{R}(f) \cdot\mathrm{R}(g) R ( f ⊗ g ) ≤ R ( f ) ⋅ R ( g ) f , g f,g f , g
f = ∑ i ℓ i ( 1 ) ⋯ ℓ i ( k ) , g = ∑ j ℓ j ( 1 ) ⋯ ℓ j ( k ) , f = \sum_i \ell_i^{(1)} \cdots\ell_i^{(k)}, \qquad g = \sum_j \ell_j^{(1)} \cdots\ell_j^{(k)}, f = i ∑ ℓ i ( 1 ) ⋯ ℓ i ( k ) , g = j ∑ ℓ j ( 1 ) ⋯ ℓ j ( k ) , then their tensor product can as well by expanding
f ⊗ g = ∑ i , j ( ℓ i ( 1 ) ⋯ ℓ i ( k ) ) ⊗ ( ℓ j ( 1 ) ⋯ ℓ j ( k ) ) = ∑ i , j ( ℓ i ( 1 ) ⊗ ℓ j ( 1 ) ) ⋯ ( ℓ i ( k ) ⊗ ℓ j ( k ) ) , \begin{aligned}
f \otimes g = \sum_{i,j} \left(\ell_i^{(1)} \cdots\ell_i^{(k)}\right) \otimes\left(\ell_j^{(1)} \cdots\ell_j^{(k)}\right) \\
&= \sum_{i,j} \left(\ell_i^{(1)} \otimes\ell_j^{(1)}\right) \cdots\left(\ell_i^{(k)} \otimes\ell_j^{(k)}\right),
\end{aligned} f ⊗ g = i , j ∑ ( ℓ i ( 1 ) ⋯ ℓ i ( k ) ) ⊗ ( ℓ j ( 1 ) ⋯ ℓ j ( k ) ) = i , j ∑ ( ℓ i ( 1 ) ⊗ ℓ j ( 1 ) ) ⋯ ( ℓ i ( k ) ⊗ ℓ j ( k ) ) , because the tensor product of rank-1 terms is again a rank-1 term.
Hyperclique tensors have the self-similarity property Δ n m ( k ) = Δ n ( k ) ⊗ Δ m ( k ) \Delta_{nm}^{(k)} = \Delta_n^{(k)} \otimes\Delta_m^{(k)} Δ nm ( k ) = Δ n ( k ) ⊗ Δ m ( k ) k = 3 k=3 k = 3 R ( Δ q ( 3 ) ) ≤ r \mathrm{R}(\Delta_q^{(3)}) \le r R ( Δ q ( 3 ) ) ≤ r n = q d n=q^d n = q d
R ( Δ q d ( 3 ) ) = R ( ( Δ q ( 3 ) ) ⊗ d ) ≤ r d . \mathrm{R}(\Delta_{q^d}^{(3)}) = \mathrm{R}\left((\Delta_q^{(3)})^{\otimes d}\right) \le r^d. R ( Δ q d ( 3 ) ) = R ( ( Δ q ( 3 ) ) ⊗ d ) ≤ r d . With some more care, one can use this to show the rank and the circuit complexity of Δ n ( 3 ) \Delta_n^{(3)} Δ n ( 3 ) O ( n log q r ) O(n^{\log_q r}) O ( n l o g q r ) ω ≤ log q r \omega\le\log_q r ω ≤ log q r
Can the tensor product argument also let us boost our “partition rank” estimate from < n 4 < n^4 < n 4 n 4 − ε n^{4-\varepsilon} n 4 − ε Δ n ( 4 ) = T 0 + T 1 \Delta_n^{(4)} = T_0+T_1 Δ n ( 4 ) = T 0 + T 1 T 0 T_0 T 0 X Z ∣ Y W XZ|YW X Z ∣ Y W T 1 T_1 T 1 X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W q q q Δ q ( 4 ) = T 0 + T 1 \Delta_q^{(4)} = T_0+T_1 Δ q ( 4 ) = T 0 + T 1 Δ q d ( 4 ) = ( Δ q ( 4 ) ) ⊗ d \Delta_{q^d}^{(4)} = (\Delta_q^{(4)})^{\otimes d} Δ q d ( 4 ) = ( Δ q ( 4 ) ) ⊗ d A ⊆ [ d ] A \subseteq[d] A ⊆ [ d ] T A = T 0 ⊗ [ d ] ∖ A T 1 ⊗ A T_A = T_0^{\otimes[d]\setminus A}T_1^{\otimes A} T A = T 0 ⊗ [ d ] ∖ A T 1 ⊗ A d d d a a a T 1 T_1 T 1 a ∈ A a \in A a ∈ A T 0 T_0 T 0
Δ q d ( 4 ) = ( T 0 + T 1 ) ⊗ d = ∑ A ⊆ [ d ] T A . \Delta_{q^d}^{(4)} = (T_0+T_1)^{\otimes d} = \sum_{A \subseteq[d]} T_A. Δ q d ( 4 ) = ( T 0 + T 1 ) ⊗ d = A ⊆ [ d ] ∑ T A . The cases A = ∅ A = \varnothing A = ∅ A = [ d ] A = [d] A = [ d ] T 0 ⊗ d T_0^{\otimes d} T 0 ⊗ d T 1 ⊗ d T_1^{\otimes d} T 1 ⊗ d X Z ∣ Y W XZ|YW X Z ∣ Y W X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W T 0 ⊗ T 1 T_0 \otimes T_1 T 0 ⊗ T 1 X Z ∣ Y W XZ|YW X Z ∣ Y W X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W
Dichotomy. Nonetheless, this problem can be resolved by a dichotomy argument. Intuitively, we will argue that if ∣ A ∣ |A| ∣ A ∣ T A T_A T A T 0 T_0 T 0 T 0 ⊗ d T_0^{\otimes d} T 0 ⊗ d low-degree case, and notationally will label tensors corresponding to this case with L L L (7) below with low degree in the τ \tau τ ∣ A ∣ |A| ∣ A ∣ T A T_A T A T 1 ⊗ d T_1^{\otimes d} T 1 ⊗ d high-degree case labeled by H H H
We pick some threshold t t t
( T 0 + T 1 ) ⊗ d = ∑ ∣ A ∣ ≤ t T A + ∑ ∣ A ∣ > t T A = : Δ q d , L ( 4 ) + Δ q d , H ( 4 ) . (T_0 + T_1)^{\otimes d} = \sum_{|A|\leq t} T_A + \sum_{|A|>t} T_A =: \Delta_{q^d,L}^{(4)} + \Delta_{q^d,H}^{(4)}. ( T 0 + T 1 ) ⊗ d = ∣ A ∣ ≤ t ∑ T A + ∣ A ∣ > t ∑ T A =: Δ q d , L ( 4 ) + Δ q d , H ( 4 ) . We can actually argue that the low-degree part Δ q d , L ( 4 ) \Delta_{q^d,L}^{(4)} Δ q d , L ( 4 ) X Z ∣ Y W XZ|YW X Z ∣ Y W Δ q d , H ( 4 ) \Delta_{q^d,H}^{(4)} Δ q d , H ( 4 ) X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W
Low-degree. The X Z ∣ Y W XZ|YW X Z ∣ Y W x x x z z z y y y w w w Δ q ( 4 ) \Delta_q^{(4)} Δ q ( 4 )
V = span { x j k ℓ z i j ℓ } i , j , k , ℓ ∈ [ q ] . V = \operatorname{span}\{x_{j k \ell}z_{i j \ell}\}_{i,j,k,\ell\in[q]}. V = span { x j k ℓ z ij ℓ } i , j , k , ℓ ∈ [ q ] . while the row space of T 0 T_0 T 0 i i i j j j
V 0 = span { x j k ℓ z i j ℓ − x i k ℓ z j i ℓ } i , j , k , ℓ ∈ [ q ] ⊂ V . V_0 = \operatorname{span}\{x_{j k \ell}z_{i j \ell} - x_{i k \ell}z_{j i \ell}\}_{i,j,k,\ell\in[q]} \subset V. V 0 = span { x j k ℓ z ij ℓ − x ik ℓ z j i ℓ } i , j , k , ℓ ∈ [ q ] ⊂ V . Think of V V V V 0 V_0 V 0 V = V 0 ⊕ V 1 V = V_0 \oplus V_1 V = V 0 ⊕ V 1 T A T_A T A ∣ A ∣ ≤ t |A| \leq t ∣ A ∣ ≤ t t t t V 1 V_1 V 1 Δ q d , L ( 4 ) \Delta_{q^d,L}^{(4)} Δ q d , L ( 4 )
R X Z ∣ Y W ( Δ q d , L ( 4 ) ) ≤ ∑ b ≤ t ( d b ) ( dim V 0 ) d − b ( dim V 1 ) b = ∑ b ≤ t ( d b ) [ q 3 ( q − 1 ) 2 ] d − b [ q 3 ( q + 1 ) 2 ] b . (5) R_{XZ|YW}(\Delta_{q^d,L}^{(4)}) \leq\sum_{b\leq t} \binom{d}{b}(\dim V_0)^{d-b}(\dim V_1)^b = \sum_{b\leq t} \binom{d}{b}\left[\frac{q^3(q-1)}{2}\right]^{d-b}\left[\frac{q^3(q+1)}{2}\right]^b. \tag*{(5)} R X Z ∣ Y W ( Δ q d , L ( 4 ) ) ≤ b ≤ t ∑ ( b d ) ( dim V 0 ) d − b ( dim V 1 ) b = b ≤ t ∑ ( b d ) [ 2 q 3 ( q − 1 ) ] d − b [ 2 q 3 ( q + 1 ) ] b . (5) High-degree. For the X Y ∣ Z ∣ W XY|Z|W X Y ∣ Z ∣ W T A T_A T A ∣ A ∣ = b > t |A| = b > t ∣ A ∣ = b > t
R X Y ∣ Z ∣ W ( T A ) ≤ R X Y ∣ Z ∣ W ( T 0 ) d − b R X Y ∣ Z ∣ W ( T 1 ) b . R_{XY|Z|W}(T_A) \leq R_{XY|Z|W}(T_0)^{d-b} R_{XY|Z|W}(T_1)^b. R X Y ∣ Z ∣ W ( T A ) ≤ R X Y ∣ Z ∣ W ( T 0 ) d − b R X Y ∣ Z ∣ W ( T 1 ) b . Write r = R X Y ∣ Z ∣ W ( T 1 ) r = R_{XY|Z|W}(T_1) r = R X Y ∣ Z ∣ W ( T 1 ) T 0 = Δ q ( 4 ) − T 1 T_0 = \Delta_q^{(4)} - T_1 T 0 = Δ q ( 4 ) − T 1 R X Y ∣ Z ∣ W ( T 0 ) R_{XY|Z|W}(T_0) R X Y ∣ Z ∣ W ( T 0 ) q 4 + r q^4 + r q 4 + r Δ q d , H ( 4 ) \Delta_{q^d,H}^{(4)} Δ q d , H ( 4 )
R X Y ∣ Z ∣ W ( Δ q d , H ( 4 ) ) ≤ ∑ b > t ( d b ) ( q 4 + r ) d − b r b . (6) R_{XY|Z|W}(\Delta_{q^d,H}^{(4)}) \leq\sum_{b>t} \binom{d}{b}(q^4+r)^{d-b}r^b. \tag*{(6)} R X Y ∣ Z ∣ W ( Δ q d , H ( 4 ) ) ≤ b > t ∑ ( b d ) ( q 4 + r ) d − b r b . (6) Threshold. We want to set the threshold t t t ( q d ) 4 − ε (q^d)^{4-\varepsilon} ( q d ) 4 − ε q 4 d q^{4d} q 4 d t t t b / d ≈ ( dim V 1 ) / ( dim V ) = ( q + 1 ) / 2 q b/d \approx(\dim V_1)/(\dim V) = (q+1)/2q b / d ≈ ( dim V 1 ) / ( dim V ) = ( q + 1 ) /2 q t t t t = d / 2 t=d/2 t = d /2
For the high-degree part, note that we have r = q ω + 1 + o ( 1 ) r=q^{\omega+1+o(1)} r = q ω + 1 + o ( 1 ) ω < 3 \omega<3 ω < 3 r / q 4 → 0 r/q^4\to0 r / q 4 → 0 q → ∞ q\to\infty q → ∞ q q q (6) just comes from the b ≈ d / 2 b\approx d/2 b ≈ d /2 [ 2 q 4 + r ⋅ r ] d [2\sqrt{q^4+r}\cdot r]^d [ 2 q 4 + r ⋅ r ] d q q q q 4 d q^{4d} q 4 d Δ q d , L ( 4 ) \Delta^{(4)}_{q^d,L} Δ q d , L ( 4 ) Δ q d , H ( 4 ) \Delta^{(4)}_{q^d,H} Δ q d , H ( 4 ) q ( 4 − ε ) d q^{(4-\varepsilon)d} q ( 4 − ε ) d
We remark that dichotomy arguments like this have already appeared in previous studies of tensors and matrices, including some partition rank (including slice rank) upper bounds in combinatorics [CLP17; EG17; TS16; NS17; Nas20], as well as matrix rigidity upper bounds [7 , 5 ] .
In the next subsection, we take this partition rank construction and complete it into a genuine circuit. Before proceeding, we remark on a few technical differences which will arise as we do this. For the general analysis of the high-degree part Δ q d , H ( k ) \Delta^{(k)}_{q^d,H} Δ q d , H ( k ) (6) by a circuit bound, since our approach mainly reduces it to many ( k − 1 ) (k-1) ( k − 1 ) Δ q d , L ( k ) \Delta^{(k)}_{q^d,L} Δ q d , L ( k ) t = d / B t=d/B t = d / B B > 2 B>2 B > 2 k k k
Circuit construction
In this subsection, we will sketch how to extend the previous partition rank upper bound to a circuit size upper bound; in section 3 we will formally prove the result sketched here. The proof proceeds by induction on k k k Δ n ( k − 1 ) \Delta^{(k-1)}_n Δ n ( k − 1 ) O ( n k − 1 − ε ) O(n^{k-1-\varepsilon}) O ( n k − 1 − ε ) ε > 0 \varepsilon>0 ε > 0 Δ n ( k ) \Delta^{(k)}_n Δ n ( k ) n k − ε ′ n^{k-\varepsilon'} n k − ε ′ ε ′ > 0 \varepsilon'>0 ε ′ > 0 Δ n ( 3 ) \Delta^{(3)}_n Δ n ( 3 ) n ω + o ( 1 ) n^{\omega+o(1)} n ω + o ( 1 )
From now on, let k k k ε \varepsilon ε n = q d n=q^d n = q d q = 2 B q=2^B q = 2 B B B B k k k ε \varepsilon ε n n n
Setup. We start by introducing some notation. Label the k k k ( i , j , z 1 , … , z k − 2 ) ∈ [ n ] k (i,j,z_1,\ldots,z_{k-2})\in[n]^k ( i , j , z 1 , … , z k − 2 ) ∈ [ n ] k U ( i , z ) U(i,z) U ( i , z ) V ( j , z ) V(j,z) V ( j , z ) X s ( i , j , z − s ) X_s(i,j,z_{-s}) X s ( i , j , z − s ) i , j ∈ [ n ] i,j\in[n] i , j ∈ [ n ] z ∈ [ n ] k − 2 z\in[n]^{k-2} z ∈ [ n ] k − 2 s ∈ [ k − 2 ] s\in[k-2] s ∈ [ k − 2 ] k k k
Δ n ( k ) = ∑ i , j ∈ [ n ] , z ∈ [ n ] k − 2 U ( i , z ) V ( j , z ) ∏ s = 1 k − 2 X s ( i , j , z − s ) . \Delta^{(k)}_n=\sum_{i,j\in[n],\,z\in[n]^{k-2}}U(i,z)V(j,z)\prod_{s=1}^{k-2}X_s(i,j,z_{-s}). Δ n ( k ) = i , j ∈ [ n ] , z ∈ [ n ] k − 2 ∑ U ( i , z ) V ( j , z ) s = 1 ∏ k − 2 X s ( i , j , z − s ) . We partition the k k k U U U X k − 2 X_{k-2} X k − 2 Q z Q^z Q z P z P^z P z
( Q z ) i j = U ( i , z ) X k − 2 ( i , j , z − ( k − 2 ) ) , (Q^z)_{ij}=U(i,z)X_{k-2}(i,j,z_{-(k-2)}), ( Q z ) ij = U ( i , z ) X k − 2 ( i , j , z − ( k − 2 ) ) , ( P z ) i j = V ( j , z ) ∏ s = 1 k − 3 X s ( i , j , z − s ) . (P^z)_{ij}=V(j,z)\prod_{s=1}^{k-3}X_s(i,j,z_{-s}). ( P z ) ij = V ( j , z ) s = 1 ∏ k − 3 X s ( i , j , z − s ) . These are n × n n \times n n × n
Δ n ( k ) = ∑ z ⟨ Q z , P z ⟩ \Delta_n^{(k)} = \sum_z \langle Q^z, P^z \rangle Δ n ( k ) = z ∑ ⟨ Q z , P z ⟩ where ⟨ A , B ⟩ = ∑ i , j A i j B i j \langle A,B\rangle= \sum_{i,j} A_{ij}B_{ij} ⟨ A , B ⟩ = ∑ i , j A ij B ij
For a linear map T T T n × n n \times n n × n twisted hyperclique tensor
Δ n , T ( k ) : = ∑ z ⟨ P z , T ⋅ Q z ⟩ . \Delta_{n,T}^{(k)} := \sum_z \langle P^z, T \cdot Q^z \rangle. Δ n , T ( k ) := z ∑ ⟨ P z , T ⋅ Q z ⟩ . We next describe how to rephrase the decomposition Δ n ( k ) = Δ n , I ( k ) = Δ n , L ( k ) + Δ n , H ( k ) \Delta_n^{(k)} = \Delta_{n,I}^{(k)} = \Delta_{n,L}^{(k)} + \Delta_{n,H}^{(k)} Δ n ( k ) = Δ n , I ( k ) = Δ n , L ( k ) + Δ n , H ( k ) L , H L,H L , H I = L + H I = L + H I = L + H
Partial transposes. We will view q d × q d q^d \times q^d q d × q d [ q ] d [q]^d [ q ] d p ∈ [ d ] p \in[d] p ∈ [ d ] τ p \tau_p τ p q d × q d q^d \times q^d q d × q d
τ p ⋅ Q ( a 1 , … , a p , … , a d ) , ( b 1 , … , b p , … , b d ) = Q ( a 1 , … , b p , … , a d ) , ( b 1 , … , a p , … , b d ) . \tau_p \cdot Q_{(a_1,\ldots,a_p,\ldots,a_d),(b_1,\ldots,b_p,\ldots,b_d)}
= Q_{(a_1,\ldots,b_p,\ldots,a_d),(b_1,\ldots,a_p,\ldots,b_d)}. τ p ⋅ Q ( a 1 , … , a p , … , a d ) , ( b 1 , … , b p , … , b d ) = Q ( a 1 , … , b p , … , a d ) , ( b 1 , … , a p , … , b d ) . Note that transpose operators commute with each other, so for A ⊆ [ d ] A \subseteq[d] A ⊆ [ d ] τ A : = ∏ a ∈ A τ a \tau_A := \prod_{a \in A} \tau_a τ A := ∏ a ∈ A τ a τ A \tau_A τ A partial transposes . These operators appear frequently in quantum information theory [53 Section 6.2.3] .
Similar to the analysis of high-degree part in Section 1.3, let’s see how partial transposes allow us to reduce Δ n , τ A ( k ) \Delta_{n,\tau_A}^{(k)} Δ n , τ A ( k ) Δ n ( k − 1 ) \Delta_n^{(k-1)} Δ n ( k − 1 ) Δ n , τ [ d ] ( k ) \Delta_{n,\tau_{[d]}}^{(k)} Δ n , τ [ d ] ( k ) Q z Q^z Q z
Δ n , τ [ d ] ( k ) = ∑ z ⟨ P z , τ [ d ] ⋅ Q z ⟩ = ∑ z ⟨ P z , ( Q z ) T ⟩ = ∑ i , j , z V ( j , z ) ∏ s = 1 k − 3 X s ( i , j , z − s ) ⋅ U ( j , z ) X k − 2 ( j , i , z − ( k − 2 ) ) . \Delta_{n,\tau_{[d]}}^{(k)}
= \sum_z \langle P^z,\tau_{[d]} \cdot Q^z\rangle
= \sum_z \langle P^z,(Q^z)^{\mathsf{T}}\rangle
= \sum_{i,j,z} V(j,z) \prod_{s=1}^{k-3} X_s(i,j,z_{-s}) \cdot U(j,z)X_{k-2}(j,i,z_{-(k-2)}). Δ n , τ [ d ] ( k ) = z ∑ ⟨ P z , τ [ d ] ⋅ Q z ⟩ = z ∑ ⟨ P z , ( Q z ) T ⟩ = i , j , z ∑ V ( j , z ) s = 1 ∏ k − 3 X s ( i , j , z − s ) ⋅ U ( j , z ) X k − 2 ( j , i , z − ( k − 2 ) ) . Now all subscripts involve j j j j j j
Δ n , τ [ d ] ( k ) = ∑ j ∑ i , z V ( j , z ) ∏ s = 1 k − 3 X s ( i , j , z − s ) ⋅ U ( j , z ) X k − 2 ( j , i , z − ( k − 2 ) ) = ∑ j ∑ i , z W ( j , z ) ⋅ X k − 2 ( j , i , z − ( k − 2 ) ) ⋅ ∏ s = 1 k − 3 X s ( i , j , z − s ) . \begin{aligned}
\Delta_{n,\tau_{[d]}}^{(k)}
&= \sum_j \sum_{i,z} V(j,z) \prod_{s=1}^{k-3} X_s(i,j,z_{-s}) \cdot U(j,z)X_{k-2}(j,i,z_{-(k-2)}) \\
&= \sum_j \sum_{i,z} W(j,z) \cdot X_{k-2}(j,i,z_{-(k-2)}) \cdot\prod_{s=1}^{k-3} X_s(i,j,z_{-s}).
\end{aligned} Δ n , τ [ d ] ( k ) = j ∑ i , z ∑ V ( j , z ) s = 1 ∏ k − 3 X s ( i , j , z − s ) ⋅ U ( j , z ) X k − 2 ( j , i , z − ( k − 2 ) ) = j ∑ i , z ∑ W ( j , z ) ⋅ X k − 2 ( j , i , z − ( k − 2 ) ) ⋅ s = 1 ∏ k − 3 X s ( i , j , z − s ) . where W ( j , z ) : = U ( j , z ) V ( j , z ) W(j,z) := U(j,z)V(j,z) W ( j , z ) := U ( j , z ) V ( j , z ) j j j i , z 1 , … , z k − 2 i,z_1,\ldots,z_{k-2} i , z 1 , … , z k − 2 Δ n ( k − 1 ) ( W , X ( 1 ) , … , X ( k − 2 ) ) \Delta_n^{(k-1)}(W,X^{(1)},\ldots,X^{(k-2)}) Δ n ( k − 1 ) ( W , X ( 1 ) , … , X ( k − 2 ) ) j ∈ [ n ] j \in[n] j ∈ [ n ] n k − 2 n^{k-2} n k − 2 W W W Δ n ( k − 1 ) \Delta_n^{(k-1)} Δ n ( k − 1 ) j ∈ [ n ] j \in[n] j ∈ [ n ]
n ⋅ ( n k − 1 − ε + n k − 2 ) = O ( n k − ε ) . n \cdot\left(n^{k-1-\varepsilon} + n^{k-2}\right) = O(n^{k-\varepsilon}). n ⋅ ( n k − 1 − ε + n k − 2 ) = O ( n k − ε ) . Hence, for a full transpose, we inherit the savings n − ε n^{-\varepsilon} n − ε k − 1 k-1 k − 1 τ A \tau_A τ A A A A n = q ∣ A ∣ n = q^{|A|} n = q ∣ A ∣ q − ε ∣ A ∣ q^{-\varepsilon|A|} q − ε ∣ A ∣
Dichotomy. We then rephrase the decomposition in § 1.3 in terms of linear operators by first writing
I = ∏ a ∈ [ d ] ( τ a + ( I − τ a ) ) = ∑ A ⊆ [ d ] ( ∏ a ∈ A τ a ) ( ∏ a ∉ A ( I − τ a ) ) . I=\prod_{a\in[d]}(\tau_a+(I-\tau_a))=\sum_{A\subseteq[d]}\left(\prod_{a\in A}\tau_a\right)\left(\prod_{a\notin A}(I-\tau_a)\right). I = a ∈ [ d ] ∏ ( τ a + ( I − τ a )) = A ⊆ [ d ] ∑ ( a ∈ A ∏ τ a ) a ∈ / A ∏ ( I − τ a ) . For a threshold t t t
L = ∑ ∣ A ∣ ≤ t ( ∏ a ∈ A τ a ) ( ∏ a ∉ A ( I − τ a ) ) (7) L=\sum_{|A|\le t}\left(\prod_{a\in A}\tau_a\right)\left(\prod_{a\notin A}(I-\tau_a)\right) \tag*{(7)} L = ∣ A ∣ ≤ t ∑ ( a ∈ A ∏ τ a ) a ∈ / A ∏ ( I − τ a ) (7) H = ∑ ∣ A ∣ > t ( ∏ a ∈ A τ a ) ( ∏ a ∉ A ( I − τ a ) ) = I − L (8) H=\sum_{|A|>t}\left(\prod_{a\in A}\tau_a\right)\left(\prod_{a\notin A}(I-\tau_a)\right)=I-L \tag*{(8)} H = ∣ A ∣ > t ∑ ( a ∈ A ∏ τ a ) a ∈ / A ∏ ( I − τ a ) = I − L (8) If we expand H H H τ a \tau_a τ a t t t L L L I − τ a I-\tau_a I − τ a d − t d-t d − t
Remark 1. A similar decomposition of the identity matrix (writing I I I [45 ] .
By an extension of the previous argument about the full transpose τ [ d ] \tau_{[d]} τ [ d ] Δ n , H ( k ) \Delta^{(k)}_{n,H} Δ n , H ( k ) t t t d d d t = ⌊ d / B ⌋ t=\lfloor d/B\rfloor t = ⌊ d / B ⌋ Δ n , L ( k ) \Delta^{(k)}_{n,L} Δ n , L ( k )
Low-degree. To compute Δ n , L ( k ) \Delta^{(k)}_{n,L} Δ n , L ( k ) q d × q d q^d\times q^d q d × q d B \mathcal{B} B q × q q\times q q × q
B = { e i i } i ∈ [ q ] ∪ { e i j + e j i , e i j − e j i } 1 ≤ i < j ≤ q . \mathcal{B}=\{e_{ii}\}_{i\in[q]}\cup\{e_{ij}+e_{ji},e_{ij}-e_{ji}\}_{1\le i<j\le q}. B = { e ii } i ∈ [ q ] ∪ { e ij + e j i , e ij − e j i } 1 ≤ i < j ≤ q . Then B ⊗ d \mathcal{B}^{\otimes d} B ⊗ d q d × q d q^d\times q^d q d × q d τ A \tau_A τ A ± 1 \pm1 ± 1 σ = ( σ 1 , … , σ d ) \sigma=(\sigma_1,\ldots,\sigma_d) σ = ( σ 1 , … , σ d ) σ i ∈ B \sigma_i\in\mathcal{B} σ i ∈ B
E σ = ⨂ i ∈ [ d ] σ i . E_\sigma=\bigotimes_{i\in[d]}\sigma_i. E σ = i ∈ [ d ] ⨂ σ i . Note that E σ E_\sigma E σ ± 1 \pm1 ± 1 π i ( σ ) \pi_i(\sigma) π i ( σ ) i i i E σ E_\sigma E σ E σ E_\sigma E σ π j ( σ ) \pi_j(\sigma) π j ( σ ) j j j u ( σ ) u(\sigma) u ( σ ) σ \sigma σ a ( σ ) a(\sigma) a ( σ ) σ \sigma σ a ( σ ) ≤ u ( σ ) a(\sigma)\le u(\sigma) a ( σ ) ≤ u ( σ )
Because B ⊗ d \mathcal{B}^{\otimes d} B ⊗ d L L L
Δ n , L ( k ) = ∑ z ⟨ P z , L Q z ⟩ = ∑ z , σ : a ( σ ) ≥ d − t c σ ⟨ P z , E σ ⟩ ⟨ Q z , E σ ⟩ . \Delta^{(k)}_{n,L}=\sum_z\langle P^z,LQ^z\rangle=\sum_{z,\sigma:a(\sigma)\ge d-t}c_\sigma\langle P^z,E_\sigma\rangle\langle Q^z,E_\sigma\rangle. Δ n , L ( k ) = z ∑ ⟨ P z , L Q z ⟩ = z , σ : a ( σ ) ≥ d − t ∑ c σ ⟨ P z , E σ ⟩ ⟨ Q z , E σ ⟩ . for some (explicit) constants c σ c_\sigma c σ a ( σ ) < d − t a(\sigma)<d-t a ( σ ) < d − t
P σ , z : = ⟨ P z , E σ ⟩ , Q σ , z : = ⟨ Q z , E σ ⟩ P_{\sigma,z}:=\langle P^z,E_\sigma\rangle,\qquad Q_{\sigma,z}:=\langle Q^z,E_\sigma\rangle P σ , z := ⟨ P z , E σ ⟩ , Q σ , z := ⟨ Q z , E σ ⟩ for all σ , z \sigma,z σ , z Q Q Q
Q σ , z = ∑ i : row i ( E σ ) ≠ 0 ( Q z ) i , π i ( σ ) ( E σ ) i , π i ( σ ) = ∑ i : row i ( E σ ) ≠ 0 ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z − ( k − 2 ) ) U ( i , z ) . (9) Q_{\sigma,z}=\sum_{i:\operatorname{row}_i(E_\sigma)\ne0}(Q^z)_{i,\pi_i(\sigma)}(E_\sigma)_{i,\pi_i(\sigma)}
=\sum_{i:\operatorname{row}_i(E_\sigma)\ne0}(E_\sigma)_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z_{-(k-2)})U(i,z). \tag*{(9)} Q σ , z = i : row i ( E σ ) = 0 ∑ ( Q z ) i , π i ( σ ) ( E σ ) i , π i ( σ ) = i : row i ( E σ ) = 0 ∑ ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z − ( k − 2 ) ) U ( i , z ) . (9) Attempt #1. Since E σ E_{\sigma} E σ 2 u ( σ ) ≤ 2 d ≤ n 2^{u(\sigma)} \le2^d \le n 2 u ( σ ) ≤ 2 d ≤ n Q σ , z Q_{\sigma,z} Q σ , z
∑ z , σ : a ( σ ) ≥ d − t ∥ E σ ∥ 0 = ∑ z , σ : a ( σ ) ≥ d − t 2 u ( σ ) = n k − 2 ∑ σ : a ( σ ) ≥ d − t 2 u ( σ ) \sum_{z,\sigma:a(\sigma)\ge d-t}\lVert E_{\sigma}\rVert_0
=
\sum_{z,\sigma:a(\sigma)\ge d-t}2^{u(\sigma)}
=
n^{k-2}\sum_{\sigma:a(\sigma)\ge d-t}2^{u(\sigma)} z , σ : a ( σ ) ≥ d − t ∑ ∥ E σ ∥ 0 = z , σ : a ( σ ) ≥ d − t ∑ 2 u ( σ ) = n k − 2 σ : a ( σ ) ≥ d − t ∑ 2 u ( σ ) operations. Unfortunately, just the contribution to this sum for the σ \sigma σ a ( σ ) = d − t a(\sigma)=d-t a ( σ ) = d − t
( d d − t ) [ 2 ( q 2 ) ] d − t [ 2 ( q 2 ) + q ] t ≈ ( d t ) n 2 \binom{d}{d-t}\left[2\binom{q}{2}\right]^{d-t}\left[2\binom{q}{2}+q\right]^t
\approx\binom{d}{t}n^2 ( d − t d ) [ 2 ( 2 q ) ] d − t [ 2 ( 2 q ) + q ] t ≈ ( t d ) n 2 which is polynomially larger than n 2 n^2 n 2 t t t d d d
However, note that there is redundant computation: many Q σ , z Q_{\sigma,z} Q σ , z Q z Q^z Q z (9) individually for each choice of σ \sigma σ z z z
Attempt #2. Let z = ( z ′ , w ) z=(z',w) z = ( z ′ , w ) Q σ , z Q_{\sigma,z} Q σ , z z ′ z' z ′ w w w σ \sigma σ a ( σ ) ≥ d − t a(\sigma)\ge d-t a ( σ ) ≥ d − t
Q σ , ( z ′ , w ) = ∑ i : row i ( E σ ) ≠ 0 ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) . (10) Q_{\sigma,(z',w)}
=
\sum_{i:\operatorname{row}_i(E_{\sigma})\ne0}
(E_{\sigma})_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z')U(i,z',w). \tag*{(10)} Q σ , ( z ′ , w ) = i : row i ( E σ ) = 0 ∑ ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) . (10) After fixing z ′ z' z ′ Q σ , ( z ′ , w ) Q_{\sigma,(z',w)} Q σ , ( z ′ , w ) σ , w \sigma,w σ , w
( ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) ) σ , i ⋅ ( U ( i , z ′ , w ) ) i , w . \left((E_{\sigma})_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z')\right)_{\sigma,i}
\cdot
\left(U(i,z',w)\right)_{i,w}. ( ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) ) σ , i ⋅ ( U ( i , z ′ , w ) ) i , w . How fast should we compute this matrix multiplication in order to get an improvement? The catch is that this matrix multiplication problem is a sparse instance — the first matrix ( ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) ) σ , i \left((E_{\sigma})_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z')\right)_{\sigma,i} ( ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) ) σ , i σ \sigma σ 2 u ( σ ) 2^{u(\sigma)} 2 u ( σ ) ( U ( i , z ′ , w ) ) i , w \left(U(i,z',w)\right)_{i,w} ( U ( i , z ′ , w ) ) i , w
Similar to the estimate of the number of terms in the previous attempt, when we take t = d / B t=d/B t = d / B m = n 2 + o ( 1 / B ) m=n^{2+o(1/B)} m = n 2 + o ( 1/ B ) m ⋅ n = n 3 + o ( 1 / B ) m\cdot n=n^{3+o(1/B)} m ⋅ n = n 3 + o ( 1/ B ) z ′ ∈ [ n ] k − 3 z'\in[n]^{k-3} z ′ ∈ [ n ] k − 3
To compute the matrix multiplication faster, we can partition the first matrix into many dense matrices. Suppose we can find a set S S S σ \sigma σ J J J σ ∈ S \sigma\in S σ ∈ S i ∈ J i\in J i ∈ J (10) by performing a ∣ S ∣ × ∣ J ∣ × n |S|\times|J|\times n ∣ S ∣ × ∣ J ∣ × n partition the first matrix this way, such that ∣ S ∣ , ∣ J ∣ = n Ω k ( 1 ) |S|,|J|=n^{\Omega_k(1)} ∣ S ∣ , ∣ J ∣ = n Ω k ( 1 )
To formalize this partitioning, we consider the graph G G G σ \sigma σ a ( σ ) ≥ d − t a(\sigma)\ge d-t a ( σ ) ≥ d − t [ n ] [n] [ n ] E σ E_{\sigma} E σ σ ∼ i \sigma\sim i σ ∼ i i i i E σ E_{\sigma} E σ E ( G ) E(G) E ( G ) n n n Lemma 7 . See Figure 2 for an illustration.
Figure 2. Computing the Q σ , ( z ′ , w ) Q_{\sigma,(z',w)} Q σ , ( z ′ , w ) z ′ z' z ′
To handle the P P P E σ E_\sigma E σ G G G
P σ , z = ∑ j : ( σ , j ) ∈ E ( G ) ( E σ ) π j ( σ ) , j V ( j , z ) ∏ s = 1 k − 3 X s ( π j ( σ ) , j , z − s ) . P_{\sigma,z} = \sum_{j:(\sigma,j)\in E(G)} (E_\sigma)_{\pi_j(\sigma),j}V(j,z)\prod_{s=1}^{k-3}X_s(\pi_j(\sigma),j,z_{-s}). P σ , z = j : ( σ , j ) ∈ E ( G ) ∑ ( E σ ) π j ( σ ) , j V ( j , z ) s = 1 ∏ k − 3 X s ( π j ( σ ) , j , z − s ) . First, note that after fixing w w w ( k − 1 ) (k-1) ( k − 1 ) k − 1 k-1 k − 1 σ \sigma σ j j j z ′ z' z ′ V V V σ \sigma σ X s X_s X s z ′ z' z ′ ( E σ ) π j ( σ ) , j (E_\sigma)_{\pi_j(\sigma),j} ( E σ ) π j ( σ ) , j X s X_s X s k − 2 k-2 k − 2 j j j P σ , z P_{\sigma,z} P σ , z P σ , z P_{\sigma,z} P σ , z Y ( σ , z ′ , w ) Y(\sigma,z',w) Y ( σ , z ′ , w ) σ , z ′ \sigma,z' σ , z ′
Φ w : = ∑ σ , z ′ P σ , z Y ( σ , z ′ , w ) \Phi_w := \sum_{\sigma,z'} P_{\sigma,z}Y(\sigma,z',w) Φ w := σ , z ′ ∑ P σ , z Y ( σ , z ′ , w ) This becomes the evaluation of a ( k − 1 ) (k-1) ( k − 1 ) [16 ] tells us that there is an equivalence between evaluating Φ w \Phi_w Φ w Y Y Y P σ , z P_{\sigma,z} P σ , z
We will use our inductive hypothesis to construct a small circuit for Φ w \Phi_w Φ w all such P σ , z P_{\sigma,z} P σ , z Q Q Q j j j σ \sigma σ
To finish, we choose the degree threshold t t t d d d Z [ 1 / 2 ] \mathbb{Z}[1/2] Z [ 1/2 ] a / 2 b a/2^b a / 2 b a a a b b b
Preliminaries
We will only need the following simple fact about fast matrix multiplication.
Lemma 1. Let ℓ = min ( n 1 , n 2 , n 3 ) \ell= \min(n_1,n_2,n_3) ℓ = min ( n 1 , n 2 , n 3 ) n 1 × n 2 n_1 \times n_2 n 1 × n 2 n 2 × n 3 n_2 \times n_3 n 2 × n 3 O ( ( n 1 n 2 n 3 ) ⋅ ℓ − γ ) O((n_1n_2n_3) \cdot\ell^{-\gamma}) O (( n 1 n 2 n 3 ) ⋅ ℓ − γ ) γ ≥ 1 / 8 \gamma\ge1/8 γ ≥ 1/8
Proof. By blocking our input matrices into ℓ × ℓ \ell\times\ell ℓ × ℓ n 1 n 2 n 3 / ℓ 3 n_1n_2n_3/\ell^3 n 1 n 2 n 3 / ℓ 3 ℓ × ℓ \ell\times\ell ℓ × ℓ O ( ℓ log 2 7 ) O(\ell^{\log_2 7}) O ( ℓ l o g 2 7 ) γ = 3 − log 2 7 > 1 / 8 \gamma= 3 - \log_2 7 > 1/8 γ = 3 − log 2 7 > 1/8 γ \gamma γ
We will also use the following generalization of Lemma 1 to the hyperclique tensor. For a tensor T T T C ( T ) \mathrm{C}(T) C ( T ) n 1 × n 2 × ⋯ × n k n_1 \times n_2 \times\cdots\times n_k n 1 × n 2 × ⋯ × n k
Δ ( n 1 , … , n k ) ( k ) : = ∑ α ∈ [ n 1 ] × [ n 2 ] × ⋯ × [ n k ] ∏ j = 1 k x α − j ( j ) . \Delta^{(k)}_{(n_1,\ldots,n_k)} := \sum_{\alpha\in[n_1]\times[n_2]\times\cdots\times[n_k]} \prod_{j=1}^{k} x^{(j)}_{\alpha_{-j}}. Δ ( n 1 , … , n k ) ( k ) := α ∈ [ n 1 ] × [ n 2 ] × ⋯ × [ n k ] ∑ j = 1 ∏ k x α − j ( j ) . Write Δ n ( k ) \Delta^{(k)}_n Δ n ( k ) Δ n ( k ) : = Δ ( n , n , … , n ) ( k ) \Delta^{(k)}_n := \Delta^{(k)}_{(n,n,\ldots,n)} Δ n ( k ) := Δ ( n , n , … , n ) ( k )
Lemma 2. For ℓ ≤ min i ∈ [ k ] n i \ell\le\min_{i\in[k]} n_i ℓ ≤ min i ∈ [ k ] n i Δ ( n 1 , … , n k ) ( k ) \Delta^{(k)}_{(n_1,\ldots,n_k)} Δ ( n 1 , … , n k ) ( k ) C ( Δ ℓ ( k ) ) ⋅ ∏ i = 1 k ⌈ n i / ℓ ⌉ \mathrm{C}(\Delta^{(k)}_\ell) \cdot\prod_{i=1}^{k} \lceil n_i/\ell\rceil C ( Δ ℓ ( k ) ) ⋅ ∏ i = 1 k ⌈ n i / ℓ ⌉
Proof. Partition each index set [ n i ] [n_i] [ n i ] n i ′ : = ⌈ n i / ℓ ⌉ n'_i := \lceil n_i/\ell\rceil n i ′ := ⌈ n i / ℓ ⌉ ℓ \ell ℓ P i , 1 , … , P i , n i ′ P_{i,1},\ldots,P_{i,n'_i} P i , 1 , … , P i , n i ′
Δ ( n 1 , … , n k ) ( k ) = ∑ ( i 1 , … , i k ) ∈ [ n 1 ′ ] × ⋯ × [ n k ′ ] ∑ J ∈ P 1 , i 1 × ⋯ × P k , i k ∏ s = 1 k x J − s ( s ) . \Delta^{(k)}_{(n_1,\ldots,n_k)}
=
\sum_{(i_1,\ldots,i_k)\in[n'_1]\times\cdots\times[n'_k]}
\sum_{J\in P_{1,i_1}\times\cdots\times P_{k,i_k}}
\prod_{s=1}^{k} x^{(s)}_{J_{-s}}. Δ ( n 1 , … , n k ) ( k ) = ( i 1 , … , i k ) ∈ [ n 1 ′ ] × ⋯ × [ n k ′ ] ∑ J ∈ P 1 , i 1 × ⋯ × P k , i k ∑ s = 1 ∏ k x J − s ( s ) . For each fixed choice of i 1 , … , i k i_1,\ldots,i_k i 1 , … , i k J J J Δ ℓ ( k ) \Delta^{(k)}_\ell Δ ℓ ( k )
We will also make use of the Baur–Strassen theorem, which converts a circuit for computing a polynomial into one that computes its partial derivatives.
Lemma 3 ([16 , 39 ] ). Suppose a polynomial P ( x 1 , … , x n ) P(x_1,\ldots,x_n) P ( x 1 , … , x n ) s s s 4 ⋅ s 4 \cdot s 4 ⋅ s ∂ P ∂ x i \frac{\partial P}{\partial x_i} ∂ x i ∂ P i ∈ [ n ] i \in[n] i ∈ [ n ] P P P O ( s ) O(s) O ( s )
Small arithmetic circuits for ( k ) n (k)n ( k ) n
In this section, we follow the overview (§ 1.4 ) to prove our main result via the following inductive step:
Theorem 6. Fix k ≥ 4 k \ge4 k ≥ 4 ε ∈ ( 0 , 1 / 8 ] \varepsilon\in(0,1/8] ε ∈ ( 0 , 1/8 ] ( k − 1 ) (k-1) ( k − 1 ) O ( n k − 1 − ε ) O(n^{k-1-\varepsilon}) O ( n k − 1 − ε ) n n n B ≥ 16 B \ge16 B ≥ 16 2 ε B ≥ ( e B ) 2 2^{\varepsilon B} \ge(eB)^2 2 εB ≥ ( e B ) 2 k k k O ( n k − ε / ( 4 B ) ) O(n^{k-\varepsilon/(4B)}) O ( n k − ε / ( 4 B ) )
We then appeal to the base case that Δ n ( 3 ) \Delta_n^{(3)} Δ n ( 3 ) n ω + o ( 1 ) n^{\omega+o(1)} n ω + o ( 1 ) ω < 3 \omega< 3 ω < 3
Reminder of Theorem 1. For every fixed k ≥ 3 k \ge3 k ≥ 3 k k k Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) O ( n k − ε k ) O(n^{k-\varepsilon_k}) O ( n k − ε k ) ε k = 2 − Θ ( 2 k ) \varepsilon_k = 2^{-\Theta(2^k)} ε k = 2 − Θ ( 2 k ) Z [ 1 / 2 ] \mathbb{Z}[1/2] Z [ 1/2 ] ( 1 n , 1 k ) (1^n,1^k) ( 1 n , 1 k ) O ( n k − ε k ) O(n^{k-\varepsilon_k}) O ( n k − ε k ) n k − ε k + o ( 1 ) n^{k-\varepsilon_k+o(1)} n k − ε k + o ( 1 )
Setup
We begin by introducing parameters and recalling the setup of the proof overview. Throughout this section, fix k k k ε \varepsilon ε k − 1 k-1 k − 1 B ≥ 16 B \ge16 B ≥ 16 2 ε B ≥ ( e B ) 2 2^{\varepsilon B} \ge(eB)^2 2 εB ≥ ( e B ) 2
q = 2 B , t = ⌊ d / B ⌋ . q = 2^B,\qquad t = \lfloor d/B \rfloor. q = 2 B , t = ⌊ d / B ⌋ . We assume that n n n q d q^d q d q q q
Label the k k k ( i , j , z 1 , … , z k − 2 ) ∈ [ n ] k (i,j,z_1,\ldots,z_{k-2}) \in[n]^k ( i , j , z 1 , … , z k − 2 ) ∈ [ n ] k U ( i , z ) U(i,z) U ( i , z ) V ( j , z ) V(j,z) V ( j , z ) X s ( i , j , z − s ) X_s(i,j,z_{-s}) X s ( i , j , z − s ) i , j ∈ [ n ] i,j \in[n] i , j ∈ [ n ] z ∈ [ n ] k − 2 z \in[n]^{k-2} z ∈ [ n ] k − 2 s ∈ [ k − 2 ] s \in[k-2] s ∈ [ k − 2 ]
Δ n ( k ) = ∑ i , j ∈ [ n ] , z ∈ [ n ] k − 2 U ( i , z ) V ( j , z ) ∏ s = 1 k − 2 X s ( i , j , z − s ) . \Delta_n^{(k)} = \sum_{\substack{i,j \in[n],z \in[n]^{k-2}}} U(i,z)V(j,z)\prod_{s=1}^{k-2} X_s(i,j,z_{-s}). Δ n ( k ) = i , j ∈ [ n ] , z ∈ [ n ] k − 2 ∑ U ( i , z ) V ( j , z ) s = 1 ∏ k − 2 X s ( i , j , z − s ) . Define matrices Q z Q^z Q z P z P^z P z
( Q z ) i j = U ( i , z ) X k − 2 ( i , j , z − ( k − 2 ) ) , ( P z ) i j = V ( j , z ) ∏ s = 1 k − 3 X s ( i , j , z − s ) . (Q^z)_{ij} = U(i,z)X_{k-2}(i,j,z_{-(k-2)}),\qquad(P^z)_{ij} = V(j,z)\prod_{s=1}^{k-3} X_s(i,j,z_{-s}). ( Q z ) ij = U ( i , z ) X k − 2 ( i , j , z − ( k − 2 ) ) , ( P z ) ij = V ( j , z ) s = 1 ∏ k − 3 X s ( i , j , z − s ) . We recall the transpose operators, which are instrumental to the decomposition of the identity matrix described in § 1.4 above. View q d × q d q^d \times q^d q d × q d [ q ] d [q]^d [ q ] d p ∈ [ d ] p \in[d] p ∈ [ d ] τ p \tau_p τ p q d × q d q^d \times q^d q d × q d
τ p ⋅ Q ( a 1 , … , a p , … , a d ) , ( b 1 , … , b p , … , b d ) = Q ( a 1 , … , b p , … , a d ) , ( b 1 , … , a p , … , b d ) . \tau_p \cdot Q_{(a_1,\ldots,a_p,\ldots,a_d),(b_1,\ldots,b_p,\ldots,b_d)}
= Q_{(a_1,\ldots,b_p,\ldots,a_d),(b_1,\ldots,a_p,\ldots,b_d)}. τ p ⋅ Q ( a 1 , … , a p , … , a d ) , ( b 1 , … , b p , … , b d ) = Q ( a 1 , … , b p , … , a d ) , ( b 1 , … , a p , … , b d ) . Let B \mathcal{B} B q × q q \times q q × q
B = { e i i } i ∈ [ q ] ∪ { e i j + e j i , e i j − e j i } 1 ≤ i < j ≤ q . \mathcal{B} = \{e_{ii}\}_{i\in[q]} \cup\{e_{ij}+e_{ji},e_{ij}-e_{ji}\}_{1\le i<j\le q}. B = { e ii } i ∈ [ q ] ∪ { e ij + e j i , e ij − e j i } 1 ≤ i < j ≤ q . Then B ⊗ d \mathcal{B}^{\otimes d} B ⊗ d n × n n \times n n × n σ = ( σ 1 , … , σ d ) \sigma=(\sigma_1,\ldots,\sigma_d) σ = ( σ 1 , … , σ d ) σ i ∈ B \sigma_i\in\mathcal{B} σ i ∈ B E σ = ⨂ i ∈ [ d ] σ i E_\sigma=\bigotimes_{i\in[d]}\sigma_i E σ = ⨂ i ∈ [ d ] σ i π i ( σ ) \pi_i(\sigma) π i ( σ ) i i i E σ E_\sigma E σ E σ E_\sigma E σ π j ( σ ) \pi_j(\sigma) π j ( σ ) j j j u ( σ ) u(\sigma) u ( σ ) σ \sigma σ a ( σ ) a(\sigma) a ( σ ) σ \sigma σ a ( σ ) ≤ u ( σ ) a(\sigma)\leq u(\sigma) a ( σ ) ≤ u ( σ )
The following are immediate:
Lemma 4. 1. ⟨ E σ , E σ ′ ⟩ = 0 \langle E_\sigma,E_{\sigma'}\rangle=0 ⟨ E σ , E σ ′ ⟩ = 0 σ ≠ σ ′ \sigma\ne\sigma' σ = σ ′ 2 u ( σ ) 2^{u(\sigma)} 2 u ( σ )
τ p E σ = E σ \tau_pE_\sigma=E_\sigma τ p E σ = E σ σ p \sigma_p σ p τ p E σ = − E σ \tau_pE_\sigma=-E_\sigma τ p E σ = − E σ σ p \sigma_p σ p
( I − τ p ) E σ = 0 (I-\tau_p)E_\sigma=0 ( I − τ p ) E σ = 0 σ p \sigma_p σ p ( I − τ p ) E σ = 2 E σ (I-\tau_p)E_\sigma=2E_\sigma ( I − τ p ) E σ = 2 E σ σ p \sigma_p σ p
Define the low and high degree operators
L = ∑ ∣ A ∣ ≤ t ( ∏ a ∈ A τ a ) ( ∏ a ∉ A ( I − τ a ) ) , H = ∑ ∣ A ∣ > t ( ∏ a ∈ A τ a ) ( ∏ a ∉ A ( I − τ a ) ) L=\sum_{|A|\leq t}\left(\prod_{a\in A}\tau_a\right)\left(\prod_{a\notin A}(I-\tau_a)\right),\qquad H=\sum_{|A|>t}\left(\prod_{a\in A}\tau_a\right)\left(\prod_{a\notin A}(I-\tau_a)\right) L = ∣ A ∣ ≤ t ∑ ( a ∈ A ∏ τ a ) a ∈ / A ∏ ( I − τ a ) , H = ∣ A ∣ > t ∑ ( a ∈ A ∏ τ a ) a ∈ / A ∏ ( I − τ a ) recalling that t = ⌊ d / B ⌋ t=\lfloor d/B\rfloor t = ⌊ d / B ⌋
For a linear map T T T n × n n\times n n × n
Δ n , T ( k ) : = ∑ z ⟨ P z , T ⋅ Q z ⟩ \Delta_{n,T}^{(k)}:=\sum_z\langle P^z,T\cdot Q^z\rangle Δ n , T ( k ) := z ∑ ⟨ P z , T ⋅ Q z ⟩ Then Δ n ( k ) = Δ n , L ( k ) + Δ n , H ( k ) \Delta_n^{(k)}=\Delta_{n,L}^{(k)}+\Delta_{n,H}^{(k)} Δ n ( k ) = Δ n , L ( k ) + Δ n , H ( k )
We first give a circuit for Δ n , H ( k ) \Delta_{n,H}^{(k)} Δ n , H ( k ) § 3.2 ), then give a circuit for Δ n , L ( k ) \Delta_{n,L}^{(k)} Δ n , L ( k ) § 3.3 ), and finally combine them (proving Theorem 6 in § 3.4 ).
High-degree
We begin by looking at the result of applying a particular partial transpose τ A \tau_A τ A
Lemma 5. Δ n , τ A ( k ) \Delta_{n,\tau_A}^{(k)} Δ n , τ A ( k ) O ( n k q − ε ∣ A ∣ ) O(n^kq^{-\varepsilon|A|}) O ( n k q − ε ∣ A ∣ )
Proof. To make the effects of the partial transpose a bit clearer, we introduce the following notation: write i = ( i A , i A ‾ ) i=(i_A,i_{\overline{A}}) i = ( i A , i A ) j = ( j A , j A ‾ ) j=(j_A,j_{\overline{A}}) j = ( j A , j A ) i ∗ = ( j A , i A ‾ ) i^*=(j_A,i_{\overline{A}}) i ∗ = ( j A , i A ) j ∗ = ( i A , j A ‾ ) j^*=(i_A,j_{\overline{A}}) j ∗ = ( i A , j A )
( τ A ⋅ Q ) ( i A , i A ‾ ) , ( j A , j A ‾ ) = Q ( j A , i A ‾ ) , ( i A , j A ‾ ) = Q i ∗ , j ∗ . (\tau_A\cdot Q)_{(i_A,i_{\overline{A}}),(j_A,j_{\overline{A}})}=Q_{(j_A,i_{\overline{A}}),(i_A,j_{\overline{A}})}=Q_{i^*,j^*}. ( τ A ⋅ Q ) ( i A , i A ) , ( j A , j A ) = Q ( j A , i A ) , ( i A , j A ) = Q i ∗ , j ∗ . By definition of Δ n , τ A ( k ) \Delta_{n,\tau_A}^{(k)} Δ n , τ A ( k ) P z P^z P z Q z Q^z Q z
\begin{aligned}
\Delta_{n,\tau_A}^{(k)}
&=\sum_z\langle P^z,\tau_A\cdot Q^z\rangle
=\sum_z\sum_{i,j}(P^z)_{ij}(Q^z)_{i^*,j^*}\\
&=\sum_{z,i,j}\left(V_{j,z}\prod_{s=1}^{k-3}X_s(i,j,z_{-s})\right)\left(U_{i^*,z}X_{k-2}(i^*,j^*,z_{-(k-2)})\right)\\
&=\sum_{j_A,j_{\overline{A}}}\sum_{z,i_A}\left(V_{j,z}U_{j_A,i_{\overline{A},z}\right)X_{k-2}(i^*,j^*,z_{-(k-2)})\cdot\prod_{s=1}^{k-3}X_s(i,j,z_{-s}).
\end{aligned}}
The key point is that the partial transpose replaces U U U i A i_A i A j A j_A j A j j j i A ‾ i_{\overline{A}} i A U U U V V V z z z k k k k − 1 k-1 k − 1
For each choice of j A , j A ‾ , i A ‾ j_A,j_{\overline{A}},i_{\overline{A}} j A , j A , i A n 2 / q ∣ A ∣ n^2/q^{|A|} n 2 / q ∣ A ∣ ( k − 1 ) (k-1) ( k − 1 ) [ q ∣ A ∣ ] × [ n ] × ⋯ × [ n ] [q^{|A|}] \times[n] \times\cdots\times[n] [ q ∣ A ∣ ] × [ n ] × ⋯ × [ n ]
( V j , z U j A , i A ‾ , z ) z , ( X k − 2 ( i ∗ , j ∗ , z − ( k − 2 ) ) ) i A , z − ( k − 2 ) , ( X s ( i , j , z − s ) ) i A , z − s , s ∈ [ k − 3 ] . (V_{j,z}U_{j_A,i_{\overline{A}},z})_z,\quad(X_{k-2}(i^*,j^*,z_{-(k-2)}))_{i_A,z_{-(k-2)}},\quad(X_s(i,j,z_{-s}))_{i_A,z_{-s}},\ s \in[k-3]. ( V j , z U j A , i A , z ) z , ( X k − 2 ( i ∗ , j ∗ , z − ( k − 2 ) ) ) i A , z − ( k − 2 ) , ( X s ( i , j , z − s ) ) i A , z − s , s ∈ [ k − 3 ] . By Lemma 2, and using n k − 2 n^{k-2} n k − 2 ( V j , z U j A , i A ‾ , z ) (V_{j,z}U_{j_A,i_{\overline{A}},z}) ( V j , z U j A , i A , z ) z ∈ [ n ] k − 2 z \in[n]^{k-2} z ∈ [ n ] k − 2
( n / q ∣ A ∣ ) k − 2 ⋅ q ∣ A ∣ ( k − 1 − ε ) + n k − 2 = O ( n k − 2 q ( 1 − ε ) ∣ A ∣ ) . (n/q^{|A|})^{k-2}\cdot q^{|A|(k-1-\varepsilon)}+n^{k-2}=O(n^{k-2}q^{(1-\varepsilon)|A|}). ( n / q ∣ A ∣ ) k − 2 ⋅ q ∣ A ∣ ( k − 1 − ε ) + n k − 2 = O ( n k − 2 q ( 1 − ε ) ∣ A ∣ ) . Summing over all j , i A ‾ j,i_{\overline{A}} j , i A
Thus, whenever ∣ A ∣ |A| ∣ A ∣ q − ε ∣ A ∣ q^{-\varepsilon|A|} q − ε ∣ A ∣ n n n
Corollary 1. Δ n , H ( k ) \Delta_{n,H}^{(k)} Δ n , H ( k ) O ( n k − ε / ( 2 B ) ) O(n^{k-\varepsilon/(2B)}) O ( n k − ε / ( 2 B ) )
Proof. We have that
Δ n , H ( k ) = ∑ ∣ A ∣ > ⌊ d / B ⌋ c A Δ n , τ A ( k ) . \Delta_{n,H}^{(k)}=\sum_{|A|>\lfloor d/B\rfloor}c_A\Delta_{n,\tau_A}^{(k)}. Δ n , H ( k ) = ∣ A ∣ > ⌊ d / B ⌋ ∑ c A Δ n , τ A ( k ) . where the integers c A c_A c A ∣ c A ∣ ≤ 2 ∣ A ∣ |c_A|\le2^{|A|} ∣ c A ∣ ≤ 2 ∣ A ∣ ∏ a ∉ A ( I − τ a ) \prod_{a\notin A}(I-\tau_a) ∏ a ∈ / A ( I − τ a ) H H H Δ n , H ( k ) \Delta_{n,H}^{(k)} Δ n , H ( k )
n k ∑ a > ⌊ d / B ⌋ ( d a ) ⋅ 2 − B ε a . n^k\sum_{a>\lfloor d/B\rfloor}\binom{d}{a}\cdot2^{-B\varepsilon a}. n k a > ⌊ d / B ⌋ ∑ ( a d ) ⋅ 2 − B ε a . We have ( d a ) ≤ ( e d a ) a < ( e B ) a \binom{d}{a}\le\left(\frac{ed}{a}\right)^a<(eB)^a ( a d ) ≤ ( a e d ) a < ( e B ) a B B B 2 ε B ≥ ( e B ) 2 2^{\varepsilon B}\ge(eB)^2 2 εB ≥ ( e B ) 2 ( d a ) ≤ 2 ε B a / 2 \binom{d}{a}\le2^{\varepsilon Ba/2} ( a d ) ≤ 2 εB a /2
n k ∑ a > ⌊ d / B ⌋ 2 − ε B a / 2 ≤ n k ⋅ 2 − ε d / 2 ⋅ 1 1 − 2 − ε B / 2 ≤ n k ⋅ 2 − ε d / 2 ⋅ 1 1 − ( e B ) − 1 = O ( n k ⋅ 2 − ε d / 2 ) . n^k\sum_{a>\lfloor d/B\rfloor}2^{-\varepsilon Ba/2}\le n^k\cdot2^{-\varepsilon d/2}\cdot\frac{1}{1-2^{-\varepsilon B/2}}\le n^k\cdot2^{-\varepsilon d/2}\cdot\frac{1}{1-(eB)^{-1}}=O(n^k\cdot2^{-\varepsilon d/2}). n k a > ⌊ d / B ⌋ ∑ 2 − εB a /2 ≤ n k ⋅ 2 − ε d /2 ⋅ 1 − 2 − εB /2 1 ≤ n k ⋅ 2 − ε d /2 ⋅ 1 − ( e B ) − 1 1 = O ( n k ⋅ 2 − ε d /2 ) . The first inequality comes from the fact that the sum is a geometric series in a a a 2 − ε B ( ⌊ d / B ⌋ + 1 ) / 2 < 2 − ε d / 2 2^{-\varepsilon B(\lfloor d/B\rfloor+1)/2}<2^{-\varepsilon d/2} 2 − εB (⌊ d / B ⌋ + 1 ) /2 < 2 − ε d /2 2 − ε B / 2 2^{-\varepsilon B/2} 2 − εB /2 B B B n = 2 B d n=2^{Bd} n = 2 B d O ( n k − ε / ( 2 B ) ) O(n^{k-\varepsilon/(2B)}) O ( n k − ε / ( 2 B ) )
Low-degree
Throughout this section, we will consider the following graph to understand (and eventually, block) the contribution of the low-degree part. Let G G G σ ∈ B ⊗ d \sigma\in\mathcal{B}^{\otimes d} σ ∈ B ⊗ d a ( σ ) a(\sigma) a ( σ ) d − t = d − ⌊ d / B ⌋ d-t=d-\lfloor d/B\rfloor d − t = d − ⌊ d / B ⌋ i ∈ [ n ] i\in[n] i ∈ [ n ] ( σ , i ) (\sigma,i) ( σ , i ) i i i E σ E_\sigma E σ ( σ , j ) (\sigma,j) ( σ , j ) j j j m = ∣ E ( G ) ∣ m=|E(G)| m = ∣ E ( G ) ∣
Lemma 6. The number of edges in G G G O ( n 2 + ε / ( 2 B ) ) O(n^{2+\varepsilon/(2B)}) O ( n 2 + ε / ( 2 B ) )
Proof. Each basis element E σ E_\sigma E σ 2 u ( σ ) 2^{u(\sigma)} 2 u ( σ ) 2 u ( σ ) 2^{u(\sigma)} 2 u ( σ ) ∑ σ : a ( σ ) ≥ d − t 2 u ( σ ) \sum_{\sigma:a(\sigma)\ge d-t}2^{u(\sigma)} ∑ σ : a ( σ ) ≥ d − t 2 u ( σ ) σ \sigma σ a ( σ ) = α a(\sigma)=\alpha a ( σ ) = α ( d α ) \binom{d}{\alpha} ( α d ) ( q 2 ) \binom{q}{2} ( 2 q ) 2 2 2 ( q 2 ) \binom{q}{2} ( 2 q ) q q q 2 2 2
[ 2 ( q 2 ) ] α ⋅ [ 2 ( q 2 ) + q ] d − α ≤ q 2 d = n 2 . \left[2\binom{q}{2}\right]^\alpha\cdot\left[2\binom{q}{2}+q\right]^{d-\alpha}\le q^{2d}=n^2. [ 2 ( 2 q ) ] α ⋅ [ 2 ( 2 q ) + q ] d − α ≤ q 2 d = n 2 . Therefore, the number of edges in G G G
n 2 ∑ α = d − t d ( d α ) ≤ n 2 ∑ i = 0 t ( d i ) ≤ n 2 B d / B ∑ i = 0 d ( d i ) B − i ≤ n 2 B d / B ( 1 + 1 B ) d ≤ n 2 ( e B ) d / B . n^2\sum_{\alpha=d-t}^{d}\binom{d}{\alpha}\le n^2\sum_{i=0}^{t}\binom{d}{i}\le n^2B^{d/B}\sum_{i=0}^{d}\binom{d}{i}B^{-i}\le n^2B^{d/B}\left(1+\frac{1}{B}\right)^d\le n^2(eB)^{d/B}. n 2 α = d − t ∑ d ( α d ) ≤ n 2 i = 0 ∑ t ( i d ) ≤ n 2 B d / B i = 0 ∑ d ( i d ) B − i ≤ n 2 B d / B ( 1 + B 1 ) d ≤ n 2 ( e B ) d / B . The first inequality results from taking i = d − α i=d-\alpha i = d − α α \alpha α t ≤ d / B t\le d/B t ≤ d / B B d / B − i ≥ 1 B^{d/B-i}\ge1 B d / B − i ≥ 1 i ≤ t i\le t i ≤ t 1 + x ≤ e x 1+x\le e^x 1 + x ≤ e x x = 1 / B x=1/B x = 1/ B ( e B ) 2 ≤ 2 ε B (eB)^2\le2^{\varepsilon B} ( e B ) 2 ≤ 2 εB n = 2 B d n=2^{Bd} n = 2 B d
∣ E ( G ) ∣ ≤ n 2 2 ε d / 2 ≤ n 2 + ε / ( 2 B ) , |E(G)|\le n^2 2^{\varepsilon d/2}\le n^{2+\varepsilon/(2B)}, ∣ E ( G ) ∣ ≤ n 2 2 ε d /2 ≤ n 2 + ε / ( 2 B ) , as desired.
Lemma 7. The edge set E ( G ) E(G) E ( G ) S × J S\times J S × J ∣ S ∣ , ∣ J ∣ ≥ ℓ |S|,|J|\ge\ell ∣ S ∣ , ∣ J ∣ ≥ ℓ ℓ : = 2 ( B − 1 ) ⌊ ( d − t ) / B ⌋ \ell:=2^{(B-1)\lfloor(d-t)/B\rfloor} ℓ := 2 ( B − 1 ) ⌊( d − t ) / B ⌋
Proof. The edges in question are of the form ( σ , j ) (\sigma,j) ( σ , j ) σ ∈ B d \sigma\in\mathcal{B}^d σ ∈ B d j j j [ n ] [n] [ n ] [ q ] d [q]^d [ q ] d σ \sigma σ d d d σ 1 , … , σ d \sigma_1,\ldots,\sigma_d σ 1 , … , σ d ∣ C o l u m n ∣ = : ρ |\mathrm{Column}|=:\rho ∣ Column ∣ =: ρ D i a g \mathrm{Diag} Diag p ∈ C o l u m n ∪ D i a g p\in\mathrm{Column}\cup\mathrm{Diag} p ∈ Column ∪ Diag c p ∈ [ q ] c_p\in[q] c p ∈ [ q ] p ∈ B a s i s p\in\mathrm{Basis} p ∈ Basis b p ∈ B b_p\in\mathcal{B} b p ∈ B p p p ( σ , j ) (\sigma,j) ( σ , j ) p p p
if p ∈ C o l u m n p\in\mathrm{Column} p ∈ Column σ p \sigma_p σ p c p c_p c p j p = c p j_p=c_p j p = c p q − 1 q-1 q − 1 σ p \sigma_p σ p
if p ∈ B a s i s p\in\mathrm{Basis} p ∈ Basis σ p = b p \sigma_p=b_p σ p = b p j p j_p j p b p b_p b p b p = e x y ± e y x b_p=e_{xy}\pm e_{yx} b p = e x y ± e y x j p j_p j p x x x y y y
::: By the definition, each ( σ , j ) (\sigma,j) ( σ , j ) σ ∈ S \sigma\in S σ ∈ S j ∈ J j \in J j ∈ J j p j_p j p σ p \sigma_p σ p S × J S \times J S × J
All that remains is to bound the sizes of S S S J J J ∣ S ∣ = ( q − 1 ) ρ |S|=(q-1)^\rho ∣ S ∣ = ( q − 1 ) ρ ∣ J ∣ = 2 u − ρ |J|=2^{u-\rho} ∣ J ∣ = 2 u − ρ u u u q = 2 B q=2^B q = 2 B q − 1 ≥ 2 B − 1 q-1 \ge2^{B-1} q − 1 ≥ 2 B − 1 ∣ S ∣ ≥ 2 ( B − 1 ) ρ |S| \ge2^{(B-1)\rho} ∣ S ∣ ≥ 2 ( B − 1 ) ρ d − t d-t d − t ∣ J ∣ = 2 u − ρ ≥ 2 d − t − ρ |J|=2^{u-\rho} \ge2^{d-t-\rho} ∣ J ∣ = 2 u − ρ ≥ 2 d − t − ρ ρ = ⌊ ( d − t ) / B ⌋ \rho=\left\lfloor(d-t)/B \right\rfloor ρ = ⌊ ( d − t ) / B ⌋ ∣ S ∣ |S| ∣ S ∣ ∣ J ∣ |J| ∣ J ∣
Lemma 8. Δ n , L ( k ) \Delta_{n,L}^{(k)} Δ n , L ( k ) O ( n k − ε / ( 4 B ) ) O(n^{k-\varepsilon/(4B)}) O ( n k − ε / ( 4 B ) )
Proof. By Lemma 4, the matrices E σ E_\sigma E σ ⟨ E σ , E σ ⟩ = 2 u ( σ ) \langle E_\sigma,E_\sigma\rangle=2^{u(\sigma)} ⟨ E σ , E σ ⟩ = 2 u ( σ ) E σ E_\sigma E σ τ p \tau_p τ p L L L
Reindexing the definition of L L L
L = ∑ C ⊆ [ d ] ∣ C ∣ ≥ d − t ( ∏ p ∈ C ( I − τ p ) ) ( ∏ p ∉ C τ p ) . L=\sum_{\substack{C\subseteq[d]\\ |C|\ge d-t}}\left(\prod_{p\in C}(I-\tau_p)\right)\left(\prod_{p\notin C}\tau_p\right). L = C ⊆ [ d ] ∣ C ∣ ≥ d − t ∑ p ∈ C ∏ ( I − τ p ) p ∈ / C ∏ τ p . Let A σ ⊆ [ d ] A_\sigma\subseteq[d] A σ ⊆ [ d ] E σ E_\sigma E σ ∣ A σ ∣ = a ( σ ) |A_\sigma|=a(\sigma) ∣ A σ ∣ = a ( σ ) C C C E σ E_\sigma E σ C ⊆ A σ C\subseteq A_\sigma C ⊆ A σ C ⊆ A σ C\subseteq A_\sigma C ⊆ A σ ∣ C ∣ = c |C|=c ∣ C ∣ = c C C C 2 2 2 C C C − 1 -1 − 1 1 1 1
L E σ = λ σ E σ , λ σ = ∑ c = d − t a ( σ ) ( a ( σ ) c ) 2 c ( − 1 ) a ( σ ) − c . LE_\sigma=\lambda_\sigma E_\sigma,\qquad\lambda_\sigma=\sum_{c=d-t}^{a(\sigma)}\binom{a(\sigma)}{c}2^c(-1)^{a(\sigma)-c}. L E σ = λ σ E σ , λ σ = c = d − t ∑ a ( σ ) ( c a ( σ ) ) 2 c ( − 1 ) a ( σ ) − c . In particular, λ σ = 0 \lambda_\sigma=0 λ σ = 0 a ( σ ) < d − t a(\sigma)<d-t a ( σ ) < d − t Q z Q^z Q z
Q z = ∑ σ ⟨ Q z , E σ ⟩ 2 u ( σ ) E σ . Q^z=\sum_\sigma\frac{\langle Q^z,E_\sigma\rangle}{2^{u(\sigma)}}E_\sigma. Q z = σ ∑ 2 u ( σ ) ⟨ Q z , E σ ⟩ E σ . We can now apply L L L P n , L z P^z_{n,L} P n , L z
Δ n , L ( k ) = ∑ z ⟨ P z , L Q z ⟩ = ∑ z , σ a ( σ ) ≥ d − t λ σ 2 u ( σ ) ⟨ P z , E σ ⟩ ⟨ Q z , E σ ⟩ . \Delta_{n,L}^{(k)}=\sum_z\langle P^z,LQ^z\rangle=\sum_{\substack{z,\sigma\\a(\sigma)\ge d-t}}\frac{\lambda_\sigma}{2^{u(\sigma)}}\langle P^z,E_\sigma\rangle\langle Q^z,E_\sigma\rangle. Δ n , L ( k ) = z ∑ ⟨ P z , L Q z ⟩ = z , σ a ( σ ) ≥ d − t ∑ 2 u ( σ ) λ σ ⟨ P z , E σ ⟩ ⟨ Q z , E σ ⟩ . We will bound this sum using the properties of the graph mentioned above. Let
E ( G ) = ⨆ β ( S β × J β ) (11) E(G)=\bigsqcup_\beta(S_\beta\times J_\beta) \tag*{(11)} E ( G ) = β ⨆ ( S β × J β ) (11) be the decomposition into bicliques of Lemma 7.
We begin by computing the values of Q σ , z = ⟨ E σ , Q z ⟩ Q_{\sigma,z}=\langle E_\sigma,Q^z\rangle Q σ , z = ⟨ E σ , Q z ⟩ z = ( z ′ , w ) z=(z',w) z = ( z ′ , w ) z ′ z' z ′ ( k − 3 ) (k-3) ( k − 3 )
Q σ , ( z ′ , w ) = ∑ i : ( σ , i ) ∈ E ( G ) ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) . Q_{\sigma,(z',w)}=\sum_{i:(\sigma,i)\in E(G)}(E_\sigma)_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z')U(i,z',w). Q σ , ( z ′ , w ) = i : ( σ , i ) ∈ E ( G ) ∑ ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) . We need to compute this quantity for all σ \sigma σ z z z Lemma 7 to partition this computation.
Fix a biclique S β × J β S_\beta\times J_\beta S β × J β (11) and a choice of z ′ z' z ′ A β A^\beta A β ∣ S β ∣ × ∣ J β ∣ |S_\beta| \times|J_\beta| ∣ S β ∣ × ∣ J β ∣
A σ , i β = ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) A^\beta_{\sigma,i}=(E_\sigma)_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z') A σ , i β = ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) and let B β B^\beta B β ∣ J β ∣ × n |J_\beta| \times n ∣ J β ∣ × n
B i , w β = U ( i , z ′ , w ) . B^\beta_{i,w}=U(i,z',w). B i , w β = U ( i , z ′ , w ) . Then
( A β B β ) σ , w = ∑ i ∈ J β ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) (A^\beta B^\beta)_{\sigma,w}=\sum_{i\in J_\beta}(E_\sigma)_{i,\pi_i(\sigma)}X_{k-2}(i,\pi_i(\sigma),z')U(i,z',w) ( A β B β ) σ , w = i ∈ J β ∑ ( E σ ) i , π i ( σ ) X k − 2 ( i , π i ( σ ) , z ′ ) U ( i , z ′ , w ) is the restriction of the sum Q σ , ( z ′ , w ) Q_{\sigma,(z',w)} Q σ , ( z ′ , w ) J β J_\beta J β Q σ , ( z ′ , w ) = ∑ β ( A β B β ) σ , w Q_{\sigma,(z',w)}=\sum_\beta(A^\beta B^\beta)_{\sigma,w} Q σ , ( z ′ , w ) = ∑ β ( A β B β ) σ , w β \beta β σ ∈ S β \sigma\in S_\beta σ ∈ S β A β B β A^\beta B^\beta A β B β Q Q Q
From Lemma 7 , ∣ S β ∣ , ∣ J β ∣ ≥ ℓ |S_\beta|,|J_\beta|\ge\ell ∣ S β ∣ , ∣ J β ∣ ≥ ℓ A β B β A^\beta B^\beta A β B β O ( ∣ S β ∣ ∣ J β ∣ n / ℓ γ ) O(|S_\beta||J_\beta|n/\ell^\gamma) O ( ∣ S β ∣∣ J β ∣ n / ℓ γ ) γ > 1 / 8 \gamma>1/8 γ > 1/8 z ′ z' z ′
n k − 3 ∑ β ∣ S β ∣ ∣ J β ∣ n / ℓ γ = O ( n k − 2 m / ℓ γ ) n^{k-3}\sum_\beta|S_\beta||J_\beta|n/\ell^\gamma=O(n^{k-2}m/\ell^\gamma) n k − 3 β ∑ ∣ S β ∣∣ J β ∣ n / ℓ γ = O ( n k − 2 m / ℓ γ ) because each of the m m m G G G ∣ S β ∣ ⋅ ∣ J β ∣ |S_\beta|\cdot|J_\beta| ∣ S β ∣ ⋅ ∣ J β ∣ γ > 1 / 8 ≥ ε \gamma>1/8\ge\varepsilon γ > 1/8 ≥ ε O ( n k − 2 m / ℓ ε ) O(n^{k-2}m/\ell^\varepsilon) O ( n k − 2 m / ℓ ε )
We now turn to computing the values of P σ , z = ⟨ E σ , P z ⟩ P_{\sigma,z}=\langle E_\sigma,P^z\rangle P σ , z = ⟨ E σ , P z ⟩
P σ , z = ∑ j : ( σ , j ) ∈ E ( G ) ( E σ ) π j ( σ ) , j V ( j , z ) ∏ s = 1 k − 3 X s ( π j ( σ ) , j , z − s ) . P_{\sigma,z}=\sum_{j:(\sigma,j)\in E(G)}(E_\sigma)_{\pi_j(\sigma),j}V(j,z)\prod_{s=1}^{k-3}X_s(\pi_j(\sigma),j,z_{-s}). P σ , z = j : ( σ , j ) ∈ E ( G ) ∑ ( E σ ) π j ( σ ) , j V ( j , z ) s = 1 ∏ k − 3 X s ( π j ( σ ) , j , z − s ) . Fix a biclique β \beta β w ∈ [ n ] w\in[n] w ∈ [ n ] Y ( σ , z ′ , w ) Y(\sigma,z',w) Y ( σ , z ′ , w ) σ ∈ S β \sigma\in S_\beta σ ∈ S β z ′ ∈ [ n ] k − 3 z'\in[n]^{k-3} z ′ ∈ [ n ] k − 3 Φ = Φ β , w \Phi=\Phi_{\beta,w} Φ = Φ β , w
Φ β , w = ∑ σ ∈ S β , j ∈ J β , z ′ ∈ [ n ] k − 3 ( E σ ) π j ( σ ) , j Y ( σ , z ′ , w ) V ( j , ( z ′ , w ) ) ∏ s = 1 k − 3 X s ( π j ( σ ) , j , ( z ′ , w ) − s ) . \Phi_{\beta,w}=\sum_{\sigma\in S_\beta,j\in J_\beta,z'\in[n]^{k-3}}(E_\sigma)_{\pi_j(\sigma),j}Y(\sigma,z',w)V(j,(z',w))\prod_{s=1}^{k-3}X_s(\pi_j(\sigma),j,(z',w)_{-s}). Φ β , w = σ ∈ S β , j ∈ J β , z ′ ∈ [ n ] k − 3 ∑ ( E σ ) π j ( σ ) , j Y ( σ , z ′ , w ) V ( j , ( z ′ , w )) s = 1 ∏ k − 3 X s ( π j ( σ ) , j , ( z ′ , w ) − s ) . This is an imbalanced ( k − 1 ) (k-1) ( k − 1 ) X s X_s X s ( E σ ) π j ( σ ) , j (E_\sigma)_{\pi_j(\sigma),j} ( E σ ) π j ( σ ) , j j j j σ \sigma σ ∣ S β ∣ × ∣ J β ∣ × n × ⋯ × n |S_\beta|\times|J_\beta|\times n\times\cdots\times n ∣ S β ∣ × ∣ J β ∣ × n × ⋯ × n
Recall that ℓ = 2 ( B − 1 ) ⌊ ( d − t ) / B ⌋ ≤ 2 d − t ≤ n \ell=2^{(B-1)\lfloor(d-t)/B\rfloor}\le2^{d-t}\le n ℓ = 2 ( B − 1 ) ⌊( d − t ) / B ⌋ ≤ 2 d − t ≤ n t ≤ d t\le d t ≤ d ∣ S β ∣ , ∣ J β ∣ ≥ ℓ |S_\beta|,|J_\beta|\ge\ell ∣ S β ∣ , ∣ J β ∣ ≥ ℓ Lemma 7 . Hence by Lemma 2 and our inductive assumption, Φ \Phi Φ
ℓ k − 1 − ε ⋅ n k − 3 ∣ S β ∣ ∣ J β ∣ ℓ k − 1 = n k − 3 ∣ S β ∣ ∣ J β ∣ ⋅ ℓ − ε . \ell^{k-1-\varepsilon}\cdot\frac{n^{k-3}|S_\beta||J_\beta|}{\ell^{k-1}}=n^{k-3}|S_\beta||J_\beta|\cdot\ell^{-\varepsilon}. ℓ k − 1 − ε ⋅ ℓ k − 1 n k − 3 ∣ S β ∣∣ J β ∣ = n k − 3 ∣ S β ∣∣ J β ∣ ⋅ ℓ − ε . By Lemma 3, we can compute the partial derivatives of Φ \Phi Φ Y Y Y P σ , ( z ′ , w ) = ∑ β : σ ∈ S β ∂ Φ β , w ∂ Y ( σ , z ′ , w ) P_{\sigma,(z',w)}=\sum_{\beta:\sigma\in S_\beta}\frac{\partial\Phi_{\beta,w}}{\partial Y(\sigma,z',w)} P σ , ( z ′ , w ) = ∑ β : σ ∈ S β ∂ Y ( σ , z ′ , w ) ∂ Φ β , w J β J_\beta J β σ ∈ S β \sigma\in S_\beta σ ∈ S β σ \sigma σ G G G P σ , z \mathcal{P}_{\sigma,z} P σ , z Φ β , w \Phi_{\beta,w} Φ β , w w w w β \beta β P \mathcal{P} P
∑ w , β n k − 3 ∣ S β ∣ ∣ J β ∣ ⋅ ℓ − ε = n k − 2 ℓ − ε ∑ β ∣ S β ∣ ∣ J β ∣ = n k − 2 m ℓ − ε . \sum_{w,\beta} n^{k-3}|S_\beta||J_\beta|\cdot\ell^{-\varepsilon}
= n^{k-2}\ell^{-\varepsilon}\sum_\beta|S_\beta||J_\beta|
= n^{k-2}m\ell^{-\varepsilon}. w , β ∑ n k − 3 ∣ S β ∣∣ J β ∣ ⋅ ℓ − ε = n k − 2 ℓ − ε β ∑ ∣ S β ∣∣ J β ∣ = n k − 2 m ℓ − ε . Finally, given all P σ , z \mathcal{P}_{\sigma,z} P σ , z Q σ , z \mathcal{Q}_{\sigma,z} Q σ , z
Δ n , L ( k ) = ∑ z , σ : a ( σ ) ≥ d − t λ σ 2 u ( σ ) P σ , z Q σ , z . \Delta^{(k)}_{n,L}=\sum_{z,\ \sigma:a(\sigma)\ge d-t}\frac{\lambda_\sigma}{2^{u(\sigma)}}\mathcal{P}_{\sigma,z}\mathcal{Q}_{\sigma,z}. Δ n , L ( k ) = z , σ : a ( σ ) ≥ d − t ∑ 2 u ( σ ) λ σ P σ , z Q σ , z . using O ( n k − 2 ⋅ # σ ) O(n^{k-2}\cdot\#\sigma) O ( n k − 2 ⋅ # σ ) # σ \#\sigma # σ G G G 2 u ( σ ) ≥ 2 a ( σ ) ≥ 2 d − t 2^{u(\sigma)}\ge2^{a(\sigma)}\ge2^{d-t} 2 u ( σ ) ≥ 2 a ( σ ) ≥ 2 d − t # σ ≤ m / 2 d − t ≤ m / ℓ \#\sigma\le m/2^{d-t}\le m/\ell # σ ≤ m / 2 d − t ≤ m / ℓ A β A^\beta A β Φ \Phi Φ β \beta β w w w O ( n k − 3 m ) O(n^{k-3}m) O ( n k − 3 m ) ℓ ≤ n \ell\le n ℓ ≤ n O ( n k − 2 m / ℓ ε ) O(n^{k-2}m/\ell^\varepsilon) O ( n k − 2 m / ℓ ε )
Finally, we need to bound ℓ \ell ℓ
log ℓ : = ( B − 1 ) ⌊ d − t B ⌋ ≥ d ( B − 1 ) 2 B 2 − ( B − 1 ) , \log\ell:= (B-1)\left\lfloor\frac{d-t}{B}\right\rfloor
\ge\frac{d(B-1)^2}{B^2}-(B-1), log ℓ := ( B − 1 ) ⌊ B d − t ⌋ ≥ B 2 d ( B − 1 ) 2 − ( B − 1 ) , which results from using t ≤ d / B t\le d/B t ≤ d / B n = 2 B d n=2^{Bd} n = 2 B d d = log n / B d=\log n/B d = log n / B
log ℓ ≥ ( B − 1 ) 2 B 3 log n − ( B − 1 ) = ( 1 − 1 / B ) 2 B log n − ( B − 1 ) , \log\ell\ge\frac{(B-1)^2}{B^3}\log n-(B-1)
=\frac{(1-1/B)^2}{B}\log n-(B-1), log ℓ ≥ B 3 ( B − 1 ) 2 log n − ( B − 1 ) = B ( 1 − 1/ B ) 2 log n − ( B − 1 ) , and exponentiating tells us that ℓ ≥ 2 − ( B − 1 ) n ( 1 − 1 / B ) 2 / B \ell\ge2^{-(B-1)}n^{(1-1/B)^2/B} ℓ ≥ 2 − ( B − 1 ) n ( 1 − 1/ B ) 2 / B B B B n n n B ≥ 16 B\ge16 B ≥ 16 ( 1 − 1 / B ) 2 ≥ 3 / 4 (1-1/B)^2\ge3/4 ( 1 − 1/ B ) 2 ≥ 3/4 ℓ ≥ Ω ( n 3 / ( 4 B ) ) \ell\ge\Omega(n^{3/(4B)}) ℓ ≥ Ω ( n 3/ ( 4 B ) )
Applying this along with Lemma 6 tells us that the overall circuit size is, up to constants, at most
n k − 2 m ℓ ε ≤ n k − 2 ⋅ n 2 + ε / ( 2 B ) n 3 ε / ( 4 B ) ≤ n k − ε / ( 4 B ) . \frac{n^{k-2}m}{\ell^\varepsilon}
\le\frac{n^{k-2}\cdot n^{2+\varepsilon/(2B)}}{n^{3\varepsilon/(4B)}}
\le n^{k-\varepsilon/(4B)}. ℓ ε n k − 2 m ≤ n 3 ε / ( 4 B ) n k − 2 ⋅ n 2 + ε / ( 2 B ) ≤ n k − ε / ( 4 B ) . The final circuit
By combining Corollary 1 (the high degree part) and Lemma 8 (the low degree part), we are finally ready to prove our main theorem.
Proof of Theorem 6. Recall that
Δ n ( k ) = Δ n , L ( k ) + Δ n , H ( k ) . \Delta^{(k)}_n=\Delta^{(k)}_{n,L}+\Delta^{(k)}_{n,H}. Δ n ( k ) = Δ n , L ( k ) + Δ n , H ( k ) . By Corollary 1, Δ n , H ( k ) \Delta^{(k)}_{n,H} Δ n , H ( k ) O ( n k − ε / ( 2 B ) ) O(n^{k-\varepsilon/(2B)}) O ( n k − ε / ( 2 B ) ) Lemma 8 , Δ n , L ( k ) \Delta^{(k)}_{n,L} Δ n , L ( k ) O ( n k − ε / ( 4 B ) ) O(n^{k-\varepsilon/(4B)}) O ( n k − ε / ( 4 B ) ) O ( n k − ε / ( 4 B ) ) O(n^{k-\varepsilon/(4B)}) O ( n k − ε / ( 4 B ) )
While the above argument suffices to show that we can attain some nontrivial savings for every value of k k k k k k 1 / ( 4 B ) 1/(4B) 1/ ( 4 B ) k k k 2 ε B ≥ ( e B ) 2 2^{\varepsilon B}\ge(eB)^2 2 εB ≥ ( e B ) 2 B B B
Proof of Theorem 1. Let ε j \varepsilon_j ε j j j j ε 3 = 1 / 8 \varepsilon_3 = 1/8 ε 3 = 1/8
L j : = log ( 1 / ε j ) B j : = ⌈ 8 L j ε j ⌉ ε j + 1 : = ε j 4 B j L_j := \log(1/\varepsilon_j) \qquad B_j := \left\lceil\frac{8L_j}{\varepsilon_j} \right\rceil\qquad\varepsilon_{j+1} := \frac{\varepsilon_j}{4B_j} L j := log ( 1/ ε j ) B j := ⌈ ε j 8 L j ⌉ ε j + 1 := 4 B j ε j We first need to check that 2 ε j B j ≥ ( e B j ) 2 2^{\varepsilon_j B_j} \ge(eB_j)^2 2 ε j B j ≥ ( e B j ) 2 j j j B j ≤ 9 L j / ε j B_j \le9L_j/\varepsilon_j B j ≤ 9 L j / ε j L j ≥ 3 L_j \ge3 L j ≥ 3 ε j ≤ 1 / 8 \varepsilon_j \le1/8 ε j ≤ 1/8
log ( e B j ) ≤ log ( 9 e ) + log ( L j ) − log ( ε j ) ≤ 5 + log ( L j ) + L j ≤ 4 L j ≤ ε j B j / 2. \log(eB_j) \le\log(9e) + \log(L_j) - \log(\varepsilon_j) \le5 + \log(L_j) + L_j \le4L_j \le\varepsilon_j B_j/2. log ( e B j ) ≤ log ( 9 e ) + log ( L j ) − log ( ε j ) ≤ 5 + log ( L j ) + L j ≤ 4 L j ≤ ε j B j /2. Doubling and exponentiating this proves the inequality. We will show that L j ≤ 2 j + 1 − j − 8 L_j \le2^{j+1} - j - 8 L j ≤ 2 j + 1 − j − 8 L 3 ≤ 3 L_3 \le3 L 3 ≤ 3
By the upper bound on B j B_j B j ε j + 1 ≥ ε j 2 / ( 36 L j ) \varepsilon_{j+1} \ge\varepsilon_j^2/(36L_j) ε j + 1 ≥ ε j 2 / ( 36 L j )
L j + 1 = − log ( ε j + 1 ) ≤ − log ( ε j 2 ) + log ( 36 L j ) ≤ 2 L j + log L j + 6. L_{j+1} = -\log(\varepsilon_{j+1}) \le-\log(\varepsilon_j^2) + \log(36L_j) \le2L_j + \log L_j + 6. L j + 1 = − log ( ε j + 1 ) ≤ − log ( ε j 2 ) + log ( 36 L j ) ≤ 2 L j + log L j + 6. Using the inductive hypothesis gives L j + 1 ≤ 2 j + 2 − ( j + 1 ) − 8 L_{j+1} \le2^{j+2} - (j+1) - 8 L j + 1 ≤ 2 j + 2 − ( j + 1 ) − 8 L k = O ( 2 k ) L_k = O(2^k) L k = O ( 2 k ) ε k = 2 − L k \varepsilon_k = 2^{-L_k} ε k = 2 − L k O ( n k − 2 − O ( 2 k ) ) O\left(n^{k-2^{-O(2^k)}}\right) O ( n k − 2 − O ( 2 k ) )
Finally, we briefly remark on the uniformity. All the constants occurring in the circuit can be efficiently constructed and are not the bottleneck. Each step of our circuit construction is evidently efficient. The only technical input is Baur–Strassen (Lemma 3) which is also known to be implementable in linear time (see [39 ] for the proof).
Applications
We have shown (Theorem 1) that the k k k Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) O ( n k − ε k ) O(n^{k-\varepsilon_k}) O ( n k − ε k ) ε k = 2 − Θ ( 2 k ) \varepsilon_k = 2^{-\Theta(2^k)} ε k = 2 − Θ ( 2 k ) Z [ 1 / 2 ] \mathbb{Z}[1/2] Z [ 1/2 ] 2 2 2 Z / ( M Z ) \mathbb{Z}/(M\mathbb{Z}) Z / ( M Z ) M M M
Counting Hypercliques
Reminder of Theorem 2. For every fixed k ≥ 3 k \ge3 k ≥ 3 ( k − 1 ) (k-1) ( k − 1 ) H H H n n n k k k H H H n k − ε k + o ( 1 ) n^{k-\varepsilon_k+o(1)} n k − ε k + o ( 1 ) ε k \varepsilon_k ε k
Proof. Make k k k V 1 , … , V k V_1,\ldots,V_k V 1 , … , V k H H H i ∈ [ k ] i \in[k] i ∈ [ k ] α ∈ ∏ j ≠ i V j \alpha\in\prod_{j\ne i} V_j α ∈ ∏ j = i V j a a a Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) a α ( i ) = 1 a_\alpha^{(i)} = 1 a α ( i ) = 1 α \alpha α H H H a α ( i ) = 0 a_\alpha^{(i)} = 0 a α ( i ) = 0 Δ n ( k ) ( a ) \Delta_n^{(k)}(a) Δ n ( k ) ( a ) k k k k k k k ! k! k ! Δ n ( k ) \Delta_n^{(k)} Δ n ( k ) O ( n k − ε k + o ( 1 ) ) O(n^{k-\varepsilon_k+o(1)}) O ( n k − ε k + o ( 1 ) ) Δ n ( k ) ( a ) \Delta_n^{(k)}(a) Δ n ( k ) ( a ) n k n^k n k Δ n ( k ) ( a ) \Delta_n^{(k)}(a) Δ n ( k ) ( a ) M M M M > n k M > n^k M > n k n k − ε k + o ( 1 ) n^{k-\varepsilon_k+o(1)} n k − ε k + o ( 1 ) m m m m 4 / 3 − ε m^{4/3-\varepsilon} m 4/3 − ε ε > 0 \varepsilon> 0 ε > 0 [8 ] on triangles), we can find maximum node-weight hypercliques faster (extending the method of [19 ] for triangles), and we can similarly list hypercliques faster (extending [40 ] and other works). We omit the details.
k-wise matrix product
Next, we show how to compute the k k k k k k [15 Section 5.1] . Given k k k A 1 , … , A k A_1,\ldots,A_k A 1 , … , A k k k k n × ⋯ × n n \times\cdots\times n n × ⋯ × n
MP k ( A 1 , … , A k ) [ i 1 , … , i k ] = ∑ ℓ = 1 n A 1 [ ℓ , i 2 , … , i k ] A 2 [ i 1 , ℓ , i 3 , … , i k ] ⋯ A k [ i 1 , … , i k − 1 , ℓ ] . \operatorname{MP}_k(A_1,\ldots,A_k)[i_1,\ldots,i_k] = \sum_{\ell=1}^{n} A_1[\ell,i_2,\ldots,i_k] A_2[i_1,\ell,i_3,\ldots,i_k] \cdots A_k[i_1,\ldots,i_{k-1},\ell]. MP k ( A 1 , … , A k ) [ i 1 , … , i k ] = ℓ = 1 ∑ n A 1 [ ℓ , i 2 , … , i k ] A 2 [ i 1 , ℓ , i 3 , … , i k ] ⋯ A k [ i 1 , … , i k − 1 , ℓ ] . Reminder of Theorem 3. For every k ≥ 3 k \ge3 k ≥ 3 ε > 0 \varepsilon> 0 ε > 0 MP k ( A 1 , … , A k ) \operatorname{MP}_k(A_1,\ldots,A_k) MP k ( A 1 , … , A k ) A 1 , … , A k A_1,\ldots,A_k A 1 , … , A k n k n^k n k O ( n k + 1 − ε ) O(n^{k+1-\varepsilon}) O ( n k + 1 − ε )
The basic idea is that we may view MP k \operatorname{MP}_k MP k ( k + 1 ) (k+1) ( k + 1 ) Δ n ( k + 1 ) \Delta_n^{(k+1)} Δ n ( k + 1 ) Δ n ( k + 1 ) \Delta_n^{(k+1)} Δ n ( k + 1 ) MP k \operatorname{MP}_k MP k
Proof. Start by indexing the k + 1 k+1 k + 1 Δ n ( k + 1 ) ( X ) \Delta_n^{(k+1)}(X) Δ n ( k + 1 ) ( X ) ( i 1 , … , i k , ℓ ) (i_1,\ldots,i_k,\ell) ( i 1 , … , i k , ℓ ) j ∈ [ k ] j \in[k] j ∈ [ k ] i j i_j i j k k k
( i 1 , … , i j − 1 , i j + 1 , … , i k , ℓ ) , (i_1,\ldots,i_{j-1},i_{j+1},\ldots,i_k,\ell), ( i 1 , … , i j − 1 , i j + 1 , … , i k , ℓ ) , and the group omitting ℓ \ell ℓ ( i 1 , … , i k ) (i_1,\ldots,i_k) ( i 1 , … , i k ) j ∈ [ k ] j \in[k] j ∈ [ k ]
x ( i 1 , … , i j − 1 , i j + 1 , … , i k , ℓ ) ( j ) : = A j [ i 1 , … , i j − 1 , ℓ , i j + 1 , … , i k ] . x^{(j)}_{(i_1,\ldots,i_{j-1},i_{j+1},\ldots,i_k,\ell)} := A_j[i_1,\ldots,i_{j-1},\ell,i_{j+1},\ldots,i_k]. x ( i 1 , … , i j − 1 , i j + 1 , … , i k , ℓ ) ( j ) := A j [ i 1 , … , i j − 1 , ℓ , i j + 1 , … , i k ] . That is, the index ℓ \ell ℓ j j j A j A_j A j x α ( k + 1 ) x^{(k+1)}_\alpha x α ( k + 1 ) α ∈ [ n ] k \alpha\in[n]^k α ∈ [ n ] k ( α , ℓ ) = ( i 1 , … , i k , ℓ ) (\alpha,\ell)=(i_1,\ldots,i_k,\ell) ( α , ℓ ) = ( i 1 , … , i k , ℓ )
A 1 [ ℓ , i 2 , … , i k ] ⋯ A k [ i 1 , … , i k − 1 , ℓ ] ⋅ x α ( k + 1 ) . A_1[\ell,i_2,\ldots,i_k]\cdots A_k[i_1,\ldots,i_{k-1},\ell]\cdot x^{(k+1)}_\alpha. A 1 [ ℓ , i 2 , … , i k ] ⋯ A k [ i 1 , … , i k − 1 , ℓ ] ⋅ x α ( k + 1 ) . Summing over ℓ \ell ℓ
Δ n ( k + 1 ) ( A 1 , … , A k , x ( k + 1 ) ) = ∑ α ∈ [ n ] k MP k ( A 1 , … , A k ) [ α ] ⋅ x α ( k + 1 ) . \Delta_n^{(k+1)}(A_1,\ldots,A_k,x^{(k+1)}) = \sum_{\alpha\in[n]^k} \operatorname{MP}_k(A_1,\ldots,A_k)[\alpha]\cdot x^{(k+1)}_\alpha. Δ n ( k + 1 ) ( A 1 , … , A k , x ( k + 1 ) ) = α ∈ [ n ] k ∑ MP k ( A 1 , … , A k ) [ α ] ⋅ x α ( k + 1 ) . Observe that this polynomial is linear in that last group of variables, and its partial derivative with respect to each x α ( k + 1 ) x^{(k+1)}_\alpha x α ( k + 1 ) α ∈ [ n ] k \alpha\in[n]^k α ∈ [ n ] k
By the Baur–Strassen theorem (Lemma 3), all partial derivatives of the above polynomial can be computed by an arithmetic circuit of size that is linear in the circuit size of the Δ n ( k + 1 ) \Delta_n^{(k+1)} Δ n ( k + 1 ) O ( n k + 1 − ε k + 1 ) O(n^{k+1-\varepsilon_{k+1}}) O ( n k + 1 − ε k + 1 ) MP k \operatorname{MP}_k MP k
Finally, to evaluate this circuit over Boolean inputs, we note that each output is a sum of n n n 0 0 0 n n n n n n
Max-kSAT, Max-kCSP, etc
Here, we review why the Max-k k k k k k n n n degree-k k k if it has degree at most k k k { 0 , 1 } \{0,1\} { 0 , 1 } k k k k k k k k k k k k n n n
Reminder of Theorem 4. For every k ≥ 3 k \ge3 k ≥ 3 δ k > 0 \delta_k > 0 δ k > 0 k k k n n n m m m 2 ( 1 − δ k ) n poly ( n , m ) 2^{(1-\delta_k)n}\operatorname{poly}(n,m) 2 ( 1 − δ k ) n poly ( n , m )
Proof. Theorem C.1 in [37 ] shows that, for all constants ℓ \ell ℓ k k k ℓ \ell ℓ k k k N N N T ( N ) T(N) T ( N ) k k k
O ~ ( ( m n k ) ( ℓ k ) ⋅ T ( ℓ ⋅ 2 n / ℓ ) + m n k ⋅ 2 k n / ℓ ) . (12) \widetilde{O}\left((mn^k)^{\binom{\ell}{k}}\cdot T(\ell\cdot2^{n/\ell})+mn^k\cdot2^{kn/\ell}\right). \tag*{(12)} O ( ( m n k ) ( k ℓ ) ⋅ T ( ℓ ⋅ 2 n / ℓ ) + m n k ⋅ 2 k n / ℓ ) . (12) (The special case of Max-k k k ℓ = k + 1 \ell=k+1 ℓ = k + 1 ( ℓ k ) = k + 1 \binom{\ell}{k}=k+1 ( k ℓ ) = k + 1 k + 1 k+1 k + 1 k k k T ( N ) ≤ O ( N k + 1 − ε k + 1 ) T(N)\le O(N^{k+1-\varepsilon_{k+1}}) T ( N ) ≤ O ( N k + 1 − ε k + 1 ) k k k (12) is then
poly ( m , n ) ⋅ ( 2 n ( k + 1 − ε k + 1 ) / ( k + 1 ) + 2 k n / ( k + 1 ) ) ≤ 2 n ( 1 − δ k ) ⋅ poly ( m , n ) \operatorname{poly}(m,n)\cdot\left(2^{n(k+1-\varepsilon_{k+1})/(k+1)}+2^{kn/(k+1)}\right)\le2^{n(1-\delta_k)}\cdot\operatorname{poly}(m,n) poly ( m , n ) ⋅ ( 2 n ( k + 1 − ε k + 1 ) / ( k + 1 ) + 2 k n / ( k + 1 ) ) ≤ 2 n ( 1 − δ k ) ⋅ poly ( m , n ) for δ k : = ε k + 1 / ( k + 1 ) \delta_k:=\varepsilon_{k+1}/(k+1) δ k := ε k + 1 / ( k + 1 )
Inspecting their proof (which generalizes the algorithm for Max-Degree-2CSP in [56 ] ), we may also exactly count the number of Boolean assignments that maximize the number of satisfied constraints in the same running time.
The k-AP Hypothesis is false
Finally, we note that our results on hyperclique finding have applications to algorithms in additive combinatorics.
Reminder of Theorem 5. For every fixed k ≥ 4 k\ge4 k ≥ 4 A ⊆ { 0 , … , n } A\subseteq\{0,\ldots,n\} A ⊆ { 0 , … , n } k k k O ( n 2 − 2 ε k / k ) O(n^{2-2\varepsilon_k/k}) O ( n 2 − 2 ε k / k )
Proof. Lemma 5.7 of [23 ] states that if deciding whether a ( k − 1 ) (k-1) ( k − 1 ) n n n k k k T ( n ) T(n) T ( n ) k k k O ( T ( n 2 / k ) ) O(T(n^{2/k})) O ( T ( n 2/ k )) T ( n ) ≤ O ( n k − ε k ) T(n)\le O(n^{k-\varepsilon_k}) T ( n ) ≤ O ( n k − ε k ) k k k O ( n ( 2 / k ) ( k − ε k ) ) = O ( n 2 − 2 ε k / k ) O(n^{(2/k)(k-\varepsilon_k)})=O(n^{2-2\varepsilon_k/k}) O ( n ( 2/ k ) ( k − ε k ) ) = O ( n 2 − 2 ε k / k )
AI methodology and background
On October 12 2026, we proposed using the algebraic approach to refute the hyperclique conjecture to ChatGPT 6 Pro. With a little encouragement, it obtained the main result. The full chat is available here.
ChatGPT and Claude were both used by the authors to help understand ideas, compare them to prior work, proofread, and draw figures. None of the text in this document is AI generated.
