MHB Solving Theorem 4.2.1 from Joel Spencer & Noga Alon's "The Probabilistic Method

  • Thread starter Thread starter Aryth1
  • Start date Start date
  • Tags Tags
    Identity Strange
AI Thread Summary
The discussion revolves around solving Theorem 4.2.1 from "The Probabilistic Method" by Joel Spencer and Noga Alon, focusing on the identity involving the sum of reciprocals of primes. The confusion arises from the application of Abel Summation and Stirling's Formula to derive the asymptotic behavior of the sum. Participants explore different approaches, including using Merten's theorems, to establish the relationship between prime density and the logarithmic terms in the integral. The consensus is that understanding the density of primes is crucial for deriving the desired results, and the use of Merten's first theorem simplifies the process significantly. Ultimately, the discussion highlights the importance of these foundational theorems in probabilistic graph theory.
Aryth1
Messages
38
Reaction score
0
I am in an independent study working through probabilistic graph theory and I am stuck on part of a theorem from chapter 4 of The Probabilistic Method by Joel Spencer and Noga Alon (specifically theorem 4.2.1).

In this context, $p$ is a prime number.

The part where I am confused comes from a remark he makes about an identity for a series. He says, and I quote: "... where here we used the well known fact that $\sum_{p\leq x}\left(\frac{1}{p}\right) = ln \ lnx + O(1)$". And claims that one can use Stirling's Formula and Abel Summation to arrive at the result. I can certainly see how Abel Summation is used, and, I tried the following:

Let $$a_n = \begin{cases} ln \ n &\mbox{if } n \mbox{ is prime} \\ 0 & \mbox{ } \mbox{otherwise}. \end{cases} $$

and let $\phi (n) = \frac{1}{nln \ n}$. Then $\sum_{p\leq x}\left(\frac{1}{p}\right) = \sum_{n=1}^x a_n\phi (n)$ and we can apply Abel summation to get:

$\sum_{p\leq x}\left(\frac{1}{p}\right) = A(x)\phi (x) - \int_1^x A(u)\phi '(u) ~du$

where $A(x) := \sum_{n=1}^x a_n = \sum_{p\leq x} lnp$. Then

$\sum_{p\leq x}\left(\frac{1}{p}\right) = \frac{A(x)}{xlnx} + \int_1^x \frac{A(u)(lnu +1)}{(u \ lnu)^2} ~du$.

But I'm stuck here. I did try other ways to do this, but they were equally unsuccessful. Any help is greatly appreciated!
 
Mathematics news on Phys.org
I can see a way to prove that by using the prime number theorem and the much simpler functions:
$$a(x) = \begin{cases}1 ~ ~ &\text{if} ~ x ~ \text{is prime} \\ 0 &\text{otherwise}\end{cases}$$
Such that, of course:
$$A(x) = \sum_{p \leq x} 1 = \pi(x)$$
And the continuously differentiable function given by:
$$\phi(x) = \frac{1}{x} ~ ~ ~ \text{and} ~ ~ ~ \phi'(x) = - \frac{1}{x^2}$$
It requires a bit of care to show that the asymptotic terms resulting from the use of the prime number theorem in the integral are absorbed by the $O(1)$ term (I assume) but it seems to work. I don't know how to prove it otherwise, though - not sure what Stirling's formula (for factorials?) has to do with this :confused:
 
Bacterius said:
I can see a way to prove that by using the prime number theorem and the much simpler functions:
$$a(x) = \begin{cases}1 ~ ~ &\text{if} ~ x ~ \text{is prime} \\ 0 &\text{otherwise}\end{cases}$$
Such that, of course:
$$A(x) = \sum_{p \leq x} 1 = \pi(x)$$
And the continuously differentiable function given by:
$$\phi(x) = \frac{1}{x} ~ ~ ~ \text{and} ~ ~ ~ \phi'(x) = - \frac{1}{x^2}$$
It requires a bit of care to show that the asymptotic terms resulting from the use of the prime number theorem in the integral are absorbed by the $O(1)$ term (I assume) but it seems to work. I don't know how to prove it otherwise, though - not sure what Stirling's formula (for factorials?) has to do with this :confused:

This was actually along the lines of my first solution to the problem. I'm glad that you also share this idea.

It does seem like using Stirling's formula (and I'm not sure which form I'm supposed to use) is a bit unnecessary... Although I've heard there is a weaker form that is actually a series with a logarithm of some kind in it. Something like this, I think:

$$\sum_{n\leq x} log(n) = xlog(x) - x + O(log(x))$$
 
