Given an indefinite integral quadratic form $Q(x,y)=ax^2 +bxy + cy^2$ with $b^24ac=d>0$, is there an easy way to count the number of integers in $t \in (\sqrt{d}/2, \sqrt{d}/2)$ such that there exists $(m,n)\in Z \times N$ with $Q(m,n)=t$, ie. m any integer, n a positive integer? Good upper bounds would also be acceptable.
1 Answer
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.$
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.
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.
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

$\begingroup$ Sorry about the nonsquare. I would be happy with d fundamental as well. Let's say I modify it so Q is reduced. You mentioned that I was essentially talking about the cycle length. Does that mean that the number of integers <$\sqrt{d}/2$ represented is bounded by the cycle length? $\endgroup$– paarshadJul 14, 2010 at 0:19

$\begingroup$ Also so I don't waste a trip to the library, is the book you're referring to "Binary Quadratic Forms: Classical Theory and Modern Computations" by Duncan Buell? $\endgroup$– paarshadJul 14, 2010 at 0:57

$\begingroup$ Yes to both questions, but the cycle length bound will often be useless, very likely so in class number one. Whether you begin with a reduced form or not changes nothing, you reduce it anyway to find the small values. If you remain confused, just email me. $\endgroup$ Jul 14, 2010 at 3:20