Algorithms for Near-rings of Non-linear Transformations ^{∗}

Franz Binder, Erhard Aichinger, J� urgen Ecker, Christof N� obauer, Peter Mayr

Department of Algebra Johannes Kepler University Linz, Austria

Franz.Binder@algebra.uni-linz.ac.at

ABSTRACT

In this note we present some algorithms to deal with nearrings, the appropriate algebraic structure to study non-linear functions. This is similar the role of rings in the theory of linear functions or that of groups for permutations. In particular, we give efficient algorithms that deal with big nearrings that are given by a small set of generators. In this context, generating involves composition as well as pointwise addition. In the extreme case, one transformation of a group of order n can generate a set of up to n^{n} transformations.

Categories and Subject Descriptors

F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—computations on discrete structures; I.1.2 [Symbolic and Algebraic Manipulation]: Algorithms—algebraic algorithms; G.2 [Mathematics and Computing]: Discrete Mathematics

General Terms

Algorithms

Keywords

Near-rings, Non-linear transformations, Groups

1. INTRODUCTION

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 [7, 6, 5].

Definition 1. A set N together with two binary operations + and · is called a near-ring if

∗This work has been supported by the Austrian National Science Foundation (Fonds zur Förderung der wiss. Forschung) under Grant P12911-INF. See

www.algebra.uni-linz.ac.at for details.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage, and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. ISSAC 2000, St. Andrews, Scotland

\begin{matrix}c \\ ◯ \end{matrix}2000 ACM 1-58113-218-2/ 00/ 0008 $5.00

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.

Let Γ be a group, and let M(Γ) be the set of all mappings (transformations) from Γ into Γ. 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. A subset N of M(Γ) is a sub-near-ring of (M(Γ), +, ·) if it is closed under +, −, and functional composition. We then write N ≤ M(Γ) and call it a transformation near-ring. In fact, every near-ring can be represented as a transformation near-ring on some group Γ, but we are primarily interested in the case where Γ is small and N (very) big.

If we are given transformations f_{1}, …, f_{r} on Γ, we would like to know how big the generated near-ring F = ⟨f_{1}, …, f_{r}⟩ is and whether a given transformation g: Γ → Γ lies in F. We notice that g ∈ F whenever it can be “built up” from f_{1}, …, f_{r}. Of course, because N is intended to be big, no straightforward enumeration is applicable. In fact, nearring theory tells us that a single transformation might on a group of size n might generate a near-ring as large as n^{n} ([8] contains many impressive examples). We note that a corresponding problem in group theory is solved via Sim’s stabilizing chains [10]. We have no comparable tool yet, but we can solve the membership problem in important special cases, thereby extending the cases solved by [3]. And we can solve satisfactorily a variety of related problems.

Definition 2. Let N be a near-ring. Then Γ together with an endomorphism Φ : N → M(Γ) is called an N-group. N operates on Γ by nγ := Φ(n)(γ). It operates faithfully if the endomorphism is injective.

Thus, N-groups correspond to modules in ring theory. Of course, if N operates faithfully on Γ, it can be identified with a sub-near-ring of M(Γ) and, conversely, every sub-near-ring of M(Γ) operates faithfully on Γ by function application.

A main endeavor of this note is to find methods to establish properties of near-rings just from a small set E of generators and to avoid the usually unfeasible task of enumerating all near-ring elements. Concretely this means that a nearring N operating on Γ might be very large, (up to |Γ|^{|Γ|}) but is given by a small set of generators E. We are looking for algorithms polynomial in |Γ| and |E|.

We can also interpret this situation in the language of systems theory: If we are given a set E ⊆ Γ^{Γ} of some building blocks, we consider all systems N that can be built from these using serial (composition) and parallel (addition) connections, i.e., N = ⟨E⟩. Typical questions in this context are:

Membership Can f be built from the blocks in E, i.e., is f ∈ N?

Realizability Can we realize all transformations using these building blocks, i.e., is ⟨E⟩ = M(Γ)? If so, how can we do this?

