Periods of some nonlinear shift registers

We determine the set of all possible least periods of shift register sequences for non-linear feedback functions of the form f(x₀,…,x_m?1) = x₀ + Π_i=1^k (x_i + b_i) where m ? k + 1 ? 3 and the least period of the k-block b₁…b_k itself.     

Romanoff theorem in a sparse set

Let A be any subset of positive integers,and P the set of all positive primes.Two of our results are:(a) the number of positive integers which are less than x and can be represented as 2k + p(resp.p-2k) with k ∈ A and p ∈ P is more than 0.03A(log x/log 2)π(x) for all sufficiently large x;(b) the number of positive integers which are less than x and can be represented as 2q + p with p,q ∈ P is(1 + o(1))π(log x/log 2)π(x).Four related open problems and one conjecture are posed.     

Irreducibility criteria of Schur-type and Pólya-type

Let f(x)=(x-a₁)?(x-a_m){f(x)=(x-a_1)\cdots (x-a_m)}, where a ₁, . . . , a _m are distinct rational integers. In 1908 Schur raised the question whether f(x) ± 1 is irreducible over the rationals. One year later he asked whether (f(x))^2k+1{(f(x))^{2^k}+1} is irreducible for every k ≥ 1. In 1919 Pólya proved that if P(x) ? \mathbbZ[x]{P(x)\in\mathbb{Z}[x]} is of degree m and there are m rational integer values a for which 0 < |P(a)| < 2^−N N! where N=ém/2ù{N=\lceil m/2\rceil}, then P(x) is irreducible. A great number of authors have published results of Schur-type or Pólya-type afterwards. Our paper contains various extensions, generalizations and improvements of results from the literature. To indicate some of them, in Theorem 3.1 a Pólya-type result is established when the ground ring is the ring of integers of an arbitrary imaginary quadratic number field. In Theorem 4.1 we describe the form of the factors of polynomials of the shape h(x) f(x) + c, where h(x) is a polynomial and c is a constant such that |c| is small with respect to the degree of h(x) f(x). We obtain irreducibility results for polynomials of the form g(f(x)) where g(x) is a monic irreducible polynomial of degree ≤ 3 or of CM-type. Besides elementary arguments we apply methods and results from algebraic number theory, interpolation theory and diophantine approximation.     

Dimensions of some fractals defined via the semigroup generated by 2 and 3

We compute the Hausdorff and Minkowski dimension of subsets of the symbolic space Σ _m ={0, ...,m?1}^? that are invariant under multiplication by integers. The results apply to the sets {x∈Σ _m :? k, x _k x _2k ... x _nk =0}, where n ≥ 3. We prove that for such sets, the Hausdorff and Minkowski dimensions typically differ.     

An inversion formula for a class of integral transforms,II

In this note we give a procedure for inverting the integral transform f(x) = ∫₀^∞k(xt) φ(t) dt, where the functions f(x) and k(x) are known and φ(x) is to be found. The inversion is accomplished in two steps: by first defining a transforming function, which is an integral, followed by the application of an infinite order differential operator.     

Universally bad integers and the 2-adics

In his 1964 paper, de Bruijn (Math. Comp. 18 (1964) 537) called a pair (a,b) of positive odd integers good, if , where is the set of nonnegative integers whose 4-adic expansion has only 0's and 1's, otherwise he called the pair (a,b) bad. Using the 2-adic integers we obtain a characterization of all bad pairs. A positive odd integer u is universally bad if (ua,b) is bad for all pairs of positive odd integers a and b. De Bruijn showed that all positive integers of the form u=2^k+1 are universally bad. We apply our characterization of bad pairs to give another proof of this result of de Bruijn, and to show that all integers of the form u=φ_p^k(4) are universally bad, where p is prime and φ_n(x) is the nth cyclotomic polynomial. We consider a new class of integers we call de Bruijn universally bad integers and obtain a characterization of such positive integers. We apply this characterization to show that the universally bad integers u=φ_p^k(4) are in fact de Bruijn universally bad for all primes p>2. Furthermore, we show that the universally bad integers φ_2^k(4), and more generally, those of the form 4^k+1, are not de Bruijn universally bad.     

Recurrent points and non-wandering points of graph maps

Let G be a graph and f:G→G be a continuous map. Denote by P(f), R(f) and Ω(f) the sets of periodic points, recurrent points and non-wandering points of f, respectively. In this paper we show that: (1) If L=(x,y) is an open arc contained in an edge of G such that {fm(x),fk(y)}⊂(x,y) for some m,k∈N, then R(f)∩(x,y)≠∅; (2) Any isolated point of P(f) is also an isolated point of Ω(f); (3) If x∈Ω(f)−Ω(fn) for some n∈N, then x is an eventually periodic point. These generalize the corresponding results in W. Huang and X. Ye (2001) [9] and J. Xiong (1983, 1986) [17] and [19] on interval maps or tree maps.     

