E. Kowalski's blog

Comments on mathematics, mostly.

Archive for the ‘Mathematics’ Category

Symmetric powers and the Chinese restaurant process

leave a comment

Here is a simple but cute computation that makes a good exercise in elementary representation theory with a probabilistic flavor — as usual, it’s probably well-known, but I wasn’t aware of it until doing the exercise myself.

We consider random permutations in the symmetric group S_n, and write \omega_n(\sigma) for the number of cycles in the disjoint cycle representation of \sigma\in S_n. It is a well-known fact (which may be due to Feller) that, viewed as a random variable on S_n (with uniform probability measure), there is a decomposition in law
\omega_n=B_1+\cdots+B_n,
where B_i is a Bernoulli random variable taking value 0 with probability 1-1/i and 1 with probability 1/i.

This decomposition is (in the sources I know) usually proved using the “Chinese Restaurant Process” to describe random permutations (n guests numbered from 1 to n enter a restaurant with circular tables; they successively sit either at the next available space of one of the tables already occupied, or pick a new one, with the same probability; after all n guests are seated, reading the cycles on the occupied tables gives a uniformly distributed element of S_n.) If one is only interested in \sigma_n, then the decomposition above is equivalent to the formula
\mathbf{E}(z^{\omega_n})=\prod_{j=1}^n\Bigl(1-\frac{1}{j}+\frac{z}{j}\Bigr)
for the probability generating function of \omega_n. (This formula comes up in mod-poisson convergence of \sigma_n and in analogies with the Erdös-Kac Theorem, see this blog post).

Here is an algebraic proof of this generating function identity. First, z\mapsto \mathbf{E}(z^{\omega_n}) is a polynomial, so it is enough to prove the formula when z=m is a non-negative integer. We can do this as follows: let V be a vector space of dimension m over \mathbf{C}. Then define W=V^{\otimes n} and view it as a representation space of S_n where the symmetric group permutes the factors in the tensor product. Using the “obvious” basis of W, it is elementary that the character of this representation is the function g\mapsto m^{\sigma_n(g)} on S_n (the matrix representing the action of g is a permutation matrix). Hence, by character theory, \mathbf{E}(m^{\sigma_n}) is the dimension of the S_n-invariant subspace of W. Since the representation is semisimple, this is the dimension of the coinvariant space, which is the n-th symmetric power of V. This in turn is well-known (number of monomials of degree n in m variables), and we get
\mathbf{E}(m^{\omega_n})=\binom{m+n-1}{n}=\prod_{j=1}^n\Bigl(1-\frac{1}{j}+\frac{m}{j}\Bigr),
as claimed!

Written by Kowalski

November 16th, 2016 at 12:21 pm

Posted in Exercise,Mathematics

Update on a bijective challenge

2 comments

A long time ago, I presented in a post a fun property of the family of curves given by the equations
x+1/x+y+1/y=t,
where t is the parameter: if we consider the number (say N_p(t)) of solutions over a finite field with p\geq 3 elements, then we have
N_p(t)=N_p(16/t),
provided t is not in the set \{0, 4, -4\}. This was a fact that Fouvry, Michel and myself found out when working on our paper on algebraic twists of modular forms.

At the time, I knew one proof, based on computations with Magma: the curves above “are” elliptic curves, and Magma found an isogeny between the curves with parameters t and 16/t, which implies that they have the same number of points by elementary properties of elliptic curves over finite fields.

By now, however, I am aware of three other proofs:

  • The most elementary, which motivates this post, was just recently put on arXiv by T. Budzinski and G. Lucchini Arteche; it is based on the methods of Chevalley’s proof of Warning’s theorem: it computes N_p(t) modulo p, proving the desired identity modulo p, and then concludes using upper bounds for the number of solutions, and for its parity, to show that this is sufficient to have the equality as integers.  Interestingly, this proof was found with the help of high-school students participating in the Tournoi Français des Jeunes Mathématiciennes et Mathématiciens. This is a French mathematical contest for high-school students, created by D. Zmiaikou in 2009, which is devised to look much more like a “real” research experience than the Olympiads: groups of students work together with mentors on quite “open-ended” questions, where sometimes the answer is not clear (see for instance the 2016 problems here).
  • A proof using modular functions was found by D. Zywina, who sent it to me shortly after the first post (I have to look for it in my archives…)
  • Maybe the most elegant argument comes by applying a more general result of Deligne and Flicker on local systems of rank 2 on the projective line minus four points with unipotent tame ramification at the four missing points (the first cohomology of the curves provide such a local system, the missing points being 0, 4, -4, \infty). Deligne and Flicker prove (Section 7 of their paper, esp. Prop. 7.6), using a very cute game with products of matrices and invariant theory, that if \mathcal{V} is such a local system and \sigma is any automorphism of the projective line that permutes the four points, then \sigma^*\mathcal{V} is isomorphic to \mathcal{V}.

