Upper bounds for prime <Emphasis Type="Italic">k</Emphasis>-tuples of size log <Emphasis Type="Italic">N</Emphasis> and oscillations

We prove the estimate for the number E_k(N) of k-tuples (n + a₁,..., n + a_k) of primes not exceeding N, for k of size c₁ log N and N sufficiently large. A bound of this strength was previously known in the special case < only, (Vaughan, 1973). For general a_i this is an improvement upon the work of Hofmann and Wolke (1996). The number of prime tuples of this size has considerable oscillations, when varying the prime pattern. Received: 20 December 2002     

Sur un problème de Rényi

Let (n) be the number of all prime divisors ofn and (n) the number of distinct prime divisors ofn. We definev _q (x)=|{nx(n)–(n)=q}|. In this paper, we give an asymptotic development ofv _q (x); this improves on previous results.

     

On the distribution of square-full and cube-full numbers

There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN _k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN _k,1(x+h)–N_k,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18.     

The minimum independence number for designs

Fort=2,3 andk2t–1 we prove the existence oft–(n,k,) designs with independence numberC _,k n ^{(k–t)/(k–1)} (ln n) ^1/(k–1) . This is, up to the constant factor, the best possible.Some other related results are considered.Supported by NSF Grant DMS-9011850     

On almost prime k-tuples

Let k?2 and ai,bi(1?i?k) be integers such that ai>0 and _∏1?i<j?k(aibj−ajbi)≠0. Let Ω(m) denote the total number of prime factors of m. Suppose has no fixed prime divisors. Results of the form where rk is asymptotic to klogk have been obtained by using sieve methods, in particular weighted sieves. In this paper, we use another kind of weighted sieve due to Selberg to obtain improved admissible values for rk.     

Beurling primes with large oscillation

A Beurling generalized number system is constructed having integer counting function N_B(x) = κx +O(x^θ) with κ>0 and 1/2 <θ <1, whose prime counting function satisfies the oscillation estimate π_B(x) =li(x) + Ω(xexp(-c)), and whose zeta function has infinitely many zeros on the curve σ=1−a/logt, t≥2, and no zero to the right of this curve, where a is chosen so that a>(4/e)(1−θ). The construction uses elements of classical analytic number theory and probability. The author was supported in part by NSF grants DMS-0070720 and DMS-0244660. The author was supported in part by NSF grant DMS-0244660.     

<Emphasis Type="Italic">q</Emphasis>-Fibonacci Polynomials and the Rogers-Ramanujan Identities

We derive some formulas for the Carlitz q-Fibonacci polynomials F_n(t) which reduce to the finite version of the Rogers-Ramanujan identities obtained by I. Schur for t = 1. Our starting point is a representation of the q-Fibonacci polynomials as the weight of certain lattice paths in contained in a strip along the x-axis. We give an elementary combinatorial proof by using only the principle of inclusion-exclusion and some standard facts from q-analysis.     

On the Function w( x)=|{1= s= k : x= a s (mod n s)}|

