Particiones consecutivas de números enteros positivos

Question

Fondo (siéntase libre de saltarse esta parte)

Supongamos que queremos $k$ -repartir todos los números enteros positivos hasta (e incluyendo) algún número entero $N$ . Esta partición debería dividir los números en $k$ conjuntos, de tal manera que cada conjunto tiene la misma suma.

Por ejemplo, para $N=4$ hay una posible $2$ -partición: $\{1,4\},\{2,3\}$ (ya que la suma de los números de cada uno es $5$ ). Por otro ejemplo, con $N=7$ hay múltiples posibles 2 partes, una de las cuales es: $\{1,2,4,7\},\{3,5,6\}$ (ya que la suma de los números de cada uno es $14$ ).

Podemos ver que para cualquier $N$ para tener un válido $2$ -partición, necesitamos $ \sum_ {i=1}^N i = \frac {N(N+1)}{2}$ para ser divisible por $2$ que significa $$N(N+1) \text { divisible by 4} \Rightarrow N \text { or } N+1 \text { divisible by 4}$$

No es demasiado difícil determinar requisitos similares en $N$ por la existencia de otros $k$ -particiones: $$k=3: \quad N(N+1) \text { divisible by 6} \Rightarrow N \text { or } N+1 \text { divisible by 3}$$ $$k=4: \quad N(N+1) \text { divisible by 8} \Rightarrow N \text { or } N+1 \text { divisible by 8}$$ $$ \vdots $$

Podría ser interesante investigar ¿cuántos $k$ -que hay para cualquier $N$ pero estoy más interesado en el problema de imponiendo restricciones en los tabiques (lo que hace más difícil encontrar la $N$ para el cual existen).

El problema

Digamos que queremos (lo que he llamado) un consecutivos $k$ -partición. Es decir, dividir los enteros positivos hasta (e incluyendo) $N$ en $k$ conjuntos, de tal manera que cada conjunto tiene la misma suma y los conjuntos están ordenados, siendo el número mayor de cada conjunto 1 menos que el número menor del siguiente conjunto. (Claramente, si existe un $k$ -partición para $N$ sólo hay una de esas particiones.)

En el caso $k=2$ una consecutiva $2$ -existe una división para $N$ si podemos encontrar un $a$ de tal manera que..: $$1+2+ \ldots +a = (a+1)+(a+2)+ \ldots +N$$

Por ejemplo, para $N=3$ hay una posible consecutiva $2$ -partición: $\{1,2\},\{3\}$ . El siguiente $N$ para el cual existe una consecutiva $2$ -La división es $N=20$ donde $a=14$ y lo hemos hecho: $$1+2+ \ldots +14=105=15+16+ \ldots +20$$

En general, un $2$ -existe una división para $N$ si podemos encontrar un $a$ de tal manera que $$ \frac {a(a+1)}{2} = \frac {N(N+1)}{2} - \frac {a(a+1)}{2},$$ que por la fórmula cuadrática significa que necesitamos $$a = \frac { \sqrt {2N^2 + 2N + 1}-1}{2}$$ para ser un entero positivo. Dado que el término raíz siempre será impar, la parte superior siempre será divisible por $2$ así que sólo necesitamos $$a = 2N^2 + 2N + 1$$ para ser un número cuadrado.

Nota interesante: Queremos $a = Z^2$ para algún número entero positivo $Z$ y podemos escribir $a = 2N^2 + 2N + 1 = N^2 + (N+1)^2 = Z^2$ y la ecuación más derecha es precisamente el conjunto de triples pitagóricos $(X, X+1, Z)$ .

Usando esta fórmula, la siguiente $N$ después de $3$ entonces $20$ parece ser $119$ Entonces $696$ Entonces $4059$ Entonces $23660$ . Claramente estos crecen más separados, y una iteración de fuerza bruta sobre todos los números enteros positivos será muy lenta para encontrarlos. ¿Hay una fórmula para encontrar $N$ s por lo que este $a$ existe? O, como una pregunta más teórica: ¿Qué podemos saber sobre el conjunto de estos $N$ s (cómo se distribuyen entre los números enteros positivos)?

Esto se pone más difícil con la consecutiva $3$ -particiones. Para cualquier $N$ tenemos que encontrar un $b$ y $c$ de tal manera que $$ \frac {b(b+1)}{2} = \frac {c(c+1)}{2} - \frac {b(b+1)}{2} = \frac {N(N+1)}{2} - \frac {c(c+1)}{2},$$ lo que significa que necesitamos que los dos siguientes sean números enteros positivos: $$b = \frac { \sqrt {12b^2 + 12b + 9} – 3}{6}$$ $$c = \frac { \sqrt {24b^2 + 24b + 9} - 3}{6}$$ Multiplicando la parte superior e inferior por $ \frac {1}{3}$ y observando que la parte superior siempre será divisible por $2$ Sólo necesitamos $$b = \frac {4}{3}N^2 + \frac {4}{3}N + 1$$ $$c = \frac {8}{3}N^2 + \frac {8}{3}N + 1$$ para ser números cuadrados.

