Mean-Value Theorems for Multiplicative Functions on Additive Arithmetic Semigroups via Halász’s Method

 We extend the mean-value theorems for multiplicative functions f on additive arithmetic semigroups, which satisfy the condition ∣f(a)∣≤1, to a wider class of multiplicative functions f for which ∣f(a)∣ is bounded in some average sense, via Halász’s method in classical probabilistic number theory. Received October 18, 2001; in final form April 11, 2002     

On Strong Uniform Distribution II

 Let ? be a class of real valued integrable functions on [0,1). We will call a strictly increasing sequence of natural numbers an sequence if for every f in ? we have

Convergence of diagonally stationary sequences in convex optimization

LetX be a real normed linear space,f, f ⁿ, n , be extended real-valued proper closed convex functions onX. A sequence {x _n} inX is called diagonally stationary for {f ⁿ} if for alln there existsx* _n f ⁿ (x _n) such that x* _{n *} 0. Such sequences arise in approximation methods for the problem of minimizingf. Some general convergence results based upon variational convergence theory and appropriate equi-well-posedness are presented.     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

This paper deals with the inversive congruential method with power of two modulusm for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that there exist parameters in the inversive congruential method such that the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude at leastm ^–1/3. The method of proof relies on a detailed analysis of certain rational exponential sums.     

Adaption allows efficient integration of functions with unknown singularities

