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 f {\displaystyle f} and g {\displaystyle g} are continuous, and f ( g ( x ) ) = g ( f ( x ) ) {\displaystyle f(g(x))=g(f(x))} for all x {\displaystyle x} in the unit interval, then there must be some x {\displaystyle x} in the unit interval for which f ( x ) = x = g ( x ) {\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 f {\displaystyle f} and g {\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 f {\displaystyle f} and g {\displaystyle g} .^[2][1]

In 1963, Ralph DeMarr showed that if f {\displaystyle f} and g {\displaystyle g} are both Lipschitz continuous, and if the Lipschitz constant of both is ≥ 1 {\displaystyle \geq 1} , then f {\displaystyle f} and g {\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 f {\displaystyle f} and g {\displaystyle g} will have a common fixed point if both are continuous and "full", where a continuous function that maps the unit interval into itself is called full if its domain can be split into a finite number of segments, such that for each segment the function restricted to that segment is a homeomorphism onto the unit interval.^[8] Later, both Jon H. Folkman and James T. Joichi, working independently, extended Cohen's work, showing that it is only necessary for one of the two functions to be full.^[9][10]

John Maxfield and W. J. Mourant, in 1965, proved that commuting functions on the unit interval have a common fixed point if one of the functions has no period 2 points (i.e., f ( f ( x ) ) = x {\displaystyle f(f(x))=x} implies f ( x ) = x {\displaystyle f(x)=x} ).^[11] The following year, Sherwood Chu and R. D. Moyer found that the conjecture holds when there is a subinterval in which one of the functions has a fixed point and the other has no period 2 points.^[12]

William M. Boyce earned his Ph.D. from Tulane University in 1967.^[13] In his thesis, Boyce identified a pair of functions that commute under composition, but do not have a common fixed point, proving the fixed point conjecture to be false.^[14]

In 1963, Glenn Baxter and Joichi published a paper about the fixed points of the composite function h ( x ) = f ( g ( x ) ) = g ( f ( x ) ) {\displaystyle h(x)=f(g(x))=g(f(x))} . It was known that the functions f {\displaystyle f} and g {\displaystyle g} permute the fixed points of h {\displaystyle h} . Baxter and Joichi noted that at each fixed point, the graph of h {\displaystyle h} must either cross the diagonal going up (an "up-crossing"), or cross it going down (a "down-crossing"), or not cross it but touch the diagonal and then move away in the opposite direction.^[15] In an independent paper, Baxter proved that the permutations must preserve the type of each fixed point (up-crossing, down-crossing, touching) and that only certain orderings are allowed.^[5]

Boyce wrote a computer program to generate permutations that followed Baxter's rules, which he named "Baxter permutations."^[2][16][17] His program carefully screened out those that could be trivially shown to have fixed points or were analytically equivalent to other cases. After eliminating more than 97% of the possible permutations through this process, Boyce constructed pairs of commuting functions from the remaining candidates and was able to prove that one such pair, based on a Baxter permutation with 13 points of crossing on the diagonal, had no common fixed point.^[18]

Boyce's paper is one of the earliest examples of a computer-assisted proof.^[1] It was uncommon in the 1960s for mathematicians to rely on computers for research,^[1][19] but Boyce, then serving in the Army, had access to computers at MIT Lincoln Laboratory. Boyce published a separate paper describing his process for generating Baxter permutations, including the FORTRAN source code of his program.^[18]

John P. Huneke also investigated the common fixed point problem for his Ph.D. at Wesleyan University, which he also received in 1967. In his thesis, Huneke provides two examples of function pairs that commute but have no common fixed points, using two different strategies.^[20] The first of Huneke's examples is essentially identical to Boyce's, though Huneke arrived at it through a different process.^[21]

Huneke's solution is based on the mountain climbing problem,^[22] which states that two climbers, climbing separate mountains of equal height, will be able to climb in such a way that they will always be at the same elevation at each point in time. Huneke used this principle to construct sequences of functions that will converge to the counterexample to the common fixed point problem.^[20]

Although the discovery of counterexamples by Boyce and Huneke meant that the decade-long pursuit of a proof of the commuting function conjecture was over, it did enable researchers to focus their efforts on investigating under what conditions, in addition to the ones already discovered, the conjecture still might hold true.^[2]

Boyce extended the work of Maxfield/Mourant and Chu/Moyer in 1971, showing weaker conditions that allow both of the commuting functions to have period 2 points but still imply that they must have a common fixed point.^[23] His work was later extended by Theodore Mitchell, Julio Cano, and Jacek R. Jachymski.^[24][25][26]

Over 25 years after the publication of his first paper, Jungck defined additional conditions under which f {\displaystyle f} and g {\displaystyle g} will have a common fixed point, based on the notions of periodic points and the coincidence set of the functions, that is, the values for which f ( x ) = g ( x ) {\displaystyle f(x)=g(x)} .^[27]

Baxter permutations have become a subject of research in their own right and have been applied to other problems beyond the common fixed point problem.^[28]