College Math Teaching

September 23, 2016

Carmichael Numbers: “not quite” primes…

Filed under: algebra, elementary number theory, number theory, recreational mathematics — collegemathteaching @ 9:49 pm

We had a fun mathematics seminar yesterday.

mathseminar

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 a be a positive integer and p be a prime, and suppose a \neq kp , that is a \neq 0 (mod p) Then a^{p-1} = 1 (mod p)

If you forgotten how this works, recall that Z_p is a field if p is a prime, so a \in Z_p, a \neq 0 (mod p) means that the set \{a, 2a, 3a, ...(p-1)a \} consists of \{1, 2, 3, ...(p-1) \} . So take the product (a)(2a)(3a)...((p-1)a)) = 1(2)(3)..(p-1)a^{p-1} = 1(2)(3)...(p-1) (mod p) . Now note that we are working in a field, so we can cancel the (1)(2)...(p-1) factor on both sides to get a^{p-1} = 1 (mod p) .

So one way to check to see if a number q might be a prime is to check all a^{q-1} for all a \leq q and see if a^{q-1} = 1 mod q .
Now this is NOT a perfect check; there are non-prime numbers for which a^{q-1} = 1 mod q for all a \leq q ; 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.

February 5, 2016

More fun with selective sums of divergent series

Just a reminder: if \sum_{k=1}^{\infty} a_k is a series and c_1, c_2, ...c_n ,, is some sequence consisting of 0’s and 1’s then a selective sum of the series is \sum_{k=1}^{\infty} c_k a_k . The selective sum concept is discussed in the MAA book Real Infinite Series (MAA Textbooks) by Bonar and Khoury (2006) and I was introduced to the concept by Ferdinands’s article Selective Sums of an Infinite Series in the June 2015 edition of Mathematics Magazine (Vol. 88, 179-185).

There is much of interest there, especially if one considers convergent series or alternating series.

This post will be about divergent series of positive terms for which lim_{n \rightarrow \infty} a_n = 0 and a_{n+1} < a_n for all n .

The first fun result is this one: any selected x > 0 is a selective sum of such a series. The proof of this isn’t that bad. Since lim_{n \rightarrow \infty} a_n = 0 we can find a smallest n such that a_n \leq x . Clearly if a_n = x we are done: our selective sum has c_n = 1 and the rest of the c_k = 0 .

If not, set n_1 = n and note that because the series diverges, there is a largest m_1 so that \sum_{k=n_1}^{m_1} a_k \leq x . Now if \sum_{k=n_1}^{m_1} a_k = x we are done, else let \epsilon_1 = x - \sum_{k=n_1}^{m_1} a_k and note \epsilon_1 < a_{m_1+1} . Now because the a_k tend to zero, there is some first n_2 so that a_{n_2} \leq \epsilon_1 . If this is equality then the required sum is a_{n_2} + \sum_{k=n_1}^{m_1} a_k , else we can find the largest m_2 so that \sum_{k=n_1}^{m_1} a_k + \sum_{k=n_2}^{m_2} a_k \leq x

This procedure can be continued indefinitely. So if we label \sum_{k=n_j}^{m_{j}} a_k = s_j we see that s_1 + s_2 + ...s_{n} = t_{n} form an increasing, bounded sequence which converges to the least upper bound of its range, and it isn’t hard to see that the least upper bound is x because x-t_{n} =\epsilon_n < a_{m_n+1}

So now that we can obtain any positive real number as the selective sum of such a series, what can we say about the set of all selective sums for which almost all of the c_k = 0 (that is, all but a finite number of the c_k are zero).

Answer: the set of all such selective sums are dense in the real line, and this isn’t that hard to see, given our above construction. Let (a,b) be any open interval in the real line and let a < x < b . Then one can find some N such that for all n > N we have x - a_n > a . Now consider our construction and choose m large enough such that x - t_m > x - a_n > a . Then the t_m represents the finite selected sum that lies in the interval (a,b) .

