Equipartition of mass distributions by hyperplanes

We consider the problem of determining the smallest dimensiond=Δ(j, k) such that, for anyj mass distributions inR ^d , there arek hyperplanes so that each orthant contains a fraction 1/2 ^k of each of the masses. The case Δ(1,2)=2 is very well known. The casek=1 is answered by the ham-sandwich theorem with Δ(j, 1)=j. By using mass distributions on the moment curve the lower bound Δ(j, k)≥j(2 ^k −1)/k is obtained. We believe this is a tight bound. However, the only general upper bound that we know is Δ(j, k)≤j2 ^k−1. We are able to prove that Δ(j, k)=⌈j(^2k−1/k⌉ for a few pairs (j, k) ((j, 2) forj=3 andj=2 ⁿ withn≥0, and (2, 3)), and obtain some nontrivial bounds in other cases. As an intermediate result of independent interest we prove a Borsuk-Ulam-type theorem on a product of balls. The motivation for this work was to determine Δ(1, 4) (the only case forj=1 in which it is not known whether Δ(1,k)=k); unfortunately the approach fails to give an answer in this case (but we can show Δ(1, 4)≤5). This research was supported by the National Science Foundation under Grant CCR-9118874.     

Disk-like Tiles Derived from Complex Bases

For each positive integer k, the radix representation of the complex numbers in the base –k+i gives rise to a lattice self-affine tile T _k in the plane, which consists of all the complex numbers that can be expressed in the form ∑ _j≥1 d _j (–k+i)^–j , where d _j ∈{0, 1, 2, ...,k ²}. We prove that T _k is homeomorphic to the closed unit disk {z∈C:∣z∣ ≤ 1} if and only if k ≠ 2. The first author is supported by Youth Project of Tianyuan Foundation (10226031) and Zhongshan University Promotion Foundation for Young Teachers (34100-1131206); the second author is supported by National Science Foundation (10041005) and Guangdong Province Science Foundation (011221)     

On a Distance-Regular Graph of Even Height with ke = kf

 Let Γ be a distance-regular graph of diameter d. The height of Γ is defined by h = max{j∣p ^d _d,j ≠ 0}. Let e, f be positive integers such that e < f and e + f≤d, and let d = 2e + s for some positive integer s. We show that if k _e = k _f , h≤ 2s and the height h is even, then Γ is an antipodal 2-cover. Received: October 23, 1997 Final version received: July 31, 2000     

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.     

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     

Precise asymptotics in self-normalized sums of iterated logarithm for multidimensionally indexed random variables

In the case of Zd (d ≥ 2)-the positive d-dimensional lattice points with partial ordering ≤, {Xk,k ∈ Zd } i.i.d. random variables with mean 0, Sn = ∑k≤nXk and Vn2 = ∑j≤nX2j, the precise asymptotics for ∑n1/|n|(log|n|)dP(|Sn/vn|≥ ε√loglog|n|) and ∑n(logn|)δ/|n|(log|n|)d-1 P(|Sn/Vn| ≥ ε√log n), as ε ↘ 0, is established.     

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).     

Dependent percolation in two dimensions

