Just-do-it proofs

This post is another sample Tricks Wiki article, which revisits a theme that I treated on my web page. Imre Leader pointed out to me that I hadn’t completely done justice to the idea, and that the notion of a “just-do-it proof” had some more specific features that I had not sufficiently emphasized. His opinion matters to me since he was the one who told me about the concept. He himself got it from Béla Bollobás: I don’t know whether it goes further back than that. This is a second attempt at explaining it. Imre, if there’s anything you don’t like about this one, then please edit it when it appears on the Tricks Wiki.

Title: Just-do-it proofs.

Quick description: If you are asked to prove that a sequence or a set exists with certain properties, then the best way of doing so may well be not to use any tricks but just to go ahead and do it: that is, you build the set/sequence up one element at a time, and however you do so you find that it is never difficult to continue building.

Prerequisites: Basic undergraduate mathematics. Ordinals for one example.

Example 1: A subset $A$ of the plane is called dense if for every point $x$ in the plane and for every positive real number $\delta$ there exists a point $a\in A$ such that the distance from $x$ to $a$ is at most $\delta$ . Does there exist a dense subset of the plane that contains no three points in a line?

This is an example of a question that is quite hard (though not impossible) if you go about it the wrong way, and almost trivial if you are used to just-do-it proofs. The hard way of solving it is to try to think of a clever definition of a set that works. One might, for instance, start with a very obvious dense set, such as the set of all points with rational coordinates, and use a continuous map to distort it in such a way that no three points lie in a line. But such an approach will need some ingenuity: the continuous map would need to be nice enough for it to be possible to prove that no three rational points had images in a line, which would be a question in number theory, but it couldn’t be too nice or there would be three images in a line.

If you are interested in keeping life simple, then the mistake in such an approach is to try to define the whole set at once. What if instead you build it up element by element?

In order to do this, you need to be clear about the conditions that the set must eventually satisfy. These can be written as follows: $\forall x\ \forall \delta>0\ \exists a\in A\ d(x,a)<\delta$ . (Here, $d(x,a)$ denotes the distance from $x$ to $a$ .) At first it looks challenging to create a set that satisfies all these conditions because there are uncountably many of them, one for each point $x$ and each $\delta>0$ . However this appearance is illusory (as it often is), because we can replace this uncountable set of conditions by a countable one: it is enough to prove it for every $\delta$ of the form $1/n$ for some positive integer $n$ , and it is also enough to prove it just for points $x$ that have rational coordinates. (Then, if you want to find a point in $A$ that is within $\delta$ of a point $z$ in the plane, you first find a rational point $x$ such that $d(x,z)<\delta/2$ , then a positive integer $n$ such that $1/n<\delta/2$ , and finally a point $a\in A$ such that $d(x,a)<1/n$ .)

The set of points within a distance $1/n$ of a point $x$ with rational coordinates is an open disc, so we can redescribe our problem as follows: we have a certain countable set of open discs $D_1,D_2,D_3,\dots$ , and we would like to find a set $A$ such that every $D_n$ contains at least one point of $A$ and no three points of $A$ lie in a line.

Once reformulated in this very minor way, the problem is perfectly set up for a just-do-it approach. We need $D_1$ to contain a point in $A$ , so let $a_1$ be a point in $D_1$ . We need $D_2$ to contain a point in $A$ , so let $a_2$ be a point in $D_2$ . We need $D_3$ to contain a point in $A$ , so let $a_3$ be a point in $D_3$ , but this time we have to be a tiny bit careful because if $a_1\ne a_2$ (which we may as well assume), then $a_3$ must not be on the line that contains $a_1$ and $a_2$ . But you can’t cover all of $D_3$ by a line, so it’s easy to pick $a_3$ that avoids this line.

In general, suppose that we have chosen distinct points $a_1,a_2,\dots,a_n$ such that $a_i$ belongs to $D_i$ for every $i$ and no three of the $a_i$ lie in a line. Can we continue the process? Well, we need $a_{n+1}$ to belong to $D_{n+1}$ , to be different from all of $a_1,a_2,\dots,a_n$ , and not to lie on any of the $\binom n2$ lines $L_{ij}$ , where by this we mean the line that contains $a_i$ and $a_j$ . But one cannot cover an open disc with just finitely many points and lines, so there is no difficulty in choosing $a_{n+1}$ .

