Enumeration of Integral Tetrahedra

Sascha Kurz Department of Mathematics Universität Bayreuth D-95440 Bayreuth Germany

                  sascha.kurz@uni-bayreuth.de

Abstract

We determine the number of integral tetrahedra with diameter d, up to isomorphism, for all d ≤ 1000, via computer enumeration. We give an algorithm that enumerates the integral tetrahedra with diameter at most d in O(d^{5}) time and an algorithm that can check the canonicity of a given integral tetrahedron with at most 6 integer comparisons. For the number of isomorphism classes of integral 4 × 4 matrices with diameter d fulfilling the triangle inequalities we derive an exact formula.

1 Introduction

Geometrical objects with integral side lengths have fascinated mathematicians for ages. A very simple geometric object is the m-dimensional simplex. Recently an intriguing bijection between m-dimensional simplices with edge lengths in {1, 2} and the partitions of m + 1 was discovered [2]. So far, for m-dimensional simplices with edge lengths in {1, 2, 3} no formula is known and exact numbers are obtained only up to m = 13 [9]. Let us more generally denote by α(m, d) the number of non-isomorphic m-dimensional simplices with edge lengths in {1, …, d} where at least one edge has length d. We also call d the diameter of the simplex. The known results, see i.e., [9], are, besides some exact numbers,

α(1, d) = 1,
α(2, d) = ⌊\frac{d + 1}{2}⌋ ⌊\frac{d + 2}{2}⌋ = ⌊\frac{(d + 1)^{2}}{4} ⌋ ,  [\underline{A002620}]
α(m, 1) = 1,
α(m, 2) = p(m + 1) − 1,  [\underline{A000065}]

where p(m + 1) denotes the number of partitions [\underline{A000041}] of m + 1. The aim of this article is the determination of the number of non-isomorphic integral tetrahedra α(3, d).

Besides an intrinsic interest in integral simplices, their study is useful in field of integral point sets. These are sets of n points in the m-dimensional Euclidean space 𝔼^{m} with pairwise integral distances. Applications for this combinatorial structure involving geometry and number theory are imaginable in radio astronomy (wave lengths), chemistry (molecules), physics (energy quantums), robotics, architecture, and other fields, see [3] for an overview. We define the largest occurring distance of an integral point set P as its diameter. From the combinatorial point of view there is a natural interest in the determination of the minimum possible diameter d(m, n) for given parameters m and n [3, 4, 5, 7, 9, 10, 11, 12, 14, 16]. In most cases exact values of d(m, n) are obtained by an exhaustive enumeration of integral point sets with diameter d ≤ d(m, n). A necessary first step for the enumeration of mdimensional integral point sets is the enumeration of m-dimensional integral simplices. Hence there is a need for an efficient enumeration algorithm.

Another application of integral tetrahedra concerns geometric probabilities. Suppose you are given a symmetric 3 × 3 matrix Δ_{2} with entries being equi-distributed in [0, 1] and zeros on the main diagonal. The probability P_{2} that Δ_{2} is the distance matrix of a triangle in the Euclidean metric can be easily determined to be P_{2} = \frac{1}{2}. As a generalization we ask for the probability P_{m} of a similar defined (m + 1) × (m + 1) matrix Δ_{m} being the distance matrix of an m-dimensional simplex in the Euclidean metric. To analyze the question for m = 3 we consider a discretization and obtain P_{3} = lim_{d→∞} \frac{4·α(3,d)}{d^{5}}. Our main results are the determination of α(3, d) for d ≤ 1000,

Theorem 1. The number α̂_{≤}(d, 3) of symmetric 4 × 4 matrices with entries in {1, …, d} fulfilling the triangle inequalities is given by