Regularized traces of singular differential operators with canonical boundary conditions

A self-adjoint differential operator \(\mathbb{L}\) of order 2m is considered in L ₂[0,∞) with the classic boundary conditions \(y^{(k_1 )} (0) = y^{(k_2 )} (0) = y^{(k_3 )} (0) = \ldots = y^{(k_m )} (0) = 0\), where 0 ≤ k ₁ < k ₂ < ... < k _m ≤ 2m ? 1 and {k _s } _s=1 ^m ∪ {2m ? 1 ? k _s } _s=1 ^m = {0, 1, 2, ..., 2m ? 1}. The operator \(\mathbb{L}\) is perturbed by the operator of multiplication by a real measurable bounded function q(x) with a compact support: \(\mathbb{P}\) f(x) = q(x)f(x), f ∈ L ₂[0,∞). The regularized trace of the operator \(\mathbb{L} + \mathbb{P}\) is calculated.     

The program iteration method in a game problem of guidance

Let a sequence of d-dimensional vectors n _k = (n _k ¹ , n _k ² ,..., n _k ^d ) with positive integer coordinates satisfy the condition n _k ^j = α _j m _k +O(1), k ∈ ?, 1 ≤ j ≤ d, where α ₁ > 0,..., α _d > 0 and {m _k } _k=1 ^∞ is an increasing sequence of positive integers. Under some conditions on a function φ: [0,+∞) → [0,+∞), it is proved that, if the sequence of Fourier sums \({S_{{m_k}}}\) (g, x) converges almost everywhere for any function g ∈ φ(L)([0, 2π)), then, for any d ∈ ? and f ∈ φ(L)(ln⁺ L) ^d?1([0, 2π) ^d ), the sequence \({S_{{n_k}}}\) (f, x) of rectangular partial sums of the multiple trigonometric Fourier series of the function f and the corresponding sequences of partial sums of all conjugate series converge almost everywhere.     

Best quadrature formulas at equally spaced nodes

It has been known for some time that the trapezoidal rule $\text{T}{}_{\mathrm{n}}\text{f =}\text{1}\text{2}\text{f(0) + f(1) + … + f(n ? 1) +}\text{1}\text{2}\text{f(n)}$ is the best quadrature formula in the sense of Sard for the space W^1,p, all functions such that f′ ?L^p. In other words, the norm of the error functional Ef = ∝₀ⁿf(x) dx ? ∑_{k = 0}ⁿλ_kf(k) in W^1,p is uniquely minimized by the trapezoidal sum. This paper deals with quadrature formulas of the form ∑_{k = 0}ⁿ ∑_l?Jc_klf^(l)(k) where J is some subset of {0, 1,…, m ? 1}. For certain index sets J we identify the best quadrature formula for the space W^m,p, all functions such that f^(m)?L^p. As a result, we show that the Euler-Maclaurin quadrature formula

$\text{T}{}_{\mathrm{n}}\text{f +}\text{∑}\text{o<2v≤m}\text{B}{}_{\mathrm{2v}}\text{(2v)!}\text{(f (2v?1)(0) ? f (2v?1) (n))}$

is the best quadrature formula of the above form with J = {0, 1, 3,…, ?m ? 1} for the space W^m,p, providing m is an odd integer.     

Equicontinuity of maps on a dendrite with finite branch points

Let(T, d) be a dendrite with finite branch points and f be a continuous map from T to T. Denote byω(x,f) and P(f) the ω-limit set of x under f and the set of periodic points of,respectively. Write Ω(x,f) = {y| there exist a sequence of points x_k E T and a sequence of positive integers n_1 n_2 … such that lim_(k→∞)x_k=x and lim_(k→∞)f~(n_k)(x_k) =y}. In this paper, we show that the following statements are equivalent:(1) f is equicontinuous.(2) ω(x, f) = Ω(x,f) for any x∈T.(3) ∩_(n=1)~∞f~n(T) = P(f),and ω(x,f)is a periodic orbit for every x ∈ T and map h : x→ω(x,f)(x ET)is continuous.(4) Ω(x,f) is a periodic orbit for any x∈T.     

