Convexity Preserving Interpolatory Subdivision Schemes

We construct local subdivision schemes that interpolate functional univariate data and that preserve convexity. The resulting limit function of these schemes is continuous and convex for arbitrary convex data. Moreover this class of schemes is restricted to a subdivision scheme that generates a limit function that is convex and continuously differentiable for strictly convex data. The approximation order of this scheme is four. Some generalizations, such as tension control and piecewise convexity preservation, are briefly discussed. November 29, 1996. Date revised: May 28, 1997.     

Functions, Measures, and Equipartitioning Convex k-Fans

A k-fan in the plane is a point x∈?² and k halflines starting from x. There are k angular sectors σ ₁,…,σ _k between consecutive halflines. The k-fan is convex if every sector is convex. A (nice) probability measure μ is equipartitioned by the k-fan if μ(σ _i )=1/k for every sector. One of our results: Given a nice probability measure μ and a continuous function f defined on sectors, there is a convex 5-fan equipartitioning μ with f(σ ₁)=f(σ ₂)=f(σ ₃).     

Shape-preserving interpolation by splines using vector subdivision

We give a local convexity preserving interpolation scheme using parametricC ² cubic splines with uniform knots produced by a vector subdivision scheme which simultaneously provides the function and its first and second order derivatives. This is also adapted to give a scheme which is both local convexity and local monotonicity preserving when the data values are strictly increasing in thex-direction.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Single Basepoint Subdivision Schemes for Manifold-valued Data: Time-Symmetry Without Space-Symmetry

This paper establishes smoothness results for a class of nonlinear subdivision schemes, known as the single basepoint manifold-valued subdivision schemes, which shows up in the construction of wavelet-like transform for manifold-valued data. This class includes the (single basepoint) Log–Exp subdivision scheme as a special case. In these schemes, the exponential map is replaced by a so-called retraction map f from the tangent bundle of a manifold to the manifold. It is known that any choice of retraction map yields a C ² scheme, provided the underlying linear scheme is C ² (this is called “C ² equivalence”). But when the underlying linear scheme is C ³, Navayazdani and Yu have shown that to guarantee C ³ equivalence, a certain tensor P _f associated to f must vanish. They also show that P _f vanishes when the underlying manifold is a symmetric space and f is the exponential map. Their analysis is based on certain “C ^k  proximity conditions” which are known to be sufficient for C ^k  equivalence. In the present paper, a geometric interpretation of the tensor P _f is given. Associated to the retraction map f is a torsion-free affine connection, which in turn defines an exponential map. The condition P _f =0 is shown to be equivalent to the condition that f agrees with the exponential map of the connection up to the third order. In particular, when f is the exponential map of a connection, one recovers the original connection and P _f vanishes. It then follows that the condition P _f =0 is satisfied by a wider class of manifolds than was previously known. Under the additional assumption that the subdivision rule satisfies a time-symmetry, it is shown that the vanishing of P _f implies that the C ⁴ proximity conditions hold, thus guaranteeing C ⁴ equivalence. Finally, the analysis in the paper shows that for k≥5, the C ^k  proximity conditions imply vanishing curvature. This suggests that vanishing curvature of the connection associated to f is likely to be a necessary condition for C ^k equivalence for k≥5.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Uniform approximation by some Hermite interpolating splines

In this paper some upper bound for the error ∥ s-f ∥_∞ is given, where f ε C¹[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(x_i) = s(x_i), f′(rmx_i) = s′(x_i), s^(j) (x_i) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots x_i are such that a = x₀ < x₁ < … < x_n = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C¹[a, b] by convex HSI is also given.     

A class of nonlinear four-point subdivision schemes

We consider four-point subdivision schemes of the form $$ (Sf)_{2i} = f_i,\qquad (Sf)_{2i+1} = \frac{f_i+f_{i+1}}{2} - \frac{1}{{8}}M\!\left(\strut \Delta^2f_{i-1}, \Delta^2f_i\right) $$ with any M that is originally defined as a positive-valued function for positive arguments and is extended to the whole of ?² by setting $M(x,y):=- M(\left|x\right|,\left|y\right|)$ if x?<?0, y?<?0 and M(x, y)?:?=?0 if xy????0. For these schemes, we study analytic properties, such as convexity preservation, convergence, smoothness of the limit function, stability and approximation order, in terms of simple and easily verifiable conditions on M. Fourth-order approximation on intervals of strict convexity is also investigated. All the results known for the most frequently used schemes, the PPH scheme and the power-p schemes, are included as special cases or improved, and extended to more general situations. The various statements are illustrated by two examples and tested by numerial experiments.     

Singular (k,n − k) boundary value problems between conjugate and right focal

For 1 ⩽k⩽n − 1 and 0 ⩽q⩽k − 1, solutions are obtained for the boundary value problem, (−1)^n−k = f(x,y), y⁽ⁱ⁾=0, 0⩽i⩽k − 1, and y⁽ⁱ⁾ = 0, q⩽j⩽n − k + q − 1, where f(x,y) is singular at y = 0. An application is made of a fixed point theorem for operators that are decreasing with respect to a cone.     

Additively decomposed quasiconvex functions

In a recently published paper with the same title, Debreu and Koopmans have studied conditions which imply the quasiconvexity of the function $$f(x) = \mathop \sum \limits_{i = 1}^n f_i (x_i ),x_i \in X_i ,$$ wherex = (x ₁,x ₂,?,x _n ) and, fori = 1, 2,?, n,X ₁ is a finite-dimensional open convex set andf _i a real-valued nonconstant function onX ₁ These conditions involve the convexity indices of functionsf _i, a concept introduced in the Debreu and Koopmans paper. First, we give a new definition of the convexity index equivalent to that of Debreu and Koopmans. Then, by means of this definition, we can simplify the proofs given by Debreu and Koopmans and extend some of their results.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

Normal Forms for Nonautonomous Differential Equations

We extend Henry Poincarés normal form theory for autonomous differential equations x=f(x) to nonautonomous differential equations x=f(t, x). Poincarés nonresonance condition λ_j−∑ⁿ_i=1 ?_iλ_i≠0 for eigenvalues is generalized to the new nonresonance condition λ_j∩∑ⁿ_i=1 ?_iλ_i=∅ for spectral intervals.     

Monochromatic Vs multicolored paths

Letl andk be positive integers, and letX={0,1,...,l ^k?1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx ₀<x ₁<...<x _l ofX with δ(x ₀,x ₁)=δ(x ₁,x ₂)=...=δ(x _l?1,x _l), or else there exist elementsy ₀<y ₁<...<y _k ofX with δ(y _i?1,y _i) ∈ δ(y _j?1,y _j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)^2k . The general question remains open.     

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A weighted geometric regularity from order restricted statistical inference

In Euclideank-space, the cone of vectors x = (x ₁,x ₂,...,x _k ) satisfyingx ₁ ≤x ₂ ≤ ... ≤x _k and $\sum\nolimits_{j = 1}^k {x_j } = 0$ is generated by the vectorsv _j = (j ?k, ...,j ?k,j, ...,j) havingj ?k’s in its firstj coordinates andj’s for the remainingk ?j coordinates, for 1 ≤j <k. In this equal weights case, the average angle between v _i and v _j over all pairs (i, j) with 1 ≤i <j <k is known to be 60°. This paper generalizes the problem by considering arbitrary weights with permutations.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

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.     

A note on the stability of Jordan triple higher ring derivations

In the present paper, we establish the stability and the superstability of a functional inequality corresponding to the functional equation fn（xyx） = ∑i＋j＋k=n fi（x）fj （y）fk（x）. In addition, we take account of the problem of Jacobson radical ranges for such functional inequality.     

Polynomial Cunningham chains

A sequence of prime numbers p₁,p₂,p₃,…, such that pi=2pi−1+? for all i, is called a Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the smallest positive integer such that 2pk+? is composite, then we say the chain has length k. It is conjectured that there are infinitely many Cunningham chains of length k for every positive integer k. A sequence of polynomials f₁(x),f₂(x),… in Z[x], such that f₁(x) has positive leading coefficient, each fi(x) is irreducible in Q[x] and fi(x)=xfi−1(x)+? for all i, is defined to be a polynomial Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the least positive integer such that fk+1(x) is reducible in Q[x], then we say the chain has length k. In this article, for polynomial Cunningham chains of both kinds, we prove that there are infinitely many chains of length k and, unlike the situation in the integers, that there are infinitely many chains of infinite length, by explicitly giving infinitely many polynomials f₁(x), such that fk+1(x) is the only term in the sequence that is reducible.