Variance Functions of Asymptotically Exponentially Increasing Integer Sequences Go Beyond Taylor’s Law

Joel E. Cohen The Rockefeller University 1230 York Avenue, Box 20 New York, NY 10065, U.S.A.

                      cohen@rockefeller.edu

also: Departments of Statistics, Columbia University & University of Chicago

Abstract

Fibonacci, Lucas, Catalan, and all asymptotically exponentially increasing positive sequences have counting functions (number of elements that do not exceed a large number y) that are asymptotically proportional to the logarithm of y, a slowly varying function. For all such sequences, the variance of the elements that do not exceed y is asymptotically proportional to the product of three factors: the logarithm of the largest sequence element a(n) that does not exceed y; an explicit function of the asymptotic ratio of successive sequence elements; and the square of the mean of the elements that do not exceed y. The variance function of an integer sequence has numbertheoretic interest because it distinguishes integer sequences according to the form of their variance function. The variance function is also important in the analysis of variance. Number-theoretic examples make it possible to analyze the variance function of well specified processes observed without error.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 11B37. Keywords: Catalan sequence, counting function, Fibonacci sequence, Lucas sequence, exponential sequence, Taylor’s law, variance function.

1 Introduction

Mathematicians have studied the statistical properties of sequences of natural numbers (positive integers) for centuries. Based on statistical analyses, Gauss at the end of the eighteenth century and Legendre at the beginning of the nineteenth century conjectured the prime number theorem, which was proved almost a century later. Erdős and Kac [?] continued the application of statistical methods to number-theoretic problems. Several authors [?, ?, ?, ?] have shown that the variance of the first n elements of some integer sequences is asymptotic, as n → ∞, to a positive power of the mean of the first n elements. This power-law variance function is often called Taylor’s law (henceforth TL). Here we go beyond TL by showing that, for sequences that asymptotically grow exponentially, a constant coefficient in TL must be replaced by a slowly varying function of the nth element of the sequence (Theorem 1). A measurable function L : (0, ∞) ↦ (0, ∞) is defined [?] to be slowly varying (at infinity, a qualification we drop henceforth) if, for all λ > 0, lim_{x→∞} L(λx)/L(x) = 1.

Let ℕ := {1, 2, 3, …} be the set of natural numbers. Let A be the collection of all infinite, eventually strictly increasing sequences of natural numbers selected from ℕ. A typical sequence is a = (a(1), a(2), a(3), …) subject to a(n) < a(n + 1) for all n ≥ n_{0} ≥ 1, where n_{0} depends on a. Define the mean m(a, n) and variance v(a, n) of the first n ∈ ℕ elements of a, n ≥ 2, as

m(a, n) := \frac{1}{n} ∑_{j=1}^{n} a(j),  (1)

v(a, n) := \frac{1}{n − 1} ∑_{j=1}^{n}(a(j) − m(a, n))^{2} = \frac{n}{n − 1} (\frac{1}{n} ∑_{j=1}^{n} a(j)^{2} − m(a, n)^{2}) .  (2)

It is easy to prove that, for all a ∈ A, as n → ∞, m(a, n) → ∞ and m(a, n) is monotonic increasing in n. While v(a, n) → ∞ also, v(a, n) does not always increase monotonically with n. For example, if a = (1, 10, 11, …), then v(a, 3) ≈ 30.33 < v(a, 2) = 40.5.

The variance function of a is the mapping m(a, n) ↦ v(a, n) [?, ?, ?, ?, ?, ?]. The variance function has number-theoretic interest because it distinguishes integer sequences according to the form of their variance function. The variance function is also important in the analysis of variance (ANOVA) and agricultural and ecological applications of ANOVA because ANOVA assumes a constant variance. Knowing the variance function sometimes makes it possible to transform data to achieve or approximate a constant variance. The variance function is also important in ecological studies of populations because it can reveal environmental heterogeneity, aggregation, and contagion. Infinite increasing integer sequences provide tractable “laboratory models” for investigating the variance function under scientifically advantageous circumstances: the process generating the “data” a = (a(1), a(2), a(3), …) is mathematically well defined and subject to analysis without sampling error.

