Sewing without Calculus

Buffon's needle is deeply unsatisfying: a question with only a passing relationship to circles (the needle can fall in any orientation -- but there's still the small matter of lateral motion!) ends up connected to π. Why?

The standard proof -- above in devout's writeup, with integrals -- does little to explain the mysterious appearance of π. Calculation is often like that.

Geometric measure theory offers a "clean" proof, one that almost does explain where π comes from. And it goes like this.

1. We are interested in the probability "p_L" that a needle of length L, randomly dropped on a surface ruled with lines at interval 1 from each other, will intersect a line. Suppose L≤1. Then almost always the needle can intersect at most 1 line, so either it intersects 1 line (with probability p_L) or it intersects 0 lines (with probability 1-p_L). Thus we may take the expectation to get the probability:

   p_L = e(L) = E(number of intersections of a needle of length L with a line)

2. Suppose we connect 2 needles of lengths L and M at their edge (not necessarily in a straight line -- we're interested in a crooked needle). Since expectation is linear, the expected number of intersections of our crooked needle with a line is

   e(L+M) = e(L) + e(M)

   (Note that our notation e(L+M) ignores the shape of the needle, as the RHS does not depend on this shape!). Naturally, we can do this for any number of needles glued at their ends. So e is a linear function, and e(t)=ct for some constant c.
3. We wish to find c -- then we will be able to determine e(L) and, especially, e(1).
4. By using our favourite convergence theorem on expectation (e.g., the monotone convergence theorem) we see that for any curve with length L, if we drop it at random, the expected number of intersections with a line will be e(L)=cL.
5. OK, so let's pick a particularly easy curve. Take the circle of diameter 1. Its perimeter is π, so the expected number of intersections of a circle of diameter 1 with a surface ruled with lines at interval 1 is e(π)=cπ. On the other hand, no matter how we drop this circle, it always intersects exactly 2 lines! So e(π)=2, and therefore c=2/π, as required.

QED.

---

The proof above is based on what appears in the introduction to

• Daniel A Klain and Gian-Carlo Rota, Introduction to Geometric Probability, Lezioni Lincee, published Cambridge University Press 1997.

Naturally, that book goes considerably further -- and generally in more algebraic directions.

Emil Post's work on undecidability is often overshadowed by the contributions of his more famous contemporary, Alan Turing. The undecidable nature of the halting problem has an elegant proof itself, but emulating Turing machines in other problems to prove their undecidability is a delicate and messy business. Post's Correspondence Problem, introduced in 1946, is a more natural fit for this role, and since it can itself mimic the halting problem, is of equal power in proving undecidability. Thus it found application to formal language theory; it can also be elegantly applied to the analysis of communication protocols, which I wish to cover here.

Post's Correspondence Problem

Firstly, here's an easy way to understand Post's Correspondence Problem. Imagine a particularly fiendish variant of Scrabble, whereby the tiles are split, like dominoes, into two halves, each bearing a string of letters. The question is, can we line up some (non-zero) number of tiles so that the top and botttom halves both spell out the same 'word' (simply a string of letters)? The types of tiles are fixed, but you may use as many of each type as you wish.

For instance, if our tile set is the following:

   _______      _______      _______
  |       |    |       |    |       |
  |   a   |    | abaaa |    |   ab  |
  |   -   |    |   -   |    |   -   |
  |  aaa  |    |   ab  |    |   b   |
  |_______|    |_______|    |_______|      

     (1)          (2)          (3)

Then the arrangement (2)(1)(1)(3) gives the 'word' abaaa a a ab = abaaaaaab on the top, and ab aaa aaa b = abaaaaaab on the bottom: that is, we have a match.

As observed above, the general form of this innocent-looking problem is undecidable: no program can take an arbitrary set of tiles A_i= g_i/h_i and decide whether there are matching sequences g_(i1)...g_(in)=g=h=h_(i1)...h_(in).

The Secrecy problem

The secrecy problem is the obvious question in the analysis of cryptographic protocols: given a protocol and some intended secret S, can an intruder intercept S? Answering this question depends of course on the powers attributed to the intruder, and the restrictions placed on the protocol. But I'll demonstrate here how even a fairly restricted definition of protocol - exploiting neither unbounded parallel sessions nor unbounded numbers of nonces (in fact, no nonces will be required at all!) - reduces to PCP. This means of course that secrecy is undecidable, else we'd be able to determine the answer to arbitrary PCP instances by encoding them into secrecy problems and answering those.

Reduction of Secrecy to PCP

The trick to proving undecidability of secrecy is to convert the correspondence problem into a communication protocol, in such a way that the secret is disclosed if and only if the encoded PCP has a solution. We give each tile to a participant; the holder of tile i will be called Appender_i. There will also be two other legitimate participants, the Initiator and the compromiser. The Appenders, Initiator and compromiser are all assumed to share a secret key which is unknown to any intruder.

To start a run of the protocol, the Initiator encrypts a pair of messages, both consisting of the empty string, into a packet and sends it to any other participant. Any Appender receiving a packet decrpyts it, and changes the strings by appending the top half of their tile to the first string and the bottom half to the second string. They then pair these two new strings together, encrpyt into a packet, and send to anyone other than the initiator. In this way, candidates for matching strings are generated, under encryption.

Should the compromiser receive a packet containing two identical non-empty strings, they send back the secret message S "in the clear" - that is, without any encryption. So an intruder will discover the secret iff the compromiser receives a solution to the PCP problem, and thus only iff such a solution exists.

For the PCP instance above, the secret would be disclosed as follows. Firstly, the initiator sends a pair of empty strings to Appender₂. He examines his tile, and creates a pair (abaaa,ab) which is sent (encrypted) to Appender₁. She adds the contents of her tile, producing (abaaaa,abaaa) then sends this to herself for another round, creating (abaaaaa,abaaaaaa). This time she sends it to Appender₃, who generates (abaaaaaab,abaaaaaab) and forwards this to the compromiser. He discovers the two strings match, so sends S back to Appender₃, which, bereft of encryption, is then known to any eavesdropper.

We can formalise all this as follows, firstly fixing some notation: Let the i^th tile have g_i written on the top half, and h_i written on the bottom half: an empty string of no letters will be denoted by e, an arbitrary string by a capital letter, an arbitrary letter by s and the concatenation of strings simply by writing them next to each other. Let K be a key shared between each of the Appender_is, the initiator and the compromiser; P be any participant other than the initiator, and S the secret. This gives roles for the legitimate participants as follows:

Initiator role
Init-->P: {(e,e)}_K

Appender roles (one for each tile)
(P or Init)-->Appender_i: {(X,Y)}_K
Appender_i-->P: {(Xg_i,Yh_i)}_K

Compromiser role
P-->Comp: {(Xs,Xs)}_K
Comp-->P: S

Which would give a secret-disclosing run of our example as follows:

Init-->Appender₂: {(e,e)}_K
Appender₂-->Appender₁: {(abaaa,ab)}_K
Appender₁-->Appender₁: {(abaaaa,abaaa)}_K
Appender₁-->Appender₃: {(abaaaaa,abaaaaaa)}_K
Appender₃-->Comp: {(abaaaaaab,abaaaaaab)}_K
Comp-->Appender₃: S

Thus, since such a run is one of the many possibilities for this protocol, secrecy is not guaranteed. Since the existence of the compromising run depends on the existence of a PCP solution, the secrecy problem is hence undecidable.

Criticisms and variations

The analysis of cryptographic protocols is made difficult by various sources of infinity- a priori, the number of sessions, the number of nonces, and the length of messages could all be unbounded. The example above is particularly devastating since it does not require the first two of these. However, since Post's Correspondence Problem does not restrict the number of tiles used the messages involved are of unbounded length. This, coupled with the 'blind copying' ability such as that of the Appender roles, means we can encode computational models.

However, there is a strong criticism that these protocols are pathological examples: they serves no useful communication purpose, having been crafted with the benefit of an intruder in mind and to prove the existence of a reduction. But practical interest is not in the class of all protocols, but of all that we might wish to use- those with an 'honest run' whereby all the roles introduced are necessary components for some legitimate purpose such as authentication. We cannot exclude blind copying completely, however, since such manipulations are necessary in, for instance, key exchange via a trusted server.

Decidability of secrecy remains an open problem for protocols with honest runs restricted to either bounded message size; or such that participants may make only a single blind copy. Sadly, even with the 'honest run' requirement, unbounded message size gives rise to an undecidable secrecy problem, but there is a decidable case: bounded nonces with participants allowed only a single blind copy.

References

CM30071: Logic and its Applications Undergraduate module, Computer Science Dept., University of Bath.
Formal analysis of Cryptographic Protocols Taught Postgraduate course, Laboratory for Foundations of Computer Science, University of Edinburgh.
Wikipedia: Emil Post, Post's Correspondence Problem.

There are a few trigonometric expressions that are also undefined, but they are mostly 'divide by zero' things. They are:

tan 90°, sec 90°, cosec 0°, cot 0°

Also, in the number set R (all real numbers), the square root of any negative number is undefined; and in any number set (N,J,Q,R,C), you cannot yet divide by zero.

A slightly altered version of mdwyer's tale of the squaw of Sohcahtoa.

A tribe of Native Americans generally referred to their womenfolk by the animal hide with which they made their blankets. Thus, one woman might be known as Squaw of Buffalo Hide, while another may be known as Squaw of Deer Hide. This tribe had a particularly large and strong woman with a unique animal hide for her blanket. She was known as Squaw of Hippopotamus Hide, and she was as strong and powerful as the animal from which she made her blanket.

Each year, she entered the tribal wrestling contest, and easily defeated all challengers, male or female. As the men of the tribe admired her strength and power, this made many of the other women of the tribe quite jealous. So one year, two of them decided to enter their sons into the tournament as a team. The Chief of the tribe agreed.

As luck would have it, the team met the squaw in the final. As the match began, it became clear that the squaw had finally met her match. The two sons wrestled and struggled as much as they could, but they could not bring her down. Likewise, the squaw did not give in, and tried unsuccessfully to become champion again. Finally, the Chief intervened and declared that, in the interests of health and safety, the match was to be terminated and the winner would be decided by himself. With that, he retired to his teepee.

For days, the Chief could not pick a winner. While the two young men had matched the squaw's power, the Chief found it difficult force the squaw to relinquish her championship. After all, it had taken two men to finally provide her with a decent challenge. What to do? Then the Chief remembered Pythagoras, a visitor from Greece who was staying with the tribe for a while. Pythagoras sat down in the Chief's teepee, thinking, and after a few moments, it came to him. He exited the teepee, called the tribe to assembly, and announced his decision:

"The Squaw of the Hippopotamus is equal to the sons of the squaws of the other two hides."

Source: Mensa Maths Wizard for Kids (1998)

---

By the way, another way to remember SOHCAHTOA would be:

• Some
• Old
• Hairy (or heavy)
• Cows
• Are
• Hairier (or heavier)
• Than
• Others
• Are

Then again, you can also just say to yourself "Soccer-toe-ah."

A hybrid graph, in mathematics, is a graph with multiple rules for x. It usually results in an irregularly-shaped graph, sometimes with an open or closed circle, both indicating discontinuity.

A typical hybrid graph, and its corresponding rule, would look like:

       _
      | x if x<-1
f(x)=-| 1 if -1<x<1
      |_-x if x>1

              |
           o--|--o
              |
              |
           -1 |  1
-----------o--|--o----------
          /   |   \
         /    |    \
        /     |     \
       /      |      \
      /       |       \

The graph can be differentiated at all points except those where there is discontinuity. For this hybrid:

• d/dx=1 if x<-1
• d/dx=0 if -1<x<1
• d/dx=-1 if x>1

Which means that the following is a graph of d/dx for this particular hybrid:

              |
-----------o  |1
              |
              |
          -1  |  1
-----------o=====o----------
              |   
              |    
              |     
            -1|  o----------   
              |       

Examples of other hybrid functions include the absolute value, or modulus, function (where y=√x², xεR) or the greatest integer function.

Hybrids commonly have no set rule, but are found on statistical graphs, such as stock exchange graphs.

See also piecewise function.