We can be even more specific if we now look at a specific series, such as the harmonic series \sum_{k=1}^{\infty} \frac{1}{k} . We know that the set of finite selected sums forms a dense subset of the real line. But it turns out that the set of select sums is the rationals. I’ll give a slightly different proof than one finds in Bonar and Khoury.

First we prove that every rational in (0,1] is a finite select sum. Clearly 1 is a finite select sum. Otherwise: Given \frac{p}{q} we can find the minimum n so that \frac{1}{n} \leq \frac{p}{q} < \frac{1}{n-1} . If \frac{p}{q} = \frac{1}{n} we are done. Otherwise: the strict inequality shows that pn-p < q which means pn-q < p . Then note \frac{p}{q} - \frac{1}{n} = \frac{pn-q}{qn} and this fraction has a strictly smaller numerator than p . So we can repeat our process with this new rational number. And this process must eventually terminate because the numerators generated from this process form a strictly decreasing sequence of positive integers. The process can only terminate when the new faction has a numerator of 1. Hence the original fraction is some sum of fractions with numerator 1.

Now if the rational number r in question is greater than one, one finds n_1 so that \sum^{n_1}_{k=1} \frac{1}{k} \leq r but \sum^{n_1+1}_{k=1} \frac{1}{k} > r . Then write r-\sum^{n_1+1}_{k=1} \frac{1}{k} and note that its magnitude is less than \frac{1}{n_1+1} . We then use the procedure for numbers in (0,1) noting that our starting point excludes the previously used terms of the harmonic series.

There is more we can do, but I’ll stop here for now.

January 20, 2016

Congratulations to the Central Missouri State Mathematics Department

Filed under: advanced mathematics, editorial, number theory — Tags: — collegemathteaching @ 10:43 pm

The largest known prime has been discovered by mathematicians at Central Missouri State University.

For what it is worth, it is: 2^{74,207,281} -1 .

Now if you want to be depressed, go to the Smithsonian Facebook page and read the comment. The Dunning-Kruger effect is real. Let’s just say that in our era, our phones are smarter than our people. ๐Ÿ™‚

October 25, 2013

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 a_n = cos(\frac{n}{2}) 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 a_n = cos(n) instead.

Of course cos(x) is periodic with a fundamental region [0, 2\pi] so we will work with that region. Now we notice the following:

n (mod 2 \pi) is a group with the usual operation of addition.

By n (mod 2 \pi) , I mean the set n + k*2\pi where k \in \{..-2, -1, 0, 1, 2, 3,...\} ; one can think of the analogue of modular arithmetic, or one might see the elements of the group \{ r| r \in [0, 2 \pi), r = n - k 2\pi \} .

Of course, to get additive inverses, we need to include the negative integers, but ultimately that won’t matter. Example: 1, 2, 3, 4, 5, 6 are just equal to themselves mod 2 \pi. 7 = 7 - 2\pi (mod 2\pi), 13 = 13 - 4 \pi (mod 2\pi) , etc. So, I’ll denote the representative of n (mod 2\pi) by [n] .

Now if n \ne m then [n] \ne [m] ; for if [n]=[m] then there would be integers j, k so that n + j2\pi = m +k2\pi which would imply that |m-n| is a multiple of \pi . Therefore there are an infinite number of [n] in [0, 2\pi] which means that the set \{[n]\} has a limit point in the compact set [0, 2\pi] which means that given any positive integer m there is some interval of width \frac{2\pi}{m} that contains two distinct [i], [j] (say, j greater than i .)

This means that [j-i] \in (0, \frac{2\pi}{m}) so there is some integers k_2, k_3, so that k_2[j-i] \in (\frac{2\pi}{m}, \frac{2*2\pi}{m}), k_3[j-i] \in (\frac{2*2\pi}{m}, \frac{3*2\pi}{m})  , etc. Therefore there is some multiple of [j-i] in every interval of width \frac{2\pi}{m} . But m was an arbitrary positive integer; this means that the [n] are dense in [0,2\pi] . It follows that cos([n]) = cos(n) is dense in [-1,1] and hence a_n = cos(n) 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.).

