PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 92(106) (2012), 35–41 DOI: 10.2298/PIM1206035L

DIGRAPHS ASSOCIATED WITH FINITE RINGS

Aleksandar T. Lipkovski

Communicated by Žarko Mijajlović

Abstract. Let A be a finite commutative ring with unity (ring for short). Define a mapping φ : A^{2} → A^{2} by (a, b) ↦ (a + b, ab). One can interpret this mapping as a finite directed graph (digraph) G = G(A) with vertices A^{2} and arrows defined by φ. The main idea is to connect ring properties of A to graph properties of G. Particularly interesting are rings A = ℤ/nℤ. Their graphs should reflect number-theoretic properties of integers. The first few graphs G_{n} = G(ℤ/nℤ) are drawn and their numerical parameters calculated. From this list, some interesting properties concerning degrees of vertices and presence of loops are noticed and proved.

1. Introduction

Finite rings have been studied for a long time (e.g., [1, 2]). Also, there have been some connections made between rings and graphs, more specifically, the graph of zero-divisors [3–5] and the unitary Cayley graph [6] of a ring. In the present paper, however, a completely different connection between finite rings and graphs is proposed and studied. This also has possible connections to elementary number theory. For basic algebraic and number-theoretic notions used here, see [7, 8].

Let A be a finite commutative ring with unity (ring for short). Define a mapping φ : A^{2} → A^{2} by (a, b) ↦ (a + b, ab). Intuitively, it reflects the ring structure of A. One can interpret this mapping as a finite directed graph (digraph) G = G(A) with vertices A^{2} and arrows defined by φ. The main idea is to deduce, if possible, ring properties of A from graph properties of G (e.g., the number of components, the lengths of longest paths and longest loops, the maximal degree of vertices, etc.).

Since A is finite, it has integer characteristic charA ∈ ℕ. If n is not a prime, then A has zero-divisors and A[X] is not a unique factorization ring (if ab = 0, a ≠ 0, b ≠ 0, then (X − a)(X − b) = X[X − (a + b)] are two distinct, nonassociated factorizations of X^{2} − (a + b)X). If n = p is prime, then A nevertheless could have zero-divisors (e.g., ℤ_{2} × ℤ_{2}). However, if A is a (finite) domain, then it must be a field, and in such case, A = GF (p^{k}) and A[X] is a UFD.

2010 Mathematics Subject Classification: Primary 11T99, Secondary 05C90.

Key words and phrases: finite rings; finite graphs; symmetric polynomials.

Supported by Ministry of Science and Education of Serbia, project OI-174020.

Particularly interesting are the rings A = ℤ_{n} = ℤ/nℤ. Their graphs should reflect some number-theoretic properties of the integers. From the above remark, we see that either n is prime, ℤ_{n} is a field and ℤ_{n}[X] is a UFD, or n is not prime, ℤ_{n} has zero-divisors and ℤ_{n}[X] does not have the UF property. The first few graphs G_{n} = G(ℤ_{n}) can be explicitly drawn (see Fig. 1 and Fig. 2). Already from this list, some interesting properties can be noticed, concerning the degrees of vertices and the presence of loops.

2. Degrees of vertices

Consider the degrees of vertices in G. As usual, the outgoing (incoming) degree of the vertex (a, b) is by definition the number of arrows beginning (ending) in this vertex. Since G is a graph of a function, the outgoing degree of each vertex (a, b) equals one. What is the incoming degree of the vertex (a, b)?

Proposition 2.1. The incoming degree of the vertex (a, b) ∈ G equals the number of distinct roots of the quadratic polynomial X^{2} − aX + b ∈ A[X].

Proof. If there is an arrow (x, y) −→ (a, b), then x + y = a, xy = b, and by substitution we deduce that both x and y are roots of this polynomial. Conversely, if x is a root of this polynomial, then there is an arrow (x, a − x) −→ (a, b), and for distinct roots such arrows are also distinct. In fact, if x_{1}, …, x_{k} are all the distinct roots of the polynomial, then there is a permutation σ ∈ S_{k} such that a − x_{i} = x_{σ(i)} . □

In the case of G_{p} for prime p, the incoming degree of a vertex (a, b) can be either 0 (if X^{2} − aX + b is irreducible, i.e., 0 ≠ 4b − a^{2} ∈ ℤ_{p} is a quadratic nonresidue modulo p), or 1 (if 4b − a^{2} = 0), or 2 (if 4b − a^{2} ≠ 0 is a quadratic residue modulo p).

In the case of G_{n} for nonprime n, the incoming degree of a vertex (a, b) can be greater than 2, which depends on the different factorizations of X^{2} − aX + b.

3. Components and closed loops

