A Necessary and Sufficient Proximity Condition for Smoothness Equivalence of Nonlinear Subdivision Schemes

In the recent literature on subdivision methods for approximation of manifold-valued data, a certain “proximity condition” comparing a nonlinear subdivision scheme to a linear subdivision scheme has proved to be a key analytic tool for analyzing regularity properties of the scheme. This proximity condition is now well known to be a sufficient condition for the nonlinear scheme to inherit the regularity of the corresponding linear scheme (this is called smoothness equivalence). Necessity, however, has remained an open problem. This paper introduces a smooth compatibility condition together with a new proximity condition (the differential proximity condition). The smooth compatibility condition makes precise the relation between nonlinear and linear subdivision schemes. It is shown that under the smooth compatibility condition, the differential proximity condition is both necessary and sufficient for smoothness equivalence. It is shown that the failure of the proximity condition corresponds to the presence of resonance terms in a certain discrete dynamical system derived from the nonlinear scheme. Such resonance terms are then shown to slow down the convergence rate relative to the convergence rate of the corresponding linear scheme. Finally, a super-convergence property of nonlinear subdivision schemes is used to conclude that the slowed decay causes a breakdown of smoothness. The proof of sufficiency relies on certain properties of the Taylor expansion of nonlinear subdivision schemes, which, in addition, explain why the differential proximity condition implies the proximity conditions that appear in previous work.     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.     

(0, 2) Pál-type interpolation on a circle in the complex plane involving Möbius transforms

We study the regularity of certain (0,?2) Pál-type interpolation problems involving the Möbius transforms of the zeros of z ²ⁿ ?ρ ²ⁿ to the circle ∣z∣?=?ρ′.     

Polynomial dynamical systems and the Korteweg—de Vries equation

We explicitly construct polynomial vector fields L_k, k = 0, 1, 2, 3, 4, 6, on the complex linear space C⁶ with coordinates X = (x₂, x₃, x₄) and Z = (z₄, z₅, z₆). The fields L_k are linearly independent outside their discriminant variety Δ ? C⁶ and are tangent to this variety. We describe a polynomial Lie algebra of the fields L_k and the structure of the polynomial ring C[X,Z] as a graded module with two generators x₂ and z₄ over this algebra. The fields L₁ and L₃ commute. Any polynomial P(X,Z) ∈ C[X,Z] determines a hyperelliptic function P(X,Z)(u₁, u₃) of genus 2, where u₁ and u₃ are the coordinates of trajectories of the fields L₁ and L₃. The function 2x₂(u₁, u₃) is a two-zone solution of the Korteweg–de Vries hierarchy, and ?z₄(u₁, u₃)/?u₁ = ?x₂(u₁, u₃)/?u₃.     

<Emphasis Type="Italic">C</Emphasis><Superscript>∞</Superscript> regularity of solutions of the Levi equation in<Emphasis Type="Italic">R</Emphasis><Superscript><Emphasis Type="Italic">2n+1</Emphasis></Superscript>

We study the regularity of the solutions of the Levi equation in ?²ⁿ⁺¹. It is a second order quasilinear equation whose characteristic matrix is positive semidefinite and has vanishing determinant at every point and for every functionu∈C ². We show that the operator associated to the equation can be represented as a sum of squares of non linear vector fields. Then, by using a freezing method, we prove theC ^∞ regularity of the solutions.     