Reachability Which states can be reached using such systems, i.e., what is Nγ, for any γ ∈ Γ?

Linearity Does the system happen to be linear, i.e., is N a ring?

The last two questions will turn out to be quite easy to answer the second one gets a satisfactory solution using results from near-ring theory, whereas the first question, which at first might seem to be easier, turns out to be the hardest, and we can give only a partial solution for it.

In very contrast to ring theory, no attempt on an algorithmic treatment of near-ring theory has been done so far. Therefore, in a project funded by the Austrian Science Fonds, the share package SONATA for GAP 4 has been developed

(www.algebra.uni-linz.ac.at). This article contains a se-

lection of those algorithms developed as part of that project that are most interesting for transformation near-rings on finite groups.

2. ORBITS AND INTERPOLATION

First, let us attack the reachability problem. Its solution, though rather simple, is the basis of all other problems solved in this note.

Problem 1. (Reachability) Let N be a near-ring given by a set E of generators, Γ an N-group, and γ ∈ Γ.

1. Compute the orbit Nγ := { nγ | n ∈ N }.

2. For each η ∈ Nγ, find f ∈ N such that η = fγ.

The key result for an efficient solution of this basic problem is easy to establish. Note that a subgroup H of Γ is an Nsubgroup via the restriction of the operation of N on Γ iff NH ⊆ H.

Theorem 1. Let N be a near-ring generated by a set E and operating on a group Γ. Then a subgroup H of Γ is an N-subgroup iff EH ⊆ H. Proof. Because E ⊆ N, necessity is trivial. To prove sufficiency, call f ∈ N good iff fH ⊆ H. By the assumption, all elements in E are good. If f, g are good, then (f − g)γ = fγ − gγ ∈ H for all γ ∈ Γ, because H was assumed to be a subgroup. Thus f − g is also good. Similarly, fg is good, and so all elements in N are good.

This leads to an easy completion algorithm. Note that Nγ is the smallest N-subgroup of Γ containing Eγ.

Algorithm 1 Computing Orbits

Let N be a near-ring operating on the group Γ.

Require: A set E generating N; γ ∈ Γ.

Ensure: H = Nγ H := ⟨Eγ⟩ while EH ⊈ H do

H := ⟨H ∪ EH⟩ (generated subgroup) end while

