format: text

text:
# A semidefinite program for distillable entanglement

## 1 Introduction

One of the central problems of quantum information theory is entanglement distillation (, ): the production of (approximate) maximally entangled states from a collection of non-maximally entangled states. Of particular interest are 1-locally distillable entanglement and 2-locally distillable entanglement (the amount of entanglement that can be distilled using local operations and a 1-way (2-way) classical channel). Nearly all of the known upper bounds on 1- or 2-locally distillable actually apply to a larger class of operations, known as p.p.t. (positive partial transpose) operations . This motivates our present study of p.p.t. distillable entanglement.

We study distillable entanglement via a more refined quantity, the “fidelity of distillation”, which measures how close one can come to producing a $`K`$-dimensional maximally entangled state from a given input. In Theorem 3.1 below, we show that the fidelity of p.p.t. distillation can be expressed as the solution to a certain semidefinite program (see  for a survey of semidefinite programming). Then any feasible solution to the dual problem (Theorem 3.3) gives us an upper bound on fidelity of distillation.

The rest of the paper is devoted to an exploration of the consequences of this semidefinite program. Section 4 gives a number of results that hold in general, including a new bound combining the bounds of  and , and a theorem to the effect that maximally entangled states cannot be used to catalyze fidelity of p.p.t. distillation. In section 5, we show that the semidefinite program simplifies in the presence of symmetries; in some cases (e.g., isotropic states, Werner states), this simplification turns the semidefinite program into a linear program. In the case of asymmetric Werner states, this linear program can be solved exactly, showing that the upper bound of  is tight in that case. Section 6 sketches a technique for producing asymptotic lower bounds, which we then use to strengthen the hashing lower bound  in the p.p.t. case. We also use this technique to partially resolve a conjecture of  by determining the p.p.t. distillable entanglement of “maximally correlated” states. Finally, in section 7, we consider possible applications of semidefinite programming to the problems of quantum codes and 1-local distillation. In particular, using the techniques of section 5, we give a new derivation of the linear programming bound for quantum codes , , .

## 2 Operators, superoperators and operations

If $`V`$ is a Hilbert space, we denote by $`(V)`$ the space of Hermitian operators on $`V`$. We also let $`𝒫(V)(V)`$ denote the convex cone of positive semi-definite Hermitian operators; we will freely write $`AB`$ to mean $`AB𝒫(V)`$. A state is then an element of $`𝒫(V)`$ of trace 1. Quantum information theory can be thought of as studying the behavior of these concepts under tensor products.

Given an operator $`A(VW)`$, we define the “partial trace” $`\mathrm{Tr}_V(A)`$ to be the (unique) operator in $`(W)`$ such that

$$\mathrm{Tr}(\mathrm{Tr}_V(A)B)=\mathrm{Tr}(A(B1)),$$
(2.1)
for all $`B(W)`$. Similarly, given a choice of basis for $`W`$, we can define the partial transpose $`A^{\mathrm{\Gamma }_W}`$ by

$$\mathrm{Tr}(A^{\mathrm{\Gamma }_W}(BC))=\mathrm{Tr}(A(BC^t)),$$
(2.2)
where $`B(V)`$, $`C(W)`$, and $`C^t`$ is the transpose of $`C`$ with respect to the chosen basis. Both of these transformations extend by linearity to non-Hermitian operators as well.

A positive operator $`C𝒫(VW)`$ is said to be “separable” if it can be written in the form

$$C=\underset{i}{}A_iB_i,$$
(2.3)
with $`A_i𝒫(V)`$, $`B_i𝒫(W)`$; in other words,

$$C𝒫(V)𝒫(W).$$
(2.4)
Similarly, $`C`$ is said to be p.p.t. (positive partial transpose) if

$$C𝒫(VW)𝒫(VW)^{\mathrm{\Gamma }_W};$$
(2.5)
note that this does not depend on the choice of basis in $`W`$. We also recall that every p.p.t. operator is separable:

$$𝒫(V)𝒫(W)𝒫(VW)𝒫(VW)^{\mathrm{\Gamma }_W}.$$
(2.6)
A “superoperator” from $`V`$ to $`V^{}`$ is a linear transformation from $`(V)`$ to $`(V^{})`$. The space of superoperators can be naturally identified with $`(VV^{})`$; to a superoperator $`\mathrm{\Psi }`$ corresponds the unique operator $`\mathrm{\Omega }(\mathrm{\Psi })`$ such that

$$\mathrm{Tr}(B\mathrm{\Psi }(A))=\mathrm{Tr}\left(\mathrm{\Omega }(\mathrm{\Psi })\left(AB\right)\right).$$
(2.7)
We also define the adjoint superoperator $`\mathrm{\Psi }^{}`$ by

$$\mathrm{Tr}(A\mathrm{\Psi }^{}(B))=\mathrm{Tr}(B\mathrm{\Psi }(A)).$$
(2.8)
Note that

$`\mathrm{\Psi }(A)`$ $`=\mathrm{Tr}_V(\mathrm{\Omega }(\mathrm{\Psi })(A1))`$ (2.9)
$`\mathrm{\Psi }^{}(B)`$ $`=\mathrm{Tr}_V^{}(\mathrm{\Omega }(\mathrm{\Psi })(1B))`$ (2.10)
and, if $`\mathrm{\Psi }_1:(V)(V^{})`$ and $`\mathrm{\Psi }_2:(V^{})(V^{\prime \prime })`$, then

$$\mathrm{\Omega }(\mathrm{\Psi }_2\mathrm{\Psi }_1)=(\mathrm{\Psi }_1^{}1)(\mathrm{\Omega }(\mathrm{\Psi }_2))=(1\mathrm{\Psi }_2)(\mathrm{\Omega }(\mathrm{\Psi }_1))=\mathrm{Tr}_V^{}((\mathrm{\Omega }(\mathrm{\Psi }_1)1_{V^{\prime \prime }})(1_V\mathrm{\Omega }(\mathrm{\Psi }_2))).$$
(2.11)
Of particular interest is the (self-adjoint) superoperator $`AA^t`$; in that case, we find

$$\mathrm{\Omega }(t)=\underset{i,j}{}(v_iv_i)(v_jv_j)^{}0.$$
(2.12)
A superoperator is said to be “positive” if $`\mathrm{\Psi }(A)0`$ whenever $`A0`$, and “trace-preserving” if $`\mathrm{\Psi }^{}(1)=1`$; equivalently, $`\mathrm{Tr}_V^{}(\mathrm{\Omega }(\mathrm{\Psi }))=1`$. A superoperator is “completely positive” if it satisfies any of the following equivalent conditions:

* (1) $`1_V\mathrm{\Psi }`$ is positive
* (2) For all Hilbert spaces $`W`$, $`1_W\mathrm{\Psi }`$ is positive
* (3) There exist operators $`A_i\mathrm{Hom}(V,V^{})`$ such that

$$\mathrm{\Psi }(A)=\underset{i}{}A_iAA_i^{}.$$
(2.13)
* (4) For any (some) basis of $`V`$, the partial transpose $`\mathrm{\Omega }(\mathrm{\Psi })^{\mathrm{\Gamma }_V}`$ is positive semi-definite.

Clearly $`21`$, and $`32`$ is straightforward. To see $`14`$, it suffices to observe that

$$\mathrm{\Omega }(\mathrm{\Psi })^{\mathrm{\Gamma }_V}=(1_V\mathrm{\Psi })(\mathrm{\Omega }(t))0.$$
(2.14)
Finally, $`43`$ follows by taking an eigenvalue decomposition of $`\mathrm{\Omega }(\mathrm{\Psi })^{\mathrm{\Gamma }_V}`$. Since the operators we will be dealing with in the sequel are mostly completely positive, we define $`\mathrm{\Omega }^{}(\mathrm{\Psi })=\mathrm{\Omega }(\mathrm{\Psi })^{\mathrm{\Gamma }_V}`$, and use this to identify the space of superoperators with $`(VV^{})`$. Thus the set of completely positive superoperators is identified with $`𝒫(VV^{})`$. An “operation” is defined to be a completely positive, trace-preserving superoperator; we denote the (convex) set of operations from $`V`$ to $`V^{}`$ by $`Op(V,V^{})`$.111This differs somewhat from the definition of operation given in , in that we are assuming operations to be “non-measuring”, but by the main result of that paper, this incurs no loss of generality when studying entanglement distillation.

On tensor product spaces, there are several classes of operations of interest, which can be defined in terms of the convex sets $`𝒫`$ and $`Op`$ as follows:

* $`ϵ`$-local: $`𝒞_ϵ=Op(V,V^{})Op(W,W^{})`$.
* $`1`$-local: $`𝒞_1=(𝒫(VV^{})Op(W,W^{}))Op(VW,V^{}W^{})`$.
* $`1^{}`$-local: $`𝒞_1^{}=(Op(V,V^{})𝒫(WW^{}))Op(VW,V^{}W^{})`$.
* separable: $`𝒞_\$=(𝒫(VV^{})𝒫(WW^{}))Op(VW,V^{}W^{})`$.
* p.p.t.: $`𝒞_\mathrm{\Gamma }=Op(VW,V^{}W^{})Op(VW,V^{}W^{})^{\mathrm{\Gamma }_{WW^{}}}`$.

We also have the class of 2-local operations, defined by allowing arbitrary compositions of 1-local and $`1^{}`$-local operations. For a different approach to defining these classes, see . We recall

$$𝒞_ϵ𝒞_1,𝒞_1^{}𝒞_2𝒞_\$𝒞_\mathrm{\Gamma },$$
(2.15)
with all inclusions strict in general. (The class $`𝒞_ϵ`$, not discussed in , is simply the closure of the class of local operations under convex linear combinations (i.e., shared randomness).)

From a physical perspective, the only natural classes are those of $`(ϵ,1,1^{},2)`$-local operations. The difficulty, however, is that in none of these cases do we have an effective way to decide whether a given operation belongs to the class; this is especially true in the case of 2-local operations. Thus the class of separable operations is important as a simplification of the class of 2-local operations, while the class of p.p.t. operations is important as the smallest class containing the 2-local class for which we can effectively decide membership. For instance, all of the known upper bounds on 2-locally distillable entanglement are really bounds on p.p.t. distillable entanglement; to a large extent this even applies to upper bounds on 1-locally distillable entanglement. Similarly, a lower bound on p.p.t. distillable entanglement provides a limit on how far the current methods can take us.

## 3 Fidelity of distillation

For any integer $`K>0`$, we define the “maximally entangled” state $`\mathrm{\Phi }(K)(^K^K)`$ by

$$\mathrm{\Phi }(K)=\frac{1}{K}\mathrm{\Omega }^{}(1_^K)=\frac{1}{K}\underset{1i,jK}{}(e_ie_i)(e_je_j)^{}.$$
(3.1)
Given any other state $`\rho `$, the “fidelity” of $`\rho `$ is defined by

$$F(\rho )=\mathrm{Tr}(\mathrm{\Phi }(K)\rho ).$$
(3.2)
###### Definition 1.

Let $`\rho 𝒫(VW)`$ be a state, and let $`K>0`$ be an integer. The “fidelity of $`K`$-state p.p.t. distillation” $`F_\mathrm{\Gamma }(\rho ;K)`$ is defined by

$$F_\mathrm{\Gamma }(\rho ;K)=\underset{\mathrm{\Psi }}{\mathrm{max}}F(\mathrm{\Psi }(\rho )),$$
(3.3)
where $`\mathrm{\Psi }`$ ranges over all p.p.t. operations from $`(VW)`$ to $`(^K^K)`$.

###### Remark.

We can define $`F_ϵ`$, $`F_1`$, $`F_2`$, etc., similarly.

This is a refinement of the concept of distillable entanglement; indeed, we can define (see , ):

###### Definition 2.

Let $`\rho `$ be as above. The p.p.t. distillable entanglement $`D_\mathrm{\Gamma }(\rho )`$ of $`\rho `$ is defined to be the supremum of all positive numbers $`r`$ such that $`lim_n\mathrm{}F_\mathrm{\Gamma }(\rho ^n;2^{rn})=1`$.

Thus a study of $`F_\mathrm{\Gamma }`$ is likely to provide insights into $`D_\mathrm{\Gamma }`$, as we shall indeed find below.

We first observe that the optimization problem defining $`F_\mathrm{\Gamma }`$ can be rewritten as an optimation over operators:

###### Theorem 3.1.

For any state $`\rho `$ and any positive integer $`K`$,

$$F_\mathrm{\Gamma }(\rho ;K)=\underset{F}{\mathrm{max}}\mathrm{Tr}(F\rho ),$$
(3.4)
where $`F`$ ranges over Hermitian operators such that

$$0F1,1/KF^\mathrm{\Gamma }1/K.$$
(3.5)
###### Proof.

Let $`\mathrm{\Psi }`$ be the operation maximizing $`F(\mathrm{\Psi }(\rho ))`$ in the definition of $`F_\mathrm{\Gamma }(\rho ;K)`$. Clearly, if we compose $`\mathrm{\Psi }`$ with any operator of the form $`U\overline{U}`$, this leaves $`F(\mathrm{\Psi }(\rho ))`$ unchanged. The same must then be true after averaging over $`U(K)`$ (“twirling” ). We may thus assume $`\mathrm{\Psi }=𝐓\mathrm{\Psi }`$, where $`𝐓`$ is the twirling superoperator. We find

$$𝐓(A)=\mathrm{Tr}(A\mathrm{\Phi }(K))\mathrm{\Phi }(K)+\frac{1}{K^21}\mathrm{Tr}(A(1\mathrm{\Phi }(K)))(1\mathrm{\Phi }(K));$$
(3.6)
$`𝐓(A)`$ must have the form $`a\mathrm{\Phi }(K)+b(1\mathrm{\Phi }(K))`$, and since

$$\mathrm{Tr}(𝐓(A))=\mathrm{Tr}(A)\text{and}\mathrm{Tr}(𝐓(A)\mathrm{\Phi }(K))=\mathrm{Tr}(A\mathrm{\Phi }(K)),$$
(3.7)
we can solve for $`a`$ and $`b`$. It follows that

$$\mathrm{\Omega }(𝐓)=\mathrm{\Phi }(K)\mathrm{\Phi }(K)+\frac{1}{K^21}(1\mathrm{\Phi }(K))(1\mathrm{\Phi }(K))=\mathrm{\Omega }^{}(𝐓)$$
(3.8)
But then we compute

$`\mathrm{\Omega }^{}(\mathrm{\Psi })=\mathrm{\Omega }^{}(𝐓\mathrm{\Psi })`$ $`=(\mathrm{\Psi }^{}1)(\mathrm{\Omega }^{}(𝐓))`$ (3.9)
$`=\mathrm{\Psi }^{}(\mathrm{\Phi }(K))\mathrm{\Phi }(K)+{\displaystyle \frac{1}{K^21}}\mathrm{\Psi }^{}(1\mathrm{\Phi }(K))(1\mathrm{\Phi }(K)).`$ (3.10)
Setting $`F=\mathrm{\Psi }^{}(\mathrm{\Phi }(K))`$, we obtain:

$$\mathrm{\Omega }^{}(\mathrm{\Psi })=F\mathrm{\Phi }(K)+\frac{1}{K^21}(1F)(1\mathrm{\Phi }(K)).$$
(3.11)
This operator is positive if and only if $`F0`$ and $`(1F)0`$. We also find

$`\mathrm{\Omega }^{}(\mathrm{\Psi })^\mathrm{\Gamma }`$ $`=F^\mathrm{\Gamma }\mathrm{\Phi }(K)^\mathrm{\Gamma }+{\displaystyle \frac{1}{K^21}}(1F^\mathrm{\Gamma })(1\mathrm{\Phi }(K)^\mathrm{\Gamma })`$ (3.12)
$`={\displaystyle \frac{1}{K+1}}(1/K+F^\mathrm{\Gamma })(1+K\mathrm{\Phi }(K)^\mathrm{\Gamma })/2+{\displaystyle \frac{1}{K1}}(1/KF^\mathrm{\Gamma })(1K\mathrm{\Phi }(K)^\mathrm{\Gamma })/2.`$ (3.13)
Since $`(1\pm K\mathrm{\Phi }(K)^\mathrm{\Gamma })/2`$ are orthogonal projections, we find that $`\mathrm{\Omega }(\mathrm{\Psi })^\mathrm{\Gamma }`$ is positive if and only if

$$1/KF^\mathrm{\Gamma }1/K.$$
(3.14)
The theorem follows by noting

$$F(\mathrm{\Psi }(\rho ))=\mathrm{Tr}(F\rho ).$$
(3.15)
###### Definition 3.

An operator that satisfies the inequalities (3.5) will be said to be primal feasible for $`F_\mathrm{\Gamma }(\rho ;K)`$; if it maximizes $`\mathrm{Tr}(F\rho )`$, it will be said to be primal optimal.

We will use this result to define $`F_\mathrm{\Gamma }(\rho ;K)`$ for all positive real values of $`K`$; for an interpretation, see the remark following Corollary 4.3 below.

###### Theorem 3.2.

The function $`F_\mathrm{\Gamma }`$ is convex in $`\rho `$ and concave in $`1/K`$; that is, for $`0\pi 1`$:

