The Markov brothers' inequality, its connection to quantum computing, and its 100-page proof

About the author

I'm a 4th-year grad student at the University of Washington, studying theoretical computer science, and in particular, things with some quantum computing flavor. My website has general information about me; I don't have experience with math exposition at this level, but the closest I've come is a blog post I did a few years ago, and I've taken a course in data visualization.

Quick Summary

I'd like to make something on the Markov brothers inequality: this inequality states that, if a degree-$d$ polynomial $p(x)$ is bounded in [-1,1], meaning that $-1 \leq p(x) \leq 1$ whenever $-1 \leq x \leq 1$, then the derivative of $p$, $p'(x)$, satisfies $-d^2 \leq p(x) \leq d^2$ (again, for all $x$ between $-1$ and $1$). Specifically, the main reference will be Shadrin's excellent survey "Twelve Proofs of the Markov Inequality", which covers historical context and an outline of the proof.

This is a pretty deep theorem in approximation theory, so I don't want to prove it. However, I think there's a lot interesting to say still:

The history of this inequality is entertaining and illustrative of how the narrative of "mathematical progress" isn't exactly as clean as one might think: a mathematician once called the 110-page paper this was proved in, one of the most cited papers and one of the least read.
A core idea in the proof, equioscillation, is beautiful and straightforward to illustrate in something like Manim, but to my knowledge hasn't appeared in the "internet math exposition" space. (I have ideas for how to explain the proof without getting into the nitty-gritty.)
The inequality can be used to prove that the quantum algorithm Grover's algorithm is optimal. I can't explain this completely (that would require knowing how quantum circuits work), but I can "almost bridge" the gap.

Target medium

I'm hoping to make this into a 3B1B-length video (hopefully <30 minutes), and I'm willing to dump time into the script. However, I have no experience with editing and Manim, so I would want someone to take charge of those aspects. Since this is a large ask, I'm happy to scope down to a blog post with animated visualizations. My hope would be to be approachable, and try to reflect how I communicate mathematical ideas as a grad student (discussing techniques and ideas without needing to get into the rigorous details for the most complicated pieces).

More details

Attached is a markdown file with a very rough outline. some-submission.md

References:

Alexei Shadrin's survey on the Markov inequality
Mark Bun's talk on the connection of the Markov inequality to quantum computing

Contact details

twitter dm: @ewintang

leios / SoME_Topics