Consider closed paths, or loops, in G. Up to cyclic permutations, the loops are described by the corresponding arrow sequences.

Definition. The sequence

(3.1)  (a_{1}, b_{1}) −→ (a_{2}, b_{2}) −→ ⋯−→ (a_{k}, b_{k})

of arrows in G defines a loop of length k (or a k-loop) if (a_{k} + b_{k}, a_{k}b_{k}) = (a_{1}, b_{1}) and (a_{i} + b_{i}, a_{i}b_{i}) ≠ (a_{j} , b_{j}) for all j ⩽ i < k.

We see from Fig. 1 that there may exist loops of length 1 as well as longer loops. Also, some graphs G_{n} do contain G_{1} as a (weakly) connected component and some do not. The definition also implies that if k > 1, then every b_{i} ≠ 0.

Figure 1

Proposition 3.1. 1) There are exactly n = # A loops of length 1 in G, and they correspond to the vertices (a, 0).

2) Each connected component of G contains exactly one loop, and the number of connected components is n + #{loops of length > 1}.

Figure 2

3) The graph G_{1} is a (weakly) connected component of G if and only if A has no nontrivial nilpotent elements.

Proof. First note that if (a, b) → (a, b) is a 1-loop, then b = 0 (and conversely). Therefore 1) follows. Since each component must end with a loop, 2) follows. Now if a ≠ 0, then the incoming degree of the vertex (a, 0) is at least 2, since (0, a) −→ (a, 0) ⟵ (a, 0). Therefore, the only vertex which could be in the component G_{1} is (0, 0). But if (x, y) −→ (0, 0), then x^{2} = 0, and if x ≠ 0, then x is a nontrivial nilpotent element. □

What is the meaning of loops longer than 1? A closer look leads to necessary conditions which generalize the condition for 1-loops.

Proposition 3.2. If the sequence (3.1) is a k-loop, then

σ_{1}(b) = σ_{2}(b) = σ_{3}(b) = 0, (σ_{k}(a) − 1) σ_{k}(b) = 0

where σ_{m}(X) = σ_{m}(X_{1}, …, X_{k}) are the usual elementary symmetric polynomials in k variables.

Proof. There is an arrow (a_{i−1} , b_{i−1} ) −→ (a_{i}, b_{i}) if and only if one has the equality X^{2} − a_{i}X + b_{i} = (X − a_{i−1} )(X − b_{i−1} ) in the polynomial ring A[X]. Therefore, the loop condition implies the equality

∏_{i=1}^{k} (X^{2} − a_{i}X + b_{i}) = ∏_{i=1}^{k} (X − a_{i})(X − b_{i})

in the polynomial ring A[X]. After a straightforward multiplication, one obtains

X^{2k} −σ_{1}(a)X^{2k−1} +[σ_{2}(a)+σ_{1}(b)]X^{2k−2} −[σ_{3}(a)+_{∑ i≠j} a_{i}b_{j} ]X^{2k−3} +⋯ +σ_{k}(b)

= X^{2k} − [σ_{1}(a) + σ_{1}(b)]X^{2k−1} + [σ_{2}(a) + σ_{1}(a) σ_{1}(b) + σ_{2}(b)]X^{2k−2}
− [σ_{3}(a) + σ_{2}(a) σ_{1}(b) + σ_{1}(a) σ_{2}(b) + σ_{3}(b)]X^{2k−3} + ⋯+ σ_{k}(a) σ_{k}(b)

where σ_{m}(x) = σ_{m}(x_{1}, …, x_{k}) = ∑ _{1⩽j_{1} <···<j_{m} ⩽k} x_{j_{1}} ⋯ x_{j_{m}} . Comparing coefficients, one first obtains σ_{1}(b) = 0, and then σ_{2}(b) = 0. Finally, observing that ∑ _{i≠j} a_{i}b_{j} = σ_{1}(a) σ_{1}(b) − ∑ _{i} a_{i}b_{i} = σ_{1}(a) σ_{1}(b) − σ_{1}(b) one has σ_{3}(b) = 0. Comparison of constant terms gives the last condition. □

For k ⩽ 3, nice characterizations of loops can be obtained.

Proposition 3.3. For k = 1, the “sequence" (3.1) is a 1-loop ⇔ σ_{1}(b) = 0.

For k = 2, the sequence (3.1) is a 2-loop ⇔ σ_{1}(b) = σ_{2}(b) = 0.

For k = 3, the sequence (3.1) is a 3-loop ⇔ σ_{1}(b) = σ_{2}(b) = σ_{3}(b) = 0.

