Metric trees of generalized roundness one

Every finite metric tree has generalized roundness strictly greater than one. On the other hand, some countable metric trees have generalized roundness precisely one. The purpose of this paper is to identify several large classes of countable metric trees that have generalized roundness precisely one. At the outset we consider spherically symmetric trees endowed with the usual path metric (SSTs). Using a simple geometric argument we show how to determine reasonable upper bounds on the generalized roundness of finite SSTs that depend only on the downward degree sequence of the tree in question. By considering limits, it follows that if the downward degree sequence (d ₀, d ₁, d ₂, . . .) of an SST (T, ρ) satisfies ${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}}${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}} , then (T, ρ) has generalized roundness one. In particular, all complete n-ary trees of depth ∞ (n ≥ 2), all k-regular trees (k ≥ 3) and all inductive limits of Cantor trees are seen to have generalized roundness one. The remainder of the paper deals with two classes of countable metric trees of generalized roundness one whose members are not, in general, spherically symmetric. The first such class of trees are merely required to spread out at a sufficient rate (with a restriction on the number of leaves) and the second such class of trees resemble infinite combs. It remains an intriguing problem to completely classify countable metric trees of generalized roundness one.     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

关于度量及纲函数的Hausdorff测度的两个反例

本文研究了度量空间中Hausdorff测度与度量及纲函数的关系.利用拓扑学及Hausdorff测度论中一些性质,构造了两反例来说明存在不等价纲函数g,h和某一紧度量空间(ρ,X),使得Hρ,g与Hρ,h对此紧度量空间等价等问题.这些反例有助于从另一个角度理解文胜友、文志英[4]中主要结果.     

The Semilinear Wave Equation on Asymptotically Euclidean Manifolds

We consider the quadratically semilinear wave equation on (? ^d , 𝔤), d ≥ 3. The metric 𝔤 is non-trapping and approaches the Euclidean metric like ?x?^?ρ. Using Mourre estimates and the Kato theory of smoothness, we obtain, for ρ > 0, a Keel–Smith–Sogge type inequality for the linear equation. Thanks to this estimate, we prove long time existence for the nonlinear problem with small initial data for ρ ≥ 1. Long time existence means that, for all n > 0, the life time of the solution is a least δ^?n , where δ is the size of the initial data in some appropriate Sobolev space. Moreover, for d ≥ 4 and ρ > 1, we obtain global existence for small data.     

