🔢 mathematics

Subsequence Sums in Permutations

Este artículo establece que para $n$ suficientemente grande, toda permutación de $\{1, 2, \ldots, n\}$ contiene una subsucesión 2-aditiva de cualquier longitud fija $k \geq 3$ , proporciona cotas polinómicas para el $n$ requerido, determina el umbral exacto de $n=18$ para subsucesiones 2-aditivas monótonas de longitud tres, y extiende estos resultados a productos y sumas inversas utilizando técnicas de la teoría de Ramsey aritmética.

Autores originales: Collier Gaiser, Paul Horn

Publicado 2026-05-29

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Collier Gaiser, Paul Horn

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes una baraja de cartas numeradas del 1 al $n$ , barajadas en un orden completamente aleatorio. Esta baraja barajada es lo que los matemáticos llaman una permutación.

Durante mucho tiempo, los matemáticos han planteado una pregunta específica sobre estas barajas barajadas: Sin importar cómo las barajes, si la baraja es lo suficientemente grande, ¿siempre podrás encontrar un pequeño grupo de cartas ocultas dentro que sigan una regla matemática especial?

Este artículo, escrito por Collier Gaiser y Paul Horn, dice "Sí", pero con un giro. Han encontrado un nuevo tipo de regla que siempre aparece en barajas lo suficientemente grandes, y han calculado exactamente qué tan grande debe ser la baraja para garantizar que esto suceda.

Aquí está el desglose de su descubrimiento utilizando analogías simples:

1. La Regla del "Duplica Tu Dinero"

Los autores buscan un patrón específico que llaman subsucesión 2-aditiva.

Piénsalo como un truco de magia con tres números: $A, B, C$ .

Si los sumas todos ( $A + B + C$ ), el total debe ser exactamente el doble del primer número ( $2 \times A$ ) O el doble del último número ( $2 \times C$ ).

El Gran Descubrimiento:
El artículo demuestra que si tienes una baraja de cartas que es "suficientemente grande" (el tamaño exacto depende de cuántas cartas quieres en tu grupo), estás garantizado de encontrar un grupo de $k$ cartas que sigue esta regla.

La Trampa: Las cartas no tienen que estar una al lado de la otra en la baraja. Solo tienen que aparecer en el orden correcto de izquierda a derecha.
El Resultado: Para cualquier tamaño de grupo $k$ (siempre que $k \ge 3$ ), existe un "número mágico" $n$ . Si tu baraja tiene más de $n$ cartas, no puedes barajarlas de una manera que evite este patrón. Es inevitable.

2. ¿Qué Tan Grande Necesita Ser la Baraja?

Los autores no solo dijeron "es grande"; calcularon los límites.

La Cota Superior: Demostraron que si tu baraja es aproximadamente proporcional a $k^5$ (un tamaño polinómico), estás garantizado de encontrar el patrón.
La Cota Inferior: También mostraron que si la baraja es demasiado pequeña (específicamente más pequeña que cierta fórmula), en realidad puedes barajarla para evitar el patrón.

Un Ejemplo Específico (El "Número Mágico" 18):
El artículo se centra en el grupo más pequeño posible: un grupo de tres cartas ( $k=3$ ).

Se preguntaron: "¿Cuál es el tamaño de baraja más pequeño donde estás forzado a encontrar tres cartas donde la suma es el doble del primero o el doble del último?"
La Respuesta: 18.
Si tienes una baraja de 17 cartas, puedes barajarlas de una manera muy específica y truculenta para evitar este patrón.
Pero en el momento en que agregas la carta número 18, sin importar cómo las barajes, inevitablemente encontrarás tres cartas que encajan en la regla.
Analogía: Imagina intentar organizar a 17 personas en una fila para que ninguna de ellas satisfaga una regla específica de suma de alturas. Puedes hacerlo. Pero si agregas a una 18ª persona, se vuelve matemáticamente imposible organizarlas sin crear ese trío específico.

3. El Giro "Monótono"

Los autores también examinaron una versión más estricta del juego. ¿Qué pasa si las tres cartas que encuentras también deben ser monótonas?

Monótono significa que están estrictamente subiendo (como 2, 5, 8) o estrictamente bajando (como 9, 4, 1).
Demostraron que incluso con esta regla más estricta, el número mágico sigue siendo 18. Si tienes 18 cartas, no puedes evitar encontrar tres cartas que estén tanto en el orden correcto como que sigan la regla de "suma doble".

4. Multiplicación y Sumas Inversas

El artículo no se detiene en la suma. Los autores utilizaron sus hallazgos para mostrar que reglas similares se aplican a otras operaciones matemáticas:

