32
$\begingroup$

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?

  • 0
    @Amy, thanks, I was never sure about this one :-)2011-05-23

2 Answers 2

17

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);     } } 
  • 0
    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!2011-05-23
9

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.

  • 1
    updated links: https://www.dropbox.com/s/g746gl8fl4sly2o/computation.pdf?dl=0 https://www.dropbox.com/s/8pxy85lmnmdrmix/computations.nb?dl=02017-07-31