New York Journal of Mathematics

New York J. Math. 14 (2008) 719–731.

Primitive words and spectral spaces

Othman Echi and Mongi Naimi

Abstract. In Bouacida–Echi–Salhi 1999 and 2000, it was shown that spectral spaces are related to foliation theory. In this paper, we prove that spectral sets and spaces are also related to the relatively new research topic combinatorics on words, an area in discrete mathematics motivated in part by computer science.

Let A be a finite alphabet, A^{∗} be the free monoid generated by A (i.e., the set of all finite words over A) and A^{+} be the set of nonempty words over A. A nonempty word is called primitive if it is not a proper power of another word. Let u be a nonempty word; then there exist a unique primitive word z and a unique integer k ≥ 1 such that u = z^{k}. The word z is called the primitive root of u and is denoted by z = p_{A}(u).

By a language over an alphabet A, we mean any subset of A^{∗}. A language will be called a primitive language if it contains the primitive root of all its elements.

The collection T := {O ⊆ A^{∗} | p−1_{A}(O) ⊆ O} defines a topology on A^{∗} (which will be called the topology of primitive languages).

Call a PL-space, each topological space X which is homeomorphic to A^{+} (equipped with the topology of primitive languages) for some finite alphabet A.

The main goal of this paper is to prove that the one-point compactification of a PL-space is a spectral space, providing a new class of spectral spaces in connection with combinatorics on words.

Contents

1. Introduction and notations 720 2. Words and Alexandroff spaces 721 3. Spectral sets and spaces 725 References 729

Received July 26, 2008. Mathematics Subject Classification. 54C05, 54F65, 68R05, 68R15, 54F05. Key words and phrases. Alexandroff space, Combinatorics on words, Free monoid, Ku-

ratowski closure, Primitive word, Spectral space. The first author is partially supported by the “DGRST: 03/UR/15-03”.

719^{ISSN 1076-9803/08}

1. Introduction and notations

By an alphabet we mean a finite nonempty set A. The elements of A are called letters of A. A finite word over an alphabet A is a finite sequence of elements of A. The set of all finite words is denoted by A^{∗}. The sequence of zero letters is called the empty word and denoted by ε_{A}. We will denote by A^{+} the set of all finite nonempty words. If u := u_{1} … u_{n} is a finite sequence of n letters, then n is called the length of the word u and we denote it by |u|. Let us denote by A^{n} the set of all finite words over A of length n. The concatenation of two words u := u_{1} … u_{n} and v := v_{1} … v_{m} of lengths respectively n and m is the word uv := u_{1} … u_{n}v_{1} … v_{m} of length n + m. The set A^{∗} equipped with the concatenation operation is a monoid with ε_{A} as a unit element. A power of a word u is a word of the form u^{k} for some k ∈ ℕ. It is convenient to set u^{0} = ε_{A}, for each word u. When k ∈ ℕ^{+} \ {1}, we say that u^{k} is a proper power of u (here and throughout the paper ℕ^{+} stands for the set of all positive natural numbers).

A word u is said to be a prefix (resp. suffix, resp. factor) of a word v if there exists a word t (resp. t, resp t and s) such that ut = v (resp. tu = v, resp. tus = v). If u = vt, then we set ut^{−1} := v or v^{−1}u := t. The prefix of length k of a word u will be denoted by pref_{k}(u).

A word is called primitive if it is nonempty and not a proper power of another word. The concept of primitive words plays a crucial role in combinatorial theory of words (see [24] and [23]).

Topology has proved to be an essential tool for certain aspects of theoretical computer science. Conversely, the problems that arise in the computational setting have provided new and interesting stimuli for topology. These problems also have increased the interaction between topology and related areas of mathematics such as order theory and topological algebra.

An Alexandroff space is a topological space in which any intersection of open sets is open. These spaces were first introduced by Alexandroff in 1937 [1] with the name of Diskrete Räume. In [28], Steiner has called Alexandroff spaces principal spaces. Topologically, Alexandroff spaces play an important role in the study of the structure of the lattice of topologies on a given set [28]: the lattice of topologies on any set is complemented; moreover, each topology has an Alexandroff topology complement.

It is worth noting that the interest in Alexandroff spaces was a consequence of the very important role of finite spaces in digital topology and the fact that these spaces have all the properties of finite spaces relevant for such theory.

It is, also, worth noting that Alexandroff T_{0}-spaces have been studied as discrete models of continuous spaces in theoretical physics ([15] and [27]).

Recently, Alexandroff topologies proved to be useful for some authors in providing examples and counterexamples in several papers dealing with topology or foliation theory (see for instance [7], [5], [6], and [11]).

Let X be a set. Recall that a map μ : 2^{X} ⟶ 2^{X} is said to be a Kuratowski closure on X, if it satisfies the following properties:

(1) μ(∅) = ∅.

(2) A ⊆ μ(A), for each A ∈ 2^{X}.

(3) μ(μ(A)) = μ(A), for each A ∈ 2^{X}.

(4) μ(A ∪ B) = μ(A) ∪ μ(B), for each A, B ∈ 2^{X}.

It is a part of the folklore of general topology that each topology T on a set X defines a Kuratowski closure (A ⟼ A); and conversely, for each Kuratowski closure μ : 2^{X} ⟶ 2^{X}, there is a unique topology on X such that μ(A) = A, for each A ∈ 2^{X}.

If A is an alphabet, then the map μ_{A} : 2^{A^{∗}} ⟶ 2^{A^{∗}}, defined by μ_{A}(L) = L ∪ p_{A}(L) is a Kuratowski closure defining an Alexandroff topology on A^{∗}.

The topology defined previously will be called the topology of primitive languages on A^{∗} (PL-topology, for short) and we denote it by PL(A) (in other words, the PL-topology is the topology which has primitive languages as closed sets).

Call a PL-space, each topological space X which is homeomorphic to A^{+} (equipped with the topology of primitive languages) for some alphabet A.

Let X be a topological space, set X̃ = X ∪ {∞} with the topology whose members are the open subsets of X and all subsets U of X̃ such that X̃ \ U is a closed compact subset of X. The space X̃ is called the Alexandroff extension of X (or the one point compactification of X).

The main goal of this paper is to prove that the one-point compactification of a PL-space is a spectral space, providing a new class of spectral spaces in connection with combinatorics on words (a relatively new research topic in discrete mathematics, mainly, but not only, motivated by computer science).

In order to make this paper as self contained as possible, Section 2 will contain material about words and Alexandroff spaces which is needed throughout.

2. Words and Alexandroff spaces

We begin by recalling some preliminary results.

Lemma 2.1 (Lyndon–Schutzenberger [25]). Let u, v ∈ A^{∗} with uv = vu. Then there exists a word t such that u, v ∈ t^{∗} := {t^{n} | n ∈ ℕ}.

Lemma 2.2 (Lyndon–Schutzenberger [25]). Let u ∈ A^{+}. Then there exists a unique primitive word z and a unique integer k ≥ 1 such that u = z^{k}.

Notations 2.3. Let u ∈ A^{+}. By Lemma 2.2, there exists a unique primitive word z and a unique integer k ≥ 1 such that u = z^{k}.

− The word z is called the primitive root of u and is denoted by z =

p_{A}(u). − The integer k is called the exponent of u and is denoted by k = 𝔢(u).

Let Pr(n, k) be the number of primitive words of length n over a nonempty alphabet A of size k. In [29], Wang has counted the number Pr(n, k) by using an inclusion/exclusion argument; this count is usually performed by using Möbius transformations.

Let us recall — see for instance [23] — that we have

Pr(n, k) = ∑_{d|n}k^{d}μ (\frac{n}{d}) ,

where μ is the Möbius function.

It follows that if the alphabet A is not a singleton, then there are infinitely many primitive words over A. This fact will be used extensively in the present paper.

Now we give some elementary properties of the PL-topology. Note that a systematic study of PL-topologies has been done by Bouallègue–Echi–Naimi in [8].

Let us, first, recall some concepts. Given a poset (X, ≤) and x ∈ X, the generization of x in X is (↓ x) = {y ∈ X | y ≤ x}, the specialization of x in X is (x ↑) = {y ∈ X | y ≥ x}. Let X have a topology T and a partial ordering ≤. We say that T is compatible with ≤ if \overline{\{x\}} = (x ↑) for all x ∈ X.

Let (X, T ) be a T_{0}-space. Then X has a partial ordering ≤ induced by T by defining x ≤ y if and only if y ∈ \overline{\{x\}}.

Let X be a topological space. Recall that X is said to be a submaximal space if each dense subset of X is open [9]. According to Kelley [18], a topological space X is said to be a door space if every subset of X is either closed or open. Thus, clearly, every door space is a submaximal space. The converse does not hold.

