From:           gls@odyssey.ATT.COM (Col. G. L. Sicherman)
Subject:        Re: sylver coinage
Date:           1 Jun 89 18:51:28 GMT

Update to Sylver Coinage:  I just stumbled over Guy's "Unsolved Problems"
column for December 1987.  A researcher named Francis Voelkle has been
coming down hard on the problem with a VAX 8600.  He found (as I did)
that {10,12,18}, {10,16,24}, and {12,15,18} are all "P."

So there are fewer gaps to fill in the table....

From:           gls@odyssey.att.com (Col. G. L. Sicherman)
Subject:        monsters in sylver coinage
Date:           5 Mar 90 15:18:53 GMT
Organization:   Jack of Clubs Precision Instruments Co.

I've been doing some Sylver Coinage computations -- on slow micros
and an even slower mini.  I've been getting nowhere with certain
non-ender generators.  If anybody has some reasonably fast hardware,
I'd appreciate knowing about these positions:

    {6,22,38} - 4 is obviously a good reply; does there exist
            a good _odd_ reply?  If so, it's greater
            than 446.
    {8,30,34,52} - if there's a good reply, it's greater than
            214.
    {14,18,26,38} - if there's a good reply, it's greater than
            222.

It's known that {8,34,36} is P (in Guy's terminology), but I have
not yet found answers to {8,34,36,54} or {8,34,36,62}.  Can anybody
help?

Explanation:  In Sylver Coinage, two players take turns picking a
number.  The loser is the first to pick 1 or a number expressible
as a sum of some previously picked numbers, with repetitions.  The
game was invented by J. H. Conway and named after J. J. Sylvester.

-:-
    "Never invite a Warpsmith to dinner."

From:           gls@odyssey.att.com (Col. G. L. Sicherman)
Newsgroups:     sci.math
Subject:        postscript to monsters
Date:           9 Mar 90 14:31:55 GMT

Since my previous posting, I have found that 469 is a winning move in
{6,22,38}.  There may be others.  Anyway, {6,22,38,469} certainly
qualifies as a monster, overshadowing even {10,14,26,293}.

-:-
    "And a forest grows up
       From the dirt on the floor..."

                --F. Zappa, "It Just Might Be a One-Shot Deal"

Newsgroups:     sci.math,rec.puzzles
From:           gls@hrcms.ATT.COM (Col. G. L. Sicherman)
Subject:        Sylver Coinage news
Organization:   F. K. Dingy & Son
Date:           Tue, 8 Feb 1994 02:16:07 GMT

It has occurred to me that I shall never get around to publishing my
1991 paper on Sylver Coinage, so I may as well offer it to the Net.
If you'd like a copy, drop me a line at gls@hrcms.ATT.COM, specifying
LaTeX or PostScript.

What is Sylver Coinage?  It's a two-player game of coining money.
On your turn you must coin a denomination that cannot be expressed
as a sum (with repetitions) of previous denominations.  For instance,
if nickels and dimes have already been coined, you may not coin
quarters, since nickels and dimes suffice to make up 25 cents.
The players who coins "1" loses.  (Otherwise the first player would
say "1" and win at once.)  Of course all denominations must
be positive integers.  The game was invented by J. H. Conway, so
naturally you'll find a chapter on it in _Winning Ways._

Every game of Sylver Coinage must end, because ... well, I'll let you
figure out why.

The body of knowledge about Sylver Coinage consists of a few
remarkable general theorems, some empirical results for certain
game positions, a lot of plausible conjectures (most of them
disproven), and some simple positions that have not been solved
but would very much like to be!  My paper provides a couple of
new (and minor) general results, and plenty of new empirical results.

-:-
    "'PATAGEOMETRY: The study of those mathematical properties
     that remain invariant under brain transplants."
-- 
Col. G. L. Sicherman
gls@hrcms.ATT.COM

Newsgroups:     sci.math
From:           gls@hrcms.att.com (The Pied Typer)
Subject:        news of Sylver Coinage?
Organization:   Save the Monopoles Foundation
Date:           Thu, 19 Oct 1995 14:25:37 GMT

Has anybody turned up new results in Sylver Coinage since my 1991
paper?  I recently searched up to 4,000 without finding an odd win 
in {8,26,30}, and have confirmed most of my old results, but that's
about it.  It would be nice to hear of a solution to {8,30,34}....

-:-
     'PATAGEOMETRY: The study of those mathematical properties
     that remain invariant under brain transplants.
-- 
Col. G. L. Sicherman
gls@hrcms.ATT.COM

Newsgroups:     sci.math
From:           gls@hrcms.att.com (The Dangling Conversationalist)
Subject:        Re: Sylver Coinage - {10,26,44} is N
Organization:   The Ned Stokes Cabal
Date:           Thu, 26 Oct 1995 04:49:03 GMT

I have a new result in Sylver Coinage:

    {10,26,44} [2383]

So far as I know, this is the highest known winning move in a small position.
The previous record was {14,26,32} [1513].

I would appreciate hearing from anybody who can confirm or contradict the
new result.

-:-
    She was now working with fourteen pairs at once, and Alice couldn't
    help looking at her in great astonishment.  "How _can_ she knit with so
    many?" the puzzled child thought to herself.  "She gets more and more
    like a porcupine every minute!"

    "Can you row?" the Sheep asked, handing her a pair of knitting
    needles as she spoke.

                --Lewis Carroll, _Through the Looking-Glass_
-- 
Col. G. L. Sicherman
gls@hrcms.ATT.COM

Newsgroups:     sci.math
From:           gls@hrcms.att.com (A deaf heart, a loose liver)
Subject:        Sylver Coinage - {8,26,30} has an odd winning move
Organization:   Kentucky Fried Fox
Date:           Tue, 5 Dec 1995 02:57:14 GMT

I've just pulled another thorn in the analysis of {8}:

    {8,26,30}   [12,4363]

This increases our hope of solving {8,30,34}.

It would be a comfort if some bright mathematics programmer set about
to confirm these results (or add to them!).  So far as Richard Nowakowski
(the Keeper of the Sylver) knows, nobody is working on Sylver Coinage but
me.

You can still get my 1991 paper, in TeX, PostScript, or paper, by writing me.
It has not appeared in print and probably never will.

-:-
    K   Cobalt's metal, hard and shining,
        Cobol's wordy and confining.
        KOBOLDS topple when you strike them--
        Don't feel bad, it's hard to like them.

                    --The Roguelet's ABC
-- 
Col. G. L. Sicherman
gls@hrcms.ATT.COM

From:           gls@hrcms.att.com (World's Largest Leprechaun)
Newsgroups:     sci.math
Subject:        Sylver Coinage: {8,30,34} is N
Date:           19 Feb 1996 00:41:45 GMT
Organization:   Save the Monopoles Foundation

In J. H. Conway's game of Sylver Coinage, the position {8, 30, 34} is
"N"; that is, the next player can obtain a winning position.  The unique
winning move is 49337.

This completes the open second-order analysis of {8}.

-:-
        `Where be the Parable you normally 'ave on your
    shoulder, Large John?' Asks Blind Jew looking up.
        `Never ye mind' reponds Large John `And anyways
    where be your white stick?'
        `'Ow the 'ell should I know when oi can't see?'

                --John Lennon In His Own Write
-- 
Col. G. L. Sicherman
gls@hrcms.ATT.COM

From:           sicherman@lucent.com (The Hobgoblin of the Net)
Newsgroups:     sci.math
Subject:        Late News of Sylver Coinage
Date:           19 Jun 1996 20:00:16 GMT
Organization:   Save the Dodoes Foundation

I have written a sequel to my 1991 paper about Sylver Coinage.
It contains results since 1991, mostly from 1995 and 1996, and
is probably the last paper I will write on the subject.

If you'd like a copy, write for one, specifying LaTeX, PostScript,
or paper.

-:-
    'PATAGEOMETRY:  The study of those mathematical properties
     that remain invariant under brain transplants.
-- 
Col. G. L. Sicherman
sicherman@lucent.com

From:           mathwft@math.canterbury.ac.nz (Bill Taylor)
Date:           29 Feb 2000 04:10:20 GMT
Newsgroups:     sci.math,sci.logic,rec.games.abstract
Subject:        Sylver Coinage - a constructivist conundrum?

This essay is really to ask a certain question about constructivism,
and constructive proofs.  But it also provides a handy place to mention
the game "Sylver Coinage".

My musing began when Keith Ramsay made a nice distinction between
*construcive* solutions to math questions, and *explicit* solutions. 
For the most part, the latter are special cases of the former, whereby you
actually *produce* a "closed formula" (whatever that may be in context).
Whereas a constructive solution need only be a recipe whereby you can
show that you could *get* an explicit solution if you wanted to. It seems
to me that the distinction between explicit and constructive is a good one.

And in fact, as we've discussed before, constructive but non-explicit
solutions can often arise in some contexts, particularly finite games,
which most mathematicians would call NON-constructive solutions, even though
they are automatically constructive solutions via finiteness, just not very
very helpful ones!  Classic cases are Hex, where the usual strategy-stealing
method proves First has a winning strategy; and Chomp on a finite
rectangle, where the corner-stealing argument does likewise.  
These proofs are constructive (in the technical logic sense), 
while being totally non-explicit.

Now I want to ask about unbounded-length games.  Not *too* infinite,
or we'll get into far too much of a mess, but not too *finite* either,
or the usual constructive-by-finiteness proof will be easily extendible
to the full game.  For example; consider Nim, but where First picks a bunch
of pile numbers, and then Second gets to decide who makes the first play
in the nimming part of the game.    Though this "you cut I'll choose"
starting mechanic is often a good way to nullify first-move advantage,
it doesn't here, obviously.  One can easily prove (in the usual way) that
Second has a winning strategy; and this proof is constructive, even though
the length of the game is unbounded.  Because the game is bounded after
the first choice is made, it's just a one-quantifier extension of 
the standard finite game, and so easily constructivised.

So that's not nearly unbounded enough.

Now we come to "Sylver Coinage", a fascinating game discussed at great
length in the bible - "Winning Ways", by Berlekamp, Conway and Guy.

In turn, each player picks a natural number, which must not be a sum of
(any positive number of) previous picks.  And it is illegal to pick 1;
plural numbers only.   You lose if you can't make any pick.

So if First picks 2, or 3, then Second can pick the other, and now as
all plurals are a sum of 2's and 3's, First can't move, and thus loses.
So First might pick 4, then second better not pick 2 or 3,  just as
before; but neither should he pick 5, or First will pick 11, cutting
out all numbers except 2,3 and 6,7, and whatever Second does now First
can match with its mate.

In general, we can play the game with any finite combination of starting
numbers already "picked" on the table.  The bible notes that the game is
unsolved in general, even though some starting positions are known to be
losers, and some winners.  The bible also notes that a solution can be
proven to exist, even though it may not be "writable down" in some sense.

One of the nice things about this game, is that it is not only unbounded,
but the first moves can be played such that it is *still* unbounded.
It is unboundedly unbounded, as they put it.  Not only that, but also
the first *unboundedly many* moves can be played so that it is *still* 
unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly 
that as well, and unboundedly *that*, and so on unboundedly...
in very ordinal-like fashion.

Nonetheless there *are* starting move sequences which *do* lead to
bounded length tail games, such as the {4,5,11} above, and it was
shown by Sylvester that eventually any choice sequence *must* lead
to this situation, and that any actual play of the game *must* end.
It's in honor of Sylvester that they give it the name, and "coinage"
because it is very neatly presented as a coinage denomination problem.
SYLver Coinage is a neat witty mis-spelling of the type so common in
the bible; though I think they missed a trick by not calling it
"Sylver COYnage", on the grounds that the players very commonly start
by coyly dancing around picking very factorful numbers, before slowly
getting to grips with more nearly co-prime ones, whence it soon ends.

So the game is a play-finite one; just incredibly well unbounded.

Now, we come to my constructivist query.  I'll put on the same simple
"you cut I'll choose" starting condition, and see what we get.

Let First choose any finite starting set of picks, for the start position;
then let Second choose who will be the first player to start the adding
of new numbers alternately one at a time.  Then they play out the game
in the standard manner.

This new game has an OBVIOUS stratgey-stealing proof that it is a win
to player Second!  And yet, I believe this is a non-constructive proof,
and one that cannot be simply made constructive, (unlike the unbounded
Nim above).    Not yet, anyway.

Note that this "cut-&-choose" version is not constructively unsolved
merely because of the unboundedness, nor even subsequently because of
the unexplicitness of the standard game - for just consider "cut-&-choose"
2-dimensional Chomp, which is also largely lacking explicit solutions:-

(A) In this, the first player chooses a finite jagged rectangle as
    the starting position, and Second chooses who'll be starter. I think
    that this is easily constructively proved winnable by Second.

(B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved
    to be a win to Second, I suspect.  Just classically so.

Am I right in these last two comments?
Would some constructivist expert please tell me?

If so, it is intriguing that essentially the same proof can be regarded
constructively in one case but not in the other, even though both games
are finite but unbounded!

-------------------------------------------------------------------------------
        Bill Taylor                    W.Taylor@math.canterbury.ac.nz
-------------------------------------------------------------------------------
        MATH:-     The discovery, clarification and rigorous study of
              precise relationships in number, pattern, and structure.
-------------------------------------------------------------------------------

From:           ikastan@uranus.uucp (Ilias Kastanas)
Date:           29 Feb 2000 18:40:23 GMT
Newsgroups:     sci.math,sci.logic,rec.games.abstract
Subject:        Re: Sylver Coinage - a constructivist conundrum?

In article <89fgrc$lar$1@cantuc.canterbury.ac.nz>,
Bill Taylor <mathwft@math.canterbury.ac.nz> wrote:
@This essay is really to ask a certain question about constructivism,
@and constructive proofs.  But it also provides a handy place to mention
@the game "Sylver Coinage".

    What??  You are not interested in bending Time to get an
excluded-middle proof that Space does not exist, Bill?

@My musing began when Keith Ramsay made a nice distinction between
@*construcive* solutions to math questions, and *explicit* solutions. 
@For the most part, the latter are special cases of the former, whereby you
@actually *produce* a "closed formula" (whatever that may be in context).
@Whereas a constructive solution need only be a recipe whereby you can
@show that you could *get* an explicit solution if you wanted to. It seems
@to me that the distinction between explicit and constructive is a good one.
@
@And in fact, as we've discussed before, constructive but non-explicit
@solutions can often arise in some contexts, particularly finite games,
@which most mathematicians would call NON-constructive solutions, even though
@they are automatically constructive solutions via finiteness, just not very
@very helpful ones!  Classic cases are Hex, where the usual strategy-stealing
@method proves First has a winning strategy; and Chomp on a finite
@rectangle, where the corner-stealing argument does likewise.  
@These proofs are constructive (in the technical logic sense), 
@while being totally non-explicit.
@
@Now I want to ask about unbounded-length games.  Not *too* infinite,
@or we'll get into far too much of a mess, but not too *finite* either,
@or the usual constructive-by-finiteness proof will be easily extendible
@to the full game.  For example; consider Nim, but where First picks a bunch
@of pile numbers, and then Second gets to decide who makes the first play
@in the nimming part of the game.    Though this "you cut I'll choose"
@starting mechanic is often a good way to nullify first-move advantage,
@it doesn't here, obviously.  One can easily prove (in the usual way) that
@Second has a winning strategy; and this proof is constructive, even though
@the length of the game is unbounded.  Because the game is bounded after
@the first choice is made, it's just a one-quantifier extension of 
@the standard finite game, and so easily constructivised.

    Seems to be the same situation as Chomp (choose-a-rectangle),
or nxn Hex.

    Or checkers...  Go...  You know. Trivial games.

@So that's not nearly unbounded enough.
@
@
@Now we come to "Sylver Coinage", a fascinating game discussed at great
@length in the bible - "Winning Ways", by Berlekamp, Conway and Guy.
@
@In turn, each player picks a natural number, which must not be a sum of
@(any positive number of) previous picks.  And it is illegal to pick 1;
@plural numbers only.   You lose if you can't make any pick.
@
@So if First picks 2, or 3, then Second can pick the other, and now as
@all plurals are a sum of 2's and 3's, First can't move, and thus loses.
@So First might pick 4, then second better not pick 2 or 3,  just as
@before; but neither should he pick 5, or First will pick 11, cutting
@out all numbers except 2,3 and 6,7, and whatever Second does now First
@can match with its mate.
@
@In general, we can play the game with any finite combination of starting
@numbers already "picked" on the table.  The bible notes that the game is
@unsolved in general, even though some starting positions are known to be
@losers, and some winners.  The bible also notes that a solution can be
@proven to exist, even though it may not be "writable down" in some sense.

    Yes.   Think of the reals, w^w, as runs of Sylver Coinage.  If
a finite integer sequence  s  is a win for player  I, put the basic open
neighborhood  U_s ={reals extending  s}  into  A; likewise if  s  breaks
the rules and it was  II  who first broke them.  So  A  is an open set,
and the game an open game.  (Indeed, by Sylvester, the corresponding
set  B  for  II  is  A's complement, i.e. the game is clopen).  Now we
appeal to the theorem  "for any set  X, open games on  X^w  are deter-
mined".

    So a solution (winning strategy) exists... but that's that.
Recall the well-known proof:  if  I  does not have a winning strategy
then for any move  x1  II has a reply  y1  such that from there on,
I  doesn't have a w.s.  So for any  x2  there is a  y2  that does
likewise... and so on.  This strategy for  II  is a winning one: if
x1,y1,x2,y2,...  were in  A  some initial segment would be  an  s,
and from there on  I  would have had a w.s. -- namely, any strategy.

    The non-constructiveness of this is clear.  (Indeed, the
theorem is equivalent to the full Axiom of Choice).

@One of the nice things about this game, is that it is not only unbounded,
@but the first moves can be played such that it is *still* unbounded.
@It is unboundedly unbounded, as they put it.  Not only that, but also
@the first *unboundedly many* moves can be played so that it is *still* 
@unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly 
@that as well, and unboundedly *that*, and so on unboundedly...
@in very ordinal-like fashion.
@
@Nonetheless there *are* starting move sequences which *do* lead to
@bounded length tail games, such as the {4,5,11} above, and it was
@shown by Sylvester that eventually any choice sequence *must* lead
@to this situation, and that any actual play of the game *must* end.
@It's in honor of Sylvester that they give it the name, and "coinage"
@because it is very neatly presented as a coinage denomination problem.
@SYLver Coinage is a neat witty mis-spelling of the type so common in
@the bible; though I think they missed a trick by not calling it
@"Sylver COYnage", on the grounds that the players very commonly start
@by coyly dancing around picking very factorful numbers, before slowly
@getting to grips with more nearly co-prime ones, whence it soon ends.
@
@So the game is a play-finite one; just incredibly well unbounded.
@
@
@Now, we come to my constructivist query.  I'll put on the same simple
@"you cut I'll choose" starting condition, and see what we get.
@
@Let First choose any finite starting set of picks, for the start position;
@then let Second choose who will be the first player to start the adding
@of new numbers alternately one at a time.  Then they play out the game
@in the standard manner.
@
@This new game has an OBVIOUS stratgey-stealing proof that it is a win
@to player Second!  And yet, I believe this is a non-constructive proof,
@and one that cannot be simply made constructive, (unlike the unbounded
@Nim above).    Not yet, anyway.

    Well, in the cut-and-choose version of any game  G,  I  never
has a winning strategy  (no starting position of  G  has  w.s.'s for
both sides!)...  so  cut-and-choose is determined  IFF  II  has a w.s.
for it  IFF  G is determined for every starting position.  If our proof
of the latter was non-constructive, then no wonder!...

@Note that this "cut-&-choose" version is not constructively unsolved
@merely because of the unboundedness, nor even subsequently because of
@the unexplicitness of the standard game - for just consider "cut-&-choose"
@2-dimensional Chomp, which is also largely lacking explicit solutions:-
@
@(A) In this, the first player chooses a finite jagged rectangle as
@    the starting position, and Second chooses who'll be starter. I think
@    that this is easily constructively proved winnable by Second.
@
@(B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved
@    to be a win to Second, I suspect.  Just classically so.
@
@Am I right in these last two comments?
@Would some constructivist expert please tell me?
@
@
@If so, it is intriguing that essentially the same proof can be regarded
@constructively in one case but not in the other, even though both games
@are finite but unbounded!

    (A)  is clopen (boldface Delta-0-1), like before.  Actually,
it is just  Delta-0-1 (recursive); that's easy.  (B)  seems to need
"for all m,  m  is a sum of elements from  s"... but no, no quantifier
is needed; it is enough that  s  contain  2 and 3  (and that no member
of  s  is a sum of prior ones).  So  (B)  is recursive too.

    Now general theory says that there exists a hyperarithmetical
(Delta-1-1)  w.s. ...  to do better it takes specifics.  E.g.  (A)
does have a recursive  w.s., due to the simple structure of its
Delta-0-1  set.  Establishing a recursive w.s. for (B) would need,
I imagine, some breakthrough -- something particular about the
problem.

                        Ilias

From:           ah170@FreeNet.Carleton.CA (David Libert)
Date:           1 Mar 2000 08:33:24 GMT
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

Ilias Kastanas (ikastan@uranus.uucp) writes:
> In article <89fgrc$lar$1@cantuc.canterbury.ac.nz>,
> Bill Taylor <mathwft@math.canterbury.ac.nz> wrote:
> @This essay is really to ask a certain question about constructivism,
> @and constructive proofs.  But it also provides a handy place to mention
> @the game "Sylver Coinage".
> 
> 
>    What??  You are not interested in bending Time to get an
> excluded-middle proof that Space does not exist, Bill?
> 
> 
> @My musing began when Keith Ramsay made a nice distinction between
> @*construcive* solutions to math questions, and *explicit* solutions. 
> @For the most part, the latter are special cases of the former, whereby you
> @actually *produce* a "closed formula" (whatever that may be in context).
> @Whereas a constructive solution need only be a recipe whereby you can
> @show that you could *get* an explicit solution if you wanted to. It seems
> @to me that the distinction between explicit and constructive is a good one.
> @
> @And in fact, as we've discussed before, constructive but non-explicit
> @solutions can often arise in some contexts, particularly finite games,
> @which most mathematicians would call NON-constructive solutions, even though
> @they are automatically constructive solutions via finiteness, just not very
> @very helpful ones!  Classic cases are Hex, where the usual strategy-stealing
> @method proves First has a winning strategy; and Chomp on a finite
> @rectangle, where the corner-stealing argument does likewise.  
> @These proofs are constructive (in the technical logic sense), 
> @while being totally non-explicit.

  Yes, but even these easy starting cases contain some interesting subtle
points.  HA is Heyting arithmetic, the usual axioms of PA but formulated
over intuitionistic logic.  HA does not prove all instances of Law of the
Excluded Middle but it does prove the following universally quantified
instance of LEM:

(*)   (for all x)(for all y) [ x=y or ~x=y].

  The HA proof of (*) is by a double induction on x and y: prove (*) by
induction on x, where the inductive claims proved along the way are
themselves proved by induction on y.

  I recall I once convinced myself that I could use Kripke models to show
that if we drop induction from HA, having just a theory of the
definitions of + and *, and probably even add axioms saying we have a
commutative ring, over intuitionistic logic (*) is not provable.  Indeed
the x=0 specialization of (*) is not provable.

  The proof Bill mentions of determinacy would have a base case of
terminal positions.  I think over full HA considerations like (*) above
give a version of LEM for classifications of who won, but without
induction I expect there could be difficulties about LEM failing about
who wins.  Ie loosely speaking the previous corresponds to "ambigous
numbers" that can't be recognized as =0 or ~=0, and similarly there could
be "ambiguous terminal positions" about recognizing who has won.

  Of course this isn't disagreeing with anyting Bill wrote, because
constructivism would normally be taken to include induction.  But if my
suggestion is correct, it is interesting that even at this early stage we
require some strength of induction.  (Ie, as opposed to the classical
version, were (*) and related are trivial without induction).

> @Now I want to ask about unbounded-length games.  Not *too* infinite,
> @or we'll get into far too much of a mess, but not too *finite* either,
> @or the usual constructive-by-finiteness proof will be easily extendible
> @to the full game.  For example; consider Nim, but where First picks a bunch
> @of pile numbers, and then Second gets to decide who makes the first play
> @in the nimming part of the game.    Though this "you cut I'll choose"
> @starting mechanic is often a good way to nullify first-move advantage,
> @it doesn't here, obviously.  One can easily prove (in the usual way) that
> @Second has a winning strategy; and this proof is constructive, even though
> @the length of the game is unbounded.  Because the game is bounded after
> @the first choice is made, it's just a one-quantifier extension of 
> @the standard finite game, and so easily constructivised.

  Yes, again even the constructive proof is able to "cheat" and get
limited cases of LEM, ie each terminal postion is determined.

>    Seems to be the same situation as Chomp (choose-a-rectangle),
> or nxn Hex.
> 
>    Or checkers...  Go...  You know. Trivial games.
> 
> 
> @So that's not nearly unbounded enough.
> @
> @
> @Now we come to "Sylver Coinage", a fascinating game discussed at great
> @length in the bible - "Winning Ways", by Berlekamp, Conway and Guy.
> @
> @In turn, each player picks a natural number, which must not be a sum of
> @(any positive number of) previous picks.  And it is illegal to pick 1;
> @plural numbers only.   You lose if you can't make any pick.
> @
> @So if First picks 2, or 3, then Second can pick the other, and now as
> @all plurals are a sum of 2's and 3's, First can't move, and thus loses.
> @So First might pick 4, then second better not pick 2 or 3,  just as
> @before; but neither should he pick 5, or First will pick 11, cutting
> @out all numbers except 2,3 and 6,7, and whatever Second does now First
> @can match with its mate.
> @
> @In general, we can play the game with any finite combination of starting
> @numbers already "picked" on the table.  The bible notes that the game is
> @unsolved in general, even though some starting positions are known to be
> @losers, and some winners.  The bible also notes that a solution can be
> @proven to exist, even though it may not be "writable down" in some sense.
> 
> 
> 
>    Yes.   Think of the reals, w^w, as runs of Sylver Coinage.  If
> a finite integer sequence  s  is a win for player  I, put the basic open
> neighborhood  U_s ={reals extending  s}  into  A; likewise if  s  breaks
> the rules and it was  II  who first broke them.  So  A  is an open set,
> and the game an open game.  (Indeed, by Sylvester, the corresponding
> set  B  for  II  is  A's complement, i.e. the game is clopen).  Now we
> appeal to the theorem  "for any set  X, open games on  X^w  are deter-
> mined".
> 
>    So a solution (winning strategy) exists... but that's that.
> Recall the well-known proof:  if  I  does not have a winning strategy
> then for any move  x1  II has a reply  y1  such that from there on,
> I  doesn't have a w.s.  So for any  x2  there is a  y2  that does
> likewise... and so on.  This strategy for  II  is a winning one: if
> x1,y1,x2,y2,...  were in  A  some initial segment would be  an  s,
> and from there on  I  would have had a w.s. -- namely, any strategy.
> 
>    The non-constructiveness of this is clear.  (Indeed, the
> theorem is equivalent to the full Axiom of Choice).

  Do you mean use AC to pick the  y1, y2 ... for II ?  I agree that if we
are playing over some complex index set of moves choice may be needed to
pick the yi's.  The discussion just now was stated for games over w
(omega), and this is the correct index set of plays for Bill's game.  Use
the natural well-ordering on w to pick the yi's.  Everything else in the
proof seems definable also.  So I don't see why, for example this isn't a
theorem over classical logic of ZF.

  On the other hand, there is an LEM issue about this proof that affects
an intuitionistic attempt.  Namely the division into cases about whether
or not I has a winning strategy:  ie if I wins, we are done, else
construct a w.s. for II.  The statement being LEM'd here has a real
existential quantifier (there exists a w.s. for I), so LEM can't be
readily recovered as it can be for low complexity statements like (*).

  So as I see it, there is a non-constructive aspect to this proof, but I
don't think it is related to AC.

> @One of the nice things about this game, is that it is not only unbounded,
> @but the first moves can be played such that it is *still* unbounded.
> @It is unboundedly unbounded, as they put it.  Not only that, but also
> @the first *unboundedly many* moves can be played so that it is *still* 
> @unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly 
> @that as well, and unboundedly *that*, and so on unboundedly...
> @in very ordinal-like fashion.

  I haven't read Winning Ways, so I don't know if this is discussed, but
Bill's "ordinal" comment can be made very precise.  Below Bill mentions
that Sylvester proved that each play of the game is finite.  So
consider the tree of plays of the game (positions of the game being
nodes of the tree), and impose a partial ordering on this corresponding
to "growing down":  later positions of play are deemed "smaller". 
Sylvester's finite play claim is equivalent to the claim this tree is
well-founded.  For such trees we can assign an ordinal rank to all nodes:
terminal positions are 0, and non-terminal postions are the proper sup of
their immediate successor position ranks (successors in play: predecessors
in the tree ordering).  (Proper sup: the least ordinal strictly greater
than the successor ranks).

  Then among such well-founded games, bounded games where the longest
play has exactly n moves (for n finite) are exactly those with opening
position having rank n.  Games are unbounded iff opeing rank is infinite.
Unbounded games where each first move produces a bounded position are
exactly those with opening rank omega.  Games having a maximum play of
length n leading to an unbounded position are rank w+n.  "Unboundedly
unbounded" corresponds to rank >= w*2.

  In general any countable ordinal can be realized as the rank of the top
of a well-founded tree.

  From Bill's comments above, I would guess Sylver coinage has been
claimed to be of at least rank w^w.  It would be interesting to know the
exact ordinal.

> @Nonetheless there *are* starting move sequences which *do* lead to
> @bounded length tail games, such as the {4,5,11} above, and it was
> @shown by Sylvester that eventually any choice sequence *must* lead
> @to this situation, and that any actual play of the game *must* end.
> @It's in honor of Sylvester that they give it the name, and "coinage"
> @because it is very neatly presented as a coinage denomination problem.
> @SYLver Coinage is a neat witty mis-spelling of the type so common in
> @the bible; though I think they missed a trick by not calling it
> @"Sylver COYnage", on the grounds that the players very commonly start
> @by coyly dancing around picking very factorful numbers, before slowly
> @getting to grips with more nearly co-prime ones, whence it soon ends.
> @
> @So the game is a play-finite one; just incredibly well unbounded.
> @
> @
> @Now, we come to my constructivist query.  I'll put on the same simple
> @"you cut I'll choose" starting condition, and see what we get.
> @
> @Let First choose any finite starting set of picks, for the start position;
> @then let Second choose who will be the first player to start the adding
> @of new numbers alternately one at a time.  Then they play out the game
> @in the standard manner.
> @
> @This new game has an OBVIOUS stratgey-stealing proof that it is a win
> @to player Second!  And yet, I believe this is a non-constructive proof,
> @and one that cannot be simply made constructive, (unlike the unbounded
> @Nim above).    Not yet, anyway.

  Yes I agree with this.  Proving the strategy-stealing proof works seems
to need LEM over whether the base games wins for I.  This is a complex
enough statement that we don't seem to get LEM for free.

  Of course, this LEM instance is just the statement of determinacy for
the base game.  But as discussed earlier that claim itself has LEM
difficulties.

>    Well, in the cut-and-choose version of any game  G,  I  never
> has a winning strategy  (no starting position of  G  has  w.s.'s for
> both sides!)...  so  cut-and-choose is determined  IFF  II  has a w.s.
> for it  IFF  G is determined for every starting position.  If our proof
> of the latter was non-constructive, then no wonder!...

  Yes, Illias is making the same point.

> @Note that this "cut-&-choose" version is not constructively unsolved
> @merely because of the unboundedness, nor even subsequently because of
> @the unexplicitness of the standard game - for just consider "cut-&-choose"
> @2-dimensional Chomp, which is also largely lacking explicit solutions:-
> @
> @(A) In this, the first player chooses a finite jagged rectangle as
> @    the starting position, and Second chooses who'll be starter. I think
> @    that this is easily constructively proved winnable by Second.

  Yes, even though these solutions are intractible to write out,
intuitionism can handle them with inductions over base cases of provable
LEM.  In these easy cases intuitionism can fake classical well enough,
and the harder case of Sylver coinage it seems it can't.

> @(B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved
> @    to be a win to Second, I suspect.  Just classically so.

  I would suspect so too.  Unfortunately I can only conjecture this, not
prove it.

> @Am I right in these last two comments?
> @Would some constructivist expert please tell me?

  I am no expert though.  For the first claim about Chomp I am more
confident, ie the intuitionism can do it.  For the second claim about
what intuitionism can't do, I am just agreeing that it sure looks that
way, but to really say I better call in those experts too.

> @If so, it is intriguing that essentially the same proof can be regarded
> @constructively in one case but not in the other, even though both games
> @are finite but unbounded!

  Yes.  I guess one difference is Chomp is easily provable to have rank w,
so handling it only involves inductions up to omega.  Sylver coinage has
rank well beyond omega, which contributes to the difficulties.  It forces
us to consider LEM for more complicated statements where we don't get LEM
for free.

>    (A)  is clopen (boldface Delta-0-1), like before.  Actually,
> it is just  Delta-0-1 (recursive); that's easy.  (B)  seems to need
> "for all m,  m  is a sum of elements from  s"... but no, no quantifier
> is needed; it is enough that  s  contain  2 and 3  (and that no member
> of  s  is a sum of prior ones).  So  (B)  is recursive too.
> 
>    Now general theory says that there exists a hyperarithmetical
> (Delta-1-1)  w.s. ...  to do better it takes specifics.  E.g.  (A)
> does have a recursive  w.s., due to the simple structure of its
> Delta-0-1  set.  Establishing a recursive w.s. for (B) would need,
> I imagine, some breakthrough -- something particular about the
> 
> 
>                        Ilias

  Yes.

  If the result is as we all seem to be conjecturing, we are asking for
an independence result, what intuitionism can't prove.  I would guess
this would be difficult, needing to combine the strangeness of
intuitionistic counterexamples to clasical theorems with the
technicalities of Sylver coinage.

  What sort of thing would be such a solution?  There are Kripke models,
and some other methods I think Kleene gave, using recursion theory? 
Another question is should an independence proof like this over classical
logic be acceptable, or must we have intuitionism in the meta-language
also?  I never pay much attention to this because I like classical logic
and intuitionism is just a side topic for me, so if classical logic says
so that's good enough for me.  But constructivist purists might not agree.
Come to think of it, for simple independence results is there a
conservative extension result saying it doesn't matter?

  Anyway, this whole question of independence results and intuitionistic
counterexamples raises another pet peeve of mine.  Independence results
have a different meta-mathematical flavour from simple straightforward
mathematical results.  And sure enough, in classical logic the effort to
formalize solutions along these lines have uncovered a technical
difference reflecting this intuitive difference: the independence results
must be proven from a higher consistency strength theory, or must
explictly include a consistency premise.  I think this technical version
in classical logic has brought a lot of clarity to such areas.

  Now consider how similar issues are dealt with in the intuitionistic
literature.  So called intuitionistic counterexamples, which seem to be
waffling about what is being assumed and what level of machinery is being
used.  "If we could do this we could decide whether pi has 7 9's, so we
can't do this...".  So when did you prove we can't decide pi has 7 9's? 
Ahh we can't do this intuitionistcally?  So intuitionism is consistent? 
How did you prove that, and in what level of language, since you never
bothered to specify where you were working?  Note that Godel's theorem
applies to HA.  Are they really trying to tell us intuitionism is
inconsistent?

  Anyway for me a good solution would be Kripke models or something like
that (not Brouwer's creative subject etc).  But I would be surprised if
such a solution were easy.
--
David Libert     (ah170@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad."  -- David Libert
3. "So don't be a morron."  -- Marek Drobnik bd308  rhetorical salvo IRC sig

From:           dmoews@xraysgi.ims.uconn.edu (David Moews)
Date:           2 Mar 2000 19:03:52 -0800
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

In article <89ikkk$f1u$1@freenet9.carleton.ca>,
David Libert <ah170@FreeNet.Carleton.CA> wrote:
|  I haven't read Winning Ways, so I don't know if this is discussed, but
|Bill's "ordinal" comment can be made very precise.  Below Bill mentions
|that Sylvester proved that each play of the game is finite.  So
|consider the tree of plays of the game (positions of the game being
|nodes of the tree), and impose a partial ordering on this corresponding
|to "growing down":  later positions of play are deemed "smaller". 
|Sylvester's finite play claim is equivalent to the claim this tree is
|well-founded.  For such trees we can assign an ordinal rank to all nodes:
|terminal positions are 0, and non-terminal postions are the proper sup of
|their immediate successor position ranks (successors in play: predecessors
|in the tree ordering).  (Proper sup: the least ordinal strictly greater
|than the successor ranks). ...
|
|  From Bill's comments above, I would guess Sylver coinage has been
|claimed to be of at least rank w^w.  It would be interesting to know the
|exact ordinal.

This ordinal is w^2.  For any non-starting position of Sylver Coinage, let g 
be the gcd of the numbers played.  Then there is some N such that all 
multiples of g bigger than Ng are sums of numbers already played, and you can 
induce to prove that the ordinal of the position is <= w.(g-1)+N.  So the 
ordinal of the starting position is <= w^2, and the following example play
shows it is >= w^2:

             2^m(2n+1),      2^m(2n-1),      ..., 2^m.3,     2^m,
             2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).3, 2^(m-1),
             ...
             2(2x+1),        2(2x-1),        ..., 6,         2,
              2q+3,           2q+1,          ..., 5,         3.
-- 
David Moews                                    dmoews@xraysgi.ims.uconn.edu

From:           kramsay@aol.commangled (Keith Ramsay)
Date:           06 Mar 2000 02:56:49 GMT
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

|In turn, each player picks a natural number, which must not be a sum of
|(any positive number of) previous picks.  And it is illegal to pick 1;
|plural numbers only.   You lose if you can't make any pick.

I like to think of it a little more simply as a misere form of the
game where picking 1 is allowed. In the misere form, whoever cannot
play wins, so whoever is forced to play 1 loses.

In article <89shua$mr5$1@cantuc.canterbury.ac.nz>,
mathwft@math.canterbury.ac.nz (Bill Taylor) writes:
||>  Sylver coinage has
||> rank well beyond omega, which contributes to the difficulties.  It forces
||> us to consider LEM for more complicated statements where we don't get LEM
||> for free.
|
|Yes, it seems so.  It's odd, though.  I'd have though induction over smallish
|ordinals was fairly constructive, yet it seems not. 

I guess you see "induction over ordinals" as the primary working
ingredient here. Look more carefully.

|Indeed, one *can* see
|that there might well be trouble even with a simple double induction,
|(i.e. over w^2).  If, to verify  A(n, x), you may go down to the A(n-1,  )'s
|but may have to go enormously far, to  A(n-1, huge), well, one can see why 
|a constructivist may have a problem with that.   I guess.    Maybe.

Don't think in terms of loose "trouble". Think of the specific steps
involved. We can call a position in the game "decided" if one player
or the other has a winning strategy in that position. We deduce for a
given position P that if all the "lesser" positions Q<P are decided
then P is also decided. How do we do that? Well, there is a set of
allowed moves for the player whose turn it is, each leading to one of
the lesser positions. If one of those positions Q is a winner for that
player, then of course P is as well, because the player can take that
move. On the other hand, if all of those positions are winners for the
other player, then the other player has a winning strategy (apply a
winning strategy at whichever position comes next).

Then (nonconstructively) we say, always either there exists a winning
play from P or there doesn't (and since each position which can be
moved to is decided, in that case the other player has a winning
strategy in each). Of course if there are finitely many allowed
moves, each which leads to a decided position, then P is also decided.
Clear enough? It's like the proof that all horses have the same color;
the whole problem lies with (certain cases of) the single inductive
step.

The original Sylver Coinage game is nevertheless decided; we have a
winning strategy, just not a very illuminating one. For the first
player, picking 5 is a winning move. Then when the second player
picks a number, the game is reduced to one with finitely many
remaining numbers. By a strategy-stealing argument, we know that
player 1 has a winning strategy, and needs only to do a finite search
to implement it.

...
||>   So called intuitionistic counterexamples, which seem to be   ...
||>  "If we could do this we could decide whether pi has 7 9's, so we
||> can't do this...".  So when did you prove we can't decide pi has 7 9's? 
|
|The pi things are traditional Heyting, but not of the essence, I suspect.
|The study of these counterexamples ("fickle" I think they're called) is
|fairly unimpeachable, I imagine.  A better scenario would be perhaps to say. 
|"If we could do this we could decide 
|                 whether an arbitrary TM will halt, so we can't do this..."
|That would make it much more gritty.     Even granitey.

Finding a proof that the conjecture in question implies one of the
standard assumptions known to be outside of your "modus operandi" is
more to my taste than are the examples involving pi and so on. It's
what mathematicians working nonconstructively often do when confronted
with statements which require this or that set-theoretical principle,
after all.

On the other hand, part of the point of the prosaic "counterexamples"
seems to be to make the argument more concrete, which is typically
perceived as making it "grittier". Your metaphor (the argument
becoming grittier as it becomes less concrete) seems a bit odd even to
me. I think Brouwer would have objected to the idea that we need
somehow to do more than what is required to convey the intuition, in
order to make it a more serious proof.

||>  So intuitionism is consistent? 
|
|I'm sure that there are more technical approaches now, but in Heyting's
|popularising book, intuitionism was more or less declared "obviously
|consistent", because of its model in N, which was taken to be a "mental
|given".
|That's how I dimly recall it, though no doubt I'll get a rocket from Keith
|for having completely misunderstood the whole point.  Anyway, OK, I don't
|*disagree* with them; the same reasoning tells us that PA is *obviously*
|consistent, which I'm quite happy with, on its somewhat informal level.

There are some cute remarks in Feferman's _In the Light of Logic_
about how Goedel skewered various of Hilbert's intuitions about how
these principles would relate to each other. One of Hilbert's guesses
was that the consistency of the law of excluded middle would be a much
bigger deal than it was. The fact that HA is consistent and PA can be
proven to be equiconsistent with HA has been used as a proof of the
consistency of PA. 

Going the other direction is nothing, however. If you *drop* an
assumption, *obviously* you are not going to introduce a contradiction
where none existed before.

No, if you're going to worry about the consistency of intuitionism,
you are doing one of two things: either worry also about the
consistency of classical mathematics (and there's only so much to be
done to help you there), or be concerned because of the extensions to
classical mathematics which were made by intuitionists that contradict
classical mathematics. Brouwer had his free-choice sequences, for
example. That's a whole different story. The logicians have cooked up
"interpretations" which show those are consistent if some more familiar
theoriest are consistent, although I have never been keenly interested
in this bit of tidying up.

||> Anyway for me a good solution would be Kripke models or something like
|that
|
|I keep hearing about these.  But there doesn't seem to be any reasonably
|simple intro anywhere.  Like, I mean, something along the lines of a
|Schaum series book!  I'd really like to learn about Kripke models - can 
|you make any likely suggestions?

I haven't found much use for them. It's one of those things which one
might think would help you figure out intuitionism by leveraging off
one's prior familiarity with classical mathematics, but really doesn't
seem to help much. It's more of a technical tool.

The definition should not be hard to find, and it's reasonably simple,
although I'm not sure I remember the rules correctly. You have a
partially ordered set F, and define a relationship |= between elements
of F and statements in the first-order language of some structure. You
define f|= p&q when f|= p and f|= q. You define f|= p or q when f|= p
or f|= q. You define f|= false never to hold. You define f|= p->q to
hold if for every f'>=f for which f'|=p, also f'|=q. Then you need to
have a domain of elements at each element of F in order to specify the
interpretation of the atomic statements and to define the meaning of
f|=(Ax)P(x) and of f|=(Ex)P(x).

Keith Ramsay

From:           mathwft@math.canterbury.ac.nz (Bill Taylor)
Date:           6 Mar 2000 06:11:05 GMT
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

OK then, time for me to show off my ignorance again.  Got to keep the pitbull
fed, after all.   ;-)

dmoews@xraysgi.ims.uconn.edu (David Moews) writes:

|> This ordinal is w^2. 

I didn't really follow your induction argument, and this still seems too small
to me.  Let me adjust your own example somewhat...

|>  the following example play shows it is >= w^2:
|> 
|>              2^m(2n+1),      2^m(2n-1),      ..., 2^m.3,     2^m,
|>              2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).3, 2^(m-1),
|>              ...
|>              2(2x+1),        2(2x-1),        ..., 6,         2,
|>               2q+3,           2q+1,          ..., 5,         3.

OK then, let me do the following:

 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5,   \
 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).7, 2^(m-1).5 \
   ...                                                      > all times 3^n     
 2(2x+1),        2(2x-1),        ...,14,        10,        /
 2q+3,           2q+1,           ..., 7,         5.       /

... ...

 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5,   \
 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).5, 2^(m-1).5 \
   ...                                                      > all times 3^(n-1)    
 2(2x+1),        2(2x-1),        ...,14,        10,        /
 2q+3,           2q+1,           ..., 7,         5.       /

...    ...

 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5    \
 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).7, 2^(m-1).5 \
   ...                                                      > all times 3    
 2(2x+1),        2(2x-1),        ...,14,        10,        /
 2q+3,           2q+1,           ..., 7,         5.       /

Wouldn't this give order type w^3 ?

I'm prepared to believe this example fails in some way, but I can't see
why it would be so different from your simpler one.   Please help me out.

-------------------------------------------------------------------------------
              Bill Taylor       W.Taylor@math.canterbury.ac.nz
-------------------------------------------------------------------------------
              Dr Frankenstein - the world's first body-builder.
-------------------------------------------------------------------------------

From:           dmoews@xraysgi.ims.uconn.edu (David Moews)
Date:           6 Mar 2000 14:45:39 -0800
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

In article <89vi5p$lgp$1@cantuc.canterbury.ac.nz>,
Bill Taylor <mathwft@math.canterbury.ac.nz> wrote:
|OK then, let me do the following: 
                                   [I have added some labels & changed letters]
|
| 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5,   \
| 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).7, 2^(m-1).5 \
|   ...                                                      > all times 3^N  
| 2(2x+1),        2(2x-1),        ...,14,        10,        /
| 2q+3,           2q+1,           ..., 7,         5.       /   (first group)
|
|... ...
|
| 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5,   \
| 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).5, 2^(m-1).5 \
|   ...                                                      >all times 3^(N-1)
| 2(2x+1),        2(2x-1),        ...,14,        10,        /
| 2q+3,           2q+1,           ..., 7,         5.       /  (second group)
|
|...    ...
|
| 2^m(2n+1),      2^m(2n-1),      ..., 2^m.7,     2^m.5    \
| 2^(m-1)(2p+1),  2^(m-1)(2p-1),  ..., 2^(m-1).7, 2^(m-1).5 \
|   ...                                                      > all times 3    
| 2(2x+1),        2(2x-1),        ...,14,        10,        /
| 2q+3,           2q+1,           ..., 7,         5.       /  (last group)
|
|
|Wouldn't this give order type w^3 ?

This example is not, in general, a play of Sylver Coinage.  After playing
5.3^N and 7.3^N, you will be able to exclude every multiple of 3^N that 
is >23.3^N; but either 2^m.3^(N-1).(2n+1) or 2^m.3^(N-1).(2n-1) will 
be congruent to +3^(N-1) or -3^(N-1) mod 3^N, so by taking sums of these
with 5.3^N and 7.3^N, you will be able to exclude all sufficiently large
multiples of 3^(N-1), where `sufficiently large' depends only on m, n, and N.
So the p, ..., x, q that occur in the second group will be limited in size,
and similar problems will occur in succeeding groups.

The Bible says (abridged):  ``Let g be the g.c.d. of the moves made.  Then
it's not hard to see that only finitely many multiples of g are not expressible
as sums of numbers already played.  So after at most this known number of 
moves the g.c.d. must be reduced.''

So we may associate with each position of Sylver Coinage an ordered pair
(g, N), where g is the g.c.d. of the moves made, and N is the number of
inexpressible multiples of g.  Any move from this position must either be

        an inexpressible multiple of g, taking us to (g, M), where M < N

                              or

        an x not a multiple of g, taking us to (g', P), for some P,
              where g'=gcd(g,x) is a proper divisor of g.

In either case, the ordered pair strictly decreases (in lexicographic order).
This gives the bound of w^2.

In your example, the sequence of g.c.d.s is

         2^m.3^N.(2n+1), 2^m.3^N, 2^(m-1).3^N, ..., 2.3^N, 3^N

in the first group, but when you start the second group the g.c.d. will drop
almost immediately to

         3^(N-1),

causing trouble.
-- 
David Moews                                       dmoews@xraysgi.ims.uconn.edu

From:           colonel@monmouth.com (He Comes As No Surprise)
Date:           8 Mar 2000 17:14:28 -0500
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - a constructivist conundrum?

In <20000305215649.05178.00000487@nso-cv.aol.com>, kramsay@aol.mangled wrote:
> 
> |In turn, each player picks a natural number, which must not be a sum of
> |(any positive number of) previous picks.  And it is illegal to pick 1;
> |plural numbers only.   You lose if you can't make any pick.
> 
> I like to think of it a little more simply as a misere form of the
> game where picking 1 is allowed. In the misere form, whoever cannot
> play wins, so whoever is forced to play 1 loses.

This simplifies some of the theory.  For example, W.W. defines an
end-position as a position with g=1 in which every legal move u less
than t excludes t, and a quiet end-position as the same except that
u excludes t using just one instance of u.  An equivalent (and neater)
characterization of a quiet end-position is that t is not the sum of
any two legal moves--but this holds only if 1 is legal.

I have not thought about independence proofs in Sylver Coinage, but
the material in W.W. raises a possibility of applying superdomino
theory.  In a position with g=2, the pattern of P's and N's in the
positions obtained by making an odd move must eventually cycle.  The
proof is inductive but easy to follow from the text; basically each
value can be shown to depend on a fixed number of previous values,
so the computation can be performed by a finite automaton.

For g=3 the computation is not bounded, mainly because it inducts over
modular classes 1 and 2 simultaneously.  This suggests a parallel with
one- and two-dimensional dominoes that I have no idea what to do with.

-:-
    'PATAGEOMETRY, n.  The study of those mathematical properties
    which remain invariant under brain transplants.
-- 
Col. G. L. Sicherman
home: colonel@mail.monmouth.com
work: sicherman@lucent.com
web: <http://www.monmouth.com/~colonel/>

From:           sicherman@lucent.com (The Dangling Conversationalist)
Date:           27 Apr 2000 19:09:26 GMT
Newsgroups:     sci.math
Subject:        numerical results in Sylver Coinage?

Is anybody out there doing research in Sylver Coinage?  I ask partly
because I'd like confirmation of my computed results, and partly because
there's one position {10,36,52,68} that I've computed beyond 15 million
without finding a winning move or a pattern.  If this position is "N",
the winning move is higher than any yet discovered in positions with
G.C.D. greater than one.  (The highest is 58905 in {6,34,62}.)

-:-
	One measures a circle, beginning anywhere.

					--Charles Fort
-- 
Col. G. L. Sicherman
work: sicherman@lucent.com
home: colonel@mail.monmouth.com

From:           sicherman@lucent.com (The Pied Typer)
Date:           29 Apr 2000 22:59:03 GMT
Newsgroups:     sci.math
Subject:        Re: numerical results in Sylver Coinage?

In <8ea396$3ae@nntpa.cb.lucent.com>, I wrote:
>
> there's one position {10,36,52,68} that I've computed beyond 15 million
> without finding a winning move or a pattern.

I just noticed that this position is short, which means that I could
compute it to a googolplex without finding a winning move.  Well, it
was good exercise for the computer.

-- 
G. L. Sicherman
work: sicherman@lucent.com
home: colonel@mail.monmouth.com

From:           colonel@monmouth.com (The Pied Typer)
Date:           15 Jun 2000 22:47:25 -0400
Newsgroups:     sci.math
Subject:        Sylver Coinage - can you prove them?

I recently stumbled over two elegant results in the theory of Sylver
Coinage (see _Winning Ways,_ ch. 18).  Unfortunately they are
empirical results; I have not found even an ugly proof of either.
Maybe you on the Net can do better!

Notation:  g(x,y,...) is the greatest common divisor of its arguments.
t(x,y,...) is the highest legal move in {x,y,...}; that is, the
greatest number not expressible as a sum with multiples of elements
of {x,y,...}.  t is defined only if g=1.  Other terminology is as
in _Winning Ways._

The earliest general results in Sylver Coinage are

Sylvester's Theorem : If g(m,n)=1, then t(m,n) = mn - (m+n).  (This
does not actually involve the game of Sylver Coinage; it is only
important in characterizing it.)

Hutchings's Theorem: If g(m,n)=1 and t(m,n)>1, then {m,n} is an ender
(and therefore "N").

Now here are the unproved results:

Proposition X:  Let S and T be initial segments of the same ascending
arithmetic progression with g=1.  Then t(S) and t(T) differ by a
multiple of the first element of the progression.  (Like Sylvester's
Theorem, this does not actually involve the game.)

Proposition Y:  Let S be a finite arithmetic progression of numbers
greater than 3.  If S is an ender, then S is a quiet ender.

From Hutchings's Theorem and Proposition Y follows the known result
that if g(m,n)=1 and m and n are greater than 3, then {m,n} is a
quiet ender.  It is easy to replace the condition that m and n are
greater than 3 with the weaker condition of Hutchings's Theorem.
Technically even {2,3} (where t=1) is a quiet ender--the only
ender that is "P".

-:-
	"'PATAGEOMETRY: The study of those mathematical properties
	 that remain invariant under brain transplants."
-- 
Col. G. L. Sicherman
home: colonel@mail.monmouth.com
work: sicherman@lucent.com
web: <http://www.monmouth.com/~colonel/>

From:           colonel@shell.monmouth.com (Col. G. L. Sicherman)
Date:           22 Jun 2000 17:30:50 -0400
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - somebody proved it!

In <8im0ug$8pj$1@shell.monmouth.com>, I wrote:
> In <8ic4ft$es2$1@shell.monmouth.com>, I wrote:
> > 
> > Proposition X:  Let S and T be initial segments of the same ascending
> > arithmetic progression with g=1.  Then t(S) and t(T) differ by a
> > multiple of the first element of the progression.  (Like Sylvester's
> > Theorem, this does not actually involve the game.)
> 
> I just ran across a reference to a 1956 paper by J. B. Roberts that
> may have a proof of this.  More later!

And so it does.  Taking the arithmetic progression to be a0, a1, ..., as
with successive difference d, Roberts gives:

	t(a0, a1, ..., as) + 1 = ([{a0-2}/s] + 1)a0 + (d - 1)(a0 - 1).

where [...] indicates the integer part.  Since the second term does not
depend on s, Proposition X follows immediately.  Roberts's proof, while
efficient, runs to 5 pages--I'm glad I don't need to discover it myself!
(Mathematics can be a good livelihood but it makes a poor hobby.)

> > Proposition Y:  Let S be a finite arithmetic progression of numbers
> > greater than 3.  If S is an ender, then S is a quiet ender.
> 
> No progress yet.

But I'll try to adapt Roberts's ideas.

-:-
	"This rock, for instance, has an I.Q. of zero.  Ouch!"
	"What's the matter, Professor?"
	"It bit me!"
-- 
Col. G. L. Sicherman
home: colonel@mail.monmouth.com
work: sicherman@lucent.com
web: <http://www.monmouth.com/~colonel/>

From:           colonel@shell.monmouth.com (Col. G. L. Sicherman)
Date:           26 Jun 2000 12:09:13 -0400
Newsgroups:     sci.math
Subject:        Re: Sylver Coinage - building on Roberts

In <8iu0ia$8pj$1@shell.monmouth.com>, I wrote:
> > > Proposition Y:  Let S be a finite arithmetic progression of numbers
> > > greater than 3.  If S is an ender, then S is a quiet ender.
> > 
> > No progress yet.
> 
> But I'll try to adapt Roberts's ideas.

Roberts's formula has inspired me to reformulate Proposition Y:

	Proposition Y:  Let S = {a[0], a[1], ... , a[s]} be an increasing
	arithmetic progression of numbers greater than 3.  If s divides
	a[0]-2, then S is a quiet ender; otherwise S is not an ender.

This is more specific and should be easier to prove.

-:-
	When by judgement one means knowing how something comes to be
	what it is, the judgement must appear as re-constructing the
	identical universe of the difference.  Then every model
	includes the measure of its own difference.  No state of
	equilibrium is empowered to remain identical, or to compel the
	individual to alter (and integrate with it).  The identical is
	equal to itself, since it is different.

					--Franco Spisani (1975)
-- 
Col. G. L. Sicherman
home: colonel@mail.monmouth.com
work: sicherman@lucent.com
web: <http://www.monmouth.com/~colonel/>

From:           gls@simba.cvu.lucent.com (G. L. Sicherman)
Date:           3 Aug 2000 19:09:16 GMT
Newsgroups:     sci.math
Subject:        Sylver Coinage: {14,26} is P

I've bagged another one:  In Sylver Coinage, {14,26} is P.  Details
are at my Sylver Coinage page:

	<http://www.monmouth.com/~colonel/sylver/>

This forms a triad of mutually responsive moves in {}:

	{10, 14, 26}

Against any opening move from this set, any other move from this set
will win.  A unique situation--so far!  By the way, the winning move
in {10, 14, 26} is 293--a result that Voelkle found long ago.

We now know all winning moves in {14}: [7, 8, 10, 26].

-:-
	"Hey, Rocky!  Watch me pull a UNIX program out of my
	   source directory!"
	"AGAIN?"
	"Nothin' up my sleeve ... PRESTO!"

		IDENTIFICATION DIVISION.
		  AUTHOR-NAME.  B. J. MOOSE, FROSTBYTE DATA SYS.
		  SOURCE-COMPUTER.  IBM-7044.
		  OBJECT-COMPUTER.  IBM-7044.
		. . .

	"No doubt about it--I gotta get a new source directory!"
-- 
G. L. Sicherman
work: sicherman@lucent.com
home: colonel@mail.monmouth.com