## anonymous one year ago Can anyone explain George E. Andrews proof of Basis Representation Theorem?

1. anonymous

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

2. anonymous

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

3. anonymous

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

4. anonymous
5. anonymous

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

6. anonymous

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

7. anonymous

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?

8. anonymous

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

9. anonymous

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}$$)

10. anonymous

i'm still not getting it :/

11. anonymous

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

12. anonymous

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)$$

13. anonymous

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

14. anonymous

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

15. anonymous

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?

16. anonymous

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$$)

17. ganeshie8

this uniqueness part looks unnecessarily complicated

18. anonymous

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

19. anonymous

pigeonhole principle

20. anonymous

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

21. anonymous

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?

22. anonymous

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

23. ganeshie8

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

24. anonymous

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?

25. anonymous

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$$)

26. anonymous

and yes @sourwing, we have that $$b_k$$ is decreasing on the natural numbers

27. anonymous

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

28. anonymous

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

29. anonymous

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

30. anonymous

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

31. anonymous

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

32. anonymous

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

33. anonymous

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

34. Empty

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.

35. anonymous

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

36. Empty

Yeah I know

37. anonymous

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

38. anonymous

by 'works' i mean gives unique representations

39. Empty

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

40. ganeshie8

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

41. anonymous

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

42. anonymous

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

43. ganeshie8

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

44. anonymous

nah, but I think it's trivial anyways

45. anonymous

@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