Is English Abelian?
rickO
being worked on by some of the graduate students and research fellows
in their spare time.
Consider the free group W generated by all the letters a to z (only a
to z, no accents, etc.) Now define the equivalence E using u ~ v [E]
iff u and v are English words (Standard American English spelling;
proper nouns excluded!) AND are permutations of each other.
(If you'd rather, replace Standard American English with British. But
don't mix the spellings.)
Examples
- tea = ate = eat
- boer <> bore since Boer is in fact a proper noun
- theater <> theatre since theatre is the British spelling.
Conjecture: The quotient group W/E is abelian
As a start: ore = roe => or = ro
This is of course not the kind of problem that brings fame or fortune.
Does anybody know whether or not it's been solved?
This has been bugging me for decades :-)
Rick
George Cox
>
> When I was still taking mathematics seriously, there was a conjecture
> being worked on by some of the graduate students and research fellows
> in their spare time.
>
> Consider the free group W generated by all the letters a to z (only a
> to z, no accents, etc.) Now define the equivalence E using u ~ v [E]
> iff u and v are English words (Standard American English spelling;
You'll need to define "English word", perhaps by specifying a
dictionary.
> proper nouns excluded!) AND are permutations of each other.
> (If you'd rather, replace Standard American English with British. But
> don't mix the spellings.)
>
> Examples
> - tea = ate = eat
> - boer <> bore since Boer is in fact a proper noun
> - theater <> theatre since theatre is the British spelling.
>
> Conjecture: The quotient group W/E is abelian
> As a start: ore = roe => or = ro
>
> This is of course not the kind of problem that brings fame or fortune.
>
> Does anybody know whether or not it's been solved?
>
> This has been bugging me for decades :-)
>
> Rick
--
G.C.
Note ANTI, SPAM and invalid to be removed if you're e-mailing me.
David Eppstein
George Cox <george_...@SPAMbtinternet.com.invalid> wrote:
I searched the official scrabble dictionary and found no anagrams
involving the following letter pairs:
bq fq gq hz jq jv jw jx jz kx pz qv qw qx qz uz vx vz xz yz
That is, there are no two words that are anagrams of each other and both
contain the two letters 'b' and 'q'. So, b and q do not commute in W/E.
In addition, the following letter pairs have some anagrams, but the two
letters appear in the same order in each anagram:
bx cj dq fj fx fy fz gj gx gz hq jk jl jn jp js jy kq kz mq qy wz
E.g. b and x both appear in the anagrams boxwood, woodbox, but in no
other anagrams, and in these two they appear in the same order.
So again, there is no way to commute these letter pairs.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Arturo Magidin
I don't think this follows just yet.
For bq to equal qb in W/E, you need the non-English "word"
q^{-1}b^{-1}qb to lie in the normal subgroup generated by all elements
of the form uv^{-1}, where u ~ v [E].
That is: q and b commute in W/E if and only if there exist English
words u_1,....,u_n, v_1,....,v_n, and elements g_1,...,g_n of the free
group W, such that
(1) for i=1,...,n, u_i ~ v_i [E] (i.e., u_i is an anagram of
v_i and neither are proper nouns);
and
(2) qb = bq* (u_i*v_i^{1})^{g_1}*...*(u_n*v_n^{-1})^{g_n}
in W,
where (u_i*v_i^{-1})^g_i = g_i^{-1}*u_i*v_i^{-1}*g_i
Now, you say that there are no words u and v such that u ~ v [E] and
both u and v contain the letters q and b. But as you can see from the
expression above, it may be possible to derive a commutation using the
other relations.
(or easier: c, s, and z are all interchangeable, by considering
defense~defence, which implies s~c; and realize~realise, which implies
z~s; so if you could find a word that involves c, q, and b, and
another word which is an anagram of this, provided you replace c with
s, then you could perhaps use those to obtain a relation between b and
q, even though there need not be a specific word that does not require
such substitution).
>In addition, the following letter pairs have some anagrams, but the two
>letters appear in the same order in each anagram:
> bx cj dq fj fx fy fz gj gx gz hq jk jl jn jp js jy kq kz mq qy wz
>E.g. b and x both appear in the anagrams boxwood, woodbox, but in no
>other anagrams, and in these two they appear in the same order.
>So again, there is no way to commute these letter pairs.
Again, you forgot that the elements of the normal subgroup generated
by E do not consist only of the elements u*v^{-1} with u and v
anagrams of each other...
--
======================================================================
"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
Robert Israel
rickO <rick...@yahoo.com> wrote:
>Consider the free group W generated by all the letters a to z (only a
>to z, no accents, etc.) Now define the equivalence E using u ~ v [E]
>iff u and v are English words (Standard American English spelling;
>proper nouns excluded!) AND are permutations of each other.
>(If you'd rather, replace Standard American English with British. But
>don't mix the spellings.)
>Examples
> - tea = ate = eat
> - boer <> bore since Boer is in fact a proper noun
> - theater <> theatre since theatre is the British spelling.
Except that seer = sere => er = re => boer=bore etc.
>Conjecture: The quotient group W/E is abelian
>As a start: ore = roe => or = ro
I doubt that q commutes with x, for example.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
David Eppstein
mag...@math.berkeley.edu (Arturo Magidin) wrote:
> >I searched the official scrabble dictionary and found no anagrams
> >involving the following letter pairs:
> > bq fq gq hz jq jv jw jx jz kx pz qv qw qx qz uz vx vz xz yz
> >That is, there are no two words that are anagrams of each other and both
> >contain the two letters 'b' and 'q'. So, b and q do not commute in W/E.
>
> I don't think this follows just yet.
>
> For bq to equal qb in W/E, you need the non-English "word"
> q^{-1}b^{-1}qb to lie in the normal subgroup generated by all elements
> of the form uv^{-1}, where u ~ v [E].
>
> That is: q and b commute in W/E if and only if there exist English
> words u_1,....,u_n, v_1,....,v_n, and elements g_1,...,g_n of the free
> group W, such that
>
> (1) for i=1,...,n, u_i ~ v_i [E] (i.e., u_i is an anagram of
> v_i and neither are proper nouns);
>
> and
>
> (2) qb = bq* (u_i*v_i^{1})^{g_1}*...*(u_n*v_n^{-1})^{g_n}
> in W,
>
> where (u_i*v_i^{-1})^g_i = g_i^{-1}*u_i*v_i^{-1}*g_i
>
> Now, you say that there are no words u and v such that u ~ v [E] and
> both u and v contain the letters q and b. But as you can see from the
> expression above, it may be possible to derive a commutation using the
> other relations.
Let BQ be the free group generated by b and q alone, and map W to BQ by
mapping all other letters to zero; similarly map W/E to BQ/E_{BQ}, where
E_{BQ} is formed by zeroing out (that is, deleting) every letter other
than b or q from every anagram pair in E.
The search I performed shows that E_{BQ} has no relations with both b
and q in it. Since every relation x=y in E is an anagram, the only
possible remaining relations are trivial ones of the form b^i=b^i or
q^j=q^j. So, BQ/E_{BQ}=BQ, a noncommutative free group on two
generators. Since W/E maps surjectively onto a noncommutative group, it
is itself noncommutative.
> (or easier: c, s, and z are all interchangeable, by considering
> defense~defence, which implies s~c; and realize~realise, which implies
> z~s;
defense-defence and realize-realise are not anagrams, and the poster
explicitly said only American spelling is allowed.
> so if you could find a word that involves c, q, and b, and
> another word which is an anagram of this, provided you replace c with
> s, then you could perhaps use those to obtain a relation between b and
> q, even though there need not be a specific word that does not require
> such substitution).
But I already said there are no anagram pairs involving b and q. So a
fortiori there are no anagram pairs involving c, q, and b. I don't see
how replacement of letters is allowed in the original poster's
formulation.
Arturo Magidin
Ah. Thanks.
>> (or easier: c, s, and z are all interchangeable, by considering
>> defense~defence, which implies s~c; and realize~realise, which implies
>> z~s;
>
>defense-defence and realize-realise are not anagrams, and the poster
>explicitly said only American spelling is allowed.
Oops. You're absolutely right here. My mistake. Yeah: every word in E
must have exponent-sum equal to 0 for each letter, so you certainly
cannot obtain equivalences which are not "anagrams" (including
negative exponents to the letters, anyway).
rickO
Thank you David and Arturo!
Somehow it's comforting to know that Scrabble can be used to solve
problems in group theory.
Now I can sleep easier ... and I won't even think about the other
related question (which letters are in the center)
Rick
David Moews
As far as I know, this conjecture has not been resolved. For an earlier
discussion of this problem, you can look at a thread on rec.puzzles
with subject `Group Theory' around 2000-VII-5
(<http://www.google.com/groups?th=f4e81b4978008f4b>).
--
David Moews dmo...@xraysgi.ims.uconn.edu
Richard Sabey
> In article <48b15538.04040...@posting.google.com>,
> rickO <rick...@yahoo.com> wrote: <some snippage>
> |Consider the free group W generated by all the letters a to z (only a
> |to z, no accents, etc.) Now define the equivalence E using u ~ v [E]
> |iff u and v are English words (Standard American English spelling;
> |proper nouns excluded!) AND are permutations of each other.
> |(If you'd rather, replace Standard American English with British. But
> |don't mix the spellings.)
> |
>
> As far as I know, this conjecture has not been resolved. For an earlier
> discussion of this problem, you can look at a thread on rec.puzzles
> with subject `Group Theory' around 2000-VII-5
> (<http://www.google.com/groups?th=f4e81b4978008f4b>).
Andrew Bremner wrote up his progress on this problem in "An Abelian
Alphabet", published, under the pseudonym Bernard E. M. Wren, in
"Word Ways", May 1994, pp. 120-122. He had been working on it far
earlier than that: some time in the spring of 1982, he gave a
talk to the Archimedeans (the Cambridge University maths society)
called something like "Fun in the Alveary", where he presented
his work on this problem and others. Already by that time he'd
proved that all letter-pairs commute, with 11 possible exceptions,
and had unearthed anagrams for some tricky cases, e.g.
px phoneboxes xenophobes
which he didn't accept because he hadn't found "phonebox" in
any dictionary.
See http://www.wordways.com/ for more on this excellent word play quarterly.
He managed to prove that any 2 letters commute, with just 6
possible exceptions: jx, kq, qw, qx, vx, xz.
Here's how Andrew Bremner solves some of David Eppstein's difficult cases:
bq basque quebas
fq fique queif
gq gasquine queasing
hz hazel zelah
jq jaques quasje
jv javar vajra
jw jewis wijse
jz jiz zij
kx boxwork workbox
pz phiz ziph
qv queven venque
uz chuze zuche
vz veze zeve
yz phytozoa zoophyta
I'd be interested to learn of David Eppstein's anagrams for the
following letter pairs. Andrew Bremner has found suitable anagrams,
but in each case at least one word is obscure (to me, at least):
cz fj fv fx fz jk ju jy nx qy ux wx wz
--
Richard Sabey Visit the r.p.crosswords competition website
cryptic_fan at hotmail.com http://www.rsabey.pwp.blueyonder.co.uk/rpc/