13. The factorial function and the Lambda* function

Prerequirements:

Almost centainly you already know the factorial function, indicated by x!, which is read as “x factorial” and for an integer x \gt 0 it consists in the product of all positive integers up to x:

x! := 1 \cdot 2 \cdot \ldots \cdot x \textrm{\ (}x \gt 0\text{)\ } \tag{1}

Moreover, remember that it’s established that 0! = 1, consistently with our usual assumption that the product of an empty set of numbers is 1.
The factorial function is used above all in combinatorics; but combinatorics is one of the foundations of number theory (see for example the post The product of the first prime numbers: an overestimation), so it should not be surprising that factorial often occurs also in number theory. In this post we’ll study the factorial from two different points of view: first we’ll study its order of magnitude; then we’ll decompose the product (1) in such a way to highlight the prime factors which it’s made up of.

Order of magnitude

Saying that the factorial function grows rapidly would be an understatement: for example, 10! is 3,628,800 and 50! is a number with 65 digits. The key techniques for studying such a function are two:

  • Comparing the factorial function with another one that grows as much rapidly, but simpler
  • Passing to logarithms. In fact the logarithm function has two good properties:
    • it considerably reduce the growth rate of a function
    • it transforms products into sums, which are easier to study

A function simpler than factorial, with a similar growth rate, is the function x^x. It’s simpler because, instead of varying the product factors, this function repeats x times the product of the same number x:

x^x = \underbrace{x \cdot \ldots \cdot x}_{x \textrm{ times}} \textrm{\ (}x \gt 0\text{)\ } \tag{2}

Comparing (1) with (2) you can see immediately that x^x is greater than x!, but how much is it greater? For understanding that, let’s study the ratio:

\frac{x^x}{x!} = \frac{x}{1} \cdot \frac{x}{2} \cdot \ldots \cdot \frac{x}{x} \tag{3}

Now let’s introduce logarithms:

\log \frac{x^x}{x!} = \log \left( \frac{x}{1} \right) + \log \left( \frac{x}{2} \right) + \ldots + \log \left( \frac{x}{x} \right) = \sum_{1 \leq n \leq x} \log \left( \frac{x}{n} \right)

The function so obtained is exactly the one we saw in the previous post. By Lemma N.6, it’s a big Oh of x, hence:

\log \frac{x^x}{x!} = O(x)

Or equivalently, removing logarithms:

\frac{x^x}{x!} = e^{O(x)} \tag{4}

From this equality we can obtain the order of magnitude of the factorial function:

x! = \frac{x^x}{e^{O(x)}} = x^x \cdot e^{-O(x)} = x^x \cdot e^{O(x)}\tag{5}

The last passage can be justified because O(x) = -O(x). In order to understand this equality, we have to remember that O(x) represents a function both on the right and on the left, so O(x) = -O(x) means two things:

  • O(x) \subset -O(x), that is for each function f = O(x) there is a function g = O(x) such that f = -g
  • -O(x) \subset O(x), that is for each function f = O(x) there is a function g = O(x) such that -f = g

Indeed the question is simpler than it may seem, because clearly this g is nothing else than -f, so for the first case it’s enough to prove that f = O(x) \Rightarrow -f = O(x); moreover the second case is equivalent to the first one, because f = -g \Leftrightarrow -f = g, so nothing else has to be proved.
Remembering the definition of f = O(x), i.e. that definitively -Ax \leq f(x) \leq Ax for some constant A \geq 0 (see Definition A.3 (Asymptotic relationships, alternative definitions using inequalities)), we can prove the implication f = O(x) \Rightarrow -f = O(x), thus completing the proof:

f = O(x) \Rightarrow -Ax \leq f(x) \leq Ax \Rightarrow Ax \geq -f(x) \geq -Ax \Rightarrow -Ax \leq -f(x) \leq A(x) \Rightarrow -f = O(x)

So we can state the following Proposition:

Order of magnitude of the factorial function

x! = x^x \cdot e^{O(x)}
A more accurate approximation of the factorial function is given by Stirling’s formula, according to which

x! \sim \sqrt{2 \pi x} \frac{x^x}{e^x}

From this formula we can obtain:

\frac{x^x}{x!} \sim \frac{e^x}{2 \pi x}

So the ratio (3), that in (4) we expressed more generically in the form e^{O(x)}, is indeed asymptotically equivalent to \frac{e^x}{2 \pi x}. But for our purposes it’s not necessary to use Stirling’s formula, but Proposition N.5 is sufficient.

The factorial function and the \Lambda^{\star} function

So far we have studied the order of magnitude of the factorial function, but what can we say about its exact value? Regarding this, we’ll see a construction that can help us to see the factorial from another point of view.

