Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

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.     

Irreducible polynomials over GF(2) with prescribed coefficients

For an even positive integer n, we determine formulas for the number of irreducible polynomials of degree n over GF(2) in which the coefficients of xⁿ⁻¹,xⁿ⁻² and xⁿ⁻³ are specified in advance. Formulas for the number of elements in GF(2ⁿ) with the first three traces specified are also given.     

Subdirectly irreducible commutative multiplicatively idempotent semirings

Commutative multiplicatively idempotent semirings were studied by the authors and F. ?vr?ek, where the connections to distributive lattices and unitary Boolean rings were established. The variety of these semirings has nice algebraic properties and hence there arose the question to describe this variety, possibly by its subdirectly irreducible members. For the subvariety of so-called Boolean semirings, the subdirectly irreducible members were described by F. Guzmán. He showed that there were just two subdirectly irreducible members, which are the 2-element distributive lattice and the 2-element Boolean ring. We are going to show that although commutative multiplicatively idempotent semirings are at first glance a slight modification of Boolean semirings, for each cardinal n > 1, there exist at least two subdirectly irreducible members of cardinality n and at least 2ⁿ such members if n is infinite. For \({n \in \{2, 3, 4\}}\) the number of subdirectly irreducible members of cardinality n is exactly 2.     

A lower estimate for the achromatic number of irreducible graphs

The achromatic number of a graph is the largest number of independent sets its vertex set can be split into in such a way that the union of any two of these sets is not independent. A graph is irreducible if no two vertices have the same neighborhood. The achromatic number of an irreducible graph with n vertices is shown to be $\text{≥(}\text{1}\text{2}\text{?0(1))log}\text{n?}\text{log log}\text{n,}$ while an example of Erdös shows that it need not be log n/log 2+2 for any n. The proof uses an indiscernibility argument.     

A bijection of the set of 3-regular partitions

A bijection of the set of 3-regular partitions of an integer n is constructed. It is shown that this map has order 2 and that the 3-cores of a partition and its image have diagrams which are mutual transposes. It is conjectured that this is the same bijection as the one induced, using the labeling of Farahat, Müller, and Peel, from the action of the alternating character upon the 3-modular irreducible representations of the symmetric group of degree n.     

Irreducible polynomials over GF(2) with three prescribed coefficients

For an odd positive integer n, we determine formulas for the number of irreducible polynomials of degree n over GF(2) in which the coefficients of xⁿ⁻¹, xⁿ⁻² and xⁿ⁻³ are specified in advance. Formulas for the number of elements in GF(2ⁿ) with the first three traces specified are also given.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Irreducible representations of the full linear group

We obtain some results on Young diagrams. Based on these results, we construct bases for Young symmetry classes of tensors. Using these bases, we obtain a complete reduction of the representation A ??^mA [A∈GL(n,$\text{C}$] and irreducible matrix representations of the full linear group.     

Representations of finite special linear groups in non-defining characteristic

We classify irreducible modules over the finite special linear group SLn(q) in the non-defining characteristic ?, describe restrictions of irreducible modules from GLn(q) to SLn(q), classify complex irreducible characters of SLn(q) irreducible modulo l, and discuss unitriangularity of the l-decomposition matrix for SLn(q).     

Fragmented deformations of primitive multiple curves

A primitive multiple curve is a Cohen-Macaulay irreducible projective curve Y that can be locally embedded in a smooth surface, and such that Y _red is smooth. We study the deformations of Y to curves with smooth irreducible components, when the number of components is maximal (it is then the multiplicity n of Y). We are particularly interested in deformations to n disjoint smooth irreducible components, which are called fragmented deformations. We describe them completely. We give also a characterization of primitive multiple curves having a fragmented deformation.     

Recurrent Methods for Constructing Irreducible Polynomials over GF(2s)

The paper is devoted to some results concerning the constructive theory of the synthesis of irreducible polynomials over Galois fields GF(q), q=2^s. New methods for the construction of irreducible polynomials of higher degree over GF(q) from a given one are worked out. The complexity of calculations does not exceed O(n³) single operations, where n denotes the degree of the given irreducible polynomial. Furthermore, a recurrent method for constructing irreducible (including self-reciprocal) polynomials over finite fields of even characteristic is proposed.     

Products of irreducible matrices

In this paper we characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n × n Boolean matrices) generated by all the irreducible matrices, and hence give a necessary and sufficient condition for a Boolean matrix A to be a product of irreducible Boolean matrices. We also give a necessary and sufficient condition for an n × n nonnegative matrix to be a product of nonnegative irreducible matrices.     

