\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{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\F}{\mathbb{F}}
\newcommand{\M}{\mathcal{M}}
\DeclareMathOperator{\ord}{ord}

\title{\texorpdfstring{The invariant $c_M$ of Gallardo and Rahavandrainy at Mersenne prime
exponents, and the case $p=7$}{The invariant c\_M of Gallardo and Rahavandrainy at Mersenne
prime exponents, and the case p=7}}
\author{David Niedbala Giraudin\\\small ORCID 0009-0009-1526-1178}
\date{}

\begin{document}
\maketitle

\begin{abstract}
A Mersenne prime polynomial is an irreducible polynomial over $\F_2$ of the form
$x^a(x+1)^b+1$ with $a,b\ge1$. Gallardo and Rahavandrainy conjectured that, apart from two
exceptions, $\sigma(M^{2h})$ always has an irreducible factor which is not a Mersenne prime.
For a prime $p\ge5$ they proved it for every $M$ outside an exceptional set
$\Sigma_p=\Sigma_p^1\cup\dots\cup\Sigma_p^4$, defined through an integer $c_M$ and an odd integer
$m_M$ read off the leading coefficients of $\sigma(\sigma(M^{p-1}))$, and later they proved
it for every Mersenne prime number $p\ge31$; their method does not reach $p=7$. We compute
$c_M$ exactly when $p=2^d-1$ is a Mersenne prime number: $c_M=d+1$ if $\deg M\ne d$, and
$c_M=d$ if $\deg M=d$. Consequently $\Sigma_p^1$ consists of the Mersenne primes of degree $d$
or $d+1$, $\Sigma_p^2$ is empty, and $\Sigma_p^3$, $\Sigma_p^4$ are described by $m_M=\deg M-d-1$ and
$m_M=\deg M-d$ respectively. For $p=7$ this reduces the conjecture to the
Mersenne primes $M$ with $m_M\in\{\deg M-4,\deg M-3\}$. A direct computation shows that
$\sigma(M^6)$ has a non-Mersenne irreducible factor for every Mersenne prime $M$ of degree at
most $500$, and that $m_M\le17$ in that range. Hence the conjecture holds whenever $7$ divides
$2h+1$ and $\deg M\le500$, and a counterexample with $7\mid 2h+1$ would need
$m_M\ge\deg M-4>496$. A script attached as an ancillary file checks these computations, and
reproduces the table of exceptional sets of Gallardo and Rahavandrainy.
\end{abstract}

\section{Introduction}

For $A\in\F_2[x]$ let $\sigma(A)$ be the sum of the divisors of $A$. A \emph{Mersenne prime}
is an irreducible polynomial $M=x^a(x+1)^b+1$ with $a,b\ge1$; we write $\M$ for the set of
Mersenne primes. Mersenne primes play a central role in the classification of even perfect polynomials over
$\F_2$ \cite{GR-K}, where the following statement is a recurring obstacle.

\begin{conjecture}[Gallardo--Rahavandrainy {\cite[Conjecture~1.2]{GR-MV}}]\label{conj}
Let $h\ge1$ and $M\in\M$, with $M\notin\{1+x+x^3,1+x^2+x^3\}$ or $h\ge2$. Then $\sigma(M^{2h})$
is divisible by an irreducible polynomial which is not a Mersenne prime.
\end{conjecture}

