Relationship between Amp and Mono | The Sparkelling Bedangler

X_{n+k+1}\) is found. If \(X_n > X_{n+1}\), compare the subsequent elements pairwise until a pair such as \(X_{n+k} 0 \in \mathbb{N}\) such as \(c_1 M_1(X) \le M_2(X) \le c_2 M_1(X)\) for every sequence \(X\). Substituting \(M_1\) and \(M_2\) with \(\mathit{Mono}\) and \(\mathit{Reve}\) respectively, and picking \(c_1 = 1\) and \(c_2 = 2\), we can conclude that: [\mathit{Mono} \equiv \mathit{Reve}] That equivalence means that we can use \(\mathit{Reve}\) instead of \(\mathit{Mono}\) when analyzing their place in the partial order of measures of disorder. Additionally, it means that any sorting algorithm adaptive to one measure is also adaptive to the other. A valuable result in and of itself, considering that the definition of \(\mathit{Reve}\) is simpler to reason about than that of \(\mathit{Mono}\). \(\mathit{Reve}\) and \(\mathit{Amp}\) \(\mathit{Reve}\) also shares some similarities to \(\mathit{Amp}\), even though the two measures cannot be equivalent11. The most interesting such similarity concerns the maximum disorder: For both measures, the maximum disorder of a sequence \(X\) is \(\lvert X \rvert - 2\). Both find maximum disorder in zigzag permutations. Computing the equal-set12 of \(\mathit{Reve}\) for a small number of inputs shows that the number of permutations for which \(\mathit{Reve}\) finds maximum disorder is exactly equal to the number of zigzag permutations for that number of inputs. We found a similar result for \(\mathit{Amp}\) in a previous article. The resemblance does not stop there: we showed that both measures can be defined in terms of the pairwise order and satisfy the \(M(\mathit{Unique}(X)) = M(X)\) property. Once again we can attempt to analyze how they relate by looking at how they are affected by changes in the pairwise order for sequences without equal neighbors. We already know how \(\mathit{Reve}\) works, so all we have left to do is analyze how differing neighbors in the pairwise order affect \(\mathit{Amp}\). Let’s go back to the original definition of \(\mathit{Amp}\): [\mathit{Amp}(X) = \lvert X \rvert - \mathit{PTP}(X) - N_{\mathit{eq}}(X) - 1] Where: \(\lvert X \rvert\) is the number of elements in the sequence \(X\). \(\mathit{PTP}(X)\) is the peak-to-peak amplitude of \(X\), which corresponds to the prefix sum of the pairwise order of \(X\). \(N_{\mathit{eq}}(X)\) is the number of neighbors in \(X\) that compare equal. We already showed that we can ignore equal neighbors when comparing \(\mathit{Reve}\) and \(\mathit{Amp}\), which leaves two observations: A \(1\) followed by a \(-1\) (or the other way around) in a prefix sum cancels itself: \(\mathit{PTP}(X)\) does not grow, and \(\lvert X \rvert - \mathit{PTP}(X)\) grows by \(1\). A \(1\) followed by a \(1\) (or a \(-1\) followed by a \(-1\)) in the pairwise order does not contribute to disorder in \(\mathit{Reve}\), but might contribute \(1\) to the disorder in the prefix sum of \(\mathit{Amp}\) depending on the rest of the sequence. It follows that \(\mathit{Amp}(X)\) always finds at least as much disorder as \(\mathit{Reve}(X)\) for any sequence \(X\). Combining that result with that of the previous section, we get: [\mathit{Mono}(X) \le \mathit{Reve}(X) \le \mathit{Amp}(X)] And that transitively proves the conjecture from the beginning of this article. Conclusion When my knowledge of formal methods failed me. When my skillset proved insufficient to tackle the problem I set out to solve. When my will and motivation started to falter. A light shone at the end of the drooly nap. I woke up, dazed, yet dragging behind me The Intuition. The one reformulation that would make sense of it all. And it was incorrect. Fuck. This new chapter in the analysis of \(\mathit{Amp}\) started with a conjecture, a sheer instinct. I tried to convince myself that it was correct through tinkering, in a deeply empirical fashion. I somehow advanced further by reconsidering wrong results I had quite literally dreamt of, and managed to turn that into a new useful tool. And to finish it off… well, back to thinking formally until it all seems to click. And I think that’s beautiful! Had I been skilled enough to compare the behaviour of \(\mathit{Amp}\) and \(\mathit{Mono}\) directly, I might have been able to prove my original conjecture without having to introduce \(\mathit{Reve}\). But I’m very happy I was unable to do so! Thanks to that, I end up with a new measure of disorder which is at the same time equivalent to \(\mathit{Mono}\), but also much simpler to define and reason about. For all I know it might be a key that I can use to prove more relationships in the future. Besides, the whole process of managing to find a new intermediary measure felt incredibly satisfying. It reminded me of how mathematics exercises chain questions that have you demonstrate smaller results, only to use them a few questions later to solve bigger problems that would otherwise be too...