Hervé Fournier

Claire Mathieu

Pablo Charles

Yassine, Simon Laurent

Clément Alessandro À Alexandre

Lucas

Alain Juhel

Jean Voedts

Alexandre Miquel

Daniel Hirschko

Stéphan Thomassé

Pascal Koiran

Jean-Florent Fabrice

Tot, Lucas Nicoo À Arnaud

Romain La

Mathilde, Mathieu Véronique Raphaël

Aux An- Ciens

Keywords: algebraic complexity, lower bounds, polynomial identity testing, arithmetic circuits, Lempel-Ziv, compression. iii complexité algébrique, bornes inférieures, test d'identité polynomiale, circuits arithmétiques, Lempel-Ziv, compression. v vi

This thesis explores two territories of computer science: complexity and compression. More precisely, in a rst part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three di erent types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity testing problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an in nite word compressible by LZ'78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name "one-bit catastrophe". We also give tight bounds on the maximal possible variation between the compression ratio of a nite word and its perturbation-when one bit is added in front of it.

Un immense merci à ma famille, et en particulier à mes parents, pour leur soutien inconditionnel et leurs conseils avisés depuis bon nombre d'années maintenant.

En n, merci à Anne d'être in niment patiente et de rayonner au quotidien. 1 Prononciation rapide non triviale.

xiii xiv

Prelude

« Par ma foi ! il y a plus de quarante ans que je dis de la prose sans que j'en susse rien, et je vous suis le plus obligé du monde de m'avoir appris cela. » Molière. Le Bourgeois gentilhomme.

Just as Monsieur Jourdain was surprised and delighted to learn that he had been using prose for years without knowing it, most of us are not conscious that we are instinctively practising computer science on a daily basis. Whenever you wonder if that very hard climbing route could even be physically feasible by a mere human being, you are trying to solve what is called a computability problem. You-a model of computation-try to solve a given task-climbing the route. After a proof that it is indeed the case-you, or a more experienced friend, nally climbed it!-, you might wonder if the huge number of moves you made were really necessary and try to decrease this number to be as close to the minimum theoretically attainable as possible, in order to save your energy next time. At that point, you changed the point of view from computability to algorithmics and complexity. Ultimately, you get an e cient way of climbing this route, and it is now the right time to explain your solution to someone else. If the sequence of moves you did was the following 2 xv then you would probably say "it consists of a sequence of "move right hand, move left foot, move left hand, move right foot" repeated 9 times", without enumeratingor so I hope, for your friend-the whole sequence move by move. Congratulation, this time, you just made what is called a compression: you described your action with a clever and compact method. This short and rather informal story introduced the two main territories studied in this thesis: complexity and compression.

In the rst part of this manuscript, we focus on complexity questions in a domain called arithmetic complexity, while in the second part we concentrate on compression questions with the study of a particular and well-used data compression method called Lempel-Ziv.

Part one: Non-commutative Arithmetic Circuits

The aim of complexity theory is to understand what are the problems we can solve with a limited amount of resources. These ressources are quite often time and space, as they are the most natural ones when dealing with computers. But these notions are not immutable and can be exempli ed in various ways depending on the model of computation and the measure that is suitable for what is wanted. Two examples among others: by "time", we can denote the number of steps of a Turing machine, but we can also denote the depth of a boolean circuit.

Arithmetic complexity is the algebraic analogue of boolean complexity with an algebraic avor. Boolean functions are replaced by multivariate polynomials, which are the core objects of the theory. The way we compute them is through a model called arithmetic circuits, the de nition of which is similar to that of boolean circuits and is stated later in this manuscript. The motivation for this is twofold: rst, the study of polynomial computations arises in many places in computer science and naturally leads to such questions, and second, by moving to a more structured world than boolean functions, it might be possible to use tools from mathematics like linear algebra, algebraic geometry, etc., to tackle the problem of nding good lower bounds, a problem known to be hard.

The contribution of this thesis to arithmetic complexity lies in the non-commutative setting, a world where variables do not commute. In this setting, we explore circuits that are restricted in the way they are allowed to compute monomials (a more precise de nition will be stated later in the manuscript, with the notion of parse trees). The results are of three di erent types:

• We give lower bounds for various models of non-commutative computations, that is, we show that some polynomials require a large number of arithmetic operations to be computed:

for circuits with a unique parse tree ("UPT circuits") through a measure xvi that characterises exactly their complexity. This extends a work by Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] for algebraic branching programs.

for circuits that allow up to an exponential number of parse trees ("rot-PT circuits" and "k-PT circuits"). The aim of this is to get lower bounds for models of computation that are closer to general non-commutative circuits.

for homogeneous formulas that allow slightly less parse trees than the maximum possible (that is, that allow up to 2 o(d) parse trees, where d corresponds to the degree of the polynomial) computing IMM n,da polynomial that corresponds to matrix multiplication and that is complete for the important model of computation called arithmetic branching programs. This makes some progress towards a separation between non-commutative formulas and algebraic branching programs, a famous open problem in the non-commutative setting.

• We provide deterministic polynomial time algorithms to solve the important white-box polynomial identity testing problem for some classes of circuits; that is, we design algorithms to decide e ciently whether a circuit within a given class computes the formal zero polynomial:

for UPT circuits, through two adapations and extensions of previous algorithms for algebraic branching programs, due to Raz and Shpilka [START_REF] Raz | Deterministic polynomial identity testing in non-commutative models[END_REF] and Arvind, Joglekar and Srinivasan [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF].

for constant sum of UPT circuits. This generalises a similar result that was obtained for sum of read once algebraic branching programs (ROABPs) by Gurjar, Korwar, Saxena and Thierauf [START_REF] Gurjar | Deterministic identity testing for sum of read-once oblivious arithmetic branching programs[END_REF].

• We construct a bridge between automata theory and arithmetic circuits.

More precisely, we show that non-commutative algebraic branching programs are equivalent to acyclic weighted automata over words, and that noncommutative unique parse tree circuits are equivalent to layered weighted automata over trees. Subsequently, this correspondence-together with the use of fundamental theorems from automata theory-allow us to derive some old and new tight lower bounds for some classes of non-commutative arithmetic circuits. Part two: Lempel-Ziv, a "One-bit catastrophe" but not a tragedy Data compression is the art of nding a concise bit description of the information in order to save storage resources or to reduce the use of the network bandwidth for example. All the methods are not equivalent, some are without loss of information-lossless-, as for the text, others slightly deteriorate the qualitylossy-as for musics or videos for example, in exchange for a better compression ratio.

Lempel-Ziv algorithms are among the most popular compression algorithms. They refer to a series of lossless techniques-all based on a notion of dictionary which is constructed during the compression process-that can work on any le format. Introduced by Abraham Lempel andJacob Ziv in 1977 and[START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF], starting with two methods called LZ'77 and LZ'78, they are widely used in practice as key ingredients in various places such as de ate, gif, gzip, etc, but were also the starting point of a long line of theoretical research-some references of which can be found in Chapter 7. Yet, their behavior and robustness are still not well understood. While it is reasonable to expect a certain stability from a data compression algorithm against small perturbation on the input, Jack Lutz, in the late '90s, asked the following: "When using LZ'78, is it possible to change the compression ratio of an in nite word by adding a single bit in front of it?". This question, known as "one-bit catastrophe" question was still unanswered.

The main contribution of this thesis to compression is to give a positive answer xviii to this question. But before proving that, we investigate the behavior of LZ'78 on nite words and get the following:

• We give an upper bound on the maximal variation possible between the compression ratio of a nite word and its variant-when one bit is added in front of it.

• We give constructions that show that the previous upper bound is tight up to a multiplicative constant.

A catastrophe for in nite word-that is, a compressible word that becomes incompressible after we add one bit in front of it-is then derived from the results on nite words.

Publications

The results presented in this thesis can be found in the following papers:

• Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 23:94, 2016

• Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 -Aalborg, Denmark, pages 41:1-41:14, 2017

• Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees (extended version). To appear in Computational Complexity

• Nathanaël Fijalkow, Guillaume Lagarde, and Pierre Ohlmann. Tight bounds using hankel matrix for arithmetic circuits with unique parse trees. Electronic Colloquium on Computational Complexity (ECCC), 25:38, 2018

• Guillaume Lagarde and Sylvain Perifel. Lempel-ziv: a "one-bit catastrophe" but not a tragedy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Jan- This part is dedicated to lower bounds for non-commutative arithmetic circuits.

• In Chapter 1, we introduce the standard de nitions related to arithmetic circuits that will be used throughout the entire part.

• Chapter 2 is a complete study of circuits with a unique parse tree ("UPT circuits").

• Chapter 3 shows lower bounds for circuits with up to an exponential number of parse trees ("rot-PT circuits" and "k-PT circuits").

• Chapter 4 makes progress towards a separation between formulas and algebraic branching programs in the non-commutative setting. More precisely, using similar ideas to that of Chapter 3, we show some lower bounds for formulas-with a restricted number of parse trees-computing the iterated matrix multiplication polynomial.

• Chapter 5 is devoted to deterministic and polynomial time algorithms for PIT-for UPT circuits, as well as for constant sum of UPT circuits-a decision problem closely related to lower bounds.

• Chapter 6 makes a bridge between some non-commutative classes of circuits and weighted automata. This bridge gives a way to derive or improve already known results in non-commutative lower bounds as consequences of theorems from automata theory based on Hankel matrices.

Chapter 1 Preliminaries

« O tôt matin du commencement ! O sou e du vent, qui vient Des rives nouvelles ! » Bertolt Brecht. La vie de Galilée.

Arithmetic complexity Arithmetic circuits

The most natural strategy to compute a target polynomial is to use the operations from the algebra F[X], that is + and ×, together with the use of the constants from the eld F. This strategy is exactly captured by arithmetic circuits. More formally:

De nition 1.1: Arithmetic circuit

An arithmetic circuit is an acyclic directed graph where gates of in-degree greater than zero are labeled by + or × and gates of in-degree zero, called the inputs of the circuit, are labeled by either a variable or a constant coming from F. Each gate Φ represents in the natural way a formal polynomial that is denoted by P Φ . The unique gate of out-degree zero is called the output of the circuit and we say that the polynomial computed (or represented) by the circuit is the polynomial computed at this gate; for a particular circuit C, this polynomial is denoted by P C .

The size of an arithmetic circuits is de ned as the number of wires. Sometimes, it will be more convenient to consider instead the number of nodes; in this case, we will explicitly mention that the measure we take is the number of nodes.

Observe that the two measures are equivalent up to a constant factor as long as the gates are of bounded fan-in. The depth of a circuit is the size of the longest path from the output to an input: this can be seen as a measure of how well you can parallelize the computation of the polynomial represented by your circuit.

What are we looking for?

The questions are mainly of two kinds:

• Polynomials' point of view "Given a polynomial f , is there a circuit that computes f with some properties on the circuit?" In particular, the lower bound question falls in this category: nd explicit 1 polynomials that require large circuits to be computed (i.e., the number of arithmetic operations needed to compute this polynomial is large). Large meaning most often superpolynomial in the number of variables and the degree of the polynomial. This is the quest of looking for intractable polynomials.

• Circuits' point of view Circuits can be used as a compact representation for polynomials since an arithmetic circuit C can compute a polynomial that has an exponential number of non-zero monomials in the size of C. See Figure 1.2 for an example. A natural question is: how to handle them e ciently; in others words: "Given a circuit C, does the polynomial computed by C satisfy a particular property?" Eg: Is the degree of the polynomial greater than 42? Is the polynomial divisible by x 7 -y, or by another polynomial also given by an arithmetic circuit? Of course, to answer this kind of questions, you can always develop explicitly the polynomial computed by the circuit but this would not yield an e cient algorithm since polynomial-sized circuits can represent polynomials with an exponential number of non-zero monomials, as the previous example shows. The most representative question that falls within this category is the famous polynomial identity testing problem (PIT): given a circuit C, decide if the polynomial computed by C is formally zero. PIT will be considered in more detail in Chapter 5

x 1 1 x 2 1 • • • x n 1 + + + × Figure 1
.2: Arithmetic circuit of size 3n that computes n i=1 (x i + 1), which is a polynomial with 2 n non-zero monomials.

But reality is cruel. Although the ultimate goal for the rst kind of questions is to nd explicit polynomials for which we can prove superpolynomial lower bounds against general circuits, the best up to now is the following theorem: Theorem 1.2: Baur and Strassen, 1983 For all n, d ∈ N, n i=1 x d i requires circuits of size Ω(n log d) to be computed.

The situation is not better for PIT, for which there is a polynomial time randomized algorithm that follows from the Schwartz-Zippel lemma but no subexponential time deterministic algorithm is known for general circuits.

In fact, these two questions (lower bounds and PIT) are strongly related; solving PIT is similar to killing two birds with one stone. Indeed, in 2003, Kabanets and Impagliazzo [START_REF] Kabanets | Derandomizing polynomial identity tests means proving circuit lower bounds[END_REF] proved a beautiful result showing-more or less-that "Derandomizing polynomial identity tests means proving circuit lower bounds". More precisely, a deterministic polynomial-time algorithm to solve PIT implies either a superpolynomial lower bound on the size of arithmetic circuits computing the permanenent or NEXP ⊂ P/poly. A pessimistic way to interpret this theorem is that this is also a hint that partially explains why PIT seems very hard to solve in P and out of reach so far: "because lower bounds are".

Restrictions

Although lower bounds for general circuits seem out of reach so far, by making some natural restrictions on the circuits, we sometimes obtain stronger lower bounds-even exponential ones. These restrictions are useful to better understand the computation of polynomials by capturing some models of computation that are more suitable for a particular situation. For example, in [START_REF] Jerrum | Some exact complexity results for straight-line computations over semirings[END_REF], it is proved that every monotone circuits (that is, arithmetic circuits that use only positive elements from an ordered eld, such as R) computing the permanent of an n × n matrix has size 2 Ω(n) .

The more the circuits are constrained, the easier it is to provide lower bounds and design good algorithms for PIT. We give below some of the restrictions that will be used in this manuscript, but notice that there are quite a lot of others such as multilinear circuits, syntactically multilinear circuits, monotone circuits, . . .

• Formulas Circuits where the underlying graph is a tree. Equivalently, a formula is a circuit where the fan-out of each gate is at most 1. Intuitively, this corresponds to polynomial computations where a computation step can be used at most one.

• Skew circuits Circuits where the × gates have at most one non input child.

• ΣΠΣ circuits Circuits of depth three, starting with a layer of + gates, then a layer of × gates, and a nal + gate.

• Constant depth circuits Circuits where the length of any path from the output to an input is bounded by a constant.

Interesting polynomials

Some polynomials receive more attention than others; a rst reason that explains this phenomenon is the fact that a polynomial can capture completely the "complexity" of an arithmetic class of polynomials/circuits; a second one is due to the important consequences that would follow from a large enough lower bound proof for them. Below is the presentation of three famous polynomials; we will see some others later in the manuscript.

• Determinant and Permanent

For X = {x 1,1 , x 1,2 , . . . , x 1,n , . . . , x n,1 , . . . , x n,n } a set of n2 variables, we de ne the determinant and the permanent as

DET n (X) = σ∈Sn sgn(σ) n i=1 x i,σ(i)
and

PERM n (X) = σ∈Sn n i=1 x i,σ(i)
where the sums are over all permutations σ of the set {1, 2, . . . , n} and sgn(σ) stands for the signature of the permutation σ. Although the two de nitions are very close, the permanent has much fewer properties than the determinant. The determinant has a beautiful geometric interpretation in terms of volumes, but the permnanent seems to have only a combinatorial avor. It is believed that the permanent is not computable by circuits of polynomial size, whereas it is well known that the determinant is computable by small circuits, for example by using the Gaussian elimination algorithm and deleting the divisions that appear in the process.

In fact, proving the two polynomials are of distinct complexity can roughly be seen as an algebraic variant of the famous P = NP? question, namely VP = VNP?

(i ∈ [d]) are distinct variables in X i . Let M = M 1 • M 2 • • • M d be the multiplication of the d matrices; each entry of M is a homogeneous polynomial of degree d from F[X]
. We de ne the polynomial IMM n,d to be the sum of the diagonal entries of M3 .

As we shall see later, this important polynomial is completely captured by the model of computation called Algebraic Branching Programs (ABPs in short).

Example 1.3

For n = 2, d = 3 and sets

X i = {x i 1,1 , . . . , x i 2,2 } IMM 2,3 (X 1 , X 2 , X 3 ) = Tr x 1 1,1 x 1 1,2 x 1 2,1 x 1 2,2 × x 2 1,1 x 2 1,2 x 2 2,1 x 2 2,2 × x 3 1,1 x 3 1,2 x 3 2,1 x 3 2,2 = Tr         2 i 1 =1 2 i 2 =1 x 1 1,i 1 x 2 i 1 ,i 2 x 3 i 2 ,1 2 i 1 =1 2 i 2 =1 x 1 2,i 1 x 2 i 1 ,i 2 x 3 i 2 ,2         = 2 i 1 =1 2 i 2 =1 x 1 1,i 1 x 2 i 1 ,i 2 x 3 i 2 ,1 + 2 i 1 =1 2 i 2 =1 x 1 2,i 1 x 2 i 1 ,i 2 x 3 i 2 ,2

Non-commutative setting

From now on, we work over the non-commutative setting, in which x 1 x 2 and x 2 x 1 are two distinct monomials. The motivation for this is twofold: rst, the study of polynomial computations over non-commutative algebras (e.g. when the polynomials are evaluated over the algebra of k × k matrices over F; or over any non-commutative eld such as the quaternions) naturally leads to such questions [START_REF] Chien | Algebras with polynomial identities and computing the determinant[END_REF][START_REF] Chien | Cli ord algebras and approximating the permanent[END_REF], and second, computing any polynomial non-commutatively is at least as hard as computing it in the commutative setting and thus, the lower bound question should be easier to tackle in this setting.

Non-commutative polynomials

We use X = {x 1 , . . . , x n } to denote the set of variables. Unless explicitly stated, we work over the algebra of non-commutative polynomials (also known as free algebra), written (F X , +, ×, .) -or just F X in short.

• F is a commutative eld.

• (F X , +, .) is the vector space of formal and nite linear combinations of strings (called monomials) over the alphabet X. Observe that x 1 x 2 and x 2 x 1 are two distinct monomials.

• × is a bilinear product de ned for two monomials m 1 and m 2 as their concatenation m 1 m 2 . It is then extended bilinearly to any pairs of polynomials from F X .

The set of monomials over the alphabet X is written M(X). Given a polynomial f and m a monomial, we say that m is a non-zero monomial if the coe cent associated to m in f is non-zero. Most often, α m will denote the coe cient associated to the monomial m.

Degree and related de nitions

The degree of a monomial m, written deg(m), is the length of the corresponding string. By extension, the degree of a polynomial f ∈ F X , written deg(f ), is the maximal degree of a non-zero monomial of f . For d ∈ N, M d (X) will denote the set of monomials of degree exactly d.

A polynomial is said to be homogeneous if all the non-zero monomials are of same degree. The homogeneous component of degree i of a polynomial f , written f [i] , is the sum of all monomials of degree i appearing in f . Example 1.4

M({x}) = {x i , ∀i ∈ N} M 3 ({x, y}) = {x 3 , x 2 y, xy 2 , y 3 , y 2 x, yx 2 , xyx, yxy} f = x 1 x 2 x 3 3 + x 2 1 + x 4 1 + x 2 x
3 is a non homogeneous polynomial of degree 5 with four non-zero monomials. Its homogeneous component of degree 2 is f [2]

= x 2 1 + x 2 x 3 . g = x 1 x 2 x 3 + x 3
1 is a homogeneous polynomial of degree 3.

j-product

The following notion will be useful to decompose and factor polynomials.

De nition 1.5: j-product of two polynomials

Given homogeneous polynomials g, h ∈ F X of degrees d g and d h respectively and an integer j ∈ [0, d h ], we de ne the j-product of g and h -denoted g × j h -as follows:

h 1 g h 2 j d g d h -j Figure 1
.3: j-product of two monomials g and h.

• If g and h are two monomials, then h is uniquely factorised as a product of two monomials

h 1 • h 2 , with deg(h 1 ) = j and deg(h 2 ) = d h -j.
In this case we de ne g × j h to be

h 1 • g • h 2 .
• The map is extended bilinearly to general homogeneous polynomials g, h. Formally, let g, h be general homogeneous polynomials, where g = g , h = i h i and g , h i are monomials of g, h respectively. For j ∈ [0, d h ], each h i can be factored uniquely into

h 1 i , h 2 i such that deg(h 1 i ) = j and deg(h 2 i ) = d h -j. And g × j h is de ned to be i h 1 i g h 2 i = i h 1 i gh 2 i . Observe that g × 0 h = g • h and g × d h h = h • g. Example 1.6 If g = x 1 x 2 2 and h = x 3 x 1 x 2 , then: g × 2 h = x 3 x 2 1 x 3 2 If g = x 1 x 2 x 3 + x 2 2 x 1 and h = x 3 x 2 + x 2 2
, then:

g × 1 h = x 1 x 2 x 3 × 1 x 3 x 2 + x 1 x 2 x 3 × 1 x 2 2 + x 2 2 x 1 × 1 x 3 x 2 + x 2 2 x 1 × 1 x 2 2 = x 3 x 1 x 2 x 3 x 2 + x 2 x 1 x 2 x 3 x 2 + x 3 x 2 2 x 1 x 2 + x 3 2 x 1 x 2 1.2.

Non-commutative circuits

In order to capture non-commutativity, we need to slightly change our model of computation. A non-commutative arithmetic circuit is an arithmetic circuit where the children of any multiplication gate have been ordered. In this way, a non-commutative arithmetic circuit represents a non-commutative polynomial: the polynomial computed by a × gate is the product of the polynomials computed by its children, where the product is taken in the given order. Further, unless mentioned otherwise, we allow both + and × gates to have unbounded fan-in and + gates to compute arbitrary linear combinations of their inputs (the input wires to the + gate are labelled by the coe cients of the linear combination). The size of a circuit will be the number of edges. We always assume that the output gate is a + gate and that the input gates feed into + gates. We also assume that + and × gates alternate on any path from the output gate to an input gate. The reason for this is that any circuit can be converted to one of this form with at most a constant-factor blow-up in size and depth; however, it will be more convenient to work with circuits of this form.

Homogeneity

Most often, our circuits and formulas will be homogeneous in the following sense. De ne the formal degree of a gate in the circuit as follows: the formal degree of an input gate is 1, the formal degree of a + gate is the maximum of the formal degrees of its children, and the formal degree of a × gate is the sum of the formal degrees of its children. We say that a circuit is homogeneous if each gate computes a homogeneous polynomial and any gate computing a non-zero polynomial computes one of degree equal to the formal degree of the gate. Note, in particular, that every input node is labelled by a variable only (and not by constants from F).

Homogeneity is not a strong assumption on the circuit thanks to the following well known lemma (stated here for multiplication fan-in 2, but any circuit can be converted to have this additional property with a small blow-up in size and by possibly increasing logarithmically the depth).

Lemma 1.7: Homogenization

Any homogeneous polynomial of degree d computed by a non-commutative circuit C of size s with × fan-in 2 can be computed by a homogeneous circuit of size O(s.d 2 ).

Proof. We construct a homogeneous circuit C for f as follows.

• The gates of C are denoted by pairs of the form (Φ, i). For each gate Φ ∈ C and for each i ∈ [0, d], we add a gate (Φ, i) to the circuit C . We then add edges and additional gates in such a way that P (Φ,i) will be the homogeneous component of degree i of the polynomial computed by Φ in the circuit C, namely

P [i] Φ . If Γ is the output gate of C, then (Γ, d) is the output gate of C .
• Edges:

-If Φ ∈ C is an addition gate with children Ψ 1 , . . . , Ψ t , then for each i, (Φ, i) is an addition gate with children (Ψ 1 , i), . . . , (Ψ t , i).

-If Φ ∈ C is a multiplication gate with children Ψ 1 , Ψ 2 (in this order), then P

[i] Φ = j≤i P (Ψ,j) × P (Ψ,i-j) . Therefore, we set (Φ, i) to be an addition gate. We then add i + 1 multiplication gates to the circuit, each corresponding to one of the i + 1 products P (Ψ,j) × P (Ψ,i-j) , and we add these gates as children of (Φ, i).

By induction, it is easy to see that C computes f and is of size O(s.d 2 ).

Parse trees restriction

If we pretend the multiplication to be non associative, a non-commutative monomial can be computed in di erent ways that depend on how the parentheses are set. For example, if we restrict the fan-in to be 2, the monomial x 1 x 2 x 3 x 4 can be basically computed by ve di erent non-commutative circuits, one for each of the following possible setting of the parentheses:

• (x 1 • x 2 ) • (x 3 • x 4 ) • (x 1 • (x 2 • x 3 )) • x 4 • x 1 • ((x 2 • x 3 ) • x 4 ) • ((x 1 • x 2 ) • x 3 ) • x 4 • x 1 • (x 2 • (x 3 • x 4 ))
see Figure 1.4. Often, the circuits we consider will be restricted in the ways they are allowed to compute monomials. The reason for this is a decomposition lemma of the polynomials according to monomials computation, see Lemma 1.8; although quite trivial, this decomposition is at the core of many others, more complex ones, that will arise in this thesis.

To make this precise we need the notion of a "parse tree" of a circuit, which has been considered in many previous works [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][START_REF] Malod | Characterizing valiant's algebraic complexity classes[END_REF].

Parse trees

Fix a homogeneous non-commutative circuit C. A parse formula of C is a noncommutative formula C obtained from C as follows:

x 1 x 2 x 3 x 4 × × × x 1 x 2 x 3 x 4 × × × x 1 x 2 x 3 x 4 × × × x 1 x 2 x 3 x 4 × × × x 1 x 2 x 3 x 4 × × × Figure 1.4:
Five essential ways to compute x 1 x 2 x 3 x 4 by non-commutative arithmetic circuit with only × gates of fan-in 2.

• Corresponding to the output + gate of C, we add an output + gate to C ,

• For every + gate Φ added to C corresponding to a + gate Φ in C, we choose exactly one child Ψ of Φ in C and add a copy Ψ to C as a child of Φ . The constant along the wire from Ψ to Φ remains the same as in C.

• For every × gate Φ added to C corresponding to a × gate Φ in C and every wire from a child Ψ to Φ in C, we add a copy of Ψ to C and make it a child of Φ. The order of the various gates Ψ added to C is the same as the order of the corresponding wires in C.

Any such parse formula C computes a monomial (with a suitable coe cient) that is denoted by val(C ). As the following lemma shows-whose a proof can be foundd in [START_REF] Malod | Polynômes et coe cients. (Polynomials and coe cients)[END_REF] for example-the polynomial computed by C is the sum of all monomials computed by parse formulas C of C.

Lemma 1.8: Monomials decomposition

Let f ∈ F X be a polynomial computed by a non-commutative arithmetic circuit C. Then

f (X) = C val(C ),
where C runs over all parse formulas of the circuit C.

A parse tree of C is a rooted, ordered tree obtained by taking a parse formula C of C, "short circuiting" the + gates (i.e., we remove the + gates and connect the gates that were connected to it directly), and deleting all labels of the gates and the edges of the tree. See Figure 1.5 for an example. Note that in a homogeneous circuit C, each such tree has exactly d leaves, where d is the degree of the polynomial computed by C. We say that the tree T is the shape of the parse formula C .

x 1 x 2 x 3 x 4 + x 1 × x 4 × × + 3 2 7 x 2 x 4 + + x 1 × x 4 × + 7 × + + + × + + × x 1 x 2 x 3 x 4 3 2
Figure 1.5: First row: from left to right, a non-commutative arithmetic circuit and two parse formulas in the circuit. Second row: the corresponding parse trees. To simplify the picture, the constant 1 has not been depicted along some edges. Also we have not introduced + gates between the two layers of × gates; the reader should assume that the edges between the two layers carry + gates of fan-in 1.

The process that converts the parse formula C into T associates to each internal node of T a multiplication and an addition gate of C and to each leaf of T an input and an addition gate of C . See Figure 1.6.

Let T be a parse tree of a homogeneous circuit C with d leaves. Recall that a pre-order traversal of a tree visits rst the root, and then recursively traverses The type of v is de ned to be type(v) := (deg(v), pos(v)). (The reason for this de nition is that in any parse formula C of shape T , the monomial computed by the addition gate, multiplication gate or input gate corresponding to v in C computes a monomial of degree deg(v) which sits at position pos(v) w.r.t. the monomial computed by C . See Figure 1.7). We also use I(T ) to denote the set of internal nodes of T and L(T ) to denote the set of leaves of T .

The set of parse trees that can be obtained from parse formulas of C is denoted T (C). We say that a homogeneous non-commutative arithmetic circuit is a Unique Parse Tree circuit (or UPT circuit) if |T (C)| = 1 (this is equivalent to the de nition of unambiguous circuits we have introduced in [START_REF] Lagarde | Non-commutative computations: lower bounds and polynomial identity testing[END_REF]). More generally if |T (C)| ≤ k, we say that C is a k-PT circuit. Finally, if T (C) ⊆ T for some family T of trees, we say that C is T -PT. Similarly, we also de ne UPT formulas, k-PT formulas and T -PT formulas. If C is a UPT circuit with T (C) = {T }, we say that T is the shape of the circuit C. Remark 1.9

We can interpret some classes using this new framework. For example:

• Algebraic Branching Programs can be proved to be equivalent to UPT circuits for which the shape is a comb a .

• Skew circuits are equivalent to circuits for which the shapes can be all possible rotations of a comb.

• General circuits are circuits for which the shapes are unrestricted.

a A comb is a tree of this form .

Lower bound techniques 1.4.1 High level idea

The main known lower bounds in arithmetic complexity are quite often a consequence of the following (high level) steps:

1. De ne a measure on polynomials µ : F X → R. This measure is extended to circuits: µ(C) := µ(P C ).

2.

Prove that the polynomials computed by a class of circuits C are of low measure (typically, polynomial in the size of the circuits). In symbol:

∀C ∈ C, µ(C) = |C| O(1) .
3. Give a polynomial p of high measure.

Then, use the observation that a circuit C ∈ C computing p satis es µ(C) = µ(p), therefore |C| O(1) ≥ µ(p). If the measure of p is large enough, this process provides an interesting lower bound on the size of any circuit of the class C computing p.

Choice of the measure

Ideally, µ should be a good approximation of the "true" complexity of our polynomials, against general circuits. Such requirements seem out of reach so far. Instead, the measures used in practice are somehow weaker but more manipulable. Most often, given a class of circuits C, a decomposition lemma for polynomials computed by circuits in the class is given: ∀C ∈ C, P C = k i=1 f i , where f i are simpler polynomials and k a parameter related to the size of C. This decomposition paves the way to de ning a well tted measure. Indeed, a natural strategy is to de ne µ such that:

• µ(f ) is small for all simple polynomials f coming from the decomposition.

• µ is subadditive. That is, ∀f, g ∈ F X , µ(f + g) ≤ µ(f ) + µ(g).
• The polynomials for which we want lower bounds are of µ-measure reasonnably high.

Subadditivity gives the point 2. that was stated in the high level strategy. Indeed, for a polynomial p, we then have:

µ(p) = µ(C) ≤ k i=1 µ(f i )
From this, one can usualy deduce a lower bound on k; but k being related to the size of C, we get lower bound on the size of any C ∈ C computing p.

Partial derivative matrix

Go back to Nisan

In an in uential result, Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] made progress on the problem of proving lower bounds for non-commutative circuits by proving exponential lower bounds on the size of non-commutative formulas, and more generally non-commutative algebraic branching brograms (ABPs), computing the determinant and permanent (and also other explicit polynomials). 4 The method used by Nisan to prove this lower bound can also be seen as a precursor to the method of partial derivatives in arithmetic circuit complexity (introduced by Nisan and Wigderson [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF]), variants of which have been used to prove a large body of lower bound results in the area [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF][START_REF] Shpilka | Depth-3 arithmetic circuits over elds of characteristic zero[END_REF][START_REF] Gupta | Approaching the chasm at depth four[END_REF][START_REF] Kayal | An exponential lower bound for homogeneous depth four arithmetic formulas[END_REF][START_REF] Kumar | On the power of homogeneous depth 4 arithmetic circuits[END_REF].

Given a homogeneous polynomial f of degree d over a set X of n variables, Nisan considers the matrix M [f ] of size n d/2 × n d/2 whose rows and columns are indexed by monomials of degree d/2 each, where the (m 1 , m 2 )th entry of M [f ] is the coe cient of the monomial m 1 m 2 in f . The measure of a polynomial is then the rank of this matrix.

Nisan then proved that any polynomial computed by a formula (or an ABP) must be of relatively small rank, that is polynomial in the size of the formula (or the ABP). But it is pretty easy to see that interesting polynomials such as the determinant or the permanent are of high rank.

Here, we follow the extension of Nisan's measure that was introduced in [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF], where the more general family of matrices

M Y [f ] where Y ⊂ [d] is of size d/2 and (m 1 , m 2 )th entry of M Y [f ]
is the coe cient of the unique monomial m such that the projection of m to the locations in Y gives m 1 , and the locations outside gives m 2 . The formal and precise de nition is stated below. This time, the hard part will be to nd good subsets Y which make the rank of the polynomials computed by an arithmetic class of circuits small. Such subsets Y can therefore be seen as weaknesses for the considered class of circuits.

Generalisation

Here we recall some de nitions from [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] and [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF]. Let Π denote a partition of

Consider X = {x 1 , x 2 } and f = 3x 1 x 3 2 + x 1 x 2 x 2 1 + 7x 2 x 2 1
x 2 a homogeneous polynomial of degree 4. Let us consider also the two partitions Π 1 = ({2, 4}, {1, 3}) and Π 2 = ({2, 3, 4}, {1}). Then we have:

M [f, Π 1 ] = x 2 1 x 1 x 2 x 2 x 1 x 2 2       0 0 0 0 x 2 1 0 0 7 0 x 1 x 2 1 0 0 0 x 2 x 1 0 3 0 0 x 2 2 and M [f, Π 2 ] = x 1 x 2                       0 0 x 3 1 0 7 x 2 1 x 2 0 0 x 1 x 2 2 3 0 x 3 2 0 0 x 2 2 x 1 1 0 x 2 x 2 1 0 0 x 1 x 2 x 1 0 0 x 2 x 1 x 2
We will use the rank of the matrix M [f, Π]-denoted rank(f, Π)-as a measure of the complexity of f . Note that since the rank of the matrix is at most the number of rows, we have for any

f ∈ F X rank(f, Π) ≤ n |Y | .
De nition 1.12: Relative Rank

Let f ∈ F X be
Y in I g , that is, Y g = {k ∈ [d g ] | Y contains the kth smallest element of I g }; Π h = (Y h , Z h ) is de ned similarly with respect to I h . Denote |Y g |, |Z g |, |Y h |, |Z h | by d g , d g , d h , d h respectively.
In the above setting, we have a simple description of the matrix M [f, Π] in terms of M [g, Π g ] and M [h, Π h ]. We use the observation that monomials of degree |Y | = d g + d h are in one-to-one correspondence with pairs (m g , m h ) of monomials of degree d g and d h respectively (and similarly for monomials of degree |Z|). The following appears in [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF].

Lemma 1.13: Tensor Lemma Let f = g × j h be as above. Then, M [f, Π] = M [g, Π g ] ⊗ M [h, Π h ],
where ⊗ stands for the tensor product.

Corollary 1.14

Let f = g × j h be as above. We have rank(f, Π) = rank(g, Π g ) • rank(h, Π h ). In the special case where one of Y g or Z g is empty and one of Y h or Z h is empty, the tensor product is an outer product of two vectors and hence rank(f, Π) ≤ 1.

Sometimes, we will associate to any partition Π = (Y, Z) the string in {-1, 1} d that contains -1 in exactly the locations indexed by Y . Given partitions Π 1 , Π 2 ∈ {-1, 1} d , we now de ne ∆(Π 1 , Π 2 ) to be the Hamming distance between the two strings, or equivalently as

|Y 1 ∆Y 2 | where Π 1 = (Y 1 , Z 1 ) and Π 2 = (Y 2 , Z 2 ). Proposition 1.15 Let f ∈ F X be homogeneous of degree d and Π ∈ {-1, 1} d . Then, rank(f, Π) = rank(f, -Π), where -Π(i) = -1 × Π(i) for all i ∈ [d]. Proof. It follows from the fact that M [f, -Π] is the transpose of M [f, Π]. Lemma 1.16: Distance lemma Let f ∈ F X be homogeneous of degree d and Π 1 , Π 2 ∈ {-1, 1} d . Then, rank(f, Π 2 ) ≤ rank(f, Π 1 ) • n ∆(Π 1 ,Π 2 ) .
Proof. We prove this by induction on ∆(Π 1 , Π 2 ). The base case of the induction is the case that ∆(Π 1 , Π 2 ) = 0, i.e., Π 1 = Π 2 . In this case, the statement is trivial. Now consider when ∆(Π 1 , Π 2 ) = ∆ ≥ 1. Take any partition Π such that ∆(Π 1 , Π) = ∆ -1 and ∆(Π, Π 2 ) = 1. By the induction hypothesis, we know that rank(f, Π) ≤ rank(f, Π 1 ) • n ∆-1 and so it su ces to show that rank(f, Π 2 ) ≤ rank(f, Π) • n.

Assume that Π = (Y, Z) and

Π 2 = (Y 2 , Z 2 ). We know that ∆(Π, Π 2 ) = |Y ∆Y 2 | = 1. W.l.o.g. assume that Y = Y 2 \ {i} for some i ∈ [d] (the other case, when Y = Y 2 ∪ {i} is similar). Note that Z = Z 2 ∪ {i}.
Consider the matrix

M 2 := M [f, Π 2 ]
. We divide M 2 into n blocks as follows. For each x ∈ X, let M x 2 be the submatrix where we only keep the rows corresponding to monomials of degree |Y 2 | that contain the variable x in the location "corresponding" to i ∈ [d] (i.e., in the jth position where j is the index of i in Y 2 ). Clearly, we have rank(M 2 ) ≤ x∈X rank(M x 2 ). On the other hand, we also see that each M x 2 is a submatrix of M := M [f, Π]: namely, the submatrix obtained by only keeping the columns corresponding to those monomials that contain the variable x in the location corresponding to i (as above but w.r.t. Z). Hence, rank(M x 2 ) ≤ rank(M ) for each x. Hence, we see that rank(M 2 ) ≤ x∈X rank(M x 2 ) ≤ n • rank(M ) and this completes the induction.

A polynomial that is full rank w.r.t. all partitions Remember the high level steps given by Remark 1.4.1 in order to provide lower bounds. For us, we will have: Theorem 1.17

For any even d and any positive N ∈ N, there is an integer q 0 (N, d) such that the following holds over any eld F of size at least q 0 (N, d).

There is an explicit homogeneous polynomial F N,d ∈ F X of degree d over N = |X| variables such that for any balanced partition

Π = (Y, Z) of [d], rank(F N,d , Π) = N d/2 (equivalently, rel-rank(F N,d , Π) = 1)
. Further, F N,d can be computed by an explicit homogeneous noncommutative arithmetic circuit of size poly(N, d).

Sketch of the proof. Fix d an even integer and let N = |X| be the number of variables. Consider the complete graph where vertices are the elements of [d]; i.e., consider the graph G = ([d], [d] 2 ). Create also a new variable λ e for every edge e in G. Then, consider the following polynomial:

g(X, λ) = M perfect matching of G ( e∈M λ e ).g M (X), where g M (X) = w∈[n] d :w i =w j ∀{i,j}∈M
x w 1 x w 2 . . . x w d .

Then one can prove that:

• This polynomial is computable by a small arithmetic circuit (recursive construction).

• For any balanced partition Π, there is (at least) one perfect matching M Π for which M [g M Π , Π] is a permutation matrix, and hence is fullrank for this partition.

• As long as the underlying eld F is of size large enough, one can instantiate the variables λ to α ∈ F d(d-1)/2 such that for any balanced partition Π, rank(g(X, α),

Π) = rank(g M Π (X), Π) = N d/2 .
• A little argument then shows that if a polynomial is full-rank with respect to any balanced partition, then this polynomial is also full-rank with respect to any partition.

Therefore, to get lower bounds, we just need to take care of 2., as we can always take the polynomial given by Theorem 1.17 for a polynomial of high measure. However, sometimes, we will want a lower bound for a particular polynomial (such as IMM n,d in Chapter 4), in this case we will need to do a proof of 3. again.

Remark 1.18

Since Theorem 1.17 provides a polynomial which is full rank with respect to any partition, it means that the rank method alone is not enough to prove superpolynomial lower bounds against general circuits.

Table of separations

The following table presents the separations between classes of non-commutative circuits that are proved in this manuscript. Each row corresponds to a separation together with the polynomial that is used to show it.

Separation

Overview

This chapter focuses on UPT circuits, which are circuits with only one kind of parse tree, called the shape of the circuit. These circuits will be the core bricks of almost all decompositions in the next chapters. One reason for this is that we understand them almost completely, as this chapter shows. A parse formula corresponds to a monomial computation, therefore the class of UPT circuits can be seen as circuits for which each monomial is computed in the same way, given by the underlying shape. The results contained in this chapter can be seen as direct extensions of Nisan's work for ABPs [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF]-in which he provides an exact characterisation of the complexity of ABPs, and uses it to derive lower bounds for them. Indeed, one can easily observe that the class of polynomials computed by ABPs are exactly the ones computed by UPT circuits for which the underlying shape is a comb (recall that the de nition of a comb is given in Remark 1.9). Following Nisan, we show an exact characterisation of the complexity of UPT circuits and use it to give lower bounds for interesting polynomials such as the determinant or the permanent. This chapter is based on the following publication:

• Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 23:94, 2016

However, some notation and proofs have been modi ed with the intention of unifying and simplifying parts of the initial paper.

Multiplication fan-in restriction

First, we observe that any UPT formula or circuit can be converted to another (of possibly di erent shape) where each multiplication gate has fan-in at most 2.

Lemma 2.1

Let C be a UPT circuit (resp. formula) of size s (recall that the size is the number of edges) and shape T . Then there is a tree T and a UPT circuit (resp. formula) C of size ≤ 3s and shape T such that C computes the same polynomial as C and every multiplication gate in C has fan-in at most 2. (This implies that every internal node of T also has fan-in at most 2.) Further, there is a deterministic polynomial-time algorithm which, when given C, computes C as above.

Proof. We give the proof only for UPT circuits, since the transformation is the same in both cases. Let C a UPT circuit as in the statement. For any ×-gate Φ with k > 2 children Ψ 0 , . . . , Ψ k-1 , we replace Φ by the following gadget of 2(k -1) -1 gates Φ 0 , . . . , Φ 2(k-2) . For any i ∈ [0, k -3], Φ 2i is a multiplication gate with inputs Ψ i and Φ 2i+1 , and Φ 2i+1 is an addition gate with input Φ 2(i+1) . Finally, Φ 2(k-2) is a multiplication gate with inputs Ψ k-2 and Ψ k-1 . The new circuit is still in alternating layer form, and is clearly UPT because we apply the same process to any multiplication gate of fan-in strictly greater than 2. For any such gate, the number of edges in the corresponding gadget is 3k -4. Therefore, the number of edges in the nal circuit increases by at most three times the number of edges in the original circuit, so that the size of the circuit obtained by this process is ≤ 3s. The shape T of the new formula is simply the modi ed version of the shape T obtained by replacing the internal nodes of fan-in k > 2 by right combs with k leaves.

This completes the construction of C from C. The construction is easily seen to be implementable by a deterministic polynomial-time algorithm.

Remark 2.2

Without loss of generality, for the rest of this chapter and in order to simplify the proofs, we consider only UPT circuits with multiplication fan-in at most 2. Lemma 2.1 tells us this is not a strong assumption since we can e ciently transform our circuits in order to get this additional property, with a small blow-up in size that does not matter.

Normal form

Let C be a UPT circuit of shape T . We say that C is in normal form if there is a function v : C → T that associates to each gate Φ of the circuit a node v(Φ) ∈ T such that the following holds: if Φ is an input gate, then v(Φ) is a leaf; if Φ is a × gate with children Ψ 1 , . . . , Ψ t (in that order), then the nodes v(Ψ 1 ), . . . , v(Ψ t ) are the children of v(Φ) (in that order); and nally, if Φ is a + gate with children Ψ 1 , . . . , Ψ t (which are all × or input gates since we assume that + and × gates are alternating along each input to output path), then v

(Φ) = v(Ψ 1 ) = • • • = v(Ψ t ).
Intuitively, what this means is that in any unravelling of a parse formula containing a (multiplication or input) gate Φ to get the parse tree T , the gate Φ always takes the position of node v(Φ). See Figure 2.2 for an example.

Let C be either a UPT formula or a UPT circuit of shape T in normal form. We say that a + gate Φ in C is a (u, +) gate if v(Φ) = u ∈ T . Similarly, we refer to a × gate Φ in C as a (u, ×) gate if v(Φ) = u. For simplicity of notation, we also refer to an input gate Φ as a (u, ×) gate if v(Φ) = u. Note that the output gate is a (u 0 , +) gate where u 0 is the root of T .

We state and prove below some simple structural facts about UPT circuits.

The following proposition shows that it is always possible to transform a UPT circuit into a UPT circuit in normal form. It is for these circuits that we will be able to give an exact characterisation of the complexity. Proof.

+ × × + + + a b c 1 1 1 1 1 (a) A UPT circuit C not in canonical form. + × + + a b 1 1 1 (b) A parse
• Proof of 1.

Let C be a UPT formula with shape T . We want to prove that C is in normal form; this is equivalent to proving that for any multiplication gate Φ ∈ C and for any parse formula containing the gate Φ, the gate always takes the same position in T . Let D, D be any two parse formulas containing Φ. D (resp. D ) is a formula, therefore there is a unique path p (resp. p ) from the root to Φ in D (resp. D ). The crucial point is the following: as C is also a formula with D and D as subformulas, these two paths must be equal. By de nition, the position of Φ in T with respect to D is characterized by (deg(Φ), pos(Φ)); we recall that deg(Φ) is the degree of the monomial computed at the gate Φ in D and pos(Φ) equals 1 + the sum of the degrees of the monomials computed at the children of the multiplication gates along the path p which are on the left side of the path. As the formula is UPT, the monomials computed at a gate are all of same degree for any parse formulas containing the gate; moreover p = p so in both cases we consider the same gates in the de nition of (deg(Φ), pos(Φ)) in D or D so that the positions of Φ in T according to D or D are equal.

• Proof of 2.

The proof of this point relies on a careful inspection of the proof of [36, Lemma 2]. A circuit is called multiplicatively disjoint if each ×-gate has disjoint subcircuits as inputs. The result [36, Lemma 2] states that every circuit C of degree d can be turned e ciently into an equivalent multiplicatively disjoint circuit of size (|C| + d) O (1) .

The normal form is obtained by applying the algorithm to transform a general circuit into a multiplicatively disjoint circuit from [36, Lemma 2].

The resulting circuit has size ≤ 2d|C|.

Observe that it is not only the fact that the circuit is multiplicatively disjoint that makes the circuit in normal form, since Figure 2.2 shows a multiplicatively disjoint circuit not in normal form; the transformation itself is crucial.

For the sake of completeness, we recall the construction here (modi ed a little bit for the needs of non-commutativity).

For each gate Φ ∈ C of formal degree e, the new circuit The proof that D is multiplicatively disjoint and computes the same polynomial as C is given in [36, Lemma 2]. There it is also proved that, in D, all gates in the subcircuit de ned by a gate Φ k of formal degree e are clones whose index lie between k and k + e -1: we will call that the index property.

D contains distinct gates Φ 1 , Φ 2 , . . . , Φ d+1-e . Φ k is called a clone of index k of Φ. In C, if Φ is a ×-
We prove by contradiction that D respects the fact that in any unravelling of a parse formula containing a gate to get the parse tree, the gate always takes the same position in the (unique) parse tree. Let Φ j be an addition gate in D and D 1 and D 2 two parse formulas which contain Φ j but at two di erent positions in the shape. Let l 1 , l 2 , . . . , l a (resp. g 1 , g 2 , . . . , g b ) be the unique path in D 1 (resp. D 2 ) from the output gate to Φ k (thus l a = g b = Φ k ). Because Φ k does not share the same position in the shape, it means that there is a minimal c such that l c and g c are +-gates with di erent positions. It means that l c-1 and g c-1 are two ×-gates (because the circuit is constituted of alternating layers) and that l c and g c are inputs of l c-1 and g c-1 , one as left input, one as right input (let us say in that order). As the circuit is UPT, l c and g c must be of same degree e. g c-1 and l c-1 are clones of same index because the path from the output gate to these gates are identical. Let us say they are of index k. Thus l c is a clone of index k and g c is a clone of index k + e (because of the construction and the fact that one is a left input, the other a right input of the multiplication gate). Thanks to the index property, this means that the subcircuits de ned by l c and g c are clones whose index lies between k and k + e -1 for l c and between k + e and k + 2e -1 for g c . These two sub-circuits are thus disjoints, but this in contradiction with the fact that Φ j belongs to both of them.

Decomposition lemma

In this section, we show that polynomials computed by UPT circuits in normal form can be decomposed in a way that will prove useful later to get a characterisation of the complexity. Recall that the de nition of the j-product (× j ) is given in De nition 1.5 and that of type in Section 1.3.

Proposition 2.4: Decomposition for UPT circuits in normal form

If a polynomial f ∈ F X of degree d is computed by a UPT circuit in normal form with shape T , then for any v ∈ T of type (i, p), f can be written as f = kv j=1 g j × p h j , where: 1. k v is the number of (v, +) gates and g 1 , . . . , g v are the polynomials computed by these gates;

2. ∀j, deg(g j ) = i and deg(h j ) = d -i.

Proof. Let C be a UPT circuit in normal form computing the polynomial f . By Lemma 1.8, we have: f = C ∈S val(C ), where S is the set of all parse formulas of C. Let Φ 1 , . . . , Φ kv be the (v, +) gates, computing respectively the polynomials g 1 , g 2 , . . . , g kv . By de nition of the type of the node v, the g j are of degree i. For 1 ≤ j ≤ k v , let S j be the set of parse formulas containing the gate Φ j . Because a parse formula contains at most one (v, +) gate, we have S j ∩ S k = ∅ for j = k. Moreover, every parse formula must contain at least one (v, +) gate. Thus the S j are a partition of S: S = S 1 S 2 • • • S kv , where denotes the disjoint union. We can then rewrite the previous equality as

f = C ∈S val(C ) = kv j=1 C ∈S j val(C ). Fix j ∈ [1, k i,p ].
Consider the circuit C j (y) obtained by changing Φ j into an input gate labeled with a new variable y and deleting unused gates. Note that C j (g j ) = C (abusing notation and using the name of the circuit for the computed polynomial). Let F j be the set of parse formulas of C j containing the input gate Φ j . The value of any parse formula C ∈ F j is of the form y × p h C where h C is a monomial of degree (d -i). Then, by bilinearity of the j-product, V j (y) := C ∈F j val(C ) = y × p h j , where h j is a polynomial of degree (d -i). Note that C ∈S j val(C ) = V j (g j ) and therefore C ∈S j val(C ) = g j × p h j .

Exact characterisation of the complexity

We will use the number of +-gates of a UPT circuit in normal form as an estimate of its size. The following lemma shows that this is a good measure of overall size.

Lemma 2.5

Let C be a UPT circuit in normal form with s +-gates. Then we can transform C into a new UPT circuit in normal form, without changing the shape, with s +-gates and at most s 2 ×-gates.

Proof. Recall that the circuits are of × fan-in at most two. Denote by s i the number of +-gates on the i-th layer of C. If C has strictly more than s 2 ×-gates, then one layer i contains strictly more than s 2 i ×-gates. It means that two di erent ×-gates on the same layer perform the same computation; therefore one of them can be deleted and its output replaced by the output of the other one.

We will use this notion of size to get an exact expression of the complexity of computing a given polynomial with a UPT circuit in normal form. To do this, we create a complexity measure which is an extension for UPT circuits in normal form of the one given by Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF] for algebraic branching programs. For a given homogeneous polynomial f of degree d and each integer i ≤ d, Nisan de ned the partial derivative matrix M (i) (P ), which is a n d-i × n i matrix whose rows are indexed by monomials on X of degree (d-i) and columns by monomials of degree i. The entry (m 1 , m 2 ) of the matrix is de ned to be the coe cient of the monomial m 1 m 2 in P . We can rephrase this with our notation by saying that the matrix

M i (P ) is exactly the matrix M [f, Π i ], where Π i = ([1, i], [i + 1, d]).
Intuitively, the rank of the matrix M (i) (f ) is a measure of how "correlated" the pre x of length i of a monomial appearing in P is to the rest of the monomial. Small ABPs have "information bottlenecks" at each degree i, and hence the amount of correlation in the computed polynomial must be low. In our case the correlation will be between the pre x of degree p and the su x of degree (d -p -i) on the one hand, and the middle part of degree i on the other hand.

To make this more precise, we need to de ne a partition corresponding to a node in the shape of a UPT circuit computing a polynomial of degree d.

De nition 2.6

Given any integer d and any pairs (i, p) with i + p ≤ d, we de ne the partition

Π (i,p) of [d] so that Π (i,p) = (Y (i,p) , Z (i,p) ) where: • Y (i,p) = [p + 1, p + i] • Z (i,p) = [d] \ Y (i,p) = [1, p] ∪ [p + i + 1, d]
For notational convenience, if T is a tree with d leaves, then for any v ∈ T , we de ne Π v to be Π type(v) .

We can now express exactly the number of additions needed to compute a given polynomial by a UPT circuit in normal form (recall that the rank of a matrix

M [f, Π] is written rank(f, Π)).

Theorem 2.7

Let f be a homogeneous polynomial of degree d over the set X of variables and T a shape with d leaves. Then the minimal number of addition gates needed to compute f by a UPT circuit in normal form with shape T is exactly equal to

v∈T rank(f, Π v ).
Proof. Fix a UPT circuit C in normal form with shape T which computes f . Fix also v ∈ T a node of type (i, p) and let Φ 1 , . . . , Φ kv be all the (v, +)-gates in C. Let f = kv j=1 g j × p h j be the decomposition given by Proposition 2.4. To simplify notation, set also k = k v .

First step: decomposition of the matrix

M [f, Π v ] as L v R v . We show that M [f, Π v ] is the product of two "small" matrices L v and R v : • R v is a matrix of size k × n i . Rows are indexed by all gates Φ 1 , . . . , Φ k .
Columns are indexed by monomials m ∈ M i (X). R v t,m is the coe cient of the monomial m in the polynomial g t computed by the gate Φ t .

• L v is a matrix of size n d-i × k. Rows are indexed by all pairs (m 1 , m 2 ) ∈ M p (X) × M d-p-i (X). Columns are indexed by all gates Φ 1 , . . . , Φ k . L v (m 1 ,m 2 )
,t is the coe cient of the monomial m 1 m 2 in the polynomial computed by the circuit where Φ t is replaced by an input gate with value 1. That is:

L v (m 1 ,m 2 ),t is the coe cient of the monomial m 1 m 2 in the polynomial h t . One can easily verify that M [f, Π v ] = L v R v . Second step: lower bound. Since rank(f, Π v ) ≤ rank (L v ) ≤ k, the number k of (v, +)
gates must be at least rank(f, Π v ). Therefore, considering all nodes in T , we have just proved that the number of addition gates is at least v∈T rank(f, Π v ). Third step: upper bound. We prove that if rank(f, Π v ) < k, we can delete one (v, +)-addition gate in the circuit. We will possibly be increasing at the same time the number of ×-gates but, thanks to Lemma 2.5, this is innocuous.

If rank (L v ) = rank (R v ) = k, then, by a linear algebra argument, rank(f, Π v )
should also be k. Thus, either L v or R v is of rank strictly less than k.

If rank (R v ) < k, then one row (let us say, w.l.o.g., the rst row) of R v is a linear combination of the other rows. Going back to the meaning of the matrix, it means that the polynomial g 1 computed by the gate Φ 1 is a linear combination of the polynomials g 2 , . . . , g k computed by the gates Φ 2 , . . . , Φ k . Let us say g 1 = k i=2 c i g i for c i ∈ F. We construct a new circuit where Φ 1 is deleted. We denote by Ψ 1 , . . . , Ψ m the ×-gates which receive as input Φ 1 . In the new circuit, we create

(k -1) copies of Ψ 1 , . . . , Ψ m -namely Ψ 2 1 , . . . , Ψ 2 m , Ψ 3 1 , . . . Ψ 3 m , . . . , Ψ k 1 , . . . , Ψ k m . Ψ i
j does exactly the same computation as Ψ j , but instead of taking Φ 1 as input, it takes Φ i . Finally, an addition gate in the old circuit which took as input a Ψ j now takes k i=2 c i Ψ i j as input. If rank (L v ) < k, then one column (let us say, w.l.o.g., the rst column) of L v is a linear combination of the other columns. This means that there are constants c 2 , . . . , c k such that h 1 = k j=2 c j h j . Let Γ 1 , . . . , Γ m be all the coe cients on the input edges of Φ 1 coming respectively from multiplication gates Ψ 1 , . . . , Ψ m . In the new circuit, we delete Φ 1 and we add for all 1 ≤ l ≤ m, 2 ≤ j ≤ k an edge between Ψ l and Φ j with the coe cient c j Γ l . The new circuit computes the polynomial k j=2 (g j + c j g 1 ) × p h j . By bilinearity of the j-product, this is equal to

k j=2 g j × p h j + k j=2 (c j g 1 ) × p h j = k j=2 g j × p h j + g 1 × p k j=2 (c j h j ) = k j=2 g j × p h j + g 1 × p h 1 = f. Remark 2.8
When the shape is a comb (thus corresponding to an ABP), then p = 0 in the proof above, and M [f, Π v ] is the usual matrix M (i) of Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF]. Since the number of additions gates in the circuit corresponds exactly to the number of vertices in the ABP, our result is a direct extension of Nisan's.

Comparison with other classes 2.4.1 UPT vs. Skew-circuits

In this section we show that the classes of polynomials computed by polynomialsize UPT circuits on the one hand, and by polynomial-size skew circuits on the other hand, are incomparable.

De nition 2.9: Palindrome polynomial

Assume d is even. The palindrome of degree d over the set X of variables is:

P al d (X) := m∈M d/2 (X) m. m, where m is the mirror of m (e.g m = x 3 x 2 x 1 if m = x 1 x 2 x 3 ).

Remark 2.10

Observe that we can also de ne a palindrome polynomial when the integer d is odd, but this is not needed in this manuscript.

UPT ⊂ Skew

It is easy to construct a small UPT skew circuit for P al d (X) by using the following inductive formula:

P al d (X) = n i=1 x i P al d-2 (X)x i
We can then use the construction for P al d (X) to compute the square of the palindrome (P al d (X)) 2 = P al d (X) × P al d (X) with a UPT circuit as well. But note that [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF] shows that the square of the palindrome polynomial needs exponentialsize skew circuits: therefore, UPT is not included in Skew. Observe that this also shows that Skew is strictly included in rot-PT since UPT is included in rot-PT.

Skew ⊂ UPT

In the remainder of this section we construct a polynomial computable by a skew circuit of polynomial size but not by UPT circuits of polynomial size. The idea is the following: given a UPT circuit in normal form of degree d with any shape T , there is always a node v ∈ T for which type(v) = (i, p) where i ∈

[ d 3 , 2d 3 ], p ∈ [0, d -i] (see Lemma 2.11 below).
We then consider a polynomial such that the associated matrices

M [f, Π (i,p) ] have an exponential rank for all i ∈ [ d 3 , 2d 3 ], p ∈ [0, d -i].
According to the previous section, this means that computing the polynomial by UPT circuits requires at least an exponential number of gates.

Lemma 2.11

Given a UPT circuit in normal form computing a polynomial of degree d with shape T , there is always a node v ∈ T for which type(v) = (i, p)

satis es i ∈ [ d 3 , 2d 3 ], p ∈ [0, d -i].
Proof. It is su cient to prove that there is a +-gate of degree i ∈ [ d 3 , 2d 3 ]: the condition on p follows immediately from the de nition of the type. Let Φ be a ×-gate of degree > 2 3 d as close as possible to the leaves. Let Ψ 1 , Ψ 2 be the inputs of Φ and i, j their respective degree. We have i

+ j > 2d 3 , 1 ≤ i ≤ 2d 3 , 1 ≤ j ≤ 2d 3 . These conditions force i or j to be in [ d 3 , 2d 3 ].

De nition 2.12: Moving palindrome

The moving palindrome of degree n over the set X ∪ {w} of n + 1 variables is:

P al n mov (X, w) := l∈[0, 2n 3 ] w l P al n 3 (X)w 2n 3 -l ,
where w is a fresh variable (distinct from the X).

The rst proposition below is easy and is given without proof. The second is an application of our size characterization for UPT circuits in normal form.

Proposition 2.13 P al n mov (X, w) is computable by a skew circuit of size polynomial in n.

Sketch of the proof. The palindrome is computable by a small skew circuit. Therefore, by de nition, the moving palindrome is computable by a small sum of small skew circuits, hence a small skew circuit.

Proposition 2.14

Computing P al n mov (X, w) with a UPT circuit in normal form requires at least n n/6 gates.

Proof. Consider a UPT circuit in normal form C computing P al n mov . Thanks to Lemma 2.11, we know that there is always a node v in the shape for which the type (i, p)

satis es i ∈ [ n 3 , 2n 3 ], p ∈ [0, n -i].
To apply Theorem 2.7, it is enough to show that for all such (i, p), rank(P al n mov , Π (i,p) ) ≥ n n/6 . This will be possible since for each such type, there is a polynomial in the sum that de nes P al n mov which has a large rank and the other polynomials will not interfere.

Let us x a particular (i, p), i

∈ [ n 3 , 2n 3 ], p ∈ [0, n -i]. Because i ≤ 2n 3 we have p + (n -p -i) ≥ n 3 .
Then one of the two following cases occurs. Case p ≥ n 6 . In this case we show rst that

rank(P al n mov , Π (i,p) ) ≥ rank(w p-n 6 P al n 3 (X)w n-p-n 6 , Π (i,p) ).
Indeed by de nition,

M [P al n mov , Π (i,p) ] = l∈[0, 2n 3 ] M [w l P al n 3 (X)w 2n 3 -l , Π (i,p) ]; And note then that, if (a, b) is a coordinate of a non-zero coe cient of M [w p-n 6 P al n 3 (X)w n-p-n 6 , Π (i,p) ] and (a , b ) is a coordinate of a non-zero coe cient of M [w l P al n 3 (X)w 2n 3 -l , Π (i,p) ],
with l = p -n 6 , then a = a and b = b . Finally, observe that in this case, every row and column of M [w p-n 6 P al n 3 (X)w n-p-n 6 , Π (i,p) ] contains at most one non-zero coe cient and there are exactly n n/6 non-zero coe cients. Thus:

rank(P al n mov , Π (i,p) ) ≥ rank(w p-n 6 P al n 3 (X)w n-p-n 6 , Π (i,p) ) ≥ n n/6 . Case n -p -i ≥ n 6 .
With similar arguments, we have this time

rank(P al n mov , Π (i,p) ) ≥ rank(w p+i-n 6 P al n 3 (X)w 5n 6 -p-i , Π (i,p) ) ≥ n n/6 .

Remark 2.15

Observe that this implies that UPT is strictly included in rot-PT since Skew is included in rot-PT. Moreover, as the moving palindrome is computable by a small sum of small skew circuits, it is also computable by a small k-PT circuit. Hence UPT is strictly included in k-PT.

UPT vs. Determinant and Permanent

In this small section, we sketch the proof of lower bounds for the determinant and the permanent that follow from the characterisation of the complexity given in Section 2.3. First, recall the de nitions of the two polynomials:

PERM n = s∈Sn n i=1 x 1,s(1) • • • x n,s(n) and DET n = s∈Sn sgn(s) n i=1 x 1,s(1) • • • x n,s(n) .
To get lower bounds we need to estimate the ranks of certain matrices M [ ,

Π (i,p) ].
The following lemma is proved exactly in the same way as Lemma 2 in [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF].

Lemma 2.16

For all i ≤ n, p ≤ n -i, rank(PERM n , Π (i,p) ) = rank(DET n , Π (i,p) ) = n i .
We can now obtain the following lower bounds.

Theorem 2.17

Computing PERM n or DET n with a UPT circuit requires at least n n/3 gates.

Proof. By Lemma 2.11, there is a gate v in the shape for which type(v) = (i, p)

and i ∈ [ n 3 , 2n 3 ]
. By Lemma 2.7 and Lemma 2.16, the number of gates needed is at least rank

(DET n , Π v ) = n i ≥ n n/3 .

Chapter 3

Variations around parse trees restriction

Overview

Chapter 2 gives a pretty complete understanding of UPT circuits. But remember that the ultimate aim is to prove lower bounds for general circuits, and these ones can have an exponential number of distinct parse trees. Here, we try to get closer to this goal by increasing the number of parse trees that are allowed to appear in a circuit. We do this in two di erent ways: in Section 3.1, we give lower bounds for circuits with at most 2 d 1/4 unrestricted shapes ("2 d 1/4 -PT circuits"). Then, in Section 3.2, we extend previous work on skew circuits to give lower bounds for circuits with an exponential number of shapes; however, this time, the shapes are constrained from the fact they all come from a xed tree and all its rotations ("rotUPT circuits"). This chapter is based on the following publication:

Lower bounds for k-PT circuits

In this section, we show that any k-PT circuit computing a polynomial of degree d where k is subexponential in d cannot compute the polynomial F N,d from Theorem 1.17. We will show that if both k and the size of the circuit are subexponential in d, then there is a Π such that rel-rank(f, Π) < 1. For large enough elds F, Theorem 1.17 gives us a polynomial that is full rank w.r.t. all partitions and we thus get a lower bound for computing this polynomial by k-PT circuits.

Proof outline. We rst show that any k-PT circuit C of size s can be written as a sum of k UPT circuits C 1 , . . . , C k whose shapes are the di erent shapes that appear in C and whose sizes are at most s 2 . At this point, for each C i , Lemma 3.2 allows us to nd many partitions

Π i,1 , . . . , Π i,t such that rel-rank(C i , Π i,j ) is small for each i ∈ [k] and j ∈ [t]
. However, we would like to nd a common partition Π so that rel-rank

(C i , Π) is small for each i ∈ [t].
To do this, we use Proposition 1.15 and Lemma 1.16, which together imply that if a partition Π is somewhat close in Hamming distance to either Π i,j or -Π i,j for any j ∈ [t], then rel-rank(f, Π) is small as well. In fact, a close look at the parameters tells us that to obtain a superpolynomial lower bound, it su ces for the quantity min{∆(Π, Π i,j ), ∆(Π, -Π i,j )} to be somewhat smaller than the worst case, which is d/2. Our aim, therefore, is to choose a Π such that for each i ∈ [k], there exists a j ∈ [t] so that the above occurs.

A natural choice for such a Π is to choose a uniformly random Π = (Y, Z) of [d]. Analyzing the probability that min{∆(Π, Π i,j ), ∆(Π, -Π i,j )} is close to d/2 for each j ∈ [t] is a simple probabilistic problem that we solve below. As this probability is low, we obtain a lower bound.

