When is an automatic set an additive basis?

DOI10.1090/BPROC/37MaRDI QIDQ4577830zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

additive basisautomatic setCantor setsfinite-state automaton

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)