# Covering a square with unit squares

\begin{conjecture} For any integer $n \geq 1$, it is impossible to cover a square of side greater than $n$ with $n^2+1$ unit squares. \end{conjecture}

Alexander Soifer in [S] raises the question of the smallest number $\Pi (n)$ of unit squares that can cover a square of side $n+\epsilon$. He shows the asymptotic upper bound $n^2+o(1)n+O(1)$, and the small values $\Pi (1)=3$, $5 \leq \Pi (2) \leq 7$, and $10 \leq \Pi (3) \leq 14$. He conjectures the asymptotic lower bound $n^2+O(1)$.

## Bibliography

[S] Soifer, Alexander, "Covering a square of side n+epsilon with unit squares," J. of Combinatorial Theory, Series A 113 (2006):380-383.

* indicates original appearance(s) of problem.

### A flaw in the text of the conjecture

The square to cover is not a __unit__ square.

### A simple upper bound for Pi(n)

For any positive integer *n*: Pi(*n*) does not exceed sqr(*n*)+*n*+1 .

*e* instead of epsilon:

*n*+*e* :

*n* by *n* unit squares as a square of side length *n* in the lower left corner. Move those unit squares on the upper-right side of the diagonal running from the upper left to the lower right corner by *e* up and right.

*e* consisting of *n*+1 horizontal lines of length 1+*e* and *n* vertical lines of length 1-*e*. If *e* is small enough, it is possible to cover that area with a regular array of *n*+1 non-overlapping unit squares such that each of them covers one horizontal line and parts of the one or two connected vertical lines.

### Correction

Sorry; please replace the last part by this:

*e* consisting of *n* horizontal lines of length 1+*e*, *n*-1 vertical lines of length 1-*e*, and one vertical line of length 1. If *e* is small enough, it is possible to cover that area with a regular array of *n*+1 touching but not (2-dimensional) overlapping unit squares such that each of the first *n* of them covers one horizontal line and parts of the one or two connected vertical lines and the remaining square covers the remaining part of the (lower) vertical line.

### Resulting upper bounds for n from 1 to 3

The given bound confirms the bounds for n=1 (3) and for n=2 (7) given by Soifer in [S] but improves the bound for n=3 (13 instead of 14).

### Possibly further readings

The two articles listed below may be on the same topic but I can't get access even to the abstracts: [1] Title: A Sharper Upper Bound for Cover-Up Squared Authors: Dmytro Karabsh and Alexander Soifer Publication: Geombinatorics Quarterly Vol XVI, Issue 1, July 2006 Pages: 219 ff. (to 226 ?) [2] Title: Note on Covering Square with Equal Squares Authors: Dmytro Karabsh and Alexander Soifer Publication: Geombinatorics Quarterly Vol XVIII, Issue 1, July 2008 Pages: 13 ff. (to 17 ?)

### A (currently) valid link to the referenced article

www.uccs.edu/~faculty/asoifer/docs/untitled.pdf

### Correction

In the URL there has to be a tilde (ASCII code 126) between 'edu/' and 'faculty' instead of the visible blank.

## A lower bound of the upper bound from polyomino-covering in [S]

(Using $e$ instead of $\epsilon$)

In [S], Soifer derives $\Pi(n) < (n-k)^2+2(k+1)[[\frac{k^2-1}{k^2+k-\sqrt{2k+2}} n]]$ .

As he mentioned, one can improve the covering construction. Holding the square of side length $n-k$ in the lower left corner, putting a square of side length $k$ in the upper right corner, covering the remaining uncovered area by 2 polyomino-coverings of rectangles of sides $n-k+e$ by $k+e$, removing useless unit squares in polyominos, we get a lower bound for the rhs of that inequality:

$(n-k)^2+k^2+2[[(k+1)(n-k)\frac{k^2-1}{k^2+k-\sqrt{2k+2}} ]]$

Denote by $U(n)$ the minimal value of this expression when varying $k$ from 2 to $n-2$.

Results of computer calculations:

$U(n)
For growing $n$ (checked up to $2\times 10^9$), for the lowest optimal $k$, $\sqrt{2\times k^3}/n$ seems to converge to 1, and $(\ln(U(n)-n^2))/(\ln n)$ seems to converge to 3/4.