Asymptotics of the probability of values of random Boolean expressions

The random Boolean expressions are considered that are obtained by the random and independent substitution with the probabilities p and 1 ? p of the constantly one function and constantly zero function for variables of repetition-free formulas over a given basis. The probability is studied that the expressions are equal to one. It is shown that, for each finite basis and p ? (0, 1), this probability tends to some finite limit P ₁(p) as the length of an expression grows. Explicit representation of the probability function P ₁(p) is found for all finite bases, the analytic properties of this function are studied, and its behavior is investigated in dependence on the properties of the basis.     

Extremal functions as divisors for kernels of Toeplitz operators

In this paper, an extremal function of a Banach space of analytic functions in the unit disk (not all functions vanishing at 0) is a function solving the extremal problem for functions f of norm 1. We study extremal functions of kernels of Toeplitz operators on Hardy spaces H^p, 1<p<∞. Such kernels are special cases of so-called nearly invariant subspaces with respect to the backward shift, for which Hitt proved that when p=2, extremal functions act as isometric divisors. We show that the extremal function is still a contractive divisor when p<2 and an expansive divisor when p>2 (modulo p-dependent multiplicative constants). We give examples showing that the extremal function may fail to be a contractive divisor when p>2 and also fail to be an expansive divisor when p<2. We discuss to what extent these results characterize the Toeplitz operators via invariant subspaces for the backward shift.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

Convergence of greedy algorithm in Walsh system in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>

Convergence of the greedy algorithm in Walsh system in L _p , p > 1 is studied. It is proved that there exists a function in L _p , 1 < p < 2, with greedy algorithm not converging in measure to that function. A continuous function with divergent in L _p , p > 2, greedy algorithm is constructed and sufficient conditions for convergence of the greedy algorithm in L _p , p > 1 are given.     

Narrow and ℓ2-strictly singular operators from L p

In the first part of the paper we prove that for 2 < p, r < ∞ every operator T: L _p → ? _r is narrow. This completes the list of sequence and function Lebesgue spaces X with the property that every operator T : L _p → X is narrow. Next, using similar methods we prove that every ?₂-strictly singular operator from L _p , 1 < p < ∞, to any Banach space with an unconditional basis, is narrow, which partially answers a question of Plichko and Popov posed in 1990. A theorem of H. P. Rosenthal asserts that if an operator T from L ₁[0, 1] to itself satisfies the assumption that for each measurable set A ? [0, 1] the restriction \(T{|_{{L_1}(A)}}\) is not an isomorphic embedding, then T is narrow. (Here L ₁(A) = {x ∈ L ₁ : supp x ? A}.) Inspired by this result, in the last part of the paper, we find a sufficient condition, of a different flavor than being ?₂-strictly singular, for operators from L _p [0, 1] to itself, 1 < p < 2, to be narrow. We define a notion of a “gentle” growth of a function and we prove that for 1 < p < 2 every operator T from L _p to itself which, for every A ? [0, 1], sends a function of “gentle” growth supported on A to a function of arbitrarily small norm is narrow.     

Representation of ap-harmonic function near a critical point in the plane

