A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

Distributions having bases which generate finite dimensional Lie algebras

Let X¹,…, X^k be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TM_p. Then X¹,…, X^k form a local basis for a real analytic k-dimensional distribution x→D^k(x)=span{X¹(x),…,X^k(x)}. We study the question of when D^k admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X¹,…, X^k can often be greatly simplified.     

Uniform finite generation of compact Lie groups

Consider a compact connected Lie group G and the corresponding Lie algebra . Let {X₁,…,X_m} be a set of generators for the Lie algebra . We prove that G is uniformly finitely generated by {X₁,…,X_m}. This means that every element KG can be expressed as K=e^Xt₁e^Xt₂···e^Xt_l, where the indeterminates X are in the set {X₁,…,X_m}, , and the number l is uniformly bounded. This extends a previous result by F. Lowenthal in that we do not require the connected one dimensional Lie subgroups corresponding to the X_i, i=1,…,m, to be compact. We link the results to the existence of universal logic gates in quantum computing and discuss the impact on bang bang control algorithms for quantum mechanical systems.     

Further oscillation criteria for delay partial difference equations

This paper is concerned with the partial difference equation A_m+1,n+A_m,n+1−A_m,n+p_m,nA_m−k,n−l=0,m,n=0,1,2,…,, where k and l are two positive integers, {p_m,n} is a real double sequence. Some new oscillation criteria for this equation are obtained.     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

The Computational Complexity of Some Julia Sets

Numerous computer programs have been written to compute sets of points which approximate Julia sets [4]. Usually, no error estimations are added so that it remains unclear, how good such approximations are. Furthermore, high precision pictures are unreliable because of rounding errors, since the realizing computer programs use fixed length floating point numbers. Computable error estimation w.r.t. the Hausdorff metric d_H means that the set is recursive [10]. Many Julia sets J are recursive [11]. Recursive compact subsets of the Euclidean plane have a computable Turing machine time complexity [10]. In this paper we prove that the Julia set of a complex function f(z) = z² + c for c < 1/4 can be computed locally in time O(k²M(k)) (where M(k) is a time bound for multiplication of k-bit integers). Roughly speaking, the local time complexity is the number of Turing machine steps to decide for a single point whether it belongs to a grid K_k (2^−k · )² such that d_H(K_k,J) ≤ = 2^−k.     

Job scheduling to minimize expected weighted flowtime on uniform processors

