Challenge IX: Dealing with Mod 1 solved by mfb

[micromass]

This challenge was proposed by Boorglar. Many thanks to him!

Let n be a natural number larger than 1, and a be a positive real number.
Prove that if the sequence \{a\}, \{an\}, \{an^2\},... does not eventually become 0, then it will exceed 1/n infinitely many times.

Here {x} means x - floor(x).

 

[mfb]

As x-{x} is an integer, {an}={{a}n} for natural numbers n.
This implies that it is sufficient to consider 0<=a<1. In addition, every value in the sequence depends on the previous value (and n) only.
As a special case, {0n}=0, for a=0 there is nothing to show.

Let a_i={anⁱ}.

1. case a_i=1/n or a_i=0: Our sequence will end at 0, nothing to show.
2. case 0<a_i<1/n: There is a smallest k such that 1/n<a_in^k<=1. If a_in^k=1, our sequence becomes 0 and there is nothing to show. Otherwise, {a_in^k} exceeds 1/n.
3. case 1/n < a_i < 1: Good, we found another element that exceeds 1/n. {an} will be one of the three cases again.

Each a which does not end up in case 1 has to stay in case 2 and 3, and case 2 always leads to case 3 in a finite number of steps. Therefore, case 3 gets visited infinitely many times.



Follow-up question: can we find general conditions such that the sequence is below 1/n infinitely many times?
This is not true for all (a,n), as the example a=1/2, n=3 shows.

 

[economicsnerd]

^ This looks right to me.

A rephrasing toward some generalization.
Let G:=\{z\in\mathbb C:\enspace |z|=1\}=\{e^{i\theta}\}_{\theta\in\mathbb R}, a nice (compact abelian) topological group under multiplication. Fixing n, let f:G\to G be the n^{\text{th}} power map, a group covering.

Let A:= \left\{e^{i\theta}:\enspace 0&lt;\theta&lt; \frac1n\right\}\subseteq G. Note that f|_A is injective.

Let B:=\{z\in G: \enspace \nexists k\in \mathbb N \text{ with } f^k(z)=1\}, the set of elements that don't have finite order divisible by n.

We want to show that iterating f on any element of B crosses through G\backslash A infinitely many times. By the inductive argument mfb used (which works because f^{-1}(B)=B and f is surjective), it's enough to show that iterating f on any element of B crosses through G\backslash A at least once.

So an equivalent formulation is the following:

Show that there does not exist a nonempty S \subseteq A such that f(S)\subseteq S.

[Note that such S would be a subset of B as well, as it excludes 1.]

I think an interesting question is: What are some sufficient conditions on G and f:G\to G to ensure that for every connected A\subseteq G\backslash\{1\} on which f is injective, there does not exist a nonempty S \subseteq A such that f(S)\subseteq S?

 

[verty]

Regarding the follow-up question, here are some calculations:

Let k be the greatest natural number such that $A_k = \{a × 3^k\} < \frac{1}{3}$.
Let $x = A_k$.

$0 < x < \frac{1}{3}$
$\{3x\} ≥ \frac{1}{3}$
$\frac{1}{9} ≤ x < \frac{1}{3}$

$1 ≤ 9x < 3$
$\{9x\} ≥ 1/3$
$\frac{4}{3} ≤ 9x < \frac{6}{3}$, $\frac{7}{3} ≤ 9x < \frac{9}{3}$
$\frac{4}{27} ≤ x < \frac{6}{27}$, $\frac{7}{27} ≤ x < \frac{9}{27}$

And so on, giving:

$A_k \in \{ x \in (0, \frac{1}{3}) : \forall k ≥ 0, \forall n ≥ 2, x \in \bigcup \; [ \; (1 + 3k)/3^n, (3 + 3k)/3^n \; ) \; \}$

This is an interesting set. I don't know that much about it but the smallest number it contains is $\frac{1}{6}$, the limit of this sequence: $\frac{1}{9}, \frac{4}{27}, \frac{13}{81}, \frac{40}{243}, \frac{3^n - 1}{6.3^n}$. But this means $\{y : \frac{1}{3} < y < \frac{1}{2} \land \{y × 3^n\} ≥ 1/3 \} = ∅$, for if there was such a y, $\frac{y}{3}$ would be a candidate for $A_k$ above, but $\frac{y}{3} < \frac{1}{6}$.

So there is an interesting void between $\frac{1}{3}$ and $\frac{1}{2}$ where no number is such that the fractional part is never below 1/3.

 

[micromass]

Congratulations to mfb for giving a nice solution to the problem.

I'm wondering if there are nice solutions to the follow-up questions by mfb and economicsnerd. Verty already came up with something nice though.

Thanks everybody for their contributions!

 

[Boorglar]

Since the original question seems to have been solved, I might just as well post my own solution, which is basically the same as mfb's but more visual I guess.

Write a as a infinite decimal in base n. Then a = a_0.a_1a_2a_3... where 0 ≤ a_i ≤ n - 1. Multiplying by n is equivalent to shifting the decimal point towards the right, and taking the fractional part changes to 0 all digits left of the decimal point. So basically
\{an^k\} = 0.a_{k+1}a_{k+2}a_{k+3}....

If a is a rational number with denominator which divides n, then (as in base 10 for 1/2 and 1/5) the base n expansion eventually terminates and all remaining digits will be 0 which corresponds to the sequence becoming 0. Otherwise, if the base n expansion doesn't terminate then there will always be some non-zero digit no matter how far. When shifting, these non-zero digits will eventually arrive at the a_1 position and we have a number larger than 0.100000... which is 1/n. Since there are infinitely many nonzero digits, the sequence exceeds 1/n infinitely many times as stated.

For the follow-up, for the sequence to be below 1/n infinitely many times is equivalent to the number a containing infinitely many 0's in its base n expansion. So for example, if n = 3, then the numbers for which the sequence does not get below 1/n infinitely many times are those that end with an infinite sequence of 1's and/or 2's, such as:
0.10120(12)... or 0.2012112111211112111112... This set looks a bit similar to the Cantor set.