Maximal integral point sets over Z^2
Full text
MAXIMAL INTEGRAL POINT SETS OVER Z2 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ ABSTRACT. Geometrical objects with integral side lengths have fascinated mathematicians through the ages. We call a set P={p1,...,pn}⊂Z2a maximal integral point set over Z2if all pairwise distances are integral and every additional point pn+1destroys this property. Here we consider such sets for a given cardinality and with minimum possible diameter. We determine some exact values via exhaustive search and give several constructions for arbitrary cardinalities. Since we cannot guarantee the maximality in these cases we describe an algorithm to prove or disprove the maximality of a given integral point set. We additionally consider restrictions as no three points on a line and no four points on a circle. 1. INTRODUCTION Geometrical objects with integral side lengths have fascinated mathematicians through the ages. A very early example is the Pythagorean triangle with side lengths 3,4, and 5. A universal framework for most of these objects are integral point sets. By an integral point set we understand a set of npoints in an mdimensional Euclidean vector space Em, where the pairwise distances between the points are integral. Those integral point sets were studied by many authors, see [9] for an overview. From a combinatorial point of view for a given cardinality nand a given dimension mthe question on the minimum possible diameter d(n, m), this is the largest distance between any two points, arises, see [16, 19, 20] for an overview. To obtain some interesting discrete structures one could also require some additional properties. One possibility is to request, that besides the distances also the coordinates must be integral. Another classical possibility is to forbid subsets of three points on a line or four points on a circle. The question of P. Erd˝ os whether there exists a set of seven points in the plane with no three points on a line, no four points on a circle, and pairwise integral distances, has recently been answered positively, see [14]. If all three mentioned additional properties are required simultaneously one speaks of nm-clusters, see [22]. In this article we request that besides the distances also the coordinates of the point sets are integral and restrict ourselves to dimension 2. Additionally we consider the cases where no three points are on a line or no four points are on a circle. In finite geometry one is sometimes interested in point configurations which are maximal with respect to some property. This means that it is not possible to add a point without destroying the requested property. Here we consider integral point sets which are maximal, meaning that there does not exist an additional point xwith integral distances to the other points of the point set. 1.1. Related work. There have been extensive studies on integral point sets in Euclidean spaces. Some authors also consider other spaces, e. g. Banach spaces [6], integral point sets over rings [13], or integral point sets over finite fields [2, 11, 15]. In [3] the authors consider integral point sets over Z2and conjecture some examples to be maximal. As an answer to their open problems in [12] the authors describe an algorithm to prove the maximality of a given integral point set and prove the conjectures of [3]. 2000 Mathematics Subject Classification. 52C10;52C45,05D99,11D99,52-04. Key words and phrases. integral distances, diameter, exhaustive search, maximality. 1
2 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ 1.2. Our contribution. In this paper we describe algorithms to efficiently test integral point sets for maximality and to determine possible extension points. To deal with the isomorphism problem we describe an algorithm which transforms a given plane integral point set into a normal form in On2time, where nis the cardinality of the point set. We give several constructions of integral point sets over Z2 which have a given cardinality and fulfill additional conditions such as that there are “no three points on a line” or “no four points on a circle”. Although we cannot prove the maximality of the point sets obtained with the proposed constructions in general, we conjecture this property for many of our constructions. By exhaustive search we have determined some exact minimum diameters of integral point sets over Z2 with given cardinality and with or without additional conditions. We give constructive upper bounds in most cases and conjecture them to be the exact values. 1.3. Outline of the paper. In Section 3 we state the basic definitions and in Section 2 we describe the basic algorithms to deal with maximal integral point sets over Z2. These include an algorithm to exhaustively generate Heronian triangles up to isomorphism, an algorithm to determine all possible embeddings of an Heronian triangle on the integer grid Z2, and an algorithm that determines all points of Z2which have integral distances to three given points in Z2with pairwise integral distances. The last mentioned algorithm enables us to algorithmically prove or disprove the maximality of a given integral point set. Since we intend to consider integral point sets up to isomorphism we introduce normal forms of integral point sets and algorithms to obtain them in Section 4. We deal with the key question of maximal integral point sets over Z2with given cardinality and minimum diameter in Section 5. Several constructions for maximal integral point sets, where the maximality is not guaranteed but very likely, are described in Section 6. In Section 7 we deal with additional properties as “no three points on a line” and “no four points on a circle”. We finish with a short conclusion and an outlook in Section 8. 2. BASICS Definition 2.1. An integral point set over Z2is a non-collinear set Pof npoints in the integer grid Z2, where the points have pairwise integral distances. For brevity we only speak of integral point sets and assume that the coordinates of the points are integral numbers, too. Definition 2.2. We call an integral point set Pover Z2maximal if for every x∈Z2\P the point set P∪{x}is not an integral point set. The existence of maximal integral point sets in the plane is guaranteed by a famous theorem of N.H.. Anning and P. Erd˝ os, respectively its proof. Theorem 2.3. An infinite set Pof points in the Euclidean space Emwith pairwise integral distances is situated on a line. [1, 4] PROOF. We only prove the statement for dimension m=2, as the generalization is obvious. If A,B, and Care three points not on a line, we set k=max AC, BCand consider points Psuch that |PA −PC| and |PB −PC|are integral. Due to the triangle inequalities the attained values are in {0,1,...,k}. Thus the point Plies on the intersection of two distinct hyperbolas, where we have at most k+1choices for each hyperbola. Thus there are at most 4(k+1)2possible locations for the point P. This proof can clearly be converted into a constructive algorithm. Given three points A= (xA, yA), B= (xB, yB), and C= (xC, yC)in P⊂Z2, which are not on a line, the problem of determing points P= (xP, yP)at integral distance to A,B, and Cis reduced to the problem of solving the equation system p(xA−xP)2+ (yA−yP)2−p(xC−xP)2+ (yC−yP)2=d1 p(xB−xP)2+ (yB−yP)2−p(xC−xP)2+ (yC−yP)2=d2 ,(1)
MAXIMAL INTEGRAL POINT SETS OVER Z23 where d1∈−AC, . . . , AC⊂Zand d2∈−BC, . . . , BC⊂Z. If there exists no integral solution in Z2\P, then the point set Pis maximal. This algorithm was already used in [12] to prove the maximality of the integral point sets of Figure 1. }(0, −4) } (−3, 0)} (0, 0)} (3, 0) }(0, 4) SSSSS S S S S S S S } (0, 12) } (9, 0)} (16, 0) } (9, 24)} (16, 24) } (25, 12) SSSSSSSS S S S S S S S S S S ZZZZZZZZZZZ Z Z Z Z Z Z Z Z Z Z Z Z Z FIGURE 1. Examples of maximal integral point sets. Since this algorithm is essential for our article we will go into the details how to solve equation system 1. To get rid of some of the square roots we add p(xC−xP)2+ (yC−yP)2on both sides and square the expressions afterwards: (xA−xP)2+ (yA−yP)2=d2 1+2d1p(xC−xP)2+ (yC−yP)2+ (xC−xP)2+ (yC−yP)2 (xB−xP)2+ (yB−yP)2=d2 2+2d2p(xC−xP)2+ (yC−yP)2+ (xC−xP)2+ (yC−yP)2 . Rearranging yields (x2 A+y2 A−x2 C−y2 C−d2 1) + 2(xC−xA)xP+2(yC−yA)yP=2d1p(xC−xP)2+ (yC−yP)2 (x2 B+y2 B−x2 C−y2 C−d2 2) + 2(xC−xB)xP+2(yC−yB)yP=2d2p(xC−xP)2+ (yC−yP)2 . (2) If d1=0then the first equation corresponds to a linear equation c1xP+c2yP+c3=0, (3) where not both c1and c2are equal to zero, since A6=C. If we square the second equation of (2) we can substitute one variable using equation (3) and obtain a quadratic equation in one variable, which can be easily solved. The case, where d2=0is similar. Here we use the second equation of (2) to obtain equation (3) (we have c16=0or c26=0due to B6=C), and substitute it into the squared version of the first equation to obtain the quadratic equation in one variable. In the remaining case we have d1, d26=0. Here we subtract d1times the second equation of (2) from d2times the first equation of (2) to obtain equation (3) (we have c16=0or c26=0since the points A,B, and Care not located on a line). Now we can square one of the two equations of (2) and subsitute one variables using equation (3). Again we end up with a quadratic equation in one variable. At the end we have to check if the obtained values (xP, yP) are solutions of the original equation system (1). Definition 2.4. For an integral point set Pits diameter diam(P)is given by the largest distance between a pair of its points. We remark that the left integral point set of Figure 1 has diameter 8and the right integral point set of Figure 1 has diameter 25.
4 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ 3. EXHAUSTIVE GENERATION OF MAXIMAL INTEGRAL POINT SETS To obtain interresting examples of maximal integral point sets we utilize computers to exhaustively generate maximal integral point sets. In the following we will describe the algorithm used. For a given diameter dwe loop over all non-isomorphic Heronian triangles (having integral side lengths and integral area) ∆= (a, b, c)with diameter d=max{a, b, c}. Utilizing the Heron formula A=p(a+b+c)(a+b−c)(a−b+c)(−a+b+c) 4(4) for the area of a triangle we can generate this list e.g. by the following short algorithm: Algorithm 3.1. (Generation of Heronian triangles) input: diameter d output: complete list of Heronian triangles with diameter dup to isomorphism begin a=d for b=a+2 2,...,ado for c=a+1−b,...,bdo if √(a+b+c)(a+b−c)(a−b+c)(−a+b+c) 4∈Zthen output (a, b, c) end For a more sophisticated and efficient algorithm we refer to [18]. The next step is to embed a given Heronian triangle ∆= (a, b, c)in the plane integer grid Z2. Here we can utilize two conjectures, which are theorems for dimension m=2, see e.g. [5]. Conjecture 3.2. Let P⊂Qmbe a finite set of points such that the distances between any two points of Pare integers. In this case one can find an Euclidean motion Tsuch that T(P)⊂Pm. Conjecture 3.3. Let P⊂Zmbe a finite set of points such that the distances between any two points of Pare integers and divisible by an integer k. In this case one can find a set P0⊂Zmsuch that P0·k(the set P0scaled by a factor k) is congruent to P. Since Conjecture 3.2 is a well known theorem for dimension m=2, see e.g. [5], for every Heronian triangle ∆(a, b, c)there exists an embedding in the plane integer grid Z2. We remark that there may be several embeddings for the same triangle ∆= (a, b, c), which lead to different results. If we consider the number of points (xP, yP)∈Z2\E which are at integral distance to an embedded triangle E= {(xA, yA),(xB, yB),(xC, yC)}, we can distinguish three different embeddings of the Heronian triangle ∆1= (25, 20, 15). The embedding E1={(0, 0),(0, 25),(12, 16)}of ∆1yields 12 points (xP, yP)at integral distance to the corners of ∆1given by E1. For the embedding E2={(0, 0),(15, 20),(0, 20)} we obtain 16 such points, and for the embedding E3={(0, 0),(7, 24),(16, 12)}we obtain only 5such points. Determining the possible embeddings of a given Heronian triangle ∆= (a, b, c)is a rather easy task. W.l.o.g. we assume a=max{a, b, c}and xB=0=yB. Since the point (xC, yC)is at distance a to the point (xB, yB), we have to solve the Diophantine equation x2 C+y2 C=a2 in integers. This is a well known problem. One might even store for each small number (e.g. a⩽10 000) a∈Na list of the corresponding solutions (xC, yC). Now the coordinates of the remaining point Aare given as solutions of the equation system (xB−xA)2+ (yB−yA)2=c2 (xC−xA)2+ (yC−yA)2=b2 ,(5) which can be easily solved. As an algorithm for the embedding of an Heronian triangle in Z2we obtain:
MAXIMAL INTEGRAL POINT SETS OVER Z25 Algorithm 3.4. (Embedding of an Heronian Triangle) input: Heronian Triangle ∆= (a, b, c) output: complete list of different embeddings of ∆in Z2 begin xB=0,yB=0 loop over the integer solutions (xC, yC)of x2 C+y2 C=a2do loop over the integer solutions (xA, yA)of equation system (5) do output {(xA, yA),(xB, yB),(xC, yC)} end The next step is to determine the points (xP, yP)∈Z2which are at integral distance to a given embedded triangle {(xA, yA),(xB, yB),(xC, yC)}: Algorithm 3.5. (Enlargement of an embedded triangle) input: Embedded triangle E={(xA, yA),(xB, yB),(xC, yC)}⊂Z2 output: complete list of points (xP, yP)∈Z2\E which are at integral distance to E begin loop over the integer solutions (xP, yP)of equation system (1) do if (xP, yP)/∈Ethen output (xP, yP) end We remark that the previous algorithms have to be implemented using an arithmetic which is able to do integer calculations with unlimited precision, since the occurring numbers can increase very quickly. We have utilized the software package CLN [8] for this purpose. Now we utilize the set of points given by Algorithm 3.5 to build up a graph G(E). The vertices are given by the possible points (xP, yP). Two points (xP1, yP1)and (xP2, yP2)are connected by an edge if and only if p(xP1−xP2)2+ (yP1−yP2)2is a positive integer. A complete subgraph of G(E)is called a clique. A clique C1is called maximal if it is not properly contained in another clique C2of G(E). Clearly the cliques of G(E)are in bijection to integral point sets P⊂Z2containing Eas a subset. The same statement holds for maximal cliques of G(E)and maximal integral point sets P⊂Z2containing E as a subset. Thus we can use a clique-search package as CLIQUER [21] to exhaustively generate maximal integral point sets Mover Z2. Let us consider an example. If we apply our algorithm on the embedded triangle E2={(0, 0),(15, 20),(0, 20)} with diameter 25, we obtain a set {(0, 28),(0, 40),(0, 56),(0, 132),(0, −92),(0, −16),(0, 12),(−15, 20), (15, 0),(−21, 20),(105, −36),(21, 20),(−48, 20),(48, 20),(−99, 20)} of 16 possible points to enlarge the integral point set E2. The clique-search program CLIQUER determines five maximal cliques which correspond to the following five maximal integral point sets: M1={(0, 0),(15, 20),(0, 20),(15, 0)}, M2={(0, 0),(15, 20),(0, 20),(0, −92),(105, −36)}, M3={(0, 0),(15, 20),(0, 20),(0, 40),(0, 56),(0, −16),(−15, 20),(−48, 20),(48, 20)}, M4={(0, 0),(15, 20),(0, 20),(0, 40),(−15, 20),(−21, 20),(21, 20),(−48, 20),(48, 20), (−99, 20),(99, 20)},and M5={(0, 0),(15, 20),(0, 20),(0, 28),(0, 40),(0, 56),(0, 132),(0, −92),(0, −16),(0, 12), (−15, 20)}.
6 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ It is interesting to have a look at the cardinalities and diameters of these maximal integral point sets. We have |M1|=4, diam(M1) = 25,|M2|=5, diam(M2) = 119,|M3|=9, diam(M3) = 96, |M4|=11, diam(M1) = 198,|M5|=11, and diam(M5) = 224. Although we start with a point set E2of small diameter, the resulting maximal integral point sets Mimay have a large diameter. We are not aware of a formula to bound diam(M)with respect to diam(E). A second somewhat disappointing fact of our algorithm is, that each subset E0of three non-collinear points of an maximal integral point set Mproduces M. Thus our algorithm produces many identical copies of maximal integral point sets with large cardinality. We will deal with this fact and the isomorphism problem in the next section. The algorithms described in this section focus on the maximality of the integral point sets. They should not be used to exhaustively generate all maximal integral point sets up to a given diameter. To perform this task the algorithms to exhaustively generate integral point sets with or without additional properties are better suited, see [16, 20], and ignore the maximality condition in the first run. All integral point sets with required cardinalities and small diameters can then be tested if they are maximal. 4. NORMAL FORMS AND AUTOMORPHISMS FOR INTEGRAL POINT SETS OVER Z2 In this section we aim to consider isomorphisms which preserve certain properties of maximal integral point sets. Since a main property of an integral point set is the set of distances between its points we only consider distance-preserving isomorphisms, so called isometries. In the Euclidean plane the isometries are given by compositions of translations Tu,v :x y7→ x y+u v, rotations Rθ:x y7→ cos θ−sin θ sin θcos θ·x y, and reflections at one of the two axes. Each isometry can be written as It,O :x7→ t+O·x, where t∈R2is a translation vector and O∈R2×2an orthogonal matrix. Next we restrict ourselves to mappings which map integral coordinates onto integral coordinates. Thus we have t∈Z2and O∈Z2×2. Each such isometry It,O maps integral point sets onto integral point sets. It is easy to figure out that there are only 8orthogonal matrices in Z2×2. So we define Aut := It,O :t∈Z2, O ∈±1 0 0±1,±1 0 0∓1,0±1 ±1 0 ,0±1 ∓1 0 as the automorphism group of plane integral point sets. We call two integral point sets Pand P0isomorphic, if there exists a mapping It,O ∈Aut such that It,O(P) = P0. So our aim is to develop an algorithm which can check whether two given integral point sets are isomorphic. For this purpose we want to use the technique of normal forms of discrete objects. This means that we have a function τwhich fulfills the following: If Ois the orbit of an integral point set Punder the group Aut then τ(P) = τ(P0)for each P0∈O. Additionally for two integral point sets of different orbits the function τshould have different images. Having such a function τat hand we can easily decide whether two integral point sets Pand P0are isomorphic, by checking whether τ(P) = τ(P0) or not. In order to describe such a function τwe need to define a total ordering on Z2: (1) if |a|<|c|, then we set a b≺c d, (2) if a > 0, then we set −a b≺a d, (3) if |b|<|d|, then we set a b≺a d, and (4) if b>0, then we set a −b≺a b
MAXIMAL INTEGRAL POINT SETS OVER Z27 for all a, b, c, d ∈Z. We set a b=c dif and only if we have a=cand b=d. By x1x2we mean x1≺x2or x1=x2. One of the properties of this total ordering is, that we have 0 0xfor all x∈Z2, so 0 0xis the smallest element in Z2. Using ≺we can bijectively identify an integral point set Pwith a list L(P)of its points, which is sorted in ascending order with respect to . Now we extend our total ordering onto such lists by utilizing the lexicographic ordering. This allows us to define our normalization function by τ(P) = min {L(σ(P)) : σ∈Aut}. To obtain a finite algorithm for the determination of τ(P)we use the fact, that for every point set P6=∅ the minimum list-representation L(σ(P)) starts with 0 0: Algorithm 4.1. (Normalization of an integral point set) input: integral point set P={p1,...,pn} output: minimum list representation τ(P) begin champion =L(P) M1=1 0 0 1,M1=1 0 0−1,M3=−1 0 0 1,M1=−1 0 0−1 M5=0 1 1 0,M6=0 1 −1 0,M7=0−1 1 0 ,M8=0−1 −1 0 for i=1,...,ndo for j=1,...,8do tmp =L(Mj·{p1−pi,...,pn−pi}) if tmp ≺champion then champion =tmp return champion end We remark that Algorithm 4.1 runs in On2time. As an example we consider the two integral point sets from Figure 1. Their normal forms or minimum list representations are given by 0 0,0 −3,0 3,−4 0,4 0 and 0 0,0 −7,−12 9,−12 −16,−24 0,−24 −7, respectively. For a given integral point set Pthere may exist rotation matrices M∈R2×2, such that M(P)has integral coordinates, which are different from the eight orthogonal matrices in Z2×2. But for these matrices there is no guarantee for a proper extension E⊃P, which is also an integral point set over Z2, such that M(E)has integral coordinates. Examples are given by the sets E1,E2,E3in Section 3. This means that for a given maximal integral point set Mover Z2there can exist an orthogonal matrix M∈R2×2, such that M(M)is also an integral point set over Z2, but which is not maximal. We may call a maximal integral point set Mover Z2strongly maximal, if such a matrix Mdoes not exist. To check whether a given integral point set Pis strongly maximal, we only have to consider all possible embeddings of Pin Z2, which are finitely many. Another possibility is to slightly alter Algorithm 3.5 by looping over the rational (instead of integral) solutions (xP, yP)of equation system (1). Now the
8 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ algorithm leads to point sets with integral distances and rational coordinates. But due to Conjecture 3.2 (which is a theorem for dimension m=2), there exist embeddings with integral coordinates. To clear the situation with integral and rational coordinates we will have to give some facts from the general theory of integral point sets (without integral coordinates). So, let Pbe a set of points in the m-dimensional Euclidean space Emwith pairwise integral distances. By S⊆Pwe denote an integral simplex, which is a set of m+1points, and by mboxvolm(S)we denote the m-dimensional volume spanned by the m+1points. Since the pairwise distances are integral we can write volm(S) = q·kwith q∈Qand kbeing a square free integer. If volm(S)6=0the square free integer kis unique and we set char(S) = k, which we call the characteristic of S. Using this notation we can cite two results from [17]: Theorem 4.2. In an m-dimensional integral point set Pall simplices S={v0, v1,...,vm}with volm(S)6= 0have the same characteristic char(S) = k. So we can speak of the characteristic char(P)of an integral point set P. Lemma 4.3. An integral m-dimensional simplex S={v0 0, v0 1,...,v0 m}with distance matrix D= (di,j)∈ Nfor 0⩽i, j ⩽mand volm(S)6=0can be transformed via an isometry into the coordinates v0= (0,0,...,0), v1= (q1,1pk1,0,0...,0), v2= (q2,1pk1, q2,2pk2,0,...,0), . . . vm= (qm,1pk1, qm,2pk2,...,qm,mpkm), where kiis the squarefree part of voli(v0 0,v0 1,...,v0 i)2 voli−1(v0 0,v0 1,...,v0 i−1)2,qi,j ∈Q, and qj,j, kj6=0. We remark that we always have k1=1. The connection between the kiand the characteristic char(P) = kis given by char(P) = char(S) = k=square free part of m Y i=1 ki. Thus plane integral point sets Pwith rational coordinates are exactly those with characteristic char(P) = 1. Due to Conjecture 3.2 plane integral point sets over Z2correspond to plane integral point sets with characteristic 1. So in principle there is no need to care about the coordinates – this can still be done afterwards. There is one further transformation that maps integral point sets over Z2onto integral point sets over Z2: scaling by an integral factor λ. One handicap of this mapping is that the inverse mapping may lead to non-integral point sets. Another shortcoming is that maximal integral point sets may be mapped onto non-maximal integral point sets. An example is given by the maximal integral point set P= 0 0,3 0,0 4,3 4. If we scale it by a factor of 2we obtain 2·P=0 0,6 0,0 8,6 8 an integral point set over Z2which can be extended by the point 3 4. In contrast to this example the integral point set 3·P=0 0,9 0,0 12,9 12is maximal. One might conjecture that for every maximal integral point set Mthere exists an integer λ>1such that λ·Mis also maximal. 5. MAXIMAL INTEGRAL POINT SETS WITH GIVEN CARDINALITY AND MINIMUM DIAMETER From the combinatorial point of view a natural question is to ask for the minimum possible diameter dM(k, m)of a maximal integral point set M⊂Zmof cardinality k. If such a point set does not exist
MAXIMAL INTEGRAL POINT SETS OVER Z29 we set dM(k, m) = ∞. Utilizing the exhaustive algorithm described in Section 3 we have obtained the results given in Table 1. k dM(k,2)corresponding point set 45{(0, 0),(3, 4),(0, 4),(3, 0)} 58{(0, 0),(3, 4),(0, 4),(0, 8),(−3, 4)} 625 {(0, 0),(12, 16),(12, 9),(−12, 9),(−12, 16),(0, 25)} 730 {(0, 0),(6, 8),(0, 8),(0, 16),(−6, 8),(−15, 8),(15, 8)} 865 {(0, 0),(15, 36),(0, 16),(15, −20),(48, −20),(48, 36),(63, 0),(63, 16)} 996 {(0, 0),(15, 20),(0, 20),(0, 40),(0, 56),(0, −16),(−15, 20),(−48, 20),(48, 20)} {(0, 0),(22, 120),(0, 120),(−27, 120),(160, 120),(182, 0),(182, 120), 10 ⩽600 (−209, 120),(209, 120),(391, 120)} {(0, 0),(5, 12),(0, 12),(0, 24),(−5, 12),(−9, 12),(9, 12),(−16, 12),(16, 12), 11 70 (−35, 12),(35, 12)} {(0, 0),(35, 120),(35, 84),(−64, −48),(0, 204),(−189, −48),(−64, 252), 12 ⩽325 (−253, 0),(−189, 252),(−288, 84),(−288, 120),(−253, 204)} {(0, 0),(48, 64),(0, 64),(0, 128),(−48, 64),(−120, 64),(120, 64),(−252, 64), 13 ⩽2046 (252, 64),(−510, 64),(510, 64),(−1023, 64),(1023, 64)} TABLE 1. Minimum possible diameters of maximal plane integral point sets with given cardinality. Clearly we have dM(1, 2) = dM(2, 2) = ∞since a line lthrough two different points P1and P2 with integral coordinates and integral distance P1P2contains an infinite integral point set P={P1+λ· (P2−P1) : λ∈Z}as a subset. So the next value to determine is dM(3, 2). Whether dM(3, 2)is finite had been an open question of [3], which was answered in [12] by determining dM(3, 2) = 2066, – a diameter out of reach for our general exhaustive algorithm described in Section 3. But it can be easily adapted for this purpose. We alter Algorithm 3.1 by omitting right-angled triangles, since these obviously are not maximal. Then we skip Algorithm 3.4 and directly run the version of Algorithm 3.5 where we search for rational instead of integral solutions (xP, yP)of equation system (1). If we have found the first solution (xP, yP)for a given triangle ∆we can immediately stop our investigations on ∆since it cannot be a maximal integral triangle. Using these reductions and skipping the time consuming clique search we were able to exhaustively search for (strongly) maximal integral triangles over Z2with diameter at most 15000 [12, 18]. There are exactly 126 such examples. Here we list the first, with respect to their diameter, ten examples, where we give the edge lengths and the coordinates in minimal list representation, which is unique in these cases: {2066, 1803, 505}(0, 0)T,(−336, −377)T,(384, −2030)T {2549, 2307, 1492}(0, 0)T,(−700, −2451)T,(1100, −1008)T {3796, 2787, 2165}(0, 0)T,(−387, −2760)T,(1680, −3404)T {4083, 2425, 1706}(0, 0)T,(−410, −1656)T,(1273, 2064)T {4426, 2807, 1745}(0, 0)T,(−280, −2793)T,(376, −4410)T {4801, 2593, 2210}(0, 0)T,(−1488, −1634)T,(1632, 2015)T {4920, 4177, 985}(0, 0)T,(−473, −864)T,(4015, 1152)T {5044, 4443, 2045}(0, 0)T,(−1204, −1653)T,(2156, −4560)T {5045, 4803, 244}(0, 0)T,(−44, −240)T,(240, 4797)T {5186, 5163, 745}(0, 0)T,(−407, −624)T,(4030, −3264)T
16 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ Thus the distance between ξsand ξtis given by |ξs−ξt|=1 R|xsyt−xtys|. Since ηsηt= (xs+ysi)(xt−yti) = xsxt+ysyt+i(xtys−xsyt) and ηsηt=iksikt r Y j=1 ωvj+uj jωvj−uj j r Y j=1 ωvj+wj jωvj−wj j =iks−kt r Y j=1 ω2vj+uj−wj jω2vj−uj+wj j =R·iks−kt r Y j=1 ωvj+uj−wj jωvj−uj+wj j∈Z[i] we have that the distance between ξsand ξtis integral for every 1⩽s, t ⩽2τ(R). Additionally we can add the center of the circle to this point set to obtain an integral point set of cardinality 2·τ(R)+ 1having rational coordinates. After a suitable rotation we can achieve integral coordinates. So let us have an example. We choose R=5·13 =65 and successively obtain ω1=2+i, ω2=3+2i, η1=65i, η2=65, η3= −52 +39i, η4=39 +52i, η5= −60 +25i, η6=25 +60i, η7= −56 −33i, η8= −33 +56i, ξ1= −65, ξ2=65, ξ3=91 5−312 5i, ξ4= −91 5+312 5i, ξ5=595 13 −600 13 i, ξ6= −595 13 +600 13 i, ξ7=2047 65 +3696 65 i, ξ8= −2047 65 −3696 65 i. After adding the origin (0, 0)Tand applying a suitable rotation and translation we obtain the maximal integral point set P=0 0,0 −32,−30 40 ,−30 −72,−63 −16,−96 40 ,−96 −72,−126 0,−126 −32 in minimum coordinate representation. Construction 6.12. For a given Rwhich has only prime factors pfulfilling p≡1(mod 4)there exists an integral point set circle(R)consisting of 2·τ(R)points on a circle of radius Rtogether with its center, where τ(R)denotes the number of divisors of R. From the above it is easy to deduce that the 2τ(R)points on the circle all have pairwise even distances and that the diameter of this point set is given by 2R. Using this we can give another construction. Construction 6.13. For a given Rwhich has only prime factors pfulfilling p≡1(mod 4)there exists an integral point set ] circle(R)consisting of 2·τ(R)points on a circle of radius R 2, where τ(R)denotes the number of divisors of R. Conjecture 6.14. The plane integral point sets given by Construction 6.12 and Construction 6.13 are maximal. We can generalize the idea of Construction 6.13 in some way. Let tbe an arbitrary integer, Rbe a integer having only prime factor fulfilling p≡1(mod 4), and P(R)be the integral point set given by Construction 6.12 with radius R. By P(R, t)we denote the point set which arises from P(R)by scaling the point set with a factor 1 t, this means dividing all distances by t. Thus P(R, t)is a point set with pairwise rational distances and rational coordinates. With this we can construct a graph Gcontaining the points of P(R, t)as its vertices. Two vertices of Gare connected by an edge, if and only if the corresponding
MAXIMAL INTEGRAL POINT SETS OVER Z217 points have an integral distance in P(R, t). The maximal cliques Cof Gcorrespond to integral point sets P(R, t, C). Construction 6.15. For a given Rwhich has only prime factors pfulfilling p≡1(mod 4)and a given integer tthere exist integral point sets circle(R, t, C)consisting of points on a circle of radius R t, where Cis a maximal clique of the above described graph. As an abbreviation we use circle(R, t)instead of circle(R, t, C). Conjecture 6.16. For t=8Construction 6.15 gives maximal integral point sets of cardinality τ(R). 7. MAXIMAL INTEGRAL POINT SETS OVER Z2WITH FURTHER CONDITIONS k dM(k, 2)construction k dM(k, 2)construction 3=2066 ∆(2066, 1803, 505)26 ⩽112895 decompose 26·3·7, 5 4=5P1(3, 4) = ] circle(5)27 ⩽2590 decompose 23·32 5=8P2(3, 4) = crab(3, 4)28 ? .203125 ] circle 56·13 =crab(4, 3)29 ⩽1798 decompose 22·3·5 6=25 ] circle 5230 ⩽105625 ] circle 54·132 7=30 crab (8, 6, 15)31 ? .211250 circle 54·132 8=65 ] circle (5·13)32 ⩽27625 ] circle 53·13 ·17 9=130 circle (5·13)33 ⩽55250 circle 53·13 ·17 10 ⩽625 ] circle 5434 ⩽142295 decompose 23·3·7·11, 5 11 =70 decompose 22·335 ⩽18430 decompose 26·3 12 =325 ] circle 52·1336 ⩽40625 ] circle 55·13 13 ⩽650 circle 52·1337 ⩽10366 decompose 24·32 14 ⩽15625 ] circle 5638 ? .571535 decompose 24·33·7, 5 15 ⩽8190 decompose 2739 ? .4816895 decompose 29·3·7, 5 16 ⩽1105 ] circle (5·13 ·17)40 ⩽138125 ] circle 54·13 ·17 17 =286 decompose 23·341 ⩽73726 decompose 27·3 18 ⩽4225 ] circle 52·13242 ? .677375 decompose 26·32·7, 5 19 ⩽8450 circle 52·13243 ? .4573799 decompose 23·32·5·7·11, 17 20 ⩽8125 ] circle 54·1344 ? .6614998 decompose 24·32·52·7, 13 21 ⩽16250 circle 54·1345 ? .7001315 decompose 23·32·72, 5 22 ⩽53360 decompose 22·3·7·11, 546 ? .64833614 decompose 22·34·5·7·11, 17 23 ⩽1150 decompose 24·347 ⩽7198 decompose 23·3·5 24 ⩽5525 ] circle 52·13 ·1748 ? .160225 ] circle 52·13 ·17 ·29 25 ⩽11050 circle 52·13 ·1749 ? .320450 circle 52·13 ·17 ·29 50 ? .4064255 decompose 27·32·7, 5 TABLE 2. Best known constructions for maximal integral point sets over Z2in arbitrary position. In Table 2 we have summarized the constructions yielding the smallest diameter of a maximal integral point set over Z2. Some of the values dM(k, 2)could be determined exactly by an exhaustive search, but
18 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ for most values of kwe only have upper bounds (and 301 as lower bound). In some cases, denoted by ? ., we were not able to check the maximality of the constructed point sets, since their diameter was too large. Looking at Table 2 we observe, that the constructions of crabs (Construction 6.6 and Construction 6.10) are very dominating. The resulting point sets contain n−2and n−1collinear points out of npoints, respectively. So it may be interesting to study maximal integral point sets over Z2, where no three points are collinear. We also say, that a point set is in semi-general position, if no three points are collinear. By dM(k, 2)we denote the minimum possible diameter of these point sets. We can check for this further condition, that no three points are collinear, by applying Lemma 6.8. Using the methods and algorithms described in this article, we were able to obtain some exact values and some upper bounds for dM(k, 2). The results are summarized in Table 3. We would like to remark that we additionally have the lower bounds dM(k, 2)⩾5525 for k∈{11, 13, 14, 15, 17}and dM(k, 2)⩾10001 for k⩾19,k6=20, 24. k dM(k, 2)construction k dM(k, 2)construction 3=2066 ∆(2066,1803,505)27 ? .305218 circle(52·132·172,8) 4=5P1(3,4)= ^ circle(5)28 ? .203125 ^ circle(56·13) 5=120 see Figure 5 29 ? .9311389618298531250 circle(528,8) 6=25 ^ circle(52)30 ⩽105625 ^ circle(54·132) 7=925 see Figure 6 31 ? .232784740457463281250 circle(530,8) 8=65 ^ circle(5·13)32 ⩽27625 ^ circle(53·13·17) 9=1045 see Figure 7 33 ? .412343750 circle(510·132,8) 10 =625 ^ circle(54)34 ? .152587890625 ^ circle(516) 11 ? .2434375 circle(510,8)35 ? .111562500 circle(56·134,8) 12 =325 ^ circle(52·13)36 ⩽71825 ^ circle(52·132·17) 13 ? .60859375 circle(512,8)37 ? .3637261569647863769531250 circle(536,8) 14 ⩽15625 ^ circle(56)38 ? .3814697265625 ^ circle(518) 15 ⩽26390 circle(54·132,8)39 ? .10314771205 circle(512·132,8) 16 =1105 ^ circle(5·13·17)40 ⩽138125 ^ circle(54·13·17) 17 ? .38037109375 circle(516,8)41 ? .2273288481029914855957031250 circle(540,8) 18 =4225 ^ circle(52·132)42 ? .2640625 ^ circle(56·132) 19 ? .950927734375 circle(518,8)43 ? .56832212025747871398925781250 circle(542,8) 20 =8125 ^ circle(54·13)44 ? .126953125 ^ circle(510·13) 21 ? .659750 circle(56·132,8)45 ? .7630450 circle(54·132·172,8) 22 ? .9765625 ^ circle(510)46 ? .2384185791015625 ^ circle(522) 23 ? .595928935571106 circle(522,8)47 ? .35520132516092419624328613281250 circle(546,8) 24 =5525 ^ circle(52·13·17)48 ? .160225 ^ circle(52·13·17·29) 25 ? .4462500 circle(54·134,8)49 ? .18854062500 circle(56·136,8) 26 ? .244140625 ^ circle(512)50 ? .17850625 ^ circle(54·134) TABLE 3. Best known constructions for maximal integral point sets over Z2in semigeneral position.
MAXIMAL INTEGRAL POINT SETS OVER Z219 We would like to have a closer look on the smallest known examples of maximal integral point sets in semi-general position consisting of an odd number of points. For cardinality 5the two smallest point sets with respect to the diameter are given in minimum coordinate representation by 0 0,0 −78,−20 21 ,−20 −99,−52, −39and 0 0,0 −80,−45 28 ,−45 −108,−96 −40, see Figure 5 for a drawing of the first point set. Both point sets consist of four point on a circle Cof radii 29·101 40 and 13·53 10 , respectively. In each case the fifth point does not lie on this circle C, but the line through this point and the center of Cis a symmetry axis of the point set. x x x x x FIGURE 5. The smallest maximal integral point set of cardinality 5in semi-general position. For cardinality 7the two smallest examples are given by 0 0,0 −285,−180 240 ,−440 −384,−700 240 ,−880 0,−880 −285 and 0 0,0 −855,−540 720 ,−1320 −1152,−2100 720 ,−2640 0,−2640 −855 , see Figure 6 for a graphical representation of the first example. The geometric shape of the corresponding two point sets is similar to the case of cardinality 5. In each case 6points are situated on a circle Cof radii 52·37 2and 3·52·37 2, respectively. Again we have the symmetry axis through the seventh point and the center of C. u uu u u u u FIGURE 6. The smallest maximal integral point set of cardinality 7in semi-general position.
20 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ For cardinality 9the two smallest examples are given by 0 0,0 −504,−64 −252,612 255,612 −759,720 210,720 −714,836 123,836 −627 and 0 0,0 −672,−123 164 ,−123 −836,−816 340 ,−816 −1012,−960 280 ,−960 −952,−1323 −336 , see Figure 7 for a graphical representation of the first example. Here in both examples all nine points are situated of circles of radii 52·132 8and 52·132 6, respectively. They both can be obtained using Construction 6.15. u u u u u u u u u FIGURE 7. The smallest maximal integral point set of cardinality 9in semi-general position. Now we observe that the constructions based on circles, Construction 6.12, Construction 6.13, and Construction 6.15, are very dominating in this context. The next natural step is to also forbid four points on a circle. If no three points are on a line and no four points on a circle we speak of general position. By ˙ dM(k, 2)we denote the minimum possible diameter of a maximal plane integral point set in general position over Z2. Without the maximality condition these point sets are also known as k2-cluster [22]. As we cannot apply our most successful constructions based on crabs and circles in this case, examples are scarce. For the check whether four points are situated on a circle we have a well known criterion similar to Lemma 6.8: Lemma 7.1. Four points (x1, y1),(x2, y2),(x3, y3),(x4, y4)in R2are situated on a circle if and only if x1y1x2 1+y2 11 x2y2x2 2+y2 21 x3y3x2 3+y2 31 x4y4x2 4+y2 41 =0 holds. In Table 4 we have summarized our knowledge on ˙ dM(k, 2). For the lower bound ˙ dM(7, 2)> 599000 we refer to [18]. Whether ˙ dM(7, 2)is finite (even if we drop the maximality condition) is an open
MAXIMAL INTEGRAL POINT SETS OVER Z221 v vv v FIGURE 8. The smallest maximal integral point set of cardinality 4in general position. v v v v v FIGURE 9. The smallest maximal integral point set of cardinality 5in general position. v vv v v v FIGURE 10. The smallest maximal integral point set of cardinality 6in general position. problem, see [7, 22]. If we drop the maximality condition and the condition on the integrality of the coordinates (in other words characteristic one), then very recently two such examples were found, see [14]. The smallest example for k=6is indeed the smallest integral point set of characteristic one in general position with cardinality 6. We would also like to give the coordinates for the second smallest examples. For cardinality 4we have 0 0,0 −69,−20 −21,−92 0, for cardinality 5we have 0 0,0 −153,−60 144,−140 −48 ,−176 57 ,
22 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ and for cardinality 6we have 0 0,−135 −1008,420 1008,735 −392,1155 616 ,1290 1624. k=|P| ˙ dM(k, 2)construction 3=2066 ∆(2066, 1803, 505) 4=87 0 0,0 −33,−16 30 ,44 −33, see Figure 8 5=165 0 0,0 −72,−35 12 ,64 −120,−90 −120, see Figure 9 6=1886 0 0,0 −828,−448 −414,−720 132 ,−1260 −1023,−1840 −414 , see Figure 10 7> 599000 TABLE 4. Best known constructions for maximal integral point sets over Z2in general position. 8. CONCLUSION AND OUTLOOK We have described several constructions for integral point sets over Z2with given cardinality that fulfill some further properties. Although the maximality of the resulting integral point sets cannot be guaranteed so far, we conjecture them to be in many cases. We have described efficient algorithms for exhaustive generation of maximal integral point sets over Z2and for testing the maximality of a given integral point set. Some exact values of minimum diameters for given cardinalities could be obtained and several values are constructed as upper bounds and conjectured to be the exact values. It remains a task to prove the maximality of point sets resulting from some of our constructions in general. Clearly similar problems could be considered in higher dimensions. REFERENCES 1. N. H. Anning and P. Erd˝ os, Integral distances, Bull. Amer. Math. Soc. 51 (1945), 598–600. 2. A. Antonov and M. Brancheva, Algorithm for finding maximal Diophantine figures, Spring Conference 2007 of the Union of Bulgarian Mathematicians, 2007. 3. S. Dimiev and K. Markov, Gauss Integers and Diophantine Figures, Mathematics and Mathematical Education 31 (2002), 88–95, arXiv:math.NT/0203061v1 7 Mar 2002. 4. P. Erd˝ os, Integral distances, Bull. Amer. Math. Soc. 51 (1945), 996. 5. J. Fricke, On heron simplices and integer embedding, preprint (2001). 6. R. E. Fullerton, Integral distances in banach spaces, Bull. Amer. Math. Soc. 55 (1949), 901–905. 7. R. K. Guy, Unsolved problems in number theory. 2nd ed., Unsolved Problems in Intuitive Mathematics. 1. New York, NY: SpringerVerlag. xvi, 285 p., 1994. 8. B. Haible and R. Kreckel, Cln, a class library for numbers, 2005, http://www.ginac.de/CLN/. 9. H. Harborth, Integral distances in point sets, Karl der Grosse und sein Nachwirken. 1200 Jahre Kultur und Wissenschaft in Europa. Band 2: Mathematisches Wissen. Turnhout: Brepols (P. L. Butzer et al., eds.), 1998, pp. 213–224. 10. H. Harborth, A. Kemnitz, and M. M¨ oller, An upper bound for the minimum diameter of integral point sets, Discrete Comput. Geom. 9(1993), no. 4, 427–432. 11. M. Kiermaier and S. Kurz, Inclusion-maximal integral point sets in affine planes over finite fields, (submitted). 12. A. Kohnert and S. Kurz, A note on Erd¨ os-Diophantine graphs and Diophantine carpets, Math. Balkanica 21 (2007), no. 1-2, 1–5. 13. A. Kohnert and S. Kurz, Integral point sets over Zm n, Discrete Appl. Math. (to appear). 14. T. Kreisel and S. Kurz, There are integral heptagons, no three points on a line, no four on a circle, Discrete. Comput. Geom. (to appear). 15. S. Kurz, Integral point sets over finite fields, (submitted).
MAXIMAL INTEGRAL POINT SETS OVER Z223 16. S. Kurz, Konstruktion und Eigenschaften ganzzahliger Punktmengen, Ph.D. thesis, Bayreuth. Math. Schr. 76. Universit¨ at Bayreuth, 2006. 17. , On the characteristic of integral point sets in Em, Australas. J. Comb. 36 (2006), 241–248. 18. S. Kurz, On the generation of heronian triangles, (in preparation). 19. S. Kurz and R. Laue, Upper bounds for integral point sets, Australas. J. Comb. 39 (2007), 233–240. 20. S. Kurz and A. Wassermann, On the minimum diameter of plane integral point sets, Ars Combin. (to appear). 21. S. Niskanen and P. R. J. ¨ Osterg˚ ard, Cliquer user’s guide, version 1.0, Tech. Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, 2003. 22. L. C. Noll and D. I. Bell, n-clusters for 1<n<7, Math. Comput. 53 (1989), no. 187, 439–444. ANDREY RADOSLAVOV ANTONOV, DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CHEMICAL TECHNOLOGY AND METALLURGY - SOFIA, BULGARIA E-mail address:[email protected] SASCHA KURZ, DEPARTMENT OF MATHEMATICS, PHYSIC AND INFORMATICS, UNIVERSITY OF BAYREUTH, GERMANY E-mail address:[email protected]