Article Accepted by Journal of Symbolic Computation

Algorithms for Finite Near-rings and their N-Groups^{∗}

Franz Binder^{†} and Peter Mayr^{‡}

Department of Algebra, Johannes Kepler University, A-4040 Linz, Austria

Abstract

In this note, we present algorithms to deal with finite near-rings, the appropriate algebraic structure to study non-linear functions on finite groups. Just as rings (of matrices) operate on vector spaces, near-rings operate on groups. In our approach, we have developed efficient algorithms for a variety of problems that involve the structure of the operation of a near-ring on a group. From this, we retrieve information about the nearring itself.

1. Introduction

Convention 1.1: All algebraic structures in this paper are finite.

Important examples of rings are matrix-rings; these arise as linear mappings on vector spaces. In the present note, we compute with algebraic structures appropriate for dealing with non-linear mappings, namely near-rings [Pilz, 1983, Meldrum, 1985, Clay, 1992].

Definition 1.1: A set N together with two binary operations + and · is called a (right) near-ring if

1. (N, +) is a (not necessarily abelian) group.

2. (N, ·) is a semigroup.

3. · is right distributive over +, i.e., ∀ a, b, c ∈ N: (a + b) · c = a · c + b · c.

∗This work has been supported by the Austrian National Science Foundation (Fonds zur Förderung der wissenschaftlichen Forschung) under Grant P12911-INF. More details are avail-

able at www.algebra.uni-linz.ac.at/sonata/.
   †mailto:Franz.Binder@algebra.uni-linz.ac.at
   ‡mailto:Peter.Mayr@algebra.uni-linz.ac.at

F. Binder and P. Mayr: Near-rings and N-Groups 2

The equality f0 = 0 for f ∈ N is not implied by these axioms.

Definition 1.2: The zero-symmetric part of a near-ring N is usually denoted by N_{0} and defined by N_{0} := {f ∈ N | f0 = 0}. Also, both the elements of N_{0} and any near-ring that fulfills N = N_{0} are called zero-symmetric. A near-ring with commutative addition is called abelian.

Note that the missing left distributive law, a(b + c) = ab + ac, has to do with linearity if a is considered as a function. In fact, functions on groups are the typical examples of near-rings. Let Γ be a group, and let M(Γ) be the set of all mappings from Γ into Γ (we will call them transformations). We define + and · on M(Γ) by (f + g)(γ) := f(γ) + g(γ) and (f · g)(γ) := f(g(γ)). Then (M(Γ), +, ·) is a near-ring, the full transformation near-ring. For the appropriate algebraic sub-structures, the sub-near-rings, we then write N ≤ M(Γ) and call them transformation near-rings. In fact, every near-ring can be represented as a transformation near-ring on some group Γ. But we are interested mainly in the natural case, where Γ is small, and N is (very) big, but generated by a small number of generators. If small means 100, then N can have up to 100^{100} elements, which is almost infinite ([Scott, 1979] contains many impressive examples). In particular, big means that the elements of N cannot be enumerated in practice, whereas small means that it is no problem to loop over all elements of Γ, or over all generators. So our main concern is to compute as much as we can with generators only. We note that a corresponding problem in group theory is solved via Sim’s stabilizing chains [Sims, 1970]. Though we could not develop such a powerful tool for near-ring theory, we can give solutions for many important special cases as well as completely satisfactory solutions to a variety of related problems.

In contrast to ring theory, no systematic attempt of an algorithmic treatment of near-ring theory seems to have been done so far, apart from Binder et al.

[2000] and a project funded by the Austrian Science Fonds, which resulted in the development of the package SONATA based on GAP 4 [Aichinger et al., 2000]. This article contains some of the theory behind the development of that package and extends Binder et al. [2000] by a more complete and better structured set of algorithms for N-groups, including the efficient computation of commutators. All these methods now also work for N_{0}-subgroups, where N (not N_{0}) is given by generators. We consider centralizer near-rings, in particular those with a group of fixed-point-free automorphisms. A straightforward, but very effective method to compute N-endomorphisms allows us to significantly generalize the previous solution to the realizability problem, using a more general interpolation algorithm together with more precise density results.

2. N-Groups

Just in the same way as R-modules or vector spaces are used in ring theory, N-groups are used in near-ring theory.

Definition 2.1: Let N be a near-ring. An N-group is an additive group Γ together with an operation of N on Γ (i.e., a mapping N × Γ → Γ), denoted by juxtaposition, such that for all n, m ∈ N and γ ∈ Γ,

(n + m)γ = nγ + mγ,
(nm)γ = n(mγ).

We say that N operates faithfully on Γ (or that Γ is a faithful N-group) if nγ = 0 for all γ ∈ Γ is true only if n = 0.

Remark 2.1: Equivalently, an N-group can be described by a homomorphism from the near-ring N into M(Γ), which is an embedding iff the operation is faithful.

As for R-modules, the actual operation is always to be understood from the context.

N-groups are always written additively, even if they are not abelian.

For each fixed near-ring N, the N-groups form a variety (just as the near-rings themselves). General definitions are obtained from the corresponding ones from group theory by prefixing them with the near-ring involved. In particular:

Definition 2.2: Let N be a near-ring.

1. A group-homomorphism α between two N-groups Γ_{1} and Γ_{2} is called an N-homomorphism if for all n ∈ N and for all γ ∈ Γ_{1},

α(nγ) = n(αγ).

2. A subgroup H of an N-group Γ (we write H ≤ Γ for this) is called an N-subgroup (written as H ≤_{N} Γ) if it is closed under the operation of N, i.e., if nγ ∈ H for all n ∈ N, γ ∈ H.

