You are currently browsing the category archive for the ‘expository’ category.

The lonely runner conjecture is the following open problem:

Conjecture 1 Suppose one has {n \geq 1} runners on the unit circle {{\bf R}/{\bf Z}}, all starting at the origin and moving at different speeds. Then for each runner, there is at least one time {t} for which that runner is “lonely” in the sense that it is separated by a distance at least {1/n} from all other runners.

One can normalise the speed of the lonely runner to be zero, at which point the conjecture can be reformulated (after replacing {n} by {n+1}) as follows:

Conjecture 2 Let {v_1,\dots,v_n} be non-zero real numbers for some {n \geq 1}. Then there exists a real number {t} such that the numbers {tv_1,\dots,tv_n} are all a distance at least {\frac{1}{n+1}} from the integers, thus {\|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}} where {\|x\|_{{\bf R}/{\bf Z}}} denotes the distance of {x} to the nearest integer.

This conjecture has been proven for {n \leq 7}, but remains open for larger {n}. The bound {\frac{1}{n+1}} is optimal, as can be seen by looking at the case {v_i=i} and applying the Dirichlet approximation theorem. Note that for each non-zero {v}, the set {\{ t \in {\bf R}: \|vt\|_{{\bf R}/{\bf Z}} \leq r \}} has (Banach) density {2r} for any {0 < r < 1/2}, and from this and the union bound we can easily find {t \in {\bf R}} for which

\displaystyle \|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{2n}-\varepsilon

for any {\varepsilon>0}, but it has proven to be quite challenging to remove the factor of {2} to increase {\frac{1}{2n}} to {\frac{1}{n+1}}. (As far as I know, even improving {\frac{1}{2n}} to {\frac{1+c}{2n}} for some absolute constant {c>0} and sufficiently large {n} remains open.)

The speeds {v_1,\dots,v_n} in the above conjecture are arbitrary non-zero reals, but it has been known for some time that one can reduce without loss of generality to the case when the {v_1,\dots,v_n} are rationals, or equivalently (by scaling) to the case where they are integers; see e.g. Section 4 of this paper of Bohman, Holzman, and Kleitman.

In this post I would like to remark on a slight refinement of this reduction, in which the speeds {v_1,\dots,v_n} are integers of bounded size, where the bound depends on {n}. More precisely:

Proposition 3 In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the {v_1,\dots,v_n} are integers of size at most {n^{Cn^2}}, where {C} is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all {n \leq n_0}, then the original version of the conjecture is also true for all {n \leq n_0}.)

In principle, this proposition allows one to verify the lonely runner conjecture for a given {n} in finite time; however the number of cases to check with this proposition grows faster than exponentially in {n}, and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of {n} than currently known.

One of the key tools needed to prove this proposition is the following additive combinatorics result. Recall that a generalised arithmetic progression (or {GAP}) in the reals {{\bf R}} is a set of the form

\displaystyle  P = \{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1, \dots, |n_d| \leq N_d \}

for some {v_1,\dots,v_d \in {\bf R}} and {N_1,\dots,N_d > 0}; the quantity {d} is called the rank of the progression. If {t>0}, the progression {P} is said to be {t}-proper if the sums {n_1 v_1 + \dots + n_d v_d} with {|n_i| \leq t N_i} for {i=1,\dots,d} are all distinct. We have

Lemma 4 (Progressions lie inside proper progressions) Let {P} be a GAP of rank {d} in the reals, and let {t \geq 1}. Then {P} is contained in a {t}-proper GAP {Q} of rank at most {d}, with

\displaystyle |Q| \leq (2t)^d d^{6d^2} \prod_{i=1}^d (2N_i+1).

Proof: See Theorem 2.1 of this paper of Bilu. (Very similar results can also be found in Theorem 3.40 of my book with Van Vu, or Theorem 1.10 of this paper of mine with Van Vu.) \Box

Now let {n \geq 1}, and assume inductively that the lonely runner conjecture has been proven for all smaller values of {n}, as well as for the current value of {n} in the case that {v_1,\dots,v_n} are integers of size at most {n^{Cn^2}} for some sufficiently large {C}. We will show that the lonely runner conjecture holds in general for this choice of {n}.

let {v_1,\dots,v_n} be non-zero real numbers. Let {C_0} be a large absolute constant to be chosen later. From the above lemma applied to the GAP {\{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in \{-1,0,1\}\}}, one can find a {n^{C_0n}}-proper GAP {Q} of rank at most {n} containing {\{v_1,\dots,v_n\}} such that

\displaystyle  |Q| \leq (6n^{C_0 n})^n n^{6n^2};

in particular {|Q| \leq n^{Cn^2}} if {C} is large enough depending on {C_0}.

We write

\displaystyle  Q = \{ n_1 w_1 + \dots + n_d w_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1,\dots,|n_d| \leq N_d \}

for some {d \leq n}, {w_1,\dots,w_d}, and {N_1,\dots,N_d \geq 0}. We thus have {v_i = \phi(a_i)} for {i=1,\dots,n}, where {\phi: {\bf R}^d \rightarrow {\bf R}} is the linear map {\phi(n_1,\dots,n_d) := n_1 w_1 + \dots + n_d w_d} and {a_1,\dots,a_n \in {\bf Z}^d} are non-zero and lie in the box {\{ (n_1,\dots,n_d) \in {\bf R}^d: |n_1| \leq N_1,\dots,|n_d| \leq N_d \}}.

We now need an elementary lemma that allows us to create a “collision” between two of the {a_1,\dots,a_n} via a linear projection, without making any of the {a_i} collide with the origin:

Lemma 5 Let {a_1,\dots,a_n \in {\bf R}^d} be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the {a_i} with their negatives {-a_i} if necessary, there exists a pair {a_i,a_j} such that {a_i-a_j \neq 0}, and such that none of the {a_1,\dots,a_n} is a scalar multiple of {a_i-a_j}.

Proof: We may assume that {d \geq 2}, since the {d \leq 1} case is vacuous. Applying a generic linear projection to {{\bf R}^2} (which does not affect collinearity, or the property that a given {a_k} is a scalar multiple of {a_i-a_j}), we may then reduce to the case {d=2}.

By a rotation and relabeling, we may assume that {a_1} lies on the negative {x}-axis; by flipping signs as necessary we may then assume that all of the {a_2,\dots,a_n} lie in the closed right half-plane. As the {a_i} are not all collinear with the origin, one of the {a_i} lies off of the {x}-axis, by relabeling, we may assume that {a_2} lies off of the {x} axis and makes a minimal angle with the {x}-axis. Then the angle of {a_2-a_1} with the {x}-axis is non-zero but smaller than any non-zero angle that any of the {a_i} make with this axis, and so none of the {a_i} are a scalar multiple of {a_2-a_1}, and the claim follows. \Box

We now return to the proof of the proposition. If the {a_1,\dots,a_n} are all collinear with the origin, then {\phi(a_1),\dots,\phi(a_n)} lie in a one-dimensional arithmetic progression {\{ mv: |m| \leq |Q| \}}, and then by rescaling we may take the {v_1,\dots,v_n} to be integers of magnitude at most {|Q| \leq n^{Cn}}, at which point we are done by hypothesis. Thus, we may assume that the {a_1,\dots,a_n} are not all collinear with the origin, and so by the above lemma and relabeling we may assume that {a_n-a_1} is non-zero, and that none of the {a_i} are scalar multiples of {a_n-a_1}.

We write

\displaystyle  a_n-a_1 = (c_1,\dots,c_d) \ \ \ \ \ (1)

with {|c_i| \leq 2 N_i} for {i=1,\dots,d}; by relabeling we may assume without loss of generality that {c_d} is non-zero, and furthermore that

\displaystyle  \frac{|c_i|}{N_i} \leq \frac{|c_d|}{N_d}

for {i=1,\dots,d}. We can also factor

\displaystyle  (c_1,\dots,c_d) = q (c'_1,\dots,c'_d) \ \ \ \ \ (2)

where {q} is a natural number and {c'_1,\dots,c'_d} have no common factor.

We now define a variant {\tilde \phi: {\bf R}^d \rightarrow {\bf R}} of {\phi: {\bf R}^d \rightarrow {\bf R}} by the map

\displaystyle  \tilde \phi(n_1,\dots,n_d) := n_1 \tilde w_1 + \dots + n_{d-1} \tilde w_{d-1} - \frac{n_d}{c_d} (c_1 \tilde w_1 + \dots + c_{d-1} \tilde w_{d-1}),

where the {\tilde w_1,\dots,\tilde w_{d-1}} are real numbers that are linearly independent over {{\bf Q}}, whose precise value will not be of importance in our argument. This is a linear map with the property that {\tilde \phi(a_n-a_1)=0}, so that {\tilde \phi(a_1),\dots,\tilde \phi(a_n)} consists of at most {n-1} distinct real numbers, which are non-zero since none of the {a_i} are scalar multiples of {a_n-a_1}, and the {\tilde w_i} are linearly independent over {{\bf Q}}. As we are assuming inductively that the lonely runner conjecture holds for {n-1}, we conclude (after deleting duplicates) that there exists at least one real number {\tilde t} such that

\displaystyle  \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n}.

We would like to “approximate” {\phi} by {\tilde \phi} to then conclude that there is at least one real number {t} such that

\displaystyle  \| t \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| t \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}.

It turns out that we can do this by a Fourier-analytic argument taking advantage of the {n^{C_0 n}}-proper nature of {Q}. Firstly, we see from the Dirichlet approximation theorem that one has

\displaystyle  \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \leq \frac{1}{10 n^2}

for a set {\tilde t} of reals of (Banach) density {\gg n^{-O(n)}}. Thus, by the triangle inequality, we have

\displaystyle  \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}

for a set {\tilde t} of reals of density {\gg n^{-O(n)}}.

Applying a smooth Fourier multiplier of Littlewood-Paley type, one can find a trigonometric polynomial

\displaystyle  \eta(x) = \sum_{m: |m| \leq n^{C_0 n/10}} b_m e^{2\pi i mx}

which takes values in {[0,1]}, is {\gg 1} for {\|x\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}}, and is no larger than {O( n^{-100 C_0n} )} for {\|x\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}}. We then have

\displaystyle  \mathop{\bf E}_t \prod_{j=1}^n \eta( t \tilde \phi(a_j) ) \gg n^{-O(n)}

where {\mathop{\bf E}_t f(t)} denotes the mean value of a quasiperiodic function {f} on the reals {{\bf R}}. We expand the left-hand side out as

\displaystyle  \sum_{m_1,\dots,m_n: m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0} b_{m_1} \dots b_{m_n}.

From the genericity of {\tilde w_1,\dots,\tilde w_n}, we see that the constraint

\displaystyle  m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0

occurs if and only if {m_1 a_1 + \dots + m_n a_n} is a scalar multiple of {a_n-a_1}, or equivalently (by (1), (2)) an integer multiple of {(c'_1,\dots,c'_d)}. Thus

\displaystyle  \sum_{m_1,\dots,m_n: m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d)} b_{m_1} \dots b_{m_n} \gg n^{-O(n)}. \ \ \ \ \ (3)

Next, we consider the average

\displaystyle  \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \ \ \ \ \ (4)

where

\displaystyle  \xi := c'_1 w_1 + \dots + c'_d w_d. \ \ \ \ \ (5)

and {\varphi} is the Dirichlet series

\displaystyle  \varphi(x) := \sum_{m: |m| \leq n^{C_0 n/2}} e^{2\pi i mx}.

By Fourier expansion and writing {v_j = \phi(a_j)}, we may write (4) as

\displaystyle  \sum_{m,m_1,\dots,m_n: |m| \leq n^{C_0n/2}; m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi} b_{m_1} \dots b_{m_n}.

The support of the {b_{m_i}} implies that {|m_i| \leq n^{C_0n/10}}. Because of the {n^{C_0 n}}-properness of {Q}, we see (for {n} large enough) that the equation

\displaystyle  m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi \ \ \ \ \ (6)

implies that

\displaystyle  m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d) \ \ \ \ \ (7)

and conversely that (7) implies that (6) holds for some {m} with {|m| \leq n^{C_0 n/2}}. From (3) we thus have

\displaystyle  \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.

In particular, there exists a {t} such that

\displaystyle  \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.

Since {\varphi} is bounded in magnitude by {n^{C_0n/2}}, and {\eta} is bounded by {1}, we thus have

\displaystyle  \eta(t v_j) \gg n^{-C_0 n/2 - O(1)}

for each {1 \leq j \leq n}, which by the size properties of {\eta} implies that {\|tv_j\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}} for all {1 \leq j \leq n}, giving the lonely runner conjecture for {n}.

Because of Euler’s identity {e^{\pi i} + 1 = 0}, the complex exponential is not injective: {e^{z + 2\pi i k} = e^z} for any complex {z} and integer {k}. As such, the complex logarithm {z \mapsto \log z} is not well-defined as a single-valued function from {{\bf C} \backslash \{0\}} to {{\bf C}}. However, after making a branch cut, one can create a branch of the logarithm which is single-valued. For instance, after removing the negative real axis {(-\infty,0]}, one has the standard branch {\hbox{Log}: {\bf C} \backslash (-\infty,0] \rightarrow \{ z \in {\bf C}: |\hbox{Im} z| < \pi \}} of the logarithm, with {\hbox{Log}(z)} defined as the unique choice of the complex logarithm of {z} whose imaginary part has magnitude strictly less than {\pi}. This particular branch has a number of useful additional properties:

  • The standard branch {\hbox{Log}} is holomorphic on its domain {{\bf C} \backslash (-\infty,0]}.
  • One has {\hbox{Log}( \overline{z} ) = \overline{ \hbox{Log}(z) }} for all {z} in the domain {{\bf C} \backslash (-\infty,0]}. In particular, if {z \in {\bf C} \backslash (-\infty,0]} is real, then {\hbox{Log} z} is real.
  • One has {\hbox{Log}( z^{-1} ) = - \hbox{Log}(z)} for all {z} in the domain {{\bf C} \backslash (-\infty,0]}.

One can then also use the standard branch of the logarithm to create standard branches of other multi-valued functions, for instance creating a standard branch {z \mapsto \exp( \frac{1}{2} \hbox{Log} z )} of the square root function. We caution however that the identity {\hbox{Log}(zw) = \hbox{Log}(z) + \hbox{Log}(w)} can fail for the standard branch (or indeed for any branch of the logarithm).

One can extend this standard branch of the logarithm to {n \times n} complex matrices, or (equivalently) to linear transformations {T: V \rightarrow V} on an {n}-dimensional complex vector space {V}, provided that the spectrum of that matrix or transformation avoids the branch cut {(-\infty,0]}. Indeed, from the spectral theorem one can decompose any such {T: V \rightarrow V} as the direct sum of operators {T_\lambda: V_\lambda \rightarrow V_\lambda} on the non-trivial generalised eigenspaces {V_\lambda} of {T}, where {\lambda \in {\bf C} \backslash (-\infty,0]} ranges in the spectrum of {T}. For each component {T_\lambda} of {T}, we define

\displaystyle  \hbox{Log}( T_\lambda ) = P_\lambda( T_\lambda )

where {P_\lambda} is the Taylor expansion of {\hbox{Log}} at {\lambda}; as {T_\lambda-\lambda} is nilpotent, only finitely many terms in this Taylor expansion are required. The logarithm {\hbox{Log} T} is then defined as the direct sum of the {\hbox{Log} T_\lambda}.

The matrix standard branch of the logarithm has many pleasant and easily verified properties (often inherited from their scalar counterparts), whenever {T: V \rightarrow V} has no spectrum in {(-\infty,0]}:

  • (i) We have {\exp( \hbox{Log} T ) = T}.
  • (ii) If {T_1: V_1 \rightarrow V_1} and {T_2: V_2 \rightarrow V_2} have no spectrum in {(-\infty,0]}, then {\hbox{Log}( T_1 \oplus T_2 ) = \hbox{Log}(T_1) \oplus \hbox{Log}(T_2)}.
  • (iii) If {T} has spectrum in a closed disk {B(z,r)} in {{\bf C} \backslash (-\infty,0]}, then {\hbox{Log}(T) = P_z(T)}, where {P_z} is the Taylor series of {\hbox{Log}} around {z} (which is absolutely convergent in {B(z,r)}).
  • (iv) {\hbox{Log}(T)} depends holomorphically on {T}. (Easily established from (ii), (iii), after covering the spectrum of {T} by disjoint disks; alternatively, one can use the Cauchy integral representation {\hbox{Log}(T) = \frac{1}{2\pi i} \int_\gamma \hbox{Log}(z)(z-T)^{-1}\ dz} for a contour {\gamma} in the domain enclosing the spectrum of {T}.) In particular, the standard branch of the matrix logarithm is smooth.
  • (v) If {S: V \rightarrow W} is any invertible linear or antilinear map, then {\hbox{Log}( STS^{-1} ) = S \hbox{Log}(T) S^{-1}}. In particular, the standard branch of the logarithm commutes with matrix conjugations; and if {T} is real with respect to a complex conjugation operation on {V} (that is to say, an antilinear involution), then {\hbox{Log}(T)} is real also.
  • (vi) If {T^*: V^* \rightarrow V^*} denotes the transpose of {T} (with {V^*} the complex dual of {V}), then {\hbox{Log}(T^*) = \hbox{Log}(T)^*}. Similarly, if {T^\dagger: V^\dagger \rightarrow V^\dagger} denotes the adjoint of {T} (with {V^\dagger} the complex conjugate of {V^*}, i.e. {V^*} with the conjugated multiplication map {(c,z) \mapsto \overline{c} z}), then {\hbox{Log}(T^\dagger) = \hbox{Log}(T)^\dagger}.
  • (vii) One has {\hbox{Log}(T^{-1}) = - \hbox{Log}( T )}.
  • (viii) If {\sigma(T)} denotes the spectrum of {T}, then {\sigma(\hbox{Log} T) = \hbox{Log} \sigma(T)}.

As a quick application of the standard branch of the matrix logarithm, we have

