Dominik Scheder
email: dscheder@inf.ethz.ch

UNSATISFIABLE LINEAR CNF FORMULAS ARE LARGE AND COMPLEX

Keywords: 1998 ACM Subject Classification: Computational and structural complexity Extremal Combinatorics, Proof Complexity, Probabilistic Method

We call a CNF formula linear if any two clauses have at most one variable in common. We show that there exist unsatisfiable linear k-CNF formulas with at most 4k 2 4 k clauses, and on the other hand, any linear k-CNF formula with at most 4 k 8e 2 k 2 clauses is satisfiable. The upper bound uses probabilistic means, and we have no explicit construction coming even close to it. One reason for this is that unsatisfiable linear formulas exhibit a more complex structure than general (non-linear) formulas: First, any treelike resolution refutation of any unsatisfiable linear k-CNF formula has size at least 2

. This implies that small unsatisfiable linear k-CNF formulas are hard instances for Davis-Putnam style splitting algorithms. Second, if we require that the formula F have a strict resolution tree, i.e. every clause of F is used only once in the resolution tree, then we need at least a a . . . a clauses, where a ≈ 2 and the height of this tower is roughly k.

Introduction

How can CNF formulas become unsatisfiable? Roughly speaking, there are two ways: Either some constraint (clause) is itself impossible to satisfy -the empty clause; or, every clause can be satisfied individually, but one cannot satisfy all of them simultaneously. In the latter case, the clauses have to somehow overlap. How much? For example, take k boolean variables x 1 , . . . , x k . The conjunction of all 2 k possible clauses of size k is the complete k-CNF formula and denote by K k . It is unsatisfiable, and as small as possible: Any k-CNF formula with less than 2 k clauses is satisfiable. Clearly, the clauses of K k overlap a lot. What if we require that any two distinct clauses share at most one variable? We call such a formula linear. There are unsatisfiable linear k-CNF formulas, but they are significantly larger and have a much more complex structure than K k .

A CNF formula is a conjunction (AND) of clauses, and a clause is a disjunction (OR) of literals. A literal is either a boolean variable x or its negation x. We require that a clause does not contain the same literal twice, and does not contain complementary literals, i.e., both x and x. To simplify notation, we also regard formulas as sets of clauses and clauses as sets of literals. A clause with k literals is a k-clause, and a k-CNF formula is a CNF formula consisting of k-clauses. For a clause C, we denote by vbl(C) set of variables x with x ∈ C or x ∈ C. Consequently, a CNF formula F is linear if |vbl(C) ∩ vbl(D)| ≤ 1 for any two distinct clauses C, D ∈ F . As a relaxation of this notion, we call F weakly linear if |C ∩ D| ≤ 1 for any distinct C, D ∈ F .

Example. The formula (x 1 ∨ x 2 ) ∧ (x 2 ∨ x 3 ) ∧ (x 3 ∨ x 4 ) ∧ (x 4 ∨ x1 ) is linear, whereas (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 2 ) ∧ (x 2 ∨ x 3 ) is weakly linear, but not linear, and finally (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 2 ∨ x3 ) is not weakly linear (and not linear, either).

It is not very difficult to construct an unsatisfiable linear 2-CNF formula, but significantly more effort is needed for a 3-CNF formula. It is not obvious whether unsatisfiable linear k-CNF formulas exist for every k. These questions have been asked first by Porschen, Speckenmeyer and Randerath [START_REF] Porschen | On linear CNF formulas[END_REF], who also proved that for any k ≥ 3, if an unsatisfiable linear k-CNF formula exists, then deciding satisfiability of linear k-CNF formulas is NPcomplete. Later, Porschen, Speckenmeyer and Zhao [START_REF] Porschen | Linear CNF formulas and satisfiability[END_REF] and, independently, myself [START_REF] Scheder | Unsatisfiable linear k-CNFs exist, for every k[END_REF] gave a construction of unsatisfiable linear k-CNF formulas, for every k ∈ N 0 : Theorem 1.1 ( [START_REF] Porschen | Linear CNF formulas and satisfiability[END_REF], [START_REF] Scheder | Unsatisfiable linear k-CNFs exist, for every k[END_REF]). For every k ≥ 0, there exists an unsatisfiable linear k-CNF formula F k , with F 0 containing one clause and

F k+1 containing |F k |2 |F k | clauses.
The |F k | are extremely large. Here, we will give an almost optimal construction. Theorem 1.2. All weakly linear k-CNF formulas with at most It is a common phenomenon in extremal combinatorics that by probabilistic means one can show that a certain object exists (in our case, a "small" linear unsatisfiable k-CNF formula), but one cannot explicitly construct it. We have no explicit construction avoiding the tower-like growth in Theorem 1.1. We give some arguments why this is so, and show that small linear unsatisfiable k-CNF formulas have a more complex structure than their non-linear relatives. To do so, we speak about resolution. It is well-known that a CNF formula F is unsatisfiable if and only if it has a resolution tree (which can be exponentially large in |F |). Proving lower bounds on the size of resolution trees (and general resolution proofs, which we will not introduce here) has been and still is an area of intensive research. See for example Ben-Sasson and Wigderson [START_REF] Ben-Sasson | Short proofs are narrow-resolution made simple[END_REF]. A large ratio between the size of F and the size of a smallest resolution tree is an indication that F has a complex structure. For example, it is well-known that the running time of so-called Davis-Putnam procedures on a formula F is lower bounded by the size of the smallest resolution tree of F (actually those procedures were introduces by Davis, Logeman and Loveland [START_REF] Davis | A machine program for theorem-proving[END_REF]). Such a procedure tries to find a satisfying assignment for a formula F (or to prove that none exists) by choosing a variable x, and then recursing on the formulas F [x →0] and F [x →1] , obtained from F by fixing the value of x to 0 or 1, respectively. If F is unsatisfiable, the procedure implicitly constructs a resolution tree.

A CNF formula F is minimal unsatisfiable if it is unsatisfiable, and for every clause C ∈ F , F \ {C} is satisfiable. The complete k-CNF formula introduced above is minimal unsatisfiable, and has a resolution tree with 2 k leaves, one for every clause. This is as small as possible, since for a minimal unsatisfiable formula, every clause must appear as label of at least one leaf of any resolution tree. We call a resolution tree strict if no two leaves are labeled by the same clause, and a formula F strictly treelike if it has a strict resolution tree. In some sense, strictly treelike formulas are the least complex formulas possible. For example, the complete formula K k and the formulas constructed in the proof of Theorem 1.1 are strictly treelike. Theorem 1.5. For any ǫ > 0, there exists a constant c such that for any k ∈ N, any strictly treelike weakly linear k-CNF formula has at least tower 2-ǫ (kc) clauses, where tower a (n) is defined by tower a (0) = 1 and tower a (n + 1) = a tower a (n) .

Strictly treelike formulas appear in other contexts, too. Consider MU(1), the class of minimal unsatisfiable formulas whose number of variables is one less than the number of clauses. A result of Davydov, Davydova and Kleine Büning ( [START_REF] Davydov | An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF[END_REF], Theorem 12) implies that every MU(1)-formula is strictly treelike. Also, MU(1)-formulas serve as "universal patterns" for unsatisfiable formulas: Szeider [START_REF] Szeider | Homomorphisms of conjunctive normal forms[END_REF] shows that a formula F is unsatisfiable if and only if it can be obtained from a MU(1)-formula G by renaming the variables of G (in a possibly non-injective manner). It is not difficult to show that a strictly treelike linear k-CNF formula can be transformed into a linear MU(1)-formula with the same number of clauses.

Related Work

For a CNF formula F and a variable x, let d F (x) denote the degree of x, i.e. the number of clauses of F containing x or x, and let d(F ) := max x d F (x) denote the maximum degree of F . For the complete k-CNF formula K k , we have d(K k ) = 2 k . Intuitively, in an unsatisfiable k-CNF formula, some variables should occur in many clauses. In other words, the following function should be large:

f (k) := max{d every k-CNF formula F with d(F ) ≤ d is satisfiable} . (1.1)
The function f (k) has first been investigated by Tovey [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF], who showed f (k) ≥ k,using Hall's Theorem. Using the famous Lovász Local Lemma (see [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF] for the original proof, or [START_REF] Alon | The probabilistic method[END_REF] for several generalized versions), Kratochvíl, Savický and Tuza [START_REF] Kratochvíl | One more occurrence of variables makes satisfiability jump from trivial to NP-complete[END_REF] proved that f (k) ≥ 2 k ek , and that while all k-CNF formulas F with d(F ) ≤ f (k) are trivially satisfiable, deciding satisfiability of k-CNF formulas F with d(F ) ≤ f (k) + 1 is already NP-complete, for k ≥ 3. For k = 3, this is already observed in [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF]. For an upper bound, the complete k-CNF formula witnesses that f (k) ≤ 2 k -1. Savický and Sgall [START_REF] Savický | DNF tautologies with a limited number of occurrences of every variable[END_REF] showed f (k) ∈ O(k -0.26 2 k ). This was improved by Hoory and Szeider [START_REF] Hoory | A note on unsatisfiable k-CNF formulas with few occurrences per variable[END_REF]

