Carmichael Numbers: “not quite” primes…

We had a fun mathematics seminar yesterday.

Andrew Shallue gave a talk about the Carmichael numbers and gave a glimpse into his research. Along the way he mentioned the work of another mathematician…one that I met during my ultramarathon/marathon walking adventures! Talk about a small world..

So, to kick start my brain cells, I’ll say a few words about these.

First of all, prime numbers are very important in encryption schemes and it is a great benefit to be able to find them. However, for very large numbers, it can be difficult to determine whether a number is prime or not.

So one can take short cuts in determining whether a number is *likely* prime or not: one can say “ok, prime numbers have property P and if this number doesn’t have property P, it is not a prime. But if it DOES have property P, we hare X percent sure that it really is a prime.

If this said property is relatively “easy” to implement (via a computer), we might be able to live with the small amount of errors that our test generates.

One such test is to see if this given number satisfies “Fermat’s Little Theorem” which is as follows:

Let be a positive integer and be a prime, and suppose , that is Then

If you forgotten how this works, recall that is a field if is a prime, so means that the set consists of . So take the product . Now note that we are working in a field, so we can cancel the factor on both sides to get .

So one way to check to see if a number might be a prime is to check all for all and see if .
Now this is NOT a perfect check; there are non-prime numbers for which for all ; these are called the Carmichael numbers. The 3 smallest such numbers are 561, 41041 and 825265.

The talk was about much more than this, but this was interesting.

Why the sequence cos(n) diverges

We are in the sequences section of our Freshman calculus class. One of the homework problems was to find whether the sequence converged or diverged. This sequence diverges, but it isn’t easy for a freshman to see.

I’ll discuss this problem and how one might go about explaining it to a motivated student. To make things a bit simpler, I’ll discuss the sequence instead.

Of course is periodic with a fundamental region so we will work with that region. Now we notice the following:

is a group with the usual operation of addition.

By , I mean the set where ; one can think of the analogue of modular arithmetic, or one might see the elements of the group .

Of course, to get additive inverses, we need to include the negative integers, but ultimately that won’t matter. Example: are just equal to themselves , etc. So, I’ll denote the representative of by .

Now if then ; for if then there would be integers so that which would imply that is a multiple of . Therefore there are an infinite number of in which means that the set has a limit point in the compact set which means that given any positive integer there is some interval of width that contains two distinct (say, greater than .)

This means that so there is some integers so that , etc. Therefore there is some multiple of in every interval of width . But was an arbitrary positive integer; this means that the are dense in . It follows that is dense in and hence cannot converge as a sequence.

Frankly, I think that this is a bit tough for most Freshman calculus classes (outside of, say those at MIT, Harvard, Cal Tech, etc.).

Enigma Machines: some of the elementary math

Note: this type of cipher is really an element of the group , the symmetric group on 26 letters. Never allowing a letter to go to itself reduced the possibilites to products of cycles that covered all of the letters.

MathFest Day Three (Lexington 2011)

I left after the second large lecture and didn’t get a chance to blog about them before now.

But what I saw was very good.

The early lecture was by Lauren Ancel Meyers (Texas-Austin) on Mathematical Approaches to Infectious Disease and Control This is one of those talks where I wish I had access to the slides; they were very useful.

She started out by giving a brief review of the classical SIR model of the spread of a disease which uses the mass action principle (from science) that says that the rate of of change of those infected with a disease is proportional to the product of those who are susceptible to the disease and those who can transmit the disease: . (this actually came from chemistry). Of course, those who are infected either recover or die; this action reduces the number infected. Of course, the number of susceptible also drop.

This leads to a system of differential equations. The basic reproduction number is significant:
where is the recovery rate and is the death rate. Note: if then the disease will die off; if it is greater than 1 we have a pandemic. We can reduce this by reducing (vaccination or quarantine), increasing recovery or, yes, increasing the death rate (as we do with livestock; remember the massive poultry slaughters to stop the spread of flu).

Of course, this model assumes that the infected organisms contact others at random and have equal probabilities of spreading, that the virus doesn’t evolve, etc.

So this model had to be improved on; methods from percolation theory were developed.

So many factors had to be taken into account such as: how much vaccine is there to spread? How far along is the outbreak? (at first children get it; then adults). How severe is the consequences? (we don’t want the virus to evolve to a more dangerous, more resistant form).

Note that the graph model of transmission is dynamic; it can actually change with time.

Of special interest: one can recover the rate of infections of the various strains (and the strains vary from season to season) by looking at the number of times flu related words were searched for on Google. The graph overlap (search rate versus reported cases) was stunning; the only exception is when a scare occurred; then the word search rate lead the actual cases, but that happened only once (2009). Note also that predictions of what will happen get better with a shorter time window (not a surprise).

There was much more in the talk; for example the role of the location of the providers of vaccines was discussed (what is the optimal way to spread out the availability of a given vaccine?)

Manjur Bhargava, Lecture III
First, he noted that in the case where was cubic, that there is always a rational change of variable to put the curve into the following form: where are integers that have the following property: if is any prime where divides then does NOT divide . So this curve can be denoted as .

Also, there are two “generic” cases of curves depending on whether the cubic in has only one real root or three real roots.

This is a catalog of elliptical algebraic curves of the form taken from here. The everywhere smooth curves are considered; the ones with a disconnected graph are said to have “an egg”; those are the ones in which the cubic in has three real roots. In the connected case, the cubic has only one; remember that these are genus one curves; we are seeing a slice of a torus in 4-space (a space with two complex dimensions) in the plane.

Also recall that the rational points on the curve may be finite or infinite. It turns out that the rational points (both coordinates rational) have a group structure (this is called the “divisor class group” in algebraic geometry). This group has a structure that can be understood by a simple geometric construction in the plane, though checking that the operation is associative can be very tedious.

I’ll give a description of the group operation and provide an elementary example:

First, note that if is a point on an elliptical curve, then so is (note: the on the left hand side of the defining equation). That is important. Also note that we will restrict ourselves to smooth curves (that have a well defined tangent line).

The elements of our group will be the rational points of the curve (if any?) along with the point at infinity. If I will denote .

The operation: if are rational points on the curve, construct the line with equation Substitute this into and note that we now have a cubic equation in that has two rational solutions; hence there must be a third rational solution . Associated to that value is two values (possibly double if the value is zero). Call that point on the curve then define where is the reflection of about the axis.

Note the following: that this operation commutes is immediate. If one adds a point to itself, one uses the tangent line as the line through two points; note that such a line might not hit the curve a third time. If such a line is vertical (parallel to the axis) the result is said to be “0” (the point at infinity); if the line is not vertical but still misses the rest of the curve, it is counted three times; that is: . Here are the situations:

Of course, is the group identity. Associativity is difficult to check directly (elementary algebra but very tedious; perhaps 3-4 pages of it?).

Since the group is Abelian, if the group is finite it must be isomorphic to where the second part is the torsion part and the number of infinite cyclic factors is the rank. The rank turns out to be the geometric rank; that is, the minimum number of points required to obtain all of the rational points (infinite number) of the curve. Let be the torsion subgroup; Mazur proved that .

Let’s look at an example of a subgroup of such a curve: let the curve be given by It is easy to see that are all rational points. Let’s see how these work: so this point has order 2. But there is also some interesting behavior: note that which implies that So the tangent line through and are both horizontal; that means that both of these points have order 3. Note also that as the tangent line runs through the point . Similarly So, we can see that have order 6, have order 3 and has order 2. So there is an isomorphism where where the integers are mod 6.

So, we’ve shown a finite Abelian subgroup of the group of rationals of this curve. It turns out that these are the only rational points; here all we get is the torsion group. This curve has rank zero (not obvious).

Note: the group of rationals for is isomorphic to though this isn’t obvious.

The generator of the term is and generates the the torsion term.

History note Some of this was tackled by computers many years ago (Birch, Swinnerton-Dyer). Because computers were so limited in those days, the code had to be very efficient and therefore people had to do quite a bit of work prior to putting it into code; evidently this lead to progress. The speaker joked that such progress might not have been so quickly today due to better computers!

If one looks at where is prime, we should have about points on the curve. So we’d expect that . If there are a lot of rational points on the curve, most of these points would correspond to points. So there is a conjecture by Birch, Swinnerton-Dyer:
where is the rank.

Yes, this is hard; win one million US dollars if you prove it. 🙂

Back to the curves: there are ways of assigning “heights” to these curves; some include:
or

