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)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top