Uncategorized

Instant classic

Posted on by John

“Instant classic” is, of course, an oxymoron. A classic is something that has passed the test of time, and by definition that cannot happen instantly.

But how long should the test of time last? In his book Love What Lasts, Joshua Gibbs argues that 100 years after the death of the artist is about the right amount of time, because that is the span of personal memory.

An individual may have memories from 50 years ago that he passes on to someone 50 years younger, but it’s unlikely the young hearer will pass along the same memory. Or to look at it another way, 100 years is about four generations, and hardly anyone has much connection to a great great grandparent.

If a work is still of interest 100 years after the death of the person who created it, the work must have some value that extends beyond a personal connection to its creator.

I’m about a third of the way through Gibbs’ book and it’s the most thought-provoking thing I’ve read lately.

Related posts

Packing versus unpacking

Posted on by John

I usually think of an instructor as someone who unpacks things, such as unpacking the meaning of an obscure word or explaining a difficult concept.

Last night I was trying to read some unbearably dry medical/legal material and thought about how an instructor might also pack things, wrapping dry material in some sort of story or illustration to make it more palatable.

I’ve often thought it would be nice to have someone explain this or that. I hadn’t really thought before that it would be nice to have someone make perfectly clear material more bearable to absorb, but I suppose that’s what a lot of instructors do. I was able to avoid courses that needed such an instructor, for which I am grateful, but I could imagine how a good instructor might make a memorization-based course tolerable.

How to memorize Unicode codepoints

Posted on by John

At the end of each month I write a newsletter highlighting the most popular posts of that month. When I looked back at my traffic stats to write this month’s newsletter I noticed that a post I wrote last year about how to memorize the ASCII table continues to be popular. This post is a follow up, how to memorize Unicode values.

Memorizing all 128 ASCII values is doable. Memorizing all Unicode values would be insurmountable. There are nearly 150,000 Unicode characters at the moment, and the list is grows over time. But knowing a few Unicode characters is handy. I often need to insert a π symbol, for example, and so I made an effort to remember its Unicode value, U+03C0.

There are convenient ways of inserting common non-ASCII characters without knowing their Unicode values, but these offer a limited range of characters and they work differently in different environments. Inserting Unicode values gives you access to more characters in more environments.

As with ASCII, you can memorize the Unicode value of a symbol by associating an image with a number and associating that image with the symbol. The most common way to associate an image with a number is the Major system. As with everything else, the Major system becomes easier with practice.

However, Unicode presents a couple challenges. First, Unicode codepoints are nearly always written in hexadecimal, and so you’ll run into the letters A through F as well as digits. Second, Unicode codepoints are four hex digits long (or five outside the Basic Multilingual Plane.) We’ll address both of these difficulties shortly.

It may not seem worthwhile to go to the effort of encoding and decoding numbers like this, but it scales well. Brute force is fine for small amounts of data and short-term memory, but image association works much better for large amounts of data and long-term memory.

Unicode is organized into blocks of related characters. For example, U+22xx are math symbols and U+26xx are miscellaneous symbols. If you know what block a symbols is in, you only need to remember the last two hex digits.

You can convert a pair of hex digits to decimal by changing bases. For example, you could convert the C0 in U+03C0 to 192. But this is a moderately difficult mental calculation.

An easier approach would be to leave hex digits alone that correspond to decimal digits, reduce hex digits A through F mod 10, and tack on an extra digit to disambiguate. Stick on a 0, 1, 2, or 3 according to whether no digits, the first digit, the second digit, or both digits had been reduced mod 10. See this page for details. With this system, C0 becomes 201. You could encode 201 as “nest” using the Major system, and imagine a π sitting in a nest, maybe something like the 3Blue1Brown plushie.

3Blue1Brown plushieFor another example, ♕ (U+2655), is the symbol for the white queen in chess. You might think of the White Queen from The Lion, the Witch, and the Wardrobe [2] and associate her with the hex number 0x55. If you convert 0x55 to decimal, you get 85, which you could associate with the Eiffel Tower using the Major system. So maybe imagine the White Queen driving her sleigh under the Eiffel Tower. If you convert 0x55 to 550 as suggested here, you might imagine her driving through a field of lilies.

Often Unicode characters are arranged consecutively in a logical sequence so you can compute the value of the rest of the sequence from knowing the value of the first element. Alphabets are arranged in alphabetical order (mostly [1]), symbols for Roman numerals are arranged in numerical order, symbols for chess pieces are arrange in an order that would make sense to chess players, etc.

[1] There are a few exceptions such as Cyrillic Ё and a gap in Greek capital letters.

[2] She’s not really a queen, but she thinks of herself as a queen. See the book for details.

Moving between differential and integral equations

Posted on by John

My years in graduate school instilled a Pavlovian response to PDEs: multiply by a test function and integrate by parts. This turns a differential equation into an integral equation [1].

I’ve been reading a book [2] on integral equations right now, and it includes several well-known techniques for turning certain kinds of integral equations into differential equations. Then this afternoon I talked to someone who was excited to have discovered a way to turn a more difficult integral equation into a differential equation.

For theoretical purposes, you often want to turn differential equations into integral equations. But for computational purposes, you often want to do the reverse.

Differential and integral equations are huge, overlapping fields, and sweeping generalities have exceptions. The opposite of the statement above may also be true. You may want to turn a differential equation into an integral equation for computational purposes (as in the finite element method) or turn an integral equation into a differential equation for theoretical convenience (as was the case for the person I was taking to).

***

[1] Sorta. More precisely this moves from the strong form of the PDE to a weak form. This involves integration, at least formally.

[2] Vladimir Ryzhov et al. Modern Methods in Mathematical Physics: Integral Equations in Wolfram Mathematica.

Overpowered proof that π is transcendental

Posted on by John

There is no polynomial with rational coefficients that evaluates to 0 at π. That is, π is a transcendental number, not an algebraic number. This post will prove this fact as a corollary of a more advanced theorem. There are proof that are more elementary and direct, but the proof given here is elegant.

A complex number z is said to be algebraic if it is the root of a polynomial with rational coefficients. The set of all algebraic numbers forms a field F.

The Lindemann-Weierstrass theorem says that if

α1, α2, …, αn

is a set of distinct algebraic numbers, then their exponentials

exp(α1), exp(α2), …, exp(αn)

are linearly independent. That is, no linear combination of these numbers with rational coefficients is equal to 0 unless all the coefficients are 0.

Assume π is algebraic. Then πi would be algebraic, because i is algebraic and the product of algebraic numbers is algebraic.

Certainly 0 is algebraic, and so the Lindemann-Weierstrass theorem would say that exp(πi) and exp(0) are linearly independent. But these two numbers are not independent because

exp(πi) + exp(0) = -1 + 1 = 0.

So we have a proof by contradiction that π is not algebraic, i.e. π is transcendental.

I found this proof in Excursions in Number Theory, Algebra, and Analysis by Kenneth Ireland and Al Cuoco.

 

Luhn checksum algorithm

Posted on by John

After writing the previous post on credit card numbers, I intended to link to a previous post that discussed credit card check sums. But I couldn’t find such a post. I’ve written about other kinds of checksums, such as the checksum scheme used in Vehicle Identification Numbers, but apparently I haven’t written about credit card checksums before.

The algorithm used by credit cards, and other identification numbers, is called the Luhn algorithm. I’ll lead up to the algorithm to explain its motivation, going through a thought process Luhn might have gone through in developing his algorithm.

NB: The intermediate steps are not the Luhn algorithm. If you’re just looking for Luhn’s algorithm, skip to the end.

Step 1

A simple way to create a check sum is to add up the digits of a number and tack on the sum mod 10 on the end. For example, this process would replace 1776 with 17761 because

1 + 7 + 7 + 6 = 21

and 21 mod 10 = 1.

This simple checksum will detect if any single digit has been changed. For example, if we receive 17791 we can compute the checksum of 1779 and tell that something is wrong because the last digit should be 4.

Step 2

A common kind of error is transposing consecutive digits, and the scheme above will not detect transpositions: all digits are treated the same way, so scrambling them doesn’t change the checksum.

Luhn’s idea was to double every other digit before taking the sum. This creates an asymmetry between the contribution of consecutive digits to the check sum and makes it possible to detect all transpositions.

Which digits to double

The method described above works whether you start from the left end or the right end, and whether you start doubling with the first or second digit you encounter. But to be compatible with the Luhn algorithm used in practice, start on the right end and double the last digit.

So going back to our little example, 1776 becomes 17764 because

2*6 + 7 + 2*7 + 1 = 34.

If we accidentally transpose the first two digits, 17764 becomes 71764. But the check sum of 7176 is 0. So 71760 would be valid but 71764 is not. We’ve detected an error.

The advantage of starting at the right end is that adding zeros to the front of the number doesn’t change the checksum. So, for example, 01776 becomes 017764.

Step 3

