Month: February 2023

Bounding derivatives of the sinc function

Posted on by John

The sinc function is defined either as sin(x)/x or as sin(πx)/πx. We’ll use the former definition here because we’ll cite a paper that uses that definition.

Here’s a plot of the sinc function and its first two derivatives.

Thomas Grönwall proposed a problem to the American Mathematical Monthly in 1913 [1] bounding the derivatives of the sinc function:

\left| \frac{d^n}{dx^n} \frac{\sin x}{x}\right| \leq \frac{1}{n+1}

Seven years later, Dunkel gave an elegant proof. Perhaps Grönwall had a proof and was proposing his inequality as a challenge, or maybe it was a conjecture at the time he published it. In any case, the proof by Dunkel is very nice. He sets

y = sin(x)/x

and repeatedly differentiates both sides of the equation

xy = sin(x).

See the details in Dunkel’s solution.

I don’t know of an application of Grönwall’s inequality offhand. But the sinc function is common in signal processing, and so maybe his inequality has applications there.

(By “Grönwall’s inequality” I mean the inequality above. There is another theorem also known as Grönwall’s inequality that is commonly applied in differential equations.)

[1] Gronwall, T. H. (1913). Problem 339. Amer. Math. Monthly. 20: 196.

[2] Dunkel, O., (1920). Solution to Problem 339. Amer. Math. Monthly. 27: 81–85.

Another Napoleon-like theorem

Posted on by John

A little while back I wrote about Napoleon’s theorem for triangles. A little later I wrote about Van Aubel’s theorem, a sort of analogous theorem quadrilaterals. This post presents another analog of Napoleon’s theorem for quadrilaterals.

Napoleaon’s theorem says that if you start with any triangle, and attach equilateral triangles to each side, the centroids of these new triangles are the vertices of an equilateral triangle.

So if you attach squares to the sides of a quadrilateral, are their centroids the vertices of a square? In general no.

But you can attach squares to two sides, and special rectangles to the other two sides, and the centroids will form the corners of a square. Specifically, we have the following theorem by Stephan Berendonk [1].

If you erect squares on the two “nonparallel” sides of a trapezoid and a rectangle on each of the two parallel sides, such that its “height” is equal to the length of the opposite side of the trapezoid, then the centers of the four erected quadrangles will form the vertices of a square.

Here’s an illustration. Berendonk’s theorem asserts that the red quadrilateral is a square.

[1] Stephan Berendonk. A Napoleonic Theorem for Trapezoids. The American Mathematical Monthly, April 2019, Vol. 126, No. 4, pp. 367–369

Playfair cipher

Posted on by John

The Playfair cipher was the first encryption technique to encrypt text two letters at a time. Instead of substituting one letter for another, it substitutes one pair of letters for another pair. This makes the method more secure than a simple substitution cipher, but hardly secure by modern standards.

The Playfair cipher was used (and broken) during the first world war. I vaguely remember reading somewhere that the cipher took about an hour to break using pencil and paper. It was secure in the sense that it could be used for messages that only needed to be secure for less time than it took to break the method. It was more secure than simple substitution, and easy to encrypt and decrypt manually.

True to Stigler’s law of eponymy, the Playfair cipher was not named after its inventor, Charles Wheatstone of Wheatstone bridge fame, but after Lyon Playfair who popularized the method. Playfair acknowledged Wheatstone, but his name stuck to the method nevertheless.

Message preparation

The Playfair cipher uses a 5 × 5 grid of letters, so some letter of the Roman alphabet has to go. A common choice was to use the same letter for I and J. (A variation on the method using a 6 × 6 grid of letters and digits would not have to leave out any letters.)

For reasons that will soon be apparent, double letters had to be broken up, say with an X. So “FOOTBALL” would become “FOXOTBALXL.” Amusingly, “MISSISSIPPI” would become “MISXSISXSIPXPI.”

After eliminating Js and splitting double letters, the message is divided into pairs. So FOXOTBALXL becomes FO XO TB AL XL.

Encryption algorithm

The key for the encryption method is the arrangement of the letters in a square. In practice, the key would be some word or phrase that was used to permute the alphabet, and then that permutation was filled into the grid.

