Friday, December 27, 2019

Behaviour of conjugacy by reduction modulo integers

Let AA and BMn(Z)B\in\mathrm{M}_n(\mathbf Z) be two square matrices with integer coefficients. Assume that they are conjugate by GLn(Z)\mathrm{GL}_n(\mathbf Z), namely, that there exists a matrix PGLn(Z)P\in\mathrm{GL}_n(\mathbf Z) such that B=P1APB=P^{-1}AP. Then we can reduce this relation modulo every integer d2d\geq 2 and obtain a similar relation between the images of AA and BB in Mn(Z/dZ)\mathrm M_n(\mathbf Z/d\mathbf Z).

Almost the same holds if AA and BB are only conjugate by GLn(Q)\mathrm{GL}_n(\mathbf Q), except for a few exceptions: we just need to take care to reduce the relation modulo integers dd that are coprime to the denominators of the coefficients of PP or of P1P^{-1}.

I was quite surprised at first to learn that the converse assertion is false. There are matrices AA and BB in M2(Z)\mathrm M_2(\mathbf Z) whose images modulo every integer d2d\geq 2 are conjugate, but which are not conjugate by a matrix in GL2(Z)\mathrm{GL}_2(\mathbf Z).

An example is given by Peter Stebe in his paper “Conjugacy separability of groups of integer matrices”, Proc. of the AMS, 32 (1), mars 1972, p. 1—7.
Namely, set
 A=( 188275 121177)=(1117+125111121116+1) A = \begin{pmatrix} 188 & 275 \\ 121 & 177 \end{pmatrix} = \begin{pmatrix} 11\cdot 17+1 & 25\cdot 11 \\ 11^2 & 11\cdot 16+1 \end{pmatrix}
and
\[ B = \begin{pmatrix} 188 & 11 \\ 3025 & 177 \end{pmatrix} =
\begin{pmatrix} 11\cdot 17+1 & 11 \\ 11^2\cdot 25 & 11\cdot 16+1 \end{pmatrix}. \]
These matrices AA and BB have integer coefficients, their determinant is 11, hence they belong to SL2(Z)\mathrm{SL}_2(\mathbf Z). They also have the same trace, hence the same characteristic polynomial, which is T2365T+1T^2-365T+1. The discriminant of this polynomial is 31123673\cdot 11^2\cdot 367. This implies that their complex eigenvalues are distinct, hence these matrices are diagonalizable over C\mathbf C, and are conjugate over C\mathbf C.

In the same way, we see that they remain conjugate modulo every prime number pp
that does not divide the discriminant. Modulo 33 and 1111, we check that both matrices become
conjugate to (1101)\begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}, while they become conjugate to (1101)\begin{pmatrix}-1 & 1 \\ 0 & -1 \end{pmatrix} modulo 367367.

It is a bit more delicate to prove that if we reduce modulo any integer d2d\geq 2, then AA and BB become conjugate under SL2(Z/dZ)\mathrm{SL}_2(\mathbf Z/d\mathbf Z). Stebe's argument runs in two steps.
He first computes the set of matrices VV that conjugate AA to BB, namely he solves the equation VA=BVVA=BV. The answer is given by
 V=V(x,y)=( xy11y25xy). V=V(x,y) = \begin{pmatrix} x & y \\ 11 y & 25 x-y \end{pmatrix}.
Moreover, one has
 det(V(x,y))=25x2xy11y2. \det(V(x,y))=25x^2 - xy -11y^2.
Consequently, to prove that AA and BB are conjugate in SL2(Z/dZ)\mathrm{SL}_2(\mathbf Z/d\mathbf Z), it suffices to find x,yZ/dZx,y\in\mathbf Z/d\mathbf Z such that det(V(x,y))=1(modd)\det(V(x,y))=1 \pmod d.
To prove that they are conjugate by SL2(Z)\mathrm{SL}_2(\mathbf Z), we need to find x,yZx,y\in\mathbf Z such that det(V(x,y))=1\det(V(x,y))=1, and if we agree to be content with a conjugacy by GL2(Z)\mathrm{GL}_2(\mathbf Z), then solutions of det(V(x,y))=1\det(V(x,y))=-1 are also admissible.

