The Fundamental Theorem of Arithmetic

It is not uncommon to hear operations on numbers, even the computations carried out in modern computers, as “mere arithmetic.” But arithmetic is hardly simple or obvious when one gets down to the fundamentals and realizes the structure that must be present in our number system in order for it to work they way we intuitively think it should work. Thus, today we consider the Fundamental Theorem of Arithmetic.

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes.

Thus every integer has a canonical representation as a product of powers of primes:

where p1 < p2 < … < pk are primes and the αi are positive integers; 1 is represented by the empty product. As example 12 = 22 × 3, and 666 = 2 × 32 × 37. Fairly familiar stuff for anyone who paid attention during grade school and secondary school math classes. But the theorem itself is not self-evident, it is something that had to be proven true in order for our everyday arithmetic to hold. A good article on why the theorem is not obvious can be found here. It also has implications beyond the natural numbers. If we extend the canonical representation to allow both positive and negative values for ai, we get the set of positive rational numbers (fractions), for which the theorem still holds. It can also be generalized to more exotic constructions, such as Gaussian Integers. Gaussian integers, often denoted ℤ[i] are complex numbers a + bi where i is the square root of -1, and a and b are integers. It can be shown that the fundamental theorem of arithmetic holds for Gaussian integers, and that there is a definite set of “Gaussian primes” just as there are prime numbers. But while plotting the prime numbers and looking for visual patterns is an exercise in frustration, the rotational nature of complex numbers (which we have discussed in a previous article) causes the Gaussian primes to fall into a visually interesting radial pattern:

With all the important and sometimes confounding properties of primes, having ways to visualize them is always intriguing.

Any mathematical construct (specifically, a “domain”) that obeys the fundamental theorem of arithmetic is known as a Euclidean Domain. (Note that this has very little to do with Euclidean spaces or the other uses of the term in geometry.) We can observe many more Euclidean domains, such as generalizing Guassian integers to other roots of 1. If we use the cube roots of 1, for example (yes, 1 has three cube roots), we get the set of Eisenstein Integers: numbers of the form a + bω, where a and b are integers and:

Like Gaussian primes, Eisenstein primes have a distinctive radial pattern when viewed on the complex plane. Whereas Guassian primes divide into quadrants, Eisenstein primes form a hexagonal pattern.

Note that while the generalization works for square roots of -1, cube roots of 1, etc., it doesn’t necessarily work for all roots of 1. Some of those sets will not form Euclidean domains.

We can also look beyond numbers to other mathematical entities that form Euclidean domains. One such example can be found in knot theory, which we discussed in an article a few years ago. Knots can be expressed as unique combinations of prime knots:

From here we can consider the implications for music of the Euclidean domains, the accompanying Euclidean algorithm for computing greatest common divisors in any of these domains. But that will be left as an exercise for another day.

Knot Theory

Today we explore the topic of Knot Theory. Most of us have a conventional idea of what a “knot” is; and those who were once Boy Scouts may have a more formal idea. But in mathematics, a knot has a very formal defintion: an embedding of a circle in 3-dimensional Euclidean space, R3, considered up to continuous deformations (isotopies). An example of a mathematical knot, the “figure eight knot”, is illustrated below:

Basically, it is a continuous curve in three-dimensional space that loops back on itself, crossing an arbitrary number of times but never cut or spliced. It relates to the conventional notion of knot as a piece of string connected at the ends.

Knots relate to other topics that have been explored here at CatSynth, such as Lissajous curves.

Many knots, when projected onto a two-dimensional plane form Lissajous curves.

It also relates to our interest here at CatSynth in highway interchanges, such as this the intersection of I-105 and I-110 in Los Angeles:

Indeed, our friend whaleshaman of Jelly Pizza suggested the link between highway interchanges and knots, although mathematically such interchanges are really tangles.

Knots (and tangles) can be arbitrarily complex with twists and crossings. But there is order in this twisty world, and indeed knots have properties analogous to numbers, such as equivalency and prime decomposition.

Two knots are considered equivalent if one can be converted to another by simple scaling (stretching or rotating), or performing one of several Reidemeister moves, twisting or untwisting in either direction, moving one loop (or segment) completely over another, or move a string completely over or under another crossing. Basically, this is any operation you can do on a closed string without cutting or splicing it.

Here at CatSynth, we are quite familiar with Reidemeister moves, as they seem to occur spontaneously on our audio cables:

Even more interesting is how knots can be decomposed into prime knots. Just as any integer can be expressed as the product of prime numbers, any knot can be expressed as the “sum” of prime knots.

Here is a chart of the first 15 prime knots:


[Click image for original and more info]

Here, the prime knots are grouped by the number of crossings. For example, the trifoil knot (second from the left on the top) has three crossings. The circle is a degenerate case, known as the “unknot”, with zero crossings. As the number of crossings increases, the number of possible prime knots also increases. For example, there are seven unique prime knots with seven crossings.

For any positive integer n, there are a finite number of prime knots with n crossings. The first few values are given in the following table.

n number of prime knots
1 0
2 0
3 1
4 1
5 2
6 3
7 7
8 21
9 49
10 165
11 552
12 2176
13 9988
14 46972
15 253293
16 1388705

This sequence (formally listed as A002863), appears to grow exponentially. Indeed, results by Welsh show a lower bound of 2.68 for the exponential base, and an upper bound of 10.40 due to Stoimenow. However, as far as I can tell, there is know known analytical formula for this sequence, and the values for n=17 and above are not known.

I find such sequences of numbers fascinating. Where to they come from, and how does one figure out the next value? In the case of prime knots, these appear to be open problems.

For more information, Giovanni de Santi has an excellent introduction to the theory of knots. Another paper by [url=http://algo.inria.fr/bsolve/constant/constant.html]Steven R. Finch is a resource for advanced analysis of knots and tangles, including more on counting prime knots.