Fixed point (mathematics)

Last updated December 12, 2024

In mathematics, a fixed point (sometimes shortened to fixpoint), also known as an invariant point, is a value that does not change under a given transformation. Specifically, for functions, a fixed point is an element that is mapped to itself by the function. Any set of fixed points of a transformation is also an invariant set.

Fixed point of a function

Formally, $c$ is a fixed point of a function $f$ if $c$ belongs to both the domain and the codomain of $f$ , and $f (c) = c$ . In particular, $f$ cannot have any fixed point if its domain is disjoint from its codomain. If $f$ is defined on the real numbers, it corresponds, in graphical terms, to a curve in the Euclidean plane, and each fixed-point $c$ corresponds to an intersection of the curve with the line $y = x$ , cf. picture.

For example, if $f$ is defined on the real numbers by $f(x)=x^{2}-3x+4,$ then 2 is a fixed point of $f$ , because $f (2) = 2$ .

Not all functions have fixed points: for example, $f (x) = x + 1$ has no fixed points because $x + 1$ is never equal to $x$ for any real number.

Fixed point iteration

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function. Specifically, given a function $f$ with the same domain and codomain, a point $x_{0}$ in the domain of $f$ , the fixed-point iteration is

$x_{n+1}=f(x_{n}),\,n=0,1,2,\dots$

which gives rise to the sequence $x_{0},x_{1},x_{2},\dots$ of iterated function applications $x_{0},f(x_{0}),f(f(x_{0})),\dots$ which is hoped to converge to a point $x$ . If $f$ is continuous, then one can prove that the obtained $x$ is a fixed point of $f$ .

The notions of attracting fixed points, repelling fixed points, and periodic points are defined with respect to fixed-point iteration.

Fixed-point theorems

A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.^[1]

For example, the Banach fixed-point theorem (1922) gives a general criterion guaranteeing that, if it is satisfied, fixed-point iteration will always converge to a fixed point.

The Brouwer fixed-point theorem (1911) says that any continuous function from the closed unit ball in n-dimensional Euclidean space to itself must have a fixed point, but it doesn't describe how to find the fixed point.

The Lefschetz fixed-point theorem (and the Nielsen fixed-point theorem) from algebraic topology give a way to count fixed points.

Fixed point of a group action

In algebra, for a group G acting on a set X with a group action $\cdot$ , x in X is said to be a fixed point of g if $g\cdot x=x$ .

The fixed-point subgroup $G^{f}$ of an automorphism f of a group G is the subgroup of G: $G^{f}=\{g\in G\mid f(g)=g\}.$

Similarly, the fixed-point subring $R^{f}$ of an automorphism f of a ring R is the subring of the fixed points of f, that is, $R^{f}=\{r\in R\mid f(r)=r\}.$

In Galois theory, the set of the fixed points of a set of field automorphisms is a field called the fixed field of the set of automorphisms.

Topological fixed point property

A topological space $X$ is said to have the fixed point property (FPP) if for any continuous function

f\colon X\to X

there exists $x\in X$ such that $f(x)=x$ .

The FPP is a topological invariant, i.e., it is preserved by any homeomorphism. The FPP is also preserved by any retraction.

According to the Brouwer fixed-point theorem, every compact and convex subset of a Euclidean space has the FPP. Compactness alone does not imply the FPP, and convexity is not even a topological property, so it makes sense to ask how to topologically characterize the FPP. In 1932 Borsuk asked whether compactness together with contractibility could be a necessary and sufficient condition for the FPP to hold. The problem was open for 20 years until the conjecture was disproved by Kinoshita, who found an example of a compact contractible space without the FPP.^[2]

Fixed points of partial orders

In domain theory, the notion and terminology of fixed points is generalized to a partial order. Let ≤ be a partial order over a set X and let f: X → X be a function over X. Then a prefixed point (also spelled pre-fixed point, sometimes shortened to prefixpoint or pre-fixpoint)^{[ citation needed ]} of f is any p such that f(p) ≤ p. Analogously, a postfixed point of f is any p such that p ≤ f(p).^[3] The opposite usage occasionally appears.^[4] Malkis justifies the definition presented here as follows: "since f is before the inequality sign in the term f(x) ≤ x, such x is called a prefix point."^[5] A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in theoretical computer science.^[6]

Least fixed point

