Fusible number

Fusible numbersFusible numbers - Jeff EricksonFusible numbers are a well-ordered set of rational numbers that produce the fast-growing fusible margin function. They were first defined by Jeff Erickson and further investigated by Junyan Xu.
== Definition ==
Consider the following classic math puzzle:
:You are given two fuses. Each one burns for exactly one minute, but not uniformly, so one cannot predict exactly how much of the fuse will be left after a given amount of time. You are allowed to light one or more unlit ends of any fuse, but only at time \(t = 0\) or when a fuse burns out completely. How do you measure 45 seconds?
The solution is to light both ends of one fuse and one end of the other fuse at the same time. When the first fuse burns out completely, 30 seconds have passed — then light the remaining end of the other fuse. Forty-five seconds will have passed when this fuse burns out.
We can expand on this problem by attempting to classify all numbers measureable in minutes by any finite number of fuses — call them fusible numbers. Since 45 seconds = 3/4 minutes can be measured, we say that \(3/4\) is fusible. Formally, a real number \(x\) is fusible if and only if \(x = 0\) or \(x = (a + b + 1) / 2\), with \(a\) and \(b\) fusible numbers and \(|a - b| < 1\).
Surprisingly, it turns out that the set of all fusible numbers is well-ordered within the real numbers. Erickson and Xu have shownFusible numbers and Peano Arithmetic - Jeff Erickson Theorem 1.2 that its order type is in fact \(\varepsilon_0\).
=== Margin function ===
Let \(m(x) = f(x) - x\), where \(f(x)\) is the smallest fusible number greater than \(x\). Erickson conjectured the function to satisfy \(m(x) = -x\) for \(x < 0\) and \(m(x - m(x - 1)) / 2\) otherwise, but Junyan Xu showedSurvey on Fusible Numbers - Junyan Xu that the formula was incorrect, and conjectured an alternative identity:
\[m(x) = \left\{ \begin{array}{ll}
 -x & \text{if } x < 0 \\
 m(x - m(x - 1) - 1/a + 2^{\lceil \log_2 m(x - 1) \rceil}) / 2 & \text{otherwise}
 \end{array} \right.\]
where \(a\) is the denominator of \(f(x - 1) = m(x - 1) + x - 1\). It is known that this value is an unconditional upper bound.Personal communication by Xu, according to revision history by LittlePeng9
Erickson and Xu have since come up with an algorithm for \(f(x)\) as well as a proof of its correctness (3).
#finds the smallest fusible number > x
f(x):
 if x < 0:
 return 0
 set min = infinity
 set b = x
 while b > x - 1/2:
 set a = f(2*x - b - 1)
 set b = f(2*x - a - 1)
 if (a + b + 1)/2 < min:
 set min = (a + b + 1)/2
 set b = b - 1/denominator(b)
 return min
This algorithm can be used to calculate \(m(x)\). The first few values of \(m(n)\) for natural numbers \(n\) are \(m(0) = 2^{-1}\), \(m(1) = 2^{-3}\), and \(m(2) = 2^{-10}\). It is also known that \(m(3)<2^{-2\uparrow^{9}16}\).
The function \(m_1(n) = -\log_2 m(n)\) is an extremely fast-growing function; the value for \(n = 4\) may well be greater than Graham's number. Little is known about \(m_1(n)\) except that it is bounded from below by \(f_{\varepsilon_0}(n-c)\) for some constant \(c\) (3).
Amusingly, in the same paper that proved this lower bound, it was shown that the function \(1/m(n)\), using Erickson's original conjectured version of \(m\), is also bounded from below by \(f_{\varepsilon_0}(n-c)\).
==Calculation example==
We can easily show here that, for example, \(m(1)\leq \frac{1}{8}\)
*At t=0, light both ends of the first fuse and one end of the second fuse.
*At t=0.5, the first fuse burns out and the second one has 30 seconds remaining. We light the other end of the second fuse and one end of yet another fuse.
*At t=0.75, the second fuse finishes burning. At that moment we light the other end of the third fuse, 45 seconds (.75 minutes) of which are left.
*At t=1.125, the third fuse is finished burning.
Therefore the number \(1.125=\frac{9}{8}\) is fusible, making \(f(1)\leq \frac{9}{8}\) and \(m(1)\leq \frac{1}{8}\).
== Sources ==
Category:Functions
Category:Unsolved problems
Category:Epsilon level
ja:可融数