We start with a decomposition lemma for k-PT circuits. The lemma is stated in slightly greater generality since it is used in later sections as well.

Lemma 3.1: Decomposition for k-PT circuits Let C be a k-PT circuit (resp. formula) of size s with T (C) = {T 1 , . . . , T k } computing f ∈ F X . Then there exist normal form UPT circuits (resp. formulas) C 1 , . . . , C k of size at most s 2 each such that T (C i ) = {T i } and f = k i=1 f i , where f i is the polynomial computed by C i .
Proof. Let C be as in the statement. We show how to construct k UPT circuits (resp. formulas) C 1 , . . . , C k of size at most s 2 , of shapes T 1 , . . . , T k respectively, computing f 1 , . . . , f k respectively such that each f i is equal to the sum of the monomials computed by all the parse formulas of C of shape T i . Given this, the polynomial f , which is equal to the sum of all monomials computed by all parse formulas of C, will be equal to k i=1 f i and the lemma will be proved.

Construction of C i .

• The gates of C i are denoted by pairs of the form (Φ, v). For each gate Φ ∈ C and for each node v ∈ V (T i ) such that deg(v) = deg(Φ), we initially add a gate (Φ, v) to the circuit C i .

• Edges:

-

If Φ ∈ C is an addition gate with children Ψ 1 , . . . , Ψ t , then (Φ, v) is an addition gate in C i with children (Ψ 1 , v), . . . , (Ψ t , v). -If Φ ∈ C is a multiplication gate with children Ψ 1 , . . . , Ψ t (in this or- der), then (Φ, v) is a multiplication gate with children (Ψ 1 , v 1 ), . . . , (Ψ t , v t ), as long as the children of v in T i are exactly v 1 , . . . , v t (in this order) with deg(v j ) = deg(Ψ j ) for each j. Otherwise, we label (Ψ, v) with 0.
-If Φ is an input gate labelled by x ∈ X and v a leaf node, then the gate (Φ, v) is also an input gate with the same label.

Notice that the size of C i is upper bounded by s 2 . Further, any parse formula that does not contain any of the nodes labelled 0 has shape T i .

We prove by induction (on any toplogical orderings of T i and C) that for any v ∈ V (T ) and Φ in C such that deg(Φ) = deg(v), the gate (Φ, v) in C i computes the sum of all parse formulas C of C starting at Φ with the shape T i [v], where T i [v] is the subtree of i rooted at v. This will prove that the output gate of C i computes the sum of the monomials computed by all the parse formulas of C of shape T i . This is clearly true for the leaves.

Take now any (Φ, v) in C i . We assume it is a multiplication gate (the other case is similar). Assume that the children of

Φ ∈ C are Ψ 1 , . . . , Ψ t and that the children of v ∈ T i are v 1 , . . . , v r . If either r = t or there is an a ∈ [t] such that deg(v a ) = deg(Ψ a )
, then there are no parse formulas starting at Φ of shape T i [v] and hence the gate (Φ, v) which is labelled with 0 computes the correct polynomial. So we now assume that r = t and deg(v

a ) = deg(Ψ a ) for each a ∈ [t].
Let us denote by S the set of parse formulas C of C starting at Φ with a shape T i [v], and S 1 (respectively S 2 , . . . , S t ) the set of parse formulas starting at the gates Ψ 1 (resp. Ψ 2 , . . . , Ψ t ) with a shape

T i [v 1 ] (resp. T i [v 2 ], . . . , T i [v t ]).
The set S is obtained by taking all possible combinations of parse formulas coming from S 1 , . . . , S t . In symbols

C ∈S val(C ) = t j=1 C ∈S j val(C )
If we denote by P (Ψ j , v j ) each polynomial computed by a gate (Ψ j , v j ) in C i , we get by induction hypothesis that

C ∈S val(S) = t j=1 P (Ψ j , v j ) and hence C ∈S val(S) = P (Φ, v) as wanted.
Finally, note that some of the leaves of the circuit are labelled by the constant 0. To eliminate this, we can repeatedly apply the following procedure. If Φ is labelled with 0 and feeds into a × gate Ψ, then remove Φ and all wires feeding into Ψ, and relabel Ψ with 0. If Φ is labelled with 0 and feeds into a + gate Ψ, then simply remove Φ and if Φ has no inputs left, then relabel it with 0. This process produces a UPT circuit with shape T i and size at most s 2 . Further, since each gate is already associated with a node of T in a natural way, the circuit C i is already in normal form.

We now analyze the probability that rank(C, Π) is close to full for a random partition Π of

Pr Π rank(f, Π) ≥ N d/2-b ≤ exp(-Ω(d/(b + c) 2 )).
Postponing the proof of the above lemma to Section 3.1.1, we show that it implies the following lower bound for homogeneous non-commutative circuits with few parse trees. Note that when the eld F is large enough, this proves a lower bound for F N,d from Theorem 1.17.

Theorem 3.3

Assume that N, d ≥ 2 are growing integer parameters with d being even. Let F ∈ F X be any polynomial such that for each balanced partition Π, rank(F, Π) = N d/2 . Then, for any constant ε ∈ (0, 1), any circuit that computes F and satis es

|T (C)| = k ≤ 2 d 1 3 -ε must have size at least or more than N d 1 3 -ε 2 . Proof. Let C be any circuit of size s ≤ N c for c = d 1/3-ε/2 with |T (C)| = k ≤ 2 d 1/3-
ε and computing f ∈ F X . We show that there is a balanced partition Π such that rank(f, Π) < N d/2 . This will prove the theorem.

To show this, we proceed as follows. Using Lemma 3.1, we can write

f = i∈[k] f i where each f i ∈ F X is computed by a normal form UPT circuit C i of size at most s 2 ≤ N 2c . Fix any i ∈ [k]. By Lemma 3.2, the number of partitions Π for which rank(f i , Π) ≥ N d 2 -c is at most 2 d • exp(-Ω(d/c 2 )). In particular, since the num- ber of balanced partitions is d d/2 = Θ( 2 d √ d ), we see that for a random balanced partition Π, Pr Π balanced rank(f i , Π) ≥ N d/2-c ≤ O( √ d) • exp(-Ω(d/c 2 )) ≤ exp(-d 1/3 ). Say f i is bad for Π if rank(f i , Π) ≥ N d/2-c
. By the above, we have

Pr Π balanced [∃i ∈ [k] s.t. f i bad for Π] ≤ k • exp(-d 1/3 ) ≤ 2 d 1/3-ε • exp(-d 1/3 ) < 1.
In particular, there is a balanced Π such that no f i is bad for Π. Fix such a balanced partition Π. By the subadditivity of rank, we have

rank(f, Π) ≤ i∈[k] rank(f i , Π) ≤ k • N d/2-c ≤ 2 d 1/3-ε • N d/2-c = N d/2 • exp(O(d 1/3-ε ) -Ω(d 1/3-ε/2 )) < N d/2 .
This proves the theorem.

Proof of Lemma 3.2

Notation. Recall from Chapter 1 that we identify each partition Π with an element of {-1,

1} d . Given partitions Π 1 , Π 2 ∈ {-1, 1} d we use Π 1 , Π 2 to denote their inner product: i.e., Π 1 , Π 2 := i∈[d] Π 1 (i)Π 2 (i). Note that the Hamming distance ∆(Π 1 , Π 2 ) is ∆(Π 1 , Π 2 ) = d 2 - 1 2 Π 1 , Π 2 . (3.1)
Let T (C) = {T }. Recall that |L(T )| = d and by Lemma 2.1, we can assume that the fan-in of each internal node of T is bounded by 2. For any u ∈ I(T ) (recall that I(T ) is the set of internal nodes of T ), let L(u) denote the set of leaves of the subtree rooted at u. We identify each leaf ∈ T with pos( ) ∈ [d]. For each u ∈ I(T ), we de ne the partition Π u by Π u ( ) = -1 i ∈ L(u). For γ > 0, de ne a partition Π to be γ-correlated to T if for each u ∈ I(T ), we have ∈L(u) Π( ) ≤ γ. For the rest of this section, let f, N, b, c, d as in the statement of Lemma 3.2. Lemma 3.2 immediately follows from Claims 3.4 and 3.5, stated below.

Claim 3.4

Let Π be any partition of [d]

such that rank(f, Π) ≥ N d/2-b . Then Π is O(b + c)-correlated to T .
Proof. We know from Theorem 2.7 and Proposition 1.15 that for each

u ∈ I(T ), rank(f, Π u ), rank(f, -Π u ) ≤ N c . If Π is a partition such that either ∆(Π, Π u ) or ∆(Π, -Π u ) is strictly smaller than d 2 -(b + c) for some u ∈ I(T ), then by Lemma 1.16 we would have rank(f, Π) < N d/2-b . Thus, if rank(f, Π) ≥ N d/2-b , we must have min{∆(Π, Π u ), ∆(Π, -Π u )} ≥ d
Let v be the root of T . Note that Π v ∈ {-1, 1} d is the vector with all its entries being -1. Hence, we have for any u ∈ I(T ),

∈L(u) Π( ) = Π, -(Π u + Π v ) 2 ≤ 1 2 (| Π, Π u | + | Π, Π v |) ≤ O(γ).
This proves the claim.

Claim 3.5

Say Π ∈ {-1, 1} d is chosen uniformly at random and γ ≤ √ d. Then Pr Π [Π is γ-correlated to T ] ≤ exp(-Ω( d γ 2 )).
The following subclaim is useful for proving Claim 3.5.

Subclaim 3.6

Assume that r, t ∈ N such that rt ≤ d/4. Then we can nd a sequence u 1 , . . . , u r ∈ I(T ) such that for each i ∈

[r] we have |L(u i ) \ i-1 j=1 L(u j )| ≥ t.
Proof. Consider the following 'greedy' procedure for choosing the u i . Order the nodes of I(T ) in topological order (recall that the edges of T are directed toward the root). We choose u 1 to be the least node in this order so that |L(u 1 )| ≥ t (such a node must exist since there are d ≥ t leaves in T ). Further, having chosen u 1 , . . . , u i we choose u i+1 to be the least node greater than or equal to u 1 , . . . , u i in the topological order such that |L(u i+1 ) \ i j=1 L(u j )| ≥ t. To argue that this process produces a sequence of size at least r, note that for

each i ≥ 0, |L(u i+1 )\ i j=1 L(u j )| ≤ 2t
. This is because the fan-in of u i+1 in T is at most 2 and by assumption, for each child u of u i+1 , we have |L(u

)\ i j=1 L(u j )| < t. Thus for each i ≥ 0, we have | i+1 j=1 L(u j )| ≤ 2t(i + 1). In particular, if i + 1 < r, we have | i+1 j=1 L(u j )| < 2tr ≤ d/2.
Thus, for v being the root of the tree, we have

|L(v) \ i+1 j=1 L(u j )| > d/2 ≥ t.
In particular, there is at least one node u of the tree such that |L(u) \ i+1 j=1 L(u j )| ≥ t. This allows us to extend the sequence further.

Proof of Claim 3.5. We apply Subclaim 3.6 with t = Θ(γ 2 ) and r = Θ(d/γ 2 ) to get a sequence u 1 , . . . , u r ∈ I(T ) such that for each i ∈

[r], we have |L(u i ) \ i-1 j=1 L(u j )| ≥ t.
By the de nition of γ-correlation, we have

Pr Π [Π γ-correlated to T ] ≤ Pr Π   ∀i ∈ [r], ∈L(u i ) Π( ) ≤ γ   ≤ i∈[r] Pr Π   ∈L(u i ) Π( ) ≤ γ {Π( ) | ∈ j<i L(u j )}   (3.2)
Fix any i ∈ [r] and Π( ) for each ∈ L <i := j<i L(u j ). Note that the event

| ∈L(u i ) Π( )| ≤ γ is equivalent to ∈L(u i )\L <i Π( ) ∈ I for some interval I of length 2γ = O( √ t)
. This is the probability that the sum of at least t independent uniformly chosen {-1, 1}-valued random variables lies in an interval of length O( √ t). By the Central Limit theorem, this can be bounded by 1 -Ω(1).

By (3.2), we get

Pr

Π [Π γ-correlated to T ] ≤ exp{-Ω(r)}
which gives the statement of the claim.

Lower bounds for circuits with rotations of one parse tree

Given two parse trees T 1 and T 2 with the same number of leaves, we say that T 1 is a rotation of T 2 , denoted T 1 ∼ T 2 , if T 1 can be obtained from T 2 by repeatedly reordering the children of various nodes in T 2 . Clearly, ∼ is an equivalence relation. We use [[T ]] to denote the equivalence class of tree T. We say that a homogeneous circuit C is rotation UPT or rotUPT if there is a tree T such that

T (C) ⊆ [[T ]].
The tree T is said to be a template for C.

Our main result in this section is the following.

Theorem 3.7

Let C be a rotUPT circuit of size s computing a polynomial f ∈ F X of degree d over N variables, then there exists a partition

Π = Π C such that rel-rank(f, Π) is at most poly(s) • N -Ω(d) .
In particular, we get the following corollary.

Corollary 3.8

Let N, d ∈ N be parameters with d even. Let |F| > q 0 (N, d) where q 0 (N, d) is as in Theorem 1.17. Then, any rotUPT circuit for F N,d over F has size N Ω(d) .

Proof outline. Our starting point is a decomposition lemma of Hrubeš et al. [START_REF] Hrubeš | Non-commutative circuits and the sum-of-squares problem[END_REF] and its subsequent strengthening in [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF]. As noted in [START_REF] Hrubeš | Non-commutative circuits and the sum-of-squares problem[END_REF], any homogeneous polynomial f of degree d computed by a non-commutative circuit of small size can be written as a small sum of polynomials of the form g × j h, where g, h are homogeneous polynomials of degrees in the range

[d/3, 2d/3].
It was observed in [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF] that for certain special kinds of circuits, this statement can be strengthened to yield a decomposition where each term g × j h satis es

deg(g) = d for some xed d ∈ [d].
This was used, with d = 3d/4, to prove a lower bound for non-commutative skew circuits in [START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF].

Here, we use a similar idea to show that whenever the template T has a node of degree

d ∈ [(3/4)d, (11/12)d], then the corresponding rotUPT circuit C is low rank w.r.t. the partition Π 2 = (Y 2 , Z 2 ) where Y 2 = [d/4 + 1, 3d/4].
It remains to handle the case when T has no such "large degree" node. To see what happens in this case, consider the extreme case when the root v of T has two children u 1 and u 2 of degree d/2 each. In this case, it is easily seen that every parse formula computes two monomials of degree d/2 which are multiplied together to compute the output monomial. From here, it is not hard to show that the polynomial computed by the circuit C can be written as a small sum of polynomials of the form g • h where g and h have degree d/2 each. As observed by Nisan [START_REF] Nisan | Lower bounds for non-commutative computation (extended abstract)[END_REF], this implies that C is now low-rank w.r.t. the partition

Π 1 = (Y 1 , Z 1 ) where Y 1 = [d/2].
The more general case is an abstraction of this argument to allow for a few "low-degree" nodes near the root and also for a single large degree node v to have many small degree children (as opposed to just two in the above example).

We now begin with the proof. First, we will need a decomposition lemma for non-commutative circuits. The following is a variant of lemmas proved in [START_REF] Hrubeš | Non-commutative circuits and the sum-of-squares problem[END_REF][START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF] and Chapter 2.

Lemma 3.9: A decomposition lemma for homogeneous circuits

Let C be any homogeneous arithmetic circuit of size s computing f ∈ F X of degree d. Assume that there is some d ∈ [d/2 + 1, d] such that every parse formula C of C contains a gate computing a (homogeneous) polynomial of degree d . Let Φ 1 , . . . , Φ r (r ≤ s) be the set of × gates computing polynomials of degree d in C and let g 1 , . . . , g r be the polynomials they compute (respectively). Then, there exist homogeneous polynomials h i,j

(i ∈ [r], j ∈ [0, d -d ]) of degree d -d such that f = r i=1 d-d j=0 g i × j h i,j .
Proof. We will rst simplify the circuit C so that each gate Φ appears in some parse formula of C. If Φ appears in no parse formula of C, then we can remove it from the circuit without changing the polynomial computed by the circuit.

We consider a topological ordering of the gates of the circuit C so that if the gate Φ computes a polynomial of degree at most the degree of the gate Ψ, then Φ appears before Ψ in the ordering. This can be done since C is a homogeneous circuit.

Let Ψ 1 , . . . , Ψ p (p ≤ s) be this topological ordering of the gates and let f k be the polynomial computed at

Ψ k (k ∈ [p]). Let d k = deg(f k ). We prove by induction on k ∈ [p] that if d k ≥ d , then f k = r i=1 d-d j=0 g i × j h (k) i,j . (3.3)
for some homogeneous polynomials h

(k)
i,j of degree d -d each. Note that this is vacuously true for k such that deg(f k ) < d .

If the gate Ψ k is a × gate of degree d k ≥ d , then we have the following possibilities:

• d k = d : In this case f k = g i for some i ∈ [r] and hence we can take h

(k) i,0 = 1 and h (k) i ,j = 0 for all other i , j pairs. • d k > d : In this case f k = f k 1 • • • f kt for some t
f ka = r i=1 d j=0 g i × j h (ka) i,j .
for suitable h (ka) i,j of degree d ka -d each. Thus, we have

f = f k 1 • • • f kt = r i=1 d ka -d j=0 f 1 • • • f ka-1 • (g i × j h (ka) i,j ) • f ka+1 • • • f kt = r i=1 d ka -d j=0 g i × j+d k 1 +•••+d k a-1 (f 1 • • • f ka-1 h (ka) i,j f ka+1 • • • f kt )
where for the nal equality we have used the observation that (g × j h) × j h = g × j+j (h × j h ) for any homogeneous polynomials g, h, h and any relevant j, j .

For any j ∈ [0, d ka -d ], we have j

:= j + d k 1 + • • • + d k a-1 ∈ [d k 1 + • • • + d k a-1 , d k -d ]. Hence, setting h (k) i,j = f 1 • • • f ka-1 h (ka) i,j f ka+1 • • • f kt for each j ∈∈ [d k 1 + • • • + d k a-1 , d k -d ], and 0 for all j < d k 1 + • • • + d k a-1 , the above yields (3.3) in this case. If the gate Ψ k is a + gate of degree d k ≥ d , then it is a linear combination of gates Ψ k 1 , . . . , Ψ kt of degree d k each. By induction, for each a ∈ [t], we have f ka = r i=1 d-d j=0 g i × j h (ka) i,j .
Say f k = a α a f ka where α a ∈ F. Then using the fact that × j is bilinear, we get

f k = a∈[t] α a f ka = r i=1 d-d j=0 a α a (g i × j h (ka) i,j ) = r i=1 d-d j=0 g i × j ( a α a h (ka) i,j ))
which is of the form required in (3.3). This completes the induction.

We now prove the main theorem of this section.

Proof of Theorem 3.7. Let C be rotUPT of size s computing a polynomial f of degree d over N variables, and let T be a template for C.

Let Π i = (Y i , Z i ) for i ∈ [2] be two partitions of [d] with Y 1 = [d/2] and Y 2 = [d/4 + 1, 3d/4]. We will show that rel-rank(f, Π) ≤ poly(s) • N -Ω(d) for at least one Π ∈ {Π 1 , Π 2 }.
We consider two cases:

Case 1: there is a node of degree d 0 ∈ [ 3 4 d, 11 12 d] in the template T . Note that every rotation T ∈ [[T ]] also has a node of degree d 0 . Since every parse tree of C is a member of [[T ]], this implies that each parse formula C of C contains a gate of degree d 0 . Applying Lemma 3.9 with d = d 0 , we see that there are k ≤ s homogeneous polynomials g 1 , . . . , g k of degree d 0 and k

• (d -d 0 + 1) homogeneous polynomials h i,j (i ∈ [k], j ∈ [0, d -d 0 ]) of degree d -d 0 such that: f = k i=1 d-d 0 j=0 g i × j h i,j (3.4)
We show that each term of the above decomposition has low relative rank w.r.t. the partition Π 2 de ned above. Fix a term g i × j h i,j from the decomposition above. Let

Π j = (Y j , Z j ) where Y j = [j + 1, j + d 0 ]
. By Corollary 1.14, we see that rank(g i × j h i,j , Π j ) ≤ 1.

A straightforward calculation shows that ∆(Π j , Π 2 ) = d 0 -d 2 = d 2 -Ω(d) for all j. Hence, by Lemma 1.16, we see that rank(g i × j h i,j , Π 2 ) ≤ N (d/2)-Ω(d) and hence rel-rank(g i × j h i,j , Π 2 ) ≤ N -Ω(d) for each i, j.

Using (3.4) and the subadditivity of rank, we see that rel-rank(f, Π 2 )

≤ (sd) • N -Ω(d) ≤ s 2 • N -Ω(d) .
Case 2: there is no gate of degree d 0 ∈ [ 3 4 d, 11 12 d] in the template T . In this case, we show that rel-rank(f, Π 1 ) is small, where Π 1 is as de ned above.

Let v be the node in T such that deg(v) > 11 12 d and all its children have degree ≤ 11 12 d. Note that such a v is uniquely de ned (if there were another such node v , it cannot be an ancestor or descendant of v; hence, we see that the number of leaves in T is at least

deg(v) + deg(v ) > d which is a contradiction). Let d 0 = deg(v). Let v 1 , . . . , v t be the children of v in T and assume that deg(v i ) = d i . Note that d i < 3d
4 for each i. As in the previous case, we see that every parse formula contains a gate of degree d 0 and hence applying the lemma with d = d 0 we get

f = i=1 d-d 0 j=0 g i × j h i,j (3.5)
where g 1 , . . . , g ( ≤ s) are the polynomials of degree d 0 computed by multiplication gates in C. We show that for each i, j, rel-rank(g i × j h i,j , Π 1 ) ≤ N -Ω(d) .

As in the previous case, this will imply rel-rank(f, Π) ≤ s 2 • N -Ω(d) .

Fix any i, j. We use g and h instead of g i and h i,j . We know that g is a polynomial computed by some × gate Φ of degree d 0 in the circuit. Consider the + gates feeding into Φ. Since every parse tree T of C is a rotation of T , it must be the case that there are exactly t such + gates Ψ 1 , . . . , Ψ t computing polynomials g1 , . . . , gt such that g = g1

h = (g 1 • • • gt ) × j h. For any a ∈ [t],
we note that we can also write

g × j h = (g 1 • • • ga ) × j h a where h a := (g a+1 • • • gt ) × j h. Let Π a = (Y a , Z a ) be the partition of [d] such that Y a = [j + 1, j + d 1 + • • • + d a ]. By Corollary 1.14, we know that rank(g × j h, Π a ) = rank((g 1 • • • ga ) × j h a , Π a ) ≤ 1 for each a ∈ [t].
Therefore, by Lemma 1.16, to prove that rel-rank(g

× j h, Π 1 ) ≤ N -Ω(d) , it su ces to show that ∆(Π a , Π 1 ) ≤ d 2 -Ω(d) for some a ∈ [t]. We do this now. Consider the least b ∈ [t] so that d 1 +d 2 +• • •+d b ≥ 1 20 d. Let δ = d 1 +• • •+d b . Since each d a < 3 4 d, we know that δ ∈ [ 1 20 d, d -1 5 d]. Note that for partition Π b , we have ∆(Π b , Π 1 ) = |Y b ∆Y 1 | where Y b = [j + 1, j + δ] and Y 1 = [ 1 2 d]. We thus get |Y b ∆Y 1 | ≤ j + | d 2 -(j + δ)| = j + max{ d 2 -(j + δ), j + δ - d 2 } = max{ d 2 -δ, 2j + δ - d 2 } = d 2 -min{δ, d -(2j + δ)}. Since δ ≥ 1 20 d and (2j + δ) ≤ 2 • 1 12 d + d -1 5 d < d -Ω(d), we see that ∆(Π b , Π 1 ) = |Y b ∆Y 1 | = d 2 -Ω(d).
This completes the proof.

53

Remark 3.10

We note that the proof of the theorem yields the stronger statement that f is low-rank w.r.t. one of the two partitions Π 1 and Π 2 . It is not hard to use this to prove a lower bound for an even simpler polynomial than the polynomial F N,d from Theorem 1.17, by taking for example g

(X) = αP al d (X) + βP al d/2 (X) × P al d/2 (X) for suitable α, β ∈ F to ensure that rank(g, Π 1 ) = rank(P al d (X), Π 1 ) = N d/2 and rank(g, Π 2 ) = rank(P al d/2 (X) × P al d/2 (X), Π 2 ) = N d/2 .
Note also that g(X) is computable by a small 2-PT circuit, hence 2-PT ⊂ rot-PT.

Overview

In the previous chapters, we make some progress in proving lower bounds for circuits closer and closer to general circuits by restricting the parse trees in the circuits. In this chapter, we make progress on the "Formulas vs. ABPs" question, using the same approach: we use restrictions on the parse trees that appear in formulas. More precisely, we prove some tight lower bounds for formulas (with some restrictions on the parse trees) computing IMM

Notation and decomposition lemma for labelled UPT formulas

In this section, we x some notation that will be used in the rest of Chapter 4. We also prove that any polynomial computed by a labelled UPT formula (de ned below) admits a speci c decomposition, given by Lemma 4.5.

Throughout the chapter, the set X will be a set of N = n 2 d variables satisfying X = i∈[d] X i where each X i has n 2 variables. Let M i be an n × n matrix whose entries are distinct variables from X i . Recall from Section 1.1 that

IMM n,d = Tr(M 1 • • • M d ) ∈ F X .

Algebraic Branching Programs

We also consider homogeneous algebraic branching programs (ABPs), de ned by Nisan in the non-commutative context. We give here a slightly di erent de nition that is equivalent up to polynomial factors.

A homogeneous algebraic branching program (ABP) for a homogenous polynomial f ∈ F X of degree d is a pair (n 1 , ρ) where n 1 ∈ N and ρ is a map from X = {x 1 , . . . , x n 2 1 d } to homogeneous linear functions from F X such that f can be obtained by substituting ρ(x i ) for each x i in the polynomial IMM n 1 ,d (X ). The parameter n 1 is called the width of the ABP.

Other notation and rst properties

For I = {i 1 < • • • < i t } ⊆ [d],
we de ne the set of I-monomials to be the set of monomials of the form x 1 • • • x t where x j ∈ X i j . Also, we de ne P I to be the set of those polynomials P over the variables j∈[t] X i j that can be written as a linear combination of I-monomials. We de ne IMM I to be Tr(M i 1 • • • M it ). Note that IMM I ∈ P I .

Given I as above and f ∈ P I , we de ne M I (f ) to be a n 2 t 2 × n 2 t 2 matrix whose rows and columns are labelled by I odd -monomials and I even -monomials respectively, where I odd = {i 1 , i 3 , i 5 , . . .} and I even = {i 2 , i 4 , i 6 , . . .}. The (m , m )th entry of M I (f ) is the coe cient in f of the I-monomial which is equal to m when restricted to its odd locations and m when restricted to its even locations. Note that rank(M I (f )) ≤ n 2 t 2 . We de ne rel-rank I (f ) = rank(M I (f ))/n 2 t 2 . We will need the following simple observations. Let T be a parse tree with t leaves and

I = {i 1 < i 2 < • • • < i t }.
The I-labelling of T is the function lab : T → 2 I \ {∅} de ned as follows. For each u ∈ L(T ) (recall that L(T ) is the set of leaves of T and I(T ) is the set of internal nodes of T ), we de ne lab(u) to be {i j } if u is the jth leaf in the pre-order traversal of T . We will sometimes abuse notation and write lab(u) = i j . For each v ∈ I(T ), we de ne lab(v) to be the set of labels of the leaves in the subtree rooted at v.

Let F be a UPT formula of shape T . By Proposition 2.3, we know that F is in normal form. We say that F is I-labelled if for each input gate Φ of F that is a (u, ×)-gate with u ∈ L(T ), the variable labelling Φ lies in the set X lab(u) . The following is an easy observation.

Observation 4.2

If F is an I-labelled UPT formula with shape T , then it computes a polynomial from P I . More generally, if Φ is a (u, +) or (u, ×) gate of F with u ∈ T , then Φ computes a polynomial from P lab(u) .

Further, for any F that is a UPT formula of size at most s computing a polynomial f , there is an I-labelled UPT formula F of shape T and size at most s that computes the polynomial f ∈ P I that is obtained from f by zeroing out the coe cients of all monomials that are not I-monomials.

In the lower bound proofs, we follow a strategy used by Nisan and Wigderson [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF], and show that any small formula (with suitably restricted parse trees) can be converted to a low-rank polynomial after setting a subset of the variables. To make this precise, we need the notion of a restriction, which we de ne now.

A restriction is formally just a subset I ⊆ [d], which represents a substitution ρ I of the set of variables in X = i∈[d] X i as follows:

ρ I (x) =    x if x ∈ i∈I X i , 0 if x is an o diagonal entry of M j for j ∈ I, 1 if x is a diagonal entry of M j for j ∈ I.
In other words, we substitute all the variables in j ∈I X j such that each M j (j ∈ I) becomes the identity matrix. All variables from the set i∈I X i are left as is.

Every polynomial P ∈ F X is transformed in the natural way by such a substitution. We call this new polynomial a restriction of P and denote it by P | I .

Let T be a parse tree with d leaves. For any restriction I, let T | I denote the tree obtained by removing all nodes u ∈ T such that lab(u) ∩ I = ∅ (in particular only leaves with labels from I survive in T | I ). The I-labelling of the tree T | I is given by the labelling function lab I where lab I (u) = lab(u) ∩ I.

We make the following simple observations. We note that the above restrictions don't increase the complexity of the polynomial as far as UPT formulas are concerned. Proof. Let F be as in the statement and I be any restriction. If we replace every variable in the formula F by ρ I (x), we obtain by de nition a formula F which computes f | I . F is not a UPT formula since the leaves which were labeled by a variable from X j (j ∈ I) have been replaced by some constants, whereas leaves in a UPT formula have to be variables. We now transform F to a UPT formula F | I in the following way. Let u, v be any pair of nodes in T with lab(u) ∩ I = ∅ and lab(v) ∩ I = ∅. Each (u, +)-gate Ψ in F computes a constant (say α) and is wired to a (v, ×)-gate Φ in F . We delete the subformula rooted at Ψ from F and multiply by α the constant labelling the output wire of Φ. By doing this for every u, v and Ψ, the formula F becomes a new formula F | I which is UPT with shape T | I , and still computes f | I .

Decomposition lemma

We now state a decomposition lemma for UPT formulas which will help us choose suitable restrictions that help simplify small formulas to low-rank polynomials.

Let T be a parse tree and π = (v r , . . . , v 0 ) a path of length r in it 1 . We say that u is an o -path node of π if there is an i < r such that u is a child of v i and u = v i+1 . The set of o -path nodes of π is denoted off(π). 1 Recall that our trees are oriented towards the root. 59 Lemma 4.5

Let F be an I-labelled UPT formula of size s with shape T computing a polynomial f ∈ P I , and let π = (v r , . . . , v 0 ) be a path in T . If we de ne u j to be the jth node of off(π) ∪ {v r } that appears in the pre-order traversal of T , then we can decompose f as:

f = k i=1 t j=1 f i,j where • k ≤ s, • t = |off(π) ∪ {v r }|, • f i,j ∈ P lab(u j ) .
Proof. Let F be an I-labelled UPT formula as in the statement and π = (v r , . . . , v 0 ) be a path in T . Let (u 1 , . . . , u t ) be the ordering of the set of nodes (off(π) ∪ {v r }) given by a pre-order traversal of T . By Proposition 2.3, F is in normal form.

We say that a path in the formula F is of signature π if the +-gates along this path are successively a (v r , +) gate, a (v r-1 , +) gate, and so on until we get a (v 0 , +) gate. Let k be the number of paths in F with signature π, and p 1 , p 2 , ..., p k be these paths. As F is a formula, the number of paths from a leaf to the root is upper bounded by s. Therefore k ≤ s.

Each parse formula F (which is a subformula of F ) of F has shape T and further each +-gate in F has fan-in 1; thus, each parse formula contains one and only one path of signature π. The set S of parse formulas of F is therefore naturally partitioned as S = S 1 ∪ • • • ∪ S k , where S i is the set of parse formulas that contain the path p i . Recall that if F is a parse formula of F , we denote by val(F ) the monomial (along with its coe cient) computed by it. We have:

f = F ∈S val(F ) = k i=1 F ∈S i val(F ) From now, what remains to prove is that for each a ∈ [k], F ∈Sa val(F ) is of the form t j=1
f i,j with the additional property that each f i,j is a polynomial in P lab(u j ) .

We x a particular a ∈ [k]. The polynomial F ∈Sa val(F ) is nothing else than the polynomial computed by the I-labelled UPT formula G where for all m ∈ {0, . . . , r}, each (v m , +) gate that is not present on the path p a has been deleted (together with the entire subformula at that gate). Observe that for all m, the (v m , +) gate in G is of in-degree and out-degree 1, except for the output gate, which is a (v 0 , +) gate of in-degree 1 and is of out-degree 0.

Let

p a = Φ r , Ψ r-1 , Φ r-1 , Ψ r-2 , Φ r-2 , . . . , Φ 1 , Ψ 1 , Φ 0
, where Φ 0 is the root and for each m, Φ m is the (v m , +)-gate and Ψ m is the (v m , ×)-gate in p a . By construction, the path p a is present in G. We prove by induction that the following statement H(m) holds for each m ≤ r, H(m): If we denote by (w 1 , . . . , w tm ) the ordering of the set off((v r , . . . , v m )) ∪ {v r } given by a pre-order traversal of T , then the polynomial computed by Φ m in G is of the form tm j=1 g j where:

• t m = |off((v r , . . . , v m )) ∪ {v r }| • g j ∈ P lab(w j )
We now prove H(m) by downward induction on m. It is clearly true when m = r since t r = 1, as F is an I-labelled UPT formula and hence the polynomial computed by Φ r is an element of P lab(vr) .

Assume the statement H(m + 1) and let j∈[t m+1 ] h j be the decomposition of the polynomial computed by the gate Φ m+1 given by the induction hypothesis. The polynomial computed by Φ m (a +-gate of fan-in 1 in the formula G) is the product of the inputs of Ψ m : assume that these inputs are (in left-to-right order) Φ 1 , . . . , Φ b with each Φ being a (w , +)-gate for some w ∈ T . Let P be the polynomial computed by

Φ ( ∈ [b]). The gate Φ m+1 is one among Φ 1 , . . . , Φ b : let us say it is Φ c . The polynomial computed by Φ m is equal to b =1 P = ( c-1 =1 P ).( t m+1 j=1 h j ).( b =c+1
P ) by the induction hypothesis. Each P is computed by a (w , +)-gate and is thus a polynomial in P lab(w ) (Observation 4.2), and by induction, the h j are polynomials in P lab(w j ) , where w 1 , . . . , w t m+1 is the ordering of off((v r , . . . , v m+1 )) ∪ {v r } given by the pre-order traversal of T . But observe that w 1 , . . . , w c-1 , w 1 , . . . , w t m+1 , w c+1 , . . . , w tm is exactly the ordering of off((v r , . . . , v m )) ∪ {v r } given by the pre-order traversal of T , so that the induction holds, and the lemma is proved.

Proof outline of the two lower bounds contained in this chapter. The basic proof strategy is to choose a suitable I ⊆ [d] and apply this restriction to the polynomial IMM n,d as well as the formula computing it. By Observation 4.3, under any such restriction, IMM n,d becomes the polynomial IMM I which, by Observation 4.1, has reasonably large relative rank. On the other hand, for any given small formula (with some restriction on the parse trees), we show that there is a suitable choice for the restriction that makes its relative rank quite small. This will prove the lower bound.

The choice of the restriction to make a small formula low rank is dictated by Lemma 4.5. Consider rst the case of a UPT formula F of shape T which has depth ∆. In this case, we show that we can nd a path π = (v r , . . . , v 0 ) in T with t many o -path nodes where t is roughly ∆d 1/∆ . Applying Lemma 4.5, we can nd a decomposition of F of the form

s i=1 j∈[t] f i,j
where s is the size of the formula F ; it is crucial here that the sets of variables among X 1 , . . . , X d that f i,j depends upon is exactly the set of labels of the jth o -path node of π and in particular, is the same no matter which i we choose (this is where the formula being UPT is used). Say that I j ⊆ [d] indexes the variable sets that f i,j depends on. To make sure that these terms are low-rank, we use the following observation (used also by [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF]): for each j such that |I j | is odd, the relative rank of the term j f i,j drops by a factor of 1/n. Thus, if we restrict to a subset I such that |I ∩ I j | = 1 for each j, the relative rank of each term is at most n -t and hence we obtain a lower bound of n t on the size s of the formula. This gives a lower bound of roughly n Ω(∆d 1/∆ ) on the size of F . With no restriction on ∆, this gives a lower bound of n Ω(log d) . Now consider the case that F is a k-PT formula for k 2 d . In this case, we rst write F as a sum of k UPT formulas F 1 , . . . , F k (Lemma 3.1) and nd a restriction I such that each F i becomes low-rank with respect to I. To do this, we note that, by our proof in the UPT case, for some F j to be low-rank w.r.t. I, it su ces to show that after applying the restriction we can nd some path π = (v r , . . . , v 0 ) in the corresponding shape such that there are many opath nodes in π whose labels involve an odd number of variable sets among X 1 , . . . , X d .

The way we do this is that we choose a restriction I ⊆ [d] uniformly at random and show that for any given shape T , the probability that there is no π as above in the restricted parse tree T | I is very small. With this technical statement in hand, the proof of the lower bound follows as in the UPT case.

For the rest of this chapter and in order to avoid useless technical details, the size of a circuit will be its number of vertices.

Lower bound for UPT formulas

We de ne the ×-depth of a formula to be the maximum number of ×-gates that one can meet on a path from the root to a leaf. Note that if a formula has alternating + and × gates on each path and has depth ∆ and ×-depth ∆, then ∆ ≤ ∆ 2 . We will state our lower bounds bounds in terms of ×-depth. Throughout this section, we assume that all the UPT formulas we consider don't have any multiplication gate of fan-in 1, or equivalently, the shape of any UPT formula we consider does not have any internal node of fan-in 1. This assumption is w.l.o.g. as shown below.

Lemma 4.6

Given any UPT formula F of shape T and size s computing a polynomial f , there is another UPT formula F of shape T and size at most s computing f where T has no internal nodes of fan-in 1 (and consequently F has no ×-gates of fan-in 1). Further, if all internal nodes of T have fan-in at most k ∈ N with k ≥ 2, then the same holds for T .

Proof. The transformation process is the following: a multiplication gate of fan-in 1 does not change its input and therefore can be deleted without changing the polynomial computed. Merging the two layers of +-gates above and below the deleted gate ensures the formula still alternates between +-gates and ×-gates. The shape T of the new formula is simply the shape T where the internal nodes of fan-in 1 have been removed and replaced by an edge. Clearly, the new shape T has the required property.

Before attacking the main theorem, we will need one more lemma.

Lemma 4.7

Let T be a tree with d leaves and depth ∆, such that all internal nodes are of in-degree strictly greater than 1. Then there is a path π = (v , . . . , v 0 ) in T such that |off(π) ∪ {v }| ≥ Ω(∆d 1/∆ ).

Proof. Let T be a tree as in the statement. We denote by wt(v) the fan-in of the node v. We will prove the following equivalent conclusion: there is a path π = (v , . . . , v 0 ) from a leaf to the root such that 1 + 0≤i< (wt(v i ) -1) ≥ Ω(∆d 1/∆ ).

We consider two distinct cases:

• Case 1: ∆ > log e (d). In this case, any path p = (v ∆ , . . . , v 0 ) of depth ∆ satis es 1 + 0≤i<∆ (wt(v i ) -1) ≥ ∆ + 1 = Ω(∆d 1/∆ ).

• Case 2: ∆ ≤ log e (d). We consider the following greedy procedure to choose the path of internal nodes: starting from the root, repeatedly choose a child such that the number of leaves in the resulting subtree is maximized. Let p = v 0 , . . . , v be the sequence of nodes thus obtained. Note that ≤ ∆ ≤ log e (d).

We prove by induction on the tree T that the number of leaves of the tree is at most the product of the fan-ins of v 0 , . . . , v -1 (this fact is true for any tree T and not just trees T of depth at most log e d). If = 0, the entire tree consists of just the root: hence the number of leaves is 1 and the (empty) product also evaluates to 1. Assume now that the root v 0 has k children corresponding to subtrees T 1 , T 2 , . . . T k . We assume the number of leaves in the subtree T i is t i . Assume the greedy algorithm chooses v 1 corresponding to the subtree rooted in T i (thus, we must have t i ≥ t j for any j ∈ [k]). By the induction hypothesis,

j=1 wt(v j ) ≥ t i . Therefore -1 j=0 wt(v j ) ≥ k • t i ≥ k j=1 t j = d
which concludes the induction.

By the inequality of arithmetic and geometric means, we have

0≤i<l wt(v) ≥ 0≤i< wt(v) 1/ ≥ d 1/ .
So, we have

0≤i< (wt(v) -1) ≥ (d 1/ -1).
Notice that the right part of this inequality is a decreasing function of in the regime ≤ log e (d), so that:

0≤i< (wt(v) -1) ≥ ∆(d 1/∆ -1) = ∆d 1/∆ (1 - 1 d 1/∆ ) ≥ ∆d 1/∆ (1 - 1 e )
= Ω(∆d 1/∆ ).

We now prove a lower bound for any UPT formula computing IMM n,d . The lower bound is depth-dependent and stronger for smaller depths.

Theorem 4.8

Let F be a UPT formula of ×-depth ∆, size s, computing IMM n,d ∈ F X . Then, s ≥ n Ω(∆d 1/∆ ) . In particular, any UPT formula for IMM n,d must have size n Ω(log d) .

By our earlier observation relating the ×-depth with depth, we get the lower bound stated in the introduction.

Proof. Let F be a UPT formula as in the statement. Let T be the shape of F : note that the depth of T is precisely the ×-depth of F which is ∆.

By Lemma 4.2, we can assume w.l.o.g that the formula F is [d]-labelled and hence that the variables that label any input gate Φ of F corresponding to a node v(Φ) ∈ T are all included in X lab(v(Φ)) where lab is the [d]-labelling of T . By Lemma4.7, there is a path π = (v , . . . , v 0 ) in the shape T of F , such that |off(π) ∪ {v 0 }| ≥ Ω(∆d 1/∆ ). Let us denote by t the size of off(π) ∪ {v 0 }. We decompose IMM n,d along this path by Lemma 4.5, as:

IMM n,d (X 1 , X 2 , ..., X d ) = k i=1 t j=1 f i,j
with k ≤ s. Each f i,j is a P lab(u j ) where (u 1 , . . . , u t ) is the ordering of off(π)∪{v 0 } given by a pre-order traversal of T .

We now apply a restriction to this equality given by the subset I choosen in the following way: for each j, we select one element from lab(u j ) -we call it p j -and add it to I. The set I is of size t. Under this restriction, each f i,j becomes a homogeneous linear polynomial in the variables X p j . We call these homogeneous linear polynomials l i,j . On the other hand, we know (Observation 4.3) that IMM n,d | I = IMM I . We thus get

IMM I = k i=1 t j=1 l i,j .
It is not hard to see that for each i, rank(M I ( t j=1 l i,j )) ≤ 1. By Observation 4.1 and subadditivity of the rank, we get:

n 2 t/2 -1 ≤ k Therefore, we get s ≥ k ≥ n Ω(∆t 1/∆ )
as wanted.

Remark 4.9

Notice that this lower bound is tight for every ×-depth ∆, since the standard divide and conquer approach to computing IMM n,d gives in fact a UPT formula of size n O(∆d 1/∆ ) and ×-depth ∆, for any ∆ ≤ log d.

Separation between k-PT formulas and ABPs

In this section, we will prove a lower bound on the size of k-PT formulas computing IMM n,d as long as k is signi cantly smaller than 2 d . Recall that the total number of parse trees with d leaves is 2 O(d) (see for example [START_REF] Church | Coping with syntactic ambiguity or how to put the block in the box on the table[END_REF]) and hence the results of this section may be intuitively interpreted as saying that any nontrivial upper bound on the number of parse trees appearing in the formula gives a separation between non-commutative formulas and ABPs.

The main theorem of this section is the following. In particular, if k = 2 o(d) , then size(F ) ≥ n ω (1) and if k = 2 d 1-Ω(1) , then size(F ) ≥ n Ω(log d) .

Remark 4.11

We say a few words about the assumption d ≤ log n. The standard divideand-conquer approach computing IMM n,d yields a (UPT) formula of size n O(log d) . It would be quite surprising if this standard algorithm were not optimal in terms of formula size (even for non-UPT formulas).

Intuitively, improving on the standard divide-and-conquer algorithm gets harder as d gets smaller: this is because any formula of size n o(log d) for computing IMM n,d can be straightforwardly used to recursively obtain formulas for IMM n,D of size n o(log D) for any D > d. Thus, the case of smaller d, which seems harder algorithmically, is a natural rst candidate for lower bounds.

Let T be a parse tree. We say that a node u ∈ T is odd if the number of leaves in the subtree rooted at u is odd. Given a path π, let odd(π) denote the set of odd o -path nodes of π.

Lemma 4.12

Let F be an I-labelled UPT formula of size s with shape T computing polynomial f . If T has a path π = (v r , . . . , v 0 ) with |odd(π)| ≥ , then

rel-rank I (f ) ≤ s n -1 .
Proof. Let (u 1 , . . . , u t ) be the ordering of the set of nodes (off(π) ∪ {v 0 }) given by a pre-order traversal of T , and f = k i=1 t j=1 f i,j be a decomposition given by Lemma 4.5, where each f i,j is in P lab(u j ) . By Observation 4.1, we know that rank(M I (f i,j )) ≤ n 2 |lab(u j )|/2 . Hence, by the subadditivity of rank and Lemma 1.13, we have:

rank(M I (f )) ≤ k i=1 t j=1 rank(M I (f i,j )) ≤ k i=1 t j=1 n 2 |lab(u j )| 2 = k i=1 n 2 t j=1 |lab(u j )| 2 = k i=1 n 2( |I| 2 - |odd(π)| 2 ) As k ≤ s, this implies that rel-rank I (f ) ≤ s n 2 |odd(π)| 2 ≤ s n -1 .
We now try to show that, given a small k-PT formula, there is a suitable choice of the restriction that makes its relative rank quite small. To do this, we will use Lemma 4.12, which translates the statement to a combinatorial statement about some trees. On the other hand, IMM remains high rank under arbitrary restrictions by Observation 4.1. This will prove Theorem 4.10.

The main technical lemma in the proof of Theorem 4.10 is the following.

Lemma 4.13

Let T be any tree with d leaves such that every internal node has fan-in exactly 2. Assume we choose I ⊆ [d] by adding each i ∈ [d] to I independently with probability 1/2. Then for any ∈ N

Pr I [T | I has no path π such that |odd(π)| ≥ ] ≤ exp(-Ω( d 2 8
)).

Postponing the proof of the above lemma to the end of this section, we can prove Theorem 4.10 as follows.

Proof of Theorem 4.10. We assume throughout that log d -log log k is larger than a large enough constant (to be chosen later), since otherwise the theorem is trivial. Let = 1 10 (log d -log log k) . Assume that F is a k-PT formula of size s computing IMM n,d . If s ≥ n /4 , then we are done.

Otherwise, we argue as follows. By Lemma 3.1, there exist UPT formulas F 1 , . . . , F k of size at most s 2 each such that

IMM n,d = k i=1 f i
where f i is the polynomial computed by F i . Let T i denote the shape of F i . By Lemma 2.1, we can assume that each internal node of T i has fan-in exactly 2.

By Observation 4.2 and Lemma 4.6, for each F i , there is a [d]-labelled UPT formula F i of shape T i and size at most s 2 that computes the polynomial f i that is obtained from f i by removing monomials that are not [d]-monomials. Since IMM n,d ∈ P [d] , we see that

IMM n,d = k i=1 f i . (4.1)
Now, choose a random restriction I by adding each j ∈ [d] to I independently with probability 1/2. Consider the relative rank of the polynomials on both sides of (4.1) after the restriction. For the left hand side, we know using Observation 4.1 that for any I, We now consider the right hand side of (4.1). By Lemma 4.4, for any choice of restriction I and i ∈ [k], the restricted polynomial f i | I has a UPT formula F i | I of size at most s 2 and shape T i | I computing f i | I . For each i ∈ [k], let E i denote the event that T i | I has no path π such that |odd(π)| ≥ . By Lemma 4.13, we know that the probability of E i is at most exp(-Ω( d 2 8 )). Let E = k i=1 E i . By a union bound we have

Pr [E] ≤ k • exp -Ω d 2 8 < 1 (4.3)
if (log d -log log k) is larger than some xed constant. If I is such that the event E does not occur, then for this choice of I and any i ∈ [k], by Lemma 4.12, rel-rank

I (f i | I ) ≤ s 2 n -1 ≤ 1 n ( /2)-1
, where the nal inequality follows from our assumption that s < n /4 . Now, since rel-rank I (•) is subadditive, we have

rel-rank I ( i∈[k] f i ) ≤ k n ( /2)-1 ≤ 2 d n ( /2)-1 ≤ 1 n ( /2)-2 < 1
where the nal two inequalities follow from the fact that d ≤ log n and the assumption that is greater than some xed constant. This contradicts (4.1) and (4.2) and hence concludes the proof of the theorem.

Proof of Lemma 4.13

We impose a natural partial order on the vertices in T by saying that u v for u, v ∈ T if v is an ancestor of u. Given a set of paths P = {π 1 , . . . , π r } in the tree T , we say that P is independent if the sets off(π i ) (i ∈ [r]) are pairwise disjoint and moreover, the set off(P ) := i off(π i ) forms an antichain w.r.t. the partial order (informally, no node in off(P ) is an ancestor of another).

We show the following claim.

Claim 4.14

Assume T is as in the statement of the lemma. Then for any ≥ 1, there is an independent set P of paths in T of length such that |P | = Ω(d/22 ).

Proof. Given a tree T as in Lemma 4.13, let us de ne T to be the subtree of T which contains every node of T that has height or more (here the height of a node u is the length of the longest path from a leaf from L(u) to u). Though every internal node in T has degree two, T may have internal nodes of degree two as well as one. The leaves of T are those internal nodes of T that have height exactly .

The main idea is as follows: Suppose T has 'many' leaves, then it is easy to nd many independent paths in T . This is because each leaf v of T is a node in T with at least one path of length rooted at v. This gives us as many independent paths as the number of leaves in T . On the other hand, if T does not have many leaves, then it also does not have many fan-in two nodes. In this case, by throwing away all fan-in two nodes of T , we get many components. Each component is a path and not all can be of length less than . Subdividing the long paths into paths of length then gives us the set of independent paths 2 . We now work out the details.

As every internal node of T has degree two, the number of nodes at height h, for any parameter h ≥ 1, is at least half of the number of nodes at height h -1. It follows that the number of leaves in T and therefore |T | is ≥ d 2 . We use s to denote |T |.

Case I, the number of leaves in T is ≥ s/100 : Each leaf v in T has a subtree rooted at it in T , say T v . For each leaf v in T , T v has at least one path of length from v to a leaf of T . Let us call this path π v . As the leaves of T are all the nodes at height , for two leaves of T , say u = v, and for any vertex x in off(π v ) and any vertex y in off(π u ), neither x y nor y

x. (If one of the conditions holds then it will contradict the fact that both u, v have height .)

The number of paths thus obtained is at Ω(s/ ) = Ω(d/2 2 ), and hence we are done in this case.

Case II, the number of leaves in T is < s/100 : It is easy to see that the number of fan-in two nodes in any tree is upper bounded by the number of leaves in the tree. Therefore, T has at most s/100 degree two nodes. Let F be the forest obtained by deleting all fan-in two nodes of T . F is a collection of paths. As we deleted degree two nodes, the total number of components created in F is at most twice the number of degree two nodes, i.e., at most s/50 .

We call a component small if it has at most nodes and large otherwise. The total number of nodes in small components is at most (s/50 ) • = s/50. We will not consider such components. Since |T | = s, we are left with at least s -s/50 ≥ s/2 nodes even if we discard all the small components.

Let C be a component with r vertices, where r > . It can be broken down into r +1 paths, each of length . This will give us at least s/2( + 1) many paths in total. As s/2( + 1) > d/2 2 , if we argue that all these paths are independent, we will be done.

It is not very hard to see why these paths are independent. Suppose two paths π, π belonged to the same large component, then consider vertices x ∈ off(π) and y ∈ off(π ). As T is a tree, neither x y nor y

x. Therefore, any such two paths are independent. Now say π, π are two paths which come from two di erent large components. Then for x ∈ off(π) and y ∈ off(π ), the common ancestor of x, y is a degree two node, which we deleted. Again, we can see that neither x y nor y x.

Given Claim 4.14, we proceed as follows. Applying Claim 4.14 with 4 in place of , we obtain a set P = {π 1 , . . . , π r } of independent paths in T with r = Ω(d/2 8 ). For each π i , let off(π i ) = {u i,1 , . . . , u i,4 }. Note that these o -path nodes all exist since each internal node of T is assumed to have fan-in 2.

We now consider the e ect of the random restriction I, chosen as in the lemma statement, on the tree T . For any i ∈ [r] and j ∈ [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF], let Z i,j ∈ {0, 1} be the random variable that is 1 if u i,j is present in T | I and is an odd node, and 0 otherwise; equivalently, if lab is the [d]-labelling of T , then Z i,j = 1 i the number of leaves v such that lab(v) ∈ I is odd. Note that E[Z i,j ] = (1/2) for each i ∈ [r] and j ∈ [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF]. Moreover, since P is an independent set of paths, the sets of leaves in the subtrees of u i,j (for di erent i, j) are pairwise disjoint and consequently, the random variables Z i,j (for various i, j) are mutually independent. In particular, by a Cherno bound applied to Z := i∈[r],j∈ [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF] Z i,j , we get

Pr [Z ≤ r ] = Pr Z ≤ 1 2 E[Z] ≤ exp(-Ω(E[Z])) ≤ exp(-Ω(r )) ≤ exp(-Ω( d 2 8
)).

Note that Z is the total number of nodes in off(P ) that end up as odd nodes in T | I . Hence, if Z > r , then the number of odd nodes per (surviving) path of P in T | I is at least r /r = . In particular, there must be some path π in T | I such that |odd(π)| ≥ . This concludes the proof of Lemma 4.13.

Chapter 5

Polynomial Identity Testing

Overview

Polynomial Identity Testing (PIT in short) is the important problem of determining whether a multivariate polynomial given by an arithmetic circuit equals formally zero (that is, each coe cient of the polynomial has to be zero). A very e cient and simple probabilistic algorithm is known for this problem: evaluate the polynomial at a random point over the eld Z/pZ for a large enough random prime p, and answer that the polynomial is formally zero if the evaluation equals zero. The correctness of this algorithm can be proved by using the Schwartz-Zippel lemma (saying essentially that a non-zero low-degree polynomial does not have a lot of zeros) and the Prime Number Theorem. This places the algorithm in the complexity class coRP (the class of problems which admit probabilistic polynomial-time algorithms which never reject a good input but may accept a wrong one with small probability (false positive)). Nevertheless, no deterministic sub-exponential time algorithm for PIT is known. The main issue is to derandomize the problem, that is, to design a deterministic algorithm still working in polynomial time (or at least in sub-exponential time). Testing polynomial identities is of great importance in algorithm design. For example, the best parallel algorithms for nding perfect matchings are based on testing whether a polynomial (in this case the determinant) equals formally zero. Designing a good deterministic algorithm for PIT would imply a good parallel deterministic algorithm for nding perfect matchings.

PIT is also linked with lower bounds. Indeed, in 2003, Kabanets and Impagliazzo have shown that if PIT has a deterministic polynomial-time algorithm, then either NEXP ⊂ P/poly or the permanent does not have polynomial size arithmetic circuits. For a complete proof of this result, see [START_REF] Perifel | Complexité algorithmique. Ellipses, 1st edition[END_REF] or [START_REF] Arora | Computational Complexity: A Modern Approach[END_REF]. This result explains partially why derandomization of PIT seems hard: it would imply lower bounds which are known hard to prove (because of a lot of barriers-diagonalization, algebraization, natural proofs, . . . ).

PIT is considered in mainly two ways:

• The black-box setting, in which one has access to a given polynomial f computed by a class of circuits only through evaluations of f over a set of points that the decider can choose.

• The white-box setting, in which the input of the problem is a circuit computing f itself.

We will focus on the white-box setting.

Remark 5.1

Observe that as evaluations of a polynomial f can be done e ciently given a circuit for f , a black-box PIT algorithm gives a white-box PIT algorithm working in roughly the same time as well. However, although white-box PIT algorithms should be easier to design, there is still no big di erence on what we can solve in black-box model compared to the white-box model.

This chapter is based on the three following publications:

PIT for UPT Circuits

In this section, we give two di erents deterministic polynomial-time algorithms for PIT for the polynomials computed by UPT circuits.

• The rst one 5.1.1 is based on the idea of the Hadamard product, used also by Arvind et al. [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF] in the context of non-commutative ABPs. The idea is to show that if a polynomial f has a small UPT circuit, then so does the polynomial F each of whose coe cients is the square of the corresponding coe cient of f . When the underlying eld is R, all coe cients of F are now non-negative and hence F is the zero polynomial if and only if it evaluates to a non-zero value when each of its input variables is substitured by the scalar 1. While this method can be extended to work over C as well, it is not clear how to use this in the context of, say, positive characteristic.

• The second approach 5.1.2 leads a deterministic PIT algorithm for UPT circuits over general elds by adapating an older algorithm for ABPs due to Raz and Shpilka [START_REF] Raz | Deterministic polynomial identity testing in non-commutative models[END_REF]. The idea behind this test is to compute, for each d , a small set of monomials of degree d whose "coe cients"1 determine the coe cients of all other monomials in the underlying polynomial. In particular, it reduces the problem of PIT for ABPs to computing the coe cient of a particular monomial, which can be done e ciently. A very similar idea turns out to work for UPT circuits as well.

Via Hadamard product

We will use the following binary operation over polynomials from [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF], which is to polynomials what intersection is to formal languages.

De nition 5.2: Hadamard product

Given two polynomials in

F X , f = m∈M(X)
α m m and g = m∈M(X)

β m m,
the Hadamard product of f and g, written f g, is:

f g = m∈M(X) α m β m m
In [START_REF] Arvind | Arithmetic circuits and the Hadamard product of polynomials[END_REF], a logspace algorithm is given which, on input two ABPs A and B, outputs a new ABP C computing the Hadamard product of the polynomials computed by A and B. Consequently, they observed that this result gives the following derandomization for PIT.

Theorem 5.3: [4]

The problem of polynomial identity testing for non-commutative algebraic branching programs over R is in P.

Here, we extend this result: we give a construction to perform the Hadamard product of two UPT circuits with the same shape. In other words, we prove that the class of UPT circuits of a given shape is stable under Hadamard product. As in the case of ABPs, it will provide a deterministic polynomial-time algorithm for PIT over UPT circuits over R.

Circuits will be assumed in normal form with multiplication fan-in 2, since Lemma 2.1 and Proposition 2.3 give explicit algorithms working in polynomial time to transform a UPT circuit with these two additional properties. The idea is then to create a circuit computing iteratively the Hadamard product of all pairs of addition gates of same type. The regularity of the parse tree will allow us to spread the Hadamard product layer by layer.

First, we state without proof the following easy lemma, saying essentially that if two polynomials admit two similar decomposition, then their Hadamard product respects a similar decomposition as well that can be computed from the Hadamard product of the smaller bricks.

Lemma 5.4

Let d, d ∈ N and let (f i ) 1≤i≤n and (g i ) 1≤i≤m be families of polynomials in F X with deg(f i ) = d and deg(g i ) = d . Set also (α i,j ) 1≤i≤n,1≤j≤m ∈ R nm and (β i,j ) 1≤i≤n,1≤j≤m ∈ R nm . Then:

  (i,j) α i,j f i g j     (i,j) β i,j f i g j   = (i,j),(k,l) α i,j β k,l (f i f k )(g j g l ).
Theorem 5.5: Hadamard product of two UPT circuits Let C and D be two UPT circuits in normal form, of same shape, and of size s and s , that compute two polynomials f and g. Then f g is computed by a UPT circuit of size at most ss ; moreover, this circuit can be constructed in polynomial time.

Proof. The new circuit computes the Hadamard product of all pairs (Φ 1 , Φ 2 ) ∈ C × D of addition gates of the same type. As the output gate in C and in D are of the same type (because C and D have the same shape), the new circuit will in particular compute the Hadamard product of f and g. If the degree of Φ 1 and Φ 2 is 1, then the Hadamard product is trivial since the gates compute variables.

Assume we have constructed the circuit up to layer i (that is, for each gate of degree less than or equal to i). We now show how to construct the layer (i + 1). Let Φ 1 ∈ C and Φ 2 ∈ D be two addition gates of degree (i + 1) and of same type. Because the circuits are UPT, Φ 1 (resp. Φ 2 ) computes a polynomial of the form h 1 = ( (i,j) α i,j f i g j ) (resp. h 2 = ( (i,j) β i,j f i g j )), where the f i are all of identical types, and where the g j are also all of identical types. Lemma 5.4 then shows how to compute h 1 h 2 from the previously computed f i f j and g i g j .

By induction, we thus construct the desired circuit layer by layer. Given a type, if there were i (resp. j) addition gates of this type in C (resp. in D), we have created exactly ij gates in the new circuit. Therefore, the total number of gates in the new circuit is no more than ss .

Corollary 5.6

There is a deterministic polynomial-time algorithm for PIT for polynomials computed by non-commutative UPT circuits over R.

Proof. Given f (x 1 , . . . , x n ) computed by a UPT circuit, construct the circuit which computes (f f )(x 1 , . . . , x n ) and evaluate it on (1, 1, . . . , 1). The output is the sum of the squares of the coe cients of f , therefore it is equal to 0 if and only if f is equal to the zero polynomial.

Remark 5.7

From a UPT circuit computing a polynomial f = m∈M(X) α m m over C, it is not hard to deduce a UPT circuit of same shape for the conjugate f = m∈M(X) ᾱm m. Therefore, a similar algorithm works over C, since

(f f ) = m∈M(X) |α m | 2 m.
We also obtain another corollary that is to be compared with the results of Section 2.4.2.

Corollary 5.8

Over R, in the non-commutative setting, computing the determinant with an UPT circuit is as hard as computing the permanent.

Proof. Observe that DET DET = PERM. Therefore, by Theorem 5.5, from a circuit computing the determinant, we can build in polynomial time a circuit computing the permanent.

Via Raz and Shpilka

In this section, we give another deterministic PIT algorithm for UPT circuits. Our algorithm, which is an adaptation of the algorithm of Raz and Shpilka [START_REF] Raz | Deterministic polynomial identity testing in non-commutative models[END_REF], is eld independent.

Theorem 5.9: Whitebox PIT for UPT circuits over all elds Let N, s ∈ N be parameters. There is a deterministic algorithm running in time poly(s) which, on input a UPT circuit C of size at most s over N variables, decides whether C computes the zero polynomial.

Proof. Let C be the input UPT circuit. Let T be the unique parse tree of the circuit C (it is easy to determine T from the circuit C by constructing an arbitrary parse formula of C and obtaining the parse tree corresponding to it). By Proposition 2.3 and Lemma 2.1, we can assume without loss of generality that C is in normal form and that T has fan-in bounded by 2.

For each node v ∈ T , let r v denote the number of (v, ×)-gates and t v the number of (v, +)-gates. We also identify the (v, ×)-gates with [r v ] and (v, +)gates with [t v ] in an arbitrary way. For any v ∈ T and any monomial m ∈ M deg(v) (X), let ξ v m ∈ F rv be de ned so that for any i ∈ [r v ], the ith entry ξ v m (i) of the vector ξ v m is the coe cient of the monomial m in the polynomial computed at the ith (v, ×) gate. Similarly, let χ v m ∈ F tv be the coe cient vector of the monomial m at the (v, +)-gates.

The idea of the algorithm is to compute, for each v ∈ T , a set B v,+ ⊆ M deg(v) (X) of size at most t v such that the set of vectors Bv,+ = {χ v m | m ∈ B v,+ } is a linearly independent set of vectors that generates all the vectors in Cv,

+ := {χ v m | m ∈ M deg(v) (X)} ⊆ F tv .
In particular, the polynomial computed by the circuit C is non-zero i for u being the root of T , there is a χ ∈ Bu,+ such that the entry of χ corresponding to the output gate of the circuit is non-zero. 2Thus, it su ces to compute the sets B v,+ and Bv,+ for each v ∈ T . In order to do so, it will also help to compute

B v,× ⊆ M deg(v) (X) and Bv,× = {ξ v m | m ∈ B v,×
} of size at most r v each so that the set of vectors Bv,× is a linearly independent set of vectors that generates all the vectors in Cv,× :

= {ξ v m | m ∈ M deg(v) (X)} ⊆ F rv .
The algorithm begins by choosing the sets B v,× for each leaf node v ∈ T . This may be done e ciently since deg(v) = 1 for each leaf node and hence the number of monomials m ∈ M deg(v) (X) is exactly |X| = N . By computing the coe cient vectors for each such monomial and performing Gaussian elimination, we can nd a suitable set B v,× as required in time poly(N, s) = poly(s).

To compute these bases for nodes higher up in T we proceed inductively as follows.

Sum gates. We rst describe how to construct B v,+ and Bv,+ given B v,× and Bv,× . Since each (v, +)-gate computes a linear combination of the (v, ×)-gates, we see that there is a matrix

M v ∈ F tv×rv such that χ v m = M v ξ v m for every m ∈ M deg(v) (X).
In particular, given sets B v,× and Bv,× as above, the set {χ v m | m ∈ B v,× } is a spanning set for the set Cv,+ . By Gaussian elimination, we can choose a basis Bv,+ ⊆ Bv,× in time poly(N, t v , r v ) = poly(s) and choose B v,+ to be the corresponding set of monomials.

Multiplication gates. Now let v ∈ T be an internal node with children u and w. We show how to compute B v,× and Bv,× given B u,+ , B w,+ , Bu,+ and Bw,+ .

Let r = r v and let Φ i be the ith (v, ×)-gate in C for each i ∈ [r]. Let Φ i and Φ i be the left and right children respectively of Φ i ; note that Φ i is a (u, +)-gate and Φ i a (w, +)-gate. For monomials m ∈ M deg(u) (X) and m ∈ M deg(w) (X), let λ u m and λ w m ∈ F r denote the coe cient vectors of m and m at the gates Φ i (i ∈ [r]) and Φ i (i ∈ [r]) respectively. 3 For any monomial m , each entry of the vector λ u m is the coe cient of the monomial m at some (u, +)-gate and hence an entry of the vector χ u m . In particular, λ u m = P u χ u m for some linear projection P u ; a similar fact is true for the λ w m as well. Thus, the vectors This completes the description of the algorithm and its analysis. From the analysis above, it is clear that the algorithm runs in time poly(s). We have shown Theorem 5.9.

{λ u m | m ∈ B u,+ } span all the vectors in {λ u m | m ∈ M deg(u) (X)}

PIT for sum of UPT circuits

In this section we will give a deterministic polynomial time algorithm for the PIT problem for the sum of k UPT circuits. Recently a deterministic algorithm was designed by Gurjar et al. [START_REF] Gurjar | Deterministic identity testing for sum of read-once oblivious arithmetic branching programs[END_REF] for polynomial identity testing of sum of ROABPs. Our algorithm uses a similar idea for the PIT of sum of UPT circuits. Our PIT algorithm is white box, i.e., it uses the structure of the underlying UPT circuits.

Proof idea

Say that circuit C i has shape T i for i ∈ [0, k] (it is easy to compute T i given each C i as observed in Section 5.1.2). By Proposition 2.3 and Lemma 2.1, we can assume without loss of generality that each C i is in normal form and that T i has fan-in bounded by 2.

Let P i be the polynomial computed by the UPT circuit C i for each 0 ≤ i ≤ k. Let P = -P 0 and let Q = k i=1 P i . Note that in this notation, checking whether k i=0 P i ≡ 0 is equivalent to checking whether P ≡ Q. We will present an algorithm to do this in four steps.

Step 1: We show how to e ciently build a small set of characterizing identities for the polynomial P . We will ensure that this set of identities is of size poly(N, s, d) = poly(s).

Step 2: We will then check whether all the identities hold for the polynomial Q as well. This is done by a call to the PIT algorithm for the sum of k UPT circuits. We will analyze the complexity of this step and bound it by s O(2 k ) .

Step 3: We will then show that if Q satis es all the characterizing identities, and moreover P and Q agree on a small set of coe cents, then the two polynomials are in fact identical.

Step 4: We will show that testing the equality of the above set of coe cients of P and Q can also be performed in time poly(s).

We now give a more detailed outline of the above steps with the statements of many formal claims. For the sake of exposition, we postpone the proofs of these intermediate claims to the end of this section.

Step 1: We now introduce some notation to formally de ne the characterizing identities for a polynomial de ned by a UPT circuit. Let I = [i, j] be an interval in [d], i.e., 1 ≤ i ≤ j ≤ d. If the interval is of size 1, i.e., I = [i, i], then we simply use i to denote it. Recall that M |I| (X) stands for all monomials of degree exactly |I|. For any r, let F X r be the set of homogeneous polynomials of degree r.

For any interval I in [d] and any monomial m ∈ M |I| (X), we de ne a map ∂ I,m : F X d → F X d-|I| , which is de ned as follows:

∂ I,m (P ) = m 1 ,m 2 :deg(m 1 )=i-1,deg(m 2 )=d-j α m 1 ,m,m 2 • m 1 • m 2 ,
where α m 1 ,m,m 2 is the coe cient of the monomial m 1 •m•m 2 in P . Informally, ∂ I,m is an operator which, when applied to a polynomial P of degree d, retains only those monomials of P (along with their coe cients) which have the monomial m at exactly the positions in the interval I, while substituting the constant 1 for all the variables in positions indexed by I.

Let T be T 0 , the shape of the parse tree corresponding to P . For each v ∈ T , we use

I v to denote the interval [pos(v), pos(v) + deg(v) -1] where type(v) = (pos(v), deg(v)) is as de ned in Section 1.3.
Starting from the leaves, we start building identities corresponding to each of the nodes in the tree T . Formally, we show the following inductive claim.

Claim 5.11

There is an algorithm that runs in time poly(s) that, for every node v in T , computes a set The algorithm for the above is almost identical to the PIT algorithm in Section 5.1.2. Note that the size of the output of the algorithm is poly(N, s, d) = poly(s).

B v ⊆ M deg(v) (X) such that |B v | ≤
We will prove this claim later.

Step 2: Let us assume that the above claim holds. Now if P = Q, then the same set of identities must also hold for the polynomial Q. We now describe how one can check that Q satis es these identities (the algorithm can safely reject if some identity is not satis ed by Q). Suppose we have all the identities for P along with the sets B v for all nodes v in T and all the coe cients c v m ,m m ∈Bu,w,m∈Bv again for every node v in T .

In general, we need to check identities of the following form when v is an internal node with children u, w: ∂ Iv, m(Q) = m∈Bv c m,m • ∂ Iv,m (Q) for each m ∈ B u,w . (A similar check has to be made when v is a leaf node.)

Recall that Q = k i=1 P i . Therefore, we can rewrite the above identity as follows:

k i=1 ∂ Iv, m(P i ) = m∈Bv c m,m • k i=1 ∂ Iv,m (P i ).

Rearranging this we get

k i=1 m∈Bv c m,m • ∂ Iv,m (P i ) -∂ Iv, m(P i ) ≡ 0.
(5.1)

We rst show that each of the k terms in the above sum has a small UPT circuit.

Claim 5.12

For each i ∈ [k], m∈Bv c m,m • ∂ Iv,m (P i ) -∂ Iv, m(P i
) can be computed by a UPT circuit of size at most O(s 2 ). Further, these circuits can be constructed in time poly(k, s).

By the above claim, Equation 5.1 reduces to an identity testing question for the sum of at most k UPT circuits, and hence can be solved recursively. Finally, when we get to the case that k = 1, we simply appeal to our result from Section 5.1.2. Using Claim 5.12 (which we will prove later) and the algorithm from Section 5.1.2 for a single UPT circuit, we see that this step can be performed in time

(s 2 ) O(2 k-1 ) = s O(2 k ) .
Step 3: Now suppose all the above checks succeed. That is, we have been able to ensure that the following statements hold:

• For every leaf node v, x ∈ X, m ∈ B v and i such that

I v = i: ∂ i,x (P ) = m∈Bv c v x,m • ∂ i,m (P ) and ∂ i,x (Q) = m∈Bv c v x,m • ∂ i,m (Q). (5.2)
• For every internal node v with children u, w, for every m ∈ B v and m ∈ B u,w we have:

