Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

Spectral decomposition and Gelfand’s theorem

We consider the spectral decomposition of A, the generator of a polynomially bounded n-times integrated group whose spectrum set $\sigma(A)=\{i\lambda_{k};k\in\mathbb{\mathbb{Z}}^{*}\}We consider the spectral decomposition of A, the generator of a polynomially bounded n-times integrated group whose spectrum set s(A)={il_k;k ? \mathbb\mathbbZ^*}\sigma(A)=\{i\lambda_{k};k\in\mathbb{\mathbb{Z}}^{*}\} is discrete and satisfies ?\frac1|l_k|^ld_kⁿ < ￥\sum \frac{1}{|\lambda_{k}|^{\ell}\delta_{k}^{n}}<\infty , where ℓ is a nonnegative integer and d_k=min(\frac|l_k+1-l_k|2,\frac|l_k-1-l_k|2)\delta _{k}=\min(\frac{|\lambda_{k+1}-\lambda _{k}|}{2},\frac{|\lambda _{k-1}-\lambda _{k}|}{2}) . In this case, Theorem 3, we show by using Gelfand’s Theorem that there exists a family of projectors (P_k)_{k ? \mathbb\mathbbZ^*}(P_{k})_{k\in\mathbb{\mathbb{Z}}^{*}} such that, for any x∈D(A ^n+ℓ ), the decomposition ∑P _k x=x holds.     

On the growth order of the rectangular partial sums of multiple non-orthogonal series

Пустьd-натуральное ч исло,Z ^d — множество на боров k=(k ₁, ...,k _d ), состоящих из неотрицательных цел ыхk _j ,Z ₊ ^d =k∈Z ^d :k≧1. Предположи м, что системаf _k (x):k∈Z ₊ ^d ? ?L₂(X,A, μ) и последовател ьностьa _k :k∈Z ₊ ^d . таковы, чт о для всех b∈Z^d и m∈Z ₊ ^d выполн ены неравенства (2) $$\left\| {\sum\limits_{b + 1 \leqq k \leqq b + m} {a_k f_k (x)} } \right\|_2^2 \leqq w^2 (m)\sum\limits_{b + 1 \leqq k \leqq b + m} {a_k^2 } $$ где последовательно сть {w(m): m∈Z ₊ ^d положительн а и не убывает. Например, есл иf _k (х) — квазистационарная система, то для соотве тствующей последовательности {ω(m) (2) имeeт Меcтo ДЛЯ ЛЮбОЙ ПОС ЛеДОВатеЛЬНОСТИ {a_k}. В работе получены оце нки порядка роста пря моугольных частных суммS _m (x)= =∑ a_kf_k(x) при maxmj→∞ как в случ ае {a_k}∈l₂, таки для {a_k}l₂. Эти оценки явля1≦k≦m 1≦j≦d ются новыми даже для о ртогональных кратны х рядов. Показано, что упомяну тые оценки в общем слу чае являются точными.     

Bounds for ratios of eigenvalues using traces

Let A be an n × n matrix with real eigenvalues λ₁ ? … ? λ_n, and let 1 ? k < l ? n. Bounds involving trA and trA² are introduced for λ_k/λ_l, (λ_k ? λ_l)/(λ_k + λ_l), and {kλ_k + (n ? l + 1)λ_l}²/{kλ²_k + (n ? l + 1)λ²_l}. Also included are conditions for λ_l >; 0 and for λ_k + λ_l > 0.     

Periodicity and attractivity for a rational recursive sequence

In this paper, the existence of periodic positive solution and the attractivity are investigated for the rational recursive sequencex _n+1=(A+ax _n?k )/(b+x _n?1), whereA, a andb are real numbers,k andl are nonnegative integer numbers.     

An intersection problem whose extremum is the finite projective space

Suppose that $\text{A}$ is a finite set-system of N elements with the property |A ∩ A′| = 0, 1 or k for any two different A, A′ ?A. We show that for N > k¹⁴

$\text{|a|=?}\text{N(N?1)(N?k)}\text{(k}{}^2\text{?k+1)(k}{}^2\text{?2k+1)}\text{+}\text{N(N?1)}\text{k(k?1)}\text{+N+1}$

where equality holds if and only if k = q + 1 (q is a prime power) $\text{N =}\text{(q}{}^{\mathrm{t+1}}\text{? 1)}\text{(q ? 1)}$ and $\text{A}$ is the set of subspaces of dimension at most two of the t-dimensional finite projective space of order q.     

A reducibility theorem for smooth quasiperiodic linear systems

We construct an iterative procedure for finding a change of variables to reduce the linear system. x′ = Ax + P(?)x ?′ = ω where P(?) is l times differentiable, to a system with constant coefficients. Under certain conditions on ω and the eigenvalues of A we use the technique of accelerated convergence to overcome the difficulty of small divisors and show that this sequence of transformations converges to a quasiperiodic transformation. As is always the case in such problems, there is an inevitable loss of derivatives. The best previous result, due to Mitropol'skǐi and Samoǐlenko required $\text{l>}\text{k}\text{(k ? 1)(2 ? k)}\text{[k(m + τ) + 2m + 2]}$, where κ is the exponent of the accelerated convergence (1 < κ < 2), and τ is a constant occurring in the relationship between the eigenvalues of A and ω. Our result requires only that l>τ.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

On the positive nonoscillatory solutions of the difference equation Xn＋1=α＋（xn-k/xn-m）^p

The aim of this paper is to show that the following difference equation：Xn＋1=α＋（xn-k/xn-m）^p, n=0,1,2,…,
where α 〉 -1, p 〉 O, k,m ∈ N are fixed, 0 ≤ m 〈 k, x-k, x-k＋1,…,x-m,…,X-1, x0 are positive, has positive nonoscillatory solutions which converge to the positive equilibrium x=α＋1. It is interesting that the method described in the paper, in some cases can also be applied when the parameter α is variable.     

Self-adjusting stochastic processes

Let A_t(i, j) be the transition matrix at time t of a process with n states. Such a process may be called self-adjusting if the occurrence of the transition from state h to state k at time t results in a change in the hth row such that A_t+1(h, k) ? A_t(h, k). If the self-adjustment (due to transition h → kx) is A_{t + 1}(h, j) = λA_t(h, j) + (1 ? λ)δ_jk (0 < λ < 1), then with probability 1 the process is eventually periodic. If A₀(i, j) < 1 for all i, j and if the self-adjustment satisfies A_{t + 1}(h, k) = ?(A_t(h, k)) with ?(x) twice differentiable and increasing, x < ?(x) < 1 for 0 ? x < 1,?(1) = ?′(1) = 1, then, with probability 1, lim A_t does not exist.     

Solution-free sets for linear equations

We study the maximum size and the structure of sets of natural numbers which contain no solution of one or more linear equations. Thus, for every natural i and k?2, we find the minimum α=α(i,k) such that if the upper density of a strongly k-sum-free set is at least α, then A is contained in a maximal strongly k-sum-free set which is a union of at most i arithmetic progressions. We also determine the maximum density of sets of natural numbers without solutions to the equation x=y+az, where a is a fixed integer.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Robust interpolation of random fields homogeneous in time and isotropic on a sphere,which are observed with noise

We study the problem of optimal linear estimation of the functional $$A_N \xi = \sum\limits_{k = 0}^{\rm N} {\int\limits_{S_n } {a(k,x)\xi (k,x)m_n (dx),} }$$ , which depends on unknown values of a random field ξ(k, x),k?Z,x?S _n homogeneous in time and isotropic on a sphereS _n, by observations of the field ξ(k,x)+η(k,x) with k? Z{0, 1, ...,N},x?S_n (here, η (k, x) is a random field uncorrelated with ξ(k, x), homogeneous in time, and isotropic on a sphere S_n). We obtain formulas for calculation of the mean square error and spectral characteristic of the optimal estimate of the functionalA _Nξ. The least favorable spectral densities and minimax (robust) spectral characteristics are found for optimal estimates of the functionalA _Nξ.     

Finite time extinction of super-Brownian motions with deterministic catalyst

In this paper we consider a super-Brownian motion X with branching mechanism k(x)zα, where k(x) > 0 is a bounded Holder continuous function on Rd and infx∈Rd k(x) = 0. We prove that if k(x) ≥ //x// -l(0 ≤l < ∞) for sufficiently large x, then X has compact support property, and for dimension d = 1, if k(x) ≥exp(-l‖x‖)(0≤l < ∞) for sufficiently large x, then X also has compact support property. The maximal order of k(x) for finite time extinction is different between d = 1, d = 2 and d ≥ 3: it is O(‖x‖-(α+1)) in one dimension, O(‖x‖-2(log‖x‖)-(α+1) ) in two dimensions, and O(‖x‖2) in higher dimensions. These growth orders also turn out to be the maximum order for the nonexistence of a positive solution for 1/2Δu =k(x)uα.     

On extensions of polynomial functions

Let X, Y be two linear spaces over the field ? of rationals and let D ≠ ? be a (?—convex subset of X. We show that every function ?: D → Y satisfying the functional equation $${\mathop\sum^{n+1}\limits_{j=0}}(-1)^{n+1-j}\Bigg(^{n+1}_{j}\Bigg)f\Bigg((1-{j\over {n+1}})x+{j\over{n+1}}y\Bigg)=0,\ \ \ x,y\in\ D,$$ admits an extension to a function F: X → Y of the form $$F(x)=A^o+A^1(x)+\cdot\cdot\cdot+A^n(x),\ \ \ x\in\ X,$$ where A ^o ∈ Y, A^k(x) ? A_k(x,…,x), x ∈ X, and the maps A _k: X ^k → Y are k—additive and symmetric, k ∈ {1,…, n}. Uniqueness of the extension is also discussed.     

An asymptotic evaluation of the cycle index of a symmetric group

Let $\text{Z(S}{}_{\mathrm{n}}\text{;?(x))}$ denote the polynomial obtained from the cycle index of the symmetric group Z(S_n) by replacing each variable s_i by f(x¹). Let f(x) have a Taylor series with radius of convergence ? of the form f(x)=x^k + a_k+1x^k+1 + a_k+2x^k+2+? with every a₁?0. Finally, let 0<x<1 and let x??. We prove that

This limit is used to estimate the probability (for n and p both large) that a point chosen at random from a random p-point tree has degree n + 1. These limiting probabilities are independent of p and decrease geometrically in n, contrasting with the labeled limiting probabilities of $\text{1}\text{n!e}$.In order to prove the main theorem, an appealing generalization of the principle of inclusion and exclusion is presented.     

A metric discrepancy result for a lacunary sequence with small gaps

For any ${G(k) \uparrow \infty}$ , there exists a sequence {n _k } of integers with 1 ?? n _k+1 ? n _k ?? G(k) such that the discrepancies of {n _k x} obey the law of the iterated logarithm in the same way as uniform distributed i.i.d.     

Padé approximants of special functions

Let $ {f_{\gamma }}(x) = \sum\nolimits_{{k = 0}}^{\infty } {{{{T_k (x)}} \left/ {{{{\left( \gamma \right)}_k}}} \right.}} $ , where (??) _k =??(??+1) ? (??+k?1) and T _k (x)=cos (k arccos x) are Padé?CChebyshev polynomials. For such functions and their Padé?CChebyshev approximations $ \pi_{n,m}^{ch}\left( {x;{f_{\gamma }}} \right) $ , we find the asymptotics of decreasing the difference $ {f_{\gamma }}(x) - \pi_{n,m}^{ch}\left( {x;{f_{\gamma }}} \right) $ in the case where 0 ? m ? m(n), m(n) = o (n), as n???? for all x ?? [?1, 1]. Particularly, we determine that, under the same assumption, the Padé?CChebyshev approximations converge to f _?? uniformly on the segment [?1, 1] with the asymptotically best rate.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

Monochromatic Vs multicolored paths

Letl andk be positive integers, and letX={0,1,...,l ^k?1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx ₀<x ₁<...<x _l ofX with δ(x ₀,x ₁)=δ(x ₁,x ₂)=...=δ(x _l?1,x _l), or else there exist elementsy ₀<y ₁<...<y _k ofX with δ(y _i?1,y _i) ∈ δ(y _j?1,y _j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)^2k . The general question remains open.