1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge IX: Dealing with Mod 1 solved by mfb

  1. Aug 15, 2013 #1
    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 [itex]\{a\}, \{an\}, \{an^2\},... [/itex] does not eventually become 0, then it will exceed 1/n infinitely many times.

    Here {x} means x - floor(x).
  2. jcsd
  3. Aug 16, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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 ai={ani}.

    1. case ai=1/n or ai=0: Our sequence will end at 0, nothing to show.
    2. case 0<ai<1/n: There is a smallest k such that 1/n<aink<=1. If aink=1, our sequence becomes 0 and there is nothing to show. Otherwise, {aink} exceeds 1/n.
    3. case 1/n < ai < 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.
  4. Aug 17, 2013 #3
    ^ This looks right to me.

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

    Let [itex]A:= \left\{e^{i\theta}:\enspace 0<\theta< \frac1n\right\}\subseteq G.[/itex] Note that [itex]f|_A[/itex] is injective.

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

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

    So an equivalent formulation is the following:

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

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

    I think an interesting question is: What are some sufficient conditions on [itex]G[/itex] and [itex]f:G\to G[/itex] to ensure that for every connected [itex]A\subseteq G\backslash\{1\}[/itex] on which [itex]f[/itex] is injective, there does not exist a nonempty [itex]S \subseteq A[/itex] such that [itex]f(S)\subseteq S[/itex]?
  5. Aug 17, 2013 #4


    User Avatar
    Homework Helper

    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.
    Last edited: Aug 17, 2013
  6. Aug 17, 2013 #5
    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!
  7. Aug 17, 2013 #6
    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 [itex] a = a_0.a_1a_2a_3... [/itex] where [itex]0 ≤ a_i ≤ n - 1 [/itex]. 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
    [itex]\{an^k\} = 0.a_{k+1}a_{k+2}a_{k+3}...[/itex].

    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 [itex]a_1[/itex] position and we have a number larger than [itex]0.100000...[/itex] 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook