An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial $p\left( z \right) = \sum\nolimits_{i = 0}^n {p_i x^i } $ within the error bound $2^{ - u} \sum\nolimits_{i = 0}^n {\left| {p_i } \right|} $ . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

The Law of Iterated Logarithm of Rescaled Range Statistics for AR（1） Model

Let {Xn,n ≥ 0} be an AR（1） process. Let Q（n） be the rescaled range statistic, or the R/S statistic for {Xn} which is given by （max1≤k≤n（∑j=1^k（Xj - ^-Xn）） - min 1≤k≤n（∑j=1^k（ Xj - ^Xn ））） /（n ^-1∑j=1^n（Xj -^-Xn）^2）^1/2 where ^-Xn = n^-1 ∑j=1^nXj. In this paper we show a law of iterated logarithm for rescaled range statistics Q（n） for AR（1） model.     

Integration and Lipschitz functions

The aim of the paper is to prove that every f ∈ L ¹([0,1]) is of the form f = , where j _n,k is the characteristic function of the interval [k- 1 / 2 ⁿ , k / 2 ⁿ ) and Σ _n=0^∞Σ _k=1²ⁿ |a _n,k | is arbitrarily close to ||f|| (Theorem 2). It is also shown that if μ is any probabilistic Borel measure on [0,1], then for any ɛ > 0 there exists a sequence (b _n,k ) _n≧0 ^k=1,...,2n of real numbers such that and for each Lipschitz function g: [0,1] → ℝ (Theorem 3).      

Fundamental Solution of the Anisotropic Porous Medium Equation

We establish the existence of fundamental solutions for the anisotropic porous medium equation, ut = ∑n i=1（u^mi）xixi in R^n × （O,∞）, where m1,m2,..., and mn, are positive constants satisfying min1≤i≤n{mi}≤ 1, ∑i^n=1 mi 〉 n - 2, and max1≤i≤n{mi} ≤1/n（2 ＋ ∑i^n=1 mi）.     

A general law of moment convergence rates for uniform empirical process

Let {X _n ; n ≥ 1} be a sequence of independent and identically distributed U[0,1]-distributed random variables. Define the uniform empirical process $F_n (t) = n^{ - \tfrac{1} {2}} \sum\nolimits_{i = 1}^n {(I_{\{ X_i \leqslant t\} } - t),0} \leqslant t \leqslant 1,\left\| {F_n } \right\| = \sup _{0 \leqslant t \leqslant 1} \left| {F_n (t)} \right| $F_n (t) = n^{ - \tfrac{1} {2}} \sum\nolimits_{i = 1}^n {(I_{\{ X_i \leqslant t\} } - t),0} \leqslant t \leqslant 1,\left\| {F_n } \right\| = \sup _{0 \leqslant t \leqslant 1} \left| {F_n (t)} \right| . In this paper, the exact convergence rates of a general law of weighted infinite series of E {‖F _n ‖ − ɛg ^s (n)}₊ are obtained.     

Two Inequalities for Convex Functions

Let a ₀ < a ₁ < ··· < a _n be positive integers with sums $ {\sum\nolimits_{i = 0}^n {\varepsilon _{i} a_{i} {\left( {\varepsilon _{i} = 0,1} \right)}} } Let a ₀ < a ₁ < ··· < a _n be positive integers with sums distinct. P. Erd?s conjectured that The best known result along this line is that of Chen: Let f be any given convex decreasing function on [A, B] with α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n being real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , Then In this paper, we obtain two generalizations of the above result; each is of special interest in itself. We prove: Theorem 1 Let f and g be two given non-negative convex decreasing functions on [A, B], and α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n , α' ₀, α' ₁, ... , α' _n , β' ₀ , β' ₁ , ... , β' _n be real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , α' ₀ ≤ α' ₁ ≤ ··· ≤ α' _n , Then Theorem 2 Let f be any given convex decreasing function on [A, B] with k ₀, k ₁, ... , k _n being nonnegative real numbers and α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n being real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , Then      