3. If H is the kernel of an N-homomorphism, then it is called an N-normal subgroup and we write H ⊴_{N} Γ.

Using the term “N-normal” for the kernels of homomorphisms (as we do here) seems to be quite natural but is not standard in near-ring theory. The notions “N-ideal” or sometimes “N-module” are used instead by most authors.

Example 2.1:

1. If N ≤ M(Γ), then Γ is a faithful N-group via function application as operation (or via the identity as the homomorphism into M(Γ)).

2. The additive group (N, +) of a near-ring (N, +, ·) is an N-group via the near-ring multiplication.

3. N-Subgroups

For the following, we introduce some useful notations:

Definition 3.1: Let Γ be an N-group, H ≤ Γ, E ⊆ N, and F ⊆ Γ. Then

1. ⟨E⟩ denotes the sub-near-ring generated by E;

2. ⟨F ⟩ denotes the subgroup generated by F;

3. ⟨E^{+}⟩ denotes the (additive) subgroup generated by E additively;

4. EF := { aγ | a ∈ E, γ ∈ F }.

5. H is called E-invariant if EH ⊆ H;

6. ⟨F ⟩_{E} denotes the smallest E-invariant subgroup of Γ containing F; in particular, ⟨F ⟩_{N} denotes the N-subgroup generated by F;

Note that these definitions apply e.g. when Γ is (N, +). We also use the usual simplifications for singleton sets, e.g., Eγ := E{γ}.

The following is immediate:

Proposition 3.1: Let E be a subset of a near-ring N. Then ⟨E⟩ = ⟨E^{+}⟩_{E}.

This means that we can use induction proofs over N: to prove a statement for all f ∈ N, we just show that it is true for all generators and that it is closed under subtraction and under multiplications by generators from the left. This technique is demonstrated by the (easy) proof below.

Proposition 3.2: Let Γ be an N-group, N = ⟨E⟩, F ⊆ Γ, and γ ∈ Γ. Then:

1. ⟨F ⟩_{N} = ⟨F ⟩_{E};

2. Nγ = ⟨Eγ⟩_{E};

3. NF = ⋃_{η∈F} Nη.

Proof: For the first part, we have to show that ⟨F ⟩_{E} is N-invariant, i.e., that f(⟨F ⟩_{E}) ⊆ ⟨F ⟩_{E} for all f ∈ N. We use induction on f.

Base case: For f ∈ E, the statement is true by definition.

Subtraction case: Assume that it is true for f and g in E, and let η ∈ ⟨F ⟩_{E}. Then, (−f +g)η = −fη +gη ∈ ⟨F ⟩_{E}, by induction and because ⟨F ⟩_{E} is a group.

Multiplication case: Finally, assume that the statement is true for f ∈ N and take e ∈ E, η ∈ ⟨F ⟩_{E}. Then,

(ef)η = e( \underbrace{fη}_{∈⟨F ⟩_{E}}) ∈ ⟨F ⟩_{E},

by induction and because ⟨F ⟩_{E} is E-invariant.

The other parts are immediate. □

Algorithm 1 Computing Orbits Let Γ be an N-group. Require: N = ⟨E⟩, F ⊆ Γ. Ensure: H = ⟨F ⟩_{E}

H := ⟨F ⟩

while EH ⊈ H do

H := ⟨H ∪ EH⟩ end while

These results lead to easy, but essential, algorithms.

Corollary 3.1: Under the same hypotheses, ⟨F ⟩_{N}, Nγ, {Nη | η ∈ Γ}, and NF can be computed within O(|E| |Γ|) operations.

Proof: From the proposition, the method to compute ⟨F ⟩_{E} is obvious and made explicit in Algorithm 1. The computation of Nγ is just a special case of this. And NF is just the union of the Nη’s. To obtain the complexity bound, note first that all of the necessary group-oriented operations (i.e., generating subgroups) can be done within the bound and need not be counted. What essentially remains to be done is to compute all products eη for e ∈ E and for each η in the result, which is at most Γ. Thus, with appropriate storage of the intermediate results, we still do not exceed the bound. □

Remark 3.1: If N is a near-ring with identity, then NF = ⟨F ⟩_{N}.

Remark 3.2: If we add some obvious book-keeping to Algorithm 1, we can compute more information. For example, for each η ∈ Nγ, we then can determine an appropriate f ∈ N such that η = fγ. We could even store how f is constructed from the generators in E.

4. Difference Operator

Computations in spaces of continuous functions are usually performed using linearization via the differential operator. In the discrete case, we can do something similar with a difference operator. We define it in the following way.

Definition 4.1: Let N be a near-ring and Γ an N-group. For f ∈ N and x, a ∈ Γ, we define

Δfxa := −fx + f(x + a),

and call it the difference of f at x in direction a.

Thus the operator Δ is understood to map an element of N into a function that maps elements of Γ into elements of M(Γ). In particular, Δfx ∈ M(Γ). This operator is also useful in the case Γ = N.

Proposition 4.1: With the notation of the definition we have

Δfx(a + b) = Δfxa + Δf(x + a)b,  (quasi-linearity)  (1)
Δf(x + a)b = −Δfxa + Δfx(a + b).  (translation rule)  (2)

Proof: Of course, both equations are equivalent. We show (2):

−Δfxa + Δfx(a+b) = −f(x+a) + fx − fx + f(x+a+b)

= Δf(x+a)b. □

Proposition 4.2: Continuing the above notation and with g ∈ N, we have

Δ(f + g)xa = −gx + Δfxa + gx + Δgxa,
Δ(−f)xa = −(fx + Δfxa − fx).

Proof: We show the second equation: Δ(−f)xa = −(−f)x+(−f)(x+a) = fx− f(x+a) = −(f(x+a)−fx) = −(fx−fx+f(x+a)−fx) = −(fx+Δfxa−fx).

□

Thus, in general, Δ is not linear in the first argument unless Γ is abelian. When considering normal subgroups, these annoying conjugations are absorbed.

Of course, the definition of the difference operator should mirror that of the differential operator for functions on linear spaces. In contrast to the latter, the difference at a point, Δfx, need not be a linear function. Equation (1), however, suggests that it is not too far away. In particular, if we know the difference in directions generating Γ (as a group), then we know it in any direction. This is similar to partial derivatives. On the other hand, the equivalent equation (2) shows that the difference at 0, Δf0, already determines the difference at any point Δfx. This is far away from the idea that the difference at a point should describe a function locally.

Proposition 4.3: The operator Δ fulfills the following chain rule:

Δ(fg)xa = Δf(gx)Δgxa.  (3)

Proof: Δ(fg)xa = −fgx + fg(x + a) = −fgx + f(gx + Δgxa) = Δf(gx)Δgxa. □

The difference operator can be iterated in the following way. The definition is motivated by the formalism Δ^{n+1}f = Δ(Δ^{n}f).

Definition 4.2: Let Γ be an N-group, f ∈ N, x, a, b ∈ Γ, a ∈ Γ^{n}. Then we define the higher order difference operators as

Δ^{n+1}fxba := −Δ^{n}fxa + Δ^{n}f(x + b)a.

In particular,

Δ^{2}fxba = Δ(Δf)xba
= −Δfxa + Δf(x + b)a
= −f(x + a) + fx − f(x + b) + f(x + b + a).

Remark 4.1: If Γ is abelian, then Δ^{n} is symmetric in the last n arguments.

Proposition 4.4: Δ^{2} fulfills the following chain rule:

Δ^{2}(fg)xba = Δ^{2}f(gx)(Δgxa)(Δgxb) + Δf (g(x + b) + Δgxa) Δ^{2}gxab.

Proof: We compute

Δ^{2}(fg)xba = −Δ(fg)xa + Δ(fg)(x + b)a
= −Δf(gx) (Δgxa) + Δf (g(x + b)) (Δgxa)
− Δf (g(x + b)) (Δgxa) + Δf (g(x + b)) (Δg(x + b)a)
= Δ^{2}f(gx)(Δgxb)(Δgxa) + Δf (g(x + b) + Δgxa) (Δ^{2}gxba).

The last stage has used the translation rule (2) with x ↦ g(x+b) and a ↦ Δgxa.

□

Definition 4.3: Let E ⊆ N and A, F ⊆ Γ.

1. By ΔEAF := { Δeaγ | e ∈ E, a ∈ A, γ ∈ F }, the Δ-operator can be applied to sets, and we use the obvious modifications for singleton sets.

2. We say that F is ΔEA-invariant iff ΔEAF ⊆ F;

3. (F)_{ΔEA} denotes the smallest ΔEA-invariant normal subgroup containing F.

5. N-Normal Subgroups

N-normal subgroups, are usually characterized as follows.

Proposition 5.1: Let Γ be an N-group and H a subgroup of Γ. Then H ⊴_{N} Γ iff H ⊴ Γ and

−fγ + f(γ + η) ∈ H for all η ∈ H, f ∈ N, and γ ∈ Γ.

Note that −fγ + f(γ + η) = Δfγη. In fact, we can express this as

Corollary 5.1: A normal subgroup of Γ is N-normal iff it is ΔNΓ-invariant.

N-normal subgroups of N^{+} (i.e., N considered as an N-group) are called left ideals.

Corollary 5.2: A left ideal of a near-ring N is a ΔNN-invariant normal subgroup.

An efficient method to compute N-normal subgroups is provided by a stronger result.

Proposition 5.2: Let Γ be an N-group with N = ⟨E⟩. A normal subgroup is N-normal iff it is ΔEΓ-invariant.

Proof: Let H be a ΔEΓ-invariant normal subgroup. To show that ΔfΓH ⊆ H for all f ∈ N, we use induction on f. The base case holds. For the subtraction case, consider Δ(−f + g)xγ = −gx − (fx + Δfxγ − fx) + gx + Δgxγ ∈ H, using Proposition 4.2 and by normality. And for the multiplication case, consider e ∈ E and f ∈ N fulfilling the statement. Then, using the chain rule (3), we have Δ(ef)xγ = Δe(fx)Δfxγ ∈ H, because Δfxγ ∈ H. □

Corollary 5.3: The N-normal subgroup generated by a set I can be computed within O(|E| |Γ| k) operations, where k is a bound for the number of generators necessary to generate any normal subgroup of Γ.

Proof: By Proposition 5.2, we need to compute (I)_{ΔEΓ}. The straightforward algorithm is similar to Algorithm 1. This leads to the complexity bound O(|E| |Γ|^{2}). To improve it, note that we can use quasi-linearity (1). □

6. Commutators

In the previous sections, we have developed efficient algorithms to compute the lattice of N-subgroups as well as the lattice of N-normal subgroups, i.e., the congruence lattice of an N group. In addition to this, we would like to be able to compute the commutator operation on the congruences, in the sense of Universal Algebra. We will use the notation [X, Y]_{N} to distinguish the N-commutator (i.e., that with respect to the variety of N-groups) from the usual group commutator [X, Y]. Using the definition of Gumm [1980], we obtain the following adaptation for N-groups.

