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

[Benoît Jubin]

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