Here’s a grid I constructed by asking Python for a random permutation of the alphabet.

IFTVX PCGDY RNHQK EBSLA OUMWZ

Given a pair of letters, the two letters either lie on the same row, the same column, or are in different rows and columns. (This is why you break up double letters.)

If the two letters lie in the same row, advance each letter one position, wrapping around if necessary. For example, IT would be encrypted as FV, and TX would be encrypted as VI.

If two letter line in the same column, proceed analogously, moving each letter down. So TH would be encrypted as GB and OI would be encrypted as IP.

Finally, if the two letters are in different rows and columns, they form the diagonal corners of a rectangle. Replace the two letters with the letters on the remaining corners. For example, IH becomes TR, HE becomes RB, GW becomes DM, etc.

Cryptanalysis

Just as you can attack a simple substitution cipher by looking at letter frequencies, you can attack a Playfair cipher by looking at bigram frequencies. You can find these frequencies for English text on Peter Norvig’s site. TH sticks out in bigram frequencies similarly to how E sticks out in letter frequencies. However, bigram frequencies are more evenly distributed than letter frequencies.

As I pointed out in the previous post, making a mapping between 676 pairs of letters to a randomly generated list of 676 other pairs of letters will not create a secure cipher. But Playfair is much weaker than such a random assignment. There is a lot of structure to the Playfair cipher. This makes it more convenient to use, and easier to break.

Suppose pairs of letters where mapped to random pairs of letters and you learn that GB is the encrypted form of TH. What have you learned about decrypting any other pair? Nothing, except that you’ve eliminated 1 out of 676 possibilities.

But if you learn that a Playfair cipher sends TH to GB, you learn that either (1) T, H. G, and B all lie in the same row or column, or (2) that T and B are in the same column, G and B are in the same column, T and G are in the same row, and H and B are in the same row.

Symmetry

If we rotate the rows or columns in our encryption matrix, nothing changes. This is easy to see in the case when two letters are in the same row or in the same column. It’s a little harder to see but still true when the letters are in different rows and columns.

For example, consider the following encryption matrix, formed by rotating the columns two positions and the rows one position.

GDYPC HQKRN BLAES MWZOU TVXIF

If you work through all the examples above, you’ll see that they remain the same. IT still goes to FV etc.

The reason rotating columns or rows doesn’t make a difference is that in matrix notation, the encryption algorithm does not depend on the subscripts per se but the difference in subscripts mod 5.

It almost doesn’t matter if you transpose the encryption matrix. If you transpose a matrix, elements that were in the same row are now in the same column and vice versa. When two letters are not in the same row or column, transposing the encryption matrix transposes the encrypted pair. In the example above HE goes to RB. If we transpose the encryption matrix, HE goes to BR.

We said above that the key to a Playfair cipher is a permutation of the alphabet. But many keys correspond to the same encryption mapping. The analyst doesn’t need to recover the original encryption matrix but only some rearrangement of it.

Related posts

Simple substitution ciphers over a gargantuan alphabet

Posted on by John

Simple substitution ciphers replace one letter with another. Maybe A goes to W, B goes to G, C goes to A, etc.

These ciphers are famously easy to break, so easy that they’re common in puzzle books. Here’s one I made [1] for this post in case you’d like to try it.

X RF SXIIXKW XK IYZ UXINYZK HT IYZ CXIICZ YHJSZ RI FZGTXZCG, HJQ SZNHKG TRQF BYXNY XS NJI HTT EV IYZ QXGWZ RKG R MJRQIZQ-FXCZ RNQHSS IYZ TXZCGS TQHF HJQ YHFZ LCRNZ, BYZQZ VHJ RQZ. X RF BQXIXKW R EHHU. XK XI X RF SLZRUXKW IH VHJ. EJI X RF RCSH SLZRUXKW IH IYZ BHQCG. IH EHIY X HBZ RK RNNHJKIXKW.

As is common in puzzle books, I kept the spaces and punctuation.

