Exact and Asymptotic Evaluation of the Number of Distinct Primitive Cuboids

Werner Hürlimann^{1} Swiss Mathematical Society Feldstrasse 145 CH-8004 Zürich Switzerland

                     whurlimann@bluewin.ch

Abstract

We express the number of distinct primitive cuboids with given odd diagonal in terms of the twisted Euler function with alternating Dirichlet character of period four, and two counting formulas for binary sums of squares. Based on the asymptotic behaviour of the sums of these formulas, we derive an approximation formula for the cumulative number of primitive cuboids.

1 Introduction

A primitive cuboid is a rectangular parallelepiped with natural edges and inner diagonal that have no common factor. It is best described by a solution in non-zero natural numbers x, y, z, t of the Diophantine equation x^{2} + y^{2} + z^{2} = t^{2} satisfying gcd(x, y, z, t) = 1, where x, y, z are the edges and t is the inner diagonal.

With the exception of Shanks [23], [24, Thm. 86, p. 293], which counts the number of primitive cuboids with prime diagonal, no general counting formula seems to be known. Generalizing the proof of Shanks and using results on the twisted Euler function, an exact and an asymptotic formula for the number of distinct primitive cuboids is derived. A more detailed account of the content follows.

1Dedicated to the 75th birthday of N. J. A. Sloane on October 10, 2014.

Section 2 begins with a brief historical survey. The existence of solutions to the primitive cuboid equation was settled by Hurwitz [11] who also gave a formula for the total number of representations of a square as a sum of three squares counting zeros, permutations and sign changes. The total number of primitive representations was first evaluated by Gauss [6]. In modern number theory, it belongs to a variety of similar formulas with dimensions going up to twelve as in Cooper and Hirschhorn [2]. Gauss’s formula is reinterpreted in terms of the twisted Euler function associated to the Dirichlet character of period four. Lemma 4 states the required exact counting formula. Section 3 derives an asymptotic formula for the corresponding cumulative number of primitive cuboids and illustrates its very good approximation.

2 Primitive cuboids and the twisted Euler function

It is well-known that the solutions of the Diophantine equation, also called cuboids and Pythagorean quadruples,

x^{2} + y^{2} + z^{2} = t^{2}  (1)

in non-zero natural numbers x, y, z, t can be obtained from the identity of Lebesgue [17]

x = p^{2} + q^{2} − r^{2} − s^{2}, y = 2(pr + qs), z = 2(ps − qr), t = p^{2} + q^{2} + r^{2} + s^{2}.

Since every integer is a sum of four squares by the theorem of Lagrange [16], it has been stated [3, Chap. VII, p. 265], and [20, p. 194], that every square can be written as a sum of three squares. However, when restricted to non-zero squares, all numbers of the form 2^{k} and 2^{k} · 5 are exceptions, a result due to Hurwitz ([11], [3, p. 271], [25, p. 101]).

Theorem 1. The three squares equation x^{2} + y^{2} + z^{2} = t^{2}, 0 < x ≤ y ≤ z, has a solution if, and only if, the positive integer t is not of the form 2^{k} or 2^{k} · 5, k ∈ ℕ.

Proof. Since a proof by Hurwitz is not available, one must rely on Gordon and Fraser [9] or Fraedrich [5].

Hurwitz [11] also stated (without proof) a formula for the number of representations r_{3}(t^{2}), where in general r_{k}(m) denotes the total number of representations of m as a sum of k ≥ 2 squares such that x_{1}^{2}+x_{2}^{2}+⋯+x_{k}^{2} = m counting zeros, permutations and sign changes. Dickson [3, p. 271] reproduces this formula. A modern version of it with an elementary proof is due to [15].

Theorem 2. Given the unique decomposition t = ∏_{i=1}^{m} p_{i}^{s_{i}} in prime numbers p_{i} and power exponents s_{i}, one has r_{3}(t^{2}) = 6 · ∏_{i=1}^{m} (σ(p_{i}^{s_{i}}) − (−1)^{(p_{i}−1)/2}σ(p_{i}^{s_{i}−1})), where σ(m) counts the sum of all positive divisors of m.

What about the number of primitive representations R_{3}(t^{2}), where similarly to the preceding R_{k}(m) is the number of primitive representations of m as a sum of k ≥ 2 squares counting zeros, permutations and sign changes? In general, given a formula for r_{k}(m), it is possible to derive a formula for R_{k}(m) from it through Möbius inversion of the basic relationship [10, Thm. 1, Section 1.1]:

r_{k}(m) = ∑_{d|m^{2}} R_{k} (\frac{m}{d^{2}}) .

Cooper and Hirschhorn [2] exploit this technique and obtain a wide variety of formulas for R_{k}(m) including the range 2 ≤ k ≤ 8 for any m, and the range 9 ≤ k ≤ 12 for certain values of m. In particular, one has [2, Thm. 2, Eq. (1.19)]

R_{3}(t^{2}) = 6 · ∏_{i=1}^{m} p_{i}^{s_{i}−1} (p_{i} − (−1)^{(p_{i}−1)/2}) .  (2)

Recall that the original evaluation of R_{3}(m) is due to Gauss [6], [3, Chap. VII, p. 262]. Restricting the attention to primitive representations with non-zero entries and gcd(x, y, z, t) = 1, Theorem 1 implies that there exist primitive cuboids with odd diagonals for all t ≠ 5. A formula for the number of distinct primitive cuboids with odd diagonal t does not seem to exist in the literature, with the exception of a prime number t = p, a result due to Shanks [23], [24, Thm. 86, p. 293]. Adopting a terminology similar to the above, let us denote by R_{k}^{d}(m) the number of distinct primitive representations of m as a sum of k ≥ 2 non-zero squares such that x_{1}^{2} + x_{2}^{2} + ⋯ + x_{k}^{2} = m with ∏_{j=1}^{k} x_{j} ≠ 0. Then the number of distinct primitive cuboids with odd diagonal is described by the arithmetic function R_{3}^{d}(t^{2}).

Theorem 3 (Shanks). For a prime of the form p = 8n±1 or p = 8n±5, one has R_{3}^{d}(p^{2}) = n.

We present an alternative but more general formula for arbitrary odd diagonal t ≥ 3 based on analytic number theory. This viewpoint is best suited to derive an asymptotic formula for the cumulative number of primitive cuboids with odd diagonal t ≥ 3 less than or equal to x, as done in Section 3. Starting point is the observation that the finite product in (2) identifies with the twisted Euler (totient) function

φ(t, χ) = t · ∏_{p|t} (1 − χ(p)/p) ,  (3)

where the subscript p|t stands for the primes p_{i} that divides t = ∏_{i=1}^{m} p_{i}^{s_{i}}, and χ(·) is the alternating multiplicative Dirichlet character of period four defined by

χ(p) = \begin{cases}0, & if p = 2; \\ 1, & if p ≡ 1 (mod 4); \\ −1, & otherwise. \end{cases}  (4)

Inserted into (2) the equation gives R_{3}(t^{2}) = 6 · φ(t, χ). This formula yields the number of primitive solutions of (1) counting permutations, sign changes, and zeros. The distinct solutions are of three different forms, namely (x, y, z), (x, y, y) and (x, y, 0), where 0 < x < y < z. Counting permutations and sign changes the number of resulting representations for each of these forms are, respectively, 48 for the form (x, y, z) and 24 for the forms (x, y, y) and (x, y, 0). Now the number of primitive (respectively, distinct primitive) representations of t^{2} as a sum of two squares is equal to, respectively, [2, Thm. 1, Eq. (1.6)]

R_{2}(t^{2}) = \begin{cases}4 · 2^{m}, & if p_{i} ≡ 1 (mod 4), i = 1, …, m; \\ 0, & otherwise; \end{cases}

R_{2}^{d}(t^{2}) = \begin{cases}2^{m−1}, & if p_{i} ≡ 1 (mod 4), i = 1, …, m; \\ 0, & otherwise. \end{cases}

Similarly, if one denotes the number of primitive representations of the form x^{2} + 2y^{2} = t^{2} by R_{2}(t^{2}; 2) and the corresponding number of distinct ones by R_{2}^{d}(t^{2}; 2), one has

R_{2}(t^{2}; 2) = \begin{cases}4 · 2^{m−1}, & if p_{i} ≡ 1, 3 (mod 8), i = 1, …, m; \\ 0, & otherwise; \end{cases}

R_{2}^{d}(t^{2}; 2) = \begin{cases}2^{m−1}, & if p_{i} ≡ 1, 3 (mod 8), i = 1, …, m; \\ 0, & otherwise. \end{cases}

The total number of representations of these different forms must by (2) and (3) satisfy the basic relationship

48 · (R_{3}^{d}(t^{2}) − R_{2}^{d}(t^{2}; 2)) + 24 · R_{2}^{d}(t^{2}; 2) + 24 · R_{2}^{d}(t^{2}) = R_{3}(t^{2}) = 6 · φ(t, χ).

The resulting counting formula is summarized as follows.

Lemma 4. The number of distinct primitive cuboids with odd diagonal t ≥ 3 is given by

R_{3}^{d}(t^{2}) = \frac{1}{8} · φ(t, χ) + \frac{1}{2} (R_{2}^{d}(t^{2}; 2) − R_{2}^{d}(t^{2})) .  (5)

Clearly, the exact calculation of all three terms in (5) requires a factorization table of the distinct prime factors for all odd numbers. Since such tables are necessarily limited to the finite computing and storage capacity of computers, a search for alternative computational tools is necessary. It turns out to be more efficient to study the partial sums below x of the twisted Euler function over all natural numbers 2 ≤ n ≤ x (including even ones), which is denoted by

Φ(x, χ) = ∑_{2≤n≤x} φ(n, χ).

Such sums have been recently studied by Kaczorowski [12] and Kaczorowski and Wiertelak [13, 14], where the required result will be stated in Theorem 6. For now, some preliminary formula that accounts separately for sums over odd and even numbers is needed. The elementary analysis applies as well to other multiplicative Dirichlet characters χ(·) satisfying χ(2) = 0. Consider the partial sums of the twisted Euler function over odd and even numbers denoted by

Φ_{o}(x, χ) = ∑_{{3≤n≤x \atop n odd}} φ(n, χ), Φ_{e}(x, χ) = ∑_{{2≤n≤x \atop n even}} φ(n, χ), Φ(x, χ) = Φ_{o}(x, χ) + Φ_{e}(x, χ). (6)

Lemma 5. Let χ(·) be a multiplicative character satisfying χ(2) = 0. Then the even partial sums in (6) are determined by the formula Φ_{e}(x, χ) = 2 · (1 + Φ(2^{−1} · x, χ)).

Proof. Under the assumption χ(2) = 0 the following basic identity holds:

Φ(x, χ) = ∑_{k=1}^{⌊ln x/ ln 2⌋} 2^{k} + ∑_{k=0}^{⌊ln x/ ln 2⌋−1} 2^{k} · Φ_{o}(2^{−k} · x, χ).  (7)

Indeed, if 2 ≤ n ≤ x is even, then there exists 1 ≤ k ≤ ⌊ln x/ ln 2⌋ such that n = 2^{k} · m with m odd such that 1 ≤ m ≤ 2^{−k} · x, which implies that

Φ_{e}(x, χ) = ∑_{k=1}^{⌊ln x/ ln 2⌋} 2^{k} + ∑_{k=1}^{⌊ln x/ ln 2⌋−1} 2^{k} · Φ_{o}(2^{−k} · x, χ).

Changing the index of summation and noting that ⌊ln x/ ln 2⌋ − 1 = ⌊ln(x/2)/ ln 2⌋, one sees immediately that

Φ_{e}(x, χ) = 2 · (1 + ∑_{j=1}^{⌊ln(x/2)/ ln 2⌋} 2^{j} + ∑_{j=0}^{⌊ln(x/2)/ ln 2⌋−1} 2^{j} · Φ_{o}(2^{−j} · (x/2), χ)) ,

which coincides with 2 · (1 + Φ(2^{−1} · x, χ)) by (7).

3 The cumulative number of primitive cuboids

Based on (5) the total number of primitive cuboids with odd diagonal 3 ≤ t ≤ x is equal to

N_{3}(x) = \frac{1}{8} · Φ_{o}(x, χ) + \frac{1}{2} · (N_{2}(x; 2) − N_{2}(x)) ,  (8)

with the following cumulative counting functions

N_{3}(x) = ∑_{{3≤t≤x \atop t odd}} R_{3}^{d}(t^{2}), N_{2}(x; 2) = ∑_{{3≤t≤x \atop t odd}} R_{2}^{d}(t^{2}; 2), N_{2}(x) = ∑_{{3≤t≤x \atop t odd}} R_{2}^{d}(t^{2}).  (9)

In the following, we determine the asymptotic behaviour of these counting functions. To obtain the one for Φ_{o}(x, χ) it suffices by Lemma 5 to find the one for

Φ̃(x, χ) = ∑_{1≤n≤x} φ(n, χ) = 1 + Φ(x, χ).

Now the twisted Euler function φ(n, χ) is related to the Dirichlet L-function, introduced by Dirichlet [4], via its Euler product through the identity

L(s, χ) = ∑_{n=1}^{∞} \frac{χ(n)}{n^{s}} = ∏_{p} (1 − χ(p)/p)^{−1} , Re(s) > 1,

and the following result about sums of twisted Euler functions.

Theorem 6. For all x ≥ 1 one has the asymptotic relationship

Φ̃(x, χ) = ∑_{1≤n≤x} φ(n, χ) = \frac{1}{2}L(2, χ)^{−1} · x^{2} + O(x ln(2x)).

Proof. Consult Kaczorowski and Wiertelak [13], and Kaczorowski [12, Thm. 1.1].

Applied to our situation, one obtains for the Dirichlet character (4) the asymptotic formula Φ(x, χ) ∼ Φ̃(x, χ) ∼ (2G)^{−1} · x^{2} (x ⟶ ∞), with Catalan’s constant

G = L(2, χ) = ∑_{n=0}^{∞} \frac{(−1)^{n}}{(2n + 1)^{2}} ≐ 0.915965594177.

Making use of Lemma 5, one sees that Φ_{0}(x, χ) = Φ(x, χ) − 2 · (1 + Φ(2^{−1} · x, χ)), which implies the required asymptotic relationship

Φ_{0}(x, χ) ∼ (4G)^{−1} · x^{2} (x ⟶ ∞).

Catalan’s constant is described by the sequence \underline{A006752} in Sloane [26]. It has originally been computed to 14 decimals by Catalan [1] and to 24 decimals by Bresse in 1867 making use of a technique from Kummer. It has been computed to 20 and 32 decimals by Glaisher [7, 8] and to 3.1026 · 10^{10} decimal digits by Yee and Chan in 2009. Lima [19] and Yee [27] provide more details.

It remains to determine the asymptotic behaviour of the counting functions N_{2}(x; 2), N_{2}(x) defined in (9). This was achieved a long time ago. Lehmer [18, p. 329] obtains the asymptotic formulas

N_{2}(x; 2) ∼ \frac{\sqrt{2} · x}{2π}, N_{2}(x) ∼ \frac{x}{2π} .

Inserting the above into the equation (8) one obtains the following result.

Theorem 7. The cumulative number of primitive cuboids satisfies the asymptotic formula

N_{3}(x) = \frac{1}{8} · Φ_{o}(x, χ) + \frac{1}{2} · (N_{2}(x; 2) − N_{2}(x)) ∼ \frac{x^{2}}{32G} + \frac{(\sqrt{2} − 1) · x}{4π} (x ⟶ ∞).  (10)

limit x exact asymptotic difference error (in %)
100  347 344  −3  0.86
200  1364 1371  7  0.51
300  3079 3080  1  0.03
400  5484 5472  −12  0.22
500  8541 8546  5  0.06
600  12299 12302  3  0.02
700  16750 16740  −10  0.06
800  21837 21861  24  0.11
900  27664 27664  0  0.00
1000 34163 34150  −13  0.04

Table 1: Exact and asymptotic counts

It is remarkable that exact and asymptotic counts do not differ very much (at least for lower values of x). We conclude with some related comments. Our main results, namely Lemma 4, (8), and Theorem 7 extend to primitive Pythagorean quadruples the long known similar results for primitive Pythagorean triples. For example, the number of primitive Pythagorean triples with hypotenuse less than or equal to x is approximately equal to x/2π [18, p. 28]. The exact count is described by Sloane’s OEIS sequence \underline{A020882}. Roque [21, 22] provides algorithms to generate and count them exhaustively.

References

[1] E. Catalan, Mémoire sur la transformation des séries, et sur quelques intégrales définies, Mémoires Couronnés et Mémoires des Savants Étrangers 33 (1867), 1–50.

[2] S. Cooper and M. D. Hirschhorn, On the number of primitive representations of integers as sum of squares, Ramanujan J. 13 (2007), 13–25.

[3] L. E. Dickson, History of the Theory of Numbers, Vol. II, Carnegie Institute of Washington, 1920. Reprint: Chelsea, 1966.

[4] P. G. L. Dirichlet, Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Faktor sind, unendlich viele Primzahlen enthält, Abhand. Kgl. Preuss. Akad. Wiss. (1837), 45–81.

[5] A. M. Fraedrich, Zur Existenz von pythagoreischen Quadern mit vorgegebener Raumdiagonale, Elem. Math. 37 (1982), 54–56.

[6] C. F. Gauss, Disquitiones Arithmeticae, 1801. German translation: Untersuchungen über Höhere Arithmetik, Springer, 1889. Reprint: Chelsea, 1965. English translation: Yale, 1966; Springer, 1986.

[7] J. W. L. Glaisher, On a numerical continued product, Messenger Math. 6 (1877), 71–76.

[8] J. W. L. Glaisher, Numerical values of the series 1 − 1/3^{n} + 1/5^{n} − 1/7^{n} + 1/9^{n} − & c for n = 2, 4, 6 Messenger Math. 42 (1913), 35–58.

[9] B. Gordon and O. Fraser, On representing a square as the sum of three squares, Amer. Math. Monthly 76 (1969), 922–923.

[10] E. Grosswald, Representations of Integers as Sums of Squares, Springer, 1985.

[11] A. Hurwitz, Somme de trois carrés, L’Intermédiaire des Mathématiciens, 14 (1907), 106–107. Reprinted in Mathematische Werke, Vol. 2, 1933, p. 751.

[12] J. Kaczorowski, On a generalization of the Euler totient function, Monatsh. Math. 170 (2013), 27–48.

[13] J. Kaczorowski and K. Wiertelak, On the sum of the twisted Euler function, Internat. J. Number Theory 8 (2013), 1741–1761.

[14] J. Kaczorowski and K. Wiertelak, Omega theorems related to the general Euler totient function, J. Math. Anal. Appl. 412 (2014), 401–415.

[15] J. Lagrange, Décomposition d’un entier en somme de carrés et fonction multiplicative, Séminaire Delange-Pisot-Poitou, Théorie des nombres 14 (1972–73), 1–5.

[16] J. L. Lagrange, Démonstration d’un théorème d’arithmétique, Nouveaux Mémoires de l’Acad. Royale des Sciences et Belles Lettres de Berlin (1770). Reprinted in Oeuvres, Vol. 3, 695–795.

[17] V. A. Lebesgue, Sur une identité qui conduit à toutes les solutions de l’équation t^{2} = x^{2} + y^{2} + z^{2}, Compte Rendus de l’Académie des Sciences de Paris 66 (1868), 396–398.

[18] D. N. Lehmer, Asymptotic evaluation of certain totient sums, Amer. J. Math. 22 (1900), 293–335.

[19] F. M. S. Lima, A rapidly converging Ramanujan-type series for Catalan’s constant,

preprint, 2012. Available at http://arxiv.org/abs/1207.3139.

[20] T. Nagell, Introduction to Number Theory, Wiley, 1951.

[21] E. C. Roque, On general formulas for generating sequences of Pythagorean triples ordered by c − b, preprint, 2013. Available at http://vixra.org/pdf/1211.0122v2.pdf.

[22] E. C. Roque, Enumeration of all primitive Pythagorean triples with hypotenuse less than or equal to N, preprint, 2013. Available at http://vixra.org/pdf/1211.0122v2.pdf.

[23] D. Shanks, Review of Alan Forbes and Mohan Lal tables, Math. Comp. 25 (1971), 630.

[24] D. Shanks, Solved and Unsolved Problems in Number Theory, Chelsea, 4th edition, 1993.

[25] W. Sierpiński, Pythagorean Triangles, Scripta Mathematica Studies 9, Yeshiva University, 1962.

[26] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

[27] A. J. Yee, y-cruncher - a multi-threaded Pi-program 2014,

    http://www.numberworld.org/y-cruncher/.

2010 Mathematics Subject Classification: Primary 11D45; Secondary 11N37, 11A25, 11B34. Keywords: arithmetic function, twisted Euler function, Dirichlet L-function, Dirichlet beta function, Catalan’s constant, Lehmer’s totient sum, Pythagorean quadruple.

(Concerned with sequences \underline{A006752} and \underline{A020882}.)

Received August 1 2014; revised versions received August 6 2014; January 12 2015; January 14 2015. Published in Journal of Integer Sequences, January 25 2015.

Return to Journal of Integer Sequences home page.