Proposition 1. Algorithm 1 correctly computes Nγ within O(|E| |Nγ| ≤ O(|E| |Γ|) operations in Γ. In particular, the size of N does not matter.

Proof. Correctness is immediate from the theorem. For the bound, observe that the size of H, and therefore the computing time, doubles at each step in the loop. Thus the total complexity has the same order as that for the last step, which is O(|E| |Nγ|).

Note that the class of near-rings is defined by equations. Thus the whole theory for varieties applies, in particular, there are free near-rings over any set.

Corollary 1. With appropriate bookkeeping, for any η ∈ Nγ, Algorithm 1 can also compute f ∈ N such that η = fγ. In fact, it can also construct a term in the free near-ring generated over E that represents f.

Proof. The necessary bookkeeping is straightforward. In the first step, each element of H has the form eγ, e ∈ E, thus has an appropriate representation by definition. If for each element η ∈ H we have a representation η = f_{η}γ, then for each element eη ∈ EH, we use f_{eη} := ef_{η}. Similarly, if η = η_{1} + … + η_{m}, then we use f_{η} = f_{η_{1}} + … + f_{η_{m}}.

Given γ, η ∈ Γ, the statement η ∈ Nγ means that there is an f ∈ N such that f(γ) = η. This leads us to the following problem very common in near-ring theory.

Problem 2. (k-Interpolation) Given a sequence (γ_{1}, η_{1}), …, (γ_{k}, η_{k}) of points in Γ × Γ and a near-ring N operating on Γ, we want to know whether there is (and if so, find) a function f ∈ N such that f(γ_{i}) = η_{i} for all i = 1, …, n.

Obviously, Algorithm 1 solves the 1-interpolation problem. In fact, the same algorithm can also be used to solve higher interpolation problems, as can be easily seen as follows. If Γ is an N-group then Γ^{2} is an N group, too, in a natural way by defining the operation as f(a, b) := (fa, fb). Similarly each Γ^{k} is an N-group. With this definition, (c, d) ∈ N(a, b) just means that there exists f ∈ N such that f(a) = c and f(b) = d, which is the 2-interpolation property.

Proposition 2. The k-interpolation problem can be solved within O(|E| |Γ|^{k}) operations.

Proof. This follows immediately from Proposition 2.2, using the operation defined above and applying Algorithm 1 to compute N((γ_{1}, …, γ_{k})) and to decide whether (and find out how) (η_{1}, …, η_{k}) is in this orbit.

Thus, the k-interpolation-problem can be solved in time polynomial in |E| and in |Γ|. Unfortunately, the solution is exponential in k. In particular, for the |Γ|-interpolation problem, which just means to test whether a given transformation is in N, we only get the bound O(|E| |Γ|^{|Γ|}), which essentially means to enumerate all elements of N. But see Section 8 for a different approach that works in many important cases.

3. FINDING THE IDENTITY IN A NEAR-RING OF TRANSFORMATIONS

A near-ring need not have an identity. Thus we need a method to find out whether a near-ring contains an identity, and, in the affirmative case, how it looks like. We give a solution for near-rings N faithfully operating on a group Γ. Without loss of generality, we assume that N ≤ M(Γ). Again, think of Γ to be small, and N to be big, but generated by a small subset E.

Clearly, if the identity transformation id is an element of N, the near-ring has an identity and it is id. The converse, in general, is not true, as the following counterexample demonstrates:

Example 1. Let Γ = ℤ_{2} × ℤ_{2} be Klein’s 4-group and N = ({¯0, π_{1}}, +, ∘), where ¯0 denotes the zero mapping, and π_{1} the projection onto the first component, i.e., π_{1}(x, y) = (x, 0). Then N is a near-ring with identity π_{1}, in fact it is isomorphic to the residue class field of integers modulo 2. But π_{1} ≠ id_{ℤ_{2}×ℤ_{2}}

Nevertheless, the identity in N (if it exists) cannot be too far from the identity transformation. We are going to develop some necessary conditions for a transformation i to be the identity of N.

First, we use that i is a left identity. Thus, for all n ∈ N, and all x ∈ Γ, we have i(nx) = (in)x = nx. Hence

i|_{NΓ} = id|_{NΓ}  (1)

is a necessary condition for i to be the near ring’s identity. This means that at least on NΓ it has to behave like the identity mapping. And NΓ can be computed efficiently by Algorithm 1.

Next, we use that i is a right identity. Thus, for all f ∈ N and all x ∈ Γ, we have f(ix) = (fi)x = fx, or, equivalently, ix ∈ f^{−1}({fx}). So ix ∈ I_{x} := NΓ ∩ ⋂_{f∈N} f^{−1}({fx}).

Of course, we cannot compute such an intersection if we want to avoid computing all elements of N. Fortunately, the condition f(ix) = fx only has to be tested for the set E of generators of N, because from f(ix) = fx and g(ix) = gx, we get immediately that fg(ix) = fgx and (f + g)(ix) = (f + g)x. Thus we just have to go through the elements of NΓ and find out all the elements y for which fy = fx for all f ∈ E.

Finally, we use that i must take some unique value for each x ∈ Γ. Thus, if for some x ∈ Γ the set I_{x} is empty, N cannot have an identity. Similarly, if I_{x} contains more than one element for some x ∈ Γ, N cannot have an identity, too: Suppose, a, b ∈ I_{x}. Then a, b ∈ NΓ and ∀ n ∈ N: na = nx = nb. In particular, ia = ib. But a and b are from NΓ (whereupon i acts as identity transformation, by (1)), so a = ia = ib = b.

Summarizing, if N is generated by E, then

∀x ∈ Γ: I_{x} := |NΓ ∩ ⋂_{n∈E} n^{−1}(nx)| = 1.  (2)

and I_{x} = {i(x)} is the single element. Conversely, if this condition is satisfied, we define i(x) as the unique element of I_{x}. If this i is contained in N, it is its identity. Otherwise N has no identity.

Condition (2) uniquely determines ix at every point x (or contradicts the existence of an identity). If the candidate i computed using (2) happens to be an element of N, then it is the identity of N. This is formulated in Algorithm 2.

Algorithm 2 Identity

Let N be a near-ring of transformations on the group Γ. Require: E a set of generators of N. Ensure: Find an identity, if there is one.

for x ∈ Γ do I_{x} := ⋂_{n∈E}(NΓ ∩ n^{−1}nx); if |I_{x}| ≠ 1 then

return (N has no identity); end if Define i(x) to be the unique element in I_{x}.

end for

if i ∈ N or N contains an identity then

return (i is the identity of N); else

return (N has no identity); end if

So, for a near ring of transformations on a group, we can find its identity (if it has one) and the decision problem of testing whether is has one has been reduced to the problem of deciding membership of a single transformation. The complexity of this reduction is the same as the complexity of computing NΓ.

4. LINEARITY

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 its elements are distributive on N. It is called abelian iff the addition is commutative. Obviously, a near-ring is a ring iff it is abelian and distributive.

Again, we take a small group Γ and a (probably big) nearring N ≤ M(Γ) generated by a small set E. Of course, if f is an endomorphism of Γ then it is distributive. But this condition is not necessary. We need a weaker one. Call f a piecewise endomorphism on N iff all restrictions of f to Nγ, γ ∈ Γ, are endomorphisms. Note that this notion, like distributivity, depends on the near-ring N involved.

Proposition 3. 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 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 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 4. N is an abelian near-ring iff all Nγ are abelian groups. 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)γ, which again follows directly from Nγ being abelian.