Proposition 1 Let {G} be one of the following matrix groups: {GL_n({\bf C})}, {GL_n({\bf R})}, {U_n({\bf C})}, {O(Q)}, {Sp_{2n}({\bf C})}, or {Sp_{2n}({\bf R})}, where {Q: {\bf R}^n \rightarrow {\bf R}} is a non-degenerate real quadratic form (so {O(Q)} is isomorphic to a (possibly indefinite) orthogonal group {O(k,n-k)} for some {0 \leq k \leq n}. Then any element {T} of {G} whose spectrum avoids {(-\infty,0]} is exponential, that is to say {T = \exp(X)} for some {X} in the Lie algebra {{\mathfrak g}} of {G}.

Proof: We just prove this for {G=O(Q)}, as the other cases are similar (or a bit simpler). If {T \in O(Q)}, then (viewing {T} as a complex-linear map on {{\bf C}^n}, and using the complex bilinear form associated to {Q} to identify {{\bf C}^n} with its complex dual {({\bf C}^n)^*}, then {T} is real and {T^{*-1} = T}. By the properties (v), (vi), (vii) of the standard branch of the matrix logarithm, we conclude that {\hbox{Log} T} is real and {- \hbox{Log}(T)^* = \hbox{Log}(T)}, and so {\hbox{Log}(T)} lies in the Lie algebra {{\mathfrak g} = {\mathfrak o}(Q)}, and the claim now follows from (i). \Box

Exercise 2 Show that {\hbox{diag}(-\lambda, -1/\lambda)} is not exponential in {GL_2({\bf R})} if {-\lambda \in (-\infty,0) \backslash \{-1\}}. Thus we see that the branch cut in the above proposition is largely necessary. See this paper of Djokovic for a more complete description of the image of the exponential map in classical groups, as well as this previous blog post for some more discussion of the surjectivity (or lack thereof) of the exponential map in Lie groups.

For a slightly less quick application of the standard branch, we have the following result (recently worked out in the answers to this MathOverflow question):

Proposition 3 Let {T} be an element of the split orthogonal group {O(n,n)} which lies in the connected component of the identity. Then {\hbox{det}(1+T) \geq 0}.

The requirement that {T} lie in the identity component is necessary, as the counterexample {T = \hbox{diag}(-\lambda, -1/\lambda )} for {\lambda \in (-\infty,-1) \cup (-1,0)} shows.

Proof: We think of {T} as a (real) linear transformation on {{\bf C}^{2n}}, and write {Q} for the quadratic form associated to {O(n,n)}, so that {O(n,n) \equiv O(Q)}. We can split {{\bf C}^{2n} = V_1 \oplus V_2}, where {V_1} is the sum of all the generalised eigenspaces corresponding to eigenvalues in {(-\infty,0]}, and {V_2} is the sum of all the remaining eigenspaces. Since {T} and {(-\infty,0]} are real, {V_1,V_2} are real (i.e. complex-conjugation invariant) also. For {i=1,2}, the restriction {T_i: V_i \rightarrow V_i} of {T} to {V_i} then lies in {O(Q_i)}, where {Q_i} is the restriction of {Q} to {V_i}, and

\displaystyle  \hbox{det}(1+T) = \hbox{det}(1+T_1) \hbox{det}(1+T_2).

The spectrum of {T_2} consists of positive reals, as well as complex pairs {\lambda, \overline{\lambda}} (with equal multiplicity), so {\hbox{det}(1+T_2) > 0}. From the preceding proposition we have {T_2 = \exp( X_2 )} for some {X_2 \in {\mathfrak o}(Q_2)}; this will be important later.

It remains to show that {\hbox{det}(1+T_1) \geq 0}. If {T_1} has spectrum at {-1} then we are done, so we may assume that {T_1} has spectrum only at {(-\infty,-1) \cup (-1,0)} (being invertible, {T} has no spectrum at {0}). We split {V_1 = V_3 \oplus V_4}, where {V_3,V_4} correspond to the portions of the spectrum in {(-\infty,-1)}, {(-1,0)}; these are real, {T}-invariant spaces. We observe that if {V_\lambda, V_\mu} are generalised eigenspaces of {T} with {\lambda \mu \neq 1}, then {V_\lambda, V_\mu} are orthogonal with respect to the (complex-bilinear) inner product {\cdot} associated with {Q}; this is easiest to see first for the actual eigenspaces (since { \lambda \mu u \cdot v = Tu \cdot Tv = u \cdot v} for all {u \in V_\lambda, v \in V_\mu}), and the extension to generalised eigenvectors then follows from a routine induction. From this we see that {V_1} is orthogonal to {V_2}, and {V_3} and {V_4} are null spaces, which by the non-degeneracy of {Q} (and hence of the restriction {Q_1} of {Q} to {V_1}) forces {V_3} to have the same dimension as {V_4}, indeed {Q} now gives an identification of {V_3^*} with {V_4}. If we let {T_3, T_4} be the restrictions of {T} to {V_3,V_4}, we thus identify {T_4} with {T_3^{*-1}}, since {T} lies in {O(Q)}; in particular {T_3} is invertible. Thus

\displaystyle  \hbox{det}(1+T_1) = \hbox{det}(1 + T_3) \hbox{det}( 1 + T_3^{*-1} ) = \hbox{det}(T_3)^{-1} \hbox{det}(1+T_3)^2

and so it suffices to show that {\hbox{det}(T_3) > 0}.

At this point we need to use the hypothesis that {T} lies in the identity component of {O(n,n)}. This implies (by a continuity argument) that the restriction of {T} to any maximal-dimensional positive subspace has positive determinant (since such a restriction cannot be singular, as this would mean that {T} positive norm vector would map to a non-positive norm vector). Now, as {V_3,V_4} have equal dimension, {Q_1} has a balanced signature, so {Q_2} does also. Since {T_2 = \exp(X_2)}, {T_2} already lies in the identity component of {O(Q_2)}, and so has positive determinant on any maximal-dimensional positive subspace of {V_2}. We conclude that {T_1} has positive determinant on any maximal-dimensional positive subspace of {V_1}.

We choose a complex basis of {V_3}, to identify {V_3} with {V_3^*}, which has already been identified with {V_4}. (In coordinates, {V_3,V_4} are now both of the form {{\bf C}^m}, and {Q( v \oplus w ) = v \cdot w} for {v,w \in {\bf C}^m}.) Then {\{ v \oplus v: v \in V_3 \}} becomes a maximal positive subspace of {V_1}, and the restriction of {T_1} to this subspace is conjugate to {T_3 + T_3^{*-1}}, so that

\displaystyle  \hbox{det}( T_3 + T_3^{*-1} ) > 0.

But since {\hbox{det}( T_3 + T_3^{*-1} ) = \hbox{det}(T_3) \hbox{det}( 1 + T_3^{-1} T_3^{*-1} )} and { 1 + T_3^{-1} T_3^{*-1}} is positive definite, so {\hbox{det}(T_3)>0} as required. \Box

The Euler equations for three-dimensional incompressible inviscid fluid flow are

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

\displaystyle \nabla \cdot u = 0

where {u: {\bf R} \times {\bf R}^3 \rightarrow {\bf R}^3} is the velocity field, and {p: {\bf R} \times {\bf R}^3 \rightarrow {\bf R}} is the pressure field. For the purposes of this post, we will ignore all issues of decay or regularity of the fields in question, assuming that they are as smooth and rapidly decreasing as needed to justify all the formal calculations here; in particular, we will apply inverse operators such as {(-\Delta)^{-1}} or {|\nabla|^{-1} := (-\Delta)^{-1/2}} formally, assuming that these inverses are well defined on the functions they are applied to.

Meanwhile, the surface quasi-geostrophic (SQG) equation is given by

\displaystyle  \partial_t \theta + (u \cdot \nabla) \theta = 0 \ \ \ \ \ (2)

\displaystyle  u = ( -\partial_y |\nabla|^{-1}, \partial_x |\nabla|^{-1} ) \theta \ \ \ \ \ (3)

where {\theta: {\bf R} \times {\bf R}^2 \rightarrow {\bf R}} is the active scalar, and {u: {\bf R} \times {\bf R}^2 \rightarrow {\bf R}^2} is the velocity field. The SQG equations are often used as a toy model for the 3D Euler equations, as they share many of the same features (e.g. vortex stretching); see this paper of Constantin, Majda, and Tabak for more discussion (or this previous blog post).

I recently found a more direct way to connect the two equations. We first recall that the Euler equations can be placed in vorticity-stream form by focusing on the vorticity {\omega := \nabla \times u}. Indeed, taking the curl of (1), we obtain the vorticity equation

\displaystyle  \partial_t \omega + (u \cdot \nabla) \omega = (\omega \cdot \nabla) u \ \ \ \ \ (4)

while the velocity {u} can be recovered from the vorticity via the Biot-Savart law

\displaystyle  u = (-\Delta)^{-1} \nabla \times \omega. \ \ \ \ \ (5)

The system (4), (5) has some features in common with the system (2), (3); in (2) it is a scalar field {\theta} that is being transported by a divergence-free vector field {u}, which is a linear function of the scalar field as per (3), whereas in (4) it is a vector field {\omega} that is being transported (in the Lie derivative sense) by a divergence-free vector field {u}, which is a linear function of the vector field as per (5). However, the system (4), (5) is in three dimensions whilst (2), (3) is in two spatial dimensions, the dynamical field is a scalar field {\theta} for SQG and a vector field {\omega} for Euler, and the relationship between the velocity field and the dynamical field is given by a zeroth order Fourier multiplier in (3) and a {-1^{th}} order operator in (5).

However, we can make the two equations more closely resemble each other as follows. We first consider the generalisation

\displaystyle  \partial_t \omega + (u \cdot \nabla) \omega = (\omega \cdot \nabla) u \ \ \ \ \ (6)

\displaystyle  u = T (-\Delta)^{-1} \nabla \times \omega \ \ \ \ \ (7)

where {T} is an invertible, self-adjoint, positive-definite zeroth order Fourier multiplier that maps divergence-free vector fields to divergence-free vector fields. The Euler equations then correspond to the case when {T} is the identity operator. As discussed in this previous blog post (which used {A} to denote the inverse of the operator denoted here as {T}), this generalised Euler system has many of the same features as the original Euler equation, such as a conserved Hamiltonian

\displaystyle  \frac{1}{2} \int_{{\bf R}^3} u \cdot T^{-1} u,

the Kelvin circulation theorem, and conservation of helicity

\displaystyle  \int_{{\bf R}^3} \omega \cdot T^{-1} u.

Also, if we require {\omega} to be divergence-free at time zero, it remains divergence-free at all later times.

Let us consider “two-and-a-half-dimensional” solutions to the system (6), (7), in which {u,\omega} do not depend on the vertical coordinate {z}, thus

\displaystyle  \omega(t,x,y,z) = \omega(t,x,y)

and

\displaystyle  u(t,x,y,z) = u(t,x,y)

but we allow the vertical components {u_z, \omega_z} to be non-zero. For this to be consistent, we also require {T} to commute with translations in the {z} direction. As all derivatives in the {z} direction now vanish, we can simplify (6) to

\displaystyle  D_t \omega = (\omega_x \partial_x + \omega_y \partial_y) u \ \ \ \ \ (8)

where {D_t} is the two-dimensional material derivative

\displaystyle  D_t := \partial_t + u_x \partial_x + u_y \partial_y.

Also, divergence-free nature of {\omega,u} then becomes

\displaystyle  \partial_x \omega_x + \partial_y \omega_y = 0

and

\displaystyle  \partial_x u_x + \partial_y u_y = 0. \ \ \ \ \ (9)

In particular, we may (formally, at least) write

\displaystyle  (\omega_x, \omega_y) = (\partial_y \theta, -\partial_x \theta)

for some scalar field {\theta(t,x,y,z) = \theta(t,x,y)}, so that (7) becomes

\displaystyle  u = T ( (- \Delta)^{-1} \partial_y \omega_z, - (-\Delta^{-1}) \partial_x \omega_z, \theta ). \ \ \ \ \ (10)

The first two components of (8) become

\displaystyle  D_t \partial_y \theta = \partial_y \theta \partial_x u_x - \partial_x \theta \partial_y u_x

\displaystyle - D_t \partial_x \theta = \partial_y \theta \partial_x u_y - \partial_x \theta \partial_y u_y

which rearranges using (9) to

\displaystyle  \partial_y D_t \theta = \partial_x D_t \theta = 0.

Formally, we may integrate this system to obtain the transport equation

\displaystyle  D_t \theta = 0, \ \ \ \ \ (11)

Finally, the last component of (8) is

\displaystyle  D_t \omega_z = \partial_y \theta \partial_x u_z - \partial_x \theta \partial_y u_z. \ \ \ \ \ (12)

At this point, we make the following choice for {T}:

\displaystyle  T ( U_x, U_y, \theta ) = \alpha (U_x, U_y, \theta) + (-\partial_y |\nabla|^{-1} \theta, \partial_x |\nabla|^{-1} \theta, 0) \ \ \ \ \ (13)

\displaystyle  + P( 0, 0, |\nabla|^{-1} (\partial_y U_x - \partial_x U_y) )

where {\alpha > 0} is a real constant and {Pu := (-\Delta)^{-1} (\nabla \times (\nabla \times u))} is the Leray projection onto divergence-free vector fields. One can verify that for large enough {\alpha}, {T} is a self-adjoint positive definite zeroth order Fourier multiplier from divergence free vector fields to divergence-free vector fields. With this choice, we see from (10) that

\displaystyle  u_z = \alpha \theta - |\nabla|^{-1} \omega_z

so that (12) simplifies to

\displaystyle  D_t \omega_z = - \partial_y \theta \partial_x |\nabla|^{-1} \omega_z + \partial_x \theta \partial_y |\nabla|^{-1} \omega_z.

This implies (formally at least) that if {\omega_z} vanishes at time zero, then it vanishes for all time. Setting {\omega_z=0}, we then have from (10) that

\displaystyle (u_x,u_y,u_z) = (-\partial_y |\nabla|^{-1} \theta, \partial_x |\nabla|^{-1} \theta, \alpha \theta )

and from (11) we then recover the SQG system (2), (3). To put it another way, if {\theta(t,x,y)} and {u(t,x,y)} solve the SQG system, then by setting

\displaystyle  \omega(t,x,y,z) := ( \partial_y \theta(t,x,y), -\partial_x \theta(t,x,y), 0 )

\displaystyle  \tilde u(t,x,y,z) := ( u_x(t,x,y), u_y(t,x,y), \alpha \theta(t,x,y) )

then {\omega,\tilde u} solve the modified Euler system (6), (7) with {T} given by (13).

We have {T^{-1} \tilde u = (0, 0, \theta)}, so the Hamiltonian {\frac{1}{2} \int_{{\bf R}^3} \tilde u \cdot T^{-1} \tilde u} for the modified Euler system in this case is formally a scalar multiple of the conserved quantity {\int_{{\bf R}^2} \theta^2}. The momentum {\int_{{\bf R}^3} x \cdot \tilde u} for the modified Euler system is formally a scalar multiple of the conserved quantity {\int_{{\bf R}^2} \theta}, while the vortex stream lines that are preserved by the modified Euler flow become the level sets of the active scalar that are preserved by the SQG flow. On the other hand, the helicity {\int_{{\bf R}^3} \omega \cdot T^{-1} \tilde u} vanishes, and other conserved quantities for SQG (such as the Hamiltonian {\int_{{\bf R}^2} \theta |\nabla|^{-1} \theta}) do not seem to correspond to conserved quantities of the modified Euler system. This is not terribly surprising; a low-dimensional flow may well have a richer family of conservation laws than the higher-dimensional system that it is embedded in.

An extremely large portion of mathematics is concerned with locating solutions to equations such as

\displaystyle  f(x) = 0

or

\displaystyle  \Phi(x) = x \ \ \ \ \ (1)

for {x} in some suitable domain space (either finite-dimensional or infinite-dimensional), and various maps {f} or {\Phi}. To solve the fixed point iteration equation (1), the simplest general method available is the fixed point iteration method: one starts with an initial approximate solution {x_0} to (1), so that {\Phi(x_0) \approx x_0}, and then recursively constructs the sequence {x_1, x_2, x_3, \dots} by {x_n := \Phi(x_{n-1})}. If {\Phi} behaves enough like a “contraction”, and the domain is complete, then one can expect the {x_n} to converge to a limit {x}, which should then be a solution to (1). For instance, if {\Phi: X \rightarrow X} is a map from a metric space {X = (X,d)} to itself, which is a contraction in the sense that

\displaystyle  d( \Phi(x), \Phi(y) ) \leq (1-\eta) d(x,y)

for all {x,y \in X} and some {\eta>0}, then with {x_n} as above we have

\displaystyle  d( x_{n+1}, x_n ) \leq (1-\eta) d(x_n, x_{n-1} )

for any {n}, and so the distances {d(x_n, x_{n-1} )} between successive elements of the sequence decay at at least a geometric rate. This leads to the contraction mapping theorem, which has many important consequences, such as the inverse function theorem and the Picard existence theorem.

A slightly more complicated instance of this strategy arises when trying to linearise a complex map {f: U \rightarrow {\bf C}} defined in a neighbourhood {U} of a fixed point. For simplicity we normalise the fixed point to be the origin, thus {0 \in U} and {f(0)=0}. When studying the complex dynamics {f^2 = f \circ f}, {f^3 = f \circ f \circ f}, {\dots} of such a map, it can be useful to try to conjugate {f} to another function {g = \psi^{-1} \circ f \circ \psi}, where {\psi} is a holomorphic function defined and invertible near {0} with {\psi(0)=0}, since the dynamics of {g} will be conjguate to that of {f}. Note that if {f(0)=0} and {f'(0)=\lambda}, then from the chain rule any conjugate {g} of {f} will also have {g(0)=0} and {g'(0)=\lambda}. Thus, the “simplest” function one can hope to conjugate {f} to is the linear function {z \mapsto \lambda z}. Let us say that {f} is linearisable (around {0}) if it is conjugate to {z \mapsto \lambda z} in some neighbourhood of {0}. Equivalently, {f} is linearisable if there is a solution to the Schröder equation

\displaystyle  f( \psi(z) ) = \psi(\lambda z) \ \ \ \ \ (2)

for some {\psi: U' \rightarrow {\bf C}} defined and invertible in a neighbourhood {U'} of {0} with {\psi(0)=0}, and all {z} sufficiently close to {0}. (The Schröder equation is normalised somewhat differently in the literature, but this form is equivalent to the usual form, at least when {\lambda} is non-zero.) Note that if {\psi} solves the above equation, then so does {z \mapsto \psi(cz)} for any non-zero {c}, so we may normalise {\psi'(0)=1} in addition to {\psi(0)=0}, which also ensures local invertibility from the inverse function theorem. (Note from winding number considerations that {\psi} cannot be invertible near zero if {\psi'(0)} vanishes.)

We have the following basic result of Koenigs:

Theorem 1 (Koenig’s linearisation theorem) Let {f: U \rightarrow {\bf C}} be a holomorphic function defined near {0} with {f(0)=0} and {f'(0)=\lambda}. If {0 < |\lambda| < 1} (attracting case) or {1 < |\lambda| < \infty} (repelling case), then {f} is linearisable near zero.

Proof: Observe that if {f, \psi, \lambda} solve (2), then {f^{-1}, \psi^{-1}, \lambda^{-1}} solve (2) also (in a sufficiently small neighbourhood of zero). Thus we may reduce to the attractive case {0 < |\lambda| < 1}.

Let {r>0} be a sufficiently small radius, and let {X} denote the space of holomorphic functions {\psi: B(0,r) \rightarrow {\bf C}} on the complex disk {B(0,r) := \{z \in {\bf C}: |z| < r \}} with {\psi(0)=0} and {\psi'(0)=1}. We can view the Schröder equation (2) as a fixed point equation

\displaystyle  \psi = \Phi(\psi)

where {\Phi: X' \rightarrow X} is the partially defined function on {X} that maps a function {\psi: B(0,r) \rightarrow {\bf C}} to the function {\Phi(\psi): B(0,r) \rightarrow {\bf C}} defined by

\displaystyle  \Phi(\psi)(z) := f^{-1}( \psi( \lambda z ) ),

assuming that {f^{-1}} is well-defined on the range of {\psi(B(0,\lambda r))} (this is why {\Phi} is only partially defined).

We can solve this equation by the fixed point iteration method, if {r} is small enough. Namely, we start with {\psi_0: B(0,r) \rightarrow {\bf C}} being the identity map, and set {\psi_1 := \Phi(\psi_0), \psi_2 := \Phi(\psi_1)}, etc. We equip {X} with the uniform metric {d( \psi, \tilde \psi ) := \sup_{z \in B(0,r)} |\psi(z) - \tilde \psi(z)|}. Observe that if {d( \psi, \psi_0 ), d(\tilde \psi, \psi_0) \leq r}, and {r} is small enough, then {\psi, \tilde \psi} takes values in {B(0,2r)}, and {\Phi(\psi), \Phi(\tilde \psi)} are well-defined and lie in {X}. Also, since {f^{-1}} is smooth and has derivative {\lambda^{-1}} at {0}, we have

\displaystyle  |f^{-1}(z) - f^{-1}(w)| \leq (1+\varepsilon) |\lambda|^{-1} |z-w|

if {z, w \in B(0,r)}, {\varepsilon>0} and {r} is sufficiently small depending on {\varepsilon}. This is not yet enough to establish the required contraction (thanks to Mario Bonk for pointing this out); but observe that the function {\frac{\psi(z)-\tilde \psi(z)}{z^2}} is holomorphic on {B(0,r)} and bounded by {d(\psi,\tilde \psi)/r^2} on the boundary of this ball (or slightly within this boundary), so by the maximum principle we see that

\displaystyle  |\frac{\psi(z)-\tilde \psi(z)}{z^2}| \leq \frac{1}{r^2} d(\psi,\tilde \psi)

on all of {B(0,r)}, and in particular

\displaystyle  |\psi(z)-\tilde \psi(z)| \leq |\lambda|^2 d(\psi,\tilde \psi)

on {B(0,\lambda r)}. Putting all this together, we see that

\displaystyle  d( \Phi(\psi), \Phi(\tilde \psi)) \leq (1+\varepsilon) |\lambda| d(\psi, \tilde \psi);

since {|\lambda|<1}, we thus obtain a contraction on the ball {\{ \psi \in X: d(\psi,\psi_0) \leq r \}} if {\varepsilon} is small enough (and {r} sufficiently small depending on {\varepsilon}). From this (and the completeness of {X}, which follows from Morera’s theorem) we see that the iteration {\psi_n} converges (exponentially fast) to a limit {\psi \in X} which is a fixed point of {\Phi}, and thus solves Schröder’s equation, as required. \Box

Koenig’s linearisation theorem leaves open the indifferent case when {|\lambda|=1}. In the rationally indifferent case when {\lambda^n=1} for some natural number {n}, there is an obvious obstruction to linearisability, namely that {f^n = 1} (in particular, linearisation is not possible in this case when {f} is a non-trivial rational function). An obstruction is also present in some irrationally indifferent cases (where {|\lambda|=1} but {\lambda^n \neq 1} for any natural number {n}), if {\lambda} is sufficiently close to various roots of unity; the first result of this form is due to Cremer, and the optimal result of this type for quadratic maps was established by Yoccoz. In the other direction, we have the following result of Siegel:

Theorem 2 (Siegel’s linearisation theorem) Let {f: U \rightarrow {\bf C}} be a holomorphic function defined near {0} with {f(0)=0} and {f'(0)=\lambda}. If {|\lambda|=1} and one has the Diophantine condition {\frac{1}{|\lambda^n-1|} \leq C n^C} for all natural numbers {n} and some constant {C>0}, then {f} is linearisable at {0}.

The Diophantine condition can be relaxed to a more general condition involving the rational exponents of the phase {\theta} of {\lambda = e^{2\pi i \theta}}; this was worked out by Brjuno, with the condition matching the one later obtained by Yoccoz. Amusingly, while the set of Diophantine numbers (and hence the set of linearisable {\lambda}) has full measure on the unit circle, the set of non-linearisable {\lambda} is generic (the complement of countably many nowhere dense sets) due to the above-mentioned work of Cremer, leading to a striking disparity between the measure-theoretic and category notions of “largeness”.

Siegel’s theorem does not seem to be provable using a fixed point iteration method. However, it can be established by modifying another basic method to solve equations, namely Newton’s method. Let us first review how this method works to solve the equation {f(x)=0} for some smooth function {f: I \rightarrow {\bf R}} defined on an interval {I}. We suppose we have some initial approximant {x_0 \in I} to this equation, with {f(x_0)} small but not necessarily zero. To make the analysis more quantitative, let us suppose that the interval {[x_0-r_0,x_0+r_0]} lies in {I} for some {r_0>0}, and we have the estimates

\displaystyle  |f(x_0)| \leq \delta_0 r_0

\displaystyle  |f'(x)| \geq \eta_0

\displaystyle  |f''(x)| \leq \frac{1}{\eta_0 r_0}

for some {\delta_0 > 0} and {0 < \eta_0 < 1/2} and all {x \in [x_0-r_0,x_0+r_0]} (the factors of {r_0} are present to make {\delta_0,\eta_0} “dimensionless”).

Lemma 3 Under the above hypotheses, we can find {x_1} with {|x_1 - x_0| \leq \eta_0 r_0} such that

\displaystyle  |f(x_1)| \ll \delta_0^2 \eta_0^{-O(1)} r_0.

In particular, setting {r_1 := (1-\eta_0) r_0}, {\eta_1 := \eta_0/2}, and {\delta_1 = O(\delta_0^2 \eta_0^{-O(1)})}, we have {[x_1-r_1,x_1+r_1] \subset [x_0-r_0,x_0+r_0] \subset I}, and

\displaystyle  |f(x_1)| \leq \delta_1 r_1

\displaystyle  |f'(x)| \geq \eta_1

\displaystyle  |f''(x)| \leq \frac{1}{\eta_1 r_1}

for all {x \in [x_1-r_1,x_1+r_1]}.

The crucial point here is that the new error {\delta_1} is roughly the square of the previous error {\delta_0}. This leads to extremely fast (double-exponential) improvement in the error upon iteration, which is more than enough to absorb the exponential losses coming from the {\eta_0^{-O(1)}} factor.

Proof: If {\delta_0 > c \eta_0^{C}} for some absolute constants {C,c>0} then we may simply take {x_0=x_1}, so we may assume that {\delta_0 \leq c \eta_0^{C}} for some small {c>0} and large {C>0}. Using the Newton approximation {f(x_0+h) \approx f(x_0) + h f'(x_0)} we are led to the choice

\displaystyle  x_1 := x_0 - \frac{f(x_0)}{f'(x_0)}

for {x_1}. From the hypotheses on {f} and the smallness hypothesis on {\delta} we certainly have {|x_1-x_0| \leq \eta_0 r_0}. From Taylor’s theorem with remainder we have

\displaystyle  f(x_1) = f(x_0) - \frac{f(x_0)}{f'(x_0)} f'(x_0) + O( \frac{1}{\eta_0 r_0} |\frac{f(x_0)}{f'(x_0)}|^2 )

\displaystyle  = O( \frac{1}{\eta_0 r_0} (\frac{\delta_0 r_0}{\eta_0})^2 )

and the claim follows. \Box

We can iterate this procedure; starting with {x_0,\eta_0,r_0,\delta_0} as above, we obtain a sequence of nested intervals {[x_n-r_n,x_n+r_n]} with {f(x_n)| \leq \delta_n}, and with {\eta_n,r_n,\delta_n,x_n} evolving by the recursive equations and estimates

\displaystyle  \eta_n = \eta_{n-1} / 2

\displaystyle  r_n = (1 - \eta_{n-1}) r_{n-1}

\displaystyle  \delta_n = O( \delta_{n-1}^2 \eta_{n-1}^{-O(1)} )

\displaystyle  |x_n - x_{n-1}| \leq \eta_{n-1} r_{n-1}.

If {\delta_0} is sufficiently small depending on {\eta_0}, we see that {\delta_n} converges rapidly to zero (indeed, we can inductively obtain a bound of the form {\delta_n \leq \eta_0^{C (2^n + n)}} for some large absolute constant {C} if {\delta_0} is small enough), and {x_n} converges to a limit {x \in I} which then solves the equation {f(x)=0} by the continuity of {f}.

As I recently learned from Zhiqiang Li, a similar scheme works to prove Siegel’s theorem, as can be found for instance in this text of Carleson and Gamelin. The key is the following analogue of Lemma 3.

Lemma 4 Let {\lambda} be a complex number with {|\lambda|=1} and {\frac{1}{|\lambda^n-1|} \ll n^{O(1)}} for all natural numbers {n}. Let {r_0>0}, and let {f_0: B(0,r_0) \rightarrow {\bf C}} be a holomorphic function with {f_0(0)=0}, {f'_0(0)=\lambda}, and

\displaystyle  |f_0(z) - \lambda z| \leq \delta_0 r_0 \ \ \ \ \ (3)

for all {z \in B(0,r_0)} and some {\delta_0>0}. Let {0 < \eta_0 \leq 1/2}, and set {r_1 := (1-\eta_0) r_0}. Then there exists an injective holomorphic function {\psi_0: B(0, r_1) \rightarrow B(0, r_0)} and a holomorphic function {f_1: B(0,r_1) \rightarrow {\bf C}} such that

\displaystyle  f_0( \psi_1(z) ) = \psi_1(f_1(z)) \ \ \ \ \ (4)

for all {z \in B(0,r_1)}, and such that

\displaystyle  |\psi_1(z) - z| \ll \delta_0 \eta_0^{-O(1)} r_1

and

\displaystyle  |f_1(z) - \lambda z| \leq \delta_1 r_1

for all {z \in B(0,r_1)} and some {\delta_1 = O(\delta_0^2 \eta_0^{-O(1)})}.

Proof: By scaling we may normalise {r_0=1}. If {\delta_0 > c \eta_0^C} for some constants {c,C>0}, then we can simply take {\psi_1} to be the identity and {f_1=f_0}, so we may assume that {\delta_0 \leq c \eta_0^C} for some small {c>0} and large {C>0}.

To motivate the choice of {\psi_1}, we write {f_0(z) = \lambda z + \hat f_0(z)} and {\psi_1(z) = z + \hat \psi(z)}, with {\hat f_0} and {\hat \psi_1} viewed as small. We would like to have {f_0(\psi_1(z)) \approx \psi_1(\lambda z)}, which expands as

\displaystyle  \lambda z + \lambda \hat \psi_1(z) + \hat f_0( z + \hat \psi_1(z) ) \approx \lambda z + \hat \psi_1(\lambda z).

As {\hat f_0} and {\hat \psi} are both small, we can heuristically approximate {\hat f_0(z + \hat \psi_1(z) ) \approx \hat f_0(z)} up to quadratic errors (compare with the Newton approximation {f(x_0+h) \approx f(x_0) + h f'(x_0)}), and arrive at the equation

\displaystyle  \hat \psi_1(\lambda z) - \lambda \hat \psi_1(z) = \hat f_0(z). \ \ \ \ \ (5)

This equation can be solved by Taylor series; the function {\hat f_0} vanishes to second order at the origin and thus has a Taylor expansion

\displaystyle  \hat f_0(z) = \sum_{n=2}^\infty a_n z^n

and then {\hat \psi_1} has a Taylor expansion

\displaystyle  \hat \psi_1(z) = \sum_{n=2}^\infty \frac{a_n}{\lambda^n - \lambda} z^n.

We take this as our definition of {\hat \psi_1}, define {\psi_1(z) := z + \hat \psi_1(z)}, and then define {f_1} implicitly via (4).

Let us now justify that this choice works. By (3) and the generalised Cauchy integral formula, we have {|a_n| \leq \delta_0} for all {n}; by the Diophantine assumption on {\lambda}, we thus have {|\frac{a_n}{\lambda^n - \lambda}| \ll \delta_0 n^{O(1)}}. In particular, {\hat \psi_1} converges on {B(0,1)}, and on the disk {B(0, (1-\eta_0/4))} (say) we have the bounds

\displaystyle  |\hat \psi_1(z)|, |\hat \psi'_1(z)| \ll \delta_0 \sum_{n=2}^\infty n^{O(1)} (1-\eta_0/4)^n \ll \eta_0^{-O(1)} \delta_0. \ \ \ \ \ (6)

In particular, as {\delta_0} is so small, we see that {\psi_1} maps {B(0, (1-\eta_0/4))} injectively to {B(0,1)} and {B(0,1-\eta_0)} to {B(0,1-3\eta_0/4)}, and the inverse {\psi_1^{-1}} maps {B(0, (1-\eta_0/2))} to {B(0, (1-\eta_0/4))}. From (3) we see that {f_0} maps {B(0,1-3\eta_0/4)} to {B(0,1-\eta_0/2)}, and so if we set {f_1: B(0,1-\eta_0) \rightarrow B(0,1-\eta_0/4)} to be the function {f_1 := \psi_1^{-1} \circ f_0 \circ \psi_1}, then {f_1} is a holomorphic function obeying (4). Expanding (4) in terms of {\hat f_0} and {\hat \psi_1} as before, and also writing {f_1(z) = \lambda z + \hat f_1(z)}, we have

\displaystyle  \lambda z + \lambda \hat \psi_1(z) + \hat f_0( z + \hat \psi_1(z) ) = \lambda z + \hat f_1(z) + \hat \psi_1(\lambda z + \hat f_1(z))

for {z \in B(0, 1-\eta_0)}, which by (5) simplifies to

\displaystyle  \hat f_1(z) = \hat f_0( z + \hat \psi_1(z) ) - \hat f_0(z) + \hat \psi_1(\lambda z) - \hat \psi_1(\lambda z + \hat f_1(z)).

From (6), the fundamental theorem of calculus, and the smallness of {\delta_0} we have

\displaystyle  |\hat \psi_1(\lambda z) - \hat \psi_1(\lambda z + \hat f_1(z))| \leq \frac{1}{2} |\hat f_1(z)|

and thus

\displaystyle  |\hat f_1(z)| \leq 2 |\hat f_0( z + \hat \psi_1(z) ) - \hat f_0(z)|.

From (3) and the Cauchy integral formula we have {\hat f'_0(z) = O( \delta_0 \eta_0^{-O(1)})} on (say) {B(0,1-\eta_0/4)}, and so from (6) and the fundamental theorem of calculus we conclude that

\displaystyle  |\hat f_1(z)| \ll \delta_0^2 \eta_0^{-O(1)}

on {B(0,1-\eta_0)}, and the claim follows. \Box

If we set {\eta_0 := 1/2}, {f_0 := f}, and {\delta_0>0} to be sufficiently small, then (since {f(z)-\lambda z} vanishes to second order at the origin), the hypotheses of this lemma will be obeyed for some sufficiently small {r_0}. Iterating the lemma (and halving {\eta_0} repeatedly), we can then find sequences {\eta_n, \delta_n, r_n > 0}, injective holomorphic functions {\psi_n: B(0,r_n) \rightarrow B(0,r_{n-1})} and holomorphic functions {f_n: B(0,r_n) \rightarrow {\bf C}} such that one has the recursive identities and estimates

\displaystyle  \eta_n = \eta_{n-1} / 2

\displaystyle  r_n = (1 - \eta_{n-1}) r_{n-1}

\displaystyle  \delta_n = O( \delta_{n-1}^2 \eta_{n-1}^{-O(1)} )

\displaystyle  |\psi_n(z) - z| \ll \delta_{n-1} \eta_{n-1}^{-O(1)} r_n

\displaystyle  |f_n(z) - \lambda z| \leq \delta_n r_n

\displaystyle  f_{n-1}( \psi_n(z) ) = \psi_n(f_n(z))

for all {n \geq 1} and {z \in B(0,r_n)}. By construction, {r_n} decreases to a positive radius {r_\infty} that is a constant multiple of {r_0}, while (for {\delta_0} small enough) {\delta_n} converges double-exponentially to zero, so in particular {f_n(z)} converges uniformly to {\lambda z} on {B(0,r_\infty)}. Also, {\psi_n} is close enough to the identity, the compositions {\Psi_n := \psi_1 \circ \dots \circ \psi_n} are uniformly convergent on {B(0,r_\infty/2)} with {\Psi_n(0)=0} and {\Psi'_n(0)=1}. From this we have

\displaystyle  f( \Psi_n(z) ) = \Psi_n(f_n(z))

on {B(0,r_\infty/4)}, and on taking limits using Morera’s theorem we obtain a holomorphic function {\Psi} defined near {0} with {\Psi(0)=0}, {\Psi'(0)=1}, and

\displaystyle  f( \Psi(z) ) = \Psi(\lambda z),

obtaining the required linearisation.

Remark 5 The idea of using a Newton-type method to obtain error terms that decay double-exponentially, and can therefore absorb exponential losses in the iteration, also occurs in KAM theory and in Nash-Moser iteration, presumably due to Siegel’s influence on Moser. (I discuss Nash-Moser iteration in this note that I wrote back in 2006.)

The von Neumann ergodic theorem (the Hilbert space version of the mean ergodic theorem) asserts that if {U: H \rightarrow H} is a unitary operator on a Hilbert space {H}, and {v \in H} is a vector in that Hilbert space, then one has

\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N U^n v = \pi_{H^U} v

in the strong topology, where {H^U := \{ w \in H: Uw = w \}} is the {U}-invariant subspace of {H}, and {\pi_{H^U}} is the orthogonal projection to {H^U}. (See e.g. these previous lecture notes for a proof.) The same proof extends to more general amenable groups: if {G} is a countable amenable group acting on a Hilbert space {H} by unitary transformations {T^g: H \rightarrow H} for {g \in G}, and {v \in H} is a vector in that Hilbert space, then one has

\displaystyle \lim_{N \rightarrow \infty} \mathop{\bf E}_{g \in \Phi_N} T^g v = \pi_{H^G} v \ \ \ \ \ (1)

 

for any Folner sequence {\Phi_N} of {G}, where {H^G := \{ w \in H: T^g w = w \hbox{ for all }g \in G \}} is the {G}-invariant subspace, and {\mathop{\bf E}_{a \in A} f(a) := \frac{1}{|A|} \sum_{a \in A} f(a)} is the average of {f} on {A}. Thus one can interpret {\pi_{H^G} v} as a certain average of elements of the orbit {Gv := \{ T^g v: g \in G \}} of {v}.

In a previous blog post, I noted a variant of this ergodic theorem (due to Alaoglu and Birkhoff) that holds even when the group {G} is not amenable (or not discrete), using a more abstract notion of averaging:

Theorem 1 (Abstract ergodic theorem) Let {G} be an arbitrary group acting unitarily on a Hilbert space {H}, and let {v} be a vector in {H}. Then {\pi_{H^G} v} is the element in the closed convex hull of {Gv := \{ T^g v: g \in G \}} of minimal norm, and is also the unique element of {H^G} in this closed convex hull.

I recently stumbled upon a different way to think about this theorem, in the additive case {G = (G,+)} when {G} is abelian, which has a closer resemblance to the classical mean ergodic theorem. Given an arbitrary additive group {G = (G,+)} (not necessarily discrete, or countable), let {{\mathcal F}} denote the collection of finite non-empty multisets in {G} – that is to say, unordered collections {\{a_1,\dots,a_n\}} of elements {a_1,\dots,a_n} of {G}, not necessarily distinct, for some positive integer {n}. Given two multisets {A = \{a_1,\dots,a_n\}}, {B = \{b_1,\dots,b_m\}} in {{\mathcal F}}, we can form the sum set {A + B := \{ a_i + b_j: 1 \leq i \leq n, 1 \leq j \leq m \}}. Note that the sum set {A+B} can contain multiplicity even when {A, B} do not; for instance, {\{ 1,2\} + \{1,2\} = \{2,3,3,4\}}. Given a multiset {A = \{a_1,\dots,a_n\}} in {{\mathcal F}}, and a function {f: G \rightarrow H} from {G} to a vector space {H}, we define the average {\mathop{\bf E}_{a \in A} f(a)} as

\displaystyle \mathop{\bf E}_{a \in A} f(a) = \frac{1}{n} \sum_{j=1}^n f(a_j).

Note that the multiplicity function of the set {A} affects the average; for instance, we have {\mathop{\bf E}_{a \in \{1,2\}} a = \frac{3}{2}}, but {\mathop{\bf E}_{a \in \{1,2,2\}} a = \frac{5}{3}}.

We can define a directed set on {{\mathcal F}} as follows: given two multisets {A,B \in {\mathcal F}}, we write {A \geq B} if we have {A = B+C} for some {C \in {\mathcal F}}. Thus for instance we have {\{ 1, 2, 2, 3\} \geq \{1,2\}}. It is easy to verify that this operation is transitive and reflexive, and is directed because any two elements {A,B} of {{\mathcal F}} have a common upper bound, namely {A+B}. (This is where we need {G} to be abelian.) The notion of convergence along a net, now allows us to define the notion of convergence along {{\mathcal F}}; given a family {x_A} of points in a topological space {X} indexed by elements {A} of {{\mathcal F}}, and a point {x} in {X}, we say that {x_A} converges to {x} along {{\mathcal F}} if, for every open neighbourhood {U} of {x} in {X}, one has {x_A \in U} for sufficiently large {A}, that is to say there exists {B \in {\mathcal F}} such that {x_A \in U} for all {A \geq B}. If the topological space {V} is Hausdorff, then the limit {x} is unique (if it exists), and we then write

\displaystyle x = \lim_{A \rightarrow G} x_A.

When {x_A} takes values in the reals, one can also define the limit superior or limit inferior along such nets in the obvious fashion.

We can then give an alternate formulation of the abstract ergodic theorem in the abelian case:

Theorem 2 (Abelian abstract ergodic theorem) Let {G = (G,+)} be an arbitrary additive group acting unitarily on a Hilbert space {H}, and let {v} be a vector in {H}. Then we have

\displaystyle \pi_{H^G} v = \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v

in the strong topology of {H}.

Proof: Suppose that {A \geq B}, so that {A=B+C} for some {C \in {\mathcal F}}, then

\displaystyle \mathop{\bf E}_{a \in A} T^a v = \mathop{\bf E}_{c \in C} T^c ( \mathop{\bf E}_{b \in B} T^b v )

so by unitarity and the triangle inequality we have

\displaystyle \| \mathop{\bf E}_{a \in A} T^a v \|_H \leq \| \mathop{\bf E}_{b \in B} T^b v \|_H,

thus {\| \mathop{\bf E}_{a \in A} T^a v \|_H^2} is monotone non-increasing in {A}. Since this quantity is bounded between {0} and {\|v\|_H}, we conclude that the limit {\lim_{A \rightarrow G} \| \mathop{\bf E}_{a \in A} T^a v \|_H^2} exists. Thus, for any {\varepsilon > 0}, we have for sufficiently large {A} that

\displaystyle \| \mathop{\bf E}_{b \in B} T^b v \|_H^2 \geq \| \mathop{\bf E}_{a \in A} T^a v \|_H^2 - \varepsilon

for all {B \geq A}. In particular, for any {g \in G}, we have

\displaystyle \| \mathop{\bf E}_{b \in A + \{0,g\}} T^b v \|_H^2 \geq \| \mathop{\bf E}_{a \in A} T^a v \|_H^2 - \varepsilon.

We can write

\displaystyle \mathop{\bf E}_{b \in A + \{0,g\}} T^b v = \frac{1}{2} \mathop{\bf E}_{a \in A} T^a v + \frac{1}{2} T^g \mathop{\bf E}_{a \in A} T^a v

and so from the parallelogram law and unitarity we have

\displaystyle \| \mathop{\bf E}_{a \in A} T^a v - T^g \mathop{\bf E}_{a \in A} T^a v \|_H^2 \leq 4 \varepsilon

for all {g \in G}, and hence by the triangle inequality (averaging {g} over a finite multiset {C})

\displaystyle \| \mathop{\bf E}_{a \in A} T^a v - \mathop{\bf E}_{b \in A+C} T^b v \|_H^2 \leq 4 \varepsilon

for any {C \in {\mathcal F}}. This shows that {\mathop{\bf E}_{a \in A} T^a v} is a Cauchy sequence in {H} (in the strong topology), and hence (by the completeness of {H}) tends to a limit. Shifting {A} by a group element {g}, we have

\displaystyle \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v = \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A + \{g\}} T^a v = T^g \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v

and hence {\lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v} is invariant under shifts, and thus lies in {H^G}. On the other hand, for any {w \in H^G} and {A \in {\mathcal F}}, we have

\displaystyle \langle \mathop{\bf E}_{a \in A} T^a v, w \rangle_H = \mathop{\bf E}_{a \in A} \langle v, T^{-a} w \rangle_H = \langle v, w \rangle_H

and thus on taking strong limits

\displaystyle \langle \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v, w \rangle_H = \langle v, w \rangle_H

and so {v - \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v} is orthogonal to {H^G}. Combining these two facts we see that {\lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^a v} is equal to {\pi_{H^G} v} as claimed. \Box

To relate this result to the classical ergodic theorem, we observe

Lemma 3 Let {G} be a countable additive group, with a F{\o}lner sequence {\Phi_n}, and let {f_g} be a bounded sequence in a normed vector space indexed by {G}. If {\lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} f_a} exists, then {\lim_{n \rightarrow \infty} \mathop{\bf E}_{a \in \Phi_n} f_a} exists, and the two limits are equal.

Proof: From the F{\o}lner property, we see that for any {A} and any {\varepsilon>0}, the averages {\mathop{\bf E}_{a \in \Phi_n} f_a} and {\mathop{\bf E}_{a \in A+\Phi_n} f_a} differ by at most {\varepsilon} in norm if {n} is sufficiently large depending on {A}, {\varepsilon} (and the {f_a}). On the other hand, by the existence of the limit {\lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} f_a}, the averages {\mathop{\bf E}_{a \in A} f_a} and {\mathop{\bf E}_{a \in A + \Phi_n} f_a} differ by at most {\varepsilon} in norm if {A} is sufficiently large depending on {\varepsilon} (regardless of how large {n} is). The claim follows. \Box

It turns out that this approach can also be used as an alternate way to construct the GowersHost-Kra seminorms in ergodic theory, which has the feature that it does not explicitly require any amenability on the group {G} (or separability on the underlying measure space), though, as pointed out to me in comments, even uncountable abelian groups are amenable in the sense of possessing an invariant mean, even if they do not have a F{\o}lner sequence.

Given an arbitrary additive group {G}, define a {G}-system {({\mathrm X}, T)} to be a probability space {{\mathrm X} = (X, {\mathcal X}, \mu)} (not necessarily separable or standard Borel), together with a collection {T^g: X \rightarrow X} of invertible, measure-preserving maps, such that {T^0} is the identity and {T^g T^h = T^{g+h}} (modulo null sets) for all {g,h \in G}. This then gives isomorphisms {T^g: L^p({\mathrm X}) \rightarrow L^p({\mathrm X})} for {1 \leq p \leq \infty} by setting {T^g f(x) := f(T^{-g} x)}. From the above abstract ergodic theorem, we see that

\displaystyle {\mathbf E}( f | {\mathcal X}^G ) = \lim_{A \rightarrow G} \mathop{\bf E}_{a \in A} T^g f

in the strong topology of {L^2({\mathrm X})} for any {f \in L^2({\mathrm X})}, where {{\mathcal X}^G} is the collection of measurable sets {E} that are essentially {G}-invariant in the sense that {T^g E = E} modulo null sets for all {g \in G}, and {{\mathbf E}(f|{\mathcal X}^G)} is the conditional expectation of {f} with respect to {{\mathcal X}^G}.

In a similar spirit, we have

Theorem 4 (Convergence of Gowers-Host-Kra seminorms) Let {({\mathrm X},T)} be a {G}-system for some additive group {G}. Let {d} be a natural number, and for every {\omega \in\{0,1\}^d}, let {f_\omega \in L^{2^d}({\mathrm X})}, which for simplicity we take to be real-valued. Then the expression

\displaystyle \langle (f_\omega)_{\omega \in \{0,1\}^d} \rangle_{U^d({\mathrm X})} := \lim_{A_1,\dots,A_d \rightarrow G}

\displaystyle \mathop{\bf E}_{h_1 \in A_1-A_1,\dots,h_d \in A_d-A_d} \int_X \prod_{\omega \in \{0,1\}^d} T^{\omega_1 h_1 + \dots + \omega_d h_d} f_\omega\ d\mu

converges, where we write {\omega = (\omega_1,\dots,\omega_d)}, and we are using the product direct set on {{\mathcal F}^d} to define the convergence {A_1,\dots,A_d \rightarrow G}. In particular, for {f \in L^{2^d}({\mathrm X})}, the limit

\displaystyle \| f \|_{U^d({\mathrm X})}^{2^d} = \lim_{A_1,\dots,A_d \rightarrow G}

\displaystyle \mathop{\bf E}_{h_1 \in A_1-A_1,\dots,h_d \in A_d-A_d} \int_X \prod_{\omega \in \{0,1\}^d} T^{\omega_1 h_1 + \dots + \omega_d h_d} f\ d\mu

converges.

We prove this theorem below the fold. It implies a number of other known descriptions of the Gowers-Host-Kra seminorms {\|f\|_{U^d({\mathrm X})}}, for instance that

\displaystyle \| f \|_{U^d({\mathrm X})}^{2^d} = \lim_{A \rightarrow G} \mathop{\bf E}_{h \in A-A} \| f T^h f \|_{U^{d-1}({\mathrm X})}^{2^{d-1}}

for {d > 1}, while from the ergodic theorem we have

\displaystyle \| f \|_{U^1({\mathrm X})} = \| {\mathbf E}( f | {\mathcal X}^G ) \|_{L^2({\mathrm X})}.

This definition also manifestly demonstrates the cube symmetries of the Host-Kra measures {\mu^{[d]}} on {X^{\{0,1\}^d}}, defined via duality by requiring that

\displaystyle \langle (f_\omega)_{\omega \in \{0,1\}^d} \rangle_{U^d({\mathrm X})} = \int_{X^{\{0,1\}^d}} \bigotimes_{\omega \in \{0,1\}^d} f_\omega\ d\mu^{[d]}.

In a subsequent blog post I hope to present a more detailed study of the {U^2} norm and its relationship with eigenfunctions and the Kronecker factor, without assuming any amenability on {G} or any separability or topological structure on {{\mathrm X}}.

Read the rest of this entry »

In 1946, Ulam, in response to a theorem of Anning and Erdös, posed the following problem:

Problem 1 (Erdös-Ulam problem) Let {S \subset {\bf R}^2} be a set such that the distance between any two points in {S} is rational. Is it true that {S} cannot be (topologically) dense in {{\bf R}^2}?

The paper of Anning and Erdös addressed the case that all the distances between two points in {S} were integer rather than rational in the affirmative.

The Erdös-Ulam problem remains open; it was discussed recently over at Gödel’s lost letter. It is in fact likely (as we shall see below) that the set {S} in the above problem is not only forbidden to be topologically dense, but also cannot be Zariski dense either. If so, then the structure of {S} is quite restricted; it was shown by Solymosi and de Zeeuw that if {S} fails to be Zariski dense, then all but finitely many of the points of {S} must lie on a single line, or a single circle. (Conversely, it is easy to construct examples of dense subsets of a line or circle in which all distances are rational, though in the latter case the square of the radius of the circle must also be rational.)

The main tool of the Solymosi-de Zeeuw analysis was Faltings’ celebrated theorem that every algebraic curve of genus at least two contains only finitely many rational points. The purpose of this post is to observe that an affirmative answer to the full Erdös-Ulam problem similarly follows from the conjectured analogue of Falting’s theorem for surfaces, namely the following conjecture of Bombieri and Lang:

Conjecture 2 (Bombieri-Lang conjecture) Let {X} be a smooth projective irreducible algebraic surface defined over the rationals {{\bf Q}} which is of general type. Then the set {X({\bf Q})} of rational points of {X} is not Zariski dense in {X}.

In fact, the Bombieri-Lang conjecture has been made for varieties of arbitrary dimension, and for more general number fields than the rationals, but the above special case of the conjecture is the only one needed for this application. We will review what “general type” means (for smooth projective complex varieties, at least) below the fold.

The Bombieri-Lang conjecture is considered to be extremely difficult, in particular being substantially harder than Faltings’ theorem, which is itself a highly non-trivial result. So this implication should not be viewed as a practical route to resolving the Erdös-Ulam problem unconditionally; rather, it is a demonstration of the power of the Bombieri-Lang conjecture. Still, it was an instructive algebraic geometry exercise for me to carry out the details of this implication, which quickly boils down to verifying that a certain quite explicit algebraic surface is of general type (Theorem 4 below). As I am not an expert in the subject, my computations here will be rather tedious and pedestrian; it is likely that they could be made much slicker by exploiting more of the machinery of modern algebraic geometry, and I would welcome any such streamlining by actual experts in this area. (For similar reasons, there may be more typos and errors than usual in this post; corrections are welcome as always.) My calculations here are based on a similar calculation of van Luijk, who used analogous arguments to show (assuming Bombieri-Lang) that the set of perfect cuboids is not Zariski-dense in its projective parameter space.

We also remark that in a recent paper of Makhul and Shaffaf, the Bombieri-Lang conjecture (or more precisely, a weaker consequence of that conjecture) was used to show that if {S} is a subset of {{\bf R}^2} with rational distances which intersects any line in only finitely many points, then there is a uniform bound on the cardinality of the intersection of {S} with any line. I have also recently learned (private communication) that an unpublished work of Shaffaf has obtained a result similar to the one in this post, namely that the Erdös-Ulam conjecture follows from the Bombieri-Lang conjecture, plus an additional conjecture about the rational curves in a specific surface.

Let us now give the elementary reductions to the claim that a certain variety is of general type. For sake of contradiction, let {S} be a dense set such that the distance between any two points is rational. Then {S} certainly contains two points that are a rational distance apart. By applying a translation, rotation, and a (rational) dilation, we may assume that these two points are {(0,0)} and {(1,0)}. As {S} is dense, there is a third point of {S} not on the {x} axis, which after a reflection we can place in the upper half-plane; we will write it as {(a,\sqrt{b})} with {b>0}.

Given any two points {P, Q} in {S}, the quantities {|P|^2, |Q|^2, |P-Q|^2} are rational, and so by the cosine rule the dot product {P \cdot Q} is rational as well. Since {(1,0) \in S}, this implies that the {x}-component of every point {P} in {S} is rational; this in turn implies that the product of the {y}-coordinates of any two points {P,Q} in {S} is rational as well (since this differs from {P \cdot Q} by a rational number). In particular, {a} and {b} are rational, and all of the points in {S} now lie in the lattice {\{ ( x, y\sqrt{b}): x, y \in {\bf Q} \}}. (This fact appears to have first been observed in the 1988 habilitationschrift of Kemnitz.)

Now take four points {(x_j,y_j \sqrt{b})}, {j=1,\dots,4} in {S} in general position (so that the octuplet {(x_1,y_1\sqrt{b},\dots,x_4,y_4\sqrt{b})} avoids any pre-specified hypersurface in {{\bf C}^8}); this can be done if {S} is dense. (If one wished, one could re-use the three previous points {(0,0), (1,0), (a,\sqrt{b})} to be three of these four points, although this ultimately makes little difference to the analysis.) If {(x,y\sqrt{b})} is any point in {S}, then the distances {r_j} from {(x,y\sqrt{b})} to {(x_j,y_j\sqrt{b})} are rationals that obey the equations

\displaystyle (x - x_j)^2 + b (y-y_j)^2 = r_j^2

for {j=1,\dots,4}, and thus determine a rational point in the affine complex variety {V = V_{b,x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4} \subset {\bf C}^5} defined as

\displaystyle V := \{ (x,y,r_1,r_2,r_3,r_4) \in {\bf C}^6:

\displaystyle (x - x_j)^2 + b (y-y_j)^2 = r_j^2 \hbox{ for } j=1,\dots,4 \}.

By inspecting the projection {(x,y,r_1,r_2,r_3,r_4) \rightarrow (x,y)} from {V} to {{\bf C}^2}, we see that {V} is a branched cover of {{\bf C}^2}, with the generic cover having {2^4=16} points (coming from the different ways to form the square roots {r_1,r_2,r_3,r_4}); in particular, {V} is a complex affine algebraic surface, defined over the rationals. By inspecting the monodromy around the four singular base points {(x,y) = (x_i,y_i)} (which switch the sign of one of the roots {r_i}, while keeping the other three roots unchanged), we see that the variety {V} is connected away from its singular set, and thus irreducible. As {S} is topologically dense in {{\bf R}^2}, it is Zariski-dense in {{\bf C}^2}, and so {S} generates a Zariski-dense set of rational points in {V}. To solve the Erdös-Ulam problem, it thus suffices to show that

Claim 3 For any non-zero rational {b} and for rationals {x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4} in general position, the rational points of the affine surface {V = V_{b,x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4}} is not Zariski dense in {V}.

This is already very close to a claim that can be directly resolved by the Bombieri-Lang conjecture, but {V} is affine rather than projective, and also contains some singularities. The first issue is easy to deal with, by working with the projectivisation

\displaystyle \overline{V} := \{ [X,Y,Z,R_1,R_2,R_3,R_4] \in {\bf CP}^6: Q(X,Y,Z,R_1,R_2,R_3,R_4) = 0 \} \ \ \ \ \ (1)

 

of {V}, where {Q: {\bf C}^7 \rightarrow {\bf C}^4} is the homogeneous quadratic polynomial

\displaystyle (X,Y,Z,R_1,R_2,R_3,R_4) := (Q_j(X,Y,Z,R_1,R_2,R_3,R_4) )_{j=1}^4

with

\displaystyle Q_j(X,Y,Z,R_1,R_2,R_3,R_4) := (X-x_j Z)^2 + b (Y-y_jZ)^2 - R_j^2

and the projective complex space {{\bf CP}^6} is the space of all equivalence classes {[X,Y,Z,R_1,R_2,R_3,R_4]} of tuples {(X,Y,Z,R_1,R_2,R_3,R_4) \in {\bf C}^7 \backslash \{0\}} up to projective equivalence {(\lambda X, \lambda Y, \lambda Z, \lambda R_1, \lambda R_2, \lambda R_3, \lambda R_4) \sim (X,Y,Z,R_1,R_2,R_3,R_4)}. By identifying the affine point {(x,y,r_1,r_2,r_3,r_4)} with the projective point {(X,Y,1,R_1,R_2,R_3,R_4)}, we see that {\overline{V}} consists of the affine variety {V} together with the set {\{ [X,Y,0,R_1,R_2,R_3,R_4]: X^2+bY^2=R^2; R_j = \pm R_1 \hbox{ for } j=2,3,4\}}, which is the union of eight curves, each of which lies in the closure of {V}. Thus {\overline{V}} is the projective closure of {V}, and is thus a complex irreducible projective surface, defined over the rationals. As {\overline{V}} is cut out by four quadric equations in {{\bf CP}^6} and has degree sixteen (as can be seen for instance by inspecting the intersection of {\overline{V}} with a generic perturbation of a fibre over the generically defined projection {[X,Y,Z,R_1,R_2,R_3,R_4] \mapsto [X,Y,Z]}), it is also a complete intersection. To show (3), it then suffices to show that the rational points in {\overline{V}} are not Zariski dense in {\overline{V}}.

Heuristically, the reason why we expect few rational points in {\overline{V}} is as follows. First observe from the projective nature of (1) that every rational point is equivalent to an integer point. But for a septuple {(X,Y,Z,R_1,R_2,R_3,R_4)} of integers of size {O(N)}, the quantity {Q(X,Y,Z,R_1,R_2,R_3,R_4)} is an integer point of {{\bf Z}^4} of size {O(N^2)}, and so should only vanish about {O(N^{-8})} of the time. Hence the number of integer points {(X,Y,Z,R_1,R_2,R_3,R_4) \in {\bf Z}^7} of height comparable to {N} should be about

\displaystyle O(N)^7 \times O(N^{-8}) = O(N^{-1});

this is a convergent sum if {N} ranges over (say) powers of two, and so from standard probabilistic heuristics (see this previous post) we in fact expect only finitely many solutions, in the absence of any special algebraic structure (e.g. the structure of an abelian variety, or a birational reduction to a simpler variety) that could produce an unusually large number of solutions.

The Bombieri-Lang conjecture, Conjecture 2, can be viewed as a formalisation of the above heuristics (roughly speaking, it is one of the most optimistic natural conjectures one could make that is compatible with these heuristics while also being invariant under birational equivalence).

Unfortunately, {\overline{V}} contains some singular points. Being a complete intersection, this occurs when the Jacobian matrix of the map {Q: {\bf C}^7 \rightarrow {\bf C}^4} has less than full rank, or equivalently that the gradient vectors

\displaystyle \nabla Q_j = (2(X-x_j Z), 2(Y-y_j Z), -2x_j (X-x_j Z) - 2y_j (Y-y_j Z), \ \ \ \ \ (2)

 

\displaystyle 0, \dots, 0, -2R_j, 0, \dots, 0)

for {j=1,\dots,4} are linearly dependent, where the {-2R_j} is in the coordinate position associated to {R_j}. One way in which this can occur is if one of the gradient vectors {\nabla Q_j} vanish identically. This occurs at precisely {4 \times 2^3 = 32} points, when {[X,Y,Z]} is equal to {[x_j,y_j,1]} for some {j=1,\dots,4}, and one has {R_k = \pm ( (x_j - x_k)^2 + b (y_j - y_k)^2 )^{1/2}} for all {k=1,\dots,4} (so in particular {R_j=0}). Let us refer to these as the obvious singularities; they arise from the geometrically evident fact that the distance function {(x,y\sqrt{b}) \mapsto \sqrt{(x-x_j)^2 + b(y-y_j)^2}} is singular at {(x_j,y_j\sqrt{b})}.

The other way in which could occur is if a non-trivial linear combination of at least two of the gradient vectors vanishes. From (2), this can only occur if {R_j=R_k=0} for some distinct {j,k}, which from (1) implies that

\displaystyle (X - x_j Z) = \pm \sqrt{b} i (Y - y_j Z) \ \ \ \ \ (3)

 

and

\displaystyle (X - x_k Z) = \pm \sqrt{b} i (Y - y_k Z) \ \ \ \ \ (4)

 

for two choices of sign {\pm}. If the signs are equal, then (as {x_j, y_j, x_k, y_k} are in general position) this implies that {Z=0}, and then we have the singular point

\displaystyle [X,Y,Z,R_1,R_2,R_3,R_4] = [\pm \sqrt{b} i, 1, 0, 0, 0, 0, 0]. \ \ \ \ \ (5)

 

If the non-trivial linear combination involved three or more gradient vectors, then by the pigeonhole principle at least two of the signs involved must be equal, and so the only singular points are (5). So the only remaining possibility is when we have two gradient vectors {\nabla Q_j, \nabla Q_k} that are parallel but non-zero, with the signs in (3), (4) opposing. But then (as {x_j,y_j,x_k,y_k} are in general position) the vectors {(X-x_j Z, Y-y_j Z), (X-x_k Z, Y-y_k Z)} are non-zero and non-parallel to each other, a contradiction. Thus, outside of the {32} obvious singular points mentioned earlier, the only other singular points are the two points (5).

We will shortly show that the {32} obvious singularities are ordinary double points; the surface {\overline{V}} near any of these points is analytically equivalent to an ordinary cone {\{ (x,y,z) \in {\bf C}^3: z^2 = x^2 + y^2 \}} near the origin, which is a cone over a smooth conic curve {\{ (x,y) \in {\bf C}^2: x^2+y^2=1\}}. The two non-obvious singularities (5) are slightly more complicated than ordinary double points, they are elliptic singularities, which approximately resemble a cone over an elliptic curve. (As far as I can tell, this resemblance is exact in the category of real smooth manifolds, but not in the category of algebraic varieties.) If one blows up each of the point singularities of {\overline{V}} separately, no further singularities are created, and one obtains a smooth projective surface {X} (using the Segre embedding as necessary to embed {X} back into projective space, rather than in a product of projective spaces). Away from the singularities, the rational points of {\overline{V}} lift up to rational points of {X}. Assuming the Bombieri-Lang conjecture, we thus are able to answer the Erdös-Ulam problem in the affirmative once we establish

Theorem 4 The blowup {X} of {\overline{V}} is of general type.

This will be done below the fold, by the pedestrian device of explicitly constructing global differential forms on {X}; I will also be working from a complex analysis viewpoint rather than an algebraic geometry viewpoint as I am more comfortable with the former approach. (As mentioned above, though, there may well be a quicker way to establish this result by using more sophisticated machinery.)

I thank Mark Green and David Gieseker for helpful conversations (and a crash course in varieties of general type!).

Remark 5 The above argument shows in fact (assuming Bombieri-Lang) that sets {S \subset {\bf R}^2} with all distances rational cannot be Zariski-dense, and thus (by Solymosi-de Zeeuw) must lie on a single line or circle with only finitely many exceptions. Assuming a stronger version of Bombieri-Lang involving a general number field {K}, we obtain a similar conclusion with “rational” replaced by “lying in {K}” (one has to extend the Solymosi-de Zeeuw analysis to more general number fields, but this should be routine, using the analogue of Faltings’ theorem for such number fields).

Read the rest of this entry »

Many problems and results in analytic prime number theory can be formulated in the following general form: given a collection of (affine-)linear forms {L_1(n),\dots,L_k(n)}, none of which is a multiple of any other, find a number {n} such that a certain property {P( L_1(n),\dots,L_k(n) )} of the linear forms {L_1(n),\dots,L_k(n)} are true. For instance:

  • For the twin prime conjecture, one can use the linear forms {L_1(n) := n}, {L_2(n) := n+2}, and the property {P( L_1(n), L_2(n) )} in question is the assertion that {L_1(n)} and {L_2(n)} are both prime.
  • For the even Goldbach conjecture, the claim is similar but one uses the linear forms {L_1(n) := n}, {L_2(n) := N-n} for some even integer {N}.
  • For Chen’s theorem, we use the same linear forms {L_1(n),L_2(n)} as in the previous two cases, but now {P(L_1(n), L_2(n))} is the assertion that {L_1(n)} is prime and {L_2(n)} is an almost prime (in the sense that there are at most two prime factors).
  • In the recent results establishing bounded gaps between primes, we use the linear forms {L_i(n) = n + h_i} for some admissible tuple {h_1,\dots,h_k}, and take {P(L_1(n),\dots,L_k(n))} to be the assertion that at least two of {L_1(n),\dots,L_k(n)} are prime.

For these sorts of results, one can try a sieve-theoretic approach, which can broadly be formulated as follows:

  1. First, one chooses a carefully selected sieve weight {\nu: {\bf N} \rightarrow {\bf R}^+}, which could for instance be a non-negative function having a divisor sum form

    \displaystyle  \nu(n) := \sum_{d_1|L_1(n), \dots, d_k|L_k(n); d_1 \dots d_k \leq x^{1-\varepsilon}} \lambda_{d_1,\dots,d_k}

    for some coefficients {\lambda_{d_1,\dots,d_k}}, where {x} is a natural scale parameter. The precise choice of sieve weight is often quite a delicate matter, but will not be discussed here. (In some cases, one may work with multiple sieve weights {\nu_1, \nu_2, \dots}.)

  2. Next, one uses tools from analytic number theory (such as the Bombieri-Vinogradov theorem) to obtain upper and lower bounds for sums such as

    \displaystyle  \sum_n \nu(n) \ \ \ \ \ (1)

    or

    \displaystyle  \sum_n \nu(n) 1_{L_i(n) \hbox{ prime}} \ \ \ \ \ (2)

    or more generally of the form

    \displaystyle  \sum_n \nu(n) f(L_i(n)) \ \ \ \ \ (3)

    where {f(L_i(n))} is some “arithmetic” function involving the prime factorisation of {L_i(n)} (we will be a bit vague about what this means precisely, but a typical choice of {f} might be a Dirichlet convolution {\alpha*\beta(L_i(n))} of two other arithmetic functions {\alpha,\beta}).

  3. Using some combinatorial arguments, one manipulates these upper and lower bounds, together with the non-negative nature of {\nu}, to conclude the existence of an {n} in the support of {\nu} (or of at least one of the sieve weights {\nu_1, \nu_2, \dots} being considered) for which {P( L_1(n), \dots, L_k(n) )} holds

For instance, in the recent results on bounded gaps between primes, one selects a sieve weight {\nu} for which one has upper bounds on

\displaystyle  \sum_n \nu(n)

and lower bounds on

\displaystyle  \sum_n \nu(n) 1_{n+h_i \hbox{ prime}}

so that one can show that the expression

\displaystyle  \sum_n \nu(n) (\sum_{i=1}^k 1_{n+h_i \hbox{ prime}} - 1)

is strictly positive, which implies the existence of an {n} in the support of {\nu} such that at least two of {n+h_1,\dots,n+h_k} are prime. As another example, to prove Chen’s theorem to find {n} such that {L_1(n)} is prime and {L_2(n)} is almost prime, one uses a variety of sieve weights to produce a lower bound for

\displaystyle  S_1 := \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{L_2(n) \hbox{ rough}}

and an upper bound for

\displaystyle  S_2 := \sum_{z \leq p < x^{1/3}} \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{p|L_2(n)} 1_{L_2(n) \hbox{ rough}}

and

\displaystyle  S_3 := \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{L_2(n)=pqr \hbox{ for some } z \leq p \leq x^{1/3} < q \leq r},

where {z} is some parameter between {1} and {x^{1/3}}, and “rough” means that all prime factors are at least {z}. One can observe that if {S_1 - \frac{1}{2} S_2 - \frac{1}{2} S_3 > 0}, then there must be at least one {n} for which {L_1(n)} is prime and {L_2(n)} is almost prime, since for any rough number {m}, the quantity

\displaystyle  1 - \frac{1}{2} \sum_{z \leq p < x^{1/3}} 1_{p|m} - \frac{1}{2} \sum_{z \leq p \leq x^{1/3} < q \leq r} 1_{m = pqr}

is only positive when {m} is an almost prime (if {m} has three or more factors, then either it has at least two factors less than {x^{1/3}}, or it is of the form {pqr} for some {p \leq x^{1/3} < q \leq r}). The upper and lower bounds on {S_1,S_2,S_3} are ultimately produced via asymptotics for expressions of the form (1), (2), (3) for various divisor sums {\nu} and various arithmetic functions {f}.

Unfortunately, there is an obstruction to sieve-theoretic techniques working for certain types of properties {P(L_1(n),\dots,L_k(n))}, which Zeb Brady and I recently formalised at an AIM workshop this week. To state the result, we recall the Liouville function {\lambda(n)}, defined by setting {\lambda(n) = (-1)^j} whenever {n} is the product of exactly {j} primes (counting multiplicity). Define a sign pattern to be an element {(\epsilon_1,\dots,\epsilon_k)} of the discrete cube {\{-1,+1\}^k}. Given a property {P(l_1,\dots,l_k)} of {k} natural numbers {l_1,\dots,l_k}, we say that a sign pattern {(\epsilon_1,\dots,\epsilon_k)} is forbidden by {P} if there does not exist any natural numbers {l_1,\dots,l_k} obeying {P(l_1,\dots,l_k)} for which

\displaystyle  (\lambda(l_1),\dots,\lambda(l_k)) = (\epsilon_1,\dots,\epsilon_k).

Example 1 Let {P(l_1,l_2,l_3)} be the property that at least two of {l_1,l_2,l_3} are prime. Then the sign patterns {(+1,+1,+1)}, {(+1,+1,-1)}, {(+1,-1,+1)}, {(-1,+1,+1)} are forbidden, because prime numbers have a Liouville function of {-1}, so that {P(l_1,l_2,l_3)} can only occur when at least two of {\lambda(l_1),\lambda(l_2), \lambda(l_3)} are equal to {-1}.

Example 2 Let {P(l_1,l_2)} be the property that {l_1} is prime and {l_2} is almost prime. Then the only forbidden sign patterns are {(+1,+1)} and {(+1,-1)}.

Example 3 Let {P(l_1,l_2)} be the property that {l_1} and {l_2} are both prime. Then {(+1,+1), (+1,-1), (-1,+1)} are all forbidden sign patterns.

We then have a parity obstruction as soon as {P} has “too many” forbidden sign patterns, in the following (slightly informal) sense:

Claim 1 (Parity obstruction) Suppose {P(l_1,\dots,l_k)} is such that that the convex hull of the forbidden sign patterns of {P} contains the origin. Then one cannot use the above sieve-theoretic approach to establish the existence of an {n} such that {P(L_1(n),\dots,L_k(n))} holds.

Thus for instance, the property in Example 3 is subject to the parity obstruction since {0} is a convex combination of {(+1,-1)} and {(-1,+1)}, whereas the properties in Examples 1, 2 are not. One can also check that the property “at least {j} of the {k} numbers {l_1,\dots,l_k} is prime” is subject to the parity obstruction as soon as {j \geq \frac{k}{2}+1}. Thus, the largest number of elements of a {k}-tuple that one can force to be prime by purely sieve-theoretic methods is {k/2}, rounded up.

This claim is not precisely a theorem, because it presumes a certain “Liouville pseudorandomness conjecture” (a very close cousin of the more well known “Möbius pseudorandomness conjecture”) which is a bit difficult to formalise precisely. However, this conjecture is widely believed by analytic number theorists, see e.g. this blog post for a discussion. (Note though that there are scenarios, most notably the “Siegel zero” scenario, in which there is a severe breakdown of this pseudorandomness conjecture, and the parity obstruction then disappears. A typical instance of this is Heath-Brown’s proof of the twin prime conjecture (which would ordinarily be subject to the parity obstruction) under the hypothesis of a Siegel zero.) The obstruction also does not prevent the establishment of an {n} such that {P(L_1(n),\dots,L_k(n))} holds by introducing additional sieve axioms beyond upper and lower bounds on quantities such as (1), (2), (3). The proof of the Friedlander-Iwaniec theorem is a good example of this latter scenario.

Now we give a (slightly nonrigorous) proof of the claim.

Proof: (Nonrigorous) Suppose that the convex hull of the forbidden sign patterns contain the origin. Then we can find non-negative numbers {p_{\epsilon_1,\dots,\epsilon_k}} for sign patterns {(\epsilon_1,\dots,\epsilon_k)}, which sum to {1}, are non-zero only for forbidden sign patterns, and which have mean zero in the sense that

\displaystyle  \sum_{(\epsilon_1,\dots,\epsilon_k)} p_{\epsilon_1,\dots,\epsilon_k} \epsilon_i = 0

for all {i=1,\dots,k}. By Fourier expansion (or Lagrange interpolation), one can then write {p_{\epsilon_1,\dots,\epsilon_k}} as a polynomial

\displaystyle  p_{\epsilon_1,\dots,\epsilon_k} = 1 + Q( \epsilon_1,\dots,\epsilon_k)

where {Q(t_1,\dots,t_k)} is a polynomial in {k} variables that is a linear combination of monomials {t_{i_1} \dots t_{i_r}} with {i_1 < \dots < i_r} and {r \geq 2} (thus {Q} has no constant or linear terms, and no monomials with repeated terms). The point is that the mean zero condition allows one to eliminate the linear terms. If we now consider the weight function

\displaystyle  w(n) := 1 + Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )

then {w} is non-negative, is supported solely on {n} for which {(\lambda(L_1(n)),\dots,\lambda(L_k(n)))} is a forbidden pattern, and is equal to {1} plus a linear combination of monomials {\lambda(L_{i_1}(n)) \dots \lambda(L_{i_r}(n))} with {r \geq 2}.

The Liouville pseudorandomness principle then predicts that sums of the form

\displaystyle  \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )

and

\displaystyle  \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) ) 1_{L_i(n) \hbox{ prime}}

or more generally

\displaystyle  \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) ) f(L_i(n))

should be asymptotically negligible; intuitively, the point here is that the prime factorisation of {L_i(n)} should not influence the Liouville function of {L_j(n)}, even on the short arithmetic progressions that the divisor sum {\nu} is built out of, and so any monomial {\lambda(L_{i_1}(n)) \dots \lambda(L_{i_r}(n))} occurring in {Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )} should exhibit strong cancellation for any of the above sums. If one accepts this principle, then all the expressions (1), (2), (3) should be essentially unchanged when {\nu(n)} is replaced by {\nu(n) w(n)}.

Suppose now for sake of contradiction that one could use sieve-theoretic methods to locate an {n} in the support of some sieve weight {\nu(n)} obeying {P( L_1(n),\dots,L_k(n))}. Then, by reweighting all sieve weights by the additional multiplicative factor of {w(n)}, the same arguments should also be able to locate {n} in the support of {\nu(n) w(n)} for which {P( L_1(n),\dots,L_k(n))} holds. But {w} is only supported on those {n} whose Liouville sign pattern is forbidden, a contradiction. \Box

Claim 1 is sharp in the following sense: if the convex hull of the forbidden sign patterns of {P} do not contain the origin, then by the Hahn-Banach theorem (in the hyperplane separation form), there exist real coefficients {c_1,\dots,c_k} such that

\displaystyle  c_1 \epsilon_1 + \dots + c_k \epsilon_k < -c

for all forbidden sign patterns {(\epsilon_1,\dots,\epsilon_k)} and some {c>0}. On the other hand, from Liouville pseudorandomness one expects that

\displaystyle  \sum_n \nu(n) (c_1 \lambda(L_1(n)) + \dots + c_k \lambda(L_k(n)))

is negligible (as compared against {\sum_n \nu(n)} for any reasonable sieve weight {\nu}. We conclude that for some {n} in the support of {\nu}, that

\displaystyle  c_1 \lambda(L_1(n)) + \dots + c_k \lambda(L_k(n)) > -c \ \ \ \ \ (4)

and hence {(\lambda(L_1(n)),\dots,\lambda(L_k(n)))} is not a forbidden sign pattern. This does not actually imply that {P(L_1(n),\dots,L_k(n))} holds, but it does not prevent {P(L_1(n),\dots,L_k(n))} from holding purely from parity considerations. Thus, we do not expect a parity obstruction of the type in Claim 1 to hold when the convex hull of forbidden sign patterns does not contain the origin.

Example 4 Let {G} be a graph on {k} vertices {\{1,\dots,k\}}, and let {P(l_1,\dots,l_k)} be the property that one can find an edge {\{i,j\}} of {G} with {l_i,l_j} both prime. We claim that this property is subject to the parity problem precisely when {G} is two-colourable. Indeed, if {G} is two-colourable, then we can colour {\{1,\dots,k\}} into two colours (say, red and green) such that all edges in {G} connect a red vertex to a green vertex. If we then consider the two sign patterns in which all the red vertices have one sign and the green vertices have the opposite sign, these are two forbidden sign patterns which contain the origin in the convex hull, and so the parity problem applies. Conversely, suppose that {G} is not two-colourable, then it contains an odd cycle. Any forbidden sign pattern then must contain more {+1}s on this odd cycle than {-1}s (since otherwise two of the {-1}s are adjacent on this cycle by the pigeonhole principle, and this is not forbidden), and so by convexity any tuple in the convex hull of this sign pattern has a positive sum on this odd cycle. Hence the origin is not in the convex hull, and the parity obstruction does not apply. (See also this previous post for a similar obstruction ultimately coming from two-colourability).

Example 5 An example of a parity-obstructed property (supplied by Zeb Brady) that does not come from two-colourability: we let {P( l_{\{1,2\}}, l_{\{1,3\}}, l_{\{1,4\}}, l_{\{2,3\}}, l_{\{2,4\}}, l_{\{3,4\}} )} be the property that {l_{A_1},\dots,l_{A_r}} are prime for some collection {A_1,\dots,A_r} of pair sets that cover {\{1,\dots,4\}}. For instance, this property holds if {l_{\{1,2\}}, l_{\{3,4\}}} are both prime, or if {l_{\{1,2\}}, l_{\{1,3\}}, l_{\{1,4\}}} are all prime, but not if {l_{\{1,2\}}, l_{\{1,3\}}, l_{\{2,3\}}} are the only primes. An example of a forbidden sign pattern is the pattern where {\{1,2\}, \{2,3\}, \{1,3\}} are given the sign {-1}, and the other three pairs are given {+1}. Averaging over permutations of {1,2,3,4} we see that zero lies in the convex hull, and so this example is blocked by parity. However, there is no sign pattern such that it and its negation are both forbidden, which is another formulation of two-colourability.

Of course, the absence of a parity obstruction does not automatically mean that the desired claim is true. For instance, given an admissible {5}-tuple {h_1,\dots,h_5}, parity obstructions do not prevent one from establishing the existence of infinitely many {n} such that at least three of {n+h_1,\dots,n+h_5} are prime, however we are not yet able to actually establish this, even assuming strong sieve-theoretic hypotheses such as the generalised Elliott-Halberstam hypothesis. (However, the argument giving (4) does easily give the far weaker claim that there exist infinitely many {n} such that at least three of {n+h_1,\dots,n+h_5} have a Liouville function of {-1}.)

Remark 1 Another way to get past the parity problem in some cases is to take advantage of linear forms that are constant multiples of each other (which correlates the Liouville functions to each other). For instance, on GEH we can find two {E_3} numbers (products of exactly three primes) that differ by exactly {60}; a direct sieve approach using the linear forms {n,n+60} fails due to the parity obstruction, but instead one can first find {n} such that two of {n,n+4,n+10} are prime, and then among the pairs of linear forms {(15n,15n+60)}, {(6n,6n+60)}, {(10n+40,10n+100)} one can find a pair of {E_3} numbers that differ by exactly {60}. See this paper of Goldston, Graham, Pintz, and Yildirim for more examples of this type.

I thank John Friedlander and Sid Graham for helpful discussions and encouragement.

The wave equation is usually expressed in the form

\displaystyle  \partial_{tt} u - \Delta u = 0

where {u \colon {\bf R} \times {\bf R}^d \rightarrow {\bf C}} is a function of both time {t \in {\bf R}} and space {x \in {\bf R}^d}, with {\Delta} being the Laplacian operator. One can generalise this equation in a number of ways, for instance by replacing the spatial domain {{\bf R}^d} with some other manifold and replacing the Laplacian {\Delta} with the Laplace-Beltrami operator or adding lower order terms (such as a potential, or a coupling with a magnetic field). But for sake of discussion let us work with the classical wave equation on {{\bf R}^d}. We will work formally in this post, being unconcerned with issues of convergence, justifying interchange of integrals, derivatives, or limits, etc.. One then has a conserved energy

\displaystyle  \int_{{\bf R}^d} \frac{1}{2} |\nabla u(t,x)|^2 + \frac{1}{2} |\partial_t u(t,x)|^2\ dx

which we can rewrite using integration by parts and the {L^2} inner product {\langle, \rangle} on {{\bf R}^d} as

\displaystyle  \frac{1}{2} \langle -\Delta u(t), u(t) \rangle + \frac{1}{2} \langle \partial_t u(t), \partial_t u(t) \rangle.

A key feature of the wave equation is finite speed of propagation: if, at time {t=0} (say), the initial position {u(0)} and initial velocity {\partial_t u(0)} are both supported in a ball {B(x_0,R) := \{ x \in {\bf R}^d: |x-x_0| \leq R \}}, then at any later time {t>0}, the position {u(t)} and velocity {\partial_t u(t)} are supported in the larger ball {B(x_0,R+t)}. This can be seen for instance (formally, at least) by inspecting the exterior energy

\displaystyle  \int_{|x-x_0| > R+t} \frac{1}{2} |\nabla u(t,x)|^2 + \frac{1}{2} |\partial_t u(t,x)|^2\ dx

and observing (after some integration by parts and differentiation under the integral sign) that it is non-increasing in time, non-negative, and vanishing at time {t=0}.

The wave equation is second order in time, but one can turn it into a first order system by working with the pair {(u(t),v(t))} rather than just the single field {u(t)}, where {v(t) := \partial_t u(t)} is the velocity field. The system is then

\displaystyle  \partial_t u(t) = v(t)

\displaystyle  \partial_t v(t) = \Delta u(t)

and the conserved energy is now

\displaystyle  \frac{1}{2} \langle -\Delta u(t), u(t) \rangle + \frac{1}{2} \langle v(t), v(t) \rangle. \ \ \ \ \ (1)

Finite speed of propagation then tells us that if {u(0),v(0)} are both supported on {B(x_0,R)}, then {u(t),v(t)} are supported on {B(x_0,R+t)} for all {t>0}. One also has time reversal symmetry: if {t \mapsto (u(t),v(t))} is a solution, then {t \mapsto (u(-t), -v(-t))} is a solution also, thus for instance one can establish an analogue of finite speed of propagation for negative times {t<0} using this symmetry.

If one has an eigenfunction

\displaystyle  -\Delta \phi = \lambda^2 \phi

of the Laplacian, then we have the explicit solutions

\displaystyle  u(t) = e^{\pm it \lambda} \phi

\displaystyle  v(t) = \pm i \lambda e^{\pm it \lambda} \phi

of the wave equation, which formally can be used to construct all other solutions via the principle of superposition.

When one has vanishing initial velocity {v(0)=0}, the solution {u(t)} is given via functional calculus by

\displaystyle  u(t) = \cos(t \sqrt{-\Delta}) u(0)

and the propagator {\cos(t \sqrt{-\Delta})} can be expressed as the average of half-wave operators:

\displaystyle  \cos(t \sqrt{-\Delta}) = \frac{1}{2} ( e^{it\sqrt{-\Delta}} + e^{-it\sqrt{-\Delta}} ).

One can view {\cos(t \sqrt{-\Delta} )} as a minor of the full wave propagator

\displaystyle  U(t) := \exp \begin{pmatrix} 0 & t \\ t\Delta & 0 \end{pmatrix}

\displaystyle  = \begin{pmatrix} \cos(t \sqrt{-\Delta}) & \frac{\sin(t\sqrt{-\Delta})}{\sqrt{-\Delta}} \\ \sin(t\sqrt{-\Delta}) \sqrt{-\Delta} & \cos(t \sqrt{-\Delta} ) \end{pmatrix}

which is unitary with respect to the energy form (1), and is the fundamental solution to the wave equation in the sense that

\displaystyle  \begin{pmatrix} u(t) \\ v(t) \end{pmatrix} = U(t) \begin{pmatrix} u(0) \\ v(0) \end{pmatrix}. \ \ \ \ \ (2)

Viewing the contraction {\cos(t\sqrt{-\Delta})} as a minor of a unitary operator is an instance of the “dilation trick“.

It turns out (as I learned from Yuval Peres) that there is a useful discrete analogue of the wave equation (and of all of the above facts), in which the time variable {t} now lives on the integers {{\bf Z}} rather than on {{\bf R}}, and the spatial domain can be replaced by discrete domains also (such as graphs). Formally, the system is now of the form

\displaystyle  u(t+1) = P u(t) + v(t) \ \ \ \ \ (3)

\displaystyle  v(t+1) = P v(t) - (1-P^2) u(t)

where {t} is now an integer, {u(t), v(t)} take values in some Hilbert space (e.g. {\ell^2} functions on a graph {G}), and {P} is some operator on that Hilbert space (which in applications will usually be a self-adjoint contraction). To connect this with the classical wave equation, let us first consider a rescaling of this system

\displaystyle  u(t+\varepsilon) = P_\varepsilon u(t) + \varepsilon v(t)

\displaystyle  v(t+\varepsilon) = P_\varepsilon v(t) - \frac{1}{\varepsilon} (1-P_\varepsilon^2) u(t)

where {\varepsilon>0} is a small parameter (representing the discretised time step), {t} now takes values in the integer multiples {\varepsilon {\bf Z}} of {\varepsilon}, and {P_\varepsilon} is the wave propagator operator {P_\varepsilon := \cos( \varepsilon \sqrt{-\Delta} )} or the heat propagator {P_\varepsilon := \exp( - \varepsilon^2 \Delta/2 )} (the two operators are different, but agree to fourth order in {\varepsilon}). One can then formally verify that the wave equation emerges from this rescaled system in the limit {\varepsilon \rightarrow 0}. (Thus, {P} is not exactly the direct analogue of the Laplacian {\Delta}, but can be viewed as something like {P_\varepsilon = 1 - \frac{\varepsilon^2}{2} \Delta + O( \varepsilon^4 )} in the case of small {\varepsilon}, or {P = 1 - \frac{1}{2}\Delta + O(\Delta^2)} if we are not rescaling to the small {\varepsilon} case. The operator {P} is sometimes known as the diffusion operator)

Assuming {P} is self-adjoint, solutions to the system (3) formally conserve the energy

\displaystyle  \frac{1}{2} \langle (1-P^2) u(t), u(t) \rangle + \frac{1}{2} \langle v(t), v(t) \rangle. \ \ \ \ \ (4)

This energy is positive semi-definite if {P} is a contraction. We have the same time reversal symmetry as before: if {t \mapsto (u(t),v(t))} solves the system (3), then so does {t \mapsto (u(-t), -v(-t))}. If one has an eigenfunction

\displaystyle  P \phi = \cos(\lambda) \phi

to the operator {P}, then one has an explicit solution

\displaystyle  u(t) = e^{\pm it \lambda} \phi

\displaystyle  v(t) = \pm i \sin(\lambda) e^{\pm it \lambda} \phi

to (3), and (in principle at least) this generates all other solutions via the principle of superposition.

Finite speed of propagation is a lot easier in the discrete setting, though one has to offset the support of the “velocity” field {v} by one unit. Suppose we know that {P} has unit speed in the sense that whenever {f} is supported in a ball {B(x,R)}, then {Pf} is supported in the ball {B(x,R+1)}. Then an easy induction shows that if {u(0), v(0)} are supported in {B(x_0,R), B(x_0,R+1)} respectively, then {u(t), v(t)} are supported in {B(x_0,R+t), B(x_0, R+t+1)}.

The fundamental solution {U(t) = U^t} to the discretised wave equation (3), in the sense of (2), is given by the formula

\displaystyle  U(t) = U^t = \begin{pmatrix} P & 1 \\ P^2-1 & P \end{pmatrix}^t

\displaystyle  = \begin{pmatrix} T_t(P) & U_{t-1}(P) \\ (P^2-1) U_{t-1}(P) & T_t(P) \end{pmatrix}

where {T_t} and {U_t} are the Chebyshev polynomials of the first and second kind, thus

\displaystyle  T_t( \cos \theta ) = \cos(t\theta)

and

\displaystyle  U_t( \cos \theta ) = \frac{\sin((t+1)\theta)}{\sin \theta}.

In particular, {P} is now a minor of {U(1) = U}, and can also be viewed as an average of {U} with its inverse {U^{-1}}:

\displaystyle  \begin{pmatrix} P & 0 \\ 0 & P \end{pmatrix} = \frac{1}{2} (U + U^{-1}). \ \ \ \ \ (5)

As before, {U} is unitary with respect to the energy form (4), so this is another instance of the dilation trick in action. The powers {P^n} and {U^n} are discrete analogues of the heat propagators {e^{t\Delta/2}} and wave propagators {U(t)} respectively.

One nice application of all this formalism, which I learned from Yuval Peres, is the Varopoulos-Carne inequality:

Theorem 1 (Varopoulos-Carne inequality) Let {G} be a (possibly infinite) regular graph, let {n \geq 1}, and let {x, y} be vertices in {G}. Then the probability that the simple random walk at {x} lands at {y} at time {n} is at most {2 \exp( - d(x,y)^2 / 2n )}, where {d} is the graph distance.

This general inequality is quite sharp, as one can see using the standard Cayley graph on the integers {{\bf Z}}. Very roughly speaking, it asserts that on a regular graph of reasonably controlled growth (e.g. polynomial growth), random walks of length {n} concentrate on the ball of radius {O(\sqrt{n})} or so centred at the origin of the random walk.

Proof: Let {P \colon \ell^2(G) \rightarrow \ell^2(G)} be the graph Laplacian, thus

\displaystyle  Pf(x) = \frac{1}{D} \sum_{y \sim x} f(y)

for any {f \in \ell^2(G)}, where {D} is the degree of the regular graph and sum is over the {D} vertices {y} that are adjacent to {x}. This is a contraction of unit speed, and the probability that the random walk at {x} lands at {y} at time {n} is

\displaystyle  \langle P^n \delta_x, \delta_y \rangle

where {\delta_x, \delta_y} are the Dirac deltas at {x,y}. Using (5), we can rewrite this as

\displaystyle  \langle (\frac{1}{2} (U + U^{-1}))^n \begin{pmatrix} 0 \\ \delta_x\end{pmatrix}, \begin{pmatrix} 0 \\ \delta_y\end{pmatrix} \rangle

where we are now using the energy form (4). We can write

\displaystyle  (\frac{1}{2} (U + U^{-1}))^n = {\bf E} U^{S_n}

where {S_n} is the simple random walk of length {n} on the integers, that is to say {S_n = \xi_1 + \dots + \xi_n} where {\xi_1,\dots,\xi_n = \pm 1} are independent uniform Bernoulli signs. Thus we wish to show that

\displaystyle  {\bf E} \langle U^{S_n} \begin{pmatrix} 0 \\ \delta_x\end{pmatrix}, \begin{pmatrix} 0 \\ \delta_y\end{pmatrix} \rangle \leq 2 \exp(-d(x,y)^2 / 2n ).

By finite speed of propagation, the inner product here vanishes if {|S_n| < d(x,y)}. For {|S_n| \geq d(x,y)} we can use Cauchy-Schwarz and the unitary nature of {U} to bound the inner product by {1}. Thus the left-hand side may be upper bounded by

\displaystyle  {\bf P}( |S_n| \geq d(x,y) )

and the claim now follows from the Chernoff inequality. \Box

This inequality has many applications, particularly with regards to relating the entropy, mixing time, and concentration of random walks with volume growth of balls; see this text of Lyons and Peres for some examples.

For sake of comparison, here is a continuous counterpart to the Varopoulos-Carne inequality:

Theorem 2 (Continuous Varopoulos-Carne inequality) Let {t > 0}, and let {f,g \in L^2({\bf R}^d)} be supported on compact sets {F,G} respectively. Then

\displaystyle  |\langle e^{t\Delta/2} f, g \rangle| \leq \sqrt{\frac{2t}{\pi d(F,G)^2}} \exp( - d(F,G)^2 / 2t ) \|f\|_{L^2} \|g\|_{L^2}

where {d(F,G)} is the Euclidean distance between {F} and {G}.

Proof: By Fourier inversion one has

\displaystyle  e^{-t\xi^2/2} = \frac{1}{\sqrt{2\pi t}} \int_{\bf R} e^{-s^2/2t} e^{is\xi}\ ds

\displaystyle  = \sqrt{\frac{2}{\pi t}} \int_0^\infty e^{-s^2/2t} \cos(s \xi )\ ds

for any real {\xi}, and thus

\displaystyle  \langle e^{t\Delta/2} f, g\rangle = \sqrt{\frac{2}{\pi}} \int_0^\infty e^{-s^2/2t} \langle \cos(s \sqrt{-\Delta} ) f, g \rangle\ ds.

By finite speed of propagation, the inner product {\langle \cos(s \sqrt{-\Delta} ) f, g \rangle\ ds} vanishes when {s < d(F,G)}; otherwise, we can use Cauchy-Schwarz and the contractive nature of {\cos(s \sqrt{-\Delta} )} to bound this inner product by {\|f\|_{L^2} \|g\|_{L^2}}. Thus

\displaystyle  |\langle e^{t\Delta/2} f, g\rangle| \leq \sqrt{\frac{2}{\pi t}} \|f\|_{L^2} \|g\|_{L^2} \int_{d(F,G)}^\infty e^{-s^2/2t}\ ds.

Bounding {e^{-s^2/2t}} by {e^{-d(F,G)^2/2t} e^{-d(F,G) (s-d(F,G))/t}}, we obtain the claim. \Box

Observe that the argument is quite general and can be applied for instance to other Riemannian manifolds than {{\bf R}^d}.

The prime number theorem can be expressed as the assertion

\displaystyle  \sum_{n \leq x} \Lambda(n) = x + o(x) \ \ \ \ \ (1)

as {x \rightarrow \infty}, where

\displaystyle  \Lambda(n) := \sum_{d|n} \mu(d) \log \frac{n}{d}

is the von Mangoldt function. It is a basic result in analytic number theory, but requires a bit of effort to prove. One “elementary” proof of this theorem proceeds through the Selberg symmetry formula

\displaystyle  \sum_{n \leq x} \Lambda_2(n) = 2 x \log x + O(x) \ \ \ \ \ (2)

where the second von Mangoldt function {\Lambda_2} is defined by the formula

\displaystyle  \Lambda_2(n) := \sum_{d|n} \mu(d) \log^2 \frac{n}{d} \ \ \ \ \ (3)

or equivalently

\displaystyle  \Lambda_2(n) = \Lambda(n) \log n + \sum_{d|n} \Lambda(d) \Lambda(\frac{n}{d}). \ \ \ \ \ (4)

(We are avoiding the use of the {*} symbol here to denote Dirichlet convolution, as we will need this symbol to denote ordinary convolution shortly.) For the convenience of the reader, we give a proof of the Selberg symmetry formula below the fold. Actually, for the purposes of proving the prime number theorem, the weaker estimate

\displaystyle  \sum_{n \leq x} \Lambda_2(n) = 2 x \log x + o(x \log x) \ \ \ \ \ (5)

suffices.

In this post I would like to record a somewhat “soft analysis” reformulation of the elementary proof of the prime number theorem in terms of Banach algebras, and specifically in Banach algebra structures on (completions of) the space {C_c({\bf R})} of compactly supported continuous functions {f: {\bf R} \rightarrow {\bf C}} equipped with the convolution operation

\displaystyle  f*g(t) := \int_{\bf R} f(u) g(t-u)\ du.

This soft argument does not easily give any quantitative decay rate in the prime number theorem, but by the same token it avoids many of the quantitative calculations in the traditional proofs of this theorem. Ultimately, the key “soft analysis” fact used is the spectral radius formula

\displaystyle  \lim_{n \rightarrow \infty} \|f^n\|^{1/n} = \sup_{\lambda \in \hat B} |\lambda(f)| \ \ \ \ \ (6)

for any element {f} of a unital commutative Banach algebra {B}, where {\hat B} is the space of characters (i.e., continuous unital algebra homomorphisms from {B} to {{\bf C}}) of {B}. This formula is due to Gelfand and may be found in any text on Banach algebras; for sake of completeness we prove it below the fold.

The connection between prime numbers and Banach algebras is given by the following consequence of the Selberg symmetry formula.

Theorem 1 (Construction of a Banach algebra norm) For any {G \in C_c({\bf R})}, let {\|G\|} denote the quantity

\displaystyle  \|G\| := \limsup_{x \rightarrow \infty} |\sum_n \frac{\Lambda(n)}{n} G( \log \frac{x}{n} ) - \int_{\bf R} G(t)\ dt|.

Then {\| \|} is a seminorm on {C_c({\bf R})} with the bound

\displaystyle  \|G\| \leq \|G\|_{L^1({\bf R})} := \int_{\bf R} |G(t)|\ dt \ \ \ \ \ (7)

for all {G \in C_c({\bf R})}. Furthermore, we have the Banach algebra bound

\displaystyle  \| G * H \| \leq \|G\| \|H\| \ \ \ \ \ (8)

for all {G,H \in C_c({\bf R})}.

We prove this theorem below the fold. The prime number theorem then follows from Theorem 1 and the following two assertions. The first is an application of the spectral radius formula (6) and some basic Fourier analysis (in particular, the observation that {C_c({\bf R})} contains a plentiful supply of local units:

Theorem 2 (Non-trivial Banach algebras with many local units have non-trivial spectrum) Let {\| \|} be a seminorm on {C_c({\bf R})} obeying (7), (8). Suppose that {\| \|} is not identically zero. Then there exists {\xi \in {\bf R}} such that

\displaystyle  |\int_{\bf R} G(t) e^{-it\xi}\ dt| \leq \|G\|

for all {G \in C_c}. In particular, by (7), one has

\displaystyle  \|G\| = \| G \|_{L^1({\bf R})}

whenever {G(t) e^{-it\xi}} is a non-negative function.

The second is a consequence of the Selberg symmetry formula and the fact that {\Lambda} is real (as well as Mertens’ theorem, in the {\xi=0} case), and is closely related to the non-vanishing of the Riemann zeta function {\zeta} on the line {\{ 1+i\xi: \xi \in {\bf R}\}}:

Theorem 3 (Breaking the parity barrier) Let {\xi \in {\bf R}}. Then there exists {G \in C_c({\bf R})} such that {G(t) e^{-it\xi}} is non-negative, and

\displaystyle  \|G\| < \|G\|_{L^1({\bf R})}.

Assuming Theorems 1, 2, 3, we may now quickly establish the prime number theorem as follows. Theorem 2 and Theorem 3 imply that the seminorm {\| \|} constructed in Theorem 1 is trivial, and thus

\displaystyle  \sum_n \frac{\Lambda(n)}{n} G( \log \frac{x}{n} ) = \int_{\bf R} G(t)\ dt + o(1)

as {x \rightarrow \infty} for any Schwartz function {G} (the decay rate in {o(1)} may depend on {G}). Specialising to functions of the form {G(t) = e^{-t} \eta( e^{-t} )} for some smooth compactly supported {\eta} on {(0,+\infty)}, we conclude that

\displaystyle  \sum_n \Lambda(n) \eta(\frac{n}{x}) = \int_{\bf R} \eta(u)\ du + o(x)

as {x \rightarrow \infty}; by the smooth Urysohn lemma this implies that

\displaystyle  \sum_{\varepsilon x \leq n \leq x} \Lambda(n) = x - \varepsilon x + o(x)

as {x \rightarrow \infty} for any fixed {\varepsilon>0}, and the prime number theorem then follows by a telescoping series argument.

The same argument also yields the prime number theorem in arithmetic progressions, or equivalently that

\displaystyle  \sum_{n \leq x} \Lambda(n) \chi(n) = o(x)

for any fixed Dirichlet character {\chi}; the one difference is that the use of Mertens’ theorem is replaced by the basic fact that the quantity {L(1,\chi) = \sum_n \frac{\chi(n)}{n}} is non-vanishing.

Read the rest of this entry »

In graph theory, the recently developed theory of graph limits has proven to be a useful tool for analysing large dense graphs, being a convenient reformulation of the Szemerédi regularity lemma. Roughly speaking, the theory asserts that given any sequence {G_n = (V_n, E_n)} of finite graphs, one can extract a subsequence {G_{n_j} = (V_{n_j}, E_{n_j})} which converges (in a specific sense) to a continuous object known as a “graphon” – a symmetric measurable function {p\colon [0,1] \times [0,1] \rightarrow [0,1]}. What “converges” means in this context is that subgraph densities converge to the associated integrals of the graphon {p}. For instance, the edge density

\displaystyle  \frac{1}{|V_{n_j}|^2} |E_{n_j}|

converge to the integral

\displaystyle  \int_0^1 \int_0^1 p(x,y)\ dx dy,

the triangle density

\displaystyle  \frac{1}{|V_{n_j}|^3} \lvert \{ (v_1,v_2,v_3) \in V_{n_j}^3: \{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_1\} \in E_{n_j} \} \rvert

converges to the integral

\displaystyle  \int_0^1 \int_0^1 \int_0^1 p(x_1,x_2) p(x_2,x_3) p(x_3,x_1)\ dx_1 dx_2 dx_3,

the four-cycle density

\displaystyle  \frac{1}{|V_{n_j}|^4} \lvert \{ (v_1,v_2,v_3,v_4) \in V_{n_j}^4: \{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}, \{v_4,v_1\} \in E_{n_j} \} \rvert

converges to the integral

\displaystyle  \int_0^1 \int_0^1 \int_0^1 \int_0^1 p(x_1,x_2) p(x_2,x_3) p(x_3,x_4) p(x_4,x_1)\ dx_1 dx_2 dx_3 dx_4,

and so forth. One can use graph limits to prove many results in graph theory that were traditionally proven using the regularity lemma, such as the triangle removal lemma, and can also reduce many asymptotic graph theory problems to continuous problems involving multilinear integrals (although the latter problems are not necessarily easy to solve!). See this text of Lovasz for a detailed study of graph limits and their applications.

One can also express graph limits (and more generally hypergraph limits) in the language of nonstandard analysis (or of ultraproducts); see for instance this paper of Elek and Szegedy, Section 6 of this previous blog post, or this paper of Towsner. (In this post we assume some familiarity with nonstandard analysis, as reviewed for instance in the previous blog post.) Here, one starts as before with a sequence {G_n = (V_n,E_n)} of finite graphs, and then takes an ultraproduct (with respect to some arbitrarily chosen non-principal ultrafilter {\alpha \in\beta {\bf N} \backslash {\bf N}}) to obtain a nonstandard graph {G_\alpha = (V_\alpha,E_\alpha)}, where {V_\alpha = \prod_{n\rightarrow \alpha} V_n} is the ultraproduct of the {V_n}, and similarly for the {E_\alpha}. The set {E_\alpha} can then be viewed as a symmetric subset of {V_\alpha \times V_\alpha} which is measurable with respect to the Loeb {\sigma}-algebra {{\mathcal L}_{V_\alpha \times V_\alpha}} of the product {V_\alpha \times V_\alpha} (see this previous blog post for the construction of Loeb measure). A crucial point is that this {\sigma}-algebra is larger than the product {{\mathcal L}_{V_\alpha} \times {\mathcal L}_{V_\alpha}} of the Loeb {\sigma}-algebra of the individual vertex set {V_\alpha}. This leads to a decomposition

\displaystyle  1_{E_\alpha} = p + e

where the “graphon” {p} is the orthogonal projection of {1_{E_\alpha}} onto {L^2( {\mathcal L}_{V_\alpha} \times {\mathcal L}_{V_\alpha} )}, and the “regular error” {e} is orthogonal to all product sets {A \times B} for {A, B \in {\mathcal L}_{V_\alpha}}. The graphon {p\colon V_\alpha \times V_\alpha \rightarrow [0,1]} then captures the statistics of the nonstandard graph {G_\alpha}, in exact analogy with the more traditional graph limits: for instance, the edge density

\displaystyle  \hbox{st} \frac{1}{|V_\alpha|^2} |E_\alpha|

(or equivalently, the limit of the {\frac{1}{|V_n|^2} |E_n|} along the ultrafilter {\alpha}) is equal to the integral

\displaystyle  \int_{V_\alpha} \int_{V_\alpha} p(x,y)\ d\mu_{V_\alpha}(x) d\mu_{V_\alpha}(y)

where {d\mu_V} denotes Loeb measure on a nonstandard finite set {V}; the triangle density

\displaystyle  \hbox{st} \frac{1}{|V_\alpha|^3} \lvert \{ (v_1,v_2,v_3) \in V_\alpha^3: \{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_1\} \in E_\alpha \} \rvert

(or equivalently, the limit along {\alpha} of the triangle densities of {E_n}) is equal to the integral

\displaystyle  \int_{V_\alpha} \int_{V_\alpha} \int_{V_\alpha} p(x_1,x_2) p(x_2,x_3) p(x_3,x_1)\ d\mu_{V_\alpha}(x_1) d\mu_{V_\alpha}(x_2) d\mu_{V_\alpha}(x_3),

and so forth. Note that with this construction, the graphon {p} is living on the Cartesian square of an abstract probability space {V_\alpha}, which is likely to be inseparable; but it is possible to cut down the Loeb {\sigma}-algebra on {V_\alpha} to minimal countable {\sigma}-algebra for which {p} remains measurable (up to null sets), and then one can identify {V_\alpha} with {[0,1]}, bringing this construction of a graphon in line with the traditional notion of a graphon. (See Remark 5 of this previous blog post for more discussion of this point.)

Additive combinatorics, which studies things like the additive structure of finite subsets {A} of an abelian group {G = (G,+)}, has many analogies and connections with asymptotic graph theory; in particular, there is the arithmetic regularity lemma of Green which is analogous to the graph regularity lemma of Szemerédi. (There is also a higher order arithmetic regularity lemma analogous to hypergraph regularity lemmas, but this is not the focus of the discussion here.) Given this, it is natural to suspect that there is a theory of “additive limits” for large additive sets of bounded doubling, analogous to the theory of graph limits for large dense graphs. The purpose of this post is to record a candidate for such an additive limit. This limit can be used as a substitute for the arithmetic regularity lemma in certain results in additive combinatorics, at least if one is willing to settle for qualitative results rather than quantitative ones; I give a few examples of this below the fold.

It seems that to allow for the most flexible and powerful manifestation of this theory, it is convenient to use the nonstandard formulation (among other things, it allows for full use of the transfer principle, whereas a more traditional limit formulation would only allow for a transfer of those quantities continuous with respect to the notion of convergence). Here, the analogue of a nonstandard graph is an ultra approximate group {A_\alpha} in a nonstandard group {G_\alpha = \prod_{n \rightarrow \alpha} G_n}, defined as the ultraproduct of finite {K}-approximate groups {A_n \subset G_n} for some standard {K}. (A {K}-approximate group {A_n} is a symmetric set containing the origin such that {A_n+A_n} can be covered by {K} or fewer translates of {A_n}.) We then let {O(A_\alpha)} be the external subgroup of {G_\alpha} generated by {A_\alpha}; equivalently, {A_\alpha} is the union of {A_\alpha^m} over all standard {m}. This space has a Loeb measure {\mu_{O(A_\alpha)}}, defined by setting

\displaystyle \mu_{O(A_\alpha)}(E_\alpha) := \hbox{st} \frac{|E_\alpha|}{|A_\alpha|}

whenever {E_\alpha} is an internal subset of {A_\alpha^m} for any standard {m}, and extended to a countably additive measure; the arguments in Section 6 of this previous blog post can be easily modified to give a construction of this measure.

The Loeb measure {\mu_{O(A_\alpha)}} is a translation invariant measure on {O(A_{\alpha})}, normalised so that {A_\alpha} has Loeb measure one. As such, one should think of {O(A_\alpha)} as being analogous to a locally compact abelian group equipped with a Haar measure. It should be noted though that {O(A_\alpha)} is not actually a locally compact group with Haar measure, for two reasons:

  • There is not an obvious topology on {O(A_\alpha)} that makes it simultaneously locally compact, Hausdorff, and {\sigma}-compact. (One can get one or two out of three without difficulty, though.)
  • The addition operation {+\colon O(A_\alpha) \times O(A_\alpha) \rightarrow O(A_\alpha)} is not measurable from the product Loeb algebra {{\mathcal L}_{O(A_\alpha)} \times {\mathcal L}_{O(A_\alpha)}} to {{\mathcal L}_{O(\alpha)}}. Instead, it is measurable from the coarser Loeb algebra {{\mathcal L}_{O(A_\alpha) \times O(A_\alpha)}} to {{\mathcal L}_{O(\alpha)}} (compare with the analogous situation for nonstandard graphs).

Nevertheless, the analogy is a useful guide for the arguments that follow.

Let {L(O(A_\alpha))} denote the space of bounded Loeb measurable functions {f\colon O(A_\alpha) \rightarrow {\bf C}} (modulo almost everywhere equivalence) that are supported on {A_\alpha^m} for some standard {m}; this is a complex algebra with respect to pointwise multiplication. There is also a convolution operation {\star\colon L(O(A_\alpha)) \times L(O(A_\alpha)) \rightarrow L(O(A_\alpha))}, defined by setting

\displaystyle  \hbox{st} f \star \hbox{st} g(x) := \hbox{st} \frac{1}{|A_\alpha|} \sum_{y \in A_\alpha^m} f(y) g(x-y)

whenever {f\colon A_\alpha^m \rightarrow {}^* {\bf C}}, {g\colon A_\alpha^l \rightarrow {}^* {\bf C}} are bounded nonstandard functions (extended by zero to all of {O(A_\alpha)}), and then extending to arbitrary elements of {L(O(A_\alpha))} by density. Equivalently, {f \star g} is the pushforward of the {{\mathcal L}_{O(A_\alpha) \times O(A_\alpha)}}-measurable function {(x,y) \mapsto f(x) g(y)} under the map {(x,y) \mapsto x+y}.

The basic structural theorem is then as follows.

Theorem 1 (Kronecker factor) Let {A_\alpha} be an ultra approximate group. Then there exists a (standard) locally compact abelian group {G} of the form

\displaystyle  G = {\bf R}^d \times {\bf Z}^m \times T

for some standard {d,m} and some compact abelian group {T}, equipped with a Haar measure {\mu_G} and a measurable homomorphism {\pi\colon O(A_\alpha) \rightarrow G} (using the Loeb {\sigma}-algebra on {O(A_\alpha)} and the Baire {\sigma}-algebra on {G}), with the following properties:

  • (i) {\pi} has dense image, and {\mu_G} is the pushforward of Loeb measure {\mu_{O(A_\alpha)}} by {\pi}.
  • (ii) There exists sets {\{0\} \subset U_0 \subset K_0 \subset G} with {U_0} open and {K_0} compact, such that

    \displaystyle  \pi^{-1}(U_0) \subset 4A_\alpha \subset \pi^{-1}(K_0). \ \ \ \ \ (1)

  • (iii) Whenever {K \subset U \subset G} with {K} compact and {U} open, there exists a nonstandard finite set {B} such that

    \displaystyle  \pi^{-1}(K) \subset B \subset \pi^{-1}(U). \ \ \ \ \ (2)

  • (iv) If {f, g \in L}, then we have the convolution formula

    \displaystyle  f \star g = \pi^*( (\pi_* f) \star (\pi_* g) ) \ \ \ \ \ (3)

    where {\pi_* f,\pi_* g} are the pushforwards of {f,g} to {L^2(G, \mu_G)}, the convolution {\star} on the right-hand side is convolution using {\mu_G}, and {\pi^*} is the pullback map from {L^2(G,\mu_G)} to {L^2(O(A_\alpha), \mu_{O(A_\alpha)})}. In particular, if {\pi_* f = 0}, then {f*g=0} for all {g \in L}.

One can view the locally compact abelian group {G} as a “model “or “Kronecker factor” for the ultra approximate group {A_\alpha} (in close analogy with the Kronecker factor from ergodic theory). In the case that {A_\alpha} is a genuine nonstandard finite group rather than an ultra approximate group, the non-compact components {{\bf R}^d \times {\bf Z}^m} of the Kronecker group {G} are trivial, and this theorem was implicitly established by Szegedy. The compact group {T} is quite large, and in particular is likely to be inseparable; but as with the case of graphons, when one is only studying at most countably many functions {f}, one can cut down the size of this group to be separable (or equivalently, second countable or metrisable) if desired, so one often works with a “reduced Kronecker factor” which is a quotient of the full Kronecker factor {G}. Once one is in the separable case, the Baire sigma algebra is identical with the more familiar Borel sigma algebra.

Given any sequence of uniformly bounded functions {f_n\colon A_n^m \rightarrow {\bf C}} for some fixed {m}, we can view the function {f \in L} defined by

\displaystyle  f := \pi_* \hbox{st} \lim_{n \rightarrow \alpha} f_n \ \ \ \ \ (4)

as an “additive limit” of the {f_n}, in much the same way that graphons {p\colon V_\alpha \times V_\alpha \rightarrow [0,1]} are limits of the indicator functions {1_{E_n}\colon V_n \times V_n \rightarrow \{0,1\}}. The additive limits capture some of the statistics of the {f_n}, for instance the normalised means

\displaystyle  \frac{1}{|A_n|} \sum_{x \in A_n^m} f_n(x)

converge (along the ultrafilter {\alpha}) to the mean

\displaystyle  \int_G f(x)\ d\mu_G(x),

and for three sequences {f_n,g_n,h_n\colon A_n^m \rightarrow {\bf C}} of functions, the normalised correlation

\displaystyle  \frac{1}{|A_n|^2} \sum_{x,y \in A_n^m} f_n(x) g_n(y) h_n(x+y)

converges along {\alpha} to the correlation

\displaystyle  \int_G \int_G f(x) g(y) h(x+y)\ d\mu_G(x) d\mu_G(y),

the normalised {U^2} Gowers norm

\displaystyle  ( \frac{1}{|A_n|^3} \sum_{x,y,z,w \in A_n^m: x+w=y+z} f_n(x) \overline{f_n(y)} \overline{f_n(z)} f_n(w))^{1/4}

converges along {\alpha} to the {U^2} Gowers norm

\displaystyle  ( \int_{G \times G \times G} f(x) \overline{f(y)} \overline{f(z)} f_n(x+y-z)\ d\mu_G(x) d\mu_G(y) d\mu_G(z))^{1/4}

and so forth. We caution however that some correlations that involve evaluating more than one function at the same point will not necessarily be preserved in the additive limit; for instance the normalised {\ell^2} norm

\displaystyle  (\frac{1}{|A_n|} \sum_{x \in A_n^m} |f_n(x)|^2)^{1/2}

does not necessarily converge to the {L^2} norm

\displaystyle  (\int_G |f(x)|^2\ d\mu_G(x))^{1/2},

but can converge instead to a larger quantity, due to the presence of the orthogonal projection {\pi_*} in the definition (4) of {f}.

An important special case of an additive limit occurs when the functions {f_n\colon A_n^m \rightarrow {\bf C}} involved are indicator functions {f_n = 1_{E_n}} of some subsets {E_n} of {A_n^m}. The additive limit {f \in L} does not necessarily remain an indicator function, but instead takes values in {[0,1]} (much as a graphon {p} takes values in {[0,1]} even though the original indicators {1_{E_n}} take values in {\{0,1\}}). The convolution {f \star f\colon G \rightarrow [0,1]} is then the ultralimit of the normalised convolutions {\frac{1}{|A_n|} 1_{E_n} \star 1_{E_n}}; in particular, the measure of the support of {f \star f} provides a lower bound on the limiting normalised cardinality {\frac{1}{|A_n|} |E_n + E_n|} of a sumset. In many situations this lower bound is an equality, but this is not necessarily the case, because the sumset {2E_n = E_n + E_n} could contain a large number of elements which have very few ({o(|A_n|)}) representations as the sum of two elements of {E_n}, and in the limit these portions of the sumset fall outside of the support of {f \star f}. (One can think of the support of {f \star f} as describing the “essential” sumset of {2E_n = E_n + E_n}, discarding those elements that have only very few representations.) Similarly for higher convolutions of {f}. Thus one can use additive limits to partially control the growth {k E_n} of iterated sumsets of subsets {E_n} of approximate groups {A_n}, in the regime where {k} stays bounded and {n} goes to infinity.

Theorem 1 can be proven by Fourier-analytic means (combined with Freiman’s theorem from additive combinatorics), and we will do so below the fold. For now, we give some illustrative examples of additive limits.

Example 2 (Bohr sets) We take {A_n} to be the intervals {A_n := \{ x \in {\bf Z}: |x| \leq N_n \}}, where {N_n} is a sequence going to infinity; these are {2}-approximate groups for all {n}. Let {\theta} be an irrational real number, let {I} be an interval in {{\bf R}/{\bf Z}}, and for each natural number {n} let {B_n} be the Bohr set

\displaystyle  B_n := \{ x \in A^{(n)}: \theta x \hbox{ mod } 1 \in I \}.

In this case, the (reduced) Kronecker factor {G} can be taken to be the infinite cylinder {{\bf R} \times {\bf R}/{\bf Z}} with the usual Lebesgue measure {\mu_G}. The additive limits of {1_{A_n}} and {1_{B_n}} end up being {1_A} and {1_B}, where {A} is the finite cylinder

\displaystyle  A := \{ (x,t) \in {\bf R} \times {\bf R}/{\bf Z}: x \in [-1,1]\}

and {B} is the rectangle

\displaystyle  B := \{ (x,t) \in {\bf R} \times {\bf R}/{\bf Z}: x \in [-1,1]; t \in I \}.

Geometrically, one should think of {A_n} and {B_n} as being wrapped around the cylinder {{\bf R} \times {\bf R}/{\bf Z}} via the homomorphism {x \mapsto (\frac{x}{N_n}, \theta x \hbox{ mod } 1)}, and then one sees that {B_n} is converging in some normalised weak sense to {B}, and similarly for {A_n} and {A}. In particular, the additive limit predicts the growth rate of the iterated sumsets {kB_n} to be quadratic in {k} until {k|I|} becomes comparable to {1}, at which point the growth transitions to linear growth, in the regime where {k} is bounded and {n} is large.

If {\theta = \frac{p}{q}} were rational instead of irrational, then one would need to replace {{\bf R}/{\bf Z}} by the finite subgroup {\frac{1}{q}{\bf Z}/{\bf Z}} here.

Example 3 (Structured subsets of progressions) We take {A_n} be the rank two progression

\displaystyle  A_n := \{ a + b N_n^2: a,b \in {\bf Z}; |a|, |b| \leq N_n \},

where {N_n} is a sequence going to infinity; these are {4}-approximate groups for all {n}. Let {B_n} be the subset

\displaystyle  B_n := \{ a + b N_n^2: a,b \in {\bf Z}; |a|^2 + |b|^2 \leq N_n^2 \}.

Then the (reduced) Kronecker factor can be taken to be {G = {\bf R}^2} with Lebesgue measure {\mu_G}, and the additive limits of the {1_{A_n}} and {1_{B_n}} are then {1_A} and {1_B}, where {A} is the square

\displaystyle  A := \{ (a,b) \in {\bf R}^2: |a|, |b| \leq 1 \}

and {B} is the circle

\displaystyle  B := \{ (a,b) \in {\bf R}^2: a^2+b^2 \leq 1 \}.

Geometrically, the picture is similar to the Bohr set one, except now one uses a Freiman homomorphism {a + b N_n^2 \mapsto (\frac{a}{N_n}, \frac{b}{N_n})} for {a,b = O( N_n )} to embed the original sets {A_n, B_n} into the plane {{\bf R}^2}. In particular, one now expects the growth rate of the iterated sumsets {k A_n} and {k B_n} to be quadratic in {k}, in the regime where {k} is bounded and {n} is large.

Example 4 (Dissociated sets) Let {d} be a fixed natural number, and take

\displaystyle  A_n = \{0, v_1,\dots,v_d,-v_1,\dots,-v_d \}

where {v_1,\dots,v_d} are randomly chosen elements of a large cyclic group {{\bf Z}/p_n{\bf Z}}, where {p_n} is a sequence of primes going to infinity. These are {O(d)}-approximate groups. The (reduced) Kronecker factor {G} can (almost surely) then be taken to be {{\bf Z}^d} with counting measure, and the additive limit of {1_{A_n}} is {1_A}, where {A = \{ 0, e_1,\dots,e_d,-e_1,\dots,-e_d\}} and {e_1,\dots,e_d} is the standard basis of {{\bf Z}^d}. In particular, the growth rates of {k A_n} should grow approximately like {k^d} for {k} bounded and {n} large.

Example 5 (Random subsets of groups) Let {A_n = G_n} be a sequence of finite additive groups whose order is going to infinity. Let {B_n} be a random subset of {G_n} of some fixed density {0 \leq \lambda \leq 1}. Then (almost surely) the Kronecker factor here can be reduced all the way to the trivial group {\{0\}}, and the additive limit of the {1_{B_n}} is the constant function {\lambda}. The convolutions {\frac{1}{|G_n|} 1_{B_n} * 1_{B_n}} then converge in the ultralimit (modulo almost everywhere equivalence) to the pullback of {\lambda^2}; this reflects the fact that {(1-o(1))|G_n|} of the elements of {G_n} can be represented as the sum of two elements of {B_n} in {(\lambda^2 + o(1)) |G_n|} ways. In particular, {B_n+B_n} occupies a proportion {1-o(1)} of {G_n}.

Example 6 (Trigonometric series) Take {A_n = G_n = {\bf Z}/p_n {\bf C}} for a sequence {p_n} of primes going to infinity, and for each {n} let {\xi_{n,1},\xi_{n,2},\dots} be an infinite sequence of frequencies chosen uniformly and independently from {{\bf Z}/p_n{\bf Z}}. Let {f_n\colon {\bf Z}/p_n{\bf Z} \rightarrow {\bf C}} denote the random trigonometric series

\displaystyle  f_n(x) := \sum_{j=1}^\infty 2^{-j} e^{2\pi i \xi_{n,j} x / p_n }.

Then (almost surely) we can take the reduced Kronecker factor {G} to be the infinite torus {({\bf R}/{\bf Z})^{\bf N}} (with the Haar probability measure {\mu_G}), and the additive limit of the {f_n} then becomes the function {f\colon ({\bf R}/{\bf Z})^{\bf N} \rightarrow {\bf R}} defined by the formula

\displaystyle  f( (x_j)_{j=1}^\infty ) := \sum_{j=1}^\infty e^{2\pi i x_j}.

In fact, the pullback {\pi^* f} is the ultralimit of the {f_n}. As such, for any standard exponent {1 \leq q < \infty}, the normalised {l^q} norm

\displaystyle  (\frac{1}{p_n} \sum_{x \in {\bf Z}/p_n{\bf Z}} |f_n(x)|^q)^{1/q}

can be seen to converge to the limit

\displaystyle  (\int_{({\bf R}/{\bf Z})^{\bf N}} |f(x)|^q\ d\mu_G(x))^{1/q}.

The reader is invited to consider combinations of the above examples, e.g. random subsets of Bohr sets, to get a sense of the general case of Theorem 1.

It is likely that this theorem can be extended to the noncommutative setting, using the noncommutative Freiman theorem of Emmanuel Breuillard, Ben Green, and myself, but I have not attempted to do so here (see though this recent preprint of Anush Tserunyan for some related explorations); in a separate direction, there should be extensions that can control higher Gowers norms, in the spirit of the work of Szegedy.

Note: the arguments below will presume some familiarity with additive combinatorics and with nonstandard analysis, and will be a little sketchy in places.

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 4,590 other followers