Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: $Revision: 1.6.2.16 $; site inmet.UUCP Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!cca!inmet!janw From: janw@inmet.UUCP Newsgroups: net.math Subject: Re: Need proof for density problem Message-ID: <5700010@inmet.UUCP> Date: Sun, 29-Sep-85 18:18:00 EDT Article-I.D.: inmet.5700010 Posted: Sun Sep 29 18:18:00 1985 Date-Received: Thu, 3-Oct-85 04:39:06 EDT References: <58@unc.UUCP> Lines: 99 Nf-ID: #R:unc:-5800:inmet:5700010:000:3629 Nf-From: inmet!janw Sep 29 18:18:00 1985 [ Written 12:17 am Sep 23, 1985 by southard@unc in inmet:net.math] > Is the set of numbers of the form 2^m * 3^n (that's 2 to the m power times > 3 to the n power) where m and n are integers, dense in the positive > rational numbers? Your problem was the last thing I read before the hurricane hit. So it gave me something to think about during the blackout. The answer to the problem is *yes*, proof follows: Denote the set of numbers of the form 2^m * 3^n with Z. (1) Obviously, multiplying or dividing two elements of Z produces an element of Z. In particular, 1/x, where x is a number of our type, also belongs to it. (2) Lemma : 1 is a condensation point of Z. In other words, there is a sequence of elements of Z, all different from 1, tending to 1. This lemma is proved below, in (4); for now assume it proved. Then it follows, as a corollary, that there exists a sequence of elements of Z, all *less than 1*, tending to 1. To prove the corollary, take any sequence of the kind whose existence is established by Lemma, and replace each member z of it that is >1 , with 1/z. (3) Using this corollary, we can prove the main proposition. Namely, that for every alpha & beta such that 0 < alpha < beta, there exists a z belonging to Z such that alpha < z < beta. By Lemma and its corollary in (2), there exists an A such that alpha/beta < A < 1 and A belongs to Z. Obviously, there exists an element B of Z such that beta < B. Now consider the sequence b[i] = B * A^i (i = 0, 1, ...). Each member of this sequence belongs to Z. For sufficiently large i, b[i] < beta (since A < 1). Consider the *last* element b[t] such that b[t] >= beta. Then, since A > alpha / beta, alpha < b[t+1] < beta, Q. E. D. (4) Now we have to prove the Lemma stated in (2). Consider two sequences a[i], b[i] (i = 0, 1, ...) defined as follows: a[0] = 2/3 ; b[0] = 4/3 ; for every i, a[i+1] = a[i] * b[i] iff a[i] * b[i] < 1; else a[i+1] = a[i]; similarly, for every i, b[i+1] = a[i] * b[i] iff a[i] * b[i] > 1; else b[i+1] = b[i]; Note : The case a[i] * b[i] = 1 will never arise since all the numerators in a[i], b[i] are powers of 2, while all the denominators are powers of 3. For the same reason no a[i] or b[i] equals 1. Intervals ( a[i] , b[i] ) form a sequence of shrinking intervals straddling 1 : a[i] < 1 < b[i] for all i. a[i] monotonically increase, while b[i] monotonically decrease. It follows that there are limits A <= 1 and B >= 1, to which a[i] and b[i], respectively, tend. Let us prove that at least one of these limits equals 1 (actually, both do). Since all the numbers a[i], b[i] belong to Z, this will prove the lemma. Assume the contrary : A<1 1, or A * B < 1. Assume the former: A*B > 1. But then, for sufficiently large i, say, for i >= t >0, a[i] * b[i] > 1. Therefore, for all i >=t, b[i+1] = a[i] * b[i] < A * b[i]. Thus, for i > t, b[i] < b[t] * A^(i-t), and, since, by hypothesis, A < 1, b[i] tends to 0, which is absurd. For the case A*B < 1, the proof is symmetrical to this: Assume A*B < 1. But then, for sufficiently large i, say, for i >= t >0, a[i] * b[i] < 1. Therefore, for all i >=t, a[i+1] = a[i] * b[i] > a[i] * B. Thus, for i > t, a[i] > a[t] * B^(i-t), and, since, by hypothesis, B > 1, a[i] tends to infinity, which is absurd. The Lemma is proved. Jan Wasilewsky, at Intermetrics, Inc. 733 Concord Ave, Cambridge, MA Brought to you by Super Global Mega Corp .com