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

Mon Jun 28 01:53:52 CEST 2021

What about our upper bound for a(6), we cannot just append {0,1,2} onto the
previous, because that would give us 81 instead of 73.

Do we also have a known list of 73 for a(6) and onwards for the upper
bounds of a(7), a(8) and so on?

On Mon, 28 Jun 2021 at 00:55, Rob Pratt <robert.william.pratt at gmail.com>
wrote:

> Just prepend each of the 9 strings with 0, 1, or 2, yielding 27, as
> mentioned in the comments section.
>
> > On Jun 27, 2021, at 10:47 AM, Robert McKone <r.p.mckone at gmail.com>
> wrote:
> >
> > 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/
> >>
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>