[math-fun] tiling rectangles with rectangles.
I would like to know whether the following stuff is known. Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE. GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable. ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S. THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area. The necessity of the condition is easy and probably known. It's the sufficiency which is interesting. EXAMPLE; a,b,c,d,e are rationally independent positive numbers S consists of two rectangles with (width, height) (a,b-c) and (a-c,d) S' is three rectangles (e,b),(a-e,b-c),(a-e-d,c) . One verifies the tensor areas are equal. Our proof of sufficiency is constructive showing how to find the tiles that do the job. (I have some pretty pictures if anyone is interested) [ Actually it matters whether we or not we use SYMMETRIC tensor product where we have a(x)b=b(x)a. This corresponds to allowing interchanging height and width in the tiling. (or of rotating tiles through 90 degrees). Refernces?? David G
On Sun, Oct 24, 2004 at 03:54:57PM -0500, David Gale wrote:
I would like to know whether the following stuff is known.
Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE.
GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable.
ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S.
THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area.
This is surely known. There's a harder problem, one of Hilbert's problem, solved by Dehn: Question. When are two polyhedra in R^3 equidecomposable into polyhedra? [Allow arbitrary polyhedra, not just rectangles] Answer. For each edge, consider l(x)theta, where l is the length of the edge and theta is the angle of the edge, as an element of R(x)(R/2pi), tensor product over Q. The sum of this quantity over all edges of a polyhedron P is called the Dehn invariant of P. Then P and P' are equidecomposable iff they have the same area and same Dehn invariant. I don't know the references, sorry. It was solved early last century. Peace, Dylan
My reaction was similar to Dylan's. However, I don't remember hearing this problem formulated in this way before---it's a nice phenomenon. Just to be more explicit about what Dylan was alluding to, you can think of each edge of a polyhedron as determining a rectangle, in cylindrical coordinates, whose length is the length of the edge and whose width is the angle. An equidecomposition of polyhedra leads to an equidecomposition of these rectangles in Gale's sense, except that any rectangle of width 2 pi can be created or thrown away "for free". One person who has worked on related questions more recently is Walter Neumann; if you need references, he probably has a pretty good grip. This is all connected to the homology of classifying spaces for Lie Groups given the discrete topology. E.g. the fancy terminology for equidecomposition classes of rectangle case as described is the 2nd homology group of R with the discrete topology (which is well-known since as an abstract group R is just a free abelian group on lots of generators, if you accept the axiom of choice.) The only point not captured directly by homology is the issue of positive vs. negative rectangles. Bill Thurston On Oct 25, 2004, at 8:50 AM, Dylan Thurston wrote:
On Sun, Oct 24, 2004 at 03:54:57PM -0500, David Gale wrote:
I would like to know whether the following stuff is known.
Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE.
GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable.
ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S.
THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area.
This is surely known. There's a harder problem, one of Hilbert's problem, solved by Dehn:
Question. When are two polyhedra in R^3 equidecomposable into polyhedra? [Allow arbitrary polyhedra, not just rectangles]
Answer. For each edge, consider l(x)theta, where l is the length of the edge and theta is the angle of the edge, as an element of R(x)(R/2pi), tensor product over Q. The sum of this quantity over all edges of a polyhedron P is called the Dehn invariant of P. Then P and P' are equidecomposable iff they have the same area and same Dehn invariant.
I don't know the references, sorry. It was solved early last century.
Peace, Dylan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Thurstons and rkg. Thanks for your responses. There are several things to say. 1. Believe me, I am very familiar with the story of "Hilbert's third". I am in the process of creating a web site which has a whole exhibit on equi-decomposition of polygons. Please click below.(if the first one doesn't work try the second one). Then go to the Dissection exhibit, enter the Gallery and click on the History panel with the picture of Hilbert. Keep going and find the link to Dehn, a very touching story. As an aside, I had the intention of sending these links to the group anyway. They are certainly math and they're supposed to be fun. I'd welcome reaction from any of you. http://mathsite.math.berkeley.edu/intro.html http://mathsite.math.berkeley.edu/main.html 2.Dylan, your remarks about the problem are not correct. You wrote " Then P and P' are equidecomposable iff they have the same area and same Dehn invariant." "It was solved early last century". Not true. Dehn only proved the necessity. The sufficiency was proved (?) seventy years later by a Danish mathematician named Sydler and a clear proof was given by Borge Jessen shortly afterwards. The proof is difficult and uses homological algebra (!). The book "Hilbert's Third Problem" by Vladimir Boltyanskii 1978 is the definitive reference. 3. Bill, Do your remarks imply that the Dehn-Hilbert problem can be reduced to our rectangle problem??? This would be astonishing because our method for finding the equi-decompositions is quite elementary. By the way, when I say "our", the main work was done not by me but by Clifford Gardner. Following your suggestion I'm sending a copy of this to Walter Neumann. 4. Just for emphasis let me say again, what we have is an algorithm. Given two finite sets of rectangles with the same tensor area it finds a common dissection. Such a natural problem, you'd think it would be known, but is it? David G
My reaction was similar to Dylan's. However, I don't remember hearing this problem formulated in this way before---it's a nice phenomenon. Just to be more explicit about what Dylan was alluding to, you can think of each edge of a polyhedron as determining a rectangle, in cylindrical coordinates, whose length is the length of the edge and whose width is the angle. An equidecomposition of polyhedra leads to an equidecomposition of these rectangles in Gale's sense, except that any rectangle of width 2 pi can be created or thrown away "for free".
One person who has worked on related questions more recently is Walter Neumann; if you need references, he probably has a pretty good grip. This is all connected to the homology of classifying spaces for Lie Groups given the discrete topology. E.g. the fancy terminology for equidecomposition classes of rectangle case as described is the 2nd homology group of R with the discrete topology (which is well-known since as an abstract group R is just a free abelian group on lots of generators, if you accept the axiom of choice.) The only point not captured directly by homology is the issue of positive vs. negative rectangles. Bill Thurston
On Oct 25, 2004, at 8:50 AM, Dylan Thurston wrote:
On Sun, Oct 24, 2004 at 03:54:57PM -0500, David Gale wrote:
I would like to know whether the following stuff is known.
Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE.
GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable.
ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S.
THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area.
This is surely known. There's a harder problem, one of Hilbert's problem, solved by Dehn:
Question. When are two polyhedra in R^3 equidecomposable into polyhedra? [Allow arbitrary polyhedra, not just rectangles]
Answer. For each edge, consider l(x)theta, where l is the length of the edge and theta is the angle of the edge, as an element of R(x)(R/2pi), tensor product over Q. The sum of this quantity over all edges of a polyhedron P is called the Dehn invariant of P. Then P and P' are equidecomposable iff they have the same area and same Dehn invariant.
I don't know the references, sorry. It was solved early last century.
Peace, Dylan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Mon, Oct 25, 2004 at 01:50:32PM -0500, David Gale wrote:
1. Believe me, I am very familiar with the story of "Hilbert's third". ...
My apologies; I didn't understand what you were asking about.
As an aside, I had the intention of sending these links to the group anyway. They are certainly math and they're supposed to be fun. I'd welcome reaction from any of you.
http://mathsite.math.berkeley.edu/intro.html http://mathsite.math.berkeley.edu/main.html
Unfortunately, none of the exhibit itself works with free software, so I cannot view it. It sounds quite interesting, though.
2.Dylan, your remarks about the problem are not correct. You wrote " Then P and P' are equidecomposable iff they have the same area and same Dehn invariant." "It was solved early last century".
Not true. Dehn only proved the necessity. The sufficiency was proved (?) seventy years later by a Danish mathematician named Sydler and a clear proof was given by Borge Jessen shortly afterwards. The proof is difficult and uses homological algebra (!). The book "Hilbert's Third Problem" by Vladimir Boltyanskii 1978 is the definitive reference.
Thanks for the correction!
3. Bill, Do your remarks imply that the Dehn-Hilbert problem can be reduced to our rectangle problem??? This would be astonishing because our method for finding the equi-decompositions is quite elementary. By the way, when I say "our", the main work was done not by me but by Clifford Gardner. Following your suggestion I'm sending a copy of this to Walter Neumann.
I think the import of Bill's message was that the same homological techniques that can be used to prove the converse of the Dehn-Hilbert problem can also be used to solve your question. Your proof is doubtless much easier than that.
4. Just for emphasis let me say again, what we have is an algorithm. Given two finite sets of rectangles with the same tensor area it finds a common dissection. Such a natural problem, you'd think it would be known, but is it?
Can you say a bit more about the proof? I would guess that essentially from the definition of tensor product you can get an algorithm that possibly uses negative area rectangles, and the difficulties are avoiding those? In any case, I would ask Walter Neumann if he knew about previous work. Peace, Dylan
C20 in UPIG gives M. Dehn, "Uber den Rauminhalt, Math Ann 55(1901) but no page numbers. R. On Mon, 25 Oct 2004, Dylan Thurston wrote:
On Sun, Oct 24, 2004 at 03:54:57PM -0500, David Gale wrote:
I would like to know whether the following stuff is known.
Well known: There does not exist a set of rectangles which will tile both a 1 by 2 rectangle and a square of side sqrt(2) (although they both have the same area). We say these sets are not EQUI-TILABLE.
GENERAL PROBLEM: Let S be a union of a finite set of rectangles and let S' be another such set. Under what conditions are S and S' equi-tilable.
ANSWER: Think of reals as a vector space over Q. For a rectangle of width a and height b we can form their TENSOR PRODUCT a(x)b. The TENSOR AREA of the set S is summation(a_i(x)b_i) summed over the rectangles of S.
THEOREM. The sets S and S' are equi-tilable if and only if they have the same tensor area.
This is surely known. There's a harder problem, one of Hilbert's problem, solved by Dehn:
Question. When are two polyhedra in R^3 equidecomposable into polyhedra? [Allow arbitrary polyhedra, not just rectangles]
Answer. For each edge, consider l(x)theta, where l is the length of the edge and theta is the angle of the edge, as an element of R(x)(R/2pi), tensor product over Q. The sum of this quantity over all edges of a polyhedron P is called the Dehn invariant of P. Then P and P' are equidecomposable iff they have the same area and same Dehn invariant.
I don't know the references, sorry. It was solved early last century.
Peace, Dylan
participants (4)
-
David Gale -
dpt＠lotus.bostoncoop.net -
Richard Guy -
William Thurston