¿Cómo se decide que esta función tome valores enteros?

Question

Estoy trabajando en una cuestión combinatoria. Necesito decidir cuándo la siguiente función $$\frac{m(7m^2 - 22m +7)}{ \sqrt{ (m^2- 2m + 9)(9m^2 - 2m +1) } } $$ toma valores enteros con la siguiente suposición: 1) m toma todos los valores enteros positivos; 2) $(m^2- 2m + 9)(9m^2 - 2m +1)$ es un cuadrado perfecto (= $n^2$ para algún número entero $n$ ). El cómputo es limitado para $m < 20000$ muestra $m = 1, 5$ .

Muchas gracias, Jianmin

Answer 1

Hay dos sustituciones que deberían ocurrírsele como posibilidades inmediatas al mirar esta integral: $u = 2x-1$ y $u = \sqrt{2x-1}$ . Elige uno y pruébalo; si funciona, genial, y si no, puedes seguir probando el otro. Usted no tiene que acertar en el primer intento, y no debería empezar a preocuparse hasta que haya agotado las posibilidades obvias y directas. En este caso, eso no ocurrirá (a menos que cometas un error): ambos sustituciones funcionan. De hecho, deberías probar ambas para ver cómo que funcionen, porque es probable que necesites estos dos tipos de sustituciones antes de terminar el curso.

Answer 2

El problema específico de Diofantino del OP ha sido respondido, pero aún así vale la pena señalar una técnica general que se aplica a problemas de este tipo:

Dada una función algebraica $f(x)$ , encontrar todos los $x$ de manera que ambos $x$ y $f(x)$ son números enteros

siempre que $f$ no es en sí mismo un polinomio pero puede expandirse en una serie de potencias sobre $x=\infty$ con coeficientes racionales . Tal es el caso de la función $$ f(m) = \frac{m (7m^2-22m+7)}{\sqrt{(m^2-2m+9)(9m^2-2m+1)}} = \frac{7}{3} m - \frac{128}{27} + O(1/m) $$ del problema de combinatoria, o de hecho su denominador $$\sqrt{(m^2-2m+9)(9m^2-2m+1)} = 3m^2−\frac{10}{3}m+\frac{337}{27}+O(1/m)$$ (como he señalado en mi comentario a la respuesta de C.Matthew). A menudo $f$ es una función racional, que satisface automáticamente la condición siempre que no sea un polinomio. La técnica es sencilla:

Utilice la expansión de la serie de potencia para escribir $f(x) = P(x) + O(1/x)$ con $P \in {\bf Q}[x]$ , encontrar un denominador común $D$ para que $DP \in {\bf Z}[x]$ y observar que una vez $x$ es lo suficientemente grande como para que el $O(1/x)$ error cae por debajo de $1/D$ en valor absoluto la única manera de que $Df(x)$ puede ser integral es para $x$ para ser una raíz de $f(x) = P(x)$ . Esto reduce el problema a una búsqueda finita.

El candidato no dijo de dónde procedía exactamente su pregunta, pero estos problemas surgen a menudo en la teoría de los diseños combinatorios y los grafos fuertemente regulares. Por ejemplo, en un grafo de Moore de circunferencia 5 y grado $d$ cada vértice tiene $d$ vecinos y dos vértices distintos cualesquiera son xadyacentes xo tienen un vecino común, en cuyo caso ese vecino es único. Utilizando el hecho de que cada valor propio de la matriz de adyacencia tiene multiplicidad integral, se demuestra que $d=2$ o $d=m^2+m+1$ para algún número entero $m$ tal que $(m^2+m+1)(m^2+m-1) / (2m+1) \in {\bf Z}$ . Así que escribimos $$ 16 \frac{(m^2+m+1) (m^2+m-1)} {2m+1} = 8m^3+12m^2+2m-1 - \frac{15}{2m+1} $$ y (ya que $15/(2m+1)$ no puede desaparecer) se deduce que $2m+1 \leq 15$ Así que $m \leq 7$ . Entonces encontramos que de los candidatos restantes sólo $m=1,2,7$ trabajo. De ahí que $d$ es una de 2, 3, 7 o 57. [Véase, por ejemplo, la obra de Cameron y Van Lint Diseños, gráficos, códigos y sus enlaces (LMS 1991, 1996) para este y otros muchos ejemplos. Así, cada uno de los $d=2,3,7$ se produce para un único grafo de Moore, a saber, el de 5 ciclos, el de Petersen y el de Hoffman-Singleton, respectivamente, mientras que la existencia de un grafo de Moore de grado 57 es un famoso problema abierto].

