35
$\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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ May 21, 2011 at 4:38
  • $\begingroup$ 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! $\endgroup$
    – Alon Amit
    May 21, 2011 at 4:52
  • $\begingroup$ @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. $\endgroup$ May 21, 2011 at 5:03
  • $\begingroup$ @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. $\endgroup$
    – amWhy
    May 23, 2011 at 2:01
  • $\begingroup$ @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. $\endgroup$
    – Alon Amit
    May 23, 2011 at 4:25

3 Answers 3

19
+200
$\begingroup$

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);
    }
}
$\endgroup$
10
  • $\begingroup$ 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 $\endgroup$ May 23, 2011 at 13:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alon Amit
    May 23, 2011 at 14:04
  • $\begingroup$ apparently I can only award the bounty in 9 hours. It's coming :-) $\endgroup$
    – Alon Amit
    May 23, 2011 at 14:28
  • $\begingroup$ @Alon: No hurry :-) I didn't really do all that much for it -- ideally, Junyan Xu should get it... $\endgroup$
    – joriki
    May 23, 2011 at 14:39
  • $\begingroup$ 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! $\endgroup$
    – Alon Amit
    May 23, 2011 at 19:25
13
$\begingroup$

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.

$\endgroup$
9
5
$\begingroup$

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 .

$\endgroup$
1
  • $\begingroup$ Great catch, thanks for sharing! $\endgroup$
    – Alon Amit
    Dec 3, 2020 at 16:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .