# Is there a better proof of this fact in number theory/formal group theory?

Let $\Phi_n$ be the $n$'th cyclotomic polynomial, and put \begin{align*} a_n &= \Phi_n(1) \\ b_n &= \gcd\left(\left(\begin{array}{c} n \\ 1\end{array}\right),\dotsc,\left(\begin{array}{c} n \\ n-1\end{array}\right)\right) \\ c_n &= \begin{cases} p & \text{ if } n = p^k \text{ for some prime } p \text{ and } k>0 \\ 1 & \text{ otherwise. } \end{cases} \end{align*} It is well-known that $a_n=b_n=c_n$. Indeed, there are a bunch of ways to prove that $a_n=c_n$, and a bunch of ways to prove that $b_n=c_n$. I ask: is there a more direct proof that $a_n=b_n$? A good answer might give a tidier approach to some fundamental results in formal group theory. Ideally I'd like a proof that expresses $a_n$ as a $\mathbb{Z}$-linear combination of binomial coefficients as in $b_n$.

• What you write requires $n > 1$. At $n = 1$ it breaks down, since $\Phi_1(1) = 0$ and $b_0$ is not really defined. – KConrad May 22 '14 at 21:58
• This reminds me of the fact that when $f(x) = \sum_{k =0}^n d_k\binom{x}{k}$ with integers $d_k$, we have $\gcd(d_0,d_1,\dots,d_n) = \gcd_{m \in \mathbf Z} f(m)$. – KConrad May 22 '14 at 22:00
• <troll> In the divisibility poset $0$ is maximal, so surely it's appropriate to say it's the greatest common divisor of an empty set? </troll> – Tom Lovering May 23 '14 at 0:44
• Every proof that I tried goes through $c_n$... – Sungjin Kim May 23 '14 at 0:58
• Your `ideal' situation provides only $b_n\mid a_n$. Is it enough for you? – Ilya Bogdanov May 23 '14 at 12:56

## 3 Answers

Define $a_n=\Phi_n(1)$ except $a_1=1$. These values are uniquely determined by $$n=\prod_{d \mid n}a_d.$$ From this it would be quick to get $a_n=c_n$ but , as requested, we won't. An important step is to observe that $\gcd(a_m,a_n)=1$ if $\gcd(m,n)=c \lt m \lt n.$ This follows from $\gcd(\frac{m}{c},\frac{n}{c})=1$ by writing $m,n,c$ as products of the $a_i$ and simplifying.

If follows that $$n!=\prod_{k=1}^na_k^{\lfloor n/k\rfloor}$$ and $$\binom{n}{m}=\frac{n!}{m!(n-m)!}=\prod_{k \le n}a_k^{e_{n,m,k}}$$ where the exponent $$e_{n,m,k}=\lfloor n/k \rfloor-\lfloor m/k \rfloor-\lfloor (n-m)/k \rfloor$$ Note that $0 \le e_{n,m,k} \le 1$ and $e_{n,m,k}=0$ if $k \mid m$ and $k \mid n.$

We hope to show that $$\gcd{\Large (}\binom{n}{1},\binom{n}{2},\cdots,\binom{n}{n-1}{\Large )}=a_n.$$ We certainly know that $a_n$ divides each of these binomial coefficients. We will now see that it is sufficient to consider just $\binom{n}{1}$ and the various $\binom{n}{n/p}$ as $p$ ranges over the prime divisors of $n.$

Let $n=q_1q_2\cdots q_j$ where the $q_j=p_j^{e_j}$ are powers of distinct primes and define $G_0=\binom{n}{1}$ and $G_i=\gcd(G_{i-1},\binom{n}{n/p_i})$ for $1 \le i \le j.$ Then $G_i$ is the product of the $a_k$ with $q_1q_2\cdots q_i \mid k \mid n.$ and $G_j=a_n$

I will illustrate with the example of $n=900=2^23^25^2$. So $G_0=\binom{900}{1}$, $G_1=\gcd(G_0,\binom{900}{900/2})$, $G_2=\gcd(G1,\binom{900}{900/3})$ and $G_3=\gcd(G_2,\binom{900}{900/5}).$ I claim that $G_3=a_{900}.$

$G_0=\binom{900}{1}$ is the product of the $26$ $a_k$ with $1 \lt k \mid 900.$ Of these, the $9$ which are multiples of $2^2$, namely $a_4,a_{12},a_{20},a_{36},a_{60},a_{100},a_{180},a_{300}$ and $a_{900}$ also divide $\binom{900}{900/2}=\binom{900}{450}$, the other $17$ have $e_{900,450,k}=0.$ There are many other $a_k$ with $e_{900,450,k}=1$ but all of them are relatively prime to $G_0$ by the important step above. Hence $G_1$ is exactly the product of the $9$ $a_k$ with $4 \mid k \mid 900$. Now $G_2=\gcd(G_1,\binom{900}{300})=a_{36}a_{180}a_{900}$ because the only other $a_k$ dividing $\binom{900}{300}$ are such that $k$ neither divides nor is a multiple of $4,12,20,60,100,300$ and hence all are relatively prime to $G_1$ by the important step. Finally $G_3=\gcd(G_2,\binom{900}{180})=a_{900}$ because the only other $a_k$ with $e_{900,180,k}=1$ are relatively prime to both $a_{36}$ and $a_{180}$.

I believe this does what was requested.

It may be helpful to look at a more abstract setting where essentially the same proof goes through. The idea is to replace each integer $n$ by a generalized integer $I_n$, replace $a_n$ by some appropriate $A_n$, define a generalized factorial $[I_n]!=I_1I_2\cdots I_n$ and then a generalized binomial coefficient $${n \brack m}=\frac{[I_n]!}{[I_m]![I_{n-m}]!},$$ and deduce that $\gcd\left( {n \brack 1},{n \brack 2},\cdots,{n \brack {n-1}}\right)=A_n$. What is meant by $\gcd$ needs to specified in some cases.

Suppose that we have a commutative ring $\mathcal{R}$ and within it a sequence of elements $I_1,I_2,I_3,\cdots$ with the property

$$\gcd(I_m,I_n)=I_{\gcd(m,n)} \tag{**}$$

or perhaps merely the weaker property

$I_d \mid I_n$ when $d\mid n$ $(*)$

Based just on $(*)$ we have that there are elements $A_1,A_2,\cdots$ uniquely defined by $I_n=\prod_{d\mid n}A_d.$ (Although we will not need it, it then follows that $A_n=\prod_{d\mid n}I_n^{\mu(n/d)}$ where $\mu$ is the classic Mobius function.)

A familiar and obvious choice with (**) is $I_n=1+X+\cdots+X^{n-1}.$ Then we have the cyclotomic polynomials $A_n=\Phi_n(X)$ defined by $$I_n=\prod_{d\mid n}A_d.$$ (Except that $A_1=1$.)

Examples with (*) include

1. $I_n=n$ in $\mathbb{N}$
2. The Fibonacci numbers $F_n$ in $\mathbb{N}$
3. $I_n=u^n-v^n$ in $\mathbb{Z}[u,v]$
4. $I_n=\frac{u^n-v^n}{u-v}=\Sigma_{k=0}^{n-1}u^{n-k-1}v^{k}$ in $\mathbb{Z}[u,v]$

Asides: We will always be able, if desired, to assume $A_1=I_1=1$ by replacing $I_n$ with $\frac{I_n}{I_1}$ as in 4. Example 1 is the case $u=v=1$ of 4 while example 2 is the case $u,v=(1\pm \sqrt{5})/2$ with the convenient feature $uv=-1$. The obvious choice above is example 4 with $u=X,v=1.$

In any case, given just (*) we can define a generalized factorial $$[I_n]!=I_1I_2I_3\cdots I_n$$ and it follows that $$[I_n]!=\prod_{k=1}^nA_k^{\lfloor n/k\rfloor}$$ as in the integer case.

We can also define a generalized binomial coefficient by

$${n \brack m}=\frac{[I_n]!}{[I_m]![I_{n-m}]!}=\prod_{k \le n}A_k^{e_{n,m,k}}$$

The argument above becomes $\gcd\left( {n \brack 1},{n \brack 2},\cdots,{n \brack {n-1}}\right)=A_n$ provided we do have the stronger condition $(**)$. This requires knowng what is meant by $\gcd$ and that it behaves as expected. I don't think (**) holds for example 4, but it does when $v=1$. The fact that it hold in the case of example 2 is perhaps due to the extra relation $uv=-1$.

In a ring $\mathcal{R}$ I will take as the definition of $\gcd(U,V)=W$ ($W$ is a gcd of $U$ and $V$) to be

$W \mid U$ and $W \mid V$ and $US+VT=W$ for some $S,T \in \mathcal{R}$.

Note that we do not assume that every pair $U,V$ have a $\gcd$. In $\mathbb{Z}[X]$ We do not have a $\gcd$ for $U=\Phi_4=X^2+1$ and $V=\Phi_2=X+1$. We can get $US+VT=2$ but not $1$.

Actually finding the the explicit cofactors might be impractical.

The fact that they exist follows (in certain of the examples above) from

• $1n-1m=n-m$
• $| F_{m+1}F_n-F_{n+1}F_m |= F_{n-m}$
• $1\frac{X^n-1}{X-1}-X^{n-m}\frac{X^m-1}{X-1}=\frac{X^{n-m}-1}{X-1}$

but even in the first case we don't have a simple way to explicitly find $s,t$ with $ns+mt=\gcd(n,m)$, even in the case that the right-hand side is $1.$ Furthermore, the claim that this $\gcd$ behaves appropriately depends on iterated application of facts such as:

Given (in some ring) that $\gcd(U,V)=\gcd(U,V')=1$ in the sense that there are $S,T,S',T'$ with $US+TV=1$ and $U'S'+T'V'=1$, it follows that $\gcd(U,VV')=1$ since $$U{\LARGE(}USS'+ST'V'+S'TV{\LARGE)}+VV'(TT')=1.$$

It is something I have asked about before, although not very clearly.

• Very interesting! Has anyone considered a q-analog of the Lazard ring / universal formal group? – მამუკა ჯიბლაძე May 25 '14 at 7:18
• Your "obvious choice" $I_n = 1 + X + X^2 + \cdots + X^{n-1}$ is wrong if it is to be the product of $d$th cyclotomic polynomials for *all* $d$ dividing $n$. For that you need $I_n = X^n - 1$. – KConrad May 25 '14 at 7:46
• I changed things and made more explicit note of this. – Aaron Meyerowitz May 27 '14 at 9:11
• Your commutative ring should be an integral domain, I assume? – darij grinberg May 27 '14 at 10:41
• Nice construction! As far as I remember, some answers about when cyclotomic polynomials have a gcd in the strong sense in $\mathbb{Z}\left[X\right]$ can be found in G. Dresden, Resultants of Cyclotomic Polynomials, home.wlu.edu/~dresdeng/papers/Res.pdf . – darij grinberg May 27 '14 at 10:47

Inspired by the previous answer I am thinking about simplest possible ways to prove $$gcd\left(\binom n1_q,...,\binom n{n-1}_q\right)=\Phi_n(q).$$ One most primitive way to do it is to check that both sides have the same roots. On the left, multiplicity of a primitive root of unity of degree $k$ is $$\min\left\{\left[\frac nk\right]-\left[\frac mk\right]-\left[\frac{n-m}k\right]\ |\ m=1,...,n-1\right\}$$ and it must not be difficult to show that this is 0 for $k\ne n$ and 1 for $k=n$.

• For $k>n$, its obviously zero and for $k=n$, its obviously $1$. For $k<n$, take $m=k$ to get $0$. – David E Speyer May 29 '14 at 16:03
• Right, thanks. Except it is somehow not totally clear to me whether this after all answers the original question... – მამუკა ჯიბლაძე May 29 '14 at 16:05

This answer seemed to be a simplification of arguments given by Aaron Meyerowitz.

As it was mentioned numbers $a_n=\Phi_n(1)$ are uniquely determined by $$n=\prod_{d \mid n}a_d.$$ So it is sufficient to check that numbers $c_n$ satisfy the same equation. But $c_n=e^{\Lambda(n)}$, where $$\Lambda(n)=\begin{cases} \log p & \text{ if }n = p^k, \\ 0 & \text{otherwise}, \end{cases}$$ and verification of identity $n=\prod_{d \mid n}c_d$ is an easy exercise.

We can express $a_n$ as a $\mathbb{Z}$-linear combination of binomial coefficients as in $b_n$ in the following way (this construction is taken from the paper Coefficient rings of formal groups).

If $n=p^k$ then $\binom{n}{p^{k-1}}\equiv p\pmod{p^2},$ so we can easely find $\lambda_{p^{k-1}}$ such that $\lambda_{p^{k-1}}\binom{p^k}{p^{k-1}}\equiv p\pmod {p^{k}}$. So for some $\lambda_{1}$ $$\lambda_{p^{k-1}}\binom{p^k}{p^{k-1}}+\lambda_{1}\binom{p^k}{1}=p.$$

Now let $n=p_1^{k_1}\ldots p_s^{k_s}$, where $s>1$. Then by Kummer's theorem $\mathrm{ord}_{p_i}\binom{n}{p_i^{k_i}}=0$ and $\mathrm{ord}_{p_j}\binom{n}{p_i^{k_i}}\ge k_j$ ($j\ne i$). Taking $\lambda_{p_i^{k_i}}\equiv \binom{n}{p_i^{k_i}}^{-1}\pmod{p_i^{k_i}}$ we'll have $$\lambda_{p_1^{k_1}}\binom{n}{p_1^{k_1}}+\ldots+\lambda_{p_s^{k_s}}\binom{n}{p_s^{k_s}}\equiv 1\pmod n.$$ So for some $\lambda_1$ $$\lambda_{p_1^{k_1}}\binom{n}{p_1^{k_1}}+\ldots+\lambda_{p_s^{k_s}}\binom{n}{p_s^{k_s}}+\lambda_{1}\binom{n}{1}=1.$$

• This does not mention the numbers $b_n$, and so does not answer the question as asked. – Neil Strickland Oct 19 '15 at 7:55
• $b_n=c_n$ by Kummer's theorem en.wikipedia.org/wiki/Kummer%27s_theorem – Alexey Ustinov Oct 19 '15 at 7:59
• Yes, the question says that there are many known proofs that $a_n=c_n$ and that $b_n=c_n$. – Neil Strickland Oct 19 '15 at 8:01
• Both proofs are almost in one line. It is strange that you insist on simpler arguments. What is hinder you to use these arguments? – Alexey Ustinov Oct 19 '15 at 8:20
• I did not ask for a simpler proof, I asked for a more direct one. "More direct" means that it should be formulated in terms of the algebra of roots of unity and the combinatorics of subsets of $\{1,\dotsc,n\}$. – Neil Strickland Oct 19 '15 at 8:25