Minimum value of a positive definite binary quadratic form along integers

Question

Is there a formula for the least non-zero value of $$f(x,y):=ax^2+bxy+cy^2$$ as $x,y$ assume integer values? Here $a,b,c$ are integers with $a,d>0$ and $b^2-4ac<0$.

Answer 1

I don't know of a simple solution. Here's a terrible one that at least shows that the problem is solvable.

If $a$ or $c$ is less than 0, you can make $f$ as small as you like, so assume neither is negative. If either was 0 then $b^2<0$, so both are positive. If $b=0$ then the minimum is $\min(a,\,c).$ If $b>0$ then negating $x$ flips $b$ while leaving the problem otherwise unchanged. So without loss of generality assume $b<0<a\le c.$

An obvious upper bound is $f(1,1)=a+b+c$ which is positive by the discriminant assumption (and the arithmetic-geometric mean inequality). Now it remains only to check if 1, 2, ..., $a+b+c-1$ are possible values. But each of these is a Diophantine quadratic on two variables, for which algorithms are known. Apply the algorithm to each of the equations $ax^2+bxy+cy^2=k$ in turn; if the equation is solvable then return $k$, else return $a+b+c.$

Answer 2

There is an algorithm which results in Gauss-Lagrange-Eisenstein reduced form, which answers your question and more. Oh, Gauss and or Lagrange did this, I throw in the name Eisenstein because Gauss did not allow $b$ to be odd. Write your form as $$ \langle a,b,c \rangle. $$ If $c < a,$ or if $c = a$ and $b<0,$ replace the form (the triple) by $$ \langle c, \; -b, \; a \rangle $$ (and rename as abc again). If either $b > a $ or $b \leq -a,$ find the integer $n$ so that $-a < 2an+b \leq a,$ then replace the form by $$ \langle a, \; \; 2an+b, \; \; an^2 + bn+c \rangle $$ (and rename as abc again). Keep alternating these steps until the form is "reduced" which means $$ 1 \leq a \leq c, \; \; \mbox{AND} \; \; \; -a < b \leq a, \; \; \mbox{AND IF} \; \; a=c \; \; \; \mbox{THEN} \; \; b \geq 0 . $$ Once a form is reduced, the first coefficient (the new $a$ value) is the smallest positive element represented.

This algorithm is quick; it is as fast as, and very similar to, the Euclidean algorithm for finding the GCD of two numbers.

Note that both the algorithm and the nature of "reduced" are a little different for indefinite binary forms. See http://math.blogoverflow.com/2014/08/23/binary-quadratic-forms-over-the-rational-integers-and-class-numbers-of-quadratic-%EF%AC%81elds/ for lots of stuff in a small space.

Gauss reduction for positive forms is in many, many number theory books.