Only integers behave nicely

This week I solved the following PEN-problem:

Find out which pairs of real numbers (\alpha, \beta) have the property that: \alpha [\beta n] = \beta [\alpha n] for all natural numbers n, where [x] denotes the largest integer \le x

At first glance, this problem looked quite easy to me. While I’m not sure if that’s a good sign in general, in this case it was advantageous. Because some problems that are stated in the form ‘find all x such that y’, are only solvable by providing a way of finding those x, where that way of finding, immediately shows that you’re right. This might be vague, so let me give you an example. Consider the problem of finding all primes less than 10000. I guess that no one will just write down the list of primes. No, probably everyone will just use the sieve of Eratosthenes. And not only will that sieve give you all primes below 10000 it is/should be immediately clear why it works and generates all these primes. So using the sieve of Eratosthenes gives the answer and proves you`re right in one blow. While that’s awesome, in general it’s not that easy to straightforwardly find a solution that strong. Going back to the problem at hand, you may feel that it begs for an impossibility proof, except for trivial or ‘degenerate’ cases. In other words, we already ‘found’ our solution, we only have to prove it’s right. In still other words, we already know how or where to start (for example: assume a true non-degenerate case) and where to end (in contradiction). And knowing how a proof could reasonably look like, before you even started, is a big advantage, I think.

Ok, so far the preliminary remarks. To concretise the above part, the degenerate cases are:

1) \alpha \beta = 0
2) \alpha, \beta \in Z
3) \alpha = \beta

It’s a trivial matter to show that all these cases indeed solve \alpha [\beta n] = \beta [\alpha n]. Now, I kind of simplified things in the above paragraph. Because there is definitely not 1 way to prove we’re right that these cases are the only ones that solve the above equation. We could assume that 1), 2) and 3) all don’t hold and end up in contradiction, we could assume 0 < |\alpha| < |\beta| and try to prove \alpha, \beta \in Z, we could (since proving that \alpha is integral iff \beta is, is trivial), assume that \alpha, \beta \notin Z and show that \alpha = \beta must hold, etc. There are tons of distinct ways to end up where we want to end up. But, in a way, they’re all the same too, of course.

One of the first things I did was assuming that both \alpha and \beta are positive. This is something I do a lot, because, well, I’m just not that fond of negative numbers. Moreover, usually the general case quite easily simplifies to the positive case and in here I felt it was a natural thing to do. Although it turned out that we actually do lose generality, without an extra argument, by assuming positivity, it was still a useful pet problem, so let’s assume positivity for now anyway. The next thing I tried was dividing both sides by \beta[\beta n] to get our first result: \dfrac{\alpha}{\beta} = \dfrac{[\alpha n]}{[\beta n]} is rational! While this is not much, it accounts for something. This inspired me to do a few things; First of all I filled in n = 1 and found out for which real numbers this equation holds by letting: \alpha = a + \gamma, \beta = b + \delta for integral a,b such that 0 < \gamma, \delta < 1. Second of all I noticed that this argument doesn’t work if a = b = 0, because then we just have \dfrac{\alpha}{\beta} = \dfrac{0}{0}, and there’s not much to conclude from that. So I tried to prove ab \neq 0, in which I succeeded (see below). Third of all, since we know that \dfrac{\alpha}{\beta} \in Q, it seems natural to (try to) show that \alpha and \beta can’t be distinct, rational, non-integral numbers. As it turns out, this is quite straightforward, so to solve our problem, the following suffices:

Let \alpha,\beta be distinct, irrational numbers. Then \alpha [\beta n] \neq \beta [\alpha n] for at least 1 positive integer n.

Like I said, proving that \alpha, \beta > 1 (while assuming positivity and distinctness), is possible, so here is its proof: Let \alpha < \beta. If \alpha < 1, \beta < 1 as well, otherwise we would have: \displaystyle \frac{[\alpha]}{[\beta]} = 0 < \frac{\alpha}{\beta}, which is a contradiction. So we may assume 0 < \alpha < \beta < 1. Let N be the smallest integer such that \beta N > 1. Then \alpha N must be larger than 1 as well, because otherwise we would have the same contradiction as above. But we now have: \displaystyle \frac{[\alpha N]}{[\beta N]} = \frac{1}{1} = 1 = \frac{\alpha}{\beta}, which implies \alpha = \beta. So if \alpha and \beta are distinct and positive (although I hardly used the positivity condition), \alpha [\beta n] = \beta [\alpha n] can’t hold for all natural numbers n.

Now that we showed that, we can definitely say we are on our way. A cool way to go further is by using induction. When you see an (moderately easy) equation that should hold for all natural numbers n, it’s often possible to show that it indeed holds by using induction on n. However, here it might be possible to go the other way around, by using induction on \alpha! More precisely; assume that \alpha [\beta n] \neq \beta [\alpha n] for some natural number n. Show that a natural number m exists for which (\alpha + 1) [\beta m] \neq \beta [(\alpha + 1) m] (except degenerate cases). And since we proved our base case (0 < \alpha, \beta < 1), this suffices. I must say I think this way of attacking our problem is both weirdly awesome and awesomely weird. But when I first tried it, the computations didn’t make any sense, so I chose a different approach. Although I might give it some thought again, since I have a better understanding of the problem now. Anyway, for me this wasn’t the way to go, so let’s try something else.

The good part is: we didn’t use the, to me, most obvious way of approaching this problem, extensively yet. So let’s do that. I believe that, whenever you’re dealing with the ‘greatest integer smaller than’-function, it’s usually a great idea to split that what’s inside the gist-function in two parts: an integer part and a rest part. For example: [9.87] = [9 + .87] = 9 + [.87]. So let’s, like I said above briefly, assume \alpha = a + \gamma, \beta = b + \delta with a, b \in Z and 0 < \gamma, \beta < 1. Then we have:

\alpha [\beta n] = \beta [\alpha n]
(a + \gamma) [(b + \delta) n] = (b + \delta) [(a + \gamma) n]
(a + \gamma)(bn + [\delta n]) = (b + \delta)(an + [\gamma n])
(a + \gamma) [\delta n] + \gamma bn = (b + \delta) [\gamma n] + \delta an
\alpha [\delta n] + \gamma bn = \beta [\gamma n] + \delta an

We know that this must hold for all n \in \aleph. In particular, it should hold for n = 1. When n = 1, the above equation simplifies to:

\gamma b = \delta a

So we know that this must be the case. But then \gamma bn and \delta an always cancel each other out, so the equation becomes:

\alpha [\delta n] = \beta [\gamma n ]

And the great news is that we basically solved this equation already, when we showed the impossibility of distinct, positive integers \alpha, \beta such that \alpha [\beta n] = \beta [\alpha n] for \alpha and \beta smaller than 1. But, for completeness’ sake; let N be the smallest positive integer such that \max(\gamma N, \delta N) \ge 1. Then \min(\gamma N, \delta N) \ge 1 as well, because otherwise we would have 0 on one side of the equation while the other side is non-zero. Since our equation is true for all n \in \aleph, it must be true for N too. And for this N, it further simplifies to:

\alpha = \beta

And we’re done.


One Response to “Only integers behave nicely”

  1. Yes, only integers « Woett's Blog Says:

    […] my post ‘only integers behave nicely’, I came up with another proof (and another variation of it) of the following […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: