An estimate for the number of terms in the Hilbert--Kamke problem

D. A. Mit'kin

Sbornik. Mathematics, Tome 57 (1987) no. 2, pp. 561-590

Résumé

Let $r(n)$ denote the smallest $s$ for which the system of equations \begin{equation} x^j_1+\dots+x^j_s=N_j\qquad(j=1,\dots,n) \end{equation} is solvable in nonnegative integers $x_1,\dots,x_s$ for all sufficiently large natural numbers $N_1,\dots,N_n$ which satisfy the following conditions: 1) the singular integral $\gamma=\gamma(N_1,\dots,N_n)$ of the system (1) satisfies the inequality $\gamma\geqslant c(n,s)>0$ (the order conditions). 2) the system of equations $\sum^n_{k=1}k^jt_k=N_j$ $(j=1,\dots,n)$ is solvable in integers $t_1,\dots,t_n$ (the arithmetic conditions). In 1937, K. K. Mardzhanishvili proved that $n^2\ll r(n)\leqslant n^42^{2n^2-n-2}$. G. I. Arkhipov has recently obtained upper and lower estimates for $r(n)$ having the same order of magnitude: $2^n-1\leqslant r(n)\leqslant3n^32^n-n$ $(n\geqslant5)$. In this paper, the upper estimate for $r(n)$ is reduced to \begin{equation} r(n)\leqslant\sum_{0\leqslant k\leqslant[\ln n/\ln2]}2^k(2^{[n/2^k]}-1)\qquad(n\geqslant12); \end{equation} in particular, the asymptotic formula $r(n)=2^n+O(2^{n/2})$ is obtained. It is conjectured that the estimate (2) is best possible. Bibliography: 20 titles.