Corollary 2. We can test whether N is a ring using O(|Γ| |E|^{2}) operations. Proof. A near-ring is a ring iff it is abelian and all its generators are distributive.

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

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

Our test for distributivity is generalized in Section 7.

5. 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 3. Let N be a near-ring and Γ an N-group. For f ∈ N, 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 Γ^{Γ}. In particular, Δfx ∈ Γ^{Γ}. This operator is also useful in the case Γ = N, i.e., if N itself is considered as an N-group via the multiplication of N (just as a ring might be considered as a module over itself).

Proposition 6. With the notation of the definition we have

Δfx(a + b) = Δfxa + Δf(x + a)b,  (quasi-linearity) (3)

Δf(x + a)b = −Δfxa + Δfx(a + b). (translation rule) (4)

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

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

Of course, the definition of the difference operator is to 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 (3), however, suggests that it is not too far away. In particular, if we know the difference in directions generating G (as a group), then we know it in any direction. This is similar to partial derivatives. On the other hand, the equivalent equation (4) 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. The following proposition again suggests a very close connection.

Proposition 7. The operator Δ fulfills the following chain rule:

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

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

Some essential properties occurring in near-ring theory [9] can be expressed easily using the difference operator:

Definition 4. A faithful N-group Γ is

1. tame iff ∀f ∈ N, ∀x ∈ Γ, ∀a ∈ Γ ∃f′ ∈ N such that Δfxa = f′a;

2. k-tame iff ∀f ∈ N, ∀x ∈ Γ, ∀a_{1}, …, a_{k} ∈ Γ ∃f ∈ N′ such that Δfxa_{i} = f′a_{i}, ∀i = 1, …, k;

3. compatible iff ∀f ∈ N, ∀x ∈ Γ ∃f ∈ N′ such that Δfxa = f′a, ∀a ∈ Γ.

Thus, compatible means that Δfx (∈ Γ^{Γ}) operates in the same way as some f′ ∈ N, meaning something similar to differentiability. Similarly, k-tame means that Δfx can be interpolated at k places by some element in N. Of course, tame just means 1-tame, and can also be expressed as the reachability problem Δfxa ∈ Na. The following proposition reduces the tameness test to testing the generators of the near-ring.

