Friday, February 14, 2014

A map of the universe

If you'd be asked to tell what a map of the universe looks like, I'm pretty sure you'd imagine something on a dark background, with many dots representing planets, and shaded areas corresponding to galaxies. That map of the universe, drawn by Gabriel Conant,  a graduate student at Berkeley,  is of more or less like that. Except that dots are mathematical theories, and galaxies correspond to some stability properties defined in model theory.

Here theories have esoteric nicknames, such as ACF, ACVF, SCF$_p^n$, or ``universal graph omitting a bowtie'' (an homage to Tom S. ? :-)), and properties have even more esoteric nicknames — NIP, o-minimal, NSOP$_{n+1}$, or superstable.  To make it something more than an enjoyable invitation au voyage, Gabriel indicated important specific examples, with their definitions and references.

By the way, this is also a beautiful illustration of the power of HTML5.

Saturday, February 1, 2014

Wadada Leo Smith: Ten Freedom Summers

Last Saturday (January 25th), I attended a concert by trumpetist Wadada Leo Smith in Vitry/Seine, within the Sons d'hiver festival, which serves as a pretext for this blog entry.

The first part featured the Anti Pop Consortium's machine-player HPrizm, accompanied by improvisers David Virelles (piano), Steve Lehman (saxophone) and Wadada Leo Smith (trumpet), as well by Emanuuel Pidre (visuals). I found this part a bit bland. HPrizm's music lacked inspiration, rhythm, and although the improvisers are remarkable musicians, it was probably difficult for them to build on a lame material. Steve Lehman saved most of it, I think, because his playing is very lyrical, and quite dense, so that he could made the music.

The second part was Wadada Leo Smith's Ten Freedom Summers — well, only a part of it, although they played for almost two hours.  Ten Freedom Summers is the title of a monumental series of compositions by Wadada Leo Smith: 19 pieces, lasting for 4 hours and a half, depicting those moments of American history where African american people fought for Freedom. The first piece,  “Dred Scott, 1857” recalls the story of Dred Scott, a slave who filed a suit at the Supreme Court to be able to buy his freedom, and lost, when the Supreme court ruled (1857) that people of African origin, whether slave or free, were not citizens of the United States —anyway, Scott had been freed the very same year by his new owner. The second piece is about the Montgomery bus boycott initiated by Rosa Parks in 1944. Two pieces are also devoted to the US presidents John F. Kennedy and Lyndon Johnson, celebrating the New Frontier, and the Civil Rights act of 1964.

I had been introduced to Wadada Leo Smith's music thanks to France Musique program Open Jazz, when Alex Dutilh aired the piece “Kulture of Jazz”, from the Kulture Jazz CD. Most of the pieces of that disc are evocations of jazz through some prominent figures of jazz (Louis Armstrong, Billie Holiday, John Coltrane, Albert Ayler), African literature (Ayl Kwel Armah), or his personal life (Sarah Brown-Smith-Wallace). The “K” in the title, which reminds me of the Klan, already emphasized the fact that jazz is an African-american music of emancipation. That is the music that black people played, but didn't have the right to listen to.

In Kulture Jazz, Wadada Leo Smith is the only credited musician. He mostly plays the trumpet, an instrument that truly belongs to jazz music (although it is slightly less heared these days), but he also sings, plays percussions, as well as koto, a rarely heard instrument in this context!

For Ten Freedom Summers, he combines a jazz quartet (trumpet, bass, drums and piano) and the Southwest Chamber Ensemble, a 9-musician strings combo. The combo that was initially announced for the concert was Smith's Golden quartet (with Anthony Davis, piano; John Lindberg, bass; Pheeroan akLaff, drums), except that the bassist had broken his wrist and could not play. He was thus replaced by Ashley Waters (from the Southwest Chamber Ensemble) on cello. Consequently, but that's probably one of the miracles allowed for by improvised music, the concert sounded pretty much like the recorded music.

Anyway, both Kulture Jazz and Ten Freedom Summers are very different from other jazz pieces devoted to the civil rights movements that I know (such as Max Roach's Freedom Now. We Insist! whose “Triptych: Prayer/Protest/Peace” is one of the rare jazz pieces that made me cry, or from Charles Mingus's “Fables of Faubus”).

First, the music sounds different. For example, there is no rhythm section in Kulture Jazz, and almost nothing as such in Ten Freedom Summers. And the pieces are definitely not built on the classical form (rhythmic/harmonic) we're now used to, either from listening to classical music, or from blues, or from the modal pieces played by Miles Davis, John Coltrane and others in the 50s-60s.  Maybe not unlike latter pieces by Coltrane (Love Supreme, or Interstellar Space), Wadada Leo Smith's music is an abstract meditation about the place of an African-american musician in History.