May 16, 2013

Big Breakthrough in Number Theory: progress toward the twin primes conjecture.

Filed under: advanced mathematics, number theory — Tags: , , — collegemathteaching @ 7:26 pm

It is a long standing conjecture in number theory that there exists an infinite number of twin primes: twin primes are prime integers that differ by 2.

Example: 3 and 5, 11 and 13, 17 and 19 are examples of twin prime pairs.

Very large twin primes have been found: (2,003,663,613 \times 2^{2195,000}) - 1 and (2,003,663,613 \times 2^{2195,000}) + 1 .
But, up to now: We don’t know if this pairing “stops” at some point (is there a largest pair?)

In fact, up to recently, we had no statement of the following form: given a finite integer M there exists an infinite number or pairs of primes p, q such that p - q \le M (assuming that p is the greater of the pair).

Well, now we do. The Annals of Mathematics (the top ranked mathematics journal in the world) has accepted a paper that shows the infinite pairs statement is true, if M = 70,000,000 :

The twin prime conjecture says that there is an infinite number of such twin pairs. Some attribute the conjecture to the Greek mathematician Euclid of Alexandria, which would make it one of the oldest open problems in mathematics.

The problem has eluded all attempts to find a solution so far. A major milestone was reached in 2005 when Goldston and two colleagues showed that there is an infinite number of prime pairs that differ by no more than 16. But there was a catch. โ€œThey were assuming a conjecture that no one knows how to prove,โ€ says Dorian Goldfeld, a number theorist at Columbia University in New York.

The new result, from Yitang Zhang of the University of New Hampshire in Durham, finds that there are infinitely many pairs of primes that are less than 70 million units apart without relying on unproven conjectures. Although 70 million seems like a very large number, the existence of any finite bound, no matter how large, means that that the gaps between consecutive numbers donโ€™t keep growing forever. The jump from 2 to 70 million is nothing compared with the jump from 70 million to infinity. โ€œIf this is right, Iโ€™m absolutely astounded,โ€ says Goldfeld.

Zhang presented his research on 13 May to an audience of a few dozen at Harvard University in Cambridge, Massachusetts, and the fact that the work seems to use standard mathematical techniques led some to question whether Zhang could really have succeeded where others failed.

But a referee report from the Annals of Mathematics, to which Zhang submitted his paper, suggests he has. โ€œThe main results are of the first rank,โ€ states the report, a copy of which Zhang provided to Nature. โ€œThe author has succeeded to prove a landmark theorem in the distribution of prime numbers. โ€ฆ We are very happy to strongly recommend acceptance of the paper for publication in the Annals.โ€

Hey, 70 million is a LOT less than “infinity”. ๐Ÿ™‚

January 17, 2013

Enigma Machines: some of the elementary math

Note: this type of cipher is really an element of the group S_{26} , 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.

