p-Adic dynamical systems of Chebyshev polynomials

We study the behaviour of the iterates of the Chebyshev polynomials of the first kind in p-adic fields. In particular, we determine in the field of complex p-adic numbers for p > 2, the periodic points of the p-th Chebyshev polynomial of the first kind. These periodic points are attractive points. We describe their basin of attraction. The classification of finite field extensions of the field of p-adic numbers ? _p , enables one to locate precisely, for any integer ν ≥ 1, the ν-periodic points of T _p : they are simple and the nonzero ones lie in the unit circle of the unramified extension of ? _p , (p > 2) of degree ν. This generalizes a result, stated by M. Zuber in his PhD thesis, giving the fixed points of T _p in the field ? _p , (p > 2). As often happens, we consider separately the case p = 2. Also, if the integer n ≥ 2 is not divisible by p, then any fixed point w of T _n is indifferent in the field of p-adic complex numbers and we give for p ≥ 3, the p-adic Siegel disc around w.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

2-Normalization of lattices

Let τ be a type of algebras. A valuation of terms of type τ is a function v assigning to each term t of type τ a value v(t) ⩾ 0. For k ⩾ 1, an identity s ≈ t of type τ is said to be k-normal (with respect to valuation v) if either s = t or both s and t have value ⩾ k. Taking k = 1 with respect to the usual depth valuation of terms gives the well-known property of normality of identities. A variety is called k-normal (with respect to the valuation v) if all its identities are k-normal. For any variety V, there is a least k-normal variety N _k (V) containing V, namely the variety determined by the set of all k-normal identities of V. The concept of k-normalization was introduced by K. Denecke and S. L. Wismath in their paper (Algebra Univers., 50, 2003, pp.107–128) and an algebraic characterization of the elements of N _k (V) in terms of the algebras in V was given in (Algebra Univers., 51, 2004, pp. 395–409). In this paper we study the algebras of the variety N ₂(V) where V is the type (2, 2) variety L of lattices and our valuation is the usual depth valuation of terms. We introduce a construction called the 3-level inflation of a lattice, and use the order-theoretic properties of lattices to show that the variety N ₂(L) is precisely the class of all 3-level inflations of lattices. We also produce a finite equational basis for the variety N ₂(L). This research was supported by Research Project MSM6198959214 of the Czech Government and by NSERC of Canada.     

On the cube problem of Las Vergnas

We prove a conjecture of Las Vergnas in dimensions d7: The matroid of the d-dimensional cube C ^d has a unique reorientation class. This extends a result of Las Vergnas, Roudneff and Salaün in dimension 4. Moreover, we determine the automorphism group G ^d of the matroid of the d-cube C ^d for arbitrary dimension d, and we discuss its relation to the Coxeter group of C ^d . We introduce matroid facets of the matroid of the d-cube in order to evaluate the order of G ^d . These matroid facets turn out to be arbitrary pairs of parallel subfacets of the cube. We show that the Euclidean automorphism group W ^d is a proper subgroup of the group G ^d of all matroid symmetries of the d-cube by describing genuine matroid symmetries for each Euclidean facet. A main theorem asserts that any one of these matroid symmetries together with the Euclidean Coxeter symmetries generate the full automorphism group G ^d . For the proof of Las Vergnas' conjecture we use essentially these symmetry results together with the fact that the reorientation class of an oriented matroid is determined by the labeled lower rank contractions of the oriented matroid. We also describe the Folkman-Lawrence representation of the vertex figure of the d-cube and a contraction of it. Finally, we apply our method of proof to show a result of Las Vergnas, Roudneff, and Salaün that the matroid of the 24-cell has a unique reorientation class, too.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

   Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

On the invertibility of the operator <Emphasis Type="Italic">d/dt</Emphasis> + <Emphasis Type="Italic">A</Emphasis> in certain functional spaces

We prove that the operator d/dt + A constructed on the basis of a sectorial operator A with spectrum in the right half-plane of ℂ is continuously invertible in the Sobolev spaces W _p ¹ (ℝ, D _α), α ≥ 0. Here, D _α is the domain of definition of the operator A ^α and the norm in D _α is the norm of the graph of A ^α. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1020–1025, August, 2007.     

Multiphasic Individual Growth Models in Random Environments