α̂_{≤}(d, 3) = \{ \begin{matrix}\frac{17d^{6}+425d^{4}+1628d^{2}}{2880} , & if d ≡ 0(mod 2); \\ \frac{17d^{6}+425d^{4}+1763d^{2}+675}{2880}, & if d ≡ 1(mod 2). \end{matrix}

If we additionally request a diameter of exactly d we have

α̂(d, 3) = \{ \begin{matrix}\frac{34d^{5}−85d^{4}+680d^{3}−962d^{2}+1776d−960}{960} & if d ≡ 0(mod 2); \\ \frac{34d^{5}−85d^{4}+680d^{3}−908d^{2}+1722d−483}{960} & if d ≡ 1(mod 2). \end{matrix}

Theorem 2.

0.090 ≤ P_{3} ≤ 0.111,

and the enumeration algorithms of Section 4 and Section 5, which allows us to enumerate integral tetrahedra with diameter at most d in time O(d^{5}) and to check a 4 × 4-matrix for canonicity using at most 6 integer comparisons.

2 Number of integral tetrahedra

Because a symmetric 4 × 4-matrix with zeros on the diagonal has six independent non-zero values there are d^{6} labeled integral such matrices with diameter at most d. To obtain the number \overline{α}_{≤}(d, 3) of unlabeled matrices we need to apply the following well known Lemma:

Lemma 3. (Cauchy-Frobenius, weighted form) Given a group action of a finite group G on a set S and a map w : S ⟶ R from S into a commutative ring R containing ℚ as a subring. If w is constant on the orbits of G on S, then we have, for any transversal T of the orbits:

∑_{t∈T} w(t) = \frac{1}{|G|} ∑_{g∈G} ∑_{s∈S_{g}} w(s)

where S_{g} denotes the elements of S being fixed by g, i.e.

S_{g} = {s ∈ S|s = gs} .

For a proof, notation and some background we refer to [6]. Applying the lemma yields:

Lemma 4.

\overline{α}_{≤}(d, 3) = \frac{d^{6} + 9d^{4} + 14d^{2}}{24}

and

\overline{α}(d, 3) = \overline{α}_{≤}(d, 3) − \overline{α}_{≤}(d − 1, 3) = \frac{6d^{5} − 15d^{4} + 56d^{3} − 69d^{2} + 70d − 24}{24}.

As geometry is involved in our problem we have to take into account some properties of Euclidean spaces. In the Euclidean plane 𝔼^{2} the possible occurring triples of distances of triangles are completely characterized by the triangle inequalities. In general there is a set of inequalities using the so called Cayley-Menger determinant to characterize whether a given symmetric (m + 1) × (m + 1) matrix with zeros on the diagonal is a distance matrix of an m-dimensional simplex [13]. For a tetrahedron with distances δ_{i,j}, 0 ≤ i ≤ j < 4, the inequality

CMD_{3} = | \begin{matrix}0 & δ_{0,1}^{2} & δ_{0,2}^{2} & δ_{0,3}^{2} & 1 \\ δ_{1,0}^{2} & 0 & δ_{1,2}^{2} & δ_{1,3}^{2} & 1 \\ δ_{2,0}^{2} & δ_{2,1}^{2} & 0 & δ_{2,3}^{2} & 1 \\ δ_{3,0}^{2} & δ_{3,1}^{2} & δ_{3,2}^{2} & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{matrix} | > 0  (1)

has to be fulfilled besides the triangle inequalities.

In the first step we exclusively consider the triangle inequalities for m = 3 and count the number α̂_{≤}(d, 3) of non-isomorphic symmetric 4 × 4 matrices with entries in {1, …, d} fulfilling the triangle inequalities.

Proof of Theorem 1. Counting labeled symmetric 4 × 4 matrices with entries in {1, …, d} fulfilling the triangle inequalities is equivalent to determining integral points in a six-dimensional polyhedron. Prescribing the complete automorphism group results in some further equalities and an application of the inclusion-exclusion principle. Thus, after a lengthy but rather easy computation we can apply Lemma 3 and obtain

24α̂_{≤}(d, 3) = 3 · ⌈\frac{4d^{4} + 5d^{2}}{12} ⌉ + 6 · \frac{37d^{4} − 18d^{3} + 20d^{2} − 21d + (36d^{2} + 42) ⌈\frac{d}{2}⌉}{96}

+ ⌈\frac{34d^{6} + 55d^{4} + 136d^{2}}{240} ⌉ + 6 · (d^{2} − d ⌈\frac{d}{2}⌉ + ⌈\frac{d}{2}⌉^{2}) + 8 · (d^{2} − d ⌈\frac{d}{2}⌉ + ⌈\frac{d}{2}⌉^{2}) ,

which can be modified to the stated formulas. □

\begin{matrix}d & α(d, 3) & d & α(d, 3) & d & α(d, 3) & d & α(d, 3) & d & α(d, 3) \\ 1 & 1 & 26 & 305861 & 51 & 8854161 & 76 & 65098817 & 120 & 639349793 \\ 2 & 4 & 27 & 369247 & 52 & 9756921 & 77 & 69497725 & 140 & 1382200653 \\ 3 & 16 & 28 & 442695 & 53 & 10732329 & 78 & 74130849 & 160 & 2695280888 \\ 4 & 45 & 29 & 527417 & 54 & 11783530 & 79 & 79008179 & 180 & 4857645442 \\ 5 & 116 & 30 & 624483 & 55 & 12916059 & 80 & 84138170 & 200 & 8227353208 \\ 6 & 254 & 31 & 735777 & 56 & 14133630 & 81 & 89532591 & 220 & 13251404399 \\ 7 & 516 & 32 & 861885 & 57 & 15442004 & 82 & 95198909 & 240 & 20475584436 \\ 8 & 956 & 33 & 1005214 & 58 & 16845331 & 83 & 101149823 & 260 & 30554402290 \\ 9 & 1669 & 34 & 1166797 & 59 & 18349153 & 84 & 107392867 & 280 & 44260846692 \\ 10 & 2760 & 35 & 1348609 & 60 & 19957007 & 85 & 113942655 & 300 & 62496428392 \\ 11 & 4379 & 36 & 1552398 & 61 & 21678067 & 86 & 120807154 & 320 & 86300970558 \\ 12 & 6676 & 37 & 1780198 & 62 & 23514174 & 87 & 127997826 & 340 & 116862463817 \\ 13 & 9888 & 38 & 2033970 & 63 & 25473207 & 88 & 135527578 & 360 & 155526991341 \\ 14 & 14219 & 39 & 2315942 & 64 & 27560402 & 89 & 143409248 & 380 & 203808692441 \\ 15 & 19956 & 40 & 2628138 & 65 & 29783292 & 90 & 151649489 & 400 & 263399396125 \\ 16 & 27421 & 41 & 2973433 & 66 & 32145746 & 91 & 160268457 & 420 & 336178761892 \\ 17 & 37062 & 42 & 3353922 & 67 & 34657375 & 92 & 169272471 & 440 & 424224122232 \\ 18 & 49143 & 43 & 3773027 & 68 & 37322859 & 93 & 178678811 & 460 & 529820175414 \\ 19 & 64272 & 44 & 4232254 & 69 & 40149983 & 94 & 188496776 & 480 & 655468974700 \\ 20 & 82888 & 45 & 4735254 & 70 & 43145566 & 95 & 198743717 & 500 & 803900006590 \\ 21 & 105629 & 46 & 5285404 & 71 & 46318399 & 96 & 209427375 & 520 & 978079728301 \\ 22 & 133132 & 47 & 5885587 & 72 & 49673679 & 97 & 220570260 & 540 & 1181221582297 \\ 23 & 166090 & 48 & 6538543 & 73 & 53222896 & 98 & 232180129 & 560 & 1416796092768 \\ 24 & 205223 & 49 & 7249029 & 74 & 56969822 & 99 & 244275592 & 580 & 1688540496999 \\ 25 & 251624 & 50 & 8019420 & 75 & 60926247 & 100 & 256866619 & 600 & 2000468396580 \end{matrix}

Table 1: Number α(d, 3) of integral tetrahedra with diameter d - part 1. In addition to this proof we have verified the stated formula for d ≤ 500 via a computer

enumeration. We remark that \frac{α̂_{≤}(d,3)}{\overline{α}_{≤}(d,3)} and \frac{α̂(d,3)}{\overline{α}(d,3)} tend to \frac{17}{120} = 0.141\overline{6} if d → ∞. Moreover we were able to obtain an exact formula for α̂(d, 3) because the Cayley-Menger determinant

CMD_{2} = | \begin{matrix}0 & δ_{0,1}^{2} & δ_{0,2}^{2} & 1 \\ δ_{1,0}^{2} & 0 & δ_{1,2}^{2} & 1 \\ δ_{2,0}^{2} & δ_{2,1}^{2} & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix} |

for dimension m = 2 can be written as CMD_{2} = −(δ_{0,1} + δ_{0,2} + δ_{1,2})(δ_{0,1} + δ_{0,2} − δ_{1,2})(δ_{0,1} − δ_{0,2} + δ_{1,2})(−δ_{0,1} + δ_{0,2} + δ_{1,2}).

Thus CMD_{2} < 0 is equivalent to the well known linear triangle inequalities δ_{0,1} + δ_{0,2} > δ_{1,2}, δ_{0,1}+δ_{1,2} > δ_{0,2} and δ_{0,2}+δ_{1,2} > δ_{0,1}. Unfortunately for m ≥ 3 the Cayley-Menger determinant is irreducible [1] and one cannot simplify (−1)^{m+1}CMD_{m} > 0 into a set of inequalities of lower degree. So we are unable to apply the same method to derive an analytic formula for α(d, 3).

d  α(d, 3) d  α(d, 3)  d  α(d, 3)
620 2356880503873 760 6523288334629 900 15192308794063
640 2762373382787 780 7428031732465 920 16957109053082
660 3221850132593 800 8430487428682 940 18882231158104
680 3740530243895 820 9538364312059 960 20978358597822
700 4323958989350 840 10759766492473 980 23256639532080
720 4978017317882 860 12103204603044 1000 25728695195597
740 5708932993276 880 13577602128303

Table 2: Number α(d, 3) of integral tetrahedra with diameter d - part 2.

Lemma 5. We have α(3, d) ∈ Ω(d^{5}), α(3, d) ∈ O(d^{5}), α_{≤}(3, d) ∈ Ω(d^{6}), and α_{≤}(3, d) ∈ O(d^{6}).

Proof. The upper bounds are trivial since they also hold for symmetric matrices with integer values at most d and zeros on the diagonal. For the lower bounds we consider six-tuples δ_{0,1} ∈ [d, d(1−ε)), δ_{0,2} ∈ [d(1−ε), d(1−2ε)), δ_{1,2} ∈ [d(1−2ε), d(1−3ε)), δ_{0,3} ∈ [d(1−3ε), d(1−4ε)), δ_{1,3} ∈ [d(1 − 4ε), d(1 − 5ε)), and δ_{2,3} ∈ [d(1 − 5ε), d(1 − 6ε)). For each ε there are Ω(d^{6}) non-isomorphic matrices. If ε is suitable small then all these matrices fulfill the triangle conditions and inequality 1.

In general we have α_{≤}(m, d) ∈ Ω(d^{m(m+1)/2}), α_{≤}(m, d) ∈ O(d^{m(m+1)/2}), α(m, d) ∈ Ω(d^{m(m+1)/2−1}), and α(m, d) ∈ O(d^{m(m+1)/2−1}).

In Section 4 and Section 5 we give an algorithm to obtain α(d, 3) via implicit computer enumeration. Some of these computed values are given in Table 1 and Table 2. For a complete list of α(d, 3) for d ≤ 1000 we refer to [8]. This amounts to

α_{≤}(1000, 3) = 4299974867606266 ≈ 4.3 · 10^{15}.

3 Bounds for P_{3}

In this section we give bounds for the probability P_{3} that Δ_{3} is the distance matrix of a tetrahedron in the 3-dimensional Euclidean space 𝔼^{3}, where Δ_{3} is a symmetric 4 × 4 matrix with zeros on the main diagonal and the remaining entries being equi-distributed in [0, 1]. Therefore we consider a discretization. Let d be a fixed number. We consider the d^{6} sixdimensional cubes C_{i_{1},...,i_{6}} := ×_{j=1}^{6} [\frac{i_{j}}{d} , \frac{i_{j}+1}{d}] ⊆ [0, 1]^{6}. For every cube C it is easy to decide whether every point of C fulfills the triangle conditions, no points of C fulfill the triangle conditions, or both cases occur. For inequality 1 we have no explicit test but we are able to compute a lower bound \underline{CMD_{3}}(C) and an upper bound \overline{CMD_{3}}(C), so that we have

\underline{CMD_{3}}(C) ≤ CMD_{3}(x) ≤ \overline{CMD_{3}}(C) for all x ∈ C.

Thus for some cubes C we can decide that all x ∈ C correspond to a tetrahedron. We denote this case by Ξ(C) = 1. If no x ∈ C corresponds to a tetrahedron we set Ξ(C) = −1. In all other cases we define Ξ(C) = 0. With this we obtain for all d ∈ ℕ the following bounds:

Lemma 6.

∑_{C: Ξ(C)=1} \frac{1}{d^{6}} ≤ P_{3} ≤ 1 − ∑_{C: Ξ(C)=−1} \frac{1}{d^{6}} .

Thus we have a method to obtain bounds on P_{3} using computer calculations. For the actual computation we use two further speed ups. We can take advantage of symmetries and use an adaptive strategy: We start with a small value of d and subdivide cubes C with Ξ(C) = 0 recursively into 8 smaller cubes. After a computer calculation we obtain

0.090 ≤ P_{3} ≤ 0.111,

which proves Theorem 2. Clearly Theorem 2 can be improved by simply letting the computers work for a longer time or by using a computing cluster, but the convergence of our approach seems to be rather slow. An enhanced check whether a cube C fulfills inequality (1) would be very useful.

Good estimates for P_{3} can be obtained by considering the values α(3, d) in the following way. At first we consider the probability P̃_{3} being defined as P_{3} where additionally δ_{0,1} = 1.

Lemma 7.

P̃_{3} = P_{3}.

Proof. The problem of determining P_{3} or P̃_{3} is an integration problem. Due to symmetry we only need to consider the domain where δ_{0,1} is the maximum. For every δ_{0,1} ∈ (0, 1] there is a probability p(δ_{0,1}) that δ_{0,1}, …, δ_{2,3} are distances of a tetrahedron where δ_{0,2}, …, δ_{2,3} ∈ (0, δ_{0,1}] are equi-distributed random variables. Since p(δ_{0,1}) is constant we can conclude the stated equation.

Lemma 8.

P_{3} = lim_{d→∞} \frac{4 · α(d, 3)}{d^{5}}.

Proof. We consider a modified version of the algorithm described above to obtain exact bounds on P̃_{3}. As already mentioned, the triangle inequalities alone define a five-dimensional polyhedron. Since determinants are continuous CMD_{3} = 0 defines a smooth surface and so the volume of all cubes C with Ξ(C) = 0 converges to zero. Thus substituting Ξ(C) by the evaluation of Ξ in an arbitrary corner of C yields the correct value for P̃_{3} = P_{3} for d → ∞. Since there are at most O(d^{4}) six-tuples (d, i_{2}, …, i_{6}), i_{j} ∈ {1, …, d} with nontrivial automorphism group we can factor out symmetry and conclude the stated result.

Using Lemma 4 and Theorem 1 we can modify this to

P_{3} = lim_{d→∞} \frac{α(d, 3)}{\overline{α}(d, 3)} ≤ lim_{d→∞} \frac{α̂(d, 3)}{\overline{α}(d, 3)} = \frac{17}{120} = 0.141\overline{6}.

Heuristically we observe that the finite sequence (\frac{α(d,3)}{\overline{α}(d,3)})_{1≤d≤1000} is strictly decreasing. So

the following values might be seen as a good estimate for P_{3}:

\frac{α(600, 3)}{\overline{α}(600, 3)} = \frac{2000468396580}{19359502966749} ≈ 0.103333,

\frac{α(800, 3)}{\overline{α}(800, 3)} = \frac{8430487428682}{81665192828999} ≈ 0.103232, and

\frac{α(1000, 3)}{\overline{α}(1000, 3)} = \frac{25728695195597}{249377330461249} ≈ 0.103172.

4 Orderly generation of integral tetrahedra

Our strategy to enumerate integral tetrahedra is to merge two triangles along a common side. In Figure 1 we have depicted the two possibilities in the plane to join two triangles (0, 1, 2) and (0, 1, 3) along the side \overline{01}. If we rotate the triangle (0, 1, 3) in the 3-dimensional space from the position on the left in Figure 1 to the position on the right we obtain tetrahedra and the distance δ_{2,3} forms an interval [l, u]. The restriction to integral tetrahedra is fairly easy.

[figure: 0; 1; 3; 2; 0; 1; 3; 2]

Figure 1: Joining two triangles.

Let us consider the example δ_{0,1} = 6, δ_{0,2} = δ_{1,2} = 5, δ_{0,3} = 4, and δ_{1,3} = 3. Solving CMD_{3} = 0 over the positive real numbers yields that the configuration is a tetrahedron

iff δ_{2,3} ∈ (^{\frac{\sqrt{702−24\sqrt{455}}}{6}}, ^{\frac{\sqrt{702+24\sqrt{455}}}{6}}) ≈ (2.297719304, 5.806934304). Thus there are integral

tetrahedra for δ_{2,3} ∈ {3, 4, 5}. In general we denote such a set of tetrahedra by

δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3} ∈ [l, r].

