Gamifying propositional logic: QED, an interactive textbook

About six years ago on this blog, I started thinking about trying to make a web-based game based around high-school algebra, and ended up using Scratch to write a short but playable puzzle game in which one solves linear equations for an unknown using a restricted set of moves. (At almost the same time, there were a number of more professionally made games released along similar lines, most notably Dragonbox.)

Since then, I have thought a couple times about whether there were other parts of mathematics which could be gamified in a similar fashion. Shortly after my first blog posts on this topic, I experimented with a similar gamification of Lewis Carroll’s classic list of logic puzzles, but the results were quite clunky, and I was never satisfied with the results.

Over the last few weeks I returned to this topic though, thinking in particular about how to gamify the rules of inference of propositional logic, in a manner that at least vaguely resembles how mathematicians actually go about making logical arguments (e.g., splitting into cases, arguing by contradiction, using previous result as lemmas to help with subsequent ones, and so forth). The rules of inference are a list of a dozen or so deductive rules concerning propositional sentences (things like “( AND ) OR (NOT )”, where are some formulas). A typical such rule is Modus Ponens: if the sentence is known to be true, and the implication “ IMPLIES ” is also known to be true, then one can deduce that is also true. Furthermore, in this deductive calculus it is possible to temporarily introduce some unproven statements as an assumption, only to discharge them later. In particular, we have the deduction theorem: if, after making an assumption , one is able to derive the statement , then one can conclude that the implication “ IMPLIES ” is true without any further assumption.

It took a while for me to come up with a workable game-like graphical interface for all of this, but I finally managed to set one up, now using Javascript instead of Scratch (which would be hopelessly inadequate for this task); indeed, part of the motivation of this project was to finally learn how to program in Javascript, which turned out to be not as formidable as I had feared (certainly having experience with other C-like languages like C++, Java, or lua, as well as some prior knowledge of HTML, was very helpful). The main code for this project is available here. Using this code, I have created an interactive textbook in the style of a computer game, which I have titled “QED”. This text contains thirty-odd exercises arranged in twelve sections that function as game “levels”, in which one has to use a given set of rules of inference, together with a given set of hypotheses, to reach a desired conclusion. The set of available rules increases as one advances through the text; in particular, each new section gives one or more rules, and additionally each exercise one solves automatically becomes a new deduction rule one can exploit in later levels, much as lemmas and propositions are used in actual mathematics to prove more difficult theorems. The text automatically tries to match available deduction rules to the sentences one clicks on or drags, to try to minimise the amount of manual input one needs to actually make a deduction.

Most of one’s proof activity takes place in a “root environment” of statements that are known to be true (under the given hypothesis), but for more advanced exercises one has to also work in sub-environments in which additional assumptions are made. I found the graphical metaphor of nested boxes to be useful to depict this tree of sub-environments, and it seems to combine well with the drag-and-drop interface.

The text also logs one’s moves in a more traditional proof format, which shows how the mechanics of the game correspond to a traditional mathematical argument. My hope is that this will give students a way to understand the underlying concept of forming a proof in a manner that is more difficult to achieve using traditional, non-interactive textbooks.

I have tried to organise the exercises in a game-like progression in which one first works with easy levels that train the player on a small number of moves, and then introduce more advanced moves one at a time. As such, the order in which the rules of inference are introduced is a little idiosyncratic. The most powerful rule (the law of the excluded middle, which is what separates classical logic from intuitionistic logic) is saved for the final section of the text.

Anyway, I am now satisfied enough with the state of the code and the interactive text that I am willing to make both available (and open source; I selected a CC-BY licence for both), and would be happy to receive feedback on any aspect of the either. In principle one could extend the game mechanics to other mathematical topics than the propositional calculus – the rules of inference for first-order logic being an obvious next candidate – but it seems to make sense to focus just on propositional logic for now.

A corollary of the ergodic theorem

