Is English trivial?
Moderators: jestingrabbit, Moderators General, Prelates
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Is English trivial?
Let G be the free group on the 26 letters az. Consider the quotient of G by the following relations:
1) For any letter [imath]\tau[/imath], the relation [imath]\tau=\tau^{1}[/imath]. (So wood=wd and bookkeeper=bper.)
2) For any pair of synonyms 'foo', 'bar', the relation foo=bar. (So large=big.)
Is the resulting group trivial?
1) For any letter [imath]\tau[/imath], the relation [imath]\tau=\tau^{1}[/imath]. (So wood=wd and bookkeeper=bper.)
2) For any pair of synonyms 'foo', 'bar', the relation foo=bar. (So large=big.)
Is the resulting group trivial?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Oculus Vespertilionis
 Posts: 434
 Joined: Thu Jun 04, 2009 7:42 pm UTC
Re: Is English trivial?
Is this problem just intended for the really mathknowledgeable?
I'm going to try to figure out what you're asking.
So, what is meant by "the free group on the 26 letters az?" Is this every possible finite combination of letters?
And, if so, then wouldn't "big = large" imply that members of this group can be written in more than one nontrivial way? Because that seems to go against the definition of a "free group".
I'm going to try to figure out what you're asking.
Wikipedia wrote:In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses (disregarding trivial variations).
So, what is meant by "the free group on the 26 letters az?" Is this every possible finite combination of letters?
And, if so, then wouldn't "big = large" imply that members of this group can be written in more than one nontrivial way? Because that seems to go against the definition of a "free group".
You do what you can to make relationships and to respect yourself and others. Everything else is bookkeeping.
 MartianInvader
 Posts: 782
 Joined: Sat Oct 27, 2007 5:51 pm UTC
Re: Is English trivial?
This is the coolest puzzle I've seen in a long, long, time.
I'll try to explain a bit for the nonmathknowledgeable. We're looking at all finite strings of letters, including the "empty string", which I'll call "". We're allowed to make replacements for synonyms, so for example, "bigot" could become "largeot", or "rate" could become "rconsumed". We can also add in or delete pairs of the same letter next to each other, for example, "genesis" can become "oogenesis" or "fall" can become "fa". If there's two strings and we can get from one to the other, we can also move letters from the end of one to the end of the other (or from beginning to beginning) and use those as replacements as well. For example, since "big" = "large", "ig" = "blarge", "i" = "blargeg", and "blargegi" = "", the empty string.
The question is: Can we get from any string of letters to the empty string? One way to do this is to show that we can get from each single letter to the empty string, since then we can take any string and use those replacements to delete one letter at a time.
Skeptical: Do you have a solution in mind, or is this more of a "be creative" thread?
Some thoughts:
I'll try to explain a bit for the nonmathknowledgeable. We're looking at all finite strings of letters, including the "empty string", which I'll call "". We're allowed to make replacements for synonyms, so for example, "bigot" could become "largeot", or "rate" could become "rconsumed". We can also add in or delete pairs of the same letter next to each other, for example, "genesis" can become "oogenesis" or "fall" can become "fa". If there's two strings and we can get from one to the other, we can also move letters from the end of one to the end of the other (or from beginning to beginning) and use those as replacements as well. For example, since "big" = "large", "ig" = "blarge", "i" = "blargeg", and "blargegi" = "", the empty string.
The question is: Can we get from any string of letters to the empty string? One way to do this is to show that we can get from each single letter to the empty string, since then we can take any string and use those replacements to delete one letter at a time.
Skeptical: Do you have a solution in mind, or is this more of a "be creative" thread?
Some thoughts:
Spoiler:
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Is English trivial?
You can also add or subtract arbitrary letters to the beginning or end of both sides of an equation. For instance:
good = great > ood = reat
large = huge > lar = hu
nail = tack > snail = stack
good = great > ood = reat
large = huge > lar = hu
nail = tack > snail = stack
Re: Is English trivial?
Building off of the above two posts:
EDIT: Some more.
MORE EDIT:
EVEN MORE EDIT:
Spoiler:
EDIT: Some more.
Spoiler:
MORE EDIT:
Spoiler:
EVEN MORE EDIT:
Spoiler:
Re: Is English trivial?
I remember solving a similar problem for extra credit for my Linear Algebra class, except that homophones, rather than synonyms, were equal, and there wasn't that fact that each letter has order two. I think homophones is easier since one can cancel many individual letters pretty quickly.
My result was:
My result was:
Spoiler:
 MartianInvader
 Posts: 782
 Joined: Sat Oct 27, 2007 5:51 pm UTC
