\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[margin=2.6cm]{geometry}
\usepackage{booktabs}
\usepackage[hidelinks]{hyperref}
\renewcommand{\labelitemi}{$\bullet$}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\F}{\mathbb{F}}
\newcommand{\ord}{\operatorname{ord}}

\title{\texorpdfstring{On the largest irreducible factor of an odd perfect polynomial over $\F_2$}{On the largest irreducible factor of an odd perfect polynomial over F2}}
\author{David Niedbala Giraudin\\\small ORCID 0009-0009-1526-1178}
\date{}

\begin{document}
\maketitle

\begin{abstract}
A polynomial $A\in\F_2[x]$ is perfect if it equals the sum $\sigma(A)$ of all its divisors, and
odd if it is coprime to $x^2+x$. Canaday conjectured in 1941 that $1$ is the only odd perfect
polynomial. Known necessary conditions on a counterexample bound its number of distinct
irreducible factors ($\omega\ge5$, Gallardo and Rahavandrainy), its number of irreducible
factors counted with multiplicity and its degree ($\Omega\ge12$ and $\deg A>200$, Cengiz, Pollack
and Trevi\~no), and, when all exponents equal $2$, the degree of its smallest irreducible factor
(at least $40$, Gallardo). We bound a different invariant: every odd perfect polynomial
$A\ne1$ has an irreducible factor of degree at least $20$. The proof reduces the question, for
each $D$, to a finite system: if all irreducible factors of $A$ have degree at most $D$, the
exponents of $A$ belong to an explicit finite set, through the cyclotomic factorisation of
$\sigma(P^h)$ and the multiplicative order of $P$ modulo the factors of $\sigma(P^h)$. An
iterated sieve on the resulting production relations empties for every $D\le19$. The
computation was carried out twice, by two independent programs, with identical results; the
second program is attached as an ancillary file. As a cross-check of the method, the
same programs reproduce, by the orbit argument of Gallardo and Rahavandrainy, the exclusion of
every prime of degree at most $30$ as the smallest factor of a special perfect polynomial, in
agreement with the published bounds.
\end{abstract}

\section{Introduction}

For $A\in\F_2[x]$ let $\sigma(A)$ be the sum of all the divisors of $A$ (all divisors are monic
over $\F_2$). The function $\sigma$ is multiplicative, and
$\sigma(P^h)=1+P+\dots+P^h=(P^{h+1}+1)/(P+1)$ for $P$ irreducible. The polynomial $A$ is
\emph{perfect} if $\sigma(A)=A$, and \emph{odd} if neither $x$ nor $x+1$ divides it. Perfect
polynomials divisible by $x$ or $x+1$ are plentiful: $(x^2+x)^{2^n-1}$ is perfect for every
$n\ge1$, and eleven further ones are known \cite{Can,CPT}. The odd case is open.

\medskip\noindent\textbf{Conjecture} (Canaday \cite{Can}). \emph{The only odd perfect polynomial
over $\F_2$ is $1$.}

\medskip
Let $A\ne1$ be odd and perfect. The following necessary conditions are known.
\begin{itemize}
\item $A$ is a square \cite{Can}.
\item $A$ has at least $5$ distinct irreducible factors \cite{GR07,GR09}.
\item $A$ has at least $12$ irreducible factors counted with multiplicity (see \cite{CPT}), and
$\deg A>200$ \cite[Theorem~1.2]{CPT}.
\item If $A$ is \emph{special}, that is, $A=S^2$ with $S$ squarefree, then $A$ has at least
$10$ distinct irreducible factors, each of them of even degree and congruent to $1$ modulo
$x^2+x+1$ \cite[Lemma~5.3 and Theorem~5.5]{GR07}; its irreducible factor of smallest degree
has degree at least $30$ \cite[Theorem~5.5]{GR07}, and in fact at least $40$
\cite[Theorem~1.2]{Gal22}. Further conditions on the special case are given in \cite{Rah26}.
\end{itemize}
None of these conditions bounds the degree of the \emph{largest} irreducible factor of $A$ in
general: a counterexample of very large degree all of whose irreducible factors have small
degree is not excluded by them. We exclude it below degree $20$.

