\documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[letterpaper,margin=1in]{geometry} \usepackage{microtype} \usepackage{mathtools,amssymb} \usepackage{xcolor} \definecolor{linkblue}{rgb}{0,0,0.55} \usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue]{hyperref} \hypersetup{ pdftitle={Balanced additive complements with bounded representation functions}, pdfauthor={Will Howe; Grant Huffman; Jensen Kohlmeyer; Liam Kruer}, pdfsubject={A counterexample to Erdos Problem 1145}, pdfkeywords={additive complements, representation functions, Erdos-Sarkozy conjecture}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newcommand{\N}{\mathbb N} \newcommand{\Nzero}{\mathbb N_0} \newcommand{\Z}{\mathbb Z} \newcommand{\PA}{P^A} \newcommand{\PB}{P^B} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\rAB}{r_{A,B}} \DeclareMathOperator{\card}{card} \setlength{\emergencystretch}{2em} \newcommand{\Needspace}[1]{% \par\begingroup \dimen0=#1\relax \dimen2=\pagegoal \advance\dimen2 by -\pagetotal \ifdim\dimen0>\dimen2\newpage\fi \endgroup} \allowdisplaybreaks[1] \title[Balanced additive complements]{Balanced additive complements with\\ bounded representation functions} \author[W. Howe]{Will Howe} \author[G. Huffman]{Grant Huffman} \author[J. Kohlmeyer]{Jensen Kohlmeyer} \author[L. Kruer]{Liam Kruer} \date{November 2026} \subjclass[2020]{11B13, 11B34} \keywords{additive complements, representation functions, Erd\H{o}s--S\'ark\"ozy conjecture} \thanks{Email addresses: \href{mailto:howew@purdue.edu}{\texttt{howew@purdue.edu}} (Will Howe), \href{mailto:huffma97@purdue.edu}{\texttt{huffma97@purdue.edu}} (Grant Huffman), \href{mailto:jenwin@purdue.edu}{\texttt{jenwin@purdue.edu}} (Jensen Kohlmeyer), \href{mailto:kruerl@purdue.edu}{\texttt{kruerl@purdue.edu}} (Liam Kruer).} \begin{document} \begin{abstract} We construct infinite sets $A=\{a_1K \] elements of $S$. In a safe class, the union contains at most $(K-M)+M=K$ elements. An unsafe class receives no element of $C$, and its old count is bounded by the count of its parent class modulo $m$. \end{proof} At stage $k$, safety for the $A$-component is defined from $\PA_k$ modulo $q_{k+1}$. Safety for the $B$-component is defined from $\PB_k$ modulo $p_{k+1}$. Thus every class modulo $q_k$ has at most one unsafe child among its three classes modulo $q_{k+1}$, and every class modulo $p_k$ has at most one unsafe child among its $d_k$ classes modulo $p_{k+1}$. \section{Construction of a block} Assume that the earlier blocks have been constructed, satisfy \eqref{eq:invariant}, and are pairwise disjoint within each component. Throughout this section abbreviate $p=p_k$ and $q=q_k$. \subsection{Separating the blocks} We choose integers \begin{equation}\label{eq:anchors} U_k=p^2+\alpha_k,\quad 0\leq\alpha_k256p^2. \] This proves the bounds on $R$. \end{proof} \Needspace{7\baselineskip} \begin{proposition}\label{prop:coverage} Every integer in $[16p_k^2,256p_k^2]$ belongs to $A_k+B_k$. \end{proposition} \begin{proof} Use Lemma~\ref{lem:coefficients}, and consider \begin{align*} a(t)&=U+p(x+qt),\\ b(t)&=V+q\bigl(y+p(R-t)\bigr), \end{align*} where $t$ ranges over the integer interval \begin{equation}\label{eq:phaseinterval} I=[\max(0,R-H),\min(H,R)]\cap\Z. \end{equation} Both $t$ and $R-t$ lie between $0$ and $H$. The bounds $12\leq R\leq507$ show that $I$ contains at least thirteen consecutive integers. All the $a(t)$ lie in a single class modulo $q$. Modulo $3q$, changing $t$ by one changes $a(t)$ by $pq$. Since $p$ is relatively prime to $3$, the three residues of $t$ modulo $3$ give the three different child classes. Lemma~\ref{lem:safety} implies that at most one residue of $t$ modulo $3$ makes $a(t)$ unsafe. Write $p_{k+1}=d_kp$ with $d_k\in\{2,4\}$. All the $b(t)$ lie in one class modulo $p$. Changing $t$ by one changes $b(t)$ by $-pq$, and $q$ is relatively prime to $d_k$. The residues of $t$ modulo $d_k$ therefore give the different child classes. At most one of those residues makes $b(t)$ unsafe. In any thirteen consecutive integers, a fixed residue modulo $3$ occurs at most five times, and a fixed residue modulo $d_k$ occurs at most seven times. At most twelve positions are excluded. Choose a remaining $t\in I$. Then $a(t)$ and $b(t)$ are safe unshifted candidates, so both were retained. Finally \eqref{eq:decompose} gives $a(t)+b(t)=n$. \end{proof} \section{The infinite sets and their representation function} Start at $k=3$ with empty preceding unions, which satisfy \eqref{eq:invariant}. Lemma~\ref{lem:anchors} and Proposition~\ref{prop:block} allow the construction to continue for every $k\geq3$. Define \begin{equation}\label{eq:unions} A=\bigcup_{k\geq3}A_k,\qquad B=\bigcup_{k\geq3}B_k. \end{equation} Proposition~\ref{prop:coverage} makes each block nonempty. Disjointness within each component therefore makes both unions infinite. All their elements are positive by \eqref{eq:blockrange}. The intervals covered in Proposition~\ref{prop:coverage} overlap, since \[ 16p_{k+1}^2\leq16(4p_k)^2=256p_k^2. \] Their endpoints tend to infinity. Their first lower endpoint is $16p_3^2=16\cdot32^2=16384$, which proves \eqref{eq:cover}. \begin{lemma}\label{lem:maximalscales} For any positive integer $n$, at most five indices $j\geq3$ satisfy \begin{equation}\label{eq:eligible} p_j^2\leq n\leq526p_j^2. \end{equation} \end{lemma} \begin{proof} Successive values of $p_j^2$ increase by a factor of at least four. If six indices $j_0<\cdots0$. Each representation $n=a+b$ has unique block indices $i,j$ with $a\in A_i$ and $b\in B_j$. Put $\ell=\max(i,j)$. Monotonicity of the scales and \eqref{eq:blockrange} give \[ p_\ell^2\leq n\leq526p_\ell^2. \] Lemma~\ref{lem:maximalscales} leaves at most five possibilities for $\ell$. Fix one such $\ell$, and abbreviate $p=p_\ell$, $q=q_\ell$, $U=U_\ell$, $V=V_\ell$. Representations with maximal index $\ell$ fall into the following three disjoint cases. \smallskip \noindent\emph{The $A$-point lies in $A_\ell$ and the $B$-point lies in $\PB_\ell$.} The $A$-point belongs to one of the three residues $U+sq$ modulo $p$. For a fixed $s$, its partner belongs to the residue $n-U-sq$ modulo $p$. The invariant \eqref{eq:invariant} bounds the number of such partners in the entire set $\PB_\ell$ by $K$. Each partner determines the $A$-point uniquely, giving at most $3K$ representations. \smallskip \noindent\emph{The $B$-point lies in $B_\ell$ and the $A$-point lies in $\PA_\ell$.} There are two possible residues $V+up$ modulo $q$ for the $B$-point. The same argument, using the $A$-side of \eqref{eq:invariant}, gives at most $2K$ representations. \smallskip \noindent\emph{Both points lie in block $\ell$.} Fix their shifts $0\leq s<3$ and $0\leq u<2$. The remaining equation is \[ pX+qY=n-U-V-sq-up. \] Modulo $q$, this determines $X$ uniquely as a residue class. Among the $Lq$ indices $0\leq Xb_i$, the second gives the required bound directly. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] The construction in Section~5 gives infinite positive sets satisfying \eqref{eq:cover}. Proposition~\ref{prop:representations} proves \eqref{eq:bound}, and Lemma~\ref{lem:ordering} proves \eqref{eq:rank}. Since $b_i\to\infty$, \[ \left|\frac{a_i}{b_i}-1\right|\leq\frac5{\sqrt{b_i}} \longrightarrow0. \] The representation function has finite upper limit, which disproves \eqref{eq:question}. \end{proof} \Needspace{22\baselineskip} \section{The everywhere-covering formulation} The same construction also gives a counterexample when the covering condition is imposed on every nonnegative integer, with zero allowed in the summand sets. \begin{corollary}\label{cor:everywhere} There are infinite sets $A^*,B^*\subseteq\Nzero$ with $A^*+B^*=\Nzero$, whose increasing enumerations satisfy $a_i^*/b_i^*\to1$ and whose ordered representation function is uniformly bounded. \end{corollary} \begin{proof} Let $A,B$ be the sets in Theorem~\ref{thm:main} and put $N=16384$. The complement of $B$ in $\Nzero$ is infinite. Otherwise, for any $47006$ distinct elements $a$ of $A$, every sufficiently large $n$ would have $n-a\in B$ for all of them. This would give $\rAB(n)\geq47006$, contradicting \eqref{eq:bound}. Set $F=\{0,\ldots,N-1\}\setminus A$ and $m=|F|$. We have $m\geq1$ because $0\notin A$. Choose a set $G\subseteq\Nzero\setminus B$ with $0\in G$ and $|G|=m$, and put $A^*=A\cup F$, $B^*=B\cup G$. Every $n