Smallest value taken by a quadratic polynomial in two variables.

Question

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following:

Problem 1: Given $A,B,C,D,E,F$ determine the smallest possible absolute value that $p(x,y)$ can take with $x,y \in \mathbb Z$.

Does there exists a way to do this? What is an efficient way, algorithmically speaking?

The problem is very simple the form $Ax^2 + By^2 + Cxy$ is positive (or negative) definite. Then, $|p(x,y)|$ takes a minimum over $\mathbb R$, and it will suffice to consider a small number of integer points in the neighbourhood.

Otherwise, (perhaps after multiplying $p$ by some positive integer) one can find a representation of $p(x,y)$ in the form $p(x,y) = (ax + by + c)^2 - d (a'x + b'y + c')^2$, with $d \in \mathbb N$, squarefree and $a,b,c,a',b',c' \in \mathbb Z$. We can now phrase the problem in more fancy terms:

Problem 2: Given $a,b,c,a',b',c'$, determine the least norm of a number $\alpha = k + l \sqrt{d} \in \mathbb Z[\sqrt{d}]$ such where $k = ax + by + c$, $l = a'x + b'y + c'$ for some $x,y \in \mathbb Z$.

The latter is somewhat closer to the original motivation, and gives access to some of the machinery available for quadratic fields.

One possible approach is to list elements of $\mathbb Z [\sqrt{d}]$ in order of increasing norm, up to equivalence modulo an appropriately chosen large integer (which is not a simple task, but is algorithmically feasible as far as I can tell), and then for each $\alpha = k + l \sqrt{d}$ on the list, verify if it takes the desired form. But that's neither elegant, nor very efficient. Are there better ways?

Answer 1

The quadratic form $A x^2 + C x y + B y^2$ is positive or negative definite (implying $|p(x,y)| \to \infty$ as $\|(x,y)\| \to \infty$ ) if $C^2 < 4 A B$ and indefinite (implying $p(x,y)$ is not bounded above or below) if $C^2 > 4 AB$. Your statement about "if the leading coefficients have the same sign" is false, e.g. $x^2 + 3 x y + y^2$ has no minimum (try $x = -y$).

Answer 2

EDIT: I put information related to this, including the method used in the computer output below, at http://math.blogoverflow.com/

I think you should work out the case $D=E=F=0$ first, it is trickier than you think. Given an indefinite form $$ f(x,y) = P x^2 + Q xy + R y^2 $$ with integers $P,Q,R$ and discriminant $$ \Delta = Q^2 - 4 P R $$ positive but not a square, apply the Gauss-Lagrange method. First, it may take several steps to reduce the form, where "reduced" is equivalent to: $$ PR < 0 \; \; \mbox{and} \; \; Q > |P+R|. $$ After that, it is a theorem of Lagrange that all numbers $n$ with $|n| < \sqrt \Delta / 2$ that can be written primitively $\gcd(x,y) =1$ as $n=P x^2 + Q xy + R y^2$ occur as coefficients in the cycle of reduced forms. For example,

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 53 475 29

  0  form             53         475          29  delta     16
  1  form             29         453        -123


           0          -1
           1          16

To Return  
          16           1
          -1           0

0  form   29 453 -123   delta  -3
1  form   -123 285 281   delta  1
2  form   281 277 -127   delta  -2
3  form   -127 231 327   delta  1
4  form   327 423 -31   delta  -14
5  form   -31 445 173   delta  2
6  form   173 247 -229   delta  -1
7  form   -229 211 191   delta  1
8  form   191 171 -249   delta  -1
9  form   -249 327 113   delta  3
10  form   113 351 -213   delta  -1
11  form   -213 75 251   delta  1
12  form   251 427 -37   delta  -12
13  form   -37 461 47   delta  9
14  form   47 385 -379   delta  -1
15  form   -379 373 53   delta  7
16  form   53 369 -393   delta  -1
17  form   -393 417 29   delta  15
18  form   29 453 -123


  form   29 x^2  + 453 x y  -123 y^2 

minimum was   29rep   x = 1   y = 0 disc   219477 dSqrt 468.48372437  M_Ratio  260.9715
Automorph, written on right of Gram matrix:  
-4500809  -71507280
-16859440  -267856889
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

---

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 53 475  31

  0  form             53         475          31  delta     15
  1  form             31         455         -97


           0          -1
           1          15

To Return  
          15           1
          -1           0

0  form   31 455 -97   delta  -4
1  form   -97 321 299   delta  1
2  form   299 277 -119   delta  -3
3  form   -119 437 59   delta  7
4  form   59 389 -287   delta  -1
5  form   -287 185 161   delta  2
6  form   161 459 -13   delta  -35
7  form   -13 451 301   delta  1
8  form   301 151 -163   delta  -1
9  form   -163 175 289   delta  1
10  form   289 403 -49   delta  -8
11  form   -49 381 377   delta  1
12  form   377 373 -53   delta  -7
13  form   -53 369 391   delta  1
14  form   391 413 -31   delta  -14
15  form   -31 455 97   delta  4          -1 composed with form zero  
16  form   97 321 -299   delta  -1
17  form   -299 277 119   delta  3
18  form   119 437 -59   delta  -7
19  form   -59 389 287   delta  1
20  form   287 185 -161   delta  -2
21  form   -161 459 13   delta  35
22  form   13 451 -301   delta  -1
23  form   -301 151 163   delta  1
24  form   163 175 -289   delta  -1
25  form   -289 403 49   delta  8
26  form   49 381 -377   delta  -1
27  form   -377 373 53   delta  7
28  form   53 369 -391   delta  -1
29  form   -391 413 31   delta  14
30  form   31 455 -97


  form   31 x^2  + 455 x y  -97 y^2 

minimum was   13rep   x = -95   y = -452 disc   219053 dSqrt 468.03098188  M_Ratio  227.9428
Automorph, written on right of Gram matrix:  
-55934164938053  -832725277152184
-266128696821832  -3962016650548813
=========================================

---