<abstract><title style='display:none'>Abstract</title> Let f(x) be a monic polynomial in Z[x] with roots α1, . . ., αn. We point out the importance of linear relations among 1, α1, . . . , αn over rationals with respect to the distribution of local roots of f modulo a prime. We formulate it as a conjectural uniform distribution in some sense, which elucidates data in previous papers.</abstract>

Notes on the Distribution of Roots Modulo a Prime of a Polynomial

<abstract><title style='display:none'>Abstract</title>A recent paper by P. Lafrance, N. Rampersad, and R. Yee studies the sequence of occurrences of 10 as a scattered subsequence in the binary expansion of integers. They prove in particular that the summatory function of this sequence has the “root <italic>N</italic>” property, analogously to the summatory function of the Golay-Shapiro sequence. We prove here that the root <italic>N</italic> property does not hold if we twist the sequence by powers of a complex number of modulus one, hence showing a fundamental difference with the Golay-Shapiro sequence.</abstract>

On a Golay-Shapiro-Like Sequence

<abstract><title style='display:none'>Abstract</title> Denote by Θ1,Θ2, · · · the sequence of approximation coefficients of Minkowski’s diagonal continued fraction expansion of a real irrational number x. For almost all x this is a uniformly distributed sequence in the interval [0, 1/2 ]. The average distance between two consecutive terms of this sequence and their correlation coefficient are explicitly calculated and it is shown why these two values are close to 1/6 and 0, respectively, the corresponding values for a random sequence in [0, 1/2].</abstract>

A Note on the Continued Fraction of Minkowski

<abstract><title style='display:none'>Abstract</title>We study several pseudorandom properties of the Liouville function and the Möbius function of polynomials over a finite field. More precisely, we obtain bounds on their balancedness as well as their well-distribution measure, correlation measure, and linear complexity profile.</abstract>

On the Pseudorandomness of the Liouville Function of Polynomials over a Finite Field

<abstract><title style='display:none'>Abstract</title>The Bernoulli convolution associated to the real <italic>β</italic> &gt; 1 and the probability vector (<italic>p</italic>0, . . . , <italic>pd</italic>−1) is a probability measure <italic>ηβ,p</italic> on ℝ, solution of the self-similarity relation <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0015_eq_001.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>η</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo>⋅</mml:mo><mml:mi>η</mml:mi><mml:mi>○</mml:mi><mml:msubsup><mml:mi>S</mml:mi><mml:mi>k</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup></mml:mrow></mml:mstyle></mml:math><tex-math>$\eta = \sum\nolimits_{k = 0}^{d - 1} {p_k \cdot \eta \circ S_k^{ - 1} } $</tex-math></alternatives></inline-formula>, where <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0015_eq_002.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msub><mml:mi>S</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mi>x</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow><mml:mi>β</mml:mi></mml:mfrac></mml:math><tex-math>$S_k (x) = {{x + k} \over \beta }$</tex-math></alternatives></inline-formula>. If <italic>β</italic> is an integer or a Pisot algebraic number with finite Rényi expansion, <italic>ηβ,p</italic> is sofic and a Markov chain is naturally associated. If <italic>β</italic> = <italic>b</italic> ∈ ℕ and <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0015_eq_003.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msub><mml:mi>p</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo>⋯</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>d</mml:mi></mml:mfrac></mml:math><tex-math>$p_0 = \cdots = p_{d - 1} = {1 \over d}$</tex-math></alternatives></inline-formula>, the study of <italic>ηb,p</italic> is close to the study of the order of growth of the number of representations in base <italic>b</italic> with digits in {0, 1, . . . , <italic>d</italic> − 1}. In the case <italic>b</italic> = 2 and <italic>d</italic> = 3 it has also something to do with the metric properties of the continued fractions.</abstract>

Sofic Measures and Densities of Level Sets

<abstract><title style='display:none'>Abstract</title> Continuing the previous paper, we give several data on the distribution of roots modulo primes of an irreducible polynomial, and based on them, we propose problems on the distribution.</abstract>

Statistical Distribution of Roots of a Polynomial Modulo Primes II

<abstract>
<title style='display:none'>Abstract</title>
For polynomials <italic>f</italic> (<italic>x</italic>),<italic>g</italic>1(<italic>x</italic>),<italic>g</italic>2(<italic>x</italic>)over ℤ, we report several observations about the density of primes <italic>p</italic> for which <italic>f</italic> (<italic>x</italic>) is fully splitting at <italic>p</italic> and <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2023-0002_eq_001.png"/>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:mrow><mml:mo>{</mml:mo> <mml:mrow><mml:mfrac><mml:mrow><mml:msub><mml:mrow><mml:mi>g</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>r</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow> <mml:mo>}</mml:mo></mml:mrow><mml:mo>&lt;</mml:mo><mml:mrow><mml:mo>{</mml:mo> <mml:mrow><mml:mfrac><mml:mrow><mml:msub><mml:mrow><mml:mi>g</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>r</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow> <mml:mo>}</mml:mo></mml:mrow></mml:mrow></mml:math>
<tex-math>\left\{ {{{{g_1}\left( r \right)} \over p}} \right\} &lt; \left\{ {{{{g_2}\left( r \right)} \over p}} \right\}</tex-math>
</alternatives>
</inline-formula> for some root <italic>r</italic> of <italic>f</italic> (<italic>x</italic>) ≡ 0 mod <italic>p</italic>.
</abstract>

Notes on the Distribution of Roots Modulo Primes of a Polynomial IV

<abstract>
<title style='display:none'>Abstract</title>
In 1895, Vahlen proved a theorem concerning a simultaneous approximation of a real number by its two consecutive convergent. In this paper, we will provide a sharper bound for the theorem.
</abstract>

Refinement of the Theorem of Vahlen

<abstract>
<title style='display:none'>Abstract</title>
In this paper, we study an efficient algorithm for constructing point sets underlying quasi-Monte Carlo integration rules for weighted Korobov classes. The algorithm presented is a reduced fast component-by-component digit-by-digit (CBC-DBD) algorithm, which is useful for situations where the weights in the function space show a sufficiently fast decay. The advantage of the algorithm presented here is that the computational effort can be independent of the dimension of the integration problem to be treated if suitable assumptions on the integrand are met. By considering a reduced digit-by-digit construction, we allow an integration algorithm to be less precise with respect to the number of bits in those components of the problem that are considered less important. The new reduced CBC-DBD algorithm is designed to work for the construction of lattice point sets, and the corresponding integration rules (so-called lattice rules) can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithm satisfy error bounds of almost optimal convergence order. Furthermore, we give details on an efficient implementation such that we obtain a considerable speed-up of a previously known CBC-DBD algorithm that has been studied in the paper <italic>Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness</italic> by Ebert, Kritzer, Nuyens, and Osisiogu, published in the Journal of Complexity in 2021. This improvement is illustrated by numerical results.
</abstract>

On a Reduced Component-by-Component Digit-by-Digit Construction of Lattice Point Sets

<abstract>
<title style='display:none'>Abstract</title>
For a probability measure <italic>μ</italic> on [0, 1] without discrete component, the best possible order of approximation by a finite point set in terms of the star-discrepancy is &amp;inline as has been proven relatively recently. However, if <italic>μ</italic> contains a discrete component no non-trivial lower bound holds in general because it is straightforward to construct examples without any approximation error in this case. This might explain, why the approximation of discrete measures on [0, 1] by finite point sets has so far not been completely covered in the existing literature. In this note, we close the gap by giving a complete description for discrete measures. Most importantly, we prove that for any discrete measures (not supported on one point only) the best possible order of approximation is for infinitely many <italic>N</italic> bounded from below by &amp;inline for some constant 6 ≥ <italic>c&gt;</italic> 2 which depends on the measure. This implies, that for a finitely supported discrete measure on [0, 1]d the known possible order of approximation &amp;inline is indeed the optimal one.
</abstract>

Approximation of Discrete Measures by Finite Point Sets

<abstract>
<title style='display:none'>Abstract</title>
It is important in cryptographic applications that the “key” used should be generated from a random seed. Thus, if the Legendre symbol sequence generated by a polynomial (as proposed by Hoffstein and Lieman) is used, that is
<disp-formula>
<alternatives>
<graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2023-0006_eq_001.png"/>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mml:mrow><mml:mrow><mml:mo>{</mml:mo> <mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>,</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>,</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>3</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>,</mml:mo><mml:mo>⋯</mml:mo><mml:mo>,</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mi>p</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow> <mml:mo>}</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math>
<tex-math>\left\{ {\left( {{{f\left( 1 \right)} \over p}} \right),\left( {{{f\left( 2 \right)} \over p}} \right),\left( {{{f\left( 3 \right)} \over p}} \right), \cdots ,\left( {{{f\left( p \right)} \over p}} \right)} \right\},</tex-math>
</alternatives>
</disp-formula>
then it is important to choose the polynomial <italic>f</italic> “almost” at random. Goubin, Mauduit, and Sárközy presented some not very restrictive conditions on the polynomial <italic>f</italic>, but these conditions may not be satisfied if we choose a “truly” random polynomial. However, how can it be guaranteed that the pseudorandom measures of the sequence should be small for almost "random" polynomials? These semirandom polynomials will be constructed with as few modifications as necessary from a truly random polynomial.
</abstract>

