Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an indefinite integral quadratic form $Q(x,y)=ax^2 +bxy + cy^2$ with $b^2-4ac=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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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  
share|improve this answer
    
Sorry about the non-square. 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? –  paarshad Jul 14 '10 at 0:19
    
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? –  paarshad Jul 14 '10 at 0:57
    
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. –  Will Jagy Jul 14 '10 at 3:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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