% The body of the paper, shared by paper/, arxiv/ and AMM/.  Each wrapper
% defines \paperSection, \secref, the environments pf, ptheorem, theorem,
% cor, prop, example, and the switch \ifanonymous, in its own style.
\paperSection{Introduction}

A critical value of a nonconstant $g \in \Z[x]$ is a number $\alpha$ with
$g(\beta) = \alpha$ and $g'(\beta) = 0$ for some $\beta$. Since $\overline{\Q}$ is
closed under polynomial evaluation, every critical value is algebraic.
Schwarz, Vologodsky and Walcher posed the problem of establishing the
reverse implication \cite{svw2017}.
This note solves the problem.

\begin{ptheorem}
  Let $f$ be an irreducible integral polynomial of positive degree. Then there
  exist $F$ and $g$ in $\Z[x]$, with $F$ irreducible and of positive degree,
  such that
  \[
    F \mid g' \quad\text{and}\quad F^{2} \mid f \circ g .
  \]
\end{ptheorem}

The construction in \secref{Scons} was derived independently. Petrov's theorem
\cite{petrov2021} was found later.
The corollary is the statement in the title.

\begin{cor}\label{C3}
  The set of critical values is exactly $\overline{\Q}$.
\end{cor}

\begin{pf}
  Write $f = m_{\alpha}$. If $g(\beta) = \alpha$ and $g'(\beta) = 0$ then
  $\beta$ is a double root of $f \circ g$, since $(f \circ g)' = (f' \circ g)\,g'$,
  so $m_{\beta} \mid g'$ and $m_{\beta}^{2} \mid f \circ g$. Conversely take $F$
  and $g$ from Petrov's theorem. A root $\beta$ of $F$ has $g'(\beta) = 0$ and
  $f(g(\beta)) = 0$, so $g(\beta)$ is a conjugate of $\alpha$, and conjugation
  gives $\alpha$ itself.
\end{pf}

\paperSection{The construction}\label{Scons}

Let $f$ be irreducible of degree $n \geq 1$ and $\alpha$ a root. Write
$f(x) = \sum_{k=0}^{n} a_{k}x^{n-k}$, so that $a_{n} = f(0)$. If $f = x$, then
$g = x^{2}$ and $F = x$ work. Otherwise $f(0) \neq 0$, and since
$\gcd(f,f') = 1$ in $\Q[x]$, the elimination ideal $(f,f') \cap \Z$ is nonzero.
Let $u, v \in \Z[x]$ and $\rho \in \Z$, $\rho \neq 0$, be such that
$u\,f + v\,f' = \rho$, and set $M := \rho\,a_{n}$, $F(x) := f(Mx)/a_{n}$ and
$W(x) := \bigl(v(0)F(x) - v(Mx)\bigr)/\rho$. The polynomial claimed by
Petrov's theorem is
\begin{equation}\label{Eg}
  g(x) := Mx + f(Mx)\,W(x).
\end{equation}

\begin{pf}
  Write $F(x) = \sum_{k=0}^{n} A_{k}x^{n-k}$. From $A_{k} = a_{k}M^{n-k}/a_{n}$
  we get $A_{n} = 1$ and
  $A_{k} = a_{k}\rho^{\,n-k}a_{n}^{\,n-k-1}$ for $k < n$, so $F \in \Z[x]$ with
  $F(0) = 1$, which gives $W(0) = 0$. And $\rho$ divides $M$ and every $A_{k}$
  with $k < n$, so it divides $v(0)F(x) - v(Mx)$ and $W \in \Z[x]$. Therefore
  $g$ is an integral polynomial.

  Let $\beta = \alpha/M$, a root of $F$. Therefore $g(\beta) = \alpha$, and
  $\rho W(\beta) = -v(\alpha)$. Then
  \begin{align*}
    g'(\alpha/M)
      &= M + \rho\,a_{n}f'(\alpha)\,W(\alpha/M)
         + \cancel{f(\alpha)}\,W'(\alpha/M) \\
      &= M - a_{n}f'(\alpha)v(\alpha) = 0 ,
  \end{align*}
  because $u(\alpha)\cancel{f(\alpha)} + v(\alpha)f'(\alpha) = \rho$.
  Hence $\beta$ is a double root of $f \circ g$, and $F$ is irreducible, so
  $F \mid g'$ and $F^{2} \mid f \circ g$ by Gauss.
