PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 87(101) (2010), 39–58 DOI: 10.2298/PIM1001039K

PARASTROPHICALLY EQUIVALENT QUASIGROUP EQUATIONS

Aleksandar Krapež and Dejan Živković

Communicated by Žarko Mijajlović

Abstract. Fedir M. Sokhats’kyi recently posed four problems concerning parastrophic equivalence between generalized quasigroup functional equations. Sava Krstić in his PhD thesis established a connection between generalized quadratic quasigroup functional equations and connected cubic graphs. We use this connection to solve two of Sokhats’kyi’s problems, giving also complete characterization of parastrophic cancellability of quadratic equations and reducing the problem of their classification to the problem of classification of connected cubic graphs. Further, we give formulas for the number of quadratic equations with a given number of variables. Finally, we solve all equations with two variables.

1. Introduction

We study generalized quadratic functional equations on quasigroups. These are equations s = t, where each variable appears exactly twice in s = t and each operational symbol is assumed to be a quasigroup operation on a (fixed) set.

A fundamental problem in this class of equations is to investigate their structure and classify them accordingly. Our main tool in this endeavor is a cubic graph representation of the equations. In the first part of the paper we consider parastrophic equivalence as one criterion to classify quadratic equations. The second part of the paper begins a systematic classification of the equations with one and two variables based on their corresponding graphs.

The paper is organized as follows. We review necessary definitions and facts about quasigroups, quasigroup functional equations and graphs in Sections 2, 3 and

2010 Mathematics Subject Classification: Primary: 39B52, Secondary: 20N05, 05C25. Key words and phrases: quasigroup, quadratic functional equation, cubic graph, parastrophic

equivalence, parastrophic cancellability.

We have benefited from our discussions with Slobodan Simić and gratefully acknowledge his help. Our gratitude goes also to an anonymous referee whose remarks helped to improve the paper. The first author is supported by grants 144013 and 144018 of the Ministry of Science and Technology of Serbia.

4, respectively. In Section 5 we consider a connection between generalized quadratic quasigroup functional equations and connected cubic graphs. The four problems of Sokhats’kyi are presented in Section 6. In this section we also prove our main result about the full characterization of parastrophic (un)cancellability of equations. Section 7 is devoted to the calculation of the number of generalized quadratic equations for a given number of variables. Section 8 starts with a brief discussion of the degenerate case of the equation with one variable, and then proceeds to a full treatment of the equations with two variables giving general solutions to all nine of these equations.

2. Quasigroups

A quasigroup is a natural generalization of the concept of group. Quasigroups differ from groups in that they need not be associative.

Definition 2.1. We say that a groupoid (S; ·) is a quasigroup if for all a, b ∈ S there are unique solutions x, y ∈ S to the equations x · a = b and a · y = b.

A loop is a quasigroup with an identity element e, which satisfies the identities e · x = x · e = x. An associative quasigroup is a group.

Quasigroups are important algebraic (combinatorial, geometric) structures arising in various areas of mathematics and other disciplines. We mention just a few of their applications:

• in combinatorics (as latin squares, see Dénes and Keedwell [4])

• in geometry (as nets/webs, see Belousov [3] and [4])

• in statistics (see Fisher [6] and [4])

• in coding theory and cryptography (see [4])

• in special theory of relativity (see Ungar [20]) It is well known (see Belousov [3]) that a net can be coordinatized by an

ortogonal system of quasigroups. Closure conditions in nets correspond to some (systems of) equations in their coordinate quasigroups. The equations are not always quadratic, the case we are particularly interested in, but when they are, they can be solved using methods developed mainly by Krstić [14] and described in this paper.

The other typical application of generalized quasigroup equations is within the theory of quasigroups. Let s = t be a quadratic equation expressing a property of a quasigroup ·. We consider the generalized version of s = t in which each occurrence of operation · (or \, /) is replaced by a new operational symbol so that no symbol appears more than once. This new equation often gives us important information about · – usually that it is isotopic to some group.

∗ ∗ ∗ Whenever unambiguous, a term like x · y is shortened to xy. Also, if many

quasigroup operations are defined on the base set S, they are denoted by capital letters.

A quasigroup operation · is often considered together with its inverse operations: left (\) and right (/) division. The inverse operations are defined by: xy = z iff x\z = y iff z/y = x. Both of the inverse operations are also quasigroups. However, the inverse operations of a loop (group) operation need not be loops (groups).

It is often convenient to say that the operation · itself is a quasigroup, assuming the underlying base set S and the division operations.

Definition 2.2. A triple groupoid (S; ·, \, /) is an equational quasigroup (also known as equasigroup or primitive quasigroup) if it satisfies the following axioms:

x\xy = y,  xy/y = x,
x(x\y) = y ,  (x/y)y = x

If it further satisfies x\x = y/y (i.e., if the operation · is a loop operation) we have an equational loop.

The systems of quasigroups (loops) and equational quasigroups (loops) are equivalent, but the advantage of the latter is that it defines a variety.

Definition 2.3. The dual operations of ·, \, / are:

x ∗ y = yx,  x\\y = y\x,  x//y = y/x

These are also quasigroup operations, and the six operations ·, \, /, ∗, \\, // are said to be parastrophes (or conjugates) of each other.

We use the notation x ∘ y so that the symbol ∘ stands for either one of the operations · or ∗. Similarly, in x ⋄ y the symbol ⋄ stands for one of the operations ·, \, /, ∗, \\, or //.

When we use the prefix notation for operations and a quasigroup operation is A, we define: A(x_{1}, x_{2}) = x_{3} iff A^{(1)}(x_{1}, x_{2}) = x_{3} iff A^{(12)} (x_{2}, x_{1}) = x_{3} iff A^{(13)} (x_{3}, x_{2}) = x_{1} iff A^{(23)} (x_{1}, x_{3}) = x_{2} iff A^{(123)} (x_{2}, x_{3}) = x_{1} iff A^{(132)} (x_{3}, x_{1}) = x_{2}. In general, A(x_{1}, x_{2}) = x_{3} iff A^{σ}(x_{σ(1)} , x_{σ(2)} ) = x_{σ(3)} for σ ∈ S_{3} (symmetric group in three elements).

Definition 2.4. If (S; ·) and (T; ×) are quasigroups and f, g, h : S → T are bijections such that f(xy) = g(x) × h(y), then we say that (S; ·) and (T; ×) are isotopic and that (f, g, h) is an isotopy.

Isotopy is a generalization of isomorphism. The isotopic image of a quasigroup is again a quasigroup. Every quasigroup is isotopic to some loop. A loop isotopic to a group is isomorphic to it. If two quasigroups are isotopic, so are their corresponding parastrophes.

Definition 2.5. Two quasigroups are isostrophic if one of them is isotopic to a parastrophe of the other.

All these relations are equivalences between quasigroups. Isomorphism is a finer relation than isotopy, which in turn is finer than isostrophy.

3. Functional equations on quasigroups

We use (object) variables x_{1}, x_{2}, . . .. However, we also use x, y, z, u, v, w in formulas with a small number of variables. Operation symbols (i.e. functional variables) are F_{1}, F_{2}, …, but we use A, B, C, … in formulas with a small number of operation symbols. We assume that all operation symbols represent quasigroup operations and that if a symbol A is used, we also have symbols for the parastrophes of A.

Definition 3.1. A functional equation is an equality s = t, where s and t are terms with symbols of unknown operations occurring in at least one of them.

We write Eq[F_{1}, …, F_{n}] to emphasize that all operation symbols of the equation Eq are among F_{1}, …, F_{n}.

Definition 3.2. A solution to the functional equation Eq[F_{1}, …, F_{n}] on a set S is a sequence Q_{1}, …, Q_{n} of quasigroup operations on S such that Eq[Q_{1}, …, Q_{n}] is identically true on S.

A general solution to the equation Eq is a sequence of formulas

F_{i} = t_{i}(p_{1}, …, p_{m}), (1 ⩽ i ⩽ n),

with parameters p_{1}, …, p_{m}, such that Eq[t_{1}, …, t_{n}] is identically true on S and such that every solution to the equation Eq can be obtained by specifying the values of parameters.

The equation Eq is consistent if it has at least one solution. Obviously, every functional equation has a solution on any one–element set. This solution is called trivial and except for proving consistency it is quite uninteresting. We further assume that solutions of functional equations are algebras of quasigroups on a given but otherwise unspecified set S with more than one element.

Definition 3.3. The length |t| of the term t is the number of occurrences of object variables in it. Formally:

– If t is a variable, then |t| = 1.

– If t = t_{1} ⋄ t_{2}, then |t| = |t_{1}| + |t_{2}|. The length of the equation s = t is |s| + |t|.

We define an order between terms that contain only the operation symbol ·.

Definition 3.4. The order ◁ between terms is defined as follows:

– If |s| < |t|, then s ◁ t.

– For variables x_{i} and x_{j}, x_{i} ◁ x_{j} iff i < j.

– If |s| = |t|, s = s_{1} · s_{2}, t = t_{1} · t_{2} and s_{1} ◁ t_{1}, then s ◁ t.

– If |s| = |t|, s = s_{1} · s_{2}, t = s_{1} · t_{2} and s_{2} ◁ t_{2}, then s ◁ t.

Additionally, if we use x, y, z, u, v, w as variables, we assume x ◁ y ◁ z ◁ u ◁ v ◁ w. Note that, if we restrict ourselves to one type of variables (either from the set {x_{1}, x_{2}, …} or from the set {x, y, z, u, v, w}), the relation ◁ is a total order.

Definition 3.5. The term t is linear if every object variable appears exactly once in t. The functional equation s = t is linear if both s and t are linear.

Definition 3.6. The functional equation s = t is quadratic if every object variable appears exactly twice in s = t. The equation is balanced if every object variable appears exactly once in s and once in t.

Obviously, a quadratic functional equation is balanced iff it is linear.

Definition 3.7. Functional equation s = t is generalized if every functional variable F of s = t (including all parastrophes of F) appears only once in s = t.

Example 3.1. The following are various functional equations.

xy · z= x · yz  (associativity)
xy · zu= xz · yu  (mediality)
xy · zu= (xz · y)u  (pseudomediality)
x · yz= xy · xz  (left distributivity)
xy · yz= xz  (transitivity)
A(B(x, y), z) = C(x, D(y, z))  (generalized associativity)
A(B(x, y), C(z, u)) = D(E(x, z), F (y, u))  (generalized mediality)
A(B(x, y), C(z, u)) = D(E(F (x, z), y), u)  (generalized pseudomediality)
A(x, B(y, z)) = D(E(x, y), F (x, z))  (generalized left distributivity)
A(B(x, y), C(y, z)) = D(x, z)  (generalized transitivity)

Associativity, mediality and pseudomediality (generalized or not) are balanced, transitivity is quadratic but not balanced, and left distributivity is not even quadratic.

Investigation of generalized balanced quasigroup equations was initiated in the important paper [1] by Aczél, Belousov and Hosszú where equations of generalized associativity and mediality were solved. Alimpić in [2] gave formulas of general solution to any generalized balanced quasigroup equation. Quadratic quasigroup equations were defined in Krapež [11] where a fairly wide class of them were solved. The complete solution to quadratic equations was given in Krstić [14].

Definition 3.8. Let Eq[F_{1}, …, F_{n}] be a generalized quadratic functional equation on quasigroups. We write F_{i} ∼ F_{j} (1 ⩽ i, j ⩽ n) and say that F_{i} and F_{j} are necessarily isostrophic if in every solution Q_{1}, …, Q_{n} of Eq the operations Q_{i} and Q_{j} are isostrophic.

An operational symbol F_{i} is {loop, group, abelian} if Q_{i} is always isostrophic to a {loop, group, abelian group} operation.

Definition 3.9. A ∼–class with one or two elements is called small, otherwise it is big.

Definition 3.10. Two equations Eq and Eq′ are parastrophically equivalent (denoted Eq PEEq′) if one of them can be obtained from the other by applying a finite number of the following steps:

(1) Renaming object and/or functional variables.

(2) Replacing s = t by t = s.

(3) Replacing equation A(t_{1}, t_{2}) = t_{3} by one of the following equations: A^{σ}(t_{σ(1)} , t_{σ(2)} ) = t_{σ(3)} for some permutation σ ∈ S_{3}.

(4) Replacing a subterm A(t_{1}, t_{2}) of s or t by A^{(12)} (t_{2}, t_{1}).

(5) Replacing a subterm A(x, t_{2}) by a new variable y and simultaneously replacing all other occurrences of x by either A^{(13)} (y, t_{2}) or A^{(123)} (t_{2}, y).

(6) Replacing a subterm A(t_{1}, x) by a new variable y and simultaneously replacing all other occurrences of x by either A^{(23)} (t_{1}, y) or A^{(132)} (y, t_{1}).

Theorem 3.1 (Krstić [14]). Let equations Eq[F_{1}, …, F_{n}] and Eq′[G_{1}, …, G_{n}] be parastrophically equivalent. For all i (1 ⩽ i ⩽ n) let G_{i} be obtained from F_{i} by transformations described in Definition 3.10, and let Q_{1}, …, Q_{n} and R_{1}, …, R_{n} be solutions on a set S of Eq, Eq′, respectively. Then the operations Q_{i} and R_{i} (1 ⩽ i ⩽ n) are mutually isostrophic.

This theorem shows why the notion of parastrophic equivalence is so important – namely, if we have a solution to a quadratic equation, then we can easily produce solutions to all equations parastrophically equivalent to it.

4. Graphs

Following Krstić [14], functional equations are represented by multigraphs. We use standard graph–theoretic notions and facts, which we review next for the sake of completeness.

A multigraph is a triple (V, E; I), where V and E are disjoint sets whose elements are called vertices and edges, respectively, while I is an incidence relation I ⊆ V × E. We also assume that for every edge e there are one or two vertices incident to e. If there is a unique vertex v incident to an edge e, then e is called a loop (which should not be confused with a loop as a quasigroup with an identity, see Section 2). A simple graph is a multigraph with no loops and no multiple edges. In this paper we shall use shorter term graph for multigraph and assume that all graphs are finite (V and E are both finite) and nontrivial (V and E are both nonempty).

Definition 4.1. A graph (W, F; J) is a subgraph of a graph (V, E; I) if W ⊆ V, F ⊆ E and J ⊆ I ∩ (W × F).

Definition 4.2. Two graphs (V, E; I) and (W, F; J) are isomorphic ((V, E; I) ≃ (W, F; J)) if there are bijections f : V → W and g : E → F such that vertices v_{1}, v_{2} ∈ V are incident to an edge e ∈ E iff the vertices f(v_{1}), f(v_{2}) are incident to the edge g(e).

Two vertices in a graph are adjacent if there is an edge such that both are incident to it. Two edges are adjacent if there is a vertex incident to both of them. A path (from v_{0} to v_{n}) in a graph is an alternating (vertex–edge) sequence v_{0}, e_{1}, v_{1}, …, e_{n}, v_{n} such that for i = 1, …, n the vertices v_{i−1} and v_{i} are the endvertices of the edge e_{i}. If v_{0} = v_{n} the path is closed. A path is simple if it has no subpath which is closed. A cycle is a simple closed path. Two paths, one from v_{1} to v_{2} and the other from v_{3} to v_{4}, are disjoint if they have neither common edges nor common vertices except perhaps v_{1}, v_{2}, v_{3}, v_{4}.

A graph is connected if for every two vertices there is a path from one to the other. A bridge of a graph G is an edge whose removal disconnects G. A pair of edges is a bridge-couple of G if neither is a bridge and the removal of both disconnects G. A connectivity c(G) of a graph G is the smallest number such that removal of some c(G) edges disconnects G.

Theorem 4.1 (Menger). For any two vertices v_{1}, v_{2} of a graph G there are at least c(G) disjoint paths from v_{1} to v_{2}.

Obviously, c(G) = 1 iff there is a bridge in G and c(G) = 2 iff there is no bridge in G but G contains a bridge-couple.

We are particularly interested in cubic graphs. A graph is cubic if for every vertex v there are exactly three edges to which v is incident, provided that if an edge is a loop it is counted twice. In a cubic graph G, c(G) ⩽ 3.

Lemma 4.1. If (V, E; I) is a cubic graph, then there is a positive integer n such that |V | = 2n and |E| = 3n.

Definition 4.3. Two vertices v_{1} and v_{2} of a graph G are 3-edge-connected if v_{1} = v_{2} or we need to remove at least three edges in G to disconnect v_{1} and v_{2}.

The 3-edge-connectivity relation between vertices of G is an equivalence relation denoted by the symbol ≡. To see transitivity, if v_{1} ≡ v_{2} and v_{2} ≡ v_{3}, then there are at least three edge-disjoint paths from v_{1} to v_{2} and three edge-disjoint paths from v_{2} to v_{3}. But then if we remove any two edges from the graph, we may disconnect at most two of the three edge-disjoint paths from v_{1} to v_{2} and at most two of the three edge-disjoint paths from v_{2} to v_{3}. Thus, v_{1} and v_{3} remain connected by one path from v_{1} to v_{2} and one path from v_{2} to v_{3}.

The vertices of a graph G are partitioned by this relationship into equivalence classes called ≡-classes.

Definition 4.4. A ≡-class with one or two elements is called small, otherwise it is big.

Definition 4.5. A graph G is 3-edge-connected if c(G) ⩾ 3, i.e., we need to remove at least three edges from G to make G disconnected.

Since we are only interested in the notion of egde-connectivity in a graph (as oposed to the vertex-connectivity), we call the 3-edge-connectivity property simply 3-connectivity. By Menger Theorem, a graph G is 3-connected iff for any two vertices v_{1} and v_{2} of G there are at least three edge-disjoint paths in G from v_{1} to v_{2}. Obviously, a cubic graph G is 3-connected iff c(G) = 3 iff the relation ≡ is the full relation on the vertices of G.

Definition 4.6. Let vertices v_{1} and v_{2} be incident to an edge e in a graph G. A new graph is said to be obtained by the subdivision of the edge e if it is obtained from G by the addition of a new vertex v and the replacement of the edge e by two new edges e_{1} and e_{2} such that v_{1} and v are incident to e_{1} whereas v_{2} and v are incident to e_{2}.

Definition 4.7. A graph G′is a subdivision of a graph G iff there is a sequence G_{1}, …, G_{n} of graphs such that G = G_{1}, G′ = G_{n}, and G_{i} (1 < i ⩽ n) is obtained from G_{i−1} by the subdivision of some edge of G_{i−1} .

