How to show that two generating functions share congruent coefficients

Question

I have two generating functions.

$A(x)= \frac{x^{\frac{m \left(m-1\right)}{2}}}{\left(1-x\right)\cdot \left(1-x^{2}\right)\cdot ...\cdot \left(1-x^{m}\right)}$

$B(x)= \frac{A(x)}{x^t} = \frac{x^{\frac{m \left(m-1\right)}{2}}}{\left(1-x\right)\cdot \left(1-x^{2}\right)\cdot ...\cdot \left(1-x^{m}\right) \cdot x^t}$

If $m=2$ and $t=4$ we get:

$A(x)= \frac{x}{\left(1-x\right)\cdot \left(1-x^{2}\right)} = x+x^{2}+2 x^{3}+2 x^{4}+3 x^{5}+3 x^{6}+4 x^{7}+4 x^{8}+5 x^{9} + ...$

$B(x)= \frac{1}{\left(1-x\right)\cdot \left(1-x^{2}\right) \cdot x^3 } =x^{-3}+x^{-2}+2 x^{-1}+2+3 x+3 x^{2}+4 x^{3}+4 x^{4}+5 x^{5}+5 x^{6}+6 x^{7}+6 x^{8}+7 x^{9} $

We see that the coefficients are congruent modulo $m=2$, for the terms with positive exponents. I.e.
$3 = 1 \mod 2$
$4 = 2 \mod 2$
$5 = 3 \mod 2$
...

I have been able to prove this for the pairs $t,m = (2,4), (3,18)$ by considering the coefficients of the the partial fraction decomposition of $B(x)-A(x)$ which for $m=2$ and $t=4$ is: $\frac{2}{1-x}+\frac{2}{x}+\frac{1}{x^{2}}+\frac{1}{x^{3}}$

And for $m=3$ and $t=18$ is: $\frac{3}{\left(1-x\right)^{2}}+\frac{24}{1-x}+\frac{24}{x}+\frac{21}{x^{2}}+\frac{19}{x^{3}}+\frac{16}{x^{4}}+\frac{14}{x^{5}}+\frac{12}{x^{6}}+\frac{10}{x^{7}}+\frac{8}{x^{8}}+\frac{7}{x^{9}}+\frac{5}{x^{10}}+\frac{4}{x^{11}}+\frac{3}{x^{12}}+\frac{2}{x^{13}}+\frac{1}{x^{14}}+\frac{1}{x^{15}}$

This however is a quite tedious calculation. Do anyone know a better way to show this, ideally how to find $t$ when given an $m$ such that their coefficients are congruent modulo $m$?

Or a way to only find the coefficients of the terms in the partial fraction decomposition containing $\frac{1}{1-x^i}$

Any advice is greatly appreciated.

Answer 1

I would do the computations in the Laurent power series ring in the variable $x$ with coefficients in the field $$ F=\Bbb F_2 $$ with two elements, $0,1$. Then for instance for the case $m=2$ and $t=4$ the computation is, writing $A=A_{m,t}$, and $B=B_{m,t}$ for the corresponding $A$-polynomial and $B$-polynomial: $$ \begin{aligned} B(x)-A(x)&=(1-x^4)\cdot B(x) \\ &=\frac {1-x^4}{(1-x)(1-x^2)x^3}=\frac{(1+x)^4}{(1+x)(1+x)^2x^3}= \color{brown}{\frac {1+x}{x^3}} = \color{blue}{\frac1{x^3}+\frac1{x^2}}\ , \end{aligned} $$ so the power series for $A$, $B$ coincide in all powers (in $F$, or considered modulo $2$) except for degrees $-3,-2$.