Puede haber más atajos cuando $D$ y/o la constante implícita en $O(1/x)$ son lo suficientemente grandes como para que la búsqueda final, aunque sea finita, siga siendo inconveniente o inviable hacerla exhaustivamente. Por ejemplo, en el problema del grafo de Moore, $15/(2m+1)$ debe ser integral, por lo que $2m+1$ debe ser un factor de $15$ y se obtienen inmediatamente las soluciones $m=1,2,7$ correspondiente a los factores $3,5,15$ . El numerador $15$ podría haberse predicho a partir del valor $15/16$ tomada por $(m^2+m+1) (m^2+m-1)$ en $m=-1/2$ la raíz del denominador $2m+1$ . En general, si $f(x)$ es una función racional $A(x)/B(x)$ con $A,B \in {\bf Z}[x]$ relativamente primos, podemos utilizar el algoritmo euclidiano para polinomios para encontrar $M,N \in {\bf Z}[x]$ tal que $MA-NB$ es un número entero no nulo, digamos $R$ ; entonces si $f(x)$ es un número entero, entonces también lo es $$ M(x) f(x) - N(x) = \frac{M(x)A(x) - N(x)B(x)}{B(x)} = \frac{R}{B(x)} , $$ y sólo necesitamos encontrar soluciones enteras de $B(x) = r$ para cada uno de los factores $r$ de $R$ y probar cada uno de estos candidatos. $R$ es un factor de la resultante de $A$ y $B$ . En realidad, esto no está muy lejos del análisis de G.Robinson: si elevamos al cuadrado para obtener la función racional $m^2 (7m^2-22m+7)^2 / ((m^2-2m+9)(9m^2-2m+1))^2$ la resultante es $2^{36} 3^{12}$ explicando los factores de 2 y 3 que surgieron en esa solución. Todavía hay $2 \cdot 37 \cdot 13 = 962$ factores a probar (permitiendo tanto los negativos como los positivos $r$ ), pero eso es mucho menos que el número de candidatos que el método genérico requeriría probar.

Answer 3

En este caso, basta con una aproximación elemental. Si el cociente dado es un número entero, entonces cualquier primo $p$ que divide $m^2 -2m+9$ divide a cualquiera de los dos $m$ o $7m^2-22m+7$ . Si $p$ divide $m$ entonces claramente $p =3$ . Si $p$ divide $7m^2-22m+7$ entonces $p$ divide $$[7m^2-14m+63 - (7m^2-22m+7)] = 8m+56. $$ Por lo tanto, o bien $p=2$ o $p$ divide $m+7.$ En el segundo caso, $p$ divide $$(m^2-2m+9) -(m+7) = m^2-3m+2 = (m-1)(m-2).$$ Ahora $p$ divide $8$ si $m \equiv 1$ (mod p) y $p$ divide $9$ si $m \equiv 2$ (mod p). Por lo tanto, $(m-1)^2 +8$ tiene la forma $2^a 3^b$ . El máximo común divisor de $7m^2 -22m+7$ y $9m^2-2m+1$ también está muy restringido. Si $p$ es un primo impar que divide ambos $7m^2-22m +7$ y $9m^2-2m+1$ entonces (restando la primera de la segunda y dividiendo por $2$ ), $p$ divide $m^2 +10m-3$ . Entonces (restando la primera ecuación de $7$ veces la nueva ecuación), $p$ divide $92m-28 = 4(23m-7)$ y por lo tanto $p$ divide $7m^2 +m = 7m^2-22m +7 + (23m-7).$ Desde $p$ no divide $m$ , $p$ divide $7m+1$ y, por lo tanto, divide $(23m-7)-3(7m+1) = 2(m-5).$ Pero ahora $p$ también divide $7(m-5) + 36$ Así que $p$ divide $36$ y $p=3$ .

Por lo tanto, vemos que $m^2 -2m+9$ tiene la forma $2^a 3^b$ y $9m^2 - 2m+1$ tiene la forma $2^e 3^f$ para los enteros $a,b,e,f$ . Pero ahora observe que el máximo común divisor divisor $d$ de $m^2 -2m+9$ y $9m^2 - 2m+1$ divide $16m-80$ que es la última ecuación menos 9 veces la primera. También, $16$ no divide $d$ , ya que $(m-1)^2 +8$ no es divisible por 16 (y tampoco lo es $8m^2 +(m-1)^2$ ). Si $h$ es la parte impar de $d$ entonces $m \equiv 5$ (mod h), y $h$ divide $24$ . Por lo tanto, $d$ divide $24$ . Si $m$ es divisible por $3$ entonces $9m^2 - 2m+1$ debe ser un poder de $2$ pero no es divisible por $16$ , dando lugar a $m=0$ bajo los supuestos actuales. Por lo tanto, podemos suponer que $m$ no es divisible por $3$ . Si $9$ divide $m^2-2m +9$ entonces $ m \equiv 2 $ (mod 9) por lo que $9m^2 - 2m+1 \in \{3,12,24\}$ , una contradicción. Por lo tanto, $m^2-2m +9 = 24$ y $m= 5$ o $m^2-2m +9 = 8$ y $m= 1$ son las únicas posibilidades que quedan (para los positivos $m$ no es divisible por 3, como suponemos actualmente). Así pues, $m=1 $ y $m=5$ son los únicos enteros positivos que dan un valor integral. (Observación posterior: Nótese que la solución adicional $m=-1$ mencionado en el comentario de Noam Elkies corresponde al caso $9m^2 - 2m+1 = 12 = m^2 -2m +9$ lo que no ocurre para los positivos $m$ ).