Given natural numbers of special very composite form, like primorials or factorials, how to give some useful upper bound limit of continued fraction period length of their square roots?
I'm not a professional, any advices are welcome.
Given natural numbers of special very composite form, like primorials or factorials, how to give some useful upper bound limit of continued fraction period length of their square roots?
I'm not a professional, any advices are welcome.
The continued fraction length is usually a small constant factor away from the regulator. A more precise version can also be achieved, but I don't remember a reference, so if anyone does...
Then, we know the regulator times the class number is usually a small constant factor away from the discriminant (of the order, not necessarily the field).
In addition, if a discriminant has $n$ prime factors in its squarefree part, the class number will be divisible by $2^{n-1}$.
Finally, most positive numbers of some size don't have many prime factors, and we suspect the real quadratic fields composed from these to have relatively small class number (look up Cohen-Lenstra).
Combining these facts and heuristics we get that primorials, and even factorials (still have large squarefree part), will have larger class number, hence small regulator, and therefore smaller continued fraction period length.
That said, we can dig even deeper. For factorials, there is a hefty squareful part. When we go from the maximal order of the field $\mathbb{Q}(\sqrt{n!})$ to the order $\mathbb{Z}(\sqrt{n!})$, the discriminant is enlarged hugely. Each prime (even) power $p^{2m}\ ||\ n!$ adds $p^{m-1}(p-(squarefree(n!)/p))$ to the original $h_K\times R_K$. So for each such factor, something goes into the class number of the smaller order, and something goes into the regulator of the smaller order.
Here comes the interesting bit. The factors that make up the new regulator tell us how far the unit group in the small order is from the unit group of the maximal order. Since we are in a real quadratic field the unit groups are of rank 1, so this distance is just the exponent to which the fundamental unit is powered by in order to enter the smaller order. Say $p_1-1$ and $p_2-1$ (say Legendre symbol is 1) have a large gcd. Once we power the fundamental unit to, say, $p_1-1$ to get (locally) into the $p$-part of the smaller order, we can slack off when getting into the $p_2$-part of the smaller order, because we've already done some of the work.
So in the factorial case, or in any number with many square factors (not dividing the squarefree part), since many of the above mentioned factors will have a large gcd, most of the factors will have to go into the class number of the small order - hence the very small regulator and continued fraction expansion.
We can write the above explicitly, but we need another notion. When a prime divides the discriminant to an even power greater than 2, the power of $p$ from the above mentioned factor that goes into the regulator measures how the fundamental unit is far p-adically from being 1. For most $p$, the fundamental unit will not be $1\ (mod\ p^2)$, so pretty much all of the $p^{m-1}$ goes into the regulator.
Hence, we expect:
$$ \frac{period-length(n!)}{\sqrt{n!}} \sim \frac{lcm(\{\ p-(p/squarefree(n!))\ |\ p^{2m}\ ||\ n!\ \}}{\prod_{p^{2m}||n!} (p-(p/squarefree(n!))} $$
And how that factor behaves - I have no idea. Sounds like a combinatorical answer could exist.
I'm making this an answer because it is long, and I think you can use this hard-won information. If you try to write the simple continued fraction for some $\sqrt N$ for large positive $N,$ you have two problems, one is decimal accuracy and another is detecting when the cycle is repeating. Well, maybe you have software that takes care of both problems automatically. If not, here is how to minimize both problems using only integer arithmetic, albeit large integers.
This is from Binary Quadratic Forms, by Duncan A. Buell, especially chapter 3 "Indefinite Forms": the binary quadratic form $\langle a,b,c \rangle$ refers to $f(x,y) = a x^2 + b x y + c y^2.$ In your case you start with $x^2 - N y^2.$ Find, carefully (I wrote my own Newton's method for the integer part of the square root using only integers) $a_0 = \lfloor \sqrt N \rfloor .$ Your quadratic form is "equivalent to" the "reduced" form $\langle 1,\; 2 a_0, \; a_0^2 - N \rangle.$ Using the method of right adjacent forms, you then keep finding (reduced) neighbors until you arrive back at $\langle 1,\; 2 a_0, \; a_0^2 - N \rangle.$ The important thing is this: it is not necessary to record the intermediate forms at all! The cycle is guaranteed to close up by arriving back at its beginning. Here is a run using 10 factorial: Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 1 3808 -3584
0 form 1 3808 -3584 delta -1
1 form -3584 3360 225 delta 15
2 form 225 3390 -3359 delta -1
3 form -3359 3328 256 delta 13
4 form 256 3328 -3359 delta -1
5 form -3359 3390 225 delta 15
6 form 225 3360 -3584 delta -1
7 form -3584 3808 1 delta 3808
8 form 1 3808 -3584
The matrix that takes us to a right neighbor is
$$ R = \left( \begin{array}{cc} 0 & -1 \\\ 1 & \delta \end{array} \right) $$
where, if $M$ is the Gram matrix for the current forms, the Gram matrix for the neighbor is $$ R' M R $$ where $R'$ is the transpose.
Let's see, if the current form is $\langle a,b,c \rangle$ then we define $\delta$ by $$ \delta c > 0$$ and $$ | \delta | = \lfloor \left| \frac{b + \sqrt{4 N}}{2 c} \right| \rfloor $$ see especially pages 21-24 in Buell, here the "discriminant" is always $ b^2 - 4 a c = 4 N.$ So the right adjacent form is $$ \langle c,- \; b + 2 c \delta, \; a - b \delta + c \delta^2 \rangle $$ Also you might as well compute $ \lfloor \sqrt{4 N} \rfloor $ once and keep it under a new variable name for repeated use.
EDIT** It ($ \lfloor \sqrt{4 N} \rfloor $) is close to $2 a_0$ but may not be equal; consider $N=7,$ so $a_0 = 2,$ and $2 a_0 = 4.$ But $ \lfloor \sqrt{4 N} \rfloor = \lfloor \sqrt{28} \rfloor = 5.$
For more general reduced forms, instead of $ \sqrt{4 N}$ you use $ \sqrt{\Delta},$ where $\Delta = b^2 - 4 a c $ is called the discriminant and is positive but not a perfect square. You make a perfect calculation of $ \lfloor \sqrt{\Delta} \rfloor $ once and keep it under a new variable name, because then you can calculate $$ | \delta | = \lfloor \left| \frac{b + \sqrt{\Delta}}{2 c} \right| \rfloor $$ using integer arithmetic. But here you must check that your initial form really is reduced, see page 21 in Buell, or reduce it, Proposition 3.3 on pages 22-23.
Well, email me if this seems useful but you cannot get it to work. Also, I think Ramanujan's superior highly composite numbers really are a good idea for you, let me know if you can't find out how to generate them.
ANOTHER EDIT: my memory is that the absolute values of the $\delta$'s are the $a_i$'s for the periodic part of the related continued fraction. So the period length for the continued fraction of some $\sqrt n$ may be smaller than the cycle length here. This is true, for example, for $\sqrt {k^2 + 1}$
Input n for Pell
17
0 form 1 8 -1 delta -8
1 form -1 8 1 delta 8
2 form 1 8 -1
As the absolute values of 8 and $-8$ are the same, the continued fraction period length for $\sqrt {17}$ is actually 1, not 2. But for the $ \sqrt {10!}$ example earlier, the period length for the continued fraction should still be 8 because $13 \neq 3808.$
I don't think that divisibility properties allow you to improve the known upper bound $C \sqrt{n} \log n$ for the period length of $\sqrt{n}$. The reason why period lengths for square roots of factorials are "suspiciously small" is that the period length depends on the squarefree kernel of a number.