If $p$ is a prime dividing $2h+1$, then $\sigma(M^{p-1})=(M^p-1)/(M-1)$ divides
$\sigma(M^{2h})$, so it suffices to treat $2h+1=p$ prime. Put
\[
S=\sigma(M^{p-1})=\Phi_p(M),\qquad U=\sigma(S),\qquad W=U+S+1,
\]
where $\Phi_p$ is the $p$-th cyclotomic polynomial. Following \cite{GR-MV}, let
$\alpha_l(F)$ be the coefficient of $x^{\deg F-l}$ in $F$,
\[
c_M=(p-1)\deg M-\deg W=\deg S-\deg W,
\]
and, when $\deg W$ is even, let $m_M$ be the least odd $l$ with $\alpha_l(W)=1$. With
$n=\deg M$, the exceptional sets of \cite{GR-MV} are
\begin{align*}
\Sigma_p^1&=\{M\in\M:\ c_M=n\},\\
\Sigma_p^2&=\{M\in\M:\ c_M=n+1,\ c_M\text{ odd}\},\\
\Sigma_p^3&=\{M\in\M:\ c_M+m_M=n,\ c_M\text{ even}\},\\
\Sigma_p^4&=\{M\in\M:\ c_M+m_M=n+1,\ c_M\text{ even},\ m_M\ge3\},
\end{align*}
and $\Sigma_p=\Sigma_p^1\cup\Sigma_p^2\cup\Sigma_p^3\cup\Sigma_p^4$.
Gallardo and Rahavandrainy proved that for $p\ge5$ prime and $M\notin\Sigma_p$, $\Phi_p(M)$ has
a non-Mersenne irreducible factor \cite[Theorem~1.1]{GR-MV}, and tabulated the sizes of the
$\Sigma_p^j$ for small $p$ \cite[Table~1]{GR-MV}. In \cite[Proposition~1.1]{GR-K} they settled the conjecture whenever $2h+1$ has a prime
divisor in an explicit set which contains every Mersenne prime number other than $7$, and
every prime $p$ with $\ord_p(2)\equiv0\pmod 8$; for a Mersenne prime number $p\ge31$ this is
\cite[Lemma~4.17]{GR-K}. The case $p=7$ is left open there.

Our main result computes $c_M$ when $p$ is a Mersenne prime number.

\begin{theorem}\label{thm:c}
Let $d\ge3$ be such that $p=2^d-1$ is prime, and let $M$ be a Mersenne prime of degree $n$.
Then
\[
c_M=\begin{cases} d+1 & \text{if } n\ne d,\\ d & \text{if } n=d.\end{cases}
\]
\end{theorem}

\begin{corollary}\label{cor:sigma}
Under the hypotheses of Theorem~\ref{thm:c},
\begin{itemize}
\item $\Sigma_p^1$ is the set of Mersenne primes of degree $d$ or $d+1$;
\item $\Sigma_p^2=\emptyset$;
\item $\Sigma_p^3=\{M\in\M:\ \deg M\ne d,\ m_M=\deg M-d-1\}$ and
$\Sigma_p^4=\{M\in\M:\ \deg M\ne d,\ m_M=\deg M-d,\ m_M\ge3\}$.
\end{itemize}
\end{corollary}

For $p\ge31$ the conjecture is already known \cite{GR-K}, and Corollary~\ref{cor:sigma} only
describes the exceptional sets of \cite[Theorem~1.1]{GR-MV}. For $p=7$ it gives the following
reduction, which we complete by a computation in Section~\ref{sec:p7}.

\begin{corollary}\label{cor:p7}
Let $M\in\M$. If $\sigma(M^6)$ has no irreducible factor other than Mersenne primes, then
either $\deg M\in\{3,4\}$, or $m_M\in\{\deg M-4,\ \deg M-3\}$.
\end{corollary}

\begin{proposition}\label{prop:comp}
For every Mersenne prime $M$ with $\deg M\le500$, $\sigma(M^6)$ has an irreducible factor which
is not a Mersenne prime. In that range $m_M\le17$, and $\Sigma_7$ consists of the four
Mersenne primes of degree $3$ and $4$ (in $\Sigma_7^1$), the two of degree $6$ in
$\Sigma_7^4$, and two of degree $7$ in $\Sigma_7^3$.
\end{proposition}

Consequently, Conjecture~\ref{conj} holds for every $h$ with $7\mid2h+1$ and every $M$ of degree
at most $500$; beyond, a counterexample with $7\mid 2h+1$ would need $m_M\ge\deg M-4>496$.

\section{Proof of Theorem \ref{thm:c}}

We work in the field $\F_2((1/x))$ of Laurent series in $1/x$, where every non-zero
polynomial $F$ is invertible and $F^{-1}=x^{-\deg F}(1+O(x^{-1}))$.

\begin{lemma}\label{lem:kappa}
Let $S=P_1\cdots P_k$ be a product of distinct irreducible polynomials, $r=\min_i\deg P_i\ge2$,
$\kappa$ the number of $i$ with $\deg P_i=r$, and $T=\sigma(S)+S$. In $T/S$, the coefficient of
$x^{-j}$ vanishes for $j<r$ and equals $\kappa\bmod2$ for $j=r$. If no $P_i$ has degree $r+1$,
the coefficient of $x^{-r-1}$ equals $\sum_{\deg P_i=r}a_i\bmod2$, where $a_i$ is the
coefficient of $x^{r-1}$ in $P_i$. In particular $\deg T=\deg S-r$ when $\kappa$ is odd.
\end{lemma}