Definition 6.1: Let Γ be an N-group of a near-ring N and X ⊴_{N} Γ, Y ⊴_{N} Γ. With ξ := {(a, a + x) | a ∈ Γ, x ∈ X}, we define

δ_{X}^{Y} := ({ (y, y) | y ∈ Y })_{ΔNξ};
[X, Y]_{N} := { z | (0, z) ∈ δ_{X}^{Y} }.

Then [X, Y]_{N} ⊴_{N} Γ, and it is called the N-commutator of X and Y.

Remember that the congruence associated with a normal subgroup X is given as ξ above and that any N-congruence is an N-subgroup of Γ × Γ.

Theorem 6.1: Let N be a transformation near-ring generated by E, and let X and Y be N-normal subgroups of the N-group Γ, generated additively by I and J, respectively. Then the N-commutator of X and Y is the N-normal subgroup of Γ generated by [X, Y] and Δ^{2}EΓIJ.

Proof: Let ξ be as in Definition 6.1 and Z := ([X, Y] ∪ Δ^{2}EΓXY)_{ΔNξ}.

At first, we show that the commutator [X, Y]_{N} indeed contains all the generators of Z. Note that {z | (0, z) ∈ δ_{X}^{Y}} = {z | (y, y+z) ∈ δ_{X}^{Y}}, for any y ∈ Y, as δ_{X}^{Y} contains all pairs of the form (y, y). Because −(0, x)+(y, y)+(0, x) ∈ δ_{X}^{Y}, we have −y − x + y + x ∈ [X, Y]_{N} for all x ∈ X, y ∈ Y. Similarly, by Δe(a, a + x)(y, y) = (Δeay, Δe(a + x)y) ∈ δ_{X}^{Y}, we have −Δeay + Δe(a + x)y = Δ^{2}eaxy ∈ [X, Y]_{N} for all e ∈ N, a ∈ Γ, x ∈ X, y ∈ Y. Thus Z ⊆ [X, Y]_{N}.

Conversely, to prove Z ⊇ [X, Y]_{N}, define δ := { (y, y + z) | y ∈ Y, z ∈ Z }. Below we show that δ is N-normal in ξ. Because δ contains the generators of δ_{X}^{Y}, this means that δ ⊇ δ_{X}^{Y} and, consequently, that Z = {z | (0, z) ∈ δ} ⊇ {z | (0, z) ∈ δ_{X}^{Y}} = [X, Y]_{N}.

For the following, let y_{1}, y_{2}, y ∈ Y, z_{1}, z_{2}, z ∈ Z, x ∈ X, and a ∈ Γ.

δ is a subgroup: (y_{1}, y_{1} + z_{1}) − (y_{2}, y_{2} + z_{2}) = (y_{1} − y_{2}, y_{1} + z_{1} − z_{2} − y_{2}). Clearly, y_{1} − y_{2} ∈ Y, and y_{2} − y_{1} + y_{1} + z_{1} − z_{2} − y_{2} = y_{2} + (z_{1} − z_{2}) − y_{2} ∈ Z, as Z is normal.

δ is normal: (a, a+x)+(y, y +z)−(a, a+x) = (a+y −a, a+x+y +z −x−a) should be in δ. Clearly, a + y − a ∈ Y, and, since Z is normal −(a + y − a) +

(a + x + y + z − x − a) = a \underbrace{−y + x + y − x}_{∈Z} + \underbrace{x + z − x}_{∈Z} −a ∈ Z.

δ is ΔEξ-invariant: Δe(a, a + x)(y, y + z) = ( Δeay, Δe(a + x)(y + z) ) should be in δ. Clearly, Δeay ∈ Y, and

−Δeay + Δe(a + x)(y + z) = −Δeay + Δe(a + x)y + Δe(a + x + y)z

= \underbrace{Δ^{2}eaxy}_{∈Z} + \underbrace{Δe(a + x + y)z}_{∈Z} ∈ Z.

The validity of the restriction to the additive generators of the ideals again follows from quasilinearity. □

Corollary 6.1: N-commutators of N-normal subgroups of N-groups can be computed within O(|E| |Γ| k^{2}) operations, with k as in Corollary 5.3.

7. Left Ideals and N_{0}-Subgroups

Our algorithms for computing with an N-group Γ (N given by a small set E of generators) depend on the efficient computation of orbits (e.g. Nγ). We show that essentially the same methods work if, instead of N, we encounter a left ideal given by (left ideal) generators.

Proposition 7.1: Let N be a near-ring, Γ an N-group, and L a left ideal of N. If γ ∈ Γ and I is a set of (left ideal) generators of L, then

Lγ = (Iγ)_{ΔE(Nγ)}.

Proof: Let H := (Iγ)_{ΔE(Nγ)}. For all f ∈ L and h ∈ H, we have to show that fγ ∈ H. We do this by induction on f using L = (I)_{ΔEN}. The base case is trivial, so are the difference case and the conjugation case. For the Δ-case, consider e ∈ E, n ∈ N, and f ∈ L for which the statement is true. Then

(Δenf)γ = Δe(\underbrace{nγ}_{∈Nγ})(\underbrace{fγ}_{∈H}) ∈ H.

□

Corollary 7.1: Lγ can be computed within O(|E| |Γ| k) operations, with k as in Corollary 5.3.

For an arbitrary subset E of N, we define

E_{0} = {−f0 + f | f ∈ E}.

