1. Not finding help here? Sign up for a free 30min 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!

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
    Staff Emeritus
    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]

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Quick questions~
  1. Quick Question (Replies: 4)

  2. Quick logic question (Replies: 3)

  3. Quick Matrix Question (Replies: 1)