∂ Iv,m (P ) = m∈Bv c v m ,m • ∂ Iv,m (P ) and ∂ Iv,m (Q) = m∈Bv c v m ,m • ∂ Iv,m (Q) (5.
∂ Iv,m (P ) = m∈Bv c v m ,m • ∂ Iv,m (P ) and ∂ Iv,m (Q) = m∈Bv c v m ,m • ∂ Iv,m (Q).
Note that (5.2) and ( 5.3) only give us a polynomially large set of common identities satis ed by P and Q. The content of Claim 5.13 is that we can use these to infer an exponentially (since the size of M |I| (X) is exponential) large set of common identitites for P and Q.

We will present the proof of Claim 5.13 later. For now let us assume this claim. Now, let v 0 be the root of T . We check that for each m ∈ B v 0 , ∂ Again, if any of these coe cients are not equal, we can safely reject. However, if these checks succeed, using Claim 5.13, we can see that all the coe cients of polynomials P and Q are equal and hence they are the same polynomial. In this case, we accept.

Step 4: As noted above, ∂ [d],m (P ) and ∂ [d],m (Q) are simply coe cients of the monomial m in the polynomials P and Q respectively. We use the following lemma proved in [START_REF] Arvind | New results on noncommutative and commutative polynomial identity testing[END_REF] to compute these coe cients. Lemma 5.14: [START_REF] Arvind | New results on noncommutative and commutative polynomial identity testing[END_REF] Given access to a non-commutative circuit C of size s which is computing the polynomial f of degree d and given a monomial m, the coe cient of m in f can be computed in time polynomial in s, d.

This completes the description of the four main steps. We now prove the claims used in these steps.

Proof sketch of Claim 5.11. We follow exactly the procedure in the PIT algorithm for UPT circuits in Section 5.1.2 and compute sets B v,+ , Bv,+ , B v,× , and Bv,× exactly as in that algorithm. We will take our sets B v to be the sets B v,× for each v ∈ T . Clearly |B v | ≤ s for each v.

To compute the coe cients c v m ,m ∈ F, we proceed as follows. For any leaf node v ∈ T , y ∈ X and x ∈ B v , we choose c v y,x such that we have ξ v y = x∈Bv c v y,x ξ v x . For an internal node v ∈ T with children u and w, and any m ∈ B u • B w , we note that by the de nition of B v,× in the proof of Theorem 5.9, each m ∈ B u • B w , ξ v m lies in Span( Bv,× ) and hence we can nd c v m ,m such that

ξ v m = m∈Bv c v m ,m ξ v m .
This concludes the description of the algorithm. To show that this works as intended, it su ces to prove the following claim.

B ⊆ M t (X), if ξ v m = m∈B c v m ,m • ξ v m then ∂ I,m (P ) = m∈B c v m ,m • ∂ I,m (P ).
Proof. Let v ∈ T be such that type(v) = (t, p), where t is deg(v) and p is pos(v). Let K v be the number of nodes in C 0 corresponding to v. For any polynomial computed by a UPT circuit, Chapter 2 gives the following decomposition lemma, which we will recall and use below.

Lemma 5.16

Let P be a polynomial of degree d computed by a UPT circuit of size s with a parse tree T . Let (t, p) be the type of a node v ∈ T and let K v be the number of gates in C of that type. Let f 1 , f 2 , . . . , f Kv be the polynomials computed by these gates, each of degree t. Then P can be written as

P = Kv j=1 f j × p h j , where ∀j, 1 ≤ j ≤ K v deg(h j ) = d -t.
Using the above lemma our claim follows. Given below is the detailed proof of the claim.

∂ I,m (P ) = ∂ I,m Kv j=1 f j × p h j (a) = ∂ I,m Kv j=1 ξ v m (j) • m × p h j + m =m ξ v m(j) • m × p h j = ∂ I,m Kv j=1 ξ v m (j) • m × p h j + ∂ I,m m =m ξ v m(j) • m × p h j = Kv j=1 ξ v m (j) • 1 × p h j + : 0 ∂ I,m m =m ξ v m(j) • m × p h j = Kv j=1 m∈B c v m ,m • ξ v m (j) × p h j (b) = m∈B c v m ,m Kv j=1 ξ v m (j) × p h j = m∈B c v m ,m • ∂ I,m Kv j=1 ξ v m (j) • m × p h j = m∈B c v m ,m • ∂ I,m Kv j=1 ξ v m (j) • m × p h j + ∂ I,m m =m ξ v m(j) • m × p h j = m∈B c v m ,m • ∂ I,m Kv j=1 ξ v m (j) • m × p h j + m =m ξ v m(j) • m × p h j = m∈B c v m ,m • ∂ I,m (P )
The identity (a) holds due to Lemma 5.16. The identity (b) follows due to our assumption in the statement of the claim. The other identities follow due to the de nition and/or by the linearity of ∂ I,m .

Proof of Claim 5.12. We know that P i has a UPT circuit C i with shape T i . Say we x a monomial m and an interval I = [i 1 , i 2 ] such that deg(m) = |I|. Let T i be the tree obtained from T i by deleting all nodes u such that I u ⊆ I. We claim that ∂ I,m (P i ) is computed by a UPT circuit of size at most s and shape T i .

Consider any leaf node w ∈ T i such that pos(w) = i 1 + -1 ∈ I. We consider each (w, ×) gate Φ of C (note that these are input gates) and replace the gate by 0 if the variable x labelling Φ is the th variable in m and 0 otherwise. This gives a non-commutative arithmetic circuit where some leaves are labelled by constants. However, these constants are easily eliminated inductively as follows. For any × gate Φ which has a child labelled by a constant α, we can remove the child and multiply the label of each wire leaving Φ by α; for any + gate Φ which has a child labelled by a constant, it must be the case that all its children are labelled by constants (this follows from the UPT restriction) and hence the + gate can now be labelled by a constant as well. Continuing this way, all the gates with constant labels are eliminated.

It can be checked that the circuit thus obtained is a UPT circuit of size at most s and shape T i computing ∂ I,m (P i ). Returning to the statement of the claim, we have therefore shown that each of ∂ Iv, m(P i ) and ∂ Iv,m (P i ) can be computed by a UPT circuit of size s and shape T i .

Therefore, we can compute

m∈Bv c m,m • ∂ Iv,m (P i ) -∂ Iv, m(P i ) by a linear combination of the O(s) UPT circuits computing ∂ Iv,m (P ) for m ∈ B v ∪ { m}.
Overall, this gives a UPT circuit of size O(s 2 ). Since the above proof is constructive, we can actually nd this circuit in time poly(s).

Proof of Claim 5.13. We will prove this claim by induction on |I v |.

The base case is |I

v | = 1 which follows directly from Equation 5.2. Suppose |I v | = t > 1.
Then v is an internal node in T . Let u, w be its two children. This implies that

I v = I u ∪ I w . Let |I u | = t 1 , |I w | = t 2 . Note that t 1 , t 2 < t.
We wish to prove that for any m

∈ M |Iv| (X), ∂ Iv,m (P ) = m∈Bv c v m ,m • ∂ Iv,m (P ) and ∂ Iv,m (Q) = m∈Bv c v m ,m • ∂ Iv,m (Q) for a suitable choice of c v m ,m . Note that this already follows from (5.3) if m ∈ B u • B w . So we assume that m ∈ B u • B w . Let m = m 1 • m 2 , where deg(m 1 ) = t 1 and deg(m 2 ) = t 2 . Let R be either P or Q. ∂ Iv,m (R) = ∂ Iu∪Iw,m 1 m 2 (R) = ∂ Iu,m 1 • ∂ Iw,m 2 (R) (a) = ∂ Iu,m 1 • m∈Bw c w m 2 ,m • ∂ Iw,m (R) (b) = m∈Bw c w m 2 ,m • ∂ Iu,m 1 • ∂ Iw,m (R) = m∈Bw c w m 2 ,m • ∂ Iw-|Iu|,m • ∂ Iu,m 1 (R) (a) = m∈Bw c w m 2 ,m m∈Bu c u m 1 ,m • ∂ Iw-|Iu|,m • ∂ Iu,m (R) (b) = m∈Bw,m∈Bu c u m 1 ,m • c w m 2 ,m • ∂ Iu∪Iw,mm (R) (a) = m•m∈Bu,w c u m 1 ,m • c w m 2 ,m • ∂ Iv,mm (R) = m∈Bv m,m c u m 1 ,m • c w m 2 ,m • c v mm,m • ∂ Iv,m (R). (c)
The equalities marked by (a) follow due to Observation 5.17 below. The equalities marked (b) follow due to the induction hypothesis. Finally, the equality marked (c) follows due to Equation 5.3.

The above implies the inductive claim with c v m ,m de ned to be

m∈Bu,m∈Bw c u m 1 ,m • c w m 2 ,m • c v mm,m .
Since the choice of c v m ,m is the same for both P and Q, we are done.

Observation 5.17

Let I, J be two contiguous intervals in [d] such that I precedes J, i.e., if

I = [i 1 , i 2 ] and J = [j 1 , j 2 ] then 1 ≤ i 1 , i 2 + 1 = j 1 and j 2 ≤ d. Then ∂ I∪J,m 1 m 2 = ∂ J-|I|,m 2 • ∂ I,m 1 = ∂ I,m 1 • ∂ J,m 2 ,

Overview

This chapter revisits Nisan's result about ABPs and results from Chapter 2 about UPT circuits. The conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.

The key notion for understanding the minimisation question of weighted automata is the Hankel matrix: the rank of the Hankel matrix of a word or tree series is exactly the size of the smallest weighted automaton recognising this series. For automata over words, the correspondence we establish allows us to rephrase Nisan's celebrated tight bounds for algebraic branching programs. We extend this result by considering automata over trees and obtain tight bounds for all circuits with unique parse trees (whereas tight bounds were previously obtained only for UPT circuits in some normal form, a constraint that can increase a lot the size of the circuits.).

Correspondence with weighted automata. We build a bridge between automata theory and arithmetic complexity. The correspondence is summarised in this table.

Arithmetic complexity

Weighted automata variable letter monomial word polynomial word series or tree series algebraic branching program layered weighted automaton over words circuit with unique parse trees layered weighted automaton over trees In Section 6.1, we show that Nisan's results about algebraic branching programs follow from theorems coming from automata theory. We introduce weighted automata (WA) over words, and show the following correspondence:

• any ABP can be seen as a WA,

• under some syntactic restriction called layered, a WA can be seen as an ABP,

• for a given word series f , the size of the minimal WA recognising f is the rank of the Hankel matrix of f ,

• if the word series f represents a homogeneous polynomial P , then the minimal WA recognising f is an ABP computing P .

This gives an alternative approach to state and prove Nisan's result about minimal ABPs.

Our main technical contribution is to extend this result from ABPs to UPT circuits in Section 6.2. To this end we show a more subtle and involved correspondence between UPT circuits and weighted automata over trees. Our main result is tight bounds on the size of a UPT circuit computing a given polynomial.

A similar result was obtained in Chapter 2 for UPT circuits in normal form; here we remove this assumption, leading to an exponential improvement in some examples as explained in Section 6.3. This chapter is based on the following publication:

• Nathanaël Fijalkow, Guillaume Lagarde, and Pierre Ohlmann. Tight bounds using hankel matrix for arithmetic circuits with unique parse trees. Electronic Colloquium on Computational Complexity (ECCC), 25:38, 2018

Tight bounds for algebraic branching programs

We give here a de nition of ABPs that slightly di ers from Chapter 3. The two can easily be proved to be equivalent. However, this one is more convenient in order to state the correspondence with weighted automata.

De nition 6.1

An algebraic branching program (ABP) is a directed acyclic graph with a distinguished source vertex s. The vertices are partitioned into d + 1 layers, starting with layer 0 which contains only the vertex s, and ending in layer d.

Each edge is between two consecutive layers and is labeled by a homogeneous linear function over the variables X and real-valued constants. Each vertex in the last layer has a real output value. See Figure 6.2. A path from s to a vertex in layer d induces a homogeneous polynomial of degree d obtained by multiplying all the labels of the edges and the output value. An algebraic branching program C computes a homogeneous polynomial P C de ned by summing the polynomials over all paths from s to vertices of the layer d.

The size of an ABP is its number of vertices.

One of the motivations for studying algebraic branching programs is that they capture matrix multiplication (cf Chapter 4). They can be proved to be equivalent to left skew circuits (i.e., circuits for which the left argument of any multiplication gate is an input).

Nisan's theorem

Nisan's theorem gives for a homogeneous polynomial P the size of the smallest ABP computing P . Let d be the degree of P . For each i ∈ {0, . . . , d}, we de ne a matrix M P,i as follows. The rows are indexed by monomials of degree i, and the columns by monomials of degree d -i (there are |X| i rows and |X| d-i columns). Then for u a monomial of degree i and v of degree d -i, de ne M P,i (u, v) to be the coe cient of uv in P . We now state Nisan's theorem (already introduced without any formal statement in Chapter 1)

• Any ABP computing P has size at least n,

• There exists an ABP computing P of size exactly n.

In this section, we give an alternative proof of this theorem using a correspondence with weighted automata over nite words. The number n will appear as the rank of a single matrix called the Hankel matrix, which will in our case consist of d + 1 independent blocks, hence the summation in Nisan's theorem.

The point of this section is to serve as an introduction to our main result in Section 6.2. Indeed, we will prove a theorem extending Nisan's theorem to a wider class of arithmetic circuits, namely circuits with unique parse trees, following the same schema. In this section we deal with weighted automata over words, in the next section we will consider weighted automata over trees.

Weighted automata over words

An element of X * can be seen either as a monomial over the variables X, as in ABPs, or as a ( nite) word over the alphabet X. A word series is a function f : X * → R.

A polynomial P with variables in X can be seen as a word series X * → R which we also write P , such that P (w) is the coe cient of w in P .

De nition 6.3

A weighted automaton over words (WA) is given by • a nite set of states Q,

• an initial state q 0 ∈ Q, • a transition function ∆ : Q × X × Q → R, • an output function F : Q → R.
The usual de nition proceeds with introducing runs, explaining that along a run the weights of the transitions are multiplied, and that the value of a word is the sum of the values of its accepting runs. We use here a more algebraic equivalent de nition. Equivalently, we see the transition function as ∆ : X → R Q×Q , i.e., ∆(x) is a matrix de ned by ∆(x)(p, q) = ∆(p, x, q). The initial state q 0 (seen as an element of R Q ) and the transition function induce ∆ * : X * → R Q de ned by ∆ * (ε) = q 0 and ∆ * (wx) = ∆ * (w) • ∆(x), where • is matrix multiplication. Similarly, we see F as a vector in R Q .

The weighted automaton A recognises the word series f A :

X * → R de ned by f A (w) = ∆ * (w) • F, where • is the dot product in R Q .
The size of a WA is its number of states.

Algebraic branching programs as weighted automata over words

ABPs form a subclass of WA over words that we de ne now. Let f : X * → R, we de ne the (in nite) Hankel matrix

H (f ) ∈ R X * × R X * ,
whose rows and columns are indexed by words, by

H (f ) (u, v) = f (u • v).
The notion of Hankel matrix and the rank of a formal non-commutative series were introduced by Carlyle and Paz [START_REF] Carlyle | Realizations by stochastic nite automata[END_REF]. One of the main results of Fliess' PhD thesis was the following theorem [START_REF] Fliess | Matrices de Hankel[END_REF]. Theorem 6.7

Let f : X * → R be a word series such that rank(H (f ) ) is nite.

• Any WA recognising f has size at least rank(H (f ) ).

• There exists a WA recognising f of size exactly rank(H (f ) ). This article is in French. However, one can nd great exposition of the ideas in the handbooks of Berstel and Reutenauer [START_REF] Berstel | Noncommutative Rational Series with Applications[END_REF] and Sakarovitch [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]. The proof of the second item gives a construction of the WA recognising f that we detail now as we will need it to prove Theorem 6.2.

Recall that the rows of H (f ) are indexed by words in X * . For u ∈ X * , let H (f ) u be the row corresponding to u in H (f ) , which we see as

H (f ) u ∈ R X * . Let Q ⊆ X * But since H (P )
ux ∈ V |u|+1 and the vector spaces V 0 , . . . , V d are in direct sum, it follows that for v ∈ Q of length i = |u| + 1 we have v∈Q i ∆(u, x, v)H

(P ) v = 0.

Since the vectors

H (P ) v | v ∈ Q i are
linearly independent, this implies that ∆(u, x, v) = 0. Thus the property (2) is satis ed.

We now explain how to obtain the proof of Nisan's theorem (Theorem 6.2) from the correspondence. Let P be a homogeneous polynomial of degree d. Thanks to the rst item of Theorem 6.7 any WA recognising P has size at least rank(H (P ) ), and thanks to the rst item of Lemma 6.5 this implies that any ABP computing P has size at least rank(H (P ) ). Thanks to the second item of Theorem 6.7, there exists a WA recognising P of size rank(H (P ) ), and thanks to Lemma 6.8, it is d-layered. Thanks to the second item of Lemma 6.5, it induces an ABP computing P of size rank(H (P ) ).

Let us have a closer look at the Hankel matrix of P for a homogeneous polynomial P of degree d. Most of the matrix is lled with zeros, except for d + 1 independent blocks, which are precisely the matrices M P,i for i ∈ {0, . . . , d}. This explains the summation in Nisan's statement of the theorem, since rank(H (P ) ) = d i=0 rank(M P,i ). As we shall see in the next section, when considering UPT circuits the blocks will no longer be independent, allowing to share the result of partial computations.

Tight bounds for circuits with unique parse trees

In this section, we allow circuits to have multiple output in order to make the correspondence with weighted automata over trees cleaner. To prevent any confusion, we state below the de nition that will be used in the rest of the chapter.

De nition 6.9

A circuit is a directed acyclic graph whose vertices, called gates, are of four di erent types.

• The input gates have indegree zero and are labeled with variables x ∈ X.

• The addition gates have unbounded fan-in and perform a linear combination of their inputs, with the associated coe cients α in R given on the edges.

• The multiplication gates have fan-in two, their arguments are ordered and the multiplication is interpreted according to this order (the left argument is multiplied before the right argument).

• The output gates have outdegree zero and are labeled with a real output value.

The size of an algebraic circuit is its number of addition gates.

While this de nition allows multiple output gates, the circuits we construct only have one single output.

The reason for not taking the multiplication gates into account is because of Lemma 2.5 from Chapter 2, proving that for UPT circuits (which are the only circuits we consider), if s is the number of addition gates, then the number of multiplication gates can always be bounded by s 2 . Therefore, the number of addition gates gives a pretty good idea on the total size of UPT circuits. Observe also that the situation is similar in Nisan's work for ABPs as the vertices of an ABP correspond exactly to addition gates when this ABP is converted into circuits.

We also normalise the circuits by requiring that all paths alternate between addition gates and multiplication gates and start and nish with an addition gate, which increases the size by at most a linear factor.

Statement of the result

Shapes are binary trees without any labels, we use T, T , . . . for shapes. They can be built inductively: a leaf is a shape, and given two shapes T 1 , T 2 , the shape T 1 • T 2 is a root with T 1 as left subtree and T 2 as right subtree.

We also consider labeled trees (later refered to as trees), which are binary trees whose leaves are labeled by variables x ∈ X. We let Tree(X) denote the set of trees, and use t, t , . . . for them. Trees can be built inductively similarly as shapes, except that the basic trees are variables x ∈ X. A tree series is a function f : Tree(X) → R.

For t ∈ Tree(X), we let t be the underlying shape of t, and for a shape T , we let Tree(X, T ) denote the set of trees t such that t = T . We de ne the Hankel matrix for tree series. We rst need the notion of contexts: a context C is an element of Tree(X ∪ { }) with a unique leaf labeled . We let Context(X) denote the set of contexts, and use C, C , . . . for them. A context C and a tree t can be composed into a tree C • t by replacing the placeholder by the tree t.

De nition 6.10

Let f : Tree(X) → R, we de ne the (in nite) Hankel matrix

H (f ) ∈ R Tree(X) × R Context(X) by H (f ) (t, C) = f (C • t).
Our main theorem gives tight bounds on the size of UPT circuits. More precisely, we consider a homogeneous polynomial P of degree d and a shape T , and nd the size of the smallest UPT circuit with shape T computing P .

A necessary condition for the existence of such a circuit is that the number of leaves of T is d. Under this condition a homogeneous polynomial P of degree d and a shape T induce a function f P,T : Tree(X) → R: for t ∈ Tree(X, T ), we see t as a monomial and de ne f P,T (t) as the coe cient of this monomial in P , the function f P,T is zero outside of Tree(X, T ). We refer to Figure 6.5 for an illustration of this de nition.

For the sake of simplicity we use H (P,T ) instead of H (f P,T ) .

Our main result is the following: Figure 6.5: Given the shape T displayed on the left hand side, the polynomial P = xyx+4x 2 y +2y 3 can be seen as the tree series P : Tree(X) → R associating with these three trees the values indicated below them and zero to all other trees. Theorem 6.11

Let P be a homogeneous polynomial of degree d, and T be a shape with d leaves.

• Any UPT circuit for P with shape T has size at least rank(H (P,T ) ),

• There exists a UPT circuit with shape T computing P of size exactly rank(H (P,T ) ).

Weighted automata over trees

De nition 6.12: weighted automaton over trees A weighted automaton over trees (WA) is given by • a nite set of states Q,

• an initial function ι :

X × Q → R, • a transition function ∆ : Q × Q × Q → R, • an output function F : Q → R.
Equivalently, we write the transition function as a bilinear function ∆ :

R Q × R Q → R Q de ned by ∆(p, q)(r) = ∆(p, q, r).
The initial and transition functions induce

∆ * : Tree(X) → R Q de ned by ∆ * (x) = ι(x) ∈ R Q and ∆ * (t 1 • t 2 ) = ∆(∆ * (t 1 ), ∆ * (t 2 )).
The weighted automaton A recognises the tree series f A : Tree(X) → R de ned by

f A (t) = ∆ * (t) • F,
where • is the dot product in R Q .

UPT circuits as weighted automata over trees

UPT circuits form a subclass of WA over trees that we de ne now.

Let T be a shape and v a node of T , we let T v be the subshape of T rooted in v. We let

[T ] denote {T v | v node of T }.
De nition 6.13

A weighted automaton A = (Q, ι, ∆, F ) is T -layered if there exists a map m : Q → [T ] such that (1) for all x ∈ X, if ι(x, q) = 0 then m(q) is the shape reduced to a single leaf, (2)
for all q, q 1 , q 2 ∈ Q, if ∆(q, q 1 , q 2 ) = 0, then m(q) = m(q 1 ) • m(q 2 ),

(3) for all q ∈ Q, if F (q) = 0 then m(q) = T . Lemma 6.14

• For all UPT C with shape T , there exists a T -layered WA over trees A of the same size such that f A = P C .

• For all WA over trees A which is T -layered, there exists a UPT C with shape T of the same size such that P C = f A .

Proof. Let C be a UPT circuit. We de ne a WA over trees as follows. The set of states is the set of addition gates of C. The initial function de ned by ι(g, x) is the label of the edge coming from an input gate with label x to g, and 0 if there is no such edge. The output function de ned by F (g) is the label of g if g is an output gate, and 0 otherwise. The transition function is de ned as follows: ∆(g 1 , g 2 , g) is the label of (the unique) multiplication gate g using g 1 and g 2 as arguments and g argument of g. Then f A = P C . For the second claim, the de nition of layered WA over trees exactly says that the above construction can be reverted. We de ne m : Q → [T ] by m(t) = t. To see that indeed t ∈ [T ], we remark that if t / ∈ [T ] then H (P,T ) t = 0, hence t cannot be in Q. The conditions (1) and ( 3) are clearly satis ed, so we focus on (2).

For T ∈ [T ], let V T denote the vector space spanned by

H (P,T ) t | t = T .
We claim that the subspaces

V T for T ∈ [T ] are in direct sum. It follows from the fact that if L ∈ V T , then for a context C such that C • T = T , we have L(C ) = 0.
Let t 1 , t 2 ∈ Q. By de nition

H (P,T ) t 1 •t 2 = t∈Q ∆(t 1 , t 2 , t)H (P,T ) t = T ∈[T ] t∈Q | t=T ∆(t 1 , t 2 , t)H (P,T ) t ∈V T .
Since H

(P,T )

t 1 •t 2 ∈ V t 1 • t 2 and the vector spaces V T for T ∈ [T ] are in direct sum, it follows that for T ∈ [T ] such that t 1 • t 2 = T we have t∈Q | t=T ∆(t 1 , t 2 , t)H (P,T ) t = 0.

Since the vectors H (P,T ) t

| t ∈ Q are linearly independent, this implies that ∆(t 1 , t 2 , t) = 0. Thus Property (2) is satis ed.

We now prove our main result, Theorem 6.11. Let P be a homogeneous polynomial of degree d and T a shape with d leaves. Thanks to the rst item of Theorem 6.15 any WA recognising P has size at least rank(H (P,T ) ), and thanks to the rst item of Lemma 6.14 this implies that any UPT circuit with shape T computing P has size at least rank(H (P,T ) ). Thanks to the second item of Theorem 6.15, there exists a WA recognising P of size rank(H (P,T ) ), and thanks to Lemma 6.16, it is T -layered. Thanks to the second item of Lemma 6.5, it induces a UPT circuit with shape T computing P of size rank(H (P,T ) ).

Applications

In this section, we apply our main theorem to explicit polynomials. The rst example illustrates the di erence between general UPT circuits and UPT circuits in normal form as studied in Chapter 2, witnessing an exponential gap between the two models. Our second example is the permanent.

An exponential gap between UPT circuits and their normal restrictions

Consider the polynomial P (x 1 , x 2 , x 3 , x 4 ) = x 1 x 2 x 3 x 4 + x 3 x 4 x 1 x 2 and let T be a complete binary tree with 4 leaves. Figure 6.6 shows the smallest UPT circuit with shape T computing P given by the construction of Theorem 6.11. It witnesses an interesting phenomenon: both computations x 1 x 2 and x 3 x 4 are shared and used twice each. This is captured in the Hankel matrix by observing that two blocks contribute only by one to the rank since the two rows are identical. Informally they correspond to isomorphic subshapes. This circuit is not in the normal form studied in Chapter 2, which does not allow such shared computations. Figure 6.6: On the left hand side, the smallest UPT circuit computing x 1 x 2 x 3 x 4 + x 3 x 4 x 1 x 2 . We have not depicted some addition gates to keep the gure simple. On the right hand side a sample of the corresponding Hankel matrix. The blue rectangle corresponds to an interaction between two di erent type of contexts.

We push this further to obtain an exponential gap between UPT circuits and UPT circuits in normal form. Let n ∈ N and T be the complete binary tree with 2 n leaves. Consider the polynomial P (x) = x 2 n . Inspecting the Hankel matrix (see Figure 6.8) yields rank(H (P,T ) ) = n. Thus thanks to Theorem 6.11 the smallest UPT circuit with shape T computing P has exactly n addition gates, illustrated in Figure 6.7. The characterisation obtained in Chapter 2 shows that the smallest UPT circuit with shape T in normal form has 2 n+1 -1 addition gates, yielding an exponential gap. Note however that such a large gap can only be obtained for circuits with large degrees. Figure 6.7: An example of a UPT circuit computing x 2 n . The circuit is on the left hand side and its shape on the right hand side, it is the complete binary tree of height n.

The permanent

We look at the permanent polynomial

P = σ∈Sn n i=1 x i,σ(i) over the n 2 variables X = {x i,j | i, j ∈ [n]}.
We examine the Hankel matrix H (P,T ) for any shape T with n leaves and obtain the size of the smallest UPT circuit of shape T which computes the permanent.

For v a node of T , let d v be the number of leaves in T v .

Lemma 6.17 Proof. Let T be a shape with n leaves { 1 , . . . , n } and v ∈ T be a node in T . We let i v denote the leftmost index of a leaf in T v , i.e., T v has leaves iv , iv+1 , . . . , iv+dv-1 . Moreover, let S be a subset of {1, . . . , n} of size d v .

We argue that in the Hankel matrix there are v∈T n dv independent blocks, and that the set of these blocks is in bijection with pairs (v, S) where v is a node of T and S a subset of size d v .

Let S = {s 1 , . . . , s dv } and its complement {1, . . . , n} \ S = {q 1 , . . . , q n-dv }. Let U S v be the set of labelings of the leaves iv , . . . , iv+dv-1 of T v by variables x iv,σ(s 1 ) , . . . , x iv+dv-1,σ(s dv ) in this order, ranging over permutations σ of S.

Likewise, we let C denote the unlabeled context obtained by removing T v from node v in T and replacing it by a placeholder , and put B S v to be the set of labelings of all leaves but those in T v of C by the variables x 1,τ (q 1 ) , . . . , x iv-1,τ (q iv -1 ) , x iv+dv,τ (q iv ) , . . . , x n,τ (q n-dv ) , ranging over permutations τ of the complement of S.

For any σ, τ , the corresponding labeled tree t σ ∈ U S v and labeled context

c τ ∈ B S v are such that f P (c τ [t σ ]) = H (P,T ) (t σ , c τ ) = 1, inducing a block of 1's indexed by U S v × B S v in H (P,T ) .
Conversely, we see that any (t, c) ∈ Tree(X)×Context(X) such that H (P,T ) (t, c) = 1 is in some U S v × B S v , and that for any two distinct (S, v), (S , v ), both U S v and U S v and B S v and B S v are disjoint, hence the blocks cover all 1's in H (P,T ) and are independent. This concludes.

We instantiate this result for two shapes:

• If T is a comb, this yields that the smallest ABP computing the permanent has size

n i=1 n i + n i=1 n 0 = 2 n + n, • If T is
a full binary tree of depth k = log(n), this yields that the smallest UPT circuit with this shape computing the permanent has size k i=0

2 i 2 k 2 k-i = Θ( 2 n √ n ).
Hence the latter UPT circuit is more e cient.

However, recall that in our model circuits have unbounded fan-in on addition gates. In this setting a natural and a more accurate estimation of the size of the circuit (or number of operations that are performed) is to count directly the total number of arguments of addition gates. Examining more closely the automata and the circuits we construct, we obtain the following formula that gives the number of such edges for a UPT circuit with shape T computing the permanent

v∈T d v f v n d v ,
where f v is the number of leaves in T v , with v an argument of v (indeed, it does not depend upon which argument is chosen). Note that our optimality result does not apply to this new measure, but we can still consider the size of the circuits constructed by Theorem 6.11. It yields an ABP of size n2 n-1 + n, which asymptotically matches the well known optimal ABP for the permanent that is asymptotically as fast as Ryser formula. For the case of the full binary tree, we obtain a UPT circuit of size Θ(2

Overview

This part gives a positive answer to the "one-bit catastrophe" question-introduced by Jack Lutz in the late '90s-that asks whether an in nite word compressible by LZ'78 can become incompressible by adding a single bit in front of it. In Chapter 7 we introduce all the notions related to LZ'78 and state our main results. Chapter 8 is devoted to the proof of the upper bound (the "not a tragedy" part), whereas the next chapters are about lower bounds. In Chapter 9 we explicitly give a word, based on de Bruijn sequences, whose compression ratio is optimal but the addition of a single bit deteriorates the compression ratio as much as the aforementioned upper bound allows to. That is a particular case of the result of Chapter 10 but we include it anyway for three reasons: it illustrates the main ideas without obscuring them with too many technical details; the construction is more explicit; and the bounds are better.

In Chapter 10 we prove our main theorem on nite words (Theorem 7.10). It requires the existence of a family of "de Bruijn-style" words shown in Section 10.1 thanks to the probabilistic method. Finally, Chapter 11 uses the previous results to prove the "original" one-bit catastrophe, namely on in nite words (Theorem 7.6). The whole part is based on the following publication:

• Guillaume Lagarde and Sylvain Perifel. Lempel-ziv: a "one-bit catastrophe" but not a tragedy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1478-1495, 2018

Chapter 7

Introduction

Suppose you compressed a le using your favorite compression algorithm, but you realize there was a typo that makes you add a single bit to the original le. Compress it again and you get a much larger compressed le, for a onebit di erence only between the original les. Most compression algorithms fortunately do not have this strange behaviour; but if your favorite compression algorithm is called LZ'78, one of the most famous and studied of them, then this surprising scenario might well happen. . . In rough terms, that is what we show in this second part of the thesis, thus closing a question advertised by Jack Lutz under the name "one-bit catastrophe" and explicitly stated for instance in papers of Lathrop and Strauss [START_REF] Lathrop | A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data[END_REF], Pierce II and Shields [START_REF] Pierce | Sequences Incompressible by SLZ (LZW), Yet Fully Compressible by ULZ[END_REF], as well as more recently by López-Valdés [START_REF] Lopéz-Valdés | Lempel-Ziv dimension for Lempel-Ziv compression[END_REF].

Ziv-Lempel algorithms

In the paper [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] where they introduce their second compression algorithm LZ'78, Ziv and Lempel analyse its performance in terms of nite-state lossless compressors and show it achieves the best possible compression ratio. Together with its cousin algorithm LZ'77 [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF], this generic lossless compressor has paved the way to many dictionary coders, some of them still widely used in practice today. For instance, the deflate algorithm at the heart of the open source compression program gzip uses a combination of LZ'77 and Hu man coding; or the image format GIF is based on a version of LZ'78. As another example, methods for e cient access to large compressed data on the internet based on Ziv-Lempel algorithms have been proposed [START_REF] Hoobin | Relative Lempel-Ziv factorization for e cient storage and retrieval of web collections[END_REF].

Besides its pratical interest, the algorithm LZ'78 was the starting point of a long line of theoretical research, triggered by the optimality result among nitestate compressors proved by Ziv and Lempel. In recent work, for instance, a comparison of pushdown nite-state compressors and LZ'78 is made in [START_REF] Mayordomo | Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable[END_REF]; the article [START_REF] Kärkkäinen | On the size of Lempel-Ziv and Lyndon factorizations[END_REF] studies Lempel-Ziv and Lyndon factorisations of words; or the e cient construction of absolutely normal numbers of [START_REF] Jack | Computing absolutely normal numbers in nearly linear time[END_REF] makes use of the Lempel-Ziv parsing.

Some works of bioinformatics have also focussed on Ziv-Lempel algorithms, since their compression scheme makes use of repetitions in a sequence in a way that proves useful to study DNA sequences (see e.g. [START_REF] Zhang | Normalized Lempel-Ziv complexity and its application in bio-sequence analysis[END_REF]), or to measure the complexity of a discrete signal [START_REF] Aboy | Interpretation of the Lempel-Ziv complexity measure in the context of biomedical signal analysis[END_REF] for instance.

Actually, both in theory and in practice, Ziv-Lempel algorithms are undoubtedly among the most studied compression algorithms and we have chosen only a very limited set of references: we do not even claim to be exhaustive in the list of elds where LZ'77 or LZ'78 play a role.

Robustness

Yet, the robustness of LZ'78 remained unclear: the question of whether the compression ratio of a sequence could vary by changing a single bit appears already in [START_REF] Lathrop | A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data[END_REF], where the authors also ask how LZ'78 will perform if a bit is added in front of an optimally compressible word. Since the Hausdor dimension of complexity classes introduced by Lutz [START_REF] Jack | Dimension in complexity classes[END_REF] can be de ned in terms of compression (see [START_REF] López | Dimension is compression[END_REF]), this question is linked to nite-state and polynomial-time dimensions as [START_REF] Lopéz-Valdés | Lempel-Ziv dimension for Lempel-Ziv compression[END_REF] shows. As a practical illustration of the issue the (lack of) robustness can cause, let us mention that the deflate algorithm tries several starting points for its parsing in order to improve the compression ratio.

Here, we show the existence of an in nite sequence w which is compressible by LZ'78, but the addition of a single bit in front of it makes it incompressible (the compression ratio of 0w is non-zero, see Theorem 7.6), thus we settle the "one-bit catastrophe" question. To that end, we study the question over nite words, which enable stating more precise results. For a word w and a letter a, we rst prove in Theorem 7.7 that the compression ratio ρ(aw) of aw cannot deviate too much from the compression ratio ρ(w) of w:

ρ(aw) ≤ 3 √ 2 ρ(w) log |w|.
In particular, aw can only become incompressible (ρ(aw) = Θ(1)) if w is already poorly compressible, namely ρ(w) = Ω(1/ log n). This explains why the one-bit catastrophe cannot be "a tragedy" as we point out in the title. However, our results are tight up to a constant factor, as we show in Theorem 7.10: there are constants α, β > 0 such that, for any l

(n) ∈ [90 2 log 2 n, √ n],
there are in nitely many words w satisfying

ρ(w) ≤ α log |w| l(|w|) whereas ρ(0w) ≥ β log |w| l(|w|) .
In particular, for l(n) = 90 2 log 2 n, these words satisfy

ρ(w) ≤ 1 log |w| and ρ(0w) ≥ β 90
(this is the one-bit catastrophe over nite words). But actually the story resembles much more a tragedy for well-compressible words. Indeed, for l(n) = √ n we obtain:

ρ(w) ≤ α log |w| |w| whereas ρ(0w) ≥ β log |w| |w| 1/4 ,
that is to say that the compression ratio of 0w is much worse than that of w (which in that case is optimal). To give a concrete idea, the bounds given by our Theorem 9.1 for words of size 1 billion (|w| = 10 9 ) yield a compression for w of size at most d log d ≤ 960,000 (where d = 1.9 |w|), whereas for 0w the compression size is at least d log d ≥ 3,800,000 (where d = 0.039|w| 3/4 ). 1This "catastrophe" shows that LZ'78 is not robust with respect to the addition or deletion of bits. Since a usual good behaviour of functions used in data representation is a kind of "continuity", our results show that, in this respect, LZ'78 is not a good choice, as two words that di er in a single bit can have images very far apart.

Lempel-Ziv, compression and results

Before turning to the description of LZ'78 algorithm, let us recall standard notation on words.

Basic notation

The binary alphabet is the set {0, 1}. A word w is an element of {0, 1} , that is, a nite ordered sequence of letters 0 or 1, whose length is denoted by |w|. The empty word is denoted by λ. For a word w = x 0 • • • x n-1 (note that the indices begin at zero), where x i ∈ {0, 1}, w[i..j] will denote the substring x i • • • x j of w (or λ if j < i); w[i] or w i will denote the letter x i ; and w ≤i (respectively w <i ) will denote w[0..i] (resp. w[0..i -1]). We say that a word m is a factor of w if m is any substring w[i..j]. In the particular case of i = 0 (respectively j = n -1), m is also called a pre x (resp. a su x) of w. The set of factors of w is denoted by F (w), and its set of pre xes P(w). By extension, for a set M of words, F (M ) will denote ∪ w∈M F (w) and similarly for P(M ). If u and w are two words, we denote by Occ w (u) the number of occurrences of the factor u in w.

The "length-lexicographic order" on words is the lexicographic order where lengths are compared rst.

An in nite word is an element of {0, 1} N . The same notation as for nite words apply.

All logarithms will be in base 2. The size of a nite set A is written |A|. • m 1 , . . . , m k-1 are all distinct 2 ;

• ∀i ≤ k, P(m i ) ⊆ {m 1 , . . . , m i }.

The words m 1 , . . . , m k are called blocks. The predecessor of a block m i is the unique m j , j < i, such that m i = m j a for a letter a. The compression algorithm LZ'78 parses the word w and encodes each block m i as a pointer to its predecessor m j together with the letter a such that m i = m j a. For instance, the word w = 00010110100001 is parsed as Blocks 0 00 1 01 10 100 001 Block number 0 1 2 3 4 5 6

and thus encoded as (λ, 0); (0, 0); (λ, 1); (0, 1); (2, 0); (4, 0); (1, 1). 2 The last word m k might be equal to another m i .

The dictionary of w is the set Dic(w) = {m 1 , . . . , m k } (in the example, {0, 1, 00, 01, 10, 001, 100}). Remark that, by de nition, {λ} ∪ Dic(w) is pre xclosed.

The parse tree of w is the unique rooted binary tree whose (k + 1) vertices are labeled with λ, m 1 , . . . , m k , such that the root is λ and if a vertex m i has a left child, then it is m i 0, and if it has a right child, then it is m i 1. By abuse of language, we say that a block b "increases" or "grows" in the parsing of a word w when we consider one of its successors, or when we consider a path from the root to the leaves that goes through b. Indeed, going from b to its successor amounts to add a letter at the end of b (hence the "increase").

Compression ratio

As in the example above, given a word w and its LZ-parsing m 1 • • • m k , the LZcompression of w is the ordered list of k pairs (p i , a i ), where p i is the binary representation of the unique integer j < i such that m j = m i [0..(|m i | -2)], and a i the last letter of m i (that is, the unique letter such that m i = m j a i ). When the LZ-compression is given, one can easily reconstruct the word w.

Remark 7.1

• If x is a word, we de ne Pref(x) the concatenation of all its pre xes in ascending order, that is,

Pref(x) = x 0 .x 0 x 1 .x 0 x 1 x 2 . • • • .x 0 • • • x n-2 x n-1 .
Then the parsing of the word w = Pref(x) is exactly the pre xes of x, thus the size of the blocks increases each time by one: this is the optimal compression. In that case, the number of blocks is

k = |x| = √ 2 |w| -O(1).
Actually, it is easy to see that this optimal compression is attained only for the words w of the form Pref(x).

In Chapter 10 we will need the concatenation of all pre xes of x starting from a size p + 1, denoted by Pref >p (x), that is,

Pref >p (x) = x 0 x 1 • • • x p .x 0 x 1 • • • x p+1 . • • • .x 0 • • • x n-1 .
• On the other hand, if w is the concatenation, in length-lexicographic order, of all words of size ≤ n (w = 0.1.00.01.10.11.000.001 . . . ), then it has size

|w| = n i=1 i2 i = (n -1)2 n+1 + 2,
and its parsing consists of all the words up to size n, therefore that is the worst possible case and the number of blocks is

k = 2 n+1 -2 = |w| log |w| + O |w| log 2 |w| .
(And that is clearly not the only word achieving this worst compression.)

The number of bits needed in the LZ-compression is A sequence of words (w n ) is said LZ-compressible if ρ(w n ) tends to zero (i.e., k n log k n = o(|w n |)), and consistently it will be considered LZ-incompressible if lim inf n→∞ ρ(w n ) > 0 (in other terms, k n log k n = Ω(|w n |)).

Θ( k i=1 (|p i | + 1)) = Θ(k log k).
Actually, the (log k) factor is not essential in the analysis of the algorithm, therefore we drop it in our de nitions (moreover, most of the time we will focus directly on the size of the dictionary rather than the compression ratio).

De nition 7.3

The size of the LZ-compression of w, or compression size, is de ned as the size of Dic(w), that is, the number of blocks in the LZ-parsing of w.

Remark that |Dic(w)| = Ω( |w|) and |Dic(w)| = O(|w|/ log(|w|)). We can now restate the de nition of incompressibility of a sequence of words in terms of compression size instead of the number of bits in the LZ-compression.

De nition 7.4

A sequence of words (w n ) is said to be incompressible i

|Dic(w n )| = Θ |w n | log(|w n |)
.

In those de nitions, we have to speak of sequences of nite words since the asymptotic behaviour is considered. That is not needed anymore for in nite words, of course, but then two notions of compression ratio are de ned, depending on whether we take the lim inf or lim sup of the compression ratios of the pre xes.

De nition 7.5: compression ratios for in nite words

Let w ∈ {0, 1} N be an in nite word. The word w is called incompressible if ρ inf (w) > 0.

One-bit catastrophe and results

The one-bit catastrophe question is originally stated only on in nite words. It asks whether there exists an in nite word w whose compression ratio changes when a single letter is added in front of it. More speci cally, a stronger version asks whether there exists an in nite word w compressible (compression ratio equal to 0) for which 0w is not compressible (compression ratio > 0). In Chapter 11 we will answer that question positively:

Theorem 7.6
There exists w ∈ {0, 1} N such that ρ sup (w) = 0 and ρ inf (0w) ≥ 1 6 075 .

Remark that the lim inf is considered for the compression ratio of 0w and the lim sup for w, which is the hardest possible combination as far as asymptotic compression ratios are concerned. But before proving this result, most of the work will be on nite words (only in Chapter 11 will we show how to turn to in nite words). Let us therefore state the corresponding results on nite words. Actually, on nite words we can have much more precise statements and therefore the results are interesting on their own (perhaps even more so than the in nite version).

In Chapter 8, we show that the compression ratio of aw cannot be much worse than that of w. In particular, all words "su ciently" compressible (compression size o(|w|/ log 2 |w|)) cannot become incompressible when a letter is added in front (in some sense, thus, the one-bit catastrophe cannot happen for those words, see Remark 7.11). When stated in terms of compression ratio, using the fact that |Dic(w)| ≥ |w|, this result reads as follows:

ρ(aw) ≤ 3 √ 2 ρ(w) log |w|.
We also show in Chapter 9 that this result is tight up to a multiplicative constant, since Theorem 9.1 implies the following result. This shows that the upper bound is tight (up to a multiplicative constant) for any possible compression size. This also provides an example of compressible words that become incompressible when a letter is added in front (see Remark 7.11), thus showing the one-bit catastrophe for nite words. • however, by Theorem 7.10, there is an increasing sequence of words

(w n ) such that |Dic(w n )| = Θ(|w n |/ log 2 |w n |) (compressible) but |Dic(0w n )| = Θ(|w n |/ log |w n |) (incompressible)
, which is the onebit catastrophe on nite words;

• the following interesting case is also true: there is an increasing sequence of words

(w n ) such that |Dic(w n )| = Θ( |w n |) (optimal com- pression) but |Dic(0w n )| = Θ(|w n | 3/4
). This special case is treated extensively in Theorem 9.

Parsings of w and aw

We will often compare the parsing of a word w and the parsing of aw for some letter a: let us introduce some notation (see Figure 7.2).

• The blocks of w will be called the green blocks.

• The blocks of aw will be called the red blocks and are split into two categories 4 :

-The junction blocks, which are red blocks that overlap two or more green blocks when we align w and aw on the right (that is, the factor w of aw is aligned with the word w, see Figure 7.2).

-The o set-i blocks, starting at position i in a green block and completely included in it. If not needed, the parameter i will be omitted.

0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 o set-1 o set-0 junction

Upper bound

This chapter is devoted to the proof of Theorem 7.7 giving an upper bound on the compression ratio of aw, for any letter a, as a function of the compression ratio of the word w. In their 1998 paper [START_REF] Lathrop | A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data[END_REF], Lathrop and Strauss ask the following question: "Consider optimally compressed sequences: Will such sequences compress reasonably well if a single bit is removed or added to the front of the sequence?" We give a positive and quanti ed answer: indeed, a word w compressed optimally has a compression size O( √ n), thus by Theorem 7.7, the word aw has a compression size O(n 3/4 ). (And we shall complete this answer with the matching lower bound in the next chapter.)

The rst lemma bounds the size of the partition of a word w if the partitioning words come from a family with a limited number of words of same size. In its application, the partition will be a subset of the LZ-parsing, and Lemma 8.3 below will give the required bound on the number of factors of a given size.

Lemma 8.1

Let F be a family of distinct words such that for each i, the number of words of size i in F is bounded by a constant N . Suppose that a word w is partitioned into di erent words of F. Then the number of words used in the partition is at most 2 N |w|.

Proof. Let m(i) be the number of words of size i occurring in the partition of w, and k the size of the largest words used. We want to prove that

k i=1 m(i) ≤ 2 N |w|.
We have:

|w| = k i=1 im(i) ≥ i≥ |w| N im(i) ≥ |w| N i≥ |w| N m(i) hence i≥ |w| N m(i) ≤ N |w|.
On the other hand, since m(i) ≤ N : We now come to the lemma bounding the number of factors of a given size in a word w as a function of its LZ-parsing.

i< |w| N m(i) < N |w| N = N |w|.

Lemma 8.3

Let T be the parse tree of a word w. Then the number of di erent factors of size i in the blocks of w is at most

|T | -i (that is, |F (Dic(w)) ∩ {0, 1} i | ≤ |T | -i).
Proof. A factor of size i in a block b corresponds to a subpath of size i in the path from the root to b in the parse tree. The number of such subpaths is bounded by the number of vertices at depth at least i.

Actually, below we will use Lemma 8.3 sub-optimally since we will ignore the parameter i and use the looser bound (|T | -1).

Let us turn to the proof of Theorem 7.7, the main result of the present chapter. "Weak catastrophe" for the optimal compression ratio Before the proof of Theorem 7.10, we rst present a "weak catastrophe", namely the third item of Remark 7.11 in which the compression size of a sequence changes from O( √ n) (optimal compression) to Ω(n 3/4 ) when a letter is added in front, thus matching the upper bound of Theorem 7.7. Observe that this weak catastrophe is a special case of Theorem 7.10 (with better constants, though). The aim of this chapter is twofold: rst, it will be a constructive proof, whereas the main theorem will use the probabilistic method; second, this chapter will set up the main ideas and should help understand the general proof.

A main ingredient in the construction is de Bruijn sequences, that we introduce shortly before giving the overview of the proof.

• For the rst, what could happen is that by coincidence the parsing creates most of the time an o set-i red block (called i-violation in the sequel), which therefore would increase until it covers almost all the word w. To avoid this, we introduce gadgets: we make sure that this happens at most half of the time (and thus cannot cover more than half of w). More precisely, Lemma 9.5 shows that at most half of the pre xes of x can contain o set-i blocks for any xed i ≤ γk. This is due to the insertion of gadgets that "kill" some starting positions i if necessary, by "resynchronizing" the parsing at a di erent position.

• On the other hand, red blocks starting at position i > γk are shown to be of small size by Proposition 9.7. This is implied by Lemma 9.6 claiming that, due to the structure of the DB(k) (few repetitions of factors), few junction red blocks can go up to position (i -1) and precede an o set-i block.

Since all large enough pre xes of x have a constant portion containing only red blocks of size O(n 1/4 ), the compression size is Ω(n 3/4 ) (Theorem 9.1). Gadgets must satisfy two conditions:

• they must not disturb the parsing of w;

• the gadget g i must "absorb" the end of the red block ending at position (i-1), and ensures that the parsing restarts at a controlled position di erent from i.

The insertion of gadgets in w is not trivial because we need to "kill" positions without creating too many other bad positions, that is why gadgets are only inserted in the second half of w. Moreover, gadget insertion depends on the parsing of 0w and must therefore be adaptive, which is the reason why we give an algorithm to describe the word w.

Let us summarize the organisation of the lemmas of this chapter:

• Lemma 9.3 is necessary for the algorithm: it shows that, in 0Pref(x), there can be at most one position i such that the number of i-violations is too high.

• Lemma 9.4 shows that the parsing of w is not disturbed by gadgets and therefore the compression size of w is O( √ n).

• Lemma 9.5 shows that gadgets indeed remove i-violations as required, for i ≤ γk.

• Lemma 9.6 uses the property of the DB(k) to prove that junction blocks cannot create too many i-violations if i > γk.

The number of i-violations is l i = a + b + c and the number of i -violations is l i = b + d. But b + c + d ≤ s -i and b ≤ i -i -a (since a red block starting at position i can only be increased (i -i) times before it overlaps position i , and it has already increased a times in the rst i green blocks), so that l

i + l i = (b + c + d) + (a + b) ≤ (s -i ) + (i -i) ≤ s. Therefore, l i or l i has to be ≤ s/2.
The algorithm constructing w, illustrated in Figure 9.1, is as follows.

1. If the number of i-violations in w 0 .w 1 . . . w s-1 is ≤ s/2 for all i ∈ [0, γk],

then output w = w 0 .w 1 . . . w s-1 .

2. Otherwise, let i be the (unique by Lemma 9.3) integer in [0, γk] for which the number of i-violations is > s/2. Let c = 0 (counter for the number of inserted gadgets) and d = s/2 + 1 (counter for the place of the gadget to be inserted).

3. For all j ∈ [0, s -1], let z j = w j .

4. While the number of i-violations in z 0 .z 1 . . . z s-1 is ≥ d, do:

(a) let j be such that w j is the d-th i-violated green block;

(b) z j ← g c i w j (we add the gadget g c i before the block w j ); (c) c ← c + 1;

(d) if w j is still i-violated, then d ← d + 1. to deal with the i-violations for i > γk, therefore for now we only care about i-violations for i ≤ γk. They are not problematic if there are at most (roughly) s/2 of them. Thanks to Lemma 9.3, there is therefore at most one i 0 which can be problematic. To guarantee the upper bound of (roughly) s/2 for the number of i 0 -violations, every time it is necessary we insert between two regular green blocks one gadget to kill the (s/2 + 1)-th, (s/2 + 2)-th, etc., i 0 -violations. But gadgets are guaranteed to work as expected only if at least 1 + (γ + 1)k of them have already been inserted (see Lemma 9.5), hence the counter d is useful to avoid inserting two gadgets in front of the same regular block.

Return w

= z 0 .z 1 . . . z s-1 . z j-1 w j z j-1 w j gadget = z j
From now on, we call w the word output by the algorithm. We rst evaluate the size of w. Its minimal size is obtained when no gadgets are added during the algorithm:

|w| ≥ s(s + 1) 2 .
On the other hand, if s/2 gadgets g c γk of size γk + 1 + c are added, we obtain an upper bound on |w|:

|w| ≤ s(s + 1) 2 + s/2-1 c=0 (γk + 1 + c) = 5s 2 8 + o(s 2 ).
Let us show that the word w is nearly optimally compressible (upper bound).

Lemma 9.4

The compression size of w is at most Otherwise, we add at most one gadget for each w j , and only for j > s/2. Therefore, there are at most s/2 gadgets. Remark that, for the i xed in the algorithm, the gadgets (g j i ) j are pre xes one of each other, and none of them are pre xes of x. Thus the parse tree of w consists of one main path of size s (corresponding to w 0 , w 1 , . . . , w s-1 ), together with another path of size ≤ s/2 (corresponding to the gadgets (g j i ) j ) starting from a vertex of the main path. See Figure 9.2.

The worst case for the compression size is when the second path is of size s/2 and starts at the root. Then the size of w is

|w| ≥ s(s + 1) 2 + (s/2)(1 + s/2) 2 ≥ 5s 2
8 and the size of the dictionary is 3s/2, yielding the compression size stated in the lemma.

Let us now turn to the lower bound on the compression size of 0w. The next lemma shows that, for i ≤ γk, there are not too many i-violations thanks to the gadgets.

Lemma 9.5

For all i ∈ [0, γk], the number of i-violations in w is at most

s/2 + (1 + γ)k + 1.
Proof. If no gadgets have been added during the algorithm, then for all i ∈ [0, γk], the number of i-violations in w is ≤ s/2.

Otherwise, rst remark that Lemma 9.3 remains valid even when the gadgets are added. We need to distinguish on the type (i = 0 or i > 0) of the most frequent violations in w.

• Case 1: the most frequent violations are 0-violations. In that case, we claim that whenever a gadget is inserted before a block w i , the 0-violation in w i disappears. It is enough to prove that whenever a gadget g j 0 is added, it was already in the dictionary of 0w, so that the next word in the dictionary will begin by g j 0 0 and the parsing will overlap position 0 of the next green block. We proceed by induction: for j = 0, g 0 0 = 1, and this word is the third block in the parsing of 0w, because x starts with 01. For j > 0: when g j-1 0 was parsed, by induction it was already in the dictionary, so that the block added in the dictionary of 0w starts with g j-1 0 0 = g j 0 . After at most s/2 iterations of the while loop, there is no more (s/2 + 1)th 0-violation: the number of 0-violations is exactly s/2. Observe that violations for i > 0 have been created, but by Lemma 9.3, for each i > 0, the number of i-violations remains ≤ s/2.

• Case 2: the most frequent violations are i-violations for some i > 0. In that case, the rst few times when a gadget is inserted, it may fail to kill the corresponding i-violation. But we claim that the number of such fails cannot be larger than (γ + 1)k + 1 (equivalently, in the algorithm the counter d remains ≤ s/2 + (γ + 1)k + 2).

Indeed, since we add a gadget only before an i-violation, the parsing splits the gadget g j i = x <i xi .1 j between x <i and xi .1 j . Furthermore, by induction, xi .1 j is not split by the parsing. But for the gadget g k+1 i , xi .1 k+1 is parsed in exactly one block because this factor does not appear anywhere in w before g k+1 i . From that moment on, each i-violation creates through the gadget a 0-violation. The number of blocks that are both 0-violated and i-violated is at most i (due to the growth of the block at position 0). Thus, at most i more gadgets may fail to kill position i. The total number of "failing" gadgets is ≤ k + 1 + i ≤ (γ + 1)k + 1.

The weak catastrophe

This chapter is devoted to the proof of the lower bound: the compression size of 0w is Ω(|w| 3/4 ). Thanks to Property ( ) from page 130, Lemma 9.6 below bounds the number of junction blocks ending at a xed position (i -1) by a decreasing function of i. The proof is quite technical and requires to distinguish three categories among (red) junction blocks:

• Type 1: junctions over consecutive factors w a and w a+1 (no gadget between two regular green blocks); Proposition 9.7

For any i > γk, the size of an o set-i block included in a regular green block is at most

2 √ s + 5k + 2 k+1 i -2k -1 .
Proof. Let u be an o set-i block of size ≥ 2k.

We claim that the red blocks predecessors of u of size at least 2k + 1 have to start at position i in regular green blocks. Indeed, let v be a pre x of size ≥ 2k + 1 of u; let us analyse as before the di erent cases:

• If v is included in a regular green block, then it has to start at position i by Property ( ) (page 130);

• v cannot be included in a gadget since it would lead to a contradiction:

in gadgets of type g j 0 , v would contain 0 2k , -in gadgets of type g j a = x <a xa 1 j (for a ∈]0, γk]), either v goes into x <a by at least k and v[0..k -1] would appear at two positions in x, or v goes into xa 1 j by at least k + 2 and v would contain 1 k+1 ;

• If v is included in a junction block of type 1, then v starts at position i in the left regular block, otherwise either v[0..k -1] would be in the left regular block at a position di erent from i, or v[k + 1..2k] would be in the right regular block at a position ≤ γk < i;

• v cannot be included in a junction block of type 2: indeed, by the red parsing, the left part of the junction (included in a gadget) is either 10 j or a1 j for some letter a ∈ {0, 1}, thus v cannot go on the left by ≥ k + 2 and hence has to go on the right by at least k leading to a contradiction with Property ( );

• If v is included in a junction block of type 3, then v starts at position i in the left regular block, otherwise either v[0..k -1] would be in the left (regular) block at a position di erent from i, or, by the red parsing, the gadget is of type g j a (for a > 0) and v[k + 1..2k] would be included in x <a at a position ≤ γk < i.

Thus, at least |u| -2k red blocks end at position i -1.

By Lemma 9.6, at most 2 k+1 i-2k-1 of them are junctions of type 1. Note furthermore that, as shown during the proof of Lemma 9.5, if a ≥ k + 1, the a-th junction of type 2 stops at position 0 or 1, hence at most k of the blocks ending at position i -1 are junctions of type 2. Finally, there is, by de nition, no junction of type 3. Therefore, there are at least |u| -3k -2 k+1 i-2k-1 o set blocks ending at position i -1. We call M the set of such blocks. See Figure 9.3. Remark that |u| -3k -2 k+1 i-2k-1 is a lower bound on the number of o set blocks ending at position i -1. But the number of such blocks is at most i. Therefore

|u| -3k - 2 k+1 i -2k -1 ≤ i
We distinguish two cases in the proof:

First case: i ∈ [γk + 1, 2 √ s]. Then |u| -3k - 2 k+1 i -2k -1 ≤ i ≤ 2 √ s so that |u| ≤ 2 √ s + 3k + 2 k+1 i -2k -1 ≤ 2 √ s + 5k + 2 k+1 i -2k -1 .
Second case: i > 2 √ s. All the words in M are in the dictionary and are of di erent size, since two o set blocks ending at the same position and of same size would be identical, which is not possible in the LZ-parsing. The words of P(M ) (the set of pre xes of the words in M ) are also in the dictionary. Let

A = |u| -5k -2 k+1 i-2k-1 2 . Observe that i -A -2k ≥ i 2 -k as |u| -3k -2 k+1 i-2k-1 ≤ i. Therefore i -A -2k ≥ √ s -k, which is large against γk. Consider the words of P(M ) containing x[i -A -2k..i -A]: they must start at a position ≤ i -A -2k and end at a position ∈ [i -A, i -1].
The number of such words is at least the product of the number of blocks in M starting at position ≤ i -A -2k and of the number of possible ending points, that is, at least

|u| -3k - 2 k+1 i -2k -1 -A + 2k A.
Remark that these words contain a part of a regular green block of size at least 2k + 1 starting at position i -A -2k > γk. Hence, by the same case analysis as before, for these words, the part corresponding to the factor x[i -A -2k..i -A -k -1] must appear included in a regular green block, so that two such words cannot appear in the same regular green block by Property ( ) (page 130). But there are at most s distinct regular green blocks, thus:

|u| -5k - 2 k+1 i -2k -1 -A A ≤ s.
The value of A gives:

|u| -5k -2 k+1 i-2k-1 2 2 ≤ s |u| ≤ 2 √ s + 5k + 2 k+1 i -2k -1 . i u #o set blocks ≥ |u| -3k -2 k+1 i-2k-1 #Junctions type 1 ≤ 2 k+1 i-2k-1
#Junctions type 2 ≤ k We are ready for the proof of the main theorem of this chapter.

Proof of Theorem 9.1. The intuition is the following: by Proposition 9.7, the red blocks starting at position j, for j = Ω( √ s), are of size Θ( √ s) = Θ(|w| 1/4 ), so if we prove that a portion of size Θ(|w|) of the word 0w is covered by o set-j blocks for j large enough, then the compression size will be Ω(|w| 3/4 ). To that purpose, we prove that for large enough regular green blocks, there is an interval of positions [2s/3 -l, 2s/3] (with l = 2 √ s + 5k + 3), such that there is at least one o set-i block for i ∈ [2s/3 -l, 2s/3].

