When is a sequence the sum of two Beatty sequences?

Question

In other words, given a sequence $(s_n)$, how can we tell if there exist irrationals $u>1$ and $v>1$ such that

$$s_n = \lfloor un\rfloor + \lfloor vn\rfloor$$

for every positive integer $n$?

A few thoughts: Graham and Lin (Math. Mag. 51 (1978) 174-176) give a test for $(s_n)$ to be a single Beatty sequence $(\lfloor un\rfloor)$ (which they call the spectrum of $u$). Perhaps someone knows a reference for a test for sums of two or more Beatty sequences? A special case would be a test for a given sequence $(s_n)$ to be the sum of two complementary Beatty sequences (i.e., $1/u + 1/v = 1$).

In response to comments, the part of the question that says "for every positive integer n" indicates that the intended sequence is infinite. It seems to me that the question, as stated above, is okay. If it's undecidable - well, that's of interest.

In any case, while it may be difficult to give a test that actually finds $u$ and $v$ when such numbers exist, there are some simple tests for deciding that $(s_n)$ is not a sum of two Beatty sequences:

(1) $\lim_{n\to\infty}s(n)/n$ must exist;

(2) if $u$ and $v$ exist, then $u$ + $v$ = $\lim_{n\to\infty}s(n)/n$;

(3) $\lfloor(u+v)n\rfloor \in \{[un]+[vn],[un]+[vn]+1\}$ for every $n$;

(4) if $(s_n)$ is a sum of two Beatty sequences, then the difference sequence of $(s_n)$ consists of at most three terms; and if there are three, then they are consecutive integers.

It's easy to see how each of those generalizes to give a "negative test"; that is, a way to see that a given $(s_n)$ is not a sum of any prescribed number of Beatty sequences. I hope that someone can find more "negative tests", or even better, a "positive test", perhaps similar to Graham and Lin's result.

Answer 1

Let's use the notation $\{ x\}$ for the fractional part of a number $x$.

Assume $u, v$, and $u/v$ are all irrational.

Then, $\{un\}$ and $\{vn\}$ behave as independent uniform random variables. (This is proved by Fourier analysis, vindicating James Cranch's suggestion) $s_{n+1}-s_n$ depends on $\{un\}$ and $\{vn\}$:

It is $\lfloor u \rfloor + \lfloor v \rfloor$ if $\{un\} < 1- \{u\}$ and $\{vn\} < 1 - \{v\}$

$\lceil u \rceil + \lceil v \rceil$ if $\{un\} \geq 1- \{u\}$ and $\{vn \} \geq 1- \{ v\}$

and the integer intermediate between those two otherwise.

So by measuring the frequencies with which these $s_{n+1}-s_n$ takes its maximal value, its minimal value, or the intermediate one, we can determine $\{u\} \{v\}$ and $(1-\{u\})(1-\{v\})$, hence by solving the equation $\{u\}$ and $\{v\}$. Then clearly how we distribute the integer part between $u$ and $v$ does not affect $\lfloor un \rfloor + \lfloor vn \rfloor$, so we can choose any values of $u$ and $v$ with the correct fractional part and sum and plug them in to see if they fit our sequence.

In fact the same thing works if just $u/v$ is irrational, because they are independent non-uniform random variables, and the probability that $\{un\}$ and $\{vn\}$ is in the range to increase by a larger amount is still $\{u\}$ or $\{v\}$ just because the average increase of $\lfloor un\rfloor$ or $\lfloor vn \rfloor$ must be $u$ and $v$ respectively.

Does this still work even if the ratio $u/v$ is rational?

Answer 2

This is the closest I can come to a positive test, but I don't know how well it will work for you. It is essentially taking the intersection of possible solution sets.

Let us cut down on symmetry by assuming $u \geq v \gt 1$. (I suppose if $u=v$ that would be a tipoff.) For each positive integer $i$, intersect the $u-v$ domain assumed above with the set of $(u,v)$ such that $s_i = \lfloor ui \rfloor + \lfloor vi \rfloor$. If the intersection is nonempty, then there is $(u,v)$ in the intersection which satisfies all the relations, and that gives you a positive result. It is unclear if there will be more than one pair though. It is also not clear if you can use this to predict the first few decimals of either $u$ or $v$.

Gerhard "Uncertain If It Is Positive" Paseman, 2015.06.29