Random Polynomials in Legendre Symbol Sequences

<abstract>
<title style='display:none'>Abstract</title>
We give a necessary and sufficient condition for equidistribution of continuous functions along monotone compact covers on locally compact spaces. We show the existence of equidistributed mappings along Bohr nets arising from group actions. Using almost periodic means, we give an analogue of Weyl’s equidistribution criterion for continuous functions with values in arbitrary topological groups. We prove van der Corput’s inequality on the lattice ℕm for vectors in Hilbert spaces, and use this inequality to extend Hlawka’s equidistribution theorem to functions on the lattice ℕm (<italic>m</italic> ≥ 1) with values in arbitrary topological groups.
</abstract>

Equidistribution of Continuous Functions Along Monotone Compact Covers

<abstract><title style='display:none'>Abstract</title>It is known that there is a constant <italic>c</italic> &gt; 0 such that for every sequence <italic>x</italic>1, <italic>x</italic>2, . . . in [0, 1) we have for the star discrepancy <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0001_eq_001.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>D</mml:mi><mml:mi>N</mml:mi><mml:mo>*</mml:mo></mml:msubsup></mml:math><tex-math>$D_N^* $</tex-math></alternatives></inline-formula> of the first <italic>N</italic> elements of the sequence that <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0001_eq_002.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>ND</mml:mi><mml:mi>N</mml:mi><mml:mo>*</mml:mo></mml:msubsup><mml:mo>≥</mml:mo><mml:mi>c</mml:mi><mml:mo>⋅</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>N</mml:mi></mml:math><tex-math>$ND_N^* \ge c \cdot \log N$</tex-math></alternatives></inline-formula> holds for infinitely many <italic>N</italic>. Let <italic>c</italic>∗ be the supremum of all such <italic>c</italic> with this property. We show <italic>c</italic>∗ &gt; 0.065664679 . . . , thereby slightly improving the estimates known until now.</abstract>

Institute of Financial Mathematics and Applied Number Theory, University Linz, Altenbergerstraße 69, 4040 Linz,

An Improved Bound for the Star Discrepancy of Sequences in the Unit Interval

<abstract><title style='display:none'>Abstract</title>Quantization for a probability distribution refers to the idea of estimating a given probability by a discrete probability supported by a finite number of points. In this paper, firstly a general approach to this process is outlined using independent random variables and ergodic maps; these give asymptotically the optimal sets of <italic>n</italic>-means and the <italic>n</italic>th quantization errors for all positive integers <italic>n</italic>. Secondly two piecewise uniform distributions are considered on R: one with infinite number of pieces and one with finite number of pieces. For these two probability measures, we describe the optimal sets of <italic>n</italic>-means and the <italic>n</italic>th quantization errors for all <italic>n</italic> ∈ N. It is seen that for a uniform distribution with infinite number of pieces to determine the optimal sets of <italic>n</italic>-means for <italic>n ≥</italic> 2 one needs to know an optimal set of (<italic>n −</italic> 1)-means, but for a uniform distribution with finite number of pieces one can directly determine the optimal sets of <italic>n</italic>-means and the <italic>n</italic>th quantization errors for all <italic>n</italic> ∈ N.</abstract>

Optimal Quantization for Piecewise Uniform Distributions

<abstract><title style='display:none'>Abstract</title>This paper concerns the problem of determining or estimating the maximal upper density of the sets of nonnegative integers <italic>S</italic> whose elements do not differ by an element of a given set <italic>M</italic> of positive integers. We find some exact values and some bounds for the maximal density when the elements of <italic>M</italic> are generalized Fibonacci numbers of odd order. The generalized Fibonacci sequence of order <italic>r</italic> is a generalization of the well known Fibonacci sequence, where instead of starting with two predetermined terms, we start with <italic>r</italic> predetermined terms and each term afterwards is the sum of <italic>r</italic> preceding terms. We also derive some new properties of the generalized Fibonacci sequence of order <italic>r</italic>. Furthermore, we discuss some related coloring parameters of distance graphs generated by the set <italic>M</italic>.</abstract>

Motzkin’s Maximal Density and Related Chromatic Numbers

