# A family of polynomials with symmetric galois group

Consider the following family of polynomials in $K[x,y]$, where $K$ has characteristic zero:

$f_n(x,y)=(x+y)^n+(x-1)y^n,$

for $n\geq 3$. I can prove that $f_n(x,y)$ has an irreducible factor of degree $n-1$ in $x$. I also know that the galois group of $f_n$ over $K(y)$ is the symmetric group of degree $n-1$, but am having trouble proving this.

Here is an alternative form for $f_n$: make the substitution $x\rightarrow xy$ and divide by $y^n$. this gives:

$g_n(x,y)=(x+1)^n+yx-1.$

Substituting $-n$ for $y$ in $g_n(x,y)$ we get:

$g_n(x,-n)=x^2h(x),$

where $h(x)$ is separable (EDIT: $h(x)$ is the subject of this question).

Alternatively, substituting $x\rightarrow x-1$ into $g_n(x,y)$ gives us a polynomial which factors as:

$(x-1)(x^{n-1}+x^{n-2}+\ldots +x^2+x+y+1)$

It seems as though it shouldn't be hard to show that some specialisation of $y$ into this gives a polynomial with galois group $S_{n-1}$ over $K$...but I'm well and truly stuck.

-
If $K$ is algebraically closed, looking at specializations may not be the best approach. –  Kevin Ventullo Sep 9 '11 at 16:52
I don't understand the setup. $f_n(x,y)$ has degree $n$ in $x$ and seems to be irreducible in $K[x,y]$ (at least it is irreducible for small $n$), so there's no factor of degree $n-1$. Also, the substitution of $xy$ for $x$ does not yield a multiple of $(x+1)^n + yx - 1$, which does have a factor of $x$ and with an complementary factor that's irreducible in $K[x,y]$ simply because it's monic and linear in $y$. Was $f_n(x,y)$ supposed to be $(x+y)^n + (x-1)y^n$? That would make the $x \leftarrow xy$ transformation work as claimed. –  Noam D. Elkies Sep 12 '11 at 2:28
Yes you're right...it was supposed to be $(x+y)^n+(x-1)y^n$. Thanks for pointing this out - I have edited the question. –  MrB Sep 14 '11 at 8:55

[Edited mostly to incorporate references etc. from Michael Zieve]

The polynomial $(x^n-1)/(x-1) - y$ has Galois group $S_{n-1}$ over ${\bf C}(y)$ for each $n$, as expected. This answers one of the three problems; the question statements asserts that they are equivalent, which doesn't seem to be the case (see my comment there), so I hope I'm answering the intended one.

The proof combines group theory and polynomial algebra (as might be expect) with algebraic topology, which might be a bit less expected. The connection is as follows. Let $S$ be the Riemann sphere with coordinate $y$, let $P(x,y)$ be any polynomial of degree $d>0$ in $x$, and let $S'$ be the Riemann surface corresponding to $P(x,y)=0$. The rational function $y$ on $S'$ gives a map $S' \rightarrow S$; let $B = \lbrace y_1,\ldots,y_b\rbrace$ be its set of branch points, and fix some $\eta \in S$ not in $B$. Then $\pi_1(S-B,\phantom.\eta)$ is a free group on $b-1$ generators, with generators $g_1,\ldots,g_b$ (where each $g_j$ is a loop from the base point $\eta$ around $y_j$ and back to $\eta$) subject to the single relation $g_1 g_2 \cdots g_b = 1$. These lift to automorphisms $\tilde g_j$ of $S' - y^{-1}(B)$ such that $y = y \cdot \tilde g_j$, and thus to permutations $\pi_j$ of the $d$ sheets of $S'$ above $S$. Then the key fact is that

The Galois group of $P(x,y)$ as a polynomial over ${\bf C}(y)$ is the subgroup of $S_d$ generated by the permutations $\pi_j$.

In our case $P\phantom.$ has the form $p(x) - y$. In general I think it is known which polynomials (or even rational functions) $p$ yield $p(x)-y$ with Galois group other than $S_d$, but it's not easy and involves the classification of finite simple groups! [Actually even less is known; the groups have been determined, but the polynomials, not quite, even in the polynomial case. See below. But this is tangential to the question at hand (albeit a fascinating tangent) because the ensuing argument is enough.] Fortunately in our case the following sufficient condition is all we need:

Let $p\in {\bf C}[X]$ be a polynomial of degree $d$. Assume that the derivative $p'$ has distinct roots $x_1,\ldots,x_{d-1}$, and that the numbers $y_j = p(x_j)$ are also pairwise distinct. Then $p(x)-y$ has Galois group $S_d$ over ${\bf C}(y)$.

[Naturally this result is not new, but I was still surprised to learn from Mike Zieve of its true age and pedigree: Hilbert (1892)! See below.]

Proof: Here $b=d$ and the branch points are $y_1,\ldots,y_{d-1}$ and $y_d = \infty$. Since $P$ is a polynomial, $\pi_d$ is a $d$-cycle. (This already proves that the Galois group is transitive, that is, that the polynomial is irreducible; but we already knew this because it is obviously irreducible over ${\bf C}[y]$.) Each $\pi_j$ for $j<d$ is a simple transposition. So we have $d-1$ transpositions whose product is a $d$-cycle. But we readily prove the following by induction on $d$:

Let $s_1,\ldots,s_{d-1}$ be $d-1$ simple transpositions of $d$ letters. Then TFAE: (i) $s_1 s_2 \cdots s_{d-1}$ is a $d$-cycle; (ii) $s_1,\ldots,s_{d-1}$ generate a transitive subgroup of $S_d$; (iii) $s_1,\ldots,s_{d-1}$ generate $S_d$; (iv) the graph on $d$ vertices in which two vertices are adjacent iff they're permuted by some $s_j$ is a tree.