Let (X, T ) be a T_{0}-space and ≤ be the ordering induced by T . A chain x_{0} < x_{1} < ⋯ < x_{n} of elements of X is said to be of length n; the supremum of the lengths is called the Krull dimension of (X, T ), which we write as dim_{K}(X, T ).

Let us recall a characterization of submaximal Alexandroff spaces due to Bezhanishvili et al [4].

Proposition 2.4 ([4, Proposition 4.1]). Let (X, T ) be an Alexandroff T_{0}- space. Then the following statements are equivalent.

(i) X is submaximal; (ii) dim_{K}(X, T ) ≤ 1.

Recall that, according to [13], a space X is said to a quasi-Hausdorff space if for each distinct points x, y ∈ X, either there exists z ∈ X such that x, y ∈ \overline{\{z\}}, or x and y have disjoint neighborhoods. A space X is said to be a T_{\frac{1}{2}} -space if each point of X is either closed or open.

The following result sheds light on the PL-topology and provides a class of submaximal spaces which are not door.

Proposition 2.5. Let A be an alphabet. We equip A^{∗} by its PL-topology. Then the following properties hold.

(1) If u ∈ A^{+} is a primitive word, then u is a closed point and the smallest open set containing u is V_{A}(u) := {u^{n} : n ∈ ℕ^{+}}.

(2) If u ∈ A^{+} is not a primitive word, then u is an open point and

\overline{\{u\}} = \{u, p_{A}(u)\}.

(3) ε_{A} is the unique clopen point of A^{∗} (clopen:= closed and open).

(4) dim_{K}(A^{∗}) = 1.

(5) A^{∗} is a T_{\frac{1}{2}} -space.

(6) A^{∗} is a submaximal space. In addition, A^{∗} is a door space if and only if A is a singleton.

(7) A^{∗} is quasi-Hausdorff.

Proof. Let us, first, note that \overline{\{ε_{A}\}} = \{ε_{A}\} and A^{∗} \ \{ε_{A}\} = A^{+} = μ(A^{+}). Consequently, ε_{A} is a clopen point of A^{∗}.

(1) Since A^{∗} is an Alexandroff space, the smallest open set containing a word u is V_{A}(u) = \{v ∈ A^{∗} : u ∈ \overline{\{v\}}\} = \{v ∈ A^{∗} : u ∈ \{v, p_{A}(v)\}\}.

If u ∈ A^{+} is a primitive word and v ∈ V_{A}(u), then u = v or u = p_{A}(v). By Lemma 2.2, there exists a unique n ∈ ℕ^{+} such that v = u^{n}.

Conversely, if v ∈ {u^{n} : n ∈ ℕ^{+}}, then p_{A}(v) = u (by Lemma 2.2) and thus u ∈ \overline{\{v\}}, proving that v ∈ V_{A}(u). Also, it is clear that u is a closed point of A^{∗}.

(2) Suppose that u ∈ A^{+} is not a primitive word. Let v ∈ V_{A}(u). Then u ∈ \overline{\{v\}}. Hence v ≠ ε_{A}, and p_{A}(v) is a primitive word. So u ∈ \{v, p_{A}(v)\} and accordingly u = v (since u is not primitive). It follows that V_{A}(u) = {u}; therefore u is an open point.

(3) Let u ∈ A^{+}. − If u is a primitive word, then V_{A}(u) = {u^{n} : n ∈ ℕ} ≠ {u}. This

implies that u is not an open point. − If u is not primitive, then \overline{\{u\}} = \{u, p_{A}(u)\} ≠ \{u\}; and thus u is not

a closed point.

(4) and (5) These properties follow immediately from (1), (2).

(6) The fact that A^{∗} is a submaximal space follows immediately from Proposition 2.4.

Now, we will check when A^{∗} is a door space. Two cases are to be considered.

Case 1. Suppose that A is a singleton (say A = {a}). Then a is the unique primitive word over A. Let S be a nonempty subset of A^{∗}.

− If a ∈ S, then A^{∗} \ S contains only nonprimitive words. Hence A^{∗} \ S

is an open set, by (2). Thus S is a closed set. − If a ∉ S, then a ∈ A^{∗} \ S and thus S = A^{∗} \ (A^{∗} \ S) is an open set.

So in this case A^{∗} is a door space.

Case 2. Suppose that A contains more than one element. Then there are infinitely many primitive words over A. Let u ∈ A^{+} be a primitive word and v a nonprimitive word with primitive root distinct from u. Then the subset S := {u, v} is neither closed (p_{A}(v) ∉ S) nor open (V_{A}(u) = {u^{n} : n ∈ ℕ^{+}} ⊈ S). We conclude that A^{∗} is not a door space.