Some remarks on Vinogradov's mean value theorem and Tarry's problem

LetW(k, 2) denote the, least numbers for which the system of equations has a solution with . We show that for largek one hasW(k, 2)1/2k ²(logk+loglogk+O(1)), and moreover that whenK is large, one hasW(k, 2)1/2k(k+1)+1 for at least one valuek in the interval [K, K ^3/4+]. We show also that the leasts for which the expected asymptotic formula holds for the number of solutions of the above system of equations, inside a box, satisfiessk ²(logk+O(loglogk).Research supported in part by NSF grant DMS-9303505, an Alfred P. Sloan Research Fellowship, and a Fellowship from the David and Lucile Packard Foundation.     

On the rate of convergence of a regular martingale related to a branching random walk

Let M _n , n = 1, 2, ..., be a supercritical branching random walk in which the number of direct descendants of an individual may be infinite with positive probability. Assume that the standard martingale W _n related to M _n is regular and W is a limit random variable. Let a(x) be a nonnegative function regularly varying at infinity with index greater than −1. We present sufficient conditions for the almost-sure convergence of the series . We also establish criteria for the finiteness of EW ln⁺ Wa(ln⁺ W) and E ln⁺|Z _∞|a(ln⁺|Z _∞|), where and (M _n , Q _n ) are independent identically distributed random vectors not necessarily related to M _n . __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 3, pp. 326–342, March, 2006.     

Asymptotic behavior of the irrational factor

We study the irrational factor function I(n) introduced by Atanassov and defined by , where is the prime factorization of n. We show that the sequence {G(n)/n} _n≧1, where G(n) = Π _ν=1 ⁿ I(ν)^1/n , is convergent; this answers a question of Panaitopol. We also establish asymptotic formulas for averages of the function I(n). Research of the third author is supported in part by NSF grant number DMS-0456615.     

On the sum of the first <Emphasis Type="Italic">n</Emphasis> primes being a square

Let p _n be the nth prime. In this note, we show that the set of n such that is a square is of asymptotic density zero. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 301–306, July–September, 2007.     

Fourier and Hermite series estimates of regression functions

Summary In the paper we estimate a regressionm(x)=E {Y|X=x} from a sequence of independent observations (X ₁,Y ₁),…, (X _n, Y_n) of a pair (X, Y) of random variables. We examine an estimate of a type , whereN depends onn andϕ _N is Dirichlet kernel and the kernel associated with the hermite series. Assuming, that E|Y|<∞ and |Y|≦γ≦∞, we give condition for to converge tom(x) at almost allx, provided thatX has a density. if the regression hass derivatives, then converges tom(x) as rapidly asO(nC^{−(2s−1)/4s}) in probability andO(n ^{−(2s−1)/4s} logn) almost completely.     

Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors

The authors present an algorithm which is a modification of the Nguyen-Stehle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) , where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O(log² A) algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n! · 3 ⁿ (log A) ^O(1) algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n! · (log A) ^O(1) by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.     

A stability test for real polynomials

Summary By the argument principle the number of zeros inside of the unit circle of a real polynomial , can be estimated by the variation of the argument ofp _n (exp(it)) ift varies from 0 to . This variation has its maximal value n iff then distinct zeros of are separated by then–1 distinct zeros of . Now from Sturm sequence techniques in connection with special properties of the Chebyshev polynomials there results a very simple stability test.Dedicated to Professor Dr. Wilhelm Niethammer on his sixtieth birthday (December 2, 1993)     

The asymptotic distributions of sums of record values for distributions with lognormal-type tails

Let X1,X2,... be a sequence of i.i.d. random variables and let X(1),X(2),... be the associatedrecord value sequence. We focus on the asymptotic distributions of sums of records, Tn=∑nk=1X(k), forX1 ∈ LN(γ). In this case, we find that 2 is a strange point for parameter γ. When γ＞ 2, Tn is asymptoticallynormal, while for 2 ＞γ＞ 1, we prove that Tn cannot converge in distribution to any non-degenerate lawthrough common centralizing and normalizing and log Tn is asymptotically normal.     

