You are currently browsing the monthly archive for décembre 2014.

Can an integer pretend to be a square and yet not be a square? So let n be an integer which is not a square – can it be a quadratic residue modulo every prime? No. Indeed, suppose n is squarefree (square factors don’t alter the property of being a square or quadratic residue) and write n=p_1\cdots p_k. Suppose none of the p_i is 2 first. We want to find a prime q such that (\frac{n}{q})=\prod (\frac{p_i}{q})=-1. If k=1 (n is prime), it’s easy because of the quadratic reciprocity law: if n=1 [4], (\frac{n}{q})=(\frac{q}{n}) so we just have to find q which is not a square modulo n, which is the case of about the half of the residues so it shouldn’t be too hard. In general, we can even find q=1[4] with (\frac{p_1}{q})=-1 and the Legendre symbol equal to +1 for the other primes: indeed, (\frac{p_i}{q})=(\frac{q}{p_i}) then and it will be +1 if q=1[p_i]. By Chinese remainder theorem, imposing a condition modulo each p_i (q=1[p_i] for i>1 here, and q=a_{p_1}[p_1] for a fixed non-quadratic residue a_{p_1}) and modulo 4 amount to imposing a condition q=b[4n] with b\leq 4n.
And by Dirichlet’s theorem, there exists a prime number in this progression. If n is even (p_1=2, say), we argue similarly except that we must replace the quadratic reciprocity law by
the formula (\frac{2}{q})=(-1)^{\frac{q^2-1}{8}}. Thus we can for instance decide that q=5[8], thus for the odd factors (\frac{p_i}{q})=(\frac{q}{p_i}) and we can ensure these symbols are all 1 by taking a number belonging to suitable classes.

It is not too easy to bound such a q. In the case where n is prime, there is the terribly difficult Vinogradov’s conjecture which states that there should exist a q\leq\sqrt{n} non quadratic residue modulo n. But then you have to find a prime number in the congruence classe q \text{ mod } n. Linnik’s theorem ensures the existence of a prime number \ll n^L for some constant L (5.5 would do but it’s quite big, 2 is conjectured to work as well).

However, it’s a classical question in sieve theory (see an exercise in Tenenbaum’s book, chapter 4 or in Luca-de Koninck chapter 12) to ask how many n\leq x there are such that n is a quadratic residue modulo every prime p\leq\sqrt{x}. The answer is: between \lfloor\sqrt{x}\rfloor (the number of squares) and C\sqrt{x} for some constant C. The necessary restriction to p\leq\sqrt{x} is a feature of the large sieve. So there are certainly numbers who « pretend to be squares » but which are not.

This post comes directly from a talk of Elisa Covato at the seminar of the the PhD students of Bristol.

Definition of the prime graph of a group
Let G be a finite group. Let \pi (G) be the set of prime factors of \lvert G\rvert. The prime graph \Gamma(G) has \Pi(G) as vertex set and two primes r,s are neighbours if there exists g\in G whose order is multiple of rs.

Note that Lagrange’s theorem implies that every order of an element of G is a divisor of \lvert G\rvert, hence is a product of elements of \Pi(G) ; and that thanks to Cauchy, we know that every element of \Pi(G) is the order of somebody. But a product rs of elements of this set is not always the order of somebody, not even a divisor of the order of somebody.

In the case of the unique abelian group of order p_1\cdots p_k where the p_i are pairwise distinct primes, the prime graph is the complete graph.

In the case of \mathcal{A}_{10}, we have \Pi(G)=\{2,3,5,7\}. And there’s somebody of order 6, for instance (123)(45)(67) ; of order 10, for instance (12345)(67)(89). There’s also somebody of order 15, for example (12345)(678). There’s somebody of order 21, (1234567)(89A) (où A=10). But no one has order 14 nor 35. Indeed, recall that the order of a permutation is the ppcm of the orders of the cycles in its decomposition in a product of disjoint cycles ; and if 14 is the ppcm of some numbers, then 2 and 7 ; and in order to make an even permutation with at least one cycle of length 2 and at least one of length 7, you need 11 elements. For 5\times 7, you need 12 elements.

A lot of information about G is encoded in the prime graph but not every thing.

Recognition problem
Can a group G be uniquely determined by its prime graph (at least among a more or less restricted class of groups) ? So if \Gamma (G_1)=\Gamma(G_2) are the groups isomorphic ? Be careful, when I say that the graphs are equal, I mean it ! Not only isomorphic ! Otherwise for instance all the \mathbb{Z}_P have the same graph, a single vertex.

The answer is rather no in general.

Theorem (Lucchini, Morigi, Shumyatski)
Let G be a finit group. Then there exists H\leq G which is 3-generated and has the same prime graph.

Of course, the theorem doesn’t claim that H\neq G so it’s only interesting when G is not himself 3-generated (generated by a set of at most 3 elements). Moreover, if G is simple, it is even 2-generated (if you believe in the classification of finite simple groups).

Problem : let G be finite and simple. Determine (H,H) with H\leq G,\Gamma(H)=\Gamma(G).

Theorem (Burness, Covato)
Let G be finite, simple and H be a maximal subgroup. Then \Gamma (H)=\Gamma (G) implies that one of the following holds:
a) (G,H) belongs to a quite short table of exceptions.
b) G=\mathcal{A}_n,H=(\mathcal{S}_k\times\mathcal{S}_{n-k})\cap\mathcal{A}_n
Moreover, \Gamma(H)=\Gamma (G) whenever they are in the table.

I didn’t really get how the proof goes but apparently it uses a former result of Liebeck, Prager & Saxl who determined in which case the set of prime factors is the same. And then it uses an old result of Zsygmondi (1892) : for all prime power q, e integer, q^e has a prime divisor which divides no other q^i-1 with i\leq e.

When b) holds, it is not always true that the prime graphs are equal.

Conjecture : Suppose G=\mathcal{A}_n,H=(\mathcal{S}_k\times\mathcal{S}_{n-k})\cap\mathcal{A}_n with 1< k< n and p\leq n\implies p\leq k for every prime p.
Then \Gamma(H)=\Gamma (G)\Longleftrightarrow either
i)n\geq 25 is odd,k=n-1, n-4 is composite
ii)(n,k) is (6,5) or (10,7)

Goldbach's conjecture implies this conjecture. In fact
Lemma : suppose G=\mathcal{A}_{p+1}, H=\mathcal{A}_{p},p\geq 7. Then
\Gamma(H)=\Gamma (G)\Longleftrightarrow p+1=r+s.

We have restricted ourselves in all this to maximal subgroups H. Can we go further?
Theorem : let G be finite simple and H a proper subgroup. Let’s even suppose that G=\mathcal{A}_n and H is transitive (so we forbid the situation of b)). Then they have same prime graphs if and only if either
i) H is maximal and (G,H) are in the table.
ii) H is a second maximal group (maximal subgroup of maximal subgroup M).