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.


Carnival of Mathematics #38: 8-8-8

We at CatSynth are happy to be hosting the 38th Carnival of Mathematics, a bi-weekly round-up of mathematical posts from around the blogosphere. This is our second time hosting, and it falls on an auspicious day, August 8, 2008 or 8-8-8!

Eight is associated with good fortune and prosperity in Chinese culture, and so a trio of eights is especially fortunate. It is no accident that the Olympics in Beijing opened today.

Mathematically, 8 is of course a power of two, the third power of two in fact. 8 * 8 * 8 is 512. 8 raised to the 8th power raised the 8th power is…well…a very big number:

6277101735386680763835789423207666416102355444464034512896

Coincidentally, “888” is the name of a popular former product by my current employer.

So, with so much coincidence and good fortune surrounding the three eights, one would think this would be a great day for us at CatSynth. And they would be wrong, it is in fact rather bad day, capping a not-so-great week. So does that make us uniquely star-crossed? Probably not, but it does call into question the idea of using numerical patterns to divine good fortune.

And that brings us to our first entry, entitled Don’t Listen to Numbers from epsilonica. People have found significance in the patterns of digits of ? and the square root of 2 and countless other numbers for centuries, but as this post suggests, such patterns are inevitable. And very profound, when you think about the fact that this blog post, or any great work of literature or digitized music file can be represented by a unique number in binary, or English text in base 27.

So numerical patterns should be viewed with caution. So should the well-known statistical tool, the histogram, as described the Parable of the Histogram at ecthathy. The parable shows how the partitioning of data in to histograms can lead to very different interpretations, as a slight offset produces very different results for a group of students.

A numerical reality today is the explosion of online math videos, as report by the Teaching College Math Technology Blob. Videos on mathematical topics can be quite interesting and entertaining, especially for people who read blog posts about math. But they can be a source for media-oriented students to get answers to math problems without fully understanding the solution. And since correct solutions should be identical, it is more difficult to track down such sources than it is for essays.

Some of us learned mathematics not just to pass a class in school, but for the enjoyment, and perhaps for the realization that it is valuable to many aspects of our lives. You can read more about why we learn math at the blog It’s the Thought That Counts. This site has a lot of articles about science, religion and politics, and Barack Obama as well, so worth a detour…

Ok, back to mathematics. Sam Shah offers us a mind-boggling maximization problem, it is deceptively simple, but ends up brining in some rather difficult numbers (which I am sure have some strange and mystical patterns hidden inside of them). He also explains the Richter Scale and Logarithms, a topic close to many of us here in California.

Larry Ferlazzo presents a math word game, in which players have to chose the words that correctly describe the displayed numbers. It is geared towards beginning English Language students. I wonder if they can find the solutions to these problems on YouTube…

One of my favorite disciplines within mathematics is number theory, and our friends at Walking Randomly offer a method to generate Fibonacci numbers from matrix determinants. In particular, they can be generated from the determinants of a tridiagonal matrix with the imaginary number i in the “side bands.” It is always fascinating to see interesting mathematical concepts unified, in this case imaginary numbers, linear algebra and the Fibonacci sequence.

More interesting ideas with matrices and sequences can be found in this discussion of Phylogenetics and Algebraic Geometry at Rigorous Trivialities. Again, this crosses over into the complex numbers, and vector spaces.

The order of operations is a fundamental concept in arithmetic and computation. Apparently, it does not apply to the world of reality television, where producers have about as much mathematical literacy as a $1 calculator. Our friends at 360 analyze a recent mathematical puzzle given to contestants on the popular British TV program Big Brother.

I wonder how those contestants would do at coloring a plane, a interesting problem posed by Skeptics Play and explored in detail by Yoo at Stochastic Scribbles

Jon Ingram presents the game of Nim at Lessons Taught; Lessons Learnt. He starts with volunteers at conference to introduce this simple but fascinating game, and then plots the losing positions using Autograph. The result is quite surprising.

More observations on innumeracy in Why Can’t Johnny Add? at Staring at Empty Pages. The problems illustrated are not so much basic arithmetic as basic algebra, and how students can lack these basic skills in both 1983 and 2008.

From basic algebra, we move back to probability statistics, and normal errors for binomial and Poisson distributions. Textbooks say the normal distribution is good when “n is large”, but how large is large enough?

Next, The Endeavor presents an article on connecting probability and number theory. Prime numbers, and some properties of integers like the number of distinct prime divisors, can behave like random variables. This is an area of interest for me right now, not only with prime numbers, but also the other problems such as the Collatz Conjecture.

The above link to the Collatz Conjecture and related problems is from our friend Andrée of meeyauw, who this week presents aFriday Fractal: Pink Dragon Spewing Pink Flame.

That concludes the carnival for now. We will continue to post submissions through the weekend (including any we have missed due to 8-8-8 contrary fortunate), so please let us know if we missed you.


Carnival of Mathematics at CatSynth on Friday

The Carnival of Mathematics is returning to CatSynth this Friday!

You can submit your mathematical articles to the carnival by leaving a comment here, contacting us, or the carnival submission form. Leaving a comment is the best way to ensure your article will make it in time, but we will be compiling results from all sources and using our best mathematical talents to test for equivalency among multiple submissions.


The Fourier Transform of a Cat

We at CatSynth never miss an opportunity to combine mathematics and cats. Recently, our friends at Walking Randomly posted this image:

It was created by Andrew J. Bennieston, and inspired by this comic from xkcd:

Unlike the number theory and other mathematics we like to post here at CatSynth, the Fourier Transform is part of our stock and trade. There are many variants, including the Discrete Time Fourier Transform which one of the basic tools of signal processing and sound synthesis:

Basically, what a Fourier Transform does is decompose a signal (or any time-varying mathematical function) into separate frequencies. If you have a spectrum representation of a sound, this is output of a Fourier Transform. Similarly, if you have a graphic equalizer on your stereo, it can be seen as operating on a very low-resolution Fourier transform, as it allows one to raise and lower different frequency ranges of sound.

For images, “frequency” corresponds to detail. Highly detailed areas of image that change from pixel to pixel are high-frequency, while areas of constant color or intensity are lower frequency. Another variant of the Fourier Transform, the Discrete Cosine Transform, or DCT, is more often used with images because it tends to put more information in lower frequencies.

Theoritcally, one should not lose any information when taking a Fourier Transform of a signal (or image) and taking the inverse to retrieve the original. However, in Bennieston’s image, which applies two DCTs to the original image, results in the “ghost” that loses a bit of the original detail. Certainly, some is due to the rounding error when doing any calculations on the computer, but it seems like more than that. Most, likely, the DCT is more sensitive the boundaries, i.e., what happens at the beginning or end of a signal.

DCTs are often used in “lossy” image and audio compression, such as JPEG for images. However, I have rarely seen them used in music applications, where one tends to see more general Fourier Transformations, which correspond more closely to an intuitive understanding of musical frequency.

As such, it would be interesting to work with DCTs in a musical context and see what transpires. If we ever get around to this project, we will certainly post it here on CatSynth.

This post is part of the Carnival of Mathematics which is being hosted this weekend by Logic Nest.


Math Cats

In search of my next mathematics topics, I stumbled upon the Math Cats, a site that uses cats to explore a variety of mathematical topics, from the very basic to the more esoteric. The emphasis is really on “exploration” rather than a series of lessons or tutorials, though there is a collection of resources for teachers and parents. Beyond the basics, the attic is full of facts and definitions, some of which are quite sophisticated (for example, do you remember exactly what a geodesic is, and who doesn’t want to forget avoirdupois weights). Sadly, I could not make the “Animal Math” link work. I was particularly fond of the virtual mobile, which also introduces viewers to the work of Alexander Calder. There is also a visit to a more recent geometric artist George Hart. Indeed his art studio looks a bit like the music studio here at CatSynth HQ, festooned with stuffed cats.

Among the shapes the Hart uses in his work are the regular polyhedra, but also Archimedean solids, such as the truncated icosohedron, or “buckyball.” You can see an example here, as well as some of the more esoteric shapes.

This of course ties into our discussion of the 13 Archimedean solids at the last Carnival of Mathematics, and we at CatSynth of course like to see our mathematical discussions interconnect.

And who can go wrong with the intersection of cats, mathematics and art?


Carnival of Mathematics #35

We at CatSynth are delighted to be hosting the 35th Carnival of Mathematics.

The date “Friday the 13th” of course evokes many superstitions. And perhaps that is why we have so few entries so far this weekend. That having been said, we at CatSynth take a dim view of superstitions. Many of the traditions that led to the irrational fear of the number 13 (including skipping over of 13 in building floor numbers, etc) are the same ones that promote the unfair treatment of black cats. Neither has a place in a modern, rational, society.

Consider that 13th of the month is no more likely to fall on a Friday than any other day of the week. Over a period of 28 years, that is 48 “Fridays the 13th,” as described here.

