probability in algebra

**ymar** · November 25th 2011, 03:00 AM

I'm not sure that this is the right place to post my question, but other places don't seem right either.

While dealing with a certain highly irregular algebraic structure with two operations, say $\circ$ and $\square,$ and a partial order, say $\leq,$ I was trying to find any relation between the two operations. An obvious guess was the distributive property but it's not there. I thought I would try the following property

$a\circ(b\square c)\leq (a\circ b)\square (a\circ c).$

It turns out it doesn't hold for all $a,b,c$ either. However, I wrote a program to see how many of all possible triples $(a,b,c)$ satisfy the above formula. It seems, experimentally, that most of them do. The structure is unambiguously given by its size $n$ . It seems to me that for $n$ approaching infinity the probability of the formula being satisfied for random $a,b,c$ diverges to 1, quite quickly at that. I haven't proven it and I don't know if it isn't well beyond my skills, but this is not why I'm writing this.

I found the idea of a structure "almost having" a property (in this probabilistic sense) intriguing. I would be interested to know if you have encountered any research in this direction. Do people do this? Is it useful?

**Swlabr** · January 5th 2012, 05:55 AM

Originally Posted by ymar

I'm not sure that this is the right place to post my question, but other places don't seem right either.

While dealing with a certain highly irregular algebraic structure with two operations, say $\circ$ and $\square,$ and a partial order, say $\leq,$ I was trying to find any relation between the two operations. An obvious guess was the distributive property but it's not there. I thought I would try the following property

$a\circ(b\square c)\leq (a\circ b)\square (a\circ c).$

It turns out it doesn't hold for all $a,b,c$ either. However, I wrote a program to see how many of all possible triples $(a,b,c)$ satisfy the above formula. It seems, experimentally, that most of them do. The structure is unambiguously given by its size $n$ . It seems to me that for $n$ approaching infinity the probability of the formula being satisfied for random $a,b,c$ diverges to 1, quite quickly at that. I haven't proven it and I don't know if it isn't well beyond my skills, but this is not why I'm writing this.

I found the idea of a structure "almost having" a property (in this probabilistic sense) intriguing. I would be interested to know if you have encountered any research in this direction. Do people do this? Is it useful?

Yes, they do. It is not uncommon to prove that a result "almost always" holds. Just go to the arXiv and search for "almost all" in your favourite topic! (Best to just search the titles or abstracts thought...)

For example, almost all one-relator groups with more than two generators are residually finite. The people who proved this actually showed that something like 98% of one-relator groups with more than two generators are residually finite. Now, it is "well-known" (for a suitable value of "well") that not all one-relator groups are residually finite. Famously, the group $\langle a, b; b^{-1}a^2b=a^3\rangle$ is not residually finite (because it doesn't have a weaker property: it isn't Hopfian), and if you know enought about all this stuff you can quite easily see that $\langle a, b, c; b^{-1}a^2b=a^3\rangle$ is not residually finite. So, you have a result which says "almost all one-relator groups with more than two generators are residually finite, but some are not". Which is, holistically speaking, very nice.

Their proof of the 98% was quite neat. A one-relator group is a group of the form $\langle X; W\rangle$ where $W$ is a word over the alphabet $X$ . This word $W$ defines a walk in $X$ -dimensional space (if you assume, without loss of generality, that every letter in $X$ appears in $W$ ), and so the authors proved that if you take a random walk it "almost always" has a specific property which implies that the corresponding group is residually finite (they proved that words which define a certain type of walk yield groups which are "ascending HNN-extensions of free groups"). The paper is by Mark Sapir and Iva Spakulova.

(A group is residually finite if for any $1\neq g\in G$ there exists a homomorphism $\phi_g:G\rightarrow H$ where $H$ is some finite group, such that $g\phi\neq 1$ ( $1$ denotes the itentity). For instance, $\mathbb{Z}$ is residually finite (here, $0$ denotes the identity), as taking $n$ an arbitrary integer then it is mapped to $-1\neq 0$ modulo $n+1$ . It is a rather strong finiteness condition.)

**ymar** · January 5th 2012, 06:19 AM

Great example, thanks!

