Hervé Fournier

Guillaume Malod

Maud Szusterman

Sébastien Tavenas

Nonnegative rank measures and monotone algebraic branching programs

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.

1

This definition makes sense both in the usual case of commuting variables and in the case of noncommuting variables, over a free algebra, which we consider for the moment. For a noncommutative homogeneous polynomial P of degree d over variables in X, define matrices M i (P ), for 0 i d: the rows of M i (P ) are indexed by all possible monomials u over X of degree i, the columns are indexed by all possible monomials v over X of degree d -i, and the coefficient (u, v) of M i (P ) is the coefficient of the monomial uv in P . We call this matrix the i-th Nisan matrix of P . The characterization is then expressed by the following theorem.

 Fliess [11]). The size of a smallest ABP computing a noncommutative polynomial P is the sum of the ranks of its Nisan matrices, i.e., d i=0 rk M i (P ). More precisely, the value rk M i (P ) is the width of the i-th layer in a smallest ABP computing P . It is also the smallest possible width of the i-th layer in any ABP computing P .

Nisan also considers the case of monotone noncommutative computations. In this case Nisan does not obtain a characterization of monotone noncommutative complexity, but a sufficient tool for lower bounds, using the notion of nonnegative rank.

Definition 2. An ABP over an ordered field is called monotone if all coefficients of linear forms on the edges are nonnegative.

Definition 3. The nonnegative rank of a nonnegative matrix M , rk + M , is the smallest integer r such that M can be written as a sum of r rank-1 nonnegative matrices.

Introduction

Measures based on rank are one of the main tools to prove lower bounds in algebraic complexity theory. The complexity of first-order partial derivatives is the key ingredient for the best lower bound known for general circuits [START_REF] Baur | The complexity of partial derivatives[END_REF]. When looking at higher-order partial derivatives, one can consider their rank: the rank of partial derivatives, and some variants, have been intensively used to obtain lower bounds on restricted models [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF][START_REF] Raz | Multi-linear formulas for permanent and determinant are of super-polynomial size[END_REF][START_REF] Kumar | On the power of homogeneous depth 4 arithmetic circuits[END_REF]. Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] provided one of the earliest and cleanest examples of such a measure: when computing a polynomial over noncommuting variables by a so-called algebraic branching program, it gives an exact characterization of the complexity. 1To state this result more precisely, let us give here the definition of algebraic branching programs used in [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF]. Definition 1. An algebraic branching program (ABP) is a layered directed acyclic graph with a source s and a sink t. The first layer contains only the source s, the last layer contains only the sink t. Edges can only appear between vertices of successive layers and carry a weight which is a linear form of the variables. The weight of a path from s to t is the product of the weights of its edges. The (homogeneous) polynomial computed by the ABP is the sum of the weights of the paths from s to t. The width of a layer is the number of vertices on that layer.

Proposition 1 (Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF]). For a polynomial P with nonnegative coefficients, the value rk + M i (P ) is the smallest possible width of the i-th layer in a monotone ABP computing P . The size of a smallest monotone ABP computing P is therefore at least d i=0 rk + M i (P ).

Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] leaves the tightness of the inequality in Proposition 1 as an open question: does nonnegative rank also provide a characterization of monotone noncommutative complexity? One of our main results is a negative answer to this question (Theorem 6).

Before that, we consider in Section 2 a more general notion of monotone computation, which we call weakly monotone. Where monotonicity completely disallows cancellations, weak monotonicity allows them as long as any monomial appearing in the computation also appears in the end result. In other words, cancellations can be used to obtain the specific coefficients of a polynomial, but not to produce and then cancel out monomials outside the support of the polynomial. We strengthen Proposition 1 for weakly monotone noncommutative ABPs using a new rank measure. We then obtain a separation showing that weakly monotone noncommutative arithmetic formulas can be exponentially more powerful than monotone noncommutative ABPs. Thus weakly monotone lower bounds are stronger than monotone lower bounds.

In Section 3 we prove Theorem 6, answering Nisan's question, and more generally explore the link between nonnegative rank measures and the size of monotone noncommutative algebraic branching programs.

Finally, in Section 4 we focus on proving lower bounds for monotone commutative ABPs, building on ideas from the previous sections to develop new tools. Imposing monotonicity as a restriction on arithmetic computations to prove lower bounds has a long history [START_REF] Schnorr | A lower bound on the number of additions in monotone computations[END_REF][START_REF] Jerrum | Some exact complexity results for straight-line computations over semirings[END_REF], which often involves hard polynomials and yields exponential lower bounds. We focus here on the elementary symmetric polynomials e n,k .

While it is known that the elementary symmetric polynomials e n,k require monotone, or even homogeneous multilinear, formulas of size k Ω(k) n [START_REF] Hrubes | Homogeneous formulas and symmetric polynomials[END_REF], these can be efficiently computed: by arithmetic circuits of size O(n log k) [START_REF] Baur | The complexity of partial derivatives[END_REF]; by depth-3 arithmetic formulas of size O(n2 ), using interpolation; by monotone ABPs of size O(k(n -k)) by the following simple dynamic programming construction.

Apart from s and t, the ABP for e n,k has layers indexed by 1 i k -1; the i-th layer contains n -k + 1 vertices u i,1 , . . . , u i,n-k+1 ; vertex u i,j sends an edge of weight x i+ to vertex u i+1, for all 2 i k -2 and j n -k + 1; s sends an edge of weight x to u 1, and u k-1, sends an edge of weight

x k+ -1 + • • • + x n to t for 1 n -k + 1.
The monotone branching program obtained this way has size (k -1)(n -k + 1) + 2.

s t x 1 x 2 x n - k + 1 . . . x k + • • • + x n x n . . . x i+j x n + i -k + 1 x i + u i,j u i+1, . . . . . . 0 1 2 . . . i i + 1 . . . k -1 k 1 . . . j . . . n -k + 1
The existence of efficient computations imply that our lower bound techniques must be very precise. Surprisingly, there is also a very simple Ω(k(n -k + 1)) monotone lower bound in [START_REF] Jukna | On the optimality of Bellman-Ford-Moore shortest path algorithm[END_REF], but in a model where edge weights can only be a scalar or a scalar times a variable, not linear forms, which would only give a trivial lower bound in our setting. Our second main result is a similarly quadratic lower bound for our model, and for weakly monotone computations, at the cost of a significant increase in the complexity of the proof: we use a generalization of a combinatorial problem known as Galvin's problem. 2 Our lower bound can be equivalently stated as applying to homogeneous syntactically multilinear ABPs.

Let us add one remark on the definition of ABPs. This computation model is inherently homogeneous and we only consider nonzero homogeneous polynomials. We could also consider nonhomogeneous ABPs: these are directed acyclic graphs with a source and a sink, not necessarily layered, with arcs labelled with affine forms. In the noncommutative case, when computing a homogeneous polynomial, one can show that there is always a minimal-size ABP which is homogeneous and corresponds to Definition 1. We provide a proof sketch in Appendix A. This is also true in the commutative case for weakly monotone computations. Hence we shall consider only homogeneous branching programs.

Throughout the paper we use R in the case of an ordered field, but these results hold over any ordered field. When the field is not ordered we denote it by K and assume it is of characteristic 0.

A rank measure for weakly monotone computations 2.1 Weakly monotone computations

As defined before, the weight of a path is the product of the weights of its edges, i.e., a product of linear forms. Any of the monomials obtained when expanding completely this product, by choosing one term in each linear form, is said to be produced along the path. Definition 4. An ABP is called weakly monotone if any monomial produced along a path from the source to the sink has a nonzero coefficient in the polynomial computed by this ABP.

Note that this notion of monotonicity makes sense both in the commutative and noncommutative settings (Sections 2 and 3 deal with noncommutative computations, while we will use the commutative case in Section 4). We now define a new measure for weakly monotone computations. We will denote the support of a matrix M by supp M : it is the subset of the coordinates of M which correspond to nonzero entries. Definition 5. The weakly nonnegative rank of a matrix M , denoted by rk w M , is the smallest number r such that there exist M 1 , . . . , M r of rank 1 (with entries of any sign) such that supp M i ⊆ supp M for all i and r i=1 M i = M .

The usual nonnegative rank of a matrix already plays a role in several areas. For instance, the fact that the minimum number of facets of an extension of a polyhedron is equal to the nonnegative rank of its so-called slack matrix. In another direction, for a 0, 1-matrix M , log(rk M ) is a lower bound on the communication complexity of the associated problem. The log-rank conjecture stipulates that there is also a log O(1) (rk M ) upper bound. This conjecture is known to be equivalent to the fact that for any 0, 1-matrix M , log(rk + M ) = log O(1) (rk M ). The influence of communication complexity will be felt here too, as it can be seen from the use of the support of the matrix in the definition of weakly nonnegative rank. In fact, we will borrow a few more basic concepts from communication complexity. Definition 6. For a matrix M with rows indexed by a set I and columns indexed by a set J, a combinatorial rectangle is a subset of I × J of the form A × B, with A ⊆ I and B ⊆ J.