(7) Let u, v be two distinct words over A. We consider three cases.

Case 1. Suppose that one of the two words is empty. Say, for instance, u = ε_{A}. Then {ε_{A}} and V_{A}(p_{A}(v)) are disjoint neighborhoods for u, v.

Case 2. Suppose that neither u nor v is primitive; then {u} and {v} are disjoint neighborhoods for u, v.

Case 3. Suppose that u and v are nonempty words and one of them is primitive (say for example u is a primitive word). Two subcases have, also, to be considered.

− If p_{A}(u) ≠ p_{A}(v). Then V_{A}(p_{A}(u)) and V_{A}(p_{A}(v)) are disjoint neigh-

borhoods, respectively, of u and v. − If p_{A}(u) = p_{A}(v), then u, v ∈ \overline{\{v\}} = \{u, v\}. Therefore, A^{∗} is a quasi-Hausdorff space. □

Let ≤ be an ordering on a set X. A subset Y of X is said to be leftdirected in (X, ≤) if for each x, y ∈ Y, there is some z ∈ Y such that z ≤ x and z ≤ y.

Recall that a subspace Y of a topological space X is said to be irreducible if any two nonempty open sets of Y meet. It is worth noting that Y is irreducible if and only if Y is irreducible.

Let (X, T ) be a T_{0}-space and ≤ be the ordering induced by the topology T . If Y is a left-directed subset of X, then Y is irreducible in (X, T ).

Now, suppose that (X, T ) is an Alexandroff space; then a subset Y ⊆ X is irreducible if and only if Y is left-directed (see Hoffman [14, Lemma 1.1]).

A T_{0}-space X is said to be sober if each nonempty irreducible closed subset C of X has a generic point (that is, there exists a ∈ C such that C = \overline{\{a\}}).

The following result gives a complete characterization of Alexandroff sober spaces.

Theorem 2.6. Let X be an Alexandroff T_{0}-space and ≤ be the ordering induced by the topology of X. Then the following statements are equivalent:

(1) X is a sober space.

(2) Each decreasing sequence of (X, ≤) is stationary.

Proof. (1) ⟹ (2) First, let us show that if Y is an irreducible subset of X, then Y has an infimum.

Indeed, since Y is an irreducible closed set of X, it has a generic point a; \overline{\{a\}} = Y. Thus a ≤ y, for each y ∈ Y. On the other hand, if z ∈ X is such that z ≤ y, for each y ∈ Y, then Y ⊆ \overline{\{z\}}. Therefore, Y ⊆ \overline{\{z\}}; and consequently, z ≤ a; proving that a is an infimum of Y.

Let (x_{n})_{n∈ℕ} be a decreasing sequence of (X, ≤). Since Y = {x_{n} | n ∈ ℕ} is left-directed, then Y is an irreducible subset of X and consequently, it has an infimum a in Y, by the previous comment; so that \overline{\{a\}} = Y.

But (↓ a) is an open subset of X containing a, this yields (↓ a) ∩ Y ≠ ∅. Hence there is p ∈ ℕ such that x_{p} ∈ (↓ a). Therefore,

x_{n} ≤ x_{p} ≤ a ≤ x_{n} ≤ x_{p}

for each n ≥ p, proving that the sequence (x_{n})_{n∈ℕ} is stationary.

(2)⟹(1) Let C be an irreducible closed subset of X. Suppose that C has no generic point. Pick x_{0} ∈ C. Then \overline{\{x_{0}\}} ⊆ C; so that there is y_{0} ∈ C such that y_{0} ∉ \overline{\{x_{0}\}}; consequently, \overline{\{x_{0}\}} ∪ \overline{\{y_{0}\}} ⊆ C. Since C is left-directed [14, Lemma 1.1], there is x_{1} ∈ C such that x_{1} ≤ x_{0} and x_{1} ≤ y_{0}.

Necessarily, x_{0} ≰ x_{1}; if not \overline{\{x_{0}\}} = \overline{\{x_{1}\}} and thus y_{0} ∈ \overline{\{x_{1}\}} = \overline{\{x_{0}\}}, a contradiction. One may do the same thing for x_{1} ∈ C in order to get x_{2} ∈ C such that x_{2} ≤ x_{1} and x_{1} ≰ x_{2} etc … This procedure provides a decreasing sequence (x_{n})_{n∈ℕ} of elements of C which is not stationary, a contradiction. It follows that C has a generic point. □

