nach oben

Theory of Computing Systems

Erschienen in:

29.05.2019

Additive Number Theory via Automata Theory

verfasst von: Aayush Rajasekaran, Jeffrey Shallit, Tim Smith

Erschienen in: Theory of Computing Systems | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.

Vorheriger Artikel Space-Efficient Algorithms for Longest Increasing Subsequence

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Allouche, J.-P., Rampersad, N., Shallit, J.: Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410, 2795–2803 (2009)CrossRefMathSciNetMATH

Aloui, K., Mauduit, C., Mkaouar, M.: Somme des chiffres et répartition dans les classes de congruence pour les palindromes ellipséphiques. Acta Math. Hung. 151, 409–455 (2017)CrossRefMATH

Alur, R., Madhusudan, P.: Visibly Pushdown Languages. In: Proc. Thirty-Sixth Ann. ACM Symp. Theor. Comput. (STOC), pp. 202–211, ACM (2004)

Alur, R., Madhusudan, P.: Adding nested structure to words. J. Assoc. Comput. Mach. 56 (2009), Art. 16

Appel, K., Haken, W.: Every planar map is four colorable. I. Discharging Illinois J. Math. 21, 429–490 (1977)CrossRefMathSciNetMATH

Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. II. Reducibility Illinois J. Math. 21, 491–567 (1977)CrossRefMathSciNetMATH

Ashbacher, C.: More on palindromic squares. J. Recreat. Math. 22, 133–135 (1990)MATH

Banks, W.D.: Every natural number is the sum of forty-nine palindromes. INTEGERS — Electronic J. Combinat. Number Theory 16 (2016), #A3 (electronic)

Banks, W.D., Hart, D.N., Sakata, M.: Almost all palindromes are composite. Math. Res. Lett. 11, 853–868 (2004)CrossRefMathSciNetMATH

10.

Banks, W.D., Shparlinski, I.E.: Prime divisors of palindromes. Period. Math Hung. 51, 1–10 (2005)CrossRefMathSciNetMATH

11.

Banks, W.D., Shparlinski, I.E.: Average value of the Euler function on binary palindromes. Bull. Pol. Acad. Sci Math. 54, 95–101 (2006)CrossRefMathSciNetMATH

12.

Barnett, J.K.R.: Tables of square palindromes in bases 2 and 10. J. Recreat. Math. 23(1), 13–18 (1991)MATH

13.

Basić, B. : On d-digit palindromes in different bases: the number of bases is unbounded. Internat. J. Number Theory 8, 1387–1390 (2012)CrossRefMathSciNetMATH

14.

Basić, B.: On “very palindromic” sequences. J. Korean Math. Soc. 52, 765–780 (2015)CrossRefMathSciNetMATH

15.

Bell, J., Hare, K., Shallit, J.: When is an automatic set an additive basis. Proc. Amer. Math. Soc. Ser. B 5, 50–63 (2018)CrossRefMathSciNetMATH

16.

Bell, J.P., Lidbetter, T.F., Shallit, J.: Additive number theory via approximation by regular languages. In: Hoshi, M., Seki, S. (eds.) DLT Vol. 11088 of Lecture Notes in Computer Science, pp 121–132. Springer, Berlin (2018)

17.

Bérczes, A., Ziegler, V.: On simultaneous palindromes. J. Combin. Number Theory 6, 37–49 (2014)MathSciNetMATH

18.

Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for your Mathematical Plays, Vol. 2 Games in Particular. Academic Press, Cambridge (1982)MATH

19.

Berstel, J.: Axel Thue’s Papers on Repetitions in Words: a Translation. Number 20 in Publications Du Laboratoire De Combinatoire Et d’Informatique Mathématique. Université du Québec à Montréal (1995)

20.

von Braunmühl, B., Verbeek, R.: Input-driven languages are recognized in n space. In: Karpinski, M. (ed.) Foundations of Computation Theory, FCT 83, Vol. 158 of Lecture Notes in Computer Science, pp 40–51. Springer, Berlin (1983)