This notation permits to implicitly list Ω(d^{6}) integral tetrahedra in O(d^{5}) time.

All integral tetrahedra can be obtained in this manner. So an enumeration method is to loop over all suitable pairs of integral triangles and to combine them. We will go into detail in a while. Before that we have to face the fact that our enumeration method may construct pairs of isomorphic tetrahedra. Looking at Table 1 we see that storing all along the way constructed non-isomorphic integral tetrahedra in a hash table is infeasible. Here we use the concept of orderly generation [15] which allows us to decide independently for each single constructed discrete structure if we have to take or to reject it. Therefore we have to define a canonical form of an integral tetrahedron. Here we say that a tetrahedron T with side lengths δ_{i,j} is canonical if for the lexicographic ordering of vectors ⪰,

(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3}) ⪰ (δ_{τ(0),τ(1)}, …, δ_{τ(2),τ(3)})

holds for all permutation τ of the points 0, 1, 2, 3. We describe the algorithmic treatment of a canonicity function χ(T ) ↦ {true, false} which decides whether a given integral tetrahedron T is canonical in Section 5. We have the following obvious lemma:

Lemma 9. If χ(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3}) = true and χ(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3} + 1) = false then χ(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3} + n) = false for all n ≥ 1.

Thus for given δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, and δ_{1,3} the possible values for δ_{2,3} which correspond to a canonical tetrahedron form an interval [l̂, û]. Clearly, the value of χ(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3}) has to be evaluated for δ_{2,3} ∈ {δ_{i,j} − 1, δ_{i,j}, δ_{i,j} + 1 | (i, j) ∈ {(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)}} only. Thus we can determine the interval [l̂, û] using O(1) evaluations of χ(T ).