The next refinement is strange. Instead of simply doubling every other digit, we’ll double every other digit and reduce mod 9.

So we could calculate the checksum for 1776 by first doubling every other digit

1776 -> 1, 14, 7, 12

then reducing the doubled digits mod 9, i.e. replacing 14 by 5 and 12 by 3,

1, 14, 7, 12 -> 1, 5, 7, 3

and then finally taking the last digit of the sum.

1 + 5 + 7 + 3 = 16 -> 6.

What does this extra complication buy us? Nothing as far as I can tell. It weakens the algorithm. The algorithm in Step 2 could detect if 09 were transposed to 90; the algorithm here in Step 3 cannot.

Update: Nathan points out in the comments that without the mod 9 step some changes to a single digit could go undetected, namely changing the second of a pair of doubled digits by 5. For example, 33 and 38 would have the same checksum in Step 2 but not in Step 3.

Step 4

The final step is to take the tens compliment of the checksum computed above. This adds nothing to the effectiveness of the algorithm, but it’s what Luhn did.

Luhn algorithm in practice

Let’s describe the position of digits in a number by numbering them from the right end, starting with o: the last digit is in position 0, the one to its left is in position 1, etc.

We can summarize the Luhn algorithm in the following pseudocode.

    sum = 0
    for d in digits:
        if d is in an even position:
            sum = sum + (2*d) mod 9
        else:
            sum = sum + d
    return 10 - sum mod 10

The last line isn’t quite correct. If sum mod 10 is 0, then this returns 10 when it should return 0. A clever way around this is to change the last line to

    return (sum*9) mod 10

which will always return a single digit.

NB: In our examples above, the checksum was added to the end. Some credit cards do this, but others put the checksum somewhere in the interior of the number.

Afterword

The Luhn algorithm was developed in 1954, though it is still widely used. Since that time much more sophisticated error correcting codes have been developed. See the links below for examples.

What can you learn from a credit card number?

Posted on by John

The first 4 to 6 digits of a credit card number are the bank identification number or BIN. The information needed to decode a BIN is publicly available, with some effort, and so anyone could tell from a credit card number what institution issued it, what bank it draws on, whether its a personal or business card, etc.

Suppose your credit card number was exposed in a data breach. Someone makes a suspicious purchase with your card, the issuer contacts you, you cancel the card, and you get a new card from the same source. The number can no longer be used to make purchases on your account, but what information did it leave behind?

The cancelled number might tell someone where you used to bank, which is probably where you still bank. And it may tell them the first few digits of your new card since the new card is issued by the same institution [1]. If the old BIN doesn’t directly reveal your new BIN, it at least narrows down the possibilities.

The information in your BIN, by itself, will not identify you, but it does provide clues that might lead to identifying you when combined with other information.

Related posts

[1] According to Andrew in the comments, American Express often changes credit card numbers as little as possible when issuing a replacement, changing only one content digit and the checksum.

Gold, silver, and bronze ratios

Posted on by John

The previous post showed that if you inscribe a hexagon and a decagon in the same circle, the ratio of the sides of the two polygons is the golden ratio. After writing the post I wondered whether you could construct the silver ratio or bronze ratio in an analogous way.

Metallic ratios

To back up a bit first, what are these ratios? The golden ratio is famous, but the silver and bronze ratios are not so well known. I’ve written the silver ratio before, and hinted at the bronze ratio.

The continued fraction representation of the golden ratio contains all 1s.

1 + \cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cdots}}}

Similarly, the continued fraction for the silver ratio contains all 2s.

2 + \cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}

In general, the nth metallic ratio is the number whose continued fraction representation contains all ns.

n + \cfrac{1}{n+\cfrac{1}{n+\cfrac{1}{n+\cdots}}} = \frac{n + \sqrt{n^2 + 4}}{2}

The metallic ratios for n > 3 do not have standard names.

Polygon side ratios

Let’s call a number a polygon ratio if it equals the ratio of sides of polygons inscribed in the same circle. Is the silver ratio or the bronze ratio a polygon ratio?

Apparently not. I would expect that if the silver or bronze ratio were the ratio of the side of an m-gon and an n-gon, then m and n would be fairly small integers, though I have no proof of this.

I did an empirical search, letting m and n vary from 1 to 1,000. Some ratios came close to the silver and bronze ratios, but no matches. I expect you can approximate any number as closely as you like with the ratio of polygon sides, but if there’s an exact match for the silver or bronze ratio, then m and n must be larger than 1,000.