21.

Bruyère, V., Hansel, G.: Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181, 17–43 (1997)CrossRefMathSciNetMATH

22.

Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1, 191–238 (1994). Corrigendum, Bull. Belg. Math. Soc. 1 (1994) 577MathSciNetMATH

23.

Büchi, J.R.: Weak secord-order arithmetic and finite automata. Zeitschrift fur̈ mathematische Logik und Grundlagen der Mathematik 6, 66–92 (1960). Reprinted in S. Mac Lane and D. Siefkes, eds., The Collected Works of J. Richard Buchï, Springer, 1990, pp.398–424CrossRefMATH

24.

Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23, 1035–1066 (2012)CrossRefMathSciNetMATH

25.

Cilleruelo, J., Luca, F.: Every positive integer is a sum of three palindromes. arXiv:1602.06208v1 (2016)

26.

Cilleruelo, J., Luca, F., Baxter, L.: Every positive integer is a sum of three palindromes. Math. Comput. 87, 3023–3055 (2018)CrossRefMathSciNetMATH

27.

Cilleruelo, J., Luca, F., Shparlinski, I.E.: Power values of palindromes. J Combin. Number Theory 1, 101–107 (2009)MathSciNetMATH

28.

Cilleruelo, J., Tesoro, R., Luca, F.: Palindromes in linear recurrence sequences. Monatsh. Math. 171, 433–442 (2013)CrossRefMathSciNetMATH

29.

Col, S.: Palindromes dans les progressions arithmétiques. Acta Arith. 137, 1–41 (2009)CrossRefMathSciNetMATH

30.

Du, C.F., Mousavi, H., Rowland, E., Schaeffer, L.: J. Shallit. Decision algorithms for Fibonacci-automatic words II: related sequences and avoidability. Theoret. Comput. Sci. 657, 146–162 (2017)CrossRefMathSciNetMATH

31.

Du, C.F., Mousavi, H., Schaeffer, L., Shallit, J.: Decision algorithms for Fibonacci-automatic words III: enumeration and abelian properties. Internat. J. Found. Comp. Sci. 27, 943–963 (2016)CrossRefMathSciNetMATH

32.

Dymond, P.W.: Input-driven languages are in n depth. Inform. Process. Lett. 26, 247–250 (1988)CrossRefMathSciNet

33.

Goč, D., Henshall, D., Shallit, J.: Automatic theorem-proving in combinatorics on words. In: Moreira, N., Reis, R. (eds.) CIAA 2012, Vol. 7381 of Lecture Notes in Computer Science, pp 180–191. Springer, Berlin (2012)

34.

Goč, D., Mousavi, H., Shallit, J.: On the number of unbordered factors. In: Dediu, A.-H., Martin-Vide, C., Truthe, B. (eds.) LATA 2013, Vol. 7810 of Lecture Notes in Computer Science, pp 299–310. Springer, Berlin (2013)

35.

Goč, D., Saari, K., Shallit, J.: Primitive words and Lyndon words in automatic and linearly recurrent sequences. In: Dediu, A.-H., Martin-Vide, C., Truthe, B. (eds.) LATA 2013, Primitive Vol. 7810 of Lecture Notes in Computer Science, pp 311–322. Springers, Berlin (2013)

36.

Goč, D., Schaeffer, L., Shallit, J.: The subword complexity of k-automatic sequences is k-synchronized. In: Béal, M.-P., Carton, O. (eds.) DLT 2013, Vol. 7907 of Lecture Notes in Computer Science, pp 252–263. Springer, Berlin (2013)

37.

Goins, E.H.: Palindromes in different bases: a conjecture of J. Ernest Wilkins. INTEGERS — Electronic J. Combinat. Number Theory 9, 725–734 (2009). Paper #A55, (electronic)MathSciNetMATH

38.

Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. 410, 2961–2971 (2009)CrossRefMathSciNetMATH

