Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The set of fusible numbers is a fantastic set of rational numbers defined by a simple rule. The story is well told here but I'll repeat the definitions. It's the formula on slide 17 that I'm trying to understand.

Define $\displaystyle a \oplus b = \frac{a+b+1}{2}$. A number is fusible if it is $0$ or if it can be written as $a \oplus b$ where $a, b$ are fusible and $|a-b|<1$. Let $F$ be the set of fusible numbers. More formally, $F$ is the intersection of all sets of real numbers that are closed under $\oplus$ applied to arguments at a distance at most 1.

The set $F$ is a well-ordered set of non-negative rational numbers. The proof that it's well-ordered isn't included in the PDF file I linked to, but it's not hard to show this. (It wouldn't be true if we hadn't insisted on the condition $|a-b|<1$, by the way.)

Amazingly, the order type of $F$ is $\varepsilon_0$. It's also true that $F$ is closed under ordinary addition; this isn't hard to prove either but I don't know if it plays a part in what follows.

Because $F$ is well-ordered, we may define $f(x)$ to be the least fusible number greater than $x$, for any real $x$. Further, set $m(x) = f(x)-x$. We obviously have $m(x) = -x$ for $x<0$, while for $x \geq 0$, it is posited that $$m(x) = \frac{1}{2}m(x-m(x-1))$$ The question is: why is this last formula true?

I'm able to show one of the necessary inequalities, namely that $\displaystyle m(x) \leq \frac{1}{2}m(x-m(x-1))$:
Given $x$, observe that $$(x-1+t) \oplus (x-t+u) = x + u/2$$ Take $t = m(x-1)$, which guarantees that ($x-1+t$) is indeed fusible. Now set $u = m(x-t)$ which makes ($x-t+u$) fusible as well, and the distance between those two fusible numbers can't be greater than $1$. It follows that ($x+u/2$) is fusible, and so $m(x)$ is at most $u/2$ for that particular $u$, which is indeed $m(x-m(x-1))$.

The question, then, is:

How can we prove that no other choice of $t$ yields an even smaller value for $m(x)$?

It's not hard to show that there's no loss of generality in focusing on $x-1+t$ and $x-t+m(x-t)$, but greedily minimizing $t$ by setting $t=m(x-1)$ is not in any obvious way guaranteed to yield the minimum value for $m(x)$, as far as I can see.

What am I missing?

share|improve this question
    
Intuitively, the fusible numbers get very much denser as you go up. As you need two fusible numbers that sum to greater than $2x-1$ and want the smallest excess over that, you should take one ($x-1+t$)as small as possible. That way the other (which has the excess over $x-t$) is as close to the minimum as possible. I haven't figured out how to formalize this, either. –  Ross Millikan May 21 '11 at 4:38
    
Thing is, they don't get (monotonically) denser as you go up. There are critical points where the density drops sharply - for instance, $1-2^{-n}$ is fusible for all $n$, as is 1, but then nothing until 9/8. That's how the order type gets so wild! –  Alon Amit May 21 '11 at 4:52
    
@Alon Amit: you are right. That's why I don't have a proof. But if you think about finding $m(2+\epsilon)$ you can either take 9/8 and the next after $2-1/8+2\epsilon$ or $2-3/16+2\epsilon$ and you would rather have the first. –  Ross Millikan May 21 '11 at 5:03
    
@Alon: perhaps just a quibble, or I'm missing something. In your proof/outline of "one of the necessary inequalities", you use $leq$, and argue that "...the distance between those two fusible numbers can't be greater than 1." Correct me if I'm wrong, but in your definition of a fusible number, you require that it is $0$, or else can be written as "$a \oplus b$, where $a$ and $b$ are fusible numbers and $|a-b| < 1$". So, I take it, the distance must be *strictly" less than 1. Does that entail a change to the inequality you state to "strictly less than"? etc. –  amWhy May 23 '11 at 2:01
    
@Amy J.M., It doesn't matter at all since $a \oplus (a+1) = a+1$. You get nothing new if you allow the two arguments to be exactly 1 apart, so you might as well allow it. Regardless, sorry for any confusion I caused. –  Alon Amit May 23 '11 at 4:25

2 Answers 2

up vote 15 down vote accepted
+200

That formula is wrong -- see here (linked to from here). That note also contains other interesting thoughts about the fusible numbers, including a new conjecture that would also imply that the order type of $F$ is $\epsilon_0$.