For a natural number k, define an oriented site percolation on ℤ² as follows. Let x _i , y _j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ² closed if x _i = y _j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i ₀, j ₀)(i ₁, j ₁) · · · such that 0 = i ₀≤i ₁≤· · ·, 0 = j ₀≤j ₁≤· · ·, and each site (i _n , j _n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x _i ) and (y _j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000     

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.     

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.     

The size of the shadow boundary projection

Among all embedded closed manifoldsM ^d ⊂ ℝ ^d+1 with positive exterior curvature ≤k the ratio between the (d − 1)-Hausdorff measure of the shadow boundary projection and the volume ofM ^d is maximized by the sphere of radius 1/k.     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

Analogues of Horn’s theorem for finite unions of starshaped sets in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

Fix k, d, 1 ≤ k ≤ d + 1. Let $ \mathcal{F} $ \mathcal{F} be a nonempty, finite family of closed sets in ℝ ^d , and let L be a (d − k + 1)-dimensional flat in ℝ ^d . The following results hold for the set T ≡ ∪{F: F in $ \mathcal{F} $ \mathcal{F} }. Assume that, for every k (not necessarily distinct) members F ₁, …, F _k of $ \mathcal{F} $ \mathcal{F} ,∪{F _i : 1 ≤ i ≤ k} is starshaped and the corresponding kernel contains a translate of L. Then T is starshaped, and its kernel also contains a translate of L.     

Convergence of the iteration of Halley’s family and Smale operator class in Banach space

Smale operator classes of any order for nonlinear operators in Banach space are introduced. For an operatorf in Smale operator class of orderk, a proper condition for the convergence and the exact estimations error for the iteration of Halley’s family {H _j,k ⁿ } _n=0 ^∞ (1≤j≤k) are given. This Halley’s family is a higher order explicit generalization of Newton iteration. Project supported by China State Major Key Project for Basic Research and Zhejiang Provincial Natrural Science Foundation.     

Dérivé convexe d’une loi de probabilité et lois stables. Application a un problème d’isomorphisme

The “convex derived set” of a symmetric probability lawF on the real line is defined as the set of limits of laws ∗ _j−1/k ⁿ F(t _j ⁿ η), inf 1≤j≤k _n t _j ⁿ →∞ ifn→∞ and the stable laws it contains are exhibited. A new criterion of stochastic compacity of the set of the powers of a probability law is established. Finally, an isomorphism theorem between somel ^p andL ⁰ spaces is given.

---

---

Laboratoire associé au C.N.R.S. n^o 224 “Processus stochastiques et applications”.     

Tiling Groupoids and Bratteli Diagrams II: Structure of the Orbit Equivalence Relation

In this second paper, we study the case of substitution tilings of \mathbb R^d{{\mathbb R}^d} . The substitution on tiles induces substitutions on the faces of the tiles of all dimensions j = 0, . . . , d − 1. We reconstruct the tiling’s equivalence relation in a purely combinatorial way using the AF-relations given by the lower dimensional substitutions. We define a Bratteli multi-diagram B{{\mathcal B}} which is made of the Bratteli diagrams B^j, j=0, ?d{{\mathcal B}^j, j=0, \ldots d} , of all those substitutions. The set of infinite paths in B^d{{\mathcal B}^d} is identified with the canonical transversal Ξ of the tiling. Any such path has a “border”, which is a set of tails in B^j{{\mathcal B}^j} for some j ≤ d, and this corresponds to a natural notion of border for its associated tiling. We define an étale equivalence relation R_B{{\mathcal R}_{\mathcal B}} on B{{\mathcal B}} by saying that two infinite paths are equivalent if they have borders which are tail equivalent in B^j{{\mathcal B}^j} for some j ≤ d. We show that R_B{{\mathcal R}_{\mathcal B}} is homeomorphic to the tiling’s equivalence relation R_X{{\mathcal R}_\Xi} .     

The genus of space curves

LetC be a curve contained in ℙ _k ³ (k of any characteristic), which is locally Cohen-Macaulay, not contained in a plane and of degreed. We prove thatp _a (C)≤≤((d−2)(d−3))/2. Moreover we show existence of curves with anyd, p _a satisfying this inequality and we characterize those curves for which equality holds.

---

Sunto Si dimostra che seC⊃ℙ _k ³ (k di caratteristica qualunque) é una curva, non piana, localmente Cohen-Macaulay, di gradod, allorap _a (C)≤((d−2)(d−3))/2. Si mostra che questa limitazione è ottimale, e si classificano le curve di genere aritmetico massimale.

     

Higher dimensional extensions of substitutions and their dual maps

Given a substitution σ ond letters, we define itsk-dimensional extension,E _k (σ), for 0≤k≤d. Thek-dimensional extension acts on the set ofk-dimensional faces of unit cubes inR ^d with integer vertices. The extensions of a substitution satisfy a commutation relation with the natural boundary operator: the boundary of the image is the image of the boundary. We say that a substitution is unimodular (resp. hyperbolic) if the matrix associated to the substitution by abelianization is unimodular (resp. hyperbolic). In the case where the substitution is unimodular, we also define dual substitutions which satisfy a similar coboundary condition. We use these constructions to build self-similar sets on the expanding and contracting space for an hyperbolic substitution.     

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.     

Construction of a class of multivariate compactly supported wavelet bases for L 2(? d )

In this paper, for a given d×d expansive matrix M with |detM| = 2, we investigate the compactly supported M-wavelets for L ²(ℝ ^d ). Starting with a pair of compactly supported refinable functions ϕ and [(j)\tilde]\tilde \varphi satisfying a mild condition, we obtain an explicit construction of a compactly supported wavelet ψ such that {2 ^j/2 ψ(M ^j · −k): j ∈ ℤ, k ∈ ℤd} forms a Riesz basis for L ²(ℝ ^d ). The (anti-)symmetry of such ψ is studied, and some examples are also provided.