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.

Advertisements

Leave a comment

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=LMFirstly, 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)=1This 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<p-1. 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.

2 Comments

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<z<\varepsilon 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.

Leave a comment

Filed under Algebra, Number theory