<<

. 11
( 14 .)



>>

and mathematically more interesting part. The proof uses a combination of
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  

<<

. 11
( 14 .)



>>