Characterizing the Sum of Two Cubes

Kevin A. Broughan University of Waikato Hamilton 2001 New Zealand

                       kab@waikato.ac.nz

Abstract

An intrinsic characterization of positive integers which can be represented as the sum or difference of two cubes is given. Every integer has a smallest multiple which is a sum of two cubes and such that the multiple, in the form of an iterated composite function of the integer, is eventually periodic with period one or two. The representation of any integer as the sum of two cubes to a fixed modulus is always possible if and only if the modulus is not divisible by 7 or 9.

1 Introduction

Consider the beautiful characterization of numbers which are the sum of two squares, namely [2, Theorem 366] a number n is the sum of two squares if and only if all the prime factors of n of the form 4m + 3 have even exponent in the standard factorization of n. This is not matched by any known comparable condition for the sum of two cubes. In the absence of such a characterization there has been a great deal of interest in questions related to the sum of two cubes, see for example [6], [8].

In Section 2 we give an intrinsic characterization, a property of n itself, which will determine whether it is representable as the sum of two cubes or not. The characterization is not so simple but is complete, and covers both n = x^{3} + y^{3} and n = x^{3} − y^{3}. To have a representation in either of these forms n must have a divisor m which satisfies strict conditions: m^{3} − n/m must be divisible by 3 with quotient l satisfying m^{2} + 4l is a perfect square. The applicable range for values of m and sign of l discriminates between the two equations n = x^{3} + y^{3} and n = x^{3} − y^{3}.

In Section 3 the equation n = x^{3} + y^{3} modulo m is considered and the main result of the paper proved. The divisibility of m by 7 or 9 is definitive, in that it is in these cases, and only in these cases, that the form n ≡ x^{3} + y^{3} mod m does not have a solution for every n.

Every positive integer has a multiple which is the sum of two cubes. This phenonena is studied in Section 4 where functions, θ(n) and η(n) giving the “minimum multiple” of an integer which represents the sum of two cubes, are defined. These functions, when iterated, are eventually periodic with period length one or two.

2 Characterizing the sum of two cubes

Theorem 2.1. Let n be a positive integer. Then the equation n = x^{3} + y^{3} has a solution in positive integers x and y if and only if the following three conditions are satisfied:

1a. There exists a divisor m | n with n^{\frac{1}{3}} ≤ m ≤ 2^{\frac{2}{3}} n^{\frac{1}{3}} such that

2a. for some positive integer l, m^{2} − n/m = 3l and such that

3a. the integer m^{2} − 4l is a perfect square.

The conditions equivalent to the existence of a solution to n = x^{3} − y^{3} in positive integers are as follows:

1b. There exists a divisor m | n with 1 ≤ m < n^{\frac{1}{3}} such that

2b. for some positive integer l, n/m − m^{2} = 3l and such that

3b. the integer m^{2} + 4l is a perfect square.

Proof. First we show that if the equation n = x^{3} + y^{3} has a solution then (1a-3a) must be satisfied.

(1a) Let n = u^{3} + v^{3} = (u + v)(u^{2} − uv + v^{2}) in positive integers u, v and let m = u + v so m | n. The form

x^{2} − xy + y^{2} = \frac{n}{m}

is the equation of an ellipse, called here E, with major axis the line y = x, and (u, v) is a point on the ellipse in the first quadrant.

The straight line m = x + y cuts the x-axis at x = m which is equal or to the right of the point where the ellipse cuts the axis, namely x = \sqrt{n/m}. Hence

\sqrt{\frac{n}{m}} ≤ m ⇒ n^{\frac{1}{3}} ≤ m (1).

The length of the major axis of E is \sqrt{2n/m} and the distance of the line x + y = m from the origin m/\sqrt{2}. Since the line cuts the ellipse we must have

\frac{m}{\sqrt{2}} ≤ \sqrt{\frac{2n}{m}} ⇒ m ≤ 2^{\frac{2}{3}} n^{\frac{1}{3}} (2).

