# Volume 14 (2019): Issue 2 (December 2019)

Journal Details
Format
Journal
eISSN
2309-5377
First Published
30 Dec 2013
Publication timeframe
2 times per year
Languages
English

#### Search

8 Articles Open Access

#### Joint Distribution in Residue Classes of the Base-q and Ostrowski Digital Sums

Published Online: 27 Mar 2020
Page range: 1 - 26

#### Abstract

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

α=[0;1,m¯],m2,\alpha = \left[ {0;\overline {1,m} } \right],\,\,\,m \ge 2,

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

gcd(q-1,m1)=gcd(m,m2)=1\gcd \left( {q - 1,{m_1}} \right) = \gcd \left( {m,{m_2}} \right) = 1

We prove that there exists δ> 0 such that for all integers r1,r2,

|{0n<N:Sq(n)r1(modm1),Sα(n)r2(modm2)}|=Nm1m2+0(N1-δ).\matrix{ {\left| {\left\{ {0 \le n < N:{S_q}(n) \equiv {r_1}\left( {\bmod \,{m_1}} \right),\,\,{S_\alpha }(n) \equiv {r_2}\left( {\bmod \,{m_2}} \right)} \right\}} \right|} \cr { = {N \over {{m_1}{m_2}}} + 0\left( {{N^{1 - \delta }}} \right).} \cr }

The asymptotic relation implied by this equality was proved by Coquet, Rhin & Toffin and the equality was proved for the case α=[1¯]\alpha = \left[ {\bar 1} \right] by Spiegelhofer.

#### Keywords

• Ostrowski representation
• Sum of digits function
• Joint distribution

#### MSC 2010

• 11N64
• 11N69
• 11A63 Open Access

#### Chains of Truncated Beta Distributions and Benford’s Law

Published Online: 27 Mar 2020
Page range: 27 - 32

#### 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.

#### Keywords

• Benford’s law
• beta distribution

#### MSC 2010

• 11K06
• 60A10 Open Access

#### On the Maximum Order Complexity of the Thue-Morse and Rudin-Shapiro Sequence

Published Online: 27 Mar 2020
Page range: 33 - 42

#### 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.

#### Keywords

• Thue-Morse sequence
• Rudin-Shapiro sequence
• automatic sequences
• maximum order complexity
• measures of pseudorandomness

#### MSC 2010

• 11B85
• 11K45 Open Access

#### On Freiman’s 3k − 4 Theorem

Published Online: 27 Mar 2020
Page range: 43 - 68

#### 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 ).

#### Keywords

• Freiman’s 3 − 4 Theorem
• sumset
• Lev-Smeliansky Theorem

#### MSC 2010

• Primary 11B13
• Secondary 11B75 Open Access

#### Sur Les Parties Fractionnaires Des Suites (βn)n≥1

Published Online: 27 Mar 2020
Page range: 69 - 72

#### Abstract

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

#### Keywords

• Distribution modulo one
• sequence of intervals
• exponential sequence

#### MSC 2010

• Primary 11K06
• 11J71 Open Access

#### On the Discrepancy of Random Walks on the Circle

Published Online: 27 Mar 2020
Page range: 73 - 86

#### Abstract

Let X1,X2,... be i.i.d. absolutely continuous random variables, let Sk=j=1kXj{S_k} = \sum\nolimits_{j = 1}^k {{X_j}} (mod 1) and let D*N denote the star discrepancy of the sequence (Sk)1≤kN. We determine the limit distribution of NDN*\sqrt N D_N^* and the weak limit of the sequence N(FN(t)-t)\sqrt N \left( {{F_N}(t) - t} \right) in the Skorohod space D[0, 1], where FN (t) denotes the empirical distribution function of the sequence (Sk)1≤kN.

#### Keywords

• i.i.d. sums mod 1
• empirical distribution
• discrepancy
• weak convergence

#### MSC 2010

• 11K38
• 60G50
• 60F17 Open Access

#### Stable Configurations of Repelling Points on Flat Tori

Published Online: 27 Mar 2020
Page range: 87 - 102

#### 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.

#### Keywords

• electrostatics
• tori

#### MSC 2010

• 11N64
• 11N69
• 11A63 Open Access

#### Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Published Online: 27 Mar 2020
Page range: 103 - 126

#### 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.)

#### Keywords

• quasi-random graph
• pseudo-random graph
• pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528

• 05C80