## When is an automatic set an additive basis?

HTML articles powered by AMS MathViewer

- by
Jason Bell, Kathryn Hare and Jeffrey Shallit
**HTML**| PDF - Proc. Amer. Math. Soc. Ser. B
**5**(2018), 50-63

## Abstract:

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

- Jean-Paul Allouche, Narad Rampersad, and Jeffrey Shallit,
*Periodicity, repetitions, and orbits of an automatic sequence*, Theoret. Comput. Sci.**410**(2009), no. 30-32, 2795–2803. MR**2543333**, DOI 10.1016/j.tcs.2009.02.006 - Jean-Paul Allouche and Jeffrey Shallit,
*Automatic sequences*, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR**1997038**, DOI 10.1017/CBO9780511546563 - Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy,
*Winning ways for your mathematical plays. Vol. 2*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1982. Games in particular. MR**654502** - I. Borosh and L. B. Treybig,
*Bounds on positive integral solutions of linear Diophantine equations*, Proc. Amer. Math. Soc.**55**(1976), no. 2, 299–304. MR**396605**, DOI 10.1090/S0002-9939-1976-0396605-3 - N. G. de Bruijn,
*Some direct decompositions of the set of integers*, Math. Comp.**18**(1964), 537–546. MR**167447**, DOI 10.1090/S0025-5718-1964-0167447-9 - Véronique Bruyère, Georges Hansel, Christian Michaux, and Roger Villemaire,
*Logic and $p$-recognizable sets of integers*, Bull. Belg. Math. Soc. Simon Stevin**1**(1994), no. 2, 191–238. Journées Montoises (Mons, 1992). MR**1318968** - Carlos A. Cabrelli, Kathryn E. Hare, and Ursula M. Molter,
*Sums of Cantor sets*, Ergodic Theory Dynam. Systems**17**(1997), no. 6, 1299–1313. MR**1488319**, DOI 10.1017/S0143385797097678 - Émilie Charlier, Narad Rampersad, and Jeffrey Shallit,
*Enumeration and decidable properties of automatic sequences*, Internat. J. Found. Comput. Sci.**23**(2012), no. 5, 1035–1066. MR**2983367**, DOI 10.1142/S0129054112400448 - PawełGawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey Shallit,
*Finding the growth rate of a regular or context-free language in polynomial time*, Internat. J. Found. Comput. Sci.**21**(2010), no. 4, 597–618. MR**2678190**, DOI 10.1142/S0129054110007441 - Seymour Ginsburg and Edwin H. Spanier,
*Bounded regular sets*, Proc. Amer. Math. Soc.**17**(1966), 1043–1049. MR**201310**, DOI 10.1090/S0002-9939-1966-0201310-3 - M. J. E. Golay,
*Multi-slit spectrometry*, J. Optical Soc. America**39**(1949), 437–444. - 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. - John E. Hopcroft and Jeffrey D. Ullman,
*Introduction to automata theory, languages, and computation*, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR**645539** - Oscar H. Ibarra and B. Ravikumar,
*On sparseness, ambiguity and other decision problems for acceptors and transducers*, STACS 86 (Orsay, 1986) Lecture Notes in Comput. Sci., vol. 210, Springer, Berlin, 1986, pp. 171–179. MR**827734**, DOI 10.1007/3-540-16078-7_{7}4 - 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. - G. Kreisel, D. Lacombe, and J. R. Shoenfield,
*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, North-Holland Publishing Co., Amsterdam, 1957, pp. 290–297. MR**0108443** - Marion Le Gonidec,
*On the complexity of a family of $k$-context-free sequences*, Theoret. Comput. Sci.**414**(2012), 47–54. MR**2896582**, DOI 10.1016/j.tcs.2011.09.022 - M. Lothaire,
*Combinatorics on words*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997. With a foreword by Roger Lyndon and a preface by Dominique Perrin; Corrected reprint of the 1983 original, with a new preface by Perrin. MR**1475463**, DOI 10.1017/CBO9780511566097 - 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. - Leo Moser,
*An Application of Generating Series*, Math. Mag.**35**(1962), no. 1, 37–38. MR**1571147**, DOI 10.1080/0025570X.1962.11975291 - Yossi Moshe,
*On some questions regarding $k$-regular and $k$-context-free sequences*, Theoret. Comput. Sci.**400**(2008), no. 1-3, 62–69. MR**2424342**, DOI 10.1016/j.tcs.2008.02.018 - H. Mousavi.
*Automatic theorem proving in Walnut*, preprint available at https://arxiv.org/abs/1603.06017, 2016. - Melvyn B. Nathanson,
*Additive number theory*, Graduate Texts in Mathematics, vol. 164, Springer-Verlag, New York, 1996. The classical bases. MR**1395371**, DOI 10.1007/978-1-4757-3845-2 - A. Rajasekaran,
*Using automata theory to solve problems in additive number theory*, Master’s thesis, School of Computer Science, University of Waterloo, 2018. - A. Rajasekaran, T. Smith, and J. Shallit, Sums of palindromes: an approach via automata, in R. Niedermeier and B. Vallée, 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ür Informatik, 2018. - Walter Rudin,
*Some theorems on Fourier coefficients*, Proc. Amer. Math. Soc.**10**(1959), 855–859. MR**116184**, DOI 10.1090/S0002-9939-1959-0116184-5 - H. S. Shapiro,
*Extremal problems for polynomials and power series*, Master’s thesis, MIT, 1952. - Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeffrey Shallit,
*Characterizing regular languages with polynomial densities*, Mathematical foundations of computer science 1992 (Prague, 1992) Lecture Notes in Comput. Sci., vol. 629, Springer, Berlin, 1992, pp. 494–503. MR**1255157**, DOI 10.1007/3-540-55808-X_{4}8 - V. I. Trofimov,
*Growth functions of some classes of languages*, Kibernetika (Kiev)**6**(1981), i, 9–12, 149 (Russian, with English summary). MR**689421** - R. C. Vaughan and T. D. Wooley,
*On Waring’s problem: some refinements*, Proc. London Math. Soc. (3)**63**(1991), no. 1, 35–68. MR**1105718**, DOI 10.1112/plms/s3-63.1.35 - Bin Wei and Trevor D. Wooley,
*On sums of powers of almost equal primes*, Proc. Lond. Math. Soc. (3)**111**(2015), no. 5, 1130–1162. MR**3477231**, DOI 10.1112/plms/pdv048 - Trevor D. Wooley,
*Large improvements in Waring’s problem*, Ann. of Math. (2)**135**(1992), no. 1, 131–164. MR**1147960**, DOI 10.2307/2946566 - Dan Zwillinger,
*A Goldbach conjecture using twin primes*, Math. Comp.**33**(1979), no. 147, 1071. MR**528060**, DOI 10.1090/S0025-5718-1979-0528060-5

## Additional Information

**Jason Bell**- Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 632303
- Email: jpbell@uwaterloo.ca
**Kathryn Hare**- Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 246969
- Email: kehare@uwaterloo.ca
**Jeffrey Shallit**- Affiliation: School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 159555
- Email: shallit@uwaterloo.ca
- Received by editor(s): October 23, 2017
- Received by editor(s) in revised form: March 27, 2018
- Published electronically: August 2, 2018
- Additional Notes: Research of the first author was supported by NSERC Grant 2016-03632.

Research of the second author was supported by NSERC Grant 2016-03719.

Rsearch of the third author was supported by NSERC Grant 105829/2013. - Communicated by: Matthew A. Papanikolas
- © Copyright 2018 by the authors under Creative Commons Attribution-Noncommercial 3.0 License (CC BY NC 3.0)
- Journal: Proc. Amer. Math. Soc. Ser. B
**5**(2018), 50-63 - MSC (2010): Primary 11B13; Secondary 11B85, 68Q45, 28A80
- DOI: https://doi.org/10.1090/bproc/37
- MathSciNet review: 3835513