Using continued fractions to well-approximate a quadratic form?

Question

Continued fractions are the "best rational approximation" of other numbers.

For a real number $\alpha$ the continued fraction algorithm produces a sequence of integers $\alpha = [a_1, a_2, \dots, a_n, \dots, ]$ and a sequence of fractions $ \tfrac{p_1}{q_1}, \tfrac{p_2}{q_2},\tfrac{p_3}{q_3},\dots \approx \alpha$ which are good approximations to $\alpha$ in the sense that:

$$ |\alpha q - p| > |\alpha q_N - p_N|$$

for any fraction $\tfrac{p}{q}$ which is not a convergent. I have seen this phrased in other ways, I should think about it some...

---

There is also a strong connection between quadratic forms and continued fractions. I believe there is a bijection of the type:

$$ ax^2 + bxy + c^2 \leftrightarrow \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \overline{[n_1, n_2, n_3,\dots, n_k ]}$$

The more I search on google the less clear this relation seems to be.

---

So I guess my question is two fold:

• what is the relation between binary quadratic forms and continued fractions?

• then, do notions of diophantine approxation pass over in this way?

Answer 1

Ummm. Gaus and Lagrange called an indefinite binary quadratic form $ax^2 + b xy + c y^2$ or $\langle a,b,c \rangle$ if certain inequalities hold. Reduced forms join up in cycles; indeed, two reduced forms are $SL_2 \mathbb Z$ equivalent if and only if they are in the same cycle. Reduced forms correspond to purely periodic continued fractions.

Not widely known (there are two of us) "reduced" is equivalent to: $$ ac < 0 \; \; \; \mbox{AND} \; \; \; b > |a+c|. $$

Example including reduction. I have described the algorithm with the delta's in many places, including https://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-compos/23014#23014

Ummm, the absolute values of the $\delta$'s are the continued fraction for something, it is either the positive root of $a + b t + c t^2$ (I think that is the one) or $a t^2 + b t + c$ for a reduced form. In some cases, while the $\delta$'s do not quite repeat, their absolute values do, and the actual continued fraction cycle is exactly half this length.

Let's see, approximation, given $\langle a,b,c \rangle$ with $\Delta = b^2 - 4 a c$ positive but not a square, all occurrences of $|a x^2 + b x y + c y^2| < \frac{\sqrt \Delta}{2}$ with $\gcd(x,y) =1$ appear as first (and third) coefficients of some form in the cycle. In the other direction, all first coefficients in the cycle have absolute value below $\sqrt \Delta,$ which is twice as large, so there is a little room for uncertainty.

jagy@phobeusjunior:Cplusplus ./indefCycle  27 143  22

  0  form             27         143          22  delta      6
  1  form             22         121         -39


           0          -1
           1           6

To Return  
           6           1
          -1           0

0  form   22 121 -39   delta  -3
1  form   -39 113 34   delta  3
2  form   34 91 -72   delta  -1
3  form   -72 53 53   delta  1
4  form   53 53 -72   delta  -1
5  form   -72 91 34   delta  3
6  form   34 113 -39   delta  -3
7  form   -39 121 22   delta  5
8  form   22 99 -94   delta  -1
9  form   -94 89 27   delta  4
10  form   27 127 -18   delta  -7
11  form   -18 125 34   delta  3
12  form   34 79 -87   delta  -1
13  form   -87 95 26   delta  4
14  form   26 113 -51   delta  -2
15  form   -51 91 48   delta  2
16  form   48 101 -41   delta  -2
17  form   -41 63 86   delta  1
18  form   86 109 -18   delta  -6
19  form   -18 107 92   delta  1
20  form   92 77 -33   delta  -3
21  form   -33 121 26   delta  4
22  form   26 87 -101   delta  -1
23  form   -101 115 12   delta  10
24  form   12 125 -51   delta  -2
25  form   -51 79 58   delta  1
26  form   58 37 -72   delta  -1
27  form   -72 107 23   delta  5
28  form   23 123 -32   delta  -4
29  form   -32 133 3   delta  44
30  form   3 131 -76   delta  -1
31  form   -76 21 58   delta  1
32  form   58 95 -39   delta  -2
33  form   -39 61 92   delta  1
34  form   92 123 -8   delta  -16
35  form   -8 133 12   delta  11
36  form   12 131 -19   delta  -6
37  form   -19 97 114   delta  1
38  form   114 131 -2   delta  -66
39  form   -2 133 48   delta  2
40  form   48 59 -76   delta  -1
41  form   -76 93 31   delta  3
42  form   31 93 -76   delta  -1
43  form   -76 59 48   delta  2
44  form   48 133 -2   delta  -66
45  form   -2 131 114   delta  1
46  form   114 97 -19   delta  -6
47  form   -19 131 12   delta  11
48  form   12 133 -8   delta  -16
49  form   -8 123 92   delta  1
50  form   92 61 -39   delta  -2
51  form   -39 95 58   delta  1
52  form   58 21 -76   delta  -1
53  form   -76 131 3   delta  44
54  form   3 133 -32   delta  -4
55  form   -32 123 23   delta  5
56  form   23 107 -72   delta  -1
57  form   -72 37 58   delta  1
58  form   58 79 -51   delta  -2
59  form   -51 125 12   delta  10
60  form   12 115 -101   delta  -1
61  form   -101 87 26   delta  4
62  form   26 121 -33   delta  -3
63  form   -33 77 92   delta  1
64  form   92 107 -18   delta  -6
65  form   -18 109 86   delta  1
66  form   86 63 -41   delta  -2
67  form   -41 101 48   delta  2
68  form   48 91 -51   delta  -2
69  form   -51 113 26   delta  4
70  form   26 95 -87   delta  -1
71  form   -87 79 34   delta  3
72  form   34 125 -18   delta  -7
73  form   -18 127 27   delta  4
74  form   27 89 -94   delta  -1
75  form   -94 99 22   delta  5
76  form   22 121 -39


  form   22 x^2  + 121 x y  -39 y^2 

minimum was   2rep   x = -886076244499295041   y = -2901739051836842472 disc   18073 dSqrt 134.43585831  M_Ratio  37.34091
Automorph, written on right of Gram matrix:  
172828187958347781813567725611028988779  1003329921172594192901147173988987814312
565980981174283903687826610968146972176  3285723584416909252096614085935837335747
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

---