Remark 2.7. The assertion that if Y is an irreducible subset of a sober space X then Y has an infimum is proved in the Johnstone’s book Stone spaces [16] (it is a part of the proof of [16, Lemma I.1.9]).

3. Spectral sets and spaces

A topology T on a set X is said to be spectral [13] if and only if the following axioms hold:

(1) T is sober (that is, every nonempty irreducible closed subset of X is the closure of a unique point).

(2) (X, T ) is compact.

(3) The compact open subsets of X form a basis of T .

(4) The family of compact open subsets of X is closed under finite intersections.

In lattice theory, a spectral space is showed to be homeomorphic to the prime spectrum of a bounded (with 0 and 1) distributive lattice.

Let Spec(R) denote the set of prime ideals of a commutative ring R with identity, ordered by inclusion, and call a partial ordered set spectral if it is order isomorphic to Spec(R) for some ring R [22]. Such spectral sets are of interest not only in (topological) ring and lattice theory, but also in computer science, in particular, in domain theory (introduced in 1970 by Dana Scott as a mathematical theory of computation for the semantics of programming languages [26]).

Although many results about spectral sets have been obtained by Dobbs, Hochster, Fontana, Lewis, Ohm and Kaplansky (see for instance, [10], [12], [13], [17], [21] and [22]), a complete algebraic characterization of spectral sets still seems very far off.

Recall that if R is a ring, then the Zariski topology (the hull kernel topology) for Spec(R) is defined by letting C ⊆ Spec(R) be closed if and only if there exists an ideal A of R such that C = {P ∈ Spec(R) | P ⊇ A}.

In the remarkable paper [13], Hochster has proved that spectral spaces are exactly topological spaces homeomorphic to the prime spectrum of a ring equipped with the Zariski topology.

One can, obviously, see that (X, ≤) is spectral if and only if there exists an order compatible spectral topology on X.

By an Alexandroff-spectral space (A-spectral space, for short), we mean a topological space such that its one-point compactification (Alexandroff compactification) is a spectral space [3].

Before recalling the main result of [3], let us rewrite [3, Definition 1.5]; but with a slight change as done in [11].

Definitions 3.1. Let X be a topological space and U a subset of X.

(1) U is said to be intersection compact open, or ICO, if for each compact open subset O of X, U ∩ O is compact.

(2) U is said to be intersection compact closed, or ICC, if for each compact closed subset O of X, U ∩ O is compact.

(3) U is said to be intersection compact open closed, or ICOC, if it is ICO and ICC.

(4) Let P be a property. U is said to be co-P if X \ U satisfies P.

A complete characterization of A-spectral spaces has been given by Belaid–Echi–Gargouri.

Theorem 3.2 ([3]). A space X is A-spectral if and only if the following axioms hold.

(1) (X, T ) is a sober space.

(2) X has a basis of compact open sets which is closed under finite intersections.

(3) For each compact closed subset C of X, there exists a co-compact ICOC open subset O of X such that O ⊆ X \ C.

An up-spectral space is defined to be a topological space satisfying the axioms of a spectral space with the exception that X is not necessarily compact [2]. Up-spectral spaces have been introduced and studied by Belaid and Echi [2], in order to give some substantial information on a conjecture about spectral sets raised by Lewis and Ohm in 1976 [22].

Using [3, Theorem 2.2], it is clear that an A-spectral space is up-spectral. A natural question is whether an up-spectral space is necessarily A-spectral?

The above question has been answered by Echi and Gargouri in [11]. Next, we recall a concept introduced in [11].

Definition 3.3 ([11]). Let X be a topological space and U a subset of X. Call U a T -subset of X, if U is a closed compact co-ICO subset of X.

Recall that a link between up-spectral spaces and A-spectral space has been given by Echi and Gargouri as follows.

Theorem 3.4 ([11, Theorem 1.8]). Let X be a topological space. Then the following statements are equivalent:

(1) X is A-spectral;

(2) X satisfies the following properties:

(i) X is up-spectral.

(ii) For each compact closed subset C of X, there exists a T -subset D of X such that C ⊆ D.

Now we are in a position to state the main result of this paper.

Theorem 3.5. Let (X, T ) be a PL-space and ≤ be the ordering defined on X by: u ≤ v if and only if v ∈ \overline{\{u\}}. Then the following properties hold.

