John D. Cook

Let G be a directed graph whose nodes are the positive integers and whose edges represent relations between two integers. In our first example we'll draw an edge from x to y if x is a multiple of y. In our second example we'll draw an edge from x to y if x >= y. [...]The post From graph theory to category theory first appeared on John D. Cook.

Test functions are how you can make sense of functions that aren't really functions. The canonical example is the Dirac delta function" that is infinite at the origin, zero everywhere else, and integrates to 1. That description is contradictory: a function that is 0 almost everywhere integrates to 0, even if you work in extended [...]The post Test functions first appeared on John D. Cook.

This article will probably only be of interest to a small number of readers. Those unfamiliar with category theory may find it bewildering, and those well versed in category theory may find it trivial. My hope is that someone in between, someone just starting to get a handle on category theory, will find it helpful. [...]The post Groups vs Abelian groups: Pedantic or profound? first appeared on John D. Cook.

The Depths of Wikipedia twitter account posted a screenshot about supereggs that's popular at the moment. It says there's no way this is real. they must be making these words up above a screenshot from the Wikipedia article on supereggs saying The definition can be changed to have an equality rather than an inequality; this [...]The post Supereggs, squigonometry, and squircles first appeared on John D. Cook.

Meredith Whittaker posted on Twitter that In addition to being the best in privacy, Signal is also the best in not subjecting you to corny AI' features no one asked for or wants. I love the phrase corny AI." That's exactly what a lot of AI features are. Would you like help composing that tweet?" [...]The post Corny AI first appeared on John D. Cook.

The star-like image above is today's exponential sum. The exponential sum page on my site generates a new image each day by putting the numbers of the day's month, day, and year into the equation and connecting the partial sums in the complex plane. Here m is the month, d is the day, and y [...]The post Today's star first appeared on John D. Cook.

Coupon collector problem Suppose you have a bag of balls labeled 1 through 1,000. You draw draw balls one at a time and put them back after each draw. How many draws would you have to make before you've seen every ball at least once? This is the coupon collector problem with N = 1000, [...]The post Consecutive coupon collector problem first appeared on John D. Cook.

Monte Carlo integration is not as simple in practice as it is often introduced. A homework problem might as you to integrate a function of two variables by selecting random points from a cube and counting how many of the points fall below the graph of the function. This would indeed give you an estimate [...]The post Regular solids and Monte Carlo integration first appeared on John D. Cook.

The previous post describes the hoops I jumped through to enter Unicode characters on a Mac. Here's a script to run from the command line that will copy Unicode characters to the system clipboard. It runs anywhere the Python module pyperclip runs. #!/usr/bin/env python3 import sys import pyperclip cp = sys.argv[1] ch = eval(f"chr(0x{cp})") print(ch) [...]The post Cross-platform way to enter Unicode characters first appeared on John D. Cook.

Setting up Unicode on my MacBook took some research, so I'm leaving myself a note here if I need to do it again. Maybe it'll help someone else too. Update: I've gotten some feedback on this article that suggest people imagine that I want to use this approach to enter large quantities of text, such [...]The post Using Unicode on MacOS first appeared on John D. Cook.

About three years ago I ran across a strange coordinate system in which familiar functions lead to interesting plots. The system is called circular coordinates" but it is not polar coordinates. This morning I was playing around with this again. Here's a plot of f(x) = x. And here's a plot of f(x) = cos(8x). [...]The post Circular coordinate art first appeared on John D. Cook.

Today's date, US style, is 9/26/2023, and there is only one group, up to isomorphism, of size 9262023. You could verify this in Mathematica with the command FiniteGroupCount[9262023] which returns 1. For a given n, when is there only one group of size n? There are two requirements. First, n has to be the product [...]The post When there is only one group of a given size first appeared on John D. Cook.

Simple groups are the building blocks of groups similar to the way prime numbers are the building blocks of integers. This post will unpack this analogy in two ways: How do simple groups compare to prime numbers? How does the composition of simple groups compare to the composition of prime numbers? The former analogy is [...]The post Analogy between prime numbers and simple groups first appeared on John D. Cook.

The word normal" in mathematical nomenclature does not always means usual" or customary" as it does in colloquial English. Instead, it might that something has a convenient property. That is the case for normal subgroups. We can do things with normal subgroups that we cannot do with other subgroups, such as take quotients, and so [...]The post Normal and non-normal subgroups first appeared on John D. Cook.

In the previous post I mentioned that a particular Mersenne prime would be unsuitable for cryptography. In fact, all Mersenne primes are unsuitable for cryptography. A prime number p is called safe" if p = 2q + 1 where q is also a prime. Safe primes are called safe because p - 1 does not [...]The post Mersenne primes are unsafe first appeared on John D. Cook.

Electronic computers were invented before public key cryptography. Would public key cryptography have been possible before computers? The security of RSA encryption depends on the ratio of the difficulty of factoring relative to the difficulty of multiplication. This ratio was high, maybe higher, before modern computers. Suppose the idea of RSA encryption had occurred to [...]The post Victorian public key cryptography first appeared on John D. Cook.

I like generating long LaTeX documents from org-mode because, for one thing, org-mode has nice section folding. But not everyone I work with uses Emacs, so its better to work in LaTeX directly rather than have Emacs generate LaTeX. AUCTeX has section folding for LaTeX documents, though so far I've only has limited success at [...]The post Navigating a LaTeX file first appeared on John D. Cook.

It's surprisingly hard to find a complete list of HTML entities in the form of a data file. There are numerous sites that give lists, often incomplete, in a page formatted to be human-readable but not machine-readable. Here's an XML file from the W3C. Here's a two-column text file I created from the W3C data.The post HTML entity data first appeared on John D. Cook.

I've needed to use double-struck capital letters lately, also called blackboard bold. There are a few quirks in how they are represented in Unicode and in HTML entities, so I'm leaving some notes for myself here and for anyone else who might need to look this up. Unicode The double-struck capital letters are split into [...]The post Double-struck capital letters first appeared on John D. Cook.

Here's a quote from Don Zagier that I found in Larry Rolen's lecture notes on modular forms. There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role [...]The post Primes, weeds, and military precision first appeared on John D. Cook.

A continued fraction of the form with n terms can be written as the composition where As discussed in the previous post, a Mobius transformation can be associated with a matrix. And the composition of Mobius transformations is associated with the product of corresponding matrices. So the continued fraction at the top of the post [...]The post Continued fractions as matrix products first appeared on John D. Cook.

A function of the form where ad - bc 0 is sometimes called a fractional linear transformation or a bilinear transformation. I usually use the name Mobius transformation. In what sense are Mobius transformations linear transformations? They're nonlinear functions unless b = c = 0. And yet they're analogous to linear transformations. For starters, [...]The post Fractional linear and linear first appeared on John D. Cook.

The Awk programming language was named after the initials of its creators. In the preface to a book that just came out, The AWK Programing Language, Second Edition, the authors give a little background on this. Naming a language after its creators shows a certain paucity of imagination. In our defense, we didn't have a [...]The post Naming Awk first appeared on John D. Cook.

Warm up The geometric mean of two numbers is the square root of their product. For example, the geometric mean of 9 and 25 is 15. More generally, the geometric mean of a set of n numbers is the nth root of their product. Alternatively, the geometric mean of a set of n numbers the [...]The post Geometric mean on unit circle first appeared on John D. Cook.

The Gauss map [1] is the function where y is the floor of y, the greatest integer no larger than y. I've written about this map a couple times before. First, I wrote about how this map is measure-preserving. Second, I wrote about the image at the top of the post, based on Michael Trott's [...]The post Gauss map, Euclidean algorithm, and continued fractions first appeared on John D. Cook.

