You are currently browsing the monthly archive for August 2011.

This fall (starting Monday, September 26), I will be teaching a graduate topics course which I have entitled “Hilbert’s fifth problem and related topics.” The course is going to focus on three related topics:

  • Hilbert’s fifth problem on the topological description of Lie groups, as well as the closely related (local) classification of locally compact groups (the Gleason-Yamabe theorem).
  • Approximate groups in nonabelian groups, and their classification via the Gleason-Yamabe theorem (this is very recent work of Emmanuel Breuillard, Ben Green, Tom Sanders, and myself, building upon earlier work of Hrushovski);
  • Gromov’s theorem on groups of polynomial growth, as proven via the classification of approximate groups (as well as some consequences to fundamental groups of Riemannian manifolds).

I have already blogged about these topics repeatedly in the past (particularly with regard to Hilbert’s fifth problem), and I intend to recycle some of that material in the lecture notes for this course.

The above three families of results exemplify two broad principles (part of what I like to call “the dichotomy between structure and randomness“):

  • (Rigidity) If a group-like object exhibits a weak amount of regularity, then it (or a large portion thereof) often automatically exhibits a strong amount of regularity as well;
  • (Structure) This strong regularity manifests itself either as Lie type structure (in continuous settings) or nilpotent type structure (in discrete settings). (In some cases, “nilpotent” should be replaced by sister properties such as “abelian“, “solvable“, or “polycyclic“.)

Let me illustrate what I mean by these two principles with two simple examples, one in the continuous setting and one in the discrete setting. We begin with a continuous example. Given an {n \times n} complex matrix {A \in M_n({\bf C})}, define the matrix exponential {\exp(A)} of {A} by the formula

\displaystyle  \exp(A) := \sum_{k=0}^\infty \frac{A^k}{k!} = 1 + A + \frac{1}{2!} A^2 + \frac{1}{3!} A^3 + \ldots

which can easily be verified to be an absolutely convergent series.

Exercise 1 Show that the map {A \mapsto \exp(A)} is a real analytic (and even complex analytic) map from {M_n({\bf C})} to {M_n({\bf C})}, and obeys the restricted homomorphism property

\displaystyle  \exp(sA) \exp(tA) = \exp((s+t)A) \ \ \ \ \ (1)

for all {A \in M_n({\bf C})} and {s,t \in {\bf C}}.

Proposition 1 (Rigidity and structure of matrix homomorphisms) Let {n} be a natural number. Let {GL_n({\bf C})} be the group of invertible {n \times n} complex matrices. Let {\Phi: {\bf R} \rightarrow GL_n({\bf C})} be a map obeying two properties:

  • (Group-like object) {\Phi} is a homomorphism, thus {\Phi(s) \Phi(t) = \Phi(s+t)} for all {s,t \in {\bf R}}.
  • (Weak regularity) The map {t \mapsto \Phi(t)} is continuous.

Then:

  • (Strong regularity) The map {t \mapsto \Phi(t)} is smooth (i.e. infinitely differentiable). In fact it is even real analytic.
  • (Lie-type structure) There exists a (unique) complex {n \times n} matrix {A} such that {\Phi(t) = \exp(tA)} for all {t \in {\bf R}}.

Proof: Let {\Phi} be as above. Let {\epsilon > 0} be a small number (depending only on {n}). By the homomorphism property, {\Phi(0) = 1} (where we use {1} here to denote the identity element of {GL_n({\bf C})}), and so by continuity we may find a small {t_0>0} such that {\Phi(t) = 1 + O(\epsilon)} for all {t \in [-t_0,t_0]} (we use some arbitrary norm here on the space of {n \times n} matrices, and allow implied constants in the {O()} notation to depend on {n}).

The map {A \mapsto \exp(A)} is real analytic and (by the inverse function theorem) is a diffeomorphism near {0}. Thus, by the inverse function theorem, we can (if {\epsilon} is small enough) find a matrix {B} of size {B = O(\epsilon)} such that {\Phi(t_0) = \exp(B)}. By the homomorphism property and (1), we thus have

\displaystyle  \Phi(t_0/2)^2 = \Phi(t_0) = \exp(B) = \exp(B/2)^2.

On the other hand, by another application of the inverse function theorem we see that the squaring map {A \mapsto A^2} is a diffeomorphism near {1} in {GL_n({\bf C})}, and thus (if {\epsilon} is small enough)

\displaystyle  \Phi(t_0/2) = \exp(B/2).

We may iterate this argument (for a fixed, but small, value of {\epsilon}) and conclude that

\displaystyle  \Phi(t_0/2^k) = \exp(B/2^k)

for all {k = 0,1,2,\ldots}. By the homomorphism property and (1) we thus have

\displaystyle  \Phi(qt_0) = \exp(qB)

whenever {q} is a dyadic rational, i.e. a rational of the form {a/2^k} for some integer {a} and natural number {k}. By continuity we thus have

\displaystyle  \Phi(st_0) = \exp(sB)

for all real {s}. Setting {A := B/t_0} we conclude that

\displaystyle  \Phi(t) = \exp(tA)

for all real {t}, which gives existence of the representation and also real analyticity and smoothness. Finally, uniqueness of the representation {\Phi(t) = \exp(tA)} follows from the identity

\displaystyle  A = \frac{d}{dt} \exp(tA)|_{t=0}.

\Box

Exercise 2 Generalise Proposition 1 by replacing the hypothesis that {\Phi} is continuous with the hypothesis that {\Phi} is Lebesgue measurable (Hint: use the Steinhaus theorem.). Show that the proposition fails (assuming the axiom of choice) if this hypothesis is omitted entirely.

Note how one needs both the group-like structure and the weak regularity in combination in order to ensure the strong regularity; neither is sufficient on its own. We will see variants of the above basic argument throughout the course. Here, the task of obtaining smooth (or real analytic structure) was relatively easy, because we could borrow the smooth (or real analytic) structure of the domain {{\bf R}} and range {M_n({\bf C})}; but, somewhat remarkably, we shall see that one can still build such smooth or analytic structures even when none of the original objects have any such structure to begin with.

Now we turn to a second illustration of the above principles, namely Jordan’s theorem, which uses a discreteness hypothesis to upgrade Lie type structure to nilpotent (and in this case, abelian) structure. We shall formulate Jordan’s theorem in a slightly stilted fashion in order to emphasise the adherence to the above-mentioned principles.

Theorem 2 (Jordan’s theorem) Let {G} be an object with the following properties:

  • (Group-like object) {G} is a group.
  • (Discreteness) {G} is finite.
  • (Lie-type structure) {G} is contained in {U_n({\bf C})} (the group of unitary {n \times n} matrices) for some {n}.

