\documentclass[11pt]{amsart} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=1in]{geometry} \usepackage{booktabs} \usepackage[hidelinks]{hyperref} \emergencystretch=3em \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem*{theoremA}{Theorem A} \newtheorem*{theoremB}{Theorem B} \newtheorem*{theoremC}{Theorem C} \newtheorem*{theoremD}{Theorem D} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\ord}{\operatorname{ord}} \newcommand{\cO}{\mathcal{O}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\F}{\mathbb{F}} \DeclareMathOperator{\Nm}{N} \title[Mersenne divisors under doubling]{Divisors of Mersenne numbers under doubling, and prime factors of $2^p-1$\\ beside near-Wagstaff numbers: sharp elementary bounds,\\ exact reductions, and barriers} \author{Sunay Venkat} \date{November 2026} \subjclass[2020]{Primary 11A51, 11N25; Secondary 11R18, 11B83} \keywords{Mersenne numbers, divisor function, Wagstaff primes, cyclotomic polynomials, Erd\H{o}s problems} \begin{document} \begin{abstract} Let $f(n)=\sum_{k\le n}\tau(2^k-1)$. Erd\H{o}s asked whether $f(2n)/f(n)$ tends to a limit (Problem~\#893). Kova\v{c} and Luca proved $\limsup f(2n)/f(n)=\infty$. Whether the limit is $+\infty$ is open. We prove that $f(2n)\ge 3f(n)$ for every $n$, with equality exactly for $n\in\{1,2,4\}$. If the Fermat number $F_a$ is composite, then $f(2n)\ge\bigl(4-\tfrac{16}{3\cdot2^{a-2}+4}\bigr)f(n)$ on $[2^a,2^{a+1})$. Hence $f(2n)\ge\tfrac{24}{7}f(n)$ for $32\le n<2^{33}$, and $\liminf f(2n)/f(n)\ge4$ if all large Fermat numbers are composite. For every $C$, the set $\{n:f(2n)>Cf(n)\}$ meets every chain $n,2n,\dots,2^{J(C)-1}n$ and has lower density at least $1/(2^{J(C)}-1)$. We reduce $f(2n)/f(n)\to\infty$ exactly to a statement about indices whose odd part has few divisors. This gives a conditional theorem whose hypothesis is far weaker than that of Kova\v{c} and Luca. We also show that one natural route to a negative answer needs primes $p$ for which $\tau(2^p+1)$ is bounded and $\omega(2^p-1)=\exp\bigl((\log2+o(1))\log p/\log\log p\bigr)$. This leads to the constant $\beta_K=\limsup_{p:\,\tau(2^p+1)\le K}\log\omega(2^p-1)\,\log\log p/\log p$ and the conjecture $\beta_K=0$. We do not settle it. We prove that a disproof would settle two open problems at once. We give barrier theorems, in sketch form: axioms that capture the bounded-depth properties of the factorizations are consistent with $\beta_K=0$ and with $\beta_K=\infty$. We give an ``honest ideal'' family showing that exact divisibility at the level of ideals is still not enough. We prove the function-field analogue, which holds uniformly in $p$. All numerical claims were re-checked against independent factor tables. \end{abstract} \maketitle \tableofcontents %====================================================================== \section{Introduction} %====================================================================== \subsection{Erd\H{o}s Problem \#893} Write $\tau$ for the divisor function, $\omega$ for the number of distinct prime factors, and \[ T(k)=\tau(2^k-1),\qquad f(n)=\sum_{k\le n}T(k). \] Erd\H{o}s~\cite{Er98} asked whether $f(2n)/f(n)$ tends to a limit; this is Problem~\#893 in~\cite{EP}. He remarked that $f$ probably has no simple asymptotic formula because it grows too fast. Kova\v{c} and Luca~\cite{KL} proved $\limsup_{n}f(2n)/f(n)=\infty$, so no finite limit exists. They also proved that $f(2n)/f(n)\to\infty$ under either of two conjectures. One of them is \begin{equation}\label{eq:KL} \omega(\Phi_d(2))\le 10\log d\qquad\text{for all sufficiently large } d. \end{equation} Whether $f(2n)/f(n)\to\infty$ unconditionally, equivalently whether $\liminf f(2n)/f(n)=\infty$, is open. To our knowledge no lower bound for the $\liminf$ beyond the trivial $f(2n)>2f(n)$ has been recorded. That trivial bound, and a $\liminf\ge4$ conditional on a different hypothesis, appear in an informal online report~\cite{Wh26}. Part~I proves the following. \begin{theoremA}[Sharp constant; Theorems~\ref{thm:three}, \ref{thm:fermat}] $f(2n)\ge3f(n)$ for all $n\ge1$, with equality exactly for $n\in\{1,2,4\}$. If $a\ge4$ and $F_a=2^{2^a}+1$ is composite, then $f(2n)\ge\bigl(4-\frac{16}{3\cdot2^{a-2}+4}\bigr)f(n)$ for $2^a\le n<2^{a+1}$. In particular $f(2n)\ge\frac{24}{7}f(n)$ for $32\le n<2^{33}$. If $F_a$ is composite for all large $a$, then $\liminf f(2n)/f(n)\ge4$. \end{theoremA} \begin{theoremB}[Good $n$ are everywhere; Theorem~\ref{thm:density}] Let $D(M)=\max_{m\le M}\tau(m)$ and $J(C)=\min\{J:D(2^J)-2>J\log_2C\}$. For every $C>1$ and every $n$, some $0\le jCf(2^jn)$. Hence $\{n:f(2n)>Cf(n)\}$ has lower natural density at least $1/(2^{J(C)}-1)$. Here $J(C)=O(\log\log C\cdot\log\log\log C)$. \end{theoremB} Theorem~B reproves the theorem of Kova\v{c} and Luca, since it gives $\limsup=\infty$. \begin{theoremC}[Exact reduction; Theorem~\ref{thm:thin}, Corollary~\ref{cor:cond}] Call $k$ \emph{$K$-thin} if the odd part of $k$ has fewer than $K$ divisors. Then $f(2n)/f(n)\to\infty$ if and only if, for every fixed $K$, $\sum_{k\le n,\ k\ K\text{-thin}}T(k)=o\bigl(f(2n)-f(n)\bigr)$. Consequently $f(2n)/f(n)\to\infty$ provided that, for every $K$, $\omega(\Phi_d(2))=o\bigl(\psi(d)/\log^2d\bigr)$ as $d\to\infty$ through $K$-thin $d$, where $\psi(x)=\max_{m\le x}\tau(m)=2^{(1+o(1))\log x/\log\log x}$. \end{theoremC} This hypothesis is much weaker than~\eqref{eq:KL}. It allows $\omega(\Phi_d(2))$ as large as $\psi(d)^{1-o(1)}$, and it says nothing at all about indices that are not thin. \begin{theoremD}[What a negative answer needs; Propositions~\ref{prop:negative}, \ref{prop:spike}] If $f(2n)\le Cf(n)$ for infinitely many $n$, then for a fixed $K=K(C)$ there are $K$-thin $d\le n$ with $\omega(\Phi_d(2))\ge(1-o(1))\psi(n)/(K\log_2^2n)$ for each such $n$. If moreover a single prime index $p\le n$ carries a fixed fraction $1/\lambda$ of $f(n)$, then $\tau(2^p+1)\le C\lambda$ and $\omega(2^p-1)\ge\exp\bigl((\log2+o(1))\log p/\log\log p\bigr)$ for infinitely many such $p$. \end{theoremD} \subsection{Mersenne numbers beside near-Wagstaff numbers} Theorem~D isolates a concrete arithmetic scenario. Let $p$ be prime, $M_p=2^p-1$, and for $K\ge4$ let \[ P_K=\{p:\ \tau(2^p+1)\le K\},\qquad \beta_K=\limsup_{p\to\infty,\ p\in P_K}\frac{\log\omega(M_p)\cdot\log\log p}{\log p}, \] with $\beta_K:=0$ if $P_K$ is finite. For $p>3$, $\tau(2^p+1)=4$ exactly when $(2^p+1)/3$ is a Wagstaff prime. Theorem~D shows that $\beta_K\ge\log 2$ for some $K$ is necessary for the ``prime spike'' route to a negative answer to Problem~\#893. \begin{conjecture}\label{conj:beta} $\beta_K=0$ for every $K\ge4$. \end{conjecture} Gillies' heuristic~\cite{Gi64} (see also Wagstaff~\cite{Wa83}) predicts that $\omega(M_p)$ is typically of order $\log p$. This would make Conjecture~\ref{conj:beta} true with room to spare. Unconditionally, nothing better than $\omega(M_p)\le(\frac{\log2}{2}+o(1))\,p/\log p$ seems to be known pointwise. We do not resolve Conjecture~\ref{conj:beta}. Part~II proves: \begin{itemize} \item a disproof would give infinitely many composite $M_p$ ($p$ prime) on which $(2^p+1)/3$ has at most $K/2-1$ prime factors (Theorem~\ref{thm:disproof}); \item barrier theorems: families of fake factorizations satisfy every bounded-depth property of the true ones, yet give $\beta_K=0$ or $\beta_K=\infty$ as desired, and even saturate the trivial constant $\frac{\log2}2$ (Section~\ref{sec:barriers}); \item an ``honest ideal'' obstruction: elements $2^k-\zeta_p$ share every algebraic feature of $2-\zeta_p$ used by class-group, Stickelberger, Galois and lattice methods, but have $\omega\ge\tau(k)$ (Theorem~\ref{thm:honest}); \item the function-field analogue: over $\F_\ell[T]$, $\tau(a^p+1)\le K$ implies $\omega(a^p-1)\le\deg a\,(1+\log_2K)$, uniformly in $p$ (Theorem~\ref{thm:ff}); \item a divisor-lattice inequality and an incidence lemma that isolate the one estimate every method we tried needs (Section~\ref{sec:tools}). \end{itemize} \subsection{What is new, and what is not} In short, \emph{neither problem is resolved here}. The theorem $\limsup f(2n)/f(n)=\infty$ is due to Kova\v{c} and Luca. The trivial bounds, Zsigmondy-type facts and all factor data are classical or tabulated. To our knowledge, the following are not in the literature: Theorems~A--D, the barrier theorems, the honest-ideal obstruction, the function-field theorem and the divisor-lattice lemma. All of them are elementary, or use only classical analytic input (Siegel--Walfisz, Bombieri--Vinogradov). \begin{remark}[Provenance] The results were first obtained in two working notes written with extensive help from AI research agents. For this paper every proof given in full was re-derived and checked line by line. Every numerical claim was re-verified against independent factor tables~\cite{OEIS}. Results proved only in sketch form are labelled as such. \end{remark} %====================================================================== \section{Preliminaries} %====================================================================== For odd $d$ let $o(d)=\ord_d2$. We use the following standard facts. \begin{enumerate} \item[(P1)] \emph{Cyclotomic factorization.} $2^k-1=\prod_{d\mid k}\Phi_d(2)$, and $2^m+1=\prod_{e\mid2m,\ e\nmid m}\Phi_e(2)$. \item[(P2)] \emph{Bang--Zsigmondy}~\cite{Ba86,Zs92}. For $n\notin\{1,6\}$ there is a prime $q$ with $\ord_q2=n$ (a \emph{primitive} prime for $n$). Primitive primes for distinct $n$ are distinct. A primitive prime for $n$ divides $2^k-1$ if and only if $n\mid k$. \item[(P3)] \emph{Lifting the exponent.} If $q$ is an odd prime with $q\mid 2^m-1$, then $v_q(2^{mt}-1)=v_q(2^m-1)+v_q(t)$. \item[(P4)] \emph{Coprimality.} $\gcd(2^m-1,2^m+1)=1$, so $T(2m)=T(m)\,\tau(2^m+1)$. \item[(P5)] \emph{Wigert}~\cite{Wi07}. $\psi(x):=\max_{m\le x}\tau(m)=2^{(1+o(1))\log x/\log\log x}$. \end{enumerate} \begin{lemma}[Divisor gain]\label{lem:gain} Let $m\mid k$. Suppose $2^k-1$ has $s$ distinct prime factors that do not divide $2^m-1$. Then $T(k)\ge2^sT(m)$. In particular, if $E$ is a set of divisors $e$ of $k$ with $e\nmid m$, then $T(k)\ge2^{|E\setminus\{1,6\}|}T(m)$. \end{lemma} \begin{proof} $\tau(N)=\prod_{q\mid N}(v_q(N)+1)$. Every prime factor of $N'=2^m-1$ divides $N=2^k-1$ to at least the same power. Each of the $s$ new primes contributes a factor $\ge2$. For the second claim apply (P2). \end{proof} \begin{lemma}\label{lem:Tupper} $T(k)\le(k+1)^{\omega(2^k-1)}$ and $\omega(2^k-1)\le\tau(k)\max_{d\mid k}\omega(\Phi_d(2))$. \end{lemma} \begin{proof} Each exponent satisfies $v_q(2^k-1)\le\log_3 2^k1$. Then $2^{m/u}+1$ is a proper divisor of $2^m+1$ greater than $1$. If $\tau(2^m+1)=3$, then $2^m+1=q^2$, so $(q-1)(q+1)=2^m$, which forces $q=3$ and $m=3$. (b) Write $m=2^cu$. By (P1) the indices $e\mid 2m$ with $e\nmid m$ are $e=2^{c+1}w$ with $w\mid u$. There are $\tau(u)$ of them, and each except possibly $e=6$ has a primitive prime by (P2). \end{proof} %====================================================================== \part*{Part I. The doubling ratio} %====================================================================== \section{An exact identity} \begin{theorem}\label{thm:identity} $f(n)=\sum_{d\ \mathrm{odd}}\lfloor n/o(d)\rfloor$. Hence $f(2n)-2f(n)=\#\{d\ \mathrm{odd}:\{n/o(d)\}\ge\frac12\}$, where $\{\cdot\}$ is the fractional part. \end{theorem} \begin{proof} An odd $d$ divides $2^k-1$ if and only if $o(d)\mid k$. So $f(n)=\sum_{d}\#\{k\le n:o(d)\mid k\}=\sum_d\lfloor n/o(d)\rfloor$, where only finitely many $d$ contribute. For real $x$, $\lfloor2x\rfloor-2\lfloor x\rfloor$ is $1$ if $\{x\}\ge\frac12$ and $0$ otherwise. \end{proof} The identity is elementary and probably folklore. It shows that $f(2n)>2f(n)$ always, since $d=3$ gives $\{n/2\}=\frac12$ for odd $n$, and $d=2^{n+1}-1$ gives $o(d)=n+1>n$. It also recasts the problem: do the moduli $d$ whose order puts $n$ in the upper half of a period outnumber $\sum_d\lfloor n/o(d)\rfloor$ by an unbounded factor? \section{The sharp constant 3} Write $F_i=2^{2^i}+1$. By (P4), $T(2^{a+1})=\tau(F_a)\,T(2^a)$ and $T(2^a)=\prod_{i1$ odd, and $C(r)=\sum_{i=0}^{b}T(2^iu)$. Then $C(r)\le T(2r)/3$. \end{lemma} \begin{proof} By (P4), $T(2^{i+1}u)=T(2^iu)\,\tau(2^{2^iu}+1)$. Since $u>1$, the exponent $2^iu$ is never a power of $2$. By Lemma~\ref{lem:plus}(a), each factor $\tau(2^{2^iu}+1)$ is $\ge4$, except the factor $\tau(9)=3$ when $i=0$, $u=3$. If all factors are $\ge4$, then $T(2^iu)\le4^{-(b+1-i)}T(2r)$, and $C(r)\le T(2r)\sum_{j\ge1}4^{-j}=T(2r)/3$. If $u=3$, the same bound holds for $i\ge1$, and $T(3)=T(6)/3\le T(2r)/(3\cdot4^b)$. Then $C(r)\le T(2r)\bigl(\sum_{j=1}^{b}4^{-j}+\frac{1}{3\cdot4^b}\bigr)=T(2r)/3$. \end{proof} \begin{lemma}\label{lem:3pow} For $c\ge1$, $T(3\cdot2^c)\ge\frac32\,2^c\,T(2^c)$. \end{lemma} \begin{proof} Let $N=2^{3\cdot2^c}-1$ and $N'=2^{2^c}-1$. The indices $3\cdot2^i$, $0\le i\le c$, $i\ne1$, divide $3\cdot2^c$ but not $2^c$. Their $c$ primitive primes (P2) are distinct, do not divide $N'$, and differ from $3$, because $\ord_32=2$. By (P3), $v_3(N')=v_3(4^{2^{c-1}}-1)=1$ and $v_3(N)=1+v_3(3\cdot2^{c-1})=2$. So the prime $3$ contributes $3$ to $\tau(N)$ against $2$ to $\tau(N')$, and $\tau(N)\ge\tau(N')\cdot\frac32\cdot2^c$. \end{proof} \begin{lemma}\label{lem:fermatsum} $T(2^{i+1})\ge2T(2^i)$. Hence $\sum_{i(\tau(F_a)-2)T(2^a)-4T(2^{a-1})\ge-4T(2^{a-1}). \] To compensate, let $r_0=3\cdot2^{a-2}$ if $n<3\cdot2^{a-1}$, and $r_0=3\cdot2^{a-1}$ otherwise. In both cases $r_0\in R$ and $r_0\ne2^a$. Also $2^{3\cdot2^{a-1}}-1$ divides $2^{2r_0}-1$, so $T(2r_0)\ge T(3\cdot2^{a-1})$. By Lemma~\ref{lem:3pow}, $\tfrac13T(2r_0)\ge\tfrac13T(3\cdot 2^{a-1})\ge2^{a-2}T(2^{a-1})\ge4T(2^{a-1})$. The sum in~\eqref{eq:master} is therefore strictly positive. \end{proof} \begin{remark}[Sharpness for soft methods; heuristic]\label{rem:sharp3} The constant $3$ cannot be improved by any argument that uses only the soft properties listed in Section~\ref{sec:barrier-doubling}. Consider a model in which $\Phi_{2^a}(2)=F_{a-1}$ is replaced by a product of many primes, so that $T^*(2^a)$ dominates $f^*(2^a)$, and $F_a$ is ``prime''. Then $T^*(2^{a+1})=2T^*(2^a)$, so $f^*(2^{a+1})/f^*(2^a)\to3$. \end{remark} \begin{theorem}\label{thm:fermat} If $a\ge4$ and $F_a$ is composite, then $f(2n)\ge\bigl(4-\frac{16}{3\cdot2^{a-2}+4}\bigr)f(n)$ for all $n\in[2^a,2^{a+1})$. \end{theorem} \begin{proof} Apply~\eqref{eq:master} with $\lambda=3$. The terms with $r\ne2^a$ are $\ge0$ by Lemma~\ref{lem:Cr}. Since $F_a\equiv2\pmod3$ is not a square, compositeness gives $\tau(F_a)\ge4$. With Lemma~\ref{lem:fermatsum}, the $r=2^a$ term is then $\ge T(2^a)-6T(2^{a-1})\ge-4T(2^{a-1})$. Put $t=T(2^{a-1})/f(n)$; this gives $f(2n)/f(n)\ge4-4t$. On the other hand $3\cdot2^{a-1}\le2n$, so by Lemma~\ref{lem:3pow} $f(2n)\ge T(3\cdot2^{a-1})\ge3\cdot2^{a-2}\,T(2^{a-1})$, that is, $f(2n)/f(n)\ge3\cdot2^{a-2}t$. The larger of the two bounds is smallest where they meet, at $t=4/(3\cdot2^{a-2}+4)$. \end{proof} \begin{corollary}\label{cor:fermat} (a) $F_5,\dots,F_{32}$ are composite, so $f(2n)\ge\frac{24}{7}f(n)$ for $32\le n<2^{33}$. (b) If $F_a$ is composite for all sufficiently large $a$, then $\liminf_{n}f(2n)/f(n)\ge4$. \end{corollary} \begin{proof} (a) Take $a=5$ in Theorem~\ref{thm:fermat}; the bound increases with $a$. (b) Every large $n$ lies in some $[2^a,2^{a+1})$, and the bound tends to $4$ as $a\to\infty$. \end{proof} The value $4$ in (b) is the value predicted by the naive ``random integer'' model, which Kova\v{c} and Luca show to be misleading. Exact data give $\min_{32\le n\le606}f(2n)/f(n)=14.26$, computed from the table of $\tau(2^n-1)$, $n\le1212$, in~\cite{OEIS}. \section{Growth along chains and the density of good \texorpdfstring{$n$}{n}} \begin{proposition}\label{prop:mult} For all $M,n\ge1$, $f(Mn)\ge2^{D(M)-2}f(n)$, where $D(M)=\max_{m\le M}\tau(m)$. \end{proposition} \begin{proof} Choose $h\le M$ with $\tau(h)=D(M)$, and fix $m\le n$. The indices $me$ with $e\mid h$, $e>1$, divide $hm$ but not $m$. There are $\tau(h)-1$ of them, and at most one equals $6$. By Lemma~\ref{lem:gain}, $T(hm)\ge2^{\tau(h)-2}T(m)$. The numbers $hm$, $m\le n$, are distinct and at most $Mn$. Summing over $m$ gives the claim. \end{proof} \begin{theorem}\label{thm:density} Let $J=J(C)=\min\{J:D(2^J)-2>J\log_2C\}$. For every $n$ some $0\le jCf(2^jn)$. Consequently $\{n:f(2n)>Cf(n)\}$ has lower natural density at least $1/(2^J-1)$. This bound is optimal for the chain property alone. \end{theorem} \begin{proof} By Proposition~\ref{prop:mult} with $M=2^J$, $\prod_{jC^J$. So some factor exceeds $C$. For the density, group $n\le x$ by odd part $m$. The chain $m,2m,4m,\dots$ has $\lfloor\log_2(x/m)\rfloor+1$ terms up to $x$. Every $J$ consecutive terms contain a good one, so at least $\lfloor(\lfloor\log_2(x/m)\rfloor+1)/J\rfloor=\#\{i\ge0:m2^{iJ+J-1}\le x\}$ terms are good. Summing over odd $m$ gives $\sum_{i\ge0}\frac{x}{2^{iJ+J}}+O(J\log x)=\frac{x}{2^J-1}+O(J\log x)$. The set $\{n:v_2(n)\equiv J-1\pmod J\}$ meets every chain of $J$ consecutive terms and has density exactly $1/(2^J-1)$. \end{proof} By direct computation, $D(2^J)$ for $J=7,8,12,13,20,21$ equals $16,20,48,64,240,288$. Hence $J(4)=8$, $J(16)=13$ and $J(10^4)=21$. By (P5), $\log_2D(2^J)=(1+o(1))J\log2/\log J$, so $J(C)=O(\log\log C\cdot\log\log\log C)$. \begin{corollary}[Kova\v{c}--Luca~\cite{KL}]\label{cor:KL} $\limsup_nf(2n)/f(n)=\infty$. More strongly, $f(M(n)n)/f(n)\to\infty$ for every integer sequence $M(n)\to\infty$. \end{corollary} The argument of~\cite{KL} also uses highly composite numbers, through $f'(n)=\sum_{k\le n}2^{\tau(k)}$. Theorem~\ref{thm:density} adds the chain and density statements. \section{Exact reduction to thin indices} \begin{definition} Fix $K\ge2$. An integer $k$ is \emph{$K$-thin} if its odd part has fewer than $K$ divisors. Every divisor of a $K$-thin number is $K$-thin. \end{definition} \begin{theorem}\label{thm:thin} For all $n$ and all $K\ge2$, \[ \sum_{\substack{k\le n\\ k\text{ not }K\text{-thin}}}T(k)\ \le\ \frac{f(2n)-f(n)}{2^{K-1}-1}. \] Hence $f(2n)/f(n)\to\infty$ if and only if, for every fixed $K$, the $T$-mass of the $K$-thin $k\le n$ is $o\bigl(f(2n)-f(n)\bigr)$. \end{theorem} \begin{proof} For $k\le n$ there is a unique $b\ge1$ with $N=2^bk\in(n,2n]$. The map $k\mapsto(N,b)$ is a bijection onto $\{(N,b):N\in(n,2n],\ 1\le b\le v_2(N)\}$. If $k$ is not $K$-thin, then every $2^ik$ has the same odd part $u$ with $\tau(u)\ge K$. By (P4) and Lemma~\ref{lem:plus}(b), each doubling multiplies $T$ by at least $2^{K-1}$, so $T(N)\ge2^{b(K-1)}T(k)$. Therefore \[ \sum_{k\text{ not thin}}T(k)\le\sum_{N\in(n,2n]}T(N)\sum_{b\ge1}2^{-b(K-1)}=\frac{f(2n)-f(n)}{2^{K-1}-1}. \] For the equivalence: if the thin mass is $o(f(2n)-f(n))$ for every $K$, then $\limsup f(n)/(f(2n)-f(n))\le1/(2^{K-1}-1)$ for every $K$, so the ratio tends to infinity. The converse is trivial, since the thin mass is at most $f(n)$. \end{proof} \begin{corollary}[Conditional divergence]\label{cor:cond} Suppose that for every $K\ge2$, \begin{equation}\label{eq:thinhyp} \omega(\Phi_d(2))=o\!\left(\frac{\psi(d)}{\log^2d}\right)\qquad(d\to\infty,\ d\ K\text{-thin}). \end{equation} Then $f(2n)/f(n)\to\infty$. In particular this holds under~\eqref{eq:KL}, or under $\omega(\Phi_d(2))\le\psi(d)^{1-\delta}$ for some $\delta>0$ and all large $d$. \end{corollary} \begin{proof} Fix $K$ and a $K$-thin $k\le n$. Then $\tau(k)2C$. Then for each such $n$ there are a $K$-thin $k\le n$ with $\log_2T(k)\ge\psi(n)-3-\log_2n$, and a $K$-thin $d\mid k$ with \[ \omega(\Phi_d(2))\ \ge\ \frac{\psi(n)-3-\log_2n}{K(\log_2n+1)\log_2(n+1)}. \] \end{proposition} \begin{proof} By Theorem~\ref{thm:thin}, the non-thin mass is at most $(f(2n)-f(n))/(2^{K-1}-1)2pj$ and $(2p)^kk!<2^p$. We may assume $k\ge p/\log^2p$. Then $\log k\ge\log p-2\log\log p$ and $k!\ge(k/e)^k$ give $k(2\log p-2\log\log p+\log 2-1)0$ and $00$ forces $P_K$ to be infinite. Apply $\tau(n)\ge\Omega(n)+1$ and $\tau(n)\ge2^{\omega(n)}$ to $\tau(a_p)\le K/2$. \end{proof} The infinitude of composite $M_p$ with $p$ prime is open (Guy~\cite{Guy}, A3). A disproof would settle it together with an almost-prime statement for $(2^p+1)/3$ on the same set of $p$. \begin{proposition}\label{prop:finite} $P_K$ is finite for every $K$ if and only if $\Omega(a_p)\to\infty$. In particular, finiteness of $P_4$ means that there are only finitely many Wagstaff primes. \end{proposition} This is believed false. The Lenstra--Pomerance--Wagstaff-type heuristic (see~\cite{BSW89}) predicts $\asymp\log x$ Wagstaff exponents $p\le x$. \begin{proposition}[No fixed-family certificate]\label{prop:nocert} Let $f_1,\dots,f_r\in\Z[x]$ be nonconstant. There is a set of primes $p$ of positive relative density on which no $f_j(p)$ is a divisor of $a_p$ other than $\pm1$, and likewise for $M_p$. \end{proposition} \begin{proof} If $f_j=c\,x^k$, then $f_j(p)=cp^k$ is never such a divisor, because every prime factor of $a_pM_p$ is at least $2p+1$. Otherwise write $f_j=x^kg_j$ with $g_j(0)\ne0$ and $g_j$ nonconstant. By Schur's theorem infinitely many primes $\ell$ divide some value $g_j(r)$. Choose such odd primes $\ell_j$, distinct and not dividing $g_j(0)$, with residues $r_j$. Then $r_j\not\equiv0\pmod{\ell_j}$. By the Chinese remainder theorem and Dirichlet's theorem, a positive proportion of primes satisfy $p\equiv r_j\pmod{\ell_j}$ for all $j$. For these $p$ we have $\ell_j\mid f_j(p)$, while $\ell_j<2p+1$ for large $p$. So $f_j(p)$ divides neither $a_p$ nor $M_p$, unless $f_j(p)=0$, which happens for finitely many $p$. \end{proof} The working note's proof of Proposition~\ref{prop:nocert} omitted the case $f_j=cx^k$, in which no nonzero residue works; the repair is the first sentence above. %====================================================================== \section{Barriers for soft and bounded-depth arguments}\label{sec:barriers} %====================================================================== The results in this section are \emph{meta-theorems}. Each lists properties of the true factorizations and builds fake factorizations with all of them but with opposite behaviour. Any argument that uses only the listed properties therefore proves nothing about the question. The constructions are explicit, but they rely on the Siegel--Walfisz or Bombieri--Vinogradov theorems and are ineffective. Full verifications are in the working notes. Here we give statements and the key steps; these results are \emph{proved in sketch form only}. \subsection{Soft properties of \texorpdfstring{$2^k-1$}{2\textasciicircum k-1}}\label{sec:barrier-doubling} The \emph{soft properties} are the following: \begin{itemize} \item the cyclotomic factorization and $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$; \item a primitive prime $\equiv1\pmod d$ for every index $d\ne1,6$; \item $T(2k)=T(k)\tau(2^k+1)$ and lifting-the-exponent multiplicities; \item the size $\log\Phi_d(2)\approx\varphi(d)\log 2$ and Aurifeuillian splitting; \item the rule $q\equiv\pm1\pmod8$ if and only if $2\mid(q-1)/\ord_q2$, and power-residue rules of bounded depth; \item Stewart's lower bound for the largest prime factor~\cite{St13}; \item Brun--Titchmarsh and averaged sieve bounds. \end{itemize} \begin{theorem}[Models for the doubling problem; sketch]\label{thm:model-doubling} There are ``fake'' factorizations, in which each $\Phi_d(2)$ is replaced by a product of genuine primes $\equiv1\pmod d$ satisfying all soft properties, of the following kind. They have one prime per generic index (two at Aurifeuillian indices). Along a sparse sequence of primes $\ell_j$, index $\ell_j$ carries $W_j\ge D(3\ell_j)+O(\log\ell_j)$ primes and index $2\ell_j$ carries one. For these models $f^*(2\ell_j)/f^*(\ell_j)\to5$, so $\liminf f^*(2n)/f^*(n)<\infty$. Other models, with every $\omega(\Phi_d^*(2))\le d^{o(1)}$, have $f^*(2n)/f^*(n)\to\infty$. \end{theorem} \begin{proof}[Key steps] In $(\ell_j,2\ell_j]$ the only multiples of $\ell_j$ are $\ell_j$ and $2\ell_j$, so $T^*(\ell_j)=2^{W_j}$ and $T^*(2\ell_j)=4T^*(\ell_j)$. Every other $k\le2\ell_j$ has $\log_2T^*(k)\le D(2\ell_j)+\sum_{i2^{p-1}$ forces $\prod F(p)=M_p$, and adding exact divisibility $\prod F\mid M_p$ recovers the truth. So fake models die only at $p$-adic depth $J\gtrsim p\log2/\log p$, or at residue depth $(q-1)/p$, which is unbounded. \end{proposition} \begin{lemma}[Mod-24 limit of the construction] No product of primes that are all $\equiv7\pmod 8$ and $\equiv2\pmod3$ is $\equiv M_p\pmod{24}$. \end{lemma} \begin{proof} $M_p\equiv7\pmod8$ needs an odd number of factors, and $M_p\equiv1\pmod3$ needs an even number. \end{proof} So adding product congruences modulo $3$ forces genuine Chebotarev conditions in non-abelian Kummer fields such as $\Q(\zeta_3,2^{1/3})$. The construction above does not handle these; that extension is \emph{unproved}. \begin{theorem}[Barrier for the constant; sketch, using Bombieri--Vinogradov and Heath-Brown's Linnik bound~\cite{HB92}] \label{thm:constbarrier} Fix $\varepsilon\in(0,\frac1{10})$ and $D\ge3$. For all primes $p$ outside a set of relative density zero, there are a set $Q'_p$ of at least $(\frac{\log2}2-\varepsilon)\,p/\log p$ primes in $[p^2,p^2(\log p)^{20}]$ and a prime $r$ with the following properties. Each of them is $\equiv1\pmod{2p}$, $\equiv7\pmod8$, and $\not\equiv1\pmod\ell$ for odd $\ell\le D$. The product $N'=r\prod Q'_p$ satisfies $N'N^\theta$ with $\gcd(s,N)=1$. Let a nonempty set $D'$ of divisors of $N$ meet $R$ residue classes modulo $s$. Then $\theta\,\omega(N)<1+\log_2R+\log_2(\tau(N)/|D'|)$. \end{lemma} \begin{proof} Let $t=\lfloor\theta\,\omega(N)\rfloor$ and let $A$ be the product of the $t$ smallest prime-power parts of $N$. Then $A\le N^{t/\omega(N)}\le N^\theta