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 auto...
详细信息
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.
We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 25 is the sum of at most thr...
详细信息
We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 25 is the sum of at most three natural numbers whose base-2 representation has an equal number of 0's and 1's.
There is a standard "word length'' metric canonically associated to any set of generators for a group. In particular, for any integers a and b greater than 1, the additive group Z has generating sets {a(i...
详细信息
There is a standard "word length'' metric canonically associated to any set of generators for a group. In particular, for any integers a and b greater than 1, the additive group Z has generating sets {a(i)}(i=0)(infinity) and {b(j)}(j=0)(infinity) with associated metrics d(A) and d(B), respectively. It is proved that these metrics are bi-Lipschitz equivalent if and only if there exist positive integers m and n such that a(m) = b(n).
Let R be a commutative ring R with 1(R) and with group of units R-x. Let Phi = Phi(t(1), ... ,t(h)) = Sigma(h)(i=0) phi(i)t(i) be an h-ary linear form with nonzero coefficients phi(1), ... ,phi(h) is an element of R. ...
详细信息
Let R be a commutative ring R with 1(R) and with group of units R-x. Let Phi = Phi(t(1), ... ,t(h)) = Sigma(h)(i=0) phi(i)t(i) be an h-ary linear form with nonzero coefficients phi(1), ... ,phi(h) is an element of R. Let M be an R-module. For every subset A of M, the image of A under Phi is Phi(A) = {Phi(a(1), ... ,a(h)) : (a(1), ... , a(h)) is an element of A(h)}. For every subset I of {1,2, ... , h}, there is the subset sum s(I) = Sigma(i is an element of I) phi(i). Let S(Phi) = {s(I) : emtey set not equal I subset of {1, 2, ... ,h}}. Theorem. Let (sic)(t(1), ... , t(g)) = Sigma(g)(i=1) v(i)t(i) and Phi(t(1), ... , t(h)) = Sigma(h)(i=1) phi(i)t(i) be linear forms with nonzero coefficients in the ring R. If {0, 1} subset of S((sic)) and S(Phi) is an element of R-x, then for every epsilon > 0 and c > 1 there exist a finite R-module M with vertical bar M vertical bar > c and a subset A of M such that (sic)(A boolean OR{0}) = M and vertical bar Phi(A)vertical bar < epsilon vertical bar M vertical bar. (C) 2017 Elsevier Inc. All rights reserved.
The set A = {a(n)}(n=1)(infinity) of nonnegative integers is an asymptotic basis of order h if every sufficiently large integer can be represented as the sum of h elements of A. If a(n) similar to alpha n(h) for some ...
详细信息
The set A = {a(n)}(n=1)(infinity) of nonnegative integers is an asymptotic basis of order h if every sufficiently large integer can be represented as the sum of h elements of A. If a(n) similar to alpha n(h) for some real number alpha > 0, then alpha is called an additive eigenvalue of order h. The additive spectrum of order h is the set N(h) consisting of all additive eigenvalues of order h. It is proved that there is a positive number eta h <= 1/h ! such that N(h) = (0, eta(h)) or N(h) = (0, eta(h)]. The proof uses results about the construction of supersequences of sequences with prescribed asymptotic growth, and also about the asymptotics of rearrangements of infinite sequences. For example, it is proved that there does not exist a strictly increasing sequence of integers B = {b(n)}(n=1)(infinity) such that b(n) similar to 2(n) and B contains a subsequence {b(nk)}(k=1)(infinity) such that b(nk) similar to 3(k). (C) 2008 Elsevier Inc. All rights reserved.
We disprove a 2002 conjecture of Dombi from additive number theory. More precisely, we find examples of sets A subset of N with the property that N \ A is infinite, but the sequence n -> |{(a, b, c) : n = a + b + c...
详细信息
We disprove a 2002 conjecture of Dombi from additive number theory. More precisely, we find examples of sets A subset of N with the property that N \ A is infinite, but the sequence n -> |{(a, b, c) : n = a + b + c and a, b, c is an element of A}|, counting the number of 3-compositions using elements of A only, is strictly increasing.
The number theoretic analog of a net in metric geometry suggests new problems and results in combinatorial and additive number theory. For example, for a fixed integer g >= 2, the study of h-nets in the additive gr...
详细信息
The number theoretic analog of a net in metric geometry suggests new problems and results in combinatorial and additive number theory. For example, for a fixed integer g >= 2, the study of h-nets in the additive group of integers with respect to the generating set A(g) = additive number theoryboolean OR{+/- g(i) : i = 0, 1, 2, ...} requires a knowledge of the word lengths of integers with respect to Ag. A g-adic representation of an integer is described that algorithmically produces a representation of shortest length. additive complements and additive asymptotic complements are also discussed, together with their associated minimality problems.
The set A of nonnegative integers is called a basis of order h if every nonnegative integer can be represented as the sum of exactly h not necessarily distinct elements of A. An additive basis A of order It is called ...
详细信息
The set A of nonnegative integers is called a basis of order h if every nonnegative integer can be represented as the sum of exactly h not necessarily distinct elements of A. An additive basis A of order It is called thin if there exists c > 0 such that the number of elements of A not exceeding x is less than cx(1/h) for all x >= 1. This paper describes a construction of Shatrovskii of thin bases of order h. (C) 2012 Elsevier B.V. All rights reserved.
暂无评论