Friday, December 27, 2019
Behaviour of conjugacy by reduction modulo integers
Almost the same holds if and are only conjugate by , except for a few exceptions: we just need to take care to reduce the relation modulo integers that are coprime to the denominators of the coefficients of or of .
I was quite surprised at first to learn that the converse assertion is false. There are matrices and in whose images modulo every integer are conjugate, but which are not conjugate by a matrix in .
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
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 and have integer coefficients, their determinant is , hence they belong to . They also have the same trace, hence the same characteristic polynomial, which is . The discriminant of this polynomial is . This implies that their complex eigenvalues are distinct, hence these matrices are diagonalizable over , and are conjugate over .
In the same way, we see that they remain conjugate modulo every prime number
that does not divide the discriminant. Modulo and , we check that both matrices become
conjugate to , while they become conjugate to modulo .
It is a bit more delicate to prove that if we reduce modulo any integer , then and become conjugate under . Stebe's argument runs in two steps.
He first computes the set of matrices that conjugate to , namely he solves the equation . The answer is given by
Moreover, one has
Consequently, to prove that and are conjugate in , it suffices to find such that .
To prove that they are conjugate by , we need to find such that , and if we agree to be content with a conjugacy by , then solutions of are also admissible.
Let us first start with the equations modulo . By the Chinese remainder theorem, we may assume that is a power of a prime number . Now, if , we can take and such that . If , we take and we solve for , which is possible since is a square, and it is easy, by induction (anyway, this is an instance of Hensel's lemma), to produce modulo such that and .
On the other hand, the equation has no solutions in integers.
The case of is easy by reduction modulo : it becomes , which has no solution since and is not a square modulo .
The case of is rather more difficult. Stebe treats it by reducing to the Pell equation and shows by analysing the minimal solution to this Pell equation that is divisible by , which is incompatible with the initial equation.
From a more elaborate point of view, is a smooth scheme over that violates the integral Hasse principle. In fact, is a torsor under the centralizer of , 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 n≥1, the nth cyclotomic polynomial Φn is the monic polynomial whose complex roots are the primitive nth roots of unity. A priori, this is a polynomial with complex coefficients, but since every nth root of unity is a primitive dth root of unity, for a unique divisor d of n, one has the relation
Tn−1=d∣n∏Φd(T),
which implies, by induction and euclidean divisions, that Φn∈Z[T] for every n.
The degree of the polynomial Φn is ϕ(n), the Euler indicator, number of units in Z/nZ, or number of integers in {0,1,…,n−1} which are prime to n.
The goal of this note is to explain a few proofs that these polynomials are irreducible in Q[T] — or equivalently, in view of Gauss's lemma, in Z[T]. This also amounts to saying that deg(Φn)=ϕ(n) or that the cyclotomic extension has degree ϕ(n), or that the canonical group homomorphism from the Galois group of Q(ζn) to (Z/nZ)× is an isomorphism.
1. The case where n=p is a prime number.
One has Tp−1=(T−1)(Tp+1+⋯+1), hence Φp=Tp−1+⋯+1. If one reduces it modulo p, one finds Φp(T)≡(T−1)p−1, because (T−1)Φp(T)=Tp−1≡(T−1)p. Moreover, Φp(1)=p is not a multiple of p2. By the Eisenstein criterion (after a change of variables T=1+U, if one prefers), the polynomial Φp is irreducible.
This argument also works when n=pe is a power of a prime number. Indeed, since a complex number α is a primitive peth root of unity if and only if αpe−1 is a primitive pth root of unity, one has Φpe=Φp(Tpe−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) is totally ramified at p, of ramification index p−1.
Consequently, it must have degree p−1. More generally, it will prove that Φp is irreducible over the field Qp of p-adic numbers, or even over any unramified extension of it, or even over any algebraic extension of Qp for which the ramification index is prime to p−1.
2. The classical proof
Let us explain a proof that works for all integer n. Let α be a primitive nth root of unity, and let P∈Z[T] be its minimal polynomial — one has P∣Φn in Z[T]. Let (A priori, the divisibility is in Q[T], but Gauss's lemma implies that it holds in Z[T] as well.) Fix a polynomial Q∈Z[T] such that Φn=PQ.
By euclidean division, one sees that the set Z[α] of complex numbers of the form S(α), for S∈Z[T], is a free abelian group of rank deg(P), with basis 1,α,…,αdeg(P)−1.
Let p be a prime number which does not divide n. By Fermat's little theorem, one has P(T)p≡P(Tp)(modp), so that there exists P1∈Z[T] such that P(X)p−P(Xp)=pP1(T). This implies that P(αp)=pP1(α)∈pZ[α].
Since p is prime to n, αp is a primitive nth root of unity, hence Φn(αp)=0. Assume that P(αp)=0. Then one has Q(αp)=0. Differentiating the equality Φn=PQ, one gets nTn=TΦn′(T)=TP′Q+TPQ′; let us evaluate this at αp, we obtain n=αpP(αp)Q′(αp)=pαpP1(αp)Q′(αp). In other words, n∈pZ[α], which is absurd because n does not divide p. Consequently, P(αp)=0, and P is also the minimal polynomial of αp.
By induction, one has P(αm)=0 for every integer m which is prime to n. All primitive nth roots of unity are roots of P and deg(P)=ϕ(n)=deg(Φn). This shows that P=Φn.
Comment. — Since this proof considers prime numbers p which do not divide n, it makes implicit use of the fact that the cyclotomic extension is unramified away from primes dividing n. The differentiation that appears in the proof is a way of proving this non-ramification: if P(αp) is zero modulo p, 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, α being a primitive nth root of unity and P∈Z[T] being its minimal polynomial.
Let us consider, when k varies, the elements P(αk) of Z[α]. There are finitely many of them, since this sequence is n-periodic, so that they can be written as finitely polynomials of degree <deg(P) in α. Let A be an upper-bound for their coefficients. If p is a prime number, we have P(αp)∈pZ[α] (by an already given argument). This implies P(αp)=0 if p>A.
By induction, one has P(αm)=0 for any integer m whose prime factors are all >A.
One the other hand, if m is an integer prime to n and P is the product of all prime number p such that p≤A and p does not divide m, then m′=m+nP is another integer all of which prime factors are >A. (Indeed, if p≤A, then either p∣m in which case p∤nP so that then p∤m′, or p∤m in which case p∣nP so that p∤m′.) Since m′≡m(modn), one has P(αm)=P(αm′)=0.
This shows that all primitive nth roots of unity are roots of P, hence P=Φ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 Kn contains, as subextension, the cyclotomic extensions Kpe, where n=∏piei is the decomposition of n has a product of powers of prime numbers. By the first case, Kpe has degree ϕ(pe)=pe−1(p−1) over Q. To prove that Φ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). Over this field, the polynomials Φ4=T2+1 and Φ3=T2+T+1 are both
irreducible (because they have degree 2 and no root). However
Φ12=T4−T2+1=(T2+1)2−3T2=(T2−3T+1)(T2+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 m and n be integers and let d be their gcd. Then Km∩Kn=Kd.
This is an application of Galois theory (and the result holds for every ground field as soon as its characteristic does not divide m and n). Let M be the least common multiple of m and n. One has KN=Km⋅Kn, and the cyclotomic character furnishes a group morphism Gal(KN/Q)→(Z/NZ)×. The Galois groups Gal(KN/Km) and Gal(KN/Kn) corresponding to the subfields Km and Kn are the kernels of the composition of the cyclotomic character with the projections to (Z/mZ)× and (Z/nZ)×, 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)×.
Sunday, May 19, 2019
Designs, Skolem sequences, and partitions of integers

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,…,2n in n pairs (a1,b1),…,(an,bn) such that the differences are all different, namely bi−ai=i for i∈{1,…,r}. One can put it differently: write a sequence of 2n integers, where each of the integers from 1 to n appear exactly twice, the two 1s being at distance 1, the two 2s at distance 2, etc.
For example, 4,2,3,2,4,3,1,1 is a Skolem sequence of length n, corresponding to the pairs (7,8),(2,4),(3,6),(1,5).
![]() |
Le jeu des cavaliers (photo V. Pantaloni) |
There is a basic necessary and sufficient condition for such a sequence to exist, namely n has to be congruent to 0 or 1 modulo 4. The proof of necessity is easy (attributed by Skolem to Bang): one has ∑i=1n(bi−ai)=n(n+1)/2, and ∑i=1n(bi+ai)=2n(2n+1)/2, so that ∑i=1nbi=n(n+1)/4+2n(2n+1)/2=n(5n+3)/4. If n is even, this forces n≡0(mod4), while if n is odd, this forces 5n+3≡0(mod4), hence n≡1(mod4). 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 S is the datum of triplets of elements of S such that each pair of two elements of S appears exactly once. In other words, they are a (3,2,1)-design on S — a (m,p,q)-design on a set S being a family of m-subsets of S such that each q-subset appears in exactly p 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 S 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 s of elements of S be congruent to 1 or 3 modulo 6. Indeed, there are s(s−1)/2 pairs of elements of S, and each 3-subset of the triple system features 3 such pairs, so that there are N=s(s−1)/6 triples. On the other hand, each element of S appears exactly 3N/s times, so that (s−1)/2 is an integer. So s has to be odd, and either 3 divides s (in which case s≡3(mod6)) or s≡1(mod6).
And Skolem's observation is that a family of n pairs (ai,bi) as above furnishes a triple system on the set S=Z/(6n+1)Z, namely the triples (i,i+j,i+bj+n) where 1≤i,j≤n, thus constructing Steiner triple systems on a set whose cardinality 6n+1, when n≡0,1(mod4).
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 and β>1 be irrational real numbers such that α−1+β−1=1. Then each strictly positive integer can be written either as ⌊αn⌋, or ⌊βn⌋ for some integer n≥1, but not of both forms.
First of all, assume N=⌊αn⌋=⌊βm⌋. Using that α,β are irrational, we thus write N<αn<N+1 and N<βm<N+1. Dividing these inequalities by α and β and adding them, we get N<n+m<N+1, since α−1+β−1=1. This proves that any given integer can be written only of one of those two forms.
Since α−1+β−1=1, one of α,β has to be <2. Assume that 1<α<2. The integers of the form ⌊αn⌋ form a strictly increasing sequence, and we want to show that any integer it avoids can be written ⌊βm⌋.
Set γ=α−1, so that β=α/(α−1)=1+1/γ.
For every integer, we have ⌊α(n+1)⌋=⌊αn⌋+1 or ⌊α(n+1)⌋=⌊αn⌋+2, so that if ⌊αn⌋+1 is avoided, one has ⌊α(n+1)⌋=⌊αn⌋+2.
Then, ⌊αn⌋=n+⌊γn⌋=n+k−1, where k=1+⌊γn⌋. The inequalities k−1<γn<k imply k/γ−1/γ<n<k/γ. Moreover, ⌊α(n+1)⌋=n+1+⌊γ(n+1)⌋=n+k+1, so that k+1<γ(n+1)<k+2, hence n>k/γ+1/γ−1>k/γ−1. This proves that n=⌊k/γ⌋. Then, ⌊kβ⌋=k+⌊k/γ⌋=k+n=⌊αn⌋+1.