wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum of squares with coeffs as 1 or -1
        
(Message started by: Aryabhatta on Jun 8^th, 2008, 11:26am)

Title: Sum of squares with coeffs as 1 or -1
Post by Aryabhatta on Jun 8^th, 2008, 11:26am

Interesting result:

Show that, any integer n can be written in the form

n = sum a_k k² where k ranges from 1 to m for some positive integer m and each a_k is either 1 or -1.

(note: m is dependent on n)

For example:

2 = - 1² - 2² -3² + 4²

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Barukh on Jun 8^th, 2008, 9:26pm

[hide]Since for every k, k² - (k+1)² - (k+2)² + (k+3)² = 4, it suffices to show that the statement holds for n = 1, 2, 3.[/hide]

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Aryabhatta on Jun 8^th, 2008, 9:55pm

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.

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Eigenray on Jun 8^th, 2008, 11:45pm

In fact we can show that there is always an m < C*n^1/3.

What's the best value of C you can prove? (For n sufficiently large, i.e., bound limsup (smallest m)/n^1/3)

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Aryabhatta on Jun 9^th, 2008, 12:25am

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).

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Eigenray on Jun 9^th, 2008, 1:34am

What is s? And clearly the liminf is 3^1/3.

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Aryabhatta on Jun 9^th, 2008, 10:16am

Sorry. s = n, the number which we intend to write as sum of squares.

Title: Re: Sum of squares with coeffs as 1 or -1
Post by Eigenray on Jun 9^th, 2008, 10:39am

Interesting. It looks like you are attacking it from the left. I was thinking: [hide]we can make the difference O(n^2/3) using the first O(n^1/3) terms of the form k², then make it O(n^1/3) using O(n^1/3) terms of the form 2k+1; with at most one more term we make the error 0 mod 4, then use O(n^1/3) 4s[/hide]. But I did not feel like putting in the constants.

We had a similar problem [link=http://www.ocf.berkeley.edu/%7Ewwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1134435769]before[/link].