$`F_\mathrm{\Gamma }(\pi \rho _1+(1\pi )\rho _2;K)`$ $`\pi F_\mathrm{\Gamma }(\rho _1;K)+(1\pi )F_\mathrm{\Gamma }(\rho _2;K)`$ (3.16)
$`F_\mathrm{\Gamma }(\rho ;(K_1K_2)/(\pi K_2+(1\pi )K_1))`$ $`\pi F_\mathrm{\Gamma }(\rho ;K_1)+(1\pi )F_\mathrm{\Gamma }(\rho ;K_2).`$ (3.17)
In particular, $`F_\mathrm{\Gamma }`$ is continuous in both variables.

###### Proof.

Let $`F`$ be primal optimal for $`F_\mathrm{\Gamma }(\pi \rho _1+(1\pi )\rho _2;K)`$. Then

$`F_\mathrm{\Gamma }(\pi \rho _1+(1\pi )\rho _2;K)`$ $`=\mathrm{Tr}(F(\pi \rho _1+(1\pi )\rho _2))`$ (3.18)
$`=\pi \mathrm{Tr}(F\rho _1)+(1\pi )\mathrm{Tr}(F\rho _2)`$ (3.19)
$`\pi F_\mathrm{\Gamma }(\rho _1;K)+(1\pi )F_\mathrm{\Gamma }(\rho _2;K).`$ (3.20)
Similarly, let $`F_1`$ and $`F_2`$ be primal optimal for $`F_\mathrm{\Gamma }(\rho ;K_1)`$ and $`F_\mathrm{\Gamma }(\rho ;K_2)`$ respectively. Then $`\pi F_1+(1\pi )F_2`$ is primal feasible for $`F_\mathrm{\Gamma }(\rho ;(K_1K_2)/(\pi K_2+(1\pi )K_1))`$, thus giving the second inequality. ∎

The above optimization problem is an instance of what is known as “semi-definite programming” (SDP) (). That is, it involves the optimization of a linear function subject to the constraint that certain operators (depending linearly on the variables) must be positive semidefinite. This has several consequences, including the computational one that semi-definite programs can be solved in polynomial time (typically polynomial in the dimension, although special structure can greatly reduce this). Another consequence is that there is a notion of duality for SDPs.

For a Hermitian operator $`A`$, we define the positive part $`A_+`$ and negative part $`A_{}`$ to be the unique positive operators such that

$$A_+A_{}=A,A_+A_{}=0.$$
(3.21)
We also define $`|A|=A_++A_{}`$.

###### Theorem 3.3.

For any state $`\rho (VW)`$ and any positive real number $`K`$,

$$F_\mathrm{\Gamma }(\rho ;K)=\underset{D(VW)}{\mathrm{min}}\mathrm{Tr}(\rho D)_++\frac{1}{K}\mathrm{Tr}|D^\mathrm{\Gamma }|.$$
(3.22)
###### Proof.

Let $`F`$ be an operator satisfying the constraints above. Then for any operators $`A`$, $`B`$, $`C`$, we have:

$`\mathrm{Tr}(F\rho )`$ $`=\mathrm{Tr}(A)+1/K\mathrm{Tr}(B+C)`$
$`\mathrm{Tr}((\rho +A+B^\mathrm{\Gamma }C^\mathrm{\Gamma })F)\mathrm{Tr}(A(1F))\mathrm{Tr}(B(1/KF^\mathrm{\Gamma }))\mathrm{Tr}(C(1/K+F^\mathrm{\Gamma })).`$ (3.23)
If $`A0`$, $`B0`$, $`C0`$, and

$$A\rho (BC)^\mathrm{\Gamma },$$
(3.24)
then the last four terms are all nonnegative, and we have

$$\mathrm{Tr}(F\rho )\mathrm{Tr}(A)+1/K\mathrm{Tr}(B+C),$$
(3.25)
and thus

$$F_\mathrm{\Gamma }(\rho ;K)\mathrm{Tr}(A)+1/K\mathrm{Tr}(B+C).$$
(3.26)
In fact, by the theory of duality for SDPs, this inequality can be made tight, to wit:

$$F_\mathrm{\Gamma }(\rho ;K)=\underset{A,B,C}{\mathrm{min}}\mathrm{Tr}(A)+1/K\mathrm{Tr}(B+C),$$
(3.27)
minimizing over operators satisfying the constraints. Upon adding a variable $`D`$ with $`D=(BC)^\mathrm{\Gamma }`$, the constraints become

$$A,B,C0,A\rho D,B+C=D^\mathrm{\Gamma }.$$
(3.28)
We thus find

$$F_\mathrm{\Gamma }(\rho ;K)=\underset{D}{\mathrm{min}}\left(\underset{\begin{array}{c}A0\\ A\rho D\end{array}}{\mathrm{min}}\mathrm{Tr}(A)+\frac{1}{K}\underset{\begin{array}{c}B,C0\\ BC=D^\mathrm{\Gamma }\end{array}}{\mathrm{min}}\mathrm{Tr}(B+C)\right).$$
(3.29)
But we readily see that

$`\underset{\begin{array}{c}A0\\ A\rho D\end{array}}{\mathrm{min}}\mathrm{Tr}(A)`$ $`=\mathrm{Tr}(\rho D)_+,`$ (3.30)
$`\underset{\begin{array}{c}B,C0\\ BC=D^\mathrm{\Gamma }\end{array}}{\mathrm{min}}\mathrm{Tr}(B+C)`$ $`=\mathrm{Tr}|D^\mathrm{\Gamma }|,`$ (3.31)
proving the theorem. ∎

###### Definition 4.

An operator $`D(VW)`$ such that

$$F_\mathrm{\Gamma }(\rho ;K)=\mathrm{Tr}(\rho D)_++\frac{1}{K}\mathrm{Tr}|D^\mathrm{\Gamma }|$$
(3.32)
will be said to be dual optimal for $`F_\mathrm{\Gamma }(\rho ;K)`$.

Thus given any operator $`D`$, we obtain bounds on fidelity of distillation, and conversely any such bound can in principle be shown by choosing a suitable operator $`D`$. For instance, Theorem 3.2 could also be proved as follows:

###### Proof.

If $`D_1`$ and $`D_2`$ are dual optimal for $`F_\mathrm{\Gamma }(\rho _1;K)`$ and $`F_\mathrm{\Gamma }(\rho _2;K)`$, then

$`F_\mathrm{\Gamma }(\pi \rho _1+(1\pi )\rho _2;K)`$ $`\mathrm{Tr}(\pi \rho _1+(1\pi )\rho _2\pi D_1+(1\pi )D_2)_++{\displaystyle \frac{1}{K}}\mathrm{Tr}|\pi D_1^\mathrm{\Gamma }+(1\pi )D_2^\mathrm{\Gamma }|`$ (3.33)
$`\pi (\mathrm{Tr}(\rho _1D_1)_++\mathrm{Tr}|D_1^\mathrm{\Gamma }|)+(1\pi )(\mathrm{Tr}(\rho _2D_2)_++\mathrm{Tr}|D_2^\mathrm{\Gamma }|)`$ (3.34)
$`=\pi F_\mathrm{\Gamma }(\rho _1;K)+(1\pi )F_\mathrm{\Gamma }(\rho _2;K).`$ (3.35)
Similarly, if $`D`$ is dual optimal for $`F_\mathrm{\Gamma }(\rho ;(K_1K_2)/(\pi K_2+(1\pi )K_1))`$, then

$`F_\mathrm{\Gamma }(\rho ;(K_1K_2)/(\pi K_2+(1\pi )K_1))`$ $`=\mathrm{Tr}(\rho D)_++(\pi {\displaystyle \frac{1}{K_1}}+(1\pi ){\displaystyle \frac{1}{K_2}})\mathrm{Tr}|D^\mathrm{\Gamma }|`$ (3.36)
$`=\pi (\mathrm{Tr}(\rho D)_++{\displaystyle \frac{1}{K_1}}\mathrm{Tr}|D^\mathrm{\Gamma }|)+(1\pi )(\mathrm{Tr}(\rho D)_++{\displaystyle \frac{1}{K_2}}\mathrm{Tr}|D^\mathrm{\Gamma }|)`$ (3.37)
$`\pi F(\rho ;K_1)+(1\pi )F(\rho ;K_2).`$ (3.38)
## 4 General results

###### Lemma 4.1.

For any integer $`d1`$, and any $`K>0`$, $`F_\mathrm{\Gamma }(\mathrm{\Phi }(d);K)=\mathrm{min}(1,d/K)`$.

###### Proof.

For $`Kd`$, take $`F=d/K`$, $`D=\mathrm{\Phi }(d)`$. For $`Kd`$, take $`F=\mathrm{\Phi }(d)`$, $`D=0`$. ∎

###### Theorem 4.2.

For any states $`\rho _1`$ and $`\rho _2`$, and any $`K,K^{}>0`$,

$$F_\mathrm{\Gamma }(\rho _1;K^{})F_\mathrm{\Gamma }(\rho _2;K/K^{})F_\mathrm{\Gamma }(\rho _1\rho _2;K)F_\mathrm{\Gamma }(\rho _1;K/\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|).$$
(4.1)
###### Proof.

For the first inequality, let $`F_1`$ and $`F_2`$ be primal optimal for $`F_\mathrm{\Gamma }(\rho _1;K^{})`$ and $`F_\mathrm{\Gamma }(\rho _2;K/K^{})`$; then $`F_1F_2`$ is primal feasible for $`F_\mathrm{\Gamma }(\rho _1\rho _2;K)`$, giving the inequality.

For the second inequality, let $`D`$ be dual optimal for $`F_\mathrm{\Gamma }(\rho _1;K/\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|)`$. Then, taking $`D^{}=D\rho _2`$, we have

$`F_\mathrm{\Gamma }(\rho _1\rho _2;K)`$ $`\mathrm{Tr}((\rho _1\rho _2)(D\rho _2))_++{\displaystyle \frac{1}{K}}\mathrm{Tr}|(D\rho _2)^\mathrm{\Gamma }|`$ (4.2)
$`=\mathrm{Tr}(\rho _1D)_++{\displaystyle \frac{\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|}{K}}\mathrm{Tr}|D^\mathrm{\Gamma }|`$ (4.3)
$`=F_\mathrm{\Gamma }(\rho _1;K/\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|).`$ (4.4)
In particular, if $`F_\mathrm{\Gamma }(\rho _2;\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|)=1`$, then equality holds in this theorem, taking $`K^{}=K/\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|`$. Since this is true for $`\mathrm{\Phi }(d)`$,

###### Corollary 4.3.

For all integers $`d`$, all $`K>0`$, and any state $`\rho `$,

$$F_\mathrm{\Gamma }(\rho \mathrm{\Phi }(d);dK)=F_\mathrm{\Gamma }(\rho ;K).$$
(4.5)
###### Remark.

This gives us another way to define $`F_\mathrm{\Gamma }(\rho ;K)`$ for general $`K>0`$. For rational $`K>0`$, we can define

$$F_\mathrm{\Gamma }(\rho ;p/q)=F_\mathrm{\Gamma }(\rho \mathrm{\Phi }(q);p),$$
(4.6)
which is well-defined by the theorem. Since the resulting function is nonincreasing in $`K`$, there is a unique way to extend it to a left-continuous function of $`K`$, which must then agree with our earlier definition.

Another example is when $`\rho _2`$ is p.p.t.; then $`\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|=1`$. We have:

###### Corollary 4.4.

For all $`K>0`$, any state $`\rho `$, and any p.p.t. state $`\rho ^{}`$,

$$F_\mathrm{\Gamma }(\rho \rho ^{};K)=F_\mathrm{\Gamma }(\rho ;K).$$
(4.7)
###### Corollary 4.5.

For any $`K>0`$ and any state $`\rho `$,

$$\mathrm{min}(1,1/K)F_\mathrm{\Gamma }(\rho ;K)\mathrm{min}(1,\mathrm{Tr}|\rho ^\mathrm{\Gamma }|/K).$$
(4.8)
###### Proof.

By the theorem, we have, writing $`\rho =\mathrm{\Phi }(1)\rho `$:

$$\mathrm{min}(1,1/K)=F_\mathrm{\Gamma }(\mathrm{\Phi }(1);K)F_\mathrm{\Gamma }(\rho ;1)F_\mathrm{\Gamma }(\rho ;K)F_\mathrm{\Gamma }(\mathrm{\Phi }(1);K/\mathrm{Tr}|\rho ^\mathrm{\Gamma }|)=\mathrm{min}(1,\mathrm{Tr}|\rho ^\mathrm{\Gamma }|/K).$$
(4.9)
Asymptotically, the theorem becomes:

###### Corollary 4.6.

For any pair of states $`\rho _1`$, $`\rho _2`$,

$$D_\mathrm{\Gamma }(\rho _1)+D_\mathrm{\Gamma }(\rho _2)D_\mathrm{\Gamma }(\rho _1\rho _2)D_\mathrm{\Gamma }(\rho _1)+\mathrm{log}_2\mathrm{Tr}|\rho _2^\mathrm{\Gamma }|.$$
(4.10)
In particular,

$$D_\mathrm{\Gamma }(\rho \mathrm{\Phi }(d))=D_\mathrm{\Gamma }(\rho )+\mathrm{log}_2(d),$$
(4.11)
and for any p.p.t. state $`\rho ^{}`$,

$$D_\mathrm{\Gamma }(\rho \rho ^{})=D_\mathrm{\Gamma }(\rho ).$$
(4.12)
###### Remark 1.

Subtracting $`D_\mathrm{\Gamma }(\rho _1)`$ from the inequality, we obtain the bound $`D_\mathrm{\Gamma }(\rho )\mathrm{log}_2\mathrm{Tr}|\rho ^\mathrm{\Gamma }|`$ of . (But see Theorem 4.13 below.) See also , for an independent rederivation.

###### Remark 2.

For other classes of operations, (4.11) is known only when $`D(\rho )>0`$.

Since Definition 1 maximizes over all p.p.t. operations, we can obtain relations between different values of $`\rho `$ and (integral) $`K`$ by composing with appropriate p.p.t. operations. The next two results extend this. We recall from  that for a superoperator $`\mathrm{\Psi }`$, $`\mathrm{\Psi }^\mathrm{\Gamma }`$ is defined by

$$\mathrm{\Psi }^\mathrm{\Gamma }(\rho )=\mathrm{\Psi }(\rho ^\mathrm{\Gamma })^\mathrm{\Gamma }.$$
(4.13)
Note that $`\mathrm{\Omega }(\mathrm{\Psi }^\mathrm{\Gamma })=\mathrm{\Omega }(\mathrm{\Psi })^{WW^{}}`$, and thus $`\mathrm{\Psi }`$ is p.p.t. if and only if $`\mathrm{\Psi }`$ and $`\mathrm{\Psi }^\mathrm{\Gamma }`$ are completely positive.

###### Theorem 4.7.

For any state $`\rho `$, any $`K>0`$, and any trace-preserving superoperator $`\mathrm{\Psi }`$ such that both $`\mathrm{\Psi }`$ and $`\mathrm{\Psi }^\mathrm{\Gamma }`$ are positive,

$$F_\mathrm{\Gamma }(\mathrm{\Psi }(\rho );K)F_\mathrm{\Gamma }(\rho ;K).$$
(4.14)
###### Proof.

(First proof) Let $`F`$ be primal optimal for $`F(\mathrm{\Psi }(\rho );K)`$. Then $`\mathrm{\Psi }^{}(F)`$ is primal feasible for $`F(\rho ;K)`$, so

$$F_\mathrm{\Gamma }(\mathrm{\Psi }(\rho );K)=\mathrm{Tr}(F\mathrm{\Psi }(\rho ))=\mathrm{Tr}(\mathrm{\Psi }^{}(F)\rho )F_\mathrm{\Gamma }(\rho ;K).$$
(4.15)
(Second proof) Let $`D`$ be dual optimal for $`F_\mathrm{\Gamma }(\rho ;K)`$. Then

$`F_\mathrm{\Gamma }(\mathrm{\Psi }(\rho );K)`$ $`\mathrm{Tr}(\mathrm{\Psi }(\rho )\mathrm{\Psi }(D))_++1/K\mathrm{Tr}|\mathrm{\Psi }(D)^\mathrm{\Gamma }|`$ (4.16)
$`\mathrm{Tr}\mathrm{\Psi }((\rho D)_+)+1/K\mathrm{Tr}\mathrm{\Psi }^\mathrm{\Gamma }(|D^\mathrm{\Gamma }|)`$ (4.17)
$`=\mathrm{Tr}(\rho D)_++1/K\mathrm{Tr}|D^\mathrm{\Gamma }|`$ (4.18)
$`=F_\mathrm{\Gamma }(\rho ;K).`$ (4.19)
Here we used the facts that for a positive superoperator $`\mathrm{\Psi }`$ and an arbitrary operator $`\rho `$,

$$\mathrm{Tr}(\mathrm{\Psi }(\rho )_+)\mathrm{Tr}(\mathrm{\Psi }(\rho _+))\text{ and }\mathrm{Tr}(|\mathrm{\Psi }(\rho )|)\mathrm{Tr}(\mathrm{\Psi }(|\rho |)).$$
(4.20)
###### Remark.

It follows from this that we cannot improve on the p.p.t. fidelity by using trace-preserving superoperators $`\mathrm{\Psi }`$ such that both $`\mathrm{\Psi }`$ and $`\mathrm{\Psi }^\mathrm{\Gamma }`$ are positive. In fact, one can show using the techniques of Section 5 that any such operator that produces isotropic output must in fact be p.p.t.

###### Lemma 4.8.

For any state $`\rho `$, the function $`KF_\mathrm{\Gamma }(\rho ;K)`$ is nondecreasing in $`K`$, while the function