(1) (X, ≤) is a spectral set.

(2) (X, T ) is an up-spectral space.

(3) (X, T ) is spectral if and only if X has a unique closed point (in other words, any alphabet associated to X is a singleton).

(4) (X, T ) is an A-spectral space.

Proof. One may suppose without loss of generality that X = A^{+} (equipped with the topology of primitive languages), for some finite alphabet A.

(1) Let Prim(A) be the set of all primitive words over A. For u ∈ Prim(A), we let X_{u} be the set {u^{n} | n ∈ ℕ^{+}}. Then

X = ⋃_{u∈Prim(A)} X_{u}

is an ordered disjoint union, where the ordering on X_{u} is defined by u^{n} ≤ u^{m} if and only if n = m or m = 1.

By [22, Teorem 4.1], in order to prove that (X, ≤) is spectral, it is enough to show that (X_{u}, ≤) is spectral, for each u ∈ Prim(A). But this is an immediate consequence of the characterization of L(eft)-spectral spaces done by Dobbs–Fontana–Papick in [10]. Therefore, (X, ≤) is a spectral set.

(2)

− (X, T ) is a sober space.

This follows immediately from Proposition 2.5(4) and Theorem 2.6. − (X, T ) has a basis of compact open sets which is closed under finite

intersections.

It is easily seen that B := {V_{A}(u) | u ∈ A^{∗}} ∪ {∅} is a basis of compact open sets; and for each two words u, v ∈ A^{∗}, the two sets V_{A}(u) and V_{A}(v) are comparable or do not meet.

(3) According to (2), X is spectral if and only if it is compact.

− If A is not a singleton, then there are infinitely many primitive words. Hence

X := ⋃_{u∈Prim(A)} V_{A}(u)

is an open covering of X which has no finite subcover. Thus X is not compact.

− Now, if A is a singleton (say for example A = {a}), then the unique closed point (the unique primitive word) of A^{∗} is the word a. In this case, X = V_{A}(a); and thus X is compact.

(4) To prove that X is A-spectral, let us use Theorem 3.2. Since X is up-spectral, it is enough to show that (X, T ) satisfies Condition (3) of Theorem 3.2.

Let C be a compact closed set of X. Then there exist finitely many primitive words p_{1}, p_{2}, …, p_{n} over A such that

C ⊆ V_{A}(p_{1}) ∪ V_{A}(p_{2}) ∪ … V_{A}(p_{n}).

Set

O := ⋃_{u∈Prim(A)\{p_{1},p_{2},...,p_{n}}} V_{A}(u);

then, clearly, O is a clopen set of X. It is easy to check that each closed set of a topological space is ICOC. Thus O is a co-compact ICOC open subset of X such that O ⊆ X \ C.

Therefore, (X, T ) is an A-spectral space. □

Next, we give an example a topological space satisfying Properties (1),

(2) of Theorem 3.5 and Conditions (4), (5), (6) of Proposition 2.5 which is not a PL-space.

First, let us recall that the study of the geometric and topological properties of digital images is the goal of digital topology. In the process of digitizing a movie, some situations are often represented by subspaces and quotients of locally finite topological spaces, so the study of these topological spaces is important. The digital line, also known as the Khalimsky line, is the major building bloc of the digital n-space. The Khalimsky line is the set of the integers ℤ, equipped with the topology K, generated by the subbase G_{K} = {{2n − 1, 2n, 2n + 1} | n ∈ ℤ} [19], [20]. Hence a set U ⊆ ℤ is open in K if and only if whenever x ∈ U is an even integer, then x − 1, x + 1 ∈ U.

Example 3.6. The Khalimsky line (ℤ, K) satisfies the following properties:

(1) K is an Alexandroff topology.

(2) \overline{\{2n\}} = \{2n\} and \overline{\{2n + 1\}} = \{2n, 2n + 1, 2n + 2\}, for each n ∈ ℤ. Let ≤_{K} be the ordering induced by the Khalimsky topology. Then the ordered set (ℤ, ≤_{K}) is a 1-dimensional poset which looks like

[figure: …; •^{2n}; •^{2(n+1)}; …; …; •^{2n+1}; …]

(3) For each n ∈ ℤ, {2n} is closed and {2n + 1} is open in (ℤ, K). Thus (ℤ, K) is a T_{\frac{1}{2}} -space.

(4) (ℤ, K) is a submaximal space.

(5) K is a quasi-Hausdorff topology.