The goal of this post is to unpack a remark in [1]: ... we can say this in fancier terms. Fix a field k .... We say that an elliptic curve E defined over k is that functor which ... Well that is fancy. But what does it mean? Looking for objects A functor is [...]The post An elliptic curve is a functor first appeared on John D. Cook.

The geometric description of addition of points P and Q on an elliptic curve involves four logical branches: If one of P or Q is the point at infinity ... Else if P = Q ... Else if P and Q lie on a vertical line ... Else ... It would seem that an algorithm [...]The post Elliptic curve addition formulas first appeared on John D. Cook.

Mathematicians often speak informally about the relative simplicity of rational numbers. For example, musical intervals that correspond to simple fractions have less tension than intervals that correspond to more complicated fractions. Such informal statements can be made more precise using height functions. There are a variety of height functions designed for different applications, but the [...]The post Rational height functions first appeared on John D. Cook.

If you ask someone a question and they say yes" immediately, that gives you different information than if they pause and slowly say yes." The information you receive is not just the response but also the time it took to generate the response. Encryption can be analogous. The time it takes to encrypt data can [...]The post Timing attacks first appeared on John D. Cook.

I concluded the previous post by saying elliptic curve Diffie-Hellman key exchange (ECDHE) requires smaller keys than finite field Diffie-Hellman (FFDHE) to obtain the same level of security. How much smaller are we talking about? According to NIST recommendations, a 256-bit elliptic curve curve provides about the same security as working over a 3072-bit finite [...]The post Elliptic curve Diffie-Hellman key exchange first appeared on John D. Cook.

Diffie-Hellman key exchange is conceptually simple. Alice and Bob want to generate a shared cryptographic key. They want to use asymmetric (public) cryptography to share a symmetric (private) key. The starting point is a large prime p and a generator 1 < g < p. Alice generates a large random number x, her private key, [...]The post Finite field Diffie Hellman primes first appeared on John D. Cook.

Suppose m = pq where p and q are large, distinct primes. In the previous post we said that calculations mod m can often be carried out more efficiently by working mod p and mod q, then combining the results to get back to a result mod m. The Chinese Remainder Theorem assures us that [...]The post Chinese Remainder Theorem synthesis algorithm first appeared on John D. Cook.

Suppose m is a large integer that you are able to factor. To keep things simple, suppose m = pq where p and q are distinct primes; everything in this post generalizes easily to the case of m having more than two factors. You can carry out calculations mod m more efficiently by carrying out [...]The post Gaining efficiency by working modulo factors first appeared on John D. Cook.

RSA encryption a map from numbers mod n to numbers mod n where n is a public key. A message is represented as an integer m and is encrypted by computing c = me mod n where e is part of the public key. In practice, e is usually 65537 though it does not have [...]The post Group theory and RSA encryption first appeared on John D. Cook.

Not all messages encrypted with the RSA algorithm can be decrypted. This post will show why this is possible and why it does not matter in practice. RSA in a nutshell RSA encryption starts by finding two large primes, p and q. These primes are kept secret, but their productn = pq is made public. [...]The post RSA encrypted messages that cannot be decrypted first appeared on John D. Cook.

Dimension 2 The equation for the perimeter of an ellipse is wherea is the semimajor axis, e is eccentricity, and E is a special function. The equation is simple, in the sense that it has few terms, but it is not elementary, because it depends on an advanced function, the complete elliptic integral of the [...]The post Hyperellipsoid surface area first appeared on John D. Cook.

I posted some notes this morning on how to find the perimeter of an ellipse given its axes. The notes include a simple approximation, a better but more complicated approximation, and the exact value. So given the semi axes a and b, the notes give three ways to compute the perimeter p. If you are [...]The post Solve for ellipse axes given perimeter first appeared on John D. Cook.

The home team lost in a new way yesterday. The Baltimore Ravens beat the Houston Texans by 25-9. This was the first time that score has been seen in the NFL. Possible individual team scores How many scores are possible? It is possible to score any number of points except 1. You can score 2 [...]The post Possible and actual football scores first appeared on John D. Cook.

