Prime numbers

From TheTangentSpace

1 An additive characterization
2 Extending the primes
3 Consecutive Sums as sieves (linear and otherwise):
4 Sums of an even number of consecutive odd numbers
5 Formula for odd composites

An additive characterization

Let $A * A$ denote the set of all products of any two elements from $A$ ; that is, $A*A := \{a\cdot a'|a,a'\in A\}$ .

What is the set $P:=\mathbb{N}_{>1} - (\mathbb{N}_{>1}*\mathbb{N}_{>1})$ ? Clearly, this is the primes -- our definition is basically the standard one.

From this multiplicative characterization, many additive questions arise which are easy to state yet surprisingly difficult to answer. Two famous unknowns:

The Goldbach conjecture: Is $2\mathbb{N}_{>1}\subset P+P$ ?
The twin prime conjecture: Is $P\cap(P+2)$ an infinite set?

In both cases, the guess is yes.

Here is an intuitive idea about why these questions might be so challenging: we are asking additive questions about a set defined as the complement of an essentially multiplicative set - the composites. This is motivation for a simple additive characterization of the primes:

Property: Let $\mathsf{odds} := \{n | n=2k+1 \text{ for some } k\in\mathbb{N}\}$ be the positive odd integers, and, for any sequence $A=(a_i)_{i=1}^\infty$ , let $A \;+\!\!\!\!\to A$ denote the set of sums of at least two consecutive elements of $A$ ; that is, $A\;+\!\!\!\!\to A := \{\sum_{i=m}^n a_i | m < n\}$ . Then
$\mathsf{odds} - (\mathsf{odds}\;+\!\!\!\!\to\mathsf{odds}) = P \Delta \{1, 2\}$

In words: The positive odds which cannot be decomposed as a nontrivial sum of consecutive odds is exactly the set of prime numbers, with the exceptions of 1 and 2.

Proof: For any sequence $A=(a_i)_{i=1}^\infty$ , write $\sum A$ for the sequence of cumulative sums from $A$ ; that is, $\sum A := \bigg(\sum_{j=1}^i a_j\bigg)_{i=1}^\infty$ . Notice that $\sum \mathsf{odds}$ is the sequence $1, 4, 9, 16, \ldots$ of perfect squares. It's also the case that, for any sequence $A$ , we have
$A\;+\!\!\!\!\to A = \{b_i-b_j | i-j>1; b_i,b_j\in \sum A\}.$
So $a\in\mathsf{odds} \cap (\mathsf{odds}\;+\!\!\!\!\to\mathsf{odds})$ iff $a = x 2 - y 2$ with $x - y > 1$ iff $a = (x - y)(x + y)$ with both factors greater than 1. Since we're only considering odd numbers for $a$ , this means any factors of $a$ must be odd, so that we can always find a factorization of the form $(x - y)(x + y)$ whenever $a$ is composite. The conclusion is that an odd number is in $(\mathsf{odds}\;+\!\!\!\!\to\mathsf{odds})$ iff it is not prime.

This may lead you to ask the question, which I'll state as an exercise for now:

Excercise: What is the set $\mathbb{N}_{>0} - (\mathbb{N}_{>0}\;+\!\!\!\!\to\mathbb{N}_{>0})$ ?

Next we'll see a general way to analyze sets of this form, when $A$ is an infinite arithmetic progression with step size $d$ . That is, $A = \{a_0 + dn | n\in\mathbb{Z}\}$ .

Suppose $b=\sum_{i\in[m,n)}a_i$ .

If $n - m$ is odd, then $b = (m-n)a_{i_0}$ , where $i 0 = (m + n) / 2$ is the middle element.
If $n - m$ is even, then we can use the same formula by defining, for any $i=n+1/2, n\in\mathbb{Z}$ that $a i : = (a n + a n + 1) / 2$ .

This reveals that the set $\mathbb{N}_{>0}\;+\!\!\!\!\to\mathbb{N}_{>0}$ consists of positive integers which are either odd or the product of an even and an odd number. The only missing numbers are powers of 2.

In general, for arithmetic progression $A$ , define $A^*:=\{a_i | i = n + 1/2, n\in\mathbb{Z}\}$ ; and we see that $(A\;+\!\!\!\!\to A)$ consists of all even multiples from $A *$ and all nontrivial odd multiples from $A$ .

Extending the primes