Let’s suppose to compute the factorial of an integer x \gt 0. Let’s construct a table made up of x rows and just as many columns, numbered from 1 to x. Let’s fill the table this way: in the cell at the intersection between column c and row r we write, only if r \mid c, the number

  • p, if r = p^m for some prime p and some integer m \gt 0
  • 1, otherwise

In other terms, we write p if in the factorization of r only a prime p is present, whereas we write 1 if no prime is present, i.e. r = 1, or several different primes occur.

For example, for x = 15 the following table is obtained:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3
4 2 2 2
5 5 5 5
6 1 1
7 7 7
8 1
9 3
10 1
11 11
12 1
13 13
14 1
15 1

In fact:

  • 1 is the power of no prime number, so in its row there is always 1
  • In the factorization of 6, 10, 12, 14, 15 there are several distinct primes, so in the corresponding rows we write always 1
  • In the factorization of 2, 3, 4, 5, 7, 8, 9, 11, 13 there is only a distinct prime number, i.e. these numbers are of the form p^m with m \gt 0, so in the corresponding rows we write this prime p

The table so obtained has a fundamental property: for each column c, the product of the numbers inside it is c itself. For example, in reference to the previous example, inside column 12 we have 1, 2, 3 and again 2, in fact 12 = 1 \cdot 2 \cdot 3 \cdot 2.

In order to prove this property, first of all we have to remember that we wrote a number in the cell (r, c), belonging to row r and column c, if and only if r \mid c. So, inside column c, only the cells in rows that are divisors of c will be filled. Now let’s decompose c into prime factors:

c = q_1^{m_1} \cdot q_2^{m_2} \cdot \ldots \cdot q_h^{m_h} \tag{6}

where q_1, q_2, \ldots, q_h are the distinct primes occurring in the factorization of c, so the respective exponents m_1, m_2, \ldots, m_h are all greater than zero.

Now let’s consider a divisor d of c. Having written c in the form (6), d can be written in the form

d = q_1^{n_1} \cdot q_2^{n_2} \cdot \ldots \cdot q_h^{n_h} (0 \leq n_1 \leq m_1, 0 \leq n_2 \leq m_2, \ldots, 0 \leq n_h \leq m_h)\tag{7}

That is, only the prime numbers that are present in the factorization of c can occur in the factorization of d, and each of them, if it occurs, has an exponent less than or equal to the one it has in the factorization of c. Indeed, the fact that a prime q_i occurs or not in the factorization of d is regulated by the relative exponent n_i: if n_i = 0 then q_i does not occur; whereas if 0 \lt n_i \leq m_i, then it occurs with an exponent at most equal to the one it has in the factorization of c.
The fact that d can be written in the form (7) can be proved by contradiction. If d could not be written in the form (7), it would mean that either its factorization contains some primes that are not present in the one of c; or it contains a prime that is present in both factorizations, but the exponent of such a prime in the factorization of d is greater than the one in the factorization of c. But in both these cases d would not be a divisor of c. So, since by negating (7) we obtained that d isn’t a dividor of c, then conversely, if d is a divisor of c, formula (7) is true.

Having written d this way, we can distinguish three cases:

  • n_1 = n_2 = \ldots = n_h = 0. In this case d = 1, so in the cell (d, c) = (1, c) there is the number 1.
  • At least two among n_1, n_2, \ldots, n_h are greater than zero. In this case the factorization of d contains at least two distinct prime factors, so in the cell (d, c) there is the number 1.
  • Only one among n_1, n_2, \ldots, n_h is greater than zero. In this case d = q_i^{n_i} for some i, so in the cell (d, c) there is the number q_i.

It’s clear that only the third case affects the product of the numbers inside column c, so let’s focus our attention on it. How many times can this case happen? Answering this question is equivalent to ask how many divisors of c of the kind d = q_i^{n_i}, with n_i \gt 0, exist. The count is simple, because q_i can vary between q_1 and q_h, while, for each choice of q_i, the relative exponent n_i can vary between 1 and m_i. So there are m_1 possibilities for q_1, m_2 possibilities for q_2, …, m_h possibilities for q_h, hence the total number of possibile cases is m_1 \cdot m_2 \cdot \ldots \cdot m_h. Let’s write them explicitly:

  • d = q_1^{n_1}, 0 \lt n_1 \leq m_1: they are the m_1 divisors d = q_1, d = q_1^2, \ldots, d = q_1^{m_1}: in all these cases in the cell (d, c) there is the number q_1
  • d = q_2^{n_2}, 0 \lt n_2 \leq m_2: they are the m_2 divisors d = q_2, d = q_2^2, \ldots, d = q_2^{m_2}: in all these cases in the cell (d, c) there is the number q_2
  • d = q_h^{n_h}, 0 \lt n_h \leq m_h: they are the m_h divisors d = q_h, d = q_h^2, \ldots, d = q_h^{m_h}: in all these cases in the cell (d, c) there is the number q_h

