[seqfan] Re: No progress on the classic "Football pools" problem in 52 years

Sun Jun 27 14:55:32 CEST 2021

I am interested in actual examples of these strings (for purely
mathematical reasons and totally not to gambling use).  So in the
literature there is an example of a(4) is {0000, 0112, 0221, 1022, 1101,
1210, 2011, 2120, 2202}.  However I cannot find an example for a(5).

On Sun, 27 Jun 2021 at 16:04, Tomasz Ordowski <tomaszordowski at gmail.com>
wrote:

> I do not have a good heuristic for my formula, except the intuition that if
> the extreme upper case occurs in general, then it must immediately follow
> the extreme lower case; because if not, when?
> Scanty data double my intuition /;-)
>
> Tom
>
>
> czw., 24 cze 2021 o 20:27 Benoît Jubin <benoit.jubin at gmail.com>
> napisał(a):
>
> > On Thu, Jun 24, 2021 at 3:42 PM Tomasz Ordowski <
> tomaszordowski at gmail.com>
> > wrote:
> >
> > > Conjecture: a((3^n+1)/2) = 3^((3^n+1)/2 - n) for n > 0.
> > >
> >
> > Can you explain your reasoning ?  It's obviously an upper bound since
> > trivially a(n+1) <= 3a(n), but that looks like a lot of overlap.  Did you
> > study the structure of the Hamming codes in dimension (3^m-1)/2 ?  The
> > problem is that it's possible that there exist perfect non-Hamming codes
> ?
> > Or it's also possible that none of the three "layers" are actually
> covered
> > by the balls centered in these layers ?
> >
> > Using the known lower and upper bounds and the existence of perfect
> Hamming
> > codes, we have
> >   ceil(3^n/(2n+1)) <= a(n) <= 3^(n-floor(log_3(2n+1))) for n>=0
> > but beyond that, I'm stuck.
> >
> > Benoît
> >
> >
> >
> > >
> > > T. Ordowski
> > >
> > >
> > > czw., 24 cze 2021 o 12:21 Benoît Jubin <benoit.jubin at gmail.com>
> > > napisał(a):
> > >
> > > > Thanks Neil for the reference, which readily answers the question.
> On
> > > page
> > > > 286 of that book, section "11.1 Perfect linear codes over \F_q",
> > > paragraph
> > > > "Hamming codes", it says that Hamming codes exist in theses
> dimensions
> > > and
> > > > are perfect, which is what we want ("perfect" means that the balls do
> > not
> > > > overlap).  So you may add to the sequence page:
> > > > DATA: a(0) = 1
> > > > OFFSET: 0
> > > > COMMENTS (or FORMULA ?): a((3^m-1)/2) = 3^((3^m-1)/2 - m) follows
> from
> > > the
> > > > existence of Hamming codes in these dimensions (see page 286 of
> [Cohen
> > et
> > > > al.]).
> > > >
> > > > There are also many lower and upper bounds and asymptotics in this
> > book,
> > > > and some of them probably apply to the current sequence. (I won't
> have
> > > time
> > > > to look at them more closely at the moment, but anyone reading this
> is
> > > > encouraged to do so.)  One caveat: the book calls "sphere" what is
> > > actually
> > > > a "ball"... very unusual and puzzling until you discover it.
> > > >
> > > > Best,
> > > > Benoît
> > > >
> > > > On Wed, Jun 23, 2021 at 8:04 PM Neil Sloane <njasloane at gmail.com>
> > wrote:
> > > >
> > > > > Hi Benoit, The book by Gerard Cohen et al on Covering Codes is
> really
> > > > > excellent.  I have it downstairs, if you seriously want me to go
> > look.
> > > > > Hamming codes are certainly relevant.
> > > > >
> > > > > Best regards
> > > > > Neil
> > > > >
> > > > > Neil J. A. Sloane, President, OEIS Foundation.
> > > > > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > > > > Also Visiting Scientist, Math. Dept., Rutgers University,
> Piscataway,
> > > NJ.
> > > > > Phone: 732 828 6098; home page: http://NeilSloane.com
> > > > > Email: njasloane at gmail.com
> > > > >
> > > > >
> > > > >
> > > > > On Wed, Jun 23, 2021 at 1:14 PM Benoît Jubin <
> benoit.jubin at gmail.com
> > >
> > > > > wrote:
> > > > >
> > > > > > It looks like A004044(0) = 1 !
> > > > > > In that case, the trivial lower bound is attained.  Actually, in
> > the
> > > > > known
> > > > > > cases where 3^n/(2n+1) is an integer, then that lower bound is
> > > > attained.
> > > > > > This means that there is a solution with no overlaps.  If this is
> > > true
> > > > in
> > > > > > general, this is probably well-known by people knowing Hamming
> > codes
> > > > (of
> > > > > > which I am not).  Or did I misinterpret the problem ?
> > > > > > Best regards,
> > > > > > Benoît
> > > > > >
> > > > > > On Mon, Jun 21, 2021 at 6:52 AM Neil Sloane <njasloane at gmail.com
> >
> > > > wrote:
> > > > > >
> > > > > > > I grew up in a country where many people played the football
> > pools
> > > > > every
> > > > > > > week (trying to guess the winners of next week's games: you
> know
> > > > > > Manchester
> > > > > > > United is going to beat Arsenal, but there are 13 games to
> > > predict).
> > > > > > >
> > > > > > > The classical problem translates into finding the smallest
> > covering
> > > > > code
> > > > > > in
> > > > > > > {0,1,2}^n with covering radius 1.  The sequence (A004044)
> begins
> > > > > > > 1,3,5,9,27, but even after 52 years, a(6) is still not known.
> > > > Tonight
> > > > > I
> > > > > > > came across a lot of references, which I have added to A004044.
> > > a(6)
> > > > > is
> > > > > > > known to be 71, 72, or 73.
> > > > > > > If you can solve it, you might not make any money, but you will
> > > > > probably
> > > > > > > get your name in the science section of the newspaper.
> > > > > > >
> > > > > > > Good publicity for the OEIS too!
> > > > > > >
> > > > > > >
> > > > > > > Best regards
> > > > > > > Neil
> > > > > > >
> > > > > > > Neil J. A. Sloane, President, OEIS Foundation.
> > > > > > > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > > > > > > Also Visiting Scientist, Math. Dept., Rutgers University,
> > > Piscataway,
> > > > > NJ.
> > > > > > > Phone: 732 828 6098; home page: http://NeilSloane.com
> > > > > > > Email: njasloane at gmail.com
> > > > > > >
> > > > > > > --
> > > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > > > >
> > > > > >
> > > > > > --
> > > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > > >
> > > > >
> > > > > --
> > > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > > >
> > > >
> > > > --
> > > > Seqfan Mailing list - http://list.seqfan.eu/
> > > >
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>