A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Can anyone explain George E. Andrews proof of Basis Representation Theorem?

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this is what you're talking about? http://puu.sh/iMtN8/0b7006bf62.png

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i am sure it is in a textbook that is why they cost like $250

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I have the book. I'm having difficulty following the proof

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, it's done in a relatively unorthodox way. The idea is to tackle existence and uniqueness of a representation at the same time by defining \(b_k(n)\) to denote the # of representations of \(n\) in base \(k\) and then arguing \(b_k(n)=1\) for all integers \(n>0,k>1\)

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the next tricky thing they do is use the fact that $$\sum_{j=0}^{t-1} k^j=\frac{k^t-1}{k-1}$$ to rewrite \(k^t-1=\sum\limits_{j=0}^{t-1}(k-1)k^j\)

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah I understand the general idea. Ok, let's just go through line by line (well not completely). I already posted the link so here it goes: He said let b_k(n) be the number of representation for n. And we need to show that b_k(n) = 1. Ok Then he say some of the coefficient can be zero, thus, can be omitted. But then n = a_0 k^s + a_1 k^(s-1) + ... + a_(s-t) k^t <--- where does this come from?

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and why is it written differently from the way it was written in theorem?

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    suppose we can represent \(n\) as a \(t\)-digit expansion in base \(k\); they're saying if the first \(s\) of the \(t\) digits of our representation then we're only looking at the \(s-t\) digits that matter in our sum (hence we why we don't write \(k^0,k^1,k^2,\dots,k^{s-1}\))

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'm still not getting it :/

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops, if the first \(s\) digits of our \(t\)-digit representation of \(n\) in base \(k\) are all zeros then we can forget them; to be honest this part isn't necessary

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the important part is just to show that if we have a representation of \(n\), then we can derive a distinct representation of \(n-1\), so there are at least as many representations of \(n-1\) as there are of \(n\) -- in other words, \(b_k(n)\le b_k(n-1)\)

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    now we know that powers of \(k\) have only one representation trivially so we can use that inequality to bound \(b_k(n)\) between \(k^0=1\) and \(k^n\) which is guaranteed bigger than \(n\) since \(k>1\). we find: $$k^n>n>1\implies b_k(k^n)\le b_k(n)\le b_k(1)\implies b_k(n)=1$$ since \(b_k(k^n)=b_k(1)=1\)

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    actually, oops, earlier I meant the first \(t\) digits of the \(s\)-digit-long expansion of \(n\) in base \(k\) are \(0\)

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, I understand the last part of the proof. It's the part where it says b_k (n) <= b_k(n-1) that gives me trouble. Why is this inequality true?

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    because we showed that every representation of \(n\) gives rise to its own representation of \(n-1\), thus it must be that there are at least as many representations of \(n-1\) as there are of \(n\) (basically there's an injection from the set of the representations of \(n\) to the set of representations of \(n-1\))

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    this uniqueness part looks unnecessarily complicated

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and recall that if \(f:A\to B\) is an injection then \(|A|\le |B|\)

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    pigeonhole principle

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 the beauty is that it does existence and uniqueness simultaneously to show that \(b_k(n)=1\) in one swoop !

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    o: oh ok. so by the same argument if there is another representation for n-1, we use the same algebra and generate a representation for n-2?

  21. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes! so therefore there must be at least one representation of \(n-2\) for every representation of \(n-1\), and possibly more

  22. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh yeah, I'm coming from euclid division algorithm and divisibility argument thats somewhat easier to follow for me... honestly i still don't get the George E. Andrews's proof, still going thru..

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So the conclusion is that a smaller natural less than or equal to the number of representation of a bigger natural number? Isn't that what the statement b_k(m) <= b_k(m-1) <= ... <= b_(n-1) <= b_k(n) is saying?

  24. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it's honestly a quite beautiful trick; the part about $$k^t-1=\sum_{j=0}^{j-1}(k-1)k^j$$ is implicitly saying you 'borrow' from the last non-zero digit and then the others become 'nines' (or \(k-1\) in base \(k\))

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and yes @sourwing, we have that \(b_k\) is decreasing on the natural numbers

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, here is the stupid question. Why is b_k(1) = 1? XD and also b_k(k^n) = 1

  27. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    because \(1=1_k\) is the same in every base \(k\) (since \(k^0=1\)) and any other digits would trivially result in something too big to be \(1\)

  28. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    though to be fair they don't actually argue that \(b_k(k^p)=1\), they just argue that \(b_k(k^p)\ge 1\) since it permits at least one obvious representation -- the digit \(1\) followed by \(p\) zeros :) just like \(10^3=1000\)

  29. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but that's enough for us since we're only using \(b^k(k^p)\) as a lower-bound

  30. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ah yeah because 1 <= b_k(k^n) <=1 thus b_k(k^n) = 1

  31. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops, \(b_k(k^n)\) as a lower bound* and yes exactly, it gets sandwiched between

  32. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Much thanks @oldrin.bataku :') I have a better understanding of the proof now. Thanks. @ganeshie8 thank you for giving replies too :)

  33. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    You can don't even need to use powers of a number, you just need to multiply by any number greater than 2 to get he next place and one less than that is what you can hold. For instance a "factorial base" gives us a nice result such as: \[4! - 1 = 3*3!+2*2!+1*1!\] Which corresponds to a unique representation in the factorial base: \[1000_f - 1_f = 321_f\] Something fun to play with.

  34. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that's not really relevant here; he's interested in vanilla base-\(k\) representations of positive integers

  35. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah I know

  36. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but I will say the reason that the factorial number system works is that the next 'place'-value \(P(n)\) satisfies a recurrence $$\sum_{n=0}^n (n-1)\cdot P(n)=P(n+1)-1$$

  37. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    by 'works' i mean gives unique representations

  38. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sure this is just one instance, we don't have to have the basis following any pattern at all.

  39. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    just so you know why i felt it was complicated earlier... below argument looks simple enough for me let the two representations be \[n=a_0k^s+a_1k^{s-1}+\cdots+a_{s-t}k^t ~~=~~ a'_0k^s+a'_1k^{s-1}+\cdots+a'_{s-t}k^t \] subtract them and get \[0=(a_0-a'_0)k^s+(a_1-a'_1)k^{s-1}+\cdots+(a_{s-t}-a'{s-t})k^t\] divide \(k^t\) through out and argue that \(k\mid (a_{s-t}-a'_{s-t})\) is impossible

  40. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops, i messed up that recurrence, but hopefully you know what i'm talking about; it's an elementary result in mixed-radix positional number systems

  41. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i think there are some conditions you need to prove as well to ensure that's enough @ganeshie8

  42. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    like \(a_0,~~a'_0\ne 0\) and \(a_{s-t},~~a'_{s-t}\ne 0\) ?

  43. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    nah, but I think it's trivial anyways

  44. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 I hope Euclid Division proof is easier as you said earlier. I'm generally scared to read proofs on my own XD. But that's ok. Shooting dead ducks through airplane's engine seems like a fun way to test an newly manufactured plane. (nah i'm just being random right now XD) Thanks everyone! bye

  45. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.