Algorithm 1. Orderly generation of integral tetrahedra Input: Diameter d Output: A complete list of canonical integral tetrahedra with diameter d begin δ_{0,1} = d for δ_{0,2} from ⌊\frac{d+2}{2}⌋ to d do for δ_{1,2} from d + 1 − δ_{0,2} to δ_{0,2} do for δ_{0,3} from d + 1 − δ_{0,2} to δ_{0,2} do for δ_{1,3} from d + 1 − δ_{0,3} to δ_{0,2} do Determine the interval [l̂, û] for δ_{2,3} print δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, [l̂, û] end end end end end

We leave it as an exercise for the reader to prove the correctness of Algorithm 1 (see [15] for the necessary and sufficient conditions of an orderly generation algorithm). Since we will see in the next section that we can perform χ(T ) in O(1) the runtime of Algorithm 1 is O(d^{4}). By an obvious modification Algorithm 1 returns a complete list of all canonical integral tetrahedra with diameter at most d in O(d^{5}) time.

We remark that we have implemented Algorithm 1 using Algorithm 2 for the canonicity check. For the computation of α(800, 3) our computer needs only 3.3 hours which is really fast compared to the nearly 3 hours needed for a simple loop from 1 to α(800, 3) on the same machine. Due to the complexity of O(d^{4}) for suitable large d the determination of α(d, 3) will need less time than the simple loop from 1 to α(d, 3).

