Recursive constructions of -polynomials over

This paper presents procedures for constructing irreducible polynomials over GF(2^s) with linearly independent roots (or normal polynomials or N-polynomials). For a suitably chosen initial N-polynomial F₀(x)GF(2^s) of degree n, polynomials F_k(x)GF(2^s) of degrees n2^k are constructed by iteratively applying the transformation x→x+x^-1, and their roots are shown to form a normal basis of GF(2^sn2k) over GF(2^s). In addition, the sequences are shown to be trace compatible, i.e., the trace map T_{GF(2^sn2k+1)/GF(2^sn2k)} fromGF(2^sn2k+1) onto GF(2^sn2k) maps the roots of F_k+1(x) onto those of F_k(x).     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.     

New pairs of -sequences with 4-level cross-correlation

Let ω be a primitive element of GF(2ⁿ), where . Let d=(2^2k+2^s+1-2^k+1-1)/(2^s-1), where n=2k, and s is such that 2s divides k. We prove that the binary m-sequences s(t)=tr(ω^t) and s(dt) have a four-level cross-correlation function and give the distribution of the values.     

On the weak non-defectivity of veronese embeddings of projective spaces

Fix integers n, x, k such that n≥3, k>0, x≥4, (n, x)≠(3, 4) and k(n+1)<( _n ^n+x ). Here we prove that the order x Veronese embedding ofP ⁿ is not weakly (k−1)-defective, i.e. for a general S⊃P ⁿ such that #(S) = k+1 the projective space | I _2S (x)| of all degree t hypersurfaces ofP ⁿ singular at each point of S has dimension ( _n ^/n+x )−1− k(n+1) (proved by Alexander and Hirschowitz) and a general F∈| I _2S (x)| has an ordinary double point at each P∈ S and Sing (F)=S. The author was partially supported by MIUR and GNSAGA of INdAM (Italy).     

旗传递5-(v,k,2)设计的分类

本文研究了5-(v,k,2)设计的分类问题.利用典型群PSL(2,q)的子群作用于投影线的轨道定理,证明了旗传递5-(v,k,2)设计的自同构群的基柱不能与PSL(2,3n)同构.从而证明了不存在旗传递的5-(v,k,2)设计.     

On <Emphasis Type="Italic">n</Emphasis>-weak amenability of Rees semigroup algebras

Let S be a Rees matrix semigroup. We show that l ¹(S) is (2k + 1)-weakly amenable for k ∈ ℤ⁺.     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

Consecutive customer losses in oscillating GIX/M//n systems with state dependent services rates

We address the probability that k or more Consecutive Customer Losses take place during a busy period of a queue, the so-called k-CCL probability, for oscillating GI ^X /M//n systems with state dependent services rates, also denoted as GI ^X /M(m)−M(m)//n systems, in which the service rates oscillate between two forms according to the evolution of the number of customers in the system. We derive an efficient algorithm to compute k-CCL probabilities in these systems starting with an arbitrary number of customers in the system that involves solving a linear system of equations. The results derived are illustrated for specific sets of parameters.     

Onp-adic functions preserving Haar measure

Let {a _n } _n ^=0/ be a uniformly distributed sequence ofp-adic integers. In the present paper we study continuous functions close to differentiable ones (with respect to thep-adic metric); for these functions, either the sequence {f(a _n )} _n ^=0/ is uniformly distributed over the ring ofp-adic integers or, for all sufficiently largek, the sequences {f _k (_k(a_n))} _n ^=0/ are uniformly distributed over the residue class ring modp ^k , where _k is the canonical epimorphism of the ring ofp-adic integers to the residue class ring modp ^k andf _k is the function induced byf on the residue class ring modp ^k (i.e.,f k _(x) =f( _k (x)) (modp ^k )). For instance, these functions can be used to construct generators of pseudorandom numbers.Translated fromMatematicheskie Zametki, Vol. 63, No. 6, pp. 935–950, June, 1998.In conclusion, the author wishes to express his deep gratitude to V. S. Anashin for permanent attention to this research and for support.     

On the central value of symmetric square L-functions

Let S _k (N, χ) be the space of cusp forms of weight k, level N and character χ. For let L(s, sym² f) be the symmetric square L-function and be the Rankin–Selberg square attached to f. For fixed k ≥ 2, N prime, and real primitive χ, asymptotic formulas for the first and second moment of the central value of L(s, sym² f) and over a basis of S _k (N, χ) are given as N → ∞. As an application it is shown that a positive proportion of the central values L(1/2, sym² f) does not vanish. The author was supported by NSERC grant 311664-05.     