It is immediate that this notation just extends that for the zero-symmetric part of a near-ring. Unfortunately, N = ⟨E⟩ does not imply N_{0} = ⟨E_{0}⟩. In fact, we are not aware of any general efficient method to compute near-ring generators of N_{0} from those of N.

Nevertheless, N_{0} is a left ideal of N and E_{0} generates N_{0} as a left ideal.

Proposition 7.2: Let N be a near-ring generated by a set ⟨E⟩. Then

N_{0} = (E_{0})_{ΔNN} = (E_{0})_{ΔEN} = (E_{0})_{ΔE(N0)}.

Proof: That N_{0} is a left ideal is well known and immediately checked. Let M := (E_{0})_{ΔEN0}. It remains to prove N_{0} ⊆ M. Note that N_{0} = {−f0 + f | f ∈ N}. Thus, we have to show that −f0 + f ∈ M, for all f ∈ N, which we prove by induction on f. The base case, f ∈ E, is trivial. For the difference case, let f, g ∈ N such that −f0 + f ∈ M and −g0 + g ∈ M. We have to show that −(f − g)0 + (f − g) ∈ M. Using normality,

−(f − g)0 + (f − g) = g0 − f0 + f − g

= g0 − f0 + f − g0 + g0 − g + g0 − g0

= \underbrace{g0 \underbrace{−f0 + f}_{∈M} −g0}_{∈M} + \underbrace{g0 − (\underbrace{−g0 + g}_{∈M}) − g0}_{∈M} ∈ M.

For the multiplication case, we need to show that −ef0 + ef ∈ M for e ∈ E under the assumption that −f0 + f ∈ M. We apply the ΔE(N0)-invariance:

−ef0 + ef = −ef0 + e(f0 − f0 + f)

= Δe(f0) \underbrace{(−f0 + f)}_{∈M} ∈ M.

□

Corollary 7.2: Let Γ be an N-group and γ ∈ Γ. If N is generated by E, then N_{0}γ = (E_{0}γ)_{ΔE(Nγ)}.

Proof: Just combine the previous results. □

8. Centralizer Near-rings

Definition 8.1: Let Γ be a group and S be a semigroup of endomorphisms of Γ. Then the sub-near-ring of M(Γ)

M_{S}(Γ) := {f ∈ M(Γ) | fs = sf for all s ∈ S}

is called a centralizer near-ring.

Particular examples are M(Γ) (for S = ∅) and M_{0}(Γ) (for S = {0}). In this context, we use S^{0} := S ∪ {0}.

For a centralizer near-ring, it is easy to decide whether it contains a given f ∈ M(Γ). This is in contrast to the case of transformation near-rings. Dually, it is hard to compute non-trivial elements of an arbitrary centralizer near-ring (easy for a transformation near-ring).

An automorphism α of Γ is called fixed-point-free if for all γ ∈ Γ, γ ≠ 0, the equation α(γ) = γ implies α = id. If α ≠ id is fixed-point-free on Γ, then αf = fα for f ∈ M(Γ) implies that f(0) = 0 since αf(0) = fα(0) = f(0). For D a group of fixed-point-free automorphisms and |D| > 1, we have that M_{D}(Γ) = M_{D^{0}}(Γ). These centralizer near-rings are essential for the structure theory of near-rings This is a consequence of the well-known density theorems. As an example, we cite a simplified version of Theorem 4.52 in Pilz [1983].

Theorem 8.1: Let N be a zero-symmetric near-ring with identity and Γ a faithful N-group without proper N-subgroups. Let D be the set of all non-zero N-endomorphisms of Γ. Then D is a group of fixed-point-free automorphisms, N is a simple near-ring, and

• either N is a full matrix ring (if N is a ring)

• or N = M_{D^{0}}(Γ) (if N is not a ring).

This shows that the near-rings M_{D^{0}}(Γ) (D fixed-point-free) can be regarded as a non-linear version of matrix rings. In fact, there is even more analogy, because the elements of these near-rings can be described explicitly, very similar to the construction of matrices (or linear mappings) using a basis.

The following is Theorem 3.31 in Meldrum [1985].

Theorem 8.2: Let Γ be a group, D be a group of fixed-point-free automorphisms of Γ, and A be a set of non-zero orbit representatives, i.e., Γ \ {0} = ⨄_{γ∈A} Dγ. Then each function h from A into Γ can be extended to exactly one element f ∈ M_{D^{0}}(Γ) by f(0) := 0 and

f(αγ) := αh(γ),

for each α ∈ D and γ ∈ A. In particular,

|M_{D^{0}}(Γ)| = |Γ|^{|A|} .

Thus, A is used instead of a vector basis here.

For transformation near-rings, note that the assumptions of Theorem 8.1 can be checked easily by the methods developed so far and those in section 10.

Variants of these results in Pilz [1983] also work for non-zero-symmetric nearrings.

9. N-Endomorphisms

The previous section shows that in order to represent a transformation nearring N ≤ M(Γ) as a centralizer near-ring, it is important to have an effective method to determine the N-endomorphisms of Γ.

Proposition 9.1: Let ⟨E⟩ = N ≤ M(Γ). Then the endomorphism α ∈ End(Γ) is an N-endomorphism iff

αe = eα, for all e ∈ E.

Proof: The necessarity is trivial. For the sufficiency, we have to prove αf = fα, for all f ∈ N. This is done by induction on f. Let α commute with e ∈ E and f, g ∈ N. Then

(ef)α = eαf = α(ef);
(−f + g)α = −fα + gα = −αf + αg = α(−f + g).

The second computation has used that α is a group-homomorphism. □