Multiple recurrence and nilsequences

Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tⁿx)f(T²ⁿx)? f(T^knx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d^*(E)>0 and for all {n ? \mathbbZ\colon d^*(E?(E+n)?(E+2n)?(E+3n)) > d^*(E)⁴-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}     

A complete determination of Rabinowitsch polynomials

Let m be a positive integer and fm(x) be a polynomial of the form fm(x)=x²+x−m. We call a polynomial fm(x) a Rabinowitsch polynomial if for and consecutive integers x=x₀,x₀+1,…,x₀+s−1, |fm(x)| is either 1 or prime. In this paper, we show that there are exactly 14 Rabinowitsch polynomials fm(x).     

Three positive solutions to a discrete focal boundary value problem

We are concerned with the discrete focal boundary value problem Δ³x(t − k) = f(x(t)), x(a) = Δx(t₂) = Δ²x(b + 1) = 0. Under various assumptions on f and the integers a, t₂, and b we prove the existence of three positive solutions of this boundary value problem. To prove our results we use fixed point theorems concerning cones in a Banach space.     

On the finiteness of certain Rabinowitsch polynomials II

Let m be a positive integer and f_m(x) be a polynomial of the form f_m(x)=x²+x−m. We call a polynomial f_m(x) a Rabinowitsch polynomial if for and consecutive integers is either 1 or prime. In Byeon (J. Number Theory 94 (2002) 177), we showed that there are only finitely many Rabinowitsch polynomials f_m(x) such that 1+4m is square free. In this note, we shall remove the condition that 1+4m is square free.     

On the class of limits of lacunary trigonometric series

Let (n _k ) _k≧1 be a lacunary sequence of positive integers, i.e. a sequence satisfying n _k+1/n _k > q > 1, k ≧ 1, and let f be a “nice” 1-periodic function with ∝ ₀ ¹ f(x) dx = 0. Then the probabilistic behavior of the system (f(n _k x)) _k≧1 is very similar to the behavior of sequences of i.i.d. random variables. For example, Erd?s and Gál proved in 1955 the following law of the iterated logarithm (LIL) for f(x) = cos 2πx and lacunary $ (n_k )_{k \geqq 1} $ : (1) $$ \mathop {\lim \sup }\limits_{N \to \infty } (2N\log \log N)^{1/2} \sum\limits_{k = 1}^N {f(n_k x)} = \left\| f \right\|_2 $$ for almost all x ∈ (0, 1), where ‖f‖₂ = (∝ ₀ ¹ f(x)² dx)^1/2 is the standard deviation of the random variables f(n _k x). If (n _k ) _k≧1 has certain number-theoretic properties (e.g. n _k+1/n _k → ∞), a similar LIL holds for a large class of functions f, and the constant on the right-hand side is always ‖f‖₂. For general lacunary (n _k ) _k≧1 this is not necessarily true: Erd?s and Fortet constructed an example of a trigonometric polynomial f and a lacunary sequence (n _k ) _k≧1, such that the lim sup in the LIL (1) is not equal to ‖f‖₂ and not even a constant a.e. In this paper we show that the class of possible functions on the right-hand side of (1) can be very large: we give an example of a trigonometric polynomial f such that for any function g(x) with sufficiently small Fourier coefficients there exists a lacunary sequence (n _k ) _k≧1 such that (1) holds with √‖f‖ ₂ ² + g(x) instead of ‖f‖₂ on the right-hand side.     

Subsequent to a theorem of Markoff

Let f(x, y) be an indefinite binary quadratic form, d(f) its discriminant, m(f) the infimum of |f(x, y)| over all integers x, y not both zero, and put $\text{μ(f) = m(f)d(f)}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$. In this paper we prove the existence of countably many disjoint open intervals I_j contained in $\text{0 ≤ x ≤}\text{1}\text{3}$ such that there is no f with μ(f) in I_j (j = 1, 2,…) and such that for any interval I containing two intervals I_j, I_k there is an f with μ(f) in I.     

Nonparametric estimation of mixed partial derivatives of a multivariate density

On the basis of a random sample of size n on an m-dimensional random vector X, this note proposes a class of estimators f_n^(p) of f^(p), where f is a density of X w.r.t. a σ-finite measure dominated by the Lebesgue measure on R^m, p = (p₁,…,p_m), p_j ≥ 0, fixed integers, and for x = (x₁,…,x_m) in R^m, f^(p)(x) = ?^p₁+…+p_m f(x)/(?^p₁x₁ … ?^p_mx_m). Asymptotic unbiasedness as well as both almost sure and mean square consistencies of f_n^(p) are examined. Further, a necessary and sufficient condition for uniform asymptotic unbisedness or for uniform mean square consistency of f_n^(p) is given. Finally, applications of estimators of this note to certain statistical problems are pointed out.     

Solution and stability of generalized mixed type cubic, quadratic and additive functional equation in quasi-Banach spaces

In this paper, we achieve the general solution and the generalized Hyers–Ulam–Rassias stability of the following functional equation

f(x+ky)+f(x−ky)=k²f(x+y)+k²f(x−y)+2(1−k²)f(x)