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).