$$(KF_\mathrm{\Gamma }(\rho ;K)1)/(K1)$$
(4.21)
is nonincreasing in $`K`$.

###### Proof.

We first consider $`KF_\mathrm{\Gamma }(\rho ;K)`$. Writing $`F^{}=KF`$, we have

$$KF_\mathrm{\Gamma }(\rho ;K)=\underset{F^{}}{\mathrm{max}}\mathrm{Tr}(F^{}\rho ),$$
(4.22)
with $`F^{}`$ subject to the constraints

$$0F^{}K,1F^\mathrm{\Gamma }1.$$
(4.23)
Since increasing $`K`$ increases the feasible set, the maximum cannot decrease. Dually,

$$KF_\mathrm{\Gamma }(\rho ;K)=\underset{D}{\mathrm{min}}K\mathrm{Tr}(\rho D)_++\mathrm{Tr}|D^\mathrm{\Gamma }|,$$
(4.24)
which is nondecreasing in $`K`$ for any choice of $`D`$.

For $`(KF_\mathrm{\Gamma }(\rho ;K)1)/(K1)`$, we proceed similarly; taking $`F^{}=(KF1)/(K1)`$, we have:

$$(KF_\mathrm{\Gamma }(\rho ;K)1)/(K1)=\underset{F^{}}{\mathrm{max}}\mathrm{Tr}(F^{}\rho )$$
(4.25)
with $`F^{}`$ subject to the constraints

$$1/(K1)F^{}1,2/(K1)F^\mathrm{\Gamma }0.$$
(4.26)
These constraints become harder to satisfy as $`K`$ increases, and thus the maximum cannot increase. Dually,

$$(KF_\mathrm{\Gamma }(\rho ;K)1)/(K1)=\underset{D}{\mathrm{min}}(K\mathrm{Tr}(\rho D)_++\mathrm{Tr}|D^\mathrm{\Gamma }|1)/(K1).$$
(4.27)
But

$`{\displaystyle \frac{1}{K1}}(K\mathrm{Tr}(\rho D)_++\mathrm{Tr}|D^\mathrm{\Gamma }|1)`$ $`={\displaystyle \frac{1}{K1}}(K\mathrm{Tr}(\rho D)_++\mathrm{Tr}(D^\mathrm{\Gamma })+2\mathrm{Tr}(D^\mathrm{\Gamma })_{}1)`$ (4.28)
$`={\displaystyle \frac{1}{K1}}(K\mathrm{Tr}(\rho D)_+\mathrm{Tr}(\rho D)+2\mathrm{Tr}(D^\mathrm{\Gamma })_{})`$ (4.29)
$`=\mathrm{Tr}(\rho D)_++{\displaystyle \frac{1}{K1}}(\mathrm{Tr}(\rho D)_{}+2\mathrm{Tr}(D^\mathrm{\Gamma })_{}).`$ (4.30)
This, of course, is nonincreasing in $`K`$, so we are done. ∎

For integer $`K`$, this corresponds to composition by the following p.p.t. operations:

###### Lemma 4.9.

Let $`I_d(f)`$ denote the isotropic state

$$I_d(f):=f\mathrm{\Phi }(d)+\frac{1f}{d^21}(1\mathrm{\Phi }(d))$$
(4.31)
of dimension $`d`$ and fidelity $`f`$. If $`f1/d`$, then for all $`K>0`$,

$$F_\mathrm{\Gamma }(I_d(f);K)=1/K.$$
(4.32)
Otherwise, for $`0<Kd`$,

$$F_\mathrm{\Gamma }(I_d(f);K)=1/K+\frac{fd1}{d1}(11/K),$$
(4.33)
and for $`Kd`$,

$$F_\mathrm{\Gamma }(I_d(f);K)=\frac{fd}{K}.$$
(4.34)
###### Proof.

For the first claim, take $`F=1/K`$, $`D=I_d(f)`$, at which point $`D^\mathrm{\Gamma }0`$, so $`\mathrm{Tr}|D^\mathrm{\Gamma }|=1`$. For the second claim, take

$`F`$ $`=1/K+{\displaystyle \frac{d\mathrm{\Phi }(d)1}{d1}}(11/K)`$ (4.35)
$`D`$ $`={\displaystyle \frac{1f}{d^21}}(1+d\mathrm{\Phi }(d)).`$ (4.36)
Finally, for the third claim, take

$`F`$ $`=\mathrm{\Phi }(d){\displaystyle \frac{d}{K}}`$ (4.37)
$`D`$ $`=I_d(f).`$ (4.38)
In each case, the lower bound coming from $`F`$ agrees with the upper bound coming from $`D`$, and thus both $`F`$ and $`D`$ are optimal. ∎

###### Remark.

In particular, we have $`F_\mathrm{\Gamma }(I_d(f);d)=\mathrm{max}(1/d,f)`$; the fidelity of an entangled isotropic state cannot be increased by p.p.t. operations.

It is instructive to translate the relative entropy bounds of ,  in terms of the dual SDP. We recall the definition

$$S(\rho ||\sigma )=\mathrm{Tr}(\rho (\mathrm{log}_2\rho \mathrm{log}_2\sigma )),$$
(4.39)
and the following result:

###### Lemma 4.10.

\[4, Theorem 2.2\] Let $`\rho ,\sigma 𝒫(V)`$, with $`\rho `$ a state. For $`0<ϵ<1`$ and $`n^+`$, define

$$\gamma _n(ϵ):=\frac{1}{n}\mathrm{log}_2\underset{P}{\mathrm{min}}\mathrm{Tr}(\sigma ^nP),$$
(4.40)
where $`P`$ ranges over projection operators on $`V^n`$ such that $`\mathrm{Tr}(P\rho )1ϵ`$. Then

$`\underset{n\mathrm{}}{lim\; inf}\gamma _n(ϵ)`$ $`S(\rho ||\sigma )`$ (4.41)
$`\underset{n\mathrm{}}{lim\; sup}\gamma _n(ϵ)`$ $`{\displaystyle \frac{1}{1ϵ}}S(\rho ||\sigma ).`$ (4.42)
###### Remark.

In , this is stated only when $`\sigma `$ is a state; scale invariance gives the result in general. Also, if both $`\rho `$ and $`\sigma `$ are diagonal, we may restrict $`P`$ to be diagonal as well; this is just the analogous result of classical information theory.

We then have:

###### Theorem 4.11.

 For any state $`\rho `$ and any p.p.t. state $`\sigma `$,

$$D_\mathrm{\Gamma }(\rho )S(\rho ||\sigma ).$$
(4.43)
###### Proof.

We need to show that for any $`x>S(\rho ||\sigma )`$,

$$\underset{n\mathrm{}}{lim\; sup}F_\mathrm{\Gamma }(\rho ^n;2^{xn})<1.$$
(4.44)
Choose $`y`$ between $`x`$ and $`S(\rho ||\sigma )`$, and consider the dual SDP bound with

$$D=2^{yn}\sigma ^n.$$
(4.45)
Then $`D`$ is p.p.t., so $`1/K\mathrm{Tr}|D^\mathrm{\Gamma }|=2^{(yx)n}0`$; the first term is bounded below 1 by the following lemma. ∎

###### Lemma 4.12.

Let $`\rho `$ and $`\sigma `$ be arbitrary states, and let $`y`$ be a nonnegative real number. Then

$$\underset{n\mathrm{}}{lim\; sup}\mathrm{Tr}(\rho ^n2^{yn}\sigma ^n)_+<1$$
(4.46)
whenever $`y>S(\rho ||\sigma )`$.

###### Proof.

Let $`P_n(y)`$ be the projection onto the positive part of

$$\rho ^n2^{yn}\sigma ^n;$$
(4.47)
then we need to show that

$$F_n(y):=\mathrm{Tr}((\rho ^n2^{yn}\sigma ^n)P_n(y))=\mathrm{Tr}(\rho ^nP_n(y))2^{yn}\mathrm{Tr}(\sigma ^nP_n(y))$$
(4.48)
is bounded below 1. Fix $`ϵ`$, and consider the statement $`F_n(y)1ϵ`$. For this to be true, we must certainly have

$`\mathrm{Tr}(\rho ^nP_n(y))`$ $`1ϵ`$ (4.49)
$`\mathrm{Tr}(\sigma ^nP_n(y))`$ $`2^{yn}ϵ.`$ (4.50)
Letting $`y(ϵ)`$ be the largest value of $`y`$ such that these inequalities simultaneously hold for infinitely many $`n`$, we conclude by Lemma 4.10 that

$$y(ϵ)\frac{1}{1ϵ}S(\rho ||\sigma ).$$
(4.51)
In particular, if $`y>S(\rho ||\sigma )`$, then there exists $`ϵ`$ such that $`y>y(ϵ)`$, so

$$\underset{n\mathrm{}}{lim\; sup}F_n(y)<1ϵ$$
(4.52)
as required. ∎

###### Remark.

Similarly, using the fact that $`P_n(y)`$ is optimal among projections, we can conclude from the other half of Lemma 4.10 that $`lim_n\mathrm{}F_n(y)=1`$ when $`y<S(\rho ||\sigma )`$. We also have the natural conjecture that the lemma can be strengthened to say $`lim_n\mathrm{}F_n(y)=0`$ when $`y>S(\rho ||\sigma )`$.

This, of course, suggests that we should remove the requirement that $`\sigma `$ be p.p.t.; the same proof then gives:

###### Theorem 4.13.

For any states $`\rho `$ and $`\sigma `$,

$$D_\mathrm{\Gamma }(\rho )S(\rho ||\sigma )+\mathrm{log}_2\mathrm{Tr}|\sigma ^\mathrm{\Gamma }|.$$
(4.53)
When $`\sigma `$ is p.p.t., we recover the previous bound, while when $`\sigma =\rho `$, we obtain the bound of  (see the remark following Corollary 4.6 above). Note that we could also have obtained this result using Theorem 1 of , based on the fidelity bound of Corollary 4.5; this is essentially just the dual of the above proof.222M., P., and R. Horodecki (personal communication) have pointed out a third proof via Theorem 2 of ; it is reasonably straightforward to show that the new bound satisfies their criteria for an upper bound to distillable entanglement. The proof given above was chosen to emphasize the fact that any bound on distillable entanglement can in principle be deduced from the dual SDP bound.

If we define

$$(\rho ,\sigma ):=S(\rho ||\sigma )+\mathrm{log}_2\mathrm{Tr}|\sigma ^\mathrm{\Gamma }|,$$
(4.54)
then we have:

###### Theorem 4.14.

For any states $`\rho `$ and $`\sigma `$, and any trace-preserving superoperator $`\mathrm{\Psi }`$ with both $`\mathrm{\Psi }`$ and $`\mathrm{\Psi }^\mathrm{\Gamma }`$ positive,

$$(\mathrm{\Psi }(\rho ),\mathrm{\Psi }(\sigma ))(\rho ,\sigma ).$$
(4.55)
For any other state $`\rho ^{}`$ and real number $`0<p<1`$,

$$(p\rho +(1p)\rho ^{},\sigma )p(\rho ,\sigma )+(1p)(\rho ^{},\sigma ).$$
(4.56)
Finally, we have in general

$$(\rho \rho ^{},\sigma \sigma ^{})=(\rho ,\sigma )+(\rho ^{},\sigma ^{}).$$
(4.57)
###### Proof.

Indeed, this is true for each of the functions $`S(\rho ||\sigma )`$ and $`\mathrm{log}_2\mathrm{Tr}|\sigma ^\mathrm{\Gamma }|`$ individually, so must be true for their sum. ∎

In general, $``$ is not convex in $`\sigma `$. In particular, we cannot assume that a local maximum of $``$ is necessarily a global maximum. This is likely to make it very difficult to explicitly compute $`\mathrm{min}_\sigma ((\rho ,\sigma ))`$, although one can still, of course, obtain bounds from any given value of $`\sigma `$.

## 5 Exploiting symmetries

If the state $`\rho `$ has a large group of local symmetries, we can greatly simplify the primal and dual SDPs, in several cases to the point of being linear programs. The key observation is that, by the proof of Theorem 4.7, we have:

###### Theorem 5.1.

Let $`\mathrm{\Psi }`$ be a trace-preserving superoperator with both $`\mathrm{\Psi }`$ and $`\mathrm{\Psi }^\mathrm{\Gamma }`$ positive. Then for any state $`\rho =\mathrm{\Psi }(\rho )`$ and any $`K>0`$, if $`F`$ is primal optimal and $`D`$ dual optimal for $`F_\mathrm{\Gamma }(\rho ;K)`$, then so are $`\mathrm{\Psi }^{}(F)`$ and $`\mathrm{\Psi }(D)`$. In particular, if $`\mathrm{\Psi }^2=\mathrm{\Psi }`$, we may assume that $`F`$ is $`\mathrm{\Psi }^{}`$-invariant and $`D`$ is $`\mathrm{\Psi }`$-invariant.

###### Corollary 5.2.

Let $`G`$ be any closed subgroup of $`U(k)U(l)`$, and let $`\rho `$ be a $`G`$-invariant state; that is, a state such that for all $`UG`$,

$$U\rho U^{}=\rho .$$
(5.1)
Then for any $`K>0`$, there exists primal optimal $`F`$ and dual optimal $`D`$ invariant under $`G`$. If we further have

$$U_0\rho ^tU_0^{}=\rho ,$$
(5.2)
for some $`U_0U(k)U(l)`$ with $`U_0\overline{G}\overline{U_0}=G`$, then we may further take

$`U_0F^tU_0^{}`$ $`=F,`$ (5.3)
$`U_0D^tU_0^{}`$ $`=D.`$ (5.4)
###### Proof.

Let $`\mathrm{\Psi }`$ be the superoperator

$$\mathrm{\Psi }:\rho _{UG}U\rho U^{},$$
(5.5)
integrating with respect to the uniform probability measure on $`G`$. This is trace-preserving, $`ϵ`$-local (thus p.p.t.), and satisfies $`\mathrm{\Psi }=\mathrm{\Psi }^{}=\mathrm{\Psi }^2`$. The first claim thus follows from the theorem.

Similarly, if $`\mathrm{\Psi }^{}`$ is the superoperator

$$\mathrm{\Psi }^{}:\rho \frac{1}{2}(\mathrm{\Psi }(\rho )+U_0\mathrm{\Psi }(\rho )^tU_0^{}),$$
(5.6)
then the theorem applies to $`\mathrm{\Psi }^{}`$. ∎

###### Remark.

In particular, if $`\rho `$ is real, then we can take $`U_0=1`$, allowing us to force $`F`$ and $`D`$ to be real as well. If $`\rho =U_0\rho ^tU_0^{}`$ for some $`U_0`$, we will say that $`\rho `$ is pseudo-real.

To apply this, it will be helpful to work in greater generality initially. Suppose simply that $`\rho `$ is a Hermitian operator invariant under a subgroup $`GU(k)`$; we would like an efficient representation of $`\rho `$ in which it is still straightforward to test positivity.

Clearly, $`\rho `$ is invariant under $`G`$ if and only if $`\rho `$ commutes with every element of $`G`$. But then $`\rho `$ in fact commutes with the algebra $`[G]`$ of linear combinations of elements of $`G`$. In other words, $`\rho `$ must be an element of the centralizer algebra $`A`$ of $`[G]`$. From representation theory, we have:

###### Lemma 5.3.

There exists a unitary change of basis exhibiting an isomorphism

$$[G]_\lambda \left(\mathrm{Mat}(d_\lambda ,)1_{m_\lambda }\right),$$
(5.7)
for appropriate constants $`d_\lambda `$ and $`m_\lambda `$ such that

$`{\displaystyle \underset{\lambda }{}}d_\lambda ^2`$ $`=dim([G]),`$ (5.8)
$`{\displaystyle \underset{\lambda }{}}m_\lambda d_\lambda `$ $`=k.`$ (5.9)
In the same basis, the centralizer algebra is given by

$$_\lambda \left(1_{d_\lambda }\mathrm{Mat}(m_\lambda ,)\right).$$
(5.10)
In particular, the state $`\rho `$ is determined by a set of Hermitian operators $`\rho _\lambda `$, with dimensions $`m_\lambda `$; furthermore, $`\rho `$ is positive if and only if $`\rho _\lambda `$ is positive for each $`\lambda `$. Pseudo-reality conditions also carry over readily: in an appropriate basis, they produce conditions of the form (a) $`\rho _\lambda `$ real, (b) $`\rho _\lambda =\overline{\rho _\lambda ^{}}`$, or (c) $`\rho _\lambda `$ quaternionic. Finally, we have the trace identity

$$\mathrm{Tr}(\rho \sigma )=\underset{\lambda }{}d_\lambda \mathrm{Tr}(\rho _\lambda \sigma _\lambda ).$$
(5.11)
In particular, our simplification of $`F_\mathrm{\Gamma }`$ above can be viewed as a special case of this, based on the following two examples:

###### Example.

Let $`G_i`$ be the subgroup of $`U(d^2)`$ consisting of operators $`U\overline{U}`$. Any $`G_i`$-invariant operator can be written in the form

$$\rho =x\mathrm{\Phi }(d)+y(1\mathrm{\Phi }(d)),$$
(5.12)
with $`\rho 0`$ iff $`x,y0`$.

Partial-transposing the above example, we get:

###### Example.

Let $`G_w`$ be the subgroup of $`U(d^2)`$ consisting of operators $`UU`$. Any $`G_w`$-invariant operator can be written in the form