Then there is a subgroup {G'} of {G} such that

  • ({G'} is close to {G}) The index {|G/G'|} of {G'} in {G} is {O_n(1)} (i.e. bounded by {C_n} for some quantity {C_n} depending only on {n}).
  • (Nilpotent-type structure) {G'} is abelian.

A key observation in the proof of Jordan’s theorem is that if two unitary elements {g, h \in U_n({\bf C})} are close to the identity, then their commutator {[g,h] = g^{-1}h^{-1}gh} is even closer to the identity (in, say, the operator norm {\| \|_{op}}). Indeed, since multiplication on the left or right by unitary elements does not affect the operator norm, we have

\displaystyle  \| [g,h] - 1 \|_{op} = \| gh - hg \|_{op}

\displaystyle  = \| (g-1)(h-1) - (h-1)(g-1) \|_{op}

and so by the triangle inequality

\displaystyle  \| [g,h] - 1 \|_{op} \leq 2 \|g-1\|_{op} \|h-1\|_{op}. \ \ \ \ \ (2)

Now we can prove Jordan’s theorem.

Proof: We induct on {n}, the case {n=1} being trivial. Suppose first that {G} contains a central element {g} which is not a multiple of the identity. Then, by definition, {G} is contained in the centraliser {Z(g)} of {g}, which by the spectral theorem is isomorphic to a product {U_{n_1}({\bf C}) \times \ldots \times U_{n_k}({\bf C})} of smaller unitary groups. Projecting {G} to each of these factor groups and applying the induction hypothesis, we obtain the claim.

Thus we may assume that {G} contains no central elements other than multiples of the identity. Now pick a small {\epsilon > 0} (one could take {\epsilon=\frac{1}{10d}} in fact) and consider the subgroup {G'} of {G} generated by those elements of {G} that are within {\epsilon} of the identity (in the operator norm). By considering a maximal {\epsilon}-net of {G} we see that {G'} has index at most {O_{n,\epsilon}(1)} in {G}. By arguing as before, we may assume that {G'} has no central elements other than multiples of the identity.

If {G'} consists only of multiples of the identity, then we are done. If not, take an element {g} of {G'} that is not a multiple of the identity, and which is as close as possible to the identity (here is where we crucially use that {G} is finite). By (2), we see that if {\epsilon} is sufficiently small depending on {n}, and if {h} is one of the generators of {G'}, then {[g,h]} lies in {G'} and is closer to the identity than {g}, and is thus a multiple of the identity. On the other hand, {[g,h]} has determinant {1}. Given that it is so close to the identity, it must therefore be the identity (if {\epsilon} is small enough). In other words, {g} is central in {G'}, and is thus a multiple of the identity. But this contradicts the hypothesis that there are no central elements other than multiples of the identity, and we are done. \Box

Commutator estimates such as (2) will play a fundamental role in many of the arguments we will see in this course; as we saw above, such estimates combine very well with a discreteness hypothesis, but will also be very useful in the continuous setting.

Exercise 3 Generalise Jordan’s theorem to the case when {G} is a finite subgroup of {GL_n({\bf C})} rather than of {U_n({\bf C})}. (Hint: The elements of {G} are not necessarily unitary, and thus do not necessarily preserve the standard Hilbert inner product of {{\bf C}^n}. However, if one averages that inner product by the finite group {G}, one obtains a new inner product on {{\bf C}^n} that is preserved by {G}, which allows one to conjugate {G} to a subgroup of {U_n({\bf C})}. This averaging trick is (a small) part of Weyl’s unitary trick in representation theory.)

Exercise 4 (Inability to discretise nonabelian Lie groups) Show that if {n \geq 3}, then the orthogonal group {O_n({\bf R})} cannot contain arbitrarily dense finite subgroups, in the sense that there exists an {\epsilon = \epsilon_n > 0} depending only on {n} such that for every finite subgroup {G} of {O_n({\bf R})}, there exists a ball of radius {\epsilon} in {O_n({\bf R})} (with, say, the operator norm metric) that is disjoint from {G}. What happens in the {n=2} case?

Remark 1 More precise classifications of the finite subgroups of {U_n({\bf C})} are known, particularly in low dimensions. For instance, one can show that the only finite subgroups of {SO_3({\bf R})} (which {SU_2({\bf C})} is a double cover of) are isomorphic to either a cyclic group, a dihedral group, or the symmetry group of one of the Platonic solids.

Read the rest of this entry »

One of the most notorious problems in elementary mathematics that remains unsolved is the Collatz conjecture, concerning the function {f_0: {\bf N} \rightarrow {\bf N}} defined by setting {f_0(n) := 3n+1} when {n} is odd, and {f_0(n) := n/2} when {n} is even. (Here, {{\bf N}} is understood to be the positive natural numbers {\{1,2,3,\ldots\}}.)

Conjecture 1 (Collatz conjecture) For any given natural number {n}, the orbit {n, f_0(n), f^2_0(n), f^3_0(n), \ldots} passes through {1} (i.e. {f^k_0(n)=1} for some {k}).

Open questions with this level of notoriety can lead to what Richard Lipton calls “mathematical diseases” (and what I termed an unhealthy amount of obsession on a single famous problem). (See also this xkcd comic regarding the Collatz conjecture.) As such, most practicing mathematicians tend to spend the majority of their time on more productive research areas that are only just beyond the range of current techniques. Nevertheless, it can still be diverting to spend a day or two each year on these sorts of questions, before returning to other matters; so I recently had a go at the problem. Needless to say, I didn’t solve the problem, but I have a better appreciation of why the conjecture is (a) plausible, and (b) unlikely be proven by current technology, and I thought I would share what I had found out here on this blog.

Let me begin with some very well known facts. If {n} is odd, then {f_0(n) = 3n+1} is even, and so {f_0^2(n) = \frac{3n+1}{2}}. Because of this, one could replace {f_0} by the function {f_1: {\bf N} \rightarrow {\bf N}}, defined by {f_1(n) = \frac{3n+1}{2}} when {n} is odd, and {f_1(n)=n/2} when {n} is even, and obtain an equivalent conjecture. Now we see that if one chooses {n} “at random”, in the sense that it is odd with probability {1/2} and even with probability {1/2}, then {f_1} increases {n} by a factor of roughly {3/2} half the time, and decreases it by a factor of {1/2} half the time. Furthermore, if {n} is uniformly distributed modulo {4}, one easily verifies that {f_1(n)} is uniformly distributed modulo {2}, and so {f_1^2(n)} should be roughly {3/2} times as large as {f_1(n)} half the time, and roughly {1/2} times as large as {f_1(n)} the other half of the time. Continuing this at a heuristic level, we expect generically that {f_1^{k+1}(n) \approx \frac{3}{2} f_1^k(n)} half the time, and {f_1^{k+1}(n) \approx \frac{1}{2} f_1^k(n)} the other half of the time. The logarithm {\log f_1^k(n)} of this orbit can then be modeled heuristically by a random walk with steps {\log \frac{3}{2}} and {\log \frac{1}{2}} occuring with equal probability. The expectation

\displaystyle  \frac{1}{2} \log \frac{3}{2} + \frac{1}{2} \log \frac{1}{2} = \frac{1}{2} \log \frac{3}{4}

is negative, and so (by the classic gambler’s ruin) we expect the orbit to decrease over the long term. This can be viewed as heuristic justification of the Collatz conjecture, at least in the “average case” scenario in which {n} is chosen uniform at random (e.g. in some large interval {\{1,\ldots,N\}}). (It also suggests that if one modifies the problem, e.g. by replacing {3n+1} to {5n+1}, then one can obtain orbits that tend to increase over time, and indeed numerically for this variant one sees orbits that appear to escape to infinity.) Unfortunately, one can only rigorously keep the orbit uniformly distributed modulo {2} for time about {O(\log N)} or so; after that, the system is too complicated for naive methods to control at anything other than a heuristic level.

Remark 1 One can obtain a rigorous analogue of the above arguments by extending {f_1} from the integers {{\bf Z}} to the {2}-adics {{\bf Z}_2}. This compact abelian group comes with a Haar probability measure, and one can verify that this measure is invariant with respect to {f_1}; with a bit more effort one can verify that it is ergodic. This suggests the introduction of ergodic theory methods. For instance, using the pointwise ergodic theorem, we see that if {n} is a random {2}-adic integer, then almost surely the orbit {n, f_1(n), f_1^2(n), \ldots} will be even half the time and odd half the time asymptotically, thus supporting the above heuristics. Unfortunately, this does not directly tell us much about the dynamics on {{\bf Z}}, as this is a measure zero subset of {{\bf Z}_2}. More generally, unless a dynamical system is somehow “polynomial”, “nilpotent”, or “unipotent” in nature, the current state of ergodic theory is usually only able to say something meaningful about generic orbits, but not about all orbits. For instance, the very simple system {x \rightarrow 10x} on the unit circle {{\bf R}/{\bf Z}} is well understood from ergodic theory (in particular, almost all orbits will be uniformly distributed), but the orbit of a specific point, e.g. {\pi\hbox{ mod } 1}, is still nearly impossible to understand (this particular problem being equivalent to the notorious unsolved question of whether the digits of {\pi} are uniformly distributed).

The above heuristic argument only suggests decreasing orbits for almost all {n} (though even this remains unproven, the state of the art is that the number of {n} in {\{1,\ldots,N\}} that eventually go to {1} is {\gg N^{0.84}}, a result of Krasikov and Lagarias). It leaves open the possibility of some very rare exceptional {n} for which the orbit goes to infinity, or gets trapped in a periodic loop. Since the only loop that {1} lies in is {1,4,2} (for {f_0}) or {1,2} (for {f_1}), we thus may isolate a weaker consequence of the Collatz conjecture:

Conjecture 2 (Weak Collatz conjecture) Suppose that {n} is a natural number such that {f^k_0(n)=n} for some {k \geq 1}. Then {n} is equal to {1}, {2}, or {4}.

Of course, we may replace {f_0} with {f_1} (and delete “{4}“) and obtain an equivalent conjecture.

This weaker version of the Collatz conjecture is also unproven. However, it was observed by Bohm and Sontacchi that this weak conjecture is equivalent to a divisibility problem involving powers of {2} and {3}:

Conjecture 3 (Reformulated weak Collatz conjecture) There does not exist {k \geq 1} and integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

such that {2^{a_{k+1}}-3^k} is a positive integer that is a proper divisor of

\displaystyle  3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k},

i.e.

\displaystyle  (2^{a_{k+1}} - 3^k) n = 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k} \ \ \ \ \ (1)

for some natural number {n > 1}.

Proposition 4 Conjecture 2 and Conjecture 3 are equivalent.

Proof: To see this, it is convenient to reformulate Conjecture 2 slightly. Define an equivalence relation {\sim} on {{\bf N}} by declaring {a \sim b} if {a/b = 2^m} for some integer {m}, thus giving rise to the quotient space {{\bf N}/\sim} of equivalence classes {[n]} (which can be placed, if one wishes, in one-to-one correspondence with the odd natural numbers). We can then define a function {f_2: {\bf N}/\sim \rightarrow {\bf N}/\sim} by declaring

\displaystyle  f_2( [n] ) := [3n + 2^a] \ \ \ \ \ (2)

for any {n \in {\bf N}}, where {2^a} is the largest power of {2} that divides {n}. It is easy to see that {f_2} is well-defined (it is essentially the Syracuse function, after identifying {{\bf N}/\sim} with the odd natural numbers), and that periodic orbits of {f_2} correspond to periodic orbits of {f_1} or {f_0}. Thus, Conjecture 2 is equivalent to the conjecture that {[1]} is the only periodic orbit of {f_2}.

Now suppose that Conjecture 2 failed, thus there exists {[n] \neq [1]} such that {f_2^k([n])=[n]} for some {k \geq 1}. Without loss of generality we may take {n} to be odd, then {n>1}. It is easy to see that {[1]} is the only fixed point of {f_2}, and so {k>1}. An easy induction using (2) shows that

\displaystyle  f_2^k([n]) = [3^k n + 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}]

where, for each {1 \leq i \leq k}, {2^{a_i}} is the largest power of {2} that divides

\displaystyle  n_i := 3^{i-1} n + 3^{i-2} 2^{a_1} + \ldots + 2^{a_{i-1}}. \ \ \ \ \ (3)

In particular, as {n_1 = n} is odd, {a_1=0}. Using the recursion

\displaystyle  n_{i+1} = 3n_i + 2^{a_i}, \ \ \ \ \ (4)

we see from induction that {2^{a_i+1}} divides {n_{i+1}}, and thus {a_{i+1}>a_i}:

\displaystyle  0 = a_1 < a_2 < \ldots < a_k.

Since {f_2^k([n]) = [n]}, we have

\displaystyle  2^{a_{k+1}} n = 3^k n + 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k} = 3 n_k + 2^{a_k}

for some integer {a_{k+1}}. Since {3 n_k + 2^{a_k}} is divisible by {2^{a_k+1}}, and {n} is odd, we conclude {a_{k+1} > a_k}; if we rearrange the above equation as (1), then we obtain a counterexample to Conjecture 3.

Conversely, suppose that Conjecture 3 failed. Then we have {k \geq 1}, integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

and a natural number {n > 1} such that (1) holds. As {a_1=0}, we see that the right-hand side of (1) is odd, so {n} is odd also. If we then introduce the natural numbers {n_i} by the formula (3), then an easy induction using (4) shows that

\displaystyle  (2^{a_{k+1}} - 3^k) n_i = 3^{k-1} 2^{a_i} + 3^{k-2} 2^{a_{i+1}} + \ldots + 2^{a_{i+k-1}} \ \ \ \ \ (5)

with the periodic convention {a_{k+j} := a_j + a_{k+1}} for {j>1}. As the {a_i} are increasing in {i} (even for {i \geq k+1}), we see that {2^{a_i}} is the largest power of {2} that divides the right-hand side of (5); as {2^{a_{k+1}}-3^k} is odd, we conclude that {2^{a_i}} is also the largest power of {2} that divides {n_i}. We conclude that

\displaystyle f_2([n_i]) = [3n_i + 2^{a_i}] = [n_{i+1}]

and thus {[n]} is a periodic orbit of {f_2}. Since {n} is an odd number larger than {1}, this contradicts Conjecture 3. \Box

Call a counterexample a tuple {(k,a_1,\ldots,a_{k+1})} that contradicts Conjecture 3, i.e. an integer {k \geq 1} and an increasing set of integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

such that (1) holds for some {n \geq 1}. We record a simple bound on such counterexamples, due to Terras and to Garner :

Lemma 5 (Exponent bounds) Let {N \geq 1}, and suppose that the Collatz conjecture is true for all {n < N}. Let {(k,a_1,\ldots,a_{k+1})} be a counterexample. Then

\displaystyle  \frac{\log 3}{\log 2} k < a_{k+1} < \frac{\log(3+\frac{1}{N})}{\log 2} k.

Proof: The first bound is immediate from the positivity of {2^{a_{k+1}}-3^k}. To prove the second bound, observe from the proof of Proposition 4 that the counterexample {(k,a_1,\ldots,a_{k+1})} will generate a counterexample to Conjecture 2, i.e. a non-trivial periodic orbit {n, f(n), \ldots, f^K(n) = n}. As the conjecture is true for all {n < N}, all terms in this orbit must be at least {N}. An inspection of the proof of Proposition 4 reveals that this orbit consists of {k} steps of the form {x \mapsto 3x+1}, and {a_{k+1}} steps of the form {x \mapsto x/2}. As all terms are at least {N}, the former steps can increase magnitude by a multiplicative factor of at most {3+\frac{1}{N}}. As the orbit returns to where it started, we conclude that

\displaystyle  1 \leq (3+\frac{1}{N})^k (\frac{1}{2})^{a_{k+1}}

whence the claim. \Box

The Collatz conjecture has already been verified for many values of {n} (up to at least {N = 5 \times 10^{18}}, according to this web site). Inserting this into the above lemma, one can get lower bounds on {k}. For instance, by methods such as this, it is known that any non-trivial periodic orbit has length at least {105{,}000}, as shown in Garner’s paper (and this bound, which uses the much smaller value {N = 2 \times 10^9} that was available in 1981, can surely be improved using the most recent computational bounds).

Now we can perform a heuristic count on the number of counterexamples. If we fix {k} and {a := a_{k+1}}, then {2^a > 3^k}, and from basic combinatorics we see that there are {\binom{a-1}{k-1}} different ways to choose the remaining integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

to form a potential counterexample {(k,a_1,\ldots,a_{k+1})}. As a crude heuristic, one expects that for a “random” such choice of integers, the expression (1) has a probability {1/q} of holding for some integer {n}. (Note that {q} is not divisible by {2} or {3}, and so one does not expect the special structure of the right-hand side of (1) with respect to those moduli to be relevant. There will be some choices of {a_1,\ldots,a_k} where the right-hand side in (1) is too small to be divisible by {q}, but using the estimates in Lemma 5, one expects this to occur very infrequently.) Thus, the total expected number of solutions for this choice of {a, k} is

\displaystyle  \frac{1}{q} \binom{a-1}{k-1}.

The heuristic number of solutions overall is then expected to be

\displaystyle  \sum_{a,k} \frac{1}{q} \binom{a-1}{k-1}, \ \ \ \ \ (6)

where, in view of Lemma 5, one should restrict the double summation to the heuristic regime {a \approx \frac{\log 3}{\log 2} k}, with the approximation here accurate to many decimal places.

We need a lower bound on {q}. Here, we will use Baker’s theorem (as discussed in this previous post), which among other things gives the lower bound

\displaystyle  q = 2^a - 3^k \gg 2^a / a^C \ \ \ \ \ (7)

for some absolute constant {C}. Meanwhile, Stirling’s formula (as discussed in this previous post) combined with the approximation {k \approx \frac{\log 2}{\log 3} a} gives

\displaystyle  \binom{a-1}{k-1} \approx \exp(h(\frac{\log 2}{\log 3}))^a

where {h} is the entropy function

\displaystyle  h(x) := - x \log x - (1-x) \log (1-x).

A brief computation shows that

\displaystyle  \exp(h(\frac{\log 2}{\log 3})) \approx 1.9318 \ldots

and so (ignoring all subexponential terms)

\displaystyle  \frac{1}{q} \binom{a-1}{k-1} \approx (0.9659\ldots)^a

which makes the series (6) convergent. (Actually, one does not need the full strength of Lemma 5 here; anything that kept {k} well away from {a/2} would suffice. In particular, one does not need an enormous value of {N}; even {N=5} (say) would be more than sufficient to obtain the heuristic that there are finitely many counterexamples.) Heuristically applying the Borel-Cantelli lemma, we thus expect that there are only a finite number of counterexamples to the weak Collatz conjecture (and inserting a bound such as {k \geq 105{,}000}, one in fact expects it to be extremely likely that there are no counterexamples at all).

This, of course, is far short of any rigorous proof of Conjecture 2. In order to make rigorous progress on this conjecture, it seems that one would need to somehow exploit the structural properties of numbers of the form

\displaystyle  3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}. \ \ \ \ \ (8)

In some very special cases, this can be done. For instance, suppose that one had {a_{i+1}=a_i+1} with at most one exception (this is essentially what is called a {1}-cycle by Steiner). Then (8) simplifies via the geometric series formula to a combination of just a bounded number of powers of {2} and {3}, rather than an unbounded number. In that case, one can start using tools from transcendence theory such as Baker’s theorem to obtain good results; for instance, in the above-referenced paper of Steiner, it was shown that {1}-cycles cannot actually occur, and similar methods have been used to show that {m}-cycles (in which there are at most {m} exceptions to {a_{i+1}=a_i+1}) do not occur for any {m \leq 63}, as was shown by Simons and de Weger. However, for general increasing tuples of integers {a_1,\ldots,a_k}, there is no such representation by bounded numbers of powers, and it does not seem that methods from transcendence theory will be sufficient to control the expressions (8) to the extent that one can understand their divisibility properties by quantities such as {2^a-3^k}.

Amusingly, there is a slight connection to Littlewood-Offord theory in additive combinatorics – the study of the {2^n} random sums

\displaystyle  \pm v_1 \pm v_2 \pm \ldots \pm v_n

generated by some elements {v_1,\ldots,v_n} of an additive group {G}, or equivalently, the vertices of an {n}-dimensional parallelepiped inside {G}. Here, the relevant group is {{\bf Z}/q{\bf Z}}. The point is that if one fixes {k} and {a_{k+1}} (and hence {q}), and lets {a_1,\ldots,a_k} vary inside the simplex

\displaystyle  \Delta := \{ (a_1,\ldots,a_k) \in {\bf N}^k: 0 = a_1 < \ldots < a_k < a_{k+1}\}

then the set {S} of all sums of the form (8) (viewed as an element of {{\bf Z}/q{\bf Z}}) contains many large parallelepipeds. (Note, incidentally, that once one fixes {k}, all the sums of the form (8) are distinct; because given (8) and {k}, one can read off {2^{a_1}} as the largest power of {2} that divides (8), and then subtracting off {3^{k-1} 2^{a_1}} one can then read off {2^{a_2}}, and so forth.) This is because the simplex {\Delta} contains many large cubes. Indeed, if one picks a typical element {(a_1,\ldots,a_k)} of {\Delta}, then one expects (thanks to Lemma 5) that there there will be {\gg k} indices {1 \leq i_1 < \ldots < i_m \leq k} such that {a_{i_j+1} > a_{i_j}+1} for {j=1,\ldots,m}, which allows one to adjust each of the {a_{i_j}} independently by {1} if desired and still remain inside {\Delta}. This gives a cube in {\Delta} of dimension {\gg k}, which then induces a parallelepiped of the same dimension in {S}. A short computation shows that the generators of this parallelepiped consist of products of a power of {2} and a power of {3}, and in particular will be coprime to {q}.

If the weak Collatz conjecture is true, then the set {S} must avoid the residue class {0} in {{\bf Z}/q{\bf Z}}. Let us suppose temporarily that we did not know about Baker’s theorem (and the associated bound (7)), so that {q} could potentially be quite small. Then we would have a large parallelepiped inside a small cyclic group {{\bf Z}/q{\bf Z}} that did not cover all of {{\bf Z}/q{\bf Z}}, which would not be possible for {q} small enough. Indeed, an easy induction shows that a {d}-dimensional parallelepiped in {{\bf Z}/q{\bf Z}}, with all generators coprime to {q}, has cardinality at least {\min(q, d+1)}. This argument already shows the lower bound {q \gg k}. In other words, we have

Proposition 6 Suppose the weak Collatz conjecture is true. Then for any natural numbers {a, k} with {2^a > 3^k}, one has {2^a-3^k \gg k}.

This bound is very weak when compared against the unconditional bound (7). However, I know of no way to get a nontrivial separation property between powers of {2} and powers of {3} other than via transcendence theory methods. Thus, this result strongly suggests that any proof of the Collatz conjecture must either use existing results in transcendence theory, or else must contribute a new method to give non-trivial results in transcendence theory. (This already rules out a lot of possible approaches to solve the Collatz conjecture.)

By using more sophisticated tools in additive combinatorics, one can improve the above proposition (though it is still well short of the transcendence theory bound (7)):

Proposition 7 Suppose the weak Collatz conjecture is true. Then for any natural numbers {a, k} with {2^a > 3^k}, one has {2^a-3^k \gg (1+\epsilon)^k} for some absolute constant {\epsilon > 0}.

Proof: (Informal sketch only) Suppose not, then we can find {a, k} with {q := 2^a-3^k} of size {(1+o(1))^k = \exp(o(k))}. We form the set {S} as before, which contains parallelepipeds in {{\bf Z}/q{\bf Z}} of large dimension {d \gg k} that avoid {0}. We can count the number of times {0} occurs in one of these parallelepipeds by a standard Fourier-analytic computation involving Riesz products (see Chapter 7 of my book with Van Vu, or this recent preprint of Maples). Using this Fourier representation, the fact that this parallelepiped avoids {0} (and the fact that {q = \exp(o(k)) = \exp(o(d))}) forces the generators {v_1,\ldots,v_d} to be concentrated in a Bohr set, in that one can find a non-zero frequency {\xi \in {\bf Z}/q{\bf Z}} such that {(1-o(1))d} of the {d} generators lie in the set {\{ v: \xi v = o(q) \hbox{ mod } q \}}. However, one can choose the generators to essentially have the structure of a (generalised) geometric progression (up to scaling, it resembles something like {2^i 3^{\lfloor \alpha i \rfloor}} for {i} ranging over a generalised arithmetic progression, and {\alpha} a fixed irrational), and one can show that such progressions cannot be concentrated in Bohr sets (this is similar in spirit to the exponential sum estimates of Bourgain on approximate multiplicative subgroups of {{\bf Z}/q{\bf Z}}, though one can use more elementary methods here due to the very strong nature of the Bohr set concentration (being of the “{99\%} concentration” variety rather than the “{1\%} concentration”).). This furnishes the required contradiction. \Box

Thus we see that any proposed proof of the Collatz conjecture must either use transcendence theory, or introduce new techniques that are powerful enough to create exponential separation between powers of {2} and powers of {3}.

Unfortunately, once one uses the transcendence theory bound (7), the size {q} of the cyclic group {{\bf Z}/q{\bf Z}} becomes larger than the volume of any cube in {S}, and Littlewood-Offord techniques are no longer of much use (they can be used to show that {S} is highly equidistributed in {{\bf Z}/q{\bf Z}}, but this does not directly give any way to prevent {S} from containing {0}).

One possible toy model problem for the (weak) Collatz conjecture is a conjecture of Erdos asserting that for {n>8}, the base {3} representation of {2^n} contains at least one {2}. (See this paper of Lagarias for some work on this conjecture and on related problems.) To put it another way, the conjecture asserts that there are no integer solutions to

\displaystyle  2^n = 3^{a_1} + 3^{a_2} + \ldots + 3^{a_k}

with {n > 8} and {0 \leq a_1 < \ldots < a_k}. (When {n=8}, of course, one has {2^8 = 3^0 + 3^1 + 3^2 + 3^5}.) In this form we see a resemblance to Conjecture 3, but it looks like a simpler problem to attack (though one which is still a fair distance beyond what one can do with current technology). Note that one has a similar heuristic support for this conjecture as one does for Proposition 3; a number of magnitude {2^n} has about {n \frac{\log 2}{\log 3}} base {3} digits, so the heuristic probability that none of these digits are equal to {2} is {3^{-n\frac{\log 2}{\log 3}} = 2^{-n}}, which is absolutely summable.

I’ve been focusing my blog posts recently on the mathematics around Hilbert’s fifth problem (is every locally Euclidean group a Lie group?), but today, I will be discussing another of Hilbert’s problems, namely Hilbert’s seventh problem, on the transcendence of powers {a^b} of two algebraic numbers {a,b}. (I am not randomly going through Hilbert’s list, by the way; I hope to explain my interest in the seventh problem in a later post.) This problem was famously solved by Gelfond and Schneider in the 1930s:

Theorem 1 (Gelfond-Schneider theorem) Let {a, b} be algebraic numbers, with {a \neq 0,1} and {b} irrational. Then (any of the values of the possibly multi-valued expression) {a^b} is transcendental.

For sake of simplifying the discussion, let us focus on just one specific consequence of this theorem:

Corollary 2 {\frac{\log 2}{\log 3}} is transcendental.

Proof: If not, one could obtain a contradiction to the Gelfond-Schneider theorem by setting {a := 3} and {b := \frac{\log 2}{\log 3}}. (Note that {\frac{\log 2}{\log 3}} is clearly irrational, since {3^p \neq 2^q} for any integers {p,q} with {q} positive.) \Box

In the 1960s, Alan Baker established a major generalisation of the Gelfond-Schneider theorem known as Baker’s theorem, as part of his work in transcendence theory that later earned him a Fields Medal. Among other things, this theorem provided explicit quantitative bounds on exactly how transcendental quantities such as {\frac{\log 2}{\log 3}} were. In particular, it gave a strong bound on how irrational such quantities were (i.e. how easily they were approximable by rationals). Here, in particular, is one special case of Baker’s theorem:

Proposition 3 (Special case of Baker’s theorem) For any integers {p, q} with {q} positive, one has

\displaystyle  |\frac{\log 2}{\log 3} - \frac{p}{q}| \geq c \frac{1}{q^C}

for some absolute (and effectively computable) constants {c, C > 0}.

This theorem may be compared with (the easily proved) Liouville’s theorem on diophantine approximation, which asserts that if {\alpha} is an irrational algebraic number of degree {d}, then

\displaystyle  |\alpha - \frac{p}{q}| \geq c \frac{1}{q^d}

for all {p,q} with {q} positive, and some effectively computable {c>0}, and (the more significantly difficult) Thue-Siegel-Roth theorem, which under the same hypotheses gives the bound

\displaystyle  |\alpha - \frac{p}{q}| \geq c_\epsilon \frac{1}{q^{2+\epsilon}}

for all {\epsilon>0}, all {p,q} with {q} positive and an ineffective constant {c_\epsilon>0}. Finally, one should compare these results against Dirichlet’s theorem on Diophantine approximation, which asserts that for any real number {\alpha} one has

\displaystyle  |\alpha - \frac{p}{q}| < \frac{1}{q^2}

for infinitely many {p,q} with {q} positive. (The reason the Thue-Siegel-Roth theorem is ineffective is because it relies heavily on the dueling conspiracies argument, i.e. playing off multiple “conspiracies” {\alpha \approx \frac{p}{q}} against each other; the other results however only focus on one approximation at a time and thus avoid ineffectivity.)

Proposition 3 easily implies the following separation property between powers of {2} and powers of {3}:

Corollary 4 (Separation between powers of {2} and powers of {3}) For any positive integers {p, q} one has

\displaystyle  |3^p - 2^q| \geq \frac{c}{q^C} 3^p

for some effectively computable constants {c, C > 0} (which may be slightly different from those in Proposition 3).

Indeed, this follows quickly from Proposition 3, the identity

\displaystyle  3^p - 2^q = 3^p ( 1 - 3^{q (\frac{\log 2}{\log 3} - \frac{p}{q})}) \ \ \ \ \ (1)

and some elementary estimates.

In particular, the gap between powers of three {3^p} and powers of two {2^q} grows exponentially in the exponents {p,q}. I do not know of any other way to establish this fact other than essentially going through some version of Baker’s argument (which will be given below).

For comparison, by exploiting the trivial (yet fundamental) integrality gap – the obvious fact that if an integer {n} is non-zero, then its magnitude is at least {1} – we have the trivial bound

\displaystyle  |3^p - 2^q| \geq 1

for all positive integers {p, q} (since, from the fundamental theorem of arithmetic, {3^p-2^q} cannot vanish). Putting this into (1) we obtain a very weak version of Proposition 3, that only gives exponential bounds instead of polynomial ones:

Proposition 5 (Trivial bound) For any integers {p, q} with {q} positive, one has

\displaystyle  |\frac{\log 2}{\log 3} - \frac{p}{q}| \geq c \frac{1}{2^q}

for some absolute (and effectively computable) constant {c > 0}.

The proof of Baker’s theorem (or even of the simpler special case in Proposition 3) is largely elementary (except for some very basic complex analysis), but is quite intricate and lengthy, as a lot of careful book-keeping is necessary in order to get a bound as strong as that in Proposition 3. To illustrate the main ideas, I will prove a bound that is weaker than Proposition 3, but still significantly stronger than Proposition 5, and whose proof already captures many of the key ideas of Baker:

Proposition 6 (Weak special case of Baker’s theorem) For any integers {p, q} with {q > 1}, one has

\displaystyle  |\frac{\log 2}{\log 3} - \frac{p}{q}| \geq \exp( - C \log^{C'} q )

for some absolute constants {C, C' > 0}.

Note that Proposition 3 is equivalent to the assertion that one can take {C'=1} (and {C} effective) in the above proposition.

The proof of Proposition 6 can be made effective (for instance, it is not too difficult to make the {C'} close to {2}); however, in order to simplify the exposition (and in particular, to use some nonstandard analysis terminology to reduce the epsilon management), I will establish Proposition 6 with ineffective constants {C, C'}.

Like many other results in transcendence theory, the proof of Baker’s theorem (and Proposition 6) rely on what we would nowadays call the polynomial method – to play off upper and lower bounds on the complexity of polynomials that vanish (or nearly vanish) to high order on a specified set of points. (I have discussed the polynomial method in relation to problems in incidence geometry in several previous blog posts.) In the specific case of Proposition 6, the points in question are of the form

\displaystyle  \Gamma_N := \{ (2^n, 3^n): n = 1,\ldots,N \} \subset {\bf R}^2

for some large integer {N}. On the one hand, the irrationality of {\frac{\log 2}{\log 3}} ensures that the curve

\displaystyle \gamma := \{ (2^t, 3^t): t \in {\bf R} \}

is not algebraic, and so it is difficult for a polynomial {P} of controlled complexity to vanish (or nearly vanish) to high order at all the points of {\Gamma_N}; the trivial bound in Proposition 5 allows one to make this statement more precise. (Here, “complexity” of a polynomial is an informal term referring both to the degree of the polynomial, and the height of the coefficients, which in our application will essentially be integers up to some normalisation factors.) On the other hand, if Proposition 6 failed, then {\frac{\log 2}{\log 3}} is close to a rational, which by Taylor expansion makes {\gamma} close to an algebraic curve over the rationals (up to some rescaling by factors such as {\log 2} and {\log 3}) at each point of {\Gamma_N}. This, together with a pigeonholing argument, allows one to find a polynomial {P} of reasonably controlled complexity to (nearly) vanish to high order at every point of {\Gamma_N}.

These observations, by themselves, are not sufficient to get beyond the trivial bound in Proposition 5. However, Baker’s key insight was to exploit the integrality gap to bootstrap the (near) vanishing of {P} on a set {\Gamma_N} to imply near-vanishing of {P} on a larger set {\Gamma_{N'}} with {N'>N}. The point is that if a polynomial {P} of controlled degree and size (nearly) vanishes to higher order on a lot of points on an analytic curve such as {\gamma}, then it will also be fairly small on many other points in {\gamma} as well. (To quantify this statement efficiently, it is convenient to use the tools of complex analysis, which are particularly well suited to understand zeroes (or small values) of polynomials.) But then, thanks to the integrality gap (and the controlled complexity of {P}), we can amplify “fairly small” to “very small”.

Using this observation and an iteration argument, Baker was able to take a polynomial of controlled complexity {P} that nearly vanished to high order on a relatively small set {\Gamma_{N_0}}, and bootstrap that to show near-vanishing on a much larger set {\Gamma_{N_k}}. This bootstrap allows one to dramatically bridge the gap between the upper and lower bounds on the complexity of polynomials that nearly vanish to a specified order on a given {\Gamma_N}, and eventually leads to Proposition 6 (and, with much more care and effort, to Proposition 3).

Below the fold, I give the details of this argument. My treatment here is inspired by this expose of Serre, and these lecture notes of Soundararajan (as transcribed by Ian Petrow).

Read the rest of this entry »

One of the fundamental structures in modern mathematics is that of a group. Formally, a group is a set {G = (G,1,\cdot,()^{-1})} equipped with an identity element {1 = 1_G \in G}, a multiplication operation {\cdot: G \times G \rightarrow G}, and an inversion operation {()^{-1}: G \rightarrow G} obeying the following axioms:

  • (Closure) If {g, h \in G}, then {g \cdot h} and {g^{-1}} are well-defined and lie in {G}. (This axiom is redundant from the above description, but we include it for emphasis.)
  • (Associativity) If {g, h, k \in G}, then {(g \cdot h) \cdot k = g \cdot (h \cdot k)}.
  • (Identity) If {g \in G}, then {g \cdot 1 = 1 \cdot g = g}.
  • (Inverse) If {g \in G}, then {g \cdot g^{-1} = g^{-1} \cdot g = 1}.

One can also consider additive groups {G = (G,0,+,-)} instead of multiplicative groups, with the obvious changes of notation. By convention, additive groups are always understood to be abelian, so it is convenient to use additive notation when one wishes to emphasise the abelian nature of the group structure. As usual, we often abbreviate {g \cdot h} by {gh} (and {1_G} by {1}) when there is no chance of confusion.

If furthermore {G} is equipped with a topology, and the group operations {\cdot, ()^{-1}} are continuous in this topology, then {G} is a topological group. Any group can be made into a topological group by imposing the discrete topology, but there are many more interesting examples of topological groups, such as Lie groups, in which {G} is not just a topological space, but is in fact a smooth manifold (and the group operations are not merely continuous, but also smooth).

There are many naturally occuring group-like objects that obey some, but not all, of the axioms. For instance, monoids are required to obey the closure, associativity, and identity axioms, but not the inverse axiom. If we also drop the identity axiom, we end up with a semigroup. Groupoids do not necessarily obey the closure axiom, but obey (versions of) the associativity, identity, and inverse axioms. And so forth.

Another group-like concept is that of a local topological group (or local group, for short), which is essentially a topological group with the closure axiom omitted (but do not obey the same axioms set as groupoids); they arise primarily in the study of local properties of (global) topological groups, and also in the study of approximate groups in additive combinatorics. Formally, a local group {G = (G, \Omega, \Lambda, 1, \cdot, ()^{-1})} is a topological space {G} equipped with an identity element {1 \in G}, a partially defined but continuous multiplication operation {\cdot: \Omega \rightarrow G} for some domain {\Omega \subset G \times G}, and a partially defined but continuous inversion operation {()^{-1}: \Lambda \rightarrow G}, where {\Lambda \subset G}, obeying the following axioms:

  • (Local closure) {\Omega} is an open neighbourhood of {G \times \{1\} \cup \{1\} \times G}, and {\Lambda} is an open neighbourhood of {1}.
  • (Local associativity) If {g, h, k \in G} are such that {(g \cdot h) \cdot k} and {g \cdot (h \cdot k)} are both well-defined, then they are equal. (Note however that it may be possible for one of these products to be defined but not the other, in contrast for instance with groupoids.)
  • (Identity) For all {g \in G}, {g \cdot 1 = 1 \cdot g = g}.
  • (Local inverse) If {g \in G} and {g^{-1}} is well-defined, then {g \cdot g^{-1} = g^{-1} \cdot g = 1}. (In particular this, together with the other axioms, forces {1^{-1} = 1}.)

We will often refer to ordinary groups as global groups (and topological groups as global topological groups) to distinguish them from local groups. Every global topological group is a local group, but not conversely.

One can consider discrete local groups, in which the topology is the discrete topology; in this case, the openness and continuity axioms in the definition are automatic and can be omitted. At the other extreme, one can consider local Lie groups, in which the local group {G} has the structure of a smooth manifold, and the group operations are smooth. We can also consider symmetric local groups, in which {\Lambda=G} (i.e. inverses are always defined). Symmetric local groups have the advantage of local homogeneity: given any {g \in G}, the operation of left-multiplication {x \mapsto gx} is locally inverted by {x \mapsto g^{-1} x} near the identity, thus giving a homeomorphism between a neighbourhood of {g} and a neighbourhood of the identity; in particular, we see that given any two group elements {g, h} in a symmetric local group {G}, there is a homeomorphism between a neighbourhood of {g} and a neighbourhood of {h}. (If the symmetric local group is also Lie, then these homeomorphisms are in fact diffeomorphisms.) This local homogeneity already simplifies a lot of the possible topology of symmetric local groups, as it basically means that the local topological structure of such groups is determined by the local structure at the origin. (For instance, all connected components of a local Lie group necessarily have the same dimension.) It is easy to see that any local group has at least one symmetric open neighbourhood of the identity, so in many situations we can restrict to the symmetric case without much loss of generality.

A prime example of a local group can be formed by restricting any global topological group {G} to an open neighbourhood {U \subset G} of the identity, with the domains

\displaystyle  \Omega := \{ (g,h) \in U: g \cdot h \in U \}

and

\displaystyle  \Lambda := \{ g \in U: g^{-1} \in U \};

one easily verifies that this gives {U} the structure of a local group (which we will sometimes call {G\downharpoonright_U} to emphasise the original group {G}). If {U} is symmetric (i.e. {U^{-1}=U}), then we in fact have a symmetric local group. One can also restrict local groups {G} to open neighbourhoods {U} to obtain a smaller local group {G\downharpoonright_U} by the same procedure (adopting the convention that statements such as {g \cdot h \in U} or {g^{-1} \in U} are considered false if the left-hand side is undefined). (Note though that if one restricts to non-open neighbourhoods of the identity, then one usually does not get a local group; for instance {[-1,1]} is not a local group (why?).)

Finite subsets of (Hausdorff) groups containing the identity can be viewed as local groups. This point of view turns out to be particularly useful for studying approximate groups in additive combinatorics, a point which I hope to expound more on later. Thus, for instance, the discrete interval {\{-9,\ldots,9\} \subset {\bf Z}} is an additive symmetric local group, which informally might model an adding machine that can only handle (signed) one-digit numbers. More generally, one can view a local group as an object that behaves like a group near the identity, but for which the group laws (and in particular, the closure axiom) can start breaking down once one moves far enough away from the identity.

One can formalise this intuition as follows. Let us say that a word {g_1 \ldots g_n} in a local group {G} is well-defined in {G} (or well-defined, for short) if every possible way of associating this word using parentheses is well-defined from applying the product operation. For instance, in order for {abcd} to be well-defined, {((ab)c)d}, {(a(bc))d}, {(ab)(cd)}, {a(b(cd))}, and {a((bc)d)} must all be well-defined. In the preceding example {\{-9,\ldots,9\}}, {-2+6+5} is not well-defined because one of the ways of associating this sum, namely {-2+(6+5)}, is not well-defined (even though {(-2+6)+5} is well-defined).

Exercise 1 (Iterating the associative law)

  • Show that if a word {g_1 \ldots g_n} in a local group is well-defined, then all ways of associating this word give the same answer, and so we can uniquely evaluate {g_1 \ldots g_n} as an element in {G}.
  • Give an example of a word {g_1 \ldots g_n} in a local group which has two ways of being associated that are both well-defined, but give different answers. (Hint: the local associativity axiom prevents this from happening for {n \leq 3}, so try {n=4}. A small discrete local group will already suffice to give a counterexample; verifying the local group axioms are easier if one makes the domain of definition of the group operations as small as one can get away with while still having the counterexample.)

Exercise 2 Show that the number of ways to associate a word {g_1 \ldots g_n} is given by the Catalan number {C_{n-1} := \frac{1}{n} \binom{2n-2}{n-1}}.

Exercise 3 Let {G} be a local group, and let {m \geq 1} be an integer. Show that there exists a symmetric open neighbourhood {U_m} of the identity such that every word of length {m} in {U_m} is well-defined in {G} (or more succinctly, {U_m^m} is well-defined). (Note though that these words will usually only take values in {G}, rather than in {U_m}, and also the sets {U_m} tend to become smaller as {m} increases.)

In many situations (such as when one is investigating the local structure of a global group) one is only interested in the local properties of a (local or global) group. We can formalise this by the following definition. Let us call two local groups {G = (G, \Omega, \Lambda, 1_G, \cdot, ()^{-1})} and {G' = (G', \Omega', \Lambda', 1_{G'}, \cdot, ()^{-1})} locally identical if they have a common restriction, thus there exists a set {U \subset G \cap G'} such that {G\downharpoonright_U = G'\downharpoonright_U} (thus, {1_G = 1_{G'}}, and the topology and group operations of {G} and {G'} agree on {U}). This is easily seen to be an equivalence relation. We call an equivalence class {[G]} of local groups a group germ.

Let {{\mathcal P}} be a property of a local group (e.g. abelianness, connectedness, compactness, etc.). We call a group germ locally {{\mathcal P}} if every local group in that germ has a restriction that obeys {{\mathcal P}}; we call a local or global group {G} locally {{\mathcal P}} if its germ is locally {{\mathcal P}} (or equivalently, every open neighbourhood of the identity in {G} contains a further neighbourhood that obeys {{\mathcal P}}). Thus, the study of local properties of (local or global) groups is subsumed by the study of group germs.

Exercise 4

  • Show that the above general definition is consistent with the usual definitions of the properties “connected” and “locally connected” from point-set topology.
  • Strictly speaking, the above definition is not consistent with the usual definitions of the properties “compact” and “local compact” from point-set topology because in the definition of local compactness, the compact neighbourhoods are certainly not required to be open. Show however that the point-set topology notion of “locally compact” is equivalent, using the above conventions, to the notion of “locally precompact inside of an ambient local group”. Of course, this is a much more clumsy terminology, and so we shall abuse notation slightly and continue to use the standard terminology “locally compact” even though it is, strictly speaking, not compatible with the above general convention.
  • Show that a local group is discrete if and only if it is locally trivial.
  • Show that a connected global group is abelian if and only if it is locally abelian. (Hint: in a connected global group, the only open subgroup is the whole group.)
  • Show that a global topological group is first-countable if and only if it is locally first countable. (By the Birkhoff-Kakutani theorem, this implies that such groups are metrisable if and only if they are locally metrisable.)
  • Let {p} be a prime. Show that the solenoid group {{\bf Z}_p \times {\bf R} / {\bf Z}^\Delta}, where {{\bf Z}_p} is the {p}-adic integers and {{\bf Z}^\Delta := \{ (n,n): n \in {\bf Z}\}} is the diagonal embedding of {{\bf Z}} inside {{\bf Z}_p \times {\bf R}}, is connected but not locally connected.

Remark 1 One can also study the local properties of groups using nonstandard analysis. Instead of group germs, one works (at least in the case when {G} is first countable) with the monad {o(G)} of the identity element {1_G} of {G}, defined as the nonstandard group elements {g = \lim_{n \rightarrow \alpha} g_n} in {{}^* G} that are infinitesimally close to the origin in the sense that they lie in every standard neighbourhood of the identity. The monad {o(G)} is closely related to the group germ {[G]}, but has the advantage of being a genuine (global) group, as opposed to an equivalence class of local groups. It is possible to recast most of the results here in this nonstandard formulation; see e.g. the classic text of Robinson. However, we will not adopt this perspective here.

A useful fact to know is that Lie structure is local. Call a (global or local) topological group Lie if it can be given the structure of a (global or local) Lie group.

Lemma 1 (Lie is a local property) A global topological group {G} is Lie if and only if it is locally Lie. The same statement holds for local groups {G} as long as they are symmetric.

We sketch a proof of this lemma below the fold. One direction is obvious, as the restriction a global Lie group to an open neighbourhood of the origin is clearly a local Lie group; for instance, the continuous interval {(-10,10) \subset {\bf R}} is a symmetric local Lie group. The converse direction is almost as easy, but (because we are not assuming {G} to be connected) requires one non-trivial fact, namely that local homomorphisms between local Lie groups are automatically smooth; details are provided below the fold.

As with so many other basic classes of objects in mathematics, it is of fundamental importance to specify and study the morphisms between local groups (and group germs). Given two local groups {G, G'}, we can define the notion of a (continuous) homomorphism {\phi: G \rightarrow G'} between them, defined as a continuous map with

\displaystyle  \phi(1_G) = 1_{G'}

such that whenever {g, h \in G} are such that {gh} is well-defined, then {\phi(g)\phi(h)} is well-defined and equal to {\phi(gh)}; similarly, whenever {g \in G} is such that {g^{-1}} is well-defined, then {\phi(g)^{-1}} is well-defined and equal to {\phi(g^{-1})}. (In abstract algebra, the continuity requirement is omitted from the definition of a homomorphism; we will call such maps discrete homomorphisms to distinguish them from the continuous ones which will be the ones studied here.)

It is often more convenient to work locally: define a local (continuous) homomorphism {\phi: U \rightarrow G'} from {G} to {G'} to be a homomorphism from an open neighbourhood {U} of the identity to {G'}. Given two local homomorphisms {\phi: U \rightarrow G'}, {\tilde \phi: \tilde U \rightarrow \tilde G'} from one pair of locally identical groups {G, \tilde G} to another pair {G', \tilde G'}, we say that {\phi, \phi'} are locally identical if they agree on some open neighbourhood of the identity in {U \cap \tilde U'} (note that it does not matter here whether we require openness in {G}, in {\tilde G}, or both). An equivalence class {[\phi]} of local homomorphisms will be called a germ homomorphism (or morphism for short) from the group germ {[G]} to the group germ {[G']}.

Exercise 5 Show that the class of group germs, equipped with the germ homomorphisms, becomes a category. (Strictly speaking, because group germs are themselves classes rather than sets, the collection of all group germs is a second-order class rather than a class, but this set-theoretic technicality can be resolved in a number of ways (e.g. by restricting all global and local groups under consideration to some fixed “universe”) and should be ignored for this exercise.)

As is usual in category theory, once we have a notion of a morphism, we have a notion of an isomorphism: two group germs {[G], [G']} are isomorphic if there are germ homomorphisms {\phi: [G] \rightarrow [G']}, {\psi: [G'] \rightarrow [G]} that invert each other. Lifting back to local groups, the associated notion is that of local isomorphism: two local groups {G, G'} are locally isomorphic if there exist local isomorphisms {\phi: U \rightarrow G'} and {\psi: U' \rightarrow G} from {G} to {G'} and from {G'} to {G} that locally invert each other, thus {\psi(\phi(g))=g} for {g \in G} sufficiently close to {1_G}, and {\phi(\psi(g))} for {g' \in G'} sufficiently close to {1_{G'}}. Note that all local properties of (global or local) groups that can be defined purely in terms of the group and topological structures will be preserved under local isomorphism. Thus, for instance, if {G, G'} are locally isomorphic local groups, then {G} is locally connected iff {G'} is, {G} is locally compact iff {G'} is, and (by Lemma 1) {G} is Lie iff {G'} is.

Exercise 6

  • Show that the additive global groups {{\bf R}/{\bf Z}} and {{\bf R}} are locally isomorphic.
  • Show that every locally path-connected group {G} is locally isomorphic to a path-connected, simply connected group.
  • — 1. Lie’s third theorem —

    Lie’s fundamental theorems of Lie theory link the Lie group germs to Lie algebras. Observe that if {[G]} is a locally Lie group germ, then the tangent space {{\mathfrak g} := T_1 G} at the identity of this germ is well-defined, and is a finite-dimensional vector space. If we choose {G} to be symmetric, then {{\mathfrak g}} can also be identified with the left-invariant (say) vector fields on {G}, which are first-order differential operators on {C^\infty(M)}. The Lie bracket for vector fields then endows {{\mathfrak g}} with the structure of a Lie algebra. It is easy to check that every morphism {\phi: [G] \rightarrow [H]} of locally Lie germs gives rise (via the derivative map at the identity) to a morphism {D\phi(1): {\mathfrak g} \rightarrow {\mathfrak h}} of the associated Lie algebras. From the Baker-Campbell-Hausdorff formula (which is valid for local Lie groups, as discussed in this previous post) we conversely see that {D\phi(1)} uniquely determines the germ homomorphism {\phi}. Thus the derivative map provides a covariant functor from the category of locally Lie group germs to the category of (finite-dimensional) Lie algebras. In fact, this functor is an isomorphism, which is part of a fact known as Lie’s third theorem:

    Theorem 2 (Lie’s third theorem) For this theorem, all Lie algebras are understood to be finite dimensional (and over the reals).

    1. Every Lie algebra {{\mathfrak g}} is the Lie algebra of a local Lie group germ {[G]}, which is unique up to germ isomorphism (fixing {{\mathfrak g}}).
    2. Every Lie algebra {{\mathfrak g}} is the Lie algebra of some global connected, simply connected Lie group {G}, which is unique up to Lie group isomorphism (fixing {{\mathfrak g}}).
    3. Every homomorphism {\Phi: {\mathfrak g} \rightarrow {\mathfrak h}} between Lie algebras is the derivative of a unique germ homomorphism {\phi: [G] \rightarrow [H]} between the associated local Lie group germs.
    4. Every homomorphism {\Phi: {\mathfrak g} \rightarrow {\mathfrak h}} between Lie algebras is the derivative of a unique Lie group homomorphism {\phi: G \rightarrow H} between the associated global connected, simply connected, Lie groups.
    5. Every local Lie group germ is the germ of a global connected, simply connected Lie group {G}, which is unique up to Lie group isomorphism. In particular, every local Lie group is locally isomorphic to a global Lie group.

    We record the (standard) proof of this theorem below the fold, which is ultimately based on Ado’s theorem and the Baker-Campbell-Hausdorff formula. Lie’s third theorem (which, actually, was proven in full generality by Cartan) demonstrates the equivalence of three categories: the category of finite-dimensonal Lie algebras, the category of local Lie group germs, and the category of connected, simply connected Lie groups.

    — 2. Globalising a local group —

    Many properties of a local group improve after passing to a smaller neighbourhood of the identity. Here are some simple examples:

    Exercise 7 Let {G} be a local group.

    • Give an example to show that {G} does not necessarily obey the cancellation laws

      \displaystyle  gk=hk \implies g=h; \quad kg=kh \implies g=h \ \ \ \ \ (1)

      for {g,h,k \in G} (with the convention that statements such as {gk=hk} are false if either side is undefined). However, show that there exists an open neighbourhood {U} of {G} within which the cancellation law holds.

    • Repeat the previous part, but with the cancellation law (1) replaced by the inversion law

      \displaystyle  (gh)^{-1} = h^{-1} g^{-1} \ \ \ \ \ (2)

      for any {g,h \in G} for which both sides are well-defined.

    • Repeat the previous part, but with the inversion law replaced by the involution law

      \displaystyle  (g^{-1})^{-1} = g \ \ \ \ \ (3)

      for any {g} for which the left-hand side is well-defined.

    Note that the counterexamples in the above exercise demonstrate that not every local group is the restriction of a global group, because global groups (and hence, their restrictions) always obey the cancellation law (1), the inversion law (2), and the involution law (3). Another way in which a local group can fail to come from a global group is if it contains relations which can interact in a “global’ way to cause trouble, in a fashion which is invisible at the local level. For instance, consider the open unit cube {(-1,1)^3}, and consider four points {a_1, a_2, a_3, a_4} in this cube that are close to the upper four corners {(1,1,1), (1,1,-1), (1,-1,1), (1,-1,-1)} of this cube respectively. Define an equivalence relation {\sim} on this cube by setting {x \sim y} if {x, y \in (-1,1)^3} and {x-y} is equal to either {0} or {\pm 2a_i} for some {i=1,\ldots,4}. Note that this indeed an equivalence relation if {a_1,a_2,a_3,a_4} are close enough to the corners (as this forces all non-trivial combinations {\pm 2a_i \pm 2a_j} to lie outside the doubled cube {(-2,2)^3}). The quotient space {(-1,1)^3/\sim} (which is a cube with bits around opposite corners identified together) can then be seen to be a symmetric additive local Lie group, but will usually not come from a global group. Indeed, it is not hard to see that if {(-1,1)^3/\sim} is the restriction of a global group {G}, then {G} must be a Lie group with Lie algebra {{\bf R}^3} (by Lemma 1), and so the connected component {G^\circ} of {G} containing the identity is isomorphic to {{\bf R}^3/\Gamma} for some sublattice {\Gamma} of {{\bf R}^3} that contains {a_1,a_2,a_3,a_4}; but for generic {a_1,a_2,a_3,a_4}, there is no such lattice, as the {a_i} will generate a dense subset of {{\bf R}^3}. (The situation here is somewhat analogous to a number of famous Escher prints, such as Ascending and Descending, in which the geometry is locally consistent but globally inconsistent.) We will give this sort of argument in more detail below the fold (see the proof of Proposition 7).

    Nevertheless, the space {(-1,1)^3/\sim} is still locally isomorphic to a global Lie group, namely {{\bf R}^3}; for instance, the open neighbourhood {(-0.5,0.5)^3/\sim} is isomorphic to {(-0.5,0.5)^3}, which is an open neighbourhood of {{\bf R}^3}. More generally, Lie’s third theorem tells us that any local Lie group is locally isomorphic to a global Lie group.

    Let us call a local group globalisable if it is locally isomorphic to a global group; thus Lie’s third theorem tells us that every local Lie group is globalisable. Thanks to Goldbring’s solution to the local version of Hilbert’s fifth problem, we also know that locally Euclidean local groups are globalisable. A modification of this argument by van den Dries and Goldbring shows in fact that every locally compact local group is globalisable.

    In view of these results, it is tempting to conjecture that all local groups are globalisable;; among other things, this would simplify the proof of Lie’s third theorem (and of the local version of Hilbert’s fifth problem). Unfortunately, this claim as stated is false:

    Theorem 3 There exists local groups {G} which are not globalisable.

    The counterexamples used to establish Theorem 3 are remarkably delicate; the first example I know of is due to van Est and Korthagen. One reason for this, of course, is that the previous results prevents one from using any local Lie group, or even a locally compact group as a counterexample. We will present a (somewhat complicated) example below, based on the unit ball in the infinite-dimensional Banach space {\ell^\infty({\bf N}^2)}.

    However, there are certainly many situations in which we can globalise a local group. For instance, this is the case if one has a locally faithful representation of that local group inside a global group:

    Lemma 4 (Faithful representation implies globalisability) Let {G} be a local group, and suppose there exists an injective local homomorphism {\phi: U \rightarrow H} from {G} into a global topological group {H} with {U} symmetric. Then {U} is isomorphic to the restriction of a global topological group to an open neighbourhood of the identity; in particular, {G} is globalisable.

    The material here is based in part on this paper of Olver and this paper of Goldbring.

    Read the rest of this entry »

    The classical formulation of Hilbert’s fifth problem asks whether topological groups that have the topological structure of a manifold, are necessarily Lie groups. This is indeed, the case, thanks to following theorem of Gleason and Montgomery-Zippin:

    Theorem 1 (Hilbert’s fifth problem) Let {G} be a topological group which is locally Euclidean. Then {G} is isomorphic to a Lie group.

    We have discussed the proof of this result, and of related results, in previous posts. There is however a generalisation of Hilbert’s fifth problem which remains open, namely the Hilbert-Smith conjecture, in which it is a space acted on by the group which has the manifold structure, rather than the group itself:

    Conjecture 2 (Hilbert-Smith conjecture) Let {G} be a locally compact topological group which acts continuously and faithfully (or effectively) on a connected finite-dimensional manifold {X}. Then {G} is isomorphic to a Lie group.

    Note that Conjecture 2 easily implies Theorem 1 as one can pass to the connected component {G^\circ} of a locally Euclidean group (which is clearly locally compact), and then look at the action of {G^\circ} on itself by left-multiplication.

    The hypothesis that the action is faithful (i.e. each non-identity group element {g \in G \backslash \{\hbox{id}\}} acts non-trivially on {X}) cannot be completely eliminated, as any group {G} will have a trivial action on any space {X}. The requirement that {G} be locally compact is similarly necessary: consider for instance the diffeomorphism group {\hbox{Diff}(S^1)} of, say, the unit circle {S^1}, which acts on {S^1} but is infinite dimensional and is not locally compact (with, say, the uniform topology). Finally, the connectedness of {X} is also important: the infinite torus {G = ({\bf R}/{\bf Z})^{\bf N}} (with the product topology) acts faithfully on the disconnected manifold {X := {\bf R}/{\bf Z} \times {\bf N}} by the action

    \displaystyle  (g_n)_{n \in {\bf N}} (\theta, m) := (\theta + g_m, m).

    The conjecture in full generality remains open. However, there are a number of partial results. For instance, it was observed by Montgomery and Zippin that the conjecture is true for transitive actions, by a modification of the argument used to establish Theorem 1. This special case of the Hilbert-Smith conjecture (or more precisely, a generalisation thereof in which “finite-dimensional manifold” was replaced by “locally connected locally compact finite-dimensional”) was used in Gromov’s proof of his famous theorem on groups of polynomial growth. I record the argument of Montgomery and Zippin below the fold.

    Another partial result is the reduction of the Hilbert-Smith conjecture to the {p}-adic case. Indeed, it is known that Conjecture 2 is equivalent to

    Conjecture 3 (Hilbert-Smith conjecture for {p}-adic actions) It is not possible for a {p}-adic group {{\bf Z}_p} to act continuously and effectively on a connected finite-dimensional manifold {X}.

    The reduction to the {p}-adic case follows from the structural theory of locally compact groups (specifically, the Gleason-Yamabe theorem discussed in previous posts) and some results of Newman that sharply restrict the ability of periodic actions on a manifold {X} to be close to the identity. I record this argument (which appears for instance in this paper of Lee) below the fold also.

    Read the rest of this entry »

    One of the most well known problems from ancient Greek mathematics was that of trisecting an angle by straightedge and compass, which was eventually proven impossible in 1837 by Pierre Wantzel, using methods from Galois theory.

    Formally, one can set up the problem as follows. Define a configuration to be a finite collection {{\mathcal C}} of points, lines, and circles in the Euclidean plane. Define a construction step to be one of the following operations to enlarge the collection {{\mathcal C}}:

    • (Straightedge) Given two distinct points {A, B} in {{\mathcal C}}, form the line {\overline{AB}} that connects {A} and {B}, and add it to {{\mathcal C}}.
    • (Compass) Given two distinct points {A, B} in {{\mathcal C}}, and given a third point {O} in {{\mathcal C}} (which may or may not equal {A} or {B}), form the circle with centre {O} and radius equal to the length {|AB|} of the line segment joining {A} and {B}, and add it to {{\mathcal C}}.
    • (Intersection) Given two distinct curves {\gamma, \gamma'} in {{\mathcal C}} (thus {\gamma} is either a line or a circle in {{\mathcal C}}, and similarly for {\gamma'}), select a point {P} that is common to both {\gamma} and {\gamma'} (there are at most two such points), and add it to {{\mathcal C}}.

    We say that a point, line, or circle is constructible by straightedge and compass from a configuration {{\mathcal C}} if it can be obtained from {{\mathcal C}} after applying a finite number of construction steps.

    Problem 1 (Angle trisection) Let {A, B, C} be distinct points in the plane. Is it always possible to construct by straightedge and compass from {A,B,C} a line {\ell} through {A} that trisects the angle {\angle BAC}, in the sense that the angle between {\ell} and {BA} is one third of the angle of {\angle BAC}?

    Thanks to Wantzel’s result, the answer to this problem is known to be “no” in general; a generic angle {\angle BAC} cannot be trisected by straightedge and compass. (On the other hand, some special angles can certainly be trisected by straightedge and compass, such as a right angle. Also, one can certainly trisect generic angles using other methods than straightedge and compass; see the Wikipedia page on angle trisection for some examples of this.)

    The impossibility of angle trisection stands in sharp contrast to the easy construction of angle bisection via straightedge and compass, which we briefly review as follows:

    1. Start with three points {A, B, C}.
    2. Form the circle {c_0} with centre {A} and radius {AB}, and intersect it with the line {\overline{AC}}. Let {D} be the point in this intersection that lies on the same side of {A} as {C}. ({D} may well be equal to {C}).
    3. Form the circle {c_1} with centre {B} and radius {AB}, and the circle {c_2} with centre {D} and radius {AB}. Let {E} be the point of intersection of {c_1} and {c_2} that is not {A}.
    4. The line {\ell := \overline{AE}} will then bisect the angle {\angle BAC}.

    The key difference between angle trisection and angle bisection ultimately boils down to the following trivial number-theoretic fact:

    Lemma 2 There is no power of {2} that is evenly divisible by {3}.

    Proof: Obvious by modular arithmetic, by induction, or by the fundamental theorem of arithmetic. \Box

    In contrast, there are of course plenty of powers of {2} that are evenly divisible by {2}, and this is ultimately why angle bisection is easy while angle trisection is hard.

    The standard way in which Lemma 2 is used to demonstrate the impossibility of angle trisection is via Galois theory. The implication is quite short if one knows this theory, but quite opaque otherwise. We briefly sketch the proof of this implication here, though we will not need it in the rest of the discussion. Firstly, Lemma 2 implies the following fact about field extensions.

    Corollary 3 Let {F} be a field, and let {E} be an extension of {F} that can be constructed out of {F} by a finite sequence of quadratic extensions. Then {E} does not contain any cubic extensions {K} of {F}.

    Proof: If E contained a cubic extension K of F, then the dimension of E over F would be a multiple of three. On the other hand, if E is obtained from F by a tower of quadratic extensions, then the dimension of E over F is a power of two. The claim then follows from Lemma 2. \Box

    To conclude the proof, one then notes that any point, line, or circle that can be constructed from a configuration {{\mathcal C}} is definable in a field obtained from the coefficients of all the objects in {{\mathcal C}} after taking a finite number of quadratic extensions, whereas a trisection of an angle {\angle ABC} will generically only be definable in a cubic extension of the field generated by the coordinates of {A,B,C}.

    The Galois theory method also allows one to obtain many other impossibility results of this type, most famously the Abel-Ruffini theorem on the insolvability of the quintic equation by radicals. For this reason (and also because of the many applications of Galois theory to number theory and other branches of mathematics), the Galois theory argument is the “right” way to prove the impossibility of angle trisection within the broader framework of modern mathematics. However, this argument has the drawback that it requires one to first understand Galois theory (or at least field theory), which is usually not presented until an advanced undergraduate algebra or number theory course, whilst the angle trisection problem requires only high-school level mathematics to formulate. Even if one is allowed to “cheat” and sweep several technicalities under the rug, one still needs to possess a fair amount of solid intuition about advanced algebra in order to appreciate the proof. (This was undoubtedly be one reason why, even after Wantzel’s impossibility result was published, a large amount of effort was still expended by amateur mathematicians to try to trisect a general angle.)

    In this post I would therefore like to present a different proof (or perhaps more accurately, a disguised version of the standard proof) of the impossibility of angle trisection by straightedge and compass, that avoids explicit mention of Galois theory (though it is never far beneath the surface). With “cheats”, the proof is actually quite simple and geometric (except for Lemma 2, which is still used at a crucial juncture), based on the basic geometric concept of monodromy; unfortunately, some technical work is needed however to remove these cheats.

    To describe the intuitive idea of the proof, let us return to the angle bisection construction, that takes a triple {A, B, C} of points as input and returns a bisecting line {\ell} as output. We iterate the construction to create a quadrisecting line {m}, via the following sequence of steps that extend the original bisection construction:

    1. Start with three points {A, B, C}.
    2. Form the circle {c_0} with centre {A} and radius {AB}, and intersect it with the line {\overline{AC}}. Let {D} be the point in this intersection that lies on the same side of {A} as {C}. ({D} may well be equal to {C}).
    3. Form the circle {c_1} with centre {B} and radius {AB}, and the circle {c_2} with centre {D} and radius {AB}. Let {E} be the point of intersection of {c_1} and {c_2} that is not {A}.
    4. Let {F} be the point on the line {\ell := \overline{AE}} which lies on {c_0}, and is on the same side of {A} as {E}.
    5. Form the circle {c_3} with centre {F} and radius {AB}. Let {G} be the point of intersection of {c_1} and {c_3} that is not {A}.
    6. The line {m := \overline{AG}} will then quadrisect the angle {\angle BAC}.

    Let us fix the points {A} and {B}, but not {C}, and view {m} (as well as intermediate objects such as {D}, {c_2}, {E}, {\ell}, {F}, {c_3}, {G}) as a function of {C}.

    Let us now do the following: we begin rotating {C} counterclockwise around {A}, which drags around the other objects {D}, {c_2}, {E}, {\ell}, {F}, {c_3}, {G} that were constructed by {C} accordingly. For instance, here is an early stage of this rotation process, when the angle {\angle BAC} has become obtuse:

    Now for the slightly tricky bit. We are going to keep rotating {C} beyond a half-rotation of {180^\circ}, so that {\angle BAC} now becomes a reflex angle. At this point, a singularity occurs; the point {E} collides into {A}, and so there is an instant in which the line {\ell = \overline{AE}} is not well-defined. However, this turns out to be a removable singularity (and the easiest way to demonstrate this will be to tap the power of complex analysis, as complex numbers can easily route around such a singularity), and we can blast through it to the other side, giving a picture like this:

    Note that we have now deviated from the original construction in that {F} and {E} are no longer on the same side of {A}; we are thus now working in a continuation of that construction rather than with the construction itself. Nevertheless, we can still work with this continuation (much as, say, one works with analytic continuations of infinite series such as {\sum_{n=1}^\infty \frac{1}{n^s}} beyond their original domain of definition).

    We now keep rotating {C} around {A}. Here, {\angle BAC} is approaching a full rotation of {360^\circ}:

    When {\angle BAC} reaches a full rotation, a different singularity occurs: {c_1} and {c_2} coincide. Nevertheless, this is also a removable singularity, and we blast through to beyond a full rotation:

    And now {C} is back where it started, as are {D}, {c_2}, {E}, and {\ell}… but the point {F} has moved, from one intersection point of {\ell \cap c_3} to the other. As a consequence, {c_3}, {G}, and {m} have also changed, with {m} being at right angles to where it was before. (In the jargon of modern mathematics, the quadrisection construction has a non-trivial monodromy.)

    But nothing stops us from rotating {C} some more. If we continue this procedure, we see that after two full rotations of {C} around {A}, all points, lines, and circles constructed from {A, B, C} have returned to their original positions. Because of this, we shall say that the quadrisection construction described above is periodic with period {2}.

    Similarly, if one performs an octisection of the angle {\angle BAC} by bisecting the quadrisection, one can verify that this octisection is periodic with period {4}; it takes four full rotations of {C} around {A} before the configuration returns to where it started. More generally, one can show

    Proposition 4 Any construction of straightedge and compass from the points {A,B,C} is periodic with period equal to a power of {2}.

    The reason for this, ultimately, is because any two circles or lines will intersect each other in at most two points, and so at each step of a straightedge-and-compass construction there is an ambiguity of at most {2! = 2}. Each rotation of {C} around {A} can potentially flip one of these points to the other, but then if one rotates again, the point returns to its original position, and then one can analyse the next point in the construction in the same fashion until one obtains the proposition.

    But now consider a putative trisection operation, that starts with an arbitrary angle {\angle BAC} and somehow uses some sequence of straightedge and compass constructions to end up with a trisecting line {\ell}:

    What is the period of this construction? If we continuously rotate {C} around {A}, we observe that a full rotations of {C} only causes the trisecting line {\ell} to rotate by a third of a full rotation (i.e. by {120^\circ}):

    Because of this, we see that the period of any construction that contains {\ell} must be a multiple of {3}. But this contradicts Proposition 4 and Lemma 2.

    Below the fold, I will make the above proof rigorous. Unfortunately, in doing so, I had to again leave the world of high-school mathematics, as one needs a little bit of algebraic geometry and complex analysis to resolve the issues with singularities that we saw in the above sketch. Still, I feel that at an intuitive level at least, this argument is more geometric and accessible than the Galois-theoretic argument (though anyone familiar with Galois theory will note that there is really not that much difference between the proofs, ultimately, as one has simply replaced the Galois group with a closely related monodromy group instead).

    Read the rest of this entry »

    A few days ago, I released a preprint entitled “Localisation and compactness properties of the Navier-Stokes global regularity problem“, discussed in this previous blog post.  As it turns out, I was somewhat impatient to finalise the paper and move on to other things, and the original preprint was still somewhat rough in places (contradicting my own advice on this matter), with a number of typos of minor to moderate severity.  But a bit more seriously, I discovered on a further proofreading that there was a subtle error in a component of the argument that I had believed to be routine – namely the persistence of higher regularity for mild solutions.   As a consequence, some of the implications stated in the first version were not exactly correct as stated; but they can be repaired by replacing a “bad” notion of global regularity for a certain class of data with a “good” notion.   I have completed (and proofread) an updated version of the ms, which should appear at the arXiv link of the paper in a day or two (and which I have also placed at this link).  (In the meantime, it is probably best not to read the original ms too carefully, as this could lead to some confusion.)   I’ve also added a new section that shows that, due to this technicality, one can exhibit smooth H^1 initial data to the Navier-Stokes equation for which there are no smooth solutions, which superficially sounds very close to a negative solution to the global regularity problem, but is actually nothing of the sort.

    Let me now describe the issue in more detail (and also to explain why I missed it previously).  A standard principle in the theory of evolutionary partial differentiation equations is that regularity in space can be used to imply regularity in time.  To illustrate this, consider a solution u to the supercritical nonlinear wave equation

    -\partial_{tt} u + \Delta u = u^7  (1)

    for some field u: {\bf R} \times {\bf R}^3 \to {\bf R}.   Suppose one already knew that u had some regularity in space, and in particular the C^0_t C^2_x \cap C^1_t C^1_x norm of u was bounded (thus u and up to two spatial derivatives of u were bounded).  Then, by (1), we see that two time derivatives of u were also bounded, and one then gets the additional regularity of C^2_t C^0_x.

    In a similar vein, suppose one initially knew that u had the regularity C^0_t C^3_x \cap C^1_t C^2_x.  Then (1) soon tells us that u also has the regularity C^2_t C^1_x; then, if one differentiates (1) in time to obtain

    -\partial_{ttt} u + \Delta \partial_t u = 7 u^6 \partial_t u

    one can conclude that u also has the regularity of C^3_t C^0_x.  One can continue this process indefinitely; in particular, if one knew that u \in C^0_t C^\infty_x \cap C^1_t C^\infty_x, then these sorts of manipulations show that u is infinitely smooth in both space and time.

    The issue that caught me by surprise is that for the Navier-Stokes equations

    \partial_t u + (u \cdot \nabla) u =\Delta u -\nabla p  (2)

    \nabla \cdot u = 0

    (setting the forcing term f equal to zero for simplicity), infinite regularity in space does not automatically imply infinite regularity in time, even if one assumes the initial data lies in a standard function space such as the Sobolev space H^1_x({\bf R}^3).  The problem lies with the pressure term p, which is recovered from the velocity via the elliptic equation

    \Delta p = -\nabla^2 \cdot (u \otimes u) (3)

    that can be obtained by taking the divergence of (2).   This equation is solved by a non-local integral operator:

    \displaystyle p(t,x) = \int_{{\bf R}^3} \frac{\nabla^2 \cdot (u \otimes u)(t,y)}{4\pi |x-y|}\ dy.

    If, say, u lies in H^1_x({\bf R}^3), then there is no difficulty establishing a bound on p in terms of u (for instance, one can use singular integral theory and Sobolev embedding to place p in L^3_x({\bf R}^3).  However, one runs into difficulty when trying to compute time derivatives of p.  Differentiating (3) once, one gets

    \Delta \partial_t p = -2\nabla^2 \cdot (u \otimes \partial_t u).

    At the regularity of H^1, one can still (barely) control this quantity by using (2) to expand out \partial_t u and using some integration by parts.  But when one wishes to compute a second time derivative of the pressure, one obtains (after integration by parts) an expansion of the form

    \Delta \partial_{tt} p = -4\nabla^2 \cdot (\Delta u \otimes \Delta u) + \ldots

    and now there is not enough regularity on u available to get any control on \partial_{tt} p, even if one assumes that u is smooth.   Indeed, following this observation, I was able to show that given generic smooth H^1 data, the pressure p will instantaneously fail to be C^2 in time, and thence (by (2)) the velocity will instantaneously fail to be C^3 in time.  (Switching to the vorticity formulation buys one further degree of time differentiability, but does not fully eliminate the problem; the vorticity \omega will fail to be C^4 in time.  Switching to material coordinates seems to makes things very slightly better, but I believe there is still a breakdown of time regularity in these coordinates also.)

    For later times t>0 (and assuming homogeneous data f=0 for simplicity), this issue no longer arises, because of the instantaneous smoothing effect of the Navier-Stokes flow, which for instance will upgrade H^1_x regularity to H^\infty_x regularity instantaneously.  It is only the initial time at which some time irregularity can occur.

    This breakdown of regularity does not actually impact the original formulation of the Clay Millennium Prize problem, though, because in that problem the initial velocity is required to be Schwartz class (so all derivatives are rapidly decreasing).  In this class, the regularity theory works as expected; if one has a solution which already has some reasonable regularity (e.g. a mild H^1 solution) and the data is Schwartz, then the solution will be smooth in spacetime.   (Another class where things work as expected is when the vorticity is Schwartz; in such cases, the solution remains smooth in both space and time (for short times, at least), and the Schwartz nature of the vorticity is preserved (because the vorticity is subject to fewer non-local effects than the velocity, as it is not directly affected by the pressure).)

    This issue means that one of the implications in the original paper (roughly speaking, that global regularity for Schwartz data implies global regularity for smooth H^1 data) is not correct as stated.  But this can be fixed by weakening the notion of global regularity in the latter setting, by limiting the amount of time differentiability available at the initial time.  More precisely, call a solution u: [0,T] \times {\bf R}^3 \to {\bf R}^3 and p: [0,T] \times {\bf R}^3 \to {\bf R} almost smooth if

    • u and p are smooth on the half-open slab (0,T] \times {\bf R}^3; and
    • For every k \geq 0, \nabla^k_x u, \nabla^k_x p, \nabla^x_u \partial_t u exist and are continuous on the full slab [0,T] \times {\bf R}^3.

    Thus, an almost smooth solution is the same concept as a smooth solution, except that at time zero, the velocity field is only C^1_t C^\infty_x, and the pressure field is only C^0_t C^\infty_x.  This is still enough regularity to interpret the Navier-Stokes equation (2) in a classical manner, but falls slightly short of full smoothness.

    (I had already introduced this notion of almost smoothness in the more general setting of smooth finite energy solutions in the first draft of this paper, but had failed to realise that it was also necessary in the smooth H^1 setting also.)

    One can now “fix” the global regularity conjectures for Navier-Stokes in the smooth H^1 or smooth finite energy setting by requiring the solutions to merely be almost smooth instead of smooth.  Once one does so, the results in my paper then work as before: roughly speaking, if one knows that Schwartz data produces smooth solutions, one can conclude that smooth H^1 or smooth finite energy data produces almost smooth solutions (and the paper now contains counterexamples to show that one does not always have smooth solutions in this category).

    The diagram of implications between conjectures has been adjusted to reflect this issue, and now reads as follows:

    I’ve just uploaded to the arXiv my paper “Localisation and compactness properties of the Navier-Stokes global regularity problem“, submitted to Analysis and PDE. This paper concerns the global regularity problem for the Navier-Stokes system of equations

    \displaystyle  \partial_t u + (u \cdot \nabla) u = \Delta u - \nabla p + f \ \ \ \ \ (1)

    \displaystyle  \nabla \cdot u = 0 \ \ \ \ \ (2)

    \displaystyle  u(0,\cdot) = u_0 \ \ \ \ \ (3)

    in three dimensions. Thus, we specify initial data {(u_0,f,T)}, where {0 < T < \infty} is a time, {u_0: {\bf R}^3 \rightarrow {\bf R}^3} is the initial velocity field (which, in order to be compatible with (2), (3), is required to be divergence-free), {f: [0,T] \times {\bf R}^3 \rightarrow {\bf R}^3} is the forcing term, and then seek to extend this initial data to a solution {(u,p,u_0,f,T)} with this data, where the velocity field {u: [0,T] \times {\bf R}^3 \rightarrow {\bf R}^3} and pressure term {p: [0,T] \times {\bf R}^3 \rightarrow {\bf R}} are the unknown fields.

    Roughly speaking, the global regularity problem asserts that given every smooth set of initial data {(u_0,f,T)}, there exists a smooth solution {(u,p,u_0,f,T)} to the Navier-Stokes equation with this data. However, this is not a good formulation of the problem because it does not exclude the possibility that one or more of the fields {u_0, f, u, p} grows too fast at spatial infinity. This problem is evident even for the much simpler heat equation

    \displaystyle  \partial_t u = \Delta u

    \displaystyle  u(0,\cdot) = u_0.

    As long as one has some mild conditions at infinity on the smooth initial data {u_0: {\bf R}^3 \rightarrow {\bf R}} (e.g. polynomial growth at spatial infinity), then one can solve this equation using the fundamental solution of the heat equation:

    \displaystyle  u(t,x) = \frac{1}{(4\pi t)^{3/2}} \int_{{\bf R}^3} u_0(y) e^{-|x-y|^2/4t}\ dy.

    If furthermore {u} is a tempered distribution, one can use Fourier-analytic methods to show that this is the unique solution to the heat equation with this data. But once one allows sufficiently rapid growth at spatial infinity, existence and uniqueness can break down. Consider for instance the backwards heat kernel

    \displaystyle  u(t,x) = \frac{1}{(4\pi(T-t))^{3/2}} e^{|x|^2/(T-t)}

    for some {T>0}, which is smooth (albeit exponentially growing) at time zero, and is a smooth solution to the heat equation for {0 \leq t < T}, but develops a dramatic singularity at time {t=T}. A famous example of Tychonoff from 1935, based on a power series construction, also shows that uniqueness for the heat equation can also fail once growth conditions are removed. An explicit example of non-uniqueness for the heat equation is given by the contour integral

    \displaystyle  u(t,x_1,x_2,x_3) = \int_\gamma \exp(e^{\pi i/4} x_1 z + e^{5\pi i/8} z^{3/2} - itz^2)\ dz

    where {\gamma} is the {L}-shaped contour consisting of the positive real axis and the upper imaginary axis, with {z^{3/2}} being interpreted with the standard branch (with cut on the negative axis). One can show by contour integration that this function solves the heat equation and is smooth (but rapidly growing at infinity), and vanishes for {t<0}, but is not identically zero for {t>0}.

    Thus, in order to obtain a meaningful (and physically realistic) problem, one needs to impose some decay (or at least limited growth) hypotheses on the data {u_0,f} and solution {u,p} in addition to smoothness. For the data, one can impose a variety of such hypotheses, including the following:

    • (Finite energy data) One has {\|u_0\|_{L^2_x({\bf R}^3)} < \infty} and {\| f \|_{L^\infty_t L^2_x([0,T] \times {\bf R}^3)} < \infty}.
    • ({H^1} data) One has {\|u_0\|_{H^1_x({\bf R}^3)} < \infty} and {\| f \|_{L^\infty_t H^1_x([0,T] \times {\bf R}^3)} < \infty}.
    • (Schwartz data) One has {\sup_{x \in {\bf R}^3} ||x|^m \nabla_x^k u_0(x)| < \infty} and {\sup_{(t,x) \in [0,T] \times {\bf R}^3} ||x|^m \nabla_x^k \partial_t^l f(t,x)| < \infty} for all {m,k,l \geq 0}.
    • (Periodic data) There is some {0 < L < \infty} such that {u_0(x+Lk) = u_0(x)} and {f(t,x+Lk) = f(t,x)} for all {(t,x) \in [0,T] \times {\bf R}^3} and {k \in {\bf Z}^3}.
    • (Homogeneous data) {f=0}.

    Note that smoothness alone does not necessarily imply finite energy, {H^1}, or the Schwartz property. For instance, the (scalar) function {u(x) = \exp( i |x|^{10} ) (1+|x|)^{-2}} is smooth and finite energy, but not in {H^1} or Schwartz. Periodicity is of course incompatible with finite energy, {H^1}, or the Schwartz property, except in the trivial case when the data is identically zero.

    Similarly, one can impose conditions at spatial infinity on the solution, such as the following:

    • (Finite energy solution) One has {\| u \|_{L^\infty_t L^2_x([0,T] \times {\bf R}^3)} < \infty}.
    • ({H^1} solution) One has {\| u \|_{L^\infty_t H^1_x([0,T] \times {\bf R}^3)} < \infty} and {\| u \|_{L^2_t H^2_x([0,T] \times {\bf R}^3)} < \infty}.
    • (Partially periodic solution) There is some {0 < L < \infty} such that {u(t,x+Lk) = u(t,x)} for all {(t,x) \in [0,T] \times {\bf R}^3} and {k \in {\bf Z}^3}.
    • (Fully periodic solution) There is some {0 < L < \infty} such that {u(t,x+Lk) = u(t,x)} and {p(t,x+Lk) = p(t,x)} for all {(t,x) \in [0,T] \times {\bf R}^3} and {k \in {\bf Z}^3}.

    (The {L^2_t H^2_x} component of the {H^1} solution is for technical reasons, and should not be paid too much attention for this discussion.) Note that we do not consider the notion of a Schwartz solution; as we shall see shortly, this is too restrictive a concept of solution to the Navier-Stokes equation.

    Finally, one can downgrade the regularity of the solution down from smoothness. There are many ways to do so; two such examples include

    • ({H^1} mild solutions) The solution is not smooth, but is {H^1} (in the preceding sense) and solves the equation (1) in the sense that the Duhamel formula

      \displaystyle  u(t) = e^{t\Delta} u_0 + \int_0^t e^{(t-t')\Delta} (-(u\cdot\nabla) u-\nabla p+f)(t')\ dt'

      holds.

    • (Leray-Hopf weak solution) The solution {u} is not smooth, but lies in {L^\infty_t L^2_x \cap L^2_t H^1_x}, solves (1) in the sense of distributions (after rewriting the system in divergence form), and obeys an energy inequality.

    Finally, one can ask for two types of global regularity results on the Navier-Stokes problem: a qualitative regularity result, in which one merely provides existence of a smooth solution without any explicit bounds on that solution, and a quantitative regularity result, which provides bounds on the solution in terms of the initial data, e.g. a bound of the form

    \displaystyle  \| u \|_{L^\infty_t H^1_x([0,T] \times {\bf R}^3)} \leq F( \|u_0\|_{H^1_x({\bf R}^3)} + \|f\|_{L^\infty_t H^1_x([0,T] \times {\bf R}^3)}, T )

    for some function {F: {\bf R}^+ \times {\bf R}^+ \rightarrow {\bf R}^+}. One can make a further distinction between local quantitative results, in which {F} is allowed to depend on {T}, and global quantitative results, in which there is no dependence on {T} (the latter is only reasonable though in the homogeneous case, or if {f} has some decay in time).

    By combining these various hypotheses and conclusions, we see that one can write down quite a large number of slightly different variants of the global regularity problem. In the official formulation of the regularity problem for the Clay Millennium prize, a positive correct solution to either of the following two problems would be accepted for the prize:

    • Conjecture 1.4 (Qualitative regularity for homogeneous periodic data) If {(u_0,0,T)} is periodic, smooth, and homogeneous, then there exists a smooth partially periodic solution {(u,p,u_0,0,T)} with this data.
    • Conjecture 1.3 (Qualitative regularity for homogeneous Schwartz data) If {(u_0,0,T)} is Schwartz and homogeneous, then there exists a smooth finite energy solution {(u,p,u_0,0,T)} with this data.

    (The numbering here corresponds to the numbering in the paper.)

    Furthermore, a negative correct solution to either of the following two problems would also be accepted for the prize:

    • Conjecture 1.6 (Qualitative regularity for periodic data) If {(u_0,f,T)} is periodic and smooth, then there exists a smooth partially periodic solution {(u,p,u_0,f,T)} with this data.
    • Conjecture 1.5 (Qualitative regularity for Schwartz data) If {(u_0,f,T)} is Schwartz, then there exists a smooth finite energy solution {(u,p,u_0,f,T)} with this data.

    I am not announcing any major progress on these conjectures here. What my paper does study, though, is the question of whether the answer to these conjectures is somehow sensitive to the choice of formulation. For instance:

    1. Note in the periodic formulations of the Clay prize problem that the solution is only required to be partially periodic, rather than fully periodic; thus the pressure has no periodicity hypothesis. One can ask the extent to which the above problems change if one also requires pressure periodicity.
    2. In another direction, one can ask the extent to which quantitative formulations of the Navier-Stokes problem are stronger than their qualitative counterparts; in particular, whether it is possible that each choice of initial data in a certain class leads to a smooth solution, but with no uniform bound on that solution in terms of various natural norms of the data.
    3. Finally, one can ask the extent to which the conjecture depends on the category of data. For instance, could it be that global regularity is true for smooth periodic data but false for Schwartz data? True for Schwartz data but false for smooth {H^1} data? And so forth.

    One motivation for the final question (which was posed to me by my colleague, Andrea Bertozzi) is that the Schwartz property on the initial data {u_0} tends to be instantly destroyed by the Navier-Stokes flow. This can be seen by introducing the vorticity {\omega := \nabla \times u}. If {u(t)} is Schwartz, then from Stokes’ theorem we necessarily have vanishing of certain moments of the vorticity, for instance:

    \displaystyle  \int_{{\bf R}^3} \omega_1 (x_2^2-x_3^2)\ dx = 0.

    On the other hand, some integration by parts using (1) reveals that such moments are usually not preserved by the flow; for instance, one has the law

    \displaystyle \partial_t \int_{{\bf R}^3} \omega_1(t,x) (x_2^2-x_3^2)\ dx = 4\int_{{\bf R}^3} u_2(t,x) u_3(t,x)\ dx,

    and one can easily concoct examples for which the right-hand side is non-zero at time zero. This suggests that the Schwartz class may be unnecessarily restrictive for Conjecture 1.3 or Conjecture 1.5.

    My paper arose out of an attempt to address these three questions, and ended up obtaining partial results in all three directions. Roughly speaking, the results that address these three questions are as follows:

    1. (Homogenisation) If one only assumes partial periodicity instead of full periodicity, then the forcing term {f} becomes irrelevant. In particular, Conjecture 1.4 and Conjecture 1.6 are equivalent.
    2. (Concentration compactness) In the {H^1} category (both periodic and nonperiodic, homogeneous or nonhomogeneous), the qualitative and quantitative formulations of the Navier-Stokes global regularity problem are essentially equivalent.
    3. (Localisation) The (inhomogeneous) Navier-Stokes problems in the Schwartz, smooth {H^1}, and finite energy categories are essentially equivalent to each other, and are also implied by the (fully) periodic version of these problems.

    The first two of these families of results are relatively routine, drawing on existing methods in the literature; the localisation results though are somewhat more novel, and introduce some new local energy and local enstrophy estimates which may be of independent interest.

    Broadly speaking, the moral to draw from these results is that the precise formulation of the Navier-Stokes equation global regularity problem is only of secondary importance; modulo a number of caveats and technicalities, the various formulations are close to being equivalent, and a breakthrough on any one of the formulations is likely to lead (either directly or indirectly) to a comparable breakthrough on any of the others.

    This is only a caricature of the actual implications, though. Below is the diagram from the paper indicating the various formulations of the Navier-Stokes equations, and the known implications between them:

    The above three streams of results are discussed in more detail below the fold.

    Read the rest of this entry »

    Archives

    RSS Google+ feed

    • An error has occurred; the feed is probably down. Try again later.
    Follow

    Get every new post delivered to your Inbox.

    Join 3,307 other followers