<abstract><title style='display:none'>Abstract</title>Let <italic>n ≥</italic> 2 be an integer and denote by <italic>θn</italic> the real root in (0, 1) of the trinomial <italic>Gn</italic>(<italic>X</italic>) = −1 + <italic>X</italic> + <italic>Xn</italic>. The sequence of Perron numbers <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0006_eq_001.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>θ</mml:mi><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math><tex-math>$(\theta _n^{ - 1} )_{n \ge 2} $</tex-math></alternatives></inline-formula> tends to 1. We prove that the Conjecture of Lehmer is true for <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0006_eq_002.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>{</mml:mo><mml:msubsup><mml:mi>θ</mml:mi><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>|</mml:mo><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn><mml:mo>}</mml:mo></mml:math><tex-math>$\{ \theta _n^{ - 1} |n \ge 2\} $</tex-math></alternatives></inline-formula> by the direct method of Poincaré asymptotic expansions (divergent formal series of functions) of the roots <italic>θn</italic>, <italic>zj,n</italic>, of <italic>Gn</italic>(<italic>X</italic>) lying in <italic>|z|</italic> &lt; 1, as a function of <italic>n, j</italic> only. This method, not yet applied to Lehmer’s problem up to the knowledge of the author, is successfully introduced here. It first gives the asymptotic expansion of the Mahler measures <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0006_eq_003.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>M</mml:mtext><mml:mo>(</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>)</mml:mo><mml:mo>=</mml:mo><mml:mtext>M</mml:mtext><mml:mo>(</mml:mo><mml:msub><mml:mi>θ</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>)</mml:mo><mml:mo>=</mml:mo><mml:mtext>M</mml:mtext><mml:mo>(</mml:mo><mml:msubsup><mml:mi>θ</mml:mi><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>)</mml:mo></mml:math><tex-math>${\rm{M}}(G_n ) = {\rm{M}}(\theta _n ) = {\rm{M}}(\theta _n^{ - 1} )$</tex-math></alternatives></inline-formula> of the trinomials <italic>Gn</italic> as a function of <italic>n</italic> only, without invoking Smyth’s Theorem, and their unique limit point above the smallest Pisot number. Comparison is made with Smyth’s, Boyd’s and Flammang’s previous results. By this method we obtain a direct proof that the conjecture of Schinzel-Zassenhaus is true for <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0006_eq_004.png"/><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>{</mml:mo><mml:msubsup><mml:mi>θ</mml:mi><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>|</mml:mo><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn><mml:mo>}</mml:mo></mml:math><tex-math>$\{ \theta _n^{ - 1} |n \ge 2\} $</tex-math></alternatives></inline-formula>, with a minoration of the house <inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2016-0006_eq_005.png"/>, and a minoration of the Mahler measure M(<italic>Gn</italic>) better than Dobrowolski’s one. The angular regularity of the roots of <italic>Gn</italic>, near the unit circle, and limit equidistribution of the conjugates, for <italic>n</italic> tending to infinity (in the sense of Bilu, Petsche, Pritsker), towards the Haar measure on the unit circle, are described in the context of the Erdős-Turán-Amoroso-Mignotte theory, with uniformly bounded discrepancy functions.</abstract>

On the Conjecture of Lehmer, Limit Mahler Measure of Trinomials and Asymptotic Expansions

<abstract><title style='display:none'>Abstract</title>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 <italic>N</italic>th maximum order complexity is of order of magnitude log <italic>N</italic> whereas it is easy to find families of sequences with <italic>N</italic>th expansion complexity exponential in log <italic>N</italic>. 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 <italic>N</italic> th maximum order complexity which are both of the largest possible order of magnitude <italic>N</italic>. 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>

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

Introduction

Uniform distribution theory

The Journal of Slovak Academy of Sciences

 The journal is published by:Institute of Mathematics of the Slovak Academy of Sciences, (Bratislava, Slovakia)  The aim of this journal is to publish...

 The journal is published by:Institute of Mathematics of the Slovak Academy of Sciences, (Bratislava, Slovakia) ...

AHEAD OF PRINT

Volume 18 (2023): Issue 1 (July 2023)

Volume 17 (2022): Issue 2 (December 2022)

Volume 17 (2022): Issue 1 (May 2022)

Volume 16 (2021): Issue 2 (December 2021)

Volume 16 (2021): Issue 1 (June 2021)

Volume 15 (2020): Issue 2 (December 2020)

Volume 15 (2020): Issue 1 (June 2020)

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

Volume 14 (2019): Issue 1 (June 2019) The sixth International Conference on Uniform Distribution Theory (UDT 2018) CIRM, Luminy, Marseilles, France, October 1–5, 2018