[seqfan] RE : Re: A279196: a plausible meaning?

[Luc Rousseau]

Hello,

Thank you Max for your decisive remarks on the nonnegativity of the coefficients in Q and associated counterexample(s).
Now that the situation is clarified with the new definition you gave to A279196, I edited it with new terms up to n=18.

Regards,
Luc

Envoyé à partir de Courrier<https://go.microsoft.com/fwlink/?LinkId=550986> pour Windows

De : Max Alekseyev<mailto:maxale at gmail.com>
Envoyé le :mercredi 28 juin 2023 19:30
À : Sequence Fanatics Discussion list<mailto:seqfan at list.seqfan.eu>
Objet :[seqfan] Re: A279196: a plausible meaning?

I've started a draft for the new sequence: https://oeis.org/draft/A363933
Comments and extension are welcome.

Regards,
Max


On Tue, Jun 27, 2023 at 10:48 PM Max Alekseyev <maxale at gmail.com> wrote:

> After a bit more research, it looks like Luc got a correct meaning of the
> terms in A279196, while its current definition is incorrect.
> Namely, to match its terms one needs to additionally require that the
> quotient of division of P(x,y) by (x+y-1) also has nonnegative coefficients.
> If this requirement is violated, then we have a mismatch already for n =
> 5, when there exist 14 polynomials (rather than a(5)=13) satisfying the
> current definition of A279196:
>
> x^3*y + x^2*y^2 + x*y^2 + x^2 + y   =   1 + (x+y-1) * (x^2*y + x*y + x + 1)
> x^2*y^2 + x*y^3 + x^2*y + x^2 + y   =   1 + (x+y-1) * (x*y^2 + x*y + x + 1)
> x^3 + 2*x^2*y + x*y^2 + y   =   1 + (x+y-1) * (x^2 + x*y + x + 1)
> x^4 + x^3*y + x^2*y + x*y + y   =   1 + (x+y-1) * (x^3 + x^2 + x + 1)
> x^3*y + x^2*y^2 + x^3 + x*y + y   =   1 + (x+y-1) * (x^2*y + x^2 + x + 1)
> x^3*y + x^2*y^2 + x*y^2 + y^2 + x   =   1 + (x+y-1) * (x^2*y + x*y + y + 1)
> x^2*y^2 + x*y^3 + x^2*y + y^2 + x   =   1 + (x+y-1) * (x*y^2 + x*y + y + 1)
> x^2*y + 2*x*y^2 + y^3 + x   =   1 + (x+y-1) * (x*y + y^2 + y + 1)
> x^2*y^2 + x*y^3 + y^3 + x*y + x   =   1 + (x+y-1) * (x*y^2 + y^2 + y + 1)
> x*y^3 + y^4 + x*y^2 + x*y + x   =   1 + (x+y-1) * (y^3 + y^2 + y + 1)
> x^2*y + x*y^2 + x^2 + x*y + y^2   =   1 + (x+y-1) * (x*y + x + y + 1)
> x^3 + x^2*y + 2*x*y + y^2   =   1 + (x+y-1) * (x^2 + x + y + 1)
> x*y^2 + y^3 + x^2 + 2*x*y   =   1 + (x+y-1) * (y^2 + x + y + 1)
> x^3 + y^3 + 3*x*y   =   1 + (x+y-1) * (x^2 - x*y + y^2 + x + y + 1)
>
> All but the last one have quotients with nonnegative coefficients.
> Perhaps, it's worth correcting the definition of A279196, and adding a new
> sequence with the old definition.
>
> Regards,
> Max
>
> On Tue, Jun 27, 2023 at 5:23 PM Max Alekseyev <maxale at gmail.com> wrote:
>
>> Hi Luc,
>>
>> From your translation of languages, it seems to follow that in the formula
>> degrade^<n>(P) = P + (x+y-1) * Q_n
>> the coefficients of Q_n are nonnegative, aren't they?
>>
>> If so, let's consider n=5 and the polynomial
>> x^3 + 3xy + y^3 = 1 + (x + y - 1) * (x^2 + y^2 - xy + x + y + 1)
>> It satisfies the definition of A279196 but cannot be obtained by
>> degradation.
>> Do I miss something?
>>
>> Regards,
>> Max
>>
>>
>> On Tue, Jun 27, 2023 at 3:47 PM Luc Rousseau <luc_rousseau at hotmail.com>
>> wrote:
>>
>>> Dear SeqFans,
>>>
>>>
>>> In 1971 Richard Guy sent a letter to Neil Sloane outlining some integer
>>> sequences; one of them is A279196,
>>> "Number of polynomials P(x,y) with nonnegative integer coefficients such
>>> that P(x,y)==1 (mod x+y−1) and P(1,1)=n".
>>>
>>> 1, 1, 2, 5, 13, 36, 102, 295, 864.
>>>
>>> In 2017 in a Winter Fruits talk (https://vimeo.com/201218446), Neil
>>> said about A279196:
>>> "I don't even know what the [...] polynomials are for the first few
>>> values, so it might be interesting to look into this."
>>>
>>> = = = =
>>>
>>> Unaware of this context, a few days ago, I imagined this:
>>> let the initial configuration be one token at (0, 0).
>>> A configuration can be "degraded": to do so, { choose a nonempty pile of
>>> tokens in it, say that at (i, j); remove one token from that pile; then add
>>> one token at (i + 1, j) and one token at (i, j + 1) }.
>>> The process being nondeterministic, define a(n) as the number of
>>> distinct configurations one can possibly get after (n - 1) "degradations"
>>> of the initial configuration.
>>>
>>> A brute force program that I coded gave:
>>>
>>> 1, 1, 2, 5, 13, 36, 102, 295, 864, 2557, 7624, 22868, 68920, 208527,
>>> 632987, 1926752.
>>>
>>> Superseeker then showed me that this sequence was extending A279196's
>>> known terms. Are the two sequences the same? I discovered the
>>> above-mentionned context.
>>>
>>> It appears I can prove a(n) <= A279196(n) (see below); and I am asking:
>>> has anyone any insights to prove or disprove the equality?
>>>
>>> = = = =
>>>
>>> Translating languages, from the piles of tokens to polynomials, is easy:
>>> C*x^i*y^j means that the height of the pile at (i,j) is C.
>>> The mod(x+y−1) sounds like a bridge between the two definitions, because
>>> clearly:
>>>
>>> degrade(C*x^i*y^j) = (C−1)*x^i*y^j + x^(i+1)*y^j + x^i*y^(j+1) =
>>> C*x^i*y^j + (x+y−1)*(x^i*y^j)
>>>
>>> Now, write P = Sum_{i,j} C[i,j]*x^i*y^j, and degrade P. We have to
>>> choose an (i0,j0) to actually degrade; this gives:
>>>
>>> degrade(P) = (Sum_{(i,j)!=(i0,j0)} C[i,j]x^i*y^j) + (C[i0,j0]*x^i0*y^j0
>>> + (x+y−1)(x^i0*y^j0))
>>>
>>> degrade(P) = P + (x+y−1)*(x^i0*y^j0)
>>>
>>> Applying "degrade" several times lets the cofactor of (x+y−1) grow
>>> accordingly; we can write:
>>>
>>> degrade^<n>(P) = P + (x+y−1) * Q_n
>>>
>>> where Q_n keeps the record of where we took the tokens. The fact we took
>>> exactly n tokens can be transcripted Q_n(1,1)=n. This implies:
>>>
>>> degrade^<n−1>(1)(1,1) = 1+(1+1−1)*(n−1) = n.
>>>
>>> Thus the polynomials of the degradation problem satisfy Richard Guy's
>>> axioms and a(n) <= A279196(n).
>>> But are there other polynomials that do? Was the degradation problem the
>>> meaning Richard Guy had in mind, was the definition by polynomials a way to
>>> make it succinct?
>>>
>>>
>>> Best regards,
>>> Luc
>>>
>>> P.S.: for essentially the same speech in a more comfortable, LaTeX form,
>>> here is a Math StackExchange thread:
>>>
>>> https://math.stackexchange.com/questions/2127914/polynomials-px-y-with-nonnegative-integer-coefficients-such-that-px-y-eq
>>>
>>>
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>

--
Seqfan Mailing list - http://list.seqfan.eu/