to f (k) ∈ O ln(k)2 k k
, and recently Gebauer [START_REF] Gebauer | Disproof of the neighborhood conjecture with implications to SAT[END_REF] proved that f (k) ≤ 2 k+2 k . Thus, f (k) is known up to a constant factor. The best upper bounds on f (k) come from MU(1)-formulas. This is true for large values of k, since the formulas constructed in [START_REF] Gebauer | Disproof of the neighborhood conjecture with implications to SAT[END_REF] are MU(1), as for small values: Hoory and Szeider [START_REF] Hoory | Computing unsatisfiable k-SAT instances with few occurrences per variable[END_REF] show that the function f (k), when restricted to MU(1)-formulas, is computable (in general this is not known), and derive the currently best-known bounds on f (k) for small k (k ≤ 9). To summarize: When we try to find unsatisfiable k-CNF formulas minimizing a certain parameter, like number of clauses or maximum degree, strictly treelike formulas do an excellent job. However, if we try to construct a small unsatisfiable linear k-CNF formula, they perform horribly. Just compare our upper bound in Theorem 1.2 with the lower bound for strictly treelike formulas in Theorem 1.5

While interest in linear CNF formulas is rather young, linear hypergraphs have been studied for quite some time. A hypergraph H = (V, E) is linear if |e ∩ f | ≤ 1 for any two distinct hyperedges e, f ∈ E. A k-uniform hypergraph is a hypergraph where every hyperedge has cardinality k. We ask when a hypergraph 2-colorable, i.e., admits a 2-coloring of its vertices such that no hyperedge becomes monochromatic. Bounds on the number of edges in such a hypergraph were given by Erdős and Lovász [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF] (interestingly, this is the paper where the Local Lemma has been proven). They show that there are non-2-colorable linear k-uniform hypergraphs with ck 4 4 k hyperedges, but not with less than c ′ 4 k k 3 . The proof of the lower bound directly translates into our lower bound for linear k-CNF formulas. For the number of edges in linear k-uniform hypergraphs that are not 2-colorable, the currently best upper bound is ck 2 4 k by Kostochka and Rödl [START_REF] Kostochka | Constructions of sparse uniform hypergraphs with high chromatic number[END_REF], and the best lower bound is k -ǫ 4 k , for any ǫ > 0 and sufficiently large k, due to Kostochka and Kumbhat [START_REF] Kostochka | Coloring uniform hypergraphs with few edges[END_REF].

Existence and Upper and Lower Bounds

Proof of Theorem 1.1. Choose F 0 to be the formula consisting of only the empty clause. Suppose we have constructed F k , and want to construct F k+1 . Let m = |F k |. We create m new variables x 1 , . . . , x m , and let K m = {D 1 , D 2 , . . . , D 2 m } be the complete m-CNF formula over x 1 , . . . , x m . It is unsatisfiable, but not linear. We take 2 m variable disjoint copies of F k , denoted by

F (1) k , F (2) k , . . . , F (2 m ) k . For each 1 ≤ i ≤ 2 m , we build a linear (k + 1)-CNF formula F (i) k from F (i) k
by adding, for each 1 ≤ j ≤ m, the j th literal of D i to the j th clause of F (i) k . Note that every assignment satisfying F (i) k also satisfies D i . Finally, we set

F k+1 := 2 m i=1 F (i)
k . This is an unsatisfiable linear (k + 1)-CNF formula with m2 m clauses. Using induction, it is not difficult to see that the formulas F k are strictly treelike. We will prove the upper bound in Theorem 1.2 by giving a probabilistic construction of a comparably small unsatisfiable linear k-CNF formula. Our construction consists of two steps. First, we construct a linear k-uniform hypergraph H that is "dense" in the sense that m n is large, where m and n are the number of hyperedges and vertices, respectively, and then transform it randomly into a linear k-CNF formula F that is unsatisfiable with high probability.

Lemma 2.1. If there is a linear k-uniform hypergraph H with n vertices and m edges such that m n ≥ 2 k , then there is an unsatisfiable linear k-CNF formula with m clauses. Proof. Let H = (V, E). By viewing V as a set of variables and E as a set of clauses (each containing only positive literals), this is a (satisfiable) linear k-CNF formula. We replace each literal in each clause by its complement with probability 1 2 , independently in each clause. Let F denote the resulting (random) formula. For any fixed truth assignment α, it holds that Pr[α satisfies F ] = (1 -2 -k ) m . Hence the expected number of satisfying assignments of F is

2 n (1 -2 -k ) m < 2 n e -2 -k m = e ln(2)n-2 -k m ≤ 1 ,
where the last inequality follows from m n ≥ 2 k . Hence some formula F has fewer than one satisfying assignment, i.e., none.

How can we construct a dense linear hypergraph? We use a construction by Kuzjurin [START_REF] Kuzjurin | On the difference between asymptotically good packings and coverings[END_REF]. Our application of this construction is motivated by Kostochka and Rödl [START_REF] Kostochka | Constructions of sparse uniform hypergraphs with high chromatic number[END_REF], who use it to construct linear hypergraphs of large chromatic number. Lemma 2.2. For any prime power q and any k ∈ N, there exists a k-uniform linear hypergraph with kq vertices and q 2 edges.

With n = kq, this hypergraph has n 2 /k 2 hyperedges. This is almost optimal, since any linear k-uniform hypergraph on n vertices has at most n 2 / k 2 hyperedges: The n vertices provide us with n 2 vertex pairs. Each hyperedge occupies k 2 pairs, and because of linearity, no pair can be occupied by more than one hyperedge.

Proof. Choose the vertex set

V = V 1 ⊎ • • • ⊎ V k ,
where each V i is a disjoint copy of the finite field GF (q). The hyperedges consist of all k-tuples (x 1 , . . . , x k ) with

x i ∈ V i , 1 ≤ i ≤ k, such that        1 1 1 1 1 2 . . . i . . . k 1 4 i 2 k 2 . . . . . . . . . . . . 1 2 k-3 . . . i k-3 . . . k k-3                  x 1 x 2 . . . x i . . . x k           = 0 . (2.1)
Consider two distinct vertices x ∈ V i , y ∈ V j . How many hyperedges contain both of them? If i = j, none. If i = j, we can find out by plugging the fixed values x, y into (2.1). We obtain a (possibly non-uniform) (k -2) × (k -2) linear system with a Vandermonde matrix, which has a unique solution. In other words, x and y are in exactly one hyperedge, and the hypergraph is linear. By the same argument, there are exactly q 2 hyperedges.

Proof of the upper bound in Theorem 1.2. Choose a prime power q ∈ {k2 k , . . . , 2k2 k -1}. By Lemma 2.2, there is a linear k-uniform hypergraph H with n = qk vertices and m = q 2 hyperedges. Since m n = q k ≥ 2 k , Lemma 2.1 shows that there is an unsatisfiable linear k-CNF formula with q 2 ≤ 4k 2 4 k clauses.

Let us prove the lower bound of Theorem 1.2. For a literal u and a CNF formula F , we write occ F (u) := |{C ∈ F | u ∈ C}|, the degree of the literal u. Thus d F (x) = occ F (x) + occ F (x). We write occ(F ) = max u occ F (u). In analogy to f (k), we define f occ (k) to be the largest integer d such that any k-CNF formula F with occ(F ) ≤ d is satisfiable.

Clearly f occ (k) ≥ f (k)
2 , and thus from [START_REF] Kratochvíl | One more occurrence of variables makes satisfiability jump from trivial to NP-complete[END_REF] it follows that f occ (k) ≥ 2 k 2ek . Actually, an application of the Lopsided Lovász Local Lemma [6, 1, 14] yields f occ (k) ≥ 2 k ek -1. Lemma 2.3. Let F be a linear k-CNF formula with at most 1 + f occ (k -1) variables of degree at least 1 + f occ (k -1). Then F is satisfiable.

Proof. Transform F into a (k -1)-CNF formula F ′ by removing in every clause in F a literal of maximum degree. We claim that deg F ′ (u) ≤ f occ (k -1) for every literal u. Therefore F ′ is satisfiable, and F is, as well.

For the sake of contradiction, suppose there is a literal u such that t := occ

F ′ (u) ≥ 1 + f occ (k -1). Let C ′ i , i = 1, 2, . . . , t, be the clauses in F ′ containing u. C ′ i is obtained by removing some literal v i from some clause C i ∈ F . By construction of F ′ , occ F (v i ) ≥ occ F (u) ≥ f occ (k -1) + 1 for all 1 ≤ i ≤ t. The v i are pairwise distinct: If v i = v j , then {u, v i } ⊆ C i ∩ C j . Since F is weakly linear, this can only mean i = j. Now u, v 1 , v 2 , . . . , v t are t + 1 ≥ 2 + f occ (k -1) variables of degree at least 1 + f occ (k -1) in F, a contradiction.
We see that an unsatisfiable weakly linear k-CNF formula has at least f occ (k -1) + 2 ≥

2 k 2e(k-1) + 1 literals of degree at least f occ (k -1) + 1 ≥ 2 k 2e(k-1) . Double counting yields k|F | = u occ F (u) > 4 k 4e 2 (k-1) 2 , thus |F | > 4 k
16e 2 k 3 . By a more careful argument, we can improve this by a factor of k. We call a hypergraph (j, d)-rich if at least j vertices have degree at least d. The following lemma is due to Welzl [22].

