Algorithms for computing the global infimum and minimum of a polynomial function

By catching the so-called strictly critical points,this paper presents an effective algorithm for computing the global infimum of a polynomial function.For a multivariate real polynomial f ,the algorithm in this paper is able to decide whether or not the global infimum of f is finite.In the case of f having a finite infimum,the global infimum of f can be accurately coded in the Interval Representation.Another usage of our algorithm to decide whether or not the infimum of f is attained when the global infimum of f is finite.In the design of our algorithm,Wu’s well-known method plays an important role.     

计算多项式函数的全局下确界和全局最小值的有效算法

通过捕获所谓的严格临界点, 本文提出了一个计算实多项式函数的全局下确界和全局最小值的有效方法. 对于实数域R 上一个n 元多项式f, 该方法可用来判定f 在Rⁿ 上是否具有有限的全局下确界. 在f 具有有限的全局下确界的情况下, f 的下确界可严格地表示为码(h; a, b), 其中h 是一个实单元多项式, a 和b 是使得a < b 的两个有理数, 而(h; a, b) 代表h(z) 在开区间]a, b[ 中仅有的实根.此外, 当f 具有有限下确界时, 本文的方法可进一步判定f 的下确界能否达到. 在我们的算法设计中,著名的吴方法起着重要作用.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

Normal families of meromorphic functions concerning shared values

In this paper we study the problem of normal families of meromorphic functions concerning shared values and prove that a family F of meromorphic functions in a domain D is normal if for each pair of functions f and g in F, f^′−afn and g^′−agn share a value b in D where n is a positive integer and a,b are two finite constants such that n?4 and a≠0. This result is not true when n?3.     

Quasi-GCD computations

For univariate polynomials with real or complex coefficients and a given error bound ? > 0, h is called a quasi-gcd of f and g, if h is an ?-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors u, ν such that | uf + νg ? h | < ? | h | holds. Suitable “pivoting” leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound O(n² lg n(lg(1/?) + n lg n)) of “pointer time” for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.     

On the algebraic structure of Abelian integrals for a kind of perturbed cubic Hamiltonian systems

The finite generators of Abelian integral are obtained, where Γh is a family of closed ovals defined by H(x,y)=x²+y²+ax⁴+bx²y²+cy⁴=h, h∈Σ, ac(4ac−b²)≠0, Σ=(0,h₁) is the open interval on which Γh is defined, f(x,y), g(x,y) are real polynomials in x and y with degree 2n+1 (n?2). And an upper bound of the number of zeros of Abelian integral I(h) is given by its algebraic structure for a special case a>0, b=0, c=1.     

Isoperimetric type inequalities for harmonic functions

For 0<p<+∞ let hp be the harmonic Hardy space and let bp be the harmonic Bergman space of harmonic functions on the open unit disk U. Given 1?p<+∞, denote by ‖⋅bp_‖ and ‖⋅hp_‖ the norms in the spaces bp and hp, respectively. In this paper, we establish the harmonic hp-analogue of the known isoperimetric type inequality ‖fb2p_‖?‖fhp_‖, where f is an arbitrary holomorphic function in the classical Hardy space Hp. We prove that for arbitrary p>1, every function f∈hp satisfies the inequality

‖fb2p_‖?ap‖fhp_‖,     

Selection principle for pointwise bounded sequences of functions

For a number ? > 0 and a real function f on an interval [a, b], denote by N(?, f, [a, b]) the least upper bound of the set of indices n for which there is a family of disjoint intervals [a _i , b _i ], i = 1, …, n, on [a, b] such that |f(a _i ) ? f(b _i )| > ? for any i = 1, …, n (sup Ø = 0). The following theorem is proved: if {f _j } is a pointwise bounded sequence of real functions on the interval [a, b] such that n(?) ≡ lim sup _j→∞ N(?, f _j , [a, b]) < ∞ for any ? > 0, then the sequence {f _j } contains a subsequence which converges, everywhere on [a, b], to some function f such that N(?, f, [a, b]) ≤ n(?) for any ? > 0. It is proved that the main condition in this theorem related to the upper limit is necessary for any uniformly convergent sequence {f _j } and is “almost” necessary for any everywhere convergent sequence of measurable functions, and many pointwise selection principles generalizing Helly’s classical theorem are consequences of our theorem. Examples are presented which illustrate the sharpness of the theorem.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Hyperbolicity of the invariant sets for the real polynomial maps

In this paper, the conditions under which there exits a uniformly hyperbolic invariant set for the map f_a(x) = ag(x) are studied, where a is a real parameter, and g(x) is a monic real-coefficient polynomial. It is shown that for certain parameter regions, the map has a uniformly hyperbolic invariant set on which it is topologically conjugate to the one-sided subshift of finite type for A, where ∣a∣ is sufficiently large, A is an eventually positive transition matrix, and g has at least two different real zeros or only one real zero. Further, it is proved that there exists an invariant set on which the map is topologically semiconjugate to the one-sided subshift of finite type for a particular irreducible transition matrix under certain conditions, and one type of these maps is not hyperbolic on the invariant set.     

Pairings from down-sets and up-sets in distributive lattices

If D is a set of subsets of a finite set such that a?D,b ? a ? b?D, then D is called a down-set. Berge proved that any down-set D is the disjoint union of pairs {a, b} such that a ∩ b = /b/ together with the singleton {?} if |D| is odd. A proof is given of the corresponding result for finite distributive lattices, together with a number of generalizations and analogues of it; when specialized to the lattice of all subsets of a finite set, this proof is rather simpler than was Berge's.     

SOME NORMALITY CRITERIA OF MEROMORPHIC FUNCTIONS

Let F be a family of functions meromorphic in a domain D, let n ≥ 2 be a positive integer, and let a ≠ 0, b be two finite complex numbers. If, for each f ∈ F, all of whose zeros have multiplicity at least k ＋ 1, and f ＋ a（f^（k））^n≠b in D, then F is normal in D.     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

The structure of rigid functions

A function f:R→R is called vertically rigid if graph(cf) is isometric to graph(f) for all c≠0. We prove Jankovi?'s conjecture by showing that a continuous function is vertically rigid if and only if it is of the form a+bx or a+bekx (a,b,k∈R). We answer the question of Cain, Clark and Rose by showing that there exists a Borel measurable vertically rigid function which is not of the above form. We discuss the Lebesgue and Baire measurable case, consider functions bounded on some interval and functions with at least one point of continuity. We also introduce horizontally rigid functions, and show that a certain structure theorem can be proved without assuming any regularity.     

A uniqueness theorem for indefinite Sturm-Liouville operators

In this paper, we discuss the inverse problem for indefinite Sturm-Liouville operators on the finite interval [a, b]. For a fixed index n(n = 0, 1, 2, ··· ), given the weight function ω(x), we will show that the spectral sets {λ n (q, h a , h k )} +∞ k=1 and {λ-n (q, h b , h k )} +∞ k=1 for distinct h k are sufficient to determine the potential q(x) on the finite interval [a, b] and coefficients h a and h b of the boundary conditions.     

Extending a function on a graph

Let G be a graph with vertex set V, and let h be a function mapping a subset U of V into the real numbers R. If ? is a function from V to R, we define δ (?) to be the sum of ∥?(b)? ?(a)∥ over all edges {a, b} of G. A best extension of h is such a function ? with ?(x) = h(x) for X ∈ U and minimum δ (?). We show that such a best extension exists and derive an algorithm for obtaining such an extension. We also show that if instead we minimise the sum of (?(b)??(a))², there is generally a unique best extension, obtainable by solving a system of linear equations.     

Polynomial testing of the query “IS ab ≥ cd?” with application to finding a minimal cost reliability ratio spanning tree

Given integers a, b, c, d, we present a polynomial algorithm for the query “is a^b ≥ c^d?”. The result is applied to yield a polynomial algorithm for the minimal cost reliability ratio spanning tree problem.     

An even-order three-point boundary value problem on time scales

We study the even-order dynamic equation (−1)ⁿx^(Δ∇)n(t)=λh(t)f(x(t)), t∈[a,c] satisfying the boundary conditions x^(Δ∇)i(a)=0 and x^(Δ∇)i(c)=βx^(Δ∇)i(b) for 0?i?n−1. The three points a,b,c are from a time scale , where 0<β(b−a)<c−a for b∈(a,c), β>0, f is a positive function, and h is a nonnegative function that is allowed to vanish on some subintervals of [a,c] of the time scale.     

Cantor sets arising from continued radicals

If a ₁,a ₂,a ₃,… are nonnegative real numbers and $f_{j}(x) = \sqrt{a_{j}+x}$ , then lim _n→∞ f ₁°f ₂°?°f _n (0) is a continued radical with terms a ₁,a ₂,a ₃,…. The set of real numbers representable as a continued radical whose terms a _i are all from a set S={a,b} of two natural numbers is a Cantor set. We investigate the thickness, measure, and sums of such Cantor sets.