A tiling game and generating functions

Created	@August 29, 2023 5:29 PM
Contact	pranav.joshi@iitgn.ac.in
Creator	Pranav Joshi

Hi! This problem is a generalisation of a special case which Mathologer has a video on. This generalisation was presented in the ES214 course (Discrete Mathematics) conducted in 2023 at IITGN.

Claim

Given a sequence $A_n = [a_0\;a_1\;a_2\dots a_{n-1}]$ , with indexing operation $A_n[i] = a_i$ , we generate the reduced sequence $A_{n-1}$ as

A_{n-1}[r] = -(A_n[r] + A_n[r+1]) \mod{p} \;\;\forall r \in \{0,1\dots n-2\}

for an odd prime $p$ .

I claim that if $n = p^k + 1$ for any whole number $k$ , then

A_1[0] = -(A_n[0] + A_n[n-1]) \mod{p} .

Simulation

Play around with this for a few times to get a feel.

The top row is the sequence $A_n$ . You can also input arithmetic expressions for $n$ (For example, “3**2 + 1”) to get a randomly generated $A_n$ .

https://pj29072004.github.io/DM_Tiling_Game/

Proof

Consider this function :

p_m(x) = (a_0+a_1x+a_2x^2+\dots)(-\frac{1}{x}-1)^m .

The coefficients of non negative powers of $x$ in $p_m(x)$ give us the sequence $A_{n-m}$ . Basically, the coefficient of $x^n$ in $p_m(x)$ is congruent, modulo $p$ , to the $n^\text{th}$ entry in the sequence $A_{n-m}$ , namely $A_{n-m}[n]$ . Stated compactly,

\text{Coefficinet of }x^n \text{ in }p_m(x) \equiv A_{n-m}[n] \mod{p}

So to find $A_1[0]$ , we look for the coefficient of $x^0$ in $p_{n-1}(x)$ , which can be equivalently stated as the coefficient of $x^{n-1}$ in the polynomial

(a_0+a_1x+a_2x^2+\dots)(-1-x)^{n-1}

, which can be rewritten as

(-1)^{n-1}(a_0+a_1x+a_2x^2+\dots)(\sum_{r=0}^{n-1} \;^{n-1}C_r \;x^r) .

Thus, the coefficient of $x^{n-1}$ is :

(-1)^{n-1} (a_0 \;^{n-1}C_{n-1}\; + a_1 \;^{n-1}C_{n-2}\; + a_2 \;^{n-1}C_{n-3}\; + \dots + a_{n-1} \;^{n-1}C_{0}\;) .

Now, if

n = p^k +1

….

…then this expression is equivalent to

(-1)^{p^k}(a_0+a_{n-1})

, but modulo $p$ .

This is because

p \;|\; ^{p^k}C_{r} \;\forall r\in {1,2,\dots p^k-1}

But since $p$ is odd, $(-1)^{p^k}(a_0+a_{n-1}) = -(a_0 + a_{n-1})$ .

Thus, in summary, we have showed

A_1[0] \equiv \\ (-1)^{n-1} (a_0 \;^{n-1}C_{n-1}\; + a_1 \;^{n-1}C_{n-2}\; + a_2 \;^{n-1}C_{n-3}\; + \dots + a_{n-1} \;^{n-1}C_{0}\;) \\ \equiv -(a_0+a_{n-1}) \mod{p} \\\text{ if }\; \exists \,k \in \mathbb{W} \;\text{ s.t.}\;n=p^k+1

When n is not in the form required

Since $n-1$ is not a power of a prime $p$ , we can write it as $n-1= xp^k$ where $\gcd(x,p) = 1$ and $x > 1$ .

A useful (general) property

If $p$ is a prime and $\gcd(p,x)=1$ , then $^{xp^k}C_{p^k} \equiv x \mod{p}$ .

Proof

We can split the problem of choosing from $x p^k$ $xp^k$ $p^k$ and write :

^{xp^k}C_{p^k} = \sum_{r_1+r_2+\dots+r_x = p^k }\;^{p^k}C_{r_1}^{p^k}C_{r_2}\dots^{p^k}C_{r_x}

Since $p \;|\; ^{p^k}C_r \;\;\forall r \in \{1,2,3\dots p^k-1\}$ , thus we can write the following congruence (modulo $p$ ) :

^{xp^k}C_{p^k} \equiv 0 + \sum_{r_j=p^k\,;\;r_i=0 \;\forall i\neq j}\;^{p^k}C_{r_1}^{p^k}C_{r_2}\dots^{p^k}C_{r_x} = \sum_{1\leq j\leq x}\;1 = x

Now, using this property, if we set $a_{n-1-p^k} = 1$ and all other $a_i = 0$ (including $a_0$ , since $x > 1 \implies {n-1} \neq p^k$ and thus $a_{n-1-p^k}$ and $a_0$ are distinct coefficients), then we get :

A_1[0] \equiv \\(-1)^{n-1} (a_0 \;^{n-1}C_{n-1}\; + a_1 \;^{n-1}C_{n-2}\; + a_2 \;^{n-1}C_{n-3}\; + \dots + a_{n-1} \;^{n-1}C_{0}\;) \\ \equiv (-1)^{n-1} (a_{n-1-p^k} \;^{xp^k}C_{p^k} + 0) \\\equiv (-1)^{n-1}(1\cdot x) \mod{p}.

But since $p$ does not divide $x$ , this is not divisible by $p$ and. But since $a_0 = a_{n-1} = 0$ , so,

-(a_0 + a_{n-1}) \equiv 0 \mod{p}

And thus we have :

A_1[0] \equiv (-1)^{n-1}x \not\equiv -(a_0+a_{n-1}) \mod{p}

In conclusion, there exists an $A_n$ , namely the one we constructed, such that the claim $A_1[0] = -(A_n[0] + A_n[n-1]) \mod{p}$ doesn’t hold true, if and only if $n$ can’t be written as $p^k + 1$ for some $k \in \mathbb{W}$ .