Skip to main content
MathOverflow

Return to Answer

added 940 characters in body
Source Link
Will Jagy
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

First reference is "Binary Quadratic Forms: Classical Theory and Modern Computations" by Duncan A. Buell.

From this, and from a much older book, "Introduction to the Theory of Numbers" by Leonard Eugene Dickson: every form is "equivalent" to a reduced form, that is it represents the same numbers and primitively represents the same numbers. (Dickson uses "properly"). So we might as well stick with reduced forms. Meanwhile, it is a theorem of Lagrange (Theorem 85,page 111 in Dickson) that every number $n$ that is primitively represented by a form and lies between your bounds $$ \frac{- \sqrt d}{2} < n < \frac{\sqrt d}{2} $$ does in fact occur as the "first" coefficient of a form in the cycle. So it is true that the set of primitively represented numbers has cardinality bounded by the cycle length, but this length may be larger than $ \sqrt d$ and therefore useless, your interval of interest has length only $ \sqrt d.$

First reference is "Binary Quadratic Forms: Classical Theory and Modern Computations" by Duncan A. Buell.

From this, and from a much older book, "Introduction to the Theory of Numbers" by Leonard Eugene Dickson: every form is "equivalent" to a reduced form, that is it represents the same numbers and primitively represents the same numbers. (Dickson uses "properly"). So we might as well stick with reduced forms. Meanwhile, it is a theorem of Lagrange (Theorem 85,page 111 in Dickson) that every number $n$ that is primitively represented by a form and lies between your bounds $$ \frac{- \sqrt d}{2} < n < \frac{\sqrt d}{2} $$ does in fact occur as the "first" coefficient of a form in the cycle. So it is true that the set of primitively represented numbers has cardinality bounded by the cycle length, but this length may be larger than $ \sqrt d$ and therefore useless, your interval of interest has length only $ \sqrt d.$

added 136 characters in body
Source Link
Will Jagy
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

MeanwhileSo, I am not sure you can have a universal bound that much smaller than $\sqrt d.$ For the principal cycle with $ d = 1201$ and $ \sqrt d = 34.65\ldots$ I get most numbers primitively represented, then add in $25, 27, 32$ imprimitive, so the total missing set total 16, each $\pm$ with absolute values $11, 13, 17, 22, 26, 29, 31, 34.$ Out of 69 numbers from $-34$ to $34$ that is about 77 percent success. Wait, I screwed up, you want successes between $-17$ and $17$ in which case we have only 6 misses out of 35 numbers, up to $ 83\% $ successes.

Meanwhile, I am not sure you can have a universal bound that much smaller than $\sqrt d.$ For the principal cycle with $ d = 1201$ and $ \sqrt d = 34.65\ldots$ I get most numbers primitively represented, then add in $25, 27, 32$ imprimitive, so the total missing set total 16, each $\pm$ with absolute values $11, 13, 17, 22, 26, 29, 31, 34.$ Out of 69 numbers from $-34$ to $34$ that is about 77 percent success.

So, I am not sure you can have a universal bound that much smaller than $\sqrt d.$ For the principal cycle with $ d = 1201$ and $ \sqrt d = 34.65\ldots$ I get most numbers primitively represented, then add in $25, 27, 32$ imprimitive, so the total missing set total 16, each $\pm$ with absolute values $11, 13, 17, 22, 26, 29, 31, 34.$ Out of 69 numbers from $-34$ to $34$ that is about 77 percent success. Wait, I screwed up, you want successes between $-17$ and $17$ in which case we have only 6 misses out of 35 numbers, up to $ 83\% $ successes.

Source Link
Will Jagy
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

By the way, you need $d$ to not be a square.

From Buell's book, page 82: "Computations of class numbers have shown that about $80 \%$ of the class numbers for positive prime discriminants are actually 1," and "It is conjectured, and is almost assuredly true, that the number of discriminants of class number 1 is infinite."

Now, those numbers that are primitively represented occur as coefficient $a$ in the full cycle. As there is not generally tremendous repetition in these numbers, I would say you are asking essentially about the cycle length. This is, I'm afraid, somewhat random. I can say, of course, that any number divisible by a prime $p$ with $(d | p) = -1$ is not primitively represented, and is not represented at all if the relevant exponent is odd. But this gets you only so far within your stringent bounds.

Meanwhile, I am not sure you can have a universal bound that much smaller than $\sqrt d.$ For the principal cycle with $ d = 1201$ and $ \sqrt d = 34.65\ldots$ I get most numbers primitively represented, then add in $25, 27, 32$ imprimitive, so the total missing set total 16, each $\pm$ with absolute values $11, 13, 17, 22, 26, 29, 31, 34.$ Out of 69 numbers from $-34$ to $34$ that is about 77 percent success.

