Double Factorial Table

The double factorial is the product of a number and every second natural number less than itself. That is:

\(n!! = \prod_{k = 0}^{ \lceil n/2 \rceil - 1} (n - 2k) = n(n-2)(n-4)...\)

Presentation of the values for double factorials is usually split up into separate even- and odd- sequences. Instead, I wanted to see the sequence all together, as below:

Geometry Formulas in Tau

Here's a modified a geometry formula sheet so all the presentations of circular shapes are in terms of tau (not pi); tack it to your wall and see if anybody spots the difference.

(Original sheet here.)

On Zeration

In my post last week on hyperoperations, I didn't talk much about the operation under addition, the zero-th operation in the hierarchy, which many refer to as "zeration". There is a surprising amount of disagreement about exactly how zeration should be defined.

The standard Peano axioms defining the natural numbers stipulate a single operation called the "successor". This is commonly written S(n), which indicates the next natural number after n. Later on, addition is defined in terms of repeated successor operations, and so forth.

The traditional definition of zeration, per Goodstein, is: \(H_0(a, b) = b + 1\). Now when I first saw this, I was surprised and taken aback. All the other operations start with \(a\) as a "base", and then effectively apply some simpler operation \(b\) times, so it seems odd to start with the \(b\) and just add one to it. (If anything my expectation would have been to take \(a+1\), but that doesn't satisfy the regular recursive definition of \(H_n\) when you try to construct addition.)

As it turns out, when you get to this basic level, you're doomed to lose many of the regular properties of the operations hierarchy. So there's nothing to do but start arguing about which properties to prioritize as "most fundamental" when constructing the definition.

Here are some points in favor of the standard definition \(b+1\): (1) It does satisfy the recursive formula that repeated applications are equivalent to addition (\(H_1\)). (2) It does looking passingly like counting by 1, i.e., the Peano "successor" operation. (3) It shares the key identity that \(H_n(a, 0) = 1\), for all \(n \ge 3\). (4) Since it is an elementary operation (addition, really), it can be extended from natural numbers to all real and complex numbers in a fashion which is analytic (infinitely differentiable).

But here are some points against the standard definition (1) It is not "really" a binary operator like the rest of the hierarchy, in that it totally ignores the first parameter \(a\). (2) Because of its ignoring \(a\), it's not commutative like the other low-level operations n = 1 or 2 (yet like them it is still associative and distributive, or as I sometimes say, collective of the next higher operation). (3) For the same reason, it has no identity element (no way to recover the value \(a\), unique among the entire hyperoperations hierarchy). (4) It's the only hyperoperation which doesn't need a special base case for when \(b = 0\). (5) I might turn around favorable point #3 above and call it weird and unfavorable, in that it is misaligned in this way with operations n = 1 and 2, and it's the only case of one of the key identities being added at a lower level instead of being lost. See how weird that looks below?

So as a result, a variety of alternative definitions have been put forward. I think my favorite is \(H_0(a, b) = max(a, b) + 1\). Again, this looks a lot like counting; I might possibly explain it to a young student as "count one more than the largest number you've seen before". Points in favor: (1) Repeated applications are again the same as addition. (2) It is truly a binary operation. (3) It is commutative, and thus completes the trifecta of commutativity, association, and distribution/collection being true for all operations \(n < 3\). (4) It does have an identity element, in \(b = 0\). (5) It maintains the pattern of losing more of the high-level identities, and in fact perfects the situation in that none of the five identities hold for this zeration (all "no's" in the modified table above for \(n = 0\)). Points against: (1) It isn't exactly the same as the unary Peano successor function. (2) It's non-differentiable, and therefore cannot be extended to an analytic function over the fields of real or complex numbers.

There are vocal proponents of related possible re-definition: \(H_0(a, b) =  max(a, b) + 1\) if a ≠ b, \(a + 2\) if a = b. Advantage here is that it matches some identities in other operations, like \(H_n(a, a) = H_{n+1}(a, 2)\) and \(H_n(2, 2) = 4\), but I'm less impressed by specific magic numbers like that (as compared to having commutativity and the pattern of actually losing more identities). Disadvantage is obviously that the possibility of adding 2 in the \(a+2\) case gets us even further away from the simple Peano successor function.

And then some people want to establish commutativity so badly that they assert this: \(H_0(a, b) =  ln(e^a + e^b)\). That does get you commutativity, but at that point we're so far away from simple counting in natural numbers that I don't even want to think about it.


Final thought: While most people interpret the standard definition of zeration, \(H_0(a, b) = b + 1\) as "counting 1 more place from b", it makes more sense to my brain to turn that around and say that we are "counting b places from 1". That is, ignoring the \(a\) parameter, start at the number 1 and apply the successor function repeatedly b times: \(S(S(S(...S(1))))\), with the \(S\) function appearing \(b\) times. This feels more like "basic" Peano counting, it maintains the sense of \(b\) being the number of times some simpler operation is applied, and it avoids defining zeration in terms of the higher operation of addition. And then you also need to stipulate a special base case for \(b = 0\), like all the other hyperoperations, namely \(H_0(a, 0) = 1\).

So maybe the standard definition is the best we can do, and the closest expression of what Peano successor'ing in natural numbers (counting) really indicates. Perhaps we can't really have a "true" binary operator at level \(H_0\), at a point when we haven't even discovered what the number "2" is yet.

P.S. Can we consider defining an operation one level even lower, perhaps \(H_{-1}(a, b) = 1\) which ignores both parameters, just returns the natural number 1, and loses every single one of the regular properties of hyperoperations (including recursivity in the next one up)?

On Hyperoperations

Consider the basic operations: Repeated counting is addition; repeated addition is multiplication; repeated multiplication is exponentiation. Hyperoperations are the idea of generally extending this sequence. This was first proposed as such, in a passing comment, by R. L. Goodstein in an article to the Journal of Symbolic Logic, "Transfinite Ordinals in Recursive Number Theory" (1947):

At this point, there are a lot of different ways of denoting these operations. There's \(H_n\) notation. There's the Knuth up-arrow notation. There's box notation and bracket notation. The Ackerman function means almost the same thing. Conway's chained arrow notation can be used to show them. Some people concisely symbolize the zero-th level operation (under addition) as \(a \circ b\), and the fourth operation (above exponentiation) as \(a \# b\). Wikipedia reiterates Goodstein's original definition like so, for \(H_n (a,b): (\mathbb N_0)^3 \to \mathbb N_0\):

Let's use Goodstein's suggested names for the levels above exponentiation. Repeated exponentiation is tetration; repeated tetration is pentation; repeated pentation is hexation; and so forth. Since I don't see them anywhere else online, below you'll find some partial hyperproduct tables for these next-level operations (and ODS spreadsheet here). Of course, the values get large very fast; you'll see some entries in scientific notation, and then "#NUM!" indicates a place where my spreadsheet could no longer handle the value (that is, something greater than \(1 \times 10^{308}\)).

From this point forward, the hyperoperation tables look passingly similar in this limited view. You have some fixed values in the first two rows and columns; the 2-by-2 result is eternally 4; and everything other than that is so astronomically huge that you can't even usefully write it in scientific notation. Here are some identities suggested above that we can prove pretty easily for all hyperoperations \(n > 3\):

1. \(H_n(a, 0) = 1\) (by definition)
2. \(H_n(a, 1) = a\)
3. \(H_n(0, b) = \) 0 if b odd, 1 if b even
4. \(H_n(1, b) = 1\)
5. \(H_n(2, 2) = 4\)

One passingly interesting question is how many of these master identities hold true in the lower operations (n = 1 to 3; addition, multiplication, and exponentiation); in short, each step further down the hierarchy loses more of these identities, as summarized here:

Now, to connect up to my post last week, recall the basic properties of real numbers taken as axiomatic at the start of most algebra and analysis classes. Addition and multiplication (n = 1 and 2) are commutative and associative; but exponents are not, and neither are any of the higher operations.

Finally consider the general case of distribution, what in my algebra classes I summarize as the "General Distribution Rule" (Principle #2 here). Or perhaps based on last week's observation I might suggest it could be better phrased as "collecting terms of the next higher operation", like \(ac + bc = (a+b)c\) and \(a^c \cdot b^c = (a \cdot b)^c\), or in the general hyperoperational form: 

\(H_n(H_{n+1}(a, c), H_{n+1}(b, c)) = H_{n+1}(H_n(a, b), c)\)

Well, just like commutativity and associativity, distribution in this general form also holds for n = 1 and 2, but fails for higher operations. Here's the first counterexample, using \(a \uparrow b\) for exponents (\(H_3\)), and \(a \# b\) for tetration (\(H_4\)):

\((2\#2)\uparrow (0\#2) = 4 \uparrow 1 = 4\), but

\((2 \uparrow 0)\#2 = 1 \# 2 = 1\). 

Likewise, what I call the "Fundamental Rules of Exponents" (Principle #1 above, or also here) works only for levels \(n \le 3\), and fails to be meaningful at higher levels of hyperoperation.

Why Is Distribution Prioritized Over Combining?

So I've come up with this question that's been bothering me for weeks,and I've been searching and asking everyone and everywhere that I can. I suspect that it may have no answer. The question is this:

Consider the properties of real numbers that we take for granted at the start of an algebra or analysis class (commutativity, association, and distribution of multiplying over addition). Granted that the last one, distribution (the transformation \(a(b+c) = ab + ac\)), is effectively equivalent to what we might call "combining like terms" (the transformation \(ax + bx = (a+b)x\)). It seems like the latter is more fundamental and easier to intuit as an axiom, since it resembles simple addition of units (e.g., 3 feet + 5 feet = 8 feet). So historically and/or pedagogically, what was the reason choosing the name and order we have ("distribution", \(a(b+c)=ab+ac\)), instead of the other option ("combining", \(ax+bx = (a+b)x\)) for the starting axiom?

I suspect now that there simply isn't any reason that we can document. Some expansion on the problem:

In dimensional analysis, some call the idea of only adding or comparing like units the "Great Principle of Similitude". Which provides some of my motivation for wishing that we would start with this ("combining") and then derive distribution (using commutativity a few times). Note that this phrase is in many places erroneously attributed to Newton; in truth the earliest documented usage of the phrase is by Rayleigh in a letter to Nature (No. 2368, Vol. 95; March 18, 1915). I could probably write a whole post just on the hunt for this quote. Big thanks to Juan Santiago who teaches a class by that name at Stanford (link) for helping me track down the article.

The Math Forum at Drexel discusses some history of the names of the basic properties. The best that Doctor Peterson can track down is that terms such as "distribution" were first used in the late 1700's to 1800's (starting in French in a memoir by Francois Joseph Servois). No commentary on a reason for why this was picked over alternative formulations. But perhaps the fact that the original discussion was in terms of functions (not binary operators) provides a clue. (For the full French text, see here and search "commutative and distributive").

Here's me asking the question at the StackExchange Mathematics site. Unfortunately, most commentators considered it to be uninteresting. When it got no responses, I cross-posted to the Mathematics Educators site -- which is apparently a huge faux pas, and immediately got it down-moderated into oblivion. The only relevant answer to date was from Benjamin Dickman, who pointed to a very nice quote from Euclid: when he states a similar property in geometric terms (area of a rectangle versus the sum of it being sliced up), it happens to be in the same order as we present the distribution property. But still no word on any reason why it should be in that order and not the reverse. 

Observations from a few textbooks that I have lying around:

• Rietz and Crathorne, Introductory College Algebra (1933). Article 4 shows combining like terms, and asserts that's justified by the associative law (which is nonsensical). The distributive property isn't presented until later, in Article 8.
• Martin-Gay, Prealgebra & Introductory Algebra. In the purely numerical prealgebra section, this first shows up as distribution among numbers (Sec 1.5). But the first time it appears in the algebra section with variables it is in fact written and used for combining like terms (Sec 3.1: \(ac + bc = (a+b)c\), although still called the "distributive property"). Combining like terms is actually done even earlier than that on an intuitive basis (see Sec. 2.6, Example 4). Only later is the property presented and used to remove parentheses from variable expressions.
• Bittinger's Intermediate Algebra shows standard distribution, followed immediately by use for combining like terms. Sullivan's Algebra & Trigonometry does the same.

So my point with those sources is that even though distribution is usually presented in a removing-parentheses format, in practice many textbook authors find themselves unable to escape the need to use combining like terms at some earlier point in their presentation (Rietz and Crathorne, Martin-Gay). This observation bolsters my growing instinct that it would be more intuitive to present the property in that format in the first place (as Martin-Gay does, the first time it appears with variables), and then derive what we call distribution from that.

Another thought is that while you can point to distribution as justifying the standard long-multiplication process (across decimal place value), the interior additions are implied and not explicit, and so they don't really serve to develop intuition in the same way that simple unit addition does.

Therefore, I find myself fantasizing about the following. Write a slightly nonstandard algebra textbook that starts by assuming commutativity, association, and the combining-like-terms-property (and shortly after deriving the distribution property). Perhaps for a better name it could be called "collection of like multiplications inside addition", or something like that.

Do you think this would be a better set of axioms for a basic algebra class? Can you think of a solid historical or pedagogical reason why the name and presentation were not the other way around, like this? Likely some more on this later.

Rational Numbers and Randomized Digits

Here's a quick thought experiment to develop intuition about the cardinality of rational versus irrational decimal numbers. We know that any rational number (a/b with integer a, b and b ≠ 0) has a decimal expansion that either terminates or repeats (and terminating is itself equivalent to ending with a repeating block of all 0's).

Consider randomizing decimal digits in an infinite string (say, by using a standard d10 from a roleplaying game, shown above). How likely does it seem that at any point you'll start rolling repeated 0's, and nothing but 0's, until the end of time? It's obviously diminishingly unlikely, so effectively impossible that you'll roll a terminating decimal. Alternatively, how probable does it seem that you'll roll some particular block of digits, and then repeat them in exactly the same order, and keep doing so without fail an infinite number of times? Again, it seems effectively impossible.

So this intuitively shows that if you pick any real number "at random" (in this case, generating random decimal digits one at a time), it's effectively certain that you'll produce an irrational number. The proportion of rational numbers can be seen to be practically negligible compared to the preponderance of irrationals.

Algebra for Cryptography

Cryptography researcher Victor Shoup recently gave a talk at the Simons Institute at Berkeley. Richard Lipton quotes him in one of his interesting observations about cryptography:

He also made another point: For the basic type of systems under discussion, he averred that the mathematics needed to describe and understand them was essentially high school algebra. Or as he said, “at least high school algebra outside the US.”

Quoted here.