[math-fun] Moore-Schulman base-3/2 conjecture
1. Fractional bases (Cris Moore) From: Cris Moore <moore@santafe.edu> If we're talking about fractional bases, allow me to introduce you to a conjecture of Leonard J. Schulman and me:
Consider writing zero in base 3/2. That is, for i=0,1,2... let a_i be an integer, and let
0 = \sum_{i=0}^\infty a_i (2/3)^i .
Furthermore, assume that a_i is in {+1,0,-1} for each i, and that a_0 = 1. Thus the first term is 1, and the remaining terms need to cancel it out.
Conjecture: all initial subsequences have a nonzero density of nonzero coefficients. That is, there is a constant C > 0 such that, for every n, at least Cn of the coefficients a_1, a_2, ... a_n are nonzero.
I am equally interested in any nearby conjecture: e.g. replace 3 with 5 or 7, let a_i belong to {-2,-1,0,1,2}, and so on.
If you can prove this, it will have nice consequences for a construction in computer science called tree codes: see http://arxiv.org/abs/1308.6007
- Cris
--That's an interesting conjecture! Seems like P-adics ought to be of some use: http://en.wikipedia.org/wiki/P-adic_number but I don't know anything about them and have not tried. Also, you were asking for the sum to equal 0. However, if it must equal x, then it seems to me it is easy to then prove your conjecture for almost all x, simply based on a volume argument. That is, the percentage of reals in any nonzero width interval, which are representable in base (3/2) using below any positive constant fraction of nonzero digits in {-1, 0, +1}, obviously is zero, so almost all x require at least a constant fraction of nonzero digits, to get represented. Indeed, let's do an entropy calculation. Let the fraction of nonzero digits be F. Then entropy per digit in nats then is E = (F-1)*ln(1-F) - F*ln(F/2). In order to represent a positive fraction of reals, we must have exp(E) >= 3/2. I find that F > 0.1038573417. So now the Moore-Schulman conjecture is proven... except not for x=0, just for "almost all x." Now let us consider the "special x" which ARE representable using less than, say, 1%, of the digits nonzero. We can prove properties these special x must have. For example, we can easily show that any special x must have an infinite number of rational approximations p/q, where q is a power of 3, such that |x-p/q| < q^(-1.01). (Which yet again proves these x have measure zero.) The set of special x is closed under multiplication by (2/3).
Hi Warren. Yes, we had noticed the "almost all x" argument. But we really need it to work for some explicit real, such as zero... Cris On Oct 14, 2013, at 10:20 AM, Warren D Smith <warren.wds@gmail.com> wrote:
1. Fractional bases (Cris Moore) From: Cris Moore <moore@santafe.edu> If we're talking about fractional bases, allow me to introduce you to a conjecture of Leonard J. Schulman and me:
Consider writing zero in base 3/2. That is, for i=0,1,2... let a_i be an integer, and let
0 = \sum_{i=0}^\infty a_i (2/3)^i .
Furthermore, assume that a_i is in {+1,0,-1} for each i, and that a_0 = 1. Thus the first term is 1, and the remaining terms need to cancel it out.
Conjecture: all initial subsequences have a nonzero density of nonzero coefficients. That is, there is a constant C > 0 such that, for every n, at least Cn of the coefficients a_1, a_2, ... a_n are nonzero.
I am equally interested in any nearby conjecture: e.g. replace 3 with 5 or 7, let a_i belong to {-2,-1,0,1,2}, and so on.
If you can prove this, it will have nice consequences for a construction in computer science called tree codes: see http://arxiv.org/abs/1308.6007
- Cris
--That's an interesting conjecture! Seems like P-adics ought to be of some use:
http://en.wikipedia.org/wiki/P-adic_number
but I don't know anything about them and have not tried.
Also, you were asking for the sum to equal 0. However, if it must equal x, then it seems to me it is easy to then prove your conjecture for almost all x, simply based on a volume argument. That is, the percentage of reals in any nonzero width interval, which are representable in base (3/2) using below any positive constant fraction of nonzero digits in {-1, 0, +1}, obviously is zero, so almost all x require at least a constant fraction of nonzero digits, to get represented.
Indeed, let's do an entropy calculation. Let the fraction of nonzero digits be F. Then entropy per digit in nats then is E = (F-1)*ln(1-F) - F*ln(F/2). In order to represent a positive fraction of reals, we must have exp(E) >= 3/2. I find that F > 0.1038573417.
So now the Moore-Schulman conjecture is proven... except not for x=0, just for "almost all x."
Now let us consider the "special x" which ARE representable using less than, say, 1%, of the digits nonzero. We can prove properties these special x must have. For example, we can easily show that any special x must have an infinite number of rational approximations p/q, where q is a power of 3, such that |x-p/q| < q^(-1.01). (Which yet again proves these x have measure zero.)
The set of special x is closed under multiplication by (2/3).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun- bounces@mailman.xmission.com] On Behalf Of Cris Moore Sent: Monday, October 14, 2013 1:48 PM To: math-fun Subject: Re: [math-fun] Moore-Schulman base-3/2 conjecture
Hi Warren. Yes, we had noticed the "almost all x" argument. But we really need it to work for some explicit real, such as zero...
Cris
On Oct 14, 2013, at 10:20 AM, Warren D Smith <warren.wds@gmail.com> wrote:
1. Fractional bases (Cris Moore) From: Cris Moore <moore@santafe.edu> If we're talking about fractional bases, allow me to introduce you to a conjecture of Leonard J. Schulman and me:
Consider writing zero in base 3/2. That is, for i=0,1,2... let a_i be an integer, and let
0 = \sum_{i=0}^\infty a_i (2/3)^i .
Furthermore, assume that a_i is in {+1,0,-1} for each i, and that a_0 =
Probably only tenuously related, but in the base 3/2 of A024629, I found 13*3^15 = 210110020200000010101001200022000000000000000 which has 32 zeroes out of 45 digits. In this case, I would conjecture the other way that you can get as high a proportion < 1 of zeroes as you like. But the Moore-Schulman conjecture concerns balanced base 3/2, for which I have little intuition. 1.
Thus the first term is 1, and the remaining terms need to cancel it out.
Conjecture: all initial subsequences have a nonzero density of nonzero coefficients. That is, there is a constant C > 0 such that, for every n, at least Cn of the coefficients a_1, a_2, ... a_n are nonzero.
I am equally interested in any nearby conjecture: e.g. replace 3 with 5 or 7, let a_i belong to {-2,-1,0,1,2}, and so on.
If you can prove this, it will have nice consequences for a construction in computer science called tree codes: see http://arxiv.org/abs/1308.6007
- Cris
--That's an interesting conjecture! Seems like P-adics ought to be of some use:
http://en.wikipedia.org/wiki/P-adic_number
but I don't know anything about them and have not tried.
Also, you were asking for the sum to equal 0. However, if it must equal x, then it seems to me it is easy to then prove your conjecture for almost all x, simply based on a volume argument. That is, the percentage of reals in any nonzero width interval, which are representable in base (3/2) using below any positive constant fraction of nonzero digits in {-1, 0, +1}, obviously is zero, so almost all x require at least a constant fraction of nonzero digits, to get represented.
Indeed, let's do an entropy calculation. Let the fraction of nonzero digits be F. Then entropy per digit in nats then is E = (F-1)*ln(1-F) - F*ln(F/2). In order to represent a positive fraction of reals, we must have exp(E) >= 3/2. I find that F > 0.1038573417.
So now the Moore-Schulman conjecture is proven... except not for x=0, just for "almost all x."
Now let us consider the "special x" which ARE representable using less than, say, 1%, of the digits nonzero. We can prove properties these special x must have. For example, we can easily show that any special x must have an infinite number of rational approximations p/q, where q is a power of 3, such that |x-p/q| < q^(-1.01). (Which yet again proves these x have measure zero.)
The set of special x is closed under multiplication by (2/3).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute
The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Cris Moore -
David Wilson -
Warren D Smith