Proof. The case k = 1 was already discussed above: b_{1} = 0 ⇔ (a_{1}, b_{1}) −→ (a_{1}, b_{1}). For k = 2, we have b_{1} + b_{2} = 0 and b_{1}b_{2} = 0. It is also easy to check that these two conditions imply (a_{2}, b_{2}) −→ (a_{1}, b_{1}). Finally, for k = 3, one needs to prove that conditions σ_{1}(b) = σ_{2}(b) = σ_{3}(b) = 0 imply (a_{3}, b_{3}) −→ (a_{1}, b_{1}). Suppose that in the sequence (a_{1}, b_{1}) −→ (a_{2}, b_{2}) −→ (a_{3}, b_{3}) one has b_{1} +b_{2} +b_{3} = b_{1}b_{2} + b_{1}b_{3} + b_{2}b_{3} = b_{1}b_{2}b_{3} = 0. This implies that (X − b_{1})(X − b_{2})(X − b_{3}) = X^{3}. Now a_{3} + b_{3} = a_{2} + b_{2} + b_{3} = a_{1} + σ_{1}(b) = a_{1}. Using these two facts and comparing the coefficients of X^{4} in the polynomial identity

(X^{2} −a_{1}X +a_{3}b_{3})(X^{2} −a_{2}X +b_{2})(X^{2} −a_{3}X +b_{3}) = (X −a_{1})(X −a_{2})(X −a_{3})X^{3},

one obtains σ_{2}(a) + a_{3}b_{3} + b_{2} + b_{3} = σ_{2}(a), and finally a_{3}b_{3} = b_{1}. □

Remark. 1) It is easy to see that there exists a 2-loop ⇔ the ring A has nontrivial nilpotent elements. For, since (a_{2}, b_{2}) ≠ (a_{1}, b_{1}), we have b_{1} ≠ 0, b_{1}^{2} = 0 and this is a nilpotent in A. Conversely, if c is a nilpotent, c^{k−1} ≠ 0, c^{k} = 0 for k > 1, take b = c^{k−1} . Then b^{2} = 0 and there is a 2-loop (−1, b) −→ (b − 1, −b) −→ (−1, b). Therefore, the existence of nilpotents in A is visible in the graph G in two different, equivalent ways: the absence of a G_{1}-component and the presence of 2-loops.

2) In the case A = ℤ_{n}, this is equivalent to the condition that n is not squarefree, since ℤ_{n} has no nontrivial nilpotents if and only if n is square-free. This leads to an (inefficient) algorithm for deciding whether a given integer n is square-free: look for 2-loops in the corresponding graph G_{n}.

3) The existence of a 3-loop implies that the ring A has zero-divisors, since in such case b_{1}b_{2}b_{3} = 0 and all b_{i} ≠ 0.

4) Proposition 5 suggests a tempting conjecture: if the sequence (3.1) is a kloop, then σ_{1}(b) = σ_{2}(b) = ⋯= σ_{k}(b) = 0. However, as the example A = ℤ_{5} shows (see Fig. 1), it is already false for k = 4: there is a 4-loop (2, 2) −→ (4, 4) −→ (3, 1) −→ (4, 3) such that σ_{1}(b) = σ_{2}(b) = σ_{3}(b) = 0 and σ_{4}(b) ≠ 0. In this case, σ_{4}(a) = 1 in accordance with the proposition.

4. Computer calculations

A computer program has been written and run on a PC to calculate some properties of the graph G_{n}, such as the number c_{n} of components, the length p_{n} of the longest path (including the loop closing the path) and l_{n} of the longest loop. The values of c_{n}, p_{n}, and l_{n} for n ⩽ 50 are shown in the following table.

