Matrix product states and the quantum max-flow/min-cut conjectures
Fulvio Gesmundo J. M. Landsberg Michael Walter
quant-ph math.AG



QMATH, University of Copenhagen, Universitetsparken 5, 2100 København Ø, Denmark
fulges@math.ku.dk

Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA
jml@math.tamu.edu

QuSoft, Korteweg-de Vries Institute for Mathematics, Institute for Theoretical Physics, Institute for Logic, Language and Computation, University of Amsterdam, 1098 XG Amsterdam, Netherlands
Stanford Institute for Theoretical Physics, Stanford University, Stanford, CA 94305, USA
m.walter@uva.nl




In this note we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut.
In the first we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions.
In the second we generalize this result to a 2d-cycle.
In the third we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely a gap of at least 2^d-2 between the quantum max-flow and the quantum min-cut.

Matrix product states and the quantum max-flow/min-cut conjectures
    Michael Walter
    December 30, 2023
==================================================================







§ INTRODUCTION



A tensor network associated to a graph is a way of constructing tensors in large spaces from smaller building-block tensors.
From the perspective of algebraic geometry, tensor networks provide a natural way of constructing varieties of tensors.
The use of graphs to study tensors dates back at least to Clifford in 1881 (see Ref. [Fig. 2.11.1]MR2865915).
In applied mathematics and physics, tensor networks are versatile tools for efficiently approximating high-dimensional data, such as ground states of many-body quantum systems in condensed matter physics (see, e.g., Refs. MR2535056,verstraete2009tnsreview,orus2014tnsreview).

In this paper we focus exclusively on translation-invariant matrix product states with periodic boundary conditions as defined in <ref>.
We use them to obtain three sequences of examples of tensor networks where the quantum max-flow (<ref>) is strictly less than the quantum min-cut (<ref>) for certain partitions.
Our results disprove a natural conjecture and verify a numerical prediction from Ref. MR3613509 (<ref>).




 §.§ Matrix product states with periodic boundary conditions


In this paper, we work exclusively with tensor networks associated with the oriented cyclic graphs C_m, as in Figure <ref> (a), and one building-block tensor T taken from ^N^n (^n)^*, which we write as A B B^*.



One constructs tensors in A^ m=(^N)^ m from this set-up as follows:
For each vertex, we associate a copy of A to the external (physical) edge, a copy of B to the outgoing edge from the circle, and a copy of B^* to the incoming edge in the circle.
We thus obtain a tensor Φ(T)∈ A^ m by

    Φ(T)=contract(T^ m),

where we place a copy of T at each vertex, and then contract B B^* along the edges on the circle.
We will refer to the tensor Φ(T)∈ A^ m as the tensor network state associated to (C_m,T).
The dimensions N,n are known as the bond dimensions.

In physics, tensors such as Φ(T) are also known as translation-invariant matrix product states with periodic boundary conditions.
In indices, if a_1 a_N is a basis of A, b_1 b_n a basis of B with dual basis ^̱1^̱n, so we may write T=∑_i,s,tT^is_    t a_i b_s^̱t, then

    Φ(T)=∑ T^i_1s_1_       s_m T^i_2s_2_       s_1⋯ T^i_ms_m_       s_m-1 a_i_1 a_i_m.

If we think of each T^i=(T^is_    t) as an n× n matrix, we may write the a_i_1 a_i_m coefficient of Φ(T) as

    (T^i_m⋯ T^i_1),

which explains the terminology “matrix product state”.
“Periodic boundary conditions” refers to the fact that the graph is a cycle and not a linear graph, and “translation-invariant” means that the same tensor T is placed at each vertex.
This implies a cyclic _m-symmetry for Φ(T) that will play an important role in this paper.

Let (C_m,N,n)⊂ A^ m denote the set of all tensor network states Φ(T) associated to C_m, and let
(C_m,N,n)⊂(A^ m) denote its Zariski closure in projective space.
In other words, Φ defines a rational map

    Φ:  (A B B^*) (A^ m)

