5
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ I'm not entirely convinced the "trees" tag belongs, so, if someone from the forest feels otherwise, feel free to chop it down. $\endgroup$ – James S. Cook Dec 23 '14 at 5:33
  • $\begingroup$ This is not in Sage. But I am familiar with the text you mention, and it would be a neat addition. $\endgroup$ – kcrisman Dec 24 '14 at 2:35
  • $\begingroup$ did you ever find program to draw the diagrams? $\endgroup$ – Bob Woodley Apr 19 '18 at 0:17
  • $\begingroup$ @BobWoodley I did not find such a program, although, a student of mine made one... then left... I'm not sure if he finished debugging it. I think it's an open problem to do nicely. $\endgroup$ – James S. Cook Apr 19 '18 at 19:41
5
$\begingroup$

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.

enter image description here

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

enter image description here

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 

=========================================
$\endgroup$
  • $\begingroup$ Thanks Will. This answer will be very useful to those students who wish to dig further into this. We may have to wait a few years before we can just tell them the words they wish to hear "here's the ap for that". Well, maybe the students we seek never will say that, I will keep the email in mind. Thanks! $\endgroup$ – James S. Cook Dec 24 '14 at 4:21
2
$\begingroup$

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:~$ 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.