Rectangles as sums of squares (Q1043649): Difference between revisions

Given an \(n\times m\) rectangle with \(n\) and \(m\) integers, some tilings of the rectangle by suares can be constructed. Laczkovich posed the problem: what is the minimum number of squares required? He also asked the corresponding analogue in higher dimensions. \textit{R.~Kenyon} [``Tiling a rectangle with the fewest squares'', J. Comb. Theory, Ser. A. 76, No. 2, 272--291 (1996; Zbl 0873.05033)] proved a tight logarithmic bound for the two-dimensional problem. Here the author turns to some generalizations of the problem. In one of generalizations the rectangle is replaced by a hypercuboid, the squares are replaced by hypercubes. In another generalization the indicator function of the rectangle is written as a plus/minus sum of the indicator functions of squares. Using different methods the author proves good upper and lower bounds for various generalizations of the problem. The results are related to discrepancy theory.