Contents

1 Background: Conditional Probability and Independence 1 1.1 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Continued Fractions 3 2.1 Basic Continued Fraction Theory . . . . . . . . . . . . . . . . . . 3 2.2 How to find the quotients of a continued fraction . . . . . . . . . 4 2.3 Uniqueness and Property of Infinite Continued Fraction Expansions 4

3 Kuzmin’s Theorem 7 3.1 General Comments . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Detailed Analysis of Kuzmin’s Theorem . . . . . . . . . . . . . . 7

4 Expected Results and Kuzmin Applied 10 4.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 (1,1) Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Results 17 5.1 Brief Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

6 Conclusion 22

Abstract

The purpose of this paper is to determine whether a specific subset of degree three algebraic numbers corroborate Kuzmin’s Theorem regarding the dependency among the digits of the continued fraction expansion of a generic number. Kuzmin would predict that for a generic number between (0,1), we should expect that the value of a_{n} is dependent on a_{n−1}, and the dependency should be fairly equal for all values of n, where n is larger than the desired error. Furthermore, Kuzmin gives a numerical prediction for the dependency of a_{n}’s value, given the value of a_{n−1}. Numbers such as e and quadratic irrationals do not obey Kuzmin’s Theorem, in that the dependencies between digits is disparate from Kuzmin’s prediction. We still seek additional classes of numbers that are consistently disparate from Kuzmin’s dependencies. This paper will present results based on the continued fraction expansions of cube roots of prime numbers or those numbers satisfying the equation x^{3} − p = 0, p is prime. We repeat the experiment for the first 100 primes and the first 100 primes larger than 10^{6}. Finally, we examine the dependency of a_{n}’s value on the value of a_{n−1} when a_{n−1} is equal to a specific number k, in particular, the pairs (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3). The results of the experiment for this special subset of degree three algebraic numbers exhibit the same dependencies that Kuzmin would predict for a generic number.

Chapter 1

Background: Conditional Probability and Independence

1.1 Conditional Probability

Let us denote P(X) the probability of event X occurring. We will also denote P (A|B) as the probability that event A occurrs, given that event B has already occurred. We can thus define the conditional probability as follows:

Definition 1.1.1. For any two events A and B with P (B) > 0, the conditional probability of A given that B has occurred is defined by

P (A|B) = \frac{P (A ∩ B)}{P (B)}  (1.1)

1.2 Independence

Definition 1.2.1. Two events A and B are independent if P (A|B) = P (A) and are dependent otherwise.

Two mutually exclusive events are not independent because if the knowledge that Event B occurs gives you knowledge of the expected probability of Event A occurring, then the events are not independent. In other words, if knowing that Event B occurs does not affect the probability of observing Event A, then A and B are independent.

Quite often in mathematics and statistics P (A|B) ≠ P (A), but if A and B are independent then P (A|B) = P (A). Kuzmin’s Theorem explicates that, indeed, P (x_{1}|x_{2}) ≠ P (x_{1}). We shall derive and test Kuzmin’s predicted value of P (x_{1}|x_{2}).

Combining our section on conditional probability and independence, we arrive at a proposition: Proposition 1.2.2. A and B are independent if and only if

P (A ∩ B) = P (A) ∗ P (B)  (1.2)

In otherwords, the probability that both events occur is the product of the two individual probabilities. The verification is as follows:

P (A ∩ B) = P (A|B) ∗ P (B) = P (A) ∗ P (B)  (1.3)

where the second inequality is valid if and only if A and B are independent.

We conclude this section with a general definition and an example [Dev]: Definition 1.2.3. Events A_{1}, …, A_{n} are mutually independent if for every k (k = 2, 3, …, n) and every subset of indicies i_{1}, i_{2}, …, i_{k}, we have

P (A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{k}}) = P (A_{i_{1}}) ∗ P (A_{i_{2}}) ∗ ⋯ ∗ P (A_{i_{k}})  (1.4)

Just as a note, statistically independent events are uncorrelated, but the converse is not necessairly true. Example 1.2.4. One can consider tossing two fair coins. Let heads=1 and tails=0. Let E_{1} = value of coin #1 and E_{2} =value of coin #2. If one flips the coins, then E_{1} and E_{2} are independent. Let us now define E_{3} = sum of E_{1} and E_{2}. Clearly, the event space of E_{3}=(0,1,2), but E_{3}, E_{1}, and E_{2} are not independent of each other when all three events are considered together. Now if we were to compute P (E_{1} = 0|E_{2} = 0), this probability is just P (E_{1} = 0) = .50. Introducing E_{3}, we compute P (E_{1} = 0|E_{3} = 2), this probability is now \frac{P (E_{1}=0 ∩ E_{3}=2)}{P (E_{3}=2)} = 0.

This example is important because it illustrates that two events considered separately may be independent, but if one introduces a separate event where E_{1} and E_{2} are considered together, then given the knowledge of E_{3}, the events E_{1} and E_{2} are no longer independent. In other words, two events may be independent, but upon introducing a third event, the three events considered together are no longer independent. Any two of the events are independent, but once two events are decided, the third event’s value is determined. The situation becomes one in which conditional probability needs to be considered. Further examples and definitions can be found in [Dev].

Continued Fractions

2.1 Basic Continued Fraction Theory

In this chapter, I merely want to build the case for using continued fractions and to state some basic theorems and facts about continued fractions. Many of the statements will go without proofs, but [Ni] is a great source for many of the proofs.