When you learn that simple substitution is breakable, you might reasonably think that the problem is the small alphabet size. What if you replaced pairs of letters with pairs of letters, effectively working over an alphabet of size 26² = 676. That’s an improvement, but it’s still not secure. It could be broken manually in a few hours, depending on the length of the text, and of course could be broken quickly using a computer.

If we want a cipher to be secure against computer-aided cryptanalysis, we’re going to need a much bigger alphabet.

The Roman alphabet has 26 letters, which can be expressed in 5 bits. Pairs of Roman letters would require 10 bits. What if we used a 32-bit alphabet, substituting 32-bit sequences with other 32-bit sequences? This is working over an alphabet of over 4 billion symbols. Surely that’s secure? Nope.

What if we use blocks of 128 bits? This is working over an alphabet of size

2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456.

Nope. Still not good enough. Because you can see the penguin.

Original encrypted Tux image

The image above is a famous example of a downfall of simple substitution, albeit over a gargantuan alphabet. The image was created by taking a graphic of the Linux mascot and encrypting the bits using 128-bit encryption. Each block of 128 bits goes to a unique, essentially random replacement. Each block is well encrypted. But there are repetitive blocks in the original that become repetitive blocks in the encrypted version.

The AES (Rijndael) encryption algorithm is a good algorithm, but in the example above it was used poorly. It was used in electronic code book mode (ECB), something that nobody would do in practice.

In practice, you might do something like cipher block chaining where you XOR each block with the encrypted version of the previous block. You could think of this as a clever way of using a simple substitution over an enormous alphabet. You look up the substitution of each block, but then XOR its bits with the previously encrypted block. Now repetitive input does not produce repetitive output. You cannot see the penguin. The penguin image becomes random-looking static.

Related posts

[1] I produced the cryptogram using

    cat myfile | tr [a-z] [A-Z] | tr [A-Z] ...

where “…” is a permutation of the 26 upper case letters.

How Mr. Bidder calculated logarithms

Posted on by John

George Parker Bidder (1806–1878) was a calculating prodigy. One of his feats was mentally calculating logarithms to eight decimal places. This post will explain his approach.

I’ll use “log” when the base of the logarithm doesn’t matter, and add a subscript when it’s necessary to specify the base. Bidder was only concerned with logarithms base 10.

Smooth numbers

If you wanted to calculate logarithms, a fairly obvious strategy would be to memorize the logarithms of small prime numbers. Then you could calculate the logarithm of a large integer by adding the logarithms of its factors. And this was indeed Bidder’s approach. And since he was calculating logarithms base 10, so he could make any number into a integer by shifting the decimal and then subtracting off the number of places he moved the decimal after taking the log of the integer.

Numbers with only small prime factors are called “smooth.” The meaning of “small” depends on context, but we’ll say numbers are smooth if all the prime divisors are less than 100. Bidder knew the logs of all numbers less than 100 and the logs of some larger numbers.

Rough numbers

But what to do with numbers that have a large prime factor? In this case he used the equation

log(a + b) = log(a(1 + b/a)) = log(a) + log(1 + b/a).

So if a number n doesn’t factor into small primes, but it is close to a number a that does factor into small primes, you’re left with the problem of finding log(1 + b/a) where b = n − a and the fraction b/a is small.

At this point you may be thinking that now you could use the fact that

log(1 + x) ≈ x

for small x. However, Bidder was interested in logarithms base 10, and the equation above is only valid for natural logarithms, logarithms base e. It is true that

loge(1 + x) ≈ x

but

log10(1 + x) ≈ log10(e) x = 0.43429448 x.

Bidder could have used 0.43429448 x as his approximation, but instead he apparently [1] used a similar approximation, namely

log(1 + b/a) ≈ log(1 + 10−m) 10m b/a

where b/a is between 10−m−1 and 10−m. This approximation is valid for logarithms with any base, though Bidder was interested in logs base 10 and had memorized log101.01, log101.001, log101.0001, etc. [2]

Finding nearby smooth numbers

To get eight significant figures, the fraction b/a must be on the order of 0.001 or less. But not every number n whose log Bidder might want to calculate is so close to a smooth number. In that case Bidder might multiply n by a constant k to find a number so that kn is close to a smooth number, take the log of kn, then subtract log k.