If f(x) and g(x) are real-valued functions of real x and g(x) > 0 for all x sufficiently large, define f(x) ∼ g(x) to mean that f(x)/g(x) → 1 as x → ∞.

A sequence a ∈ A satisfies TL asymptotically if there exist a finite real constant coefficient c > 0 and a finite real constant b such that

lim_{n→∞} v(a, n)/m(a, n)^{b} = c.  (3)

Thousands of empirical illustrations of TL [?] and theoretical analyses and models [?] of TL have been published. Because m(a, n) → ∞ as n → ∞, TL (3) implies that

lim_{n→∞}(log v(a, n))/(log m(a, n)) = b.  (4)

In economics, the exponent b would be called the elasticity of the variance with respect to the mean.

We call a sequence of positive numbers asymptotically exponentially increasing if and only if successive elements of the sequence asymptotically increase by a fixed ratio greater than 1: a(n+1)/a(n) ∼ z > 1 for large n. Jakimczuk [?] independently gives an equivalent definition. The variance functions of the Fibonacci (OEIS \underline{A000045}), Lucas (OEIS \underline{A000032}), Catalan (OEIS \underline{A000108}), and all asymptotically exponentially increasing sequences have apparently not yet been investigated. The local elasticity b(a, n) of a sequence a is defined below in (15). We show here that, as n → ∞, b(a, n) → 2 but that the ratio v(a, n)/m(a, n)^{2}, instead of converging to a constant c as in the exact TL and asymptotic TL, are asymptotic to the product of log a(n) times (z − 1)/((z + 1) log z).

The prime numbers obey TL asymptotically with b = 2, c = 1/3 [?]. The proof in [?] for prime numbers is a special case of a much more general result [?]: the variance functions of increasing integer sequences with regularly varying [?] counting functions with positive index, ρ > 0, asymptotically obey TL with b = 2 and c = (ρ(ρ + 2))^{−1}. The prime number theorem implies that, for the primes, ρ = 1. Examples of increasing integer sequences with regularly varying counting functions with positive index include natural numbers raised to a fixed power, primes, primes in residue classes, the lesser of twin primes (given the Hardy-Littlewood twin primes conjecture), prime constellations (given a Hardy-Littlewood conjecture), primes from polynomials (given the Bateman-Horn conjecture), perfect powers, triangular numbers, squares, pentagonal numbers, and others.

M. P. Cohen [?] (no known relation) gave an alternative proof, not involving regularly varying functions, that the primes obey TL asymptotically with b = 2, c = 1/3. Demers [?] found numerically, without mathematical support, that 110 of the 113 finite integer sequences classified as “nice” in the On-Line Encyclopedia of Integer Sequences (OEIS) have means and variances closely approximated by log(v(a, n)) = 2.040 log(m(a, n)) + 0.335 (with coefficient of determination R^{2} = 0.99). Here n is the finite length of the sequence, which varied from 2 to 2,137,453, with a median value of n = 17. The reported 95% confidence interval around the slope is ±0.013. If, in the context of this collection of finite integer sequences, the methods Demers used to calculate this confidence interval are justified and if there is a plausible probabilistic interpretation of such a confidence interval, then the hypothesis of a slope b = 2 for these integer sequences would seem to be rejected at a significance level p ≪ 0.05. Demers [?] also showed analytically that, asymptotically as n → ∞, the n + 1 binomial coefficients \binom{n}{k}, k = 0, 1, …, n, obey TL with c = 1, b = 2.

Cohen, Davis, and Samorodnitsky [?, p. 6, eq. 3.3] gave an example in which the ratio of the sample variance to a constant power (corresponding to b in TL) of the sample mean of heavy-tailed data converges in distribution to a random variable times a slowly varying function of the sample size. We are not aware of any other prior example in which a slowly varying function replaces the constant coefficient c of TL.

