Forging Your Signature with a Linkage Mechanism: Kempe's Theorem

In this post I'll tell you about a program that forges any signature using a linkage mechanism. The program is based on Kempe's theorem, proved in the mid-19th century.

Kempe's Theorem

With the development of technology and the advent of trains, inquisitive minds faced a very interesting problem: is it possible to create a linkage mechanism that converts circular motion into motion along a straight line — in other words, one that draws a straight line? A linkage mechanism is a collection of rods connected to each other that can freely rotate at their connection points. Many scientists struggled with this problem, inventing ingenious mechanisms, but all of them drew imprecise straight lines. Here, for example, are the mechanisms of Watt, Chebyshev, and Hoeken.

Many mathematicians believed that the problem of creating a linkage mechanism that draws an ideal straight line was fundamentally unsolvable, until in the mid-19th century the ingenious Peaucellier-Lipkin linkage was discovered, which draws an exact straight line.

In this mechanism, all rods of the same color have the same length. You can prove that the mechanism indeed draws a straight line by direct computation — brute force, so to speak. But people familiar with the inversion transformation can see fairly clear logic in the proof. By the time the Peaucellier-Lipkin linkage was invented, lubricants had already become good enough that technology could get by without this ideal converter to linear motion. After all, you can transmit nearly-linear motion to a piston through another rod. This rod won't always be perfectly parallel to the piston's guide rail, but that's nothing terrible. As a result, the Peaucellier-Lipkin linkage never found widespread use in technology, but it had an enormous influence on mathematics.

A few years later, the mathematician-lawyer Kempe presented an algorithm for constructing, for absolutely any algebraic curve in the plane, a linkage mechanism that can draw only that curve and nothing else. In other words, there exists a mechanism constrained to one degree of freedom. Moving along this degree of freedom, the mechanism draws our algebraic curve. I found an excellent exposition of Kempe's proof in this article. Let me remind the reader that algebraic curves are curves defined by the equation P(x,y)=0, where P is any polynomial. For example, x² + y² = r² is a circle of radius r, y = ax + b is an inclined line, y = ax² + bx + c is a parabola. In his proof, Kempe uses many interesting ideas, but the key construction tool is the already-familiar Peaucellier-Lipkin linkage.

The Process

As soon as I learned about Kempe's theorem, I immediately wanted to write a program in which the user could draw any curve — say, their signature — and the program would approximate the signature with an algebraic curve, and then use Kempe's algorithm to build a linkage mechanism that forges it. I really wanted to make a web application so the user wouldn't need to install anything on their computer — they could just visit the site and launch everything "in one click". Since I'm not a programmer, this was also a wonderful opportunity for me to get acquainted with JavaScript and HTML5.

After I learned Kempe's proof, I faced a very serious problem: how to approximate a signature with an algebraic curve P(x,y)=0 with good accuracy, quickly, and on top of that in slow JavaScript? There exists a very simple but unsuitable method of approximating a curve by a union of small circles scattered along the curve.

Each small i-th circle is obviously an algebraic curve, since it's defined by the polynomial equation (x-a_i)² + (y-b_i)² = r_i², where (a_i, b_i) is the center of the circle and r_i is its radius. The union of all small circles will obviously also be an algebraic curve, since this union is defined by a polynomial equation. But as you can see, this type of approximation is completely unsuitable for us, because too many self-intersection points arise. We would like to have a more "elegant" approximation. It turns out that the problem of "elegant" approximation is difficult both mathematically and computationally. To get a feel for this, it's useful to imagine the algebraic curve P(x,y)=0 as the intersection of the surface z = P(x,y) and the plane z=0. The line of intersection is very sensitive to the coefficients of the polynomial P — it can be disconnected in a completely uncontrolled way, have branch points, and this is what ruins the "elegance" of the approximation.

After a week of experimenting with various algorithms, all my attempts to approximate the curve in any way proved futile. All algorithms were very slow and produced poor results. I had almost given up, having previously posted a question on MathOverflow, where traditionally many professional mathematicians hang out. In the question, I casually mentioned that I needed this in order to forge signatures with linkages. Imagine my surprise when, a day or two later, mathematician Mikhail Kapovich responded. He hit the nail right on the head. It turned out that he had once worked on Kempe's theorem and, together with John Millson, in their paper had proved that one can build linkage mechanisms not only for algebraic curves, but also for curves that are more naturally suited to approximation problems — namely, for curves defined parametrically by polynomial expressions.

Such curves are extremely easy to use for approximating any continuous curves, including our signature. You can approximate using so-called Chebyshev polynomials, or you can first approximate with Fourier series and then approximate the trigonometric functions in the Fourier series with Taylor series. It turns out that instead of trying to approximate the curve with algebraic curves, it's better to modify Kempe's proof itself and learn to build linkage mechanisms that can draw curves more suitable for approximation tasks.

The whole experience felt like finding an enormous diamond. But to my shame, I didn't fully understand that paper. It's written in rather complex terms. But the very fact that a solution to my problem existed opened my eyes. I figured out that with a minor modification to the original Kempe proof, one can build linkages that draw cosinusoidal trigonometric curves.

These curves make it even easier to approximate our signature (via Fourier series theory) than the curves from the Kapovich-Millson paper. Indeed, from Fourier series theory it follows that on an interval, the functions x(t) and y(t) can be expanded in a cosine series. The coefficients are easily found: you simply multiply both sides by a cosine and integrate, and then almost all integrals on the right-hand side vanish.

I spent a very long time thinking about whether to include in this post the algorithm for constructing the linkages that draw these trigonometric curves. Then I realized that it would add mathematical tedium to the text. People usually don't like reading long proofs in this kind of writing. So I'll simply provide a link — the curious can take a look.

And here is the application itself that forges your signature: david.wf/linkage. Please note that you can move the construction with the mouse and zoom in/out with the scroll wheel (the degree of approximation can also be changed with a special "approximation" slider). The application works on modern browsers — I haven't tested it on older ones. It lags least on Chrome, since Chrome is much faster than other browsers at drawing straight lines. I must admit I spent a lot of effort on optimization so that nothing would lag on weak computers, but, honestly, I didn't achieve much success. Let me emphasize again: the linkage that the program builds cannot draw anything except your signature. The linkage is driven by a rotating blue triangle — the "motor".