Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

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).     

Estimates for sums of moduli of blocks in trigonometric Fourier series

We consider the following two problems. Problem 1: what conditions on a sequence of finite subsets A _k ? ? and a sequence of functions λ _k : A _k → ? provide the existence of a number C such that any function f ∈ L ₁ satisfies the inequality ‖U _A,Λ(f)‖ _p ≤ C‖f‖₁ and what is the exact constant in this inequality? Here, \(U_{\mathcal{A},\Lambda } \left( f \right)\left( x \right) = \sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {\lambda _k \left( m \right)c_m \left( f \right)e^{imx} } } \right|}\) and c _m (f) are Fourier coefficients of the function f ∈ L ₁. Problem 2: what conditions on a sequence of finite subsets A _k ? ? guarantee that the function \(\sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {c_m \left( h \right)e^{imx} } } \right|}\) belongs to L _p for every function h of bounded variation?     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).     

An improved approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level facility location problem with soft capacities

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u _i along with an initial opening cost f _i ≥ 0, i.e., the capacity of facility i is an integer multiple of u _i incurring a cost equals to the corresponding multiple of f _i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.     

On Templeman averages and variation functions

Let S be a countable semigroup acting in a measure-preserving fashion (g ? T _g ) on a measure space (Ω, A, µ). For a finite subset A of S, let |A| denote its cardinality. Let (A _k ) _k=1 ^∞ be a sequence of subsets of S satisfying conditions related to those in the ergodic theorem for semi-group actions of A. A. Tempelman. For A-measureable functions f on the measure space (Ω, A, μ) we form for k ≥ 1 the Templeman averages \(\pi _k (f)(x) = \left| {A_k } \right|^{ - 1} \sum\nolimits_{g \in A_k } {T_g f(x)}\) and set V _q f(x) = (Σ _k≥1|π _k+1(f)(x) ? π _k (f)(x)|q)^1/q when q ∈ (1, 2]. We show that there exists C > 0 such that for all f in L ¹(Ω, A, µ) we have µ({x ∈ Ω: V _q f(x) > λ}) ≤ C(∫_Ω | f | dµ/λ). Finally, some concrete examples are constructed.     

On existence of a universal function for <Emphasis Type="Italic">L</Emphasis> <Superscript> <Emphasis Type="Italic">p</Emphasis> </Superscript>[0, 1] with <Emphasis Type="Italic">p</Emphasis>∈(0, 1)

We show that, for every number p ∈ (0, 1), there is g ∈ L¹[0, 1] (a universal function) that has monotone coefficients c_k(g) and the Fourier–Walsh series convergent to g (in the norm of L¹[0, 1]) such that, for every f ∈ L^p[0, 1], there are numbers δ_k = ±1, 0 and an increasing sequence of positive integers N_q such that the series ∑ _k=0^+∞δ_kc_k(g)W_k (with {W_k} theWalsh system) and the subsequence \(\sigma _{{N_q}}^{\left( \alpha \right)}\), α ∈ (?1, 0), of its Cesáro means converge to f in the metric of L^p[0, 1].     

Brochette percolation

We study bond percolation on the square lattice with one-dimensional inhomogeneities. Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on Z. Select vertical columns at random independently with a given positive probability. Keep (respectively remove) vertical edges in the selected columns, with probability p (respectively 1?p). All horizontal edges and vertical edges lying in unselected columns are kept (respectively removed) with probability q (respectively 1 ? q). We show that, if p > p_c(Z²) (the critical point for homogeneous Bernoulli bond percolation), then q can be taken strictly smaller than p_c(Z²) in such a way that the probability that the origin percolates is still positive.     

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 criteria of estimation of the errors of cubature formulas

The paper considers cubature formulas for calculating integrals of functions f(X), X = (x ₁, …, x _n ) which are defined on the n-dimensional unit hypercube K ⁿ = [0, 1] ⁿ and have integrable mixed derivatives of the kind \(\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)\), 0 ≤ α _j ≤ 2. We estimate the errors R[f] = \(\smallint _{K^n } \) f(X)dX ? Σ _{k = 1} ^N c _k f(X(k)) of cubature formulas (c _k > 0) as functions of the weights c _k of nodes X(k) and properties of integrable functions. The error is estimated in terms of the integrals of the derivatives of f over r-dimensional faces (r≤n) of the hypercube K ⁿ : |R(f)| ≤ \(\sum _{\alpha _j } \) G(α _j )\(\int_{K^r } {\left| {\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)} \right|} \) dX _r , where coefficients G(α _j ) are criteria which depend only on parameters c _k and X(k). We present an algorithm to calculate these criteria in the two- and n-dimensional cases. Examples are given. A particular case of the criteria is the discrepancy, and the algorithm proposed is a generalization of those used to compute the discrepancy. The results obtained can be used for optimization of cubature formulas as functions of c _k and X(k).     