\begin{matrix}n & c_{n} & p_{n} & l_{n} \\ 1 & 1 & 1 & 1 \\ 2 & 2 & 3 & 1 \\ 3 & 3 & 5 & 1 \\ 4 & 5 & 4 & 2 \\ 5 & 6 & 6 & 4 \\ 6 & 6 & 5 & 1 \\ 7 & 7 & 9 & 1 \\ 8 & 12 & 6 & 4 \\ 9 & 14 & 6 & 3 \\ 10 & 12 & 6 & 4 \\ 11 & 12 & 14 & 6 \\ 12 & 15 & 6 & 2 \\ 13 & 14 & 22 & 4 \\ 14 & 14 & 9 & 1 \\ 15 & 18 & 8 & 4 \\ 16 & 30 & 10 & 8 \\ 17 & 19 & 18 & 10 \end{matrix}  \begin{matrix}n & c_{n} & p_{n} & l_{n} \\ 18 & 28 & 6 & 3 \\ 19 & 20 & 34 & 8 \\ 20 & 31 & 6 & 4 \\ 21 & 21 & 9 & 1 \\ 22 & 24 & 14 & 6 \\ 23 & 24 & 32 & 10 \\ 24 & 36 & 8 & 4 \\ 25 & 50 & 12 & 5 \\ 26 & 28 & 22 & 4 \\ 27 & 63 & 10 & 9 \\ 28 & 35 & 10 & 2 \\ 29 & 32 & 35 & 14 \\ 30 & 36 & 8 & 4 \\ 31 & 32 & 44 & 18 \\ 32 & 72 & 18 & 16 \\ 33 & 36 & 14 & 6 \\ 34 & 38 & 18 & 10 \end{matrix}  \begin{matrix}n & c_{n} & p_{n} & l_{n} \\ 35 & 42 & 12 & 4 \\ 36 & 73 & 8 & 6 \\ 37 & 39 & 49 & 24 \\ 38 & 40 & 34 & 8 \\ 39 & 42 & 22 & 4 \\ 40 & 80 & 8 & 4 \\ 41 & 45 & 63 & 22 \\ 42 & 42 & 9 & 1 \\ 43 & 48 & 98 & 11 \\ 44 & 61 & 15 & 6 \\ 45 & 87 & 14 & 12 \\ 46 & 48 & 32 & 10 \\ 47 & 50 & 60 & 12 \\ 48 & 90 & 12 & 8 \\ 49 & 118 & 10 & 7 \\ 50 & 100 & 12 & 5 \end{matrix}

From the table, it is evident that local peaks of p_{n} and l_{n} appear for (some, but not all) primes n and the peaks of l_{n} appear also for n = 2^{k}. Why? This and many other similar questions can be raised and answered.

We give here two very rough estimates for c_{n} and p_{n}. Consider n = 2^{k} (k ⩾ 3). Suppose that p, q ∈ ℤ_{n} are not divisible by 2, and let m ⩾ 2. There exists an arrow (2p, 2^{m}q) −→ (2p′, 2^{m+1} q′) where p′ = p + 2^{m−1} q, q′ = pq are again not divisible by 2. This gives a path

(2, 2^{2}) −→ ⋯−→ (2p, 2^{k−1} q) −→ (2p′, 0) ⟲

of length k − 1. This means that in the case considered, p_{n} ⩾ k − 1. Similar arguments can be used in the general case for any prime factor of n, which means that p_{n} ⩾ k − 1 where k is the maximal multiplicity of any prime factor of n. However, as the table shows, this rough lower estimate is not very close to p_{n}.

The starting vertices (a, b) (with incoming degree 0) correspond to irreducible quadratic polynomials X^{2} −aX +b in ℤ_{n}[X]. It can easily be seen that the number i of irreducible quadratic polynomials is i ⩾ n^{2}−\binom{n+1}{2} = \frac{n(n−1)}{2} (ℤ_{n}[X] has unique factorization exactly when n is prime, and then the equality holds), therefore the number of starting vertices is i. This gives a rough upper estimate for the number of components c_{n} ⩽ i. Again, as the table shows, this is not very close to c_{n}.

5. Graphs for 1 ⩽ ⩽ ⩽ n ⩽ ⩽ ⩽ 9

Here are the first nine digraphs G_{n}. The components which appear several times in the same and/or different graphs are denoted by the same letter (these are G_{1}, L_{2}, L_{3}) and drawn only by their first appearance. The number to the left of the component is the number of times this component appears in the whole graph. The sign + denotes the (disjoint) union of components.

References

1. C. Fletcher, Rings of small order, Math. Gazette 64 (1980), 9-22

2. B. Fine, Classification of finite rings of order p^{2}, Math. Magazine 66 (1993), 248-252

3. D. F. Anderson, P. S. Livingston, The zero-divisor graph of commutative ring, J. Algebra 217 (1999), 434-447

4. D. F. Anderson, M. C. Axtell, J. A. Stickles Jr., Zero-divisor graphs in commutative rings. (In: Commutative Algebra, Noetherian and Non-Noetherian Perspectives, Fontana M., Kabbaj S.- E., Olberding B., Swanson I., eds., Springer New York, 2011, 23-45)

5. M. Axtell, J. Stickles, Graphs and zero-divisors, College Math. J. 41 (2010), 396-399

6. R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jimenez, R. Karpman, A. Kinzel, D. Pritikin, On the unitary Cayley graph of a finite ring, El. J. Combinatorics 216 (2009), #R117

7. T. Hungerford, Algebra (GTM v. 73), Springer, 1980

8. A. Baker, A Concise Introduction to the Theory of Numbers, Cambridge University Press, 1985

Faculty of Mathematics (Received 31 03 2011) University of Belgrade (Revised 10 04 2012) Belgrade, Serbia

    acal@matf.bg.ac.rs