Let be a measure-preserving system – a probability space equipped with a measure-preserving translation (which for simplicity of discussion we shall assume to be invertible). We will informally think of two points in this space as being “close” if for some that is not too large; this allows one to distinguish between “local” structure at a point (in which one only looks at nearby points for moderately large ) and “global” structure (in which one looks at the entire space ). The local/global distinction is also known as the time-averaged/space-averaged distinction in ergodic theory.

A measure-preserving system is said to be ergodic if all the invariant sets are either zero measure or full measure. An equivalent form of this statement is that any measurable function which is locally essentially constant in the sense that for -almost every , is necessarily globally essentially constant in the sense that there is a constant such that for -almost every . A basic consequence of ergodicity is the mean ergodic theorem: if , then the averages converge in norm to the mean . (The mean ergodic theorem also applies to other spaces with , though it is usually proven first in the Hilbert space .) Informally: in ergodic systems, time averages are asymptotically equal to space averages. Specialising to the case of indicator functions, this implies in particular that converges to for any measurable set .

In this short note I would like to use the mean ergodic theorem to show that ergodic systems also have the property that “somewhat locally constant” functions are necessarily “somewhat globally constant”; this is not a deep observation, and probably already in the literature, but I found it a cute statement that I had not previously seen. More precisely:

Corollary 1 Let be an ergodic measure-preserving system, and let be measurable. Suppose that

 

for some . Then there exists a constant such that for in a set of measure at least .

Informally: if is locally constant on pairs at least of the time, then is globally constant at least of the time. Of course the claim fails if the ergodicity hypothesis is dropped, as one can simply take to be an invariant function that is not essentially constant, such as the indicator function of an invariant set of intermediate measure. This corollary can be viewed as a manifestation of the general principle that ergodic systems have the same “global” (or “space-averaged”) behaviour as “local” (or “time-averaged”) behaviour, in contrast to non-ergodic systems in which local properties do not automatically transfer over to their global counterparts.

Proof: By composing with (say) the arctangent function, we may assume without loss of generality that is bounded. Let , and partition as , where is the level set

For each , only finitely many of the are non-empty. By (1), one has

Using the ergodic theorem, we conclude that

On the other hand, . Thus there exists such that , thus

By the Bolzano-Weierstrass theorem, we may pass to a subsequence where converges to a limit , then we have

for infinitely many , and hence

The claim follows.

1% quasimorphisms and group cohomology

Let , be additive groups (i.e., groups with an abelian addition group law). A map is a homomorphism if one has

for all . A map is an affine homomorphism if one has

for all additive quadruples in , by which we mean that and . The two notions are closely related; it is easy to verify that is an affine homomorphism if and only if is the sum of a homomorphism and a constant.

Now suppose that also has a translation-invariant metric . A map is said to be a quasimorphism if one has

for all , where denotes a quantity at a bounded distance from the origin. Similarly, is an affine quasimorphism if

for all additive quadruples in . Again, one can check that is an affine quasimorphism if and only if it is the sum of a quasimorphism and a constant (with the implied constant of the quasimorphism controlled by the implied constant of the affine quasimorphism). (Since every constant is itself a quasimorphism, it is in fact the case that affine quasimorphisms are quasimorphisms, but now the implied constant in the latter is not controlled by the implied constant of the former.)

“Trivial” examples of quasimorphisms include the sum of a homomorphism and a bounded function. Are there others? In some cases, the answer is no. For instance, suppose we have a quasimorphism . Iterating (2), we see that for any integer and natural number , which we can rewrite as for non-zero . Also, is Lipschitz. Sending , we can verify that is a Cauchy sequence as and thus tends to some limit ; we have for , hence for positive , and then one can use (2) one last time to obtain for all . Thus is the sum of the homomorphism and a bounded sequence.

In general, one can phrase this problem in the language of group cohomology (discussed in this previous post). Call a map a -cocycle. A -cocycle is a map obeying the identity

for all . Given a -cocycle , one can form its derivative by the formula

