Math puzzle #2 - Page 2

On September 10 2010 15:30 gondolin wrote:
We may assume by the CRT that d=p^n, with p odd, the case p=2 being trivial.
Now by induction, there exist N such that 2^N+N=0 mod phi(d).
Write 2^N+N + k phi(d) =0.
Then 2^(N+k phi(d)) + (N + k phi(d)) = 2^N+N+k phi(d) = 0 mod p^n.
CQFD.




Nice. Will you use it to prove the Hasse-Weil theorem on the zeta function of algebraic curve? From what I remember you can prove it without the classical proof from Weil with Jacobians by clever user of the Riemann-Roch (the hardest part being the Riemann hypothesis, with Jacobians you have the Rosati involution, here I don't remember how you do it).

By the way I infer from your signature that you are working on Complex Multiplication? That's one of the most beautiful area in Mathematics (according to Hilbert )!

On September 10 2010 15:36 Steve496 wrote:
Why does CRT force d=p^n?

On September 10 2010 15:43 mieda wrote:


Riemann Roch is useful for just about everything involving curves (ofc there is an analogue for surfaces.. but the formulas get nasty when dimensions rise)! I'm preparing the notes as a background for students who are starting to count dimensions of automorphic forms of various weights. They'll need to know some dimension theory on the complex surfaces formed from congruence subgroups, and that's just riemann roch ^^. Actually you don't need serre duality for proof of riemann roch theorems, especially if one is only working over the complexes, but the idea is nice enough

I'm not really working on complex multiplication per se. That's more lower dimension (i.e. elliptic curves). Of course there are analogues for higher dimensional abelian varieties, but the thing I work on is nice combinatorial descriptions (if I can!) of cohomology of rapoport-zink spaces.

Also, you should probably fill in more detail for reduction to d = p^n case. Chinese Remainder Theorem directly doesn't apply, as you will see. The problem is that the modulus are not pair-wise coprime when you apply it directly. But it just takes a little more work to get it to work.

Are you working on math also?

Yeah that's true, you need to keep track of the congruent relations of the N_i solution for p_i to verify you can "glue" the solutions. (That's funny how the point of view change, before I thought of the CRT as an arithmetic statement, now when I think about it I visualize it as local sections over Spec(Z/NZ) that we try to glue).

I have a background in mathematics, but now I am working on computer science By the way I see that you are from Harvard. Do you know Sophie Morel? She attended the same "college" as me and is very good

It's interesting to see another person who did math in TL.net ^^. Did you play SC also?

On September 10 2010 17:21 gondolin wrote:


There is a user (Muirhead I think) that is also doing math (he works on algebraic geometry in MIT).
Yeah I discovered SC when I went to the "college" I mentioned. I played warcraft 3 before, but once I discovered SC i switched

On September 10 2010 21:08 Ivs wrote:
There is a generalisation to this:
Fixing any a, d, k, and gcd(d,k)=1
ka^x = x mod d
always has infinitely many solutions x.

Proof:
+ Show Spoiler +

Setting a=2, k=-1 solves your question =).

On September 11 2010 00:23 mieda wrote:


The problem is that x = ka^y mod d doesn't imply a^(ka^y) = a^x (mod d).

On September 11 2010 00:55 Ivs wrote:


I didn't say it implies, rather, it is suffice to solve the second equation to obtain a solution to the first.

edit: More specifically,
If x = ka^y, then
ka^x = x mod d if and only if a^(ka^y) = a^y mod d

On September 11 2010 02:23 KristianJS wrote:
This exercise taught me a useful lesson in how the normal conditions given for CRT are stronger than necessary

On September 11 2010 02:07 mieda wrote:


Sure, but when k < 0 you're raising a to a negative power. For example in our case a = 2 and k = -1, you're saying -2^x = x (mod d) iff 2^(-2^y) = 2^y mod d, and how will you interpret 2^(-2^y) ? it's not an integer.

Also, in your original proof you wrote x = ka^y (mod d), thus sufficient to solve a^(ka^y) = a^y mod d, from which I thought that you seemed to be saying that if x = ka^y (mod d) then a^x = a^(ka^y) mod d, which isn't true.

Remark: When k > 0, the remark I made earlier in this thread is exactly this method. This solution doesn't seem to work, because we have k < 0 now. I made the remark that when we have to solve 2^N = N (mod d) and not 2^N = -N (mod d), then it's a bit easier.

Edit: There is a way to fix this argument, and that is to choose k so that gcd(d,k) = 1 and k > 0 by adding d to it sufficient number of times.

I did impose gcd(d,k) = 1, read the whole thing =P. You are right about the negative part though, and yup it is easily fixed.

On September 11 2010 11:36 mieda wrote:


I read the whole thing. Only the $k > 0$ is meant to be new. You should read my last sentencen as "gcd(d,k) = 1" *and also* "k > 0"