The next case is similar, $m=3$ and $t=18$, we are working now in characteristic $3$, i.e. over the field $$ F=\Bbb F_3\ , $$ i saw this relatively late, and the similar computation is $$ \begin{aligned} &B(x)-A(x)\\ &\ =(1-x^{18})\cdot B(x) \\ &\ =\frac {1-x^{18}}{(1-x)(1-x^2)(1-x^3)x^{15}} =\frac{(1-x^2)^9}{(1-x)\;(1-x)(1+x)\;(1-x)^3\;x^{15}} \\ &\ =\frac {(1-x)^9(1+x)^9}{(1-x)^5(1+x)x^{15}} = \color{brown}{\frac {(1-x)^4(1+x)^8}{x^{15}}} \ , \end{aligned} $$ and we expand the numerator which has degree $12<15$, see that only negative powers of $x$ survive.

---

The value $m=4$ can be considered in a similar manner, however we are working over a power series ring over the ring of coefficients $\Bbb Z/4$, which is not a field, so let us consider the next case, $m=p=5$.

---

The case $m=p=5$, and we are working over the field with five elements $$ F=\Bbb F_5\ , $$ The polynomial $A$ does not depend on $t$, it is $$ A(x) = \frac{x^{10}}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)}\ , $$ and we are searching for a power $N$ so that $(1-x^N)$ is a multiple of the denominator. So we want to see the factorization of the denominator first: $$ (1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)\\ =(1-x)\; (1-x)(1+x)\; (1-x)(1+x+x^2)\; (1-x)(1+x)(1+2x)(1+3x)\; (1-x)^5\\ =(1-x)^9\; (1+x)^2\; (1+2x)(1+3x)\; (1+x+x^2)\ , $$ so $(1-x^N)$ should be divisible with $(1-x)^9$ first, else a corresponding term will survive in the partial fraction decomposition, and contribute at infinitely many places in positive degrees in the final Taylor series (modulo five). Well, $(1-x^5)=(1-x)^5$ is not enough, so we need a higher power, the power $p^2=5^2=25$ is enough, since $(1-x^{25})=(1-x)^{25}$. Now we also need to cover some $(1+x)^2$ factor, we look among the multiples of $25$, and $2\cdot 25$ is enough, $(1-x^{50})=(1-(x^2)^{25})=(1-x^2)^{25}=(1-x)^{25}(1+x)^{25}$. The next "cyclotomic" polynomial to be covered is $1+x+x^2$, of course $N=25\cdot 2\cdot 3$ is doing the job. It remains the next and last "cyclotomic" polynomial $\Phi_4(x)=1+x^2=(1+2x)(1+3x)$ to be covered, and it turns out that we need $N=2^2\cdot 3\cdot 5^2$. So our choice of $t$ is this one, and the computation is easy now: $$ \begin{aligned} &B(x)-A(x)\\ &\ =(1-x^{300})\cdot B(x) \\ &\ =\frac {1-(x^{12})^{25}}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)x^{290}} \\ &\ =\frac{(1-x^{12})^{25}}{(1-x)\;(1-x)(1+x)\;(1-x)(1+x+x^2)\;(1-x)(1+x+x^2+x^3)\;(1-x)^5\;x^{290}} \\ &\ = \color{brown}{ \frac{(1-x^{12})^6}{(1-x)\cdot(1-x)^5}\cdot \frac{(1-x^{12})}{(1-x)^2}\cdot \frac{(1-x^{12})}{(1-x)^3}\cdot \frac{(1-x^{12})}{(1-x)^4}\cdot \frac{(1-x^{12})^{\dots}}{x^{290}}} \ , \end{aligned} $$ and $9$ from the $25$ factors $(1-x^{12})$ "cover" $(1-x)^{1+1+1+1+5}$, and the next few factors cover one by one $(1-x^2)$, $(1-x^3)$, $(1-x^4)$. So the brown fraction remains after simplifications a fraction with denominator $x^{290}$, and the degree in the numerator is smaller. (Ten$=m(m-1)/2$ versus $1+2+3+4+5=m(m+1)/2$, ten is smaller at the beginning, so also at the end, $B$ has same total negative degree.) So only terms in negative degree finally remain.

---

Similar computations can be done for other values of $m$, best using a computer. If $m$ is a prime $p$, then $t=p^2\cdot (p-1)!$ is good - the same argument as above applies. For $p=2$ this recovers $t=2^2\cdot1!=4$, for $p=3$ we obtain $t=3^2\cdot2!=18$, and for $p=5$ we get $t=5^2\cdot 4!=600$, which is too big, $300$ would be enough.

