An inequality involving phi() and pi()

[Playdo]

Is this inequality true ever and when?

[tex]1/2 \phi{(p_{n}^{\sharp})} < \pi{(p_{n}^{\sharp})}-n[/tex]

 

[CRGreathouse]

n = 13 was the first example I noticed. What significance does this have?

 

[Playdo]

n = 13 was the first example I noticed. What significance does this have?

You mean counterexample? The inequality proves the Goldbach Conjecture using a pidgeon hole argument for any [itex]p_{n}^\sharp[/itex] for which it is true.

If it is not true generally above some finite n then Goldbach being true is quite amazing.

Just write out the reduced residue system as sums that add to [itex]p_{n}^\sharp[/itex].

The density of primes is getting less as n gets larger so the probability of Goldbach being true on the sequence [itex]p^\sharp[/itex] becomes small rather quickly.

I do not have Mathematica on my computer so I can't quickly do what I suspect you did which is just evaluate the inequality using functions in Mathematica or Maple.

 

[Playdo]

The next thing to do is fill in this table using the follwing inequality

[tex]1/2 \phi{(p_{n}^{\sharp})} < \pi{(p_{n}^{\sharp})}-n+k[/tex]

You already did k=0

Fill in the table

Least n for which the inequality is false | k

13 | 0

? | 1

.
.
.

as high as your PC will take you. You should use the exact value of pi(x) and not any of the approximations if possible. If you have to use an approximation use the PNT since this a lower bound for the others like Li(x) and Re(x).

Thanks for getting involved.

 

[CRGreathouse]

I don't know that 13 is the least one. I'm not even sure I properly understood the expression -- your ^\sharp is primorial, maybe? Why don't you give some examples of calculations.

 

[Playdo]

I don't know that 13 is the least one. I'm not even sure I properly understood the expression -- your ^\sharp is primorial, maybe? Why don't you give some examples of calculations.

Yes it is primorial. Hmm that is a new term. It's good to see that sequence getting special recognition it is very important.

Yes, so if you have Maple or mathematica just calculate that inequality for each sequential k and value of n until it fails. The pi is primes less than the primorial and the phi is eulers totient.

If you don't mind posting that info in a table here. I would really appreciate it.

The equation is simple to understand, all of the primes less than the primorial that are also in the reduced residue system modulo the primorial are accounted for on the right. The size of the reduced residue system is accounted for on the left. All true Goldbach Statements x+y = p#[n] must come from the reduced residue system. Thus if there are more than half as many primes as elements in the reduced residue system Golbach is true for that primorial by the pigeon-hole principle. The k comes in as a way to see how quickly the size of the residue system is decaying with respect to the number of primes in it.

Actually analytically the change between n can be calculated