Given this ordering, what are average sizes of ranks?
Katz-Sarnak: half have rank 0, half have rank 1. It was known that average ranks are bounded; previous results had the bound at 2.3, 2, 1.79, assuming that the Generalized Riemann Hypothesis and the Birch, Swinnerton-Dyer conjecture were asssumed.

The speaker and his students got some results without making these large assumptions:

Result 1: when is ordered by height, the average rank is less than 1.
Result 2: A positive portion (10 percent, at least) have rank 0.
Result 3: at least 80 percent have rank 0 or 1.
Corollary: the BSD is true for a positive proportion of elliptic curves;

The speaker (with his student) proved results 1, 2, and 3 and then worked backwards on the existing “BSD true implies X” results to show that BSD was true for a positive proportion of the elliptic curves.

MathFest Day 2 (2011: Lexington, KY)

I went to the three “big” talks in the morning.
Dawn Lott’s talk was about applied mathematics and its relation to the study of brain aneurysms; in particular the aneurysm model was discussed (partial differential equations with a time coordinate and stresses in the radial, circumference and latitudinal directions were modeled).

There was also modeling of the clipping procedure (where the base of the aneurysm was clipped with a metal clip); various clipping strategies were investigated (straight across? diagonal?). One interesting aspect was that the model of the aneurysm was discussed; what shape gave the best results?

Note: this is one procedure that was being modeled:

Next, Bhargava gave his second talk (on rational points on algebraic curves)
It was excellent. In the previous lecture, we saw that a quadratic curve either has an infinite number of rational points or zero rational points. Things are different with a cubic curve.

For example, has exactly one rational point (namely (0,0) ) but has an infinite number! It turns out that the number of rational points an algebraic curve has is related to the genus of the graph of the curve in (where one uses complex values for both variables). The surface is a punctured multi-holed torus of genus with the punctures being “at infinity”.

The genus is as follows: 0 if the degree is 1 or 2, 1 if the degree is 3, and greater than 1 if the degree is 4 or higher. So what about the number of rational points:
0 or finite if the genus is zero
finite if the genus is strictly greater than 1 (Falting’s Theorem; 1983)
indeterminate if the genus is 1. Hence much work is done in this area.

No general algorithm is known to make the determination if the curve is cubic (and therefore of genus 1)

Note: the set of rational points has a group structure.