Proposition 8. Let E be a set of generators of the nearring N. Then a faithful abelian N-group Γ is tame iff ∀f ∈ E, ∀x ∈ Γ, and ∀a ∈ Γ: Δfxa ∈ Na; Proof. Only sufficiency is non-trivial. Suppose that f and g fulfill the condition. Then Δ(f − g)xa = Δfxa − Δgxa ∈ Na−Na = Na and, applying (5), Δ(fg)xa = Δf(gx)Δgxa = f′(g′a) = (f′g′)a ∈ Na.

Corollary 3. We can test whether a faithful abelian Ngroup Γ is tame within O(|E|^{2} |Γ|) multiplications Proof. By the proposition, the property in the definition of tameness just has to be tested for all generators.

Corollary 4. We can test whether a faithful abelian Ngroup Γ is k-tame within O(|E|^{k+1} |Γ|) multiplications. Proof. Instead of the 1-interpolation problems before, we are faced with k-interpolation problems here.

Proposition 9. Testing whether a transformation nearring N (on Γ) generated by a set E is compatible reduces to O(|E| |Γ|) membership problems. Proof. We just have to test whether Δfx ∈ N, for all points x ∈ Γ and generators f ∈ E.

6. COMPLETENESS AND REALIZABILITY

We continue considering a transformation near-ring N ≤ M(Γ) given by a set E of generators.

It is natural to ask, whether E already generates the full transformation near-ring, i.e., whether N = M(Γ). Certainly, this will not be the case if all generators are zerosymmetric, i.e., if E0 = {0}, because this property is preserved by addition and composition. In this case, we better to ask whether all zero-symmetric transformations can be generated, i.e., whether N = M_{0}(Γ) := { f ∈ M(Γ) | f(0) = 0 }.

Problem 3. (Completeness) Let N ≤ M(Γ) be a near-ring given by a set E of generators.

If N is zero-symmetric, decide whether N = M_{0}(Γ), otherwise whether N = M(Γ).

Let Γ be a group, and let N be a sub-near-ring of M(Γ). We say that N has the k-interpolation property iff for all finite subsets Ω of Γ with |Ω| ≤ k and for all mappings m: Ω → Γ there exists an element f ∈ F such that f|_{Ω} = m. It has the k-interpolation property with respect to M_{0}(Γ) if it is enough to interpolate all zero-symmetric mappings m ∈ M_{0}(Γ).

Of course, as we only consider the case that Γ is finite, the |Γ|-interpolation property means that N = M(Γ), and if N is zero-symmetric, then N = M_{0}(Γ) is the same as the |Γ|−1 interpolation-property with respect to M_{0}(Γ).

Using our solution to the k-interpolation problem (Proposition 2.4) we can see that the k-interpolation property can be solved within O(|E|)|Γ|^{2k+1}|F |^{2}, where F is a set of generators for the group Γ: it is enough to test all interpolation Problems of the form f(γ_{1}) = η_{1}, …, f(γ_{k}) = η_{k} with γ_{i} ∈ Γ, η_{i} ∈ F. This bound is polynomial in all variables, except in k. In particular, we cannot really solve the completeness problem this way.

At this point, classical near-ring theory can help us, as it provides the following density theorems:

Theorem 2. If N has the 2-interpolation property and N_{0} := {f ∈ N | f0 = 0} is not a ring, then N has the k-interpolation property for all k ∈ ℕ.

Note that the 2-interpolation property can be tested efficiently. Usually, it is not difficult to establish that N_{0} is not a ring. But in some cases this may be difficult to test, and we have to use a similar theorem.

Theorem 3. If N has the 3-interpolation property and there is an element γ ∈ Γ with γ + γ ≠ 0, then N has the kinterpolation property for all k ∈ ℕ.

If this does not help either, we have to resort to interpolation on 4 places, which has no additional requirements and still provides a polynomial-time algorithm.