\end{pf}

Any $\rho$ will do, but $M = \rho\,a_{n}$ multiplies into every coefficient of
$F$, $W$ and $g$, so the reduced resultant gives the answer with the smallest
coefficients.

\paperSection{Classification}\label{Sclass}

We say a polynomial $p$ is reducible if it is not primitive, or $p = fg$
with $\deg f, \deg g < \deg p$, and irreducible otherwise. For
$\alpha \in \overline{\Q}$ we normalize the minimal polynomial $m_{\alpha}$
with positive leading coefficient for uniqueness.
Say that $\alpha$ is a critical value for $\beta \in \overline{\Q}$ if some
$g \in \Z[x]$ has $g(\beta) = \alpha$ and $g'(\beta) = 0$, and call such a $g$
a solution for $\beta$. Here we classify which $g$ can appear for a given
$\alpha$. Let $P \in \Z[x]$ with $\deg P > 0$. By the fundamental theorem
of algebra, $P(x) - \alpha$ has a root $\beta$. Moreover this root is
algebraic because it is a root of $m_{\alpha} \circ P \in \Z[x]$.

\begin{theorem}\label{Tcoset}
  Let $P \in \Z[x]$ be nonconstant, let $\beta$ be a root of $P - \alpha$,
  and write $m_{\alpha} \circ P = m_{\beta}\,h$ with $h \in \Z[x]$. Then
  $\alpha$ is a critical value for $\beta$ if and only if
  \[
    m_{\alpha}'(\alpha) \mid h(\beta) \ \text{ in } \Z[\beta] .
  \]
  In that case,
  for $Q \in \Z[x]$ with $Q(\beta) = -h(\beta)/m_{\alpha}'(\alpha)$,
  $g_{0} = P + m_{\beta}Q$ is a solution for $\beta$, and the solutions $g$
  for $\beta$ are exactly $g \in g_{0} + m_{\beta}^{2}\,\Z[x]$.
\end{theorem}

\begin{pf}
  By Gauss's lemma $m_{\beta}$ divides $m_{\alpha} \circ P$ in $\Z[x]$, since
  $m_{\beta}$ is irreducible. Differentiating $m_{\alpha} \circ P = m_{\beta}h$
  and evaluating at $\beta$ gives
  $m_{\alpha}'(\alpha)P'(\beta) = m_{\beta}'(\beta)h(\beta)$, where
  $m_{\alpha}'(\alpha), m_{\beta}'(\beta) \neq 0$, so the two
  divisibilities are equivalent and $-h(\beta)/m_{\alpha}'(\alpha)$ equals
  $-P'(\beta)/m_{\beta}'(\beta)$. Now $g_{0}(\beta) = P(\beta) = \alpha$ and
  \[
    g_{0}'(\beta) = P'(\beta) + m_{\beta}'(\beta)Q(\beta) = 0 .
  \]
  If $g$ is a solution for $\beta$ then $g - P$ vanishes at $\beta$, so
  $g = P + m_{\beta}q$ with $q \in \Z[x]$, and
  $0 = g'(\beta) = P'(\beta) + m_{\beta}'(\beta)q(\beta)$ gives the
  divisibility and $q(\beta) = Q(\beta)$, so $m_{\beta} \mid q - Q$ and
  $g \in g_{0} + m_{\beta}^{2}\Z[x]$; conversely every $g_{0} + m_{\beta}^{2}r$
  has value $\alpha$ and derivative $0$ at $\beta$.
\end{pf}


Since the solutions for $\alpha$ are cosets $g \in g_{0} + m_{\beta}^{2}\,\Z[x]$,
$\deg g$ is unbounded above. So the natural question is what is the
smallest $\deg g$ for $\alpha$; we do not answer that question, but we provide the
following lower bound.

\begin{prop}\label{Pdeg}
  If $g$ is a nonconstant solution for $\beta$, then $\deg g > \deg \alpha$.
