topology and combinatorics. A detailed description would take us too far

a¬eld, but we will attempt to get some of the main ideas across.

69

Let us look at the situation from a geometric point of view. Each equation

xi1 = xi2 = · · · = xik determines an (n ’ k + 1)-dimensional linear subspace

of Rn , the n-dimensional space consisting of all n-tuples (x1 , x2 , . . . , xn ) of

real numbers xi . The k-equal problem is from this point of view to determine

whether a given point x = (x1 , x2 , . . . , xn ) lies in at least one such subspace,

or ” which is the same ” lies in the union of all the subspaces xi1 = xi2 =

· · · = xik .

Removal of linear subspaces disconnects Rn . For instance, removal of a

plane (a 2-dimensional subspace) cuts R3 into two pieces, whereas removal

of a line (a 1-dimensional subspace) leaves another kind of “hole”. These

are precisely the kinds of holes that are measured by the topological Betti

numbers (as was discussed in Section 9). Going back to the general situation,

it seems clear that if all the subspaces xi1 = xi2 = · · · = xik are removed from

Rn then lots of holes of di¬erent dimensions will be created. This must mean

that the sum of Betti numbers of Mn,k , the part of space Rn that remains

after all these subspaces have been removed, is a large number:

β(Mn,k ) = β0 (Mn,k ) + β1 (Mn,k ) + · · · + βn (Mn,k ).

The idea now is that if the space Mn,k is complicated topologically, as

measured by this sum of Betti numbers, then this ought to imply that it

is computationally di¬cult to determine whether a point x lies on it. This

turns out to be true in the following quantitative form.

Fact 1. The complexity of the k-equal problem is at least log3 β(Mn,k ).

Here log3 denotes logarithm to the base 3, which di¬ers by a constant factor

from the logarithm to the base 10 that was mentioned earlier.

So, now the problem has been converted into a topological one ” to com-

pute or estimate the sum of Betti numbers β(Mn,k ). This can be done via a

formula of Robert Mark Goresky (b. 1950) and Robert Duncan MacPherson

(b. 1944), which expresses these Betti numbers in terms of some ¬nite sim-

plicial complexes associated to certain partitions. To get further we need to

introduce a few more concepts from combinatorics.

We began this paper by discussing partitions of numbers, and we shall

70

return once more to the ubiquitous concept of partitions. Here we need,

however, the notion of partitions of sets. A partition of a ¬nite set A is a

way of breaking it into smaller pieces, namely a collection of pairwise disjoint

subsets whose union is A. (None of these subsets is allowed to be empty ”

in other words, all the subsets have at least one element.) For instance, here

are the 15 partitions of the set {1, 2, 3, 4}:

1234, 12”34, 13”24, 14”23, 1”234, 2”134, 3”124, 4”123,

12”3”4, 13”2”4, 14”2”3, 23”1”4, 24”1”3, 34”1”2,

1”2”3”4

In the following we will use {1, 2, . . . , n} as the ground set and for ¬xed k

(an integer between 2 and n) consider the collection of all partitions of this

set that have no parts of sizes 2, 3, . . . , k ’ 1. Denote this collection by Πn,k .

For instance, Π4,2 is the collection of all partitions of {1, 2, 3, 4} (there are no

forbidden parts), while Π4,3 is the following subcollection (now parts of size

2 are forbidden):

1234, 1”234, 2”134, 3”124, 4”123, 1”2”3”4

There is a natural way to compare set partitions, saying that partition π

is less than partition σ (written π ¤ σ) if π is obtained from σ by further

partitioning its parts. This way we get an order structure on the set Πn,k ,

which can be illustrated in a diagram. Figure 12 shows the order diagram of

Π4,2 and Figure 13 shows that of Π4,3 .

These diagrams are to be understood so that a partition π is less than a

partition σ if and only if there is a downward path from σ to π in the order

diagram, corresponding to further breaking up of σ™s parts.

Now, consider the M¨bius function (see BOX) computed over the poset

o

Πn,k . Let µn,k denote the value that the M¨bius function attains at the par-

o

tition with only one part, which is at the top of the order diagram. For

example, computation as demonstrated in the BOX over the posets in Fig-

ures 12 and 13 shows that µ4,3 = 3 and µ4,2 = ’6.

71

1234

123 4 12 34 14 23 134 2 234 1

124 3 13 24

