PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 98(112) (2015), 45–51 DOI: 10.2298/PIM150404026S

THE SEMIRING VARIETY GENERATED BY ANY FINITE NUMBER OF FINITE FIELDS AND DISTRIBUTIVE LATTICES

Yong Shao, Miaomiao Ren, Siniša Crvenković, and Melanija Mitrović

Abstract. We study the semiring variety V generated by any finite number of finite fields F_{1}, …, F_{k} and two-element distributive lattice B_{2}, i.e., V = HSP{B_{2}, F_{1}, …, F_{k}}. It is proved that V is hereditarily finitely based, and that, up to isomorphism, B_{2} and all subfields of F_{1}, …, F_{k} are the only subdirectly irreducible semirings in V.

1. Introduction and preliminaries

Semirings are the natural generalization of rings and distributive lattices. Besides the two well-known examples of semirings: the set of nonnegative integers ℕ with the usual addition and multiplication as the most trivial one, and the first nontrivial example given by Dedekind [2] in connection with algebra of ideals of commutative ring, history of semirings date back, at least, to Vandiver [22]. The intensive study of semirings was initiated during the late 1960’s when their significant applications were found. Thus, nowadays, semirings have both a developed algebraic theory as well as important practical applications. More about applications of semiring theory within analysis, fuzzy set theory, the theory of discreteevent dynamical systems, automata and formal language theory can be found in the trilogy [4]–[6] and in [15]. Recently, new examples of applications of semiring constructions have been investigated in [11]–[14].

All semirings (S, +, ·) occurring in the literature satisfy at least the following axioms: (S, +), the additive reduct, and (S, ·), the multiplicative reduct of a semiring S are semigroups, and the multiplication distributes over addition from both sides, i.e., (SR1) x + (y + z) ≈ (x + y) + z; (SR2) x(yz) ≈ (xy)z; (SR3) x(y + z) ≈ xy + xz, (x + y)z ≈ xz + yz.

2010 Mathematics Subject Classification: Primary 16Y60, 08B05; Secondary 20M07.

Key words and phrases: finite field, distributive lattice, subdirectly irreducible, hereditarily finitely based, variety.

The first author is supported by the Natural Science Foundation of Shannxi Province, Grant 2015JQ1210. The third author is supported by the Ministry of Education, Science and Technological Development of Serbia, Grant 174018. The forth author is supported by the Ministry of Education, Science and Technological Development of Serbia, Grant 174026.

Communicated by Žarko Mijajlović.

It is, as well, often assumed that (S, +) is commutative, i.e.,

(SR4) x + y ≈ y + x. Note that the variety considered in the present paper satisfy this identity too.

Let S be a semiring. We can distinguish, in general, the following three subsets of idempotents (if there are any) of S: E(S)_{•} the set of all multiplicative idempotents of (S, ·); E(S)_{+} the set of all additive idempotents of (S, +), and E(S) = E(S)_{•} ∩ E(S)_{+} . A semiring S is idempotent if S = E(S), i.e., if it satisfies

x + x ≈ x ≈ x^{2}.

An idempotent semiring S is called a bisemilattice if both the additive and multiplicative reducts (S, +) and (S, ·) of S are semilattices. A distributive lattice is a bisemilattice which satisfies the absorption law

x + xy ≈ x.

The variety of all distributive lattices is denoted by D. The smallest nontrivial distributive lattice, the two-element boolean algebra B_{2}, given by

+ 0 1 0 0 1 1 1 1  \begin{matrix}· & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}

is the only subdirectly irreducible (moreover, B_{2} is congruence simple too) member of D and we have D = HSP{B_{2}}.

Kelarev in [9] described the ring variety generated by a finite number of finite fields with pairwise distinct characteristics and proved that such varieties are finitely based. Some of their properties, including the one that such a ring variety is arithmetical, are given in [18, 25]. Specially, in [10], it is proved that the ring variety generated by a finite ring is finitely based. Thus, in [23] the ring variety of square root rings is considered, and it is proved that it is generated by the finite field F_{2^{k}} . In [1] it is proved that the ring variety generated by a finite number of finite fields with pairwise distinct characteristics is finitely based and used in term rewriting. Shao and Ren in [20] proved that the semiring variety generated by distributive lattices and any finite number of prime fields are finitely based. In [21], it is proved that the semiring variety generated by a finite number of finite fields with pairwise distinct characteristics and distributive lattices are finitely based.

As we know, the “simplest” semiring variety generated by finite fields and distributive lattices is the the variety of Boolean semirings generated by B_{2} and the smallest nontrivial finite field Z_{2}, the field of integers modulo 2 or 2-element Boolean ring, given by