Multiplicación: Si buscas un grupo donde el producto de los números sea igual al cuadrado del primero o del último número, se aplica la misma lógica. Si la baraja es lo suficientemente grande, este patrón es inevitable.
Sumas Inversas: También examinaron la suma de fracciones (como $1/A + 1/B + 1/C$ ). Demostraron que si la baraja es lo suficientemente grande, encontrarás un grupo donde la suma de las fracciones sea igual al doble de la primera o la última fracción.

5. Por Qué Esto Importa (En Términos Matemáticos)

Antes de este artículo, los matemáticos sabían que podías barajar una baraja para evitar progresiones aritméticas (como 2, 4, 6 o 5, 10, 15). Puedes ocultar esos patrones.

Sin embargo, este artículo muestra que, aunque puedes ocultar las progresiones aritméticas, no puedes ocultar estos patrones "2-aditivos". Es como decir: "Puedes ocultar una línea recta en un montón desordenado de arena, pero no puedes ocultar una forma de triángulo específica".

Resumen

El Problema: ¿Puedes barajar una baraja de números para que ningún grupo pequeño siga una regla matemática específica?
La Respuesta: No. Si la baraja es lo suficientemente grande, la regla es inevitable.
La Regla: La suma del grupo es igual al doble del primer o último número.
El Umbral: Para un grupo de 3, necesitas al menos 18 números para garantizar que aparezca la regla.
La Extensión: Esta lógica también funciona para la multiplicación y las fracciones.

El artículo proporciona la "red de seguridad" matemática que demuestra que estos patrones son inevitables en colecciones lo suficientemente grandes de números, sin importar cuán caótica parezca la disposición.

Resumen Técnico: Sumas de Subsecuencias en Permutaciones

Enunciado del Problema
Este artículo investiga la existencia de subsecuencias aritméticas específicas dentro de permutaciones del conjunto $\{1, 2, \dots, n\}$ . Mientras que la teoría de Ramsey aritmética clásica (por ejemplo, el teorema de van der Waerden) garantiza progresiones aritméticas monocromáticas en conjuntos coloreados suficientemente grandes, Entringer y Jackson (1973) demostraron que las permutaciones pueden evitar progresiones aritméticas monótonas de 3 términos (3-AP). Los autores preguntan si otras propiedades aritméticas, específicamente subsecuencias "aditivas", son inevitables en permutaciones grandes.

Una secuencia de enteros positivos $(a_1, a_2, \dots, a_k)$ se define como $\ell$ -aditiva si la suma de sus términos satisface $\sum_{i=1}^k a_i = \ell a_1$ o $\sum_{i=1}^k a_i = \ell a_k$ . El enfoque principal está en las subsecuencias 2-aditivas (donde la suma es igual al doble del primer o último término) y sus variantes monótonas. El artículo aborda dos preguntas principales:

Para una longitud fija $k \ge 3$ , ¿existe un $n$ tal que toda permutación de $\{1, \dots, n\}$ contenga una subsecuencia 2-aditiva de longitud $k$ ?
¿Cuáles son los umbrales y cotas precisos para la existencia de tales subsecuencias, particularmente cuando se restringen a secuencias monótonas?

Metodología
Los autores emplean una combinación de argumentos combinatorios, análisis de casos y técnicas de la teoría de Ramsey aritmética.

Construcción Combinatoria y Contradicción: Las pruebas centrales para la existencia (Teoremas 1.1 y 1.3) se basan en construir subconjuntos específicos de permutaciones y utilizar la demostración por contradicción. Al analizar las posiciones relativas de los elementos (usando $L_p(s)$ y $R_p(s)$ para denotar elementos a la izquierda y a la derecha de $s$ en una permutación $p$ ), los autores demuestran que evitar una subsecuencia 2-aditiva fuerza una contradicción estructural en la disposición de la permutación.
Técnicas de Acotación: Para establecer cotas superiores para el menor $n$ (denotado $f(k, 2)$ ), los autores definen un conjunto de sumas "peligrosas" derivadas de los primeros $2k-1$ elementos de una permutación. Utilizan el mínimo común múltiplo (MCM) de estas sumas para determinar un umbral $N_k$ más allá del cual se fuerza una subsecuencia 2-aditiva.
Cotas Inferiores y Contraejemplos: Las cotas inferiores se establecen construyendo explícitamente permutaciones de tamaño $n-1$ que carecen de las subsecuencias deseadas.
Análisis Asintótico: El artículo utiliza el Teorema de los Números Primos (a través de los resultados de Rosser) para derivar cotas inferiores sobre el número de tales subsecuencias en permutaciones grandes.
Argumentos de Transformación: Para extender los resultados a productos y sumas inversas, los autores utilizan transformaciones estándar que mapean propiedades aditivas en $\{1, \dots, n\}$ a propiedades multiplicativas en $\{2^1, \dots, 2^n\}$ y propiedades inverso-aditivas en $\{L_n/1, \dots, L_n/n\}$ (donde $L_n$ es el MCM de 1 a $n$ ).