Re: Is English trivial?
This was a very cool puzzle. Here's my solution:
Hmm, apparently I can't nest spoiler tags, or I'd spoiler each letter separately inside my solution. As it is, revealing the following spoiler will show the entire solution:
Hey! This puzzle stole a couple hours of my life, and I want them back!
Hmm, apparently I can't nest spoiler tags, or I'd spoiler each letter separately inside my solution. As it is, revealing the following spoiler will show the entire solution:
Spoiler:
Hey! This puzzle stole a couple hours of my life, and I want them back!
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Is English trivial?
MartianInvader wrote:Skeptical: Do you have a solution in mind, or is this more of a "be creative" thread?
Well, I solved this puzzle with a bunch of math undergrads on Friday. (I can't claim credit for it by the way  one of the undergrads proposed it.) It's a lot easier when you have about 15 people working in parallel to try to find useful relations; I think it took us about 20 minutes. So I knew the answer (in some respects it's obvious, see spoiler), but of course it's the type of problem where no two people trying to solve it will ever find exactly the same solution.* I was expecting a solution of the sort you produced.
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Is English trivial?
When I proposed this problem to a friend yesterday, he referred me to #5 here. (For those who can't access JSTOR, the problem is to find the center of G modulo the relation that for any English anagrams xyzzy and zyxyz, xyzzy~zyxyz. So for instance ab=ba, since able=bale.)
I'm tempted to have a go at it, despite its being unsolved.
I'm tempted to have a go at it, despite its being unsolved.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Is English trivial?
I'm assuming only singleword anagrams are allowed? Otherwise I'd be pretty confident that Z(G/anagrams)=G/anagrams. As it is, I'm guessing that
Here's a list of letters that commute with a. I'm using words from the morewords.com word list since it's easily searchable, and trying to use more common words when possible:
Spoiler:
Here's a list of letters that commute with a. I'm using words from the morewords.com word list since it's easily searchable, and trying to use more common words when possible:
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Is English trivial?
skeptical scientist wrote:Here's a list of letters that commute with a.
Here's one more:
Spoiler:
Re: Is English trivial?
And another:
Spoiler:
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

 Posts: 1459
 Joined: Fri Apr 20, 2007 3:27 pm UTC
 Location: The Tower of Flints. (Also known as: England.)
Re: Is English trivial?
Another few:
Spoiler:
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
dubsola
dubsola
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Is English trivial?
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Is English trivial?
Spoiler:

 Posts: 165
 Joined: Wed Apr 11, 2007 10:17 am UTC
Re: Is English trivial?
Cosmologicon wrote:Spoiler:
Spoiler:
Re: Is English trivial?
Cosmologicon wrote:Spoiler:
Spoiler:
Re: Is English trivial?
About q:
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Is English trivial?
Using the morewords.com word list,
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Is English trivial?
If you guys want to seriously attack this problem, I'd suggest setting up a google doc with a 26x26 spreadsheet just as in the original article with a proof of commutativity in each entry as you find it.
Re: Is English trivial?
With regards to the homophone alternative that aleph_one mentioned:
Spoiler:
Re: Is English trivial?
That is a really fun puzzle! I haven't looked too much at the anagram one, but the synonym one made me miss my subway stop (and a couple thereafter before I noticed!)
I'm not going to go through the entire process I used, but I'll outline my strategy:
Anyway, thanks for the great puzzle!
I'm not going to go through the entire process I used, but I'll outline my strategy:
Spoiler:
Anyway, thanks for the great puzzle!
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Who is online
Users browsing this forum: No registered users and 8 guests