Using calculus to do number theory(hidden-phenomena.com)
hidden-phenomena.com
Using calculus to do number theory
https://hidden-phenomena.com/articles/hensels
22 comments
The technical term is "formal derivative" b/c there are no limits involved, it's basically a rewrite rule for changing x^n to nx^(n-1).
I know, yes, but did not want to digress. Thanks though. Actually, it is the "extension" to K[e] with e^2=0, as "usual".
The infinitesimally thickened point.
The mathematical field of tackling number theory problems in this way is called analytic number theory.
https://en.wikipedia.org/wiki/Analytic_number_theory
The prime number theorem, on how prime numbers are distributed amongst the integers, was first proved using analytic techniques.
https://en.wikipedia.org/wiki/Analytic_number_theory
The prime number theorem, on how prime numbers are distributed amongst the integers, was first proved using analytic techniques.
Analytic number theory exists and involves calculus, but it's not what the linked post is about. The article talks about Hensel's lemma, which is a purely algebraic statement with a purely algebraic proof, which, however, is inspired by techniques from calculus. This is typically still categorized as algebraic number theory.
I love complex analysis, and that's the branch of calculus that is most associated with number theory. For example, it was critical in the original proof of the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions. Today, all kinds of number theoretic functions are studied using complex analysis, like the famous Riemann zeta function, Dirichlet L-functions, theta functions, and so on.
So that's what I expected this to be about. And it was super fun to see that it was actually not! Definitely learned something today.
I had to think about the following sentence for a bit: "We know that any integer x obeying f(x)≡0 (mod 125) must obey x≡2(mod 5)."
My explanation (it's basically all in the article, but here I spell it out): If f(x) = 0 (mod 125), then 125 divides f(x). Since 125 = 5^3, it must be that 5 also divides f(x). The only way for 5 to divide f(x) is for x = 2 (mod 5), by brute-forcing all solutions to f(x) = 0 (mod 5). Therefore for f(x) = 0 (mod 125), x = 2 (mod 5).
It's also worth saying why we only need to check all integers between 0 and n-1 when solving an equation mod n:
Suppose that for some integer y, f(y) = 0 (mod n) but y >= n or y < 0. Then for some x between 0 and n-1 (inclusive),
x = y (mod n).
Since the function f is a polynomial with integer coefficients, evaluating f on an integer involves only multiplication and addition by integers. Some crucial facts about congruences:
If x = y (mod n) then a + x = a + y (mod n) for any integer a. If x = y (mod n) then ax = ay (mod n) for any integer a. If x = y (mod n) then x^2 = y^2 (mod n), and similarly other integer powers.
From these we conclude that if x = y (mod n), then f(x) = f(y) (mod n) for any polynomial f.
So, for any y >= n with f(y) = 0 (mod n), there's some x between 0 and n-1 (inclusive) that also satisfies f(x) = 0 (mod n); in fact it's whatever integer in that range that y is congruent to. So we need only check integers in that range to find all possible solutions to f(x) = 0 (mod n).
Forgive me for the long explanation for what are of course elementary facts in number theory! I'm rusty on number theory so I had to explicitly work them out, so I figured maybe someone else might also benefit.
So that's what I expected this to be about. And it was super fun to see that it was actually not! Definitely learned something today.
I had to think about the following sentence for a bit: "We know that any integer x obeying f(x)≡0 (mod 125) must obey x≡2(mod 5)."
My explanation (it's basically all in the article, but here I spell it out): If f(x) = 0 (mod 125), then 125 divides f(x). Since 125 = 5^3, it must be that 5 also divides f(x). The only way for 5 to divide f(x) is for x = 2 (mod 5), by brute-forcing all solutions to f(x) = 0 (mod 5). Therefore for f(x) = 0 (mod 125), x = 2 (mod 5).
It's also worth saying why we only need to check all integers between 0 and n-1 when solving an equation mod n:
Suppose that for some integer y, f(y) = 0 (mod n) but y >= n or y < 0. Then for some x between 0 and n-1 (inclusive),
x = y (mod n).
Since the function f is a polynomial with integer coefficients, evaluating f on an integer involves only multiplication and addition by integers. Some crucial facts about congruences:
If x = y (mod n) then a + x = a + y (mod n) for any integer a. If x = y (mod n) then ax = ay (mod n) for any integer a. If x = y (mod n) then x^2 = y^2 (mod n), and similarly other integer powers.
From these we conclude that if x = y (mod n), then f(x) = f(y) (mod n) for any polynomial f.
So, for any y >= n with f(y) = 0 (mod n), there's some x between 0 and n-1 (inclusive) that also satisfies f(x) = 0 (mod n); in fact it's whatever integer in that range that y is congruent to. So we need only check integers in that range to find all possible solutions to f(x) = 0 (mod n).
Forgive me for the long explanation for what are of course elementary facts in number theory! I'm rusty on number theory so I had to explicitly work them out, so I figured maybe someone else might also benefit.
>for any y >= n with f(y) = 0 (mod n), there's some x between 0 and n-1
There's a simpler way to see this, any such y can be represented as y = nk + x where i,j are divisor & remainder. Then f(y) = f(nk + x) = f(x) modulo n since by binomial theorem all other terms other than those with just x will be divisible by n.
There's a simpler way to see this, any such y can be represented as y = nk + x where i,j are divisor & remainder. Then f(y) = f(nk + x) = f(x) modulo n since by binomial theorem all other terms other than those with just x will be divisible by n.
Thank you and yes, I agree! It's neat to use the binomial theorem to see this, because that's the tool the article uses for the main trick/insight it's explaining.
>neat to use the binomial theorem to see this,
Yeah as far as I understand this basically _is_ where the connection to calculus comes in. As the article points out, it's very similar to computing the derivative via infinitessimals, e.g. (x+dx)^3 = x^3 + 3x^2 dx + O(dx^2), and from that you recover the term linear in dx as the derivative, 3x^2 . For the derivative you consider epsilon as a nilpotent where dx^2 = 0, and for hensel lifting lemma any term with a factor of p^2 gets zeroed (modulo p^2).
I'm just a layperson but I'm not really convinced that this is differential calculus in a meaningful sense. The other commenter mentioned "formal derivative" which seems fitting. There might be a connection to "umbral calculus" (something i know nothing about fwiw) though in the way you use the formal computations of derivatives for identities on polynomial equations, even without there being any differentials actually involved.
Yeah as far as I understand this basically _is_ where the connection to calculus comes in. As the article points out, it's very similar to computing the derivative via infinitessimals, e.g. (x+dx)^3 = x^3 + 3x^2 dx + O(dx^2), and from that you recover the term linear in dx as the derivative, 3x^2 . For the derivative you consider epsilon as a nilpotent where dx^2 = 0, and for hensel lifting lemma any term with a factor of p^2 gets zeroed (modulo p^2).
I'm just a layperson but I'm not really convinced that this is differential calculus in a meaningful sense. The other commenter mentioned "formal derivative" which seems fitting. There might be a connection to "umbral calculus" (something i know nothing about fwiw) though in the way you use the formal computations of derivatives for identities on polynomial equations, even without there being any differentials actually involved.
author was so excited to point at calculus, that he forgot to derive actual mod3000 answer from chinese remainders...
and it seems much more intuitive for me to see this technique as "find x mod p^n, then apply x->ans+p*x transformation and do everything at mod p^n+1" - and to derive that it results in derivatives from that
and it seems much more intuitive for me to see this technique as "find x mod p^n, then apply x->ans+p*x transformation and do everything at mod p^n+1" - and to derive that it results in derivatives from that
It's delightful (and unsurprising) that Newton's method shows up as the main bridge.
This idea leads to the p-adic numbers:
https://en.wikipedia.org/wiki/P-adic_number
https://en.wikipedia.org/wiki/P-adic_number
"Appendix: The Langlands program"
no offense but this doesn't even come close to describing it at all
no offense but this doesn't even come close to describing it at all
If author is following this: minor typo in "we use the seem approximation trick again": seem -> same
Blog looks promising. Is there a RSS feed associated with it?
Loved this. Thanks.
But great and elegant article. Thanks.