Fork me on GitHub
Math for the people, by the people.

User login

Birkhoff Recurrence Theorem

Keywords: 
Recurrence; Dynamical Systems
Major Section: 
Reference
Type of Math Object: 
Theorem

Comments

Thus we have a case of indirect primality testing: whenever a given n is generated by an arithmetic progression like 1+3k,2+7k,3+13k,4+7k….. f(n) is composite. Otherwise f(n) is prime. Note it is indirect primality testing since we are not testing f(n) for primality; we are only testing whether a given n is generated by the relevant failure function (arithmetic progression). If it is not f(n) is prime.

Any doubt so far pl?

Dear Jussi, would you like me to continue?

Yes. First the proposition!

Thank you, Jussi. Proposition: There are infinitely many prime numbers with shape n^2+n+1.

Let me summarise up to the point I had already contributed: let f(n) = n^2 + n + 1 ( n belongs to N). Let n_0 be a specific value of n. Then n = n_0 + kf(n_0) generates values of n such that f(n) is composite. Note: please ignore trivial cases like k = 0. This is easily proved. All other values of n are such that f(n) is prime. (to be continued).

I forgot to mention that k belongs to Z. Now I will take a break for two days to enable you to find a counter-example. (to be continued)

Let me be very clear as to what counter example you should try to find; I will do this by taking a specific interval - n = 5 to 36.This interval is spaned by the failure functions( arithmetic progressions ) 1+3k, 2+7k, 3 +13k, 4 +7k and 5+31k, 7+19k and 9+13k. However the values of n skiped by the above are 5,6, 8, 12, 14, 15, 17, 20, 21, 24,27 and 33. Now all these skiped values of n are such that f(n) is prime. So you have to find a value of n skiped by the relevant failure functions such that f(n) is composite. Such a counter example may be very difficult to find.

This means we have a case of indirect primality testing: f(n) is composite if n = n_0 +kf(n_0). Otherwise f(n) is prime. Note we are not testing f(n) directly for primality; we are only testing whether is n is generated by n_0+kf(n_0); if so f(n) is composite-if not f(n) is prime. (to be continued)

Before proceeding let me emphasise that the values of n skiped by the failure functions i.e. n_0+kf(n_0) are such that f(n) are prime and they need not be tested for primality. We now set up an iteration as follows: Let p_0 be the largest known prime having shape n^2+n+1. Let n_0 be the corresponding value of n i.e. n_0^2+n_0+1 = p_0. Consider the interval n_0, n_0+p_0. I am considering this interval because f(n_0+kf(n_0)) is congruent to 0 (mod f(n_0)). Note the fraction of this interval not covered by the failure functions( arithmetic progressions) 1+3k, 2+7k, 3+13k 4+7k………… . Let n_1 be the largest of these values of n not covered by any failure function. f(n_1) is prime which need not be tested for primality. Let this prime be p_1. 2nd iteration: consider the interval n_1, n_1 +p_1. proceed as in the 1st iteration i.e. mark the fraction of values of n in this interval not covered by any failure function. Let n_2 be the largest value of n in this interval not covered by any failure function. f(n_2) is prime; call this p_2. Consider the interval n_2, n_2 + p_2. Mark the fraction of values of n in this interval not covered by any failure function. The fraction of values of n not covered by any failure function in any interval decreases asymptotically from iteration to iteration to a rational number- call this beta (to be continued ).

Since the fraction of values of n in any interval which are not covered by any failure function decreases asymptotically to beta the iteration is perpetual. This is because the fraction of primes in any interval never reaches zero - hence there are infinitely many primes of shape n^2+n+1 (proved- subject to confirmation by a programmer.) (to be continued).

Note a) p_0 less than p_1 less than p_2 less than p_i b) This means the intervals become succeedingly bigger c)As the fraction of primes in each interval becomes suceedingly smaller it may appear that the number of primes i.e. the number of ns not overed by any failure function becomes smaller- actually it may turn out that the number of primes become bigger since the intervals become bigger d) there is no need to test any f(n) where n is skiped by the failure functions for primality - they are automatically prime e) my conjecture is that the value of beta is 0.03 - even if beta is 0.01 it makes no difference since the perpetuality of the iteration is established f) only a competent programmer can program the failure functions and the iteration g)to go from iteration i to iteration i+1 we need only one value of n not covered by any falure function h) the iteration can come to an end only if all the values of n in an interval are covered by one or more of the failure functions ( this is highly improbable ) (to be continued)

I would like to conclude my message with one point: The fact that any value of n skiped is such that f(n) is prime can be proved: f(n)=n^2+n+1 is such that whenever f(n) is composite one of its factors is smaller than n. This implies that it that the relevant n has to satisfy a prior failure function. Any question, Jussi?

No questions.

Happy to inform members that Carl Pomerance has given qualified support to my concept of indirect primality testing.

Pl write an article on simple groups.

Indirect primality testing is not only possible when f(n) = n^2 +n +1 but also in the cases of several quadratic polynomials in which the constant term is not large. Further research needs to be done to establish the relative efficiency of indirect vs direct primality testing.

Subscribe to Comments for "Birkhoff Recurrence Theorem"