Smith says in [1] “For example, to obtain log 877, he would multiply 877 by 13, which gives 11,401, or 600 × 19 + 1.” Then he could calculate

log(877) = log(13*877) −- log(13) = log(11400) + log(1/11400) − log(13)

and use his algorithm for approximating log(1/11400).

I can’t imagine thinking “Hmm. 877 isn’t close enough to a smooth number, but if I multiply it by 13 it will be.” But apparently Bidder thought that way.

Related posts

Here is a simple way to approximate logarithms to a couple significant figures without having to memorize anything.

See also this post on mentally calculating other functions to similar accuracy.

Notes

[1] This equation comes from The Great Mental Calculators by Steven B. Smith. Bidders methods are not entirely known, and Smith prefaces the approximation above by saying “it appears that Bidder’s approximation was …”.

[2]

|-------+-------------|
|     x | log_10(1+x) |
|-------+-------------|
| 10^-2 |  0.00432137 |
| 10^-3 |  0.00043408 |
| 10^-4 |  0.00004342 |
| 10^-5 |  0.00000434 |
| 10^-6 |  0.00000043 |
| 10^-7 |  0.00000004 |
|------+--------------|

Sines of integers

Posted on by John

The sine function has period 2π, an irrational number. and so if we take the sines of the integers, we’re going to get a somewhat random sequence. (I’m assuming, as always that we’re working in radians. The sines of integer numbers of degrees are much less interesting.)

Here’s a plot of the sines of 0, 1, 2, …, 99.

The points are not literally random, but they’re what Marsaglia would call higgledy-piggledy [1].

Since the points are higgledy-piggledy, it doesn’t seem possible that we could find a lower bound on |sin(n)|, but there is one. For all positive integers n,

|sin(n)| > 2−n.

This result may be due to Christopher Stuart, but in any case he proved [2] a stronger version of this theorem, showing that the 2 on the right hand side can be replaced with any number

α > (sin(3))−1/3 = 1.9207….

Related posts

[1] “If the numbers are not random, they are at least higgledy-piggledy.” — RNG researcher George Marsaglia

[2] Christopher Stuart. An Inequality Involving sin(n). The American Mathematical Monthly , Feb 2018, Vol. 125, No. 2, pp. 173–174

Derive or memorize?

Posted on by John

A lot of smart people have a rule not to memorize anything that they can derive on the spot. That’s a good rule, up to a point. But past that point it becomes a liability.

Most students err on the side of memorizing too much. For example, it’s common for students to memorize three versions of Ohms law:

  • V = IR
  • I = V/R
  • R = V/I.

Not only is this wasteful, tripling the number of facts to remember, it’s also error prone. When you memorize things without understanding them, you have no way to detect mistakes. Someone memorizing the list above might think “Is I = V/R or R/V?” but someone who knows what the terms mean will know that more resistance means less current, so the latter cannot be right.

I got through my first probability class in college without memorizing anything. I worked every problem from first principles, and that was OK. But later on I realized that even though I could derive things from scratch every time I needed them, doing so was slowing me down and keeping me from seeing larger patterns.

The probability example stands out in my mind because it was a conscious decision. I must have implicitly decided to remember things in other classes, but it wasn’t such a deliberate choice.

I’d say “Don’t memorize, derive” is a good rule of thumb. But once you start to say to yourself “Here we go again. I know I can derive this. I’ve done it a dozen times.” then maybe it’s time to memorize the result. To put it another way, don’t memorize to avoid understanding. Memorize after thoroughly understanding.

Related post: Just-in-case versus just-in-time

Divisibility by base + 1

Posted on by John

To test whether a number is divisible by 11, add every other digit together and subtract the rest of the digits. The result is divisible by 11 if and only if the original number is divisible by 11.

For example, start with n = 31425. Add 3, 4, and 5, and subtract 1 and 2. Since 3 + 4 + 5 − 1 − 2 = 9, and 9 is not divisible by 11, neither is 31425.

