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

[Tomasz Ordowski]

Conjecture: a((3^n+1)/2) = 3^((3^n+1)/2 - n) for n > 0.

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