A basic family of iteration functions for polynomial root finding and its characterizations

Let p(x) be a polynomial of degree n?2 with coefficients in a subfield K of the complex numbers. For each natural number m?2, let L_m(x) be the m×m lower triangular matrix whose diagonal entries are p(x) and for each j=1,…,m−1, its jth subdiagonal entries are . For i=1,2, let L_m^i)(x) be the matrix obtained from L_m(x) by deleting its first i rows and its last i columns. L₁⁽¹⁾(x)≡1. Then, the function B_m(x)=x−p(x) defines a fixed-point iteration function having mth order convergence rate for simple roots of p(x). For m=2 and 3, B_m(x) coincides with Newton's and Halley's, respectively. The function B_m(x) is a member of S(m,m+n−2), where for any M?m, S(m,M) is the set of all rational iteration functions g(x) ∈ K(x) such that for all roots θ of p(x), then g(x)=θ+∑_i=m^Mγ_i(x)(θ−x)ⁱ, with γ_i(x) ∈ K(x) and well-defined at any simple root θ. Given g ∈ S(m,M), and a simple root θ of p(x), gⁱ(θ)=0, i=1, …, m−1 and the asymptotic constant of convergence of the corresponding fixed-point iteration is . For B_m(x) we obtain . If all roots of p(x) are simple, B_m(x) is the unique member of S(m,m + n − 2). By making use of the identity , we arrive at two recursive formulas for constructing iteration functions within the S(m,M) family. In particular, the family of B_m(x) can be generated using one of these formulas. Moreover, the other formula gives a simple scheme for constructing a family of iteration functions credited to Euler as well as Schröder, whose mth order member belongs to S(m,mn), m>2. The iteration functions within S(m,M) can be extended to any arbitrary smooth function f, with the uniform replacement of p^(j) with f^(j) in g as well as in γ_m(θ).     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

On Invariants and Strict Systems of Irreducible Polynomials Over Henselian Valued Fields

Let g(x) be a monic irreducible defectless polynomial over a henselian valued field (K, v), i.e., K(θ) is a defectless extension of (K, v) for any root θ of g(x). It is known that a complete distinguished chain for θ with respect to (K, v) gives rise to several invariants associated with g(x). Recently Ron Brown studied certain invariants of defectless polynomials by introducing strict systems of polynomial extensions. In this article, the authors establish a one-to-one correspondence between strict systems of polynomial extensions and conjugacy classes of complete distinguished chains. This correspondence leads to a simple interpretation of various results proved for strict systems. The authors give new characterizations of an invariant γ _g introduced by Brown.     

A New Result on Alspach's Problem

Let G be a simple graph. Let g(x) and f(x) be integer-valued functions defined on V(G) with g(x)≥2 and f(x)≥5 for all x∈V(G). It is proved that if G is an (mg+m−1, mf−m+1)-graph and H is a subgraph of G with m edges, then there exists a (g,f)-factorization of G orthogonal to H. Received: January 19, 1996 Revised: November 11, 1996     

Seshadri constants on surfaces of general type

We study Seshadri constants of the canonical bundle on minimal surfaces of general type. First, we prove that if the Seshadri constant ε(K _X , x) is between 0 and 1, then it is of the form (m − 1)/m for some integer m ≥ 2. Secondly, we study values of ε(K _X , x) for a very general point x and show that small values of the Seshadri constant are accounted for by the geometry of X.     

Hypersurfaces containing flat subspaces

Lek k be an infinite field and suppose m.i. and n are positive integers such that t m We study the subset of k[x ₁,x ₂, … x_m ] which consists of 0 and the homogeneous members t of f of k[x ₁,x ₂, … x_m ] of fixed degree n such that there exists homogeneous F ₁, F ₂, … F_t in k[x ₁,x ₂, … x_m ] of degree one and homogenous g ₁ g ₂, …g_t , in k[x ₁,x ₂, … x_m ] such that f(x) = F ₁(x)g ₁(x) + F ₂(x)g ₂(x) + … + F _t (x)g _t (x) for each x in k ^m. In case k is algebrarcally closed we are able to prove that this set is an algebraic variety. Consequently. if k is also of characteristic 0 then we are able to prove that certain collections of symmetric k-valued multilinear functions are algebraic varieties.     

On an optimization problem of Bellman