(It’s pretty obvious that you can’t cover an open disc with finitely many points and lines, but it is not quite trivial, so here’s a short proof: since there are only finitely many lines $L_{ij}$ it is possible to pick a line $L$ through the centre of $D_{n+1}$ that is not parallel to any of them. Then we can choose any point of $L\cap D_{n+1}$ as long as it isn’t one of the forbidden points or the point of intersection of $L$ with one of the $L_{ij}$ . But $L\cap D_{n+1}$ is infinite and this rules out only finitely many points.)

It is not hard to modify the above proof to add the condition that every point in $A$ has rational coordinates

General remarks: A just-do-it proof is one that builds a sequence $a_1,a_2,\dots$ that satisfies a sequence of constraints $P_1,P_2,\dots$ , where the $n$ th constraint, $P_n$ , is a property of $a_1,\dots,a_n$ , and where for any sequence $a_1,\dots,a_n$ that satisfies $P_n$ it is not hard to prove that there exists $a_{n+1}$ such that the sequence $a_1,\dots,a_{n+1}$ satisfies $P_{n+1}$ . In the example above, $a_1,a_2,\dots$ were points in the plane and $P_n$ was the property that $a_i\in D_i$ for every $i\leq n$ , the $a_i$ with $i\leq n$ are distinct, and no three of those $a_i$ lie in a line.

Example 1 is what one might think of as a completely standard just-do-it proof. If you adopt the mentality used in the above proof, then many results that at first look quite hard can in fact be proved extremely easily. In the remainder of this article, we shall give two further examples of the basic just-do-it approach, then two examples of problems that are not immediately obviously of the just-do-it type, but which can be converted into ones that are, and finally an example where the building-up process continues transfinitely.

Example 2. Is it possible to colour the positive integers with two colours, red and blue, in such a way that no infinite arithmetic progression is coloured entirely red or entirely blue?

Once again, a very small amount of reformulation is needed to bring out the just-do-it nature of this problem. First, one notes that there are only countably many infinite arithmetic progressions. If we enumerate these as $A_1,A_2,A_3,\dots$ , then it is enough to construct sequences $r_1,r_2,r_3,\dots$ and $b_1,b_2,b_3,\dots$ of positive integers such that for each $i$ both $r_i$ and $b_i$ belong to $A_i$ and such that no $r_i$ is equal to any $b_j$ . If we can do that, then we can colour the $r_i$ red, the $b_i$ blue, and all other integers however we like, and each $A_i$ will contain at least one red point and at least one blue point.

But this is a very easy task. If we have chosen $r_1,\dots,r_n$ and $b_1,\dots,b_n$ such that $r_i$ and $b_i$ belong to $A_i$ for each $i\leq n$ and such that no $r_i$ is equal to any $b_j$ , then there is no difficulty in continuing the sequence with $r_{n+1}$ and $b_{n+1}$ , since $A_{n+1}$ is infinite and there are only finitely many numbers that have already been used.

In this case it is quite easy to define a colouring that works, but the just-do-it approach brings out the true nature of the problem: that it is trivial.

Example 3. Is it possible to find exponentially many subsets of $\{1,2,\dots,N\}$ such that any two of them have symmetric difference of size at least $N/3$ ?

There are clever methods in coding theory for defining such a collection of sets, but these methods were serious mathematical results. Actually, so was the observation that a just-do-it approach would work, but from today’s perspective is more or less obvious. All you do is choose a sequence of sets $A_1,A_2,\dots$ however you like, making sure only that when you choose $A_n$ the symmetric difference of $A_i$ and $A_n$ has size at least $N/3$ for every $i<n$ . When is this easy to do? Well, for a set to have symmetric difference with $A_i$ of size at most $N/3$ you have to choose a set of size at most $N/3$ to be the symmetric difference. The number of these is at most $\sum_{k=0}^{N/3}\binom Nk$ , and it is a straightforward exercise (consider ratios of successive binomial coefficients) to show that this is bounded above by $C^N$ for some constant $C$ that is strictly less than 2. Therefore, provided $nC^N<2^N$ , we can continue the sequence. From this it follows that we can choose exponentially many such sets.