Positive Solution of Multi-Point Boundary Value Problems for the One-Dimensional p-Laplacian with Singularities

In this paper, we obtain positive solution to the following multi-point singular boundary value problem with p-Laplacian operator,{（ φp（u＇））＇＋q（t）f（t,u,u＇）=0,0〈t〈1,u（0）=∑i=1^nαiu（ξi）,u＇（1）=∑i=1^nβiu＇（ξi）,whereφp（s）=｜s｜^p-2s,p≥2;ξi∈（0,1）（i=1,2,…,n）,0≤αi,βi〈1（i=1,2,…n）,0≤∑i=1^nαi,∑i=1^nβi〈1,and q（t） may be singular at t=0,1,f（t,u,u＇）may be singular at u＇=0     

On the strong law of large numbers and additive functions

Let f(n) be a strongly additive complex-valued arithmetic function. Under mild conditions on f, we prove the following weighted strong law of large numbers: if X,X ₁,X ₂, … is any sequence of integrable i.i.d. random variables, then

Vive la différence III

We show that, consistently, there is an ultrafilter on ω such that if N _n^ℓ = (P _n^ℓ ∪ Q _n^ℓ, P _n^ℓ, Q _n^ℓ, R _n^ℓ) (for ℓ = 1, 2, n < ω), P _n^ℓ ∪ Q _n^ℓ ⊆ ω, and are models of the canonical theory t ^ind of the strong independence property, then every isomorphism from onto is a product isomorphism. The first version of this work done in 93; First typed: May 1993. This research was partially supported by the United States-Israel Binational Science Foundation. Publication 509     

On a Composition Preserving Inequalities between Polynomials

The Schur-Szegö composition of two polynomials \(f\left( z \right) = \sum\nolimits_{j = 0}^n {{A_j}{z^j}} \) and \(g\left( z \right) = \sum\nolimits_{j = 0}^n {{B_j}{z^j}} \), both of degree n, is defined by \(f * g\left( z \right) = \sum\nolimits_{j = 0}^n {{A_j}{B_j}{{\left( {\begin{array}{*{20}{c}}n \\ j \end{array}} \right)}^{ - 1}}{z^j}} \). In this paper, we estimate the minimum and the maximum of the modulus of f * g(z) on z = 1 and thereby obtain results analogues to Bernstein type inequalities for polynomials.     

Real moments of the restrictive factor

Let λ be a real number such that 0 < λ < 1. We establish asymptotic formulas for the weighted real moments Σ _n≤x R ^λ (n)(1 − n/x), where R(n) =$ \prod\nolimits_{\nu = 1}^k {p_\nu ^{\alpha _\nu - 1} } $ \prod\nolimits_{\nu = 1}^k {p_\nu ^{\alpha _\nu - 1} } is the Atanassov strong restrictive factor function and n =$ \prod\nolimits_{\nu = 1}^k {p_\nu ^{\alpha _\nu } } $ \prod\nolimits_{\nu = 1}^k {p_\nu ^{\alpha _\nu } } is the prime factorization of n.     

Meet and join matrices in the poset of exponential divisors

It is well-known that (ℤ₊, |) = (ℤ₊, GCD, LCM) is a lattice, where | is the usual divisibility relation and GCD and LCM stand for the greatest common divisor and the least common multiple of positive integers. The number $ d = \prod\nolimits_{k = 1}^r {p_k^{d^{(k)} } } $ d = \prod\nolimits_{k = 1}^r {p_k^{d^{(k)} } } is said to be an exponential divisor or an e-divisor of $ n = \prod\nolimits_{k = 1}^r {p_k^{n^{(k)} } } $ n = \prod\nolimits_{k = 1}^r {p_k^{n^{(k)} } } (n > 1), written as d | _e n, if d ^(k) for all prime divisors p _k of n. It is easy to see that (ℤ₊\{1}, | _e is a poset under the exponential divisibility relation but not a lattice, since the greatest common exponential divisor (GCED) and the least common exponential multiple (LCEM) do not always exist.