User terry tao - MathOverflow

How much of character theory can be done without Schur's lemma or the Artin-Wedderburn theorem?

2013-05-21T16:39:13Z

This is a somewhat imprecise question, as I am not sure how exactly how to formalise how to do mathematics "without" a certain key tool, but hopefully the intent of the question will still be clear.

Let $G$ be a finite group. Traditionally, a character $\chi: G \to {\bf C}$ on $G$ is defined as being the trace of a finite-dimensional unitary representation $\rho: G \to U(V)$ of $G$, and then representation-theoretic tools (including Schur's lemma) can then be used to derive the basic results of character theory, including the following assertions:

The irreducible characters form an orthonormal basis of the space $L^2(G)^G$ of class functions, and all other characters are natural number combinations of the irreducible characters.
The space of characters form a semiring with identity; in particular, for three irreducible characters $\chi_1,\chi_2,\chi_3$, the structure constants $\langle \chi_1 \chi_2, \chi_3 \rangle$ are natural numbers.
For any character $\chi$, $\chi(1)$ is a positive integer.
For any character $\chi$, $\chi(g^{-1})=\overline{\chi(g)}$ for all $g$.
For any irreducible character $\chi$, the convolution operation $f \mapsto f * \chi(1) \chi$ is a minimal idempotent in $L^2(G)$, and one has the Fourier inversion formula $f = \sum_\chi f * \chi(1) \chi$ for all class functions $f$. Furthermore, the image $I_\chi$ of the convolution operation $f \mapsto f * \chi(1) \chi$ in $L^2(G)$ (or ${\bf C} G$) is an irreducible $G \times G$ representation.
If $\chi$ is an irreducible character of $G$, and $\eta$ is an irreducible character of a subgroup $H$ of $G$, then the structure constant $\langle \chi, \operatorname{Ind}^G_H \eta \rangle_{L^2(G)^G} = \langle \operatorname{Res}^H_G \chi, \eta \rangle_{L^2(H)^H}$ is a natural number.

Note that representation theory does not make an explicit appearance in the above character theory facts (induction and restriction of characters can be done at a purely character-theoretic level without explicit reference to representations), other than as one of the conclusions to Fact 5.

Note also that one can define characters directly, without mention of representations. The space $L^2(G)^G$ of class functions is a finite-dimensional commutative algebra under the convolution operation, and one can then locate the minimal idempotents $f$ of this algebra; $f(1)$ will then be positive, so one can define an "irreducible" character $\chi$ associated to this idempotent by the formula $f = \chi(1) \chi$ with $\chi(1) := f(1)^{1/2}$ being the positive square root of $f(1)$. One can then define an arbitrary character to be a natural number combination of the irreducible characters. This definition of character automatically gives Facts 1, 4, and 5 above (the $G \times G$-irreducibility of $I_\chi$ can be obtained by computing that the dimension of $\operatorname{Hom}^{G \times G}(I_\chi,I_\chi)$ is one), and if one is allowed to use Schur's lemma (or the Artin-Wedderburn theorem), one can also show that this definition is equivalent to the usual representation-theoretic definition of a character which then gives the remaining Facts 2, 3, and 6.

My (imprecise) question is whether one can still recover Facts 2, 3, and 6 from this non-representation-theoretic definition of a character if one is "not allowed" to use Schur's lemma or the Artin-Wedderburn theorem. Now, I do not know how to rigorously formalise the concept of not being allowed to use a particular mathematical result; my first attempt was to phrase the problem with the complex numbers replaced by the field of definition of the characters $\chi$ (or the cyclotomic field of order $|G|$), so that the underlying field is not algebraically closed and so Schur's lemma or Artin-Wedderburn do not directly apply. But this is hardly any constraint at all since one can immediately pass to the algebraic closure of these fields in order to bring Schur or Artin-Wedderburn back into play. Another option is to take a constructivist (or maybe reverse mathematics) point of view, and only permit one's mathematical reasoning to work with representations as long as they can be constructed from characters using explicit, "functorial", representation-theoretic constructions (e.g. tensor sum, tensor product, orthogonal complement, isotypic component, Schur functors, induction, or restriction) from concrete representations (e.g. trivial representation, regular representation, or quasiregular representation), but prohibit any argument that requires one to make "arbitrary" or "non-functorial" choices on representations (and in particular, to split an isotypic representation or module into irreducibles). However, I do not know how to formalise this sort of mathematical reasoning (perhaps one has to introduce a suitable topos?). It has also been suggested to me (by Allen Knutson) that perhaps the correct setting for this framework is that of quantum groups over roots of unity rather than classical groups, but I am not familiar enough with quantum groups to formalise this suggestion.

Leaving aside the question of how to properly formalise the question, one can make some intriguing partial progress towards Facts 2, 3, 6 without invoking Schur or Artin-Wedderburn. The isotypic representation $I_\chi$ has character $\chi(1) \chi$ by construction, so in particular this shows that $\chi(1)^2$ is a positive integer which is in some sense the "square" of Fact 3. By considering the $\chi_3\otimes \overline{\chi_3}$-isotypic component of $I_{\chi_1} \otimes I_{\chi_2}$, viewed as $G \times G$ representations, one can similarly show that the square $|\langle \chi_1 \chi_2, \chi_3 \rangle|^2$ of the structure constant $\langle \chi_1 \chi_2, \chi_3 \rangle$ is a natural number, and by viewing these representations instead as $G$-representations one also gets that $\chi_1(1)\chi_2(1) \chi_3(1) \langle \chi_1 \chi_2, \chi_3 \rangle$ is a natural number. These two facts don't quite establish Fact 2, but they do at least show that Fact 3 implies Fact 2. Finally, for Fact 6, the Frobenius reciprocity $\langle \chi, \operatorname{Ind}^G_H \eta \rangle_{L^2(G)^G} = \langle \operatorname{Res}^H_G \chi, \eta \rangle_{L^2(H)^H}$ is an easy algebraic identity if one defines induction and restriction in character-theoretic terms, and the same sort of arguments as before show that $|\langle \chi, \operatorname{Ind}^G_H \eta \rangle_{L^2(G)^G}|^2$ and $\chi(1) \eta(1) \langle \chi, \operatorname{Ind}^G_H \eta \rangle_{L^2(G)^G}$ are natural numbers, so again Fact 3 will imply Fact 6. (Conversely, it is not difficult to deduce Fact 3 from either Fact 2 or Fact 6.)

So it all seems to boil down to Fact 3, or equivalently that the dimension of any minimal ideal of $L^2(G)$ (or ${\mathbf C} G$, if you prefer) is a perfect square. This is immediate from the Artin-Wedderburn theorem, and also follows easily from Schur's lemma (applied to an irreducible representation of this ideal) but I have been unable to demonstrate this fact without such a representation-theoretic (or module-theoretic) tool.

Characters do give a partial substitute for Schur's lemma, namely that the dimension of the space $\operatorname{Hom}^G(V,W)$ of $G$-morphisms between two representations $V,W$ is equal to $\langle \chi_V, \chi_W \rangle_{L^2(G)^G}$, where $\chi_V, \chi_W$ are the characters associated to $V, W$. This gives Schur's lemma when the characters $\chi_V, \chi_W$ are irreducible in the sense defined above (defined through minimal idempotents and square roots rather than through irreducible representations). At the level of $G \times G$-representations, the isotypic components $I_\chi$ are irreducible (in both the character-theoretic and representation-theoretic senses) and so one has a satisfactory theory at this level (which is what is giving the "square" of Facts 2, 3, and 6) but at the level of $G$-representations there are these annoying multiplicities of $\chi(1)$ which do not seem to be removable without the ability to reduce to subrepresentations for which Schur's lemma applies.

Somehow the enemy is a sort of phantom scenario in which a group-like object $G$ has an irreducible (but somehow not directly observable) "ghost representation" of an irrational dimension such as (say) $\sqrt{24}$, creating an isotypic component $I_\chi$ whose dimension ($24$, in this case) is not a perfect square. This is clearly an absurd situation, but one which appears consistent with the weakened version of representation theory discussed above, in which Schur's lemma, the Artin-Wedderburn theorem, or "non-constructive" representations are not available. But I do not know if this is a genuine limitation to this sort of theory (e.g. can one cook up a quantum group with such irrational representations?), or whether I am simply missing some clever argument.

(My motivation for this question, by the way, is to explore substitutes for character-theoretic or representation-theoretic methods in finite group theory, for instance to find alternate proofs of Frobenius's theorem on Frobenius groups, which currently relies crucially on Fact 6.)

Can the fact that the square of an integer is a natural number be categorified?

2013-05-23T17:13:15Z

If $a$ and $b$ are natural numbers, then $a-b$ is an integer and so the square $(a-b)^2$ is a natural number. In particular

$$ (a-b)^2 \geq 0. \qquad (1)$$

Combining this fact with the identity

$$ ab + ba + (a-b)^2 = a^2 + b^2 \qquad (2)$$

we obtain the inequality

$$ ab + ba \leq a^2 + b^2 \qquad (3)$$

which can be viewed as a special case of either the arithmetic mean-geometric mean inequality or the Cauchy-Schwarz inequality.

Of course this argument can be generalised; for instance, if $v, w$ are elements of a (real or complex) inner product space, then

$$ \langle v-w, v -w \rangle \geq 0 \qquad (1')$$

and by combining this with the identity

$$ \langle v, w \rangle + \langle w, v \rangle + \langle v-w, v-w \rangle = \langle v,v \rangle + \langle w, w \rangle \qquad (2')$$

we conclude the inequality

$$ \langle v, w \rangle + \langle w, v \rangle \leq \langle v, v \rangle + \langle w, w \rangle \qquad (3')$$

which is closely related to the Cauchy-Schwarz inequality (indeed one can amplify (3') to the Cauchy-Schwarz inequality, as discussed in this blog post of mine).

The inequalities (3) or (3') can be interpreted in various categories. For instance, (3) in the category of finite sets becomes

Theorem 1. Let $A, B$ be finite sets. Then there exists an injection from $(A \times B) \uplus (B \times A)$ to $(A \times A) \uplus (B \times B)$.

while (3) in the category of finite-dimensional vector spaces becomes

Theorem 2. Let $V, W$ be finite-dimensional vector spaces. Then there exists an injective linear map from $(V \otimes W) \oplus (W \otimes V)$ to $(V \otimes V) \oplus (W \otimes W)$.

In the category of unitary representations of a compact (or finite) group $G$, a little character theory (or complete reducibility together with Schur's lemma) allows one to similarly interpret (3') in this category:

Theorem 3. Let $V, W$ be finite-dimensional unitary representations of a compact group $G$. Then there exists an injective $G$-equivariant linear map from $(V \otimes W) \oplus (W \otimes V)$ to $(V \otimes V) \oplus (W \otimes W)$.

Theorem 3. Let $V, W$ be finite-dimensional unitary representations of a compact group $G$. Then there exists an injective linear map from $\operatorname{Hom}_G(V,W) \times \operatorname{Hom}_G(W,V)$ to $\operatorname{Hom}_G(V,V) \times \operatorname{Hom}_G(W,W)$.

One can presumably state similar theorems for modules of semisimple algebras over an algebraically closed field, or for various types of vector bundles (or finite covers) over a fixed base space, although I won't attempt to do so here.

Anyway, these results suggest that there may be a way to categorify the inequalities (1), (3), (1'), (3') and/or the identities (2), (2'), for instance by finding a bijective proof (or perhaps an "injective proof") of Theorem 1. However, despite the simplicity of these inequalities and identities this seems to be a surprisingly difficult task. In the ordered case in which one knows that $a=b+k$ or $b=a+k$ for some natural number $k$, one can interpret $(a-b)^2$ as $k^2$, so it is not difficult to categorify Theorem 1 if one possesses an injection from $A$ to $B$ or vice versa, and similarly for Theorem 2 and Theorem 3. From this and the trichotomy of order one can finish off Theorem 1 or Theorem 2, though this is an argument which requires one to make a number of arbitrary choices (as the injections here are not canonical) and so one might consider this to be an incomplete categorification. And in any event, this trick does not seem to recover the full strength of Theorem 3, since there need not be an injective $G$-equivariant map from $V$ to $W$ or vice versa. So I'm wondering if there is another way to categorify these results? For the vector space results (Theorem 2 and Theorem 3) it seems natural to try to use K-theory somehow to achieve this goal (since K-theory already has a formalism for taking formal differences of vector spaces), but I don't know enough K-theory to take this idea further.

[Closely related questions to these were discussed some years ago at the n-category cafe here and here regarding the categorification of the Cauchy-Schwarz inequality, but the results of the discussion were inconclusive, although David Speyer did show that there was an obstruction to categorifying Theorem 3 in the case $G = Z/2Z$ in that the injection could not be natural.]

How many orders of infinity are there?

2010-06-26T17:40:55Z

Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's say that one growth function $F$ dominates another $G$ if one has $F(n) \geq G(n)$ for all $n$. (One could instead ask for eventual domination, in which one works with sufficiently large $n$ only, or asymptotic domination, in which one allows a multiplicative constant $C$, but it seems the answers to the questions below are basically the same in both cases, so I'll stick with the simpler formulation.)

Let's call a collection ${\mathcal F}$ of growth functions ~~complete~~ cofinal if every growth function is dominated by at least one growth function in ${\mathcal F}$.

Cantor's diagonalisation argument tells us that a cofinal set of growth functions cannot be countable. On the other hand, the set of all growth functions has the cardinality of the continuum. So, on the continuum hypothesis, a cofinal set of growth functions must necessarily have the cardinality of the continuum.

My first question is: what happens without the continuum hypothesis? Is it possible to have a cofinal set of growth functions of intermediate cardinality?

My second question is more vague: is there some simpler way to view the poset of growth functions under domination (or asymptotic domination) that makes it easier to answer questions like this? Ideally I would like to "control" this poset in some sense by some other, better understood object (e.g. the first uncountable ordinal, the nonstandard natural numbers, or the Stone-Cech compactification of the natural numbers).

EDIT: notation updated in view of responses.

Answer by Terry Tao for Good uses of Siegel zeros?

2013-03-22T17:36:52Z

With the usual definition of a Siegel zero (involving an unspecified constant $C_\varepsilon$ for each $\varepsilon>0$), it is not easy to talk about a "single" Siegel zero unless one decides to fix exactly how $C_\varepsilon$ is to depend on $\varepsilon$.

On the other hand, the classical proof of the prime number theorem also shows that $L(\sigma+it,\chi)$ has no zeroes in the region $\sigma \geq 1-\frac{c}{\log q(|t|+1)}$ for some effective (and very explicit) $c>0$, with at most one exception. This gives an effective prime number theorem in arithmetic progressions

$$ \psi(x; a,q) = \frac{x}{\phi(q)} - \frac{\chi(a)}{\phi(q)} \frac{x^\beta}{\beta} + O( x \exp(-b \sqrt{\log x}))$$

for an absolute and effective constant $b>0$, where $\beta$ is the exceptional zero (if it exists) of the exceptional quadratic character $\chi$. (If there is no exceptional zero, the second term on the right-hand side is simply deleted.) This formula can then be used as a partial but effective substitute for the Siegel-Walfisz theorem for all sorts of number-theoretic applications, e.g. this formula (or something very close to it) is used in all the known effective unconditional proofs of Vinogradov's three primes theorem. In many cases the results are actually easier to prove if the exceptional zero is present. Iwaniec's ICM survey at http://www.icm2006.org/proceedings/Vol_I/16.pdf discusses these issues in more detail.

ADDED LATER: Another interesting phenomenon, first observed by Montgomery and Weinberger, is that the existence of a single Siegel zero $L(\sigma,\chi)=0$ forces many other L-functions $L(s,\psi)$ to have most of their zeroes (at a certain height) arranged on the critical line and to lie close to an arithmetic progression (this type of behaviour is occasionally referred to as the "Alternative Hypothesis", being the extreme opposite to the more commonly believed "GUE hypothesis" but which thus far has proven impossible to completely exclude). Roughly speaking, the reason for this is that if $L(\sigma,\chi)=0$ for some $\sigma$ close to $1$, then the residue of $\zeta(s) L(s,\chi)$ is unexpectedly small at $1$, making the Dirichlet convolution $1*\chi$ much sparser than expected. For any other Dirichlet character $\psi$, $\psi*\chi\psi$ is pointwise dominated by $1*\chi$ and is similarly sparse. This means that the function $L(s,\psi) L(s,\psi\chi)$ is very well behaved for typical $\psi$ and for $s$ near the critical line; indeed, it is dominated by the initial segment of the Dirichlet series $\sum_n \frac{\psi*\psi\chi(n)}{n^s}$ (which is very smooth in $s$), plus the complementary term coming from the functional equation (or equivalently, from Poisson summation), which oscillates at a precise frequency depending on the height of $s$ and the conductor of $\psi$ and $\psi \chi$. The interaction between these two terms is what places the zeroes of $L(s,\psi) L(s,\psi\chi)$, and hence of $L(s,\psi)$, near an arithmetic progression.

Answer by Terry Tao for Is there any proof that you feel you do not "understand"?

2013-05-18T16:06:47Z

As an undergraduate, I learned the Sylow theorems in my algebra classes but could never retain either the statement or proof of these theorems in memory except for short periods of time (and in particular, for the duration of an algebra exam). I think the problem was that I was exposed to these theorems long before I had internalised the concept of a group action. But once one has the mindset to approach a mathematical object $X$ through the various natural group actions on that object, and then look at the various dynamical features of that action (orbits, stabilisers, quotients, etc.) then all the Sylow theorems (and Cauchy's theorem, Lagrange's theorem, etc.) all boil down to observing some natural action on some natural space (e.g. the conjugacy action on the group, or on tuples of elements on that group) and counting orbits and stabilisers (p-adically, in the case of the Sylow theorems). (Isaacs book on finite group theory emphasises this perspective very nicely, by the way.)

Why are Schur multipliers of finite simple groups so small?

2013-05-17T17:39:11Z

Given a finite simple group $G$, we can consider the quasisimple extensions $\tilde G$ of $G$, that is to say central extensions which remain perfect. Some basic group cohomology (based on the standard trick of averaging a cocycle to try to make it into a coboundary) shows that up to isomorphism, there are only finitely many such quasisimple extensions, and they are all quotients of a maximal quasisimple extension, which is known as the universal cover of $G$, and is an extension of $G$ by a finite abelian group known as the Schur multiplier $H^2(G,{\bf C}^\times)$ of $G$ (or maybe it would be slightly more accurate to say that it is the Pontryagian dual of the Schur multiplier, although up to isomorphism the two groups coincide).

On going through the list of finite simple groups it is striking to me how small the Schur multipliers are for all of them; with the exception of the projective special linear groups $A_{n-1}(q)=PSL_n({\bf F}_q)$ and the projective special unitary groups ${}^2 A_{n-1}(q^2) = PSU_n({\bf F}_q)$ , all other finite simple groups have Schur multiplier of order no larger than 12, and even the projective special linear and special unitary groups of rank $n-1$ do not have Schur multiplier of size larger than $n$ (other than a finite number of small exceptional cases, but even there the largest Schur multiplier size is 48). In particular, in all cases the Schur multiplier is much smaller than the order of the group itself (indeed it is always of order $O(\sqrt{\frac{\log|G|}{\log\log|G|}})$). For comparison, the standard proof of the finiteness of the Schur multiplier (based on showing that every $C^\times$-valued cocycle on $G$ is cohomologous to $|G|^{th}$ roots of unity) only gives the terrible upper bound of $|G|^{|G|}$ for the order of the multiplier.

In the case of finite simple groups of Lie type, one can think of the Schur multiplier as analogous to the notion of a fundamental group of a simple Lie group, which is similarly small (being the quotient of the weight lattice by the root lattice, it is no larger than $4$ in all cases except for the projective special linear group $PSL_n$, where it is of order $n$ at most). But this doesn't explain why the Schur multipliers for the alternating and sporadic groups are also so small. Intuitively, this is asserting that it is very difficult to make a non-trivial central extension of a finite simple group. Is there any known explanation (either heuristic, rigorous, or semi-rigorous) that helps explain why Schur multipliers of finite simple groups are small? For instance, are there results limiting the size of various group cohomology objects that would support (or at least be very consistent with) the smallness of Schur multipliers?

Ideally I would like an explanation that does not presuppose the classification of finite simple groups.

Answer by Terry Tao for For what spaces is the Hardy-Littlewood maximal operator of strong type $(p,p)$ if and only if $p > p_0 > 1$?

2013-05-14T16:01:38Z

For the uncentred maximal function, one can cook up examples by using the star graph with a suitable weight on the vertices. In more detail, if one takes a star graph (with the graph metric) with $n$ spokes, with the root vertex having measure one and the leaves having measure $n^{-1/p_0}$, then the uncentred maximal function has bounded $L^p$ operator norm for $p \geq p_0$ but unbounded norm for $p > p_0$, by testing this function on the indicator function of the root vertex. If one then takes a disjoint union of such star graphs with the $n$ parameter going to infinity, one gets an example of the form you wanted.

For the centred maximal function, the star graph construction is no longer useful, but there are other, more complicated, constructions (based on metrics in vector spaces over finite fields) in Section 6 of my paper with Assaf Naor which can probably be adapted to give a suitable counterexample, though this would require a bit of tinkering (the examples there were designed to have weak (1,1) fail but strong (p,p) for all $p>1$).

Answer by Terry Tao for Compactness in Sobolev spaces

2013-04-23T02:55:25Z

No. As a general rule, in order to obtain compactness in some norm, one needs control of a higher regularity than what is associated to that norm, in order to shut down an "escape to frequency infinity". For instance, $H^1_0$ has one degree of regularity, so one needs to control a norm involving more than one derivative in order to obtain compactness. (But in many cases one only needs an epsilon more regularity; for instance, Arzela-Ascoli tells us that equicontinuity, which can be thought of as an infinitesimal amount of regularity, is enough (together with some additional hypotheses) to obtain compactness in the uniform norm, which has zero degrees of regularity.)

In this specific case, a concrete counterexample can be obtained by considering the unit cube $\Omega = [0,1]^3$ and the sequence $f_n := \frac{1}{n} \sin(2\pi n x) \sin(2\pi y) \sin(2\pi z)$, which goes to zero in $L^\infty$ but stays away from zero in $H^1_0$, and so cannot have any $H^1_0$ convergent subsequence.

Answer by Terry Tao for How many distinct eigenvalues does a random graph have?

2013-04-22T14:49:57Z

In this recent paper of Erdos, Knowles, Yau, and Yin, it is shown that in the bulk of the spectrum, the spacing between eigenvalues of an Erdos-Renyi graph on $n$ vertices obeys GOE statistics asymptotically. This implies that most of the eigenvalues are simple (i.e. $n-o(n)$ of the $n$ eigenvalues are simple) asymptotically almost surely, so that the number of distinct eigenvalues is $n-o(n)$ a.a.s.. It is very likely that in fact a.a.s. all of the $n$ eigenvalues are simple; Van Vu and I have some preliminary unpublished results in this direction but we are still working on the full problem.

Answer by Terry Tao for Intuition behind the spectral density of random matrices

2013-04-10T15:34:31Z

I don't know of a fully intuitive derivation, but there are some informal arguments that give the circular law with a relatively small amount of calculation.

Let $M$ be a matrix where the entries are iid with mean zero and variance one. One can begin with the determinant formula

$$ \log |\det( M - z )| = \sum_{j=1}^n \log |\lambda_j - z|.$$

The circular law suggests that the eigenvalues $\lambda_j$ should be uniformly distributed in the disk of radius $\sqrt{n}$, so one should be proving something like

$$ \log |\det( M - z )| \approx \frac{1}{\pi} \int_{|w| \leq \sqrt{n}} \log |w-z|\ dw.$$

A routine calculation (e.g. using Jensen's formula, or the fundamental solution for the Laplacian) reveals that the RHS is equal to $n \log |z|$ when $|z| \geq \sqrt{n}$ and $\frac{1}{2} n \log n - \frac{1}{2} n + \frac{1}{2} |z|^2$ for $|z| \leq \sqrt{n}$. So heuristically, the circular law is equivalent to the approximations

$$ |\det(M-z)| \approx |z|^n$$

for $|z| \geq \sqrt{n}$ and

$$ |\det(M-z)| \approx n^{n/2} e^{-n/2} e^{|z|^2/2}$$

for $|z| \leq \sqrt{n}$. Here one should interpret the $\approx$ symbol rather loosely (in particular, polynomial factors in $n$ should be considered negligible).

However, by the Leibniz formula for determinants and the iid mean zero variance one nature of the entries (which makes all the covariances between the terms in the Leibniz formula vanish), one can easily compute that

$$ {\bf E} |\det(M-z)|^2 = \sum_{j=0}^n |z|^{2j} \frac{n!}{j!}.$$

(This type of calculation goes back to an old paper of Turan.)

For $|z| \gg \sqrt{n}$, the $|z|^{2n}$ term on the RHS dominates, while for $|z| \ll \sqrt{n}$, the RHS is most of the Taylor series for $n! e^{|z|^2}$. The claim then morally follows from Stirling's approximation.

(Incidentally, my recent paper with Van Vu on local versions of the circular law basically proceeds by making the above argument rigorous; see also recent work of Bourgarde, Yau, and Yin. The idea of controlling the spectrum of an iid matrix through its log-determinant goes back to the early work of Girko.)

Note also that without too much calculation, one can see that the limiting law of the spectrum should be invariant with respect to rotations around the origin (especially if one assumes that the entries of the iid matrix are similarly invariant, e.g. they are complex gaussian). From the matrix inequality $\sum_{j=1}^n |\lambda_j|^2 \leq \hbox{tr}(M M^*)$ and the law of large numbers we also see that the typical size of an eigenvalue $\lambda_j$ should be of the order of $\sqrt{n}$. These facts fall well short of the full circular law but are certainly consistent with that law.

Answer by Terry Tao for Ordinary Generating Function for Mobius

2013-04-04T16:11:36Z

Mobius randomness heuristics suggest that $\sum_n \mu(n) (r e^{i\theta})^n$ does not converge to a limit as $r \to 1^-$ for any (or at least almost any) $\theta$. If it did converge for some $\theta$, then we would have

$$\sum_n \mu(n) e^{in\theta} \psi_k(n) \to 0$$ as $k \to \infty$, where

$$ \psi_k(n) := (1-2^{-k-1})^n - (1-2^{-k})^n.$$

The cutoff function $\psi_k$ is basically a smoothed out version of the indicator function $1_{[2^k,2^{k+1}]}$. The Mobius randomness heuristic (discussed for instance in this article of Sarnak) then suggests that the sum $\sum_n \mu(n) e^{in\theta} \psi_k(n)$ should have a typical size of $2^{k/2}$, and so should not decay to zero as $k \to \infty$.

Note from Plancherel's theorem that the $L^2_\theta$ mean of $\sum_n \mu(n) e^{in\theta} \psi_k(n)$ is indeed comparable to $2^{k/2}$. This does not directly preclude the (very unlikely) scenario that this exponential sum is very small for many $\theta$ and only large for a small portion of the $\theta$, but if one optimistically applies various versions of the Mobius randomness heuristic (with square root gains in exponential sums) to guess higher moments of $\sum_n \mu(n) e^{in\theta} \psi_k(n)$ in $\theta$, one is led to conjecture a central limit theorem type behaviour for the distribution of this quantity (as $\theta$ ranges uniformly from $0$ to $2\pi$), i.e. it should behave like a complex gaussian with mean zero and variance $\sim 2^k$, and in particular it should only be $O(1)$ about $O(2^{-k})$ of the time, and Borel-Cantelli then suggests divergence for almost every $\theta$ at least. Unfortunately this is all very heuristic, and it seems difficult with current technology to unconditionally rule out a strange conspiracy that makes $\sum_n \mu_n (re^{i\theta})^n$ bounded as $r \to 1$ for some specific value of $\theta$ (say $\theta = \sqrt{2} \pi$), though this looks incredibly unlikely to me. (One can use bilinear sums methods, e.g. Vaughan identity, to get some nontrivial pointwise upper bounds on these exponential sums when $\theta$ is highly irrational, but I see no way to get pointwise lower bounds, since $L$-function methods will not be available in this setting, and there may well be some occasional values of $\theta$ and $k$ for which these sums are actually small. But it is likely at least that the $\theta=0$ theory can be extended to rational values of $\theta$.)

Is there a natural random process that is rigorously known to produce Zipf's law?

2010-09-18T16:24:22Z

Zipf's law is the empirical observation that in many real-life populations of n objects, the $k^{th}$ largest object has size proportional to $1/k$, at least for $k$ significantly smaller than $n$ (and one also sometimes needs to assume $k$ somewhat larger than 1). It is a special case of a power law distribution (in which $1/k$ is replaced with $1/k^\alpha$ for some exponent $\alpha$), but the remarkable thing is that in many empirical cases (e.g. frequencies of words, or sizes of cities), the exponent is very close to 1.

My question is: is there a "natural" random process (e.g. a birth-death process) that one can rigorously demonstrate (or at least conjecture) to generate populations of n non-negative quantities $X_1,\ldots,X_n$ (with n large but possibly variable) that obey Zipf's law on average with exponent 1? There are plenty of natural ways to generate processes that have power law tails (e.g. consider n positive quantities $X_1,\ldots,X_n$ evolving by iid copies of log-Brownian motion), but I don't see how to ensure the exponent is 1 without artificially setting the parameters to force this.

Ideally, such processes should be at least somewhat plausible as models for an empirical situation in which Zipf's law is observed to hold, such as city sizes, but I would be happy with any non-artificial example of a process.

One obstruction here is the exponent one property is not invariant with respect to taking powers: if $X_1,\ldots,X_n$ obeys Zipf's law with exponent one, then for any fixed $\beta>0$, $X_1^\beta,\ldots,X_n^\beta$ obeys the power law with a different exponent $\beta$. So whatever random process one would propose for Zipf's law must somehow be quite different from its powers.

Does the inverse function theorem hold for everywhere differentiable maps?

2011-09-09T23:09:04Z

(This question was posed to me by a colleague; I was unable to answer it, so am posing it here instead.)

Let $f: {\bf R}^n \to {\bf R}^n$ be an everywhere differentiable map, and suppose that at each point $x_0 \in {\bf R}^n$, the derivative $Df(x_0)$ is nonsingular (i.e. has non-zero determinant). Does it follow that $f$ is locally injective, i.e. for every $x_0 \in {\bf R}^n$ is there a neighbourhood $U$ of $x_0$ on which $f$ is injective?

If $f$ is continuously differentiable, then the claim is immediate from the inverse function theorem. But if one relaxes continuous differentiability to everywhere differentiability, the situation seems to be much more subtle:

In one dimension, the answer is "Yes"; this is the contrapositive of Rolle's theorem, which works in the everywhere differentiable category. (The claim is of course false in weaker categories such as the Lipschitz (and hence almost everywhere differentiable) category, as one can see from a sawtooth function.)
The Brouwer fixed point theorem gives local surjectivity, and degree theory gives local injectivity if $\det Df(x_0)$ never changes sign. (This gives another proof in the case when $f$ is continuously differentiable, since $\det Df$ is then continuous.)
On the other hand, if one could find an everywhere differentiable map $f: B \to B$ on a ball $B$ that was equal to the identity near the boundary of $B$, whose derivative was always non-singular, but for which $f$ was not injective, then one could paste infinitely many rescaled copies of this function $f$ together to produce a counterexample. The degree theory argument shows that such a map does not exist in the orientation-preserving case, but maybe there is some exotic way to avoid the degree obstruction in the everywhere differentiable category?

It seems to me that a counterexample, if one exists, should look something like a Weierstrass function (i.e. a lacunary trigonometric series), as one needs rather dramatic failure of continuity of the derivative to eliminate the degree obstruction. To try to prove the answer is yes, one thought I had was to try to use Henstock-Kurzweil integration (which is well suited to the everywhere differentiable category) and combine it somehow with degree theory, but this integral seems rather unpleasant to use in higher dimensions.

Answer by Terry Tao for Applications of Rademacher's Theorem

2013-03-21T17:16:54Z

The one-dimensional Rademacher differentiation theorem implies that the Cartesian product of two compact measure zero subsets of the real line is purely unrectifiable, which in turn can be used to establish the Besicovitch projection theorem, which asserts that if a subset of the plane has finite 1-dimensional Hausdorff measure and is purely unrectifiable, then almost every projection of that set to the real line has measure zero. Thus, for instance, if one takes the Cartesian product $C \times C$ of two copies of the middle-halves Cantor set $\{0,1\} \in C = \frac{1}{4} C \cup (\frac{1}{4} C + \frac{3}{4}) \subset [0,1]$, then almost every line in the plane will fail to hit this set. (Quantitative versions of this problem (commonly known as "Buffon's needle problem") have attracted attention in recent years, see e.g. the recent survey of Laba at http://arxiv.org/abs/1212.0247 .)

A few years ago with Hans Lindblad in http://arxiv.org/abs/1011.0949 , we used the one-dimensional Rademacher differentiation theorem to establish that solutions to a certain nonlinear wave equation in one spatial dimension necessarily decayed to zero as time went to infinity. This is in contrast to the linear wave equation which does not decay in one spatial dimension. The rough idea was that if the solution did not decay, then one could show that it concentrated along a Lipschitz curve in spacetime, which by Rademacher was approximately linear at some locations and some scales, and this could be shown to be in contradiction to a certain Morawetz-type estimate on solutions to nonlinear wave equations.

One fairly well known application of the higher-dimensional Rademacher differentiation theorem is by Pansu who extended this theorem to Carnot groups, and a variant of his theory establishes the fact that if two finitely generated nilpotent groups are quasiisometric, then their associated Carnot groups are isomorphic, which is still one of the strongest statements known about quasiisometry of groups in the nilpotent case.

Answer by Terry Tao for Reference for a nice proof of "undetermined coefficients"

2013-03-16T15:50:46Z

If $L$ has characteristic polynomial $\lambda \mapsto p(\lambda)$, then the conjugated differential operator $e^{-qt} L e^{qt}$ has characteristic polynomial $\lambda \mapsto p(\lambda+q)$. From this we may easily reduce the problem to the $q=0$ case.
If the characteristic polynomial $\lambda \mapsto p(\lambda)$ of $L$ has a zero of order $k$ at the origin, then $p$ factors as $p(\lambda) = \tilde p(\lambda) \lambda^k$, and $L$ similarly factors as $L = \tilde L \frac{d}{dt^k}$. Since every degree $m$ polynomial has a $k$-fold antiderivative that is equal to $t^k$ times a degree $m$ polynomial, we can thus reduce the problem to the $q=0, k=0$ case.
If $q=0$ and $k=0$, then $p(0)$ is non-vanishing; by rescaling we may take $p(0)=1$. Then $p(\lambda) = 1 + \lambda r(\lambda)$ for some polynomial $r$, so $L = 1 + R \frac{d}{dt}$ for some differential operator $R$. On the finite dimensional vector space spanned by $1,t,\ldots,t^m$, the operator $R \frac{d}{dt}$ acts nilpotently (as it always reduces the degree) and so $L$ is unipotent, hence invertible (by Neumann series), in this space, and the claim follows.

Riemannian surfaces with an explicit distance function?

2010-09-03T19:06:37Z

I'm looking for explicit examples of Riemannian surfaces (two-dimensional Riemannian manifolds $(M,g)$) for which the distance function d(x,y) can be given explicitly in terms of local coordinates of x,y, assuming that x and y are sufficiently close. By "explicit", I mean things like a closed form description in terms of special functions, by implicitly solving a transcendental equation or (at worst) by solving an ODE, as opposed to having to solve a variational problem or a PDE such as the eikonal equation, or an inverse problem for an ODE, or to sum an asymptotic series.

The only examples of this that I know of are the constant curvature surfaces, which can be locally modeled either by the Euclidean plane ${\bf R}^2$, the sphere ${\bf S}^2$, or the hyperbolic plane ${\bf H}^2$, for which we have classical formulae for the distance function.

But I don't know of any other examples. For instance, the distance functions on the surface of the solid ellipsoid or solid torus in ${\bf R}^3$ look quite unpleasant already to write down explicitly. Presumably Zoll surfaces would be the next thing to try, but I don't know of any tractable explicit examples of Zoll surfaces that are not already constant curvature.

Answer by Terry Tao for Second order difference implies differentiability

2013-02-16T20:37:07Z

As Gerald says, the answer is no without further hypotheses on f. But if one makes some minimal additional regularity hypotheses on f, such as continuity, then the answer is yes.

Write $D_h f(x)$ for the difference quotient $D_h f(x) := (f(x+h)-f(x))/h$, then the hypothesis is that $$ D_h f(x+h) = D_h f(x) + O( |h|^{1/2} )$$ for all $x, h$ (with $h$ nonzero), which implies $$ D_{2h} f(x) = D_h f(x + ih) + O( |h|^{1/2} )$$ for $i=0,1$. Iterating this we have $$ D_{2^j h} f(x) = D_h f(x + ih) + O( 2^{j/2} |h|^{1/2} ) \qquad (1)$$ for natural numbers $j$ and any integer $0 \leq i < 2^j$, which in particular implies $$ D_h f(x+ih) = D_h f(x) + O( |ih|^{1/2} ) \qquad (2)$$ for all integer $i$; in particular, we have $$ D_{(y-x)/n} f(y) = D_{(y-x)/n} f(x) + O( |y-x|^{1/2} )$$ for any distinct $x,y$ and natural number $n$. This already gives the derivative bound $|f'(y)-f'(x)| = O( |y-x|^{1/2} )$ if $f$ is differentiable.

To establish differentiability, we return to (1), which (in combination with (2)) gives $$ f(x+(i+2^j)h) - f(x+ih) = 2^j h D_h f(x) + O( |2^j h|^{3/2} )$$ whenever $i = O( 2^j )$. Telescoping this using binary expansion we see that $$ f(x+nh) - f(x) = n h D_h f(x) + O( |nh|^{3/2} )$$ or equivalently $$ D_{nh} f(x) = D_h f(x) + O( |nh|^{1/2} )$$ for any integer $n$ (not necessarily a power of two), and thus $$ D_{h} f(x) = D_{h/n} f(x) + O( |h|^{1/2} )$$ for any non-zero $h$ and nonzero integers $n$. In particular $$ D_{h} f(x) = D_{h'} f(x) + O( |h|^{1/2} + |h'|^{1/2} )$$ whenever $h,h'$ are nonzero rational (as then we can write $h = n h'', h' = n' h''$ for some nonzero integers $n,n'$ and some nonzero $h'$); by continuity of $f$, this is also true for nonzero real $h,h'$. Thus $D_h f$ is a Cauchy sequence as $h \to 0$, giving differentiability.

It is likely that one can also relax continuity to Lebesgue measurability (it seems that the above argument gives almost everywhere differentiability or something very close to this, in which case some version of the fundamental theorem of calculus should then finish the job).

Answer by Terry Tao for Geometric interpretations of matrix inverses

2013-02-05T18:03:36Z

Here is one simple geometric relationship: if $X_1,\ldots,X_n$ are the rows of $A$, and $C_1,\ldots,C_n$ are the columns of $A^{-1}$, then the length of the column $C_i$ is equal to the reciprocal of the distance between $X_i$ and the hyperplane $V_i$ spanned by the other $n-1$ rows $X_1,\ldots,X_{i-1},X_{i+1},\ldots,X_n$ of $A$. This is because $C_i$ is orthogonal to $V_i$ and has an inner product of $1$ with $X_i$. If one then square sums in $i$, we obtain the negative second moment identity

$$ \sum_{i=1}^n \sigma_i(A)^{-2} = \sum_{j=1}^n \hbox{dist}(X_j,V_j)^{-2}$$

where $\sigma_1(A),\ldots,\sigma_n(A)$ are the singular values of $A$, which turns out to be a useful identity in random matrix theory (see e.g. this blog post of mine). In particular, it highlights the importance of understanding the distance between a row and the hyperplane spanned by the other rows if one is to get some control on the small singular values.

Answer by Terry Tao for Trichotomies in mathematics

2013-02-03T03:03:59Z

After passing to a subsequence if necessary, a sequence of real numbers either (a) converges to a real number; (b) diverges to $+\infty$; or (c) diverges to $-\infty$. In a similar vein, a sequence of positive real numbers either (a) converges to a positive real; (b) diverges to $+\infty$; or (c) diverges to $0$. In nonstandard analysis, these trichotomies become those of being bounded, negative unbounded, or positive unbounded, or of being infinitesimal, unbounded, or neither (i.e. both bounded, and bounded away from zero). These are of course variants of the basic $(-,0,+)$ trichotomy.
Up to isomorphism, there are only three types of (connected) one-dimensional algebraic groups over an algebraically closed field: the additive group of the field, the multiplicative group of that field, and the elliptic curves over that field. (This last family would definitely be the "middle column".) This is of course connected to many of the other trichotomies previously mentioned. On the Riemann surface side, it comes from the fact that all one-dimensional connected complex groups are isomorphic to ${\bf C}/\Gamma$ for some discrete subgroup $\Gamma$ of ${\bf C}$, which can have rank 0 (additive case), 1 (multiplicative case), or 2 (elliptic curve case).
If one squints at it in just the right way, the classification of finite simple groups is a trichotomy: cyclic, Lie type (including Lie over F_1, i.e. alternating group), or sporadic. (Of course, it can be sliced in many other ways; counting the items in this Wikipedia list, for instance, would make it a tetratetracontachotomy.) Sometimes it is conceptually useful to split up the large Lie type groups into three regimes: large characteristic but bounded rank; large rank but bounded characteristic (including the alternating groups); and large characteristic and large rank. (Alternatively, one can partition into bounded rank, alternating, and unbounded rank.) One can debate as to which of these categories is the "middle column".
If $\xi_1,\xi_2,\xi_3$ are three frequencies with $\xi_3 = \xi_1+\xi_2$, then we have the Littlewood-Paley trichotomy: (a) "high-low" interactions with $|\xi_1| \gg |\xi_2|$ and $|\xi_1| \sim |\xi_3|$; (b) "low-high" interactions with $|\xi_1| \ll |\xi_2|$ and $|\xi_2| \sim |\xi_3|$; and (c) "high-high" interactions with $|\xi_1| \sim |\xi_2|$ and $|\xi_1| \gg |\xi_3|$. (One has to carefully demarcate the boundaries between these three possibilities to ensure it is a true trichotomy.) To an algebraic geometer, this would reflect the Y-shaped nature of the amoeba of the set $\{ (\xi_1,\xi_2,\xi_3): \xi_3 = \xi_1 + \xi_2 \}$. This trichotomy is important in harmonic analysis and PDE, and in particular in the paradifferential calculus of products and paraproducts (see e.g. this blog post of mine). Often, one of the three interactions will be the most dominant, reflecting either a high-to-low frequency cascade or a low-to-high frequency cascade, but it depends heavily on the situation. Note that this trichotomy is basically a variant of the $(<,=,>)$ trichotomy.
(ADDED LATER) Another variant of the $(<,=,>)$ trichotomy: most basic examples of semilinear PDE (or more precisely, a semilinear PDE problem, such as an initial value problem in a certain function space) can be classified as subcritical, critical, or supercritical, depending on whether the nonlinear component of the PDE is "weaker than", "comparable to", or "stronger than" the linear component in a suitable asymptotic limit (usually the fine scale/high frequency limit, although for scattering theory the coarse scale/low frequency limit is the relevant one instead). This distinction (which can usually be made precise through a scaling analysis or dimensional analysis) is often decisive in determining the difficulty level of the PDE problem. For instance, the regularity problem for 3D Navier-Stokes is supercritical and thus considered close to intractable, but 2D Navier-Stokes is critical and was solved decades ago. The global analysis of Ricci flow (with surgery) was considered supercritical until Perelman discovered new monotone quantities that made it critical, which was absolutely necessary for Perelman to be able to execute the rest of Hamilton's program and solve the Poincare and geometrisation conjectures. In this trichotomy, the critical (or scale-invariant) case is generally viewed as the most interesting and delicate, with some very nice mathematical tools coming into play to control the interaction between different scales. Perhaps it should also be pointed out that this trichotomy is orthogonal to the elliptic/parabolic/hyperbolic trichotomy, which only concerns the linear component of the PDE and not the nonlinear component, and all nine combinations (critical elliptic PDE, supercritical parabolic PDE, etc.) are studied in the literature.
(ADDED YET LATER) In analysis, there are basically three scenarios that prevent a weakly convergent sequence $f_n$ of functions in some function space from being strongly convergent in that space: (a) escape to "horizontal infinity" (basically, the support of the function runs off to spatial infinity, i.e. moving bump type examples); (b) escape to "vertical infinity" (the peaks of the function go to infinity, e.g. a sequence of approximations to the identity converging weakly but not strongly to a delta function); and (c) escape to "frequency infinity" (the functions become increasingly oscillatory). If one can shut down all three modes of escape then one can recover strong convergence, and thus also strong (pre)compactness, cf. the Arzela-Ascoli theorem which has three hypotheses (compact domain, pointwise boundedness, equicontinuity) to shut down (a), (b), and (c) respectively. In Section 2.9 of Lieb-Loss, these three scenarios are called "wanders off to infinity", "goes up the spout", and "oscillates to death" respectively.

Answer by Terry Tao for When must it be sets rather than proper classes, or vice-versa, outside of foundational mathematics?

2013-02-02T17:26:56Z

In my experience in analysis, basically the only place where it is actually important to distinguish sets from proper classes arises when one wishes to invoke Zorn's lemma to locate a maximal object in some non-empty partially ordered set $X$ in which all chains are bounded (e.g. to create a maximal proper subspace, a maximal filter, a maximally defined bounded linear functional, etc.). Here it is crucial that $X$ is "small" enough to be an actual set (e.g. it is a collection of subsets of some space $V$ that is already known to be a set, or a collection of functions from $V$ to yet another set). For instance, one cannot use Zorn's lemma to construct a maximal set in the class of all sets, or a maximal group in the class of all groups, or a maximal vector space in the class of all vector spaces, despite the fact that in each of these classes, any chain has an upper bound (the direct limit). (Such maximal objects, if they existed, would soon lead to contradictions of the flavour of Russell's paradox or the Burali-Forti paradox; not coincidentally, one of the standard proofs of Zorn's lemma proceeds by contradiction, using the axiom of choice to embed all the ordinals into $X$, which can then be used to set up the Burali-Forti paradox.)

To put it another way: regardless of one's choice of foundations, it is clearly mathematically desirable to be able to easily locate maximal objects of various types; but it is obviously also desirable for the existence of such maximal objects to not lead (or mislead) one into paradoxes of Russell or Burali-Forti type. ZFC, with Zorn's lemma on one hand and the set/class distinction on the other, manages to achieve both of these objectives simultaneously. Presumably, many other choices of foundations (particularly those which are essentially equivalent to ZFC in a logical sense) can also achieve both objectives at once, but I usually don't see these points emphasised when such alternative foundations are presented in the literature.

Answer by Terry Tao for Prove an inequality related to moments

2013-01-12T22:58:14Z

As observed in a (now deleted) previous comment, the exponent of $\|\alpha\|_2$ should be $2k$ instead of $2$ for homogeneity reasons.

If the $\varepsilon_i$ are symmetric, then this can be proven by a variant of the exponential moment generating function method used to prove Khintchine's inequality. Indeed, if we normalise ${\bf E} \varepsilon_i^{2k}$ to be 1, then from Holder's inequality we see that ${\bf E} \varepsilon_i^j$ vanishes for odd $j$ and is bounded by $1$ for even $j$ up to $2k$. In particular, the exponential moment generating function

$$ {\bf E} \exp( t \varepsilon_i ) = \sum_{j=0}^\infty \frac{t^j}{j!} {\bf E} \varepsilon_i^j$$

is dominated by $\cosh( t^2 )$ in the sense that the coefficients of the former power series up to $t^{2k}$ are bounded in magnitude by those of the latter. $\cos(t^2)$ is dominated in turn by $\exp(t^2/2)$. Since

$$ {\bf E} \exp( t \varepsilon ) = \prod_{i=1}^n {\bf E} \exp(\alpha_i t \varepsilon_i )$$

we conclude that ${\bf E} \exp( t \varepsilon )$ is dominated by $\exp( \|\alpha\|_2^2 t^2 / 2)$. Extracting the $t^{2k}$ coefficient gives the claim.

The situation seems to be more subtle in the non-symmetric case; there does not seem to be a similarly simple argument (though one can certainly obtain a bound with $(2k-1)!!$ replaced by some weaker constant $C_k$ depending on $k$). It might be that the authors overlooked or neglected to mention a symmetry hypothesis when using this result.

Answer by Terry Tao for Distribution of 1-norm for Gaussian Unitary Ensemble

2009-10-27T04:02:09Z

Let's normalise the variance of the entries to be $1$. Then GUE asymptotically obeys the semicircular law, i.e., the eigenvalues (which equal the singular values, as GUE is Hermitian), after dividing by $\sqrt{n}$, are distributed according to the law $\frac{1}{2 \pi} (4 - x^2)^{1/2}_+ dx$. So the Schatten $1$-norm (Ky Fan norm) should asymptotically equal $\sqrt{n}$ times n times the integral

\begin{equation*} \int \frac{|x|}{2 \pi} (4 - x^2)^{1/2}_+ dx, \end{equation*}

which Wolfram alpha tells me is $8/3 \pi$. So the answer is $n^{3/2} ( 8 / 3 \pi + o(1) )$ with probability $1-o(1)$. Using an explicit convergence rate for GUE, one can probably replace the $o(1)$ with $O(n^{-c})$ for some explicit constant $c>0$.

Getting the variance may be within current technology - it's some integral of two-point correlations of GUE, which are known - but somewhat tedious. Higher moments should also (in principle) be computable. My guess is that the limiting distribution will be asymptotically gaussian, but I might be wrong about this (the central limit theorem doesn't apply directly because the eigenvalues are correlated with each other).

Answer by Terry Tao for An algebra of "integrals"

2012-12-08T22:48:48Z

Property (2) gives $T(1) = T(1)+a$ for any real $a$, which is not solvable in any real algebra (or vector space) $A$. Property (3) leads to a similar issue as it implies that $T(1) = aT(1)$ for all $a>0$.

Note that many common ways of evaluating divergent sums and integrals (e.g. zeta function regularisation) do not actually obey (2) or (3). For instance, the famous identity $1 + 2 + 3 + \ldots = -1/12$, which is valid if the LHS is summed using zeta function regularisation, is inconsistent with basic axioms such as (2), as discussed in this blog post of mine. Also, none of these methods are able to sum all divergent series (or integrate all non absolutely integrable functions). In view of this, I doubt that an axiomatic approach that assumes that all integrals can be integrated is the most natural way to proceed here.

ADDED LATER: Using enough abstract nonsense, one can integrate arbitrary functions, but in a rather useless way. For instance, using nonstandard analysis, one can map $f \in C^\infty({\bf R})$ to the nonstandard real number $\int_0^N f(x)\ dx \in {}^* {\bf R}$ for some fixed unbounded real number $N$, and this will be a perfectly well defined additive homomorphism. If one quotients out the infinitesimals $o({\bf R}) := \{ x \in {}^* {\bf R}: x = o(1) \}$ from ${}^* {\bf R}$, one in fact gets a real-linear map that obeys property (1) (if one identifies ${\bf R}$ with a subspace of ${}^* {\bf R}/o({\bf R})$ in the usual manner), but not (2) or (3). But I'm not sure one can do anything particularly interesting with this construction.

Is there an algebraic geometry analogue of the closed graph theorem?

2012-11-19T19:14:30Z

In functional analysis, the closed graph theorem asserts that if a linear map $T: X \to Y$ between two Banach spaces $X, Y$ has a closed graph $S := \{ (x,Tx): x \in X \}$, then the map is continuous. Thus, it gives a criterion for regularity of a map in terms of regularity of the graph of that map.

I am curious as to whether there is any analogous statement in algebraic geometry. The naive formulation would be: if $T: X \to Y$ was a function (in the set-theoretic sense) between algebraic varieties $X, Y$ over an algebraically closed field $k$ whose graph $S := \{ (x,Tx): x \in X \}$ was also an algebraic variety, then $T$ would be a regular map. (Here I will be vague as to whether I want varieties to be affine, projective, quasiprojective, or abstract.) But this is false, even in characteristic zero: for instance, the coordinate function $(t^2,t^3) \mapsto t$ from the cuspidal curve $\{ (t^2,t^3): t \in k \}$ to $k$ has a graph which is an algebraic variety, but is not a regular map (it is not given by a rational function in a neighbourhood of the origin). In characteristic $p$, the inverse of the Frobenius map $x \mapsto x^p$ provides another counterexample. Somehow the difficulty is that regular functions in $S$ need not come from pullback from regular functions in $X$, even though the vertical line test suggests that such maps should be "degree 1" in some sense.

Still, I feel like there should be some positive statement to be made here, though I was not able to find one after searching through a few algebraic geometry texts. For instance, if one demands that $X, Y, S$ are all smooth and that the field has characteristic zero, does the claim now hold? Ideally, I would like to only have conditions on the varieties $X,Y,S$ and not on the various maps between these varieties; for instance, I would prefer not to have to assume that the projection map from $S$ to $X$ is finite (though perhaps this is automatic?).

Answer by Terry Tao for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T10:22:08Z

There are examples (possibly due to Hecke?) of zeta-like functions which obey almost all of the known properties of the Riemann zeta function, such as the functional equation, Euler product, and asymptotics at infinity, but which have nontrivial zeroes off the critical line. This strongly indicates that one cannot hope to prove the Riemann hypothesis purely by complex analytic methods; at some point, one needs to use something more about the integers than just the fundamental theorem of arithmetic (encoded here as the Euler product), the Poisson summation formula (encoded here as the functional equation), and asymptotic distribution in the reals (encoded here as asymptotics of zeta).

In a related spirit, there are examples (due to Diamond, Montgomery, and Vorhauer) of Beurling integers (generated by a set of Beurling primes, which have asymptotic distribution similar to that of the rational integers) whose zeta function either has non-trivial zeroes or fails to be analytically continued beyond the classical zero-free region. Admittedly this example does not have the functional equation, but it does seem to indicate that multiplicative number theory methods alone are insufficient to resolve the Riemann hypothesis.

EDIT: It turns out that my first paragraph here is based on outdated information. It is currently possible that all functions in the Selberg class (whose members obey all the axioms above, in addition to the Ramanujan conjecture) could obey the RH. I don't know though if anyone is seriously proposing that this much more general conjecture is the right way to attack RH and its relatives, though.

An etale version of the van Kampen theorem

2012-10-24T05:26:39Z

Let $V$ be a smooth connected algebraic variety over an algebraically closed field $k$. Let $W_1, W_2$ be closed subvarieties of $V$ of positive codimension whose intersection $W_1 \cap W_2$ has codimension at least 2, and let $p$ be a point in $V \backslash (W_1 \cup W_2)$. Then we can form the four etale fundamental groups

$$ \pi_1( V, p ), \pi_1(V \backslash W_1, p), \pi_1(V \backslash W_2, p ), \pi_1(V \backslash (W_1 \cup W_2), p ).$$

There are canonical surjective homomorphisms from $\pi_1(V \backslash W_1, p)$ and $\pi_1(V \backslash W_2, p)$ to $\pi_1(V, p)$, and from $\pi_1(V \backslash (W_1 \cup W_2),p)$ to $\pi_1(V \backslash W_1, p)$ and $\pi_1(V \backslash W_2, p)$, forming a commuting square. (The surjectivity comes from the fact that a connected finite etale cover of a smooth variety remains connected even if one removes a positive codimension piece from the base.) So there is a canonical homomorphism from $\pi_1(V \backslash (W_1 \cup W_2),p)$ to the fibre product $\pi_1(V \backslash W_1, p) \times_{\pi_1(V,p)} \pi_1(V \backslash W_2,p)$.

My question is: is this latter homomorphism necessarily surjective also?

In the case when $k$ has characteristic zero, I believe I can deduce this from the topological van Kampen theorem, after first using the Riemann existence theorem to describe the etale fundamental group as the profinite completion of the topological fundamental group (after passing to a complex model). In the positive characteristic case, it seems to boil down (if I understand the etale fundamental group construction correctly) to verifying the following fact: if one has two finite etale covers of $V \backslash W_1$ and $V \backslash W_2$ respectively that become isomorphic on restriction to $V \backslash (W_1 \cup W_2)$, then they can be "glued" together to create a finite etale cover of $V$ (or of $V \backslash (W_1 \cap W_2)$). By reasoning in analogy with the topological case, this seems very reasonable to me, but I had trouble verifying it rigorously (I could glue together the covers as a prevariety, but then I couldn't establish separability to make the cover a variety again).

Answer by Terry Tao for Believing the Conjectures

2012-10-25T16:49:45Z

In number theory, I would say that the counterpart of the "Maximise" principle is the "Local to global principle": if there is no local obstruction to solvability of some number-theoretic problem (e.g. solving a Diophantine equation), then there is no global obstruction either. In the case of Diophantine equations, this becomes the Hasse principle. In the case of patterns in the primes, this leads to the prime tuples conjecture and its generalisations. And so forth. (But bear in mind that this principle sometimes fails, due to non-obvious algebraic structure beyond the obvious "local" ones.)

EDIT: The Riemann zeta function (and other L-functions) also exhibit the "maximise" principle, a phenomenon known as zeta function universality. (But it may well be that whimsical identity fails; as pointed out in comments below, Selberg conjectured that standard axioms such as Euler product, analytic continuation, functional equation, and the Ramanujan conjecture may, when combined, become just strong enough to describe the class of all known L-functions without introducing any really exotic ones (and in particular, avoiding the artificial examples of "fake" L-functions which do bad things such as violate RH).)

Answer by Terry Tao for Believing the Conjectures

2012-10-25T17:03:43Z

In algebraic geometry, I would say that the counterpart of the "reflection" principle is the Lefschetz principle, as discussed in this previous MathOverflow question: if something is solvable in a "big" field, then it is also solvable in a "small" field.

As for the maximise principle in algebraic geometry, perhaps Ravi Vakil's "Murphy's law in algebraic geometry" qualifies.

Non-enumerative proof that there are many derangements?

2012-01-19T17:38:18Z

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle tells us that out of all the $n!$ permutations, a proportion $1/e + o(1)$ of them will be derangements. Indeed, by computing moments (or factorial moments) or using generating function methods, one can establish the stronger result that the number of fixed points in a random permutation is asymptotically distributed according to a Poisson process of intensity 1.

In particular, we have:

Corollary: the proportion of permutations that are derangements is bounded away from zero in the limit $n \to \infty$.

My (somewhat vague) question is whether there is a "non-enumerative" proof of this corollary that does not rely so much on exact combinatorial formulae. For instance, a proof using the Lovasz Local Lemma would qualify, although after playing with that lemma for a while I concluded that there was not quite enough independence in the problem to make that lemma useful for this problem.

Ideally, the non-enumerative proof should have a robust, "analytic" nature to it, so that it would be applicable to other situations in which one wants to lower bound the probability that a large number of weakly correlated, individually unlikely events do not happen (much in the spirit of the local lemma). My original motivation, actually, was to find a non-enumerative proof of a strengthening of the above corollary, namely that given $l$ permutations $\pi_1,\ldots,\pi_l: \{1,\ldots,n\} \to \{1,\ldots,n\}$ chosen uniformly and independently at random, where $l$ is fixed and $n$ is large, the probability that these $l$ permutations form a $2l$-regular graph is bounded away from zero in the limit $n \to \infty$. There is a standard argument (which I found in Bollobas's book) that establishes this fact by the moment method (basically, showing that the number of repeated edges or loops is distributed according to a Poisson process), but I consider this an enumerative proof as it requires a precise computation of the main term in the moment expansion.

Answer by Terry Tao for approximate uncertainty principle for finite abelian groups

2012-10-02T20:36:57Z

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can obtain an analogous result in the Fourier setting and give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

ADDED LATER: Actually, on thinking about it a bit more, the RIP is probably too strong a property for this purpose (it creates a set S that becomes a counterexample for all sparse T, whereas for your problem it would suffice to find a different counterexample S for each sparse T). The situation is then a bit closer to my original paper with Candes and Romberg which only needed an oversampling of order $\log |G|$ or so, though we didn't phrase our analysis in an easily portable form and one would have to look through the argument in detail to check if the bounds there indeed give a negative answer to your question for $\varepsilon < c/\log |G|$. I still don't know how to get rid of the final logarithm, though.

Comment by Terry Tao

2013-05-28T16:43:46Z

This (very early!) paper of Soundararajan ams.org/mathscinet-getitem?mr=1207502 shows that there are $O( \log x / (\log \log x)^2)$ primes of the form $1^1 + \ldots + n^n$ less than $x$. This doesn't directly help with the problem though...

Comment by Terry Tao

2013-05-27T22:41:24Z

At the level of correspondences between finite subsets of finite fields or Z, see this paper of Vu-Wood-Wood arxiv.org/abs/0711.4407 for transferring from C to large finite fields, and this paper of Grosu arxiv.org/abs/1303.2363 for the converse direction.

Comment by Terry Tao

2013-05-23T20:39:36Z

@Andre: Oops! I mis-stated Theorem 3, I replaced it with what is (hopefully) a corrected version.

Comment by Terry Tao

2013-05-23T16:37:31Z

Intuitively, the reason for the saving comes from the fact that it is known (from zero density estimates) that only a tiny fraction of the zeroes of zeta can have real part anywhere close to $\alpha$, so their net contribution to the explicit formula $\psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} + \ldots$ is small enough that their portion of sum $\sum_\rho 1/\rho$ is absolutely convergent, thus producing no logarithmic factor.

Comment by Terry Tao

2013-05-21T02:06:36Z

If one wishes to inspect the manuscript carefully, I would focus attention on Lemma 7.1, as this is a crucial lemma whose proof is extremely sketchy, to put it mildly.

Comment by Terry Tao

2013-05-20T01:17:19Z

Correction: the transfer argument only restricts to those primes p for which the p-Sylow group is non-cyclic rather than non-abelian. (This is because one needs cyclicity, not abelianness, to ensure that the lifted p-Sylow group in $\tilde G$ remains abelian.)

Comment by Terry Tao

2013-05-19T23:59:11Z

... so I guess that if we could explain why Sylow groups of finite simple groups tended to be abelian (with some notable exceptions, e.g. p-Sylow subgroups of a finite simple group of Lie type in characteristic p), this would be a partial explanation of the small Schur multiplier phenomenon.

Comment by Terry Tao

2013-05-19T23:58:05Z

@Agol: one easy application of transfer (e.g. Theorem 5.3 of Isaacs' "finite group theory") is that the order of the Schur multiplier can only be divisible by p when the p-Sylow group of G is non-abelian. (Otherwise, take a p-fold cover $\tilde G$ of $G$, and lift an abelian $p$-Sylow group of $G$ to the cover (which will also be an abelian $p$-Sylow group of $\tilde G$), then the transfer homomorphism from $\tilde G$ to $H$ is non-trivial, as can be seen by computing this transfer map on a central element of $\tilde G$ of order $p$.) (cont)

Comment by Terry Tao

2013-05-16T15:41:02Z

This question sounds like it should be covered by the literature on Fourier-based edge detection, see e.g. jstor.org/stable/27642530

Comment by Terry Tao

2013-05-14T20:30:27Z

Vinogradov's theorem already suffices for this (but that theorem in turn relies on the prime number theorem, which certainly is stronger than Euclid's theorem). In any case Helfgott's argument uses effective estimates on the number of primes less than x which also gives Euclid's theorem.

Comment by Terry Tao

2013-05-06T17:02:06Z

Perhaps "perpendicular to" should be replaced by "perpendicular to all but"?

Comment by Terry Tao

2013-05-02T22:30:02Z

Section 2 of Thurston's article arxiv.org/abs/math/9404236 is relevant here. There are actually a large number of subtly different ways to profitably think about the notion of differentiation, and one will have to internalise several of them before one really gets a feel for the concept.

Comment by Terry Tao

2013-04-18T04:31:16Z

I find it useful to distinguish between pre-rigorous thinking, rigorous thinking, and post-rigorous thinking (see my essay on this at terrytao.wordpress.com/career-advice/… ). It is desirable to transition from a rigorous mindset to a post-rigorous one, but it is not desirable to transition from a rigorous mindset to a pre-rigorous one.

Comment by Terry Tao

2013-04-18T04:24:41Z

In mathoverflow.net/questions/105438 the explicit example of $f(x) := \sin^2(1/x) e^{-1/x} + e^{-2/x}$ (for $x>0$) and $f(x) := 0$ (for $x \leq 0$) is given for a smooth function vanishing to infinite order at the origin, such that the square root of $f$ fails to be smooth at the origin.

Comment by Terry Tao

2013-04-18T04:17:50Z

For what it's worth, I have a writeup of the Joris argument at math.ucla.edu/~tao/preprints/Expository/…