Calculus VII

Three weddings and a funeral

Posted on February 24, 2012 by Leonid Kovalev

This is a continuation of the series on submetries. First, an example: the distance function to a closed convex set $K\subset \mathbb R^n$ is a submetry from $\mathbb R^n\setminus K$ onto $(0,\infty)$ . Note that the best regularity we can expect from such distance function is $C^{1,1}$ , the Lipschitzness of first derivatives. The second derivative does not exist at the points where level curves make the transition from straight to circular.

Distance function is a submetry

Now back to an attempt to introduce duality between immetries (=isometric embeddings) and submetries. Recall that the Lipschitz dual $X^\sharp$ of a pointed metric space $X\ni 0$ is the set of all Lipschitz functions $\varphi\colon X\to\mathbb R$ such that $f(0)=0$ . Given the Lipschitz norm, $X^\sharp$ becomes a Banach space. Any closed ball $B_r(a)\subset X$ can be written as
(*) $B_r(a)=\lbrace x\in X\colon |\varphi(x)-\varphi(a)|\le r \text{ for all } \varphi\in X^\sharp \text{ such that }\|\varphi\|\le 1\rbrace$ .
Indeed, $\subset$ is obvious, and the reverse inclusion follows by considering $\varphi(x)=d(x,a)-d(0,a)$ .

It’s natural to use (*) to relate immetries to submetries, because the former are defined by $f^{-1}(B_r(f(x)))=B_r(x)$ and the latter by $f(B_r(x))=B_r(f(x))$ .

In the previous post I considered four implications:

If $f$ is an immetry, then $f^\sharp$ is a submetry
If $f$ is a submetry, then $f^\sharp$ is an immetry
If $f^\sharp$ is an immetry, then $f$ is a submetry
If $f^\sharp$ is a submetry, then $f$ is an immetry

Here is a proof of (4). If $f^{\sharp}\colon X^\sharp\to Y^\sharp$ is a submetry, then $\lbrace \varphi\in X^\sharp \colon \|\varphi\|\le 1\rbrace = \lbrace \psi\circ f\colon \psi\in Y^\sharp, \|\psi\|\le 1\rbrace$ . We can use this in (*) to obtain, for any $a\in X$ and $r\ge 0$ ,
$B_r(a)=\lbrace x\in X\colon |\psi(f(x))-\psi(f(a))|\le r \text{ for all } \psi\in Y^\sharp \text{ such that }\|\psi\|\le 1\rbrace$ .
The latter set is nothing but $\lbrace x\in X\colon f(x)\in B_r(f(a))\rbrace$ , which means $f$ is an immetry.

I already noted that (3) fails for general metric spaces, the inclusion $f\colon \mathbb Q\to \mathbb R$ being a counterexample. However, this counterexample is not impressive, because $f(B_r(x))$ is dense in $B_r(f(x))$ . One could still hope that (3) holds for proper metric spaces. By definition, a metric space is proper if every closed ball is compact. (Or, equivalently, every bounded sequence has a convergent subsequence.) In metric geometry properness is a very common assumption which excludes incomplete spaces and infinite-dimensional spaces. Its relevance to submetries can be seen from their definition $f(B_r(x))=B_r(f(x))$ . It requires the image $f(B_r(x))$ to be closed, which is not very likely to happen unless $B_r(x)$ is compact. (No such issues arise on the immetry side, because $f^{-1}(B_r(f(x)))$ is always closed.)

However, it turns out (3) is false even for compact spaces. The counterexample was already present on this blog:

These aren't the quotients I'm looking for

Indeed, the Lipschitz norm of a function $\varphi$ defined on an interval is equal to the essential supremum of $|\varphi'|$ . The composition with the metric quotient map given above preserves $\mathrm{ess\,sup}\, |\varphi'|$ . Hence, the induced map $[0,2]^\sharp\to [0,3]^\sharp$ is an immetry.

Posted in Uncategorized | Tagged immetry, Lipschitz dual, submetry | Leave a comment

Lipschitz duality: immetries and submetries

