{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:47Z","timestamp":1776802547819,"version":"3.51.2"},"reference-count":24,"publisher":"American Mathematical Society (AMS)","issue":"308","license":[{"start":{"date-parts":[[2018,3,29]],"date-time":"2018-03-29T00:00:00Z","timestamp":1522281600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100002923","name":"Consejo Nacional de Investigaciones Cient\u00c3\u00adficas y T\u00c3\u00a9cnicas","doi-asserted-by":"publisher","award":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"],"award-info":[{"award-number":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"]}],"id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003074","name":"Agencia Nacional de Promoci\u00c3\u00b3n Cient\u00c3\u00adfica y Tecnol\u00c3\u00b3gica","doi-asserted-by":"publisher","award":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"],"award-info":[{"award-number":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002923","name":"Consejo Nacional de Investigaciones Cient\u00c3\u00adficas y T\u00c3\u00a9cnicas","doi-asserted-by":"publisher","award":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"],"award-info":[{"award-number":["PICT 002014-\u00c3\u0083\u00c2\u00a2\u00c3\u0082\u00c2\u0081\u00c3\u0082\u00c2 3260"]}],"id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Among the currently known constructions of absolutely normal numbers, the one given by Mordechay\u00a0Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give the digits of the fractional expansion explicitly, but it gives a sequence of increasing approximations whose limit is the announced absolutely normal number. The\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -th approximation has an error less than\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"2 Superscript minus 2 Super Superscript n\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\n                                \u2212\n                                \n                              <\/mml:mo>\n                              <mml:msup>\n                                <mml:mn>2<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mi>n<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">2^{-2^{n}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . To obtain the\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -th approximation the construction requires, in the worst case, a number of mathematical operations that is doubly exponential in\u00a0\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy.\n                  <\/p>","DOI":"10.1090\/mcom\/3188","type":"journal-article","created":{"date-parts":[[2016,6,8]],"date-time":"2016-06-08T09:41:48Z","timestamp":1465378908000},"page":"2927-2946","source":"Crossref","is-referenced-by-count":0,"title":["M. Levin\u2019s construction of absolutely normal numbers with very low discrepancy"],"prefix":"10.1090","volume":"86","author":[{"given":"Nicol\u00e1s","family":"\u00c1lvarez","sequence":"first","affiliation":[]},{"given":"Ver\u00f3nica","family":"Becher","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2017,3,29]]},"reference":[{"key":"1","isbn-type":"print","volume-title":"Handbook of mathematical functions with formulas, graphs, and mathematical tables","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0486612724"},{"issue":"1-2","key":"2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00208-015-1209-9","article-title":"On simply normal numbers to different bases","volume":"364","author":"Becher, Ver\u00f3nica","year":"2016","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"issue":"1-2","key":"3","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1016\/S0304-3975(01)00170-0","article-title":"An example of a computable absolutely normal number","volume":"270","author":"Becher, Ver\u00f3nica","year":"2002","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1-3","key":"4","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.tcs.2007.02.022","article-title":"Turing\u2019s unpublished algorithm for normal numbers","volume":"377","author":"Becher, Ver\u00f3nica","year":"2007","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"296","key":"5","doi-asserted-by":"publisher","first-page":"2939","DOI":"10.1090\/mcom\/2964","article-title":"A computable absolutely normal Liouville number","volume":"84","author":"Becher, Ver\u00f3nica","year":"2015","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2013.08.013","article-title":"A polynomial-time algorithm for computing absolutely normal numbers","volume":"232","author":"Becher, Ver\u00f3nica","year":"2013","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1112\/jlms\/jdu035","article-title":"On the normality of numbers to different bases","volume":"90","author":"Becher, Ver\u00f3nica","year":"2014","journal-title":"J. Lond. Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","article-title":"On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines","volume":"21","author":"Blum, Lenore","year":"1989","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"key":"9","doi-asserted-by":"crossref","unstructured":"\u00c9. Borel, Les probabilit\u00e9s d\u2019enombrables et leurs applications arithm\u00e9tiques, Supplemento di Rendiconti del Circolo Matematico di Palermo 27 (1909), 247\u2013271.","DOI":"10.1007\/BF03019651"},{"key":"10","series-title":"Cambridge Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139017732","volume-title":"Distribution modulo one and Diophantine approximation","volume":"193","author":"Bugeaud, Yann","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521111690"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1112\/jlms\/s1-8.4.254","article-title":"The Construction of Decimals Normal in the Scale of Ten","volume":"8","author":"Champernowne, D. G.","year":"1933","journal-title":"J. London Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"key":"12","series-title":"Theory and Applications of Computability","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic randomness and complexity","author":"Downey, Rodney G.","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387955674"},{"key":"13","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093404","volume-title":"Sequences, discrepancies and applications","volume":"1651","author":"Drmota, Michael","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540626069"},{"key":"14","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S1385-7258(64)50015-3","article-title":"The discrepancy of the sequence {(2\u207f\ud835\udc65)}","volume":"26","author":"Gaal, S.","year":"1964","journal-title":"Indag. Math."},{"key":"15","series-title":"Scriptum, no. 5","volume-title":"Some theorems on Diophantine inequalities","author":"Koksma, J. F.","year":"1950"},{"key":"16","unstructured":"L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Dover Publications, Inc., New York, 2006."},{"issue":"2","key":"17","first-page":"207","article-title":"The uniform distribution of the sequence {\ud835\udefc\ud835\udf06^{\ud835\udc65}}","volume":"98(140)","author":"Levin, M. B.","year":"1975","journal-title":"Mat. Sb. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0368-8666","issn-type":"print"},{"issue":"1","key":"18","first-page":"31","article-title":"Absolutely normal numbers","author":"Levin, M. B.","year":"1979","journal-title":"Vestnik Moskov. Univ. Ser. I Mat. Mekh.","ISSN":"https:\/\/id.crossref.org\/issn\/0579-9368","issn-type":"print"},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.4064\/aa-88-2-99-111","article-title":"On the discrepancy estimate of normal numbers","volume":"88","author":"Levin, M. B.","year":"1999","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"20","doi-asserted-by":"crossref","unstructured":"M. Madritsch and R. Tichy, Dynamical systems and uniform distribution of sequences, arXiv:1501.07411v1, 2015.","DOI":"10.1007\/978-3-319-28203-9_17"},{"key":"21","doi-asserted-by":"crossref","unstructured":"A.-M. Scheerer, Computable absolutely normal numbers and discrepancies, Math. Comp., to appear, DOI: 10.1090\/mcom\/3189.","DOI":"10.1090\/mcom\/3189"},{"issue":"2","key":"22","doi-asserted-by":"publisher","first-page":"175","DOI":"10.4064\/aa-47-2-175-186","article-title":"Discrepancy of normal numbers","volume":"47","author":"Schiffer, Johann","year":"1986","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"23","doi-asserted-by":"publisher","first-page":"299","DOI":"10.4064\/aa-7-3-299-309","article-title":"\u00dcber die Normalit\u00e4t von Zahlen zu verschiedenen Basen","volume":"7","author":"Schmidt, Wolfgang M.","year":"1961","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"24","series-title":"Collected Works of A. M. Turing","isbn-type":"print","volume-title":"Pure mathematics","author":"Turing, A. M.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880593"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03188-4\/mcom3188_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03188-4\/S0025-5718-2017-03188-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03188-4\/S0025-5718-2017-03188-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:22:38Z","timestamp":1776799358000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03188-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,29]]},"references-count":24,"journal-issue":{"issue":"308","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["S0025-5718-2017-03188-4"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3188","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2017,3,29]]}}}