A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
Can anyone explain George E. Andrews proof of Basis Representation Theorem?
anonymous
 one year ago
Can anyone explain George E. Andrews proof of Basis Representation Theorem?

This Question is Closed

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0this is what you're talking about? http://puu.sh/iMtN8/0b7006bf62.png

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0i am sure it is in a textbook that is why they cost like $250

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I have the book. I'm having difficulty following the proof

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Well, 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0the next tricky thing they do is use the fact that $$\sum_{j=0}^{t1} k^j=\frac{k^t1}{k1}$$ to rewrite \(k^t1=\sum\limits_{j=0}^{t1}(k1)k^j\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0yeah 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^(s1) + ... + a_(st) k^t < where does this come from?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and why is it written differently from the way it was written in theorem?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0suppose 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 \(st\) digits that matter in our sum (hence we why we don't write \(k^0,k^1,k^2,\dots,k^{s1}\))

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0i'm still not getting it :/

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops, 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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0the important part is just to show that if we have a representation of \(n\), then we can derive a distinct representation of \(n1\), so there are at least as many representations of \(n1\) as there are of \(n\)  in other words, \(b_k(n)\le b_k(n1)\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0now 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0actually, oops, earlier I meant the first \(t\) digits of the \(s\)digitlong expansion of \(n\) in base \(k\) are \(0\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Yeah, I understand the last part of the proof. It's the part where it says b_k (n) <= b_k(n1) that gives me trouble. Why is this inequality true?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0because we showed that every representation of \(n\) gives rise to its own representation of \(n1\), thus it must be that there are at least as many representations of \(n1\) as there are of \(n\) (basically there's an injection from the set of the representations of \(n\) to the set of representations of \(n1\))

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1this uniqueness part looks unnecessarily complicated

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and recall that if \(f:A\to B\) is an injection then \(A\le B\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0pigeonhole principle

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0@ganeshie8 the beauty is that it does existence and uniqueness simultaneously to show that \(b_k(n)=1\) in one swoop !

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0o: oh ok. so by the same argument if there is another representation for n1, we use the same algebra and generate a representation for n2?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0yes! so therefore there must be at least one representation of \(n2\) for every representation of \(n1\), and possibly more

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Oh 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..

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0So 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(m1) <= ... <= b_(n1) <= b_k(n) is saying?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0it's honestly a quite beautiful trick; the part about $$k^t1=\sum_{j=0}^{j1}(k1)k^j$$ is implicitly saying you 'borrow' from the last nonzero digit and then the others become 'nines' (or \(k1\) in base \(k\))

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0and yes @sourwing, we have that \(b_k\) is decreasing on the natural numbers

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ok, here is the stupid question. Why is b_k(1) = 1? XD and also b_k(k^n) = 1

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0because \(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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0though 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0but that's enough for us since we're only using \(b^k(k^p)\) as a lowerbound

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ah yeah because 1 <= b_k(k^n) <=1 thus b_k(k^n) = 1

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops, \(b_k(k^n)\) as a lower bound* and yes exactly, it gets sandwiched between

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Much thanks @oldrin.bataku :') I have a better understanding of the proof now. Thanks. @ganeshie8 thank you for giving replies too :)

Empty
 one year ago
Best ResponseYou've already chosen the best response.0You 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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0that's not really relevant here; he's interested in vanilla base\(k\) representations of positive integers

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0but 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 (n1)\cdot P(n)=P(n+1)1$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0by 'works' i mean gives unique representations

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Sure this is just one instance, we don't have to have the basis following any pattern at all.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1just 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^{s1}+\cdots+a_{st}k^t ~~=~~ a'_0k^s+a'_1k^{s1}+\cdots+a'_{st}k^t \] subtract them and get \[0=(a_0a'_0)k^s+(a_1a'_1)k^{s1}+\cdots+(a_{st}a'{st})k^t\] divide \(k^t\) through out and argue that \(k\mid (a_{st}a'_{st})\) is impossible

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops, i messed up that recurrence, but hopefully you know what i'm talking about; it's an elementary result in mixedradix positional number systems

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0i think there are some conditions you need to prove as well to ensure that's enough @ganeshie8

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1like \(a_0,~~a'_0\ne 0\) and \(a_{st},~~a'_{st}\ne 0\) ?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0nah, but I think it's trivial anyways

anonymous
 one year ago
Best ResponseYou've already chosen the best response.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
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.