Earlier I wrote a post showing what happens when you start with an equilateral triangle, then repeatedly subdivide it into smaller and smaller triangles by drawing lines from the centroid (barycenter) to each of the vertices. I mentioned in that post that I moved the code for finding the center to its own function because [...]The post How you define center matters a lot first appeared on John D. Cook.

I just saw a tweet from Dave Richeson saying I remember as a kid calculating the size difference (diameter) of a belt between each hole. Now I think about it every time I wear a belt. Holes 1 inch apart change the diameter by about one-third of an inch (1/). [Assuming people have a circular [...]The post Belt around an elliptical waist first appeared on John D. Cook.

The other day I saw where Cliff Pickover tweeted some images of triangles recursively subdivided by adding a point to the barycenter of each triangle. The images were not what I expected, so I wanted to reproduce the images to look into this further. Here are the first three steps: I set the alpha value [...]The post Recursive triangle subdivision first appeared on John D. Cook.

One of the most common things a statistician is asked to do is compute a sample. There are well known formulas for this, so why isn't calculating a sample size trivial? As with most things in statistics, plugging numbers into a formula is not the hard part. The hard part is deciding what numbers to [...]The post Justifiable sample size first appeared on John D. Cook.

A large class of checksum algorithms have the following pattern: Think of the bits in a file as the coefficients in a polynomial P(x). Divide P(x) by a fixed polynomial Q(x) mod 2 and keep the remainder. Report the remainder as a sequence of bits. In practice there's a little more to the algorithm than [...]The post Checksum polynomials first appeared on John D. Cook.

Given a square complex matrix A, the Jordan normal form of A is a matrix J such that and J has a particular form. The eigenvalues of A are along the diagonal of J, and the elements above the diagonal are 0s or 1s. There's a particular pattern to the 1s, giving the matrix J [...]The post Jordan normal form: 1's above or below diagonal? first appeared on John D. Cook.

When is the discrete Fourier transform of a vector proportional to the original vector? And when that happens, what is the proportionality constant? In more formal language, what can we say about the eigenvectors and eigenvalues of the DFT matrix? Setup I mentioned in the previous post that Mathematica's default convention for defining the DFT [...]The post Eigenvectors of the DFT matrix first appeared on John D. Cook.

Just as there are multiple conventions for defining the Fourier transform, there are multiple conventions for defining the discrete Fourier transform (DFT), better known as the fast Fourier transform (FFT). [1] This post will look at two DFT conventions, one used in Python's NumPy library, and one used in Mathematica. There are more conventions in [...]The post DFT conventions: NumPy vs Mathematica first appeared on John D. Cook.

Math books often use some illustration from the book contents as cover art. When they do, there's often some mystery to the cover art, and a sense of accomplishment when you get far enough into the book to understand the significance of the cover. (See examples here.) William L. Briggs and Van Emden Henson wrote [...]The post DFT mandalas first appeared on John D. Cook.

In his book How to Read Literature Like a Professor, Thomas Foster says that if a poem looks like a square on the printed page, it's likely a sonnet. The miracle of the sonnet, you see, is that it is fourteen lines long and written almost always in iambic pentameter. ... suffice it to say [...]The post Sonnets are square first appeared on John D. Cook.

Suppose you've been monitoring a rare event for a long time, then you see your first occurrence on the Nth observation. Now what would you say about the event's probability? For example, suppose you're wondering whether dogs ever have two tails. You observe thousands of dogs and never see two tails. But then you see [...]The post First time seeing a rare event first appeared on John D. Cook.

Imagine the following dialog. Logarithms are usually taken to integer bases, like 2 or 10." What about e?" OK, that's an example of an irrational base, but it's the only one." Decibels are logarithms tobase 101/10." Really?!" Yeah, you can read about this here." That's weird. But logarithms are always take to bases bigger than [...]The post Stellar magnitude first appeared on John D. Cook.