Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quick questions~

  1. Nov 29, 2005 #1
    Quick question~

    Is it true that

    [tex] \forall p,q,r \in \mathbb{N} \text{ where } p > q > 0 , [/tex]
    [tex] \exists \left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} {\text{ such that }}\frac{r}{q} = \sum\limits_{k = 0}^n { a_k \left( \frac{p}{q} \right) ^ k } \;\, ? [/tex]
    Last edited: Nov 30, 2005
  2. jcsd
  3. Dec 4, 2005 #2
    :bugeye: Any ideas??
  4. Jan 10, 2006 #3
    Just an example,

    Let [tex]p=3[/tex], [tex]q=2[/tex], and [tex]r=8[/tex].

    [tex]\bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} = \left\{ {0,\frac{1}{2},1} \right\} [/tex]

    Oh, and [tex] r/q = 8/2 = 4[/tex].

    *Now, to satisfy the conditions
    [tex]\left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}}[/tex]
    [tex]\frac{r}{q} = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k } [/tex]

    [tex]\left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} = \left\{ {1,\frac{1}{2},1} \right\}[/tex]

    And so,
    [tex]\sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k} = 1\left( {\frac{3}{2}} \right)^0 + \frac{1}{2}\left( {\frac{3}{2}} \right) + 1\left( {\frac{3}{2}} \right)^2 = 4 = \frac{r}{q}[/tex]

    :smile: Again, I ask:

    [tex] \forall p,q,r \in \mathbb{N} \text{ where } p > q > 0 , \; \text{does} [/tex]
    [tex] \exists \left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} {\text{ such that }} \,\frac{r}{q} = \sum\limits_{k = 0}^n { a_k \left( \frac{p}{q} \right) ^ k } \;\, ? [/tex]
  5. Jan 10, 2006 #4
    Excuse me, but how {1,1/2,1} is a subset of {0,1/2,1} in the above example?
  6. Jan 10, 2006 #5


    User Avatar
    Science Advisor

    Because sets don't have "multiple" members. {1, 1/2, 1} is exactly the same as {1/2, 1} which is clearly a subset of {0, 1/2, 1}
  7. Jan 16, 2006 #6
    Hmm...to prove the original statement, we just have to show that:

    \forall p,q \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\
    \mathbb{N} \subset \bigcup\limits_{k \geqslant 0} {\left\{ {\sum\limits_{n = 0}^\infty {\left( {\left\lfloor {\frac{k}{{p^n }}} \right\rfloor - p\left\lfloor {\frac{k}{{p^{n + 1} }}} \right\rfloor } \right)\left( {\frac{p}{q}} \right)^n } } \right\}} \hfill \\
    \end{gathered} [/tex]
    Last edited: Jan 17, 2006
  8. Jan 17, 2006 #7


    User Avatar
    Science Advisor
    Homework Helper

    Adopt the convention that 0 is a natural number. Let [itex]\mathbb{Z}_p[/itex] denote the set {0, 1, ..., p-1}. Given naturals r, p, and q such that p > q > 0, the problem can be considered as that of proving that there exists a natural n such that there exists a = (a1, a2, ...) in [itex]A = \mathbb{Z}_p \times \mathbb{Z}_p \times \dots[/itex] such that for all i > n, ai = 0 and

    [tex]r = \sum_{k=0}^{\infty}a_i\left(\frac{p}{q}\right)^k[/tex]

    Suppose there exists m such that r = (pm+1)/qm. Given an arbitrary element a of A, define deg(a) to be the least natural number such that ak = 0 for all k > deg(a). I claim that given this configuration of r, p, and q (and I'll probably have to add in some extra hypotheses along the way) there exists no a in A satisfying the requirements.

    Case 1: deg(a) > m
    Case 2: deg(a) = m
    Case 3: deg(a) < m

    Case 1 implies that the sum that r is supposed to equal to is greater than or equal to (p/q)m+1 which is greater than (pm+1)/qm which equals r, so the sum that is supposed to equal r is greater than r, so doesn't in fact equal r.

    Case 2 implies that the sum is equal to:

    [tex]\frac{p^m}{q^m} + \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k[/tex]

    where am is in {0, 1, ..., p-2} and the rest of the ak are in {0, 1, ..., p-1}. So we would get:

    [tex]r = \frac{p^m}{q^m} + \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k[/tex]

    [tex]\frac{1}{q^m} = \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k[/tex]

    Hopefully you can see why this is impossible. If am > 0, then the right side is too big by virtue of p being greater than 1. If am = 0, then we get the right side being:

    [tex]\sum _{k=0} ^{m-1}a_k\left(\frac{p}{q}\right)^k[/tex]

    But this means that you will be able to write the right side in the form z/qm-1 where z is some natural number. So we would get:

    [tex]\frac{1}{q^m} = \frac{z}{q^{m-1}}[/tex]

    [tex]1 = zq[/tex]

    Add the hypothesis that q > 1, and we get a contradiction.

    Finally, in case 3, we get:

    [tex]\frac{p^m + 1}{q^m} = \sum _{k=0} ^{deg(a)} a_k\left (\frac{p}{q}\right )^k[/tex]

    .... I'm not sure where to go with this, or even if I'm proving/disproving the right thing. Keeping in mind the left-side has to be an integer, I don't see an easy way to make the above contradictory.

    Note that if q = 1, then the whole problem is easy, and the answer is yes. It's just a consequence of the division algorithm, and we'd just be writing r in base p. If you consider the ring generated by (p/q) with the normal addition and multiplication, maybe there is generalized division algorithm that would give the desired result.

    Initially, I tried proving that the answer to the question was yes. I tried using the idea of the division algorithm, but then I started thinking that I might have r's that were close to some power of p/q, but off by a small correction term, one that the terms in the sum on the right side couldn't take care of? That's where I got the idea for the r in my above attempt-of-a-proof. But now I'm not sure. The problem in my initial proof (in my attempt to prove the affirmative) is that I was doing what, in the terminology of the "proof" you see above, would amount to taking deg(a)=m, and we already see that won't work. This new proof shows that I would have to take deg(a) < m, and since I've had such a tough time showing that this leads to a contradiction, maybe rather than finding the highest power of (p/q) that divides a given r, and making that your n, I would have to check the specific r. If it is slightly larger than a power of (p/q), then maybe I should make my n one less than that highest power.
  9. Jan 19, 2006 #8
    -\Essentially, we just have to show whether

    [tex]\forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0,[/tex]

    [tex]\exists \left\{ {a_0,a_1,a_2,\ldots,a_n} \right\} \subset \mathbb{Z} \cap \left[ {0,p - 1} \right] [/tex]

    [tex]\text{such that }\,r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k } [/tex]
    Last edited: Jan 19, 2006
  10. Jan 19, 2006 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How big can that sum be? :tongue2:
  11. Jan 19, 2006 #10


    User Avatar
    Science Advisor
    Homework Helper

    Some things to note:

    If the problem has a solution where gcd(p,q) = 1, then it has a solution for any p, q.

    Given gcd(p,q) = 1, two sums are equal iff the coefficients are equal, i.e.

    [tex]\sum _{k=0}^na_k\left(\frac{p}{q}\right)^k = \sum _{k=0}^nb_k\left(\frac{p}{q}\right)^k \Leftrightarrow a_i = b_i[/tex]

    To prove this, we work by induction on n. When n = 0, this is obvious. Assume it holds for n = m. We want to show it holds for n = m+1. Well, we get:

    [tex]\sum _{k=0}^{m+1}a_k\left(\frac{p}{q}\right)^k = \sum _{k=0}^{m+1}b_k\left(\frac{p}{q}\right)^k \Leftrightarrow a_i = b_i[/tex]

    [tex]\sum _{k=1}^{m+1}a_kp^kq^{m+1-k} = \sum _{k=1}^{m+1}b_kp^kq^{m+1-k}[/tex]

    [tex](a_{m+1} - b_{m+1})p^{m+1} = \sum _{k=0} ^m(b_k - a_k)p^kq^{m+1-k}[/tex]

    [tex]p[p^m(a_{m+1} - b_{m+1})] = (b_0 - a_0)q^{m+1} + \sum _{k=1} ^m(b_k - a_k)p^kq^{m+1-k}[/tex]

    [tex]p[p^m(a_{m+1} - b_{m+1})] = (b_0 - a_0)q^{m+1} + p\sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}[/tex]

    From this, we get that p | (b0 - a0), but since the bi and ai are less than p, this means that (b0 - a0) = 0, giving us that the 0th coefficients are the same. Now since this is zero, we are left with:

    [tex]p[p^m(a_{m+1} - b_{m+1})] = p\sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}[/tex]

    [tex]p^m(a_{m+1} - b_{m+1}) = \sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}[/tex]

    [tex]\sum _{k=0} ^ma_{k+1}p^kq^{m-k} = \sum _{k=0} ^ma_{k+1}p^kq^{m-k}[/tex]

    [tex]\sum _{k=0} ^m a_{k+1}\left(\frac{p}{q}\right)^k = \sum _{k=0} ^m b_{k+1}\left(\frac{p}{q}\right)^k[/tex]

    [tex]a_1 = b_1, \dots , a_{m+1} = b_{m+1}[/tex]

    the last line following from the inductive hypothesis.

    We can also look at the problem as that of finding, given coprime p and q, and then given r, some natural n and some ai in {0, 1, ..., p-1} such that

    rqn = a0qn + ... + akpkqn-k + ... + anpn

    Now it's clear from this that q | an.

    Also note that for all r, there is some M such that for all m > M, we get:

    rqm < pm

    So given an r, there are only so many values for n that could possibly work.

    Now I'm not exactly sure how to formulate it, but I was thinking that we could use the pigeonhole principle in some way. We can note that if we have a sum going up to n, then the highest number we can make is:

    [tex]\sum _{k=0}^n (p-1)p^kq^{n-k}[/tex]

    The number of multiples of qn that are less than or equal to this number is

    [tex]fl\left (\frac{(p-1)\sum_{k=0}^np^kq^{n-k}}{q^n}\right ) = fl\left ((p-1)\sum _{k=0}^n\left (\frac{p}{q}\right)^k\right)[/tex]

    where fl is the floor function. On the other hand, the number of distinct sums we can make that go up to n, where in particular q | an is:

    [tex]fl\left (\frac{p}{q}\right )p^n[/tex]

    Well for now, this is just a collection of facts which maybe can be put together in some useful way, but I can't think of how to do so exactly right now.
    Last edited: Jan 19, 2006
  12. Jan 21, 2006 #11
    Using the sequence (and my TI-89)
    [tex]A_n = \sum\limits_{k = 0}^n {\left( {\left\lfloor {\frac{n}{{p^k }}} \right\rfloor - p\left\lfloor {\frac{n}{{p^{k + 1} }}} \right\rfloor } \right)\left( {\frac{p}{q}} \right)^k } [/tex]

    I tried to derive the relationship between [itex]n[/itex] and [itex]r[/itex]. In other words, calculate the value of [itex]n[/itex] given any [itex] r = A_n[/itex] (much like finding the inverse of a function or sequence...at least for the natural values of An).

    As it turns out, An is not everywhere increasing, although an interesting & noticeable pattern is generated upon inspection. If someone can provide me with a download/link where I can plot sequences, I can attach the image here, of this sequence.

    Not quite, though. There are sequences of [itex]\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \mathbb{Z} \cap \left[ {0,p - 1} \right][/itex] for which
    [tex]\sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k } [/tex]
    is not an integer.

    You see, [itex]\forall n \in \mathbb{N}[/itex], there are
    different sequences possible.

    Of course,
    For all sequences [itex]\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}[/itex] (that satisfy the conditions), the largest sum possible is
    [tex]\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}
    {q}} \right)^k } [/tex]
    which corresponds to a sequence where every term is [itex]p-1[/itex].
    -And also, the largest possible integer--that [itex]\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}[/itex] can correspond to--is thus:
    [tex]\left\lfloor {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}
    {q}} \right)^k } } \right\rfloor [/tex]
    [tex]\forall q > 1, \; p^{n + 1} > 1 + {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}{q}} \right)^k } } [/tex]

    There will be a greater quantity of sequences possible (that satisfy the conditions) than is needed to express all the integers from zero to
    [tex]\left\lfloor {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}{q}} \right)^k } } \right\rfloor[/tex]

    (Needless to say, the extraneous non-integer-representing sequences will represent non-integral rational numbers)

    Well, the sum can be any natural number. And as the
    Frivolous Theorem of Arithmetic states :biggrin:,

    "Almost all natural numbers are very, very, very large." :smile:
    Last edited: Jan 22, 2006
  13. Jan 27, 2006 #12

    [tex]\forall p,q,r \in \mathbb{N}{\text{ where }}p > q > 0,\;{\text{does}}[/tex]

    [tex]\exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \left\{ {0,1, \ldots ,p - 1} \right\}[/tex]

    [tex]{\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}
    {q}} \right)^k } \;?[/tex]

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook