On the fractional parts of the natural powers of a fixed number

Let ξ ≠ = 0 and α > 1 be reals. We prove that the fractional parts {ξ αⁿ}, n = 1, 2, 3, ..., take every value only finitely many times except for the case when α is the root of an integer: α = q ^1/d, where q ≥ 2 and d ≥ 1 are integers and ξ is a rational factor of a nonnegative integer power of α.     

Radial rearrangement, harmonic measures and extensions of Beurling's shove theorem

LetI be a union of finitely many closed intervals in [−1, 0). LetI ^↞ be a single interval of the form [−1, −a] chosen to have the same logarithmic length asI. LetD be the unit disc. Then, Beurling [8] has shown that the harmonic measure of the circle ∂D at the origin in the slit discD/I is increased ifI is replaced byI ^↞. We prove a number of cognate results and extensions. For instance, we show that Beurling's result remains true if the intervals inI are not just one-dimensional, but if they in fact constitute polar rectangles centred on the negative real axis and having some fixed constant angular width. In doing this, we obtain a new proof of Beurling's result. We also discuss a conjecture of Matheson and Pruss [25] and some other open problems. Much of the present paper has been adapted from Chapter IV of the author's doctoral dissertation. The research was partially supported by Professor J. J. F. Fournier's NSERC Grant #4822.     

Linear equations with unknowns from a multiplicative group whose solutions lie in a small number of subspaces

Let K be a field of characteristic 0 and let (K^*)ⁿ denote the n-fold Cartesian product of K^*, endowed with coordinatewise multiplication. Let Γ be a subgroup of (K^*)ⁿ of finite rank. We consider equations (*) a₁x₁ + … + a_nx_n = 1 in x = (x₁x_n)Γ, where a = (a₁,a_n)(K^*)ⁿ. Two tuples a, b(K^*)ⁿ are called Γ-equivalent if there is a uΓ such that b = u · a. Gy?ry and the author [Compositio Math. 66 (1988) 329-354] showed that for all but finitely many Γ-equivalence classes of tuples a(K^*)ⁿ, the set of solutions of (*) is contained in the union of not more than 2⁽ⁿ⁺¹! proper linear subspaces of Kⁿ. Later, this was improved by the author [J. reine angew. Math. 432 (1992) 177-217] to (n!)²ⁿ⁺². In the present paper we will show that for all but finitely many Γ-equivalence classes of tuples of coefficients, the set of non-degenerate solutions of (*) (i.e., with non-vanishing subsums) is contained in the union of not more than 2ⁿ proper linear subspaces of Kⁿ. Further we give an example showing that 2ⁿ cannot be replaced by a quantity smaller than n.     

Powers of roots in linear spaces

Suppose K is a field, αn∈K^∗, and n is the least natural number with this property. We study the question on how many powers αj, 0?j<n, lie in a given K-linear space.     

The distribution of reduced numbers in an ideal of a real cubic number field

Let K be a real but not totally real field of degree three over Q, and let A be an ideal in K. It is proved that the reduced numbers in A (i.e., numbers α with α > 1 and ?1 < Re α^(j) < 0 for all conjugates α^(j) ≠ α) are dense in a set of intervals of constant length, and no reduced numbers in A occur in the gaps between these intervals. In fact, the intervals are determined explicitly, and criteria are given for when the reduced numbers in A actually are dense in the whole of [1, ∞).     

Description of the Space of Riesz Potentials of Functions in a Grand Lebesgue Space on ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

The Riesz potentials L^af, 0 < α < ∞, are considered in the framework of a grand Lebesgue space L_a^p),θ, 1 < p < ∞, θ > 0, on Rn with grandizers a ∈ L¹(?ⁿ), which are understood in the case α ≥ n/p in terms of distributions on test functions in the Lizorkin space. The images under I^α of functions in a subspace of the grand space which satisfy the so-called vanishing condition is studied. Under certain assumptions on the grandizer, this image is described in terms of the convergence of truncated hypersingular integrals of order α in this subspace.     

Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.     