We study numerical integration for functions f with singularities. Nonadaptive methods are inefficient in this case, and we show that the problem can be efficiently solved by adaptive quadratures at cost similar to that for functions with no singularities. Consider first a class of functions whose derivatives of order up to r are continuous and uniformly bounded for any but one singular point. We propose adaptive quadratures Q*_n, each using at most n function values, whose worst case errors are proportional to n^−r. On the other hand, the worst case error of nonadaptive methods does not converge faster than n⁻¹. These worst case results do not extend to the case of functions with two or more singularities; however, adaption shows its power even for such functions in the asymptotic setting. That is, let F^∞_r be the class of r-smooth functions with arbitrary (but finite) number of singularities. Then a generalization of Q*_n yields adaptive quadratures Q**_n such that |I(f)−Q**_n(f)|=O(n^−r) for any f ∈ F^∞_r. In addition, we show that for any sequence of nonadaptive methods there are `many' functions in F^∞_r for which the errors converge no faster than n⁻¹. Results of numerical experiments are also presented. The authors were partially supported, respectively, by the State Committee for Scientific Research of Poland under Project 1 P03A 03928 and by the National Science Foundation under Grant CCR-0095709.     

On the number of zero-sum subsequences

For a sequence S of elements from an additive abelian group G, let f(S) denote the number of subsequences of S the sum of whose terms is zero. In this paper we characterize all sequences S in G with f(S)>2^|S|-2, where |S| denotes the number of terms of S.     

Average growth-behavior and distribution properties of generalized weighted digit-block-counting functions

We introduce a generalized weighted digit-block-counting function on the nonnegative integers, which is a generalization of many digit-depending functions as, for example, the well known sum-of-digits function. A formula for the first moment of the sum-of-digits function has been given by Delange in 1972. In the first part of this paper we provide a compact formula for the first moment of the generalized weighted digit-block-counting function and show that a (weak) Delange type formula holds if the sequence of weights converges. The question, whether the converse is true as well, can only be answered partially at the moment. In the second part of this paper we study distribution properties of generalized weighted digit-block-counting sequences and their d-dimensional analogues. We give an if and only if condition under which such sequences are uniformly distributed modulo one. Roswitha Hofer, Recipient of a DOC-FFORTE-fellowship of the Austrian Academy of Sciences at the Institute of Financial Mathematics at the University of Linz (Austria). Friedrich Pillichshammer, Supported by the Austrian Science Foundation (FWF), Project S9609, that is part of the Austrian National Research Network “Analytic Combinatorics and Probabilistic Number Theory”. Dedicated to Prof. Robert F. Tichy on the occasion of his 50th birthday Authors’ address: Roswitha Hofer, Gerhard Larcher and Friedrich Pillichshammer, Institut für Finanzmathematik, Universit?t Linz, Altenbergerstra?e 69, A-4040 Linz, Austria     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

A survey of truncation error analysis for Padé and continued fraction approximants

To compute the value of a functionf(z) in the complex domain by means of a converging sequence of rational approximants {f _n(z)} of a continued fraction and/or Padé table, it is essential to have sharp estimates of the truncation error ¦f(z)–f _n(z)¦. This paper is an expository survey of constructive methods for obtaining such truncation error bounds. For most cases dealt with, {f _n(z)} is the sequence of approximants of a continued fractoin, and eachf _n(z) is a (1-point or 2-point) Padé approximant. To provide a common framework that applies to rational approximantf _n(z) that may or may not be successive approximants of a continued fraction, we introduce linear fractional approximant sequences (LFASs). Truncation error bounds are included for a large number of classes of LFASs, most of which contain representations of important functions and constants used in mathematics, statistics, engineering and the physical sciences. An extensive bibliography is given at the end of the paper.Research supported in part by the U.S. National Science Foundation under Grants INT-9113400 and DMS-9302584.     

Paths through inverse limits

In Bani?, ?repnjak, Merhar and Milutinovi? (2010) [2] the authors proved that if a sequence of graphs of surjective upper semi-continuous set-valued functions fn:X→X² converges to the graph of a continuous single-valued function f:X→X, then the sequence of corresponding inverse limits obtained from fn converges to the inverse limit obtained from f. In this paper a more general result is presented in which surjectivity of fn is not required. The result is also generalized to the case of inverse sequences with non-constant sequences of bonding maps. Finally, these new theorems are applied to inverse limits with tent maps. Among other applications, it is shown that the inverse limits appearing in the Ingram conjecture (with a point added) form an arc.     

Linear Versus Hereditary Discrepancy*

Lovász, Spencer and Vesztergombi proved that the linear discrepancy of a hypergraph H is bounded above by the hereditary discrepancy of H, and conjectured a sharper bound that involves the number of vertices in H. In this paper we give a short proof of this conjecture for hypergraphs of hereditary discrepancy 1. For hypergraphs of higher hereditary discrepancy we give some partial results and propose a sharpening of the conjecture.* A proof of the conjecture of Lovász, Spencer and Vesztergombi for hypergraphs of hereditary discrepancy 1 has also been independently obtained by B. Doerr [6]. Supported in part by NSF grant DMS-0100400. Research supported by the Technion V. P. R. Fund–M. and M. L. Bank Mathematics Research Fund and by the Fund for the Promotion of Research at the Technion.     

Une Remarque sur une Formule Sommatoire liée à la Somme des Chiffres

Let g ≥ 2 be an integer, and let s(n) be the sum of the digits of n in basis g. Let f(n) be a complex valued function defined on positive integers, such that . We propose sufficient conditions on the function f to deduce the equality . Applications are given, for instance, on the equidistribution mod 1 of the sequence (s(n))^α, where α is a positive real number.     

A free-boundary problem for the evolution <Emphasis Type="Italic">p</Emphasis>-Laplacian equation with a combustion boundary condition

We study the existence, uniqueness and regularity of solutions of the equation f _t  = Δ _p f = div (|Df| ^p-2 Df) under over-determined boundary conditions f = 0 and |Df| = 1. We show that if the initial data is concave and Lipschitz with a bounded and convex support, then the problem admits a unique solution which exists until vanishing identically. Furthermore, the free-boundary of the support of f is smooth for all positive time.     

On almost sure convergence of Cesaro averages of subsequences of vector-valued functions

A remarkable theorem proved by Komlòs [4] states that if {f_n} is a bounded sequence in L¹(R), then there exists a subsequence {f_nk} and f L¹(R) such that f_nk (as well as any further subsequence) converges Cesaro to f almost everywhere. A similar theorem due to Révész [6] states that if {f_n} is a bounded sequence in L²(R), then there is a subsequence {f_nk} and f L²(R) such that Σ_k=1^∞ a_k(f_nk − f) converges a.e. whenever Σ_k=1^∞ | a_k |² < ∞. In this paper, we generalize these two theorems to functions with values in a Hilbert space (Theorems 3.1 and 3.3).     

Mean-value theorems for multiplicative functions on Beurling’s generalized integers (I)

Halász’s general mean-value theorem for multiplicative functions on ℕ is classical in probabilistic number theory. We extend this theorem to functions f, defined on a set of generalized integers associated with a set of generalized primes in Beurling’s sense, which satisfies Halász’s conditions, in particular,Assume that the distribution function N(x) of satisfieswith γ>γ₀, where ρ₁<ρ₂<···<ρ_m are constants with ρ_m≥1 and A₁,···,A_m are real constants with A_m>0. Also, assume that the Chebyshev function ψ(x) of satisfieswith M>M₀. Then the asymptoticimplieswhere τ is a positive constant with τ≥1 and L(u) is a slowly oscillating function with |L(u)|=1.     

Mixing Properties and Central Limit Theorem for a Class of Non-Identical Piecewise Monotonic C2 — Transformations

For a sequence T⁽¹⁾, T⁽²⁾,…of piecewise monotonic C² - transformations of the unit interval I onto itself, we prove exponential ψ- mixing, an almost Markov property and other higher-order mixing properties. Furthermore, we obtain optimal rates of convergence in the central limit Theorem and large deviation relations for the sequence f_k oT(k?1)o…oT⁽¹⁾, k=1, 2, …, provided that the real-valued functions f₁, f₂,…on I are of bounded variation and the corresponding probability measure on I possesses a positive, Lipschitz-continuous Lebesgue density.     

Regularities of the Distribution of β-adic van der Corput Sequences

For Pisot numbers β with irreducible β-polynomial, we prove that the discrepancy function D(N, [0,y)) of the β-adic van der Corput sequence is bounded if and only if the β-expansion of y is finite or its tail is the same as that of the expansion of 1. If β is a Parry number, then we can show that the discrepancy function is unbounded for all intervals of length . We give explicit formulae for the discrepancy function in terms of lengths of iterates of a reverse β-substitution.