For another example, take 349041. We have 3 + 9 + 4 = 16, and 4 + 0 + 1 = 5, and 16 − 5 = 11. Since 11 is obviously divisible by 11, so is 349041.

The same trick that works for testing base 10 numbers for divisibility by 11 works for testing base 16 numbers for divisibility by 17. More generally, it works for testing base b numbers for divisibility by b+1.

Let m = b + 1. Then

b \equiv −1 \pmod m

which implies

\sum_{n=0}^N a_nb^n \equiv \sum_{n=0}^N a_n(-1)^n \pmod m

Here an is the nth digit of a number in base b, numbering the digits from the least significant, counting from 0.

Sometimes a rule for testing divisibility by m will also tell you the remainder when a number is divided by m, but sometimes not. The method presented here will give you the remainder by b + 1, but only if you start adding up digits from the right end. Note in the proof that the digits in even positions (counting from 0) have a positive coefficient and the digits in odd positions have a negative coefficient.

For example, let’s look at 1EDA86hex in hexadecimal (base 16). If we add 6, A, and E, and subtract 8, D, and 1, we get 8, which is the remainder when 1EDA86hex is divided by 11hex (i.e. 17ten). But if we add 1, D, and 8 and subtract E, A, and 8, we get 9.

You can start from either end of a number if you only want to test divisibility, not to compute a remainder. But if you do want the remainder, you might get the wrong result if you start at the wrong end.

Application: Divisibility by 7, 11, and 13

We can apply the technique above to test for divisibility by 1001 in base 1000. And why would we want to do that? Because 1001 = 7 × 11 × 13. Reducing a large number mod 1001 takes the problem of testing for divisibility mod 7, 11, or 13 down to the problem of testing 3-digit numbers.

Base 1000 is just base 10, thinking of triples of ordinary digits as a single base 1000 digit. If we write a number with thousands separators (i.e. commas in some countries, periods in others) then each segment is a base 1000 “digit.”

Example 1

For example, let’s test whether n = 598,203,918 is divisible by 7, 11, or 13.

The alternating (base 1000) digit sum is

598 − 203 + 918 = 1313 = 13 × 101.

The result is clearly divisible by 13, so n is divisible by 13. But since 101 is not divisible by 7 or 11, neither is n.

Example 2

For another example, let n = 314,159,265,358 and find the remainders when n is divided by 7, 11, and 13. We start by reducing n mod 1001.

314159265358 =  −314 + 159 − 265 + 358 = −62 = 939 mod 1001.

Now 939 = 1 = mod 7, so n = 1 mod 7.

Also, 9 + 9 − 3 = 15 = 4 mod 11, and so n = 4 mod 11.

Finally, 939 = 3 mod 13, so n = 3 mod 13.

 

How large is a Maidenhead field?

Posted on by John

The Maidenhead locator system divides the earth into fields, squares, and subsquares. The first two characters in a Maidenhead locator specify the square. These are letters A through R representing 20 degrees of longitude or 10 degrees of latitude. Latitude A runs from the South Pole to 80° south of the equator. Latitude R runs from 80° north of the equator up to the North Pole.

The area of a field depends on latitude. The previous post was a lemma for this post, solving the general problem of finding the area of a region bounded by longitudes θ1 and θ2 and latitudes φ1 and φ2. Working in degrees, the area is

A = π r² (sin φ1 − sin φ2) (θ1 − θ2) / 180.

So area of the ith field above or below the equator is

A = π r² (sin 10i° − sin 10(i−1)° ) / 6.

Fields whose second character is I or J are nearest to the equator and have the largest area. This area is

π r² sin 10° / 6

If we take r to be 3959 miles (6371 km) this gives an area of about 950,000 square miles or 2,500,000 square kilometers.

Let’s do a quick check to see whether this result is reasonable. The circumference of the earth is about C = 40,000 km [1]. The fields on either side of the equator are roughly Euclidean rectangles C/18 wide and C/36 tall. This also gives an area of about 2.5 million km².

For fields nearest the poles, fields with second character A or R, the area is

π r² (sin 90° − sin 80° ) / 6

which works out to be 83,000 square miles or 215,000 square kilometers.

