Improved Bounds on the Anti-Waring Number

Paul LeVan and David Prier Department of Mathematics Gannon University Erie, PA 16541-0001 USA levan006@knights.gannon.edu prier001@gannon.edu

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^{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.

1 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^{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^{th} powers of r or more distinct positive integers. In 2010, Johnson and Laughlin [6] 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 [7] proved that N(k, r) exists for all positive integers k and r. In 2014 and 2015, Prier et al. [5] and Fuller et al. [4] 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 ≤ k ≤ 5 and 1 ≤ r ≤ 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.

2 Definitions

For the remainder of the paper, let r and k be positive integers.

We say an integer n is (k, r)-good if one can write it as the sum of k^{th} powers of r or more distinct positive integers, and it is (k, r)-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^{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) = ∑_{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 [2]. 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 or more distinct squares, Bateman et al. considered those integers one can write as the sum of 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^{th} powers of exactly r distinct positive integers. An integer n is (k, r)_{0}-good if one can write it as the sum of k^{th} powers of exactly r distinct positive integers, and it is (k, r)_{0}-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.

3 Improved bounds for N(k, r)

The following two results represent the previously known bounds on N(k, r).

Lemma 1. [6]

i N(1, r) = P_{1}(r) = \frac{r(r+1)}{2}.

ii If k > 1, then P_{k}(r − 1) + (r + 1)^{k} ≤ N(k, r).

Lemma 2. [7] For k > 1 and r ≥ 1, N(k, r) exists.

Lemma 1 gives the exact value of N(1, r), and together, Lemmas 1 and 2 imply the following bound.

P_{k}(r − 1) + (r + 1)^{k} ≤ N(k, r) < ∞

Lemma 3. 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).

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^{th} powers other than P_{k}(r) must be P_{k}(r − 1) + (r + 1)^{k}.

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 1.

Theorem 4. For k > 1 and r > 1, we have P_{k}(r − 2) + r^{k} + (r + 1)^{k} ≤ N(k, r).

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

d = (P_{k}(r−1)+(r+2)^{k})−(P_{k}(r−2)+r^{k} +(r+1)^{k}) = ((r+2)^{k} −(r+1)^{k})−(r^{k} −(r−1)^{k}).

By the binomial theorem, ((r + 2)^{k} − (r + 1)^{k}) = ∑_{i=0}^{k−1} \binom{k}{i}(r + 1)^{i}, and (r^{k} − (r − 1)^{k}) = ∑_{i=0}^{k−1} \binom{k}{i}(r − 1)^{i}. Therefore, d = ∑_{i=0}^{k−1} \binom{k}{i}(r + 1)^{i} − ∑_{i=0}^{k−1} \binom{k}{i}(r − 1)^{i} = ∑_{i=0}^{k−1} \binom{k}{i}((r + 1)^{i} − (r − 1)^{i}). If i = 0, then \binom{k}{0}((r + 1)^{0} − (r − 1)^{0}) = 0, so d can be rewritten as

d = ∑_{i=1}^{k−1} \binom{k}{i}((r + 1)^{i} − (r − 1)^{i}).

For i > 0, it is true that ((r + 1)^{i} − (r − 1)^{i}) > 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 (P_{k}(r−2)+r^{k} +(r+1)^{k}), and the second (k, r)-good number (P_{k}(r−1)+(r+1)^{k}) is greater than one. These results imply that (P_{k}(r−2)+r^{k}+(r+1)^{k})−1 is (k, r)-bad, and therefore P_{k}(r−2)+r^{k}+(r+1)^{k} ≤ N(k, r).

In the previous theorem, we required that r ≥ 2 in order for r − 2 ≥ 0. If r = 1, then a better lower bound exists.

\begin{matrix}k & 4^{k} & N(k, 1) \\ 2 & 16 & 129 \\ 3 & 64 & 12759 \\ 4 & 256 & 5134241 \\ 5 & 1024 & 67898772 \\ 6 & 4096 & 11146309948 \\ 7 & 16384 & 766834015735 \end{matrix}

Table 1: 4^{k} compared to N(k, 1) for 1 ≤ k ≤ 7

Theorem 5. For k > 1, it is true that 4^{k} ≤ N(k, 1).

Proof. For k = 2, Sprague proved that N(2, 1) = 129 [10]. Clearly 4^{2} ≤ 129. For k > 2, the following is a list of the first eight (k, 1)-good numbers in numerical order.

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}

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} = ∑_{i=0}^{k−1} \binom{k}{i}3^{k} = ∑_{i=1}^{k−1} \binom{k}{i}3^{k} + 1. Therefore, d = ∑_{i=1}^{k−1} \binom{k}{i}3^{k} + 1 − 2^{k} − 1 = ∑_{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} + ∑_{i=1}^{k−2} \binom{k}{i}3^{k} − 2^{k} = k3^{k−1} + ∑_{i=1}^{k−2} \binom{k}{i}3^{k} − 2^{k}. Again, as k > 2, it must be that k3^{k−1} − 2^{k} > 2 · 3^{k−1} − 2^{k} > 2 · 2^{k−1} − 2^{k} = 0. Also, ∑_{i=1}^{k−2} \binom{k}{i}3^{k} ≥ 1 for k > 2. Thus d ≥ 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} ≤ N(k, 1).