Example 4. Are all real numbers algebraic? That is, is every real number a root of some polynomial with integer coefficients? The answer is of course no, and as is very well known there are two contrasting approaches. One is that of Liouville, which was to prove that no algebraic number can be too well approximated by rationals and then to construct a real (and irrational) number that could be very well approximated by rationals. In a similar spirit, Hermite and Lindemann showed that $e$ and $\pi$ are transcendental. The other approach is that of Cantor, who noted that the algebraic numbers form a countable set, while the real numbers are uncountable.

It is often stated (even by me on occasion) that Cantor’s proof is an abstract existence proof. But a better way of regarding it is as a just-do-it proof, as I shall explain.

Let us take it as read that the algebraic numbers are countable. What then is our task? We have a list $a_1,a_2,\dots$ of real numbers and we must find a new real number $r$ that is not equal to any number on our list. This does not look like a just-do-it proof because we are trying to find a single object, the real number $r$ , rather than a sequence. But if you are acquainted with elementary real analysis then you will know that the single-object quality of a real number is somewhat illusory, and that real numbers is intimately tied up with sequences. (An elementary illustration of this is the fact that real numbers can be given by infinite decimal expansions and usually not by finite ones. The restnof the discussion could take place in terms of decimal expansions but I prefer the approach I shall take, which is based on Cantor’s first proof that the reals are uncountable.)

One way of specifying a real number is as the unique point that belongs to a nested intersection of closed intervals with widths that tend to zero. That is, one uses the lemma (which is equivalent to the completeness property of the reals) that if $u_1\leq u_2\leq\dots$ and $v_1\geq v_2\geq\dots$ are sequences of real numbers such that $v_n-u_n$ is a non-negative sequence that tends to zero, then there is exactly one real number that belongs to every closed interval $\null [u_n,v_n]$ . This is useful to us because it allows us to construct a sequence of some kind rather than defining $r$ all at once; it therefore opens up the possibility of a just-do-it proof.

What properties should the sequence of intervals $\null [u_n,v_n]$ have if we want the intersection not to equal any of the $a_n$ ? Well, if we ensure that for each $n$ the number $a_n$ does not belong to the interval $\null [u_n,v_n]$ then we will certainly have ensured that $a_n$ does not belong to the intersection of all those intervals. Therefore, we will be done if we can construct the intervals $\null [u_n,v_n]$ in such a way that $a_n\notin [u_n,v_n]$ , that $\null [u_{n+1},v_{n+1}]\subset [u_n,v_n]$ for every $n$ and (less importantly) that the lengths $v_n-u_n$ tend to zero. But this is easy: given any closed interval $I$ and any real number $a$ one can find a closed subinterval $J\subset I$ that does not contain $a$ and has at most half the length of $I$ .

The above proof is inexplicit in the sense that it does not directly specify a transcendental number. However, with a little trouble it can be converted into an algorithm for generating the sequence of intervals, so in that sense it is a constructive proof. (One would have to modify it slightly so that for each polynomial one found good approximations to its roots and then avoided any numbers that were within the margin of error.) But what the proof does not give is a formula for the intersection of the intervals that result.

Example 5. Is there an infinite matrix $(a_{mn})$ such that $\lim_n a_{mn}=0$ for every $m$ and $\lim_m a_{mn}=1$ for every $n$ ?

We have already seen that problems may need to be reformulated in order to become amenable to the basic just-do-it technique. Up to now the reformulation has been very mild. This example is here to show that sometimes it can be slightly deeper. In a moment I will say more precisely what I mean by this comment.

Let us begin with the observation that we have a countable set of conditions that our matrix must satisfy: its rows must tend to 0 and its columns must tend to 1. The main constraint we face is that if a row and a column intersect then they must take the same value at the point of intersection. There is thus the potential for a just-do-it proof, but in order to make it fit the general description of such proofs we need to choose what order to do the tasks in. This is where the very slight depth arises: effectively we need to prove that the union of the set of all rows and the set of all columns is countable. The simplest way of listing them is to take the first row, then the first column, then the second row, then the second column, and so on.

