Î T Beno

Ion Collins

Nechita
email: nechita@math.univ-lyon1.fr

RANDOM QUANTUM CHANNELS II: ENTANGLEMENT OF RANDOM SUBSPACES, R ÉNYI ENTROPY ESTIMATES AND ADDITIVITY PROBLEMS

Keywords: 2000 Mathematics Subject Classification. 15A52, 94A17, 94A40 Random matrices, Quantum information theory, Random channel, Additivity conjecture, Schatten p-norm. 1, ..., a

In this paper we obtain new bounds for the minimum output entropies of random quantum channels. These bounds rely on random matrix techniques arising from free probability theory. We then revisit the counterexamples developed by Hayden and Winter to get violations of the additivity equalities for minimum output Rényi entropies. We show that random channels obtained by randomly coupling the input to a qubit violate the additivity of the p-Rényi entropy, for all p > 1. For some sequences of random quantum channels, we compute almost surely the limit of their Schatten S1 → Sp norms.

Introduction

The relationship between random matrix theory and free probability theory lies in the asymptotic freeness of random matrices. Asymptotic freeness, as it was discovered by Voiculescu (see e.g. [START_REF] Voiculescu | Free random variables[END_REF]), usually predicts the asymptotic pointwise behavior of joint noncommutative moments. However in some cases it can also predict more. For example, in the case of i.i.d. GUE random matrices, it was showed by Haagerup and Thorbjørnsen [START_REF] Haagerup | A new application of random matrices: Ext(C * red (F2)) is not a group[END_REF] that even the norms have an almost sure behavior predicted by free probability theory.

Quantum information theory is the analogue of classical information theory, where classical communication protocols are replaced by quantum information protocols, known as quantum channels. Despite the apparent simplicity of some mathematical question related to information theory, their resistance to various attempts to (dis)prove them have led to the study of their statistical properties.

