Maximal integral point sets over Z^2
Full text
MAXIMAL INTEGRAL POINT SETS OVER Z2
ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
ABSTRACT. Geome ical objec s wi h in eg al side leng hs ha e ascina ed ma hema icians h ough he ages.
We call a se P={p1,...,pn}⊂Z2a maximal in eg al poin se o e Z2i all pai wise dis ances a e
in eg al and e e y addi ional poin pn+1des oys his p ope y. He e we conside such se s o a gi en
ca dinali y and wi h minimum possible diame e . We de e mine some exac alues ia exhaus i e sea ch and
gi e se e al cons uc ions o a bi a y ca dinali ies. Since we canno gua an ee he maximali y in hese cases
we desc ibe an algo i hm o p o e o disp o e he maximali y o a gi en in eg al poin se . We addi ionally
conside es ic ions as no h ee poin s on a line and no ou poin s on a ci cle.
1. INTRODUCTION
Geome ical objec s wi h in eg al side leng hs ha e ascina ed ma hema icians h ough he ages. A
e y ea ly example is he Py hago ean iangle wi h side leng hs 3,4, and 5. A uni e sal amewo k o
mos o hese objec s a e in eg al poin se s. By an in eg al poin se we unde s and a se o npoin s in an
mdimensional Euclidean ec o space Em, whe e he pai wise dis ances be ween he poin s a e in eg al.
Those in eg al poin se s we e s udied by many au ho s, see [9] o an o e iew. F om a combina o ial
poin o iew o a gi en ca dinali y nand a gi en dimension m he ques ion on he minimum possible
diame e d(n, m), his is he la ges dis ance be ween any wo poin s, a ises, see [16, 19, 20] o an
o e iew.
To ob ain some in e es ing disc e e s uc u es one could also equi e some addi ional p ope ies. One
possibili y is o eques , ha besides he dis ances also he coo dina es mus be in eg al. Ano he classical
possibili y is o o bid subse s o h ee poin s on a line o ou poin s on a ci cle. The ques ion o P.
E d˝
os whe he he e exis s a se o se en poin s in he plane wi h no h ee poin s on a line, no ou poin s
on a ci cle, and pai wise in eg al dis ances, has ecen ly been answe ed posi i ely, see [14]. I all h ee
men ioned addi ional p ope ies a e equi ed simul aneously one speaks o nm-clus e s, see [22]. In his
a icle we eques ha besides he dis ances also he coo dina es o he poin se s a e in eg al and es ic
ou sel es o dimension 2. Addi ionally we conside he cases whe e no h ee poin s a e on a line o no
ou poin s a e on a ci cle.
In ini e geome y one is some imes in e es ed in poin con igu a ions which a e maximal wi h espec
o some p ope y. This means ha i is no possible o add a poin wi hou des oying he eques ed
p ope y. He e we conside in eg al poin se s which a e maximal, meaning ha he e does no exis an
addi ional poin xwi h in eg al dis ances o he o he poin s o he poin se .
1.1. Rela ed wo k. The e ha e been ex ensi e s udies on in eg al poin se s in Euclidean spaces. Some
au ho s also conside o he spaces, e. g. Banach spaces [6], in eg al poin se s o e ings [13], o in eg al
poin se s o e ini e ields [2, 11, 15]. In [3] he au ho s conside in eg al poin se s o e Z2and conjec u e
some examples o be maximal. As an answe o hei open p oblems in [12] he au ho s desc ibe an
algo i hm o p o e he maximali y o a gi en in eg al poin se and p o e he conjec u es o [3].
2000 Ma hema ics Subjec Classi ica ion. 52C10;52C45,05D99,11D99,52-04.
Key wo ds and ph ases. in eg al dis ances, diame e , exhaus i e sea ch, maximali y.
1
2 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
1.2. Ou con ibu ion. In his pape we desc ibe algo i hms o e icien ly es in eg al poin se s o
maximali y and o de e mine possible ex ension poin s. To deal wi h he isomo phism p oblem we de-
sc ibe an algo i hm which ans o ms a gi en plane in eg al poin se in o a no mal o m in On2 ime,
whe e nis he ca dinali y o he poin se . We gi e se e al cons uc ions o in eg al poin se s o e Z2
which ha e a gi en ca dinali y and ul ill addi ional condi ions such as ha he e a e “no h ee poin s on a
line” o “no ou poin s on a ci cle”. Al hough we canno p o e he maximali y o he poin se s ob ained
wi h he p oposed cons uc ions in gene al, we conjec u e his p ope y o many o ou cons uc ions.
By exhaus i e sea ch we ha e de e mined some exac minimum diame e s o in eg al poin se s o e Z2
wi h gi en ca dinali y and wi h o wi hou addi ional condi ions. We gi e cons uc i e uppe bounds in
mos cases and conjec u e hem o be he exac alues.
1.3. Ou line o he pape . In Sec ion 3 we s a e he basic de ini ions and in Sec ion 2 we desc ibe he
basic algo i hms o deal wi h maximal in eg al poin se s o e Z2. These include an algo i hm o exhaus-
i ely gene a e He onian iangles up o isomo phism, an algo i hm o de e mine all possible embeddings
o an He onian iangle on he in ege g id Z2, and an algo i hm ha de e mines all poin s o Z2which
ha e in eg al dis ances o h ee gi en poin s in Z2wi h pai wise in eg al dis ances. The las men ioned
algo i hm enables us o algo i hmically p o e o disp o e he maximali y o a gi en in eg al poin se .
Since we in end o conside in eg al poin se s up o isomo phism we in oduce no mal o ms o in eg al
poin se s and algo i hms o ob ain hem in Sec ion 4. We deal wi h he key ques ion o maximal in eg al
poin se s o e Z2wi h gi en ca dinali y and minimum diame e in Sec ion 5. Se e al cons uc ions o
maximal in eg al poin se s, whe e he maximali y is no gua an eed bu e y likely, a e desc ibed in Sec-
ion 6. In Sec ion 7 we deal wi h addi ional p ope ies as “no h ee poin s on a line” and “no ou poin s
on a ci cle”. We inish wi h a sho conclusion and an ou look in Sec ion 8.
2. BASICS
De ini ion 2.1. An in eg al poin se o e Z2is a non-collinea se Po npoin s in he in ege g id Z2,
whe e he poin s ha e pai wise in eg al dis ances.
Fo b e i y we only speak o in eg al poin se s and assume ha he coo dina es o he poin s a e
in eg al numbe s, oo.
De ini ion 2.2. We call an in eg al poin se Po e Z2maximal i o e e y x∈Z2 P he poin se
P∪{x}is no an in eg al poin se .
The exis ence o maximal in eg al poin se s in he plane is gua an eed by a amous heo em o
N.H.. Anning and P. E d˝
os, espec i ely i s p oo .
Theo em 2.3. An in ini e se Po poin s in he Euclidean space Emwi h pai wise in eg al dis ances is
si ua ed on a line. [1, 4]
PROOF. We only p o e he s a emen o dimension m=2, as he gene aliza ion is ob ious. I A,B, and
Ca e h ee poin s no on a line, we se k=max AC, BCand conside poin s Psuch ha |PA −PC|
and |PB −PC|a e in eg al. Due o he iangle inequali ies he a ained alues a e in {0,1,...,k}. Thus
he poin Plies on he in e sec ion o wo dis inc hype bolas, whe e we ha e a mos k+1choices o
each hype bola. Thus he e a e a mos 4(k+1)2possible loca ions o he poin P.
This p oo can clea ly be con e ed in o a cons uc i e algo i hm. Gi en h ee poin s A= (xA, yA),
B= (xB, yB), and C= (xC, yC)in P⊂Z2, which a e no on a line, he p oblem o de e ming poin s
P= (xP, yP)a in eg al dis ance o A,B, and Cis educed o he p oblem o sol ing he equa ion sys em
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
whe e d1∈−AC, . . . , AC⊂Zand d2∈−BC, . . . , BC⊂Z. I he e exis s no in eg al solu ion
in Z2 P, hen he poin se Pis maximal. This algo i hm was al eady used in [12] o p o e he maximali y
o he in eg al poin se s o Figu e 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 o maximal in eg al poin se s.
Since his algo i hm is essen ial o ou a icle we will go in o he de ails how o sol e equa ion sys em
1. To ge id o some o he squa e oo s we add p(xC−xP)2+ (yC−yP)2on bo h sides and squa e
he exp essions a e wa ds:
(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
.
Rea anging 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)
I d1=0 hen he i s equa ion co esponds o a linea equa ion
c1xP+c2yP+c3=0, (3)
whe e no bo h c1and c2a e equal o ze o, since A6=C. I we squa e he second equa ion o (2) we
can subs i u e one a iable using equa ion (3) and ob ain a quad a ic equa ion in one a iable, which can
be easily sol ed. The case, whe e d2=0is simila . He e we use he second equa ion o (2) o ob ain
equa ion (3) (we ha e c16=0o c26=0due o B6=C), and subs i u e i in o he squa ed e sion o he
i s equa ion o ob ain he quad a ic equa ion in one a iable. In he emaining case we ha e d1, d26=0.
He e we sub ac d1 imes he second equa ion o (2) om d2 imes he i s equa ion o (2) o ob ain
equa ion (3) (we ha e c16=0o c26=0since he poin s A,B, and Ca e no loca ed on a line). Now we
can squa e one o he wo equa ions o (2) and subsi u e one a iables using equa ion (3). Again we end
up wi h a quad a ic equa ion in one a iable. A he end we ha e o check i he ob ained alues (xP, yP)
a e solu ions o he o iginal equa ion sys em (1).
De ini ion 2.4. Fo an in eg al poin se Pi s diame e diam(P)is gi en by he la ges dis ance be ween
a pai o i s poin s.
We ema k ha he le in eg al poin se o Figu e 1 has diame e 8and he igh in eg al poin se o
Figu e 1 has diame e 25.
4 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
3. EXHAUSTIVE GENERATION OF MAXIMAL INTEGRAL POINT SETS
To ob ain in e es ing examples o maximal in eg al poin se s we u ilize compu e s o exhaus i ely gen-
e a e maximal in eg al poin se s. In he ollowing we will desc ibe he algo i hm used. Fo a gi en
diame e dwe loop o e all non-isomo phic He onian iangles (ha ing in eg al side leng hs and in eg al
a ea) ∆= (a, b, c)wi h diame e d=max{a, b, c}. U ilizing he He on o mula
A=p(a+b+c)(a+b−c)(a−b+c)(−a+b+c)
4(4)
o he a ea o a iangle we can gene a e his lis e.g. by he ollowing sho algo i hm:
Algo i hm 3.1. (Gene a ion o He onian iangles)
inpu : diame e d
ou pu : comple e lis o He onian iangles wi h diame e dup o isomo phism
begin
a=d
o b=a+2
2,...,ado
o c=a+1−b,...,bdo
i √(a+b+c)(a+b−c)(a−b+c)(−a+b+c)
4∈Z hen
ou pu (a, b, c)
end
Fo a mo e sophis ica ed and e icien algo i hm we e e o [18]. The nex s ep is o embed a gi en
He onian iangle ∆= (a, b, c)in he plane in ege g id Z2. He e we can u ilize wo conjec u es, which
a e heo ems o dimension m=2, see e.g. [5].
Conjec u e 3.2. Le P⊂Qmbe a ini e se o poin s such ha he dis ances be ween any wo poin s o
Pa e in ege s. In his case one can ind an Euclidean mo ion Tsuch ha T(P)⊂Pm.
Conjec u e 3.3. Le P⊂Zmbe a ini e se o poin s such ha he dis ances be ween any wo poin s o
Pa e in ege s and di isible by an in ege k. In his case one can ind a se P0⊂Zmsuch ha P0·k( he
se P0scaled by a ac o k) is cong uen o P.
Since Conjec u e 3.2 is a well known heo em o dimension m=2, see e.g. [5], o e e y He onian
iangle ∆(a, b, c) he e exis s an embedding in he plane in ege g id Z2. We ema k ha he e may be
se e al embeddings o he same iangle ∆= (a, b, c), which lead o di e en esul s. I we conside
he numbe o poin s (xP, yP)∈Z2 E which a e a in eg al dis ance o an embedded iangle E=
{(xA, yA),(xB, yB),(xC, yC)}, we can dis inguish h ee di e en embeddings o he He onian iangle
∆1= (25, 20, 15). The embedding E1={(0, 0),(0, 25),(12, 16)}o ∆1yields 12 poin s (xP, yP)a
in eg al dis ance o he co ne s o ∆1gi en by E1. Fo he embedding E2={(0, 0),(15, 20),(0, 20)}
we ob ain 16 such poin s, and o he embedding E3={(0, 0),(7, 24),(16, 12)}we ob ain only 5such
poin s. De e mining he possible embeddings o a gi en He onian iangle ∆= (a, b, c)is a a he easy
ask. W.l.o.g. we assume a=max{a, b, c}and xB=0=yB. Since he poin (xC, yC)is a dis ance a
o he poin (xB, yB), we ha e o sol e he Diophan ine equa ion
x2
C+y2
C=a2
in in ege s. This is a well known p oblem. One migh e en s o e o each small numbe (e.g. a⩽10 000)
a∈Na lis o he co esponding solu ions (xC, yC). Now he coo dina es o he emaining poin Aa e
gi en as solu ions o he equa ion sys em
(xB−xA)2+ (yB−yA)2=c2
(xC−xA)2+ (yC−yA)2=b2
,(5)
which can be easily sol ed. As an algo i hm o he embedding o an He onian iangle in Z2we ob ain:
MAXIMAL INTEGRAL POINT SETS OVER Z25
Algo i hm 3.4. (Embedding o an He onian T iangle)
inpu : He onian T iangle ∆= (a, b, c)
ou pu : comple e lis o di e en embeddings o ∆in Z2
begin
xB=0,yB=0
loop o e he in ege solu ions (xC, yC)o x2
C+y2
C=a2do
loop o e he in ege solu ions (xA, yA)o equa ion sys em (5) do
ou pu {(xA, yA),(xB, yB),(xC, yC)}
end
The nex s ep is o de e mine he poin s (xP, yP)∈Z2which a e a in eg al dis ance o a gi en
embedded iangle {(xA, yA),(xB, yB),(xC, yC)}:
Algo i hm 3.5. (Enla gemen o an embedded iangle)
inpu : Embedded iangle E={(xA, yA),(xB, yB),(xC, yC)}⊂Z2
ou pu : comple e lis o poin s (xP, yP)∈Z2 E which a e a in eg al dis ance o E
begin
loop o e he in ege solu ions (xP, yP)o equa ion sys em (1) do
i (xP, yP)/∈E hen
ou pu (xP, yP)
end
We ema k ha he p e ious algo i hms ha e o be implemen ed using an a i hme ic which is able o
do in ege calcula ions wi h unlimi ed p ecision, since he occu ing numbe s can inc ease e y quickly.
We ha e u ilized he so wa e package CLN [8] o his pu pose.
Now we u ilize he se o poin s gi en by Algo i hm 3.5 o build up a g aph G(E). The e ices a e
gi en by he possible poin s (xP, yP). Two poin s (xP1, yP1)and (xP2, yP2)a e connec ed by an edge i
and only i p(xP1−xP2)2+ (yP1−yP2)2is a posi i e in ege . A comple e subg aph o G(E)is called
a clique. A clique C1is called maximal i i is no p ope ly con ained in ano he clique C2o G(E).
Clea ly he cliques o G(E)a e in bijec ion o in eg al poin se s P⊂Z2con aining Eas a subse . The
same s a emen holds o maximal cliques o G(E)and maximal in eg al poin se s P⊂Z2con aining E
as a subse . Thus we can use a clique-sea ch package as CLIQUER [21] o exhaus i ely gene a e maximal
in eg al poin se s Mo e Z2.
Le us conside an example. I we apply ou algo i hm on he embedded iangle
E2={(0, 0),(15, 20),(0, 20)}
wi h diame e 25, we ob ain a se
{(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)}
o 16 possible poin s o enla ge he in eg al poin se E2. The clique-sea ch p og am CLIQUER de e mines
i e maximal cliques which co espond o he ollowing i e maximal in eg al poin se s:
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
I is in e es ing o ha e a look a he ca dinali ies and diame e s o hese maximal in eg al poin se s.
We ha e |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. Al hough we s a wi h a poin se
E2o small diame e , he esul ing maximal in eg al poin se s Mimay ha e a la ge diame e . We a e
no awa e o a o mula o bound diam(M)wi h espec o diam(E). A second somewha disappoin ing
ac o ou algo i hm is, ha each subse E0o h ee non-collinea poin s o an maximal in eg al poin se
Mp oduces M. Thus ou algo i hm p oduces many iden ical copies o maximal in eg al poin se s wi h
la ge ca dinali y. We will deal wi h his ac and he isomo phism p oblem in he nex sec ion.
The algo i hms desc ibed in his sec ion ocus on he maximali y o he in eg al poin se s. They should
no be used o exhaus i ely gene a e all maximal in eg al poin se s up o a gi en diame e . To pe o m
his ask he algo i hms o exhaus i ely gene a e in eg al poin se s wi h o wi hou addi ional p ope ies
a e be e sui ed, see [16, 20], and igno e he maximali y condi ion in he i s un. All in eg al poin se s
wi h equi ed ca dinali ies and small diame e s can hen be es ed i hey a e maximal.
4. NORMAL FORMS AND AUTOMORPHISMS FOR INTEGRAL POINT SETS OVER Z2
In his sec ion we aim o conside isomo phisms which p ese e ce ain p ope ies o maximal in eg al
poin se s. Since a main p ope y o an in eg al poin se is he se o dis ances be ween i s poin s we
only conside dis ance-p ese ing isomo phisms, so called isome ies. In he Euclidean plane he isome-
ies a e gi en by composi ions o ansla ions Tu, :x
y7→ x
y+u
, o a ions Rθ:x
y7→
cos θ−sin θ
sin θcos θ·x
y, and e lec ions a one o he wo axes. Each isome y can be w i en as
I ,O :x7→ +O·x, whe e ∈R2is a ansla ion ec o and O∈R2×2an o hogonal ma ix.
Nex we es ic ou sel es o mappings which map in eg al coo dina es on o in eg al coo dina es. Thus
we ha e ∈Z2and O∈Z2×2. Each such isome y I ,O maps in eg al poin se s on o in eg al poin se s.
I is easy o igu e ou ha he e a e only 8o hogonal ma ices in Z2×2. So we de ine
Au := I ,O : ∈Z2, O ∈±1 0
0±1,±1 0
0∓1,0±1
±1 0 ,0±1
∓1 0
as he au omo phism g oup o plane in eg al poin se s.
We call wo in eg al poin se s Pand P0isomo phic, i he e exis s a mapping I ,O ∈Au such ha
I ,O(P) = P0. So ou aim is o de elop an algo i hm which can check whe he wo gi en in eg al poin
se s a e isomo phic. Fo his pu pose we wan o use he echnique o no mal o ms o disc e e objec s.
This means ha we ha e a unc ion τwhich ul ills he ollowing: I Ois he o bi o an in eg al poin
se Punde he g oup Au hen τ(P) = τ(P0) o each P0∈O. Addi ionally o wo in eg al poin se s
o di e en o bi s he unc ion τshould ha e di e en images. Ha ing such a unc ion τa hand we can
easily decide whe he wo in eg al poin se s Pand P0a e isomo phic, by checking whe he τ(P) = τ(P0)
o no .
In o de o desc ibe such a unc ion τwe need o de ine a o al o de ing on Z2:
(1) i |a|<|c|, hen we se a
b≺c
d,
(2) i a > 0, hen we se −a
b≺a
d,
(3) i |b|<|d|, hen we se a
b≺a
d, and
(4) i b>0, hen we se a
−b≺a
b
MAXIMAL INTEGRAL POINT SETS OVER Z27
o all a, b, c, d ∈Z. We se a
b=c
di and only i we ha e a=cand b=d. By x1x2we
mean x1≺x2o x1=x2. One o he p ope ies o his o al o de ing is, ha we ha e 0
0x o all
x∈Z2, so 0
0xis he smalles elemen in Z2. Using ≺we can bijec i ely iden i y an in eg al poin
se Pwi h a lis L(P)o i s poin s, which is so ed in ascending o de wi h espec o . Now we ex end
ou o al o de ing on o such lis s by u ilizing he lexicog aphic o de ing. This allows us o de ine ou
no maliza ion unc ion by
τ(P) = min
{L(σ(P)) : σ∈Au }.
To ob ain a ini e algo i hm o he de e mina ion o τ(P)we use he ac , ha o e e y poin se P6=∅
he minimum lis - ep esen a ion L(σ(P)) s a s wi h 0
0:
Algo i hm 4.1. (No maliza ion o an in eg al poin se )
inpu : in eg al poin se P={p1,...,pn}
ou pu : minimum lis ep esen a ion τ(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
o i=1,...,ndo
o j=1,...,8do
mp =L(Mj·{p1−pi,...,pn−pi})
i mp ≺champion hen
champion = mp
e u n champion
end
We ema k ha Algo i hm 4.1 uns in On2 ime. As an example we conside he wo in eg al poin
se s om Figu e 1. Thei no mal o ms o minimum lis ep esen a ions a e gi en by
0
0,0
−3,0
3,−4
0,4
0
and 0
0,0
−7,−12
9,−12
−16,−24
0,−24
−7,
espec i ely.
Fo a gi en in eg al poin se P he e may exis o a ion ma ices M∈R2×2, such ha M(P)has in e-
g al coo dina es, which a e di e en om he eigh o hogonal ma ices in Z2×2. Bu o hese ma ices
he e is no gua an ee o a p ope ex ension E⊃P, which is also an in eg al poin se o e Z2, such ha
M(E)has in eg al coo dina es. Examples a e gi en by he se s E1,E2,E3in Sec ion 3. This means ha
o a gi en maximal in eg al poin se Mo e Z2 he e can exis an o hogonal ma ix M∈R2×2, such
ha M(M)is also an in eg al poin se o e Z2, bu which is no maximal.
We may call a maximal in eg al poin se Mo e Z2s ongly maximal, i such a ma ix Mdoes no
exis . To check whe he a gi en in eg al poin se Pis s ongly maximal, we only ha e o conside all
possible embeddings o Pin Z2, which a e ini ely many. Ano he possibili y is o sligh ly al e Algo i hm
3.5 by looping o e he a ional (ins ead o in eg al) solu ions (xP, yP)o equa ion sys em (1). Now he
8 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
algo i hm leads o poin se s wi h in eg al dis ances and a ional coo dina es. Bu due o Conjec u e 3.2
(which is a heo em o dimension m=2), he e exis embeddings wi h in eg al coo dina es.
To clea he si ua ion wi h in eg al and a ional coo dina es we will ha e o gi e some ac s om he
gene al heo y o in eg al poin se s (wi hou in eg al coo dina es). So, le Pbe a se o poin s in he
m-dimensional Euclidean space Emwi h pai wise in eg al dis ances. By S⊆Pwe deno e an in eg al
simplex, which is a se o m+1poin s, and by mbox olm(S)we deno e he m-dimensional olume
spanned by he m+1poin s. Since he pai wise dis ances a e in eg al we can w i e olm(S) = q·kwi h
q∈Qand kbeing a squa e ee in ege . I olm(S)6=0 he squa e ee in ege kis unique and we se
cha (S) = k, which we call he cha ac e is ic o S. Using his no a ion we can ci e wo esul s om [17]:
Theo em 4.2. In an m-dimensional in eg al poin se Pall simplices S={ 0, 1,..., m}wi h olm(S)6=
0ha e he same cha ac e is ic cha (S) = k.
So we can speak o he cha ac e is ic cha (P)o an in eg al poin se P.
Lemma 4.3. An in eg al m-dimensional simplex S={ 0
0, 0
1,..., 0
m}wi h dis ance ma ix D= (di,j)∈
N o 0⩽i, j ⩽mand olm(S)6=0can be ans o med ia an isome y in o he coo dina es
0= (0,0,...,0),
1= (q1,1pk1,0,0...,0),
2= (q2,1pk1, q2,2pk2,0,...,0),
.
.
.
m= (qm,1pk1, qm,2pk2,...,qm,mpkm),
whe e kiis he squa e ee pa o oli( 0
0, 0
1,..., 0
i)2
oli−1( 0
0, 0
1,..., 0
i−1)2,qi,j ∈Q, and qj,j, kj6=0.
We ema k ha we always ha e k1=1. The connec ion be ween he kiand he cha ac e is ic
cha (P) = kis gi en by
cha (P) = cha (S) = k=squa e ee pa o
m
Y
i=1
ki.
Thus plane in eg al poin se s Pwi h a ional coo dina es a e exac ly hose wi h cha ac e is ic cha (P) =
1. Due o Conjec u e 3.2 plane in eg al poin se s o e Z2co espond o plane in eg al poin se s wi h
cha ac e is ic 1. So in p inciple he e is no need o ca e abou he coo dina es – his can s ill be done
a e wa ds.
The e is one u he ans o ma ion ha maps in eg al poin se s o e Z2on o in eg al poin se s
o e Z2: scaling by an in eg al ac o λ. One handicap o his mapping is ha he in e se mapping
may lead o non-in eg al poin se s. Ano he sho coming is ha maximal in eg al poin se s may be
mapped on o non-maximal in eg al poin se s. An example is gi en by he maximal in eg al poin se P=
0
0,3
0,0
4,3
4. I we scale i by a ac o o 2we ob ain 2·P=0
0,6
0,0
8,6
8
an in eg al poin se o e Z2which can be ex ended by he poin 3
4. In con as o his example he
in eg al poin se 3·P=0
0,9
0,0
12,9
12is maximal. One migh conjec u e ha o e e y
maximal in eg al poin se M he e exis s an in ege λ>1such ha λ·Mis also maximal.
5. MAXIMAL INTEGRAL POINT SETS WITH GIVEN CARDINALITY AND MINIMUM DIAMETER
F om he combina o ial poin o iew a na u al ques ion is o ask o he minimum possible diame e
dM(k, m)o a maximal in eg al poin se M⊂Zmo ca dinali y k. I such a poin se does no exis
MAXIMAL INTEGRAL POINT SETS OVER Z29
we se dM(k, m) = ∞. U ilizing he exhaus i e algo i hm desc ibed in Sec ion 3 we ha e ob ained he
esul s gi en in Table 1.
k dM(k,2)co esponding poin se
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 diame e s o maximal plane in eg al poin se s wi h gi en ca dinali y.
Clea ly we ha e dM(1, 2) = dM(2, 2) = ∞since a line l h ough wo di e en poin s P1and P2
wi h in eg al coo dina es and in eg al dis ance P1P2con ains an in ini e in eg al poin se P={P1+λ·
(P2−P1) : λ∈Z}as a subse . So he nex alue o de e mine is dM(3, 2). Whe he dM(3, 2)is ini e
had been an open ques ion o [3], which was answe ed in [12] by de e mining dM(3, 2) = 2066, – a
diame e ou o each o ou gene al exhaus i e algo i hm desc ibed in Sec ion 3. Bu i can be easily
adap ed o his pu pose. We al e Algo i hm 3.1 by omi ing igh -angled iangles, since hese ob iously
a e no maximal. Then we skip Algo i hm 3.4 and di ec ly un he e sion o Algo i hm 3.5 whe e we
sea ch o a ional ins ead o in eg al solu ions (xP, yP)o equa ion sys em (1). I we ha e ound he i s
solu ion (xP, yP) o a gi en iangle ∆we can immedia ely s op ou in es iga ions on ∆since i canno
be a maximal in eg al iangle. Using hese educ ions and skipping he ime consuming clique sea ch we
we e able o exhaus i ely sea ch o (s ongly) maximal in eg al iangles o e Z2wi h diame e a mos
15000 [12, 18]. The e a e exac ly 126 such examples. He e we lis he i s , wi h espec o hei diame e ,
en examples, whe e we gi e he edge leng hs and he coo dina es in minimal lis ep esen a ion, which
is unique in hese 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 he dis ance be ween ξsand ξ is gi en by |ξs−ξ |=1
R|xsy −x ys|. Since
ηsη = (xs+ysi)(x −y i) = xsx +ysy +i(x ys−xsy )
and
ηsη =iksik
Y
j=1
ω j+uj
jω j−uj
j
Y
j=1
ω j+wj
jω j−wj
j
=iks−k
Y
j=1
ω2 j+uj−wj
jω2 j−uj+wj
j
=R·iks−k
Y
j=1
ω j+uj−wj
jω j−uj+wj
j∈Z[i]
we ha e ha he dis ance be ween ξsand ξ is in eg al o e e y 1⩽s, ⩽2τ(R). Addi ionally we can
add he cen e o he ci cle o his poin se o ob ain an in eg al poin se o ca dinali y 2·τ(R)+ 1ha ing
a ional coo dina es. A e a sui able o a ion we can achie e in eg al coo dina es.
So le us ha e an example. We choose R=5·13 =65 and successi ely ob ain
ω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.
A e adding he o igin (0, 0)Tand applying a sui able o a ion and ansla ion we ob ain he maximal
in eg al poin se
P=0
0,0
−32,−30
40 ,−30
−72,−63
−16,−96
40 ,−96
−72,−126
0,−126
−32
in minimum coo dina e ep esen a ion.
Cons uc ion 6.12. Fo a gi en Rwhich has only p ime ac o s p ul illing p≡1(mod 4) he e exis s
an in eg al poin se ci cle(R)consis ing o 2·τ(R)poin s on a ci cle o adius R oge he wi h i s cen e ,
whe e τ(R)deno es he numbe o di iso s o R.
F om he abo e i is easy o deduce ha he 2τ(R)poin s on he ci cle all ha e pai wise e en dis ances
and ha he diame e o his poin se is gi en by 2R. Using his we can gi e ano he cons uc ion.
Cons uc ion 6.13. Fo a gi en Rwhich has only p ime ac o s p ul illing p≡1(mod 4) he e exis s
an in eg al poin se ]
ci cle(R)consis ing o 2·τ(R)poin s on a ci cle o adius R
2, whe e τ(R)deno es
he numbe o di iso s o R.
Conjec u e 6.14. The plane in eg al poin se s gi en by Cons uc ion 6.12 and Cons uc ion 6.13 a e
maximal.
We can gene alize he idea o Cons uc ion 6.13 in some way. Le be an a bi a y in ege , Rbe a
in ege ha ing only p ime ac o ul illing p≡1(mod 4), and P(R)be he in eg al poin se gi en by
Cons uc ion 6.12 wi h adius R. By P(R, )we deno e he poin se which a ises om P(R)by scaling he
poin se wi h a ac o 1
, his means di iding all dis ances by . Thus P(R, )is a poin se wi h pai wise
a ional dis ances and a ional coo dina es. Wi h his we can cons uc a g aph Gcon aining he poin s
o P(R, )as i s e ices. Two e ices o Ga e connec ed by an edge, i and only i he co esponding
MAXIMAL INTEGRAL POINT SETS OVER Z217
poin s ha e an in eg al dis ance in P(R, ). The maximal cliques Co Gco espond o in eg al poin se s
P(R, , C).
Cons uc ion 6.15. Fo a gi en Rwhich has only p ime ac o s p ul illing p≡1(mod 4)and a gi en
in ege he e exis in eg al poin se s ci cle(R, , C)consis ing o poin s on a ci cle o adius R
, whe e
Cis a maximal clique o he abo e desc ibed g aph. As an abb e ia ion we use ci cle(R, )ins ead o
ci cle(R, , C).
Conjec u e 6.16. Fo =8Cons uc ion 6.15 gi es maximal in eg al poin se s o ca dinali y τ(R).
7. MAXIMAL INTEGRAL POINT SETS OVER Z2WITH FURTHER CONDITIONS
k dM(k, 2)cons uc ion k dM(k, 2)cons uc ion
3=2066 ∆(2066, 1803, 505)26 ⩽112895 decompose 26·3·7, 5
4=5P1(3, 4) = ]
ci cle(5)27 ⩽2590 decompose 23·32
5=8P2(3, 4) = c ab(3, 4)28
?
.203125 ]
ci cle 56·13
=c ab(4, 3)29 ⩽1798 decompose 22·3·5
6=25 ]
ci cle 5230 ⩽105625 ]
ci cle 54·132
7=30 c ab (8, 6, 15)31
?
.211250 ci cle 54·132
8=65 ]
ci cle (5·13)32 ⩽27625 ]
ci cle 53·13 ·17
9=130 ci cle (5·13)33 ⩽55250 ci cle 53·13 ·17
10 ⩽625 ]
ci cle 5434 ⩽142295 decompose 23·3·7·11, 5
11 =70 decompose 22·335 ⩽18430 decompose 26·3
12 =325 ]
ci cle 52·1336 ⩽40625 ]
ci cle 55·13
13 ⩽650 ci cle 52·1337 ⩽10366 decompose 24·32
14 ⩽15625 ]
ci cle 5638
?
.571535 decompose 24·33·7, 5
15 ⩽8190 decompose 2739
?
.4816895 decompose 29·3·7, 5
16 ⩽1105 ]
ci cle (5·13 ·17)40 ⩽138125 ]
ci cle 54·13 ·17
17 =286 decompose 23·341 ⩽73726 decompose 27·3
18 ⩽4225 ]
ci cle 52·13242
?
.677375 decompose 26·32·7, 5
19 ⩽8450 ci cle 52·13243
?
.4573799 decompose 23·32·5·7·11, 17
20 ⩽8125 ]
ci cle 54·1344
?
.6614998 decompose 24·32·52·7, 13
21 ⩽16250 ci cle 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 ]
ci cle 52·13 ·1748
?
.160225 ]
ci cle 52·13 ·17 ·29
25 ⩽11050 ci cle 52·13 ·1749
?
.320450 ci cle 52·13 ·17 ·29
50
?
.4064255 decompose 27·32·7, 5
TABLE 2. Bes known cons uc ions o maximal in eg al poin se s o e Z2in a bi-
a y posi ion.
In Table 2 we ha e summa ized he cons uc ions yielding he smalles diame e o a maximal in eg al
poin se o e Z2. Some o he alues dM(k, 2)could be de e mined exac ly by an exhaus i e sea ch, bu
18 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
o mos alues o kwe only ha e uppe bounds (and 301 as lowe bound). In some cases, deno ed by
?
.,
we we e no able o check he maximali y o he cons uc ed poin se s, since hei diame e was oo la ge.
Looking a Table 2 we obse e, ha he cons uc ions o c abs (Cons uc ion 6.6 and Cons uc ion 6.10)
a e e y domina ing. The esul ing poin se s con ain n−2and n−1collinea poin s ou o npoin s,
espec i ely. So i may be in e es ing o s udy maximal in eg al poin se s o e Z2, whe e no h ee poin s
a e collinea . We also say, ha a poin se is in semi-gene al posi ion, i no h ee poin s a e collinea . By
dM(k, 2)we deno e he minimum possible diame e o hese poin se s. We can check o his u he
condi ion, ha no h ee poin s a e collinea , by applying Lemma 6.8. Using he me hods and algo i hms
desc ibed in his a icle, we we e able o ob ain some exac alues and some uppe bounds o dM(k, 2).
The esul s a e summa ized in Table 3. We would like o ema k ha we addi ionally ha e he lowe
bounds dM(k, 2)⩾5525 o k∈{11, 13, 14, 15, 17}and dM(k, 2)⩾10001 o k⩾19,k6=20, 24.
k dM(k, 2)cons uc ion k dM(k, 2)cons uc ion
3=2066 ∆(2066,1803,505)27
?
.305218 ci cle(52·132·172,8)
4=5P1(3,4)= ^
ci cle(5)28
?
.203125 ^
ci cle(56·13)
5=120 see Figu e 5 29
?
.9311389618298531250 ci cle(528,8)
6=25 ^
ci cle(52)30 ⩽105625 ^
ci cle(54·132)
7=925 see Figu e 6 31
?
.232784740457463281250 ci cle(530,8)
8=65 ^
ci cle(5·13)32 ⩽27625 ^
ci cle(53·13·17)
9=1045 see Figu e 7 33
?
.412343750 ci cle(510·132,8)
10 =625 ^
ci cle(54)34
?
.152587890625 ^
ci cle(516)
11
?
.2434375 ci cle(510,8)35
?
.111562500 ci cle(56·134,8)
12 =325 ^
ci cle(52·13)36 ⩽71825 ^
ci cle(52·132·17)
13
?
.60859375 ci cle(512,8)37 ?
.3637261569647863769531250 ci cle(536,8)
14 ⩽15625 ^
ci cle(56)38
?
.3814697265625 ^
ci cle(518)
15 ⩽26390 ci cle(54·132,8)39
?
.10314771205 ci cle(512·132,8)
16 =1105 ^
ci cle(5·13·17)40 ⩽138125 ^
ci cle(54·13·17)
17 ?
.38037109375 ci cle(516,8)41 ?
.2273288481029914855957031250 ci cle(540,8)
18 =4225 ^
ci cle(52·132)42
?
.2640625 ^
ci cle(56·132)
19 ?
.950927734375 ci cle(518,8)43 ?
.56832212025747871398925781250 ci cle(542,8)
20 =8125 ^
ci cle(54·13)44
?
.126953125 ^
ci cle(510·13)
21
?
.659750 ci cle(56·132,8)45
?
.7630450 ci cle(54·132·172,8)
22
?
.9765625 ^
ci cle(510)46
?
.2384185791015625 ^
ci cle(522)
23 ?
.595928935571106 ci cle(522,8)47 ?
.35520132516092419624328613281250 ci cle(546,8)
24 =5525 ^
ci cle(52·13·17)48
?
.160225 ^
ci cle(52·13·17·29)
25
?
.4462500 ci cle(54·134,8)49
?
.18854062500 ci cle(56·136,8)
26
?
.244140625 ^
ci cle(512)50
?
.17850625 ^
ci cle(54·134)
TABLE 3. Bes known cons uc ions o maximal in eg al poin se s o e Z2in semi-
gene al posi ion.
MAXIMAL INTEGRAL POINT SETS OVER Z219
We would like o ha e a close look on he smalles known examples o maximal in eg al poin se s in
semi-gene al posi ion consis ing o an odd numbe o poin s. Fo ca dinali y 5 he wo smalles poin se s
wi h espec o he diame e a e gi en in minimum coo dina e ep esen a ion by
0
0,0
−78,−20
21 ,−20
−99,−52, −39and 0
0,0
−80,−45
28 ,−45
−108,−96
−40,
see Figu e 5 o a d awing o he i s poin se . Bo h poin se s consis o ou poin on a ci cle Co
adii 29·101
40 and 13·53
10 , espec i ely. In each case he i h poin does no lie on his ci cle C, bu he line
h ough his poin and he cen e o Cis a symme y axis o he poin se .
x x
x
x
x
FIGURE 5. The smalles maximal in eg al poin se o ca dinali y 5in semi-gene al posi ion.
Fo ca dinali y 7 he wo smalles examples a e gi en 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 Figu e 6 o a g aphical ep esen a ion o he i s example. The geome ic shape o he co esponding
wo poin se s is simila o he case o ca dinali y 5. In each case 6poin s a e si ua ed on a ci cle Co
adii 52·37
2and 3·52·37
2, espec i ely. Again we ha e he symme y axis h ough he se en h poin and he
cen e o C.
u
uu
u
u
u
u
FIGURE 6. The smalles maximal in eg al poin se o ca dinali y 7in semi-gene al posi ion.
20 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
Fo ca dinali y 9 he wo smalles examples a e gi en 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 Figu e 7 o a g aphical ep esen a ion o he i s example. He e in bo h examples all nine poin s a e
si ua ed o ci cles o adii 52·132
8and 52·132
6, espec i ely. They bo h can be ob ained using Cons uc ion
6.15.
u
u
u
u
u
u
u
u
u
FIGURE 7. The smalles maximal in eg al poin se o ca dinali y 9in semi-gene al posi ion.
Now we obse e ha he cons uc ions based on ci cles, Cons uc ion 6.12, Cons uc ion 6.13, and
Cons uc ion 6.15, a e e y domina ing in his con ex . The nex na u al s ep is o also o bid ou poin s
on a ci cle. I no h ee poin s a e on a line and no ou poin s on a ci cle we speak o gene al posi ion.
By ˙
dM(k, 2)we deno e he minimum possible diame e o a maximal plane in eg al poin se in gene al
posi ion o e Z2. Wi hou he maximali y condi ion hese poin se s a e also known as k2-clus e [22]. As
we canno apply ou mos success ul cons uc ions based on c abs and ci cles in his case, examples a e
sca ce. Fo he check whe he ou poin s a e si ua ed on a ci cle we ha e a well known c i e ion simila
o Lemma 6.8:
Lemma 7.1. Fou poin s (x1, y1),(x2, y2),(x3, y3),(x4, y4)in R2a e si ua ed on a ci cle i and only
i
x1y1x2
1+y2
11
x2y2x2
2+y2
21
x3y3x2
3+y2
31
x4y4x2
4+y2
41
=0
holds.
In Table 4 we ha e summa ized ou knowledge on ˙
dM(k, 2). Fo he lowe bound ˙
dM(7, 2)> 599000
we e e o [18]. Whe he ˙
dM(7, 2)is ini e (e en i we d op he maximali y condi ion) is an open
MAXIMAL INTEGRAL POINT SETS OVER Z221
FIGURE 8. The smalles maximal in eg al poin se o ca dinali y 4in gene al posi ion.
FIGURE 9. The smalles maximal in eg al poin se o ca dinali y 5in gene al posi ion.
FIGURE 10. The smalles maximal in eg al poin se o ca dinali y 6in gene al posi ion.
p oblem, see [7, 22]. I we d op he maximali y condi ion and he condi ion on he in eg ali y o he
coo dina es (in o he wo ds cha ac e is ic one), hen e y ecen ly wo such examples we e ound, see
[14]. The smalles example o k=6is indeed he smalles in eg al poin se o cha ac e is ic one in
gene al posi ion wi h ca dinali y 6. We would also like o gi e he coo dina es o he second smalles
examples. Fo ca dinali y 4we ha e
0
0,0
−69,−20
−21,−92
0,
o ca dinali y 5we ha e
0
0,0
−153,−60
144,−140
−48 ,−176
57 ,
22 ANDREY RADOSLAVOV ANTONOV AND SASCHA KURZ
and o ca dinali y 6we ha e
0
0,−135
−1008,420
1008,735
−392,1155
616 ,1290
1624.
k=|P| ˙
dM(k, 2)cons uc ion
3=2066 ∆(2066, 1803, 505)
4=87 0
0,0
−33,−16
30 ,44
−33, see Figu e 8
5=165 0
0,0
−72,−35
12 ,64
−120,−90
−120, see Figu e 9
6=1886 0
0,0
−828,−448
−414,−720
132 ,−1260
−1023,−1840
−414 ,
see Figu e 10
7> 599000
TABLE 4. Bes known cons uc ions o maximal in eg al poin se s o e Z2in gene al posi ion.
8. CONCLUSION AND OUTLOOK
We ha e desc ibed se e al cons uc ions o in eg al poin se s o e Z2wi h gi en ca dinali y ha ul ill
some u he p ope ies. Al hough he maximali y o he esul ing in eg al poin se s canno be gua an eed
so a , we conjec u e hem o be in many cases. We ha e desc ibed e icien algo i hms o exhaus i e
gene a ion o maximal in eg al poin se s o e Z2and o es ing he maximali y o a gi en in eg al poin
se . Some exac alues o minimum diame e s o gi en ca dinali ies could be ob ained and se e al alues
a e cons uc ed as uppe bounds and conjec u ed o be he exac alues.
I emains a ask o p o e he maximali y o poin se s esul ing om some o ou cons uc ions in
gene al. Clea ly simila p oblems could be conside ed in highe dimensions.
REFERENCES
1. N. H. Anning and P. E d˝
os, In eg al dis ances, Bull. Ame . Ma h. Soc. 51 (1945), 598–600.
2. A. An ono and M. B anche a, Algo i hm o inding maximal Diophan ine igu es, Sp ing Con e ence 2007 o he Union o
Bulga ian Ma hema icians, 2007.
3. S. Dimie and K. Ma ko , Gauss In ege s and Diophan ine Figu es, Ma hema ics and Ma hema ical Educa ion 31 (2002),
88–95, a Xi :ma h.NT/0203061 1 7 Ma 2002.
4. P. E d˝
os, In eg al dis ances, Bull. Ame . Ma h. Soc. 51 (1945), 996.
5. J. F icke, On he on simplices and in ege embedding, p ep in (2001).
6. R. E. Fulle on, In eg al dis ances in banach spaces, Bull. Ame . Ma h. Soc. 55 (1949), 901–905.
7. R. K. Guy, Unsol ed p oblems in numbe heo y. 2nd ed., Unsol ed P oblems in In ui i e Ma hema ics. 1. New Yo k, NY:
Sp inge - Ve lag. x i, 285 p., 1994.
8. B. Haible and R. K eckel, Cln, a class lib a y o numbe s, 2005, h p://www.ginac.de/CLN/.
9. H. Ha bo h, In eg al dis ances in poin se s, Ka l de G osse und sein Nachwi ken. 1200 Jah e Kul u und Wissenscha in
Eu opa. Band 2: Ma hema isches Wissen. Tu nhou : B epols (P. L. Bu ze e al., eds.), 1998, pp. 213–224.
10. H. Ha bo h, A. Kemni z, and M. M¨
olle , An uppe bound o he minimum diame e o in eg al poin se s, Disc e e Compu .
Geom. 9(1993), no. 4, 427–432.
11. M. Kie maie and S. Ku z, Inclusion-maximal in eg al poin se s in a ine planes o e ini e ields, (submi ed).
12. A. Kohne and S. Ku z, A no e on E d¨
os-Diophan ine g aphs and Diophan ine ca pe s, Ma h. Balkanica 21 (2007), no. 1-2,
1–5.
13. A. Kohne and S. Ku z, In eg al poin se s o e Zm
n, Disc e e Appl. Ma h. ( o appea ).
14. T. K eisel and S. Ku z, The e a e in eg al hep agons, no h ee poin s on a line, no ou on a ci cle, Disc e e. Compu . Geom.
( o appea ).
15. S. Ku z, In eg al poin se s o e ini e ields, (submi ed).
MAXIMAL INTEGRAL POINT SETS OVER Z223
16. S. Ku z, Kons uk ion und Eigenscha en ganzzahlige Punk mengen, Ph.D. hesis, Bay eu h. Ma h. Sch . 76. Uni e si ¨
a
Bay eu h, 2006.
17. , On he cha ac e is ic o in eg al poin se s in Em, Aus alas. J. Comb. 36 (2006), 241–248.
18. S. Ku z, On he gene a ion o he onian iangles, (in p epa a ion).
19. S. Ku z and R. Laue, Uppe bounds o in eg al poin se s, Aus alas. J. Comb. 39 (2007), 233–240.
20. S. Ku z and A. Wasse mann, On he minimum diame e o plane in eg al poin se s, A s Combin. ( o appea ).
21. S. Niskanen and P. R. J. ¨
Os e g˚
a d, Clique use ’s guide, e sion 1.0, Tech. Repo T48, Communica ions Labo a o y, Helsinki
Uni e si y o Technology, Espoo, Finland, 2003.
22. L. C. Noll and D. I. Bell, n-clus e s o 1<n<7, Ma h. Compu . 53 (1989), no. 187, 439–444.
ANDREY RADOSLAVOV ANTONOV, DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CHEMICAL TECHNOLOGY AND
METALLURGY - SOFIA, BULGARIA
E-mail add ess:[email p o ec ed]
SASCHA KURZ, DEPARTMENT OF MATHEMATICS, PHYSIC AND INFORMATICS, UNIVERSITY OF BAYREUTH, GERMANY
E-mail add ess:[email p o ec ed]