text:
# Can the Lawvere fixed point theorem be used to prove the Brouwer fixed point theorem?

The Lawvere fixed point theorem asserts that if $X, Y$ are objects in a category with finite products such that the exponential $Y^X$ exists, and if $f : X \to Y^X$ is a morphism which is surjective on points in the sense that the induced map $\text{Hom}(1, X) \to \text{Hom}(1, Y^X)$ is surjective, then $Y$ has the fixed point property: for every morphism $g : Y \to Y$ there exists a point $y : 1 \to Y$ such that $g \circ y = y$.

The Brouwer fixed point theorem asserts that the closed $n$-disks, all of which I will denote by $D$ for ease of notation, have the fixed point property as objects of $\text{Top}$.

Seeing these two theorems together, it is tempting to try to prove the latter from the former by finding a topological space $X$ such that the exponential $D^X$ exists, together with a surjective continuous map $X \to D^X$. Does there in fact exist such an $X$?

Edit, 4/13/17: I'm still interested in this question, and so are some people associated with MIRI (at least when $n = 1$); for some details about why see here.

• I guess I should mention, in passing, that Lawvere's is much more constructive than Brouwer's. So, if there is an implication that way, the space $X$ will have to contain a lot of non constructive data. (What is needed is essentially a choice of a point from every nonempty compact subspace of $\mathbb{R}$.) – François G. Dorais Jul 12 '13 at 20:54
• Hey! Next, let's prove the measure-theoretic Fubini theorem from the Category theory Fubini theorem! – Gerald Edgar Jul 12 '13 at 21:08
• Category theory seems to have the universal property of eliciting snarky remarks from those who don't have much taste for it. – Todd Trimble Jul 13 '13 at 11:20
• @user36938 : well, I see your point, but I think maybe you're being a little harsh ("does not belong on MO"). Even if we assume the question was a shade offhand (e.g., even if Qiaochu hadn't considered the constructivity aspects before posting), that's true of so many questions here; it's okay to kick it around for a few minutes before deciding that it's naive. It all comes under the heading of exploring. For a comparison: there are a lot of naive questions about logic here. But they usually don't elicit the same kinds of cracks, do they? No "logic corrupting the youth of today" trope. – Todd Trimble Jul 15 '13 at 6:22
• Well, I'm not sure. All I can say is that there are a lot more wise-cracks about category theory, and a lot of people think they understand it well enough to make pronouncements on (and jokes about) it. Happily, such jokes are becoming more and more pass\'e, as more and more people see that category theory is seriously useful stuff, and that professional category theorists are not in the business of "trying to get something from nothing". (Still, I can't think of any other field where people make such jokes. Can you?) – Todd Trimble Jul 15 '13 at 17:37

In my experience it is worth considering variants of Lawvere fixed point theorem. In the present case, I would split things up as follows, in order to circumvent the non-constructive nature of Brouwer's fixed point theorem.

Also, let me point out that we need not worry about exponentials too much, even though they do not exist in the category of topological spaces, unless the exponent is nice enough. We can move over to a cartesian-closed subcategory, such as teh compactly generated spaces, or to a cartesian closed supcategory, such as equilogical spaces.

Theorem: [Approximate Lawvere] Suppose $(B, d)$ is a metric space and $e : A \to B^A$ is a continuous map, such that for every continuous map $g : A \to B$ and $\epsilon > 0$ there is $a \in A$ such that $d(e(a)(a), g(a)) < \epsilon$. Then every continuous map $f : B \to B$ has approximate fixed points: for every $\epsilon > 0$ there is $b \in B$ such that $d(b, f(b)) < \epsilon$.

Proof. Given any $f$ and $\epsilon$ consider the map $g(a) = f(e(a)(a))$. there is $a \in A$ such that $d(e(a)(a), g(a)) < \epsilon$ and then $b = e(a)(a)$is an $\epsilon$-approximate fixed point of $f$. QED.

One way to use the theorem is via the sup metric (allowing infinite distance):

Corollary: If $e : A \to B^A$ has a dense image in the sup metric on $B^A$ then every endomap on $B$ has approximate fixed points.

Suppose we could apply the previous theorem to the closed ball $D^n$. Then we would know (constructively!) that every endomap on $D^n$ has approximate fixed points. then we just have another easy step, which contains all the classical reasoning needed:

Theorem: Suppose $X$ is compact and $f : X \to X$ has an $\epsilon$-approximate fixed point for every $\epsilon > 0$. Then $f$ has a fixed point.

Proof. By countable choice, for every $n$ there is $x_n \in X$ such that $d(x_n, f(x_n)) < 1/n$. Because $X$ is compact, $x_n$ has a subsequence converging to some $y \in X$. It is now easy to see that $y$ is a fixed point of $f$. QED.

But I do not see how to apply the approximate Lawvere to the closed ball, if that is even possible.

