Beatty solutions of almost Golomb functional equations

Abstract

We study the almost Golomb equation of order $r$, $a(S(n))=n$, where $S(n)=a(n)+a(n-1)+\cdots +a(n-r+1)$, for nondecreasing sequences of positive integers. Its greedy solution is $r$-regular in the sense of Allouche and Shallit. Beyond that one, and for every non-square order $r$, the equation has another solution, an inhomogeneous Beatty sequence $a(n)=\lfloor n/\sqrt{r}+d\rfloor$ where $d$ is a parameter. No other positive slope occurs, and the equation holds for all $n\ge r$ exactly when $d$ lies in an explicit closed interval depending on $r$. That interval is a single point when $r=2$ and has positive length for every non-square $r\ge 3$. Iterating the equation gives, for $k\ge 1$, $a^{\circ k}(S(n))=a^{\circ (k-1)}(n)$, with $a^{\circ 0}$ the identity. Its Beatty solutions of positive slope are again of the form $\lfloor n/\sqrt{r}+d\rfloor$, and the sets of admissible $d$ form an increasing chain. The equation for $k$ holds exactly when $a^{\circ (k-1)}$ agrees at $n$ and at $a(S(n))$. We determine these solutions for $k=2$ when $r=2$ and $r=3$. At the right endpoint of the $r=2$ interval the first equation fails on a thin set of indices, which we identify as the return times of an irrational rotation to an explicit interval. The proofs combine equidistribution with an exact computation in $\mathbb{Z}[\sqrt{r}]$ over a finite range of orders.

43 pages, 2 figures. This version: the shift interval is determined for every non-square r, and the equation is iterated. The Beatty-shift intervals for the triple-nested equation are proved sharp for r=2 and r=3