\begin{theorem}\label{thm:main}
Every odd perfect polynomial $A\ne1$ over $\F_2$ has an irreducible factor of degree at least
$20$.
\end{theorem}

For $D\ge2$ let $S_D$ be the set of irreducible polynomials of $\F_2[x]$ of degree between $2$
and $D$, and let $E_D$ be the set of odd perfect polynomials $A\ne1$ all of whose irreducible
factors lie in $S_D$. Theorem~\ref{thm:main} is the statement $E_{19}=\emptyset$. It is obtained
in two steps.

\begin{theorem}\label{thm:A}
Let $D\ge2$ and $T_D=\{t>1:\ t\mid 2^m-1\text{ for some }m\le D\}$. Every $A\in E_D$ is of the
form $A=\prod_{P\in T}P^{h_P}$ with $T\subseteq S_D$ and $h_P+1\in T_D$ for every $P\in T$.
In particular $E_D$ is finite.
\end{theorem}

\begin{theorem}\label{thm:B}
$E_D=\emptyset$ for every $D\le19$.
\end{theorem}

Theorem~\ref{thm:A} is proved in Section~\ref{sec:finite}. Theorem~\ref{thm:B} is a finite
computation, described in Section~\ref{sec:sieve}; only the case $D=19$ is needed, since
$E_D\subseteq E_{19}$ for $D\le19$. Section~\ref{sec:special} applies the same programs to the
special case, as a check against the published results. Section~\ref{sec:verif} describes the
two independent computations.

Combined with $\omega(A)\ge5$ and with the fact that $A$ is a square, Theorem~\ref{thm:main}
only gives $\deg A\ge2(20+2+3+3+4)=64$, which is weaker than $\deg A>200$. The two statements
bound different invariants and neither implies the other.

\section{Notation and the finiteness of \texorpdfstring{$E_D$}{E\_D}}\label{sec:finite}

Throughout, $P$ denotes an irreducible polynomial of degree at least $2$; such a $P$ satisfies
$P(0)=P(1)=1$. We write $N(k)$ for the number of irreducible polynomials of degree $k$ over
$\F_2$, $\Phi_n(Y)\in\F_2[Y]$ for the reduction modulo $2$ of the $n$-th cyclotomic polynomial,
$\varphi$ for Euler's function, $\ord_t(2)$ for the multiplicative order of $2$ modulo an odd
integer $t$, and $v_R(B)$ for the exponent of the irreducible $R$ in $B$. A polynomial is
\emph{$D$-smooth} if all its irreducible factors have degree at most $D$.

\begin{lemma}[Canaday \cite{Can}]\label{lem:even}
If $A\ne1$ is odd and perfect, every exponent $h_P=v_P(A)$ is even.
\end{lemma}

\begin{proof}
For $P\mid A$ we have $P(0)=1$, hence $\sigma(P^{h_P})(0)=h_P+1$ in $\F_2$. Since $A$ is odd,
$A(0)=1$, and $1=\sigma(A)(0)=\prod_{P\mid A}(h_P+1)$ in $\F_2$. Every $h_P+1$ is therefore
odd.
\end{proof}

\begin{lemma}\label{lem:cyclo}
Let $P$ be irreducible of degree at least $2$, $h\ge2$ even, and $t=h+1$.
\begin{enumerate}
\item[(i)] $\sigma(P^h)=\prod_{d\mid t,\,d>1}\Phi_d(P)$, and the factors $\Phi_d(P)$ are pairwise
coprime.
\item[(ii)] If $d>1$ is odd and $Q$ is an irreducible factor of $\Phi_d(P)$, then $Q\ne P$, and
the multiplicative order of $P$ modulo $Q$ equals $d$. In particular $d\mid 2^{\deg Q}-1$.
\item[(iii)] If $d>1$ is odd, $\Phi_d(P)$ is divisible neither by $x$ nor by $x+1$.
\end{enumerate}
\end{lemma}