$$\rho =\frac{x}{2}(1+d\mathrm{\Phi }(d)^\mathrm{\Gamma })+\frac{y}{2}(1d\mathrm{\Phi }(d)^\mathrm{\Gamma })$$
(5.13)
with $`\rho 0`$ iff $`x,y0`$.

Another important example is:

###### Example.

Let $`\rho `$ be a state of dimension $`d`$. Then the state $`\rho ^n`$ is invariant under the symmetric group $`S_n`$, acting by permuting the tensor factors. If $`\rho ^{}`$ is a generic $`S_n`$-invariant operator, then the blocks $`\rho _\lambda ^{}`$ are in one-to-one correspondence with the degree $`n`$ representations of $`\mathrm{GL}_d()`$, in such a way that $`\rho ^n`$ maps to the image of $`\rho `$ in the corresponding representation.

If $`\rho `$ itself has symmetries, then we can simplify further. If $`A(x,y)`$ is a homogeneous polynomial in two variables, then we write

$$A(x,y)0$$
(5.14)
to denote the condition that $`A`$ has nonnegative coefficients; similarly,

$$A(x,y)B(x,y)$$
(5.15)
means that $`B(x,y)A(x,y)`$ has nonnegative coefficients.

###### Theorem 5.4.

For any real numbers $`0f1`$, $`K>0`$ and any integers $`d>1`$, $`n>0`$,

$$F_\mathrm{\Gamma }(I_d(f)^n;K)=\underset{B,S}{\mathrm{max}}B(f,(1f)/(d^21)),$$
(5.16)
where $`B(x,y)`$ and $`S(x,y)`$ range over homogeneous polynomials of degree $`n`$ such that

$`0B(`$ $`x,y)(x+(d^21)y)^n`$ (5.17)
$`{\displaystyle \frac{1}{K}}({\displaystyle \frac{d^2+d}{2}}x+{\displaystyle \frac{d^2d}{2}}y)^nS(`$ $`x,y){\displaystyle \frac{1}{K}}({\displaystyle \frac{d^2+d}{2}}x+{\displaystyle \frac{d^2d}{2}}y)^n`$ (5.18)
$`S(x,y)`$ $`=B({\displaystyle \frac{(d+1)x(d1)y}{2}},{\displaystyle \frac{x+y}{2}}).`$ (5.19)
###### Proof.

Let $`F`$ be primal optimal for $`F_\mathrm{\Gamma }(I_d(f)^n;K)`$ such that $`F`$ is invariant under $`S_n`$ and $`G_i^n`$. The representations of this group are in one-to-one correspondence with the integers $`0\lambda n`$, with $`d_\lambda =\left(\genfrac{}{}{0pt}{}{n}{\lambda }\right)(d^21)^\lambda `$ and $`m_\lambda =1`$. Writing

$`B_\lambda `$ $`=d_\lambda F_\lambda ,`$ (5.20)
$`B(x,y)`$ $`={\displaystyle \underset{\lambda }{}}B_\lambda x^{n\lambda }y^\lambda ,`$ (5.21)
we have

$`\mathrm{Tr}(FI_d(f)^n)`$ $`={\displaystyle \underset{\lambda }{}}d_\lambda F_\lambda (\rho ^n)_\lambda `$ (5.22)
$`={\displaystyle \underset{\lambda }{}}B_\lambda f^{n\lambda }((1f)/(d^21))^\lambda `$ (5.23)
$`=B(f,(1f)/(d^21)).`$ (5.24)
We next observe that $`0F`$ iff $`0B(x,y)`$ and $`F1`$ iff

$$B(x,y)\underset{\lambda }{}d_\lambda x^{n\lambda }y^\lambda =(x+(d^21)y)^n.$$
(5.25)
Similarly, the partial transpose $`F^\mathrm{\Gamma }`$ is invariant under $`S_n`$ and $`G_w^n`$. Again the representations are indexed by $`0\lambda n`$, with

$`d_\lambda ^{}`$ $`=\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\lambda }}\right)\left({\displaystyle \frac{d^2+d}{2}}\right)^{n\lambda }\left({\displaystyle \frac{d^2d}{2}}\right)^\lambda `$ (5.26)
$`m_\lambda ^{}`$ $`=1`$ (5.27)
Defining

$`S_\lambda `$ $`=d_\lambda ^{}(F^\mathrm{\Gamma })_\lambda ,`$ (5.28)
$`S(x,y)`$ $`={\displaystyle \underset{\lambda }{}}S_\lambda x^{n\lambda }y^\lambda ,`$ (5.29)
we obtain the condition

$$\frac{1}{K}\left(\frac{d^2+d}{2}x+\frac{d^2d}{2}y\right)^nS(x,y)\frac{1}{K}\left(\frac{d^2+d}{2}x+\frac{d^2d}{2}y\right)^n.$$
(5.30)
Finally, the relation between $`S(x,y)`$ and $`B(x,y)`$ obtains by noting that

$`S(x,y)`$ $`=\mathrm{Tr}\left(F^\mathrm{\Gamma }\left({\displaystyle \frac{x}{2}}(1+d\mathrm{\Phi }(d)^\mathrm{\Gamma })+{\displaystyle \frac{y}{2}}(1d\mathrm{\Phi }(d)^\mathrm{\Gamma })\right)^n\right)`$ (5.31)
$`=\mathrm{Tr}\left(F\left({\displaystyle \frac{(d+1)x(d1)y}{2}}\mathrm{\Phi }(d)+{\displaystyle \frac{x+y}{2}}(1\mathrm{\Phi }(d))\right)^n\right)`$ (5.32)
$`=B({\displaystyle \frac{(d+1)x(d1)y}{2}},{\displaystyle \frac{x+y}{2}}).`$ (5.33)
###### Remark.

For $`d=2`$, this linear program appeared in , as an upper bound on the fidelity of separable distillation; the observation that it provides a lower bound on p.p.t. distillation is new.

Similarly,

###### Theorem 5.5.

Fix a real number $`0p1`$ and an integer $`d2`$, and let $`W_d(p)`$ denote the Werner state

$$W_d(p)=\frac{1p}{d^2+d}(1+T(21))+\frac{p}{d^2d}(1T(21)),$$
(5.34)
where $`T(21)=d\mathrm{\Phi }(d)^\mathrm{\Gamma }`$. Then

$$F_\mathrm{\Gamma }(W_d(p)^n;K)=\underset{B,S}{\mathrm{max}}B(\frac{2(1p)}{d^2+d},\frac{2p}{d^2d}),$$
(5.35)
where

$`0B(`$ $`x,y)({\displaystyle \frac{d^2+d}{2}}x+{\displaystyle \frac{d^2d}{2}}y)^n`$ (5.36)
$`{\displaystyle \frac{1}{K}}(x+(d^21)y)^nS(`$ $`x,y){\displaystyle \frac{1}{K}}(x+(d^21)y)^n`$ (5.37)
$`B(x,y)`$ $`=S({\displaystyle \frac{(d+1)x(d1)y}{2}},{\displaystyle \frac{x+y}{2}}).`$ (5.38)
###### Corollary 5.6.

For the antisymmetric Werner state $`W_d(1)`$, we have

$`F_\mathrm{\Gamma }(W_d(1);K)`$ $`=\mathrm{min}(1,{\displaystyle \frac{d+2}{dK}}).`$ (5.39)
$`D_\mathrm{\Gamma }(W_d(1))`$ $`=\mathrm{log}_2\left({\displaystyle \frac{d+2}{d}}\right).`$ (5.40)
For any state $`\rho `$,

$`F_\mathrm{\Gamma }(\rho W_d(1);K)`$ $`=F_\mathrm{\Gamma }(\rho ;{\displaystyle \frac{dK}{d+2}}).`$ (5.41)
$`D_\mathrm{\Gamma }(\rho W_d(1))`$ $`=D_\mathrm{\Gamma }(\rho )+D_\mathrm{\Gamma }(W_d(1)).`$ (5.42)
###### Proof.

We observe that $`\mathrm{Tr}|W_d(1)^\mathrm{\Gamma }|=\frac{d+2}{d}`$. Thus if we show that $`F_\mathrm{\Gamma }(W_d(1);\frac{d+2}{d})=1`$, the proof of Corollary 4.3 will apply to give equation (5.41); taking $`\rho =\mathrm{\Phi }(1)`$ gives equation (5.39), and the equations for $`D_\mathrm{\Gamma }`$ follow immediately. It thus remains to show $`F_\mathrm{\Gamma }(W_d(1);\frac{d+2}{d})1`$ (since the other inequality is immediate).

Taking

$`B(x,y)`$ $`=\left({\displaystyle \frac{d^2+d}{2}}\right)\left({\displaystyle \frac{d2}{d+2}}\right)x+{\displaystyle \frac{d^2d}{2}}y,`$ (5.43)
$`S(x,y)`$ $`={\displaystyle \frac{d}{d+2}}(x+(d^21)y),`$ (5.44)
we find

$$F_\mathrm{\Gamma }(W_d(1);\frac{d+2}{d})B(0,\frac{2}{d^2d})=1.$$
(5.45)
Similar results apply to “iso-Werner” states—states which are linear combinations of $`1`$, $`T(21)`$, and $`\mathrm{\Phi }(d)`$ (invariant under $`OO`$ with $`OO(d)`$)—and Bell-diagonal states—states on $`^{2\times 2}`$ which are linear combinations of $`\mathrm{\Phi }(2)`$ and $`\sigma _w\mathrm{\Phi }(2)\sigma _w^1`$ for $`w\{x,y,z\}`$.

Using Theorem 4.14, we can apply the argument of Corollary 5.2 to conclude that when minimizing $`(\rho ,\sigma )`$, we may insist that $`\sigma `$ possess the symmetries of $`\rho `$. When $`\rho `$ is isotropic, we learn nothing new (the earlier bound (, , ) is unchanged), but when $`\rho `$ is Werner, we obtain:

###### Corollary 5.7.

Fix a real number $`0p1`$ and an integer $`d>2`$. Then