Let us first start with the equations modulo dd. By the Chinese remainder theorem, we may assume that d=pmd=p^m is a power of a prime number pp. Now, if p5p\neq 5, we can take y=0y=0 and xx such that 5x=1(modpm)5x=1\pmod {p^m}. If p=5p=5, we take x=0x=0 and we solve yy for 11y2=1(mod5m)-11y^2=1\pmod {5^m}, which is possible since 114(mod5)-11\equiv 4\pmod 5 is a square, and it is easy, by induction (anyway, this is an instance of Hensel's lemma), to produce yy modulo 5m5^m such that y3(mod5)y\equiv 3\pmod 5 and 11y2=1(mod5m)-11y^2=1\pmod{5^m}.

On the other hand, the equation 25x2xy11y2=±125x^2-xy-11y^2=\pm 1 has no solutions in integers.
The case of 1-1 is easy by reduction modulo 33: it becomes x2+2xy+y2=2x^2+2xy+y^2=2, which has no solution since x2+2xy+y2=(x+y)2x^2+2xy+y^2=(x+y)^2 and 22 is not a square modulo 33.
The case of +1+1 is rather more difficult. Stebe treats it by reducing to the Pell equation u2=1101y2+1u^2=1101y^2+1 and shows by analysing the minimal solution to this Pell equation that yy is divisible by 55, which is incompatible with the initial equation.


From a more elaborate point of view, VV is a smooth scheme over Z\mathbf Z that violates the integral Hasse principle. In fact, VV is a torsor under the centralizer of AA, which is a torus, and the obstruction has been studied by Colliot-Thélène and Xu, precisely in this context. However, I did not make the calculations that could use their work to reprove Stebe's theorem.

Tuesday, July 2, 2019

Irreducibility of cyclotomic polynomials

For every integer n1n\geq 1, the nnth cyclotomic polynomial Φn\Phi_n is the monic polynomial whose complex roots are the primitive nnth roots of unity. A priori, this is a polynomial with complex coefficients, but since every nnth root of unity is a primitive ddth root of unity, for a unique divisor dd of nn, one has the relation
Tn1=dnΦd(T), T^n-1 = \prod_{d\mid n} \Phi_d(T),
which implies, by induction and euclidean divisions, that ΦnZ[T]\Phi_n \in \mathbf Z[T] for every nn.
The degree of the polynomial Φn\Phi_n is ϕ(n)\phi(n), the Euler indicator, number of units in Z/nZ\mathbf Z/n\mathbf Z, or number of integers in {0,1,,n1}\{0,1,\dots,n-1\} which are prime to nn.

The goal of this note is to explain a few proofs that these polynomials are irreducible in Q[T]\mathbf Q[T] — or equivalently, in view of Gauss's lemma, in Z[T]\mathbf Z[T]. This also amounts to saying that deg(Φn)=ϕ(n)\deg(\Phi_n)=\phi(n) or that the cyclotomic extension has degree ϕ(n)\phi(n), or that the canonical group homomorphism from the Galois group of Q(ζn)\mathbf Q(\zeta_n) to (Z/nZ)×(\mathbf Z/n\mathbf Z)^\times is an isomorphism.

1. The case where n=pn=p is a prime number.

One has Tp1=(T1)(Tp+1++1)T^p-1=(T-1)(T^{p+1}+\dots+1), hence Φp=Tp1++1\Phi_p=T^{p-1}+\dots+1. If one reduces it modulo pp, one finds Φp(T)(T1)p1\Phi_p(T)\equiv (T-1)^{p-1}, because (T1)Φp(T)=Tp1(T1)p(T-1)\Phi_p(T)=T^p-1\equiv (T-1)^p. Moreover, Φp(1)=p\Phi_p(1)=p is not a multiple of p2p^2. By the Eisenstein criterion (after a change of variables T=1+UT=1+U, if one prefers), the polynomial Φp\Phi_p is irreducible.

This argument also works when n=pen=p^e is a power of a prime number. Indeed, since a complex number α\alpha is a primitive pep^eth root of unity if and only if αpe1\alpha^{p^{e-1}} is a primitive ppth root of unity, one has Φpe=Φp(Tpe1)\Phi_{p^e}= \Phi_p(T^{p^{e-1}}). Then the Eisenstein criterion gives the result.

Comment.From the point of view of algebraic number theory, this proof makes use of the fact that the cyclotomic extension Q(ζp)\mathbf Q(\zeta_p) is totally ramified at pp, of ramification index p1p-1.
Consequently, it must have degree p1p-1. More generally, it will prove that Φp\Phi_p is irreducible over the field Qp\mathbf Q_p of pp-adic numbers, or even over any unramified extension of it, or even over any algebraic extension of Qp\mathbf Q_p for which the ramification index is prime to p1p-1.


2. The classical proof

Let us explain a proof that works for all integer nn. Let α\alpha be a primitive nnth root of unity, and let PZ[T]P\in\mathbf Z[T] be its minimal polynomial — one has PΦnP\mid \Phi_n in Z[T]\mathbf Z[T]. Let (A priori, the divisibility is in Q[T]\mathbf Q[T], but Gauss's lemma implies that it holds in Z[T]\mathbf Z[T] as well.) Fix a polynomial QZ[T]Q\in\mathbf Z[T] such that Φn=PQ\Phi_n=PQ.

By euclidean division, one sees that the set Z[α]\mathbf Z[\alpha] of complex numbers of the form S(α)S(\alpha), for SZ[T]S\in\mathbf Z[T], is a free abelian group of rank deg(P)\deg(P), with basis 1,α,,αdeg(P)11,\alpha,\dots,\alpha^{\deg(P)-1}.

Let pp be a prime number which does not divide nn. By Fermat's little theorem, one has P(T)pP(Tp)(modp)P(T)^p \equiv P(T^p) \pmod p, so that there exists P1Z[T]P_1\in\mathbf Z[T] such that P(X)pP(Xp)=pP1(T)P(X)^p-P(X^p)=pP_1(T). This implies that P(αp)=pP1(α)pZ[α]P(\alpha^p)=p P_1(\alpha)\in p\mathbf Z[\alpha].

Since pp is prime to nn, αp\alpha^p is a primitive nnth root of unity, hence Φn(αp)=0\Phi_n(\alpha^p)=0. Assume that P(αp)0P(\alpha^p)\neq 0. Then one has Q(αp)=0Q(\alpha^p)=0. Differentiating the equality Φn=PQ\Phi_n=PQ, one gets nTn=TΦn(T)=TPQ+TPQnT^{n}=T\Phi'_n(T)=TP'Q+TPQ'; let us evaluate this at αp\alpha_p, we obtain n=αpP(αp)Q(αp)=pαpP1(αp)Q(αp)n=\alpha^p P(\alpha_p) Q'(\alpha^p)=p \alpha^p P^1(\alpha^p)Q'(\alpha^p). In other words, npZ[α]n\in p\mathbf Z[\alpha], which is absurd because nn does not divide pp. Consequently, P(αp)=0P(\alpha^p)=0, and PP is also the minimal polynomial of αp\alpha^p.

By induction, one has P(αm)=0P(\alpha^m)=0 for every integer mm which is prime to nn. All primitive nnth roots of unity are roots of PP and deg(P)=ϕ(n)=deg(Φn)\deg(P)=\phi(n)=\deg(\Phi_n). This shows that P=ΦnP=\Phi_n.

Comment.Since this proof considers prime numbers pp which do not divide nn, it makes implicit use of the fact that the cyclotomic extension is unramified away from primes dividing nn. The differentiation that appears in the proof is a way of proving this non-ramification: if P(αp)P(\alpha^p) is zero modulo pp, it must be zero.

3. Landau's proof

A 1929 paper by Landau gives a variant of this classical proof which I just learnt from Milne's notes on Galois theory and which I find significantly easier.

We start as previously, α\alpha being a primitive nnth root of unity and PZ[T]P\in\mathbf Z[T] being its minimal polynomial.

Let us consider, when kk varies, the elements P(αk)P(\alpha^k) of Z[α]\mathbf Z[\alpha]. There are finitely many of them, since this sequence is nn-periodic, so that they can be written as finitely polynomials of degree <deg(P)<\deg(P) in α\alpha. Let AA be an upper-bound for their coefficients. If pp is a prime number, we have P(αp)pZ[α]P(\alpha^p) \in p\mathbf Z[\alpha] (by an already given argument). This implies P(αp)=0P(\alpha^p)=0 if p>Ap>A.

By induction, one has P(αm)=0P(\alpha^m)=0 for any integer mm whose prime factors are all >A>A.

One the other hand, if mm is an integer prime to nn and PP is the product of all prime number pp such that pAp\leq A and pp does not divide mm, then m=m+nPm'=m+nP is another integer all of which prime factors are >A>A. (Indeed, if pAp\leq A, then either pmp\mid m in which case pnPp\nmid nP so that then pmp\nmid m', or pmp\nmid m in which case pnPp\mid nP so that pmp\nmid m'.) Since mm(modn)m'\equiv m \pmod n, one has P(αm)=P(αm)=0P(\alpha^{m})=P(\alpha^{m'})=0.

This shows that all primitive nnth roots of unity are roots of PP, hence P=ΦnP=\Phi_n.

Comment. —This proof is quite of a mysterious nature to me.

4. Can one use Galois theory to pass from local information to global information?


The cyclotomic extension KnK_n contains, as subextension, the cyclotomic extensions KpeK_{p^e}, where n=piein=\prod p_i^{e_i} is the decomposition of nn has a product of powers of prime numbers. By the first case, KpeK_{p^e} has degree ϕ(pe)=pe1(p1)\phi(p^e)=p^{e-1}(p-1) over Q\mathbf Q. To prove that Φn\Phi_n is irreducible, it would be sufficient to prove that these extensions are linearly disjoint.

This is what I had claimed in a first version of this blog post. Unfortunately, as Olivier Fouquet made me observe (September 26, 2020), this cannot be true without any additional argument that uses the fact that the ground field is the field of rational numbers.

Assume, for example, that the ground field K=Q(3)K=\mathbf Q(\sqrt 3). Over this field, the polynomials  Φ4=T2+1\Phi_4=T^2+1 and Φ3=T2+T+1\Phi_3=T^2+T+1 are both irreducible (because they have degree 2 and no root). However Φ12=T4T2+1=(T2+1)23T2=(T23T+1)(T2+3T+1)\Phi_{12}=T^4-T^2+1=(T^2+1)^2-3T^2=(T^2-\sqrt 3T+1)(T^2+\sqrt 3T+1) is not irreducible.

 
(For consistency, I leave below the lemma that I had used. I have not yet thought about where the mistake lies, nor to how I could correct the statement.)

Unlemma. — Let mm and nn be integers and let dd be their gcd. Then KmKn=KdK_m\cap K_n=K_d.

This is an application of Galois theory (and the result holds for every ground field as soon as its characteristic does not divide mm and nn). Let MM be the least common multiple of mm and nn. One has KN=KmKnK_N=K_m\cdot K_n, and the cyclotomic character furnishes a group morphism Gal(KN/Q)(Z/NZ)×\operatorname{Gal}(K_N/\mathbf Q)\to (\mathbf Z/N\mathbf Z)^\times. The Galois groups Gal(KN/Km)\operatorname{Gal}(K_N/K_m) and Gal(KN/Kn)\operatorname{Gal}(K_N/K_n) corresponding to the subfields KmK_m and KnK_n are the kernels of the composition of the cyclotomic character with the projections to (Z/mZ)×(\mathbf Z/m\mathbf Z)^\times and (Z/nZ)×(\mathbf Z/n\mathbf Z)^\times, and their intersection to the subgroup generated by these two kernels, which is none but the kernel of the composition of the cyclotomic character with the projection to (Z/dZ)×(\mathbf Z/d\mathbf Z)^\times.

Sunday, May 19, 2019

Designs, Skolem sequences, and partitions of integers

Recently, my father offered me the first volume of a graphic novel by Jean-François Kierzkowski and Marek called La suite de Skolem — Skolem's sequences. I knew about the norwegian mathematician Thoralf Skolem for two different reasons (the Löwenheim-Skolem theorem in model theory, and some diophantine equations that Laurent Moret-Bailly put in a more geometric setting — see his series of papers on Problèmes de Skolem), but I had never heared about Skolem sequences.

They appear in his 1957 paper, On certain distributions of integers in pairs with given differences (Math Scand., 5, 57-68).
The question is to put the integers 1,2,,2n1,2,\dots,2n in nn pairs (a1,b1),,(an,bn)(a_1,b_1),\dots,(a_n,b_n) such that the differences are all different, namely biai=ib_i-a_i=i for i{1,,r}i\in\{1,\dots,r\}. One can put it differently: write a sequence of 2n2n integers, where each of the integers from 11 to nn appear exactly twice, the two 11s being at distance 11, the two 22s at distance 22, etc.
For example, 4,2,3,2,4,3,1,14,2,3,2,4,3,1,1 is a Skolem sequence of length nn, corresponding to the pairs (7,8),(2,4),(3,6),(1,5)(7,8), (2,4), (3,6),(1,5).

Le jeu des cavaliers (Jessica Stockholder) — photo V. Pantaloni
Le jeu des cavaliers (photo V. Pantaloni)
The possibility of such sequences has been materialized under the form of a giant sculpture Le jeu des cavaliers by Jessica Stockholder at the Institut des Hautes Études Scientifiques (IHÉS) at Bures sur Yvette.

There is a basic necessary and sufficient condition for such a sequence to exist, namely nn has to be congruent to 00 or 11 modulo 44. The proof of necessity is easy (attributed by Skolem to Bang): one has i=1n(biai)=n(n+1)/2\sum_{i=1}^n(b_i-a_i)=n(n+1)/2, and i=1n(bi+ai)=2n(2n+1)/2\sum_{i=1}^n (b_i+a_i)=2n(2n+1)/2, so that i=1nbi=n(n+1)/4+2n(2n+1)/2=n(5n+3)/4\sum_{i=1}^n b_i=n(n+1)/4+2n(2n+1)/2=n(5n+3)/4. If nn is even, this forces n0(mod4)n\equiv 0 \pmod 4, while if nn is odd, this forces 5n+30(mod4)5n+3\equiv 0\pmod 4, hence n1(mod4)n\equiv 1\pmod 4. The proof of  existence consists in an explicit example of such a sequence, which is written down in Skolem's paper.

Skolem's motivation is only alluded to in that paper, but he explains it a bit further next year. In Some Remarks on the Triple Systems of Steiner, he gives the recipe that furnishes such a system from a Skolem sequence. Steiner triple systems on a set SS is the datum of triplets of elements of SS such that each pair of two elements of SS appears exactly once. In other words, they are a (3,2,1)(3,2,1)-design on SS — a (m,p,q)(m,p,q)-design on a set SS being a family of mm-subsets of SS such that each qq-subset appears in exactly pp of those subsets. Some relatively obvious divisibility conditions can be written down that give a necessary condition for the existence of designs with given parameters, but actual existence is much more difficult. In fact, it has been shown only recently by Peter Keevash that these necessary conditions are sufficient, provided the cardinality of the set SS is large enough, see Gil Kalai's talk Designs exist! at the Bourbaki Seminar.

In the case of Steiner triple systems, the condition is that the number ss of elements of SS be congruent to 11 or 33 modulo 66. Indeed, there are s(s1)/2s(s-1)/2 pairs of elements of SS, and each 3-subset of the triple system features 3 such pairs, so that there are N=s(s1)/6N=s(s-1)/6 triples. On the other hand, each element of SS appears exactly 3N/s3N/s times, so that (s1)/2(s-1)/2 is an integer. So ss has to be odd, and either 33 divides ss (in which case s3(mod6)s\equiv 3\pmod 6) or s1(mod6)s\equiv 1\pmod 6.

And Skolem's observation is that a family of nn pairs (ai,bi)(a_i,b_i) as above furnishes a triple system on the set S=Z/(6n+1)ZS=\mathbf Z/(6n+1)\mathbf Z, namely the triples (i,i+j,i+bj+n)(i,i+j,i+b_j+n) where 1i,jn1\leq i,j\leq n, thus constructing Steiner triple systems on a set whose cardinality 6n+16n+1, when n0,1(mod4)n\equiv 0,1\pmod 4.

My surprise came at the reading of the rest of Skolem's 1957 paper, because I knew the result he then described but had no idea it was due to him. (In fact, it was one of the first homework my math teacher Johan Yebbou gave to us when I was in classes préparatoires.) And since this result is very nice, let me tell you about it.

Theorem.Let α>1\alpha>1 and β>1\beta>1 be irrational real numbers such that α1+β1=1\alpha^{-1}+\beta^{-1}=1. Then each strictly positive integer can be written either as αn\lfloor \alpha n\rfloor, or βn\lfloor \beta n\rfloor for some integer n1n\geq 1, but not of both forms.

First of all, assume N=αn=βmN=\lfloor \alpha n\rfloor=\lfloor \beta m\rfloor. Using that α,β\alpha,\beta are irrational, we thus write N<αn<N+1N< \alpha n<N+1 and N<βm<N+1N<\beta m<N+1. Dividing these inequalities by α\alpha and β\beta and adding them, we get N<n+m<N+1N<n+m<N+1, since α1+β1=1\alpha^{-1}+\beta^{-1}=1. This proves that any given integer can be written only of one of those two forms.

Since α1+β1=1\alpha^{-1}+\beta^{-1}=1, one of α,β\alpha,\beta has to be <2<2. Assume that 1<α<21<\alpha<2. The integers of the form αn\lfloor \alpha n\rfloor form a strictly increasing sequence, and we want to show that any integer it avoids can be written βm\lfloor \beta m\rfloor.

Set γ=α1\gamma=\alpha-1, so that β=α/(α1)=1+1/γ\beta=\alpha/(\alpha-1)=1+1/\gamma

For every integer, we have α(n+1)=αn+1\lfloor \alpha(n+1)\rfloor = \lfloor \alpha n\rfloor + 1 or α(n+1)=αn+2\lfloor \alpha(n+1)\rfloor=\lfloor \alpha n\rfloor+2, so that if αn+1\lfloor \alpha n\rfloor + 1 is avoided, one has α(n+1)=αn+2\lfloor \alpha (n+1)\rfloor=\lfloor\alpha n\rfloor +2.

Then, αn=n+γn=n+k1\lfloor \alpha n\rfloor = n+\lfloor \gamma n\rfloor=n+k-1, where k=1+γnk=1+\lfloor \gamma n\rfloor. The inequalities k1<γn<kk-1<\gamma n <k imply k/γ1/γ<n<k/γk/\gamma - 1/\gamma< n<k/\gamma. Moreover, α(n+1)=n+1+γ(n+1)=n+k+1\lfloor \alpha(n+1)\rfloor=n+1+\lfloor \gamma(n+1)\rfloor=n+k+1, so that k+1<γ(n+1)<k+2k+1<\gamma(n+1)<k+2, hence n>k/γ+1/γ1>k/γ1n>k/\gamma+1/\gamma-1>k/\gamma-1. This proves that n=k/γn=\lfloor k/\gamma\rfloor. Then, kβ=k+k/γ=k+n=αn+1\lfloor k\beta\rfloor=k+\lfloor k/\gamma\rfloor=k+n=\lfloor \alpha n\rfloor +1.