Optimal inverse Littlewood–Offord theorems

Let ηi, i=1,…,n, be iid Bernoulli random variables, taking values ±1 with probability . Given a multiset V of n integers v₁,…,vn, we define the concentration probability as A classical result of Littlewood–Offord and Erd?s from the 1940s asserts that, if the vi are non-zero, then ρ(V) is O(n−1/2). Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V.About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ(V) is relatively large.In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sárközy and Szemerédi and Halász.The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices.All results extend to the general case when V is a subset of an abelian torsion-free group, and ηi are independent variables satisfying some weak conditions.     

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

LetN _r (x) be the number ofr-full integers x and let _r (x) be the error term in the asymptotic formula forN _r (x). Under Riemann's hypothesis, we prove the estimates ₂(x)x^1/7+, ₃(x)x^97/804+(>0), which improve those of Cao and Nowak. We also investigate the distribution ofr-full andl-free numbers in short intervals (r=2,3). Our results sharpen Krätzel's estimates.     

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.     

On the Mean Value of the Index of Composition of an Integer

For each integer n 2, let be the index of composition of n, where . For convenience, we write (1)=(1)=1. We obtain sharp estimates for and , as well as for and . Finally we study the sum of running over shifted primes.Research supported in part by a grant from NSERC.Research supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA.     

Exact Convergence Rate for the Distributions of GI/M/c/K Queue as K Tends to Infinity

We obtain the exact convergence rate of the stationary distribution ^(K) of the embedded Markov chain in GI/M/c/K queue to the stationary distribution of the embedded Markov chain in GI/M/c queue as K. Similar result for the time-stationary distributions of queue size is also included. These generalize Choi and Kim's results of the case c=1 by nontrivial ways. Our results also strengthen the Simonot's results [5].     

Uniform-fast-gerade Funktionen mit vorgegebenen Werten,II

For a given sequence n₁ < n₂ < ... of integers satisfying and for a given convergent sequence of complex numbers {a_j}, it was shown in [4] that there is a uniformly-almost-even function assuming the values f(n_j) = a_j. For the proof, Gelfands theory of commutative Banach algebras and Tietzes extension theorem were used. In [3] an incomplete proof [by elementary means] of this result was given.¹⁾The aim of this note is to give some results which can be proved by the method from [3].¹⁾The first-named author is grateful to the second author for pointing out a missing case in the above-mentioned proof.Received: 7 November 2002     

Arithmetical identities of the Brauer-Rademacher type

Summary LetA be a regular arithmetical convolution andk a positive integer. LetA _k (r) = {d: d ^k A(r ^k )}, and letf A _k g denote the convolution of arithmetical functionsf andg with respect toA _k . A pair (f, g) of arithmetical functions is calledadmissible if(f A _k g)(m) 0 for allm and if the functions satisfy an arithmetical functional equation which generalizes the Brauer—Rademacher identity. Necessary and sufficient conditions are found for a pair (f, g) of multiplicative functions to be admissible, and it follows that, if(f A _k g)(m) 0 f(m) for allm, then (f, g) is admissible if and only if itsdual pair (f A _k g, g ^–1 ) is admissible.Iff andg ^–1 areA _k -multiplicative (a condition stronger than being multiplicative), and(f A _k g)(m) 0 for allm, then (f, g) is admissible, calledCohen admissible. Its dual pair is calledSubbarao admissible. If (f A _k g) ^–1 (m) 0 itsinverse pair (g ^–1 , f ^–1 ) is also Cohen admissible.Ifg is a multiplicative function then there exists a multiplicative functionf such that the pair (f, g) is admissible if and only if for everyA _k -primitive prime powerp ⁱ either (i)g(p ⁱ ) 0 or (ii)g(p ) = 0 for allp havingA _k -type equal tot. There is a similar kind of characterization of the multiplicative functions which are first components of admissible pairs of multiplicative functions. IfA _k is not the unitary convolution, then there exist multiplicative functionsg which satisfy (i) and are such that neitherg norg ^–1 isA _k -multiplicative: hence there exist admissible pairs of multiplicative functions which are neither Cohen admissible nor Subbarao admissible.An arithmetical functionf is said to be anA _k -totient if there areA _k -multiplicative functionsf _T andf _V such thatf = f _T A _k f _V ^-1 Iff andg areA _k -totients with(f A _k g)(m) 0 for allm, and iff _V = g _T , then the pair (f, g) is admissible. The class of such admissible pairs includes many pairs which are neither Cohen admissible nor Subbarao admissible. If (f, g) is a pair in this class, and iff(m), (f A _k g) ^–1 (m), g ^–1 (m),f ^–1 (m) andg(m) are all nonzero for allm, then its dual, its inverse, the dual of its inverse, the inverse of its dual and the inverse of the dual of its inverse are also admissible, and in many cases these six pairs are distinct.A number of related results, and many examples, are given.     

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.     

Increasing Self-Described Sequences