\end{prop}

\begin{pf}
  Since $\alpha = g(\beta)$, $\Q(\alpha) \subseteq \Q(\beta)$, so
  $\deg \beta \geq \deg \alpha$. And $g' \neq 0$ vanishes at $\beta$, so
  $m_{\beta} \mid g'$ and $\deg g - 1 \geq \deg \beta$.
\end{pf}

Each line below is a closed identity, checkable by expansion.

\begin{example}[$f = qx - p$, $p \neq 0$, $\gcd(p,q) = 1$]
  Here $f' = q$ and $p = qx - f$, so $(f,f') \cap \Z = \Z$ and $\rho = 1$.
  Choose $a, b \in \Z$ with $ap + bq = 1$ and take $u = -a$, $v = ax + b$. Then
  $f(0) = -p$, $M = -p$, $F = qx + 1$, $W = x$, and
  \[
    g = -pqx^{2} - 2px, \qquad
    g' = -2p\,(qx+1), \qquad
    f \circ g = -p\,(qx+1)^{2}.
  \]
\end{example}

\begin{example}[$f = ax^{2} + bx + c$]\label{Exquad}
  This is irreducible of degree $2$ exactly when $a \neq 0$, $\gcd(a,b,c) = 1$,
  and $D := b^{2} - 4ac$ is not a square. Since $(f')^{2} = 4af + D$,
  \[
    \rho = \operatorname{Res}(f,f') = -aD, \qquad u = 4a^{2}, \qquad v = -af',
  \]
  so $M = -acD$ and
  \[
    F = a^{3}cD^{2}x^{2} - abD\,x + 1, \qquad
    W = a^{3}bcD\,x^{2} - a(b^{2}-2ac)\,x ,
  \]
  \[
    g = a^{6}bc^{3}D^{3}x^{4} - 2a^{4}c^{2}(b^{2}-ac)D^{2}x^{3}
        + a^{2}bc(b^{2}-ac)D\,x^{2} - 2ac(b^{2}-3ac)\,x ,
  \]
  with $g' = 2ac\bigl(2a^{2}bcD\,x - (b^{2}-3ac)\bigr)F$. For $b = 0$ the
  quartic term drops and $\deg g = 3 = n+1$, the least any solution can have.
  On $f = x^{2} - d$ that cubic is $g(x) = -D_{3}(4d^{2}x, d)/(2d)$, a rescaling
  of the Dickson polynomial $D_{3}(x,d) = x^{3} - 3dx$, whose pair of critical
  values is classical.

\end{example}

\begin{example}[$f = x^{3}-x-1$]
  The construction gives $M = 23$ and a sextic. Then a search exhibits a
  quintic. Let $\theta$ be a root of $f$. Then Theorem~\ref{Tcoset}
  with $\beta = 1/(\theta^{2} - \theta + 2)$, so that
  $m_{\beta} = 23x^{3} - 23x^{2} + 8x - 1$, $P = 46x^{2} - 23x + 3$, and
  $Q = -1058x^{2} + 667x - 115$, gives the quintic
  \[
    g = -24334x^{5} + 39675x^{4} - 26450x^{3} + 9085x^{2} - 1610x + 118 .
  \]
  This is the least possible degree. By Proposition~\ref{Pdeg} a solution
  has degree at least $4$, and degree $4$ cannot happen. In fact no
  $g \in \Q[x]$ of degree $4$ has $\theta$ as a critical value. Suppose
  $g(\beta) = \theta$ and $g'(\beta) = 0$ with $\deg g = 4$. Up to a rational
  translation of $x$, $g'$ is a multiple of a depressed cubic,
  $g' = 4a\,(x^{3} + ux + w)$ with $a, u, w \in \Q$, $a \neq 0$, so
  $g = a\,h + r$ with $h = x^{4} + 2ux^{2} + 4wx$ and $r \in \Q$, and the
  critical values of $g$ are $a s_{i} + r$ with $s_{i} = h(\beta_{i})$, where
  the $\beta_{i}$ are the roots of $x^{3} + ux + w$. Since
  $\beta_{i}^{3} = -u\beta_{i} - w$, $s_{i} = u\beta_{i}^{2} + 3w\beta_{i}$,
  and the characteristic polynomial of this element of
  $\Q[\beta]/(\beta^{3} + u\beta + w)$ is
  \[
    s(z) = z^{3} + 2u^{2}z^{2} + (u^{4} + 18uw^{2})\,z + 2u^{3}w^{2} + 27w^{4} .
  \]
  Now $s(z)$ is a monic cubic over $\Q$ with root $(\theta - r)/a$, whose
  minimal polynomial is $a^{-3}f(az + r)$, so $s(z) = a^{-3}f(az + r)$. The
  $z^{2}$ coefficient gives $r = 2au^{2}/3$, and with it the $z$ and constant
  coefficients become $-1/a^{2} = 18uw^{2} - u^{4}/3$ and
  $-1/a^{3} = 27w^{4} - 10u^{3}w^{2} - 2u^{6}/27$. The first forces
  $u \neq 0$, so $\sigma = 27w^{2}/u^{3} \in \Q$, and the two equations read
  $-1/a^{2} = -u^{4}(1 - 2\sigma)/3$ and
  $-1/a^{3} = u^{6}(\sigma^{2} - 10\sigma - 2)/27$. Cubing the first and
  squaring the second gives $-1/a^{6}$ and $1/a^{6}$ on the left, so adding
  them, $u$ and $a$ drop out:
  $(\sigma^{2} - 10\sigma - 2)^{2} = 27(1 - 2\sigma)^{3}$, that is,
  $\sigma^{4} + 196\sigma^{3} - 228\sigma^{2} + 202\sigma - 23 = 0$. This is
  monic with integer coefficients, so a rational root is an integer dividing
  $23$. But the polynomial takes the values $148$ and $-648$ at
  $\sigma = \pm 1$ and is nonzero at $\pm 23$. So there is no rational
  $\sigma$, a contradiction.
\end{example}

\begin{example}[Dedekind's cubic]\label{Ex85}
  $f = x^{3} - x^{2} - 2x - 8$, the standard example of a field whose ring of
  integers is not monogenic. Here $2$ is a common index divisor
  \cite{dedekind1878}. With $u = 21x - 125$, $v = -7x^{2} + 44x - 3$,
  $\rho = 1006$, $f(0) = -8$, $M = -8048$,
  \begin{align*}
    F &= 65158925824x^{3} + 8096288x^{2} - 2012x + 1, \\
    W &= -194310912x^{3} + 426544x^{2} + 358x,
  \end{align*}
  \[
    \begin{aligned}
      g = {}& 101288722414414331904x^{6} \\
            & {} - 209759614012620800x^{5} - 217370176548864x^{4} \\
            & {} - 14767629312x^{3} + 2350016x^{2} - 10912x .
    \end{aligned}
  \]
\end{example}

\paperSection{Computerization}\label{Sformal}

The construction of $g$ was provided by AI. However, the crucial step that
allowed the agent to provide answers was my proof of Corollary~\ref{C3}. Once I
recast the problem as the search for an irreducible polynomial $F$ satisfying
the hypotheses of Petrov's theorem, the agent found $g$ for a general linear
polynomial (which one can do by hand), then for a general quadratic, then for a
general cubic, and finally gave the formula for $g$ for arbitrary $f$.
Previously, all agents I tried failed to construct $g$ for $x^{3}-x-1$.
An agent later found Petrov's theorem on MathOverflow after I insisted it
should do a deep literature search, including all the classical literature.
The development above has been formalized in Lean~4 \cite{lean4} against
Mathlib \cite{mathlib}, in about $1{,}700$ lines\ifanonymous\ (repository
withheld for double-blind review)\else\ \cite{repo}\fi. An online
calculator\ifanonymous\ (withheld for double-blind review)\else\ \cite{app}\fi\ is
provided for the reader to verify the construction. It
runs the construction in the browser and, if $\alpha$ is real, generates a
Desmos plot that allows the reader to check visually that it is a critical
value. The implemented program does have a virtue that Petrov's construction
doesn't have. Because it uses the reduced resultant, the coefficients come out
as small as possible.