Distance Sequences In Locally Infinite Vertex-Transitive Digraphs

We prove that the out-distance sequence {f⁺(k)} of a vertex-transitive digraph of finite or infinite degree satisfies f⁺(k+1)≤f⁺(k)² for k≥1, where f⁺(k) denotes the number of vertices at directed distance k from a given vertex. As a corollary, we prove that for a connected vertex-transitive undirected graph of infinite degree d, we have f(k)=d for all k, 1≤k<diam(G). This answers a question by L. Babai.     

Another Proof of Kasami's Theorem

We give a short direct proof for a famous theorem published by Kasami in 1971. In terms of Walsh analysis it states that for d = 2^2k - 2^k + 1 the Walsh spectrum of the Boolean function Tr(x ^d ) on GF(2 ⁿ ) consists precisely of the three values 0, ±2^(n+s)/2 if s = gcd(k, n) = gcd(2k, n).     

Paranorm <Emphasis Type="Italic">I</Emphasis>-convergent sequence spaces

In this article we introduced the sequence spaces c ^I (p), c ₀ ^I (p), m ^I (p) and m ₀ ^I (p) for p = (p _k ), a sequence of positive real numbers. We study some algebraic and topological properties of these spaces. We prove the decomposition theorem and obtain some inclusion relations.      

On thek dimensional Piatetski-Shapiro prime number theorem

Thek-dimensional Piatetski-Shapiro prime number problem fork⩾3 is studied. Let π(x ₁ c ₁,⋯,c _k ) denote the number of primesp withp⩽x, , where 1<c ₁<⋯<c _k are fixed constants. It is proved that π(x;c ₁,⋯,c _k ) has an asymptotic formula ifc ₁ ⁻¹ +⋯+c _k ⁻¹ >k−k/(4k ²+2). Project supported by the National Natural Science Foundation of China (Grant No. 19801021) and the Natural Science Foundation of Shandong Province (Grant No.Q98A02110).     

Optimal broadcast on parallel locality models

In this paper matching upper and lower bounds for broadcast on general purpose parallel computation models that exploit network locality are proven. These models try to capture both the general purpose properties of models like the PRAM or BSP on the one hand, and to exploit network locality of special purpose models like meshes, hypercubes, etc., on the other hand. They do so by charging a cost l(|i−j|) for a communication between processors i and j, where l is a suitably chosen latency function.An upper bound T(p)=∑_i=0^loglogp2ⁱ·l(p^1/2i) on the runtime of a broadcast on a p processor H-PRAM is given, for an arbitrary latency function l(k).The main contribution of the paper is a matching lower bound, holding for all latency functions in the range from l(k)=Ω(logk/loglogk) to l(k)=O(log²k). This is not a severe restriction since for latency functions l(k)=O(logk/log¹⁺log(k)) with arbitrary >0, the runtime of the algorithm matches the trivial lower bound Ω(logp) and for l(k)=Θ(log¹⁺k) or l(k)=Θ(k), the runtime matches the other trivial lower bound Ω(l(p)). Both upper and lower bounds apply for other parallel locality models like Y-PRAM, D-BSP and E-BSP, too.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

An optimal version of an inequality involving the third symmetric means

Let (GA) _n ^[k](a), A _n (a), G _n (a) be the third symmetric mean of k degree, the arithmetic and geometric means of a ₁, …, a _n (a _i > 0, i = 1, …, n), respectively. By means of descending dimension method, we prove that the maximum of p is k−1/n−1 and the minimum of q is n/n−1(k−1/k) ^k/n so that the inequalities {fx505-1} hold.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Linear Point Sets and Rédei Type k-blocking Sets in PG(n, q)

In this paper, k-blocking sets in PG(n, q), being of Rédei type, are investigated. A standard method to construct Rédei type k-blocking sets in PG(n, q) is to construct a cone having as base a Rédei type k-blocking set in a subspace of PG(n, q). But also other Rédei type k-blocking sets in PG(n, q), which are not cones, exist. We give in this article a condition on the parameters of a Rédei type k-blocking set of PG(n, q = p ^h ), p a prime power, which guarantees that the Rédei type k-blocking set is a cone. This condition is sharp. We also show that small Rédei type k-blocking sets are linear.