Recall the definition of a continued fraction:

Definition 2.1.1. A finite continued fraction is a number of the form

a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+_{\frac{1}{^{...}+ \frac{1}{an}}}}}}  (2.1)

This continued fraction can be represented as [a_{0}, a_{1}, …, a_{n}]

An infinite continued fraction is of the same form except the representation does not terminate. The numbers with which I experimented all possessed infinited continued fraction representations, but I truncated the expansion at n = 500, 000. We shall present a few definitions followed by an important theorem.

Definition 2.1.2. (Positive Continued Fraction) A continued fraction [a_{0}, a_{1}, ….a_{n}] is positive if each a_{i} > 0 [TMHS].

Definition 2.1.3. (Simple Continued Fraction) A continued fraction is simple if each a_{i} is a positive integer, except for possibly i = 0 [TMHS].

Definition 2.1.4. (Convergents) If x_{m} = [a_{0}, a_{1}, …, a_{n}] = \frac{p_{m}}{q_{m}}, then \frac{p_{m}}{q_{m}} is m-th convergent [TMHS].

2.2 How to find the quotients of a continued fraction

Aside from other methods such as the Lang-Trotter method, the ’old-fashioned’ way of ascertaining the quotients of a continued fraction expansion employs the Euclidean algorithm. Omitting the details of the Euclidean algorithm, we expect to arrive at x’s unique continued fraction expansion representation [TMHS].

x = a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+ \frac{1}{...}}}}  (2.2)

where we can assume that this continued fraction is simple. To begin the expansion we take a_{0} to be the greatest integer less than x, [x]. Henceforth, the remainder of the continued fraction expansion represents the remainder of x-[x].

x − [x] = \frac{1}{a_{1} + _{\frac{1}{a_{2}+ \frac{1}{...}}}}  (2.3)

taking the recriprical, we know that

x_{1} = \frac{1}{x − [x]} = a_{1} + \frac{1}{a_{2} + _{\frac{1}{a_{3}+ \frac{1}{...}}}}  (2.4)

again, extending the process, a_{1} = [x_{1}], then we repeat the process for x_{2} until our continued fraction repeats or terminates. So x_{2} = \frac{1}{x_{1}−[x_{1}]}.

Since we assumed that x’s continued fraction representation was simple, the only modification needed if x < 0 is to allow a_{0} < 0. It is also important to reiterate that a_{i} ≥ 1 for all 1 ≤ i ≤ m since x_{i+1} < x_{i}.

2.3 Uniqueness and Property of Infinite Continued Fraction Expansions

We shall omit the proof, but a continued fraction is the best rational approximation to a given irrational number. However, to be sure that only one such expansion exists, it is necessary to prove the uniqueness of a continued fraction expansion. Along the same lines, the further we expand the continued fraction, the better approximation we achieve.

Theorem 2.3.1. Let x = [a_{0}, a_{1}, …, a_{n}] = [b_{0}, b_{1}, …, b_{m}] be continued fractions with a_{n}, b_{m} > 1. Then N = M and a_{i} = b_{i} for i = 0 to N = M.

Proof: From [TMHS] we proceed by induction. Let a_{0} = [x], b_{0} = [x]. If [a_{0}, …, a_{n}] = [b_{0}, …, b_{n}] then [[x], [a_{1}, …, a_{n}]] = [[x], [b_{1}, …, b_{m}]] from which we see that

[x] + \frac{1}{[a_{1}, …, a_{n}]} = [x] + \frac{1}{[b_{1}, …, b_{m}]}  (2.5)

Thus, [a_{1}, …, a_{n}] = [b_{1}, …, b_{m}]. Since we have m, n terms instead of m + 1 or n + 1, the proof follows by induction. □

Two lemmas are necessary to prove the main theorem of this section. The lemmas will go without proofs because we are only interested in their results.

Lemma 2.3.2. A real number α is irrational if and only if for any positive ϵ there exists infinitely many pairs of integers (x,y) such that 0 < |αx − y| < ϵ

Proof: see[Ni]

Lemma 2.3.3. If the quotients a_{0} to a_{n} are positive, then the sequence x_{2m} is an increasing sequence, the sequence x_{2m+1} is a decreasing sequence, and for every m, x_{2m} < x < x_{2m+1} (if n ≠ 2m or 2m + 1)

Proof: [TMHS]

Theorem 2.3.4. Any infinite simple continued fraction [b_{0}, b_{1}, …] is an irrational number.

Proof: From [Ni]: Let θ = [b_{0}, …] be an infinite continued fraction. We see by Lemma 2.3.3 that θ lies between consecutive convergents x_{n} and x_{n+1}, or between \frac{p_{n}}{q_{n}} and \frac{p_{n+1}}{q_{n+1}} . Thus by a lemma not proved here, we have

0 < |q_{n}θ − p_{n}| = q_{n} ∗ |θ − x_{n}| < q_{n} ∗ |x_{n+1} − x_{n}|
= q_{n} ∗ \frac{1}{q_{n} ∗ q_{n+1}} = \frac{1}{q_{n+1}}  (2.6)

Now, we know that the q_{n} are positive integers, increasing with n. Given any positive ϵ, we can find infinitely many pairs p, q such that 0 < |qθ − p| < ϵ. Hence, by 2.3.2, θ is irrational □

So we have established that infinite continued fractions are the best obtainable approximations to irrational numbers. In addition, the continued fraction of an irrational or rational number is unique. Therefore, when examining a continued fraction expansion of a number, we need not worry that other possible results exist.

