The ABSTRACT LACE EXPANSION Doron ZEILBERGER ^{1}

For Erdős Pál, In Memoriam

Abstract: David Brydges and Thomas Spencer’s Lace Expansion is abstracted, and it is shown how it sometimes gives rise to sieves.

LACES

Definition: Let P be a finite set of properties. A mapping l that assigns to any subset S ⊂ P another subset l(S), is called a lace-map, if for all S, G, S_{1}, S_{2} ⊂ P:

(i) l(S) ⊂ S ; (ii) l(S) ⊂ G ⊂ S ⇒ l(G) = l(S) ; (iii) l(S_{1}) = l(S_{2}) ⇒ l(S_{1} ∪ S_{2}) = l(S_{1}) .

A set L for which l(L) = L is called a lace. By applying (ii) to G = l(S), it is seen that l(l(S)) = l(S), for any set of properties S, hence l(S) is always a lace, and l is a projection: l^{2} = l.

If L is a lace then, by (iii), there exists a set C(L) ⊂ P \L such that

{S ⊂ P | l(S) = L} = {S | L ⊂ S ⊂ L ∪ C(L)} .

The set C(L) is called the set of properties compatible with L. The collection of laces will be denoted by L. For any lace L, obviously C(L) = {p ∈ P \L | l(L ∪ {p}) = L}.

Theorem: Let X be a set of elements each of which possesses a subset of the properties of P. Let wt be any function on X (in particular the counting function wt(x) ≡ 1). For any lace L define N(L) to be the sum of the weights of those elements of X that definitely have all the properties of L and definitely don’t have any of the properties in C(L). Then the sum of the weights of those elements of X that have none of the properties of P, N_{0}(X), is given by:

N_{0}(X) = ∑_{L∈L}(−1)^{|L|}N(L) .  (Lace Expansion)

Proof: For each property p ∈ P, assign a variable Y_{p}. Since every subset S of P has a unique lace L = l(S), and by (iii), the collection of subsets G for which l(G) = L consist of the interval (in the Boolean lattice) between L and L ∪ C(L), we have

∏_{p∈P}(1 + Y_{p}) = ∑_{S⊂P} ∏_{s∈S} Y_{s} = ∑_{L∈L} ∑_{{S; \atop l(S)=L}} ∏_{s∈S} Y_{s} =

∑_{L∈L} ∏_{s∈L} Y_{s} ∑_{{S; \atop l(S)=L}} ∏_{s∈S\L} Y_{s} = ∑_{L∈L} ∏_{s∈L} Y_{s} ∏_{s∈C(L)}(1 + Y_{s}) .  (∗)

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu ;

http://www.math.temple.edu/~zeilberg. Supported in part by the NSF. Dec. 5, 1996.

For every x ∈ X and p ∈ P, let χ_{p}(x) = −1 if x has property p and 0 if x doesn’t. Since 0^{r} = 0 when r > 0, while 0^{0} = 1, we have

N_{0}(X) = ∑_{nX} wt(x) ∏_{p∈P}(1 + χ_{p}(x)) = ∑_{x∈X} wt(x) ∑_{L∈L} ∏_{p∈L} χ_{p}(x) ∏_{p∈C(L)}(1 + χ_{p}(x)) =

∑_{L∈L} ∑_{x∈X} wt(x) ∏_{p∈L} χ_{p}(x) ∏_{p∈C(L)}(1 + χ_{p}(x)) = ∑_{L∈L}(−1)^{|L|}N(L) .

SIEVES

Let’s call a lace saturated if its set of compatible properties, C(L), is empty. In this case N(L) is simply the sum of the weights of the elements of X that definitely have all the properties in L (and possibly others). Let L_{s} be the collection of saturated laces. If l is such that the parity of the cardinalities of all unsaturated laces is always the same, one has the inequalities:

N_{0}(X) ≤ ∑_{L∈L_{s}}(−1)^{|L|}N(L) or

N_{0}(X) ≥ ∑_{L∈L_{s}}(−1)^{|L|}N(L) ,

according to whether that parity is odd or even respectively.

EXAMPLES

1) The identity lace-map : l(S) = S for every S ⊂ P. Every subset S of P is a lace, and C(S) is always empty. In this case the Lace Expansion reduces to the inclusion-exclusion principle.

2) The Bonferroni Lace: Let P = {1, …, n}, for a positive integer n. For S ⊂ P, define l(S) to be the subset of S consisting of its k smallest elements, if |S| ≥ k, and otherwise l(S) := S. It is easy to see that l is a lace-map, and that the laces are the subsets of P with cardinality ≤ k. The saturated laces are those whose cardinality is < k and for an unsaturated lace L = {i_{1} < … < i_{k}}, C(L) = i_{k} + 1, i_{k} + 2, …, n. The resulting sieve is the Bonferroni sieve (see, e.g., [C]).

