Conjetura de Scholz

En matemáticas , la conjetura de Scholz es una conjetura sobre la longitud de ciertas cadenas de adición . A veces también se la llama conjetura de Scholz-Brauer o conjetura de Brauer-Scholz , en honor a Arnold Scholz , quien la formuló en 1937 ^[1] y Alfred Brauer , quien la estudió poco después y demostró un límite más débil. ^[2]

Neill Clift ha anunciado un ejemplo que demuestra que el límite de la conjetura no siempre es estricto.

Declaración

La conjetura establece que

l (2 norte - 1) \leq norte - 1 + l (norte)

donde $l (n)$ es la longitud de la cadena de adición más corta que produce n . ^[3]

Aquí, una cadena de adición se define como una secuencia de números, comenzando con 1, de modo que cada número después del primero se puede expresar como una suma de dos números anteriores (que pueden ser ambos iguales). Su longitud es el número de sumas necesarias para expresar todos sus números, que es uno menos que la longitud de la secuencia de números (ya que no hay suma de números anteriores para el primer número de la secuencia, 1). Calcular la longitud de la cadena de adición más corta que contiene un número dado $x$ se puede hacer mediante programación dinámica para números pequeños, pero no se sabe si se puede hacer en tiempo polinomial medido como una función de la longitud de la representación binaria de $x$ . La conjetura de Scholz, si es cierta, proporcionaría cadenas de adición cortas para números $x$ de una forma especial, los números de Mersenne .

Ejemplo

A modo de ejemplo, $l (5) = 3$ : tiene la cadena de adición más corta

1, 2, 4, 5

de longitud tres, determinada por las tres sumas

1 + 1 = 2,

2 + 2 = 4,

4 + 1 = 5.

Además, $l (31) = 7$ : tiene una cadena de adición más corta

1, 2, 3, 6, 12, 24, 30, 31

de longitud siete, determinada por las siete sumas

1 + 1 = 2,

2 + 1 = 3,

3 + 3 = 6,

6 + 6 = 12,

12 + 12 = 24,

24 + 6 = 30,

30 + 1 = 31.

Tanto $l (31)$ como $5 - 1 + l (5)$ son iguales a 7. Por lo tanto, estos valores obedecen a la desigualdad (que en este caso es una igualdad) y la conjetura de Scholz es verdadera para el caso $n = 5$ .

Resultados parciales

Mediante una combinación de técnicas de búsqueda por computadora y caracterizaciones matemáticas de cadenas de adición óptimas, Clift (2011) demostró que la conjetura es verdadera para todos $los n < 5784689$ . Además, verificó que para todos $los n \leq 64$ , la desigualdad de la conjetura es en realidad una igualdad. ^[4]

El límite de la conjetura no siempre es una igualdad exacta. Por ejemplo, para , , con . ^[5]^[6] ${\estilo de visualización n=9307543}$ $l(2^{n}-1)\leq 9307570<9307571=n-1+l(n)$ $l(n)=29$

Referencias

^ Scholz, Arnold (1937), "Aufgaben und Lösungen, 253", Jahresbericht der Deutschen Mathematiker-Vereinigung , 47 : 41–42, ISSN 0012-0456
^ Brauer, Alfred (1939), "Sobre cadenas de adición", Boletín de la Sociedad Matemática Americana , 45 (10): 736–739, doi : 10.1090/S0002-9904-1939-07068-7 , ISSN 0002-9904, MR 0000245, Zbl 0022.11106
^ Guy, Richard K. (2004). Problemas no resueltos en teoría de números (3.ª ed.). Springer-Verlag . pp. 169–171. ISBN 978-0-387-20860-2.Zbl 1058.11001 .
^ Clift, Neill Michael (2011). "Cálculo de cadenas de adición óptimas". Computing . 91 (3): 265–284. doi : 10.1007/s00607-010-0118-8 .
^ Clift, Neill (julio de 2024). «Igualdad exacta en la conjetura de Scholz-Brauer» . Consultado el 20 de julio de 2024 .
^ Flammenkamp, Achim (julio de 2024). "Un contraejemplo de que la conjetura de Scholz-Brauer es válida con igualdad para todo n" . Consultado el 20 de julio de 2024 .

Enlaces externos

Cadenas de adición más cortas
Secuencia OEIS A003313