The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ_∞ ^d , the infinite graph with vertex set ℤ ^d and an edge (u, v) whenever ∥u − v∥_∞ = 1. The growth rate of G, denoted ρ _G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ^ρ vertices. By simple volume arguments, dim(G) = Ω(ρ _G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ _G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ _G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ _G log ρ _G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ _G log ρ _G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ _G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.     

Correlation structure of intermittency in the parabolic Anderson model

Consider the Cauchy problem ∂u(x, t)/∂t = ℋu(x, t) (x∈ℤ^d, t≥ 0) with initial condition u(x, 0) ≡ 1 and with ℋ the Anderson Hamiltonian ℋ = κΔ + ξ. Here Δ is the discrete Laplacian, κ∈ (0, ∞) is a diffusion constant, and ξ = {ξ(x): x∈ℤ ^d } is an i.i.d.random field taking values in ℝ. G?rtner and Molchanov (1990) have shown that if the law of ξ(0) is nondegenerate, then the solution u is asymptotically intermittent. In the present paper we study the structure of the intermittent peaks for the special case where the law of ξ(0) is (in the vicinity of) the double exponential Prob(ξ(0) > s) = exp[−e ^{s /θ}] (s∈ℝ). Here θ∈ (0, ∞) is a parameter that can be thought of as measuring the degree of disorder in the ξ-field. Our main result is that, for fixed x, y∈ℤ ^d and t→∈, the correlation coefficient of u(x, t) and u(y, t) converges to ∥w _ρ∥⁻² _ℓ2Σ_{z ∈ℤd} w _ρ(x+z)w _ρ(y+z). In this expression, ρ = θ/κ while w _ρ:ℤ^d→ℝ⁺ is given by w _ρ = (v _ρ)^{⊗ d} with v _ρ: ℤ→ℝ⁺ the unique centered ground state (i.e., the solution in ℓ²(ℤ) with minimal l ²-norm) of the 1-dimensional nonlinear equation Δv + 2ρv log v = 0. The uniqueness of the ground state is actually proved only for large ρ, but is conjectured to hold for any ρ∈ (0, ∞). empty It turns out that if the right tail of the law of ξ(0) is thicker (or thinner) than the double exponential, then the correlation coefficient of u(x, t) and u(y, t) converges to δ _{x, y} (resp.the constant function 1). Thus, the double exponential family is the critical class exhibiting a nondegenerate correlation structure. Received: 5 March 1997 / Revised version: 21 September 1998     

The Wave Front Set of the Wigner Distribution and Instantaneous Frequency

We prove a formula expressing the gradient of the phase function of a function f:ℝ ^d ↦ℂ as a normalized first frequency moment of the Wigner distribution for fixed time. The formula holds when f is the Fourier transform of a distribution of compact support, or when f belongs to a Sobolev space H ^d/2+1+ε (ℝ ^d ) where ε>0. The restriction of the Wigner distribution to fixed time is well defined provided a certain condition on its wave front set is satisfied. Therefore we first need to study the wave front set of the Wigner distribution of a tempered distribution.     

The relative trace formula for groups with involution

A theorem of Bourgain states that the harmonic measure for a domain in ℝ ^d is supported on a set of Hausdorff dimension strictly less thand [2]. We apply Bourgain’s method to the discrete case, i.e., to the distribution of the first entrance point of a random walk into a subset of ℤ ^d ,d≥2. By refining the argument, we prove that for allβ>0 there existsρ(d,β)<d andN(d,β), such that for anyn>N(d,β), anyx ∈ ℤ ^d , and anyA ⊂ {1,…,n} ^d •{y∈ℤ whereν _A,x (y) denotes the probability thaty is the first entrance point of the simple random walk starting atx intoA. Furthermore,ρ must converge tod asβ → ∞. Supported by Swiss NF grant 20-55648.98.     

Nonlinear stochastic wave and heat equations

We study nonlinear wave and heat equations on ℝ ^d driven by a spatially homogeneous Wiener process. For the wave equation we consider the cases of d = 1, 2, 3. The heat equation is considered on an arbitrary ℝ ^d -space. We give necessary and sufficient conditions for the existence of a function-valued solution in terms of the covariance kernel of the noise. Received: 1 April 1998 / Revised version: 23 June 1999 / Published online: 7 February 2000     

On the intersection of infinite geometric and arithmetic progressions

We prove that the intersection G ∩ A of an infinite geometric progression G = u, uq, uq ², uq ³, ..., where u > 0 and q > 1 are real numbers, and an infinite arithmetic progression A contains at most 3 elements except for two kinds of ratios q. The first exception occurs for q = r ^1/d , where r > 1 is a rational number and d ∈ ℕ. Then this intersection can be of any cardinality s ∈ ℕ or infinite. The other (possible) exception may occur for q = β ^1/d , where β > 1 is a real cubic algebraic number with two nonreal conjugates of moduli distinct from β and d ∈ ℕ. In this (cubic) case, we prove that the intersection G ∩ A contains at most 6 elements.     

Embedding metric spaces into normed spaces and estimates of metric capacity

Let M^d{\cal M}^d be an arbitrary real normed space of finite dimension d ≥ 2. We define the metric capacity of M^d{\cal M}^d as the maximal m ? \Bbb Nm \in {\Bbb N} such that every m-point metric space is isometric to some subset of M^d{\cal M}^d (with metric induced by M^d{\cal M}^d ). We obtain that the metric capacity of M^d{\cal M}^d lies in the range from 3 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 , where the lower bound is sharp for all d, and the upper bound is shown to be sharp for d ∈ {2, 3}. Thus, the unknown sharp upper bound is asymptotically linear, since it lies in the range from d + 2 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 .     

Equivalent Characterizations for Boundedness of Maximal Singular Integrals on ax+b-Groups

Let (S,d,ρ) be the affine group ℝ ⁿ ⋉ℝ⁺ endowed with the left-invariant Riemannian metric d and the right Haar measure ρ, which is of exponential growth at infinity. In this paper, for any linear operator T on (S,d,ρ) associated with a kernel K satisfying certain integral size condition and H?rmander’s condition, the authors prove that the following four statements regarding the corresponding maximal singular integral T ^∗ are equivalent: T ^∗ is bounded from L_c^￥L_{c}^{\infty} to BMO, T ^∗ is bounded on L ^p for all p∈(1,∞), T ^∗ is bounded on L ^p for some p∈(1,∞) and T ^∗ is bounded from L ¹ to L ^1,∞. As applications of these results, for spectral multipliers of a distinguished Laplacian on (S,d,ρ) satisfying certain Mihlin-H?rmander type condition, the authors obtain that their maximal singular integrals are bounded from L_c^￥L_{c}^{\infty} to BMO, from L ¹ to L ^1,∞, and on L ^p for all p∈(1,∞).     

Sausages are good packings

LetB ^d be thed-dimensional unit ball and, for an integern, letC _n ={x ¹,...,x ⁿ } be a packing set forB ^d , i.e.,|x ⁱ −x ^j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C _n )+ρB ^d )≥V(conv(S _n )+ρB ^d ), whereS _n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d ⁻²,V(conv(C _n )+ρK)≥V(conv(S _n )+ρK), whereC _n is a packing set with respect toK andS _n is a minimal “sausage” arrangement ofK, holds.     

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f([`(x)]) = ?<sub>i = 1</sub><sup>k</sup> h<sub>i</sub> ([`(x)]) ·g_i ([`(x)])f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} , where each h _i is a polynomial that depends on only ρ linear functions, and each g _i is a product of linear functions (when h _i = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max _i (deg(h _i · g _i )) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.

A Turán type inequality for rational functions with prescribed poles

Summary By employing a novel idea and simple techniques, we substantially generalize the Turán type inequality for rational functions with real zeros and prescribed poles established by Min [5] to include L^pspaces for 1≤p≤∞<span style='font-size:10.0pt'>while loosing the restriction ρ > 2 at the same time.     

A new inductive approach to the lace expansion for self-avoiding walks

Summary. We introduce a new inductive approach to the lace expansion, and apply it to prove Gaussian behaviour for the weakly self-avoiding walk on ℤ ^d where loops of length m are penalised by a factor e ^{−β/m p} (0<β≪1) when: (1) d>4, p≥0; (2) d≤4, . In particular, we derive results first obtained by Brydges and Spencer (and revisited by other authors) for the case d>4, p=0. In addition, we prove a local central limit theorem, with the exception of the case d>4, p=0. Received: 29 October 1997 / In revised form: 15 January 1998     

On a class of stochastic partial differential equations related to turbulent transport

Summary. We consider the Cauchy problem for the mass density ρ of particles which diffuse in an incompressible fluid. The dynamical behaviour of ρ is modeled by a linear, uniformly parabolic differential equation containing a stochastic vector field. This vector field is interpreted as the velocity field of the fluid in a state of turbulence. Combining a contraction method with techniques from white noise analysis we prove an existence and uniqueness result for the solution ρ∈C ^1,2([0,T]×ℝ ^d ,(S)^*), which is a generalized random field. For a subclass of Cauchy problems we show that ρ actually is a classical random field, i.e. ρ(t,x) is an L ²-random variable for all time and space parameters (t,x)∈[0,T]×ℝ ^d . Received: 27 March 1995 / In revised form: 15 May 1997     

Linear series computing the Clifford index of a projective curve

For a (smooth irreducible) curveC of genus g and Clifford indexc>2 with a linear seriesg _d ^r computing c (so ) it is well known thatc + 2 ≤d ≤2 (c + 2), and if then 2c + 1 ≤g ≤ 2c + 4 unlessd = 2c + 4 in which caseg = 2c + 5. Let c ≥ 0 andg be integers. If 2c + 1 ≤g ≤2c + 4 we prove that for any integerd <g such thatd ≡c mod 2 andc + 2 ≤d < 2(c + 2) there exists a curve of genus g and Clifford index c with a g_d ^r computing c. Ford ≥c + 6 (i.e.r ≥ 3) we construct this curve on a surface of degree 2r-2 in ℙ^r, and ford ≥c + 8 (i.e.r ≥ 4) we show that such a curve cannot be found on a surface in ℙ^r of smaller degree. In fact, if g_d ^r computes the Clifford index c of C such thatc + 8 ≤d ≤ 2c + 3 then the birational morphism defined by this series cannot map C onto a (maybe, singular) curve contained in a surface of degree at most 2r-3 in ℙ^r.     

Application of Hilbert＇s Projective Metric on Symmetric Cones

Let Ω be a symmetric cone. In this note, we introduce Hilbert＇s projective metric on Ω in terms of Jordan algebras and we apply it to prove that, given a linear invertible transformation g such that g（Ω） = Ω and a real number p, ｜p｜ 〉 1, there exists a unique element x ∈ Ω satisfying g（x） = x^p.     

Blow up of balls and coverings in metric spaces

We obtain some refinements and extensions of the Basic Covering Theorem in a metric space (X, ρ). The properties of the metric ρ are used to define an inclusion coefficient k in this theorem, and this is related to the supremum of numbers t such that ρ ^t is a metric in X. The inclusion coefficient k characterizes ultrametric spaces.