A cover of a matrix M is a set of combinatorial rectangles, included in the support of M and whose union is equal to the support of M . We define cov M as the smallest size of a cover of M . Proposition 2. We have cov M rk w M and rk M rk w M . For a nonnegative matrix M , rk w M rk + M .

Let us remark that we can have rk M < rk w M : this is the case for the following matrix [START_REF] Joel | Nonnegative ranks, decompositions, and factorizations of nonnegative matrices[END_REF], for which rk R = 3 and cov R = 4:

R =     1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1     .
The following proposition is the weak monotone version of Proposition 1.

Proposition 3. For a noncommutative polynomial P , the smallest size of the i-th layer of a weakly monotone ABP computing P is equal to rk w M i (P ). Hence the weakly monotone ABP size of P is greater or equal to i rk w M i (P ).

Proof. Let ∈ {1, . . . , d -1} and let M = M (P ), r = rk w M .

Consider a weakly monotone ABP computing P . Let s be the size of layer . Cutting the ABP at layer we get P = s i=1 L i R i . Let A i be the matrix of the polynomial L i R i . The matrices A 1 , . . . , A s satisfy all the conditions to show that rk w M s.

Conversely, write M (P ) = A 1 + . . . + A r where A i are rank 1 matrices with supp A i ⊆ supp M . Each A i can be interpreted as a product of two polynomials L i R i . It is easy to design a weakly monotone ABP with -layer of size r computing the polynomials L 1 , . . . , L r on the -th layer.

So we have proved that for any , the minimal size of the -th layer of a weakly monotone ABP computing P is equal to rk w M (P ). The last inequality follows from the fact that the minimal size of a weakly monotone ABP computing P is greater or equal to the sum of the minimal size of the different layers.

Separation of rank measures

We show now that we can have rk w M < rk + M . In the following J is the matrix with all entries equal to 1 and • is the infinite norm. Proposition 4. Let M be a nonnegative matrix. For ε > 0 small enough, N = M + εJ satisfies rk w N rk M + 1 and rk + N cov M .

Proof. We have rk N rk M + 1 because J is of rank 1, and rk N = rk w N since the support of N is full. Hence rk w N rk M + 1.

It remains to show the lower bound on r = rk

+ N . Write N = N 1 +. . .+N r with N i nonnegative matrix of rank 1. Write N i = a i b T i with a i and b i nonnegative satisfying a i = b i : this implies that a i , b i N 2 M
for ε small enough. Let ãi and bi be obtained from a i and b i by putting to 0 all entries smaller or equal to √ ε. Let Ñi = ãi bT i . The support of Ñi is a combinatorial rectangle. Moreover, supp Ñi ⊆ supp M since any nonzero entry of Ñi is greater than ε.

Let us show that supp M ⊆ i supp Ñi . Let Ñ = Ñ1 + . . . + Ñr . For any entry (x, y), we have

|N i (x, y) -Ñi (x, y)| 2 √ ε M so N -Ñ 2r ε M . This shows that M -Ñ M -N + N -Ñ ε + 2r ε M .
Hence M -Ñ is smaller than the smallest nonzero entry of M for ε small enough. This proves that supp M is covered by r i=1 supp Ñi .

We want to apply the previous proposition to a matrix with a large gap between rank and covering bound. Such examples are known: the n × n matrix defined by M i,j = (a i -a j ) 2 for distinct reals a 1 , . . . , a n has rank 3 but cov M = Ω(log n) [START_REF] Beasley | Real rank versus nonnegative rank[END_REF]; the slack matrix of a generic polygon also exhibits such a gap [START_REF] Fiorini | Extended formulations for polygons[END_REF] (note that this matrix is not explicit).

We will build on a third construction to obtain an exponential separation between weakly monotone formulas and monotone ABPs in the noncommutative setting. Let U n be the matrix whose rows and columns are indexed by {0, 1} n and which is defined by

U n (u, v) = ( u, v -1) 2 ,
where the scalar product is over R. Theorem 2 ([7], see also [START_REF] Fiorini | Exponential lower bounds for polytopes in combinatorial optimization[END_REF]). It holds that rk

U n = O(n 2 ) and cov U n = 2 Ω(n) .
Using Proposition 4, this theorem gives a matrix with an exponential gap between weakly nonnegative rank and nonnegative rank.

Proposition 5. For ε > 0 small enough, rk w (U n + εJ) = O(n 2 ) and rk + (U n + εJ) = 2 Ω(n) .

Separating noncommutative monotone and weakly monotone classes

Let us define a noncommutative polynomial over the variables {x 0 , x 1 }. For u ∈ {0, 1} n , let x u = x u 1 . . . x un and define P = u,v∈{0,1} n ( u, v -1) 2 x u x v . This polynomial was used in [START_REF] Hrubes | Formulas are exponentially stronger than monotone circuits in non-commutative setting[END_REF] to obtain the following separation.

Theorem 3 ([14]

). The noncommutative polynomial P defined above has formula size O(n 3 ) but monotone circuit size 2 Ω(n) .

As a consequence, we get a separation illustrating the difference between monotone and weakly monotone computations. Definition 7. A formula is called weakly monotone if any monomial produced by the computation (before any possible cancellations) has a nonzero coefficient in the computed polynomial. More formally, a formula is weakly monotone if any monomial produced by a parse tree is present in the computed polynomial.

Theorem 4. For ε > 0 small enough, the noncommutative polynomial P + ε(x 0 + x 1 ) 2n has weakly monotone formula size O(n 3 ) but requires monotone ABP size 2 Ω(n) .

Proof. Let Q = P + ε(x 0 + x 1 ) 2n for some ε > 0 small enough. The polynomial P has formula size O(n 3 ) by the upper bound from Theorem 3. The polynomial ε(x 0 + x 1 ) 2n has formula size O(n). Since the support of Q is full, the formula obtained for Q by summing these two formulas is weakly monotone.

The middle Nisan matrix of

Q is M n (Q) = U n + εJ so rk + M n (Q) = 2 Ω(n) by Proposition 5. It follows from Proposition 1 that Q has monotone ABP size 2 Ω(n) .

Monotone noncommutative complexity vs monotone rank measures

This section is devoted to the comparison between nonnegative rank measures and the size of monotone noncommutative algebraic branching programs, in particular Nisan's question on the tightness of the lower bound for monotone noncommutative ABPs. Let us start by a particular case where the inequality is tight. We work over a field K of characteristic zero. We say a vector v is a weakly monotone linear combination of u 1 , . . . , u p if there exist scalars λ i for 1 i p such that no cancellations occur:

v = i∈[1,p] λ i u i with supp(v) = i∈[1,p] λ i =0 supp(u i ).

In the case of ranks at most 2

In the case where each Nisan matrix is of rank at most 2, we prove that an algebraic branching program of minimal size can be chosen to be monotone (or weakly monotone). Since rk M 2 implies rk M = rk w M = rk + M , it means that the measures i rk + M i (P ) and i rk w M i (P ) do characterize the monotone and weakly monotone ABP size in this case.

Lemma 1. If a homogeneous noncommutative polynomial P of degree d with nonnegative coefficients satisfies rk M i (P ) = 2 for all 0 < i < d, then there exists a monotone ABP of width 2 computing P . Hence the minimal size of a monotone ABP computing P is equal to d i=0 rk + M i (P ).

Proof. For any i ∈ {1, . . . , d}, the matrix M i (P ) is a matrix of size k × , of nonnegative rank 2 and so also of rank 2.

Claim 1. There exist U i and V i two columns of M i (P ) which nonnegatively generate all columns of M i (P ).

Proof. Up to removing the all-zeros columns, we can assume all columns of M i (P ) are nonzero. The column vectors W 1 , . . . , W of M i (P ) lie in a 2-dimensional vector space P of R k . Let us consider the vectors W 1 W 1 1 , . . . , W W 1 . They are still in P, but, as they are nonnegative, they are also in the affine hyperplane

H def = {X ∈ R k | X i = 1}
. The intersection of P and H is an affine line, so we can find U i and V i among the (W j ) 1 j such that for all j,

W j W j is in the closed affine segment U i U i , V i V i .
As U i and V i are nonnegative, they nonnegatively generate all columns of M i (P ).

For i ∈ {1, . . . , d -1}, let Q (i) 1 and Q (i)
2 be the polynomials corresponding to the columns U i and V i . Let X be the set of variables of P , then

