4
$\begingroup$

Is there anything known about the asymptotic expected growth of $card\{a_0,a_1,...,a_n\}$, where the $a_i$ are the first $n$ coefficient of a continued fraction $[a_0; a_1, ... ]$?

$\endgroup$
4
  • $\begingroup$ What does this mean? You are asking about the cardinality of a set of $n+1$ elements??? $\endgroup$
    – Igor Rivin
    Aug 18, 2015 at 14:00
  • 1
    $\begingroup$ @IgorRivin no, as the $a_i$ need not be distinct, there may (or better will) be fewer than $n$ distinct elements in the set. I agree that my notation is misleading, but I don't know how to express the set that contains the first $n$ parameters of the continued fraction. Any suggestions are highly welcome. $\endgroup$ Aug 18, 2015 at 14:49
  • $\begingroup$ At least for quadratic irrational numbers, the cardinality is bounded above. $\endgroup$ Aug 18, 2015 at 14:56
  • $\begingroup$ yes, it actually is $O(1)$, but the interesting question is, whether some expected growth could be quantified; I guess there should be something in that line in analogy to the Khinchin constant or the Levy constant. $\endgroup$ Aug 18, 2015 at 14:59

2 Answers 2

3
$\begingroup$

Since the question asks about an expectation, one needs to specify a probability space of continued fractions. It seems the most natural such space is the interval $[0,1)$ with the density function $1/(1+x)$ that is the natural invariant measure in the study of continued fractions. It is known (Khinchin) that the probability that $a_i=r$ is equal to $\log(1+\frac1{r(r+2)})/\log 2$. Therefore the expected number of distinct $a_i$ among $a_1,\dots,a_k$ is (by linearity of expectation) $$ \sum_{r=1}^\infty \bigg( 1 - \bigg(1- \frac{\log(1+\frac1{r(r+2)})}{\log 2} \bigg)^k \bigg). $$ (The $r$th summand is the probability that $r$ occurs at least once among $a_1,\dots,a_k$.) When $\frac1{r(r+2)}$ is small compared with $\frac1k$, then the $r$th summand is approximately $k\log(1+\frac1{r(r+2)})/\log 2 \asymp \frac k{r^2}$; the contribution of such terms where $r>R$ say (with $R$ large compared with $\sqrt k$) is $O(k/R)$. The contribution of the initial $\sqrt k$ or so terms should have order of magnitude $\sqrt k$. So I suspect that the expected number of distinct $a_i$ among the first $k$ partial quotients is asymptotic to some constant times $\sqrt k$. Numerical experimentation is reasonably consistent with this, with the constant quite close to $2.1$.

$\endgroup$
1
  • $\begingroup$ Note that this is not inconsistent with the Diamond/Vaaler result mentioned in Igor Rivin's answer. $\endgroup$ Aug 19, 2015 at 6:13
3
$\begingroup$

Results of Diamond and Vaaler (see Flajolet-Vallee-Vardi survey) and others would seem to indicate that the cardinality for a "random" number grows logarithmically with $n.$

$\endgroup$
1
  • $\begingroup$ Thanks for the link to the article; its a very good overview. $\endgroup$ Aug 19, 2015 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.