Theorem 4. If N has the 4-interpolation property, then N has the n-interpolation property for all n ∈ ℕ.

Proofs for these classical results are contained in [2, 1].

For the 0-symmetric case, it is sometimes enough to test for the 1-interpolation property.

Theorem 5. Let Γ be a group with |Γ| ≥ 3, and let N be a sub-near-ring of M_{0}(Γ). Then N has the k-interpolation property for all k ∈ ℕ with respect to M_{0}(Γ) iff

1. N has the 1-interpolation property with respect to M_{0}(Γ),

2. N is not a ring,

3. There is no fixed point free group automorphism α ≠ id of (Γ, +) of prime order such that ∀f ∈ N: αf = fα.

An automorphism α of (Γ, +) is called fixed point free iff α(γ) = γ implies γ = 0. The order of α is the smallest positive k with α^{k} = id. Theorem 6.4 can be proved using the description of 0-primitive near-rings in [4] or [1, Theorem 4.21].

If these requirements cannot be established, we can always resort to the 2-interpolation property.

Theorem 6. Let N be a sub-near-ring of M_{0}(Γ) that has the 2-interpolation property with respect to M_{0}(Γ). If N is not a ring, then N has the k-interpolation property with respect to M_{0}(Γ) for all k ∈ ℕ.

Often we will not be satisfied with the information that some f ∈ M(Γ) 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 4. (Realizability) Suppose that M(Γ) is generated by a set E of generators and let f ∈ M(Γ). Compute a term t in the free near-ring over E that realizes f.

Suppose, e.g., that completeness of the near-ring generated by E was established by Theorem 6.1. The constructive proof of this theorem by [1] can be used to solve the realizability problem in this case, as described in Algorithm 3.

For this algorithm we will need a binary term (“multiplication”) K on Γ such that K(γ, 0) = K(0, γ) = 0 for all γ ∈ Γ, but K(α, β) ≠ 0 for some α, β ∈ Γ. In our case, these can be found as follows. If (Γ, +) is not abelian, then we can take α and β in Γ with α + β ≠ β + α, and define K(γ_{1}, γ_{2}) := −γ_{1}−γ_{2}+γ_{1}+γ_{2}. Otherwise, from establishing Theorem 6.1, we know how to construct (from the generators in E) a transformation f ∈ M_{0}(Γ), such that there are α, β ∈ Γ with f(α + β) ≠ f(α) + f(β). Then we can take these together with K(γ_{1}, γ_{2}) := f(γ_{1}) + f(γ_{2}) − f(γ_{1} + γ_{2}).

Algorithm 3 takes a finite subset

S := {(γ_{1}, η_{1}), (γ_{2}, η_{2}), …, (γ_{k}, η_{k})}

(all γ_{i} different) of Γ×Γ, and returns a term f (built from the generators in E) such that f(γ_{i}) = η_{i} for i = 1, 2, …, k. We assume that we have an algorithm InterpolateAtTwo that produces this f if S has at most two elements. Proposition 2.4 (with full book-keeping, of course) can be used for this purpose.

Algorithm 3 Interpolation Require: A set { (γ_{i}, η_{i}) | i = 1, …, k } of points in Γ × Γ. Ensure: A term f satisfying f(γ_{i}) = η_{i} for all i = 1, …, n.

if k ≤ 2 then

return InterpolateAtTwo(S) else

(* Interpolate recursively on k − 1 points *) s_{1} := Interpolation[{(γ_{i}, η_{i}) | i = 1, 2, …, k − 1}] s_{2} := LagrangePoly({(γ_{i}, 0) | i = 1, 2, …, k − 1}∪

{(γ_{k}, η_{k} − s_{1}(γ_{k}))})

return s_{2} + s_{1} end if

The following algorithm LagrangePoly solves a specific interpolation problem by a divide and conquer strategy. Require: A set { (γ_{i}, η_{i}) | i = 1, …, k } of points in Γ × Γ

with η_{1} = ⋯ = η_{k−1} = 0. Ensure: A function f satisfying f(γ_{i}) = η_{i} for all i =

