Siedemnasty problem Hilberta - Hilbert's seventeenth problem

Siedemnasty problem Hilberta jest jednym z 23 problemów Hilberta przedstawionych na słynnej liście sporządzonej w 1900 roku przez Davida Hilberta . Chodzi ekspresję dodatnio określonych funkcji wymiernych jak sum z ilorazów z kwadratów . Pierwotne pytanie można przeformułować jako:

  • Mając wielomian wielowymiarowy, który przyjmuje tylko wartości nieujemne po liczbach rzeczywistych, czy można go przedstawić jako sumę kwadratów funkcji wymiernych?

Pytanie Hilberta można ograniczyć do jednorodnych wielomianów stopnia parzystego, ponieważ wielomian nieparzystego stopnia zmienia znak, a homogenizacja wielomianu przyjmuje tylko wartości nieujemne wtedy i tylko wtedy, gdy to samo dotyczy wielomianu.

Motywacja

Główny artykuł: Wielomian SOS

Sformułowanie pytania uwzględnia, że ​​istnieją nieujemne wielomiany , na przykład

które nie mogą być reprezentowane jako suma kwadratów innych wielomianów . W 1888 Hilbert wykazał, że każdy nieujemny jednorodny wielomian w n zmiennych i stopniu 2 d może być reprezentowany jako suma kwadratów innych wielomianów wtedy i tylko wtedy, gdy (a) n = 2 lub (b) 2 d = 2 lub ( c) n = 3 i 2 d = 4. Dowód Hilberta nie wykazał żadnego wyraźnego kontrprzykładu: dopiero w 1967 roku pierwszy jawny kontrprzykład został skonstruowany przez Motzkina.

W poniższej tabeli podsumowano przypadki, w których wielomian jednorodny (lub wielomian parzystego stopnia) można przedstawić jako sumę kwadratów:

Wielomian jednorodny można przedstawić jako sumę kwadratów? 2 d (stopień) Wielomian parzystego stopnia można przedstawić jako sumę kwadratów? 2 d (stopień)
2 4 ≥6 2 4 ≥6
n (liczba zmiennych) 1 TAk TAk TAk n (liczba zmiennych) 1 TAk TAk TAk
2 TAk TAk TAk 2 TAk TAk Nie
3 TAk TAk Nie 3 TAk Nie Nie
≥4 TAk Nie Nie ≥4 TAk Nie Nie

Rozwiązanie i uogólnienia

Szczególny przypadek n = 2 został już rozwiązany przez Hilberta w 1893 roku. Ogólny problem został rozwiązany twierdząco w 1927 roku przez Emila Artina dla dodatnich półokreślonych funkcji nad liczbami rzeczywistymi lub ogólniej dla ciał rzeczywistych domkniętych . Rozwiązanie algorytmiczne znalazł Charles Delzell w 1984 roku. Wynik Albrechta Pfistera pokazuje, że dodatnia postać półokreślona w n zmiennych może być wyrażona jako suma 2 n kwadratów.

Dubois wykazał w 1967 r., że odpowiedź jest ogólnie negatywna dla pól uporządkowanych . W tym przypadku można powiedzieć, że wielomian dodatni jest sumą ważonych kwadratów funkcji wymiernych o dodatnich współczynnikach.

Uogólnienie na przypadek macierzy (macierze z wielomianowymi wpisami funkcji, które są zawsze dodatnie półokreślone, mogą być wyrażone jako suma kwadratów symetrycznych macierzy z wpisami funkcji wymiernych) podali Gondard, Ribenboim i Procesi, Schacher, z elementarnym dowodem podanym przez Hillara i Nie.

Minimalna liczba kwadratów wyrażeń wymiernych

Pytanie otwarte, jaka jest najmniejsza liczba

tak, że każdy n- zmienny, nieujemny wielomian stopnia d może być zapisany jako suma co najwyżej kwadratowych funkcji wymiernych po liczbach rzeczywistych.

Najbardziej znanym wynikiem (stan na 2008 r.) jest

z powodu Pfistera w 1967 roku.

Z drugiej strony, n- zmienna instancja 3-SAT może być zrealizowana jako problem dodatni na wielomianu z n zmiennymi i d=4 . Dowodzi to, że test dodatni jest NP-Hard . Dokładniej, zakładając, że hipoteza czasu wykładniczego jest prawdziwa, .

W analizie złożonej analog hermitowski, wymagający, aby kwadraty były kwadratami norm odwzorowań holomorficznych, jest nieco bardziej skomplikowany, ale prawdziwy w przypadku wielomianów dodatnich w wyniku Quillena. Z drugiej strony wynik Pfistera zawodzi w przypadku hermitowskim, to znaczy nie ma ograniczenia wymaganej liczby kwadratów, patrz D'Angelo-Lebl.

Zobacz też

Uwagi

Bibliografia