On highly palindromic words

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length-a power of the prevalent letter-we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word w by the ratio |rws|/|w|, where the word rws is minimal palindromic and rs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.     

Avoiding abelian squares in partial words

Erd?s raised the question whether there exist infinite abelian square-free words over a given alphabet, that is, words in which no two adjacent subwords are permutations of each other. It can easily be checked that no such word exists over a three-letter alphabet. However, infinite abelian square-free words have been constructed over alphabets of sizes as small as four. In this paper, we investigate the problem of avoiding abelian squares in partial words, or sequences that may contain some holes. In particular, we give lower and upper bounds for the number of letters needed to construct infinite abelian square-free partial words with finitely or infinitely many holes. Several of our constructions are based on iterating morphisms. In the case of one hole, we prove that the minimal alphabet size is four, while in the case of more than one hole, we prove that it is five. We also investigate the number of partial words of length n with a fixed number of holes over a five-letter alphabet that avoid abelian squares and show that this number grows exponentially with n.     

On the Class-number of the Maximal Real Subfield of a Cyclotomic Field

For any square-free positive integer m, let H(m) be the class-number of the field , where ζ_m is a primitive m-th root of unity. We show that if m = {3(8 g + 5)}² ? 2 is a square-free integer, where g is a positive integer, then H(4 m) > 1. Similar result holds for a square-free integer m = {3(8 g +7)}² ?2, where g is a positive integer. We also show that n|H(4 m) for certain positive integers m and n.     

Homotopy Spheres in Formal Language

The set of nonempty proper subwords of a word is either contractible or a homotopy n-sphere. There is a simple algorithm which computes n. The existence of spherical words is investigated, and the words which yield spheres are determined. A language which is closed under subwords has a finite number of components, and each component has a finitely generated fundamental group. For each n greater than 1, there is a language on two letters which has the homotopy type of an infinite cluster of n-sphere. There is a language on two letters which has nontrivial homology in each dimension greater than 1. If a language is closed under subwords and has bounded period, then it has the homotopy type of a finite polyhedron.     

The euclidean bianchi group

The Bianchi Groups Γ_d are PSL₂(0_d) where 0_d is the ring of integers in the quadratic imaginary number field Q√-d with d a positive square-free rational integer. If d=1,2,3,7,11 0_d has a Euclidean algorithm and the corresponding groups are called the Euclidean Bianchi Groups. The group Γ₁ is the Picard Group has been studied independently. Here the subgroup structure of the remaining Euclidean Bianchi Groups is investigated. We show that they have a unique normal subgroup of index in if(n,6)=1 among other results. We also classify the abelian and nilpotent subgroups and discuss the structure of both congruence and non-congruence subgroups.     

A Note on the Multiplicative Semigroups Z n Whose Bi-ideals Are Quasi-ideals

We show that for any positive integer n, the multiplicative semigroup Z_n has the property that the set of bi-ideals and the set of quasi-ideals coincide if and only if either n = 4 or n is square-free.AMS Subject Classification (1991): 20M10     

On the Decomposition of an Operator into a Sum of Four Idempotents

We prove that operators of the form (2 ± 2/n)I + K are decomposable into a sum of four idempotents for integer n > 1 if there exists the decomposition K = K ₁ K ₂ ... K _n, , of a compact operator K. We show that the decomposition of the compact operator 4I + K or the operator K into a sum of four idempotents can exist if K is finite-dimensional. If n trK is a sufficiently large (or sufficiently small) integer and K is finite-dimensional, then the operator (2 – 2/n)I + K [or (2 + 2/n)I + K] is a sum of four idempotents.     

On Rauzy graph sequences of infinite words

Under study are the sequences of Rauzy graphs (i.e., the graphs of subwords overlapping) of infinite words. The k-stretching of a graph is the graph we obtain by replacing each edge with a chain of length k. Considering a sequence of strongly connected directed graphs of maximal in and out vertex degrees equal to s, we prove that it is, up to stretchings, a subsequence of a Rauzy graphs sequence of some uniformly recurrent infinite word on s-letter alphabet. The language of a word of this kind and stretching for a given sequence of graphs are constructed explicitly.     

Edge-Ramsey theory

LetK be a configuration, a set of points in some finite-dimensional Euclidean space. Letn andk be positive integers. The notationR(K, n, r) is an abbreviation for the following statement: For everyr-coloring of the points of then-dimensional Euclidean space,R ⁿ , a monochromatic configurationL which is congruent toK exists. A configurationK is Ramsey if the following holds: For every positive integerr, a positive integern=n(K, r) exists such that, for allm≥n, R(K, m, r) holds. A configuration is spherical if it can be embedded in the surface of a sphere inn-space, providedn is sufficiently large. It is relatively easy to show that if a configuration is Ramsey, it must be spherical. Accordingly, a good fraction of the research efforts in Euclidean Ramsey theory is devoted to determining which spherical configurations are Ramsey. It is known that then-dimensional measure polytopes (the higher-dimensional analogs of a cube), then-dimensional simplex, and the regular polyhedra inR ² andR ³ are Ramsey. Now letE denote a set of edges in a configurationK. The pair (K, E) is called an edge-configuration, andR _e (K, E, n, r) is used as an abbreviation for the following statement: For anyr-coloring of the edges ofR ⁿ , there is an edge configuration (L, F) congruent to (K, E) so that all edges inF are assigned the same color. An edge-configuration isedge-Ramsey if, for allr≥1, a positive integern=n(K, E, r) exists so that ifm≥n, the statementR _e (K, E, m, r) holds. IfK is a regular polytope, it is saidK isedge-Ramsey when the configuration determined by the set of edges of minimum length is edge-Ramsey. It is known that then-dimensional simplex is edge-Ramsey and that the nodes of any edge-Ramsey configuration can be partitioned into two spherical sets. Furthermore, the edges of any edge-Ramsey configuration must all have the same length. It is conjectured that the unit square is edge-Ramsey, and it is natural to ask the more general question: Which regular polytopes are edge-Ramsey? In this article it is shown that then-dimensional measure polytope and then-dimensional cross polytope are edge-Ramsey. It is also shown that these two infinite families and then-dimensional simplexes are the only regular edge-Ramsey polytopes, with the possible exceptions of the hexagon and the 24-cell.     