Here's some Java code I wrote to explore these numbers. You can place a red line somewhere by shift-clicking there, and then by clicking or dragging (without Shift) you can move a pair of green lines such that $a\oplus b = c$, where $a$ and $b$ are the numbers corresponding to the green lines and $c$ is the number corresponding to the red line. I used this to find for instance that 101/64 can be generated in three different ways: $101/64=3/4\oplus45/32=15/16\oplus39/32=31/32\oplus19/16$.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionAdapter;
import java.awt.event.MouseMotionListener;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class FusibleNumbers {
    static class BinaryNumber {
        long mantissa;
        int exponent;

        public BinaryNumber (long mantissa,int exponent) {
            this.mantissa = mantissa;
            this.exponent = exponent;

            normalize ();
        }

        public void normalize () {
            if (mantissa == 0)
                exponent = 0;
            else
                while ((mantissa & 1) == 0) {
                    mantissa >>= 1;
                    exponent--;
                }
        }

        public double toDouble () {
            return mantissa / (double) (1L << exponent);
        }

        public String toString () {
            return mantissa + "/2^" + exponent;
        }
    }

    static BinaryNumber getMargin (BinaryNumber x) {
        if (x.mantissa < 0)
            return new BinaryNumber (-x.mantissa,x.exponent);
        BinaryNumber m = getMargin (new BinaryNumber (x.mantissa - (1L << x.exponent),x.exponent));
        int newExponent = Math.max (x.exponent,m.exponent);
        m = getMargin (new BinaryNumber ((x.mantissa << (newExponent - x.exponent)) - (m.mantissa << (newExponent - m.exponent)),newExponent));
        m.exponent++;
        m.normalize ();
        if (m.exponent > 50)
            throw new Error ("exponent overflow");
        return m;
    }

    static int xmin;
    static int xother;

    public static void main (String [] args) {
        JFrame frame = new JFrame ();

        final JPanel panel = new JPanel () {
            public void paintComponent (Graphics g) {
                super.paintComponent (g);
                int exponent = 9;
                int scale = 1 << exponent;
                Dimension size = getSize ();
                for (int i = 0;i < size.width;i++) {
                    BinaryNumber b = new BinaryNumber (i,exponent);
                    BinaryNumber m = getMargin (b);
                    double d = b.toDouble () + m.toDouble ();
                    int x = (int) (d * scale + .5);
                    g.drawLine (x,0,x,size.height);
                }
                drawLine (g,size,xmin,Color.RED);
                drawLine (g,size,xother,Color.GREEN);
                drawLine (g,size,2*xmin - scale - xother,Color.GREEN);
            }

            private void drawLine (Graphics g,Dimension size,int x,Color color) {
                g.setColor (color);
                g.drawLine (x,0,x,size.height);
            }
        };

        panel.addMouseListener (new MouseAdapter () {
            boolean ctrl;

            MouseMotionListener motionListener = new MouseMotionAdapter () {
                public void mouseDragged (MouseEvent me) {
                    update (me);
                }
            };

            public void mouseReleased (MouseEvent me) {
                update (me);
                panel.removeMouseMotionListener (motionListener);
            }

            public void mousePressed (MouseEvent me) {
                ctrl = (me.getModifiers () & MouseEvent.SHIFT_MASK) != 0;
                panel.addMouseMotionListener (motionListener);
                update (me);
            }

            void update (MouseEvent me) {
                if (ctrl)
                    xmin = me.getX ();
                else
                    xother = me.getX ();
                panel.repaint ();
            }
        });

        frame.getContentPane ().add (panel);
        frame.setBounds (0,0,1200,200);
        frame.setVisible (true);
    }
}
share|improve this answer
    
There are a couple typos (maybe made because of the save to Google docs) in the linked note. The 1/211 and 1/212 should be 1/2^11 and 1/2^12 respectively. Still very interesting –  Ross Millikan May 23 '11 at 13:05
    
This is incredible. I thought this might be the case but failed to find a counterexample by hand. Good reminder that a beautiful formula known to hold for small numbers isn't necessarily true. I'm checking some of these claims and will award the bounty right after. –  Alon Amit May 23 '11 at 14:04
    
apparently I can only award the bounty in 9 hours. It's coming :-) –  Alon Amit May 23 '11 at 14:28
    
@Alon: No hurry :-) I didn't really do all that much for it -- ideally, Junyan Xu should get it... –  joriki May 23 '11 at 14:39
    
I don't know that he's around :-) but thanks so much for the awesome find. I would have spent who knows how much more time trying to figure this out before switching my efforts to seriously looking for counterexamples. math.SE works! –  Alon Amit May 23 '11 at 19:25

I have expanded my note into a paper, available here. A Mathematica library of useful functions for exploring fusible numbers is available here, but I haven't written up a documentation for it. Hopefully you can figure out what the functions do. Have fun!

Just briefly mention a fact: $-\log_2\ m(3)$ is actually larger than $2\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow16$, following Knuth's up-arrow notation.

In fact the above should be a comment, but I don't have enough reputation here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.