P (X) = m deg d-i-1 monomial P (i+1) m (X) • m = m deg d-i-1 monomial v∈X P (i) vm (X) • vm.
So, each column of M i+1 (P ) can be obtained by

P (i+1) m (X) = v∈X P (i) vm (X) • v, and so by a monotone combination v∈X (α v Q (i) 1 + β v Q (i) 2 ) • v = Q (i) 1 v∈X α v v + Q (i) 2 v∈X α v v . This designs a monotone ABP of width 2 computing Q (1) i and Q (2) i on layer i for all i.
In order to prove the analog of Lemma 1 in the weakly monotone case, we will use several times the following very simple observation. Proposition 6. Let E i be the i-th coordinate hyperplane of K n . and E = i∈I E i for I ⊆ [n]. Let v ∈ E, and u 1 , . . . , u p ∈ K n . Assume v = p j=1 λ j u j is a weakly monotone linear combination. Then for all j such that λ j = 0, we have u j ∈ E.

In particular, if v = 0 is a weakly monotone linear combination v = j λ j u j , then there exists j 0 such that λ j 0 = 0 and u j 0 ∈ E \ {0}.

Proof. For the first point, if λ j = 0, then, by definition, supp(u j ) ⊆ supp(v), which implies that u j ∈ E. The second point follows directly by noticing that if v = 0, then at least one of the λ j has to be nonzero.

Lemma 2. If P is a homogeneous noncommutative polynomial of degree d such that rk M i (P ) = 2 for all 0 < i < d, there exists a weakly monotone ABP of width 2 computing P . Hence the minimal size of a weakly monotone ABP computing P is equal to d i=0 rk w M i (P ).

Proof. For any i ∈ {1, . . . , d}, the matrix M i (P ) is a matrix of size k × , of nonnegative rank 2 and so also of rank 2.

Claim 2. There exist U i and V i two columns of M i (P ) which nonnegatively generate all columns of M i (P ).

Proof. Up to removing the all-zeros columns, we can assume all columns of M i (P ) are nonzero.

The column vectors W 1 , . . . , W of M i (P ) lie in a 2-dimensional vector space P of R k . Let us consider the vectors W 1 W 1 1 , . . . , W W 1 . They are still in P, but, as they are nonnegative, they are also in the affine hyperplane

H def = {X ∈ R k | X i = 1}
. The intersection of P and H is an affine line, so we can find U i and V i among the (W j ) 1 j such that for all j,

W j W j is in the closed affine segment U i U i , V i V i .
As U i and V i are nonnegative, they nonnegatively generate all columns of M i (P ).

For i ∈ {1, . . . , d -1}, let Q (i) 1 and Q (i)
2 be the polynomials corresponding to the columns U i and V i . Let X be the set of variables of P , then

P (X) = m deg d-i-1 monomial P (i+1) m (X) • m = m deg d-i-1 monomial v∈X P (i) vm (X) • vm.
So, each column of M i+1 (P ) can be obtained by

P (i+1) m (X) = v∈X P (i)
vm (X) • v, and so by a monotone combination v∈X (α v Q

(i) 1 + β v Q (i) 2 ) • v = Q (i) 1 v∈X α v v + Q (i) 2 v∈X α v v . This designs a monotone ABP of width 2 computing Q (1) i and Q (2) i on layer i for all i.
Then we can easily conclude: Theorem 5. Let P be a noncommutative polynomial, homogeneous of degree d > 0, such that rk M i (P ) 2 for all i. Then the minimal size of a weakly monotone ABP computing P is equal to d i=0 rk w M i (P ). Moreover, if P is nonnegative, the minimal size of a monotone ABP computing P is equal to d i=0 rk + M i (P ).

Proof. Assume P is nonnegative homogeneous of degree d > 0. We prove the second point by induction on d. If d = 1 the polynomial P is linear with nonnegative coefficients, P = 0, and thus rk + M 0 (P ) + rk + M 1 (P ) = 2, which is the size of a minimal monotone ABP. Assume now that d > 1. If rk M i (P ) = 2 for all 0 < i < d, then the minimal size of a monotone ABP computing P is equal to d i=0 rk + M i (P ) by Lemma 1. Otherwise, there exists 0 < i < d such that rk + M i (P ) = 1. It means that P = QR with Q and R homogeneous of degree i and d -i. By induction the minimal size of a monotone ABP computing Q is equal to d i=0 rk + M i (Q) and similarly for R. The conclusion follows easily for P .

The proof of the first point is analogous, using Lemma 2.

Separation of monotone rank measure and ABP size

We now prove a separation between the sum-of-ranks measure and the minimal noncommutative ABP size, both in the monotone and in the weakly monotone cases.

If X = X 1 . . . X d is a partition of the set of variables, a noncommutative polynomial f is called ordered over the family X 1 , . . . , X d if it is homogeneous of degree d and if each monomial m from f is of the form v 1 v 2 • • • v d , where v i ∈ X i for each i.
M i (H) = rk w M i (H) = rk M i (H) = 3 for i ∈ {1, 2}, so that 3 i=0 rk + M i (H) = 3 i=0 rk w M i (H) = 8
, but the minimal size of a monotone ABP and of a weakly monotone ABP is 9.

Proof. Define the vectors

A =     1 0 0 1     , B =     0 1 1 0     , C =     1 0 1 0     , D =     0 1 0 1    
(they correspond to the columns of the matrix R of Section 2). Then, rk(A, B, C, D) = 3 and rk w (A, B, C, D) = 4, since cov(A, B, C, D) = 4. Define the matrices M ∈ R 4×8 0 and N ∈ R 8×4 0 :

M def = A B A+C 2 B+C 2 C C C+D 2 C+D 2
and

N def = A B A+C 2 B+C 2 C C C+D 2 C+D 2
.

As C+D Hence, rk + M = rk + N = 3. This shows that rk w M = rk w N = 3.

Let X = {x 1 , x 2 , x 3 , x 4 }, Y = {y 1 , y 2 } and Z = {z 1 , z 2 , z 3 , z 4 }. We consider the ordered polynomial H ∈ R 0 [X, Y, Z]: H def = x 1 y 1 z 1 + x 4 y 1 z 1 + x 2 y 1 z 2 + x 3 y 1 z 2 + x 1 y 1 z 3 + 1 2 x 3 y 1 z 3 + 1 2 x 4 y 1 z 3 + 1 2 x 1 y 1 z 4 + 1 2 x 2 y 1 z 4 + x 3 y 1 z 4 + x 1 y 2 z 1 + x 3 y 2 z 1 + x 1 y 2 z 2 + x 3 y 2 z 2 + 1 2 x 1 y 2 z 3 + 1 2 x 2 y 2 z 3 + 1 2 x 3 y 2 z 3 + 1 2 x 4 y 2 z 3 + 1 2 x 1 y 2 z 4 + 1 2 x 2 y 2 z 4 + 1 2 x 3 y 2 z 4 + 1 2 x 4 y 2 z 4 .
One can verify than the middle Nisan matrices of H are M 1 (H) = M and M 2 (H) = N . Assume that there exists a weakly monotone noncommutative homogeneous ABP of size 8 = rk w M i (H) computing H. It means that the ABP has exactly rk w M i nodes at layer i for 0 i 3. In particular, such an ABP has three nodes at layer 1, each one computing a polynomial

P (1) 1 (X), P (1)

(X) and P

(1) 3 (X) and has also three nodes at layer 2 which compute the polynomials

P (2) 1 (X, Y ), P (2)
2 (X, Y ) and P where λ s = 0 if and only if we can read the monomial y j z k between the node corresponding to P (1) s (X) and the output of the ABP. It remains to show that this linear combination C = 3 s=1 λ s P

(1) s is weakly monotone. Assume this is not, it means for some i the coefficient of x i is 0 in C but there exists s such that λ s = 0 and the coefficient of x i in P (1) s is different to 0. It means that the coefficient of x i y j z k is 0 in H but there is a path in the ABP with nonzero coefficient for this monomial (otherwise the scalar in front of P [START_REF] Noga Alon | Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits[END_REF] s (X) would be 0). It contradicts the fact that the ABP is weakly monotone. Proof. As rk(A, B, C) = 3, we can consider the vector-space F generated by {A, B, C}, namely

F = {T ∈ R 4 | t 1 + t 2 -t 3 -t 4 = 0}.
So the vectors U , V and W must form a basis of F and so, have to lie in F. For 1 i 4, let E i be the i-th coordinate hyperplane of R 4 .

Notice that RA = F ∩E 2 ∩E 3 . By Proposition 6, since A is a weakly monotone linear combination of U, V, W , (at least) one of the vectors {U, V, W } must belong to E 2 ∩ E 3 . Since this vector lies also in F, it is in RA.

In the same way, since RB = F ∩ E 1 ∩ E 4 and RC = F ∩ E 2 ∩ E 4 , one vector of B must belong to RB and one must belong to RC.

Since RA, RB, RC are 3 distinct one-dimensional linear subspaces, each one of these spaces has to contain one of the vectors U, V, W .

∈ R A C , R ∈ R B C , S ∈ R C D .
Proof. Let us define B = {Q, R, S}. We can easily see that the columns of N lie in the vector space given by the intersection of the three hyperplanes

F 1 = {T ∈ R 8 | t 1 + t 2 = t 3 + t 4 }, F 2 = {T ∈ R 8 | t 5 + t 6 = t 7 + t 8 }, F 3 =    T ∈ R 8 | 4 i=1 t i = 8 j=5 t j    . As rk(Q, R, S) = rk N , the vectors Q, R and S are in F 1 ∩ F 2 ∩ F 3 .
For 1 i 8, we denote by E i the i-th coordinate hyperplane of R 8 . Looking at the two first columns of N we can notice that

R A C = F 1 ∩ F 2 ∩ F 3 ∩ E 2 ∩ E 3 ∩ E 6 ∩ E 8 and R B C = F 1 ∩ F 2 ∩ F 3 ∩ E 1 ∩ E 4 ∩ E 6 ∩ E 8
are two distinct one-dimensional spaces of R 8 . By Proposition 6, there is at least one vector of B (let us suppose this is Q) such that Q = q A C and at least one other vector of B (assume this is R) such that R = r B C . Finally we need to identify the last vector S. For that, we decompose S = S 1 S 2 where S 1 is the projection of S on its first four coordinates and S 2 the projection on the last four. Now, we know that B weakly monotonically generates the last two columns of N . So there exist a 1 , a 2 , a 3 , b 1 , b 2 , b 3 ∈ R such that:

a 1 q A C + a 2 r B C + a 3 S 1 S 2 = A+C 2 C+D 2 and b 1 q A C + b 2 r B C + b 3 S 1 S 2 = B+C 2 C+D 2
.

By Proposition 6, as

A+C 2 C+D 2 ∈ E 2 and B+C 2 C+D 2
∈ E 4 , we know that a 2 = b 1 = 0. Moreover, as A and (A + C) are not colinear, it means that S 1 belongs to the plane vect(A, A + C) (by the way, this space is inside E 2 ). Similarly, S 1 ∈ vect(B, B + C). As B / ∈ E 2 , these two planes are distinct, so the intersection is of dimension at most 1. Moreover, vect(C) is in the intersection, and so, S 1 ∈ vect(C). There exists s = 0 such that S 1 = sC. As a 1 qA + a 3 sC = A+C 2 , it implies that a 1 q = a 3 s = 1 2 . Then, we have

C 2 + S 2 2s = C+D 2 , i.e., S 2 = sD.
Consequently, by Claim 3 and Claim 5, one node at layer 2 computes the polynomial whose matrix is s C D (with s = 0). By instantiating y 1 to 0 and y 2 to 1/s, this node computes exactly the polynomial corresponding to D as a weakly monotone linear combination of the nodes at layer 1. By Claim 4, the nodes at layer 1 are polynomials associated to A, B and C (up to scalar multiplication). This would imply that rk w (A, B, C, D) = 3, which is false. Hence, there does not exist a weakly monotone ABP of size 8.

To complete the proof, we show there is a monotone ABP of size 9 computing H. There are two natural monotone ABPs of size 9, let us describe one of them. One can compute the four polynomials associated to A, B, C and D at the first layer. It gives the following monotone ABP of size 9:

H = 1 2 x 1 + x 4 x 2 + x 3 x 1 + x 3 x 2 + x 4     y 1 0 0 0 y 1 0 y 2 y 2 y 1 0 0 y 2       2z 1 + z 3 2z 2 + z 4 z 3 + z 4   .
Theorem 6. There exists a noncommutative homogeneous degree 3 polynomial P over 4 variables such that rk + M i (P ) = rk w M i (P ) = rk M i (P ) = 3 for i ∈ {1, 2}, so that

3 i=0 rk + M i (P ) = 3
i=0 rk w M i (P ) = 8, but the minimal size of a weakly monotone or monotone ABP computing P is 9.

Proof. Consider the noncommutative polynomial P = H(x 1 , x 2 , x 3 , x 4 , x 1 , x 2 , x 1 , x 2 , x 3 , x 4 ). As H is ordered, and as the previous substitution follows this order, it is injective over the set of monomials which appear in H, that is to say, if m 1 and m 2 are two monomials from H which give the same monomial in P , then m 1 = m 2 . It directly implies that the substitution establishes a bijection between the set of monomials which appear in H and the ones which appear in P . We will say that this substitution is faithful.

Any ABP A which computes the polynomial H can be transformed into an ABP B which computes P with layers of same size by a direct substitution of the variables. Moreover, if A is monotone, then B is immediately monotone. Then, if A is weakly monotone, the faithfulness property implies that B is also weakly monotone.

In the other direction, if in a weakly monotone noncommutative ABP A computing P we replace the variables x 1 and x 2 in the second layer by y 1 and y 2 and the variables x 1 , x 2 , x 3 and x 4 in the third layer by z 1 , z 2 , z 3 and z 4 , then we get a new ABP B which computes the polynomial H(x 1 , x 2 , x 3 , x 4 , y 1 , y 2 , z 1 , z 2 , z 3 , z 4 ). The fact that this transformation preserves the monotonicity is still immediate. The faithfulness property implies it also preserves the weak monotonicity. So, the theorem follows from Lemma 3.

Corollary 1 (Gap increasing with the degree and the number of variables). Let P be the polynomial defined in Theorem 6. Let m, n 1. Let X 1 , . . . , X n be n sets of distinct variables, with each set of size 4. Let Q(X 1 , . . . , X n ) = n j=1 P m (X j ). This is a polynomial of degree 3m in 4n variables such that 3m i=0 rk + M i (Q) = 3m i=0 rk w M i (Q) = 7mn -n + 2 but the minimal size of a monotone or weakly monotone ABP for it is equal to 8mn -n + 2.

Proof. Let us first consider the case n = 1. From Theorem 6, one can easily checked that rk M i (P m (X 1 )) = 1 for i multiple of 3 and rk M i (P m (X 1 )) = rk + M i (P m (X 1 )) = 3 otherwise, and that a minimal (weakly) monotone ABP computing P m (X 1 ) has 8m + 1 nodes.

Consider a weakly monotone ABP for Q. Assume there is an internal node α and two distinct indices k and k such that α depends on at least one variable of X k and one variable of X k . Consequently, one path of the ABP produces a monomial which contains both a variable in X k and a variable not in X k . Since Q = n j=1 P m (X j ), a given monomial in Q can only contain variables coming from a single X k . The above statement thus contradicts the fact that the ABP is weakly monotone. Hence, we can partition the internal nodes of the ABP into n parts, each one related to one variable set X j . As mentioned earlier, a minimal weakly monotone ABP for P m (X j ) has 8m -1 internal nodes. The minimal size of a weakly monotone ABP is therefore 8mn -n + 2. The same is true of a monotone ABP computing Q.

Let us compute the sum of ranks for Q. If 0 < i < 3m, the i-th Nisan matrix of Q is blockdiagonal with n blocks, where the j-th block corresponds to the i-th Nisan matrix of P m (X j ). As the nonnegative rank of a block-diagonal matrix is equal to the the sum of the nonnegative ranks of its blocks, rk M i (Q) = rk + M i (Q) = n for i ∈ {3, 6, . . . , 3m -3} and rk M i (Q) = rk + M i (Q) = 3n for i ≡ 1, 2 mod 3. Summing over the different layers we get that the sum-of-ranks measure for Q, both for usual rank and nonnegative rank, and thus for weakly nonnegative rank, is equal to 7mn -n + 2.

An upper bound on the size of a monotone ABP computing a homogeneous degree d polynomial P is obtained by summing, for each ∈ {0, . . . , d} the minimal number of rows extracted from M (P ) whose cone contains all other columns of M (P ). The example above shows that this is not a characterization of monotone size: for the polynomial H built in Lemma 3, it is needed to extract 4 rows in both M 1 (H) and M 2 (H). The same remark applies in the weakly monotone setting (about the minimum number of extracted rows which weakly monotonically generate all the rows). For a matrix M whose rows and columns are indexed by noncommutative monomials, we define M com the matrix obtained by summing rows and columns indexed by the same commutative monomial.

m = m 1 m 2 , there is no noncommutative monomial m = m 1 m 2 in Q such that m i computes commutatively m i for i ∈ {1, 2}.
Together, these two statements prove the proposition.

For a homogeneous degree d polynomial P and ∈ {0, . . . , d} consider the support matrix S (P ) indexed by degree-commutative monomials on the rows, degree-(d-) commutative monomials on the column, such that S (P ) m 1 ,m 2 = 1 if the coefficient of m 1 m 2 in P is nonzero and S (P ) m 1 ,m 2 = 0 otherwise. Definition 8. For M, S two matrices of the same size we define rk w (M, S) to be the smallest r such that there exist rank 1 matrices M 1 , . . . , M r such that supp(M i ) ⊆ supp(S) and M = r i=1 M i .

Notice that rk w M , defined in Section 2, is nothing but rk w (M, M ). Proof. Let ∈ {1, . . . , d -1}. Consider an ABP computing P with minimal number of nodes at level : say it is w. Cutting this ABP at layer gives a decomposition P = w i=1 Q i R i . For i ∈ {1, . . . , w} let M i be the matrix of Q i R i . All matrices M i are of rank 1 and we have w i=1 M i ∈ M (P ). If the ABP is monotone, the matrices M i are nonnegative and we get min{rk + M | M ∈ M (P ), M 0} w. If the ABP is weakly monotone, we have supp(M i ) ⊆ supp(S (P )). Hence min{rk w (M, S (P )) | M ∈ M (P )} w.

For two same-sized matrices M, S, let cov(M, S) be the smallest number of combinatorial rectangles included in the support of S and whose union covers the support of M . Proposition 8. cov(M, S) rk w (M, S).

Proof. Let r = rk w (M, S) and write M = r i=1 M i with M i of rank 1, supp(M i ) ⊆ supp(S). We have supp(M ) ⊆ r i=1 supp(M i ): this shows that cov(M, S) r.

Application to the elementary symmetric polynomials

For n positive integer we write [n] = {1, . . . , n}. For 0 k n, let e n,k be the elementary symmetric polynomial of degree k over the variables x 1 , . . . , x n : e n,k = I∈( [n] k ) i∈I x i . Notice that S j (e n,k ) is exactly the disjointness matrix D n,j,k-j with rows indexed by elements of [n] j and columns indexed by elements of [n] k-j , and whose entry in row A and column B is 1 if A ∩ B = ∅ and 0 otherwise.

To get lower bounds for e n,k using Corollary 2 we need to show that, for enough values of j and for any M ∈ M j (e n,k ), cov(M, D n,j,k-j ) is large. Proposition 9. For n, j, k fixed, assume cov(M, D n,j,k-j ) m for some M ∈ M j (e n,k ). Then there exists A 1 , . . . , A m ⊆ [n] with the following property: For all B ∈

[n] k , there is i ∈ {1, . . . , m} such that |A i ∩ B| = j.

(1)

Proof. Let M ∈ M j (e n,k ). Assume U 1 × V 1 , . . . , U m × V m is a set of combinatorial rectangles from [n] j × [n] k-j included in the support of D n,j,k-j and covering supp M . Notice that such a combinatorial rectangle U × V is included in the support of D n,j,k-j if and only if u∈U u ∩ v∈V v = ∅. For i ∈ {1, . . . , m}, let A i = u∈U i u. From the previous remark the set of combinatorial rectangles R 1 , . . . , R m defined by

R i = A i j × [n]\A i k-j
is included in the support of D n,j,k-j and covers supp M .

Let us show that the family {A 1 , . . . , A m } satisfies Equation [START_REF] Noga Alon | Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits[END_REF]. Let B ∈ [n] k . The monomial i∈B x i appears in e n,k so one non-zero entry of M is of the form (I, J) with I ∈ [n] j , J ∈ [n] k-j and I ∪ J = B. Therefore (I, J) ∈ R i for some i ∈ {1, . . . , m}, i.e. |A i ∩ B| = |I| = j.

We will now relate our lower bound endeavor to a combinatorial question known as Galvin's problem: for n a multiple of 4, prove a lower bound on the size m of a family {A 1 , . . . , A m } ⊆ [n] n/2 such that for any B ∈ [n] n/2 , there exists i such that |A i ∩ B| = n/4. Proving a lower bound on a family {A 1 , . . . , A m } satisfying Equation (1) for the parameters k = n/2 and j = n/4 is a generalization of Galvin's problem because the sets A i can be of arbitrary size, instead of n/2 in the original problem.

Otherwise, we have k > n/2. It means that k 2k -n > 0. Then a weakly monotone ABP of size s for e n,k gives a weakly monotone ABP of size at most s for e 2n-2k,n-k by Lemma 7, choosing the parameters p = k and q = 2k -n. The lower bound s = Ω((n -k) 2 ) follows from Lemma 5.

The lower bound is obtained for n odd by noticing that e 2 n/2 ,k can be reduced to e n,k by putting one variable to 0. Moreover, e n,k reduces to e n-1,k-1 by Lemma 7. So the lower bound holds for n and k of any parity.

This lower bound also holds in the homogeneous syntactically multilinear model: indeed, any such ABP computing e n,k is weakly monotone because e n,k has all degree k monomials in its support.

A From nonhomogeneous to homogeneous ABPs

The nonhomogeneous model described in the introduction can be shown to be equivalent (without changing the size) to one where the vertices are not layered, but still with linear forms on the edges except one possible additional scalar edge from the source to the sink.

In the noncommutative case, this second model can be seen as a special case of linear representations of word series as in [START_REF] Fliess | Matrices de Hankel[END_REF], see also [START_REF] Berstel | Rational Series and Their Languages[END_REF]. The basic result there is that the minimal size of a linear representation is the rank of the so-called Hankel matrix. We can take from the proof of this theorem the construction of a minimal-size linear representation from the Hankel matrix. In the case of a noncommutative homogeneous polynomial, this linear representation will be exactly an ABP in the sense of Definition 1.

In the weakly monotone case, when computing a homogeneous polynomial, each node has to compute a homogeneous polynomial. So this second model can be layered to conform to Definition 1. Note that there cannot be a scalar edge from source to sink in this case.

Lemma 3 .

 3 There exists a noncommutative ordered degree 3 polynomial H with nonnegative coefficients in R over the set of variables (X, Y, Z) with |X| = 4, |Y | = 2, |Z| = 4, such that rk +

2 = A+B 2 ,

 22 the columns of M are monotone linear combinations of A, B and C. Moreover, the columns of N are monotone linear combinations of

Claim 3 .

 3 , Y ). The goal is to show that these triplets of polynomials are precisely defined and there is no way to link them together in a weakly monotone ABP. By definition of the Nisan matrix, we can see columns of M as polynomials in R[X] and columns of N as polynomials in R[X, Y ]. The polynomials P the columns of M and the polynomials P

  the columns of N .Proof. Let us show the result at layer 1, the case of layer 2 is symmetrical. Consider a column C of the first Nisan matrix: say it corresponds to the coefficient of y j z k in H. If we instantiate the variables y j and z k to 1 and the other variables from Y ∪ Z to 0 in the ABP, we get C as a linear combination of columns representing P

Claim 4 .

 4 If three vectors U , V and W weakly monotonically generate the family (A, B, C) then (up-to permuting the names of U , V and W ), U ∈ RA,V ∈ RB and W ∈ RC.

Claim 5 .

 5 If three vectors Q, R and S weakly monotonically generate the columns of N then, up to permuting the names of Q, R and S, Q

4

  Lower bounds for monotone commutative ABPs 4.1 Lower bound tools for monotone and weakly monotone ABPs Consider a homogeneous degree d commutative polynomial P . For ∈ {0, . . . , d}, we define the set M (P ) of matrices, whose rows are indexed by commutative degree-monomials and whose columns indexed by degree-(d -) commutative monomials. A matrix M belongs to M (P ) if: (a) For any degree d commutative monomial m such that m does not appear in P and any (m 1 , m 2 ) satisfying m = m 1 m 2 , m 1 of degree and m 2 of degree d -, we have M m 1 ,m 2 = 0; (b) For any other degree d commutative monomial m, m 1 m 2 =m M m 1 ,m 2 is equal to the coefficient of m in P .

Theorem 7 .

 7 The size of a monotone ABP computing a homogeneous commutative polynomial P of degree d is at least d =0 min{rk + M | M ∈ M (P ), M 0}. If the ABP is weakly monotone the bound becomes d =0 min{rk w (M, S (P )) | M ∈ M (P )}.

Corollary 2 .

 2 Any weakly monotone ABP computing P has size greater or equal to d =0 min{cov(M, S (P )) | M ∈ M (P )}.

It was noticed in[START_REF] Fijalkow | Lower bounds for arithmetic circuits via the hankel matrix[END_REF] (see also[START_REF] Klivans | Learning restricted models of arithmetic circuits[END_REF]) that this result actually follows from an older characterization for word series[START_REF] Fliess | Matrices de Hankel[END_REF]. This characterization was also extended to tree series in[START_REF] Bozapalidis | The rank of a formal tree power series[END_REF], which can be applied to circuits.

A different generalization of this combinatorial problem was recently used to prove almost quadratic lower bounds on the size of syntactically multilinear circuits[START_REF] Noga Alon | Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits[END_REF].

We first give a lower bound for the middle elementary symmetric polynomial. The argument is similar to the solution of Galvin's original problem presented in [START_REF] Frankl | Forbidden intersections[END_REF]Theorem 11.1], which we reproduce here for completeness. It is based on the following result, restricted here to the case of codes over an alphabet with 2 elements (we denote by ∆ the symmetric difference between two sets): Theorem 8 ( [START_REF] Frankl | Forbidden intersections[END_REF], Theorem 1.10). Suppose 0 < δ < 1 2 is given. Then there exists ε > 0 such that for any d even satisfying δn < d < (1 -δ)n, any family of distinct subsets

Lemma 4. There exists α > 0 such that for n ∈ 4N \ {0}, k = n/2 and j odd, any family {A 1 , . . . , A m } satisfying Equation (1) has size m αn.

Proof. Assume there exists A 1 , . . . , A m ⊆ [n] such that F = {A 1 , . . . , A m } satisfies Equation [START_REF] Noga Alon | Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits[END_REF]. Let V be the subspace of F n 2 spanned by the characteristic vectors of the elements of F. By assumption, for all B ∈ [n] n/2 , there exists F ∈ F such that |B ∩ F | = j; this means that χ(B), χ(F ) = 1 = 0 because j is odd. Hence V ⊥ contains no vector of weight n/2. Because V ⊥ is a vector space, it implies that for any

By Theorem 8,

Lemma 5. For n ∈ 4N, every weakly monotone ABP computing e n,n/2 has size Ω(n 2 ).

Proof. There exists α > 0 such that for n ∈ 4N, k = n/2 and j odd, any family {A 1 , . . . , A m } satisfying Equation ( 1) has size m αn by Lemma 4. It follows from Proposition 9 that for all M ∈ M j (e n,n/2 ), cov(M, D n,j,n/2-j ) αn. The lower bound is obtained by Corollary 2.

From the simple observation e n,k (x 1 , . . . , x m , 0, . . . , 0) = e m,k (x 1 , . . . , x m ), Lemma 5 yields quadratic lower bounds on the size of weakly monotone ABPs computing e n,k for δn k n/2 for a fixed δ > 0. However we need to be more careful to get a quadratic lower bound for e.g. e n,2n/3 . Indeed the simple reduction

uses divisions, which are not allowed in our model and would cost too much to remove. In an ABP, the formal degree fdeg t (α) of a node α with respect to a variable t is defined as the maximum degree in t of the polynomial computed along a path from the source to α, which is also the maximal degree in t of a monomial produced along a path from the source to α. By definition, the formal degree of the source is 0. Let us denote by α the polynomial computed at the node α. Remark that fdeg t (α) deg t (α). The formal degree in t of an ABP is the formal degree in t of its output.

Let us show now that we can always extract the part of maximal formal degree without changing the size of an ABP. We denote by [t k ]f the coefficient of the homogeneous component of f of degree k in t. Lemma 6. Let A be an ABP of size s and of formal degree k in the variable t computing a polynomial f . Then there exists A an ABP of size at most s such that A computes [t k ]f . Moreover, if A is weakly monotone, then it is also the case for A .

Proof. We show by induction that we can construct A such that for every node α in A, there is α in A which computes the coefficient of the homogeneous part of α of degree fdeg(α). That is, α computes [t fdeg(α) ]α. The result is immediate for an ABP with only one node since it computes 0. Let us consider a node α = 1 β 1 + . . . + m β m where β 1 , . . . , β m are predecessors of the node α in A and where 1 , . . . , m are linear forms. Let us denote by I and J the subsets of indices:

Then, β) ] βi .

So we just have to define

The second point is a consequence of the fact that if some monomial m cancels in A , the monomial t k m cancels in A.

Lemma 7. If there is a weakly monotone ABP of size s computing the polynomial e n,p , then for all q p, there is a weakly monotone ABP of size at most s which computes the polynomial e n-q,p-q .

Proof. Let us replace the variables x n-q+1 , . . . , x n in the weakly monotone ABP A computing e n,k by the variable t. As the monomial x 1 x 2 • • • x p-q x n-q+1 • • • x n appears in e n,p and gives a monomial of degree q with respect to t, the formal degree in t of our new ABP is exactly q. As we work over a field of characteristic 0, all monomials of the form t i∈I x i (for some 0 q) with I ⊆ [n -q] of size p -appear in e n,p (x 1 , . . . , x n-q , t, . . . , t). It implies that the ABP we get after substitution is still weakly monotone.

By Lemma 6, there is a weakly monotone ABP of size at most s which computes [t q ]e n,p (x 1 , . . . , x n-q , t, . . . , t) = e n-q,p-q .

Theorem 9. Every weakly monotone ABP, or equivalently every homogeneous syntactically multilinear ABP, computing e n,k has size Ω(min{k 2 , (n -k) 2 }).

Proof. Let us first prove the lower bound when n and k are even. If k n/2, then as mentioned previously, any weakly monotone ABP of size s implies a weakly monotone ABP of size at most s for e 2k,k by putting some variables to 0. So in this case s = Ω(k 2 ) by Lemma 5.


Edoardo Ruggeri

Samuel D Stranks

Emmanouil Manidakis

Constantinos C Stoumpos

Claudine Katan

Halide Perovskites: Low Dimensions for Devices

come

Among the 12 invited talks the 56 oral presentations and its 38 poster presentations (including a joint session with Symposium B -Emerging photovoltaics: strategies for more stable devices), the Symposium delivered lively discussion stimulated by the invited researchers who delineated the different themes of the Symposium. B. Lounis showed how the excitonphonon coupling operates in perovskites, presenting an excellent account on the photo-physics of halide perovskite nanocrystals at the single-particle level [START_REF] Tamarat | The Ground Exciton State of Formamidinium Lead Bromide Perovskite Nanocrystals Is a Singlet Dark State[END_REF] . On a more applied topic, M. Bodnarchuk explained the intricacies of the synthesis and emission tuning of colloidal perovskite nanocrystals, showing how much the interface interactions between the inorganic perovskite and the organic surfactants can influence the properties, and proposed innovative methodologies on how to control the interactions 2 . On the "phonon problem", R. Schaller presented a "high-throughput" study of many perovskite derivatives, experimentally pinpointing the anharmonic nature of the phonons that derive from the dynamically disordered nature of the crystal lattice [START_REF] Guo | Infrared-Pump Electronic-Probe of Methylammonium Lead Iodide Reveals Electronically Decoupled Organic and Inorganic Sublattices[END_REF] . P. Plochocka covered the excitons present in the perovskites and highlighted very vividly how to manipulate excitons using (enormous) magnetic fields and extract useful information on their binding energy and lifetimes within the perovskite structure [START_REF] Baranowski | Phase-Transition-Induced Carrier Mass Enhancement in 2D Ruddlesden-Popper Perovskites[END_REF] . Shifting the dimensionality to perovskite nanowires, the presentation of E. Horvath introduced many innovative methods to produce functional perovskite nanowires that can be shaped "at will" to various morphologies, by manipulating the substrate pattern and the surface conditions [START_REF] Ćirić | Mechanical Response of CH 3 NH 3 PbI 3 Nanowires[END_REF] . Two-dimensional (2D) halide perovskites, arguably one of the "hottest" topics in recent years, also had a strong representation with many talks on the topic from young investigators. The senior scientists were represented by S. Jin who explained how it is possible to construct heterostructures of these 2D materials akin to the development of III-V semiconductor heterostructures [START_REF] Fu | Incorporating Large A Cations into Lead Iodide Perovskite Cages: Relaxed Goldschmidt Tolerance Factor and Impact on Exciton-Phonon Interaction[END_REF] . In addition, D. Mitzi --a living legend in the halide perovskite field having almost single-handedly established the field in the 90's and the 00's --presented an excellent account on the historical evolution of the materials and explained where the field stands today [START_REF] Mitzi | Introduction: Perovskites[END_REF] . C. Quarti (Figure 2) stimulated 2D perovskite discussions from the theory point of view, explaining what can be learned from modelling the optical properties of the materials and how polarons play a key role in the evolution of the physical properties of dimensionally reduced perovskites [START_REF] Thouin | Phonon Coherences Reveal the Polaronic Character of Excitons in Two-Dimensional Lead Halide Perovskites[END_REF] .

The more traditional three-dimensional (3D) perovskites also had their key place in the Symposium, with their theoretical properties addressed as much as their different synthesis approaches, collectively revealing new permutations of the "malleable" perovskite structure. In an innovative and uncompromising presentation, A. Zunger cast a fresh eye on the halide perovskite structures -reframing them in the context of the polymorphous structure -to account for their unconventional features that are not easily addressable by means of conventional band structure calculations [START_REF] Zhao | The Polymorphous Nature of Cubic Halide Perovskites[END_REF] . H. Hillebrecht gave an excellent solid-state synthesis "tutorial", illustrating that the solid-state chemistry of halide perovskites is indeed very rich and well worth exploring further [START_REF] Daub | First Representatives of (210)-Oriented Perovskite Variants -Synthesis , Crystal Structures and Properties of the New 2D Hybrid Perovskites A[END_REF] . As he showed through a variety of crystal structures --from 3D "hollow" perovskites to 2D perovskites and molecular coordination compounds --it is possible to find almost anything in a beaker of a stirred perovskite solution! Combining theory and experiment, G. Volonakis (Figure 2) achieved a remarkable feat: he was able to predict in silico and isolate in vitro a new member of the double perovskite family, which even more impressively possessed the optical properties predicted by theory [START_REF] Volonakis | Oxide Analogs of Halide Perovskites and the New Semiconductor Ba 2 AgIO 6[END_REF] .

On the perovskite device front, the Symposium (jointly with Symposium B) featured talks on the major debate revolving around halide perovskites, namely their long-term stability and viability. A. Mohite (Figure 3) presented recent progress in 2D perovskite solar cells explaining in great detail how parameters such as phase purity and crystallinity play important roles in the performance and stability of devices [START_REF] Tsai | Light-Induced Lattice Expansion Leads to High-Efficiency Perovskite Solar Cells[END_REF] . A. Petrozza (Figure 3) focused on the intrinsic (in)stability of the perovskites governed by ionic motion and dynamic disorder within the materials, and on the unusual defect physics that are so important to the operation of perovskite photovoltaic devices [START_REF] Motti | Controlling Competing Photochemical Reactions Stabilizes Perovskite Solar Cells[END_REF] .

The Symposium of course featured a large number of young "rising stars" from the graduate school level all the way to senior postdoctoral researchers, all of whom contributed to advancing the scientific level of the symposium and moving perovskite systems a small but significant step forward. The covered topics ranging from the fundamental understanding of these remarkable materials to assessing their potential as a viable technology in the near future. In recognition of the prowess of the young investigators, awards were presented for the best graduate student (EMRS Graduate Student Award), awarded to Mr Young-Kwang Jung for his work on elucidating the green luminescence in the 0D perovskite Cs 4 PbBr 6 [START_REF] Jung | Intrinsic Doping Limit and Defect-Assisted Luminescence in Cs 4 PbBr 6[END_REF] . The best oral and best poster awards, sponsored by Nature Materials, were respectively awarded to Dr. Azhar Fakharuddin (Figure 2) for his talk on light-emitting diodes of two dimensional quasi-2D perovskites [START_REF] Fakharuddin | Reduced Efficiency Roll-Off and Improved Stability of Mixed 2D/3D Perovskite Light Emitting Diodes by Balancing Charge Injection[END_REF] and Géraud Delport (Figure 3) for his poster discussing the diffusion of carriers in perovskite crystals via timeresolved photoluminescence microscopy [START_REF] Stavrakas | Visualizing Buried Local Carrier Diffusion in Halide Perovskite Crystals via Two-Photon Microscopy[END_REF] .

In the organizers' view, as well as in the opinion of many participants, Halide Perovskites: low dimensions for devices was a fruitful meeting with discussions and debates from all around the halide perovskite and many useful energyrelated scientific conclusions reached. We believe that meetings with a similar scope should be held in the near future, since they will be beneficial for the advancement of the field -providing the critical links between fundamental science and applied device deployment.

Figure I .

 I Figure I. Photo of the late George Papavassiliou. (Photo courtesy of I. Koutselas.)

Figure

  Figure II. Photo of the best oral winner (W), prize committee members (M), and Symposium G "Halide Perovskites: Low Dimensions for Devices" organizers (O) at the occasion of the E-MRS19 Spring Meeting. From left to right: Claudio Quarti (M), Claudine Katan (O), Jovana Milic (M), George Volonakis (M), Azhar Fakharuddin (W), and Constantinos Stoumpos (O). Absent from the picture: Samuel Stranks (O).(Photo courtesy of J. Even.)

Figure

  Figure III. Photo of the best poster winner (W) and prize committee members (M) of Symposium G "Halide Perovskites: Low Dimensions for Devices" at the occasion of the E-MRS19 Spring Meeting. From left to right: Annamaria Petrozza (M), Aditya Mohite (M), and Géraud Delport (W). Absent from the picture: Richard Schaller (M). (Photo courtesy of J Even )

ACKNOWLEDGMENTS

