26
$\begingroup$

I am hoping that the brilliant MathOverflow geometers can help me out.

Question 1. Suppose that I have a fixed finite-length straightedge and fixed finite-size compass. Can I still construct all constructible points in the plane?

I know the answers in several variations.

But what I don't know is the remaining case, where both the straightedge and compass are limited in size. The difficult case seems to be where you have two points very far apart and you want to construct the line joining them.

Will Sawin's comment answers the question I had asked above. But it doesn't seem to answer the relative version of the question, which is what I had had in mind:

Question 2. Suppose that I have a fixed finite-length straightedge and fixed finite-size compass. Can I still construct all constructible points in the plane, relative to a fixed finite set of points?

In other words, is the tool set of a finite straightedge and finite compass fully equivalent to the arbitrary size toolset we usually think about.

$\endgroup$
  • 1
    $\begingroup$ If $(a,b)$ is a constructible point, can't we construct $( \frac{a}{n}, \frac{b}{n})$ for $n$ sufficiently large by pretending my straightedge is infinite and then shrinking my construction? Then can I walk along that line in steps of size $\frac{a}{n}, \frac{b}{n}$ by using a special case of the rusty compass theorem construction? $\endgroup$ – Will Sawin Jul 11 at 16:42
  • $\begingroup$ Ah, I've realized that this answers the question I asked, but not the question I was thinking of, which was the relative constructibility question. Given points, can you still construct the same points relative to them? In other words, is the tool set fully equivalent? (Meanwhile, Will, please post your comment as an answer.) $\endgroup$ – Joel David Hamkins Jul 11 at 16:45
  • 2
    $\begingroup$ For the difficult case you mention, suppose you have two points P and Q that are very far apart. Suppose you pick a line leaving $P$, approximately in the direction of $Q$, and count along it, one unit interval at a time, until you reach a point $R$ within one unit interval of $Q$, after $n$ unit intervals in total. Then to construct the line from $P$ to $Q$ we need to take $Q-R$, shrink my a factor of $n$, and then translate it to the point one unit interval off from $P$. These steps all seem like they can probably be done with a bounded straightedge but I didn't check. $\endgroup$ – Will Sawin Jul 11 at 16:52
  • $\begingroup$ @WillSawin That is what I was trying to do, but didn't see how to carry out the scaling part. If you could post an answer, I'd be grateful. $\endgroup$ – Joel David Hamkins Jul 11 at 16:54
  • 4
    $\begingroup$ "approximately in the direction of" is a tall order if P,Q are far away and you must get within one unit. A more robust solution is to tile the plane with squares (or even parallelograms) and count to determine the coordinates $(a,b)$, and thus also $(a/n,b/n)$, within one unit. (We can construct the tiling in square-spiral order to make sure we get from P to Q in a finite number of steps.) $\endgroup$ – Noam D. Elkies Jul 11 at 16:58
27
$\begingroup$

A bounded-length straightedge can emulate an arbitrarily large straightedge (even without requiring any compass), so the rusty compass theorem is sufficient.

Note that, in particular, it suffices to show that there exists an $\varepsilon > 0$ such that a straightedge of length $1$ is capable of joining two points separated by any distance $\leq 1 + \varepsilon$ (and therefore emulates a straightedge of length $1 + \varepsilon$, and therefore arbitrarily long straightedges by iterating this process).

We can use Pappus's theorem to establish this result for any $\varepsilon < 1$:

https://en.wikipedia.org/wiki/Pappus%27s_hexagon_theorem

In particular, given two points $A$ and $c$ (separated by a distance slightly greater than 1) which we wish to join, draw a line $g$ through $A$ and a line $h$ through $c$ which approach relatively close to each other. Then add arbitrary points $B, C$ on $g$ and $a, b$ on $h$ such that the four new points are within distance $1$ of each other and the two original points. We assume wlog $b$ is between $a, c$ and $B$ is between $A, C$.

Then we can construct $X$ by intersecting the short (length $< 1$) lines $Ab, Ba$, and construct $Z$ by intersecting the short lines $Bc, Cb$. Then $Y$ can be constructed by intersecting the short lines $XZ$ and $Ca$.

Now, $Y$ is positioned collinear with $A$ and $c$ and between them, so we can use it as a 'stepping stone' to draw a straight line between $A$ and $c$.

The result follows.

EDIT: I decided to do this with the edge of a coaster and two points slightly too far apart to be joined directly:

Demonstration of algorithm

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ The construction means that you can henceforth proceed as though you have a length-$(1 + \varepsilon)$ straightedge instead of a length-$1$ straightedge. By the same argument, you can proceed as though you have a length-$(1 + \varepsilon)^2$ straightedge (by using the length-$(1 + \varepsilon)$ straightedge to draw each line in the diagram). $\endgroup$ – Adam P. Goucher Jul 11 at 17:27
  • 5
    $\begingroup$ Note that this naive recursive approach means that, in particular, joining two points separated by a distance of $(1 + \varepsilon)^n$ would take $10^n$ applications of the original straightedge! (It's still polynomial in the length, though, so not too bad.) $\endgroup$ – Adam P. Goucher Jul 11 at 17:30
  • $\begingroup$ Thanks for your excellent answer. This is great! $\endgroup$ – Joel David Hamkins Jul 12 at 8:30
  • 1
    $\begingroup$ See also this 2008 article (in French) by Xavier Caruso xavier.toonywood.org/papers/publis/troppetit.pdf, which seems to use the same method. $\endgroup$ – Joel David Hamkins Jul 12 at 8:32
  • 2
    $\begingroup$ @Goucher. Note that one can do an arbitrary line of lenght n by n applications of the ruler. So the arbitrary lines can solve the problem in one step, if you're lucky enough. That makes it seem like your argument is way to pessimistic. On the other hand, it seems that there is a carpenters way, but no mathematicians way to select the directions. Next thing you know the problem is NP complete. Groetjes Albert $\endgroup$ – Albert van der Horst Jul 12 at 8:57
0
$\begingroup$

@joel-david-hamkins Indeed I was too pessimistic. Instead of tiling one could proceed with 4 perpendicular lines shooting from each point. Prolong them in turn. After a certain number of steps O(L/l) you will find an intersection. Here L is the distance between the points and l is the length of the ruler.

| cite | improve this answer | |
$\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.