On Vertices, focal curvatures and differential geometry of space curves

The focal curve of an immersed smooth curve γ : θ ↦ γ (θ), in Euclidean space ℝ^m+1, consists of the centres of its osculating hyperspheres. This curve may be parametrised in terms of the Frenet frame of γ (t, n₁, . . . , n_m), as C_γ (θ) = (γ +c₁n₁+ c₂n₂ + • • • + c_mn_m)(θ), where the coefficients c₁, . . . , c_m-1 are smooth functions that we call the focal curvatures of γ . We discovered a remarkable formula relating the Euclidean curvatures κ_i , i = 1, . . . ,m, of γ with its focal curvatures. We show that the focal curvatures satisfy a system of Frenet equations (not vectorial, but scalar!). We use the properties of the focal curvatures in order to give, for ℓ = 1, . . . ,m, necessary and sufficient conditions for the radius of the osculating ℓ-dimensional sphere to be critical. We also give necessary and sufficient conditions for a point of γ to be a vertex. Finally, we show explicitly the relations of the Frenet frame and the Euclidean curvatures of γ with the Frenet frame and the Euclidean curvatures of its focal curve C_γ.     

Type-B generalized triangulations and determinantal ideals

For n≥3, let Ω_n be the set of line segments between the vertices of a convex n-gon. For j≥2, a j-crossing is a set of j line segments pairwise intersecting in the relative interior of the n-gon. For k≥1, let Δ_n,k be the simplicial complex of (type-A) generalized triangulations, i.e. the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing.The complex Δ_n,k has been the central object of many papers. Here we continue this work by considering the complex of type-B generalized triangulations. For this we identify line segments in Ω_2n which can be transformed into each other by a 180^°-rotation of the 2n-gon. Let F_n be the set Ω_2n after identification, then the complex D_n,k of type-B generalized triangulations is the simplicial complex of subsets of F_n not containing any (k+1)-crossing in the above sense. For k=1, we have that D_n,1 is the simplicial complex of type-B triangulations of the 2n-gon as defined in [R. Simion, A type-B associahedron, Adv. Appl. Math. 30 (2003) 2-25] and decomposes into a join of an (n−1)-simplex and the boundary of the n-dimensional cyclohedron. We demonstrate that D_n,k is a pure, k(n−k)−1+kn dimensional complex that decomposes into a kn−1-simplex and a k(n−k)−1 dimensional homology-sphere. For k=n−2 we show that this homology-sphere is in fact the boundary of a cyclic polytope. We provide a lower and an upper bound for the number of maximal faces of D_n,k.On the algebraical side we give a term order on the monomials in the variables X_ij,1≤i,j≤n, such that the corresponding initial ideal of the determinantal ideal generated by the (k+1) times (k+1) minors of the generic n×n matrix contains the Stanley-Reisner ideal of D_n,k. We show that the minors form a Gröbner-Basis whenever k∈{1,n−2,n−1} thereby proving the equality of both ideals and the unimodality of the h-vector of the determinantal ideal in these cases. We conjecture this result to be true for all values of k<n.     

The delay of circuits whose inputs have specified arrival times

Let C be a circuit representing a straight-line program on n inputs x₁,x₂,…,x_n. If for 1?i?n an arrival timet_i∈N₀ for x_i is given, we define the delay of x_i in C as the sum of t_i and the maximum number of gates on a directed path in C starting in x_i. The delay of C is defined as the maximum delay of one of its inputs.The notion of delay is a natural generalization of the notion of depth. It is of practical interest because it corresponds exactly to the static timing analysis used throughout the industry for the analysis of the timing behaviour of a chip. We prove a lower bound on the delay and construct circuits of close-to-optimal delay for several classes of functions. We describe circuits solving the prefix problem on n inputs that are of essentially optimal delay and of size O(nlog(logn)). Finally, we relate delay to formula size.     

Distribution of Primitive A-Roots of Composite Moduli Ⅱ

Abstract We improve estimates for the distribution of primitive λ-roots of a composite modulus q yielding an asymptotic formula for the number of primitive λ-roots in any interval I of length ∣I∣ ≫ q ^1/2+∈. Similar results are obtained for the distribution of ordered pairs (x, x ⁻¹) with x a primitive λ-root, and for the number of primitive λ-roots satisfying inequalities such as |x − x ⁻¹| ≤ B. (Dedicated to Professor Wang Yuan on the occasion of his 75th birthday) *Project supported by the National Natural Science Foundation of China (No.19625102) and the 973 Project of the Ministry of Science and Technology of China.     

On the classes of hereditarily ℓp Banach spaces

Let X denote a specific space of the class of X _α,p Banach sequence spaces which were constructed by Hagler and the first named author as classes of hereditarily ℓ_p Banach spaces. We show that for p > 1 the Banach space X contains asymptotically isometric copies of ℓ_p. It is known that any member of the class is a dual space. We show that the predual of X contains isometric copies of ℓ_p where 1/p + 1/q = 1. For p = 1 it is known that the predual of the Banach space X contains asymptotically isometric copies of c ₀. Here we give a direct proof of the known result that X contains asymptotically isometric copies of ℓ₁.     

Quadratic Hermite–Padé polynomials associated with the exponential function

The asymptotic behavior of quadratic Hermite–Padé polynomials associated with the exponential function is studied for n→∞. These polynomials are defined by the relation

(*)

p_n(z)+q_n(z)e^z+r_n(z)e^2z=O(z³ⁿ⁺²) as z→0,

where O(·) denotes Landau's symbol. In the investigation analytic expressions are proved for the asymptotics of the polynomials, for the asymptotics of the remainder term in (*), and also for the arcs on which the zeros of the polynomials and of the remainder term cluster if the independent variable z is rescaled in an appropriate way. The asymptotic expressions are defined with the help of an algebraic function of third degree and its associated Riemann surface. Among other possible applications, the results form the basis for the investigation of the convergence of quadratic Hermite–Padé approximants, which will be done in a follow-up paper.     

Realizable Quadruples for Hex-polygons

There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ² with vertices in the integral lattice ℤ². Geometrically, ℤ² is the set of corners of a tiling of ℝ² by unit squares. Denote by H the set of corners of a tiling of the plane by regular hexagons of unit area and call a polygon P a Hex-polygon or an H-polygon if all vertices of P are in H. Our purpose is to study several combinatorial properties of H-polygons that are analogous to properties of lattice polygons. In particular we aim to find some relationships between the numbers b and i of points from H on the boundary and in the interior of an H-polygon P with the numbers v and c of vertices and the so-called boundary characteristic of P. We also pose three open problems dealing with convex Hex-polygons.     

The volume and foundation of star trades

An x-star trade consists of two disjoint decompositions of some simple graph H into copies of K_1,x, the graph known as the x-star. The number of vertices of H is referred to as the foundation of the trade, while the number of copies of K_1,x in each of the decompositions is called the volume of the trade. We determine all values of x, v and s for which there exists a K_1,x-trade of volume s and foundation v.     

The metric dimension of Cayley digraphs

A vertex x in a digraph D is said to resolve a pair u, v of vertices of D if the distance from u to x does not equal the distance from v to x. A set S of vertices of D is a resolving set for D if every pair of vertices of D is resolved by some vertex of S. The smallest cardinality of a resolving set for D, denoted by dim(D), is called the metric dimension for D. Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay(Δ:Γ), where Γ is the group Z_n1⊕Z_n2⊕?⊕Z_nm and Δ is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Z_n⊕Z_m) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D_n of order 2n with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the n-cube and the Cayley digraph Cay(Δ:D_n), where Δ is a minimum set of generators for D_n, are established.     

On the multi-phase M/G/1 queueing system with random feedback

In this paper we consider an M/G/1 queue with k phases of heterogeneous services and random feedback, where the arrival is Poisson and service times has general distribution. After the completion of the i-th phase, with probability θ _i the (i + 1)-th phase starts, with probability p _i the customer feedback to the tail of the queue and with probability 1 − θ _i − p _i  = q _i departs the system if service be successful, for i = 1, 2 , . . . , k. Finally in kth phase with probability p _k feedback to the tail of the queue and with probability 1 − p _k departs the system. We derive the steady-state equations, and PGF’s of the system is obtained. By using them the mean queue size at departure epoch is obtained.     

Sharp Error Terms for Return Time Statistics under Mixing Conditions

We describe the statistics of repetition times of a string of symbols in a stochastic process. Denote by τ _A the time elapsed until the process spells a finite string A and by S _A the number of consecutive repetitions of A. We prove that, if the length of the string grows unboundedly, (1) the distribution of τ _A , when the process starts with A, is well approximated by a certain mixture of the point measure at the origin and an exponential law, and (2) S _A is approximately geometrically distributed. We provide sharp error terms for each of these approximations. The errors we obtain are point-wise and also allow us to get approximations for all the moments of τ _A and S _A . To obtain (1) we assume that the process is φ-mixing, while to obtain (2) we assume the convergence of certain conditional probabilities.      

Joint Distributions of Numbers of Runs of Specified Lengths in a Sequence of Markov Dependent Multistate Trials

Let Z ₀, Z ₁,...,Z _n be a sequence of Markov dependent trials with state space Ω = {F ₁,...,F _λ, S ₁,...,S _ν}, where we regard F ₁,...,F _λ as failures and S ₁,...,S _ν as successes. In this paper, we study the joint distribution of the numbers of S _i -runs of lengths k _ij (i = 1,2,...,ν, j = 1,2,...,r _i ) based on four different enumeration schemes. We present formulae for the evaluation of the probability generating functions and the higher order moments of this distribution. In addition, when the underlying sequence is i.i.d. trials, the conditional distribution of the same run statistics, given the numbers of success and failure is investigated. We give further insights into the multivariate run-related problems arising from a sequence of the multistate trials. Besides, our results have potential applications to problems of various research areas and will come to prominence in the future. This research was partially supported by the ISM Cooperative Research Program (2004-ISM·CRP-2007).     