\begin{proof}
(i) In $\F_2[Y]$ one has $(Y^t-1)/(Y-1)=\prod_{d\mid t,\,d>1}\Phi_d(Y)$. Since $t$ is odd,
$Y^t-1$ is separable, so the $\Phi_d(Y)$ are squarefree and pairwise coprime; a B\'ezout
relation $U\Phi_d+V\Phi_e=1$ in $\F_2[Y]$ remains one after the substitution $Y=P$.
(ii) For $d\ge2$ the constant term of the cyclotomic polynomial $\Phi_d$ is $1$, so
$\Phi_d(P)\equiv1\pmod P$ and $Q\ne P$. In the field $\F_2[x]/(Q)$ the class of $P$ is a root of
$\Phi_d$; as $Y^d-1$ is separable, the roots of $\Phi_d$ are exactly the elements of order $d$,
and $d$ divides the order $2^{\deg Q}-1$ of the multiplicative group.
(iii) Since $P(0)=P(1)=1$, both values $\Phi_d(P)(0)$ and $\Phi_d(P)(1)$ equal $\Phi_d(1)$
reduced modulo $2$. Now $\Phi_d(1)$ is a prime $q$ if $d$ is a power of $q$, and $1$
otherwise; $d$ being odd, $\Phi_d(1)$ is odd.
\end{proof}

\begin{lemma}\label{lem:exp}
Let $A\in E_D$ and $P\mid A$. Then $h_P+1$ divides $2^m-1$ for some $m\le D$; in particular
$h_P\le2^D-2$.
\end{lemma}

\begin{proof}
By Lemma~\ref{lem:even}, $t=h_P+1\ge3$ is odd. Since $\sigma$ is multiplicative,
$\sigma(P^{h_P})$ divides $\sigma(A)=A$ and is therefore $D$-smooth. By
Lemma~\ref{lem:cyclo}(i), $\Phi_t(P)$ divides $\sigma(P^{h_P})$; it has degree
$\varphi(t)\deg P\ge2$, hence an irreducible factor $Q$ with $\deg Q\le D$, and
Lemma~\ref{lem:cyclo}(ii) gives $t\mid 2^{\deg Q}-1$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:A}]
The irreducible factors of $A\in E_D$ lie in $S_D$ by definition, and $h_P+1\in T_D$ by
Lemma~\ref{lem:exp}. Both sets are finite.
\end{proof}

\begin{remark}
Lemma~\ref{lem:even} is what makes $E_D$ finite. In the even case, $\sigma(x^{2^n-1})=(x+1)^{2^n-1}$,
and the exponents of the perfect polynomials $(x^2+x)^{2^n-1}$ are unbounded.
\end{remark}

The next lemma discards most pairs $(P,h)$ without any polynomial computation.

\begin{lemma}\label{lem:cut}
Let $P$ be irreducible of degree $p\ge2$, let $t>1$ be odd, $m=\ord_t(2)$, and
\[
B(t,D)=\sum_{j\ge1,\ jm\le D} jm\,N(jm).
\]
If $\Phi_t(P)$ is $D$-smooth, then $\varphi(t)\,p\le B(t,D)+\varepsilon$, where
$\varepsilon=p-1$ if $m\le p-1$ and $\varepsilon=0$ otherwise.
\end{lemma}

\begin{proof}
By Lemma~\ref{lem:cyclo}(ii), every irreducible factor $Q$ of $\Phi_t(P)$ satisfies
$t\mid2^{\deg Q}-1$, that is, $m\mid\deg Q$. Write $\Phi_t(P)=\prod_Q Q^{k_Q}$. If $k_Q\ge2$,
then $Q^{k_Q}\mid P^t-1$, and $Q^{k_Q-1}$ divides the derivative $tP^{t-1}P'=P^{t-1}P'$; as
$Q\ne P$, $Q^{k_Q-1}\mid P'$. The polynomials $Q^{k_Q-1}$ being pairwise coprime, their product
divides $P'$, which is non-zero because $P$ is separable; hence
$\sum_Q(k_Q-1)\deg Q\le p-1$. A repeated factor has degree divisible by $m$ and at most $p-1$,
so there is none when $m>p-1$. Finally
$\varphi(t)p=\deg\Phi_t(P)=\sum_Q\deg Q+\sum_Q(k_Q-1)\deg Q$, where the first sum runs over
distinct irreducibles of degrees divisible by $m$ and at most $D$, and is therefore at most
$B(t,D)$.
\end{proof}