If we do this then the problem becomes as easy as the other examples above. How can we make the first row tend to 0? The simplest way is to set $a_{1n}=0$ for every $n$ . How can we make the first column tend to 1, given that it must agree with the first row at $a_{11}$ ? The simplest way is to set $a_{11}=0$ and $a_{m1}=1$ for every $m>1$ . If we continue in this way then we rapidly see that it produces the example $a_{mn}=0$ if $m\leq n$ and $a_{mn}=1$ if $m>n$ .

One sometimes sees examples such as $a_{m,n}=m/(m+n)$ given as solutions to this problem. While they too work, they obscure the fact that once again the problem is trivial (in the sense that no serious constraints arise when one tries to build an example).

Here is an exercise. Let $g$ be any function from $\mathbb{Q}\times\mathbb{Q}$ to $\mathbb{R}$ . Prove that there is a function $f$ from $\mathbb{Q}\times\mathbb{Q}$ such that for any two rational numbers $\lambda$ and $\mu$ the limit of $f(x,\lambda x+\mu)$ , as $x$ tends to infinity in $\mathbb{Q}$ , is $g(\lambda,\mu)$ . This problem would be pretty hard to solve with an explicit formula but it is just as easy as all the others if one uses a just-do-it approach.

I should remark that in principle it is possible to use any well-ordered set to index the tasks in a just-do-it approach. This is why I describe the idea of organizing the above construction by alternating between rows and columns as “slightly deep”, since one has to realize that it is a bad idea to do all the rows first and then all the columns. The next example illustrates a just-do-it proof over a more general well-ordered set.

Example 6. Is there a subset $A\subset\mathbb{R}^2$ such that for every positive real number $r$ there is exactly one pair of points $x,y$ in $A$ such that the distance between $x$ and $y$ is $r$ ?

The answer to this is yes, but this time the building-up process is transfinite. The set $A$ is required to satisfy one constraint for each positive real number $r$ . So we build it up an element at a time, with each new element designed to make sure that some new distance $r$ occurs. Of course, as we do so, we must be careful that no distance occurs twice.

To make this approach work we must appeal to the well-ordering principle, which tells us that we can ind a well-ordering of the positive real numbers. Moreover, we can do so in such a way that the number of predecessors of each $r$ in the well-ordering is strictly less than the number of reals. (If the continuum hypothesis is true then the number of predecessors will therefore be countable, but that is not necessary.)

If the positive reals are well-ordered, then we can associate with each one an ordinal $\alpha$ , which we call its index. Now let us define the elements of $A$ by induction on these ordinals. Suppose that we have defined a sequence of sets $A_\beta$ , one for each ordinal less than $\alpha$ , in such a way that (i) if $\beta<\gamma$ then $A_\beta\subset A_\gamma$ , (ii) for each $\beta<\alpha$ the real number with index $\beta$ occurs as a distance in $A_\beta$ , and (iii) no distance occurs more than once in any $A_\beta$ . We now construct $A_\alpha$ as follows. If the distance $r$ with index $\alpha$ occurs in some $A_\beta$ with $\beta<\gamma$ then we let $A_\alpha$ be the union of all $A_\beta$ with $\beta<\alpha$ . Otherwise, we take this union and add an extra point to it in order to create a distance of $r$ . To do this, we choose an arbitrary point $P$ in the union and look at the circle of radius $r$ about $P$ . We would like to pick a point in this circle to add to our set, since this would give us a distance of $r$ . However, we must not add a point that causes any of the existing distances to be duplicated. Geometrically speaking, our new point must not lie on any circle about any existing point if the radius of that circle is equal to a distance we already have in the set. But each such circle intersects the circle of radius $r$ about $P$ in at most two points, and the number of such circles is easily checked to be less than the cardinality of $\mathbb{R}$ , which is the cardinality of any circle, so we can find a new point to continue our sequence. Continuing in this way we create the desired set.

