Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss     

Existence principles for higher-order nonlocal boundary-value problems and their applications to singular Sturm-Liouville problems

We present existence principles for the nonlocal boundary-value problem (φ(u^(p−1)))′=g(t,u,...,u^(p−1), α_k(u)=0, 1≤k≤p−1, where p ≥ 2, π: ℝ → ℝ is an increasing and odd homeomorphism, g is a Carathéodory function that is either regular or has singularities in its space variables, and α _k: C ^p−1[0, T] → ℝ is a continuous functional. An application of the existence principles to singular Sturm-Liouville problems (−1)ⁿ(φ(u⁽²ⁿ⁻⁾))′=f(t,u,...,u⁽²ⁿ⁻¹⁾), u^(2k)(0)=0, α_ku^(2k)(T)+b_ku^(2k=1)(T)=0, 0≤k≤n−1, is given. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 2, pp. 240–259, February, 2008.     

A Five Color Zero-Sum Generalization

Let g_zs(m, 2k) (g_zs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , g_zs(m, 2k) by (the integers from 1 to g_zs(m, 2k+1) by ) there exist integers such that 1. there exists j_x such that Δ(x_i) ∈ for each i and ∑_i=1^m Δ(x_i) = 0 mod m (or Δ(x_i)=∞ for each i); 2. there exists j_y such that Δ(y_i) ∈ for each i and ∑_i=1^m Δ(y_i) = 0 mod m (or Δ(y_i)=∞ for each i); and 1. 2(x_m−x₁)≤y_m−x₁. In this note we show g_zs(m, 2)=5m−4 for m≥2, g_zs(m, 3)=7m+−6 for m≥4, g_zs(m, 4)=10m−9 for m≥3, and g_zs(m, 5)=13m−2 for m≥2. Supported by NSF grant DMS 0097317     

A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

Estimates on binomial sums of partition functions

Let p(n) denote the partition function and define where p(0)= 1. We prove that p(n,k) is unimodal and satisfies for fixed n≥ 1 and all 1≤k≤n. This result has an interesting application: the minimal dimension of a faithful module for a k-step nilpotent Lie algebra of dimension n is bounded by p(n,k) and hence by , independently of k. So far only the bound n ^{n −1} was known. We will also prove that for n≥ 1 and . Received: 17 December 1999     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Some notes on the adams spectral sequence

In the beginning of 1980's Cohen, R. proved thath0b(1k)=B(1,k)=B(1,k)⊗ζ₁ survives toE _∞ in the Adams spectral sequence. Later, Cohen, R. and Goerss, P. proved that is a permanent cycle. And they are represented by ζ _k ,ηj respectively. Here the author proved: Theorem 2: Let 2≤s≤p−1,j≥3, then β _s η _j ≠0. Theorem 3: For 2≤s≤p−1,k≥2, β _s ζ _k ≠0 in the stable homotopy groups of spheres. As a remark, we get in . Supported by Doctoral Program Fundation.     

On the Problem of Parameter Estimation in Exponential Sums

Let I≥1 be an integer, ω ₀=0<ω ₁<⋯<ω _I ≤π, and for j=0,…,I, a _j ∈ℂ, a_-j=[`(a_j)]a_{-j}={\overline{{a_{j}}}}, ω _−j =−ω _j , and a_j 1 0a_{j}\not=0 if j 1 0j\not=0. We consider the following problem: Given finitely many noisy samples of an exponential sum of the form

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

Total colorings of graphs of order 2n having maximum degree 2n−2

Let χ _t (G) and †(G) denote respectively the total chromatic number and maximum degree of graphG. Yap, Wang and Zhang proved in 1989 that ifG is a graph of orderp having †(G)≥p−4, then χ _t (G≤Δ(G)+2. Hilton has characterized the class of graphG of order 2n having †(G)=2n−1 such that χ _t (G=Δ(G)+2. In this paper, we characterize the class of graphsG of order 2n having †(G)=2n−2 such that χ _t (G=Δ(G)+2 Research supported by National Science Council of the Republic of China (NSC 79-0208-M009-15)     

Thed-step conjecture for polyhedra of dimensiond<6

Two functions Δ and Δ _b , of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δ _b (d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δ _b (d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δ _b are presented. This revised version was published online in November 2006 with corrections to the Cover Date.     

Minimum ideal triangulations of hyperbolic 3-manifolds

Let σ(n) be the minimum number of ideal hyperbolic tetrahedra necessary to construct a finite volumen-cusped hyperbolic 3-manifold, orientable or not. Let σ_or(n) be the corresponding number when we restrict ourselves to orientable manifolds. The correct values of σ(n) and σ_or(n) and the corresponding manifolds are given forn=1,2,3,4 and 5. We then show that 2n−1≤σ(n)≤σ_or(n)≤4n−4 forn≥5 and that σ_or(n)≥2n for alln. Both authors were supported by NSF Grants DMS-8711495, DMS-8802266 and Williams College Research Funds.     

A class of optimal linear codes of length one above the Griesmer bound

In this paper, we determine the smallest lengths of linear codes with some minimum distances. We construct a [g _q (k, d) + 1, k, d] _q code for sq ^k-1 − sq ^k-2 − q ^s  − q ² + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s with 3 ≤ s ≤ k − 2 and q ≥ s + 1. Then we get n _q (k, d) = g _q (k, d) + 1 for (k − 2)q ^k-1 − (k − 1)q ^k-2 − q ² + 1 ≤ d ≤ (k − 2)q ^k-1 − (k − 1)q ^k-2, k ≥ 6, q ≥ 2k − 3; and sq ^k-1 − sq ^k-2 − q ^s  − q + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s , s ≥ 2, k ≥ 2s + 1 and q ≥ 2s − 1. This work was partially supported by the Com²MaC-SRC/ERC program of MOST/KOSEF (grant ^# R11-1999-054) and was partially supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2005-214-C00175).     

Concerning the order of approximation of periodic continuous functions by trigonometric interpolation polynomials

Letx _kn=2θk/n,k=0,1 …n−1 (n odd positive integer). LetR _n(x) be the unique trigonometric polynomial of order 2n satisfying the interpolatory conditions:R _n(x_kn)=f(x_kn),R _n ^(j)(x_kn)=0,j=1,2,4,k=0,1…,n−1. We setw ₂(t,f) as the second modulus of continuity off(x). Then we prove that |R _n(x)-f(x)|=0(nw₂(1/nf)). We also examine the question of lower estimate of ‖R _n-f‖. This generalizes an earlier work of the author.     

On the average hyperoscillations of planted plane trees

Assume that the leaves of a planted plane tree are enumerated from left to right by 1, 2, .... Thej-ths-turn of the tree is defined to be the root of the (unique) subtree of minimal height with leavesj, j+1, ...,j+s−1. If all trees withn nodes are regarded equally likely, the average level number of thej-ths-turn tends to a finite limitα _s (j), which is of orderj ^1/2. Thej-th ”s-hyperoscillation”α ₁(j)−α _s+1(j) is given by 1/2α ₁(s)+O(j ^−1/2) and therefore tends (forj → ∞) to a constant behaving like √8/π·s ^1/2 fors → ∞. These results are obtained by setting up appropriate generating functions, which are expanded about their (algebraic) singularities nearest to the origin, so that the asymptotic formulas are consequences of the so-called Darboux-Pólyamethod.     

An optimal bound on the tail distribution of the number of recurrences of an event in product spaces

 Let X ₁ ,X ₂ ,... be independent random variables and a a positive real number. For the sake of illustration, suppose A is the event that |X _i+1 +...+X _j |≥a for some integers 0≤i<j<∞. For each k≥2 we upper-bound the probability that A occurs k or more times, i.e. that A occurs on k or more disjoint intervals, in terms of P(A), the probability that A occurs at least once. More generally, let X=(X ₁ ,X ₂ ,...)Ω=Π _{j ≥1}Ω _j be a random element in a product probability space (Ω,ℬ,P=⊗ _{j ≥1} P _j ). We are interested in events AB that are (at most contable) unions of finite-dimensional cylinders. We term such sets sequentially searchable. Let L(A) denote the (random) number of disjoint intervals (i,j] such that the value of X _(i,j] =(X _i+1 ,...,X _j ) ensures that XA. By definition, for sequentially searchable A, P(A)≡P(L(A)≥1)=P(𝒩_{−ln (P(Ac))} ≥1), where 𝒩_γ denotes a Poisson random variable with some parameter γ>0. Without further assumptions we prove that, if 0<P(A)<1, then P(L(A)≥k)<P(𝒩_{−ln (P(Ac))} ≥k) for all integers k≥2. An application to sums of independent Banach space random elements in l ^∞ is given showing how to extend our theorem to situations having dependent components. Received: 8 June 2001 / Revised version: 30 October 2002 Published online: 15 April 2003 RID="*" ID="*" Supported by NSF Grant DMS-99-72417. RID="†" ID="†" Supported by the Swedish Research Council. Mathematics Subject Classification (2000): Primary 60E15, 60G50 Key words or phrases: Tail probability inequalities – Hoffmann-Jo rgensen inequality – Poisson bounds – Number of event recurrences – Number of entrance times – Product spaces     

Un théorème sur les séries de Dirichlet

We considerk Dirichlet series a _j (n)n ^–s (1jk),k2. We suppose that for eachj the series a _j (n)n ^–s converges fors=s _j =j+it _j , and that Max j<1/(k–1). We prove that the (Dirichlet) product of these series converges uniformly on every bounded segment of the line es = (₁+...+ _k )/k+1–1/k and we estimate the rate of convergence. The number 1–1/k cannot be replaced by a smaller one.     

The Linear 2-Arboricity of Planar Graphs

 Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la ₂(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la ₂(G)≤⌈(Δ+1)/2⌉+12; (2) la ₂(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la ₂(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la ₂(G)≤⌈(Δ+1)/2⌉+1 if g≥7. Received: June 28, 2001 Final version received: May 17, 2002 Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei. The financial support provided by the Institute is greatly appreciated.     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.