\documentclass[11pt,reqno]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage{amsmath,amssymb,mathtools} \usepackage{microtype} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \hypersetup{pdftitle={Infinitely Many Exceptions to a Prime-Square Representation Problem of Erdos}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\R}{\mathbb R} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\ind}{\mathbf 1} \newcommand{\ee}[1]{\mathrm e\!\left(#1\right)} \newcommand{\normt}[1]{\left\|#1\right\|_{\R/\Z}} \DeclareMathOperator{\lcm}{lcm} \allowdisplaybreaks[1] \setlength{\emergencystretch}{2em} \title[Exceptions to an Erd\H{o}s representation problem]{Infinitely many exceptions to a prime-square representation problem of Erd\H{o}s} \author[W. Howe]{Will Howe} \author[G. Huffman]{Grant Huffman} \author[J. Kohlmeyer]{Jensen Kohlmeyer} \author[L. Kruer]{Liam Kruer} \date{November 11, 2026} \subjclass[2020]{Primary 11N35; Secondary 11N36, 11A07} \keywords{Erd\H{o}s problems, prime-square residues, sieve methods, exceptional sets} \thanks{\raggedright E-mail addresses: \href{mailto:howew@purdue.edu}{howew@purdue.edu} (W. Howe), \href{mailto:huffma97@purdue.edu}{huffma97@purdue.edu} (G. Huffman), \href{mailto:jenwin@purdue.edu}{jenwin@purdue.edu} (J. Kohlmeyer), \href{mailto:kruerl@purdue.edu}{kruerl@purdue.edu} (L. Kruer).} \begin{document} \begin{abstract} We prove that infinitely many positive integers have no representation $n=ap^2+b$ with $p$ prime, $a\geq1$, and $0\leq b
0$ and $X_0$ such that \begin{equation}\label{eq:main} c\frac{X}{\log X}\leq E(X)\leq C\frac{X}{\log X} \qquad(X\geq X_0). \end{equation} In particular, infinitely many positive integers have no representation \eqref{eq:representation}. \end{theorem} Erd\H{o}s recorded $g(x)\ll x/(\log x)^c$ for some $c>0$, with $g(x)$ counting exceptions up to $x$, in \cite[p.~68]{Erdos}. We determine the order of the exceptional count and prove the upper bound from the same sieve estimate. We first work with positive integer $X$ and write $I=(X,2X]\cap\Z$. For a prime $p$, let \[ A_p(n)=\ind_{\{n\bmod p^2
0$, depending only on the fixed exponents, such that
\begin{equation}\label{eq:correlation}
\sum_{n\in\Z}G(n)U(n)
=\lambda\sum_{n\in\Z}U(n)+O(X^{1-\delta}).
\end{equation}
The error is uniform in $\mathcal P$ and $\mathcal Q$.
\end{lemma}
\begin{proof}
Choose $b<\eta 0$ such that, for all
sufficiently small fixed $\alpha>0$,
\begin{align}
\sum_{n\in I}B(n)&\geq
(1-C_1\alpha^2-o_\alpha(1))XV(z),\label{eq:first}\\
\sum_{n\in I}B(n)^2&\leq
(1+C_2\alpha^2+o_\alpha(1))XV(z)^2.\label{eq:second}
\end{align}
\end{proposition}
\subsection{The first moment}
Partition the primes through $z$ into nonempty blocks
\[
\mathcal P_j=\{p:z^{2^{-j-1}} 0
\end{equation}
uniformly, since $-\log(1-1/p)\leq2/p$ for $p\geq2$.
Choose an absolute integer $L_0$ so large that
$C_0^k/k!\leq2^{-k}$ for $k\geq2L_0$, and put
\[
T=\lceil\log_2(1/\alpha)\rceil+L_0,\qquad k_j=2T+2j.
\]
For $K_j(n)=\sum_{p\in\mathcal P_j}A_p(n)$, the Bonferroni
polynomials
\[
U_j(n)=\sum_{i=0}^{k_j}(-1)^i\binom{K_j(n)}i,
\qquad
L_j(n)=\sum_{i=0}^{k_j-1}(-1)^i\binom{K_j(n)}i
\]
satisfy
\[
L_j\leq\ind_{\{K_j=0\}}\leq U_j,
\qquad U_j\geq0,\qquad U_j-L_j=\binom{K_j}{k_j}.
\]
Telescoping the product, using the nonnegativity of the upper
polynomials, gives
\begin{equation}\label{eq:bonfproduct}
S_z(n)\geq\prod_jU_j(n)
-\sum_j(U_j(n)-L_j(n))\prod_{i\ne j}U_i(n).
\end{equation}
Replace the variables $A_p(n)$ temporarily by independent Bernoulli
variables of means $1/p$. For a single block,
\[
\E U_j\geq V_j,\qquad
\E(U_j-L_j)\leq\frac{C_0^{k_j}}{k_j!}\leq2^{-k_j}.
\]
Also $\E U_j-V_j\leq\E(U_j-L_j)$, so
$\E U_j\leq V_j(1+v_0^{-1}2^{-k_j})$.
Independence between blocks and \eqref{eq:blocksurvival} show that
the expectation of the right side of \eqref{eq:bonfproduct} is at least
\[
V(z)\left(1-O\left(\sum_j2^{-k_j}\right)\right)
\geq V(z)(1-O(\alpha^2)).
\]
To transfer this bound to integers, expand \eqref{eq:bonfproduct}
into products of distinct $A_p$.
Every resulting squarefree modulus $m$ satisfies
\[
m\leq z^{\sum_{j\geq0}k_j2^{-j}}
=z^{4T+4}\leq X^{1/4}
\]
when $\alpha$ is sufficiently small.
Each coefficient has absolute value at most $J+2$.
The Chinese remainder theorem gives exactly $m$ forbidden residue
classes modulo $m^2$ for a product indexed by $m$, hence its sum
over $I$ is $X/m+O(m)$.
The total transfer error is bounded by
\[
O\left((J+2)\sum_{m\leq X^{1/4}}m\right)
=O((J+2)X^{1/2})=o(XV(z)).
\]
Thus $\sum_{n\in I}S_z(n)\geq(1-C_1\alpha^2-o_\alpha(1))XV(z)$.
Translating $I$ by an integer $0\leq j 0$ and all sufficiently large $X$, such that
every $n\in U^*$ and $0\leq j 2X$, so it cannot occur in a representation
of $m$. Thus $m$ is exceptional.
For any fixed $m$, at most $H$ pairs $(n,j)$ satisfy $m=n+j$ with
$0\leq j