We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate μ_j, where μ₁μ₂μ_m. Job i incurs a holding cost at rate c_i per unit time while still in the system, where c₁c₂c_n. We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if k>(Σ_i^j−₁μ_i)/μ_j−j k−1. After each assignment the jobs are renumbered (so that job k+1 becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs c_i. This result is a generalization of the result of Agrawala et al. (1984) for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result.     

Conditioning of infinite Hankel matrices of finite rank

Let H be an infinite Hankel matrix with h_i+j−2 as its (i,j)-entry, h_k=∑_l=1ⁿr_l z_l^k, k=0,1,…,|z_l|<1, and . We derive upper bounds for the 2-condition number of H as functions of n, r_l and z_l, which show that the Hankel matrix H becomes well conditioned whenever the z's are close to the unit circle but not extremely close to each other. Numerical results which illustrate the theory are provided.     

Characterizations of distributions of exponential or geometric type by the integrated lack of memory property and record values

Let be a sequence of i.i.d. random variables, the sequence of its upper record values (i.e. L(0) = 1, L(n) = inf{jX_j>X_L(n−1} for n≥1). Without any assumptions to the support of P^X₁ the equidistribution of X₁ and a record increment X_L(n − X_L(n−1), n ≥ 1 yields X₁ to be either exponentially or geometrically distributed according to whether the additive subgroup generated by the support of P^X₁ is dense or a lattice in . The integrated lack of memory property can easily be reduced to the above problem for the case n = 1. Similarly the independence of X_L(n−1) and X_L(n) − X_L(n−1) for some n>1 characterizes X₁ to have e exponential or a geometric tail provided that the support of P^X₁ is bounded to the left and its right extremity no atom. Hence, if also its left extremity is no atom the independence of X_L(n−1) and X_L(n−1) − X_L(n−1) characterizes X₁ to be exponentially distributed.     

Rank and eigenvalues of a supersymmetric tensor, the multivariate homogeneous polynomial and the algebraic hypersurface it defines

A real n-dimensional homogeneous polynomial f(x) of degree m and a real constant c define an algebraic hypersurface S whose points satisfy f(x)=c. The polynomial f can be represented by Ax^m where A is a real mth order n-dimensional supersymmetric tensor. In this paper, we define rank, base index and eigenvalues for the polynomial f, the hypersurface S and the tensor A. The rank is a nonnegative integer r less than or equal to n. When r is less than n, A is singular, f can be converted into a homogeneous polynomial with r variables by an orthogonal transformation, and S is a cylinder hypersurface whose base is r-dimensional. The eigenvalues of f, A and S always exist. The eigenvectors associated with the zero eigenvalue are either recession vectors or degeneracy vectors of positive degree, or their sums. When c⁄=0, the eigenvalues with the same sign as c and their eigenvectors correspond to the characterization points of S, while a degeneracy vector generates an asymptotic ray for the base of S or its conjugate hypersurface. The base index is a nonnegative integer d less than m. If d=k, then there are nonzero degeneracy vectors of degree k−1, but no nonzero degeneracy vectors of degree k. A linear combination of a degeneracy vector of degree k and a degeneracy vector of degree j is a degeneracy vector of degree k+j−m if k+j≥m. Based upon these properties, we classify such algebraic hypersurfaces in the nonsingular case into ten classes.     

Direct amperometric determination of l-ascorbic acid (Vitamin C) at octacyanomolybdate-doped-poly(4-vinylpyridine) modified electrode in fruit juice and pharmaceuticals

The glassy carbon electrode (GCE) modified with Mo(CN)₈⁴⁻-incorporated-poly(4-vinylpyridine) (PVP/Mo(CN)₈⁴⁻), which has been recently shown to possess several attractive attributes as an efficient electrocatalytic electrode for l-ascorbic acid oxidation and its estimation, is used for l-ascorbic acid estimation directly in orange fruit juice and Celin tablet in a 0.1 M H₂SO₄ acid solution without any special treatment. Constant potential amperometry at 570 mV (saturated calomel electrode, SCE) in stirred solutions is used for this purpose. A good correlation is attained with the official titrametric method. To understand the possible electrocatalytic reaction mechanism for the electro-oxidation of l-ascorbic acid, calibration graphs over the range 1 × 10⁻⁵ to 1 × 10⁻² mol dm⁻³ l-ascorbic acid are compared for the three electrodes, ca. PVP/Mo(CN)₈⁴⁻, undoped PVP, and GCE; the curvature at high ascorbic acid concentration for the PVP/Mo(CN)₈⁴⁻ electrode is explained in terms of Michaelis–Menten (MM) saturation kinetics. The apparent MM constant (K_M), the maximum catalytic current (i_M), the complex decomposition rate constant (k_c), and the heterogeneous modified electrode rate constant (k^′_ME) are calculated from three different approaches. A reasonably high value of ≈1 × 10⁻² cm s⁻¹ is obtained for k^′_ME, indicating efficient l-ascorbic acid mediation at the PVP/Mo(CN)₈⁴⁻ electrode, thus accounting for quite a high sensitivity of this modified film electrode compared to several other modified electrodes.     

Elements of small norm in Shanks’ cubic extensions of imaginary quadratic fields

Let be an imaginary quadratic number field with ring of integers Z_k and let k(α) be the cubic extension of k generated by the polynomial f_t(x)=x³−(t−1)x²−(t+2)x−1 with tZ_k. In the present paper we characterize all elements γZ_k[α] with norms satisfying |N_k(α)/k|≤|2t+1| for |t|≥14. This generalizes a corresponding result by Lemmermeyer and Pethő for Shanks’ cubic fields over the rationals.     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Strategy for a class of games with dynamic ties

Let 0 < 2b ≤ a < c be integers. Two players play alternately with a pile of stones. Each player at his turn selects one move from the following two: (i) Remove k stones from the pile subject to 1 ≤ k ≤ a or c + 1 ≤ k ≤ c + a. (ii) If the number m of stones in the pile satisfies m ≡ 2b (mod 2a), add a stones to the pile. The player making the last move wins. If there is no last move, the game is a (dynamic) tie. The Generalized Sprague—Grundy function G is determined, thus giving the strategy of play for the game and its disjunctive compound. An algorithm requiring O(a²) steps for computing G is given. It turns out that G = G (a, b, c) is of a rather complicated form. The main interest of the paper is in presenting a complete strategy for a class of games with dynamic ties.     

An optimal strategy for a conflict resolution problem

Relevant to the design of multiple access protocols is the problem of finding the largest of N i.i.d. numbers X₁,…,X_N uniformly distributed over [0,1] using the minimum number of questions of the following type. We pick a set A(1) [0, 1] and ask which X_i ε A(1). Depending on the response, we pick another subset A(2) and ask which X_i ε A(2), and so on, until we identify the largest X_i. It is shown that the optimum sequence of questions must be of the type A(k) = (a(k), 1]; the best sequence {a(k)} can then be determined by dynamic programming following the work of Arrow, Pesotchinsky and Sobel.     

Generalized dilations and the stabilization of uncertain systems via measurement feedback

We study the problem of semiglobally stabilizing uncertain nonlinear system

Full-size image

, with (A,B) in Brunowski form. We prove that if p₁(z,u,t)u and p₂(z,u,t)u are of order greater than 1 and 0, respectively, with “generalized” dilation δ_l(z,u)=(l¹⁻ⁿz₁,…,l⁻¹z_n−1,z_n,lu) and uniformly with respect to t, where z_i is the ith component of z, then we can achieve semiglobal stabilization via arbitrarily bounded linear measurement feedback.     

Compact Recognizers of Episode Sequences

Given two strings X=a₁…a_n and P=b₁…b_m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n²) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑_i=1^mrocc_i·i) or O(n+∑_i=1^mrocc_i·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc_i is the number of distinct minimal substrings of X having b₁…b_i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.