Graphs of difference operators for p-ary sequences

For a given prime p and positive integer n, we consider the graph G _n of the difference operator acting on p-ary sequences of length n. We suggest new proofs of some results of V.I. Arnold on the graph G _n and the complexity of sequences and obtain new results for the length of a maximal cycle in the general case of p-ary sequences. We also provide estimates for the number of complicated sequences.      

Proof of the local REM conjecture for number partitioning. II. Growing energy scales

We continue our analysis of the number partitioning problem with n weights chosen i.i.d. from some fixed probability distribution with density ρ. In Part I of this work, we established the so‐called local REM conjecture of Bauke, Franz and Mertens. Namely, we showed that, as n → ∞, the suitably rescaled energy spectrum above some fixed scale α tends to a Poisson process with density one, and the partitions corresponding to these energies become asymptotically uncorrelated. In this part, we analyze the number partitioning problem for energy scales α_n that grow with n, and show that the local REM conjecture holds as long as n^‐1/4α_n → 0, and fails if α_n grows like κn^1/4 with κ > 0. We also consider the SK‐spin glass model, and show that it has an analogous threshold: the local REM conjecture holds for energies of order o(n), and fails if the energies grow like κn with κ > 0. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the Maximal Multiplicity of Parts in a Random Integer Partition

We study the asymptotic behavior of the maximal multiplicity μ_n = μ_n(λ) of the parts in a partition λ of the positive integer n, assuming that λ is chosen uniformly at random from the set of all such partitions. We prove that πμ_n/(6n)^1/2 converges weakly to max _jX_j/j as n→∞, where X₁, X₂, … are independent and exponentially distributed random variables with common mean equal to 1.2000 Mathematics Subject Classification: Primary—05A17; Secondary—11P82, 60C05, 60F05     

Weighted endpoint estimates for commutators of fractional integrals

Given α, 0 < α < n, and b ∈ BMO, we give sufficient conditions on weights for the commutator of the fractional integral operator, [b, I _α ], to satisfy weighted endpoint inequalities on ℝⁿ and on bounded domains. These results extend our earlier work [3], where we considered unweighted inequalities on ℝⁿ.     

Discrimination Between B-Processes is Impossible

