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

Tue Jun 29 16:18:30 CEST 2021

Right, prepending yields only an upper bound, but for a(5) it is tight.

> On Jun 29, 2021, at 9:53 AM, Robert McKone <r.p.mckone at gmail.com> wrote:
> 
> 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/
>> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/