# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="kevinatilusa"]Ah, I was reading your argument as taking "1" to be the "1" in the additive group instead of the multiplicative one. If we let `1` be the generator for the additive group, the argument goes through I think, since 3*2=(`1`+`1`+`1`)(`1`+`1`)=`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`=0 regardless of whether `1`*`1`=0 or not, since anything added to itself 6 times gives 0. For the other question, [spoiler]The integers mod 3 and the integers mod 5 give you two of the domains. For the other one, we have to work a little bit harder. Suppose there is such a domain. What are the two groups? The additive group has order 4, so is either Z_4 or Z_2xZ_2. The former is impossible, since we would (by the same argument) have 2*2=(`1`+`1`)(`1`+`1`)=0. In the latter case, let's call the elements 0,1,a,b. The additive table looks like: + 0 1 a b 0 0 1 a b 1 1 0 b a a a b 0 1 b b a 1 0 For the multiplicative table, we also have little choice, since the 0 and 1 rows and columns are decided, and there's only one way to fill in the remainder to avoid repeats in the columns * 0 1 a b 0 0 0 0 0 1 0 1 a b a 0 a b 1 b 0 b 1 a A good bit of checking shows this works. [/spoiler] Random comments and technical stuff about the above: [spoiler]Another way of constructing the size 4 domain is to take the polynomials with integer coefficients mod 2, and then mod out by x^2+x+1 (whenever we have a quadratic term or higher, we replace x^2 by -(x+1) which equals x+1 since we're working mod 2). Therefore (for example) (x+1)(x+1)=x^2+2x+1=x^2+1=(x+1)+1=x. I picked x^2+x+1 for two reasons: First to get the right number of elements (2 possibilities for the constant term, 2 for the x coefficient, and we cancel out the rest). Secondly, x^2+x+2 doesn't factor mod 2. What this means is that if (x^2+x+2) divides a product of two things (i.e. if the product of those two things is 0 once we mod out) then it had to divide one of the original things (i.e one of our original things was 0 after modding out). This irreducibility guaranteed that we got an integral domain. The same technique works for any power of a prime. If I want to construct an integral domain of size p^k, what I do is take the polynomials mod p, then mod out by some kth degree polynomial which doesn't factor. What I'm left with is the polynomials with coefficients between 0 and p-1, and at most k coefficients, of which there are exactly p^k. As long as I can find a polynomial of degree k which does not reduce mod p, this construction will give an integral domain. For example, x^3+x+1 doesn't factor mod 5 (if it did, one of the factors would be linear and would correspond to a root of the polynomial, which it doesn't have). Therefore if we take the polynomials mod 5 and mod out by x^3+x+1, we get an integral domain with 125 elements. [/spoiler][/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Antrax
Posted: Wed Jul 07, 2004 12:24 pm    Post subject: 1

Whoops. I used the multiplication table (with elements 0,1,a,b) to prove that it can't be done
Antrax
kevinatilusa
Posted: Wed Jul 07, 2004 12:16 pm    Post subject: 0

Ah, I was reading your argument as taking "1" to be the "1" in the additive group instead of the multiplicative one. If we let `1` be the generator for the additive group, the argument goes through I think, since 3*2=(`1`+`1`+`1`)(`1`+`1`)=`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`+`1`*`1`=0 regardless of whether `1`*`1`=0 or not, since anything added to itself 6 times gives 0.

For the other question,
The integers mod 3 and the integers mod 5 give you two of the domains. For the other one, we have to work a little bit harder.

Suppose there is such a domain. What are the two groups? The additive group has order 4, so is either Z_4 or Z_2xZ_2. The former is impossible, since we would (by the same argument) have 2*2=(`1`+`1`)(`1`+`1`)=0. In the latter case, let's call the elements 0,1,a,b. The additive table looks like:

+ 0 1 a b
0 0 1 a b
1 1 0 b a
a a b 0 1
b b a 1 0

For the multiplicative table, we also have little choice, since the 0 and 1 rows and columns are decided, and there's only one way to fill in the remainder to avoid repeats in the columns