Posted on February 21, 2012 by Leonid Kovalev

Continuation of an earlier post that considered submetries, namely the maps $f\colon Y\to X$ between metric spaces such that $f(B_r(y))=B_r(f(y))$ for all $y\in Y$ and all $r\ge 0$ . (Here and in what follows $B_r$ is a closed ball.) The dual notion is an immetry: a map $f\colon X\to Y$ such that $f^{-1}(B_r(f(x)))=B_r(x)$ for all $x\in X$ and all $r\ge 0$ . Immetries can be characterized by the condition $d(f(a),f(b))=d(a,b)$ , which means they are nothing but isometric embeddings. I just made up the word to introduce symmetry between submetry and immetry. And then tried to look it up.

This has got me stumped

In what sense are these dual? Recall that reversal of arrows in a “categorical” definition of an immetry did not produce a submetry. Let’s try another approach. Let our metric spaces be pointed: they all contain the point $0$ which is fixed by all maps under consideration. The Lipschitz dual $X^\sharp$ of a metric space $X$ consists of all Lipschitz maps $\varphi\colon X\to \mathbb R$ . This is naturally a vector space. Moreover, it is a Banach space with the norm $\displaystyle \|\varphi\|=\sup\frac{|\varphi(a)-\varphi(b)|}{d(a,b)}$ . A Lipschitz map $f\colon X\to Y$ induces a bounded linear operator $f^\sharp\colon Y^\sharp\to X^\sharp$ . If $f$ is 1-Lipschitz, then so is $f^\sharp$ (i.e., its operator norm is at most 1).

It would be nice to have the following:

$f$ is an immetry iff $f^\sharp$ is a submetry
$f$ is a submetry iff $f^\sharp$ is an immetry

but that’s too much to hope for. For example, the inclusion of $\mathbb Q$ into $\mathbb R$ is not a submetry, but it induces the identity map $\mathbb R^\sharp\to\mathbb Q^\sharp$ . Let’s go through these one by one.

Suppose $f\colon X\to Y$ is an immetry. Then we think of $X$ as a subset of $Y$ , and $f^\sharp$ is simply the restriction operator. To prove that it’s a submetry, we should verify the 2-point lifting property: given any $\varphi,\psi\in X^\sharp$ and any $\Phi\in Y^\sharp$ that extends $\varphi$ , we must find $\Psi\in Y^\sharp$ that extends $\psi$ and satisfies $\|\Psi-\Phi\|=\|\psi-\varphi\|$ . This is easy: extend $\psi-\varphi$ in a norm-preserving way (by McShane-Whitney) and add $\Phi$ .

I also wrote down an (easy) proof that $f$ being a submetry implies that $f^\sharp$ is an immetry, but WP ate it. Specifically, having pressed “Save Draft”, I was asked to re-login (the cookie expired). Having done so, I was presented with a 10 min old draft.

We already know that $f^\sharp$ being an immetry does not imply that $f$ is a submetry. Whether $f^\sharp$ being an submetry implies that $f$ is an immetry is left as an exercise for the reader.

Posted in Uncategorized | Tagged immetry, Lipschitz dual, submetry, symmetry | 1 Comment

Compactness of operators, and a lot of projections

Posted on February 19, 2012 by Leonid Kovalev

Let $\mathcal{H}$ be an infinite-dimensional Hilbert space. Claim: an operator $T\colon\mathcal{H}\to\mathcal{H}$ is compact if and only if $Te_n\to 0$ for every orthonormal sequence $\lbrace e_n\rbrace$ .
Continue reading →

Posted in MAT 702 Functional Analysis | Tagged compact operator, orthonormal sequence, projection | Leave a comment

Injective:Surjective :: Isometric:?

Posted on February 17, 2012 by Leonid Kovalev

I used this sort of title before, in “Continuous:Lipschitz :: Open:?“, but the topics are related anyway.

In some sense (formal or informal) the following classes of maps are dual to each other.

Injective : Surjective
Immersion : Submersion
Monomorphism : Epimorphism

An isometric embedding of metric space $X$ into a metric space $Y$ is a map $f\colon X\to Y$ such that $d_Y(f(a),f(b))=d_X(a,b)$ for all $a,b\in X$ . This concept belongs to the left column of the table above. What should be its counterpart?

Candidate 1. Observe that a 1-Lipschitz map $f\colon X\to Y$ is an isometric embedding iff it does not factor through any 1-Lipschitz surjection $g\colon X\to Z$ (for any space $Z$ ) unless $g$ is an isometric isomorphism. Reversing the order of arrows, we arrive at the following concept:

A 1-Lipschitz map $f\colon Y\to X$ is a metric quotient map if it does not factor through any 1-Lipschitz injection $g\colon Z\to X$ (for any space $Z$ ) unless $g$ is an isometric isomorphism.

This can be reformulated as follows: $\rho(a,b):=d_{X}(f(a),f(b))$ is the greatest pseudo-metric on $Y$ subject to

$\rho(a,b)\le d_{Y}(a,b)$
$\rho(a,b)=0$ if $f(a)=f(b)$

This seems reasonable: $f$ does as little damage as possible, given the structure of its fibers. There is also a natural way to construct $\rho$ for any reasonable fibering of $Y$ : begin by defining $\widetilde{d_Y}=d_Y$ for points in different fibers and $0$ otherwise. Then force the triangle inequality by letting $\rho(a,b)=\inf \sum_{j=1}^n \widetilde{d_Y}(y_j,y_{j-1})$ subject to $y_0=a$ and $y_n=b$ . As long as the fibers stay at positive distance from one another, this $\rho$ will be a metric. The corresponding metric quotient map sends each point of $Y$ onto its fiber.

Here is a simple example, in which a part of an interval is mapped to a point.

These aren't the quotients I'm looking for

However, the above example made me unhappy. The only nontrivial fiber is the interval $[1,2]$ . Both points $0$ and $3$ belong to trivial fibers, but the distance between them decreases from 3 to 2. This looks like a wrong kind of quotient to me.

Candidate 2 already appeared in my post on Lipschitz quotient, but wasn’t recognized at the time. It could be called $(1,1)$ -Lipschitz quotient, but a better name is available. A map $f\colon Y\to X$ is a submetry if $f(B_Y(y,r))=B_X(f(y),r)$ where the balls are closed (using open balls yields something almost equivalent, but generally weaker). Such $f$ need not be an isometry: consider orthogonal projections in a Euclidean space. It does have to be 1-Lipschitz. The additional property that distinguishes it from general 1-Lipschitz maps is the 2-point lifting property: for every $x_0,x_1\in X$ and every $y_0\in f^{-1}(x_0)$ there is $y_1\in f^{-1}(x_1)$ such that $d_{Y}(y_0,y_1)=d_X(x_0,x_1)$ . Incidentally, this shows that $x\mapsto f^{-1}(x)$ is an isometric embedding of $X$ into the hyperspace $\mathcal{H}(Y)$ which I covered earlier (“This ain’t like dusting crops, boy“).

The concept and the name were introduced by В.Н. Берестовский (V.N. Berestovskii) in his paper “Submetries of space-forms of nonnegative curvature” published in 1987 in Siberian Math. J. Among other things, he proved that a submetry between spheres (of any dimension) is an isometry. Of course, there are many submetries of $S^{n-1}$ onto other spaces: take the quotient by a subgroup of $O(n)$ , which can be either discrete or continuous. Are there any submetries that are not quotients by isometries?

Yes, there are. I’ll describe a (modified) example given by Berestovskii and Guijarro (2000). Let $\mathbb{H}$ be the hyperbolic plane realized as the upper half-plane with the metric $\frac{dx^2+dy^2}{y^2}$ . Define $f\colon \mathbb{H}\to\mathbb{R}$ by

$\displaystyle f(x,y)=\begin{cases} \log y, \qquad x\le 0 \\ \log\frac{x^2+y^2}{y}, \qquad x\ge 0 \end{cases}$

