On Certain C-Test Words for Free Groups

Let F_m be a free group of a finite rank m ≥ 2 and let X_i, Y_j be elements in F_m. A non-empty word w(x₁,…,x_n) is called a C-test word in n letters for F_m if, whenever (X₁,…,X_n) = w(Y₁,…,Y_n) ≠ 1, the two n-typles (X₁,…,X_n) and (Y₁,…,Y_n) are conjugate in F_m. In this paper we construct, for each n ≥ 2, a C-test word v_n(x₁,…,x_n) with the additional property that v_n(X₁,…,X_n) = 1 if and only if the subgroup of F_m generated by X₁,…,X_n is cyclic. Making use of such words v_m(x₁,…,x_m) and v_m + 1(x₁,…,x_m + 1), we provide a positive solution to the following problem raised by Shpilrain: There exist two elements u₁, u₂ ∈ F_m such that every endomorphism ψ of F_m with non-cyclic image is completely determined by ψ(u₁), ψ(u₂).     

Statistical properties of nucleotides in human chromosomes 21 and 22

In this paper the statistical properties of nucleotides in human chromosomes 21 and 22 are investigated. The n-tuple Zipf analysis with n = 3, 4, 5, 6, and 7 is used in our investigation. It is found that the most common n-tuples are those which consist only of adenine (A) and thymine (T), and the rarest n-tuples are those in which GC or CG pattern appears twice. With the n-tuples become more and more frequent, the double GC or CG pattern becomes a single GC or CG pattern. The percentage of four nucleotides in the rarest ten and the most common ten n-tuples are also considered in human chromosomes 21 and 22, and different behaviors are found in the percentage of four nucleotides. Frequency of appearance of n-tuple f(r) as a function of rank r is also examined. We find the n-tuple Zipf plot shows a power-law behavior for r < 4ⁿ⁻¹ and a rapid decrease for r > 4ⁿ⁻¹. In order to explore the interior statistical properties of human chromosomes 21 and 22 in detail, we divide the chromosome sequence into some moving windows and we discuss the percentage of ξη (ξ, η = A, C, G, T) pair in those moving windows. In some particular regions, there are some obvious changes in the percentage of ξη pair, and there maybe exist functional differences. The normalized number of repeats N₀(l) can be described by a power law: N₀(l) ∼ l^−μ. The distance distributions P₀(S) between two nucleotides in human chromosomes 21 and 22 are also discussed. A two-order polynomial fit exists in those distance distributions: log P₀(S) = a + bS + cS², and it is quite different from the random sequence.     

Characterizations of PG(n − 1, q)\PG(k − 1, q) by Numerical and Polynomial Invariants

We show that the simple matroid PG(n − 1, q)\PG(k − 1, q), for n ≥ 4 and 1 ≤ k ≤ n − 2, is characterized by a variety of numerical and polynomial invariants. In particular, any matroid that has the same Tutte polynomial as PG(n − 1, q)\PG(k − 1, q) is isomorphic to PG(n − 1, q)\PG(k − 1, q).     

Interpolation by Integer-Valued Polynomials

LetRbe a Krull ring with quotient fieldKanda₁,…,a_ninR. If and only if thea_iare pairwise incongruent mod every height 1 prime ideal of infinite index inRdoes there exist for all valuesb₁,…,b_ninRan interpolating integer-valued polynomial, i.e., anf ∈ K[x] withf(a_i) = b_iandf(R) ⊆ R.IfSis an infinite subring of a discrete valuation ringR_vwith quotient fieldKanda₁,…,a_ninSare pairwise incongruent mod allM^k_v ∩ Sof infinite index inS, we also determine the minimald(depending on the distribution of thea_iamong residue classes of the idealsM^k_v ∩ S) such that for allb₁,…,b_n ∈ R_vthere exists a polynomialf ∈ K[x] of degree at mostdwithf(a_i) = b_iandf(S) ⊆ R_v.     

A semi-Markov process with an inverse Gaussian distribution as sojourn time

Let X_n denote the state of a device after n repairs. We assume that the time between two repairs is the time τ taken by a Wiener process {W(t), t ? 0}, starting from w₀ and with drift μ < 0, to reach c ∈ [0, w₀). After the nth repair, the process takes on either the value X_n?1 + 1 or X_n?1 + 2. The probability that X_n = X_n?1 + j, for j = 1, 2, depends on whether τ ? t₀ (a fixed constant) or τ > t₀. The device is considered to be worn out when X_n ? k, where k ∈ {1, 2, …}. This model is based on the ones proposed by Rishel (1991) [1] and Tseng and Peng (2007) [2]. We obtain an explicit expression for the mean lifetime of the device. Numerical methods are used to illustrate the analytical findings.     

On generalized Jordan 1-derivation in rings

Let n ⩾ 1 be a fixed integer and let R be an (n + 1)!-torsion free 1-ring with identity element e. If F, d:R → R are two additive mappings satisfying F(xⁿ⁺¹) = F(x)(x¹)ⁿ + xd(x)(x¹)ⁿ⁻¹ + x²d(x)(x¹)ⁿ⁻²+ ⋯ +xⁿd(x) for all x ∈ R, then d is a Jordan 1-derivation and F is a generalized Jordan 1-derivation on R.     

Complexity Estimates for the Schmüdgen Positivstellensatz

LetKbe a closed basic set inRⁿgiven by the polynomial inequalities φ₁≥ 0, . . . , φ_m≥ 0 and let Σ be the semiring generated by the φ_kand the squares inR[x₁, . . . ,x_n]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iff∈R⁺+ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0⁺, in any representation off + das an element of Σ in terms of the φ_k, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd^−1/2≤N(d) ≤Cd^−1/2log (1/d).     

Quantum Complexity of Integration

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes F^k, α_d on [0, 1]^d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(F^k, α_d, ε)≍ε^−1/γ and comp^random(F^k, α_d, ε)≍ε^−2/(1+2γ). For a quantum computer we prove comp^quant_query(F^k, α_d, ε)≍ε^−1/(1+γ) and comp^quant(F^k, α_d, ε)⩽Cε^−1/(1+γ)(log ε⁻¹)^1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove comp^coin(F^k, α_d, ε)⩽Cε^−2/(1+2γ)(log ε⁻¹)^1/(1+2γ). To summarize the results one can say that   • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small;   • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small.     

New exact solitary-wave special solutions for the nonlinear dispersive K(m, n) equations

In this paper, we study the nonlinear dispersive K(m, n) equations: u_t + (u^m)_x − (uⁿ)_xxx = 0 which exhibit solutions with solitary patterns. New exact solitary solutions are found. The two special cases, K(2, 2) and K(3, 3), are chosen to illustrate the concrete features of the decomposition method in K(m, n) equations. The nonlinear equations K(m, n) are studied for two different cases, namely when m = n being odd and even integers. General formulas for the solutions of K(m, n) equations are established.     

A Bijective Approach to the Area of Generalized Motzkin Paths

For fixed positive integer k, let E_n denote the set of lattice paths using the steps (1, 1), (1, − 1), and (k, 0) and running from (0, 0) to (n, 0) while remaining strictly above the x-axis elsewhere. We first prove bijectively that the total area of the regions bounded by the paths of E_n and the x-axis satisfies a four-term recurrence depending only on k. We then give both a bijective and a generating function argument proving that the total area under the paths of E_n equals the total number of lattice points on the x-axis hit by the unrestricted paths running from (0, 0) to (n − 2, 0) and using the same step set as above.     

On “P” property and the column-W property

P-matrices play an important role in the well-posedness of a linear complementarity problem (LCP). Similarly, the well-posedness of a horizontal linear complementarity problem (HLCP) is closely related to the column-W property of a matrix k-tuple.In this paper we first consider the problem of generating P-matrices from a given pair of matrices. Given a matrix pair (D, F) where D is a square matrix of order m and matrix F has m rows, “what are the conditions under which there exists a matrix G such that (D + FG) is a P-matrix?”. We obtain necessary and sufficient conditions for the special case when the column rank of F is m ? 1. A decision algorithm of complexity O(m²) to check whether the given pair of matrices (D, F) is P-matrisable is obtained. We also obtain a necessary and an independent sufficient condition for the general case when rank(F) is less than m ? 1.We then generalise the P-matrix generating problem to the generation of matrix k-tuples satisfying the column-W property from a given matrix (k + 1)-tuple. That is, given a matrix (k + 1)-tuple (D₁, … ,D_k, F), where D_js are square matrices of order m and F is a matrix having m rows, we determine the conditions under which the matrix k-tuple (D₁ + FG₁, … ,D_k + FG_k) satisfies the column-W property. As in the case of P-matrices we obtain necessary and sufficient conditions for the case when rank(F) = m ? 1. Using these conditions a decision algorithm of complexity O(km²) to check whether the given matrix (k + 1)-tuple is column-W matrisable is obtained. Then for the case when rank(F) is less than m ? 1, we obtain a necessary and an independent sufficient condition.For a special sub-class of P-matrices we give a polynomial time decision algorithm for P-matrisability. Finally, we obtain a geometric characterisation of column-W property by generalising the well known separation theorem for P-matrices.     

An exact algorithm for the knapsack sharing problem with common items

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, N_k (k = 0, 1, … , s). The player k is concerned only with the items in N₀ ∪ N_k, where N₀ is the set of ‘common’ items, while N_k represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.     

An extended rational interpolation method