The primes give a unique multiplicative decomposition for the positive integers. Can we do something similar for all positive reals? Sure. Just take logs and build a Hamel basis. I have not yet written up these ideas carefully in the wiki, but there is a more detailed explanation of this idea in this blog post.

Consecutive Sums as sieves (linear and otherwise):

From "an odd number is composite iff can be expressed as the sum of an odd number of consecutive odd numbers" (Tyler's Prime number Theorem?) which follows from above work, you can arrange such sums in a table to reveal interesting pattern.

Write down in the 1st column all 3-sums of consecutive odd numbers, in the 2nd column all 5-sums and so on.

       1+3+5=9      1+3+5+7+9=25     1+3+5+7+9+11+13=49  .....etc
       3+5+7=15     3+5+7+9+11=35    3+5+...+15=63       .....etc
       5+7+9=21     5+...+13=45      5+...+17=77
       21           55               91
       27           65               105
       33           ....etc
       ...etc

Notice:

The 1st row = all odd squares = {(2j+1)^2}  j=1,2,3,...
The 1st column = {3(2i+1)}  i=1,2,3,...
The 2nd column = {5(2i+3)}
The 3rd column = {7(2i+5)}  ...  and so on.

Thus the odd composites = {3(2i+1)} U {5(2i+3)} U {7(2i+5)} U ....etc = a union of linear sieves

Now, notice the rows.

They can be expressed as quadratic expressions, giving a quadratic sieve.

1st row = {9+16i+4i(i-1)}
2nd row = {15+20i+4i(i-1)}
3rd row = {21+24i+4i(i-1)}
....
jth row = {(3+6j)+(12+4j)i+4i(i-1)}

Take the union of these and you have a quadratic sieve.

Another: from each of the 1st row entires go diagonally down and to the left. The result is a "finite" backward sieve.

odd composites = {3^2} U {5^2,5^2-2(5)} U {7^2,7^2-2(7),7^2-2(7+7)} U {9^2,9^2-2(9),9^2-2(9+9),9^2-2(9+9+9)} U ...etc

There are other types of sieves (play around with table!)

Sums of an even number of consecutive odd numbers

It is realtively easy to show that:

Sums of an even number of 4 or more consecutive odd QUARTERS = odd and even composites

eg: 5/4+7/4+...+15/4 = 15 etc

Formula for odd composites

From the quadratic sieve above, you can construct formulas f(n) and g(n) (and probably more) that generate all odd composites, albeit not in order (drats!). All you need is a way to count each entry (row=i,column=j). One way is along diagonals (a bit like Cantor's diagonalization process) from bottom left to top right. That is, from (1,1) to (1,2) to (2,1) to (3,1) ... and so on.

Doing this, (I'll spare you the details which involve triangular numbers) gives:

f(n) = (2m+3)[m^2+3m+3-2n] where m=int((sqr(8n+1)-1)/2) for n=0,1,2,...

and (going in the opposite direction):

g(n) = (2m+3)[2n-m+3-m^2] with m as above.

The first formula gives f(0)=9, f(1)=25, f(2)=15, f(3)=49, f(4)=35, ...etc

The second is slightly more ordered: g(n)=9,15,25,21,35,49,27,...

Questions:

1. Is it possible to find an analytic solution for f or g and thus a (fast?) primality test?

2. Can you solve suitably configured f or g using (say) Newton's method or like?

3. Is there a "simple" ORDERED formula for composites (or a proof such doesn't exist)? That is, f(0)= 1st composite, f(1)= 2nd composite and so on.

4. Is there a "simple' formula for primes? (There's a 24-variable polynomial expression found in 1977 by Jones, Wada et al that follows from Hilbert's 10th problem).

You can genralise much of the above for tables with sums of terms from an arithmetic progression.

But what about terms other than arithmetic? Are there interesting patterns waiting to be found for such? (Sums of consecutive Fibonacci numbers produce interesting results).

Overall, nice work Tyler for finding (refinding?) such a wonderful pattern to play with!

(added by D Williams)

Retrieved from "http://thetangentspace.com/wiki/Prime_numbers"

Prime numbers

From TheTangentSpace

Contents

An additive characterization

Extending the primes

Consecutive Sums as sieves (linear and otherwise):

Sums of an even number of consecutive odd numbers

Formula for odd composites

Views

Personal tools

Navigation

Search

Toolbox