+ 0 1 0 0 1 1 1 0  \begin{matrix}· & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 . \end{matrix}

In [8] it is proved that this variety is finitely based, and it is equivalent to the category of partially Stone spaces. This motivates us to give a little progress in that direction.

The main subject here is the semiring variety V = HSP{B_{2}, F_{1}, …, F_{k}} generated by B_{2} and any finite number of finite fields F_{1}, …, F_{k}. In our consideration, we do not need that finite fields F_{1}, …, F_{k} have pairwise distinct characteristics. We prove that V = HSP{B_{2}, F_{1}, …, F_{k}} is hereditarily finitely based and characterize all subdirectly irreducible semirings in V. We refer to [4]–[6] as sources of references on semirings. For notions and terminology not given here, we refer to [16] as the background on finite fields, [17] on universal algebras, and [7, 19] for semigroup theory.

2. On the semiring variety V = HSP{B_{2}, F_{1}, …, F_{k}}

Let p_{1}, …, p_{k} be primes and q_{1} = p_{1}^{n_{1}} , …, q_{k} = p_{k}^{n_{k}} for some positive integers n_{1}, …, n_{k}. Assume that d is the least common multiple of p_{1}, …, p_{k} and that m is a positive integer such that m−1 is the product of q_{1} −1, …, q_{k} −1. Let W denote the variety of semirings defined by identities (SR1–4) and the following ones

(W1) (d + 1) · x ≈ x; (W2) x^{m} ≈ x; (W3) d · x^{2} ≈ d · x; (W4) x + d · xy ≈ x; (W5) xy ≈ yx. Let S be a semiring in W. We denote by E(S)_{+} the set of all idempotents of

the additive reduct (S, +) of S. By Theorems 1.1, 1.2, 2.1 and Lemma 2.1 in [21], we have

Theorem 2.1. Let S be a semiring in W. Then the following statements are true:

(i) E(S)_{+} = {d · a|a ∈ S}, and (E(S)_{+} , +, ·) is a distributive lattice; (ii) (S, +) is an E-unitary Clifford semigroup; (iii) If R is a subdirectly irreducible semiring in W, then R is two-element

distributive lattice or R is a finite field.

In this section we assume that F_{1}, …, F_{k} is any given finite number of finite fields with characteristics p_{1}, …, p_{k} and sizes q_{1}, …, q_{k}. In what follows the semiring variety V = HSP{B_{2}, F_{1}, …, F_{k}} will be considered.

It suffices to consider the following cases:

• V_{1} = HSP{B_{2}, F_{1}, …, F_{k}}, in which there exist at least two finite fields in {F_{1}, …, F_{k}} such that their characteristics are distinct.

• V_{2} = HSP{B_{2}, F_{1}, …, F_{k}}, in which F_{1}, …, F_{k} have the same characteristics. We firstly consider the variety V_{1}. Clearly, V_{1} satisfies (W1–5) so it is a

subvariety of W. We also have that B_{2} and finite fields F_{1}, …, F_{k} satisfy the following identities

(W6)  \frac{d}{p_{i}} · x^{q_{i}} ≈ \frac{d}{p_{i}} · x (1 ⩽ i ⩽ k),

which implies that V_{1} = HSP{B_{2}, F_{1}, …, F_{k}} satisfies (W1–6). In fact, we have

Theorem 2.2. Let V_{1} = HSP{B_{2}, F_{1}, …, F_{k}}. Then

(i) V_{1} is finitely based; (ii) if S is a subdirectly irreducible semiring in V_{1}, then S is isomorphic to B_{2}, or there exists a field F in {F_{1}, …, F_{k}} such that S is isomorphic to a subfield of F.

Proof. (i) Let V^{∗} be the variety of semirings defined by (SR1-4) and (W1-6). It is easy to see that V^{∗} is a subvariety of W and that V_{1} is a subvariety of V^{∗}. In what follows we will prove that V_{1} = V^{∗}.

Suppose that S is a subdirectly irreducible semiring in V^{∗}. It follows from Theorem 2.1 that S, up to isomorphism, is B_{2} or a finite field. If S is a finite field, then S satisfies the identity (W1). Thus, the characteristic of S is equal to some p_{i} (1 ⩽ i ⩽ k) since d is the least common multiple of p_{1}, …, p_{k}. Next, S satisfies

\frac{d}{p_{i}} · x^{q_{i}} = \frac{d}{p_{i}} · x, which implies that S satisfies x^{q_{i}} = x, so the size of S divides q_{i}.