Indeed, still not quite clear to me how it is useful here though. I worked a bit with your idea in your first post but I don't see how it leads to a simpler solution; it seems you ultimately need to know about the density of the primes to make your integral converge to what you need it to - the other term is clearly $O(1)$ - the reason being that:
$$\int_{1}^x \frac{\ln{u} + 1}{u \ln{u}} ~ \mathrm{d} u = \ln{x} + \ln{\ln{x}} \tag{1}$$
Which is what I think you would eventually derive (up to asymptotic terms) without using the prime density, whereas:
$$\int_{1}^x \frac{\ln{u} + 1}{u \ln^2{u}} ~ \mathrm{d} u = \ln{\ln{x}} - \frac{1}{\ln{x}} = \ln{\ln{x}} + O(1)$$
Where you notice the extra $\ln{u}$ factor in the denominator which accounts for the density of the primes, coming from the fact that:
$$\frac{A(u)}{u \ln{u}} = \frac{1}{u} \sum_{p \leq u} \frac{\ln{p}}{\ln{u}} \leq \frac{\pi(u)}{u} \sim \frac{1}{\ln{u}}$$
And you (eventually) get the desired result, though not as easily, whereas not using the density of primes only gives you the weak upper bound:
$$\frac{A(u)}{u \ln{u}} \leq 1$$
Which as seen above in $(1)$ is insufficient to conclude :confused:
 
Last edited:
Bacterius said:
Indeed, still not quite clear to me how it is useful here though. I worked a bit with your idea in your first post but I don't see how it leads to a simpler solution; it seems you ultimately need to know about the density of the primes to make your integral converge to what you need it to - the other term is clearly $O(1)$ - the reason being that:
$$\int_{1}^x \frac{\ln{u} + 1}{u \ln{u}} ~ \mathrm{d} u = \ln{x} + \ln{\ln{x}} \sim \ln{x} \tag{1}$$
Which is what I think you would eventually derive (up to asymptotic terms) without using the prime density, whereas:
$$\int_{1}^x \frac{\ln{u} + 1}{u \ln^2{u}} ~ \mathrm{d} u = \ln{\ln{x}} - \frac{1}{\ln{x}} = \ln{\ln{x}} + O(1)$$
Where you notice the extra $\ln{u}$ factor in the denominator which accounts for the density of the primes, coming from the fact that:
$$\frac{A(u)}{u \ln{u}} = \frac{1}{u} \sum_{p \leq u} \frac{\ln{p}}{\ln{u}} \leq \frac{\pi(u)}{u} \sim \frac{1}{\ln{u}}$$
And you (eventually) get the desired result, though not as easily, whereas not using the density of primes only gives you the weak upper bound:
$$\frac{A(u)}{u \ln{u}} \leq 1$$
Which as seen above in $(1)$ is insufficient to conclude :confused:

Yeah, now that I've seen it worked out it makes sense. Mine was certainly not leading to a simpler solution, I was just curious about how they were so sure that Stirling's formula and Abel summation were used to solve it. I think in any case the density of the prime numbers is required, as you said.

I did some pretty extensive googling yesterday and found the theorems that prove these (although I have yet to find a proof that uses both Stirling's formula and Abel summation). My problem is apparently Merten's second theorem and it uses Merten's first theorem to prove it.

Merten's First Theorem

$$\sum_{p\leq x}\frac{lnp}{p} = lnx + O(1)$$

Merten's Second Theorem

$$\sum_{p\leq x} \left(\frac{1}{p}\right) = ln \ lnx + C_1 + O\left(\frac{1}{lnx}\right)$$

So I may have gotten the functions mixed up. Maybe with a choice of

$$ \displaystyle a_n = \begin{cases} \frac{ln \ n}{n} &\mbox{if } n \mbox{ is prime} \\ 0 & \mbox{ } \mbox{otherwise}. \end{cases} $$

and

$$\phi(x) = \frac{1}{lnx}$$

the solution may come out in a slightly easier way than my previous choices?

Then we'd get

$$A(x) = \sum_{p\leq x}\frac{ln p}{p} = lnx + r(x)$$ (by Merten's First Theorem)

where $$|r(x)|\leq c$$ for some constant $c$, and so

$$\sum_{p\leq x}\left(\frac{1}{p}\right) = \frac{A(x)}{lnx} + \int_2^x \frac{A(u)}{uln^2u} ~du$$

$$ = 1 + \frac{r(x)}{lnx} + \int_2^x\frac{1}{ulnu} ~du + \int_2^x\frac{r(u)}{uln^2u}~du$$

Is this any better? I'm still kind of new to number theory so I'm not sure how I should proceed.
 
Yep, that absolutely works and gives you the right answer; of course, Merten's first theorem which you are using for $A(x)$ is basically equivalent to the prime number theorem, at least for our purposes ;) (specifically it's what gives you the required asymptotic density of the primes of $1 / \ln{n}$) but the fact that it's already given in asymptotic notation makes it easy to prove your original expression (just evaluate the integrals and bound the error terms and you're done)
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top