\begin{proof}
As $S$ is squarefree, $\sigma(S)=\prod_i(1+P_i)$ and
$T/S=\prod_i(1+P_i^{-1})-1=\sum_{\emptyset\ne I}\prod_{i\in I}P_i^{-1}$. A product over $|I|\ge2$
has valuation at least $2r\ge r+2$. A single $P_i^{-1}$ with $\deg P_i\ge r+2$ starts at
$x^{-r-2}$, and for $\deg P_i=r$ one has $P_i^{-1}=x^{-r}(1+a_ix^{-1}+O(x^{-2}))$. Finally
$T=S\cdot(T/S)$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:c}]
Since $p=2^d-1$ is prime, $d$ is prime, hence odd as $d\ge3$, and $\ord_p(2)=d$. Recall that
$S=\Phi_p(M)$ is squarefree \cite[Lemma~2.3]{GR-MV}.

\emph{Degrees of the factors.} Let $\gamma$ be a root of $S$ in an algebraic closure of $\F_2$.
Then $M(\gamma)^p=1$, and $M(\gamma)\ne1$ since $\Phi_p(1)=p$ is odd. So $M(\gamma)$ has
multiplicative order $p$ in $\F_2(\gamma)^\times$, and $d=\ord_p(2)$ divides
$[\F_2(\gamma):\F_2]$. Every irreducible factor of $S$ has degree divisible by $d$; in
particular there is none of degree $d+1$.

\emph{The factors of degree $d$.} As $d$ is prime, the elements of $\F_{2^d}\setminus\F_2$
are exactly the roots of the $N=(2^d-2)/d$ irreducible polynomials of degree $d$, each root
once. Let $\beta\in\F_{2^d}\setminus\F_2$ with $M(\beta)\ne0$. Then $M(\beta)\ne1$, for
otherwise $\beta^a(\beta+1)^b=0$; and $M(\beta)^p=1$ since $\F_{2^d}^\times$ has order $p$. As
$p$ is prime, $M(\beta)$ is a root of $\Phi_p$, that is, $S(\beta)=0$. If $M(\beta)=0$, then
$S(\beta)=\Phi_p(0)=1$. Hence the irreducible factors of degree $d$ of $S$ are the irreducible
polynomials of degree $d$ other than $M$ (this is \cite[Corollary~4.4]{GR-K}), and their number
is $\kappa=N$ if $n\ne d$, $\kappa=N-1$ if $n=d$. By Fermat's little theorem $d$ divides
$2^{d-1}-1$, so $N=2(2^{d-1}-1)/d$ is even.

\emph{Case $n=d$.} Then $\kappa$ is odd, the smallest degree of a factor is $d$, and
Lemma~\ref{lem:kappa} gives $\deg T=\deg S-d$, where $T=\sigma(S)+S=W+1$.

\emph{Case $n\ne d$.} Then $\kappa=N$ is even and the coefficient of $x^{-d}$ in $T/S$
vanishes. The coefficient of $x^{-d-1}$ is the sum of the coefficients of $x^{d-1}$ of all
irreducible polynomials of degree $d$, that is, the sum of their roots, which is
$\sum_{\beta\in\F_{2^d}}\beta-(0+1)=1$. Hence $\deg T=\deg S-d-1$.

In both cases $\deg T\ge1$, so $\deg W=\deg T$ and $c_M=\deg S-\deg W$ has the stated value.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:sigma}]
If $n=d$, then $c_M=d=n$ is odd: $M\in\Sigma_p^1$, and $M$ lies in none of the other sets,
which require $c_M=n+1$ or $c_M$ even. If $n\ne d$, then $c_M=d+1$ is even, $M\in\Sigma_p^1$ if
and only if $n=d+1$, $M\notin\Sigma_p^2$, and the conditions defining $\Sigma_p^3$ and
$\Sigma_p^4$ become $m_M=n-d-1$ and $m_M=n-d$, $m_M\ge3$.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:p7}]
Apply \cite[Theorem~1.1]{GR-MV} with $p=7$, $d=3$, and Corollary~\ref{cor:sigma}.
\end{proof}

