Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have a set $S\subset\mathbb{Z}[x,y].$ How can one efficiently partition the polynomials into sets such that the primes represented by the polynomials in any given set are identical? For these purposes, "efficient" can be interpreted as "subquadratic", though I'm interested in practical as well as theoretical/worst-case.

A special case of particular interest: binary quadratic forms $ax^2+bxy+cy^2.$

For any pair of polynomials, it's possible to check if the two are equivalent forms. Of course this requires checking quadratically many pairs. One practical speedup would be to first partition the polynomials by discriminant—in the case of binary quadratic forms, $b^2-4ac.$ This takes only (essentially) linear time, and results in speedup by a factor of $k$ if there are $k$ discriminants with roughly equal numbers of polynomials for each (time $n^2/k^2$ for each discriminant, $k$ discriminants). Are there further invariants that can be used in similar fashion?

share|cite|improve this question
A good reference might be David Cox's "Primes of the Form x^2+ny^2." He discusses some applications of genus theory, class field theory, and complex multiplication to this kind of problem. – Tony Mar 21 '11 at 2:52
up vote 0 down vote accepted

I will address the special case of binary quadratic forms. Some of this applies more generally.

First partition the polynomials $ax^2+bxy+cy^2$ by their discriminant $\Delta=b^2-4ac$, as mentioned in the question. Polynomials with $\Delta>0$ have a unique reduced form, that is, can be represented uniquely as $ax^2+bxy+cy^2$ with $$\left|\sqrt\Delta-2|c|\right|<b<\sqrt\Delta$$

So within a given positive discriminant, equivalent forms can be collected immediately.

Polynomials with negative discriminant have only finitely many forms with $$|b|\le a\le c$$ (To be reduced, $b\ge0$ if $a\in\{|b|,c\},$ but of course finitude does not depend on this.) It's not clear that this is practical when comparing forms; it depends on the size of the coefficients and the number of forms of a given discriminant.

Of course since only the primes in those discriminants are desired, certain transformations can be made that would otherwise be impermissible. For example, polynomials with non-unitary content $c$ can be reduced to either $\{c\}$ or $\emptyset$ as appropriate. Broadening slightly to binary quadratic polynomials, parity substitutions can be made: $$x^2+2y^2\mapsto (2x+1)^2+2y^2$$

share|cite|improve this answer

Your Answer


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.