7
$\begingroup$

I'm referring to an answer posted on Math Overflow (see the post by fedja on https://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable)

The question is whether the set of real numbers $a > 1$ so that for $K > 0$ the distance between $K a^n$ and its nearest integer approaches $0$ for $n \to \infty$ is countable.

The integers are obviously in that set. However I couldn't come up with a proof that for all other reals the limit does not exist.

  • 0
    You can show that it is countable easy enough (they are all computable numbers, for one thing), but I don't know$a$simple way of describing the set. Fedja's comment that it is not known if it is a subset of the algebraic numbers suggests nobody else knows either.2011-03-22

2 Answers 2

7

Here's a method of generating the set of numbers described in a way which makes clear that it is countable (so look away if you're taking Fedja's challenging to see how quickly you can prove it!).

Suppose that the distance beween $Ka^n$ and the nearest integer tends to zero. Then, letting $u_n$ be the nearest integer to $Ka^n$, you have $a=\lim_{n\to\infty}\frac{u_{n+1}}{u_n}$. Also, $Ka^n-u_n\to0$ and $u_n\to\infty$ as $n\to\infty$.

Then, $u_{n+2}-u_{n+1}^2/u_n\to0$. This means that, for large enough $n$, $ u_{n+2}={\rm closest\ integer\ to\ }\frac{u_{n+1}^2}{u_n}. $ Replacing $K$ by $Ka^m$ for large enough $m$, this can be assumed to hold for all $n\ge0$. So, we have a recurrence relation generating the entire sequence once $u_0,u_1$ are given, and allows us to calculate $a=\lim_{n\to\infty}u_{n+1}/u_n$. Therefore every element of the set is determined by a pair of positive integers $\{u_0 < u_1\}$, so it is countable.

  • 0
    @only: yes, I fixed this. Thanks2012-05-05
5

For integral K any Pisot-Vijayaraghavan number will do the trick (Qiaochu gives an example of one in the comments) - and there are a lot of these, although countably many. Regardless, these are good examples of how arbitrary non-integers can satisfy your condition.

A not-terribly-complicated proof of the fact that any PV number satisfies your condition for $K = 1$ is as follows. Consider a PV number $\alpha$ and its minimal polynomial p (in $\mathbb{R}/\mathbb{Q}$). Let the roots of p be $\alpha = x_1, x_2, \cdots, x_k$. By the fundamental theorem of symmetric polynomials, we know that the expression $P_n = x_1^n + x_2^n + \cdots + x_k^n$ is an integral linear combination of the symmetric polynomials in $x_1, x_2, \cdots, x_k$ - which, by Vieta's formulas, are simply the coefficients of p (as the minimal polynomial is monic). As p has integral coefficients, $P_n = x_1^n + x_2^n + \cdots + x_k^n$ is an integer for all n. As $\alpha$ is a PV-number, we know that $|x_2|, |x_3|, \cdots, |x_k| < 1$. So we have for large n that $|P_n - \alpha^n| < |x_2|^n + |x_3|^n + \cdots + |x_k|^n << 1,$ that is, $P_n - \alpha^n \rightarrow 0$ as desired.

This proof will work for any integer K - as for non-integer K, unless I'm missing something obvious (which could very well be the case) this is quite a bit harder. You might be able to use a nice trick to get rationals, but I suspect irrationals are a real pain.