Exercise: Here is a final question that can be solved easily using the technique of Example 6. Can you prove that there is a red/blue colouring of the set of all infinite subsets of the natural numbers, with the following two properties: (i) every infinite set $X$ of natural numbers has at least one red subset and at least one blue subset, and (ii) if the symmetric difference of two sets of natural numbers is finite then they have the same colour? (The second condition is there to rule out a well-known and rather straightforward direct application of the axiom of choice to obtain a colouring where two sets have different colours whenever they have a finite symmetric difference that is of odd cardinality.)

This entry was posted on August 16, 2008 at 9:25 am and is filed under Mathematical pedagogy, Mathematics on the internet. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

28 Responses to “Just-do-it proofs”

Chris Eagle Says:
August 16, 2008 at 12:31 pm | Reply
In the statement of example six, do you mean R squared rather than R?
Chris Eagle Says:
August 16, 2008 at 12:37 pm | Reply
You need another condition on the final exercise, otherwise I can just colour the finite sets red and the infinite sets blue.

Many thanks for both comments — I’ve made changes accordingly.
Isabel Lugo Says:
August 16, 2008 at 3:31 pm | Reply
In Example 3, you say “making sure only that when you choose A_n the symmetric difference of A_i and A_n has size at most N/3 for every i<n.” Shouldn’t “most” be “least” here?

Also, I realize that this isn’t the point of the post, but another possible trick might be the trick that is actually used to compute that C, namely that of bounding a sequence by a geometric series. Similarly, certain integrals can be bounded by exponentials, which is useful for the (obviously related) problem of calculating a tail bound for the normal distribution. There are certainly other examples, although I don’t have them at my fingertips.

Thanks — correction made. And your suggestion would indeed make a suitable Tricks Wiki article. And if you don’t have as many examples as you would like, it shouldn’t stop you as we will be encouraging submission of incomplete articles, provided they are clearly marked as such with a sentence such as “This article needs a few more examples,” or “I have several examples but I do not yet have a clear general description of the method.”
Terence Tao Says:
August 17, 2008 at 5:54 pm | Reply
It seems that a common theme in all of these examples is that the underlying object one is seeking to construct has a lot of freedom in it, and the constraints one are imposing on it are quite weak or somehow “decoupled” (e.g. they only exclude a measure zero or otherwise “thin” set of possibilities from the ambient or “free” space of possibilities, or the constraints can be satisfied by exercising only a portion of the freedom available [e.g. using just the lower triangular portion of an infinite matrix]).

Hmm, this brings up a more general suggestion for the Tricks Wiki – in addition to having examples and discussion of situations in which the trick shows some promise of working, one might also want to exhibit examples or general situations in which the trick is not likely to be effective. For instance, in this case, a “just do it” approach fails horribly for the task of constructing Hadamard matrices (orthogonal square matrices with entries +1 and -1) – the constraints are just too global and too algebraic to give one the “wiggle room” one needs for this sort of approach.
gowers Says:
August 17, 2008 at 8:05 pm | Reply
Terry, by coincidence, though not much of a coincidence, I started writing a page earlier today that would go some way towards following your suggestion. As you pointed out in a comment a few months ago, many tricks are concerned with proving the existence of mathematical objects with certain properties. So I started writing a kind of index page that is aimed at helping people to navigate through the Wiki if they are trying to prove a statement that begins “There exists”. What I’m trying to do is send the reader to appropriate articles (hardly any of which yet exist) given their answers to simple questions about the object they are trying to construct. One obvious question is, “What sort of object is it?” with the answer being something like a matrix, or a group, or a subset of the plane, or a topological space, etc. But another very important one is exactly the issue you’re talking about, of whether one is in a world with many constraints or few, since the kinds of methods one uses are radically different. The two questions are of course related: one wouldn’t use a just-do-it approach to construct a finite group, say.