5 Canonicity check

In the previous section we have used the canonicity check χ(T ) as a black box. The straight forward approach to implement it as an algorithm is to run over all permutations τ ∈ S_{4} and to check whether (δ_{0,1}, …, δ_{2,3}) ⪰ (δ_{τ(0),τ(1)}, …, δ_{τ(2),τ(3)}). This clearly leads to running time O(1) but is too slow for our purpose. It may be implemented using 24 · 6 = 144 integer comparisons. Here we can use the fact that the tetrahedra are generated by Algorithm 1. So if we arrange the comparisons as in Algorithm 2 at most 6 integer comparisons suffice.

Algorithm 2. Canonicity check for integral tetrahedra generated by Algorithm 1 Input: δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3} Output: χ(δ_{0,1}, δ_{0,2}, δ_{1,2}, δ_{0,3}, δ_{1,3}, δ_{2,3}) begin if δ_{0,1} = δ_{0,2} then if δ_{0,2} = δ_{1,2} then if δ_{0,3} < δ_{1,3} then return false else if δ_{1,3} < δ_{2,3} then return false else return true end else if δ_{1,3} < δ_{2,3} then return false else if δ_{0,1} = δ_{0,3} then if δ_{1,2} < δ_{1,3} then return false else return true end else if δ_{0,1} > δ_{1,3} then return true else if δ_{1,2} < δ_{0,3} then return false else return true end end end end end else if δ_{0,2} = δ_{1,2} then if δ_{0,1} < δ_{2,3} or δ_{0,3} < δ_{1,3} then return false else return true end else if δ_{0,2} = δ_{1,3} then if δ_{0,3} > δ_{1,2} or δ_{0,1} < δ_{2,3} then return false else return true end else if δ_{0,2} = δ_{0,3} then if δ_{1,2} < δ_{1,3} or δ_{0,1} ≤ δ_{2,3} then return false else return true end else if δ_{0,3} > δ_{1,2} then if δ_{0,1} ≤ δ_{2,3} then return true else return false end else if δ_{0,1} < δ_{2,3} then return true else return false end end end end end end end