Thus, up to isomorphism, S is a subfield of F_{i}. Since every subfield of F_{i} is in the variety V_{1} = HSP{B_{2}, F_{1}, …, F_{k}}, we have that S belongs to V_{1}. This shows that every subdirectly irreducible semiring of V^{∗} is in V_{1} and so V^{∗} ⊆ V_{1} and so V^{∗} = V_{1}. This shows that V_{1} is finitely based.

(ii) If S is a subdirectly irreducible semiring in V_{1}, then it follows directly from the proof of (i) that S is isomorphic to B_{2}, or there exists a field F in {F_{1}, …, F_{k}} such that S is isomorphic to a subfield of F. □

In general, V_{1} can be a proper subvariety of W. This can be shown by the following example.

Example 2.1. Let us consider the variety HSP{B_{2}, F_{3}, F_{2^{2}} , F_{2^{3}} , F_{7^{2}} } and the semiring variety W(2, 3, 7, 2017) defined by the additional identities

(1) x + 42 · x ≈ x; (3) 42 · x^{2} ≈ 42 · x; (5) xy ≈ yx.

(2) x^{2017} ≈ x; (4) x + 42 · xy ≈ x;

It is easy to see that HSP{B_{2}, F_{3}, F_{2^{2}} , F_{2^{3}} , F_{7^{2}} } satisfies identities (1)–(5). It is a routine matter to verify that F_{3^{2}} is in W(2, 3, 7, 2017). By Theorem 2.2 we have that F_{3^{2}} does not belong to HSP{B_{2}, F_{3}, F_{2^{2}} , F_{2^{3}} , F_{7^{2}} }. This implies that HSP{B_{2}, F_{3}, F_{2^{2}} , F_{2^{3}} , F_{7^{2}} } is a proper subvariety of W(2, 3, 7, 2017). This means that, for V_{1}, the identity (W6) is indispensable.

In the following we will discuss the variety V_{2} = HSP{B_{2}, F_{1}, …, F_{k}} generated by B_{2} and a finite number of finite fields with the same characteristic. Without loss of generality, we assume that there exists a prime p such that the characteristics of F_{1}, …, F_{k} are equal to p. Thus, there exist positive integers n_{1}, …, n_{k} such that |F_{i}| = p^{n_{i}} (1 ⩽ i ⩽ k).

Let n be a positive integer such that n−1 is the product of p^{n_{1}} −1, …, p^{n_{k}} −1. It is easy to verify that V_{2} satisfy (FSR1) (p + 1) · x ≈ x; (FSR2) x^{n} ≈ x; (FSR3) p · x^{2} ≈ p · x; (FSR4) x + p · xy ≈ x; (FSR5) x + (x^{p^{n_{1}}} + (p − 1) · x) …(x^{p^{n_{k}}} + (p − 1) · x) ≈ x ;

(W5) xy ≈ yx.

Thus we have

Theorem 2.3. Let V_{2} = HSP{B_{2}, F_{1}, …, F_{k}} be the variety generated by B_{2} and a finite number of finite fields with the same characteristic p. Then

(i) V_{2} is finitely based; (ii) if S is a subdirectly irreducible semiring in V_{2}, then S is isomorphic to B_{2}, or there exists a field F in {F_{1}, …, F_{k}} such that S is isomorphic to a subfield of F.

Proof. (i) We denote by V′ the variety of semirings defined by (SR1–4), (FSR1–5) and (W5). It is easy to see that V_{2} is a subvariety of V′. In what follows, we will prove that V_{2} = V′.

