Permutation Polynomials Modulo 2w

We give an exact characterization of permutation polynomials modulo n=2^w, w≥2: a polynomial P(x)=a₀+a₁x +···+a_dx^d with integral coefficients is a permutation polynomial modulo n if and only if a₁ is odd, (a₂+a₄+a₆+···) is even, and (a₃+a₅+a₇+···) is even. We also characterize polynomials defining latin squares modulo n=2^w, but prove that polynomial multipermutations (that is, a pair of polynomials defining a pair of orthogonal latin squares) modulo n=2^wdo not exist.     

A method of constructing Krall's polynomials

We propose a method of constructing orthogonal polynomials P_n(x) (Krall's polynomials) that are eigenfunctions of higher-order differential operators. Using this method we show that recurrence coefficients of Krall's polynomials P_n(x) are rational functions of n. Let P_n^(a,b;M)(x) be polynomials obtained from the Jacobi polynomials P_n^(a,b)(x) by the following procedure. We add an arbitrary concentrated mass M at the endpoint of the orthogonality interval with respect to the weight function of the ordinary Jacobi polynomials. We find necessary conditions for the parameters a,b in order for the polynomials P_n^(a,b;M)(x) to obey a higher-order differential equation. The main result of the paper is the following. Let a be a positive integer and b⩾−1/2 an arbitrary real parameter. Then the polynomials P_n^(a,b;M)(x) are Krall's polynomials satisfying a differential equation of order 2a+4.     

Rational approximation with varying weights I

We investigate two problems concerning uniform approximation by weighted rationals {w ⁿr_n～ _∞ ⁿ⁼¹ }, wherer _n=p_n Namely, forw(x):=e ^x we prove that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [0,a] witha>2π. Forw(x):=x ^?, ?>1, we show that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [b, 1] withb<tan ⁴(π(??1)/4?). (The latter result can be interpreted as a rational analogue of results concerning “incomplete polynomials.”) More generally, for α≥0, β≥0, α+β>0, we investigate forw(x)=e ^x andw(x)=x ^?, the possibility of approximation byw ⁿ p_n/q_n～ _∞ ⁿ⁼¹ , where depp _n≤αn, degq _n≤βn. The analysis utilizes potential theoretic methods. These are essentially sharp results though this will not be established in this paper.     

Where does the sup norm of a weighted polynomial live?

A characterization is given of the sets supporting the uniform norms of weighted polynomials [w(x)] ⁿ P _n (x), whereP _n is any polynomial of degree at mostn. The (closed) support ∑ ofw(x) may be bounded or unbounded; of special interest is the case whenw(x) has a nonempty zero setZ. The treatment of weighted polynomials consists of associating each admissible weight with a certain functional defined on subsets of ∑ —Z. One main result of this paper states that there is a unique compact set (independent ofn andP _n ) maximizing this functional that contains the points where the norms of weighted polynomials are attained. The distribution of the zeros of Chebyshev polynomials corresponding to the weights [w(x)] ⁿ is also studied. The main theorems give a unified method of investigating many particular examples. Applications to weighted approximation on the real line with respect to a fixed weight are included.     

Some imbedding theorems for the function spaces − fr,ρ,θ λ,ϕ,bs (G)

One considers imbedding type theorems for the spaces ? _fr,ρ,θ ^λ,?,bs (G) of real functions, defined on a domain G of then -dimensional Euclidean space Eⁿ. As opposed to the known spaces of this type, the power function t^a, characterizing the degree of the smoothness of the functions, is replaced here by a function ?(t), arbitrary in a certain sense.     

Polynomials orthogonal on the semicircle,II

Generalizing previous work [2], we study complex polynomials {π _k },π _k (z)=z ^k +?, orthogonal with respect to a complex-valued inner product (f,g)=∫ ₀ ^π f(e ^iθ)g(e ^iθ)w(e ^iθ)dθ. Under suitable assumptions on the “weight function”w, we show that these polynomials exist whenever Re ∫ ₀ ^π w(e ^iθ)dθ≠0, and we express them in terms of the real polynomials orthogonal with respect to the weight functionw(x). We also obtain the basic three-term recurrence relation. A detailed study is made of the polynomials {π _k } in the case of the Jacobi weight functionw(z)=(1?z)^α(1+z)^β, α>?1, and its special case \(\alpha = \beta = \lambda - \tfrac{1}{2}\) (Gegenbauer weight). We show, in particular, that for Gegenbauer weights the zeros ofπ _n are all simple and, ifn≥2, contained in the interior of the upper unit half disc. We strongly suspect that the same holds true for arbitrary Jacobi weights. Finally, for the Gegenbauer weight, we obtain a linear second-order differential equation forπ _n (z). It has regular singular points atz=1, ?1, ∞ (like Gegenbauer's equation) and an additional regular singular point on the negative imaginary axis, which depends onn.     

Weighted polynomial approximation with Freud weights

We show that ifw(x)=exp(–|x|), then in the case =1 for every continuousf that vanishes outside the support of the corresponding extremal measure there are polynomialsP _n of degree at mostn such thatw ⁿ P _n uniformly tends tof, and this is not true when <1. these=" are=" the=" missing=" cases=" concerning=" approximation=" by=" weighted=" polynomials=" of=" the=">w ⁿ P _n wherew is a Freud weight. Our second theorem shows that even if we are only interested in approximation off on the extremal support, the functionf must still vanish at the endpoints, and we actually determine the (sequence of) largest possible intervals where approximation is possible. We also briefly discuss approximation by weighted polynomials of the formW(a_nx)P _n (x).Communicated by Edward B. Saff.     

Estimation of an algebraic polynomial in a plane in terms of its real part on the unit circle

We consider the class P _n ^* of algebraic polynomials of a complex variable with complex coefficients of degree at most n with real constant terms. In this class we estimate the uniform norm of a polynomial P _n ∈ P _n ^* on the circle Γ_r = z ∈ ?: ¦z¦ = r of radius r = 1 in terms of the norm of its real part on the unit circle Γ₁ More precisely, we study the best constant μ(r, n) in the inequality ||P_n||C(Γ_r) ≤ μ(r,n)||Re P_n||C(Γ₁). We prove that μ(r,n) = rⁿ for rⁿ⁺² ? r ⁿ ? 3r² ? 4r + 1 ≥ 0. In order to justify this result, we obtain the corresponding quadrature formula. We give an example which shows that the strict inequality μ(r, n) = r ⁿ is valid for r sufficiently close to 1.     

Homogenization of foliated annuli

Let \(\Omega = \Omega _0 \backslash \bar \Omega _1\) be a regular annulus inR ^N and \(\phi :\bar \Omega \to R\) be a regular function such that φ=0 on ?Ω₀, φ=1 on ?Ω₁ and ▽φ ≠ 0. Let K_n be the subset of functions v ε W^1,p (Ω) such that v=0 on ?Ω₀, v=1 on ?Ω₁, v=(unprescribed) constant on n given level surfaces of φ. We study the convergence of sequences of minimization problems of the type $$Inf\left\{ {\int\limits_\Omega {\frac{1}{{a_n \circ \phi }}G(x,(a_n \circ \phi )\nabla v)dx;v \in K_n } } \right\},$$ where a_n ε L^∞ (0,1) and G: (x, ζ) ε Ω × R^N → G(x, ζ εR is convex with respect to ξ and verifies some standard growth conditions.     

Uniform asymptotic expansion for a class of polynomials biorthogonal on the unit circle

An asymptotic expansion including error bounds is given for polynomials {P _n, Q_n} that are biorthogonal on the unit circle with respect to the weight function (1?e^iθ)^α+β(1?e^?iθ)^α?β. The asymptotic parameter isn; the expansion is uniform with respect toz in compact subsets ofC{0}. The pointz=1 is an interesting point, where the asymptotic behavior of the polynomials strongly changes. The approximants in the expansions are confluent hyper-geometric functions. The polynomials are special cases of the Gauss hyper-geometric functions. In fact, with the results of the paper it follows how (in a uniform way) the confluent hypergeometric function is obtained as the limit of the hypergeometric function₂ F ₁(a, b; c; z/b), asb→±∞,z≠b, withz=0 as “transition” point in the uniform expansion.     

Hausdorff-summability of power series II

Let H _x a regular Hausdorff method and P(w)=∑ a_k w^k a power series with positive radius of convergence. A theorem of Okada states that P(w) is summable (H _x ) for w in a certain starshaped region G(H _x ,P). We call G=G(H _x ,P) the exact region of summability for P if summability cannot hold for any w \( \in \bar G\) Okada's theorem is said to be sharp for H_x if G(H_x,P) is the exact region of summability for any P. Three items are treated: 1. Criteria for Okada's theorem to be sharp are given in terms of the distribution function X (t) and the Mellin transform \(D(z) = \int\limits_0^1 {t^z d\chi (t)} \) . 2. When is Okada's theorem sharp for product methods? 3. Special classes of functions P(w) are indicated such that G(H_x, P) is the exact region of summability for any H_x. We use the notations of “Hausdorff-Summability of Power Series I” referred as “I”.     

Structure of cubic mapping graphs for the ring of Gaussian integers modulo n

Let ? _n [i] be the ring of Gaussian integers modulo n. We construct for ?n[i] a cubic mapping graph Γ(n) whose vertex set is all the elements of ?n[i] and for which there is a directed edge from a ∈ ?n[i] to b ∈ ?n[i] if b = a ³. This article investigates in detail the structure of Γ(n). We give suffcient and necessary conditions for the existence of cycles with length t. The number of t-cycles in Γ₁(n) is obtained and we also examine when a vertex lies on a t-cycle of Γ₂(n), where Γ₁(n) is induced by all the units of ?n[i] while Γ₂(n) is induced by all the zero-divisors of ?n[i]. In addition, formulas on the heights of components and vertices in Γ(n) are presented.     

Approximately reducing subspaces for unbounded linear operators

We give sufficient conditions for generation of strongly continuous contraction semigroups of linear operators on Hilbert or Banach space. Let L be a dissipative (unbounded) linear operator in a Hilbert space $\text{H}$ and let {P_n} be an increasing sequence of self-adjoint projections converging weakly to the identity projection. We show that if there is a positive integer k such that for all n the range of P_n is contained in the domain of L and mapped by L into the range of P_{n + k}, and if the sequence {LP_n ? P_nLP_n} is dominated in norm (∥LP_n ? P_nLP_n∥ ? a_n) by some {a_n} ? $\text{R}$₊ with ∑_{n = 1}^∞a_n^?1 = ∞, then the closure of the restriction of L to ∪_{n = 1}^∞ range (P_n) is the infinitesimal generator of a strongly continuous contraction semigroup on $\text{H}$. Applications to an important class of finite perturbations, properly larger than the finite Kato perturbations, are given.We also give sufficient conditions for generation of contraction semigroups when {P_γ} (indexed by a directed set) is a set of bounded self-adjoint operators converging weakly to the identity and each having range contained in D(L). In the latter theorem, and in an analogous theorem for dissipative linear operators L in a Banach space, we do not assume that L interchanges at most finitely many of the approximately reducing operators P_γ.     

Enumeration of arrays of a given size

Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)².In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums $\text{nr}\text{(2, n)}$ and $\text{nr}\text{(3, n)}$, where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)ⁿ and (1 ? y)²ⁿ?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Necessary and sufficient conditions for the Robbins-Monro method

This paper examines the relation between convergence of the Robbins-Monro iterates $\text{X}{}_{\mathrm{n+1}}\text{= X}{}_{\mathrm{n}}\text{?a}{}_{\mathrm{n}}\text{?(X}{}_{\mathrm{n}}\text{)+a}{}_{\mathrm{n}}\text{ξ}{}_{\mathrm{n}}\text{, ?(θ)=0}$, and the laws of large numbers S_n=a_nΣ^n?1_j=0ξ_j→0 as n→+∞. If a_n is decreasing at least as rapidly as c/n, then X_n→θw.p. 1 (resp. in L_p, p?1) implies S_n→0 w.p. 1 (resp. in L_p, p?1) as n→+∞. If a_n is decreasing at least as slowly as c?n and lim_n→+∞a_n=0, then S_n→0 w.p. 1 (resp. in L_p, p?2) implies X_n→θw.p. 1 (resp. in L_p, p?2) as n →+∞. Thus, there is equivalence in the frequently examined case $\text{a}{}_{\mathrm{n}}\text{?c?n}$. Counter examples show that the LLN must have the form of S_n, that the rate of decrease conditions are sharp, that the weak LLN is neither necessary nor sufficient for the convergence in probability of X_n to θ when $\text{a}{}_{\mathrm{n}}\text{?c?n}$.     

Cone Dependence—A Basic Combinatorial Concept

We call A ? $ \mathbb{E} $ ⁿ cone independent of B ? $ \mathbb{E} $ ⁿ , the euclidean n-space, if no a = (a ₁,..., a _n ) ∈ A equals a linear combination of B \ {a} with non-negative coefficients. If A is cone independent of A we call A a cone independent set. We begin the analysis of this concept for the sets P(n) = {A ? {0, 1} ⁿ ? $ \mathbb{E} $ ⁿ : A is cone independent} and their maximal cardinalities c(n) ? max{|A| : A ∈ P(n)}. We show that lim _{n → ∞} $ \frac{{c\left( n \right)}}{{2^n }} $ > $\frac{1}{2}$ , but can't decide whether the limit equals 1. Furthermore, for integers 1 < k < ? ≤ n we prove first results about c _n (k, ?) ? max{|A| : A ∈ P _n (k, ?)}, where P _n (k, ?) = {A : A ? V ⁿ _k and V ⁿ _? is cone independent of A} and V ⁿ _k equals the set of binary sequences of length n and Hamming weight k. Finding c _n (k, ?) is in general a very hard problem with relations to finding Turan numbers.     

A note on a problem by H. S. Shapiro

В РАБОтЕ ДОкАжАНО, ЧтО limk _a *f(x)=f(x) пОЧтИ ВсУДУ, гДЕk _a(t)=a^?n k(a^?1t), t?Rⁿ, Для Дль ДОВОльНО шИРОкОг О клАссА ФУНкцИИk(t). ДАНы УслОВИь, пРИ кОтО Рых пОлУЧЕННыИ РЕжУл ьтАт РАспРОстРАНьЕтсь НА ФУНкцИУ $$k(x,y) = \gamma \frac{1}{{1 + |x|^\alpha }} \cdot \frac{1}{{1 + |y|^\beta }},$$ гДЕ α, β>1, А γ — НОРМИРУУЩ ИИ МНОжИтЕль тАкОИ, Чт О∫∫k(x, y) dx dy=1.     

On the tree structure of the power digraphs modulo n

For any two positive integers n and k ? 2, let G(n, k) be a digraph whose set of vertices is {0, 1, …, n ? 1} and such that there is a directed edge from a vertex a to a vertex b if a ^k ≡ b (mod n). Let \(n = \prod\nolimits_{i = 1}^r {p_i^{{e_i}}} \) be the prime factorization of n. Let P be the set of all primes dividing n and let P ₁, P ₂ ? P be such that P ₁ ∪ P ₂ = P and P ₁ ∩ P ₂ = ?. A fundamental constituent of G(n, k), denoted by \(G_{{P_2}}^*(n,k)\), is a subdigraph of G(n, k) induced on the set of vertices which are multiples of \(\prod\nolimits_{{p_i} \in {P_2}} {{p_i}} \) and are relatively prime to all primes q ∈ P ₁. L. Somer and M. K?i?ek proved that the trees attached to all cycle vertices in the same fundamental constituent of G(n, k) are isomorphic. In this paper, we characterize all digraphs G(n, k) such that the trees attached to all cycle vertices in different fundamental constituents of G(n, k) are isomorphic. We also provide a necessary and sufficient condition on G(n, k) such that the trees attached to all cycle vertices in G(n, k) are isomorphic.