Polynomials $P(x,y)$ with nonnegative integer coefficients such that $P(x,y) \equiv 1 \text{ (mod } x+y-1)$ and $P(1,1) = n$.

Question

In 1971 Richard Guy sent a letter to Neil Sloane outlining some integer sequences. One of these sequences, A279196, was added to the OEIS by Neil only in December of 2016:

A279196: Number of polynomials $P(x,y)$ with nonnegative integer coefficients such that $P(x,y) \equiv 1 \text{ (mod } x+y-1)$ and $P(1,1) = n$.

The first few terms of the sequence are:

1, 1, 2, 5, 13, 36, 102, 295, 864

---

In a recent lecture (see 9:50), Neil said:

I don't even know what the [...] polynomials are for the first few values, so it might be interesting to look into this.

I tried to address this in an ad hoc manner, and I managed to find all of the examples for $n \leq 3$ and three examples for $n = 4$:

$a(1) = 1$ with:

• $1$

$a(2) = 1$ with:

• $x + y = (x + y - 1) + 1$

$a(3) = 2$ with:

• $xy + x + y^2 = (y + 1) (x + y - 1) + 1$ and
• $xy + y + x^2 = (x + 1) (x + y - 1) + 1$

And for $n = 4$:

• $x^2 + 2xy^2 + y^2 = (x + y + 1)(x + y - 1) + 1$
• $x^2y + x^2 + xy^2 + y = (xy + x + 1)(x + y - 1) + 1$
• $x^2y + xy^2 + x + y^2 = (xy + y + 1)(x + y - 1) + 1$

---

What is an algorithm or technique to enumerate polynomials for some arbitrary $n$?

Could anyone provide an example of, say, the remaining two polynomials when $n=4$? All thirteen polynomials for $n=5$?

Answer 1

I think I figured it out (but I would still love to see a proof that this technique is exhaustive!)

It seems that (at least the small) values can be built up recursively:

To create a list of polynomials for $a(n)$, for each term (on the right) and polynomial (on the left) in $a(n-1)$, take a term from the left-hand side and move it to the factor of the right hand side.

For example, to create a polynomial for $n = 4$, take the first term/factor pair for $n = 3$ (highlighted below in bold) and move the term to be inside of the factor:

n = 4 (example 1)

$\boldsymbol{xy} + x + y^2 = \boldsymbol{(y + 1)}(x + y - 1) + 1$

Leads to: $x^2y + xy^2 + x + y^2 = \boldsymbol{(xy + y + 1)}(x + y - 1) + 1$

---

Remaining examples:

n = 4 (example 2)

$xy + \boldsymbol{x} + y^2 = \boldsymbol{(y + 1)}(x + y - 1) + 1$ and

$xy + \boldsymbol{y} + x^2 = \boldsymbol{(x + 1)}(x + y - 1) + 1$

Leads to: $x^2 + 2xy + y^2 = \boldsymbol{(x + y + 1)}(x + y - 1) + 1$

n = 4 (example 3)

$xy + x + \boldsymbol{y^2} = \boldsymbol{(y + 1)}(x + y - 1) + 1$

Leads to: $xy^2 + xy + x + y^3 = \boldsymbol{(y^2 + y + 1)}(x + y - 1) + 1$

n = 4 (example 4)

$\boldsymbol{xy} + y + x^2 = \boldsymbol{(x + 1)} (x + y - 1) + 1$

Leads to: $x^2y + xy^2 + x + y^2 = \boldsymbol{(xy + y + 1)}(x + y - 1) + 1$

n = 4 (example 5)

$xy + y + \boldsymbol{x^2} = \boldsymbol{(x + 1)} (x + y - 1) + 1$

Leads to: $ x^3 + x^2y + xy + y = \boldsymbol{(x^2 + x + 1)}(x + y - 1) + 1$

Answer 2

I think I have found accidentally some key to this sequence.

Yesterday I imagined this: let the initial configuration be one token at (0, 0). A configuration can be "degraded": 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 gives: 1, 1, 2, 5, 13, 36, 102, 295, 864, 2557, 7624, 22868, 68920, 208527, 632987, 1926752, (and then out of memory). This extends A279196's known terms so far (nine terms). Then that's through OEIS's Superseeker, and A279196's history that I found your post here on Math StackExchange 6 years later.

Translating languages, from my 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 $\mbox{mod}(x+y-1)$ sounds like a bridge between the two definitions, because clearly $$\mbox{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 $(i_0,j_0)$ to actually degrade, this gives

$$\mbox{degrade}(P) = \left ( \sum_{(i,j)\neq (i_0,j_0)} C_{i,j} x^i y^j \right ) + \left ( C_{i_0,j_0} x^{i_0} y^{j_0} + (x+y-1)(x^{i_0} y^{j_0}) \right )$$ $$\mbox{degrade}(P) = P + (x+y-1)(x^{i_0}y^{j_0}) $$

Applying "degrade" several times lets the cofactor of $(x+y-1)$ grow accordingly, we can write: $$\mbox{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

$$\mbox{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 I think we've proved $a(n) \leq \mbox{A279196}(n)$. But are there other polynomials that do?

So I'm not 100% sure that the two definitions are equivalent, but a nine terms match and may be the premises of a proof sound rather good for a start.

Regards, Luc Rousseau.