Normal families of meromorphic functions and shared functions

The paper is devoted to the normal families of meromorphic functions and shared functions. Generalizing a result of Chang (2013), we prove the following theorem. Let h (≠≡ 0,∞) be a meromorphic function on a domain D and let k be a positive integer. Let F be a family of meromorphic functions on D, all of whose zeros have multiplicity at least k + 2, such that for each pair of functions f and g from F, f and g share the value 0, and f^(k) and g^(k) share the function h. If for every f ∈ F, at each common zero of f and h the multiplicities m_f for f and m_h for h satisfy m_f ≥ m_h + k + 1 for k > 1 and m_f ≥ 2m_h + 3 for k = 1, and at each common pole of f and h, the multiplicities nf for f and nh for h satisfy n_f ≥ n_h + 1, then the family F is normal on D.     

Large strings of consecutive smooth integers

In this note we improve an algorithm from a recent paper by Bauer and Bennett for computing a function of Erdös that measures the minimal gap size f(k) in the sequence of integers at least one of whose prime factors exceeds k. This allows us to compute values of f(k) for larger k and obtain new values of f(k).     

Order of magnitude of multiple Fourier coefficients of functions of bounded <Emphasis Type="Italic">p</Emphasis>-variation

For a Lebesgue integrable complex-valued function f defined over the n-dimensional torus \(\mathbb{T}^n \):= [0, 2π) ⁿ , let \(\hat f\)(k) denote the Fourier coefficient of f, where k = (k ₁, … k _n ) ∈ ? ⁿ . In this paper, defining the notion of bounded p-variation (p ≧ 1) for a function from [0, 2π] ⁿ to ? in two diffierent ways, the order of magnitude of Fourier coefficients of such functions is studied. As far as the order of magnitude is concerned, our results with p = 1 give the results of Móricz [5] and Fülöp and Móricz [3].     

Local solvability of the k-Hessian equations

We give a classification of second-order polynomial solutions for the homogeneous k-Hessian equation σ_k[u] = 0. There are only two classes of polynomial solutions: One is convex polynomial; another one must not be(k + 1)-convex, and in the second case, the k-Hessian equations are uniformly elliptic with respect to that solution. Based on this classification, we obtain the existence of C∞local solution for nonhomogeneous term f without sign assumptions.     

The Generalized <Emphasis Type="Italic">M/G/k</Emphasis> Blocking System with Heterogeneous Servers

This paper studies the equilibrium behaviour of the generalized M/G/k blocking system with heterogeneous servers. Such a service system has k servers, each with a (possibly) different service time distribution, whose customers arrive in accordance with a Poisson process. They are served, unless all the servers are occupied. In this case they leave and they do not return later (i.e. they are ‘blocked’). Whenever there are n (n = 0, 1, 2,..., k) servers occupied, each arriving customer balks with probability 1 - f _{n +1}(f _{k +1} = 0) and each server works at a rate g _n . Among other things, a generalization of the Erlang B-formula is given and also it is shown that the equilibrium departure process from the system is Poisson.     

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.$$

     

Inequalities between best polynomial approximations and some smoothness characteristics in the space <Emphasis Type="Italic">L</Emphasis> <Subscript>2</Subscript> and widths of classes of functions

We obtain exact constants in Jackson-type inequalities for smoothness characteristics Λ_k(f), k ∈ N, defined by averaging the kth-order finite differences of functions f ∈ L₂. On the basis of this, for differentiable functions in the classes L₂^r, r ∈ N, we refine the constants in Jackson-type inequalities containing the kth-order modulus of continuity ω_k. For classes of functions defined by their smoothness characteristics Λ_k(f) and majorants Φ satisfying a number of conditions, we calculate the exact values of certain n-widths.     

The logarithm of the modulus of a holomorphic function as a minorant for a subharmonic function. II. The complex plane

Let u ? ?∞be a subharmonic function in the complex plane. We establish necessary and/or sufficient conditions for the existence of a nonzero entire function f for which the modulus of the product of each of its kth derivative k = 0, 1,..., by any polynomial p is not greater than the function Ce ^u in the entire complex plane, where C is a constant depending on k and p. The results obtained significantly strengthen and develop a number of results of Lars Hörmander (1997).     

Generalized separants of differential polynomials

Let f ∈ K{y} be an element of the ring of differential polynomials in one differential variable y with one differential operator δ. For any variable y _k , the polynomial g = δ ⁿ (f) can be represented in the form g = A _k y _k + go, where go does not depend on y _k . If y _k is the leader of g, then A _k is a separant of the polynomial f. A formula for A _k is obtained for sufficiently large numbers n and k and some applications of this formula are presented.     

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).