Let us turn away from superstition and myth, so some of the more mathematical properties of the number 13. It is a prime number (indeed, the sixth smallest prime). It is also a well-known twin prime, and it is one of only three known Wilson primes. For those less interested that I am in prime numbers, it is also a Fibnoacci number, and the number of Archimedean solids.

You can find more about the mathematics and mythology of 13 at “13 the Unlucky”.

Last week’s host, the blog 360, has a post about 13 and other “unlucky” numbers. But they also contribute a demonstration, using Godzilla, of how to calculate the speed of a
dinosaur by its footprints
.

Recursivity introduces us to the Open Problem Garden, a site collecting open problems in mathematics and theoretical computer science. He presents an open problem about discrete iterations that is easy to state yet frustratingly hard to solve, as are many of the great problems of mathematics.

Looking for a more modest challenge? Math and Logic Play presents a bicycle-racing puzzle. Practice your math skills while staying healthy and reducing your carbon footprint…

Larry Ferlazzo describes a site for math games and education in Tutpup Math & Spelling Games.

Andrée from meeyauw treats us to Sierpinski cookies and earings this week. Those cookies look pretty good, but challenging to make. Fractals are by nature very detail oriented, and I am by nature very not detail oriented. But I’m sure they would taste great in either case.

The state of math education (in the United States) in a frequent topic on Carnival of Mathematics. This week, female math professor critiques an elementary school math program at Life on the Tenure-Track. It seems that at least in some classes, teachers aren’t able to make it through the full syllabus.

More topics in math education can be found at Teach College Math, where we are introduced to the Math Girl videos. “Who says there’s nothing good on YouTube?”

For the more discriminating reader, we have Discriminating Determinants, third in a series from Matt-a-matical Thinking.

We get back to our theme of the number 13. The fashionablemathematician presents the sum of prime factors. For a prime number like 13, the sum is of course the same: 13. But are there other numbers whose prime factors sum to 13? Well, the number 22 has prime factors 2 and 11, which add up to 13.

Sometimes a mathematician can end up being an astrophysicist, especially on Friday the 13th, as is the case with this article from Math Trek.

That is all the posts we currently have. We will continue to add sites throughout the weekend, so please leave a comment or contact us if you would like to participate.



]]

Prime-counting function revisited

A couple of weeks ago we posted an article on “Calculus for Cats” and the Prime Number Theorem, which featured the, the prime-counting function π(x):

Basically, this function counts the number of primes less than or equal to a particular number. For example π(20) would be all the prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17 and 19. So π(20) = 8.

So to calculate π(1000) would one have to literally count all the prime numbers less than 1000, including figuring out which numbers are prime? And what about π(1000000)? Unfortunately, the answer is yes.

Unfortunately, the answer is no, as Victor points out in the comments. Or more specifically, Victor's cat Blue Chip says “Neow!” I think is the point where one is supposed to say “my bad.” Victor is in fact V. S. Miller who co-authored the paper “Computing pi(x): The Meissel-Lehmer Method”.

The oldest method for computing π(x) is to use the sieve of Eratosthenes, which is literally counting all the primes below x. More efficient methods have existed for quite a while, notably astronomer E. D. F. Meissel found a method in the 1870s that he used to compute π(100,000,000) as 5,761,455; and π(1,000,000,000), though his result was found to be slightly off (too small by 56). It should be noted that Meissel carried out his calculations without the aid of a digital computer. D.H. Lemher extended and simplified Meissel's method in the context of modern computers, and calculated π(1010).

Miller and his co-authors present new algorithms that refine the Meissel-Lehmer method, including new sieving techniques and optimizations for parallel computing. Those interested in the technique are encouraged to read the paper. The “Extended Meiseel-Lehmer” technique is used to compute π(1016) as 279,238,341,033,925.

They also include an interesting chart comparing large values of π(x) and Li (x), the offset logarithmic integral that we presented in our article. Recall that Li(x) is an upper bound on the value of π(x). And for 1016, the difference between Li(x) and π(x) is 3,214,632. Only off by three million, which isn't too bad…

This post was included in Carnival of Mathematics #33 at Walking Randomly.

Calculus for Cats and Prime Number Theorem

<I was looking for a quick way to combine cats and mathematics this morning, and came across the book Calculus for Cats.

This is a book for people about to take calculus, and for survivors of calculus who still wonder what it was all about. It gently explains the basic concepts and vocabulary without making the reader ever do a single problem.

Basically, the book draws (quite literally) an analogy between the fluid motion of cats at play (or in pursuit of “prey”) and the concepts and techniques of calculus, which focuses on continuous functions.

