Nested powers and collisions: final chapter

This is where the story of nested powers of metric spaces and of collision-inducing ODE reaches its logical conclusion.

Theorem 1. For every {d\ge 1} and every {n\ge 2} there exists a Lipschitz retraction {r\colon {\mathbb R}^d(n)\rightarrow {\mathbb R}^d(n-1)}.

Compared to previous posts, I changed notation to improve readability: {X(n)} now stands for the set of all nonempty subsets of {X} with at most {n} elements. The metric on {X(n)} is the Hausdorff metric {d_H}. The map {r} was defined in Collisions II as follows:

Given a set {A\in {\mathbb R}^d(n)\setminus {\mathbb R}^d(n-1)}, enumerate its elements {a_1,\dots,a_n} and consider the initial-value problem

\displaystyle    \dot{x}_i = \sum_{j\ne i}\frac{x_j-x_i}{|x_j-x_i|}, \quad x_i(0)=a_i, \quad i=1,\dots,n

Define {r(A) = \{x_i(t_c)\}} where {t_c} be the time of the first collision between particles in this system. Also define {r(A)=A} when {A\in{\mathbb R}^d(n-1)}.

I claim that

\displaystyle    d_H(r(A),r(B))\le (2n-1)\sqrt{n} \,d_H(A,B)   \ \ \ \ \ (1)


for all {A,B\in{\mathbb R}^d(n)}. Interestingly, the Lipschitz constant does not depend on the dimension of ambient space. (Well, I’m not so sure it has to depend on cardinality either.)

Proof. Let

\displaystyle \delta(A)=\begin{cases} \min_{i\ne j}|a_i-a_j|,\quad  A\in{\mathbb R}^d(n)\setminus {\mathbb R}^d(n-1) \\ 0,\quad \quad A\in \mathbb R^d(n-1) \end{cases}

It is easy to check that the function {A\mapsto \delta(A)} is {2}-Lipschitz on {{\mathbb R}^d(n)}.

Earlier I proved that { t_c\le \dfrac{1}{2}\delta(A)} and, as a consequence,

\displaystyle    d_H(r(A),A)\le \frac{n-1}{2} \delta(A)   \ \ \ \ \ (2)

Let {\rho=d_H(A,B)}. If {\delta(A)+\delta(B)\le 4\,\rho}, then (2) already gives (1). From now on assume {\delta(A)> 2\,\rho}, hence {\delta(B)>0}. The geometric meaning of these inequalities is that the points of {A} are spread out in space, yet each of them is close to a point of {B}. Therefore, we can enumerate them {a_i} and {b_i} in such a way that {|a_i-b_i|\le \rho} for all {i}.

Let {(x_i)} and {(y_i)} be the solutions of our ODE with initial data {(a_i)} and {(b_i)}, respectively. Here comes a monotonicity lemma.

Lemma 2. {\sum_{i=1}^n |x_i-y_i|^2} is nonincreasing with time {t}.

Proof: Encode the sequence {(x_i)} by a single point {\mathbf{x}\in {\mathbb R}^{nd}}. This point is moved by the gradient flow of the convex function {\Phi(\mathbf{x}) = \sum_{i<j}|x_i-x_j|}. Since the gradient of a convex function is monotone, we have {\langle {\mathbf{ \dot x}}-{\mathbf{\dot y}}, \mathbf{x}-\mathbf{y}\rangle\le 0}. It follows that {|\mathbf{x}-\mathbf{y}|^2} is nonincreasing. \Box

By Lemma 2, {|x_i-y_i|\le \sqrt{n}\,\rho } holds for all {i} until a collision occurs in either system. We may assume that {x}-particles collide first. Then, at the time of their collision they form the set {r(A)} while the {y}-particles form some set {B'}, with {d_H(r(A),B')\le \sqrt{n}\,\rho}. Since r(A) has fewer than n elements, {\delta(B')\le 2d_H(r(A),B')}. From (2) we obtain {d_H(r(B'),B')\le 2(n-1)\sqrt{n}\,\rho}. Note that {r(B')=r(B)} because our ODE system is autonomous. The final estimate is {d_H(r(A),r(B))\le d_H(r(A),B')+d_H(r(B'),B')}, which is (1). {\Box}

Here is how a 20-point set gets retracted onto {{\mathbb R}^2(19)}:

20 particles, stopped
20 particles, stopped

The plot was produced by a version of the familiar Scilab routine, modified to stop the computation at first collision. It was called with

gravity3(grand(1,20,"unf",0,2),grand(1,20,"def"),300)
function gravity3(vx,vy,Nsteps)
    Npoints = length(vx);
    h = 0.01/Npoints;
    tolerance = h*(Npoints-1)/3;
    collided = 0;
    x = zeros(Nsteps,Npoints);
    y = zeros(Nsteps,Npoints);
    x(1,:) = vx;
    y(1,:) = vy;
    m = 1;
    while (m<Nsteps & collided==0) do
        x(m+1,:)= x(m,:);
        y(m+1,:)= y(m,:);
        for i = 1:Npoints
            for j = (i+1):Npoints
                v = [x(m,j),y(m,j)]-[x(m,i),y(m,i)];
                if norm(v) < tolerance then 
                    collided=1; 
                else
                    x(m+1,i) = x(m+1,i) + h*v(1)/norm(v);
                    x(m+1,j) = x(m+1,j) - h*v(1)/norm(v);
                    y(m+1,i) = y(m+1,i) + h*v(2)/norm(v);
                    y(m+1,j) = y(m+1,j) - h*v(2)/norm(v);
                end
            end
        end
    m = m+1;    
    end
    clf();
    plot(x(:,:),y(:,:),'o');
endfunction

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s