Maps of primitive vectors and Conway's river, has anyone built this in SAGE?
I am attempting to teach number theory from John Stillwell's Elements of Number Theory in the upcoming semester. There are two sections (5.7 and 5.8) which describe the diagrammatic method for the derivation of primitive vectors which ultimately lead to a healthy understanding of values which the quadratic form $x^2-ny^2$ may attain for fixed $n$ and integers $x,y$. The "river" is a particular path in this "tree of integral bases" which separates positive and negative values for the quadratic form. Here is an example: an example from David Vogan of MIT To be fair, there is a good discussion in Stillwell, my question is simply this:
Has anyone implemented a routine, command, etc. which produces some part of the integral tree of bases or the more interesting diagrams as shown in section 5.8 of Stillwell?
I'm more inclined to cover it if I can create examples without falling prey to the inevitable arithmetic mistakes I will make in the creation of such a diagram. Also, for the homework, it would really be nice for them to be able to play around with it without investing too much time.
Thanks in advance for your help!
EDIT: I think I should emphasize that I have no graphics program for this and am not competent to make one. The diagrams below were done by hand, then scanned on my one-page home scanner as jpegs; those seem to work better on MSE than pdf's. My programs give a good idea how the diagram ought to look, also eliminate simple arithmetic errors; however, a user needs to read some rather cryptic output and then draw the diagram.
ORIGINAL: Not Sage, but I have written several programs either using or helping to draw the river for a Pell form. First, i put four related excerpts at http://zakuski.utsa.edu/~jagy/other.html with prefix indefinite_binary. Second, the book by Conway that introduced this diagram is available at http://www.maths.ed.ac.uk/~aar/papers/conwaysens.pdf and for sale as a real book.
Especially for Pell forms, i have come to prefer a hybrid diagram, one that emphasizes the automorphism group of the form $x^2 - n y^2.$ See recent answer at Proving a solution to a double recurrence is exhaustive and, in fact, many earlier answers.
I can tell you that actually drawing these things is what explains them...Conway deliberately leaves out the automorphisms, he wanted a brief presentation I guess, I really wanted to include that and show how the diagram displays the generator of that group. Also discussed in many number theory books, including my favorite, Buell.
You are welcome to email me, gmail is better (click on my profile and go to the AMS Combined Membership Listings link). I have many diagrams, programs in C++, what have you.
Here is the simpler of two diagrams I did for $x^2 - 8 y^2.$ All I mean by the automorphism group is the single formula $$ (3x+8y)^2 - 8 (x+3y)^2 = x^2 - 8 y^2, $$ with the evident visual column vector $(3,1)^T$ giving a form value of $1$ and the column vector $(8,3)^T$ directly below it giving a form value of $-8,$ thus replicating the original form.
This is another pretty recent, the very similar $x^2 - 2 y^2,$ where I was emphasizing finding all solutions to $x^2 - 2 y^2 = 7,$ and how there is more than one "orbit" of the automorphism group involved, i.e. every other pair...
Well, why not. One should be aware that the Gauss-Lagrange method of cycles of "reduced" forms is part of the topograph, in fact one such cycle is the exact periodocity of Conway's river. Reduced forms, that is $a x^2 + b xy + c y^2$ with $ac < 0$ and $b > |a+c|,$ occur at what Weissman calls "riverbends," where the action switches sides of the river. Anyway, all the following information is automatically part of the diagram for $x^2 - 13 y^2.$ As a result, the diagram is quite large, it took me two pages. Generate solutions of Quadratic Diophantine Equation
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 13
0 form 1 6 -4 delta -1
1 form -4 2 3 delta 1
2 form 3 4 -3 delta -1
3 form -3 2 4 delta 1
4 form 4 6 -1 delta -6
5 form -1 6 4 delta 1
6 form 4 2 -3 delta -1
7 form -3 4 3 delta 1
8 form 3 2 -4 delta -1
9 form -4 6 1 delta 6
10 form 1 6 -4
disc 52
Automorph, written on right of Gram matrix:
109 720
180 1189
Pell automorph
649 2340
180 649
Pell unit
649^2 - 13 * 180^2 = 1
=========================================
Pell NEGATIVE
18^2 - 13 * 5^2 = -1
=========================================
4 PRIMITIVE
11^2 - 13 * 3^2 = 4
=========================================
-4 PRIMITIVE
3^2 - 13 * 1^2 = -4
=========================================
I was surprised to learn, recently, that a simple idea ( made up, it appears, by Tito Piezas, without him knowing it was a neologism) allowed me to get the information in Conway's topograph with a fairly simple computer program, as long as what I wanted was to guarantee finding all solutions $(x,y)$ to $ax^2 + bxy+ cy^2 = n$ with integers $x,y > 0$ and $a,b,c,n$ fixed, $b^2 - 4ac>0$ but not a square. It seems the first answer where I displayed this material was If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution. and has good explanations, while Tito's comments began with Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$? in the thread Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?
There are a few programs involved for me, as one must tell the final program the fundamental solution to a relevant Pell equation. Anyway, you are welcome to the programs. For me, it means I can give all solutions, then draw the topograph when time permits. My first program on this is restricted to $x^2 - d y^2 = t,$ and it must be told the "fundamental" solution to $x^2 - d y^2 = 1.$
The output below are the two problems for which I posted topograph diagrams in my earlier answer
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 8
Pell unit
3^2 - 8 * 1^2 = 1
=========================================
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
3^2 - 8 1^2 = 1
x^2 - 8 y^2 = -7
Fri Apr 29 11:15:41 PDT 2016
x: 1 y: 1 ratio: 1 SEED
x: 5 y: 2 ratio: 2.5 SEED
x: 11 y: 4 ratio: 2.75
x: 31 y: 11 ratio: 2.818181818181818
x: 65 y: 23 ratio: 2.826086956521739
x: 181 y: 64 ratio: 2.828125
x: 379 y: 134 ratio: 2.828358208955223
x: 1055 y: 373 ratio: 2.828418230563003
x: 2209 y: 781 ratio: 2.82842509603073
x: 6149 y: 2174 ratio: 2.828426862925483
x: 12875 y: 4552 ratio: 2.828427065026362
x: 35839 y: 12671 ratio: 2.828427117038907
x: 75041 y: 26531 ratio: 2.828427122988202
x: 208885 y: 73852 ratio: 2.828427124519309
x: 437371 y: 154634 ratio: 2.82842712469444
x: 1217471 y: 430441 ratio: 2.828427124739511
x: 2549185 y: 901273 ratio: 2.828427124744667
x: 7095941 y: 2508794 ratio: 2.828427124745993
x: 14857739 y: 5253004 ratio: 2.828427124746145
Fri Apr 29 11:16:01 PDT 2016
x^2 - 8 y^2 = -7
jagy@phobeusjunior:~$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 2
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Pell unit
3^2 - 2 * 2^2 = 1
=========================================
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
3^2 - 2 2^2 = 1
x^2 - 2 y^2 = 7
Fri Apr 29 11:20:19 PDT 2016
x: 3 y: 1 ratio: 3 SEED
x: 5 y: 3 ratio: 1.666666666666667 SEED
x: 13 y: 9 ratio: 1.444444444444444
x: 27 y: 19 ratio: 1.421052631578947
x: 75 y: 53 ratio: 1.415094339622641
x: 157 y: 111 ratio: 1.414414414414414
x: 437 y: 309 ratio: 1.414239482200647
x: 915 y: 647 ratio: 1.414219474497681
x: 2547 y: 1801 ratio: 1.414214325374792
x: 5333 y: 3771 ratio: 1.41421373640944
x: 14845 y: 10497 ratio: 1.414213584833762
x: 31083 y: 21979 ratio: 1.414213567496246
x: 86523 y: 61181 ratio: 1.414213563034275
x: 181165 y: 128103 ratio: 1.414213562523907
x: 504293 y: 356589 ratio: 1.414213562392558
x: 1055907 y: 746639 ratio: 1.414213562377534
x: 2939235 y: 2078353 ratio: 1.414213562373668
x: 6154277 y: 4351731 ratio: 1.414213562373226
Fri Apr 29 11:20:39 PDT 2016
x^2 - 2 y^2 = 7
jagy@phobeusjunior:~$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=