Cartesian powers of 3-manifolds

Previous results of the authors completely determine when the n-fold self-products of two 3-dimensional lens spaces are diffeomorphic; in particular, if n is odd then the fundamental group determines the diffeomorphism type. We prove that for all other irreducible geometric 3-manifolds with trivial first Betti number, the n-fold products of such manifolds with themselves are homeomorphic for some n?2 if and only if the manifolds themselves are homeomorphic and obtain partial results for other cases. The proofs use an assortment of techniques from 3-dimensional topology and group theory.     

Dimension of the crown Skn

In 1941, Dushnik and Miller introduced the concept of the dimension of a poset (X, P) as the minimum number of linear extensions of P whose intersection is exactly P. Although Dilworth has given a formula for the dimension of distributive lattices, the general problem of determining the dimension of a poset is quite difficult. An equally difficult problem is to classify those posets which are dimension irreducible, i.e., those posets for which the removal of any point lowers the dimension. In this paper, we construct for each n≥3, k≥0, a poset, called a crown and denoted S^k_n, for which the dimension is given by the formula $\text{2?(n+k)}\text{(k+2)}$. Furthermore, for each t≥3, we show that there are infinitely many crowns which are irreducible and have dimension t. We then demonstrate a method of combining a collection of irreducible crowns to form an irreducible poset whose dimension is the sum of the crowns in the collection. Finally, we construct some infinite crowns possessing combinatorial properties similar to finite crowns.     

On the Number of Vedernikov–Ein Irreducible Components of the Moduli Space of Stable Rank 2 Bundles on the Projective Space

We propose a method for finding the exact number of Vedernikov–Ein irreducible components of the first and second types in the moduli space M(0, n) of stable rank 2 bundles on the projective space P³ with Chern classes c₁ = 0 and c₂ = n ≥ 1. We give formulas for the number of Vedernikov–Ein components and find a criterion for their existence for arbitrary n ≥ 1.     

Arc spaces and DAHA representations

A theorem of Y. Berest, P. Etingof and V. Ginzburg states that finite-dimensional irreducible representations of a type A rational Cherednik algebra are classified by one rational number m/n. Every such representation is a representation of the symmetric group S _n . We compare certain multiplicity spaces in its decomposition into irreducible representations of S _n with the spaces of differential forms on a zero-dimensional moduli space associated with the plane curve singularity x ^m = y ⁿ .     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

Transversal structures on triangulations: A combinatorial study and straight-line drawings

This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, which are called irreducible triangulations. The structure has been introduced by Xin He under the name of regular edge-labelling and consists of two bipolar orientations that are transversal. For this reason, the terminology used here is that of transversal structures. The main results obtained in the article are a bijection between irreducible triangulations and ternary trees, and a straight-line drawing algorithm for irreducible triangulations. For a random irreducible triangulation with n vertices, the grid size of the drawing is asymptotically with high probability 11n/27×11n/27 up to an additive error of . In contrast, the best previously known algorithm for these triangulations only guarantees a grid size (⌈n/2⌉−1)×⌊n/2⌋.     

On the reducibility of some composite polynomials over finite fields

Let g(x)?=?x ⁿ ?+?a _n-1 x ^n-1?+?. . .?+?a ₀ be an irreducible polynomial over ${\mathbb{F}_q}$ . Varshamov proved that for a?=?1 the composite polynomial g(x ^p ?ax?b) is irreducible over ${\mathbb{F}_q}$ if and only if ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})\neq 0}$ . In this paper, we explicitly determine the factorization of the composite polynomial for the case a?=?1 and ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})= 0}$ and for the case a?≠ 0, 1. A recursive construction of irreducible polynomials basing on this composition and a construction with the form ${g(x^{r^kp}-x^{r^k})}$ are also presented. Moreover, Cohen’s method of composing irreducible polynomials and linear fractions are considered, and we show a large number of irreducible polynomials can be obtained from a given irreducible polynomial of degree n provided that gcd(n, q ³ ? q)?=?1.