So, summarizing:

  • In the cell (r, c) there is a number only when r = d, where d is a divisor of c
  • The m_1 cells (q_1, c), (q_1^2, c), …, (q_1^{m_1}, c) contain the number q_1
  • The m_2 cells (q_2, c), (q_2^2, c), …, (q_2^{m_2}, c) contain the number q_2
  • The m_h cells (q_h, c), (q_h^2, c), …, (q_h^{m_h}, c) contain the number q_h
  • No other cell contains a number different from 1, because there are no other divisors of c in the factorization of which there is only a distinct prime number.

From that we can deduce that the product of the numbers in column c is q_1^{m_1} \cdot q_2^{m_2} \cdot \ldots q_h^{m_h}; but this product, by (6), is just c, as we wanted to prove.

But if the product of the numbers in any column, from 1 to x, is equal to the column number, then the product of the numbers of all the columns, that is the product of all the numbers in the table, is equal to 1 \cdot 2 \cdot \ldots \cdot x = x!.

Now let’s focus our attention on the last product, the one on all the numbers in the table. Clearly it doesn’t change if, instead of reading the numbers by columns, we read them by rows: this way we can obtain a rather interesting formula.
For how we constructed the table, on a single row r there is always the same number, that we’ll call \Lambda^{\star}(r), setting x := r in the following general Definition:

Function \Lambda^{\star}

We define the function \Lambda^{\star}: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} such that:

\Lambda^{\star}(x) := \begin{cases} p & \text{if $x = p^m$ for some prime $p$ and some positive integer $m$} \\ 1 & \text{otherwise}\end{cases}

But how many times does the number \Lambda^{\star}(r) occur in row r? It occurs at the intersection with columns with a number that is multiple of r, so in total it occurs as many times as the amount of multiples of r that belong to the range [1, x]. This number can be computed with a simple formula:

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.

If we divide x by n, we have that there are two integers q and r (respectively, the quotient and the remainder) such that:

x = qn + r, 0 \leq r \lt n \tag{8}

So there are certainly q multiples of n in the range [1, x]: n, 2n, \ldots, qn. All these are in fact positive numbers less than or equal to qn, that in turn, by (8), is less than or equal to x. Let’s see if there is some other multiple of n in the range [1, x]. We can obviously discard the negative multiples and zero, that surely do not belong to the range. Concerning instead the multiple (q + 1)n, it’s greater than x, because (q + 1)n = qn + n \gt qn + r = x. So all the more true also any other multiple hn, with h \gt q, is greater than x. Then there are exactly q multiples of n in the range [1, x], and they are n, 2n, \ldots, qn.
But q, the quotient of the division of x by n, indeed coincides with the integer part of the division itself, that is \left \lfloor \frac{x}{n} \right \rfloor. For proving this, we have to remember that the integer part (or floor) of a real number t is defined as the greatest integer less than or equal to t. In this case t := \frac{x}{n}, and q is an integer less than or equal to \frac{x}{n}; in fact, by (8):

q = \frac{x - r}{n} \leq \frac{x}{n}

Moreover q is the greatest integer less than or equal to \frac{x}{n}; in fact the next integer, q + 1, is greater than \frac{x}{n}:

q + 1 = \frac{x - r}{n} + 1 = \frac{x + n - r}{n} \geq \frac{x + 1}{n} \gt \frac{x}{n}

where in the passage \frac{x + n - r}{n} \geq \frac{x + 1}{n} we used the fact that r \lt n, by (8). So, by definition of integer part, q = \left \lfloor \frac{x}{n} \right \rfloor and q, as we saw before, is the number of multiples of n in the range [1, x].

Setting n := r in Property N.5, we have that there are \left \lfloor \frac{x}{r} \right \rfloor multiples of r in the range [1, x], so \Lambda^{\star}(r) occurs \left \lfloor \frac{x}{r} \right \rfloor times in the row r. Then the product of the numbers in row r is \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}, and the product of all the numbers in the table is

\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}

This is the product of the numbers in the table computed by rows. Since it must coincide with the same product computed by column, that is x! as we saw before, we have proved the following Proposition:

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} \tag{9}

Joining Proposition N.5 with Proposition N.6, we’ll obtain that the order of magnitude of the function \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor} is x^x e^{O(x)}. This can be a starting point for the study of the \Lambda^{\star} function, but it would be better without the integer part, because this operator complicates calculations. So we can ask ourselves: what happens if in formula (9) we remove the integer part? How much would the right member differ from the factorial? Let’s see.
First of all, since any real number differs from its integer part by less than a unity, we have that

