\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 b0$ 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^20$, 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<\eta0$ for which \begin{equation}\label{eq:smoothnorm} \sum_{X-H\leq n\leq2X+H}|G_H(n)-\lambda|^2 \ll X^{1-\delta_1}. \end{equation} Enlarge and contract both the ambient interval and every forbidden residue interval by $H$ at its endpoints. This gives indicators $U_-$ and $U_+$ such that, for $|h|\leq H$, \[ U_-(n-h)\leq U(n)\leq U_+(n-h). \] The enlarged ambient interval lies in $[X-H,2X+H]$. For a prime $q$, the boundary change meets at most $O(H(X/q^2+1))$ integers in that interval. Thus \begin{align*} \sum_n(U_+(n)-U_-(n)) &\ll H+H\sum_{X^c\leq q\leq2\sqrt X}(X/q^2+1)\\ &\ll HX^{1-c}, \end{align*} where the reciprocal-square tail can be bounded by the sum over all integers and $c\leq1/2$. Also $\lambda=O_{a,b}(1)$ by \eqref{eq:mertens}. Since $G\geq0$, averaging the pointwise comparisons and changing variables gives \[ \sum_n U_-(n)G_H(n)\leq\sum_nU(n)G(n) \leq\sum_nU_+(n)G_H(n). \] Cauchy--Schwarz and \eqref{eq:smoothnorm} bound either centered sum by $O(X^{1-\delta_1/2})$. The boundary error is $O(HX^{1-c})$, which also saves a positive power because $\eta1+3/4+(3/4)^2/2>2$. \begin{proposition}\label{prop:large} There is an absolute constant $c_0>0$ such that, for every fixed integer $L\geq2$, with $\alpha=2^{-L}$, \begin{equation}\label{eq:largecount} \#\{n\in I:A_p(n)=0\text{ for every }X^\alpha0$ 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 j0$, uniformly in $k$ and in integer intervals $J_X$ of length $X$, \begin{equation}\label{eq:twoposition} \sum_{n\in J_X}S_z(n)S_z(n+k) \leq(1+C\alpha^2)XV_k+O(X^{3/5}), \end{equation} where $C$ and the implied constant are absolute. \end{lemma} \begin{proof} If $g_k(p)=1$ for some $p$, then $V_k=0$ and the left side is zero. We may therefore suppose $00$ and put \[ Y=c_1\log H,\qquad M=\prod_{p\leq Y}p^2,\qquad L(k)=\prod_{p\leq Y}R_p(k). \] By \eqref{eq:cheb}, $M\leq H^{1/4}$. The Chinese remainder theorem shows that $L$ has mean one modulo $M$. A uniform integer in $\{0,\ldots,H-1\}$ has residue probabilities $1/M+O(1/H)$; convolving with another probability distribution preserves this error bound. Consequently \begin{equation}\label{eq:headmean} \sum_kw_H(k)L(k)=1+O(M/H). \end{equation} Set $Y_0=H^{1/4}$ and $Y_1=H^{1-\alpha^2}$. For $Y0$ and all sufficiently large $X$, such that every $n\in U^*$ and $0\leq j1/4$, \[ \frac{(2^{-L})^2}{d^L}=(4d)^{-L}\longrightarrow0. \] Choose $L$ sufficiently large, put $\alpha=2^{-L}$, and set $\rho=c_2d^L$. We can require $0<\rho\leq1$ and $\max(C_1,C_2)\alpha^2\leq\rho/16$. Then fix this $L$ and take $X$ sufficiently large to absorb all $o_\alpha(1)$ errors into $\rho/16$. Writing $V=V(z)$, we obtain \[ \sum_{n\in I}B(n)\geq(1-\rho/8)XV, \qquad \sum_{n\in I}B(n)^2\leq(1+\rho/8)XV^2, \qquad |I\setminus U^*|\leq(1-\rho)X. \] Cauchy--Schwarz now gives \begin{align*} \sum_{n\in U^*}B(n) &\geq \sum_{n\in I}B(n) -\sqrt{|I\setminus U^*|\sum_{n\in I}B(n)^2}\\ &\geq XV\left(1-\frac\rho8 -\sqrt{(1-\rho)(1+\rho/8)}\right) \geq\frac\rho8 XV. \end{align*} The last inequality follows from $(1-\rho)(1+\rho/8)\leq(1-\rho/4)^2$ for $0\leq\rho\leq1$. Whenever $n\in U^*$ and a term $S_z(n+j)$ in $B(n)$ equals one, the integer $m=n+j$ lies in $I$ and avoids every prime through $z$. It also avoids the primes $z2X$, 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