Unbalanced digit sets and the closest choice strategy for minimal weight integer representations

An algorithm is presented that produces an optimal radix-2 representation of an input integer n using digits from the set , where ℓ ≤ 0 and u ≥ 1. The algorithm works by scanning the digits of the binary representation of n from left-to-right (i.e., from most-significant to least-significant); further, the algorithm is of the online variety in that it needs to scan only a bounded number of input digits before giving an output digit (i.e., the algorithm produces output before scanning the entire input). The output representation is optimal in the sense that, of all radix-2 representations of n with digits from D _ℓ,u , it has as few nonzero digits as possible (i.e., it has minimal weight). Such representations are useful in the efficient implementation of elliptic curve cryptography. The strategy the algorithm utilizes is to choose an integer of the form d 2 ⁱ , where , that is closest to n with respect to a particular distance function. It is possible to choose values of ℓ and u so that the set D _ℓ,u is unbalanced in the sense that it contains more negative digits than positive digits, or more positive digits than negative digits. Our distance function takes the possible unbalanced nature of D _ℓ,u into account.      

Multiplicative character sums with the sum of g-ary Digits Function

We establish upper bounds for multiplicative character sums with the function σ_g (n) which computes the sum of the digits of n in a fixed base g ≥ 2. Our results may be viewed as analogues of some previously known results for exponential sums with sum of g-ary digits function. 2000 Mathematics Subject Classification Primary—11A63, 11B50, 11L40     

On the Distribution in Residue Classes of Integers with a Fixed Sum of Digits

We give an asymptotic formula for the distribution of those integers n in a residue class, such that n has a fixed sum of base-g digits, with some uniformity over the choice of the modulus and g. We then use this formula to solve the problem of I. Niven of giving an asymptotic formula for the distribution of those integers n divisible by the sum of their base-g digits. Our results also allow us to give a stronger form of a result of M. Olivier dealing with the distribution of integers with a given gcd with their sum of base-g digits.For our friend Jean-Louis Nicolas on his sixtieth birthdayResearch partially supported by the Hungarian National Foundation for Scientific Research, Grant No. T029759, and “Balaton” French-Hungarian exchange program F-18/00.2000 Mathematics Subject Classification: Primary—11A63     

General algorithm of computation of <Emphasis Type="Italic">c</Emphasis>-table and detection of valleys

We present a review of all interesting results concerning the c-table obtained by the authors for the last two decades. These results are not widely known because they were presented in publications of limited circulation. We discuss different computational aspects of software producing the c-tables in the presence of blocs and their evolution following the evolution of the computer environment: effects of the use of 32-bit arithmetic .≈8 digits), 64-bit arithmetic (double precision, ≈16 digits), and Bailey’s Fortran multiprecision package .32 or 64 digits), competition between the ascending and descending algorithms, relationship between the complexity of computation and precision, overflow and underflow problems, competition between different formulas allowing one to overcome the blocs in the c-table, practical simple criterion of detecting numerical zeros in the c-table allowing to identify the blocs, and automatic detection of valleys.     

Minimal expansions in redundant number systems: Fibonacci bases and Greedy algorithms

We study digit expansions with arbitrary integer digits in base q (q integer) and the Fibonacci base such that the sum of the absolute values of the digits is minimal. For the Fibonacci case, we describe a unique minimal expansion and give a greedy algorithm to compute it. Additionally, transducers to calculate minimal expansions from other expansions are given. For the case of even integer bases q, similar results are given which complement those given in [6].     

ON THE ASYMPTOTIC BEHAVIOUR OF THE DIGITS OF CONTINUED FRACTIONS WITH ODD PARTIAL QUOTIENTS

Abstract

The asymptotic behaviour of the digits a_n and e_n of continued fractions with odd partial quotients is investigated in the context of dependence with complete connections. In particular, we obtain a formula for the geometric mean of partial denominators and the relative frequency of a pair (a, ε) of digits.     

Frequencies of digits, divergence points, and Schmidt games

Sets of divergence points, i.e. numbers x (or tuples of numbers) for which the limiting frequency of a given string of N-adic digits of x fails to exist, have recently attracted huge interest in the literature. In this paper we consider sets of simultaneous divergence points, i.e. numbers x (or tuples of numbers) for which the limiting frequencies of all strings of N-adic digits of x fail to exist. We show that many natural sets of simultaneous divergence points are (α, β)-wining sets in the sense of the Schmidt game. As an application we obtain lower bounds for the Hausdorff dimension of these sets.     

Exponential sums and prime divisors of sparse integers

We obtain a new lower bound on the number of prime divisors of integers whose g-ary expansion contains a fixed number of nonzero digits.      

On the Hausdorff dimension of generalized Besicovitch-Eggleston sets of d-tuples of numbers

We give a systematic and detailed account of the Hausdorff dimensions of sets of d-tuples of numbers defined in terms of the asymptotic behaviour of the frequencies of strings of digits in their N-adic expansion.     

Computing denumerants in numerical 3-semigroups

Abstract

As far as we know, usual computer algebra packages can not compute denumerants for almost medium (about a hundred digits) or almost medium-large (about a thousand digits) input data in a reasonably time cost on an ordinary computer. Implemented algorithms can manage numerical n-semigroups for small input data.

