Distribution of primes of the form P=[tc]-[nd] in arithmetic progressions

Ew obtain an asymptotic formula and a theorem about the mean (of the type of the large sieve) for the numberF _c,d (x;q,l) of primes px such thatp=(modq), p=[t^c]=[n ^d ], t,n , whereq>0, ,c,d are given numbers.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 121, pp. 94–202, 1983.     

Embeddings of graphs in euclidean spaces

The dimension of a graphG=(V, E) is the minimum numberd such that there exists a representation and a thresholdt such thatxy E iff . We prove that d(G)n–x(G) and wheren=|V| andx(G) is the chromatic number ofG; we present upper bounds for the dimension of graphs with a large girth and we show that the complement of a forest can be represented by unit vectors inR ⁶. We prove that d(G)1/15n for most graphs and that there are 3-regular graphs with d(G)c logn/log logn.     

Geometric methods in the study of irregularities of distribution

Let be a signed measure on E ^d with E ^d =0 and ¦¦E^d<. DefineD _s() as sup ¦H¦ whereH is an open halfspace. Using integral and metric geometric techniques results are proved which imply theorems such as the following.Theorem A. Let be supported by a finite pointsetp _i. ThenD _s()>c _d(₁/ ₂)^1/2{ _{i(p i})²}^1/2 where ₁ is the minimum distance between two distinctp _i, and ₂ is the maximum distance. The numberc _d is an absolute dimensional constant. (The number .05 can be chosen forc ₂ in Theorem A.)Theorem B. LetD be a disk of unit area in the planeE ², andp ₁,p ₂,...,p _n be a set of points lying inD. If m if the usual area measure restricted toD, while nP _i=1/n defines an atomic measure _n, then independently of _n,nD _s(m – _n) .0335n ^1/4. Theorem B gives an improved solution to the Roth disk segment problem as described by Beck and Chen. Recent work by Beck shows thatnD _s(m – _n)cn ^1/4(logn)^–7/2.     

Remarks on ergodicity of stationary irreducible transient Markov chains

