(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 1016661, 26016]*) (*NotebookOutlinePosition[ 1018530, 26071]*) (* CellTagsIndexPosition[ 1018300, 26062]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["\<\ The Lagarias multidimensional geodesic continued fraction algorithm \ \>", "Title"], Cell["\<\ This algorithm finds all Hermite best approximations in simpler rationals (p_1/q,p_2/q,...p_n/q) to a given rational vector in n dimensions. \ \>", "Subtitle"], Cell["\<\ An Hermite approximation to a vector v in n dimensions is a rational vector r=(p_1/q,p_2/q,...p_n/q) so that, for all t in some interval 0", "Subsubtitle"], Cell[TextData[{ "\nThe procedures here culminate with a procedure getcfx which takes two \ inputs, \na rational target vector v in some dimension greater than 1, and a \ positive \ninteger n which stipulates the depth to which the procedure shall \ be carried \nif it doesn't terminate due to having hit upon the input vector \ itself. \n\nAccompanying this we offer two variants that produce simpler \ output. \nThe first, \"gethermites\", takes as input a listtheta of rational \ numbers in (-1/2,1/2) \nand a positive integer, and returns all the Hermite \ n-tuples (p_1,...p_{n-1},q) \nsuch that q is a Hermite denominator for the \ target, theta, and such that the p_j's \nare the integers nearest q theta_j. \ The second, hermites, takes the same kind of inputs\nbut returns only the \ Hermite denominators themselves. \n\nWe also provide a simpler algorithm, \ lllcfx, which takes the same kind of input but returns \na sequence of \ integers that arise out of executing ", StyleBox["Mathematica", FontSlant->"Italic"], "'s variant of the Lenstra-Lenstra-Lovasz \nalgorithm. If the target list \ `u' has length n-1, one takes an n-1 by n-1 identity matrix, appends -theta \ as\na final row, then pads each row but the last with a final zero, appending \ instead 2^(-k) to that last row, u.\nThe resulting n by n matrix is \ LLL-reduced and the successive integers that appear as absolute values of the \ last entry in \nthe top row are noted. These are more easily computed than \ the Hermite approximations, and they afford denominators q that lead to \ serviceable simultaneous diophantine approximations of u. \n\n\n\nSticking to \ rational inputs has the advantage that the algorithm executes \ncleanly. \ There is never any doubt as to whether one number is greater than \nanother \ when dealing with rationals, and so branching decisions are not \ncontingent \ upon the vagaries of floating point arithmetic. \n\n\n\nWe illustrate the \ algorithm by examining what happens when v is a {very good} \nrational \ approximation to a certain kind of algebraic input. Suppose P(x) is \nan \ irreducible polynomial with integer coefficients, of degree n. Let u be \nthe \ vector (x,x^2,...x^(n-1)). As Drmota and Tichy have shown, u is badly \n\ approximable, meaning that there is some positive epsilon so that for all \n\ rational approximations r=(p1/q,...p_n/q), q^(1/n)|u-r|>epsilon. \n\n\n\nIf \ we take for v a rational approximation to u of the form \n\ v=10^(-N)Map[Floor,10^N u], then we may expect that the execution history of \ \nthe geodesic continued fraction algorithm on input v, will track to \n\ considerable depth that of what would abstractly happen if we worked with u \n\ itself. The resulting sequence of integers q_j, and approximations r_j, can \ \nfor the case n=3 be inspected by evaluating the corresponding points \n\ q_j^(1/2)(q_j v mod 1), where the interval (-1/2,1/2] is used to select a \n\ representative element mod 1. These will, on theoretical grounds, all fall \n\ within an annulus about the origin. The surprise is that they all \nfall onto \ a finite set of ellipses, concentric and similar, about the origin. \n\n\n\n\n\ \n\n\n" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(?getcfx\)\)], "Input"], Cell["Global`getcfx", "Print", CellTags->"Info3339663997-2203256"], Cell[BoxData[ InterpretationBox[GridBox[{ {GridBox[{ {\(getcfx[v_List, stopwhen_] := Module[{n, k, m, t, u, e, s, z, sofar, q, qq}, n = Length[v]; m = Table[esubi[k, n + 1], {k, 1, n}]; AppendTo[m, Append[\(-v\), 1]]; t = 1; z = {}; u = Table[esubi[k, n + 1], {k, 1, n + 1}]; e = u; s = {m, t, u, e}; sofar = 0; qq = {}; While[\(! timetoquit[ v, \(s\[LeftDoubleBracket]3\[RightDoubleBracket]\ \)\[LeftDoubleBracket]1\[RightDoubleBracket]]\) && sofar < stopwhen, AppendTo[z, s]; s = step[s]; q = \(\(s\[LeftDoubleBracket]1\[RightDoubleBracket]\)\ \[LeftDoubleBracket]1\[RightDoubleBracket]\)\[LeftDoubleBracket]\(-1\)\ \[RightDoubleBracket]; qq = qq \[Union] {Abs[q]}; qq >> "qq.m"; s >> "mtue.m"; sofar >> "sofar.m"; \((z >> "z.m"; \(sofar++\))\)]; z]\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnWidths->0.999, ColumnAlignments->{Left}]} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], Definition[ "getcfx"], Editable->False]], "Print", CellTags->"Info3339663997-2203256"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(hermites[{\(-31\)/101, 50/139}, 400]\)], "Input"], Cell[BoxData[ \({0, 1, 3, 39, 75, 114, 303}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(lllcfx[{\(-31\)/101, 50/139}, 30]\)], "Input"], Cell[BoxData[ \({1, 3, 39, 114, 303, 14039}\)], "Output"] }, Open ]], Cell[BoxData[""], "Input"], Cell[BoxData[ \(\(\(\[IndentingNewLine]\)\(esubi[k_, n_] := Join[Table[0, {k - 1}], {1}, Table[0, {n - k}]]\)\)\)], "Input", InitializationCell->True], Cell[BoxData[ \(reddit[u_] := Module[{v, w}, v = LatticeReduce[u]; w = v . Inverse[u]; Abs[\(w[\([1]\)]\)[\([\(-1\)]\)]]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(lllcfx[u_, n_] := Module[{j, k, r}, r = Length[u]; Drop[Union[ Table[reddit[ Join[Table[ esubi[k, r + 1], {k, 1, r}], {Join[ u, {2^\((\(-j\))\)}]}]], {j, 0, n}]], 1]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(switchmatrix[{j_, k_, n_}] := Module[{r}, Join[Table[esubi[r, n], {r, 1, j - 1}], {esubi[k, n]}, Table[esubi[r, n], {r, j + 1, k - 1}], {esubi[j, n]}, Table[esubi[r, n], {r, k + 1, n}]]]\)], "Input", InitializationCell->True], Cell[CellGroupData[{ Cell[BoxData[ \(norm[b_, t_] := Module[{b1, b2}, b1 = Drop[b, \(-1\)]; b2 = b[\([\(-1\)]\)]; b1 . b1 + t\ b2^2]\)], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{\(General::"spell1"\), \(\(:\)\(\ \)\), "\<\"Possible spelling \ error: new symbol name \\\"\\!\\(norm\\)\\\" is similar to existing symbol \\\ \"\\!\\(Norm\\)\\\". \\!\\(\\*ButtonBox[\\\"More\[Ellipsis]\\\", \ ButtonStyle->\\\"RefGuideLinkText\\\", ButtonFrame->None, \ ButtonData:>\\\"General::spell1\\\"]\\)\"\>"}]], "Message"] }, Open ]], Cell[BoxData[ \(switchedspots[e_] := Module[{j, k, s}, s = {}; j = 1; n = Length[e]; While[Length[s] < 2 && j \[LessEqual] n, If[e[\([j]\)] \[NotEqual] esubi[j, n], AppendTo[s, j]; \(j++\), \(j++\)]]; s]\)], "Input", InitializationCell->True], Cell[BoxData[ \(switchvalue[{e_, m_, t_}] := Module[{j, k, m1, m2, n1at0, n2at0, n1att, n2att, tau, s}, {j, k} = switchedspots[e]; m1 = m[\([j]\)]; m2 = m[\([k]\)]; n1at0 = norm[m1, 0]; n2at0 = norm[m2, 0]; If[n1at0 \[LessEqual] n2at0, Return[False]]; n1att = norm[m1, t]; n2att = norm[m2, t]; If[n1att > n2att, Return[False]]; \[IndentingNewLine]tau = Solve[norm[m1, s] \[Equal] norm[m2, s]]; \[IndentingNewLine]tau = \((s /. tau)\)[\([1]\)]; tau]\)], "Input", InitializationCell->True], Cell[CellGroupData[{ Cell[BoxData[ \(nchoosek[0, n_] = {{}}\)], "Input", InitializationCell->True], Cell[BoxData[ \({{}}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(nchoosek[j_, 0] = {}\)], "Input", InitializationCell->True], Cell[BoxData[ \({}\)], "Output"] }, Open ]], Cell[BoxData[""], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(plusminusvectors[0] = {{}}\)], "Input", InitializationCell->True], Cell[BoxData[ \({{}}\)], "Output"] }, Open ]], Cell[BoxData[ \(plusminusvectors[n_] := \(plusminusvectors[n] = Join[Map[Join[#, {1}] &, plusminusvectors[n - 1]], Map[Join[#, {\(-1\)}] &, plusminusvectors[n - 1]]]\)\)], "Input", InitializationCell->True], Cell[BoxData[ \(nchoosek[k_, n_] := \(nchoosek[k, n] = Join[nchoosek[k, n - 1], Map[Join[#, {n}] &, nchoosek[k - 1, n - 1]]]\)\)], "Input", InitializationCell->True], Cell[BoxData[ \(settovectors[s_, n_] := Module[{pm, j, k, l}, l = Length[s]; pm = Select[plusminusvectors[l], #[\([\(-1\)]\)] > 0 &]; Table[Sum[ esubi[s[\([k]\)], n] \(pm[\([j]\)]\)[\([k]\)], {k, 1, l}], {j, 1, Length[pm]}]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(lastentry[ v_] := \(\(Position[v, 1]\)[\([\(-1\)]\)]\)[\([1]\)]\)], "Input", InitializationCell->True], Cell[BoxData[ \(vectortomatrix[v_] := Module[{j, k, n}, k = lastentry[v]; n = Length[v]; Join[Table[esubi[j, n], {j, 1, k - 1}], {v}, Table[esubi[j, n], {j, k + 1, n}]]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(\(\(movevalue[{v_, m_, t_}] := Module[{e, k, m1, m2, n1at0, n2at0, n1att, n2att, s, tau}, e = vectortomatrix[v]; k = lastentry[v]; m1 = m[\([k]\)]; m2 = \((e . m)\)[\([k]\)]; \[IndentingNewLine]n1at0 = norm[m1, 0]; n2at0 = norm[m2, 0]; \[IndentingNewLine]If[n1at0 \[LessEqual] n2at0, Return[False]]; \[IndentingNewLine]n1att = norm[m1, t]; n2att = norm[m2, t]; \[IndentingNewLine]If[n1att > n2att, Return[False]]; \[IndentingNewLine]tau = Solve[norm[m1, s] \[Equal] norm[m2, s], s]; \[IndentingNewLine]tau = \((s /. tau)\)[\([1]\)]; tau]\)\(\[IndentingNewLine]\) \)\)], "Input", InitializationCell->True], Cell[BoxData[ \(vectors[n_] := Flatten[\((settovectors[#1, n] &)\) /@ usablesubsets[n], 1]\)], "Input",\ InitializationCell->True], Cell[BoxData[ \(usablesubsets[n_] := Flatten[Join[Table[nchoosek[j, n], {j, 2, n}]], 1]\)], "Input", InitializationCell->True], Cell[BoxData[ \(switchy[n_] := Flatten[Table[{j, k, n}, {k, 2, n}, {j, 1, k - 1}], 1]\)], "Input", InitializationCell->True], Cell[BoxData[ \(switchbunch[n_] := Map[{#, switchmatrix[#]} &, switchy[n]]\)], "Input", InitializationCell->True], Cell[CellGroupData[{ Cell[BoxData[ \(subsets[0] = {{}}\)], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{\(General::"spell1"\), \(\(:\)\(\ \)\), "\<\"Possible spelling \ error: new symbol name \\\"\\!\\(subsets\\)\\\" is similar to existing symbol \ \\\"\\!\\(Subsets\\)\\\". \\!\\(\\*ButtonBox[\\\"More\[Ellipsis]\\\", \ ButtonStyle->\\\"RefGuideLinkText\\\", ButtonFrame->None, \ ButtonData:>\\\"General::spell1\\\"]\\)\"\>"}]], "Message"], Cell[BoxData[ \({{}}\)], "Output"] }, Open ]], Cell[BoxData[ \(subsets[n_] := \(subsets[n] = Join[subsets[n - 1], Map[Join[#, {n}] &, subsets[n - 1]]]\)\)], "Input", InitializationCell->True], Cell[BoxData[ \(usablesubsets[n_] := Select[subsets[n], \((Length[#] \[GreaterEqual] 2)\) &]\)], "Input", InitializationCell->True], Cell[BoxData[ \(vectorbunch[n_] := Partition[Flatten[Map[{#, vectortomatrix[#]} &, vectors[n]], 1], 2]\)], "Input", InitializationCell->True], Cell[BoxData[ \(moves[n_] := Join[switchbunch[n], vectorbunch[n]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(\(\(validswitches[{m_, t_}] := Module[{n, vs}, n = Length[m]; vs = switchbunch[n]; Select[vs, NumberQ[switchvalue[{#[\([2]\)], m, t}]] &]]\)\(\[IndentingNewLine]\)\(\[IndentingNewLine]\) \)\)], "Input", InitializationCell->True], Cell[BoxData[""], "Input"], Cell[BoxData[ \(validmoves[{m_, t_}] := Module[{n, vs}, n = Length[m]; vs = vectorbunch[n]; Select[vs, NumberQ[movevalue[{#[\([1]\)], m, t}]] &]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(valids[{m_, t_}] := Join[Map[{switchvalue[{#[\([2]\)], m, t}], #} &, validswitches[{m, t}]], \[IndentingNewLine]Map[{movevalue[{#[\([1]\)], m, t}], #} &, validmoves[{m, t}]]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(bestchoices[{m_, t_}] := Sort[valids[{m, t}], OrderedQ[{#1[\([1]\)], #2[\([1]\)]}] &]\)], "Input",\ InitializationCell->True], Cell[BoxData[ \(step[{m_, t_, u_}] := Module[{e, s, v, w}, w = bestchoices[{m, t}]; v = w[\([\(-1\)]\)]; e = \(v[\([\(-1\)]\)]\)[\([2]\)]; s = v[\([1]\)]; {e . m, s, e . u}]\)], "Input", InitializationCell->True], Cell[BoxData[ \(settovectors[s_, n_] := Module[{pm, j, k, l}, l = Length[s]; pm = Select[plusminusvectors[l], #[\([\(-1\)]\)] > 0 &]; Table[Sum[ esubi[s[\([k]\)], n] \(pm[\([j]\)]\)[\([k]\)], {k, 1, l}], {j, 1, Length[pm]}]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(\(\(setandtemplatetovectors[s_, n_, template_] := Module[{pm, j, k, l}, l = Length[s]; If[l \[NotEqual] Length[template], Print["\