przypuszczenie Scholza
W matematyce hipoteza Scholza jest hipotezą dotyczącą długości pewnych łańcuchów dodawania . Czasami nazywa się to również hipotezą Scholza-Brauera lub hipotezą Brauera-Scholza , na cześć Arnolda Scholza , który sformułował ją w 1937 r., I Alfreda Brauera , który zbadał ją wkrótce potem i udowodnił słabszą granicę.
Oświadczenie
Domniemanie to stwierdza
- l (2 n - 1) ≤ n - 1 + l ( n ) ,
gdzie l ( n ) jest długością najkrótszego łańcucha dodawania dającego n .
Tutaj łańcuch dodawania jest definiowany jako sekwencja liczb rozpoczynająca się od 1, tak że każda liczba po pierwszej może być wyrażona jako suma dwóch wcześniejszych liczb (które mogą być równe). Jego długość to liczba sum potrzebnych do wyrażenia wszystkich jego liczb, czyli o jeden mniej niż długość ciągu liczb (ponieważ nie ma sumy poprzednich liczb dla pierwszej liczby w ciągu, 1). Obliczenie długości najkrótszego łańcucha dodawania zawierającego daną liczbę x można wykonać metodą programowania dynamicznego dla małych liczb, ale nie wiadomo, czy można to zrobić w czasie wielomianowym jako funkcja długości binarnej reprezentacji x . Hipoteza Scholza, jeśli jest prawdziwa, dostarczyłaby krótkich łańcuchów dodawania dla liczb x o specjalnej postaci, liczb Mersenne'a .
Przykład
Na przykład l (5) = 3 : ma najkrótszy łańcuch dodawania
- 1, 2, 4, 5
o długości trzy, określonej przez trzy sumy
- 1 + 1 = 2,
- 2 + 2 = 4,
- 4 + 1 = 5.
Również l (31) = 7 : ma najkrótszy łańcuch dodawania
- 1, 2, 3, 6, 12, 24, 30, 31
o długości siedem, określonej przez siedem sum
- 1 + 1 = 2,
- 2 + 1 = 3,
- 3 + 3 = 6,
- 6 + 6 = 12,
- 12 + 12 = 24,
- 24 + 6 = 30,
- 30 + 1 = 31.
Zarówno l (31), jak i 5 - 1 + l (5) równają się 7. Dlatego wartości te są zgodne z nierównością (która w tym przypadku jest równością), a hipoteza Scholza jest prawdziwa dla przypadku n = 5 .
Wyniki częściowe
Wykorzystując kombinację technik wyszukiwania komputerowego i matematycznej charakterystyki optymalnych łańcuchów dodawania, Clift (2011) wykazał, że przypuszczenie jest prawdziwe dla wszystkich n < 5784689 . Dodatkowo zweryfikował, że dla wszystkich n ≤ 64 nierówność hipotezy jest w rzeczywistości równością.