0 \leq \frac{x}{r} - \left \lfloor \frac{x}{r} \right \rfloor \lt 1

So, if in (9) we remove the integer part, we’ll obtain a greater quantity, with an error belonging to the following range:

\prod_{r = 1}^x \Lambda^{\star}(r)^0 \leq \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left( \frac{x}{r} - \left \lfloor \frac{x}{r} \right \rfloor \right)} \lt \prod_{r = 1}^x \Lambda^{\star}(r)^1

Starting from this inequality, doing the calculations and using Proposition N.6, we’ll obtain:

\begin{aligned}1 \leq \frac{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}}}{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}} \lt \prod_{r = 1}^x \Lambda^{\star}(r) & \Leftrightarrow \\ 1 \leq \frac{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}}}{x!} \lt \prod_{r = 1}^x \Lambda^{\star}(r) & \end{aligned}\tag{10}

The product \prod_{r = 1}^x \Lambda^{\star}(r) is very interesting. Computing this product means to scan all integer numbers from 1 to x, and to multiply by a factor p each time that a new power of a prime p is encountered. Doing so, finally every prime p will occur in the product as many times as the number of its powers less than or equal to x. But if there are N powers of p less than or equal to x, they are p, p^2, \ldots, p^N. Then the greatest power of p less than or equal to x is p^N, so N = \left \lfloor \log_p x \right \rfloor. An example is shown in the following picture, for x = 9:

The factorial function and the Lambda* function

So we can say that:

\prod_{r = 1}^x \Lambda^{\star}(r) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor}

Do you remember what is the function on the right? By Proposition N.2 (Computation of \psi^{\star}(x)), \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor} = \psi^{\star}(x): it’s the function that computes the least common multiple of the integer numbers from 1 to x. Therefore we can state the following Property:

Connection between \Lambda^{\star} and \psi^{\star}

For every integer x \gt 0:

\prod_{r = 1}^x \Lambda^{\star}(r) = \psi^{\star}(x)

So, by (10) and Property N.6:

1 \leq \frac{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}}}{x!} \lt \psi^{\star}(x) \tag{11}

But, by Theorem N.4 (Asymptotic equivalence and order of magnitude of \theta(x) and \psi(x)), \log \psi^{\star}(x) = \psi(x) \asymp x, so in particular \log \psi^{\star}(x) = O(x), hence \psi^{\star}(x) = e^{O(x)}. Substituting into (11) we’ll obtain:

\frac{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}}}{x!} = e^{O(x)} \tag{12}

Let’s call f the function that appears on the left side of (11), i.e. f(x) := \frac{\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}}}{x!}. By (11) we have that 1 \leq f(x) \lt \psi^{\star}(x), in addition we saw that \psi^{\star}(x) = e^{O(x)}, hence 1 \leq f(x) \lt e^{O(x)}. So the question is: from this inequality, can we deduce that f(x) = e^{O(x)}?

In order to answer, let’s remember that O(x) by definition is a function g such that definitively |g(x)| \leq Ax, that is -Ax \leq g(x) \leq Ax, for some constant A \geq 0. So a function e^{O(x)} is a function h such that definitively e^{-Ax} \leq h(x) \leq e^{Ax}. We have to prove that this inequality is true for h := f. Starting from 1 \leq f(x) \lt e^{O(x)}, since e^{O(x)} \leq e^{Ax}, we have that:

1 \leq f(x) \lt e^{Ax}

But, being the function e^x increasing and A \geq 0, we have that e^{-Ax} \leq e^0 = 1, therefore:

e^{-Ax} \leq f(x) \lt e^{Ax}

So, by definition, f(x) = e^{O(x)}, as we wanted to prove.
Let’s observe that, in order to achieve this result, both members of the starting inequality, 1 \leq f(x) \lt e^{O(x)}, are important. If we disregarded the fact that 1 \leq f(x), we couldn’t conclude that f(x) = e^{O(x)}. In fact this is not true, for example, if f(x) is -x or another function with all negative values.

Finally from (12), by applying Proposition N.5, we’ll obtain:

\prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}} = x!\ e^{O(x)} = (x^x e^{O(x)}) e^{O(x)} = x^x e^{O(x) + O(x)} = x^x e^{O(x)}

Summarizing, we can state the following Proposition:

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)}
Comparing Proposition N.7 with Proposition N.5, we can note that the function \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}} has order of magnitude x^x e^{O(x)} just like the factorial, so the fact that we removed the integer parts from (9) was irrelevant from this point of view.

Leave a Reply

Your email address will not be published.