We at CatSynth remember calculus fondly as a mathematical pursuit. But number theory is more my thing. Calculus primary concerns itself with continuous functions of real and complex numbers, while number theory deals with discrete entities, like integers. But in mathematics, all things are interconnected. For example, we demonstrated the connection between the gamma function, pi and factorials, combining continuous and discrete concepts.

Consider the function π(x), the prime-counting function. It's a bit unfortunate they chose the symbol π, but it is what it is. Basically, this function counts the number of primes less than or equal to a particular number. For example π(20) would be all the prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17 and 19. So π(20) = 8.

So to calculate π(1000) would one have to literally count all the prime numbers less than 1000, including figuring out which numbers are prime? And what about π(1000000)? Unfortunately, the answer is yes. But there are good ways to approximate the number of primes, using the results of the Prime Number Theorem. Those interested in the formal theorem are encouraged to follow the link, but we will skip ahead to one of the interesting results. One of basic functions to come out of calculus is the natural logarithm ln(x), whose base is the famous constant e. If you don't know about it, go look it up. Otherwise, the rest of this article will not make much sense. One can use ln(x) to build more complicated functions in calculus, one of which is the offset logarithmic integral, or Li(x):

This is one of those functions, like the gamma function, that cannot be expressed without the use of calculus. Turns out, however, that it is a good approximately for π(x), which is very much a discrete concept and quite distant from the continuous motions involved in calculus. The prime number theorem provides the connection.

This article is included in Carnival of Mathematics #31 at recursivity.

The logistic function revisted

Today we revisit one of our most popular articles, on the logistic function:

f(x) = ax(x-1)

In the original article, we demonstrated how we can use this function as a “logistic map” by iterating (i.e.,applying it repeatedly to the previous result). The logistic map produced different sorts of behavior depending on the values of a. For example, for some values of a, iteration settles into a cycle, bouncing among two or more points on the function.

The original article provided more examples and more detail about the mathematics, and those who are interested are encouraged to go back and check it out. One of the main this we discussed was how one can characterize the logistic function over
different values of a using a graph called a bifurcation
diagram
. As the values of a increase (a is labelled as “r” in this graphic I shamelessly but legally ripped off from wikipedia), one can observe vertically the period doubling where the logistic map converges on a single value, then bounces between two points, then four, then eight, and so on, until the onset of chaos at approximately 3.57.

When a is greater than or equal to 4, the function “diverges”, i.e., it just gets bigger and bigger (or smaller and smaller because the numbers are negative) when you repeatedly apply it.

The bifurcation diagram shows what happens for real values of a, i.e., all integers, fractions and other numbers that can be expressed as a decimal. But suppose we allow a to be any complex number, or any combination of real and “imaginary” numbers (i.e., square roots of negative numbers). Real numbers can be expressed a line, while complex numbers are expressed on a plane. So we can produce an analog of the bifurcation diagram over a plane instead of a line as above.

In the following diagrams, we are looking at the complex plane of
different values for a. If the logistic map converges to either a single value or a cycle, the location on the plane is colored in black. If it diverges, i.e., gets infinitely farther away from zero, then the location is white. Unlike for real numbers, where the convergent “black” values of a form a simple line segment, for complex numbers the set of convergent values is a lot more “complex”:

Zooming in, we can see the structure of the set, with lots of smaller “bubbles” and “filaments” off of the main circles. The large circles are the complex-number equivalents of the single-line sections of the bifurcation diagrams, with the small bubbles representing cycles and period doubling.

Some readers might recognize similarities between this set and more well-known Mandelbrot set:

The similarity is more than coincidence, as the Mandelbrot set is based on a map similar to the logistic map. But the Mandelbrot set has the pronounced cardioid shape and asymmetry different from the logistic-map set. Zooming in further, we see that filaments and local areas of the two sets have more similarity. Indeed, we see small “Mandelbrot-like sets” at the junctions of the filaments:

It is interesting how these miniature versions have a shape similar to Mandelbrot set rather than the double-circle of the logistic-map set.

Although these sets have a “fractal-like” qualities, neither is a fractal in the strict sense of the word. They are not strictly self-similar, nor do they have fractional dimension. Nonetheless, we are featuring the logistic-map set as a “Friday Fractal” , an event started by our friend Andrée at meeyauw.

I am not sure the logistic-map set has a name like the Mandelbrot set has, so how about calling it the CatSynth set?

Submitted to Carnival of Mathematics #29.