On Tue, Jul 23, 2013 at 5:05 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 7/23/13, Mike Stay <metaweta@gmail.com> wrote:
... Actually, it has to do with "cubic" continued fractions. See, e.g. Gupta & Mittal, "Bifurcating Continued Fractions" and Mittal & Gupta "Bifurcating Continued Fractions II". Both are available on the arxiv or here:
http://www.cs.auckland.ac.nz/~mike/maths/continued%20fractions/BCF1.pdf http://www.cs.auckland.ac.nz/~mike/maths/continued%20fractions/BCF2.pdf --
[Oops--- there goes the carpet again.]
The authors seem completely unaware of the existing literature on MDCF (Multidimensional Continued Fractions), Lattice Basis Reduction, Diophantine Approximation etc.
That is true. That said, they have some really nice parallels to normal continued fractions that I haven't seen in other higher-order CFs. The cubic continued fraction algorithm approximates a pair of numbers (alpha, beta) with a pair of sequences of integers. One can use these terms to find triples (a_n, b_n, c_n) such that lim a_n n->inf --- = alpha c_n lim b_n n->inf --- = beta c_n At least one of the sequences terminate if alpha or beta is rational. If both sequences repeat, then alpha and beta are solutions to a pair of cubic equations. alpha_n is a positive integer for n>0; beta_n is a nonnegative integer. The algorithm is as follows: alpha'_0= alpha beta'_0 = beta alpha_n = [alpha'_n] beta_n = [beta'_n] alpha'_{n+1} = 1 / (beta'_n - [beta'_n]) beta'_{n+1} = (alpha'_n - [alpha'_n]) / (beta'_n - [beta'_n]) where [x] is greatest integer less than x. To find the nth covergent, take a_n = alpha_n b_n = beta_n c_n = 1 a_{n-1} = alpha_{n-1} a_n + b_n b_{n-1} = beta_{n-1} a_n + c_n c_{n-1} = a_n The determinant |a_n a_{n-1} a_{n-2}| |b_n b_{n-1} b_{n-2}| = 1 |c_n c_{n-1} c_{n-2}| My interest in them was to see if there was a similar continued fraction algorithm for factoring; with the usual continued fractions, the magnitude of the square of the numerator of the convergents is within 2sqrt(N) of a multiple of N. Here, instead of sqrt(N), it's N^{2/3}: Let x=n^(1/3). a_i/c_i -> x^2, b_i/c_i -> x, w = complex root of 1, w^2=-w |a_i b_i x c_i x^2| |b_i x c_i x^2 a_i | |c_i x^2 a_i b_i x | = |a_i^3 + b_i^3 x^3 + c_i^3 x^6 - 3a_i b_i c_i x| = c_i^3 |1 x^2 + 1 b_i/c_i x + 1 a_i/c_i| |1 x^2 + w b_i/c_i x - w a_i/c_i| |1 x^2 - w b_i/c_i x + w a_i/c_i| <= c_i^3 3 x^2 1/c_{i+1} 1/c_{i+2} <= 3 x^2 Let S be the set of numbers expressible in the form a x^2 + b x + c where a,b,c, are integers. It is self-evident that if y,z are elements of S, then yz is also an element of S. The determinant above acts like a kind of norm for S. Similar determinants exist for higher-order BCFs as well.
There are a number of algorithms besides LLL, with implementations built into Mathematica, Maple etc. See eg.
These will get you far better denominators than BCFs. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com