To interpolate function, f(x), a ? x ? b, when we have some information about the values of f(x) and their derivatives in separate points on {x₀, x₁, … , x_n} ? [a, b], the Hermit interpolation method is usually used. Here, to solve this kind of problems, extended rational interpolation method is presented and it is shown that the suggested method is more efficient and suitable than the Hermit interpolation method, especially when the function f(x) has singular points in interval [a, b]. Also for implementing the extended rational interpolation method, the direct method and the inverse differences method are presented, and with some examples these arguments are examined numerically.     

Combinatorial R Matrices for a Family of Crystals: B(1)n,D(1)n,A(2)2n,and D(2)n + 1 Cases

For coherent families of crystals of affine Lie algebras of type B⁽¹⁾_n, D⁽¹⁾_n, A⁽²⁾_2n, and D⁽²⁾_n + 1 we describe the combinatorial R matrix using column insertion algorithms for B, C, D Young tableaux. This is a continuation of previous work by the authors (2000, in “Physical Combinatorics” (M. Kashiwara and T. Miwa, Eds.), Birkhäuser, Boston).     

Calculation of a static potential created by plane fractal cluster

In this paper we demonstrate new approach that can help in calculation of electrostatic potential of a fractal (self-similar) cluster that is created by a system of charged particles. For this purpose we used the simplified model of a plane dendrite cluster [1] that is generated by a system of the concentric charged rings located in some horizontal plane (see Fig. 2). The radiuses and charges of the system of concentric rings satisfy correspondingly to relationships: r_n = r₀ξⁿ and e_n = e₀bⁿ, where n determines the number of a current ring. The self-similar structure of the system considered allows to reduce the problem to consideration of the functional equation that similar to the conventional scaling equation. Its solution represents itself the sum of power-low terms of integer order and non-integer power-law term multiplied to a log-periodic function [5], [6]. The appearance of this term was confirmed numerically for internal region of the self-similar cluster (r₀ ≪ r ≪ r_N−1), where r₀, r_N−1 determine the smallest and the largest radiuses of the limiting rings correspondingly. The results were obtained for homogeneously (b > 0) and heterogeneously (b < 0) charged rings. We expect that this approach allows to consider more complex self-similar structures with different geometries of charge distributions.     

Special Functions on the Sphere with Applications to Minimal Surfaces

A function which is homogeneous in x, y, z of degree n and satisfies V_xx + V_yy + V_zz = 0 is called a spherical harmonic. In polar coordinates, the spherical harmonics take the form rⁿf_n, where f_n is a spherical surface harmonic of degree n. On a sphere, f_n satisfies ▵ f_n + n(n + 1)f_n = 0, where ▵ is the spherical Laplacian. Bounded spherical surface harmonics are well studied, but in certain instances, unbounded spherical surface harmonics may be of interest. For example, if X is a parameterization of a minimal surface and n is the corresponding unit normal, it is known that the support function, w = X · n, satisfies ▵w + 2w = 0 on a branched covering of a sphere with some points removed. While simple in form, the boundary value problem for the support function has a very rich solution set. We illustrate this by using spherical harmonics of degree one to construct a number of classical genus-zero minimal surfaces such as the catenoid, the helicoid, Enneper's surface, and Hennenberg's surface, and Riemann's family of singly periodic genus-one minimal surfaces.     

Fast Rectangular Matrix Multiplication and Applications

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of ann×nmatrix by ann×n²matrix in arithmetic timeO(n^ω),ω=3.333953…, which is less by 0.041 than the previous record 3.375477…. Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results:   (a) we decrease from 2.851 to 2.837 the known exponent of the work bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of ann×nmatrix, as well as for the solution to a nonsingular linear system ofnequations,   (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod xⁿ, yielding the complexity boundO(n^1.667) versus the old record ofO(n^1.688), and for the univariate polynomial factorization over a finite field, and   (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem withmconstraints andnvariables.     

The Exponent of Discrepancy Is at Least 1.0669

LetP⊂[0, 1]^dbe ann-point set and letw: P→[0, ∞) be a weight function withw(P)=∑_z∈P w(z)=1. TheL₂-discrepancy of the weighted set (P, w) is defined as theL₂-average ofD(x)=vol(B_x)−w(P∩B_x) overx∈[0, 1]^d, where vol(B_x) is the volume of thed-dimensional intervalB_x=∏^d_k=1 [0, x_k). The exponent of discrepancyp* is defined as the infimum of numberspsuch that for all dimensionsd⩾1 and allε>0 there exists a weighted set of at mostKε^−ppoints in [0, 1]^dwithL₂-discrepancy at mostε, whereK=K(p) is a suitable number independent ofεandd. Wasilkowski and Woźniakowski proved thatp*⩽1.4779, by combining known bounds for the error of numerical integration and using their relation toL₂-discrepancy. In this note we observe that a careful treatment of a classical lower- bound proof of Roth yieldsp*⩾1.04882, and by a slight modification of the proof we getp*⩾1.0669. Determiningp* exactly seems to be quite a difficult problem.