Proof of recursive formula for "fusible numbers"

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

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

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

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