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

Tomasz Ordowski tomaszordowski at gmail.com
Fri Jun 25 07:49:14 CEST 2021

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