Proof of Theorem 1.4

Let F be an unsatisfiable weakly linear k-CNF formula, and let T be a resolution tree of minimal size of F . We want to show that T has a large number of nodes. It is not difficult to see that a resolution tree of minimal size is regular, meaning that no variable is resolved more than once on a path from a leaf to the root. See Urquhart [START_REF] Urquhart | The complexity of propositional proofs[END_REF], Lemma 5.1, for a proof of this fact. We take a random walk of length ℓ in T starting at the root, in every step choosing randomly to go to one of the two children of the current node. If we arrive at a leaf, we stay there. We claim that if ℓ ≤ √ 2 k-2 , then with probability at least 1 2 , our walk does not end at a leaf. Thus, T has at least 2 ℓ-1 inner vertices at distance ℓ from the root, thus at least 2

2 k 2 -1 leaves.
As illustrated in Figure 1, we label each edge in T with an assignment. If C is the resolvent of D 1 and D 2 , x ∈ D 1 and x ∈ D 2 , we label the edge from C to D 1 by x → 0 and from C to D 2 by x → 1. Each path from the root to a node gives a partial assignment α. If that node is labeled with clause C, then C evaluates to false under α. In our random walk, let α i denote the partial assignment associated with the first i steps. α 0 is the empty assignment, and α i assigns exactly i variables (if we are not yet at a leaf). We set F i := F [α i ] , i.e., the formula obtained from F by fixing the variables according to the partial assignment α i . For a formula G, we define the weight w(G) to be

w(G) := C∈G,|C|≤k-2 2 k-|C| . (3.1)
Since F is a k-CNF formula, w(F ) = 0. If some formula G contains the empty clause, then w(G) ≥ 2 k . In our random walk, w(F i ) is a random variable.

Lemma 3.1. E[w(F i+1 )] ≤ E[w(F i )] + 4i. Since w(F 0 ) = 0, this implies E[w(F ℓ )] ≤ 4 ℓ 2 ≤ 2ℓ 2 .
If our random walk ends at a leaf, then F ℓ contains the empty clause, thus w(F ℓ ) ≥ 2 k . Therefore 2ℓ 2 ≥ E[w(F ℓ )] ≥ 2 k Pr[the random walk ends at a leaf]. We conclude that at least half of all paths of length ℓ * = √ 2 k-2 starting at the root do not end at a leaf. Thus T has at least 2 ℓ * -1 internal nodes at distance ℓ * from the root, and thus at least 2 ℓ * leaves, which proves the theorem. It remains to prove the lemma.

Proof of the lemma. For a formula G and a variable x, let d k-1 (x, G) denote the number of (k -1)-clauses containing x or x. Since F 0 is a k-CNF formula, d k-1 (x, F 0 ) = 0, for all variables x. We claim that d k-1 (x, F i+1 ) ≤ d k-1 (x, F i ) + 2 for every variable x. To see this, note that in step i, some variable y is set to b ∈ {0, 1}, say to 0. At most one k-clause of F i contains y and x, and at most one contains y and x, since F i is weakly linear, thus

d k-1 (x, F i+1 ) ≤ d k-1 (x, F i ) + 2. It follows immediately that d k-1 (x, F i ) ≤ 2i.
Consider w(F i ), which was in (3.1). F i+1 is obtained from F i by setting some variable y randomly to 0 or 1.

Proof of Theorem 1.5

Let F be a strictly treelike weakly linear k-CNF formula F , and let T be a strict resolution tree of F . Letters a, b, c denote nodes of T , and u, v, w denote literals. Every node a of T is labeled with a clause C a . We define a graph G a with vertex set C a , connecting u, v ∈ C a if u, v ∈ D for some clause D ∈ F that occurs as a label of a leaf in the subtree of a. Since T is a strict resolution tree and F is weakly linear, every edge in G a comes from a unique leaf of T . Resolution now has a simple interpretation as a "calculus on graphs", see Figure 2. If a is a leaf, then G a = K k . Since the root of a resolution tree is labeled with the empty clause, we have

G root = (∅, ∅), For a graph G, let κ i (G) denote the minimum size of a set U ⊆ V (G) such that G -U contains no i-clique. Here, G -U is the subgraph of G induced by V (G) \ U . Thus, κ 1 (G) = |V (G)|, and κ 2 (G) is the size of a minimum vertex cover of G. For the complete graph K k , κ i (K k ) = k -i + 1.
We write κ i (a) := κ i (G a ). The tuple (κ 1 (a), . . . , κ k (a)) can be viewed as the complexity measure for a. We observe that if a is a leaf, then κ i (a) = ki + 1, and κ i (root) = 0, for all 1 ≤ i ≤ k. If a is an ancestor of b in T , let dist(a, b) denote the number of edges in the T -path from a to b. Since one resolution step deletes one literal (and may add several), the next proposition is immediate: let a be i-extendable, for 1 ≤ i < ℓ.

Proposition 4.1. If b is a descendant of a in T , then κ i (b) ≤ κ i (a) + dist(a, b).
Claim: Let b be a descendant of a with dist(a, b) ≤ θ i . If b is (i + 1)-extendable, then there is an (i + 1)-extendable antichain A of b at distance at most θ i+1 of size 2 ν i+1 θ i+1 -1 .

Proof of the claim. By applying the induction hypothesis of the lemma to b, there is an (i + 2)-extendable antichain A of b at distance at most θ i+1 of size 2 ν i+1 θ i+1 . Let A good := {c ∈ A | κ i+1 (c) ≤ θ i+1 }. This is an (i + 1)-extendable antichain. If A good contains at least half of A, we are done. See Figure 3 for an illustration. Write A bad := A\A good and suppose for the sake of contradiction that A bad > 2 ν i+1 θ i+1 -1 . Consider any c ∈ A bad . On the path from c to b, in each step some literal gets removed (and others may be added). Let P denote the set of the removed literals. ≥ 2θ i + 1 edge-disjoint (i + 1)-cliques. Two such cliques overlap in no vertex besides v, hence G b contains at least 2θ i + 1 vertex-disjoint i-cliques, thus κ i (b) ≥ 2θ i + 1. By Proposition 4.1, κ i (a) ≥ κ i (b)dist(a, b) ≥ θ i + 1. This contradicts the assumption of Lemma 4.4 that a is i-extendable. We conclude that |A bad | ≤ 1 2 |A|, which proves the claim. Let us continue with the proof of the lemma. If A is an (i + 1)-extendable antichain of a at distance d ≤ θ i , then by the claim for each vertex b ∈ A there exists an (i + 1)extendable antichain of b at distance at most θ i+1 , of size 2 ν i+1 θ i+1 -1 . Their union is an (i + 1)-extendable antichain A ′ of a at distance at most d + θ i+1 , of size |A|2 ν i+1 θ i+1 -1 . Hence we can "inflate" A to A ′ , as long as d ≤ θ i . Starting with the (i + 1)-extendable antichain {a} and inflate it θ i θ i+1 times, and obtain a final (i + 1)-extendable antichain of a at distance at most θ i of size at least 2 ν i+1 θ i+1 -1

j θ i θ i+1 k = 2 ν i θ i .
Applying Lemma 4.4 to the root of T , which is 1-extendable, we obtain an antichain A of size 2 ν 1 θ 1 nodes. Since T has at least |A| leaves, this proves the theorem.

Open Problems

Let f LIN (k) be the largest integer d such that any linear k-CNF formula F with d(F ) ≤ d is satisfiable. Clearly f LIN (k) ≥ f (k), and from the proof of the upper bound in Theorem 1.2 it follows that f LIN (k) ≤ 2k2 k . Is there a significant gap between f (k) and f LIN (k)? It is not difficult to show that f (2) = f LIN (2) = 2, but we do not know the value of f LIN (k) for any k ≥ 3. How do unsatisfiable linear k-CNF formulas look like? Can one find an explicit construction of an unsatisfiable linear k-CNF formula whose size is singly exponential in k?

We suspect one has to come up with some algebraic construction. What is the resolution complexity of linear k-CNF formulas? Tree resolution complexity is doubly exponential in k. We suspect the same to be true for general resolution.

4 k 8e 2

 42 (k-1) 2 clauses are satisfiable. There exists an unsatisfiable linear k-CNF formula with 4k 2 4 k clauses.

1. 1 .

 1 Resolution Trees If C and D are clauses and there is unique literal u such that u ∈ C and ū ∈ D, then (C \ {u}) ∪ (D \ {ū}) is called the resolvent of C and D. It is easy to check that every assignment satisfying C and D also satisfies the resolvent. Definition 1.3. A resolution tree for a CNF formula F is a tree T whose vertices are labeled with clauses, such that • each leaf of T is labeled with a clause of F , • the root of T is labeled with the empty clause, • if vertex a has children b and c, and these are labeled with clauses C a , C b , C c , respectively, then C a is the resolvent of C b and C c .

Theorem 1 . 4 . 2 k 2 - 1

 14221 Let k ≥ 2. Every resolution tree of an unsatisfiable weakly linear k-CNF formula has at least 2 leaves.

