When is an automatic set an additive basis?

Bell, Jason; Hare, Kathryn; Shallit, Jeffrey

doi:10.1090/bproc/37

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