Nathanaël Fijalkow

Guillaume Lagarde

Pierre Ohlmann

Olivier Serre
email: olivier.serre@cnrs.fr

LOWER BOUNDS FOR ARITHMETIC CIRCUITS VIA THE HANKEL MATRIX

Keywords: Arithmetic Circuit Complexity, Lower Bounds, Parse Trees, Hankel Matrix Subject classification. 68Q17

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish (xy)z from x(yz). Our first and main conceptual result is a characterization result: we show that the size of the smallest circuit computing a given nonassociative polynomial is exactly the rank of a matrix constructed from the polynomial and called the Hankel matrix. This result applies to the class of all circuits in both commutative and non-commutative settings, and can be seen as an extension of the seminal result of Nisan giving a similar characterization for non-commutative algebraic branching programs. The study of the Hankel matrix provides a unifying approach for proving lower bounds for polynomials in the (classical) associative setting. Our key technical contribution is to provide generic lower bound theorems based on analyzing and decomposing the Hankel matrix. We obtain significant improvements on lower bounds for circuits with many parse trees, in both (associative) commutative and non-commutative settings, as well as alternative proofs of recent results proving superpolynomial and exponential lower bounds for different classes of circuits as corollaries of our characterization and decomposition results.

Introduction

The model of arithmetic circuits is the algebraic analogue of Boolean circuits: the latter computes Boolean functions and the former computes polynomials, replacing OR gates by addition and AND gates by multiplication. Computational complexity theory is concerned with understanding the expressive power of such models. A rich theory investigates the algebraic complexity classes VP and VNP introduced by Valiant [START_REF] Valiant | The Complexity of Computing the Permanent[END_REF]. A widely open problem in this area of research is to explicitly construct hard polynomials, meaning for which we can prove superpolynomial lower bounds. To this day the best general lower bounds for arithmetic circuits were given by Baur and Strassen [START_REF] Baur | The Complexity of Partial Derivatives[END_REF] for the polynomial n i=1 x d i , which requires Ω(n log d) operations.

The seminal paper of Nisan [START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF]) initiated the study of non-commutative computation: in this setting variables do not commute, and therefore xy and yx are considered as being two distinct monomials. Non-commutative computations arise in different scenarios, the most common mathematical examples being when working with algebras of matrices, group algebras of noncommutative groups or the quaternion algebra. A second motivation for studying the non-commutative setting is that it makes it easier to prove lower bounds which can then provide powerful ideas for the commutative case. Indeed, commutativity allows a circuit to rely on cancellations and to share calculations across different gates, making them more complicated to analyze.

1.1. Nisan's Characterization for ABP. The main result of Nisan [START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF]) is to give a characterization of the smallest ABP computing a given polynomial. As a corollary of this characterization Nisan obtains exponential lower bounds for the noncommutative permanent against the subclass of circuits given by ABPs.

We sketch the main ideas behind Nisan's characterization, since our first contribution is to extend these ideas to the class of all non-associative circuits. An ABP is a layered graph with two distinguished vertices, a source and a target. The edges are labelled by affine functions in a given set of variables. An ABP computes a polynomial obtained by summing over all paths from the source to the target, with the value of a path being the multiplication of the affine functions along the traversed edges. Following Nisan, fix a polynomial f , and define a matrix N f whose rows and columns are indexed by monomials: for u, v two monomials, let N f (u, v) denote the coefficient of the monomial u • v in f .

The beautiful and surprisingly simple characterization of Nisan states that for a homogeneous (i.e., all monomials have the same degree) non-commutative polynomial f , the size of the smallest ABP computing f is exactly the rank of N f . The key idea is to decompose the computation arising in the ABP, say C: to any vertex r in C we associate two polynomials L r and R r that are respectively the one computed by the ABP induced by the original source of C and target r and the one computed by the ABP induced by source r and the original target of C. For a polynomial f and a monomial m we use f (m) to denote the coefficient of m in f .

For u, v two monomials, we observe that the coefficient of u • v in f is equal to r L r (u)R r (v), where r ranges over all vertices of C, L r (u) is the coefficient of u in L r , and R r (v) is the coefficient of v in R r . We see this as a matrix equality:

N f = r L r • R r ,
where L r is seen as a column vector, and R r as a row vector. By subadditivity of the rank and since the product of a column vector by a row vector is a matrix of rank at most 1, this implies that the rank of N f is bounded by the size of the ABP, yielding the lower bound in Nisan's result.

The crucial idea of splitting the computation of a monomial into two parts had been independently developed by Fliess when studying so-called Hankel Matrices in [START_REF] Fliess | Matrices de Hankel[END_REF] to derive a very similar result in the field of weighted automata, which are finite state machines recognising words series, i.e., functions from finite words into a field. Fliess' theorem (Fliess 1974, Th. 2.1.1) states that the size of the smallest weighted automaton recognising a word series f is exactly the rank of the Hankel matrix of f . The key insight to relate the two results is to see a non-commutative monomial as a finite word over the alphabet whose letters are the variables. Using this correspondence one can obtain Nisan's theorem from Fliess' theorem, observing that the Hankel matrix coincides with the ma-trix N f defined by Nisan and that acyclic weighted automata correspond to ABPs. (We refer to an early technical report of this work for more details on this correspondence [START_REF] Fijalkow | Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees[END_REF]).)

1.2. Non-Associative Computations. Hrubeš, Wigderson and Yehudayoff [START_REF] Hrubeš | Noncommutative circuits and the sum-of-squares problem[END_REF] drop the associativity rule and show how to define the complexity classes VP and VNP in the absence of either commutativity or associativity (or both) and prove that these definitions are sound in particular by obtaining the completeness of the permanent.

In the same way that a non-commutative monomial can be seen as a word, a non-commutative and non-associative monomial such as (xy)(x(zy)) can be seen as a tree, and more precisely as an ordered binary rooted tree whose leaves are labelled by variables. The starting point of our work was to exploit this connection. The work of Bozapalidis and Louscou-Bozapalidou [START_REF] Bozapalidis | The Rank of a Formal Tree Power Series[END_REF] extends Fliess' result to trees; although we do not technically rely on their results, they serve as a guide, in particular for understanding how to decompose trees.

Let us return to the key idea in Nisan's proof, which is to decompose the computation of an ABP into two parts. The way a monomial, e.g., x 1 x 2 x 3 • • • x d , is evaluated in an ABP is very constrained, namely from left to right, or if we make the implicit non-associative structure explicit as w = (• • • (((x

1 x 2 )x 3 )x 4 ) • • • )x d .
The decompositions of w into two monomials u, v are of the form

u = (• • • ((x 1 x 2 )x 3 ) • • • )x i-1 ) and v = (• • • (( x i )x i+1 ) • • • )x d .
Here Let f be a non-associative (possibly commutative) polynomial f , the Hankel matrix H f of f is defined as follows: the rows of Extending Nisan's proof to computations in a general circuit, which are done along trees, we obtain a characterization in the non-associative setting (a more precise statement is given by Theorem 2.4)).

Theorem. Let f be a non-associative homogeneous polynomial and let H f be its Hankel matrix. Then, the size of the smallest circuit computing f is exactly rank (H f ).

Note that this is a characterization result: the Hankel matrix exactly captures the size of the smallest circuit computing f (upper and lower bounds), exactly as in Nisan's result. Hence, understanding the rank of the Hankel matrix is equivalent to studying circuits for f . We recover and extend Nisan's characterization as a special case of our result. The shape of a non-associative monomial is the tree obtained by forgetting the variables, e.g., the shape of (z((xy

)((xx)y))) is (_ ((_ _)((_ _) _))).
The parse trees of a circuit C are the shapes induced by computations in C.

Many interesting classes of circuits can be defined by restricting the set of allowed parse trees, both in the commutative and the non-commutative setting.

• The simplest such class is that of Algebraic Branching Programs (ABP) [START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF][START_REF] Dvir | Separating multilinear branching programs and formulas[END_REF][START_REF] Ramya | Deterministic polynomial identity testing in non-commutative models[END_REF], whose only parse trees are left-combs, that is, the variables are multiplied sequentially.

• Lagarde, Malod and Perifel [START_REF] Lagarde | Non-commutative computations: lower bounds and polynomial identity testing[END_REF] introduced the class of Unique Parse Tree circuits (UPT), which are circuits computing non-commutative homogeneous (but associative) polynomials such that all monomials are evaluated in the same non-associative way.

• The class of skew circuits [START_REF] Toda | Classes of Arithmetic Circuits Capturing the Complexity of Computing the Determinant[END_REF][START_REF] Allender | Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds[END_REF][START_REF] Malod | Characterizing Valiant's algebraic complexity classes[END_REF][START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF] and its extension to small non-skew depth circuits [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF], together with the class of unambiguous circuits (Arvind & Raja 2016) are all defined via parse tree restrictions.

• We propose in our technical developments some related restrictions called slightly balanced and slightly unbalanced circuits. Our most technical developments are discussed in Section 4.

We prove generic lower bound results by further analyzing and decomposing the Hankel matrix, with the following proof scheme.

We consider a polynomial f in the associative setting. Let C be a circuit computing f . Forgetting about associativity we can see C as computing a non-associative polynomial f , which projects onto f , meaning is equal to f assuming associativity. This induces a set of linear constraints: for instance if the monomial xyz has coefficient 3 in f , then we know that f ((xy)z) + f (x(yz)) = 3. We make use of the linear constraints to derive lower bounds on the rank of the Hankel matrix H f , yielding a lower bound on the size of C.

The final section is devoted to applications of our results, where we obtain superpolynomial and exponential lower bounds for various classes. In the results mentioned below, n is the number of variables, d is the degree of the polynomial, and k the number of parse trees. We note that the lower bounds hold for any (prime) n, any d, and any field.

We obtain alternative proofs of some known lower bounds: unambiguous circuits (Arvind & Raja 2016), skew circuits [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF]) and small non-skew depth circuits (obtaining a much shorter proof than [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF])).

Our novel results are:

• Slightly unbalanced circuits. We extend the exponential lower bound from [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF]) on 1 5 -unbalanced circuits to 1 2 -ε -unbalanced circuits.

