Remarks on number theory. III. (Hungarian. English, Russian summaries) Zbl 0123.25503

Summary: Let \(a_1 < a_2 < \cdots\), \(A(x) = \sum_{a_i \leq x} 1\) be an infinite sequence for which (1) \(a_k=a_{i_1}+\cdots +a_{i_r}\), \(i < \cdots < i_r < k\), is not solvable. I prove that \(A(x)/x \to 0\) and that \(\sum {1 \over a_i} < 103.\) Further I show that \(A(x) = o(x)\) is best possible, but there always exists a sequence \(x_i \to \infty\) for which (2) \(A(x) < Cx_i^{(\sqrt5-1)/2}\). On the other hand, there exists a sequence \(A\) for which (1) has no solutions, but \(A(x)>cx^{2/7}\) for every \(x\). Perhaps (2) can be improved, but the exponent can certainly not be made smaller than \(2/7\). Consider now the sequences \(A\) for which the equation (1’) \(a_{r_1}+\cdots+a_{r_{s_1}}=a_{l_1}+\cdots+a_{l_{s2}},\) \(r_1 <\cdots< r_{s_1}\); \(l_1 <\cdots<l_{s_2}\); \(s_1 \neq s_2\), is not solvable for every choice of \(s_1 \neq s_2\). There exists such a sequence with \(A(x) > c_x^{\alpha}\) for every \(x\) if \(\alpha\) is sufficiently small. On the other hand, I show by using Rényi’s strengthening of the large sieve of Linnik that if \(A\) is such that (1’) has no solutions, then \(A(x) < cx^{5/6}\) for every \(x\) if \(c\) is a sufficiently large absolute constant. Perhaps the exponent \(5/6\) can be improved, but I have not succeeded in doing this.


11B75 Other combinatorial number theory

Online Encyclopedia of Integer Sequences:

Length of shortest addition chain for n.