Summary Consider a stationary process {X _n(), – < n < . If the measure of the process is finite (the measure of the whole sample space finite), it is well known that ergodicity of the process {X _n(), - < n < and of each of the subprocesses {X _n(), 0 n < , {X _n(), – < n 0 are equivalent (see [3]). We shall show that this is generally not true for stationary processes with a sigma-finite measure, specifically for stationary irreducible transient Markov chains. An example of a stationary irreducible transient Markov chain {X _n(), - < n <} with {itX_n(), 0 n < < ergodic but {X _n(), < n 0 nonergodic is given. That this can be the case has already been implicitly indicated in the literature [4]. Another example of a stationary irreducible transient Markov chain with both {X _n(), 0 n < and {itX _n(),-< < n 0} ergodic but {X _n(), - < n < nonergodic is presented. In fact, it is shown that all stationary irreducible transient Markov chains {X _n(), - < n < < are nonergodic.This research was supported in part by the Office of Naval Research.John Simon Guggenheim Memorial Fellow.     

Isotropic random walks in a tree

Summary Let T be an infinite homogeneous tree of order a+1. We study Markov chains {X _n} in T whose transition functions p(x, y)=A[d(x,y)] depend only on the shortest distance between x and y in the graph. The graph T can be represented as a symmetric space of a p-adic matrix group; we prove a series of results using essentially the spherical functions of this symmetric space. Theorem 1. d(X _n,x) n a.s., where >0 if A(0) 1, X ₀=x. Assuming {X _n} is strongly aperiodic, Theorem 2. p ₂(x, y)CRⁿ/n^3/2 for fixed x, y where R=(d) A(d)<1, and if E[d(X₁, X₀)²]<, Theorem 3. R(1–u, x, y) = (1–u)ⁿp_n(x, y)=Ca^–d[exp(–du/)+o_d(1)] as d=d(x,y) uniformly for 0u2. Using Theorem 3, we calculate the Martin boundary Dirichlet kernel of p(x, y) on T, which turns out to be independent of {itA(d)}. We also consider a stepping-stone model of a randomly-mating-and-migrating population on the nodes of T. If initially all individuals are distinct, then in generation n approximately half of the individuals of a given type are within n of a typical one and essentially all are within 2n.This work was partially supported by the National Science Foundation under grant number MCS 75-08098-A01For the academic year 1977–78: Department of Mathematics GN-50, University of Washington, Seattle, Washington 98195 USA     

New applications of random sampling in computational geometry

This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requiresO(s ^d+ ) expected preprocessing time to build a search structure for an arrangement ofs hyperplanes ind dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query pointp, the cell of the arrangement containingp can be found inO(logs) worst-case time. (The bound holds for any fixed >0, with the constant factors dependent ond and .) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expectedO(n ^[d/2]) time, wheren is the total number of vertices of the two polytopes. This matches previous results [10] for the cased = 3 and extends them. Another algorithm samples points in the plane to determine their orderk Voronoi diagram, and requires expectedO(s ¹⁺ k) time fors points. (It is assumed that no four of the points are cocircular.) This sharpens the boundO(sk ² logs) for Lee's algorithm [21], andO(s ² logs+k(s–k) log² s) for Chazelle and Edelsbrunner's algorithm [4]. Finally, random sampling is used to show that any set ofs points inE ³ hasO(sk ² log⁸ s/(log logs)⁶) distinctj-sets withjk. (ForS E ^d , a setS S with |S| =j is aj-set ofS if there is a half-spaceh ⁺ withS =S h ⁺.) This sharpens with respect tok the previous boundO(sk ⁵) [5]. The proof of the bound given here is an instance of a probabilistic method [15].A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986.     

On a zero-crossing probability

Let {X(t), 0E{exp (–sX(t))}=exp (–t(s)), where (s)=(1–(s)), is the intensity of the Poisson process, and (s) is the Laplace transform of the distribution of nonnegative jumps. Consider the zero-crossing probability =P{X(t)–t=0 for some t,0<t<}. We show that =() where is the largest nonnegative root of the equation (s)=s. It is conjectured that this result holds more generally for any stochastic process with stationary independent increments and with sample paths that are nondecreasing step functions vanishing at 0.     

The quality of the Diophantine approximations found by the Jacobi-Perron algorithm and related algorithms

Given a vector of real numbers=(₁,... _d ) ^d , the Jacobi-Perron algorithm and related algorithms, such as Brun's algorithm and Selmer's algorithm, produce a sequence of (d+1)×(d+1) convergent matrices {C⁽ⁿ⁾():n1} whose rows provide Diophantine approximations to . Such algorithms are specified by two mapsT:[0, 1] ^d [0, 1] ^d and A:[0,1] ^d GL(d+1,), which compute convergent matrices C⁽ⁿ⁾())...A(T())A(). The quality of the Diophantine approximations these algorithms find can be measured in two ways. The best approximation exponent is the upper bound of those values of for which there is some row of the convergent matrices such that for infinitely many values ofn that row of C⁽ⁿ⁾() has . The uniform approximation exponent is the upper bound of those values of such that for all sufficiently large values ofn and all rows of C⁽ⁿ⁾⁽⁾ one has . The paper applies Oseledec's multiplicative ergodic theorem to show that for a large class of such algorithms and take constant values and on a set of Lebesgue measure one. It establishes the formula where are the two largest Lyapunov exponents attached by Oseledec's multiplicative ergodic theorem to the skew-product (T, A,d), whered is aT-invariant measure, absolutely continuous with respect to Lebesgue measure. We conjecture that holds for a large class of such algorithms. These results apply to thed-dimensional Jacobi-Perron algorithm and Selmer's algorithm. We show that; experimental evidence of Baldwin (1992) indicates (nonrigorously) that. We conjecture that holds for alld2.     

The number of different distances determined by a set of points in the Euclidean plane

In 1946 P. Erdös posed the problem of determining the minimum numberd(n) of different distances determined by a set ofn points in the Euclidean plane. Erdös provedd(n) cn ^1/2 and conjectured thatd(n)cn/ logn. If true, this inequality is best possible as is shown by the lattice points in the plane. We showd(n)n ^4/5/(logn) ^c .The research of W. T. Trotter was supported in part by the National Science Foundation under DMS 8713994 and DMS 89-02481.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.

     

A chord-stretching map of a convex loop is an isometry

Let ⁿ be n-dimensional Euclidean space, and let : [0, L] ⁿ and : [0, L] ⁿ be closed rectifiable arcs in ⁿ of the same total length L which are parametrized via their arc length. is said to be a chord-stretched version of if for each 0s tL, |(t)–(s)| |(t)–(s)|. is said to be convex if is simple and if ([0, L]) is the frontier of some plane convex set. Individual work by Professors G. Choquet and G. T. Sallee demonstrated that if were simple then there existed a convex chord-stretched version of . This result led Professor Yang Lu to conjecture that if were convex and were a chord-stretched version of then and would be congruent, i.e. any chord-stretching map of a convex arc is an isometry. Professor Yang Lu has proved this conjecture in the case where and are C ² curves. In this paper we prove the conjecture in general.     

The Skorohod oblique reflection problem in domains with corners and application to stochastic differential equations

Summary The Skorohod oblique reflection problem for (D, , w) (D a general domain in ^d , (x),xD, a convex cone of directions of reflection,w a function inD(⁺, ^d )) is considered. It is first proved, under a condition on (D, ), corresponding to (x) not being simultaneously too large and too much skewed with respect to D, that given a sequence {w ⁿ} of functions converging in the Skorohod topology tow, any sequence {(x ⁿ, ⁿ)} of solutions to the Skorohod problem for (D, , w ⁿ) is relatively compact and any of its limit points is a solution to the Skorohod problem for (D, , w). Next it is shown that if (D, ) satisfies the uniform exterior sphere condition and another requirement, then solutions to the Skorohod problem for (D, , w) exist for everywD(⁺, ^d ) with small enough jump size. The requirement is met in the case when D is piecewiseC _b ¹ , is generated by continuous vector fields on the faces ofD and (x) makes and angle (in a suitable sense) of less than /2 with the cone of inward normals atD, for everyxD. Existence of obliquely reflecting Brownian motion and of weak solutions to stochastic differential equations with oblique reflection boundary conditions is derived.     

Kleine Nullstellen homogener quadratischer Gleichungen

Let 0 be a real quadratic form inn variables, which takes on integral values on ⁿ . Denote by the largest coefficient of in absolute value. Suppose vanishes on ad-dimensional rational subspace. It is shown that has a zero (x ₁,...,x _n ⁿ \{(0,...,0)} with max |x _i ^(n-d/2d).     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

A sequence has almost nowhere small discrepancy

LetD _n (x) be the discrepancy function of a sequence in [0,1) as defined in the first lines of the introduction. A well known result ofW. M. Schmidt states that limsup _n sup _x |D _n (x)|/logn1/100 for every sequence. In this paper it is proved that for every sequence sup _x |D _n (x)|/logn1/100 for almost all values ofn. A more refined assertion is given in Theorem 1, a more general one in Theorem 2, while it is proved in Theorem 3 that these results are essentially the best possible. Another result ofSchmidt is that for every sequence limsup _n|D _n (x)|/loglogn1/2000 for almost allx in [0, 1). In this paper it is shown that for every sequence limsup _n|D _n (x)|/logn1/400 for almost allx in [0, 1). Theorem 4 contains a more refined and Theorem 5 a more general statement. Finally Theorem 6 implies that also these results are essentially the best possible.     

Spline polynomials with a prescribed sequence of extrema

In the present note a theorem about strong suitability of the space of algebraic polynomials of degree n in C[a,b] (Theorem A in [1]) is generalized to the space of spline polynomials _{[a, b} ^{]n, k} (n2, 0) in C[a, b]. Namely, it is shown that the following theorem is valid: for arbitrary numbers ₀, ₁, ..., _n+k, satisfying the conditions (_i–_i–1) (_{i+1{ i}< 0(i=1, ..., n +k–1), there is a unique polynomials _n,k (t) _{[a, b} ^]/n,k and pointsa=₀,<₁<...< _n+k– 1< _n+k = b (₁1 <_n, ..., _kk<_n+k–1), such that s_n,k(_i) = _i(i=0, ..., n + k), s_n,k(_i)=0 (i=1, ..., n + k–1).Translated from Matematicheskii Zametki, Vol. 11, No. 3, pp. 251–258, March, 1972.     

Circularity of Finite Groups without Fixed Points

Let be a fixed point free group given by the presentation where and are relative prime numbers, t = /s and s = gcd( – 1,), and is the order of modulo . We prove that if (1) = 2, and (2) is embeddable into the multiplicative group of some skew field, then is circular. This means that there is some additive group N on which acts fixed point freely, and |((a)+b)((c)+d)| 2 whenever a,b,c,d N, a0c, are such that (a)+b(c)+d.     

On the postulation of a general projection of a curve inP 3

Summary We say that a curve C in P ³ has maximal rank if for every integer k the restriction map r_c(k):H ⁰(P ³, O_P3(k)) H⁰ (C, O_C(k))has maximal rank. Here we prove the following results. Theorem 1Fix integers g, d with 0g3,dg+3.Fix a curve X of genus g and L Pic^d (X).If g=3and X is hyperelliptic, assume d8. Let _L(X)be the image of X by the complete linear system H ⁰(X, L). Then a general projection of _L(X)into P ³ has maximal rank. Theorem 2For every integer g0,there exists an integer d(g, 3)such that for every dd(g, 3),for every smooth curve X of genus g and every LPic^d (X) the general projection of _L(X)into P ³ has maximal rank.     

Generalised Holley-Preston inequalities on measure spaces and their products

Summary It is shown that if (X, ) is a product of totally ordered measure spaces andf _j (j=1,2,3,4) are measurable non-negative functions onX satisfyingf ₁(x)f₂(y)f₃(xy)f₄(xy), where (, ) are the lattice operations onX, then (f ₁ d)(f ₂ d)(f ₃ d)(f ₄ d). This generalises results of Ahlswede and Daykin (for counting measure on finite sets) and Preston (for special choices off _j).     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).