Is English trivial?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Is English trivial?

Postby skeptical scientist » Fri Jun 26, 2009 10:18 pm UTC

Let G be the free group on the 26 letters a-z. 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?
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

User avatar
Oculus Vespertilionis
Posts: 434
Joined: Thu Jun 04, 2009 7:42 pm UTC

Re: Is English trivial?

Postby Oculus Vespertilionis » Sat Jun 27, 2009 3:23 pm UTC

Is this problem just intended for the really math-knowledgeable?
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 a-z?" 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.

User avatar
MartianInvader
Posts: 796
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Is English trivial?

Postby MartianInvader » Sat Jun 27, 2009 4:15 pm UTC

This is the coolest puzzle I've seen in a long, long, time.

I'll try to explain a bit for the non-math-knowledgeable. 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:
I'd consider "a" and "an" to be synonyms, so right off the bat we get that "n" = "". I'm gonna play with this a bit more.

Do British/American spellings count as synonyms? (i.e. "color" = "colour") :)
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Is English trivial?

Postby Cosmologicon » Sat Jun 27, 2009 4:37 pm UTC

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

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Is English trivial?

Postby Buttons » Sat Jun 27, 2009 6:50 pm UTC

Building off of the above two posts:
Spoiler:
We also have sail=tack (more or less), so sail=nail, thus s=n="".

Can we knock more letters down? It would be especially convenient if we had e equal to the identity as well.

EDIT: Some more.
Spoiler:
Also, inflammable=flammable, so i=in="" as well.

s being the identity helps a lot. For instance, man=guy=guys=men, so a=e=m. This also yields am=is="", which we already knew.

MORE EDIT:
Spoiler:
And since ill=off, o is also the identity. With s, n, i, and o, we can start building more and more trivial words and finding their synonyms. son = scion = c, so c is trivial. mom=mum, so u is trivial.

EVEN MORE EDIT:
Spoiler:
Ah, here we go. entitle=title, so en=e is trivial, as are a and m. So we've got a bunch of trivial letters now: aeioucmns. The rest should be easy, I suspect.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Is English trivial?

Postby aleph_one » Sat Jun 27, 2009 9:53 pm UTC

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:
Spoiler:
All letters are the identity, except possibly v, which has no relations, as confirmed by searching through a list of homophones.

User avatar
MartianInvader
Posts: 796
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Is English trivial?

Postby MartianInvader » Sat Jun 27, 2009 11:31 pm UTC

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:

Spoiler:
The group is trivial. Here's the letter-by-letter calculation (each will rely on the previous letters being trivial, and I use "" to mean the empty string):

n: a=an => n = ""
i: flammable=inflammable => "" = in => "" = i
e: pig = hog => p = ho => pho = ""
phone = call => e = ca
noon = midday => nn = miay => "" = may = can = ca = e
a:phone = call => pho = "" (from previous ca = e = "") => o = ph
cap=hat => "" = phat => "" = oat => ot = a
see=spot => "" = pot => "" = pa = dad => dd = a => "" = a
c:(from previous) ca = e => c = ""
p:(from previous) pa = "" => p = ""
m: ma = mama => m = mm => m = ""
y: (from preivous)may = "" => y = ""
o: mama = mom => "" = o
r: cry=yell=> cry = y => cr = "" => r = ""
v: mobile = movable => bl = vbl => "" = v
h: phone=call => h = ""
t: cap=hat => "" = t
b: party=celebrate => " = lb => l = b
celibate = abstinent => lb = b => "" = b
l: (from previous) l=b => l = ""
g: divine = godly => d = gd = > "" = g
d: dog=canine => d = ""
s: step = pace => s = ""
u: rump = rear => u = ""
f: face = countenance => f = ""
j: jump = hop => j = ""
k: slay = kill => "" = k
w: weep=cry => w = ""
x: exit = leave => x = ""
z: zealous = fervent => z = ""
q: ubiquitous = everywhere => q = ""


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!

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Is English trivial?

Postby skeptical scientist » Sun Jun 28, 2009 2:14 pm UTC

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:
Assuming the puzzle is solvable, the solution kind of has to be "English is trivial", because it's easy to imagine a proof that English is just trivial: just find enough relations to show that each letter individually is the identity. However, trying to prove English is not trivial seems hopeless; the standard way would be to find an invariant, but to prove an invariant one would need to check every single pair of synonyms in English, and even if such an invariant existed, it would seem very hard to guess, and one would certainly require a computer to check it.

*Since the number of solutions far exceeds the number of people who will ever attempt it.

Interestingly, the first two pairs of synonyms we came up with were also a=an and flammable=inflammable.
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

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Is English trivial?

Postby Buttons » Sun Jun 28, 2009 3:30 pm UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Is English trivial?

Postby skeptical scientist » Sun Jun 28, 2009 8:08 pm UTC

