Common fixed point problem

In mathematics, the common fixed point problem is the conjecture that, for any two continuous functions that map the unit interval into itself and commute under functional composition, there must be a point that is a fixed point of both functions. In other words, if the functions ${\displaystyle f}$ and ${\displaystyle g}$ are continuous, and ${\displaystyle f(g(x))=g(f(x))}$ for all ${\displaystyle x}$ in the unit interval, then there must be some ${\displaystyle x}$ in the unit interval for which ${\displaystyle f(x)=x=g(x)}$.

First posed in 1954, the problem remained unsolved for more than a decade, during which several mathematicians made incremental progress toward an affirmative answer. In 1967, William M. Boyce and John P. Huneke independently^[1]:3 proved the conjecture to be false by providing examples of commuting functions on a closed interval that do not have a common fixed point.

A 1951 paper by H. D. Block and H. P. Thielman sparked interest in the subject of fixed points of commuting functions.^[2] Building on earlier work by J. F. Ritt and A. G. Walker, Block and Thielman identified sets of pairwise commuting polynomials and studied their properties. They proved, for each of these sets, that any two polynomials would share a common fixed point.^[3]

Block and Thielman's paper led other mathematicians to wonder if having a common fixed point was a universal property of commuting functions. In 1954, Eldon Dyer asked whether if ${\displaystyle f}$ and ${\displaystyle g}$ are two continuous functions that map a closed interval on the real line into itself and commute, they must have a common fixed point. The same question was raised independently by Allen Shields in 1955 and again by Lester Dubins in 1956.^[4]John R. Isbell also raised the question in a more general form in 1957.^[5]

During the 1960s, mathematicians were able to prove that the commuting function conjecture held when certain assumptions were made about ${\displaystyle f}$ and ${\displaystyle g}$.^[2][1]

In 1963, Ralph DeMarr showed that if ${\displaystyle f}$ and ${\displaystyle g}$ are both Lipschitz continuous, and if the Lipschitz constant of both is ${\displaystyle \geq 1}$, then ${\displaystyle f}$ and ${\displaystyle g}$ will have a common fixed point.^[6] Gerald Jungck refined DeMarr's conditions, showing that they need not be Lipschitz continuous, but instead satisfy similar but less restrictive criteria.^[7]

Taking a different approach, Haskell Cohen showed in 1964 that ${\displaystyle f}$ and ${\displaystyle g}$tendrán un punto fijo común si ambas son continuas y "completas", donde una función continua que mapea el intervalo unitario en sí mismo se llama completa si su dominio se puede dividir en un número finito de segmentos, de modo que para cada segmento la función restringida a ese segmento es un homeomorfismo sobre el intervalo unitario. ^{[ 8 ]} Posteriormente, tanto Jon H. Folkman como James T. Joichi, trabajando independientemente, extendieron el trabajo de Cohen, mostrando que solo es necesario que una de las dos funciones sea completa. ^{[ 9 ] [ 10 ]}

John Maxfield y WJ Mourant, en 1965, demostraron que las funciones conmutativas en el intervalo unitario tienen un punto fijo común si una de las funciones no tiene puntos de período 2 (es decir,${\displaystyle f(f(x))=x}$implica${\displaystyle f(x)=x}$). ^{[ 11 ]} Al año siguiente, Sherwood Chu y RD Moyer descubrieron que la conjetura se cumple cuando hay un subintervalo en el que una de las funciones tiene un punto fijo y la otra no tiene puntos de período 2. ^{[ 12 ]}

William M. Boyce obtuvo su doctorado de la Universidad de Tulane en 1967. ^{[ 13 ]} En su tesis, Boyce identificó un par de funciones que conmutan bajo composición, pero no tienen un punto fijo común, demostrando que la conjetura del punto fijo es falsa. ^{[ 14 ]}