If some special other $m$ is of interest, i can closer cover the case.

---

---

LATER EDIT: Let us consider also a case of a non-prime $m$. We start with the observation, that we can more or less reduce to the case of a prime power case. For instance, if $m=6$, then a congruence of coefficients modulo six is equivalent to their congruence modulo two, and modulo three. So if we know the answers for two and three, we can adapt them to the new case. (However, the denominators $(1-x)(1-x^2)$ for $m=2$, and $(1-x)(1-x^2)(1-x^3)$ for $m=3$ has to be adapted to the new case, we have more factors in the product, $(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)(1-x^6)$ for $m=6$. Maybe is a good idea to have different variables for the number of factors, here $2,3,6$, and the modulus taken for the congruence, here also $2,3,6$, but the rôles are different. So we may take the product $(1-x)(1-x^2)(\dots)(1-x^{2024})$ and ask for a congruence modulo $2027$, the next prime year. Anyways, the computations in $\Bbb F_2$ and $\Bbb F_3$ are similar to those from above.)

So let us consider the case of a prime power, the value $m=4=2^2$ is a good first test. We consider $f=(1-x)(1-x^2)(1-x^3)(1-x^4)\in R[x]$ as a polynomial with coefficients in the ring $R=\Bbb Z/4$. Then we no longer have the unique factorization property, for instance $X^2=(X+2)^2$, but we have units, divisibility and factorizations. Also, results are of interest finally in the power series ring $R[[x]]$ over the same ring of coefficients $R=\Bbb Z/4$ of integers modulo four.

