×

When is an automatic set an additive basis? (English) Zbl 1437.11017

Summary: We characterize those \( k\)-automatic sets \( S\) of natural numbers that form an additive basis for the natural numbers, and we show that this characterization is effective. In addition, we give an algorithm to determine the smallest \( j\) such that \( S\) forms an additive basis of order \( j\), if it exists.

MSC:

11B13 Additive bases, including sumsets
11B85 Automata sequences
68Q45 Formal languages and automata
28A80 Fractals

Software:

Walnut
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allouche, Jean-Paul; Rampersad, Narad; Shallit, Jeffrey, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci., 410, 30-32, 2795-2803 (2009) · Zbl 1173.68044 · doi:10.1016/j.tcs.2009.02.006
[2] Allouche, Jean-Paul; Shallit, Jeffrey, Automatic sequences\upshape, Theory, applications, generalizations, xvi+571 pp. (2003), Cambridge University Press, Cambridge · Zbl 1086.11015 · doi:10.1017/CBO9780511546563
[3] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K., Winning ways for your mathematical plays. Vol. 2\upshape, Games in particular, i-xxxiii and 429-850 and i-xix (1982), Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York · Zbl 0485.00025
[4] Borosh, I.; Treybig, L. B., Bounds on positive integral solutions of linear Diophantine equations, Proc. Amer. Math. Soc., 55, 2, 299-304 (1976) · Zbl 0291.10014 · doi:10.2307/2041711
[5] de Bruijn, N. G., Some direct decompositions of the set of integers, Math. Comp., 18, 537-546 (1964) · Zbl 0126.27903 · doi:10.2307/2002940
[6] Bruy\`“ere, V\'”eronique; Hansel, Georges; Michaux, Christian; Villemaire, Roger, Logic and \(p\)-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin, 1, 2, 191-238 (1994) · Zbl 0804.11024
[7] Cabrelli, Carlos A.; Hare, Kathryn E.; Molter, Ursula M., Sums of Cantor sets, Ergodic Theory Dynam. Systems, 17, 6, 1299-1313 (1997) · Zbl 0891.28001 · doi:10.1017/S0143385797097678
[8] Charlier, \'Emilie; Rampersad, Narad; Shallit, Jeffrey, Enumeration and decidable properties of automatic sequences, Internat. J. Found. Comput. Sci., 23, 5, 1035-1066 (2012) · Zbl 1282.68186 · doi:10.1142/S0129054112400448
[9] Gawrychowski, Pawe\l; Krieger, Dalia; Rampersad, Narad; Shallit, Jeffrey, Finding the growth rate of a regular or context-free language in polynomial time, Internat. J. Found. Comput. Sci., 21, 4, 597-618 (2010) · Zbl 1206.68172 · doi:10.1142/S0129054110007441
[10] Ginsburg, Seymour; Spanier, Edwin H., Bounded regular sets, Proc. Amer. Math. Soc., 17, 1043-1049 (1966) · Zbl 0147.25301 · doi:10.2307/2036087
[11] Golay:1949 M. J. E. Golay, Multi-slit spectrometry, J. Optical Soc. America 39 (1949), 437-444.
[12] Golay:1951 M. J. E. Golay, Static multislit spectrometry and its application to the panoramic display of infrared spectra, J. Optical Soc. America 41 (1951), 468-472.
[13] Hopcroft, John E.; Ullman, Jeffrey D., Introduction to automata theory, languages, and computation\upshape, Addison-Wesley Series in Computer Science, x+418 pp. (1979), Addison-Wesley Publishing Co., Reading, Mass. · Zbl 0426.68001
[14] Ibarra, Oscar H.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and transducers. STACS 86, Orsay, 1986, Lecture Notes in Comput. Sci. 210, 171-179 (1986), Springer, Berlin · Zbl 0605.68080 · doi:10.1007/3-540-16078-7\_74
[15] Kane&Sanna&Shallit:2017 D. M. Kane, C. Sanna, and J. Shallit, Waring’s theorem for binary powers, preprint, available at https://arxiv.org/abs/1801.04483. Submitted 2018. · Zbl 1463.11148
[16] Kreisel, G.; Lacombe, D.; Shoenfield, J. R., Partial recursive functionals and effective operations. Constructivity in mathematics: Proceedings of the colloquium held at Amsterdam, 1957 (edited by A. Heyting), Studies in Logic and the Foundations of Mathematics, 290-297 (1957), North-Holland Publishing Co., Amsterdam · Zbl 0178.32201
[17] Le Gonidec, Marion, On the complexity of a family of \(k\)-context-free sequences, Theoret. Comput. Sci., 414, 47-54 (2012) · Zbl 1239.68057 · doi:10.1016/j.tcs.2011.09.022
[18] Lothaire, M., Combinatorics on words\upshape, with a foreword by Roger Lyndon and a preface by Dominique Perrin; corrected reprint of the 1983 original, with a new preface by Perrin, Cambridge Mathematical Library, xviii+238 pp. (1997), Cambridge University Press, Cambridge · doi:10.1017/CBO9780511566097
[19] Madhusudan&Nowotka&Rajasekaran&Shallit:2017 P. Madhusudan, D. Nowotka, A. Rajasekaran, and J. Shallit. Lagrange’s theorem for binary squares, to appear, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), available at https://arxiv.org/abs/1710.04247. Submitted 2017.
[20] Moser, Leo, An application of generating series, Math. Mag., 35, 1, 37-38 (1962) · Zbl 0134.27305
[21] Moshe, Yossi, On some questions regarding \(k\)-regular and \(k\)-context-free sequences, Theoret. Comput. Sci., 400, 1-3, 62-69 (2008) · Zbl 1143.68038 · doi:10.1016/j.tcs.2008.02.018
[22] Mousavi:2016 H. Mousavi. Automatic theorem proving in Walnut, preprint available at https://arxiv.org/abs/1603.06017, 2016.
[23] Nathanson, Melvyn B., Additive number theory\upshape, The classical bases, Graduate Texts in Mathematics 164, xiv+342 pp. (1996), Springer-Verlag, New York · Zbl 0859.11002 · doi:10.1007/978-1-4757-3845-2
[24] Rajasekaran:2018 A. Rajasekaran, Using automata theory to solve problems in additive number theory, Master’s thesis, School of Computer Science, University of Waterloo, 2018.
[25] Rajasekaran&Smith&Shallit:2018 A. Rajasekaran, T. Smith, and J. Shallit, Sums of palindromes: an approach via automata, in R. Niedermeier and B. Vall\'ee, editors, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Leibniz International Proceedings in Informatics, pages 54:1-54:12. Schloss Dagstuhl — Leibniz-Zentrum f\"ur Informatik, 2018. · Zbl 1497.68277
[26] Rudin, Walter, Some theorems on Fourier coefficients, Proc. Amer. Math. Soc., 10, 855-859 (1959) · Zbl 0091.05706 · doi:10.2307/2033608
[27] Shapiro:1952 H. S. Shapiro, Extremal problems for polynomials and power series, Master’s thesis, MIT, 1952.
[28] Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey, Characterizing regular languages with polynomial densities. Mathematical foundations of computer science 1992, Prague, 1992, Lecture Notes in Comput. Sci. 629, 494-503 (1992), Springer, Berlin · Zbl 1493.68195 · doi:10.1007/3-540-55808-X\_48
[29] Trofimov, V. I., Growth functions of some classes of languages, Cybernetics, 6, i, 9-12, 149 (1981)
[30] Vaughan, R. C.; Wooley, T. D., On Waring’s problem: some refinements, Proc. London Math. Soc. (3), 63, 1, 35-68 (1991) · Zbl 0736.11058 · doi:10.1112/plms/s3-63.1.35
[31] Wei, Bin; Wooley, Trevor D., On sums of powers of almost equal primes, Proc. Lond. Math. Soc. (3), 111, 5, 1130-1162 (2015) · Zbl 1338.11096 · doi:10.1112/plms/pdv048
[32] Wooley, Trevor D., Large improvements in Waring’s problem, Ann. of Math. (2), 135, 1, 131-164 (1992) · Zbl 0754.11026 · doi:10.2307/2946566
[33] Zwillinger, Dan, A Goldbach conjecture using twin primes, Math. Comp., 33, 147, 1071 pp. (1979) · Zbl 0405.10002 · doi:10.2307/2006081
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.