Don’t panic; this is just the signed distance function (in the metric of $\mathbb H$ ) to the fat green curve below. I also drew two other level sets of $f$ , to the best of my Friday night line-drawing ability.

Weird submetry

To convince yourself that $f$ is a submetry, first consider $y\mapsto \log y$ for which the submetry property is clear (it’s the quotient by horizontal translation), and then note that the inversion in the unit circle exchanges horizontal lines (horocycles at infinity) with horocycles at 0. An interesting feature of this submetry that it is not very smooth: $C^{1,1}$ but not $C^2$ .

Posted in Seminar | Tagged lipschitz, metric space, quotient, submetry | Leave a comment

Re: “Democracy on the high seas” by Colin Carroll

Posted on February 16, 2012 by Leonid Kovalev

A slightly modified version of the riddle discussed in detail by Colin Carroll. I recap the key parts of his description below. Rule 4 was added by me in order to eliminate any probabilistic issues from the problem.

You are the captain of a pirate ship with a crew of N people ordered by rank. Your crew just managed to plunder 100 Pieces of Eight. Now you are to propose a division of the 100 PoE, and the crew will vote on the division. The captain doesn’t vote except to break a tie. If the proposal fails, the captain walks the plank, and the first mate becomes captain, the third in command becomes first mate, and so on. Each pirate votes according to the following ordered priorities:

They do not want to die.

They want to maximize their own profit.

They like to kill people, including crewmates.

They prefer to be on good terms with the higher ranked crewmates.

The question is: what division do you, as the captain, suggest?

Continue reading →

Posted in Uncategorized | Tagged Democracy, Google spreadsheet, Pirates | Leave a comment

The exits are North South and East but are blocked by an infinite number of mutants

Posted on February 15, 2012 by Leonid Kovalev

I used the word mutation in the previous post because of the (implicit) connection to quiver mutation. The quiver mutation is easy to define: take an oriented graph (quiver) where multiple edges are allowed, but must have consistent orientation (i.e., no 2-edge oriented cycles are allowed). Mutation at vertex v is done in three steps:

v is removed and each oriented path of length two through v is contracted into an edge. That is, the stopover at v is eliminated.
Step 1 may create some 2-edge oriented cycles, which must be deleted. That is, we cancel the pairs of arrows going in opposite directions.
The replacement vertex v’ is inserted, connected to the rest of the graph in the same way that v was, but with opposite orientation. In practice, one simply reuses v for this purpose.

Some quivers have a finite set of mutation equivalent ones; others an infinite one. Perhaps the simplest nontrivial case is the oriented 3-cycle with edges of multiplicities $x,y,z$ . The finiteness of its equivalents has to do with the Markov constant $C(x,y,z)=x^2+y^2+z^2-xyz$ (not $3xyz$ this time), which is invariant under mutation. This is investigated in the paper “Cluster-Cyclic Quivers with Three Vertices and the Markov Equation” by Beineke, Brűstle and Hille. The appendix by Kerner relates the Markov constant to Hochschild cohomology, which I take as a clue for me to finish this post.

So I’ll leave you to play with the mutation applet linked in the embedded tweet below.

Tired of Sudoku? Try quiver mutation puzzles math.jussieu.fr/~keller/quiver… and maybe win €20. Mutation rules & more puzzles at mutatingquivers.com—
Syracuse Mathematics (@SUmathematics) February 14, 2012

Posted in Seminar | Tagged Hochschild cohomology, quiver mutation | Leave a comment

“Let me say a few words about the solutions in positive integers of the equation

Posted on February 14, 2012 by Leonid Kovalev

$x^2+y^2+z^2=3xyz.$

This equation is symmetric with respect to unknown terms $x$ , $y$ , $z$ ; therefore, knowing one of its solutions

$x=\alpha, \quad y=\beta, \quad z=\gamma,$

it is easy to find the following five:

$x=\alpha, \quad y=\gamma, \quad z=\beta;$
$x=\beta, \quad y=\gamma, \quad z=\alpha;$
$x=\beta, \quad y=\alpha, \quad z=\gamma;$
$x=\gamma, \quad y=\alpha, \quad z=\beta;$
$x=\gamma, \quad y=\beta, \quad z=\alpha.$