Definition 4.8. Two graphs G and H are homeomorphic iff there is an isomorphism from some subdivision of G to some subdivision of H.

Definition 4.9. A graph G is homeomorphically embeddable into a graph H iff there is a subgraph H′ of H homeomorphic to G.

Definition 4.10. A graph G is homeomorphically embeddable into a graph H within a subgraph H′ of H iff it is homeomorphically embeddable into H′.

Definition 4.11. A graph G is planar if it can be represented by points (for vertices) and lines (for edges) in the Euclidean plane so that lines intersect only at vertex points.

Figure 1 shows planar cubic graph K_{4}, nonplanar noncubic graph K_{5}, and nonplanar cubic graph K_{3,3}.

Figure 1. The graphs K_{4}, K_{5}, and K_{3,3}.

Embeddability of these graphs is an important condition for graphs relevant to the properties of associated equations (see the next section).

Theorem 4.2 (Krstić [14]). A graph G consists of small ≡–classes iff K_{4} cannot be homeomorphically embedded in G.

Theorem 4.3 (Kuratowski). A graph G is planar iff neither K_{5} nor K_{3,3} can be homeomorphically embedded in G.

5. Functional equations and their graphs

In this section we establish a connection between generalized quadratic quasigroup functional equations and connected cubic graphs. The results are mainly from Krstić [14] with occasional improvements. See also Krapež and Taylor [13].

Definition 5.1. Let s = t be a generalized quadratic quasigroup functional equation. The Krstić graph K(s = t) of the equation s = t is a graph (V, E; I) given by:

• The vertices of K(s = t) are operation symbols from s = t.

• The edges of K(s = t) are subterms of s and t, including s and t which are considered a single edge. Likewise, any variable (which appears twice in s = t) is taken to be a single edge.

• If A(p, q) is a subterm of s or t, then the vertex A is incident to edges p, q, A(p, q) and no other.

Note that if an equation s = t has a subterm of the form A(x, x), then there is a corresponding loop in the graph K(s = t).

Lemma 5.1. For every generalized quadratic functional equation s = t, the graph K(s = t) is a connected cubic graph.

Observe that Lemma 4.1 implies that if the quadratic equation s = t has n variables, then the graph K(s = t) has 2(n − 1) vertices and 3(n − 1) edges.

Example 5.1. The parastrophically equivalent equations of generalized associativity and generalized transitivity have the same Krstić graph K_{4}, and the Krstić graph of generalized mediality is K_{3,3}.

The conclusion that the parastrophically equivalent equations have the same (i.e., isomorphic) Krstić graphs holds also in general.

Lemma 5.2. Let s = t and s′ = t′ be two parastrophically equivalent generalized quadratic functional equations. Then K(s = t) and K(s′ = t′) are isomorphic graphs.

Definition 5.2. Given a connected cubic graph G = (V, E; I), we construct its functional equation QE(G) as follows.

Let F_{v} (v ∈ V) be operation symbols and x_{e} (e ∈ E) variables related to G. For every vertex v write F_{v}(x_{p}, x_{q}) = x_{r} if vIp, vIq, vIr (we could use any F_{v}^{σ} instead). Choose v_{1} ∈ V, define V_{1} = V ∖ {v_{1}} and establish the quasiidentity (⋀ _{v∈V_{1}} F_{v}(x_{p_{v}} , x_{q_{v}}) = x_{r_{v}} ) ⇒ F_{v_{1}} (x_{p_{1}} , x_{q_{1}}) = x_{r_{1}} . Denote this quasiidentity by (⋀ _{v∈V_{1}} F_{v}(x_{p_{v}} , x_{q_{v}}) = x_{r_{v}} ) ⇒ s_{1} = t_{1}.

Next, given (⋀ _{v∈V_{i}} F_{v}(x_{p_{v}} , x_{q_{v}}) = x_{r_{v}} ) ⇒ s_{i} = t_{i}, choose a variable y with just one occurrence in s_{i} = t_{i} (there is always one such because G is connected). There is a v_{i+1} ∈ V_{i} such that F_{v_{i+1}} (x_{p_{i}} , x_{q_{i}}) = x_{r_{i}} and y is one of x_{p_{i}} , x_{q_{i}} , x_{r_{i}} . Then y = F_{v_{i+1}}^{σ} (x, z) for {x, y, z} = {x_{p_{i}} , x_{q_{i}} , x_{r_{i}} } and some σ ∈ S_{3}. Replace y in s_{i} = t_{i} by F_{v_{i+1}}^{σ} (x, z)to obtain s_{i+1} = t_{i+1} . Define V_{i+1} = V_{i} ∖ {v_{i+1} }. We have (⋀ _{v∈V_{i+1}} F_{v}(x_{p_{v}} , x_{q_{v}}) = x_{r_{v}} ) ⇒ s_{i+1} = t_{i+1} .

The equation QE(G) is s_{|V |} = t_{|V |}.

Lemma 5.3. Let G be a connected cubic graph. Then QE(G) is a generalized quadratic functional equation.

Note that we can ensure the uniqueness of QE(G) if we prescribe the choice of F_{1} first, and then if we take variable y in s_{i} = t_{i} with the smallest index. However, in view of the next lemma, it is not necessary to do so.

Lemma 5.4. Let G and H be two isomorphic connected cubic graphs. Then QE(G) and QE(H) are parastrophically equivalent equations.

Together, Lemmas 5.2 and 5.4 give the following theorem:

Theorem 5.1. Generalized quadratic quasigroup functional equations Eq and Eq′ are parastrophically equivalent iff their Krstić graphs K(Eq) and K(Eq′) are isomorphic.

Theorem 5.2 (Krstić [14]). Let Eq[F_{1}, …, F_{n}] be a generalized quadratic functional equation. Then:

• F_{i} ∼ F_{j} in Eq iff F_{i} ≡ F_{j} in K(Eq).

• Every F_{i} is a loop symbol.

• A symbol F_{i} is a group symbol iff F_{i}/∼ is big iff F_{i}/≡ is big iff K_{4} is homeomorphically embeddable in K(Eq) within F_{i}/≡.

• A symbol F_{i} is abelian iff the subgraph of K(Eq) defined by F_{i}/≡ is not planar iff K_{3,3} is homeomorphically embeddable in K(Eq) within F_{i}/≡.

