Onp-adic functions preserving Haar measure

Let {a _n } _n ^=0/ be a uniformly distributed sequence ofp-adic integers. In the present paper we study continuous functions close to differentiable ones (with respect to thep-adic metric); for these functions, either the sequence {f(a _n )} _n ^=0/ is uniformly distributed over the ring ofp-adic integers or, for all sufficiently largek, the sequences {f _k (_k(a_n))} _n ^=0/ are uniformly distributed over the residue class ring modp ^k , where _k is the canonical epimorphism of the ring ofp-adic integers to the residue class ring modp ^k andf _k is the function induced byf on the residue class ring modp ^k (i.e.,f k _(x) =f( _k (x)) (modp ^k )). For instance, these functions can be used to construct generators of pseudorandom numbers.Translated fromMatematicheskie Zametki, Vol. 63, No. 6, pp. 935–950, June, 1998.In conclusion, the author wishes to express his deep gratitude to V. S. Anashin for permanent attention to this research and for support.     

A fast transform for spherical harmonics

Spherical harmonics arise on the sphere S² in the same way that the (Fourier) exponential functions {e^ik}k arise on the circle. Spherical harmonic series have many of the same wonderful properties as Fourier series, but have lacked one important thing: a numerically stable fast transform analogous to the Fast Fourier Transform (FFT). Without a fast transform, evaluating (or expanding in) spherical harmonic series on the computer is slow—for large computations probibitively slow. This paper provides a fast transform.For a grid ofO(N²) points on the sphere, a direct calculation has computational complexityO(N⁴), but a simple separation of variables and FFT reduce it toO(N³) time. Here we present algorithms with timesO(N^5/2 log N) andO(N²(log N)²). The problem quickly reduces to the fast application of matrices of associated Legendre functions of certain orders. The essential insight is that although these matrices are dense and oscillatory, locally they can be represented efficiently in trigonometric series.     

Zur Darstellung Miquelscher Möbiusräume

In this paper we prove the following theorem (shown by J.TITS [7] in the case of finite dimension): LetO be a set of at least 2 points of a projective space of dimension 2 and suppose that the intersections ofO and the planes of are either empty or one point sets or Pascalian ovals. ThenO is an ellipsoid (nondegenerate quadric of index 1). As a corollary we obtain that every Miquelian Möbius-space is the geometry of the plane sections of an ellipsoid.     

The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Letf ₁, ...,f _m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n ^d (n)), where(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d – 1)-dimensional compact convex sets) in ^d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n ^d+1–(d+1) ) for some fixed constant(d+1)>0.Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development.     

Sur un problème de Rényi

Let (n) be the number of all prime divisors ofn and (n) the number of distinct prime divisors ofn. We definev _q (x)=|{nx(n)–(n)=q}|. In this paper, we give an asymptotic development ofv _q (x); this improves on previous results.

     

Über die Anzahl der Lösungen der diskreten Theodorsen-Gleichung

Summary Discretization of the Theodorsen integral equation (T) yields the discrete Theodorsen-equation (T _d ), a system of 2N nonlinear equations. A so-called -condition may be fulfilled. It is known that (T) has exactly one continuous solution. This solution gives the boundary correspondence of the normalized conformal map of the unit disc onto a given domainG. It is also known that (T _d ) has one and only one solution if <1 and at least one solution if 1. We show here that for every 1 and N\ {1} there is a domainG satisfying an -condition such that (T _d ) has an infinite number of solutions. Moreover, givenK>0 and any domainG that fulfills an -condition, we will construct a domainG ₁ in the neighbourhood ofG that fulfills a max (1, +K)-condition such that (T _d ) forG ₁ has an infinite number of solutions. The underlying idea of the construction of those domains allows also to give important new facts about iterative methods for the solution of (T _d ), even in the case <1.

     

Isoperimetric inequalities for lattices in semisimple lie groups of rank 2

LetG be a connected semisimple Lie group with finite center. Let be an irreducible non-uniform lattice inG. We show that if the real rank ofG is 2, then the Dehn (or filling) function of is exponential.     

Strict lower semicontinuity of the level sets and invexity of a locally Lipschitz function

The strict lower semicontinuity property (slsc property) of the level sets of a real-valued functionf defined on a subsetCR ⁿ was introduced by Zang, Choo, and Avriel (Ref. 1). They showed a class of functions for which the slsc property is equivalent to invexity, i.e., the statement that every stationary point off overC is a global minimum. In this paper, we study the relationship between the slsc property of the level sets and invexity for another class of functions. Namely, we consider the class formed by all locally Lipschitz real-valued functions defined on an open set containingC. For these functions, invexity implies the slsc property of the level sets, but not conversely.The authors would like to thank Dr. B. D. Craven and the referees for helpful comments and suggestions.     