Suppose that S is a subdirectly irreducible semiring in V′. It follows from Theorem 2.1 that S, up to isomorphism, is B_{2} or a finite field. If S is a finite field, then S satisfies the identity (FSR1). This implies that the characteristic of S is equal to p. Since (S, +, ·) is a finite field, we denote by 0 and 1 the zero element and the identity of S, respectively. Thus we have that (S ∖ {0}, ·) is a cyclic group of a finite order. Without loss of generality, we suppose that (S∖{0}, ·) can be generated by the element a and the order of (S ∖ {0}, ·) is equal to q, i.e., |S ∖ {0}| = q. From (FSR5) we have that a + (a^{p_{1} ^{n_{1}}} + (p − 1) · a) …(a^{p_{k} ^{n_{k}}} + (p − 1) · a) = a. It follows that (a^{p^{n_{1}}} +(p−1)·a) …(a^{p^{n_{k}}} +(p−1)·a) = 0 since (S, +) is a group. Furthermore, there exists 1 ⩽ j ⩽ k such that a^{p^{n_{j}}} +(p−1)·a = 0 and so a^{p^{n_{j}}} +(p−1)·a+a = a. Since the characteristic of S is equal to p, a = a^{p^{n_{j}}} +(p−1)·a+a = a^{p^{n_{j}}} +p·a = a^{p^{n_{j}}} and so a^{p^{n_{j}} −1} = 1. This shows the size q of (S ∖ {0}, ·) divides p^{n_{j}} − 1 and so the size of S divides p^{n_{j}} . Thus, S is isomorphisic to the subfield of F_{j}. Since every subfield of F_{i} is in the variety V_{2} = HSP{B_{2}, F_{1}, …, F_{k}}, we have that S belongs to V_{2}. This shows that every subdirectly irreducible semiring of V′ is in V_{2} and so V′ = V_{2}. This means that V_{2} is finitely based.

(ii) If S is a subdirectly irreducible semiring in V_{2}, then it follows directly from the proof of (i) that S is isomorphic to B_{2}, or there exists a field F in {F_{1}, …, F_{k}} such that S is isomorphic to a subfield of F. □

In general, V_{2} can be a proper subvariety of W. For example, let us consider the variety HSP{B_{2}, F_{3^{3}} , F_{3^{5}} , F_{3^{7}} } and the semiring variety W(3, 13754313) defined by the additional identities

(1) 4 · x ≈ x; (3) 3 · x^{2} ≈ 3 · x; (5) xy ≈ yx.

(2) x^{13754313} ≈ x; (4) x + 3 · xy ≈ x;

It is easy to see that HSP{B_{2}, F_{3^{3}} , F_{3^{5}} , F_{3^{7}} } satisfies identities (1)–(5). It is routine to verify that F_{3^{2}} is in W(3, 13754313). By Theorem 2.3 it follows that F_{3^{2}} does not belong to the variety HSP{B_{2}, F_{3^{3}} , F_{3^{5}} , F_{3^{7}} }. This implies that HSP{B_{2}, F_{3^{3}} , F_{3^{5}} , F_{3^{7}} } is a proper subvariety of W(3, 13754313). This means that, for V_{2}, the identity (FSR5) is indispensable.

By Theorems 2.2 and 2.3, we can establish the following result:

Theorem 2.4. Let V be the variety generated by B_{2} and a finite number of finite fields {F_{1}, …, F_{k}}. Then

(i) V is finitely based; (ii) if S is a subdirectly irreducible semiring in V, then S is isomorphic to

B_{2}, or there exists a field F in {F_{1}, …, F_{k}} such that S is isomorphic to a subfield of F.

Theorem 2.4 extends and enriches the main results of [8]–[10], [20] and [21]. A variety is said to be hereditarily finitely based if every variety contained

in it is finitely based. In the rest of this section, we will show that the variety V considered in Theorem 2.4 is hereditarily finitely based. By Theorem 2.4 (ii) we immediately have that, up to isomorphism, there are finitely many subdirectly irreducible members in V. Let T denote the set of all subdirectly irreducible members in V. Since every subvariety of V is generated by a subset of T , it follows that the lattice of all subvarieties of V is finite. Let A ⊆ T . To show that HSP(A) is finitely based, we need only to consider the following cases:

• A = ∅. It is clear that HSP(A) is the trivial variety.

• A = {B_{2}}. HSP(A) = D is finitely based.

• A consists of B_{2} and a finite number of finite fields. Then, by Theorem 2.4(i) it follows that HSP(A) is finitely based.

• A consists of a finite number of finite fields. Without loss of generality, we assume that A = {F_{s_{1}} , …, F_{s_{t}} }, in which every finite field F_{s_{j}} is a subfield of some F_{i}. Let b the least common multiple of characteristics of F_{s_{1}} , …, F_{s_{t}} . It is easy to see that every finite field in {F_{s_{1}} , …, F_{s_{t}} } satisfies the identity b · x ≈ b · y, but B_{2} does not satisfy b · x ≈ b · y. Thus, HSP(A) is a subvariety of HSP(A ∪ {B_{2}}) determined by additional identity b · x ≈ b · y. Suppose that K is a subdirectly irreducible semiring in the subvariety HSP(A ∪ {B_{2}}) determined by additional identity b · x ≈ b · y. It follows by Theorem 2.4 (ii) that K is a subfield of some finite field in A and so K belongs to HSP(A). This shows that HSP(A) is the subvariety of HSP(A ∪ {B_{2}}) determined by additional identity b · x ≈ b · y. Hence, HSP(A) is finitely based.

