Common fixed point problem

Last updated

In mathematics, the common fixed point problem is the conjecture that for any two continuous functions which map the unit interval into itself and which commute under functional composition, there must be a point which is a fixed point of both functions. In other words, if the functions and are continuous and for all in the unit interval, then there must be some in the unit interval for which .

Contents

First posed in 1954, the problem remained unsolved for over 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.

History

A 1951 paper by H. D. Block and H. P. Thielman sparked interest in the subject of fixed points of commuting functions. [1] 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. [2]

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 and 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. [3] John R. Isbell also raised the question in a more general form in 1957. [4]

During the 1960s, mathematicians were able to prove that the commuting function conjecture held when certain assumptions were made about and . [1] [5]

In 1963, Ralph DeMarr showed that if and are both Lipschitz continuous, and if the Lipschitz constant of both is , then and 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 and will have a common fixed point if both are continuous and also open. [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 open. [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., implies ). [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]

Boyce's counterexample

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 . It was known that the functions and permute the fixed points of . Baxter and Joichi noted that at each fixed point, the graph of must either cross the diagonal going up (an "up-crossing"), or going down (a "down-crossing"), or 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. [4]

Boyce wrote a computer program to generate permutations that followed Baxter's rules, which he named "Baxter permutations." [1] [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 over 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. [5] It was uncommon in the 1960s for mathematicians to rely on computers for research, [19] [5] 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]

Huneke's counterexample

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 aways 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.[ citation needed ]

Later research

Although the discovery of counterexamples by Boyce and Huneke meant that the decade-long pursuit of a proof of the commuting function conjecture was lost, 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. [1]

Boyce extended the work of Maxfield/Mourant and Chu/Moyer in 1971, proving that under some circumstances, commuting functions can have a common fixed point even if one of the functions has period 2 fixed points. [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 and will have a common fixed point, based on the notions of periodic points and the coindence set of the functions, that is, the values for which . [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]

Related Research Articles

In mathematical analysis, the Weierstrass approximation theorem states that every continuous function defined on a closed interval [a, b] can be uniformly approximated as closely as desired by a polynomial function. Because polynomials are among the simplest functions, and because computers can directly evaluate polynomials, this theorem has both practical and theoretical relevance, especially in polynomial interpolation. The original version of this result was established by Karl Weierstrass in 1885 using the Weierstrass transform.

<span class="mw-page-title-main">Nathan Jacobson</span> American mathematician (1910–1999)

Nathan Jacobson was an American mathematician.

<span class="mw-page-title-main">Irving Kaplansky</span> Canadian mathematician (1917–2006)

Irving Kaplansky was a mathematician, college professor, author, and amateur musician.

In mathematics, the topological entropy of a topological dynamical system is a nonnegative extended real number that is a measure of the complexity of the system. Topological entropy was first introduced in 1965 by Adler, Konheim and McAndrew. Their definition was modelled after the definition of the Kolmogorov–Sinai, or metric entropy. Later, Dinaburg and Rufus Bowen gave a different, weaker definition reminiscent of the Hausdorff dimension. The second definition clarified the meaning of the topological entropy: for a system given by an iterated function, the topological entropy represents the exponential growth rate of the number of distinguishable orbits of the iterates. An important variational principle relates the notions of topological and measure-theoretic entropy.

Nathan Jacob Fine was an American mathematician who worked on basic hypergeometric series. He is best known for his lecture notes on the subject which for four decades served as an inspiration to experts in the field until they were finally published as a book. He solved the Jeep problem in 1946.

In mathematics, the Caristi fixed-point theorem generalizes the Banach fixed-point theorem for maps of a complete metric space into itself. Caristi's fixed-point theorem modifies the -variational principle of Ekeland. The conclusion of Caristi's theorem is equivalent to metric completeness, as proved by Weston (1977). The original result is due to the mathematicians James Caristi and William Arthur Kirk.

<span class="mw-page-title-main">Harry Kesten</span> American mathematician (1931–2019)

Harry Kesten was a Jewish American mathematician best known for his work in probability, most notably on random walks on groups and graphs, random matrices, branching processes, and percolation theory.

<span class="mw-page-title-main">Oscar Lanford</span> American mathematician

Oscar Erasmus Lanford III was an American mathematician working on mathematical physics and dynamical systems theory.

In mathematics, and particularly complex dynamics, the escaping set of an entire function ƒ consists of all points that tend to infinity under the repeated application of ƒ. That is, a complex number belongs to the escaping set if and only if the sequence defined by converges to infinity as gets large. The escaping set of is denoted by .

Isidore Isaac Hirschman Jr. (1922–1990) was an American mathematician, and professor at Washington University in St. Louis working on analysis.

James Dugundji was an American mathematician, a professor of mathematics at the University of Southern California.

In combinatorial mathematics, a Baxter permutation is a permutation which satisfies the following generalized pattern avoidance property:

In mathematics, Kostant's convexity theorem, introduced by Bertram Kostant, can be used to derive Lie-theoretical extensions of the Golden–Thompson inequality and the Schur–Horn theorem for Hermitian matrices.

Jane Smiley Cronin Scanlon was an American mathematician and an emeritus professor of mathematics at Rutgers University. Her research concerned partial differential equations and mathematical biology.

In mathematics, the Poincaré–Miranda theorem is a generalization of intermediate value theorem, from a single function in a single dimension, to n functions in n dimensions. It says as follows:

Roger David Nussbaum is an American mathematician, specializing in nonlinear functional analysis and differential equations.

Stephen M. Gersten is an American mathematician, specializing in finitely presented groups and their geometric properties.

Wallace Smith Martindale III is an American mathematician, known for Martindale's Theorem (1969) and the Martindale ring of quotients introduced in the proof of the theorem. His 1969 paper generalizes Posner's theorem and a theorem of Amitsur and gives an independent, unified proof of the two theorems.

James Allister Jenkins was a Canadian–American mathematician, specializing in complex analysis.

Goodman's conjecture on the coefficients of multivalent functions was proposed in complex analysis in 1948 by Adolph Winkler Goodman, an American mathematician.

References

  1. 1 2 3 4 McDowell, Eric L. (5 August 2009). "Coincidence Values of Commuting Functions" (PDF). Topology Proceedings. 34: 365–384.
  2. ↑ Block, H. D.; Thielman, H. P. (1951). "Commutative polynomials". The Quarterly Journal of Mathematics. 2 (1): 241–243. doi:10.1093/qmath/2.1.241.
  3. ↑ Shields, Allen L. (1964). "On Fixed Points of Commuting Analytical Functions" (PDF). Proceedings of the American Mathematical Society. 15 (5): 703–706. doi:10.1090/S0002-9939-1964-0165508-3.
  4. 1 2 Baxter, Glenn (December 1964). "On Fixed Points of the Composite of Commuting Functions" (PDF). Proceedings of the American Mathematical Society. 15 (6): 851–855. doi:10.1090/S0002-9939-1964-0184217-8.
  5. 1 2 3 Brown, Robert F. (15 January 2021). "A Good Question Won't Go Away: An Example Of Mathematical Research" (PDF). The American Mathematical Monthly. 128 (1). doi:10.1080/00029890.2021.1847592.
  6. ↑ DeMarr, Ralph (1963). "A common fixed point theorem for commuting mappings". The American Mathematical Monthly. 70 (5): 535–537. doi:10.2307/2312067.
  7. ↑ Jungck, Gerald (1966). "Commuting Mappings and Common Fixed Points". The American Mathematical Monthly. 73 (7): 735–738. doi:10.2307/2313982.
  8. ↑ Cohen, Haskell (1964). "On Fixed Points of Commuting Functions" (PDF). Proceedings of the American Mathematical Society. 15 (2): 293–296. doi:10.1090/S0002-9939-1964-0184219-1.
  9. ↑ Folkman, Jon H. (1966). "On functions that commute with full functions" (PDF). Proceedings of the American Mathematical Society. 17 (2): 383–386. doi:10.1090/S0002-9939-1966-0190916-6. ISSN   0002-9939.
  10. ↑ Joichi, James T. (1966). "On functions that commute with full functions and common fixed points". Nieuw. Arch. Wiss. 14: 247–251.
  11. ↑ Maxfield, J.; Mourant, W. (1965). "Common Fixed Points of Commuting Continuous Functions on the Unit Interval" (PDF). Indag. Math. 27: 668–670. doi:10.1016/S1385-7258(65)50068-8.
  12. ↑ Chu, S.; Moyer, R. (1966). "On Continuous Functions, Commuting Functions and Fixed Points" (PDF). Fund. Math. 59: 91–95. doi:10.4064/fm-59-1-91-95.
  13. ↑ "Math Dissertations". Tulane University. Retrieved 15 October 2024.
  14. ↑ Boyce, William M. (March 1969). "Commuting Functions with No Common Fixed Point" (PDF). Transactions of the American Mathematical Society. 137: 77–92. doi:10.1090/S0002-9947-1969-0236331-5.
  15. ↑ Baxter, Glen; Joichi, J. T. (1963). "On Permutations Induced by Commuting Functions, and an Embedding Question". Mathematica Scandinavica. 13 (2): 140–150. ISSN   0025-5521.
  16. ↑ McCroskey, Erin J. (2013). The Common Fixed Point Problem Expanded [Master's thesis]. Tennessee Technological University.
  17. ↑ Mallows, C. L (1979-11-01). "Baxter permutations rise again". Journal of Combinatorial Theory, Series A. 27 (3): 394–396. doi:10.1016/0097-3165(79)90034-7. ISSN   0097-3165.
  18. 1 2 Boyce, William M. (1967). "Generation of a Class of Permutations Associated with Commuting Functions" (PDF). Mathematical Algorithms. 2: 19–26.
  19. ↑ LaSalle, J. P., ed. (1974). The Influence of Computing on Mathematical Research and Education. American Mathematical Society. pp. vii–viii. The computer intelligently used by, as yet, relatively few mathematicians has proved to be an important empirical tool ...
  20. ↑ Huneke, John Philip (1967). On Common Fixed Points of Commuting Continuous Functions on a Closed Interval (PhD thesis). Wesleyan University.
  21. ↑ Huneke, John Philip (1969). "On common fixed points of commuting continuous functions on an interval" (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). "Mountain climbing" (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). "Γ-compact maps on an interval and fixed points" (PDF). Transactions of the American Mathematical Society. 160: 87–102. doi:10.1090/S0002-9947-1971-0280655-1. ISSN   0002-9947.
  24. ↑ Mitchell, Theodore (1972). "Common fixed-points for equicontinuous semigroups of mappings" (PDF). Proceedings of the American Mathematical Society. 33 (1): 146–150. doi:10.1090/S0002-9939-1972-0289735-4. ISSN   0002-9939.
  25. ↑ Cano, J. (1982). "Common fixed points for a class of commuting mappings on an interval" (PDF). Proceedings of the American Mathematical Society. 86 (2): 336–338. doi:10.1090/S0002-9939-1982-0667301-2. ISSN   0002-9939.
  26. ↑ Jachymski, Jacek (1996). "Equivalent conditions involving common fixed points for maps on the unit interval" (PDF). Proceedings of the American Mathematical Society. 124 (10): 3229–3233. doi:10.1090/S0002-9939-96-03397-7. ISSN   0002-9939.
  27. ↑ Jungck, Gerald (1992). "Common fixed points for compatible maps on the unit interval" (PDF). Proceedings of the American Mathematical Society. 115 (2): 495–499. doi:10.1090/S0002-9939-1992-1105040-0. ISSN   0002-9939.
  28. ↑ Chung, F. R. K.; Graham, R. L.; Hoggatt, V. E. Jr.; Kleiman, M. (1978). "The number of Baxter permutations" (PDF). Journal of Combinatorial Theory . Series A. 24 (3): 382–394. doi: 10.1016/0097-3165(78)90068-7 . MR   0491652. Baxter permutations apparently first arose in attempts to prove the "commuting function" conjecture ... However, ... Baxter permutations are of more general significance in analysis than had previously been realized.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.