Therefore Krstić graphs can be used to determine if equations are parastrophically equivalent or not, but also whether some or all operations occurring in an equation are necesarilly isostrophic to each other and to some (abelian) groups. Other questions on quadratic equations can be also answered using corresponding graph notions (see the next section).

6. The problems of Sokhats’kyi

In this and the next section we use the following convention:

• The difference between operation symbols will not be significant. We shall therefore use only one, the infix binary symbol ·, to denote any of them.

• All products will be assumed to associate to the left. For example, using this convention, the equation A(B(x, y), z) = C(x, D(y, z)) of generalized associativity is represented by the equation xyz = x · yz.

∗ ∗ ∗ Sokhats’kyi formulated in [17] some problems concerning quasigroup functional

equations. We cite verbatim:

Problem 6.1. Construct a complete classification of uncancellable quadratic functional equations with an arbitrary number of object variables.

Problem 6.2. For parastrophically uncancelablle quadratic equations, determine visual properties that distinguish equations parastrophically equivalent to the general identity of mediality from equations parastrophically equivalent to the general identity of pseudomediality.

Problem 6.3. Construct a complete classification of cancellable quadratic equations.

Problem 6.4. Find applications of the results obtained to the investigation of identities on quasigroup algebras, i.e., on algebras whose signature is composed of quasigroup operations.

Some partial results on the Problem 6.1 were given by Duplák [5] (uncancellable equations with three variables), Sokhats’kyi [15]–[18] (uncancellable equations with four variables) and Koval’ [7]–[10] (uncancellable equations with five variables). The Problem 6.2 is solved in Krapež, Simić and Tošić [12].

The following definition of (parastrophic) cancellability is used in the formulation of the above problems.

Definition 6.1 (Sokhats’kyi [17]). A quasigroup functional equation is cancellable if it has a self-sufficient sequence of subwords (a sequence of subwords of an equation is called self-sufficient if it contains all appearances of all its variables in the equation). Otherwise it is uncancellable.

An equation is parastrophically cancellable if it is parastrophically equivalent to a cancellable equation. Otherwise it is parastrophically uncancellable.

The definition becomes more transparent if we take into account the following lemmas.

Lemma 6.1 (Sokhats’kyi [17]). If an object variable x has exactly two appearances in the functional equation s = t, then this equation is parastrophically equivalent to an equation x = xt_{0} …t_{n} for some subterms t_{0}, …, t_{n} of s, t.

The sequence t_{0}, …, t_{n} is called the edging of the variable x in the equation s = t.

For example, the equation A(B(x, y), z) = C(x, D(y, z)) of generalized associativity is equivalent to the equation x = C^{(13)} (A(B(x, y), z), D(y, z)), i.e., parastrophically equivalent to the equation (represented by) x = xyz · yz. Since the difference between C and C^{(13)} disappears, it would be, perhaps, more appropriate to use the symbol ⋄ introduced in Section 2, instead of ·, but we keep the notation as defined by Sokhats’kyi.

Lemma 6.2 (Sokhats’kyi [17]). A cyclic permutation of an edging of the variable x is also an edging of this variable in some functional equation parastrophically equivalent to the given one.

A subsequence t_{i+1} , …, t_{i+j} , where + is the addition modulo n + 1, is called an edging arc. If an arc contains all appearances of all of its variables, then it is called self-sufficient.

Lemma 6.3 (Sokhats’kyi [17]). If a variable of the equation s = t has a selfsufficient edging arc, then this equation is parastrophically cancellable.

Finally, building on work of Sokhats’kyi [17] and Krstić [14] we are able to look at parastrophic (un)cancellability of equations from different perspective.

Theorem 6.1. The following statements are mutually equivalent:

(1) A generalized quadratic quasigroup functional equation Eq is parastrophically uncancellable.

(2) The relation ≡ is the full relation on vertices of K(Eq).

(3) The relation ∼ is the full relation on operation symbols of Eq.

(4) c(K(Eq)) = 3, i.e., K(Eq) is 3-connected.

Proof. (1 ⇔ 2) To show 2 ⇒ 1, assume that the equation Eq is cancellable. Then Eq is parastrophically equivalent to some equation x = xt_{0} ⋯ t_{n} with a self-sufficient edging arc t_{i+1} , …, t_{n} (i < n). The equivalent equation is just a shorthand for the equation pictured in Figure 2.

The Krstić graph K(Eq) of Eq is shown in Figure 3, where T_{m} are graphs of terms t_{m} (0 ⩽ m ⩽ n).

Figure 2. The tree of x = xt_{0} ⋯ t_{n}.

Note that some T_{j} and T_{k} are connected via common variables of t_{j} and t_{k} but, because of the self-sufficiency of t_{i+1} , …, t_{n}, this never happens for 0 ⩽ j ⩽ i < k ⩽ n. Therefore, there are only two disjoint paths in K(Eq) from F_{0} to F_{n}: the first one via x and the second through the vertices F_{1}, F_{2}, …, F_{n−i−1} , F_{n−i} , …, F_{n−1} .

Actually, there are other paths from F_{0} to F_{n} (via some of T_{m}’s) but they all contain edge y, so cannot be disjoint from the path through the vertices F_{1}, F_{2}, …, F_{n−i−1} , F_{n−i} , …, F_{n−1} . Consequently, F_{0} ≡ F_{n} is not true and so ≡ is not the full relation.

Figure 3. The graph K(Eq).

To show the other direction 1 ⇒ 2, assume that an equation Eq is given such that the relation ≡ on vertices of K(Eq) is not full. Then K(Eq) has either a bridge or a bridge-couple. We show that in both cases the equation Eq is parastrophically cancellable.

Case (i): There is a bridge in K(Eq).

If we construct QE(K(Eq)) using Definition 5.2 starting from the bridge, then Eq is parastrophically equivalent to an equation s = t such that the sets of variables of s and t are disjoint. Since Eq is quadratic, s must be a product pq. Without loss of generality we may assume that there is a variable in p which also occurs in q.

If this is not the case, then all variables of p and q are disjoint and equation pq = t is equivalent to p = q//t. Thus it is parastrophically equivalent to p = qt and variables of p and qt are also disjoint. This procedure can be repeated if necessary, until, since regression must be finite, we get the product with a variable in both factors.

