On the transcendence of real numbers with a regular expansion

We apply the Ferenczi-Mauduit combinatorial condition obtained via a reformulation of Ridout's theorem to prove that a real number whose b-ary expansion is the coding of an irrational rotation on the circle with respect to a partition in two intervals is transcendental. We also prove the transcendence of real numbers whose b-ary expansion arises from a non-periodic three-interval exchange transformation.     

Congruences for the class numbers of real cyclic sextic number fields

LetK ₆ be a real cyclic sextic number field, andK ₂,K ₃ its quadratic and cubic subfield. Leth(L) denote the ideal class number of fieldL. Seven congruences forh ^- =h (K ₆)/(h(K ₂)h(K ₃)) are obtained. In particular, when the conductorf ₆ ofK ₆ is a primep, , whereC is an explicitly given constant, andB _n is the Bernoulli number. These results on real cyclic sextic fields are an extension of the results on quadratic and cyclic quartic fields. Project supported by the National Natural Science Foundation of China (Grant No. 19771052).     

On the Kolmogorov complexity of continuous real functions

Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials with rational coefficients.Based on this definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that ‘almost every’ continuous real function has such a high-growth Kolmogorov complexity. An asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions will be presented as well.     

On the distribution of multiples of real numbers

We introduce new series (of the variable ??) that enable to measure the irregularity of distribution of the sequence of fractional parts {n??}. A detailed analysis of the convergence and divergence of these series is done, depending mainly on the convergents of ??. As a by product, we obtain new Fourier series of square integrable functions that converge almost everywhere but at no rational number.     

On the complexity of recognizing a set of vectors by a neuron

We consider the problems connected with the computational abilities of a neuron. The orderings of finite subsets of real vectors associated with neural computing are studied. We construct a lattice of such orderings and study some its properties. The interrelation between the orders on the sets and the neuron implementation of functions defined on these sets is derived. We prove the NP-hardness of “The Shortest Vector” problem and represent the relationship of the problem with neural computing.     

On the Pythagoras numbers of real analytic curves

We show that the Pythagoras number of a real analytic curve is the supremum of the Pythagoras numbers of its singularities, or that supremum plus 1. This includes cases when the Pythagoras number is infinite.      

The set of real numbers left uncovered by random covering intervals

Summary Random covering intervals are placed on the real line in a Poisson manner. Lebesgue measure governs their (random) locations and an arbitrary measure μ governs their (random) lengths. The uncovered set is a regenerative set in the sense of Hoffmann-J?rgensen's generalization of regenerative phenomena introduced by Kingman. Thus, as has previously been obtained by Mandelbrot, it is the closure of the image of a subordinator —one that is identified explicitly. Well-known facts about subordinators give Shepp's necessary and sufficient condition on μ for complete coverage and, when the coverage is not complete, a formula for the Hausdorff dimension of the uncovered set. The method does not seem to be applicable when the covering is not done in a Poisson manner or if the line is replaced by the plane or higher dimensional space. This work does not represent a collaboration among the three authors, but rather is an outgrowth of a discovery that the first author on one hand and the second and third authors on the other hand had proved identical results via similar methods. Based on part of the first author's PhD dissertation written under Kenneth J. Hochberg at Case Western Reserve University. Research partially supported by National Science Foundation Grant MCS 78-01168.     

On localization of the characteristic numbers of real matrices

In this paper we give domains for the distribution on the complex plane of the characteristic numbers of a set of real matrices, basing our work on results obtained by F. I. Karpelevich for matrices with nonnegative elements.Translated from Matematicheskie Zametki, Vol. 15, No. 5, pp. 765–768, May, 1974.In conclusion the author expresses his thanks to R. A. Poluéktov and G. S. Épel'man for useful discussions of his work.     

On the complexity of online computations of real functions

A reasonable computational complexity theory for real functions is obtained by using the modified infinite binary representation with digits 0, l, and −1 for the real numbers and Turing machines which transform with one-way output modified binary input sequences into modified binary output sequences. As the main result of this paper it is shown that there is a trade-off between the input lookahead, i.e., the deviation of online computation and the computational complexity for machines computing certain real functions.     

On characterizations of the ordered field of real numbers

This self-contained note could find classroom use in an introductory course on analysis. It is proved that an ordered field F is complete (that is, order-isomorphic to the field of real numbers) if and only if each bounded monotonic sequence in F converges in F. Also established is the key tool that an ordered field is complete if and only if it is Archimedean and Cauchy-complete, along with a number of characterizations of Archimedean fields.     

On approximation of real numbers by algebraic numbers of bounded degree

Dirichlet proved that for any real irrational number ξ there exist infinitely many rational numbers p/q such that |ξ−p/q|<q⁻². The correct generalization to the case of approximation by algebraic numbers of degree ?n, n>2, is still unknown. Here we prove a result which improves all previous estimates concerning this problem for n>2.     

On the complexity of finding the convex hull of a set of points

An n log n lower bound is found for linear decision tree algorithms with integer inputs that either identify the convex hull of a set of points or compute its cardinality.     

On the complexity of four polyhedral set containment problems

A nonempty closed convex polyhedronX can be represented either asX = {x: Ax b}, where (A, b) are given, in which caseX is called anH-cell, or in the formX = {x: x = U + V, _j = 1, 0, 0}, where (U, V) are given, in which caseX is called aW-cell. This note discusses the computational complexity of certain set containment problems. The problems of determining if , where (i)X is anH-cell andY is a closed solid ball, (ii)X is anH-cell andY is aW-cell, or (iii)X is a closed solid ball andY is aW-cell, are all shown to be NP-complete, essentially verifying a conjecture of Eaves and Freund. Furthermore, the problem of determining whether there exists an integer point in aW-cell is shown to be NP-complete, demonstrating that regardless of the representation ofX as anH-cell orW-cell, this integer containment problem is NP-complete.     

On the unimodality of the independent set numbers of a class of matroids

It is shown that the independent set numbers of polygon matroids of outerplanar graphs are log concave.     

On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients

Kostka numbers and Littlewood-Richardson coefficients appear in combinatorics and representation theory. Interest in their computation stems from the fact that they are present in quantum mechanical computations since Wigner [15]. In recent times, there have been a number of algorithms proposed to perform this task [1–3, 11, 12]. The issue of their computational complexity has received at-tention in the past, and was raised recently by E. Rassart in [11]. We prove that the problem of computing either quantity is #P-complete. Thus, unless P = NP, which is widely disbelieved, there do not exist efficient algorithms that compute these numbers.