En 1963, Glenn Baxter y Joichi publicaron un artículo sobre los puntos fijos de la función compuesta.${\displaystyle h(x)=f(g(x))=g(f(x))}$Se sabía que las funciones${\displaystyle f}$y${\displaystyle g}$permutar los puntos fijos de${\displaystyle h}$Baxter y Joichi observaron que en cada punto fijo, la gráfica de${\displaystyle h}$debe cruzar la diagonal hacia arriba (un "cruce ascendente"), o cruzarla hacia abajo (un "cruce descendente"), o no cruzarla pero tocar la diagonal y luego alejarse en la dirección opuesta. ^{[ 15 ]} En un artículo independiente, Baxter demostró que las permutaciones deben preservar el tipo de cada punto fijo (cruce ascendente, cruce descendente, contacto) y que solo se permiten ciertos ordenamientos. ^{[ 5 ]}

Boyce escribió un programa informático para generar permutaciones que seguían las reglas de Baxter, al que denominó " permutaciones de Baxter ". ^{[ 2 ] [ 16 ] [ 17 ]} Su programa excluía cuidadosamente aquellas que podían demostrarse fácilmente que tenían puntos fijos o que eran analíticamente equivalentes a otros casos. Tras eliminar más del 97 % de las permutaciones posibles mediante este proceso, Boyce construyó pares de funciones conmutativas a partir de las candidatas restantes y pudo demostrar que uno de esos pares, basado en una permutación de Baxter con 13 puntos de cruce en la diagonal, no tenía ningún punto fijo común. ^{[ 18 ]}

El artículo de Boyce es uno de los primeros ejemplos de una demostración asistida por computadora . ^{[ 1 ]} En la década de 1960, era poco común que los matemáticos recurrieran a las computadoras para la investigación, ^{[ 1 ] [ 19 ]} pero Boyce, que entonces prestaba servicio en el Ejército, tenía acceso a computadoras en el Laboratorio Lincoln del MIT . Boyce publicó un artículo aparte que describía su proceso para generar permutaciones de Baxter, incluyendo el código fuente FORTRAN de su programa. ^{[ 18 ]}

John P. Huneke también investigó el problema del punto fijo común para su doctorado en la Universidad de Wesleyan, que obtuvo en 1967. En su tesis, Huneke proporciona dos ejemplos de pares de funciones que conmutan pero no tienen puntos fijos comunes, utilizando dos estrategias diferentes. ^{[ 20 ]} El primero de los ejemplos de Huneke es esencialmente idéntico al de Boyce, aunque Huneke llegó a él mediante un proceso diferente. ^{[ 21 ]}

La solución de Huneke se basa en el problema de la escalada de montañas ^{[ 22 ]} , que establece que dos escaladores, ascendiendo montañas separadas de igual altura, podrán hacerlo de tal manera que siempre se encuentren a la misma elevación en cada instante. Huneke utilizó este principio para construir secuencias de funciones que convergen al contraejemplo del problema del punto fijo común ^{[ 20 ] .}

Aunque el descubrimiento de contraejemplos por parte de Boyce y Huneke significó el fin de la búsqueda de una demostración de la conjetura de la función conmutativa, que duró una década, permitió a los investigadores centrar sus esfuerzos en investigar bajo qué condiciones, además de las ya descubiertas, la conjetura aún podría ser cierta. ^{[ 2 ]}

En 1971, Boyce extendió el trabajo de Maxfield/Mourant y Chu/Moyer, demostrando condiciones más débiles que permiten que ambas funciones conmutativas tengan puntos de periodo 2, pero que aún implican que deben tener un punto fijo común. ^{[ 23 ]} Su trabajo fue extendido posteriormente por Theodore Mitchell, Julio Cano y Jacek R. Jachymski. ^{[ 24 ] [ 25 ] [ 26 ]}

Más de 25 años después de la publicación de su primer artículo, Jungck definió condiciones adicionales bajo las cuales${\displaystyle f}$y${\displaystyle g}$tendrán un punto fijo común, basado en las nociones de puntos periódicos y el conjunto de coincidencias de las funciones, es decir, los valores para los cuales${\displaystyle f(x)=g(x)}$. ^{[ 27 ]}

Las permutaciones de Baxter se han convertido en un tema de investigación por derecho propio y se han aplicado a otros problemas más allá del problema común del punto fijo. ^{[ 28 ]}