A JOINT CENTRAL LIMIT THEOREM FOR THE SUM-OF-DIGITS

FUNCTION, AND ASYMPTOTIC DIVISIBILITY OF CATALAN-LIKE SEQUENCES

MICHAEL DRMOTA^{∗} AND CHRISTIAN KRATTENTHALER^{†}

∗Institute of Discrete Mathematics and Geometry, TU Wien, Wiedner Hauptstraße 8–10, A-1040 Vienna, Austria.

                     WWW: https://www.dmg.tuwien.ac.at/drmota

†Fakultät für Mathematik der Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

                     WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We prove a central limit theorem for the joint distribution of s_{q}(A_{j}n), 1 ≤ j ≤ d, where s_{q} denotes the sum-of-digits function in base q and the A_{j}’s are positive integers relatively prime to q. We do this in fact within the framework of quasi-additive functions. As application, we show that most elements of “Catalanlike” sequences — by which we mean integer sequences defined by products/quotients of factorials — are divisible by any given positive integer.

1. Introduction

In [5], Burns shows that most of the ubiquitous Catalan numbers C_{n} := \frac{1}{n+1} \binom{2n}{n} (cf. [17, Ex. 6.19]) are divisible by p, where p is some given prime number. Let v_{p}(N) denote the p-adic valuation of the integer N, which by definition is the maximal exponent α such that p^{α} divides N. In view of Legendre’s formula [10, p. 10] for the p-adic valuation of factorials,

v_{p}(n!) = \frac{1}{p − 1}(n − s_{p}(n)),  (1.1)

where s_{p}(N) denotes the p-ary sum-of-digits function

s_{p}(N) = ∑_{j≥0} ε_{j}(N),

with ε_{j}(N) denoting the j-th digit in the p-adic representation of N, we have

v_{p} (\frac{1}{n + 1}\binom{2n}{n}) = \frac{1}{p − 1}(2s_{p}(n) − s_{p}(2n)) − v_{p}(n + 1).

Thus, one sees that the above and many more asymptotic divisibility results — such as the divisibility of most of the Catalan numbers, or even of most of the Fuß–Catalan numbers (cf. [1, pp. 59–60]) by any given prime power — can be proved if one has sufficiently precise results on the distribution of the vector

2010 Mathematics Subject Classification. Primary 11K65; Secondary 05A15 11A63 11N60 60F05.

Key words and phrases. Sum-of-digits function, quasi-additive functions, central limit theorem, Catalan numbers, central binomial coefficients.

∗† Research partially supported by the Austrian Science Foundation FWF, in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”, project F50-N15.

(s_{p}(A_{1}n), s_{p}(A_{2}n), …, s_{p}(A_{d}n)),  n < N.  (1.2)

Indeed, for p = 2, Schmidt [14] and Schmid [13] showed that for pairwise different positive odd integers A_{1}, A_{2}, …, A_{d} the vector (1.2) satisfies a d-dimensional central limit theorem with asymptotic mean vector (1/2, …, 1/2)·log_{2} N and asymptotic covariance matrix Σ · log_{2} N with

Σ = (\frac{gcd(A_{i}, A_{j})^{2}}{4A_{i}A_{j}} )_{1≤i,j≤d} .

We want to mention that the distribution of the vector (1.2) in residue classes was intensively studied in [6]. Furthermore we also emphasize that many results on divisiblity properties of non-central binomial coefficients are available, too, see for example [16].

The first goal of the present paper is to generalize the central limit theorem by Schmidt [14] and Schmid [13] to arbitrary primes p, and even to arbitrary bases q. We do this in Theorem 1 in Section 2, by using an even more general concept, namely the concept of q-quasi-additive functions.

We then apply this result in Section 3 (see Theorem 4 and Corollary 5) to prove the somewhat non-intuitive fact that most elements of any sequence (S(n))_{n≥0} of integers given by a (non-trivial) formula

\frac{P (n)}{Q(n)} \frac{∏_{i=1}^{r}(C_{i}n)!}{∏_{i=1}^{s}(D_{i}n)!}

are divisible by any given prime power, and thus by any given positive integer. Here, P (n) and Q(n) are polynomials in n over the integers, where Q(n) is a product of linear factors, and the C_{i}’s and D_{i}’s are positive integers with ∑_{i=1}^{r} C_{i} = ∑_{i=1}^{s} D_{i}. The attribute “non-trivial” means that the set of C_{i}’s is different from the set of D_{i}’s. As is pointed out in more detail in Section 3, numerous (mainly combinatorial) sequences that appear in the literature in various contexts are of this form.

2. A central limit theorem

Let q ≥ 2 be a given integer. It is well known that the sum-of-digits function s_{q}(n) satisfies a central limit theorem of the form

\frac{1}{N} # \{n < N : s_{q}(n) ≤ μ_{q} log_{q} N + t\sqrt{σ_{q}^{2} log_{q} N}\} = Φ(t) + o(1),  (2.1)

uniformly in t, where μ_{q} = (q−1)/2, σ_{q}^{2} = (q^{2}−1)/12, and Φ(t) denotes the distribution function of the standard Gaußian distribution. This result is easy to prove since the digits ε_{j}(n), 0 ≤ j < log_{q}(N), behave almost as i.i.d. random variables if n varies between 0 and N − 1. Actually much more is known (see for example [2]). Suppose that P (x) is a polynomial of degree D ≥ 1 with non-negative integer coefficients. Then we also have

\frac{1}{N} # \{n < N : s_{q}(P (n)) ≤ μ_{q} log_{q} P (N) + t\sqrt{σ_{q}^{2} log_{q} P (N)}\} = Φ(t) + o(1).

Note that the value P (N) can be replaced by N^{D} without changing the validity of the statement.

This result applies in particular to linear polynomials P_{j}(n) = A_{j}n (with integers A_{j} ≥ 1). In what follows, we will consider linear combinations of the form

f(n) = c_{1}s_{q}(A_{1}n) + c_{2}s_{q}(A_{2}n) + ⋯ + c_{d}s_{q}(A_{d}n),  n < N,  (2.2)

with real numbers c_{j} and integers A_{j} ≥ 1, 1 ≤ j ≤ d. Clearly, the central limit result of Schmidt [14] and Schmid [13] mentioned in the introduction is equivalent to the fact that f(n) as in (2.2) with q = 2, n < N, satisfies a one-dimensional central limit theorem with asymptotic mean \frac{1}{2}(c_{1} + c_{2} + ⋯ + c_{d}) · log_{2} N and asymptotic covariance cΣc^{t} · log_{2} N, where c = (c_{1}, c_{2}, …, c_{d}).

It is also clear that the results of [13, 14] should directly transfer to a general basis q ≥ 2 so that we can cover general f(n). We will establish this generalization, however, with a completely different (and in fact more modern) proof.

Theorem 1. Let q ≥ 2 be an integer, and let A_{1}, A_{2}, …, A_{d} be positive integers. Then the vector

(s_{q}(A_{1}n), s_{q}(A_{2}n), …, s_{q}(A_{d}n)), 0 ≤ n < N, (2.3)

satisfies a d-dimensional central limit theorem with asymptotic mean vector ((q − 1)/2, …, (q − 1)/2) · log_{q} N and asymptotic covariance matrix Σ · log_{q} N, where Σ is positive semi-definite.

If we further assume that q is prime and that the integers A_{1}, A_{2}, …, A_{d} are not divisible by q, then Σ is explicitly given by

Σ = (\frac{(q^{2} − 1)}{12} \frac{gcd(A_{i}, A_{j})^{2}}{A_{i}A_{j}} )_{1≤i,j≤d} .  (2.4)

For the proof we make use of the (recent) concept of quasi-additivity which is thoroughly discussed in [8]. There, a function f defined on the non-negative integers is called q-quasi-additive, if there exists r ≥ 0 such that

f(q^{k+r}a + b) = f(a) + f(b) for all b < q^{k}.  (2.5)

We note that if (2.5) holds for some r ≥ 0, then it holds as well for every larger r. This also shows that linear combinations of q-quasi-additive functions are q-quasi-additive, too. We further note that s_{q}(n) is q-quasi-additive with parameter r = 0.

One of the main results of the paper [8] is that any q-quasi-additive function f(n) of at most logarithmic growth satisfies a central limit theorem of the form

\frac{1}{N} # \{n < N : f(n) ≤ μ log_{q} N + t\sqrt{σ^{2} log_{q} N}\} = Φ(t) + o(1),

for appropriate constants μ and σ^{2}.

Our first observation is that f(n) given in (2.2) is q-quasi-additive. The logarithmic growth property is trivially satisfied since s_{q}(n) ≤ (q − 1) log_{q} n.

Lemma 2. Let A and r be positive integers with q^{r} ≥ A. Then g(n) = s_{q}(An) is q-quasi-additive (with parameter r).

Proof. Suppose that b < q^{k}. Then Ab < q^{k+r}, and consequently

g(q^{k+r}a + b) = s_{q}(q^{k+r}Aa + Ab) = s_{q}(Aa) + s_{q}(Ab) = g(a) + g(b).  □

Since linear combinations of q-quasi-additive functions are q-quasi-additive, it directly follows that f(n), as given by (2.2), satisfies a central limit theorem of the prescribed form. This also implies that the vector (2.3) satisfies a d-dimensional central limit theorem with asymptotic mean ((q −1)/2, …, (q −1)/2)·log_{q} N. (This follows from the fact that a random vector X = (X_{1}, … X_{d}) is Gaußian with mean vector (μ_{1}, …, μ_{d}) and covariance matrix Σ if and only if every projection c_{1}X_{1} +⋯+c_{d}X_{d} with real c_{1}, …, c_{d} is univariate Gaußian with mean c_{1}μ_{1}+⋯+c_{d}μ_{d} and variance (c_{1}, …, c_{d})Σ(c_{1}, …, c_{d})^{t}).

It remains to compute the covariance matrix in the case, where q is a prime number.

Lemma 3. Let q ≥ 2 be a prime number, let A_{1}, A_{2} be positive integers that are not divisible by q, and set D = gcd(A_{1}, A_{2}). Then, uniformly for (log N)^{1/3} ≤ i, j ≤ log_{q} N − (log N)^{1/3} and a, b ∈ {0, 1, …, q − 1}, we have

\frac{1}{N} # \{n < N : ε_{i}(A_{1}n) = a, ε_{j}(A_{2}n) = b\}

= \begin{cases}\frac{1}{q^{2}} + O ((log N)^{−C}) , & if i ≠ j, \\ \frac{1}{q^{2}} + \frac{D^{2}}{A_{1}A_{2}} ∑_{ℓ≠0} \frac{1}{4π^{2}ℓ^{2}} (e (−\frac{ℓA_{2}a}{qD}) − e (−\frac{ℓA_{2}(a+1)}{qD})) (e (\frac{ℓA_{1}b}{qD}) − e (−\frac{ℓA_{1}(b+1)}{qD})) \\ +O ((log N)^{−C}) , & if i = j, \end{cases}

for any given C > 0. Here, e(x) = e^{2πix}.

Proof. We adapt the method of [2] to the present situation. However, in order to make the presentation more transparent, we first present a slightly simplified approach. First we note that ε_{j}(n) = a if and only if {nq^{−j−1}} ∈ [a/q, (a + 1)/q), where {x} = x − ⌊x⌋ denotes the fractional part of x. We also note that the Fourier series of the characteristic function 1_{[a/q,(a+1)/q)}(x) is given by

1_{[\frac{a}{q} , \frac{a+1}{q})}(x) = ∑_{m} d_{m}(a)e(mx) with d_{m}(a) = \begin{cases}\frac{1}{q}, & if m = 0, \\ \frac{e(− \frac{ma}{q})−e(− \frac{m(a+1)}{q})}{2πim}, & if m ≠ 0. \end{cases}

This Fourier series is not absolutely convergent. This is the major reason that we have to be more precise in a second round. Observe that d_{m}(a) = 0 if m ≠ 0 and m ≡ 0 mod q.

We have

# \{n < N : ε_{i}(A_{1}n) = a, ε_{j}(A_{2}n) = b\} = ∑_{n<N} 1_{[\frac{a}{q} , \frac{a+1}{q})} (\frac{A_{1}n}{q^{i+1}}) 1_{[\frac{b}{q} , \frac{b+1}{q})} (\frac{A_{2}n}{q^{j+1}})

= ∑_{m_{1},m_{2}} d_{m_{1}}(a) d_{m_{2}}(b) ∑_{n<N} e ((\frac{A_{1}m_{1}}{q^{i+1}} + \frac{A_{2}m_{2}}{q^{j+1}} ) n) .

Since

|∑_{n<N} e(αn)| ≤ \frac{2}{|1 − e(α)|},

we may neglect all exponential sums where α = \frac{A_{1}m_{1}}{q^{i+1}} + \frac{A_{2}m_{2}}{q^{j+1}} is not an integer. At this moment, this step is not rigorous since the Fourier series is not absolutely convergent.

Next suppose that α is an integer. If i ≠ j, the number \frac{A_{1}m_{1}}{q^{i+1}} + \frac{A_{2}m_{2}}{q^{j+1}} can be an integer only if m_{1} = m_{2} = 0 since we also assume that A_{1} and A_{2} are not divisible by q. Thus we should get

# \{n < N : ε_{i}(A_{1}n) = a, ε_{j}(A_{2}n) = b\} = d_{0}(a)d_{0}(b)N + o(N) = \frac{N}{q^{2}} + o(N).

If i = j, then the assumption \frac{A_{1}m_{1}}{q^{j+1}} + \frac{A_{2}m_{2}}{q^{j+1}} = k for an integer k leads to |m_{1}| ≥ \frac{1}{2A_{1}} |k|q^{i+1} ≥ \frac{1}{2A_{1}} |k|q^{(log N)^{1/3}} or |m_{2}| ≥ \frac{1}{2A_{2}} |k|q^{j+1} ≥ \frac{1}{2A_{2}} |k|q^{(log N)^{1/3}} so that the corresponding terms are negligible (if the Fourier series would be absolutely convergent).

Thus we should get (again by observing that all summands for which α is an integer can be put into an error term)

# {n < N : ε_{j}(A_{1}n) = a, ε_{j}(A_{2}n) = b} = ∑_{ℓ} d_{ℓA_{2}/D}(a)d_{−ℓA_{1}/D}(b) N + o(N)

= \frac{N}{q^{2}} + ∑_{ℓ≠0} \frac{1}{4π^{2}ℓ^{2}} (e (−\frac{ℓA_{2}a}{qD}) − e (−\frac{ℓA_{2}(a+1)}{qD})) (e (\frac{ℓA_{1}b}{qD}) − e (−\frac{ℓA_{1}(b+1)}{qD})) N

+ o(N).

In order to make the above heuristics rigorous, we proceed as in [2]. We replace the characteristic function 1_{[a/q,(a+1)/q)}(x) by a smoothed version. Let χ_{a,Δ}(x) be defined by

χ_{a,Δ}(x) := \frac{1}{Δ} ∫_{−Δ/2}^{Δ/2} 1_{[ \frac{a}{q} , \frac{a+1}{q}]}(\{x + z\}) dz,

The Fourier coefficients of the Fourier series χ_{a,Δ}(x) = ∑_{m∈ℤ} d_{m,Δ}(a)e(mx) are given by

d_{0,Δ}(a) = \frac{1}{q},

and for m ≠ 0 by

d_{m,Δ}(a) = \frac{e (−\frac{ma}{q}) − e (−\frac{m(a+1)}{q})}{2πim} · \frac{e (\frac{mΔ}{2}) − e (−\frac{mΔ}{2})}{2πimΔ}.

Note that d_{m,Δ}(a) = 0 if m ≠ 0 and m ≡ 0 mod q, and that

|d_{m,Δ}(a)| ≤ min (\frac{1}{π|m|}, \frac{1}{Δπm^{2}} ) .

By definition, we have 0 ≤ χ_{a,Δ}(x) ≤ 1 and

χ_{a,Δ}(x) = \begin{cases}1, & if x ∈ [\frac{a}{q} + Δ, \frac{a+1}{q} − Δ] , \\ 0, & if x ∈ [0, 1] \ [\frac{a}{q} − Δ, \frac{a+1}{q} + Δ] . \end{cases}

In particular, we set Δ = (log N)^{−C} for some (sufficiently large) constant C. Of course we have to take into account all error terms. The smoothing error can be handled with the help of a discrepancy estimate (see [2]). Putting the resulting estimates together — we leave the details to the reader —, one obtains

# {n < N : ε_{i}(A_{1}n) = a, ε_{j}(A_{2}n) = b} = d_{0,Δ}(a)d_{0,Δ}(b)N + O (N(log N)^{−C})

= \frac{N}{q^{2}} + O (N(log N)^{−C})

for i ≠ j, and

# {n < N : ε_{j}(A_{1}n) = a, ε_{j}(A_{2}n) = b} = ∑_{ℓ} d_{ℓA_{2}/D,Δ}(a)d_{−ℓA_{1}/D,Δ}(b) N

+ O (N(log N)^{−C})

for i = j, where all estimates are uniform for (log N)^{1/3} ≤ i, j ≤ log_{q} N − (log N)^{1/3}. Since

d_{m,Δ}(a) = d_{m}(a)\frac{sin(πmΔ)}{πmΔ} = d_{m}(a) (1 + O (\frac{1}{mΔ}))

for 1 ≤ |m| ≤ 1/Δ, we obtain (with A = max{A_{1}, A_{2}})