Lemma 2 . 4 .Figure 1 :Theorem 2 . 5 .2 b+2 e 2 k 2+ 1 b

 241251 Figure1: A resolution tree, with its edges labeled in the obvious way. Every clause is unsatisfied when applying the assignments on the path to the root.

  Consider a clause C. How does its contribution to (3.1) change when setting y? If (i) y ∈ vbl(C) or |C| = k, it does not change. If (ii) y ∈ vbl(C) and |C| ≤ k-2, then with probability 1 2 each, its contribution to (3.1) doubles or vanishes. Hence on expectation, it does not change. If (iii) y ∈ vbl(C) and |C| = k -1, then C contributes nothing to w(F i ), and with probability 1 2 , it contributes 4 to w(F i+1 ). On expectation, its contribution to (3.1) increases by 2. Case (iii) applies to at most d k-1 (y, F i ) ≤ 2i clauses. Hence E[w(F i+1 )] ≤ E[w(F i )] + 4i.

Figure 3 :

 3 Figure 3: Illustration of the claim in the proof of Lemma 4.4. If node a is i-extendable, and b is a close (i + 1)-extendable descendant of a, then b itself has many close descendants A, at least half of which are (i + 1)-extendable themselves.

  Then C c \ {P } ⊆ C b , and G c -P is a subgraph of G b . Node c is not (i + 1)-extendable, thus κ i+1 (c) ≥ θ i+1 + 1. Since |P | = dist(b, c) ≤ θ i+1 , the graph G c -P contains at least one (i+1)-clique, which is also contained in G b . This holds for every c ∈ A bad , and by weak linearity, G b contains at least |A bad | edge disjoint (i + 1)-cliques. Since b is(i + 1)-extendable, there exists a set U ⊆ V (G v ), |U | = κ i+1 (b) such that G b -U contains no (i + 1)-clique. Each of the |A bad | edge-disjoint (i + 1)-cliques G b contains some vertex of U , thus some vertex v ∈ U is contained in at least |A bad | |U | ≥ 2 ν i+1 θ i+1 -1 θ i+1

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgments

My thanks go to Emo Welzl, Robin Moser, Heidi Gebauer, Andreas Razen and Philipp Zumstein for very helpful and fruitful discussions.

Research is supported by the SNF Grant 200021-118001/1.

At this point we want to give an intuition of the proofs that follow. Our goal is to show that if the values κ i (a) are small for some node a in the tree, then the subtree of a is big. The proof goes roughly as follows: If the subtree of a is small, then there are many descendants b of a that are not too far from a and have even smaller subtrees. By induction, we will be able to show that κ i+1 (b) is fairly large. Thus, on the path from b to a, not all (i+ 1)-cliques are destroyed, and every such descendant b of a provides G a with an (i + 1)-clique. These cliques need not be vertex-disjoint, but they are edge-disjoint. This implies that G a has many vertex-disjoint i-cliques, a contradiction to κ i (a) being small. To make this intuition precise, we have to define what small and big actually means in this context: We fix a value 1 ≤ ℓ ≤ k and define ν i and θ i for 1 ≤ i ≤ ℓ as follows: θ ℓ := k-ℓ+1 2 -1 and ν ℓ := 1, and for 1 ≤ i < ℓ, we inductively define

should not worry about these ugly expressions too much, they are only chosen that way to make the induction go through. For the right value of ℓ, one checks that θ 1 is a tower function in k. More precisely, for any ǫ > 0, there exists a c ∈ N such that when choosing ℓ = kc, then θ 1 ≥ tower 2-ǫ (kc). The following theorem is a more precise version of Theorem 1.5. Theorem 4.2. Let F be a strictly treelike linear k-CNF formula. Then F has at least 2 ν 1 θ 1 clauses.

Proof. A node a in T is i-extendable if κ j (a) ≤ θ j for each i ≤ j ≤ ℓ. We observe that if a is i-extendable, it is also (i + 1)-extendable. For i = ℓ + 1, the condition is void, so every node is (ℓ + 1)-extendable. Also, the root is 1-extendable, since κ 1 (root) = 0. Definition 4.3. A set A of descendants of a in T such that (i) no vertex in A is an ancestor of any other vertex in A and (ii) dist(a, b) ≤ d for all b ∈ A is called an antichain of a at distance at most d. If furthermore every b ∈ A is i-extendable, we call A an i-extendable antichain.

Lemma 4.4. Let 1 ≤ i ≤ ℓ, and let a be a node in T . If a is i-extendable, then there is an (i + 1)-extendable antichain A of a at distance at most θ i such that |A| = 2 ν i θ i .

Proof. We use induction on ℓi. For the base case i = ℓ, we have κ ℓ (a) ≤ θ ℓ , as a is ℓ-extendable. Since each leaf b of T has κ ℓ (b) = kℓ + 1 ≥ 2θ ℓ + 2, Proposition 4.1 tells us that every leaf in the subtree of a has distance at least θ ℓ + 2 from a. Since T is a complete binary tree, there are 2 θ ℓ descendants of a at distance exactly θ ℓ from a. This is the desired antichain A of a. Since every node is (ℓ + 1)-extendable, the base case holds. For the step,


¸ois Laudenbach

A note on the Chas-Sullivan product

Keywords: 2000 Mathematics Subject Classification. 55N10, 57R19, 57R45 Free loop space, intersection product, Chas-Sullivan product

We give a finite dimensional approach to the Chas-Sullivan product on the free loop space of a manifold, orientable or not, compact or not.

Introduction

Let M be an n-dimensional manifold with empty boundary; it is not required to be either compact or orientable. Denote LM = C ∞ (S 1 , M) be its free loop space. In a famous paper [START_REF] Chas | String Topology[END_REF], in the case when M is an orientable and closed manifold, M. Chas and D. Sullivan constructed a natural graded algebra structure on the homology H * (LM; Z), more precisely a product H i (LM; Z) ⊗ H j (LM; Z) → H i+j-n (LM; Z), in the same intersection spirit as the usual intersection product on H * (M; Z). But their ideas remained not completely accomplished. A different approach has been considered by R. Cohen and J. Jones in [START_REF] Cohen | A homotopy theoretic realization of string topology[END_REF]. According to their abstract, they describe "a realization of the Chas-Sullivan product in terms of a ring spectrum structure on the Thom spectrum of a certain virtual bundle over the loop space", a difficult technique indeed. Recently in [START_REF] Félix | String topology on Gorenstein spaces[END_REF], Y. Félix and J.-C. Thomas have put String Topology into a broad homotopy theoretical setting; they prove that the operations in string topology are preserved by homotopy equivalence, at least in the 1connected case. On the contrary, in the present note we propose a finite dimensional approach, very close to the spirit of [START_REF] Chas | String Topology[END_REF], based on transversality arguments. We also treat the case of a non-orientable manifold using local coefficients instead of Z.

We do not think of LM as a topological space but as a simplicial set (except in section 4). A k-simplex in LM is a smooth map Σ : ∆ k × S 1 → M where ∆ k is the standard k-simplex. Let 0 be the base point of S 1 = R/Z. The evaluation map ev 0 : LM → M is simplicial: ev 0 (Σ) = σ where σ : ∆ k → M is the k-simplex of M defined by σ(t) = Σ(t, 0).

It is easy to form a chain complex based on the simplices of LM and a bi-complex based on bi-simplices (pairs of simplices). In order to take into account the non-orientabiliy, we limit ourselves to small simplices and bi-simplices (see 2.1). To define an intersection product we consider transverse bi-simplexes. By Thom's transversality theorem, they generate a sub-bicomplex which has the same homology as LM × LM. As we shall see, smallness (resp. transversality property) will only refer to the image of simplices (resp. bi-simplices) through the evaluation map. Let us introduce the sub-bicomplex LM × M LM of LM × LM made of composable loops, that is, pairs of loops having a common origin. Performing the composition yields a well defined map in homology LM × M M → LM The intersection product will be not far from being defined on the chain level: the intersection of two transverse cycles in LM will produce a "singular" smooth manifold W in LM × M LM, hence in LM after composing, which becomes a simplicial cycle once W is triangulated. According to Whitehead [START_REF] Whitehead | On C 1 -complexes[END_REF], such a triangulation is unique up to subdivision and isotopy. Therefore the product is well defined at the homology level.

In last section it is shown that this definition of the free loop product is not less efficient than the "infinite dimensional" one when calculations are performed in concrete geometric situations. Results due to different authors (M. Goresky, N. Hingston in [START_REF] Goresky | Loop Products and Closed Geodesics[END_REF], D. Chataur, J.-F. Le Borgne in [START_REF] Chataur | Homology of spaces of regular loops in the sphere[END_REF]) are rewritten in this setting.

Acknowledgments. I had the chance to hear Dennis Sullivan lecturing on this subject on the occasion of his Doctorat Honoris Causa at École normale supérieure (Lyon) in Dec. 2001. Later on, I had fruitful conversations with David Chataur and Hossein Abbaspour who gave me more details. I feel indebted to all of them. I am also grateful to Jean-Claude Thomas for comments on a preliminary version of this note and to Antoine Touzé who prevented me from making a mistake in spectral sequences.

Simplices and bi-simplices at the manifold level

In this section we give a geometrical approach to the intersection product in the homology of M. The important point is that it is done in a way so that the intersection product lifts immediatly to LM. This requires an appeal to Thom's transversality with constraints which is more powerful than the usual transversality, as it is usually done (see J.E. McClure [START_REF] Mcclure | On the chain-level intersection pairing for P L manifolds[END_REF] in the P L case or E. Castillo, R. Diaz [START_REF] Castillo | Homology and manifolds with corners[END_REF] in the smooth case).