Two series of binary observations x ₁,x ₁,… and y ₁,y ₂,… are presented: x _n and y _n are given at each time n∈ℕ. It is assumed that the sequences are generated independently of each other by two B-processes. The question of interest is whether the sequences represent a typical realization of two different processes or of the same one. It is demonstrated that this is impossible to decide, in the sense that every discrimination procedure is bound to err with non-negligible frequency when presented with sequences from some B-processes. This contrasts with earlier positive results on B-processes, in particular, those showing that there are consistent [`(d)]\bar{d} -distance estimates for this class of processes, and on ergodic processes, in particular, those establishing consistent change point estimates.     

An almost‐bijective proof of an asymptotic property of partitions

Let 𝒫_n be the set of all distinct ordered pairs (λ,λ_i), where λ is a partition of n and λ_i is a part size of λ. The primary result of this note is a combinatorial proof that the probability that, for a pair (λ,λ_i) chosen uniformly at random from 𝒫_n, the multiplicity of λ_i in λ is 1 tends to 1/2 as n →∞. This is inspired by work of Corteel, Pittel, Savage, and Wilf (Random Structures and Algorithms 14 (1999), 185–197). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Generalized Sets of Lengths

LetRbe a Dedekind domain and (R) the set of irreducible elements ofR. In this paper, we study the sets _R(n) = {m | α₁,…,α_n, β₁,…,β_m (R) such that α₁,…,α_n = β₁,…,β_m}, wherenis a positive integer. We show, in constrast to indications in some earlier work, that the sets _R(n) are not completely determined by the Davenport constant of the class group ofR. We offer some specific constructions for Dedekind domains with small class groups, and show how these sets are generalizations of the sets studied earlier by Geroldinger [[9], [10]].     

QUASIREGULAR TORSION RINGS HAVING ISOMORPHIC ADDITIVE AND CIRCLE COMPOSITION GROUPS

Abstract

We investigate the role played by torsion properties in determining whether or not a commutative quasiregular ring has its additive and circle composition (or adjoint) groups isomorphic. We clarify and extend some results for nil rings, showing, in particular, that an arbitrary torsion nil ring has the isomorphic groups property if and only if the components from its primary decomposition into p-rings do too.

We look at the more specific case of finite rings, extending the work of others to show that a non-trivial ring with the isomorphic groups property can be constructed if the additive group has one of the following groups in its decomposition into cyclic groups: Z₂ ⁿ (for n ≥ 3), Z₂ ⊕ Z₂ ⊕ Z₂, Z₂ ⊕ Z₄, Z₄ ⊕ Z₄, Z _p ⊕ Z _p (for odd primes, p), or Z _p ⁿ (for odd primes, p, and n ≥ 2).

We consider, also, an example of a ring constructed on an infinite torsion group and use a specific case of this to show that the isomorphic groups property is not hereditary.     

Enumerating (Multiplex) Juggling Sequences

We consider the problem of enumerating periodic σ-juggling sequences of length n for multiplex juggling, where σ is the initial state (or landing schedule) of the balls. We first show that this problem is equivalent to choosing 1’s in a specified matrix to guarantee certain column and row sums, and then using this matrix, derive a recursion. This work is a generalization of earlier work of Chung and Graham.     

The linear polarization constant of R n

Summary He present work deals with estimations of the n-th linear polarization constant c(H)_n of an n-dimensional real Hilbert space H. We provide some new lower bounds on the value of sup_║y║=1 │1,y> ... n,y>│, where x₁, ... ,x_n are unit vectors in H. In particular, the results improve an earlier estimate of Marcus. However, the intriguing conjecture c(H) _n= n^n/2 remains open.     

Free limits of Thompson’s group <Emphasis Type="Italic">F</Emphasis>

We produce a sequence of markings S _k of Thompson’s group F within the space G_n{{\mathcal G}_n} of all marked n-generator groups so that the sequence (F, S _k ) converges to the free group on n generators, for n ≥ 3. In addition, we give presentations for the limits of some other natural (convergent) sequences of markings to consider on F within G₃{{\mathcal G}_3}, including (F, {x ₀, x ₁, x _n }) and (F,{x₀,x₁,x₀ⁿ}){(F,\{x_0,x_1,x_0^n\})}.     

A note about the filtering problem in discrete time making use of weak convergence of probability measures

In this paper we consider a partially observable stochastic processX _n ,Y _n , whereX _n is a Markov process andY _n depends only on the current value ofX _n . It is known that, under suitable regularity assumptions, ifX _n ,Y _n admits a finite-dimensional filter, then theprediction, observation, andfiltering densities are all of exponential class. We prove that, under some additional assumptions, the existence of a finite-dimensional filter implies that theMarkov transition kernel ofX _n is itself of exponential class. To do this we apply a simple property of weak convergence of probability measures.     

Extremal Systems of Points and Numerical Integration on the Sphere

This paper considers extremal systems of points on the unit sphere S ^r⊂R ^r+1, related problems of numerical integration and geometrical properties of extremal systems. Extremal systems are systems of d _n =dim P _n points, where P _n is the space of spherical polynomials of degree at most n, which maximize the determinant of an interpolation matrix. Extremal systems for S ² of degrees up to 191 (36,864 points) provide well distributed points, and are found to yield interpolatory cubature rules with positive weights. We consider the worst case cubature error in a certain Hilbert space and its relation to a generalized discrepancy. We also consider geometrical properties such as the minimal geodesic distance between points and the mesh norm. The known theoretical properties fall well short of those suggested by the numerical experiments.

     

Basic Commutators in Weights Six and Seven as Relators

Charles Sims has asked whether or not the lower central subgroup γ _n (F) of a free group F coincides with the normal closure in F of the basic commutators of weight n. This question has a positive answer in weights at most 5, but remains an open question in general. In earlier work with Gaglione and Spellman, it was shown that γ _n (F) is the normal closure in F of the basic commutators of weights n through 2n ? 4. Here, we specialize to the case where F has rank 2 and show that γ₆(F) is the normal closure in F of the basic commutators of weights 6 and 7.     

On the Homology and Fiber Cone of Ideals

In this article, we give a unified approach for several results concerning the fiber cone. Our novel idea is to use the complex C(x _k , ? _{I 1; I 2} , (1, n)). We improve earlier results obtained by several researchers and get some new results. We give a more general definition of ideals of minimal multiplicity and of ideals of almost minimal multiplicity. We also compute the Hilbert series of the fiber cone for these ideals.     

On the maximal multiplicity of block sizes in a random set partition

We study the asymptotic behavior of the maximal multiplicity M_n = M_n(σ) of the block sizes in a set partition σ of [n] = {1,2,…,n}, assuming that σ is chosen uniformly at random from the set of all such partitions. It is known that, for large n, the blocks of a random set partition are typically of size W = W(n), with We^W = n. We show that, over subsequences {n_k}_{k ≥ 1} of the sequence of the natural numbers, , appropriately normalized, converges weakly, as k→∞, to , where Z₁ and Z₂ are independent copies of a standard normal random variable. The subsequences {n_k}_{k ≥ 1}, where the weak convergence is observed, and the quantity u depend on the fractional part f_n of the function W(n). In particular, we establish that . The behavior of the largest multiplicity M_n is in a striking contrast to the similar statistic of integer partitions of n. A heuristic explanation of this phenomenon is also given.     

Reorienting regularn-gons

Imagine that randomly oriented objects in the shape of a regularn-sided polygon are moving on a conveyor. Our aim is to specify sequences composed of two different rigid motions which, when performed on these objects, will reposition them in all possible ways. We call such sequencesfacing sequences. (Expressed in group theoretical terms, a facing sequence in a groupG is a sequence of elementsa ₁,a ₂, ...,a _n fromG such thatG={e,a ₁,a ₁ a ₂, ...,a ₁ a ₂ ...a _n }). In this paper we classify various kinds of facing sequences and determine some of their properties. The arguments are group theoretical and combinatorial in nature.     

Some algebraic properties of hypergraphs

We consider Stanley-Reisner rings k[x ₁, …, x _n ]/I(H) where I(H) is the edge ideal associated to some particular classes of hypergraphs. For instance, we consider hypergraphs that are natural generalizations of graphs that are lines and cycles, and for these we compute the Betti numbers. We also generalize some known results about chordal graphs and study a weak form of shellability.     

Some Skew Linear Groups Satisfying Generalized Group Identities

In this article, we consider a type of generalized group identity and extend some earlier results. For example, we show that, if D is a division ring with infinite center, then every subnormal subgroup of GL_n(D) satisfying a generalized group identity over GL_n(D) is central.     

Permutation Polyhedra and Minimisation of the Variance of Completion Times on a Single Machine

We consider the problem of minimising variance of completion times when n-jobs are to be processed on a single machine. This problem is known as the CTV problem. The problem has been shown to be difficult. In this paper we consider the polytope P _n whose vertices are in one-to-one correspondence with the n! permutations of the processing times [p ₁, p ₂, ..., p _n]. Thus each vertex of P _n represents a sequence in which the n-jobs can be processed. We define a V-shaped local optimal solution to the CTV problem to be the V-shaped sequence of jobs corresponding to which the variance of completion times is smaller than for all the sequences adjacent to it on P _n. We show that this local solution dominates V-shaped feasible solutions of the order of 2 ^n–3 where 2 ^n–2 is the total number of V-shaped feasible solutions.Using adjacency structure an P _n, we develop a heuristic for the CTV problem which has a running time of low polynomial order, which is exact for n 10, and whose domination number is (2 ^n–3). In the end we mention two other classes of scheduling problems for which also ADJACENT provides solutions with the same domination number as for the CTV problem.