39.

Haque, S., Shallit, J.: Discriminators and k-regular sequences. INTEGERS — Electronic J. Combinat. Number Theory 16, A76 (2016). (electronic)MathSciNetMATH

40.

Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1985)

41.

Harminc, M., Soták, R.: Palindromic numbers in arithmetic progressions. Fibonacci Quart. 36, 259–262 (1998)MathSciNetMATH

42.

Heizmann, M., Hoenicke, J., Podelski, A.: Software model checking for people who love automata. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification — 25th International Conference, CAV 2013, vol. 8044 of Lecture Notes in Computer Science, pp 36–52. Springer, Berlin (2013)

43.

Heizmann, M., Dietsch, D., Greitschus, M., Leike, J., Musa, B., Schätzle, C., Podelski, A.: Ultimate automizer with two-track proofs. In: Chechik, M., Raskin, J.-F. (eds.) Tools and Algorithms for the Construction and Analysis of Systems — 22nd International Conference, TACAS 2016, vol. 9636 of Lecture Notes in Computer Science, pp 950–953. Springer, Berlin (2016)

44.

Hernández, S., Luca, F.: Palindromic powers. Rev. Colombiana Mat. 40, 81–86 (2006)MathSciNetMATH

45.

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston (1979)MATH

46.

Kane, D.M., Sanna, C., Shallit, J.: Waring’s Theorem for Binary Powers. arXiv:1801.04483. To appear, Combinatorica (2018)

47.

Keith, M.: Classification and enumeration of palindromic squares. J. Recreat. Math. 22(2), 124–132 (1990)MATH

48.

Kidder, P., Kwong, H.: Remarks on integer palindromes. J. Recreat. Math. 36, 299–306 (2007)MathSciNet

49.

Korec, I.: Palindromic squares for various number system bases. Math. Slovaca 41, 261–276 (1991)MathSciNetMATH

50.

Kresová, H., Sǎlát, T.: On palindromic numbers. Acta Math. Univ Comenian. 42(/43), 293–298 (1984)MathSciNetMATH

51.

La Torre, S., Napoli, M., Parente, M.: On the membership problem for visibly pushdown languages. In: Graf, S., Zhang, W. (eds.) ATVA 2006, vol. 4218 of Lecture Notes in Computer Science, pp. 96–109, Springer (2006)

52.

Lekkerkerker, C.G.: Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci. Simon Stevin 29, 190–195 (1952)MathSciNet

53.

Luca, F.: Palindromes in Lucas sequences. Monatsh. Math. 138, 209–223 (2003)CrossRefMathSciNetMATH

54.

Luca, F., Togbé, A.: On binary palindromes of the form 10ⁿ1. C. R. Acad. Sci. Paris 346, 487–489 (2008)CrossRefMathSciNetMATH

55.

Luca, F., Young, P.T.: On the Binary Expansion of the Odd Catalan Numbers. In: Proc. 14Th Int. Conf. on Fibonacci Numbers and Their Applications, pp. 185–190. Soc. Mat. Mexicana (2011)

56.