The Holevo conjecture is arguably the most important conjecture in quantum information theory, and the theory of random matrices has been used here with success by Hayden and Winter [14,[START_REF] Hayden | Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1[END_REF] to produce counterexamples to the additivity conjecture of Rényi entropy for p > 1. These counterexamples are of great theoretical importance, as they depict the likely behavior of a random channel. In [START_REF] Hastings | A Counterexample to Additivity of Minimum Output Entropy[END_REF], Hastings gave a counterexample for the case p = 1. It is also of probabilistic nature, but uses a very different and less canonical measure.

In our previous paper [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF], we introduced a graphical model that allowed us to understand more systematically the computation of expectation and covariance of random channels and their powers. In particular we studied at length the output of the Bell state under a random conjugate bi-channel and obtained the explicit asymptotic behavior of this random matrix.

In the present paper, we focus on the mono-channel case. Our main result is Theorem 4.1. It relies on a result obtained by one author in [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability Probab[END_REF] and can be stated as follows:

Theorem 1.1. Let k be an integer and t be a real number in (0, 1). Let Φ n be a sequence of random channels defined according to Equation [START_REF] Bengtsson | Geometry of quantum states. An introduction to quantum entanglement[END_REF]. Then there exists a probability vector β (t) (defined in Equation [START_REF] Bhatia | Matrix Analysis[END_REF]) such that, for all ε > 0, almost surely when n → ∞, for all input density matrix ρ, the inequality [START_REF] Aubrun | Catalytic majorization and lp norms[END_REF] spec(Φ(ρ)) ≺ β (t) is ε-close to being satisfied. Moreover, β (t) is optimal in the sense that any other probability vector β ∈ ∆ k satisfying the same property must satisfy β (t) ≺ β.

We combine this result result with bi-channel bounds to obtain new counterexamples to the additivity conjectures for p > 1.

An illustration of our result is Corollary 5.6, which one can reformulate as follows:

Theorem 1.2. For each p > 1 and each finite quantum space A of dimension k ′ 2, there exists an integer such that for each quantum system B of dimension larger than this integer, the quantum channel arising from a quantum coupling A and B (of appropriate relative dimension, depending on p and k ′ ) has a high probability to be Rényi superadditive when coupled with its conjugate.

From a quantum information theory point of view, the true novelty of this result is that any dimension k ′ 2 is acceptable. This result does not seem to be attainable with the alternative proofs available in [START_REF] Hayden | The maximal p-norm multiplicativity conjecture is false[END_REF][START_REF] Hastings | A Counterexample to Additivity of Minimum Output Entropy[END_REF][START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF][START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF].

Our techniques rely on free probability theory. They allow us to understand entanglement of random subspaces, and do not rely on a specific choice of a measure of entanglement. Even though the von Neumann entropy is the most natural measure of entanglement in general, this subtlety is important as the papers [START_REF] Aubrun | Catalytic majorization and lp norms[END_REF][START_REF] Aubrun | Stochastic domination for iterated convolutions and catalytic majorization[END_REF] imply that all the p 1 Rényi entropies don't enclose enough data to fully understand entanglement.

Our paper is organized as follows. We first recall a few basics and useful results of free probability theory of random matrix theoretical flavor in Section 2. In Section 3, we describe the random quantum channels we study. Section 4 describes the behavior of the eigenvalues of the outputs of random channels. In Section 5, we use results of the previous sections and of [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF] to obtain new counterexamples to the additivity conjectures.

A reminder of free probability

The following is a summary of results contained in [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability Probab[END_REF], [START_REF] Voiculescu | A strengthened asymptotic freeness result for ran-dom matrices with applications to free entropy Internat[END_REF], [START_REF] Voiculescu | Free random variables[END_REF] and [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF].

Asymptotic freeness.

A non-commutative probability space is an algebra A with unit endowed with a tracial state ϕ. An element of A is called a (non-commutative) random variable. In this paper we shall be mostly concerned with the non-commutative probability space of random matrices

(M n (L ∞-(Ω, P)), E[n -1 Tr(•)]) (we use the standard notation L ∞-(Ω, P) = ∩ p 1 L p (Ω, P)).
Let A 1 , . . . , A k be subalgebras of A having the same unit as A. They are said to be free if for all a i ∈ A j i (i = 1, . . . , k) such that ϕ(a i ) = 0, one has

ϕ(a 1 • • • a k ) = 0
as soon as j 1 = j 2 , j 2 = j 3 , . . . , j k-1 = j k . Collections S 1 , S 2 , . . . of random variables are said to be free if the unital subalgebras they generate are free.

Let (a 1 , . . . , a k ) be a k-tuple of selfadjoint random variables and let C X 1 , . . . , X k be the free * -algebra of non commutative polynomials on C generated by the k indeterminates X 1 , . . . , X k . The joint distribution of the family {a i } k i=1 is the linear form

µ (a 1 ,...,a k ) : C X 1 , . . . , X k → C P → ϕ(P (a 1 , . . . , a k )).
Given a k-tuple (a 1 , . . . , a k ) of free random variables such that the distribution of a i is µ a i , the joint distribution µ (a 1 ,...,a k ) is uniquely determined by the µ a i 's. A family (a n 1 , . . . , a n k ) n of k-tuples of random variables is said to converge in distribution towards (a 1 , . . . , a k ) iff for all P ∈ C X 1 , . . . , X k , µ (a n as n → ∞. Sequences of random variables (a n 1 ) n , . . . , (a n k ) n are called asymptotically free as n → ∞ iff the k-tuple (a n 1 , . . . , a n k ) n converges in distribution towards a family of free random variables.

The following result was contained in [START_REF] Voiculescu | A strengthened asymptotic freeness result for ran-dom matrices with applications to free entropy Internat[END_REF] (see also [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]).

Theorem 2.1. Let {U (n)
k } k∈N be a collection of independent Haar distributed random matrices of M n (C) and {W (n) k } k∈N be a set of constant matrices of M n (C) admitting a joint limit distribution as n → ∞ with respect to the state n -1 Tr. Then the family {U

(n) k , W (n) k } k∈N admits a limit * -distribution {u k , w k } k∈N with respect to E[n -1
Tr], such that u 1 , u 2 , . . . , {w 1 , w 2 , . . .} are free.

Free projectors.

Let us fix real numbers 0 α, β 1, and consider, for all n, a selfadjoint projector π n ∈ M n (C) of rank q n such that asymptotically q n ∼ αn as n → ∞. Let π ′ n be a projector of rank q ′ n such that q ′ n ∼ βn, and assume that it can be written under the form U π n U * , where U is a Haar distributed unitary random matrix independent from π n It is a consequence of Theorem 2.1, that π n and π ′ n are asymptotically free. Therefore π n π ′ n π n has an empirical eigenvalues distribution converging towards a probability measure. This measure is usually denoted by µ 1 ⊠ µ 2 , where µ 1 , µ 2 are the limit empirical eigenvalue distributions of the projectors π n and π ′ n respectively:

µ 1 = (1 -α)δ 0 + αδ 1 , µ 2 = (1 -β)δ 0 + βδ 1 .
In this specific case, we can compute explicitly µ 1 ⊠ µ 2 . For this purpose, we introduce two 2-variable functions which will be of great importance in what follows.

ϕ + : {(x, y) ∈ [0, 1] 2 } → [0, 1] (x, y) → 1 - (1 -x)(1 -y) - √ xy 2 ϕ -: {(x, y) ∈ [0, 1] 2 } → [0, 1] (x, y) → 1 - (1 -x)(1 -y) + √ xy 2
Let us omit the variables of ϕ +/-and rewrite

ϕ +/-= ϕ +/-(α, β) = α + β -2αβ ± 4αβ(1 -α)(1 -β)
It follows then from [START_REF] Voiculescu | Free random variables[END_REF], Example 3.6.7, that

µ 1 ⊠ µ 2 = [1 -min(α, β)]δ 0 + [max(α + β -1, 0)]δ 1 + (ϕ + -x)(x -ϕ -) 2πx(1 -x) 1 [ϕ -,ϕ + ] dx
The proof relies on a technique introduced by Voiculescu to compute µ 1 ⊠ µ 2 in general, called the S-transform. For more details, we refer the interested reader to [START_REF] Voiculescu | Free random variables[END_REF]. Since we are only interested in ϕ + , we consider the two-variable function ϕ

: [0, 1] 2 → [0, 1] ϕ(x, y) =      0 if x = 0 or y = 0; ϕ + (x, y) if x, y > 0 and x + y 1; 1 if x + y > 1.
In the case where α + β < 1, the ranges of π n and π ′ n do not (generically) overlap and ϕ(α, β) < 1. The previous asymptotic freeness results imply that almost surely, lim inf

n ||π n π ′ n π n || ∞ ϕ(α, β).
We are interested in whether we actually have

lim n ||π n π ′ n π n || ∞ = ϕ(α, β) < 1.
This turns out to be true. This is an involved result whose proof we won't discuss here. We just recall the result below as a theorem, following [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability Probab[END_REF] (Theorem 4.15), see also [START_REF] Ledoux | Differential operators and spectral distributions of invariant ensembles from the classical orthogonal polynomials part I: the continuous case[END_REF].

Theorem 2.2. In C n , choose at random according to the Haar measure two independent subspaces V n and V ′ n of respective dimensions q n ∼ αn and q ′ n ∼ βn where α, β ∈ (0, 1). Let π n (resp. π ′ n ) be the orthogonal projection onto V n (resp. V ′ n ). Then,

lim n π n π ′ n π n ∞ = ϕ(α, β).
3. Quantum channels and additivity conjectures 3.1. Rényi entropies and minimum output entropies.

Let ∆ k = {x ∈ R k + | k i=1
x i = 1} be the (k -1)-dimensional probability simplex. For a positive real number p > 0, define the Rényi entropy of order p of a probability vector x ∈ ∆ k to be

H p (x) = 1 1 -p log k i=1
x p i .

Since lim p→1 H p (x) exists, we define the Shannon entropy of x to be this limit, namely:

H(x) = H 1 (x) = - k i=1 x i log x i .
We extend these definitions to density matrices by functional calculus:

H p (ρ) = 1 1 -p log Tr ρ p ; H(ρ) = H 1 (ρ) = -Tr ρ log ρ.
Given a vector x ∈ C n , x = 1, we call P x the rank one orthogonal projection onto the span of x. Using Dirac's bra-ket notation, P x = |x x|. More generally, for a subspace V ⊂ C n , we denote by P V the orthogonal projection onto V in M n (C).

A quantum channel is a linear completely positive trace preserving map Φ :

M n (C) → M k (C).
The trace preservation condition means that density matrices are mapped to density matrices, and the complete positivity reads:

∀d 1, Φ ⊗ I d : M nd (C) → M kd (C) is a positive map.
We recall that according to Stinespring theorem, a linear map Φ :

M n (C) → M k (C
) is a quantum channel if and only if there exists a finite dimensional Hilbert space K = C d , and a partial isometry

V ∈ End(C n , C kd ) (satisfying V * V = I n ) such that (2) Φ(X) = Tr K [V XV * ] , ∀X ∈ M n (C).
For a quantum channel Φ : M n (C) → M k (C), we define its minimum output Rényi entropy (of order p) by

H p min (Φ) = min ρ∈Mn(C) ρ 0,Tr ρ=1 H p (Φ(ρ)).
Since the Rényi entropies are concave functions, their minima are attained on the extremal points of the set of density matrices and hence

H p min (Φ) = min x∈C n x =1
H p (Φ(P x )).

3.2.

The random quantum channel model. We fix an integer k and a real number t ∈ (0, 1). For each n, let U n ∈ M nk (C) be a random unitary matrix distributed according to the Haar measure, and q n be a projection of M nk (C) of trace p n such that p n /(kn) ∼ t as n → ∞. To q n we associate a non-unital matrix algebra map χ n : M pn (C) → M nk (C) satisfying χ n (1) = q n . The choice of χ n is unique up to unitary conjugation, and the actual choice of χ n is irrelevant for the computations we want to perform -in the sense that any choice will yield the same results.

We study the sequence of random channels

Φ n : M pn (C) → M k (C)
given by

(3) Φ n (X) = Tr n (U n (χ n (X))U * n ). Remark 3.1.
In our previous paper [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF], we considered exactly the same model of random quantum channels, with one small difference: the partial trace was taken with respect to C k . However, it is well-known that, when partial tracing a rank one projector, the non-zero eigenvalue of the resulting matrix do not depend on which space is traced out. Hence, from the point of view of eigenvalue statistics, the model we consider here is identical with the one in [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF], Section 6.2.

Graphically, our model amounts to Figure 1. We refer to the first paper of this series, [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF] for details about this graphical notation.

U U * Φ(X) = X Figure 1. Diagram for Φ(X)
We are interested in the random process given by the set of all possible eigenvalues of Φ(X) as n → ∞. In our setup, we deal with k eigenvalues.

Let V n be the image of U χ n U * . This is a random vector space in C n ⊗ C k of dimension p n distributed according to the uniform measure on the Grassmannian space Gr pn (C nk ).

If we can ensure that the entanglement of every norm one vector x ∈ V n in C n ⊗ C k is large with high probability for the uniform measure on V n ∈ Gr pn (C nk ), this will yield new entropy bounds. The entanglement is always a concave function of the principal values of x. We recall that for an element x ∈ C n ⊗ C k we denote λ(x) and rk(x) the singular values and the rank of x, when viewed as a matrix x ∈ M n×k (C). In quantum information theory, these quantities are also called the Schmidt coefficients and the Schmidt rank of x respectively:

x = rk(x) i=1 λ i (x)e i ⊗ f i ,
where {e i } and {f i } are orthonormal families from C n and C k respectively. Both quantities can also be expressed as the rank and respectively the spectrum of the reduced density matrix Tr n P x . The strategy adopted in this paper is to describe a convex polyhedron such that with high probability, for a vector subspace V chosen at random, for all input x ∈ V , the eigenvalue vector λ(x) belongs to a neighborhood of this convex set.

3.3. Known bounds. Some results are already available in order to quantify the entanglement of generic spaces in Gr pn (C n ⊗ C k ). The best result known so far is arguably the following theorem of Hayden, Leung and Winter in [START_REF] Hayden | Aspects of generic entanglement Comm[END_REF]:

d ∼ d A d B Γα 2.5 (log d A ) 2.5
such that all states x ∈ S have entanglement satisfying

H(P x ) log d A -α -β, where β = d A /(d B log 2) and Γ = 1/1753.
To prove this result, the authors require sophisticated methods from asymptotic geometry theory. In particular, they need estimates on the covering numbers of unitary groups by balls of radius ε and results of concentration of measure. The results of concentration of measure are applied to a specific measure of entanglement (e.g. one entropy H p ), therefore the measure of entanglement does not deal directly with the behavior of the Schmidt coefficients, but rather with the behavior of a function of them.

Confining the eigenvalues almost surely

4.1. Main result. Our strategy is to describe a convex polyhedron K inside the probability simplex ∆ k with the property that, for all ε > 0, almost surely when n goes to infinity, all input density matrices ρ 0, Tr(ρ) = 1, are mapped to output states Φ(ρ) whose spectra are contained K + ε, the ε-neighborhood of K.

For t ∈ (0, 1), let us first define the vector

β (t) ∈ R k , where (4) β (t)
j = ϕ j k , t -ϕ j -1 k , t , ∀ 1 j k.
One can check directly that β (t) is a probability vector and that it is a non-increasing sequence. Moreover, β

1 = ϕ(1/k, t) and β (t) j = 0 for j ⌊k(1t)⌋ + 2. Since the majorization partial order plays an important role in this situation, let us remind here the definition and some basic properties of this relation. For two probability vectors x, y ∈ ∆ k , we say that x is majorized by y (and we write x ≺ y) iff for all j ∈ {1, . . . , k}

(5) s j (x) = j i=1 x ↓ i j i=1 y ↓ i = s j (y),
where x ↓ and y ↓ are the decreasing rearrangements of x and y; note that for j = k we actually have an equality, since x and y are probability vectors. We extend the functions s j , by functional calculus, to selfadjoint matrices X ∈ M k (C). The majorization relation can also be characterized in the following way: for a probability vector y and a permutation σ ∈ S k , denote by σ.y the vector obtained by permuting the coordinates of y along σ : (σ.y) i = y σ(i) . Then

x ≺ y iff. x ∈ S(y),

where S(y) is the convex hull of the set {σ.y | σ ∈ S k }. Moreover, the extremal points of S(y) are exactly y and its permutations σ.y. In Figure 2, we plot ∆ 3 , the 2-dimensional simplex together with the sets S(β (t) ), for t = 1/k ′ and k ′ = 2, 3, 4, 5, 10, 20, 50, 100. Notice that for k ′ = 2, 3, the set S(β (1/k ′ ) ) touches the triangle ∆ 3 , because of the fact that β (t) has in this case a zero coordinate.

We can now state the main result of this section: Theorem 4.1. Let t be a parameter in (0, 1) and ε > 0. Let S(β (t) ) + ε be the ε-ball around S(β (t) ) in ∆ k . Then, almost surely when n → ∞, for all input density matrix ρ,

(6) spec(Φ(ρ)) ∈ S(β (t) ) + ε.
Moreover, β (t) is optimal: a probability vector β ∈ ∆ k such that, with positive probability,

(7) spec(Φ(ρ)) ∈ S(β) + ε ∀ρ must satisfy β (t) ≺ β.
We split the proof of Theorem 4.1 into several lemmas. The first one is an easy consequence of the definition of the operator norm. Proof. Since QRQ is a self adjoint operator, we have:

QRQ ∞ = sup y 1 QRQy, y = sup y 1 RQy, Qy = sup x∈Im Q x 1 Rx, x = max x∈Im Q Tr(P x R).
The following lemma is a reformulation of the min-max theorem:

Lemma 4.3. Let λ 1 λ 2 • • • λ k be the Schmidt coefficients of a vector x ∈ C nk . Then, for all 1 j k, s j (x) = λ 1 + λ 2 + • • • + λ j = max F ∈Gr j (C k ) Tr(P x P C n ⊗F ).
Proof. Since λ i are the eigenvalues of Tr n P x ∈ M k (C), the min-max theorem for Tr n P x can be stated as:

s j (x) = max F ∈Gr j (C k )
Tr(P F Tr n P x ).

The conditional expectation property of the partial trace implies that

s j (x) = max F ∈Gr j (C k ) Tr(P x • I n ⊗P F ) = max F ∈Gr j (C k ) Tr(P x • P C n ⊗F ).
We are interested in majorization inequalities which hold uniformly for all norm one elements of a subspace V . In other words, we are interested in the quantity max

x∈V x =1 s j (x) = max x∈V x =1 max F ∈Gr j (C k ) Tr(P x P C n ⊗F ).
Since k is a fixed parameter of our model, in order to compute the maximum over the Grassmannian, it suffices to consider only a finite number of subspaces F : Lemma 4.4. For all ε > 0, for all j, there exists a finite number of j-dimensional subspaces

F 1 , . . . , F N ∈ Gr j (C k ) such that, for all x ∈ C nk , N max i=1 Tr(P x P C n ⊗F i ) s j (x) N max i=1 Tr(P x P C n ⊗F i ) + ε.
Note that in Lemma 4.4, N does depend on ε but can be chosen to be finite for any ε > 0.

Proof. We only need to prove the second inequality. Since the Grassmannian Gr j (C k ) is compact and metric for d(E, F ) = P E -P F ∞ , for all ε > 0 there exists a covering of Gr j (C k ) by a finite number of balls of radius ε centered in F 1 , . . . , F N . Fix some x ∈ C nk and consider the element F ∈ Gr j (C k ) for which the maximum in the definition of s j (x) is attained. F is inside some ball centered at F i and we have Proof of Theorem 4.1. First, notice that it suffices to show (6) holds for rank one projectors ρ = P x . The general case follows from the convexity of the functions s 1 , . . . , s k .

Tr(P x P C n ⊗F ) Tr(P x P C n ⊗F i ) + |Tr(P x (P C n ⊗F ) -P C n ⊗F i ))| = = Tr(P x P C n ⊗F i ) + P F -P F i ∞ Tr(P x P C n ⊗F i ) + ε,
Let ε > 0 and j ∈ {1, . . . , k}. For a random subspace V ⊂ C nk of dimension p n ∼ tnk,

max x∈V x =1 s j (x) = max x∈V x =1 max F ∈Gr j (C k )
Tr(P x P C n ⊗F ).

Using the compactness argument in Lemma 4.4, one can consider (at a cost of ε) only a finite number of subspaces F :

max x∈V x =1 s j (x) N max i=1 max x∈V x =1
Tr(P x P C n ⊗F i ) + ε.

According to Theorem 2.2, for all i ∈ {1, . . . N }, almost surely when n → ∞,

lim n P V P C n ⊗F i P V ∞ = ϕ(j/k, t).
Since N is finite, with probability one, the above equality is true for all i. Next, using Lemma 4.2, one has that, almost surely, lim sup

n max x∈V x =1 s j (x) ϕ(j/k, t) + ε,
which concludes the proof of the direct implication.

Conversely, let β ∈ ∆ k be a probability vector which satisfies Equation [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability Probab[END_REF]. For j ∈ {1, 2, . . . , k} fixed, let F 0 be a subspace of C k of dimension j. We have max

x∈V x =1 s j (x) = max x∈V x =1 max F ∈Gr j (C k ) Tr(P x P C n ⊗F ) max x∈V x =1 Tr(P x P C n ⊗F 0 ) = P V P C n ⊗F 0 P V ∞ a.s. ---→ n→∞ ϕ(j/k, t).
Since, with positive probability, max x∈V x =1 s j (x) s j (β) + ε, we conclude that s j (β) ϕ(j/k, t) = s j (β (t) ) and the proof is complete.

The interest of Theorem 4.1 in comparison to Theorem 3.2 is that it does not rely specifically on one measurement of entanglement, as we are able to confine almost surely the eigenvalues in a convex set. Also, our argument relies neither on concentration inequalities nor on net estimates, as we fix k. However, unlike Theorem 3.2, Theorem 4.1 does not give explicit control on n. It is theoretically possible to give an explicit control on n (using techniques introduced in [START_REF] Ledoux | Differential operators and spectral distributions of invariant ensembles from the classical orthogonal polynomials part I: the continuous case[END_REF]), but this would lead to considerably involved technicalities.

Application to Entropies.

Once the eigenvalues of the output of a channel have been confined inside a fixed convex polyhedron, entropy inequalities follow easily. Indeed, the confining polyhedron is defined in terms of the majorization partial order, and thus the notion of Schur-convexity (see [START_REF] Bhatia | Matrix Analysis[END_REF]) is crucial in what follows.

A function f : R k → R is said to be Schur-convex if x ≺ y implies f (x) f (y). The Rényi entropies H p are Schur-concave, and thus majorization relations x ≺ y imply H p (x) H p (y) for all p 1. The reciprocal implication has been studied in [START_REF] Aubrun | Catalytic majorization and lp norms[END_REF][START_REF] Aubrun | Stochastic domination for iterated convolutions and catalytic majorization[END_REF]: entropy inequalities H p (x) H p (y) (for all p 1) characterize a weaker form of majorization called catalytic majorization, which has applications in LOCC protocols for the transformation of bipartite states.

For the purposes of this paper, the main corollary of Theorem 4.1 is the following Theorem 4.5. For a fixed parameter t, almost surely, when n → ∞, for all input ρ ∈ D tnk ,

lim inf n H p min (Φ U ) H p (β (t) ).
Proof. This follows directly from Theorem 4.1 and from the Schur-concavity of the Rényi entropies.

New examples and counterexamples of superadditive channels

Since our main result, Theorem 4.1, is valid almost surely in the limit n → ∞, the limiting objects depend only on the (a priori fixed) parameters k and t. In what follows, we consider large values of the parameter k, and introduce the "little-o" notation o(•) with respect to the limit k → ∞.

5.1. Superadditivity. We start with a crucial recent series of result, which we summarize into the following theorem: Theorem 5.1. For all p 1, there exist quantum channels Φ 1 and Φ 2 such that

(8) H p min (Φ 1 ⊗ Φ 2 ) < H p min (Φ 1 ) + H min (Φ 2
). This theorem results mainly from the papers [START_REF] Hastings | A Counterexample to Additivity of Minimum Output Entropy[END_REF][START_REF] Hayden | The maximal p-norm multiplicativity conjecture is false[END_REF][START_REF] Hayden | Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1[END_REF]. Note that the equality

H p min (Φ 1 ⊗ Φ 2 ) = H p min (Φ 1
) + H min (Φ 2 ) for any Φ 1 and Φ 2 and any p > 1 was a conjecture until 2007, and that even nowadays, no concrete counterexamples are known for p small or p = 1.

The Bell phenomenon.

In order to provide counterexamples for the additivity conjectures, one has to produce lower bounds for the minimum output entropy of single copies of the channels (and this is where Theorem 4.1 is useful) and upper bounds for the minimum output entropy of the tensor product of the quantum channels. The latter task is somewhat easier, since one has to exhibit a particular input state such that the output has low entropy.

The choice of the input state for the product channel is guided by the following observation. It is clear that if one chooses a product input state ρ = ρ 1 ⊗ ρ 2 , then the output state is still in product form, and the entropies add up:

H p ([Φ 1 ⊗ Φ 2 ](ρ 1 ⊗ ρ 2 )) = H p (Φ 1 (ρ 1 ) ⊗ Φ 2 (ρ 2 )) = H p (Φ 1 (ρ 1 )) + H p (Φ 2 (ρ 2 )).
Hence, such choices cannot violate the additivity of Rényi entropies. Instead, one has to look at entangled states, and the maximally entangled states are obvious candidates.

All our examples rely on the study of the product of conjugate channels

Φ n ⊗ Φ n where Φ n (X) = Tr n (U n χ n (X)U * n ), Φ n (X) = Tr n (U n χ n (X)U t n
) have been introduced in subsection 3.2. Our task is to obtain a good upper bound for

lim sup n H p min (Φ n ⊗ Φ n ).
Our strategy is systematically to write

lim sup n H p min (Φ n ⊗ Φ n ) H p min (Φ n ⊗ Φ n (E tnk ))
where E tnk is the maximally entangled state over the input space (C tnk ) ⊗2 . More precisely, E tnk is the projection on the Bell vector

Bell tnk = 1 √ tnk tnk i=1 e i ⊗ e i ,
where {e i } tnk i=1 is a fixed basis of C tnk . Using the graphical formalism of [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF], we are dealing with the diagram in Figure 3 (recall that square symbols correspond to C k , round symbols correspond to C n , diamond ones to C tnk and triangle-shaped symbols correspond to C 1/t ).

U U * Z = Φ U ⊗ Φ Ū (E tnk ) = Ū Ū * 1 tnk U Ū = Ū U 1 tnk Figure 3. Z n = Φ U ⊗ Φ Ū (E tnk )
The random matrix Φ n ⊗ Φ n (E tnk ) was thoroughly studied in our previous paper [START_REF] Collins | Random quantum channels I: Graphical calculus and the Bell state phenomenon[END_REF] and we recall here one of the main results of this paper: Theorem 5.2. Almost surely, as n → ∞, the random matrix

Φ n ⊗ Φ n (Bell tnk ) ∈ M k 2 (C) has eigenvalues γ (t) =     t + 1 -t k 2 , 1 -t k 2 , . . . , 1 -t k 2 k 2 -1 times     .
From this we deduce the following corollary, which gives an upper bound for the minimum output entropy for the product channel Φ ⊗ Φ:

Corollary 5.3. Almost surely, as n → ∞, lim sup n H p min (Φ n ⊗ Φ n ) 1 1 -p log t + 1 -t k 2 p + (k 2 -1) 1 -t k 2 p
In the case p = 1 the upper bound simplifies to

lim sup n H min (Φ n ⊗ Φ n ) -t + 1 -t k 2 log t + 1 -t k 2 -(k 2 -1) 1 -t k 2 log 1 -t k 2 .
5.3. Macroscopic counterexamples for the Rényi entropy. In this section, we start by fixing t = 1/2. We assume that k is even, in order to avoid non-integer dimensions. A value of 1/2 for t means that the environment to which the input of the channel is coupled is 2-dimensional, i.e. a single qubit. The main result of this section is that we obtain a violation of the Rényi entropy in this simplest purely quantum case, k ′ = 2. Using Theorem 5.2, the asymptotic eigenvalue vector for the output of the product channel is

γ = γ (1/2) = 1 2 + 1 2k 2 , 1 2k 2 , . . . , 1 2k 2 .
The series expansion for H p (γ) when k → ∞ and the Corollary 5.3 imply that, almost surely, [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF] lim sup

n H p min (Φ ⊗ Φ) p p -1 log 2 + o(1).
In the case of a single channel, since ϕ(x, 1/2) = 1/2 + x(1x), the vector β = β (1/2) is has a particularly simple form in this case:

β 1 = 1 2 + √ k -1 k , β j = ψ j k -ψ j -1 k , ∀ 2 j k/2, β j = 0, ∀ k/2 < j k,
where ψ(x) = x(1x). Note that the first eigenvalue is large (of order 1/2) and that the others are small:

β j 1 k ψ ′ 1 k 1 √ k , ∀ 2 j k/2. Theorem 5.4. Almost surely as n → ∞, lim inf n H p min (Φ) = lim inf n H p min (Φ) p p -1 log 2 + o(1). Since lim sup n H p min (Φ ⊗ Φ) p p -1 log 2 + o(1),
the additivity of the Rényi p-norms is violated for all p > 1.

Proof. We shall provide a lower bound for H p (β). Notice that the main contribution is given by the largest eigenvalue:

β p 1 = 2 -p + o(1)
. Next, we show that the contribution of the smaller eigenvalues is asymptotically zero. We consider three cases: p > 2, p = 2 and 1 < p < 2. If p > 2, then

j 2 β p j j 2 k -p/2 k 1-p/2 = o(1).
For p = 2, one has:

j 2 β 2 j = k/2 j=2 ψ( j k ) -ψ( j -1 k ) 2 k/2 j=2 1 k • sup (j-1)/k x j/k ψ ′ (x) 2 = k/2 j=2 1 k ψ ′ j -1 k 2 = 1 k k/2-1 j=1 (1 -2j/k) 2 4j(1 -j/k) = o(1).
The case 1 < p < 2 is more involved:

j 2 β p j k/2 j=2 1 k ψ ′ j -1 k p k 1-p 1/2 0 ψ ′ (t) p dt = o(1).
Hence, in all three cases, H p (β) p p-1 log 2 + o(1). This inequality and Eq. ( 9) provide the announced violation of the additivity conjecture for Rényi entropies.

H p min (Φ n ⊗ Φ n ) p p -1 log 2 < 2 • p p -1 log 2 + o(1) 2H p min (Φ n ).
Let us now come back to the more general case of arbitrary t ∈ (0, 1) fixed. It is natural to ask whether the bound H p (β (t) ) is optimal. Even though this is an open question for fixed k, the corollary below implies that it is asymptotically optimal for large k. More precisely, let Φ k,n be the random quantum channel Φ n introduced in Section 3.2 (since k will vary in the statement below, we need to keep track of it). We can then state the following Corollary 5.5. For all p > 1, there exists a sequence n k tending to infinity as k tends to infinity, such that, almost surely

lim k H p min (Φ k,n k ⊗ Φ k,n k ) = lim k H p min (Φ k,n k ) = p 1 -p log t.
In particular this means that we can almost surely estimate the Schatten S 1 → S p norm of that quantum channel:

lim k ||Φ k,n k ⊗ Φ k,n k || S 1 →Sp = lim k ||Φ k,n k || S 1 →Sp = t
Proof. For t = 1/2, this follows directly by a diagonal argument from Theorem 5.4 and Equation ( 9) together with the simple fact that the entropy increases when one takes tensor products:

H p min (Φ k,n k ) H p min (Φ k,n k ⊗ Φ k,n k ).
The asymptotic estimates of Theorem 5.4 are readily adapted to arbitrary t ∈ (0, 1). As for the norm estimate, it follows from the definition of the Schatten norm and the Rényi entropy, as well as the fact that the S 1 → S p norm is attained on density matrices.

It is remarkable that the norm estimate for ||Φ ⊗ Φ|| S 1 →Sp given by ||Φ ⊗ Φ(E tnk )|| Sp is actually optimal. The above corollary stands as a mathematical evidence that the Bell states asymptotically maximize the S 1 → S p norm of Φ ⊗ Φ.

The first example of 'Rényi superadditive' quantum channel was obtained by Holevo and Werner in [START_REF] Werner | Counterexample to an additivity conjecture for output purity of quantum channels[END_REF] using a deterministic channel. However, their example violated the additivity conjecture only for p > 4.79. Hayden and Winter found a class of random counter examples for the whole range of parameters p > 1 in [START_REF] Hayden | The maximal p-norm multiplicativity conjecture is false[END_REF]. Our being able to prescribe t in the counterexample of Theorem 5.4 is an improvement to the counterexamples provided in the paper [START_REF] Hayden | Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1[END_REF] (even though there is evidence that the very recent techniques of [START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF][START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF] could be applied for p > 1 and finite t -yet perhaps not as big as 1/2 or 1/3).

Physically, this means that to obtain a counterexample, it is enough to couple randomly the input to a qubit (k ′ = 1/t = 2) to obtain a counterexample. The above reasoning applies actually for any t. In the following corollary we focus on the case t = 1/k ′ for integer k ′ , as it is more relevant physically.

Corollary 5.6. For each p > 1 and each integer k ′ 2, let t = 1/k ′ . There exists an integer k 0 such that for all k k 0 , one has almost surely

lim sup n H p min (Φ ⊗ Φ) < 2 lim inf n H p min (Φ)
Since the proof is very similar to the case k ′ = 2, instead of providing the details, we plot in Figure 4 acceptable values for k 0 as functions of p, for several values of k ′ = 1/t:

k 0 (t, p) = min{k ∈ N | lim sup n H p (Φ ⊗ Φ)(E tnk ) < 2H p (β (t) )}.
Note that k 0 as defined above may note be the smallest dimension yielding a violation of p-Rényi additivity. It may be that a better choice for the input state of the product channel could yield a smaller value for H p min (Φ ⊗ Φ). As the plots suggest, the values of k 0 are not bounded when p → 1. This fact is independent on the choice of the parameter t = 1/k ′ . The results of [START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF][START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF] suggest that there should be a k ′ large enough for which it is possible to keep k 0 bounded as p → 1. This improvement is due to their better bounds on H p min (Φ), obtained using the techniques developed by Hastings in [START_REF] Hastings | A Counterexample to Additivity of Minimum Output Entropy[END_REF]. We finish this section by a computation showing that the above bounds are not good enough to obtain the violation of the additivity conjecture in the case p = 1. We start with the entropy of the product channel:

H(γ) = log k + log 2 + o(1).
For the case of the single channel, we need an upper bound for H(β (1/2) ) (recall that h(x) = -x log x):

H(β) = h(β 1 ) + k/2 j=2 h(β j ) = log 2 2 + k/2 j=2 h ψ j k -ψ j -1 k + o(1) log 2 2 + k/2 j=2 h 1 k • sup (j-1)/k x j/k ψ ′ (x) + o(1) = log 2 2 + k/2 j=2 h 1 k ψ ′ j -1 k + o(1). Using h 1 k ψ ′ j k = log k k ψ ′ j k + 1 k [h • ψ ′ ] j k and 1/2 0 [h • ψ ′ ](t) dt = - log 2 2 ,
we obtain

H(β (1/2) ) log 2 2 + k/2-1 j=1 log k k ψ ′ j k + k/2-1 j=1 1 k [h • ψ ′ ] j k + o(1) = log 2 2 + 1 2 log k - log 2 2 + o(1) = log k 2 + o(1).
At the end, the entropy deficit is

H(γ) -2H(β) log 2 + o(1) > 0,
which does not yield a violation of the minimum output von Neumann entropy.

5.4.

The case t = k -α . We conclude this paper with the study of the case t = k -α , where α > 0 is a fixed parameter. This corresponds to an exploration of a larger environment size C k α . To simplify the computations, we consider only the case of the minimum output von Neumann entropy. As before, we provide estimates, when k is fixed but large, for the minimum output entropies of Φ ⊗ Φ and Φ. We start with the simpler case of the product channel Φ ⊗ Φ. Theorem 5.2 provides the almost sure eigenvalues of [Φ ⊗ Φ](E tnk ):

γ = γ (k -α ) =     1 k α + 1 k 2 - 1 k α+2 , 1 k 2 - 1 k α+2 , . . . , 1 k 2 - 1 k α+2 k 2 -1 times     .

Using the series expansion

h(1 -x) = x -x 2 /2 + o(x 2
), one can compute the asymptotics for the minimum output entropy: Proposition 5.7. For the product channel Φ ⊗ Φ, the following upper bounds hold almost surely:

(10) H min (Φ ⊗ Φ) H(γ) =      2 log k -(2-α) log k k α + o log k k α if 0 < α < 2; 2 log k -2 log 2-1 k 2 + o 1 k 2 if α = 2; 2 log k -1 2k 2α-2 + o 1 k 2α-2 if α > 2.
Our estimate for the single channel case is as follows: Proposition 5.8. For all α > 0, the following lower bound holds true almost surely:

H min (Φ) H min (β) = log k - log k k α + o log k k α .
For the purposes of this proof, we define ϕ

k : [0, 1 -k -α ] → [0, 1], ϕ k (x) = ϕ(x, k -α ) and h(x) = -x log x. We have ∂ ∂x ϕ(x, y) = 1 -2y + y(1 -y) √ 1 -x √ x - √ x √ 1 -x = (1 -2y) 1 + g(x) g(y) ,
where the function g : (0, 1) → R is defined by

g(x) = √ 1 -x √ x - √ x √ 1 -x .
Proof. According to Theorem 4.5, for all ε > 0,

H min (Φ) H(β) -ε, where β = β (k -α )
is the k-dimensional vector defined by

β 1 = ϕ k 1 k ; β j = ϕ k j k -ϕ k j -1 k = 1 k ϕ ′ k ξ j k , ∀ 2 j J; β j = 0 ∀ J < j k.
The index J is the number of non-trivial inequalities we get by using Theorem 4.1, and it is equal to k -1 if α 1 and to ⌊k -

k 1-α ⌋ if α < 1.
Our purpose in what follows is to provide a "good" estimate for H(β). We start by rescaling the eigenvalues: H(β) = log k + 1 k H(kβ). In this way, we can focus on the "entropy defect" log k -H(β) and reduce our problem to showing that The next step in our asymptotic computation is to replace the unknown points ξ j by simpler estimates of the type j/k. Notice that the largest eigenvalue β 1 is of order k -1 . By the continuity of the function h, there exists a constant C > 0 such that |h(kβ j )| C and thus, individual terms in the sum [START_REF] Haagerup | A new application of random matrices: Ext(C * red (F2)) is not a group[END_REF] have no asymptotic contribution. Moreover, we can assume J = k -1, ignoring at most k 1-α terms which have again no asymptotic contribution. It is clear that the function x → ϕ ′ k (x) is decreasing at fixed k and since the entropy function h is increasing for x ∈ (0, e -1 ) and decreasing for x e -1 ,we can bound h(ϕ ′ k (ξ j /k)) by h(ϕ ′ k (j/k)), and we reduce our problem to showing that (12)

k α-1 log k k-1 j=1 h ϕ ′ k j k ---→ k→∞ -1,
or, equivalently,

k α-1 log k ⌊k/2⌋ j=1 h ϕ ′ k j k + h ϕ ′ k 1 - j k ---→ k→∞ -1.

Now,

h (1 -2y) 1 + g(x) g(y) + h (1 -2y) 1 -g(x) g(y) = = 2h(1 -2y) + (1 -2y) h 1 + g(x) g(y) + h 1 -g(x) g(y) .

The term 2h(1 -2y) = 2h(1 -2k -α ) ∼ 4k -α has no asymptotic contribution and, using h(1 + t) + h(1t) = -t 2 + O(t 4 ), we are left with computing the limit of the main contribution k α-1 log k (1 -2j/k) 4 (1j/k) 2 converges to zero. In conclusion, we have shown that Equation ( 11) holds and we deduce that

H(β) = log k - log k k α + o log k k α .
. The bounds obtained in this section do not yield a violation of the Holevo additivity conjecture. However, after the first version of this paper was released, Brandao-Horodecki [START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF] and Fukuda-King [START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF] used the same model as ours and adapted original ideas from Hastings [START_REF] Hastings | A Counterexample to Additivity of Minimum Output Entropy[END_REF] to prove that this model can also lead to a violation of the minimum output entropy additivity.

The techniques in [START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF][START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF] yield more information on the possibility of large values of the minimum output entropy for the model under discussion. However, our proofs are of free probabilistic nature and yield results of almost sure nature. In addition, [START_REF] Brandao | On Hastings's counterexamples to the minimum output entropy additivity conjecture[END_REF][START_REF] Fukuda | Entanglement of random subspaces via the Hastings bound[END_REF] rely very much on the actual properties of Shannon's entropy function, whereas our techniques attack directly the question of the behavior of the eigenvalues.

We conjecture that the set S(β (t) ) (having the property that for any ε > 0, S(β (t) ) + ε contains almost surely the eigenvalues of outputs of random quantum channels) can be made smaller and actually optimal, thus yielding as a byproduct that all the values H min (Φ) converge almost surely. However, the results of this paper show that the notion of majorization is not sufficient to achieve this goal.

Theorem 3 . 2 (

 32 Hayden, Leung, Winter, [15], Theorem IV.1). Let A and B be quantun systems of dimesion d a and d B with d b d A 3 Let 0 < α < log d A . Then there exists a subspace S ⊂ A ⊗ B of dimension

Figure 2 .

 2 Figure 2. The 2-dimensional probability simplex with the sets S(β (t) ), for t = 1/k ′ and k ′ = 2, 3, 4, 5, 10, 20, 50, 100.

Lemma 4 . 2 .

 42 Let Q, R be two selfadjoint projections in M n (C). Then QRQ ∞ = max x∈Im Q Tr(P x R).

  and the conclusion follows. Now we are ready to prove Theorem 4.1.

Figure 4 .

 4 Figure 4. Plots of k 0 , i.e. acceptable values of k for which we get an asymptotic additivity violation, in function of p, for different values of k ′ = 1/t. Two ranges for p are plotted separately: p ∈ [1.1, 2] in (a) and p ∈ [2, 5] in (b).

Acknowledgments

This paper was completed while one author (B.C.) was visiting the university of Tokyo and then the university of Wroc law and he thanks these two institutions for providing him with a very fruitful working environment. I.N. thanks Guillaume Aubrun for useful discussions.

B.C. was partly funded by ANR GranMa and ANR Galoisint. The research of both authors was supported in part by NSERC grants including grant RGPIN/341303-2007.


Irénée Briquel
email: irenee.briquel@ens-lyon.fr

LIP ⋆ Pascal Koiran
email: pascal.koiran@ens-lyon.fr

A Dichotomy Theorem for Polynomial Evaluation

Keywords: Algebraic complexity, polynomial evaluation, Valiant's model, Constraint Satisfaction Problems, dichotomy theorem, #P-completeness

A dichotomy theorem for counting problems due to Creignou and Hermann states that or any finite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete. In the present paper we show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated families of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials. We also prove that several problems which were known to be #P-complete under Turing reductions only are in fact #P-complete under many-one reductions.

Introduction

.

In a seminal paper, Schaefer [START_REF] Schaefer | The complexity of satisfiability problems[END_REF] proved a dichotomy theorem for boolean constraint satisfaction problems: he showed that for any finite set S of logical relations the satisfiability problem SAT(S) for S-formulas is either in P, or NP-complete. Here, an S-formula over a set of n variables is a conjunction of relations of S where the arguments of each relation are freely chosen among the n variables. Schaefer's result was subsequently extended in a number of directions. In particular, dichotomy theorems were obtained for counting problems, optimization problems and the decision problem of quantified boolean formulas. An account of this line of work can be found in the book by Creignou, Khanna and Sudan [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF]. In a different direction, constraint satisfaction problems were also studied over non-boolean domains. This turned out to be a surprisingly difficult question, and it took a long time before a dichotomy theorem over domains of size 3 could be obtained [1].

In the present paper we study polynomial evaluation from this dichotomic point of view. We work within Valiant's algebraic framework: the role of the complexity class NP in Schaefer's dichotomy theorem will be played by the class VNP of "easily definable" polynomial families, and the role of P will be played by the class VP of "easily computable" polynomial families [START_REF] Valiant | Completeness classes in algebra[END_REF][START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]. There is a well-known connection between counting problems and polynomial evaluation. For instance, as shown by Valiant the permanent is complete in both settings [START_REF] Valiant | The complexity of computing the permanent[END_REF][START_REF] Valiant | Completeness classes in algebra[END_REF]. In the realm of counting problems, a dichotomy theorem was obtained by Creignou and Hermann [START_REF] Creignou | Complexity of generalized satisfiability counting problems[END_REF][START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF].

Theorem 1. For any finite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete.

In fact, the sets S such that #SAT(S) is in FP are exactly the sets containing only affine constraints (a constraint is called affine if it expressible as a system of linear equations over Z/2Z).

Main Contributions

To a family of boolean formulas (φ n ) we associate the multilinear polynomial family

P (φ n )(X) = ε φ n (ε)X ε , (1)
where X ε is the monomial

X ε1 1 • • • X ε k(n)
k(n) , and k(n) is the number of variables of φ n . Imagine that the φ n are chosen among the S-formulas of a fixed finite set S of logical relations. One would like to understand how the complexity of the polynomials P (φ n ) depends on S. Definition 1. A family (φ n ) of S-formulas is called a p-family if φ n is a conjunction of at most p(n) relations from S, for some polynomial p (in particular, φ n depends on polynomially many variables when S is finite).

Theorem 2 (Main Theorem). Let S be a finite set of logical relations. If S contains only affine relations of at most two variables, then the families (P (φ n )) of polynomials associated to p-families of S-formulas (φ n ) are in VP. Otherwise, there exists a p-family (φ n ) of S-formulas such that the corresponding polynomial family P (φ n ) is VNP-complete.

We can remark, that the hard cases for counting problems are strictly included in our hard evaluation problems, exactly as the hard decision problems in Schaefer's theorem were strictly included in the hard counting problems.

In our algebraic framework the evaluation of the polynomial associated to a given formula consists in solving a "weighted counting" problem: each assignment (ε 1 , . . . , ε k ) of the variables of φ comes with a weight

X ε1 1 • • • X ε k k .
In particular, when the variables X i are all set to 1, we obtain the counting problem #SAT(S). It is therefore natural that evaluation problems turn out to be harder than counting problems.

The remainder of this paper is mostly devoted to the proof of Theorem 2.

Allong the way, we obtain several results of independent interest. First, we obtain several new VNP-completeness results. The main ones are about:

(i) the vertex cover polynomial VCP(G) and the independent set polynomial IP(G), associated to a vertex-weighted graph G. Most VNP-completeness results in the literature (and certainly all the results in Chapter 3 of [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]) are about edge-weighted graphs. (ii) the antichain polynomial AP(X) and the ideal polynomial IPP(X), associated to a weighted poset (X, ≤).

Unlike in most VNP-completeness results, we need more general reductions to establish VNP-completeness results than Valiant's p-projection. In Section 6, we use the "c-reductions", introduced by Bürgisser [2,[START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF] in his work on VNP families that are neither p-computable nor VNP-complete. They are akin to the oracle (or Turing) reductions from discrete complexity theory. The c-reduction has not been used widely in VNP-completeness proofs. The only examples that we are aware of are: (i) A remark in [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF] on probability generating functions. (ii) The VNP-completeness of the weighted Tutte polynomial in [START_REF] Lotz | On the algebraic complexity of some families of coloured Tutte polynomials[END_REF]. Even there, the power of c-reductions is used in a very restricted way since a single oracle call is performed in each reduction.

By contrast, the power of oracle reductions has been put to good use in #Pcompleteness theory (mostly as a tool for performing interpolation). Indeed, as pointed out in [START_REF] Jerrum | Counting, Sampling and Integrating : Algorithms and Complexity[END_REF], "interpolation features prominently in a majority of #Pcompleteness proofs", and "it is not clear whether the phenomenon of #Pcompleteness would be as ubiquitous if many-one reducibility were to be used in place of Turing." We argue that the importance of Turing reductions in #Pcompleteness should be revised downwards since, as a byproduct of our VNPcompleteness results, we can replace Turing reductions by many-one reductions in several #P-completeness results from the literature. In particular, we obtain a many-one version of Creignou and Hermann's dichotomy theorem 1 . We leave it as an open problem whether the 0/1 partial permanent is #P-complete under many-one reductions (see Section 3 for a definition of the partial permanent, and [START_REF] Jerrum | Two-dimensional monomer-dimer systems are computationally intractable[END_REF] for a # P-completeness proof under oracle reductions).

Organization of the Paper and Additional Results

Earlier in this section we gave an informal introduction to constraint satisfaction problems. We give more precise definitions at the beginning of Section 2. The remainder of that section is devoted to Valiant's algebraic model of computation. We also deal briefly with the easy cases of Theorem 2 (Remark 1).

We then establish the proof of the hard cases of Theorem 2, beginning with the case of non affine constraints. For that case, the high-level structure of the proof is similar to Creignou and Hermann's proof of #P-completeness of the corresponding counting problems in [START_REF] Creignou | Complexity of generalized satisfiability counting problems[END_REF]. The singletons S = {OR 2 }, S = {OR 1 } and S = {OR 0 } play a special role in the proof. Here OR 2 denotes the negative two-clause (x, y) → (x ∨y); OR 0 denotes the positive two-clause (x, y) → (x∨y); and OR 1 denotes the implicative two-clause (x, y) → (x ∨ y). The corresponding VNP-completeness results for S = {OR 2 } and S = {OR 0 } are established in section 3; the case of {OR 1 } is treated in Section 4.These results are put together with Creignou and Hermann's results in Section 5 to establish the existence of a VNP-complete family for any set S containing non affine clauses (Theorem 8). Section 6 deals with the affine clauses with at least three variables (Theorem 9). This completes the proof of Theorem 2. In Section 7, we build on our VNP-completeness results to prove #P-completeness under many-one reductions for several problems which were only known to be #P-complete under oracle reductions.

Preliminaries

Constraint satisfaction problems

We define a logical relation to be a function from {0, 1} k to {0, 1}, for some integer k called the rank of the relation. Let us fix a finite set S = {φ 1 , . . . , φ n } of logical relations. An S-formula over n variables (x 1 , . . . , x n ) is a conjunction of boolean formulas, each of the form g i (x ji (1) , . . . , x ji(ki) ) where each g i belongs to S and k i is the rank of g i . In words, each element in the conjunction is obtained by applying a function from S to some variables chosen among the n variables. An instance of the problem SAT(S) studied by Schaefer [START_REF] Schaefer | The complexity of satisfiability problems[END_REF] is an S-formula φ, and one must decide whether φ is satisfiable. For instance, consider the 3 boolean relations OR 0 (x, y) = x∨y, OR 1 (x, y) = x∨y and OR 2 (x, y) = x∨y. The classical problem 2-SAT is SAT(S) where S = {OR 0 , OR 1 , OR 2 }. The counting problem #SAT(S) was studied by Creignou and Hermann [START_REF] Creignou | Complexity of generalized satisfiability counting problems[END_REF]. In this paper we study the complexity of evaluating the polynomials P (φ) in (1). We establish which sets S give rise to VNP-complete polynomial families, and which one give rise only to easy to compute families. We next define these notions precisely.

#P-completeness and VNP-completeness

Let us introduce the notion of many-one reduction for counting problems [START_REF] Zankó | #P-completeness via many-one reductions[END_REF]: Definition 2 (Many-one reduction). Let f : {0, 1} * → N and g : {0, 1} * → N be two counting problems. A many-one reduction from f to g consists of a pair of polynomial-time computable functions σ : {0, 1} * → {0, 1} * and τ : N → N such that for every x ∈ {0, 1} * , the equality f (x) = τ (g(σ(x))) holds. When τ is the identity function, this reduction is called parsimonious.

A counting problem f is #P-hard under many-one reduction if every problem in #P admits a many-one reduction to f . In Valiant's model one studies the computation of multivariate polynomials. This can be done over any field. In the sequel we fix a field K of characteristic = 2. All considered polynomials are over K.

A p-family is a sequence f = (f n ) of multivariate polynomials such that the number of variables and the degree are polynomially bounded functions of n. A prominent example of a p-family is the permanent family PER = (PER n ), where PER n is the permanent of an n×n matrix with independent indeterminate entries.

We define the complexity of a polynomial f to be the minimum number L(f ) of nodes of an arithmetic circuit computing f . We recall that the internal nodes of an arithmetic circuit perform additions or multiplications, and each input node is labeled by a constant from K or a variable X i .

Definition 3 (VP). A p-family (f n ) is p-computable if L(f n ) is a

Definition 4 (VNP).

A p-family (f n ) is called p-definable if there exists a p-computable family g = (g n ) such that f n (X 1 , . . . , X p(n) ) = ε∈{0,1} q(n) g n (X 1 , . . . , X p(n) , ε 1 , . . . , ε q(n) )
The set of p-definable families forms the class VNP.

Clearly, VP is included in VNP. To define VNP-completeness we need a notion of reduction:

Definition 5 (p-projection). A polynomial f with v arguments is said to be a projection of a polynomial g with u arguments, and we denote it

f ≤ g, if f (X 1 , . . . , X v ) = g(a 1 , . . . , a u ) where each a i is a variable of f or a constant from K. A p-family (f n ) is a p-projection of (g m ) if there exists a polynomially bounded function t : N → N such that: ∃n 0 ∀n ≥ n 0 , f n ≤ g t(n) . Definition 6 (VNP-completeness). A p-family g ∈ VNP is VNP-complete if every p-family f ∈ VNP is a p-projection of g.
The VNP-completeness of the permanent under p-projections [START_REF] Valiant | Completeness classes in algebra[END_REF][START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF] is a central result in Valiant's theory.

It seems that p-projections are too weak for some of our completeness results. Instead, we use the more general notion of c-reduction [2,[START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]. First we recall the notion of oracle computation : Definition 7. The oracle complexity L g (f ) of a polynomial f with respect to the oracle polynomial g is the minimum number of arithmetic operations (+, * ) and evaluations of g over previously computed values that are sufficient to compute f from the indeterminates X i and constants from K.

Definition 8 (c-reduction). Let us consider two p-families f = (f n ) and g = (g n ). We have a polynomial oracle reduction, or c-reduction, from f to g (denoted f ≤ c g) if there exists a polynomially bounded function t :

N → N such that the map n → L g t(n) (f n ) is polynomially bounded.
We can define a more general notion of VNP-completeness based on c-

reductions: A p-family f is VNP-hard if g ≤ c f for every p-family g ∈ VNP. It is VNP-complete if in addition, f ∈ VNP.
The new class of VNP-complete families contains all the classical VNP-complete families since every p-reduction is a c-reduction.

In our completeness proofs we need c-reductions to compute the homogeneous components of a polynomial. This can be achieved thanks to a well-known lemma (see e.g. [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]):

Lemma 1. Let f be a polynomial in the variables X 1 , . . . , X n . For any δ such that δ ≤ deg f , let denote f (δ) the homogeneous component of degree δ of f . Then, L f (f (δ)
) is polynomially bounded in the degree of f . By Valiant's criterion (Proposition 2.20 in [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]), for any finite set S of logical relations and any p-family (φ n ) of S-formulas the polynomials (P (φ n )) form a VNP family. Furthermore, the only four boolean affine relations with at most two variables are (x = 0), (x = 1), (x = y) and (x = y). Since for a conjunction of such relations, the variables are either independent or completely bounded, a polynomial associated to a p-family of such formulas is immediately factorizable. Thus :

Remark 1. For a set S of affine relations with at most two variables, every pfamily of polynomials associated to S-formulas is in VP.

All the work in the proof of Theorem 2 therefore goes into the hardness proof.

Monotone 2-clauses

In this section we consider the set {OR 2 } = {(x, y) → (x ∨ y)} and {OR 0 } = {(x, y) → (x ∨ y)}. For S = {OR 2 } and S = {OR 0 }, we show that there exists a VNP-complete family of polynomials (P (φ n )) associated to a p-family of Sformulas (φ n ).

The partial permanent PER * (A) of a matrix A = (A i,j ) is defined by the formula:

PER * (A) = π i∈defπ A iπ(i)
where the sum runs over all injective partial maps from [1, n] to [1, n]. It is shown in [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF] that the partial permanent is VNP-complete (the proof is attributed to Jerrum). The partial permanent may be written as in (1), where φ n is the boolean formula that recognizes the matrices of partial maps from [1, n] to [1, n]. But φ n is a p-family of {OR 2 }-formulas since

φ n (ε) = i,j,k:j =k ε ij ∨ ε ik ∧ i,j,k:i =k ε ij ∨ ε kj .
Here the first conjunction ensures that the matrix ε has no more than one 1 on each row; the second one ensures that ε has no more than one 1 on each column. We have obtained the following result.

Theorem 3. The family (φ n ) is a p-family of {OR 2 }-formulas, and the polynomial family

(P (φ n )) is VNP-complete under p-projections.
The remainder of this section is devoted to the set S = {OR 0 } = {(x, y) → x ∨ y}. The role played by the partial permanent in the previous section will be played by vertex cover polynomials. There is more work to do because the corresponding VNP-completeness result is not available from the literature.

Consider a vertex-weighted graph G = (V, E):

to each vertex v i ∈ V is associated a weight X i . The vertex cover polynomial of G is VCP(G) = S vi∈S X i (2)
where the sum runs over all vertex covers of G (recall that a vertex cover of G is a set S ⊆ V such that for each edge e ∈ E, at least one of the two endpoints of e belongs to S). The univariate vertex cover polynomial defined in [START_REF] Dong | The vertex-cover polynomial of a graph[END_REF] is a specialization of ours; it is obtained from VCP(G) by applying the substitutions X i := X (for i = 1, . . . , n), where X is a new indeterminate.

Our main result regarding {OR 0 }-formulas is as follows.

Theorem 4. There exists a family G n of polynomial size bipartite graphs such that:

1. The family

(VCP(G n )) is VNP-complete. 2. VCP(G n ) = P (φ n ) where φ n is a p-family of {OR 0 }-formulas.
Given a vertex-weighted graph G, let us associate to each v i ∈ V a boolean variable ε i . The interpretation is that v i is chosen in a vertex cover when ε i is set to 1. We then have

VCP(G) = ε∈{0,1} |V | (vi,vj )∈E ε i ∨ ε j X ε .
The second property in Theorem 4 will therefore hold true for any family (G n ) of polynomial size graphs.

To obtain the first property, we first establish a VNP-completeness result for the independent set polynomial IP(G). This polynomial is defined like the vertex cover polynomial, except that the sum in (2) now runs over all independent sets S (recall that an independent set is a set S ⊆ V such that there are no edges between any two elements of S).

Theorem 5. There exists a family (G ′ n ) of polynomial size graphs such that

IP(G ′ n ) = PER * n where PER * n is the n × n partial permanent. The family IP(G ′ n ) is therefore VNP-complete.
Proof. The vertices of G ′ n are the n 2 edges ij of the complete bipartite graph K n,n , and the associated weight is the indeterminate X ij . Two vertices of G ′ n are connected by an edge if they share an endpoint in K n,n . An independent set in G ′ n is nothing but a partial matching in K n,n , and the corresponding weights are the same.

Next we obtain a reduction from the independent set polynomial to the vertex cover polynomial. The connection between these two problems is not astonishing since vertex covers are exactly the complements of independent sets. But we deal here with weighted counting problems, so that there is a little more work to do. The connection between independent sets and vertex covers does imply a relation between the polynomials IP(G) and VCP(G). Namely,

IP(G)(X 1 , . . . , X n ) = X 1 • • • X n • VCP(G)(1/X 1 , . . . , 1/X n ). (3)
Indeed,

IP(G) = S independent X 1 • • • X n vi ∈S X i = X 1 • • • X n S ′ vertex cover 1 vi∈S ′ X i .
Recall that the incidence graph of a graph

G ′ = (V ′ , E ′ ) is a bipartite graph G = (V, E) where V = V ′ ∪ E ′ .
In the incidence graph there is an edge between e ′ ∈ E ′ and u ′ ∈ V ′ if u ′ is one of the two endpoints of e ′ in G. When G ′ is vertex weighted, we assign to each V ′ -vertex of G the same weight as in G and we assign to each E ′ -vertex of G the constant weight -1.

Lemma 2. Let G ′ be a vertex weighted graph and G its vertex weighted incidence graph as defined above. We have the following equalities:

VCP(G) = (-1) e(G ′ ) IP(G ′ ) (4) IP(G) = (-1) e(G ′ ) VCP(G ′ ) ( 5
)
where e(G ′ ) is the number of edges of G ′ .

Proof. We begin with (4). To each independent set I ′ of G ′ we can injectively associate the vertex cover C = I ′ ∪ E ′ . The weight of C is equal to (-1) e(G ′ ) times the weight of I ′ . Moreover, the weights of all other vertex covers of G add up to 0. Indeed, any vertex cover C which is not of this form must contain two vertices

u ′ , v ′ ∈ V ′ such that u ′ v ′ ∈ E ′ . The symmetric difference C∆{u ′ v ′ }
remains a vertex cover of G, and its weight is opposite to the weight of C since it differs from C only by a vertex u ′ v ′ of weight -1.

The equality (5) follow from the combination of ( 3) and (4).

To complete the proof of Theorem 4 we apply Lemma 2 to the graph

G ′ = G ′ n of Theorem 5. The resulting graph G = G n satisfies VCP(G n ) = IP(G ′ n ) = PER * n since G ′ n has an even number of edges: e(G ′ n ) = n 2 (n -1).

Implicative 2-clauses

Here we consider the set S = {OR 1 } = {(x, y) → (x∨y)}. Those logical relations are called implicative, because x∨y is equivalent to y ⇒ x. The #P-completeness of #SAT(S) was established by a chain of reductions in [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] and [START_REF]Hard enumeration problems in geometry and combinatorics[END_REF]. Here we will follow this chain of reductions to find a VNP-complete family associated to S-formulas. These two articles show consecutively that the problems of counting the independent sets, the independent sets in a bipartite graph, the antichains in partial ordered sets (posets), the ideals in posets, and finally satisfaction of implicative 2-clauses are #P-complete. We will start from the family (G ′ n ) such that IP(G ′ n ) = PER * n , whose existence is stated in Theorem 5, and follow the reductions for the counting problems.

We first transform the family (G ′ n ) into a family of bipartite graphs, without changing the independent set polynomials.

Lemma 3. There exists a family of bipartite graphs (G

′′ n ) such that IP(G ′′ n ) = PER *
n , the partial permanent of size n × n.

Proof. By Lemma 2, we know how to transform a graph G into a bipartite graph G ′ such that VCP(G ′ ) = (-1) e(G) IP(G) and IP(G ′ ) = (-1) e(G) VCP(G) where e(G) is the number of edges of G. By applying this transformation one more time to G ′ , we obtain a graph G ′′ such that:

IP(G ′′ ) = (-1) e(G ′ ) VCP(G ′ ) = (-1) e(G) IP(G)
Thus, the transformation of G into G ′′ consists of the replacement of each edge (u, v) in G by the subgraph represented in Figure 1.

G ′′ n ) such that IP(G ′′ n ) = PER * n .
In the following we will not only use the statement of this lemma: we will also use the structure of G ′′ n . More precisely, let us denote by V 1 and V 2 the partite sets of G ′′ n . We will use for instance the fact that in one of those two sets, say V 1 , all vertices have weight -1.

It is pointed out in [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] that, given a bipartite graph, one can construct naturally a partially ordered set. From the bipartite graph G ′′ n = (V 1 , V 2 , E), we define the partially ordered set (X n , ≤) with X n = V 1 ∪ V 2 , and given x and y in X n , x ≤ y if and only if x ∈ V 1 , y ∈ V 2 and (x, y) ∈ E. We see easily that ≤ is transitive and antisymmetric.

Next we recall the definition of an antichain.

Definition 9 (Antichain). An antichain A in a poset (X, ≤) is a subset of X such that for all pair (x, y) of distinct elements of A, x and y are incomparable.

We define the antichain polynomial of a (weighted) poset (X, ≤) as the polynomial:

AP(X) = A x∈A w(x)
where the sum runs over all antichains A of (X, ≤). Let us consider a bipartite graph G and its corresponding poset (X, ≤). A set S ⊆ X is an antichain in (X, ≤) if and only if it is independent in G. We thus have: AP(X) = IP(G). Thus, we can identify the families (AP(X n )) and (IP(G ′′ n )). We then define the notion of ideal in a poset.

Definition 10 (Ideal). An ideal I in a poset (X, ≤) is a subset of X such that for all x ∈ I, all y such that y ≤ x belong to I.

We can also define the ideal polynomial IPP(X) in a poset (X, ≤):

IPP(X) = I x∈I w(x)
where the sum runs over all ideals I of (X, ≤).

Given an ideal I in a poset (X, ≤), the maximal elements of I form an antichain A: since they are maximal in I, they cannot be compared. Conversely, given an antichain A, the set of elements x that are not greater than an element of A form an ideal. One can verify easily that those transformations are bijective and inverse of each other. We thus have a bijection between the ideals and the antichains of a given poset. This fact suffices to the authors of [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF], since the bijection shows that a poset has the same number of antichains and ideals; the counting problems are thus equivalent.

But for our weighted counting problems, since the ideals and the antichains have different weights, we cannot identify simply AP(X) and IPP(X) for any poset X.

We do not know how to reduce a family of antichain polynomials into ideal polynomials in general, but in the case of the family (AP(X n )), since the structure of the family (G ′′ n ) is particular, the problem is easier. We claim the following. Theorem 6. For all integers n, we have: AP(X n ) = IPP(X n ) The proof will be given at the end of this section.

Corollary 1. There exists a VNP-complete family of polynomials of the form (IPP(X n )).

To conclude, we note that the ideal polynomial in a poset (X, ≤) may be expressed as a polynomial associated to a S-formula. Namely, we associate to each x i ∈ X a boolean variable ε i with the intended meaning that x i belongs to an ideal when ε i is true. For every pair (x i , x j ) ∈ X such that x i ≤ x j , the condition x j ∈ I ⇒ x i ∈ I may be expressed by (ε j ⇒ ε i ), or (ε i ∨ ε j ). Thus, we have

IPP(X) = ε∈{0,1} |X| (i,j):xi≤xj ε i ∨ ε j X ε ,
and as a result:

Theorem 7. There exists a VNP-complete family of polynomials associated to a p-family of {OR 1 }-formulas.

To complete this section, we now provide the proof of Theorem 6. Let us fix an integer n. We recall that in the bipartite graph

G ′′ n = (V 1 , V 2 , E) constructed in Lemma 3, each vertex of V 1 has weight -1.
We also know that |V 1 | is even, since the elements of V 1 are added two by two in the transformation from G ′ n to G ′′ n . Fortunately, by modifying the correspondence between antichains and ideals, we can preserve the weights: we will construct in Lemma 4 a bijection from the antichains to the ideals of X n that preserves the weights, and thus we have:

AP(X n ) = IPP(X n ).
Lemma 4. There exists a bijection (different from the natural one considered previously) from the antichains to the ideals of X n , this one keeping the weights unchanged.

Proof. To an antichain A of X n , we associate the set I such that:

-A and I coincide on V 2 . -I ∩ V 1 is the complement of A ∩ V 1 in V 1 .
The map A → I is clearly injective, and one can verify that the image I is an ideal: given x ∈ X n and y ∈ I such that x ≤ y, we have that x ∈ V 1 and y ∈ V 2 . Therefore, y ∈ A, and x cannot belong to A as the elements of A are incomparable. Thus, x belong to I. Our map is thus a bijection from the antichains to the ideals of X n .

Since all the elements of V 1 have weight -1 and |V 1 | is even, the weights of I and A differ by a factor (-1) |V1| = 1.

Non affine constraints

In this section we consider the general case of a set S containing non affine constraints: Theorem 8. For every set S containing a non affine relation, there exists a VNP-complete family (under p-projection) of polynomials associated to S-formulas.

The proof of this result is an analogue of the proof of the #P-completeness of the corresponding counting problems given in [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF]. We will adapt this proof to our context. The authors use the notion of perfect and faithful implementation (definition 5.1 in [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF]): Definition 11. A conjunction of α boolean constraints {f 1 , . . . , f α } over a set of variables x = {x 1 , . . . , x n } and y = {y 1 , . . . , y n } is a perfect and faithful implementation of a boolean formula f (x), if and only if 1. for any assignment of values to x such that f (x) is true, there exists a unique assignment of values to y such that all the constraints f i (x, y) are satisfied. 2. for any assignment of values to x such that f (x) is false, no assignment of values to y can satisfy more than (α -1) constraints.

We refer to the set x as the function variables and to the set y as the auxiliary variables.

We say, that a set S of logical relations implements perfectly and faithfully a boolean formula f (x) if there is a S-formula that implements f (x) perfectly and faithfully. We also extend the definition to logical relations: a set S of logical relations implements perfectly and faithfully a logical relation f if S implements perfectly and faithfully every application of f to a set of variables x.

Let us denote F the unary relation F (x) = x. From [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF], lemma 5.30, we have:

Lemma 5. If a logical relation f is not affine, then {f, F} implements at least one of the three logical relations OR 0 , OR 1 or OR 2 perfectly and faithfully.

The following lemma, analogue to lemma 5.15 from [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF], shows that perfect and faithful implementation provide a mechanism to do projections from the polynomials associated to sets of logical relations. Lemma 6. Let S and S ′ be two sets of logical relations such that every relation of S can be perfectly and faithfully implemented by S ′ . Then every p-family of polynomials associated to a p-family of S-formulas is a projection of a p-family of polynomials associated to a p-family of S ′ -formulas.

Proof. Let (φ n ) be a p-family of S-formulas, and let us fix an integer n.

Let x = {x 1 , . . . , x p } be the set of variables of the formula φ n . This formula φ n is a conjunction of logical relations f i ∈ S applied on variables from {x 1 , . . . , x p }. If we replace each of those relations f i by a perfect and faithful implementation using constraints in S ′ , using for each f i a new set of auxiliary variables, we obtain a conjunction ψ n of logical relations from S ′ applied on variable set x ∪ y, where y = {y 1 , . . . , y q } is the union of the auxiliary variables sets added for each logical relation f i .

Since all implementations are perfect and faithful, every assignment to x that satisfies all constraints of φ n can be extended by a unique assignment to x ∪ y that satisfies all constraints of ψ n . Conversely, for an assignment to x that does not satisfy all constraints of φ n , no assignment to x ∪ y can extend the previous one and satisfy every constraint of ψ n .

Since ψ n is a conjunction of logical relations from S ′ applied on a set of variables x ∪ y, ψ n is a S ′ -formula. Furthermore, the number of constraints of ψ n is bounded by the product of the number of constraints of φ n and the maximum number of logical relations from S ′ needed to implement a logical relation from S -which does not depend on n. The size of ψ n is therefore polynomially linear in the size of φ n . We have:

P (φ n )(X 1 , . . . , X p ) = ε∈{0,1} p φ n (ε)X ε = ε∈{0,1} p ,y∈{0,1} q ψ n (ε, y)X ε = ε∈{0,1} p ,y∈{0,1} q ψ n (ε, y)X ε 1 y1 . . . 1 yq = P (ψ n )(X 1 , . . . , X p , 1, . . . , 1)
Finally, the family (P (φ n )) is a projection of the family (P (ψ n )), which is a p-family of polynomials associated to S ′ -formulas.

From the two previous lemmas, and from the VNP-completeness of families of polynomials associated to {OR 0 }-, {OR 1 }and {OR 2 }-formulas, we conclude that for every set of logical relations S such that S contains non affine relations, there exists a VNP-complete family of polynomials associated to S ∪ {F}formulas. To get rid of the logical relation {F}, the authors of [START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF] need to reinvestigate the expressiveness of a non affine relation, and distinguish various cases. For our polynomial problems, we can easily force a boolean variable to be set to false by giving to the associated polynomial variable the value 0. We can now give the proof of Theorem 8:

Proof. Let (φ n ) be a p-family of S ∪ {F}-formulas such that (P (φ n )) is VNPcomplete. The existence of such a family is ensured by lemmas 5 and 6.

Let us consider an integer n. φ n (x 1 , . . . , x n ) is a conjunction of logical relations from S applied to variables from x and and constraints of the form (x i = 0). We remark, that if φ n (x) contains the constraint (x i = 0), then the variable X i does not appear in the polynomial P (φ n )(X 1 , . . . , X n ): all the monomials containing the variable X i have null coefficients. If we suppress from the conjunction the constraint (x i = 0), and instead replace the corresponding variable X i by 0, we obtain exactly the same polynomial: the monomials such that X i appears in it have null coefficients; the others correspond to assignments such that x i = 0.

Let us denote ψ n the formula obtained by suppressing from φ n all the constraints of the form (x i = 0). Since P (φ n )(X 1 , . . . , X n ) = P (ψ n )(y 1 , . . . , y n ), where y i is 0 if the constraint (x i = 0) was inserted in φ n , and X i otherwise, (P (φ n )) is a p-projection of (P (ψ n )). Thus, the family (P (ψ n )) is VNP-complete.

Affine relations with at least three variables

Here we consider the case of a set S containing large affine constraints. We first establish the existence of a VNP-complete family of polynomials associated to a p-family of affine formulas, and then show how to reduce this family to each affine constraint with at least three variables. In this section, our VNP-completeness results are in the sense of c-reduction.

Let us consider the n × n permanent PER n (M ) of a matrix M = (M i,j ). It may be expressed as the polynomial associated to the formula accepting the n × n permutation matrices: PER n (M ) = ε φ n (ε)X ε This formula φ n expresses, that each row and each column of the matrix ε contains exactly one 1. Let us consider the formula ϕ n defined by:

ϕ n (ε) = n i=1 ε i1 ⊕ . . . ⊕ ε in = 1 ∧ n j=1 ε 1j ⊕ . . . ⊕ ε nj = 1
The formula ϕ n expresses, that each row and each column of ε contains an odd number of values 1. Thus, ϕ n accepts the permutation matrices, and other assignments that contain more values 1. We therefore remark, that the n × n permanent is exactly the homogeneous component of degree n of P (ϕ n ). But from Lemma 1, this implies a c-reduction from the permanent family to the p-family (P (ϕ n )). Thus: Lemma 7. The family (P (ϕ n )) is VNP-complete with respect to c-reductions.

Through c-reductions and p-projections, this suffices to establish the existence of VNP-complete families for affine formulas of at least three variables: Theorem 9. 1. There exists a VNP-complete family of polynomials associated to {x ⊕ y ⊕ z = 0}-formulas. 2. There exists a VNP-complete family of polynomials associated to {x⊕y ⊕z = 1}-formulas. 3. For every set S containing an affine formula with at least three variables, there exists a VNP-complete family of polynomials associated to S-formulas.

Proof. 1. Let us consider the formula ϕ n . This formula is a conjunction of affine relations with constant term 1: x 1 + . . . + x k = 1. Let ϕ ′ n be the formula obtained from ϕ n by adding a variable a and replacing such clauses by x 1 + . . . + x k + a = 0. In the polynomial associated to ϕ ′ n , the term of 3. Bipartite Vertex Cover: the restriction of vertex cover to bipartite graphs. 4. Bipartite Independent Set: the restriction of independent set to bipartite graphs. 5. Antichain: counting the number of antichains of a given poset. 6. Ideal: counting the number of ideals of a given poset. 7. Implicative 2-SAT: counting the number of satisfying assignments of a conjunction of implicative 2-clauses. 8. Positive 2-SAT: counting the number of satisfying assignments of a conjunction of positive 2-clauses. 9. Negative 2-SAT: counting the number of satisfying assignments of a conjunction of negative 2-clauses.

Remark 2. #P-completeness under oracle reductions is established in [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] for the first six problems, in [START_REF]Hard enumeration problems in geometry and combinatorics[END_REF] for the 7th problem and in [START_REF] Valiant | The complexity of enumeration and reliability problems[END_REF] for the last two. In Section 2, the last three problems are denoted #SAT(S) where S is respectively equal to {OR 1 }, {OR 0 } and {OR 2 }.

Proof. Provan and Ball establish in [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] the equivalence of Problems 1 and 2, 3 and 4, and 5 and 6; they produce many-one reductions from 1 to 8 and from 4 to 5, and Linial gives in [START_REF]Hard enumeration problems in geometry and combinatorics[END_REF] a many-one reduction from 6 to 7. Problems 8 and 9 are clearly equivalent. Therefore, to obtain #P-completeness under many-one reductions for all those problems, we just need to show the #P-completeness of Problem 1 and to produce a many-one reduction from Problem 1 to Problem 3 (replacing the oracle reduction from [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF]).

In order to prove the #P-completeness of Problem 1, we first establish a many-one reduction from the #P-complete problem of computing the permanent of {0, 1}-matrices (which is known to be #P-complete under many-one reductions [START_REF] Zankó | #P-completeness via many-one reductions[END_REF]) to the problem of computing the vertex cover polynomial of a weighted graph with weights in {0, 1, -1}. In [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF], Bürgisser attributes to Jerrum a projection from the permanent to the partial permanent, with the use of the constant -1. Applied to a {0, 1}-matrix, this gives a many-one reduction from the permanent on {0, 1}-matrices to the partial permanent on {0, 1, -1}matrices. By Theorem 5, the n×n partial permanent is equal to the independent set polynomial of the graph G ′ n ; the reduction is obviously polynomial. Moreover, by Lemma 2 this polynomial is the projection of the vertex cover polynomial of G n , with the use of the constant -1. The partial permanent on entries in {0, 1, -1} therefore reduces to the vertex cover polynomial on graphs with weights in {0, 1, -1}.

Let G be such a vertex weighted graph, with weights in {0, 1, -1}. A vertex cover of nonzero weight does not contain any vertex v of weight 0, and in order to cover the edges that are incident to v, it must contain all its neighbors. One can therefore remove v, and replace each edge from v to another vertex u by a self-loop (an edge from u to u). Thus, we obtain a graph G ′ with weights in {1, -1} such that VCP(G) = VCP(G ′ ).

To deal with the weights -1, we use a method similar to [START_REF] Valiant | The complexity of computing the permanent[END_REF]. Since VCP(G ′ ) is the value of a partial permanent on a {0, 1}-matrix, it is positive. We will construct an integer N and a graph H such that the number of vertex covers of H modulo N is equal to VCP(G ′ ). This will establish a reduction from the boolean permanent to counting vertex covers.

We choose N larger than the maximum value of the number of vertex covers of G ′ : N = 2 v(G ′ ) + 1 will suit our purposes. Now that we compute the number of vertex covers modulo N , we can replace each -1 weight in G ′ by the weight N -1 = 2 v(G ′ ) . But one can simulate such a weight on a vertex by adding to it v(G ′ ) leaves. Finally, we construct a many-one reduction from vertex cover to bipartite vertex cover. From Lemma 3, we have a projection from the vertex cover polynomial of a graph to the vertex cover of a bipartite graph, with the use of -1 weights. To eliminate these weights, we can follow the method used in our above proof of the #P-completeness of Problem 1. Indeed, since the leaves added to the graph preserve bipartiteness, we obtain a reduction from counting vertex covers in a general graph to counting vertex covers in a bipartite graph.

The proof of Creignou and Hermann's dichotomy theorem [START_REF] Creignou | Complexity of generalized satisfiability counting problems[END_REF][START_REF] Creignou | Complexity classification of boolean constraint satisfaction problems[END_REF] is based on manyone reductions from the last 3 problems of Theorem 10. We have just shown that these 3 problems are #P-complete under many-one reductions. As a result, we have the following corollary to Theorem 10.

Corollary 2. Theorem 1 still holds for #P-completeness under many-one reduction.

  polynomially bounded function of n. Those families constitute the complexity class VP. In Valiant's model, VNP is the analogue of the class NP (or perhaps more accurately, of #P).

Fig. 1 .

 1 Fig. 1. The transformation of Lemma 3

Fig. 2 .

 2 Fig. 2. Simulation of a weight 2 k

degree 1 in the variable associated to a is exactly the polynomial P (ϕ n ): when a is assigned to 1, the satisfying assignments of ϕ ′ n are equal to the satisfying assignments of ϕ n . Since this term of degree 1 can be recovered by polynomial interpolation of P (ϕ ′ n ), the family (P (ϕ n )) c-reduces to (P (ϕ ′ n )). ϕ ′ n is a conjunction of affine relations with constant term 0. The polynomial P (ϕ ′ n ) is the projection of the polynomial P (ψ n ), where the formula ψ n is obtained from ϕ ′ n by replacing each affine relation of the type x 1 ⊕. . .⊕x k = 0 by the conjunction of relations

where the a i are new variables. In fact, on sees easily, that for a given assignment of the x i satisfying ϕ ′ n , a single assignment of the a i gives a satisfying assignment of ψ n ; and that if the x i do not satisfy ϕ ′ n , no assignment of the a i works on. The polynomial P (ϕ ′ n ) is thus the polynomial obtained by replacing the variables associated to a i by the value 1 in P (ψ n ); the family (P (ϕ ′ n )) is a p-projection of (P (ψ n )). 2. The formula ψ n constructed above is a conjunction of relations of the type

x ⊕ y ⊕ z = 0. Let us construct a new formula ψ ′ n by introducing two new variables a and b and replacing each of such relations by the conjunction (x ⊕ y ⊕ a = 1) ∧ (a ⊕ z ⊕ b = 1). One sees easily, that P (ψ n ) is the projection of P (ψ ′ n ) obtained by setting the variables associated to a and b to 1 and 0 respectively. 3. Let us suppose, that S contains a relation of the type x 1 ⊕ . . . ⊕ x k = 0, with k ≥ 3. The polynomial P (ψ n ) is the projection of the polynomial associated to the S-formula obtained by replacing each relation x ⊕ y ⊕ z = 0 of ψ n by a relation x ⊕ y ⊕ z ⊕ a 1 ⊕ . . . ⊕ a k-3 = 0, and setting the variables associated to the a i to 0. Thus, the family (P (ψ n )) projects on a family of polynomials associated to S-formulas, which is therefore VNP-complete.

When S contains a relation with constant term 1, one projects the family (P (ψ ′ n )) similarly.

#P-completeness proofs

Up to now, we have studied vertex weighted graphs mostly from the point of view of algebraic complexity theory. Putting weights on edges, or on vertices, can also be useful as an intermediate step in #P-completeness proofs [START_REF] Valiant | The complexity of computing the permanent[END_REF][START_REF] Jerrum | Two-dimensional monomer-dimer systems are computationally intractable[END_REF]. Here we follow this method to obtain new #P-completeness results. Namely, we prove #P-completeness under many-one reductions for several problems which were only known to be #P-complete under oracle reductions.

Theorem 10. The following problems are #P-complete for many-one reductions.