1, …, k.

if k ≤ 2 then

InterpolateAtTwo(S) else

Partition {1, …, k − 1} into two smaller subsets X, Y p_{1} := LagrangePoly({(γ_{i}, 0) | i ∈ X} ∪ {(γ_{k}, α)}) p_{2} := LagrangePoly({(γ_{i}, 0) | i ∈ Y } ∪ {(γ_{k}, β)}) (* Multiply using K *) h := K(p_{1}, p_{2}) g := InterpolateAtTwo[{(0, 0), K(α, β), η_{k})}]

end if

return g ∘ h

Note that this algorithm just needs O(k^{2}) interpolations on 2 places. Similar algorithms can be used to solve the realizability in the cases where one of the other density theorems is applicable.

Theorem 7. The Realizability problem can be solved in polynomial time.

7. DEGREE

Considering real functions, we know that a polynomial has degree n iff its (n + 1)st derivative is the first one that vanishes.

We do something similar using the difference operator, which in fact can be iterated in the following way. The definition is motivated by the formal rule Δ^{n+1}f = Δ(Δ^{n}f).

Definition 5. 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 2. If Γ is abelian, then Δ^{n} is symmetric in the last n arguments.

Remark 3. By the translation rule, Δf = 0 iff Δ^{n}f0 = 0 iff Δ^{n}fx = 0 for some x.

Remark 4. An element f in a near-ring is constant (i.e., satisfies fg = f for all g) iff Δf = 0. It is affine (i.e., f − f0 is distributive) iff Δ^{2}f0 = 0. Here, we have considered N to operate over itself.

Definition 6. An element f in a near-ring N has degree n

iff Δ^{n+1}f0 \underbrace{N … N}_{n+1} = 0 but Δ^{n}f0 \underbrace{N … N}_{n} ≠ 0.

Example 2. Let R be an integral domain. Then the notion of degree in the near-ring (R[x], +, ∘), according to the above definition, coincides with the usual definition.

Theorem 8. If a near-ring N operates faithfully on a group Γ, then each f ∈ N has degree at most n iff it operates on Γ piecewisely like a function of degree at most n, i.e, iff Δ^{n+1}a0(Nγ)...(Nγ) = {0}, for each γ ∈ Γ. Proof. We proceed exactly as in the test for distributivity. Suppose f has degree at most n. Let f_{1}γ, …, f_{n}γ ∈ Nγ. Then, using the distribute law, Δ^{n+1}a0(f_{1}γ, …, f_{n}γ) = Δ^{n+1}a0(f_{1}, …, f_{n})γ = 0γ = 0. Conversely, to prove that Δ^{n+1}a0(f_{1}, …, f_{n}) = 0 (this is an equation over N) disappears we have to show that how that Δ^{n+1}a0(f_{1}, …, f_{n})γ for all γ ∈ Γ, which is true by the same equality as above.

Remark 5. Again, instead of testing Δ^{n+1}a0(Nγ)...(Nγ) = {0}, it is enough to test Δ^{n+1}a0(Mγ)F...F = {0}, if F generates Nγ. Thus the complexity of this test is in O(|Γ| |F |^{n}).

8. MEMBERSHIP

One of the most natural problems arising in the context of transformation near-rings is the following.

Problem 5. (Membership) Let N ≤ M(Γ) be given by a set of generators E. For any f ∈ M(Γ) test whether f ∈ N.

This turns out to be the hardest of our problems and we cannot give a completely satisfactory answer, but one that is acceptable in many important cases.

The idea is to compute a set A of additive generators for N, i.e., ones that generate N as a group. Then we can use all the method’s known from computational group theory to solve problems about N, e.g., computing its size and solving the membership problem.

Translated to the language of systems theory, additive generators correspond to building blocks from which all transformations in N can be built using only parallel connections.