In order theory, the least fixed point of a function from a partially ordered set (poset) to itself is the fixed point which is less than each other fixed point, according to the order of the poset. A function need not have a least fixed point, but if it does then the least fixed point is unique.

One way to express the Knaster–Tarski theorem is to say that a monotone function on a complete lattice has a least fixed point that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).^[7]

Fixed-point combinator

In combinatory logic for computer science, a fixed-point combinator is a higher-order function ${\mathsf {fix}}$ that returns a fixed point of its argument function, if one exists. Formally, if the function f has one or more fixed points, then

\operatorname {\mathsf {fix}} f=f(\operatorname {\mathsf {fix}} f).

Fixed-point logics

In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query languages, in particular to Datalog.

Applications

In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. Some examples follow.

In projective geometry, a fixed point of a projectivity has been called a double point.^[8]^[9]
In economics, a Nash equilibrium of a game is a fixed point of the game's best response correspondence. John Nash exploited the Kakutani fixed-point theorem for his seminal paper that won him the Nobel prize in economics.
In physics, more precisely in the theory of phase transitions, linearization near an unstable fixed point has led to Wilson's Nobel prize-winning work inventing the renormalization group, and to the mathematical explanation of the term "critical phenomenon."^[10]^[11]
Programming language compilers use fixed point computations for program analysis, for example in data-flow analysis, which is often required for code optimization. They are also the core concept used by the generic program analysis method abstract interpretation.^[12]
In type theory, the fixed-point combinator allows definition of recursive functions in the untyped lambda calculus.
The vector of PageRank values of all web pages is the fixed point of a linear transformation derived from the World Wide Web's link structure.
The stationary distribution of a Markov chain is the fixed point of the one step transition probability function.
Fixed points are used to finding formulas for iterated functions.

Notes

↑ Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.
↑ Kinoshita, Shin'ichi (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. doi: 10.4064/fm-40-1-96-98 . ISSN 0016-2736.
↑ Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). Proceedings, 18th IEEE Symposium on Foundations of Computer Science. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062.
↑ Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF). Pacific Journal of Mathematics . 82 (1): 43–57. doi:10.2140/pjm.1979.82.43.
↑ Malkis, Alexander (2015). "Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial" (PDF). Reachability Problems. Lecture Notes in Computer Science. 9328: 114–127. doi:10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID 17640585. Archived from the original (PDF) on 2022-08-10.
↑ Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine
↑ Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine
↑ Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.
↑ G. B. Halsted (1906) Synthetic Projective Geometry, page 27
↑ Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture". Physical Review B. 4 (9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi: 10.1103/PhysRevB.4.3174 .
↑ Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior". Physical Review B. 4 (9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi: 10.1103/PhysRevB.4.3184 .
↑ "P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints".

External links

Yutaka Nishiyama (2012). "An Elegant Solution for Drawing a Fixed Point" (PDF). International Journal of Pure and Applied Mathematics. 78 (3): 363–377.

Related Research Articles

Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function $mapping a nonempty compact convex set to itself, there is a point such that . The simplest forms of Brouwer's theorem are for continuous functions from a closed interval in the real numbers to itself or from a closed disk to itself. A more general form than the latter is for continuous functions from a nonempty convex compact subset of Euclidean space to itself.$

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number $is equal to itself (reflexive). If, then (symmetric). If and, then (transitive).$

In mathematics, a group action of a group $G$ on a set $S$ is a group homomorphism from $G$ to some group of functions from $S$ to itself. It is said that $G$ acts on $S$ .

<span class="mw-page-title-main">Homeomorphism</span> Mapping which preserves all topological properties of a given space

In mathematics and more specifically in topology, a homeomorphism, also called topological isomorphism, or bicontinuous function, is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are the mappings that preserve all the topological properties of a given space. Two spaces with a homeomorphism between them are called homeomorphic, and from a topological viewpoint they are the same.

In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points, along with an additional structure called a topology, which can be defined as a set of neighbourhoods for each point that satisfy some axioms formalizing the concept of closeness. There are several equivalent definitions of a topology, the most commonly used of which is the definition through open sets, which is easier than the others to manipulate.

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure". If the transformation is from a metric space to itself, it is a kind of geometric transformation known as a motion.

Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behavior of time averages of various functions along trajectories of dynamical systems. The notion of deterministic dynamical systems assumes that the equations determining the dynamics do not contain any random perturbations, noise, etc. Thus, the statistics with which we are concerned are properties of the dynamics.