More specifically, the numbers that I examined and the results that I extracted from the continued fraction expansions of the cube roots of the certain primes are results that will not vary given a different method used to calculate the continued fraction expansion (uniqueness). Since the numbers that I chose to examine are irrational, we also do not need to concern ouselves with the possibility that the continued fraction is repeating or will terminate after some point. If the continued fraction expansions repeated or were finite, then we could calculate with full confidence the properties and dependencies of a_{n} and a_{n−1} in the continued fraction expansion. However, since the numbers that I examined did not repeat and we can prove that the expansion is infinite, our confidence in the results obtained will be limited because we are examining a proper subset of the full continued fraction expansion. This experiment will be more of a verification of Kuzmin’s theorem at a given precision (500,000 digits),therefore, the results obtained should suffice.

Kuzmin’s Theorem

3.1 General Comments

As an introduction to Kuzmin’s Theorem, I will present the general statement and implications of this theorem and then provide technical details. Given a random number x ∈ (0, 1) there exists a continued fraction expansion for this number. The probability that the i^{th} coefficient of the continued fraction expansion assumes

value k is given by a probability distribution function ∫_{\frac{1}{k+1}}^{\frac{1}{k}} \frac{1}{ln2} ∗ \frac{1}{1+x} dx, which upon

integrating results in log_{2} (1 + \frac{1}{k∗(k+2)})+error(n, k), where the error is a function of n and k and is

error(n, k) = \frac{C_{1}}{k(k + 1)} · e^{−C_{2}\sqrt{n−1}}  (3.1)

The error term decreases exponentially as n → ∞, which means that for a large n, the probability that a_{n}(x) = k is independent of n.

We can generalize Kuzmin’s Theorem to include any number x by considering x − [x] where [ ] is the greatest integer function. Kuzmin’s Theorem is true for all x ∈ (0, 1) except for a set of M = 0

3.2 Detailed Analysis of Kuzmin’s Theorem

Let α ∈ (0, 1) and examine the first element of the continued fraction expansion. (Much of the following analysis, notation, and proofs can be found in [Ki])

\frac{1}{α} = a_{1} + \frac{1}{a_{2} + ⋯}  (3.2)

Thus a_{1} = [\frac{1}{α}], such that if a_{1} = k, then it follows that k ≤ \frac{1}{α} < k + 1 and \frac{1}{k+1} < α ≤ \frac{1}{k}. This inteval is an interval of first rank. The function a_{1} = a_{1}(α) has a discountinuity at all those values of α for which \frac{1}{α} is an integer, and it increases without bound as α approaches 0 [Ki]. The analysis for a_{2} follows in the same fashion where we will allow a_{2} = l, which implies that \frac{1}{k+ \frac{1}{l}} ≤ α < \frac{1}{k+ \frac{1}{l+1}} . This interval is an interval of the second rank.

Now let us suppose that the first n coefficients are determined, such that α = [a_{1} = k_{1}, a_{2} = k_{2}, …, a_{n} = k_{n}, …]. The interval of rank n corresponds to (\frac{p_{n}}{q_{n}} , \frac{p_{n}+p_{n−1}}{q_{n}+q_{n−1}} ), where \frac{p_{k}}{q_{k}} are the convergents of the number α of order k.

Let J_{n} be the rank of order n of the continued fraction expansion of α and J_{n+1} be defined correspondingly. For all points in the interval J_{n+1} we have a_{n+1} = [r_{n+1}] = s, and hence s ≤ r_{n+1} < s + 1, Thus among all the points

α = \frac{p_{n}r_{n+1} + p_{n−1}}{q_{n}r_{n+1} + q_{n−1}}  (3.3)

of the interval J_{n}, those for which s ≤ r_{n+1} < s + 1 belong to the interval J_{n+1}, such that we have:

α = \frac{p_{n}r_{n+1} + p_{n−1}}{q_{n}r_{n+1} + q_{n−1}}  (3.4)

The endpoints of J_{n+1} are then (\frac{p_{n}s+p_{n−1}}{q_{n}s+q_{n−1}} , \frac{p_{n}(s+1)+p_{n−1}}{q_{n}(s+1)+q_{n−1}} ). Through a bit of algebraic manipulation, we culminate with

\frac{MJ_{n}}{3s^{2}} < MJ_{n+1} < \frac{2MJ_{n}}{s^{2}}  (3.5)

We will now develop some technical results and conclude with a statement of Kuzmin’s Theorem, much of this analysis, etc can be found in [TMHS]

Kuzmin showed that if a sequence of functions (f_{n})_{n} satisfies the relation

f_{n+1}(x) = ∑_{k=1}^{∞} \frac{1}{(m + x)^{2}} f(\frac{1}{k + x})  (3.6)

and we have some bounds on f_{1}(x), call the bound B such that 0 < f_{1}(x) < B, f1^{′}(x) < B, then we find by background analysis found in [TMHS]

f_{n}(x) = \frac{a}{1 + x} + C_{1}e^{−C_{2}\sqrt{n}}, where a = \frac{1}{ln 2} ∫_{0}^{1} f_{1}(x) dx  (3.7)

These conditions enable us to prove that Theorem 3.2.1. Let α be chosen uniformly in (0,1). Then

P (a_{n}(x) = k) = log_{2} (1 + \frac{1}{k(k + 2)}) + \frac{C_{3}}{k(k + 1)}e^{−C_{2}\sqrt{n−1}}  (3.8)