∑_{1≤|ℓ|≤1/(AΔ)} d_{ℓA_{2}/D,Δ}(a)d_{−ℓA_{1}/D,Δ}(b) = ∑_{1≤|ℓ|≤1/(AΔ)} d_{ℓA_{2}/D}(a)d_{−ℓA_{1}/D}(b)

+ O (Δ log(1/Δ)) ,

and

∑_{|ℓ|>1/(AΔ)} d_{ℓA_{2}/D,Δ}(a)d_{−ℓA_{1}/D,Δ}(b) = O (Δ) ,
∑_{|ℓ|>1/(AΔ)} d_{ℓA_{2}/D}(a)d_{−ℓA_{1}/D}(b) = O (Δ) .

Thus,

∑_{ℓ} d_{ℓA_{2}/D,Δ}(a)d_{−ℓA_{1}/D,Δ}(b) = ∑_{ℓ} d_{ℓA_{2}/D}(a)d_{−ℓA_{1}/D}(b) + O (\frac{log log N}{(log N)^{C}} )

This completes the proof of the lemma. □

It is now not difficult to complete the computation of the covariance matrix (which also completes the Proof of Theorem 1). By definition, the covariance of s_{q}(A_{1}n) and s_{q}(A_{2}n) is given by

Cov = \frac{1}{N} ∑_{n<N} s_{q}(A_{1}n)s_{q}(A_{2}n) − \frac{1}{N} ∑_{n<N} s_{q}(A_{1}n) · \frac{1}{N} ∑_{n<N} s_{q}(A_{2}n).

In order to apply Lemma 3, we neglect the digits ε_{j} with j ≤ (log N)^{1/3} or j ≥ log_{q}(N)− (log N)^{1/3} and denote by \overline{s}_{q} the sum of digits of the remaining digits ε_{j} with (log N)^{1/3} < j < log_{q} N − (log N)^{1/3}. Then the corresponding approximate covariance \overline{Cov} satisfies

Cov −\overline{Cov} = O ((log N)^{5/6}) ,

which can be shown with the help of the Cauchy–Schwarz inequality. Hence, by rewriting \overline{Cov} with the help of the numbers \frac{1}{N} # \{n < N : ε_{i}(A_{1}n) = a, ε_{j}(A_{2}n) = b\} (from Lemma 3) and the numbers

\frac{1}{N} # \{n < N : ε_{j}(A_{i}n) = a\} = \frac{1}{q} + O ((log N)^{−C})

(note that the fact that this asymptotic property holds uniformly for (log N)^{1/3} ≤ j ≤ log_{q} N − (log N)^{1/3}, a ∈ {0, 1, …, q − 1}, and i = 1, 2 follows from Lemma 3), we immediately get

\overline{Cov} = L\frac{D^{2}}{A_{1}A_{2}} ∑_{a,b=0}^{q−1} ab ∑_{ℓ≢0 mod q} \frac{1}{4π^{2}ℓ^{2}}

· (e (−\frac{ℓA_{2}a}{qD}) − e (−\frac{ℓA_{2}(a+1)}{qD})) (e (\frac{ℓA_{1}b}{qD}) − e (−\frac{ℓA_{1}(b+1)}{qD}))
+ O ((log N)^{2−C})

= L\frac{D^{2}}{A_{1}A_{2}} \frac{q^{2}}{4π^{2}} ∑_{ℓ≢0 mod q} \frac{1}{ℓ^{2}} + O ((log N)^{2−C})

= L\frac{D^{2}}{A_{1}A_{2}} \frac{q^{2} − 1}{12} + O ((log N)^{2−C}) ,

where L = ⌊log_{q} N − 2(log N)^{1/3}⌋, and where we have used the identity

∑_{a=0}^{q−1} a e(ak/q) = \frac{q}{e(k/q) − 1},

which is valid for integers k that are not divisible by q. We can choose C appropriately — for example C = 2 — and finally obtain

Cov = \frac{q^{2} − 1}{12} \frac{gcd(A_{i}, A_{j})^{2}}{A_{i}A_{j}} log_{q} N + O ((log N)^{5/6}) ,

which completes the proof of Theorem 1.

3. Asymptotic divisibility of Catalan-like integer sequences

The main result in this section concerns divisibility of “Catalan-like” sequences by prime powers.

Theorem 4. Let p be a given prime number, α a positive integer, P (n) a polynomial in n with integer coefficients, and (C_{i})_{1≤i≤r}, (D_{i})_{1≤i≤s}, (E_{i})_{1≤i≤t}, (F_{i})_{1≤i≤t} given integer sequences with C_{i}, D_{i} > 0 and p ∤ gcd(E_{i}, F_{i}) for all i, ∑_{i=1}^{r} C_{i} = ∑_{i=1}^{s} D_{i}, and {C_{i} : 1 ≤ i ≤ r} ≠ {D_{i} : 1 ≤ i ≤ s}. If all elements of the sequence (S(n))_{n≥0}, defined by

S(n) := \frac{P (n)}{∏_{i=1}^{t}(E_{i}n + F_{i})} \frac{∏_{i=1}^{r}(C_{i}n)!}{∏_{i=1}^{s}(D_{i}n)!},  (3.1)

are integers, then

lim_{N→∞} \frac{1}{N} # \{n < N : S(n) ≡ 0 (mod p^{α})\} = 1.  (3.2)

We note that (3.2) remains true if α increases slowly with N. In particular, we can choose α = ⌊η log N⌋ for an appropriate η > 0. We will actually show in the proof of Theorem 4 that

# \{n < N : v_{p}(S(n)) < η log N\} = O (\frac{N}{\sqrt{log N}} )

if η > 0 is sufficiently small.

Furthermore we note that the assumption p ∤ gcd(E_{i}, F_{i}) is not really necessary since we can always reduce the problem to this case by separating the factors p^{v_{p}(gcd(E_{i},F_{i}))}. Thus, we immediately obtain the following corollary.

Corollary 5. Let S(n) be given as in Theorem 4 (without assuming the condition p ∤ gcd(E_{i}, F_{i})). Then, for all positive integers m, we have

lim_{N→∞} \frac{1}{N} # \{n < N : S(n) ≡ 0 (mod m)\} = 1.  (3.3)

We call integer sequences of the form as in (3.1) — that is, integer sequences given by a product/quotient of factorials multiplied by a rational function — “Catalan-like” since the Catalan numbers \frac{1}{n+1} \binom{2n}{n} represent obviously such a sequence, but as well many other sequences that one finds in the literature (and in the On-Line Encyclopedia of Integer Sequences [15]).

Examples. All of the following sequences are “Catalan-like” in the sense of (3.1).

(1) Binomial coefficients such as the central binomial coefficients \binom{2n}{n}, or more generally \binom{(a+b)n}{an} for positive integers a and b, including variations such as \binom{2n}{n−1}, etc.

(2) Multinomial coefficients such as \frac{((a_{1}+a_{2}+···+a_{s})n)!}{(a_{1}n)! (a_{2}n)!···(a_{s}n)!}, etc.

(3) Fuß–Catalan numbers. These are defined by (cf. [1, pp. 59–60]) \frac{1}{n} \binom{(m+1)n}{n−1}, where m is a given positive integer.

(4) Gessel’s [7] super ballot numbers (often also called super-Catalan numbers) \frac{(2n)! (2m)!}{n! m! (m+n)!} for non-negative integers m, or for m = an with a a positive integer.

(5) Many counting sequences in tree and map enumeration (cf. [12] for a survey) such as \frac{m+1}{n((m−1)n+2)} \binom{mn}{n−1} (m-ary blossom trees with n white nodes; cf. [11, Sec. 3]), \frac{2·3^{n}}{(n+2)(n+1)} \binom{2n}{n} (number of rooted planar maps with n edges; cf. [20]), \frac{2}{(3n−1)(3n−2)} \binom{3n−1}{n} (number of rooted non-separable planar maps with n edges; cf. [4]), \frac{2}{(3n+1)(n+1)} \binom{4n+1}{n} (number of rooted planar triangulations with n+3 vertices; cf. [18]), \frac{1}{2(n+2)(n+1)} \binom{2n}{n}\binom{2n+2}{n+1} (number of rooted Hamiltonian maps with 2n vertices; cf. [19]), to mention just a few.

What Theorem 4 says is that, for any of these sequences, most elements (in the sense that the proportion of those in the set of all elements tends to 1) are divisible by p^{α}, for a given prime number p and given positive integer α.

We should at this point remind the reader of Landau’s criterion [9], which says that

U(n) := \frac{∏_{i=1}^{r}(C_{i}n)!}{∏_{i=1}^{s}(D_{i}n)!}

is an integer for all n if and only if

∑_{i=1}^{r} ⌊C_{i}x⌋ − ∑_{i=1}^{s} ⌊D_{i}x⌋ ≥ 0  (3.4)

for all real numbers x. (Here, we still assume that ∑_{i=1}^{r} C_{i} = ∑_{i=1}^{s} D_{i}.) In view of [3, Lemma 3.3], which says that if U(n) is non-integral for some n then, for almost all primes p, there exists an n such that v_{p}(U(n)) < 0, this means (more or less; we do not believe that the polynomial P (n) can “correct” non-integrality of U(n) for all n) that (3.4) is an implicit assumption in Theorem 4.

For the proof of Theorem 4, we consider the integer interval [0, N − 1] as a probability space, with each integer equally likely, precisely as in Section 2. For notational convenience, the corresponding probability function will be denoted by P_{N}. Functions on the non-negative integers are then interpreted as random variables X on this space by restricting them to [0, N − 1]. The expectation of X on the space, that is, \frac{1}{N} ∑_{i=0}^{N−1} X(i), will be denoted by E_{N}(X), the variance will be denoted by Var_{N}(X), and the covariance of two functions by Cov_{N}(X, Y).

We need two auxiliary lemmas. The first concerns asymptotic mean and variance for the p-adic valuation of a linear function.

Lemma 6. Let E and F be integers, E > 0, not both divisible by the prime p. If v_{p}(En + B) is considered as a random variable for n in the integer interval [0, N − 1], then

E_{N}(v_{p}(En + F)) = \begin{cases}0, & if p | E, \\ \frac{1}{p−1} + o(1), & if p ∤ E, \end{cases}  as N → ∞,  (3.5)

and

Var_{N}(v_{p}(En + F)) = \begin{cases}0, & if p | E, \\ \frac{p}{(p−1)^{2}} + o(1), & if p ∤ E, \end{cases}  as N → ∞.  (3.6)

Proof. The first assertion in the case distinction in (3.5) is obvious since our assumptions imply that En + F ≢ 0 (mod p) if p | E. If p ∤ E, then the congruence En + F ≡ 0 (mod p^{α}) has a unique solution for n modulo p^{α} for any given positive integer α. Thus, we have

E_{N}(v_{p}(an + b)) = \frac{1}{N} ∑_{ℓ=1}^{⌊log_{p} N⌋} (\frac{N}{p^{ℓ}} + O(1)) = \frac{1}{p − 1} + o(1), as N → ∞.

Similarly, still assuming p ∤ E, for the variance we have

Var_{N}(v_{p}(an + b)) = \frac{1}{N} ∑_{ℓ=1}^{⌊log_{p} N⌋}(2ℓ − 1) (\frac{N}{p^{ℓ}} + O(1)) − ( E_{N}(v_{p}(an + b)))^{2}

= \frac{p + 1}{(p − 1)^{2}} − \frac{1}{(p − 1)^{2}} + o(1), as N → ∞,

establishing also (3.6). □

The second auxiliary lemma provides an asymptotic upper bound on the covariance of a linear function and the sum-of-digits function of a linear function.

Lemma 7. Let C, E, and F be integers, C, E > 0, and E and F not both divisible by p. If s_{p}(Cn) and v_{p}(En + B) are considered as random variables for n in the integer interval [0, N − 1], then

Cov_{N}(s_{p}(Cn), v_{p}(En + F)) = O(log_{p}^{1/2}(N)) ,  as N → ∞.  (3.7)

Proof. By the Cauchy–Schwarz inequality in probabilistic setting, we have

Cov_{N}(s_{p}(Cn), v_{p}(En + F )) ≤ Var_{N}(s_{p}(Cn))^{1/2} Var_{N}(v_{p}(En + F ))^{1/2}.

The variance of s_{p}(Cn) = s_{p}(Cp^{−v_{p}(C)}n) has been (implicitly) given in (2.1) (see the line below that equation; see also (2.4) with q = p and A_{i} = A_{j} = Cp^{−v_{p}(C)}) and turned out to be of the order log_{p}(N), while the variance of v_{p}(En+F ) has been given in (3.6) and turned out to be bounded. The assertion of the lemma is hence obvious. □

Proof of Theorem 4. With S(n) given in (3.1), we have

v_{p}(S(n)) = v_{p}(P (n)) − ∑_{i=1}^{t} v_{p}(E_{i}n + F_{i}) + ∑_{i=1}^{r} v_{p}((C_{i}n)!) − ∑_{i=1}^{s} v_{p}((D_{i}n)!)

≥ − ∑_{i=1}^{t} v_{p}(E_{i}n + F_{i}) − \frac{1}{p − 1} ∑_{i=1}^{r} s_{p}(C_{i}n) + \frac{1}{p − 1} ∑_{i=1}^{s} s_{p}(D_{i}n).  (3.8)

