Varieties of Birkhoff Systems Part II

This is the second part of a two-part paper on Birkhoff systems. A Birkhoff system is an algebra that has two binary operations ? and + , with each being commutative, associative, and idempotent, and together satisfying x?(x + y) = x+(x?y). The first part of this paper described the lattice of subvarieties of Birkhoff systems. This second part continues the investigation of subvarieties of Birkhoff systems. The 4-element subdirectly irreducible Birkhoff systems are described, and the varieties they generate are placed in the lattice of subvarieties. The poset of varieties generated by finite splitting bichains is described. Finally, a structure theorem is given for one of the five covers of the variety of distributive Birkhoff systems, the only cover that previously had no structure theorem. This structure theorem is used to complete results from the first part of this paper describing the lower part of the lattice of subvarieties of Birkhoff systems.     

On idempotent modifications of generalized <Emphasis Type="Italic">MV</Emphasis>-algebras

The notion of idempotent modification of an algebra was introduced by Je?ek; he proved that the idempotent modification of a group is always subdirectly irreducible. In the present note we show that the idempotent modification of a generalized MV -algebra having more than two elements is directly irreducible if and only if there exists an element in A which fails to be boolean. Some further results on idempotent modifications are also proved.     

The variety of commutative additively and multiplicatively idempotent semirings

The variety \({\mathcal Z}\) of commutative additively and multiplicatively idempotent semirings is studied. We prove that \({\mathcal Z}\) is generated by a single subdirectly irreducible three-element semiring and it has a canonical form for its terms. Hence, \({\mathcal Z}\) is locally finite despite the fact that it is residually large. The word problem in \({\mathcal Z}\) is solvable.     

Maximal number of Boolean functions realized by an initial Boolean automaton with two constant states

The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of set of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with two constant states and n inputs is obtained.     

Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.     

Universal functions for classes of Boolean polynomials

The following problem is considered: Find Boolean function f of n variables with the property that, given any polynomial p of degree at most s, there exists a set of n-tuples such that p is the only polynomial of degree at most s taking the same values as f at these n-tuples. It is shown that for any fixed s and sufficiently large n, such a function exists and can be chosen from among those with domains of cardinality that grow as O(n ^s ).     

Ultraproducts preserve finite subdirect reducibility

An algebraic structure A is said to be finitely subdirectly reducible if A is not finitely subdirectly irreducible. We show that for any signature providing only finitely many relation symbols, the class of finitely subdirectly reducible algebraic structures is closed with respect to the formation of ultraproducts. We provide some corollaries and examples for axiomatizable classes that are closed with respect to the formation of finite subdirect products, in particular, for varieties and quasivarieties.     

Certain decompositions of matrices over Abelian rings

A ring R is (weakly) nil clean provided that every element in R is the sum of a (weak) idempotent and a nilpotent. We characterize nil and weakly nil matrix rings over abelian rings. Let R be abelian, and let n ∈ ?. We prove that M ⁿ (R) is nil clean if and only if R/J(R) is Boolean and M _n (J(R)) is nil. Furthermore, we prove that R is weakly nil clean if and only if R is periodic; R/J(R) is ?₃, B or ?₃ ⊕ B where B is a Boolean ring, and that M _n (R) is weakly nil clean if and only if M _n (R) is nil clean for all n ≥ 2.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

On decompositions of semirings via <Emphasis Type="Italic">k</Emphasis>-radicals of some relations

We generalize the notion of k-radical of Green’s \({\overline{\mathcal{J}}}\)-relation, study the decompositions of semirings and investigate the semirings on which the powers and transitive closures of k-radicals are distributive lattice congruences.     

Projective bichains

An algebra with two binary operations · and +  that are commutative, associative, and idempotent is called a bisemilattice. A bisemilattice that satisfies Birkhoff’s equation x · (x + y) =  x + (x · y) is a Birkhoff system. Each bisemilattice determines, and is determined by, two semilattices, one for the operation +  and one for the operation ·. A bisemilattice for which each of these semilattices is a chain is called a bichain. In this note, we characterize the finite bichains that are weakly projective in the variety of Birkhoff systems as those that do not contain a certain three-element bichain. As subdirectly irreducible weak projectives are splitting, this provides some insight into the fine structure of the lattice of subvarieties of Birkhoff systems.     

