Bhargava factorial

In mathematics, Bhargava's factorial function, or simply Bhargava factorial, is a certain generalization of the factorial function developed by the Fields Medal winning mathematician Manjul Bhargava as part of his thesis in Harvard University in 1996. 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 Z of integers, Bhargava associated a positive integer with every positive integer k, which he denoted by k !_S, with the property that if we take S = Z itself, then the integer associated with k, that is k !_Z, would turn out to be the ordinary factorial of k. ^[1]

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]

1. For any positive integers k and l, (k + l)! is a multiple of k! l!.
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 Z be the set of integers and n any integer. Then the number of polynomial functions from the ring of integers Z to the quotient ring Z/nZ is given by ${\displaystyle \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 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 ${\displaystyle 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 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 asspociated 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 (sequence A053657 in the OEIS).

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

	p = 2	p = 3	p = 5	p = 7	p = 11	. . .	k!P
k = 0	1	1	1	1	1	. . .	1×1×1×1×1×. . . = 1
k = 1	1	1	1	1	1	. . .	1×1×1×1×1×. . . = 1
k = 2	2	1	1	1	1	. . .	2×1×1×1×1×. . . = 2
k = 3	8	3	1	1	1	. . .	8×3×1×1×1×. . . = 24
k = 4	16	3	1	1	1	. . .	16×3×1×1×1×. . . = 48
k = 5	128	9	5	1	1	. . .	128×9×5×1×1×. . . = 5760
k = 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 natural numbers 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 natural numbers are

• 0!_Z = 1×1×1×1×1×. . . = 1.
• 1!_Z = 1×1×1×1×1×. . . = 1.
• 2!_Z = 2×1×1×1×1×. . . = 2.
• 3!_Z = 2×3×1×1×1×. . . = 6.
• 4!_Z = 8×3×1×1×1×. . . = 24.
• 5!_Z = 8×3×5×1×1×. . . = 120.
• 6!_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.^[1]

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

Properties

Let S be an infinite subset of the set Z of integers. For any integer k, let k!_S be the Bhargava factorial of k associated with the set S. Manjul Bhargava proved the following results which are generalisations of corresponding results for ordinary factorials.^[1]

1. For any positive integers k and l, (k + l)!_S is a multiple of k!_S × l!_S.
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 values of x in the set S is a divisor of k!_S.
3. Let a₀, a₁, a₂, . . . , a_n be any n + 1 integers in the set S. Then the product of their pairwise differences is a multiple of 0!_S 1!_S ... n!_S.
4. Let Z be the set of integers and n any integer. Then the number of polynomial functions from S to the quotient ring Z/nZ is given by ${\displaystyle \prod _{k=0}^{n-1}{\frac {n}{\gcd(n,k!_{S})}}}$.

References

1. Bhargava, Manjul (2000). "The Factorial Function and Generalizations" (PDF). The American Mathematical Monthly. 107 (9): 783–799. doi:10.2307/2695734.