Семнадцатая проблема Гильберта

Выражение многочленов в виде суммы квадратов

Семнадцатая проблема Гильберта — одна из 23 проблем Гильберта, изложенных в знаменитом списке, составленном в 1900 году Дэвидом Гильбертом . Она касается выражения положительно определенных рациональных функций в виде сумм частных квадратов . Исходный вопрос можно переформулировать так:

• Если задан многомерный полином, принимающий только неотрицательные значения среди действительных чисел, можно ли его представить в виде суммы квадратов рациональных функций?

Вопрос Гильберта можно ограничить однородными многочленами четной степени, поскольку многочлен нечетной степени меняет знак, а гомогенизация многочлена принимает только неотрицательные значения тогда и только тогда, когда то же самое верно для самого многочлена.

Мотивация

Формулировка вопроса учитывает, что существуют неотрицательные многочлены , например ^[1]

${\displaystyle f(x,y,z)=z^{6}+x^{4}y^{2}+x^{2}y^{4}-3x^{2}y^{2}z^{2},}$

который не может быть представлен в виде суммы квадратов других многочленов . В 1888 году Гильберт показал, что любой неотрицательный однородный многочлен от n переменных и степени 2 d может быть представлен в виде суммы квадратов других многочленов тогда и только тогда, когда либо (a) n = 2, либо (b) 2 d = 2, либо (c) n = 3 и 2 d = 4. ^[2] Доказательство Гильберта не содержало явного контрпримера: только в 1967 году первый явный контрпример был построен Моцкиным . [ ^3] Более того, если многочлен имеет степень 2 d больше двух, существует значительно больше неотрицательных многочленов, которые не могут быть выражены в виде суммы квадратов. ^[4]

В следующей таблице приведены случаи, в которых каждый неотрицательный однородный многочлен (или многочлен четной степени) может быть представлен в виде суммы квадратов:

Решение и обобщения

Частный случай n = 2 уже был решен Гильбертом в 1893 году. ^[5] Общая проблема была решена утвердительно в 1927 году Эмилем Артином ^[6] для положительно полуопределенных функций над вещественными числами или, в более общем случае, вещественно-замкнутыми полями . Алгоритмическое решение было найдено Чарльзом Делцеллом в 1984 году. ^[7] Результат Альбрехта Пфистера ^[8] показывает, что положительно полуопределенная форма от n переменных может быть выражена как сумма 2 ⁿ квадратов. ^[9]

Дюбуа показал в 1967 году, что ответ в общем случае отрицателен для упорядоченных полей . ^[10] В этом случае можно сказать, что положительный многочлен является суммой взвешенных квадратов рациональных функций с положительными коэффициентами. ^[11] Маккенна показал в 1975 году, что все положительные полуопределенные многочлены с коэффициентами в упорядоченном поле являются суммами взвешенных квадратов рациональных функций с положительными коэффициентами, только если поле плотно в своем действительном замыкании в том смысле, что любой интервал с конечными точками в действительном замыкании содержит элементы из исходного поля. ^[12]

Обобщение на матричный случай (матрицы с элементами полиномиальной функции, которые всегда являются положительно полуопределенными, могут быть выражены как сумма квадратов симметричных матриц с элементами рациональной функции) было дано Гондаром, Рибенбоймом ^[13] и Прочези, Шахером ^[14] с элементарным доказательством, данным Хилларом и Ни. ^[15]

Минимальное количество квадратных рациональных членов

Это открытый вопрос, какое наименьшее число

${\displaystyle v(n,d),}$

так что любой n -мерный, неотрицательный многочлен степени d может быть записан как сумма не более чем квадратичных рациональных функций по действительным числам. Верхняя граница , полученная Пфистером в 1967 году, такова: ^[8] ${\displaystyle v(n,d)}$

${\displaystyle v(n,d)\leq 2^{n},}$

В другом направлении условная нижняя граница может быть получена из теории вычислительной сложности . n- переменный экземпляр 3-SAT может быть реализован как задача положительности для полинома с n переменными и d=4 . Это доказывает, что проверка положительности является NP-Hard . Точнее, предполагая, что гипотеза экспоненциального времени верна, . ${\displaystyle v(n,d)=2^{\Omega (n)}}$

В комплексном анализе эрмитов аналог, требующий, чтобы квадраты были квадратами норм голоморфных отображений, несколько сложнее, но верен для положительных многочленов по результату Квиллена. ^[16] С другой стороны, результат Пфистера неверен в эрмитовом случае, то есть нет ограничения на количество требуемых квадратов, см. D'Angelo–Lebl. ^[17]

Смотрите также

• Полиномиальный SOS
• Положительный многочлен
• Оптимизация по сумме квадратов
• SOS-выпуклость

Примечания

