\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \usepackage{enumerate} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\Large\bf Improved Bounds on the Anti-Waring Number } \vskip 1cm \large Paul LeVan and David Prier\\ Department of Mathematics\\ Gannon University\\ Erie, PA 16541-0001\\ USA\\ \href{mailto:levan006@knights.gannon.edu}{levan006@knights.gannon.edu}\\ \href{mailto:prier001@gannon.edu}{prier001@gannon.edu} \\ \end{center} \vskip .2 in \begin{abstract} The Anti-Waring number, $N(k,r)$, is defined to be the least integer such that it and every larger integer can be written as the sum of the $k^{\rm th}$ powers of $r$ or more distinct positive integers. Several authors have examined this variation of the classical Waring problem. We provide improved bounds for $N(k,r)$ in general and when $k=2$. We then connect this problem to the theory of partitions. We use traditional counting arguments, as well as a generating function methodology that has not yet been applied to finding the Anti-Waring number. \end{abstract} \section{Introduction} In 1770, Waring conjectured that for each positive integer $k$ there exists a $g(k)$ such that every positive integer is a sum of $g(k)$ or fewer $k^{\rm th}$ powers of positive integers. In 1909, Hilbert offered a valid proof of this theorem. The challenge then that became known as the Waring problem was the question that asks, "For each $k$, what is the smallest $g(k)$ such that this statement holds?" The Anti-Waring number, $N(k,r)$, is defined to be the least integer such that it and every larger integer can be written as the sum of the $k^{\rm th}$ powers of $r$ or more distinct positive integers. In 2010, Johnson and Laughlin \cite{Johnson} introduced the Anti-Waring number and provided some initial results and lower bounds. In particular, they noticed that $N(1,r)=\frac{r(r+1)}{2}$. In 2012, Looper and Saritzky \cite{Looper} proved that $N(k,r)$ exists for all positive integers $k$ and $r$. In 2014 and 2015, Prier et al.\ \cite{Prier} and Fuller et al.\ \cite{Fuller} found a method of using certain conditions to verify values of $N(k,r)$. With the aid of computers, they calculated $N(k,r)$ for many values including $2\leq k \leq 5$ and $1\leq r\leq 36$ as well as $N(6,1)$. Currently, only computing limitations impede calculating $N(k,r)$ for a specific $(k,r)$ pair. In this paper, we find improved bounds for $N(k,r)$ in the general case and in the specific case when $k=2$. We also reexamine the question of finding $N(k,r)$ under the lens of generating functions. \section{Definitions}\label{Definitions} For the remainder of the paper, let $r$ and $k$ be positive integers. We say an integer $n$ is $(k,r)$\textit{-good} if one can write it as the sum of $k^{\rm th}$ powers of $r$ or more distinct positive integers, and it is $(k,r)$\textit{-bad} if it is not $(k,r)$-good. For example, 36 is $(3,2)$-good because $36=1^3+2^3+3^3$. However, 37 is $(3,2)$-bad because one cannot write 37 as the sum of two or more distinct cubes. When considering which positive integers are $(k,r)$-good, one should notice that the smallest $(k,r)$-good number is the sum of $k^{\rm th}$ powers of the first $r$ distinct positive integers. In order to simplify notation, we define $P_k(n)$ to be this sum. In other words, $P_k(n)=\sum_{i=1}^{n} i^k $. Here, we allow $n$ to be any nonnegative integer including $0$. In 1994, Bateman et al.\ studied the sum of distinct squares \cite{Bateman}. We use results from that work to further the study of $N(k,r)$ in this article. However, they examined a slightly different question than that of the Anti-Waring question. Whereas $N(2,r)$ concerns integers that can be written as the sum of $r$ \textit{or more} distinct squares, Bateman et al.\ considered those integers one can write as the sum of \textit{exactly} $r$ distinct squares. This distinction motivates the following analogous definitions. Define $N_0(k,r)$ to be the first integer such that it and every larger integer is the sum of $k^{\rm th}$ powers of exactly $r$ distinct positive integers. An integer $n$ is $(k,r)_0$\textit{-good} if one can write it as the sum of $k^{\rm th}$ powers of exactly $r$ distinct positive integers, and it is $(k,r)_0$\textit{-bad} if it is not $(k,r)_0$-good. For example, 28 is $(3,2)_0$-good because $28=1^3+3^3$. However, 36 is $(3,2)_0$-bad because one cannot write 36 as the sum of exactly two distinct cubes. Notice here that if $n$ is $(k,r)_0$-good, then it is by definition $(k,r)$-good. However, the reverse implication is not true. A positive integer could be $(k,r)$-good but not $(k,r)_0$-good. As shown above, 36 is $(3,2)$-good, but it is not $(3,2)_0$-good. \section{Improved bounds for $N(k,r)$} The following two results represent the previously known bounds on $N(k,r)$. \begin{lemma} \label{L1} \cite{Johnson} \leavevmode \begin{enumerate}[i] \item $N(1,r)=P_1(r)=\frac{r(r+1)}{2}$. \item If $k>1$, then $P_k(r-1)+(r+1)^k \leq N(k,r)$. \end{enumerate} \end{lemma} \begin{lemma} \label{L2} \cite{Looper} For $k>1$ and $r\geq 1$, $N(k,r)$ exists. \end{lemma} Lemma \ref{L1} gives the exact value of $N(1,r)$, and together, Lemmas \ref{L1} and \ref{L2} imply the following bound. $$P_k(r-1)+(r+1)^k \leq N(k,r)< \infty $$ \begin{lemma} \label{L3} $P_k(r)$ is the smallest $(k,r)$-good number, and $P_k(r-1)+(r+1)^k$ is the smallest $(k,r)$-good number greater than $P_k(r)$. \end{lemma} \begin{proof} By definition, $P_k(r)$ is the smallest $(k,r)$-good number. Any $(k,r)$-good number larger than $P_k(r)$ must contain $a^k$ for some $a>r$. The least such $a$ is $(r+1)$, and therefore the least sum of $r$ or more distinct $k^{\rm th}$ powers other than $P_k(r)$ must be $P_k(r-1)+(r+1)^k$. \end{proof} Note that the above lemma is true for all positive integers $r$ including $r=1$. Also, for all values of $k>1$, it is true that $P_k(r-1)+(r+1)^k-P_k(r)>1$ which implies that there are $(k,r)$-bad numbers in between the two smallest $(k,r)$-good numbers. This result then implies part $ii$ of Lemma \ref{L1}. \begin{theorem} \label{T1} For $k>1$ and $r>1$, we have $P_k(r-2)+r^k+(r+1)^k \leq N(k,r)$. \end{theorem} \begin{proof} The next $(k,r)$-good number after $P_k(r-1)+(r+1)^k$ must contain in its sum either an $(r+1)^k$ or an $a^k$ for some $a>(r+1)$. The least $(k,r)$-good number that contains $(r+1)^k$ and is not $P_k(r-1)+(r+1)^k$ is $P_k(r-2)+r^k+(r+1)^k$. The least $(k,r)$-good number that contains an $a^k$ for some $a>(r+1)$ is $P_k(r-1)+(r+2)^k$. The difference, $d$, between these numbers is \begin{displaymath} d=\Bigl(P_k(r-1)+(r+2)^k\Bigr) - \Bigl(P_k(r-2)+r^k+(r+1)^k\Bigr)=\Bigl((r+2)^k-(r+1)^k\Bigr)-\Bigl(r^k-(r-1)^k\Bigr). \end{displaymath} By the binomial theorem, $\bigl((r+2)^k-(r+1)^k\bigr)=\sum_{i=0}^{k-1} \binom{k}{i} (r+1)^i$, and $\bigl(r^k-(r-1)^k\bigr)=\sum_{i=0}^{k-1} \binom{k}{i} (r-1)^i$. Therefore, $d= \sum_{i=0}^{k-1} \binom{k}{i} (r+1)^i-\sum_{i=0}^{k-1} \binom{k}{i} (r-1)^i=\sum_{i=0}^{k-1} \binom{k}{i}\bigl((r+1)^i-(r-1)^i\bigr)$. If $i=0$, then $\binom{k}{0}\bigl((r+1)^0-(r-1)^0\bigr)=0$, so $d$ can be rewritten as \begin{displaymath} d=\sum_{i=1}^{k-1} \binom{k}{i}\Bigl((r+1)^i-(r-1)^i\Bigr). \end{displaymath} For $i>0$, it is true that $\bigl((r+1)^i-(r-1)^i\bigr)>0$. Therefore, $d$ is positive and thus $P_k(r-2)+r^k+(r+1)^k$ must be the third $(k,r)$-good number in numerical order. As long as $k>1$, the difference between the third $(k,r)$-good number $\bigl(P_k(r-2)+r^k+(r+1)^k\bigr)$, and the second $(k,r)$-good number $\bigl(P_k(r-1)+(r+1)^k\bigr)$ is greater than one. These results imply that $\bigl(P_k(r-2)+r^k+(r+1)^k\bigr)-1$ is $(k,r)$-bad, and therefore $P_k(r-2)+r^k+(r+1)^k \leq N(k,r)$. \end{proof} In the previous theorem, we required that $r\geq 2$ in order for $r-2\geq 0$. If $r=1$, then a better lower bound exists. \begin{theorem} \label{T2} For $k>1$, it is true that $4^k\leq N(k,1)$. \end{theorem} \begin{proof} For $k=2$, Sprague proved that $N(2,1)=129$ \cite{Sprague}. Clearly $4^2\leq 129$.\\ For $k>2$, the following is a list of the first eight $(k,1)$-good numbers in numerical order. \begin{displaymath} 1^k< 2^k< 2^k+1^k< 3^k< 3^k+1^k< 3^k+2^k <3^k+2^k+1^k< 4^k \end{displaymath} The only non-obvious inequality in this list is the last one claiming that $ 3^k+2^k+1^k< 4^k$. Indeed, consider the difference $d=(4^k)-(3^k+2^k+1^k)$. By the binomial theorem, $4^k-3^k=\sum_{i=0}^{k-1} \binom{k}{i}3^k=\sum_{i=1}^{k-1} \binom{k}{i}3^k+1$. Therefore, $d=\sum_{i=1}^{k-1} \binom{k}{i}3^k+1-2^k-1=\sum_{i=1}^{k-1} \binom{k}{i}3^k-2^k$. Since $k>2$, it is true that $d=\binom{k}{k-1}3^{k-1}+\sum_{i=1}^{k-2} \binom{k}{i}3^k-2^k=k 3^{k-1}+\sum_{i=1}^{k-2} \binom{k}{i}3^k-2^k$. Again, as $k>2$, it must be that $k 3^{k-1}-2^k>2 \cdot 3^{k-1}-2^k > 2 \cdot 2^{k-1} - 2^k=0$. Also, $\sum_{i=1}^{k-2} \binom{k}{i}3^k\geq 1$ for $k>2$. Thus $d\geq 2$. Therefore, not only is $3^k+2^k+1^k< 4^k$, but there must also be at least one $(k,1)$-bad number between $3^k+2^k+1^k$ and $4^k$. This claim is true because no $(k,1)$-good number not listed above can be less than $4^k$. Specifically $4^k-1$ must be $(k,1)$-bad, and therefore $4^k\leq N(k,1)$. \end{proof} Values of $N(k,1)$ are known for $1\le k \le 7$ and are one more than the tabulated values in the sequence \seqnum{A001661} referenced in the On-Line Encyclopedia of Integer Sequences. The value of $N(8,1)$ is known to be greater than $74^8$ \cite{Sloane}. Upon examining the values for $N(k,1)$ in Table \ref{table:1}, one can see that there is significant room for improvement upon the lower bound of $4^k$. \begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline \textbf{$k$}& \textbf{$4^k$} &\textbf{$N(k,1)$}\\ \hline 2 & 16 & 129 \\ 3 & 64 & 12759 \\ 4 & 256 & 5134241 \\ 5 & 1024 & 67898772 \\ 6 & 4096 & 11146309948 \\ 7 & 16384 & 766834015735 \\ \hline \end{tabular} \end{center} \caption{$4^k$ compared to $N(k,1)$ for $1\leq k\leq 7$} \label{table:1} \end{table} Theorems \ref{T1} and \ref{T2} offer improved lower bounds for $N(k,r)$ in general, while the following results offer improved bounds in the special case when $k=2$. In Section \ref{Definitions}, we mentioned that Bateman et al.\ examined $N_0(2,r)$, which is the first integer such that it and every larger integer is the sum of \textit{exactly} $r$ distinct positive squares. In actuality, this paper examined a number denoted $N(r)$ which, using our notation, is defined to be largest $(2,r)_0$-bad number. Therefore $N(r)=N_0(2,r)-1$. Theorems \ref{T3} and \ref{T5} stated below have been rewritten to match the notation of this paper. As previously stated, if one can write a number as the sum of $k^{\rm th}$ powers of exactly $r$ distinct positive integers, then one can certainly write that number as the sum of $k^{\rm th}$ powers of $r$ or more distinct positive integers. Hence, we have the following lemma. \begin{lemma} \label{L4} As long as $N_0(k,r)$ exists, $N(k,r)\leq N_0(k,r)$. \end{lemma} For example, $N_0(2,5)=246$, but $N(2,5)=198$. Indeed, $245=1^2+2^2+3^2+5^2+6^2+7^2+11^2$ is not the sum of exactly 5 distinct squares but is the sum of 5 \textit{or more} distinct squares. The following lemma is not a new result. See, for instance, Conway and Fung \cite[pp.~137--140]{Conway}. \begin{lemma} The number, $N_0(2,r)$, does not exist for $r\in \{1,2,3,4\}$. \end{lemma} \begin{proof} For $r=1$, any non-square natural number is not expressible as the sum of one square. For $r=2$, Fermat's two-square theorem implies that numbers with prime decomposition containing a prime of the form $4 a + 3$ raised to an odd power, for some integer $a$, are not expressible as the sum of two squares of not necessarily distinct integers. For $r=3$, Legendre's three-square theorem implies that numbers of the form $4^a (8b+7)$, for integers $a$ and $b$, are not expressible as the sum of three squares of not necessarily distinct integers. For $r=4$, the numbers not expressible as the sum of four positive squares are $1,3,5,9,11,17,29,41$ and numbers of the form $2 (4^a), 6 (4^a),$ or $14 (4^a)$, for some integer $a$ \cite{Conway}. \end{proof} Bateman et al.\ \cite{Bateman} proved the following concerning $N_0(2,r)$. \begin{theorem} \cite{Bateman} \label{T3} $N_0(2,r)\leq P_2(r)+2r\sqrt{2r}+44r^{5/4}+108r$ for $r\geq 5$. \end{theorem} Bateman et al.\ actually proved $N_0(2,r)\leq P_2(r)+2r\sqrt{2r}+44r^{5/4}+108r$ for $r\geq 166$. However, they also calculated the exact value of $N_0(2,r)$ for $5\leq r\leq 400$. For $5 \leq r\leq 165$, $N_0(2,r)$ satisfies this inequality. Therefore, Theorem \ref{T3} is true for $r\geq 5$. Using the theorem above, we prove a new bound on $N(2,r)$ in general. \begin{theorem} \label{T4} If $r>1$, then $P_2(r-2)+r^2+(r+1)^2 \leq N(2,r)\leq P_2(r)+2r\sqrt{2r}+44r^{5/4}+108r$. \end{theorem} \begin{proof} If $1\leq r\leq 4$, then $N(2,r)=129$ \cite{Prier}, which is less than $P_2(r)+2r\sqrt{2r}+44r^{5/4}+108r$. This observation along with Theorem \ref{T1}, Lemma \ref{L4} and Theorem \ref{T3} directly implies the result. \end{proof} Though the main results of Bateman et al.\ \cite{Bateman} involved sums of distinct squares, they did prove the following result concerning sums of distinct $k^{\rm th}$ powers for integers $k\geq 2$. \begin{theorem}\cite{Bateman} \label{T5} For sufficiently large $r$, $N_0(k,r) = \frac{r^{k+1}}{k+1}+O(r^k)$. \end{theorem} This result implies that $N_0(k,r)$ is asymptotic to $P_k(r)$. As $P_k(r) \le N(k,r) \le N_0(k,r)$, we see that $N(k,r)$ tends to be ``close" to $P_k(r)$ for large enough $r$. If one developed a more precise relationship of this type, then one could significantly reduce the complexity in computation of $N(k,r)$. \section{Generating functions} Many, including Euler and Ramanujan, have studied the theory of generating functions concerning partitions of all types \cite{Andrews}. For this discussion, define the $q$-Pochhammer symbol to be the product $(a;q)_m = \prod_{p = 0}^{m-1} (1-a q^p)$ and $[x^n]f(x)$ to be the $n^{\rm th}$ coefficient of $f(x)$ in the associated Laurent series of $f(x)$. Combinatorially, the $q$-Pochhammer symbol relates to the generating function of many partition counting functions. For instance, $[q^n](q;q)_m^{-1}$ gives the number of ways one can express $n$ as the sum of not necessarily distinct nonnegative integers of size at most $m$ \cite[Ch.\ 3]{Subset}. $[a^r q^n](-aq;q)_\infty$ gives the number of ways one can express $n$ as the sum of exactly $r$ distinct natural numbers \cite[Ch.\ 3]{Subset}. Thus, $n$ is $(1,r)_0$-good if $[a^r q^n](-aq;q)_\infty > 0$. We may now give an alternative proof to part $i$ of Lemma \ref{L1}, by first examining $N_0(1,r)$. \begin{theorem} $N_0(1,r)=\binom{r+1}{2}$. \end{theorem} \begin{proof} To obtain a formula for $N_0(1,r)$, it suffices to find the smallest power of $q$ in $[a^r](-aq;q)_\infty$ such that it and all following powers have nonzero coefficients, and thus are $(1,r)_0$-good. To find this power, we need the following result. The $q$-binomial theorem \cite{Andrews}: $$ (a;q)_\infty = \sum_{i = 0}^\infty \frac{(-1)^i q^{\binom{i}{2}}}{(q;q)_i} a^i $$ We may thus express: $$ (-aq;q)_\infty = \sum_{i = 0}^\infty \frac{(-1)^i q^{\binom{i}{2}}}{(q;q)_i} (-aq)^i = \sum_{i = 0}^\infty \frac{q^{\binom{i + 1}{2}}}{(q;q)_i} a^i $$ One can represent every nonnegative integer as the sum of not necessarily distinct nonnegative integers. Therefore, $[q^n](q;q)_i^{-1} \geq 1$ for $i\geq 0$. However, the first nonzero coefficient of $[a^r](-aq;q)_\infty$ is a coefficient of $q^{\binom{r+1}{2}}$. Therefore, $[a^rq^n](-aq;q)_\infty \neq 0$ if and only if $n\geq \binom{r+1}{2}$. Thus, $N_0(1,r)=\binom{r+1}{2}$. \end{proof} \begin{corollary} $N(1,r)=\binom{r+1}{2}$. \end{corollary} \begin{proof} $P_1(r)=\binom{r+1}{2}\leq N(1,r) \leq N_0(1,r)=\binom{r+1}{2}$. \end{proof} If we consider a generalized $q$-Pochhammer symbol, defined as $(a;q)_{m,k} = \prod_{p = 1}^{m-1} (1-a q^{p^k})$, we can obtain information for $N_0(k,r)$. In the case of $k=1$, the original $q$-Pochhammer symbol is recovered. The coefficient, $[a^r q^n](-a;q)_{\infty,k}$, gives the number of ways one can express $n$ as the sum of exactly $r$ $k^{\rm th}$ powers of distinct natural numbers \cite[Ch.\ 3]{Subset}. Hence:\\ \begin{lemma} $n$ is $(k,r)_0$-good if $[a^r q^n](-a;q)_{\infty,k} > 0$. \end{lemma} The case of $k \geq 2$ seems significantly more challenging than the case of $k=1$. An explicit summation formula for the product generating function can be found in terms of Bell polynomials of sums of the form $\sum_{p=1}^\infty x^{p^k}$. These sums reduce easily into a closed form when $k=1$, but they become much more complex for $k\geq 2$. When $k=2$, they develop into a closed expression in terms of the well studied Jacobi Theta functions. Although this method did not yield any results concerning a generalized formula for $N_0(k,r)$, it can be helpful in computing $N_0(k,r)$ for specific, small values of $r$ and $k$. \begin{thebibliography}{99} \bibitem{Andrews} G. E. Andrews and K. Eriksson, \textit{Integer Partitions}, Cambridge University Press, 2004. \bibitem{Bateman} P. T. Bateman, A. J. Hildebrand, and G. B. Purdy, Sums of distinct squares, \textit{Acta Arith.} \textbf{67} (1994), 349--380. \bibitem{Conway} J. H. Conway and F. Y. C. Fung, The Sensual (Quadratic) Form, Vol.~26 of Carus Mathematical Monographs, Mathematical Association of America, 1997. \bibitem{Fuller} C. Fuller and R. H. Nichols Jr., Generalized Anti-Waring numbers, \textit{J. Integer Sequences} \textbf{18} (2015), \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Fuller/fuller2.html}{Article 15.10.5}. \bibitem{Prier} C. Fuller, D. Prier, and K. Vasconi, New results on an anti-Waring problem. \textit{Involve} \textbf{7} (2014), 239--244. \bibitem{Johnson} P. Johnson, Jr. and M. Laughlin, An Anti-Waring conjecture and problem, \textit{Int. J. Math. Comput. Sci.} \textbf{6} (2011), 21--26. \bibitem{Looper} N. Looper and N. Saritzky, An Anti-Waring theorem, \textit{J. Combin. Math. and Combin. Comput.} \textbf{99} (2016), 237--240. \bibitem{Roth} K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions. \textit{Quart. J. Math., Oxford Ser. } (2) \textbf{5}, (1954), 241--259. \bibitem{Sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at \url{http://oeis.org}, 2016. \bibitem{Sprague} R. Sprague, \"Uber Zerlegungen in ungleiche Quadratzahlen. \textit{Math. Z.} \textbf{51} (1948), 289--290. \bibitem{Subset} H. S. Wilf, \textit{Generatingfunctionology}, 2nd edition, Academic Press, 1994. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 \textit{Mathematics Subject Classification}: Primary 11P05; Secondary 05A17, 05A15. \noindent \textit{Keywords}: anti-Waring number, sum of powers, sum of distinct powers, generating function. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A001661}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 20 2017; revised versions received August 9 2017; August 11 2017. Published in {\it Journal of Integer Sequences}, September 5 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}