Proof: We construct the following notation [TMHS]

α = \frac{1}{a_{1} + _{\frac{1}{a_{2}+ \frac{1}{a_{3}+···}}}}
z_{n}(α) = \frac{1}{a_{n+1} + _{\frac{1}{a_{n+2}+ \frac{1}{a_{n+3}+···}}}}
m_{n}(x) = |(α ∈ (0, 1) : z_{n}(α) < x)|
m_{n+1} = ∑_{k=1}^{∞} m_{n}(\frac{1}{k}) − m_{n}(\frac{1}{k + x})  (3.9)

The probability we want is

m_{n−1}(\frac{1}{k}) − m_{n−1}(\frac{1}{k + x}) = ∫_{\frac{1}{k+1}}^{\frac{1}{k}} mn−1^{′}(x) dx  (3.10)

Now, f_{n}(x) = m′(x) satisfies Equations 3.6 and 3.7 and the result is a simple integration. The error term may be taken as Ae^{−λn} [Le]

Expected Results and Kuzmin Applied

4.1 General Case

I shall present the general case and perform one sample calculation. The remaining eight cases are simple applications of the general case.

Kuzmin’s theorem gives us the probability distribution function that a_{n}(x) = k given a specific n, where a_{n}(x) is the n^{th} quotient in the continued fraction expansion and k ∈ Z > 0. However, Kuzmin’s theorem is only generally true, meaning that this probability distribution function is true for most k and for most x, where x is the number that we are representing with a continued fraction expansion. Formally, Kuzmin states that except for a set of measure 0, if one chooses randomly a number x ∈ (0, 1), then the probability that a_{n}(x) = k is q_{k} + error(n, k), where q_{k} is the probability and the error term is a function of n and k. It is important to note that the error term gets exponentially smaller as n increases. Furthermore, Kuzmin’s theorem holds in general in the limit, or as the n → ∞, where n in the n in a_{n}(x). Given all of these constraints, we can still test the validity of Kuzmin’s theorem with a precision of only 500,000. The probability distribution function excluding the error term given by Kuzmin is

\frac{1}{ln2} ∗ \frac{1}{1 + x}  (4.1)

Integrating this function from \frac{1}{k+1} to \frac{1}{k} will give the probability of observing a_{n}(x) = k.

∫_{\frac{1}{k+1}}^{\frac{1}{k}} \frac{1}{ln2} ∗ \frac{1}{1 + x} dx = cumulative distributive function

simplifying = log_{2} (1 + \frac{1}{k ∗ (k + 2)}) + error(n, k)
log_{2} (1 + \frac{1}{k ∗ (k + 2)}) + error(n, k) = P (a_{n} = k)  (4.2)

The justification for calculating the probability this way is that according to Kuzmin, if we randomly choose n and look at the quotient a_{n}(x), then Kuzmin gives a numerical value for P (a_{n}(x) = k_{1}). When n is large the error term tends towards 0, thus we disregard the first n−1 and n+1 (and onward) terms; we have a probability distribution function for a_{n}(x) at n. Since the value of the continued fraction’s tail is limited once we assign a_{n}(x) = k_{1}, we ascertain that the value continued fraction’s (n+1)^{th} tail can be no larger than \frac{1}{k_{1}} and no smaller than \frac{1}{k_{1}+1}, and these two bounds give all the possible continued fraction representations given that a_{n}(x) = k_{1}. Therefore the probability that a_{n+1}(x) = k_{2} has been affected because a_{n+1} = k_{2} must be chosen only from intervals where a_{n} = k_{1}, which reduces to a conditional probability problem.

Now the results become a bit trickier. We are looking at a conditional probability; given a_{n}(x) = k_{1}, what is the probability that a_{n+1}(x) = k_{2}? To calculate this probability we must look within the subinterval of the probability function where a_{n}(x) = k_{1}, and then calculate the probability that a_{n+1}(x) = k_{2} within that interval. Naively, one might conclude from Kuzmin that the probability of a_{n+1}(x) = k_{2} is log_{2} (1 + \frac{1}{k_{2}∗(k_{2}+2)}), but we have have restricted the domain from which we can choose a_{n+1}(x) because a_{n}(x) = k_{1}. If the quotients of the continued fraction are independent then P (a_{n+1}(x) = k_{2}|a_{n} = k_{1}) should just be P (a_{n+1}(x) = k_{2}), so from the above probability functions:

P (a_{n+1} = k_{2}|a_{n} = k_{1}) = \frac{P (a_{n+1} = k_{2} ∩ a_{n} = k_{1})}{P (a_{n} = k_{1})}  (4.3)

If a_{n}(x) and a_{n+1}(x) are independent, then the above equation should reduce:

P (a_{n+1} = k_{2}|a_{n} = k_{1}) = \frac{P (a_{n+1} = k_{2}) ∗ P (a_{n} = k_{1}))}{P (a_{n} = k_{1})} = P (a_{n+1} = k_{2}) (4.4)

We shall see shortly that given the data, we can tentatively conclude that a_{n+1}(x) is not independent of a_{n}(x)’s value. Disregarding the first n − 1 and n + 1 (and onwards) terms again, if a_{n}(x) = k_{1}, then x is bounded irrespective of k_{2}, or in other words, the domain from which we can choose a_{n+1}(x) has been constricted.

\frac{1}{k_{1} + 1} ≤ x ≤ \frac{1}{k_{1}}  (4.5)

