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.

  • 6
    $\begingroup$ Well, that's not true. See what happens when $a$ is the golden ratio. $\endgroup$ – Qiaochu Yuan Mar 22 '11 at 18:49
  • $\begingroup$ Here's is the direct link to fedja's post on the MO thread: mathoverflow.net/questions/59115/… $\endgroup$ – Rahul Mar 22 '11 at 20:31
  • $\begingroup$ 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. $\endgroup$ – George Lowther Mar 22 '11 at 22:06

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.

  • $\begingroup$ I don't understand why the trick shouldn't work for every real number. Simply use completeness of the real line and create a sequence $K_n$ such that the distance from $Ka^n$ to the nearest integer is less than $1/n$. Why this does not work? $\endgroup$ – ooboo Mar 23 '11 at 14:41
  • $\begingroup$ @ooboo: I don't understand the question. The argument applies to a real number $a$ which satisfies the condition. The conclusion of the argument shows precisely that most real numbers do not satisfy the condition, so what does it mean to apply the argument to an arbitrary real number? $\endgroup$ – Qiaochu Yuan Mar 23 '11 at 20:16
  • $\begingroup$ @ooboo: You can create a sequence $K_n$ such that the distance from $K_na^n$ to the nearest integer is less than $1/n$. You can also do it so that $K_n$ tends to a limit $K$. That does not mean that the distance from $Ka^n$ to the nearest integer approaches zero. $\endgroup$ – George Lowther Mar 23 '11 at 22:22
  • $\begingroup$ Why not? I create a sequence of closed intervals $I_1 \supset I_2 ...$ such that for every $x \in I_n$ the distance from $xa^n$ to the nearest integer is less than $1/n$. So if $K$ is a real number that belongs to all these intervals then the distance from $Ka^n$ to the nearest integer is less than $1/n$ for any $n$ $\endgroup$ – ooboo Mar 24 '11 at 10:21
  • $\begingroup$ @ooboo: No, for most real numbers $a$ there does not exist a sequence of nested intervals as you describe. $\endgroup$ – George Lowther Mar 25 '11 at 0:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.