The title was stolen from Waffle.Happy April Fool's Day everyone, and good luck to those of you hearing from colleges in 19 minutes!
Thursday, April 1, 2010
Fun Little Math Problem Of The Day
The title was stolen from Waffle.Happy April Fool's Day everyone, and good luck to those of you hearing from colleges in 19 minutes!
Subscribe to:
Post Comments (Atom)
haha i like your blog layout ;)
ReplyDeleteHmm so I guess the case p=2 is pretty trivial, too.
ReplyDeletehow do you do spoiler tags :(
ReplyDeleteor should i post the solution?
You can just post the solution or part of a solution.
ReplyDeleteSpoiler tags are REALLY annoying to code in
ReplyDeleteIs flmpotd going to be a new thing now?
ReplyDeleteIt's not going to be every day, it's just going to be whenever I have a problem that I think is nice.
ReplyDeleteThe key to this problem is knowing the random fact that (1 + zeta_p + (zeta_p)^4 + ... + (zeta_p)^((p-1)^2))^2 is p for p = 1 (mod 4) and -p for p = 3 (mod 4) (where zeta denotes a root of unity).
ReplyDeleteThis can easily be proven by considering the equation x^2 + y^2 = a (mod p), which happens to have p + 1 solutions for p = 3 (mod 4) and p not dividing a, 1 solution for p = 3 (mod 4) with p | a, p - 1 solutions for p = 1 (mod 4) and p not dividing a, and 2p - 1 solutions for p = 1 (mod 4) and p | a. (Most of) the proof of this is an exercise in the book Problems from the Book, as well as a problem on one of Brian's TJUSAMO contests.
The other key to solving this problem is the lemma that if integers a_0, a_1, ..., a_(p-1) satisfy a_0 + a_1 zeta_p + a_2 (zeta_p)^2 + ... + a_(p-1) (zeta_p)^(p-1) = 0, a_0 = a_1 = ... = a_(p-1). This can be proven using the fact that the field extension F_p/Q has degree p-1. I don't really know what a field extension is.
Note that this implies that if integers a_0, a_1, ..., a_(p-1), b_0, b_1, ..., b_(p-1) satisfy a_0 + a_1 zeta_p + a_2 (zeta_p)^2 + ... + a_(p-1) (zeta_p)^(p-1) = b_0 + b_1 zeta_p + b_2 (zeta_p)^2 + ... + b_(p-1) (zeta_p)^(p-1), a_0 - b_0 = a_1 - b_1 = ... = a_(p-1) - b_(p-1). I will refer to this in my proof as "the lemma."
Anyways, consider the number of solutions c_k to the equation (a_1)^2 + (a_2)^2 + ... + (a_n)^2 = k (mod p). (we are looking for c_0.)
Now imagine expanding out (1 + zeta_p + (zeta_p)^4 + ... + (zeta_p)^((p-1)^2))^n. Expanding this is equivalent to choosing one of 1, zeta_p, (zeta_p)^4, ..., (zeta_p)^((p-1)^2) from each term, multiplying them together, and summing this over all p^n choices.
So we get (1 + zeta_p + (zeta_p)^4 + ... + (zeta_p)^((p-1)^2))^n = c_0 + c_1 zeta_p + c_2 (zeta_p)^2 + ... + c_(p-1) (zeta_p)^(p-1).
Now, we split into a lot of cases.
ReplyDeleteCase 1. p = 1 (mod 4).
Case 1a. n is even.
Then p^(n/2) + 0 zeta_p + 0 (zeta_p)^2 + ... + 0 (zeta_p)^(p-1) = p^(n/2) = (1 + zeta_p + (zeta_p)^4 + ... + (zeta_p)^((p-1)^2))^n = c_0 + c_1 zeta_p + c_2 (zeta_p)^2 + ... + c_(p-1) (zeta_p)^(p-1).
Therefore, by the lemma, c_0 - p^(n/2) = c_1 - 0 = c_2 - 0 = ... = c_(p-1) - 0. Also, c_0 + c_1 + ... + c_(p-1) = p^n. Solving this, we get c_0 = (p - 1) p^(n/2 - 1) + p^(n - 1). (Also, c_k for p not dividing k is p^(n - 1) - p^(n/2 - 1).)
Case 1b. n is odd.
Then n - 1 is even. Therefore, the number of ways for (a_1)^2 + (a_2)^2 + ... + (a_(n-1))^2 = -(a_n)^2 (mod p) for a fixed a_n is (from the last section) p^(n - 2) - p^((n - 1)/2 - 1) if a_n is nonzero and (p - 1) p^((n - 1)/2 - 1) + p^(n - 2) otherwise. There are p - 1 ways for a_n to be nonzero and 1 way for a_n to be 0. Thus, there are (p-1)(p^(n - 2) - p^((n - 1)/2 - 1)) + (p - 1) p^((n - 1)/2 - 1) + p^(n - 2) = p^(n-1) ways for (a_1)^2 + (a_2)^2 + ... + (a_(n-1))^2 = -(a_n)^2 (mod p), total. Thus, the answer is p^(n-1) in this case.
Case 2. p = 3 (mod 4).
Case 1a. n is even. Then (-p)^(n/2) + 0 zeta_p + 0 (zeta_p)^2 + ... + 0 (zeta_p)^(p-1) = (-p)^(n/2) = (1 + zeta_p + (zeta_p)^4 + ... + (zeta_p)^((p-1)^2))^n = c_0 + c_1 zeta_p + c_2 (zeta_p)^2 + ... + c_(p-1) (zeta_p)^(p-1).
Therefore, by the lemma, c_0 - (-p)^(n/2) = c_1 - 0 = c_2 - 0 = ... = c_(p-1) - 0. Also, c_0 + c_1 + ... + c_(p-1) = p^n. Solving this, we get c_0 = (-1)^(n/2)(p - 1) p^(n/2 - 1) + p^(n - 1). (Also, c_k for p not dividing k is p^(n - 1) - (-1)^(n/2) p^(n/2 - 1).)
Case 2b. n is odd.
Then n - 1 is even. Therefore, the number of ways for (a_1)^2 + (a_2)^2 + ... + (a_(n-1))^2 = -(a_n)^2 (mod p) for a fixed a_n is (from the last section) p^(n - 2) - (-1)^((n-1)/2)p^((n - 1)/2 - 1) if a_n is nonzero and (p - 1) (-1)^((n-1)/2) p^((n - 1)/2 - 1) + p^(n - 2) otherwise. There are p - 1 ways for a_n to be nonzero and 1 way for a_n to be 0. Thus, there are (p-1)(p^(n - 2) - (-1)^((n-1)/2) p^((n - 1)/2 - 1)) + (p - 1) (-1)^((n-1)/2) p^((n - 1)/2 - 1) + p^(n - 2) = p^(n-1) ways for (a_1)^2 + (a_2)^2 + ... + (a_(n-1))^2 = -(a_n)^2 (mod p), total. Thus, the answer is p^(n-1) in this case.
To summarize: the answer is (p - 1) p^(n/2 - 1) + p^(n - 1) for p = 1 (mod 4) and n even, (-1)^(n/2)(p - 1) p^(n/2 - 1) + p^(n - 1) for p = 3 (mod 4) and n even, and p^(n-1) for n odd.