When is an automatic set an additive basis?

DOI10.1090/BPROC/37zbMATH Open1437.11017arXiv1710.08353OpenAlexW2963125350WikidataQ129451770 ScholiaQ129451770MaRDI QIDQ4577830FDOQ4577830

Authors: Kathryn E. Hare, Jason P. Bell, Jeffrey Shallit 

Publication date: 3 August 2018

Published in: Proceedings of the American Mathematical Society, Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1710.08353

Recommendations

• Additive Number Theory via Approximation by Regular Languages
• On additive bases
• Automatic sets of rational numbers
• \(k\)-automatic sets of rational numbers
• Additive number theory via automata theory

zbMATH Keywords

Cantor setsadditive basisfinite-state automatonautomatic set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Periodicity, repetitions, and orbits of an automatic sequence
• Automatic Sequences
• Logic and \(p\)-recognizable sets of integers
• Title not available (Why is that?)
• Some Direct Decompositions of the Set of Integers
• An Application of Generating Series
• Title not available (Why is that?)
• Finding the growth rate of a regular or context-free language in polynomial time
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Some Theorems on Fourier Coefficients
• Bounded Regular Sets
• Large improvements in Waring's problem
• Title not available (Why is that?)
• Enumeration and decidable properties of automatic sequences
• On sums of powers of almost equal primes
• Title not available (Why is that?)
• Characterizing regular languages with polynomial densities
• On the complexity of a family of \(k\)-context-free sequences
• On some questions regarding \(k\)-regular and \(k\)-context-free sequences
• On Waring's Problem: Some Refinements
• Waring's theorem for binary powers
• Sums of Palindromes: an Approach via Automata
• Sums of Cantor sets
• A Goldbach Conjecture Using Twin Primes

Cited In (10)

• Additive number theory via automata theory
• Computational aspects of sturdy and flimsy numbers
• Automatic sequences and generalised polynomials
• The upper density of an automatic set is rational
• Automata and tame expansions of \((\mathbb{Z}, +)\)
• ADDITIVE BASES AND NIVEN NUMBERS
• Additive Number Theory via Approximation by Regular Languages
• On automatic subsets of the Gaussian integers
• Automata, palindromes, and reversed subwords
• A refinement of Christol's theorem for algebraic power series

Uses Software

• Walnut

This page was built for publication: When is an automatic set an additive basis?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577830)