Not too bad a track record for such a simple-looking question… Whether there is a bijective proof remains open, however!

Written by Kowalski

September 24th, 2016 at 10:47 am

Horizon

leave a comment

The Swiss Science Foundation (SNF in German, FNS in French) publishes a regular magazine that surveys current topics concerning science and research in Switzerland. It often highlights subjects that are unexpected and interesting in all areas of science, from the humanities to forestry, the deterioration of prussian blue in paintings and so on, and does so in its three parallel editions, in English, French and German.

The last issue has a special focus on Open Science in its various forms. For some reason, although there is no discussion of Polymath per se, the editors decided to have a picture of a mathematician working on Polymath as an illustration, and they asked me if they could make such a picture with me, and in fact two of them (the photographer is Valérie Chételat) appear in the magazine. Readers may find it amusing to identify which particular comment of the Polymath 8 blog I am feigning to be studying in those pictures…

Besides (and of greater import than) this, I recommend looking at the illustration pages 6 and 7,

Forest

Forest

which is a remarkably precise computer representation of the 44000 trees in a forest near Baden, each identified and color-coded according to its species… (This is done by the team of M. Schaepman at the University of Zürich).

Written by Kowalski

September 1st, 2016 at 8:30 pm

Jordan blocks

3 comments

Here is yet another definition in mathematics where it seems that conventions vary (almost like the orientation of titles on the spines of books): is a Jordan block an upper-triangular or lower-triangular matrix? In other words, which of the matrices

A_1=\begin{pmatrix}\alpha & 1\\0&\alpha\end{pmatrix},\quad\quad A_2=\begin{pmatrix} \alpha & 0\\1&\alpha\end{pmatrix}

is a Jordan block of size 2 with respect to the eigenvalue \alpha?

I have the vague impression that most elementary textbooks in Germany (I taught linear algebra last year…) use A_1, but for instance Bourbaki (Algèbre, chapitre VII, page 34, définition 3, in the French edition) uses A_2, and so does Lang’s “Algebra”. Is it then a cultural dichotomy (again, like spines of books)?

I have to admit that I tend towards A_2 myself, because I find it much easier to remember a good model for a Jordan block: over the field K, take the vector space V=K[X]/X^nK[X], and consider the linear map u\colon V\to V defined by u(P)=\alpha P+XP. Then the matrix of u with respect to the basis (1,X,\ldots,X^{n-1}) is the Jordan block in its lower-triangular incarnation. The point here (for me) is that passing from n to n+1 is nicely “inductive”: the formula for the linear map u is “independent” of n, and the bases for different n are also nicely meshed. (In other words, if one finds the Jordan normal form using the classification of modules over principal ideal domains, one is likely to prefer the lower-triangular version that “comes out” more naturally…)

Written by Kowalski

August 5th, 2016 at 8:28 pm

Posted in Mathematics

A geometric interpretation of Schinzel’s Hypothesis

3 comments

Schinzel’s “Hypothesis” for primes is (update: actually, not really, see the remark at the end…) the statement that if F is an irreducible polynomial (say monic) in \mathbf{Z}[Y], and if there is no “congruence obstruction”, then the sequence of values F(n) for integers n\geq 1 contains infinitely many primes. More precisely, one expects that the number \pi_F(x) of integers n\leq X such that F(n) is prime satisfies
\pi_F(x)\sim c_F\frac{x}{\log x},
for some (explicitly predicted) constant c_F>0, called sometimes the “singular series”.

Except if F has degree one, this problem is very much open. But it makes sense to translate it to a more geometric setting of polynomials over finite fields, and this leads (as is often the case) to problems that are more tractable. The translation is straightforward: instead of \mathbf{Z}, one considers the ring A=\mathbf{F}_q[X] of polynomials over a finite field \mathbf{F}_q with q elements, instead of F, one considers a polynomial F\in A[Y]=\mathbf{F}_q[X,Y], and then the question is to determine asymptotically how many polynomials f\in A of given degree n\geq 1 are such that F(f)\in A is an irreducible polynomial.

The reason the problem becomes more accessible is that there is an algebraic criterion for a polynomial f with coefficients in a finite field \mathbf{F}_q to be irreducible: if we look at the natural action of the Frobenius automorphism x\mapsto x^q on the set of roots of the polynomial, then f is irreducible if and only if this action “is” a cycle of length \deg(f). This is especially useful for the variant of the Schinzel problem where the size of the finite field is varying, whereas the degree n of the polynomials f remains fixed, since in that case the variation of the action of the Frobenius on the roots of the polynomial is encoded in a group homomorphism from the Galois group of the function field of the parameter space to the symmetric group on n letters. (This principle goes back at least to work of S.D. Cohen on Hilbert’s Irreducibility Theorem).