On the Convergence and Iterates of q-Bernstein Polynomials

The convergence properties of q-Bernstein polynomials are investigated. When q1 is fixed the generalized Bernstein polynomials _nf of f, a one parameter family of Bernstein polynomials, converge to f as n→∞ if f is a polynomial. It is proved that, if the parameter 0<q<1 is fixed, then _nf→f if and only if f is linear. The iterates of _nf are also considered. It is shown that _n^Mf converges to the linear interpolating polynomial for f at the endpoints of [0,1], for any fixed q>0, as the number of iterates M→∞. Moreover, the iterates of the Boolean sum of _nf converge to the interpolating polynomial for f at n+1 geometrically spaced nodes on [0,1].     

Periodic solutions in an array of coupled FitzHugh–Nagumo cells

We analyse the dynamics of an array of N²$N^2$ identical cells coupled in the shape of a torus. Each cell is a 2-dimensional ordinary differential equation of FitzHugh–Nagumo type and the total system is _ZN×_ZN${\mathbb{Z}}_N\times {\mathbb{Z}}_N$-symmetric. The possible patterns of oscillation, compatible with the symmetry, are described. The types of patterns that effectively arise through Hopf bifurcation are shown to depend on the signs of the coupling constants, under conditions ensuring that the equations have only one equilibrium state.     

Proximity and remoteness in triangle-free and C4-free graphs in terms of order and minimum degree

Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness $\rho (G)$ and the proximity $\pi (G)$ of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of $C_4$-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.     

Conditional expectations and operator decompositions

For aC ^*-algebraA with a conditional expectation Φ:A → A onto a subalgebraB we have the linear decompositionA=B⊕H whereH=ker(Φ). Since Φ preserves adjoints, it is also clear that a similar decomposition holds for the selfadjoint parts:A ^s =B ^s ⊕H ^s (we useV ^s ={aεV;a ^*=a} for any subspaceV of A). Apply now the exponential function to each of the three termsA ^s ,B ^s , andH ^s . The results are: the setG ⁺ of positive invertible elements ofA, the setB ⁺ of positive invertible elements ofB, and the setC={e^h;h ^*=h, Φ(h)=0}, respectively. We consider here the question of lifting the decompositionA ^s =B ^s ⊕H ^s to the exponential sets. Concretely, is every element ofG ⁺ the product of elements ofB ⁺ andC, respectively, just as any selfadjoint element ofA is the sum of selfadjoint elements ofB andH? The answer is yes in the following sense: Eacha ε G ⁺ is the positive part of a productbe of elementsb ε B ⁺ and c εC, and bothb andc are uniquely determined and depend analytically ona. This can be rephrased as follows: The map (6, c) →(bc) ⁺ is an analytic diffeomorphism fromB ⁺ x C ontoG ⁺, where for any invertiblex ε A we denote with x⁺ the positive square root ofxx ^*. This result can be expressed equivalently as: The map (b, c) →bcb is a diffeomorphism between the same spaces. Notice that combining the polar decomposition with these results we can write every invertibleg ε A asg=bcu, whereb ε B ⁺,c ε C, andu is unitary. This decomposition is unique and the factorsb, c, u depend analytically ofg. In the case of matrix algebras with Φ=trace/dimension, the factorization corresponds tog=| det(g)|cu withc > 0,det(c)=1, andu unitary. This paper extends some results proved by G. Corach and the authors in [2]. Also, Theorem 2 states that the reductive homogeneous space resulting from a conditional expectation satisfies the regularity hypothesis introduced by L. Mata-Lorenzo and L. Recht in [5], Definition 11.1. The situation considered here is the ”general context” for regularity indicated in the introduction of the last mentioned paper.     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

On two classes of permutations with number-theoretic conditions on the lengths of the cycles

Let Λ be an arbitrary set of positive integers andS _n (Λ) the set of all permutations of degreen for which the lengths of all cycles belong to the set Λ. In the paper the asymptotics of the ratio |S _n (Λ)|/n! asn→∞ is studied in the following cases: 1) Λ is the union of finitely many arithmetic progressions, 2) Λ consists of all positive integers that are not divisible by any number from a given finite set of pairwise coprime positive integers. Here |S _n (Λ)| stands for the number of elements in the finite setS _n (Λ). Translated fromMatematicheskie Zametki, Vol. 62, No. 6, pp. 881–891, December, 1997. Translated by A. I. Shtern