Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\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?

share|cite|improve this question
+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
up vote 14 down vote accepted

To split $\rm\,ab + t\,$ with $\rm\,\gcd(a,b)=1,\,$ write $\rm\ \color{#c00}{\bf 1} = ad\!-\!bc\,$ by Bezout's GCD identity.

Recall the Catalan series $\rm\, C(x)\in \mathbb Z[[x]]\,$ satisfies $\rm\,\color{#090}{C(x) - x\:C(x)^2\! = 1},\,$ so with $\rm\,e = cd$

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

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)) \\[0.4em] &=&\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{#090}{C(x) - x\:C(x)^2 = 1}\:$ we confirm $$\rm\ (4 + t\:C(6t))\:(25-6t\:C(6t))\ =\ 100 + t\:(\color{#090}{C(6t)-6t\:C(6t)^2})\ =\ 100 + t\quad QED $$

share|cite|improve this answer
This solution is particularly appealing given that I lectured on the Catalan numbers 2 weeks ago. – chris Mar 25 '12 at 23:56
I knew it was you when I saw your colours :~). +1. – YoTengoUnLCD May 12 at 2:20

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.