If we apply this principle in the Schinzel setting, this means that we consider specialized polynomials F(f) for some fixed polynomial F\in A[Y]=\mathbf{F}_q[X][Y], where f runs over polynomials of a fixed degree d\geq 1, but q ranges over powers of a fixed prime. “Generically”, the polynomial F(f) has some fixed degree n, and is squarefree. If we interpret the parameter space X_d geometrically, the content of the previous paragraph is that we have a group homomorphism
\rho\colon \pi_1(X_d)\to \mathfrak{S}_n,
from the fundamental group of X_d to the symmetric group. Then the Chebotarev Density Theorem solves, in principle, the problem of counting the number of irreducible specializations in the large q limit: essentially (omitting the distinction between geometric and arithmetic fundamental groups), the asymptotic proportion of f\in X_d(\mathbf{F}_q) such that F(f) is irreducible converges as q\to+\infty to the proportion, in the image of \rho, of the elements that are n-cycles in \mathfrak{S}_n. If the homomorphism \rho is surjective, then this means that the probability that F(f) is irreducible is about 1/n. This is the expected answer in many cases, because this is also the probability that a random polynomial of degree n is irreducible.

All this has been used by a number of people (including Hall, Pollack, Bary-Soroker, and most successfully Entin). However, there is a nice geometric interpretation that I haven’t seen elsewhere. To see it, we go back to F(f) and the action of Frobenius on its roots that will determine if F(f) is irreducible. A root of F(f) is an element x such that
F(f)(x)=F(x,f(x))=0
where we view F as a two-variable polynomial. In other words, x is the first coordinate of a point (x,f(x)) that belongs to the intersection of the graph of f in the plane, and the plane affine curve S with equation F(x,y)=0. Since the Frobenius will permute these intersection points in the same way that it permutes the roots of F(f), we can interpret the Schinzel Problem, in that context, as asking about the “variation” of this Galois action as f varies and the curve S is fixed.

Schinzel Problem

Schinzel Problem

This point of view immediately suggests some generalizations: there is no reason to work over a finite field (any field will do), the base curve (which is implicitly the affine line where polynomials live) can be changed to another (open) curve U; the point at infinity, where polynomials have their single pole, might also be changed to any effective divisor with support the complement of U in its smooth projective model (e.g., allowing poles at 0 and \infty on the projective line); and S may be any (non-vertical) curve in U\times\mathbf{A}^1. For instance (to see that this generalization is not pointless), take any curve U, and define S=U\times\{0\}. Then the intersection of the graph of a function f on U and S is the set of zeros of f. The problem becomes something like figuring out the “generic” Galois group of the splitting field of this set of zeros. (E.g., the Galois group of a complicated elliptic function defined over \mathbf{Q}…)

In fact this special case was (with different motivation and terminology) considered by Katz in his book “Twisted L-functions and monodromy” (see Chapter 9). Katz shows that if the (fixed) effective divisor used to define the poles of the functions considered has degree \geq 2g+1, where g is the genus of the smooth projective model of U, then the image of Galois is the full symmetric group (his proof is rather nice, using character sums on the Jacobian…)

The general case, on the other hand, does not seem to have been considered before. In the recent note that I’ve written on the subject, I use quite elementary arguments with Lefschetz pencils / Morse-like functions (again inspired by results of Katz and Katz-Rains) to show that in very general conditions, the image of the fundamental group is again the full symmetric group. This gives the asymptotic for this geometric Schinzel problem in this generality over finite fields. (In the classical case, this was essentially done by Entin, though the conditions of applicability are not exactly the same).

I recently gave a talk about this in Berlin, and the slides might be a good introduction to the ideas of the proof for interested readers…

Leibnitz Room

Leibnitz Room

As I mention at the end of those slides, the next step is of course to think about the fixed finite field case, where the degree of the polynomials tends to infinity. This seems, even geometrically, to be quite an interesting problem…

[Update: after I wrote this post, I remembered that in fact the (qualitative) problem of representing primes with one polynomial that I consider here is actually Bunyakowski’s Problem, and that the Schinzel Hypothesis is the qualitative statement for a finite set of polynomials… The quantitative versions of both are usually called the Bateman-Horn conjecture. So my terminology is multiply inaccurate…]

Written by Kowalski

June 5th, 2016 at 12:29 pm

Posted in Mathematics