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.     

On Elliptic Extensions in the Disk

Given two arbitrary functions f ⁽⁰⁾, f ⁽¹⁾ on the boundary of the unit disk D in \({\mathbb R}^2\), it is shown that there exists a second order uniformly elliptic operator L and a function v in L ^p , with L ^p second derivatives (1?p?Lv?=?0 a.e. in D and with v?=?f ⁽⁰⁾ and \(\frac{ \partial v}{\partial n} = f^{(1)}\) on \(\partial{D}\). A similar extension property was proved in Cavazzoni (2003) for any pair of functions f ⁽⁰⁾, f ⁽¹⁾ that are analytic; a result is obtained under weaker regularity assumptions, e.g. with \(\frac{\partial f^{(0)}}{\partial \theta}\) and f ⁽¹⁾ Hölder continuous with exponent \(\eta > \frac{1}{2}\).     

The Euler obstruction of a function on a determinantal variety and on a curve

Given an analytic function germ f: (X, 0) → C on an isolated determinantal singularity or on a reduced curve, we present formulas relating the local Euler obstruction of f to the vanishing Euler characteristic of the fiber X ∩ f^-1(0) and to the Milnor number of f. Restricting ourselves to the case where X is a complete intersection, we obtain an easy way to calculate the local Euler obstruction of f as the difference between the dimension of two algebras.     

An elementary proof of the <Emphasis Type="Italic">A</Emphasis><Subscript>2</Subscript> bound

A martingale transform T, applied to an integrable locally supported function f, is pointwise dominated by a positive sparse operator applied to |f|, the choice of sparse operator being a function of T and f. As a corollary, one derives the sharp A _p bounds for martingale transforms, recently proved by Thiele-Treil-Volberg, as well as a number of new sharp weighted inequalities for martingale transforms. The (very easy) method of proof (a) only depends upon the weak-L ¹ norm of maximal truncations of martingale transforms, (b) applies in the vector valued setting, and (c) has an extension to the continuous case, giving a new elementary proof of the A ² bounds in that setting.     

Locally Adaptive Density Estimation on the Unit Sphere Using Needlets

The problem of estimating a probability density function f on the d?1-dimensional unit sphere S ^d?1 from directional data using the needlet frame is considered. It is shown that the decay of needlet coefficients supported near a point x??S ^d?1 of a function f:S ^d?1??? depends only on local H?lder continuity properties of f at?x. This is then used to show that the thresholded needlet estimator introduced in Baldi, Kerkyacharian, Marinucci, and Picard (Ann. Stat. 39, 3362?C3395, 2009) adapts to the local regularity properties of?f. Moreover, an adaptive confidence interval for f based on the thresholded needlet estimator is proposed, which is asymptotically honest over suitable classes of locally H?lderian densities.     

Inequalities of the Kolmogorov type for norms of Riesz derivatives of multivariate functions and some of their applications

We obtained new exact inequalities that estimate the L _?? -norm of the Riesz derivative D ^?? f of a function f defined on $ {\mathbb{R}^m} $ in terms of the uniform norm of the function itself and the L _s -norm of the function acted by the Laplace operator. On a class of functions f such that ||??f||s ?? 1, we solved the problem of approximation of an unbounded operator D ^?? by bounded ones and the problem of optimal recovery of the operator D ^?? on elements of this class given with known error.     

Remarks on the stochastic integral

In Karandikar-Rao [11], the quadratic variation [M, M] of a (local) martingale was obtained directly using only Doob’s maximal inequality and it was remarked that the stochastic integral can be defined using [M, M], avoiding using the predictable quadratic variation 〈M, M〉 (of a locally square integrable martingale) as is usually done. This is accomplished here- starting with the result proved in [11], we construct ∫ f dX where X is a semimartingale and f is predictable and prove dominated convergence theorem (DCT) for the stochastic integral. Indeed, we characterize the class of integrands f for this integral as the class L(X) of predictable processes f such that |f| serves as the dominating function in the DCT for the stochastic integral. This observation seems to be new.We then discuss the vector stochastic integral ∫ 〈f, dY〉 where f is ? ^d valued predictable process, Y is ? ^d valued semimartingale. This was defined by Jacod [6] starting from vector valued simple functions. Memin [13] proved that for (local) martingales M¹, … M ^d : If N ⁿ are martingales such that N _t ⁿ → N _t for every t and if ?f ⁿ such that N _t ⁿ = ∫ 〈f ⁿ , dM〉, then ?f such that N = ∫ 〈f, dM〉.Taking a cue from our characterization of L(X), we define the vector integral in terms of the scalar integral and then give a direct proof of the result due to Memin stated above.This completeness result is an important step in the proof of the Jacod-Yor [4] result on martingale representation property and uniqueness of equivalent martingale measure. This result is also known as the second fundamental theorem of asset pricing.     

On the measurability of functions with quasi-continuous and upper semi-continuous vertical sections

Let f: ?² → ? be a function with upper semicontinuous and quasi-continuous vertical sections f _x (t) = f(x, t), t, x ∈ ?. It is proved that if the horizontal sections f ^y (t) = f(t, y), y, t ∈ ?, are of Baire class α (resp. Lebesgue measurable) [resp. with the Baire property] then f is of Baire class α + 2 (resp. Lebesgue measurable and sup-measurable) [resp. has Baire property].     

Meromorphic Solutions for a Class of Differential Equations and Their Applications

In this note, we study the admissible meromorphic solutions for algebraic differential equation fⁿf' + P_n?1(f) = R(z)e^α(z), where P_n?1(f) is a differential polynomial in f of degree ≤ n ? 1 with small function coefficients, R is a non-vanishing small function of f, and α is an entire function. We show that this equation does not possess any meromorphic solution f(z) satisfying N(r, f) = S(r, f) unless P_n?1(f) ≡ 0. Using this result, we generalize a well-known result by Hayman.     

On the positive definiteness of some functions related to the Schoenberg problem

For a broad class of functions f: [0,+∞) → ?, we prove that the function f(ρ ^λ(x)) is positive definite on a nontrivial real linear space E if and only if 0 ≤ λ ≤ α(E, ρ). Here ρ is a nonnegative homogeneous function on E such that ρ(x) ? 0 and α(E, ρ) is the Schoenberg constant.     

Modified Dyadic Integral and Fractional Derivative on ℝ+

For functions from the Lebesgue space L(?₊), we introduce the modified strong dyadic integral J _α and the fractional derivative D ^(α) of order α > 0. We establish criteria for their existence for a given function f ∈ L(?₊). We find a countable set of eigenfunctions of the operators D ^(α) and J _α, α > 0. We also prove the relations D ^(α)(J _α(f)) = f and J _α(D ^(α)(f)) = f under the condition that $\smallint _{\mathbb{R}_ + } f(x)dx = 0$ . We show the unboundedness of the linear operator $J_\alpha :L_{J_{_\alpha } } \to L(\mathbb{R}_ + )$ , where L _{J α} is its natural domain of definition. A similar assertion is proved for the operator $D^{(\alpha )} :L_{D^{(\alpha )} } \to L(\mathbb{R}_ + )$ . Moreover, for a function f ∈ L(?₊) and a given point x ∈ ?₊, we introduce the modified dyadic derivative d ^(α)(f)(x) and the modified dyadic integral j _α(f)(x). We prove the relations d ^(α)(J _α(f))(x) = f(x) and j _α(D ^(α)(f)) = f(x) at each dyadic Lebesgue point of the function f.     

The absolute convergence of the Fourier-Haar series for two-dimensional functions

It is well-known that if an one-dimensional function is continuously differentiable on [0, 1], then its Fourier-Haar series converges absolutely. On the other hand, if a function of two variables has continuous partial derivatives f _x ^′ and f _y ^′ on T ², then its Fourier series does not necessarily absolutely converge with respect to a multiple Haar system (see [1]). In this paper we state sufficient conditions for the absolute convergence of the Fourier-Haar series for two-dimensional continuously differentiable functions.     

Inductive and projective limits of Banach spaces of measurable functions with order unities with respect to power parameter

We prove that a measurable function f is bounded and invertible if and only if there exist at least two equivalent norms by order unit spaces with order unities f^α and f^β with α > β > 0. We show that it is natural to understand the limit of ordered vector spaces with order unities f^α (α approaches to infinity) as a direct sum of one inductive and one projective limits. We also obtain some properties for the corresponding limit topologies.     

Real analytic expansion of spectral projections and extension of the Hecke-Bochner identity

In this article, we review the Weyl correspondence of bigraded spherical harmonics and use it to extend the Hecke-Bochner identities for the spectral projections f × φ _k ^n?1 for function f ∈ L ^p (? ⁿ ) with 1 ≤ p ≤ ∞. We prove that spheres are sets of injectivity for the twisted spherical means with real analytic weight. Then, we derive a real analytic expansion for the spectral projections f × φ _k ^n?1 for function f ∈ L ²(? ⁿ ). Using this expansion we deduce that a complex cone can be a set of injectivity for the twisted spherical means.     

Weak Compactness and Variational Characterization of the Convexity

We prove that if X is a Banach space and ${f : X \rightarrow \mathbb{R} \cup \{+\infty\}}$ is a proper function such that f ? ? attains its minimum for every ? ε X ^*, then the sublevels of f are all relatively weakly compact in X. As a consequence we show that a Banach space X where there exists a function ${f : X \rightarrow \mathbb{R}}$ such that f ? ? attains its minimum for every ? ε X ^* is reflexive. We also prove that if ${f : X \rightarrow \mathbb{R} \cup \{+\infty\}}$ is a weakly lower semicontinuous function on the Banach space X and if for every continuous linear functional ? on X the set where the function f ? ? attains its minimum is convex and non-empty then f is convex.     

Results of prescribing Q-curvature on S n

Using a flow approach, generalizing previous results from Chen and Xu [12] and Ho [20], an existence result of prescribing Q-curvature on the even-dimensional standard sphere S ⁿ as a given positive function f was obtained under suitable assumptions on the Morse index of f. In this note, we prove a more general existence result by assuming only that f is positive somewhere.     

Bounds for the number of points on curves over finite fields

Let U be a bounded open subset of ?^d, d ≥ 2 and f ∈ C(?U). The Dirichlet solution f^CU of the Dirichlet problem associated with the Laplace equation with a boundary condition f is not continuous on the closure ū of U in general if U is not regular but it is always Baire-one.Let H(U) be the space of all functions continuous on the closure ū and harmonic on U and F(H(U)) be the space of uniformly bounded absolutely convergent series of functions in H(U). We prove that f^CU can be obtained as a uniform limit of a sequence of functions in F(H(U)). Thus f^CU belongs to the subclass B_1/2 of Baire-one functions studied for example in [8]. This is not only an improvement of the result obtained in [10] but it also shows that the Dirichlet solution on the closure ū can share better properties than to be only a Baire-one function. Moreover, our proof is more elementary than that in [10].A generalization to the abstract context of simplicial function space on a metrizable compact space is provided.We conclude the paper with a brief discussion on the solvability of the abstract Dirichlet problem with a boundary condition belonging to the space of differences of bounded semicontinuous functions complementing the results obtained in [17].     

The strong <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-<Emphasis Type="Italic">greedy</Emphasis> property of the Walsh system

For any 0 < ? < 1 one can find a measurable set E ? [0, 1] with the measure |E| > 1 ? ? such that for each function f(x) ε L ¹ (0, 1) a function g(x) ε L ¹ (0, 1) exists such that it coincides with f (x) on E, its Fourier—Walsh series converges to it in the metric of L ¹ (0, 1), and all nonzero terms of the sequence of Fourier coefficients of the new function obtained by the Walsh system have the modulo decreasing order; consequently, the greedy algorithm for this function converges to it in the L ¹ (0, 1)-norm.     

Radial growth,Lipschitz and Dirichlet spaces on solutions to the non-homogenous Yukawa equation

In this paper, we investigate some properties of solutions f to the nonhomogenous Yukawa equation Δf(z) = λ(z)f(z) in the unit ball \(\mathbb{B}^n\) of ? ⁿ , where λ is a real function from \(\mathbb{B}^n\) into ?. First, we prove that a main result of Girela, Pavlovi? and Peláez (J. Analyse Math. 100 (2006), 53–81) on analytic functions can be extended to this more general setting. Then we study relationships on such solutions between the bounded mean oscillation and Lipschitz-type spaces. The obtained result generalized the corresponding result of Dyakonov (Acta Math. 178 (1997), 143–167). Finally, we discuss Dirichlet-type energy integrals on such solutions in the unit ball of ? ⁿ and give an application.