Although these six solutions may be different, we will consider them as one, denoted by

$x,y,z=\alpha,\beta,\gamma.$ “

The above is a quote from A.A.Markov’s paper “Sur les formes quadratiques binaires indéfinies” (part 2). Back in 1880 people were patient enough to write out all permutations of three symbols… If we fix $x=\alpha$ and $y=\beta$ , the equation for $z$ becomes

$z^2-3\alpha \beta z +(\alpha^2+\beta^2)=0$

which admits the second integer root $\gamma'=3\alpha\beta-\gamma$ . We can also write $\gamma\gamma'=\alpha^2+\beta^2$ which does not immediately tell that $\gamma'$ is an integer, but it does tell us that $\gamma'$ is positive. For example, from the obvious solution $(1,1,1)$ we get $(1,1,2)$ . Now it would not do us any good to mutate in the third variable again, for it would bring us back to $(1,1,1)$ . But we can mutate in the second variable, replacing it with $6-1=5$ . Having understood so well the symmetry of the equation, we write this new solution as $(1,2,5)$ , in the increasing order. Now we can mutate either 1 or 2, and so it goes…

Markov number tree, from http://en.wikipedia.org/wiki/File:MarkoffNumberTree.png

All triples, except for the two at the beginning, consist of distinct numbers (thus, they do generate six distinct solutions if order matters). The tree contains all solutions of the Markov equation. The Wikipedia article also points out the occurrence of Fibonacci numbers along the top branch, as well as a curious identity discovered by Don Zagier: let $f(t)=\cosh^{-1}(3t/2)$ ; then (for triples written in increasing order)

$\displaystyle x^2+y^2+z^2=3xyz+\frac{4}{9} \quad \Leftrightarrow \quad f(x)+f(y)=f(z)$

Looks like a fun problem on simplification of inverse hyperbolic trigonometric functions.

Also, it’s still unknown whether two distinct Markov triples can have the same maximum $\max(\alpha,\beta,\gamma)$ . Looks like a fun problem for amateur number theorists.

To wrap this up, I will describe how Markov (the one of Markov chains fame, not his identically-named son of 4-manifold undecidability fame) came across the equation. Let $Q(m,n)=am^2+2bmn+cn^2$ be a quadratic form with real coefficients $a,b,c$ normalized by $b^2-ac=1$ . What is the best upper bound on

$\displaystyle \min_{(m,n)\in \mathbb{Z}^2\setminus \lbrace(0,0)\rbrace} |Q(m,n)|?$

In 1873 Korkin and Zolotarev published a paper showing that the best bound is $2/\sqrt{5}$ , attained by the form $\displaystyle Q_1=\frac{2}{\sqrt{5}}(m^2-mn-n^2)$ . Looks like the case is closed. But what if $Q$ is not $Q_1$ (precisely, not equivalent to $Q_1$ under the action of $SL(2,\mathbb Z)$ )? Then the best bound improves to $1/\sqrt{2}$ , attained by $\displaystyle Q_2=\frac{1}{\sqrt{2}}(m^2-2mn-n^2)$ (this is also due to KZ). Well, what if $Q$ is not equivalent to either $Q_1$ or $Q_2$ ? Then the bound improves to $\sqrt{\frac{100}{221}}$ (found by Markov), and we could go on…

But rather than continue in this fashion, Markov looked for the threshold $\mu$ at which the number of inequivalent forms with minimum $\ge \mu$ becomes infinite. And he found it: $\mu =2/3$ (for comparison, $\sqrt{\frac{100}{221}}=0.67267\dots$ ). Specifically, there are only finitely many forms with minimum above $2/3+\epsilon$ , for every $\epsilon>0$ . But there are infinitely many forms with minimum exactly $2/3$ , such as $\frac{2}{3}(x^2-\sqrt{5}xy-y^2)$ . It was the iterative process of getting more and more of these forms that led Markov to the Diophantine equation $x^2+y^2+z^2=3xyz$ .