An N-homomorphism on Γ is uniquely determined by its restriction to any set G with ⟨G⟩_{N} = Γ. The total number of N-endomorphisms of Γ is bounded by |Γ|^{|G|}, where G is a minimal N-generating set. This is particularly nice if Γ can be generated by a single element γ. For all possible images i ∈ Γ, we test whether the homomorphism from Γ to Γ induced by γ ↦ i commutes with all generators of N. If it does, it is indeed an N-homomorphism.

If Γ = ⟨γ_{1}, …, γ_{l}⟩_{N} needs l N-generators, l > 1, we can still use an inductive approach, determining the partial N-homomorphisms from H = ⟨γ_{1}, …, γ_{k}⟩_{N} to Γ, and then extending each of them to N-homomorphisms from ⟨H, γ_{k+1}⟩_{N} to Γ by finding a feasible image for γ_{k+1}, if possible.

Algorithm 2 shows how to extend a partial N-homomorphism α from H ≤_{N} Γ into Γ to an N-homomorphism β defined on ⟨H, g⟩_{N}.

The condition that |⟨{ (h, α(h)) | h ∈ H } ∪ { (g, i) }⟩_{N}| = |⟨H, g⟩_{N}| is necessary and sufficient for β determined by β|_{H} = α and β(g) = i to be a group homomorphism on ⟨H, g⟩_{N}. If β commutes with all generators of N, then it is an N-homomorphism by Proposition 9.1.

Remark 9.1: Of course, not every element i of Γ is a feasible image of a particular g under a group homomorphism, let alone an N-homomorphism. We can Algorithm 2 Extending N-homomorphism Let N be a near-ring of transformations on the group Γ. Require: N = ⟨E⟩, H <_{N} Γ, α ∈ Hom_{N}(H, Γ) and g ∈ Γ \ H. Ensure: Nhomos = { β ∈ Hom_{N}(⟨H, γ⟩_{N}, Γ) | β|_{H} = α }

Nhomos = ∅

for i ∈ Γ do

if |⟨{ (h, α(h)) | h ∈ H } ∪ { (g, i) }⟩_{N}| = |⟨H, g⟩_{N}| then Define β on ⟨H, g⟩_{N} such that β|_{H} = α and β(g) = i. if for all e ∈ E : eβ = βe then

Add β to Nhomos end if end if

end for

restrict the search space to elements fulfilling a number of criteria that are easy to check by using only near-ring generators. Thus we avoid using the costlier computation of the size of the N-groups by the closure algorithm for a choice of i which is obviously not feasible.

The order of i divides the order of g, and it is equal to the order of g if Algorithm 2 is used for the computation of N-automorphisms.

If g is an element of eΓ for some e ∈ E, then the image of g under an N-endomorphism is again an element of eΓ. For any N-automorphism we also have that if g ∉ eΓ for some e ∈ E, then the image of g is not in eΓ.

Moreover, if we already know a group S of N-automorphisms (e.g., the inner automorphisms), we may compute the stabilizer S′ := {s ∈ S | sα = α} of the partial N-endomorphism α in S. Let i be a feasible image for g to extend α on ⟨H, g⟩_{N} to an N-endomorphism β. Then si, for s ∈ S′, also gives an N-endomorphism, namely, sβ. Thus, because we are satisfied with (semi)group generators for the N-(endo)automorphisms, it is sufficient to search for images i to extend α on g under the representatives of the orbits of Γ under S′.

Then S and the list of N-endomorphisms that are computed by using Algorithm 2 iteratively generate all N-endomorphisms.

For those cases, where we have to expect that there are particularly many N-homomorphisms, namely, if Γ is a direct product of N-groups, we can find a representation of the N-homomorphisms in terms of the N-homomorphisms of smaller N-groups.

Proposition 9.2: Let N be zero-symmetric and Γ = H_{1} × H_{2} be the direct product of the N-groups H_{1} and H_{2}.

Then α is an N-endomorphism of Γ iff there exist α_{ij} ∈ Hom_{N}(H_{j}, H_{i}) such that α(x_{1}, x_{2}) = (α_{11}(x_{1}) + α_{12}(x_{2}), α_{21}(x_{1}) + α_{22}(x_{2})) with x_{i} ∈ H_{i}.

Proof: Straightforward generalization of the corresponding result for groups. □

10. Transformation Near-rings

Let Γ be a group, N ≤ M(Γ), and N = ⟨E⟩. If Γ is small (note that N still can be very big), then, by the methods discussed so far, we have no problems computing anything we want to know about the N-group Γ.

Now we turn to the problem of getting information about N itself. The trick is to transfer near-ring problems to N-group problems.

An element f of a near-ring N is called distributive on N iff f(g+h) = fg+fh for all f, h ∈ N. A near-ring is distributive iff all of its elements are distributive on N. Obviously, a near-ring is a ring iff it is abelian and distributive.

Of course, if f is an endomorphism of Γ, then it is distributive on N. But this condition is not necessary. We need a weaker one. Call f an N-piecewise endomorphism iff all restrictions of f to Nγ, γ ∈ Γ, are endomorphisms. Note that this notion, like distributivity, depends on the near-ring N involved.

Proposition 10.1: Let f ∈ N ≤ M(Γ). Then f ∈ N is distributive iff it is a piecewise endomorphism on N.

Proof: Let f be distributive and gγ, hγ ∈ Nγ. Then f(gγ + hγ) = f(g + h)γ = (fg + fh)γ = f(gγ) + f(hγ). So the restriction of f to Nγ is a homomorphism. Clearly f(gγ) = (fg)γ ∈ Nγ. Conversely, if f(g+h)γ = (fg+fh)γ for all γ ∈ Γ, then, using faithfulness, f(g + h) = fg + fh. Hence f is distributive. □