Arithmetical progressions formed byk different Lehmer pseudoprimes

LetU _n=(αⁿ-β²)/(α-β) forn odd andU _n=(αⁿ-βⁿ)/(α²-β²) for evenn, where α and β are distinct roots of the trinomialf(z)=z ²-√Lz+Q andL>0 andQ are rational integers.U _n is then-th Lehmer number connected withf(z). A compositen is a Lehmer pseudoprime for the bases α and β ifU _n??(n)≡0 (modn), where?(n)=(LD/n) is the Jacobi symbol. IfD=L?4Q>0, U _n denotesn-th Lehmer number,p>3 and 2p?1 are primes,p(2p-1)+(α²-β²)², (α^2p-1±β^2p-1)/(α±β) are composite then the numbers (α^2p-1+β^2p-1)/(α+β), (α^2p-β^2p)/(α²-β²), (α^2p-1-β^2p-1)/(α-β) are lehmer pseudoprimes for the bases α and β and form an arithmetical progression. IfD>0 then from hypothesisH of A. Schinzel on polynomials it follows that for every positive integerk there exists infinitely many arithmetic progressions formed fromk different Lehmer pseudoprimes for the bases α and β.     

Convergence of Multipoint Padé-type Approximants

Let μ be a finite positive Borel measure whose support is a compact subset K of the real line and let I be the convex hull of K. Let r denote a rational function with real coefficients whose poles lie in C\I and r(∞)=0. We consider multipoint rational interpolants of the function where some poles are fixed and others are left free. We show that if the interpolation points and the fixed poles are chosen conveniently then the sequence of multipoint rational approximants converges geometrically to f in the chordal metric on compact subsets of C\I.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

Fields with large Kronecker constants

For any algebraic number field K there is a positive number ? such that if α is a nonzero integer of K other than a root of unity, then at least one conjugate of α has absolute value ≥ 1 + ?. It has been conjectured that ? can be taken as $\text{2}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{? 1}$, where n is the degree of K over the field of rationals. In this paper various conditions are discussed under which the validity of this conjecture can be established.     

Surfaces meeting porous sets in positive measure

Let X be a Banach space and 2 < n < dimX. We show there exists a directionally porous set P in X for which the set of C ¹ surfaces of dimension n meeting P in positive measure is not meager. If X is separable, this leads to a decomposition of X into the union of a σ-directionally porous set and a set which is null on residually many C ¹ surfaces of dimension n. This is of interest in the study of Γn-null and Γ-null sets and their applications to differentiability of Lipschitz functions.     

The compactness of adaptive routing tables

The compactness of a routing table is a complexity measure of the memory space needed to store the routing table on a network whose nodes have been labelled by a consecutive range of integers. It is defined as the smallest integer k such that, in every node u, every set of labels of destinations having the same output in the table of u can be represented as the union of k intervals of consecutive labels. While many works studied the compactness of deterministic routing tables, few of them tackled the adaptive case when the output of the table, for each entry, must contain a fixed number α of routing directions. We prove that every n-node network supports shortest path routing tables of compactness at most n/α for an adaptiveness parameter α, whereas we show a lower bound of n/α^O(1).     

Stability of associated primes of integral closures of monomial ideals

Let I be a monomial ideal of a polynomial ring R=K[X₁,…,Xr] and d(I) the maximal degree of minimal generators of I. In this paper, we explicitly determine a number n₀ in terms of r and d(I) such that for all n?n₀. Furthermore, our n₀ is almost sharp.     

An extension of Lagrange’s theorem to interval exchange transformations over quadratic fields