One remark I intend to make is that establishing existence is easy if there are few enough constraints, and sometimes also easy if there are many constraints (in the latter case because you don’t have much choice about what to do), which leaves a rather interesting class of problems that are hard because they are somehow in between the two extremes. The problem of finding a Hadamard matrix of order $4n$ is a good example. Another is the problem, also open, of finding a Hamilton cycle in the bipartite graph that consists of all subsets of size $n$ or $n+1$ of a set of size $2n+1$ , with $A$ joined to $B$ if one is a proper subset of the other. There it is easy to get started just building a path, but after a while the constraints become overwhelming. And yet it seems that there are probably several examples, so one isn’t led to any particular construction.

This phenomenon partly explains another trick — that of proving a stronger result than you need, in order to reduce the size of the space in which you are searching. Of course, finding a suitable strengthening isn’t easy.
Define Radius Server Says:
August 18, 2008 at 4:26 am | Reply
[…] Just-do-it proofs […]
Andrew Stacey Says:
August 18, 2008 at 8:27 am | Reply
Example 5 is what I would call a “just write it down” trick! As I started reading it I wondered what could possibly need the sort of construction of the previous examples as one could simply write down a matrix with all the properties required. Maybe this particular example is so well ingrained into my subconscious that I don’t realise how tricky it can be first time one sees it.

However, to make a serious point on this, there is a slight difference between Example 5 and the others: in Example 5 you construct an actual matrix with actual numbers. The others, while mildly constructive, give a procedure which, if followed, would produce the desired ‘whatever’ but no one is seriously going to follow those steps and the final answer is unguessable without doing so. Of course, this slight difference is probably too slight to mention: if one can see a solution straight away then one doesn’t need a trick but if one can’t then this is a good trick to use to get the solution. Still, bytes are cheap!
gowers Says:
August 18, 2008 at 8:42 am | Reply
Andrew, I know what you mean because I happen to be able to remember my first encounter with this question, and my experience bears out what you say since the answer came to me in a flash and not by means of some systematic derivation such as I propose here. However, I think that something just-do-it-like was probably going on in my mind. I might have been asking myself things like, “What do we need to happen?” “How can we achieve it most simply?” “What can interfere with what?” and the feeling of getting it in a flash might have resulted from the fact that after a very small number of stages one is suddenly able to see an explicit description of the final answer. But the just-do-it view of the problem does add something I think, since it gives you a recipe for constructing lots of solutions in a very easy way. (For example, you can enumerate the rows and columns however you like, and you can fill them in however you like as long as you tend to the right limits and don’t change anything you’ve previously decided on.)

My other thought on this is that I don’t see how a computer would “just write it down” but I do see how a computer could “just do it”.
Ori Says:
August 22, 2008 at 2:44 pm | Reply
An interesting topic! I was once given the problem of finding a dense set in the plane intersecting any vertical or horizontal line at a single point (at most or exactly, it doesn’t really matter; most solutions to the former lead quite immediately to a solution to the latter). I came up with the idea of rotating Q^2 by an angle whose tangent was irrational, but I now realize the question was more trivial than I had first thought.
elacaraq Says:
August 28, 2008 at 7:32 am | Reply
“To make this approach work we must appeal to the well-ordering principle, which tells us that we can ind a well-ordering of the positive real numbers.”

On both wikipedia and mathworld.wolfram.com the well-ordering principle is defined as “every nonempty set of positive integers contains a smallest number.” Maybe I am missing something here, how could that imply positive real numbers could be well ordered?

Another elementary question I have is: what is the difference between a normal induction and a transfinite induction? Is that in a normal induction, we prove something holds for a chain of sets a_1, a_2,…, a_n, then show it holds for set a_{n+1}, while in transfinite induction, a_n is replaced with the union of all sets before it? Thanks.
Tyler Says:
August 28, 2008 at 8:15 am | Reply
elacaraq:

You can well-order the reals using the well-ordering _theorem_:

http://en.wikipedia.org/wiki/Well-ordering_theorem

which is logically equivalent (in ZF set theory) to the axiom of choice. The ordering would have to be very different from the usual ordering of the reals, which is of course very poor (as opposed to well, hehe math humor).

“Normal” induction is usually meant to only apply to a countable set where each element has an immediate successor, such as the natural numbers. You proceed like this: if I know phi(x), then I also know phi(x+1). But this approach fails as soon as the set has an element that is not the immediate successor of another, even if it’s well-ordered.