Therefore, to find the probability that a_{n+1}(x) = k_{2}, we use the Kuzmin’s probability distribution function as before, but this time our upper and lower bounds change slightly to account for new restrictions on the values that x can assume. We can attempt to characterize this situation as given a_{n}(x) = k_{1} in the continued fraction expansion, there are a limited, but infinte amount of numbers x ∈ (0, 1) having a continued fraction expansion such that a_{n}(x) = k_{1}. So within this subset of numbers where a_{n}(x) = k_{1}, we look at the cases where a_{n+1}(x) = k_{2} and so on for extended cases.

P (a_{n+1} = k_{2} ∩ a_{n} = k_{1}) = \frac{1}{ln2} ∫_{\frac{1}{k_{1}+ \frac{1}{k_{2}}}}^{\frac{1}{k_{1}+ \frac{1}{k_{2}+1}}} \frac{1}{1 + x} dx

P (a_{n} = k_{1}) = \frac{1}{ln2} ∫_{\frac{1}{k_{1}+1}}^{\frac{1}{k_{1}}} \frac{1}{1 + x} dx

P (a_{n+1} = k_{2}|a_{n} = k_{1}) = \frac{∫_{\frac{1}{k_{1}+ \frac{1}{k_{2}}}}^{\frac{1}{k_{1}+ \frac{1}{k_{2}+1}}} \frac{1}{1+x} dx}{∫_{\frac{1}{k_{1}+1}}^{\frac{1}{k_{1}}} \frac{1}{1+x} dx}  (4.6)

Clearly, in the above set of equations, the constant \frac{1}{ln2} in both the denominator and numerator cancel in the final equation.

In attempting to arrive at a true expected value of the number of occurrences of (a_{n}(x) = k_{1}, a_{n+1}(x) = k_{2}) in a given continued fraction expansion of m quotients, we must use Kuzmin’s theorem to make the jump from knowing the expected value of a_{n}(x) = k to generalizing for all m quotients. We know the P (a_{n}(x) = k) for any specific n from Kuzmin’s Theorem, now how can we generalize this to make statements about all the quotients together? We will essentially define one event as the sum of simple events, whose probability is known to us. Then we can make statements about the one total event. I shall build the general case for a_{n}(x) = k and then generalize to the pair (a_{n}(x) = k_{1}, a_{n+1}(x) = k_{2}).

Problem 4.1.1. Let the event A_{n,k}(x) be defined as such:

A_{n,k}(x) = \begin{cases}1 & if a_{n}(x) = k \\ 0 & otherwise \end{cases}  (4.7)

n is the index used to label the specific quotients of the continued fraction expansion of x. a_{n}(x) is the n^{th} quotient of this continued fraction expansion. The expected value for A_{n,k}(x) at any position in the continued fraction expansion n:

E[A_{n,k}(x)] = 1 ∗ q_{k} + 0 ∗ (1 − q_{k})  (4.8)

Allow the continued fraction expansion to be expanded to m terms. Let us

further define w(x) = ∑_{n=1}^{n=m} A_{n,k}(x), meaning that w(x) is the number of k’s in

the first m quotients of the continued fraction expansion of x. We can begin the summation at n = 1, however, one must be mindful of the larger error term given that n is small. We can adjust our summation according to our error tolerance by letting n = r, where r > 1. The expected value of w(x) is essentially E[w(x)] = q_{k}, at which we arrive by using the linearity of expected values. The argument for this problem and the next is adapted from [LT] and [TMHS].

E[w(x)] = E[ ∑_{n=1}^{n=m} A_{n,k}(x)]

∑_{n=1}^{n=m} E[A_{n,k}(x)] = ∑_{n=1}^{n=m} P (a_{n}(x) = k)  (4.9)

but from Kuzmin we know that

P (a_{n}(x) = k) = log_{2}(1 + \frac{1}{k ∗ (k + 2)}) + error(n, k)  (4.10)

we are left with

∑_{n=1}^{n=m} E[A_{n,k}(x)] = m ∗ (q_{k} + error)
= E[w(x)]  (4.11)

where q_{k} = log_{2}(1 + \frac{1}{k∗(k+2)}) is simply Kuzmin’s calculation without the error term for P (a_{n}(x) = k) . So given this construction, we now have Kuzmin’s estimate of how many k’s we should observe in the first m quotients. It is advisible to begin examiniation of a continued fraction expansion at a larger n than n = 1 because the results of Kuzmin’s Theorem imply that the error term in the above calculations decreases exponentially with an increasing n. Therefore the P (a_{n}(x) = k) and E[w(x)] for a large enough n should be independent of n. As a quick concrete example we look to [TMHS]. If we were to look at digits of a continued fraction expansion from n = 50001 to n = 100000, the number of ones (k = 1) we would expect to observe would be

50000 · log_{2}(1 + \frac{1}{1(1 + 2)}) ≈ 50000 · q_{1} = 50000 · .415  (4.12)

Again, reemphasizing that given a large enough n we may disregard the error term.

