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.

  • 6
    Well, that's not true. See what happens when $a$ is the golden ratio.2011-03-22
  • 0
    Here's is the direct link to fedja's post on the MO thread: http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59130#591302011-03-22
  • 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

6

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
    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?2011-03-23
  • 0
    @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?2011-03-23
  • 0
    @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.2011-03-23
  • 0
    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$2011-03-24
  • 0
    @ooboo: No, for most real numbers $a$ there does not exist a sequence of nested intervals as you describe.2011-03-25
  • 0
    George: does the existence of a sequence $K_n$ such that the difference between $K_na^n$ and the nearest integer is less than $1/n$ not imply the existence of a sequence of such closed intervals?2011-03-29
  • 0
    Nitpick: shouldn't it be $\frac{u_{n+1}}{u_n}$ instead of $\frac{u^{n+1}}{u^n}$? (In the second paragraph.)2012-05-04
  • 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.