The evolution of the growth of an individual in a random environment can be described through stochastic differential equations of the form dY _t  = β(α − Y _t )dt + σdW _t , where Y _t  = h(X _t ), X _t is the size of the individual at age t, h is a strictly increasing continuously differentiable function, α = h(A), where A is the average asymptotic size, and β represents the rate of approach to maturity. The parameter σ measures the intensity of the effect of random fluctuations on growth and W _t is the standard Wiener process. We have previously applied this monophasic model, in which there is only one functional form describing the average dynamics of the complete growth curve, and studied the estimation issues. Here, we present the generalization of the above stochastic model to the multiphasic case, in which we consider that the growth coefficient β assumes different values for different phases of the animal’s life. For simplicity, we consider two phases with growth coefficients β ₁ and β ₂. Results and methods are illustrated using bovine growth data.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

The convergence on spectrum of sample covariance matrices for information-plus-noise type data

In this paper,we consider the limiting spectral distribution of the information-plusnoise type sample covariance matrices Cn =1/N (Rn + σXn) (Rn + σXn)*,under the assumption that the entries of Xn are ...     

Maximizing Voronoi Regions of a Set of Points Enclosed in a Circle with Applications to Facility Location

In this paper we introduce an optimization problem which involves maximization of the area of Voronoi regions of a set of points placed inside a circle. Such optimization goals arise in facility location problems consisting of both mobile and stationary facilities. Let ψ be a circular path through which mobile service stations are plying, and S be a set of n stationary facilities (points) inside ψ. A demand point p is served from a mobile facility plying along ψ if the distance of p from the boundary of ψ is less than that from any member in S. On the other hand, the demand point p is served from a stationary facility p _i  ∈ S if the distance of p from p _i is less than or equal to the distance of p from all other members in S and also from the boundary of ψ. The objective is to place the stationary facilities in S, inside ψ, such that the total area served by them is maximized. We consider a restricted version of this problem where the members in S are placed equidistantly from the center o of ψ. It is shown that the maximum area is obtained when the members in S lie on the vertices of a regular n-gon, with its circumcenter at o. The distance of the members in S from o and the optimum area increases with n, and at the limit approaches the radius and the area of the circle ψ, respectively. We also consider another variation of this problem where a set of n points is placed inside ψ, and the task is to locate a new point q inside ψ such that the area of the Voronoi region of q is maximized. We give an exact solution of this problem when n = 1 and a (1 − ε)-approximation algorithm for the general case.     

On the interpolation of some generalized function spaces of different anisotropy

In the paper, the interpolation properties of the spacesH _p ^s (v; ℝ _n ) of Sobolev-Liouville type and the spacesB _{p, q} ^s (μ ℝ _n ) of Nikol'skii-Besov type generated by functions of polynomial growth that are infinitely differentiable outside of the origin are studied. Interpolation formulas for the pairs {H(v _o ),H(v ₁)} and {B(μ₀),B(μ₁)} of spaces of the above types for which the anisotropies of the interpolated spaces do not depend on each other are proved. The investigated spaces, for certain specification of the generating functions, coincide with the classical (isotropic and anisotropic) Sobolev-Liouville and Nikol'skii-Besov spaces. Translated fromMatematicheskie Zametki, Vol. 62, No. 5, pp. 666–672, November, 1997. Translated by A. I. Shtern     

A type-B associahedron

The (type-A) associahedron is a polytope related to polygon dissections which arises in several mathematical subjects. We propose a B-analogue of the associahedron. Our original motivation was to extend the analogies between type-A and type-B noncrossing partitions, by exhibiting a simplicial polytope whose h-vector is given by the rank-sizes of the type-B noncrossing partition lattice, just as the h-vector of the (simplicial type-A) associahedron is given by the Narayana numbers. The desired polytope Q^B_n is constructed via stellar subdivisions of a simplex, similarly to Lee's construction of the associahedron. As in the case of the (type-A) associahedron, the faces of Q^B_n can be described in terms of dissections of a convex polygon, and the f-vector can be computed from lattice path enumeration. Properties of the simple dual $\text{Q}{}^{\mathrm{<mtext>B</mtext><mtext>1</mtext>}}{}_{\mathrm{n}}$ are also discussed and the construction of a space tessellated by $\text{Q}{}^{\mathrm{<mtext>B</mtext><mtext>1</mtext>}}{}_{\mathrm{n}}$ is given. Additional analogies and relations with type A and further questions are also discussed.     

The moduli space of curves of genus two covering elliptic curves

We consider the moduli spaceS _n of curvesC of genus 2 with the property:C has a “maximal” mapf of degreen to an elliptic curveE. Here, the term “maximal” means that the mapf∶C→E doesn't factor over an unramified cover ofE. By Torelli mapS _n is viewed as a subset of the moduli spaceA ₂ of principally polarized abelian surfaces. On the other hand the Humbert surfaceH _Δ of invariant Δ is defined as a subvariety ofA ₂(C), the set of C-valued points ofA ₂. The purpose of this paper is to releaseS _n withH _Δ.     

