Monday Mathematics: Power Play
Sep. 24th, 2012 08:09 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowI give up; I'm not going to be able to say anything more about my polygons research without going into a horrendous amount of detail. Sorry about that, the one or two of you who were waiting for more....
Instead of that, I'm going to talk about a nice little tidbit that I learned from Dr. Chung-wu Ho, who was then the Chair of the department. (He retired and moved west years ago.) Here it is. Let A and B be two positive whole numbers, and assume that A is not a power of 10. Then there is some power of A whose decimal representation begins with the digits of B. For example, suppose A is 5 and B is 7. The successive powers of 5 are 5, 25, 125, 625, 3125, 15625, 78125, and there we are: 57 begins with 7. But the same thing would work with A=13 and B=215, or any other pair, so long as A is not a power of 10. Unfortunately, the proof doesn't give any information about what power will do the trick; it may be very very large. The proof - which really isn't that hard, if you've had enough math to understand the concept of greatest lower bound - is under the cut.
First, let's talk about base-10 logarithms. The logarithm of a number N has an integer part, the characteristic, and a fractional part, the mantissa. The characteristic really just describes how large the number is; if a number lies between 10 and 99, the characteristic of its logarithm is 1, while it's 2 for a number between 100 and 999, 3 between 1000 and 9999, and so on up. It's the mantissa which is important for this problem; it gives the initial digits of N. If the first digit of N is, say, 4, then the mantissa of its logarithm will lie between log 4 and log 5; if the first digits are 732, then the mantissa will lie between log 7.32 and log 7.33, and so on. So, here's the first key point: the numbers N which begin with the digits of B are those whose logarithms have mantissas lying in some small interval I.
Next: the logarithms of the powers of A are simply the multiples of log A, which we'll call x for convenience. So, the claim is that some multiple of x has fractional part lying in the interval I; or, to put it another way, that there are positive integers m and n so that m x - n lies in I. If the length of I is y, it's enough to show that some number z of the form m x - n is positive and less than y - because then the multiples of z show up at least every y units along the line, and there's got to be one in I. (One important thing: x has to be irrational, because A isn't a power of 10.)
All right. Now, let S be the set of all positive numbers of the form m x - n, with m and n positive integers, and let t be the greatest lower bound of S. I claim that t must be 0. Suppose not; then t is positive. There's some positive integer M such that t is less than 1/(M-1) and at least equal to 1/M. Because t is the greatest lower bound of S, we can pick a member of S - call it u - which is just a tiny bit larger than t. If u is close enough to t, M u is larger than 1, but (M-1) u is less than 1; that means that M u - 1 is positive, but less than u. If you're careful about things, you can force M u - 1 to be less than t - but M u - 1 is in S, which is a contradiction! Therefore t must be 0, and there's a number z in S which is less than y - which is what we wanted, and which proves the claim.
The neat thing about this proof is that the claim is one about whole numbers, but the proof is essentially topological (or at least analytic). When Chung-wu showed it to me, I just whistled and said, "That is slick!"
(The bit about being "careful about things" requires what Paul Halmos called "epsilontics"; if you took calculus and your teacher gave you careful proofs that, e.g., the function x2 is continuous, the proofs involved epsilontics. Epsilontics is never enlightening, so I'm not going through those details here.)
Instead of that, I'm going to talk about a nice little tidbit that I learned from Dr. Chung-wu Ho, who was then the Chair of the department. (He retired and moved west years ago.) Here it is. Let A and B be two positive whole numbers, and assume that A is not a power of 10. Then there is some power of A whose decimal representation begins with the digits of B. For example, suppose A is 5 and B is 7. The successive powers of 5 are 5, 25, 125, 625, 3125, 15625, 78125, and there we are: 57 begins with 7. But the same thing would work with A=13 and B=215, or any other pair, so long as A is not a power of 10. Unfortunately, the proof doesn't give any information about what power will do the trick; it may be very very large. The proof - which really isn't that hard, if you've had enough math to understand the concept of greatest lower bound - is under the cut.
First, let's talk about base-10 logarithms. The logarithm of a number N has an integer part, the characteristic, and a fractional part, the mantissa. The characteristic really just describes how large the number is; if a number lies between 10 and 99, the characteristic of its logarithm is 1, while it's 2 for a number between 100 and 999, 3 between 1000 and 9999, and so on up. It's the mantissa which is important for this problem; it gives the initial digits of N. If the first digit of N is, say, 4, then the mantissa of its logarithm will lie between log 4 and log 5; if the first digits are 732, then the mantissa will lie between log 7.32 and log 7.33, and so on. So, here's the first key point: the numbers N which begin with the digits of B are those whose logarithms have mantissas lying in some small interval I.
Next: the logarithms of the powers of A are simply the multiples of log A, which we'll call x for convenience. So, the claim is that some multiple of x has fractional part lying in the interval I; or, to put it another way, that there are positive integers m and n so that m x - n lies in I. If the length of I is y, it's enough to show that some number z of the form m x - n is positive and less than y - because then the multiples of z show up at least every y units along the line, and there's got to be one in I. (One important thing: x has to be irrational, because A isn't a power of 10.)
All right. Now, let S be the set of all positive numbers of the form m x - n, with m and n positive integers, and let t be the greatest lower bound of S. I claim that t must be 0. Suppose not; then t is positive. There's some positive integer M such that t is less than 1/(M-1) and at least equal to 1/M. Because t is the greatest lower bound of S, we can pick a member of S - call it u - which is just a tiny bit larger than t. If u is close enough to t, M u is larger than 1, but (M-1) u is less than 1; that means that M u - 1 is positive, but less than u. If you're careful about things, you can force M u - 1 to be less than t - but M u - 1 is in S, which is a contradiction! Therefore t must be 0, and there's a number z in S which is less than y - which is what we wanted, and which proves the claim.
The neat thing about this proof is that the claim is one about whole numbers, but the proof is essentially topological (or at least analytic). When Chung-wu showed it to me, I just whistled and said, "That is slick!"
(The bit about being "careful about things" requires what Paul Halmos called "epsilontics"; if you took calculus and your teacher gave you careful proofs that, e.g., the function x2 is continuous, the proofs involved epsilontics. Epsilontics is never enlightening, so I'm not going through those details here.)
