# Upper bound of period length of continued fraction representation of very composite number square root

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.

-
I just want to point out that the period lengths of continued fractions of factorials are suspiciously small, compared to the period lengths of numbers of similar size which are not factorials. So this is a reasonable question to ask. –  Michael Lugo Apr 28 '10 at 12:29
You might compile statistics on your question for Ramanujan's "superior highly composite" numbers, which also have an explicit recipe for construction but have, eventually, far more divisors than factorials or primorials. Note there is no recipe for just the highly composite numbers. en.wikipedia.org/wiki/Superior_highly_composite_number and oeis.org/A002201 –  Will Jagy Apr 29 '10 at 3:12

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.

-
Although the OP worded the question in terms of upper bounds for special classes of numbers, it would appear that anything published that relates directly to this would likely be discussing lower bounds on the three related items, continued fraction length, regulator, order discriminant, then perhaps giving examples of types of numbers that get near the lower bound... en.wikipedia.org/wiki/Infrastructure_(number_theory) In this item, Golubeva apparently discusses lower bounds: springerlink.com/content/f11602324177865w –  Will Jagy Apr 30 '10 at 0:31
I was typing the explicit section while you posted (I too thought it wasn't clear how my post makes for an upper bound). But I think now it does. The factor on the right is obviously small and a study of it will provide an upper bound for the period length on the left. –  Dror Speiser Apr 30 '10 at 0:42
Also this, in this case definitely downloadable in Russian: springerlink.com/content/r5n2462km18u0t13 –  Will Jagy Apr 30 '10 at 0:42
Very nice. From your answer it appears that none of the three sequences mentioned are guaranteed to give astonishingly low C.F. length, just very small. Can you think of an optimization problem (in the S.H.C. numbers style, say) that gives a sequence of numbers that each give some sort of "world champion" surprisingly small C.F. length compared in some way with $N?$ It could be something no more complicated than maximizing $N^\epsilon / {length}.$ You see, I'm afraid the bit about even/odd exponents makes this tricky. Plus I am trying to make this more fun. –  Will Jagy Apr 30 '10 at 1:10
This depends on your definition of "astonishingly low" :) Think of all the prime factors between $\sqrt[3]{n}$ and $\sqrt{n}$. I would guess their lcm (after minusing legendres I mean) is smaller than their product by at least a subexponential function in $n$ (like $e^{\sqrt[6]{n}}$ or something). Compared to the numbers around it, I would say the factorial has astonishingly small CF period length. –  Dror Speiser Apr 30 '10 at 6:46

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.$

-
Thank you very much. I was using PARI with decimal precision set to crazy value and brute force cycle detection. This algorithm is a much better option. –  user5539 Apr 29 '10 at 18:52
For cycle detection, either of Floyd's or Brent's algorithms should be suitable. –  J. M. Dec 10 '11 at 11:33
@J. M. no cycle detection is necessary. For the first example, the cycle begins with 1 3808 -3584 and ends precisely when we get to 1 3808 -3584 again. –  Will Jagy Jul 17 '12 at 4:43

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.

-
@Franz Lemmermeyer: According to Pari, The period lengths of the square roots of 7, $7^3$ and $7^5$ are 4, 16 and 93. What is this dependence on the squarefree kernel? –  SJR Apr 28 '10 at 13:36
oops. These continued fractions correspond to fundamental units in orders of conductor 1, 7, 7^2 etc. in the ring of integers of the quadratic number field generated by a square root of 7. The length of the period should roughly correspond to the size of these units, which in turn are at most the 7th power of the unit generating the unit group of the next larger order. I would guess that these units grow at a smaller rate than that provided by the general upper bound, but haven't done the calculations. –  Franz Lemmermeyer Apr 28 '10 at 14:54
@Franz Lemmermeyer: That is why I also asked about primorials, since they are square-free and have surprisingly small periods too, surely I didn't checked all of them. The numbers I work with are not exactly primorials nor factorials, they are products of some small prime factor with primorial, so they have big square-free kernels of consequent small prime factors. This is not the case for "ordinary" numbers of comparable magnitude, because they have some big prime factors or gaps in their square-free kernels. –  user5539 Apr 28 '10 at 16:02