Bhargava factorial

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?

• 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.

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 (sequence A053657 in the OEIS).

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.

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

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})}}}$.