Proof of recursive formula for "fusible numbers"

Question

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?

Answer 1

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

Answer 2

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.

Update: the Mathematica files and the PDF file mentioned in the comments below are now also available at https://github.com/alreadydone/fusible where I collect all resources about fusible numbers that I can find.

Answer 3

It may be worth noting that a new paper on Fusible Numbers 'snuck onto' the arXiv earlier this year; it proves the order type $\epsilon_0$ and shows (unsurprisingly, given that) unprovability in PA of the statement 'there exists a next fusible number after $n$ for any $n\in\mathbb{N}$'. It doesn't entirely solve the minimal-gap question but establishes some new bounds, as well. The paper is "Fusible numbers and Peano Arithmetic" from Jeff Erickson, Gabriel Nivasch, and Junyan Xu, at https://arxiv.org/abs/2003.14342 .