I'm assuming only single-word anagrams are allowed? Otherwise I'd be pretty confident that Z(G/anagrams)=G/anagrams. As it is, I'm guessing that
Spoiler:
by examining all anagrams involving q, j, x, and z, and assuming all other pairs of letters commute, you can find all strings which might commute with those four letters. Then you can prove that those strings do commute with q, z, x, and z, and also commute with every other letter, and so generate the center. Anyone want to write a program to find all one-word anagrams involving one of those four letters? I'm guessing it's not too long a list.


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:
ab=ba (able=bale)
ac=ca (cat=act)
ad=da (add=dad)
ae=ea (fete=feet => et=te; eat=ate => eat=aet => ea=ae) - remember that it's sometimes easier to prove a relation in more than one step.
af=fa (aft=fat)
ah=ha
ai=ia (lair=liar)
ak=ka (akin=kain)
al=la (calm=clam)
am=ma
an=na (sang=snag)
ao=oa (gaol=goal)
ap=pa (apt=pat)
ar=ra (rat=art)
as=sa (asp=sap)
at=ta (feat=feta)
au=ua (gaun=guan)

missing:
g, j, q, v-z
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

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Is English trivial?

Postby Buttons » Sun Jun 28, 2009 8:44 pm UTC

skeptical scientist wrote:Here's a list of letters that commute with a.

Here's one more:
Spoiler:
hose=hoes => se=es; gas=sag; ages=sage=gase=gaes => ag=ga.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Is English trivial?

Postby Token » Mon Jun 29, 2009 1:19 pm UTC

And another:

Spoiler:
raj = jar
ajar = raja = jara = jaar
aj = ja
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Is English trivial?

Postby Ended » Mon Jun 29, 2009 8:41 pm UTC

Another few:
Spoiler:
aves = vase
hose=hoes => se=es
av = va

wan = awn
aw = wa

aye = yea
ea=ae => aye=yae
ay = ya

[obscure words warning!]
azole = zoeal
ae=ea, ao=oa => azole = zaoel
pale=peal
ae=ea => pale=pael => le=el
az = za

Missing: q, x
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Is English trivial?

Postby skeptical scientist » Tue Jun 30, 2009 12:48 am UTC

Spoiler:
coxa=coax => ax=xa. We still need q. Lists of single-word anagrams containing j, q, x, and z would be immensely useful. Anyone?

Also, if anyone can show that a and q commute, we'll know that the center is nontrivial.
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

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Is English trivial?

Postby Cosmologicon » Tue Jun 30, 2009 4:45 am UTC

Spoiler:
How is it possible to show that q commutes with anything if it's never not followed by u?

LLCoolDave
Posts: 165
Joined: Wed Apr 11, 2007 10:17 am UTC

Re: Is English trivial?

Postby LLCoolDave » Tue Jun 30, 2009 5:32 am UTC

Cosmologicon wrote:
Spoiler:
How is it possible to show that q commutes with anything if it's never not followed by u?


Spoiler:
There are a few obscure words, the only anagram I found so far is maquis and umiaqs, not sure yet if that helps in any way at all.

fyjham
Posts: 240
Joined: Wed Nov 21, 2007 1:16 am UTC

Re: Is English trivial?

Postby fyjham » Tue Jun 30, 2009 5:50 am UTC

Cosmologicon wrote:
Spoiler:
How is it possible to show that q commutes with anything if it's never not followed by u?

Spoiler:
http://en.wikipedia.org/wiki/List_of_English_words_containing_Q_not_followed_by_U

Now we just need one that's an anagram... probably start with the ones where the word actually contains u ;)

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Is English trivial?

Postby Nitrodon » Tue Jun 30, 2009 9:50 am UTC

About q:
Spoiler:
If a letter can be proven to commute with both u and qu, then it also commutes with q.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Is English trivial?

Postby skeptical scientist » Tue Jun 30, 2009 12:36 pm UTC

Using the morewords.com word list,
Spoiler:
q and z do not commute, so the group is non-abelian. Searching *z*q* matches only 8 words, "bezique", "beziques", "cazique", "caziques", "mezquit", "mezquite", "mezquites", and "mezquits", and none of them have one-word anagrams (in the morewords.com word list). In fact, by searching for words that contain at least 2 of the letters j, q, x, and z, it can easily be shown that no pair of those letters commutes. I didn't check any other letter pairs, but I suspect that this method can easily be used by hand until we reach sufficiently common letters that checking all words for anagrams by hand will take too long. Sometimes it's much faster to check one direction than the other: *x*z* matches 114 words, but *z*x* matches only 6.
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

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Is English trivial?

Postby t0rajir0u » Tue Jun 30, 2009 9:05 pm UTC

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.

Tiax
Posts: 53
Joined: Wed Aug 29, 2007 3:22 pm UTC

Re: Is English trivial?

Postby Tiax » Wed Jul 01, 2009 4:00 am UTC

With regards to the homophone alternative that aleph_one mentioned:

Spoiler:
V can be solved with the extremely questionable alternate pronunciation of "Veldt" as "felt".

http://www.merriam-webster.com/dictionary/veldt

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is English trivial?

Postby mike-l » Fri Jul 03, 2009 5:04 pm UTC

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:

Spoiler:
Obviously getting a = 0 is the best outcome you can get for a single letter, I found a couple of these but not too many. A couple I found after the fact: (par)t = (even)t = party, so y = 0, and 0 = boob = tit so i = 0.

Next best would be ab = 0, meaning a and b are interchangeable. Ultimately I had 4 trivial letters, 18 letters equal to each other, then got everything trivial with wonder=ponder. With 22 letters it's easy to nab the last 4.

Even getting ab = 0 is difficult at the start, but pretty easy is getting abc = 0. This is convenient since it means a, b, and c commute (only true when each has order 2). Mainly I found a lot of these, and anytime 2 letters overlapped between 2 triplets, we get a pair ab=0.


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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 3 guests