Editing Champernowne constant

{{Short description|Transcendental number(s) with all positive integers  in order}}
In [[mathematics]], the '''Champernowne constant''' {{math|''C''<sub>10</sub>}} is a [[transcendental number|transcendental]] [[real number|real]] [[mathematical constant|constant]] whose decimal expansion has important properties.  It is named after economist and mathematician [[D. G. Champernowne]], who published it as an undergraduate in 1933.<ref name=Cha33>{{harvnb|Champernowne|1933}}</ref>  The number is defined by [[concatenation|concatenating]] the [[base-10]] representations of the positive integers:
:{{math|1=''C''<sub>10</sub> = 0.1234567891011121314151617181920... }} {{OEIS|A033307}}.

Champernowne constants can also be constructed in other bases similarly; for example,
:{{math|1=''C''<sub>2</sub> = 0.11011100101110111... <sub>2</sub>}}
and
:{{math|1=''C''<sub>3</sub> = 0.12101112202122... <sub>3</sub>}}.

The '''Champernowne word''' or '''Barbier word''' is the sequence of digits of ''C''<sub>10</sub> obtained by writing it in base 10 and juxtaposing the digits:<ref>Cassaigne & Nicolas (2010) p.165</ref><ref>{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [[Cambridge University Press]] | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 | page=299 }}</ref>

:{{math| 12345678910111213141516... }} {{OEIS|A007376}}

More generally, a ''Champernowne sequence'' (sometimes also called a ''Champernowne word'') is any sequence of digits obtained by concatenating all finite digit-strings (in any given base) in some recursive order.<ref>
{{citation
 | last1 = Calude | first1 = C. | author1-link = Cristian S. Calude
 | last2 = Priese | first2 = L. | author2-link = Lutz Priese
 | last3 = Staiger | first3 = L. | author3-link = Ludwig Staiger
 | publisher = University of Auckland, New Zealand
 | pages = 1–35
 | title = Disjunctive sequences: An overview
 | year = 1997 | citeseerx = 10.1.1.34.1370 }}</ref>
For instance, the binary Champernowne sequence in [[shortlex order]] is

:{{math|1= 0 1 00 01 10 11 000 001 ...}} {{OEIS|A076478}}
where spaces (otherwise to be ignored) have been inserted just to show the strings being concatenated.

== Properties ==
A [[real number]] ''x'' is said to be ''[[normal number|normal]]'' if its digits in every base follow a uniform distribution: all digits being equally likely, all pairs of digits equally likely, all triplets of digits equally likely, etc. A number ''x'' is said to be normal in [[radix|base]] ''b'' if its digits in base ''b'' follow a uniform distribution.

If we denote a digit string as [''a''<sub>0</sub>, ''a''<sub>1</sub>, ...], then, in base 10, we would expect strings [0], [1], [2], …, [9] to occur 1/10 of the time, strings [0,0], [0,1], ..., [9,8], [9,9] to occur 1/100 of the time, and so on, in a normal number.

Champernowne proved that <math>C_{10}</math> is normal in base 10,<ref name=Cha33>{{harvnb|Champernowne|1933}}</ref> while Nakai and Shiokawa proved a more general theorem, a corollary of which is that <math>C_{b}</math> is normal in base <math>b</math> for any ''b''.<ref name=Nak92>{{harvnb|Nakai|Shiokawa|1992}}</ref> It is an open problem whether <math>C_{k}</math> is normal in bases <math>b \neq k</math>. For example, it is not known if <math>C_{10}</math> is normal in base 9. For example, 54 digits of <math>C_{10}</math> is 0.123456789101112131415161718192021222324252627282930313. When we express this in base 9 we get <math>{0.10888888853823026326512111305027757201400001517660835887}_9</math>.

