@ Appl. Gen. Topol. 21, no. 1 (2020), 87-110 doi:10.4995/agt.2020.12091 c© AGT, UPV, 2020 Fixed point sets in digital topology, 1 Laurence Boxer a and P. Christopher Staecker b a Department of Computer and Information Sciences, Niagara University, Niagara University, NY 14109, USA; and Department of Computer Science and Engineering, SUNY at Buffalo (boxer@niagara.edu) b Department of Mathematics, Fairfield University, Fairfield, CT 06823-5195,USA. (cstaecker@fairfield.edu) Communicated by V. Gregori Abstract In this paper, we examine some properties of the fixed point set of a digitally continuous function. The digital setting requires new meth- ods that are not analogous to those of classical topological fixed point theory, and we obtain results that often differ greatly from standard results in classical topology. We introduce several measures related to fixed points for continuous self-maps on digital images, and study their properties. Perhaps the most important of these is the fixed point spectrum F(X) of a digital image: that is, the set of all numbers that can appear as the num- ber of fixed points for some continuous self-map. We give a complete computation of F(Cn) where Cn is the digital cycle of n points. For other digital images, we show that, if X has at least 4 points, then F(X) always contains the numbers 0, 1, 2, 3, and the cardinality of X. We give several examples, including Cn, in which F(X) does not equal {0, 1, . . . , #X}. We examine how fixed point sets are affected by rigidity, retraction, deformation retraction, and the formation of wedges and Cartesian products. We also study how fixed point sets in digital images can be arranged; e.g., for some digital images the fixed point set is always connected. 2010 MSC: 54H25. Keywords: digital image; fixed point; retraction. Received 16 July 2019 – Accepted 08 October 2019 http://dx.doi.org/10.4995/agt.2020.12091 L. Boxer and P. Christopher Staecker 1. Introduction Digital images are often used as mathematical models of real-world objects. A digital model of the notion of a continuous function, borrowed from the study of topology, is often useful for the study of digital images. However, a digital image is typically a finite, discrete point set. Thus, it is often necessary to study digital images using methods not directly derived from topology. In this paper, we introduce several such methods to study properties of the fixed point set of a continuous self-map on a digital image. Many of our results have elementary proofs. Their importance is, in part, due to the following. Digital topology has been successful in showing that digital images resemble the Euclidean objects they model with respect to topologi- cal properties such as connectedness, homotopy, covering maps, fundamental groups, retractions, and homology; however, we see in this paper that the fixed point properties of digital images and the Euclidean objects they model can be very different. Some of the results of this paper were presented in [7]. 2. Preliminaries Let N denote the set of natural numbers; and Z, the set of integers. #X will be used for the number of elements of a set X. 2.1. Adjacencies. A digital image is a pair (X,κ) where X ⊂ Zn for some n and κ is an adjacency on X. Thus, (X,κ) is a graph for which X is the vertex set and κ determines the edge set. Usually, X is finite, although there are papers that consider infinite X. Usually, adjacency reflects some type of “closeness” in Zn of the adjacent points. When these “usual” conditions are satisfied, one may consider the digital image as a model of a black-and-white “real world” digital image in which the black points (foreground) are the members of X and the white points (background) are members of Zn \X. We write x ↔κ y, or x ↔ y when κ is understood or when it is unnecessary to mention κ, to indicate that x and y are κ-adjacent. Notations x -κ y, or x - y when κ is understood, indicate that x and y are κ-adjacent or are equal. The most commonly used adjacencies are the cu adjacencies, defined as follows. Let X ⊂ Zn and let u ∈ Z, 1 ≤ u ≤ n. Then for points x = (x1, . . . ,xn) 6= (y1, . . . ,yn) = y we have x ↔cu y if and only if • for at most u indices i we have |xi −yi| = 1, and • for all indices j, |xj −yj| 6= 1 implies xj = yj. The cu-adjacencies are often denoted by the number of adjacent points a point can have in the adjacency. E.g., • in Z, c1-adjacency is 2-adjacency; • in Z2, c1-adjacency is 4-adjacency and c2-adjacency is 8-adjacency; c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 88 Fixed point sets in digital topology, 1 • in Z3, c1-adjacency is 8-adjacency, c2-adjacency is 18-adjacency, and c3-adjacency is 26-adjacency. We discuss the digital n-cycle, the n-point image Cn = {x0, . . . ,xn−1} in which each xi is adjacent only to xi+1 and xi−1, and subscripts are always read modulo n. The literature also contains several adjacencies to exploit properties of Carte- sian products of digital images. These include the following. Definition 2.1 ([1]). Let (X,κ) and (Y,λ) be digital images. The normal product adjacency or strong adjacency on X ×Y , denoted NP(κ,λ), is defined as follows. Given x0,x1 ∈ X, y0,y1 ∈ Y such that p0 = (x0,y0) 6= (x1,y1) = p1, we have p0 ↔NP(κ,λ) p1 if and only if one of the following is valid: • x0 ↔κ x1 and y0 = y1, or • x0 = x1 and y0 ↔λ y1, or • x0 ↔κ x1 and y0 ↔λ y1. Theorem 2.2 ([9]). Let X ⊂ Zm, Y ⊂ Zn. Then (X ×Y,NP(cm,cn)) = (X ×Y,cm+n), i.e., the cm+n-adjacency on X ×Y ⊂ Zm+n coincides with the normal product adjacency based on cm and cn. Building on the normal product adjacency, we have the following. Definition 2.3 ([5]). Given u,v ∈ N, 1 ≤ u ≤ v, and digital images (Xi,κi), 1 ≤ i ≤ v, let X = Πvi=1Xi. The adjacency NPu(κ1, . . . ,κv) for X is defined as follows. Given xi,x ′ i ∈ Xi, let p = (x1, . . . ,xv) 6= (x′1, . . . ,x ′ v) = q. Then p ↔NPu(κ1,...,κv) q if for at least 1 and at most u indices i we have xi ↔κi x′i and for all other indices j we have xj = x ′ j. Notice NP(κ,λ) = NP2(κ,λ) [5]. When (X,κ) is understood to be a digital image under discussion, we use the following notations. For x ∈ X, N(x) = {y ∈ X |y ↔κ x}, N∗(x) = {y ∈ X |y -κ x} = N(x) ∪{x}. 2.2. Digitally continuous functions. We denote by id or idX the identity map id(x) = x for all x ∈ X. Definition 2.4 ([14, 3]). Let (X,κ) and (Y,λ) be digital images. A function f : X → Y is (κ,λ)-continuous, or digitally continuous or just continuous when κ and λ are understood, if for every κ-connected subset X′ of X, f(X′) is a λ-connected subset of Y . If (X,κ) = (Y,λ), we say a function is κ-continuous to abbreviate “(κ,κ)-continuous.” c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 89 L. Boxer and P. Christopher Staecker Theorem 2.5 ([3]). A function f : X → Y between digital images (X,κ) and (Y,λ) is (κ,λ)-continuous if and only if for every x,y ∈ X, if x ↔κ y then f(x) -λ f(y). Theorem 2.6 ([3]). Let f : (X,κ) → (Y,λ) and g : (Y,λ) → (Z,µ) be con- tinuous functions between digital images. Then g ◦ f : (X,κ) → (Z,µ) is continuous. A path is a continuous function r : [0,m]Z → X. We use the following notation. For a digital image (X,κ), C(X,κ) = {f : X → X |f is continuous}. Definition 2.7 ([3]; see also [13]). Let X and Y be digital images. Let f,g : X → Y be (κ,κ′)-continuous functions. Suppose there is a positive integer m and a function h : X × [0,m]Z → Y such that • for all x ∈ X, h(x, 0) = f(x) and h(x,m) = g(x); • for all x ∈ X, the induced function hx : [0,m]Z → Y defined by hx(t) = h(x,t) for all t ∈ [0,m]Z is (c1,κ ′)−continuous. That is, hx(t) is a path in Y . • for all t ∈ [0,m]Z, the induced function ht : X → Y defined by ht(x) = h(x,t) for all x ∈ X is (κ,κ′)−continuous. Then h is a digital (κ,κ′)−homotopy between f and g, and f and g are digi- tally (κ,κ′)−homotopic in Y , denoted f 'κ,κ′ g or f ' g when κ and κ′ are understood. If (X,κ) = (Y,κ′), we say f and g are κ-homotopic to abbreviate “(κ,κ)-homotopic” and write f 'κ g to abbreviate “f 'κ,κ g”. If there is a κ-homotopy between idX and a constant map, we say X is κ-contractible, or just contractible when κ is understood. Definition 2.8. Let A ⊆ X. A κ-continuous function r : X → A is a retrac- tion, and A is a retract of X, if r(a) = a for all a ∈ A. If such a map r satisfies i◦ r 'κ idX where i : A → X is the inclusion map, then r is a κ-deformation retraction and A is a κ-deformation retract of X. A topological space X has the fixed point property (FPP) if every continuous f : X → X has a fixed point. A similar definition has appeared in digital topology: a digital image (X,κ) has the fixed point property (FPP) if every κ-continuous f : X → X has a fixed point. However, this property turns out to be trivial, in the sense of the following. Theorem 2.9 ([8]). A digital image (X,κ) has the FPP if and only if #X = 1. The proof of Theorem 2.9 was due to the establishment of the following. Lemma 2.10 ([8]). Let (X,κ) be a digital image, where #X > 1. Let x0,x1 ∈ X be such that x0 ↔κ x1. Then the function f : X → X given by f(x0) = x1 and f(x) = x0 for x 6= x0 is κ-continuous and has 0 fixed points. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 90 Fixed point sets in digital topology, 1 Figure 1. A rigid image in Z2 with 8-adjacency A function f : (X,κ) → (Y,λ) is an isomorphism (called a homeomorphism in [2]) if f is a continuous bijection such that f−1 is continuous. 3. Rigidity We will say a function f : X → Y is rigid when no continuous map is homotopic to f except f itself. This generalizes a definition in [11]. When the identity map id : X → X is rigid, we say X is rigid. Many digital images are rigid, though it can be difficult to show directly that a given example is rigid. A computer search described in [15] has shown that no rigid images in Z2 with 4-adjacency exist having fewer than 13 points, and no rigid images in Z2 with 8-adjacency exist having fewer than 10 points. We will demonstrate some methods for showing that a given image is rigid. For example, the digital image in Figure 1 is rigid, as shown below in Example 3.11. An immediate consequence of the definition of rigidity is the following. Proposition 3.1. Let (X,κ) be a rigid digital image such that #X > 1. Then X is not κ-contractible. Rigidity of functions is preserved when composing with an isomorphism, as the following theorems demonstrate: Theorem 3.2. Let f : X → Y be rigid and g : Y → Z be an isomorphism. Then g ◦f : X → Z is rigid. Proof. Suppose otherwise. Then there is a homotopy h : X × [0,m]Z → Z from g ◦f to a map G : X → Z such that g ◦f 6= G. Then by Theorem 2.6, g−1 ◦h : X × [0,m]Z → X is a homotopy from f to g−1 ◦G, and since g−1 is one-to-one, f 6= g−1 ◦G. This contradiction of the assumption that f is rigid completes the proof. � Theorem 3.3. Let f : X → Y be rigid. Let g : W → X be an isomorphism. Then f ◦g is rigid. Proof. Suppose otherwise. Then there is a homotopy h : W × [0,m]Z → Y from f ◦ g to some G : W → Y such that G 6= f ◦ g. Thus, for some w ∈ W , G(w) 6= f ◦g(w). Now consider the function h′ : X × [0,m]Z → Y defined by c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 91 L. Boxer and P. Christopher Staecker h′(x,t) = h(g−1(x), t). By Theorem 2.6, h′ is a homotopy from f ◦g◦g−1 = f to G◦g−1. Since f ◦g(w) 6= G(w) = (G◦g−1)(g(w)), the homotopic functions f and G◦g−1 differ at g(w), contrary to the assumption that f is rigid. The assertion follows. � As an immediate corollary, we obtain: Corollary 3.4. If f : X → Y is an isomorphism and one of X and Y are rigid, then f is rigid. Proof. In the case where X is rigid, the identity map idX is rigid. Then by Theorem 3.3 we have f◦idX = f is rigid. In the case where Y is rigid, similarly by Theorem 3.2 we have idY ◦f = f is rigid. � The corollary above can be stated equivalently as follows: Corollary 3.5. A digital image X is rigid if and only if every digital image Y that is isomorphic to X is rigid. It is easy to see that no digital image in Z is rigid: Proposition 3.6. If X ⊂ Z is a connected digital image with c1 adjacency and #X > 1, then X is not rigid. Proof. A connected subset of Z having more than one point takes one of the forms [a,b]Z, {z ∈ Z |z ≥ a}, {z ∈ Z |z ≤ b}, Z. In all of these cases, it is easily seen that there is a deformation retraction of X to a proper subset of X. Therefore, X is not rigid. � We also show that a normal product of images is rigid if and only if all of its factors are rigid. Theorem 3.7. Let (Xi,κi) be digital images for each 1 ≤ i ≤ v, and (X,κ) = ( v∏ i=1 Xi,NPu(κ1, . . . ,κv)) for some u, 1 ≤ u ≤ v. Then X is rigid if and only if Xi is rigid for each i. Proof. First we assume X is rigid, and we will show that Xi is rigid for each i. For some i, let hi : Xi × [0,m]Z → Xi be a κi-homotopy from idXi to fi : Xi → Xi. Without loss of generality we may assume m = 1, and we will show that hi(xi, 1) = xi, and thus fi = idXi . The function h : X × [0, 1]Z → X defined by h(x1, . . . ,xv, t) = (x1, . . . ,xi−1,hi(xi, t),xi+1, . . . ,xv), is a homotopy. Since X is rigid we must have h(x1, . . . ,xv, 1) = idX, and this means hi(xi, 1) = xi as desired. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 92 Fixed point sets in digital topology, 1 Now we prove the converse: assume Xi is rigid, and we will show X is rigid. Let Ji : Xi → X be the function Ji(x) = (x1, . . . ,xi−1,x,xi+1, . . . ,xn). Let pi : X → Xi be the projection function, pi(x1, . . . ,xv) = xi. Then Ji is (κi,κ)-continuous, where κ = NPu(κ1, . . . ,κv), and pi is (κ,κi)- continuous [5, 6]. For the sake of a contradiction, suppose X is not rigid. Then there is a homotopy h : (X,κ)× [0,m]Z → X between idX and a function g such that for some y = (y1, . . . ,yv) ∈ X, g(y) 6= y. Then for some index j, pj(y) 6= pj(g(y)). Then the function h′ : Xj × [0,m]Z → Xj defined by h′(x,t) = pj(h(Jj(x), t)), is a homotopy from idXj to a function gj, with gj(yj) = pj(h(Jj(yj),m)) = pj(h(y,m)) = pj(g(y)) 6= pj(y) = yj, contrary to the assumption that Xi is rigid. We conclude that X is rigid. � We have a similar result when X is a disjoint union of digital images. Let X be a digital image of the form X = A∪B where A and B are disjoint and no point of A is adjacent to any point of B. We say X is the disjoint union of A and B, and we write X = AtB. Theorem 3.8. Let X = AtB. Then X is rigid if and only if A and B are rigid. Proof. First we assume that X is rigid, and we will show that A is rigid. (It will follow from a similar argument that B is rigid.) Let f : A → A be any self-map homotopic to idA, and we will show that f = idA. Define g : X → X by g(x) = { f(x) if x ∈ A; x if x ∈ B. Then g is continuous and homotopic to idX, and since X is rigid we must have g = idX, which means that f = idA. Now for the converse, assume that A and B are both rigid. Take some self- map f : X → X homotopic to idX, and we will show that f = idX. Since f is homotopic to the identity, we must have f(A) ⊆ A and f(B) ⊆ B. This is because there will always be a path from any point x to f(x) given by the homotopy from idX to f(x). Thus if x ∈ A we must also have f(x) ∈ A since there are no paths from points of A to points of B. Since f(A) ⊆ A and f(B) ⊆ B, there are well-defined restrictions fA : A → A and fB : B → B, and the homotopy from idX to f induces homotopies from idA to fA and idB to fB. Since A and B are rigid we must have fA = idA and fB = idB, and thus f = idX as desired. � Since every digital image is a disjoint union of its connected components, we have: c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 93 L. Boxer and P. Christopher Staecker Corollary 3.9. A digital image X is rigid if and only if every connected com- ponent of X is rigid. Let X be some digital image of the form X = A∪B, where A∩B is a single point x0, and no point of A is adjacent to any point of B except x0. We say X = A∪B is the wedge of A and B, denoted X = A∨B, and x0 is called the wedge point of A∨B. We have the following. Theorem 3.10. If X = A∨B and A and B are rigid, then X is rigid. Proof. Let x0 be the wedge point of A∨B, and let A0 and B0 be the components of A and B that include x0. If #A0 = 1 or #B0 = 1, then the components of A∨B are in direct correspondence to the components of A and B and the result follows by Corollary 3.9. Thus we assume #A0 > 1 and #B0 > 1. Let h : A∨B × [0,m]Z → A∨B be a homotopy such that h(x, 0) = x for all x ∈ A∨B. Without loss of generality, m = 1. If the induced map h1 is not idX then there is a point x ′ ∈ X such that h1(x′) = h(x′, 1) 6= x′. Without loss of generality, x′ ∈ A. Let pA : X → A be the projection pA(x) = { x for x ∈ A; x0 for x ∈ B. Since pA ◦h is a homotopy from idA to pA ◦h1, and A is rigid, we have (3.1) pA ◦h1 = idA . Were h1(x ′) ∈ A then it would follow that h1(x ′) = pA ◦h1(x′) = x′, contrary to our choice of x′. Therefore we have h1(x ′) ∈ B \ {x0}. But x′ ↔ h1(x′), so x′ = x0. Since A0 is connected and has more than 1 point, there exists x1 ∈ A such that x1 ↔κ x0. By the continuity of h1 and choice of x0, we must therefore have h1(x1) = x0, and therefore pA ◦h1(x1) = pA(x0) = x0. This contradicts statement (3.1), so the assumption that h1 is not idX is incorrect, and the assertion follows. � A loop is a continuous function p : Cm → X. The converse of Theorem 3.10 is not generally true. In [11] it was mentioned (without proof) that a wedge of two long cycles is in general rigid. We give a specific example: Example 3.11. Let A and B be non-contractible simple closed curves. Then A and B are non-rigid [11]. However, X = A∨B is rigid. E.g., using c2 = 8- adjacency in Z2, let A = {a0 = (0, 0),a1 = (1,−1),a2 = (2,−1),a3 = (3, 0),a4 = (2, 1),a5 = (1, 1)} and let B = {b0 = a0,b1 = (−1,−1),b2 = (−2,−1),b3 = (−3, 0),b4 = (−2, 1),b5 = (−1, 1)}. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 94 Fixed point sets in digital topology, 1 By continuity, if there is a homotopy h : X × [0,m]Z → X - without loss of generality, m = 1 - such that h0 = idX and h(x, 1) 6= x, then h “pulls” [11] every point of A or of B and therefore “breaks” one of the loops of X, a contradiction since “breaking” a loop is a discontinuity. Thus no such homotopy exists. 2 4. Homotopy fixed point spectrum The paper [10] gave a brief treatment of homotopy-invariant fixed point theory, defining two quantities M(f) and X(f), respectively the minimum and maximum possible number of fixed points among all maps homotopic to f. When f : X → X, clearly we will have: 0 ≤ M(f) ≤ X(f) ≤ #X. We will see in the examples below that any one of these inequalities can be strict in some cases, or equality in some cases. More generally, for some map f : X → X, let Fix(f) denote the set of fixed points of f. We consider the following set S(f), which we call the homotopy fixed point spectrum of f: S(f) = {# Fix(g) | g ' f}⊆{0, . . . , #X}. An immediate consequence of Lemma 2.10: Corollary 4.1. Let (X,κ) be a connected digital image, where #X > 1. Then 0 ∈ S(c), where c ∈ C(X,κ) is a constant map. We can also consider the fixed point spectrum of X, defined as: F(X) = {# Fix(f) | f : X → X is continuous} Remark 4.2. The following assertions are immediate consequences of the rele- vant definitions. • If X is a digital image of only one point, then F(X) = {1}. • If f : X → X is rigid, then S(f) = {# Fix(f)}. If X is rigid, then S(id) = {#X}. Since every image X has a constant map and an identity map, we always have: {1, #X}⊆ F(X). The number of fixed points is always preserved by isomorphism: Lemma 4.3. Let X and Y be isomorphic digital images. Let f : X → X be continuous. Then there is a continuous g : Y → Y such that # Fix(f) = # Fix(g). Proof. Let G : X → Y be an isomorphism. Let A = Fix(f). Since G is one- to-one, #G(A) = #A. Let g : Y → Y be defined by g = G ◦ f ◦ G−1. For y0 ∈ G(A), let x0 = G−1(y0). Then g(y0) = G◦f ◦G−1(y0) = G◦f(x0) = G(x0) = y0. Let B = Fix(g) It follows that G(A) ⊆ B, so #A ≤ #B. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 95 L. Boxer and P. Christopher Staecker Since G−1 is an isomorphism, it similarly follows that #B ≤ #A. Thus, # Fix(f) = # Fix(g). � As an immediate consequence, we have the following. Corollary 4.4. Let X and Y be isomorphic digital images. Then F(X) = F(Y ). There is a certain regularity to the fixed point spectrum for connected digital images. When X has only a single point, we have already remarked that F(X) = {1}. For images of more than 1 point, we will show that F(X) always includes 0, 1, and #X, and, provided the image is large enough, the set F(X) also includes 2 and 3. The following statements hold for connected images. We discuss the fixed point spectrum of disconnected images in terms of their connected components in Theorem 7.2 and its corollary. We begin with a simple lemma: Lemma 4.5. Let X be any connected digital image with #X > 1. Let x0 ∈ X, and let 0 ≤ k ≤ #N∗(x0). Then k ∈ S(c) ⊆ F(X), where c is the map with image {x0}. Proof. By Corollary 4.1, a constant map is homotopic to a map with no fixed points, so 0 ∈ S(c) as desired. For k > 0, let n = #N∗(x0) and write N∗(x0) = {x0,x1, . . . ,xn−1}. Then define f : X → X by: f(x) = { x if x = xi for some i < k, x0 otherwise. Then f is continuous with Fix(f) = {x0, . . . ,xk−1} and thus k ∈ F(X). Fur- thermore, f is homotopic to the constant map at x0, and so in fact k ∈ S(c). � Theorem 4.6. Let X be a connected digital image, and let c : X → X be any constant map. If #X ≥ 2 then {0, 1, 2}⊆ S(c). If #X ≥ 3, then {0, 1, 2, 3}⊆ S(c). Proof. If #X = 2, then X consists simply of two adjacent points. Thus #N∗(x) = 2 for each x ∈ X, and so Lemma 4.5 implies that {0, 1, 2}⊆ S(c). When #X ≥ 3, there must be some x ∈ X with #N∗(x) ≥ 3. (Otherwise the image would consist only of disjoint pairs of adjacent points, which would not be connected.) Thus by Lemma 4.5 we have {0, 1, 2, 3}⊆ S(c). � Since we always have #X ∈ S(id) and S(c) ∪S(id) ⊆ F(X) ⊆{0, 1, . . . , #X}, the theorem above directly gives: c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 96 Fixed point sets in digital topology, 1 Corollary 4.7. Let X be a connected digital image. If #X = 2 then F(X) = {0, 1, 2}. If #X > 2, then {0, 1, 2, 3, #X}⊆ F(X). We have already seen that #X ∈ F(X) in all cases. There is an easy condition that determines whether or not #X − 1 ∈ F(X). Lemma 4.8. Let X be connected with n = #X > 1. Then n − 1 ∈ F(X) if and only if there are distinct points x1,x2 ∈ X with N(x1) ⊆ N∗(x2). Proof. Suppose there are points x1,x2 ∈ X, x1 6= x2, such that N(x1) ⊆ N∗(x2). Then the map f(x1) = x2, f(x) = x for all x 6= x1, is a self-map on X with exactly n−1 fixed points. That f is continuous is seen as follows. Suppose x,x′ ∈ X with x ↔ x′. • If x1 6∈ {x,x′}, then f(x) = x ↔ x′ = f(x′). • If, say, x = x1, then x′ ∈ N(x1) ⊆ N∗(x2), so f(x′) = x′ - x2 = f(x1). Thus f is continuous, and we conclude n− 1 ∈ F(X). Now assume that n− 1 ∈ F(X). Thus there is some continuous self-map f with exactly n− 1 fixed points. Let x1 be the single point not fixed by f, and let x2 = f(x1). Then let x ∈ X with x ↔ x1. Then x = f(x) - f(x1) = x2, so N(x1) ⊆ N∗(x2). � Lemma 4.8 can be used to show that a large class of digital images will satisfy n − 1 6∈ F(X). For example when X = Cn for n > 4, no N(xi) is contained in N∗(xj) for j 6= i. Thus we have: Corollary 4.9. Let n > 4. Then n− 1 6∈ F(Cn). In particular this means that 4 6∈ F(C5), so the result of Theorem 4.7 cannot in general be improved to state that 4 ∈ F(X) for all images of more than 4 points. 5. Pull indices Let Fix(f) be the complement of the fixed point set, that is, Fix(f) = {x ∈ X | f(x) 6= x}. When f(x) 6= x, we say f moves x. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 97 L. Boxer and P. Christopher Staecker Definition 5.1. Let (X,κ) be a digital image with #X > 1 and let x ∈ X. The pull index of x, P(x) or P(x,X) or P(x,X,κ), is P(x) = min{#Fix(f) | f : X → X is continuous and f(x) 6= x}. When f(x) 6= x, the set Fix(f) always contains at least the point x, and so P(x) ≥ 1 for any x that is moved by some f. Example 5.2. Let X = [1, 3]Z with c1-adjacency. To compute P(3), consider the function f(x) = min{x, 2}. This is contin- uous, not the identity, and Fix(f) = {1, 2}, and thus P(3) = 1. Similarly we can show that P(1) = 1. But we have P(2) = 2, since any continuous self-map f on X that moves 2 must also move at least one other point: if f(2) = 1 we must have f(3) ∈{1, 2}, and if f(2) = 3 we must have f(1) ∈{2, 3}. Proposition 5.3. Let (X,κ) be a connected digital image with n = #X > 1. Let m ∈ N, 1 ≤ m ≤ n. Suppose, for all x ∈ X, we have P(x) ≥ m . Then F(X) ∩{i}n−1i=n−m+1 = ∅. Proof. By hypothesis, f ∈ C(X,κ) \{idX} implies f moves at least m points, hence # Fix(f) ≤ n−m. The assertion follows. � Theorem 5.4. Let (X,κ) be a connected digital image with n = #X > 1. The following are equivalent. 1) n− 1 ∈ F(X). 2) There are distinct x1,x2 ∈ X such that N(x1) ⊆ N∗(x2). 3) There exists x ∈ X such that P(x) = 1. Proof. 1) ⇔ 2) is shown in Lemma 4.8. 1) ⇔ 3): We have n−1 ∈ F(X) ⇔ there exists f ∈ C(X) with exactly n−1 fixed points, i.e., the only x ∈ X not fixed by f has P(x) = 1. � The following generalizes 1) ⇒ 3) of Theorem 5.4. Proposition 5.5. Let (X,κ) be a connected digital image with n = #X > 1. Let k ∈ [1,n−1]Z. Then k ∈ F(X) implies there exist distinct x1, . . . ,xn−k ∈ X such that P(xi) ≤ n−k. Proof. k ∈ F(X) implies there exists f ∈ C(X) with exactly k fixed points, hence distinct x1, . . . ,xn−k ∈ X such that xi 6∈ Fix(f). Thus for each i, the members of Fix(f) are not pulled by f and xi. Thus P(xi) ≤ n−k. � 6. Retracts In this section, we study how retractions interact with fixed point spectra. Theorem 6.1 ([2]). Let (X,κ) be a digital image and let A ⊆ X. Then A is a retract of X if and only if for every continuous f : (A,κ) → (Y,λ) there is an extension of f to a continuous g : (X,κ) → (Y,λ). c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 98 Fixed point sets in digital topology, 1 In the proof of Theorem 6.1, an extension of f is obtained by using g = f◦r, where r : X → A is a retraction. We use this in the proof of the next assertion. Theorem 6.2. Let A be a retract of (X,κ). Then F(A) ⊆ F(X). Proof. Let f : A → A be κ-continuous. Let r : X → A be a κ-retraction. Let i : A → X be the inclusion function. By Theorem 2.6, G = i◦f ◦ r : X → X is continuous. Further, G(x) = f(x) if and only if x ∈ A, so Fix(G) = Fix(f). Since f was taken arbitrarily, the assertion follows. � Remark 6.3. We do not have an analog to Theorem 6.2 by replacing fixed point spectra by spectra of identity maps. E.g, in Example 3.11 we have {0, #A}⊆ S(idA), and A is a retract of X, but X is rigid, so S(idX) = {#X}. However, we have the following Corollaries 6.4 and 6.5. Corollary 6.4. Let A be a deformation retract of X. Then S(idA) ⊆ S(idX) ⊆ F(X). In particular, #A ∈ S(idX). Corollary 6.5. Let a,b ∈ Z, a < b. Then S(id[a,b]Z,c1) = F([a,b]Z,c1) = {0, 1, . . . ,b−a + 1}. Proof. Since a < b and [a,b]Z is c1-contractible, it follows from Theorem 2.9 that 0 ∈ S(id[a,b]Z,c1). Since for each d ∈ [a,b]Z there is a c1-deformation of [a,b]Z to [a,d]Z, it follows from Corollary 6.4 that #[a,d]Z ∈ S(id[a,b]Z,c1). Thus, F([a,b]Z,c1) ⊆{i}b−a+1i=0 = S(id[a,b]Z,c1) ⊆ F([a,b]Z,c1). The assertion follows. � We can generalize this result about intervals to a two-dimensional box in Z2. Theorem 6.6. Let X = [1,a]Z × [1,b]Z, with adjacency κ ∈{c1,c2}. Then S(idX) = F(X) = {0, 1, . . . ,ab} Proof. All self-maps on [1,a]Z × [1,b]Z are homotopic to the identity, so it suffices only to show that F(X) = {0, 1, . . . ,ab}. The proof is by induction on a. For a = 1, our image X is isomorphic to the one-dimensional image ([1,b]Z,c1). Thus by Theorem 6.5 we have F(X) = {0, 1, . . . ,b} = {0, 1, . . . ,ab} as desired. For the inductive step, first note that [1,a − 1]Z × [1,b]Z is a retract of X (using either κ = c1 or c2). Thus by induction and Theorem 6.2 we have {0, 1, . . . , (a− 1)b}⊆ F(X). It remains only to show that {(a− 1)b + 1, (a− 1)b + 2, . . . ,ab}⊆ F(X). We do this by exhibiting a family of self-maps of X having these numbers of fixed points. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 99 L. Boxer and P. Christopher Staecker Figure 2. The map ft from Theorem 6.6, pictured in the case t = 2. All points are fixed except those with arrows indicating where they map to. Let t ∈{0, . . . ,b− 1}, and define ft : X → X as follows: ft(x,y) = { (x,y) if x > 1 or y > t, (x + 1,y + 1) if x = 1 and y ≤ t See Figure 2 for a pictorial depiction of ft. This ft is well-defined and both c1- and c2-continuous for each t ∈{0, . . . ,b− 1} and has ab− t fixed points. Thus we have {ab,ab− 1, . . . ,ab− (b− 1) = (a− 1)b + 1}⊆ F(X) as desired. � 7. Cartesian products and disjoint unions In the following, assume Ai ⊂ N, 1 ≤ i ≤ v. Define v⊗ i=1 Ai = { v∏ i=1 ai | ai ∈ Ai } and v⊕ i=1 Ai = { v∑ i=1 ai | ai ∈ Ai } . If fi : Xi → Yi, let Πvi=1fi : Π v i=1Xi → Π v i=1Yi be the product function defined by Πvi=1fi(x1, . . .xv) = (f1(x1), . . . ,fv(xv)) for xi ∈ Xi. Theorem 7.1. Suppose (Xi,κi) is a digital image, 1 ≤ i ≤ v. Let X = Πvi=1Xi. Then ⊗v i=1 F(Xi,κi) ⊆ F(X,NPv(κ1, . . . ,κv)). Proof. Let fi : Xi → Xi be κi-continuous. Let X = Πvi=1Xi. Then the product function f = Πvi=1fi(x1, . . .xv) : X → X is NPv(κ1, . . . ,κv)-continuous [5]. If Ai = {yi,ji} pi ji=1 is the set of distinct fixed points of fi, then each point (y1,j1, . . . ,yv,jv ), for 1 ≤ ji ≤ pi, is a fixed point of f. The assertion follows. � c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 100 Fixed point sets in digital topology, 1 We note that the conclusion of Theorem 7.1 cannot in general be strength- ened to say that ⊗v i=1 F(Xi) = F(X). For example, if X = [1, 3]Z × [1, 3]Z, we have F(X) = {0, 1, . . . , 9} by Theorem 6.6, but F([1, 3]Z) ⊗F([1, 3]Z) = {0, 1, 2, 3}⊗{0, 1, 2, 3} = {0, 1, 2, 3, 4, 6, 9}. We do have a similar result, this time with equality, for a disjoint union of digital images. Theorem 7.2. Let X = AtB. If A and B both have at least 2 points, then F(X) = F(A) ⊕F(B). Proof. First we show that F(A)⊕F(B) ⊆ F(X). Take some k ∈ F(A)⊕F(B), say k = m + n with m ∈ F(A) and n ∈ F(B). That means there are two self- maps f : A → A and g : B → B with # Fix(f) = m and # Fix(g) = n. Let h : X → X be defined by: h(x) = { f(x) if x ∈ A g(x) if x ∈ B Then # Fix(h) = # Fix(f) + # Fix(g) = m + n = k and so k ∈ F(X) as desired. Next we show F(X) ⊆ F(A) ⊕ F(B). Take some k ∈ F(X), so there is some self-map f with # Fix(f) = k. Let fA : A → X and fB : B → X be the restrictions of f to A and B. Since X = A∪B, we have Fix(f) = Fix(fA) ∪ Fix(fB), and Fix(fA) = Fix(f) ∩ A and Fix(fB) = Fix(f) ∩ B. Since A and B are disjoint, the union of the fixed point sets above is disjoint. Thus we have k = # Fix(fA) + # Fix(fB). Since continuous functions preserve connectedness, we must have fA(A) ⊆ A or fA(A) ⊆ B. Similarly fB(B) ⊆ A or fB(B) ⊆ B. We show that k ∈ F(A) ⊕F(B) in several cases. In the case where fA(A) ⊆ B and fB(B) ⊆ A, there are no fixed points of fA or fB, and thus no fixed points of f. Thus k = 0, and it is true that k ∈ F(A) ⊕F(B) since 0 ∈ F(A) and 0 ∈ F(B) by Theorem 4.6. In the case where fA(A) ⊆ B and fB(B) ⊆ B, there are no fixed points of fA, and thus Fix(f) = Fix(fB). In this case in fact fB is a self-map of B, and so k = # Fix(f) = 0 + # Fix(fB) ∈ F(A) ⊕F(B) since 0 ∈ F(A) by Theorem 4.6 and # Fix(fB) ∈ F(B) since fB is a self-map on B. The case where fA(A) ⊆ A and fB(B) ⊆ A is similar. The final case is when fA(A) ⊆ A and fB(B) ⊆ B. In this case fA is a self-map of A and fB is a self-map of B. Since Fix(f) = Fix(fA) ∪ Fix(fB), the k fixed points of f must partition into m fixed points of fA and n fixed points of fB, where m + n = k. Thus m ∈ F(A) and n ∈ F(B), and so k = m + n ∈ F(A) ⊕F(B). � c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 101 L. Boxer and P. Christopher Staecker The assumption above that A and B have at least 2 points is necessary. For example if A and B are each a single point, then F(X) = {0, 1, 2} while F(A) = F(B) = {1} and thus F(A) ⊕F(B) = {2}. Since any digital image is a disjoint union of its connected components, we have: Corollary 7.3. Let X1, . . . ,Xk be the connected components of a digital image X, and assume that #Xi > 1 for all i. Then we have: F(X) = k⊕ i=1 F(Xi) 8. Locations of fixed points In many cases, the existence of two fixed points will imply that other fixed points must exist in certain locations. In some cases we will show that Fix(f) must be connected. We do not have Fix(f) connected in general, as shown by the following. Example 8.1. Let X = {p0 = (0, 0),p1 = (1, 0),p2 = (2, 0),p3 = (1, 1)}. Let f : X → X be defined by f(p0) = p0, f(p1) = p3, f(p2) = p2, f(p3) = p1. Then X is c2-connected, f ∈ C(X,c2), and Fix(f) = {p0,p2} is c2-disconnected. Lemma 8.2. Let (X,κ) be a digital image and f : X → X be continuous. Suppose that x,x′ ∈ Fix(f) and that y ∈ X lies on every path of minimal length between x and x′. Then y ∈ Fix(f). Proof. Let k be the minimal length of a path from x to x′. First we show that y must occur at the same location along any minimal path from x to x′. That is, we show that there is some i ∈ [0,k]Z with p(i) = y for every minimal path p from x to x′. This we prove by contradiction: assume we have two minimal paths p and q with p(i) = y = q(j) for some j < i. Then construct a new path r by traveling from x to y along q, and then from y to x′ along p. Then this path r has length less than the length of p, contradicting the minimality of p. Thus we have some i ∈ [0,k]Z with p(i) = y for every minimal path p from x to x′. Let p be some minimal path from x to x′, and since the endpoints of p are fixed, the path f(p) is also a path from x to x′. Furthermore the length of f(p) must be at most k, and thus must equal k since this is the minimal possible length of a path from x to x′. Since both p and f(p) are minimal paths from x to x′, we have p(i) = f(p(i)) = y, and thus y = f(y) as desired. � A vertex v of a connected graph (X,κ) is an articulation point of X if (X\{v},κ) is disconnected. We have the following immediate consequences of Lemma 8.2. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 102 Fixed point sets in digital topology, 1 Corollary 8.3. Let (X,κ) be a connected digital image. Let v be an articula- tion point of X. Suppose f ∈ C(X,κ) has fixed points in distinct components of X \{v}. Then v is a fixed point of f. Corollary 8.4. Let (X,κ) be a digital image and f ∈ C(X,κ). Suppose x,x′ ∈ Fix(f) are such that there is a unique shortest κ-path P in X from x to x′. Then P ⊆ Fix(f). Proof. This follows immediately from Lemma 8.2. � Corollary 8.5. Let (X,κ) be a digital image that is a tree. Then f ∈ C(X,κ) implies Fix(f) is κ-connected. Proof. This follows from Corollary 8.4, since given x,x′ in a tree X, there is a unique shortest path in X from x to x′. � For a digital cycle, the fixed point set is typically connected. The only exception is in a very particular case, as we see below. Theorem 8.6. Let f : Cn → Cn be any continuous map. Then Fix(f) is connected, or is a set of 2 nonadjacent points. The latter case occurs only when n is even and the two fixed points are at opposite positions in the cycle. Proof. If # Fix(f) ∈{0, 1}, then Fix(f) is connected. When # Fix(f) > 1, we show that if xi,xj ∈ Fix(f) are two distinct fixed points, then either there is a path from xi to xj through other fixed points, or that no other points are fixed. There are two canonical paths p and q from xi to xj: the two injective paths going in either “direction” around the cycle. Without loss of generality assume |p| ≥ |q|. This means that |q| is the shortest possible length of a path from xi to xj. Consider the case in which |p| > |q|. In this case |q| is the unique shortest path from xi to xj, and by Lemma 8.4, q ⊆ Fix(f), and so xi and xj are connected by a path of fixed points as desired. Now consider the case in which |p| = |q|. In this case again |q| is the shortest possible length of a path from xi to xj, and p and q are the only two paths from xi to xj having this length. Then f(q) is a path from xi to xj of length |q|, and so we must have either f(q) = q or f(q) = p. In the former case, q is a path of fixed points connecting xi and xj as desired. In the latter case, Fix(f) ∩q = {xi,xj}. Similarly considering the path f(p), we must have either f(p) = p (in which case p is a path of fixed points connecting xi and xj); or f(p) = f(q), in which case Fix(f) ∩p = {xi,xj}. Considering all cases, either a minimal-length path from xi to xj is contained in Fix(f), or Fix(f) = {xi,xj}. The second sentence of the theorem follows from our analysis of the various cases. The only case which gives 2 nonadjacent fixed points requires xi and xj to be opposite points on the cycle, which requires n to be even. � c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 103 L. Boxer and P. Christopher Staecker x3 x2 x7 x6 x0 x1 x4 x5 Figure 3. A contractible image for which F(X) 6= {0, 1, . . . , #X}. 9. Remarks and examples In classical topology M(f) is the only interesting homotopy invariant count of the number of fixed points. S(f) is not studied in classical topology, since in all typical cases (all continuous maps on polyhedra) we would have S(f) = [M(f),∞)Z. In classical topology the value of M(f) is generally hard to compute. The Lefschetz number gives a very rough indication of homotopy invariant fixed point information, and the more sophisticated Nielsen number is a homotopy invariant lower bound for M(f). See [12]. When X is contractible, all self-maps are homotopic, so S(f) = F(X) for any self-map f. It is natural to suspect that when X is contractible with #X > 1, we will always have F(X) = {0, 1, . . . , #X}. This is false, however, as the following example shows: Example 9.1. Let X ⊂ Z3 be the unit cube of 8 points with c1 adjacency, shown in Figure 3. Then X is contractible, so S(f) = F(X) for any self-map f. By projecting the cube into one of its faces, we see that X retracts to C4, and since F(C4) = {0, 1, 2, 3, 4}, we have {0, 1, 2, 3, 4}⊆ F(X) by Theorem 6.2. In fact there are also continuous maps having 5 or 6 fixed points: Let: g(x5) = x0, g(x6) = x3, g(xi) = xi for i 6∈ {5, 6} Then g is continuous with 6 fixed points. Let: h(x5) = h(x7) = x0, h(x6) = x3, h(xi) = xi for i 6∈ {5, 6, 7} Then h is continuous with 5 fixed points. Since of course the identity map has 8 fixed points, we have so far shown that {0, 1, 2, 3, 4, 5, 6, 8}⊆ F(X). In fact 7 6∈ F(X). This follows from Lemma 4.8. We have shown that: F(X) = {0, 1, 2, 3, 4, 5, 6, 8}. The computation of S(f) in general seems to be a difficult and interesting problem. Even in the case of self-maps on the cycle Cn, the results are in- teresting. First we show that in fact there are exactly 3 homotopy classes of self-maps on Cn: the identity map id(xi) = xi, the constant map c(xi) = x0, and the flip map l(xi) = x−i. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 104 Fixed point sets in digital topology, 1 Theorem 9.2. Given f ∈ C(Cn), f is homotopic to one of: a constant map, the identity map, or the flip map. Proof. We have noted above that if n ≤ 4 then Cn is contractible, so every f ∈ C(Cn) is homotopic to a constant map. Thus, in the following, we assume n > 4. We can compose f by some rotation r to obtain g = r ◦ f ' f such that g(x0) = x0. We will show that g is either the identity, the flip map, or homo- topic to a constant map. If g is not a surjection, then its continuity implies g(Cn) is a connected proper subset of Cn, hence is contractible. Therefore, g is homotopic to a constant map. If g is a surjection, then g is a bijection because the domain and codomain of g both have cardinality n. By continuity, g(x1) ↔ g(x0) = x0. Therefore, either g(x1) = xn−1 or g(x1) = x1. If g(x1) = x−1, then continuity and the fact that g is a bijection yield an easy induction showing that g(xi) = x−i, 0 ≤ i < n. Therefore, g is the flip map. If g(x1) = x1, a similar argument shows that g is the identity. � In fact the proof of Theorem 9.2 demonstrates the following stronger state- ment. Let rd : Cn → Cn be the rotation map rd(xi) = xi+d. The following generalizes Theorem 3.4 of [4], which states that any map homotopic to the identity must be a rotation. Theorem 9.3. Let f : Cn → Cn be continuous. Then one of the following is true: • f is homotopic to a constant map • f is homotopic to the identity, and f = rd for some d • f is homotopic to the flip map l, and f = rd ◦ l for some d The proof of Theorem 9.2 also demonstrated that all non-isomorphisms on Cn must be nullhomotopic. Thus all isomorphisms on Cn fall into the second and third categories above, and in fact all maps in those two categories are isomorphisms. Thus we obtain: Corollary 9.4. Let n > 4, and f : Cn → Cn be an isomorphism with f ' g for some g. Then g is an isomorphism. Now we are ready to compute the values of S(f) for our three classes of self-maps on Cn. Theorem 9.5. We have S(f) = {1} for every f : C1 → C1. When 1 < n ≤ 4, we have S(f) = {0, . . . ,n} for any f : Cn → Cn. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 105 L. Boxer and P. Christopher Staecker x0 x1 x4 x2 x3 x0 x1 x5 x2 x3 x4 Figure 4. The map f from Theorem 9.5 pictured in the cases n = 5 and n = 6. All points are fixed except those with arrows indicating where they map to. The path f(Cn) is in bold. When n > 4, let c be any constant map, id be the identity map, and l be the flip map on Cn. We have: S(id) = {0,n} S(c) = {0, 1, . . . ,bn/2c + 1} S(l) = { {0, 1} if n is odd {0, 2} if n is even Proof. When n = 1, our image is a single point, and the constant map (which is also the identity map) is the only continuous self-map. Thus S(f) = F(X) = {1} for every f : C1 → C1. When 1 < n ≤ 4, again all maps are homotopic, and we have S(f) = F(X) = {0, . . . ,n} for any f by Theorem 4.7. Now we consider Cn with n > 4, which is the interesting case. By Theorem 9.3 the only maps homotopic to id are rotation maps rd. Since # Fix(r0) = n and # Fix(rd) = 0 for d 6= 0, we have S(id) = {0,n}. Now we consider the constant map c(xi) = x0. Let f ∈ C(Cn) be defined as follows. f(xi) = { x−i for 0 ≤ i ≤bn/2c; xi for bn/2c < i < n. This map “folds” the cycle onto a path that is “about half” of the cycle, with bn/2c + 1 fixed points. See Figure 4. This can be taken as the first step of a homotopy, in which successive steps shrink the path and the number of fixed points by one per step, until a constant map is reached at the end of the homotopy. Thus {1, . . . ,bn/2c + 1} ⊆ S(c), and of course 0 ∈ S(c) also by Theorem 4.6. Thus we have shown there is a fixed path p between fixed points of f, xi,xj, of length at least bn/2c + 1. We wish to show that in fact S(c) = {0, . . . ,bn/2c + 1}. We show this by contradiction: take some nullhomotopic f, assume that k ∈ S(f) with k > bn/2c + 1, and we will show in fact that c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 106 Fixed point sets in digital topology, 1 Figure 5. An image having a self-map with X(f) = 0 all points are fixed; this would be a contradiction since f 6= id. Choose any x ∈ Cn\p. Then x lies on the unique shortest path in Cn from xi to xj. Then x ∈ Fix(f) by Lemma 8.4; this gives our desired contradiction. Finally we consider the flip map l(xi) = x−i. By Theorem 9.3, all maps homotopic to l have the form f(xi) = rd◦l(xi) = xd−i. Such a map has a fixed point at xi if and only if d = 2i (mod n). When d is odd there are no solutions, and so # Fix(f) = 0. When d is even, say d = 2a, and n is odd, there is one solution: i = a. When d is even and n is also even, there are two solutions: i = a and i = a + n/2. Thus we have some maps with no fixed points, and when k is odd we have some with one fixed point, and when k is even we have some with two. We conclude: S(l) = { {0, 1} if n is odd {0, 2} if n is even � By Theorem 9.2, any self-map on Cn is homotopic to the constant, identity, or flip. Thus by taking unions of the sets above, we have: Corollary 9.6. F(Cn) =   {1} if n = 1, {0, . . . ,n} if 1 < n ≤ 4, {0, 1, . . . ,bn/2c + 1,n} if n > 4. From the Corollary above we see that F(C5) = {0, 1, 2, 3, 5}, and thus the formula of Corollary 4.7 is exact for X = C5. This is the only example known to the authors in which this occurs. Question 9.7. Is there any digital image X 6= C5 with #X > 4 and F(X) = {0, 1, 2, 3, #X}? We conclude this section with two interesting examples showing the wide variety of fixed point sets that can be exhibited for other digital images. Tools we use in our discussion include the following. A path r : [0,m]Z → X that is an isomorphism onto r([0,m]Z) is a simple path. If a loop p is an isomorphism onto p(Cm), p is a simple loop. Definition 9.8 ([11]). A simple path or a simple loop in a digital image X has no right angles if no pair of consecutive edges of the path or loop belong to a loop of length 4 in X. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 107 L. Boxer and P. Christopher Staecker x x′ Figure 6. A lasso for the points x = (0, 1) and x′ = (0, 0) Figure 7. An image with many different values for S(f) Definition 9.9 ([11]). A lasso in X is a simple loop p : Cm → X and a path r : [0,k]Z → X such that k > 0, m ≥ 5, r(k) = p(x0), and neither p(x1) nor p(xm−1) is adjacent to r(k − 1). The lasso has no right angles if neither p nor r has a right angle, and no right angle is formed where r meets p, i.e., the final edge of r and neither of the edges of p at p(x0) form 2 edges of a loop of length 4 in X. Theorem 9.10 ([11]). Let X be an image in which, for any two adjacent points x ↔ x′ ∈ X, there is a lasso with no right angles having path r : [0,k]Z → X with r(0) = x and r(1) = x′. Then X is rigid. Example 9.11. Let X be the digital image X = ([0, 6]Z ×{0, 2}) ∪{(0, 1), (2, 1), (4, 1), (6, 1)} (see Figure 5), with 4-adjacency. By Theorem 9.10, this image is rigid. It is easy, though a bit tedious, to verify that the hypothesis of Theorem 9.10 is satisfied by X. For example, in Figure 6 we exhibit a lasso with no right angles for two adjacent points. It is easy to construct such lassos for any pair of adjacent points. Since X is rigid, we have S(id) = {#X} = {18}. Let f : X → X be the 180-degree rotation of X. Then f is an isomorphism, and so by Theorem 3.2, f = f ◦ idX is rigid. Thus S(f) = {# Fix(f)} = {0}. In particular this provides an example for the question posed in [10] if X(f) could ever equal 0 for a connected image. The following example demonstrates an image which has many different possible sets which can occur as S(f) for various self-maps f. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 108 Fixed point sets in digital topology, 1 Example 9.12. Let X = ([0, 5]Z ×{0, 2}) ∪{(0, 1), (2, 1), (5, 1)} (see Figure 7), with 4-adjacency. In this image we have several different homo- topy classes of maps. We will derive sufficient information about S for some of these to compute F(X). By Theorem 9.10, X is rigid, so S(id) = {#X} = {15}. Let f be a vertical reflection. Then f is rigid by Corollary 3.4, and has 3 fixed points, so S(f) = {3}. Let g be the function that maps the bottom horizontal bar onto the top one, and fixes all other points. Then g has 9 fixed points, and is homotopic to a constant map. We can retract the image of g down to a point one point at a time, and so {0, 1, . . . , 9}⊆ S(g). Let h be the function which maps the left vertical bar into the middle vertical bar and fixes all other points. Then h has 12 fixed points. We can addition- ally map one or both of the next two points into the middle vertical bar to obtain maps homotopic to h with 11 or 10 fixed points. We can do these re- tractions followed by a rotation around the 10-cycle on the right to obtain a map homotopic to h with no fixed points. Thus {0, 10, 11, 12}⊆ S(h). We have F(X)∩{13, 14} = ∅ by Proposition 5.3, since for all x ∈ X we see easily that P(x) ≥ 3. We therefore have F(X) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15}. 10. Further remarks We have studied several measures concerning the fixed point set of a con- tinuous self-map on a digital image. We anticipate further research in this area. Acknowledgements. We are grateful for the suggestions of an anonymous reviewer, and some careful corrections by Muhammad Sirajo Abdullahi and Jamilu Abubakar. References [1] C. Berge, Graphs and Hypergraphs, 2nd edition, North-Holland, Amsterdam, 1976. [2] L. Boxer, Digitally continuous functions, Pattern Recognition Letters 15 (1994), 833– 839. [3] L. Boxer, A classical construction for the digital fundamental group, Journal of Mathe- matical Imaging and Vision 10 (1999), 51–62. [4] L. Boxer, Continuous maps on digital simple closed curves, Applied Mathematics 1 (2010), 377–386. [5] L. Boxer, Generalized normal product adjacency in digital topology, Applied General Topology 18, no. 2 (2017), 401–427. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 109 L. Boxer and P. Christopher Staecker [6] L. Boxer, Alternate product adjacencies in digital topology, Applied General Topology 19, no. 1 (2018), 21–53. [7] L. Boxer, Fixed points and freezing sets in digital topology, Proceedings, 2019 Interdis- ciplinary Colloquium in Topology and its Applications, in Vigo, Spain; 55–61. [8] L. Boxer, O. Ege, I. Karaca, J. Lopez, and J. Louwsma, Digital fixed points, approximate fixed points, and universal functions, Applied General Topology 17, no. 2 (2016), 159– 172. [9] L. Boxer and I. Karaca, Fundamental groups for digital products, Advances and Appli- cations in Mathematical Sciences 11, no. 4 (2012), 161–180. [10] L. Boxer and P. C. Staecker, Remarks on fixed point assertions in digital topology, Applied General Topology 20, no. 1 (2019), 135–153. [11] J. Haarmann, M. P. Murphy, C. S. Peters and P. C. Staecker, Homotopy equivalence in finite digital images, Journal of Mathematical Imaging and Vision 53 (2015), 288–302. [12] B. Jiang, Lectures on Nielsen fixed point theory, Contemporary Mathematics 18 (1983). [13] E. Khalimsky, Motion, deformation, and homotopy in finite spaces, in Proceedings IEEE Intl. Conf. on Systems, Man, and Cybernetics (1987), 227–234. [14] A. Rosenfeld, ‘Continuous’ functions on digital pictures, Pattern Recognition Letters 4 (1986), 177–184. [15] P. C. Staecker, Some enumerations of binary digital images, arXiv:1502.06236, 2015. c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 1 110