Tag Archives: root of unity

Binomial sum modulo prime power: Part 2

Let $p$ be a prime number and $\omega=\exp(2\pi i/p)$. Recall that we conjectured in this post that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

is divisible by $p^{\lceil n/(p-1)\rceil}$. From exercise 2 of this post we know that $(p)$ factors as $(p,\omega-1)^{p-1}$ into prime ideals in the ring $\mathbb Z[\omega]$. So $(\omega-1)^{p-1}\in (p)$. Therefore the right-hand side of $(*)$ is divisible by $p^{\lfloor n/(p-1)\rfloor}$. So we are off by at most one factor of $p$! I believe this approach can be improved upon to account for the extra factor, since we haven’t used any property of the sum.

Furthermore,

$\displaystyle\sum_{j=0}^{p-1}\omega^{-rj}(1-\omega^j)^n=p\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}$

for any $r$. So our best result thus far is the following:

Theorem (weaker version of Fleck’s).

$\displaystyle\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\lfloor\frac{n}{p-1}\rfloor-1}}$.

Goal: Improve the floors to ceilings.

Filed under Algebra, Number theory

Ring of integers of cyclotomic field

Let $\zeta=\zeta_n=e^\frac{2\pi i}{n}$ be a primitive $n$-th root of unity, and let $K=\mathbb Q(\zeta)$. I am going to outline a proof that $\mathcal O_K=\mathbb Z[\zeta]$, based on several homework problems from one of my recent courses. There are probably many other proofs of this, but I particularly like this one because it’s easy to follow, touches on a wide range of topics, and I worked hard through it!

First, let $n=p^m$ be a prime power. The minimal polynomial of $\zeta$ is the $n$-th cyclotomic polynomial

$\displaystyle\Phi_n(X)=\Phi_{p^m}(X)=\sum_{j=0}^{p-1}X^{jp^{m-1}}$.

Let $f(X)=\Phi_n(X+1)$.

Exercise 1. Following the above notation, show that $f$ satisfies the conditions of Eisenstein’s criterion for the prime $p$.

Consider the discriminant $\Delta(f)=\Delta(R)$, where $R=\mathbb Z[\zeta-1]$. If $q$ is a prime factor of $\Delta(f)$, then $f$ must have a multiple root modulo $q$. Hence $X^{p^m}-1$ will also have a multiple root modulo $q$. But $\gcd(X^{p^{m}}-1, p^{m}X^{p^{m}-1})=1$ in $\mathbb Z/q\mathbb Z$ unless $q=p$. Thus $\Delta(f)=\Delta(R)=[\mathcal O_K:R]^2\Delta(\mathcal O_K)$ is a power of $p$. In particular, $[\mathcal O_K:R]$ is a power of $p$.

Exercise 2. Suppose that $f\in\mathbb Z[X]$ satisfies the conditions of Eisenstein’s criterion for a prime number $p$. Let $\alpha$ be a root of $f$ and let $R=\mathbb Z[\alpha]$. Prove that there is exactly one prime ideal $P\subseteq R$ that contains $p$, and that the local ring $R_P$ is a DVR with uniformiser $\alpha$.

Now if $Q\subseteq R$ is another prime ideal, then $p\not\in Q$. So $[\mathcal O_K:R]\not\in Q$.

Exercise 3. Let $K$ be a number field and $R\subseteq\mathcal O_K$ a subring of finite index $d$. If $Q\subseteq R$ is a prime ideal not containing $d$, show that $R_Q$ is a DVR.

I’ll include this solution because I love it!

Solution. Let $D=\mathcal O_K$. By going up, there is a prime ideal $\tilde Q\subseteq D$ with $\tilde Q\cap R=Q$. We’ll show that $D_{\tilde Q}=R_Q$, so the result will follow.

Let $a/b\in R_Q$, so that $a\in R$, $b\in R\setminus Q$. If $b\in \tilde Q$, then $b\in R\cap \tilde Q=Q$, a contradiction. Hence $b\not\in\tilde Q$, i.e. $a/b\in D_{\tilde Q}$. Thus $R_Q\subseteq D_{\tilde Q}$.

Now let $a/b\in D_{\tilde Q}$, so that $a\in D$, $b\in D\setminus\tilde Q$. Then $da\in R$, $db\in R$, and $a/b=(da)/(db)$. Note that $b\not\in\tilde Q\supseteq Q$, and $d\not\in Q$ by assumption. So $db\not\in Q$ since $Q$ is a prime ideal. Thus $a/b=(da)/(db)\in R_Q$, i.e. $D_{\tilde Q}=R_Q$. $\square$