Then, although some parts of the concert seemed to be improvised, it all looked as if they played the music as it is written on a score. This was the more surprising for the drummer who, most always in jazz music, is left to imagining by himself how he should bring his playing to the music being created. (When drummers have scores, that's rarely drum scores, but more often that of the bass player, or simply the main theme with the chords changes.)

Even Pheeroan akLaff was obviously playing the drums as written on the score, but the compositions gave him a quite interesting role in the development of the music. Wadada Leo Smith had written long solos for the drums which began or ended the pieces. In fact, since the group that night had no bass player, but a cellist who played with the bow — anyway, Lindberg mostly plays with the bow on the CD too — the other musicians are not given the explicit harmonic/rhythmic pattern that a “walking bass” can impose on the music, so there's probably no point for the drummer to play a definite swing rhythm, which akLaff did not do.

And within Wadada Leo Smith's mostly meditative music, that was akLaff's playing — sometimes forceful, or with traces of military marches — that reminded us that Freedom is a fight.

An everyday-fight.

Thursday, January 9, 2014

Radon measures form a sheaf for a natural Grothendieck topology on topological spaces

First post of the year, so let me wish all of you a happy new year!

Almost two years ago, Antoine Ducros and I released a preprint about differential forms and currents on Berkovich spaces. We then embarked in revising it thoroughly; unfortunately, we had to correct a lot of inaccuracies, some of them a bit daunting. We made a lot of progress and we now have a much clearer picture in mind. Fortunately, all of the main ideas remain the same.

A funny thing emerged, which I want to explain in this blog.

One of our mottos was to define sheaves of differential forms, or of currents. Those differential forms were defined in two steps : by definition, they are locally given by tropical geometry, so we defined a presheaf of tropical forms, and passed at once to the associated sheaf. What we observed recently is that it is worth spending some time to study the presheaf of tropical forms.

Also, Grothendieck topologies play such an important rôle in analytic geometry over non-archimedean fields; this is obvious for classical rigid spaces, but they are also important in Berkovich geometry, in particular if you want to care about possibly non-good spaces for which points may not have a neighborhood isomorphic to an affinoid space. So it was natural to sheafify the presheaf of tropical forms for the G-topology, giving rise to a G-sheaf of G-forms.

Now, every differential form of maximal degree $\omega$ on a Berkovich space $X$ gives rise to a measure on the topological space underlying $X$. Our proof of this is a bit complicated, and was made more complicated by the fact that we first tried to define the integral $\int_X \omega$, and then defined $\int_X f\omega$ for every smooth function $f$, and then got $\int_X f\omega$ for every continuous function with compact support $f$ by approximation, using a version of the Stone-Weierstrass theorem in our context.

In the new approach, we directly concentrate on the measure that we want to construct. For G-forms, this requires to glue measures defined locally for the G-topology. As it comes out (we finished to write down the required lemmas today), this is quite nice.

Since Berkovich spaces are locally compact, we may restrict ourselves to classical measure theory on locally compact spaces. However, we may not make any metrizability assumption, nor any countability assumption, since the most basic Berkovich spaces lack those properties. Assume that the ground non-archimedean field $k$ is the field $\mathbf C((t))$ of Laurent series over the field $\mathbf C$ of complex numbers. Then the projective line $\mathrm P^1$ over $k$ is not metrizable, and the complement of its ``Gauss point'' $\gamma$ has uncountably many connected components (in bijection with the projective line over $\mathbf C$). Similarly, the complement of the Gauss point in the projective plane $\mathrm P^2$ over $k$ is connected, but is not countable at infinity, hence not paracompact.

As always, there are two points of view on measure theory: Borel measures (countably additive set functions on the $\sigma$-algebra of Borel sets) and Radon measures (linear forms on the vector space of continuous compactly supported functions). By the theorem of Riesz, they are basically equivalent: locally finite, compact inner regular Borel measures are in canonical bijection with Radon measures. Unfortunately, basic litterature is not very nice on that topic; for example, Rudin's book constructs an outer regular Borel measure which may not be inner regular, while for us, the behavior on compact sets is really the relevant one.

Secondly, we need to glue Radon measures defined on the members of a G-cover of our Berkovich space $X$. This is possible because Radon measures on a locally compact topological space naturally form a sheaf for a natural Grothendieck topology!

Let $X$ be a locally compact topological space and let us consider the category of locally compact subspaces, with injections as morphisms.  Radon measures can be restricted to a locally compact subspace, hence form a presheaf on that category.

Let us decree that a family $(A_i)_{i\in I}$ of locally compact subspaces of a locally compact subspace $U$ is a B-cover (B is for Borel) if for every point $x\in U$, there exists a finite subset $J$ of $I$ such that $x\in A_i$ for every $i\in J$ and such that $\bigcup_{i\in J}A_i$ is a neighborhood of $x$. B-covers form a G-topology on the category of locally compact subsets, for which Radon measures form a sheaf! In other words, given Radon measures $\mu_i$ on members $A_i$ of a B-cover of $X$ such that the restrictions to $A_i\cap A_j$ of $\mu_i$ and $\mu_j$ coincide, for all $i,j$, then there exists a unique Radon measure on $X$ whose restriction to $A_i$ equals $\mu_i$, for every $i$.

This said, the proof (once written down carefully) is not a big surprise, nor specially difficult,  but I found it nice to get a natural instance of sheaf for a Grothendieck topology within classical analysis.

Sunday, December 8, 2013

Homotopy type theory on Images des mathématiques

This post will be a short advertisement to a longer general audience text about homotopy type theory that I published on the website Images des mathématiques.

In this text, I try to convey my excitement at the reading of the book published by the participants of last year's IAS program, under direction of Steve Awoodey, Thierry Coquand and Vladimir Voevodsky.  As I write there (this is the title of this article), this remarkable work is at the crossroads of foundations of mathematics, topology and computer science. Indeed, the new foundational setup for mathematics provided by type theory may not only replace set theory; it is also at the heart of the systems for computer proof checking, and gave birth to a new kind of ``synthetic homotopy theory'' which is totally freed of the general topology framework.

Also remarkable is the way this book was produced: written collaboratively, using technology well known in open source software's development, then published under a Creative commons's license, and printed on demand.

This is not the only general audience paper on this subject, probably not the last one neither. Here are links to those I know of:
Once more, here is the link towards my article on Images des mathématiques and that towards the HoTT Book!

Friday, November 8, 2013

Ari Hoenig concert

Among the three themes I planned to discuss, only math had some place here, and not a single word about jazz. Many concerts, though, and a few of them were good, but none really good to the point to grab a keyboard and write a notice.

Two of them were even a bit disappointing. One year ago, Wayne Shorter celebrated his 80th birthday with his quartet (Danilo Perez, John Pattitucci, Brian Blade) at the Salle Pleyel. But I found the music a bit cold. Only now do I begin to appreciate the CD Without a net that they published soon after.

In september, John Zorn celebrated his 60th birthday at La Villette with a kind of musical marathon: 3 concerts, 9 bands (even 10), some 5 hours of music. Alas. While a similar concert at Banlieues bleues in 2012 had been wonderful, that one was a great disappointment. Except for 3-4 bands (Holy visions, Acoustic Masada, The Dreamers, Bar Kokhba), the rest was boring (Alchemist), ridiculous (Song Project),  if not unbearable (Templars).

But I had the great pleasure to hear Ari Hoenig in Vincennes, with Gilad Hekselman on guitar and Noam Wiesenberg on bass. Ari is a nice young drummer from Philadelphia, with a very melodic touch; I had heared him twice at the Smalls (once with Pilc and Moutin, the other I don't remember!), and he is always very interesting. When I say that he his a melodist, this is not a metaphor. The last piece they played was Charlie Parker's theme Anthropology, and this is the first time that I heard the theme played on the drums. The introduction was rather variations at a slow tempo, but at some point, he played the theme at full speed, and that was really music! Incredible when you think that drums do not have many notes to offer; so for some strokes, Ari had to put his elbow on the drumhead, pressing strongly, so as to modify the pitch. There is a video on youtube where you can see him in action, playing Anthropology (at 7:44, you can guess what I'm talking about), you can also hear that on his CD Inversations. If you like that, his Punk Bop - Live at Smalls is also an excellent CD to listen to.


Friday, October 11, 2013

Walls have ears—Random numbers, Diffie-Hellman, Tom Hales and the NSA

I've been silent for a while, sorry.

Today's message will be quite short, essentially a bunch of links to various other blog posts related to cryptography, the NSA, and how our electronic messages are potentially listened to by people we did not think of, at least before Snowden leaked all this information.

I learned of this story through Thomas Hales's web page and his blog post The NSA back door to NIST (to be published in the Notices of the AMS). There he explains how a standard protocol referenced by the NIST (National Institute for Standards and Technology) has a structural flaw that may well be intended.

All modern cryptographic protocols rely on some randomness. This is in particular the case of the Diffie-Hellman key exchange protocol which allows two people to share a secret without risking to let anybody else aware of this secret.

However, in our computers, randomness is not really random, becaused it is produced by algorithms, but is enough random-looking so that it can be used safely in applications.

As Hales explains, one of these standards for pseudo-random numbers has a back door. While it looks secure at first sight, it is possible that somebody possesses the ``back door'' information that allows him to understand the logic in the output of our series of pseudo-random numbers, all over the world, thus undermining the solidity of the algorithm.

Worse, this somebody might well be the NSA (National Security Agency).

There are two arguments in favor of this thesis:
  1. The back door is very elementary, so elementary in fact, that specialists can't believe its existence is not on purpose. According to a New York Times paper (N.S.A. Able to Foil Basic Safeguards of Privacy on Web, September 5th, 2013) classified memos apparently confirm this.
  2. By American law, the use of NIST-approved protocols is required to obtain various certifications. Moreover, the NSA is consulted for whatever cryptographic protocol is issued and has been a strong advocate of this protocol at the NIST and subsequently promoted this protocol at all major members of the International Standard Organization (ISO).
 As Hales concludes: « An algorithm that has been designed by NSA with a clear mathematical structure giving them exclusive back door access is no accident, particularly in light of the Snowden documents. This is a work of experts. »


Friday, March 8, 2013

A presheaf that has no associated sheaf

In his paper Basically bounded functors and flat sheaves (Pacific Math. J, vol. 57, no. 2, 1975, p. 597-610), William C. Waterhouse gives a nice example of a presheaf that has no associated sheaf. This is Theorem 5.5 (page 605).  I thank François Loeser for having indicated this paper to me, and for his suggestion of explaining it here!

Of course, such a beast is reputed not to exist, since it is well known that any presheaf has an associated sheaf, see for example Godement's book Topologie algébrique et théorie des faisceaux, pages 110-111.
That is, for any presheaf $F$ on a topological space, there is a sheaf $G$ with a morphism of presheaves $\alpha\colon F\to G$ which satisfies a universal property: any morphism from $F$ to a sheaf factors uniquely through $\alpha$.

Waterhouse's presheaf is a more sophisticated example of a presheaf, since it is a presheaf on the category of affine schemes for the flat topology. Thus, a presheaf $F$ on the category of affine schemes is the datum, 

  • of a set $F(A)$ for every ring $A$, 
  • and of a map $\phi_*\colon F(A)\to F(B)$ for every morphism of rings $\phi\colon A\to B$,

subject to the following conditions:

  • if $\phi\colon A\to B$ and $\psi\colon B\to C$ are morphism of rings, then $(\psi\circ\phi)_*=\psi_*\circ\phi_*$;
  • one has ${\rm id}_A)_*={\rm id}_{F(A)}$ for every ring $A$.

Any morphism of rings $\phi\colon A\to B$ gives rise to two morphisms $\psi_1,\psi_2\colon B\to B\otimes B$ respectively defined by $\psi_1(b)=b\otimes 1$ and $\psi_2(b)=1\otimes b$, and the two compositions $A\to B\to B\otimes_A B$ are equal. Consequently, for any presheaf $F$, the two associated maps $F(A) \to F(B) \to F(B\otimes_A B)$ are equal.

By definition, a presheaf $F$ is a sheaf for the flat topology if for any faithfully flat morphism of rings, the map ${\phi_*} \colon F(A)\to F(B)$ is injective and its image is the set of elements $g\in F(B)$ at which the two natural maps $(\psi_1)_*$ and $(\psi_2)_*$ from $F(B)$ to $F(B\otimes_A B)$ coincide.

Here is Waterhouse's example.

For every ring $A$, let $F(A)$ be the set of all locally constant functions $f$ from $\mathop{\rm Spec}(A)$ to some von Neumann cardinal such that $f(\mathfrak p)<\mathop{\rm Card}(\kappa(\mathfrak p))$ for every $\mathfrak p\in\mathop{\rm Spec}(A)$.

This is a presheaf. Indeed, let $\phi\colon A\to B$ is a ring morphism, let $\phi^a\colon\mathop{\rm Spec}(B)\to \mathop{\rm Spec}(A)$ be the associated continuous map on spectra. For $f\in F(A)$, then $f\circ\phi^a$ is a locally constant map from ${\rm Spec}(B)$ to some von Neumann cardinal. Moreover, for every prime ideal $\mathfrak q$ in $B$, with inverse image $\mathfrak p=\phi^{-1}(\mathfrak q)=\phi^a(\mathfrak q)$, the morphism $\phi$ induces an injection from the residue field $\kappa(\mathfrak q)$ into $\kappa(\mathfrak p)$, so that $f\circ\phi^a$ satisfies the additional condition on $F$, hence $f\circ\phi^a\in F(B)$.

However, this presheaf has no associated sheaf for the flat topology. The proof is by contradiction. So assume that $G$ is a sheaf and $\alpha\colon F\to G$ satisfies the universal property.

First of all, we prove that the morphism $\alpha$ is injective: for any ring $A$, the map $\alpha_A\colon F(A)\to G(A)$ is injective. For any cardinal $c$ and any ring $A$, let $L_c(A)$ be the set of locally constant maps  from ${\rm Spec}(A)$ to $c$. Then $L_c$ is a presheaf, and in fact a sheaf. There is a natural morphism of presheaves $\beta_c\colon F\to L_c$, given by $\beta_c(f)(\mathfrak p)=f(\mathfrak p)$ if $f(\mathfrak p)\in c$, that is, $f(\mathfrak p)<c$, and $\beta_c(f)(\mathfrak p)=0$ otherwise. Consequently, there is a unique morphism of sheaves $\gamma_c\colon G\to L_c$ such that $\beta_c=\gamma_c\circ\alpha$. For any ring $A$, and any large enough cardinal $c$, the  map $\beta_c(A)\colon F(A)\to L_c(A)$ is injective. In particular, the map $\alpha(A)$ must be injective.

Let $B$ be a ring and $\phi\colon A\to B$ be a faithfully flat morphism. Let $\psi_1,\psi_2\colon B\to B\otimes_A B$ be the two natural morphisms of rings defined above. Then, the equalizer $E(A,B)$ of the two maps $(\psi_1)_*$ and $(\psi_2)_*$ from $F(B)$ to $F(B\otimes_A B)$ must inject into the equalizer of the two corresponding maps from $G(B)$ to $G(B\otimes_A B)$. Consequently, one has an injection from $E(A,B)$ to $G(A)$.

The contradiction will become apparent once one can find rings $B$ for which $E(A,B)$ has a cardinality as large as desired. If ${\rm Spec}(B)$ is a point $\mathfrak p$, then $F(B)$ is just the set of functions $f$ from the point $\mathfrak p$ to some von Neumann cardinal $c$ such that $f(\mathfrak p)<{\rm Card}(\kappa(\mathfrak p))$. That is, $F(B)$ is the cardinal ${\rm Card}(\kappa(\mathfrak p))$ itself. And since ${\rm Spec}(B)$ is a point, the coincidence condition is necessarily satisfied, so that $E(A,B)= {\rm Card}(\kappa(\mathfrak p))\leq G(A)$.

To conclude, it suffices to take a faithfully flat morphism $A\to B$  such that $B$ is field of cardinality strictly greater than $G(A)$. For example, one can take $A$ to be a field and $B$ the field of rational functions in many indeterminates (strictly more than the cardinality of $G(A)$).

What does this example show? Why isn't there a contradiction in mathematics (yet)?

Because the definition of sheaves and presheaves for the flat topology that I gave above was definitely defective: it neglects in a too dramatic way the set theoretical issues that one must tackle to define sheaves on categories. In the standard setting of set theory provided by ZFC, everything is a set. In particular, categories, presheaves, etc. are sets or maps between sets (themselves represented by sets).  But the presheaf $F$ that Waterhouse defines does not exist as a set, since there does not exist a set $\mathbf{Ring}$ of all rings, nor a set $\mathbf{card}$ of all von Neumann cardinals.

The usual way (as explained in SGA 4) to introduce sheaves for the flat topology consists in adding the axiom of universes — there exists a set $\mathscr U$ which is a model of set theory. Then, one does not consider the (inexistent) set of all rings, or cardinals, but only those belonging to the universe $\mathscr U$—one talks of $\mathscr U$-categories, $\mathscr U$-(pre)sheaves, etc.. In that framework, the $\mathscr U$-presheaf $F$ defined by Waterhouse (where one restricts oneself to algebras and von Neumann cardinals in $\mathscr U$) has an associated sheaf $G_{\mathscr U}$. But this sheaf depends on the chosen universe: if $\mathscr V$ is an universe containing $\mathscr U$, the restriction of $G_{\mathscr V}$ to algebras in $\mathscr U$ will no longer be a $\mathscr U$-presheaf.