Instantly share code, notes, and snippets.

# narain/sim-rect-diss.sage

Created Dec 19, 2022
Dissection of a square into n similar rectangles via guillotine cuts
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from dataclasses import dataclass from typing import Any from sage.all import * n = 4 # A guillotine partition is a binary tree of horizontal and vertical cuts. # In our problem each leaf node is a horizontal or vertical rectangle. # For example, 3 vertical cuts and 4 vertical rectangles produce [ | | | ] @dataclass class CH: c0: Any c1: Any @dataclass class CV: c0: Any c1: Any @dataclass class RH: pass @dataclass class RV: pass # First we generate the partitions. # At the root, due to symmetry we only need one of CH or CV. def guillotine(n, root=False): if n <= 1: yield RH() yield RV() else: for i in range(1, n//2 + 1): for c0 in guillotine(i): for c1 in guillotine(n-i): yield CH(c0, c1) if not root: yield CV(c0, c1) # Then, we find the aspect ratios of the partitions, # assuming the aspect ratios of the leaves are 1:u, # and solve for the values of u that yield squares. u = QQ['u'].0 def simplify(p0, p1): q = p0.gcd(p1) return (p0//q, p1//q) def aspect(t): if isinstance(t, RH): return (u,1) elif isinstance(t, RV): return (1,u) elif isinstance(t, CH): (w0,h0) = aspect(t.c0) (w1,h1) = aspect(t.c1) return simplify(w0*w1, w0*h1 + w1*h0) elif isinstance(t, CV): (w0,h0) = aspect(t.c0) (w1,h1) = aspect(t.c1) return simplify(w0*h1 + w1*h0, h0*h1) d = {aspect(t):t for t in guillotine(n, True)} def genroots(d): for a, t in d.items(): rs = (a-a).roots(ring=RR) for r in rs: if r >= 1: yield(1/r, r, a, t) l = sorted(list(genroots(d)), key=lambda i: i) for i in l: print(i)

### narain commented Dec 19, 2022

As requested by John C. Baez, a list of the polynomials that the ratios are roots of for n = 5.

``````u - 5
u^3 - 4*u^2 + u - 3
u^3 - 4*u^2 + 2*u - 4
2*u - 7
u^3 - 4*u^2 + 3*u - 3
2*u^3 - 6*u^2 + u - 2
u^3 - 3*u^2 + 2*u - 5
u^3 - 3*u^2 + 2*u - 4
2*u^3 - 6*u^2 + 2*u - 2
u^3 - 3*u^2 + u - 1
3*u - 8
u^3 - 3*u^2 + 3*u - 5
2*u^3 - 5*u^2 + u - 2
u^5 - 3*u^4 + 3*u^3 - 4*u^2 + u - 1
-2*u^2 + 6*u - 3
2*u^3 - 5*u^2 + 2*u - 3
3*u - 7
u^4 - 3*u^3 + 3*u^2 - 4*u + 2
2*u^3 - 5*u^2 + 3*u - 3
u^3 - 3*u^2 + 4*u - 4
-u^2 + 4*u - 4
4*u - 8
3*u^3 - 6*u^2 + u - 1
2*u^3 - 4*u^2 + 2*u - 3
u^3 - 2*u^2 + 3*u - 5
3*u^3 - 6*u^2 + 2*u - 2
u^5 - 2*u^4 + 3*u^3 - 5*u^2 + u - 1
2*u^3 - 4*u^2 + 3*u - 4
4*u - 7
u^3 - 2*u^2 + 4*u - 6
-u^3 + 3*u^2 - 4*u + 3
2*u^3 - 5*u^2 + 4*u - 2
2*u^3 - 4*u^2 + 3*u - 3
3*u^3 - 5*u^2 + 2*u - 3
5*u - 8
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + u - 1
-3*u^2 + 6*u - 2
2*u^4 - 4*u^3 + 3*u^2 - 3*u + 1
3*u^3 - 5*u^2 + 2*u - 2
4*u^3 - 6*u^2 + u - 1
-2*u^3 + 4*u^2 - 3*u + 2
2*u^3 - 3*u^2 + 3*u - 4
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + 2*u - 1
5*u - 7
u^3 - 2*u^2 + 3*u - 3
2*u^3 - 3*u^2 + 2*u - 2
-u^3 + 2*u^2 - 4*u + 4
3*u^3 - 5*u^2 + 3*u - 2
3*u^3 - 4*u^2 + u - 1
4*u^3 - 6*u^2 + 2*u - 1
4*u - 5
2*u^3 - 3*u^2 + 4*u - 4
-5*u + 6
6*u - 7
``````

By my count there are 51 different ratios. But there are more than 51 polynomials above, because some of them yield equal roots.