Contribuciones y Resultados Clave

Existencia de Subsecuencias 2-Aditivas (Teorema 1.1):
Para cualquier $k \ge 3$ fijo, si $n$ es suficientemente grande, toda permutación de $\{1, \dots, n\}$ contiene una subsecuencia 2-aditiva de longitud $k$ .
- Cotas: El artículo proporciona cotas polinómicas para el menor $n$ $n$ tal, denotado $f(k, 2)$ $f (k, 2)$ .
  - Cota inferior: $f(k, 2) \ge (k-1)(3k-4)/2$ .
  - Cota superior: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$ .
- Valor Exacto para $k=3$ : Los autores prueban que $f(3, 2) = 5$ . Toda permutación de $\{1, \dots, 5\}$ contiene una subsecuencia 2-aditiva de longitud 3, mientras que existe un contraejemplo para $n=4$ .
Subsecuencias 2-Aditivas Monótonas (Teorema 1.3):
El artículo aborda la condición más estricta donde la subsecuencia debe ser monótona.
- Resultado: Si $n \ge 18$ , toda permutación de $\{1, \dots, n\}$ contiene una subsecuencia 2-aditiva monótona de longitud 3.
- Optimalidad: El valor 18 es óptimo; se construye una permutación específica de $\{1, \dots, 17\}$ que evita tales subsecuencias.
- Pregunta Abierta: Se desconoce si esto se cumple para subsecuencias 2-aditivas monótonas de longitud $k \ge 4$ .
Subsecuencias $\ell$ -Aditivas Generales:
- Si $k = \ell$ , la permutación identidad $(1, 2, \dots, n)$ no contiene ninguna subsecuencia $\ell$ -aditiva de longitud $k$ .
- El artículo resuelve dos casos mixtos específicos:
  - $f(4, 3) = 8$ (Toda permutación de 8 elementos tiene una subsecuencia 3-aditiva de longitud 4).
  - $f(3, 4) = 13$ (Toda permutación de 13 elementos tiene una subsecuencia 4-aditiva de longitud 3).
- El caso general para $k \neq \ell$ con $k, \ell \ge 4$ queda como una pregunta abierta.
Conteo de Subsecuencias:
Los autores proporcionan cotas sobre el número mínimo de subsecuencias $\ell$ -aditivas de longitud $k$ en cualquier permutación de tamaño $n$ :
- Cota Superior: $O(n^{k-1})$ .
- Cota Inferior: $\Omega(n / \log n)$ (asumiendo que $f(k, \ell)$ existe), derivada utilizando argumentos de distribución de números primos.
- Se dan cotas específicas para subsecuencias 2-aditivas monótonas de longitud 3 como $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ .
Extensiones a Productos y Sumas Inversas:
Utilizando transformaciones de la teoría de Ramsey aritmética, el artículo extiende los resultados aditivos a:
- Multiplicativo: Toda permutación lo suficientemente grande tiene una subsecuencia donde el producto es el cuadrado del primer o último término (2-multiplicativa).
- Inverso-Aditivo: Toda permutación lo suficientemente grande tiene una subsecuencia donde la suma de los recíprocos es el doble del recíproco del primer o último término.
- El artículo señala que para subsecuencias 2-multiplicativas monótonas de longitud 3, el umbral es como máximo 32 (y exactamente 32, ya que existe un contraejemplo para $n=31$ ).

Significado y Afirmaciones
El artículo afirma establecer los primeros resultados de tipo Schur-Rado específicamente para permutaciones, demostrando que, aunque las permutaciones pueden evitar progresiones aritméticas monótonas (3-AP), no pueden evitar subsecuencias 2-aditivas de longitud arbitraria. El trabajo proporciona las primeras cotas polinómicas para la existencia de estas estructuras y determina umbrales exactos para casos pequeños ( $k=3$ ).

Los autores enmarcan modestamente su contribución como una base para estudios futuros. Destacan que el caso general para $k \neq \ell$ permanece abierto y que el comportamiento de las subsecuencias 2-aditivas monótonas para longitudes $k > 3$ es desconocido. El artículo posiciona estos hallazgos como un paso hacia la comprensión de la interacción entre la estructura de las permutaciones y las propiedades aritméticas, sugiriendo direcciones futuras en sumas de subsecuencias ponderadas y el refinamiento de umbrales para variantes multiplicativas e inverso-aditivas.