Composition limits and separating examples for some boolean function complexity measures

Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*(f) ≤ C(f) = O(bs(f)²). We provide an infinite family of examples for which C(f) grows quadratically in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was \(C(f) = C*(f)^{\log _{4,5} 5}\). We also give a family of examples for which C*(f)= Ω (bs(f)^3/2).These examples are obtained by composing boolean functions in various ways. Here the composition fog of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are submultiplicative (where measure m is submultiplicative if m(fog) ≤ m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, m ^lim(f) to be the limit as k grows of m(f ^(k))^1/k , where f ^(k) is the iterated composition of f with itself k-times. For any function f we show that bs ^lim(f) = (C*)^lim(f) and characterize s ^lim(f); (C*)^lim(f), and C ^lim(f) in terms of the largest eigenvalue of a certain set of 2×2 matrices associated with f.     

How to make a linear network code (strongly) secure

A linear network code is called k-secure if it is secure even if an adversary eavesdrops at most k edges. In this paper, we show an efficient deterministic construction algorithm of a linear transformation T that transforms an (insecure) linear network code to a k-secure one for any k, and extend this algorithm to strong k-security for any k . Our algorithms run in polynomial time if k is a constant, and these time complexities are explicitly presented. We also present a concrete size of \(|\mathsf{F}|\) for strong k-security, where \(\mathsf{F}\) is the underling finite field.     

On almost good triples of vertices in edge regular graphs

Consider a connected edge regular graph Γ with parameters (v, k, λ) and put b ₁ = k?λ?1. A triple (u, w, z) of vertices is called (almost) good whenever d(u, w) = d(u, z) = 2 and µ(u, w)+µ(u, z) ≤ 2k ? 4b ₁ + 3 (and µ(u, w) + µ(u, z) = 2k ? 4b ₁ + 4). If k = 3b ₁ + γ with γ ≥ ?2, a triple (u, w, z) is almost good, and Δ = [u] ∩ [w] ∩ [z] then: either |Δ| ≤ 2; or Δ is a 3-clique and Γ is a Clebsch graph; or Δ is a 3-clique, k = 16, b ₁ = 6, and v = 31; or Δ is a 4-clique and Γ is a Schläfli graph.     

The Bergman kernel: Explicit formulas,deflation, Lu Qi-Keng problem and Jacobi polynomials

We investigate the Bergman kernel function for the intersection of two complex ellipsoids {(z,w ₁,w ₂) ∈ C ⁿ⁺²: |z ₁|²+...+|z _n |²+|w ₁| ^q < 1, |z ₁|²+...+|z _n |²+|w ₂| ^r < 1}. We also compute the kernel function for {(z ₁,w ₁,w ₂) ∈ C³: |z ₁|^2/n + |w ₁| ^q < 1, |z ₁|^2/n + |w ₂| ^r < 1} and show deflation type identity between these two domains. Moreover in the case that q = r = 2 we express the Bergman kernel in terms of the Jacobi polynomials. The explicit formulas of the Bergman kernel function for these domains enables us to investigate whether the Bergman kernel has zeros or not. This kind of problem is called a Lu Qi-Keng problem.     

Congruent elliptic curves with non-trivial Shafarevich-Tate groups: Distribution part

Given a large positive number x and a positive integer k, we denote by Qk(x) the set of congruent elliptic curves E(n): y2= z3- n2 z with positive square-free integers n x congruent to one modulo eight,having k prime factors and each prime factor congruent to one modulo four. We obtain the asymptotic formula for the number of congruent elliptic curves E(n)∈ Qk(x) with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)2. We also get a lower bound for the number of E(n)∈ Qk(x)with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)4. The key ingredient of the proof of these results is an independence property of residue symbols. This property roughly says that the number of positive square-free integers n x with k prime factors and residue symbols(quadratic and quartic) among its prime factors being given compatible values does not depend on the actual values.     

Value sharing problems for differential and difference polynomials of meromorphic functions in a non-Archimedean field

In this paper we discuss the uniqueness problem for differential and difference polynomials of the form (f ^nm (z)f ^nd (qz + c))^(k) for meromorphic functions in a non-Archimedean field.     

Metric extension operators,vertex sparsifiers and Lipschitz extendability

We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k/ log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log²k/ log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators.     

Ck-regularity for the $$\bar \partial $$ -equation with a support condition

Let D be a C ^d q-convex intersection, d ≥ 2, 0 ≤ q ≤ n ? 1, in a complex manifold X of complex dimension n, n ≥ 2, and let E be a holomorphic vector bundle of rank N over X. In this paper, C ^k -estimates, k = 2, 3,...,∞, for solutions to the \(\bar \partial \)-equation with small loss of smoothness are obtained for E-valued (0, s)-forms on D when n ? q ≤ s ≤ n. In addition, we solve the \(\bar \partial \)-equation with a support condition in C ^k -spaces. More precisely, we prove that for a \(\bar \partial \)-closed form f in C _0,q ^k (X D,E), 1 ≤ q ≤ n ? 2, n ≥ 3, with compact support and for ε with 0 < ε < 1 there exists a form u in C _0,q?1 ^k?ε (X D,E) with compact support such that \(\bar \partial u = f\) in \(X\backslash \bar D\). Applications are given for a separation theorem of Andreotti-Vesentini type in C ^k -setting and for the solvability of the \(\bar \partial \)-equation for currents.     