1. Мари-Франсуаза Руа . Роль проблем Гильберта в реальной алгебраической геометрии. Труды девятого собрания EWM, Локум, Германия, 1999 г.
2. Гильберт, Дэвид (сентябрь 1888 г.). «Ueber die Darstellung definer Formen als Summe von Formenquadraten». Математические Аннален . 32 (3): 342–350. дои : 10.1007/bf01443605. S2CID  177804714.
3. Моцкин, ТС (1967). «Арифметико-геометрическое неравенство». В Шиша, Овед (ред.). Неравенства . Academic Press. С. 205–224.
4. Блехерман, Григорий (2006). «Неотрицательных многочленов значительно больше, чем сумм квадратов». Israel Journal of Mathematics . 153 (1): 355–380. doi : 10.1007/BF02771790 . ISSN  0021-2172.
5. Гильберт, Дэвид (декабрь 1893 г.). «Über ternäre определенные формы». Акта Математика . 17 (1): 169–197. дои : 10.1007/bf02391990 .
6. Артин, Эмиль (1927). «Über die Zerlegung definer Funktionen in Quadrate». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 5 (1): 100–115. дои : 10.1007/BF02952513. S2CID  122607428.
7. Делзелл, Китай (1984). «Непрерывное конструктивное решение 17-й проблемы Гильберта». Математические изобретения . 76 (3): 365–384. Бибкод : 1984InMat..76..365D. дои : 10.1007/BF01388465. S2CID  120884276. Збл  0547.12017.
8. Пфистер, Альбрехт (1967). «Zur Darstellung definer Funktionen als Summe von Quadraten». Inventiones Mathematicae (на немецком языке). 4 (4): 229–237. Бибкод : 1967InMat...4..229P. дои : 10.1007/bf01425382. S2CID  122180608. Збл  0222.10022.
9. Лэм (2005) стр.391
10. Дюбуа, Д. В. (1967). «Заметка о решении Артином 17-й проблемы Гильберта». Bull. Am. Math. Soc . 73 (4): 540–541. doi : 10.1090/s0002-9904-1967-11736-1 . Zbl  0164.04502.
11. Лоренц (2008) стр.16
12. Маккенна, К. (1975). Новые факты о семнадцатой проблеме Гильберта . Теория моделей и алгебра, заметки лекций по математике. Т. 498. Springer, Берлин, Гейдельберг. С. 220–230.
13. Гондар, Даниэль; Рибенбойм, Пауло (1974). «17-я проблема Гильберта для матриц». Бык. наук. Математика. (2) . 98 (1): 49–56. МР  0432613. Збл  0298.12104.
14. Процессеси, Клаудио; Шехер, Мюррей (1976). «Некоммутативный действительный Nullstellensatz и 17-я проблема Гильберта». Энн. математики . 2. 104 (3): 395–406. дои : 10.2307/1970962. JSTOR  1970962. МР  0432612. Збл  0347.16010.
15. Хиллар, Кристофер Дж.; Ни, Цзяванг (2008). «Элементарное и конструктивное решение 17-й проблемы Гильберта для матриц». Proc. Am. Math. Soc . 136 (1): 73–76. arXiv : math/0610388 . doi :10.1090/s0002-9939-07-09068-5. S2CID  119639574. Zbl  1126.12001.
16. Quillen, Daniel G. (1968). «О представлении эрмитовых форм в виде сумм квадратов». Invent. Math . 5 (4): 237–242. Bibcode :1968InMat...5..237Q. doi :10.1007/bf01389773. S2CID  119774934. Zbl  0198.35205.
17. D'Angelo, John P.; Lebl, Jiri (2012). «Теорема Пфистера не работает в эрмитовом случае». Proc. Am. Math. Soc . 140 (4): 1151–1157. arXiv : 1010.3215 . doi :10.1090/s0002-9939-2011-10841-4. S2CID  92993604. Zbl  1309.12001.

Ссылки

• Пфистер, Альбрехт (1976). «Семнадцатая проблема Гильберта и связанные с ней проблемы определенных форм». В Феликсе Э. Браудере (ред.). Математические разработки, возникающие из проблем Гильберта . Труды симпозиумов по чистой математике . Том XXVIII.2. Американское математическое общество . стр. 483–489. ISBN 0-8218-1428-1.
• Лам, Цит-Юэн (2005). Введение в квадратичные формы над полями . Аспирантура по математике . Том 67. Американское математическое общество. ISBN 0-8218-1095-2. Збл  1068.11023.
• Лоренц, Фалько (2008). Алгебра. Том II: Поля со структурой, алгебры и дополнительные темы . Springer-Verlag . стр. 15–27. ISBN 978-0-387-72487-4. Збл  1130.12001.
• Раджваде, AR (1993). Квадраты . Серия заметок к лекциям Лондонского математического общества. Том 171. Cambridge University Press . ISBN 0-521-42668-5. Збл  0785.11022.