A representation theorem is given for ap-harmonic function φ(1<p<∞) in the plane, near a zeroz _o of grad φ. The proof uses “stream functions” and the hodograph transformation. The stream function of ap-harmonic function isp′-harmonic, where \(\frac{1}{p} + \frac{1}{{p'}} = 1\) . In principle, all properties of φ nearz _o can be found from the representation. Some consequences are derived here, e.g. the optimal Hölder continuity of grad φ.     

Application of wavelet bases in linear and nonlinear approximation to functions from Besov spaces

Linear and nonlinear approximations to functions from Besov spaces B _{p, q} ^σ ([0, 1]), σ > 0, 1 ≤ p, q ≤ ∞ in a wavelet basis are considered. It is shown that an optimal linear approximation by a D-dimensional subspace of basis wavelet functions has an error of order D ^{-min(σ, σ + 1/2 ? 1/p)} for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). An original scheme is proposed for optimal nonlinear approximation. It is shown how a D-dimensional subspace of basis wavelet functions is to be chosen depending on the approximated function so that the error is on the order of D ^?σ for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). The nonlinear approximation scheme proposed does not require any a priori information on the approximated function.     

Maximally singular Sobolev functions

It is known that for any Sobolev function in the space Wm,p(RN), p?1, mp?N, where m is a nonnegative integer, the set of its singular points has Hausdorff dimension at most N−mp. We show that for p>1 this bound can be achieved. This is done by constructing a maximally singular Sobolev function in Wm,p(RN), that is, such that Hausdorff's dimension of its singular set is equal to N−mp. An analogous result holds also for Bessel potential spaces Lα,p(RN), provided αp<N, α>0, and p>1. The existence of maximally singular Sobolev functions has been announced in [Chaos Solitons Fractals 21 (2004), p. 1287].     

A higher order p-adic class number formula

We generalize a formula of Leopoldt which relates the p-adic regulator modulo p of a real abelian extension of ? with the value of the relative Dedekind zeta function at s = 2 ? p. We use this generalization to give an alternative proof of the non-vanishing modulo p of this relative zeta function at the point s = 1 under a mild condition.     

A remark on the transformation formula of theta functions associated to positive definite quadratic forms

Let L be a positive Z-lattice with level N = cd, (c, d) = 1. Then the Fourier expansion at cusp $\text{1}\text{d}$ of the theta function associated to L is a theta function associated to L₁, where a lattice L₁ is defined by Z_pL₁ = Z_pL for $\text{p?c}$, Z_pL₁ = the dual of Z_pL for p | c.     

Uniform approximation of continuous functions by probability functions of Boolean bases

Random Boolean expressions obtained by random and independent substitution of the constants 1, 0 with probabilities p, 1 ? p, respectively, into random non-iterated formulas over a given basis are considered. The limit of the probability of appearance of expressions with the value 1 under unrestricted growth of the complexity of expressions, which is called the probability function, is considered. It is shown that for an arbitrary continuous function f(p) mapping the segment [0, 1] into itself there exists a sequence of bases whose probability functions uniformly approximate the function f(p) on the segment [0, 1].     

Cohen-Host type idempotent theorems for representations on Banach spaces and applications to Figà-Talamanca-Herz algebras

Let G be a locally compact group, and let R(G) denote the ring of subsets of G generated by the left cosets of open subsets of G. The Cohen-Host idempotent theorem asserts that a set lies in R(G) if and only if its indicator function is a coefficient function of a unitary representation of G on some Hilbert space. We prove related results for representations of G on certain Banach spaces. We apply our Cohen-Host type theorems to the study of the Figà-Talamanca-Herz algebras Ap(G) with p∈(1,∞). For arbitrary G, we characterize those closed ideals of Ap(G) that have an approximate identity bounded by 1 in terms of their hulls. Furthermore, we characterize those G such that Ap(G) is 1-amenable for some—and, equivalently, for all—p∈(1,∞): these are precisely the abelian groups.     

Extensions of a theorem of Cauchy-Liouville

We deal with the equations Δpu+f(u)=0 and Δpu+(p−1)g(u)p|∇u|+f(u)=0 in RN, where g(t) is a continuous function in (0,∞), p>1 and f(t) is a smooth function for t>0. Under appropriate conditions on g and f we show that the corresponding equation cannot have nontrivial non-negative entire solutions.     

A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length

A Boolean function f: {?1, +1} ⁿ → {?1, +1} is called the sign function of an integer-valued polynomial p(x) if f(x) = sgn(p(x)) for all x ∈ {?1, +1} ⁿ . In this case, the polynomial p(x) is called a perceptron for the Boolean function f. The weight of a perceptron is the sum of absolute values of the coefficients of p. We prove that, for a given function, a small change in the degree of a perceptron can strongly affect the value of the required weight. More precisely, for each d = 1, 2, ..., n ? 1, we explicitly construct a function f: {?1, +1} ⁿ → {?1, +1} that requires a weight of the form exp{Θ(n)} when it is represented by a degree d perceptron, and that can be represented by a degree d + 1 perceptron with weight equal to only O(n ²). The lower bound exp{Θ(n)} for the degree d also holds for the size of the depth 2 Boolean circuit with a majority function at the top and arbitrary gates of input degree d at the bottom. This gap in the weight values is exponentially larger than those that have been previously found. A similar result is proved for the perceptron length, i.e., for the number of monomials contained in it.     

Extremal problems related to maximal dyadic-like operators

We obtain sharp estimates for the localized distribution function of the dyadic maximal function Md?, when ? belongs to Lp,∞. Using this we obtain sharp estimates for the quasi-norm of Md? in Lp,∞ given the localized L¹-norm and certain weak Lp-conditions.     

Strong Convergence Theorems for Two Parameter Vilenkin-Fourier Series

As main result we prove that certain means of the partial sums of two-parameter Vilenkin-Fourier series are uniformly bounded operators from H ^P to L ^p (0 < p ≦ 1). The Hardy space H ^p (0 < p ≦ 1) will be defined by means of a diagonal maximal function. As a consequence we obtain a so-called strong convergence theorem for the Vilenkin-Fourier partial sums. Some dual inequalities are also verified for BMO spaces.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

Near invariance and kernels of Toeplitz operators

This paper makes a systematic study of kernels of Toeplitz operators on scalar and vector-valued H _p spaces (for 1 < p < ∞). The property of near invariance of a kernel for the backward shift is analysed and shown to hold in increased generality. In the scalar case, and in some vectorial cases, the existence of a minimal kernel containing a given function is established, and a symbol for a corresponding Toeplitz operator is determined; thus, for rational symbols, its dimension can be easily calculated. It is shown that every Toeplitz kernel in H _p is the minimal kernel for some function lying in it.     

A family of new smoothing functions and?a?nonmonotone smoothing Newton method for?the?nonlinear complementarity problems

In this paper, based on a p-norm with p being any fixed real number in the interval (1,+??), we introduce a family of new smoothing functions, which include the smoothing symmetric perturbed Fischer function as a special case. We also show that the functions have several favorable properties. Based on the new smoothing functions, we propose a nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. The proposed algorithm only need to solve one linear system of equations. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Numerical experiments indicate that the method associated with a smaller p, for example p=1.1, usually has better numerical performance than the smoothing symmetric perturbed Fischer function, which exactly corresponds to p=2.