Check Character Systems Using Quasigroups: II

In this part of the article we continue to research check character systems with one check character over quasigroups under check equations which have one permutation. These systems always detect all single errors (i.e. errors in only one component of a code word) and can detect some other errors arising during transmission of data. We study check character systems over T-quasigroups. These quasigroups are isotopic to abelian groups and generalize the well-known class of medial quasigroups. We establish some properties of a T-quasigroup so that the check character systems over it are able to detect transpositions, jump transpositions, twin errors and jump twin errors. We also give some models of T-quasigroups, which satisfy all of the required properties for detection of errors of each of the considered types. Communicated by: P. Wild     

Check digit systems over groups and anti-symmetric mappings

A check digit system over a group which detects all single errors and all adjacent transpositions exists if and only if the group possesses an anti-symmetric mapping. In this article we give a characterisation for (anti-)automorphisms to be anti-symmetric, show how anti-automorphisms are used to construct new anti-symmetric mappings from others and give an upper bound for the number of anti-symmetric mappings of a group. For groups with sign structure, particularly the dihedral group, we present a further construction for anti-symmetric mappings. The fact that groups of order 2(2k + 1) have a non-trivial sign-structure leads to a very short proof that groups of order 2(2k + 1) possess no complete mapping. Finally we show that over the dihedral group D_m, m odd, no check digit system exists, which detects all jump transpositions or all twin errors or all jump twin errors.     

Permutations of finite fields for check digit systems

Let q be a prime power. For a divisor n of q ? 1 we prove an asymptotic formula for the number of polynomials of the form

$f(X)=\frac{a-b}{n}\left(\sum_{j=1}^{n-1}X^{j(q-1)/n}\right)X+\frac{a+b(n-1)}{n}X\in\mathbb{F}_q[X]$

such that the five (not necessarily different) polynomials f(X), f(X)±X and f(f(X))±X are all permutation polynomials over \({\mathbb{F}_q}\) . Such polynomials can be used to define check digit systems that detect the most frequent errors: single errors, adjacent transpositions, jump transpositions, twin errors and jump twin errors.

     

Classification of Quadratic Parastrophically Uncancelable Functional Equations for Five Object Variables on Quasigroups

We continue the investigation of quadratic functional equations over quasigroup operations and prove that every parastrophically uncancelable quadratic equation for five object variables is parastrophically equivalent to one of four given functional equations. __________ Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 8, pp. 1058 – 1068, August, 2005.     

On the smallest simple, unipotent Bol loop

Finite simple, unipotent Bol loops have recently been identified and constructed using group theory. However, the purely group-theoretical constructions of the actual loops are indirect, somewhat arbitrary in places, and rely on computer calculations to a certain extent. In the spirit of revisionism, this paper is intended to give a more explicit combinatorial specification of the smallest simple, unipotent Bol loop, making use of concepts from projective geometry and quasigroup theory along with the group-theoretical background. The loop has dual permutation representations on the projective line of order 5, with doubly stochastic action matrices.     

Exclusion processes with multiple interactions

We introduce the mathematical theory of the particle systems that interact via permutations, where transition rates are assigned not to the jumps from a site to a site, but to the permutations themselves. These permutation processes can be viewed as the natural generalization of symmetric exclusion processes, where particles interact via transpositions. We develop a number of innovative coupling techniques for the permutation processes and establish the needed conditions for them to apply. We use duality, couplings and other tools to explore the stationary distributions of the permutation processes with translation invariant rates.     

Burnside Orders,Burnside Algebras and Partition Lattices

The permutation representation theory of groups has been extended, through quasigroups, to one-sided left (or right) quasigroups. The current paper establishes a link with the theory of ordered sets, introducing the concept of a Burnside order that generalizes the poset of conjugacy classes of subgroups of a finite group. Use of the Burnside order leads to a simplification in the proof of key properties of the Burnside algebra of a left quasigroup. The Burnside order for a projection left quasigroup structure on a finite set is defined by the lattice of set partitions of that set, and it is shown that the general direct and restricted tensor product operations for permutation representations of the projection left quasigroup structure both coincide with the operation of intersection on partitions. In particular, the mark matrix of the Burnside algebra of a projection left quasigroup, a permutation-theoretic concept, emerges as dual to the zeta function of a partition lattice, an order-theoretic concept.     

Sharply transitive sets in quasigroup actions

This paper forms part of the general development of the theory of quasigroup permutation representations. Here, the concept of sharp transitivity is extended from group actions to quasigroup actions. Examples of nontrivial sharply transitive sets of quasigroup actions are constructed. A general theorem shows that uniformity of the action is necessary for the existence of a sharply transitive set. The concept of sharp transitivity is related to two pairwise compatibility relations and to maximal cliques within the corresponding compatibility graphs.     

An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

Right Nuclei of Quasigroup Extensions

The aim of this article is the study of right nuclei of quasigroups with right unit element. We investigate an extension process in this category of quasigroups, which is defined by a slight modification of non-associative Schreier-type extensions of groups or loops. The main results of the article give characterizations of quasigroup extensions satisfying particular nuclear conditions. We apply these results for constructions of right nuclear quasigroup extensions with right inverse property.     

A coalgebraic approach to quasigroup permutation representations

The paper identifies the class of all permutation representations of a given finite quasigroup as a covariety of coalgebras. Each permutation representation decomposes as a sum of homomorphic images of homogeneous spaces. For a group, permutation representations in the present sense specialise to the classical concept. Burnside's Lemma, with a new proof, is extended from groups to quasigroups. Received March 13, 2002; accepted in final form September 18, 2002. RID="h1" ID="h1"This paper was written while the author was a guest of the Institute of Mathematics and Information Sciences at Warsaw University of Technology, on Faculty Professional Development Assignment from Iowa State University.     

An improved block-interchange algorithm

In a block-interchange permutation, the positions of two nonoverlapping blocks of contiguous elements of a sequence are interchanged. We consider the problem of performing such a permutation by executing a series of transpositions, which exchange the positions of any two elements. A simple, elegant algorithm is known for doing this in time proportional to the number of elements that are either in the two blocks to be interchanged, or between them. We present a new algorithm which is always as fast and can be much faster than this known algorithm. We prove that our new algorithm performs the minimal number of transpositions.     

Shift error detection in standardized exams

Hundreds of millions of multiple choice exams are given every year in the United States. These exams permit form-filling shift errors, where an absent-minded mismarking displaces a long run of correct answers. A shift error can substantially alter the exam's score, and thus invalidate it.In this paper, we develop algorithms to accurately detect and correct shift errors, while guaranteeing few false detections. We propose a shift error model, and probabilistic methods to identify shifted exam regions.We describe the results of our search for shift errors in undergraduate Stony Brook exam sets, and in over 100,000 Scholastic Amplitude Tests. These results suggest that approximately 2% of all tests contain shift errors. Extrapolating these results over all multiple choice exams and forms leads us to conclude that exam takers make millions of undetected shift errors each year.Employing probabilistic shift correcting systems is inherently dangerous. Such systems may be taken advantage of by clever examinees, who seek to increase the probability of correct guessing. We conclude our paper with a short study of optimal guessing strategies when faced with a generous shift error correcting system.     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

On the classification of functional equations on quasigroups

We consider functional equations over quasigroup operations. We prove that every quadratic parastrophically uncancelable functional equation for four object variables is parastrophically equivalent to the functional equation of mediality or the functional equation of pseudomediality. The set of all solutions of the general functional equation of pseudomediality is found and a criterion for the uncancelability of a quadratic functional equation for four object variables is established.__________Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 9, pp. 1259–1266, September, 2004.     

A graph-theoretic approach to quasigroup cycle numbers

Norton and Stein associated a number with each idempotent quasigroup or diagonalized Latin square of given finite order n, showing that it is congruent mod 2 to the triangular number T(n). In this paper, we use a graph-theoretic approach to extend their invariant to an arbitrary finite quasigroup. We call it the cycle number, and identify it as the number of connected components in a certain graph, the cycle graph. The congruence obtained by Norton and Stein extends to the general case, giving a simplified proof (with topology replacing case analysis) of the well-known congruence restriction on the possible orders of general Schroeder quasigroups. Cycle numbers correlate nicely with algebraic properties of quasigroups. Certain well-known classes of quasigroups, such as Schroeder quasigroups and commutative Moufang loops, are shown to maximize the cycle number among all quasigroups belonging to a more general class.     

Finite-dimensional pointed Hopf algebras over $\mathbb{S}_4$

Let K be an algebraically closed field of characteristic 0. We conclude the classification of finite-dimensional pointed Hopf algebras whose group of group-likes is \mathbbS₄\mathbb{S}_4. We also describe all pointed Hopf algebras over \mathbbS₅\mathbb{S}_5 whose infinitesimal braiding is associated to the rack of transpositions.     

Quasigroups,right quasigroups and category coverings

The category of modules over a fixed quasigroup in the category of all quasigroups is equivalent to the category of representations of the fundamental groupoid of the Cayley diagram of the quasigroup in the category of abelian groups. The corresponding equivalent category of coverings, and the generalization to the right quasigroup case, are also described.Dedicated to the memory of Alan DayPresented by J. Sichler.     

A strong uniform time for random transpositions

A random permutation ofN items generated by a sequence ofK random transpositions is considered. The method of strong uniform times is used to give an upper bound on the variation distance between the distributions of the random permutation generated and a uniformly distributed permutation. The strong uniform time is also used to find the asymptotic distribution of the number of fixed points of the generated permutation. This is used to give a lower bound on the same variation distance. Together these bounds give a striking demonstration of the threshold phenomenon in the convergence of rapidly mixing Markov chains to stationarity.     

Sylow Theory for Quasigroups

This paper is intended as a first step toward a general Sylow theory for quasigroups and Latin squares. A subset of a quasigroup lies in a nonoverlapping orbit if its respective translates under the elements of the left multiplication group remain disjoint. In the group case, each nonoverlapping orbit contains a subgroup, and Sylow's Theorem guarantees nonoverlapping orbits on subsets whose order is a prime‐power divisor of the group order. For the general quasigroup case, the paper investigates the relationship between non‐overlapping orbits and structural properties of a quasigroup. Divisors of the order of a finite quasigroup are classified by the behavior of nonoverlapping orbits. In a dual direction, Sylow properties of a subquasigroup P of a finite left quasigroup Q may be defined directly in terms of the homogeneous space , and also in terms of the behavior of the isomorphism type within the so‐called Burnside order, a labeled order structure on the full set of all isomorphism types of irreducible permutation representations.