[[Kurt Mahler]] showed that the constant is [[transcendental number|transcendental]].<ref name="mahler">K.&nbsp;Mahler, ''Arithmetische Eigenschaften einer Klasse von Dezimalbrüchen'', Proc. Konin. Neder. Akad. Wet. Ser. A. 40 (1937), p.&nbsp;421–428.</ref>
The [[irrationality measure]] of <math>C_{10}</math> is <math>\mu(C_{10})=10</math>, and more generally <math>\mu(C_b)=b</math> for any base <math>b\ge 2</math>.<ref>[[Masaaki Amou]], ''[http://www.sciencedirect.com/science/article/pii/S0022314X05800393 Approximation to certain transcendental decimal fractions by algebraic numbers]'', [[Journal of Number Theory]], Volume 37, Issue 2, February 1991, Pages 231–241</ref>

The Champernowne word is a [[disjunctive sequence]]. A '''disjunctive sequence''' is an infinite [[Sequence#Infinite sequences in theoretical computer science|sequence]] (over a finite [[Alphabet (computer science)|alphabet]] of [[Character (computing)|characters]]) in which every [[String (computer science)#Formal theory|finite string]] appears as a [[substring]].

== Series ==
The definition of the Champernowne constant immediately gives rise to an [[infinite series]] representation involving a double sum,
<math display="block">C_{10}=\sum_{n=1}^\infty 10^{-\delta_{10}(n)} \sum_{k=10^{n-1}}^{10^n-1}\frac{k}{10^{n(k-10^{n-1}+1)}},</math> 
where <math>\delta_{10}(n)= 9\sum_{\ell=1}^{n-1}10^{\ell-1}\ell</math> is the number of digits between the decimal point and the first contribution from an {{mvar|n}}-digit base-10 number; these expressions generalize to an arbitrary base&nbsp;{{mvar|b}} by replacing 10 and 9 with {{mvar|b}} and {{math|''b'' − 1}} respectively. Alternative forms are
<math display="block">C_b=\sum_{n=1}^\infty n \cdot b^{-\left(\sum\limits_{k=1}^n\left\lceil\log_{b}(k+1)\right\rceil\right)}</math>
and
<math display="block">C_b=\sum_{n=1}^\infty n \cdot b^{-\left(n+\sum\limits_{k=1}^{n-1}\left\lfloor\log_b(k+1)\right\rfloor\right)},</math>
where <math>\lfloor x \rfloor</math> and <math>\lceil x \rceil</math> denote the [[floor and ceiling functions]].<ref>John K. Sikora: [https://arxiv.org/abs/1408.0261 Analysis of the High Water Mark Convergents of Champernowne's Constant in Various Bases], in: arXiv:1408.0261, 1 Aug 2014, see Definition 9</ref><ref>{{MathWorld|urlname=ChampernowneConstant|title=Champernowne constant}}</ref>

Returning to the first of these series, both the summand of the outer sum and the expression for <math>\delta_b(n)</math> can be simplified using the closed form for the [[Geometric_series#Nicole_Oresme_(c.1323_–_1382)|two-dimensional geometric series]]:
<math display="block">\sum_{k=n}^\infty ka^k=a^n\frac{n-(n-1)a}{(1-a)^2}.</math>

The resulting expression for <math>\delta_b(n)</math> is
<math display="block">\delta_b(n) = (b-1)\sum_{\ell=1}^{n-1}b^{\ell-1}\ell
 = \frac{1}{b-1}\left(1+b^{n-1}((b-1)n-b)\right),</math>
while the summand of the outer sum becomes
<math display="block">\begin{align}b^{-\delta_b(n)} \sum_{k=b^{n-1}}^{b^n-1}\frac{k}{b^{n(k-b^{n-1}+1)}}
 &= b^{-\delta_b(n)}b^{n(b^{n-1}-1)}\left(\sum_{k=b^{n-1}}^\infty\frac{k}{b^{nk}}-\sum_{k=b^n}^\infty\frac{k}{b^{nk}}\right)\\
 &= \frac{b^{2n-1}-b^{n-1}+1}{\left(b^n-1\right)^2}b^{-\delta_b(n)}-\frac{b^{2n}-b^n+1}{\left(b^n-1\right)^2}b^{-\delta_b(n+1)}.\end{align}</math>
Summing over all {{math|''n'' ≥ 1}} gives
<math display="block">C_b = \frac{b}{(b-1)^2}-\sum_{n=1}^\infty \left(\frac{b^{2n}-b^n+1}{\left(b^n-1\right)^2} - \frac{b^{2n+1}-b^n+1}{\left(b^{n+1}-1\right)^2}\right)b^{-\delta_b(n+1)}.</math>
Observe that in the summand, the expression in parentheses is approximately <math>\frac{b-1}{b}</math> for {{math|''n'' ≥ 2}} and rapidly approaches that value as {{math|''n''}} grows, while the exponent <math>\delta_b(n+1)</math> grows exponentially with {{math|''n''}}. As a consequence, each additional term provides an exponentially growing number of correct digits even though the number of digits in the numerators and denominators of the fractions comprising these terms grows only linearly. For example, the first few terms of {{math|''C''<sub>10</sub>}} are
<math display="block">C_{10} = \frac{10}{81} - \left[\left(\frac{91}{81}-\frac{991}{9801}\right)\times10^{-9}+\left(\frac{9901}{9801}-\frac{99901}{998001}\right)\times10^{-189}+\left(\frac{999001}{998001}-\frac{9999001}{99980001}\right)\times10^{-2889}+\ldots\right].</math>

== Continued fraction expansion ==
[[Image:Champernowne constant.svg|right|177x177px|thumb|The first 161 quotients of the continued fraction of the Champernowne constant. The 4th, 18th, 40th, and 101st are much bigger than 270, so do not appear on the graph.]]
[[Image:Champernowne constant logscale.svg|right|172x172px|thumb|The first 161 quotients of the continued fraction of the Champernowne constant on a [[logarithmic scale]].]]
The [[continued fraction|simple continued fraction]] expansion of Champernowne's constant does not [[continued fraction#Finite continued fractions|terminate]] (because the constant is not [[rational number|rational]]) and is [[continued fraction#Periodic continued fractions|aperiodic]] (because it is not an irreducible quadratic). A simple continued fraction is a continued fraction where the denominator is 1. The [[continued fraction|simple continued fraction]] expansion of Champernowne's constant exhibits extremely large terms appearing between many small ones. For example, in base 10,
: ''C''<sub>10</sub> = [0; 8, 9, 1, 149083, 1, 1, 1, 4, 1, 1, 1, 3, 4, 1, 1, 1, 15, 4 57540 11139 10310 76483 64662 82429 56118 59960 39397 10457 55500 06620 04393 09026 26592 56314 93795 32077 47128 65631 38641 20937 55035 52094 60718 30899 84575 80146 98631 48833 59214 17830 10987, 6, 1, 1, ...]. {{OEIS|id=A030167}}

The large number at position&nbsp;18 has 166 digits, and the next very large term at position&nbsp;40 of the continued fraction has 2504 digits. That there are such large numbers as terms of the continued fraction expansion means that the convergents obtained by stopping before these large numbers provide an exceptionally good [[diophantine approximation|approximation]] of the Champernowne constant. For example, truncating just before the 4th partial quotient, gives 
<math display="block">10/81 = \sum_{k=1}^\infty k/10^k = 0.\overline{123456790},</math>
which matches the first term in the rapidly converging series expansion of the previous section and which approximates Champernowne's constant with an error of about {{math|1 × 10<sup>−9</sup>}}. Truncating just before the 18th partial quotient gives an approximation that matches the first two terms of the series, that is, the terms up to the term containing {{math|10<sup>−9</sup>}},
<math display="block">
\begin{align}
\frac{60499999499}{490050000000} &= 0.123456789+10^{-9}\sum_{k=10}^\infty k/10^{2(k-9)}=0.123456789+10^{-9}\frac{991}{9801}\\
 &= 0.123456789\overline{10111213141516171819\ldots90919293949596979900010203040506070809},
\end{align}
</math>
which approximates Champernowne's constant with error approximately {{math|9 × 10<sup>−190</sup>}}.

The first and second incrementally largest terms ("high-water marks") after the initial zero are 8 and 9, respectively, and occur at positions 1 and 2. Sikora (2012) noticed that the number of digits in the high-water marks starting with the fourth display an apparent pattern.<ref>Sikora, J. K. "On the High Water Mark Convergents of Champernowne's Constant in Base Ten." 3 Oct 2012. http://arxiv.org/abs/1210.1263</ref> Indeed, the high-water marks themselves grow doubly-exponentially, and the number of digits <math>d_n</math> in the ''n''th mark for <math>n\geqslant 3</math> are

:6, 166, <span style="color: red;">25</span>04, <span style="color: red;">33</span><span style="color: blue;">102</span>, <span style="color: red;">41</span><span style="color: rgb(0, 128, 0);">1</span><span style="color: blue;">100</span>, <span style="color: red;">49</span><span style="color: rgb(0, 128, 0);">11</span><span style="color: blue;">098</span>, <span style="color: red;">57</span><span style="color: rgb(0, 128, 0);">111</span><span style="color: blue;">096</span>, <span style="color: red;">65</span><span style="color: rgb(0, 128, 0);">1111</span><span style="color: blue;">094</span>, <span style="color: red;">73</span><span style="color: rgb(0, 128, 0);">11111</span><span style="color: blue;">092</span>, ...

whose pattern becomes obvious starting with the 6th high-water mark. The number of terms can be given by
<math display="block"> d_n = \frac{44 - 103 \times 2^{n-3} \times 5^{n-4}}{9} + \left(2^{n-1} \times 5^{n-4} \times n - 2n\right)
,n\in\mathbb{Z}\cap\left[3,\infty\right).</math>

However, it is still unknown as to whether or not there is a way to determine where the large terms (with at least 6 digits) occur, or their values. The high-water marks themselves are located at positions

:1, 2, 4, 18, 40, 162, 526, 1708, 4838, 13522, 34062, .... {{OEIS|id=A143533}}

==See also==
*[[Copeland–Erdős constant]], a similar normal number, defined using the [[prime number]]s
*[[Liouville number#Liouville constant|Liouville's constant]], another constant defined by its decimal representation
*[[Smarandache–Wellin number]], another number obtained through concatenation a representation in a given base.

== References ==
{{reflist}}
* {{cite book | last1=Cassaigne | first1=J. | last2=Nicolas | first2=F. | chapter=Factor complexity | pages=163–247 | editor1-last=Berthé | editor1-first=Valérie |editor1-link= Valérie Berthé | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1216.68204  }}
*{{citation
 | last = Champernowne | first = D. G. | author-link = D. G. Champernowne
 | doi = 10.1112/jlms/s1-8.4.254
 | journal = [[London Mathematical Society|Journal of the London Mathematical Society]]
 | pages = 254–260
 | title = The construction of decimals normal in the scale of ten
 | volume = 8
 | year = 1933
 | issue = 4}}.
*{{citation
 | last1 = Nakai | first1 = Y.
 | last2 = Shiokawa | first2 = I.
 | journal = [[Acta Arithmetica]]
 | pages = 271–284
 | title = Discrepancy estimates for a class of normal numbers
 | volume = 62
 | issue = 3
 | year = 1992| doi = 10.4064/aa-62-3-271-284
 | doi-access = free
 }}.

[[Category:Mathematical constants]]
[[Category:Number theory]]
[[Category:Real transcendental numbers]]
[[Category:Sequences and series]]