(6) (ℤ, ≤_{K}) is a spectral set.

(7) (ℤ, K) is a noncompact A-spectral space.

(8) (ℤ, K) is not a PL-space.

Proof. Clearly, Properties (1), (2), (3) and (5) are straightforward.

(4) This property follows immediately from Proposition 2.4 and the fact that the digital line is 1-dimensional.

(6) Let X_{1} be the set of elements of height 1 and X_{0} the set of elements of height 0. Since for each x ∈ X_{0}, (x ↑) ∩ (y ↑) = ∅, for all but finitely many y ∈ X_{0}, and also for each x ∈ X_{1}, (↓ x) ∩ (↓ y) = ∅, for all but finitely many y ∈ X_{1}, the poset (ℤ, ≤_{K}) is spectral, by [22, Corollary 5.10].

(7) Of course, ((↓ 2n), n ∈ ℤ) is an open covering of ℤ which has no finite subcovering. Thus (ℤ, K) is not compact.

− The fact that the digital line is 1-dimensional implies that it is a sober

space (by Theorem 2.6). − The collection B := {(↓ x) | x ∈ ℤ} ∪ {∅} is a basis of compact open

sets of the digital line, which is closed under finite intersections. − It is easily seen that compact subsets of the digital line are exactly

finite sets (since (↓ x) is finite, for each x ∈ ℤ). Thus each subset of ℤ is ICOC. It follows that Condition (3) of Theorem 3.2 is satisfied.

Therefore, (ℤ, K) is A-spectral.

(8) If X = A^{+} for some alphabet A, then for each primitive word u over A, V_{A}(u) = (↓ u) is an infinitely countable set. But, for the digital line, the set (↓ x) has cardinality 1 or 3, for each x ∈ ℤ. It follows that the digital line is not a PL-space. □

Acknowledgement. The authors gratefully acknowledge helpful comments and suggestions of the anonymous referee.

References

[1] Alexandroff, P. Diskrete Räume. Mat. Sb.(N.S.)2 (1937) 501–518. Zbl 0018.09105.

[2] Belaid, Karim; Echi, Othman. On a conjecture about spectral sets. Topology Appl. 139 (2004) 1–15. MR2051093 (2004m:06015), Zbl 1048.06003.

[3] Belaid, Karim; Echi, Othman; Gargouri, Riyadh. A-spectral spaces. Topology Appl. 138 (2004) 315–322. MR2035489 (2004k:54042), Zbl 1041.54028.

730 Othman Echi and Mongi Naimi

[4] Bezhanishvili, Guram; Esakia, Leo; Gabelaia, David. Some results on modal axiomatization and definability for topological spaces. Studia Logica 81 (2005) 325– 355. MR2195500 (2006j:03021).

[5] Bouacida, Ezzeddine; Echi, Othman; Salhi, Ezzeddine. Feuilletages et topologie spectrale. J. Math. Soc. Japan 52 (2000) 447–465. MR1742794 (2000m:57041), Zbl 0965.57025.

[6] Bouacida, Ezzeddine; Echi, Othman; Salhi, Ezzeddine. Foliations, spectral topology, and special morphisms. Advances in commutative ring theory (Fez, 1997), 111–132. Lecture Notes in Pure and Appl. Math., 205, Dekker, New York, 1999. MR1767454 (2001e:57030), Zbl 0957.57017.

[7] Bouacida, Ezzeddine; Echi, Othman; Salhi, Ezzeddine. Topologies associées à une relation binaire et relation binaire spectrale. Boll. Un. Mat. Ital. B (7) 10 (1996) 417–439. MR1397356 (97c:54008), Zbl 0865.54032.

[8] Bouallègue, S.; Echi, O.; Naimi, M. The topology of primitive languages. Submitted for publication.

[9] Bourbaki, Nicolas. General topology: Chapters 1–4, Translated from the French. Reprint of the 1989 English translation. Elements of Mathematics (Berlin). Springer-Verlag, Berlin, 1998. vii+437 pp. ISBN: 3-540-64241-2. MR1726779 (2000h:54001a), Zbl 0894.54001.

[10] Dobbs, David E.; Fontana, Marco; Papick, Ira J. On certain distinguished spectral sets. Ann. Mat. Pura Appl. 128 (1981) 227–240. MR0640784 (84b:13006), Zbl 0472.54021.

[11] Echi, Othman; Gargouri, Riyadh. An up-spectral space need not be A-spectral. New York J. Math. 10 (2004) 271–277. MR2114790 (2005j:06007).