In every regular green block of size larger than 2s/3, let us show that there is an o set-i red block, for i ∈ [2s/3 -l, 2s/3]. Indeed, for every i < 2s/3 -l, the maximal size f (i) of a red block starting at position i satis es i + f (i) ≤ 2s/3: in the case where i > γk we use the bound given by Proposition 9.7, and in the case where i ≤ γk, the (t -γk) predecessors of size ≥ γk + 1 of a red block of size t starting at position i start at position i as well (since x ≤γk is not a factor of a gadget, it cannot be seen anywhere by a red block except at position i in a regular green block), hence the size of an o set-i block in that case is at most γk plus the number of i-violations. Therefore by Lemma 9.5 red blocks starting at position i have their size upper bounded by γk + s/2 + 1 + (1 + γ)k.

Therefore, since a red block starting at position i ≥ 2s/3 -l is of size at most B = 2

√ s + 5k + 2 k+1
2s/3-l-2k-1 by Proposition 9.7, each green block of size h ≥ 2s/3 is covered by at least

h -2s/3 B ≥ h -2s/3 2 √ s + O(k)
red blocks. Thus, the total number of red blocks is at least

1 2 √ s + O(k) s h=2s/3 (h -2s/3) = 1 36 s 3/2 + o(s 3/2 ).
With the gadgets, the size of w is at most (5/8)s 2 + o(s 2 ), therefore the total number of red blocks is at least: Despite the fact that 1Pref(x) compresses optimally, this is not at all the case with the gadgets, since Theorem 9.1 remains valid with the new word w output by the algorithm even when we put 1 instead of 0 in front of w.

Chapter 10

General case

In this chapter we prove Theorem 7.10. The proof rst goes through the existence of a family F of "independent" de Bruijn-style words which will play a role similar to the de Bruijn word x in the proof of Theorem 9.1. The existence of this family is shown using the probabilistic method in Section 10.1: with high probability, a family of random words satis es a relaxed version (P1) of the "local" Property ( ), together with a global property (P2) that forbids repetitions of large factors throughout the whole family.

The word w that we will consider is the concatenation of "chains" roughly equal to Pref(x) for all words x ∈ F , with gadgets inserted if necessary as in Chapter 9. (The construction is actually slightly more complicated because in each chain we must avoid the rst few pre xes of x in order to synchronise the parsing of w; and the gadgets are also more complex.) Properties (P1) and (P2) guarantee that each of the chains of w are "independent", so that the same kind of argument as in Chapter 9 will apply individually. By choosing appropriately the number of chains and their length, we can obtain any compression size for w up to Θ(n/ log 2 n) and the matching bound for 0w (see Theorem 7.10).

The organisation of the chapter is as follows: Section 10.1 is devoted to the proof of existence of the required family of words. Section 10.2 de nes the gadgets, describes the construction of w via an algorithm, and gives the upper bound on the compression size of w. Finally, Section 10.3 shows the lower bound on the compression size of 0w via a series of results in the spirit of Section 9.4.

Throughout the present chapter, we use parameters with some relations between them that are worth being stated once and for all in Figure 10.1 for reference.

In particular, note that we have the following relations:

0 ≤ p ≤ √ l and γ log n 3 ≤ m ≤ √ l 9
.

n su ciently large (the size of w) γ ≥ 10 (an absolute constant)

l ∈ [(9γ) 2 log 2 n, √ n] (size of the x j ) p = log n l 2 (2 p is the number of chains) k = log l 2 (parameter in (P1)) m = max(γp, γ log l) (parameter in (P2)).

Family of de Bruijn-type words

We need two properties for a family F of 2 p words x 1 , . . . , x 2 p of size l (the parameters n, l, p, k, γ and m are those given in Figure 10.1): the rst is a relaxed version of Property ( ) on "true" de Bruijn words; the second guarantees that the words of F are "independent".

• (P1) For all x ∈ F , for all words u of size ≤ k, Occ x (u) ≤ kl 2 |u| .

• (P2) Any factor u of size m appears in at most one word of the family F , and within that word at only one position.

Note that in Chapter 9, we did not need (P2) since only one word was concerned, but still (P2) was true for the same value k as in ( ), instead of m here.

The following lemmas show that (P1) and (P2) hold with high probability for a random family F . We rst recall the well-known Cherno bound.

Theorem 10.1: Cherno bound Let X 1 , . . . , X n be independent random variables over {0, 1}, and X = X i . Denote by µ the expectation of X. Let δ > 1. Then:

Pr(X > δµ) < 2 -(δ-1)µ log δ 2 .

For (P1), we need to consider positions separated by a distance k in order to obtain the independence required for the Cherno bound; then a union bound will complete the argument for the other positions.

Let p and l be positive. Recall that m = max(γp, γ log l) in (P2). Let F be a family of 2 p words x 1 , . . . , x 2 p of size l chosen uniformly and independently at random. Then F satis es Property (P2) with probability a least 1 -2/l.

Proof. Let us rst show that we can assume with high probability that factors of w i are not overlapping too much. We say that a word u of size m is "bad" if it overlaps itself at least by half, that is: (Remark that a word u can be both i-bad and j-bad for i = j.) Let us rst bound the number of bad words. If u is i-bad, then for each j < i, u j+|u|-i = u j . Therefore, specifying the |u| -i rst bits speci es the whole word u, meaning that there are at most 2 |u|-i i-bad words. In total, there are at most |u|-1 i=|u|/2 2 |u|-i = 2 1+|u|/2 -2 bad words, that is, a fraction < 2 -m/2+1 of all words of size m. Now, we say that a word x j of size l is "good" if it contains no bad factor. Let us show that, with high probability, all the words x j ∈ F are good (Property (G)). Fix j ∈ [1, 2 p ]. If x j is not good, then there is at least one position where a bad factor u occurs:

Pr(x j is not good) ≤ |x j |Pr |u|=m (u is bad) ≤ l2 -m/2+1 . We use the union bound over all 2 p words x j ∈ F to obtain:

Pr(G) ≥ 1 -l2 p-m/2+1 .
Since property G has very high probability, we will only show that (P2) holds with high probability when G is satis ed. Let x = x 1 . . . x 2 p (the size of x is therefore l2 p ). Let u be a word of size m, which is not bad. Let X u be the number of occurences of u in x. In order to get at least two occurrences of u, we have to choose two positions, the |u| bits of the rst occurrence, and the bits of the second occurrence that are not contained in the rst; but u can't overlap itself by more than m/2 bits, thus:

Pr(X u ≥ 2) ≤ |w| 2 m |w| 2 m/2 ≤ l 2 2 2p-3 2 m .
Using the union bound over all good words u of size m, of which there are at most 2 m , we get:

Pr(∀ good u, X u ≤ 1) ≥ 1 -2 m l 2 2 2p-3 2 m = 1 -l 2 2 2p-m/2 . Now, the probability that F respects Property (P2) can be lower bounded by the probability that F contains no bad words, and that the number of occurences of good words is at most 1, which gives: Pr(F satis es (P2)) ≥ Pr(G ∧ ∀ good u, X u ≤ 1)

≥ 1 -l 2 2 2p-m/2 -l2 p-m/2+1 > 1 - 2 l since γ ≥ 10
(for the last line, consider the two following cases: p ≥ log l where m = γp and l ≤ n 1/3 ; and p ≤ log l where m = γ log l and l ≥ n 1/3 ).

Corollary 10.4

For all su ciently large l and p ≤ √ l, there exists a family F of 2 p words x 1 , . . . , x 2 p of size l satisfying Properties (P1) and (P2), and where the rst bit of x 1 is 1.

Construction

(Recall the choice of parameters n, l, p, k, γ and m de ned in Figure 10.1.)

For n su ciently large and l ∈ [(9γ) 2 log 2 n, √ n], we will construct a word w of size n whose compression size is Θ(n/l) whereas the compression size of 0w is Θ(n/ √ l) (thus matching the upper bound of Theorem 7.7). Let F be a family as in Corollary 10.4. For some integers q j (de ned below), the word w will merely be the concatenation of Pref >q j (x j ) (see Remark 7.1 for the de nition of Pref >q (x)) for all the 2 p words x j of the family F , with possibly some gadgets added between the pre xes of x j (each Pref >q j (x j ) together with the possible gadgets will be denoted z j and called a "chain"), and a trailing set of zeroes so as to "pad" the length to exactly n. The integer q j will be chosen so that the rst occurrence of x j [0..q j ] is parsed in exactly one green block.

Each chain z j (with gadgets) is of size Θ(l 2 ) and is fully compressible in w (compressed size Θ(l)) since it is made of pre xes (plus gadgets that won't impede much the compression ratio). Thus the total compression size of w is Θ(l2 p ), compared to |w| = n = Θ(l 2 2 p ) for a compression size of Θ(n/l).

On the other hand, due to the properties of F and similarly to Theorem 9.1, in 0w each chain will compress only to a size Θ(l 3/2 ), thus the total compression size of 0w is Θ(l 3/2 2 p ), for a compression size of Θ(n/ √ l).

Remark 10.5

• If we take the smallest possible l, that is, l = (9γ) 2 log 2 n, then we obtain compression sizes of Θ(n/ log 2 n) and Θ(n/ log n), thus showing the one-bit catastrophe.

• On the other hand, if we take the largest possible l, that is, l = √ n, then we obtain Θ( √ n) and Θ(n 3/4 ) as in Theorem 9.1.

Let us now start the formal description of the word w. As previously, we will call green the blocks in the parsing of w and red those in the parsing of 0w. The green blocks in each chain z j that are not gadgets will be called "regular blocks" (they are of the form x j [0..q] for some q). Recall that the chain z j will be of the form Pref >q j (x j ) with possibly some gadgets between the pre xes. We can already de ne the integers q j : q j = min{i ≥ 0 : x j [0..i] is not a pre x of x 1 , . . . , x j-1 }.

In that way, we guarantee that the rst green block in each z j is exactly x j [0..q j ]. Remark that, by Property (P2), q j ∈ [0, m]. For all j we will denote by s j = |x j | -q j = l -q j the number of regular green blocks in z j .

Fix n and l = l(n) ∈ [(9γ) 2 log 2 n, √ n], and let k = (log l)/2 and p = log(n/l 2 ). As in Property (P2), call m = max(γp, γ log l). Here are the new gadgets that will (possibly) be inserted in the chain z j (j ∈ [1, 2 p ]), for i ∈ [0, 2k √ l]:

• for c ≥ 0: g c 0 (j) = ua c , where a = x j [0] is the rst letter of x j , and u is the smallest word in Dic(0z 1 . . . z j-1 Pref >q j (x j [0..|x j |/2]))

but not in Dic(z 1 . . . z j-1 Pref >q j (x j )) :

this is a word which is in the parsing of 0w up to the insertion of g 0 0 (j) but not in the corresponding parsing of w (Lemma 10.7 below guarantees the existence of such a word and proves it is of size ≤ m); and its size is maximal if each chain contains l/2 gadgets g c i (whose size is at most 2k √ l + 1 + c):

|w | ≤ 2 p l i=1 i + l/2-1 c=0 ( 2k
√ l + 1 + c) ≤ n l 2 5l 2 8 + 2kl 3/2 ≤ n.
Therefore at the end of the algorithm it is legitimate to pad w with at most n/2 + o(n) zeroes to obtain the word w of size precisely n.

The following lemma justi es the existence of the gadgets g c 0 (j).

Lemma 10.7

There is a constant C > 0 such that, for all n, for all l ∈ [(9γ) 2 log 2 n, √ n] with l > C, for all j ∈ [1, 2 p ] (where p = log(n/l 2 )) there exists a word u of size ≤ m in Dic(0z1 . . . z j-1 Pref >q j (x j [0..|x j |/2]))

but not in Dic(z 1 . . . z j-1 Pref >q j (x j )). This implies that we can insert the gadgets g c 0 (j) in a chain z j whenever we need to.

Proof. For j = 1: the rst red block in z 1 is 0, but all the regular green blocks in z 1 begin with 1 (cf. Corollary 10.4). Therefore there exists a word u of size 1 in Dic(0Pref >q 1 (x 1 [0..|x 1 |/2])) not in Dic(Pref >q 1 (x 1 )).

For j > 1: as we shall see in the proof of Theorem 7.10 below 1 , in z j-1 there is an interval of A = 3 √ l positions that contains the starting position of a red block in at least l/3 regular green blocks. One of the positions of the interval is the starting point of a branch of at least

l 3A = √ l 9
≥ m red blocks. Thus there is a red block of size m which appears nowhere in z 1 , . . . , z j-1 by (P2) and is not a pre x of z j , thus it is a word of Dic(0z 1 . . . z j-1 ) not in Dic(z 1 . . . z j-1 Pref >q j (x j )).

We can now show that w has compression size O(|w|/l) by giving an upper bound on the size of the dictionary of w.

Lemma 10.8

The compression size |Dic(w)| of w is at most

3 + √ 3 2 • |w| l .
Proof. The de nition of the integers q j guarantees that the parsing resynchronizes at each beginning of a new chain z j . In a chain z j , the de nition of g 0 0 (j) guarantees that this gadget, if present, will be parsed in exactly one green block, and after that the subsequent gadgets g c 0 (j) also. Similarly, (P2) together with the fact that gadgets are only inserted in the second half of a chain (thus, after more than m green blocks) imply that the possible gadgets g c i (j) for i > 0 are also parsed in exactly one green block. For each chain z j , the parse tree consists in a main path of size l (regular green blocks) together with another path of size ≤ l/2 corresponding to the gadgets g c i (j). The compression size cannot be worse than in the (hypothetical) case where these two paths begins at depth 0, for all j. In that case, there are ≤ (3/2)l green blocks for each chain, and a size

|z j | ≥ l(l + 1) 2 + l 2 (1 + l 2 ) 2 ≥ 5 8 l 2 .
Since the number of chains is 2 p = n/l 2 , in that (hypothetical) worst case the number of green blocks in w is at most 3n/2l and |w | ≥ 5n/8. The ≤ 3n/8 trailing zeroes of w are parsed in at most √ 3n/2 ≤ ( √ 3/2)n/l green blocks. Hence the compression size of w is at most (3/2 + √ 3/2)(n/l).

Proof of the main theorem

(Recall the choice of parameters n, l, p, k, γ and m de ned in Figure 10.1.)

We now prove the lower bound of Theorem 7.10. Recall that z j denote the j-th chain of w. We will write w j i the i-th regular block of the chain z j . As in the previous chapter, we will distinguish junctions over two consecutive regular blocks (type 1); junctions starting in a gadget and ending in a regular block (type 2); and junctions starting in a regular block and ending in a gadget (type 3).

The next proposition is the core of the argument, and Theorem 7.10 will follow easily. The proposition is a corollary of lemmas that we will show afterwards.

Lemma 10.10

For any i ∈ [0, 2k

√ l] and j ∈ [1, 2 p ], the number of i-violations in the chain z j is at most l 2 + 2m + 1 + 2k √ l.

Proof. We x j and focus on the number of i-violations in the chain z j . Recall that s j denotes the number of regular blocks in the chain z j (s j ≤ l).

If no gadgets have been added during the execution of the algorithm, then for all i ∈ [0, 2k √ l], the number of i-violations is ≤ s j /2 ≤ l/2. Otherwise, we distinguish on the type of the most frequent violation (i = 0 or i > 0).

• Case 1: the most frequent violations are 0-violations. In that case, a proof similar to the case 1 of Lemma 9.5 (with 0 replaced by a = x j [0] the rst letter of x j ) shows that the number of i-violations for any i ∈ [0, 2k √ l] is ≤ s j /2 ≤ l/2.

• Case 2: the most frequent violations are i-violations for some i > 0. Let us see how the parsing of 0w splits the gadgets. As in the de nition of the gadgets, let m = max(i, m) and v = x j [0..m -1]1 l . When the rst gadget g 0 i (j) = x j [0..m -1]x j m is added, the red parsing splits the gadget g 0 i (j) between x j <i and x j [i..m -1]x j m , because the gadget is added before a regular block with an i-violation. Furthermore, x j [i..m -1]x j m is not split by the parsing, because at that moment in the algorithm, the number of i-violations in the previous regular green blocks is s j /2 ≥ m -i, so that, as the position i has been seen ≥ m -i times, the word x j [i..m -1] is already in the dictionary of 0w. Similarly, the gadget g c i (j) = x j [0..m -1]x j m v[0..c -1] is split by the red parsing between x j <i and x j [i..m -1]x j m v[0..c -1], with the additional property that this second part is not split by the parsing.

But for the gadget g 2m+1 i (j), the second part x j [i..m -1]x j m x j [0..m -1]1 m+1 is parsed in exactly one block because this factor does not appear anywhere in a regular block because of 1 m+1 (cf. (P2)) nor in a gadget of a preceding chain because of x j [0..m -1] (cf. (P2) again). From that moment on, each i-violation creates a 0-violation. The number of green blocks that are both 0-violated and i-violated is at most i ≤ 2k √ l. Thus, at most 2k √ l more gadgets fail to kill the corresponding i-violation. The total number of "failing" gadgets in the chain z j is at most 2m + 1 + 2k √ l.

• Observe rst that the number of problematic blocks that overlap the second part of the gadget (g c b (j) ≥b ) is at most m. Indeed, this part is not split by the red parsing, therefore for c ≥ m a red block that overlaps this part would contain xj m x j [0..m -1], which is not possible since the position of the word x j [0..m -1] should be 0 by Property (P2) • The number of problematic blocks that appear completely included in the rst part of a gadget (g c b (j) <b ) is at most b. Otherwise, the red parsing creates at least one red block completely included in the rst part x j [0..b -1] of the gadget, and we claim that this can happen at most b times. Indeed, each time the parsing falls in this case, the last red block included in the rst part of the gadget has to end at position b -1, but the size of this block has to be di erent each time, so that this second case can occur at most b times. Finally, each time a gadget is parsed, at most one of the red blocks included in the rst part of the gadget can be a word of S by Property (P2).

3. There is no problematic blocks that are junction blocks of type 1 or 3. Indeed, if it were the case, the right part of the junction would be of size ≤ m -1 since otherwise the problematic block would contain ax j [0..m-1] for some letter a, which is not possible. Therefore, within the problematic block, the factor x j [i -A -2m..i -A -m -1] appears on the left side of the junction and is thus included in a regular block.

4. The number of problematic blocks that are junction blocks of type 2 has already been considered when considering the gadgets.

All the red blocks corresponding to words of S and that are not problematic have to appear in distinct regular green blocks by Property (P2). As before, a word of S is obtained by choosing its beginning before the interval and its end after, so that

|S| ≥ |u| -5m - 2kl i -4m -2 -(A + 2m) • A.
Therefore:

|S| -(2k 158

√ l + 2m + 1) ≤ l |u| -7m -2kl i-4m-2
From now on, we consider a sequence of families F = (F i ) i≥0 , with parameters (l i ) and (p i ), that has both Properties (P1') and (P2') for the parameters (m i ) and (k i ) de ned above. Remark that the integers q i x de ned in De nition 11.1 satisfy q i

x ≤ m i thanks to Property P2(i). The word w that we consider is the word w F (De nition 11.1) where gadgets have possibly been added between the regular green blocks exactly as in the algorithm of Chapter 10. Since F satis es (P1') and (P2'), and the parameters l i , p i fall within the range of Theorem 7.10, it can be shown as in Chapter 10 that a chain of w coming from F i will be parsed in ≥ l 3/2 i /54 red blocks in 0w but in only ≤ 3l i /2 green blocks. The following two lemmas show Theorem 7.6, i.e., that w satis es the one-bit catastrophe. We begin with the upper bound on the compression ratio of w, before proving the lower bound for 0w in Lemma 11.4. Let j and q be the integers such that the n-th bit of w belongs to the q-th chain of the j-th family, or in other terms, that w <n is the concatenation of the chains coming from ∪ i<j F i and of the rst q -1 chains of F j , together with a piece of the q-th chain of F j .

We rst give a lower bound on n as a function of the di erent parameters. A chain coming from Family F i is of the form Pref >q i x (x) together with possible gadgets, where q i

x ≤ m i ≤ √ l i . Therefore, the size of such a chain is at least

l i j=m i j ≥ l 2 i -m 2 i 2 = l 2 i 2 -o(l 2 i ).
Thus, using l j = 2l j-1 , we get:

n + o(n) ≥ j-1 i=0 |F i | l 2 i 2 + (q -1) l 2 j 2 ≥ l 2 j-1 2 (|F j-1 | + q)
associative world, yields a lower bound on P . This is the same as giving a lower bound on the rank of a parametrized Hankel matrix; it might be a way of tackling the problem of nding lower bounds for general non commutative circuits.

• Polynomial Identity testing. To the best of our knowledge, all known polynomial time algorithms for PIT are designed for classes of circuits that have at most a constant number of distinct parse trees. While it is intuitive 1 to understand why such a parse trees restriction is a convenient assumption to design good algorithms, we believe that in this phenomenon lies a technical barrier that has to be studied deeper in order to bypass the problem and to design new kinds of algorithms that could work for more general classes of circuits.

Part two: Lempel-Ziv, a "One-bit catastrophe" but not a tragedy

We have privileged "clarity" over optimality, hence constants can undoubtedly be improved rather easily. In that direction, a (seemingly harder) question is to obtain ρ sup (w) = 0 and ρ inf (0w) = 1 in Theorem 7.6. But even if such a catastrophe is not possible, it means there is a maximal constant α ∈]0, 1[ for which it is possible to get ρ sup (w) = 0 and ρ inf (0w) = α for some word w; what is this threshold α?

The main challenge though, to our mind, is to remove the gadgets in our constructions. Remark that the construction of Chapter 9 can also be performed with high probability with a random word instead of a de Bruijn sequence (that is what we do in Chapter 10 in a more general way). Thus, if we manage to get rid of the gadgets using the same techniques as presented here, this would mean that the "weak catastrophe" is the typical case for optimally compressible words. Simulations seem to con rm that conclusion.

Another possible direction is to understand the typical expected variation for a xed compression ratio. For this question, even getting some estimations by simulations seems hard, as sampling uniformly at random from the words of a xed LZ'78 compression ratio is a challenging task.

Index

  exquises quiches 1 que vous pourrez probablement tester d'ici 1h45 environ, à ce stade. * * * Merci à ma belle-famille pour leur chaleureux accueil et la quantité astronomique de marocchinos consommée.

  : • move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, move right hand, move left foot, move left hand, move right foot, 2 Don't ask me what kind of crazy route it can be.

Figures 1 and 2 (

 2 Figures 1 and 2 (roughly) represent what was known before and what is known now in the restricted context of this thesis.

Figure 1 . 1 :

 11 Figure 1.1: Example of an arithmetic circuit of depth 5. The blue gates are the inputs. The red gate is the output. The number of nodes is 12. The number of edges is 17.

Figure 1 . 6 :

 16 Figure 1.6: Association between gates in a parse formula and nodes in the shape. Gates and nodes of same color are associated. Left: a parse formula. Right: the corresponding shape

  A parse formula and a gate Φ which is associated to a gate v ∈ T of type (i, p).p i d -p -i (b)Repartition of the variables in the monomial computed by the parse formula.

Figure 1 . 7 :

 17 Figure 1.7: Type of a gate in a parse formula.

Figure 1 .Figure 1 . 8 :

 118 Figure 1.8 gives a parse trees' point of view of some classes that we will de ne later.

  [d] given by an ordered pair (Y, Z), where Y ⊆ [d] and Z = [d] \ Y . In what follows we only use ordered partitions of sets into two parts. We say that such a Π is balanced if |Y | = |Z| = d/2. Given a monomial m of degree d and a set W ⊆ [d], we use m W to denote the monomial of degree |W | obtained by keeping only the variables in the locations indexed by W and dropping the others. For example, if W = {1, 3} ⊆ [4] and m = xyzt, then m W = xz. De nition 1.10: Partial Derivative matrix Let f ∈ F X be a homogeneous polynomial of degree d over n = |X| variables. Given a partition Π = (Y, Z) of [d], we de ne an n |Y | × n |Z| matrix M [f, Π] with entries from F as follows: the rows of M [f, Π] are labelled by monomials from M |Y | (X) and the columns by elements of M |Z| (X). Let m ∈ M |Y | (X) and m ∈ M |Z| (X); the (m , m )th entry of M [f, Π] is the coe cient in the polynomial f of the unique monomial m such that m Y = m and m Z = m . Example 1.11

  a homogeneous polynomial of degree d over n = |X| variables. For any Y ⊆ [d], we de ne the relative rank of f w.r.t. Π = (Y, Z)denoted rel-rank(f, Π)-to be rel-rank(f, Π) := rank(M [f, Π]) n |Y | . Fix a partition Π = (Y, Z) of [d] and two homogeneous polynomials g, h of degrees d g and d h respectively. Let f = g × j h for some j ∈ [0, d h ]. This induces naturally de ned partitions Π g of [d g ] and Π h of [d h ] respectively in the following way. Let I g = [j + 1, j + d g ] and I h = [d] \ I g . We de ne Π g = (Y g , Z g ) such that Y g corresponds to the indices of the elements of

Figure 2 . 1 :

 21 Figure 2.1: You are here.

Figure 3 . 1 :

 31 Figure 3.1: You are here.

Let

  C be a UPT circuit in normal form over F X of size s = N c , where N = |X|, and f the homogeneous polynomial of degree d computed by C. Let Π be a uniformly random partition of the variables of [d] into two sets. Then for any parameter b ∈ N,

Figure 4 . 1 :

 41 Figure 4.1: You are here.

Observation 4. 1

 1 For any I ⊆ [d] of size t and any f ∈ P I , we have rank(M I (f )) ≤ n 2 t/2 . For any I ⊆ [d] of size t, we have rank(M I (IMM I )) = n 2 t/2 , and hence rel-rank I (IMM I ) = 1.

Observation 4. 3 1. 2 .

 32 If P ∈ P [d] , then P | I ∈ P I . IMM n,d | I = IMM I .

Lemma 4. 4

 4 For any [d]-labelled UPT formula F of size s and shape T computing some f (note that f ∈ P [d] by Observation 4.2), there is a UPT formula F | I of size at most s and shape T | I computing f | I .

Theorem 4. 10

 10 Let n, d be growing parameters with d ≤ log n. Then, any k-PT formula F computing IMM n,d has size at least n where = Ω(log d -log log k).

  rel-rank I (IMM n,d | I ) = rel-rank I (IMM I ) = 1. (4.2)

Figure 5 . 1 :

 51 Figure 5.1: You are here.

  and similarly, {λ w m | m ∈ B w,+ } spans all the vectors in {λ w m | m ∈ M deg(w) (X)}. Now, note that for any monomial m ∈ M deg(v) (X), there is a unique pair of monomials m ∈ M deg(u) (X) and m ∈ M deg(w) (X) such that m = m m . Further, the coe cient of monomial m in the polynomial computed at Φ i is the product of the coe cients of m at Φ i and m at Φ i . In other words, we have λ v m = λ u m • λ w m , the pointwise product of the vectors λ u m and λ w m . By linearity, it follows that the coe cient vectors corresponding to the monomials in B u,w := B u,+ • B w,+ = {m m | m ∈ B u,+ , m ∈ B w,+ } span Cv,× . Since |B u,w | has size at most s 2 , both B u,w and the corresponding coe cient vectors can be computed in time poly(s). By Gaussian elimination, we can nd in time poly(s) the sets B v,× and Bv,× as required.

Theorem 5 .

 5 10: theorem Let N, s, k ∈ N with N ≤ s. There is a deterministic algorithm running in time s O(2 k ) which, on input k + 1 UPT circuits C 0 , C 1 , . . . , C k (of possibly di ering shapes) each of size at most s over N variables, decides whether k i=0 C i computes the zero polynomial.

  s and also • if v is a leaf node and I v = i then, for each x ∈ X and for each m ∈ B v , it computes coe cients c v x,m such that ∂ i,x (P ) = m∈Bv c v x,m •∂ i,m (P ), • if v is an internal node with children u, w, then for all m ∈ B u,w := B u • B w and for all m ∈ B v , it computes coe cients c v m ,m such that ∂ Iv,m (P ) = m∈Bv c v m ,m • ∂ Iv,m (P ).

3 ) 5 . 13 Equations 5 . 2 , 5 . 3

 35135253 Claim imply that for any node v ∈ T and any m ∈ M |Iv| (X) and m ∈ B v , there exist c v m ,m ∈ F such that

  [d],m (P ) = ∂ [d],m (Q) (as described in Step 4). Note that for any m of degree d, ∂ [d],m (P ) and ∂ [d],m (Q) are simply coe cients of the monomial m in P and Q respectively.

Claim 5. 15

 15 Let v ∈ T and t := deg(v). For any m such that deg(m ) = t and for any set

Figure 6 . 1 :

 61 Figure 6.1: You are here.

Figure 6 . 2 :

 62 Figure 6.2: An example of an ABP with 4 layers and of size 8.

Figure 6 . 3 :

 63 Figure 6.3: An example of 3-layered WA on the left, and its corresponding ABP on the right.

Figure 6 . 4 :

 64 Figure 6.4: The Hankel matrix of P consists of d + 1 independent blocks.

Figure 6 . 8 :

 68 Figure 6.8: The Hankel matrix for the polynomial x 2 n and the shape T being the full binary tree.

1

 1 Notions relative to LZA k-partition (or just partition) of a word w is a sequence of k non-empty words m 1 , . . . , m k such that w = m 1 .m 2 . • • • .m k . The LZ-parsing (or just parsing) of a word w is the unique partition of w = m 1 • • • m k such that:

3 Figure 7 . 1 :

 371 Figure 7.1: Parse tree of 00010110100001.

  As the two previous extremal cases show, k log k = Ω( |w| log |w|) and k log k = O(|w|). De nition 7.2 The compression ratio of a word w is ρ(w) = |Dic(w)| log |Dic(w)| |w| .

ρ

  inf (w) = lim inf n→∞ ρ(w <n ) and ρ sup (w) = lim sup n→∞ ρ(w <n ).

Theorem 7. 7 For

 7 every word w ∈ {0, 1} and any letter a ∈ {0, 1}, |Dic(aw)| ≤ 3 |w|.|Dic(w)|. Remark 7.8

Theorem 7. 9 For

 9 an in nite number of words w ∈ {0, 1} , |Dic(0w)| ≥ 1 35 |w|.|Dic(w)|.More generally, we prove in Chapter 10 our main result:Theorem 7.10 Let l : N → N be a function satisfying l(n) ∈ [(90 log n) 2 , √ n].Then for an in nite number of words w:

Remark 7. 11

 11 In particular: • Theorem 7.7 implies that, if an increasing sequence of words (w n ) satis es |Dic(w n )| = o(|w n |/ log 2 |w n |), then for any letter a ∈ {0, 1}, aw n remains fully compressible (|Dic(aw n )| = o(|w n |/ log |w n |));

1 .

 1 More generally, we can get |Dic(wn )| = Θ(|w n | α ) and |Dic(0w n )| = Θ(|w n | (1+α)/2 ) for any α ∈ [1/2, 1].

Figure 7 . 2 :

 72 Figure 7.2: The green blocks of w and red blocks of 0w for w = 001010100011.

Remark 8. 2 2 partitionedN 2 N

 222 Note that if, for all i ≥ 1, F contains exactly min(2 i , N ) words of size i, the concatenation of all the words of F up to size s gives a word w of size|w| = 2N log N + (s -log N )(s + log N + 1)N/≥ (s -log N )N.Thus m ≥ √ |w| if s >> log N . This shows the optimality of Lemma 8.1 up to a factor √ 2.

Proof of Theorem 7 . 7 .

 77 Let T be the parse tree of w and D = Dic(aw) be the set of red blocks. We partition D into D 1 and D 2 , where D 1 is the set of junction blocks together with the rst red block (consisting only of the letter a), and D 2 is the set of o set blocks.• Bound for D 1 : The number of junction blocks is less than the number of green blocks, therefore|D 1 | ≤ |Dic(w)| ≤ |Dic(w)|.|w| (recall that |Dic(w)| ≤ |w|).• Bound for D 2 : Consider w the word w where all the junction blocks have been replaced by the empty word λ. We know that w is partitioned into di erent words by D 2 . But D 2 ⊂ F, where F = F (Dic(w)) (the set of factors contained in the green blocks). By Lemma 8.3, the number of words of size i in F is bounded by |T | -i, which is at most |Dic(w)|. Finally, Lemma 8.1 tells us that the number of words in any partition of w by words of F is bounded by 2 |Dic(w)|.| w| ≤ 2 |Dic(w)|.|w|. In the end, |D| = |D 1 | + |D 2 | ≤ 3 |w|.|Dic(w)|. Remark 8.4 Instead of a single letter, we can add a whole word z in front of w. With the same proof, it is easy to see that |Dic(zw)| ≤ |Dic(z)| + 3 |w|.|Dic(w)|. Alternately, if we remove the rst letter of w = aw (or any pre x) we get the same upper bound: |Dic(w )| ≤ 3 |aw |.|Dic(aw )|. 127 Chapter 9

Theorem 9. 1 For|w| 3 / 4 -

 134 an in nite number of words w: |Dic(w)| ≤ 1.9 |w| and |Dic(0w)| ≥ 0.039|w| 3/4 .Remark 9.2The "true" values of the constants that we will get below are as follows: o(|w| 3/4 ).

Figure 9 . 1 :Figure 9 . 2 :

 9192 Figure 9.1: Illustration of Step 4(b) of the algorithm.

  If the algorithm stops at step 1, then w = Pref(x) and it is compressed optimally (see Remark 7.1): the compression size is √ 2 |w| + O(1).

Figure 9 . 3 :

 93 Figure 9.3: Blocks ending at position i -1 for the proof of Proposition 9.7.

|w| 3 / 4 -

 34 o(|w| 3/4 ) ≥ 0.039|w| 3/4 . Remark 9.8

Figure 10 . 1 :

 101 Figure 10.1: Parameters used throughout Chapter 10.

  ∃i ∈ [|u|/2, |u| -1] : u[0..i -1] = u[|u| -i..|u| -1] (we say that u is i-bad).

- 2 ≤ 2 √

 22 l + 3k + 7m + 2kl i -4m -2 .

Lemma 11. 3 ρ

 3 sup (w) = 0. Proof. By de nition (De nition 7.5), ρ sup (w) = lim sup n→∞ ρ(w <n ), therefore we need to show that ρ(w <n ) = G(log G)/n tends to zero, where G = |Dic(w <n )| is the number of green blocks in the parsing of w <n . Let us evaluate this quantity for a xed n.

  gate of formal degree e with left input Ψ of formal degree e 1 and right input Γ of formal degree e 2 , then in D, Φ k has left input Ψ k and right input Γ k+e 1 . In C, if Φ is a +-gate of formal degree e with inputs Ψ 1 , Ψ 2 , . . . , Ψ j with coe cients c 1 , c 2 , . . . , c j , then, in D, Φ k has inputs Ψ 1

	k , Ψ 2 k , . . . , Ψ j k
	with coe cients c 1 , . . . , c j .

  • Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 -Aalborg, Denmark, pages 41:1-41:14, 2017

• Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees (extended version). To appear in Computational Complexity

  and k 1 , . . . , k t < k. We observe that one of d k 1 , . . . , d kt must be at least d .To see this, assume that d ka < d for each a ∈ [t] and consider any parse formula C containing Ψ k (such a formula must exist since otherwise Ψ k would have been removed in the rst simpli cation step). By our assumption on the circuit, C must also contain some gate Ψ computing a polynomial of degree exactly d . Note that Ψ does not lie in the subcircuit of C induced by the gate Ψ k since all the non-output gates of this subcircuit compute polynomials of degree < d and the output gate computes a polynomial of degree > d . Also, as d k > d , Ψ k does not appear in the subcircuit of C induced by Ψ . Consider the parse tree T obtained by unraveling the circuit C . By the observations above, Ψ k gives rise to (at least) one node u in T of degree d k > d and Ψ gives rise to a node v in T of degree d . Thus, the degree of the root is at least deg(u) + deg(v) > 2d > d, which is a contradiction since in a homogeneous circuit all parse trees have exactly d leaves.So we can assume that deg(f ka ) ≥ d for some a ∈ [t]. Applying the induction hypothesis to f ka we have

  • • • gt . Assume that deg(g a ) = d a for each a ∈ [t]. Then {d 1 , . . . , d t } = {d 1 , . . . , d t } as multisets, where d a = deg(v a ) as de ned above; in particular, d a < 3 4 d for each a. Thus, g × j

  n,d , yielding separations from ABPs. More speci cally, we prove in Section 4.2 a tight superpolynomial lower bound on the size of any UPT formula that computes IMM n,d . In Section 4.3, we prove a superpolynomial lower bound for any formula computing IMM n,d as long as the number of distinct parse trees is signi cantly smaller than 2 d (assuming d ≤ log n).

	This chapter is based on the following publication:
	• Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds
	and PIT for non-commutative arithmetic circuits with restricted parse trees.
	In 42nd International Symposium on Mathematical Foundations of Computer
	Science, MFCS 2017, August 21-25, 2017 -Aalborg, Denmark, pages 41:1-41:14,
	2017

• Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees (extended version). To appear in Computational Complexity

explicit meaning in general that coe cients are computable by a reasonable algorithm (in P for example)

In fact, the VP versus VNP question is closer to the LOGCFL versus #P question.

This is not exactly the standard de nition of IM M n,d which is in general, de ned as the polynomial in the rst row and column of the matrix M 1 • M 2 • • • M d . However, taking the trace of the matrix gives a more symetric de nition and help in writing cleaner statements.

In contrast, we do not yet have superpolynomial lower bounds for depth-3 formulas in the commutative setting for computing any explicit polynomial.

This is what we did in the previous subsection. Indeed, our measure µ will be the rank of the matrices M [ , Π] for well chosen partition Π depending on the class of circuits that is considered.

This point will be the core of all the next chapters. Most often, a chapter will consist of nding a good decomposition of the polynomials computed by a class of circuits. This decomposition will lead us to nd partitions Π that make the rank of the computed polynomials small.

This point is already done by the following theorem, which was shown in[START_REF] Limaye | Lower bounds for non-commutative skew circuits[END_REF].

-(b + c) for each u ∈ I(T ). By (3.1), this means that for each u ∈ I(T ), | Π, Π u | ≤ γ for some γ = O(b + c).

Note that we only need the o -path nodes to form an antichain and not the nodes on the path itself.

We write the underlying polynomial f of degree d computed by the ABP as a polynomial of degree d where the coe cients are themselves polynomials of degree d -d and multiply the monomials of degree d to the left.

Recall that the output gate of the circuit C is always assumed to be a + gate, possibly of fan-in 1.

Note that the gates Φ i and Φ j may coincide even if i = j. This does not matter for our argument.

n / log(n)), worse than the ABP.