Section 2 establishes the variance functions and the counting functions of asymptotically exponentially increasing sequences. Sections 3 and ?? calculate directly the variance functions of Fibonacci and Catalan sequences to verify the general results of Section 2, and apply the general results of Section 2 to obtain the variance function of the Lucas sequence. Section ?? describes some increasing integer sequences for which the variance functions remain to be determined.

2 Asymptotically exponentially increasing sequences

Define a sequence of positive real numbers a = (a(1), a(2), …) to be asymptotically exponentially increasing if and only if there exist real w > 0, z > 1, such that for n ∈ ℕ, a(n) ∼ wz^{n} as n → ∞.

We recall an elementary identity from high school algebra. If −∞ < r < ∞, r ≠ 1, w > 0, and a(n) := wr^{n}, n ∈ ℕ, then

∑_{j=1}^{n} wr^{j} = wr ∑_{j=0}^{n−1} r^{j} = wr\frac{r^{n} − 1}{r − 1} = \frac{r}{r − 1}(a(n) − w).  (5)

If, in addition, r > 1, then

∑_{j=1}^{n} wr^{j} ∼ \frac{r}{r − 1}a(n).  (6)

Theorem 1. Suppose a sequence of positive real numbers a = (a(1), a(2), …) is asymptotically exponentially increasing, i.e., a(n) ∼ wz^{n} as n → ∞ for n ∈ ℕ, real w > 0, z > 1. Then

\frac{v(a, n)}{m(a, n)^{2}} ∼ \frac{(z − 1) log a(n)}{(z + 1) log z}.  (7)

Proof. The following limiting or asymptotic statements are as n → ∞. We have log w > −∞, log z > 0, wz^{n} → ∞, a(n) → ∞, and log a(n) → ∞. The assumption a(n) ∼ wz^{n} implies

n = \frac{log a(n) − log w}{log z} ∼ \frac{log a(n)}{log z}.  (8)

Setting r = z > 1, the mean of the first n elements of a is asymptotically

m(a, n) ∼ \frac{wz(z^{n} − 1)}{n(z − 1)}.  (9)

Setting r = z^{2} > 1, using (2) in the first step below, and using (8) in the last step below, the ratio of the variance to the squared mean of the first n elements of a is asymptotically

\frac{v(a, n)}{m(a, n)^{2}} = \frac{n}{n − 1} ( \frac{\frac{1}{n} ∑_{j=1}^{n} a(j)^{2}}{m(a, n)^{2}} − 1)  (10)

∼ (\frac{w^{2}}{n} ∑_{j=1}^{n} z^{2j}) · (\frac{wz(z^{n} − 1)}{n(z − 1)})^{−2} − 1  (11)

∼ n\frac{(z^{2n} − 1)}{(z^{2} − 1)} \frac{(z − 1)^{2}}{(z^{n} − 1)^{2}} − 1  (12)
∼ \frac{(z − 1) log a(n)}{(z + 1) log z}.  (13)

This proves (7).

As we shall show in the following sections, the Fibonacci, Lucas, and Catalan sequences share the property that the ratio of an element divided by its predecessor approaches a positive limit greater than 1 as n → ∞:

\frac{F_{n+1}}{F_{n}} → ϕ, \frac{L_{n+1}}{L_{n}} → ϕ, \frac{C(n + 1)}{C(n)} → 4,  (14)

where ϕ := (1 + \sqrt{5})/2 > 1 is the golden ratio. By contrast, the ratio of successive prime numbers approaches 1.

The factor on the right side of (7) that is independent of n, namely, (z−1)/((z+1) log z), depends only on the limiting ratio z. When z = 4, then (z − 1)/((z + 1) log z) = 3/(10 log 2) as for the Catalan sequence (??). When z = ϕ, then

