Question about field
Herb
If F={0,1,a,b} is a field of order 4, then
How can I determine a+b , a*b ?
I know a+b=/=a because b=/=0
also, a+b=/=b since a=/=0.
But I can not determine wheather a+b = 0 or 1.
I know a*b=/=a, a*b=/=b because b=/=1, a=/=1.
But I can not judge wheather a*b = 0 or 1
Would you please help me ?
Thanks.
Van Jacques
For finite fields you need to give the irreducible poly giving the
elements. When p = 2, it is x^2 + x + 1 (for n = 2, ==> p^2 = 4).
Since + = - in Z_2, x^2 = x + 1, and we have
F = (0,1,x,x+1), where x + 1 = x^2, x is the solution of the
polynomial.
Thus x^3 = x x^2 = x(x + 1) = x^2 + x = x + x + 1 = 1,
so order x = 2^2 - 1 = 3 as it must in a finite field.
Van
Jon Haugsand
> But I can not judge wheather a*b = 0 or 1
As this is a field, a*b cannot be equal to 0.
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
William Elliot
> If F={0,1,a,b} is a field of order 4, then
>
> How can I determine a+b , a*b ?
>
> But I can not determine wheather a+b = 0 or 1.
>
If a + b = 0, then a = a + a+b = ??
Ron Sperber
For the first part, remember that in a field, the elements form an
additive group under addition. So either this additive group is cyclic
of order 4, or it is isomorphic to the Klein 4-group. See if you can
show that it can't be cyclic of order 4. If it is the Klein 4-group,
each element is of order 2. thus a+a=0, so a+b can't be zero.
-Ron
Arturo Magidin
>Hello,
>
>If F={0,1,a,b} is a field of order 4, then
>
>How can I determine a+b , a*b ?
>
>I know a+b=/=a because b=/=0
>also, a+b=/=b since a=/=0.
>But I can not determine wheather a+b = 0 or 1.
Since a+a = 0, then a+b cannot also equal 0. So...
(Or you could construct the field: it is isomorphic to
F_2[x]/(x^2+x+1), where F_2 is the field of 2 elements.
>I know a*b=/=a, a*b=/=b because b=/=1, a=/=1.
>But I can not judge wheather a*b = 0 or 1
If it is a field, then surely a*b=0 would imply a=0 or b=0. So...
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Virgil
> Hello,
For one thing, the non-zero elements of a field must form a
multiplicative group. and in this case, a group with 3 elements.
That should straighten out your multiplication tables with a little
thught.
Then use the distributive property to straighen out your addition.
Bill Dubuque
>Herb <fuzz...@nate.com> wrote:
>>
>> If F = {0,1,a,b} is a field of order 4
>>
>> then how can I determine a+b, a*b ?
>>
>> I know a+b=/=a because b=/=0
>> also, a+b=/=b since a=/=0.
>
> Since a+a = 0, then a+b cannot also equal 0. So...
Which way do you prove 2a = 0? Presumably via
standard ring/field theory. Here's a direct way.
If 2 != 0 then the nonzero elts x obey x != -x
so the set of nonzero elts has even cardinality
because it may be partitioned into pairs x, -x.
So a finite field has odd cardinality if 2 != 0.
The same method shows that a natural number is
a square iff it has an odd number of divisors.
This is but one simple prototypical example of
many of the pretty applications of involutions
(above x -> -x and x -> n/x respectively).
Following is a much less trivial application.
----------------------------------------------------------------------
A One-Sentence Proof That Every Prime p = 1 (mod 4)
Is a Sum of Two Squares
D. Zagier, Amer. Math. Monthly, 97 (1990) 144
The involution on the finite set S = { (x,y,z) in N^3: x^2+4yz = p }
defined by
{ (x+2z, z, y-x-z) if x < y-z
(x,y,z) |--> { (2y-x, y, x-y+z) if y-z < x < 2y
{ (x-2y, x-y+z, y) if x > 2y
has exactly one fixed point, so |S| is odd and the involution defined
by (x,y,z) |--> (x,z,y) also has a fixed point.
This proof is a simplification of one due to Heath-Brown [1]
(inspired, in turn, by a proof given by Liouville). The verifications
of the implicitly made assertions -- that S is finite and that the
map is well-defined and involutory (i.e., equal to its own inverse)
and has exactly one fixed point -- are immediate and have been left
to the reader. Only the last requires that p be a prime of the form
4k+1, the fixed point then being (1,1,k).
Note that the proof is not constructive: it does not give a method
to actually find the representation of p as a sum of two squares. A
similar phenomenon occurs with results in topology and analysis that
are proved using fixed-point theorems. Indeed, the basic principle
we used: 'The cardinalities of a finite set and of its fixed-point
set under any involution have the same parity,' is a combinatorial
analogue and special case of the corresponding topological result:
'The Euler characteristics of a topological space and of its fixed-
point set under any continuous involution have the same parity.'
For a discussion of constructive proofs of the two-squares
theorem, see the Editor's Corner elsewhere in this issue. [p. 125]
REFERENCE
1. D. R. Heath-Brown. Fermat's two-squares theorem.
Invariant (1984) 3-5."
----------------------------------------------------------------------
Below are some further references on the Heath-Brown, Zagier proof.
Calame, Andre. A vieux theoreme demonstration nouvelle
http://www.abord-ch.org/sens/bulletin/no19/art2.htm
Elsholtz, Christian The The Liouville-Heath-Brown-Zagier
Proof of the Two Squares Theorem and generalizations.
http://www.math.tu-clausthal.de/~mace/papers/zagierenglish9thjuly2002.ps
Proofs from the Book gives an expanded version of the proof, see
http://google.com/groups?threadm=7tqdep%247p8%241%40nnrp1.deja.com
Shiu, P. Involutions associated with sums of two squares.
Publ. Inst. Math. (Beograd) (N.S.) 59(73) (1996), 18-30.
http://www.emis.de/journals/PIMB/073/3.html
--Bill Dubuque
Arturo Magidin
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>Herb <fuzz...@nate.com> wrote:
>>>
>>> If F = {0,1,a,b} is a field of order 4
>>>
>>> then how can I determine a+b, a*b ?
>>>
>>> I know a+b=/=a because b=/=0
>>> also, a+b=/=b since a=/=0.
>>> But I can't determine whether a+b = 0 or 1.
>>
>> Since a+a = 0, then a+b cannot also equal 0. So...
>
>Which way do you prove 2a = 0? Presumably via
>standard ring/field theory.
I thought I was only using group theory (applied to the additive group
of F)... Note I did not write 2a, but "a+a".
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>Herb <fuzz...@nate.com> wrote:
>>>>
>>>> If F = {0,1,a,b} is a field of order 4
>>>>
>>>> then how can I determine a+b, a*b ?
>>>>
>>>> I know a+b=/=a because b=/=0
>>>> also, a+b=/=b since a=/=0.
>>>> But I can't determine whether a+b = 0 or 1.
>>>
>>> Since a+a = 0, then a+b cannot also equal 0. So...
>>
>> Which way do you prove 2a = 0? Presumably via
>
> I thought I was only using group theory (applied to the
> additive group of F)... Note I did not write 2a, but "a+a".
But, out of curiosity, which result in group theory?
The involution proof I gave is also group theoretical.
Below I show it generalizes to a theorem which has as
corollary Cauchy's Group Theory Theorem (McKay's proof),
and also Fermat's little Theorem.
LEMMA. Let g be an element of a group and p be a prime
integer. If g^p = 1 then g has order either p or 1.
Proof: g^n = g^p = 1 => g^(n,p) = 1. But (n,p) = p or 1.
THEOREM Let G be a finite group of order n and let p be a prime.
Let R = #p'th roots of 1 in G: R = #{ g in G : g^p = 1 }. Then
R = n^(p-1) mod p, and R > 1 <=> p|n. [proof below]
COROLLARY 1 (Cauchy's Theorem) If a group G has order n
divisible by a prime p then G has a subgroup of order p.
Proof: p|n so the theorem implies R > 1, i.e. G has a
g != 1 with g^p = 1. The lemma implies g has order p,
so g generates a cyclic subgroup <g> of order p.
COROLLARY 2 (FlT: Fermat's little Theorem, strong form)
If p is prime and not p|n then n^(p-1) = 1 (mod p).
Proof: Apply theorem to any (e.g. cyclic) group of order n.
COROLLARY 3 Theorem => Lemma
Proof: Suppose g^p = 1, g != 1. Let n be the order of g.
Apply the theorem to the cyclic group <g> generated by g.
Since g^p = 1^p = 1, R > 1, so p|n, therefore n = p.
Finally, here is the promised proof of the main
THEOREM Let G be a finite group of order n and let p be a prime.
Let R = #p'th roots of 1 in G: R = #{ g in G : g^p = 1 }. Then
R = n^(p-1) mod p, and R > 1 <=> p|n.
Proof. Let S be the set of all p-tuples of elements from G
whose product is 1, i.e.
S = { (g1,g2,...,gp) : g1 g2...gp = 1, gi in G }
Let F be the cyclic rotation on p-tuples
F(g1,g2,...,gp) = (g2,g3,...,gp,g1)
Clearly F^p = 1, so F is a permutation on S. Recall that
a permutation F decomposes into disjoint cycles (orbits)
<F>s = {F^k s : k in Z}, being classes of the equivalence
relation s ~ t <=> s = F^k t, some k in Z. So the cycles
of F constitute a partition S = <F>s1 \/ ... \/ <F>sm
Consider the permutation F restricted to some cycle C.
Notice the order of F on C is the cycle length n of C.
But since F^p = 1, the lemma implies that n = p or 1.
So S decomposes into disjoint cycles of length p or 1.
S has n^(p-1) elements since after freely choosing the
first p-1 elements of a p-tuple in S, the last element
must be the inverse of the product of the others. Thus
|S| = n^(p-1) = Q p + R, Q = #p-cycles, R = #1-cycles
A 1-cycle has Fs = s, so s has all entries identical,
say g, so g^p = 1; i.e. g is a p'th root of 1 in G
iff g is a 1-cycle of R. Hence mod p: n^(p-1) = R
the number of p'th roots of 1 in G. If p|n then p|R.
But R > 0 since always 1^p = 1, hence R >= p > 1.
Conversely, if R > 1 then G has g != 1 with g^p = 1,
so the lemma implies g has order p. But also g^n = 1,
so p|n. QED
Note that the involution proof in my prior post is
essentially the case p = 2 of the proof of theorem.
--Bill Dubuque
Arturo Magidin
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>>Herb <fuzz...@nate.com> wrote:
>>>>>
>>>>> If F = {0,1,a,b} is a field of order 4
>>>>>
>>>>> then how can I determine a+b, a*b ?
>>>>>
>>>>> I know a+b=/=a because b=/=0
>>>>> also, a+b=/=b since a=/=0.
>>>>> But I can't determine whether a+b = 0 or 1.
>>>>
>>>> Since a+a = 0, then a+b cannot also equal 0. So...
>>>
>>> Which way do you prove 2a = 0? Presumably via
>>> standard ring/field theory. [...]
>>
>> I thought I was only using group theory (applied to the
>> additive group of F)... Note I did not write 2a, but "a+a".
>
>But, out of curiosity, which result in group theory?
The original post led me to believe the author already knew that
a+a=0; from the normal cancellation in group theory, from a+b=0 we
would deduce a=b, which would of course be false. I wasn't (at least,
not consciously) using the fact that in a field of characteristic 2,
2*x = 0 for all x.
Your derivations are of course both correct, nice, and interesting, as
usual.
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>>>Herb <fuzz...@nate.com> wrote:
>>>>>>
>>>>>> If F = {0,1,a,b} is a field of order 4
>>>>>>
>>>>>> then how can I determine a+b, a*b ?
>>>>>>
>>>>>> I know a+b=/=a because b=/=0
>>>>>> also, a+b=/=b since a=/=0.
>>>>>> But I can't determine whether a+b = 0 or 1.
>>>>>
>>>>> Since a+a = 0, then a+b cannot also equal 0. So...
>>>>
>>>> Which way do you prove 2a = 0? Presumably via
>>>> standard ring/field theory. [...]
>>>
>>> I thought I was only using group theory (applied to the
>>> additive group of F)... Note I did not write 2a, but "a+a".
>>
>> But, out of curiosity, which result in group theory?
>
> The original post led me to believe the author already knew that
> a+a=0; from the normal cancellation in group theory, from a+b=0 we
> would deduce a=b, which would of course be false. I wasn't (at least,
> not consciously) using the fact that in a field of characteristic 2,
> 2*x = 0 for all x.
How did you infer that the author knew a+a=0 from the original post?
It seems to me this is the only nontrivial piece of the problem and
requires either using standard results from group/ring/field theory
or else some direct proof such as I presented. Note it is possible
that this is an exercise posed before such standard results are
presented since otherwise the problem is utterly trivial. Also the
author needn't necessarily be familiar with the group-theoretical
versions if his algebra course is rings-first vs. groups-first.
Does anyone else know any other cute proofs that x + x = 0 in F ?
> Your derivations are of course both correct, nice, and interesting,
> as usual.
Thanks, that's very kind of you. I sometimes wonder if anyone reads
my posts since replies are rare. Now you've given an existence proof.
Hopefully there does not also exist a corresponding uniqueness proof!
--Bill Dubuque
Arturo Magidin
>>> But, out of curiosity, which result in group theory?
>>
>> The original post led me to believe the author already knew that
>> a+a=0; from the normal cancellation in group theory, from a+b=0 we
>> would deduce a=b, which would of course be false. I wasn't (at least,
>> not consciously) using the fact that in a field of characteristic 2,
>> 2*x = 0 for all x.
>
>How did you infer that the author knew a+a=0 from the original post?
To be honest, I can't recall right now. It seemed to me that the
original poster knew all the additions and multiplications except for
the ones she mentioned, for some reason. Whether that impression was
justified or not is debatable, certainly.
>It seems to me this is the only nontrivial piece of the problem and
>requires either using standard results from group/ring/field theory
>or else some direct proof such as I presented.
Fair enough. Certainly, if I had not made the (possibly unjustified)
assumption that the poster knew a+a=0, I probably would have started
from there. At which point you would have probably made the same post,
pointing out I didn't need to use whatever it was I would have
used. (-:
>> Your derivations are of course both correct, nice, and interesting,
>> as usual.
>
>Thanks, that's very kind of you. I sometimes wonder if anyone reads
>my posts since replies are rare.
There seems to be few points to reply to! I don't normally have
questions about what you do, and there's seldom anything for my to
add. I assume the same is true for others who read them.
Certainly it is a bit... healthy for my potential ego... to have
pointed out to me so many times that I keep swatting flies with
cannonballs, but I certainly hope you don't stop doing so.
Gerry Myerson
mag...@math.berkeley.edu (Arturo Magidin) wrote:
> In article <y8zllfc...@nestle.csail.mit.edu>,
> Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
> >Thanks, that's very kind of you. I sometimes wonder if anyone reads
> >my posts since replies are rare.
>
> There seems to be few points to reply to! I don't normally have
> questions about what you do, and there's seldom anything for my to
> add. I assume the same is true for others who read them.
What he said.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
David Hartley
<w...@nestle.csail.mit.edu> writes
>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>>>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>>>>>Herb <fuzz...@nate.com> wrote:
>>>>>>>
>>>>>>> If F = {0,1,a,b} is a field of order 4
>>>>>>>
>>>>>>> then how can I determine a+b, a*b ?
>>>>>>>
>>>>>>> I know a+b=/=a because b=/=0
>>>>>>> also, a+b=/=b since a=/=0.
>>>>>>> But I can't determine whether a+b = 0 or 1.
>>>>>>
>>>>>> Since a+a = 0, then a+b cannot also equal 0. So...
>>>>>
>>>>> Which way do you prove 2a = 0? Presumably via
>>>>> standard ring/field theory. [...]
>>>>
>>>> I thought I was only using group theory (applied to the
>>>> additive group of F)... Note I did not write 2a, but "a+a".
You can't prove it using only group theory, as it's not true in every
group of order 4.
>>> But, out of curiosity, which result in group theory?
>>
>> The original post led me to believe the author already knew that
>> a+a=0; from the normal cancellation in group theory, from a+b=0 we
>> would deduce a=b, which would of course be false. I wasn't (at least,
>> not consciously) using the fact that in a field of characteristic 2,
>> 2*x = 0 for all x.
>
>How did you infer that the author knew a+a=0 from the original post?
>It seems to me this is the only nontrivial piece of the problem and
>requires either using standard results from group/ring/field theory
>or else some direct proof such as I presented. Note it is possible
>that this is an exercise posed before such standard results are
>presented since otherwise the problem is utterly trivial. Also the
>author needn't necessarily be familiar with the group-theoretical
>versions if his algebra course is rings-first vs. groups-first.
>
>Does anyone else know any other cute proofs that x + x = 0 in F ?
Here's a proof from first principles, (but not cute).
Lemma. In any group, if c and d are not the identity, then c*d is not c
or d.
Proof. Let g be the group-inverse of c, and e the identity. If c*d=c,
then e = g*c = g*(c*d) = (g*c)*d = e*d = d ...
Applying this lemma to the multiplicative group {1,a,b} gives
immediately that ab=1.
Applying it to the additive group F, a+1 must be 0 or b. If a+1=0 then
a+1 = 0 = 0.b = (a+1)b = ab+b = b+1
and so a=b. This is not so, hence a+1=b. Similarly, b+1=a.
But this implies a+b+1+1=a+b, and so 1+1=0.
This implies x+x=0 for any x in F and, to answer the original question,
that a+b=1.
--
David Hartley
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>Herb <fuzz...@nate.com> wrote:
>>>
>>> If F = {0,1,a,b} is a field of order 4
>>>
>>> then how can I determine a+b, a*b ?
>>>
>>> I know a+b=/=a because b=/=0
>>> also, a+b=/=b since a=/=0.
>>> But I can't determine whether a+b = 0 or 1.
>>
>
> Here's a proof from first principles, (but not cute).
>
> Lemma. In any group, if c and d are not the identity, then c*d is not
> c or d.
>
> Proof. Let g be the group-inverse of c, and e the identity. If c*d=c,
> then e = g*c = g*(c*d) = (g*c)*d = e*d = d ...
>
> Applying this lemma to the multiplicative group {1,a,b} gives
> immediately that ab=1.
It's simpler to show there's only one possible value for -1.
a != b, ab = 1 => -1 isn't a or b (or 0) so -1 = 1. QED
Now we're done, the rest of the proof below is unneeded.
--Bill Dubuque
> Applying it to the additive group F, a+1 must be 0 or b.
> If a+1=0 then a+1 = 0 = 0.b = (a+1)b = ab+b = b+1 so a=b.