On the finite basis problem for certain 2-limited words

Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S(W) be the Rees quotient X*/I(W), where I(W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S(W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S(W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.     

On component factors

LetK be a connected graph. A spanning subgraphF ofG is called aK-factor if every component ofF is isomorphic toK. On the existence ofK-factors we show the following theorem: LetG andK be connected graphs andp be an integer. Suppose|G| = n|K| and 1 <p < n. Also suppose every induced connected subgraph of orderp|K| has aK-factor. ThenG has aK-factor.     

Unbordered factors and Lyndon words

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order. A word w is bordered if there is a nonempty word u such that w=uvu for some word v. A right extension of a word w of length n is a word wu where all factors longer than n are bordered. A right extension wu of w is called trivial if there exists a positive integer k such that w^k=uv for some word v.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word w which has a nontrivial right extension of length 2|w|-2.     

Bases and nonbases of square-free integers

A basis is a set A of nonnegative integers such that every sufficiently large integer n can be represented in the form n = a_i + a_j with a_i, a_i ∈ A. If A is a basis, but no proper subset of A is a basis, then A is a minimal basis. A nonbasis is a set of nonnegative integers that is not a basis, and a nonbasis A is maximal if every proper superset of A is a basis. In this paper, minimal bases consisting of square-free numbers are constructed, and also bases of square-free numbers no subset of which is minimal. Maximal nonbases of square-free numbers do not exist. However, nonbases of square-free numbers that are maximal with respect to the set of square-free numbers are constructed, and also nonbases of square-free numbers that are not contained in any nonbasis of square-free numbers maximal with respect to the square-free numbers.     

Coherent random allocations, and the Ewens-Pitman formula

Assume that there is a random number K of positive integer random variables S₁, …, S_K that are conditionally independent given K and all have identical distributions. A random integer partition N = S₁ + S₂ + … + S_K arises, and we denote by P_N the conditional distribution of this partition for a fixed value of N. We prove that the distributions {P_N} _N=1 ^∞ form a partition structure in the sense of Kingman if and only if they are governed by the Ewens-Pitman Formula. The latter generalizes the celebrated Ewens sampling formula, which has numerous applications in pure and applied mathematics. The distributions of the random variables K and S_j belong to a family of integer distributions with two real parameters, which we call quasi-binomial. Hence every Ewens-Pitman distribution arises as a result of a two-stage random procedure based on this simple class of integer distributions. Bibliography: 25 titles. This paper is an edited and actualized version of the unpublished PDMI preprint 21/1995. Further development of the ideas of this work can be found in [21, 25]. A number of detected misprints was fixed without notice, the bibliography was extended beyond the original 19 references, and a few comments were added as footnotes. (Comments by Alexander Gnedin.) __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 325, 2005, pp. 127–145.     

Square-free rings

Square-free algebras have been studied in a variety of settings amd have been completely characterized by Anderson and D ’Ambrosia. In this paper, we extend the definition of square-free to Artinian rings with identity and begin to develop the theory of square-free rings. We show that every square-free ring has an associated division ring and square-free semigroup. Many square-free rings are square-free D -algebras, i.e. rings of the form D? _K A where D is a division ring with center K and A is a square-free K-algebra. We present a characteriza-tion of all square-free D -algebras and provide examples of square-free rings that are not D-algebras.     

Replacement of Factors By Subgroups in the Factorization of Abelian Groups

In his book Abelian groups, L. Fuchs raised the question asto whether, in general, in the factorization of a finite (cyclic)abelian group one factor may always be replaced by some subgroup.The answer turned out to be negative in general, but positivein certain cases. In this paper the complete answer for cyclicgroups is given. In all previously unsolved cases, the answerturns out to be positive. It is shown that a cyclic group hasthe property that in every factorization, one factor may bereplaced by a subgroup if and only if the group has order equalto the product of a prime and a square-free integer. Certainresults are also given in non-cyclic cases. 1991 MathematicsSubject Classification 20K01.     

A new statistic on Dyck paths for counting 3-dimensional Catalan words

A 3-dimensional Catalan word is a word on three letters so that the subword on any two letters is a Dyck path. For a given Dyck path D, a recently defined statistic counts the number of Catalan words with the property that any subword on two letters is exactly D. In this paper, we enumerate Dyck paths with this statistic equal to certain values, including all primes. The formulas obtained are in terms of Motzkin numbers and Motzkin ballot numbers.     

A degree condition for the existence of regular factors in K1, n-free graphs

A graph is called K_{1, n}-free if it contains no K_{1, n} as an induced subgraph. Let n(≥3), r be integers (if r is odd, r ≥ n − 1). We prove that every K_{1, n}-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least. $ \left(n+{{n-1}\over{r}}\right) \left\lceil {n\over{2(n-1)}}r \right\rceil - {{n-1}\over{r}}\left(\left\lceil {n\over{2(n-1)}}r \right\rceil \right)^2+n-3. $ This degree condition is sharp. © 1996 John Wiley & Sons, Inc.