[itex] 1/2 \phi {(p^{\sharp}_{n+1})} - 1/2 \phi {(p^{\sharp}_n)}= 1/2 \phi{(p^{\sharp}#_{n})}{(p_{n+1}-2)}[/itex]

[itex]\pi{(p^{\sharp}_{n+1})}-n+1-\pi{(p^{\sharp}_{n})} - n =\pi{(p^{\sharp}_{n+1})}-\pi{(p^{\sharp}_n)} +1[/itex]

The ratio is

[itex]\frac{{1/2\phi{(p^{\sharp}_n)}}{(p_{n+1}-2)}}} {{\pi{(p^{\sharp}_{n+1})}-\pi{(p^{\sharp}_n)} +1}[/itex]

So the limit as we go to infinity should be? It is best to sub in for pi one of the approximations, perhaps the PNT, which is a lower bound for pi(x) but maybe Re(x) is better, more accuracy.

 

[Playdo]

Yes it is primorial. Hmm that is a new term. It's good to see that sequence getting special recognition it is very important.

Yes, so if you have Maple or mathematica just calculate that inequality for each sequential k and value of n until it fails. The pi is primes less than the primorial and the phi is eulers totient.

If you don't mind posting that info in a table here. I would really appreciate it.

The equation is simple to understand, all of the primes less than the primorial that are also in the reduced residue system modulo the primorial are accounted for on the right. The size of the reduced residue system is accounted for on the left. All true Goldbach Statements x+y = p#[n] must come from the reduced residue system. Thus if there are more than half as many primes as elements in the reduced residue system Golbach is true for that primorial by the pigeon-hole principle. The k comes in as a way to see how quickly the size of the residue system is decaying with respect to the number of primes in it.

Actually analytically the change between n can be calculated and the limit evaluated.

[itex] 1/2 \phi {(p^{\sharp}_{n+1})} - 1/2 \phi {(p^{\sharp}_n)}= 1/2 \phi{(p^{\sharp}#_{n})}{(p_{n+1}-2)}[/itex]

[itex]\pi{(p^{\sharp}_{n+1})}-n+1-\pi{(p^{\sharp}_{n})} - n =\pi{(p^{\sharp}_{n+1})}-\pi{(p^{\sharp}_n)} +1[/itex]

Is that clearing things up.

 

[CRGreathouse]

I do not have Mathematica on my computer so I can't quickly do what I suspect you did which is just evaluate the inequality using functions in Mathematica or Maple.

I have neither Mathematica nor Maple on my computer.

 

[Playdo]

I have neither Mathematica nor Maple on my computer.

Ok I'll do the analysis and post it here eventually. I'll fill in the table too.

 

[shmoe]

The next thing to do is fill in this table using the follwing inequality

[tex]1/2 \phi{(p_{n}^{\sharp})} < \pi{(p_{n}^{\sharp})}-n+k[/tex]

You already did k=0

Fill in the table

Least n for which the inequality is false | k

I'm sure I explained this to you in that other thread. pi(p#)/phi(p#)->0 as p->infinity, so that inequality will only be true for a finite number of n for any given fixed k.

edit- sorry, I removed a confusing and uneccessary pre-coffee bit and realize I should have quoted your bit in post #3 "If it is not true generally above some finite n then Goldbach being true is quite amazing."

 

[Playdo]

I'm sure I explained this to you in that other thread. pi(p#)/phi(p#)->0 as p->infinity, so that inequality will only be true for a finite number of n for any given fixed k.

edit- sorry, I removed a confusing and uneccessary pre-coffee bit and realize I should have quoted your bit in post #3 "If it is not true generally above some finite n then Goldbach being true is quite amazing."

Thanks,

Yeah, so right within the context of the reduced residue system for the pirmorials (when did we start using that name?) the primes are getting more and more sparse as n goes to infinity. The thing there I guess I have not been able to put into words more precise that "wow" is that Goldbach being true for the primorials would mean that each new prime is less and less and less free to simply be any number.

Look in base 30 we are pairing

1:29, 7:23, 11:19, 13:17

base 210

We are pairing

1:209, 11:199, 13:197,...

For very large primorials the primes are getting less dense (I know the term is not being used properly, but if you can suggest one please do) as we get closer to the base. We know the law that governs that, what if we wrote it out as an upper register and a lower register

base 30

1 7 11 13
29 23 19 17
30 30 30 30

We can write that into a more general looking table. But now for very large primorials the number of primes between anytwo numbers near to 1/2 the primorial will be very small and somehow, Goldbach being true says they have to fill up these registers so that at least one prime pair exists summing to the primorial. So if the bins are filled up sequentially left to right across the top and then right to left across the bottom, a probability argument would suggest that we are more likely to find primes around the primorial itself and that there is a sort of self similar thing going on. There could be little surges in the number of primes in intervals near to the primorials.

Is it totally unreasonable to think that some self-similarity would exist in the distribution of primes? Each new prime eliminates infinitely many natural numbers from being prime.

On the analog side of messing with this, why could we not set up sound or light waves to interact in such a way as to reveal primes? I wonder if an optical devise could factor numbers faster than a computer.

Suppose I wanted to factor N, If I can generate a population of photons with mean frequency NkHz and intersect that beam with a variable wavelength beam in such a way that interference causes a signal to be created. Could we then find the "spectrum" of N at the speed of light?

I'm glad to see you Schmoe. I like this Goldbach construct using the primorials because it shows that Goldbach is intimately related to the distribution of primes. A fact I am sure you are aware of.

I am going to start that thread on factoring using a different perspective this time. I hope you'll take a little time there too.

Cheers.

 

[Playdo]

I'm sure I explained this to you in that other thread. pi(p#)/phi(p#)->0 as p->infinity, so that inequality will only be true for a finite number of n for any given fixed k.

edit- sorry, I removed a confusing and uneccessary pre-coffee bit and realize I should have quoted your bit in post #3 "If it is not true generally above some finite n then Goldbach being true is quite amazing."

Yes, but then I tried to do a formal proof of it and thought I had worked it out. I forgot how you actually calculated that. Did you prove this?

[tex]0=\lim_{n\rightarrow\infty}\frac{{\frac{p_n^{\sharp}}{ln(p_n^{\sharp})}}}{\prod_{i=1}^n{(p_i^{\sharp}-1)}}>\lim_{n\rightarrow\infty}\frac{\pi{(p_n^{\sharp})}}{\phi{(p_n^{\sharp})}}[/tex]

Because that one does not work whenever PNT is an underestimate of Pi(x). I'm just wondering how you actually calculated that ratio.

 

[shmoe]

Yeah, so right within the context of the reduced residue system for the pirmorials (when did we start using that name?)

I've seen the name 'primorial' credited to H. Dubner, sometime in the 80's I guess. It's a combination between prime and factorial. I mentioned this term in that other thread.

The thing there I guess I have not been able to put into words more precise that "wow" is that Goldbach being true for the primorials would mean that each new prime is less and less and less free to simply be any number.

Goldbach being true wouldn't say the primes are less random. A more precise version of Goldbach's conjecture gives an asymptotic for the number of prime pairs that sum to a given number (due to Hardy and Littlewood). This is essentially based on treating the primes as a random sequence with density 1/log(n) as the prime number theorem suggests (and a few adjustments afterwards).

see the end of http://mathworld.wolfram.com/GoldbachConjecture.html for this asymptotic.

For very large primorials the primes are getting less dense (I know the term is not being used properly, but if you can suggest one please do) as we get closer to the base.

Less dense is fine, the limit I gave you is an asymptotic density.

We can write that into a more general looking table. But now for very large primorials the number of primes between anytwo numbers near to 1/2 the primorial will be very small and somehow, Goldbach being true says they have to fill up these registers so that at least one prime pair exists summing to the primorial. So if the bins are filled up sequentially left to right across the top and then right to left across the bottom, a probability argument would suggest that we are more likely to find primes around the primorial itself and that there is a sort of self similar thing going on.

I don't see what probability argument you are suggesting here, Goldbach being true doesn't mean you'd somehow need more primes near the primorial.

Look at the asymptotic for the number of solutions, and you should take the time to test how good this asymptotic is with some large numbers. I have a feeling you are going to be suprised on just how many prime pairs will add up to a given number.

[tex]0=\lim_{n\rightarrow\infty}\frac{{\frac{p_n^{\sharp}}{ln(p_n^{\sharp})}}}{\prod_{i=1}^n{(p_i^{\sharp}-1)}}>\lim_{n\rightarrow\infty}\frac{\pi{(p_n^{\sharp})}}{\phi{(p_n^{\sharp})}}[/tex]

You don't need any inequality like that (the denominator of the limit on the left isn't quite phi(p#) by the way, you shouldn't have the sharps "#" there). Just use pi(n)~n/log(n), log(p#)~p, and [tex]\prod_{p\leq x}(1-1/p)\sim e^{-\gamma}/\log{x}[/tex].

 

[Playdo]

I've seen the name 'primorial' credited to H. Dubner, sometime in the 80's I guess. It's a combination between prime and factorial. I mentioned this term in that other thread.



Goldbach being true wouldn't say the primes are less random. A more precise version of Goldbach's conjecture gives an asymptotic for the number of prime pairs that sum to a given number (due to Hardy and Littlewood). This is essentially based on treating the primes as a random sequence with density 1/log(n) as the prime number theorem suggests (and a few adjustments afterwards).

see the end of http://mathworld.wolfram.com/GoldbachConjecture.html for this asymptotic.



Less dense is fine, the limit I gave you is an asymptotic density.



I don't see what probability argument you are suggesting here, Goldbach being true doesn't mean you'd somehow need more primes near the primorial.

Look at the asymptotic for the number of solutions, and you should take the time to test how good this asymptotic is with some large numbers. I have a feeling you are going to be suprised on just how many prime pairs will add up to a given number.



You don't need any inequality like that (the denominator of the limit on the left isn't quite phi(p#) by the way, you shouldn't have the sharps "#" there). Just use pi(n)~n/log(n), log(p#)~p, and [tex]\prod_{p\leq x}(1-1/p)\sim e^{-\gamma}/\log{x}[/tex].

Ok, I'll check out the link. I would not be too surprised if there were many prime pairs adding to most even numbers. Trying to determine which number might have fewer such pairs would be one way of possibly discovering a class of numbers that had none. But on your asymptotics. Maybe I am just not getting what tilda does for us, but is it not true that a tilda tells us nothing about how often such functions might be different? For instance phi(p#) is locally small, and if p# is between a prime pair it will be much smaller than the totient of both of those. That pi(x) is asymptotic to something does not reveal the details. How do we know that there is not a subset of natural numbers for which pi(x) is always greater than x/logx? or less than it? Primes are what is left out by the map {2,3,4,...} times {2,3,4,...}. No primes appear.

It has to be true that the local density of primes is getting smaller because the local density of composites is clearly rising. That fact is clear when one considers the primorials and their reduced residue systems. Since local density of primes is decreasing the primes are becoming relative more sparse for larger and larger primorials. So that leaves me with what type of function as a guess for pi(x)? It must be one in which the first derivative is decreasing, but the first derivative can never reach zero because Euclid showed there are infinitely many primes.

It is an important point what you are saying. Let me go off and brush up on these asymptotic issues and then I will come back and either approve or give a good argument against your approach in solving (or avoiding the solution of) that inequality.

Cheers,

P

Note: pi(x) ~ x/logx the notation appears to be inconflict with this definition http://mathworld.wolfram.com/AsymptoticSeries.html ? My quandry here is how can we have a continuous function of class C-infinity that is asymptotic as a series to a discrete function. Fourier Series maybe. So the tilda must mean the old standard asymptotic in that limit as x goes to infinity of pi(x)-x/logx goes to zero. But there must be infinitely many such functions. In fact Li(x) is considered by many a better approximation along the way. I just don't see how tilda impacts the details of the distribution?

Yeah here we go http://mathworld.wolfram.com/AsymptoticNotation.html, it is just as I thought. That is not a very strong or exclusive result about the distribution of primes. Much lauded the PNT, but not the end of research on the matter.

 

[shmoe]

Ok, I'll check out the link. I would not be too surprised if there were many prime pairs adding to most even numbers. Trying to determine which number might have fewer such pairs would be one way of possibly discovering a class of numbers that had none.

That's included in the conjecture, the number of prime pairs summing to n depends on the size of n and it's prime divisors.

But on your asymptotics. Maybe I am just not getting what tilda does for us, but is it not true that a tilda tells us nothing about how often such functions might be different? For instance phi(p#) is locally small, and if p# is between a prime pair it will be much smaller than the totient of both of those. That pi(x) is asymptotic to something does not reveal the details.

The asymptotic gives enough to handle that limit, you don't need to know anything strong at all about error terms.

How do we know that there is not a subset of natural numbers for which pi(x) is always greater than x/logx? or less than it?

I've never really thought about the sign of pi(x)-x/log(x), I'd expect it's always positive since x/log(x) underestimates li(x) by a fair bit (there may be a few small values of x where pi(x)<x/log(x), I can't recall). pi(x)-li(x) changes sign infinitely often though.

It doesn't matter for the limit though.

So that leaves me with what type of function as a guess for pi(x)? It must be one in which the first derivative is decreasing, but the first derivative can never reach zero because Euclid showed there are infinitely many primes.

Well, the prime number theorem gives a good 'guess' for a smooth function to approximate pi(x) by, li(x) whose derivative is 1/log(x).

It is an important point what you are saying. Let me go off and brush up on these asymptotic issues and then I will come back and either approve or give a good argument against your approach in solving (or avoiding the solution of) that inequality.

It's all in the asymptotics I supplied. [tex]\frac{\pi(p\#)}{\phi(p\#)}\sim\frac{p\#/\log{p\#}}{p\#/(e^\gamma \log{p})}=\frac{e^\gamma\log{p}}{\log{p\#}}\sim\frac{e^\gamma\log{p}}{p}[/tex]

this tends to 0 as p->infinity.

Yeah here we go http://mathworld.wolfram.com/AsymptoticNotation.html, it is just as I thought. That is not a very strong or exclusive result about the distribution of primes.

Not very strong? I'd like to chalk that up to lack of experience, but you have an example of the utility of the pnt staring right at you in this thread. It easily handles the question of the asymptotic density of primes in the rrs of the primorials. I'm baffled that you could see how it handles this problem and call it "not very strong".

Much lauded the PNT, but not the end of research on the matter.

No kidding research didn't stop after the pnt. Of course we're always striving for better. Of course there are many problems that the pnt doesn't answer, even under the error terms the riemann hypothesis would give. It's still the first tool you use for any prime distribution question, and it works so darn well in so many applications.

 

[Playdo]

Thanks Schmoe. I'm not asking a question about the asymptotic density of primes in the reduced residue system of the primorials. So ultimately we have the ratio going to zero, meaning the pidgeon-hole argument does not work for Goldbach on the primorials forever (in fact barely at all if we think of an infinity), we agree on that.

I'm interested in the exact number of primes in the reduced residue system modulo the primorials. That is not answered using the PNT. Are we agreed on that? You cannot use asymptotics to tell me how many primes are in r.r.s. p#[n]. The why I want to know part makes no difference. You told me the density goes to zero, I concur.

You do acknowledge that asymptotic arguments do not reveal the precise number of primes in any of those reduced residues systems under consideration, yes? Therefore asymptotics do not answer the question of how often (precisely) the above inequality is true or false.

The question I asked is how long is the above inequality true for each k that one might be able to use. Someone suggested it holds for k=0 up to the thirteenth prime, well how long does it hold for k=1, k=2? I'm looking at the precise numbers, not any smooth approximation. So, I guess I will have to get over to the university and see if I can run it up in Mathematica. I want to see graphically how the density decays as well. It is experimental but looking at the pattern, and not just where the trend is going, is the whole point of messing around with primorials and reduced residue systems in the first place. I think I can get it going in Excel maybe, I'll have to try that.

Thanks again,

P-do

 

[shmoe]

I'm not asking a question about the asymptotic density of primes in the reduced residue system of the primorials.

Not directly, but it does tell you there are at most finitely many values of n where that inequality is true, rather handy to know.

You do acknowledge that asymptotic arguments do not reveal the precise number of primes in any of those reduced residues systems under consideration, yes? Therefore asymptotics do not answer the question of how often (precisely) the above inequality is true or false.

Of course, that's why it's called an asymptotic and not an equality. You aren't going to be able to find pi(p#) exactly for p beyond maybe 50 or so, p# grows too quickly. The largest values of n where pi(n) is known exactly is something like n=10^22 or maybe 10^23. These are well beyond the power of a lone desktop computer. 47# is already >6*10^17.

In otherwords, you won't be able to get very far if you limit yourself to exact values for pi(p#). I've suggested before you look up some precise bounds for pi(x), see Dusart's

http://www.unilim.fr/laco/rapports/1998/R1998_06.pdf

The bounds at the top of page 3 give a very tight range for pi(x), tight being relative to the size of pi(x) itself (incidently this also answers the question of the sign of pi(x)-x/log(x), it's always positive past something like x>11, after you check the values of x before those lower bounds apply). This way, for a given p, you can get some bounds on phi(p#)/2-pi(p#) that won't be too far from the truth.


Excel will probably be worthless. Maxima is often suggested as the free alternative to mathematica, but I've never really used either. You should look at pari/gp (also free).

 

[Playdo]

Thanks for pointing me toward that software Schmoe. Your expertise is appreciated BTW.

:-)