\begin{remark}
If $t=2^D-1$ is prime, then $m=D$ and $B(t,D)=D\,N(D)=2^D-2$, whereas
$\varphi(t)p=(2^D-2)p$. Lemma~\ref{lem:cut} therefore discards the exponent $h=2^D-2$ for every
$P$; for $D=13$ this concerns $\sigma(P^{8190})$, of degree $8190\deg P$.
\end{remark}

\section{The sieve and Theorem \ref{thm:B}}\label{sec:sieve}

Fix $D$. A pair $(P,h)$ with $P\in S_D$ and $h+1\in T_D$ is \emph{admissible} if
$\sigma(P^h)$ is $D$-smooth; it is then odd, by Lemma~\ref{lem:cyclo}(iii). Its \emph{production}
is the factorisation $\sigma(P^h)=\prod_R R^{e_R(P,h)}$, computed factor by factor through
Lemma~\ref{lem:cyclo}(i). We say that $(P,h)$ \emph{produces} $R$ if $e_R(P,h)>0$. Since
$\Phi_d(P)\equiv1\pmod P$, a pair never produces its own prime.

A polynomial $A=\prod_{P\in T}P^{h_P}$ is perfect if and only if
$\sum_{P\in T}e_R(P,h_P)=v_R(A)$ for every irreducible $R$. Starting from all primes of $S_D$
and all admissible pairs, we iterate the following three rules until nothing changes:
\begin{enumerate}
\item[(R1)] a pair dies if its prime is dead or if it produces a dead prime;
\item[(R2)] a prime dies if no living pair has it as first coordinate;
\item[(R3)] a prime dies if no living pair produces it.
\end{enumerate}

\begin{proposition}\label{prop:sound}
Let $A\in E_D$. No prime dividing $A$ and no pair $(P,v_P(A))$ with $P\mid A$ is ever killed. In
particular, if the sieve empties, then $E_D=\emptyset$.
\end{proposition}

\begin{proof}
For $P\mid A$ the pair $(P,h_P)$ is admissible: $h_P+1\in T_D$ by Lemma~\ref{lem:exp}, and
$\sigma(P^{h_P})$ divides $\sigma(A)=A$, so it is $D$-smooth and all the primes it produces
divide $A$. Assume that, before some iteration, all these primes and pairs are alive. Rule (R1)
spares $(P,h_P)$, since the primes it produces divide $A$. Rule (R2) spares $P$, which carries the
pair $(P,h_P)$. For (R3), comparing exponents of $P$ in $\sigma(A)=A$ gives
$\sum_{Q\mid A}e_P(Q,h_Q)=h_P>0$ with $e_P(P,h_P)=0$, so some $Q\mid A$, $Q\ne P$, produces
$P$ through a living pair. As $A\ne1$, the sieve does not empty.
\end{proof}

Had the sieve not emptied, an exhaustive search over the surviving primes and exponents would
have been needed; it never was.

\begin{proof}[Proof of Theorem~\ref{thm:B}]
For each $D\le19$ the admissible pairs were computed and the sieve was run to its fixed point.
It empties in every case. Table~\ref{tab:B} gives the counts.
\end{proof}

\begin{table}[ht]
\centering
\begin{tabular}{rrrr@{\qquad}rrrr}
\toprule
$D$ & $|S_D|$ & pairs & iter. & $D$ & $|S_D|$ & pairs & iter.\\
\midrule
2 & 1 & 0 & 1 & 11 & 410 & 164 & 4\\
3 & 3 & 0 & 1 & 12 & 745 & 418 & 4\\
4 & 6 & 4 & 2 & 13 & 1375 & 550 & 4\\
5 & 12 & 4 & 2 & 14 & 2536 & 1086 & 5\\
6 & 21 & 10 & 3 & 15 & 4718 & 1682 & 5\\
7 & 39 & 12 & 3 & 16 & 8798 & 3668 & 5\\
8 & 69 & 39 & 3 & 17 & 16508 & 5598 & 5\\
9 & 125 & 55 & 3 & 18 & 31040 & 12277 & 6\\
10 & 224 & 118 & 4 & 19 & 58634 & 19351 & 6\\
\bottomrule
\end{tabular}
\caption{The sieve of Section~\ref{sec:sieve}: number of primes in $S_D$, number of admissible
pairs, and number of iterations until the sieve is empty.}\label{tab:B}
\end{table}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
If every irreducible factor of an odd perfect $A\ne1$ had degree at most $19$, then $A$ would
lie in $E_{19}$, which is empty by Theorem~\ref{thm:B}.
\end{proof}