• Slightly balanced circuits. We derive a new exponential lower bound for ε-balanced circuits.

• Circuits with k parse trees in the non-commutative setting.

We substantially extend the superpolynomial lower bound of [START_REF] Lagarde | Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees[END_REF]

from k = 2 d 1/3-ε to k = 2 d 1-ε , the
total number of possible non-commutative parse trees being d) .

2 O(
• Circuits with k parse trees in the commutative setting. We substantially extend the superpolynomial lower bound from (Arvind

& Raja 2016) from k = d 1/2-ε to k = 2 d 1/3-ε
, and even to Most approaches for proving lower bounds rely on algebraic techniques and the rank of some matrix. A different and beautiful approach was investigated by Hrubeš, Wigderson and Yehudayoff [START_REF] Hrubeš | Noncommutative circuits and the sum-of-squares problem[END_REF] in the non-commutative setting through the study of the so-called sum-of-squares problem. Roughly speaking, the goal is to decompose Polynomials. Let K be a field and let X be a set of variables.

k = 2 d 1-ε , when d is polylogarithmic in n.
(x 2 1 +• • •+x 2 k )•(y 2 1 +• • •+y 2 k ) into
Following [START_REF] Hrubeš | Noncommutative circuits and the sum-of-squares problem[END_REF] we consider that unless otherwise stated multiplication is neither commutative nor associative. We assume however that addition is commutative and associative, and that multiplication distributes over addition. A monomial is a product of variables in X and a polynomial f is a formal finite sum i c i m i where m i is a monomial and c i ∈ K is a non-zero element called the coefficient of m i in f . We let f (m i ) denote the

coefficient of m i in f , so that f = i f (m i )m i .
The degree of a monomial is defined in the usual way, i.e., deg(x) = 1 when x ∈ X and deg(m 1 m 2 ) = deg(m 1 ) + deg(m 2 ); the degree of a polynomial f is the maximal degree of a monomial in f .

A polynomial is homogeneous if all its monomials have the same degree. Depending on whether we include the relations u

• v = v • u (commutativity) and u • (v • w) = (u • v)
• w (associativity) we obtain four classes of polynomials.

Unless otherwise specified, for a polynomial f we use n for the number of variables and d for the degree.

Trees and Contexts. The trees we consider have a single root and binary branching (every internal node has exactly two children). To account for the commutative and for the non-commutative setting we use either unordered trees or ordered trees, the only difference being that in the case of ordered trees we distinguish the left child from the right child. We let Tree denote the set of trees (it will be clear from the context whether they are ordered or not).

The size of a tree is defined as its number of leaves.

A non-associative monomial t is a tree with leaves labelled by variables. If t is non-commutative then it is an ordered tree, and if t is commutative then it is an unordered tree. We let Tree(X)

denote the set of trees whose leaves are labelled by variables in X and Tree i (X) denote the subset of such trees with i leaves, which are monomials of degree i. Given a non-associative monomial t, we let label(t) be the associative monomial corresponding to the multiplication of the variables at the leaves of t. If t is noncommutative, the multiplication is done from left to right, and label(t) is a non-commutative monomial, that is, a word.

In this paper, we see polynomials as finitely supported mappings from monomials to K. For instance, in the non-associative setting where monomials are trees, a non-associative polynomial is a map Tree(X) → K. To avoid possible confusion, let us insist that the notation f (t) refers to the coefficient of the monomial t in the polynomial f , not to be confused with the evaluation of f at a given point.

A (ordered or unordered) context is a tree with a distinguished leaf labelled by a special symbol called the hole and written .

We let Context(X) denote the set of contexts whose leaves are labelled by variables in X. Given a context c and a tree t we construct a new tree c[t] by substituting the hole of c by t. This operation is defined in both ordered and unordered settings. See Note that H f is an infinite matrix with finite support, so its rank is well defined. As we will be interested in computing the rank of H f , we freely depict its rows and columns ordered arbitrarily and conveniently.

Arithmetic Circuits. An (arithmetic) circuit is a directed acyclic graph such that the vertices are of three types:

• input gates: they have in-degree 0 and are labelled by vari- ables in X,

• addition gates: they have arbitrary in-degree, an output weight in K, and a weight w(a) ∈ K on each incoming arc a,

• multiplication gates: they have in-degree 2, and we distinguish between the left child and the right child.

Each gate v in the circuit computes a polynomial f v which we define by induction.

• An input gate labelled by a variable x ∈ X computes the polynomial x.

• An addition gate v with n arcs incoming from gates v 1 , . . . , v n and with weights α 1 , . . . , α n , computes the polynomial

α 1 f v 1 + • • • + α n f vn .
• A multiplication gate with left child u and right child v computes the polynomial f u f v .

The circuit itself computes a polynomial given by the sum over all addition gates of the polynomial computed by the gate times its output weight. Note that it is slightly unusual that all addition gates contribute to the circuit; one can easily reduce to the classical case where there is a unique output addition gate by adding an extra gate.

We shall make a syntactic assumption: each arc is either coming from, or going to (but not both), an addition gate. Any circuit can be put into this form by adding addition gates, at most one per input gate and per multiplication gate (see Figure 2.2). We also ask two input gates referring to the same variable to not feed the same addition gate. We then define the size of a circuit to be its number of addition gates, which compensates this small blow up.

Doing so we slightly differ from usual, however this will allow our characterization result to be exact.

Note that the definitions we gave above do not depend on which of the four settings we consider: commutative or non-commutative, associative or non-assocative. The key step to go from ABPs to general circuits is the following: the polynomial computed by an ABP is the sum over the paths of the underlying graph, whereas in a general circuit the sum is over trees. We formalize this in the next definition by introducing runs of a circuit. The definition is given in the non-commutative setting but easily adapts to the commutative setting as explained later in Remark 2.2.

Definition 2.1. Let C be a circuit and V ⊕ denote its set of addition gates. Let t ∈ Tree(X) be a monomial. A run of C over t is a map ρ from nodes of t to V ⊕ such that (i) A leaf of t with label x ∈ X is mapped to a gate with a non-zero edge incoming from an input gate labelled by x.

Figure 2.2: The circuit on the left does not satisfy our syntactic assumption because of the edges leaving the greyed gates. However, the one on the right, obtained by adding two addition gates does satisfy the assumption. It has size 6. Both circuit compute the same polynomials in each setting, which are given in the table below, where the abbreviations A, NA, C, NC respectively stand for associative, non-associative, commutative, non-commutative.

We use labelled outgoing edges to depict output weights, and omit them when the output weight is 0.

(ii) If n is a node of t with left child n 1 and right child n 2 , then ρ(n) has a non-zero edge incoming from a multiplication gate with left child ρ(n 1 ) and right child ρ(n 2 ).

The value val(ρ) of ρ is a non-zero element in K defined as the product of the weights of the edges mentioned in items (i) and (ii)

together with the output weight of ρ(r), r being the root of t.

We write by a slight abuse of notation ρ : t → V ⊕ for runs of C over t. Remark 2.2. In the commutative setting we simply replace item (ii) by: "if n is a node of t with children n 1 , n 2 , then ρ(n) has a non-zero edge incoming from a multiplication gate with children ρ(n 1 ), ρ(n 2 )".

A run of C over a monomial t additively contributes to the coefficient of t in the polynomial computed by C, leading to the following straighforward lemma.

Lemma 2.3. Let C be a circuit computing the non-associative poly-

nomial f : Tree(X) → K. Then the coefficient f (t) of a monomial t ∈ Tree(X) in f is equal to ρ:t→V ⊕ val(ρ).
We may now state and prove our cornerstone result, which holds in both the commutative and non-commutative settings.

Theorem 2.4. Let f : Tree(X) → K be a non-associative polynomial, H f be its Hankel matrix, and C be a circuit computing

f . Then |C| ≥ rank (H f ). Moreover, if f is homogeneous this bound is tight, meaning there exists a circuit C computing f of size rank (H f ).
Note that an interesting feature of this theorem is that the upper bound is effective: given a homogenous polynomial one can construct a circuit computing this polynomial of size rank (H f ).

The proof of the lower bound follows the same lines as Nisan's original proof for non-commutative ABPs [START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF].

Proof. We start with the lower bound, that is, |C| ≥ rank (H f ).

Let C be a circuit computing the non-associative polynomial For each v ∈ V ⊕ we define two circuits which decompose the computations around v. Let C v 1 be the circuit obtained from C by changing all output weights to 0 except that of v which is set to 1.

f : Tree(X) → K. Let V ⊕ denote
Note that C v 1 can be seen as the restriction of C to descendants of v.

Let C v 2 be another copy of C with just one extra input gate labelled by a fresh variable / ∈ X with a single outgoing edge with weight

1 going to v. We let f v : Tree(X) → K denote the polynomial computed by C v 1 and g v : Context(X) → K denote the restriction of the polynomial computed by C v 2 to Context(X) ⊆ Tree(X { }).
We now show the equality

H f (c, t) = v∈V ⊕ f v (t)g v (c).
For that, fix a monomial t ∈ Tree(X) and a context c ∈ Context(X) and denote by n the leaf of c labelled by , which is also the root of t and the node to which t is substituted with in

c[t]. Relying on Lemma 2.3, we calculate the coefficient f (c[t]) of c[t] in f . f (c[t]) = ρ:c[t]→V ⊕ val(ρ) = v∈V ⊕ ρ:c[t]→V ⊕ ρ(n )=v val(ρ) = v∈V ⊕ ρ v 1 :t→V ⊕ ρ v 1 (n )=v ρ v 2 :c→V ⊕ ρ v 2 (n )=v val(ρ v 1 )val(ρ v 2 ) = v∈V ⊕ ρ v 1 :t→V ⊕ ρ v 1 (n )=v val(ρ v 1 ) ρ v 2 :c→V ⊕ ρ v 2 (n )=v val(ρ v 2 ) = v∈V ⊕ f v (t)g v (c). Let M v ∈ K Tree(X)×Context(X) be the matrix given by M v (t, c) = f v (t)g v (c):
its rank is at most one as M v is the product of a column vector by a row vector. The previous equality reads in matrix form

H f = v∈V ⊕ M v .
Hence, we obtain the announced lower bound using rank subadditivity:

rank (H f ) = rank   v∈V ⊕ M v   ≤ v∈V ⊕ rank (M v ) ≤ |V ⊕ | = |C|.
We now turn to the upper bound, and assume f is homogeneous.

We first give a construction of a circuit, then provide and prove by induction a strong invariant which implies that the circuit does indeed compute f . For every t ∈ Tree(X), we let H t denote the corresponding column in the Hankel matrix, i.e.

H t : c → c[t]. Let T ⊆ Tree(X) be such that (H t ) t∈T is a basis of {H t | t ∈ Tree(X)}. In particular T has size rank (H f ). For any t ∈ Tree(X), we let α t t denote the coefficient of H t in the decomposition of H t on (H t ) t∈T , that is, ( ) H t = t∈T α t t H t .
We may now explicitly define circuit C:

• The addition gates are (identified with) elements of T . The output weight of t ∈ T is f (t).

• The input gates are given by elements of X (and the matching label). The input gate x ∈ X has an outgoing arc to the addition gate t ∈ T with weight α x t .

• The multiplication gates are given by elements (t 0 , t 1 , t) ∈ T 3 .

Such a multiplication gate has an incoming arc from t 0 on the left, an incoming arc from t 1 on the right, and an outgoing arc to t, with weight α

t 1 •t 2 t .
Note that the size of

C is |T | = rank (H f ).
For C to be well-defined as a circuit, it remains to show that its underlying graph is acyclic. This is implied by the fact that

α t 1 •
(c[t]) = d, that is, deg(c) = d -deg(t) + 1.
Hence, the set {H t , t ∈ T } may be partitioned according to the degree of t into parts with disjoint support, so for the decomposition ( ) to hold, it must be that

α t t = 0 implies deg(t) = deg(t ).
For t ∈ T , we let g t : Tree(X) → K denote the polynomial computed at gate t in C. We will now show, by induction on the size of t ∈ Tree(X), that g t (t ) = α t t .

If t = x ∈ X, then g t (t ) = α x t , so the base case is clear. We now assume that t = t 1 • t 2 ∈ Tree(X), and show that t∈T g t (t )H t = H t , which is enough to conclude by uniqueness of the decomposition in( ). For that we will show that the previous equality holds for any context c ∈ Context(X).

We first remark the following

t∈T g t (t )H t = t∈T t 1 ,t 2 ∈T α t 1 •t 2 t g t 1 (t 1 )g t 2 (t 2 ) H t = t∈T t 1 ,t 2 ∈T α t 1 •t 2 t α t 1 t 1 α t 2 t 2 H t = t 1 ,t 2 ∈T α t 1 t 1 α t 2 t 2 t∈T α t 1 •t 2 t H t = t 1 ,t 2 ∈T α t 1 t 1 α t 2 t 2 H t 1 •t 2 . Now, let c ∈ Context(X).
For any tree t ∈ Tree(X), we define Evaluating at c, we now obtain

c 1 t = c[ • t] ∈ Context(X), and c 2 t = c[t • ] ∈ Context(X) (see Figure 2.4). Then for any t 1 , t 2 , c[t 1 • t 2 ] = c 1 t 2 [t 1 ] = c 2 t 1 [t 2 ].
t∈T g t (t )H t (c) = t 1 ,t 2 ∈T α t 1 t 1 α t 2 t 2 H t 1 •t 2 (c) = t 1 ,t 2 ∈T α t 1 t 1 α t 2 t 2 f (c[t 1 • t 2 ]) = t 1 ,t 2 ∈T α t 1 t 1 α t 2 t 2 f (c 1 t 2 [t 1 ]) = t 1 ,t 2 ∈T α t 2 t 2 H t 1 (c 1 t 2 ) = t 2 ∈T α t 2 t 2 H t 1 (c 1 t 2 ) = t 2 ∈T α t 2 t 2 H t 1 •t 2 (c) = t 2 ∈T α t 2 t 2 f (c 2 t 1 [t 2 ]) = t 2 ∈T α t 2 t 2 H t 2 (c 2 t 1 ) = H t 2 (c 2 t 1 ) = H t (c)
which proves the wanted invariant, namely g t (t ) = α t t . Hence, the value computed by the circuit for monomial t is precisely

t∈T g t (t )f (t) = t∈T α t t H t ( ) = H t ( ) = f (t ),
which concludes the proof of the upper bound. (2010) in the newly introduced vocabulary.

Corollary 2.5. For d > 1, let f be the commutative non-associative polynomial of degree 2d and over two variables x 0 and x 1 defined by

f = ε 1 ,...,ε d ∈{0,1} (((• • • (x ε 1 x ε 2 )x ε 3 ) • • • )x ε d ) 2 .
Any circuit computing f has size at least 3 × 2 d-2 .

Proof. We give a lower bound on the rank of the Hankel matrix.

We consider the submatrix restricted to contexts with (d+1) leaves of the form (((

• • • (((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ) )
and to trees with d leaves of the form

((• • • (((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ). See
((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ) ), the tree t = ((• • • (((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ) and their composi- tion c[t].
This matrix is a permutation matrix of size 3 × 2 d-2 , which is, up to commutativity, the number of different trees or contexts of the form mentioned above.

We now present a first lower bound in the associative setting.

The method we shall use is generic: consider an associative circuit C, from a given restricted class of circuits, computing a given polynomial f . Let f be the non-associative polynomial computed by C when it is seen as non-associative. The restriction on C together with the coefficients in f provide informations on f which we use to derive a lower bound on rank (H), which is also a lower bound on C thanks to Theorem 2.4.

Lower Bound Against Associative Unambiguous Circuits.

We give a lower bound for unambiguous circuits computing the associative permanent or determinant. A circuit is said unambiguous, if for each (associative) monomial m, there is at most one tree t labelled by m such that C has a run over t. Such circuits were already studied in [START_REF] Vikraman Arvind | Some Lower Bound Results for Set-Multilinear Arithmetic Computations[END_REF], in which the authors provide a lower bound for the permanent: we show how to recover their result using the Hankel matrix. Note that this notion makes sense in both the commutative and the non-commutative settings and that our lower bounds hold in both settings.

Recall that, on variables X = {x i,j | i, j ∈ [n]}, if one lets S n denote the set of all permutations over [n] and sgn(σ) denote the signature of a permutation σ, the determinant of degree n is the polynomial

Det = σ∈Sn n i=1 sgn(σ)x i,σ(i)
and the permanent of degree n is the polynomial

Per = σ∈Sn n i=1 x i,σ(i) .
Corollary 2.6. Any unambiguous circuit computing the determinant or the permanent of degree n has size at least n n/3 .

Proof. Consider an unambiguous circuit C computing the permanent (the proof is easily adapted to a circuit computing the determinant) of degree n on variables X = {x i,j | i, j ∈ [n]}. For any permutation σ, let t σ ∈ Tree(X) be the unique (non-associative) monomial along which there is a run computing the (associative)

monomial x 1,σ(1) x 2,σ(2) • • • x n,σ(n) .
Then, the non-associative polynomial f computed by C when it is seen as a non-associative circuit is precisely f = σ t σ . According to Theorem 2.4, it suffices to lower bound the rank of H f .

Let (A, S) ⊆ [n] 2 be a pair of subsets. We let T A→S ⊆ Tree(X) be the subset of trees t such that the set of first (resp. second) indices of the labels of t is precisely A (resp. S). Symmetrically, let C A→S ⊆ Context(X) be the subset of contexts c such that the set of first (resp. second) indices of the labels (except for the ) of c is precisely [n] \ A (resp.

[n] \ S). If (A, S) = (A , S ), then T A→S and T A →S are disjoint, as is the case for C A→S and C A →S . Moreover, if t ∈ T A→S and c ∈ C A →S , it must be that f (c[t]) = 0. Hence, H f is a block-diagonal matrix, with blocks H A,S being given by restricting the columns to some T A→S and the rows to C A→S . Note that if |A| = |S| then H A,S = 0. In particular, rank

H f = A,S⊆[n] |A|=|S| rank (H A,S ) .
We now show using a counting argument that an exponential number of such blocks are non-zero and hence, have rank at least 1.

For all permutations σ, we choose a subtree t σ of t σ which has size in [n/3, 2n/3], and let (A σ , S σ ) be such that

t σ ∈ T Aσ→Sσ . Note that n/3 ≤ |A σ | = |S σ | = |t σ | ≤ 2n/3, and that H Aσ,Sσ = 0. Moreover, it must be that σ(A σ ) = S σ . Hence, if A, S ⊆ [n] are fixed such that n/3 ≤ |A| = |S| ≤ 2n/3, |{σ | A σ = A and S σ = S}| ≤ |{σ | σ(A) = S}| ≤ n 3 ! 2n 3 !
Hence, the number of non-zero blocks H A,S is at least

n! n 3 ! 2n 3 ! = n n/3
which concludes the proof.

Note that this exact proof goes beyond the case of unambiguous circuits. It is actually sufficient to assume that all non-associative monomials t such that f (t) = 0 are labelled by a monomial of the

form x 1,σ(1) x 2,σ(2) • • • x n,σ(n)
for some permutation σ.

Decomposing the Hankel Matrix: Unique

Parse Tree Circuits

Theorem 2.4, as already illustrated by Corollary 2.6, is a natural tool to derive lower bounds thanks to an analysis of the rank of the Hankel Matrix. In order to lower bound this rank for the most general classes possible, we need tools, parse trees and partial derivative matrices, that we introduce now; we then apply these tools to derive a general result regarding the class of Unique Parse Tree circuits (Theorem 3.9). In Section 4, we will push this analysis further and derive generic lower bounds.

3.1. Parse Trees. With any monomial t ∈ Tree(X) we associate its shape shape(t) ∈ Tree as the tree obtained from t by removing the labels at the leaves.

Definition 3.1. Let C be a circuit computing a non-commutative non-associative polynomial f . A parse tree of C is any shape s ∈ Tree for which there exists a monomial t ∈ Tree(X) whose coefficient in f is non-zero and such that s = shape(t). We let

PT (C) = {shape(t) | f (t) non-zero}.
The notion of parse trees has been considered in many previous works, see for example [START_REF] Jerrum | Some Exact Complexity Results for Straight-Line Computations over Semirings[END_REF][START_REF] Allender | Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds[END_REF]; The partial derivative matrix M A (f ) of f with respect to

Malod
A is defined as follows: the rows are indexed by u ∈ X d-i and the columns by v ∈ X i , and the value of

M A (f ) (u, v) is the coefficient of the monomial u ⊗ A v in f .
Remark 3.4. The terminology partial derivative matrix, widely adopted in the literature, comes from the observation that the row labelled by monomial u of the matrix contains the coefficients of the partial derivative ∂f ∂u . The same remark can be made for columns of M A (f ). This will not be exploited in this paper. The following lemma (see e.g., [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF])) informally says that, if A and B are close to each other, then the ranks of the corresponding partial derivative matrices are close to each other as well. Though it is well known, we give a proof for completeness.

Lemma 3.8. Let f be a homogeneous non-commutative associative polynomial of degree d with n variables. Then, for any subsets At this point, we have the material in hands to describe a precise characterization of the size of the smallest Unique Parse Tree circuit which computes a given polynomial. We take this short detour before moving on to our core lower bound results in Section 4.

A, B ⊆ [d], rank (M A (f )) ≤ n dist(A,B) rank (M B (f )).
x rank (M A (f ) x ), but each M A (f ) x is a submatrix of M B (f ) so that rank (M A (f ) x ) ≤ rank (M B (f )),

Characterization of Smallest Unique

Parse Tree Circuit. Unique Parse Tree (UPT) circuits are non-commutative associative circuits with a unique parse tree. They were first introduced in [START_REF] Lagarde | Non-commutative computations: lower bounds and polynomial identity testing[END_REF]). They generalize ABPs, which are equivalent to UPT circuits with a left comb as their unique parse tree (a left comb being a tree corresponding to the shape of tree t in Figure 2.5). Hence, we recover Nissan's Theorem [START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF] when instantiating our characterization result, Theorem 3.9, to left combs. Our techniques allow a slight improvement and a better understanding of their results since the original result requires a normal form which can lead to an exponential blow-up. Given a shape s ∈ Tree of size d, i.e., with d leaves and a node v of s, we let s v denote the subtree of s rooted in v, and

I v ⊆ [d]
denote the interval of positions of the leaves of s v in s. We say that s ∈ Tree is a subshape of s if s = s v for some v, and that Let f be a homogeneous non-commutative associative polyno-mial of degree d, let s ∈ Tree be a shape of size d, and let s be a subshape of s such that v 1 , . . . , v p are all the nodes v of s such that s = s v . We define

I ⊆ [d] is spanned by s if I = I v for some v.
M s =      M Iv 1 (f ) M Iv 2 (f )
. . .

M Iv p (f )      .
Theorem 3.9. Let f be a homogeneous non-commutative associative polynomial of degree d and let s ∈ Tree be a shape of size d. Then the smallest UPT circuit with shape s computing f has size exactly s subshape of s rank (M s ) .

Proof. Let C be a UPT circuit with shape s computing f . We let f denote the non-associative polynomial computed by C.

Since C is UPT with shape s, f is the unique non-associative polynomial which is non-zero only on trees with shape s and projects to f , i.e., f (t) = f (u) if shape(t) = s and t is labelled by u, and

f (t) = 0 otherwise.
In particular, the size of the smallest UPT circuit with shape s computing f is the same as the size of the smallest circuit computing f , which thanks to Theorem 2.4 is equal to the rank of the

Hankel matrix H f .

The Hankel matrix of f may be non-zero only on columns indexed by trees whose shapes s are subshapes of s, and on such columns, non-zero values are on rows corresponding to a context obtained from s by replacing an occurrence of s by . The corresponding blocks are precisely the matrices M s , and are placed in a diagonal fashion, hence the lower bound.

Theorem 3.9 can be applied to concrete polynomials, for instance to the permanent of degree d.

Corollary 3.10. Let s ∈ Tree be a shape. The smallest UPT circuit with shape s computing the permanent has size

v node of s d |I v | ,
where I v is the set of leaves in the subtree rooted at v in s. In particular, this is always larger than d d/3 .

Proof. Let s be a subshape of s, and v 1 , ..., v p be all the nodes of s such that s v i = s . Let = |I v i | which does not depend on i.

There are no i = j such that v i is a descendant of v j , so the

I v i are pairwise disjoint. Let I v i = [a i , a i + -1]. The coefficient of M Iv i (Per) in (u, w) ∈ X d-× X , namely, Per(u ⊗ Iv i w)
, may be non-zero only if w is of the form

x a i ,b 1 x a i +1,b 2 • • • x a i + -1

Decomposing the Hankel Matrix: Generic Lower Bounds

We now get to the technical core of the paper where we establish generic lower bound theorems through a decomposition of the Hankel matrix, that we will later instantiate in Section 5 to concrete classes of circuits.

We first restrict ourselves to the non-commutative setting. Our first decomposition, Theorem 4.1, seems to capture mostly previously known techniques. However, the second, more powerful, decomposition, Theorem 4.2, takes advantage of the global shape of the Hankel matrix. Doing so allows to go beyond previous results only hinging around considering partial derivatives matrices which turn out to be isolate slices of the Hankel matrix.

We later explain in Section 4.3 how to extend the study to the commutative case. We know that polynomials f and f are equal up to associativity, which provides linear relations among the coefficients of H f .

The bulk of the technical work is to reorganize the rows and columns of H f in order to decompose it into blocks which may be identified as partial derivative matrices with respect to some

subsets A 1 , A 2 , • • • ⊆ [d],
of some associative polynomials which depend on f and sum to f . The number and choice of these subsets depend on the parse trees of the circuit C. such that all parse trees of C span an interval at distance at most

δ from A. Then C has size at least rank (M A (f )) n -δ |PT (C) | -1 .
Proof. The proof relies on a better understanding of the structure of the Hankel matrix H = H f of a general non-associative polynomial f : Tree(X) → K.

More precisely, we organize the columns and rows of H in order to write it as a block matrix in which we can identify and understand the blocks in terms of partial derivative matrices of some non-commutative (but associative) polynomials which will eventually correspond to parse trees. In the following we refer to Using these partitions for trees and contexts, we may write H as a block matrix with blocks

H i,j = H | Tree i (X)×Context j (X) .
Using the finer refinement of contexts, we write block H i,j as a tower (recall that contexts label the rows of H) of sub-blocks

H p i,j , for p ∈ [j],
where

H p i,j = H | Tree i (X)×Context p j (X)
. We now focus on H p i,j , which we will further decompose into blocks that are partial derivative matrices of some homogeneous non-commutative polynomials on the interval [p, p + i -1].

As Tree i (X) is the set of trees with i leaves, it can be seen as all possible labeling of shapes with i leaves by variables in X. Hence, Tree i (X)

Tree i × X i Tree i × X [p,p+i-1] . Likewise, Context p j (X)
is the set of contexts with j leaves and on the p-th leave, which can be seen as Context p j (X) ,p+i-1] , where Context p j is the set of contexts of size j with no labels, except for a unique on the p-th leaf. We now let, for any shape s ∈ Tree i+j-1 , the non-commutative (but associative) homogeneous polynomial f s of degree i + j -1 be defined by

Context p j × X j-1 Context p j × X [1,i+j-1]\[p
f s : X i+j-1 → K u → f (s labelled by u)
Now, grouping the columns t ∈ Tree i (X) of H p i,j which correspond to the same shape s ∈ Tree i , and the rows c ∈ Context p j (X)

which correspond to the same shape (of context) r ∈ Context p j , we obtain a block matrix, in which the block indexed by (s, r) is

precisely the partial derivative matrix M [p,p+i-1] f r[s] .
In the following, we will be interested in non-associative polynomials f : Tree(X) → K which project to a given associative

f : X * → K, meaning that for each u ∈ X * , t∈Tree(X) label(t)=u f (t) = f (u).
In this setting, one can see the decomposition f = s∈Tree f s as a decomposition over parse trees of a circuit computing f , f s being the contribution of the parse tree s in the computation of f . We Let f : Tree(X) → K be the non-associative polynomial computed by C when it is seen as a non-associative circuit. For any shape s ∈ Tree d , let f s : X d → K be defined as previously. In particular, s∈PT(C) f s = f. With a shape s ∈ PT (C), we associate an interval I(s) spanned by s and such that dist(A, I(s)) ≤ δ. Then we have

have seen that if I = [p, p + i -1] is an interval such that s de- composes into s = r[s ] for (s , r) ∈ Tree i × Context p j ,
rank (M A (f )) = rank   s∈PT(C) M A (f s )   ≤ s∈PT(C) rank (M A (f s ))
by rank subadditivity such that all parse trees of C span an interval at distance at most

δ from A. Then C has size at least rank (M A (f )) n -δ d -2 .
Remark 4.3. Note that this is an important improvement since the number of parse trees can be up to about 4 d (as noticed in Remark 3.2). As we shall see in Section 5 the lower bounds we obtain using Theorem 4.1 match known results, while using Theorem 4.2 yields substantial improvements.

Before going on to the formal proof of Theorem 4.2, we start by giving a high-level interpretation of the techniques used to go from Theorem 4.1 to Theorem 4.2. Our aim is still to lower bound the rank of the Hankel matrix H = H f of some (unknown) nonassociative polynomial f , under the constraints that, for each u ∈

X * , t∈Tree(X) label(t)=u f (t) = f (u),
for some non-commutative (but associative) polynomial f : X * → K that we control. Given the form of our constraints, a natural strategy would be to sum some well chosen sub-matrices of H in order to obtain a matrix that depends only on f , which we could choose to have high rank.

As exposed earlier when proving Theorem 4.1, it is possible to decompose f as the sum of some f s 's, where s ranges over the shapes used by f , and then obtain partial derivative matrices of the f s 's with respect to interval spanned by s, as sub-matrices of H. If one can find a subset A ⊆ [d] such that each s spans an interval I(s) that is δ-close to A for some small δ, then one obtains a lower bound for polynomials f with high rank with respect to A.

This first method leads to Theorem 4.1 and it is already strong enough to prove several lower bounds. We believe that in many occurrences in the literature, when obtaining lower bounds involving a circuit decomposition and a partial derivative matrix with respect to a given partition of the set of positions [d], this is somehow the underlying method.

However, this method poorly makes use of the structure of H, since it may happen that some of the chosen sub-blocks are face to face with one another. A short illustration of this phenomenon is the following. Let

M =     A 1,1 A 1,2 A 2,1 A 2,2 C 1 C 2 B 1,1 B 1,2 B 2,1 B 2,2    
be a block matrix, for which one wants to obtain a lower bound on the rank, knowing a lower bound on rank i,j A i,j + B i,j , and with no assumption on the C i 's.

The previous method would go as follows:

rank (M ) ≥ max max i,j rank (A i,j ), max i,j rank (B i,j ) ≥ 1 8 i,j rank (A i,j ) + rank (B i,j ) ≥ 1 8 rank i,j A i,j + B i,j .
Note that we have lost a factor of 8, which is the number of small blocks that we wish to sum.

A more efficient method would consist in first summing rows and columns of M in order to put together the A's and the B's.

This would go as follows, for some matrices C 1 and C 2 ,

rank (M ) ≥ rank i,j A i,j C 1 C 2 i,j B i,j ≥ max rank i,j A i,j , rank i,j B i,j ≥ 1 2 rank i,j A i,j + B i,j .
By doing so, we have decreased the factor 8 to 2, which is the number of larger blocks.

Back to the Hankel matrix H, this corresponds to putting together the polynomials f s for which we have chosen the same spanned interval (this corresponds to d 2 larger blocks) instead of considering them separately (which corresponds to |PT (C) | smaller blocks). We now formalize this idea, using a total order to model the choice of intervals for convenience.

Lemma 4.4. Let f : Tree(X) → K be a non-associative noncommutative polynomial and let ≤ int be a total order on intervals of [d]. For any shape s, let I(s) be the smallest (with respect to ≤ int ) interval spanned by s. For any interval I, define a noncommutative associative polynomial by

f I : X * → K u → t∈Tree(X) label(t)=u I(shape(t))=I f (t).
Then, one has max I rank

(M I (f I )) ≤ rank H f .
We illustrate the definition of f I through a small example. Let t = ((xy)z), and assume [1, 2] is the smallest interval spanned by Let I = [p, p + i -1] be some fixed interval and j = d -i + 1.

t, that is, [1, 2] ≤ int {1}, {2}, {3}, [1, 3]. Then f (t) will contribute to f [1,2] (xyz) as label(t) = xyz and I(shape(t)) = [1, 2].
Let r ∈ Context p j be a shape of a context of size j and where is on the p-th leaf, let v be a node in r and let [a, b] be the interval spanned by v in r. We define the interval I v by

I v =      [a, b] if b < p [a, b + i -1] if a ≤ p ≤ b [a + i -1, b + i -1] if a > p,
The interval I v is to be seen as the interval of positions of the leaves that are descendants of v in some r[s ] where s is any element of Tree i . In particular, if v is the leaf labelled by in r, then

I v = I.
Likewise, for a node v of a (sub)shape s ∈ Tree i , we define

I v by I v = [a + p -1, b + p -1], where [a, b] is the interval spanned by v in s . Note that if v is the root of s then I v = I.
We may now define (we use order ≤ int on intervals)

C I = {r ∈ Context p j | I = min v node in r I v },
and

T I = {s ∈ Tree i | I = min v node in s I v }.
We extend these subsets to labelled trees and context in a straightforward fashion by defining

CI = {c ∈ Context p j (X) | shape(c) ∈ C I } and TI = {t ∈ Tree i (X) | shape(t) ∈ T I }.
Remark that for any t ∈ Tree(X) and u ∈ X * , one has label(t) = u and I = I(shape(t)) if and only if t = r[s] for some (s, r) ∈ TI × CI such that u = label(s) ⊗ I label(c).

We now consider the submatrix HI of H p i,j where the rows are restricted to CI and the columns to TI . In this matrix, we now sum the rows which are indexed by contexts with the same label, and the columns which are indexed by trees with the same label, to obtain matrix H I . Clearly, rank (H I ) ≤ rank H f . We finally prove that

H I = M I (f I ) . Indeed, let g ∈ X I X i and h ∈ X d\A X j . Then M I (f I ) (g, h) = t∈Tree(X) label(t)=g⊗ I h I(shape(t))=I f (t) = s∈ TI c∈ CI label(s)=g label(c)=h f (c[s]) = H I (g, h),
which concludes the proof of Lemma 4.4.

With Lemma 4.4 in hands, we are ready to prove Theorem 4.2.

Let f : Tree(X) → K be the non-associative polynomial computed by C when seen as a non-associative circuit. Let ≤ int be a total order on intervals of d such that I → dist(I, A) is non-decreasing.

In other words,

I 1 < int I 2 if and only if d(I 1 , A) < d(I 2 , A). Let f I : X d → K be given by f I (u) = t∈Tree(X) label(t)=u I(shape(t))=I f (t).
Then any interval I such that d(I, A) > δ is such that for every parse tree s ∈ PT (C), one has I = I(s), so f I = 0. Hence, we obtain rank We explain how to extend the notions of parse trees and the generic lower bound theorems to the associative commutative setting.

(M A (f )) = rank   M A   I interval of [d] f I     = rank     M A     I interval of [d] dist(A,I)≤δ f I         ≤ I interval of [d] dist (
Let X = X 1 X 2 • • • X d be a partition of the set X of variables. A monomial is set-multilinear with respect to the partition if it is the product of exactly one variable from each set X i , and a polynomial is set-multilinear if all its monomials are. appear exactly once as a label of a leaf.

Let C be a commutative circuit. We let f denote the commutative non-associative polynomial computed by C when it is seen as non-associative. A parse tree of C is any shape s ∈ T d for which there exists a monomial t ∈ Tree(X) whose coefficient in f is non-zero and such that s = shape(t). Formally, we let

PT (C) = shape(t) | f (t) non-zero ∩ T d .
Remark 4.7. Note that it may be the case that a circuit C computing a set-multilinear polynomial f computes a non-associative f such that f (t) = 0 for some non set-multilinear monomials t, provided their sums collapse to 0 in the associative setting. We do not count such shapes as parse trees (this explains the intersection with T d in the above definition), which leads to more general classes of circuits against which we shall obtain lower bounds. Given a shape s ∈ T d and a node v of s, we let s v denote the subtree rooted at v and A v ⊆ [d] denote the set of labels appearing on the leaves of s v . We say that A v is spanned by s.

Following the same roadmap as in the non-commutative setting we obtain the following counterpart of Theorem 4.1. We assume that the set of variables is partitioned into d parts of equal size n (this is a natural setting for polynomials such as the determinant, the permanent or the iterated matrix multiplication). In particular, it means that the polynomials we consider are of degree d and over nd variables. Proof. As this proof is an adaptation of that of Theorem 4.1, we concentrate on highlighting the necessary changes.

Let X = X 1 X 2 • • • X d denote the underlying partition. Previously, we grouped together (sub-)trees and (sub-)contexts which correspond to a given interval of positions. In the commutative setting, we instead group together the (sub-)trees and (sub-)contexts which correspond to a given subset of positions, where a position is now being given by its index in the partition. Proof. Again, we extend the ideas for the non-commutative setting to the commutative setting, and we reuse the notations of the proof of Theorem 4.2. As for proving Theorem 4.2, we mainly rely on a Lemma.

Lemma 4.10. Let f : Tree(X) → K be a non-associative commutative polynomial and let ≤ int be a total order on subsets of [d]. For any commutative shape s, let A(s) be the smallest (with respect to ≤ int ) subset spanned by s. For any subset A, define a commutative associative polynomial by

f A (u) = t∈Tree(X) label(t)=u A(shape(t))=A f (t). Then, one has max A rank (M A (f A )) ≤ rank H f .
The proof of Lemma 4.10 is very similar, yet a bit more pleasant than that of Lemma 4.4, since we no longer need to shift any interval. Formally, for A ⊆ [d] we define

T A = {t ∈ Tree A (X) | A

Applications

In this section we instantiate our generic lower bound theorems on concrete classes of circuits. We first show how the weaker version (Theorem 4.1) yields the best lower bounds to date for skew and small non-skew depth circuits. Extending these ideas we obtain exponential lower bounds for 1 2 -ε -unbalanced circuits, an extension of skew circuits which are just slightly unbalanced. We also adapt the proof to ε-balanced circuits, which are slightly balanced.

We then move on to our main results, which concern circuits with many parse trees, with lower bounds for both non-commutative and commutative settings.

Prior to that, we present a family of polynomials for which our lower bounds hold, and we state Lemma 5.1 which is used several times in our proofs.

High-Ranked Polynomials. The lower bounds we state below hold for any polynomial whose partial derivative matrices with respect to either a fixed subset A or all subsets have full rank.

Such polynomials exist for all fields in both the commutative and non-commutative settings, and can be explicitly constructed. For instance the so-called Nisan-Wigderson polynomial (Kayal et al. Proof. The proof relies on the following two easy observations. Fact 5.3. Any skew shape spans intervals of each possible size, and in particular, an interval of size 3d/4.

Proof. Let s ∈ Tree d be a skew shape, v 1 be its root, and for all i = 1 . . . d -2, v i+1 be the child of v i which is not a leaf. Then any of the two children of v d-2 is a leaf, so it spans an interval of size 1. Now for each i, v i spans an interval that includes I v i+1 and adds 1 to its size, so we easily conclude by induction. by applying Theorem 4.2 instead, but we find it remarkable that simply using a decomposition of H into blocks is enough to obtain such an exponential lower bound. We conclude the proof by applying Theorem 4.1, just as we did for skew circuits.

length smaller than 20p/3, so overall length is (20p/3)(k + 1) + k < 7kp as we initially assumed that k, p ≥ 30. This contradicts Fact 5.13.

We now consider the increasing sequence of intervals I v i 0 +20p/3-1 ⊆ In the second item, the bound 2 d 1-ε on the number of parse trees is to be compared to the total number of shapes of size d which is bounded by 2 2d as noticed in Remark 3.2. As explained in the introduction this means that we obtain superpolynomial lower bounds for any class of circuits which has a small defect in the exponent of the total number of parse trees. However, the generic lower bound theorems, namely Theorem 4.8 and Theorem 4.9, are not exactly the same, so we obtain two incomparable bounds. In the following lower bounds, the set-multilinear polynomials that we consider have their variables partitionned into Choosing appropriate values for δ and k and applying Theorem 4.8 (resp. Theorem 4.9) leads the first (resp. second) item.

I v i 0 +20p/3-2 ⊆ • • • ⊆ I v i
X = X 1 X 2 • • • X d with n = |X i | for all i.
(i) Choosing δ = d 1/3 and k = 2 d 1/3-ε , we have that k2 -αd/δ 2 = 2 d 1/3-ε -αd 1/3 < 1. Hence, picking a subset A ⊆ [d] of size d/2 such that any s ∈ PT (C) spans an interval I(s) at distance at most d/2 -δ from A, and applying Theorem 4.8 yields

|C| ≥ rank (M A (f )) n -(d/2-δ) k -1 = n d/2 n -(d/2-d 1/3 ) 2 -d 1/3-ε = 2 d 1/3 (log n-d -ε ) .
(ii) Choosing δ = d ε/3 and k = 2 d 1-ε , we have that k2 -αd/δ 2 = 2 d 1-ε -αd 1-2 3 ε < 1. Hence, picking a subset A ⊆ [d] of size d/2

and such that for all s ∈ PT (C), dist(s, A) ≤ d/2 -δ, and applying Theorem 4.9 yields

|C| ≥ rank (M A (f )) n -(d/2-δ) k -1 = n δ 2 -d 1-ε = n d ε/3 2 -d .

Discussion

We presented a new tool for proving lower bounds for arithmetic circuits in the form of the Hankel matrix. We obtained strong lower bounds both in the commutative and non-commutative set-

  is a new fresh variable (the hole) to be substituted by u. Moving to non-associative polynomials, a monomial is a tree whose leaves are labelled by variables. A context is a monomial over the set of variables extended with a new fresh one denoted and occurring exactly once. For instance (see Figure1.1) the composition of the monomial t = z((xx)y) with the context c = (xy)((z )y) is the monomial c[t] = (xy)((z(z((xx)y)))y).

H

  f are indexed by contexts and the columns by monomials, and the value of H f (c, t) at row c and column t is the coefficient of the monomial c[t] in f .

Figure 1 . 1 :

 11 Figure 1.1: On the left hand side the monomial t, in the middle the context c, and on the right hand side the monomial c[t].

1. 3 .

 3 Parse Trees. At an intuitive level, parse trees can be used to explain in what way a circuit uses the associativity rule. Consider the case of a circuit computing the (associative) monomial 2xyz. Since this monomial corresponds to two non-associative monomials: (xy)z and x(yz), the circuit may sum different computations, for instance 3(xy)z -x(yz), which up to associativity is 2xyz. We say that such a circuit contains two parse trees, corresponding to the two different ways of parenthesizing xyz.

Figure 1 .

 1 Figure 1.1 for an example. It can be read in both the ordered or unordered settings. Hankel Matrices. Let f be a non-associative polynomial. The Hankel matrix H f of f is the matrix whose rows are indexed by contexts and columns by monomials and such that the value of H f at row c and column t is the coefficient of the monomial c[t] in f .

Figure 2

 2 Figure 2.1: A depiction of the Hankel matrix of a non-associative polynomial f . Only one coefficient is displayed for clarity.

2. 2 .

 2 The Characterization. This section aims at proving the characterization stated in Theorem 2.4 below -the Hankel matrix H f exactly captures (upper and lower bounds) the size of the smallest circuit computing f -, extending Nisan's characterization of non-commutative ABPs to general circuits in the nonassociative setting. The result holds for both commutative and non-commutative settings, the proof being the same up to cosmetic changes.

Figure 2 .

 2 Figure 2.3 depicts a run in the circuit from Figure 2.2.

Figure 2

 2 Figure 2.3: A run ρ in the circuit on the left, over the monomial on the right. It has value -1.

  the set of addition gates of C. To bound the rank of the Hankel matrix H f by |C| = |V ⊕ | we show that H f can be written as the sum of |V ⊕ | matrices each of rank at most 1.

Figure 2

 2 Figure 2.4: A context c, and the contexts c 1 t 2 and c 2 t 1 .

Figure 2 .

 2 Figure 2.5 for a depiction.

Figure 2 . 5 :

 25 Figure 2.5: The context c = (((• • • (((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ) ), the tree t = ((• • • (((x ε 1 • x ε 2 ) x ε 3 ) x ε 4 ) • • • ) x ε d ) and their composition c[t].

  & Portier 2008; Arvind & Raja 2016; Lagarde et al. 2016; Saptharishi & Tengse 2017; Lagarde et al. 2018). Remark 3.2. Let C be a circuit computing a homogeneous polynomial of degree d. Then asymptotically, |PT (C) | ≤ 4 d . Indeed, the maximal number of parse trees corresponds to the number of ordered binary trees with d leaves which is the (d -1)-th Catalan number C d-1 . Asymptotically, one has C k ∼ 4 k k 3/2 √ π which implies the announced lower bound on the number of parse trees.3.2. Partial Derivative Matrices. We now introduce a popular tool for proving circuit lower bounds, namely, partial derivative matrices, originated from[START_REF] Hyafil | The Power of Commutativity[END_REF][START_REF] Nisan | Lower Bounds for Non-Commutative Computation (Extended Abstract)[END_REF]) and widely used and extended in subsequent works, see for example[START_REF] Nisan | Lower Bounds on Arithmetic Circuits Via Partial Derivatives[END_REF][START_REF] Dvir | Separating multilinear branching programs and formulas[END_REF][START_REF] Gupta | Approaching the Chasm at Depth Four[END_REF] Kayal et al. 2014a;[START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF][START_REF] Kumar | On the Power of Homogeneous Depth 4 Arithmetic Circuits[END_REF].For A ⊆ [d] of size i , u ∈ X d-i , and v ∈ X i , we define the monomial u ⊗ A v ∈ X d: it is obtained by interleaving u and v with u taking the positions indexed by [d] \ A and v the positions indexed by A. For instance x 1 x 2 ⊗ {2,4} y 1 y 2 = x 1 y 1 x 2 y 2 . Definition 3.3. Let f be a homogeneous non-commutative associative polynomial. Let A ⊆ [d] be a set of positions of size i.

♦

  Example 3.5. Let f = xyxy + 3xxyy + 2xxxy + 5yyyy and A = {2, 4}. Then M A (f ) is given below. We define a distance dist : P([d]) × P([d]) → N on subsets of [d] by letting dist(A, B) be the minimal number of additions and deletions of elements of [d] to go from A to B, assuming that complementing is for free. Formally, dist(A, B) = min{|∆(A, B)|, |∆(A c , B)|}, where ∆(A, B) = (A \ B) ∪ (B \ A) is the symmetric difference between A and B. This is illustrated in Figure 3.1.Remark 3.6. A similar looking notion of distance is also available in the current literature for commutative depth-4 lower bounds.This was first implicitly defined by[START_REF] Fournier | Lower bounds for depth 4 formulas computing iterated matrix multiplication[END_REF] and byKayal et al. (2014a), and later made explicit by[START_REF] Chillara | Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach[END_REF].

Figure 3 . 1 :

 31 Figure3.1: In this case, the symmetric difference is smaller when complementing one of the sets, so dist(A, B) is the cardinality of the hatched subset.

Proof.

  Without loss of generality, one may safely assume that dist(A, B) = |∆(A, B)| (by transposing the matrix M A (f ) if necessary). We prove the statement by induction on d = |∆(A, B)|. If d = 0, this is trivial since A and B are identical in this case. For the case d = 1, let us assume that A = B ∪{i} (the other case being very similar). We divide M A (f ) into horizontal blocks, one for each variable x, that we call M A (f ) x , corresponding to the monomials for which the position i is occupied by the variable x. Therefore the rank of M A (f ) is upper bounded by

  hence the result. If d > 1, we first find a set C such that |∆(A, C)| = 1 and |∆(C, B)| = d -1, and we conclude by applying the induction hypothesis and using the case d = 1.

  Figure 3.2 illustrates the occurrences of a subshape in a shape.

Figure 3

 3 Figure 3.2: A shape of size 11, in which three nodes v 1 , v 2 , v 3 span the same subshape. The corresponding spanned intervals are I v 1 = [3, 5], I v 2 = [6, 8] and I v 3 = [9, 11]. We display the position of each leaf for readability.

  ,b for some b 1 , . . . , b ∈ [d]. In particular, the M Iv i (Per) have non-zero columns with disjoint supports, so rank (M s ) = i rank M Iv i (Per) . We claim now that rank M Iv i (Per) = d , which leads to the announced formula. Indeed, any subset A of [d] of size corresponds to a block full of 1's in the matrix M Iv i (Per) in the following way: Per(u ⊗ Iv i w) = 1 whenever u is a monomial whose first indices are [d] \ I v i and the second indices are any permutation of [d] \ A, and w is a monomial whose first indices are I v i and the second indices are any permutation of A. Two such blocks have disjoint rows and columns, and these are the only 1's in M Iv i (Per). Moreover, there are d such sets A. Applied to s being a left-comb, Corollary 3.10 yields that the smallest ABP computing the permanent has size 2 d + d. Applied to s being a complete binary tree of depth k = log d, the size of the smallest UPT is Θ 2 d d .

4. 1 .

 1 General Roadmap. Let f be a (commutative or non-commutative) associative polynomial for which we want to prove lower bounds. Consider a circuit C which computes f , and let f be the non-associative polynomial computed by C. Our aim is, following Theorem 2.4, to lower bound the rank of the Hankel matrix H f .

  Now, assume that there exists a subset A ⊆ [d] which is at distance at most δ to each A i . Losing a factor of n δ on the rank through the use of Lemma 3.8 we reduce the aforementioned blocks of H f to partial derivatives with respect to A. Such matrices can then be summed to recover the partial derivative matrix of f with respect to A, yielding in the lower bound a (dominating) factor of rank (M A (f )).

4. 2 .

 2 Generic Lower Bounds in the Non-commutative Setting. Following the general roadmap described above, we obtain a first generic lower bound result. Theorem 4.1. Let f be a non-commutative homogeneous polynomial of degree d computed by a circuit C. Let A ⊆ [d] and δ ∈ N

Figure 4 .

 4 Figure 4.1 for illustration of the decompositions.

Figure 4

 4 Figure 4.1: Decomposing H as blocks H p i,j , which further decompose into partial derivative matrices. Here, I denotes the interval [p, p + i -1].

  which means that I is spanned by s, then M I (f s ) appears as a sub-matrix of H. s rank (M I (f s )) ≤ rank (H) . Now, we have all the necessary tools to prove Theorem 4.1.

≤

  s∈PT(C) n δ rank M I(s) (f s ) by Lemma 3.8 ≤ |PT (C) |n δ rank (H) by equation ( ) Since, by Theorem 2.4, rank (H) ≥ rank (M A (f )) n -δ |PT (C) | -1 is a lower bound on |C|, we obtain the announced result. The crux to prove Theorem 4.1 is to identify for each parse tree s of C a block in H f containing the partial derivative matrix M I(s) (f s ) where f s is the polynomial corresponding to the contribution of the parse tree s in the computation of f and I(s) is an interval spanned by s. However, we do not consider in this analysis how these blocks are located relative to each other. A more careful analysis of H f consists in grouping together all parse trees that lead to the same spanned interval. Aligning and then summing these blocks we replace the dependence in |PT (C) | by d 2 which corresponds to the total number of possibly spanned intervals of [d]. This yields Theorem 4.2. Theorem 4.2. Let f be a non-commutative homogeneous polynomial of degree d computed by a circuit C. Let A ⊆ [d] and δ ∈ N

  Proof. Our aim is to obtain M I (f I ) from H f , by first taking a sub-matrix, then adequately summing its rows and columns. The proof is summarized in Figure4.2.

Figure 4 . 2 :

 42 Figure 4.2: Decomposition of the Hankel matrix used in the proof of Lemma 4.4. Here, I = [p, p + i -1].

  A,I)≤δ rank (M A (f I ))by rank subadditivity≤ I interval of [d] dist(A,I)≤δ n δ rank (M I (f I )) by Lemma 3.8 ≤ d 2 n δ rank H f by Lemma 4.4which yields the announced lower bound.4.3. General Lower Bounds in the Commutative Setting.

Example 4. 5 .

 5 The permanent and the determinant of degree d are set-multilinear with respect to the partition X = X 1 X 2 • • • X d where X i = {x i,j , j ∈ [d]}. The iterated matrix multiplication polynomial is another example of an important and well-studied set-multilinear polynomial. ♦ Partial derivative matrices also make sense in the realm of setmultilinear polynomials.Definition 4.6. Let X = X 1 X 2 • • • X d , fbe a set-multilinear polynomial of degree d, and A ⊆ [d] be a set of indices. The partial derivative matrix M A (f ) of f with respect to A is defined as follows: the rows are indexed by set-multilinear monomials g with respect to the partition i / ∈A X i and the columns are indexed by set-multilinear monomials h with respect to the partition i∈A X i . The value of M A (f ) (g, h) is the coefficient of the monomial g • h in f . The notion of shape was defined by (Arvind & Raja 2016), and it slightly differs from the non-commutative setting because we need to keep track of the indices of the variable sets given by the partition from which the variables belong. More precisely, given a partition of X = X 1 X 2 • • • X d , we associate to any monomial t ∈ Tree(X) of degree d its shape shape(t) ∈ Tree d ([d]) defined as the tree obtained from t by replacing each label by its index in the partition. In particular if t is set-multilinear, then each element in [d] appears exactly once as an index in shape(t). Hence we let T d ⊆ Tree d ([d]) denote the set of trees such that all elements of [d]

  Theorem 4.8. Let f be a set-multilinear polynomial computed by a circuit C. Let A ⊆ [d] and δ ∈ N such that all parse trees of C span a subset at distance at most δ from A. Then C has size at least rank (M A (f )) n -δ |PT (C) | -1 .

  Formally, for A ⊆ [d], we let Tree A (X) = {t ∈ Tree(X) | the set of indices of variables labeling t is A}, and likewise, Context A (X) = {c ∈ Context(X) | the set of indices of variables (different from ) labeling c is A},and finallyH A = H | Tree A (X)×Context A c (X) .Now, grouping together the columns of H A which correspond to trees which have a given fixed shape s (recall that a commutative shape contains the index in the partition of each leaf), and the rows which correspond to contexts which have a given fixed shape of context r yields the partial derivative matrixM A f r[s ], where the (commutative, associative) polynomial f s is defined, for any commutative shape s, byf s (u) = f (s labelled by u),where the labeling respects the partition of X.Hence, rank (H) ≥ rank (M A (f s )) whenever A is spanned by s. The remainder of the proof exactly follows that of Theorem 4.1 and therefore we do not repeat it here.A notable difference with the non-commutative setting is that now parse trees no longer span intervals of [d] but subsets of [d]. As a consequence, if we follow the same technique as the one used to prove Theorem 4.2, we now groups together blocks corresponding to the same subset of [d] and therefore the multiplicative factor is now 2 -d as there are 2 d such subsets. This yields the following counterpart for Theorem 4.2. Theorem 4.9. Let f be a set-multilinear polynomial computed by a circuit C. Let A ⊆ [d] and δ ∈ N such that all parse trees of C span a subset at distance at most δ from A. Then C has size at least rank (M A (f )) n -δ 2 -d .

  2014b) -inspired by the notion of designs by Nisan and Wigderson (Nisan & Wigderson 1994) -has this property. In the commutative, set-multilinear setting, it is given by N W n,d = h∈Fn[z] deg(h)≤d/2 d i=1 x i,h(i) , where F n [z] denotes univariate polynomials with coefficients in the finite field of prime order n. In the non-commutative setting, we remove index i, and insist that the product d i=1 x h(i) is done along increasing values of i. The fact that there exists a unique polynomial h ∈ F n [z] of degree at most d/2 which takes d/2 given values at d/2 given positions exactly implies that the partial derivative matrix of N W n,d with respect to any A ⊆ [d] of size d/2 is a permutation matrix. This is then easily extended to any A ⊆ [d]. A-balanced subsets. The following combinatorial Lemma is widely used to derive our lower bounds. Intuitively, a subset B ⊆ [d] is far from a subset A ⊆ [d] of size d/2 whenever it is A-balanced, meaning that A ∩ B and A c ∩ B have roughly the same size. Lemma 5.1. Let A, B ⊆ [d] be such that |A| = d/2. Then d(A, B) = d/2 -|A ∩ B| -|A c ∩ B| . Proof. Let us first assume that |B ∩ A| ≥ |B|/2. This implies that |∆(A, B)| ≤ |∆(A c , B)|, so dist(A, B) = |∆(A, B)| = |A ∪ B| -|A ∩ B| = (|A| + |A c ∩ B|) -|A ∩ B| = d/2 -(|A ∩ B| -|A c ∩ B|) = d/2 -|A ∩ B| -|A c ∩ B| , where the last line also follows from the assumption that |B ∩ A| ≥ |B|/2. Now if |B ∩ A| < |B|/2, it suffices to replace A with A c in the previous proof to obtain the announced result. 5.1. Applications in the non-commutative setting. 5.1.1. Skew, Slightly Unbalanced, Slightly Balanced and Small Non-Skew Depth Circuits. We show how using Theorem 4.1 yields exponential lower bounds for four classes of circuits in the non-commutative setting. We adapt the ideas of (Limaye et al. 2016) into our newly introduced vocabulary and easily obtain the same exponential lower bounds for skew circuits. Straightforward generalizations lead to previously unknown exponential lower bounds on slightly unbalanced and slightly balanced circuits. Finally, we also adapt (and shorten) their proof of a lower bound on small non-skew depth circuits. In each of these four cases the use of our weaker theorem, namely Theorem 4.1 suffices. Skew Circuits A circuit C is skew if all its parse trees are skew, meaning that each node has at least one of its children which is a leaf. We let I mid = (d/4, 3d/4], which has size d/2. As a direct application of Theorem 4.1, we obtain the following result. Theorem 5.2. Let f be a homogeneous non-commutative polynomial of degree d and on n variables such that M I mid (f ) has full rank n d/2 . Then any skew circuit computing f has size at least 2 -d n d/4 .

Fact 5. 4 .

 4 Any interval of size 3d/4 is at distance at most (in fact, equal to) d/4 from I mid . Proof. Indeed, let I ⊆ [d] be an interval of size 3d/4. Then I mid ⊆ I (see Figure 5.1). Hence by Lemma 5.1, d(I, I mid ) = d/2 -|I ∩ I mid | -|I ∩ I c mid | = d/2 -|d/2 -(|I| -d/2)| = d/4.

Figure 5 . 1 :

 51 Figure 5.1: Any interval I of size 3d d is at distance d 4 from I mid .

I.

  Then, by Lemma 5.1, we have that dist(I, I mid ) = d/2 -|I ∩ I mid | -|I ∩ I c mid | = d/2 -|d/2 -(|I| -d/2)| = d -|I| < d/2 -εd/2. Assume now that I mid I. Then, either 3d/4 or d/4 + 1 does not belong to I. Both cases being symmetrical, we assume without loss of generality that 3d/4 / ∈ I. We let = |I ∩ I mid |. The current situation is depicted in Figure 5.2.

Figure 5

 5 Figure 5.2: Illustrating I and I mid when 3d/4 / ∈ I.

  0 (where the nodes u i 0 , u i 0 +1 , . . . , u i 0 +20p/3-1 are those given by Fact 5.14), which we simply denoteI 1 ⊆ I 2 ⊆ • • • ⊆ I 20p/3 . Each I i = [a i , b i ] contains 3kp, and |I i+1 | = |I i | + 1. We let n i = |I i ∩ A| and m i = |I i ∩ A c |.The assumption d(A, I i ) > d/2 -p/3 can be rephrased, thanks to Lemma 5.1, as|n i -m i | ≤ p/3. First, note that for all j < 6p, b j / ∈ {3(k + i)p + 2p + 1 | 1 ≤ i ≤ 3k}.Indeed, for such a j one would have|n j+2p/3+1 -m j+2p/3+1 | = |n j -m j | + 2p/3 + 1 > p/3 leading to a contradiction. Therefore, all the b j for j = 1, . . . , 6p -1 belong to [3(k + i)p + 2p + 2, 3(k + i + 1)p + 2p] for some 1 ≤ i ≤ 3k.Hence, m 6p-1 -m 1 ≤ 2p, which implies that n 6p-1 -n 1 ≥ 4p.

  |n 1 -m 1 | -|n 6p-1 -m 6p-1 | ≥ |n 6p-1 -m 6p-1 | -|n 1 -m 1 | ≥ n 6p-1 -m 6p-1 + m 1 -n 1 ≥ 4p -2pwhich leads to a contradiction and concludes the proof.5.1.2. Circuits withMany Parse Trees. We now turn our focus to k-PT circuits which are circuits with at most k different parse trees. We first start by a key technical lemma that works both in the non-commutative and commutative (later discussed in Section 5.2) settings. Balanced Subsets For s ∈ Tree d and X ⊆ [d], we define dist(X, s) = min {dist(X, A) | A spanned by s} .δ, that is, any s ∈ PT (C) spans an interval I(s) at distance at most d/2 -δ from A. Finally, we apply Theorem 4.1 to obtain|C| ≥ rank (M A (f )) n -(d/2-δ) k -1 = n d/2 n -(d/2-d 1/3 ) 2 -d 1/3-ε = 2 d 1/3 (log n-d -ε ) . (ii) Choosing δ = d ε/3 and k = 2 d 1-ε , we have that k2 -αd/δ 2 = 2 d 1-ε -αd 1-2 3 ε < 1,which again lets us choose A ⊆ [d] of size d/2 and such that for all s ∈ PT (C), dist(s, A) ≤ d/2 -δ. Now, applying Theorem 4.2 we obtain |C| ≥ rank (M A (f )) n -(d/2-δ) d -2 = n δ d -2 = n d ε/3 d -2 .

5. 2 .

 2 Applications in the commutative setting. Regarding application in the commutative setting, we again consider the class of k-PT circuits which are set-multilinear circuits with at most k different commutative parse trees. Recall from Section 4.3 that in the commutative set-multilinear setting, parse trees are shapes whose leaves are labelled by integers without repetition. In particular the number of parse trees is roughly bounded by d! (see Remark 4.11).Arvind and Raja (Arvind & Raja 2016) showed a superpolynomial lower bound for k-PT circuits computing set-multilinear polynomial for sublinear k (up to k = d 1/2-ε ). We improve this to superpolynomial k (up to k = 2 d 1-ε ).

Theorem 5. 19 .

 19 Let f be a set-multilinear commutative polynomial such that for all A ⊆ [d], the matrix M A (f ) has full rank. Let ε > 0. Then for large enough d,(i) any 2 d 1/3-ε -PT circuit computing f has size at least 2 d 1/3 (log n-d -ε ) ; (ii) any 2 d 1-ε -PT circuit computing f has size at least n d ε/3 d -2 .In particular, this lower bound is super polynomial when d is at most a polynomial in log n.Proof. Let C be a k-PT circuit computing f , and δ ≤ √ d. By union bound and Lemma 5.15 for the commutative setting,Pr A∼U ( [d] d/2 ) ∃s ∈ PT (C) , dist(A, s) > d/2s) > d/2 -δ ≤ k2 -αd/δ 2

  tings using generic decompositions of the Hankel matrix. A natural question is how far this approach can be pushed. The first remark is that the rank of the Hankel matrix is exactly the size of the smallest circuit computing a given (non-associative) polynomial, hence the potential loss can only be in analyzing the Hankel matrix. Limaye, Malod and Srinivasan[START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF]) defined a polynomial computed by a circuit of polynomial size but such that all partial derivative matrices have full rank: this shows that one cannot use our decomposition of the Hankel matrix to obtain strong lower bounds for the class of all circuits. This limitation is an invitation to get a deeper understanding of the Hankel matrix and to find other ways of decomposing it.On a different perspective, the Hankel matrix has been successfully used as a data structure for learning algorithms (in both supervised and unsupervised settings). It is tempting, using the characterization that we present in this paper, to construct algorithms for learning polynomials relying on the Hankel matrix as algorithmic representation.

  t 2

t may only be non-zero if deg(t) = deg(t 1 ) + deg(t 2 ), which we now prove. Since f is homogeneous of degree d, H t may be nonzero only on contexts c such that deg

Slightly Unbalanced Circuits A circuit C computing a homogeneous non-commutative polynomial of degree d is said to be α-unbalanced if every multiplication gate has at least one of its children which computes a polynomial of degree at most αd.

Theorem 5.6. Let f be a homogeneous non-commutative polynomial of degree d and on n variables such that M I mid (f ) has full rank n d/2 . Then any 1 2 -ε -unbalanced circuit computing f has size at least 4 -d n εd .

This result improves over a previously known exponential lower bound on 1 5 -unbalanced circuits [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF].

Proof. This is an adaptation of the proof of Theorem 5.2 about skew circuits. We now rely on these two observations, which respectively generalize Fact 5.3 and Fact 5.4: Proof. Let α denote ( 1 2 -ε) < 1/2 and let s ∈ Tree d be an α-unbalanced shape of size d. We let v 1 be its root, and v 2 be the child of v 1 which spans the largest interval, which has size

≤ αd, we set r = 2, and otherwise iterate for i = 3 . . . r until both children of v r span intervals of size ≤ αd. Now, if we choose v r+1 to be a child of v r , the cardinalities of the growing sequence of intervals Proof. Let s be an ε-balanced shape, and r be the root of s.

Let I = [1, b] be the interval spanned by the left child of r. Since s

which allows us to conclude using Theorem 4.1.

Note that is suffices to simply restrict the last multiplication in the circuit to be ε-balanced for the proof to carry on.

Small Non-Skew Depth Circuits A circuit C has non-skew depth k if all its parse trees are such that each path from the root to a leaf goes through at most k non-skew nodes, i.e., nodes for which the two children are inner nodes. We obtain an alternative proof of the exponential lower bound of [START_REF] Limaye | Lower Bounds for Non-Commutative Skew Circuits[END_REF]) on non-skew depth k circuits as an application of Theorem 4.1. In the rest of this section we assume that k ≥ 30, p ≥ 30 is some multiple of 3 and d = 12kp. We will make extended use of the

of size 6kp = d/2 which is better understood in We now state and prove some facts which then lead to a contradiction:

Fact 5.11. For every i ∈

Proof. Indeed, u i being at the left of the path to the leaf at position 3kp,

Fact 5.12. For every i ∈ [r], if u i is the right child of v i then

Proof. Likewise, we now have

Intuitively, a large interval in this zone must contain roughly twice as much elements from A c than from A, so they cannot be at distance close to the maximum d/2.

Let l be the number of blocks of the form

Finally, assume that l > 2. Then |A ∩ I u i | ≤ pl and |A c ∩ I u i | ≥ 2p(l -1). Therefore, using Lemma 5.1, d(A,

Fact 5.13. It must be that r ≥ 7kp.

by the I u i , which have size bounded by 5p (thanks to Fact 5.11 and Fact 5.12) and among which all but k may have size > 1 (as we consider a circuit of non-skew depth k), there must be at least 12kp -5kp = 7kp of them.

Fact 5.14. There is some index i 0 such that u i 0 , u i 0 +1 , . . . , u i 0 +20p/3-1 are all leaves in s.

Proof. Indeed, only k among the 7kp u i 's may not be leaves.

By contradiction assume that all blocks of consecutive leaves have

In the following, we let [d] d/2 denote the subsets of [d] of size d/2.

For a subset P ⊆ 2 [d] we write U (P) for the uniform distribution over P.

Recall that, following Lemma 5.1, if X ∈

The following lemma is a subtle probabilistic analysis bounding the number of subsets that are balanced over all subsets spanned by a given fixed shape s. This will later entail the existence of a subset which is close to all parses trees in PT (C), provided |PT (C) |

is not too large. It holds in both the non-commutative (in which it was originally proved) and the commutative settings.

where α is some positive constant.

We shall use an intermediate result from the aforementioned paper. Their proof (based on a greedy construction) can be read just as such in the commutative setting.

Lemma 5.16 (Subclaim 21 in [START_REF] Lagarde | Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees[END_REF]. Let s ∈ Tree d , and r, t be integers such that rt ≤ d/4. Then there exists a sequence u 1 , . . . , u r of nodes of s such that for all i ∈ [r],

We now give the proof of Lemma 5.16 in the commutative setting, noting that the proof in the non-commutative setting is a restricted version of the one we give, where spanned subsets of [d] are replaced by spanned intervals.

Proof. We pick t = δ 2 and r = d 4δ 2 , and apply Lemma 5.16 to obtain a sequence v 1 , ..., v r of nodes of s. Then we have:

The last inequality follows from the general fact, applied using

(E).

Following from there, we let E i , for i ∈ [r], be the event |X ∩ (2 [d] )

Pr X∼U (2 [d] )

In order to bound the terms Pr X∼U (2 [d] ) [E i | ∀j < i, E j ] we use the following consequence of the Central Limit theorem.

Fact 5.17. There exist β < 1 such that for all random variable Y following an unbiased binomial law of parameter n, and all interval

Then the event E i can be rephrased as having a random variable following an unbiased binomial law of parameter t = δ 2 sit in [-δ -e, δ -e] of size 2δ, which is bounded by β thanks to Fact 5.17. Hence,

for some positive constant α.

Superpolynomial lower bounds