🚀 go-pugleaf

Bjorn Poonen <poonen@digel.Berkeley.EDU> writes:
>QUESTION: Suppose you have an n-element multiset S deforming into
>another n-element multiset T.  Can you find a path from a given element
>of S to some element of T?

I think the following proves the stronger version of Bjorn's conjecture,
that a path in M^n/S_n can be lifted to M^n.


   Theorem.  Let I be the unit interval [0,1], and let M be an arbitrary
metric space.  Let S_n act on M^n by permuting the coordinates, and let
p: M^n -> M^n/S_n be the projection map.  Let f be a continuous map f: I
-> M^n/S_n.  Then there exists g: I -> M^n such that f = p o g.


   Proof of Theorem 1.  The proof goes by induction on n.  Clearly the
result is trivial for n = 1, because the projection map p is a bijection
and there is a unique possible lift.  So, we assume the result for every
n' < n, and proceed to prove it for n.

   Without loss of generality, we can assume the special case that for
every 0 < x < 1, f(x) is a multiset which contains at least two distinct
values.  Suppose that the theorem is true in this special case.  Then,
in the general case, the points x where f(x) has n repeated values
partition the remaining points in [0,1] into disjoint subintervals.  On
each such subinterval, we can apply the theorem in the special case to
obtain a lift.  At the points where there are n repeated values, there
is a unique lift.  Combining all of these lifts gives a lift on all of
[0,1].

   Let 0 < x < 1.  Consider the multiset f(x).  In the special case, it
contains k distinct values, z_1,...,z_k, where k \ge 2.  Let the minimum
distance in M between any two z_i be d.  By continuity, there is a open
interval N containing x such that, for x' in N, f(x') is within distance
d/2 of f(x).  This implies that we can partition all of the elements of
M which occur in multisets f(x'), for x' \in N, into points which are
within distance d/2 of z_1, points which are within distance d/2 of z_2,
and so on.

   For each k, let n_k be the cardinality of z_k in f(x).  Construct
f_k: N -> M^{n_k}/S_{n_k}, where f_k(x') consists of the n_k elements of
f(x') which are within distance d/2 of z_k.  Now, n_k < n, so by the
induction hypothesis on Theorem 1, there is a lift g_k: N -> M^{n_k}.

   The product of all the g_k is a lift of f on N.  Now, let x = 1/2.
Consider the union of all open intervals containing 1/2 on which a lift
of f exists.  This is the open interval (a,b), with a < 1/2 < b.  Choose
a lift of f on (a,b).  By continuity, this extends to a lift of f on
[a,b].

   Suppose b < 1.  Then, apply the previous argument again with x = b,
to construct a lift of f on an open interval containing b.  By
restriction, this gives a lift of f on the half-open interval [b,c) for
some c > b.  And, we can act on this lift by an element of S_n to make
it agree with the previous lift at b.  Combining the lifts gives a lift
on (a,c), which contradicts the hypothesis that (a,b) is the maximal
open interval containing 1/2 on which a lift exists.

   Thus b must be equal to 1.  The same argument shows that a must be
equal to 0.  Thus we have constructed a lift of f on [0,1] in the
special case, and the previous argument shows that this implies the
general case of the theorem.  QED.

                                        David desJardins