By (1) and (2)

n^{\frac{1}{3}} ≤ m ≤ 2^{\frac{2}{3}} n^{\frac{1}{3}} .

(2a) Substitute v = m − u in n/m = u^{2} − uv + v^{2} to obtain the equation

\frac{n}{m} = 3(u^{2} − mu) + m^{2}.

Hence 3 | m^{2} − n/m. Since, by (1a) n ≤ m^{3}, l = (m^{2} − n/m)/3 ≥ 0.

(3a) Now consider the value of l: l = −u^{2} + mu. This means u is an integer root of the quadratic equation x^{2} − mx + l = 0 with integer coefficients, so the discriminant, namely m^{2} − 4l, must be a perfect square.

(1b) If u ≥ 0 and v < 0 then the point (u, v) lies on E in the fourth quadrant so the line m = x + y cuts the x-axis to the left of x = \sqrt{n/m} leading to the bound m < n^{1/3}. The proofs of (2b) and (3b) are similar to those of (2a) and (3a).

Now assume that (1a-3a) are satisfied. (The case (1b-3b) is similar.)

Given m, from (1a) define l using (1b) so 3l = m^{2} − n/m. Let x_{1}, x_{2} be the two integer roots (given by condition (1c) of the quadratic equation

x^{2} − mx + l = 0

so x_{1}x_{2} = l, the product of the roots, and m = x_{1} + x_{2}, the sum of the roots.

Then

n = m · \frac{n}{m}
= (x_{1} + x_{2})(m^{2} − 3l)
= (x_{1} + x_{2})((x_{1} + x_{2})^{2} − 3x_{1}x_{2})
= (x_{1} + x^{2})(x_{1}^{2} − x_{1}x_{2} + x_{2}^{2})
= x_{1}^{3} + x_{2}^{3}.

3 Modular Constraints

By analogy with the sum of two squares it is natural to consider modular conditions on n for it to be representable as the sum of two cubes. Something interesting is happening here when the modulus is divisible by 7 or 9:

Example 3.1. Let n ∈ ℕ be such that n satisfies one of the congruences listed below. Then n = x^{3} + y^{3} has no solution in ℤ:

1. n ≡ 3 or 4 mod 7,

2. n ≡ 3, 4, 5 or 6 mod 9,

3. n ≡ 3, 4, 5, 6, 10, 11, 12, 13, 14, 15, 17, 18, 21, 22, 23, 24, 25, 30, 31, 32, 33, 38, 39, 40, 41, 42, 45, 46, 48, 49, 50, 51, 52, 53, 57, 58, 59, or 60 mod 63.

Theorem 3.2. Let m, n be such that there exist u, v, x, y with

m ≡ u^{3} + v^{3} mod 7
n ≡ x^{3} + y^{3} mod 9.

Then there exist integers A, B such that

28m − 27n ≡ A^{3} + B^{3} mod 63.

Furthermore, every sum of two cubes modulo 63 arises in this manner.

Proof. Let A = 28u − 27x and B = 28v − 27y and expand A^{3} + B^{3} modulo 63 to derive the given equation. A computation verifies the last claim of the theorem statement.

If N ≥ 2 let

δ(N) = \frac{#\{n ∈ \{1, …, N\} : n ≡ x^{3} + y^{3} mod N has a solution\}}{N}.

Lemma 3.1. Let n ∈ ℤ be given and p be a prime with p ≠ 3. Then if the equation n ≡ x^{3} + y^{3} mod p has a solution so also does the equation n ≡ x^{3} + y^{3} mod p^{α} for every α ≥ 1.

Proof. Let n ≡ x^{3} + y^{3} mod p. Assume that p ∤ x. (If p | x and p | y then p | n, so we can use x = 1 and y = −1.) Assume, using induction, that n ≡ x^{3} + y^{3} mod p^{α} has a solution for some α ≥ 1 with p ∤ x. Then

x^{3} + y^{3} − n = lp^{α}

for some l ∈ ℤ and so, if m is an integer to be chosen later,

(x + mp^{α})^{3} = y^{3} − n ≡ x^{3} + y^{3} − n + 3mx^{2}p^{α} mod p^{α+1}
≡ p^{α}(l + 3mx^{2}) mod p^{α+1}.

But p ≠ 3 and p ∤ x so we can choose m with l + 3mx^{2} ≡ 0 mod p giving

n ≡ (x + mp^{α})^{3} + y^{3} mod p^{α+1}

and p ∤ x + mp^{α} since p ∤ x. This completes the inductive step.

Lemma 3.2. Let n ∈ ℤ be given. Then if the equation n ≡ x^{3} + y^{3} mod 3^{2} has a solution so also does the equation n ≡ x^{3} + y^{3} mod 3^{α} for every α ≥ 2.

Proof. Let n ≡ x^{3} + y^{3} mod 3^{2}. Assume that 3 ∤ x. (If 3 | x and 3 | y then 3^{2} | n, so we can use x = 1 and y = −1.) Assume that n ≡ x^{3} + y^{3} mod 3^{α} has a solution for some α ≥ 2 with 3 ∤ x. Then

x^{3} + y^{3} − n = l3^{α}

for some l ∈ ℤ and so, if m is an integer to be chosen later,

(x + m3^{α−1})^{3} = y^{3} − n ≡ x^{3} + y^{3} − n + mx^{2}3^{α} mod 3^{α+1}
≡ 3^{α}(l + mx^{2}) mod 3^{α+1}.

Choose m with l + mx^{2} ≡ 0 mod 3 giving

n ≡ (x + m3^{α−1})^{3} + y^{3} mod 3^{α+1}.

Theorem 3.3. The positive integer m is such that 7 ∤ m and 9 ∤ m if and only if δ(m) = 1. If 7 | m and 9 ∤ m then δ(m) = 5/7. If 9 | m and 7 ∤ m then δ(m) = 5/9. If 7 | m and 9 | m then δ(m) = 25/63.

Proof. The “if” direction follows directly from the example at the start of this section, so assume m is such that 7 ∤ m and 9 ∤ m.

By [9], δ(p) = 1 for p ≠ 2, 3, 7. Simple computations lead to the values δ(2) = 1, δ(3) = 1, δ(9) = 5/9, δ(7) = 5/7.

By the Chinese remainder theorem and the definition of addition and multiplication in a product ring, if (N, M) = 1, then δ(MN) = δ(M)δ(N). Hence we need only consider values of m which are prime powers.

By Lemma 1, if p ≠ 3, δ(p^{α}) = δ(p) for all α ≥ 1. By Lemma 2, δ(3^{α}) = δ(9) for all α ≥ 2 and the theorem follows directly.

4 The Functions Theta and Eta

Definition 4.1. Let n ∈ ℕ. Then θ(n) is the least positive integer such that the Diophantine equation

nθ(n) = x^{3} + y^{3}

has a solution with x ≥ 0 and y ≥ 0.

Because

(n + 1)^{3} + (n − 1)^{3} = 2n(n^{2} + 3)

the function θ is well defined and θ(n) ≤ 2(n^{2} + 3). The positive integer n is expressible as the sum of two positive cubes if and only if θ(n) = 1.

Sometimes a distinction is made between general solutions to equations like n = x^{3} + y^{3} and the narrower class of so called “proper” or “primitive” solutions, namely those with x and y having no common factors, (x, y) = 1. This is to exclude the solutions ab^{3} = (xb)^{3} + (yb)^{3}, given the representation a = x^{3} + y^{3}.

Definition 4.2. Let n ∈ ℕ. Then η(n) is the least positive integer such that the Diophantine equation

nη(n) = x^{3} + y^{3}

has a solution with x ≥ 0 and y ≥ 0 and (x, y) = 1.

Because

(n + 1)^{3} + (n − 1)^{3} = 2n(n^{2} + 3)

and satisfies (n + 1, n − 1) = 1 if n is even, and

(\frac{n + 1}{2})^{3} + (\frac{n − 1}{2})^{3} = n(\frac{n^{2} + 3}{4})

satisfies (\frac{n+1}{2}, \frac{n−1}{2}) = 1 if n is odd, the function η is well defined and η(n) = O(n^{2}) also. The positive integer n is expressible as the sum of two positive cubes which are coprime if and only if η(n) = 1. Clearly θ(n) ≤ η(n) for all n ∈ ℕ.

Theorem 4.3. The composite function values θ∘θ and η ∘η satisfy θ^{2}(n) ≤ n and η^{2}(n) ≤ n for all n ∈ ℕ.

Proof. By the definition of θ applied to θ(n), there exist x, y such that θ^{2}(n) · θ(n) = x^{3} + y^{3} and θ^{2}(n) is the smallest multiple of θ(n) which can be expressed as the sum of two cubes. But n · θ(n) = u^{3} + v^{3} for some u, v also. Therefore θ^{2}(n) ≤ n. The proof for η is similar.

Theorem 4.4. For each n ∈ ℕ the sequences (θ^{j}(n)) and (η^{j}(n)) are either constant after a finite number of terms or periodic with period 2.

Proof. Since for all n ∈ ℕ, n ≥ θ^{2}(n) ≥ 1, the sequence of values (θ^{j}(n) is eventually periodic. Assume the length of the period is n ≥ 3. Then there exist distinct integers a_{1}, ⋯, a_{n} with

θ(a_{1}) = a_{2}, θ(a_{2}) = a_{3}, ⋯, θ(a_{n−1} = a_{n}, θ(a_{n}) = a_{1}.

If n is even a_{1} ≥ a_{3} ≥ a_{5}, ⋯ ≥ a_{n−1} ≥ a_{1} so a_{1} = a_{3} which is false. If n is odd we cycle through twice:

a_{1} ≥ a_{3} ≥ ⋯ a_{n} ≥ a_{2} ≥ ⋯ ≥ a_{1},

so again a_{1} = a_{3}. Hence the length of the period n must be one or two. The proof for η is similar.

Note that if (x, y) is the closest integral point on n = x^{2} − xy + y^{2} to the line y = −x and such that x + y > 0 then θ(n) ≤ x + y. Another problem is to characterize those n such that θ(n) = x + y, this minimum positive value.

Note also that a function like θ can be defined for forms with appropriate symmetry properties, e.g. f(x, y) = x^{k} + y^{k} for k odd.

Acknowledgements: The support of the Department of Mathematics of the University of Waikato, the discussions held with Ian Hawthorn and the valuable contributions, especially to shortening the proof of Theorem 3, of an anonymous referee are warmly acknowledged.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer Verlag, 1976.

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford, 1979.

[3] K. L. Hua, Introduction to Number Theory, Springer-Verlag, 1982.

[4] S. Lang, Old and new conjectured diophantine inequalities, Bull. Amer. Math. Soc., 23, (1990), 37–75.

[5] L. J. Mordell, Diophantine Equations, Academic Press, 1969.

[6] M. B. Nathanson, Additive Number Theory: The Classical Bases, Springer-Verlag, 1996.

[7] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer-Verlag, 1996.

[8] J. H. Silverman and J. Tate, Rational Points on Elliptic Curves, Springer-Verlag, 1992.

[9] A. G. Vosper, The critical pairs of subsets of a group of prime order. J. London Math. Soc., 31, (1956), 200–205, 280–282.

2000 Mathematics Subject Classification: Primary 11A07; Secondary 11B13, 11B50, 11D25, 11D79, 11P05. Keywords: sum of two cubes; diophantine equation

(Concerned with sequence \underline{A045980}.)

Received March 31 2003; revised version received December 18 2003. Published in Journal of Integer Sequences, January 14 2004.

Return to Journal of Integer Sequences home page.