Number theory statements

The following is a list of the statements appearing in our posts about number theory.

Title and link Statement
Theorem N.1: Fundamental theory of arithmetic (not proved) Every integer number greater than 1 can be written as a product of prime numbers. Moreover such expression, called factorization or decomposition into prime factors, is unique apart from the order of the factors.
Theorem N.2: Infinity of primes The number of primes is infinite.
Property N.1: Overestimation of binomials For all n > 0 and for all m: \binom{n}{m} \leq 2^{n-1}
Property N.2: Underestimation of the central binomials of the Pascal’s triangle For all n \geq 2: \binom{n}{\frac{n}{2}} \geq \frac{2^n}{n} if n is even, and \binom{n}{\left \lceil \frac{n}{2} \right \rceil} = \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \geq \frac{2^n}{n} if n is odd.
Property N.3: Underestimation of the central binomial of Pascal’s triangle, even n For all even n \geq 2: \binom{n}{\frac{n}{2}} \geq \sqrt{2^{n}}
Proposition N.1: Majorization of the product of primes up to x For all x > 0: \theta^{\star}(x) = \prod_{1 \leq p \leq x} p \leq 2^{2(x-1)}
Theorem N.3: Bertrand’s postulate For all n > 0, there exists a prime number between n + 1 and 2n.
Lemma N.1: Factorization of the binomial \binom{2n}{n} In the factorization of the binomial \binom{2n}{n}, for n > 0, a prime number p cannot have an exponent greater than \log_p 2n.
Proposition N.2: Computation of \psi^{\star}(x) For every integer x > 0: \psi^{\star}(x) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor}
Corollary of Proposition N.2: Overestimation of \psi^{\star}(x) with \pi(x) For every integer x > 0: \psi^{\star}(x) \leq x^{\pi(x)}
Proposition N.3: Underestimation of \psi^{\star}(x) For every integer x > 0: \psi^{\star}(x) \geq \sqrt[3]{2^x}
Lemma N.2: Reformulation of \psi^{\star}(x) (“calculation by rows”) For every integer x > 0: \psi^{\star}(x) = \left(\prod_{p \leq x} p\right) \cdot \left(\prod_{p^2 \leq x} p\right) \cdot \dots \cdot \left(\prod_{p^R \leq x} p\right)
Proposition N.4: Connection between \psi^{\star} and \theta^{\star} functions For every integer x > 0: \psi^{\star}(x) = \theta^{\star}(x) \cdot \theta^{\star}(\sqrt{x}) \cdot \dots \cdot \theta^{\star}(\sqrt[R]{x}), where R := \left \lfloor \log_2 x \right \rfloor.
Lemma N.3: Underestimation of \theta^{\star}(x) through \pi(x) For every real number \delta \geq 0 and for every x \gt 1: \theta^{\star}(x) \gt \left(x^{\delta}\right)^{\pi(x) - x^{\delta}}.
Theorem N.4: Asymptotic equivalence and order of magnitude of \theta(x) and \psi(x) The functions \theta(x) and \psi(x) are asymptotically equivalent and have order x: \theta(x) \sim \psi(x), \theta(x) \asymp x \asymp \psi(x).
Theorem N.5: Asymptotical equivalence between \pi(x) and \frac{\theta(x)}{\log x} \pi(x) \sim \frac{\theta(x)}{\log x}
Corollary of Theorem N.5: Asymptotical equivalence between \pi(x) and \frac{\psi(x)}{\log x} \pi(x) \sim \frac{\psi(x)}{\log x}
Corollary II of Theorem N.5: Chebyshev’s Theorem: order of magnitude of \pi(x) \pi(x) \asymp \frac{x}{\log x}
Lemma N.4: Lemma of bar chart area Let c_1, c_2, \dots, c_n be natural numbers, with n > 0. Let f: \{1, 2, ..., n\} \rightarrow \mathbb{R} be a function. Then the area A of the bar chart made up of n rectangles, each having basis c_i and height f(i), given by A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), can also be computed with the formula \begin{aligned}A &= C_n f(n) + C_{n-1} (f(n-1) - f(n)) + \ldots + C_1 (f(1) - f(2)) \\&= \sum_{k = 1}^{n-1} C_k (f(k) - f(k + 1)) + C_n f(n)\end{aligned} where C_k := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Lemma N.5: Lemma of bar chart area, second form Let c_1, c_2, \dots, c_n be natural numbers, with n > 0. Let f: \{1, 2, ..., n\} \rightarrow \mathbb{R} be a function, and \widetilde{f} a C^1 extension of f. Then the area A of the bar chart made up of n rectangles, each with basis c_i and height f(i), given by A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), can be also computed with the formula C(n) f(n) - \int_1^n \overline{C}(k) \widetilde{f}'(t) dt where C: \{1, 2, ..., n\} \rightarrow \mathbb{N} is the function defined by C(k) := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Theorem N.6: Approximation of the sum of inverses of the first positive integers

For all integers n \gt 0:

\sum_{k = 1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \approx \log n + \gamma

where logarithm base is Napier’s number e, while \gamma \approx 0.58 is the Euler’s constant. In particular:

\sum_{k = 1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} = \log n + \gamma + O\left(\frac{1}{n}\right)
Property N.4: Upper and lower bounds for the value assumed by a function defined on integer numbers, by means of integrals of an extension

Let f: I \rightarrow \mathbb{R} be a function defined on a set I \subset \mathbb{Z}.
Let \overset{\sim}{f}: \overline{I} \rightarrow \mathbb{R} an extension of f, where \overline{I} := \bigcup_{n \in I} [n, n + 1). Then:

  • If \overset{\sim}{f} is increasing, then f(n) \leq \int_n^{n+1} \overset{\sim}{f}(t) dt
  • If \overset{\sim}{f} is decreasing, then f(n) \geq \int_n^{n+1} \overset{\sim}{f}(t) dt

Let \underset{\sim}{f}: \underline{I} \rightarrow \mathbb{R} be an extension of f, where \underline{I} := \bigcup_{n \in I} (n - 1, n]. Then:

  • If \underset{\sim}{f} is increasing, then \int_{n-1}^n \underset{\sim}{f}(t) dt \leq f(n)
  • If \underset{\sim}{f} is decreasing, then \int_{n-1}^n \underset{\sim}{f}(t) dt \geq f(n)
Lemma N.6: Order of magnitude of the sum of a fraction logarithms when the denominator changes \sum_{n=1}^x \log \left(\frac{x}{n} \right) = O(x).
Proposition N.5: Order of magnitude of the factorial function x! = x^x \cdot e^{O(x)}
Property N.5: Number of multiples of a given number, between 1 and x

Let n and x be two positive integers. The number of multiples of n that belong to the range [1, x] is \left \lfloor \frac{x}{n} \right \rfloor.

Proposition N.6: The factorial function and the \Lambda^{\star} function For every integer x \gt 0: x! = \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}
Property N.6: Connection between \Lambda^{\star} and \psi^{\star} For every integer x \gt 0: \prod_{r = 1}^x \Lambda^{\star}(r) = \psi^{\star}(x)
Proposition N.7: Order of magnitude of the factorial-like function based on \Lambda^{\star} \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}} = x^x \cdot e^{O(x)}
Corollary of Proposition N.7: Order of magnitude of the factorial-like function based on \Lambda^{\star} \sum_{r = 1}^x \frac{\Lambda(r)}{r} = \log x + O(1)
Theorem N.7: Limit inferior and limit superior of the function \frac{\overline{\psi}(t)}{t} \begin{cases} \lim \inf \frac{\overline{\psi}(t)}{t} \leq 1 \\ \lim \sup \frac{\overline{\psi}(t)}{t} \geq 1 \end{cases}
Corollary of Theorem N.7: Limit inferior and limit superior of the function \overline{\pi}(t) / \frac{t}{\log t} \begin{cases} \lim \inf \overline{\pi}(t) / \frac{t}{\log t} \leq 1 \\ \lim \sup \overline{\pi}(t) / \frac{t}{\log t} \geq 1 \end{cases}
Corollary II of Theorem N.7: Chebyshev’s Theorem, strong version If the function \pi(x) / \frac{x}{\log x} tends to a limit, that limit is 1.
Theorem N.8: Prime number Theorem \pi(x) \sim \frac{x}{\log x}
Theorem N.9: Prime number Theorem, strong version \pi(x) \sim \mathrm{Li}(x)