Dividir triples pitagóricos

Question

¿Se puede dividir el conjunto de los números enteros positivos en un número finito de subconjuntos libres de triples pitagóricos? En caso afirmativo, ¿cuál es el menor número de tales subconjuntos? Haciendo conjeturas, yo menos sorprendido si la respuesta fuera 3.

Observa que los 2 subconjuntos de enteros tales que la mayor potencia de 5 que los divide es a) pares b) impar consiguen dividir la mayoría de los triples primitivos, además de todos los múltiplos de éstos.

Obsérvese también que Schur demostró que los números enteros positivos no pueden dividirse en ningún número finito de subconjuntos sin suma (es decir, ninguna partición finita puede dividir todas las potencias de 1 triples de Fermat), mientras que el teorema de Fermat demuestra que todas las potencias de n (n>2) triples pueden dividirse mediante la partición trivial en 1 conjunto.

Edita: Dado que se trata de un problema abierto conocido, vamos a añadir la etiqueta [open-problem] y a convertir esta pregunta en wiki comunitaria. La idea es tener una respuesta separada para cada posible enfoque para resolver este problema. Si tienes alguna idea adicional o una referencia para contribuir a una respuesta, sólo necesitas 100 rep para hacerlo. Todavía estamos averiguando exactamente cómo manejar los problemas abiertos en MO. La discusión está teniendo lugar en este hilo de tea.mathoverflow.net .

Answer 1

Este problema aparece en el libro de Croot y Lev de 2007 "Open Problems in Additive Combinatorics" ( http://people.math.gatech.edu/~ecroot/E2S-01-11.pdf ), donde se atribuye a Erdos y Graham (este último ofrece 250 dólares para su solución).

Otras referencias pueden ser las "Notas sobre el sistema triple pitagórico" de Cooper y Poirel ( http://www.math.sc.edu/~cooper/pth.pdf ), que menciona que incluso el caso de si 2 colores son suficientes está abierto. También exhiben una 2-coloración de los números enteros de 1 a 1344 sin ningún triples pitagóricos monocromáticos.

ACTUALIZACIÓN (5/4/16): A nuevo preprint de Heule, Kullmann y Marek (que aparecerá en la conferencia SAT 2016) responde a la pregunta de $2$ subconjuntos en negativo: Si $\{1,2,\dots,7825\}$ se divide en dos subconjuntos, uno de ellos debe contener un triple pitagórico. En $7825$ aquí está apretado. La demostración está fuertemente asistida por ordenador, y las ideas clave parecen ser plantear el problema en el lenguaje de la satisfacibilidad, y establecer un método de divide y vencerás para que la (enorme) instancia resultante sea manejable por los solucionadores de satisfacibilidad más avanzados.

Answer 2

Una forma de reformular parte de la respuesta de David Eppstein: la afirmación más fuerte ("tipo Szemeredi") de que un subconjunto de densidad positiva de los enteros contiene infinitos triples pitagóricos NO es cierta, como muestra tu ejemplo del conjunto de enteros con partes impar 3 mod 4 (o, supongo, el conjunto de enteros impar).

Pregunta ociosa, vagamente formulada: ¿se puede construir una subsecuencia de densidad positiva de Z que no contenga triples pitagóricos, pero sin ninguna razón p-ádica obvia?

Pregunta ociosa ortogonal: ¿se puede dividir Z_p - 0 en un número finito de trozos tal que ninguno contenga una solución de x^2 + y^2 = z^2?

Answer 3

Se puede llegar en parte hasta ahí con una partición en dos partes en los números cuyas partes Impares son 1 mod 4 y 3 mod 4 respectivamente.

Cada triple pitagórica tiene la forma k^2(m^2-n^2), k^2(2mn), k^2(m^2+n^2), para algunos k, m, y n, con m y n que tienen diferente paridad entre sí y m > n. La partición de dos partes descrito anteriormente pone k^2(m^2-n^2) y k^2(m^2+n^2) en diferentes particiones siempre que m es par y n es impar.

Sin embargo, esto no divide los triples con m impar, n par, y las partes impar de m y n ambas congruentes a 1 mod 4: en ese caso, a, b y c tendrán todas partes impar congruentes a 1 mod 4. Por ejemplo, k=1 m=5 n=2: la triple pitagórica 21,20,29 no se divide por esta partición bidireccional.

Answer 4

Considere una estrategia codiciosa: construya conjuntos S1, S2, S3, ... colocando cada número entero positivo c en el conjunto más pequeño que no contenga a, b con a^2 + b^2 = c^2.

Entonces S2 = {5, 10, 15, 20, 30, 35, 40, 45, 55, 60, 70, 80, 90, 95, 105, 110, 115, 120, ...} S3 = {25, 50, 65, 75, 85, 100, ...} S4 = {125, ...}

El patrón parece obvio a primera vista. ¡Pero 65 está en S3! No puede ir en S1 porque (52,39,65), (56,33,65) y (63,16,65) son triples pitagóricos; no puede ir en S2 porque (60,25,65) también lo es. Del mismo modo, (68,51,85) y (75,40,85) son ambos triples.

S4 se forma cuando llegamos a 125; los triples (117,44,125), (120,35,125) y (100,75,125) lo bloquean desde S1, S2 y S3 respectivamente. Como 5^n será la hipotenusa de n triples pitagóricos, con máximos comunes divisores 5^0, 5^1, ..., 5^(n-1), conjeturo que el miembro más pequeño de Sn suele ser 5^(n-1).

En resumen, si la respuesta es 3 (o, sospecho, cualquier número finito), un algoritmo codicioso no lo demostrará.