So $R$ localised at any prime ideal is a DVR, implying that $R=\mathbb Z[\zeta]$ is a Dedekind domain. Thus $R=\mathcal O_K$. This completes the proof for the prime power case.

Now we proceed by induction on the number of distinct prime factors of $n$. The base case has already been taken care of. So suppose that $n=ab$, where $a,b>1$ are coprime integers. Let $L=\mathbb Q(\zeta_a)$ and $M=\mathbb Q(\zeta_b)$. By the induction hypothesis, $\mathcal O_L=\mathbb Z[\zeta_a]$ and $\mathcal O_M=\mathbb Z[\zeta_b]$.

Exercise 4. Let $L$ and $M$ be number fields with discriminants $\lambda$ and $\mu$ respectively. Let $\{a_1,\dots,a_m\}$ and $\{b_1,\dots,b_n\}$ be integral bases for $L$ and $M$ respectively. Let $K=LM=\mathbb Q(a_1,\dots,a_m,b_1,\dots,b_n)$ be the composite field of $L$ and $M$. Suppose that $[K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q]$ and that $\gcd(\lambda,\mu)=1$. Show that $\{a_ib_j:1\le i\le m; 1\le j\le n\}$ is an integral basis for $K$.

So our main result will follow from exercise 4 once we have checked that all the hypotheses are satisfied.

(i) Checking $K=LM$Firstly, $LM$ contains $\zeta_a\zeta_b=e^{\frac{2\pi i(a+b)}{n}}=\zeta^{a+b}$.

Exercise 5. If $\gcd(a,b)=1$, show that $\gcd(a+b,ab)=1$.

So writing $j=a+b$ shows that $\gcd(j,n)=1$ and $\zeta^j\in LM$. If $j^{-1}\in\{1,\dots,n\}$ is the multiplicative inverse of $j\pmod n$, then $\zeta=(\zeta^j)^{j^{-1}}\in LM$. Thus $K\subseteq LM$.

Again, since $\zeta^a=\zeta_b$ and $\zeta^b=\zeta_a$, we have $LM\subseteq K$. Thus $K=LM$.

(ii) Checking $[K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q]$. We have

$[K:\mathbb Q]=\varphi(n)=\varphi(ab)=\varphi(a)\varphi(b)=[L:\mathbb Q][M:\mathbb Q]$.

(iii) Checking $\gcd(\lambda,\mu)=1$This is slightly harder. We need a few more facts.

Exercise 6. Let $E=\mathbb Q(\alpha)$ be a number field, and let $f$ be the minimal polynomial of $\alpha$. Show that

$\Delta(\alpha)=(-1)^{\binom{\deg(f)}{2}}N_{E/\mathbb Q}(f'(\alpha))$.

Solution. Let $f(x)=(x-\alpha_1)\cdots(x-\alpha_n)$. Then

$\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_{i\neq j}(\alpha_i-\alpha_j)=(-1)^{\binom n2}\prod_i\prod_{j\neq i}(\alpha_i-\alpha_j)$.

Using Leibniz’s rule,

$\displaystyle f'(x)=\sum_i\prod_{j\neq i}(x-\alpha_i)\Rightarrow f'(\alpha_i)=\prod_{j\neq i}(\alpha_i-\alpha_j)$.

Hence

$\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_if'(\alpha_i)=(-1)^{\binom n2}N_{E/\mathbb Q}(f'(\alpha))$. $\square$

Exercise 7. Using the previous exercise, show that $\Delta(\zeta_n)\mid n^{\varphi(n)}$.

Hint. Write $X^n-1=\Phi_n(X)g(X)$, and use Leibniz’s rule to get $n\zeta_n^{n-1}=\Phi_n'(\zeta_n)g(\zeta_n)$.

So $\lambda=\Delta(\zeta_a)$ divides some power of $a$, and $\mu=\Delta(\zeta_b)$ divides some power of $b$. Since $\gcd(a,b)=1$, we conclude that $\gcd(\lambda,\mu)=1$.

1 Comment

Filed under Algebra, Number theory

Binomial sum modulo prime power: Part 1

In the last post we showed that

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$

and then we used Lucas’ theorem to evaluate the sum modulo $p$.

My initial attempt at evaluating the sum was to note that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

where $\omega=\exp(2\pi i/p)$, but then I was stuck. Numerical examples suggested that this sum is in fact divisible by $p^{\lceil n/(p-1)\rceil}$, but I could not think of a way of extending the argument from the last post. Nonetheless, some extensive google search recently revealed that

