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

Sun Jun 27 16:55:38 CEST 2021

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/