Распространенная проблема с фиксированной точкой

Математическая задача, решенная в 1967 году

В математике общая проблема неподвижной точки — это гипотеза о том, что для любых двух непрерывных функций , которые отображают единичный интервал в себя и которые коммутируют при функциональной композиции , должна быть точка, которая является неподвижной точкой обеих функций. Другими словами, если функции и непрерывны и для всех в единичном интервале, то должны быть некоторые в единичном интервале, для которых . ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f(g(x))=g(f(x))}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(x)=x=g(x)}$

Впервые поставленная в 1954 году, проблема оставалась нерешенной более десятилетия, в течение которого несколько математиков постепенно продвигались к утвердительному ответу. В 1967 году Уильям М. Бойс и Джон П. Хунеке независимо друг от друга доказали ложность гипотезы, предоставив примеры коммутирующих функций на замкнутом интервале, не имеющих общей неподвижной точки.

История

Статья 1951 года HD Block и HP Thielman вызвала интерес к теме неподвижных точек коммутирующих функций. ^[1] Основываясь на более ранней работе JF Ritt и AG Walker , Block и Thielman определили наборы попарно коммутирующих многочленов и изучили их свойства. Они доказали для каждого из этих наборов, что любые два многочлена будут иметь общую неподвижную точку. ^[2]

Статья Блока и Тильмана заставила других математиков задуматься, является ли наличие общей неподвижной точки универсальным свойством коммутирующих функций. В 1954 году Элдон Дайер задался вопросом, должны ли они иметь общую неподвижную точку, если и являются двумя непрерывными функциями, отображающими замкнутый интервал на действительной прямой в себя и коммутирующими. Тот же вопрос был поднят независимо Алленом Шилдсом в 1955 году и снова Лестером Дубинсом в 1956 году. ^[3] Джон Р. Исбелл также поднял этот вопрос в более общей форме в 1957 году. ^[4] ${\displaystyle f}$ ${\displaystyle g}$

В 1960-х годах математики смогли доказать, что гипотеза о коммутирующей функции верна, если сделать определенные предположения относительно и . ^{[1] [5]} ${\displaystyle f}$ ${\displaystyle g}$

В 1963 году Ральф ДеМарр показал, что если и оба являются непрерывными по Липшицу , и если константа Липшица обоих равна , то и будут иметь общую неподвижную точку. ^[6] Джеральд Юнг уточнил условия ДеМарра, показав, что они не обязательно должны быть непрерывными по Липшицу, но вместо этого удовлетворяют похожим, но менее ограничивающим критериям. ^[7] ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \geq 1}$ ${\displaystyle f}$ ${\displaystyle g}$

Используя другой подход, Хаскелл Коэн показал в 1964 году, что и будут иметь общую неподвижную точку, если обе они непрерывны и открыты. ^[8] Позднее Джон Х. Фолкман и Джеймс Т. Джоичи, работая независимо, расширили работу Коэна, показав, что необходимо, чтобы только одна из двух функций была открыта. ^{[9] [10]} ${\displaystyle f}$ ${\displaystyle g}$

Джон Максфилд и У. Дж. Мурант в 1965 году доказали, что коммутирующие функции на единичном интервале имеют общую неподвижную точку, если одна из функций не имеет точек периода 2 (т. е. подразумевает ). ^[11] В следующем году Шервуд Чу и Р. Д. Мойер обнаружили, что гипотеза верна, когда существует подынтервал, в котором одна из функций имеет неподвижную точку, а другая не имеет точек периода 2. ^[12] ${\displaystyle f(f(x))=x}$ ${\displaystyle f(x)=x}$

Контрпример Бойса

Уильям М. Бойс получил докторскую степень в Университете Тулейна в 1967 году. ^[13] В своей диссертации Бойс определил пару функций, которые коммутируют относительно композиции, но не имеют общей неподвижной точки, доказав, что гипотеза о неподвижной точке ложна. ^[14]

В 1963 году Гленн Бакстер и Джоичи опубликовали статью о неподвижных точках составной функции . Было известно, что функции и переставляют неподвижные точки . Бакстер и Джоичи отметили, что в каждой неподвижной точке график должен либо пересекать диагональ, идущую вверх («пересечение вверх»), либо идти вниз («пересечение вниз»), либо касаться диагонали, а затем двигаться в противоположном направлении. ^[15] В независимой статье Бакстер доказал, что перестановки должны сохранять тип каждой неподвижной точки (пересечение вверх, пересечение вниз, касание) и что разрешены только определенные упорядочения. ^[4] ${\displaystyle h(x)=f(g(x))=g(f(x))}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle h}$