To prove the correctness of Algorithm 2 we consider all vectors (δ_{0,1}, …, δ_{2,3}) with δ_{i,j} ∈ {0, …, 5}, δ_{0,1} ≥ δ_{0,2} ≥ δ_{1,2}, δ_{0,2} ≥ δ_{0,3}, and δ_{0,2} ≥ δ_{1,3}. It suffices to show that Algorithm 2 returns the correct value for this finite set of vectors since these inequalities are fulfilled by Algorithm 1 and also necessary for χ(T ) = true. Algorithm 2 can be considered as a binary decision tree. It might be a task to optimize this type of binary decision tree in the worst or in the average case.

6 Dimensions m ≥ 4

Clearly the question for bounds for P_{m} arises also for m ≥ 4. But non-trivial answers seem out of reach by our approach. So far we have no efficient equivalent of Algorithm 2 at hand and the number α(4, d) of integral 4-dimensional simplices with diameter d is Ω (d^{9}). We give the known values of α(4, d) in Table 6.

\begin{matrix}d & α(d, 4) & d & α(d, 4) & d & α(d, 4) & d & α(d, 4) \\ 1 & 1 & 14 & 12957976 & 27 & 4716186332 & 40 & 162007000505 \\ 2 & 6 & 15 & 24015317 & 28 & 6541418450 & 41 & 202323976907 \\ 3 & 56 & 16 & 42810244 & 29 & 8970194384 & 42 & 251321436143 \\ 4 & 336 & 17 & 73793984 & 30 & 12168243592 & 43 & 310607982160 \\ 5 & 1840 & 18 & 123240964 & 31 & 16344856064 & 44 & 382002253424 \\ 6 & 7925 & 19 & 200260099 & 32 & 21748894367 & 45 & 467627887530 \\ 7 & 29183 & 20 & 317487746 & 33 & 28688094208 & 46 & 569910996879 \\ 8 & 91621 & 21 & 492199068 & 34 & 37529184064 & 47 & 691631229557 \\ 9 & 256546 & 22 & 747720800 & 35 & 48713293955 & 48 & 835911697430 \\ 10 & 648697 & 23 & 1115115145 & 36 & 62769489452 & 49 & 1006370948735 \\ 11 & 1508107 & 24 & 1634875673 & 37 & 80321260053 & 50 & 1207047969441 \\ 12 & 3267671 & 25 & 2360312092 & 38 & 102108730634 & 51 & 1442539675756 \\ 13 & 6679409 & 26 & 3358519981 & 39 & 128999562925 & 52 & 1718015775541 \end{matrix}