Is the set of all words over $X$ an algebraic structure in this context? I know we can concatenate words but does it make any sense to do this when we are talking about relators? (I encounter the word "relator" some two days ago for the first time and I haven't tried to understand what it means yet. I only know they provide an alternative way of denoting structures obtained from free structures by imposing relations on the generators.)

**Swlabr** · January 5th 2012, 06:34 AM

Originally Posted by ymar

Great example, thanks!

Is the set of all words over $X$ an algebraic structure in this context? I know we can concatenate words but does it make any sense to do this when we are talking about relators? (I encounter the word "relator" some two days ago for the first time and I haven't tried to understand what it means yet. I only know they provide an alternative way of denoting structures obtained from free structures by imposing relations on the generators.)

It is complicated, because of the many pitfalls which lie en-route, and others will explain it better. You might want to take a peek at the book "combinatorial group theory" by Magnus, Karrass and Solitar.

Basically, you take the alphabet $X$ and you take a second alphabet, called $X^{-1}$ , with $|X|=|X^{-1}|$ , and you pair off elements. If $a\in X$ then there is some element in $X^{-1}$ which we shall denote be $a^{-1}$ . Basically, $X$ is our set of generators, and $X^{-1}$ is the set of inverses of our generators. Then, if you take the set of all words over these two alphabets (a star, I believe it is called the Kleen star, is used to denote this - write this as $(X\cup X^{-1})^{\ast}$ ) you can define a group by setting the words $aa^{-1}$ and $a^{-1}a$ are equal to the identity element, for all $a\in X$ . You operation is concatenation of words.

So, $aba\cdot a^{-1}ba=aba^{-1}aba=abba=ab^2a$ .

You have to be careful at this point. I have eliminated the word $aa^{1-}$ here, but what is to say this is well-defined?!? There is stuff to prove, talking about equivalence classes of words and such like, but it is proven in most books which cover infinite group theory, and certainly any book which covers presentations of groups.

So, what I have defined above is the free group over $X$ . This has presentation $\langle X;\rangle$ - there are no relators. If I add a set of relators (a set of words in the free group over $X$ ), $R$ say, then this is equivalent to taking the least normal subgroup containing the set $R$ . This always exists, and is unique, and is defined formally by intersecting all the normal subgroups containing the set $R$ . It is often denoted by $\langle\langle R\rangle\rangle$ .

Problems arise when you want to know "is a given word $W$ in $\langle\langle R\rangle\rangle$ ?", a question which is insoluble in general (it is called "the word problem for groups").

Also, there are two things, relators and relations. They are essentially the same. A relator is just a word, $b^{-1}a^2ba^{-3}$ , but a relation has an equals sign in it, $b^{-1}a^2b=a^3$ . If you take the right-hand side of the relation over to the left hand side to get $b^{-1}a^2ba^{-3}=1$ , then just chop off the $=1$ and you'll see that they're just different ways of writing the same thing.

**ymar** · January 5th 2012, 06:35 AM

Ah, OK. I've just read a Wikipedia article that explained to me what a relator is. So it's not defined for all kinds algebraic structures but just for groups.

**ymar** · January 5th 2012, 06:43 AM

Originally Posted by Swlabr

It is complicated, because of the many pitfalls which lie en-route, and others will explain it better. You might want to take a peek at the book "combinatorial group theory" by Magnus, Karrass and Solitar.

...

Problems arise when you want to know "is a given word $W$ in $\langle\langle R\rangle\rangle$ ?", a question which is insoluble in general (it is called "the word problem for groups").

Thank you very much. I need to take a good look at these things. I've been looking at Derek Robinson's book on group theory. There is something about it there.

**Swlabr** · January 5th 2012, 06:44 AM

Originally Posted by ymar

Ah, OK. I've just read a Wikipedia article that explained to me what a relator is. So it's not defined for all kinds algebraic structures but just for groups.

Well...I'm not sure about that. I think presentations exist for rings, and certainly they exist for semigroups and monoids (you do what I did above, but forget about the inverse alphabet. For monoids, you put in an identity element by hand). They should exist for anything which has a free object. Free groups exists, free monoids, free semigroups...I'm pretty sure about free rings. So you just take your relators to be all the elements of your ideal or whatever. They might be of the form a+b^2, but it is still a relator...

However, there is no such thing as a "free field". So I don't think you can get a field presentation.

**Swlabr** · January 5th 2012, 06:48 AM

Originally Posted by ymar

Thank you very much. I need to take a good look at these things. I've been looking at Derek Robinson's book on group theory. There is something about it there.

Yes, there is. I like his book very much. To link in with my earlier post, he proves in his book that if a group is residually finite it is Hopfian. He proves this at the bottom of p165 on my copy, at the end of section 6.1. The group $\langle a, b; b^{-1}a^2b=a^3\rangle$ is non-Hopfian, so it cannot be residually finite.

**ymar** · January 5th 2012, 06:49 AM

Originally Posted by Swlabr

Well...I'm not sure about that. I think presentations exist for rings, and certainly they exist for semigroups and monoids (you do what I did above, but forget about the inverse alphabet. For monoids, you put in an identity element by hand). They should exist for anything which has a free object. Free groups exists, free monoids, free semigroups...I'm pretty sure about free rings. So you just take your relators to be all the elements of your ideal or whatever. They might be of the form a+b^2, but it is still a relator...

However, there is no such thing as a "free field". So I don't think you can get a field presentation.

I know there are free semigroups and free monoids, and that you can make new ones by adding relations, but what would relators mean there? In semigroups many congruences are not given by any substructures -- there is no good analogue of normal subgroups.

**Swlabr** · January 5th 2012, 07:01 AM

Originally Posted by ymar

I know there are free semigroups and free monoids, and that you can make new ones by adding relations, but what would relators mean there? In semigroups many congruences are not given by any substructures -- there is no good analogue of normal subgroups.

Ah, sorry, you are right. Relators do not exist in the same way. I mean, they do for monoids, but not every monoid can be defined this way (I presume), but they definitely don't exist for semigroups...(I should explain that although I pointed out the difference between relator and relation above they occupy the same niche in my mind, and I only know the difference as I have a post-it note on the wall in front of my desk which reminds me of the difference...)

Thread: probability in algebra

LinkBack

Thread Tools

Display

probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Re: probability in algebra

Similar Math Help Forum Discussions

Algebra 2 probability question

terminology about ring/algebra in abstract algebra and measure theory

Help with high school algebra problem (some probability)

Very useful maths tutorial website from algebra,probability to calculas

sigma algebra and probability problem

Search Tags