Бойс написал компьютерную программу для генерации перестановок, которые следовали правилам Бакстера, которые он назвал « перестановками Бакстера ». ^{[1] [16] [17]} Его программа тщательно отсеивала те, которые могли быть тривиально показаны как имеющие неподвижные точки или аналитически эквивалентные другим случаям. После исключения более 97% возможных перестановок с помощью этого процесса ^[18] Бойс построил пары коммутирующих функций из оставшихся кандидатов и смог доказать, что одна такая пара, основанная на перестановке Бакстера с 13 точками пересечения на диагонали, не имела общей неподвижной точки.

Статья Бойса является одним из самых ранних примеров доказательства с помощью компьютера . ^[5] В 1960-х годах математики редко полагались на компьютеры для исследований, ^{[19] [5]} но Бойс, тогда служивший в армии, имел доступ к компьютерам в лаборатории Линкольна Массачусетского технологического института . Бойс опубликовал отдельную статью, описывающую его процесс генерации перестановок Бакстера, включая исходный код программы на FORTRAN . ^[18]

Контрпример Хунеке

Джон П. Хунеке также исследовал проблему общей неподвижной точки для своей докторской диссертации в Уэслианском университете, которую он также получил в 1967 году. В своей диссертации Хунеке приводит два примера пар функций, которые коммутируют, но не имеют общих неподвижных точек, используя две разные стратегии. ^[20] Первый из примеров Хунеке по сути идентичен примеру Бойса, хотя Хунеке пришел к нему с помощью другого процесса. ^[21]

Решение Хунеке основано на задаче о восхождении на гору ^[22] , которая гласит , что два альпиниста, взбираясь на отдельные горы одинаковой высоты, смогут подняться таким образом, что они всегда будут на одной и той же высоте в каждый момент времени. Хунеке использовал этот принцип для построения последовательностей функций, которые будут сходиться к контрпримеру к общей задаче о неподвижной точке.

Работа Хунеке примечательна своим подходом к проблеме, основанным на первых принципах, без опоры на какие-либо работы, проделанные более ранними математиками. ^{[ необходима ссылка ]}

Более поздние исследования

Хотя открытие контрпримеров Бойсом и Хунеке означало, что десятилетние поиски доказательства гипотезы о коммутирующей функции были потеряны, это позволило исследователям сосредоточить свои усилия на изучении того, при каких условиях, в дополнение к уже обнаруженным, гипотеза все еще может оставаться верной. ^[1]

Бойс расширил работу Максфилда/Муранта и Чу/Мойера в 1971 году, доказав, что при некоторых обстоятельствах коммутирующие функции могут иметь общую неподвижную точку, даже если одна из функций имеет неподвижные точки периода 2. ^[23] Его работа была позднее расширена Теодором Митчеллом, Хулио Кано и Яцеком Р. Яхимским. ^{[24] [25] [26]}

Спустя 25 лет после публикации своей первой статьи Юнг определил дополнительные условия, при которых и будут иметь общую неподвижную точку, основываясь на понятиях периодических точек и множестве совпадений функций, то есть значений, для которых . ^[27] ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f(x)=g(x)}$

Перестановки Бакстера стали предметом самостоятельного исследования и применялись к решению других задач, выходящих за рамки общей задачи о неподвижной точке. ^{[ необходима ссылка ]}

Ссылки

