From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Lattice Problem (Triangles)
Date: 8 Oct 1997 17:00:44 GMT
In article <3435C701.7BF9@cruzio.com>, KD wrote:
>How many triangles can be formed on an 8 x 8 lattice (like a geoboard)
>such that the vertices of each triangle lie on lattice points? How many
>triangles can be formed on an an n x n lattice?
In article <61e5vk$q56$1@gannett.math.niu.edu>,
Dave Rusin wrote:
>More interesting is to ask for the number of _congruence classes_ of
>triangles, or _similarity classes_ of triangles. or something. I don't
>know the answer offhand, although for a general n I believe the
>answers is on the order of n^4. See
> http://www.math.niu.edu/known-math/95/integral.tris
[URL updated 1999/01 -- djr]
I should add that the number of congruence classes of triangles with
vertices on an NxN grid is easy to compute for small N.
Lemma: Every such triangle is congruent to one with a vertex at the origin
Proof: Label the points "topmost", "bottommost", "leftmost", and
"rightmost" as appropriate (multiple labels for ties). Three points,
4 awards, so at least one double winner. Translate that point to the
appropriate corner. Rotate by quarter turns. QED
Remark: We only use conjugacy under a _subgroup_ of the Euclidean group here.
For each such triangle we compute the squares A,B,C of the side-lengths
a,b,c; the numbers A, B, C are positive integers, and the triangle is
degenerate ( (+-)a + (+-)b + (+-)c = 0 ) iff A^2+B^2+C^2=2(AB+BC+CA).
(Proof: multiply four of those equations together). Thus we can perform a
search for congruence classes using integer arithmetic:
TriangleSet = { }
For (i,j) in {0, 1, ..., N}^2 do
For (k,l) in {0, 1, ..., N}^2 do
let A=i^2+j^2, B=k^2+l^2, C=(i-k)^2+(j-l)^2
if A^2+B^2+C^2 <> 2(AB+BC+CA) then
( Sort S={A,B,C} )
if S is not in TriangleSet, insert it (in lex order)
end if
end do
end do
display cardinality of TriangleSet
Here's what I get for the first few N:
1, 8, 29, 79, 172, 333, 587, 963, 1494, 2228, 3195, 4455
I looked for this sequence in Sloane's sequence server, but didn't
find a match. (I suppose it will now be added to the Handbook).
Is it possible to compute this number without enumerating the
elements of TriangleSet? Maybe, but I did not pursue the details,
as it seems fairly intricate.
Clearly TriangleSet has at most (N+1)^4 elements. This is
an over-count, as the two pairs of points {(i,j), (k,l)} and
{(k,l}, (i,j)} give the same triangle, and the pair
{(j,i), (l,k)} gives a congruent triangle. (If you want to track this
carefully, you'll need to pay attention to triangles of the form
{(i,j), (j,i)}. ) So we have an upper bound of (N+1)^4/4 or so.
Also note that if {(i,j),(k,l)} is a triangle for which (in the proof
of the lemma) there are two points each having two labels, then
the pair {(i,j), (|i-k|,|j-l|)} denotes a congruent triangle.
(Triangles with multiple ties will correspond to several pairs of points.)
In this way one could probably compute precisely the number of
equivalence classes of triangles, where two triangles are equivalent if
they are in the same orbit under the action of the various subgroups of
the Euclidean group. Candidates for which this might succeed include
the group T of translations
the subgroups S of the (dihedral) group of 8 symmetries of the square
the group generated by T and any of these S
But determining in advance the correct number of congruence classes is
a bit trickier. This number is less than the number of equivalence
classes under , since for example the triangle with vertices
at (4,3) and (7,4) is congruent to the one with vertices at
(5,0) and (8,1) but not by using symmetries in this restricted subgroup.
Determination of such 'skew' congruences suggests some algebraic
number theory, as I indicated in the previous post. I suspect this will
reduce the number of equivalence classes by rather less than O(N^4).
One could go further and look for equivalence classes under the
still larger group which includes dilations, that is, look for similarity
classes of triangles. One need only insert an extra step in the algorithm,
dividing (A,B,C) by their greatest common factor before sorting
and checking for inclusion.
dave
==============================================================================
From: sequences-reply@research.att.com
To: rusin@math.niu.edu
Date: Wed, 8 Oct 1997 10:56:18 -0400 (EDT)
Subject: [none]
Matches (up to a limit of 10) found for 1 8 29 79 172 333 587 :
Even though there are 28,000 sequences in the table now, at least
one of yours is not there! Please send it to me (njas@research.att.com)
and I will (probably) add it! Include a brief description. Thanks!
References (if any):
o Dec '96: Take a look at my web page which does lookups "online"! Go to:
http://www.research.att.com/~njas/sequences
o The whole sequence table is also visible there.
o For more sequences see "The Encyclopedia of Integer Sequences"
by N. J. A. Sloane & S. Plouffe, Academic Press, ISBN 0-12-558630-2.
o IF THE SEQUENCE YOU LOOKED UP WAS NOT IN THE TABLE,
PLEASE SEND IT TO ME AT njas@research.att.com !
o There is a second sequence server (superseeker@research.att.com)
that tries hard to find an explanation. Only 1 request per person
per hour please.
o Key: %I = ID line: Annnnnn = absolute catalogue number of sequence,
Mnnnn = number in the Encyclopedia,
%S, %T, %U = beginning of sequence, [%V,%W,%X = signed version]
%N = name, %R = references, %Y = cross-references, %A = authority,
%F = formula, %K = keywords, %H = URL address of source, %D = details
of references, %p = Maple; %t = Mathematica; %o = other computer languages;
%O = offset = [a,b]: a is subscript of first entry, b gives the
position of the first entry >= 2.
References to journals give volume, page, year.
o If the word "lookup" does not appear you will be sent the help file.
Sequentially yours, The On-Line Encyclopedia of Integer Sequences,
N. J. A. Sloane, AT&T Research, Florham Park NJ 07932-0971 USA njas@research.att.com
==============================================================================
[ I immediately sent this response: (I have updated the URL below, 1999/01) ]
==============================================================================
I didn't see a match to the following sequence:
1, 8, 29, 79, ...
This is the number of congruence classes of triangles which can be drawn
using the lattice points in an NxN grid for vertices. If I've searched
correctly the next few terms are
1, 8, 29, 79, 172, 333, 587, 963, 1494, 2228, 3195
I will store some information at this URL if you think this to be
appropriate data for the handbook:
http://www.math.niu.edu/~rusin/known-math/97/triangles.grid
dave
==============================================================================
Herewith some additional comments not posted. Last update 1997/10/10
==============================================================================
We can handle similarity as well as congruence with this Maple program:
N:=3:
# repeat from here ad nauseum
TriangleSet:={}:
SimSet:={}:
for i from 0 to N do
for j from 0 to N do
for k from 0 to N do
for l from 0 to N do
A:=i^2+j^2:B:=k^2+l^2:C:=(i-k)^2+(j-l)^2:
if A^2+B^2+C^2 <> 2*(A*B+B*C+C*A) then
x:=sort([A,B,C]):
TriangleSet:=TriangleSet union {x}:
y:=gcd(A,B):y:=gcd(C,y):
x:=[x[1]/y,x[2]/y,x[3]/y]:
SimSet:=SimSet union {x}:
fi:od:od:od:od:
nops(TriangleSet);
nops(SimSet);
evalf("/"");
N:=N+1;
The output data are
N 1 2 3 4 5 6 7 8 9
sim 1 6 20 55 119 229 402 667 1019
cong 1 8 29 79 172 333 587 963 1494
% 100 75 68.9 69.6 69.1 68.8 68.5 69.2 68.2
N 10 11 12 13 14 15 16 17 18
sim 1536 2216 3049 4168 5546 7203 9278 11755 14597
cong 2228 3195 4455 6050 8032 10481 13464 17014 21235
% 68.9 69.4 68.4 68.9 69.0 68.7 68.9 69.1 68.7
The number of similarity classes is a remarkably constant fraction of the
number of congruence classes. (I suspect each of them can be given as
quartic polynomials in N with an error which is perhaps O(N^2), say, so
it's not surprising that a limit fraction exists, but I didn't expect the
limit fraction to be attained so quickly.)
==============================================================================