Characterization of generalized convex functions by their best approximation in sign-monotone norms

Let {u₀, u₁,… u_{n − 1}} and {u₀, u₁,…, u_n} be Tchebycheff-systems of continuous functions on [a, b] and let f ε C[a, b] be generalized convex with respect to {u₀, u₁,…, u_{n − 1}}. In a series of papers ([1], [2], [3]) D. Amir and Z. Ziegler discuss some properties of elements of best approximation to f from the linear spans of {u₀, u₁,…, u_{n − 1}} and {u₀, u₁,…, u_n} in the L_p-norms, 1 p ∞, and show (under different conditions for different values of p) that these properties, when valid for all subintervals of [a, b], can characterize generalized convex functions. Their methods of proof rely on characterizations of elements of best approximation in the L_p-norms, specific for each value of p. This work extends the above results to approximation in a wider class of norms, called “sign-monotone,” [6], which can be defined by the property: ¦ f(x)¦ ¦ g(x)¦,f(x)g(x) 0, a x b, imply f g . For sign-monotone norms in general, there is neither uniqueness of an element of best approximation, nor theorems characterizing it. Nevertheless, it is possible to derive many common properties of best approximants to generalized convex functions in these norms, by means of the necessary condition proved in [6]. For {u₀, u₁,…, u_n} an Extended-Complete Tchebycheff-system and f ε C⁽ⁿ⁾[a, b] it is shown that the validity of any of these properties on all subintervals of [a, b], implies that f is generalized convex. In the special case of f monotone with respect to a positive function u₀(x), a converse theorem is proved under less restrictive assumptions.     

Approximation by Nörlund means of double Fourier series for Lipschitz functions

We study the rate of uniform approximation by Nörlund means of the rectangular partial sums of the double Fourier series of a function |(x, y) belonging to the class Lip α, 0 < α 1, on the two-dimensional torus −π < x, y π. As a special case we obtain the rate of uniform approximation by double Cesàro means.     

Characterization of an extremal sum of ridge functions

The approximation problem considered in the paper is to approximate a continuous multivariate function f(x)=f(_x1,…,_xd)$f(\mathbf{x})=f(x_1,\dots ,x_d)$ by sums of two ridge functions in the uniform norm. We give a necessary and sufficient condition for a sum of two ridge functions to be a best approximation to f(x)$f(\mathbf{x})$. This main result is next used in a special case to obtain an explicit formula for the approximation error and to construct one best approximation. The problem of well approximation by such sums is also considered.     

On best rational approximation of analytic functions

This paper contains some theorems related to the best approximation ρ_n(f;E) to a function f in the uniform metric on a compact set by rational functions of degree at most n. We obtain results characterizing the relationship between ρ_n(f;K) and ρ_n(f;E) in the case when complements of compact sets K and E are connected, K is a subset of the interior Ω of E, and f is analytic in Ω and continuous on E.     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

On superpositions of continuous functions

