Graph of a Nearring with Respect to an Ideal

We introduce a concept called the graph of a nearring N with respect to an ideal I of N denoted by G _I (N). Then we define a new type of symmetry called ideal symmetry of G _I (N). The ideal symmetry of G _I (N) implies the symmetry determined by the automorphism group of G _I (N). We prove that if I is a 3-prime ideal of a zero-symmetric nearring N then G _I (N) is ideal symmetric. Under certain conditions, we find that if G _I (N) is ideal symmetric then I is 3-prime. Finally, we deduce that if N is an equiprime nearring then the prime graph of N is ideal symmetric.     

On Computing the Subset Graph of a Collection of Sets

Let a given collection of sets have size N measured by the sum of the cardinalities. Yellin and Jutla presented an algorithm which constructed the partial order induced by the subset relation (a “subset graph”) in a claimed O(N²/log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Θ(N²/log² N) edges. This paper first establishes a matching upper bound on the number of edges in a subset graph. It also presents a finer analysis of the algorithm, which confirms the claimed upper bound and shows it to be tight. A simple implementation requiring O(1) bit-parallel operations per ADT operation is presented, along with a variant of the algorithm with an implementation requiring O(N²/log N) RAM operations.     

Calculating the mislin genus for a certain family of nilpotent groups

It is known that the Mislin genus of a finitely generated nilpotent group N with finite commutator subgroup admits an abelian group structure. In this paper, we compute explicitly that structure under the following additional assumptions: The torsion subgroup TN is abelian, the epimorphism N→N/TN splits and all automorphisms of TN commute with cinjugation by elements of N. Among the groups satisfying these conditions are all nilpotent split extensions of a finite cyclic group by a finitely free abelian group. We further prove that the function M ? M × N^k­1 k ≥ 2, which is in general a surjective homomorphism from the genus of N onto the genus of N^k , is an isomorphism at least in an imporatnt special case. Applications to the study of non-cancellation phenomena in group theory are given.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Berry–Esseen Bound for a Sample Sum from a Finite Set of Independent Random Variables

Let {X ₁,...,X _N} be a set of N independent random variables, and let S _n be a sum of n random variables chosen without replacement from the set {X ₁,...,X _N} with equal probabilities. In this paper we give an estimate of the remainder term for the normal approximation of S _n under mild conditions.     

Lagrangian model of a massless particle on spacelike curves

We consider a model of a massless particle in a D-dimensional space with the Lagrangian proportional to the Nth extrinsic curvature of the world line. We present the Hamiltonian formulation of the system and show that its trajectories are spacelike curves satisfying the conditions k _N+a =k _N-a and k _2N =0, a=1,,N-1, where N[(D-2)/2]. The first N curvatures take arbitrary values, which is a manifestation of N+1 gauge degrees of freedom; the corresponding gauge symmetry forms an algebra of the W type. This model describes D-dimensional massless particles, whose helicity matrix has N coinciding nonzero weights, while the remaining [(D-2)/2]-N weights are zero. We show that the model can be extended to spaces with nonzero constant curvature. It is the only system with the Lagrangian dependent on the world-line extrinsic curvatures that yields irreducible representations of the Poincaré group.     

On a multi-channel change-point problem

A continuous change-point problem is studied in which N independent diffusion processes X _j are observed. Each process X _j is associated with a “channel”, each has an unknown piecewise constant drift and the unit diffusion coefficient. All the channels are connected only by a common change-point of drift. As the result, a change-point problem is defined in which the unknown and unidentifiable drift forms a 2N-dimensional nuisance parameter. The asymptotics of the minimax rate in estimating the change-point is studied as N → ∞. This rate is compared with the case of the known drift. This problem is a special case of an open change-point detection problem in the high-dimensional diffusion with nonparametric drift.      

The Unitary Implementation of a Locally Compact Quantum Group Action

In this paper we study actions of locally compact quantum groups on von Neumann algebras and prove that every action has a canonical unitary implementation, paralleling Haagerup's classical result on the unitary implementation of a locally compact group action. This result is an important tool in the study of quantum groups in action. We will use it in this paper to study subfactors and inclusions of von Neumann algebras. When α is an action of the locally compact quantum group (M, Δ) on the von Neumann algebra N we can give necessary and sufficient conditions under which the inclusion N^αNM_αN is a basic construction. Here N^α denotes the fixed point algebra and M_αN is the crossed product. When α is an outer and integrable action on a factor N we prove that the inclusion N^αN is irreducible, of depth 2 and regular, giving a converse to the results of M. Enock and R. Nest (1996, J. Funct. Anal.137, 466–543; 1998, J. Funct. Anal.154, 67–109). Finally we prove the equivalence of minimal and outer actions and we generalize the main theorem of Yamanouchi (1999, Math. Scand.84, 297–319): every integrable outer action with infinite fixed point algebra is a dual action.     

Numerical differentiation inspired by a formula of R.P. Boas

First, we briefly discuss three classes of numerical differentiation formulae, namely finite difference methods, the method of contour integration, and sampling methods. Then we turn to an interpolation formula of R.P. Boas for the first derivative of an entire function of exponential type bounded on the real line. This formula may be classified as a sampling method. We improve it in two ways by incorporating a Gaussian multiplier for speeding up convergence and by extending it to higher derivatives. For derivatives of order s, we arrive at a differentiation formula with N^′ nodes that applies to all entire functions of exponential type without any additional restriction on their growth on the real line. It has an error bound that converges to zero like e^-αN/N^m as N→∞, where α>0 and N^′=2N, m=3/2 for odd s while N^′=2N+1, m=5/2 for even s. Comparable known formulae have stronger hypotheses and, for the same α, they have m=1/2 only. We also deduce a direct (error-free) generalization of Boas’ formula (Corollary 5). Furthermore, we give a modification of the main result for functions analytic in a domain and consider an extension to non-analytic functions as well. Finally, we illustrate the power of the method by examples.     

Analysis of a circulant based preconditioner for a class of lower rank extracted systems

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, A_px=b, which we call lower rank extracted systems (LRES), by the preconditioned conjugate gradient method. These systems correspond to integral equations with convolution kernels defined on a union of many line segments in contrast to only one line segment in the case of Toeplitz systems. The p × p matrix, A_p, is shown to be a principal submatrix of a larger N × N Toeplitz matrix, A_N. The preconditioner is provided in terms of the inverse of a 2N × 2N circulant matrix constructed from the elements of A_N. The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix similar to the clustering results for iterative algorithms used to solve Toeplitz systems. The analysis also demonstrates that the computational expense to solve LRE systems is reduced to O(N log N). Copyright © 2004 John Wiley & Sons, Ltd.     

Nonstationary weak limit of a stationary harmonic map sequence

Let M and N be two compact Riemannian manifolds. Let u_k be a sequence of stationary harmonic maps from M to N with bounded energies. We may assume that it converges weakly to a weakly harmonic map u in H^1,2 (M, N) as k → ∞. In this paper, we construct an example to show that the limit map u may not be stationary. © 2002 Wiley Periodicals, Inc.     

Large deviations for a simple closed queueing model

We consider a simple queueing model with one service station. The arrival and service processes have intensitiesa(N–Q _t) andNf(N ^–1 Q _t), where Q_t is the queue length,N is a large integer,a>0 andf(x) is a positive continuous function. We establish the large deviation principle for the sequence of the normalized queue length processq _N ^t =N ^–1Q_t,N1 for both light (a<f(0)) and heavy (af(0)) traffic and use this result for an investigation of ergodic properties ofq _N ^t ,N 1.     

A finite difference scheme of improved accuracy on a priori adapted grids for a singularly perturbed parabolic convection-diffusion equation

In the case of the Dirichlet problem for a singularly perturbed parabolic convection-diffusion equation with a small parameter ɛ multiplying the higher order derivative, a finite difference scheme of improved order of accuracy that converges almost ɛ-uniformly (that is, the convergence rate of this scheme weakly depends on ɛ) is constructed. When ɛ is not very small, this scheme converges with an order of accuracy close to two. For the construction of the scheme, we use the classical monotone (of the first order of accuracy) approximations of the differential equation on a priori adapted locally uniform grids that are uniform in the domains where the solution is improved. The boundaries of such domains are determined using a majorant of the singular component of the grid solution. The accuracy of the scheme is improved using the Richardson technique based on two embedded grids. The resulting scheme converges at the rate of O((ɛ⁻¹ N ^−K ln² N)² + N ⁻²ln⁴ N + N ₀⁻²) as N, N ₀ → ∞, where N and N ₀ determine the number of points in the meshes in x and in t, respectively, and K is a prescribed number of iteration steps used to improve the grid solution. Outside the σ-neighborhood of the lateral boundary near which the boundary layer arises, the scheme converges with the second order in t and with the second order up to a logarithmic factor in x; here, σ = O(N ^{−(K − 1)}ln² N). The almost ɛ-uniformly convergent finite difference scheme converges with the defect of ɛ-uniform convergence ν, namely, under the condition N ⁻¹ ≪ ɛ^ν, where ν determining the required number of iteration steps K (K = K(ν)) can be chosen sufficiently small in the interval (0, 1]. When ɛ⁻¹ = O(N ^{K − 1}), the scheme converges at the rate of O(N ⁻²ln⁴ N + N ₀⁻²).     

Finite Time Blow-up for a Non-linear Parabolic Equation with a Gradient Term and Applications

We give new finite time blow-up results for the non-linear parabolic equations u_t−Δu = u^p and u_t−Δu+μ∣∇u∣^q = u^p. We first establish an a priori bound in L^p+1 for the positive non-decreasing global solutions. As a consequence, we prove in particular that for the second equation on ℝ^N, with q = 2p/(p+1) and small μ>0, blow-up can occur for any N≥1, p>1, (N−2)p<N+2 and without energy restriction on the initial data. Incidentally, we present a simple model in population dynamics involving this equation.     

A decomposition algorithm for shortest paths in a network with many strongly connected components

Summary This paper presents an algorithm for finding all shortest distances in a network with a large number of strongly connected components. If the network hasN nodes the number of computations required by this algorithm is asymptotically 1/6N(N–1) (N–2) tripel operations.

---

Zusammenfassung In der vorliegenden Arbeit wird ein Algorithmus zur Bestimmung der Längen aller kürzesten Wege in Netzwerken mit mehreren strengen Zusammenhangskomponenten entwickelt. Besitzt das NetzwerkN Knoten, so hat man bei diesem Algorithmus asymptotisch insgesamt 1/6N(N–1 (N–2) Additionen und ebenso viele Vergleiche durchzuführen.

     

Conditions for periodic vibrations in a symmetric <Emphasis Type="Italic">n</Emphasis>-string

A symmetric N-string is a network of N ≥ 2 sections of string tied together at one common mobile extremity. In their equilibrium position, the sections of string form N angles of 2π/N at their junction point. Considering the initial and boundary value problem for small-amplitude oscillations perpendicular to the plane of the N-string at rest, we obtain conditions under which the solution will be periodic with an integral period.      

Invariant measure for a class of parabolic degenerate equations

In this paper we consider a stochastic flow in Rⁿ which leaves a closed convex set K invariant. By using a recent characterization of the invariance, involving the distance function, we study the corresponding transition semigroup P_t and its infinitesimal generator N. Due to the invariance property, N is a degenerate elliptic operator. We study existence of an invariant measure ν of P_t and the realization of N in L² (H, ν).     

The implicit function theorem in a non-Archimedean setting

In this paper, the inverse function theorem and the implicit function theorem in a non-Archimedean setting will be discussed. We denote by N any non-Archimedean field extension of the real numbers that is real closed and Cauchy complete in the topology induced by the order; and we study the properties of locally uniformly differentiable functions from Nⁿ to N^m. Then we use that concept of local uniform differentiability to formulate and prove the inverse function theorem for functions from Nⁿ to Nⁿ and the implicit function theorem for functions from Nⁿ to N^m with m<n.     

The linear quadratic minimum-time problem for a class of discrete systems

We consider a linear discrete-time systems controlled by inputs on L ²([0, t _N ], U), where (t _i )_{1?≤?i?≤?N} is a given sequence of times. The final time t _N (or N) is considered to be free. Given an initial state x ₀ and a final one x _d , we investigate the optimal control which steers the system from x ₀ to x _d with a minimal cost J(N, u) that includes the final time and energy terms. We treat this problem for both infinte and finite dimensional state space. We use a method similar to the Hilbert Uniqueness Method. A numerical simulation is given.