3) The Brun Lace : Let P = {1, 2, …, n}, and let n ≥ N_{1} ≥ N_{2} ≥ … ≥ N_{n} ≥ 1 be given beforehand. For a set S = {i_{1} > i_{2} > … > i_{r}}, define l(S) = S if i_{1} ≤ N_{1}, i_{2} ≤ N_{2}, …, i_{r} ≤ N_{r}, and otherwise, let l(S) = {i_{1}, …, i_{s}}, where s is the smallest index such that i_{s} > N_{s}. It is easy to see that l is a lace-map. The saturated laces are sets of the form L = {i_{1} > … > i_{r}}, where i_{1} ≤ N_{1}, i_{2} ≤ N_{2}, …, i_{r} ≤ N_{r}. The unsaturated laces are sets L = {i_{1} > … > i_{r}}, such that i_{1} ≤ N_{1}, i_{2} ≤ N_{2}, …, i_{r−1} ≤ N_{r−1}, but i_{r} > N_{r}. For such a lace, C(L) = {i_{r} − 1, i_{r} − 2, …, 1}.

To get upper and lower Brun sieves([B]) we must have N_{1} = N_{2}, N_{3} = N_{4}, … N_{n−1} = N_{n}, and N_{2} = N_{3}, N_{4} = N_{5}, … N_{n−1} = N_{n}, respectively.

4) The Brydges-Spencer Original Lace Expansion[BS] (see [MS] for a very lucid exposition): Fix n, and let P = {(i, j); 0 ≤ i < j ≤ n}. It is instructive to think of n + 1 dots placed in a row, at locations 0, 1, …, n. Then P is the set of all arcs joining two dots. For any set of arcs G, the lace-map, l(G), is defined as follows. Let s_{1} := 0, and let t_{1} be the largest t such that 0t ∈ G. Among all the arcs st ∈ G that “go over” t_{1}, let t_{2} be the endpoint that goes farthest amongst them: t_{2} := max{t : st ∈ G, s < t_{1}}, and amongst those arcs take s_{2} to be the left-endpoint farthest to the left that connects to t_{2}: s_{2} := min{s : st_{2} ∈ G}. One continues recursively: t_{i} := max{t : st ∈ G, s < t_{i−1}}, and s_{i} := min{s : st_{i} ∈ G}, until either one gets, for some k, t_{k} = n, or one finishes the connected component and starts a new component with the next dot. The lace of G, l(G), is defined to be the collection of these arcs {s_{1}t_{1}, s_{2}t_{2} …, s_{k}t_{k}}. Observe that the arcs of an irreducible lace interlace, forming the kind of lace people embroider, which explains its name.

The Brydges-Spencer lace expansion does not yield any sieves, but serves another purpose: to determine the asymptotic behavior of the number of n-step self-avoiding walks. Brydges and Spencer[BS] determined the asymptotics for weakly avoiding walks in dimensions d ≥ 5, while Hara and Slade[HS][MS], in one of the greatest mathematical feats of this decade, strengthened it to the regular self-avoiding walk in d ≥ 5. The problem is still open for dimensions d = 2, 3, 4. Perhaps we need a more complicated lace-map.

SPECULATIONS

I predict that the Abstract Lace Expansion (ALE) has a bright future. The very powerful Probabilistic Method([ASE],[S]) uses the Bonferroni sieve with k = 2. Introducing appropriate lace-maps may make it even more powerful. The Satisfiability Problem (the grandmother of all NP-complete problems) can be approached via counting (the number of covered 0-1 vectors), and introducing powerful lace-maps may improve the average-running-time of current algorithms. Another possible application is to improving current asymptotic upper and lower bounds for R(n, n), as well as to the exact evaluations of R(5, 5) and R(6, 6), in spite of Paul Erdős’s pessimistic prophesy (see [S], p. 4). Recall that the Ramsey number, R(n, n), is the smallest N such that if you 2-color the edges of the complete graph on N vertices, then you are guaranteed a monochromatic K_{n}.

This gives rise to the following counting problem. Let X is the set of all 2^{\binom{N}{2}} edge-colorings, and let P consist of the \binom{N}{n} properties: A_{S} := the induced coloring on S is monochromatic, where S ranges over all n−subsets of the set of vertices {1, …, N}. Find the number N_{0}(X) of property-less colorings. If, thanks to some lower sieve, we can ascertain that N_{0}(X) > 0, then we would get that R(n, n) > N. If, on the other hand, thanks to an upper sieve, we would find that N_{0}(X) ≤ 0, then we would know that N_{0}(X) = 0, and that R(n, n) ≤ N. So we need good lace-maps that would give good sieves that, in turn, would make the lower and upper bounds zero-in at the exact value.

REFERENCES

[ASE] N. Alon and J. Spencer, with P. Erdős, “The Probabilistic Method”, Wiley, NY, 1992.

[B] V. Brun, Le crible d’Eratosthène et le théorème de Goldbach, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-Naturvidenskabelig Klasse 1(1920), 1-36.

[BS] D.C. Brydges and T. Spencer, Self-avoiding walks in 5 or more dimensions, Comm. Math. Phys. 97(1985), 125-148.

[C] L. Comtet, “Advanced Combinatorics”, Dordrecht-Holland/Boston, 1974.

[HS] T. Hara and G. Slade, The lace expansion for self-avoiding walk in five or more dimensions, Reviews in Math. Phys. 4(1992), 235-327.

[MS] N. Madras and G. Slade, “The Self Avoiding Walk”, Birkhauser, Boston, 1993.

[S] J. Spencer, “Ten Lectures on the Probabilistic Method”, SIAM, Philadelphia, 1987.