Note: a rational cubic has a rational change of variable which changes the curve to elliptic form:
Weierstrauss form: where are integers.
Hence this is the form that is studied.
Sometimes the rational points can be found in the following way (example: :
note: this curve is symmetric about the axis.
is a rational point. So is . This line intersects the curve in a third point; this line and the cubic form a cubic in with two rational roots; hence the third must be rational. So we get a third rational point. Then we use to obtain another line and still another rational point; we keep adding rational points in this manner.

This requires proof, but eventually we get all of the rational points in this manner.

The minimum number of “starting points” that we need to find the rational points is called the “rank” of the curve. Our curve is of rank 1 since we really needed only (which, after reflecting, yields a line and a third rational point).

Mordell’s Theorem: every cubic is of finite rank, though it is unknown (as of this time) what the maximum rank is (maximum known example: rank 28), what an expected size would be, or even if “most” are rank 0 or rank 1.

Note: rank 0 means only a finite number of rational points.

Smaller talks
I enjoyed many of the short talks. Of note:
there was a number theory talk by Jay Schiffman in which different conjectures of the following type were presented: if is some sequence of positive integers and we look at the series of partial sums, or partial products (plus or minus some set number), what can we say about the number of primes that we obtain?

Example: Consider the Euclid product of primes (used to show that there is no largest prime number)
etc. It is unknown if there is a largest prime in the sequence .

Another good talk was given by Charlie Smith. It was about the proofs of the irrationality of various famous numbers; it was shown that many of the proofs follow a similar pattern and use a series of 3 techniques/facts that the presenter called “rabbits”. I might talk about this in a later post.

Another interesting talk was given by Jack Mealy. It was about a type of “hyper-hyperbolic” geometry called a “Snell geometry”. Basically one sets up the plane and then puts in a smooth closed boundary curve (say, a line or a sphere). One then declares that the geodesics are those that result from a straight lines…that stay straight until they hit the boundary; they then obey the Snell’s law from physics with respect to the normal of the boundary surface; the two rays joined together from the geodesic in the new geometry. One can do this with, say, a concentric series of circles.

If one arranges the density coefficient in the correct manner, one’s density (in terms of area) can be made to increase as one goes outward; this can lead to interesting area properties of triangles.

Blogging MathFest, 2011 (Lexington, KY)

This is what I am talking about:

I started the day by attending three large lectures:
Laura DeMarco, University of Illinois at Chicago who spoke about dynamical systems (that result from complex polynomials; for example if is a function of the complex plane, one can talk about the orbit of a point . One can then talk about sets of points and This is called the Filled Julia Set.

Ed Burger of Williams (a graduate school classmate of mine who made good) gave the second; he talked about Fibonacci numbers and their relation to irrational ratios (which can be obtained by continued fractions) and various theorems which say that natural numbers can be written uniquely as specified sums of such gadgets.

Lastly Manjul Bhargava of Princeton (who is already full professor though he is less than half my age; he was an Andrew Wiles student) gave a delightful lecture on algebraic curves.

What I noted: all three of these mathematicians are successful enough to be arrogant (especially the third). They could have blown us all away. Yes, they took the time and care to give presentations that actually taught us something.

Of the three, I was the most intrigued by the last one, so I’ll comment on the mathematics.

You’ve probably heard that a Pythagorean triple is a triple of integers such that . For now, we’ll limit ourselves to primitive triples; that is, we’ll assume that have no common factor.

You might have heard that any Pythagorean triple is of the form: for integers. It is true that being defined that way leads to a Pythagorean triple, but why do ALL Pythagorean triples come in this form?

One way to see this is to look at an algebraic curve; in this case, the curve corresponding to . Why? Start with and divide both sides by to obtain One then notes that one is now reduced to looking to rational solutions to (a rational solution to this can be put in the form by getting a common denominator).

We now wish to find all rational points (both coordinates rational) on the circle; clearly is one of them.
Easy claim: if is such a rational point, then the line from to has rational slope.
Not quite as easy claim: if a line running through has rational slope then the line intersects the circle in a rational point.
Verification: such a line has equation and intersects the circle in a point whose value satisfies . This is a quadratic that has rational coefficients and root hence the second root must also be rational. Let’s calculate the second root by doing division: . So the point of intersection has latex and . Both are rational.

Therefore, there is a one to one correspondence between rational slopes and rational points on the circle and all are of the form . Note: we obtain by letting go to infinity; use L’Hopital’s rule on the first coordinate). So if we have any Pythagorean triple then But is rational hence we write where are relatively prime integers. Just a bit of easy algebra reveals which gives us as required.

The point: the algebraic curve motivated the proof that all Pythagorean triples are of that form.

Note: we can extract even more: if latex is any quadratic rational curve (i. e., , all coefficients rational, and is any rational point and there is a line through of rational slope which intersects the curve in a second point (the quadratic nature forbids more than 2 points), the second point must also be rational. This follows by obtaining a quadratic in by substituting and obtaining a quadratic with rational coefficients that has one rational root.

Of course, it might be the case that there is no rational point to choose for . In fact, that is the case for

Why? Suppose there is a rational point on this curve with both fractions in lowest terms. We obtain Now let’s work Mod 4 (hint from the talk): note that in therefore the sum of two squares can only be 0, 1 or 2. The right hand side is either 3 or 0; equality means that both sides are zero. This means that are both even and therefore is divisible by 4 therefore either is even or is even.
Suppose is odd. Then is even and because is even, is even. This contradicts the fact that are relatively prime. If is odd, then because is even, is even. This contradicts the fact that are relatively prime. So both are even which means that are odd. Write where are odd (possibly 1). Then . Now if we obtain on the left hand side (sum of two odd numbers squared) which must be 2 mod 4. The right hand side is still only 3 or 0; this is impossible. Now if, say, then we get which means that the odd number is the difference of two even numbers. That too is impossible.

Hence contains no rational coordinates; that circle manages to miss that dense set.

The point of all of this is that algebraic curves can yield significant information about number theory.

Photos

This is the German Enigma Coding machine (with plug board) at the NSA booth.

This is another view of the Enigma

Edward Burger; I had some bad timing here.

Just prior to the first talk.