The next problem will justify why we may expect the results of the experiment at hand (given that we have 500,000 terms in a continued fraction expansion, what is the probability that we will see (a_{n}(x) = k_{1}, a_{n+1}(x) = k_{2}) where n and n + 1 are general indicies, or we have not specified the value of n) We approach the problem in a similar fashion to the previous problem, in that we use the knowledge (Kuzmin’s Theorem) of single events to define a total event that encompasses our event space. The result of this problem will prove that in general (general, because we are assuming that the error term is neglible) that we can use Kuzmin’s theorem to justify our theoretical predictions about the properties of our 500,000-quotient continued fraction expansion. In other words, we want to fix k_{1} and k_{2} and see how many occurrences of the pair (k_{1}, k_{2}) we observe in the first 500,000 digits of the continued fraction expansion. From the above analysis of Kuzmin’s Theorem, we note again that q_{k_{1},k_{2}} ≠ q_{k_{1}} ·q_{k_{2}}. What we will show is that Kuzmin’s Theorem predicts that the probability that a_{n}(x) = k_{1} and a_{n+1} = k_{2} is q_{k_{1},k_{2}} (calculated above) plus a small error term.

Problem 4.1.2. Let us define B_{n,k_{1},k_{2}}(x) to be the function such that :

B_{n,k_{1},k_{2}}(x) = \begin{cases}1 & if a_{n}(x) = k_{1} and a_{n+1}(x) = k_{2} \\ 0 & otherwise \end{cases}  (4.13)

Where n, m, k_{i}, and a_{n} are defined as above. Let us construct an event v(x) =

∑_{n=1}^{n=m} B_{n,k_{1},k_{2}}(x): v(x) is the number of times that we see the pair (a_{n} = k_{1}, a_{n+1} =

k_{2}) in our m quotient continued fraction expansion of x. Reemphasizing, we are not looking at a specific value of n, we are testing this case for all n such that 1 ≤ n ≤ m. The expected value of v(x) is E[v(x)] = 1 · q_{k_{1},k_{2}} + 0 · (1 − q_{k_{1},k_{2}}). Again by the linearity of expected values:

E[v(x)] = E[ ∑_{n=1}^{n=m} B_{n,k_{1},k_{2}}(x)]

∑_{n=1}^{n=m} E[B_{n,k_{1},k_{2}}(x)] = ∑_{n=1}^{n=m} P (a_{n+1}(x) = k_{2} ∩ a_{n}(x) = k_{1}) (4.14)

we know from Kuzmin that

P (a_{n+1}(x) = k_{2} ∩ a_{n}(x) = k_{1}) = ∫_{\frac{1}{k_{1}+ \frac{1}{k_{2}}}}^{\frac{1}{k_{1}+ \frac{1}{k_{2}+1}}} \frac{1}{1 + x} dx + error(n, k)

= q_{k_{1},k_{2}} + error(n, k)  (4.15)

which justifies:

∑_{n=1}^{n=m} E[B_{n}(x)] = m · (q_{k_{1},k_{2}} + error) = E[v(x)]  (4.16)

4.2 (1,1) Case

Let us calculate the expected results given Kuzmin’s theorem for the case P (a_{n+1}(x) = 1|a_{n}(x) = 1). We justify these calculations from the results of the above problems.

P (a_{n} = 1) = \frac{1}{ln2} ∫_{\frac{1}{2}}^{1} \frac{1}{1+x} dx = .415038

P (a_{n+1} = 1 ∩ a_{n} = 1) = \frac{1}{ln2} ∫_{\frac{1}{2}}^{\frac{2}{3}} \frac{1}{1+x} dx = .152003

P (a_{n+1} = 1|a_{n} = 1) = \frac{∫_{\frac{1}{2}}^{\frac{2}{3}} \frac{1}{1+x} dx}{∫_{\frac{1}{2}}^{1} \frac{1}{1+x} dx} = .366239  (4.17)

If a_{n}(x) and a_{n+1}(x) were independent, then we would have the following results:

P (a_{n+1} = k_{2}|a_{n} = k_{1}) = \frac{P (a_{n+1} = k_{2}) ∗ P (a_{n} = k_{1})}{P (a_{n} = k_{1})}
= \frac{.415^{2}}{.415} = .415
= P (a_{n+1} = 1)  (4.18)

In the (1,1) case, a_{n}(x) and a_{n+1}(x) are not independent, which is expected given Kuzmin’s Theorem. Randomly selecting an a_{n}(x) and looking at it in isolation should result in a probability according to Kuzmin’s probability distribution function for any n. When we select an a_{n}(x) and look at its surrounding terms, then the problem becomes a conditional probability situation.

Results

5.1 Brief Motivation

We chose to examine the cube roots of prime numbers because of the similar algebraic properties of the cube roots of the first 100 primes and the cube roots of the first 100 primes larger than 10^{6}. Three notable are properties listed below.

1. Each number examined is algebraic of degree three and irrational, obviously being the solution to the irreducible polynomial x^{3} − p = 0. For all primes, this equation is irreducible by Eisenstein’s criterion (set the Eisenstein’s divisor q = p).

2. For each prime, the equation x^{3} − p = 0 has the same Galois Group. Given that f(x) = x^{3} −p, p prime then the discriminate of f is simply DISC=−27∗p^{2} = D. D is never a perfect square because it is always negative. Thus, since f(x) is irreducible, then the Galois group is the symmetric group on 3 elements S_{3}. There are no integer roots as long as p > 1. [Lang]

3. Each number examined is the cube root of a prime number. We included no composite numbers in our analysis. Given the special and mysterious nature of prime numbers, we can justly label this property as important.

Given these three algebraic properties, we should expect that each number behaves roughly the same. By behaves we mean, their continued fraction expansions should have similar general properties. If we were to compare algebraic numbers of degree 2 with our sample, then we would not necessairly expect this similarity (in fact the continued fraction expansion is not comparable because the continued fraction expansion for degree 2 algebraic irrational numbers is periodic).