On nonregular ideals and <Emphasis Type="Italic">z</Emphasis>°-ideals in <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">X</Emphasis>)

The spaces X in which every prime z°-ideal of C(X) is either minimal or maximal are characterized. By this characterization, it turns out that for a large class of topological spaces X, such as metric spaces, basically disconnected spaces and one-point compactifications of discrete spaces, every prime z°-ideal in C(X) is either minimal or maximal. We will also answer the following questions: When is every nonregular prime ideal in C(X) a z°-ideal? When is every nonregular (prime) z-ideal in C(X) a z°-ideal? For instance, we show that every nonregular prime ideal of C(X) is a z°-ideal if and only if X is a ?-space (a space in which the boundary of any zeroset is contained in a zeroset with empty interior).     

Hermite subdivision on manifolds via parallel transport

We propose a new adaption of linear Hermite subdivision schemes to the manifold setting. Our construction is intrinsic, as it is based solely on geodesics and on the parallel transport operator of the manifold. The resulting nonlinear Hermite subdivision schemes are analyzed with respect to convergence and C ¹ smoothness. Similar to previous work on manifold-valued subdivision, this analysis is carried out by proving that a so-called proximity condition is fulfilled. This condition allows to conclude convergence and smoothness properties of the manifold-valued scheme from its linear counterpart, provided that the input data are dense enough. Therefore the main part of this paper is concerned with showing that our nonlinear Hermite scheme is “close enough”, i.e., in proximity, to the linear scheme it is derived from.     

On the completeness of the system of root vectors of the Sturm-Liouville operator with general boundary conditions

We study general boundary value problems with nondegenerate characteristic determinant Δ(λ) for the Sturm-Liouville equation on the interval [0, 1]. Necessary and sufficient conditions for the completeness of root vectors are obtained in terms of the potential. In particular, it is shown that if Δ(λ) ≠ const, q(·) ∈ C ^k [0, 1] for some k ? 0, and q ^(k)(0) ≠ (?1) ^k q ^(k)(1), then the system of root vectors is complete and minimal in L ^p [0, 1] for p ∈ [1,∞).     

On <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-estimates of derivatives of univalent rational functions

We study the growth of the quantity ∫_T|R′(z)|dm(z) for rational functions R of degree n which are bounded and univalent in the unit disk and prove that this quantity can grow like n ^γ , γ > 0, as n → ∞. Some applications of this result to problems of regularity of boundaries of Nevanlinna domains are considered. We also discuss a related result of Dolzhenko, which applies to general (non-univalent) rational functions.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

The Folded (2<Emphasis Type="Italic">D</Emphasis> + 1)-cube and Its Uniform Posets

Let Γ denote the folded (2D + 1)-cube with vertex set X and diameter D ≥ 3. Fix x ∈ X. We first define a partial order ≤ on X as follows. For y, z ∈ X let y ≤ z whenever ?(x, y) + ?(y, z) = ?(x, z). Let R (resp. L) denote the raising matrix (resp. lowering matrix) of Γ. Next we show that there exists a certain linear dependency among RL², LRL,L²R and L for each given Q-polynomial structure of Γ. Finally, we determine whether the above linear dependency structure gives this poset a uniform structure or strongly uniform structure.     

Spectral (isotropic) manifolds and their dimension

A set of n × n symmetric matrices whose ordered vector of eigenvalues belongs to a fixed set in ?ⁿ is called spectral or isotropic. In this paper, we establish that every locally symmetric C^k submanifoldMof ?ⁿ gives rise to a C^k spectral manifold for k ∈ {2, 3, …,∞,ω}. An explicit formula for the dimension of the spectral manifold in terms of the dimension and the intrinsic properties of M is derived. This work builds upon the results of Sylvester and ?ilhavý and uses characteristic properties of locally symmetric submanifolds established in recent works by the authors.