Theorem (Fleck, 1913). For any $j$,

$\displaystyle\sum_{m\equiv j\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\left\lfloor \frac{n-1}{p-1}\right\rfloor}}$.

So taking $j=0$ gives the desired claim after noting that

Fact. $\displaystyle \left\lfloor\frac{n-1}{p-1}\right\rfloor+1=\left\lceil\frac{n}{p-1}\right\rceil$.

Proof. Write $n=q(p-1)+r$ with $0\le r. If $r=0$ then the equation is just $q-1+1=q$, and if $r>0$ then it is $q+1=q+1$. $\square$

This article contains a proof of Fleck’s result using the identity $(*)$. Unfortunately I don’t have a good grasp of the theory behind it.

Filed under Number theory

A generalisation of Pell’s equation

We want to find the solutions to

$(*)\qquad x^2+mxy+ny^2=1$

over the integers, where $m,n\in\mathbb Z$.

Let $\alpha$ and $\bar\alpha$ be the roots of $x^2+mx+n=0$. We can factorise $(*)$ as $(x-y\alpha)(x-y\bar\alpha)=1$. If $\alpha$ is rational, it must be an integer and then it is easy to find all solutions. So let us consider the more interesting case where $\alpha$ is not rational (i.e. $\sqrt{m^2-4n}\not\in\mathbb Z$).

Now a solution in the form $z=x-y\alpha$ to $(*)$ is a unit in the ring $\mathbb Z[\alpha]$. For $z=x-y\alpha\in\mathbb Z[\alpha]$, denote its conjugate by $\bar z=x-y\bar\alpha$. Then we have the multiplicative norm

$N(z)=N(x-y\alpha)=z\bar z=x^2+mxy+ny^2$.

It follows that the solutions to $(*)$ form a subgroup $S$ of the multiplicative group of units of $\mathbb Z[\alpha]$.

Case 1: $m^2< 4n$. Then $(*)$ defines an ellipse, so there are at most finitely many solutions, i.e. $S$ is a finite subgroup of $\mathbb C^\times$. Hence $S$ is cyclic and every solution is of the form

$\displaystyle x-y\alpha=\cos\frac{2\pi t}{k}+i\sin\frac{2\pi t}{k},\quad x-y\bar\alpha=\cos\frac{2\pi t}{k}-i\sin\frac{2\pi t}{k}$

$\displaystyle \Rightarrow 2x+my=2\cos\frac{2\pi t}{k}\in [-2,2]\cap\mathbb Z\Rightarrow \cos\frac{2\pi t}{k}\in\{0,\pm\frac 12,\pm1\}$

$\displaystyle\Rightarrow x-y\alpha\in\{\pm 1,\pm i, \frac{1\pm i\sqrt 3}{2}, \frac{-1\pm i\sqrt 3}{2}\}$.

Case 2: $m^2>4n$. Now $\alpha$ is real, so $S$ is a subgroup of $\mathbb R^\times$.

Claim. $S$ is not dense.

Proof. WLOG $S\neq\{\pm 1\}$. Then for $z=x-y\alpha\in S\backslash\{\pm 1\}$ we have

$\displaystyle \left |z-\frac 1z\right |=|y(\alpha-\bar\alpha)|\ge |\alpha-\bar\alpha|=\sqrt{m^2-4n}=:\varepsilon> 1$.

Suppose that $1 is a solution. Then

$\displaystyle \left |z-\frac 1z\right |=z-\frac 1z<\varepsilon-\frac 1\varepsilon<\varepsilon$,

impossible. Thus $S\cap (1,\varepsilon)=\emptyset$, i.e. $S$ is not dense. $\square$

It follows that $S$ is either $\{\pm 1\}$ or $\langle\delta\rangle\cup -\langle\delta\rangle$ for some $\delta>1$ (cf. ordering in groups, corollary 4). Therefore all solutions $(x,y)$ to $(*)$ are either just $(\pm 1,0)$, or are given by

$\boxed{x-y\alpha=\pm (x_0-y_0\alpha)^k,\; k\in\mathbb Z}$

where $x_0-y_0\alpha$ is the least solution $>1$.

Corollary. (Dirichlet’s unit theorem for a real quadratic field) If $K$ is a real quadratic field, then $\mathcal O_K^*=\{\pm\varepsilon^n: n\in\mathbb Z\}$ for some $\varepsilon\ge 1$.