1. Макдауэлл, Эрик Л. (5 августа 2009 г.). "Значения совпадений коммутирующих функций" (PDF) . Топологические труды . 34 : 365–384.
2. Блок, HD; Тильман, HP (1951). «Коммутативные многочлены». The Quarterly Journal of Mathematics . 2 (1): 241–243. doi :10.1093/qmath/2.1.241.
3. Шилдс, Аллен Л. (1964). «О неподвижных точках коммутирующих аналитических функций» (PDF) . Труды Американского математического общества . 15 (5): 703–706. doi :10.1090/S0002-9939-1964-0165508-3.
4. Бакстер, Гленн (декабрь 1964 г.). «О неподвижных точках композиции коммутирующих функций» (PDF) . Труды Американского математического общества . 15 (6): 851–855. doi :10.1090/S0002-9939-1964-0184217-8.
5. Браун, Роберт Ф. (15 января 2021 г.). «Хороший вопрос не уйдет: пример математического исследования» (PDF) . The American Mathematical Monthly . 128 (1). doi :10.1080/00029890.2021.1847592.
6. ДеМарр, Ральф (1963). «Общая теорема о неподвижной точке для коммутирующих отображений». The American Mathematical Monthly . 70 (5): 535–537. doi :10.2307/2312067.
7. Юнг, Джеральд (1966). «Коммутирующие отображения и общие неподвижные точки». The American Mathematical Monthly . 73 (7): 735–738. doi :10.2307/2313982.
8. Коэн, Хаскелл (1964). «О неподвижных точках коммутирующих функций» (PDF) . Труды Американского математического общества . 15 (2): 293–296. doi :10.1090/S0002-9939-1964-0184219-1.
9. Фолкман, Джон Х. (1966). «О функциях, которые коммутируют с полными функциями» (PDF) . Труды Американского математического общества . 17 (2): 383–386. doi :10.1090/S0002-9939-1966-0190916-6. ISSN  0002-9939.
10. Joichi, James T. (1966). «О функциях, которые коммутируют с полными функциями и общими неподвижными точками». Nieuw. Arch. Wiss . 14 : 247–251.
11. Максфилд, Дж.; Мурант, У. (1965). «Общие неподвижные точки коммутирующих непрерывных функций на единичном интервале» (PDF) . Indag. Math . 27 : 668–670. doi :10.1016/S1385-7258(65)50068-8.
12. Чу, С.; Мойер, Р. (1966). «О непрерывных функциях, коммутирующих функциях и неподвижных точках» (PDF) . Fund. Math . 59 : 91–95. doi :10.4064/fm-59-1-91-95.
13. "Math Dissertations". Университет Тулейна . Получено 15 октября 2024 г.
14. Бойс, Уильям М. (март 1969). «Коммутирующие функции без общей неподвижной точки» (PDF) . Труды Американского математического общества . 137 : 77–92. doi :10.1090/S0002-9947-1969-0236331-5.
15. Бакстер, Глен; Джоичи, Дж. Т. (1963). «О перестановках, вызванных коммутирующими функциями, и вопросе вложения». Mathematica Scandinavica . 13 (2): 140–150. ISSN  0025-5521.
16. МакКроски, Эрин Дж. (2013). Расширенная общая задача о неподвижной точке [Магистерская диссертация] . Технологический университет Теннесси.
17. Маллоуз, К. Л. (1979-11-01). «Перестановки Бакстера снова растут». Журнал комбинаторной теории, серия A. 27 ( 3): 394–396. doi :10.1016/0097-3165(79)90034-7. ISSN  0097-3165.
18. Boyce, William M. (1967). «Генерация класса перестановок, связанных с коммутирующими функциями» (PDF) . Математические алгоритмы . 2 : 19–26.
19. LaSalle, JP, ed. (1974). Влияние вычислений на математические исследования и образование . Американское математическое общество. стр. vii–viii. Компьютер, разумно используемый пока еще относительно немногими математиками, оказался важным эмпирическим инструментом...
20. Хунеке, Джон Филип (1967). Об общих неподвижных точках коммутирующих непрерывных функций на замкнутом интервале (диссертация на степень доктора философии). Уэслианский университет .
21. Huneke, John Philip (1969). "О общих неподвижных точках коммутирующих непрерывных функций на интервале" (PDF) . Transactions of the American Mathematical Society . 139 (0): 371–381. doi :10.1090/S0002-9947-1969-0237724-2. ISSN  0002-9947.
22. Huneke, John Philip (1969). «Горный подъем» (PDF) . Transactions of the American Mathematical Society . 139 (0): 383–391. doi :10.1090/S0002-9947-1969-0239013-9. ISSN  0002-9947.
23. Boyce, William M. (1971). "Γ-компактные отображения на интервале и неподвижные точки" (PDF) . Transactions of the American Mathematical Society . 160 : 87–102. doi :10.1090/S0002-9947-1971-0280655-1. ISSN  0002-9947.
24. Митчелл, Теодор (1972). "Общие неподвижные точки для равностепенно непрерывных полугрупп отображений" (PDF) . Труды Американского математического общества . 33 (1): 146–150. doi :10.1090/S0002-9939-1972-0289735-4. ISSN  0002-9939.
25. Кано, Дж. (1982). «Общие неподвижные точки для класса коммутирующих отображений на интервале» (PDF) . Труды Американского математического общества . 86 (2): 336–338. doi :10.1090/S0002-9939-1982-0667301-2. ISSN  0002-9939.
26. Яхимский, Яцек (1996). «Эквивалентные условия, включающие общие неподвижные точки для отображений на единичном интервале» (PDF) . Труды Американского математического общества . 124 (10): 3229–3233. doi :10.1090/S0002-9939-96-03397-7. ISSN  0002-9939.
27. Юнгк, Джеральд (1992). «Общие неподвижные точки для совместимых отображений на единичном интервале» (PDF) . Труды Американского математического общества . 115 (2): 495–499. doi :10.1090/S0002-9939-1992-1105040-0. ISSN  0002-9939.