Things are particularly easy if all generators of the near-ring are distributive. Then additive generators can be computed successively by an easy closure algorithm: E_{0} := E, E_{1} := E_{0} ∪ EE_{1}, E_{2} := E_{1} ∪ EE_{2}, ..., until this process becomes stable. Essentially the same method works if the generators turn out to have degree 1. The basic idea here is that we need not compute E(E + E), E(E + E + E), … because from Δ^{2}e0fg = 0, i.e., −eg +e0−ef +e(f +g) = 0, we know that e(f + g) = eg − e0 + ef, and thus e(f + g) happens to be in the additive closure of ef, eg, and e0.

There is a generalization for near-rings generated by elements of small degree:

Theorem 9. Let E be a set of near-ring generators of N of degree at most n. Define E_{0} = E, E_{i+1} := E_{i} ∪ E(E_{i} + ... + E_{i}) (n-fold sum). If E_{k} = E_{k+1}, for some k, then E_{k} generates N additively.

Proof. The case n = 1 has been shown above. We show the important case n = 2 (“quadratic functions”). We have 0 = Δ^{3}e0fgh = −Δ^{2}e0gh + Δ^{2}efgh = −e(g + h) + eg − e0 + eh−e(f +h)+ef −e(f +g)+e(f +g +h) and again see that e(f + g + h) can be isolated and thus is already contained in the group generated by E0 ∪ E^{2} ∪ (E + E). We omit the general induction proof.

Thus we need O(|E| |A|^{n}) steps to compute a set A of additive generators for N. Of course, this solution by far does not have the efficiency of all the other algorithms presented in this note, in particular there is no good bound for |A|. Nevertheless, even in its most simple version, for n = 1, this method has already solved some problems previously open [3].

Some optimizations are possible, e.g., if the elements in E = {e_{1}, ..., e_{m}} have different degrees, say n_{1}, ..., n_{m}, then it is enough to compute all the e_{ν}(E_{i} + ... + E_{i}) (where the sum is only n_{ν}-fold) instead of E(E_{i} + ... + E_{i}) with the n-fold sum.

9. CONCLUSION

Various problems for computing with transformation nearrings have been considered. Most of them have got very satisfactory solutions, as everything can be done with the near-ring generators and we are able to compute with nearring of a size where group theoretic algorithms could not be applied any more. The membership problem turned out to be much harder and we had to resort to the computation of additive generators, thus reducing the problem to computations with the additive group structure. On the other hand, we can decide whether the full transformation near-ring is generated and how we can realize arbitrary functions also in this case.

10. REFERENCES

[1] E. Aichinger. Interpolation with near-rings of polynomial functions. Master’s thesis, University of Linz, 1994.

[2] E. Aichinger. Local interpolation near-rings as a frame-work for the density theorems. In Contributions to General Algebra, volume 9, pages 27 – 36. Verlag Hölder-Pichler-Tempsky, Wien - Verlag B.G. Teubner, Stuttgart, 1995.

[3] E. Aichinger and C. Nöbauer. The cardinalities of the endomorphism near-rings I(G), A(G), and E(G) for all groups G with |G| ≤ 31. In G. Saad and M. J. Thomsen, editors, Near-rings, near-fields and K-loops, pages 175–178. Kluwer Acad. Publisher, 1997.

[4] G. Betsch. Primitive near-rings. Math.Z., 130:351–361, 1973.

[5] J. Clay. Nearrings: Geneses and Applications. Oxford University Press – Oxford, New York, Tokyo, 1992.

[6] J. D. P. Meldrum. Near-rings and their links with groups, volume 134 of Research Notes in Mathematics. Pitman Publishing Ltd., 1985.

[7] G. F. Pilz. Near-Rings. The Theory and its Applications, volume 23 of North-Holland Mathematics Studies. North-Holland Publishing Company, Amsterdam, New York, Oxford, revised edition, 1983.

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

[9] S. D. Scott. Tame near-rings and N-groups. Proc. Edinburgh Math. Soc. (2), 23(3):275–296, 1980.

[10] C. Sims. Computational methods in the study of permutation groups. In J. Leech, editor, Computational problems in abstract algebra, Conf. Oxford, pages 169–183, 1970.