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


    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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
    2016 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


    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Challenge IX: Dealing with Mod 1 solved by mfb