This paper considers a problem proposed by Bellman in 1970: given a continuous kernel K(x, y) defined on I × I, find a pair of continuous functions f and g such that f(x) + g(y) ? K(x, y) on I × I and ∝_I (f + g) is minimum. The notion of basic decomposition of K is defined, and it is shown that whenever K(x, y) or K(x, a + b ? y), I = [a, b], admits a basic decomposition, Bellman's problem has a unique differentiable solution, provided K is differentiable. Explicit formulas for such solutions are given. More generally, there are kernels which admit basic decompositions on subintervals which can be “pasted together” to define a unique piecewise differentiable solution.     

The numerical solution of fredholm integral equations with rapidly varying kernels

Approximating a solution to the Fredholm integral equation ø(x)=α(x) + ∫ ^b_aK(x, y)ø(y) dy by the Nyström method involves some numerical quadrature for approximating the integral, producing a linear system satisfied by approximate function values of ø. This paper discusses the use of generalized product-interpolatory formulas which model ø as one mth-degree polynomial on each subinterval and model K as a (possibly large) sequence of nth-degree polynomials. In cases where K is varying much more rapidly than ø this allows for ø to be sampled much less often than K. Since K is modeled as a sequence of polynomials, its frequent sampling does not require a prohibitive increase in the degree of the interpolating polynomials. Coefficient formulas and examples are given for the (m,n) cases (1,1), (1,2), (2,1) and (2,2).     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

Tight bounds for rational sums of squares over totally real fields

Let K be a totally real Galois number field. Hillar proved that if f ∈ ?[x ₁, ..., x _n ] is a sum of m squares in K[x ₁, ..., x _n ], then f is a sum of N(m) squares in ?[x ₁, ..., x _n ], where N(m) ≤ 2^[K:?]+1 · $ \left( {_2^{[K:\mathbb{Q}] + 1} } \right) $ · 4m. We show in fact that N(m) ≤ m + 4 $ \left\lceil {\tfrac{m} {4}} \right\rceil $ ([K: ?] ? 1), our proof being constructive too. Moreover, we give some examples where this bound is sharp, for instance in the case of quadratic extensions. We also extend our results to the setting of non-commutative polynomials over ?.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

The conformal plate buckling equation

The linear equation Δ²u = 1 for the infinitesimal buckling under uniform unit load of a thin elastic plate over ?² has the particularly interesting nonlinear generalization Δ_g²u = 1, where Δ_g = e^?2u Δ is the Laplace‐Beltrami operator for the metric g = e^2ug₀, with g₀ the standard Euclidean metric on ?². This conformal elliptic PDE of fourth order is equivalent to the nonlinear system of elliptic PDEs of second order Δu(x)+K_g(x) exp(2u(x)) = 0 and Δ K_g(x) + exp(2u(x)) = 0, with x ∈ ?², describing a conformally flat surface with a Gauss curvature function K_g that is generated self‐consistently through the metric's conformal factor. We study this conformal plate buckling equation under the hypotheses of finite integral curvature ∫ K_g exp(2u)dx = κ, finite area ∫ exp(2u)dx = α, and the mild compactness condition K₊ ∈ L¹(B₁(y)), uniformly w.r.t. y ∈ ?². We show that asymptotically for |x|→∞ all solutions behave like u(x) = ?(κ/2π)ln |x| + C + o(1) and K(x) = ?(α/2π) ln|x| + C + o(1), with κ ∈ (2π, 4π) and . We also show that for each κ ∈ (2π, 4π) there exists a K^* and a radially symmetric solution pair u, K, satisfying K(u) = κ and maxK = K^*, which is unique modulo translation of the origin, and scaling of x coupled with a translation of u. © 2001 John Wiley & Sons, Inc.     

On the well-definedness of the order of an ordinary differential equation

It is proved that if the differential equations y ^{( n )}=f(x, y, y′, …, y ^{( n ?1 )}) and y ^{( m )}=g(x, y, y′, …, y ^{( n ?1 )}) have the same particular solutions in a suitable region where f and g are continuous real-valued functions with continuous partial derivatives (alternatively, continuous functions satisfying the classical Lipschitz condition), then n?=?m and the functions f and g are equal. This note could find classroom use in a course on differential equations as enrichment material for the unit on the existence and uniqueness theorems for solutions of initial value problems.     

On the Cyclic Homology of an Algebra Associated with a Cyclic Quiver and a Monic Polynomial