Symposium G of the 2019 E-MRS Spring Meeting was co-organized by Constantinos Stoumpos, Samuel Stranks and Claudine Katan. Emmanouil Manidakis and Edoardo Ruggeri were assistants of the symposium. The organizers acknowledge support from ACS Energy Letters, Nature Materials, M. Braun Inertgas-Systeme GmbH, Edinburgh Instruments Ltd and CNRS think tank GDR HPERO (http://gdr-hpero.cnrs.fr/). Catherine Kocher and Sylvain Schoeffter are gratefully acknowledged for their invaluable logistical support.

AUTHOR INFORMATION

Corresponding Authors *E-mail: cstoumpos@materials.uoc.gr (C.C.S.). *E-mail: claudine.katan@univ-rennes1.fr (C.K.).

Notes

Views expressed in this Energy Focus are those of the authors and not necessarily the views of the ACS. The authors declare no competing financial interest.


Alain Le Bot
email: alain.le-bot@ec-lyon.fr

Hao Li

Nicolas Totaro
email: nicolas.totaro@insa-lyon.fr

Laurent Maxit
email: laurent.maxit@insa-lyon.fr

STATISTICAL ENERGY ANALYSIS AND DIFFUSE FIELD

Keywords: sound, vibration, statistical energy analysis, diffuse field, ergodic billiard

Statistical energy analysis (SEA) is a statistical theory of sound and vibration based on an analogy with thermodynamics. The main relationship of statistical energy analysis, the so-called coupling power proportionality, is intimately linked with the establishment of a diffuse vibration field in subsystems. In this study, we explore the conditions under which a diffuse field is enforced. We show that when the subsystem is excited by a point force, a low damping, a high frequency but also a ergodic billiard geometry are required conditions. Then, the energy exchange between two weakly coupled subsystems is proportional to the difference of vibrational energies. But when the field is not diffuse, the exchange of energy does not generally follow this proportionality. Numerical simulations are provided to support the discussion.

Introduction

Statistical energy analysis [START_REF] Bot | Foundation of statistical energy analysis in vibroacoustics[END_REF][START_REF] Lyon | Power flow between linearly coupled oscillators[END_REF][START_REF] Smith | Response and radiation of structural modes excited by sound[END_REF][START_REF] Newland | Calculation of power flow between coupled oscillators[END_REF][START_REF] Newland | Power flow between a class of coupled oscillators[END_REF][START_REF] Scharton | Power flow and energy sharing in random vibration[END_REF] is a statistical theory of sound and vibration in the same way it exists a statistical mechanics, statistical physics, statistical electromagnetism. The basic concept is that of diffuse field. A vibrational field, either structural or acoustical, is diffuse if it is random, homogeneous and isotropic [START_REF] Weaver | On diffuse waves in solid media[END_REF]. Nowadays, statistical energy analysis represents the most popular method in high frequency vibroacoustics although extensions and/or alternative methods have been developed [START_REF] Bot | A vibroacoustic model for high frequency analysis[END_REF][START_REF] Bot | Comparison of an integral equation on energy and the ray-tracing technique for room acoustics[END_REF][START_REF] Bot | A functional equation for the specular reflection of rays[END_REF][START_REF] Bot | Energy transfer for high frequencies in built-up structures[END_REF][START_REF] Bot | Energy exchange in uncorrelated ray fields of vibroacoustics[END_REF][START_REF] Sadoulet-Reboul | A hybrid method for vibroacoustics based on the radiative energy transfer method[END_REF][START_REF] Bot | High frequency vibroacoustics: A radiative transfer equation and radiosity based approach[END_REF][START_REF] Maxit | Extension of SEA model to subsystems with non-uniform modal energy distribution[END_REF][START_REF] Totaro | Extension of the statistical modal energy distribution analysis for estimating energy density in coupled subsystems[END_REF][START_REF] Tanner | Dynamical energy analysis -Determining wave energy distributions in vibro-acoustical structures in the high-frequency regime[END_REF][START_REF] Chappell | Dynamical energy analysis for built-up acoustic systems at high frequencies[END_REF][START_REF] Chappell | Boundary element dynamical energy analysis: A versatile method for solving two or three dimensional wave problems in the high frequency limit[END_REF].

Identifying the exact assumptions of statistical energy analysis is of primary importance for both, theoretical and practical points of view. The success in applications is conditioned by the knowledge of this list. But if the main assumptions are well identified, it seems that the exact list of assumptions may slightly differ for the authors [START_REF] Fahy | Statistical energy analysis: A critical overview[END_REF][START_REF] Burroughs | An introduction to statistical energy analysis[END_REF][START_REF] Mace | The statistical energy analysis of coupled sets of oscillators[END_REF][START_REF] Lafont | Review of statistical energy analysis hypotheses in vibroacoustics[END_REF][START_REF] Lafont | Coupling strength assumption in statistical energy analysis[END_REF].

In this study, we explore the status of the assumption of ergodicity of subsystems in statistical energy analysis [START_REF] Li | Ergodic billiards in statistical energy analysis[END_REF]. For this purpose, we shall systematically compare the prediction of statistical energy analysis with a reference calculation obtained by a direct numerical simulation. For each test case, we shall verify whether or not the exchanged power is proportional to the difference of modal energies, as claimed in statistical energy analysis.

Statistical energy analysis

To test wether or not, the geometry of subsystems must be ergodic to ensure the validity of statistical energy analysis, we consider a simple system composed of two coupled subsystems. The subsystems are thin plates in flexural vibrations coupled by a spring. The plates are excited by a stationary random moment whose spectrum is flat and confined within the bandwidth ∆ω.

The modal density of plate i defined as the number of modes per unit circular frequency ω (rad/s) is

n i = A i 4π m i D i (1)
where m i is the mass per unit area, D i the bending stiffness, and A i the plate area. The number of resonant modes in the frequency bandwidth ∆ω is N i = n i ∆ω.

We denote by E i the expectation of vibrational energy in subsystem i. Expectation must be understood in the meaning of probability theory since the excitation is random. This is the mean value for several realizations of the random process associated to excitation moment. By virtue of stationarity, E i does not depend on time. We also denote by P ij the expectation of vibrational power exchanged between subsystems i and j. Then, the main result of statistical energy analysis states the power being exchanged between subsystems i and j is proportional to the difference of modal energies

P ij = β ij E i n i - E j n j (2)
This is the coupling power proportionality. The conductivity factor β ij verifies reciprocity β ij = β ji . For two plates coupled by a spring, its value is given by [START_REF] Mace | The statistical energy analysis of coupled sets of oscillators[END_REF]

β ij = K 2 32πω 2 m i D i m j D j ( 3
)
where K is the stiffness of the coupling spring.

Ergodic billiard

We selected two different geometries for plates whose properties of ray dynamics are well-known. The stadium geometry is a typical example of ergodic billiard [START_REF] Tanner | Waves chaos in acoustics and elasticity[END_REF][START_REF] Polack | Playing billiards in the concert hall: the mathematical foundations of geometrical room acoustics[END_REF]. This imposes that any ray explores during its travel the entire phase space i.e. passes through the vicinity of all points and all directions. An example of ray path is given in Fig. 1, left. It can be seen that a single ray spread its energy uniformly and isotropically over the subsystem. This is exactly what is required to get a diffuse field. This illustrates the fact that an ergodic billiard ensures a diffuse field state even if the excitation is a single point and has a high directivity. The second example is a circular geometry. The conservation of incident angle on boundary is a feature particular to circle. An example of ray path is shown in Fig. 1, right. It can be seen that the ray turns inside the circle but never explores the central zone of the circle. This explains why a circle is not an ergodic billiard and therefore never gives a diffuse field.

Parameters of simulation

The parameters of the simulations are the following. The plates are all made of steel with Young's modulus E 0 = 210 GPa, density ρ = 7800 kg.m -3 and Poisson's ratio ν = 0.3. The plates have a damping loss factor η = 0.001. Plate 1 has thickness 2 mm and mass per unit area m 1 = 15.6 kg/m 2 while plate 2 has thickness 2.5 mm and mass per unit area m 2 = 19.5 kg/m 2 . Plate 1 is excited by a moment, or torque, simulated by two closed forces. The forces are out-of-phase but random. The frequency band of excitation is an octave centred on ω = 2π × 4000 rad.s -1 .

The size of plates is the following. The width of stadium is 0.7 m and the length is 1.6 m so that its area is A 1 = A 2 = 1 m 2 . The circle has diameter 1.13 m and has area A 1 = A 2 = 1 m 2 . These dimensions have been chosen to ensure a same number of modes for stadium and circle in the octave band 4000 Hz (see Tab. 1). The damping η is light so that the attenuation of wave per mean-free path, ηωl/c where c is the group speed and l the mean-free path, is small. A small attenuation ensures that rays reflect a large number of times before to vanish [START_REF] Bot | Validity diagrams of statistical energy analysis[END_REF]. The coupling spring stiffness is K = 1 × 10 5 N/m. The connection strength κ = K/(m 1 A 1 m 2 A 2 ω 4 ) 1/2 is small so that the coupling is weak [START_REF] Smith | Statistical models of coupled dynamical systems and the transition from weak to strong coupling[END_REF][START_REF] Mace | The statistical energy analysis of two continuous one-dimensional subsystems[END_REF][START_REF] Finnveden | A quantitative criterion validating coupling power proportionality in statistical energy analysis[END_REF]. 3) and reference calculation versus position of coupling spring (dashed line in left).

Results and comments

In Fig. 2 is shown the ratio β of exchanged power and difference of modal energies calculated respectively from Eq. ( 3) and by the reference calculation in the case of two coupled stadiums. It is observed that a fine agreement in found between statistical energy analysis and reference for any position of the coupling spring. This agreement is remarkable since the excitation is a unique torque applied. This type of excitation is severe for statistical energy analysis since it is highly localized and highly directive. We are far from the traditional rain-on-the-roof excitation. In this case, homogeneity and isotropy of vibrational field are guaranteed by ergodicity of stadium billiard , while a torque excitation provides neither homogeneity nor isotropy of source.

In Fig. 3 is shown the ratio β in same conditions but for two coupled circular plates. We observe a large disagreement between statistical energy analysis prediction and that of the reference calculation. The reason is that since the excitation is highly localized and directive, and that the subsystems are not ergodic, the vibrational field is never diffuse. The exchanged of energy between the two plates do not not follow the thermal law of Eq. ( 2) since the thermal equilibrium is not reached in subsystems.

Conclusion

Diffuse field is an imperative assumption of statistical energy analysis. The requirement of a rainon-the-roof excitation is a condition which ensures diffuseness of the field. But when the excitation is random but localized and/or highly directive, ergodicity of subsystem is an important condition to get a diffuse field. The counter-example of circular plates show that even if the frequency is high, the attenuation is low, and the coupling is weak, the coupling power proportionality may be violated when subsystems do not have ergodic geometries.

Figure 1 :

 1 Figure 1: Ray dynamics in various billiards. Left, ray tracing in a stadium. Right, ray tracing in a circle.

Figure 2 :

 2 Figure2: Comparison of energy transfer predicted by statistical energy analysis and reference calculation for two coupled stadium plates excited by a torque on plate 1. Factor β given by Eq. (3) and reference calculation versus position of coupling spring (dashed line in left).

Figure 3 :

 3 Figure 3: Comparison of energy transfer predicted by statistical energy analysis and reference calculation for two coupled circular plates excited by a torque on plate 1. Factor β given by Eq. (3) and reference calculation versus position of coupling spring (dashed line in left).

Table 1 :

 1 Parameters of plates.

	Plate	# Modes Attenuation Modal overlap Connection strength
	Stadium 1	450	0.036	0.64	10 -5
	Stadium 2	360	0.032	0.51	-
	Circle 1	450	0.040	0.64	10 -5
	Circle 2	360	0.035	0.51	-

ICSV26, Montreal, 7-11 July 2019

Acknowledgements

This work was supported by the Labex CeLyA of Université de Lyon, operated by the French National Research Agency (ANR-10-LABX-0060/ANR-11-IDEX-0007).