Bhargava factorial

From HandWiki
Short description: Generalization of the mathematical 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 [math]\displaystyle{ \mathbb{Z} }[/math] 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 = [math]\displaystyle{ \mathbb{Z} }[/math] itself, then the integer associated with k, that is k ![math]\displaystyle{ \mathbb{Z} }[/math] , 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 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 a0, a1, a2, ... , an be any n + 1 integers. Then the product of their pairwise differences is a multiple of 0! 1! ... n!.
  4. Let [math]\displaystyle{ \mathbb{Z} }[/math] be the set of integers and n any integer. Then the number of polynomial functions from the ring of integers [math]\displaystyle{ \mathbb{Z} }[/math] to the quotient ring [math]\displaystyle{ \mathbb{Z}/n\mathbb{Z} }[/math] is given by [math]\displaystyle{ \prod_{k=0}^{n-1} \frac{n}{\gcd(n,k!)} }[/math].

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 [math]\displaystyle{ \mathbb{Z} }[/math], 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 {a0, a1, a2, ... } of numbers chosen from S as follows (such a sequence is called a p-ordering of S):
  1. a0 is any arbitrary element of S.
  2. a1 is any arbitrary element of S such that the highest power of p that divides a1 − a0 is minimum.
  3. a2 is any arbitrary element of S such that the highest power of p that divides (a2 − a0)(a2 − a1) is minimum.
  4. a3 is any arbitrary element of S such that the highest power of p that divides (a3 − a0)(a3 − a1)(a3 − a2) 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 vk(S, p) be the highest power of p that divides (ak − a0)(ak − a1)(ak − a2) ... (ak − ak − 1). The sequence {v0(S, p), v1(S, p), v2(S, p), v3(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 v0(S, p) = 1 always.)
  • The factorial of the integer k, associated with the infinite set S, is defined as [math]\displaystyle{ k!_{S}=\prod_p v_k(S,p) }[/math], 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 a0 = 19 arbitrarily from P.
  • To choose a1:
  • The highest power of p that divides 2 − a0 = −17 is 20 = 1. Also, for any a ≠ 2 in P, a − a0 is divisible by 2. Hence, the highest power of p that divides (a1 − a0) is minimum when a1 = 2 and the minimum power is 1. Thus a1 is chosen as 2 and v1(P, 2) = 1.
  • To choose a2:
  • It can be seen that for each element a in P, the product x = (a − a0)(a − a1) = (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, a2 may be chosen as 5. We have v2(P, 2) = 2.
  • To choose a3:
  • It can be seen that for each element a in P, the product x = (a − a0)(a − a1)(a − a2) = (a − 19)(a − 2)(a − 5) is divisible by 23 = 8. Also, when a = 17, x is divisible by 8 and it is not divisible by any higher power of 2. Choose a3 = 17. Also we have v3(P,2) = 8.
  • To choose a4:
  • It can be seen that for each element a in P, the product x = (a − a0)(a − a1)(a − a2)(a − a3) = (a − 19)(a − 2)(a − 5)(a − 17) is divisible by 24 = 16. Also, when a = 23, x is divisible 16 and it is not divisible by any higher power of 2. Choose a4 = 23. Also we have v4(P,2) = 16.
  • To choose a5:
  • It can be seen that for each element a in P, the product x = (a − a0)(a − a1)(a − a2)(a − a3)(a − a4) = (a − 19)(a − 2)(a − 5)(a − 17)(a − 23) is divisible by 27 = 128. Also, when a = 31, x is divisible 128 and it is not divisible by any higher power of 2. Choose a5 = 31. Also we have v5(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 v0(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).

Table of values of vk(P, p) and k!P

p
k
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 natural numbers [math]\displaystyle{ \mathbb{Z} }[/math].

  • 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![math]\displaystyle{ \mathbb{Z} }[/math] = 1×1×1×1×1×... = 1.
  • 1![math]\displaystyle{ \mathbb{Z} }[/math] = 1×1×1×1×1×... = 1.
  • 2![math]\displaystyle{ \mathbb{Z} }[/math] = 2×1×1×1×1×... = 2.
  • 3![math]\displaystyle{ \mathbb{Z} }[/math] = 2×3×1×1×1×... = 6.
  • 4![math]\displaystyle{ \mathbb{Z} }[/math] = 8×3×1×1×1×... = 24.
  • 5![math]\displaystyle{ \mathbb{Z} }[/math] = 8×3×5×1×1×... = 120.
  • 6![math]\displaystyle{ \mathbb{Z} }[/math] = 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 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

References