×

Additive number theory via approximation by regular languages. (English) Zbl 1467.11011

The authors address relatively new questions in additive number theory. Namely, classical questions in the domain ask, e.g., whether numbers can be written as a sum of at most \(k\) squares, where \(k\) is fixed. More recent questions ask, for example, for the minimal number \(d\) such that every integer is the sum of \(d\) integers whose base-\(10\) expansion is a palindrome. Such a \(d\) exists, and is at most \(49\) (see [W. D. Banks, Integers 16, A03, 9 p. (2016; Zbl 1387.11008)]); the result was improved, and generalized for any base (see [J. Cilleruelo et al., Math. Comput. 87, No. 314, 3023–3055 (2018; Zbl 1441.11016); A. Rajasekaran et al., LIPIcs – Leibniz Int. Proc. Inform. 96, Article 54, 12 p. (2018; Zbl 1497.68277)]).
In the paper under review the authors propose a method to bound from above and from below the minimal number of elements of a set \(S\) that is candidate to be an additive basis, by first looking for a subset \(S'\) and a superset \(S''\) of elements of \(S\) whose base-\(k\) representations form a regular language, then by looking at integers that can (resp. cannot) be represented as a sum of \(m'\) (resp. \(m''\)) elements of \(S'\) (resp. \(S''\)). The advantage of their approach is that everything (or almost everything) can be done by using and manipulating finite automata, hence can be automated: the authors use the software \(\texttt{Grail}\) and \(\texttt{Walnut}\). We choose one of the nice results in the paper:
Let \(S_{\geq}\) be the set of integers with at least as many \(0\)’s as \(1\)’s in their base-\(2\) expansion, so that \(S_{\geq} = 2, 4, 8, 9, 10, 12, 16, 17, 18, 20, 24, 32, 33, 34, 35, 36, 37, 38, 40\dots\). Then, every natural number, except \(1\), \(3\), \(5\), \(7\), is the sum of at most three elements of \(S_{\geq}\), and three is asymptotically optimal.
In the last section the authors show that their approach cannot work for more classical additive basis problems like Goldbach’s conjecture, or Waring’s theorem. Finally, note that this paper supersedes the corresponding conference version (see [J. P. Bell et al., Lect. Notes Comput. Sci. 11088, 121–132 (2018; Zbl 1462.11014)]).

MSC:

11B13 Additive bases, including sumsets
11A63 Radix representation; digital problems
11B85 Automata sequences
68R15 Combinatorics on words
68Q45 Formal languages and automata

Software:

OEIS; Grail; GitHub; Walnut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P. and Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (Cambridge University Press, 2003). · Zbl 1086.11015
[2] Banks, W. D., Every natural number is the sum of forty-nine palindromes, INTEGERS: Elect. J. Combin. Number Theory16 (2016) p. #A3. · Zbl 1387.11008
[3] Bell, J., Hare, K. and Shallit, J., When is an automatic set an additive basis?Proc. Amer. Math. Soc. Ser. B5 (2018) 50-63. · Zbl 1437.11017
[4] Bell, J., Lidbetter, T. F. and Shallit, J., Additive number theory via approximation by regular languages, Developments in Language Theory (DLT 2018), eds. Hoshi, M. and Seki, S., , Vol. 11088 (Springer, 2018), pp. 121-132. · Zbl 1462.11014
[5] Cilleruelo, J., Luca, F. and Baxter, L., Every positive integer is a sum of three palindromes, Math. Comp.87 (2018) 3023-3055. · Zbl 1441.11016
[6] Gawrychowski, P., Krieger, D., Rampersad, N. and Shallit, J., Finding the growth rate of a regular or context-free language in polynomial time, Internat. J. Found. Comput. Sci.21 (2010) 597-618. · Zbl 1206.68172
[7] Hartmanis, J. and Shank, H., On the recognition of primes by automata, J. Assoc. Comput. Mach.15 (1968) 382-389. · Zbl 0164.05201
[8] Hopcroft, J. E. and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979). · Zbl 0426.68001
[9] Horváth, S., Karhumäki, J. and Kleijn, J., Results concerning palindromicity, J. Inf. Process. Cybern. EIK23 (1987) 441-451. · Zbl 0634.68072
[10] T. F. Lidbetter, Counting, adding, and regular languages, Master’s thesis, School of Computer Science, University of Waterloo (2018).
[11] H. Mousavi, Automatic theorem proving in Walnut, Preprint available at https://arxiv.org/abs/1603.06017.Software available at https://github.com/hamousavi/Walnut (2016).
[12] Nathanson, M. B., Additive Number Theory: The Classical Bases (Springer-Verlag, 1996). · Zbl 0859.11002
[13] Nathanson, M. B., Elementary Methods in Number Theory (Springer-Verlag, 2000). · Zbl 0953.11002
[14] Rajasekaran, A., Smith, T. and Shallit, J., Sums of palindromes: An approach via automata, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), eds. Niedermeier, R. and Vallée, B., (Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2018), pp. 54:1-54:12. · Zbl 1497.68277
[15] Raymond, D. R. and Wood, D., Grail: A \(C++\) library for automata and expressions, J. Symbolic Comput.17 (1994) 341-350. · Zbl 0942.68803
[16] Shorey, T. N. and Stewart, C. L., On the diophantine equation \(a x^{2 t}+b x^ty+c y^2=d\) and pure powers in recurrence sequences, Math. Scand.52 (1983) 24-36. · Zbl 0491.10016
[17] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, Available at https://oeis.org (2018). · Zbl 1439.11001
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.