Tiling a rectangle with the fewest squares (Q2563714)

It is shown that a square-tiling of a \(p\times q\) rectangle, where \((p,q)=1\) and \(p<q\), requires at least \(\max\{q/p,\log_2q\}\) square tiles. The author constructs a square-tiling with less than \(q/p+ C_1\log_2p\) square tiles of integer size, for some universal constant \(C_1\). The proof of the lower bound for a square-tiling utilizes the theory of electrical networks. The notion of ``thickness'' of a Cantor set is required to prove the upper bound.