On Suboptimal LCS-alignments for Independent Bernoulli Sequences with Asymmetric Distributions

Let X = X ₁ ... X _n and Y = Y ₁ ... Y _n be two binary sequences with length n. A common subsequence of X and Y is any subsequence of X that at the same time is a subsequence of Y; The common subsequence with maximal length is called the longest common subsequence (LCS) of X and Y. LCS is a common tool for measuring the closeness of X and Y. In this note, we consider the case when X and Y are both i.i.d. Bernoulli sequences with the parameters ϵ and 1 − ϵ, respectively. Hence, typically the sequences consist of large and short blocks of different colors. This gives an idea to the so-called block-by-block alignment, where the short blocks in one sequence are matched to the long blocks of the same color in another sequence. Such and alignment is not necessarily a LCS, but it is computationally easy to obtain and, therefore, of practical interest. We investigate the asymptotical properties of several block-by-block type of alignments. The paper ends with the simulation study, where the of block-by-block type of alignments are compared with the LCS.     

Asymptotic Distribution of Nodes for Near-Optimal Polynomial Interpolation on Certain Curves in R 2

Let E\subset \Bbb R ^s be compact and let d _n ^E denote the dimension of the space of polynomials of degree at most n in s variables restricted to E . We introduce the notion of an asymptotic interpolation measure (AIM). Such a measure, if it exists , describes the asymptotic behavior of any scheme τ _n ={ \bf x _k,n } _k=1 ^dnE , n=1,2,\ldots , of nodes for multivariate polynomial interpolation for which the norms of the corresponding interpolation operators do not grow geometrically large with n . We demonstrate the existence of AIMs for the finite union of compact subsets of certain algebraic curves in R ² . It turns out that the theory of logarithmic potentials with external fields plays a useful role in the investigation. Furthermore, for the sets mentioned above, we give a computationally simple construction for ``good' interpolation schemes. November 9, 2000. Date revised: August 4, 2001. Date accepted: September 14, 2001.     

Hilbert series of subspace arrangements

The vanishing ideal I of a subspace arrangement V₁∪V₂∪?∪V_m⊆V is an intersection I₁∩I₂∩?∩I_m of linear ideals. We give a formula for the Hilbert polynomial of I if the subspaces meet transversally. We also give a formula for the Hilbert series of the product ideal J=I₁I₂?I_m without any assumptions about the subspace arrangement. It turns out that the Hilbert series of J is a combinatorial invariant of the subspace arrangement: it only depends on the intersection lattice and the dimension function. The graded Betti numbers of J are determined by the Hilbert series, so they are combinatorial invariants as well. We will also apply our results to generalized principal component analysis (GPCA), a tool that is useful for computer vision and image processing.     

Limitations of learning in automata-based systems

In this article, we aim to analyze the limitations of learning in automata-based systems by introducing the L⁺$L^{+}$ algorithm to replicate quasi-perfect learning, i.e., a situation in which the learner can get the correct answer to any of his queries. This extreme assumption allows the generalization of any limitations of the learning algorithm to less sophisticated learning systems. We analyze the conditions under which the L⁺$L^{+}$ infers the correct automaton and when it fails to do so. In the context of the repeated prisoners’ dilemma, we exemplify how the L⁺$L^{+}$ may fail to learn the correct automaton. We prove that a sufficient condition for the L⁺$L^{+}$ algorithm to learn the correct automaton is to use a large number of look-ahead steps. Finally, we show empirically, in the product differentiation problem, that the computational time of the L⁺$L^{+}$ algorithm is polynomial on the number of states but exponential on the number of agents.     

An extension of Hawkes theorem on the Hausdorff dimension of a Galton–Watson tree

Let ? be the genealogical tree of a supercritical multitype Galton–Watson process, and let Λ be the limit set of ?, i.e., the set of all infinite self-avoiding paths (called ends) through ? that begin at a vertex of the first generation. The limit set Λ is endowed with the metric d(ζ, ξ) = 2 ⁻ⁿ where n = n(ζ, ξ) is the index of the first generation where ζ and ξ differ. To each end ζ is associated the infinite sequence Φ(ζ) of types of the vertices of ζ. Let Ω be the space of all such sequences. For any ergodic, shift-invariant probability measure μ on Ω, define Ω_μ to be the set of all μ-generic sequences, i.e., the set of all sequences ω such that each finite sequence v occurs in ω with limiting frequency μ(Ω(v)), where Ω(v) is the set of all ω′?Ω that begin with the word v. Then the Hausdorff dimension of Λ∩Φ⁻¹ (Ω_μ) in the metric d is

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.