NEW BOUNDS ON THE NUMBER OF REPRESENTATIONS OF T AS A BINOMIAL COEFFICIENT

Daniel Kane Random Hall, 290 Massachusetts Avenue, Cambridge MA 02139

                                dankane@mit.edu

Received: 6/2/03, Revised: 4/24/04, Accepted: 5/4/04, Published: 5/5/04

Abstract

For t > 1, let N(t) denote the number of ways that t can be written as a binomial coefficient. We prove that N(t) = O (\frac{log t·log log log t}{(log log t)^{2}}).

1. Introduction and statement of results

If t > 1, then let N(t) denote the number of ways that t can be written as a binomial coefficient. Abbot, Erdős, and Hanson show in [1] that

N(t) = O (\frac{log t}{log log t}) .

They also note that if Cramer’s conjecture is true (i.e. if for some x_{0} and all x > x_{0} there is always a prime number between x and x + log^{2} x), then this bound can be improved to

N(t) = O ((log t)^{(2/3+ϵ)})

for any ϵ > 0. It has also been conjectured by D. Singrester that N(t) = O(1).

We improve on the first of these bounds by proving the following theorem.

Theorem 1. With N(t) defined above,

N(t) = O (\frac{log t · log log log t}{(log log t)^{2}}) .

Typeset by AMS-TEX

2 INTEGERS: ELECTRONIC J. OF COMBINATORIAL NUMBER THEORY 4 (2004), #A07

2. Preliminary Lemmas

Here are several important facts that we shall be using. If Γ(z) denotes the Euler gammafunction, then

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

This holds uniformly in the region of the complex plane where ℜ(z) > 1. This follows readily from the m = 2 case of (see [2])

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.

Also note that since

N(t) = |\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} )\}| ,

we have by the symmetry of Pascal’s triangle that

(2.2)  N(t) ≤ 2 |\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} ) , 2m ≤ n\}| .

Lemma 2.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 of Lemma 2.1. 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. □

If we let F (x) equal f(x) − p(x) where p(x) is a degree n polynomial, we get that

Corollary 2.1. If f(x) is an infinitely differentiable function and if p(x) is a polynomial of degree n so that f(x) = p(x) for x = x_{1}, x_{2}, ..., x_{n+1} where x_{1} < x_{2} < ... < x_{n+1}, then there exists a y ∈ (x_{1}, x_{n+1}) so that f^{(n)}(y) = p^{(n)}(y).

3. Approximation of the terms in binomial coefficients equal to t

Suppose that for n ≥ 2m

( \begin{matrix}n \\ m \end{matrix} ) = t.

INTEGERS: ELECTRONIC J. OF COMBINATORIAL NUMBER THEORY 4 (2004), #A07 3

We can take logs of both sides, and then we have by (2.1) that log t + log(m!) = log(n!) − log((n − m)!)

= (n + \frac{1}{2}) log(n) − n + \frac{1}{12n} − (n − m + \frac{1}{2}) log(n − m) + (n − m) − \frac{1}{12(n − m)} + O (\frac{1}{n^{3}} )

= m log(n) − (n − m + \frac{1}{2}) log (1 − \frac{m}{n}) − m + O (\frac{m}{n^{2}} )

= m log(n) + (n − m + \frac{1}{2}) (\frac{m}{n} + \frac{m^{2}}{2n^{2}} ) − m + O (\frac{m^{3}}{n^{2}} )

= m log(n) + \frac{m}{n} (\frac{−m + 1}{2}) + O (\frac{m^{3}}{n^{2}} )

= m log(n − (m − 1)/2) + O (\frac{m^{3}}{n^{2}} ) .

Hence we have that

log(n − (m − 1)/2) = \frac{log t + log(m!)}{m} + O (\frac{m^{2}}{n^{2}} ) .

So,

n = exp (\frac{log t + log(m!)}{m}) (1 + O (\frac{m^{2}}{n^{2}} )) + \frac{m − 1}{2}
(3.1)  = exp (\frac{log t + log(m!)}{m}) + \frac{m − 1}{2} + O (\frac{m^{2}}{n} ) .

Notice that if we define

( \begin{matrix}n \\ m \end{matrix} ) = \frac{Γ(n + 1)}{Γ(m + 1)Γ(n − m + 1)}

we can use this to define an analytic function f(z) by

(3.2)  ( \begin{matrix}f(z) \\ z \end{matrix} ) = t