$$D_\mathrm{\Gamma }(W_d(p))\underset{\sigma }{\mathrm{min}}(W_d(p),\sigma )=\{\begin{array}{cc}0\hfill & 0p\frac{1}{2}\hfill \\ 1+p\mathrm{log}_2(p)+(1p)\mathrm{log}_2(1p)\hfill & \frac{1}{2}p\frac{1}{2}+\frac{1}{d}\hfill \\ \mathrm{log}_2\left(\frac{d2}{d}\right)+p\mathrm{log}_2\left(\frac{d+2}{d2}\right)\hfill & \frac{1}{2}+\frac{1}{d}p1.\hfill \end{array}$$
(5.46)
###### Proof.

By the above argument, we may assume $`\sigma =W_d(p^{})`$. Now,

$$(W_d(p),W_d(p^{}))=p\mathrm{log}_2\left(\frac{p}{p^{}}\right)+(1p)\mathrm{log}_2\left(\frac{1p}{1p^{}}\right)+\{\begin{array}{cc}1\hfill & p^{}\frac{1}{2}\hfill \\ 1+\frac{2(2p1)}{d}\hfill & \frac{1}{2}p^{}1.\hfill \end{array}$$
(5.47)
We find that the optimal $`p^{}`$ satisfies

$$p^{}=\{\begin{array}{cc}p\hfill & 0p\frac{1}{2}\hfill \\ \frac{1}{2}\hfill & \frac{1}{2}p\frac{1}{2}+\frac{1}{d}\hfill \\ \frac{p(d2)}{d+24p}\hfill & \frac{1}{2}+\frac{1}{d}p1.\hfill \end{array}$$
(5.48)
Plugging in, we obtain the stated bound. ∎

###### Remark 1.

We observe that this bound is differentiable and convex for $`0<p<1`$, and tight for $`p=1`$.

###### Remark 2.

The above bound has recently been independently derived in , as the regularized relative entropy of entanglement; that is,

$$\underset{n\mathrm{}}{lim}\frac{1}{n}\underset{\sigma \text{ p.p.t}}{\mathrm{min}}S(\rho ^n||\sigma ).$$
(5.49)
This suggests that the bounds of Theorems 4.11 and 4.13 may regularize to the same bound.

## 6 Hashing analogues

One of the few known lower bounds on distillable entanglement is based on the “hashing” protocol ; it will be instructive to consider this bound (for p.p.t. distillation) via the present techniques. The key point of the hashing bound is that on “low weight” states, it gives fidelity close to 1, while on “high weight” states, it gives fidelity close to 0. This suggests the reasoning behind the following proof:

###### Theorem 6.1.

Fix a fidelity $`\frac{1}{2}f1`$ and an integer $`d>1`$. Then

$$D_\mathrm{\Gamma }(I_d(f))\mathrm{max}(\mathrm{log}_2d+f\mathrm{log}_2f+(1f)\mathrm{log}_2\frac{1f}{d+1},0).$$
(6.1)
###### Proof.

Fix an integer $`n>0`$, and consider the set $`𝒫_n`$ consisting of tensor products

$$P=_{1in}P_i$$
(6.2)
with each $`P_i\{\mathrm{\Phi }(d),1\mathrm{\Phi }(d)\}`$; note, in particular, that $`𝒫_n`$ is a set of mutually orthogonal projections. Since

$$|\mathrm{\Phi }(d)^\mathrm{\Gamma }|=\frac{1}{d}\text{and}\frac{d1}{d}|1\mathrm{\Phi }(d)^\mathrm{\Gamma }|\frac{d+1}{d},$$
(6.3)
we have

$$|P^\mathrm{\Gamma }|d^n(d+1)^{\mathrm{wt}(P)},$$
(6.4)
where we define $`\mathrm{wt}(P)`$ to be the number of factors equal to $`1\mathrm{\Phi }(d)`$.

Let us then define an operator

$$F_n(w)=\underset{\begin{array}{c}P𝒫_n\\ \mathrm{wt}(P)w\end{array}}{}P.$$
(6.5)
We observe that $`F_n(w)`$ is a projection, so $`0F_n(w)1`$, and that

$$\mathrm{Tr}(F_n(w)(I_d(f)^n)=\underset{0iw}{}\left(\genfrac{}{}{0pt}{}{n}{i}\right)f^{ni}(1f)^i,$$
(6.6)
which tends to $`1`$ as $`n\mathrm{}`$ as long as

$$\omega :=\underset{n\mathrm{}}{lim}w/n>1f.$$
(6.7)
We also compute

$$|F_n(w)^\mathrm{\Gamma }|\underset{\begin{array}{c}P𝒫_n\\ \mathrm{wt}(P)w\end{array}}{}|P^\mathrm{\Gamma }|d^n\underset{0iw}{}\left(\genfrac{}{}{0pt}{}{n}{i}\right)(d+1)^i.$$
(6.8)
If we take $`\omega <\frac{d+1}{d+2}`$, then we obtain the limit

$$\underset{n\mathrm{}}{lim}\frac{1}{n}\mathrm{log}_2(d^n\underset{0iw}{}\left(\genfrac{}{}{0pt}{}{n}{i}\right)(d+1)^i)=\omega \mathrm{log}_2\omega (1\omega )\mathrm{log}_2(1\omega )+\omega \mathrm{log}_2(d+1)\mathrm{log}_2(d).$$
(6.9)
But then by Theorem 3.1, we conclude that

$$D_\mathrm{\Gamma }(I_d(f))\mathrm{log}_2(d)+\omega \mathrm{log}_2\left(\frac{\omega }{d+1}\right)+(1\omega )\mathrm{log}_2(1\omega )$$
(6.10)
whenever $`1f<\omega <\frac{d+1}{d+2}`$. Since this is decreasing over the range, we obtain the strongest bound by taking the limit as $`\omega 1f`$, proving the theorem. ∎

###### Remark.

When $`d=2`$, this is precisely the hashing lower bound (albeit weaker, in that it applies only to p.p.t. distillation). However, for $`d>2`$, the new bound is strictly stronger.

This gives us a general technique for proving lower bounds on p.p.t.-distillable entanglement: approximate the given state as a linear combination of projections with well-controlled partial transposes. Our primary application of this will be to “maximally correlated states” . We recall that a maximally correlated operator is one of the form

$$\rho =\rho _\alpha :=\underset{1i,jk}{}\alpha _{ij}|iijj|,$$
(6.11)
for some positive Hermitian operator $`\alpha `$, and similarly for a maximally correlated state. In , an upper bound was given on the p.p.t. distillable entanglement, and the conjecture was made that this bound was tight (even for the 1-locally distillable entanglement). We give a partial resolution of this conjecture:

###### Theorem 6.2.

For any maximally correlated state

$$\rho _\alpha =\underset{i,j}{}\alpha _{ij}|iijj|,$$
(6.12)
the p.p.t. distillable entanglement is given by the formula

$$D_\mathrm{\Gamma }(\rho _\alpha )=B(\alpha ):=H(\alpha _{11},\alpha _{22},\mathrm{})S(\alpha )$$
(6.13)
###### Proof.

That this is an upper bound was shown in , so it suffices to prove the lower bound. We construct a protocol in two steps.

First, suppose $`\alpha `$ possesses a transitive group of symmetries; that is, a transitive group $`G`$ of permutations such that

$$\alpha _{\pi (i)\pi (j)}=\alpha _{ij},\pi G,1i,jk.$$
(6.14)
(For instance, the operator

$$\alpha =\left(\begin{array}{ccc}\frac{1}{3}& \frac{i}{6}& \frac{i}{6}\\ \frac{i}{6}& \frac{1}{3}& \frac{i}{6}\\ \frac{i}{6}& \frac{i}{6}& \frac{1}{3}\end{array}\right)$$
(6.15)
is symmetric under the transitive group $`_3`$ of cyclic shifts.) We decompose

$$\alpha ^n=\underset{\lambda (0,1]}{}\lambda p_\lambda (n),$$
(6.16)
where $`p_\lambda (n)`$ is the orthogonal projection onto the $`\lambda `$-eigenspace of $`\alpha ^n`$. Then $`p_\lambda (n)`$ is symmetric under the transitive group $`G^n`$, and thus has constant diagonal. If we similarly decompose

$$\rho _\alpha ^n=\underset{\lambda (0,1]}{}\lambda P_\lambda (n),$$
(6.17)
we find

$$P_\lambda (n)=\rho _{p_\lambda (n)}.$$
(6.18)
We can thus apply the following lemma to $`P_\lambda (n)`$.

###### Lemma 6.3.

Let $`\rho =\rho _\beta `$ be a maximally correlated operator of dimension $`d\times d`$ such that $`\beta `$ has constant diagonal. Then

$$|\rho ^\mathrm{\Gamma }|\frac{\mathrm{Tr}(\rho )}{d}.$$
(6.19)
###### Proof.

We compute

$$\rho ^\mathrm{\Gamma }=\underset{i,j}{}\beta _{ij}|ijji|.$$
(6.20)
This is a block matrix with 1- and 2-dimensional blocks; we thus immediately compute that its eigenvalues are $`\beta _{ii}`$ for $`1id`$, and $`\pm |\beta _{ij}|`$ for $`1i<jd`$. Since $`\beta `$ is positive, we have:

$$|\beta _{ij}|^2\beta _{ii}\beta _{jj},$$
(6.21)
and thus the largest eigenvalue of $`\rho ^\mathrm{\Gamma }`$ in absolute value is $`\mathrm{max}_{1id}\beta _{ii}`$. We thus have

$$\underset{1id}{\mathrm{max}}\beta _{ii}=\frac{1}{d}\underset{1id}{}\beta _{ii}=\frac{\mathrm{Tr}(\rho )}{d}.$$
(6.22)
Now, write

$`P(n,x)`$ $`={\displaystyle \underset{x\lambda 1}{}}P_\lambda (n),`$ (6.23)
$`x_ϵ`$ $`=inf(\{x(0,1]:\mathrm{Tr}(\rho P(n,x))>1ϵ\}).`$ (6.24)
Then for $`ϵ>0`$, we find that since

$$|P(n,x_ϵ)^\mathrm{\Gamma }|\frac{\mathrm{Tr}(P(n,x_ϵ))}{d^n},$$
(6.25)
we have

$`D_\mathrm{\Gamma }(\rho )`$ $`\underset{ϵ0}{lim}\underset{n\mathrm{}}{lim}{\displaystyle \frac{1}{n}}\mathrm{log}_2{\displaystyle \frac{\mathrm{Tr}(P(n,x_ϵ))}{d^n}}`$ (6.26)
$`=\mathrm{log}_2dS(\alpha ).`$ (6.27)
Since $`H(\alpha _{11},\alpha _{22}\mathrm{})=H(1/d,1/d,\mathrm{})=\mathrm{log}_2d`$, we have proved the theorem in the symmetric case.

To reduce the general case to the symmetric case, we adapt the distillation protocol for pure states given in . Given a word $`w`$ in the numbers $`1\mathrm{}k`$, we write $`\mathrm{wt}_i(w)`$ for the number of times $`i`$ appears in $`w`$. Then our first step is, given

$$\rho _\alpha ^n=\underset{w,w^{}}{}\left(\underset{1mn}{}\alpha _{w_m,w_m^{}}\right)|www^{}w^{}|,$$
(6.28)
to measure $`\mathrm{wt}_i`$ for $`1ik`$. Then the resulting (random) state $`\rho _\alpha ^{}`$ is maximally correlated, and $`\alpha ^{}`$ admits a transitive action of $`S_n`$. Now

$$D_\mathrm{\Gamma }(\rho _\alpha )=\frac{1}{n}D_\mathrm{\Gamma }(\rho _\alpha ^n)\frac{1}{n}𝐄(D(\rho _\alpha ^{}))=\frac{1}{n}𝐄(B(\alpha ^{})),$$
(6.29)
where $`𝐄()`$ is the expected value, and the inequality follows from the fact that the measurement is local, so cannot increase the expected distillable entanglement. It thus suffices to show that

$$𝐄(B(\alpha ^{}))=nB(\alpha )+o(n).$$
(6.30)
Now, the measurement has at most $`n^k`$ different outcomes, so gives us at most $`k\mathrm{log}_2n`$ bits of information. But then

$`𝐄(H(\alpha ^{}))`$ $`nH(\alpha )k\mathrm{log}_2n,`$ (6.31)
$`𝐄(S(\alpha ^{}))`$ $`nS(\alpha ),`$ (6.32)
so we find

$$𝐄(B(\alpha ^{}))nB(\alpha )k\mathrm{log}_2n=nB(\alpha )+o(n),$$
(6.33)
as required. ∎

We also have the following general result.

###### Theorem 6.4.

Fix a finite-dimensional Hilbert space $`V`$, and let

$$1_{VV}=\underset{1im}{}P_i$$
(6.34)
be a partition of the identity with the $`P_i`$ orthogonal projections. For each $`1im`$, let $`s_i`$ be the largest eigenvalue of $`|P_i^\mathrm{\Gamma }|`$. Then for any state $`\rho 𝒫(VV)`$, we have

$$D_\mathrm{\Gamma }(\rho )\underset{1im}{}r_i(\mathrm{log}_2r_i\mathrm{log}_2s_i),$$
(6.35)
where

$$r_i:=\mathrm{Tr}(P_i\rho ).$$
(6.36)
###### Proof.

To any subset $`S\{1,2,\mathrm{}m\}^n`$, we associate a projection

$$P_S=\underset{wS}{}\underset{1in}{}P_{w_i},$$
(6.37)
which satisfies

$$|P_S^\mathrm{\Gamma }|\underset{wS}{}\underset{1in}{}s_{w_i}.$$
(6.38)
For each $`0<ϵ<1`$ and each integer $`n1`$, let $`\beta _n(ϵ)`$ be the minimum over $`S`$ of the largest eigenvalue of $`|P_S^\mathrm{\Gamma }|`$ subject to the constraint $`\mathrm{Tr}(P_S\rho ^n)1ϵ`$. Then

$$D_\mathrm{\Gamma }(\rho )\underset{ϵ0}{lim\; inf}\underset{n\mathrm{}}{lim\; inf}\frac{\mathrm{log}_2\beta _n(ϵ)}{n}$$
(6.39)
(take $`F=P_S`$). Since

$$\mathrm{Tr}(P_S\rho ^n)=\underset{wS}{}\underset{1in}{}r_{w_i},$$
(6.40)
the theorem follows by the classical analogue of Lemma 4.10. ∎

## 7 Clones

In this section, we sketch a possible direction to take in applying the above techniques to 1-local questions (quantum codes and distillation protocols).

###### Definition 5.

An operator $`A`$ on $`(^k)^n`$ is an “$`n`$-clone” if it can be written in the form

$$A=\underset{i}{}A_i^n$$
(7.1)
where each $`A_i`$ is a positive operator, or can be written as a limit of such operators.

For a permutation $`\pi S_n`$, $`T(\pi )`$ is the operator on $`(^k)^n`$ that permutes the tensor factors by $`\pi `$; when $`\pi =21S_2`$, this agrees with our earlier notation.

###### Theorem 7.1.

Let $`A`$ be an $`n`$-clone. Then for all involutions $`\pi S_n`$, and all sets $`S\{1,2,\mathrm{}n\}`$ that intersect each 2-cycle of $`\pi `$ exactly once, the following operator is positive:

$$(AT(\pi ))^{\mathrm{\Gamma }_S}.$$
(7.2)
###### Proof.

Since nonnegative linear combinations and limits of positive operators are positive, it suffices to prove the result for $`A=A_0^n`$. In that case, $`(AT(\pi ))^{\mathrm{\Gamma }_S}`$ factors as a tensor product of the following operators:

$$A,A^t,\text{and}((AA)T(21))^{\mathrm{\Gamma }_2}.$$
(7.3)
The first two are clearly positive; that the third is positive is a special case of the following lemma. ∎

###### Lemma 7.2.

For any operator $`A`$ (not necessarily Hermitian), the operator

$$((AA^{})T(21))^{\mathrm{\Gamma }_2}$$
(7.4)
is positive.

###### Proof.

We have

$$((AA^{})T(21))^{\mathrm{\Gamma }_2}=((A1)T(21)(A^{}1))^{\mathrm{\Gamma }_2}=(A1)(T(21))^{\mathrm{\Gamma }_2}(A^{}1).$$
(7.5)
Since $`T(21)^{\mathrm{\Gamma }_2}=dim(A)\mathrm{\Phi }(dim(A))0`$, the result follows. ∎

For instance, let $`C`$ be a quantum code of length $`n`$ over an alphabet of size $`k`$, and consider the following average over codes equivalent to $`C`$:

$$W(C)=𝐄_{C^{}C}(P_C^{}P_C^{}).$$
(7.6)
This is clearly a 2-clone, so we conclude that the following operators are positive:

$$W(C),W(C)^\mathrm{\Gamma },(W(C)T(21))^\mathrm{\Gamma }.$$
(7.7)
We also find that $`W(C)`$ is invariant under operators of the form $`UU`$, with $`U`$ in the semidirect product of $`S_n`$ acting on $`U(k)^n`$. Thus using the techniques of Section 5, we conclude that the three given operators are positive if and only if the following three polynomials have nonnegative coefficients:

$`S_C(x,y):=\mathrm{Tr}(W(C)`$ $`(x{\displaystyle \frac{1T(21)}{2}}+y{\displaystyle \frac{1+T(21)}{2}})^n)`$ (7.8)
$`B_C(x,y):=\mathrm{Tr}(W(C)^\mathrm{\Gamma }`$ $`((x{\displaystyle \frac{1}{d}}T(21)+y(1{\displaystyle \frac{1}{d}}T(21)))^n)^\mathrm{\Gamma })`$ (7.9)
$`A_C(x,y):=\mathrm{Tr}((W(C)T(21))^\mathrm{\Gamma }`$ $`((x{\displaystyle \frac{1}{d}}T(21)+y(1{\displaystyle \frac{1}{d}}T(21)))^n)^\mathrm{\Gamma }).`$ (7.10)
Using the fact that $`\mathrm{Tr}(M^\mathrm{\Gamma }N^\mathrm{\Gamma })=\mathrm{Tr}(MN)`$, we find:

$`S_C(x,y)`$ $`=A_C^{}({\displaystyle \frac{x+y}{2}},{\displaystyle \frac{yx}{2}}),`$ (7.11)
$`B_C(x,y)`$ $`=A_C^{}(y,{\displaystyle \frac{xy}{d}}),`$ (7.12)
$`A_C(x,y)`$ $`=A_C^{}({\displaystyle \frac{xy}{d}},y),`$ (7.13)
where

$$A_C^{}(x,y):=\mathrm{Tr}(W(C)(x+yT(21))^n).$$
(7.14)
In other words, these are precisely the weight enumerators of $`C`$ (, , ). In the full linear programming bound for quantum codes, there is an additional inequality:

$$B_C(x,y)\frac{1}{dim(C)}A_C(x,y)0.$$
(7.15)
To prove this, we simply extend $`C`$ to a self-dual code $`C^+`$ by encoding half of $`\mathrm{\Phi }(dim(C))`$ into $`C`$. We then have

$$A_{C^+}^{}(x,y,u,v)=A_C^{}(x,y)u+A_C^{}(y,x)v,$$
(7.16)
so

$`S_{C^+}(x,y,u,v)`$ $`={\displaystyle \frac{S(x,y)S(x,y)}{2}}u+{\displaystyle \frac{S(x,y)+S(x,y)}{2}}v`$ (7.17)
$`B_{C^+}(x,y,u,v)`$ $`={\displaystyle \frac{1}{dim(C)}}A_C(x,y)u+(B_C(x,y){\displaystyle \frac{1}{dim(C)}}A_C(x,y))v`$ (7.18)
$`A_{C^+}(x,y,u,v)`$ $`={\displaystyle \frac{1}{dim(C)}}A_C(x,y)u+(B_C(x,y){\displaystyle \frac{1}{dim(C)}}A_C(x,y))v.`$ (7.19)
In particular, the polynomial $`B_C(x,y)\frac{1}{dim(C)}A_C(x,y)`$ must have nonnegative coefficients.

We can thus extend the linear programming bound to higher-order invariants () by using the relevant symmetry group to decompose the operators attached to

$$W_l(C^+)=𝐄_{C^{}C^+}P_C^{}^l$$
(7.20)
by Theorem 7.1. Note that since $`W_l(C^+)T(\pi )=W_l(C^+)`$ for $`\pi S_n`$, we have only $`\frac{l}{2}+1`$ operators to consider.

Another application of the clone concept is to 1-local operations. Fix a Hilbert space $`V_AV_B`$, and consider the 1-local operation

$$\mathrm{\Psi }=\underset{i}{}𝒜_i_i,$$
(7.21)
where $`_i`$ are operations, and $`𝒜_i`$ are completely positive superoperators such that $`_i𝒜_i`$ is an operation. Then as remarked in , we can extend $`\mathrm{\Psi }`$ to an operation on the larger Hilbert space $`V_AV_B^n`$ by simply taking

$$\mathrm{\Psi }^{(n)}=\underset{i}{}𝒜_i_i^n.$$
(7.22)
Note that this depends not just on $`\mathrm{\Psi }`$ but also on the specific decomposition (7.21). The following is straightforward:

###### Lemma 7.3.

For any 1-local operation $`\mathrm{\Psi }`$, any integer $`n>1`$, and any vector $`vV_AV_A`$, the operator

$$\mathrm{Tr}_A((|vv|1)(\mathrm{\Psi }^{(n)}(\mathrm{\Phi }(V_AV_B^n))))$$
(7.23)
is an $`n`$-clone.

Using Theorem 7.1, we obtain a number of semidefiniteness constraints that $`\mathrm{\Psi }^{(2)}`$ must satisfy; these constraints can in principle be used to obtain bounds on 1-local distillation. (For instance, the argument of  can be restated in these terms, although we have not done so.) Unfortunately, the resulting semidefinite programs tend to be fairly complicated, and thus further ideas would seem to be needed. We also note that the cloning argument is quite fragile; if we define a “catalyzed” fidelity

$$\stackrel{~}{F}_1(\rho ;K)=\underset{d\mathrm{}}{lim\; sup}F_1(\rho \mathrm{\Phi }(d);dK),$$
(7.24)
after Corollary 4.3, then we can no longer directly use cloning to bound the corresponding distillable entanglement.

We close with the following new application of the cloning argument:

###### Theorem 7.4.

Fix a pair of integers $`1<K<d`$. Then for all fidelities $`1/d<f<1`$, we have the strict inequality

$$F_1(I_d(f);K)<1/K+\frac{fd1}{d1}(11/K).$$
(7.25)
###### Proof.

Suppose we had equality. A protocol $`\mathrm{\Psi }`$ attaining this bound would certainly have to be p.p.t.; thus, if we apply this protocol to $`I_d(f^{})`$, the output fidelity will take the form $`F(f^{})=af^{}+b`$ for some constants $`a`$ and $`b`$, or equivalently

$$F(f^{})=\frac{df^{}d}{d1}a^{}+\frac{f^{}d1}{d1}b^{},$$
(7.26)
for constants $`a^{}`$, $`b^{}`$. Evaluating this at $`f^{}=1/d`$, $`f^{}=1`$, we find:

$$a^{}1/K,b^{}1.$$
(7.27)
On the other hand, at $`f^{}=f`$, we have

$$F(f)=(1/K)\frac{df^{}d}{d1}+\frac{f^{}d1}{d1}.$$
(7.28)
Since the coefficients are both positive, we conclude that $`a^{}=1/K`$, $`b^{}=1`$. In particular, $`\mathrm{\Psi }`$ must take $`I_d(1)=\mathrm{\Phi }(d)`$ to $`I_K(1)=\mathrm{\Phi }(K)`$.

Now, consider the action of $`\mathrm{\Psi }^{(2)}`$ on the state $`\mathrm{\Phi }(d)\frac{1}{d}1_d`$. Since $`\mathrm{\Psi }`$ takes the pure state $`\mathrm{\Phi }(d)`$ to the pure state $`\mathrm{\Phi }(K)`$, we conclude that $`\mathrm{\Psi }^{(2)}`$ must take $`\mathrm{\Phi }(d)\frac{1}{d}1_d`$ to a state of the form $`\mathrm{\Phi }(K)X`$; by symmetry, we conclude that $`X=\frac{1}{K}1_K`$. But then tracing away the other copy of $`V_B`$, we find that $`\mathrm{\Psi }`$ takes $`I_d(1/d^2)`$ to $`I_K(1/K^2)`$. On the other hand, we have

$$F(1/d^2)=\frac{d+1K}{dK}>\frac{1}{K^2}.$$
(7.29)
We thus obtain a contradiction, and the theorem follows. ∎

###### Remark.

From , it follows that

$$F_1(I_d(f);K)1/K^2+\frac{fd^21}{d^21}(11/K^2)$$
(7.30)
whenever $`0<Kd`$. Is this lower bound tight?


text:
# Bounds for Betti numbers

## Introduction

Let $`S=K[x_1,\mathrm{},x_n]`$ be the polynomial ring over a field $`K`$ equipped with the standard grading by setting $`\mathrm{deg}(x_i)=1`$, and let $`M`$ be a finitely generated graded $`S`$-module. We denote by $`\beta _{i,i+j}(M)=dim_K\mathrm{Tor}_i(M,K)_{i+j}`$ the graded Betti numbers of $`M`$.

Assume that the initial degree of $`M`$ is $`d`$, i.e. we have $`M_i=0`$ for $`i<d`$ and $`M_d0`$. We are interested in the numbers $`\beta _i^{lin}(M)=\beta _{i,i+d}(M)`$ for $`i0`$. These numbers determine the rank of the free modules appearing in the linear strand of the minimal graded free resolution of $`M`$. Let $`p=\mathrm{max}\{i:\beta _i^{lin}(M)0\}`$ be the length of the linear strand. In  Herzog conjectured the following:
Conjecture. Let $`M`$ be a $`k`$-th syzygy module whose linear strand has length $`p`$, then

$$\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p+k}{i+k}\right)$$

for $`i=0,\mathrm{},p`$.

This conjecture is motivated by a result of Green  (see also Eisenbud and Koh ) that contains the case $`i=0,k=1`$. For $`k=0`$ these lower bounds were shown by Herzog , and Reiner, Welker  proved them for $`k=1`$ if $`M`$ is a monomial ideal.

In this paper we prove the conjecture for $`k=1`$. For $`k>1`$ we get the weaker result:

$$\text{If }\beta _p^{lin}(M)0\text{ for }p>0\text{ and }M\text{ is a }k\text{-th syzygy module, then }\beta _{p1}^{lin}(M)p+k.$$

We also show that the conjecture holds in full generality for finitely generated $`^n`$-graded $`S`$-modules. The first three sections of this paper are concerned with the question above.

In the last years many authors (see for example ) were interested in the following problem: Fix a possible Hilbert function $`H`$ for a graded ideal. Let $`(H)`$ be the set of Betti sequences $`\{\beta _{i,j}(I)\}`$ where $`IS`$ is a graded ideal with Hilbert function $`H`$. On $`(H)`$ we consider a partial order: We set $`\{\beta _{i,j}(I)\}\{\beta _{i,j}(J)\}`$ if $`\beta _{i,j}(I)\beta _{i,j}(J)`$ for all $`i,j`$. It is known that $`(H)`$ has a unique maximal element given by the Betti sequence of the lex-segment ideal in the family of considered ideals. In general there is more than one minimal element (see ).

In Section $`4`$ we study a related problem. We fix an integer $`d0`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$. Let $`(d,k)`$ be the set of Betti sequences $`\{\beta _{i,j}(I)\}`$ where $`IS`$ is a graded ideal with $`d`$-linear resolution and $`\beta _{0,d}(I)=k`$. We show that, independent of the characteristic of the base field, there is a unique minimal and a unique maximal element in $`(d,k)`$.

The author is grateful to Prof. Herzog for inspiring discussions on the subject of the paper.

## 1. Preliminaries on Koszul complexes

Let $`K`$ be a field, $`V`$ be an $`n`$-dimensional $`K`$-vector space with basis $`𝕩=x_1,\mathrm{},x_n`$ and $`S=K[V]`$ be the symmetric algebra over $`V`$ equipped with the standard grading by setting $`\mathrm{deg}(x_i)=1`$. Furthermore let $`𝔪=(x_1,\mathrm{},x_n)`$ be the graded maximal ideal of $`S`$ and $`0M`$ be a finitely generated graded $`S`$-module which is generated in not negative degrees, i.e. $`M_i=0`$ for $`i<0`$.

Consider a graded free $`S`$-module $`L`$ of rank $`j`$ which is generated in degree $`1`$ and let $`L`$ be the exterior algebra over $`L`$. Then $`L`$ inherits the structure of a bigraded $`S`$-module. If $`z^iL`$ and $`z`$ has $`S`$-degree $`k`$, then we give $`z`$ the bidegree $`(i,k)`$. We call $`i`$ the homological degree (hdeg for short) and $`k`$ the internal degree (deg for short) of $`z`$.

We consider maps $`\mu L^{}=\mathrm{Hom}_S(L,S)`$. Note that $`L^{}`$ is again a graded free $`S`$-module generated in degree $`1`$. It is well-known (see ) that $`\mu `$ defines a graded $`S`$-homomorphism $`_\mu :LL`$ of (homological) degree $`1`$.

Recall that if we fix a basis $`e_1,\mathrm{},e_j`$ of $`L`$, then $`^iL`$ is the graded free $`S`$-module with basis consisting of all monomials $`e_J=e_{j_1}\mathrm{}e_{j_i}`$ with $`J=\{j_1<\mathrm{}<j_i\}[j]=\{1,\mathrm{},j\}`$. One has

$$_\mu (e_{j_1}\mathrm{}e_{j_i})=\underset{k=1}{\overset{i}{}}(1)^{\alpha (k,J)}\mu (e_{j_k})e_{j_1}\mathrm{}\widehat{e}_{j_k}\mathrm{}e_{j_i}$$

where for $`F,G[n]`$ we set $`\alpha (F,G)=|\{(f,g):f>g,fF,gG\}|`$ and where $`\widehat{e}_{j_k}`$ indicates that $`e_{j_k}`$ is to be omitted from the exterior product. Denote by $`e_1^{},\mathrm{},e_j^{}`$ the basis of $`L^{}`$ with $`e_i^{}(e_i)=1`$ and $`e_i^{}(e_k)=0`$ for $`ki`$. In order to simplify notations we set $`_i=_{e_i^{}}`$. Then $`_\mu =_{k=1}^j_\mu (e_k)_k`$, and we have the following:

###### Lemma 1.1.

Let $`z,\stackrel{~}{z}L`$ be bihomogeneous elements, $`fS`$ and $`\mu ,\nu L^{}`$. Then:

1. $`f_\mu =_{f\mu }`$,
2. $`_\mu +_\nu =_{\mu +\nu }`$,
3. $`_\mu _\mu =0`$,
4. $`_\mu _\nu =_\nu _\mu `$,
5. $`_\mu (z\stackrel{~}{z})=_\mu (z)\stackrel{~}{z}+(1)^{\mathrm{hdeg}(z)}z_\mu (\stackrel{~}{z})`$.

###### Proof.

Straightforward calculations (most of them are done in ). ∎

We fix a graded free $`S`$-module $`L`$ of rank $`n`$ for the rest of the paper. Let $`𝕖=e_1,\mathrm{},e_n`$ be a basis of $`L`$ with $`\mathrm{deg}(e_i)=1`$ for $`i[n]`$, and $`\mu L^{}`$ with $`\mu (e_i)=x_i`$ for $`i[n]`$. For $`j=1,\mathrm{},n`$ let $`L(j)`$ be the graded free submodule of $`L`$ generated by $`e_1,\mathrm{},e_j`$. Then $`(K(j),)`$ is the Koszul complex of $`x_1,\mathrm{},x_j`$ with values in $`M`$ where $`K(j)=L(j)_SM`$ and $``$ is the restriction of $`_\mu _S\mathrm{id}_M`$ to $`L(j)_SM`$.

We denote by $`H(j)`$ the homology of the complex $`K(j)`$, and the homology class of a cycle $`zK(j)`$ will be denoted by $`[z]`$.

Notice that $`K_i(j)_{i+k}=0`$ for $`k<0`$ and that $`H_i(n)\mathrm{Tor}_i(K,M)`$ are isomorphic as graded $`K`$-vector spaces. One has the following exact sequence (see ):

$$\mathrm{}H_{i+1}(j)H_i(j1)(1)H_i(j1)H_i(j)\mathrm{}.$$

The following observation is crucial for the rest of the paper. For a homogeneous element $`zK_i(j)`$ we can write $`z`$ uniquely as $`z=e_k_k(z)+r_z`$ and $`e_k`$ divides none of the monomials of $`r_z`$.

###### Lemma 1.2.

Let $`zK_i(j)`$ be a homogeneous cycle of bidegree $`(i,l)`$. Then $`_k(z)`$ is for all $`k[n]`$ a homogeneous cycle of bidegree $`(i1,l1)`$.

###### Proof.

This follows from 1.1. ∎

In the sequel we need the following:

###### Lemma 1.3.

Let $`p\{0,\mathrm{},n\}`$ and $`t`$. Suppose that $`H_p(j)_{p+l}=0`$ for $`l=1,\mathrm{},t1`$. Then:

1. $`H_p(j1)_{p+l}=0`$ for $`l=1,\mathrm{},t1`$,
2. $`H_p(j1)_{p+t}`$ is isomorphic to a submodule of $`H_p(j)_{p+t}`$,
3. $`H_i(j)_{i+l}=0`$ for $`l=1,\mathrm{},t1`$ and $`i=p,\mathrm{},j`$.

###### Proof.

We prove (i) by induction on $`l\{1,\mathrm{},t1\}`$. If $`l=1`$ there is nothing to show because $`H_p(j1)_{p+l}=0`$ for $`l<0`$. Now let $`l>1`$ and consider the exact sequence

$$\mathrm{}H_p(j1)_{p+l1}H_p(j1)_{p+l}H_p(j)_{p+l}\mathrm{}.$$

Since by induction hypothesis $`H_p(j1)_{p+l1}=0`$ and by the assumption $`H_p(j)_{p+l}=0`$, we get that $`H_p(j1)_{p+l}=0`$.

For $`l=t`$ the exact sequence of the Koszul homology together with (i) yields

$$0H_p(j1)_{p+t}H_p(j)_{p+t}\mathrm{},$$

which proves (ii).

We show (iii) by induction on $`j[n]`$. The case $`j=1`$ is trivial and for $`j>1`$ and $`i=p`$ the assertion is true by assumption. Now let $`j>1`$, $`i>p`$ and consider

$$\mathrm{}H_i(j1)_{i+l}H_i(j)_{i+l}H_{i1}(j1)_{i1+l}\mathrm{}.$$

By (i) and the induction on $`j`$ we get that $`H_i(j1)_{i+l}=H_{i1}(j1)_{i1+l}=0`$. Hence $`H_i(j)_{i+l}=0`$. ∎

## 2. Lower bounds for Betti numbers of graded $`S`$-modules

In this section $`M`$ is always a finitely generated graded $`S`$-module which is generated in degrees $`0`$. For $`0zK_i(j)`$ we write

$$z=m_Je_J+\underset{I[n],IJ}{}m_Ie_I$$

with coefficients in $`M`$, and where $`e_J`$ is the lexicographic largest monomial of all $`e_L`$ with $`m_L0`$. Recall that for $`I,J[n]`$, $`I=\{i_1<\mathrm{}<i_t\}`$, $`J=\{j_1<\mathrm{}<j_t^{}\}`$ $`e_I<_{lex}e_J`$ if either $`t<t^{}`$ or $`t=t^{}`$ and there exists a number $`p`$ with $`i_l=j_l`$ for $`l<p`$ and $`i_p>j_p`$. We call $`\mathrm{in}(z)=m_Je_J`$ the initial term of $`z`$. Furthermore for $`I=\{i_1<\mathrm{}<i_t\}[n]`$ we write $`_I=_{i_1}\mathrm{}_{i_t}`$.

###### Lemma 2.1.

Let $`p\{0,\mathrm{},j\}`$, $`r\{0,\mathrm{},p\}`$ and $`0zK_p(j)`$ be homogeneous with $`\mathrm{in}(z)=m_Je_J`$. Then for all $`IJ`$ with $`|I|=r`$ the elements $`_I(z)`$ are $`K`$-linearly independent in $`K_{pr}(j)`$. In particular, if $`z`$ is a cycle, then $`\{_I(z):IJ,|I|=r\}`$ is a set of $`K`$-linearly independent cycles.

###### Proof.

This follows from the fact that $`\mathrm{in}(_I(z))=m_Je_{JI}`$. Induction on $`r\{0,\mathrm{},p\}`$ proves that all $`_I(z)`$ are cycles if $`z`$ is one. ∎

###### Lemma 2.2.

Let $`p[j]`$, $`t`$ and $`zK_p(j)_{p+t}`$. Assume that $`H_{p1}(j)_{p1+l}=0`$ for $`l=1,\mathrm{},t1`$.

1. If $`p<j`$ and $`_j(z)=(y)`$ for some $`y`$, then there exists $`\stackrel{~}{z}`$ such that $`\stackrel{~}{z}=z+(r)`$ and $`_j(\stackrel{~}{z})=0`$. In particular, $`\stackrel{~}{z}K_p(j1)`$, and if $`z`$ is a cycle, then $`[z]=[\stackrel{~}{z}]`$.
2. If $`p=j`$ and $`_j(z)=(y)`$ for some $`y`$, then $`z=0`$. In particular, if $`z0`$ is a cycle, then we always have $`0[_j(z)]H_{p1}(j)_{p1+t}`$.

###### Proof.

We proceed by induction on $`t`$ to prove (i). If $`t=0`$, then $`yK_p(j)_{p+t1}=0`$, and so $`_j(z)=0`$. Thus we choose $`\stackrel{~}{z}=z`$.

Let $`t>0`$ and assume that $`_j(z)=(y)`$. We see that $`_j(y)`$ is a cycle because

$$0=_j(_j(z))=_j((y))=(_j(y)).$$

But $`_j(y)K_{p1}(j)_{p1+t1}`$. Since $`H_{p1}(j)_{p1+t1}=0`$, it follows that $`_j(y)=(y^{})`$ is a boundary for some element $`y^{}`$.

By the induction hypothesis we get $`\stackrel{~}{y}=y+(r^{})`$ such that $`_j(\stackrel{~}{y})=0`$. Note that

$$(\stackrel{~}{y})=(y)=_j(z).$$

We define

$$\stackrel{~}{z}=z+(e_j\stackrel{~}{y})=z+x_j\stackrel{~}{y}e_j_j(z).$$

Then

$$_j(\stackrel{~}{z})=_j(z)+x_j_j(\stackrel{~}{y})_j(e_j)_j(z)+e_j_j_j(z)=_j(z)_j(z)=0$$

and this proves (i).

If $`p=j`$, we see that $`z=me_{[j]}`$ for some $`mM`$ and therefore $`_j(z)0`$ if and only if $`z0`$.

We prove (ii) by induction on $`t`$. For $`t=0`$ there is nothing to show. Let $`t>0`$ and assume $`_j(z)=(y)`$. By the same argument as in the proof of (i) we get $`_j(y)=(y^{})`$ for some $`y^{}`$. The induction hypothesis implies $`y=0`$, and then $`z=0`$. ∎

###### Lemma 2.3.

Let $`p\{0,\mathrm{},j\}`$, $`t`$ and $`0zK_p(j)_{p+t}`$. Assume that $`H_p(j)_{p+l}=0`$ for $`l=1,\mathrm{},t1`$ and let $`q[j]`$. If $`zK_p(jq)_{p+t}K_p(j)_{p+t}`$ and $`(y)=z`$ in $`K(j)`$ for some element $`y`$, then there exists $`\stackrel{~}{y}=y+(r)K_{p+1}(jq)_{p+1+t1}`$ such that $`(\stackrel{~}{y})=z`$.

###### Proof.

We prove the assertion by induction on $`jq`$. For $`j=q`$ there is nothing to show. Let $`j>q`$. Since $`0=_j(z)`$ and

$$z=(y)=(e_j_j(y)+r)=x_j_j(y)e_j(_j(y))+(r),$$

we see that $`_j(y)`$ is a cycle and therefore a boundary by the assumption that $`H_p(j)_{p+t1}=0`$. By 2.2 we may assume that $`yK(j1)`$. By the induction hypothesis we find the desired $`\stackrel{~}{y}`$ in $`K(jq)`$. ∎

###### Lemma 2.4.

Let $`t`$. If $`\beta _{n1,n1+l}(M)=0`$ for $`l=1,\mathrm{},t1`$ and $`\beta _{n,n+t}(M)0`$, then there exists a basis $`𝕖`$ of $`L`$ and a cycle $`zK_n(n)_{n+t}`$ such that

1. $`[z]H_n(n)_{n+t}`$ is not zero,
2. $`[_i(z)]H_{n1}(n)_{n1+t}`$ are $`K`$-linearly independent for $`i=1,\mathrm{},n`$.

In particular, $`\beta _{n1,n1+t}(M)n`$.

###### Proof.

Let $`𝕖`$ be an arbitrary basis of $`L`$. Since $`\beta _{n,n+t}(M)0`$ there exists a cycle $`zK_n(n)_{n+t}`$ with $`0[z]H_n(n)_{n+t}`$. Furthermore $`H_{n1}(n)_{n1+l}=0`$ for $`l=1,\mathrm{},t1`$. In this situation we have $`z=me_{[n]}`$ for some socle element $`m`$ of $`M`$ and we want to show that every equation

$$0=\underset{i=1}{\overset{n}{}}\mu _i[_i(z)]=[\underset{i=1}{\overset{n}{}}\mu _i_i(z)]\text{with}\mu _iK,$$

implies $`\mu _i=0`$ for all $`i[n]`$. Assume there is such an equation where not all $`\mu _i`$ are zero. After a base change we may assume that $`_{i=1}^n\mu _i_i=_n`$. We get

$$0=[_n(z)],$$

contradicting to 2.2 (ii). ∎

###### Theorem 2.5.

Let $`t`$ and $`p[n]`$. If $`\beta _{p1,p1+l}(M)=0`$ for $`l=1,\mathrm{},t1`$ and $`\beta _{p,p+t}(M)0`$, then there exists a basis $`𝕖`$ of $`L`$ and a cycle $`zK_p(n)_{p+t}`$ such that

1. $`[z]H_p(n)_{p+t}`$ is not zero,
2. $`[_i(z)]H_{p1}(n)_{p1+t}`$ are $`K`$-linearly independent for $`i=1,\mathrm{},p`$.

In particular, $`\beta _{p1,p1+t}(M)p`$.

###### Proof.

We have $`H_p(n)_{p+t}0`$ because $`\beta _{p,p+t}(M)0`$. Choose $`0hH_p(n)_{p+t}`$. We prove by induction on $`n`$ that we can find a basis $`𝕖`$ of $`L(n)`$ and a cycle $`zK_p(n)_{p+t}`$ representing $`h`$ such that every equation

$$0=\underset{i=1}{\overset{p}{}}\mu _i[_i(z)]=[\underset{i=1}{\overset{p}{}}\mu _i_i(z)]\text{with}\mu _iK,$$

implies $`\mu _i=0`$ for all $`i`$. The cases $`n=1`$ and $`n>1,`$ $`p=n`$ were shown in 2.4.

Let $`n>1`$ and $`p<n`$. Assume that there is a basis $`𝕖`$ and such an equation for a cycle $`z`$ with $`[z]=h`$ where not all $`\mu _i`$ are zero. After a base change of $`L(n)`$ we may assume that $`_{i=1}^p\mu _i_i=_n`$. Then $`0=[_n(z)],`$ and therefore $`_n(z)=(y)`$ for some element $`y`$. By 2.2 we can find an element $`\stackrel{~}{y}`$ such that $`[\stackrel{~}{y}]=[z]`$ and $`\stackrel{~}{y}K_p(n1)_{p+t}`$. Now 1.3 guarantees that we can apply our induction hypothesis to $`\stackrel{~}{y}`$ and we find a base change $`𝕝=l_1,\mathrm{},l_{n1}`$ of $`e_1,\mathrm{},e_{n1}`$, $`[\stackrel{~}{z}]=[\stackrel{~}{y}]`$ in $`H_p(n1)_{p+t}`$ (with respect to the new basis) such that $`[_i(\stackrel{~}{z})]H_{p1}(n1)_{p1+t}`$ are $`K`$-linearly independent for $`i=1,\mathrm{},p`$. By 1.3 we have $`H_i(n1)_{i+t}H_i(n)_{i+t}`$ for $`i=p1,p`$. Then $`\stackrel{~}{z}`$ is the desired cycle because $`[\stackrel{~}{z}]=[z]`$ in $`H_p(n)_{p+t}`$. ∎

The Castelnuovo-Mumford regularity for a finitely generated graded $`S`$-module $`0M`$ is defined as $`\mathrm{reg}(M)=\mathrm{max}\{j:\beta _{i,i+j}(M)0\text{ for some }i\}.`$ For $`k\{0,\mathrm{},n\}`$ we define $`d_k(M)=\mathrm{min}(\{j:\beta _{k,k+j}(M)0\}\{\mathrm{reg}(M)\})`$. We are interested in the numbers $`\beta _i^{k,lin}(M)=\beta _{i,i+d_k(M)}(M)`$ for $`ik`$. Note that $`\beta _i^{0,lin}(M)=\beta _i^{lin}(M)`$. If $`0\mathrm{\Omega }_k(M)`$ is the $`k`$-th syzygy module in the minimal graded free resolution of $`M`$ (see  for details), then we always have $`\beta _{i,i+j}(M)=\beta _{ik,ik+j+k}(\mathrm{\Omega }_k(M))`$ for $`ik`$. Therefore $`\beta _i^{k,lin}(M)=\beta _{ik}^{lin}(\mathrm{\Omega }_k(M))`$ for these $`i`$. Observe that $`d_0(\mathrm{\Omega }_k(M))=d_k(M)+k`$.

###### Corollary 2.6.

Let $`k\{0,\mathrm{},n\}`$. If $`\beta _p^{k,lin}(M)0`$ for some $`p>k`$, then

$$\beta _{p1}^{k,lin}(M)p.$$

For the numbers $`\beta _i^{lin}(M)`$ and $`\beta _i^{1,lin}(M)`$ we get more precise results. The next result was first discovered in .

###### Theorem 2.7.

Let $`p\{0,\mathrm{},n\}`$. If $`\beta _p^{lin}(M)0`$, then

$$\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p}{i}\right)$$

