Why finding big prime numbers? why study weird arithmetic sequences?

Now I am sitting on my desk thinking on a technique to help me to identify BIG prime numbers in certain arithmetic sequences using algebraic geometry.

This was part of my last project for my PhD, which I think it was very interesting. When I say "BIG" I mean thousands of digits, maybe millions.  When I say "primes in arithmetic sequences" I mean to separate prime numbers in a list like $latex \{ \alpha_n \}_{n=0}^\infty$.

A popular, a prostituted, an important and a "dumb" sequence.

Now we will describe some non trivial sequences and we will see a glimpse of why they are important (or not).

This is of course in my opinion, since there are infinitely many sequences which I ignore and could be more interesting. In fact there is a sequence of "uninteresting numbers" which contains all numbers which appear to not have known/interesting properties (like being prime, Mersenne prime, triangular number, cube, etc...).
But well, this sequence then..., is interesting as is unique, and then we get a paradox.

The popular sequence

The popular is a very famous arithmetic sequence, and is the "Mersenne Sequence", $latex \{ 2^n-1\}_{n=1}^\infty\subset\mathbb{N}$.

$latex \{ 2,7,15,31,63,127,255,...\}$

This is the sequence of all Mersenne numbers.  We denote by $latex M_n$ to the number $latex 2^n-1$.
To identify the primes in this sequence, note that if $latex n=2k$ (is even) then $latex 2^n-1=(2^k-1)(2^k+1)$ and hence... not a prime number. This means that in the sequence we can discard all the values $latex n\in 2\mathbb{Z}$, that is $latex M_{2k}$ is not prime. A less trivial fact is that if $latex n$ is composite, namely $latex n=ab$ then we have that:

 $latex 2^n-1=2^{ab}-1=(2^a-1)(\sum_{k=0}^{b-1}2^{ka})=(2^b-1)(\sum_{k=0}^{a-1}2^{kb})$

and then also $latex M_{pq}$ is not prime. So, we are left with all the elements in the sequence of the form $latex M_p$ for $latex p$ a prime number. A quick inspection says that $latex M_2, M_3, M_5, M_7$ are Mersenne primes. But $latex M_{11} = 2047 =23\cdot 89$ which is not prime. So, which Mersenne numbers are prime ?

This is a difficult question, there are big computer grids working in this, trying to find the most spectacular prime. The biggest Mersenne prime known, (and Biggest Prime in general) is $latex 2^{74207281}-1$. which has 22.3 million digits approximately. The way to check it without putting so much effort in the algebraic geometric or number theory rigor is the following:

 To check that $latex 2^p -1$ is prime:

Consider the sequence $latex \{ \sigma_1=4, \sigma_2=14,...,\sigma_j=(\sigma_{j-1}^2)-2...\}$
then $latex M_p=2^p-1$ is prime if and only if $latex \sigma_{p-1}\equiv 0 \bmod M_p$.

This is the fastest way known today. is called the Lucas-Lehmer test.
There are other elegant tests (but not necessarily faster) using elliptic curves which I knew its existence when I was talking with Benedict Gross at the conference on L-Functions at Harvard the past year, and in some sense I have to do something similar as part of my PhD program.

The prostituted

Another famous and prostituted sequence is the so called "Fibonacci sequence".

$latex \{ 1,1,2,3,5,8,13,...,F_{n-1}+F_{n-2}, ...\} $

This is famous and is always presented as the building blocks of beauty in the universe. This just an exaggeration, but well, that is another story.

Is known that $latex \lim_{n\to\infty} \frac{F_{n}}{F_{n-1}}=\phi=1.618033...$.

This number $latex \phi$ has the property that squared is equal to $latex \phi+1$ so, is appears as a root of the polynomial $latex x^2 -x -1=0$.
The value of $latex \phi$ can be found when you divide lengths of middle lines in some polygons by the length of the sides. Also in your body, if you divide your height by the distance of your feet to your belly button, and in a lot of parts of our body. This number can be analyzed in a Leonardo da Vinci drawing called "Le proporzioni del corpo umano secondo Vitruvio" which can be seen here.
This is why $latex \phi$ has some kind of mystic and esoteric significance for some people, and that is why is called sometimes The Golden Ratio. 

To identify primes in the Fibonacci sequence, there are no good ways. This is mainly because the sequence highly depends on the "addition" operation and not "multiplication", and believe it or not, addition in number theory is a mystery.
A very important Conjecture in mathematics about this mystery, predicts the possible relation between the multiplication and the addition of integers, through its prime factorization, called the abc conjecture, so Fibonacci, is difficult as a problem in terms of primality, but as seen, has more significance in geometry.

The important sequence

Now for the important sequence is this

$latex \{2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344...\}$

Do you see it?

Well, is not too easy to see, is called the "Hardy-Ramanujan sequence", if you denote by $latex \tau(n)$ the $latex n^{th}$ element of the sequence, it means that $latex \tau(n)$ can be written in $latex n$ different ways as a sum of two cubes. Fermat Proved that there are infinitely many of these numbers hundreds of years before, but they caught the attention of Hardy by Ramanujan in a very nice story.

When Ramanujan was dying at the hospital in England, Hardy went to visit him. Hardy told him that the number in his taxi to the hospital was a dull, boring number, 1729. Ramanujan said:

 'No, Hardy, it is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways' 

That is why we use the letter $latex \tau$ because these numbers are called "taxicab numbers" because of this story.

The importance of these numbers, is the new theory in arithmetic geometry that arose,  which in fact I am very interested personally, and professionally.

Practically Ramanujan discovered in his way of thinking, an integral solution to the equation $latex x^3+y^3=z^3+w^3$ which nowadays is studied over $latex \mathbb{Q}$ and then twisted.

This kind of surfaces are called K3 Surfaces (Kodaira-Kummer-Kahler, smooth minimal complete surface with trivial canonical bundle), there is no smart way of obtaining these numbers other than using this algebraic geometry in these surfaces. An example of these surfaces with a family of rational curves parametrized  (the curves may contain taxicab solutions in it) is:

  

And yeah 1729 has the desired property, that is, $latex \tau(2)$ is a sum of two cubes in only two different ways. 

Srnivasa Ramanujan was a human computer, in fact to verify this, we check for the $latex \tau(2)=1729$ and $latex \tau(6)=24153319581254312065344$ can be written as the sum of 2 cubes in 2 and 6 different ways respectively:

$latex \begin{matrix}\tau(2)&=&1729&=&1^3 + 12^3 \\&&&=&9^3 + 10^3\end{matrix}$

...
$latex \begin{matrix}\tau(6)&=&24153319581254312065344&=&582162^3 + 28906206^3 \\&&&=&3064173^3 + 28894803^3 \\&&&=&8519281^3 + 28657487^3 \\&&&=&16218068^3 + 27093208^3 \\&&&=&17492496^3 + 26590452^3 \\&&&=&18289922^3 + 26224366^3\end{matrix}$

The "dumb" sequence

There are plenty other sequences, for example, there are some "dumb" sequences that at the end... they are not so dumb, for example, consider the following sequence:

$latex \{1, 11, 21, 1211, 111221, 312211, 13112221, ... \}$

Do you see the pattern?

Well, the pattern is visual, you begin with "1" and then the following will be the "description of the previous", that is, you ask yourself "What symbols are in the preceding element of the sequence?", and you say "one one" (11) then the next is "two ones"  (21), and so on... This sequence is called "look and say sequence".

There are a lot of things you can do in your spare time with this sequence, for example, prove that a "4" cannot appear in any element of the sequence. The number 13112221 is in fact the biggest prime known in this sequence, are there others?

This apparently dumb sequence has an amazing property which transforms it from dumb to analytic and it was due to John Conway.
Consider the $latex k^{th}$ element of that sequence, call it $latex a_k$  , and define $latex \ell(a_k)=$number of digits of $latex a_k$.
Is proved that $latex \lim_{n\to\infty} \frac{\ell(a_k)}{\ell(a_{k-1})}=\lambda=1.303577269034...$. The surprising thing is that $latex \lambda$ is an algebraic number that can be found as a root of a polynomial of degree 71. This was proved by John Conway, for more information, look at wikipedia.


But why?, why you want to find big primes or classify properties of sequences?


 I have been questioned plenty of times "Why you want to find big primes?", today was one of these days where a master student asked me.
There is a FALSE answer which is very popular among a lot of people, namely

 "It has cryptographic applications, since prime numbers are the basis for today's e-commerce and the development of cryptographic schemes" 

This is false, since cryptographic schemes for public key cryptography need prime numbers with no more than 1000 decimal digits (and this is already too long). Using more than 1000 digits maybe would be more secure, but the speed will decrease exponentially, that is why you don't use 1 million bits of security.

 Identifying these "cryptographic" prime numbers at random with certain properties (Like being a Sophie-Germain prime) to generate a public key with 4096 bits which has approx 1234 digits, (which is already paranoid for the public techniques of cryptanalysis) takes less than a second in my workstation (try: time openssl genrsa 4096).
 So, cryptography is not a good excuse to generate BIG prime numbers, when I say big, I mean thousands of digits, millions.


The answer in my case is easy... To collect them...  they are difficult to find, but they are present in a lot of shapes, for example in the last sequence, which elements are prime ? which is the biggest known ? how to identify them with geometric techniques?.

That is how the theory in mathematics is born, with a question regarding classification.

So, finding big primes is difficult, so is valuable, there are only 49 Mersenne Primes and nobody has proved that they are infinite. (but is believed heuristically that they are).

A couple of years ago I wrote here about finding a big prime of the form $latex 3\cdot 8^n -1$ , which I found here, there are a lot of possible primes disguised in infinitely many shapes, you could just define whatever recursive relation and analyze it.

Other people could say to test a big cluster, or to get some money (yes you get money if you break the records). Maybe an analytic number theorist could say To understand more the distribution of prime numbers which is unknown.

Conclusion

So well in conclusion, I think is good to collect primes and analyze sequences. This to find something hidden in the unknown nature of the logic of sequences of natural numbers, since, we don't know yet how the prime numbers arise. There is still a mystery of how the prime numbers are distributed among all the natural numbers,  even with quantum computers is hard to find them arbitrarily large, so there are still work to do in mathematics.

For more information of all the known published sequences (yes, whatever you think will be there) go to www.oeis.org, this is the Online Encyclopedia of Integer Sequences.


Eduardo Ruíz Duarte (beck)
twitter: @toorandom