Holomorphic rank of hypersurfaces with an isolated singularity

LetV be a germ at 0 C ²,n3, of hypersurface with an isolated singularity at 0. In this paper we prove that the maximal number of germs of vector fields inV ^*=V–0, which are linearly independent in all points ofV ^* is two. In the casesn=3,4 and of quasi homogeneous hypersurfaces (n3), we prove that this number is one.Dedicated to the memory of R. MañéThis research was partially supported by Pronex.     

Underlying graph and total length of optimal realizations of variable distance matrices

The general problem is to investigate, for acceptable values ofx, the optimal graph realization of a matrixD(x) obtained from a given tree-realizable distance matrixD as follows: we partition the index set ofD into two convex subsetsH andK, we subtractx from all entriesd _hk andd _kh whereh H andk K and we leave all other entries unchanged. We describe the optimal realization of the matrixD(x) and the behaviour of the total length of the optimal realization as a function ofx. This work was supported by the National Science Foundation Grant DMS-8401686 and by the PSC/CUNY Research Award Program.     

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.     

Planar realizations of nonlinear davenport-schinzel sequences by segments

LetG={l ₁,...,l _n } be a collection ofn segments in the plane, none of which is vertical. Viewing them as the graphs of partially defined linear functions ofx, letY _G be their lower envelope (i.e., pointwise minimum).Y _G is a piecewise linear function, whose graph consists of subsegments of the segmentsl _i . Hart and Sharir [7] have shown thatY _G consists of at mostO(n(n)) segments (where(n) is the extremely slowly growing inverse Ackermann's function). We present here a construction of a setG ofn segments for whichY _G consists of(n(n)) subsegments, proving that the Hart-Sharir bound is tight in the worst case.Another interpretation of our result is in terms of Davenport-Schinzel sequences: the sequenceE _G of indices of segments inG in the order in which they appear alongY _G is a Davenport-Schinzel sequence of order 3, i.e., no two adjacent elements ofE _G are equal andE _G contains no subsequence of the forma ...b ...a ...b ...a. Hart and Sharir have shown that the maximal length of such a sequence composed ofn symbols is (n(n)). Our result shows that the lower bound construction of Hart and Sharir can be realized by the lower envelope ofn straight segments, thus settling one of the main open problems in this area.Work on this paper has been partially supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. This paper is part of the first author's M.Sc. thesis prepared at Tel Aviv University under the supervision of the second author. A preliminary version of this paper has appeared inProceedings of the 27th IEEE Symposium on Foundations of Computer Science, Toronto, 97–106, 1986.     

Automorphisms on a Lie group contracting modulo a compact subgroup and applications to semistable convolution semigroups

Let ( _t ) _t0 be a -semistable convolution semigroup of probability measures on a Lie groupG whose idempotent ₀ is the Haar measure on some compact subgroupK. Then all the measures ₁ are supported by theK-contraction groupC _K() of the topological automorphism ofG. We prove here the structure theoremC _K()=C()K, whereC() is the contraction group of . Then it turns out that it is sufficient to study semistable convolution semigroups on simply connected nilpotent Lie groups that have Lie algebras with a positive graduation.     

Lines,line-point incidences and crossing families in dense sets

LetP be a set ofn points in the plane. We say thatP isdense if the ratio between the maximum and the minimum distance inP is of order . A setC of line segments in the plane is calleda crossing family if the relative interiors of any two line segments ofC intersect. Vertices of line segments of a crossing familyC are calledvertices of C. It is known that for any setP ofn points in general position in the plane there is a crossing family of size with vertices inP. In this paper we show that ifP is dense then there is a crossing family of almost linear size with vertices inP.The above result is related to well-known results of Beck and of Szemerédi and Trotter. Beck proved that any setP ofn points in the plane, not most of them on a line, determines at least (n ²) different line. Szemerédi and Trotter proved that ifP is a set ofn points and is a set ofm lines then there are at mostO(m ^2/3 n ^2/3 +m+n) incidences between points ofP and lines of . We study whether or not the bounds shown by Beck and by Szemerédi and Trotter hold for any dense setP even if the notion of incidence is extended so that a point is considered to be incident to a linel if it lies in a small neighborhood ofl. In the first case we get very close to the conjectured bound (n ²). In the second case we obtain a bound of order .The work on this paper was supported by Czech Republic grant GAR 201/94/2167, by Charles University grants No. 351 and 361, by Deutsche Forschungsgemeinschaft, grant We 1265/2-1, and by DIMACS.     

Line bundles over a moduli space of logarithmic connections on a Riemann surface

We consider logarithmic connections, on rank n and degree d vector bundles over a compact Riemann surface X, singular over a fixed point x₀ ∈ X with residue in the center of the integers n and d are assumed to be mutually coprime. A necessary and sufficient condition is given for a vector bundle to admit such a logarithmic connection. We also compute the Picard group of the moduli space of all such logarithmic connections. Let denote the moduli space of all such logarithmic connections, with the underlying vector bundle being of fixed determinant L, and inducing a fixed logarithmic connection on the determinant line L. Let be the Zariski open dense subset parametrizing all connections such that the underlying vector bundle is stable. The space of all global sections of certain line bundles on are computed. In particular, there are no nonconstant algebraic functions on Therefore, there are no nonconstant algebraic functions on although is biholomorphic to a representation space which admits nonconstant algebraic functions. The moduli space admits a natural compactification by a smooth divisor. We investigate numerically effectiveness of this divisor at infinity. It turns out that the divisor is not numerically effective in general. Received: March 2004 Revision: May 2004 Accepted: May 2004     

Ovoids and spreads of finite classical polar spaces

LetP be a finite classical polar space of rankr, r2. An ovoidO ofP is a pointset ofP, which has exactly one point in common with every totally isotropic subspace of rankr. It is proved that the polar spaceW _n (q) arising from a symplectic polarity ofPG(n, q), n odd andn > 3, that the polar spaceQ(2n, q) arising from a non-singular quadric inPG(2n, q), n > 2 andq even, that the polar space Q^–(2n + 1,q) arising from a non-singular elliptic quadric inPG(2n + 1,q), n > 1, and that the polar spaceH(n,q ²) arising from a non-singular Hermitian variety inPG(n, q ²)n even andn > 2, have no ovoids.LetS be a generalized hexagon of ordern (1). IfV is a pointset of order n³ + 1 ofS, such that every two points are at distance 6, thenV is called an ovoid ofS. IfH(q) is the classical generalized hexagon arising fromG ₂ (q), then it is proved thatH(q) has an ovoid iffQ(6, q) has an ovoid. There follows thatQ(6, q), q=3^2h+1, has an ovoid, and thatH(q), q even, has no ovoid.A regular system of orderm onH(3,q ²) is a subsetK of the lineset ofH(3,q ²), such that through every point ofH(3,q ²) there arem (> 0) lines ofK. B. Segre shows that, ifK exists, thenm=q + 1 or (q + l)/2.If m=(q + l)/2,K is called a hemisystem. The last part of the paper gives a very short proof of Segre's result. Finally it is shown how to construct the 4-(11, 5, 1) design out of the hemisystem with 56 lines (q=3).     

The expected number of parts in a partition ofn

Forn a positive integer letp(n) denote the number of partitions ofn into positive integers and letp(n,k) denote the number of partitions ofn into exactlyk parts. Let , thenP(n) represents the total number of parts in all the partitions ofn. In this paper we obtain the following asymptotic formula for .     

Finite difference methods and their convergence for a class of singular two point boundary value problems

Summary We discuss the construction of three-point finite difference approximations and their convergence for the class of singular two-point boundary value problems: (x y)=f(x,y), y(0)=A, y(1)=B, 0<<1. We first establish a certain identity, based on general (non-uniform) mesh, from which various methods can be derived. To obtain a method having order two for all (0,1), we investigate three possibilities. By employing an appropriate non-uniform mesh over [0,1], we obtain a methodM ₁ based on just one evaluation off. For uniform mesh we obtain two methodsM ₂ andM ₃ each based on three evaluations off. For =0,M ₁ andM ₂ both reduce to the classical second-order method based on one evaluation off. These three methods are investigated, theirO(h ²)-convergence established and illustrated by numerical examples.     

Quasicomplete factorizations of rational matrix functions

It is shown that within the class ofn×n rational matrix functions which are analytic at infinity with valueW()=I _n, any rational matrix functionW is the productW=W ₁...W _p of rational matrix functionsW ₁,...,W _p of McMillan degree one. Furthermore, such a factorization can be established with a number of factors not exceeding 2(W)–1, where (W) denotes the McMillan degree ofW.