In this article, we compute the Hochschild homology group of A = KΓ/(f(X ^s )), where KΓ is the path algebra of the cyclic quiver Γ with s vertices and s arrows over a commutative ring K, f(x) is a monic polynomial over K, and X is the sum of all arrows in KΓ. Moreover, we compute the cyclic homology group of A in the case f(x) = (x ? a) ^m , where a ∈ K, so that we can determine the cyclic homology of A in general when K is an algebraically closed field.     

Coxeter group actions on <Subscript>4</Subscript><Emphasis Type="Italic">F</Emphasis><Subscript>3</Subscript>(1) hypergeometric series

In this paper we investigate a certain linear combination K([(x)\vec])=K(a;b,c,d;e,f,g)K(\vec{x})=K(a;b,c,d;e,f,g) of two Saalschutzian hypergeometric series of type ₄ F ₃(1). We first show that K([(x)\vec])K(\vec{x}) is invariant under the action of a certain matrix group G _K , isomorphic to the symmetric group S ₆, acting on the affine hyperplane V={(a,b,c,d,e,f,g)∈ℂ⁷:e+f+g−a−b−c−d=1}. We further develop an algebra of three-term relations for K(a;b,c,d;e,f,g). We show that, for any three elements μ ₁,μ ₂,μ ₃ of a certain matrix group M _K , isomorphic to the Coxeter group W(D ₆) (of order 23040) and containing the above group G _K , there is a relation among K(m₁[(x)\vec])K(\mu_{1}\vec{x}), K(m₂[(x)\vec])K(\mu_{2}\vec{x}), and K(m₃[(x)\vec])K(\mu_{3}\vec{x}), provided that no two of the μ _j ’s are in the same right coset of G _K in M _K . The coefficients in these three-term relations are seen to be rational combinations of gamma and sine functions in a,b,c,d,e,f,g.     

Efficient Filon-type methods for $$\int_a^bf(x)\,{\rm e}^{{\rm i}\omega g(x)}\,{\rm d}x$$

Based on the transformation y = g(x), some new efficient Filon-type methods for integration of highly oscillatory function ò_a^bf(x) e^iwg(x) dx\int_a^bf(x)\,{\rm e}^{{\rm i}\omega g(x)}\,{\rm d}x with an irregular oscillator are presented. One is a moment-free Filon-type method for the case that g(x) has no stationary points in [a,b]. The others are based on the Filon-type method or the asymptotic method together with Filon-type method for the case that g(x) has stationary points. The effectiveness and accuracy are tested by numerical examples.     

Birational composition of quadratic forms over a local field

Let f(X) and g(Y) be nondegenerate quadratic forms of dimensions m and n, respectively, over K, char K ≠ 2. The problem of birational composition of f(X) and g(Y) is considered: When is the product f(X) · g(Y) birationally equivalent over K to a quadratic form h(Z) over K of dimension m + n? The solution of the birational composition problem for anisotropic quadratic forms over K in the case of m = n = 2 is given. The main result of the paper is the complete solution of the birational composition problem for forms f(X) and g(Y) over a local field P, char P ≠ 2.     

Schanuel's Conjecture and Algebraic Roots of Exponential Polynomials

In this article, I will prove that assuming Schanuel's conjecture, an exponential polynomial with algebraic coefficients can have only finitely many algebraic roots. Furthermore, this proof demonstrates that there are no unexpected algebraic roots of any such exponential polynomial. This implies a special case of Shapiro's conjecture: if p(x) and q(x) are two exponential polynomials with algebraic coefficients, each involving only one iteration of the exponential map, and they have common factors only of the form exp (g) for some exponential polynomial g, then p and q have only finitely many common zeros.     

Convergence of the Dirichlet solutions of the very fast diffusion equation

For any −1<m<0, positive functions f, g and u₀≥0, we prove that under some mild conditions on f, g and u₀ as R→∞ the solution u^R of the Dirichlet problem u_t=(u^m/m)_xx in (−R,R)×(0,∞), u(R,t)=(f(t)|m|R)^1/m, u(−R,t)=(g(t)|m|R)^1/m for all t>0, u(x,0)=u₀(x) in (−R,R), converges uniformly on every compact subset of R×(0,T) to the solution of the equation u_t=(u^m/m)_xx in R×(0,T), u(x,0)=u₀(x) in R, which satisfies some mass loss formula on (0,T) where T is the maximal time such that the solution u is positive. We also prove that the solution constructed is equal to the solution constructed in Hui (2007) [15] using approximation by solutions of the corresponding Neumann problem in bounded cylindrical domains.