Rectangles as sums of squares

In this paper we examine generalisations of the following problem posed by Laczkovich: Given an n×mn×m rectangle with nn and mm integers, it can be written as a disjoint union of squares; what is the smallest number of squares that can be used? He also asked the corresponding higher dimensional analogue. For the two dimensional case Kenyon proved a tight logarithmic bound but left open the higher dimensional case. Using completely different methods we prove good upper and lower bounds for this case as well as some other variants.