\documentclass{rhumj_new}
\usepackage[utf8]{inputenc}
\usepackage{mathtools}
\usepackage{amsmath,amssymb,amsthm,mathrsfs}
\usepackage{hyperref}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\DeclarePairedDelimiter\norm{\lVert}{\rVert}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclareMathOperator{\Gal}{Gal}
\numberwithin{equation}{section}
\newcommand{\bb}{\mathbb}
\def\R{\mathbb R}
\def\F{\mathbb F}
\def\Q{\mathbb Q}
\def\Z{\mathbb Z}
\def\C{\mathbb C}
\def\D{\mathbb D}
\def\P{\mathbb P}
\def\N{\mathbb N}
\def\d{\mathrm d}
\def\td{\tilde}
\def\ra{\rightarrow}
\def\pt{\partial}
\def\ee{\varepsilon}
\def\wt{\widetilde}
\def\gcd{\operatorname{gcd}}
\DeclareMathOperator\GG{G}
\DeclareMathOperator\GL{GL}
\DeclareMathOperator\SO{SO}
\DeclareMathOperator\Diff{Diff}
\newtheorem{innercustomthm}{Theorem}
\newenvironment{customthm}[1]
{\renewcommand\theinnercustomthm{#1}\innercustomthm}
{\endinnercustomthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{nonumlemma}{Lemma}
\newtheorem*{nonumtheorem}{Theorem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{statement}[theorem]{Statement}
\newtheorem{heuristic}[theorem]{Heuristic}
\newtheorem*{problem}{Problem}
\newtheorem*{claim}{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{property}[theorem]{Property}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\title[Irreducibility and Galois Groups]{Irreducibility and Galois Groups of Random Polynomials}
\date{}
\author[Hao]{Hanson Hao}
\affiliation{Stanford University}
\email{hhao@stanford.edu}
\author[Navarro]{Eli Navarro}
\affiliation{Stanford University}
\email{enava22@stanford.edu}
\author[Stern]{Henri Stern}
\affiliation{Stanford University}
\email{hsstern@stanford.edu}
\abstract{In 2015, I. Rivin introduced an effective method to bound the number of irreducible integral polynomials with fixed degree $d$ and height at most $N$. In this paper, we give a brief summary of this result and discuss the precision of Rivin's arguments for special classes of polynomials. We also give elementary proofs of classic results on Galois groups of cubic trinomials.}
\subjclass{11C08, 11R32}
\keywords{Number Theory, Probability, Random Polynomials, Galois Theory}
\begin{document}
%\maketitle
\section{Introduction}\label{intro}
Suppose $f(x)=x^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$ is a polynomial with integral coefficients $a_i$ chosen uniformly and independently at random from $[-N,N]$. It is natural to ask for the probability that $f(x)$ is reducible over $\Z$ and the probability that the Galois group of $f(x)$ is the full symmetric group $S_d$. The first question was resolved by R. Chela in 1963 \cite{chl}:
\begin{theorem}\label{chelathm}
Fix a degree $d\geq3$. Suppose $f(x)=x^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$ is a polynomial with integral coefficients $a_i$ chosen uniformly and independently at random from $[-N,N]$. Then as $N$ tends to infinity, the probability that $f(x)$ is irreducible is $\frac{(1+o(1))c_d}{N}$, where $c_d$ is a constant depending only on $d$.
\end{theorem}
The second question, in particular the following 1936 conjecture by van der Waerden \cite{vdw}, is still unresolved.
\begin{conjecture}\label{vdwconj}
For a random polynomial $f(x)$ as in Theorem \ref{chelathm}, as $N$ tends to infinity,
\begin{equation*}
\Pr(\Gal(f(x))=S_d)\geq 1-O(N^{-1+\epsilon})
\end{equation*}
for any $\epsilon>0$.
\end{conjecture}
S. Chow and R. Dietmann \cite{chdi} proved van der Waerden's conjecture for random polynomials of degrees 3 and 4 in 2018, but the general case is still open.
In 2015, I. Rivin showed the following using a very streamlined argument:
\begin{theorem}\label{riv1}
Consider random polynomials $f(x)$ of degree $d$ as in Theorem \ref{chelathm}. Then the probability that $f(x)$ is reducible is at most $O\left(\frac{\log N}{N}\right)$.
\end{theorem}
In this paper, we study the probability that a random polynomial $f(x)$ is reducible over $\Z$ using Rivin's argument. After providing a sketch of his results (with slight variations on his proofs) in Section \ref{rivinmethod}, we apply Rivin's method to more restricted models in Section \ref{further}. In particular, we will define $P_{d,N}=\{x^d+ax^m+b: 01$ is bounded by
\[|V(N)| \ll_M N^{\text{dim}(V)}.\]
\end{lemma}
\begin{proof}
See Lemma 1.2 in \cite{riv}.
\end{proof}
\begin{proof}[Proof of Theorem \ref{riv1}]
Consider
\[f(x)=x^d+a_{d-1}x^{d-1}+\dots+a_0,\] and suppose that it was reducible as $f(x)=g(x)h(x)$ where
\[g(x)=x^k+b_{k-1}x^{k-1}+\dots+b_0.\]
We begin by fixing $a_0$, but we continue to allow $\{a_1,\dots,a_{d-1}\}$ to vary in $[-N,N]$.
Next, we take $\{r_1,\dots,r_d \}$ to be the set of roots of $f(x)$. It is evident that $a_0=\prod_{i=1}^dr_i$. We also have that $b_0|a_0$. Furthermore, we have that the roots of $g(x)$ are some $k-$subset of the roots of $f(x)$ and therefore $b_0$ equals the product of some $k-$subset of the roots of $f(x)$. Expressed another way, we have that
\[\prod_{1\leq i_1\leq\dots\leq i_k\leq d}(r_{i_1}r_{i_2}...r_{i_k}-b_0)=0.\]
Because the product is fixed under all automorphisms of the roots $r_i$ (with $b_0$ fixed), it is a symmetric polynomial. Hence it can be expressed as a polynomial in the elementary symmetric polynomials of the roots of $f$, which are precisely the coefficients of $f$.
As such, there exists some polynomial $g_k$ in the coefficients of $f(x)$ such that
\[g_k(a_1,\dots,a_{d-1})=\prod_{1\leq i_1\leq\dots\leq i_k\leq d}(r_{i_1}r_{i_2}...r_{i_k}-b_0)=0.\]
Note that $g_k$ is in terms of $\{a_1,\dots,a_{d-1}\}$, since at the beginning of this process, we fixed $a_0$ as some integer in $[-N,N]$. With $g_k$, we have a variety in the coefficients of $f(x)$, so we may now use Lemma \ref{szbound}. Before doing so, it is important to show that this variety is non-trivial. In other words, it does not reduce to $0=0$ and the statement $g_k=0$ actually carries significance. A proof of this fact can be found in \cite{PhamXu}.
We see that the dimension of the variety $g_k=0$ is $d-2$ because we have one equation and $d-1$ unknowns. By Lemma \ref{szbound}, \[|g_k(N)|=O(N^{d-2}),\] where $|g_k(N)|$ is the number of $\Z$-points of the variety $\{g_k=0\}$. This tells us that, given a fixed $a_0$, there are at most $O(N^{d-2})$ reducible polynomials with constant $a_0$. Thus, the probability that such a polynomial is reducible at most is $O(1/N)$. We must then account for the variability in $b_0$. It is well-known that the average number of divisors of $n\in[1,N]$ tends to $\log N$. This means that are on average $\log N$ choices for $b_0$ given any $a_0$. Ranging over all nonzero $a_0$ and the associated $\log N$ choices for $b_0$, we have that the probability that a random polynomial is reducible is at most $O\left(\frac{\log N}{N}\right)$.
\end{proof}
\section{Further Discussion of Rivin's Method}\label{further}
It is natural to apply Rivin's counting method, which gives an upper bound on the probability that a random polynomial (selected from some finite set) is reducible, to similar situations. We may ask the following general question:
\begin{question}
When does Rivin's method give a tight upper bound on the number of reducible random polynomials?
\end{question}
Clearly, this is not always the case. From Theorem \ref{chelathm} and Theorem \ref{riv1}, we see that Rivin's method does not give a tight upper bound for any $d\geq3$. We now simplify our discussion a bit and consider the strength of Rivin's method when applied to \textit{random monic trinomials}.
For a fixed degree $d$, consider the set of trinomials of degree $d$ with height bounded by $N$: $$P_{d,N}=\{x^d+ax^m+b: 01$, it can only have $3$ or $q$ as prime factors.
\textbf{Case 1:} $q\equiv 2\mod 3$. Now, if $q|N(d)$, because $N(d)|r^2-3rq+9q^2$, we must have $q|r$ and $q|c$. Then writing $r=qm$ and $c=qn$, we have $m^2-3m+9=(m+3\omega)(m+3\omega^2)=qn^3$. But since $q\equiv 2\mod 3$, it is prime in $\bb{Z}[\omega]$, so either $m+3\omega$ or $m+3\omega^2=(m-3)-3\omega$ is a multiple of the integer $q$, a contradiction.
Thus $N(d)$ is a power of 3, so we may write $r=3m$ and $c=3n$, so that $m^2-mq+q^2=3n^3$. Going through the possibilities, we find that $9\nmid m^2-mq+q^2$, so that $\frac{m+q\omega}{-1+\omega}$, $\frac{m+q\omega^2}{-1+\omega^2}$ are coprime, hence both are cubes in $\bb{Z}[\omega]$. From the argument in Lemma \ref{trilem3}, there must exist integers $a, b$ such that $q=a^3+b^3-6a^2b+3ab^2$, and by Lemma \ref{trilem1}, there are only finitely many solutions $(a,b)$ (setting $b=1$ shows that $a^3+b^3-6a^2b+3ab^2$ is irreducible). Since $r=3m$ is also a polynomial in the $a, b$, there can only be finitely many $(r, c)$ satisfying Equation \ref{trieq4} in this case.
\textbf{Case 2:} $q\equiv 1\mod 3$. If $q|N(d)$, as above, we write $r=qm$ and $c=qn$, so \begin{equation}\label{trieq5} m^2-3m+9=(m+3\omega)(m+3\omega^2)=qn^3\end{equation} Suppose that these two factors are relatively prime. Clearly, neither divides $q$, but $q$ is not prime in $\bb{Z}[\omega]$. Write $q=c^2-ce+e^2$ for some integers $c, e$. We note the following facts:
\begin{itemize}
\item Because $q$ is prime, $c$ and $e$ are coprime.
\item Because $3\nmid q$, the following combinations $(c, e)\equiv (0,0); (1,2); (2,1)\mod 3$ do not occur. In particular, $2c-e$ does not divide $3$.
\item $q$ factorizes as $(c+e\omega)((c-e)-e\omega)$. Furthermore,\\ $c+(c-e)\omega=-\omega^2((c-e)-e\omega)=(-\frac{1}{\omega})((c-e)-e\omega)$ is also a factor of $q$.
\item At least one of $e$ or $c-e$ is not a multiple of 3.
\item $3\nmid m$. Therefore none of $A=m+3\omega$, $B=(-\omega)A=-\omega(m+3\omega)=3+(3-m)\omega$, $C=m+3\omega^2=(m-3)-3\omega$, $D=(-\omega)C=-\omega((m-3)-3\omega)=-3-m\omega$ are real.
\end{itemize}
Now, one of $A, B, C$, or $D$ equals $(c+e\omega)(a+b\omega)^3$, where $q=c^2-ce+e^2$ and $3\nmid e$ (this must happen by the fourth item above). It was necessary to introduce $B$ and $D$ above to possibly correct for the $-\omega^2$ unit. However, it does not matter which of $A, B, C$, or $D$ it is, since each has nonzero $\omega$ component $s$. Equating $\omega$ components, we have \begin{equation}\label{trieq6}s=(e)a^3+(3c-3e)a^2b-(3c)ab^2+(e)b^3.\end{equation}
To apply Lemma \ref{trilem1} and conclude there are only finitely many integral solutions $(a,b)$ (implying that there are only finitely many $m$ that satisfy Equation \ref{trieq5}), we need to show that the right-hand side of Equation \ref{trieq6} is irreducible. To see this, set $b=1$ and apply the transformation $a\to a-1$, so that the right-hand side of Equation \ref{trieq6} becomes \begin{equation}\label{trieq7}(e)a^3+(3c-6e)a^2+(-9c+9e)a+3(2c-e).\end{equation}
By construction, $3\nmid e$, and by the second bullet point, $3\nmid 2c-e$. Hence the above polynomial is Eisenstein at 3, so the right-hand side of Equation \ref{trieq6} is indeed irreducible, and there are only finitely many possibilities for $r=qm$ in this case.
Otherwise, $m+3\omega, m+3\omega^2$ are not relatively prime. Then the norm of their greatest common divisor is a multiple of 3, so that $3|m, 3|n$. Writing $m=3m', n=3n'$, we have \begin{equation}\label{trieq8}(m')^2-m'+1=(m'+\omega)((m'-1)-\omega)=3q(n')^3.\end{equation} We know that $9\nmid (m')^2-m'+1$, and $3=(-1+\omega)(-1+\omega^2)=(-1+\omega)(-2-\omega)$, so $m'+\omega$ divides either $-1+\omega$ or $-2-\omega$, and $(m'-1)-\omega$ divides the other. Note that after this division, the two quotients are coprime. Futhermore, $m'\not=0, \pm1, \pm2$ as the left-hand side of Equation \ref{trieq8} divides both 3 and the prime $q\equiv1\mod 3$, so each of the four possible quotients has nonzero $\omega$ component, even after multiplying each by $-\omega$. Then one of the four possible quotients (possibly adjusting by $-\omega$) is equal to $(c+e\omega)(a+b\omega)^3$ with $q=c^2-ce+e^2, 3\nmid e$. By the same argument as above, this case only gives finitely many possibilities for $r=3qm'$.
The final possibility is that $N(d)$ is a power of 3. Then write $r=3m$ and $c=3n$, so that $m^2-mq+q^2=3n^3$. Going through the possibilities, we find that $9\nmid m^2-mq+q^2$, so we may finish as in Case 1. So this case only gives finitely many possibilities for $r$.
\textbf{Case 3:} $q=3$. Then $N(d)|27q^2$ is a power of 3. Thus $r^2-3rq+9q^2=r^2-9r+81$ is a multiple of 3, whereupon we write $r=3m$ and $c=3n$, so that \begin{equation}\label{trieq9}m^2-3m+9=3n^3.\end{equation} From this we see that $3|m$, which makes the left-hand side of Equation \ref{trieq9} a multiple of 9, implying $3|n$. Writing $m=3m', n=3n'$, we obtain $(m')^2-m'+1=9(n')^3$. But this is a contradiction, as the left-hand side never divides 9. So this case does not give any possibilities for $r$.
Combining the results of cases 0, 1, 2, and 3 (i.e. zero or finitely many possibilities for $r$ in each), we obtain Theorem \ref{tri2}.
\end{proof}
We end with a natural generalization of Theorem \ref{tri2}:
\begin{theorem}\label{triconj1}
For any nonzero integer $c_0$, $p(x)=x^3+c_1x+c_0$ does not have Galois group $S_3$ for only finitely many integers $c_1$.
\end{theorem}
\begin{proof}
This proof relies on more advanced machinery---in particular, results on elliptic curves. See Example 2.5, \cite{KCo}.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
\section{Acknowledgments}
We would like to thank our project mentor, Max Xu, for introducing us to this problem and providing us with the necessary background material. We are grateful for his encouragement throughout the project and for his many valuable insights. The first author would like to thank Keith Conrad for his proof of Theorem \ref{triconj1} and other assistance on the results of Section \ref{cubictri}. Finally, we would like to thank Pawel Grzegrzolka and the rest of the Stanford Undergraduate Research Institute in Mathematics (SURIM) staff for setting up this program, as well as for their flexibility and support during a very unusual summer.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{chl} Chela, R. \textit{Reducible polynomials}. J. Lond. Math. Soc. 38 (1963), 183–188.
\bibitem{chdi} Chow, S. \& Dietmann, R. \textit{Enumerative Galois Theory for Cubics and Quartics}. Advances in Mathematics 372 (2020) 107282. % Crossref. Web.
\url{https://arxiv.org/abs/1807.05820}
\bibitem{KCo} Conrad, K. \textit{Galois groups of cubics and quartics (not in characteristic 2)} (n.d.). \url{http://www.math.uconn.edu/~kconrad/blurbs/galoistheory/cubicquartic.pdf}.
\bibitem{PhamXu} Pham, H. T. \& Xu, M. \textit{Irreducibility of random polynomials of bounded degree} (2020). \url{https://arxiv.org/abs/2002.10554}.
\bibitem{riv} Rivin, I. \textit{Galois Groups of Generic Polynomials} (2015). \url{https://arxiv.org/abs/1511.06446}.
\bibitem{Thue} Thue, A. \textit{Über Annäherungswerte algebraischer Zahlen}. J. reine angew. Math. 135 (1909), 284-305.
\bibitem{Tza} Tzanakis, N. \textit{The diophantine equation $x^3-3xy^2-y^3=1$ and related equations}. J.Number Th. 18, No 2 (1984), 192–205.
\bibitem{vdw} van der Waerden, B. L. \textit{Die Seltenheit der reduziblen Gleichungen und der Gleichungen mit Affekt}. Monatsh. Math. Phys. 43 (1936), 133–147.
\end{thebibliography}
\end{document}