Show that every element in a finite field can be written as the sum of two squares.

Printable View

- Aug 28th 2009, 05:32 AMynjFinite field
Show that every element in a finite field can be written as the sum of two squares.

- Aug 28th 2009, 06:03 AMnirax
you do this yourself --

1. consider $\displaystyle F^*$. prove that at least half of its elements are squares.

2. from this you conclude your result. - Aug 28th 2009, 06:08 AMynj
- Aug 28th 2009, 06:16 AMnirax
ok i will give u one more hint. suppose exactly half of them are squares (when is this the case ? when it is not ?) then the squares form an index 2 subgroup of F^*. the squares you can write as 0+a^2 .. suppose some element is not expressible as sum of two squares, then what happens if you take the squares and take the additive group generated by them ? if you add 0 to that set, will it become a subfield ? if so, what should be its cardinality ?

- Aug 28th 2009, 06:54 AMynj
hmm...I am sorry that i cannot understand your idea..

if one element can not be written as the sum of two squares, it does not mean it will not be in the additive group generated by the squares since it may be the sum of three squares..

if it is in the additive group generated by the squares, then the group will be the original group since its order is greater than the half of the original order..then nothing would happen??

May be there are some mistakes in above statements..but I am just confused... - Aug 28th 2009, 08:23 AMnirax
call $\displaystyle A$ as the multiplicative group of squares. so we decompose $\displaystyle F = A \cup \{0\} \cup B$. $\displaystyle B$ is the set of non squares. suppose an element $\displaystyle a$ is not expressible as sum of two squares. consider $\displaystyle a - A$. this set must be the same as $\displaystyle B$. consider $\displaystyle x = a - a^2$. clearly $\displaystyle x \in B$

but $\displaystyle B$ was the coset of the multiplicative group $\displaystyle A$ in $\displaystyle F^*$. so $\displaystyle B = a.A$. it follows that there exists a $\displaystyle y$ s.t

$\displaystyle x = a.y^2 = a - a^2$

$\displaystyle \Rightarrow a (y^2 - 1 + a) = 0$

$\displaystyle \Rightarrow y^2 = a - 1 $

RHS belongs to $\displaystyle B$ whereas LHS belongs to $\displaystyle A$ which are disjoint. - Aug 28th 2009, 08:38 AMynj
why a+A=B?

if we use contrapositive proof, suppose a+b^2=c^2, then a=c^2-b^2...no contradiction..

if a+b^2=0, then a=-b^2,any contradiction?

-b^2 is a square, or not? - Aug 28th 2009, 08:41 AMnirax
- Aug 28th 2009, 08:45 AMnirax
for example in $\displaystyle F_7$, $\displaystyle -1$ is not a square. whereas it is a square in all characteristic 2 fields.

- Aug 28th 2009, 08:46 AMynj
- Aug 28th 2009, 08:51 AMynj
Note that A is multiplicative group,not a additive group...So a+A is not a coset..

- Aug 28th 2009, 08:51 AMnirax
see ...

a + A has the same cardinality as A as well as B. also it cannot contain 0 as a is not a square. so it follows that a + A must either be B or A or in intersects with both. in the last two cases if it intersects nontrivially with A, it means there exist an element z^2 in A such that a + y^2 = z^2, but this is a contradiction to what we assumed about a.

edit :: this is erroneous, proof corrected above - Aug 28th 2009, 08:52 AMnirax
- Aug 28th 2009, 08:58 AMnirax
oopps!!!

instead of taking a+A, plz take a-A, it all works out then. i am sorry for this confusion. i noticed this when i myself wrote what u were hinting. i will correct above too. - Aug 28th 2009, 08:59 AMynj
ok....may be the statement of the question is unclear....I think the sum means +,not -.

I am not quite clear where is contradiction in your statement. a+y^2=z^2,a=z^2-y^2. if the sum actually means +, then z^2-y^2 is not a sum of two squares.......If the sum can mean -, then no problem exists.....