The manifold M under consideration is equipped with an atlas

A of charts. A small k-simplex is a smooth map σ : ∆ k → M
whose image is contained in a chart from A. For each simplex σ some particular chart U(σ) ∈ A is chosen once for all containing its image. A small k-chain is a linear combination ξ = n i σ i with coefficient n i ∈ Z of finitely many small simplices σ i . The oriention twisted boundary is defined by the following formula:

∂σ = k i=0 ε(-1) i F i σ,
where F i σ is the i th face of σ and ε is the sign of the Jacobian of change of coordinates from U(F i σ) to U(σ) calculated at any point of the image of F i σ. The small chains with this boundary form a chain complex whose homology is H * (M; Z or ), the homology with integral coefficients twisted by the orientation.

In the sequel, homotopy means smooth homotopy. Given a k-simplex σ, a homotopy σ t : ∆ k → M, t ∈ [0, 1], with σ 0 = σ induces a homotopy (F σ) t of each face F σ. So the following definition makes sense. Definition 2.2. Given a chain ξ = n i σ i , a boundary preserving homotopy of ξ is a one parameter family ξ t , t ∈ [0, 1], ξ t = n i σ t i , where t → σ t i is a homotopy of σ i into M (σ 0 i = σ i ), and such that, if σ i and σ j have a common face at time t = 0 the corresponding simplices σ t i and σ t j still have a common face at any time. For instance, if ξ is a cycle then ξ t is a cycle for every t ∈ [0, 1]. When we consider such a homotopy of small chain, we shall limit ourselves to the case when the homotopy is small, that is: each summand σ t i takes place in U(σ i ). The following homotopy extension lemma is easy to prove. Lemma 2.3. Let τ be any simplex which is a face of one of the summands of ξ. Any (small) homotopy of τ extends as a (small) boundary preserving homotopy of ξ. The same statement holds for a family of homotopies with an extension depending continuously on the parameter.

Definition 2.4. A (p, q)-bi-simplex of M × M is a pair (u, v)
where u is a p-simplex and v is a q-simplex of M. It is said to be small when both factors are small simplices of M.

It is convenient to denote it u×v like the map u×v : ∆ p ×∆ q → M ×M, (x, y) → (u(x), v(y)). The (small) bi-simplices generate a bi-complex C * * (M × M) whose elements are bi-chains, with two boundary operators twisted by the orientation,

∂ 1 (u × v) = (∂u) × v, ∂ 2 (u × v) = u × ∂v,
and a total boundary operator

D(u × v) = ∂u × v + (-1) p u × ∂v.
Definition 2.5. A (small) bi-simplex u × v is said to be transverse when the map u × v is transverse to the diagonal ∆ M and when all its faces (they are bi-simplices) are also transverse to the diagonal.

In the sequel, all transverse bi-simplices will be small, without saying it. The advantage is that W = (u × v) -1 (∆ M ) is a proper orientable submanifold of codimension n (with corners) in ∆ p × ∆ q . Moreover, if we use the charts U(u) and U(v) whose product contains the image of u × v, W receives a canonical orientation.

Notice that, when u × v is a transverse bi-simplex, a small homotopy of one of the factors keeps them transverse. The transverse bi-simplices generate a sub-bicomplex C tr * * (M × M) of C * * (M × M). A bi-chain is said to be transverse when each of its bi-simplices is transverse. It is said to be a product bi-chain if it has the form ξ × η where both factors are chains in M. Lemma 2.6. Let ξ × η be a product bi-chain. There exists an arbitrarily C ∞ -small boundary preserving homotopy ξ t of ξ 0 = ξ such that ξ 1 × η is transverse. Moreover, when ∂ξ × η is transverse, the homotopy can be chosen stationary on ∂ξ × η. The same statement holds for the second factor.

Considering the composition of loops we have in mind, it is very important to make this approximation among the bi-chains.

Proof. We first consider the case when ξ × η = u × v is a bi-simplex. The conclusion follows from Thom's transversality theorem, not in its elementary form but in the form known as the transversality with constraint ( [START_REF] Thom | Les singularités des applications différentiables[END_REF]). Indeed, only the first factor is moved for guaranteeing that bi-simplices remain bi-simplices during the deformation. We argue as follows. Let S be a small n-ball in the vector space containing the chart U(u), so small that, for any s ∈ S, u s := u + s is still contained in U(u). We introduce the family (u s × v) parametrized by S. It is transverse to ∆ M as well as its restriction to any face of ∆ p × ∆ q . Therefore, according to Sard's lemma (used à la Thom), for almost every s ∈ S, u s × v is a transverse bi-simplex.

For the general case, it is useful to observe that, in the above argument, the space S of parameters can be chosen arbitrarily small. When considering a product bi-chain ξ × η, its k-skeleton is the collection of all the k-faces of the bi-simplices appearing in ξ × η. Arguing recursively, we may assume that all bi-simplices in the k-skeleton are transverse. Let (u × v) be a (k + 1)-bi-simplex, which we endow with a family S of translations in U(u). According to lemma 2.3, the translation by any s ∈ S extends as a boundary preserving homotopy of ξ (ending at ξ s ) and it can be chosen small enough so that each bi-simplex of the k-skeleton remains transverse. Therefore, for almost every s ∈ S, ξ s is transverse along its k-skeleton and u × v. Repeating this process, we successively make all (k + 1)-bi-simplices transverse.

For the relative version, we notice that, if F u is a face of u and F u × v is transverse, then u × v is automatically transverse to ∆ M on a neighborhood of the domain of F u × v. In that case we can moderate the translation by s so that it becomes stationary along F u × v. The general relative version follows easily.

⋄

Let [ξ] and [η] be two classes of respective degrees p and q in H * (M; Z or ). According to lemma 2.6, they can be represented by small cycles so that the bi-cycle ξ × η is transverse. This bi-cycle is unique up to transverse homology; more precisely we claim the following uniqueness lemma: Lemma 2.7. Let ξ × η and ξ ′ × η ′ be two transverse bi-cycles in the same bi-homology class

([ξ] = [ξ ′ ] and [η] = [η ′ ]). There exists a transverse bi-chain Ω whose total boundary is DΩ = ξ ′ × η ′ -ξ × η.
Proof. There exists a cycle ξ ′′ , homotopic to ξ, such that ξ ′′ × η and ξ ′′ × η ′ are both transverse (ξ × η is already transverse and this property is preserved by approximation of ξ; according to lemma 2.6, such an approximation exists making ξ ′′ × η ′ transverse). If ω is a (p + 1)-chain such that ∂ω = ξ -ξ ′′ , there is a boundary preserving homotopy ω t , t ∈ [0, 1], of ω relative to its boundary so that ω 1 × η is transverse. By the same argument there is a (p + 1)-chain ω ′ with ∂ω ′ = η -η ′ , such that ξ ′′ × ω ′ is transverse. Eventually, there exists ω ′′ with ∂ω ′′ = ξ ′ -ξ ′′ such that ω ′′ × η ′ is transverse. By concatening the three transverse homologies ω 1 × η, ξ ′′ × ω ′ and ω ′′ × η ′ we get a transverse homology joining both given bi-cycles. ⋄

Intersection of cycles.

We are now ready for defining the intersection of cycles. To begin with, we consider a transverse product bi-chain ξ ×η of degree (p, q), which reads as a sum of transverse bi-simplices

ξ × η = n ij u i × v j .
Let W ij be the preimage of ∆ M by u i × v j . As already noted, W ij is an oriented manifold with corners of codimension n.

If F (u i × v j ) is a face of the bi-simplex, F W ij denotes the corresponding face of W ij .
According to Whitehead [START_REF] Whitehead | On C 1 -complexes[END_REF], W ij can be smoothly triangulated by a P L-triangulation T ij . Moreover if some faces have been already triangulated, by using the relative version of Whitehead's theorem, T ij can be chosen so that the triangulated faces are subcomplexes. If two bi-simplices have common faces

F (u i × v j ) = F (u k × v ℓ ), then we have a canonical diffeomor- phism F W ij → F W kℓ
which we think of as an identification. The triangulations of these faces are chosen accordingly. We consider the chain of

∆ M ∼ = M ξ • η := (-1) n(n-q) n ij (u i × v j )|(W ij , T ij )
which is called the intersection product. Of course, as a chain it depends on the chosen triangulations. But, since the latter are unique up to subdividing and boundary preserving isotopy (that is, smooth isotopy of each simplex in W ij keeping the triangulation property), the ambiguity is not severe. The sign, which we call the Dold sign, will be commented upon later.

Lemma 2.9. When ξ × η is a transverse bi-cycle, the intersection product ξ • η is a cycle of degree p + q -n (with orientation twisted coefficients). If ξ × η is changed by a transverse homology (in the sense of lemma 2.7), ξ • η is changed by a homology. Finally,

[ξ] • [η] is well-defined in H p+q-n (M; Z or ).
Note that a change of triangulation of the W ij 's may be thought of as a special case of a change by a transverse homology.