(z − 1)/((z + 1) log z) = (ϕ − 1)/((ϕ + 1) log ϕ) = ϕ/((ϕ + 1)^{2} log ϕ) = \sqrt{5} − 2,

as for the Fibonacci sequence (21) and Lucas sequence (??).

For any strictly increasing positive sequence a = (a(1), a(2), …), define the counting function N(a, y) of a at y ∈ (0, ∞) as the (integer) number of elements of a less than or equal to y. Thus if a(n) ≤ y < a(n + 1), then N(a, y) = n, and conversely. The faster a increases with n, that is, the sparser the successive elements a(n) are, the more slowly N(a, y) increases with y. If a is asymptotically exponentially increasing, and also if a ∈ A, then N(a, y) → ∞ as y → ∞. An asymptotic counting function Ñ(a, y) of a at y is any non-decreasing function such that Ñ(a, y) ∼ N(a, y) as y → ∞. An asymptotic counting function is not unique.

Theorem 2. Suppose a sequence of positive real numbers a = (a(1), a(2), …) is asymptotically exponentially increasing, i.e., a(n) ∼ wz^{n} as n → ∞ for n ∈ ℕ, real w > 0, z > 1. Then a(n + 1)/a(n) → z and an asymptotic counting function Ñ(a, y) of a at large real y is Ñ(a, y) := (log y)/ log z. Conversely, if an asymptotic counting function Ñ(a, y) of an increasing sequence of positive real numbers a = (a(1), a(2), …) at large real y is Ñ(a, y) := (log y)/ log z, z > 1, then a is asymptotically exponentially increasing and a(n + 1)/a(n) → z.

Proof. Assume a(n) ∼ wz^{n} as n → ∞ for all n ∈ ℕ, real w > 0, z > 1. Then for every y ∈ (a(1), ∞) there exists n ∈ ℕ such that a(n) ≤ y < a(n + 1). Then N(a, y) = n ∼ (log a(n))/ log z by (8). Asymptotically, log a(n) ≤ log y < log(a(n) · z) = log a(n) + log z. Hence (log a(n))/ log z ≤ (log y)/ log z < (log a(n))/ log z + 1 ∼ (log a(n))/ log z. Hence Ñ(a, y) := (log y)/ log z is an asymptotic counting function.

Conversely, suppose Ñ(a, y) := (log y)/ log z is an asymptotic counting function of an increasing sequence of positive real numbers a = (a(1), a(2), …) at y. Then Ñ(a, yz) = (log(yz))/ log z = Ñ(a, yz) + 1, i.e., i.e., multiplying y by z increases Ñ(a, yz) by 1, so asymptotically successive elements of a increase by a factor of z > 1 and a is asymptotically exponentially increasing.

Jakimczuk [?] independently proves the direct half of Theorem 2, that an asymptotically exponentially increasing sequence has an asymptotic counting function (log y)/ log z.

Define the “local elasticity” of a at a(n) as

b(a, n) := \frac{log v(a, n + 1) − log v(a, n)}{log m(a, n + 1) − log m(a, n)}.  (15)

The local elasticity is the slope of the variance function on log-log coordinates between the point with abscissa m(a, n) and ordinate v(a, n) and the point with abscissa m(a, n + 1) and ordinate v(a, n + 1). The sequence a satisfies TL asymptotically with coefficient c and exponent b > 0 if and only if, as n → ∞, b(a, n) → b and v(a, n)/m(a, n)^{b} → c.

Theorem 3. Suppose a sequence of positive real numbers a = (a(1), a(2), …) is asymptotically exponentially increasing with a(n) ∼ wz^{n} as n → ∞ for n ∈ ℕ, real w > 0, z > 1. Then the local elasticity b(a, n) (15) converges to b = 2 as n → ∞. The converse is false: b(a, n) → 2 does not require that the sequence a be asymptotically exponentially increasing.

Proof. Using (7) gives

\frac{v(a, n)}{m(a, n)^{2}} ∼ \frac{(z − 1) log a(n)}{(z + 1) log z}, \frac{v(a, n + 1)}{m(a, n + 1)^{2}} ∼ \frac{(z − 1) log a(n + 1)}{(z + 1) log z},  (16)
\frac{v(a, n + 1)}{m(a, n + 1)^{2}} /\frac{v(a, n)}{m(a, n)^{2}} ∼ \frac{log a(n + 1)}{log a(n)} = \frac{log w + (n + 1) log z}{log w + n log z} ∼ 1,  (17)
\frac{v(a, n + 1)}{m(a, n + 1)^{2}} /\frac{v(a, n}{m(a, n)^{2}} = \frac{v(a, n + 1)}{v(a, n)}/\frac{m(a, n + 1)^{2}}{m(a, n)^{2}} ,  (18)
log \frac{v(a, n + 1)}{v(a, n)} − 2 log \frac{m(a, n + 1)}{m(a, n)} ∼ log 1 = 0,  (19)
b(a, n) = log \frac{v(a, n + 1)}{v(a, n)}/ log \frac{m(a, n + 1)}{m(a, n)} ∼ 2.  (20)

That the converse is false is proved by the example of the prime numbers [?], which satisfy b(a, n) → 2 but are not asymptotically exponentially increasing.

3 Example: Fibonacci and Lucas sequences

We verify the general results in section 2 for the Fibonacci sequence by direct calculation.

Theorem 4. For the Fibonacci sequence 𝔽 (OEIS \underline{A000045}) with elements F_{1} = 1, F_{2} = 1, F_{n+2} = F_{n}+F_{n+1}, n ∈ ℕ, the variance v(𝔽, n) is related to the mean m(𝔽, n) asymptotically as n → ∞ by

v(𝔽, n) ∼ log(F_{n}) · \frac{ϕ}{(ϕ + 1)^{2} log ϕ} · m(𝔽, n)^{2}.  (21)

In this asymptotic variance function (21), log(F_{n})ϕ/((ϕ + 1)^{2} log ϕ), a slowly varying function of F_{n}, replaces the constant coefficient c of TL. To prove this theorem, we use a lemma of independent interest.

Lemma 5. For F_{n} ∈ 𝔽, n ∈ ℕ,

lim_{n→∞} \frac{∑_{j=1}^{n} F_{n}^{2}}{(∑_{j=1}^{n} F_{n})^{2}} = lim_{n→∞} \frac{F_{n}F_{n+1}}{(F_{n+2} − 1)^{2}} = \frac{ϕ}{(ϕ + 1)^{2}} = \sqrt{5} − 2.  (22)

Proof. From Hoggatt [?]:

∑_{j=1}^{n} F_{n} = F_{n+2} − 1 = F_{n} + F_{n+1} − 1,  (23)

∑_{j=1}^{n} F_{n}^{2} = F_{n} · F_{n+1}.  (24)

This establishes the first equality in (22).

Let ψ := −1/ϕ = (1 − \sqrt{5})/2. Then |ϕ| > 1 > |ψ|. Binet’s form for F_{n} is asymptotically exponentially increasing:

F_{n} = \frac{ϕ^{n} − ψ^{n}}{ϕ − ψ} = \frac{ϕ^{n} − ψ^{n}}{\sqrt{5}} ∼ \frac{ϕ^{n}}{\sqrt{5}}.  (25)

Hence

\frac{F_{n}F_{n+1}}{(F_{n+2} − 1)^{2}} ∼ \frac{F_{n}F_{n+1}}{(F_{n} + F_{n+1})^{2}} ∼ \frac{ϕ^{n}ϕ^{n+1}}{(ϕ^{n} + ϕ^{n+1})^{2}} = \frac{ϕ^{2n+1}}{ϕ^{2n}(1 + ϕ)^{2}} = \frac{ϕ}{(1 + ϕ)^{2}} .  (26)

This establishes the second equality in (22). The third equality in (22) is elementary.