Author |
Topic: Sum of squares with coeffs as 1 or -1 (Read 395 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Sum of squares with coeffs as 1 or -1
« on: Jun 8th, 2008, 11:26am » |
 Quote  Modify
|
Interesting result:
Show that, any integer n can be written in the form
n = sum ak k2 where k ranges from 1 to m for some positive integer m and each ak is either 1 or -1.
(note: m is dependent on n)
For example:
2 = - 12 - 22 -32 + 42
|
| « Last Edit: Jun 8th, 2008, 11:28am by Aryabhatta » |
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #1 on: Jun 8th, 2008, 9:26pm » |
Quote Modify
|
Since for every k, k2 - (k+1)2 - (k+2)2 + (k+3)2 = 4, it suffices to show that the statement holds for n = 1, 2, 3.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #2 on: Jun 8th, 2008, 9:55pm » |
Quote Modify
|
Very nice proof Barukh!
I had a much much more complicated proof and I also used (in fact needed) the help of a computer... but the result was stronger: There are an infinite number of such representations for each n.
Your proof can easily be extended to do the same.
|
| « Last Edit: Jun 8th, 2008, 11:23pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #3 on: Jun 8th, 2008, 11:45pm » |
Quote Modify
|
In fact we can show that there is always an m < C*n1/3.
What's the best value of C you can prove? (For n sufficiently large, i.e., bound limsup (smallest m)/n1/3)
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #4 on: Jun 9th, 2008, 12:25am » |
Quote Modify
|
The proof I have shows that any m for which
(m(m+1)(2m+1) -2s)/12 > 128
and LHS is an integer will do.
so it seems like C = 1 from that (though I am not sure).
|
| « Last Edit: Jun 9th, 2008, 12:26am by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #5 on: Jun 9th, 2008, 1:34am » |
Quote Modify
|
What is s? And clearly the liminf is 31/3.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #6 on: Jun 9th, 2008, 10:16am » |
Quote Modify
|
Sorry. s = n, the number which we intend to write as sum of squares.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of squares with coeffs as 1 or -1
« Reply #7 on: Jun 9th, 2008, 10:39am » |
Quote Modify
|
Interesting. It looks like you are attacking it from the left. I was thinking: we can make the difference O(n2/3) using the first O(n1/3) terms of the form k2, then make it O(n1/3) using O(n1/3) terms of the form 2k+1; with at most one more term we make the error 0 mod 4, then use O(n1/3) 4s. But I did not feel like putting in the constants.
We had a similar problem before.
|
| « Last Edit: Jun 9th, 2008, 10:42am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print