that satisfies

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

uniformly, so long as |f(z)| > |2z|. This will hold when

|exp (\frac{log t + log Γ(z + 1)}{z})| > |6z|.

By (2.1), this holds when ℜ(z) > 1 and

|exp (\frac{log t}{z})| > C,

for some constant C. This clearly holds if |ℑ(log z)| < π/4 and if |z| < K log t for some constant K.

Suppose that for log log t > α > 1.2

( \begin{matrix}m^{α} \\ m \end{matrix} ) = t.

We have by (3.1) and (2.1) that

m^{α} = exp (\frac{log t}{m}) \frac{m}{e}(1 + O(log m/m)) + \frac{m − 1}{2} + O(m^{2−α}).

So, we get that

(α − 1)m log m = log(t) + O(m).

Or that

m log m = \frac{log t}{α − 1} + O(m).

Hence for sufficiently large t

(3.3)  \frac{log t}{log log t(α − 1)} < m < (\frac{log t}{log log t(α − 1)}) (1 + \frac{1}{log log t}) .

4. Approximations of the derivatives of f(z)

We wish to find bounds for

\frac{1}{k!} \frac{d^{k}}{dx^{k}} f(x)

where k ≥ 2 is an integer and for f(x) as defined in (3.2) and x real, less than K log t/2, and more than 2. Notice that as a complex analytic function,

\frac{z^{2}}{f(z)} = O (z exp (\frac{− log t}{z})) .

Hence, by Cauchy’s Integral Formula we have

\frac{1}{k!} \frac{d^{k}}{dx^{k}} \frac{x^{2}}{f(x)} = ∫_{C} O (w exp (\frac{− log t}{w}) (w − x)^{−k−1}) dw.

Here C denotes the contour consisting of the circle of radius x/3 centered at x traversed once in the counterclockwise direction. Notice that on this contour,

ℜ (\frac{1}{w} ) ≥ \frac{3}{4x}.

Therefore, the integral is

O(x^{1−k}3^{k}t^{−3/4x}) = O(x^{2−k}3^{k}f(x)^{−3/4}).

It is clear that

\frac{d^{k}}{dx^{k}} \frac{x − 1}{2} = 0.

Notice that by (2.1)

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

holds for complex z. This means that, by Cauchy’s Integral Formula

\frac{1}{k!} \frac{d^{k}}{dx^{k}} \frac{log Γ(x + 1)}{x} = \frac{(−1)^{k+1}}{kx^{k}} + ∫_{C} O (\frac{log w}{w(w − x)^{k+1}} ) dw,

where C is the circle about x through 1. This is then

\frac{(−1)^{k+1}}{kx^{k}} + O((log^{2} x)(x^{−k−1})).

Therefore,

\frac{1}{k!} \frac{d^{k}}{dx^{k}} \frac{log t + log Γ(x + 1)}{x} = \frac{(−1)^{k}}{x^{k+1}} (log t + O(log^{2} x + x/k)).

This has the same sign as (−1)^{k} as long as x < k log t, which will hold in the case we are considering where x < K log t/2 and k ≥ 1. We now wish to analyze the kth derivative with respect to x of

g(x) = exp (\frac{log t + log Γ(x + 1)}{x}) .

Using our previous result, and expanding a Taylor series we find that

g(y) =

exp (\frac{log t + log Γ(y + 1)}{y}) =

exp (\frac{log t + log Γ(x + 1)}{x}) exp(a_{1}(y − x) − a_{2}(y − x)^{2} + ... + O((y − x)^{k+1}))

where a_{i} = \frac{−1}{x^{k+1}} (log t + O(log^{2} x + x/k)) < 0. This means that the coefficients of the Taylor series about 0 of g(x − y) are all positive. Therefore, \frac{d^{k}}{dy^{k}} g(y) has the same sign as (−1)^{k}. Furthermore, the absolute values of these coefficients is at least

exp (\frac{log t + log Γ(x + 1)}{x}) \frac{|a_{1}|^{k}}{k!} =

(f(x) + O(x)) (\frac{log t + O(x/k)}{x^{2}})^{k} \frac{1}{k!} >

\frac{f(x) + O(x)}{x^{k}k!}.

To find an upper bound on the absolute value of the kth coefficient, we note that if we write

exp (\frac{log t + log Γ(x + 1)}{y}) =

exp (\frac{log t + log Γ(x + 1)}{x}) exp(b_{1}(y − x) − b_{2}(y − x)^{2} + ... + O((y − x)^{k+1}))

then b_{i} and a_{i} will have the same sign, but |a_{i}| < |b_{i}|. Therefore, we know that the kth coefficient of the Taylor series for g(y) at x is at most

|\frac{1}{k!} \frac{d^{k}}{dy^{k}} exp (\frac{log t + log Γ(x + 1)}{y})|_{y=x} .

Using Cauchy’s Integral Formula, we find that

|\frac{1}{k!} \frac{d^{k}}{dx^{k}} exp (\frac{c}{x})| = |\frac{1}{2πi} ∫_{C} exp (\frac{c}{w} ) (w − x)^{−k−1}dw| ,

where C is the contour that traverses the circle about x with radius \frac{x}{log(x)} once counter clockwise. The right hand side of the preceding equation is at most

exp (\frac{c}{x} (1 + O (\frac{1}{log(x)}))) (\frac{x}{log(x)})^{−k} .

Hence we have that for large x,

|\frac{1}{k!} \frac{d^{k}}{dx^{k}} g(x)| <

exp (\frac{log t + log Γ(x + 1)}{x})^{1+2/(log x)} x^{−k}(log x)^{k} <

f(x)^{1+2/ log(x)}x^{−k}(log x)^{k}.

Hence, we have that if

f(x)^{7/4} > x^{2}3^{k+1}k!,

then we have that

(4.1)  0 < |\frac{1}{k!} \frac{d^{k}}{dx^{k}} f(x)| < 2f(x)e^{2 \frac{log f(x)}{log x}} x^{−k}(log x)^{k}

5. The Strategy

Let

A(t) = |\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} ) , 2m < n < m^{6/5}\}|
B(t) = |\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} ) , m^{6/5} < n < m^{\frac{log log(t)}{24 log log log(t)}} \}|
C(t) = |\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} ) , m^{\frac{log log(t)}{24 log log log(t)}} < n\}| .

INTEGERS: ELECTRONIC J. OF COMBINATORIAL NUMBER THEORY 4 (2004), #A07 7

It is clear that

(5.1)  N(t) = 2A(t) + 2B(t) + 2C(t) + O(1).

We now have to prove that

A(t), B(t), C(t) ≤ O (\frac{log t · log log log t}{(log log t)^{2}}) .

6. Bounds on A(t)

It is clear that if 2m < n < m^{6/5} and

t = ( \begin{matrix}n \\ m \end{matrix} ) ,

then by (3.3) n < (log(t))^{6/5} and from the proof of theorem 3 in [1] (pg. 258) ,

(6.1)  A(t) ≤ (log(t))^{3/4} = O (\frac{log t · log log log t}{(log log t)^{2}}) .

7. Bounds on B(t)

Let

k = \frac{log log t}{12 log log log t}.

Here we shall consider real x so that x^{\frac{log log t}{24 log log log t}} > f(x) > x^{6/5}. Notice that log_{x} f(x) is a decreasing function of x by (3.3). Notice also that f(x)^{7/4}x^{−2} is also a decreasing function of x by (3.2). Therefore, in this range, f(x)^{7/4}x^{−2} is minimal when f(x) = x^{6/5}. In this case, we have that f(x)^{7/4}x^{−2} is x^{1/10}, and by (3.3), this is at least

(log t)^{1/10}(log log t)^{−1/10}.

Whereas we have that,

3^{k}k! < exp(k log k + k) < exp (\frac{1}{12} (log log t) (1 + \frac{1}{log log log t})) < f(x)^{7/4}x^{−2} for all sufficiently large t.

Additionally, we have by (3.3) that x < (\frac{5 log t}{log log t}) (1 + \frac{1}{log log t}) < \frac{K log t}{2} for sufficiently large t. Hence for sufficiently large t, and x in this range, the conditions of (4.1) are satisfied.

Therefore, by (4.1)

0 < |\frac{1}{k!} \frac{d^{k}}{dx^{k}} f(x)|
<2f(x)e^{2 \frac{log f(x)}{log x}} x^{−k}(log x)^{k}
<2x^{k/2}e^{k}x^{−k}(log x)^{k}
<2e^{k}x^{−k/2}(log x)^{k}
<2e^{k} (\frac{log t}{k log log t})^{−k/2} (log log t)^{k}
<2(log t)^{−k/2}(e log log t)^{2k}
(7.1)  <(log t)^{−(k+1)/3}

