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.     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

On the complexity of the gradient of a rational function

The Baur-Strassen method implies L(?f) ? 4L(f), where L(f) is the complexity of computing a rational function f by arithmetic circuits, and ?f is the gradient of f. We show that L(? f) ? 3L(f) + n, where n is the number of variables in f. In addition, the depth of a circuit for the gradient is estimated.     

Holomorphic injective extensions of functions in <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">K</Emphasis>) and algebra generators

We present necessary and sufficient conditions on planar compacta K and continuous functions f on K in order that f generate the algebras P(K), R(K), A(K) or C(K). We also unveil quite surprisingly simple examples of non-polynomial convex compacta K ? C and f ∈ P(K) with the property that f ∈ P(K) is a homeomorphism of K onto its image, but for which f ^?1 ? P(f(K)). As a consequence, such functions do not admit injective holomorphic extensions to the interior of the polynomial convex hull \(\widehat K\). On the other hand, it is shown that the restriction f*|_G of the Gelfand-transform f* of an injective function f ∈ P(K) is injective on every regular, bounded complementary component G of K. A necessary and sufficient condition in terms of the behaviour of f on the outer boundary of K is given in order that f admit a holomorphic injective extension to \(\widehat K\). We also include some results on the existence of continuous logarithms on punctured compacta containing the origin in their boundary.     

Removable singularities of solutions of semi-elliptic equations

Let P(D) be a quasihomogeneous semi-elliptic linear differential operator with constant coefficients in ? ⁿ . We prove a metric criterion for the removability of singular sets of solutions of the equation P(D)f = 0 in function classes defined by solutions of this equation with the use of local approximations in mean.     

Sobolev-type integral representations for functions defined on Carnot groups

We obtain some integral representations of the form f(x) = P(f) + K(?f) on the Carnot groups, where P(f) is a polynomial and K is an integral operator with a specific singularity. These representations are employed to prove the weak Poincaré inequality.     

Quasisymmetric geometry of the Julia sets of McMullen maps

We study the quasisymmetric geometry of the Julia sets of McMullen maps f_λ(z) = z^m + λ/z^?, where λ ∈ ? {0} and ? and m are positive integers satisfying 1/?+1/m < 1. If the free critical points of f_λ are escaped to the infinity, we prove that the Julia set J_λ of f_λ is quasisymmetrically equivalent to either a standard Cantor set, a standard Cantor set of circles or a round Sierpiński carpet (which is also standard in some sense). If the free critical points are not escaped, we give a suffcient condition on λ such that J_λ is a Sierpiński carpet and prove that most of them are quasisymmetrically equivalent to some round carpets. In particular, there exist infinitely renormalizable rational maps whose Julia sets are quasisymmetrically equivalent to the round carpets.     

Allowable Interval Sequences and Separating Convex Sets in the Plane

In 2005, Goodman and Pollack introduced the concept of an allowable interval sequence, a combinatorial object which encodes properties of a family of pairwise disjoint convex sets in the plane. They, Dhandapani, and Holmsen used this concept to address Tverberg’s (1,k)-separation problem: How many pairwise disjoint compact convex sets in the plane are required to guarantee that one can be separated by a line from k others? (Denote this number by f _k .) A new proof was provided that f ₂=5, a result originally obtained by Tverberg himself, and the application of allowable interval sequences to the case of general k was left as an open problem. Hope and Katchalski, using other methods, proved in 1990 that 3k?1≤f _k ≤12(k?1). In this paper, we apply the method of allowable interval sequences to give an upper bound on f _k of under 7.2(k?1), shrinking the range given by Hope and Katchalski by more than half. For a family of translates we obtain a tighter upper bound of approximately 5.8(k?1).     

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.     

Representation and Approximation of Positivity Preservers

We consider a closed set S?? ⁿ and a linear operator

$\Phi \colon \mathbb{R}[X_1,\ldots,X_n]\rightarrow \mathbb{R}[X_1,\ldots,X_n]$

that preserves nonnegative polynomials, in the following sense: if f≥0 on S, then Φ(f)≥0 on S as well. We show that each such operator is given by integration with respect to a measure taking nonnegative functions as its values. This can be seen as a generalization of Haviland’s Theorem, which concerns linear functionals on ?[X ₁,…,X _n ]. For compact sets S we use the result to show that any nonnegativity preserving operator is a pointwise limit of very simple nonnegativity preservers with finite dimensional range.

     

Multivariate discriminant and iterated resultant

In this paper,we study the relationship between iterated resultant and multivariate discriminant.We show that,for generic form f(x_n) with even degree d,if the polynomial is squarefreed after each iteration,the multivariate discriminant △(f) is a factor of the squarefreed iterated resultant.In fact,we find a factor Hp(f,[x_1,...,x_n]) of the squarefreed iterated resultant,and prove that the multivariate discriminant △(f) is a factor of Hp(f,[x_1,...,x_n]).Moreover,we conjecture that Hp(f,[x_1,...,x_n]) = △(f) holds for generic form/,and show that it is true for generic trivariate form f(x,y,z).     

Integral representations and the generalized Poincaré inequality on Carnot groups

We give some integral representations of the form f(x) = P(f)+K(?f) on two-step Carnot groups, where P(f) is a polynomial and K is an integral operator with a specific singularity. We then obtain the weak Poincaré inequality and coercive estimates as well as the generalized Poincaré inequality on the general Carnot groups.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

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.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

Some relations among multiplicative and <Emphasis Type="Italic">q</Emphasis>-additive functions

We give all solutions of the equation f(n) = g(n) + h(n) for every n ∈ ?, where f is a completely multiplicative, g is a 2-additive, and h is a 3-additive function. We also determine all completely multiplicative functions f and all q-additive functions g for which f(n) = g ²(n) for every n ∈ ?.     

On some arithmetic properties of Mahler functions

Mahler functions are power series f(x) with complex coefficients for which there exist a natural number n and an integer ? ≥ 2 such that f(x), f(x^?),..., \(f({x^{{\ell ^{n - 1}}}}),f({x^{{\ell ^n}}})\) are linearly dependent over ?(x). The study of the transcendence of their values at algebraic points was initiated by Mahler around the’ 30s and then developed by many authors. This paper is concerned with some arithmetic aspects of these functions. In particular, if f(x) satisfies f(x) = p(x)f(x^?) with p(x) a polynomial with integer coefficients, we show how the behaviour of f(x) mirrors on the polynomial p(x). We also prove some general results on Mahler functions in analogy with G-functions and E-functions.     

Behavior of the Fourier–Walsh coefficients of a corrected function

We prove that, given a sequence {ak}_k=1^∞ with a_k ↓ 0 and {ak}_k=1^∞ ? l₂, reals 0 < ε < 1 and p ∈ [1, 2], and f ∈ L^p(0, 1), we can find f ∈ L^p(0, 1) with mes{f ≠ f < ε whose nonzero Fourier–Walsh coefficients c_k(f) are such that |c_k(f)| = a_k for k ∈ spec(f).     

When a smooth self-map of a semi-simple Lie group can realize the least number of periodic points

There are two algebraic lower bounds of the number of n-periodic points of a self-map f : M → M of a compact smooth manifold of dimension at least 3: NF_n(f) = min{#Fix(g~n); g ～ f; g continuous} and NJD_n(f) = min{#Fix(g~n); g ～ f; g smooth}. In general, NJD_n(f) may be much greater than NF_n(f). We show that for a self-map of a semi-simple Lie group, inducing the identity fundamental group homomorphism,the equality NF_n(f) = NJD_n(f) holds for all n ? all eigenvalues of a quotient cohomology homomorphism induced by f have moduli 1.