• We now have a bunch of results showing that the direct Lawvere fixed-point theorem is unlikely to succeed (see @ToddTrimble's answer). Can someone show that we can have $X \to [0,1]^X$ with a dense image? Or can we? – Andrej Bauer Apr 19 '17 at 21:36
• You can't have $e$ continuous w.r.t. the sup metric and have dense image, because that would give you a continuous surjection $\beta A \to B^{\beta A}$, where $\beta A$ is the Stone-Čech compactification, since $(B^A, \sup) \cong (B^{\beta A})$. You might be able to get $e$ continuous w.r.t. the exponential topology but have dense image w.r.t. the sup metric. Also, even though @ToddTrimble retracted his answer, you can't have a continuous surjection $A \to D^A$ with $A$ compact Hausdorff and $D$ a disk because $D^A$ would have the topology of the unit ball of a Banach space. – Sam Eisenstat Apr 22 '17 at 7:35

This is not an answer, but I will try to explain why I think that it is unlikely for such a space $X$ to exist.

If we replace $D$ by say, a sphere, then (using Lawvere's fixed point theorem and the fact that spheres do have fixed-point-free self-maps) such a space $X$ does not exist for the sphere. Now, I really don't see how to possibly use the fact that the disc is a disc in constructing the space $X$. So I am tempted to believe that your $X$ does not exist.

• Why can't we do an "Eilenberg swindle" where we take X to be a countable iterated exponential of disks? Something must go wrong because if that worked for disks, it would work for spheres too. Does such an iterated exponential not make sense? – Chris Schommer-Pries Jul 12 '13 at 20:56
• If such a swindle worked, it would work in the category of sets as well. It seems to me the basic problem is that there are no canonical maps between $X$ and $D^X$, so there's no obvious way to take a (co)limit of finite iterated exponentials to get an "infinite iterated exponential". – Eric Wofsey Jul 12 '13 at 21:19
• @Eric: this doesn't quite sink us. For example, as it turns out there is a canonical map $D \to D^D$ (constant functions) as well as a canonical map $D^{D^D} \to D^{D^{D^D}}$ (apply the functor $X \mapsto D^X$ to the previous map twice). These are the odd-numbered maps in a hypothetical diagram of shape $D \to D^D \to D^{D^D} \to ...$ that we would want. But it turns out that there are no canonical candidates for the even-numbered maps (in a precise sense; there are no such maps in the free cartesian closed category on $X$). We can "fix" this by considering a diagram of shape... – Qiaochu Yuan Jul 13 '13 at 4:37
• $D \to D^{D^D} \to D^{D^{D^{D^D}}} \to ...$, which does exist but which doesn't give us the kind of fixed point we would want (if the colimit exists and if the double dual functor $X \mapsto D^{D^X}$ preserves it then it's a fixed point of the double dual functor). – Qiaochu Yuan Jul 13 '13 at 4:38

Edit: Will Sawin has pointed out some difficulties with this answer. I'm going to leave this up for at least a while, in case anyone has any ideas about repairing it. Or perhaps this could be a cautionary tale?

My answer is that there is no space $X$ admitting a continuous surjection $X \to D^X$.

Following one of Andrej's suggestions, let's extend the context from $\text{Top}$ to the quasitopos $\text{Choq}$ of Choquet (aka pseudotopological) spaces. This is a convenient setting because quasitoposes are cartesian closed (so we never have to wonder about the existence of certain exponentials, as we would for $\text{Top}$), and moreover this won't alter the problem of the OP because the full inclusion $i: \text{Top} \to \text{Choq}$ preserves cartesian products and any exponentials that happen to exist in $\text{Top}$. A further convenience is that $\text{Choq}$ is concrete and even topological (over $\text{Set}$), and we may say that a map of Choquet spaces is surjective if its underlying function is, so that the inclusion $i$ also preserves surjective maps. (By concreteness, every surjective map is an epimorphism, and the converse is true in $\text{Choq}$.)

Suppose that there is a topological space $X$ such that $D^X$ exists in $\text{Top}$ and there is a surjective continuous map $\phi: X \to D^X$. In $\text{Choq}$ we get an induced map $D^\phi: D^{D^X} \to D^X$. The idea now is to construct a retraction to $D^\phi$ which might suggestively be denoted $\text{Ran}_\phi: D^X \to D^{D^X}$ (think "right Kan extension"), by exploiting the fact that $D = [0, 1]^n$ is an internal sup-lattice in $\text{Choq}$. Granting this possibility for the moment, and putting $Z = D^X$, we now have that $D^Z$ is a retract of $Z$ (to simplify notation, call the retraction $r: Z \to D^Z$ and the section $s: D^Z \to Z$), which opens the door to the argument given by Sam Eisenstat over at the related thread: Is there a topological space X homeomorphic to the space of continuous functions from X to [0, 1]?. In detail, for variables $z$ of type $Z$ and $g$ of type $D^D$, introduce the fixed-point combinator $Y: D^D \to D$ (which will live by the way in $\text{Top}$, since $D$ is an exponentiable space) by the formulas

$$H := \lambda g. s(\lambda z. g(r(z)(z)))$$

$$Y := \lambda g. (r(H(g)))(H(g))$$

and verify in the usual manner that $Y(g)$ of type $D$ is a fixed point of $g$. Then invoke Sam's argument that such continuous fixed-point combinators $Y$ can't exist. (Technically, he indicated the reason for the special case $D = I = [0, 1]$, but the problem for general $D$ can be reduced to the special case as follows. Supposing a fixed point combinator $Y: D^D \to D$ exists, choose a pair $\rho: D \to I, \sigma: I \to D$ that exhibits $I$ as a retract of $D$, and verify that the composition

$$I^I \stackrel{\sigma^\rho}{\to} D^D \stackrel{Y}{\to} D \stackrel{\rho}{\to} I$$

is a fixed point combinator, which is impossible by Sam's argument.) Contradiction.

The task now is to construct the retraction $\text{Ran}_\phi: D^X \to D^{D^X}$. As indicated before, the background of this construction is a theory of sup-lattices in quasitoposes, for which I know no literature reference, but at some point I can make some notes on this available on my nLab web. In fact I had begun a pretty deep dive into this theory here, but then luckily found some simplifications which circumvent a lot of this theory. I'll go into the simplified proof in the final section, after introducing some necessary definitions in the next section (for those not very categorically minded, the next section has the function of sparing us the terrible agony of verifying that certain "easily defined" functions between certain Choquet spaces really are continuous maps -- the abstract account which comes next does all that work for us).

A quasitopos $Q$ has a regular subobject classifier $\Omega$, which for $\text{Choq}$ is just a 2-point set $\{f, t\}$ equipped with the codiscrete (indiscrete) topology. (If $X$ is a Choquet space, then the points of $P X = \Omega^X$ are given by subspaces of $X$, i.e., subsets of $X$ with the subspace pseudotopology, or just the subspace topology if $X$ is a topological space.) Next, each map in $Q$ has a (unique) epi-(regular mono) factorization, due to the very useful fact that a quasitopos is not just regular but coregular ($Q^{op}$ is regular); see Johnstone's Elephant, Corollary A.2.6.3. The mono part will be called the regular image of $f$. This permits us to define, for a map $f: X \to Y$, the direct image mapping $\exists_f: \Omega^X \to \Omega^Y$ that in the case $Q = \text{Choq}$ takes a subspace $U$ of $X$ to the subspace $f(U)$ of $Y$. Formally, $\exists_f$ is defined by starting with the canonical regular subobject $\in_X \hookrightarrow X \times \Omega^X$ that is classified by the evaluation mapping $X \times \Omega^X \to \Omega$, then taking the regular image of the composite

$$\in_X \hookrightarrow X \times \Omega^X \stackrel{f \times 1}{\to} Y \times \Omega^X,$$

then forming the classifying map $Y \times \Omega^X \to \Omega$ of the regular image, and then currying that to get $\exists_f: \Omega^X \to \Omega^Y$.

Next, let us define a poset in $Q$ to be an object $X$ together with a regular subobject $i: X_1 \hookrightarrow X \times X$ satisfying standard axioms. If $X, Y$ are two posets, we can define their internal hom $[X, Y]$ as the pullback of an evident diagram

$$\begin{array}{ccccc} & & & & Y_1^{X_1} \\ & & & & \downarrow j^{X_1} \\ Y^X & \stackrel{sq}{\to} & (Y \times Y)^{X \times X} & \stackrel{(Y \times Y)^i}{\to} & (Y \times Y)^{X_1} \end{array}$$

where $sq(f) := f \times f$. The pullback of the regular mono $j^{X_1}$ along the bottom composite is again a regular mono $[X, Y] \to Y^X$. Of course $\Omega$ has a standard ordering $f \leq t$ and the points of $[X, \Omega]$ are given by regular upward-closed subobjects of $X$; for the quasitopos $\text{Choq}$ I'll just call them "up-sets", and similarly the points of $[X^{op}, \Omega]$ are "down-sets".

We will want to consider $[X^{op}, \Omega]$ as a free posetal cocompletion of $X$, so let's say a few words on that. The "Yoneda embedding" $y_X: X \to [X^{op}, \Omega]$ is obtained by letting $\chi_{X_1}: X \times X \to \Omega$ classify the regular subobject $X_1 \hookrightarrow X \times X$, and then appropriately currying to a map $X \to \Omega^X$, and noting this factors through a map $X \to [X^{op}, \Omega]$ by the poset axioms. We form a cocompletion functor $\mathbf{P}$ which takes a poset $X$ to $[X^{op}, \Omega]$. For a poset map $f: X \to Y$, the map $\mathbf{P}f: [X^{op}, \Omega] \to [Y^{op}, \Omega]$ is to take a down-set $U$ of $X$ to the down-set generated by the direct image $\exists_f(U)$ in $Y$. Formally: if the poset $Y$ is given by a span $Y \stackrel{\pi_1}{\leftarrow} Y_1 \stackrel{\pi_2}{\to} Y$, then the composite

$$\Omega^Y \stackrel{\pi_2^\ast}{\to} \Omega^{Y_1} \stackrel{\exists_{\pi_1}}{\to} \Omega^Y$$

has as its regular image the inclusion $[Y^{op}, \Omega] \hookrightarrow \Omega^Y$ we constructed earlier. This map maps a regular subobject to the down-set it generates. Denoting its epi-(regular mono) factorization as

$$\Omega^Y \stackrel{e}{\to} [Y^{op}, \Omega] \hookrightarrow \Omega^Y$$

we now define $\mathbf{P}f: \mathbf{P}X \to \mathbf{Y}$ to be the composite

$$[X^{op}, \Omega] \hookrightarrow \Omega^X \stackrel{\exists_f}{\to} \Omega^Y \stackrel{e}{\to} [Y^{op}, \Omega].$$

The functor $\mathbf{P}$ thus defined on the category of internal posets carries a monad structure whose unit is the Yoneda embedding $y$ (i.e., the component at $X$ is the principal down-set map $y_X: X \to [X^{op}, \Omega]$ we constructed earlier), and the multiplication turns out to be given by

$$\text{mult}_X := [y_X^{op}, \Omega]: [[X^{op}, \Omega]^{op}, \Omega] \to [X^{op}, \Omega].$$

Officially, a sup-lattice is a $\mathbf{P}$-algebra. It can also be described as a poset $X$ whose Yoneda embedding $y_X: X \to \mathbf{P}X$ has a left adjoint (which will then be the algebra structure $\mathbf{P}X \to X$: there can be only one, as $\mathbf{P}$ is a lax idempotent or KZ monad).

What seems to simplify matters greatly is to introduce another concept which, I'm pretty darned sure, is equivalent to the concept of sup-lattice. (See the post Retractions of Yoneda are reflectors, i.e., left adjoints? for some explanation why.)

Definition: An s-lattice is a poset $X$ whose Yoneda embedding admits a retraction. We let $\sup_X$ generically denote a chosen retraction (although as I suggest, I think there can be at most one!).

Here is the seed example. In $\text{Choq}$, the poset $I = [0, 1]$ is an s-lattice. The poset of down-sets $[I^{op}, \Omega]$ may be identified with $I \times \{f \leq t\}$ under the lexicographic order, topologized by the order topology. (One should check that the compact-open topology is in fact this order topology.) The Yoneda embedding takes $x \in I$ to $(x, t)$. The retraction is just the projection map $I \times \{f, t\} \to I$.

Lemma 1: If $L$ is an s-lattice, then so is $L^X$ for any object $X$.

Proof: Regard $X$ as an internal discrete poset (both maps of the span being $1_X$). There is an evident identification $\mathbf{P}(L \times X) = (\mathbf{P}L)^X$. Now examine the diagram

$$\begin{array}{cccccc} L^X & \stackrel{y^X}{\to} & \mathbf{P}(L \times X) & & & & \\ y \downarrow & & y \downarrow & \searrow^{id} & & & \\ \mathbf{P}(L^X) & \underset{\mathbf{P}(y^X)}{\to} & \mathbf{PP}(L \times X) & \underset{\text{mult}}{\to} & \mathbf{P}(L \times X) & \underset{\sup_L^X}{\to} & L^X \end{array}$$

(the square commutes by naturality of $y$, and the triangle commutes by a unit equation for the monad $\mathbf{P}$), and use the fact $\sup_L^X \circ y_L^X = 1_{L^X}$. Thus the bottom composite retracts $y_{L^X}$. $\Box$

For example, $D = I^n$ is an s-lattice in $\text{Choq}$. It follows further that any $D^X$ is an s-lattice.

Recall that if $A, B$ are posets and $f: A \to B$ is a poset map, then $f$ is an embedding if $a \leq a'$ in $A$ whenever $f(a) \leq f(a')$ in $B$. It is easy to see that embeddings are monomorphisms.

Lemma 2: If $f: X \to Y$ is a surjection in $\text{Choq}$ and $D$ is a poset, then $D^f: D^Y \to D^X$ is an embedding.

This is pretty obvious. $D^f(g) := g \circ f$, so $D^f(g) \leq D^f(g')$ means $g f \leq g' f$. This implies $g \leq g'$ by surjectivity of $f$.

Lemma 3: If $h: A \to B$ is a poset embedding in $\text{Choq}$, then $[h^{op}, \Omega]$ retracts $\mathbf{P}h$.

Proof: It suffices to check this at the level of underlying sets, by concreteness of $\text{Choq}$ over $\text{Set}$. Let $U \in \mathbf{P}A$ be a down-set of $A$. Then $\mathbf{P}h(U) = \{b \in B: \exists_{a \in A} a \in U \wedge b \leq h(a)\}$. The function $[h^{op}, \Omega]$ sends this down-set to $\{a' \in A: \exists_{a \in A} a \in U \wedge h(a') \leq h(a)\}$. Since $h$ is an embedding, this is the same as $\{a' \in A: \exists_{a \in A} a \in U \wedge a' \leq a\}$, but this is just $U$ since $U$ is downward-closed. $\Box$

Our task is completed with the following result.

Theorem: If $f: X \to Y$ is a continuous surjection in $\text{Choq}$ and $D$ is an s-lattice, then $\text{Ran}_f := \sup_{D^Y} \circ [(D^f)^{op},\Omega] \circ y_{D^X}$ retracts $D^f$.

Proof: We have

$$\begin{array}{ccc} 1_{D^Y} & = & \sup_{D^Y} \circ y_{D^Y} \\ & = & \sup_{D^Y} \circ [(D^f)^{op}, \Omega] \circ \mathbf{P}(D^f) \circ y_{D^Y} \\ & = & \sup_{D^Y} \circ [(D^f)^{op}, \Omega] \circ y_{D^X} \circ D^f \end{array}$$

where the first equation uses Lemma 1, the second uses Lemmas 2 and 3, and the third uses naturality of $y$. $\Box$

• How can the compact-open topology on $[I^{op}, \Omega]$ be the order topology when $\Omega$ has the indiscrete topology? – Will Sawin Apr 19 '17 at 21:35
• It seems to me like a retract of $D^f$ does not exist for an arbitrary continuous map $f$. To admit a retract, a map to a Hausdorff space must have closed image, as the image is exactly the locus where the composition of the retract with the original map is equal to the identity. If we take $X$ as the interval with the discrete topology, $Y$ with the interval with the usual topology, and $f$ the obvious map, then $I^X$ is the space of $I$-valued functions on $I$ with the topology of pointwise convergence, which is clearly Hausdorff, but within which the continuous functions are not closed. – Will Sawin Apr 19 '17 at 21:39
• @WillSawin Thanks for your comments. Yeah, something seems fishy, but I'm not quite sure where the real root of the problem is. Thinking... – Todd Trimble Apr 19 '17 at 22:31
• If it helps, I think the map $sup_L^X$ from ${\mathbf P}(L \times X)$ to $L^X$ is not well-defined, because it does not always produce continuous maps. From an arbitrary downward-closed subset of $L \times X$, by taking the supremum, we can produce an arbitrary function from $X$ to $L$ and not just a continuous function. – Will Sawin Apr 19 '17 at 22:38
• Sorry for the delay in responding. Actually, the root of the problem is that I badly misidentified the topology on $\mathbf{P}D$ (it's codiscrete, which seems painfully obvious in retrospect), and in fact $D$ is not an internal sup-lattice as defined here. Except for that, I believe the rest was correctly argued. I'm still investigating possible repairs... – Todd Trimble Apr 23 '17 at 17:43

Here is a sort of partial solution. I doubt it will be very helpful, but anyone who wants to read it is free to do so.

Let $I$ be any space with the fixed point property. We will construct a space $X$ and a map $X \to I^X$ such that many interesting maps lie in its image, including all maps that can be defined in a language consisting of $e$, continuous functions from finite powers of $I$ to itself, and constant symbols in $X$ (which are all that is needed to prove the Lawvere fixed point theorem).

To accomplish this we will inductively construct for each natural number $n$ a space $X_n$, a map $e_n: X_n \times X_n \to I$, and a map $i_n: X_n \to X_{n+1}$, such that $e_{n+1}(i_n(x_1),i_n(x_2))=e_n(x_1,x_2)$. We will also use auxiliary spaces $Y_n,Z_n$ along the way.

After this we set $X$ to be the forward limit of $X_n$ along $i_n$ and let $e: X\times X \to I$ be the limit of the $e_n$.

The significance of the spaces $Y_n$ and $Z_n$ is that $Z_n$ is the set of continuous $I$-valued functions of $x \in X$ that depend only on $e(x,x), e(x,t)$ for $t \in X_n$. $Y_n$ is the space of possible values of the pair $e(x,x), e(x,t)$, so that $Z_n$ is the space of functions on $Y_n$. Then $X_{n+1}$ is constructed so that it maps surjectively to $Z_n$, so all functions of $Z_n$ come from elements of $X_n$, and maps to $Y_n$, so that all functions of $Z_n$ can be extended to functions on $X_n$. For simplicity and canonicality, we define $X_{n+1}$ to be a subset of $Y_n \times Z_n$, defined by coherence condition to ensure the desired relationship between $Y_n$ and $e$. Then we can freely add also the functions $e(t,x)$ for $t\in X_n$ to $Z_n$, as they are already continuous functions of $e(x,x)$, $e(x,t)$ by construction of $X_n$.

To begin, let $X_0$ be the empty set.

Inductively, assume we have defined $X_{n-1}, Y_{n-1},Z_{n-1}, X_n$.

Let $Y_n$ be $I \times I^{X_n}$. Let $Z_n= I^{Y_n}$.

Let $X_{n+1}$ be the subset of $Y_n \times Z_n$ consisting of tuples $(b,c)\in Y_n, f\in Z_n$ satisfying the following two coherence conditions:

• $b= f(b,c)$

• For all $x$ in $X_n$, $c(x) = f( e_n(x,x), t \mapsto e_n(x,t))$

Let $i_n: X_n \to X_{n+1}$ send $x= ((b',c'),f)$ to $(e_n(x,x), t \mapsto e_n(x,t) ) , (\beta,\gamma)\mapsto f'(\beta, \gamma \circ i_{n-1} )$.

Let $e_{n+1}: X_{n+1} \times X_{n+1} \to I$ send $((b_1,c_1),f_1),((b_2,c_2),f_2)$ to $f_1(b_2,c_2)$.

Let us first check that for $x$ in $X_n$ corresponding to a tuple $(b,c),f$ in $Y_{n-1} \times Z_{n-1}$, $i_n(x)$ satisfies the coherence conditions.

For $x$ in $X_n$ which corresponds to a tuple $(b,c),f$, we need $e_n(x,x) = f( e_n(x,x), t \mapsto e_n(x, i_{n-1}(t))$, but $e_n(x)=f(b,c)$ so it is sufficient to check that $b=e_n(x,x)$ and $c= t \mapsto e_n(x, i_{n-1}(t))$, which are the coherence conditions of $X_n$.

Furthermore we need for $x'$ in $X_n$ corresponding to a tuple $(b',c'),f)$, $e_n(x,x') = f( e_n(x',x'),t \mapsto e_n(x',i_{n-1}(t)))$, which is true because by definition of $e_n$, $e_n(x,x') = f(b',c')$ and $b' = f'(b',c') =e_n(x',x')$ while $c'(t) = f'( e_{n-1}(t,t), s \mapsto e_{n-1}(s,t)) = e_n(x', i_{n-1}(t))$ by definition of $e_n$ and $i_{n-1}$.

Hence $i_n$ is actually a well-defined map from $X_n$ to $X_{n+1}$.

The fact that $e_{n+1}(i_n(x_1),i_n(x_2))=e_n(x_1,x_2)$ follows from unwinding the definitions.

Indeed, let $x_1 = ((b_1,c_1),f_1)$ and let $f_2=((b_2,c_2),f_2))$ and then $e_{n+1} (i_n ( x_1),i_n(x_2)) = f_1 ( e_n (x_2,x_2), t \mapsto e_n(x_2, i_{n-1}(t)) =f_1(b_2,c_2)= e_n(x_1,x_2)$ by the coherence conditions for $b_2,c_2$ and the definition of $e_n$, and then the definition of $e_n$.

Now we can define $X$ to be the forward limit of $X_n$ along $I_n$ and $e$ to be the forward limit of the maps $e_n$, which we have seen are compatible. Next we will characterize the image of the map $X \to I^X$ given by $x \mapsto (t \mapsto e(x,t))$. We will see that it this image can be viewed as the forward limit of $Z_n$ along the system of maps that we now define.

Consider the map $j_n: Y_{n+1} \to Y_{n}$ that sends $(b,c)$ to $( b, c \circ i_n)$. Consider also the map $k_n: Z_{n} \to Z_{n+1}$ by exponentiating $j_n$.

I claim that if $i_{n} ((b,c),f)= ((b',c'),f')$ then $j_n(b',c') = (b,c)$ and $k_n(f)=f'$.

The first statement is simply the fact that $b=e_n(x,x), c(t)= t \mapsto e_n(x,i_{n-1}(t))$, which follow from the definition of $e_n$ and the coherence conditions for $b$ and $c$ respectively.

The second statement follows immediately from the construction of $i_n$, which forces $f' ( \beta,\gamma) = f( \beta , \gamma \circ i_n) = \alpha(x)$ which is exactly $f \circ k_n$.

So we have verified the claim.

Let $Y$ be the inverse limit of $Y_n$ along $j_n$ and let $Z$ be the inverse limit of $Z_n$ along $k_n$, so that there is a natural map $Y \times Z \to I$. The compatibilities of $i_n$ with $j_n$ and $k_n$ respectively imply that there are map $X \to Y$ and $X \to Z$, and $e: X \times X \to I$ is simply the composition of these two with the map $Y \times Z \to I$.

Hence the map $X \to I^X$ induced by $e$ factors as $X \to Z \to I^Y \to I^X$. I can't prove that this composition is surjective but I can prove that the first map, $X \to Z$ is surjective.

To do this, it is sufficient to prove that the projection map $X_n \to Z_n$ is surjective. In other words, given $f: Y_n \to I$, construct $(b,c) \in Y_n$ satisfying the coherence conditions. Clearly we must have $c(x) = f( e_n(x,x), t \mapsto e_n(x,t))$. Then we can take $b$ to be any fixed point of $f(b,c)$.

What maps can we construct this way? We get all the maps defined by elements of $Z_n$ for all $n$. These, in turn, are all continuous maps that depend only on the data in $Y_n$. By the coherence conditions and the definition of $e$, the projection of $x \in X_n$ to $Y_n$ encode $e(x,x),t\mapsto e(x,t)$ for $t$ in $X_{n-1}$. Using the definition of $e$ and the compatibility of $e$ with $i_{n-1}$, one can see that it also encodes $t \mapsto e(t,x)$ for $t \in Y_{n-1}$. The compatibility of $i_n$ with $e$ and with $j_n$ ensure that $Y_n$ continues to encode this data for all $x$. Hence all continuous functions that depend only on $t\mapsto e(t,x),e(x,x),t\mapsto e(x,t)$, which seem to me to be all the "obvious" ones that we construct, are in the image of the constructed map $X \to I^X$.

The definability statement from earlier follows from the fact that any finite set of elements of $X$, such as the constant symbols appearing in the formula, must lie in $X_n$ for some $n$. Any function that depends only on $e$ evaluated with these constant symbols will then lie in $Z_n$.

• For clarity $X_0 = \emptyset$, $Y_0 = I$, $Z_0 = I^I$, $X_1$ is the space of pairs of a continuous map $I \to I$ and a fixed point of that map. $Y_1$ is the space of pairs of $b$ an element of $I$ and $c$ a pair of a map $I\to I$ and a fixed point, with $a$ forced to be the evaluation map that takes a map $I \to I$ (with a fixed point) to the evaluation of that map at $b$. – Will Sawin Apr 14 '17 at 5:50

EDIT: Pre-print available here. https://arxiv.org/abs/2005.01563 Note that I suspect that the use of the hypothesis of contractibility and the use of a homotopy is not really necessary, probably the hypothesis on the metric is enough.

Consider the "generalised Cantor space", the carrier set being $$2^{\omega_{1}}$$ and the basic open sets being sets consisting of all bit-strings of length $$\omega_{1}$$ with a fixed countable well-ordered bit-string as initial fragment. Denote this space by $$A'$$. Consider space with same carrier set with product topology obtained by viewing it as a product of $$\aleph_1$$ discrete spaces of cardinality two. Denote this space by $$A''$$.

I define a space $$X$$ to be a nice space" if:

First, the space $$X$$ is compact and contractible and is the image of $$A''$$ under a continuous surjection. Secondly, the space $$X$$ is the disjoint union of an open dense subset $$U$$ and the complement $$V$$, and both $$U$$ and $$V$$ admit a homogenous" metric, where what we mean by this is as follows. Firstly, with regard to $$U$$, there exists some $$\epsilon>0$$, with the property that, for all $$\delta$$ such that $$0<\delta<\epsilon$$, every pair of distinct open balls of radius $$\delta$$ centred at a point in $$U$$ such that the closure of the balls does not intersect $$V$$, has the property that the balls in the pair are isometric. Then, with regard to $$V$$, we require that sufficiently small open balls in $$X$$, centred at points of $$V$$, of the same radius, are isometric.

Every closed ball in a finite-dimensional Euclidean space is indeed a nice space. The space $$A''$$ is a $$k$$-space, and so is every nice space, so exponential topologies exist here. I claim that for each nice space $$X$$ a continuous surjection $$A' \rightarrow X^{A''}$$ exists with the following property. Take an open subset of $$X$$ and take the pre-image under the evaluation map in $$A'' \times X^{A''}$$, then take projection onto the second factor and then pre-image of that in $$A'$$ under the continuous surjection $$A' \rightarrow X^{A''}$$. The result subset of $$A'$$ is open in $$A'$$, and its image under the continuous map $$A' \rightarrow A''$$ which fixes every point is open in $$A''$$. This is enough to apply the method of proof of Lawvere to obtain that every continuous endomorphism of $$X$$ has a fixed point. Thus Brouwer can be recovered as a corollary of a suitable generalisation of Lawvere.

The question of the existence of a space $$A$$ with a continuous surjection $$A \rightarrow X^{A}$$ for every nice space $$X$$, or for every space $$X$$ in some class which includes every closed ball in a finite-dimensional Euclidean space, still remains an open problem.

Brief outline of method of proof for showing that the continuous surjection exists.

It is possible to construct an $$\omega$$-sequence $$S:=\{C_{n}:n \in \omega\}$$ of coverings of $$X$$ by finitely many open balls, each covering $$C_{n} \in S$$ being such that it can be partitioned into two collections of open balls with each collection having the property that all of the balls in it are pairwise isometric, and also such that the mesh of the covering $$C_{n}$$ tends towards zero as $$n$$ goes to infinity. Let $$T$$ be the collection of all centres of open balls occurring in some covering $$C_{n}$$.

An element of $$X^{A''}$$ can be coded for, non-uniquely, by a mapping from a countable collection of countable bit-strings $$B$$, closed under taking initial fragments, and such that every element of $$2^{\omega_1}$$ has some element of $$B$$, maximal under the "initial fragment" relation, as an initial fragment, into $$X$$, with bit-strings of successor length being mapped to elements of $$T$$.

One can further require that the trace of the mapping into $$X$$ along each branch of $$B$$ is generalised Cauchy"; it satisfies an obvious generalisation of the Cauchy criterion for each fragment of the branch of limit length, relative to the metric on $$X$$ which we have been holding fixed throughout, and with the speed of convergence having a uniform lower bound across all fragments of branches of $$B$$ of a given limit length.

Consider set of all mappings from such a set $$B$$ into $$X$$ satisfying the generalised Cauchy criterion" in question; this is in one-to-one correspondence with an appropriate set of countable well-ordered bit-strings $$D$$ under an appropriate coding scheme. Every element of $$X^{A''}$$ is coded for by at least one such mapping which in turn can be coded for by a countable well-ordered bit-string; further argument is required to show that every countable well-ordered bit-string does indeed code for an element of $$X^{A''}$$. To show that part of it, need to use a transfinite induction argument showing that from every mapping from an appropriate set $$B$$ into $$X$$ satisfying the appropriate constraints we can recover a continuous map $$2^{\alpha} \rightarrow X$$ for each countable ordinal $$\alpha$$ ($$2^{\alpha}$$ having the product topology), and that when $$\alpha$$ is sufficiently large, this map $$2^{\alpha} \rightarrow X$$ determines the map $$2^{\beta} \rightarrow X$$ (also continuous) for all $$\beta$$ such that $$\alpha \leq \beta \leq \omega_1$$. To get this transfinite induction to work we need to use both the "generalised Cauchy criterion" which is assumed to hold for our map $$B \rightarrow X$$ and also the given hypotheses on the space $$X$$, including the existence of an appropriate kind of metric on $$X$$.

Then, having done that, you need to show that the coding scheme for such maps $$B \rightarrow X$$, each such map being represented by a countable well-ordered bit-string from $$D$$, can indeed be constructed in such a way that it induces a surjection $$A' \rightarrow X^{A''}$$, continuous relative to generalised Cantor space topology on $$A'$$, and exponential topology on $$X^{A''}$$ arising from product topology on $$A''$$, which does indeed have all the properties I claimed.

That in very brief outline is the proof. Perhaps this post will still be thought inappropriate since I have not given all details. Or on the other hand maybe it can be accepted as a partial answer to the question.

• You claimed elsewhere that this work has been submitted for publication, no? Perhaps you could link to a preprint for more details? – Kevin Arlin May 3 '20 at 15:30
• Yes, I will do that. I must upload it to ArXiV and I need someone who can endorse me as an uploader of a Topology paper. Perhaps I can find a way around that by putting a bit more mathematical logic in it and uploading it as a logic paper. I will include the link to the pre-print as soon as possible. – Rupert May 3 '20 at 16:35
• It has been uploaded to Arxiv and should be available tomorrow; I will post the link then. Earlier drafts were rejected by "Advances in Mathematics" and "Geometry and Topology", in the first case on the grounds of "outside our scope and standards" and in the second case on the grounds of "need to find a more specialised journal". I have obtained new results since that time, which have just been written up this morning and appear in the final two sections, and should still be treated with some caution. – Rupert May 4 '20 at 9:23
• My degree of confidence about the results in the first two sections (described in my post) is currently pretty high but naturally I welcome critical feedback. – Rupert May 4 '20 at 9:25


text:
# Using promises with Shiny

Taking advantage of async programming from Shiny is not as simple as turning on an option or flipping a switch. If you have already written a Shiny application and are looking to improve its scalability, expect the changes required for async operation to ripple through multiple layers of server code.

Async programming with Shiny boils down to following a few steps.

1. Identify slow operations (function calls or blocks of statements) in your app.

2. Convert the slow operation into a future using future_promise(). (If you haven’t read the article on futures and future_promise(), definitely do that before proceeding!)

3. Any code that relies on the result of that operation (if any), whether directly or indirectly, now must be converted to promise handlers that operate on the future object.

We’ll get into details for all these steps, but first, an example. Consider the following synchronous server code:

function(input, output, session) {
output$plot <- renderPlot({ result <- expensive_operation() result <- head(result, input$n)
plot(result)
})
}

We’d convert it to async like this:

library(promises)
library(future)
plan(multisession)

function(input, output, session) {
output$plot <- renderPlot({ future_promise({ expensive_operation() }) %...>% head(input$n) %...>%
plot()
})
}

The easiest part is adding library(promises), library(future), and plan(multisession) to the top of the app.

The promises library is necessary for the %...>% operator. You may also want to use promise utility functions like promise_all and promise_race.

The future library is needed because the future() function call used inside future_promise() is how you will launch asynchronous tasks.

plan(multisession) is a directive to the future package, telling it how future tasks should actually be executed. See the article on futures for more details.

## Identifying slow operations

To find areas of your code that are good candidates for the future/promise treatment, let’s start with the obvious: identifying the code that is making your app slow. You may assume it’s your plotting code that’s slow, but it’s actually your database queries; or vice versa. If there’s one thing that veteran programmers can agree on, it’s that human intuition is a surprisingly unreliable tool for spotting performance problems.

Our recommendation is that you use the profvis profiler, which we designed to work with Shiny (see Example 3 in the profvis documentation). You can use profvis to help you focus in on where the time is actually being spent in your app.

Note: As of this writing, profvis doesn’t work particularly well for diagnosing performance problems in parts of your code that you’ve already made asynchronous. In particular, we haven’t done any work to help it profile code that executes in a future, and the mechanism we use to hide “irrelevant” parts of the stack trace doesn’t work well with promises. These are ripe areas for future development.

Async programming works well when you can identify just a few “hotspots” in your app where lots of time is being spent. It works much less well if your app is too slow because of a generalized, diffuse slowness through every aspect of your app, where no one operation takes too much time but it all adds up to a lot. The more futures you need to introduce into your app, the more fixed communication overhead you incur. So for the most bang-for-the-buck, we want to launch a small number of futures per session but move a lot of the waited-on code into each one.

## Converting a slow operation into a future

Now that we’ve found hotspots that we want to make asynchronous, let’s talk about the actual work of converting them to futures.

Conceptually, futures work like this:

future({
# Expensive code goes here
}) %...>% (function(result) {
# Code to handle result of expensive code goes here
})

which seems incredibly simple. What’s actually happening is that the future runs in a totally separate child R process, and then the result is collected up and returned to the main R process:

# Code here runs in process A
future({
# Code here runs in (child) process B
}) %...>% (function(result) {
# Code here runs in process A
})

The fact that the future code block executes in a separate process means we have to take special care to deal with a number of practical issues. There are extremely important constraints that futures impose on their code blocks; certain objects cannot be safely used across process boundaries, and some of the default behaviors of the future library may severely impact the performance of your app. Again, see the article on futures for more details.

The remainder of this document will use future_promise() in place of future(). For more information on the differences, see the article on the benefits of future_promise().

### Shiny-specific caveats and limitations

In addition to the constraints that all futures face, there is an additional one for Shiny: reactive values and reactive expressions cannot be read from within a future. Whenever reactive values/expressions are read, side effects are carried out under the hood so that the currently executing observer or reactive expression can be notified when the reactive value/expression becomes invalidated. If a reactive value/expression is created in one process, but read in another process, there will be no way for readers to be notified about invalidation.

This code, for example, will not work:

function(input, output, session) {
r1 <- reactive({ ... })

r2 <- reactive({
future_promise({
r1() # Will error--don't do this!
})
})
}

Even though r1() is called from inside the r2 reactive expression, the fact that it’s also in a future means the call will fail. Instead, you must read any reactive values/expressions you need in advance of launching the future:

function(input, output, session) {
r1 <- reactive({ ... })

r2 <- reactive({
val <- r1()
future_promise({
val # No problem!
})
})
}

However, it’s perfectly fine to read reactive values/expressions from inside a promise handler. Handlers run in the original process, not a child process, so reactive operations are allowed.

function(input, output, session) {
r1 <- reactive({ ... })

r2 <- reactive({
future_promise({ ... }) %...>%
rbind(r1()) # OK!
})
}

## Integrating promises with Shiny

Generally, you’ll be using promises with Shiny from within outputs, reactive expressions, and observers. We’ve tried to integrate promises into these constructs in as natural a way as possible.

### Outputs

Most outputs (renderXXX({ ... })) functions expect your code block to return a value; for example, renderText() expects a character vector and renderTable() expects a data frame. All such render functions that are included within the shiny package can now optionally be given a promise for such a value instead.

So this:

output$table <- renderTable({ read.csv(url) %>% filter(date == input$date)
})

could become:

output$table <- renderTable({ future_promise({ read.csv(url) }) %...>% filter(date == input$date)
})

output$table <- renderTable({ input_date <- input$date
future_promise({
})
})

The important thing to keep in mind is that the promise (or promise pipeline) must be the final expression in the code block. Shiny only knows about promises you actually return to it when you hand control back.

#### Render functions with side effects: renderPrint and renderPlot

The render functions renderPrint() and renderPlot() are slightly different than other render functions, in that they can be affected by side effects in the code block you provide. In renderPrint you can print to the console, and in renderPlot you can plot to the active R graphics device.

With promises, these render functions can work in a similar way, but with a caveat. As you hopefully understand by now, futures execute their code in a separate R process, and printing/plotting in a separate process won’t have any effect on the Shiny output in the original process. These examples, then, are incorrect:

output$summary <- renderPrint({ future_promise({ read.csv(url) %>% summary() %>% print() }) }) output$plot <- renderPlot({
future_promise({
ggplot(df, aes(length, width)) + geom_point()
})
})

Instead, do printing and plotting after control returns back to the original process, via a promise handler:

output$summary <- renderPrint({ future_promise({ read.csv(url) }) %...>% summary() %...>% print() }) output$plot <- renderPlot({
{
ggplot(., aes(length, width)) + geom_point()
}
})

Again, you do need to be careful to make sure that the last expression in your code block is the promise/pipeline; this is the only way the rendering logic can know whether and when your logic has completed, and if any errors occurred (so they can be displayed to the user).

### Observers

Observers are very similar to outputs: you must make sure that the last expression in your code block is the promise/pipeline. Like outputs, observers need to know whether and when they’re done running, and if any errors occured (so they can log them and terminate the user session). The way to communicate this from your async user code is by returning the promise.

Here’s a synchronous example that we’ll convert to async. Clicking the refresh_data action button causes data to be downloaded, which is then saved to disk as cached.rds and also used to update the reactive value data.

data <- reactiveVal(readRDS("cached.rds"))

function(input, output, session) {
observeEvent(input$refresh_data, { df <- read.csv(url) saveRDS(df, "cached.rds") data(df) }) } And the async version: data <- reactiveVal(readRDS("cached.rds")) function(input, output, session) { observeEvent(input$refresh_data, {
future_promise({
saveRDS(df, "cached.rds")
df
}) %...>%
data()
})
}

Note that in this version, we cannot call data(df) inside the future, as this would cause the update to happen in the wrong process. Instead, we use the %...>% operator to perform the assignment back in the main process once the future resolves.

### Reactive expressions

Recall that reactive expressions are used to calculate values, and are cached until they are automatically invalidated by one of their dependencies. Unlike outputs and observers, reactive expressions can be used from other reactive consumers.

Asynchronous reactive expressions are similar to regular (synchronous) reactive expressions: instead of a “normal” value, they return a promise that will yield the desired value; and a normal reactive will cache a normal value, while an async reactive will cache the promise.

The upshot is that when defining an async reactive expression, your code block should return a promise or promise pipeline, following the same rules as reactive outputs. And when calling an async reactive expression, call it like a function like you would a regular reactive expression, and treat the value that’s returned like any other promise.

function(input, output, session) {
data <- eventReactive(input$refresh_data, { read.csv(url) }) filteredData <- reactive({ data() %>% filter(date == input$date)
})

output$table <- renderTable({ filteredData() %>% head(5) }) } And now in async: function(input, output, session) { data <- eventReactive(input$refresh_data, {
})

filteredData <- reactive({
data() %...>% filter(date == input$date) }) output$table <- renderTable({
})
}

## The flush cycle

In the past, Shiny’s reactive programming model has operated using a mostly traditional event loop model. Somewhere many levels beneath shiny::runApp() was a piece of code that looked a bit like this:

while (TRUE) {
# Do nothing until a browser sends some data
# Use the received data to update reactive inputs
session$updateInput(input) # Execute all invalidated outputs/observers flushReact() # After ALL outputs execute, send the results back flushOutputs() } We call this Shiny’s “flush cycle”. There are two important properties to our flush cycle. 1. Only one of the four steps—receiving, updating, reacting, and sending—can be executing a time. (Remember, R is single threaded.) In particular, it’s not possible for inputs to be updated while outputs/observers are running. This is important in order to avoid race conditions that would be all but impossible to defend against. 2. Many outputs may change as a result of a single input value received from the browser, but none of them are sent back to the client until all of the outputs are ready. The advantage of this is a smoother experience for the end-user in most cases. (Admittedly, there has been some controversy regarding this property of Shiny; some app authors would strongly prefer to show outputs as soon as they are ready, or at least to have manual control over this behavior.) While adding async support to Shiny, we aimed to keep these two properties intact. Imagine now that flushReact(), the line that executes invalidated outputs/observers, returns a promise that combines all of the async outputs/observers (i.e. a promise that resolves only after all of the async outputs/observers have resolved). The new, async-aware event loop is conceptually more like this: doEventLoop <- function() { # Do nothing until a browser sends some data input <- receiveInputFromBrowser() # Use the received data to update reactive inputs session$updateInput(input)
# Execute all invalidated outputs/observers
flushReact() %...>% {
# After ALL outputs execute, send the results back
flushOutputs()
# Continue the event loop
doEventLoop()
}
}

The resulting behavior matches the synchronous version of the event loop, in that:

1. No inputs are received from the browser until all pending async outputs/observers have completed. Unlike the synchronous version, this separation is enforced at the session level: if Session A has some async observers that have not finished executing, that only prevents Session A from processing new input values, while new input values from Session B can be handled immediately because they belong to a different session. Again, the goal of keeping input updates separate from output/observer execution is to prevent race conditions, which are even more pernicious to debug and understand when async code is involved.
2. For a given session, no outputs are sent back to the client, until all outputs are ready. It doesn’t matter whether the outputs in question are synchronous, asynchronous, or some combination; they all must complete execution before any can be sent.

format: plain


text:
## Friday, September 13, 2013

### precisely right

Even just for fun, did it ever occur to you ...?

You are precisely right.
Always precisely right.
Even when you're wrong, still you are precisely right.
Any corrective action is precisely right.
Any failure to exercise corrective action is precisely right.

There are consequences, of course, and they too are precisely right ... just like you.
Relax -- you are precisely right.

And it has nothing to do with "right" or "wrong."


text:
# General Relativity at 100

Albert Einstein

On November 25, 1915, Einstein‘s paper on general relativity, Die Feldgleichungen der Gravitation (The Field Equations of Gravity), was published in the Sitzungsberichte der Königlich Preussische Akademie der Wissenschaften. Several scans of the original are available online, with this being a relatively clear and readable scan.  Einstein’s equations definitely had major effects on physics, but they have also led to remarkable mathematics.  Despite rumors to the contrary, Einstein was rather good at mathematics.  Much of his work relies on mathematical derivations of physical results.  An accessible example is his derivation of the equivalence of mass and energy, which is the content of his Gibbs Lecture.  More challenging is his work on the existence of singularities in space-times that contain either mass or charge [first paper, second paper – with Pauli].  Note that the paper with Pauli was published in the Annals of Mathematics.  Indeed, a MathSciNet search turns up 13 papers by Einstein that were published in the Annals.  Not bad for someone reputed to be “bad at math”.

The influence I would like to concentrate on here is the concept of an Einstein manifold.  The definition is quite simple, if you are already conversant in differential geometry:  a Riemannian (or pseudo-Riemannian) manifold is Einstein if the Ricci tensor is proportional to the metric tensor.  That is to say, the (Ricci) curvature is a scalar multiple of the metric.  An important special family of Einstein manifolds is formed by the Kähler-Einstein manifolds, which include the Calabi-Yau manifolds.  Wherever they occur, Einstein manifolds tend to have special properties.  When starting with a manifold without a metric, the goal is often to determine whether it supports an Einstein metric.

There is a great introduction to the subject in the book Einstein Manifolds, by Arthur Besse.  The review of the original edition of the book is appended below.  The book emphasizes compact Einstein manifolds.  Examples of such are few and far between.  The author of the book used to have a standing offer of a meal at a Michelin-starred restaurant for anyone who came up with a genuinely new example.  I don’t know the status of that offer today.  Also, I am not sure how you would collect on it, as Arthur Besse is a pseudonym.

Calabi-Yau manifolds are complex manifolds that are Einstein manifolds, Kähler manifolds, and Ricci flat.  They can also be described as Ricci-flat Kähler manifolds whose first Chern class vanishes. Calabi-Yau manifolds play important roles in mathematical physics, particularly in string theory and mirror symmetry.  A supersymmetric picture of the universe is ten dimensional, having the usual four dimensions of space-time, plus compact Calabi-Yau manifolds “attached” at each point.  (The ten-dimensional space is fibered by Calabi-Yau manifolds over the four-dimensional base space.)  The Calabi-Yau manifolds have three complex dimensions, which means six real dimensions.  In the late 1980s, physicists were trying to generate as many examples of compact Calabi-Yau manifolds as possible.  I was quite impressed to see that some people in Philip Candelas‘s group at the University of Texas had written computer programs to generate possible examples.  This was done without the aid of Maple, Mathematica, or any other computer algebra system.  They wrote code, which generated pages of output (on the old side-punched, 132-column computer paper), with each line being a candidate.   They then used methods of algebraic geometry and representation theory to determine if the candidates were valid examples.

In algebraic geometry, Calabi-Yau manifolds can be viewed as higher-dimensional generalizations of K3 surfaces.  Their existence was conjectured by Eugenio Calabi, first in his talk at the ICM in Amsterdam, then in his paper in a volume honoring Lefschetz.  Their existence was proved by S.-T. Yau in his famous paper in CPAM.  The MathSciNet review of the paper is appended below.  The result is essentially a statement in algebraic geometry, but the proof involves some very serious work on existence of solutions to PDEs, e.g., the complex Monge-Ampère equation.  Applications of geometric analysis to algebraic geometry in this vein continue.  A current example is the work of Xiuxiong Chen, Simon Donaldson, and Song Sun on Kähler-Einstein metrics on Fano manifolds: see MR3194014, with full details in the review of the three-part paper MR3264766, MR3264767, MR3264768.  Several talks at the 2015 Summer Institute in Algebraic Geometry were on this work.

Einstein’s influence in mathematics is truly remarkable.  Searching MathSciNet for items with “Einstein” in the title leads to over 8,000 matches.  Doing the search with “Einstein” anywhere leads to nearly 29,000 matches.  That is quite a legacy.

Happy 100th birthday, General Relativity!  And thank you for all the great mathematics!

MR0867684 (88f:53087)

Besse, Arthur L.
Einstein manifolds.
Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 10. Springer-Verlag, Berlin,1987. xii+510 pp. ISBN: 3-540-15279-2
53C25 (53-02 53C21 53C30 53C55 58D17 58E11)

A Riemannian metric on a smooth manifold $M$ is defined by a positive definite symmetric bilinar form $g$ on each tangent space $T_pM$. Part of the curvature of $g$ is represented by another symmetric bilinear form on $T_pM$, namely the Ricci tensor $r$. The metric is Einstein when $r$ is a constant multiple of $g$; if the constant if zero, $M$ is “Ricci-flat” and a positive definite analogue of a solution to Einstein’s vacuum field equations.
This book is designed to be an exhaustive survey of results concerning Einstein metrics on compact manifolds of dimension at least four, and has its origins in a 1979 symposium held at Espalion in southern France. At that time the recent solution by S. T. Yau and T. Aubin of conjectures of E. Calabi had established the existence of large classes of Kähler-Einstein manifolds whose scalar curvature $s=textrm{trace}_gr$ is nonpositive. A Kähler manifold is one with strongly compatible complex and Riemannian structures, and for example an algebraic hypersurface of degree $m+1$ in the complex projective space $mathbf{C}textrm{P}^m$ was shown to admit a Ricci-flat Kähler metric.
Complementary and more explicit classes of Einstein metrics arise on homogeneous spaces $G/H$. If $G$ is a compact Lie group, any orbit of the adjoint representation admits a canonical Kähler-Einstein metric with $s>0$. In another direction, if $H$ has irreducible isotropy representation, an invariant Riemannian metric $g$ on $G/H$ is forced to be proportional to its Ricci tensor $r$. Further progress towards a classification of homogeneous Einstein manifolds has been made, particularly by M. Wang and W. Ziller . An early observation was that $mathbf{C}textrm{P}^3$ has a nonstandard homogeneous Einstein metric, a fact that may be explained in terms of a Riemannian submersion $picolonmathbf{C}textrm{P}^3to S^4$. Such techniques were exploited by L. Bérard-Bergery to generalize an example due to D. Page of an Einstein metric on the connected sum $mathbf{C}textrm{P}^2,#,overline{mathbf{C}textrm{P}^2}$.
The description of the above examples and methods forms the central part of the book (Chapters 7, 8, 9, 11 out of a total of 16). With the exception of a few difficult proofs, the exposition is self-contained, and contains a wealth of previously unpublished or inaccessible material. The remainder of the book is organized as follows.
A comprehensive exposition of “basic material” precedes a digression into Lorentzian geometry and relativity. Motivation from physics permeates into Chapter 4, which develops the fact that Einstein metrics are the solutions to the Euler-Lagrange equations for stationary points of the integral of the scalar curvature $s$. Some attractive analysis then follows from the question of which functions arise as scalar curvatures, and which symmetric bilinear tensors are Ricci tensors. Chapter 6 is an examination of topological consequences of the Einstein condition, the most successful being the inequality $chi(M)geqfrac 32|tau(M)|$ relating the Euler characteristic and the signature of a compact oriented Einstein 4-manifold, and resulting from successive work of M. Berger, J. A. Thorpe, and N. J. Hitchin . Other techniques give conditions for the existence of Einstein metrics with $s>0$, but it is still unknown whether there is a manifold of dimension five or more admitting no Einstein metric.
Later chapters cover relevant, but more specialised topics. A sequel to the variational approach is provided by a study of deformations of Einstein metrics, and work of N. Koiso on the moduli space problem. Three chapters which could be read consecutively deal respectively with holonomy groups, self-duality in four dimensions, and quaternionic manifolds. The last of these is followed by a rather brief report on important constructions in the noncompact case. Finally there is a discussion of generalizations of the Einstein condition; interesting though these are, the reader may be left in agreement with the author’s thesis that Einstein metrics are the nicest sort. The book includes an Appendix on Sobolev spaces and elliptic operators, and an Addendum of results on five topics, too recent to make it into the main text. The fact that four of these topics are related to Kähler-Einstein manifolds is indicative of the ever-developing links between complex and Riemannian geometry.
The book under review serves several purposes. It is an efficient reference book for many fundamental techniques of Riemannian geometry. On the other hand, despite its length, the reader will have no difficulty in getting the feel of its contents and discovering excellent examples of the interaction of geometry with partial differential equations, topology, and Lie groups. Above all, the book provides a clear insight into the scope and diversity of problems posed by its title.

Reviewed by S. M. Salamon

MR0480350 (81d:53045)
Yau, Shing Tung
On the Ricci curvature of a compact Kähler manifold and the complex Monge-Ampère equation. I.
Comm. Pure Appl. Math. 31 (1978), no. 3, 339–411.
53C55 (32C10 35J60)

This remarkable paper establishes several related results which are of fundamental importance in the study of complex manifolds. These results, the main points of which were conjectured more than twenty years ago by E. Calabi [Proceedings of the International Congress of Mathematicians (Amsterdam, 1954), Vol. 2, pp. 206–207, Noordhoff, Groningen, 1954], have to do with the existence of Kähler metrics with certain special properties on compact Kähler manifolds. The results are established by reducing them to questions in nonlinear partial differential equations of Monge-Ampère type which are then treated by a continuity method involving difficult a priori estimates. The methods and results on partial differential equations have great interest in themselves in addition to their importance as the mechanism of establishing the Calabi conjectures and some similar but more general geometric results.
To discuss the contents of the paper more specifically: Let $M$ be a compact Kähler manifold with Kähler metric $g$. Then it is a well-known result of S. S. Chern that the Ricci form (= in local coordinate representation
$$(-surd(-1)/(2pi))sum_{i,j}left(partial^2[logtext{}det(g_{soverline t})]/partial z^ipartial z^{overline j}right)dz^iwedge doverline z^j=\ (surd(-1)/(2pi))sum_{i,j}R_{ioverline j}dz^iwedge doverline z^j,$$ where$sum_{i,j}R^{ioverline j}dz^iotimes doverline z^j$ is the Ricci tensor) is a closed real $(1,1)$ form whose cohomology class is the first Chern class of $M$. In particular, this cohomology class depends only on the complex structure of $M$ and not on the choice of Kähler metric $g$. The conjecture [Calabi, op. cit.], which is proved in the paper under review, was that the converse held: Every closed real $(1,1)$ form whose cohomology class is the first Chern class of $M$ is the Ricci form of some Kähler metric on $M$. More precisely, Calabi conjectured that there is a $C^infty$ function $varphicolon Mrightarrow{bf R}$ such that $tilde g={}_{text{df}}sum_{i,j}(g_{ioverline j}+partial^2varphi/partial z^ipartialoverline z^j)dz_iotimes doverline z_j$ is a positive definite Kähler metric the Ricci form of which is the given form; he proved that at most one metric of this form with given Ricci form exists, and that in fact $varphi$ is uniquely determined up to an additive constant by the Ricci form of the metric $tilde g$ [Calabi, Algebraic geometry and topology, pp. 78–89, Princeton Univ. Press, Princeton, N.J., 1957; MR0085583 (19,62b)]. A second conjecture of Calabi [op. cit., 1954] concerned the existence of Einstein-Kähler metrics. A Kähler metric $g$ is by definition an Einstein-Kähler metric if its Ricci form is a multiple at each point of the Kähler form $omega$ of the metric $g$. This condition is of course automatic by type considerations in complex dimension one. In complex dimension two or higher, it is a standard result that the multiple must be constant, so that by replacing $g$ by a positive constant multiple it is sufficient to consider the cases $R=pmomega$ or $Requiv 0$. The case $Requiv 0$ is a special case of the first conjecture: that there is a Kähler metric with Ricci form identically zero if (and only if) the first Chern class of the manifold is zero. If $R$ is to be $-omega$, then the first Chern class of $M$ must be negative or, equivalently, the canonical bundle of $M$ must be ample. The present paper establishes the existence of an Einstein-Kähler metric with $R=-omega$ on any compact complex manifold with ample canonical bundle. (A theorem of Nakano that negativity of the first Chern class implies nonexistence of nontrivial holomorphic vector fields relates this result to the original form of Calabi’s conjecture for this case.) This metric is canonical in the sense that it is uniquely determined by the complex structure of $M$. (Some results which are related to the Calabi conjectures and to which reference is made in the present article are given in the works of T. Aubin; these and their relationship to the present paper are discussed in the review of Aubin’s paper [53047 below].)
The proofs of these results are far too lengthy and intricate to treat in any detail in a review. But it is possible to indicate how the questions are transformed to nonlinear partial differential equations problems: As before, let $M$ be a compact Kähler manifold with Kähler metric $g$ and let$(surd(-1)/(2pi))sum_{i,j}R_{ioverline j}dz_iwedge doverline z_j$ be the Ricci form of $g$. Suppose that $(surd(-1)/(2pi))sum_{i,j}tilde R_{ioverline j}dz_iwedge doverline z_j$ is a closed $(1,1)$ form which also represents the first Chern class of $M$. By standard results, there is then a (smooth) function $F$ on$M$ such that $tilde R_{ioverline j}-R_{ioverline j}=-partial^2F/partial z^idoverline z^j$. If $sumtilde R_{ioverline j}dz_iotimes doverline z_j$ is in fact the Ricci tensor of a Kähler metric $tilde g$ then $tilde R_{ioverline j}=-(partial^2/partial z^ipartialoverline z^j)log(dettilde g_{soverline t})$. From the maximum principle one sees that $det(tilde g_{soverline t})=C(exp F)det(g_{soverline t})$, where $C$ is a constant. To make a unique choice of $tilde g$, one seeks $tilde g$ in the form $tilde g_{ioverline j}=g_{ioverline j}+(partial^2varphi/partial z^ipartialoverline z^j)$. Then the problem is reduced to solving the equation for $varphicolondet(g_{ioverline j}+partial^2varphi/partial z^ipartialoverline z^j)=C(exp F)det(g_{st})$, where the constant $C=text{Vol}(M)/int_Mexp F$. The solution of this is unique [Calabi, op. cit., 1957]. It is natural in this situation to attempt the solution of the equation by the continuity method, where the family of equations to which the method is to be applied is obtained by varying $F$. Specifically, fix $kgeq 3$ and $alphain(0,1]$. Let $S=$ {$tin[0,1]$: the equation $det(g_{ioverline j}+(partial^2varphi)/(partial z^ipartialoverline z^j))det(g_{ioverline j})^{-1}=text{Vol}(M)[intexp{tF}]^{-1}exp{tF}$ has a solution in $C^{k+1,alpha}(M)$}. Then clearly $0in S$ and if $1in S$ then one has solved the equation originally considered. So now it suffices to show that $S$ is open and closed in $[0,1]$. That $S$ is open can be established by applying the Banach space version of the implicit function theorem (because of ellipticity, there are no technical difficulties involving derivative loss). This step was carried out by Calabi. To see that $S$ is closed, one tries to find a solution for the value $t_0inoverline S$ by taking the limit of a (sub)sequence of the solutions $varphi_{t_i}$ of the equations for $t_iin S$ with $t_irightarrow t_0$, where for normalization one assumes $int_Mvarphi_{t_i}=0$. (This normalization actually makes each $varphi_{t_i}$ uniquely determined.) To be sure that such a limit exists, one must obtain a priori estimates on the $varphi_{t_i}$ and their derivatives. To obtain estimates that are sufficient to allow the Schauder theory to apply (i.e. estimates up to third order derivatives) is difficult. The third derivative estimates can be obtained (in the presence of the lower order estimates) by a process similar to that used by Calabi in a slightly different context (the real Monge-Ampère equation: [Calabi, Michigan Math. J. 5 (1958), 105–126; MR0106487 (21 #5219)]). But the obtaining of the estimates up to second order involves an intricate, new procedure. Once these estimates are obtained, the Schauder theory allows the proof to be completed by the continuity method.
Similar considerations imply the existence of Einstein-Kähler metrics on any compact complex manifold $M$ with ample canonical bundle (such a manifold is automatically projective algebraic and hence a Kähler manifold). Indeed by hypothesis there is a closed positive $(1,1)$ form $surd(-1)sum_{i,j}g_{ioverline j}dz^iwedge doverline z^j$, which represents the negative of the first Chern class of $M$. This form is the Kähler form of a Kähler metric $g$. By a theorem of Chern as before, the first Chern class of $M$ is also represented by $-partialoverlinepartiallogtext{}det(g_{ioverline j})$ (= the Ricci form of $g$). So there is a smooth function $f$ with $partialoverlinepartiallogtext{}det(g_{ioverline j})=surd(-1)sum g_{ioverline j}dz^iwedge doverline z^j+partialoverlinepartial f$. One seeks a function $varphi$ such that $tilde g=sum(g_{ioverline j}+(partial^2varphi/partial z^ipartialoverline z^j))dz_iotimes dz_j$ is a Kähler metric and such that $det(g_{ioverline j}+partial^2varphi/partial z^ipartialoverline z^j)=exp(varphi-f)det(g_{ioverline j})$. A brief calculation then shows that the Ricci tensor of $tilde g$ is $-tilde g$. To find $varphi$, one again uses the continuity method to solve the partial differential equation given. (Actually, a somewhat more general equation is solved.) The metric $tilde g$ is shown to be uniquely determined; i.e., it depends only on the complex structure of $M$.
Numerous technical refinements of the results stated, some of them of immediate importance in applications to geometry, are given. Detailed discussion of these refinements must be omitted here. Although the author does not discuss applications in this paper, it would be inappropriate to conclude this review without noting that not only are the results given in this article of great interest in themselves but also they have numerous important applications in geometry. These are discussed in part in a previous article of the author [Proc. Nat. Acad. Sci. 74 (1977), no. 5, 1798–1799; MR0451180 (56 #9467)]. They include: the existence of Ricci flat but nonflat compact manifolds, the uniqueness of complex structure on complex projective 2-space, and the proof that any complex surface that is oriented homotopic to a surface covered by the ball is biholomorphic to the latter surface. The results of the presently reviewed article represent a major advance in differential and transcendental algebraic geometry. These results and the methods by which they are obtained will no doubt become a permanent part of the investigative techniques of these areas.
{This review was received in April 1979.}

Reviewed by Robert E. Greene


text:
# Computer Hard Disks

The computer hard disk is a sealed unit in a computer that stores data on a magnetic coating applied to the surface of circular platters that spin like a record. The platters are constructed on a base of aluminum or glass (both nonferromagnetic), which makes them rigid - hence the term hard disk. Since the unit is sealed, the internal platters and components are inaccessible, and a "crash" (a term applied to the loss of data from a disk or the malfunction thereof) usually requires that the entire unit be replaced.
Hard disks are currently available with diameters from less than $1$ in. to $5 {1 \over 4}$ in., with the $3 {1 \over 2}$ in. the most popular for today's desktop units. Lap-top units typically use $2 {1 \over 2}$ in. All hard disk drives are often referred to as Winchester drives, a term first applied in the 1960s to an IBM drive that had 30 MB [a byte is a series of binary bits (0s and 1s) representing a number, letter, or symbol] of fixed (non-accessible) data storage and 30 MB of accessible data storage. The term Winchester was applied because the 30-30 data capacity matched the name of the popular 30-30 Winchester rifle.
The magnetic coating on the platters is called the media and is of either the oxide or the thin-film variety. The oxide coating is formed by first coating the platter with a gel containing iron-oxide (ferromagnetic) particles. The disk is then spun at a very high speed to spread the material evenly across the surface of the platter. The resulting surface is then covered with a protective coating that is made as smooth as possible. The thin-film coating is very thin, but durable, with a surface that is smooth and consistent throughout the disk area. In recent years the trend has been toward the thin-film coating because the read/write heads (to be described shortly) must travel closer to the surface of the platter, requiring a consistent coating thickness. Recent techniques have resulted in thin-film magnetic coatings as thin as one-millionth of an inch.
The information on a disk is stored around the disk in circular paths called tracks or cylinders, with each track containing so many bits of information per inch. The product of the number of bits per inch and the number of tracks per inch is the Areal density of the disk, which provides an excellent quantity for comparison with early systems and reveals how far the field has progressed in recent years. In the 1950s the first drives had an Areal density of about 2 kbits/in.2 compared to today's typical 4 Gbits/in., an incredible achievement; consider 4,000,000,000,000 bits of information on an area the size of the face of your watch. Electromagnetism is the key element in the writing of information on the disk and the reading of information off the disk.
Fig. 1: Hard disk storage using a U-shaped electromagnet write head
In its simplest form the write/read head of a hard disk (or floppy disk) is a U-shaped electromagnet with an air gap that rides just above the surface of the disk, as shown in Fig. 1. As the disk rotates, information in the form of a voltage with changing polarities is applied to the winding of the electromagnet. For our purposes we will associate a positive voltage level with a 1 level (of binary arithmetic) and a negative voltage level with a 0 level. Combinations of these 0 and 1 levels can be used to represent letters, numbers, or symbols. If energized as shown in Fig. 1 with a 1 level (positive voltage), the resulting magnetic flux pattern will have the direction shown in the core. When the flux pattern encounters the air gap of the core, it jumps to the magnetic material (since magnetic flux always seeks the path of least reluctance and air has a high reluctance) and establishes a flux pattern, as shown on the disk, until it reaches the other end of the core air gap, where it returns to the electromagnet and completes the path. As the head then moves to the next bit sector, it leaves behind the magnetic flux pattern just established from the left to the right. The next bit sector has a 0 level input (negative voltage) that reverses the polarity of the applied voltage and the direction of the magnetic flux in the core of the head. The result is a flux pattern in the disk opposite that associated with a 1 level. The next bit of information is also a 0 level, resulting in the same pattern just generated. In total, therefore, information is stored on the disk in the form of small magnets whose polarity defines whether they are representing a 0 or a 1. Now that the data have been stored, we must have some method to retrieve the information when desired. The first few hard disks used the same head for both the write and the read functions. In Fig. 2(a), the U-shaped electromagnet in the read mode simply picks up the flux pattern of the current bit of information. Faraday's law of electromagnet induction states that a voltage is induced across a coil if exposed to a changing magnetic field. The change in flux for the core in Fig. 2(a) is minimal as it passes over the induced bar magnet on the surface of the disk. A flux pattern is established in the core because of the bar magnet on the disk, but the lack of a significant change in flux level results in an induced voltage at the output terminals of the pickup of approximately 0 V, as shown in Fig. 2(b) for the readout waveform.
(a)
(b)
Fig. 2: Reading the information off a hard disk using a U-shaped electromagnet.
A significant change in flux occurs when the head passes over the transition region so marked in Fig. 2(a). In region a the flux pattern changes from one direction to the other-a significant change in flux occurs in the core as it reverses direction, causing a measurable voltage to be generated across the terminals of the pickup coil as dictated by Faraday's law and indicated in Fig. 2(b). In region b there is no significant change in the flux pattern from one bit area to the next, and a voltage is not generated, as also revealed in Fig. 2(b). However, when region c is reached, the change in flux is significant but opposite that occurring in region a, resulting in another pulse but of opposite polarity. In total, therefore, the output bits of information are in the form of pulses that have a shape totally different from the read signals but that are certainly representative of the information being stored. In addition, note that the output is generated at the transition regions and not in the constant flux region of the bit storage.
In the early years, the use of the same head for the read and write functions was acceptable; but as the tracks became narrower and the seek time (the average time required to move from one track to another a random distance away) had to be reduced, it became increasingly difficult to construct the coil or core configuration in a manner that was sufficiently thin with minimum weight. In the late 1970s IBM introduced the thin film inductive head, which was manufactured in much the same way as the small integrated circuits of today. The result is a head having a length typically less than 1/10 in., a height less than 1/50 in., and minimum mass and high durability. The average seek time has dropped from a few hundred milliseconds to 6 ms to 8 ms for very fast units and 8 ms to 10 ms for average units. In addition, production methods have improved to the point that the head can "float" above the surface (to minimize damage to the disk) at a height of only 5 micro-inches or 0.000005 in. Using a typical lap-top hard disk speed of 3600 rpm (as high as 7200 rpm for desktops) and an average diameter of 1.75 in. for a 3.5-in. disk, the speed of the head over the track is about 38 mph. Scaling the floating height up to 1/4 in. (multiplying by a factor of 50,000), the speed would increase to about $1.9 \times 10^6$ mph. In other words, the speed of the head over the surface of the platter is analogous to a mass traveling 1/4 in. above a surface at 1.9 million miles per hour, all the while ensuring that the head never touches the surface of the disk-quite a technical achievement and amazingly enough one that perhaps will be improved by a factor of 10 in the next decade. Incidentally, the speed of rotation of floppy disks is about 1/10 that of the hard disk, or 360 rpm. In addition, the head touches the magnetic surface of the floppy disk, limiting the storage life of the unit. The typical magnetizing force needed to lay down the magnetic orientation is 400 mA-turn (peak-to-peak). The result is a write current of only 40 mA for a 10-turn, thin-film inductive head.
Although the thin-film inductive head could also be used as a read head, the magneto-resistive (MR) head has improved reading characteristics. The MR head depends on the fact that the resistance of a soft ferromagnetic conductor such as permolloy is sensitive to changes in external magnetic fields. As the hard disk rotates, the changes in magnetic flux from the induced magnetized regions of the platter change the terminal resistance of the head. A constant current passed through the sensor displays a terminal voltage sensitive to the magnitude of the resistance. The result is output voltages with peak values in excess of 300 V, which exceeds that of typical inductive read heads by a factor of 2 or 3:1.
Further investigation will reveal that the best write head is of the thin-film inductive variety and that the optimum read head is of the MR variety. Each has particular design criteria for maximum performance, resulting in the increasingly common dual-element head, with each head containing separate conductive paths and different gap widths. The Areal density of the new hard disks will essentially require the dual-head assembly for optimum performance.
As the density of the disk increases, the width of the tracks or cylinders will decrease accordingly. The net result will be smaller heads for the read/write function, an arm supporting the head that must be able to move into and out of the rotating disk in smaller increments, and an increased sensitivity to temperature effects which can cause the disk itself to contract or expand. At one time the mechanical system with its gears and pulleys was sensitive enough to perform the task. However, today's density requires a system with less play and with less sensitivity to outside factors such as temperature and vibration. A number of modern drives use a voice coil and ferromagnetic arm as shown in Fig. 3. The current through the coil will determine the magnetic field strength within the coil and will cause the supporting arm for the head to move in and out, thereby establishing a rough setting for the extension of the arm over the disk.
Fig. 3: Disk drive with voice coil and ferromagnetic arm.
It would certainly be possible to relate the position of the arm to the applied voltage to the coil, but this would lack the level of accuracy required for high-density disks. For the desired accuracy, a laser beam has been added as an integral part of the head. Circular strips placed around the disk (called track indicators) ensure that the laser beam homes in and keeps the head in the right position. Assuming that the track is a smooth surface and the surrounding area a rough texture, a laser beam will be reflected back to the head if it's on the track, whereas the beam will be scattered if it hits the adjoining areas. This type of system permits continuous recalibration of the arm by simply comparing its position with the desired location-a maneuver referred to as "recalibration on the fly."
As with everything, there are limits to any design. However, in this case, it is not because larger disks cannot be made or that more tracks cannot be put on the disk. The limit to the size of hard drives in PCs is set by the BIOS (Basic Input Output System) drive that is built into all PCs. When first developed years ago, it was designed around a maximum storage possibility of 8.4 gigabytes. At that time this number seemed sufficiently large to withstand any new developments for many years to come. However, 8-gigabyte drives and larger are now becoming commonplace, with lap-tops averaging 20 gigabytes and desktops averaging 40 gigabytes. The result is that mathematical methods had to be developed to circumvent the designed maximum for each component of the BIOS system. Fundamentally, the maximum values for the BIOS drive are the following:
• Cylinders (or tracks) 1024


text:
# Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?

This problem can be turned into a two state distinguishability problem by considering the problem of distinguishing $\rho_A$ from $\rho_{B} = \frac{1}{N-1}\sum_{i\neq A}\rho_i$.

I know for two quantum states the problem has a nice solution in terms of the trace distance between the states when you minimize the maximum probability of error rather than the minimizing the average probability of error, and I was hoping that there might be something similar for this case. It is of course possible to write the probability in terms of an optimization over POVMs, but I am hoping for something where the optimization has already been performed.

I know there is a huge literature on the distinguishability of quantum states, and I've been reading through a lot of papers over the last few days trying to find the answer to this question, but I'm having trouble finding the answer to this particular variation of the problem. I'm hoping someone who knows that literature better can save me some time.

Strictly speaking, I don't need the exact probability, a good upper bound would do. However, the difference between any one state and the maximally mixed state is quite small, so the bound would have to be useful in that limit.

• Because the probability of correct answer is the maximum value of a semidefinite program, it is often useful to consider the dual to get an upper bound. – Tsuyoshi Ito Jun 16 '12 at 18:13
• @TsuyoshiIto: Indeed, but I was guessing that this problem has been well studied and that there might be a canned result. – Joe Fitzsimons Jun 16 '12 at 21:53
• Do you know if the analogous questions for classical probability distributions has a nice answer? The "trace distance" result you mention is a generalization of the use of "statistical distance" (a.k.a. "total variation distance") for classical distributions. [In the classical case, the natural strategy is to pick the distribution most likely to have generated a particular output. You can write down a closed form for its success probability, though I don't know if it can be expressed in terms of a simple quantity (such as the average distance between the distributions).] – Adam Smith Jun 17 '12 at 1:21
• @AdamSmith: It seems classically you can just weight each distribution by its probability of occurring and then pick the one most likely to give the result you observe. – Joe Fitzsimons Jun 17 '12 at 6:50

However, there are several known upper and lower bounds on the probability of error (i.e. 1 minus the average success probability). In terms of pairwise fidelities, the probability of error in your setting is known to be lower bounded by $\frac{1}{N^2} \sum_{i>j} F(\rho_i,\rho_j)$, and upper bounded by $\frac{2}{N} \sum_{i>j} F(\rho_i,\rho_j)^{1/2}$.
There is also another lower bound known in terms of trace distance: $\frac{1}{2}(1 - \frac{1}{N(N-1)} \sum_{i>j} tr|\rho_i-\rho_j|)$, which reduces to the exact Helstrom bound in the case $N=2$. See this paper for a comparison of all of these, and some other bounds too. Note that all of these bounds hold in the average-case setting where there is a prior probability distribution on the states.
• Actually, the fidelity lower bound also seems to max out at 1/2. I'm hoping for something stronger, since I want to prove the probability of error is something like $1-\epsilon$ for very small $\epsilon$. – Joe Fitzsimons Jun 18 '12 at 11:05


text:
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB444100.000%

## 문제

Long ago, in the land of Cartesia, there ruled the Rectangle Empire. The Empire was large and prosperous, and it had great success with expanding its territory through frequent conquests. The citizens of this ancient civilization followed many curious customs. Unfortunately, the significance of these are now shrouded in mystery.

The Rectangle Empire operated under a system of rectangular districts. These districts were carefully managed to meet three special criteria.

1. The Empire’s territory is divided into districts such that each piece of land controlled by the Empire belongs to exactly one district.
2. The boundaries of the districts, when viewed on a map, must be rectangles such that the length of the longer side of the rectangle is twice the length of the shorter side.
3. The side lengths of the districts must be integers, when measured in Ξ (note that Ξ was the primary unit of length in the Rectangle Empire).

When the empire was first established, it consisted of a single district. Since then, the empire has gained additional districts through conquest of neighbouring regions. Whenever the empire gained control over a new region of land, they always established a single new district using that exact land. This means that the empire was always mindful about the geometric properties of the land they were hoping to conquer. You can assume that no two of these conquests occurred at the same time.

The addition of new districts was the only way that the boundaries of the empire ever changed. Furthermore, each district, once added, was never modified or merged with another.

The final, most important tradition of the Rectangle Empire was to make sure that the overall territory of the empire was always a rectangle, though it did not necessarily need to satisfy the 2:1 ratio for the side lengths that individual districts satisfy.

Recently, archeologists have discovered that at one point in time, the empire had dimensions N by M (measured in Ξ). You need not be alarmed if these numbers are very large; after all, Cartesia is an infinite plane. Your task is to estimate the number of districts in the empire when it was at this size. Over all possible ways that the empire was founded and expanded, what is the minimum and maximum number of districts?

## 입력

The input will be a single line, containing two integers N and M (1 ≤ N, M ≤ 108).

For 5 of the 25 marks available, N, M ≤ 1000.

For an additional 8 of the 25 marks available, N, M ≤ 106.

## 출력

Output a single line, containing the minimum number of districts, followed by a space, followed by the maximum number of districts.

## 예제 입력 1

10 6

## 예제 출력 1

5 8

## 힌트

Explanation of Output for Sample Input

The illustrations below show how this minimum and maximum number of districts could have been achieved. Districts are labelled #1, #2, #3, ... giving the order in which they were added to the region. The dimensions of each district is shown in brackets as (k × 2k) or (2k × k):

## 출처

• 데이터를 추가한 사람: xiaowuc1


text:
### Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate

Schlichting S, Skokov V (2020)
Physics Letters B 806: 135511.

Zeitschriftenaufsatz | Veröffentlicht | Englisch

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor*in
Abstract / Bemerkung
We perform a numerical study of higher order saturation corrections to the dilute-dense approximation for multi-particle production in high-energy hadronic collisions in the framework of the Color Glass Condensate. We compare semi-analytical results obtained by performing a leading order expansion in the dilute field of the projectile with numerical simulations of the full Classical Yang-Mills dynamics for a number of phenomenologically relevant observables. By varying the saturation momentum of the target and the projectile, we establish the regime of validity of the dilute-dense approximation and assess the magnitude and basic features of higher order saturation corrections. In particular, we find that dilute-dense approximation faithfully reproduces dense-dense results if restricted to the range of its validity.
Stichworte
Nuclear and High Energy Physics
Erscheinungsjahr
2020
Zeitschriftentitel
Physics Letters B
Band
806
Art.-Nr.
135511
ISSN
0370-2693
Page URI
https://pub.uni-bielefeld.de/record/2943830

### Zitieren

Schlichting S, Skokov V. Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate. Physics Letters B. 2020;806: 135511.
Schlichting, S., & Skokov, V. (2020). Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate. Physics Letters B, 806, 135511. doi:10.1016/j.physletb.2020.135511
Schlichting, S., and Skokov, V. (2020). Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate. Physics Letters B 806:135511.
Schlichting, S., & Skokov, V., 2020. Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate. Physics Letters B, 806: 135511.
S. Schlichting and V. Skokov, “Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate”, Physics Letters B, vol. 806, 2020, : 135511.
Schlichting, S., Skokov, V.: Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate. Physics Letters B. 806, : 135511 (2020).
Schlichting, Sören, and Skokov, V. “Saturation corrections to dilute-dense particle production and azimuthal correlations in the Color Glass Condensate”. Physics Letters B 806 (2020): 135511.

Open Data PUB

### Quellen

arXiv: 1910.12496

Inspire: 1761438


text:
## gini ratio

Imagine an economy with only two people. Larry earns $20,000 per year, while Roger earns$80,000 per year. As shown in the following figure, the Lorenz curve for this two-person economy consists of two line segments. The first runs from the origin to point a, while the second runs from point a to point b.

b. What would the Gini ratio be if the government taxed $20,000 away from Roger and gave it to Larry? (Hint: The figure will change.) c. Start again with Larry earning$20,000 per year and Roger earning \$80,000 per year. What would the Gini ratio be if both their incomes doubled?

How much has the Gini ratio changed from before the doubling in incomes to after the doubling in incomes?


text:
# A triangle has sides A, B, and C. Sides A and B are of lengths 9 and 7, respectively, and the angle between A and B is (7pi)/8 . What is the length of side C?

Nov 6, 2016

$\text{C} = 15.7$

#### Explanation:

To answer this question, we have to use the law of cosines.

"C"^2="A"^2+"B"^2-2"AB"cos("c")=81+49-126cos(7/8pi) =246.4

$\text{C} = \sqrt{264.4} = 15.7$

Nov 6, 2016

Cosine rule (rearranged for c) = ${c}^{2} = {a}^{2} + {b}^{2} - 2 a b \cdot \cos C$
$= c = \sqrt{{9}^{2} + {7}^{2} - 2 \cdot 9 \cdot 7 \cdot \cos \left(\frac{7 \pi}{8}\right)}$


text:
# One dit is equal to ___________

This question was previously asked in
BSNL JE (TTA) 25 September 2016 Shift 2 Paper
View all BSNL TTA Papers >
1. 1.14 bits
2. 3.32 bits
3. 1.17 bits
4. none of these

Option 2 : 3.32 bits
Free
BSNL JE (TTA) 25 September 2016 Shift 1 Paper
398
200 Questions 200 Marks 180 Mins

## Detailed Solution

Base b = 10: the unit is called decimal digit or decit, or dit, and is equal to

$${\log _2}10 \approx {\rm{\;}}3.322)$$ bits.

Base b = e, the base of natural logarithms: the unit is called a nat or nit and is equal to $${\log _2}{\rm{e}} \approx {\rm{\;}}1.443)$$ bits.