On the subsemiring generated by almost idempotents of a k-regular semiring

An element e of a semiring S with commutative addition is called an almost idempotent if \(e + e^2 = e^2\). Here we characterize the subsemiring \(\langle E(S)\rangle \) generated by the set E(S) of all almost idempotents of a k-regular semiring S with a semilattice additive reduct. If S is a k-regular semiring then \(\langle E(S)\rangle \) is also k-regular. A similar result holds for the completely k-regular semirings, too.     

Certain pairs of irreducible characters of the groups <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The investigation of the pairs of irreducible characters of the symmetric group S _n that have the same set of roots in one of the sets A _n and S _n ? A _n is continued. All such pairs of irreducible characters of the group S _n are found in the case when the least of the main diagonal’s lengths of the Young diagrams corresponding to these characters does not exceed 2. Some arguments are obtained for the conjecture that alternating groups A _n have no pairs of semiproportional irreducible characters.     

Representation and character varieties of the Baumslag-Solitar groups

Representation and character varieties of the Baumslag–Solitar groups BS(p, q) are analyzed. Irreducible components of these varieties are found, and their dimension is calculated. It is proved that all irreducible components of the representation variety R_n(BS(p, q)) are rational varieties of dimension n², and each irreducible component of the character variety X_n(BS(p, q)) is a rational variety of dimension k ≤ n. The smoothness of irreducible components of the variety R_n^s (BS(p, q)) of irreducible representations is established, and it is proved that all irreducible components of the variety R_n^s (BS(p, q)) are isomorphic to A¹ {0}.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Estimates for the number of Boolean functions realized by an initial Boolean automaton with three constant states

The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Such automata are those whose output function coincides with one of n-ary constant Boolean functions 0 or 1 in all states. The exact value of the maximum number of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with three constant states and n inputs is obtained.     

On estimates of Shannon functions of the length of unit tests for transpositions of variables

A nontrival upper estimate of the form n √2n (1 + o(1)) is proposed for the Shannon function of the length of the unit checking test for transpositions of variables of a Boolean function from P ₂ ⁿ , and it is proved that the Shannon function of the length of a unit diagnostic test for transpositions of variables of a Boolean function from P ₂ ⁿ has an asymptotics of the form n ²/2.     

On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions

A class of circuits of functional elements over the standard basis of the conjunction, disjunction, and negation elements is considered. For each circuit Σ in this class, its depth D(Σ) and dimension R(Σ) equal to the minimum dimension of the Boolean cube allowing isomorphic embedding Σ are defined. It is established that for n = 1, 2,… and an arbitrary Boolean function f of n variables there exists a circuit Σ_f for implementing this function such that R(Σ_f) ? n ? log₂ log₂n + O(1) and D(Σ_f) ? 2n ? 2 log₂ log₂n + O(1). It is proved that for n = 1, 2,… almost all functions of n variables allow implementation by circuits of the considered type, whose depth and dimension differ from the minimum values of these parameters (for all equivalent circuits) by no more than a constant and asymptotically no more than by a factor of 2, respectively.     

On the number of irreducible characters in a 3-block with a minimal nonabelian defect group

Let B be a 3-block of a finite group G with a defect group D. In this paper, we are mainly concerned with the number of characters in a particular block, so we shall use Isaacs' approach to block structure. We consider the block B of a group G as a union of two sets, namely a set of irreducible ordinary characters of G having cardinality k(B) and a set of irreducible Brauer characters of G having cardinality l(B). We calculate k(B) and l(B) provided that D is normal in G and D■x, y, z|x~(3n)=y~(3m)= z~3= [x, z] = [y, z] = 1, [x, y] = z(n m ≥ 2).     

On teaching sets for 2-threshold functions of two variables

We consider k-threshold functions of n variables, i.e. the functions representable as the conjunction of k threshold functions. For n = 2, k = 2, we give upper bounds for the cardinality of the minimal teaching set depending on the various properties of the function.