# 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. 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.