In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another. A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry group, and when the function commutes with the action of the group. That is, applying a symmetry transformation and then computing the function produces the same result as computing the function and then applying the transformation.

Complex dynamics, or holomorphic dynamics, is the study of dynamical systems obtained by iterating a complex analytic mapping. This article focuses on the case of algebraic dynamics, where a polynomial or rational function is iterated. In geometric terms, that amounts to iterating a mapping from some algebraic variety to itself. The related theory of arithmetic dynamics studies iteration over the rational numbers or the p-adic numbers instead of the complex numbers.

In mathematics, a fixed-point theorem is a result saying that a function F will have at least one fixed point (a point x for which F(x) = x), under some conditions on F that can be stated in general terms.

In mathematics, an invariant is a property of a mathematical object which remains unchanged after operations or transformations of a certain type are applied to the objects. The particular class of objects and type of transformations are usually indicated by the context in which the term is used. For example, the area of a triangle is an invariant with respect to isometries of the Euclidean plane. The phrases "invariant under" and "invariant to" a transformation are both used. More generally, an invariant with respect to an equivalence relation is a property that is constant on each equivalence class.

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an $-dimensional manifold, or -manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of -dimensional Euclidean space.$

In mathematics, an invariant measure is a measure that is preserved by some function. The function may be a geometric transformation. For examples, circular angle is invariant under rotation, hyperbolic angle is invariant under squeeze mapping, and a difference of slopes is invariant under shear mapping.

A mathematical object X has the fixed-point property if every suitably well-behaved mapping from X to itself has a fixed point. The term is most commonly used to describe topological spaces on which every continuous mapping has a fixed point. But another use is in order theory, where a partially ordered set P is said to have the fixed point property if every increasing function on P has a fixed point.

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

In mathematics, a zonal spherical function or often just spherical function is a function on a locally compact group G with compact subgroup K (often a maximal compact subgroup) that arises as the matrix coefficient of a K-invariant vector in an irreducible representation of G. The key examples are the matrix coefficients of the spherical principal series, the irreducible representations appearing in the decomposition of the unitary representation of G on L²(G/K). In this case the commutant of G is generated by the algebra of biinvariant functions on G with respect to K acting by right convolution. It is commutative if in addition G/K is a symmetric space, for example when G is a connected semisimple Lie group with finite centre and K is a maximal compact subgroup. The matrix coefficients of the spherical principal series describe precisely the spectrum of the corresponding C* algebra generated by the biinvariant functions of compact support, often called a Hecke algebra. The spectrum of the commutative Banach *-algebra of biinvariant L¹ functions is larger; when G is a semisimple Lie group with maximal compact subgroup K, additional characters come from matrix coefficients of the complementary series, obtained by analytic continuation of the spherical principal series.

In mathematics, the Denjoy–Wolff theorem is a theorem in complex analysis and dynamical systems concerning fixed points and iterations of holomorphic mappings of the unit disc in the complex numbers into itself. The result was proved independently in 1926 by the French mathematician Arnaud Denjoy and the Dutch mathematician Julius Wolff.

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:

In algebra, the fixed-point subring $of an automorphism f of a ring R is the subring of the fixed points of f, that is,$

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.

[1] Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6.

[2] Kinoshita, Shin'ichi (1953). "On Some Contractible Continua without Fixed Point Property". Fund. Math. 40 (1): 96–98. doi: 10.4064/fm-40-1-96-98 . ISSN 0016-2736.

[SmythPlotkin1982-3] Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). Proceedings, 18th IEEE Symposium on Foundations of Computer Science. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062.

[CousotCousot1979-4] Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF). Pacific Journal of Mathematics . 82 (1): 43–57. doi:10.2140/pjm.1979.82.43.

[5] Malkis, Alexander (2015). "Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial" (PDF). Reachability Problems. Lecture Notes in Computer Science. 9328: 114–127. doi:10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID 17640585. Archived from the original (PDF) on 2022-08-10.

[6] Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine

[7] Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine

[8] Coxeter, H. S. M. (1942). Non-Euclidean Geometry. University of Toronto Press. p. 36.

[9] G. B. Halsted (1906) Synthetic Projective Geometry, page 27

[10] Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture". Physical Review B. 4 (9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi: 10.1103/PhysRevB.4.3174 .

[11] Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior". Physical Review B. 4 (9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi: 10.1103/PhysRevB.4.3184 .

[12] "P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]