* 0 1 a b
0 0 0 0 0
1 0 1 a b
a 0 a b 1
b 0 b 1 a

A good bit of checking shows this works.

Another way of constructing the size 4 domain is to take the polynomials with integer coefficients mod 2, and then mod out by x^2+x+1 (whenever we have a quadratic term or higher, we replace x^2 by -(x+1) which equals x+1 since we're working mod 2). Therefore (for example) (x+1)(x+1)=x^2+2x+1=x^2+1=(x+1)+1=x.

I picked x^2+x+1 for two reasons: First to get the right number of elements (2 possibilities for the constant term, 2 for the x coefficient, and we cancel out the rest). Secondly, x^2+x+2 doesn't factor mod 2. What this means is that if (x^2+x+2) divides a product of two things (i.e. if the product of those two things is 0 once we mod out) then it had to divide one of the original things (i.e one of our original things was 0 after modding out). This irreducibility guaranteed that we got an integral domain.

The same technique works for any power of a prime. If I want to construct an integral domain of size p^k, what I do is take the polynomials mod p, then mod out by some kth degree polynomial which doesn't factor. What I'm left with is the polynomials with coefficients between 0 and p-1, and at most k coefficients, of which there are exactly p^k. As long as I can find a polynomial of degree k which does not reduce mod p, this construction will give an integral domain. For example, x^3+x+1 doesn't factor mod 5 (if it did, one of the factors would be linear and would correspond to a root of the polynomial, which it doesn't have). Therefore if we take the polynomials mod 5 and mod out by x^3+x+1, we get an integral domain with 125 elements.
Antrax
Posted: Wed Jul 07, 2004 10:44 am    Post subject: -1

Actually, I think the shortening isn't valid. Nobody said "1" is the 1 in Z6. The multiplication could be defined such that 3="1" (for example, a*b=1/3*a*b. Obviously this wouldn't work, but just as an example).
Antrax
Antrax
Posted: Wed Jul 07, 2004 10:40 am    Post subject: -2

kevinatilusa, I was walking on eggshells, having never seen something like this. I really didn't want to make a leap that wasn't mathematically valid, so I just wrote out everything.
Here's another question from the same test, the other non-trivial question:
4)
d) Can there be an integral domain of size 3, 4, 5? Prove.

Antrax
kevinatilusa
Posted: Wed Jul 07, 2004 6:04 am    Post subject: -3

Looks fine, but your weak step can be shortened considerably:
If we made Z_6 into an integral domain, it would still have the additive structure of Z_6, so 1+1=2, not 0.
Antrax
Posted: Tue Jul 06, 2004 11:37 pm    Post subject: -4

Incorrect. Proof: If Z6 becomes an integral domain, it has a "1". Consider the expression ("1"+"1")*("1"+"1"+"1"). By the distributive rule we get "1"*"1"+"1"*"1"+"1"*"1"+"1"*"1"+"1"*"1"+"1"*"1"="1"+"1"+"1"+"1"+"1"+"1".

Here is the first possibly weak step:
This is equivalent to a^6 in the regular (Z6,+), and since 6 is the order of Z6, it means 1+1+1+1+1+1=0.
So we found a multiplication of two things from the ring that gives off zero. Now we'll prove neither of them is zero.
Let's suppose "1"+"1"=0. Then we get 2+2=2*"1"+2*"1"=0. But 2+2=4, contradiction. Similarily 1+1+1 can't be zero, QED.

I strongly doubt this is correct. Where are my errors, and what is the right proof?
Antrax
Antrax
Posted: Tue Jul 06, 2004 11:32 pm    Post subject: -5

From my Modern Algebra final:

4)
e) Prove/disprove: A multiplication can be defined on Z6 such that it becomes an integral domain.

It was a "new" question (meaning nothing similar was ever used on a test), so I'm not sure if I got it right. I showed it to Lili and she didn't solve it in two seconds, so I'm assuming it's of SOME interest.
Antrax