From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: equal or similar triangles
Date: 15 Nov 1995 21:31:24 GMT

In article <47talf$g13@apopi.u-strasbg.fr>,
SHAHBAZKIA Hamid <hamid@steinway.u-strasbg.fr> wrote:
>I am looking for a formal methode which tells  how many non equal or non  
>similar triangles there are in a n*n grid.

[Poster wants to enumerate equivalence classes of triples in a portion of
the standard lattice --that is,   T \subset (Z^2 \intersect [0,n]^2 )^3 --
under the usual equivalence relations of congruence or similarity.]

You have asked this question before. I think the lack of responses indicates
that others have noticed what I notice: there is some hard number theory at
work here. I wish I could be more helpful, but I think getting accurate
formulas will be equivalent to making precise statements about prime
distributions and so on, which I don't think are known. The best I can do
without spending a lot of time on it is to say that there are  O(n^4)
equivalence classes of triangles, whether you use similarity, congruence,
or just translation-equivalence.

Let me just give two illustrations of the difficulties you will encounter.

                ********************************

Surely a total count of triangles (no equivalence relation used) should
be easy, right? A triangle is an unordered triple of 
distinct points, so there are  ( (n+1)^2   choose  3 )  of them. 
Unfortunately, this is already incorrect -- presumably you intend to
disqualify degenerate triangles, so we need to subtract the number of
triples of collinear points. How many are there? You simply specify the
two endpoints of the line segment -- ( (n+1)^2  choose  2 )  choices --
and then count the number of intermediate points. If the endpoints are
(x1,y1) and (x2,y2), the intermediate points are  (tx1+(1-t)x2, ty1+(1-t)y2)
with  t  between  0  and  1; the only stipulation is that these coordinates 
be integral. This is accomplished by taking  t=p/q  where  0<p<q  and
q  any common divisor of  (x1-x2) and (y1-y2), so the number of such
intermediate points is  -1+gcd(x1-x2, y1-y2). Here's the number of such
collinear triples for the first few values of  n:

n=1  2   3    4    5    6     7     8     9    10     11     12
#=0  8  44  152  372  824  1544  2712  4448  6992  10332  15072

It's easy to see the number of such collinear triples is at most 
(1/2)(n^5)(1+o(1)), but no polynomial of degree  5  or less matches these
data, so the number of collinear triples will have to depend in a
more subtle (number-theoretic) way on  n. Sloane's sequence matcher
provided a citation to Guy and Kelly, Canad. Math. Bull. 11 (1968) 527-531
and a couple of other hits. I take it this is called the "no-3-in-line"
problem.

                ********************************

Now let's think about counting congruence classes of triangles. One may
show that every triangle is congruent to one with a vertex at the origin.
Very well, let's consider which triangles in the lattice  Z^2  with one
vertex at the origin are congruent. Actually, I'll split up the equivalence
classes into as many as  6  parts by looking to see what triangles at
the origin are congruent to a given one with a congruence which does
not permute the vertices (i.e., fixes origin and orientation). Such a 
congruence is necessarily a rotation.

One may identify the points (x,y) in  Z^2  with the Gaussian integers  x+iy.

Lemma. There is a rotation carrying the triangle with vertices 0, v,
and w to the triangle with vertices at  0, v', and w' (in that order) iff
	v=v0 r s,  w=w0 r s,  v'=u v0 rbar s,  and w'=u w0 rbar s
for some Gaussian integers  v0, w0, r, and s  and a unit  u (which must be
1, -1, i, or -i), such that  v0 and w0  are relatively prime, and
r and rbar are relatively prime.

Proof. If such numbers exist, then multiplication by  u(rbar/r)  is a
rotation of the plane which carries the one triangle to the other.

Conversely, if such a rotation exists, then  v  and  v'  have the same
length; so do  w  and  w'. 
	Now, the length of a Gaussian integer is also its norm in the
algebraic-number-theoretic sense. So we will consider the factorization
of  v  and  v'  into primes.
	Here you need to know that the ring  Z[i]  of Gaussian integers
is a unique factorization ring, and you need to know what the primes
and units in that ring are. The units are just the four powers of  i.
The primes are of three forms: (1+i) is the only prime dividing  2+0i.
Some ordinary primes  p+0i  are still prime in this ring (namely, those
p=3 mod 4); the others decompose into precisely two conjugate primes
(e.g. 5=(2+i)(2-i) ). If we fix one prime  P  dividing each rational
prime  p  then we may write a prime factorization of  v
	v = unit (1+i)^a Prod p^(e_p) Prod P^(f_p) Pbar^(g_p)
