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$
  • $\begingroup$ What does this mean? You are asking about the cardinality of a set of $n+1$ elements??? $\endgroup$ – Igor Rivin Aug 18 '15 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$ – Manfred Weis Aug 18 '15 at 14:49
  • $\begingroup$ At least for quadratic irrational numbers, the cardinality is bounded above. $\endgroup$ – Sungjin Kim Aug 18 '15 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$ – Manfred Weis Aug 18 '15 at 14:59
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$
  • $\begingroup$ Note that this is not inconsistent with the Diamond/Vaaler result mentioned in Igor Rivin's answer. $\endgroup$ – Greg Martin Aug 19 '15 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$
  • $\begingroup$ Thanks for the link to the article; its a very good overview. $\endgroup$ – Manfred Weis Aug 19 '15 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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