Covering a square of side n+ε with unit squares

In [Covering a triangle with triangles, Amer. Math. Monthly 112 (1) (2005) 78; Cover-up, Geombinatorics XIV (1) (2004) 8–9], Conway and I showed that in order to cover an equilateral triangle of side length n+ε, n2+2 unit equilateral triangles suffice while obviously n2+1 are wanted. (The latest “triangular” results can be found in [D. Karabash, A. Soifer, On covering of trigons, Geombinatorics XV (1) (2005) 13–17].) Here I pose an analogous problem for squares and show that in order to cover a square of side length n+ε, n2+o(1)n+O(1) unit squares suffice. This problem is dual to the one solved by Erdös and Graham 30 years ago [On packing squares with equal squares, J. Combin. Theory (A) 19 (1975) 119–123], which dealt with packing unit squares in a square. And as in Erdös–Graham, in our problem a natural upper bound of (n+1)2 provided by a square lattice can be much improved.