Such functions are called -coboundaries. It is easy to see that the abelian group of -coboundaries is a subgroup of the abelian group of -cocycles. The quotient of these two groups is the first group cohomology of with coefficients in , and is denoted .

If a -cocycle is bounded then its derivative is a bounded -coboundary. The quotient of the group of bounded -cocycles by the derivatives of bounded -cocycles is called the bounded first group cohomology of with coefficients in , and is denoted . There is an obvious homomorphism from to , formed by taking a coset of the space of derivatives of bounded -cocycles, and enlarging it to a coset of the space of -coboundaries. By chasing all the definitions, we see that all quasimorphism from to are the sum of a homomorphism and a bounded function if and only if this homomorphism is injective; in fact the quotient of the space of quasimorphisms by the sum of homomorphisms and bounded functions is isomorphic to the kernel of .

In additive combinatorics, one is often working with functions which only have additive structure a fraction of the time, thus for instance (1) or (3) might only hold “ of the time”. This makes it somewhat difficult to directly interpret the situation in terms of group cohomology. However, thanks to tools such as the Balog-Szemerédi-Gowers lemma, one can upgrade this sort of -structure to -structure – at the cost of restricting the domain to a smaller set. Here I record one such instance of this phenomenon, thus giving a tentative link between additive combinatorics and group cohomology. (I thank Yuval Wigderson for suggesting the problem of locating such a link.)

Theorem 1 Let , be additive groups with , let be a subset of , let , and let be a function such that

for additive quadruples in . Then there exists a subset of containing with , a subset of with , and a function such that

for all (thus, the derivative takes values in on ), and such that for each , one has

for values of .

