# Proof of recursive formula for “fusible numbers”

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?

-
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

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.MouseEvent;
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);
}
};

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;
update (me);
}

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

frame.setBounds (0,0,1200,200);
frame.setVisible (true);
}
}

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

-