INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A02

ON THE NUMBER OF WAYS OF WRITING T AS A PRODUCT OF FACTORIALS

Daniel M. Kane

Received:10/6/04, Revised: 12/20/04, Accepted: 2/5/05, Published: 2/8/05

Abstract

Let ℕ_{0} denote the set of non-negative integers. In this paper we prove that

lim sup_{t→∞} |{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| = 6.

1. Introduction

Let ℕ_{0} denote the set of non-negative integers. In this paper we will prove that

lim sup_{t→∞} |{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| = 6.

We use three techniques to prove this result. First, it is not difficult to generate an infinite set of t each of which has at least 6 representations as a product of factorials thus establishing the lower bound. We then use considerations of the number of times two divides t in order to show that all of the solutions must be near each other. Lastly we use some analytic techniques analogous to those in [1].

The following three conjectures also seem likely.

Conjecture 1.

max |{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| = 6.

Conjecture 2.

lim sup_{t→∞} |{(n, m) ∈ ℕ^{2} : n!m! = t}| = 4.

Conjecture 3.

max |{(n, m) ∈ ℕ^{2} : n!m! = t}| = 4.

It is true that conjecture 3 would imply both other conjectures, and that any of these conjectures is stronger than our main theorem.

2. The lower bound

Notice that for any integer n > 2, we have that

(n!)! = 0! · (n!)! = 1! · (n!)! = n! · (n! − 1)! = (n! − 1)! · n! = (n!)! · 1! = (n!)! · 0!.

Therefore, we have that

lim sup_{t→∞} |{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| ≥ 6.

3. The first technique

For a positive integer n, let e(n) denote the largest k so that 2^{k} divides n. Notice that

e(n!) = ∑_{i=1}^{⌊log_{2}(n)⌋} ⌊\frac{n}{2^{i}} ⌋

= ∑_{i=1}^{⌊log_{2}(n)⌋} \frac{n}{2^{i}} − ∑_{i=1}^{⌊log_{2}(n)⌋} O(1)
= n + O(log n).

Therefore we have that if n!m! = t, then e(n!) + e(m!) = e(t), and therefore, n + m + O(log n + log m) = e(t). Since (n/2)^{n/2} < n! < t, we have that n < log t for sufficiently large t. Therefore, for sufficiently large t, n+m+O(log log t) = e(t). Hence if n_{1}!m_{1}! = n_{2}!m_{2}! = t, then n_{1} + m_{1} = n_{2} + m_{2} + O(log log t). This fact provides an elementary proof that for fixed t the number of solutions to n!m! = t is O(log log t) because by convexity of the log of the factorial function, at most two solutions to n!m! = t have a given sum of n + m, and this sum cannot vary by more than O(log log t).

4. The second technique

Our second technique is similar to that used in [1]. We begin with the following lemma:

Lemma 1. If F (x) : ℝ → ℝ is an infinitely differentiable function and if F (x) = 0 for x = x_{1}, x_{2}, ..., x_{n+1} (where x_{1} < x_{2} < ... < x_{n+1}), then F^{(n)}(y) = 0 for some y ∈ (x_{1}, x_{n+1}).

Proof. We proceed by induction on n. The case of n = 1 is Rolle’s Theorem. Given the statement of Lemma 2.1 for n − 1, if there exists such an F with n + 1 zeroes, x_{1} < x_{2} < ... < x_{n+1}, then by Rolle’s theorem, there exist points y_{i} ∈ (x_{i}, x_{i+1}) (1 ≤ i ≤ n) so that F′(y_{i}) = 0. Then since F′ has at least n roots, by the induction hypothesis there exists a y with x_{1} < y_{1} < y < y_{n} < x_{n+1}, and F^{(n)}(y) = (F′)^{(n−1)}(y) = 0.

We now state a lemma that helps us to count the number of integer points on smooth curves.

Lemma 2. Let f : ℝ → ℝ be a C^{k} function. Suppose that for x ∈ (a, b), that

0 < |\frac{1}{k!} \frac{∂^{k}}{∂x^{k}} f(x)| < α.

Then if we have a < x_{0} < x_{1} < ... < x_{k} < b where x_{i} ∈ ℤ and f(x_{i}) ∈ ℤ for all 0 ≤ i ≤ k, then x_{k} − x_{0} ≥ α^{\frac{−2}{k(k+1)}} .

Proof. Let

g(x) = ∑_{i=0}^{k} f(x_{i}) ∏_{\begin{matrix}0≤j≤k \\ i≠j \end{matrix}} \frac{x − x_{j}}{x_{i} − x_{j}}

be the polynomial of degree k that interpolates f at the x_{i}. Let h(x) = f(x) − g(x). Then h(x_{i}) = 0. Hence by Lemma 1 we have that for some a < x_{0} < y < x_{k} < b that \frac{∂^{k}}{∂x^{k}} h(y) = 0. Or that

(\frac{1}{k!} \frac{∂^{k}}{∂x^{k}} f(x))_{x=y} = (\frac{1}{k!} \frac{∂^{k}}{∂x^{k}} g(x))_{x=y} = ∑_{i=0}^{k} f(x_{i}) ∏_{\begin{matrix}0≤j≤k \\ j≠i \end{matrix}} \frac{1}{x_{i} − x_{j}} .

Therefore,

s = (\frac{1}{k!} \frac{∂^{k}}{∂x^{k}} f(x))_{x=y}

is an integer multiple of M = ∏_{0≤i<j≤k} \frac{1}{x_{j}−x_{i}}. Therefore, either s = 0 or else |s| ≥ M. But

by assumption, 0 < |s| < α. Therefore, α ≥ |s| ≥ M. Hence α ≥ (x_{k} − x_{0})^{\frac{−k(k+1)}{2}} , and hence we have that α^{\frac{−2}{k(k+1)}} ≤ x_{k} − x_{0} as desired.

We will also make use of a generalization of Stirling’s formula which states that:

log(Γ(z + 1)) = (z + \frac{1}{2}) log(z) − z + \frac{1}{2} log(2π) + O(z^{−1})

uniformly for ℜ(z) > 0. This follows readily from the m = 2 case of

log Γ(z + 1) = \frac{1}{2} log(2π) + (z + \frac{1}{2}) log(z) − z

+ ∑_{j=1}^{m} \frac{B_{2j}}{(2j − 1)(2j)z^{2j−1}} − \frac{1}{2m} ∫_{0}^{∞} \frac{B_{2m}(x − [x])}{(x + z)^{2m}}dx.

where B_{2j} and B_{2m} are the Bernoulli numbers and Bernoulli polynomials (see [2]).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A02 4

5. The Strategy

We have yet to prove that for sufficiently large t

|{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| ≤ 6.

It is sufficient to show that |{(n, m) ∈ ℕ_{0}^{2} : n ≥ m, n!m! = t}| ≤ 3 for all sufficiently large t. We will split solutions of this form into three overlapping cases:

1. m < exp(2\sqrt{log log t})

2. m > exp(\sqrt{log log t}), n − m > (log t)^{25/36}

3. n − m < (log t)^{26/36} Furthermore, we will show by our results from sections 3 and 4, that for all sufficiently

large t, that all integer solutions to n!m! = t lie in one of these regions.

Define the function f : ℝ → ℝ implicitly by Γ(f(x) + 1)Γ(x + 1) = t. It is clear that

f′(x) = −\frac{g(x)}{g(f(x))}

where

g(x) = \frac{∂}{∂x} log Γ(x + 1) = log(x) + O(x^{−1})

(by our strong form of Stirling’s formula). So

f′(x) = −\frac{log x + O(1)}{log(f(x))}.

So if we have two pairs of solutions (n_{1}, m_{1}), (n_{2}, m_{2}) to n ≥ m, n!m! = t, where m_{2} > m_{1}, then

O(log log t) > n_{2} + m_{2} − (n_{1} + m_{1}) = ∫_{m_{1}}^{m_{2}} 1 + f′(x)dx.

We need to show that if there are solutions with m too big for region 1, there are none with m too small for region 2, and that if there are solutions with m too small for region 3, there are none with m too big for region 2.

We can show the first of these by verifying that for sufficiently large t

∫_{exp(\sqrt{log log t})}^{exp(2\sqrt{log log t})} 1 + f′(x)dx > ∫_{exp(\sqrt{log log t})}^{exp(2\sqrt{log log t})} \frac{log t − 4\sqrt{log log t} + O(1)}{log t}dx
= exp(2\sqrt{log log t}) + O(1)
≫ log log t.

This shows that for sufficiently large t, it is impossible to have two solutions, one of which has m too small to be in region 2, and the other of which has m too large to be in region 1 since this would imply that n_{1} + m_{1} − (n_{2} + m_{2}) ≫ log log t.

Now if x_{1} and x_{2} are the numbers so that f(x_{2}) − x_{2} = (log t)^{25/36} and f(x_{1}) − x_{1} = (log t)^{26/36}, we notice that since the log of the gamma-function is convex that x_{2} − x_{1} > \frac{1}{3}(log t)^{26/36}. Thus we verify the second of these statements by noticing that

∫_{x_{1}}^{x_{2}} 1 + f′(x)dx > \frac{1}{3}(log t)^{26/36}(1 + f′(x_{2}))
> \frac{1}{3}(log t)^{26/36} \frac{log(f(x_{2})/x_{2}) + O(x_{2}^{−1})}{log(f(x_{2}))}
> Ω ((log t)^{26/36} \frac{(f(x_{2}) − x_{2})/x_{2}}{log(f(x_{2}))} )
= Ω (\frac{(log t)^{15/36}}{log log t} )
≫ log log t.

Recall that a(t) = Ω(b(t)) means that there exists a constant c > 0 so that for all sufficiently large t, a(t) > cb(t), and that a(t) = Θ(b(t)) means that there exist c_{1} > 0 and c_{2} > 0 so that for all sufficiently large t, c_{1}a(t) > b(t) > c_{2}a(t).

In section 6, we will cover the case where there are solutions in the first region. In section 7, we will cover the case where there are solutions in the second region. In section 8, we will cover the case where there are solutions in the third region.

6. The First Region

In this section, we will prove that for sufficiently large t, that there are at most 2 solutions to n!m! = t with 0 < m ≤ exp(\sqrt{log log t}).

Notice that

e (\frac{(n + x)!}{n!}) = e((n + x)!) − e(n!)
= ∑_{i=1}^{∞} ⌊\frac{n + x}{2^{i}}⌋ − ⌊\frac{n}{2^{i}} ⌋

= ∑_{i=1}^{⌊log x⌋} \frac{x}{2^{i}} + O(1) + max_{n<c≤n+x} e(c) − log x
= x + max_{n<c≤n+x} e(c) + O(log x).

Therefore, if we have any two such solutions, n_{1}!m_{1}! = n_{2}!m_{2}! = t, with n_{1} > n_{2} then e (\frac{n_{1}!}{n_{2}!}) = e (\frac{m_{2}!}{m_{1}!}). Therefore,

n_{1} − n_{2} + O(log(n_{1} − n_{2})) + max_{n_{1}<c≤n_{2}} e(c) ≥ m_{2} − m_{1} + O(log(m_{2} − m_{1})).

Which implies that

max_{n_{1}<c≤n_{2}} e(c) > (m_{2} − m_{1}) − (n_{1} − n_{2}) + O(log(m_{2} − m_{1})).

Notice that if n_{1}!m_{1}! = n_{2}!m_{2}!, then \frac{n_{1}!}{n_{2}!} = \frac{m_{2}!}{m_{1}!}, and therefore, m_{2} −m_{1} > (n_{1} −n_{2})· \frac{log n_{2}}{log m_{2}} . Now, n_{2} log n_{2} > log t − 2\sqrt{log log t} exp(2\sqrt{log log t}). Therefore, n_{2} = Ω(\frac{log t}{log log t}), so log n_{2} = Ω(log log t). Hence m_{2} − m_{1} = Ω(\sqrt{log log t})(n_{1} − n_{2}). Therefore, we have that

max_{n_{1}<c≤n_{2}} e(c) > (m_{2} − m_{1})(1 + O((log log t)^{−1/2})) + O(log(m_{2} − m_{1}))
= Ω(m_{2} − m_{1})
= Ω(\sqrt{log log t}).

Therefore, if we have three solutions in region 1, (n_{1}, m_{1}), (n_{2}, m_{2}), (n_{3}, m_{3}) with 0 < m_{1} < m_{2} < m_{3}, then we have that there exist n_{3} < c_{1} ≤ n_{2} < c_{2} ≤ n_{1} with e(c_{i}) = Ω(\sqrt{log log t}). Therefore, since min(e(x), e(y)) ≤ e(x − y), we have that e(c_{2} − c_{1}) = Ω(\sqrt{log log t}). Therefore, n_{1} − n_{3} > c_{2} − c_{1} > exp(Ω(\sqrt{log log t})). But we notice that this and previous inequalities imply that

m_{3} + n_{3} − (m_{1} + n_{1}) = Ω(\sqrt{log log t}) exp(Ω(\sqrt{log log t})).

Since this cannot be O(log log t), we have that for sufficiently large t, there are at most 2 solutions with m ≠ 0 in region 1. Hence there are at most 3 solutions in region 1.

7. The Second Region

In this section we will show that there are at most 2 solutions with m > exp(\sqrt{log log t}) and n − m > (log t)^{25/36}. Recall that f : ℝ → ℝ so that Γ(f(x) + 1)Γ(x + 1) = t. This is defined in the range we are interested in, because the gamma-function is increasing. Let g(x) = log Γ(x + 1). So g(f(x)) + g(x) = log t. Differentiating implicitly, we get that

f′(x) = −\frac{g′(x)}{g′(f(x))}.

Therefore,

f′′(x) = −\frac{g′′(x)}{g′(f(x))} + f′(x)\frac{g′(x)g′′(f(x))}{(g′(f(x)))^{2}}
= −\frac{g′′(x)(g′(f(x)))^{2} + (g′(x))^{2}g′′(f(x))}{(g′(f(x)))^{3}}.

By differentiating our strong form of Stirling’s formula, we find that for f(x) > x

f′′(x) = −\frac{(log f(x))^{2}x^{−1} + (log x)^{2}(f(x))^{−1}(1 + O(x^{−1}))}{((log f(x)) + O(f(x)^{−1}))^{3}}.

Therefore, for all sufficiently large t, for x > exp(\sqrt{log log t}) and f(x) − x > (log t)^{25/36} we have that

0 < |\frac{1}{2}f′′(x)| < O (\frac{1}{x(log f(x))}) .

Assume for sake of contradiction that we have three solutions to n!m! = t in region 2 (n_{i}!m_{i}! = t for 1 ≤ i ≤ 3 where m_{i} < m_{i+1}). Then we have that m_{i} is an integer and that f(m_{i}) is an integer. Since between m_{1} and m_{3} we have that

0 < |\frac{1}{2}f′′(x)| < O (\frac{1}{m_{1}} ) .

Therefore, by Lemma 2, m_{3} − m_{1} > Ω(m_{1}^{1/3}). But we also have that (m_{3} + n_{3}) − (m_{1} + n_{1}) = O(log log t). Therefore

∫_{m_{1}}^{m_{1}+Ω(m_{1}^{1/3})} \frac{(log f(x)) − log x}{log f(x)}dx = O(log log t).

Now we have that for x in the range we are concerned with that

\frac{(log f(x)) − log x}{log f(x)} = Ω (\frac{(f(x) − x)/x}{log f(x)}) = Ω((log t)^{−11/36}).

Therefore, it must be that m_{1} = O((log log t)^{3}(log t)^{11/12}). But in this range, the integrand we are concerned with is at least \frac{1}{12} + o(1). Therefore, it must be that m_{1} = O((log log t)^{3}) which does not hold. Therefore, for sufficiently large t, there are at most 2 solutions in region 2.

8. Region Three

In this section we will show that there are at most 3 solutions in region 3 for sufficiently large t. This proof depends on the fact that if n and m are integers, then so are n + m and (n − m)^{2} and applications of Lemma 2 and results from section 3.

Suppose that Γ((a + \sqrt{x} + 2)/2)Γ((a − \sqrt{x} + 2)/2) = t, where x = O(a^{3/2}). Then we have by our strong form of Stirling’s formula that

log t = \frac{a + \sqrt{x} + 1}{2} log (\frac{a + \sqrt{x}}{2}) + \frac{a − \sqrt{x} + 1}{2} log (\frac{a − \sqrt{x}}{2})

−a + log 2π + O(a^{−1})

= (a + 1) log(a/2) − a + log(2π)

+\frac{a + \sqrt{x} + 1}{2} log (1 + \frac{\sqrt{x}}{a}) + \frac{a − \sqrt{x} + 1}{2} log (1 − \frac{\sqrt{x}}{a}) + O(a^{−1})

= (a + 1) log(a/2) − a + log(2π) + \frac{x}{a} + O(a^{−1}).

Therefore, we have that

x = a log (\frac{t}{2π} ) − a(a + 1) log (\frac{a}{2}) + a^{2} + O(1).

Let a_{0} be the positive real value so that (Γ((a_{0}/2) + 1))^{2} = t. So then we have that

a_{0} log (\frac{t}{2π} ) − a_{0}(a_{0} + 1) log (\frac{a_{0}}{2} ) + a_{0}^{2} = O(1).

It is also true that a_{0} = O(log t). If we pick an a so that

a log (\frac{t}{2π} ) − a(a + 1) log (\frac{a}{2}) + a^{2} + O(1) < (log t)^{16/11}.

Then there must be a unique complex x with |x| ≤ (log t)^{16/11} so that Γ((a+\sqrt{x}+2)/2)Γ((a− \sqrt{x} + 2)/2) = t. Since the derivative of

a log (\frac{t}{2π} ) − a(a + 1) log (\frac{a}{2}) + a^{2}

is

log (\frac{t}{2π} ) − (2a + 1) log (\frac{a}{2}) + a − 1

and since its second derivative is O(log a), this should hold as long as |a−a_{0}| < O((log t)^{9/20}). Furthermore, for a in this range, x attains all values with |x| ≤ (log t)^{13/9}. This allows use to define an analytic function h(a) defined on |a − a_{0}| < O((log t)^{29/20}) so that

Γ (\frac{a + \sqrt{h(a)}}{2} + 1) Γ (\frac{a − \sqrt{h(a)}}{2} + 1) = t.

Furthermore, h(a) attains all values of absolute value at most (log t)^{13/9} when |a − a_{0}| = O(log t)^{5/9}. Additionally, we have that

h(a) = a log (\frac{t}{2π} ) − a(a + 1) log (\frac{a}{2}) + a^{2} + O(1).

Since the O(1) is uniform in the region stated, its third derivative when |a−a_{0}| = O(log t)^{13/29} (notice that 4/9 < 13/29 < 9/20) can be written using Cauchy’s Integral formula as

∫_{C} O((z − a)^{−4})dz,

where C is a contour that traverses a circle centered at a of radius Ω((log t)^{9/20}) once in the counter-clockwise direction. This is O((log t)^{−27/20}). Therefore, when |h(a)| < (log t)^{13/9} we have that

h′′′(a) = \frac{∂^{3}}{∂a^{3}} (a log (\frac{t}{2π} ) − a(a + 1) log (\frac{a}{2}) + a^{2}) + O((log t)^{−27/20})
= −\frac{1}{a} + O((log t)^{−27/20}).

Since it is clear by Stirling’s formula that a_{0} = Θ (\frac{log t}{log log t}) we have that for sufficiently large

t, when |h(a)| ≤ (log t)^{13/9} then 0 < |h′′′(a)| < O (\frac{log log t}{log t}).

Now suppose for sake of contradiction that (n_{i}, m_{i}) are distinct region 3 solutions for 1 ≤ i ≤ 4. Then n_{i} + m_{i} ∈ ℤ and h(n_{i} + m_{i}) = (n_{i} − m_{i})^{2} ∈ ℤ. Furthermore, |h(n_{i} + m_{i})| ≤ (log t)^{13/9}. Then since in the range between the n_{i} + m_{i} we have that 0 < |h′′′(a)| < O (\frac{log log t}{log t}), Lemma 2 implies that the difference between the largest and smallest of the n_{i} + m_{i} is at least

Ω ((\frac{log t}{log log t})^{1/6}) .

Since this is larger than O(log log t), we have from results in section 3, that for sufficiently large t, this is impossible.

Hence there are at most three solutions in region 3 for sufficiently large t.

9. Conclusions

Hence we have proved our result that

lim sup_{t→∞} |{(n, m) ∈ ℕ_{0}^{2} : n!m! = t}| = 6.

Notice that all of our statements about there being at most 6 solutions for “sufficiently large t” can be made effective, although this was not done in this paper. I do not believe that the effective bound that is achieved would be small enough to allow for a reasonable proof that there are at most 6 solutions for any t, at least without further insight.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A02 10

References

[1] D. Kane, New bounds on the number of representations of t as a binomial coefficient, Integers 4 (2004).

[2] Hans Rademacher, Topics in Analytic Number Theory Springer-Verlag, Berlin-Heidelberg-New York