TILING A RECTANGLE WITH THE FEWEST SQUARES

Richard Kenyon

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

Typeset by AMS-TEX