So let us assume that a variable x occurs in both p and q. Equation Eq is parastrophically equivalent to the equation xs_{1} …s_{i} · xs_{i+1} …s_{j} = t for some subterms s_{1}, …, s_{j} (0 ⩽ i ⩽ j) of s. The last equation is parastrophically equivalent to x = xs_{i+1} …s_{j} ts_{i} …s_{1} and therefore t is self-sufficient edging arc of the variable x. By the Lemma 6.3 the equation s = t is parastrophically cancellable and so is Eq.

Case (ii): There is no bridge but there is a bridge-couple (with edges x, y) in K(Eq).

Making QE(K(Eq)) as in Definition 5.2 and starting from the variable y, we get the equation s = t, parastrophically equivalent to Eq and such that the variable x occurs in both s and t, while all other variables of s and t are disjoint. We can rewrite s = t in the form xs_{1} …s_{i} = xt_{1} …t_{j} for some subterms s_{1}, …, s_{i} of s and t_{1}, …, t_{j} of t. Consequently, the equation s = t is parastrophically equivalent to the equation x = xt_{1} …t_{j} s_{i} …s_{1} with the sequence t_{1}, …, t_{j} being a selfsufficient edging arc for x. This proves that both s = t and Eq are parastrophically cancellable.

(2 ⇔ 3) That the relation ∼ is full iff ≡ is full follows from Theorem 5.2.

(2 ⇔ 4) Obviously, a cubic graph G is 3-connected iff c(G) = 3 iff the relation ≡ is the full relation on V. □

This is our main result. Together with Theorem 5.1, it gives the full characterization of parastrophic (un)cancellability of equations. Therefore, it solves Sokhat’skyi problems 6.1 and 6.3.

7. How many generalized quadratic functional equations are there?

In this section we give a count of all generalized quadratic equations with n variables, as well as a count of their normal subset. Normal equations (defined below) avoid repetitions of equations with nonessential differences such as variable substitution. The numbers of generalized and normal generalized quadratic equations with n variables are denoted by E_{n} and e_{n}, respectively.

We also pose the problem of finding a general formula for the sequence of numbers π_{n} of parastrophically nonequivalent generalized quadratic quasigroup equations with n variables.

Theorem 7.1. The total number of generalized quadratic quasigroup functional equations with n variables is

E_{n} = \frac{(4n − 2)!}{2^{n}(2n − 1)!}

Proof. Let s = t be a quadratic equation with n variables. The equation is fully determined by the binary tree of the equation s = t and the order in which variables occur in the equation. The tree and the order are independent of each other.

i) It is well known that the number of different binary trees with n leaves is C_{n−1} , where C_{n} (n ⩾ 0) is the sequence of Catalan numbers. The sequence satisfies the formula: C_{n} = (2n)!/(n + 1)!n! and is denoted by A000108 in Sloane’s “The On-Line Encyclopedia of Integer Sequences” [19]. The first ten members of the sequence C_{n} (0 ⩽ n ⩽ 9) are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862.

The tree of the equation s = t is a binary tree with the root ’=’, its left subtree being the tree of s and its right subtree being the tree of t. Therefore there are T_{n} = C_{2n−1} different trees of quadratic equations with n variables. The first five members of the sequence T_{n} (n ⩾ 1) are 1, 5, 42, 429, 4862. This is the Sloane sequence A024492.

ii) The order of variables in s = t is determined by the word of length 2n in which every one of the letters x_{1}, …, x_{n} appears exactly twice. Let us denote by W_{n} the number of such words. It is easy to see that the sequence W_{n} satisfies the recurrence relation:

W_{1} = 1, W_{n} = n(2n − 1)W_{n−1}

W_{n} is the Sloane sequence A000680, and the general formula is W_{n} = (2n)!/2^{n}. The first five members of W_{n} are 1, 6, 90, 2520, 113400.

iii) As noted before, the number of all quadratic equations with n variables is E_{n} = T_{n}W_{n} = C_{2n−1} W_{n} = (4n − 2)!/2^{n}(2n − 1)!. The recurrence relation is E_{n+1} = 2(16n^{2} − 1)E_{n} and the first five members of this sequence are 1, 30, 3780, 1081080, 551350800. This sequence of numbers is not listed among the Sloane sequences. □

There is a vast number of repetitions among above equations – the difference being just the order of variables which is not essential since any permutation of variables gives basically the same equation. Likewise, the equations s = t and t = s are essentially the same so we can choose just one. Note that we cannot delete equations of the type t = t although they are obviously equivalent to x = x. This is because our equations just represent generalized equations. For example, the equation xy = xy stands for the equation A(x, y) = B(x, y) which is not equivalent to x = x. Instead, it states certain relationship between operations A and B.

Definition 7.1. A generalized quadratic quasigroup functional equation s = t is called normal if:

• For 1 ⩽ i < j ⩽ n, the first occurrence of x_{i} in s = t appears before the first occurrence of x_{j}.

• If the terms s, t are not identical, then t ◁ s.

Theorem 7.2. The total number of normal generalized quadratic quasigroup functional equations with n variables is

e_{n} = \frac{(2n)!}{2^{n+1} n!}(C_{2n−1} + C_{n−1} )

Proof. The calculations are similar to those in the previous theorem.

i) The sequence t_{n} (n ⩾ 1) of numbers of trees we get if we exclude all trees of equations s = t, where s ◁ t and the formula is: t_{n} = (C_{2n−1} + C_{n−1} )/2. We get it from the following formula for Catalan numbers: C_{n} = ∑ _{i=1}^{n} C_{i}C_{n−i} and the observation that for t_{n} we use only cases with i ⩾ n − i.

The first five members of t_{n} are 1, 3, 22, 217, 2438. The sequence is not listed among the Sloane sequences.

ii) We get the number w_{n} of words of length 2n by taking only words in which variables occur in fixed order: x_{1}, …, x_{n} (ignoring the repetitions). Therefore w_{n} = W_{n}/n! = (2n)!/2^{n}n!. This sequence is the Sloane sequence A001147 and the first five members are 1, 3, 15, 105, 945.

iii) The number e_{n} (n ⩾ 1) of normal equations is

e_{n} = t_{n}w_{n} = \frac{(2n)!}{2^{n+1} n!}(C_{2n−1} + C_{n−1} )