Apparently the golden ratio is the only metallic ratio which is also a polygon ratio. This is at least true for the first 100 metallic ratios and for polygon ratios with m and n less than 1,000.

A pentagon, hexagon, and decagon walk into a bar …

Posted on by John

The new book A Panoply of Polygons cites a theorem Euclid (Proposition XIII.10) saying

If a regular pentagon, a regular hexagon, and a regular decagon are inscribed in congruent circles, then their side lengths form a right triangle.

This isn’t exactly what Euclid said, but it’s an easy deduction from what he did say.

Here’s an illustration.

Illustrating Euclid Proposition XIII.10

Update: Ralph Corderoy suggested in the comments that it would be good to add the congruent circles through the polygon vertices. Here is a graphic with the circles added.

Illustrating Euclid Proposition XIII.10

Connection with golden ratio

I learned about this theorem from the book cited above, which arrived in the mail yesterday. The figure looked familiar because Cliff Pickover had posted essentially the same illustration on Twitter recently, saying that not only is there a right triangle in the middle of the diagram, this triangle is half of a golden rectangle.

The length of the side of a regular polygon with n sides is 2R sin(π/n) where R is the radius of the circle through the vertices. So to prove that the ratio between the side of the hexagon and the side of the decagon is the golden ratio φ, it suffices to prove

sin(π/6) / sin(π/10) = φ

You could verify this in Mathematica by seeing that the following returns True.

    Sin[Pi/6]/ Sin[Pi/10] == GoldenRatio

Python code

Here’s the code I used to create the image above.

    from numpy import exp, pi, arange
    import matplotlib.pyplot as plt
    
    # Vertices of a hexagon
    hexa = exp(2j*pi*arange(6)/6)
    
    # Vertices of a decagon, shifted and rotated
    # to have a side perpendicular to the hexagon
    deca = exp(2j*pi*(0.5+arange(10))/10)
    deca += hexa[1] - deca[5]
    
    # Shift and rotate a pentagon to share one vertex 
    # with the hexagon and one vertex with the decagon
    omega = exp(2j*pi/5)
    c = (hexa[2]*omega - deca[4])/(omega - 1)
    penta = c + (hexa[2] - c)*exp(2j*pi*arange(5)/5) 
    
    def connect(p, q, c):
        plt.plot([p.real, q.real], [p.imag, q.imag], '-', color=c)
    
    plt.gca().set_aspect("equal")
    
    for n in range(-1, 5):
        connect(hexa[n], hexa[n+1], 'blue')
    for n in range(-1, 9):
        connect(deca[n], deca[n+1], 'green')
    for n in range(-1, 4):
        connect(penta[n], penta[n+1], 'red')
    
    plt.show()

The ability to use -1 to as the index to the last element of an array simplifies the code that connects the vertices. In a language like C you’d have to write an extra statement after your loop to join the last vertex to the first.

When I first saw the illustration in Panoply of Pentagons I though that the top of the pentagon was parallel to the top of the hexagon. When I wrote the Python code first assuming this orientation of the pentagon, things didn’t line up. Writing the code made me pay closer attention, as is often the case.

Related posts

Redoing images in Midjourney

Posted on by John

My son in law was playing around with Midjourney v5 and I asked him to try to redo some of the images I’ve made with DALL-E 2.

Back in August i wrote a post about using DALL-E 2 to generate mnemonic images for memorizing the US presidents using the Major mnemonic system.

To memorize that Rutherford B. Hayes was the 19th president. you might visualize Hayes playing a tuba because you can encode 19 as tuba. The image I created last year was cartoonish and showed Hayes playing something more like a sousaphone than a tuba. Midjourney created a photorealistic image of Hayes playing some weird instrument which is something like a tuba.

Rutherford B. Hayes playing something like a ruba

Franklin Delano Roosevelt was the 32nd president. If we use an image of the moon as the peg for 32, we could imagine FDR looking up at the moon. The previous image of FDR was really creepy and looked nothing like him. The image Midjourney created with FDR was really good.

FDR looking up at the moon

Midjourney choked on the request to create a create an image of Grover Cleveland holding an onion and a wiener dog, just as DALL-E had. It didn’t do any better substituting Grover the Muppet for Grover Cleveland.

A few weeks ago I wrote a blog post about a thought experiment involving an alien astronomer with 12 fingers working in base 12. I could only get DALL-E to draw a hint of an extra finger. We weren’t able to get Midjourney to put 12 fingers on a hand either, but we did get an interesting image of an alien astronomer.

Alien astronomer