Random gap processes and asymptotically complete sequences (Q2135190)

The theme of this paper is the random construction of complete sequences. A non-decreasing sequence \(a_1 \leq a_2 \leq a_3 \leq \cdots\) is said to be complete if any natural number can be written as an index-distinct sum of members of this sequence. Such is, for example, the sequence of powers of 2, since every natural number has a unique binary expansion. If \(d\) is the greatest common divisor of the sequence and any sufficiently large multiple of it can be expressed as the \(k\)-fold index-distinct sum of members of the sequence, then this is called \textit{asymptotically \(k\)-complete}. If this is possible with at most \(k\) summands, then the sequence is called \textit{asymptotically} \(\leq k\)-\textit{complete}. The paper considers the probability that a randomly constructed sequence is complete or \(k\)-complete for some \(k\geq 2\). In particular, a random sequence \(\{W_i\}_{i\geq 1}\) is constructed with \(W_1 =1\) and the gaps \(W_{i+1} - W_i\), for \(i\geq 1\), being i.i.d. positive, integer-valued random variables. The main theorem of the paper gives a condition on the common distribution of the gaps which implies that with probability 1, the resulting sequence is asymptotically \(k\)-complete. Suppose that \(\{s_i\}_{i\geq 1}\) is the support of this distribution, where \(s_i\) occurs with probability \(p_i\). Suppose that \(-\log p_*/s_* = \inf_{i \in \mathbb{N}} (- \log p_i/s_i)\geq 0\). If the moment generating function of the distribution has radius of convergence larger than \(-\log p_*/s_*\), then for any \(k\geq 2\) the random sequence is asymptotically \(k\)-complete with probability 1. In particular, the assumption holds in the case where the gaps are Poisson-distributed as well as in the case where they are geometrically distributed with parameter (success probability) greater than \((\sqrt{5}-1)/2\). The authors also show a weaker result in which the assumption is that the distribution of the gaps has finite \(1/2\)-moment. Then with probability 1 the sequence is asymptotically complete.