(which we denote by the same symbol Φ), and (C_m,N,n) is the closure of its image.
Note that the image is linearly degenerate, lying in the space of invariants (A^ m)^_m, where _m acts by cyclically permuting the vertices.
Also note that the group (B), the invertible linear maps B B, acts on B and B^*; so (B)=(B)/{^*} acts on (A B B^*), preserving the fibers of Φ.
Thus the generic fiber of Φ contains a space isomorphic to (B).




 §.§ Quantum max-flow


Now partition the external edges into two sets S, S̅ (`sources' and `sinks', see Figure <ref>).
This induces a splitting A^ m=(_s∈ SA_s)  (_t∈S̅A_t).
Given Φ(T)∈ A^ m, we get an induced linear map

    Φ(T)_S,S̅: ⊗_s∈ SA_s^* →⊗_t∈S̅A_t

(called a flattening in the geometry literature).
The quantum max-flow is defined as the maximal rank over all Φ(T) of this flattening <cit.>

    '(C_m,(S,S̅), N,n):=max_T∈ A B B^*(Φ(T)_S,S̅).

The prime reminds us that we place the same tensor T at each vertex.
When N=n, we suppress it from the notation and just write '(C_m,(S,S̅), N).





 §.§ Quantum min-cut


To define the quantum min-cut, it is useful to define an extended graph C_m by adding terminal vertices at the dangling ends of the external edges, as in Figure <ref>, (b).
Now we may also think of the partition (S,S̅) as a partition of the terminals into two sets.
A  cut in this situation is a partition of the vertices of C_m into two sets (, ), with S⊆ and S̅⊆.
Define the quantum capacity of a cut (,) by

    (,):=∏_v∈, w∈, vw∈ E(vw),

where the quantum capacity of an edge, (vw), is the dimension of the vector space associated to it.
In our case the quantum capacities are n for edges on the circle and N for external edges.
Following Ref. MR3513725, define the quantum min-cut by

    (C_m,(S,S̅),N,n):=min_(,)(,),

where we minimize over all cuts (,) for (S,S̅).
Again we write (C_m,(S,S̅),N) when N=n.




 §.§ Quantum max-flow vs. quantum min-cut


In Ref. MR3513725 the authors propose that tensor networks with physical edges divided into two sets can be viewed as “transporting” linear-algebraic quantities such as rank and entanglement, and are properly viewed as quantum analogs of graphs modeling flow networks.
In the classical case, that is, for flow networks, it is well-known that the maximal flow passing from sources to sinks is equal to the minimum cut separating the sources from sinks—this is the famous max-flow min-cut theorem.

In the quantum case, it is well-known and easy to see that

    '(C_m,(S,S̅),(N,n)) ≤(C_m,(S,S̅),(N,n))

and similarly for arbitrary graphs.
Indeed, any cut (,) induces a factorization of the linear map Φ(T)_S,S̅ through a vector space of dimension equal to the quantum capacity of the cut, which implies (<ref>) at once.

In Ref. MR3513725, the authors studied to what extent equality holds in the quantum case, prompted by the “quantum max-flow/min-cut conjecture” from Ref. [Conjecture C.1]calegari2010positivity.
Note that in the quantum case, the quantum min-cut is still straight-forward to compute (it can be readily reduced to computing a classical min-cut), but the quantum max-flow may be difficult to compute directly.

The original conjecture was vastly more general than the set-up here, but it in particular implied that, for all (S,S̅) and N, '(C_m,(S,S̅),N)=(C_m,(S,S̅),N).
This was shown to be false in Ref. MR3513725, namely it was proved that '(C_4,(S,S̅), 2) = 3 < 4 = (C_4, (S,S̅), 2), where S={1,3}, S̅={2,4}.
In Ref. MR3513725, the cyclic graph C_4 was depicted as in Figure <ref>, (a), where the vertices in S are on the left and vertices in S̅ on the right.



This raised the question whether weaker forms of a quantum max-flow/min-cut conjecture might be true, such as the following (stated for simplicity only for cyclic graphs):


  For any partition (S,S̅) of the external edges, there exists N_0 such that, for all N≥ N_0,
  
    '(C_m, (S, S̅), N) = (C_m, (S,S̅), N).



We will be particularly interested in the case m=2d, where S corresponds to the odd-labeled indices and S̅ to the even-labeled indices, as in Figure <ref>, (b).
We will write (S,S̅)=(,) accordingly.
The example from Ref. MR3513725 is of this form, see Figure <ref>, (b).
Numerical evidence reported in Ref. MR3613509 suggested a cyclic dependency of '(C_4, (,), N) on N  4 in the situation of Figure <ref>, and, therefore, that Conjecture <ref> is false.
Our first result proves that this is indeed the case:


  For all N,
  
    '(C_4,(,),N) ≤
      N^2    if N ≡ 0,1  4
    
      N^2 - 1    if N ≡ 2,3  4,

  while (C_4,(,),N)=N^2 for all N.
  Moreover, equality holds for all square bond dimensions N=k^2, so in an infinite number of cases where N≡0,14.


Numerical evidence suggests that our bound is tight.<cit.>
For m > 4, numerical evidence is much harder to obtain.
Yet we provide a partial generalization of Theorem <ref> to higher cycles:


  For all d≡24 and N,
  
    '(C_2d,(,),N) ≤
      N^d    if N ≢3 4
    
      N^d - 1    if N≡ 3 4,

  while (C_2d,(,),N)=N^d for all N.
  Again we have equality for all N=k^2.


We prove Theorems <ref> and <ref> in <ref>.


As suggested in Ref. MR3613509, one might instead consider a weaker version of Conjecture <ref>, where we only demand that equality holds for some (and hence infinitely many) N>1.
As evidence, Ref. MR3613509 proved that for all G, (S,S̅), as functions of N, we have '(G,(S,S̅),N)=(G,(S,S̅),N)(1-o(1)) (cf. Refs. hayden2016holographic,nezami2016multipartite, where a similar result was proved in the scenario where we place different tensors at each site).








For N=2, our bound in Theorem <ref> can be improved.
This is shown by our next result, which gives an infinite sequence of graphs with constant bond dimension for which the quantum max-flow is strictly smaller than the quantum min-cut.


  For all d≥2,
  
    '(C_2d,(,),2) ≤3/4 2^d < 2^d = (C_2d,(,), 2).


Theorem <ref> puts the observation in Ref. MR3513725 that '(C_6,(,),2)=6<8 into a general context.
We prove Theorem <ref> in <ref>.
Interestingly, the rank defect is of a nonlinear origin, unlike in our preceding theorems.
Numerical calculations up to d=10 suggest that our bound is tight.


If N=n=k^2 for some integer k, then (C_m, k^2, k^2) consists of the diagonal degenerations of the m-times iterated k× k-matrix multiplication tensor

    ^m_k:=∑_i_p =1^k (a_1)^i_1_i_2⊗ (a_2)^i_2_i_3⊗⋯⊗ (a_m-1)^i_m-1_i_m⊗ (a_m)^i_m_i_1,

where {(a_p)^i_j}_ij = 1  k is a basis of the p-th copy of A. The variety TNS(C_m,k^2,k^2) is the closure of the image via Φ of the GL(A)-orbit of the tensor T = ∑ a^i_j ⊗β^j_k ⊗ b^k_i, where { a^i_j }_ij = 1  k is a basis of A and {  b^i_j }_ij = 1  k is a basis of B with dual basis {β^j_i }_ij = 1  k. In fact, T = ^3_k regarded as an element of A ⊗ B^* ⊗ B and Φ(T) = ^m_k.

The ranks of the flattenings of ^m_k are known (see, e.g., Refs. MR3513064,BuhChrZui:NondetQuantumComCompl):
when m=2d and S={1 d}, S̅={d+1 2d}, the quantum min-cut is k^4 and indeed the flattening is of maximal rank k^4.
Similarly, in the case that (S,S̅)=(,), the quantum min-cut as well as the rank of the flattening are equal to k^2d.
Thus:

    '(C_2d,(,),k^2)=k^2d=(C_2d,(,),k^2)

for all k.
This shows the equality statements in Theorems <ref> and <ref>.





 §.§ Notation and conventions


A, B are complex vector spaces respectively of dimensions N,n.
(A) denotes the group of invertible linear maps A A and _d denotes the permutation group on d elements.
We denote the elements of _d, the cyclic group of order d, by [k] for k∈.
We write S^mA and mA for the symmetric and antisymmetric subspaces of A^ m, respectively.






§ PROOF OF THEOREMS <REF> AND <REF>



We already showed in Remark <ref> that we have equality in all square dimensions N=k^2, so we only need to establish the upper bound.
We first prove Theorem <ref>, which rigorously establish the defects observed in Ref. MR3613509 and Theorem <ref>.




 §.§ Proof of Theorem <ref>




It is clear from the cyclic symmetry of the tensor network in Figure <ref>, (b) that Φ(T)∈ A^ 4 has a cyclic _4-symmetry, generated by π=(1 2 3 4).
Thus we need to understand the invariant subspace (A^4)^_4.

For this, we order the tensor factors of A^4 as (A_1 A_3)(A_2 A_4), corresponding to the flattening Φ(T)_, of interest.
We claim that

    (A^4)^_4⊆ S^2(S^2A) 2(2A)
    ⊆ S^2A S^2A 2A2A
    ⊆ (A_1 A_3)(A_2 A_4).

(In fact, the first inclusion is an equality.)
To see this, recall that the _4-symmetry is generated by π=(1 2 3 4).
Since π^2=(1 3)(2 4), it is clear that (A^4)^_4⊆ S^2A S^2A 2A2A.
Now note that π acts block diagonally with respect to the direct sum.
In fact, π=(1 3)τ, where τ=(1 2)(3 4), so π and τ have the same action on S^2A S^2A, while π acts by -τ on 2A2A.
But τ interchanges A_1 A_3 with A_2 A_4, so it follows that the _4-invariant subspace lives in S^2(S^2A) 2(2A).
This establishes (<ref>).
























































Now, (<ref>) implies that the linear map Φ(T)_, is block diagonal, mapping the symmetric subspace of A_1^* A_3^* to the symmetric subspace of A_2 A_4, and the anti-symmetric subspace to the anti-symmetric subspace.
Moreover, the first block is given by a symmetric matrix, while the second block is given by a skew-symmetric matrix.
Since the rank of a skew-symmetric matrix is always even, while 2A=1/2N(N-1) is even if and only if N≡0,14, we find that

    '(C_4,(,),N)
    ≤
        N^2    if N ≡ 0,1  4,
    
        N^2 - 1    if N ≡ 2,3  4.

(The N=2 case will be re-proved geometrically in <ref>. It also follows by a direct computation, as was done
in Ref. MR3513725.)




 §.§ Proof of Theorem <ref>


Now consider a general graph C_2d with d≡24.
Again, Φ(T)∈ A^2d has a _2d-symmetry, generated by π=(1 2 3 ⋯ 2d), so we focus on the _2d-invariant subspace of A^ 2d.

We first note that π^2=(1 3 ⋯ 2d-1)(2 4 ⋯ 2d).
Both (1 3 ⋯ 2d-1) and (2 4 ⋯ 2d) are d-cycles, permuting the odd and even subsystems, respectively.
We can decompose A^ d = ⊕_z V_z into the eigenspaces of such a d-cycle, where z runs over the d-th roots of unity.
Thus the invariance by π^2 implies that

    (A^ 2d)^_2d⊆⊕_z V_z  V_z̅,

where as before we use the odd-even ordering of tensor factors.
Since d is even, z=-1 is a possible eigenvalue.
Next, note that π=(1 3 ⋯ 2d-1)τ=τ(2 4 ⋯ 2d), where τ=(1 2)(3 4)⋯ (2d-1 2d) interchanges the odd and even subsystems.
It follows that π acts by τ on V_1 V_1, by -τ on V_-1 V_-1, and by [   0 z̅τ;  zτ   0 ] on V_z V_z̅ V_z̅ V_z.
In particular,

    (A^ 2d)^_2d⊆ S^2(V_1) 2(V_-1) ⊕_z≠±1 V_z  V_z̅.

(For d=2, the only eigenspaces are V_1=S^2A and V_-1=2A, so (<ref>) reduces to (<ref>).)

As before, (<ref>) implies that Φ(T)_, is block diagonal (e.g., with respect to the three direct summands) and the block that maps V_-1^* to V_-1 is given by a skew-symmetric matrix.
We now compute the dimension of the eigenspace V_-1.


  Let d=2(2a+1).
  Then, V_-1 = 1/2a+1∑_b=1^2a+1N^(2a+1,b) 2.
  In particular, V_-1 is odd if N≡34.


Consider the representation of _d on V=(^N)^ d by cyclically shifting tensor factors.
It is straightforward to evaluate its character χ_d→ in the standard product basis, a_i_[1] a_i_[d], where we label the indices by _d rather than {1,…,d} so that it is straightforward to implement the shift:
For all k∈{1 d},

    χ([k])
    = ∑_i_[1],…,i_[d]∈{1,…,N}∏_j=1^d δ_i_[j], i_[j+k]
    = N^|_d/k_d|
    = N^(d, k),

since we have one free index to choose per orbit of the shift by [k].
The dimension of the -1 eigenspace is the multiplicity of the sign representation in V, so given by the normalized inner product

    V_-1 = 1/d∑_k=1^d (-1)^k χ([k]) = 1/d∑_k=1^d (-1)^k N^(d,k).

Using d=2(2a+1), we can calculate the numerator as

    ∑_k=1^d (-1)^k N^(d,k)
    = ∑_b=1^2a+1 N^(d,2b) - N^(d,2b-1)
    = ∑_b=1^2a+1 N^2(2a+1,b) - N^(2a+1,2b-1)
    
    = ∑_b=1^2a+1 N^2(2a+1,b) - N^(2a+1,b)
    = ∑_b=1^2a+1 N^(2a+1,b)( N^(2a+1,b) - 1 ).

In the third step, we substituted 2b-1 by b (since this defines a bijection of _2a+1 and (2a+1,b) only depends on b modulo 2a+1, the sum is left unchanged).
Thus the multiplicity (<ref>) is given by

    V_-1
    = 1/d∑_b=1^2a+1 N^(2a+1,b)( N^(2a+1,b) - 1 )
    = 1/2a+1∑_b=1^2a+1N^(2a+1,b) 2

This establishes the first claim.
For the second, assume that N≡34.
In order to prove that V_-1 is odd, it suffices to show that each binomial coefficient is odd.
But indeed, since 2a+1 is odd, so is (2a+1,b).
This implies that N^(2a+1,b)≡ 34 for all b, which precisely ensures that the binomial coefficients are odd.


As before, Lemma <ref> implies that Φ(T)_, has a rank defect if N≡34; this establishes Theorem <ref>. 


Numerical experiments suggest that there is a rank defect for all even d, not just for d≡24.






§ THE VARIETY OF TENSOR NETWORK STATES PTNS(C_M,N,E)


In this section we discuss some general features of the variety (C_m,N,n).
In particular, we show that, for N,n≥ m, the smallest linear subspace containing the variety is (A^ m)^_m.

Let v_m( A):={ [p] | p=ℓ^⊗ m for some  0≠ℓ∈ A}⊆(S^mA) denote the Veronese variety of m-th powers of linear forms.
For any variety X⊆ V, let

    _r(X):=⋃_x_1 x_r∈ X{x_1 x_r}

denote the r-th secant variety of X, so _r(v_m( A))⊆(S^mA) is the Zariski closure of the set of homogeneous polynomials of degree m in N variables that may be written as the sum of r m-th powers of linear forms.

Observe that (C_m,N,n) contains the variety σ_n(v_m( A))⊆(S^mA).
Indeed, consider the tensor

    T=a_1 b_1^̱1+…+a_n b_n^̱n,

where b_1 b_n is a basis of B, with dual basis ^̱1^̱n.
Then (<ref>) implies

    Φ(T) = a_1^ m+…+a_n^ m.

If the a_i are chosen as general points of A, this projectivizes to a general point of _n(v_m( A)), and by (A)-invariance of the image, the whole variety must be contained in (C_m,N,n).

Not every Φ(T) is contained in S^mA (outside of the trivial case n=1 which we exclude from consideration).
E.g., for m=2d, consider the tensor

    T=a_1 b_1^̱2 + a_2 b_2^̱1.

Then, with respect to the odd-even ordering of tensor factors,

    Φ(T) = a_1^ d a_2^ d + a_2^ d a_1^ d

which is not in S^m A.

Now assume that N,n≥ m and consider the tensor

    T = a_1 b_1^̱m+a_2 b_2^̱1+…+a_m-1 b_m-1^̱m-2+a_m b_m^̱m-1.

Then Φ(T) is the sum of the terms in the _m-orbit of a_1 a_2 a_m-1 a_m.
But such vectors span (A^ m)^_m.
In summary:


If N,n≥ m, then ((C_m,N,n))=(A^ m)^_m.


It follows that rank violations that are not explained by the _m-symmetry must be of a nonlinear origin.
We will see such a phenomenon in the next section.




§ PROOF OF THEOREM <REF>



In this section, we give a geometric construction of the relevant tensor network variety and prove Theorem <ref>.




 §.§ A geometric construction of PTNS(C_2d,2,2)


Let A=B=^2, let a_0, a_1 be a basis of A with dual basis α^0, α^1 of A^*, and b_0, b_1 a basis of B with dual basis β^0, β^1 of B^*.

Consider the image under Φ of the line

    L[μ,ν]:=[μ(a_0 b_0^̱0+a_1 b_1^̱1)+ν(a_0 b_0^̱1+a_1 b_1^̱0)] ⊆(A B B^*)=7.

In <ref> we discussed the special cases ν=0 and μ=0. When ν=0, we obtain the point [a_0^ 2d+a_1^ 2d], which is a general point of the variety _2(v_2d( A)) ⊆(S^2dA), which has dimension 3. When μ=0, we obtain [a_0^ d a_1^ d+a_1^ d a_0^ d] ∉(S^2dA). Consider the closure of the union of the (A)-orbits of the points of Φ(L[μ,ν]), that is (̅A̅)̅ ̅·̅Φ̅(̅L̅[̅μ̅,̅ν̅]̅)̅: this is an irreducible projective variety of dimension 4 sitting inside (C_2d,2,2) because (A)=3 and the stabilizer of [a_0^ 2d+a_1^ 2d] in (A) is finite.

But Φ is a rational map from (A B B^*)=7 whose fibers have dimension at least (B)=3.
Thus the Zariski closure of its image (C_2d,2,2) is an irreducible variety of dimension at most 4, so (C_2d,2,2)=(A)·Φ(L[μ,ν]).
We summarize:


  The variety (C_2d,2,2) coincides with the variety (A) ·Φ(L[μ,ν]).


We adopt the following notation:  denotes a 2d-tuple of elements in {0,1}, and  and  denote d-tuples of elements in {0,1}. We use odd indices for the entries of  and even indices for the entries of . We write ⌣ for the 2d-tuple obtained by interlacing  and . Thus, if = (η_1,η_3 η_2d-1) and = (_2,_4 _2d) then = ⌣ = (η_1 , _2,η_3 _2d). We write a_ etc. for the corresponding basis vectors. For example, the contraction of a_⌣ by α^ is a_. All indices are to be read modulo 2d.

For every ∈{ 0 ,1}^2d, define

    () = ∑_i=1^2dδ_i⊞δ_i+1,

where ⊞ denotes the XOR operation, i.e., δ_i⊞δ_i+1=1 if δ_i≠δ_i+1 and δ_i⊞δ_i+1=0 otherwise. The value () counts the number of changes between 0 and 1 that one observes cyclically reading .
Directly from (<ref>), we observe that () determines the coefficient of  in Φ(L(μ,ν)).
Explicitly,

    Φ(L(μ, ν))
    = ∑_μ^2d - ()ν^()  a_
    = ∑_c [μ^2d-cν^c ∑_()=c a_].

Moreover () is always even. See Figure <ref> for a schematic representation of the contribution of μ or ν in the contraction:




The image of L[μ,ν] under Φ is a rational normal curve of degree d, as opposed to the naïve 2d.
Indeed, since only even powers of μ and ν appear, one can reparametrize the image setting μ'=μ^2,ν'=ν^2, showing that it is a rational curve of degree at most d.
Moreover, observe that for every even c = 0,2  2d there exists a d-tuple  such that () = c and the corresponding a_'s are linearly independent.
This shows that Φ(L[μ,ν]) spans a d-dimensional subspace of (A^⊗ 2d), which guarantees that it is a normal curve and that its degree is (at least) d.






 §.§ Proof of Theorem <ref>


Let F:=  (Φ(L(μ,ν)))_, be the flattening of interest for some general choice of [μ,ν] ∈1.
Since the rank of the flattening is (A)-invariant, it is sufficient to prove (F) ≤3/4 2^d, as Φ(L[μ,ν]) is a general point of (C_2d,2,2).

We describe a set of elements in the kernel of F.
Let S ⊆={1,3,…,2d-1} be a non-empty subset of even cardinality, | S | = 2p.
Let D_S = (α^0 ⊗α^1)^ p - (α^1 ⊗α^0)^ p∈ (A^*)^ S and let

    K_S = D_S ⊗ (α^0 - α^1)^ (d - 2p)∈ (A^*)^ S⊗ (A^*)^ (∖ S) = (A^*)^.

In this section, we will prove that K_S ∈(F) for every S and that the K_S's span a subspace of dimension at least 2^d-2.
This provides (F) ≤ 2^d - 2^d-2 =3/4 2^d and therefore '(C_2d,(,),2) ≤3/4 2^d, establishing Theorem <ref>.


For any fixed S⊆, the basis vectors α^ in the support of K_S are labeled by d-tuples  that are in one-to-one correspondence with elements in {0,1}×{0,1}^d-2p as follows (here ' denote a (d-2p)-tuple):

    {0,1}×{0,1}^d-2p   →{0,1}^S ×{0,1}^∖ S≅{0,1}^
    
      (0,')    ↦ ((0,1,…,0,1), '), 
    
      (1,')    ↦ ((1,0,…,1,0), ').

We denote the elements of {0,1}×{0,1}^d-2p by =(t,') and identify them with their image.
The coefficient of α^ in K_S is ():=(-1)^t + |'|, where |'| is the sum of the entries of ', as can be readily seen from (<ref>).
Thus, K_S = ∑_() α^, and if we plug this into (<ref>) then we obtain

    F(K_S)
    = ∑_(∑_() μ^2d - (⌣)ν^(⌣)) a_.

Thus we can read off the following criterion:


  The coefficient of a_ in F(K_S) is zero if there exists a permutation Θ_ of {0,1}×{0,1}^d-2p such that, for every , (⌣)=(Θ_()⌣) while (Θ_())=-().


We now show that such permutations always exist, which proves that each K_S is in the kernel.


For every subset S⊆={1,3,…,2d-1} of even cardinality, and for every =(_2,…,_2d), there exists a permutation Θ_ as in Lemma <ref>.
As a consequence, each K_S∈(F).


We distinguish two cases.
First, assume that there exists an odd index k∉S such that _k-1≠_k+1.
Define an involution Θ_ that replaces η_k by its complement η_k⊞1 (i.e., if η_k=0, it is replaced by 1, and vice versa) while leaving all other elements the same.
Then (Θ_())=-() for every .
Moreover, (Θ_())=() because the only two terms in the summation (<ref>) that involve η_k are

    (_k-1⊞η_k) + (η_k ⊞_k+1) = (0 ⊞η_k) + (1 ⊞η_k) = 1,

so their sum is independent of the value of η_k.

Now assume that _k-1=_k+1 for all odd k∉S.
Define an involution Θ_(t,') = (t⊞1,'), i.e., every entry η_k for k∈ S is reversed while all other entries are unchanged.
Again, it is clear that (Θ_())=-() for every .
We now argue that (Θ_())=().
Let S={k_1<…<k_2p}.
Then the only terms in the summation (<ref>) that involve indices in S are

    ∑_j=1^2p( (η_k_j⊞_k_j+1) + (_k_j+1-1⊞η_k_j+1) )

where we set k_2p+1:=k_1.
Note that _k_j+1=_k_j+1-1 (for k_j+1=k_j+2 this is trivial, otherwise use the assumption).
Moreover, η_k_j = 1 - η_k_j+1, which remains true when we apply Θ_.
As a consequence, applying Θ_ only exchanges 0 and 1 in each summand of (<ref>), and the total is preserved.


To conclude the proof of Theorem <ref>, it remains to show that =  { K_S : ∅≠ S ⊆, | S | even} is of dimension at least 2^d-2.
In fact, we will prove that _(1) = { K_S : 1∈ S⊆, | S| even} has dimension equal to 2^d-2.
Note that there are exactly 2^d-2 subsets S of {1,3,…,2d-1} with even cardinality that contain 1.
Therefore, we need to show that the corresponding K_S are linearly independent.
We start with the following lemma:


We have _(1) = _(1,3)_(1,3̅), where _(1,3) := { K_S : 1,3∈ S ⊆, | S| even} and _(1,3̅) := { K_S : 1∈ S ⊆, 3∉S, | S| even}.
Further, _(1,3) = _(1,3,5)_(1,3,5̅), where _(1,3,5) := { K_S : 1,3,5∈ S ⊆, | S| even} and _(1,3,5̅) := { K_S : 1,3∈ S ⊆, 5∉S, | S| even}.


Clearly _(1,3) and _(1,3̅) generate _(1).
It remains to show that their intersection is trivial.
Say it were not and let v∈_(1,3)∩_(1,3̅) be nonzero.
Choose generic projections A^* → on the factors 5  2d-1 of (A^*)^, and consider the image of v in A^* ⊗ A^*.
On the one hand, since v ∈_(1,3), the image is of the form x α^0 ⊗α^1 + y α^1 ⊗α^0
By the genericity of the projections, we may assume that both x and y are nonzero, so that the tensor has rank two.
On the other hand, since v ∈_(1,3̅), the image is of the form of (z α^0 + w α^1) ⊗ (α^1 - α^0), a rank-one tensor.
This is a contradiction.
The second statement is proved analogously.


We now show that _(1) has the desired dimension.


For d≥2, we have that _(1) = 2^d-2.


We will prove that ^(d)_(1) = 2^d-2 and ^(d)_(1,3) = 2^d-3 by induction on d.
The base cases are as follows:
^(2)_(1)=⟨ K_{1,3}⟩,
^(3)_(1)=⟨ K_{1,3}, K_{1,5}⟩, and
^(3)_(1,3)=⟨ K_{1,3}⟩
(recall we only consider nonempty subsets of even cardinality).

Now let d≥4.
Using Lemma <ref>, we have

    ^(d)_(1)
    = ^(d)_(1,3)^(d)_(1,3̅),   ^(d)_(1,3)
    = ^(d)_(1,3,5)^(d)_(1,3,5̅).

Note that ^(d)_(1,3̅)⊆ (α^0-α^1) (A^*)^(∖{3}), so we see that ^(d)_(1,3̅)≅^(d-1)_(1).
Similarly, ^(d)_(1,3,5̅)⊆ (α^0-α^1) (A^*)^(∖{5}) and ^(d)_(1,3,5̅)≅^(d-1)_(1,3).
Finally, note that ^(d)_(1,3,5)≅^(d-2)_(1).
Indeed, both spaces have the same number of generators; contraction with a_0 a_1 + a_1 a_0 ∈ A^{1,3} maps each generator K_S onto a generator K_S', where S' = { k - 4 : k ∈ S, k≠1,3}; all the latter are distinct and therefore linearly independent by the induction hypothesis.
Thus:

    ^(d)_(1)≅^(d)_(1,3)^(d-1)_(1),   ^(d)_(1,3)≅^(d-2)_(1)^(d-1)_(1,3),

and so

    ^(d)_(1,3) = 2^(d-2)-2 + 2^(d-1)-3 = 2^d-3,   ^(d)_(1) = 2^d-3 + 2^(d-1)-2 = 2^d-2

using the induction hypothesis.
This concludes the proof.


Proposition <ref> and Lemma <ref> together establish Theorem <ref>.



We thank Shrawan Kumar for a suggestion regarding the proof of Lemma <ref>.

Gesmundo supported by the European Research Council (ERC Grant Agreement no. 337603), the Danish Council for Independent Research (Sapere Aude), and VILLUM FONDEN via the QMATH Centre of Excellence (grant no. 10059).
Landsberg supported by NSF DMS-1405348 and NSF CCF-1814254.
Walter acknowledges support by the Simons Foundation, AFOSR (grant no. FA9550-16-1-0082), and the NWO (grant no. 680-47-459).