August 8, 2011

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: \frac{dI}{dt}=\beta S I . (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:
= R_0 = \frac{\beta S}{\nu + \delta} where \nu is the recovery rate and \delta is the death rate. Note: if R_0 < 1 then the disease will die off; if it is greater than 1 we have a pandemic. We can reduce this by reducing S (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 f(x,y) was cubic, that there is always a rational change of variable to put the curve into the following form: y^2 = x^3 + Ax + B where A, B are integers that have the following property: if p is any prime where p^4 divides A then p^6 does NOT divide B . So this curve can be denoted as E_{A,B} .

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

This is a catalog of elliptical algebraic curves of the form y^2 = x^3 + ax + b 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 x 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 (x,y) is a point on an elliptical curve, then so is (x, -y) (note: the y^2 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 P = (x_1, y_1) I will denote (x_1, -y_1) = P' .

The operation: if P, Q are rational points on the curve, construct the line l with equation y = m(x-x_1)+ y_1 Substitute this into y^2 = x^3 + Ax + B and note that we now have a cubic equation in x that has two rational solutions; hence there must be a third rational solution x_r . Associated to that x value is two y values (possibly double if the y value is zero). Call that point on the curve R then define P + Q = R' where R' is the reflection of R about the x 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 y 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: P + P = P' . Here are the situations:

Of course, \infty 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 \oplus_{i = 1}^r Z_i \oplus \frac{Z}{n_1 Z} \oplus \frac{Z}{n_2 Z}....\frac{Z}{n_k Z} 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 T be the torsion subgroup; Mazur proved that |T|\le 16 .

Let’s look at an example of a subgroup of such a curve: let the curve be given by y^2 = X^3 + 1 It is easy to see that (0,1), (0, -1), (2, 3), (2, -3), (-1, 0) are all rational points. Let’s see how these work: (-1, 0) + (-1, 0) = 0 so this point has order 2. But there is also some interesting behavior: note that \frac{d}{dx} (y^2) = \frac{d}{dx}(x^3 + 1) which implies that \frac{dy}{dx} = \frac{3x^2}{2y} So the tangent line through (0, 1) and (0, -1) are both horizontal; that means that both of these points have order 3. Note also that (2, 3) + (2,3) = (0,1) as the tangent line runs through the point (0, -1) . Similarly (2, 3) + (0, -1) = (2, -3) So, we can see that (2,3), (2, -3) have order 6, (0, 1), (0, -1) have order 3 and (-1, 0) has order 2. So there is an isomorphism \theta where \theta(2,3) = 1, \theta(2,-3) = 5, \theta(0, 1) = 2, \theta(0, -1) = 4, \theta(-1, 0) = 3 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 y^2 = x^3 + 2x + 3 is isomorphic to Z \oplus \frac{Z}{2Z} though this isn’t obvious.

The generator of the Z term is (3,6) and (-1,0) 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 y^2 = x^3 + Ax + B mod p where p is prime, we should have about p points on the curve. So we’d expect that \frac{N_p}{p} \approx 1 . If there are a lot of rational points on the curve, most of these points would correspond to mod p points. So there is a conjecture by Birch, Swinnerton-Dyer:
\prod_{p \le X} \frac{N_p}{p} \approx c (log(X))^r where r 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:
H(E_{(A,B)}) = max(4|A|^3, 27B^2) or \Delta(E_{(A,B)} -4A^3 - 27B^2

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 E/Q 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.

August 6, 2011

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, y^2 = x^3 - 3x has exactly one rational point (namely (0,0) ) but y^2 = x^3-2x 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 C^2 (where one uses complex values for both variables). The surface is a punctured multi-holed torus of genus g 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: y^2 = x^3 + Ax + B where A, B are integers.
Hence this is the form that is studied.
Sometimes the rational points can be found in the following way (example: y^2 = x^3 + 2x + 3 :
note: this curve is symmetric about the x axis.
(-1, 0) is a rational point. So is (3, 6) . This line intersects the curve in a third point; this line and the cubic form a cubic in x with two rational roots; hence the third must be rational. So we get a third rational point. Then we use (3, -6) 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 (3, 6) (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 S 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)
E(1) = 2 + 1 = 3, E(2) = 2*3 + 1 = 7, E(3) = 2*3*5 + 1 = 31, E(4) = 2*3*5*7 + 1 = 211 etc. It is unknown if there is a largest prime in the sequence E(1), E(2), E(3).....

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.

August 5, 2011

Blogging MathFest, 2011 (Lexington, KY)

Filed under: advanced mathematics, algebraic curves, conference, elementary number theory, number theory — collegemathteaching @ 1:50 am

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 f: C \rightarrow C is a function of the complex plane, one can talk about the orbit of a point z \in C, z, f(z), f(f(z)) = f^{(2)}(z), f(f(f(z))) = f^{(3)}(z)..... One can then talk about sets of points w, w\in C and sup|f^{(n)}| <  \infty 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 a, b, c such that a^2 + b^2 = c^2 . For now, we’ll limit ourselves to primitive triples; that is, we’ll assume that a, b, c have no common factor.

You might have heard that any Pythagorean triple is of the form: a = m^2 - n^2, b = 2mn, c = m^2 + n^2 for m, n integers. It is true that a, b, c 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 x^2 + y^2 = 1 . Why? Start with a^2 + b^2 = c^2 and divide both sides by c^2 to obtain ((\frac{a}{c})^2 +  (\frac{b}{c})^2 = 1 One then notes that one is now reduced to looking to rational solutions to x^2 + y^2 = 1 (a rational solution to this can be put in the ((\frac{a}{c})^2 +  (\frac{b}{c})^2 = 1 form by getting a common denominator).

We now wish to find all rational points (both coordinates rational) on the circle; clearly (-1,0) is one of them.
Easy claim: if (u, v) is such a rational point, then the line from (-1,0) to (u, v) has rational slope.
Not quite as easy claim: if a line running through (-1, 0) has rational slope s < \infty then the line intersects the circle in a rational point.
Verification: such a line has equation y = s(x+1) and intersects the circle in a point whose x value satisfies x^2 + s^2(x+1)^2-1 = 0 . This is a quadratic that has rational coefficients and root x = -1 hence the second root must also be rational. Let’s calculate the second root by doing division: \frac{(s^2 + 1)x^2 +2s^2x + s^2-1}{x+1} = (s^2+1)x + s^2 - 1 . So the point of intersection has x = \frac{1-s^2}{s^2 + 1} latex and y = s(\frac{1-s^2}{s^2 + 1} + 1) = \frac{2s}{s^2 + 1} . 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 (\frac{1-s^2}{s^2 +1}, \frac{2s}{s^2 + 1}) . Note: we obtain (-1,0) by letting s go to infinity; use L’Hopital’s rule on the first coordinate). So if we have any Pythagorean triple (a,b,c) then \frac{a}{c} = \frac{1-s^2}{s^2 + 1}, \frac{b}{c} = \frac{2s}{s^2 + 1}. But s is rational hence we write s = \frac{p}{q} where p, q are relatively prime integers. Just a bit of easy algebra reveals \frac{a}{c} = \frac{q^2 -p^2}{p^2 + q^2}, \frac{b}{c} = \frac{2pq}{p^2 + q^2} which gives us a = q^2 - p^2, b =2pq, c = q^2 + p^2 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 f(x,y) = 0 latex is any quadratic rational curve (i. e., f(x,y) = a_1 x^2 + a_2 x + a_3 + a_4 y^2 + a_5 y + a_6 xy , all coefficients rational, and (u, v) is any rational point and there is a line through (u,v) of rational slope s 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 x by substituting y = s(x - u) + v 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 (u, v) . In fact, that is the case for x^2 + y^2 = 3.

Why? Suppose there is a rational point on this curve x = \frac{p}{q}, y = \frac{a}{b} with both fractions in lowest terms. We obtain (pb)^2 + (aq)^2 = 3(qb)^2 Now let’s work Mod 4 (hint from the talk): note that in mod 4, 2^2 = 0, 3^2 = 1 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 pb, aq are both even and therefore 3(qb)^2 is divisible by 4 therefore either q is even or b is even.
Suppose b is odd. Then q is even and because pb is even, p is even. This contradicts the fact that p, q are relatively prime. If q is odd, then because aq is even, a is even. This contradicts the fact that a, b are relatively prime. So both q, b are even which means that p, a are odd. Write q = 2^I m, b = 2^J n where m, n are odd (possibly 1). Then (p^2)(2^{2J})n^2 + (a^2)(2^{2I}) m^2 = 2^{2J + 2I}3 m^2n^2 . Now if J = I we obtain (pn)^2 + (am)^2 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, J \ge I then we get (pn)^2 2^{2(J-I)} + (am)^2 = 2^{2J} 3 (mn)^2 which means that the odd number (am)^2 is the difference of two even numbers. That too is impossible.

Hence x^2 + y^2 = 3 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.

Create a free website or blog at WordPress.com.