for all sufficiently large t.

Suppose that m_{1} < m_{2} < ... < m_{k+1} are integers and that f(m_{i}) is also an integer for all 1 ≤ i ≤ k + 1. Then if we define the polynomial

P (x) = ∑_{i=1}^{k+1} \frac{f(m_{i}) ∏_{1≤j≤k+1}^{i≠j}(x − m_{j})}{∏_{1≤j≤k+1}^{i≠j}(m_{i} − m_{j})},

Then P is of degree k, and P (m_{i}) = f(m_{i}) for all 1 ≤ i ≤ k + 1. We also have that

\frac{1}{k!} \frac{d^{k}}{dx^{k}} P (x) = ∑_{i=1}^{k+1} \frac{f(m_{i})}{∏_{1≤j≤k+1}^{i≠j}(m_{i} − m_{j})}.

This is an integer multiple of

M = ( ∏_{1≤i<j≤k+1}(m_{j} − m_{i}))^{−1} > (m_{k+1} − m_{1})^{−k(k+1)/2}.

Therefore if

\frac{1}{k!} \frac{d^{k}}{dx^{k}} P (x) ≠ 0,

then

(7.2)  |\frac{1}{k!} \frac{d^{k}}{dx^{k}} P (x)| > (m_{k+1} − m_{1})^{−k(k+1)/2}.

Hence, if f(m_{i}) > m_{i}^{6/5} and f(m_{i}) < m_{i}^{k/2} for all i, we have by the corollary to Lemma 2.1, (7.1) and (7.2) that

(m_{k+1} − m_{1})^{−k(k+1)/2} < (log t)^{−(k+1)/3},

INTEGERS: ELECTRONIC J. OF COMBINATORIAL NUMBER THEORY 4 (2004), #A07 9

or that

m_{k+1} − m_{1} >(log t)^{1/3k}
=(log t)^{\frac{4 log log log t}{log log t}}
(7.3)  =(log log t)^{4}.

Let m_{1} < m_{2} < ... < m_{B(t)} be all of the integers so that for all i, f(m_{i}) is an integer where m_{i}^{k/2} > f(m_{i}) > m_{i}^{6/5}. It is clear that 0 < m_{1} < m_{B(t)} < log t. Therefore,

∑_{i=1}^{[B(t)/(k+1)]}(m_{(k+1)i} − m_{(k+1)(i−1)+1}) < log(t).

Therefore, by (7.3)

∑_{i=1}^{[B(t)/(k+1)]}(log log t)^{4} < log(t).

Or, [B(t)/(k + 1)] < (log t)(log log t)^{−4}. Therefore,

(7.4)  B(t) < k + (k + 1)(log t)(log log t)^{−4} < \frac{log t}{(log log t)^{3}} = O (\frac{log t · log log log t}{(log log t)^{2}}) .

8. Bounds on C(t)

We have by (3.3) that if f(x) > x^{\frac{log log t}{24 log log log t}} that

x = O (\frac{log t · log log log t}{(log log t)^{2}}) .

Therefore the largest m appearing in an element of

\{(n, m) ∈ ℕ^{2} : t = ( \begin{matrix}n \\ m \end{matrix} ) , m^{\frac{log log(t)}{24 log log log(t)}} < n\}

is

O (\frac{log t · log log log t}{(log log t)^{2}}) .

Which implies that

(8.1)  C(t) = O (\frac{log t · log log log t}{(log log t)^{2}}) .

Our result that

N(t) = O (\frac{log t · log log log t}{(log log t)^{2}})

now follows from (5.1), (6.1), (7.4) and (8.1).

Remark. This process can be done without the use of complex analysis except for the possible exception of the bounding of the derivatives of log Γ(x + 1)/x. This is done by claiming that solutions to t = ( \begin{matrix}n \\ m \end{matrix} ) correspond to points near the curve f(x) = (t · x!)^{1/x} + (x − 1)/2. This method requires that there be better bounds on the number of points where n and m are closer to each other (we would need bounds for solutions where n < m^{2}), but this can be provided by looking at the greatest common divisors of products of nearby sequences of integers.

References

[1] Abbot, H. L.; Erdös, P.; Hanson, D., On the Number of Times an Integer Occurs as a Binomial Coefficient, Amer. Math. Monthly 81 (1974), 256-261.

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