Values of N(k, 1) are known for 1 ≤ k ≤ 7 and are one more than the tabulated values in the sequence \underline{A001661} referenced in the On-Line Encyclopedia of Integer Sequences. The value of N(8, 1) is known to be greater than 74^{8} [9]. Upon examining the values for N(k, 1) in Table 1, one can see that there is significant room for improvement upon the lower bound of 4^{k}.

Theorems 4 and 5 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 2, 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 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 8 and 10 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^{th} powers of exactly r distinct positive integers, then one can certainly write that number as the sum of k^{th} powers of r or more distinct positive integers. Hence, we have the following lemma.

Lemma 6. As long as N_{0}(k, r) exists, N(k, r) ≤ N_{0}(k, r).

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 or more distinct squares.

The following lemma is not a new result. See, for instance, Conway and Fung [3, pp. 137– 140].

Lemma 7. The number, N_{0}(2, r), does not exist for r ∈ {1, 2, 3, 4}.

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 4a + 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 [3].

Bateman et al. [2] proved the following concerning N_{0}(2, r).

Theorem 8. [2] N_{0}(2, r) ≤ P_{2}(r) + 2r\sqrt{2r} + 44r^{5/4} + 108r for r ≥ 5.

Bateman et al. actually proved N_{0}(2, r) ≤ P_{2}(r) + 2r\sqrt{2r} + 44r^{5/4} + 108r for r ≥ 166. However, they also calculated the exact value of N_{0}(2, r) for 5 ≤ r ≤ 400. For 5 ≤ r ≤ 165, N_{0}(2, r) satisfies this inequality. Therefore, Theorem 8 is true for r ≥ 5.

Using the theorem above, we prove a new bound on N(2, r) in general.

Theorem 9. If r > 1, then P_{2}(r−2)+r^{2}+(r+1)^{2} ≤ N(2, r) ≤ P_{2}(r)+2r\sqrt{2r}+44r^{5/4}+108r.

Proof. If 1 ≤ r ≤ 4, then N(2, r) = 129 [5], which is less than P_{2}(r) + 2r\sqrt{2r} + 44r^{5/4} + 108r. This observation along with Theorem 4, Lemma 6 and Theorem 8 directly implies the result.

Though the main results of Bateman et al. [2] involved sums of distinct squares, they did prove the following result concerning sums of distinct k^{th} powers for integers k ≥ 2.

Theorem 10. [2] For sufficiently large r, N_{0}(k, r) = \frac{r^{k+1}}{k+1} + O(r^{k}).

This result implies that N_{0}(k, r) is asymptotic to P_{k}(r). As P_{k}(r) ≤ N(k, r) ≤ 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).

4 Generating functions

