\documentclass{article}
\usepackage{amsmath,amssymb}
\begin{document}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zn}[1]{(\Z/{#1}\Z)^{*}}

\title{Building polynomials with roots $r^k$, $k\perp n$}
\author{A. Kruppa}
\maketitle


\begin{abstract}
This note presents some of the basic ideas underlying the scheme for building 
a reciprocal Laurent polynomial from its roots as described by Montgomery 
\cite{Montgomery2007}.
\end{abstract}


\section{The set of integers coprime to $n$}
Let $\Zn{n} = \{k + n\Z, k \perp n\}$
\footnote{The notation $a\perp b$ for ``$a$ is relatively prime to $b$''
          follows the suggestion in \cite[4.5]{Graham_Knuth_Patashnik}} 
be the set of residue classes coprime to $n$.
Let $A + B$ denote the set of sums, $A + B = \{a+b, a\in A, b\in B\}$.

Then we have, for $l \perp m$, 
\begin{equation}\label{Zn_sum}
\Zn{lm} = l\Zn{m} + m\Zn{l}.
\end{equation}
and
\begin{equation}
\Zn{p^k} =  \Zn{p} + \sum_{i=1}^{k-1} p^i (\Z/p\Z).
\end{equation}

By definition of the Euler totient function $\varphi$, $|\Z/n\Z| = \varphi(n)$.

\subsection{Positive representatives}
Let $\bar{R}_n = \{1 \leq k < n, k \perp n\}$ be the set of smallest 
positive integers coprime to $n$ and less than $n$, i.e. the smallest 
positive representatives of $\Zn{n}$. 
Unfortunately, (\ref{Zn_sum}) does not immediately carry over to 
$\bar{R}_{lm}$, as $l\bar{R}_m + m\bar{R}_l$ contains integers $\geq lm$.
Since $n-1 \in \bar{R}_n$, we get
$l(m-1) + m(l-1) = 2lm-l-m \geq lm$ for $l,m > 1$. For example, 
$\bar{R}_2 = \{1\}$, $\bar{R}_3 = \{1,2\}$, and 
$3\bar{R}_2 + 2\bar{R}_3 = \{5, 7\} \neq \{1, 5\} = \bar{R}_6$.

% Not really important
% With $1, n-1 \in \bar{R}_n$, we have 
% $a \in l\bar{R}_m + m\bar{R}_l \Rightarrow l+m \leq a \leq 2lm - l - m$. 
% Hence, $l\bar{R}_m + m\bar{R}_l$ lies on an interval of length 
% $2(lm - l - m)$.

\subsection{Representatives symmetric around $0$}
Let $\hat{R}_n = \{|k| \leq (n-1)/2, k \perp n\}$ be the 
set of integers of smallest absolute value that are coprime to $n$, 
for $n > 2$. As for $\bar{R}_n$, (\ref{Zn_sum}) does not carry over, 
as for example $3\hat{S}_2 + 2\hat{S}_3 = \{-1,7\} \neq \{-1,1\}$.

% For odd $l,m,n$, since $-\frac{n-1}{2},\frac{n-1}{2} \in \hat{S}_n$,
% $a \in l\hat{S}_m + m\hat{S}_l \Rightarrow |a| \leq lm-\frac{l+m}{2}$, 
% covering an interval of length $2lm - l - m$.

For $p$ prime, $p \equiv 3 \pmod{4}$, $\hat{R}_p$ can be factored by 
$r=\frac{p+1}{4}$, $\hat{R}_p = \{ -r, r\} + \{-r+1, \ldots, r-1\}$.
The elements of the second set form an arithmetic progression and 
so it can be factored again if its cardinality is composite.

\pagebreak[1]

Montgomery suggests sets with elements symmetric around $0$ and of
even difference, i.e. $\tilde{R}_n = \{2i-n \perp n, 1\leq i \leq n-1 \}$. 
The advantage is that with $p$ prime, the elements of $\tilde{R}_p$ always 
form an arithmetic progression which can be factored as a set of sums, if 
the cardinality of the set is composite. 
% by $\tilde{S}_{lm} = m\tilde{S}_l + \tilde{S}_m$.
The factors are again arithmetic progressions, so $\tilde{R}_p$ 
can always be factored into sets of prime cardinality.
The disadvantage is that $\tilde{R}_p$ covers an interval of length 
$2p-4$, about twice as large as $p-2$ for $\bar{R}_p$ or $p-1$ for 
$\hat{R}_p$.

\subsection{Combining several sets of sums}

For composite, squarefree $n$, we can write
\begin{equation}\label{R_longsum}
R_n \equiv \sum_{p\mid n} \frac{n}{p}R_p \pmod{n}
\end{equation}
where $R_n$ represents any of $\bar{R}_n$, $\hat{R}_n$, 
$\tilde{R}_n$ or similar choice of particular representatives of
the residue classes of $\Zn{n}$.
If the the elements of $R_p$ are bounded below by $\alpha p$ and above by 
$\beta p$, we clearly have lower and upper bounds of the elements of the RHS 
of (\ref{R_longsum}) of $\alpha n\nu(n)$ and $\beta n \nu(n)$, respectively, 
where $\nu(n)$ is the number of prime divisors in $n$. 
This bound grows only linearly in $\alpha$ and $\beta$, so choosing, i.e., 
$\tilde{R}_n$ over $\hat{R}_n$ at most doubles the length of the interval 
covered by the elements of the set of sums.

\section{A polynomial with roots $r^k$, $k\perp n$}

Let
\begin{displaymath}
F_{n,r}(x) = \prod_{k \in S_n} (x-r^k).
\end{displaymath}

Then, with $p \perp n$,
\begin{eqnarray*}
F_{pn,r}(x) & = & \prod_{k \in S_{pn}} \left(x-r^k\right) \\
            & = & \prod_{k \in pS_n + nS_p} \left(x-r^k\right) \\
            & = & \prod_{i \in nS_p} \prod_{j \in pS_n} \left(x-r^{i+j}\right) \\
            & = & \prod_{i \in nS_p} \prod_{j \in S_n} \left(x-r^{i+pj}\right) \\
            & = & \prod_{i \in nS_p} \prod_{j \in S_n} \left(r^i \left(\frac{x}{r^i}-r^{pj}\right)\right) \\
            & = & \prod_{i \in nS_p} r^{i\varphi(n)} \prod_{j \in S_n} \left(\frac{x}{r^i}-r^{pj}\right) \\
            & = & \prod_{i \in nS_p} r^{i\varphi(n)} F_{n,r^p}\left(\frac{x}{r^i}\right)
\end{eqnarray*}

If $F_{n,r}(x) = \sum_{k=0}^{\varphi(n)} f_k x^k$, then 
\begin{eqnarray*}
r^{i\varphi(n)} F_{n,r}\left(\frac{x}{r^i}\right) & = &\\
\sum_{k=0}^{\varphi(n)} r^{i\varphi(n)} f_k x^k r^{-ik} & = & \\
\sum_{k=0}^{\varphi(n)} f_k x^k r^{i(\varphi(n)-k)} &&
\end{eqnarray*}
so we can generate $r^{i\varphi(n)} F_{n,r}\left(\frac{x}{r^i}\right)$ from 
$F_{n,r}(x)$ by multiplying the coefficients from highest to lowest by powers 
of $r$ in an increasing geometric progression, using $2$ multiplications 
per coefficient. This means that to produce $F_{pn,r}(x)$, we need to compute 
$F_{n,r^p}(x)$ only once.

\pagebreak[4]

\section {Converting a polynomial from base $U_i(Y)$ to $V_i(Y)$}

In section 8.1, Montgomery proposes building a polynomial 
$H(Y)=\sum_{j=1}^{n} h_j U_j(Y)$, 
$Y=X+1/X$, in the $U_j(Y) = (X^j - 1/X^j)/(X - 1/X)$ basis and converting it
to $\hat{H}(Y)=\hat{h}_0 + \sum_{j=1}^{n} \hat{h}_j V_j(Y)$ 
in the $V_j(Y) = X^j + 1/X^j$ 
basis in a separate step, using the identity 
$U_j(Y) = V_{j-1}(Y) + U_{j-2}(Y)$, $j\geq 2$, as well as $U_0(Y) = 0$, 
$U_1(Y) = 1$. 
Hence we have
\begin{eqnarray*}
  H(Y) & = & \sum_{j=1}^{n} h_j U_j(Y) \\
  & = & h_1 + \sum_{j=2}^{n} h_j U_j(Y) \\
  & = & h_1 + \sum_{j=2}^{n} h_j (V_{j-1}(Y) + U_{j-2}(Y)) \\
%  & = & h_1 + \sum_{j=1}^{n-1} h_{j+1} V_{j}(Y) + \sum_{j=0}^{n-2} h_{j+2} U_{j}(Y) \\
\end{eqnarray*}
so we can initialise $\hat{H}(Y) = 0$ and compute 
\begin{eqnarray*}
\hat{H}(Y) & := & \hat{H}(Y) + h_i V_{i-1}(Y) \\
H(Y) & := & H(Y) + h_i U_{i-2}(Y) \\
H(Y) & := & H(Y) - h_i U_i(Y),
\end{eqnarray*}
which leaves $H(Y) + \hat{H}(Y)$ invariant, for $i = d, \ldots, 2$. Then we
have $H(Y) = h_1 V_1(Y) = h_1$ left and can set 
\begin{eqnarray*}
\hat{h}_0 & := & \hat{h}_0 + h_1 \\
h_1 & := & 0
\end{eqnarray*}
which again leaves $H(Y) + \hat{H}(Y)$ invariant. We now have $H(Y) = 0$, so
$\hat{H}(Y)$ is equal to the original $H(Y)$, but is represented in standard 
basis.

Since both $h_i$ and $\hat{h_i}$ are accessed in descending order, they can 
overlap. We can have $h_i$ and $\hat{h}_{i-1}$ in the same memory, so the 
update simplifies from
\begin{eqnarray*}
  \hat{h}_{i-1} & := & h_{i} \\
  h_{i-2} & := & h_{i-2} + h_i \\
  h_i & := & h_i - h_i
\end{eqnarray*}
to
\begin{displaymath}
  h_{i-2} := h_{i-2} + h_i,
\end{displaymath}
for $i = d, \ldots, 2$, and the assignment $\hat{h}_0 := h_1$ becomes a no-op.

\begin{thebibliography}{}
\bibitem{Montgomery2007} Peter-Lawrence Montgomery: 
{\it Record Factorizations (I Hope!) Using P-1/FFT. Draft February 8, 2007}. 
Unpublished manuscript.
\bibitem{Graham_Knuth_Patashnik}Graham, Knuth, and Patashnik: 
{\it Concrete Mathematics}. Second edition. 1989. Addison Wesley
\end{thebibliography}

\end{document}