[12] Fontana, Marco. Quelques nouveaux résultats sur une classe d’espaces spectraux. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur.(8) 67 (1979) 157–161. MR0622786 (82j:06024), Zbl 0461.13002.

[13] Hochster, M. Prime ideal structure in commutative rings. Trans. Amer. Math. Soc. 142 (1969) 43–60. MR0251026 (40 #4257), Zbl 0184.29401.

[14] Hoffmann, Rudolf-E. Topological spaces admitting a “dual”. Categorical topology (Proc. Internat. Conf., Free Univ. Berlin, Berlin, 1978), 157–166. Lecture Notes in Math, 719. Springer, Berlin, 1979. MR0544641 (80j:54001), Zbl 0413.54001.

[15] Ivashchenko, A. V. Dimension of molecular spaces. VINITI, Moscow, 6422–84, 1985, 3–11.

[16] Johnstone, Peter T. Stone spaces. Cambridge Studies in Advanced Mathematics, 3. Cambridge University Press, Cambridge, 1982. xxi+370 pp. ISBN: 0-521-23893-5. MR0698074 (85f:54002), Zbl 0499.54001.

[17] Kaplansky, Irving. Commutative rings. Revised edition. The University of Chicago Press, Chicago-London, 1974. ix+182 pp MR0345945 (49 #10674), Zbl 0296.13001.

[18] Kelley, John L. General topology. Reprint of the 1955 edition [Van Nostrand, Toronto, Ont.]. Graduate Texts in Mathematics, 27. Springer-Verlag, New York-Berlin, 1975. xiv+298 pp. MR0370454 (51 #6681), Zbl 0306.54002.

[19] Khalimsky, Efim; Kopperman, Ralph; Meyer, Paul R. Computer graphics and connected topologies on finite ordered sets. Topology Appl. 36 (1990) 1–17. MR1062180 (92c:54037), Zbl 0709.54017.

[20] Kong, T. Yung; Kopperman, Ralph; Meyer, Paul R. A topological approach to digital topology. Amer. Math. Monthly 98 (1991) 901–917. MR1137537 (93b:68092), Zbl 0761.54036.

[21] Lewis, William J. The spectrum of a ring as a partially ordered set. J. Algebra 25 (1973) 419–434. MR0314811 (47 #3361), MR0266.13010.

[22] Lewis, William J.; Ohm, Jack. The ordering of spec R. Canad. J. Math. 28 (1976) 820–835. Zbl 0313.13003.

Primitive words and spectral spaces 731

[23] Lothaire, M. Combinatorics on words. With a foreword by Roger Lyndon and a preface by Dominique Perrin. Corrected reprint of the 1983 original, with a new preface by Perrin. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. xviii+238 pp. ISBN: 0-521-59924-5. MR1475463 (98g:68134), Zbl 0874.20040.

[24] Lothaire, M. Algebraic combinatorics on words. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski. With a preface by Berstel and Perrin. Encyclopedia of Mathematics and its Applications, 90. Cambridge University Press, Cambridge, 2002. xiv+504 pp. ISBN: 0-521-81220-8. MR1905123 (2003i:68115), Zbl 1001.68093.

[25] Lyndon, R. C.; Schützenberger, M. P. The equation a^{M} = b^{N}c^{P} in a free group Michigan Math. J. 9 (1962) 289–298. MR0162838 (29 #142), Zbl 0106.02204.

[26] Scott, D. S. Outline of a mathematical theory of computation. 4th annual Princeton conference on information sciences and systems, 1970, 169–176.

[27] Sorkin, Rafael D. Finitary substitute for continuous topology. Internat. J. Theoret. Phys. 30 (1991) 923–947. MR1116893 (92g:83026).

[28] Steiner, A. K. The lattice of topologies: structure and complementation. Trans. Amer. Math. Soc. 122 (1966), 379–398. MR0190893 (32 #8303), Zbl 0139.15905.

[29] Wang, Lijun. Count of primitive words. Appl. Math, J. Chinese Univ. Ser. B 16 (2001) 339–344. MR1853942 (2002j:68081), Zbl 1024.68075.

Department of Mathematics, Faculty of Sciences of Tunis. University Tunis-El Manar. “Campus Universitaire” 2092 El Manar, Tunis othechi@yahoo.com othechi@math.com

mongi.naimi@fst.rnu.tn

This paper is available via http://nyjm.albany.edu/j/2008/14-30.html.