5.2 Method

The algorithm used to calculate the number of (1,1)’s, (1,2)’s, (1,3)’s, (2,1)’s, (2,2)’s, (2,3)’s, (3,1)’s, (3,2)’s, and (3,3)’s was rather elementary. First I generated a list of the first 100 primes and the first 100 primes greater than 10^{6}, calling this list L. Then using Mathematica, I calculated the continued fraction expansion of \sqrt[3]{p}, where p ∈ L, up to 500,000 quotients.

I then commanded Mathematica to count the total number of occurrences of the digits (1),(2),(3) in the continued fraction expansion. Since Mathematica stores the expansion in a list, I partitioned the list into elements of two. I then deleted the first element from the list and partitioned the remaining 499,999 terms into pairs. Then Mathematica counted the number of pairs of (1,1), (1,2), etc in both lists. These results were documented in MS Excel, and several statistical tests were performed on the data, such as the mean, standard deviation, max, and min. The results are appended to this paper.

Armed with the general method and the sample (1,1) case, we now present the results for the remaining cases.

5.3 Results

To understand how the results compare to Kuzmin’s Theorem, let us summarize what Kuzmin predicts and what we actually observed. We are trying to determine whether our class of numbers exhibits the depenedencies that Kuzmin predicts. Recall that Kuzmin gives us an explicit formula for calculating the expected dependencies:

P (a_{n+1} = k_{2}|a_{n} = k_{1}) = \frac{∫_{\frac{1}{k_{1}+ \frac{1}{k_{2}}}}^{\frac{1}{k_{1}+ \frac{1}{k_{2}+1}}} \frac{1}{1+x} dx}{∫_{\frac{1}{k_{1}+1}}^{\frac{1}{k_{1}}} \frac{1}{1+x} dx}  (5.1)

To calculate this probability we needed to ascertain the P (a_{n}(x) = k_{1}) and P (a_{n}(x) = k_{1} ∩ a_{n+1} = k_{2}). We derived these probabilities in the last section and justified our usage of them in the two sample problems by using the linearity of expected values and Kuzmin’s Theorem. Now we must compare these results to our actual results, which are summarized in the following tables. Several statistical tests were performed on our data set of 200 samples (mean, std., max, min).

We obtained our results by averaging over all the samples. Case (1) represents the percentage of coefficients that assumed value k = 1 in the 500,000 coefficient expansion. (1,2) represents the P (a_{n+1}(x) = 2|a_{n}(x) = 1). This probability was calculated by counting the number of coefficients with value (1) and counting the number of occurrances of the pair (1,2). We then divided the occurrences of the pair by the number of 1’s in the continued fraction expansion to arrive at our desired probability. This calculation is an application of the conditional probability formula P (A|B) = \frac{P (A∩B)}{P (B)}. The rest of the representations follow this form. The standard deviation, is the standard deviation over 200 samples of cube roots. All numbers are represented in decimal form, so that .4150 = 41.50%. Numbers were rounded down.

\begin{matrix}\underline{Case} & \underline{Actual} & \underline{Kuzmin} & \underline{mean − σ} & \underline{mean + σ} & \underline{σ} \\ 1 & .41501 & .41503 & .41397 & .41605 & .00104 \\ (1,1) & .36630 & .36623 & .36515 & .36745 & .00115 \\ (1,2) & .16963 & .16959 & .16874 & .17052 & .00089 \\ (1,3) & .09788 & .09792 & .09720 & .09855 & .00067 \\ 2 & .16994 & .16992 & .16938 & .17049 & .00055 \\ (2,1) & .41436 & .41423 & .41274 & .41597 & .00161 \\ (2,2) & .17153 & .17152 & .17021 & .17284 & .00131 \\ (2,3) & .09375 & .09381 & .09276 & .09474 & .00099 \\ (3) & .09308 & .09310 & .09266 & .09349 & .00041 \\ (3,1) & .43639 & .43649 & .43425 & .43852 & .00213 \\ (3,2) & .17137 & .17121 & .16953 & .17321 & .00184 \\ (3,3) & .09153 & .09141 & .09023 & .09283 & .00130 \end{matrix}

From this chart it seems that the numbers examined indeed confirm Kuzmin’s predicted dependencies. For example, Kuzmin predicted that we should observe a 2 in the n^{th} position after observing a 1 in the (n − 1)^{th} position 16.959% of the time. The actual observed occurrance rate was 16.963%. The remaining results follow in a similar fashion. The greatest disparity was in the (3,2) case, where we observed a .016% difference from Kuzmin’s prediction. This difference is not signifignant enough to reject the hypothesis that these numbers behave as Kuzmin expects. All of Kuzmin’s predicted values fell within the standard deviation of the mean of the sampled numbers. We present now the results in terms of the actual number of occurrances of each case in the 500,000 digit expansion.

The numbers were again rounded down (i.e. mean, kuzmin, std). For the (1), (2), (3) case, Kuzmin’s prediction was calculated by multiplying the expected probability of the given case by 500,000. For the remaining cases, Kuzmin’s prediction was calculated in a similar fashion to the following sample calculation for (1,2): Kuzmin’s predicted probability P (a_{n} = 2|a_{n−1} = 1) · the total occurrence of the value (a_{n−1} = 1).