\begin{remark}
The two Mersenne primes of degree $3$ are the exceptions of Conjecture~\ref{conj} for $h=1$;
for $p=7$ they lie in $\Sigma_7^1$. The method of \cite{GR-K} uses an irreducible factor of
degree $\ord_p(2)$ of $\Phi_p(M)$ which is not a Mersenne prime; for $p=7$ both irreducible
polynomials of degree $3$ are Mersenne primes, which is why that case stays open.
\end{remark}

\section{The case \texorpdfstring{$p=7$}{p=7}}\label{sec:p7}

\begin{proof}[Proof of Proposition~\ref{prop:comp}]
For each pair $(a,b)$ with $a,b\ge1$ and $a+b\le500$ such that $M=x^a(x+1)^b+1$ is
irreducible, we factored $S=\Phi_7(M)$, which has degree $6\deg M$, computed $U$, $W$, $c_M$
and $m_M$, and checked that some irreducible factor $P$ of $S$ is not a Mersenne prime, that
is, $P+1$ is not of the form $x^i(x+1)^j$. Table~\ref{tab:m} gives the largest value of
$m_M$ and the degrees at which it is first reached, and the members of $\Sigma_7$ found.
\end{proof}

\begin{table}[ht]
\centering
\begin{tabular}{lr}
\toprule
Mersenne primes $M$ with $2\le\deg M\le500$ & 1203\\
largest $m_M$ & 17\\
first degree with $m_M=3,5,7,9,11,13,15,17$ & 2, 7, 5, 44, 84, 177, 201, 425\\
$\Sigma_7^1$ & $\deg M\in\{3,4\}$ (four polynomials)\\
$\Sigma_7^3$ & $x^3(x+1)^4+1$, $x^4(x+1)^3+1$\\
$\Sigma_7^4$ & $x(x+1)^5+1$, $x^5(x+1)+1$\\
\bottomrule
\end{tabular}
\caption{The computation of Proposition~\ref{prop:comp} ($p=7$).}\label{tab:m}
\end{table}

The members of $\Sigma_7^3\cup\Sigma_7^4$ of degree between $5$ and $100$ agree with the counts
$2$ and $2$ of \cite[Table~1]{GR-MV}. In the range computed $m_M$ grows very slowly; Corollary~\ref{cor:p7} shows that a bound
$m_M<\deg M-4$ for all Mersenne primes of degree larger than $500$ would settle
Conjecture~\ref{conj} for every $h$ with $7\mid2h+1$.

\section{Verification}

The ancillary file \texttt{VERIFY\_mersenne7.py} (Python~3 with \texttt{python-flint}) checks:
Theorem~\ref{thm:c} for $p=7$ ($\deg M\le40$), $p=31$ ($\deg M\le24$), $p=127$ ($\deg M\le12$) and
$p=8191$ ($\deg M\le3$), together with the two facts used in its proof and the parity of
$\kappa$; Corollary~\ref{cor:sigma} on the same data; all thirteen rows of
\cite[Table~1]{GR-MV}, which it reproduces exactly; and Proposition~\ref{prop:comp}. Every
factorisation used for Theorem~\ref{thm:c} and Proposition~\ref{prop:comp} is accepted only if
its product is the polynomial and every factor passes a Rabin irreducibility test. The default
run takes less than a minute; \texttt{python3 VERIFY\_mersenne7.py full} takes less than half an hour.

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

\raggedright
\begin{thebibliography}{9}

\bibitem{GR-K} L. H. Gallardo and O. Rahavandrainy, \emph{All even (unitary) perfect
polynomials over $\F_2$ with only Mersenne primes as odd divisors}, Kragujevac J. Math.
\textbf{49} (2025), no.~4, 639--652.

\bibitem{GR-MV} L. H. Gallardo and O. Rahavandrainy, \emph{Factorization of cyclotomic
polynomial values at Mersenne prime polynomials}, Mat. Vesnik, published online 2025,
doi:10.57016/MV-HMLV9f07; arXiv:2106.10008.

\end{thebibliography}

\end{document}