for $`i=0,\mathrm{},p`$.

###### Proof.

This follows from 2.1 and the fact that there are no non-trivial boundaries in $`K_i(n)_{i+d_0(M)}`$. ∎

To prove lower bounds for $`\beta _i^{1,lin}`$ we use slightly different methods. Let $`S=K[x_1,\mathrm{},x_n]`$. We fix a basis $`𝕖`$ of $`L`$ such that $`(e_i)=x_i`$ for all $`i[n]`$ for the rest of this paper. For $`a^n`$ we write $`x^a=x_1^{a_1}\mathrm{}x_n^{a_n}`$ and call it a monomial in $`S`$. Let $`F`$ be a graded free $`S`$-module with free homogeneous basis $`g_1,\mathrm{},g_t`$. Then we call $`x^ag_i`$ a monomial in $`F`$ for $`a^n`$ and $`i[t]`$. Let $`>`$ be an arbitrary degree refining term order on $`F`$ with $`x_1g_i>\mathrm{}>x_ng_i>g_i`$ (see  for details). For a homogeneous element $`fF`$ we set $`\mathrm{in}_>(f)`$ for the maximal monomial in a presentation of $`f`$. Note that we also defined $`\mathrm{in}(z)`$ for some bihomogeneous $`zK(n)`$.