Probé las fórmulas anteriores en la primera $25000$ números enteros positivos, y no he encontrado ningún $N$ s con un consecutivo $3$ -partición. ¿Hay alguna?

Resumen de las preguntas

1. ¿Hay una fórmula para encontrar $N$ s para los cuales un consecutivo $2$ -existe la partición (sin necesidad de iterar y ver si existe un entero $a$ )?
2. ¿Hay alguna $N$ s para los cuales un consecutivo $3$ -¿Existe la partición? ¿Y qué hay de las consecutivas $4$ -particiones, o $5$ etc.?
3. Para cualquier $k$ ¿qué sabemos (sobre la distribución entre los números enteros positivos) del conjunto de $N$ s para los cuales un consecutivo $k$ -¿Existe la partición?

Estoy fascinado por este tema, y cualquier información que pueda proporcionar (tal vez utilizando los conocimientos obtenidos de la teoría de números más avanzada) sería útil!

ACTUALIZACIÓN sobre la pregunta 2

Por consecutivo $3$ -particiones, parece que $N$ que satisfacen las condiciones de $b$ y $c$ puede expresarse mediante fórmulas recursivas: $$ \text {condition on } b \Rightarrow N_{i+2} = 4N_{i+1} - N_i + 1 \text {, with } N_0=0 \text { and } N_1 = 2$$ $$ \text {condition on } c \Rightarrow N'_{i+2} = 10N'_{i+1} - N'_i + 4 \text {, with } N'_0=0 \text { and } N'_1 = 5$$ Una pregunta secundaria: ¿Hay alguna manera de probar esto?

Al iterar $i$ podemos generar $N$ que satisfacen la primera condición, y $N'$ que satisfacen la segunda condición. He hecho esto para generar $N$ y $N'$ todo el camino hasta $10^{300}$ y no hay ninguno que satisfaga ambas condiciones! ¿Esto hace que sea muy probable que no haya ninguna consecutiva $3$ -¿Existen las particiones?

Estas fórmulas recursivas también pueden expresarse en forma cerrada: $$N_i = \frac {1}{4} \left ((1+ \sqrt {3})(2+ \sqrt {3})^i + (1- \sqrt {3})(2- \sqrt {3})^i - 2 \right )$$ $$N'_i = \frac {1}{4} \left ((1+ \frac { \sqrt {6}}{2})(5+2 \sqrt {6})^i + (1- \frac { \sqrt {6}}{2})(5-2 \sqrt {6})^i - 2 \right )$$ Así que la pregunta es: $$\{N_i \mid i \in \mathbb {Z^+}\} \cap \{N'_i \mid i \in \mathbb {Z^+}\} = \emptyset ?$$

Answer 1

[ Editado para incluir la conexión con el teorema de Euler que no hay ningún no-constante $4$ - la progresión aritmética de los cuadrados; brevemente, desde $1$ y $4(N^2+N)+1 = (2N+1)^2$ son siempre cuadrados, $(1,b,c,(2N+1)^2)$ es tal $4$ -progresión a largo plazo, así que $b=c=1$ y $N^2+N=0$ para cualquier racional solución. Parece que el mismo trato con todos $k \geq 3$ . ]

Las ecuaciones de Diophantine $$ B^2 = b = \frac43 (N^2+N) + 1 $$ $$ C^2 = c = \frac83 (N^2+N) + 1 $$ no tienen una solución simultánea en números enteros que no sean los ocho triviales soluciones con $N=0,-1$ , $B = \pm 1$ , $C = \pm 1$ . Tal resultado puede ser difícil de probar en general, pero aquí tenemos algo de suerte en que estos son los únicos racional soluciones, y además $N=0$ y $N=-1$ son los únicos números racionales para los que el producto $bc$ es un cuadrado. Esto se puede probar usando el método de "descenso" de Fermat; los cálculos, aunque elementales, pueden ser algo laboriosos para llevar a cabo a mano, pero felizmente esto ya no es necesario gracias a las tablas y el software existentes.

En general, si $P,Q$ son polinomios cuadráticos tales que $PQ$ tiene cuatro factores distintos, luego las ecuaciones simultáneas de Diophantine $B^2 = P(N)$ , $C^2 = Q(N)$ definir una curva elíptica. Una fundamental 1929 teorema de Siegel asegura que tal curva tiene sólo finamente muchos puntos integrales. La prueba es "ineficaz" y en general no dan un algoritmo garantizado para determinar todas las soluciones. Más tarde Los avances teóricos y computacionales proporcionan tal algoritmo, que es factible al menos para $P,Q$ con pequeños coeficientes; pero la prueba resultante está muy lejos de ser elemental, y puede ser difícil de predecir en un caso dado lo difícil que es dar una prueba elemental.