We search for a value of $N$ so that $f$ divides $g=g_N=(1-x^N)$ in $R[x]$. In particular, this divisibility also works modulo two, i.e. when seen in $\Bbb F_2[x]$ through the passage $R=\Bbb Z/4\to \Bbb Z/2$, $r\to \bar r$. I will use a bar also to denote elements from $R[x]$ seen suddenly in $\Bbb F_2[x]$. Over $\Bbb F_2$ we have $\bar f=(1-x)(1-x^2)(1-x^3)(1-x^4)=(1+x)\;(1+x)^2\;(1+x)(1+x+x^2)\;(1+x)^4=(1+x)^8(1+x+x^2)$. If $\bar f$ divides $\bar g$, then we need a relatively big value of $N$, at any rate, $(1+x)^8$ must divide $(1-x^N$, and the first value that works is $N=8$, again because we are in characteristic two, so the Frobenius two-power-map is a morphism $(a+b)^2=a^2+b^2$, and in general $(a+b)^{2^n}=a^{2^n}+b^{2^n}$ for powers of the Frobenius morphism. But there is also the factor $\Phi_3(x)=(1+x+x^2)\in \Bbb F_2[x]$, and we have to "cover it", too. It is natural to use $N=3\cdot 8$, and we immediately see that for this $N$ the modulo two polynomial $\bar f$ divides $(1-x^{24})=(1-(x^3)^8)=(1-x^3)^8=(1-x)^8(1+x+x^2)^8\in \Bbb F_2[x]$.

So we immediately check if $N=3\cdot 8=24$ is working in $R[x]$, i.e. modulo four. No, unfortunately not, "almost the same" computation applies, but we cannot take care of all the $(1-x)$ and $(1+x)$ factors: $$ \begin{aligned} f &=(1-x)(1-x^2)(1-x^3)(1-x^4)\\ &=(1-x)\; (1-x)(1+x)\; (1-x)(1+x+x^2)\; (1-x)(1+x)(1+x^2)\\ &=(1-x)^4(1+x)^2(1+x+x^2)(1+x^2)\\ &=(1-x)^4(1-x)^2(1+x+x^2)(1+x^2)\\ &=\color{red}{(1-x)^6}\color{green}{(1+x+x^2)(1+x^2)}\ , \\ g &=(1-x^{24})=(1-x)\prod_{\substack{d|24\\1<d<24}}\Phi_d(x) \\ &\qquad\text{ (which is the cyclotomic decomposition over $\Bbb Z$)}\\ \\ &=(1-x)(1+x)(1+x+x^2)(1+x^2)(1-x+x^2)(1-x^2+x^4)(1+x^4)(1-x^4+x^8) \\ &=\color{red}{(1-x)}\color{green}{(1+x+x^2)(1+x^2)} \cdot \underbrace {(1+x)(1+x^4)}_{=\color{red}{(1-x)}(\dots)} \\ & \qquad\qquad\cdot (1-x+x^2)(1-x^2+x^4)(1-x^4+x^8) \ , \end{aligned} $$ and from the remained "odd" factors (when setting $x=1$) it is not possible to force any further $(1-x)$-factor. So we take soon a multiple of $24$, and see if it works for it. In order to illustrate the problems that occur in $R[x]$, let us observe that we may even force the factor $\color{red}{(1-x)^4}$ from $(1-x^{24})$, although the above computations suggests that we are only getting the second power out of it. Indeed, $(1-x)^4=1\pm 2x^2+x^4=(1\pm x^2)^2$. Substitute $y=x^2$. Does $(1-x)^4$ divide $(1-x^{24})$? Yes, if $(1-y)^2$ divides $(1-y^{12})$. And this is the case, since $$ \scriptsize (1-y^{12})=(1-y)(1+y)(1+y^2)(\dots)=(1-y)(1+y+y^2+y^3)(\dots)=(1-y)(1+y+y^2-3y^3)(\dots)=(1-y)^2(\dots)\ ,$$ and well, yes, it is ugly to perform arithmetics in such a ring.

It turns out that $N=48$ is good enough to cover the missing $\color{red}{(1-x)^4}$. I hope that all the above showed the problems of working in the polynomial ring $R[x]$. So let us better work in the power series ring $R[[x]]$! Here, the elements $(1-x)$, $(1-x^2)$, ... are all units, $1/(1-x^d)=1+x^d+x^{2d}+\dots$, and we can easily check - aided by a computer - if the $$ \text{power series } \frac{(1-x^N)}{(1-x)(1-x^2)\dots(1-x^m)} \in R[[x]]=(\Bbb Z/4)[[x]] $$ "looks like" a polynomial. (The result of division is unique, so we have a clear computational scheme.) In our case, $N=48$ and $m=4$. I wanted to avoid any CAS in this answer, but now i cannot longer do it, since it is a part of the game when "higher" cases are of interest. What we do now? We work in fact in the power series ring modulo a high power of $x$, for instance modulo $O(x^{2024})$. If the computed power series shows coefficients only in degrees up to $N-(1+2+\dots+m)$, in our case $(48-(1+2+3+4))=38$, then it is likely that the computation leads to a polynomial, and moreover we can take this part and check if we have in fact a polynomial identity for it.

Code now. I will use sage.

R.<x> = PowerSeriesRing(Integers(4), default_prec=2024)
f = (1 - x)*(1 - x^2)*(1 - x^3)*(1 - x^4)
g = (1 - x^48)

print(latex(g/f))

And the printed quotient is: $$ \small 1 + x + 2 x^{2} + 3 x^{3} + x^{4} + 2 x^{5} + x^{6} + 3 x^{7} + 3 x^{8} + 2 x^{9} + 3 x^{10} + 3 x^{11} + 2 x^{12} + 3 x^{13} + 3 x^{14} + 2 x^{15} + 2 x^{19} + 2 x^{23} + x^{24} + x^{25} + 2 x^{26} + x^{27} + x^{28} + 2 x^{29} + x^{30} + x^{31} + 3 x^{32} + 2 x^{33} + 3 x^{34} + x^{35} + 2 x^{36} + 3 x^{37} + 3 x^{38} + O(x^{2024}) $$ And in the next second we can test that taking the "polynomial part" of the series $g/f$ and multiplying it with the polynomial $f$ we obtain the polynomial $g$:

sage: (g/f).polynomial() * f
1 + 3*x^48

---

---

From the comments it is transparent that you already knew the case $m=4$, $t=48$. So let us consider a next complicate prime power case, $$ m=9=3^2\ . $$ We work blindly with computer aid over the ring of coeficients $R=\Bbb Z/9$ in the power series ring $R[[x]]$. Consider the denominator $f=(1-x)(1-x^2)(\dots)(1-x^9)$. We ask for a "small" power $N$ so that in the polynomial ring $R[x]$ the polynomial $f$ divides the polynomial $g=(1-x^N)$. First of all, we need that $f$ divides $g$ over $\Bbb F_3[x]$. Which is the smallest power?

m = 9
R.<x> = PolynomialRing(GF(3))
f = prod([1 - x^d for d in [1..m]])
for N in [1..10000]:
    if f.divides(1 - x^N):
        print(f"N = {N}")
        break    # the for loop in the variable N

We get $N=7560=2^3\cdot 3^3\cdot 5\cdot 7$.

Now we forget about this polynomial ring, work in the power series ring, and search for a multiple of $7560$ that does the job not only modulo $3$, but also modulo $9$.

n    = 7560
PREC = 100*n
ring = Integers(9)    # this is ZZ / 9
 
R.<x> = PowerSeriesRing(ring, default_prec=PREC)
f = prod([1 - x^d for d in [1..m]])
for k in [1..100]:
    N = k*n    # N is a multiple of 7560, check it
    g = 1 - x^N
    if (g/f).polynomial() * f == g:
        print(f"N = {N} = {k}*{n}")
        break

We immediately get

N = 22680 = 3*7560

To be exact, we have tested the "polynomial equality" in a power series ring, so one more check is needed in order to have it also in the polynomial ring. I am using capital letters for the "same" objects in the polynomial world.

m, N, PREC = 9, 3*7560, 30*7560
R.<x> = PowerSeriesRing(Integers(9), default_prec=PREC)
S.<X> = PolynomialRing(Integers(9))

F = prod([1 - X^d for d in [1..m]])    # polynomial in R
G = 1 - X^N                            # polynomial in R

q = G(x) / F(x)                        # power series (quotient) in S
Q = q.polynomial()(X)                  # polynomial in R

print(f"Is G = F*Q? {G == F*Q}")

and we get:

Is G = F*Q? True

So we also have the pair $(m,t)=(9, 22680)$.

Answer 2

You have in general $$A - B = \frac{x^{m(m-1)/2 - t} (x^t - 1)}{(x-1)(x^2-1)} $$ Let's assume $t$ is even, so $x^t - 1 = (x^{t-2} + x^{t-4} + \ldots + 1)(x^2 - 1)$.
Call this $P(x)(x^2-1)$, and let $k = t - m (m-1)/2$, so that $$ A - B = \frac{P(x)}{x^k (x-1)} $$ This has a partial fraction decomposition of the form $$ \frac{r}{x-1} + \sum_{j=-k}^{m(m-1)/2-3} c_j x^j $$ where $r$ is the residue of $A-B$ at $x=1$, which is $P(1) = t/2$. When you expand $A-B$ in its Laurent series, the coefficients of $x^j$ for $j > m(m-1)/2-2$ will all be $-t/2$. So for those to be $\equiv 0 \pmod m$, you need $t/2$ to be divisible by $m$.

But it seems you want all coefficients for positive $j$ to be $\equiv 0 \pmod m$, i.e. $c_j \equiv 0 \pmod m$ for $1 \le j \le m(m-1)/2 - 3$. For $m = 2$ or $m=3$ that wasn't a problem, as $m(m-1)/2 - 3 \le 0$, but for $m \ge 4$ it will be. In fact, as $x \to +\infty$, $A - B \sim x^{m(m-1)/2 - 3}$, so we ll always have $c_{m(m-1)/2-3} = 1$. Thus you'll never get all coefficients of positive powers to be $\equiv 0 \pmod m$ when $m \ge 4$ and $t$ is even.