Table 3: Number α(d, 4) of integral 4-dimensional simplices with diameter 1 ≤ d ≤ 52.

References

[1] C. d’Andrea and M. Sombra, The Cayley-Menger determinant is irreducible for n ≥ 3, Siberian Math. J. 46 (2005), 90–97.

[2] C. Haase and S. Kurz, A bijection between the d-dimensional simplices with distances in {1, 2} and the partitions of d+1, J. Combin. Theory Ser. A 113 (2006), 736–738.

[3] H. Harborth Integral distances in point sets, in P. L. Butzer et al., eds., Karl der Grosse und sein Nachwirken. 1200 Jahre Kultur und Wissenschaft in Europa, Band 2: Mathematisches Wissen, Brepols, Turnhout, 1998, pp. 213–224.

[4] H. Harborth, A. Kemnitz, and M. Möller, An upper bound for the minimum diameter of integral point sets, Discrete Comput. Geom. 9 (1993), 427–432.

[5] A. Kemnitz. Punktmengen mit ganzzahligen Abständen. Habilitationsschrift, TU Braunschweig, 1988.

[6] A. Kerber, Applied finite group actions. 2nd, rev. and exp. ed., 1999.

[7] A. Kohnert and S. Kurz, A note on Erdös-Diophantine graphs and Diophantine carpets, Math. Balkanica 21 (2007).

