Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the infinite sum $S^2=\sum 1/(a_nb_n)$ with $a_n$ and $b_n$ positive and monotonically increasing, is it always true that we can cover a square of sidelength S with rectangles of sides $1/a_n$ and $1/b_n$ ?

Disregarding cases with trivial obstructions eg. $(1/a_1>S)$.

I am looking for cases where such a tiling is possible or impossible and the tiling or obstruction is nontrivial. Or a result that says its always a trivial tiling (ie a method to construct the tiling) or trivial obstruction

share|improve this question
You only need to consider the case $S=1$. –  Thomas Andrews Nov 17 '11 at 19:13
Why have you stated the problem in terms of inverses, rather than letting $u_i=\frac{1}{a_i}$ and $v_i=\frac{1}{b_i}$ and state the problems in terms of decreasing $u_i$ and $v_i$, leaving $a_i$ and $b_i$ out of it completely? The inverses are confusing. –  Thomas Andrews Nov 17 '11 at 20:09
Also, you haven't stated rigorously what you mean by "trivial obstruction." One definition might be that, for each $n$, you can place non-overlapping instances of the first $n$ rectangles into your square? In other words, "there is no finite obstructions." –  Thomas Andrews Nov 17 '11 at 20:12
It is true that the lack of a finitary obstruction is sufficient to imply a tiling: see my paper math.ubc.ca/~gerg/index.shtml?abstract=CTGP (the last two sentences of the paper address this explicitly). In brief, the sequence of finitary fits has a subsequence that converges to a tiling, by a compactness argument. –  Greg Martin Nov 18 '11 at 2:54
show 2 more comments

2 Answers

No, it is not always possible. If $a_1=b_1=\frac{4}{3}$ and $a_2=b_2=2$, then $\frac{1}{a_1b_1} + \frac{1}{a_2b_2} = \frac{9}{16} + \frac{1}{4} = \frac{13}{16}$, so you can fill out the rest of the sequences $a_i,b_i$ so that the $1=\sum \frac{1}{a_ib_i}$. But there is no way to fit even the first two rectangles, squares of sizes $\frac{3}4$ and $\frac{1}{2}$ into a square of size of $1$.

share|improve this answer
add comment

Let $T_0, T_1, T_2, \dots$ be an infinite sequence of tiles, fixed from now on. If there is no finite obstruction to placing the tiles (with no overlap except at boundary points) in the $1\times 1$ square, then all the $T_i$ can be placed with no overlap in the unit square. One kind of finite obstruction is if the sum of the areas of the tiles is greater than $1$. That too is a finite obstruction, since some finite sum of the areas would be greater than $1$.

The proof we sketch below may look a little complicated, but it really is a routine Compactness Theorem argument. Someone familiar with the machinery of nets can surely come up with a more orthodox proof.

We think of $T_n$ as an ordered pair $(a_n,b_n)$ where $a_n$ and $b_n$ are non-negative reals. Given a sequence of tiles, we first describe what we mean by a tiling of the square with opposite vertices at $(0,0)$ and $(1,1)$. A tiling using tiles $T_0,T_1,T_2,\dots$ is a special relation $C(n,x,y,\theta)$ where $n$ is a non-negative integer, and $x$, $y$, and $\theta$ are reals. Informally $C(n, x,y,\theta)$ holds if $(x,y)$ is the ordered pair that tells us the location of the bottom left corner of tile $T_n$, and $\theta$ is the angle that $T_n$ is rotated. But from now on, we look only at tilings where $\theta=0$ or $\theta=\pi/2$, so horizontal-vertical tilings.

Consider the theory $T$ whose language has a constant symbol for every real number, an $n$-ary relation symbol for every subset of $\mathbb{R}^n$, and an $n$-ary function symbol for every function from $\mathbb{R}^n$ to $\mathbb{R}$, and an additional special $4$-ary predicate symbol $C$. For axioms of $T$ we first of all throw in all sentences of the language that are true in the reals, when our constant symbols, predicate symbols (except $C$) and functions symbols are interpreted in the natural way. Of course we do not know what these axioms are, but that doesn't matter.

Now for every integer $n$, we throw in a special axiom $A_n$ that says that for $i=0, 1, \dots, n$, there are $x_i, y_i, \theta_i$ such that $C(i,x_i,y_i,\theta_i)$ and any two tiles intersect at most on boundary points. For our fixed sequence $T_0,T_1,\dots$ of tiles, the "non-intersecting" condition" is an uncomplicated set of inequalities. Note that we have added an infinite number of axioms.

By the "no finite obstruction" assumption, any finite subset of our set of axioms has a model, and hence by the Compactness Theorem, the whole theory $T$ has a model $\mathbb{M}$. For every non-negative integers $i$, this model assigns location say $(a_i,b_i)$ to the bottom left corner of the $i$-th tile, where (in the model) $0 \le a_i,b_i \le 1$. There is the minor complication that we have no assurance that we are in the standard model (essentially the reals). That is easily fixed: replace $a_i$, $y_i$ by the standard parts of $a_i$, $b_i$, and we obtain an orthodox "no overlap" tiling of (part of) the unit square.

Comments: At a certain stage, we restricted attention to tilings in which the rectangles had sides parallel to the sides of the square. This is because we do not have an immediate proof that if angles of rotation are replaced by their standard parts, we obtain an ordinary tiling.

Note that we have not proved that if the sum of the areas of the $T_i$ is $1$, and there is no finite obstruction, then all points of the unit square get covered. A measure $0$ subset might not be.

share|improve this answer
What is meant by 'the standard part of $x_i$' ? –  100101011011010011010110101110 Nov 17 '11 at 22:48
Let $M$ be a non-standard model of the reals. then $M$ contains a copy of the reals, which we identify with the reals. Let $x$ be in $M$ and finite, meaning that there is a real number $r$ such that $|x|<r$ (here $||$ and $<$ is sloppy notation for the interpretations in $M$ of the function symbol and relation symbol $||$ and $<$). Then there is a unique real number $st(x)$ which "infinitely close" to $x$, meaning that the distance between them is infinitesimal or $0$, that is, $<1/n$ for every positive integer $n$. –  André Nicolas Nov 17 '11 at 22:58
You might want to wait to accept, a more standard (pun) proof may come along. But of course you can unaccept. –  André Nicolas Nov 17 '11 at 23:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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