Tiling a rectangle with the fewest squares

1994/11/28 by Richard Kenyon, Kenyon, Richard
Mathematics · Computer Science · #Mathematical Dynamics and Fractals #Cellular Automata and Applications #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/9411215

Abstract

We show that a square-tiling of a p× q rectangle, where p and q are relatively prime integers, has at least log₂p squares. If q>p we construct a square-tiling with less than q/p+Clog p squares of integer size, for some universal constant C.

Related

• When Can You Tile an Integer Rectangle with Integer Squares?
• Tiling Rectangles and the Plane using Squares of Integral Sides
• Tilings with the Minimal Tile Property
• Signed shape tilings of squares
• Tiling of rectangles with squares via Diophantine approximation