# Show $100+t$ is reducible in $\mathbb{Z}[[t]]$

$\mathbb{Z}[[t]]$ is the ring of formal power series with integer coefficients, and the problem asks to show that $100+t$ is reducible. This means I need to find two power series, $\sum_{i=0}^\infty a_i t^i$ and $\sum_{j=0}^\infty b_j t^j$ with $a_i,b_j\in\mathbb{Z}$, that when multiplied give $100+t$. Since the integers are an integral domain, I know that neither of these power series may be finite, but I'm having a really hard time figuring out how to come up with two series that will telescope properly. Any suggestions?

-
+1 Interesting question. Where does it come from? –  Bill Dubuque Mar 26 '12 at 0:30
An old qualifying exam. –  chris Mar 26 '12 at 3:15

Hint  The Catalan series $\rm\: C(x)\in \mathbb Z[[x]]\:$ satisfies $\rm\:\color{#c00}{C(x) - x\:C(x)^2 = 1},\:$ so if $\rm\ ad\!-\!bc=1,\,\ e = cd$

$\qquad\quad \rm (a - ct\:C(et))\:(b+dt\:C(et))\ =\ ab + t\:(\color{#c00}{C(et) - et\:C(et)^2})\: =\ ab + t$

By Bezout, $\rm\: ad\!-\!bc=1\iff gcd(a,b) =1;\:$ if so we can split $\rm\:ab+t\:$ in $\rm\:\mathbb Z[[t]]$ as above.

Remark $\$ Below is the method that I used to discover this empirically.

By undetermined coefficients and an OEIS lookup one deduces empirically that $$\rm\ 100 + t\: =\: (4 + f(t))\:(25 - 6\: f(t))\quad where$$ $$\rm f(t)\: =\: t\:C(6t)\: =\: t\sum_{n\:=\:1}^{\infty}\: C_n (6t)^n\ =\ t + 6\: t^2 + 72\: t^3 + 1080\: t^4 + 18144\: t^5 +\:\ldots$$

where $\rm\displaystyle\ \ C_n =\: {\rm Catalan}(n)\:=\:\dfrac{1}{n+1}{2n\choose n}\ =\ \frac{(2n)!}{n!\:(n+1)!}\$ with generating function

$$\smash[b]{\rm C(t)\: =\ \sum_{n\:=\:0}^{\infty} C_n t^n\ =\ {\dfrac{1-\sqrt{1-4t}}{2t}}}$$ This yields the closed form $$\begin{eqnarray}{}\rm 100 + t &=&\rm\ \ (4\ +\ t\:C(6t))\ \ \ \ (25\ -\ 6t\:C(6t))_{\phantom{M_{M_M}}} \\ &=&\rm \dfrac{49 - \sqrt{1-24\:t}}{12}\ \dfrac{49 + \sqrt{1-24\:t}}{2}\\ \end{eqnarray}$$

In fact, employing the Catalan functional equation $\rm\ \color{#c00}{C(x) - x\:C(x)^2 = 1}\:$ we confirm $$\rm\ (4 + t\:C(6t))\:(25-6t\:C(6t))\ =\ 100 + t\:\color{#c00}{(C(6t)-6t\:C(6t)^2})\ =\ 100 + t\quad\ QED$$

-
This solution is particularly appealing given that I lectured on the Catalan numbers 2 weeks ago. –  chris Mar 25 '12 at 23:56

You want to find $(a_i)$ and $(b_i)$ such that $(\sum_i a_i t^i) (\sum_i b_i t^i) = 100+t$. Multiply this out and compare the coefficients: $$a_0 b_0 = 100\\ a_0 b_1+a_1 b_0 = 1\\ a_0 b_n + a_1 b_{n-1} + \ldots + a_{n-1} b_1 + a_n b_0 = 0 \quad \text{for } n \geq 2$$ The second equation tells you that you should choose $a_0$ and $b_0$ coprime, so let $a_0 := 2^2$ and $b_0 := 5^2$. From this you can inductively construct all the coefficients $(a_i)$ and $(b_i)$, but I let you do the details.

-
This was my first approach but I don't think it works out. To define the coefficients inductively there needs to be a formula that only relies on the previous terms, but at each stage you actually have to choose new coefficients. Above, we need to choose $a_1,b_1$ such that $4b_1+25a_1=0$ but there are an infinite number of such $a_1,b_1$ since 4 and 25 are coprime. At the next level, you have $4b_2+25a_2+a_1 b_1=0$. Once we chosen $a_1$ and $b_1$ we're again left with an infinite number of choices for $a_2$ and $b_2$. I don't see how to use induction this way. –  chris Mar 25 '12 at 19:51
You could turn it into a deterministic algorithm by choosing always the pair $(a_n,b_n)$ that is minimal with respect to a fixed enumeration of $\mathbb Z \times \mathbb Z$. Then the sequences $(a_i)$ and $(b_i)$ should be well-defined since for each $i$ you can deterministically compute $a_i$ and $b_i$ in a finite number of steps. –  marlu Mar 26 '12 at 0:00

First, solve it modulo $t$. Then modulo $t^2$. Then....

Splitting $100 = 25 \cdot 4$ is the only choice, because that is the only way to factor $100$ into relatively prime parts. this is important for reasons that will be clear if you try to apply the method below)

So, I've chosen

• $f \equiv 25 \pmod t$
• $g \equiv 4 \pmod t$

To set some terminology, let

• $f_n$ be the truncation of $f$ to degree $n$
• $g_n$ be the truncation of $g$ to degree $n$
• $a_n$ be the coefficient of $t^n$ in $f$
• $b_n$ be the coefficient of $t^n$ in $g$

Now, to get the coefficient on $t$:

• $(f_0 + t a_1) (g_0 + t b_1) = 100 + t (4 a_1 + 25 b_1) \pmod {t^2}$

So I need do an extended GCD and decide upon $a_1 = -6$ and $b_1 = 1$.

Now, induct. By hypothesis, we may assume

$$f_{n-1} g_{n-1} \equiv 100 + t \pmod {t^n}$$

and going up a degree gives

$$f_{n-1} g_{n-1} \equiv 100 + t + t^n c_n \pmod{ t^{n+1}}$$

for some value of $c_n$.

\begin{align} f_n g_n &= (f_{n-1} + a_n t^n) (g_{n-1} + b_n t^n) & \pmod {t^{n+1}} \\ &= 100 + t + t^n (c_n + a_n g_{n-1}(0) + b_n f_{n-1}(0)) & \pmod{ t^{n+1}} \\ &= 100 + t + t^n (c_n + 4 a_n + 25 b_n ) & \pmod{ t^{n+1}} \end{align}

From which it's clear that we can solve for $a_n$ and $b_n$. e.g. $a_n = 6 c_n$ and $b_n = -c_n$

Since we obtain $f_n$ and $g_n$ for all $n$, we get a solution for $f$ and $g$.

EDIT: Notice at this point, we can observe that one of the solutions has $a_n = -6 b_n$ for $n > 0$, and so we could write $100 = (25 + 6 t h(x)) (4 - t h(x))$, and then segue into Bill Dubuque's method.

-