Here’s a complete list of field areas based on the second letter.

    |-------+----------+---------|
    | Field | sq miles |   sq km |
    |-------+----------+---------|
    | A     |    83119 |  215250 |
    | B     |   246831 |  639211 |
    | C     |   403044 | 1043750 |
    | D     |   547010 | 1416575 |
    | E     |   674356 | 1746359 |
    | F     |   781211 | 2023080 |
    | G     |   864330 | 2238330 |
    | H     |   921187 | 2385571 |
    | I     |   950054 | 2460326 |
    | J     |   950054 | 2460326 |
    | K     |   921187 | 2385571 |
    | L     |   864330 | 2238330 |
    | M     |   781211 | 2023080 |
    | N     |   674356 | 1746359 |
    | O     |   547010 | 1416575 |
    | P     |   403044 | 1043750 |
    | Q     |   246831 |  639211 |
    | R     |    83119 |  215250 |
    |-------+----------+---------|

The area of a Maidenhead square is approximately 1/100 of the area of the field it is in. The area of a square also depends on latitude, but not as much as the area of a field does.

The area of a Maidenhead subsquare is approximately 1/24² = 1/576 of its square.

A typical Maidenhead field has area around 800,000 square miles or 2,000,000 square kilometers. (By “typical” I mean well populated areas. Much of the world’s population lives at around 30 or 40 degrees latitude.) So a typical square has area 8,000 square miles or 20,000 square kilometers. A typical subsquare will be around 14 square miles or 35 square kilometers.

Related posts

[1] It isn’t a coincidence that this is such a round number. The meter was initially defined as 1/10,000,000 of the distance from the North Pole to the equator.

Area of a “rectangle” on a globe

Posted on by John

What do we mean by rectangle?

This post will derive the area of a spherical region bounded by lines of latitude and longitude. Such a region corresponds to an actual rectangle on a Mercator projection map, with sides aligned with the coordinate axes, and is approximately a rectangle on a sphere if the rectangle is not too big [1].

What do we know up front?

Before we get into detailed equations, we know that the area will be proportional to the difference in longitude. If we’re looking that the area between two parallels, such as the equator and the Arctic Circle, the area between 10° and 20° longitude is the same as the area between 80° and 90° longitude, and twice the area between 72° and 77° longitude.

The difficulty is latitude. Say we look at squares on a map that are 1° of longitude wide and 1° of latitude tall. Those squares are on the map will correspond to more area on the globe for latitudes near the equator, and less area at high latitudes.

So the area bounded by longitudes θ1 and θ2 and latitudes φ1 and φ2 will depend on φ1 and φ2 individually, but only on the difference θ1 − θ2.

Spherical caps

The region on a sphere above a fixed line of latitude is called a spherical cap. The northern hemisphere, the region above the equator, would be a very large spherical cap. The region inside the Arctic Circle would be a smaller spherical cap.

Let R be the radius of the earth. Then the surface area above a latitude φ is

A = 2πR²(1 − sin φ).

You could derive this using calculus by thinking of the spherical cap as a surface of revolution.

Spherical bands

Given two latitudes φ1 and φ2 with latitudes φ1 > φ2, the area of a band between latitude φ1 and latitude φ2 is the area of the spherical cap above latitudes φ2 minus the area of the spherical cap above latitudes φ1. This gives

A = 2πR²(sin φ1 − sin φ2).

Area of latitude/longitude grid

Now we can find the area of the region bounded by longitudes θ1 and θ2 and latitudes φ1 and φ2. The total area between latitudes φ1 and φ2 is given by the equation above. The subset of this area between longitudes θ1 and θ2 is proportional to θ1 − θ2. If longitude is measured in radians then

A = R² (sin φ1 − sin φ2) (θ1 − θ2).

If longitude is measured in degrees, we have

A = π R² (sin φ1 − sin φ2) (θ1 − θ2)/180.

Related posts

[1] As Nathan helpfully pointed out in the comments, it might be clearer to say “not too big and not too close to one of the poles.” Another way to put it might be to say the idea of what is “big” depends on how close to a pole you are.