We proceed with our study of increasing self-described sequences F, beginning with 1 and defined by a functional equation In [1] we exhibited the simple solution f (t)=Ct, for some (0,1), of the associated functional-differential equation and we proved that provided <2/(2+d()), where we have the asymtotic equivalence F(m)~ Cm.In the present paper we show that this last result is optimal, in the sense that the self-described sequence defined by |F^–1(m)|=F(m)², that is

Some greedyt-intersecting families of finite sequences

Letn, s ₁,s ₂, ... ands _n be positive integers. Assume is an integer for eachi}. For , , and , denotes _p (a)={j|1jn,a _j p}, , and . is called anI _t ^p -intersecting family if, for any a,b ,a _i b _i =min(a _i ,b _i )p for at leastt i's. is called a greedyI _t ^P -intersecting family if is anI _t ^p -intersecting family andW _p (A)W _p (B+A ^c ) for anyAS _p ( ) and any with |B|=t–1.In this paper, we obtain a sharp upper bound of | | for greedyI _t ^p -intersecting families in for the case 2ps _i (1in) ands ₁>s ₂>...>s _n .This project is partially supported by the National Natural Science Foundation of China (No.19401008) and by Postdoctoral Science Foundation of China.     

2-universal -lattices over real quadratic fields

Let be a real quadratic field with m a square-free positive rational integer, and be the ring of integers in F. An -lattice L on a totally positive definite quadratic space V over F is called r-universal if L represents all totally positive definite -lattices l with rank r over . We prove that there exists no 2-universal -lattice over F with rank less than 6, and there exists a 2-universal -lattice over F with rank 6 if and only if m=2, 5. Moreover there exists only one 2-universal -lattice with rank 6, up to isometry, over .     

A note on the Ramanujan τ-function

Let τ(n) be the Ramanujan τ-function, x ≥ 10 be an integer parameter. We prove that

The GHS inequality and the Riemann hypothesis

LetV(t) be the even function on (–, ) which is related to the Riemann xi-function by (x/2)=4 _– exp(ixt–V(t))dt. In a proof of certain moment inequalities which are necessary for the validity of the Riemann Hypothesis, it was previously shown thatV'(t)/t is increasing on (0, ). We prove a stronger property which is related to the GHS inequality of statistical mechanics, namely thatV' is convex on [0, ). The possible relevance of the convexity ofV' to the Riemann Hypothesis is discussed.Communicated by Richard Varga.     

On the isotopy of Legendrian knots

Let ₀ and ₁ be Legendrian knots which are isotopic as usual knots, and which have the same obvious invariants rot and link. It seems to be an open question whether ₀ and ₁ are isotopic as Legendrian knots. In the paper we give a positive answer to this question for the (rather restricted) class of Legendrian knots with nonintersecting fronts.     

On the irrationality of factorial series III

In this paper we derive some irrationality and linear independence results for series of the form where is either a non-negative integer sequence with υ_n = o(log n/log log n) or a non-decreasing integer sequence with .     

Asymptotic Behavior of Loss Probability in GI/M/1/K Queue as K Tends to Infinity

We obtain an asymptotic behavior of the loss probability for the GI/M/1/K queue as K for cases of <1, >1 and =1.     

Tower of the maximal abelian extensions of local fields and its application

In this paper, we study the algebraic structure of principal units in the tower of the maximal abelian extensions of local fields of characteristic zero and the corresponding Galois groups at each level. As an application, we show the finiteness result for the number of coverings with a given degree of the maximal abelian extension of a local field in characteristic zero. The number of p-coverings for is computed explicitly.     

Spectral invariance,ellipticity, and the Fredholm property for pseudodifferential operators on weighted Sobolev spaces

The pseudodifferential operators with symbols in the Grushin classes \~S _inf0 ^sup, , 0 < 1, of slowly varying symbols are shown to form spectrally invariant unital Frécher-*-algebras (*-algebras) in L(L ²(R ⁿ )) and in L(H ^st ) for weighted Sobolev spaces H _inf ^supst defined via a weight d function . In all cases, the Fredholm property of an operator can be characterized by uniform ellipticity of the symbol. This gives a converse to theorems of Grushin and Kumano-Ta-Taniguchi. Both, the spectrum and the Fredholm spectrum of an operator turn out to be independent of the choices of s, t and .The characterization of the Fredholm property by uniform ellipticity leads to an index theorem for the Fredholm operators in these classes, extending results of Fedosov and Hörmander.     

Zero cycles on conic fibrations and a conjecture of Bloch

Let X be a smooth projective surface over a number field k. Let (CH₀(X)) denote the Chow group of zero-cyles modulo rational equivalence on X. Let CH₀(X) be the subgroup of CH ₀(X) consisting of classes which vanish when going over to an arbitrary completion of k. Bloch put forward a conjecture asserting that this group is isomorphic to the Tate-Shafarevich group of a certain Galois module atttached to X. In this paper, we disprove this general conjecture. We produce a conic bundle X over an elliptic curve, for which the group (CH₀(X) is not zero, but the Galois-theoretic Tate-Shafarevich group vanishes.