LetT be an interval exchange transformation onN intervals whose lengths lie in a quadratic number field. Let {T _n } _n=1 ^∞ be any sequence of interval exchange transformations such thatT ₁ =T andT _n is the first return map induced byT _n-1 on one of its exchanged intervals I_n-1. We prove that {T _n } _n=1 ^∞ contains finitely many transformations up to rescaling. If the interval I_n is chosen according to a consistent pattern of induction, e.g., the first interval is chosen, then there existk,n ₀ ∈ ℤ⁺, λ ∈R ⁺ such that for alln ≥n ₀,I _n = λI _n+k andT _n ,T _n+k are the same up to rescaling. Rephrased arithmetically, this says that a certain family of vectorial division algorithms, applied to quadratic vector spaces, yields sequences of remainders that are eventually periodic. WhenN = 2 the assertion reduces to Lagrange’s classical theorem that the simple continued fraction expansion of a quadratic irrational is eventually periodic. We also discuss the case of periodic induced sequences. These results have applications to topology. In particular, every projective measured foliation on Thurston’s boundary to Teichmüller space that is minimal and metrically ‘quadratic’ is fixed by a hyperbolic element of the modular group. Moreover, if the foliation is orientable, it covers (via a branched covering) an irrational foliation of the two-torus. We also obtain a new proof, for quadratic irrationals, of Boshernitzan’s result that a minimal rank 2 interval exchange transformation is uniquely ergodic. The first author was supported in part by NSF-DMS-9224667. The second author was supported in part by an NSF-NATO fellowship, held at the Université Paris-Sud, Orsay.     

Intervals in lattices of quasiorders

We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the intervalI has no infinite chains then the underlying space may be assumed to be finite, and in particular,I must be finite, too. We compute several upper bounds for its size in terms of its heighth, which in turn can be computed easily by means of the least and the greatest element ofI. The cover degreec of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4h. Moreover, ifc4(n–1) thenI contains a Boolean subinterval of size 2 ⁿ , and ifI is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.     

On nonmeasurable unions

For a Polish space X and a σ-ideal I of subsets of X which has a Borel base we consider families A of sets in I with the union ?A not in I. We determine several conditions on A which imply the existence of a subfamily A^′ of A whose union ?A^′ is not in the σ-field generated by the Borel sets on X and I. Main examples are X=R and I being the ideal of sets of Lebesgue measure zero or the ideal of sets of the first Baire category.     

Orthogonal Polynomials Associated with Equilibrium Measures on $\mathbb {R}$

Let K be a non-polar compact subset of \(\mathbb {R}\) and μ _K denote the equilibrium measure of K. Furthermore, let P _n (?;μ _K ) be the n-th monic orthogonal polynomial for μ _K . It is shown that \(\|P_{n}\left (\cdot ; \mu _{K}\right )\|_{L^{2}(\mu _{K})}\), the Hilbert norm of P _n (?;μ _K ) in L ²(μ _K ), is bounded below by Cap(K) ⁿ for each \(n\in \mathbb {N}\). A sufficient condition is given for\(\left (\|P_{n}\left (\cdot ;\mu _{K}\right )\|_{L^{2}(\mu _{K})}/\text {Cap}(K)^{n}\right )_{n=1}^{\infty }\) to be unbounded. More detailed results are presented for sets which are union of finitely many intervals.     

The covering number in learning theory

The covering number of a ball of a reproducing kernel Hilbert space as a subset of the continuous function space plays an important role in Learning Theory. We give estimates for this covering number by means of the regularity of the Mercer kernel K. For convolution type kernels K(x,t)=k(x−t) on [0,1]ⁿ, we provide estimates depending on the decay of k̂, the Fourier transform of k. In particular, when k̂ decays exponentially, our estimate for this covering number is better than all the previous results and covers many important Mercer kernels. A counter example is presented to show that the eigenfunctions of the Hilbert–Schmidt operator Lm_K associated with a Mercer kernel K may not be uniformly bounded. Hence some previous methods used for estimating the covering number in Learning Theory are not valid. We also provide an example of a Mercer kernel to show that L_K^1/2 may not be generated by a Mercer kernel.