Sharp bounds for the partition function of integer sequences (Q1092940): Difference between revisions

Let \(f=\{f_ 1,f_ 2,...\}\) be an infinite strictly increasing sequence of positive integers and define the partition function p of the sequence f in the following way. For any integer n, let p(n) denote the number of solutions of the equation \(n=f_{i_ 1}+...+f_{i_ s}\) with varying \(s\geq 0\) and indices \(i_ 1<...<i_ s\). \textit{K. F. Roth} and \textit{G. Szekeres} [Q. J. Math., Oxf. II. Ser. 5, 241-259 (1954; Zbl 0057.039)] presented a sufficient condition for the validity of an asymptotic expansion for the partition function p of the sequence f. As to the behaviour of p for small arguments, several authors obtained results by the application of a theorem of \textit{H.-E. Richert} [Norsk Mat. Tidsskr. 31, 120-122 (1949; Zbl 0040.308)]. The support of p may contain infinitely many integers and even all the integers greater than some minimal value. In the last case, the numbers \(b(m)=\inf \{b\geq 0|\min_{n\geq b}p(n)\geq m\}\) for \(m\geq 1\) are sharp lower bounds for the partition function p of f. The criteria of \textit{J. W. S. Cassels} [Acta Sci. Math. 21, 111-124 (1960)], \textit{P. Erdős} [Acta Arith. 7, 345-354 (1962; Zbl 0106.038)] and \textit{J. Folkman} [Can. J. Math. 18, 643-655 (1966; Zbl 0151.037)] give sufficient conditions for b(1) to be finite. Let C(m) denote the following condition. C(m): For suitable integers \(k\geq 0\), \(a\geq -1\) and \(d\geq f_{k+1}\), every integer n of \([a+1,a+d]\) has at least m representations by sums of distinct terms of \(\{f_ 1,...,f_ k\}\). H.-E. Richert [ibid.] proved that condition C(1) and the growth-condition \(f_{i+1}\leq 2f_ i\) for all \(i\geq k+1\) yield the estimate \(b(1)\leq a+1\). Theorem 1 of the paper under review asserts that condition C(m) and the growth-condition \(f_{k+i+1}\leq d+f_{k+1}+...+f_{k+i}\) for all \(i\geq 1\) yield the estimate \(b(m)\leq a+1\). Theorem 1 implies Richert's theorem (Corollary 1) and \textit{W. Sierpiński}'s theorem [Ann. Mat. Pura Appl., IV. Ser. 39, 69-74 (1955; Zbl 0066.291)] for infinite sequences with \(b(1)=0\) (Corollary 2). The main result of the paper is the following new criterion for higher multiplicities of representations. Theorem 2. For \(m\geq 2\), condition C(1) and the growth-conditions \[ f_{k+1+m}\leq d+f_{k+1},\quad f_{k+i+1}\leq d+f_{k+1}+...+f_{k+i}-f_{k+m}\text{ for all } i\geq m+1\quad and \] \[ f_{k+m-1}+f_{k+i+1}\leq d+f_{k+1}+...+f_{k+i}- f_{k+m-1}\quad (if\quad m\geq 3)\text{ for all } i\geq m+1 \] yield the estimate \(b(r)\leq a+1+f_{k+r}\) for each multiplicity r with \(2\leq r\leq m.\) Theorem 2 yields least possible bounds. A number of examples and tables are presented. The tables list the bounds b(1), b(2), b(3) and b(4) for the partition function of many integer sequences (powers, polygonal numbers, primes, primes in residue classes, iterates of the sequence of primes).