wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Triangles in Z^n
        
(Message started by: Eigenray on Aug 30^th, 2007, 7:14pm)

Title: Triangles in Z^n
Post by Eigenray on Aug 30^th, 2007, 7:14pm

When can a triangle be embedded (up to similarity) in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ?

Title: Re: Triangles in Z^n
Post by Barukh on Aug 31^st, 2007, 11:27pm

Let one of the vertices be put at the origin, and two others at lattice points A, B in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ. If a, b are corresponding vectors from the origin to points A, B, then the area S of the triangle satisfies:
(2S)² = a²b² - (ab)²,
which is an integer. Therefore, if S is not a square root of an integer, the triangle cannot be embedded.

Of course, this is not suficient to answer the original question, even in general.

Title: Re: Triangles in Z^n
Post by Barukh on Sep 1^st, 2007, 5:08am

Here’s another necessary condition: If a triangle with angles http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif is embeddable in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ, then both quantities tan²(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) and tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)/tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif) are rational.

This condition, I think, is also sufficient.

:-/

Title: Re: Triangles in Z^n
Post by Michael_Dagg on Sep 1^st, 2007, 7:59am

Good question. Obviously the squares of the ratios of the side lengths
will have to be rational. But that's not enough: a classic question asks,
"Is there an equilateral triangle in Z^n ?" ; here the ratios of the
side lengths are all equal to 1.

But, there are no equilateral triangles in Z^n by Pick's Theorem.

Title: Re: Triangles in Z^n
Post by Eigenray on Sep 1^st, 2007, 10:24am

on 08/31/07 at 23:27:25, Barukh wrote:

Therefore, if S is not a square root of an integer, the triangle cannot be embedded.

But I am asking about similarity classes of triangles.

on 09/01/07 at 05:08:38, Barukh wrote:

If a triangle with angles http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif is embeddable in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ, then both quantities tan²(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) and tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)/tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif) are rational.

This condition, I think, is also sufficient.

It is in fact sufficient for the triangle to be embeddable in some http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ.

But for each n, which triangles can be embedded in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ? It may help to first consider the case n=2.

on 09/01/07 at 07:59:55, Michael_Dagg wrote:

But, there are no equilateral triangles in Z^n by Pick's Theorem.

Not in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif², but there are in all higher dimensions. In fact, a regular n-simplex can be embedded in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ when:
n is even and n+1 is a square;
n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 3 mod 4; or
n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod 4 and n+1 is the sum of two squares.

Title: Re: Triangles in Z^n
Post by Barukh on Sep 2^nd, 2007, 5:20am

on 09/01/07 at 10:24:21, Eigenray wrote:

It may help to first consider the case n=2.

This case is easy: tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif), tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif) both rational.

Proof: Let tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) = p/q, tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif) = r/s. Then the lattice points (0, rp), (ps, 0), (rq, 0) form a triangle similar to given.

The converse may be shown using formulas for tan of the sum of two angles.

Title: Re: Triangles in Z^n
Post by Michael_Dagg on Sep 2^nd, 2007, 11:21am

I meant Z^2 when I referred to Pick's Theorem.

I don't think I've ever seen your result about the n-simplex.
I guess I can imagine a proof (assuming "when" means "if", not "iff").
Is there a simple way to handle the case n=2? I mean, besides the
Pick's Theorem method I mentioned, which I've always thought was a
wonderful use of an unexpected tool...

Title: Re: Triangles in Z^n
Post by Eigenray on Sep 2^nd, 2007, 12:03pm

on 09/02/07 at 05:20:44, Barukh wrote:

Proof: Let tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) = p/q, tan(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif) = r/s. Then the lattice points (0, rp), (ps, 0), (rq, 0) form a triangle similar to given.

Now can you think of a way to generalize that same construction?

on 09/02/07 at 11:21:47, Michael_Dagg wrote:

I don't think I've ever seen your result about the n-simplex.
I guess I can imagine a proof (assuming "when" means "if", not "iff").
Is there a simple way to handle the case n=2? I mean, besides the
Pick's Theorem method I mentioned, which I've always thought was a
wonderful use of an unexpected tool...

It is in fact iff, and it's proved in:
I. J. Schoenberg, Regular simplices and quadratic forms, J. London Math. Soc., 12 (1937) 48-55.
The relation to quadratic forms is this:

Lemma: Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif= OP₁...P_n and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif' = OP₁'...P_n' be two given n-dimensional simplices, and let
F(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i,k <P_i, P_k> x_ix_k, F(y) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i,k <P_i', P_k'> y_iy_k
be their corresponding quadratic forms. Let L(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif) and L(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif') be the lattices generated by the sets of vectors {P_i} and {P_i'}. A multiple http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lambda.gifL(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif) can be inscribed in L(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif') iff the quadratic forms F(x) and F'(y) are rationally equivalent up to a factor.

However, the case n even is relatively simple: just consider the volume.

Title: Re: Triangles in Z^n
Post by Barukh on Sep 4^th, 2007, 10:18am

on 09/02/07 at 12:03:15, Eigenray wrote:

Now can you think of a way to generalize that same construction?

In fact, I've read Beeson's paper...

Title: Re: Triangles in Z^n
Post by Barukh on Sep 7^th, 2007, 10:05am

Here’s what I know.

The embeddability of a triangle with rational tan²(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) = p/q in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ implies a non-trivial solution of the following system of Diophantine equations (indices run 1 ... n):

pq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif a_i² = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif h_i²,

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif a_ih_i = 0

where a, h are unknowns.

It then follows that if pq is represented as a sum of n squares, the corresponding angle is embeddable in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gifⁿ⁺¹. Therefore, any triangle with rational tangent squares may be embedded in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif⁵.

That’s sufficient but not necessary. It’s further shown that if triangle is embeddable in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif⁴, then it’s embeddable also in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif³. The trivial example of this is the equilateral triangle: for it, pq = 3, a sum of three squares, and embeddable in three dimensional space.