\section{A cross-check: the special case}\label{sec:special}

Let $A$ be special, $A=\prod_{P\in T}P^2$ with $T$ a finite set of irreducibles. Then
$\sigma(P^2)=\Phi_3(P)=P^2+P+1$ is the only function involved, and $\sigma(A)=A$ implies that
every irreducible factor of $\Phi_3(P)$, for $P\in T$, belongs to $T$. Every $P\in T$ has even
degree and satisfies $P\equiv1\pmod{x^2+x+1}$ \cite[Lemma~5.3]{GR07}. (The parity of the degree
also follows from Lemma~\ref{lem:cyclo}: $P$ divides $A=\sigma(A)$ and $\Phi_3(P)\equiv1\pmod P$,
so $P$ divides some $\Phi_3(Q)$, and then $3\mid 2^{\deg P}-1$.)

Let $P\in T$ be of smallest degree $d$. Define $O_0=\{P\}$ and let $O_{k}$ be the set of
irreducible factors of the polynomials $\Phi_3(R)$, $R\in O_{k-1}$. All the $O_k$ are contained
in $T$, so every element of every $O_k$ has even degree at least $d$ and is congruent to $1$
modulo $x^2+x+1$. This is the argument of \cite[Corollary~5.4]{GR07}. We say that $P$
\emph{survives to depth $k$} if the elements of $O_1,\dots,O_k$ satisfy these three conditions.

Running this test on every irreducible $P$ of even degree $d\le30$ with
$P\equiv1\pmod{x^2+x+1}$ gives Table~\ref{tab:O}. The column ``rough'' counts the $P$ for which
$\Phi_3(P)$ has no irreducible factor of degree less than $d$. No $P$ survives to depth $4$.
For $d=2$ the only candidate, $x^2+x+1$, is not congruent to $1$, and odd degrees do not
occur.

\begin{table}[ht]
\centering
\begin{tabular}{rrrl}
\toprule
$d$ & $P\equiv1$ & rough & survivors to depth $1,2,3,\dots$\\
\midrule
4 & 1 & 1 & 0\\
6 & 3 & 2 & 2, 0\\
8 & 10 & 4 & 4, 0\\
10 & 33 & 11 & 8, 2, 0\\
12 & 111 & 24 & 20, 6, 0\\
14 & 387 & 82 & 75, 4, 0\\
16 & 1360 & 338 & 317, 29, 0\\
18 & 4842 & 894 & 843, 62, 0\\
20 & 17459 & 2897 & 2696, 186, 0\\
22 & 63519 & 9915 & 9335, 526, 0\\
24 & 232950 & 33464 & 31694, 1721, 12, 0\\
26 & 860265 & 110419 & 105161, 5155, 8, 0\\
28 & 3195465 & 380186 & 363023, 16803, 32, 0\\
30 & 11930067 & 1322127 & 1266736, 53693, 128, 0\\
\bottomrule
\end{tabular}
\caption{The orbit test of Section~\ref{sec:special}, for every irreducible $P$ of degree $d$
congruent to $1$ modulo $x^2+x+1$.}\label{tab:O}
\end{table}

\begin{corollary}
No irreducible polynomial of degree at most $30$ is the factor of smallest degree of a special
perfect polynomial.
\end{corollary}