We show that if Φ is an arbitrary countable set of continuous functions of n variables, then there exists a continuous, and even infinitely smooth, function ψ(x₁,...,x_n) such that ψ(x ₁, ...,x _n ) ?g [? (f ₁(x ₁, ... ,f _f (x _n ))] for any function ? from Φ and arbitrary continuous functions g and f_i, depending on a single variable.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

The Rivest–Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables

A Boolean function f(x₁, …, x_n) is elusive if every decision tree evaluating f must examine all n variables in the worst case. Rivest and Vuillemin conjectured that every nontrivial monotone weakly symmetric Boolean function is elusive. In this note, we show that this conjecture is true for n=10.     

Approximations of Two-Place Functions by Finite Sums of Terms with Separable Variables

It is known that if a smooth function h in two real variables x and y belongs to the class Σ_n of all sums of the form Σⁿ_k=1ƒ_k(x) g_k(y), then its (n + 1)th order "Wronskian" det[h_xⁱy^j]ⁿ_i,j=0 is identically equal to zero. The present paper deals with the approximation problem h(x, y) Σⁿ_k=1ƒ_k(x) g_k(y) with a prescribed n, for general smooth functions h not lying in Σ_n. Two natural approximation sums T=T(h) Σ_n, S=S(h) Σ_n are introduced and the errors |h-T|, |h-S| are estimated by means of the above mentioned Wronskian of the function h. The proofs utilize the technique of ordinary linear differential equations.     

On Generalized Hermite–Fejér Interpolation of Lagrange Type on the Chebyshev Nodes

For fC[−1, 1], let H_m, n(f, x) denote the (0, 1, …,anbsp;m) Hermite–Fejér (HF) interpolation polynomial of f based on the Chebyshev nodes. That is, H_m, n(f, x) is the polynomial of least degree which interpolates f(x) and has its first m derivatives vanish at each of the zeros of the nth Chebyshev polynomial of the first kind. In this paper a precise pointwise estimate for the approximation error |H_2m, n(f, x)−f(x)| is developed, and an equiconvergence result for Lagrange and (0, 1, …, 2m) HF interpolation on the Chebyshev nodes is obtained. This equiconvergence result is then used to show that a rational interpolatory process, obtained by combining the divergent Lagrange and (0, 1, …, 2m) HF interpolation methods on the Chebyshev nodes, is convergent for all fC[−1, 1].     

On the irreducibility of sums of rational functions with separated variables

A rational function withn≥3 separated variables, i.e. a sumf ₁(X ₁)+f ₂(X ₂)+…+f _n (X _n ) with nonconstantf _i , is with exception of a special case in characteristicp always irreducible, i.e. has an irreducible numerator. This theorem was first proved by Schinzel. A different proof in characteristic 0 was given by Fried. We carry this proof to all characteristics. As an application we determine all rational functionsf with an addition formula of typef(x)+f(y)=f(h(x,y)) for some rational functionh. This work was partially supported by a grant from G.I.F. (German Israeli Foundation for Scientific Research and Development). I thank Wolfgang Ruppert and Moshe Jarden for helpful comments on a preliminary version of this paper. The paper was written during a stay at the Institute for Advanced Studies at the Hebrew University in Jerusalem. The author thanks the Institute for the warm hospitality which made the stay so pleasant.     

On the noise sensitivity of monotone functions

It is known that for all monotone functions f : {0, 1}ⁿ → {0, 1}, if x ∈ {0, 1}ⁿ is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability ? = n^?α, then P[f(x) ≠ f(y)] < cn^?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying P[f_n(x) ≠ f_n(y)] ≥ δ, where 0 < δ < 1/2, required ? ≥ c(δ)n^?α, where α = 1 ? ln 2/ln 3 = 0.36907 …, and c(δ) > 0. We improve this result by achieving for every 0 < δ < 1/2, P[f_n(x) ≠ f_n(y)] ≥ δ, with:

• ? = c(δ)n^?α for any α < 1/2, using the recursive majority function with arity k = k(α);
• ? = c(δ)n^?1/2log^tn for t = log₂ = .3257 …, using an explicit recursive majority function with increasing arities; and
• ? = c(δ)n^?1/2, nonconstructively, following a probabilistic CNF construction due to Talagrand.

We also study the problem of achieving the best dependence on δ in the case that the noise rate ? is at least a small constant; the results we obtain are tight to within logarithmic factors. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 333–350, 2003     

Precise orders of strong unicity constants for a class of rational functions

Let denote a certain class of rational functions. For each f ε , consider the polynomial of degree at most n that best approximates f in the uniform norm. The corresponding strong unicity constant is denoted by M_n(f). Then there exist positive constants α and β, not depending on n, such that an M_n(f) βn, N = 1,2,….     

A note on feebly continuous functions

A function f from to is said to be feebly continuous at a point (x,y) if there exist sequences x_nx and y_ny with lim_n→∞lim_m→∞f(x_n,y_m)=f(x,y). Dales asked if every function has a point of feeble continuity. Our aim in this short note is to show that (assuming the Continuum Hypothesis) the answer is ‘no’. Dales also asked what happens for functions taking only two values: we show that in this case the answer is ‘yes’.     

Divisibility of matrices associated with multiplicative functions

Let S={x₁,…,x_n} be a set of n distinct positive integers. For x,y∈S and y<x, we say the y is a greatest-type divisor of x in S if y∣x and it can be deduced that z=y from y∣z,z∣x,z<x and z∈S. For x∈S, let G_S(x) denote the set of all greatest-type divisors of x in S. For any arithmetic function f, let (f(x_i,x_j)) denote the n×n matrix having f evaluated at the greatest common divisor (x_i,x_j) of x_i and x_j as its i,j-entry and let (f[x_i,x_j]) denote the n×n matrix having f evaluated at the least common multiple [x_i,x_j] of x_i and x_j as its i,j-entry. In this paper, we assume that S is a gcd-closed set and . We show that if f is a multiplicative function such that (f∗μ)(d)∈Z whenever and f(a)|f(b) whenever a|b and a,b∈S and (f(x_i,x_j)) is nonsingular, then the matrix (f(x_i,x_j)) divides the matrix (f[x_i,x_j]) in the ring M_n(Z) of n×n matrices over the integers. As a consequence, we show that (f(x_i,x_j)) divides (f[x_i,x_j]) in the ring M_n(Z) if (f∗μ)(d)∈Z whenever and f is a completely multiplicative function such that (f(x_i,x_j)) is nonsingular. This confirms a conjecture of Hong raised in 2004.     

Distribution of values of arithmetic functions in residue classes

We give a criterion for weakly uniform distribution of integral multiplicative functionsf(n) of the class CS modulo N, generalizing a result of Narkiewicz (W. Narkiewicz, Acta Arithm.,12, 269–279 (1967)). We obtain an asymptotic formula for N(n<x|f(n)=a(mod N)). We consider particular cases for the functionf(n):r ₂(n) the number of integral points in the circlex ²+y ²n, and others.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Maternaticheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 121, pp. 176–186, 1983.     

A sequence of complexly computable functions

Specific Boolean functionsf _n,t(x₁,...,x_n) are described and a high lower bound of the complexity of calculations using functional elements is obtained for them. In particular, for some values of the parameter t=t(n) the functionsf _n,t are the most complex, to within a multiplicative constant, of the n-argument functions.Translated from Matematicheskie Zametki, Vol. 17, No. 6, pp. 957–966, June, 1975.     

Uniform rational approximation of functions with first derivative in the real hardy space ReH 1

The main result proved in the paper is: iff is absolutely continuous in (–, ) andf' is in the real Hardy space ReH ¹, then for everyn1, whereR _n(f) is the best uniform approximation off by rational functions of degreen. This estimate together with the corresponding inverse estimate of V. Russak [15] provides a characterization of uniform rational approximation.Communicated by Ronald A. DeVore.     

Estimating the Length of a Diagnostic Test for Some Nonrepeating Functions

For a given nonrepeating function f(x ₁, ... , x _n) that essentially depends on all its variables we estimate the length of the diagnostic test on the set of all nonrepeating functions arbitrarily dependent on the variables x ₁, ... , x _n. Previously the author has shown that the corresponding Shannon function is of order (n ²). In this article nonrepeating functions f(x ₁, ... , x _n) are constructed for which the length of the minimal test increases superlinearly but not faster than n ²/2.     

On the uniform distribution of sequences of random variables

Summary This paper deals with the almost sure uniform distribution (modulo 1) of sequences of random variables. In the case where the law of the increments X _n+h –X _n of the sequence X ₀, X ₁, does not depend on n, sufficient conditions are given to assure the uniform distribution (modulo 1) with probability one. As an illustrative example the partial sums of a sequence of independent, identically distributed variables is considered.