phoebus:~/Cplusplus> ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
1 1 -300

0  form   1 33 -28   delta  -1
1  form   -28 23 6   delta  4
2  form   6 25 -24   delta  -1
3  form   -24 23 7   delta  4
4  form   7 33 -4   delta  -8
5  form   -4 31 15   delta  2
6  form   15 29 -6   delta  -5
7  form   -6 31 10   delta  3
8  form   10 29 -9   delta  -3
9  form   -9 25 16   delta  1
10  form   16 7 -18   delta  -1
11  form   -18 29 5   delta  6
12  form   5 31 -12   delta  -2
13  form   -12 17 19   delta  1
14  form   19 21 -10   delta  -2
15  form   -10 19 21   delta  1
16  form   21 23 -8   delta  -3
17  form   -8 25 18   delta  1
18  form   18 11 -15   delta  -1
19  form   -15 19 14   delta  1
20  form   14 9 -20   delta  -1
21  form   -20 31 3   delta  10
22  form   3 29 -30   delta  -1
23  form   -30 31 2   delta  16
24  form   2 33 -14   delta  -2
25  form   -14 23 12   delta  2
26  form   12 25 -12   delta  -2
27  form   -12 23 14   delta  2
28  form   14 33 -2   delta  -16
29  form   -2 31 30   delta  1
30  form   30 29 -3   delta  -10
31  form   -3 31 20   delta  1
32  form   20 9 -14   delta  -1
33  form   -14 19 15   delta  1
34  form   15 11 -18   delta  -1
35  form   -18 25 8   delta  3
36  form   8 23 -21   delta  -1
37  form   -21 19 10   delta  2
38  form   10 21 -19   delta  -1
39  form   -19 17 12   delta  2
40  form   12 31 -5   delta  -6
41  form   -5 29 18   delta  1
42  form   18 7 -16   delta  -1
43  form   -16 25 9   delta  3
44  form   9 29 -10   delta  -3
45  form   -10 31 6   delta  5
46  form   6 29 -15   delta  -2
47  form   -15 31 4   delta  8
48  form   4 33 -7   delta  -4
49  form   -7 23 24   delta  1
50  form   24 25 -6   delta  -4
51  form   -6 23 28   delta  1
52  form   28 33 -1   delta  -33
53  form   -1 33 28   delta  1
54  form   28 23 -6   delta  -4
55  form   -6 25 24   delta  1
56  form   24 23 -7   delta  -4
57  form   -7 33 4   delta  8
58  form   4 31 -15   delta  -2
59  form   -15 29 6   delta  5
60  form   6 31 -10   delta  -3
61  form   -10 29 9   delta  3
62  form   9 25 -16   delta  -1
63  form   -16 7 18   delta  1
64  form   18 29 -5   delta  -6
65  form   -5 31 12   delta  2
66  form   12 17 -19   delta  -1
67  form   -19 21 10   delta  2
68  form   10 19 -21   delta  -1
69  form   -21 23 8   delta  3
70  form   8 25 -18   delta  -1
71  form   -18 11 15   delta  1
72  form   15 19 -14   delta  -1
73  form   -14 9 20   delta  1
74  form   20 31 -3   delta  -10
75  form   -3 29 30   delta  1
76  form   30 31 -2   delta  -16
77  form   -2 33 14   delta  2
78  form   14 23 -12   delta  -2
79  form   -12 25 12   delta  2
80  form   12 23 -14   delta  -2
81  form   -14 33 2   delta  16
82  form   2 31 -30   delta  -1
83  form   -30 29 3   delta  10
84  form   3 31 -20   delta  -1
85  form   -20 9 14   delta  1
86  form   14 19 -15   delta  -1
87  form   -15 11 18   delta  1
88  form   18 25 -8   delta  -3
89  form   -8 23 21   delta  1
90  form   21 19 -10   delta  -2
91  form   -10 21 19   delta  1
92  form   19 17 -12   delta  -2
93  form   -12 31 5   delta  6
94  form   5 29 -18   delta  -1
95  form   -18 7 16   delta  1
96  form   16 25 -9   delta  -3
97  form   -9 29 10   delta  3
98  form   10 31 -6   delta  -5
99  form   -6 29 15   delta  2
100  form   15 31 -4   delta  -8
101  form   -4 33 7   delta  4
102  form   7 23 -24   delta  -1
103  form   -24 25 6   delta  4
104  form   6 23 -28   delta  -1
105  form   -28 33 1   delta  33
106  form   1 33 -28
 disc   1201 dSqrt 34.655446902