Presumably the constants and can be improved further, but we have not attempted to optimise these constants. We chose as the domain on which one has a bounded derivative, as one can use the Bogulybov lemma (see e.g, Proposition 4.39 of my book with Van Vu) to find a large Bohr set inside . In applications, the set need not have bounded size, or even bounded doubling; for instance, in the inverse theory over a small finite fields , one would be interested in the situation where is the group of matrices with coefficients in (for some large , and being the subset consisting of those matrices of rank bounded by some bound .

Proof: By hypothesis, there are triples such that and

Thus, there is a set with such that for all , one has (6) for pairs with ; in particular, there exists such that (6) holds for values of . Setting , we conclude that for each , one has

for values of .

Consider the bipartite graph whose vertex sets are two copies of , and and connected by a (directed) edge if and (7) holds. Then this graph has edges. Applying (a slight modification of) the Balog-Szemerédi-Gowers theorem (for instance by modifying the proof of Corollary 5.19 of my book with Van Vu), we can then find a subset of with with the property that for any , there exist triples such that the edges all lie in this bipartite graph. This implies that, for all , there exist septuples obeying the constraints

and for . These constraints imply in particular that

Also observe that

Thus, if and are such that , we see that

for octuples in the hyperplane

By the pigeonhole principle, this implies that for any fixed , there can be at most sets of the form with , that are pairwise disjoint. Using a greedy algorithm, we conclude that there is a set of cardinality , such that each set with , intersects for some , or in other words that

whenever . In particular,

This implies that there exists a subset of with , and an element for each , such that

for all . Note we may assume without loss of generality that and .

Suppose that are such that

By construction of , and permuting labels, we can find 16-tuples such that

and

for . We sum this to obtain

and hence by (8)

where . Since

we see that there are only possible values of . By the pigeonhole principle, we conclude that at most of the sets can be disjoint. Arguing as before, we conclude that there exists a set of cardinality such that

whenever (10) holds.

For any , write arbitrarily as for some (with if , and if ) and then set

Then from (11) we have (4). For we have , and (5) then follows from (9).

Heat flow and zeroes of polynomials II: zeroes on a circle

This is a sequel to this previous blog post, in which we discussed the effect of the heat flow evolution

on the zeroes of a time-dependent family of polynomials , with a particular focus on the case when the polynomials had real zeroes. Here (inspired by some discussions I had during a recent conference on the Riemann hypothesis in Bristol) we record the analogous theory in which the polynomials instead have zeroes on a circle , with the heat flow slightly adjusted to compensate for this. As we shall discuss shortly, a key example of this situation arises when is the numerator of the zeta function of a curve.

More precisely, let be a natural number. We will say that a polynomial

of degree (so that ) obeys the functional equation if the are all real and

for all , thus

and

for all non-zero . This means that the zeroes of (counting multiplicity) lie in and are symmetric with respect to complex conjugation and inversion across the circle . We say that this polynomial obeys the Riemann hypothesis if all of its zeroes actually lie on the circle . For instance, in the case, the polynomial obeys the Riemann hypothesis if and only if .

Such polynomials arise in number theory as follows: if is a projective curve of genus over a finite field , then, as famously proven by Weil, the associated local zeta function (as defined for instance in this previous blog post) is known to take the form

where is a degree polynomial obeying both the functional equation and the Riemann hypothesis. In the case that is an elliptic curve, then and takes the form , where is the number of -points of minus . The Riemann hypothesis in this case is a famous result of Hasse.

Another key example of such polynomials arise from rescaled characteristic polynomials

of matrices in the compact symplectic group . These polynomials obey both the functional equation and the Riemann hypothesis. The Sato-Tate conjecture (in higher genus) asserts, roughly speaking, that “typical” polyomials arising from the number theoretic situation above are distributed like the rescaled characteristic polynomials (1), where is drawn uniformly from with Haar measure.

Given a polynomial of degree with coefficients

we can evolve it in time by the formula

thus for . Informally, as one increases , this evolution accentuates the effect of the extreme monomials, particularly, and at the expense of the intermediate monomials such as , and conversely as one decreases . This family of polynomials obeys the heat-type equation

In view of the results of Marcus, Spielman, and Srivastava, it is also very likely that one can interpret this flow in terms of expected characteristic polynomials involving conjugation over the compact symplectic group , and should also be tied to some sort of “” version of Brownian motion on this group, but we have not attempted to work this connection out in detail.

It is clear that if obeys the functional equation, then so does for any other time . Now we investigate the evolution of the zeroes. Suppose at some time that the zeroes of are distinct, then

From the inverse function theorem we see that for times sufficiently close to , the zeroes of continue to be distinct (and vary smoothly in ), with

Differentiating this at any not equal to any of the , we obtain

and

and

Inserting these formulae into (2) (expanding as ) and canceling some terms, we conclude that

for sufficiently close to , and not equal to . Extracting the residue at , we conclude that

which we can rearrange as

If we make the change of variables (noting that one can make depend smoothly on for sufficiently close to ), this becomes

Intuitively, this equation asserts that the phases repel each other if they are real (and attract each other if their difference is imaginary). If obeys the Riemann hypothesis, then the are all real at time , then the Picard uniqueness theorem (applied to and its complex conjugate) then shows that the are also real for sufficiently close to . If we then define the entropy functional

then the above equation becomes a gradient flow

which implies in particular that is non-increasing in time. This shows that as one evolves time forward from , there is a uniform lower bound on the separation between the phases , and hence the equation can be solved indefinitely; in particular, obeys the Riemann hypothesis for all if it does so at time . Our argument here assumed that the zeroes of were simple, but this assumption can be removed by the usual limiting argument.

For any polynomial obeying the functional equation, the rescaled polynomials converge locally uniformly to as . By Rouche’s theorem, we conclude that the zeroes of converge to the equally spaced points on the circle . Together with the symmetry properties of the zeroes, this implies in particular that obeys the Riemann hypothesis for all sufficiently large positive . In the opposite direction, when , the polynomials converge locally uniformly to , so if , of the zeroes converge to the origin and the other converge to infinity. In particular, fails the Riemann hypothesis for sufficiently large negative . Thus (if ), there must exist a real number , which we call the de Bruijn-Newman constant of the original polynomial , such that obeys the Riemann hypothesis for and fails the Riemann hypothesis for . The situation is a bit more complicated if vanishes; if is the first natural number such that (or equivalently, ) does not vanish, then by the above arguments one finds in the limit that of the zeroes go to the origin, go to infinity, and the remaining zeroes converge to the equally spaced points . In this case the de Bruijn-Newman constant remains finite except in the degenerate case , in which case .

For instance, consider the case when and for some real with . Then the quadratic polynomial

has zeroes

and one easily checks that these zeroes lie on the circle when , and are on the real axis otherwise. Thus in this case we have (with if ). Note how as increases to , the zeroes repel each other and eventually converge to , while as decreases to , the zeroes collide and then separate on the real axis, with one zero going to the origin and the other to infinity.

The arguments in my paper with Brad Rodgers (discussed in this previous post) indicate that for a “typical” polynomial of degree that obeys the Riemann hypothesis, the expected time to relaxation to equilibrium (in which the zeroes are equally spaced) should be comparable to , basically because the average spacing is and hence by (3) the typical velocity of the zeroes should be comparable to , and the diameter of the unit circle is comparable to , thus requiring time comparable to to reach equilibrium. Taking contrapositives, this suggests that the de Bruijn-Newman constant should typically take on values comparable to (since typically one would not expect the initial configuration of zeroes to be close to evenly spaced). I have not attempted to formalise or prove this claim, but presumably one could do some numerics (perhaps using some of the examples of given previously) to explore this further.

Commutators close to the identity – an update

I have just uploaded to the arXiv my paper “Commutators close to the identity“, submitted to the Journal of Operator Theory. This paper resulted from some progress I made on the problem discussed in this previous post. Recall in that post the following result of Popa: if are bounded operators on a Hilbert space whose commutator is close to the identity in the sense that

for some , then one has the lower bound

In the other direction, for any , there are examples of operators obeying (1) such that

In this paper we improve the upper bound to come closer to the lower bound:

Theorem 1 For any , and any infinite-dimensional , there exist operators obeying (1) such that

One can probably improve the exponent somewhat by a modification of the methods, though it does not seem likely that one can lower it all the way to without a substantially new idea. Nevertheless I believe it plausible that the lower bound (2) is close to optimal.

We now sketch the methods of proof. The construction giving (3) proceeded by first identifying with the algebra of matrices that have entries in . It is then possible to find two matrices whose commutator takes the form

for some bounded operator (for instance one can take to be an isometry). If one then conjugates by the diagonal operator , one can eusure that (1) and (3) both hold.

It is natural to adapt this strategy to matrices rather than matrices, where is a parameter at one’s disposal. If one can find matrices that are almost upper triangular (in that only the entries on or above the lower diagonal are non-zero), whose commutator only differs from the identity in the top right corner, thus

for some , then by conjugating by a diagonal matrix such as for some and optimising in , one can improve the bound in (3) to ; if the bounds in the implied constant in the are polynomial in , one can then optimise in to obtain a bound of the form (4) (perhaps with the exponent replaced by a different constant).

The task is then to find almost upper triangular matrices whose commutator takes the required form. The lower diagonals of must then commute; it took me a while to realise then that one could (usually) conjugate one of the matrices, say by a suitable diagonal matrix, so that the lower diagonal consisted entirely of the identity operator, which would make the other lower diagonal consist of a single operator, say . After a lot of further lengthy experimentation, I eventually realised that one could conjugate further by unipotent upper triangular matrices so that all remaining entries other than those on the far right column vanished. Thus, without too much loss of generality, one can assume that takes the normal form

for some , solving the system of equations

for , and also

It turns out to be possible to solve this system of equations by a contraction mapping argument if one takes to be a “Hilbert’s hotel” pair of isometries as in the previous post, though the contraction is very slight, leading to polynomial losses in in the implied constant.

There is a further question raised in Popa’s paper which I was unable to resolve. As a special case of one of the main theorems (Theorem 2.1) of that paper, the following result was shown: if obeys the bounds

and

(where denotes the space of all operators of the form with and compact), then there exist operators with such that . (In fact, Popa’s result covers a more general situation in which one is working in a properly infinite algebra with non-trivial centre.) We sketch a proof of this result as follows. Suppose that and for some . A standard greedy algorithm argument (see this paper of Brown and Pearcy) allows one to find orthonormal vectors for such that for each , one has for some comparable to , and some orthogonal to all of the . After some conjugation (and a suitable identification of with , one can thus place in a normal form

where is a isometry with infinite deficiency, and have norm . Setting , it then suffices to solve the commutator equation

with ; note the similarity with (3).

By the usual Hilbert’s hotel construction, one can complement with another isometry obeying the “Hilbert’s hotel” identity

and also , . Proceeding as in the previous post, we can try the ansatz

for some operators , leading to the system of equations

Using the first equation to solve for , the second to then solve for , and the third to then solve for , one can obtain matrices with the required properties.

Thus far, my attempts to extend this construction to larger matrices with good bounds on have been unsuccessful. A model problem would be to express

as a commutator with significantly smaller than . The construction in my paper achieves something like this, but with replaced by a more complicated operator. One would also need variants of this result in which one is allowed to perturb the above operator by an arbitrary finite rank operator of bounded operator norm.

246C notes 4: Brownian motion, conformal invariance, and SLE

Important note: As this is not a course in probability, we will try to avoid developing the general theory of stochastic calculus (which includes such concepts as filtrations, martingales, and Ito calculus). This will unfortunately limit what we can actually prove rigorously, and so at some places the arguments will be somewhat informal in nature. A rigorous treatment of many of the topics here can be found for instance in Lawler’s Conformally Invariant Processes in the Plane, from which much of the material here is drawn.

In these notes, random variables will be denoted in boldface.

Definition 1 A real random variable is said to be normally distributed with mean and variance if one has

for all test functions . Similarly, a complex random variable is said to be normally distributed with mean and variance if one has

for all test functions , where is the area element on .

A real Brownian motion with base point is a random, almost surely continuous function (using the locally uniform topology on continuous functions) with the property that (almost surely) , and for any sequence of times , the increments for are independent real random variables that are normally distributed with mean zero and variance . Similarly, a complex Brownian motion with base point is a random, almost surely continuous function with the property that and for any sequence of times , the increments for are independent complex random variables that are normally distributed with mean zero and variance .

Remark 2 Thanks to the central limit theorem, the hypothesis that the increments be normally distributed can be dropped from the definition of a Brownian motion, so long as one retains the independence and the normalisation of the mean and variance (technically one also needs some uniform integrability on the increments beyond the second moment, but we will not detail this here). A similar statement is also true for the complex Brownian motion (where now we need to normalise the variances and covariances of the real and imaginary parts of the increments).

Real and complex Brownian motions exist from any base point or ; see e.g. this previous blog post for a construction. We have the following simple invariances:

Exercise 3

• (i) (Translation invariance) If is a real Brownian motion with base point , and , show that is a real Brownian motion with base point . Similarly, if is a complex Brownian motion with base point , and , show that is a complex Brownian motion with base point .
• (ii) (Dilation invariance) If is a real Brownian motion with base point , and is non-zero, show that is also a real Brownian motion with base point . Similarly, if is a complex Brownian motion with base point , and is non-zero, show that is also a complex Brownian motion with base point .
• (iii) (Real and imaginary parts) If is a complex Brownian motion with base point , show that and are independent real Brownian motions with base point . Conversely, if are independent real Brownian motions of base point , show that is a complex Brownian motion with base point .

The next lemma is a special case of the optional stopping theorem.

Lemma 4 (Optional stopping identities)

• (i) (Real case) Let be a real Brownian motion with base point . Let be a bounded stopping time – a bounded random variable with the property that for any time , the event that is determined by the values of the trajectory for times up to (or more precisely, this event is measurable with respect to the algebra generated by this proprtion of the trajectory). Then

  

  and

  

  and

  

• (ii) (Complex case) Let be a real Brownian motion with base point . Let be a bounded stopping time – a bounded random variable with the property that for any time , the event that is determined by the values of the trajectory for times up to . Then

  

  

  

  

  

Proof: (Slightly informal) We just prove (i) and leave (ii) as an exercise. By translation invariance we can take . Let be an upper bound for . Since is a real normally distributed variable with mean zero and variance , we have

and

and

By the law of total expectation, we thus have

and

and

where the inner conditional expectations are with respect to the event that attains a particular point in . However, from the independent increment nature of Brownian motion, once one conditions to a fixed point , the random variable becomes a real normally distributed variable with mean and variance . Thus we have

and

and

which give the first two claims, and (after some algebra) the identity

which then also gives the third claim.

Exercise 5 Prove the second part of Lemma 4.

Polymath15, ninth thread: going below 0.22?

This is the ninth “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing this post. Discussion of the project of a non-research nature can continue for now in the existing proposal thread. Progress will be summarised at this Polymath wiki page.

We have now tentatively improved the upper bound of the de Bruijn-Newman constant to . Among the technical improvements in our approach, we now are able to use Taylor expansions to efficiently compute the approximation to for many values of in a given region, thus speeding up the computations in the barrier considerably. Also, by using the heuristic that behaves somewhat like the partial Euler product , we were able to find a good location to place the barrier in which is larger than average, hence easier to keep away from zero.

The main remaining bottleneck is that of computing the Euler mollifier bounds that keep bounded away from zero for larger values of beyond the barrier. In going below we are beginning to need quite complicated mollifiers with somewhat poor tail behavior; we may be reaching the point where none of our bounds will succeed in keeping bounded away from zero, so we may be close to the natural limits of our methods.

Participants are also welcome to add any further summaries of the situation in the comments below.

246C notes 3: Univalent functions, the Loewner equation, and the Bieberbach conjecture

We now approach conformal maps from yet another perspective. Given an open subset of the complex numbers , define a univalent function on to be a holomorphic function that is also injective. We will primarily be studying this concept in the case when is the unit disk .

Clearly, a univalent function on the unit disk is a conformal map from to the image ; in particular, is simply connected, and not all of (since otherwise the inverse map would violate Liouville’s theorem). In the converse direction, the Riemann mapping theorem tells us that every open simply connected proper subset of the complex numbers is the image of a univalent function on . Furthermore, if contains the origin, then the univalent function with this image becomes unique once we normalise and . Thus the Riemann mapping theorem provides a one-to-one correspondence between open simply connected proper subsets of the complex plane containing the origin, and univalent functions with and . We will focus particular attention on the univalent functions with the normalisation and ; such functions will be called schlicht functions.

One basic example of a univalent function on is the Cayley transform , which is a Möbius transformation from to the right half-plane . (The slight variant is also referred to as the Cayley transform, as is the closely related map , which maps to the upper half-plane.) One can square this map to obtain a further univalent function , which now maps to the complex numbers with the negative real axis removed. One can normalise this function to be schlicht to obtain the Koebe function

which now maps to the complex numbers with the half-line removed. A little more generally, for any we have the rotated Koebe function

that is a schlicht function that maps to the complex numbers with the half-line removed.

Every schlicht function has a convergent Taylor expansion

for some complex coefficients with . For instance, the Koebe function has the expansion

and similarly the rotated Koebe function has the expansion

Intuitively, the Koebe function and its rotations should be the “largest” schlicht functions available. This is formalised by the famous Bieberbach conjecture, which asserts that for any schlicht function, the coefficients should obey the bound for all . After a large number of partial results, this conjecture was eventually solved by de Branges; see for instance this survey of Korevaar or this survey of Koepf for a history.

It turns out that to resolve these sorts of questions, it is convenient to restrict attention to schlicht functions that are odd, thus for all , and the Taylor expansion now reads

for some complex coefficients with . One can transform a general schlicht function to an odd schlicht function by observing that the function , after removing the singularity at zero, is a non-zero function that equals at the origin, and thus (as is simply connected) has a unique holomorphic square root that also equals at the origin. If one then sets

it is not difficult to verify that is an odd schlicht function which additionally obeys the equation

Conversely, given an odd schlicht function , the formula (4) uniquely determines a schlicht function .

For instance, if is the Koebe function (1), becomes

which maps to the complex numbers with two slits removed, and if is the rotated Koebe function (2), becomes

De Branges established the Bieberbach conjecture by first proving an analogous conjecture for odd schlicht functions known as Robertson’s conjecture. More precisely, we have

Theorem 1 (de Branges’ theorem) Let be a natural number.

• (i) (Robertson conjecture) If is an odd schlicht function, then

  

• (ii) (Bieberbach conjecture) If is a schlicht function, then

  

It is easy to see that the Robertson conjecture for a given value of implies the Bieberbach conjecture for the same value of . Indeed, if is schlicht, and is the odd schlicht function given by (3), then from extracting the coefficient of (4) we obtain a formula

for the coefficients of in terms of the coefficients of . Applying the Cauchy-Schwarz inequality, we derive the Bieberbach conjecture for this value of from the Robertson conjecture for the same value of . We remark that Littlewood and Paley had conjectured a stronger form of Robertson’s conjecture, but this was disproved for by Fekete and Szegö.

To prove the Robertson and Bieberbach conjectures, one first takes a logarithm and deduces both conjectures from a similar conjecture about the Taylor coefficients of , known as the Milin conjecture. Next, one continuously enlarges the image of the schlicht function to cover all of ; done properly, this places the schlicht function as the initial function in a sequence of univalent maps known as a Loewner chain. The functions obey a useful differential equation known as the Loewner equation, that involves an unspecified forcing term (or , in the case that the image is a slit domain) coming from the boundary; this in turn gives useful differential equations for the Taylor coefficients of , , or . After some elementary calculus manipulations to “integrate” this equations, the Bieberbach, Robertson, and Milin conjectures are then reduced to establishing the non-negativity of a certain explicit hypergeometric function, which is non-trivial to prove (and will not be done here, except for small values of ) but for which several proofs exist in the literature.

The theory of Loewner chains subsequently became fundamental to a more recent topic in complex analysis, that of the Schramm-Loewner equation (SLE), which is the focus of the next and final set of notes.

Polymath15, eighth thread: going below 0.28

This is the eighth “research” thread of the Polymath15 project to upper bound the de Bruijn-Newman constant , continuing this post. Discussion of the project of a non-research nature can continue for now in the existing proposal thread. Progress will be summarised at this Polymath wiki page.

Significant progress has been made since the last update; by implementing the “barrier” method to establish zero free regions for by leveraging the extensive existing numerical verification of the Riemann hypothesis (which establishes zero free regions for ), we have been able to improve our upper bound on from 0.48 to 0.28. Furthermore, there appears to be a bit of further room to improve the bounds further by tweaking the parameters used in the argument (we are currently using ); the most recent idea is to try to use exponential sum estimates to improve the bounds on the derivative of the approximation to that is used in the barrier method, which currently is the most computationally intensive step of the argument.

Polymath16 now launched: simplifying the lower bound argument for the Hadwiger-Nelson problem

Just a quick announcement that Dustin Mixon and Aubrey de Grey have just launched the Polymath16 project over at Dustin’s blog.  The main goal of this project is to simplify the recent proof by Aubrey de Grey that the chromatic number of the unit distance graph of the plane is at least 5, thus making progress on the Hadwiger-Nelson problem.  The current proof is computer assisted (in particular it requires one to control the possible 4-colorings of a certain graph with over a thousand vertices), but one of the aims of the project is to reduce the amount of computer assistance needed to verify the proof; already a number of such reductions have been found.  See also this blog post where the polymath project was proposed, as well as the wiki page for the project.  Non-technical discussion of the project will continue at the proposal blog post.