Conjecture de Scholz

En mathématiques, la conjecture de Scholz, parfois appelée conjecture de Scholz-Brauer ou conjecture de Brauer-Scholz, fut proposée en 1937. Elle prétend que

$l \left( 2^n - 1 \right) \le n - 1 + l \left( n \right)$

où l(n) est la longueur de la plus courte chaîne d'additions (en) qui produit n, c'est-à-dire le plus petit entier m pour lequel il existe une suite $(v_0,\ldots,v_m)$ telle que v₀ = 1, v_m = n, et chaque v_i est de la forme v_j + v_k avec j,k < i.

Elle a été démontrée dans de nombreux cas, mais pas dans le cas général.

Par exemple pour n = 5 on a égalité, car l(5)=3 (puisque 1+1=2, 2+2=4, 4+1=5 et il n'existe pas de chaîne plus courte), l(31)=7 (1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+6=30, 30+1=31), et

$l \left( 2^5 - 1 \right) = 5 - 1 + l \left( 5 \right)$.

Des considérations élémentaires sur la nature des chaînes d'additions et le codage binaire permettent d'établir l'inégalité suivante, plus faible (en) :

$l \left( 2^n - 1 \right) \le 2 (n - 1)$,

mais une preuve qui permettrait de remplacer par l(n) l'un des deux « n − 1 » du majorant n'a pas encore été trouvée.

Liens externes

• (en) Shortest Addition Chains par Achim Flammenkamp, à l'université de Bielefeld
• (en) Suite A003313 de l'OEIS

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Scholz conjecture » (voir la liste des auteurs)
• (de) Arnold Scholz (de), « Aufgabe 252 », dans Jahresber. Deutsche Math. Vereinigung, vol. 47 « Aufgaben und Lösungen », 1937, p. 41-42 [texte intégral] 
• (en) Alfred Brauer, « On addition chains », dans Bull. Amer. Math. Soc., vol. 45, 1939, p. 736-739 [texte intégral]