###### Lemma 2.8.

Let $`MF`$ be a finitely generated graded $`S`$-module and let $`0z`$ be a homogeneous cycle of $`K_1(n,M)`$ with $`z=_{ji}m_je_j`$, $`\mathrm{in}(z)=m_ie_i`$. Then there exists an integer $`j>i`$ with $`0\mathrm{in}_>(m_j)>\mathrm{in}_>(m_i)`$. In particular, $`m_i`$ and $`m_j`$ are $`K`$-linearly independent.

###### Proof.

We have

$$0=(z)=m_ix_i+\underset{j>i}{}m_jx_j.$$

Hence there exists an integer $`j>i`$ and a monomial $`a_j`$ of $`m_j`$ with $`\mathrm{in}_>(m_i)x_i=a_jx_j`$ because all monomials have to cancel. Assume that

$$\mathrm{in}_>(m_i)\mathrm{in}_>(m_j).$$

Then

$$\mathrm{in}_>(m_i)x_i>\mathrm{in}_>(m_i)x_j\mathrm{in}_>(m_j)x_ja_jx_j$$

is a contradiction. Therefore

$$\mathrm{in}_>(m_i)<\mathrm{in}_>(m_j).$$

###### Construction 2.9.

Let $`MF`$ be a finitely generated graded $`S`$-module, $`p\{0,\mathrm{},n\}`$ and let $`0z`$ be a homogeneous cycle of $`K_p(n,M)`$ with $`z=_{J,|J|=p}m_Je_J`$, $`\mathrm{in}(z)=m_Ie_I`$. Assume that $`I=\{1,\mathrm{},p\}`$. For $`k=0,\mathrm{},p`$ we construct inductively sets

$$J_k=\{1,\mathrm{},pk,j_1,\mathrm{},j_k\}$$

with $`j_k>pk+1`$, $`j_kj_i`$ for $`i=0,\mathrm{},k1`$ and

$$\mathrm{in}_>(m_{J_k})>\mathrm{in}_>(m_{J_{k1}})>\mathrm{}>\mathrm{in}_>(m_{J_0}).$$

Set $`J_0=I`$. Assume that $`J_{k1}`$ is constructed. Then we apply 2.8 to

$$_{\{1,\mathrm{},pk,j_1,\mathrm{},j_{k1}\}}(z)\text{ where }\mathrm{in}(_{\{1,\mathrm{},pk,j_1,\mathrm{},j_{k1}\}}(z))=m_{J_{k1}}e_{pk+1}$$

and find $`j_k>pk+1`$ such that $`\mathrm{in}_>(m_{\{1,\mathrm{},pk,j_1,\mathrm{},j_{k1}\}\{j_k\}})>\mathrm{in}_>(m_{J_{k1}})`$. We see that $`j_kj_i`$ for $`i=1,\mathrm{},k1`$ because these $`e_{j_i}`$ do not appear with non-zero coefficient in $`_{\{1,\mathrm{},pk,j_1,\mathrm{},j_{k1}\}}(z)`$.

###### Corollary 2.10.

Let $`MF`$ be a finitely generated graded $`S`$-module, $`p\{0,\mathrm{},n\}`$ and let $`0z`$ be a homogeneous cycle of $`K_p(n,M)`$ with $`z=_{J,|J|=p}m_Je_J`$. Then there exist $`p+1`$ coefficients $`m_J`$ of $`z`$, which are $`K`$-linearly independent.

###### Proof.

This follows from 2.9 because the coefficients there have different leading terms. ∎

###### Theorem 2.11.

Let $`p1`$ and $`M`$ be a finitely generated graded $`S`$-module with $`\beta _p^{1,lin}(M)0`$. Then

$$\beta _i^{1,lin}(M)\left(\genfrac{}{}{0pt}{}{p}{i}\right)$$

for $`i=1,\mathrm{},p`$.

###### Proof.

Let

$$0M^{}FM0$$

be a presentation of $`M`$ such that $`F`$ is free and $`M^{}=\mathrm{\Omega }_1(M)`$. We show that

$$\beta _i^{lin}(M^{})\left(\genfrac{}{}{0pt}{}{p^{}+1}{i+1}\right)\text{ for }p^{}=p1.$$

Since $`\beta _i^{1,lin}(M)=\beta _{i1}^{lin}(M^{})`$, this will prove the theorem.

After a suitable shift of the grading of $`M`$ we may assume that $`d_0(M^{})=0`$. Note that $`M^{}`$ is a submodule of a free module and we can apply our construction 2.9. Since $`\beta _p^{}^{lin}(M^{})0`$, we get a homogeneous cycle $`0z`$ in $`K_p^{}(n,M^{})_p^{}`$. There are no boundaries except for zero in $`K_i(n,M^{})_i`$ and therefore we only have to construct enough $`K`$-linearly independent cycles in $`K_i(n,M^{})_i`$ to prove the assertion. Assume that $`\mathrm{in}(z)=m_{[p^{}]}e_{[p^{}]}`$ and construct the numbers $`j_1,\mathrm{},j_p^{}`$ for $`z`$ by 2.9.

Let $`t\{0,\mathrm{},p\}`$ and set $`i=p^{}t`$. Consider the (by 2.1) cycles $`_L(z)`$ with $`LW=W_0\dot{}\mathrm{}\dot{}W_t`$ where

$$W_k=\{I\{j_1,\mathrm{},j_k\}:I[p^{}k],|I|=tk\}\text{ for }k\{0,\mathrm{},t\}.$$

We have

$$|W_k|=\left(\genfrac{}{}{0pt}{}{p^{}k}{tk}\right)$$

and therefore

$$|W|=\underset{k=0}{\overset{t}{}}\left(\genfrac{}{}{0pt}{}{p^{}k}{tk}\right)=\left(\genfrac{}{}{0pt}{}{p^{}+1}{t}\right)=\left(\genfrac{}{}{0pt}{}{p^{}+1}{p^{}t+1}\right)=\left(\genfrac{}{}{0pt}{}{p^{}+1}{i+1}\right).$$

If we show that the cycles $`_L(z)`$ are $`K`$-linearly independent, the assertion follows.

Take $`LW`$, $`L=I_L\{j_1,\mathrm{},j_{k_L}\}`$ for some $`I_L[p^{}k_L],|I_L|=tk_L`$. It is easy to see by the construction 2.9 that

$$\mathrm{in}(_L(z))=m_{\{1,\mathrm{},p^{}k_L\}\{j_1,\mathrm{},j_{k_L}\}}e_{\{1,\mathrm{},p^{}k_L\}I_L}.$$

It is enough to show that the initial terms of the cycles are $`K`$-linearly independent.

If cycles have different initial monomials in the $`e_i`$, there is nothing to show. Take $`L,L^{}`$ and assume that the corresponding cycles have the same initial monomial in the $`e_i`$. We have to consider two cases. If $`k_L=k_L^{}`$, then $`I_L=I_L^{}`$ and the cycles are the same. For $`k_L<k_L^{}`$ the construction implies

$$\mathrm{in}(m_{\{1,\mathrm{},p^{}k_L\}\{j_1,\mathrm{},j_{k_L}\}})<\mathrm{in}(m_{\{1,\mathrm{},p^{}k_L^{}\}\{j_1,\mathrm{},j_{k_L^{}}\}}),$$

which proves the $`K`$-linearly independence. ∎

The next corollary summarizes our results related to the conjecture of Herzog.

###### Corollary 2.12.

Let $`M`$ be a finitely generated graded $`S`$-module and $`p\{0,\mathrm{},n\}`$. Suppose that $`\beta _p^{lin}(M)0`$ and $`M`$ is the $`k`$-th syzygy module in a minimal graded free resolution. Then:

1. If $`k=0`$, then $`\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p}{i}\right)`$ for $`i=0,\mathrm{},p`$.
2. If $`k=1`$, then $`\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p+1}{i+1}\right)`$ for $`i=0,\mathrm{},p`$.
3. If $`k>1`$ and $`p>0`$, then $`\beta _{p1}^{lin}(M)p+k`$.

###### Proof.

Statement (i) was shown in 2.7. In the proof of 2.11 we proved in fact (ii). Finally, (iii) follows from 2.6 since $`\beta _i^{lin}(M)=\beta _{i+k}^{k,lin}(N)`$ if $`M`$ is the $`k`$-th syzygy module in the minimal graded free resolution of some module $`N`$. ∎

Recall that a finitely generated graded $`S`$-module $`M`$ satisfies Serre’s condition $`𝒮_k`$ if

$$\mathrm{depth}(M_P)\mathrm{min}(k,dimS_P)$$

for all $`P\mathrm{Spec}(S)`$. We recall the Auslander-Bridger theorem :

###### Lemma 2.13.

Let $`M`$ be a finitely generated graded $`S`$-module. Then $`M`$ is a $`k`$-th syzygy module in a graded free resolution if and only if $`M`$ satisfies $`𝒮_k`$.

###### Proof.

The proof is essential the same as in  where the local case is treated. ∎

###### Corollary 2.14.

Let $`M`$ be a finitely generated graded $`S`$-module and $`p\{0,\mathrm{},n\}`$. Suppose that $`M`$ satisfies $`𝒮_k`$ and $`\beta _p^{lin}(M)0`$. Then:

1. If $`k=0`$, then $`\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p}{i}\right)`$ for $`i=0,\mathrm{},p`$.
2. If $`k=1`$, then $`\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p+1}{i+1}\right)`$ for $`i=0,\mathrm{},p`$.
3. If $`k>1`$ and $`p>0`$, then $`\beta _{p1}^{lin}(M)p+k`$.

###### Proof.

According to 2.13 the module $`M`$ satisfies $`𝒮_k`$ if and only if $`M`$ is a $`k`$-th syzygy module in a graded free resolution $`G_\text{.}N0`$ of some graded $`S`$-module $`N`$. It is well-known (see for example ) that $`G_\text{.}=F_\text{.}H_\text{.}`$ as graded complexes where $`F_\text{.}`$ is the minimal graded free resolution of $`N`$ and $`H_\text{.}`$ is split exact. Then $`M`$ splits as a graded module into $`\mathrm{\Omega }_k(N)W`$ where $`W`$ is a graded free $`S`$-module. If $`p=0`$, there is nothing to show. For $`p>0`$ it follows that $`\beta _p^{lin}(\mathrm{\Omega }_k(N))0`$. Then 2.12 applied to $`\mathrm{\Omega }_k(N)`$ proves the corollary, since $`\beta _{i,j}(M)\beta _{i,j}(\mathrm{\Omega }_k(N))`$ for all integers $`i,j`$. ∎

## 3. Proof of the conjecture in the case of $`^n`$-graded modules

$`S`$ is $`^n`$-graded with $`\mathrm{deg}(x_i)=\epsilon _i=(0,\mathrm{},1,\mathrm{},0)`$ where the $`1`$ is at the $`i`$-th position. Let $`M=_{a^n}M_a`$ be a finitely generated $`^n`$-graded $`S`$-module. Recall that every $`^n`$-graded $`S`$-module $`M`$ is naturally $``$-graded by setting $`M_i=_{a^n,|a|=i}M_a`$. Therefore all methods from the last section can be applied in the following. Furthermore, the Koszul complex and homology are $`^n`$-graded if we assign the degree $`\epsilon _i`$ to $`e_i`$. For example, if $`mM_a`$ for some $`a^n`$, then $`\mathrm{deg}(me_I)`$ is $`a+_{iI}\epsilon _i`$; or if $`zK_i(j)`$ is homogeneous of degree $`a`$, then $`\mathrm{deg}(_I(z))=a_{iI}\epsilon _i`$.

We want to prove more precise results than in the last section for this more restricted situation. Note that 2.2 and 2.3 hold in the $`^n`$-graded setting. The proofs are verbatim the same if we replace “graded” by “$`^n`$-graded”. We prove now a modified version of 2.5. Usually we assume that $`M=_{a^n}M_a`$.

###### Lemma 3.1.