Many, including Euler and Ramanujan, have studied the theory of generating functions concerning partitions of all types [1]. For this discussion, define the q-Pochhammer symbol to be the product (a; q)_{m} = ∏_{p=0}^{m−1}(1 − aq^{p}) and [x^{n}]f(x) to be the n^{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 [11, Ch. 3]. [a^{r}q^{n}](−aq; q)_{∞} gives the number of ways one can express n as the sum of exactly r distinct natural numbers [11, Ch. 3]. Thus, n is (1, r)_{0}-good if [a^{r}q^{n}](−aq; q)_{∞} > 0. We may now give an alternative proof to part i of Lemma 1, by first examining N_{0}(1, r).

Theorem 11. N_{0}(1, r) = \binom{r+1}{2}.

Proof. To obtain a formula for N_{0}(1, r), it suffices to find the smallest power of q in [a^{r}](−aq; q)_{∞} 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 [1]:

(a; q)_{∞} = ∑_{i=0}^{∞} \frac{(−1)^{i}q^{\binom{i}{2}}}{(q; q)_{i}} a^{i}

We may thus express:

(−aq; q)_{∞} = ∑_{i=0}^{∞} \frac{(−1)^{i}q^{\binom{i}{2}}}{(q; q)_{i}} (−aq)^{i} = ∑_{i=0}^{∞} \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} ≥ 1 for i ≥ 0. However, the first nonzero coefficient of [a^{r}](−aq; q)_{∞} is a coefficient of q^{\binom{r+1}{2}}. Therefore, [a^{r}q^{n}](−aq; q)_{∞} ≠ 0 if and only if n ≥ \binom{r+1}{2}. Thus, N_{0}(1, r) = \binom{r+1}{2}.

Corollary 12. N(1, r) = \binom{r+1}{2}.

Proof. P_{1}(r) = \binom{r+1}{2} ≤ N(1, r) ≤ N_{0}(1, r) = \binom{r+1}{2}.

If we consider a generalized q-Pochhammer symbol, defined as (a; q)_{m,k} = ∏_{p=1}^{m−1}(1−aq^{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)_{∞,k}, gives the number of ways one can express n as the sum of exactly r k^{th} powers of distinct natural numbers [11, Ch. 3]. Hence:

Lemma 13. n is (k, r)_{0}-good if [a^{r}q^{n}](−a; q)_{∞,k} > 0.

The case of k ≥ 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 ∑_{p=1}^{∞} x^{p^{k}}. These sums reduce easily into a closed form when k = 1, but they become much more complex for k ≥ 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.

References

[1] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

[2] P. T. Bateman, A. J. Hildebrand, and G. B. Purdy, Sums of distinct squares, Acta Arith. 67 (1994), 349–380.

[3] J. H. Conway and F. Y. C. Fung, The Sensual (Quadratic) Form, Vol. 26 of Carus Mathematical Monographs, Mathematical Association of America, 1997.

[4] C. Fuller and R. H. Nichols Jr., Generalized Anti-Waring numbers, J. Integer Sequences 18 (2015), Article 15.10.5.

[5] C. Fuller, D. Prier, and K. Vasconi, New results on an anti-Waring problem. Involve 7 (2014), 239–244.

[6] P. Johnson, Jr. and M. Laughlin, An Anti-Waring conjecture and problem, Int. J. Math. Comput. Sci. 6 (2011), 21–26.

[7] N. Looper and N. Saritzky, An Anti-Waring theorem, J. Combin. Math. and Combin. Comput. 99 (2016), 237–240.

[8] K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions. Quart. J. Math., Oxford Ser. (2) 5, (1954), 241–259.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at http://oeis.org, 2016.

[10] R. Sprague, Über Zerlegungen in ungleiche Quadratzahlen. Math. Z. 51 (1948), 289–290.

[11] H. S. Wilf, Generatingfunctionology, 2nd edition, Academic Press, 1994.

2010 Mathematics Subject Classification: Primary 11P05; Secondary 05A17, 05A15. Keywords: anti-Waring number, sum of powers, sum of distinct powers, generating function.

(Concerned with sequence \underline{A001661}.) Received March 20 2017; revised versions received August 9 2017; August 11 2017. Published in Journal of Integer Sequences, September 5 2017. Return to Journal of Integer Sequences home page.