Minimal bases and maximal nonbases in additive number theory

An asymptotic basis $\text{A}$ of order h is minimal if no proper subset of $\text{A}$ is an asymptotic basis of order h. Examples are constructed of minimal asymptotic bases, and also of an asymptotic basis of order two no subset of which is minimal.If $\text{B}$ is a set of nonnegative integers which is not a basis (resp. asymptotic basis) of order h, but such that every proper superset of $\text{B}$ is a basis (resp. asymptotic basis) of order h, then $\text{B}$ is a maximal nonbasis (resp. maximal asymptotic nonbasis) of order h. Examples of such sets are constructed, and it is proved that every set not a basis of order h is a subset of a maximal nonbasis of order h.     

Dense minimal asymptotic bases of order two

We call a set A of positive integers an asymptotic basis of order h if every sufficiently large integer n can be written as a sum of h elements of A. If no proper subset of A is an asymptotic basis of order h, then A is a minimal asymptotic basis of that order. Erd?s and Nathanson showed that for every h?2 there exists a minimal asymptotic basis A of order h with d(A)=1/h, where d(A) denotes the density of A. Erd?s and Nathanson asked whether it is possible to strengthen their result by deciding on the existence of a minimal asymptotic bases of order h?2 such that A(k)=k/h+O(1). Moreover, they asked if there exists a minimal asymptotic basis with lim sup(ai+1−ai)=3. In this paper we answer these questions in the affirmative by constructing a minimal asymptotic basis A of order 2 fulfilling a very restrictive condition

     

Representations of integers by linear forms in nonnegative integers

Let Ω be the set of positive integers that are omitted values of the form f = Σ_i=1ⁿa_ix_i, where the a_i are fixed and relatively prime natural numbers and the x_i are variable nonnegative integers. Set ω = #Ω and κ = max Ω + 1 (the conductor). Properties of ω and κ are studied, such as an estimate for ω (similar to one found by Brauer) and the inequality 2ω ≥ κ. The so-called Gorenstein condition is shown to be equivalent to 2ω = κ.     

On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

Partitions of the natural numbers into infinitely oscillating bases and nonbases

The setA of nonnegative integers is a basis if every sufficiently large integerx can be written in the formx=a+a′ witha, a′∈A. IfA is not a basis, then it is a nonbasis. We construct a partition of the natural numbers into a basisA and a nonbasisB such that, as random elements are moved one at a time fromA toB, fromB toA, fromA toB, …, the setA oscillates from basis to nonbasis to basis … and the setB oscillates simultaneously from nonbasis to basis to nonbasis…     

On the number of linear forms in logarithms

Let n be a positive integer. In this paper we estimate the size of the set of linear forms b₁loga₁+b₂loga₂+?+bnlogan, where |bi|?Bi and 1?ai?Ai are integers, as Ai,Bi→∞.     

Partitions of the set of natural numbers and their representation functions

For a given set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. In this paper we give a simple proof to two results by Sándor.     

The Erdös-Fuchs theorem on the square of a power series

Erdös and Fuchs proved that if a₁, a₂,… is a sequence of nonnegative integers and R(n) is the number of ordered pairs (i, j) with a_i + a_j ≤ n, then it is impossible to have $\text{R(n) = An + o(n}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{log}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{n)}$ as n → + ∞, for some positive constant A. This paper gives a generalization of this result, in which An is replaced by a function of n whose second differences are nonnegative from some point on.     

Chain Blockers and Convoluted Catalan Numbers

We give new interpretations of Catalan and convoluted Catalan numbers in terms of trees and chain blockers. For a poset P we say that a subset A ? P is a chain blocker if it is an inclusionwise minimal subset of P that contains at least one element from every maximal chain. In particular, we study the set of chain blockers for the class of posets P = C _a × C _b where C _i is the chain 1 < ? < i. We show that subclasses of these chain blockers are counted by Catalan and convoluted Catalan numbers.     

Minimal asymptotic bases for the natural numbers

The sequence A of nonnegative integers is an asymptotic basis of order h if every sufficiently large integer can be written as the sum of h elements of A. Let $\text{M}{}_{\mathrm{h}}{}^{\mathrm{A}}$ denote the set of elements that have more than one representation as a sum of h elements of A. It is proved that there exists an asymptotic basis A such that $\text{M}{}_{\mathrm{h}}{}^{\mathrm{A}}\text{(x) = O(x}{}^{\mathrm{<mtext>1?1</mtext><mtext>h+?</mtext>}}\text{)}$ for every ? > 0. An asymptotic basis A of order h is minimal if no proper subset of A is an asymptotic basis of order h. It is proved that there does not exist a sequence A that is simultaneously a minimal basis of orders 2, 3, and 4. Several open problems concerning minimal bases are also discussed.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

Sets whose sumset avoids a thin sequence

Let {a₁,a₂,a₃,…} be an unbounded sequence of positive integers with an+1/an approaching α as n→∞, and let β>max(α,2). We show that for all sufficiently large x?0, if A⊂[0,x] is a set of nonnegative integers containing 0 and satisfying

     

A just basis

An old problem of P. Erdös and P. Turán asks whether there is a basisA of order 2 for which the number of representationsn=a+a′, a,a′∈A is bounded. Erd?s conjectured that such a basis does not exist. We answer a related finite problem and find a basis for which the number of representations is bounded in the square mean. Writing σ (n)=|{(a, a ^t ) ∈A ²:a+a′=n}| we prove that there exists a setA of nonnegative integers that forms a basis of order 2 (that is,s(n)≥1 for alln), and satisfies ∑_{n ? N} σ(N)² = O(N).     

Cantor sets arising from continued radicals

If a ₁,a ₂,a ₃,… are nonnegative real numbers and $f_{j}(x) = \sqrt{a_{j}+x}$ , then lim _n→∞ f ₁°f ₂°?°f _n (0) is a continued radical with terms a ₁,a ₂,a ₃,…. The set of real numbers representable as a continued radical whose terms a _i are all from a set S={a,b} of two natural numbers is a Cantor set. We investigate the thickness, measure, and sums of such Cantor sets.     

A property of Pisot numbers and Fourier transforms of self-similar measures

For any Pisot number β it is known that the set F (β)={t:lim n→∞‖tβ n‖= 0} is countable,where a is the distance between a real number a and the set of integers.In this paper it is proved that every member in this set is of the form cβ n,where ‖n‖ is a nonnegative integer and c is determined by a linear system of equations.Furthermore,for some self-similar measures μ associated with β,the limit at infinity of the Fourier transforms lim n→∞μ(tβ n)≠0 if and only if t is in a certain subset of F (β).This generalizes a similar result of Huang and Strichartz.     

Minimal free resolution of the associated graded ring of monomial curves of generalized arithmetic sequences

Let A(C) be the coordinate ring of a monomial curve C⊆Aⁿ corresponding to the numerical semigroup S minimally generated by a sequence a₀,…,a_n. In the literature, little is known about the Betti numbers of the corresponding associated graded ring gr_m(A) with respect to the maximal ideal m of A=A(C). In this paper we characterize the numerical invariants of a minimal free resolution of gr_m(A) in the case a₀,…,a_n is a generalized arithmetic sequence.     

A note on a special case of the Frobenius problem

For a set of positive and relative prime integers A = {a ₁…,a _k }, let Γ(A) denote the set of integers of the form a ₁ x ₁+…+a _k x _k with each x _j ≥ 0. Let g(A) (respectively, n(A) and s(A)) denote the largest integer (respectively, the number of integers and sum of integers) not in Γ(A). Let S*(A) denote the set of all positive integers n not in Γ(A) such that n + Γ(A) \ {0} ? Γ((A)\{0}. We determine g(A), n(A), s(A), and S*(A) when A = {a, b, c} with a | (b + c).     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Score sets ink-partite tournaments

The set S of distinct scores (outdegrees) of the vertices of ak-partite tournamentT(X ₁, X₂, ···, X_k) is called its score set. In this paper, we prove that every set of n non-negative integers, except {0} and {0, 1}, is a score set of some 3-partite tournament. We also prove that every set ofn non-negative integers is a score set of somek-partite tournament for everyn ≥k ≥ 2.