This is contained in the published results: \cite[Theorem~5.5]{GR07} covers the degrees up to
$28$, and \cite[Theorem~1.2 and Lemma~2.6]{Gal22} extends the bound to $40$. We record it only
as an independent check, by a different procedure, of the degrees $d\le30$. With the three
conditions above, depth $3$ does not suffice from $d=24$ on. For $d=28$ and $d=30$ the first
of the two computations of Section~\ref{sec:verif} tested depth $4$ directly; the intermediate
counts in Table~\ref{tab:O} come from the second.

\section{The computations}\label{sec:verif}

Polynomials over $\F_2$ are encoded as integers, bit $i$ being the coefficient of $x^i$; all
computations are exact. Theorem~\ref{thm:B} and Table~\ref{tab:O} were obtained twice.

\paragraph{First computation (July 2026).} A self-contained Python engine generated the
irreducible polynomials by trial division, computed the admissible pairs through
Lemmas~\ref{lem:cyclo} and~\ref{lem:cut} with a weaker form of the latter, and decided
smoothness by a chain of gcds with $x^{2^k}-x$ followed by equal-degree splitting, every factor
being checked against the list of irreducibles. The orbit test used the same arithmetic, with
the factorisations of the deep levels done by the FLINT library and re-checked by exact
reconstruction and a Rabin irreducibility test. For $D\in\{6,10,13\}$ an end-to-end
reimplementation on FLINT primitives gave the same pairs and productions.

\paragraph{Second computation (October 2026).} The ancillary file \texttt{VERIFY\_canaday.py}
redoes everything with different algorithms: the irreducibles, and in the special case the
candidates $P$ and the rough check, come from a Rabin test and a product-of-gcds test written in
vectorised integer arithmetic; smoothness of $\Phi_t(P)$ is decided by the criterion that a
squarefree $h$ is $D$-smooth if and only if it divides
$\prod_{D/2\le i\le D}(x^{2^i}-x)$; smooth polynomials are factored by FLINT, and the
factorisation is accepted only if its product is the polynomial and every factor belongs to the
list of irreducibles. The factorisations of the orbit test are accepted only after exact
reconstruction and a Rabin test of every factor. The script also checks Lemma~\ref{lem:exp} by
computing $\sigma(P^h)$ directly for all even $h\le2^D-2$, $D\le6$, checks that
Lemma~\ref{lem:cut} does not change the admissible pairs for $D\le12$, and recovers by brute
force the perfect polynomials of degree at most $16$ (twelve of them, none odd). Every count in
Tables~\ref{tab:B} and~\ref{tab:O} is printed by the script and compared with the tables; the
two computations agree on all of them.

Running \texttt{python3 VERIFY\_canaday.py} takes less than a minute and covers $D\le13$ and $d\le22$;
\texttt{python3 VERIFY\_canaday.py full} covers the whole of both tables (about two hours on one core).
The script needs Python~3 with \texttt{numpy} and \texttt{python-flint}.

\paragraph{Acknowledgements.} Technical assistance: Claude (Anthropic).

\raggedright
\begin{thebibliography}{9}

\bibitem{Can} E. F. Canaday, \emph{The sum of the divisors of a polynomial}, Duke Math. J.
\textbf{8} (1941), 721--737.

\bibitem{CPT} U. C. Cengiz, P. Pollack and E. Trevi\~no, \emph{Counting perfect polynomials},
Finite Fields Appl. \textbf{47} (2017), 242--255.

\bibitem{Gal22} L. H. Gallardo, \emph{On the equation $\prod_P\Phi_3(P)=\prod_P P^2$ over
$\F_2[x]$}, Gulf J. Math. \textbf{12} (2022), no.~2, 39--48.

\bibitem{GR07} L. H. Gallardo and O. Rahavandrainy, \emph{Odd perfect polynomials over $\F_2$},
J. Th\'eor. Nombres Bordeaux \textbf{19} (2007), 165--174.

\bibitem{GR09} L. H. Gallardo and O. Rahavandrainy, \emph{There is no odd perfect polynomial over
$\F_2$ with four prime factors}, Port. Math. \textbf{66} (2009), 131--145.

\bibitem{Rah26} O. Rahavandrainy, \emph{On special perfect polynomials over $\F_2$},
arXiv:2606.08640, 2026.

\end{thebibliography}

\end{document}