An effective additive basis for the integers
type: Item
instance of: scholarly article
title: An effective additive basis for the integers
zbMATH Open document ID: 0838.11005
DOI: 10.1016/0012-365X(94)00044-J
published in: Discrete Mathematics
publication date: 1996-06-03T00:00:00Z
review text: \textit{P. Erdös} [Acta Sci. Math. 15, 255-259 (1954; Zbl 0057.03901)] proved by probabilistic means the existence of a set \(E\) of integers such that the number \(r(n)\) of representations of \(n\) as a sum of two elements of \(E\) satisfies \(c \log n < r(n) < C \log n\). Here an effective construction of such a set is given. The decision to include or exclude \(n\) depends on certain conditional probabilities, whose definition is motivated by Erdös' proof. The procedure produces the elements of \(E\) one by one and the time requires to find all elements up to \(n\) is polynomial in \(n\).
Mathematics Subject Classification ID: 11B13
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 810276
zbMATH Keywords: effective additive basis
author: Mihail N. Kolountzakis
reviewed by: Imre Z. Ruzsa
MaRDI profile type: Publication
Wikidata QID: Q60360137
cites work: The probabilistic method
cites work: Q5829865
cites work: Q3963072
full work available at URL: 0012-365x(94)00044-j
OpenAlex ID: W2109813872
description: scientific article; zbMATH DE number 810276