Common fixed point problem
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 and g are continuous, and f(g(x)) = g(f(x)) for all x in the unit interval, then there must be some x in the unit interval for which 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 proved the conjecture to be false by providing examples of commuting functions on a closed interval that do not have a common fixed point.
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 and g are continuous, and f(g(x)) = g(f(x)) for all x in the unit interval, then there must be some x in the unit interval for which 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 proved the conjecture to be false by providing examples of commuting functions on a closed interval that do not have a common fixed point. 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 implies f(x) = x ). 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. 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)) .
It was known that the functions f and g permute the fixed points of h . Baxter and Joichi noted that at each fixed point, the graph of 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. 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.
Boyce wrote a computer program to generate permutations that followed Baxter's rules, which he named "Baxter permutations." His program carefully screened out those that could be trivially shown to have fixed points or were analytically equivalent to other cases.
How it works
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. Boyce's paper is one of the earliest examples of a computer-assisted proof. It was uncommon in the 1960s for mathematicians to rely on computers for research, 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. Over 25 years after the publication of his first paper, Jungck defined additional conditions under which f and 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) .
Evidence and sources
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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370878328 under CC BY-SA 4.0; modifications have been made.