14 2 3

12 3 4 13 2 4 23 1 4 24 1 3 34 1 2

1234

Figure 12: Π4,2

1234

124 3

123 4 134 2 234 1

1234

Figure 13: Π4,3

72

We can now return to the discussion of the k-equal problem. Where we

left o¬ was with the question of how to estimate the sum of Betti numbers

β(Mn,k ). The formula of Goresky and MacPherson mentioned earlier implies,

by an argument involving among other things the topological signi¬cance of

the M¨bius function, the following relation:

o

Fact 2. β(Mn,k ) ≥ |µn,k |.

Putting Facts 1 and 2 together, the complexity question for the k-equal

problem has been reduced to the problem of showing that the combinatorially

de¬ned numbers |µn,k | grow su¬ciently fast. For this we turn to the method

of generating functions, already introduced in the early sections on counting

number partitions. Certain recurrences for the numbers µn,k lead, when

interpreted at the level of generating functions, to the following formula:

xn x2 xk’1

exp µn,k =1+x+ + ··· + . (26)

n! 2! (k ’ 1)!

n≥1

n

To make sense of this you have to imagine inserting the series y = n≥1 µn,k x

n!

yn

into the exponential series exp(y) = n≥0 n! , and then expanding in pow-

ers of x. Also, since µn,k has so far been de¬ned only for k ¤ n we should

mention that we put µn,k = 0 for 1 < n < k and µ1,k = 1.

From this relation between the numbers µn,k and the polynomial on the

right-hand-side (which is a truncation of the exponential series) we can ex-

tract the following explicit information.

Fact 3. Let ±1 , ±2 , . . . , ±k’1 be the complex roots of the polynomial 1 + x +

x2 xk’1

+ · · · + (k’1)! . Then

2!

’n

’n ’n

µn,k = ’(n ’ 1)! ±1 + ±2 + · · · + ±k’1 .

For instance, if k = 2 there is only one root ±1 = ’1, and we get

µn,2 = (’1)n’1 (n ’ 1)!.

73

Also, in this case the formula (26) specializes to

n

n’1 x

exp (’1) = 1 + x,

n

n≥1

which is well-known to all students of the calculus in the equivalent form

n

n’1 x

log(1 + x) = (’1) .

n

n≥1

√

If k = 3 there are 2 roots ±1 = ’1 + i and ±2 = ’1 ’ i, where i = ’1, and

using some formulas from elementary complex algebra we get

3πn

n

µn,3 = ’(n ’ 1)! (’1 + i)’n + (’1 ’ i)’n = ’(n ’ 1)! 21’ 2 cos . (27)

4

We have come to a point where we know on the one hand from Facts 1

and 2 that

the complexity of the k-equal problem ≥ log3 |µn,k |,

and on the other that the M¨bius numbers µn,k are given in terms of the roots

o

±1 , ±2 , . . . , ±k’1 as stated in Fact 3. It still remains to show that the numbers

|µn,k | are large enough so that log3 |µn,k | produces the desired complexity

lower bound. For this reason it comes as a chilling surprise to discover that

these numbers are not always very large. In fact, formula (27) shows that

µn,3 = 0, for n = 6, 10, 14, 18, 22, . . . .

It can also be shown that µ2k,k = 0 for all odd numbers k.

So, we are not quite done ” but almost! With a little more work it can

be shown from the facts presented so far that |µn,k | is, so to say, “su¬ciently

large for su¬ciently many n” (for ¬xed k). With this, and a “monotonicity

argument” to handle the cases where |µn,k | itself is not large but nearby

values are, it is possible to wrap up the whole story and obtain the initially

stated lower bound of the form “constant times n log 2n ”.k

74

Let us mention in closing that it is possible to work with Betti numbers

the whole way, never passing to the M¨bius function as described here. This

o

route is a bit more complicated but results in a better constant for the lower

bound.

BOX: The M¨bius function.

o

The M¨bius function is one of the most important tools of algebraic com-

o

binatorics. It assigns a very signi¬cant integer to every ¬nite “poset”. This

word is an abbreviation which stands for “partially ordered set”; for sim-

plicity we will assume that all posets considered have a bottom and a top

element. Figure 14 shows a poset of eight elements with bottom element “a”

and top element “h”.

h

t

d d

d

d

ft gt d

d

d d

d dt e

d

d