Let $`p[j]`$ and $`t`$. Suppose that $`H_i(j)_{i+l}=0`$ for $`i=p1,\mathrm{},j`$, $`l=1,\mathrm{},t1`$ and let $`zK_p(j)_{p+t}`$ be a $`^n`$-homogeneous cycle with $`0[z]H_p(j)_{p+j}`$. Then there exists a $`^n`$-homogeneous cycle $`\stackrel{~}{z}`$ with:

1. $`[\stackrel{~}{z}]=[z]H_p(j)_{p+t}`$,
2. $`[_{j_i}(\stackrel{~}{z})]H_{p1}(j)_{p1+t}`$ are $`K`$-linearly independent for $`i=1,\mathrm{},p`$ and some $`j_i[j]`$.

###### Proof.

We prove by induction on $`j[n]`$ that we find $`[\stackrel{~}{z}]=[z]`$ and a set $`\{j_1,\mathrm{},j_p\}`$ such that the cycles $`[_{j_i}(\stackrel{~}{z})]`$ are $`K`$-linearly independent for $`i=1,\mathrm{},p`$.

The cases $`j=1`$ and $`j>1,p=j`$ follow from 2.2 (ii) because if $`\mathrm{deg}(z)=a^n`$, then all $`_k(z)`$ have different degrees $`a\epsilon _k`$ and it suffices to show that these elements are not boundaries.

Let $`j>1`$ and assume that $`p<j`$. Again it suffices to show that the cycles $`_{j_i}(z)`$ are not boundaries for a suitable subset $`\{j_1,\mathrm{},j_p\}[j]`$. If such a set exists, then nothing is to prove. Otherwise there exists a $`k[j]`$ with $`[_k(z)]=0`$ and we may assume $`k=j`$. By 2.2 we find $`\stackrel{~}{z}`$ such that $`[\stackrel{~}{z}]=[z]`$ in $`H(j)`$ and $`\stackrel{~}{z}K(j1)`$. By 1.3 we can apply our induction hypothesis and assume that $`\stackrel{~}{z}`$ has the desired properties in $`H(j1)`$. Again by 1.3 we have $`H_{p1}(j1)_{p1+t}H_{p1}(j)_{p1+t}`$ and $`\stackrel{~}{z}`$ is the desired element. ∎

We need the following simple combinatorial result. Let $`p[n]`$. Define inductively a sequence of subsets $`W_i2^{[n]}`$ for $`i=0,\mathrm{},p`$. Set

$$W_0=\{\mathrm{}\}.$$

If $`W_{i1}`$ is defined, then for every set $`wW_{i1}`$ we choose $`pi+1`$ different elements $`i_1^w,\mathrm{},i_{pi+1}^w`$ such that $`i_j^ww`$. Define

$$W_i=\{w\{i_j^w\}:wW_{i1}\text{ and }j=1,\mathrm{},pi+1\}.$$

###### Lemma 3.2.

Let $`W_i`$ be defined as above. Then for $`i=0,\mathrm{},p`$ we have that

$$|W_i|\left(\genfrac{}{}{0pt}{}{p}{i}\right).$$

###### Proof.

We prove this by induction on $`p[n]`$. The case $`p=0`$ is trivial, so let $`p>0`$ and without loss of generality we may assume that $`W_1=\{\{1\},\mathrm{},\{p\}\}`$. The set $`W_i`$ is the disjoint union of the sets $`W_i^1=\{wW_i:1w\}`$ and $`W_i^{\widehat{1}}=\{wW_i:1w\}`$. The induction hypothesis applied to $`W_i^1`$ and $`W_i^{\widehat{1}}`$ implies

$$|W_i|=|W_i^1|+|W_i^{\widehat{1}}|\left(\genfrac{}{}{0pt}{}{p1}{i1}\right)+\left(\genfrac{}{}{0pt}{}{p1}{i}\right)=\left(\genfrac{}{}{0pt}{}{p}{i}\right).$$

We prove the main theorem of this section.

###### Theorem 3.3.

Let $`k[n]`$ and $`M`$ be a finitely generated $`^n`$-graded $`S`$-module. If $`\beta _p^{k,lin}(M)0`$ for some $`pk`$, then

$$\beta _i^{k,lin}(M)\left(\genfrac{}{}{0pt}{}{p}{i}\right)$$

for $`i=k,\mathrm{},p`$.

###### Proof.

Without loss of generality $`M=_{a^n}M_a`$. Since $`\beta _p^{k,lin}(M)0`$, there exists a $`^n`$-homogeneous cycle $`zK_p(n)_{p+d_k(M)}`$ such that $`0[z]`$ in $`H_p(n)_{p+d_k(M)}`$ and $`\mathrm{deg}(z)=a`$ for some $`a^n`$. By the definition of $`d_k(M)`$ and 1.3 we have $`H_i(n)_{i+l}=0`$ for $`ik`$ and $`l=1,\mathrm{},d_k(M)1`$.

We construct inductively $`W_i`$ as above, as well as cycles $`z_w`$ for each $`wW_i`$ such that $`[z_w]0`$, $`\mathrm{deg}(z_w)=a_{iw}\epsilon _i`$, $`0[_{i_k^w}(z_w)]`$ for $`k=1,\mathrm{},pi`$ and suitable $`i_k^ww`$. Furthermore, $`z_w`$ is an element of the Koszul complex with respect to the variables $`x_i`$ with $`iw`$. For $`ik`$ we take all cycles $`z_wK_i(n)_{i+d_k(M)}`$ with $`wW_i`$ which have different $`^n`$-degree. They are not zero and therefore $`K`$-linearly independent in homology. By 3.2 there are at least $`\left(\genfrac{}{}{0pt}{}{p}{pi}\right)=\left(\genfrac{}{}{0pt}{}{p}{i}\right)`$ of them and this concludes the proof.

Let $`W_0=\{\mathrm{}\}`$. By 3.1 we can choose $`z`$ in a way such that $`[z_{i_j}]=[_{i_j}(z)]0`$ for $`j=1,\mathrm{},p`$ and some $`i_j[n]`$. Choose $`z_{\mathrm{}}=z`$ and $`i_j^{\mathrm{}}=i_j`$.

If $`W_{i1}`$ and $`z_w`$ for $`wW_{i1}`$ are constructed, then define $`W_i`$ with $`W_{i1}`$ and the given $`i_k^w`$ for $`wW_{i1}`$. For $`w^{}W_i`$ with $`w^{}=w\{i_k^w\}`$, re-choose $`z_w^{}=_{i_k^w}(z_w)`$ by 3.1 in such a way that $`[_{i_j^w^{}}(z_w^{})]0`$ for $`j=1,\mathrm{},pi`$ and some $`i_j^w^{}[n]`$.

Note that since $`z_w`$ has no monomial which is divided by some $`e_i`$ for $`iw`$, we can use 2.2 and 2.3 to avoid these $`e_i`$ in the construction of $`z_w^{}`$ again. By 1.3 the cycles $`_{i_j^w^{}}(z_w^{})`$ are also not zero in $`H(n)`$. Clearly $`i_j^w^{}w^{}`$ and the assertion follows. ∎

In the $`^n`$-graded setting we prove the desired results about $`\beta _i^{lin}`$ in full generality.

###### Corollary 3.4.

Let $`M`$ be a finitely generated $`^n`$-graded $`S`$-module and $`M`$ is the $`k`$-th syzygy module in a minimal $`^n`$-graded free resolution. If $`\beta _p^{lin}(M)0`$ for some $`p`$, then

$$\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p+k}{i+k}\right)$$

for $`i=0,\mathrm{},p`$.

###### Proof.

This follows from 3.3 and the fact that

$$\beta _i^{lin}(M)=\beta _{i+k}^{k,lin}(N)\left(\genfrac{}{}{0pt}{}{p+k}{i+k}\right)$$

where $`M`$ is the $`k`$-th syzygy module of a $`^n`$-graded $`S`$-module $`N`$. ∎

Analogue to 2.13 we get:

###### Lemma 3.5.

Let $`M`$ be a finitely generated $`^n`$-graded $`S`$-module. Then $`M`$ satisfies $`𝒮_k`$ if and only if $`M`$ is a $`k`$-th syzygy module in a $`^n`$-graded free resolution.

###### Corollary 3.6.

Let $`M`$ be a finitely generated $`^n`$-graded $`S`$-module and $`M`$ satisfies $`𝒮_k`$. If $`\beta _p^{lin}(M)0`$ for some $`p`$, then

$$\beta _i^{lin}(M)\left(\genfrac{}{}{0pt}{}{p+k}{i+k}\right)$$

for $`i=0,\mathrm{},p`$.

###### Proof.

The assertion follows from 3.4 with similar arguments as in the graded case. ∎

## 4. Bounds for Betti numbers of ideals with a fixed number of generators in given degree and a linear resolution

In this section we are interested in bounds for the graded Betti numbers of graded ideals of $`S`$. We assume that the field $`K`$ is infinite and fix a basis $`𝕩=x_1,\mathrm{},x_n`$ of $`S_1`$. For a monomial $`x^a`$ of $`S`$ with $`|a|=d`$ we denote by $`R(x^a)=\{x^b:|b|=d,x^b_{rlex}x^a\}`$ the revlex-segment of $`x^a`$ where $`>_{rlex}`$ is defined as follows: $`x^a>_{rlex}x^b`$ if either $`|a|>|b|`$ or $`|a|=|b|`$ and there exists an integer $`r`$ such that $`a_r<b_r`$ and $`a_s=b_s`$ for $`s>r`$. Note that for a given $`d`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$ there exists a unique ideal $`I(d,k)`$ which is generated in degree $`d`$ by a revlex-segment $`R(x^a)`$ for some monomial $`x^a`$ with $`|R(x^a)|=k`$.

Following Eliahou and Kervaire  for a given monomial $`x^a`$ let $`m(x^a)`$ be the maximal $`i`$ with $`x_i`$ divides $`x^a`$. An ideal is a monomial ideal if it is generated by monomials. We call a monomial ideal $`I`$ stable if for all monomials $`x^aI`$ we have $`x_ix^a/x_{m(x^a)}I`$ for $`i<m(x^a)`$. Is it easy to see that it is enough to prove this condition for the generators of the ideal $`I`$. For example $`I(d,k)`$ is stable.

For stable ideals there exist explicit formulas for the Betti numbers (see ). Let $`IS`$ be a stable ideal and $`G(I)`$ be the set of minimal generators of $`I`$. Then

$$\beta _{i,i+j}(I)=\underset{x^aG(I),|a|=j}{}\left(\genfrac{}{}{0pt}{}{m(x^a)1}{i}\right)().$$

If a stable ideal $`I`$ is generated in one degree $`d`$, then $`I`$ has a linear resolution.

###### Proposition 4.1.

Let $`IS`$ be a stable ideal generated in degree $`d`$ with $`\beta _{0,d}(I)=k`$. Then

$$\beta _{i,i+j}(I)\beta _{i,i+j}(I(d,k))$$

for all $`i,j`$.

###### Proof.

Fix $`d`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$. Let $`l(I)`$ be the number of monomials in $`I_d`$ which are not monomials in $`I(d,k)_d`$. We prove the statement by induction on $`l(I)`$. If $`l(I)=0`$, then $`I=I(d,k)`$ and there is nothing to show.

Assume that $`l(I)>0`$. Let $`x^a`$ be the smallest monomial in $`I_d`$ with respect to $`>_{rlex}`$ which is not in $`I(d,k)_d`$, and $`x^b`$ be the largest monomial which is in $`I(d,k)_d`$, but not in $`I_d`$. Define the ideal $`\stackrel{~}{I}`$ by $`G(\stackrel{~}{I})=(G(I)\{x^a\})\{x^b\}`$. Then $`l(\stackrel{~}{I})=l(I)1`$, and $`\stackrel{~}{I}`$ is also stable. Thus, by the induction hypothesis

$$\beta _{i,i+j}(\stackrel{~}{I})\beta _{i,i+j}(I(d,k)).$$

Since $`x^b>_{rlex}x^a`$, the revlex order implies $`m(x^b)m(x^a).`$ Therefore $`()`$ yields

$$\beta _{i,i+j}(I)\beta _{i,i+j}(\stackrel{~}{I}),$$

which proves the assertion. ∎

For a graded ideal $`I`$, the initial ideal $`\mathrm{in}(I)`$ is generated by all $`\mathrm{in}(f)`$ for $`fI`$ with respect to some monomial order.

Every element $`g`$ of the general linear group $`\mathrm{GL}(n)`$ induces a linear automorphism of $`S`$ by

$$g(x_j)=\underset{i=1}{\overset{n}{}}g_{i,j}x_i\text{ for }g=(g_{i,j}).$$

There is a non-empty open set $`U\mathrm{GL}(n)`$ and a unique monomial ideal $`J`$ with $`J=\mathrm{in}(g(I))`$ for every $`gU`$ with respect to the revlex order (for details see ). We call $`J`$ the generic initial ideal of $`I`$ and denote it by $`\mathrm{Gin}(I)`$. A nice property is that $`\mathrm{Gin}(I)`$ is Borel-fixed, i.e. $`\mathrm{Gin}(I)=b\mathrm{Gin}(I)`$ for all $`bB`$ where $`B`$ is the Borel subgroup of $`\mathrm{GL}(n)`$ which is generated by all upper triangular matrices.

###### Proposition 4.2.

Let $`d`$ and $`IS`$ be a graded ideal with $`d`$-linear resolution. Then $`\mathrm{Gin}(I)`$ is stable, independent of the characteristic of $`K`$, and $`\beta _{i,i+j}(I)=\beta _{i,i+j}(\mathrm{Gin}(I))`$ for all $`i,j`$.

###### Proof.

It is well-known that $`\mathrm{reg}(\mathrm{Gin}(I))=\mathrm{reg}(I)`$. Therefore $`\mathrm{reg}(\mathrm{Gin}(I))=d`$ and $`\mathrm{Gin}(I)`$ also has a $`d`$-linear resolution. \[9, Prop. 10\] implies that a Borel-fixed monomial ideal, which is generated in degree $`d`$, has regularity $`d`$ if and only if it is stable. Thus we get that $`\mathrm{Gin}(I)`$ is a stable ideal, independent of the characteristic of $`K`$.

Since $`I`$ has a linear resolution, we obtain by the main result in  that $`\beta _{i,i+j}(I)=\beta _{i,i+j}(\mathrm{Gin}(I))`$ for all $`i,j`$. ∎

###### Theorem 4.3.

Let $`d`$, $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$ and $`IS`$ be a graded ideal with $`d`$-linear resolution and $`k`$ generators. Then

$$\beta _{i,i+j}(I)\beta _{i,i+j}(I(d,k))$$

for all $`i,j`$.

###### Proof.

This follows from 4.1 and 4.2. ∎

Consider the lexicographic order $`>_{lex}`$. Recall that for monomials $`x^a,x^bS`$ we have $`x^a>_{lex}x^b`$ if either $`|a|>|b|`$ or $`|a|=|b|`$ and there exists an integer $`r`$ such that $`a_r>b_r`$ and $`a_s=b_s`$ for $`s<r`$. Then $`L(x^a)=\{x^b:|b|=d,x^b_{lex}x^a\}`$ is the lex-segment of $`x^a`$. For a given $`d`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$ there exists a unique ideal $`J(d,k)`$ which is generated in degree $`d`$ by a lex-segment $`L(x^a)`$ for some monomial $`x^a`$ with $`|L(x^a)|=k`$. It is easy to see that $`J(d,k)`$ is a lex-ideal, i.e. if $`x^b>_{lex}x^c`$ and $`x^cJ(d,k)`$, then $`x^bJ(d,k)`$. In particular $`J(d,k)`$ is stable.

###### Proposition 4.4.

Let $`d`$, $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$ and $`IS`$ be a graded ideal with $`d`$-linear resolution and $`k`$ generators. Then

$$\beta _{i,i+j}(I)\beta _{i,i+j}(J(d,k))$$

for all $`i,j`$.

###### Proof.

By \[15, Thm. 31\] we find a lex-ideal $`L`$ with the same Hilbert function as $`I`$ and $`\beta _{i,i+j}(I)\beta _{i,i+j}(L)`$ for all $`i,j`$. We see that $`\beta _{0,d}(L)=\beta _{0,d}(I)=k`$ because these ideals share the same Hilbert function. It follows that $`J(d,k)=(L_d)`$, and in particular $`G(J(d,k))=G(L)_d`$. Therefore

$$\beta _{i,i+d}(I)\beta _{i,i+d}(L)=\beta _{i,i+d}(J(d,k))$$

for all $`i,j`$ where the last equality follows from $`()`$. ∎

Fix $`d`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$. Let $`(d,k)`$ be the set of Betti sequences $`\{\beta _{i,j}(I)\}`$ where $`I`$ is a graded ideal with $`d`$-linear resolution and $`\beta _{0,d}(I)=k`$. On $`(d,k)`$ we consider a partial order: We set $`\{\beta _{i,j}(I)\}\{\beta _{i,j}(J)\}`$ if $`\beta _{i,j}(I)\beta _{i,j}(J)`$ for all $`i,j`$.

###### Corollary 4.5.

Let $`d`$ and $`0k\left(\genfrac{}{}{0pt}{}{n+d1}{d}\right)`$. Then $`\{\beta _{i,j}(I(d,k))\}`$ is the unique minimal element and $`\{\beta _{i,j}(J(d,k))\}`$ is the unique maximal element of $`(d,k)`$.

Tim Römer
FB6 Mathematik und Informatik
Universität Essen
45117 Essen
Germany
tim.roemer@uni-essen.de