Note that the Nγ can be computed efficiently by Algorithm 1.

Remark 10.1: To test whether a mapping f is a homomorphism on a group Γ generated (as a group) by a set F, it is enough to test whether f(γ + φ) = f(γ) + f(φ) for all γ ∈ Γ, φ ∈ F. Thus the test has complexity O(|Γ| |F |).

Proposition 10.2: N ≤ M(Γ) is an abelian near-ring iff for each γ ∈ Γ the group Nγ is abelian.

Proof: Let fγ, gγ ∈ N. Then fγ + gγ = (f + g)γ = (g + f)γ = gγ + fγ if N is abelian. Conversely, for f, g ∈ N we have to show that (f + g)γ = (g + f)γ, for any γ, which again follows directly from Nγ being abelian. □

Proposition 10.3: An abelian near-ring N is distributive iff all its generators are distributive.

Proof: Let f, g ∈ N be distributive and a, b ∈ N. Then (fg)(a+b) = f(ga+gb) = (fg)a + (fg)b. Similarly, using that N is abelian, (f + g)(a + b) = f(a + b) + g(a + b) = fa + fb + ga + gb = fa + ga + fb + gb = (f + g)a + (f + g)b. □

Corollary 10.1: Within O(|Γ| |E|^{2}) operations, we can test whether N is a ring.

Many more properties can be tested efficiently by a reduction to the computation of some Nγ as before, e.g.:

Proposition 10.4: f ∈ N is in the center of N (i.e., commutes with all g ∈ N) iff f is distributive and commutes with all generators.

The algorithms in this section do not depend on having generators of N. It is enough to be able to compute orbits. We have seen that this works nicely for N_{0}, too, where only N is given by generators.

Corollary 10.2: We can test efficiently whether N_{0} is a ring.

Definition 10.1: Let Γ be a group, and let N ≤ M ≤ M(Γ). We say that N has the k-interpolation property with respect to M iff for all finite subsets A of Γ with |A| ≤ k and for all m ∈ M there exists an element n ∈ N such that n|_{A} = m|_{A}.

Remark 10.2: N has the 1-interpolation property with respect to M(Γ) iff Nγ = Γ for all γ ∈ Γ.

Thus, it is easy to test the 1-interpolation property. We observe that Γ × Γ is an N-group, too, by componentwise operation: n(γ_{1}, γ_{2}) = (nγ_{1}, nγ_{2}).

Proposition 10.5: N ≤ M(Γ) has the 2-interpolation property with respect to M(Γ) iff N(a, b) = Γ × Γ for all a, b ∈ Γ, a ≠ b.

Proof: The condition just means that, for an arbitrary pair (c, d) of values, there is some f ∈ N such that f(a) = c and f(b) = d. □

Corollary 10.3: Let ⟨E⟩ = N ≤ M(Γ). Then we can test the 2-interpolation property of N with respect to M(Γ) within O(|E| |Γ|^{2}) operations.

In fact, we can generalize these results to interpolation with respect to M_{D^{0}}(Γ), D a group of fixed-point-free automorphisms.

Theorem 10.1: Let D be a group of fixed-point-free automorphisms of Γ. Take a set A of orbit representatives according to the operation of D on Γ. Then, for k ≤ |A|, N ≤ M_{D^{0}}(Γ) has the k-interpolation property with respect to M_{D}(Γ) iff N(γ_{1}, …, γ_{k}) = Γ^{k} for each tuple (γ_{1}, …, γ_{k}) ∈ A^{k} (with all γ_{i} distinct).

Proof: By Theorem 8.2, each element of the centralizer near-ring is the unique extension of a function from A into Γ. Therefore, it is enough to interpolate the latter ones. □

Corollary 10.4: One can determine whether N = ⟨E⟩ has the k-interpolation property with respect to M_{D}(Γ), D fixed-point-free, within O(|E| |A|^{k}) operations, where A is a set of orbit representatives.

11. Realizability

Our solution of the k-interpolation problem (we use the notation as in Corollary 10.4) is useful only for really small k because |A| > 1 for all non-trivial cases. Note that for k ≥ |A|, the k-interpolation property just means N = M_{D}(Γ), which we would like to be able to decide. Therefore, we need a better method to do k-interpolation for k > 2. A different form of density result helps us.

Theorem 11.1: Let N be a sub-near-ring of M_{D^{0}}(Γ), (D a group of fixedpoint-free automorphisms), that has the 2-interpolation property with respect to M_{D^{0}}(Γ). If N is not a ring, then N = M_{D^{0}}(Γ).

Proof: This follows from Theorem 4.21 in Aichinger [1994] or from Algorithm 3. □

Note that the 2-interpolation property can be tested efficiently and that we can find out whether N_{0} is a ring.

Often we are not satisfied with the information that some f ∈ M_{D}(Γ) happens to be in N, but rather want to know how f can be realized, i.e., how it can be obtained from the generators using addition and composition.

Problem 11.1: [Completeness and Realizability] Let ⟨E⟩ = N ≤ M_{D}(Γ). Determine whether N = M_{D}(Γ) and, in the affirmative case, show how each f ∈ M_{D}(Γ) can be constructed from the generators, i.e., compute a term t in the free near-ring over E that realizes f.

Definition 11.1: A Kaiser multiplication for N ≤ M(Γ) is a bivariate function K: Γ × Γ → Γ such that

• K(γ, 0) = K(0, γ) = 0 for all γ ∈ Γ;

• K(α, β) ≠ 0 for some α, β ∈ Γ;

• K(f, g) ∈ N, for f, g ∈ N, where K(f, g)(γ) := K(f(γ), g(γ)) for all γ ∈ Γ.

In Algorithm 3, we need a Kaiser-multiplication for the case that N is not a ring. In fact, there is a very natural choice, the one that has has been constructed in Aichinger [1994]:

Proposition 11.1: If N is not a ring, then we can define a Kaiser multiplication K as follows:

• If (Γ, +) is not abelian, then we can find α and β in Γ with α + β ≠ β + α, and define K(γ_{1}, γ_{2}) := −γ_{1} − γ_{2} + γ_{1} + γ_{2}.

• If N is not distributive, then we can find f ∈ N, such that there are α, β ∈ Γ with f(α + β) ≠ f(α) + f(β). Then we define K(γ_{1}, γ_{2}) := f(γ_{1}) + f(γ_{2}) − f(γ_{1} + γ_{2}).

Corollary 11.1: Algorithm 3, which uses O(k^{2}) interpolations, together with appropriate book-keeping and our solution of the 2-interpolation problem, gives an efficient solution to the realizability problem for any fixed-point-free automorphism group D.

Algorithm 3 Interpolation Let ⟨E⟩ = N ≤ M_{D}(Γ), D a group of fixed-point free automorphisms, A a set of orbit representatives with respect to D, and K a Kaiser-multiplication for N. Require: A set S ⊂ A, γ ∈ A \ S, m ∈ M_{D}(Γ). Ensure: A term f satisfying f|_{S∪{γ}} = m|_{S∪{γ}} for all i = 1, …, n, γ ∈ A.

if |S| ≤ 2 then

Find f using 2-interpolation as in Proposition 10.5 else

Recursively find f_{1} such that f_{1}|_{S} = m|_{S}

Use the algorithm LagrangePoly below to find a term f_{2} such that

f_{2}(S) = 0 and f_{2}(γ) = m(γ) − f_{1}(γ). f := f_{2} + f_{1}

end if The following algorithm LagrangePoly solves a specific interpolation problem by a divide and conquer strategy. Require: A set S ⊂ A, γ ∈ A \ S, m ∈ M_{D}(Γ) with m(A) = 0. Ensure: A function f ∈ N satisfying f(S) = 0 and f(γ) = m(γ).

if |S| ≤ 2 then

Find f using 2-interpolation as in Proposition 10.5 else

Partition S into two smaller subsets S_{1}, S_{2}

Let α, β be such that K(α, β) ≠ 0

Recursively determine f_{1} such that f_{1}(S_{1}) = 0 and f_{1}(γ) = α f_{2} such that f_{2}(S_{2}) = 0 and f_{2}(γ) = β

h := K(f_{1}, f_{2})

Find g ∈ N such that g(0) = 0 and g(K(α, β)) = m(γ)

(using 2-interpolation again ) f := g ∘ h

end if

12. Conclusion

Our emphasis has been the study of sub-near-rings N of M(Γ), Γ small, that are given by a small number of generators but are potentially very big. Various efficient algorithms for problems in this area have been developed. Based on these, some interesting properties of N can be determined via its natural operation on Γ. As this topic is still rather new, the results in this article should be considered as a solid basis for further investigations.

The following problems have been solved only partially and seem to be really challenging.

Problem 12.1: Let Γ be a group and ⟨E⟩ = N ≤ M(Γ).

1. N-endomorphisms: Determine a (nearly) minimal set of semigroup generators for the set of all N-endomorphisms of Γ.

2. Membership: For any given f ∈ M(Γ), decide whether f ∈ N.

3. Size: Compute the Size of N.

This article contains a solution for problem 1 that is quite useful. For bigger groups that are not N-direct products but still have many N-endomorphisms, better methods are needed.

For the problems 2 and 3, we have presented a solution that is nice whenever Theorem 8.2 can be applied. Another partial solution is contained in Binder et al. [2000].

References

E. Aichinger. Interpolation with near-rings of polynomial functions. Master’s thesis, Johannes Kepler University Linz, Austria, 1994. Also available at http://www.algebra.uni-linz.ac.at/˜ erhard/.

E. Aichinger, F. Binder, J. Ecker, R. Eggetsberger, P. Mayr, and C. Nöbauer. SONATA: Systems Of Nearrings And Their Applications, Package for the group theory system GAP4. Johannes Kepler University Linz, Austria, 2000. Available from http://www.algebra.uni-linz.ac.at/sonata/.

F. Binder, E. Aichinger, J. Ecker, C. Nöbauer, and P. Mayr. Algorithms for near-rings of non-linear transformations. In C. Traverso, editor, Proceedings of ISSAC 2000, St. Andrews, Scotland, pages 23–29. ACM, 2000. Also available at http://www.algebra.uni-linz.ac.at/sonata/papers/.

James R. Clay. Nearrings: Geneses and applications. The Clarendon Press Oxford University Press, New York, 1992.

H.-Peter Gumm. An easy way to the commutator in modular varieties. Arch. Math. (Basel), 34(3):220–228, 1980.

J. D. P. Meldrum. Near-rings and their links with groups. Pitman (Advanced Publishing Program), Boston, MA, 1985.

Günter Pilz. Near-rings. North-Holland Publishing Co., Amsterdam, second edition, 1983.

S. D. Scott. Involution near-rings. Proc. Edinburgh Math. Soc. (2), 22(3):241– 245, 1979.

Charles C. Sims. Computational methods in the study of permutation groups. In Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967), pages 169–183. Pergamon, Oxford, 1970.