Actually, throughout the manuscript we preferred readability over optimality and thus did not try to get the best possible constants; simulations show that there is a lot of room for improvement, since already for small words the di erence is signi cant (using notation introduced in Section 7 and Chapter 9, for w = Pref(x) with x ∈ DB(12), |w| 8.10 6 and w is parsed in about 4100 blocks, whereas 0w is parsed in more than

200,000 blocks).

Note that, in order to recover the parsing from the parse tree, the vertices must also be labeled by the order of apparition of each block, but we do not need that in the sequel.

Except the rst block of aw, which is the word a and which is just called a red block.

This is to avoid dealing with the fractional part of s/2, but the construction also works in the case where k is even.

That is not a circular argument because we only need the result up to z j-1 to claim the existence of gadgets for z j .

Indeed, such a restriction allows to compare "submonomials"-which is an easier task-in order to say something on the "full monomials".

Acknowledgements

De nition 6.4

A weighted automaton A = (Q, q 0 , ∆, F ) is d-layered if Q can be partitioned into d + 1 subsets Q 0 , . . . , Q d such that (1) Q 0 = {q 0 }, (2) for all x ∈ X, q, q ∈ Q, if ∆(q, x, q ) = 0 then there exists i ∈ {0, . . . , d -1} such that q ∈ Q i and q ∈ Q i+1 ,

(3) for all q ∈ Q, if F (q) = 0 then q ∈ Q d .

Lemma 6.5

• For all ABP C, there exists a WA over words A of the same size such that f A = P C .

• For all WA over words A which is layered, there exists an ABP C of the same size such that P C = f A .

Proof. Both claims are syntactic easy transformations. We explicit the construction to help the reader's intuition.

Let C be an ABP. We de ne a WA over words A as follows. The set of states is the set of vertices of C, the initial state of A is the source vertex of C, and the output function F : Q → R is de ned by F (v) to be the output value of v if v is on the last layer, and 0 otherwise.For the transition function, let ∆(v, x, v ) be the coe cient of x in the linear function labeling the edge (v, v ) if (v, v ) ∈ E, and 0 otherwise. See Figure 6.3. We have f A = P C .

For the second claim, the de nition of d-layered WA over words exactly says that the above construction can be reversed.

Fliess' theorem

The key notion of this chapter is the Hankel matrix of a series.

such that

u | u ∈ X * . We furthermore assume that ε ∈ Q, which is possible since H (f ) ε = 0 unless f is the constant zero function.

We now construct the WA recognising f . The set of states is Q, the initial state is ε, and the output function is de ned by F (u) = f (u) for u ∈ Q. We now de ne the transition function. For u ∈ Q, there is a unique decomposition of

we de ne ∆(u, x, v) = λ(u, x, v).

Proof of Nisan's theorem Lemma 6.8

Let P be a homogeneous polynomial of degree d. The automaton constructed above for recognising P is d-layered.

Proof. Let A = (Q, ε, ∆, F ) be the automaton described in the previous subsection.

Since for u of length larger than d we have H (f ) u = 0, it implies that Q ⊆ X ≤d . For i ∈ {0, . . . , d}, we let Q i = Q ∩ X i . The conditions [START_REF] Aboy | Interpretation of the Lempel-Ziv complexity measure in the context of biomedical signal analysis[END_REF] and (3) are clearly satis ed, so we focus on [START_REF] Allender | Non-commutative arithmetic circuits: Depth reduction and size lower bounds[END_REF].

For i ∈ {0, . . . , d}, let V i denote the vector space spanned by

Note that for u ∈ Q i and v of length j, if i + j = d then H (P ) u (v) = P (u • v) = 0, hence the same is true for any L ∈ V i : if v has length j such that i + j = d, then L(v) = 0.

We claim that the subspaces V 0 , V 1 , . . . , V d are in direct sum. Indeed, assume that d i=0 L i = 0 with L i ∈ V i . Let j ∈ {0, . . . , d} such that L j = 0, and consider a word v ∈ X d-j . For i = j we have L i (v) = 0 thanks to the remark above. It follows that L j (v) = 0 for all v ∈ X d-j , implying again with the remark above that L j = 0, a contradiction. Thus the subspaces V 0 , V 1 , . . . , V d are in direct sum.

Let u ∈ Q and x ∈ X. By de nition

Minimisation of weighted automata over trees

The following theorem extends Fliess' theorem.

Theorem 6.15: [START_REF] Bozapalidis | The rank of a formal tree power series[END_REF] Let f : Tree(X) → R be a tree series such that rank(H (f ) ) is nite.

• Any WA recognising f has size at least rank(H (f ) ).

• There exists a WA recognising f of size exactly rank(H (f ) ).

We detail the construction for the second item as we will need it to prove Theorem 6.11.

Recall that the rows of H (f ) are indexed by trees in Tree(X). For t ∈ Tree(X), let H (f ) t be the row corresponding to t in H (f ) , which we see as

We furthermore assume that Q contains at least one tree reduced to a single variable x ∈ X, which is possible since H (f ) x = 0 for some x ∈ X unless f is the constant zero series.

We now construct the WA recognising f . The set of states is Q. The initial function is de ned by ι(x, t) = 1 if t is the variable x ∈ X, and 0 otherwise. We now de ne the transition function. For t 1 , t 2 ∈ Q, there is a unique decomposition of H (f )

Proof of Theorem 6.11 Lemma 6.16 Let P be a homogeneous polynomial of degree d and T a shape with d leaves. The automaton constructed above for recognising P is T -layered.

Proof. Let A = (Q, ι, ∆, F ) be the automaton described in the previous subsection.

Part II

Lempel-Ziv: a "One-bit catastrophe" but not a tragedy

De Bruijn sequences

A de Bruijn sequence of order k (or DB(k) in short, notation that will also designate the set of all de Bruijn sequences of order k) is a word x of size 2 k + k -1 in which every word of size k occurs exactly once as a substring. For instance, 0001011100 is an example of a DB(3). Such words exist for any order k as they are, for instance, Eulerian circuits in the regular directed graph whose vertices are words of size (k -1) and where there is an arc labeled with letter a from u

Given any x ∈ DB(k), the following well-known (and straightforward) property holds:

( ) Any word u of size at most k occurs exactly 2 k-|u| times in x.

(In symbols, Occ x (u) = 2 k-|u| .) Thus, a factor of size l ≤ k in x will identify exactly 2 k-l positions in x (the i-th position is the begining of the i-th occurence of the word).

The use of de Bruijn sequences is something common in the study of this kind of algorithms: Lempel and Ziv themselves use it in [START_REF] Lempel | On the complexity of nite sequences[END_REF], as well as later [START_REF] Lathrop | A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data[END_REF] and [START_REF] Pierce | Sequences Incompressible by SLZ (LZW), Yet Fully Compressible by ULZ[END_REF] for example.

Overview of the proof

Recall that a word w is optimally compressed i it is of the form w = Pref(x) for some word x (Remark 7.1). Thus we are looking for an x such that 0Pref(x) has the worst possible compression ratio. In Chapter 8 the upper bound on the dictionary size came from the limitation on the number of possible factors of a given size: it is therefore natural to consider words x where the number of factors is maximal, that is, de Bruijn sequences.

Although we conjecture that the result should hold for w = Pref(x) whenever x is a de Bruijn sequence beginning with 0, we were not able to show it directly. Instead, we need to (possibly) add small words, that we will call "gadgets", between the pre xes of x.

For some arbitrary k, we x x ∈ DB(k) and start with the word w = Pref(x) of size n. The goal is to show that there are Ω(n 3/4 ) red blocks (i.e., that the size of the dictionnary for 0w is Ω(n 3/4 )): this will be achieved by showing that a signi cant (constant) portion of the word 0w is covered by "small" red blocks (of size O(n 1/4 )). Let s = |x|, so that n = Θ(s 2 ). More precisely, we show that, in all the pre xes y of x of size ≥ 2s/3, at least the last third of y is covered by red blocks of size O( √ s) = O(n 1/4 ). This is done by distinguishing between red blocks starting near the beginning of a green block (o set-i for i ≤ γk) and red blocks starting at position i > γk:

• Finally, Proposition 9.7 uses Lemma 9.6 to show that the o set-i red blocks are small if i is large.

Construction and rst properties

Let γ be any constant greater than or equal to 3. Let x be a DB(k) beginning by 01. We denote its size by s = 2 k + k -1. Suppose for convenience that k is odd, so that s is even. 1 For i ∈ [0, s -1], let w i = x ≤i , so that Pref(x) = w 0 .w 1 . . . w s-1 .

The word w that we will construct is best described by an algorithm. It will merely be Pref(x) in which we possibly add "gadgets" (words) between some of the w j in order to control the parsings of w and 0w. The letter in front that will provoke the "catastrophe" is the rst letter of w, that is, 0.

The gadgets g j i (for i ∈ [0, γk] and j ≥ 0) are de ned as follows (where xi denotes the complement of x i ):

• g j 0 = 10 j ; • and for i > 0, g j i = x <i .x i .1 j . Recall that the green blocks are those of the parsing of w, whereas the red ones are those of the parsing of 0w. We call "regular" the green blocks that are not gadgets (they are of the form w j for some j). For i ∈ [0, s -1], we say that a regular green block in w is i-violated if there is an o set-i (red) block in it. Note that gadgets do not count in the de nition of a violation.

Lemma 9.3

For i ∈ [0, s -1], let l i be the number of i-violated blocks in Pref(x) = w 0 .w 1 . . . w s-1 . Then for all i = i , l i + l i ≤ s.

In particular, there can be at most one i such that the number of i-violated blocks is > s/2. Proof. Let i and i be such that 0 ≤ i < i < s.

Consider the red blocks starting at position i and i in any green block.

No green block in w 0 . . . w i -1 is i -violated since they are too small to contain position i . Let a be the number of i-violated blocks in w 0 . . . w i -1 . In w i . . . w s-1 , let b be the number of green blocks that are both i-violated and i -violated, and let c (respectively d) be the number of i-violated (resp. i -violated) blocks that are not i -violated (resp. i-violated) blocks.

• Type 2: junctions starting in a gadget g j j and ending in the following regular green block;

• Type 3: junctions starting in a regular green block and ending in the following gadget g j j .

Lemma 9.6

Let i ≥ 2k + 3. Let uu be a junction block of type 1 over w a w a+1 ending at position i -1 in w a+1 , with u being the su x of w a and u the pre x of

In particular, the number of such blocks is upper bounded by the number of words of size ≤ k -log(i -2k -1), that is,

Proof. Let v be the pre x of size 2k of u (which is also the pre x of x). All the pre xes of uu of size ≥ |uv| have to be in the dictionary of 0w: we call M the set of these pre xes (|M | = i -2k). We claim that these blocks are junction blocks of type 1 or 3 only (except possibly for one of type 2), with only u on the left side of the junction. Indeed, let us review all the possibilities:

1. uv cannot be completely included in a regular block, otherwise v[0..k -1] would appear both at positions 0 and p > 0 in x, which contradicts Property ( ) (page 130);

2. uv cannot be completely included in a gadget:

• if the gadget is g j 0 = 10 j , impossible because v cannot have more than k zeroes since it is a factor of x,

• if the gadget is g j b = x <b .x b .1 j , by the red parsing of gadgets, either uv is in x <b (impossible because v would appear at a position ≥ |u| in x), or uv is in xb .1 j (impossible because v cannot contain more than k ones); 3. if uv is a type 1 junction but not split between u and v, it is impossible because the three possible cases lead to a contradiction:

• if u goes on the right, then v would appear at another position p > 0 in x,

• if v goes on the left by at least k, then v[0..k -1] would again appear at two di erent positions in x,

• if v goes on the left by less than k, then it goes on the right by more than k and v[k..2k -1] would again appear at two di erent positions in x;

4. if uv is a type 2 junction but not split between u and v, it is again impossible:

• if u goes on the right, then v would appear at another position p > 0 in x, • if v goes on the left by at least 2, then v[0..1] would be either 00 or 11

(depending on the gadget), but we know it is x 0 x 1 = 01, • otherwise, v goes on the right by 2k -1, and v[1..k] would appear at positions 0 and 1 in x;

5. if uv is a type 3 junction, rst remark that the gadget is of the form g j b for b > 0 (because, for gadgets of the form g j 0 , the red parsing starts at position 0 of the gadget). If uv is not split between u and v, it is once again impossible:

• if u goes on the right, the red parsing of the gadget stops after x <b and v would appear in x at a non-zero position, • similarly, if v goes on the left by less than k, then v[k..2k -1] would again appear at two di erent positions in x, • if v goes on the left by at least k, then v[0..k -1] would again appear at two di erent positions in x.

Remark nally that all parsings of type 2 junctions have di erent sizes on the left. Therefore, at most one can contain u on the left. The claim is proved. Thus, at least |M | -1 regular green blocks have u as su x. Remark that, since |M | ≥ 3, there are at least two such green blocks, therefore |u| ≤ k. Hence by Property ( ) (page 130) we have:

As a consequence, in the next proposition we can bound the size of o set-i blocks. Along with the role of gadgets, this will be a key argument in the proof of Theorem 9.1. The idea is the following: for a red block u starting at a su ciently large position i, roughly |u| other red blocks have to end at position (i -1), and in the red parsing Ω(|u| 2 ) pre xes of these blocks must appear in di erent green blocks (and in the dictionary), giving the bound s = Ω(|u| 2 ).

Let p and l be positive integers such that p ≤ √ l. Let F be a family of 2 p words x 1 , . . . , x 2 p of size l chosen uniformly and independently at random. Then F satis es Property (P1) with probability 2 -Ω( √ l log log l) .

Proof. Fix a word u of size ≤ k and take x of size l at random. For i ∈ [0, k -1] and j ∈ [0, l/k -1], let

For a xed i, the X i j are independent. Let µ i = E( j X i j ). We have:

By the Cherno bound (Theorem 10.1):

By union bound over all the words u of size at most k, all the words of F and all the moduli i ∈ [0, k -1], we have:

The analysis for (P2) does not use Cherno bounds, but instead it uses a slight "independence" on the occurrences of a factor u obtained by showing that u can be supposed "self-avoiding" (the precise meaning of these ideas will be clear in the proof).

• for i > 0 and c ≥ 0, let m = max(i, m) and v = x j [0..m -1]1 l . Then:

where xj m denotes the complement of x j [m ]. We de ne i-violations in each chain z j as previously, that is, a regular green block is i-violated if it contains an o set-i red block. The following lemma is proved in the exact same way as Lemma 9.3.

Lemma 10.6

For j ∈ [1, 2 p ] and i ∈ [0, s j -1], let l j i be the number of i-violated blocks in z j . Then for all j and all i = i , l j i + l j i ≤ s j . In particular, for each z j there can be at most one i such that the number of i-violated blocks is > s j /2.

The formal construction of the word w is once again best described by an algorithm taking as parameters n and l:

Throughout the algorithm, z j will denote z j q j +1 . . . z j l (and thus will vary if one of the z j i varies).

2. For j = 1 to 2 p do:

(a) if there is i ∈ [0, 2k √ l] (unique by Lemma 10.6) such that the number of i-violations in the chain z j is > s j /2, then: i. let c = 0 (counter for the number of inserted gadgets in z j ) and d = s j /2 + 1 (counter for the place of the gadget to be inserted), ii. while the number of i-violations in the chain z j is ≥ d, do:

A. let r be such that z j r is the d-th i-violated green block in z j , B. z j r ← g c i (j)z j r (we add the gadget g c i (j) before the block

Remark that we have the following bounds on the size of w . Its size is minimal if no gadgets are added:

Proposition 10.9

Let f (i) be the maximal size of an o set-i (red) block included in a regular green block.

Proof. The rst point is a consequence of Lemmas 10.10 and 10.11. The second point is exactly Lemma 10.13.

With Proposition 10.9 in hand, let us prove the main theorem.

Proof of Theorem 7.10. We will show that each chain z j in 0w is parsed in at least

Fix an index j. In order to prove that the chain z j is parsed in at least 1 54 l 3/2 red blocks, we rst prove that in every regular green block of size larger than 2l/3 in the chain z j , there is an interval of positions [2l/3 -A, 2l/3] (with A = 3 √ l), such that there is at least one o set-i (red) block for i ∈ [2l/3 -A, 2l/3]. Indeed, by Proposition 10.9, for any i < 2l/3 -A, the maximal size f (i) of a red block starting at position i satis es i + f (i) ≤ 2l/3.

Therefore, since the red blocks starting at position i ≥ 2l/3 -A are of size at most f (2l/3 -A) ≤ 3 √ l, a regular green block of z j of size h is covered by at least (h -2l/3)/(3 √ l) red blocks. Thus the number of red blocks in the parsing of z j is at least

Now we prove Proposition 10.9 thanks to the next four lemmas. The rst two show that the gadgets do their job: indeed, for small i (the indices i covered by the gadgets), the o set-i blocks are not too large. For that, we rst bound the number of violations.

If the number of i-violations is not too large, then the same is true for the size of o set-i blocks, as the following easy result states.

Lemma 10.11

If the number of i-violations in the chain z j is b, then any o set-i block u in a regular block of z j is of size at most b + 2k √ l.

Proof. The |u| -2k √ l predecessors of u of size at least 2k √ l + 1 cannot appear in gadgets, hence by Property (P2) they must appear at position i in the regular green blocks of the chain z j . Therefore, each such predecessor contributes to an i-violation in z j , so that |u| -2k √ l ≤ b. Now, the next two results show that, for large i, the size of o set-i blocks is small. First, we need to bound the number of junction blocks ending at position i -1.

Lemma 10.12

Let j be xed and i > 2k √ l. Let uu be a junction block of type 1 between two regular green blocks w j a and w j a+1 , ending at position i -1 in w j a+1 (thus |u | = i). Then |u| ≤ log(kl) -log(i -4m -2).

In particular, the number of such blocks is upper bounded by 2kl i-4m-2 .

Proof. Let v be the pre x of size 4m + 1 of u (which is also the pre x of x j ).

We claim that all the pre xes of uu of size ≥ |uv| are junction blocks of type 1 or 3 only (except possibly for one of type 2), with only u on the left side of the junction. Indeed, recalling the red parsing of gadgets explained in the proof of Lemma 10.10 and Property (P2), we distinguish the following cases:

1. uv cannot be completely included in a regular block, otherwise v[0..m -1] would appear both at positions 0 and p > 0 in x j , which contradicts Property (P2);

2. uv cannot be completely included in a gadget:

• if the gadget is g c 0 (j), then v would contain a m+1 for some a ∈ {0, 1}, • if the gadget is g c b (j) for b > 0, let m = max(b, m): the red parsing splits this gadget between x j [0..b -1] and x j [b..m -1]x j m x j [0..m -1]1 d . Then uv is not contained in the rst part by (P2), nor in the second part since it cannot contain 1 m+1 ; 154 3. if uv is a type 1 junction but not split between u and v, it is impossible because the three possible cases lead to a contradiction:

• if u goes on the right, then v would appear at another position p > 0 in x j ,

• if v goes on the left by at least m, then v[0..m -1] would again appear at two di erent positions in x j ,

• if v goes on the left by less than m, then it goes on the right by more than m and v[3m + 1..4m] would again appear at two di erent positions in x j ;

4. if uv is a type 2 junction but not split between u and v, it is again impossible:

• if u goes on the right, then v would appear at another position p > 0 in x j ,

• if v goes on the left by at least 3m + 1, in case of g c 0 (j) then v would contain a 2m+1 and in case of g c b (j) then v would contain 1 m+1 (recall where the red parsing splits this gadget),

• otherwise, v goes on the right by at least m + 1, and v[3m + 1..4m] would appear at two di erent positions x j ; 5. if uv is a type 3 junction, rst remark that the gadget is of the form g c b (j) for b > 0 (because, for gadgets of the form g c 0 (j), the red parsing starts at position 0 of the gadget). If uv is not split between u and v, it is once again impossible:

• if u goes on the right, the red parsing of the gadget stops after x j <b and v would appear in x j at a non-zero position,

• similarly, if v goes on the left by less than m, then v[m..2m -1] would again appear at two di erent positions in x j ,

• if v goes on the left by at least m, then v[0..m -1] would again appear at two di erent positions in x j .

Remark nally that all parsings of type 2 junctions have di erent sizes on the left. Therefore, at most one can contain u on the left. The claim is proved. Thus u appears at least i -4m -2 times as a su x of a regular green block. Remark that Property (P1) implies that factors of size more than k appear at most k √ l times in x j . Thus, since i -4m -2 > k √ l, we have |u| ≤ k. Hence by Property (P1), the number of occurrences of u is upper bounded by kl/2 |u| . Therefore

which proves the rst part of the lemma.

The number of such blocks is then upper bounded by the number of words of size ≤ log(kl

The last lemma completes the preceding one: if an o set-i block is large, then a lot of blocks have to end at position i -1 and too many of their pre xes would have to be in di erent green blocks.

Lemma 10.13

For any j ∈ [1, 2 p ] and any i > 2k √ l, the size of an o set-i block included in a regular green block of the chain z j is at most

Proof. We argue as in Proposition 9.7. Let u be an o set-i block included in a regular green block of the chain z j . We show as before that the |u| -3m predecessors of u of size ≥ 3m have to start at position i in regular green blocks. Indeed, let v be a pre x of size ≥ 3m of u; let us analyse the di erent cases:

• If v is included in a regular green block, then it has to start at position i by Property (P2);

• v cannot be included in a gadget since it would lead to a contradiction:

in gadgets of type g c 0 (j), v would contain a m+1 for some letter a ∈ {0, 1},

), either v would contain 1 m+1 or a factor of x j of size m and at a position di erent from i;

• If v is included in a junction block of type 1, then v starts at position i in the left regular block, otherwise either v[0..m -1] would be in the left regular block at a position di erent from i, or v[m -1..2m -2] would be in the right regular block at a position ≤ 3m < i;

• v cannot be included in a junction block of type 2. Indeed, it cannot go by ≥ m on the right (by (P2)), thus it goes on the left by at least 2m + 1: for g c 0 (j) it would contain a m+1 (for some a ∈ {0, 1}), and for g c b (j) (b > 0), it would either contain 1 m+1 , or a factor of x j of size m at a position < m ≤ i;

• If v is included in a junction block of type 3, then v starts at position i in the left regular block, otherwise either v[0..m -1] would be in the left (regular) block at a position di erent from i, or, by the red parsing, the gadget is of type g c b (j) (for b > 0) and v[m -1..2m -2] would be included in x j at a position ≤ 3m < i.

Thus, at least |u| -3m red blocks end at position i -1 in the regular blocks of z j . Among them:

• By Lemma 10.12, at most 2kl i-4m-2 of them are junctions of type 1. • At most 2m of them are junctions of type 2, since from the (2m + 1)-th gadget on, the type 2 junctions end at position 0 (in case of gadgets g c b (j) for b > 0, see the proof of Lemma 10.10) or ≤ m + 1 ≤ i -1 (in case of gadgets g c 0 (j)).

• There is no junction of type 3 by de nition.

Overall, at least |u|-5m-2kl i-4m-1 of them are o set blocks, ending at position i -1. We call the set of such blocks M . Let

We say that a red block w is problematic if w ∈ S but the part of w corresponding to the factor x j [i -A -2m..i -A -m -1] is not completely included in a regular green block. We show that the number of problematic blocks is at most 2k √ l + 2m + 1.

1. The number of problematic blocks that overlap a gadget g c 0 (j) = ua c in the red parsing is at most m + 1. Indeed, ua c is never split by the red parsing, therefore for c ≥ m + 1, a red block that overlaps g c 0 (j) would contain a m+1 , which is not a factor of x j . Chapter 11

In nite words

The techniques on nite words developed in the preceding chapters can almost be used as a black box to prove the one-bit catastrophe for in nite words (Theorem 7.6). Our aim is to design an in nite word w ∈ {0, 1} N for which the compression ratios of the pre xes tend to zero, whereas the compression ratios of the pre xes of 0w tend to > 0. In Chapter 10, we concatenated the bricks obtained in Chapter 9; now, we concatenate an in nite number of bricks of Chapter 10 of increasing size (with the parameters that gave the one-bit catastrophe on nite words). As before, each chain of size l will be parsed in Θ(l) green blocks and Θ(l 3/2 ) red blocks. To guarantee that the compression ratio always remains close to zero in w and never goes close to zero in 0w, the size of the bricks mentioned above will be adjusted to grow neither too fast nor too slow, so that the compression size will be locally the same everywhere. We will need an in nite sequence of families (F i ) i≥0 of words similar to that of Chapter 10: thus we will need in nite sequences of parameters to specify them.

• For i ≥ 0, the size of words in F i will be l i = l 0 .2 i , for l 0 su ciently large.

• Let p i = √ l i /(9γ) -2 log l i , where γ ≥ 10 is a constant. For i > 0, the number of words in F i will be

• The parameter k i = (log l i )/2 will be the maximal size of words in Property P1(i) below.

• The parameter m i = γp i will be the size of words in Property P2(i) below.

We shall later show that there exists an in nite sequence F = (F i ) i≥0 matching these parameters and satisfying some desired properties (generalized versions of Properties (P1) and (P2), see below). But from an arbitrary sequence (F i ) i≥0 , let us rst de ne the "base" word from which w will be constructed.

De nition 11.1

Given a sequence F = (F i ) i≥0 where each F i is a family of words, we denote by w F the word

where q i x = max{a : x <a is a pre x of a word in ∪ j<i F j }.

For a particular sequence F = (F i ), the word w will be equal to w F with some gadgets inserted between the pre xes as in the previous chapters. The sequence F that we shall consider will be a sequence of families of random words which will satisfy the following properties (Lemma 11.2 below shows that these properties are true with high probability).

P1(i): For all x ∈ F i , for all words u of size at most k

'): For all i ≥ 0, P1(i).

P2(i): Any factor u of size m i appears in at most one word of ∪ j≤i F j , and within that word at only one position.

(P2'): For all i ≥ 0, P2(i).

Again, (P2') guarantees a kind of "independence" of the families F 0 , F 1 , . . . , whereas (P1') is a de Bruijn-style "local" property on each word of each family F i .

Our rst lemma shows that there exists a sequence F = (F i ) i≥0 satisfying (P1') and (P2').

Lemma 11.2

For every i ≥ 0, let F i be a set of 2 p i -2 p i-1 words of size l i (and 2 p 0 words of size l 0 for F 0 ) taken uniformly and independently at random. Then the probability that F satis es Properties (P1') and (P2') is non-zero.

Proof. Let us show that the probability that F satis es (P1') is > 1/2, and similarly for (P2'). We only show it for (P2'), as an analogous (and easier) proof gives the result for (P1') as well.

By Lemma 10.3, the probability that F does not satisfy P2(i) is less than 2/l i = 2 1-i /l 0 . Thus, by union bound, the probability that all P2(i) are satis ed is larger than

as soon as 2(q -1) ≥ q/2, that is, q ≥ 2. (We shall take care of the case q = 1 below.) On the other hand, when all possible gadgets are added, each chain has a size at most 5l

In particular, log G ≤ log n ≤ 2 log |F j-1 |.

Let us now bound the number of green blocks. A chain coming from F i , with gadgets, is parsed in at most 3l i /2 blocks. Hence

We can now bound the compression ratio of w <n :

Finally, for the case q = 1, looking back at the inequalities above we have: n + o(n) ≥ |F j-1 |l 2 j-1 /2 and G ≤ 3l j-1 (|F j-1 | + 1), thus ρ(w <n ) again tends to zero.

Finally we turn to the lower bound on the compression ratio of 0w. Lemma 11.4 ρ inf (0w) ≥ 2/(1215γ).

Proof. De ne j and q as in the proof of Lemma 11. Let us now give a lower bound on R. Suppose for now that q ≥ 4, so that 2 √ 2(q -1) ≥ 2q. The proof of Theorem 7.10 in Chapter 10 shows that each chain coming from a family F i is parsed in at least l In the case q ≤ 3, we have q << |F j-1 | and the same bound holds. We conclude this thesis by giving some perspectives and open questions for future works, that are linked to what has been presented throughout the manuscript.

Part one: non commutative arithmetic circuits • Lower bounds. We have shown some lower bounds using the partition method-that is, by considering rank[f, Π] for some polynomial f and partition Π. This method alone is not su cient to prove any superpolynomial bound for general non commutative circuits, as there is a polynomial computable by small circuit that is full rank with respect to any partition (see Theorem 1.17). However, the Hankel method-that is, based on the rank of Hankel matrices-does not su er from such a barrier yet. One can-by using similar ideas to the ones in Chapter 6-show that the rank of the Hankel matrix captures exactly the complexity of general non associative circuits computing a non associative polynomial. Therefore, proving a lower bound on the rank of the Hankel matrix on any non associative polynomial P that is equal to a xed non commutative polynomial P when viewed in the