Squares sums and prime decomposition.
Stush
10*10 + 11*11 = 221
Of course if you allow negative integers
5*5 + 14*14 = 221
5*5 + -14*-14 = 221
-5*-5 + 14*14 = 221
-5*-5 + -14*-14 = 221
...
Numbers which contain prime factors raised to odd powers of the form p = 3
(mod 4) cannot be written as the sum of two squares.
Guillermo Phillips wrote in message
<935797528.27748.0...@news.demon.co.uk>...
>If a number is the sum of two squares, is this always a unique
>representation, or can their be more than one representation of this number
>as the sum of other (different) pairs of squares?
>
>I'd like to prove or disprove this for myself, but my number theory is a
bit
>lacking - but I have excellent visualisation skills to hand.
>
>This would help me understand if there is a direct pairing between the
>difference of two squares and the sum of two squares.
>
>There's no mystery here, I just have a peverse fascination for squares.
>
>Ta
>
>Guillermo.
>
>
>
Oscar Lanzi III
don't have to worry about whether the Y2K bug is acting on your computer
(yeah right!).
The number 65 is 5 times 13. Any product involving two or more 4n+1
primes and at most one power of 2 will be expressible as a sum of
relatively prime squares in more than one way.
--OL
Guillermo Phillips
spam...@nil.nil
> If a number is the sum of two squares, is this always a unique
> representation, or can their be more than one representation of this number
> as the sum of other (different) pairs of squares?
If z=2^a*Q*PROD[p_j^a^j]
where:
Q=product of odd prime factors each congruent to -1 mod 4
Each p_j is a prime congruent to 1 mod 4 (and I have grouped all the
repeated occurences of, say, 5, in the term 5^a_1 where a_1 is the number
of times 5 occurs)
Then z can be written as the sum of two squares if and only if Q is a
perfect square (primes=-1 mod 4 each appear an even number of times)
Then if all the a_k are even (z is a square or twice a square), z can be
written as the sum of two squares in [PROD(a_k+1)+1]/2 ways. If at least
one a_k is odd, z can be written as the sum of two squares in
PROD(a_k+1)/2 ways.
---------
(proof: Z[i] is a UFD with units U={1,-1,i,-i} and primes=irreducibles
given by:
Uq where q is a prime in Z which is congruent to -1 mod 4 and U is a unit.
AND x+iy where x^2+y^2 is a prime in Z congruent to +1 mod 4
AND U*(1+i) where U is a unit
NOTE: each prime congruent to 1 mod 4 CAN be written as u^2+v^2
(note: for a prime congruent to 1 mod 4 and picking fixed u,v with
u^2+v^2=p=this prime, then you get eight elements of the second type:
U(u+iv) and U(u-iv) where U is a unit ... these are the x+iy's that appear
for that prime.
For 2, a prime in Z, one has 1=u,1=v, u^2+v^2=2 and for x^2+y^2=2, x+iy
are prime. You only get four different primes for 2 though, for 1+i=i(1-i)
and the primes are U(i+i))
To write z=x^2+y^2=(x+iy)(x-iy) you look at factorizations in the Gaussian
integers. As this is a UFD, you can look at the prime factorization of z
and find out how we can split the factors into x+iy and x-iy
You get such a factorization just when:
x+iy=U*(1+i)^a*SQRT(Q)*PROD{[u_k+/-iv_k]:
(u_k,v_k) term repeated a_k times but you can
make different choices for the +/- sign in each}
(SQRT(Q) has to be an integer, remember)
where for each prime p_k we pick ONE representation, u_k, v_k with
u_k^2+v_k^2=p_k and we have a_k terms u_k+/-iv_k for p_k if p_k is a
factor of z a_k-times: you can choose the +/- differently for each of the
repeated factors. The number of choices that lead to different x+iy's is
given by:
four choices for U.
For each p_k you can choose the number of times you use a + sign (instead
of - sign) from 0 times to a_k times (leading to a_k+1 choices for each
p_k) for a total number of ways of 4*PROD(a_k+1) ways.
However, this has (for 5=5^1:a_1=1) 8 ways to represent 5:
5=1^2+2^1, (-1)^2+2^2, 1^2+(-2)^2, (-1)^2+(-2)^2,
=2^2+1^2, (-2)^2+1^2, 2^2+(-1)^2, (-2)^2+(-1)^2
(these ARE different x+iy's!)
If we want essentially distinct ways of representing z (as a sum of
squares of unordered pairs of non-negative integers) each representation
(EXCEPT for one of them if z is a square or twice a square!) is in an
equivalence class of 8 elements which are essentially the same (so we
divide by 8) (if z is a square or twice a square, ONE of the equivalence
classes has four terms: if z=a^2, then a^2+0^2 only corresponds to four
terms since -0=0 and if z=2b^2, then z=b^2+b^2 corresponds to four terms
since swapping the terms does not lead to another representation)
(adjusting for the case of z being a square or twice a square gives the
above results).
---------
---------
z can be written as the sum of two *relatively prime* squares IFF Q=1 (z
is not divisible by a prime congruent to -1 mod 4) AND a=0 or 1 (z is not
divisible by 4) (this is used for finding which z's can be the hypotenuse
of a *primitive* Pythagorean triangle).
In that case, to keep x,y relatively prime we must have:
x+iy=U(1+i)^a*PROD[(u_k+/-iv_k)^a_k]
NOTE here that u_k+/-iv_k appears as one term raised to the a_k power for
the prime p_k rather than a_k separate terms ... the point is that for
relative primality one MUST choose the same sign, + or -, for all the
u_k+/-iv_k terms corresponding to any particular p_k.
The number of choices is now only two for each p_k (you can choose the
+ or - sign but have to use the same sign for each of the a_k terms
corresponding to a repeated factor of the prime p_k) (2^c in total where c
is the number of primes congruent to 1 mod 4 which divide z) and 4 for U.
The total number is 4*2^c and again, each essentially distinct way has 8
equivalent ways so there are 2^(c-1) ways to write such a z as the sum of
relatively prime squares (except for z a square or twice a square ... as
the restrictions that z be the sum of two relatively prime squares is
imposed, this only happens for z=1 (writable only as 1^2+0^2) and z=2
(1^2+1^2).
====
====
In short ... the number of ways of writing z as the sum of two squares if
z=2^a*Q*PROD[p_k^a_k] where Q is the product of the primes congruent to -1
mod 4 which divide z AND Q IS A PERFECT SQUARE and p_k are the primes
congruent to 1 mod 4 is given by INT([PROD(a_k+1)+1]/2) (the INT handles
the case of all a_k even and at least one being odd together) and this can
only be done if Q IS a perfect square.
===
For z to have an (essentially) unique representation as the sum of two
squares:
For this number to be ONE (unique), i.e. PROD(a_k+1)=2 (for at least 1 a_k
being odd) is that there be precisely one a_k=1 and the rest zero (no
other factors) or
z=2^a*Q*p where Q is a perfect square
---
If all of the a_k are even, we want PROD[a_k+1]=1 (so it is a null
product, or all a_k=0, however you like to think of it) and z=2^a*Q (where
Q is a perfect square)
NOTE that each prime p, congruent to 1 mod 4, can be written as the sum of
two squares in one (essentially) unique way.
For z=2^a*Q*p (Q a perfect square) the only way to write z as the sum of
two squares is:
x+iy=(1+i)^a*SQRT(Q)*(u+iv) where p=u^2+v^2
(in U*(1+i)^a*SQRT(Q)*(u+-/iv) ... well, the U and +/- only swap the terms
and put in +/- signs in the representation of z)
For z=2^a*Q (Q a perfect square) the only (essentially
distinct) representation is:
x+iy=(1+i)^a*SQRT(Q)
(if a is even, this is x=2^(a/2)*SQRT(Q), y=0:
if a is odd, this is x=2^([a-1]/2)*SQRT(Q)=y
in these cases z is a perfect square (z=(SQRT(z))^2+0^2) or twice a
perfect square (z=(SQRT(z/2))^2+(SQRT(z/2))^2))
Further note: (1+i)^a is 2^(a/2) times a unit in Z[i] if a is even or
(1+i)*2^((a-1)/2)*times a unit (if a is odd) (the unit only swaps and
changes signs in the final result, not giving any essentially different
representation).
Thus, for z=2^a*Q*p (Q a perfect square) to have a unique representation
we have: (for p=u^2+v^2)
for a even, this only representation is
z=(2^(a/2)*SQRT(Q)*u)^2+(2^(a/2)*SQRT(Q)*v)^2
for a odd the only representation is:
z=(2^([a-1]/2)*SQRT(Q)*[u-v])^2+(2^([a-1]/2)*SQRT(Q)*[u+v])^2
====
E.g.
z=5: a_1=1
eight representations if we worry about signs and order
5=1^2+2^2=(-1)^2+2^2=(-2)^2+(-1)^2 etc.
one essentially distinct way: 5=1^2+2^2
z=90: =2*9*5 (a_1=1)
one way
z=9^2+3^2
z=25: a_1=2:
two ways
0^2+5^2, 3^2+4^2
z=125: a_1=3
two ways
5^2+10^2, 2^2+11^2
z=625: three ways (a_1=4)
25^2+0^2, 15^2+20^2, 7^2+24^2
z=15: 3*5: a_1=a_2=1
no ways (Q=3 is not a perfect square)
z=65=5*13, a_1=1=a_2
two ways:
1^2+8^2, 4^2+7^2
spam...@nil.nil
> z=15: 3*5: a_1=a_2=1
> no ways (Q=3 is not a perfect square)
Should say: Q=3 (not a perfect square). One prime congruent to 1 mod 4
(p_1=5). a_1=1 (there is no a_2!)
Clive Tooth
Try figuring out 7^2+1^2. Then compute 5^2+5^2.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
spam...@nil.nil
> Any product involving two or more 4n+1
> primes and at most one power of 2 will be expressible as a sum of
> relatively prime squares in more than one way.
Should also require that the number have NO prime factors congruent to -1
mod 4.
(if c is the number of distinct prime factors congruent to 1 mod 4, then
the number of (essentially) distinct ways of writing z as a sum of two
rel. prime squares is 2^(c-1))
spam...@nil.nil
> where c
> is the number of primes congruent to 1 mod 4 which divide z...
> The total number is 4*2^c and again, each essentially distinct way has 8
> equivalent ways so there are 2^(c-1) ways to write such a z as the sum of
> relatively prime squares
To be overly pedantic. c is the number of *distinct* primes congruent to
1 mod 4 (and z is not divisible by 4 nor any prime congruent to
-1 mod 4)
Stush
Then the average value of f(n) is pi as n approaches infinity.
Also the sum of f(ni) for i = 0,1,2,...k = pi*k + O(k^c). The smallest c
known to be true is 27/82, but it is not known if that is the smallest
exponent; however, it is known c <=1/4 is false.
spam...@nil.nil wrote in message <37c8...@news.inch.com>...
>spam...@nil.nil wrote:
>
>> where c
>> is the number of primes congruent to 1 mod 4 which divide z...
>
>> The total number is 4*2^c and again, each essentially distinct way has 8
>> equivalent ways so there are 2^(c-1) ways to write such a z as the sum of
>> relatively prime squares
>
>To be overly pedantic. c is the number of *distinct* primes congruent to
> 1 mod 4 (and z is not divisible by 4 nor any prime congruent to
>-1 mod 4)