Bhargava factorial

Template:Short description In mathematics, Bhargava's factorial function, or simply the Bhargava factorial, is a generalization of the factorial function developed by the Fields Medal winning mathematician Manjul Bhargava as part of his bachelor's thesis at Harvard University in 1996. Bhargava subsequently published a revised version in The American Mathematical Monthly in 2000. The Bhargava factorial has the property that many number-theoretic results involving the ordinary factorials remain true even when the factorials are replaced by the Bhargava factorials. Using an arbitrary infinite subset S of the set $\mathbb{Z}$ of integers, Bhargava associated a positive integer with every positive integer k, which he denoted by k !_S, with the property that if one takes S = $\mathbb{Z}$ itself, then the integer associated with k, that is k !_$\mathbb{Z}$ , would turn out to be the ordinary factorial of k.

Motivation for the generalization

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5×4×3×2×1 = 120. By convention, the value of 0! is defined as 1. This classical factorial function appears prominently in many theorems in number theory. The following are a few of these theorems.

1. For any positive integers m and n, (m + n)! is a multiple of m! n!.
2. Let f(x) be a primitive integer polynomial, that is, a polynomial in which the coefficients are integers and are relatively prime to each other. If the degree of f(x) is k then the greatest common divisor of the set of values of f(x) for integer values of x is a divisor of k!.
3. Let a₀, a₁, a₂, ... , a_n be any n + 1 integers. Then the product of their pairwise differences is a multiple of 0! 1! ... n!.
4. Let $\mathbb{Z}$ be the set of integers and n any integer. Then the number of polynomial functions from the ring of integers $\mathbb{Z}$ to the quotient ring $\mathbb{Z}/n\mathbb{Z}$ is given by $\prod _{k=0}^{n-1}\frac{n}{gcd(n,k!)}$.

Bhargava posed to himself the following problem and obtained an affirmative answer: In the above theorems, can one replace the set of integers by some other set S (a subset of $\mathbb{Z}$, or a subset of some ring) and define a function depending on S which assigns a value to each non-negative integer k, denoted by k!_S, such that the statements obtained from the theorems given earlier by replacing k! by k!_S remain true?

The generalisation

• Let S be an arbitrary infinite subset of the set Z of integers.
• Choose a prime number p.
• Construct an ordered sequence {a₀, a₁, a₂, ... } of numbers chosen from S as follows (such a sequence is called a p-ordering of S):

1. a₀ is any arbitrary element of S.
2. a₁ is any arbitrary element of S such that the highest power of p that divides a₁ − a₀ is minimum.
3. a₂ is any arbitrary element of S such that the highest power of p that divides (a₂ − a₀)(a₂ − a₁) is minimum.
4. a₃ is any arbitrary element of S such that the highest power of p that divides (a₃ − a₀)(a₃ − a₁)(a₃ − a₂) is minimum.
5. ... and so on.

• Construct a p-ordering of S for each prime number p. (For a given prime number p, the p-ordering of S is not unique.)
• For each non-negative integer k, let v_k(S, p) be the highest power of p that divides (a_k − a₀)(a_k − a₁)(a_k − a₂) ... (a_k − a_k − 1). The sequence {v₀(S, p), v₁(S, p), v₂(S, p), v₃(S, p), ... } is called the associated p-sequence of S. This is independent of any particular choice of p-ordering of S. (We assume that v₀(S, p) = 1 always.)
• The factorial of the integer k, associated with the infinite set S, is defined as $k{!}_S=\prod _p{v}_k(S,p)$, where the product is taken over all prime numbers p.

Example: Factorials using set of prime numbers

Let S be the set of all prime numbers P = {2, 3, 5, 7, 11, ... }.

• Choose p = 2 and form a p-ordering of P.

• Choose a₀ = 19 arbitrarily from P.
• To choose a₁:

• The highest power of p that divides 2 − a₀ = −17 is 2⁰ = 1. Also, for any a ≠ 2 in P, a − a₀ is divisible by 2. Hence, the highest power of p that divides (a₁ − a₀) is minimum when a₁ = 2 and the minimum power is 1. Thus a₁ is chosen as 2 and v₁(P, 2) = 1.

• To choose a₂:

• It can be seen that for each element a in P, the product x = (a − a₀)(a − a₁) = (a − 19)(a − 2) is divisible by 2. Also, when a = 5, x is divisible 2 and it is not divisible by any higher power of 2. So, a₂ may be chosen as 5. We have v₂(P, 2) = 2.

• To choose a₃:

