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)}$ :

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

Nested powers and collisions: final chapter

Related

Leave a Reply Cancel reply