\documentclass[12pt,a4paper]{article}
\usepackage{e-jc}

\usepackage{amsmath,amsthm,amsfonts,amssymb}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    citecolor=black,
    filecolor=black,
    linkcolor=black,
    urlcolor=blue
}

\renewcommand{\qedsymbol}{\textsquare}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newtheorem{Definition}{Definition}[section]
\newtheorem{Theorem}[Definition]{Theorem}
\newtheorem{Lemma}[Definition]{Lemma}
\newtheorem{Corollary}[Definition]{Corollary}
\theoremstyle{definition}
\newtheorem{Example}{Example}[section]
\newtheorem*{Question}{Question}
\newtheorem*{Acknowledgement}{Acknowledgement}

\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Dih}{Dih}

\newcommand{\PGL}[2]{\ensuremath{\operatorname{PGL}_{#1}(#2)}}
\newcommand{\PSL}[2]{\ensuremath{\operatorname{PSL}_{#1}(#2)}}
\newcommand{\AGL}[2]{\ensuremath{\operatorname{AGL}_{#1}(#2)}}
\newcommand{\PG}[2]{\ensuremath{\operatorname{PG}_{#1}(#2)}}
\newcommand{\wreath}{\wr}

\newcommand{\fppG}[1]{\ensuremath{P_{#1}}}
\newcommand{\fppGO}[2]{\ensuremath{P_{#1, #2}}}

\newcommand{\card}[1]{\ensuremath{\left\lvert #1 \right\rvert}}
\newcommand{\abs}[1]{\ensuremath{\left\lvert #1 \right\rvert}}
\newcommand{\intsto}[1]{\ensuremath{\left[#1\right]}}

\newcommand{\ifrac}[2]{\ensuremath{#1/#2}}

\begin{document}


\title{Fixed point polynomials of permutation groups}
\author{C. M. Harden \qquad D. B . Penman\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small University of Essex\\[-0.8ex] 
\small United Kingdom\\
\small\tt cmhard@essex.ac.uk \qquad dbpenman@essex.ac.uk}
\date{\dateline{2012-12-07}{2012-00-00}\\
\small Mathematics Subject Classifications: 20B99}
\maketitle

\begin{abstract}
In this paper we study, given a group $G$ of permutations of a finite set,
the so-called fixed point polynomial $\sum_{i=0}^{n}f_{i}x^{i}$, where
$f_{i}$ is the number of permutations in $G$ which have exactly $i$ fixed
points. In particular, we investigate how root location relates to properties
of the permutation group. We show that for a large family of such groups most
roots are close to the unit circle and roughly uniformly distributed round it. We prove
that many families of such polynomials have few real roots. We show that many
of these polynomials are irreducible when the group acts transitively. We close
by indicating some future directions of this research.

\bigskip\noindent \textbf{Keywords:} group theory, finite permutation groups
\end{abstract}

\section{Introduction and definition}
In this paper we introduce the fixed-point polynomial of a permutation
group, calculate it for various well-known families of groups, and
give some results about irreducibility and the location of roots for
such polynomials. One motivation will be the recent study
of the chromatic polynomials of
graphs and the links between their roots and the properties of the associated
graphs - see e.g. \cite{jackson}, \cite{salassokal}, \cite{aberthubai} -
though our results will be of  different character.
\begin{Definition}
Let $G$ be a group of permutations of a finite set $\Omega$ of order
$n$, and $f_i$ be the number of elements of $G$ which fix \emph{exactly} $i$
points. The fixed-point polynomial, $\fppGO{G}{\Omega}$, is defined to be the
polynomial $\sum_{i = 0}^n f_ix^i$. 
\end{Definition}
Sometimes $\Omega$ is clear and in such cases we may just write
$\fppG{G}$ instead of $\fppGO{G}{\Omega}$. 
 This polynomial was (effectively)
introduced in \cite{Boston}: the
$p_{G}(t)$ in Section 4 there is $\frac{1}{\card{G}}\fppGO{G}{\Omega}(t)$. We will
use the lower-case $p$ form occasionally (see e.g. Lemma~\ref{Lem:FPPDisjointUnionAndWreathProduct}
below).
\cite{Boston} contains some observations on these polynomials, though
its main concern is
the proportion of elements which are derangements. $\fppGO{G}{\Omega}$
is also $\card{G}$ times
the cycle index polynomial of the permutation group (see \cite[p.~143]{PermGroups} for
definition), specialised to $s_{1}\to x$, $s_{i}\to 1$
for all $i\geq 2$.  It is also easy to check that $\fppGO{G}{\Omega}(x)$
is $\card{G}$ times the probability generating function of the
number of fixed points of a uniformly at random selected element of $G$
in its action on $\Omega$.   We note that $f_{n}=1$ and $f_{n-1}=0$. 

Some properties of the group can obviously be recovered from this polynomial.
For example, it is easy to see that the order of $G$ is
$\fppGO{G}{\Omega}(1)$ and the degree of $G$ is equal to the degree of
$\fppGO{G}{\Omega}$. The number of orbits is $\fppGO{G}{\Omega}^{\prime}(1)$
divided by $\card{G}$. The rank, $r$, of $G$ (i.e. the number of
orbits on $\Omega \times \Omega$) is
equal to $\frac{\fppGO{G}{\Omega}^{\prime\prime}(1) + \fppGO{G}{\Omega}^\prime(1)}{\fppGO{G}{\Omega}(1)}$. The theory behind the latter
comes about by viewing $\fix(g)$ as a character function on the vector space with
basis set $\Omega$. Taking the inner product of $\fix(g)$ with itself gives
us $\sum_{i = 0}^n \fix(g)^2 = r\card{G}$, and from this the result follows.
The minimum degree is also easy to recover. 

However this polynomial does not determine the group up to isomorphism.
Indeed, any group acting on itself in the regular action
where $g$ acts on $x$ by forming $gx$ has
$\fppGO{G}{G}(x)=x^{\card{G}}+(\card{G}-1)$
so taking two non-isomorphic groups of the same order (the smallest examples
are $C_{4}$ and $V_{4}$) we get the abstract
groups non-isomorphic but the polynomials the same. One might hope for
uniqueness if (say) the groups are both primitive, but the Mathieu group
$M_{9}$ acting on 9 points and $\AGL{1}{\mathbb{F}_{9}}$ both have
fixed-point polynomial  $x^{9}+63x+8$. Further, GAP gives an example in
degree 15 of two transitive permutation groups $(G,\Omega)$ and $(H,\Omega)$
- in GAP's notation, these are $A_{6}(15)$ and
$3S_5(15)$ - for which $\fppGO{G}{\Omega}(x) = \fppGO{H}{\Omega}(x)$ but one
of the two groups is primitive but the other not: this answers a question left open
in \cite{Boston}. We hope at some future date to address an observation
\cite{Thas} that these pairs of non-isomorphic groups with the same fixed
point polynomials also arise naturally in the study of so-called
Gassmann-Sunada triples.


We note here two properties of the polynomials: they are (effectively)
from \cite{Boston}, Theorem 4.6 parts (6) and (8). 
\begin{Lemma} \label{Lem:FPPDisjointUnionAndWreathProduct}
Suppose $(G_1, \Omega_1)$ and $(G_2, \Omega_2)$ are two permutation groups. Then
\begin{enumerate}
\item If $G_{1}\times G_{2}$ acts on the disjoint union
$\Omega_{1}\coprod \Omega_{2}$ by $(g_{1},g_{2})\omega=g_{1}\omega$ if $\omega
\in \Omega_{1}$ and $(g_{1},g_{2})\omega=g_{2}\omega$ otherwise, we have
\begin{equation*}
P_{G_{1}\times G_{2}, \Omega_{1}\coprod \Omega_{2}}(x)
= P_{G_{1},\Omega_{1}}(x)P_{G_{2},\Omega_{2}}(x).
\end{equation*}
\item In the imprimitive action of the wreath product $G_1 \wreath G_2$ on $\Omega_{1}\times
\Omega_{2}$ we have
\begin{equation*}
p_{G_{1}\wreath G_{2}, \Omega_{1}\times \Omega_{2}}(x)
= p_{G_{2},\Omega_{2}}(p_{G_{1},\Omega_{1}}(x)).
\end{equation*}
\end{enumerate}
\end{Lemma}


We have observed empirically that for many families of fixed-point
polynomials the fixed-point polynomials are very often (but not always) irreducible if the group is
transitive, have few real roots (Theorem~\ref{Thm:RealRootUpperBound} will
give some general insight on this, but in fact real roots seem to be rarer
still) and that these roots tend to be concentrated near the unit circle
unless the group is very large, when more interesting behaviours are possible.
We amplify on some of these observations in what follows. 

\section{Roots and their properties}

The first property we will look at are the location of the roots of
$\fppG{G}$. We aim to give a few basic theorems which often tell us where
most roots of $\fppG{G}$ are, and add restrictions to the factors of
$\fppG{G}$.

The following consequence of Rouch\'{e}'s theorem is proven in e.g.
\cite{Zhao}.

\begin{Theorem} \label{Thm:RootsInOutCircle}
Let $p(x) = \sum_{i = 0}^n f_ix^i$ be a complex polynomial. If there exists an
integer $k$ such that $\abs{f_k} > \sum_{i \neq k} \abs{f_i}$ then $p(x)$ has
exactly $k$ roots inside the unit circle, no roots on the unit circle, and $n - k$
roots outside the unit circle. In particular, if $f_0 > \frac{\card{G}}{2}$,
all roots are outside the unit circle. 
\end{Theorem}

The next theorem, from \cite[Theorem~3]{HughesNikeghbali} says that, when $f_{0}\neq 0$,
unless $\frac{\card{G}}{\sqrt{f_{0}}}$ is large,
most roots are in a small annulus around the unit circle. Thus
the typical behaviour of roots is unlikely to distinguish such groups. 

\begin{Theorem}[Hughes and Nikeghbali] \label{Thm:HughesNikeghbali}
Let $P(z) = \sum_{i = 0}^n f_iz^i$ be a polynomial over the complex numbers
such that $f_0f_n \neq 0$. Then, given $0 < \rho\leq 1$, we have that
\begin{equation*}
1 - \frac{\card{\{\alpha : P(\alpha) = 0, 1 - \rho \leq \abs{\alpha}
\leq \frac{1}{1 - \rho}\}}}{n} \leq \frac{2}{n\rho}L_n(P)
\end{equation*}
where
\begin{equation*}
L_n(P) = \log\left(\sum_{i = 0}^n \abs{f_i}\right) - \frac{\log(\abs{f_0})
+ \log(\abs{f_n})}{2}.
\end{equation*}
\end{Theorem}

In the case of fixed-point polynomials the above is satisfied if $G$ contains
a derangement, and the $L_n$ function simplifies to
$\log\left(\frac{\card{G}}{\sqrt{f_0}}\right)$. So if
$\log\left(\frac{\card{G}}{\sqrt{f_0}}\right)$ is small compared to $n$,
most roots will be in the annulus. 

\begin{Corollary}
Let $(G_{n},\Omega_{n})$ be primitive permutation groups of degree $n$ such
that $A_n$ is not contained in $G_{n}$. Then \fppG{G_{n}} has a proportion $1 - o(1)$ of its roots
in the annulus $1 - \rho \leq \abs{\alpha} \leq \frac{1}{1 - \rho}$, for any
$\rho>0$, as $n\to\infty$. 
\end{Corollary}
\begin{proof}
By (e.g.) Mar\'{o}ti \cite{Maroti}, an upper bound on the cardinality of such
a group is $50n^{\sqrt{n}}$. Thus $L_{n}(P)\leq \sqrt{n}\log(50n)$, which is
$o(n)$ as required.  (Those who want to avoid the use of the classification
of finite simple groups in Mar\'{o}ti's proof can instead use results of
Babai on primitive but not 2-transitive groups \cite{bab}, and Pyber \cite{pyb}
for 2-transitive groups). 
\end{proof}

If we have a sequence $(G_{n},\Omega_{n})$ of groups whose degree tends to
infinity, and an absolute bound on the number of points  any element in the
family can
fix, then we can make a stronger statement: for any $\epsilon>0$
for all large enough $n$ $G_{n}$ has \emph{all} its roots of modulus
less than $1+\epsilon$. We need a lemma:

\begin{Theorem}[Blichfeldt's Theorem]
Let $G$ be a permutation group of degree $n$, and $L = \{\fix(g) : g \in G
\setminus \{e\}\}$. Then $\card{G}$ divides $\prod_{l \in L} (n - l)$.
\end{Theorem}

\begin{Theorem} \label{Thm:RootsTendToUnitCircle}
Let $G_1, G_2, \dots$ be a family of permutation groups, and $n_i$ be the
degree of $G_i$. If
\begin{itemize}
\item The sequence $n_1, n_2, \dots$ tends to infinity
\item there exists a number $k$, such that for all $i$ we have that
$\fix(g) \leq k$ for all non-identity elements in $G_i$
\end{itemize}
then for any $\epsilon > 0$ there exists only finitely many $i$ such that
$\fppG{G_i}(z)$ has a root with modulus at least $1 + \epsilon$.
\end{Theorem}
\begin{proof}
Firstly, note that there exists a subexponential function $S$ (i.e. $S$
satisfies
\begin{equation*}
\lim_{x \to \infty}\frac{S(x)}{e^{cx}} = 0
\end{equation*}
for all $c > 0$) such that, for all $i$ we have $\card{G_i} \leq S(n_i)$. By
Blichfeldt's Theorem, $\card{G}$ divides $\prod_{l \in L} (n - l)$, and so
$\card{G} \leq \prod_{l \in L} (n - l)$. Thus $S(n_i)= \prod_{j\in L}
(n_i - j)$ is a subexponential function that satisfies our requirements.

Since there is no permutation that fixes more than $k$ points, we have that
$\fppG{G_i}(z) = z^{n_i} + f_kz^k + f_{k - 1}z^{k - 1} + \dots + f_0$.
Let $\alpha$ be a root of $\fppG{G_i}(z)$ such that $\abs{\alpha} = 1 + \epsilon$
for some $\epsilon > 0$. Then $-(\alpha^{n_i}) = \sum_{i = 0}^k f_i\alpha^i$. The
triangle equality then gives us
\begin{equation*}
\abs{\alpha}^{n_i} = \abs{\sum_{j = 0}^k f_j\alpha^j}
\leq \sum_{j = 0}^k f_j\abs{\alpha}^j.
\end{equation*}
Since $\sum_{j = 0}^k f_j = \card{G_i} - 1 < \card{G_i}$ the right hand side is
at most $\card{G_i}\abs{\alpha}^k \leq S(n_i)(1 + \epsilon)^k$, and so we have
\begin{equation*}
\abs{\alpha}^{n_i} = (1 + \epsilon)^{n_i} \leq S(n_i)(1 + \epsilon)^k . 
\end{equation*}
The left hand side is, however, an exponential function in $n_i$, whereas the
right hand side is a subexponential function in $n_i$. Thus only a finite number
of $\alpha$'s satisfying $\abs{\alpha} >1 + \epsilon$ can exist.
\end{proof}

Not only can we often get most of the roots around the unit circle, but the
same condition gives that they are spaced roughly evenly around the circle.
This was first proved by Erd\H{o}s and Tur\'{a}n - again, see
\cite[Theorem~2]{HughesNikeghbali}.

\begin{Theorem}[Erd\H{o}s and Tur\'{a}n]  
Let $P(z) = \sum_{i = 0}^n f_iz^i$ be a polynomial over the complex numbers
such that $f_0f_n \neq 0$. Then, with $L_{n}(P)$ as in Theorem~\ref{Thm:HughesNikeghbali},  there is
some constant $C$ such that, given $0 < \theta < \phi < 2\pi$, we have  
\begin{equation*}
\abs{\frac{\card{\{\alpha : P(\alpha) = 0,
\theta \leq \arg{\alpha} \leq \phi}}{n} - \frac{\phi - \theta}{2\pi}}^2
\leq \frac{C}{n}L_n(P).
\end{equation*}
\end{Theorem}
This is saying that provided $\ifrac{L_{n}(P)}{n}$ tends to zero, the uniform
distribution on the roots will weakly converge to normalised Lebesgue
measure on the unit circle. 

Though we often get many roots \emph{close} to the unit circle, roots \emph{on}
the unit circle are a lot rarer. Note that $S_2$ has $\fppG{S_2}(x) = x^2 + 1$ so $i$
is a root of a fixed-point polynomial (this is a lot easier than the apparently
unsolved question ``does there exist a graph whose chromatic polynomial has
$\sqrt{-1}$ as a root''!). However, given some conditions, this is a rarity:

\begin{Lemma}
Let $P(x) = \sum_{i = 0}^n f_ix^i$ be a monic irreducible polynomial
$\in \mathbb{Z}[x]$ such that $P(1) \neq 0$ and $P$ has a root $\alpha$ of
modulus 1. Then $P$ is a reciprocal polynomial (i.e one for which
$f_{i}=f_{n-i}$ for all $0\leq i\leq n$). 
\end{Lemma}
\begin{proof}
Since $\alpha$ is a root, $\bar{\alpha}=\alpha^{-1}$ is also a root. Thus
\begin{equation*}
\sum_{i = 0}^n f_i\alpha^i = 0
\implies \sum_{i = 0}^n f_i\alpha^{n - i} = 0
\implies \sum_{i = 0}^n f_{n - i}\alpha^i = 0.
\end{equation*}
Since $P$ is irreducible, $P$ is the minimal polynomial of $\theta$.
Thus there exists a scalar $k$ such that
$\sum_{i = 0}^n f_{n - i}x^i = kP(x)$. Substituting $x = 1$ we get
$P(1) = kP(1)$, and so $k = 1$. Thus $f_i = f_{n - i}$ as required.
\end{proof}

We use the Rado notation $[n]$ to mean $\{1,2,\ldots n\}$. 

\begin{Corollary}
Let $G$ be a group acting on $\Omega$ such that \fppG{G} is irreducible and
transitive. Then, if \fppG{G} has a root of modulus 1, $G$ is $S_2$ acting on
$\intsto{2}$. 
\end{Corollary}
\begin{proof}
We can assume $G$ is non-trivial. By the above lemma, \fppG{G} must be
reciprocal. Thus we get $f_{0}=f_{n}=1$ and $f_{1}=f_{n-1}=0$.

Now we use the Orbit-Counting Lemma. Since the one derangement has no fixed
points, and
every other element at least 2 fixed points,  
\begin{equation*}
\frac{1}{\card{G}}(0+2(\card{G}-1))\leq  1.
\end{equation*}
Manipulation yields $\card{G}\leq 2$: by transitivity and non-triviality,
$G=S_{2}$.
\end{proof} 

It seems to be the case that, for most transitive $G$, $\fppG{G}$ is irreducible
over $\mathbb{Q}$ (or equivalently over $\mathbb{Z}$), and so
has neither repeated roots, nor rational roots.  There are exceptions:
if $k$ is a positive integer such that $k^3 = 3m - 1$ for an integer $m$, the
cyclic group $C_{k^3 + 1}$  acting regularly on $\intsto{k^3 + 1}$ has
fixed-point polynomial
$\fppG{C_{k^3 + 1}}(x) = x^{k^3 + 1} + k^3 = (x^m + k)(x^{2m} - kx^m + k^2)$,
and there are other occasional factorisations for regular $G$. (Note, though,
that most polynomials $x^{n}+(n-1)$ are irreducible: for if any prime divides
$n-1$ exactly, we can use that prime in Eisenstein's criterion to deduce
irreducibility, so a necessary condition for reducibility is that $n-1$ is
powerful - i.e. for every prime $p$ dividing $n-1$, $p^{2}$ divides $n-1$ -
and Golomb \cite{Golomb} showed that only $\tfrac{\zeta\left(\frac{3}{2}\right)}{\zeta(3)}
\sqrt{x}(1+o(1))$ of the positive integers $\leq x$ are powerful, where $\zeta$
denotes the Riemann zeta function).

Lemma~\ref{Lem:FPPDisjointUnionAndWreathProduct} part 2 has the consequence that if some group has a reducible
fixed point polynomial, then infinitely many further reducible examples can
be constructed from it by taking wreath products. We have been informed
\cite{camperscomm} of an unpublished construction of, for each odd prime
$p$, two imprimitive groups of degree $p^{2}$ (with orders $p^{p-1}$ and
$p^{p}$ respectively) whose fixed-point polynomials are reducible: this
construction uses coding theory. We know
at present of no transitive groups with reducible fixed-point polynomial
other than the possibilities implied by this and the previous paragraph. 
(It is easy to see that many intransitive
permutation groups can have reducible polynomials. For example, if
$S_n$ acts on $\intsto{m}$ where $m>n$ by acting
on the first $n$ letters, then $x^{m - n}$ is a factor of
$\fppGO{S_n}{\intsto{m}}$). 

We now turn to real roots. We can often get a crude upper bound with the
following. Again, this is related to the ideas of Erd\H{o}s and Tur\'{a}n,
and we refer to \cite{Prasolov} for the proof. 

\begin{Theorem} \label{Thm:RealRootUpperBound}
Let $P(z) = \sum_{i = 0}^n f_ix^i$ be a polynomial with $m$ real roots. If
$f_0f_n \neq 0$ then, again with $L_{n}(P)$ as in
Theorem~\ref{Thm:HughesNikeghbali}
\begin{equation*}
m^2 \leq 2nL_{n}(P).
\end{equation*}
\end{Theorem}
Thus for fixed point polynomials, this inequality simplifies to
\begin{equation*}
m^2 \leq 2n\log\left(\frac{\card{G}}{\sqrt{f_0}}\right).
\end{equation*}

For many groups, the number of real roots of its fixed-point polynomial seem
to be smaller still than predicted by this bound. Indeed, of the examples
we have done so far with irreducible polynomials, we have not got more
than two real roots, for $A_{n}$ with $n$ even, or the group of invertible
transforms $x\rightarrow ax+b$ acting on a finite field of order $2^{n}$,
with $n\geq 2$. (See below for more, and intransitive examples with many
roots). 

A toy observation in this direction is that no non-trivial fixed-point
polynomial has all of its roots on the real axis.
If it did, then by e.g. \cite{Pitman} the sequence $(f_i)$ is a so-called
PF$_2$ sequence (i.e. the infinite matrix $M=(f_{i-j})$ where $f_{k}=0$
for any $k<0$ or $>n$, has all its  $1\times 1$ or $2\times 2$ minors
having non-negative determinant). This implies (again see \cite{Pitman})
that it has no internal zeros (that is, if $0\leq i<j<k\leq n$ and
$f_{i}f_{k}>0$, then $f_{j}>0$). However, $f_n > 0$,
$f_{n - 1} = 0$, and $f_i > 0$ for some $i < n - 1$, so there is an internal
zero. (Even if one restricts to the non-zero $f_{i}$s, these do not form
a unimodal sequence, even for $\fppG{S_{n}}(x)$). 


We may ask whether the complex roots are dense in the plane, which is known to
be true for chromatic polynomials by a result of Sokal. 
The answer is no when $G$ is transitive or has a bounded number of orbits.
\begin{Theorem} \label{Thm:RootsNotDenseForTransitiveGroups}
The set of all roots of $\fppG{G}(x)$ for transitive groups $G$ is not dense in the
complex plane.
\end{Theorem}
\begin{proof}
Let $\alpha$ be a complex number such that $\abs{\alpha} < 1$ and
$\abs{\alpha - 1} < 1$. We will show that there does not exist a transitive
group $G$ such that $\fppG{G}(\alpha) = 0$.

Assume that there exists a transitive group $G$ such that $\fppG{G}(\alpha) = 0$ for some $\alpha$. For all groups $G$ we have $\fppG{G}(1) = \card{G}$. Thus, using the triangle inequality to note that $\abs{1 + \alpha + \dots + \alpha^{i - 1}} \leq i$, we get
\begin{align*}
\implies &\sum_{i = 0}^n f_i(1 - \alpha^i) = \card{G} 
\implies \sum_{i = 0}^n f_i\abs{1 - \alpha}i \geq \card{G} \\
\implies &\abs{1 - \alpha}\sum_{i = 0}^n if_i \geq \card{G} 
\implies \abs{1 - \alpha} \geq 1
\end{align*}
which is a contradiction. Thus $\alpha$ cannot be a root, as required.
\end{proof}

\begin{Corollary}
Let $k > 0$ be an integer. Then the set of all roots of $\fppG{G}(x)$ for groups
$G$ with $k$ or less orbits is not dense in the complex plane.
\end{Corollary}
\begin{proof}
The proof is the same as Theorem~\ref{Thm:RootsNotDenseForTransitiveGroups},
except that the zero-free zone is the intersection of the circles $\abs{z} < 1$
and $\abs{z - 1} < \frac{1}{k}$. This follows because
\begin{equation*}
\sum_{i = 0}^n if_i = t\card{G}
\end{equation*}
where $t$ is the number of orbits of $G$, which is bounded above by $k$.
\end{proof}

It appears also that the set
$\{\alpha : \abs{\alpha} < 1, \alpha \notin \mathbb{R}^-\}$ could potentially
be a zero-free zone. Calculations with GAP\cite{GAP4} show that
this is true for transitive groups of degree $<15$.

In fact, there may well be larger zero-free regions. For example, if
we know more about the proportion of derangements, results in
\cite{HeydeSchuh} can sometimes be used to extend the zero-free region
a bit. A result of Saff and Varga \cite{SaffVarga} shows
that the
region $y^{2}\leq 4x$ contains no zeros $z=x+iy$ of the
$(\fppG{S_{n}}(z))$: there may be similar results for other families.

\begin{Question}
Are the roots of all fixed point polynomials (including
intransitive ones) dense in the complex plane?
\end{Question}

We have no very clear idea of the answer to this question. 
\section{Examples}

\begin{Example}[The symmetric group on $n$ letters]
We first need a lemma. 

\begin{Lemma} \label{Thm:FPPFromOrbitsOnKTuples}
Let $G$ be a group of degree $n$. Let $F_k$ denote the number of orbits of $G$
acting on $k$-tuples of distinct elements of $\Omega$. Then
\begin{equation*}
\frac{\fppG{G}(x)}{\card{G}} = \sum_{k = 0}^n F_k\frac{(x - 1)^k}{k!}.
\end{equation*}
\end{Lemma}
\begin{proof}
Combine \cite[Theorem~6.12]{PermGroups} with the fact that the left-hand
side of that lemma is, by an earlier observation, $\frac{\fppG{G}(x)}{\card{G}}$.
\end{proof}

Of course $S_n$ acting on $[n]$ in the usual way has one orbit on distinct
$k$-tuples for all $k\leq n$, and so the fixed-point polynomial can be
easily seen from Lemma~\ref{Thm:FPPFromOrbitsOnKTuples}.
\begin{equation*}
\fppGO{S_n}{\intsto{n}}(x) = n!\sum_{i = 0}^n \frac{(x - 1)^i}{i!}.
\end{equation*}
Thus $\frac{\fppGO{S_n}{\intsto{n}}}{n!}$ is the first $n$
terms of the Maclaurin series for $e^{x - 1}$.
\end{Example}

\begin{Example}[The alternating group on $n$ letters]
We first note the relation $f_i(A_n) = \binom{n}{i}f_0(A_{n - i})$ and that
$f_{0}(A_{n})= \frac{(f_{0}(S_{n})-(-1)^{n}(n-1))}{2}$, see e.g. \cite{Chapman}.
This allows us to calculate the fixed-point polynomial (see \cite{Myself} for details)
\begin{equation*}
\fppG{A_n}(x) =  \frac{1}{2}\left(\fppG{S_n}(x) + (x - 1)^n
+ n(x - 1)^{n - 1}\right). \\
\end{equation*}
\end{Example}

\begin{Example}[Frobenius groups]
A transitive permutation group $G$ acting on a finite set $\Omega$ is called
Frobenius if $\fix(g) \leq 1$ for all non-identity elements of the group, and
there exists an element of the group such that $\fix(g) = 1$.

The fixed point polynomial for a Frobenius group can be calculated easily: 
\begin{equation*}
\fppGO{G}{\Omega} = x^{\card{\Omega}} + (\card{G} - \card{\Omega})x +
\card{\Omega} - 1.
\end{equation*}

We investigate two families of Frobenius groups in more detail. The first
is the dihedral group $\Dih_n$ of symmetries of a regular $n$-gon, in the
case where $n$ is odd. In this case, the fixed-point polynomial is
\begin{equation*}
\fppG{\Dih_n}(x) = x^n + nx + n - 1.
\end{equation*}

The second contains the automorphism groups of Paley graphs of prime
order. Recall these have vertex set the integers modulo $p$, for a
prime $p$ congruent to 1 modulo 4. Two vertices $x$ and $y$ are
adjacent if $x - y \equiv a^2 \mod{p}$ for some $a$. It is well-known
that the automorphism group consists of all functions $f(x)=ax+b$ with
$a\neq 0$ a square in $\mathbb{F}_{p}$ and $b$ any element of $\mathbb{F}_{p}$:
(see e.g. \cite{Carlitz}: the result has been rediscovered several times). Thus a non-identity
automorphism is a derangement if and only if $a=1$, otherwise it has the
one fixed point $x = \frac{-b}{(a-1)}$. Thus 
\begin{equation*}
\fppGO{\Aut{P_p}}{V(P_p)}(x) = x^p + \frac{p(p - 3)}{2}x + p - 1.
\end{equation*}

\end{Example}

\begin{Example}[Mathieu groups]
Since there are only a few Mathieu groups, we can use \cite{GAP4} to
calculate the relevant $f_i$'s. (One could also approach the problem
for at least some of the groups based on Lemma~\ref{Thm:FPPFromOrbitsOnKTuples} and the fact the
groups are sharply transitive). 
\begin{align*}
\fppG{M_9}(x) &= x^9 + 63x + 8 \\
\fppG{M_{10}}(x) &= x^{10} + 315x^2 + 80x + 324 \\
\fppG{M_{11}}(x) &= x^{11} + 1155x^3 + 440x^2 + 3564x + 2760 \\
\fppG{M_{12}}(x) &= x^{12} + 3465x^4 + 1760x^3 + 21384x^2 + 33120x + 35310 \\
\fppG{M_{21}}(x) &= x^{21} + 315x^5 + 2240x^3 + 11844x + 5760 \\
\fppG{M_{22}}(x) &= x^{22} + 1155x^6 + 12320x^4 + 130284x^2 + 126720x + 173040 \\
\fppG{M_{23}}(x) &= x^{23} + 3795x^7 + 56672x^5 + 998844x^3 + 1457280x^2 + 3979920x \\
&\quad + 3704448 \\
\fppG{M_{24}}(x) &= x^{24} + 11385x^8 + 226688x^6 + 5993064x^4 + 11658240x^3 \\
&\quad + 47759040x^2 + 88906752x + 90267870.
\end{align*}
\end{Example}

\begin{Example}[Hyperoctahedral groups]
Consider an $n$-dimensional hypercube, $Q_n$. Then the hyperoctahedral group
$H_n$ is the automorphism group of $Q_n$. We will follow the notation of
\cite{ChenStanley} and represent the elements of $H_n$ as signed permutations.
That is, we will attach minus signs to certain elements of a permutation (for
example, $(2, \overset{-}{5}, \overset{-}{3}, 1)$). The
vertices will be seen as numbers in their binary form. The permutation will then
permute the binary digits, and will negate any bits permuted by a number with an
attached minus sign.

The sequence of $f_i$'s was mentioned very briefly in
\cite[Corollary~2.4]{ChenStanley} as a means of calculating $f_0$. The relevant
part of it is described below.

\begin{Theorem}
Let $H_n$ be the hyperoctahedral group of order $n$, and $0 < i \leq n$. Then
$f_{2^i} = 2^{n - i}c(n, i)$ where $c(n, i)$ is the unsigned Stirling number of the
first kind. The only other non-zero $f_{j}$ is $f_{0}$. 
\end{Theorem}
\begin{proof}
A permutation fixes $2^i$ points if it has $i$ cycles, and every cycle has an even
number of minus signs attached to it. If a cycle is of length $l$, there are
$2^{l - 1}$ ways of attaching an even number of minus signs. Thus there is
$2^{n - i}$ ways of attaching an even number of minus signs to a given
permutation with $i$ cycles. By definition, there are $c(n, i)$ permutations on
$\intsto{n}$ with $i$ cycles. The last sentence follows from
\cite[Proposition~2.5]{ChenStanley}
\end{proof}

We can then work out the number of permutations with fixed points, and
subtract this from the order of $H_n$, which is well known to be $2^nn!$ -
see again \cite{ChenStanley}. This gives (using a fact about Stirling numbers
at the end of the proof of Corollary 2.4 in \cite{ChenStanley})
\begin{equation*}
\fppGO{H_n}{V(Q_n)}(x) = 2^nn! - \frac{(2n)!}{2^nn!}
+ \sum_{i = 1}^n 2^{n - i}c(n, i)x^{2^i}.
\end{equation*}
\end{Example}

\begin{Example}[Projective planes]

Let $\mathbb{F}_p$ be the finite field of prime order $p$. Define the group
$\PG{2}{p}$ as the automorphism (collineation) group of a projective plane whose point set
is equal to the 1-dimensional subspaces of $\mathbb{F}_p^3$ and line set
is equal to the 2-dimensional subspaces of $\mathbb{F}_p^3$, with incidence
defined by inclusion. By the Fundamental Theorem of Projective Geometry,
$\PG{2}{p}\cong \PGL{3}{p}$, which has order
$p^{3}(p^{2}+p+1)(p-1)^{2}(p+1)$. 

The fixed-point polynomial for $\PG{2}{p}$ has four non-zero
coefficients $f_0$, $f_1$, $f_{p + 1}$ and $f_{p^2 + p + 1}=1$, as
any collineation which fixes two points fixes the whole line containing
them, and any automorphism which fixes a line and a point not
on the line in fact clearly fixes all points.
It is known that the automorphism group is 2-transitive. This
gives the equations
\begin{align*}
\card{G} &= 1+f_{p + 1} + f_1 + f_0 \\
&= (p^2 + p + 1) + (p + 1)f_{p + 1} + f_1 \\
&= p(p + 1)(p^2 + p + 1) + p(p + 1)f_{p + 1}
\end{align*}
using the fact that if $(G,\Omega)$ is $k$-transitive, then
$\fppG{G}^{(k)}(1)=\card{G}$ (see \cite[Theorem 4.6. (v)]{Boston}). Solving these
equations gives
\begin{align*}
\fppG{\PG{2}{p}}(x) &= x^{p^2 + p + 1} + (p^2 + p + 1)(p^2 - p - 1)(p^2 - p + 1)x^{p + 1} \\
&\quad + p(p^2 + p + 1)(p^5 - 2p^4 + 2p^2 - p + 1)x + p^4(p^3 - p^2 - 1).
\end{align*}
\end{Example}

\begin{Example}[Bipartite double cover of a stable graph]
Let $G=(V,E)$ be a graph. We can define the bipartite double cover of $G$,
$\tilde{G}$, to be a graph with vertex set $V \times \{1, -1\}$: we
refer to the two sets $V_{1}=\{(v,1): v\in V\}$ and $V_{-1}=\{(v,-1): v\in V\}$
as the vertex classes. Two
vertices, $(v,\epsilon_{v})$ and $(w,\epsilon_{w})$, are adjacent in
$\tilde{G}$ if and only if $v$ and $w$ are adjacent in
$G$ and $\epsilon_{v}\neq \epsilon_{w}$. An automorphism $\alpha$ of $G$ induces
an automorphism $\tilde{\alpha}$ of $\tilde{G}$ by $\tilde{\alpha}(v,\epsilon)
=(\alpha(v),\epsilon)$. There is also a \lq swapping\rq\,
automorphism that interchanges the two vertex classes. If these are
the only automorphisms of $\tilde{G}$ then $G$ is called a stable graph.

If a graph is stable, every automorphism of $\tilde{G}$ which fixes
$(v,\epsilon_{v})$ will also fix $(v,-\epsilon_{v})$, so every automorphism
coming from $G$ which fixes $i$ points in $G$ fixes $2i$ points in
$\tilde{G}$. Also, any automorphism which swaps round
$V_{1}$ and $V_{-1}$ will be a derangement. Thus we get, for a stable graph,
\begin{equation*}
\fppGO{\Aut(\tilde{G})}{V(\tilde{G})}(x) =
\fppGO{\Aut(G)}{V(G)}(x^2) + \card{\Aut(G)}.
\end{equation*}

Examples of stable graphs can be found via Surowski's theorem \cite{Surowski}.
\begin{Theorem}[Surowski's Theorem]
Any strongly regular graph $(n, k, \lambda, \mu)$ with $k > \mu \neq \lambda \geq 1$ is stable.
\end{Theorem}
\end{Example}

\begin{Example}
Suppose we consider, for a prime $p$, the Sylow $p$-subgroup of $S_{p^{k}}$.
This is well-known to be the iterated wreath product of $k$ copies of
$\mathbb{Z}_{p}$. In particular, in the case $p=2$, its fixed point
polynomial will be the $k$-fold  iteration of $(x^{2}+1)$ with itself. 
\end{Example}

\section{Irreducibility of the fixed-point polynomial} \label{Sec:Irreducibility}
We return now to showing that various of the polynomials are irreducible. We
start with $S_{n}$ and $A_{n}$, using the following generalisation by
Filaseta of a theorem of Schur (see \cite{Filaseta}).
\begin{Lemma} \label{Thm:SchurFilaseta}
Any polynomial of the form
\begin{equation*}
\sum_{i = 0}^n c_i\frac{X^i}{i!} = 1 + c_1\frac{X^1}{1!}
+ c_2\frac{X^2}{2!}+ \dots +c_{n-1}\frac{X^{n-1}}{(n-1)!}+c_n\frac{X^n}{n!}
\end{equation*}
where $c_0 = 1$, $0 < \abs{c_i} < n$ for all $i \in \intsto{n}$, and all
$c_i$ are integers, is irreducible in $\mathbb{Q}[X]$, except possibly if $c_{n}=\pm 5$ and $n=6$ or $c_{n}=\pm 7$ and
$n=10$.
\end{Lemma}
\begin{Theorem} \label{Thm:IrreducibilityConditionOrbits}
Let $G$ be a transitive group of degree $n \neq 6, 10$ with $0 < k < n$ orbits on $n$-tuples
of distinct elements. Then $\fppG{G}(x)$ is irreducible.
\end{Theorem}
\begin{proof}
We have to show that the
conditions of Lemma~\ref{Thm:SchurFilaseta} apply to $\ifrac{\fppG{G}}{\card{G}}$.
We know that $\fppG{G}(1) =\card{G}$. Using Lemma~\ref{Thm:FPPFromOrbitsOnKTuples},
\begin{equation*}
\frac{\fppG{G}(x)}{\card{G}} = \sum_{k = 0}^n F_k\frac{(x - 1)^k}{k!}.
\end{equation*}
and1we are told that $0<F_i <n$. The right-hand side is irreducible as a polynomial in $u = x-1$ by Filaseta's
result, and so the left-hand side is irreducible as a polynomial in
$\mathbb{Q}[x]$.
\end{proof}
\begin{Corollary} \label{Thm:PAnIrreducible}
Suppose that $G = S_n$ acting on $\{1, 2, \dots, n\}$ where $n \geq 2$,
or $A_n$ with $n \geq 3$. Then $\fppG{G}(x)$ is irreducible in $\mathbb{Q}[x]$. 
\end{Corollary}
\begin{proof}
The cases with $n=6$ or $n=10$ can be handled by calculating the
expressions in Examples 3.1. and 3.2: one can then use e.g. MAPLE to check
that these four fixed-point polynomials are indeed irreducible. In the other cases,
note that $S_n$ has just one orbit on distinct $n$-tuples, as there
is a permutation taking any ordering of $\{1, 2, \dots, n\}$ to any other.
For $A_n$, there are two orbits on the $n$-tuples of distinct elements
from $\{1, 2, \dots, n\}$: indeed one orbit is all the even permutations of
$\{1, 2, \dots, n\}$ and the other orbit is the odd permutations. This finishes
the proof by Theorem~\ref{Thm:IrreducibilityConditionOrbits}, as in each case $n$ exceeds the number of orbits.
\end{proof}

It is natural to try to prove irreducibility of the polynomials by considering
reductions mod a suitable prime $p$, as if the reduction is irreducible so
is the original polynomial. However, any fixed point polynomial is reducible modulo 2, as if $f_{0}$
is even, then $x$ is a factor modulo 2, and if $\card{G}$ is even, then
$(x-1)$ is a factor mod 2: and at least one of $\card{G}$ and $f_{0}$ has
to be even, e.g. considering the Handshake Lemma in the $f_{0}$-regular graph
on vertex set $G$ where $x\sim y$ if and only if $xy^{-1}$ is a derangement.
More generally, it will be reducible modulo any prime dividing
$\card{G}f_{0}$. There does not seem to be any obvious choice of prime in
general modulo which to look for irreducibility. 

Another obvious tool is Eisenstein's criterion from Galois theory. Here are
two examples of it in action. 

\begin{Theorem}
Suppose $\card{G}$ is odd and that $4$ does not divide $f_0$. Then
$\fppG{G}(x)$ is irreducible. 
\end{Theorem}
\begin{proof}
If $G$ is a group acting on a set $\Omega$, then $g$ and
$g^{-1}$ have the same number of fixed points for every $g\in G$. Further
as the order is odd, there is no element of order 2, so $g\neq g^{-1}$ unless
$g$ is the identity. Thus all the $f_{i}$ for $i<n$ are even. Since by
assumption $2^{2}=4$ does not divide $f_{0}$, the result follows from
Eisenstein's criterion applied at the prime $p=2$. 
\end{proof}

\begin{Theorem} \label{Thm:PrimeFrobeniusIrreducible}
The fixed-point polynomial for a Frobenius group of prime degree is
irreducible. In particular, the automorphism groups of Paley graphs
have irreducible fixed-point polynomials. 
\end{Theorem}
\begin{proof}
Let $G$ be a Frobenius group of order $m$ and prime degree $p$. Then the fixed
point polynomial of $G$ is $\fppG{G}(x) = x^p + (m - p)x + p - 1$. We first shift
this polynomial by 1 to get $\fppG{G}(x + 1) = (x + 1)^p + (m - p)x + m - 1$. The
prime $p$ divides every coefficient of $(x + 1)^p$ with the exceptions of the
leading term and the constant term $1$. Also $p$ divides $m$ and so
divides $m - p$. The combined constant term is $m$, which is
divisible by $p$ but not by $p^{2}$ as by Blichfeldt's theorem $m$ divides
$p(p-1)$. Thus Eisenstein's criterion shows $\fppG{G}(x + 1)$ is
irreducible. Thus $\fppG{G}(x)$ is irreducible.
\end{proof}

Similarly, one may take the calculations of the fixed-point polynomials
of Mathieu groups: then MAPLE indicates that these are all irreducible.
For the projective planes, we do not have a complete result yet, but in
the special case where $p^{2}+p+1$ is also prime, it is
not too hard to use Eisenstein's criterion on $\fppG{\PG{2}{p}}(x)$, putting
$x=u+1$, to see that it is irreducible. See \cite{Myself} for details. 


Zhao \cite{Zhao} shows (an application of Rouch\'{e}'s theorem)
that if $p(x) = \sum_{i = 0}^n a_ix^i$ is a
polynomial of degree $n$ with integer coefficients and if $\abs{a_0}$ is
prime with $\abs{a_0} > \sum_{i = 1}^n \abs{a_i}$ then $p(x)$ is irreducible.
We suspect this result will be of use in proving irreducibility results. 


\section{Location of the roots of fixed-point polynomials}
A useful technique for bounding the number of real roots of a polynomial
is Descartes' rule of signs: the relevant version for us is that the number
of negative roots of a polynomial $P(x)=\sum_{i=0}^{n}f_{i}x^{i}$ is at most the number of sign
changes in the sequence of non-zero coefficients of $f(-x)=\sum_{i=0}^{n}
(f_{i}(-1)^{i})x^{i}$. Thus Frobenius groups of odd degree (e.g. Paley graphs)
have exactly one real root of their fixed-point polynomials (they have
one real root for having odd degree, and there is only one change on sign
in the coefficients).  

\begin{Example}[Symmetric groups]
This is a well-understood story. Let $g_{n}(z)=\sum_{i=0}^{n-1} \frac{z^i}{i!}$,
so that the roots of $g_{n}(z)$ are the roots of $\fppG{S_{n-1}}(x)$ translated
by 1. It thus suffices to understand the roots of $g_{n}(z)$.
\begin{Theorem}
The roots of $g_{n}(nz)$ converge, as $n \to \infty$, to the
curve $\abs{ze^{1-z}} = 1$  in the complex plane. There is exactly
one real root of $\fppG{S_{n}}(x)$ if $n$ is odd, and none if $n$ is even.
The real root, when it exists, is near $c^{*}n$, where $c^{*}$ is the unique
(negative) real solution of $\abs{ce^{1 - c}} = 1$, which is approximately $-0.278$.
\end{Theorem}
\begin{proof}
This is a compilation of results of Szeg\H{o}\cite{Szego} and
Zemyan\cite{Zemyan}.
\end{proof}
See \cite{Zemyan} for a picture of the curve and the roots converging to it.

Note also this result on the real root allows us to construct \emph{intransitive}
permutation groups whose fixed-point polynomial has many real roots. Indeed
take the disjoint union of complete graphs of orders
$2n_{1}+1<2n_{2}+1<\ldots <2n_{k}+1$: the automorphism group is then
$S_{2n_{1}+1}\times S_{2n_{2}+1}\times \ldots \times S_{2n_{k}+1}$ and this will have
fixed point polynomial the product of the fixed point polynomials on
$S_{2n_{j}+1}$ on $K_{2n_{j}+1}$, by Lemma~\ref{Lem:FPPDisjointUnionAndWreathProduct} part 1. Each of these $k$ polynomials has (exactly)
one real root by the above, so overall there will be $k$ real roots. 
\end{Example}
\begin{Example}[Alternating groups]
Again the seeming pattern of roots is a horseshoe of the same general style
as for the symmetric group, though we have not formally proved this. As
regards real roots, numerical work suggests that there
are exactly two real roots of $\fppG{A_n}(x)$ for $n$ even, one close to
$-\frac{n}{\sqrt{2}}$
and the other close to $-c^*n$ where $c^*$ is as in the discussion of
the symmetric group: for $n$ odd, it seems there is exactly one real root
close to $-\frac{n}{\sqrt{2}}$. Here is a partial result. 
\begin{Lemma} \label{Lem:AlternatingRootEstimate}
Suppose that $\fppG{A_{n-1}}(z_{n}n+1)=0$ for real $z_{n}$. Then if $n$ is even, we get
$(z_{n}) \to \frac{-1}{\sqrt{2}}$. If $n$ is large enough and odd, and
there are infinitely many $z_{n}$, then $(z_{n}) \to \frac{-1}{\sqrt{2}}$ if
$\liminf_{n}\sqrt{n}\left(\frac{e^{z_n - 1}}{z_n}\right)^{n}=0$, and otherwise
$\liminf_{n} z_{n}\geq c^{*}$.  
\end{Lemma}
\begin{proof}
By the Enestr\"{o}m-Kakeya theorem, any root of
$\sum_{i=0}^{n}a_{i}z^{i}$
with $a_{i}>0$ for all $i$ lies in the annulus
\begin{equation*}
\min_{0\leq i\leq n-1}\frac{a_{i}}{a_{i+1}}\leq \abs{z}
\leq \max_{0\leq i\leq n-1}\frac{a_{i}}{a_{i+1}}.
\end{equation*}
Recall that
\begin{equation*}
\fppG{A_{n}}(x)=\frac{n!}{2}\sum_{i=0}^{n-2}\frac{(x-1)^{i}}{i!}
+n(x-1)^{n-1}+(x-1)^{n}.
\end{equation*}
Thus, putting $z=(x-1)$ we have 
\begin{equation*}
a_{i}=\frac{1}{2}\frac{n!}{i!}\text{~for~}0\leq i\leq n-2,\,a_{n-1}=n,\,
a_{n}=1
\end{equation*}
so all roots of $\fppG{A_{n}}(x)$ have $1\leq \abs{x - 1} \leq n$; real
roots are in $1-n\leq x\leq 0$.  We need to show that there is not a root
at $x=1-n$ for $n\geq 2$, in order to apply a result of Dieudonn\'{e}
shortly. The claim that $\fppG{A_{n}}(1-n)\neq 0$ will follow if we show
\begin{equation*}
\fppG{A_{n}}(x)=\frac{n!}{2}\sum_{i=0}^{n-2}\frac{(-n)^{i}}{i!}\neq 0.
\end{equation*}
If $n$ is odd, simply note that each two consecutive terms in the sum
\begin{equation*}
\frac{(-n)^{2j}}{(2j)!}+\frac{(-n)^{2j+1}}{(2j+1)!}<0
\end{equation*}
for $2j+1\leq n-2$ is negative: this follows as the numerator is a
positive number times $2j+1-n<0$. Similarly, if $n$ is even, the $i=0$ term
is positive, and thereafter for
any $1\leq 2j-1\leq n-2$ we have
\begin{equation*}
\frac{(-n)^{2j-1}}{(2j-1)!}+\frac{(-n)^{2j}}{(2j)!}>0.
\end{equation*}
Thus we need only consider roots of $\fppG{A_{n-1}}(z_{n}n+1)$ with
$z_{n}\in (-1,0)$. Dieudonn\'{e} proved (see. e.g. \cite{Yildirim}) that, for
any fixed $\eta>0$, if
$z \in \{w: \abs{w} < 1\} \cap \{w:  \abs{w - 1} \geq \eta\}$ we have
$(f_{n}(z))$ converges uniformly to $\ifrac{1}{(1-z)}$, where
\begin{equation*}
f_{n}(z)=\frac{n!}{(nz)^{n}}\left(e^{nz}-\sum_{i=0}^{n-1}
\frac{(zn)^{i}}{i!}\right).
\end{equation*}
Thus for real $z\in (-1,0)$, given $\epsilon>0$ for
$n\geq N_{1}(\epsilon)$ we get
\begin{align*}
&\frac{1}{1 - z} - \epsilon < f_n(z) < \frac{1}{1 - z} + \epsilon \\
\implies &\frac{1}{1 - z} - \epsilon < \frac{n!e^{nz}}{(nz)^n}
- \frac{n\fppG{S_{n - 1}}(nz + 1)}{(nz)^n} < \frac{1}{1 - z} + \epsilon.
\end{align*}
Substituting $\fppG{A_{n - 1}}(x) = \frac{1}{2}(\fppG{S_{n - 1}}(x)
+ (x - 1)^{n - 1} + (n - 1)(x - 1)^{n - 2})$ gives
\begin{equation*}
\frac{1}{1-z}-\epsilon <\frac{n!e^{nz}}{(nz)^{n}}
-\frac{n(2\fppG{A_{n-1}}(nz+1)-(nz)^{n-2}(nz + n - 1))}{(nz)^{n}} <
\frac{1}{1-z}+\epsilon
\end{equation*}
\begin{equation*}
\frac{1}{1-z}-\frac{1}{z}-\frac{1}{z^{2}}-\epsilon
<\frac{n!e^{nz}}{(nz)^{n}}-\frac{2n\fppG{A_{n-1}}(nz+1)}{(nz)^{n}}-\frac{1}{nz^{2}}
<\frac{1}{1-z}
-\frac{1}{z}-\frac{1}{z^{2}}+\epsilon
\end{equation*}
\begin{equation*}
\frac{2z^{2}-1}{(1-z)z^{2}}-\epsilon
<\frac{n!e^{nz}}{(nz)^{n}}-\frac{2n\fppG{A_{n-1}}(nz+1)}{(nz)^{n}}
-\frac{1}{nz^{2}}<\frac{2z^{2}-1}{(1-z)z^{2}}+\epsilon.
\end{equation*}
In particular, if $n\geq N_{1}(\epsilon)$
and $z_{n}$ is such that $\fppG{A_{n-1}}(nz_{n}+1)=0$, we get that
\begin{equation*}
\frac{2z_{n}^{2}-1}{(1-z_{n})z_{n}^{2}}-\epsilon
<\frac{n!e^{nz_{n}}}{(nz_{n})^{n}}-\frac{1}{nz_{n}^{2}}
<\frac{2z_{n}^{2}-1}{(1-z_{n})z_{n}^{2}}+\epsilon.
\end{equation*}
Recall that a form of Stirling's approximation says that, for all $n\in \mathbb{N}$,
\begin{equation*}
\sqrt{2\pi}n^{n+\ifrac{1}{2}}e^{-n}\leq n!\leq en^{n+\ifrac{1}{2}}e^{-n}.
\end{equation*}
This gives 
\begin{align*}
\sqrt{2\pi n}\frac{n^n}{e^n}\frac{e^{nz_{n}}}{(-nz_{n})^{n}}
\leq \frac{n!e^{nz_{n}}}{(-nz_{n})^{n}}\leq
e\sqrt{n}\frac{n^{n}}{e^{n}}\frac{e^{nz_{n}}}{(-nz_{n})^{n}}\\
\implies \sqrt{2\pi n}\left(\frac{e^{z_{n}-1}}{-z_{n}}\right)^{n}\leq
\frac{n!e^{nz_{n}}}
{(-nz_{n})^{n}}\leq e\sqrt{n}\left(\frac{e^{z_{n}-1}}{-z_{n}}\right)^{n}.
\end{align*}
Thus, if $n$ is even (respectively odd) we get 
\begin{align*}
\sqrt{2\pi n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}\leq 
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}+\frac{1}{nz_{n}^{2}}
+\epsilon \\
e\sqrt{n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}\geq 
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}+\frac{1}{nz_{n}^{2}}-\epsilon
\end{align*}
respectively
\begin{align*}
e\sqrt{n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}\leq
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}+\frac{1}{nz_{n}^{2}}+\epsilon \\
\sqrt{2\pi n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}\geq
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}
+\frac{1}{nz_{n}^{2}}-\epsilon.\,\,(*)
\end{align*}
In the case when $n$ is even, we see we must have
\begin{align*}
&\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}+\frac{1}{nz_{n}^{2}}
+\epsilon>0 \\
\implies &(2n+\epsilon n(1-z_{n}))z_{n}^{2}-n+1-z_{n}>0 \\
\implies &2n(1+\epsilon)z_{n}^{2}> n-2
\end{align*}
which implies that  $\limsup_{n}z_{n}\leq \frac{-1}{\sqrt{2}}$. We record for future
use that taking $\epsilon=0.01$ and $n=200$, that indeed we have
$z_{n}^{2}>\frac{0.99}{2.02}$ for $n\geq 200$ so $z_{n}<-0.7$ for $n\geq 200$.

On the
other hand, since
$z_{n}\leq \frac{-1}{\sqrt{2}}+\delta$ for $n$ large enough, we have that
$\abs{\frac{e^{z_{n}-1}}{z_{n}}} <0.256$ (taking $\delta$ small enough) so
$\abs{\left(\frac{e^{z_{n}-1}}{-z_{n}}\right)^{n}e\sqrt{n}} <\epsilon$ for all $n\geq N_{2}(\epsilon)$. Thus
\begin{equation*}
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}+\frac{1}{nz_{n}^{2}}>-2\epsilon
\end{equation*}
for $n$ large enough.  Thus again $\liminf_{n}z_{n}\geq \frac{-1}{\sqrt{2}}$:
thus $(z_{n})\to \frac{-1}{\sqrt{2}}$.

For $n$ odd,  from the formula
\begin{align*}
\sqrt{2\pi n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}\geq
\frac{2z_{n}^{2}-1}{z_{n}^{2}(1-z_{n})}
+\frac{1}{nz_{n}^{2}}-\epsilon.
\end{align*}
we note that as $n$ is odd and $z_{n}<0$ the left-hand side is negative.
Thus we must get 
\begin{equation*}
\frac{2z_{n}^{2}-1}{(z_{n}^{2}(1-z_{n}))}+\frac{1}{nz_{n}^{2}} <\epsilon
\end{equation*}
which again implies that  $\liminf_{n}z_{n}\geq \frac{-1}{\sqrt{2}}$.

Now suppose
that $\liminf\sqrt{n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}=0$ so that
$\sqrt{n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}>-\epsilon$ for $n$ large enough.
Multiplying by $e$ and using the inequalities (*) for $n$ odd, 
\begin{equation*}
\frac{2z_{n}^{2}-1}{(z_{n}^{2}(1-z_{n}))}+\frac{1}{nz_{n}^{2}}>-(1+e)\epsilon
>-4\epsilon
\end{equation*}
(say) for $n$ large enough. This cannot happen if, for infinitely many
$n$, we have $z_{n}>\frac{-1}{\sqrt{2}}+\delta$, so we get
$\limsup_{n}z_{n}\leq \frac{-1}{\sqrt{2}}$
so $\lim_{n\to\infty}z_{n}= \frac{-1}{\sqrt{2}}$.

Otherwise $\liminf_{n}\sqrt{n}\left(\frac{e^{z_{n}-1}}{z_{n}}\right)^{n}<0$, i.e. there is some
$\epsilon>0$ such that for all
but finitely many $n$, $\sqrt{n}\left(\frac{e^{z_{n}-1}}{-z_{n}}\right)^{n}>\epsilon$;
this would not work if for infinitely many $n$ we had 
$\ifrac{-e^{z_{n}-1}}{z_{n}} \leq 1-\delta$. Thus we cannot have infinitely
many $z_{n}<c^{*}$ as then we would have
\begin{align*}
e^{z_n - 1} &< e^{c^* - 1} \\
\frac{e^{z_n - 1}}{-z_n} &< \frac{e^{c^* - 1}}{-c^*} \\
\abs{\frac{e^{z_n - 1}}{-z_n}} &< \abs{\frac{e^{c^* - 1}}{-c^*}} \\
&= \abs{\frac{1}{c^*e^{1 - c^*}}} \\
&= 1
\end{align*}
and so $\liminf_{n}z_{n}\geq c^{*}$. (We suspect, as noted above,
that the limsup is $c^{*}$ too, but there is a technical issue about proving
it and we do not need it for our argument, so omit the point). 
\end{proof}
\begin{Lemma}
For even $n=2k\geq 4$, $\fppG{A_{2k}}(1-k)<0$ (so in particular there are at least
two real roots).
\end{Lemma}
\begin{proof}
We do the case $k=2$ by hand. For $k\geq 3$, using MAPLE and simplifying,
we have
\begin{equation*}
\fppG{A_{2k}}(1-k)=\frac{k(2k-1)}{e^{k}}\Gamma(2k-1,-k)-k^{2k}
\end{equation*}
where $\Gamma(2k-1,-k)=\int_{-k}^{\infty}e^{-t}t^{2k-2}dt$. Thus we need
to prove that
\begin{equation*}
\int_{-k}^{\infty}e^{-t}t^{2k-2}<\frac{(k^{2}e)^{k}}{k(2k-1)}.
\end{equation*}
We split the integral into
\begin{equation*}
\int_{0}^{\infty}e^{-t}t^{2k-2}dt+\int_{-k}^{0}e^{-t}t^{2k-2}dt
\leq (2k-2)!+k\sup e^{-t}t^{2k-2}.
\end{equation*}
Easy calculus shows the supremum of $e^{-t}t^{2k-2}$ is attained at
$t=(2k-2)$ where the supremum is $e^{-2k-2}(2k-2)^{2k-2}$. So we have
to prove that
\begin{equation*}
(2k-2)!+ke^{-2k-2}(2k-2)^{2k-2}<\frac{(k^{2}e)^{k}}{k(2k-1)}.
\end{equation*}
By Stirling again, it is enough to show that
\begin{equation*}
\frac{e(2k-2)^{2k-2+\ifrac{1}{2}}}{e^{2k-2}}+ke^{-(2k-2)}(2k-2)^{2k-2}
<\frac{(k^{2}e)^{k}}{k(2k-1)}
\end{equation*}
For this in turn, it is enough to show that
\begin{equation*}
(2k)^{2k-2}[e\sqrt{2k-2}+k]<\frac{k^{2k-1}e^{3k-2}}{2k}
\end{equation*}
for which, manipulating, it is enough to show that
\begin{equation*}
\left(\frac{e^{3}}{4}\right)^{k}>\frac{e^{2}}{2}[e\sqrt{2k-2}+k]
\end{equation*}
for which it is enough to show that
\begin{equation*}
\left(\frac{e^{3}}{4}\right)^{k}>16k.
\end{equation*}
This is easily proved by induction on $k\geq 3$.
\end{proof} 
\begin{Corollary}
$\fppG{A_{n}}$ has exactly two real roots for $n$ even, and exactly one
for $n$ odd.
\end{Corollary}
\begin{proof}
We have for $n\leq 200$ that the claim holds by (MAPLE) calculation. For
$k\geq 101$, we prove the following statement $P(k)$ by induction:
\\
$P(k)$: $\fppG{A_{2k}}(x)$ has two real roots $z_{2k+1}(2k+1)+1$, with
exactly one of them having $z_{k}>-0.5$ and $\fppG{A_{2k-1}}$ has
exactly one real root $z_{2k}(2k)+1$.
\\
For the base case $k=101$ we have that the lower root of $\fppG{A_{202}}$
is $-141.896\ldots$ and the upper $-55.288\ldots$ which indeed gives
exactly one of the two $z_{203}<-0.5$. Similarly
the unique root of $\fppG{A_{201}}(x)$ is $-141.189$ which give $z_{202}<-0.7$. 

For subsequent cases, suppose we have proved $P(k)$ for $k\leq n$. 
$\fppG{A_{2n+1}}$ of course has at least one real root; if it had
more than one, it would have at least 3. By the estimates in Lemma~\ref{Lem:AlternatingRootEstimate},
the corresponding $z_{2n+2}$'s are all $<-0.7$. Hence both
roots of $\fppG{A_{2n}}$ are between these, so $<-0.7\times (2k+2)+1$ and
so not greater than $-0.5\times (2k+1)$. This is a contradiction, so $\fppG{A_{2k+1}}$
has only one root. 

Finally, if $\fppG{A_{2n+2}}$ has more than 2 roots, it has at least 4: thus
we would get 3 roots of $\fppG{A_{2n+1}}$ but we know that this is not true.
Thus we need only check that $\fppG{A_{2n+2}}$ has at least one real root,
and that at least one of them has $z_{2n+3}>-0.5$. But this follows
from the last Lemma. 
\end{proof}
\end{Example}
\begin{Example}[Frobenius groups]
\begin{Theorem}
If $G$ is a Frobenius group acting on $n$ points then
$\fppG{G}(z)$ has one root inside the unit circle, no roots on the unit
circle, and
$n - 1$ roots outside the unit circle.
\end{Theorem}
\begin{proof}
If $n \neq \ifrac{\card{G}}{2}$, then $f_1 > f_0 + 1$ and so the result follows by
applying Theorem \ref{Thm:RootsInOutCircle}. We will thus assume that $n = \ifrac{\card{G}}{2}$.

To see that there are no roots on the unit circle, assume that
$z = e^{i\theta}$ is a root. Then separating $\fppG{G}(z) = 0$ into real and
imaginary parts gives us the system of equations
\begin{align*}
\cos n\theta &= -(n\cos\theta + n - 1) \\
\sin n\theta &= -(n\sin\theta).
\end{align*}
Squaring both equations and summing them together gives us the unique
solution $\theta = \pi$. This means that $z = -1$. For $z = -1$ to
be a root, we must have $n$ be an even number. However, $n$ is also
the size of the Frobenius kernel, and the size of any Frobenius complement
of $G$ is 2. These orders are not coprime \cite[35.234 p. 191]{Aschbacher}, so $G$ cannot exist in this case.

To see that the roots are distinct, assume that there is a repeated root $\alpha$. Then
$\fppG{G}(\alpha) = \fppG{G}^\prime(\alpha) = 0$. Since
$\fppG{G}^\prime(z) = n(z^{n - 1} + 1)$, the roots of $\fppG{G}^\prime(z)$ occur at
$e^\frac{\pi i(2k + 1)}{n - 1}$, where $k$ is an integer between 0 and $n - 1$.

Thus $\alpha$ must be one of these roots. Inserting this formula into $\fppG{G}(z)$
gives
\begin{align*}
\fppG{G}\left(e^\frac{\pi i(2k + 1)}{n - 1}\right)
&= -e^\frac{\pi i(2k + 1)}{n - 1} + ne^\frac{\pi i(2k + 1)}{n - 1} + n - 1 \\
&= (n - 1)\left(e^\frac{\pi i(2k + 1)}{n - 1} + 1\right).
\end{align*}

Since $n - 1 \neq 0$, $e^\frac{\pi i(2k + 1)}{n - 1} + 1$ must be zero, which
implies that $k = \frac{n}{2} - 1$. However, $n$ must be odd and so $k$ cannot
be an integer. Thus, by contradiction, no such $\alpha$ can exist.

There exists one root inside the unit circle, since $\fppG{G}(-1) = -2$ and
$\fppG{G}(0) > 0$. To see that this is the only root, assume that there are two roots $\alpha_1$, $\alpha_2$ inside the unit circle.
Then
\begin{equation*}
\alpha_1^n + n\alpha_1 + n - 1= 0,\,\,\alpha_2^n + n\alpha_2 + n - 1= 0.
\end{equation*}
Subtracting these equations gives $(\alpha_1^n - \alpha_2^n)
+ n(\alpha_1 - \alpha_2) = 0$. Since the roots must be distinct,
$\alpha_1 - \alpha_2 \neq 0$, and so we can divide through to get
\begin{equation*}
\sum_{j = 0}^{n - 1} \alpha_1^{n - j - 1}\alpha_2^j + n = 0 \\
\implies \abs{\sum_{j = 0}^{n - 1} \alpha_1^{n - j - 1}\alpha_2^j} = n.
\end{equation*}

But as $\abs{\alpha_i} <1$, the triangle inequality gives the contradiction
\begin{equation*}
n \leq \sum_{j = 0}^{n - 1} \abs{\alpha_1^{n - j - 1}\alpha_2^j}
  < \sum_{j = 0}^{n - 1} 1 = n.
\end{equation*}
Thus there must be a unique root inside the circle
as required.
\end{proof}

The question of how many real roots lie outside the unit circle can be answered
by applying Descartes' rule of signs. We noted earlier a Frobenius group
of odd degree has exactly one real root. For a Frobenius group of even degree, there will
be 2 changes in sign. Since we can guarantee the existence of one root inside the
unit circle, there must be exactly two real roots and so this other real root
must be outside the unit circle.

Note that, as the Paley graph has its one real root close to $\ifrac{-2}{p}$ for
large $p$, that there can be no extension of the \lq obvious\rq\, zero-free
range of the $x$-axis (namely, positive $x$). This is in contrast with
chromatic polynomials, which have a zero-free region $(0,1)\cup \left(1, \ifrac{32}{27}\right]$ in
addition to their \lq obvious\rq\, zero-free region $x<0$.

Note that, if $q=2^{r}$, with $r\geq 2$, then the fixed-point polynomial for the action of
the maps $x\rightarrow ax+b$ with $a,b\in \mathbb{F}_{q}$ and $a\neq 0$,
similarly has a fixed point polynomial $x^{q}+q(q-2)x+q-1$ and this has
at most two real roots by the rule of signs, and at least two real roots
since its value at 0 is positive, its value at -1 is negative and its value
at $-2$ is easily checked by induction to be positive. 
\end{Example}

\begin{Example}[Mathieu groups]
All eight fixed-point polynomials from Mathieu groups $M_{n}$ have exactly zero
real roots if $n$ is even and exactly one if $n$ is odd: the slightly tedious
calculations checking this are in \cite{Myself}. Note that this result, together
with the alternating groups having one/two real roots according as $n$ is
odd/even, suggest that it is hard to make a link between a group's
being simple and the existence of real roots of its fixed point polynomial.
\end{Example}

\begin{Example}[Hyperoctahedral Groups]
The roots of the fixed-point polynomial for the hyperoctahedral groups can be
described with two theorems. Firstly, all roots lie outside the unit circle.

\begin{Theorem}
All roots of $\fppG{H_n}(x)$ lie outside the unit circle for all $n > 1$.
\end{Theorem}
\begin{proof}
This is equivalent to the claim that $(2n)! < 2^{2n + 1}n!^2$, since then
$2f_0 > \card{H_n}$ and so Theorem~\ref{Thm:RootsInOutCircle} will apply. The
claim follows from the fact that $2^{2n}=\sum_{i=0}^{n}\binom{2n}{i}\geq \binom{2n}{n}$.
\end{proof}

Secondly, the roots tend toward the unit circle as $n \to \infty$.

\begin{Theorem}
The modulus of the roots of $\fppG{H_n}(z)$ tends to 1 as $n\rightarrow\infty$.
\end{Theorem}
\begin{proof}
Note that $\fppG{H_n}(z) = f_{2^n}z^{2^n} + f_{2^{n - 1}}z^{2^{n - 1}} + \dots + f_2z^2 + f_0$.

Let $\alpha$ be a root of $\fppG{H_n}(z)$ for some $n$. Then
\begin{equation*}
\abs{\alpha}^{2^n}
= \abs{\sum_{i = 0}^{2^{n - 1}} f_i\alpha^i} \leq (2^nn! - 1)\abs{\alpha}^{2^{n-1}}
\leq 2^nn! \abs{\alpha}^{2^{n-1}}\\
\implies \abs{\alpha} \leq (2^nn!)^\frac{1}{2^{n - 1}}.
\end{equation*}
We show that $\lim_{n \to \infty} (2^nn!)^\frac{1}{2^{n - 1}}$ exists and
is equal to 1. The crude bound $n!<n^{n}$ and the sandwich rule make
it clear it is enough to show that 
$\lim_{n\to\infty}(2n)^\frac{n}{2^{n-1}}=1$. But for large enough $n$,
$\ifrac{n}{(2^{n-1})}$ is $\leq \ifrac{1}{(2n)}$ and it is known
that $(2n)^{\frac{1}{(2n)}}\to 1$, so we indeed get the claim. 
\end{proof}
There are clearly no real roots in this case. 
\end{Example}

\begin{Example}[Projective planes]
Again, these polynomials have as few real roots as possible and only one
root in the unit circle:
\begin{Theorem}
\fppG{\PG{2}{p}}(x) has exactly one root inside the unit circle, and no roots
on it for any prime $p$.  There is only the one real root.
\end{Theorem}
\begin{proof}
Showing this claim is equivalent to showing that $f_{1}$ dominates the
sum of the other $f_{i}$, using Theorem~\ref{Thm:RootsInOutCircle}. By
Example 6 and manipulation, we have that this boils down to showing that
the polynomial
$f(x) = x^8 - 2x^7 - x^6 + x^5 + 2x^4 + 3x^3 + 2x$ is positive for all
$x \geq 2$. This function $f$ has two real roots, one at $x = 0$ and one
near $x \approx -1.1258$, and as it is positive for $x = 1$ the result on
roots inside $D$ follows.  The unique root inside the unit circle is
clearly real.

Thus it remains to show that there are no real roots in $(-\infty,-1]$.  Again deal with
$p=2, 3, 5$ as special cases, so that $p\geq 7$. Suppose instead that the
fixed point polynomial had two or more real roots; being of odd degree, it must have
at least three. Since exactly one of these has modulus $<1$, the other two
are less than $-1$.  Thus there must be a root of the derivative of the fixed
point polynomial between them (so also $<-1$).  But the derivative of the fixed
point polynomial is
$(p^{2}+p+1)x^{p^{2}+p}+(p+1)f_{p+1}x^{p}+f_{1}$. Putting $u=x^{p}$, there
has to be a root $u<-1$ of the polynomial
$g(u)=(p^{2}+p+1)u^{p+1}+f_{p+1}(p+1)u+f_{1}$. We now claim that this cannot
happen.  Noting that $(p^{2}+p+1)u^{p+1}$ is positive, we see that we would
have to have $f_{p+1}(p+1)u+f_{1}<0$, i.e. $u<\frac{-f_{1}}{(f_{p+1}(p+1))}$, which
(by MAPLE checking) is $<-p+1$. But also
we must have that $(p^{2}+p+1)u^{p+1}+f_{p+1}(p+1)u<0$ and so must have
$u>\left(\frac{-f_{p+1}(p+1)}{(p^{2}+p+1)}\right)^{\frac{1}{p}}$.  Now
\\
$\frac{-f_{p+1}(p+1)}{(p^{2}+p+1)}=-p^{5}+p^{4}+p^{3}-p^{2}+p+1>-p^{5}$ so 
$u>-(p^{\frac{1}{p}})^{5}$. Now $(p^{\frac{1}{p}})$ is decreasing for $p\geq 7$ so is always
less than $7^{\frac{1}{7}}$ for $p\geq 7$: thus we get $u>-(7^{\frac{5}{7}})>-5$,
but we also must have $u<-6$. This contradiction completes the proof.
\end{proof}
\end{Example}

\begin{Example}[Bipartite double cover of a stable graph]
Regardless of  the choice of $G$, $\fppG{\tilde{G}}$ possesses no real roots,
since it can be written as a sum of even powers of $x$ (plus a positive
constant term). We will also have
$f_{0}(\tilde{G})> \ifrac{\card{\tilde{G}}}{2}$ as long as $\Aut(G)$ contains a
derangement. Thus again
there are no roots of $\fppG{\tilde{G}}$ in the unit circle in this case.
\end{Example}

The above example, together with the easily checked fact that the fixed-point
polynomial for the automorphism group acting on the complete bipartite
graph $K_{n,n}$ is $\fppG{S_{n}}(x)^{2}+n!^{2}$, and the above results
for hypercubes and dihedral groups, plus some other calculations, leave open
the possibility that the fixed point polynomial for the full automorphism
group of a vertex-transitive bipartite graph acting on that graph has no real
roots. We have no counterexample. (Transitivity would be needed: the fixed-point
polynomial for $K_{1,n}$ is $x$ times the fixed-point polynomial for
$S_{n-1}$ so has a root at $x=0$ (and one more root if $n-1$ is odd)). It is
easy to see that if a transitive permutation group has blocks of
imprimitivity of size 2, then its fixed-point polynomial is a polynomial
in $x^{2}$ so has no real roots: cases covered by this include the automorphisms
of a perfect matching, and some other cases above e.g. hypercubes. However
we have no proof in general. 

\begin{Question}
Can the fixed point polynomial for the full automorphism group of a vertex-transitive bipartite graph acting on the vertices of the graph have any real roots?
\end{Question}

\section{Miscellaneous remarks and future topics}
We record here that we have also calculated the fixed-point polynomials
for the natural actions on $\PGL{2}{\mathbb{F}_{q}}$ and $\PSL{2}{q}$
on 1-dimensional subspaces of $\mathbb{F}_{q}^{2}$. For $q>3$ odd, the
polynomials for $\PSL{2}{q}$ have no real roots and again roots converge to
the unit circle. (for $q=3$, $\PSL{2}{\mathbb{F}_{3}} \equiv A_{4}$ so there
are two real roots). Similarly for $\PGL{2}{q}$ for $q$ odd there are no
real roots. For $q$ even, $\PSL{2}{q}$ is equal to $\PGL{2}{q}$: their
fixed point polynomials have at least one real root being of odd degree,
and again one can show that there is only one real root. Details are in \cite{Myself}.

Neumann \cite{Neumann} proved various results to the effect that
transitive permutation groups $(G,\Omega)$ which are not regular have
to have $f_{i}\neq 0$ for some `not-too-large' $i$. For example,
he shows transitivity and not being regular imply there is some $1\leq i\leq \frac{n}{2}$
such that $f_{i}>0$, and that this is best possible: that if
further $G$ is primitive, there is some
$f_{i}>0$ with $1\leq i<\ifrac{(n+3)}{4}$, and that there are infinitely many $n$
for which there is a primitive non-regular group with $f_{i}=0$ for
$1\leq i<n^{\frac{1}{3}}$, and also has results on the case where $(G,\Omega)$ is
primitive and soluble.


We have talked so far about doing this for groups acting on sets. However
it is possible to apply the same concept to semigroup actions. For example, if
we have the full transformation semigroup $T_{n}$ of all maps from
$\intsto{n}$ to itself, it is easy to check that
\begin{equation*}
\fppGO{T_n}{\intsto{n}}(x) =\sum_{i=0}^{n}\binom{n}{i}(n-1)^{n-i}x^{i}=(x + n - 1)^n \\
\end{equation*}
as there are $\binom{n}{i}$ ways of choosing $i$ points to fix,
and $(n - 1)^{n - i}$ ways to derange the remaining $n - i$ points. Note
that this polynomial is far from irreducible!

When asking about the irreducibility of polynomials, it is natural to
ask also `what is the Galois group of the
polynomial?'. In the case of the fixed-point polynomial for $S_n$
acting on $\intsto{n}$, Schur showed that the Galois group 
is $S_n$ if $n \not\equiv 0 \mod{4}$ and $A_n$
otherwise. Using \cite{GAP4} we have found some interesting conjectural
patterns for various families of fixed-point polynomials, which can be found
in \cite{Myself}. We can use standard techniques for calculating
Galois groups to show that, for example, the Galois group of the fixed-point
polynomial for each Mathieu group is the whole of $S_{n}$.

Note that in general it will be NP-hard to compute the fixed point polynomials:
for even in the special case of the automorphism group of a graph acting on
its vertex set, the (easier) problem of working out whether or not
$f_{0}$ is zero or not is known to be NP-complete by a result of Lubiw. We
have not yet investigated tractability in special cases, or approximating
the values.

We hope to address some of the above areas, plus calculations of the roots
for maximal subgroups of $S_{n}$ and for the somewhat more general situation
of the action of finite groups on themselves by conjugation, in a further
paper in this series.
\smallskip

\begin{Acknowledgement}
We are grateful to Peter Cameron for his helpful
comments on an earlier draft of this paper and in particular for outlining
the construction of reducible fixed-point polynomials in \cite{camperscomm} to us. We also thank two anonymous referees for helpful comments on an earlier draft of this paper.
\end{Acknowledgement}

\phantomsection
\addcontentsline{toc}{section}{\refname}
\begin{thebibliography}{10}

\bibitem{aberthubai}
Mikl\'{o}s Ab\'{e}rt and Tam\'{a}s Hubai.
\newblock Benjamini-Schramm convergence and the distribution of chromatic roots
  for sparse graphs.
\newblock Preprint, available at\\ \arxiv{1201.3861}.

\bibitem{Aschbacher}
Michael Aschbacher.
\newblock {\em Finite group theory}.
\newblock Cambridge University Press, 1986.

\bibitem{bab}
L\'{a}szl\'{o} Babai.
\newblock On the order of uniprimitive permutation groups.
\newblock {\em Annals of Mathematics}, 113(3):553--568, 1981.

\bibitem{Boston}
Nigel Boston, Walter Dabrowski, Tuval Foguel, Paul~J. Gies, Judy Leavitt, and
  David~T. Ose.
\newblock The proportion of fixed-point-free elements of a transitive
  permutation group.
\newblock {\em Communications in Algebra}, 21(9):3259--3275, 1993.

\bibitem{camperscomm}
Peter~J. Cameron.
\newblock Personal communication.

\bibitem{PermGroups}
Peter~J. Cameron.
\newblock {\em Permutation Groups}.
\newblock Cambridge University Press, 1999.

\bibitem{Carlitz}
L.~Carlitz.
\newblock A theorem on permutations in a finite field.
\newblock {\em Proc. Amer. Math. Soc.}, 11:456--459, 1960.

\bibitem{Chapman}
Robin~J. Chapman.
\newblock An involution on derangements.
\newblock {\em Discrete Mathematics}, 231:121--122, 2001.

\bibitem{ChenStanley}
William~Y.C. Chen and Richard~P. Stanley.
\newblock Derangements on the n-cube.
\newblock {\em Discrete Mathematics}, 115(1-3):65--75, May 1993.

\bibitem{Filaseta}
Michael Filaseta.
\newblock A generalization of an irreducibility theorem of {I. Schur}.
\newblock {\em Analytic Number Theory: Proceedings of a Conference in Honor of
  Heini Halberstam}, 1:317--396, 1996.
\newblock Edited by {B. C. Berndt}, {H. G. Diamond} and {A. J. Hildebrand}.

\bibitem{GAP4}
The GAP~Group.
\newblock {\em {GAP -- Groups, Algorithms, and Programming, Version 4.4.12}},
  2008.

\bibitem{Golomb}
Solomon~W. Golomb.
\newblock Powerful numbers.
\newblock {\em American Mathematical Monthly}, 77(8):848--852, October 1970.

\bibitem{Myself}
Christopher Harden.
\newblock {\em Fixed-point Polynomials}.
\newblock PhD thesis, The University of Essex.
\newblock To appear.

\bibitem{HeydeSchuh}
Christopher~C. Heyde and Hans-J\"{u}rgen Schuh.
\newblock Uniform bounding of probability generating functions and the
  evolution of reproduction rates in birds.
\newblock {\em Journal of Applied Probability}, 15:243--250, 1978.

\bibitem{HughesNikeghbali}
Christopher~P. Hughes and Ashkan Nikhegbali.
\newblock The zeros of random polynomials cluster uniformly near the unit
  circle.
\newblock {\em Compositio Mathematica}, 144:734--746, 2008.

\bibitem{jackson}
Bill Jackson.
\newblock Zeros of chromatic and flow polynomials of graphs.
\newblock {\em J. Geometry}, 76:95--109, 2003.

\bibitem{Maroti}
Attila Mar\'{o}ti.
\newblock On the orders of primitive groups.
\newblock {\em Journal of Algebra}, 258(2):631--640, December 2002.

\bibitem{Neumann}
Peter~M. Neumann.
\newblock {\em A study of some finite permutation groups}.
\newblock PhD thesis, The Queen's College, Oxford, April 1966.

\bibitem{Pitman}
Jim Pitman.
\newblock Probabilistic bounds on the coefficients of polynomials with only
  real zeros.
\newblock {\em Journal of Combinatorial Theory, Series A}, 77(2):279--303,
  February 1997.

\bibitem{Szego}
Gy{\"o}rgy P\'{o}lya and Gab\'{o}r Szeg\H{o}.
\newblock {\em Aufgaben und Lehrs\"{a}tze aus der Analysis}.
\newblock Springer-Verlag, 1964.

\bibitem{Prasolov}
Victor~V. Prasolov.
\newblock {\em Polynomials}.
\newblock Springer-Verlag, 2001.

\bibitem{pyb}
L\'{a}szl\'{o} Pyber.
\newblock On the orders of doubly transitive permutation groups, elementary
  estimates.
\newblock {\em Journal of Combinatorial Theory, Series A}, 62(2):361--366,
  1993.

\bibitem{SaffVarga}
Ed~B. Saff and Richard Varga.
\newblock Zero-free parabolic regions for sequences of polynomials.
\newblock {\em SIAM Journal on Mathematical Analysis}, 7(3):344--357, 1976.

\bibitem{salassokal}
Jes\'{u}s Salas and Alan~D. Sokal.
\newblock Transfer matrices and partition-function zeroes for antiferromagnetic
  potts models v. further results for the square-lattice chromatic polynomial.
\newblock {\em Journal of Statistical Physics}, 144(5):1028--1122, 2011.

\bibitem{Surowski}
David~B. Surowski.
\newblock Stability of arc-transitive graphs.
\newblock {\em Journal of Graph Theory}, 38:95--110, 2001.

\bibitem{Thas}
Koen Thas.
\newblock Personal communication.

\bibitem{Yildirim}
Cem~Yal\c{c}{\i}n Y{\i}ld{\i}r{\i}m.
\newblock On the tails of the exponential series.
\newblock {\em Canad. Math. Bull}, 37:278--286, 1994.

\bibitem{Zemyan}
Stephen~M. Zemyan.
\newblock On the zeros of the {Nth} partial sum of the exponential series.
\newblock {\em The American Mathematical Monthly}, 113:891--909, December 2005.

\bibitem{Zhao}
Yufei Zhao.
\newblock Integer polynomials, June 2007.\\
\url{yufeizhao.com/olympiad/intpoly.pdf}

\end{thebibliography}

\end{document}