Here (i) is satisfied, so (iii) holds and the Galois group is $S_d$ as claimed.

[NB we cannot drop the condition that the $y_j$ be distinct; e.g. the Čebyšev polynomial $T_d$ has dihedral Galois group, which is smaller than $S_d$ once $d>3$, even though $T'_d$ has distinct roots $x_j$, because $T_d(x_j) = \pm 1$ for each of them.]

It remains to check that the hypothesis on $p$ is satisfied when $d=n-1$ and $p=(X^n-1)/(X-1)$. For lack of a better idea I did this by computing the discriminant of the polynomial $$q(y) = \frac{(n-1)^{n-1} y^n - n^n (y-1)^{n-1}}{(y-n)^2} \qquad (1)$$ of degree $n-2$ whose roots are the $y_j$, and checking that it is nonzero; in fact $$\mathop{\rm disc} q(y) = \pm 2 \Delta_{n-1} \Delta_n$$ where $\Delta_m := m^{(m-1)(m-3)}$ (and the sign depends on $n \bmod 4$). The formula for $q$ was obtained from the familiar expression $\pm \bigl( (n-1)^{n-1} A^n - n^n B^{n-1} \bigr)$ for the discriminant of the trinomial $x^n - Ax + B$. It follows that the numerator of (1) is $\pm$ the discriminant of $x^n - xy + (y-1) = (x-1) (p(x)-y)$ as a polynomial in $x$, whence (1) soon follows; substituting $y = nz/(nz-(n-1))$, and using the covariance of the discriminant under ${\rm PGL}_2$ together with the same trinomial formula, soon gives the claimed $\pm 2 \Delta_{n-1} \Delta_n$ (the factor of $2$ arises at the end from a double application of L'Hôpital's rule), QED.

$\phantom.$

Here are some relevant references and additional information.

Polynomials with distinct critical values: This is in section 4.4 of Serre's Topics in Galois Theory (Boston: Jones & Bartlett 1992), as is the reference to Hilbert: "Ueber die irreduzibilität genzen rationalen Funktionen mit ganzzahligen Koeffizienten", J. reine angew. Math. ("Crelle's J.") 110, 104-129 (= Ges. Abh. II, 264-286). Serre gives such polynomials the suggestive name "Morse functions". M. Zieve also notes that a 1959 paper by Birch and Swinnerton-Dyer in Acta Arith. (MR0113844 (22 #4675)) attributes to Davenport the equivalent formulation

[The Galois group of $f(x) = y$] is the symmetric group if the discriminant of the discriminant of $f(x)-y$ does not vanish.

They call this a "more euphonious form"; that's a matter of taste, but at any rate it's a memorable formulation, and the one that ended up being used here.

Exceptional Galois groups of $p(x) = y$. The primitive groups that can occur are described by Peter Müller in a paper Primitive monodromy groups of polynomials. They are the symmetric and alternating groups, plus cyclic and dihedral groups (for polynomials equivalent to powers and Čebyšev), and a finite but substantial list of exceptional possibilities. It is hopeless to classify all cases of alternating Galois group. For the rest it can be done, but not easily. Some are exhibited by Cassou-Nogues and Couveignes in an Acta Arith. paper Factorisations explicites de $g(y)-h(z)$; most others were done by Mike Zieve himself; and the final case, polynomials of degree $23$ with Galois group the Mathieu group $M_{23}$, I computed only a few days ago after Mike noted it was still open (they're defined over the quadratic extension of ${\bf Q}(\sqrt{-23})$ of discriminant $3 \cdot 23^3$).

When $p$ is allowed to be a rational function, even the list of groups is not yet known. Mike notes that this "ties in with the 'genus zero program' initiated by Guralnick and Thompson" that was completed in a 2001 paper by Frohardt and Magaard in the Annals of Math. Thanks again to Mike Zieve for all this information.

-

Your second form is a trinomial (as a polynomial in $x$) and the Galois groups of trinomials have been studied half to death -- Noam Elkies has some very cool results. But for your purposes, just look at the first paragraph of

http://jlms.oxfordjournals.org/content/53/3/433.full.pdf

-
Thanks. Originally I had thought that I could prove it that way. Unfortunately it is not an irreducible trinomial though! So I don't think any of the various results apply. –  MrB Sep 9 '11 at 13:01
Ah, so. On the other hand, I might be being totally dense, but by specializing $y$ to various primes, and then reducing mod those same primes (when your polynomial is essentially $x^n -1$, don't you get enough cycles of different lengths to get the symmetric group? –  Igor Rivin Sep 9 '11 at 13:36
No..I don't think so. $x^n-1$ has cyclic galois group, so lots of cycle-types would be missing. –  MrB Sep 9 '11 at 13:52
This journal paper is not freely available online; looking it up in the library, it is not clear that the technique applies. Neither are my own computations with trinomials directly relevant... Fortunately at least the question on the Galois group of $((x^n-1)/(x-1)) - y$ over ${\bf C}(y)$ yields to known techniques, as I explain further in my answer. –  Noam D. Elkies Sep 14 '11 at 2:06
@MrB: The polynomial x^n - 1 does not have cyclic Galois group. Well, it depends what your base field of the Galois extension is. The extension of Q by an n-th root of unity has Galois group over Q isomorphic to (Z/nZ)*, which is often not cyclic (e.g., if n has at least two different odd prime factors). –  KConrad Sep 14 '11 at 2:27