which reflects the presence of units and distinguishes the three kinds
of primes. Note that this gives the prime factorization of  Norm(v)  as
	N(v)=2^a Prod p^(2e_p) Prod p^(f_p+g_p).
In particular, since  N(v)=N(v')  we must have  a=a', e_p=e'_p, and
f_p+g_p=f'_p+g'_p. Thus if  d  is the GCD  of  v  and  v', we see
d  must contain all the powers of  2  and the primes of the first sort
which occur in  v  (and  v'); moreover if we let  r = v/d  and
r' = v'/d, then r and r' are relatively prime and conjugate
up to a unit (e.g.  if  v=P^2 Pbar  and  v'=i Pbar^3, then  r=P^2  and 
r'=i Pbar^2.) Moreover, v'  is obtained from  v  by multiplying by
(r'/r), which is of length  1, so that this operation is a rotation.

Thus the original rotation and this new one agree on their action on
the nonzero point  v, and hence they are equal.

In particular, this requires  w'= (r'/r) w, i.e.  r w' = r' w.
Using unique factorization and the relative primality of  r  and  r',
it's then easy to see  w=r s and  w'=r' s  for some  s  (namely
s=gcd(w, w'), up to units.)

So both  v  and  w  are divisible by  r;  if  r1  is the greatest
common divisor of the two, let  v0=v/r1, w0=w/r1, and  s=r1/r. Then
it is easy to check that the claims of the lemma are met.  //


In a similar way one may show that the triangles determined by 0, v, w
and by  0, v', w'  are similar (with similarity pairing the vertices shown)
iff there are Gaussian integers  v0, w0, r, s  with  v0 and w0  relatively
prime such that  v=v0 r, w=w0 r, v'=v0 s, w'=w0 s. Thus the equivalence
classes of triangles (in this sense) are counted by enumerating the ordered
pairs of relatively prime Gaussian integers lying in the  n x n  square.

(Well, roughly, anyway -- you have to toss in a count of the pairs of
relatively prime numbers  (v0, w0)  with  v0  in the square but  w0  in
one of the adjoining squares and having the property that some multiple of
this pair lies in one quadrant and still has small enough magnitude.
I'll ignore these pairs for now.)

Well, there are  (n+1)^4  ordered pairs of Gaussian integers in the square.
What fraction of them are relatively prime? For large enough  n  you can
estimate this heuristically as follows: For each Gaussian prime  p , the
probabilty that both integers are _not_ divisible by  p  is about  
1-1/Norm(p)^2. For primes small relative to  n, these divisibility conditions 
are roughly independent, so that the fraction of pairs not divisible by any 
of the small primes is about  Prod(1-1/Norm(p)^2). This product converges,
that is, the large primes tend to have a very small effect on the likelihood
of selecting relatively prime pairs. Indeed, the inverse of this product is
Prod(Sum 1/Norm(p)^2r)) = Sum(1/Norm(n)^2), the zeta function of this
number field, at s=2.  (This is roughly the argument used to show that the
probability of selecting two relatively prime integers is about  6/pi^2,
but I don't know the values of the zeta function of this field.)
Whatever this constant C  is, we see that there are roughly  (1/C)n^4
pairs of relatively prime Gaussian integers in the square, meaning about
that many classes of similar triangles.

I don't think it impossible to do a careful analysis which gives 
asymptotic formulas for the number of equivalence classes of triangles
(in any of these senses), but I do foresee that it will be a lot of
work, and not be accurate enough to determine the exact number except
for the smallest values of  n, which may be enumerated by hand.

dave

==============================================================================
[Evidently this next draft was neither posted nor emailed. -- djr]
==============================================================================
From: rusin@math.niu.edu (Dave Rusin)
Date: 14 Nov 1995 22:57 CST [from file's timestamp]
Newsgroups: sci.math
Subject: Re: equal or similar triangles
Cc: hamid@steinway.u-strasbg.fr 

In article <47talf$g13@apopi.u-strasbg.fr>,
SHAHBAZKIA Hamid <hamid@steinway.u-strasbg.fr> wrote:
>I am looking for a formal methode which tells  how many non equal or non  
>similar triangles there are in a n*n grid.

[Poster wants to enumerate equivalence classes of triples in a portion of
the standard lattice --that is,   T \subset (Z^2 \intersect [0,n]^2 )^3 --
under the usual equivalence relations of congruence or similarity.]

You have asked this question before. I think the lack of responses indicates
that others have noticed what I notice: there is some hard number theory at
work here.

Certainly there are about  ((n+1)^2 choose 3 )  triangles in this portion of 
the lattice, roughly  n^6/6. But there seems to be no reasonable way to count
the number of triangles in each equivalence class, nor to find a "canonical"
representative of each equivalence class. As far as I can tell, at least
one of those would be necessary if you wanted to count the equivalence
classes.

Let me clarify by trying to count the number of equivalence classes of
triangles with a few other notions of equivalence. We can write T1 ~ T2
if there is a motion  G  with  G(T1)=T2, where  G  comes from
	(a) G={1}  (no equivalences except identity)
	(b) G=Z^2  (translations)
	(c) G=(Z^2).D4 (translations and rigid permutations of the 
			whole square)
	(d) G=O(2,R) (translations and all rotations and reflections)
	(e) G=GL(2,R) (same, plus dilations)
(Here 'and' is taken to mean the additional motions are used as generators,
so of course composites of various motions are allowed.) You evidently
intended to count the orbits under groups  (d)  or  (e).

Surely   (a)  would be easy, right? A triangle is an unordered triple of 
distinct points, so there are  ( (n+1)^2   choose  3 )  of them. 
Unfortunately, this is already incorrect -- presumably you intend to
disqualify degenerate triangles, so we need to subtract the number of
triples of collinear points. How many are there? You simply specify the
two endpoints of the line segment -- ( (n+1)^2  choose  2 )  choices --
and then count the number of intermediate points. If the endpoints are
(x1,y1) and (x2,y2), the intermediate points are  (tx1+(1-t)x2, ty1+(1-t)y2)
with  t  between  0  and  1; the only stipulation is that these coordinates 
be integral. This is accomplished by taking  t=p/q  where  0<p<q  and
q  any common divisor of  (x1-x2) and (y1-y2), so the number of such
intermediate points is  -1+gcd(x1-x2, y1-y2). Here's the number of such
collinear triples for the first few values of  n:

n=1  2   3    4    5    6     7     8     9    10     11     12
#=0  8  44  152  372  824  1544  2712  4448  6992  10332  15072

It's easy to see the number of such collinear triples is at most 
(1/2)(n^5)(1+o(1)), but no polynomial of degree  5  or less matches these
data, so the number of collinear triples will have to depend in a
more subtle (number-theoretic) way on  n. Sloane's sequence matcher
provided a citation to Guy and Kelly, Canad. Math. Bull. 11 (1968) 527-531
and a couple of other hits.

So perhaps it is easier if we allow degenerate triangles in our
count. If so, then we have enumerated the classes in (a).

Now let's move on to another equivalence relation, say (b). Here we can
easily find an triangle in each equivalence class. Each triangle is
equivalent to precisely one in which there is a point on the bottom
row and a point on the left edge. To enumerate these, though, it
appears we need to consider two cases. If the two points just described
are equal, then there is a point at the origin. In this case, we have
precisely the equivalence classes of these triangles: (0,0), (x,y), and
(z,w) -- ( (n+1)^2-1  choose  2 )  such triangles. (This glosses over
the collinearity issue.) Otherwise, our triangle has two points
(x,0) and (0,y) with  x, y >0, and a third point  (z,w) different from
these and from the origin. This appears to give  n^2( (n+1)^2-3 ) triangles,
although if  z  or  w  is zero, we will create a triangle which will
be counted twice.

==============================================================================
[This next was also evidently neither posted nor mailed.
[Timestamp: 15 Nov 1995 08:53 CST]
==============================================================================
Now let us consider the equivalneece classes under the group  Z^2.C_4
of translations and 90-degree rotations. There are several quantities
asociated with a triangle which are preserved under this group. One is
what I might call the _collection of inverse slopes_ of the three
sides: to a side of slope  m  we associate the number  m  if |m|<=1 and 
1/m  if |m|>1; vertical and horizontal lines are assigned the number 0.
Thus a triangle determines a set of three numbers {m1, m2, m3} each in
the interval [-1,1]; these numbers do not change upon translation and
90-degree rotation, that is, they are functions of equivalence classes.

Note that a non-degenerate triangle cannot have the collection be {0,0,0}.
It can have form {0,0,m} -- this happens iff there are two sides parallel to 
the axes. In this case a unique rotation and translation will move their
intersection to the origin, so that the triangle is {(0,0), (a,0), (0,b)}
with a>0, b>0. Thus I count n^2 equivalence classes of form {0,0,m}.

If a triangle has form {0, m1, m2} then there is a unique rotation
which gives it a horizontal side "south" of the triangle. If the angle
to the left of this base is acute, there is a unique translation taking
the triangle to  {(0,0), (a,0), (x,y)} where a, x, y > 0: n^3 triangles. 
If instead the angle at the left is obtuse, rotate 90 degrees clockwise
and follow by the rotation taking the triangle to {(0,0), (0,a), (x,y)}
where a>0 and this time we must have x>0 and y>a. Summing over the
choices of  a  gives n^2(n-1)/2 more triangles.

If the triangle has form {m1, m2, m3} in which the  m_i  are not all of
the same sign, then there is a unique rotation making two of the  m_i  
positive and the triangle to the "northeast" of the intersection the
corresponding lines. Then a unique translation takes the triangle to
{(0,0), (x,y), (z,w)} where the negativity of the third slope means
(x-z)/(y-w)<0. To count these triangles, fix any  (x,y)  not on the left
or bottom edges to be the top-most point, and count the choices for
(z,w) to the southeast of it: there are (n-x)(y-1) such choices. This gives
n^2(n-1)^2/4  triangles.

Finally, if the triangle has form {m1, m2, m3} in which the  m_i  _are_
all of the same sign, then there are _two_ rotations making all the 
m_i   positive and the triangle to the "northeast" of the intersection
the corresponding lines. In this case we choose the one with the
longest side to the north. Then  a unique translation takes the
triangle to {(0,0), (x,y), (z,w)} in which, if  (x,y)  is the
right-most point, we have x>z, y>w, and x/y > z/w. For any pair
(x,y) not on the left or bottom the choices for  (z,w)  are all those
strictly inside the triangle  {(0,0), (x,y), (0,x)}. These are of course
half the points inside a rectangle, apart from the points on the perimeter
and the additional -1+gcd(x,y) points on the diagonal. Thus the total 
number of such triangles is  Sum( (1/2)((x-1)(y-1)+1-gcd(x,y),  0<x,y<=n ).
I count  n^2(n-1)^2/8 + (1/2)(n-1)^2 - Sum( gcd(x,y), 1<=x,y<=n ) of
them, but I'm afraid I don't know what that last sum is.

Grand total: 3n^4/8-n^3/4+n^2/8+5n^2/4-n+1/2 - Sum( gcd(x,y), 1<=x,y<=n ) 

Also note that we have established that every triangle is equivalent to one
with a vertex at the origin, for any notion of equivalence at least as
strong as the one above.


The action of the group  Z^2.D_4  is almost the same. Since this contains
the previous group as a subgroup of index two, the equivalence classes
now are unions of either one or two of the previous ones. We can check
which is true by examining the effect of a single new group element, say
the reflection along the line  y=x. In almost every case above, this
group element carries our canonical representative of an equivalence
class to the canonical representative of another -- similar but distinct --
class. For example, it carries {(0,0), (0,a), (b,0)} to {(0,0), (a,0), (0,b)},
which we observed was inequivalent unless  a=b. So the only old
equivalence classes of this first type which are invariant under the
new group are those containing {(0,0), (a,0), (0,a)}, of which there are
only  n.

Likewise the only invariant classes of type {0,m1, m2} are those 
containing  {(0,0), (x,y), (2x,0)}, of which there are n^2/2
(n(n-1)/2  if  n  is odd).

If m1, m2, and m3 do not all have the same sign, then the classes are
inequivalent except for the ones containing triangles {(0,0), (x,y), (y,x)}:
(1/2)(n^2+n) more clases.

Finally, I leave it to the reader to verify that the new group element
carries the class containing {(0,0), (x,y), (z,w)} (with  m1, m2, and m3
all positive) to the class containing {(0,0), (y,x), (y-w,x-z)}, which
is a different class representative unless x=y=z+w. The number of such
classes is  (n-1)+(n-3)+...=(n^2-2n)/4 or (n^2-2n+1)/4 depending on
whether  n  is even or odd.

So if there are  N  equivalence classes unded  Z^2.C_4, including the
K  D_4-invariant ones just enumerated  (K=(3/4)n^2 + lower-order terms)
then there are  (1/2)( N + K )  equivalence classes under  Z^2.D_4.


Now, in the cases considered so far, we used only group actions which
preserved the entire lattice  Z^2. The original poster enquired about
equivalences under the Euclidean group -- a group in which only _some_
translates of _some_ triangles will again be triangles in  Z^2. In this
case I would use a different analysis -- one which is incomplete but
which should indicate some of the complexity of the problem.

One may identify the points (x,y) in  Z^2  with the Gaussian integers  x+iy.

Lemma. There is a rotation carrying the triangle with vertices 0, v,
and w to the triangle with vertices at  0, v', and w' (in that order) iff
	v=v0 r s,  w=w0 r s,  v'=u v0 rbar s,  and w'=u w0 rbar s
for some Gaussian integers  v0, w0, r, and s  and a unit  u (which must be
1, -1, i, or -i), such that  v0 and w0  are relatively prime, and
r and rbar are relatively prime.

Proof. If such numbers exist, then multiplication by  u(rbar/r)  is a
rotation of the plane which carries the one triangle to the other.

Conversely, if such a rotation exists, then  v  and  v'  have the same
length; so do  w  and  w'. 
	Now, the length of a Gaussian integer is also its norm in the
algebraic-number-theoretic sense. So we will consider the factorization
of  v  and  v'  into primes.
	Here you need to know that the ring  Z[i]  of Gaussian integers
is a unique factorization ring, and you need to know what the primes
and units in that ring are. The units are just the four powers of  i.
The primes are of three forms: (1+i) is the only prime dividing  2+0i.
Some ordinary primes  p+0i  are still prime in this ring (namely, those
p=3 mod 4); the others decompose into precisely two conjugate primes
(e.g. 5=(2+i)(2-i) ). If we fix one prime  P  dividing each rational
prime  p  then we may write a prime factorization of  v
	v = j (1+i)^a Prod p^(e_p) Prod P^(f_p) Pbar^(g_p)
which reflects the presence of units and distinguishes the three kinds
of primes. Note that this gives the prime factorization of  Norm(v)  as
	N(v)=2^a Prod p^(2e_p) Prod p^(f_p+g_p).
In particular, since  N(v)=N(v')  we must have  a=a', e_p=e'_p, and
f_p+g_p=f'_p+g'_p. Thus if  d  is the GCD  of  v  and  v', we see
d  must contain all the powers of  2  and the primes of the first sort
which occur in  v  (and  v'); moreover if we let  r = v/d  and
r' = v'/d, then r and r' are relatively prime and conjugate
up to a unit (e.g.  if  v=P^2 Pbar  and  v'=i Pbar^3, then  r=P^2  and 
r'=i Pbar^2.) Moreover, v'  is obtained from  v  by multiplying by
(r'/r), which is of length  1, so that this operation is a rotation.

Thus the original rotation and this new one agree on their action on
the nonzero point  v, and hence they are equal.

In particular, this requires  w'= (r'/r) w, i.e.  r w' = r' w.
Using unique factorization and the relative primality of  r  and  r',
it's then easy to see  w=r s and  w'=r' s  for some  s  (namely
s=gcd(w, w'), up to units.)

So both  v  and  w  are divisible by  r;  if  r1  is the greatest
common divisor of the two, let  v0=v/r1, w0=w/r1, and  s=r1/r. Then
it is easy to check that the claims of the lemma are met.  //
==============================================================================
Further comments Dec 1997 -- djr:
==============================================================================
Let  F_n  be the number of triangles in the  nxn  grid,  up to translation.
Then  F_n - F_(n-1) is the number of triangles of width or height (or both)
equal to  n. This is twice the number A_n with width   n  and height <n, plus
the number B_n with width AND height equal to  n.

Count  B_n  by looking at the number of triangles with
	3 corners: 4 such triangles (ask which corner is left out)
	2 adjacent corners: 4 edges x (N-1) points on opposite edge
	2 opposite corners: 2 such pairs x N^2-N locations for other vertex
	1 corner: 4 choices of corner x (N-1)^2 pairs of  points on the
		nonadjacent edges
	0 corners: Can't then have width AND height = N

Count  A_n:
	2 adjacent corners: 2 such edges xN(N-2) locations for remaining vertex
	1 corner: one point on opposite (Left/right) edge (N-2 choices)
		and other point anywhere not on line, not on top/bottom...

Somewhat easier to count classes invariant under the larger groups Z^2.C_4
or Z^2.D_4.

...