I am reading Kenneth Ireland and Michael Rosen's A Classical Introduction to Modern Number Theory, and I'm having trouble with a step in one of their proofs.

The proof in question is of Corollary 1 in chapter 2, section 4. The corollary is stated as follows:

There is a positive constant $c_{1}$ such that $\pi(x) < c_{1}x/$log $x$ for $x \ge 2$.

It goes without saying, but for the benefit of readers new to number theory, $\pi(x)$ is the number of primes less than or equal to $x$ and is known as the prime counting function. The proof employs a function on the natural numbers defined as $\theta(x) = \sum_{p \le x}$ log $p$, the sum being over all primes at most x. The proof begins as follows:

$\theta(x) \ge \sum^{p \le x}_{p > \sqrt{x}}$ log $p \ge $ (log$\sqrt{x})(\pi(x) - \pi(\sqrt{x})) \ge $ (log$\sqrt{x})\pi(x) - \sqrt{x}$log$\sqrt{x}$.

The first inequality follows from the definition of $\theta(x)$, the next follows from the fact that log $p > $ (log$\sqrt{x})$ and $\pi(x) - \pi(\sqrt{x})$ is the number of primes $p$ that satisfy $\sqrt{x} < p \le x$. However, the last inequality seems to imply that $\pi(\sqrt{x}) \ge \sqrt{x}$ if you multiply out the (log$\sqrt{x}$) term, and that can't be true.

I'd like to know if there's some logic I'm missing here, like maybe they aren't multiplying out the (log$\sqrt{x}$) term and are instead using some trick to get that last inequality. Perhaps they're using one of the earlier propositions about $\pi(x)$, namely Proposition 2.4.1: $\pi(x) \ge $ log(log$x$) or Proposition 2.4.2: $\pi(x) \ge $ log$x/(2$log$2)$ - though I'm having trouble spotting how they might be using them.

Edit: Silly mistake, going to leave this question up as a reminder for myself to stay humble.


Your misunderstanding is simple. They actually use $\pi(\sqrt{x})\le \sqrt{x}$, which is obviously true and equivalent to $-\pi(\sqrt{x})\ge -\sqrt{x}$. Since the term has a negative sign, this is the correct result.

  • $\begingroup$ That was silly of me. Thanks. $\endgroup$ – Alena Gusakov Jun 19 '19 at 16:41
  • $\begingroup$ @Alena No problem ;) $\endgroup$ – F.U.A.S. Jun 19 '19 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.