• It can be seen that for each element a in P, the product x = (a − a₀)(a − a₁)(a − a₂) = (a − 19)(a − 2)(a − 5) is divisible by 2³ = 8. Also, when a = 17, x is divisible by 8 and it is not divisible by any higher power of 2. Choose a₃ = 17. Also we have v₃(P,2) = 8.

• To choose a₄:

• It can be seen that for each element a in P, the product x = (a − a₀)(a − a₁)(a − a₂)(a − a₃) = (a − 19)(a − 2)(a − 5)(a − 17) is divisible by 2⁴ = 16. Also, when a = 23, x is divisible 16 and it is not divisible by any higher power of 2. Choose a₄ = 23. Also we have v₄(P,2) = 16.

• To choose a₅:

• It can be seen that for each element a in P, the product x = (a − a₀)(a − a₁)(a − a₂)(a − a₃)(a − a₄) = (a − 19)(a − 2)(a − 5)(a − 17)(a − 23) is divisible by 2⁷ = 128. Also, when a = 31, x is divisible 128 and it is not divisible by any higher power of 2. Choose a₅ = 31. Also we have v₅(P,2) = 128.

• The process is continued. Thus a 2-ordering of P is {19, 2, 5, 17, 23, 31, ... } and the associated 2-sequence is {1, 1, 2, 8, 16, 128, ... }, assuming that v₀(P, 2) = 1.

• For p = 3, one possible p-ordering of P is the sequence {2, 3, 7, 5, 13, 17, 19, ... } and the associated p-sequence of P is {1, 1, 1, 3, 3, 9, ... }.

• For p = 5, one possible p-ordering of P is the sequence {2, 3, 5, 19, 11, 7, 13, ... } and the associated p-sequence is {1, 1, 1, 1, 1, 5, ...}.

• It can be shown that for p ≥ 7, the first few elements of the associated p-sequences are {1, 1, 1, 1, 1, 1, ... }.

The first few factorials associated with the set of prime numbers are obtained as follows Template:OEIS.

Table of values of v_k(P, p) and k!_P

Template:Diagonal split header	2	3	5	7	11	...		k!P
0	1	1	1	1	1	...		1×1×1×1×1×... =	1
1	1	1	1	1	1	...		1×1×1×1×1×... =	1
2	2	1	1	1	1	...		2×1×1×1×1×... =	2
3	8	3	1	1	1	...		8×3×1×1×1×... =	24
4	16	3	1	1	1	...		16×3×1×1×1×... =	48
5	128	9	5	1	1	...		128×9×5×1×1×... =	5760
6	256	9	5	1	1	...		256×9×5×1×1×... =	11520

Example: Factorials using the set of natural numbers

Let S be the set of integers $\mathbb{Z}$.

• For p = 2, the associated p-sequence is {1, 1, 2, 2, 8, 8, 16, 16, 128, 128, 256, 256, ... }.
• For p = 3, the associated p-sequence is {1, 1, 1, 3, 3, 3, 9, 9, 9, 27, 27, 27, 81, 81, 81, ... }.
• For p = 5, the associated p-sequence is {1, 1, 1, 1, 1, 5, 5, 5, 5, 5, 25, 25, 25, 25, 25, ... }.
• For p = 7, the associated p-sequence is {1, 1, 1, 1, 1, 1, 1, 7, 7, 7, 7, 7, 7, 7, ... }.
• ... and so on.

Thus the first few factorials using the integers are

• 0!_$\mathbb{Z}$ = 1×1×1×1×1×... = 1.
• 1!_$\mathbb{Z}$ = 1×1×1×1×1×... = 1.
• 2!_$\mathbb{Z}$ = 2×1×1×1×1×... = 2.
• 3!_$\mathbb{Z}$ = 2×3×1×1×1×... = 6.
• 4!_$\mathbb{Z}$ = 8×3×1×1×1×... = 24.
• 5!_$\mathbb{Z}$ = 8×3×5×1×1×... = 120.
• 6!_$\mathbb{Z}$ = 16×9×5×1×1×... = 720.

Examples: Some general expressions

The following table contains the general expressions for k!_S for some special cases of S.

Sl. No.	Set S	k!S
1	Set of integers	k!
2	Set of even integers	2k×k!
3	Set of integers of the form an + b	ak×k!
4	Set of integers of the form 2n	(2k − 1)(2k − 2) ... (2k − 2k − 1)
5	Set of integers of the form qn for some prime q	(qk − 1)(qk − q) ... (qk − qk − 1)
6	Set of squares of integers	(2k)!/2