Proof. As W ij is an oriented proper submanifold, (W ij , T ij ) is a relative cycle in ∆ p × ∆ q . Thus, the total boundary of (

u i × v j )|(W ij , T ij ) is (∂u i ) × v j |(W ij , T ij ) + (-1) p u i × (∂v j ) |(W ij , T ij ).
By summing on ij we get the boundary of ξ • η. As ξ and η are cycles, each hyperface in the latter sum appears twice with opposite sign. The rest of the statement is easy to prove. ⋄ Remark 2.10. In his book [START_REF] Dold | Lectures on Algebraic Topology[END_REF] (Chap. VIII, §13.3), A. Dold explains that the chosen sign makes the intersection product on homology and the (unsigned) cup-product on cohomology fit together via the Poincaré duality. Another advantage of this sign is the following. Set H * (M; Z or ) = H * +n (M; Z or ). This regraded homology endowed with the above intersection product becomes a commutative ring in the graded sense.

3. Simplices and bi-simplices at the free loop space level 3.1. We recall the evaluation map ev 0 : LM → M. A simplex Σ : ∆ k × S 1 → M is said to be small when σ = ev 0 (Σ) is so. The i th -face of Σ is is obtained by restricting Σ to

F i ∆ k × S 1 .
We have F i (ev 0 (Σ)) = ev 0 (F i Σ). The oriention twisted boundary of Σ is

∂Σ = k i=0 ε(-1) i F i Σ,
where ε is the sign of the Jacobian of change of coordinates from U(ev 0 (F i Σ)) to U(ev 0 (Σ)). The small chains with this boundary form a sub-complex of C * (LM), the singular chain complex of LM, whose homology is H * (LM; Z or ). Indeed, this sub-complex is obtained from C * (LM) by two operations which induce homotopy equivalences: subdivision and smoothing. The notion of boundary preserving homotopy is similar to the one given in 2.1.

Lemma 3.2. The evaluation map has the lifting property for boundary preserving homotopy of chains with any initial chain. Moreover, if the lifting of the homotopy is given along some faces this partial lifting can be extended to a global lifting.

Proof. It is clear for ∆ k ×S 1 ×[0, 1] retracts onto ∆ k ×S 1 ×{0}∪∆ k ×{0}×[0, 1]∪F ×S 1 ×[0, 1],
where F is any union of faces in ∆ k . ⋄

A (p, q)-bi-simplex u × v in LM × LM is a map ∆ p × ∆ q × S 1 → M × M, (x, y, θ) → u(x, θ), v(y, θ) .
It is said to be transverse when ev 0 (u), ev 0 (v) is a transverse bi-simplex of M × M. In that case, the preimage of the diagonal ∆ M yields a submanifold with corners W ⊂ ∆ p × ∆ q . For each (x, y) ∈ W , the loops u(x, -) and v(y, -) are composable, as they have common base points u(x, 0) = v(y, 0). Therefore, taking a triangulation of W and the Dold sign as in 2.8, we get a (p + q -n)-chain of composable loops, which we call the loop intersection product:

u * v := (-1) n(n-q) (u × v)|W × S 1 .
Performing the composition (in some order, u before v) yields a (p + q -n)-chain in LM, called the Chas-Sullivan product or loop product u

• CS v.
Of course, it depends on the choice of the triangulation of W . Here, we see that the product structure of u×v is very important; without it we lose the entries of the composition. Thus, when making a bi-simplex transverse, it is crucial to do it by homotopy through bi-simplices. That is the reason why we used transversality with constraints. This loop product extends linearly to the transverse bi-chains. When performing it on a product bi-cycle, the result is a cycle in LM whose homology class in H p+q-n (LM; Z or ) is welldefined. Strictly speaking the system of coefficients is ev * 0 (Z or ), which we write Z or for short and we shall do the same each time a loop space is in question. More precisely, we have the following proposition. Proof. Starting with arbitrary representatives of the given homology classes in LM, lemma 2.6 is applied: it produces an homotopy of their images by the evaluation map making them a transverse bi-cycle in M × M. The lifting homotopy property (lemma 3.2) allows one to make ξ × η a transverse bi-cycle in LM × LM. For this representative, the loop product ξ • CS η is well defined. If another representative ξ ′ × η ′ is used, one can prove that ξ ′ × η ′ and ξ × η are joined by a transverse homology, that is a transverse bi-chain in LM × LM. It is nothing but a loop version of the uniqueness lemma 2.7 and it can be deduced from the latter by applying the lifting homotopy property. As a consequence the homology class of ξ • CS η is well defined. ⋄ Remark 3.4. Of course the composition of smooth loops produces a piecewise smooth loop only. There are two ways for correcting this default. One consists of doing a smoothing (boundary preserving) homotopy. The other consists of using LM = C 0 (S 1 , M) equipped with a mixed simplicial structure: a k-simplex will be a continuous map u : ∆ k × S 1 → M whose restriction to ∆ k × 0 is smooth.

In the sequel we use the following simplified notation:

ξ • η := ξ • CS η, which is defined when the bi-cycle ξ × η is transverse, and [ξ] • [η] := [ξ • CS η]
which is well defined. Actually, there is a 1-parameter family of compositions -• s -, s ∈ [0, 1], defined as follows. Two loops u and v are said to be s-composable when u(s) = v(0); in that case the composed loop u

• s v is made of u|[0, 1 -s] * v * u|[1 -s, 1]
. When s = 0, it is the usual composition and when s = 1 we have u • 1 v = v • u (notice that if two loops are 0-composable, they are also 1-composable). Proposition 3.5. At the homology level, the loop product is commutative up to sign. Precisely, if ξ and η are respectively a p-cycle and a q-cycle of LM, then

[ξ] • [η] = (-1) (p-n)(q-n) [η] • [ξ].
The loop product is also associative.

If the regrading H * = H * +n is applied, then H * (LM, Z or ) when endowed with the loop product becomes a graded commutative and associative ring.

Proof. We assume that the bi-cycle ξ × η in LM × LM is transverse. We first prove:

[ξ] • [η] = [ξ • 1 η]. Writing ξ × η = n ij u i × v j ,
one can make a boundary preserving homotopy of ξ so that, for every ij, the following map

(x, y, s) ∈ ∆ p × ∆ q × [0, 1] → (u i (x, s), v j (y, 0), s) ∈ M × M × [0, 1] is transverse to ∆ M × [0, 1]
. This transversality yields us a (p + q -n + 1)-chain ω in LM whose boundary is ∂ω = ξ • 1 η -ξ • η. Note that the loops in ω have u(x, 0) as base points; therefore, even if the loops in u are orientation reversing no sign appears in the formula of ∂ω. Now, we are reduced to proving:

[ξ • 1 η] = (-1) (p-n)(q-n) [η] • [ξ].
On both sides of this equality the composition is the same. The only difference comes from the orientation of the manifold W ij associated to each transverse bi-simplex u i × v j appearing in ξ × η. The permutation of both factors in this bi-simplex induces a change (-1) n in the co-orientation of the diagonal ∆ M and a change (-1) pq due to the order of the factors ∆ p and ∆ q in the source. Moreover, the Dold sign (-1) n(n-q) is changed to (-1) n(n-p) . Altogether, the sign rule follows. For associativity, if three chains ξ, η, ζ (of respective degrees p, q, r) are given in LM, ξ ×η ×ζ is easily defined to be transverse. If they are cycles and if the triple is transverse, the triple composition Now the only question is how to make ξ × η × ζ transverse when the is not. It is not sufficient to move one factor, as one factor in M × M × M is not transverse to the small diagonal. It is necesary to move two factors, say ξ × η, but keeping the product structure, that is moving through product chains ξ t × η t ; it is again transversality with constraint. ⋄ Remark 3.6. Each free loop γ, θ → γ(θ), gives rise to a 1-cycle ∆(γ) of loops by rotating the source:

[ξ] • [η] • [ζ] is
∆(γ)(t)(θ) = γ(t + θ), t ∈ S 1 .
This map induces ∆ : H * (LM) → H * +1 (LM), with twisted coefficients when M is not orientable. Arguing in a similar way as in the previous proposition 3.5, one could prove the theorem of Chas-Sullivan that H * (LM), endowed with the loop product and ∆, is a Batalin-Vilkovsky algebra.

A multiplicative spectral sequence

In this section, using our definition of the loop product, we discuss multiplicative properties which have been stated and proved by Mark Goresky and Nancy Hingston in [START_REF] Goresky | Loop Products and Closed Geodesics[END_REF], §12 (up to the coefficient system). The setting is the one that R. Bott first considered in his seminal paper [START_REF] Bott | Nondegenerate critical manifolds[END_REF], where he studied the standard n-sphere, and in the next paper [START_REF] Bott | On manifolds all of whose geodesics are closed[END_REF]. We summarize his results as follows. Let M be an n-dimensional closed Riemannian manifold whose primitive geodesics are all simple loops with the same length (= 1, say). Denote by Λ the space of loops parametrized proportionally to arc length. The class of regularity is not very important here. For instance take piecewise smooth loops; a good class is the Sobolev class H 1 (S 1 , M). Let ℓ 2 : Λ → R be the squared length. Bott proved that it is a nondegenerate function (now called a Morse-Bott function) and he calculated the index of the critical points (that is, the closed geodesics). For p ∈ N, let Λ p be the subspace of loops of length ≤ p and Σ p be the space of geodesics of length p. A geodesic in Σ p is just a primitive geodesic which is traversed p times. As a manifold Σ 0 ∼ = M and, for p ≥ 1, Σ p ∼ = UM where UM stands for the unit tangent space to M. Let α p be the index of the Hessian of ℓ 2 at any point of Σ p ; obviously α 0 = 0. Bott proved the iteration formula:

α p = pα 1 + (p -1)(n -1).
Moreover he calculated (with Z 2 coefficients) the spectral sequence derived from the filtration Λ 0 ⊂ Λ 1 ⊂ . . . of Λ. We are going to consider the same spectral sequence, up to some regrading.

Definition 4.1. A spectral sequence {E r p,q , d r } r≥1 is said to be multiplicative when it is endowed with a product E r p,q ⊗ E r p ′ ,q ′ → E r p+p ′ ,q+q ′ such that: 1) d r is a derivation in the graded sense:

d r (x • y) = d r (x) • y + (-1) |x| x • d r (y),
where |.| stands for the total degree |x| = p + q when x ∈ E r p,q ; 2) the product on E r+1 * , * ∼ = H * (E r * , * , d r ) is induced by the one of E r * , * on the ideal ker d r .

Following Chataur-Le Borgne in [START_REF] Chataur | Homology of spaces of regular loops in the sphere[END_REF], we set

E 1 p,q = E 1 p,q+n = H p+q+n (Λ p , Λ p-1 ; ev * 0 (Z or )
). The differential d 1 is the connecting homomorphism in the long exact sequence of the triple (Λ p , Λ p-1 , Λ p-2 ). More generally, d r : E r * , * → E r * , * is defined by the usual algorithm associated to the filtration [START_REF] Mccleary | User's Guide to Spectral Sequences[END_REF], Chap. 2). Notice that page 0 exists in this spectral sequence, but there is no multiplicative structure on it. Proposition 4.2. The loop product endows {E r * , * } r≥1 with a multiplicative structure. Proof. Here the system of coefficients ev * 0 (Z or ) is understood. We first look at the desired properties on page r = 1. When ξ is a relative i-cycle of the pair (Λ p , Λ p-1 ), η is a relative j-cycle of the pair (Λ p ′ , Λ p ′ -1 ) and ξ × η is transverse, the loop intersection product ξ * η is a (i + j -n)-chain of composable loops. By performing the composition we get a chain c of loops of length ≤ p + p ′ since the length of the composed loop is just the sum of the lengths of the entries. The boundary of c is a cycle in

• • • Λ p-1 ⊂ Λ p ⊂ Λ p+1 ⊂ • • • Λ (see
Λ p+p ′ -1 . The class of [ξ] • [η] is well defined in H i+j-n (Λ p+p ′ , Λ p+p ′ -1
). After regrading, this product behaves well with respect to the bi-degree. It remains to check that d 1 is a derivation.

We look first at a transverse bi-simplex u × v of bi-degree (i, j) in Λ × Λ. Let W ⊂ ∆ i × ∆ j be the preimage of the diagonal ∆ M by ev 0 (u) × ev 0 (v). Its boundary is made of two parts:

-

∂ 1 W := W ∩ (∂∆ i × ∆ j ) -∂ 2 W := W ∩ (∆ i × ∂∆ j ) Each part gives rise to an (i + j + n -1)-chain in Λ which is a part of ∂(u • v).
As in the proof of lemma 2.9 the second chain is endowed with the sign (-1) i according to the formula for the total boundary which is written after definition 2.4. Taking the Dold sign into account yields:

∂(u • v) = (∂u) • v + (-1) n-i u • (∂v).
By summing such a formula over all bi-chains forming ξ × η, we get:

∂(ξ • η) = (∂ξ) • η + (-1) n-i ξ • (∂η).
After regrading, it becomes a derivation formula. When ξ and η are relative cycles as above,

d 1 ([ξ] • [η]) = (d 1 [ξ]) • [η] + (-1) |ξ| [ξ] • d 1 [η]; hence, property 1 from definition 4.1 holds for r = 1.
The product on E 2 * , * is defined by taking ξ, a relative cycle of the pair (Λ p , Λ p-2 ), and η, a relative cycle in the pair (Λ p ′ , Λ p ′ -2 ), where ξ × η is transverse. Thus the chain of composed loops is a relative cycle of the pair (Λ p+p ′ , Λ p+p ′ -2 ). It can be checked that elements in ker d 1 are represesentable by such cycles. Hence property 2 from definition 4.1 holds for r = 1.

The same argument applies for every r ≥ 1 once one remembers the definition of E r p, * associated to the filtration of Λ. The product on E r * , * is defined by taking ξ, a relative cycle of the pair (Λ p , Λ p-r ), and η, a relative cycle of the pair (Λ p ′ , λ p ′ -r ), where ξ × η is transverse. The boundary operator d r is induced by ∂ and is not affected by the value of r. After regrading d r , like d 1 , is a derivation and the product which is induced on its homology is the one of E r+1 * , * . ⋄

The Thom isomorphism.

There is a Morse-Bott version of the famous Morse lemma. It yields a "normal" form for a Morse-Bott function near a critical manifold. We are going to apply it to the function ℓ 2 : Λ → R near the critical manifold Σ p whose index is α p . If one feels uncomfortable by applying this lemma in infinite dimension, one can take a finite dimensional approximation of Λ near Σ p by considering the space of geodesics polygons (still parametrized proportionally to arc length) with Np edges of equal length, where 1/N is less than the injectivity radius. Let E - p be the vector bundle of rank α p over Σ p generated by the eigenvectors of the Hessian of ℓ 2 (with respect to some Riemannian metric on Λ) whose eigenvalues are negative; it is a sub-bundle of T Λ|Σ p . With notation borrowed from [START_REF] Goresky | Loop Products and Closed Geodesics[END_REF], let Σ - p = exp(E - p ) denote the unstable manifold of Σ p with respect to the gradient of ℓ 2 ; we are mainly interested in its germ along the critical manifold. Finally Λ - p denotes the open set of loops whose length is less than p. We have Σ - p Σ p ⊂ Λ - p (as a consequence of Taylor expansion).

The Morse-Bott lemma states:

(1) Λ - p retracts by deformation onto Λ p-1 ; (2) Λ p retracts by deformation onto Λ p-1 ∪ Σ - p .

As a consequence, the inclusions of pairs induce the following isomorphisms:

H * (Λ p , Λ p-1 ) ∼ = H * (Λ p , Λ - p ) ∼ = H * (Σ - p , Σ - p Σ p ).
Here the system of coefficients is ev * 0 (Z or ). The orientation of the fibre bundle E - p being twisted as ev * 0 (Z) is (see [START_REF] Goresky | Loop Products and Closed Geodesics[END_REF] Prop. 12.2), we are ready to apply the Thom isomorphism:

h p : H * (Σ p ; Z) ∼ = H * +αp (Σ - p , Σ - p Σ p ; ev * 0 (Z or ))
, which can also be read, when p > 0, The proof below mainly follows the same line as [START_REF] Goresky | Loop Products and Closed Geodesics[END_REF]. But it is based on the notion of loop product that we have introduced in the previous section.

Proof. There are several steps. A) One can factorize the intersection product int of H * (UM) in the following way:

H i (UM) ⊗ H j (UM) int 0 / / int H i+j-n (UM × M UM) int 1 H i+j-(2n-1) (UM) = / / H i+j-(2n-1) (UM × U M UM)
Indeed, starting with a transverse bi-cycle ξ × η we may first intersect it with the fibered product UM × M UM ⊂ UM × UM yielding an (i + j -n)-cycle ζ (this induces the morphism int 0 ), which, in turn, is transverse to the diagonal ∆ U M = UM × U M UM (this induces the morphism int 1 ). B) Since ev 0 |Σ p is a smooth submersion, the fibered product Σ p,p ′ := Σ p × M Σ p ′ is a smooth manifold. A point of it is a pair of closed geodesics of respective lengths p and p ′ which are composable as loops. In general the composed loop is not a geodesic.

Similarly, since Σ - p is tangent to E - p , a fibre bundle over Σ p , then ev 0 |Σ - p is also a submersion onto M near Σ p . Thus Σ - p,p ′ := Σ - p × M Σ - p ′ is smooth near Σ p,p ′ . The tangent space to Σ - p,p ′ along Σ p,p ′ is the restriction of E - p × E - p ′ , a vector bundle of rank α p + α p ′ . So we have a Thom isomorphism:

h p,p ′ : H * (Σ p,p ′ ) ∼ = H * +αp+α p ′ (Σ - p,p ′ , Σ - p,p ′ Σ p,p ′ ).
At the chain level of small simplices, the Thom isomorphism is generated by the following Thom "extension": take a small simplex in the base of a disk bundle (which hence is trivial over the considered small simplex) and cross it with the fiber. If ξ × η is a bi-cycle in Σ p × Σ p ′ transverse to Σ p,p ′ , then the Thom extension ξ × η is transverse to Σ - p,p ′ and its intersection with Σ - p,p ′ is the Thom extension of the intersection cycle in the base Σ p,p ′ . This proves that the Thom isomorphism carries the loop intersection product H i (Σ p )⊗H j (Σ p ′ ) → H i+j-n (Σ p,p ′ ) to the suitable relative version of the loop intersection product

