Browse

1 - 10 of 71 items :

  • Numerical and Computational Mathematics x
  • Algebra and Number Theory x
  • Discrete Mathematics x
Clear All

Abstract

It was proved by Jang et al. that various chains of one-parameter distributions converge to Benford’s law. We study chains of truncated distributions and propose another approach, using a recent convergence result of the Lerch transcendent function, to proving that they converge to Benford’s law for initial Beta distributions with parameters α and 1.

Abstract

Let q be an integer greater than or equal to 2, and let S q(n)denote the sum of digits of n in base q.For

α=[0;1,m¯],m2,

let S α(n) denote the sum of digits in the Ostrowski α-representation of n. Let m 1,m 2 ≥ 2 be integers with

gcd(q-1,m1)=gcd(m,m2)=1

We prove that there exists δ> 0 such that for all integers r 1,r 2,

|{0n<N:Sq(n)r1(modm1),Sα(n)r2(modm2)}|=Nm1m2+0(N1-δ).

The asymptotic relation implied by this equality was proved by Coquet, Rhin & Toffin and the equality was proved for the case α=[1¯] by Spiegelhofer.

Abstract

Let X and Y be nonempty finite subsets of 𝕑 and X +Y its sumset. The structures of X and Y when r(X, Y ):= |X +Y |−|X|−|Y | is small have been widely studied; in particular the Generalized Freiman’s 3k − 4 Theorem describes X and Y when r(X, Y ) ≤ min{|X|, |Y |} − 4. However, not too much is known about X and Y when r(X, Y ) > min{|X|, |Y |} − 4. In this paper we study the structure of X and Y for arbitrary r(X, Y ).

Abstract

Let X 1,X 2,... be i.i.d. absolutely continuous random variables, let Sk=j=1kXj (mod 1) and let D* N denote the star discrepancy of the sequence (S k)1≤ k N. We determine the limit distribution of NDN* and the weak limit of the sequence N(FN(t)-t) in the Skorohod space D[0, 1], where F N (t) denotes the empirical distribution function of the sequence (S k)1≤ k N.

Abstract

Expansion complexity and maximum order complexity are both finer measures of pseudorandomness than the linear complexity which is the most prominent quality measure for cryptographic sequences. The expected value of the Nth maximum order complexity is of order of magnitude log N whereas it is easy to find families of sequences with Nth expansion complexity exponential in log N. This might lead to the conjecture that the maximum order complexity is a finer measure than the expansion complexity. However, in this paper we provide two examples, the Thue-Morse sequence and the Rudin-Shapiro sequence with very small expansion complexity but very large maximum order complexity. More precisely, we prove explicit formulas for their N th maximum order complexity which are both of the largest possible order of magnitude N. We present the result on the Rudin-Shapiro sequence in a more general form as a formula for the maximum order complexity of certain pattern sequences.

Abstract

In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and strongly pseudo-random graphs, respectively.)

Abstract

Flat tori are analyzed in the context of an intrinsic Fourier-analytic approach to electrostatics on Riemannian manifolds, introduced by one of the authors in 1984 and previously developed for compact hyperbolic manifolds. The approach covers a large class of repelling laws, but does not naturally include laws with singularities at the origin, for which possible accommodations are discussed in the final section of the paper.

Abstract

We show that for an arbitrary sequence of intervals I n with constant length c, there exist real numbers β such that for all n β n belongs to I n modulo one.

Abstract

We give a complete classification of all matrices C 1,C 2,C 3C3𝔽2m×m which generate a digital (0,m, 3)-net in base 2 and a complete classification of all matrices C 1,C 2C2𝔽2× which generate a digital (0, 2)-sequence in base 2.

Abstract

Given a subset A of the natural numbers 𝕅 = {0, 1, 2, ···} (resp. of the ring 𝕑/ N𝕑 of residue classes modulo a positive integer N), we introduce certain sums of roots of unity associated with A. We study some of their properties, and we use them to obtain new expressions for the classical functions that characterize A, i.e. of the representation function, the counting function and the characteristic function of A. We also give an example of computations of the representation function using such expressions.