Here, we used Legendre’s formula (1.1) and the assumption that ∑_{i=1}^{r} C_{i} = ∑_{i=1}^{s} D_{i}.

Now, it follows from [3, Lemma 3.5 and its proof], that under the integrality and non-triviality assumption for S(n) of the theorem, we have r < s.

The expression on the right-hand side of (3.8) is a linear combination of the functions v_{p}(E_{i}n + F_{i}), s_{p}(C_{i}n), and s_{p}(D_{i}n), which we view again as random variables on [0, N − 1]. For convenience, let us denote the function on the right-hand side of (3.8) by T (n). By Theorem 1 and (3.5), we have

E_{N}(T (n)) = Ω( log_{p}(N)), as N → ∞.

The reader should observe that the inequality r < s is used here crucially. On the other hand, the variance of T (n) is bounded above by the sum of the pairwise covariances of the involved random variables (functions). By Theorem 1, (3.6), and (3.7), we see that

Var_{N}(T (n)) = O( log_{p}(N)), as N → ∞.

Given a random variable X, Chebyshev’s inequality reads

P(|X − E(X)| < ε) > 1 − \frac{1}{ε^{2}} V (X).  (3.9)

Choosing ε = ( log_{p}(n))^{3/4} and X = T (n), we get

P_{N}(|T (n) − E_{N}(T (n))| < log_{p}^{3/4}(N)) = 1 + O(log_{p}^{−1/2}(N)) , as N → ∞.

Thus, for N large enough, we have

T (n) > E_{N}(T (n)) − log_{p}^{3/4}(N) = Ω(log_{p}(N)) > α,

with probability 1 + O( log_{p}^{−1/2}(N)). If we use this information in (3.8), then the assertion of the theorem follows immediately. □

References

[1] D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, R.I., 2009.

[2] N. L. Bassily and I. Kátai, Distribution of the values of q-additive functions on polynomial sequences, Acta Math. Hung. 68 (1995), 353–361.

[3] J. W. Bober, Factorial ratios, hypergeometric series, and a family of step functions, J. London Math. Soc. 79 (2009), 422–444.

[4] W. G. Brown, Enumeration of non-separable planar maps, Can. J. Math. 15 (1963), 526–545.

[5] R. Burns, Structure and asymptotics for Catalan numbers modulo primes using automata,

preprint, arχiv:1701.02975.

[6] C. Dartyge and G. Tenenbaum, Sommes des chiffres de multiples d???entiers, Ann. Inst. Fourier 55(7) (2005), 2423–2474.

[7] I. M. Gessel, Super ballot numbers, J. Symbolic Comput. 14 (1992), 179–194.

[8] S. Kropf and S. Wagner, On q-quasiadditive and q-quasimultiplicative functions, Electron. J. Combin. 24(1) (2017), Article 1.60, 22 pp.

[9] E. Landau, Sur les conditions de divisibilité d’un produit de factorielles par un autre, Nouv. Ann. Math. 19 (1900), 344–362.

[10] A. M. Legendre, Essai sur la théorie des nombres, 2ed., Courcier, Paris, 1808.

[11] G. Schaeffer, A combinatorial interpretation of super-Catalan numbers of order two, unpublished manuscript, 2003; available at

http://www.lix.polytechnique.fr/Labo/Gilles.Schaeffer/Biblio/Sc03.ps.

[12] G. Schaeffer, Planar maps, in: Handbook of Enumerative Combinatorics, M. Bóna (ed.), CRC Press, Boca Raton, London, New York, 2015, pp. 335–395. 589–678.

[13] J. Schmid, The joint distribution of the binary digits of integer multiples, Acta Arith. 43 (1984), 391–415.

[14] W. M. Schmidt, The joint distribution of the digits of certain integer s-tuples, Studies in Pure Mathematics, Mem. of P. Turán (1983), 605–622.

[15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

[16] L. Spiegelhofer and M. Wallner, Divisibility of binomial coefficients by powers of two,

preprint, arχiv:1710.10884.

[17] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[18] W. T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21–38.

[19] W. T. Tutte, A census of Hamiltonian polygons, Canad. J. Math. 14 (1962), 402–417.

[20] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249–271.

∗Institute of Discrete Mathematics and Geometry, TU Wien, Wiedner Hauptstraße

8–10, A-1040 Vienna, Austria. WWW: https://www.dmg.tuwien.ac.at/drmota.

†Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090

Vienna, Austria. WWW: http://www.mat.univie.ac.at/~kratt.