# When is a sequence the sum of two Beatty sequences?

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.

• "Given a sequence" -- what exectly this means? Generally speaking, a sequence is an infinite object. – Max Alekseyev Jun 29 '15 at 16:54
• As Max Alekseyev says, a sequence is an infinite object, and there are many irrational numbers to test... This question might very well be undecidable, and if not, the question if a sequence is a sum of a finite number of Beatty sequences might be... – Per Alexandersson Jun 29 '15 at 17:16
• I would guess that Fourier analysis could tell you something: once you remove the linear part, what you have is a sum of some quasiperiodic phenomena with various different periods, and that's exactly the sort of thing that Fourier analysis is good at explaining. There must be someone around who can push this further (or explain why it's a stupid idea) much faster than me though. – James Cranch Jun 29 '15 at 19:18

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?

• Does this generalize if it is a sum more then two Beatty sequences? – Per Alexandersson Jun 29 '15 at 20:42
• @PerAlexandersson If they are $\mathbb Q$-linearly independent, yes by similar logic. – Will Sawin Jun 30 '15 at 1:46

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