# Finite field

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Aug 28th 2009, 06:32 AM
ynj
Finite field
Show that every element in a finite field can be written as the sum of two squares.
• Aug 28th 2009, 07:03 AM
nirax
you do this yourself --

1. consider $F^*$. prove that at least half of its elements are squares.
2. from this you conclude your result.
• Aug 28th 2009, 07:08 AM
ynj
Quote:

Originally Posted by nirax
you do this yourself --

1. consider $F^*$. prove that at least half of its elements are squares.
2. from this you conclude your result.

yeah....I know but I'm sorry that I just have no idea how to get 2 from 1...
• Aug 28th 2009, 07:16 AM
nirax
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, 07:54 AM
ynj
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, 09:23 AM
nirax
call $A$ as the multiplicative group of squares. so we decompose $F = A \cup \{0\} \cup B$. $B$ is the set of non squares. suppose an element $a$ is not expressible as sum of two squares. consider $a - A$. this set must be the same as $B$. consider $x = a - a^2$. clearly $x \in B$

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

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

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

RHS belongs to $B$ whereas LHS belongs to $A$ which are disjoint.
• Aug 28th 2009, 09:38 AM
ynj
why a+A=B?
if we use contrapositive proof, suppose a+b^2=c^2, then a=c^2-b^2...no contradiction..
-b^2 is a square, or not?
• Aug 28th 2009, 09:41 AM
nirax
Quote:

Originally Posted by ynj
why a+A=B?
if we use contrapositive proof, suppose a+b^2=c^2, then a=c^2-b^2...no contradiction..
-b^2 is a square, or not?

a+A must be the same as B else it intersects with A then a wud be expressible as sum of two squares. also note that A and B are equicardinal. -b^2 may not be a square as -1 is not a square in all fields.
• Aug 28th 2009, 09:45 AM
nirax
for example in $F_7$, $-1$ is not a square. whereas it is a square in all characteristic 2 fields.
• Aug 28th 2009, 09:46 AM
ynj
Quote:

Originally Posted by nirax
a+A must be the same as B else it intersects with A then a wud be expressible as sum of two squares.

hmm...would you please explain it in detail? In my previous post, I actually try to prove a+A=B. but we get a=b^2-c^2,not a=b^2+c^2!!
• Aug 28th 2009, 09:51 AM
ynj
Note that A is multiplicative group,not a additive group...So a+A is not a coset..
• Aug 28th 2009, 09:51 AM
nirax
Quote:

Originally Posted by ynj
hmm...would you please explain it in detail? In my previous post, I actually try to prove a+A=B. but we get a=b^2-c^2,not a=b^2+c^2!!

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, 09:52 AM
nirax
Quote:

Originally Posted by ynj
Note that A is multiplicative group,not a additive group...So a+A is not a coset..

i am not saying a+A is a coset ... but B is a coset .. and a+A happens to be the same as B

edit :: this is erroneous, proof corrected above. plz read a-A in place of a+A
• Aug 28th 2009, 09:58 AM
nirax
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, 09:59 AM
ynj
Quote:

Originally Posted by nirax
see ...

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.

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.....
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last