En el presente caso, sin embargo, la curva elíptica ya tiene finamente muchos puntos racionales, como lo hace la curva "isógena" $A^2 = P(N) Q(N)$ . Traemos esta curva $$ A^2 = \left ( \frac43 (N^2+N) + 1 \right ) \left ( \frac83 (N^2+N) + 1 \right ) $$ en forma de Weierstrass estándar de la forma habitual a partir de la punto racional $(N,A) = (0,1)$ la expansión de Taylor de $A$ sobre $N=0$ comienza $1 + 2N + O(N^2)$ así que para $N \neq 0$ podemos escribir $$ A = 1 + 2N + rN^2 $$ para algunos racionales $r$ y dividir la ecuación resultante por $N^2$ para conseguir $$ (9r^2-32)N^2 + (36r-64)N + (18r-32) = 0. $$ Esta ecuación es cuadrática en $N$ y así tiene raíces racionales iff su discriminante W.R.T. $N$ es un cuadrado. Que los factores discriminantes como $-72(r-2)r(9r-16)$ ; tomando $r=-2x/9$ y eliminando un factor $(8/3)^2$ encontramos que $$ y^2 = x (x+8) (x+9) = x^3 + 17 x^2 + 72 x $$ para algunos racionales $x,y$ . Esta curva elíptica resulta tener director $24$ así que ya aparece en las "Tablas de Amberes" de Tingley de curvas elípticas modulares de conductor a lo sumo $200$ ; resulta que tiene la etiqueta 24C aquí . Encontramos que tiene rango cero, y sólo cuatro puntos racionales, que debe ser el punto en el infinito y los tres " $2$ -puntos de torsión" con $y=0$ . Alternativamente, podemos introducir [0,17,0,72,0] al programa de Cremona mwrank para encontrar que la curva tiene rango cero, y luego encontrar sus puntos de torsión con gp . De cualquier manera, terminamos volviendo sobre nuestros pasos para encontrar que cada uno de $r=0,2,16/9$ corresponde a una de las soluciones conocidas con $N=0$ o $N=-1$ (en cada caso una doble raíz de la cuadrática en $N$ ), así que hemos terminado.

[Gracias a Will Jagy para llamando mi atención a esta pregunta.]

Añadido más tarde : Resulta que este $2$ -cálculo del descenso es muy anterior a las tablas de Amberes: es esencialmente equivalente a La prueba de Euler de su teorema de que no hay un no-constante $4$ - la progresión aritmética de los cuadrados. (Véase por ejemplo Keith La exposición de Conrad que afirma que Euler probó el resultado en 1780, respondiendo a una pregunta "planteada por primera vez por Fermat en 1640"). En efecto, si $b$ y $c$ son cuadrados entonces $$ 1, \ \frac43 (N^2+N)+1, \ \frac83 (N^2+N)+1, \ 4(N^2+N)+1 $$ es tal progresión (el último término es $(2N+1)^2$ , por lo que es constante por Euler, de donde $b=c=1$ y hemos terminado.

jamaicanworm escribe en un comentario que para el general $k \geq 3$ el problema es si existe un entero positivo $N$ de tal manera que $c_i := \frac {4(k-i)}{k}(N^2+N) + 1$ es un cuadrado para cada uno $i=1,2, \ldots ,k-1$ . Estos $c_i$ forman una progresión aritmética, y extenderlo por un término en cada dirección de nuevo da como resultado los cuadrados $c_k = 1$ y $c_0 = (2N+1)^2$ . Por lo tanto, tenemos una progresión aritmética de $k+1$ cuadrados, y de nuevo el teorema de Euler muestra que incluso si permitimos $N$ para ser racional los únicos ejemplos son los triviales con $N^2+N=0$ .

Answer 2

Puedo ayudarte a responder la primera pregunta: Esto tiene algo que ver con las soluciones a La ecuación de Pell . Dejé que la matemática lo resolviera y dio la siguiente solución: $$ \frac {1}{4} \left ( \sqrt {2} \left (3+2 \sqrt {2} \right )^{c_1}- \left (3+2 \sqrt {2} \right )^{c_1}- \sqrt {2} \left (3-2 \sqrt {2} \right )^{c_1}- \left (3-2 \sqrt {2} \right )^{c_1}-2 \right ) $$ donde $c_1$ es un número entero. El sistema de ecuaciones para la pregunta dos no puede ser resuelto por la matemática, pero no veo una prueba simple para eso ahora mismo. Ya sea que se trate o no de un $k$ -existe una partición para un número entero $k$ no es una pregunta fácil, pero tal vez puedas expresar un sistema de ecuaciones para $k$ y demostrar que no puede tener soluciones.

EDITAR El comando que usé fue Solve[2n^2+2n+1==k^2&&n>0&&k>0,{n,k},Integers] . De esta manera, puede resolver este tipo de fórmulas. Un solucionador en línea está disponible aquí . Esto devuelve una relación de recurrencia para generar los valores consecutivos de $n$ dada por la fórmula anterior. Cómo resolver una relación de recurrencia lineal general se puede encontrar aquí .

EDITO 2 Me acabo de dar cuenta de lo siguiente: $3$ -sumas iguales consecutivas sólo pueden ocurrir cuando las dos primeras son iguales, y por lo tanto, el elemento más grande de la suma media tiene que ser un valor de $N$ que proviene de la fórmula de arriba y que satura la $2$ -un criterio de suma consecutiva. Intentaré probar que $k$ -no existen sumas consecutivas para $k \geq 3$ .