Basically, the denumerant of a non-negative element s ∈ ? is the number of non-negative integer solutions of certain linear non-negative Diophantine equation which constant term is equal to s.

Here we are interested in denumerants of numerical 3-semigroups which have almost medium input data. A new algorithm for computing denumerants is given for this task. It can manage almost medium input data in the worst case and medium-large or even large input data in some cases.     

Singular Probability Distributions and Fractal Properties of Sets of Real Numbers Defined by the Asymptotic Frequencies of Their <Emphasis Type="Italic">s</Emphasis>-Adic Digits

Properties of the set T _s of “particularly nonnormal numbers” of the unit interval are studied in detail (T _s consists of real numbers x some of whose s-adic digits have the asymptotic frequencies in the nonterminating s-adic expansion of x, and some do not). It is proved that the set T _s is residual in the topological sense (i.e., it is of the first Baire category) and is generic in the sense of fractal geometry (T _s is a superfractal set, i.e., its Hausdorff-Besicovitch dimension is equal to 1). A topological and fractal classification of sets of real numbers via analysis of asymptotic frequencies of digits in their s-adic expansions is presented. Dedicated to V. S. Korolyuk on occasion of his 80th birthday __________ Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 9, pp. 1163–1170, September, 2005.     

Transformations preserving the Hausdorff-Besicovitch dimension

Continuous transformations preserving the Hausdorff-Besicovitch dimension (“DP-transformations”) of every subset of R ¹ resp. [0, 1] are studied. A class of distribution functions of random variables with independent s-adic digits is analyzed. Necessary and sufficient conditions for dimension preservation under functions which are distribution functions of random variables with independent s-adic digits are found. In particular, it is proven that any strictly increasing absolutely continuous distribution function from the above class is a DP-function. Relations between the entropy of probability distributions, their Hausdorff-Besicovitch dimension and their DP-properties are discussed. Examples are given of singular distribution functions preserving the fractal dimension and of strictly increasing absolutely continuous functions which do not belong to the DP-class.      

A dimension gap for continued fractions with independent digits

Kinney and Pitcher (1966) determined the dimension of measures on [0, 1] which make the digits in the continued fraction expansion i.i.d. variables. From their formula it is not clear that these dimensions are less than 1, but this follows from the thermodynamic formalism for the Gauss map developed by Walters (1978). We prove that, in fact, these dimensions are bounded by 1−10⁻⁷. More generally, we considerf-expansions with a corresponding absolutely continuous measureμ under which the digits form a stationary process. Denote byE _δ the set of reals where the asymptotic frequency of some digit in thef-expansion differs by at leastδ from the frequency prescribed byμ. ThenE _δ has Hausdorff dimension less than 1 for anyδ>0.     

Asymptotic properties of digit sequences of random numbers

We consider several aspects of the relationship between a [0, 1]‐valued random variable X and the random sequence of digits given by its m‐ary expansion. We present results for three cases: (a) independent and identically distributed digit sequences; (b) random variables X with smooth densities; (c) stationary digit sequences. In the case of i.i.d. an integral limit thorem is proved which applies for example to relative frequencies, yielding asymptotic moment identities. We deal with occurrence probabilities of digit groups in the case that X has an analytic Lebesgue density. In the case of stationary digits we determine the distribution of X in terms of their transition functions. We study an associated [0, 1]‐valued Markov chain, in particular its ergodicity, and give conditions for the existence of stationary digit sequences with prespecified transition functions. It is shown that all probability measures induced on [0, 1] by such sequences are purely singular except for the uniform distribution. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The generalized Oppenheim expansions for the direct product of non-Archimedean fields

The well-known Oppenheim expansion algorithm in the field ℚ _p is generalized to the ring ℚ _g , where g = p ₁ · ... · p _N . The metric properties of the digits of this expansion and also the metric properties of the coefficients of some expansions of polyadic numbers are studied.     

Recursive events in random sequences

Let ω be a Kolmogorov–Chaitin random sequence with ω_{1: n} denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω_{1: n} )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. Received: 1 December 1998 / Published online: 3 October 2001     

On the number of nonzero digits of the partition function

Let p(n) be the function that counts the number of partitions of n. Let b ≥ 2 be a fixed positive integer. In this paper, we show that for almost all n the sum of the digits of p(n) in base b is at least log n/(7log log n). Our proof uses the first term of Rademacher’s formula for p(n).     

Practical problems arising for finding roots of nonlinear equations

Consider the numerical solutions of a nonlinear equation f(x)=0. We apply Newton's and Newton's-like methods to solve the equation.First, we discuss the attainable correct digits for the approximated root. Second, we give a practical termination criterion and the method to estimate the accuracy of the obtained root. Some numerical examples are presented.     

Poisson approximation for the number of large digits of inhomogeneousf-expansions

We determine the exact rate of Poisson approximation and give a second-order Poisson-Charlier expansion for the number of excedances of a given levelL _n among the firstn digits of inhomogeneousf-expansions of real numbers in the unit interval. The application of this general result to homogeneousf-expansions and, in particular, to regular continued fraction expansions provides not only a generalization but also a strengthening of a classical Poisson limit theorem due to W. Doeblin.     

Prime divisors of sparse integers

We obtain a lower bound on the number of prime divisors of integers whose g-ary expansion contains a fixed number of nonzero digits. This revised version was published online in August 2006 with corrections to the Cover Date.