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

[Benoît Jubin]

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/
>