For a finite system of arithmetic sequences the covering function is w(x) = |{1 s k : x a_s (mod n_s)}|. Using equalities involving roots of unity we characterize those systems with a fixed covering function w(x). From the characterization we reveal some connections between a period n₀ of w(x) and the moduli n₁, . . . , n_k in such a system A. Here are three central results: (a) For each r=0,1, . . .,n_k/(n₀,n_k)–1 there exists a Jc{1, . . . , k–1} such that . (b) If n₁ ···n_k–l <n_k–l+1 =···=n_k (0 < l < k), then for any positive integer r < n_k/n_k–l with r 0 (mod n_k/(n₀,n_k)), the binomial coefficient can be written as the sum of some (not necessarily distinct) prime divisors of n_k. (c) max_(xw(x) can be written in the form where m₁, . . .,m_k are positive integers.The research is supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher Education Institutions of MOE, and the National Natural Science Foundation of P. R. China.     

Divisibility properties of generalized Laguerre polynomials

In this paper we give effective upper bounds for the degree k of divisors (over ?) of generalized Laguerre polynomials L^α_n(x), i.e. of for α = −tn − s − 1 and α = tn + s with t,s ∈ ?, t = O(log k), s = O(k log k) and k sufficiently large.     

Exponential-cosine operator-valued functional equation in the strong operator topology

LetX be a Banach Space and letB(X) denote the family of bounded linear operators onX. LetR ⁺ = [0, ). A one parameter family of operators {S(t);t R ⁺},S:R ⁺ B(X), is called exponential-cosine operator function ifS(O) =I andS(s +t) – 2S(s)S(t) = (S(2s) – 2S ²(s))S(t –s), for alls, t R ⁺,s t. Let ,fD(A), and ,fD(B). It is shown that for a strongly continuous exponential-cosine operator {S(t)},fD(A ²) implies ₀ ^t (t –u(S(u)fduD(B) and B ₀ ^t (t –u)S(u)fdu =S(t)f –f +tAf – 2A ₀ ^t S(u)fdu + 2A ² ₀ ^t (t –u)S(u)fdu.D(B) is seen to be dense inD(A ²). Some regularity properties ofS(t) have also been obtained.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,P _k withP _i joinings _i tot _i , 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds . We show here thatk(G)22k will do.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

Difference sets and inverting the difference operator

For a setA of non-negative numbers, letD(A) (the difference set ofA) be the set of nonnegative differences of elements ofA, and letD ^k be thek-fold iteration ofD. We show that for everyk, almost every set of non-negative integers containing 0 arises asD ^k (A) for someA. We also give sufficient conditions for a setA to be the unique setX such that 0X andD ^k (X)=D ^k (A). We show that for eachm there is a setA such thatD(X)=D(A) has exactly 2 ^m solutionsX with 0X.This work was supported by grants DMS 92-02833 and DMS 91-23478 from the National Science Foundation. The first author acknowledges the support of the Hungarian National Science Foundation under grants, OTKA 4269, and OTKA 016389, and the National Security Agency (grant No. MDA904-95-H-1045).Lee A. Rubel died March 25, 1995. He is very much missed by his coauthors.     

The k-orbit reconstruction and the orbit algebra

Let (G, W) be a permutation group on a finite set W = {w ₁,..., w _n}. We consider the natural action of G on the set of all subsets of W. Let h ₀, h ₁,..., h _N be the orbits of this action. For each i, 1 i N, there exists k, 1 k n, such that h _i is a set of k-element subsets of W. In this case h _i is called a symmetrized k-orbit of the group (G, W) or simply a k-orbit. With a k-orbit h _i we associate a multiset H(h _i ) = % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykJeoaaa!3690!\[\langle \]h _i ⁽¹⁾, h _i ⁽²⁾,..., h _i ^(k)% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkJepaaa!36A1!\[\rangle \] of its (k – 1)-suborbits. Orbits h _i and h _j are called equivalent if H(h _i ) = H(h _j ). An orbit is reconstructible if it is equivalent to itself only. The paper concerns the k-orbit reconstruction problem and its connections with different problems in combinatorics. The technique developed is based on the notion of orbit and co-orbit algebras associated with a given permutation group (G, W).     

Lower Bounds For Multidimensional Zero Sums

Let f(n, d) denote the least integer such that any choice of f(n, d) elements in contains a subset of size n whose sum is zero. Harborth proved that (n-1)2 ^d +1 f(n,d) (n-1)n ^d +1. The upper bound was improved by Alon and Dubiner to c _d n. It is known that f(n-1) = 2n-1 and Reiher proved that f(n-2) = 4n-3. Only for n = 3 it was known that f(n,d) > (n-1)2 ^d +1, so that it seemed possible that for a fixed dimension, but a sufficiently large prime p, the lower bound might determine the true value of f(p,d). In this note we show that this is not the case. In fact, for all odd n 3 and d 3 we show that .     

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

Newman's phenomenon for generalized Thue-Morse sequences

Let t_j=(-1)^s(j) be the Thue-Morse sequence with s(j) denoting the sum of the digits in the binary expansion of j. A well-known result of Newman [On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc. 21 (1969) 719-721] says that t₀+t₃+t₆+?+t_3k>0 for all k?0.In the first part of the paper we show that t₁+t₄+t₇+?+t_3k+1<0 and t₂+t₅+t₈+?+t_3k+2?0 for k?0, where equality is characterized by means of an automaton. This sharpens results given by Dumont [Discrépance des progressions arithmétiques dans la suite de Morse, C. R. Acad. Sci. Paris Sér. I Math. 297 (1983) 145-148]. In the second part we study more general settings. For a,g?2 let ω_a=exp(2πi/a) and , where s_g(j) denotes the sum of digits in the g-ary digit expansion of j. We observe trivial Newman-like phenomena whenever a|(g-1). Furthermore, we show that the case a=2 inherits many Newman-like phenomena for every even g?2 and large classes of arithmetic progressions of indices. This, in particular, extends results by Drmota and Ska?ba [Rarified sums of the Thue-Morse sequence, Trans. Amer. Math. Soc. 352 (2000) 609-642] to the general g-case.     

Supersequences, rearrangements of sequences, and the spectrum of bases in additive number theory

The set of nonnegative integers is an asymptotic basis of order h if every sufficiently large integer can be represented as the sum of h elements of A. If an∼αnh for some real number α>0, then α is called an additive eigenvalue of order h. The additive spectrum of order h is the set N(h) consisting of all additive eigenvalues of order h. It is proved that there is a positive number ηh?1/h! such that N(h)=(0,ηh) or N(h)=(0,ηh]. The proof uses results about the construction of supersequences of sequences with prescribed asymptotic growth, and also about the asymptotics of rearrangements of infinite sequences. For example, it is proved that there does not exist a strictly increasing sequence of integers such that bn∼n² and B contains a subsequence such that bnk∼k³.     

On generalized gamma functions related to the Laurent coefficients of the Riemann zeta function

Summary We study a class of generalized gamma functions _k (z) which relate to the generalized Euler constants _k (basically the Laurent coefficients of(s)) as (z) does to the Euler constant. A new series expansion for _k is derived, and the constant term in the asymptotic expansion for log _k (z) is studied in detail. These and related constants are numerically computed for 1 k 15.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.