Here’s a simple example of such a set: Let’s take N, the natural numbers, and add the single element B (for “Big number”) which is larger than any element of N. Clearly any nonempty subset still has a least element, so it’s still a well ordered set. But now normal induction fails sometimes — for example, let me define 1 \in N as odd, and then n+1 as (even,odd) iff n is (odd,even). Is B even or odd? I could write a normal inductive proof to show this is a good definition on N, but it fails to hold for B as well.

The wikipedia entry on transfinite induction splits induction into two types: successor case (as with the natural numbers, the normal way); or the limit case, of which B is an example. But you can also elegantly state transfinite induction as a single case, which planetmath gives:

http://planetmath.org/encyclopedia/TransfiniteInduction.html
elacaraq Says:
August 28, 2008 at 8:17 am | Reply
In the last sentence in above message, I meant a_{n+1} is replaced with the union of all sets before it. Sorry to make the correction here. I wish we could edit our own comments.
On another note: if the questions are two elementary, please delete them.
Tyler Says:
August 31, 2008 at 9:36 am | Reply
I’ve informally written up an abstract framework to capture the unifying concept here:

http://thetangentspace.com/wiki/index.php?title=Pigeonhole_constructions

along with a few other examples:
* a dense set in the plane with no two similar triangles
* an infinite matrix with no singular subsquares
* a graph exists for any countably infinite choice of positive degrees
Jose Brox Says:
September 11, 2008 at 9:47 pm | Reply
Hi Tim!

I thought we could use some words from Polya in the Introduction Page to the Tricki. I looked at the preface of “How to Solve It” and the paragraph I liked the most for us was this one:

<>

— George Polya, How To Solve It: A new aspect of mathematical method. 1944 —

If you like the idea, I plan to look also into his ‘more serious’ volumes “Mathematics and Plausible Reasoning” (vol1 “Induction and Analogy in Mathematics” and vol2 “Patterns of Plausible Inference”). In any case, I suspect that they can be a source for the Tricki to much greater extent than just quoting…

Btw, another “concept” (using the term I suggested in the hierarchy I sketched by email) would be the one of “reverse engineering”: If you know what you want your solution to look like, then try to arrive from it to your hypotheses (or to _some acceptable_ hypotheses as well) by a chain of double implications. If any extra assumption was made in the process, just add it to the hyphoteses.
Jose Brox Says:
September 11, 2008 at 9:49 pm | Reply
(I’m sorry, the paragraph pasted in the window but I think the webpage restrict the use of “<“. Here it goes again)

———————
Studying the methods of solving problems, we perceive
another face of mathematics. Yes, mathematics has two
faces; it is the rigorous science of Euclid but it is also
something else. Mathematics presented in the Euclidean
way appears as a systematic, deductive science; but
mathematics in the making appears as an experimental,
inductive science. Both aspects axe as old as the science of
mathematics itself. But the second aspect is new in one
respect; mathematics “in statu nascendi,” in the process
of being invented, has never before been presented in
quite this manner to the student, or to the teacher
himself, or to the general public.
——— Polya —————

Regards!
Anonymous Says:
September 18, 2008 at 3:35 am | Reply
Great post!

There is a typo in example 5:
“How can we make the first column tend to 0, given that it must agree with the first row at a_{11}?”
It should say “first column tend to 1.”

[Thanks very much for pointing that out — I’ve corrected it now.]
The forthcoming launch of the Tricki « Gowers’s Weblog Says:
October 15, 2008 at 7:05 pm | Reply
[…] searches and tags. But even these may leave some articles a bit hard to find. For example, consider my sample article on just-do-it proofs. If you are unfamiliar with the just-do-it technique and have a problem that you find difficult but […]
Mark Dominus Says:
October 16, 2008 at 5:36 am | Reply
There’s an extensive discussion of this technique, in the context of transfinite induction, in Cieselski’s book “Set Theory for the Working Mathematician”. Among the (many) examples are proofs that, R^3 is a union of disjoint circles, but R^2 is not, and that there is a subset of the plane which is intersected in exactly one point by every horizontal line but whose intersection with every vertical line is a dense subset of R.
Jaime Montuerto Says:
October 28, 2008 at 5:23 pm | Reply
Dear Prof Gowers,

