The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Contributions are welcome!
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
Big O is sort of like <=. little o is sort of like <.
O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".
o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)
Lim f/g -> C a constant
Lim f/h -> 0This isn't quite correct. O(g) doesn't require the limit to exist.
If you were joking then maybe you got me
https://stackoverflow.com/questions/1364444/difference-betwe...
this does not feel like a healthy place to be
Honestly it is not that much different from the divine inspiration if you have ever experienced it.
I do not know how you view the world or walk through it but language in general is simply subject to interpretation to me, the arrangement of words for the sentence is inspiration in and of itself - though the majority of time it amounts to minimum jumps.