The first five members of the sequence e_{n} are 1, 9, 330, 22785, 2303910. This sequence is not present in the Sloane list of sequences. □

We also define the sequence π_{n} (n ⩾ 1), where π_{n} is the number of classes of parastrophically nonequivalent generalized quadratic quasigroup equations with n variables. According to Theorem 5.1 π_{n} is also the number of nonisomorphic connected cubic graphs with 2(n − 1) vertices and 3(n − 1) edges. By the definition (see section 8), π_{1} = 1. We prove that π_{2} = 2. We know that π_{3} = 5 and π_{4} = 17, but the proof will be published elsewhere. We do not know a general formula for π_{n}. Therefore:

Problem 7.1. Find a general formula for the sequence π_{n} (n ⩾ 1).

8. Equations with one and two variables

As an example of an application of general results, we give solutions of all normal generalized quadratic quasigroup equations with (one and) two variables. As for equations with more variables, we can solve any such particular equation (using methods provided by Krstić), but the complexities of connected cubic graphs prevent us from producing a formula in closed form giving rise to general solutions of all such equations. This problem requires further investigation.

∗ ∗ ∗

The special case of equations with one variable is easy, since there is only one such equation: x = x. However, there are no operation symbols in x = x so it does not fit our definition of functional equation. Despite this we define π_{1} to be 1.

The case of equations with two variables is much more interesting. There are 30 generalized quadratic quasigroup functional equations with two variables, nine of them normal. They are:

A(x, x) = B(y, y) (8.1)

A(x, y) = B(x, y) (8.2)

A(x, y) = B(y, x) (8.3)

A(x, B(x, y)) = y (8.4)

A(x, B(y, x)) = y (8.5)

A(x, B(y, y)) = x (8.6)

A(B(x, x), y) = y (8.7)

A(B(x, y), x) = y (8.8)

A(B(x, y), y) = x. (8.9)

The following lemmas are useful in solving these equations.

Lemma 8.1. Let S be a nonempty set, e ∈ S and σ a permutation of S. A general solution to the equation

(8.10)  σA(x, x) = e

in the quasigroup A on S is given by:

A(x, y) = σ^{−1} αL^{(23)} (σx, σy)

where:

• L is an arbitrary loop on S with the identity e

• α is an arbitrary permutation of S such that αe = e.

Proof. We prove first that the above formulas always give a solution to the equation (8.10).

Since L is a loop, we have L(x, e) = x, so L^{(23)} (x, x) = e. It follows that σA(x, x) = σσ^{−1} αL^{(23)} (σx, σx) = αe = e.

Next, we prove that every solution to equation (8.10) is of the form given in the statement of the lemma.

Let A be a particular quasigroup on S which satisfies (8.10). Pick any p ∈ S and define: a = A(p, p), αx = σA(a, σ^{−1} x) and L(x, y) = σA^{(23)} (σ^{−1} x, σ^{−1} αy). It follows that σa = σA(p, p) = e, function α is permutation and

αe = σA(a, σ^{−1} e) = σA(a, a) = e.

The operation L is a quasigroup since it is an isostrophe of the quasigroup A. Moreover, L is a loop with identity e. To see this, first observe that

L(e, x) = σA^{(23)} (σ^{−1} e, σ^{−1} αx) = σA^{(23)} (a, σ^{−1} σA(a, σ^{−1} x))
= σA^{(23)} (a, A(a, σ^{−1} x)) = σσ^{−1} x = x.

On the other hand, A(σ^{−1} x, σ^{−1} x) = σ^{−1} e = a implies A^{(23)} (σ^{−1} x, a) = σ^{−1} x and thus

L(x, e) = σA^{(23)} (σ^{−1} x, σ^{−1} αe) = σA^{(23)} (σ^{−1} x, σ^{−1} e)
= σA^{(23)} (σ^{−1} x, a) = σσ^{−1} x = x.

From the definition of L it follows that A(x, y) = σ^{−1} αL^{(23)} (σx, σy). This completes the proof. □

The proofs of the next two lemmas are similar, so we skip them.

Lemma 8.2. Let S be a nonempty set, q ∈ S and σ a permutation of S. A general solution to the equation

σA(x, q) = x

in the quasigroup A on S is given by:

A(x, y) = σ^{−1} L(x, αy)

where:

• L is an arbitrary loop on S with identity e

• α is an arbitrary permutation of S such that αq = e.

Lemma 8.3. Let S be a nonempty set, p ∈ S and σ a permutation of S. A general solution to the equation

σA(p, x) = x

in the quasigroup A on S is given by:

A(x, y) = σ^{−1} L(αx, y)

where:

• L is an arbitrary loop on S with identity e

• α is an arbitrary permutation of S such that αp = e.

The graph K(Eq) of an equation Eq with 2 variables has 2 vertices and 3 edges. There are only two such non-isomorphic graphs shown in Figure 4: the dumbbell graph and the dipole D_{3} graph. Therefore, π_{2} = 2.

The dumbbell graph corresponds to equations (8.1), (8.6) and (8.7). The ∼- classes are singletons. General solutions to these equations are given in the next three theorems.

Figure 4. Two non-isomorphic graphs with 2 vertices and 3 edges.

Theorem 8.1. A general solution to the equation (8.1) on a set S is given by:

A(x, y) = αL_{1}^{(23)} (x, y)
B(x, y) = βL_{2}^{(23)} (x, y)

where:

• L_{1} and L_{2} are arbitrary loops on S with a common identity e.

• α and β are arbitrary permutations on S such that αe = e, βe = e.

Proof. The equation (8.1) is equivalent to the system

A(x, x) = e, B(y, y) = e

for some e ∈ S. Both equations are special cases of (8.10) for σ = Id, where Id(x) = x is the identity function on S. By Lemma 8.1, the general solution to A(x, x) = e is given by A(x, y) = αL_{1}^{(23)} (x, y), where L_{1} is an arbitrary loop on S with identity e and α is a permutation of S such that αe = e. Analogously, B(x, y) = βL_{2}^{(23)} (x, y), where L_{2} is an arbitrary loop on S with identity e and β is a permutation of S such that βe = e.

Combined together, the last two statements complete the proof. □

Proofs of general solutions to equations (8.6) and (8.7) are similar.

Theorem 8.2. A general solution to the equation (8.6) on a set S is given by:

A(x, y) = L_{1}(x, αy),
B(x, y) = α^{−1} βL_{2}^{(23)} (αx, αy),

where:

• L_{1} and L_{2} are arbitrary loops on S with a common identity e.

• α and β are arbitrary permutations on S such that βe = e.

Theorem 8.3. A general solution to the equation (8.7) on a set S is given by:

A(x, y) = L_{1}(αx, y)
B(x, y) = α^{−1} βL_{2}^{(23)} (αx, αy)

where:

• L_{1} and L_{2} are arbitrary loops on S with a common identity e

• α and β are arbitrary permutations on S such that βe = e.

As the representative equation for this class of parastrophically equivalent equations we take the equation (8.1).

The dipole D_{3} graph corresponds to the rest of the equations: (8.2)–(8.5), (8.8) and (8.9). The relation ∼ is the full relation, so A ∼ B. General solutions to these equations are given in the next theorems.

Theorem 8.4. A general solution to the equation (8.2) on a set S is given by:

A(x, y) = L(A_{1}x, A_{2}y)
B(x, y) = L(B_{1}x, B_{2}y)

where:

• L is an arbitrary loop on S

• A_{1}, A_{2}, B_{1}, B_{2} are arbitrary permutations on S such that A_{1} = B_{1}, A_{2} = B_{2}.

The proof of this theorem is only slightly more complicated then the proof of Theorem 8.1. However, in this and the remaining cases there is a much simpler form of a general solution – note that equations are just requirements for B to be a certain parastrophe of A. Therefore, the following theorem is true.

Theorem 8.5. A general solution to the equation { (8.2), (8.3), (8.4), (8.5), (8.8), (8.9)} on a set S is given by:

• A = Q

• B = Q^{σ} {σ = (1), σ = (12), σ = (23), σ = (132), σ = (123), σ = (13)}.

where Q is an arbitrary quasigroup on S.

We take equation (8.2) as the representative one for this class of parastrophically equivalent equations.

The results concerning equations with two variables are summarized in Table 1.

PE–class Graph Number of ; ∼–classes Number of equations Representative equation

1  dumbbell  2  3  (8.1)
2  D_{3}  1  6  (8.2)

Table 1. Summary results on equations with two variables

Neither Krapež [11] nor Krstić [14] considered equations (8.1)–(8.9). If they had done, their solutions would have been similar to those given in Theorem 8.4. There are two novelties in our approach:

• The use of unipotent quasigroups instead of loops in solutions of (8.1), (8.6) and (8.7)

• The use of parastrophes of the quasigroup Q in remaining equations with a result of increased simplicity.

References

[1] J. Aczél, V. D. Belousov, M. Hosszú, Generalized associativity and bisymmetry on quasigroups, Acta Math. Acad. Sci. Hungar. 11 (1960), 127–136.

[2] B. Alimpić, Balanced laws on quasigroups, Mat. Vesnik 9(24) (1972), 249–255.

[3] V. D. Belousov, Configurations in algebraic nets (Russian), Shtiinca, Kishinev, (1979), Zbl 0447.94058.

[4] J. Dénes, A. D. Keedwell, Latin squares and their applications, Académiai Kiadó, Budapest, (1974), Zbl 0283.05014.

[5] J. Duplák, Identities and deleting maps on quasigroups, Czech. Math. J. 38(113)/1 (1988), 1–7, Zbl 0649.20058.

[6] R. A. Fisher, The design of experiments, 8th edition, Oliver and Boyd, Edinburgh, (1966), JFM 61.0566.03.

[7] R. F. Koval’, A classification of quadratic quasigroup functional equations of small length (Ukrainian), Vesnik KPU im. M. P. Dragomanova, Fiz.-Mat. 5 (2004).

[8] R. F. Koval’, Solutions of quadratic functional equations with five object variables on quasigroup operations (Ukrainian), Tr. Inst. Prikl. Mat. Mekh. 11 (2005), Zbl 1137.39303.

[9] R. F. Koval’, Classification of quadratic parastrophically uncancellable functional equations for five object variables on quasigroups (Ukrainian), Ukrain. Mat. Zh. 57/8 (2005), Zbl 1100.39026.

[10] R. F. Koval’, Classification of quadratic parastrophically uncancellable functional equations for five object variables on quasigroups, Ukrainian Math. J. 57/8 (2005), English translation of [9].

[11] A. Krapež, Strictly quadratic functional equations on quasigroups I, Publ. Inst. Math., Nouv. Sér. 29(43) (1981), 125–138.

[12] A. Krapež, S. K. Simić, D. V. Tošić, Parastrophically uncancellable quasigroup equations, accepted for publication in Aequationes Math.

[13] A. Krapež, M. A. Taylor, Gemini functional equations on quasigroups, Publ. Math. Debrecen 47/3–4 (1995), Zbl 0859.39014.

[14] S. Krstić, Quadratic quasigroup identities (Serbocroatian), PhD thesis, University of Belgrade, (1985).

[15] F. M. Sokhats’kyi, On isotopes of groups I (Ukrainian), Ukrain. Mat. Zh. 47/10 (1995), 1387–1398, Zbl 0888.20044.

[16] F. M. Sokhats’kyi, On isotopes of groups I, Ukrainian Math. J. 47/10 (1995), 1585–1598, English translation of [15 ].

[17] F. M. Sokhats’kyi, On the classification of functional equations on quasigroups (Ukrainian), Ukrain. Mat. Zh. 56/9 (2004), 1259–1266.

[18] F. M. Sokhats’kyi, On the classification of functional equations on quasigroups, Ukrainian Math. J. 56/9 (2004), 1499–1508, English translation of [17 ].

[19] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences , (accessed December 9, 2008).

[20] A. Ungar, Beyond the Einstein Addition Law and its Gyroscopic Thomas Precession – The Theory of Gyrogroups and Gyrovector Spaces, Kluwer, Dordrecht–Boston–London, (2001), Zbl 0972.83002.

Mathematčki institut SANU (Received 27 07 2009) Knez Mihailova 36 (Revised 18 03 2010) Beograd, Serbia

sasa@mi.sanu.ac.rs

Univerzitet Singidunum, FIM Danijelova 32 Beograd, Serbia

dzivkovic@singidunum.ac.rs