H i+αp (Σ - p ) ⊗ H j+α p ′ (Σ - p ′ ) → H i+j+αp+α p ′ -n (Σ - p,p ′ ).
Note that, after identification, the first morphism is nothing but int 0 from A). C) We observe that Σ p+p ′ lifts (by a section of the composition map) as a submanifold of codimension n -1 in Σ p,p ′ . Indeed, any smooth geodesic of length p + p ′ splits uniquely into two geodesics of respective lengths p and p ′ . Conversely, (γ, γ ′ ) ∈ Σ p,p ′ belongs to this lifting of Σ p+p ′ if and only if the initial velocities γ(0) and γ′ (0) are positively proportional, which is a condition of codimension n -1. Thus, the composition is a map of pairs:

comp : (Σ - p,p ′ , Σ - p,p ′ Σ p+p ′ ) → (Λ p+p ′ , Λ p+p ′ Σ p+p ′ ).
The normal bundle to Σ p+p ′ in Σ - p,p ′ , denoted by ν, is the direct sum E - p ⊕ E - p ′ ⊕ ν p,p ′ where ν p,p ′ denotes the normal bundle to Σ p+p ′ in Σ p,p ′ . The rank of ν is α p + α p ′ + n -1. According to Bott's iteration formula, it equals α p+p ′ , which is the rank of

E - p+p ′ . If ξ is a relative cycle in (Σ - p,p ′ , Σ - p,p ′ Σ p,p ′ ) transverse to Σ p+p ′ , its trace in the pair (Σ - p,p ′ , Σ - p,p ′ Σ p+p ′ )
is the Thom extension of its intersection with Σ p+p ′ . In other words we have the following commutative diagram:

H k (Σ p,p ′ ) int 1 / / H k-n+1 (Σ p+p ′ ) H k+αp+α p ′ (Σ - p,p ′ , Σ - p,p ′ Σ p,p ′ ) / / H k-n+1+α p+p ′ (Σ - p,p ′ , Σ - p,p ′ Σ p+p ′ ),
where the vertical arrows are the respective Thom isomorphisms. The proof of proposition 4.4

is not yet achieved because we are still at the level of composable loops and the composition has not yet been performed. D) Some difficulty comes here from the fact that the composition map comp : Σ - p,p ′ → Λ p+p ′ could be singular along Σ p+p ′ in the direction of ν p,p ′ since comp maps Σ p,p ′ into the critical level set of ℓ whose value is p + p ′ . We are going to construct: a) a linear embedding ϕ : ν → T Λ|Σ p+p ′ , over the identity of Σ p+p ′ , such that Hess(ℓ 2 ) • ϕ is negative definite; b) a homotopy from comp to exp • ϕ • exp -1 among the maps of pairs

(Σ - p,p ′ , Σ - p,p ′ Σ p+p ′ ) → (Λ p+p ′ , Λ p+p ′ Σ p+p ′ ). If such items exist, comp * : H * (Σ - p,p ′ , Σ - p,p ′ Σ p+p ′ ) → H * (Λ p+p ′ , Λ p+p ′ Σ p+p ′
) commutes with the respective Thom isomorphisms, as it is true for ϕ * , and the proof of proposition 4.4 is finished.

We choose ϕ to be the identity of the factor E - p ⊕ E - p ′ . This makes sense as E - p γ (resp. E ′- p γ ′ ) embeds canonically into (T Λ p+p ′ ) γ * γ ′ , thought of as the set of vector fields tangent to M along γ * γ ′ : it is a set of tangent vector fields which are vanishing along γ ′ (resp. along γ); notice that a vector in (E p ) γ corresponds to a vector field along γ which vanishes at γ(0) since UM is homogeneous.

Let (γ, γ ′ ) ∈ Σ p+p ′ ⊂ Σ p,p ′ and X be a vector in ν (γ,γ ′ ) . This vector indicates an infinitesimal deformation of (γ, γ ′ ) among the pairs of composable closed smooth geodesics, deformation which separates the directions of their initial velocities. Precisely, there is a one-parameter family (γ u , γ ′ u ), u ∈ [0, ε), of pairs of closed geodesics such that γ u (0) = γ(0) = γ ′ (0) = γ ′ u (0) and d du γu (0) -γ′ u (0) |u=0 = X (up to a positive scalar); here we identify ν (γ,γ ′ ) with the fibre UM γ(0) . Instead of taking this deformation which leaves the length unchanged, we consider the following shortening deformation made of geodesic triangles T u : the first edge in T u is γ u (t), t ∈ [0, 1 -ε], the second edge joins geodesically the point γ u (1 -ε) to the nearby point γ ′ u (ε) and the third edge is γ ′ u (t), t ∈ [ε, 1] (the triangle is parametrized proportionally to arc length). We define ϕ(X) to be the infinitesimal generator of this family. By estimating ℓ(T u ) it is easily seen that Hess(ℓ 2 ) ϕ(X) < 0. Moreover ϕ(X) is independent of E - p ⊕ E - p ′ since, as a tangent vector field to M along the composed loop γ * γ ′ , it does not vanish at the junction point γ(1) = γ ′ (0). This proves item a). In order to obtain item b) it is sufficient to make ǫ tend to 0. ⋄ By taking the different regradings into account, the Thom isomorphism yields when p > 0: The multiplicative structure on E 1 * , * can be interpreted in terms of H * (UM). The following statement is due to Chataur-Le Borgne in [START_REF] Chataur | Homology of spaces of regular loops in the sphere[END_REF] (up to the coefficient system). Here E 1 * , * is endowed with the bigraded ring structure yielded by proposition 4.2. The intersection rings H * (M) and H * (UM) have bi-degree (0, * ). The new variable T has bi-degree (1, α 1 +n-2) and appears only at a positive power. Regarding H * (UM) as a H * (M)-module, the right hand side has a well-defined ring structure.

2) The differential d 1 on page 1 vanishes at every place.

3) The page ∞ inherits the same isomorphism of bigraded rings as page 1:

E ∞ * , * ∼ = H * (M; Z or ) ⊕ H * (UM; Z)[T ] ≥1 .
Proof. 1) We read the first page of the spectral sequence, E 1 * , * , via the Thom isomorphism taking proposition 4.4 into account. For instance, we have (without writing the coefficients):

H 0 (UM) = H 2n-1 (UM) = H 2n-1+α 1 (UM) ∼ = E 1 1,2n-2+α 1 = E 1 1,n-2+α 1
and T is nothing but the image of the unit µ ∈ H 0 (UM) (that is, the fundamental class of UM) through the Thom isomorphism. Once the desired ring isomorphism is specified on T it extends globally using the multiplicative property of the Thom isomorphism.

2) As H * (Λ 0 ) is a direct factor in H * (Λ), d 1 : E 1 1, * → E 1 0, * has to vanish. In particular, d 1 (T ) = 0. As d 1 is a derivation (prop. 4.2), it vanishes everywhere.

3) As a consequence, page 2 of the spectral sequence is isomorphic to page 1 as a bi-graded ring. Therefore the differential d 2 vanishes for the same reason as d 1 . Proceeding recursively through the successive pages yields the conclusion. ⋄

Proposition 3 . 3 .

 33 Let [ξ] ∈ H p (LM; Z or ) and [η] ∈ H q (LM; Z or ). These classes can be represented by cycles in LM such that ξ × η is a transverse bi-cycle. The class of ξ • CS η is uniquely defined in H p+q-n (LM; Z or ).

  h p : H * (UM; Z) ∼ = H * +αp (Λ p , Λ p-1 ; ev * 0 (Z or )). Notice also that the Gysin morphism H * (M; Z or ) → H * +n-1 (UM; Z) makes H * (UM; Z) a H * (M; Z or )-module for the intersection product. In the next proposition the coefficients are not written; they are meant as we just specified them. Proposition 4.4. (Goresky-Hingston, [9] Theorem 12.5). The Thom isomorphisms carry the intersection product of H * (UM) into the loop product of ⊕ p>0 H * +αp (Λ p , Λ p-1 ). Moreover, they carry the H * (M)-module structure of H * (UM) to the H * (Λ 0 )-module structure of H * (Λ p , Λ p-1 ).

∼

  = H p+q+n-αp (Σ p , Z) ∼ = H p+q+n-αp (UM, Z) ∼ = H p+q+n-αp-(2n-1) (UM, Z),where H * (UM; Z) denotes the regraded intersection ring of the (2n -1)-dimensional manifold UM. Similarly, after regrading the Gysin morphism, H * (M; Z or ) → H * +n-1 (UM; Z), becomes a morphism of degree 0, H * (M; Z or ) → H * (UM; Z), making H * (UM; Z) a H * (M; Z or )-module for the intersection product.

Proposition 4. 5 . 1 )

 51 There is an isomorphism of bigraded rings:E 1 * , * ∼ = H * (M; Z or ) ⊕ H * (UM; Z)[T ] ≥1 .

  well defined in H p+q+r-2n (LM; Z or ). Moreover, in that situation the following facts are easily checked:-ξ × η is transverse; -(ξ * η) × ζis transverse (where * stands for the loop intersection product); -(ξ • η) • ζ coincides with ξ • η • ζ up to a canonical reparametrization of the circle. The last item yields the associativity in homology once it is observed that the same is true for other bracketing.