From above it follows that every subvariety of V is finitely based. We now have

Theorem 2.5. The semiring variety generated by a two-element distributive lattice and any finite number of finite fields is hereditarily finitely based.

References

1. S. Burris, J. Lawrence, Term rewrite rules for finite fields, Int. J. Algebra Comput. 1(3) (1991), 353–369.

2. R. Dedekind, Über die Theorie derganzen algebraiscen Zahlen, Supplement XI to P. G. Lejeune Dirichlet: Vorlesung über Zahlentheorie 4, Aufl., Druck und Verlag, Braunschweig, 1894.

3. S. Ghosh, A Characterization of semirings which are subdirect product of a distributive lattice and a ring, Semigroup Forum 59 (1999), 106–120.

4. J. S. Golan, The theory of Semirings with Applications in Mathematics and Theoretical Computer Science, Pitman Monographs and Surveys in Pure Appl. Math., Longman Scientific and Technical, Harlow, 1992.

5. , Power Algebras over Semirings, Kluwer, Dordrecht, 1999.

6. , Semirings and Affine Equations over Them, Kluwer, Dordrecht, 2003.

7. J. M. Howie, Fundamentals of Semigroup Theory, Oxford Science Publication, Oxford, 1995.

8. F. Guzmán, The variety of Boolean semirings, J. Pure Appl. Algebra 78 (1992), 253–270.

9. A. V. Kelarev, Semigroup rings in semisimple varieties, Bull. Aust. Math. Soc. 57 (1998), 387–391.

10. R. L. Kruse, Identities satisfied by a finite ring, J. Algebra 26 (1973), 298–318.

11. D. Y. Gao, A. V. Kelarev, J. L. Yearwood, Optimization of matrix semirings for classification systems, Bull. Aust. Math. Soc. 84 (2011), 492–503.

12. J. Abawajy, A. V. Kelarev, J. L. Yearwood, C. Turville, A data mining application of the incidence semirings, Houston J. Math. 39(4) (2013), 1083–1093.

13. J. Abawajy, A. V. Kelarev, J. Zeleznikow, Optimization of classification and clustering systems based on Munn semirings, Semigroup Forum 87 (2013), 617–626.

14. J. Abawajy, A. V. Kelarev, M. Miller, J. Ryan, Incidence semirings of graphs and visible bases, Bull. Aust. Math. Soc. 89 (2014), 451–459.

15. W. Kuich, A. Salomaa, Semirings, Automata and Languages, EATCS Monographs on Theoretical Computer Science, Springer Verlag, Berlin, 1986.

16. R. Lidl, H. Niederreiter, Finite Fields, (2nd ed.), Cambridge University Press, 1997.

17. R. N. McKenzie, G. F. McNulty, W. F. Taylor, Algebras, Lattices, Varieties, 1, Monterey: Wadsworth and BrookdCole, 1987.

18. G. Michler, R. Wille, Die primitiven Klassen arithmetischer Ringe, Math. Z. 113 (1970), 369–372.

19. M. Petrich, Inverse Semigroups, Wiley, New York, 1984.

20. Y. Shao, M. M. Ren, The variety of semirings generated by distributive lattices and prime fields, J. Math. Res. Appl. 34(5) (2014), 529–534.

21. Y. Shao, S. Crvenkovi]’c, M. Mitrović, Variety generated by distributive lattices and finite fields, Publ. Inst. Math., Nouv. Sér. 95(109), (2014), 101–109.

22. H. S. Vandiver, Note on simple type of algebra in which cancellation law of addition does not hold, Bull. Am. Math. Soc. 40 (1934), 914–920.

23. J. P. D. Varela, Equivalence between varieties of square root rings and Boolean algebras with a distinguished automorphism, J. Algebra 299 (2006), 190–197.

24. B. M. Vernikov, Self-dual varieties of associative rings, Ural. Gos. Univ. Mat. Zap. 14 (1985), 31–37.

25. H. Werner, R. Wille, Charakterisierungen der primitiven Klassen arithmetischer Ringe. Math. Z. 115 (1970), 197–200.

School of Mathematics (Received 20 02 2015) Northwest University Xian, P. R. China

 yongshaomath@126.com
 miaomiaoren@yeah.net

Department of Mathematics and Informatics, University of Novi Sad, Serbia

 sima@eunet.rs

Faculty of Mechanical Engineering, University of Niš, Serbia

 meli@masfak.ni.ac.rs