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, ... ]$?
-
$\begingroup$ What does this mean? You are asking about the cardinality of a set of $n+1$ elements??? $\endgroup$– Igor RivinAug 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$– Manfred WeisAug 18, 2015 at 14:49
-
$\begingroup$ At least for quadratic irrational numbers, the cardinality is bounded above. $\endgroup$– Sungjin KimAug 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$– Manfred WeisAug 18, 2015 at 14:59
2 Answers
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$.
-
$\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
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.$
-
$\begingroup$ Thanks for the link to the article; its a very good overview. $\endgroup$ Aug 19, 2015 at 11:04