Menor valor que toma una ecuación cuadrática polinomio en dos variables.

Question

Deje $p$ ser un grado $2$ polinomio con coeficientes enteros, dicen $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ Me gustaría encontrar un algoritmo que resuelve los siguientes:

Problema 1: Dado $A,B,C,D,E,F$ determinar el mínimo valor absoluto que $p(x,y)$ puede tomar con $x,y \in \mathbb Z$.

¿Existe una manera de hacer esto? ¿Cuál es una manera eficiente, a través de algoritmos hablando?

El problema es muy simple, la forma $Ax^2 + By^2 + Cxy$ es positivo (o negativo) definitiva. A continuación, $|p(x,y)|$ toma un mínimo de más de $\mathbb R$, y que será suficiente para considerar que un pequeño número entero de puntos en la vecindad.

De lo contrario, (tal vez después de multiplicar $p$ por algún entero positivo) se puede encontrar una representación de $p(x,y)$ en la forma$p(x,y) = (ax + by + c)^2 - d (a'x + b'y + c')^2$,$d \in \mathbb N$, squarefree y $a,b,c,a',b',c' \in \mathbb Z$. Ahora podemos expresar el problema en más de fantasía términos:

Problema 2: Dado $a,b,c,a',b',c'$, determinar el mínimo de la norma de un número $\alpha = k + l \sqrt{d} \in \mathbb Z[\sqrt{d}]$ ejemplo donde $k = ax + by + c$, $l = a'x + b'y + c'$ para algunos $x,y \in \mathbb Z$.

El último es un poco más cerca de la motivación original, y da acceso a algunas de la maquinaria disponible para cuadrática campos.

Un enfoque posible es la lista de elementos de $\mathbb Z [\sqrt{d}]$ con el fin de aumentar la norma, hasta equivalencia modulo adecuadamente un elegido de enteros grandes (que no es una tarea sencilla, pero es algorítmicamente factible como lo que puedo decir) y, a continuación, para cada una de las $\alpha = k + l \sqrt{d}$ en la lista, compruebe si toma la forma deseada. Pero que no es ni elegante ni muy eficiente. Hay mejores maneras?

Answer 1

La forma cuadrática $A x^2 + C x y + B y^2$ es positivo o negativo definido (lo que implica $|p(x,y)| \to \infty$$\|(x,y)\| \to \infty$ ) si $C^2 < 4 A B$ e indefinido (lo que implica $p(x,y)$ no está delimitado por encima o por debajo) si $C^2 > 4 AB$. Su afirmación acerca de que "si el líder de los coeficientes tienen el mismo signo" es falso, por ejemplo, $x^2 + 3 x y + y^2$ no tiene mínimo (intente $x = -y$).

Answer 2

EDIT: pongo la información relacionada a este, incluyendo el método utilizado en la salida del sistema a continuación, en http://math.blogoverflow.com/

Creo que se debe trabajar en el caso de $D=E=F=0$ en primer lugar, es más complicado de lo que piensas. Dada una forma indefinida $$ f(x,y) = P x^2 + Q xy + R y^2 $$ with integers $P,Q,R$ y discriminante $$ \Delta = Q^2 - 4 P R $$ positivo pero no un cuadrado, aplicar Gauss-método de Lagrange. En primer lugar, se pueden tomar varias medidas para reducir el formulario, donde "reducido" es equivalente a: $$ PR < 0 \; \; \mbox{and} \; \; Q > |P+R|. $$ Después de eso, es un teorema de Lagrange que todos los números de $n$ $|n| < \sqrt \Delta / 2$ que puede ser escrito primitivamente $\gcd(x,y) =1$ $n=P x^2 + Q xy + R y^2$ se producen como coeficientes en el ciclo de formas reducidas. Por ejemplo,

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
=========================================

---