Partitioning the positive integers with higher order recurrences (Q1178781): Difference between revisions

For \(\alpha > 1\), irrational, \(n\in \mathbb{Z}\), \(g(n)=[\alpha n+1/2]\) is the closest integer to \(\alpha n\). We define the array \(\{s(i,j)\}\) of positive integers where: \(s(1,1)=1\), \(s(i,j)=g(s(i,j-1))\) for \(j>1\) and \(s(i,1)\) is the least positive integer not in the set \(\{s(h,j)\mid h<i\}\). This array is a Stolarsky array if: (i) every positive integer occurs exactly once in the array, and (ii) \(\exists c_ 0,c_ 1,\dots,c_{k-1}\in \mathbb{Z}\) such that \(\forall i,\forall j \geq k+1\), \(s(i,j)=c_{k-1}s(i,j-1)+c_{k-2}s(i,j-2)+\dots+c_ 0s(i,j-k)\). K. Stolarsky examined the array formed from \(\alpha = (1+\sqrt{5})/2\), the larger root of \(x^ 2-x-1\). Other workers have investigated other quadratic integers. The author extends this analysis to roots of cubic and higher order polynomials. Let \(r_ \ell=\alpha g^{\ell-1}(n)-g^ \ell(n)\), so \(| r_ \ell| < 1/2\). The author proves that an array satisfying the linear recurrence in (ii) is a Stolarsky array if and only if \[ \begin{multlined}\left|{1\over 2(\alpha-1)}(c_ 0+c_ 1+\dots+c_{k-1}- 1)-{r_ 1c_ 0\over \alpha}-{r_ 2(c_ 0+c_ 1\alpha)\over \alpha^{k-1}}-\right.\dots \\\left. -{r_{k-1}(c_ 0+c_ 1\alpha+\dots +c_{k-2}\alpha^{k-2})\over \alpha^{k-1}}-r_ k\right| < 1.\end{multlined} \] Using this criterion the author shows that the largest real root \(\alpha\) of \(p(x)=x^ k-x^{k-1}-\dots - x- 1\), gives a Stolarsky array for \(k\geq 2\), and the largest real root \(\beta\) of the cubic \(q(x)=x^ 3-a_ 2x^ 2-a_ 1x-a_ 0\) gives a Stolarsky array provided \(a_ 0\geq 1\), \(a_ 1\geq a_ 0(1-(1/\beta))\) and \(a_ 2\geq ((a_ 0/\beta) + a_ 1)(1-(1/\beta))\).