[8] S. Kurz, Number of integral tetrahedrons with given diameter,

http://www.wm.uni-bayreuth.de/index.php?id=252.

[9] S. Kurz, Konstruktion und Eigenschaften ganzzahliger Punktmengen, PhD thesis, Bayreuth. Math. Schr. 76, Universität Bayreuth, 2006.

[10] S. Kurz, On the characteristic of integral point sets in 𝔼^{m}, Australas. J. Combin. 36 (2006), 241–248.

[11] S. Kurz and R. Laue, Bounds for the minimum diameter of integral point sets, Australas. J. Combin. (to appear).

[12] S. Kurz and A. Wassermann, On the minimum diameter of plane integral point sets, preprint.

[13] K. Menger, Untersuchungen über allgemeine Metrik, Math. Ann. 100 (1928), 75–163.

[14] L. Piepmeyer, Räumliche ganzzahlige Punktmengen, Master’s thesis, TU Braunschweig, 1988.

[15] R. C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math. 2 (1978), 107–120.

[16] J. Solymosi, Note on integral distances, Discrete Comput. Geom. 30 (2003), 337–342.

2000 Mathematics Subject Classification: Primary 33F05; Secondary 05A15. Keywords: implicit enumeration, integral tetrahedra, geometric probability, Euclidean metric, orderly generation, canonicity check.

(Concerned with sequences \underline{A000041}, \underline{A000065}, and \underline{A002620}.) Received June 18 2007; revised version received September 3 2007. Published in Journal of Integer Sequences, September 3 2007. Return to Journal of Integer Sequences home page.