Skip to main content
6 of 8
edited body
José Hdz. Stgo.
  • 8.8k
  • 4
  • 68
  • 106

Cycle length and total count of Gauss reduced indefinite binary quadratic forms

Wikipedia lists two articles on maximum length for the continued fraction of $\sqrt n,$ Hickerson 1973 and Cohn 1977. There is a mess in the references, Cohn is not visible, just the link.

Hmmm. This guy does a review of one of the (Russian) references, http://www.jpr2718.org/podstotalc.pdf

I did my own modelling for two items, longest Gauss-Lagrange cycles of reduced forms, and largest number of reduced forms for a discriminant (positive but not a square). Reduced forms are $\langle a,b,c\rangle$ such that $\gcd(a,b,c) = 1, \; $ $d = b^2 - 4ac, \; \; $ $ac < 0, \; b > |a+c|.$ This equivalent version of reduction is in Franz's book, Theorem 1.36, formula 1.34. It is page numbered 37, pdf page 43.

Details: the longest individual cycles were all prime discriminant, class number one. The largest form count was sometimes composite discriminant, class number not one.

Hickerson and Cohn say that the period length for $\sqrt d$ is below $\sqrt d \log d.$ My own computations say this for both cycles of arbitrary reduced forms and total count of forms, where the latter has slightly larger implied constant (maybe over Cohn's $\frac{7}{2 \pi^2}.$ So the questions are, is $C_j \sqrt d \log d$ a provable upper bound for my two related problems?

Best length of individual cycle:

     5           1           1          -1              2   3.598813   0.5557389
    17           1           3          -2              6   11.68164   0.5136266
    41           1           5          -4             10   23.77846   0.4205486
    73           1           7          -6             18   36.6577    0.4910291
   193           1          13          -6             30   73.11163   0.4103314
   241           1          15          -4             38   85.14695   0.4462873
   337           1          17         -12             42   106.8425   0.3931019
   409           1          19         -12             54   121.6199   0.4440064
   601           1          23         -18             66   156.8635   0.420748
   769           1          27         -10             70   184.274    0.3798691
  1033           1          31         -18             78   223.061    0.3496802
  1201           1          33         -28            106   245.7386   0.4313526
  1609           1          39         -22            118   296.1642   0.3984276
  1801           1          41         -30            130   318.1208   0.4086498
  2161           1          45         -34            146   356.939    0.4090335
  2521           1          49         -30            170   393.2619   0.4322819
  3361           1          57         -28            178   470.7496   0.3781203
  3529           1          59         -12            198   485.2689   0.4080212
  4201           1          63         -58            210   540.7576   0.3883441
  4561           1          67         -18            214   569.0039   0.3760958
  5209           1          71         -42            238   617.6703   0.3853188
  5569           1          73         -60            258   643.6448   0.4008422
  6841           1          81         -70            290   730.3893   0.3970485
  7561           1          85         -84            306   776.5653   0.3940428
  8089           1          89         -42            330   809.2934   0.4077631
  9241           1          95         -54            346   877.8031   0.3941658
 12049           1         109         -42            378   1031.46    0.3664707
 12289           1         109        -102            390   1043.869   0.3736102
 12601           1         111         -70            394   1059.851   0.3717503
 13729           1         117         -10            426   1116.317   0.3816119
 15649           1         125          -6            454   1208.197   0.3757665
 16921           1         129         -70            474   1266.507   0.3742578
 18481           1         135         -64            502   1335.59    0.3758639
 19009           1         137         -60            522   1358.418   0.3842705
 20161           1         141         -70            530   1407.329   0.3765999
 21121           1         145         -24            542   1447.206   0.3745147
 21961           1         147         -88            566   1481.483   0.3820495
 24049           1         155          -6            578   1564.397   0.3694714
 26041           1         161         -30            590   1640.741   0.3595937
 26161           1         161         -60            602   1645.26    0.3658996
 28081           1         167         -48            622   1716.434   0.3623793
 28729           1         169         -42            630   1739.992   0.3620706
 31249           1         175        -156            674   1829.564   0.3683938
 33049           1         181         -72            702   1891.701   0.3710947
 33289           1         181        -132            714   1899.877   0.3758138
 38329           1         195         -76            722   2066.233   0.3494282
 40609           1         201         -52            750   2138.444   0.3507222
 43201           1         207         -88            766   2218.496   0.345279
 43801           1         209         -30            794   2236.735   0.3549817
 47041           1         215        -204            842   2333.464   0.3608369
 47881           1         217        -198            862   2358.079   0.3655518
 48049           1         219         -22            878   2362.98    0.3715648
 49009           1         221         -42            886   2390.848   0.3705798
 51769           1         227         -60            914   2469.714   0.3700834
 53881           1         231        -130            966   2528.87    0.3819888
 59929           1         243        -220            974   2693.068   0.3616693
 61681           1         247        -168           1002   2739.307   0.365786
 65521           1         255        -124           1006   2838.747   0.3543817
 66361           1         257         -78           1022   2860.168   0.3573217
 67369           1         259         -72           1042   2885.721   0.3610882
 69001           1         261        -220           1074   2926.753   0.3669596
 70849           1         265        -156           1086   2972.721   0.3653219
 80809           1         283        -180           1142   3212.198   0.3555198
 87481           1         295        -114           1242   3365.64    0.3690234
101641           1         317        -288           1246   3675.646   0.338988
101929           1         319         -42           1270   3681.754   0.3449443
102001           1         319         -60           1298   3683.279   0.3524034

==========================================

Best total count of reduced forms:

jagy@phobeusjunior:~$ 
      d    red  red/(sqrt(d) log(d))
      5      2   0.555739    5 = 5
     12      4   0.464686    12 = 2^2 * 3
     17      6   0.513627    17 = 17
     28      8   0.453711    28 = 2^2 * 7
     41     10   0.420549    41 = 41
     57     12   0.393129    57 = 3 * 19
     73     18   0.491029    73 = 73
    105     20   0.419385    105 = 3 * 5 * 7
    145     28   0.467229    145 = 5 * 29
    193     30   0.410331    193 = 193
    217     32   0.403781    217 = 7 * 31
    241     38   0.446287    241 = 241
    265     40   0.440376    265 = 5 * 53
    337     42   0.393102    337 = 337
    385     44   0.376677    385 = 5 * 7 * 11
    409     54   0.444006    409 = 409
    481     56   0.413445    481 = 13 * 37
    505     60   0.42894     505 = 5 * 101
    601     66   0.420748    601 = 601
    649     68   0.412209    649 = 11 * 59
    721     72   0.407471    721 = 7 * 103
    865     80   0.402217    865 = 5 * 173
    889     84   0.414909    889 = 7 * 127
   1009     90   0.409635    1009 = 1009
   1081     92   0.400561    1081 = 23 * 47
   1129    102   0.431871    1129 = 1129
   1201    106   0.431353    1201 = 1201
   1489    114   0.404377    1489 = 1489
   1609    118   0.398428    1609 = 1609
   1801    130   0.40865     1801 = 1801
   1969    140   0.415943    1969 = 11 * 179
   2161    146   0.409034    2161 = 2161
   2521    170   0.432282    2521 = 2521
   3241    180   0.391135    3241 = 7 * 463
   3529    198   0.408021    3529 = 3529
   3649    208   0.419803    3649 = 41 * 89
   4201    210   0.388344    4201 = 4201
   4321    216   0.392529    4321 = 29 * 149
   4369    220   0.397072    4369 = 17 * 257
   4729    230   0.395273    4729 = 4729
   5209    238   0.385319    5209 = 5209
   5401    240   0.379981    5401 = 11 * 491
   5569    258   0.400842    5569 = 5569
   6049    264   0.389817    6049 = 23 * 263
   6169    272   0.396809    6169 = 31 * 199
   6769    276   0.380341    6769 = 7 * 967
   6841    290   0.397049    6841 = 6841
   7561    306   0.394043    7561 = 7561
   8089    330   0.407763    8089 = 8089
   9241    346   0.394166    9241 = 9241
   9529    352   0.393572    9529 = 13 * 733
  10921    380   0.391059    10921 = 67 * 163
  12289    390   0.37361     12289 = 12289
  12601    394   0.37175     12601 = 12601
  12961    404   0.374736    12961 = 13 * 997
  13729    426   0.381612    13729 = 13729
  14281    434   0.37962     14281 = 14281
  14569    448   0.387165    14569 = 17 * 857
  15409    472   0.394326    15409 = 19 * 811
  15961    480   0.392582    15961 = 11 * 1451
  17329    492   0.382933    17329 = 13 * 31 * 43
  18001    516   0.392515    18001 = 47 * 383
  19009    522   0.38427     19009 = 19009
  20161    530   0.3766      20161 = 20161
  20689    532   0.372195    20689 = 17 * 1217
  21121    542   0.374515    21121 = 21121
  21961    566   0.38205     21961 = 21961
  23689    574   0.370245    23689 = 23689
  23809    576   0.370412    23809 = 29 * 821
  23881    584   0.374878    23881 = 11 * 13 * 167
  25249    596   0.370028    25249 = 7 * 3607
  26161    602   0.3659      26161 = 26161
  27049    616   0.367007    27049 = 11 * 2459
  28081    622   0.362379    28081 = 28081
  28681    660   0.379691    28681 = 23 * 29 * 43
  31201    680   0.372014    31201 = 41 * 761
  33049    702   0.371095    33049 = 33049
  33289    714   0.375814    33289 = 33289
  37129    752   0.3709      37129 = 107 * 347
  37801    756   0.368915    37801 = 103 * 367
  40441    768   0.360025    40441 = 37 * 1093
  40681    776   0.362499    40681 = 17 * 2393
  43801    794   0.354982    43801 = 43801
  43849    808   0.361006    43849 = 13 * 3373
  44209    812   0.361037    44209 = 11 * 4019
  44641    826   0.365148    44641 = 44641
  45049    848   0.372856    45049 = 19 * 2371
  46561    852   0.36735     46561 = 101 * 461
  47881    862   0.365552    47881 = 47881
  48049    878   0.371565    48049 = 48049
  49009    886   0.37058     49009 = 49009
  50521    912   0.374649    50521 = 19 * 2659
  51769    914   0.370083    51769 = 51769
  53881    966   0.381989    53881 = 53881
  58969    984   0.368886    58969 = 109 * 541
  61681   1002   0.365786    61681 = 61681
  63361   1022   0.367213    63361 = 63361
  65209   1040   0.367392    65209 = 61 * 1069
  65641   1052   0.370186    65641 = 41 * 1601
  69001   1074   0.36696     69001 = 69001
  70849   1086   0.365322    70849 = 70849
  74281   1100   0.359858    74281 = 59 * 1259
  74881   1128   0.367273    74881 = 103 * 727
  77401   1144   0.365291    77401 = 17 * 29 * 157
  81481   1180   0.365564    81481 = 17 * 4793
  84529   1200   0.363814    84529 = 137 * 617
  85801   1212   0.364239    85801 = 239 * 359
  86641   1252   0.374111    86641 = 23 * 3767
  92569   1286   0.369611    92569 = 92569
  95209   1296   0.366384    95209 = 19 * 5011
 100321   1320   0.361886    100321 = 13 * 7717
      d    red  red/(sqrt(d) log(d))
jagy@phobeusjunior:~$

enter image description here

Will Jagy
  • 25.7k
  • 2
  • 65
  • 121