Post

The square root can be uniformly approximated to error ε by a rational function of degree O(log²(1/ε)). This surprising, since a polynomial approximation (e.g. Taylor series) requires degree Ω(1/ε), so rational functions are exponentially better than polynomials.

19/11/24, 6:23 pm9 reposts58 likes

Thomas Steinke

@stein.ke

19 Nov 2024

The proof uses the Poisson summation formula to show that an integral representation of the square root can be very well approximated by a discrete sum. bsky.app/profile/stei...

Thomas Steinke@stein.ke

The Poisson summation formula is one of my favorite tricks. It seems magical, but the proof is quite simple:

Thomas Steinke

@stein.ke

19 Nov 2024

This approximation result was originally shown by Newman in 1964 (using a different construction and proof). Approximating the square root function on [0,1] is equivalent to approximating the absolute value function on [-1,1]. doi.org/10.1307/mmj/...

Thomas Steinke

@stein.ke

19 Nov 2024

This result has been extended to other exponents (i.e. x^α for any α>0) and we have sharp constants: www.ams.org/journals/bul...

Thomas Steinke

@stein.ke

19 Nov 2024

The proof above is adapted from Gopal & Trefethen (2019, doi.org/10.1007/s002... ), although they cite another source that I wasn't able to access. What's nice about this proof is that it extends to x in the complex plane.