I have a question that I have been working on for a long time and somehow relates to a lot of articles I’ve read in your blog about Fermat’s little theorem.

Here’s the question,

Do all primes divides a Mersenne number? A Mersenne prime divides itself.

As a counterpoint 7, a Mersenne number itself does not divide any Fermat number, it seems so.

Thanks!
Dave Futer Says:
February 7, 2009 at 12:34 am | Reply
I could be missing something, but it seems that Example 5 is susceptible to a very simple — and not at all deep — “just do it” attack. That is, one can write down the matrix explicitly.

Take a single, bi-infinite sequence $s_k$ with the property that the sequence approaches 1 as $k \to \infty$, and approaches 0 as $k \to -\infty$. For example, you can let $s_k = 2^k$ for negative $k$, and $s_k = 1 – 2^{-k}$ for positive $k$. Alternately, one can rig something up by rescaling the arctangent function.

Now, to get the desired matrix, let $a_{mn} = s_{m-n}$. As $m$ goes to infinity, the terms tend to 1, and as $n$ goes to infinity, the terms tend to 0. This solution has the added advantage of a lot of symmetry.

Or is this explicit way of “just doing it” not a good illustration of the inductive-construction philosophy?
gowers Says:
February 7, 2009 at 11:18 am | Reply
Dave, That’s a simple argument, but in a way that’s a prototype of the non-just-do-it approach (in the technical sense of “just do it” that I’m discussing here). Embedded in what you say is the idea (simple, but an idea nevertheless) of making your matrix depend on $m-n$ only. I claim that the just-do-it approach avoids the need for any idea whatsoever. I won’t try to be precise about what I mean by that …
Wikipedia References Says:
January 24, 2012 at 7:22 pm | Reply
Wikipedia References…

[…]Just-do-it proofs « Gowers's Weblog[…]…
Don’t do it! | Complex Projective 4-Space Says:
April 7, 2013 at 11:13 am | Reply
[…] Sir Timothy Gowers FRS wrote about the usefulness of a particular proof strategy, known as ‘just do it’. He gives […]
Mushfeq Khan Says:
April 15, 2016 at 6:28 pm | Reply
I’m concerned about a possible gap in your proof of Example 6. Your construction appears to ensure that an existing distance isn’t duplicated by the addition of a new point, but how does it ensure that a new distance is not added twice? One way to address this explicitly would be to consider the lines that are the loci of points equidistant from pairs of existing points and delete their intersections with the circle as well.

Also, one might need to add another condition to the induction hypothesis saying that we add at most one point at each step. Otherwise, I don’t see how the cardinality of the deleted points can be controlled.
- gowers Says:
  April 17, 2016 at 3:42 pm
  I agree with these comments. I should have said that when we add a point at distance $r$ from some point $x$ in the set, we make sure not only that it isn’t at an already used distance from one of the other points, but also that it isn’t at distance $r$ from one of the other points. But that adds only a small set (meaning of size strictly less than the continuum) of further points that need to be avoided.
  
  Of course, that’s exactly what you are suggesting.
- Mushfeq Khan Says:
  April 18, 2016 at 6:42 am
  Thanks for clarifying.
  
  I may be missing something, but it seems to me that one must never duplicate any distance, whether it is existing, $r_\alpha$ , or otherwise. The last type of distance may be duplicated if we add a new point $x$ such that $d(x, y) = d(x, z)$ for two existing points $y$ and $z$ .
- gowers Says:
  April 18, 2016 at 11:54 am
  You’re right, and I somehow didn’t take that in from what you wrote before. But it’s still OK (as you pointed out) because we have a circle of possible points to add, which has continuum size, and fewer than that many points to avoid, some of which are the result of existing distances and some of which are intersections of that circle with bisecting lines between pairs of points that have already been chosen.
a dense set in plane [duplicate] – Math Solution Says:
March 8, 2022 at 12:10 pm | Reply
[…] no three collinear points. Such a set can be constructed by adding the points one by one; see Timothy Gowers’s blog for a nice […]