Madhusudan, P., Nowotka, D., Rajasekaran, A., Shallit, J.: Lagrange’s theorem for binary squares. In: Potapov, I., Spirakis, P., Worrell, J. (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics, pp. 18:1–18:14. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Germany (2018)

57.

McCune, W.: Solution of the Robbins problem. J. Autom. Reason. 19(3), 263–276 (1997)CrossRefMathSciNetMATH

58.

Mehlhorn, K.: Pebbling Mountain Ranges and Its Application of DCFL-Recognition. In: Proc. 7Th Int’l Conf. on Automata, Languages, and Programming (ICALP), Vol. 85 of Lecture Notes in Computer Science, pp. 422–435. Springer (1980)

59.

Mousavi, H.: Automatic theorem proving in Walnut. arXiv:1603.06017 (2016)

60.

Mousavi, H., Schaeffer, L., Shallit, J.: Decision algorithms for Fibonacci-automatic words, I Basic results. RAIRO Inform. Théor. App. 50, 39–66 (2016)CrossRefMathSciNetMATH

61.

Nathanson, M.B.: Additive Number Theory: The Classical Bases. Springer, Berlin (1996)CrossRefMATH

62.

Ogden, W.: A helpful result for proving inherent ambiguity. Math. Systems Theory 2, 191–194 (1968)CrossRefMathSciNetMATH

63.

Okhotin, A., Salomaa, K.: State complexity of operations on input-driven pushdown automata. J Comput. System Sci. 86, 207–228 (2017)CrossRefMathSciNetMATH

64.

Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci. 410, 3290–3302 (2009)CrossRefMathSciNetMATH

65.

Pollack, P.: Palindromic sums of proper divisors. INTEGERS — Electronic J. Combinat. Number Theory 15A, Paper #A13 (electronic) (2015)MathSciNetMATH

66.

Rajasekaran, A.: Using automata theory to solve problems in additive number theory. Master’s thesis, School of Computer Science, University of Waterloo, 2018. Available at https://uwspace.uwaterloo.ca/handle/10012/13202

67.

Rajasekaran, A., Smith, T., Shallit, J.: Sums of palindromes: an approach via automata. In: Niedermeier, R., Vallée, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Leibniz International Proceedings in Informatics, pp. 54:1–54:12. Schloss Dagstuhl — Leibniz-Zentrum fur̈ Informatik (2018)

68.

Salomaa, K.: Limitations of lower bound methods for deterministic nested word automata. Inform. Comput. 209, 580–589 (2011)CrossRefMathSciNetMATH

69.

Shallit, J.: Decidability and enumeration for automatic sequences: a survey. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013, vol. 7913 of Lecture Notes in Computer Science, pp 49–63. Springer, Berlin (2013)

70.

Shorey, T.N.: On the equation z^q = (xⁿ − 1)/(x − 1). Indag. Math. 48, 345–351 (1986)CrossRefMathSciNet

71.

Sigg, M.: On a conjecture of John Hoffman regarding sums of palindromic numbers. arXiv:1510.07507 (2015)

72.

Simmons, G.J.: On palindromic squares of non-palindromic numbers. J. Recreat. Math. 5(1), 11–19 (1972)MathSciNet

73.

Sloane, N.J.A., et al.: The on-line encyclopedia of integer sequences Available at https://oeis.org (2019)

74.

Thue, A.: ÜBer die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1, 1–67 (1912). Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, 413–478MATH

75.

Trigg, C.: Infinite sequences of palindromic triangular numbers. Fibonacci Quart. 12, 209–212 (1974)MathSciNetMATH

76.

Tymoczko, T.: The four-color problem and its philosophical significance. J. Philosophy 76(2), 57–83 (1979)CrossRef

77.

Vaughan, R.C., Wooley, T.: Number Theory for the Millennium. III, pp. 301–340. A. K. Peters. In: Bennett, M.A., Berndt, B.C., Boston, N., Diamond, H.G., Hildebrand, A.J., Philipp, W. (eds.) (2002)

78.

Yates, S.: The mystique of repunits. Math. Mag. 51, 22–28 (1978)CrossRefMathSciNetMATH

79.

Zeckendorf, E.: Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Liége 41, 179–182 (1972)MathSciNetMATH

Titel: Additive Number Theory via Automata Theory
verfasst von: Aayush Rajasekaran
Jeffrey Shallit
Tim Smith
Publikationsdatum: 29.05.2019
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 3/2020
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-019-09929-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2020

Space-Efficient Algorithms for Longest Increasing Subsequence

On Approximating the Stationary Distribution of Time-Reversible Markov Chains

Optimal Dislocation with Persistent Errors in Subquadratic Time

Lower Bound Techniques for QBF Expansion

Computing Hitting Set Kernels By AC0-Circuits

On the Tree Conjecture for the Network Creation Game