\begin{matrix}\underline{Case} & \underline{Actual} & \underline{Kuzmin} & \underline{mean − σ} & \underline{mean + σ} & \underline{σ} \\ 1 & 207536 & 207515 & 207209 & 207863 & 327 \\ (1,1) & 76021 & 76008 & 75693 & 76349 & 328 \\ (1,2) & 35206 & 35197 & 35028 & 35384 & 178 \\ (1,3) & 20314 & 20322 & 20173 & 20455 & 141 \\ 2 & 84971 & 84960 & 84693 & 85249 & 278 \\ (2,1) & 35209 & 35198 & 35043 & 35375 & 166 \\ (2,2) & 14575 & 14574 & 14438 & 14712 & 137 \\ (2,3) & 7966 & 7971 & 7879 & 8053 & 87 \\ (3) & 46542 & 46550 & 46333 & 46751 & 209 \\ (3,1) & 20311 & 20315 & 20171 & 20451 & 140 \\ (3,2) & 7975 & 7968 & 7888 & 8062 & 87 \\ (3,3) & 4260 & 4254 & 4192 & 4328 & 68 \end{matrix}

Once again the largest difference (21) (case(1, 1)) between the observed value and this difference is trivial compared to our sample size of 500,000. These results show with great confidence that these sampled numbers behave as Kuzmin expected, at least when considering the first 500,000 coefficients. Kuzmin’s predicted values were well within our (mean ±σ) range. In fact, in all cases, we could have divided our standarded deviation by 10, used this reduced figure as our σ, and Kuzmin’s predicted values would have fallen within the mean (±σ_{reduced}).

I must note that the examination of these continued fraction expansions began with n = 1 therefore we would expect the error to be larger than had I begun with n = r where r is larger than 1000. (1000 was chosen arbitrarily, but the error predicted by Kuzmin would be of order \frac{1}{e^{\sqrt{1000}}} ). Altough the error term involved with my calculations should be at its maximum value, our results coroborate Kuzmin’s Theorem with complete confidence.

An interesting question to answer is if these percentages or number of occurrences conform to a normal distribution. However, after plotting the histograms in MS Excel, the results were not convincing. Most of the distributions were either positively skewed or bimodal. Possibly with a larger sample, we may observe a distribution closer to the normal distribution.

Conclusion

Concluding this experiment to verify Kuzmin’s Theorem, we observed that the coefficients of the continued fraction expansion of cube roots of primes (at least the ones considered) do exhibit the same dependencies that Kuzmin’s Theorem forecasts. However, there are still many questions to be answered in the quest to find whether an algebraic class of numbers comports with Kuzmin’s Theorem or can be considered an exception. The irrational algebraic numbers of degree 2 and e are two such classes, but other experimenters may investigate additional numbers or classes of numbers that violate Kuzmin’s expectation. Another interesting question to answer that directly relates to the problem discussed by this paper is if one were to expand the continued fraction expansion to m = 10^{10}, would we expect the standard deviation to lessen, would the distribution of percentages reflect a known distribution (Poisson, Normal, etc).

Because Kuzmin’s Theorem holds in the limit, we can never be certain about the properties of a continued fraction expansion, unless the continued fraction is finite or periodic. Despite this restriction, our precision of 500,000 coefficients should give a good approximation as to the properties of these numbers examined. Another experiment is to start the examiniation of these continued fractions at a larger beginning value, so as to reduce the error term. I would suspect that the mean would converge to Kuzmin’s estimate.

Finally, a fantastic problem would be to examine how a_{n+2} depends on the value of a_{n} and a_{n+1}. Applying Kuzmin’s Theorem to ascertain the expected probabilities would be an easy extension of this paper, but calculating the actual numbers could become tricky because the algorithm that I implemented for this experiment may be inexpedient for such an experiment. Lastly, a side experiment that I conducted (but did not have enough data from which to draw any definitive conclusions) is to calculate the dependency of the a_{n+1}^{th} coefficient in a given continued fraction expansion where it is given that a_{n} assumes the largest value in the expansion of m coefficients. My initial results showed that a_{n+1} = 1 over 50% of the time. Is this what we should expect? The search is still underway to explain the intricies of and exceptions to Kuzmin’s Theorem, but we are now virtually confident that numbers satisfying the algebraic equation x^{3} − p = 0 are not exceptions.

Bibliography

[Dev] J.Devore, Probability and Statistics for Engineering and the Sciences, Fifth Edition. Duxbury Thomson Learning, Pacific Grove, 2000, pp. 75 − 92.

[Ki] A. Y. Khinchin, Continued Fractions, Third Edition, The University of Chicago Press, Chicago 1964.

[Lang] S. Lang, Algebra 3rd Edition, Addison-Wesley Publishing Company, Reading, Mass. 1993 pp. 270.

[LT] S. Lang and H. Trotter, Continued fractions for some algebraic numbers, J. Reine Angew. Math. 255, 1972, 112 − 134.

[Le] P. Lévy, Sur les lois de probabilité dont dependent les quotients complets et incomplets d’une fraction continue, Bull. Soc. Math., 57, 1929, 178 − 194.

[TMHS] S. Miller, R. Takloo-Bighash, H. Helfgott, and F. Spinu, Junior Research Seminar: Diophantine Analysis and Approximations, Princeton University, Princeton, 2002.

[Ni] I. Nivan, Irrational Numbers, Pub: The Mathematical Association of America, Dist: by John Wiley and Sons, Inc., Print: Quinn & Boden Company Inc., 1956.