52
$\begingroup$

This is a claim one of my students made without justification on his exam. It definitely wasn't the right way to approach the problem, but now I've been nerdsniped into trying to figure out if it is true.

Let $a_i$ be a sequence of positive reals such that $\sum a_i^2 = \infty$. Then $[0,1]^2$ can be covered by translates of the squares $[0,a_i]^2$.

It is definitely not enough that $\sum a_i^2>1$: You can't cover a unit square with $5$ axis-aligned squares of sidelength $1/\sqrt{5}$.

$\endgroup$
  • 1
    $\begingroup$ Does "covered" mean here "exactly covered"? Otherwise you can take $9$·sqaures of sidelength $1/\sqrt 5$ instead of $5$. $\endgroup$ – ajotatxe Dec 20 '17 at 22:58
  • 3
    $\begingroup$ There are an infinite number of terms such that $a_n\geq \frac{1}{n\log n}$, so I am prone to believe the claim is true. $\endgroup$ – Jack D'Aurizio Dec 20 '17 at 22:59
  • 1
    $\begingroup$ Yes, @ajotatxi, but then $\sum a_i^2 >\frac85$ and the statement OP made was that it is that $\sum a_i^2 >1$ does not guarantee coverage. $\endgroup$ – Mark Fischler Dec 20 '17 at 23:00
  • 1
    $\begingroup$ just an example, $1/\sqrt n$ for $n=7,8,9,10,...$ With $7,8,9$ we can cover a strip wider then $1$ and at least as tall as $1/3.$ With $10,11,12,13$ a strip taller than $1/4.$ With $14,15,16,17,18$ a strip taller than $1/5.$ With $19,20,21,22,23,24$ a strip taller than $1/6.$ With $25,26,27,28,29,30,31$ a strip taller than $1/7.$ Also $1/3 + 1/4 + 1/5 + 1/6 + 1/7 > 1.$ $\endgroup$ – Will Jagy Dec 20 '17 at 23:11
  • 4
    $\begingroup$ @John xkcd first introduced me to the term nerdsniping. You may appreciate the relevant xkcd. $\endgroup$ – Brian J Dec 21 '17 at 14:28
48
$\begingroup$

We actually only need $\sum a_i^2 >4$ for this to hold*. In particular, note that this condition implies that there is some finite set $I$ of the indexing subset such that $\sum_{i\in I}a_i^2>4$.

Let $b_i$ be the largest power of two less than or equal to $a_i$ for each $i\in I$. Clearly, $2b_i>a_i$. In particular, $\sum_{i\in I}b_i^2>1$. Now, we can inductively construct a by squares of side length $b_i$ for $i\in I$. To be specific, for each $k$, let $c_k$ be the number of $i\in I$ such that $b_i=2^{-k}$. We are equivalently trying to cover $[0,1]^2$ by a collection of squares of powers of two in side length, with $c_k$ copies of $[0,2^{-k}]^2$.

However, this is easy: Let $G_k$ be the partition** of $[0,1]^2$ into translates $[0,2^{-k}]^2$ in the obvious way (i.e. by slicing into $2^k$ rows and columns). Note that $G_{k+1}$ is always a refinement** of $G_k$. Then, we can place the squares from biggest to smallest; we can greedily place as many of the biggest $c_1$ squares into $G_1$ as possible. Then, if the square is not full, we put as many $c_2$ squares into the uncovered cells of $G_2$ as possible - and so on. Since each is a refinement of the last, we can always place a new square in without overlap of a previous square - unless everything is already full. This process must terminate eventually, since we only have finitely many squares. However, since their areas sum to more than one, and they are being placed without overlap, they must actually cover the square.

(*This inequality actually doesn't need to be strict; if you trace through the argument, the fact that the inequality $2b_i>a_i$ is strict lets us weaken the inequality for the sum)

(**This is all up to the boundaries of the cells, which might intersect. But since we're dealing with a finite set of squares, the union is closed, so measure zero sets don't matter anyways)


Here's an illustration of the process, where the squares are assumed to have powers of two as side lengths, $c_1=2$ and $c_2=5$ and $c_3=9$ and $c_4=12$. Observe that there's really nothing that could possibly go wrong:

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
  • 7
    $\begingroup$ This is beautifully simple. $\endgroup$ – David K Dec 21 '17 at 2:16
  • 2
    $\begingroup$ (+1) The idea of approximating $a_n$ with a power of $2$ recalls Calderòn-Zygmund lemma and it is indeed very efficient. In two words, greedy works. $\endgroup$ – Jack D'Aurizio Dec 21 '17 at 2:31
  • 2
    $\begingroup$ This looks brilliant, but you lost me somewhere. Maybe I'd get it if it weren't late at night, but I think a few more words of clarification might be in order. $\endgroup$ – Wildcard Dec 21 '17 at 5:40
  • 11
    $\begingroup$ In fact, it's enough to have $\sum a_i^2>3$ (an elementary proof can be found in Newman's A problem seminar, for example). Also, $3$ is sharp; three squares with $1-\epsilon$ can't cover a unit square (since each square can cover at most one of the corners). $\endgroup$ – Ankoganit Dec 21 '17 at 14:12
  • 3
    $\begingroup$ @Ankoganit Thanks for that! I thought $3$ might suffice, but despite my best late-night efforts, couldn't prove it. (Also, for anyone who doesn't want to track down the book: The solution is to use the proof outlined in Jack D'Aurizio's answer, and the strategy for the bounds suggested in my comment thereon, using that the area of the $i^{th}$ strip is bounded by $(1+r_{i-1})r_i\leq r_i+r_{i-1}$) $\endgroup$ – Milo Brandt Dec 21 '17 at 17:13
13
$\begingroup$

An answer exploiting the idea of Will Jagy outlined in the comments.

If there is some $a_n\geq 1$ there is nothing to prove, so we may assume $0< a_n <1$. There is nothing to prove also if $\limsup a_n>0$, so we may assume $\lim_{n\to +\infty}a_n=0$.

Assuming $\sum_{n\geq 1}a_n<+\infty$ we would have $\sum_{n\geq 1} a_n^2<+\infty$, so $\sum_{n\geq 1}a_n$ is divergent. We may say that some finite subset $S\subseteq \mathbb{N}^+$ is a good subset if $\sum_{s\in S}a_s\geq 1$ and decide that the rank of a good subset is $\min_{s\in S}a_s$. We may pick the good subset with the highest rank (there is a highest rank since $\lim_{n\to +\infty}a_n=0$) for covering a strip as tall as the rank of such subset, remove these elements from the original sequence, re-index it and repeat.

It is not be difficult to show that the set of strips built by this $\min\max$ greedy algorithm is a cover of the whole square, i.e. that the sum of the ranks exceeds one at some point. Assuming that an infinity of strips is produced, the fact that these strips do not cover the whole square but $\sum_{n\geq 1}a_n^2$ is divergent leads to a contradiction.


This introduces a horribly difficult problem:

What is the infimum of $r\in\mathbb{R}^+$ such that for every sequence $\{a_n\}_{n\geq 1}$ with $a_n\in(0,1)$ and $\sum_{n\geq 1}a_n^2\geq r$, it is possible to cover $[0,1]^2$ with translates of $[0,a_1]^2,[0,a_2]^2,[0,a_3]^2,\ldots$?

$\endgroup$
  • 1
    $\begingroup$ If I haven't made an error, I think you get a pretty good bound here - let $S_i$ be the $i^{th}$ good subset chosen and $r_i$ be its rank, with $r_0=1$ by convention. Note $\sum_{j\in S_i}a_j^2 \leq \left\lceil\frac{1}{r_i}\right\rceil\cdot r_{i-1}^2.$ As a crude bound, the RHS is no more than $2r_{i-1}$, since the sequence $r$ is decreasing in $[0,1]$. Thus $\sum_{j\in S_i}a_j^2\leq 2r_{i-1}$, so $\sum_{i=1}^n\sum_{j\in S_i}a_j^2\leq 2+2\sum_{i=1}^{n-1}r_i$. I think this means that if $\sum_{i}a_i^2>4$, the sum of the ranks is at least one (at least as long as $\sum_ia_i=\infty$). $\endgroup$ – Milo Brandt Dec 21 '17 at 3:00
6
$\begingroup$

Let $(X_i,Y_i)$ be a sequence of i.i.d. uniform variables on $[0,1]$ and let $S_i$ be the square of side $a_i$ centered at $(X_i,Y_i)$. Let $(x,y)$ be a point in the unit square. Then

$$\begin{align} \mathbb{P}\left((x,y) \notin \bigcup_iS_i\right)&=\prod_i \bigl(1-\mathbb{P}((x,y)\in S_i)\bigr) \\ &\leq \prod_i \bigl(1-a_i^2/4\bigr). \end{align} $$

Since $\sum_i a_i^2$ is divergent, $\prod_i \bigl(1-a_i^2/4\bigr)=0$ so $(x,y)$ lies in $\bigcup_i S_i$ almost surely. It follows that almost surely, $\bigcup_i S_i$ contains all rational points inside the square. Take such a realisation of variables $(X_i,Y_i)$ : it should be possible to show that $\bigcup_i S_i$ covers in fact the whole square even if I can't find a good argument for that.

$\endgroup$
  • $\begingroup$ ah, you got there just as I did... $\endgroup$ – Countingstuff Dec 20 '17 at 23:52
  • $\begingroup$ @Countingstuff : indeed ! $\endgroup$ – tristan Dec 20 '17 at 23:52
  • $\begingroup$ (+1) to both for the slick probabilistic idea. I am not entirely happy by its non-constructive flavour, but I will deal with it. $\endgroup$ – Jack D'Aurizio Dec 20 '17 at 23:59
  • $\begingroup$ @kimchilover : I am not sure why the odd squares would be able to 'mop up' the set of uncovered points. $\endgroup$ – tristan Dec 21 '17 at 0:53
  • $\begingroup$ On reflection, I'm not sure either. I'll remove my comment; if I think of a real reason I'll post it as an answer. $\endgroup$ – kimchi lover Dec 21 '17 at 1:20
4
$\begingroup$

If $a_i\geq 1$ for some $a_i$ then it's easy to do, otherwise for each square independently pick a point in $[0,1]^2$ uniformly at random to be the centre for that square.

For each point $(u,v)$ the probability that $(u,v)$ is covered by that square is at least $a_i^2/4$ (worst case is it's a corner point).

So the probability that $(u,v)$ is not covered is $p=\prod_{k=1}^{k=\infty} (1-a_k^2/4) \leq exp(-\sum_{k=1}^{\infty}a_k^2/4)=0$

edit - now I'm not so convinced by this, I thought the finishing off would be simple but it's not so much so.

$\endgroup$
  • $\begingroup$ It should be enough to invoke Borel-Cantelli applied to an enumeration of the rational points in $[0,1]^2$. $\endgroup$ – Jack D'Aurizio Dec 21 '17 at 1:32
1
$\begingroup$

Note first the interesting case is $a_i \rightarrow 0$, as otherwise there are infinitely many squares with side length greater than some $\epsilon$. So consider this case. Also, we need only consider the case where all $a_i<1$. Order the sequence so that $a_i\geq a_{i+1} \: \forall(i)$.

Line up the first n squares (with side lengths $a_1,a_2,\dots,a_n$) until their lengths just sum to $\geq 1$. These cover a rectangle whose height is $a_n$ (because we assume the $a_i$ are decreasing). Then line up the next $m$ squares until their lengths just sum to $\geq 1$, and translate them up by $a_n$ so that the two lines of squares cover a rectangle with height $a_n + a_m$. Repeat.

Let $a_k$ be the side of the last square in row $k$. Row $k+1$ has a width $<2$, and each square has height $<a_k$, so the area it covers is $<2a_k$. Since the sum of all areas is $\infty$, we must have $\sum a_k =\infty$. This means that stacking the rows of squares on top of each other, we can make the pile arbitrarily high. In particular, we can make it 1 high, so that it covers the unit square.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.