22
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What you write requires $n > 1$. At $n = 1$ it breaks down, since $\Phi_1(1) = 0$ and $b_0$ is not really defined. $\endgroup$ – KConrad May 22 '14 at 21:58
  • 3
    $\begingroup$ 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)$. $\endgroup$ – KConrad May 22 '14 at 22:00
  • 9
    $\begingroup$ <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> $\endgroup$ – Tom Lovering May 23 '14 at 0:44
  • 2
    $\begingroup$ Every proof that I tried goes through $c_n$... $\endgroup$ – i707107 May 23 '14 at 0:58
  • $\begingroup$ Your `ideal' situation provides only $b_n\mid a_n$. Is it enough for you? $\endgroup$ – Ilya Bogdanov May 23 '14 at 12:56
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Very interesting! Has anyone considered a q-analog of the Lazard ring / universal formal group? $\endgroup$ – მამუკა ჯიბლაძე May 25 '14 at 7:18
  • 3
    $\begingroup$ 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$. $\endgroup$ – KConrad May 25 '14 at 7:46
  • $\begingroup$ I changed things and made more explicit note of this. $\endgroup$ – Aaron Meyerowitz May 27 '14 at 9:11
  • $\begingroup$ Your commutative ring should be an integral domain, I assume? $\endgroup$ – darij grinberg May 27 '14 at 10:41
  • 3
    $\begingroup$ 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 . $\endgroup$ – darij grinberg May 27 '14 at 10:47
3
$\begingroup$

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$.

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

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.$$

$\endgroup$
  • 1
    $\begingroup$ This does not mention the numbers $b_n$, and so does not answer the question as asked. $\endgroup$ – Neil Strickland Oct 19 '15 at 7:55
  • $\begingroup$ $b_n=c_n$ by Kummer's theorem en.wikipedia.org/wiki/Kummer%27s_theorem $\endgroup$ – Alexey Ustinov Oct 19 '15 at 7:59
  • $\begingroup$ Yes, the question says that there are many known proofs that $a_n=c_n$ and that $b_n=c_n$. $\endgroup$ – Neil Strickland Oct 19 '15 at 8:01
  • 1
    $\begingroup$ Both proofs are almost in one line. It is strange that you insist on simpler arguments. What is hinder you to use these arguments? $\endgroup$ – Alexey Ustinov Oct 19 '15 at 8:20
  • 4
    $\begingroup$ 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\}$. $\endgroup$ – Neil Strickland Oct 19 '15 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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