# Tag Archives: ideal

## 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

## Minimum number of prime ideals

Let $K$ be an algebraically closed field and $R=K[x,y]$. Let $J=(P(x),Q(y))$ $\subseteq R$ be an ideal. Since $R$ is noetherian, a theorem of Noether says that there are finitely many prime ideals $p_1,\dots,p_n\supseteq J$ such that $p_1\cdots p_n\subseteq J$.

Suppose that $P(x)=(x-a)^A(x-b)^B$ and $Q(y)=(y-c)^C$ are uniquely factored into irreducibles. Then each $p_i$ is equal to $(x-a,y-c)$ or $(x-b,y-c)$. Suppose that $r$ of them are $(x-a,y-c)$ and $s$ of them are $(x-b,y-c)$. Then

$\displaystyle p_1\cdots p_n=\left((x-a)^i(x-b)^j(y-c)^k:\begin{cases}0\le i\le r\\ 0\le j\le s\\ 0\le k\le r+s\\ i+j+k=r+s\end{cases}\right)$

To have $p_1\cdots p_n\subseteq J$, therefore, we need

$\{k\ge C\}\cup(\{i\ge A\}\cap\{j\ge B\})$.

So we need $k\ge C$ or $\min\{i,j\}\ge\max\{A,B\}$, i.e.

$k+\min\{i,j\}\ge C+\max\{A,B\}-1$

\begin{aligned}\Leftrightarrow n=r+s&=k+\min\{i,j\}+\max\{i,j\}\\ &\ge C+\max\{A,B\}-1+\max\{i,j\}.\end{aligned}

As $i,j,k$ vary, we may replace $\max\{i,j\}$ with $\max\{r,s\}$. We therefore deduce:

Bound 1. $\min\{r,s\}\ge C+\max\{A,B\}-1$.

Bound 2. $n\ge 2(C+\max\{A,B\}-1)$.

Remark. Bound 1 is obviously stronger; however, since in general we don’t have information on $r$ and $s$, bound 2 is uniformly the best possible.

The calculation becomes much more subtle for general polynomials.

Filed under Algebra

## Some divisibility properties of Fibonacci-like sequences

Here we shall aim to generalise the corollary from the last post, and on the way generalise some other important properties of the Fibonacci sequence, to general Fibonacci-like sequences.

Consider a sequence $\{a_n\}$ with $a_0=0, a_1=1$ and $a_n=ua_{n-1}+va_{n-2}$ for $n\ge 2$, where $u,v\in\mathbb Z$ such that $u^2+4v\neq 0$. Let $\alpha,\beta$ be the roots of $x^2-ux-v=0$. Then

$\displaystyle a_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$.

Let $p$ be an odd prime. Suppose $(\alpha)$ and $(p)$ have a common factor. By Dedekind’s factorisation criterion, $(p)$ is either prime or it factors into two (not necessarily distinct) prime ideals each with norm $p$. In the first case, we must have $(p)\mid (\alpha)$ i.e. $p^2\mid v$, taking ideal norms. In the second case, if one of the prime factors of $(p)$ divides $(\alpha)$, then (again taking norms) $p$ must divide $v$.

So we take $(p,v)=1$ which ensures that $(\alpha)$ and $(p)$ are coprime. Thus we deduce from the general exponent lifting result,

Lemma 1. If $p$ is a prime factor of $a_k$ such that $p\nmid v$, then $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Next, recalling the proof of the corollary from last time, we seem to require the condition $(a_m,a_n)=a_{(m,n)}$.

Lemma 2. If $(u,v)=1$, then $(a_m,a_n)=a_{(m,n)}$ for all $m,n$.

Proof. First, it is clear that $(a_m,a_n)/a_{(m,n)}\in\mathcal O_K$, where $K=\mathbb Q(\alpha)$, and that $(a_m,a_n)/a_{(m,n)}\in\mathbb Q$. Thus $(a_m,a_n)/a_{(m,n)}\in\mathbb Z$.

Let $p$ be a prime factor of $(a_m,a_n)$. Then for $m\ge n$,

$\displaystyle p\mid\frac{\alpha^m-\beta^m}{\alpha-\beta}-\frac{\alpha^{m-n}(\alpha^n-\beta^n)}{\alpha-\beta}=\frac{\beta^n(\alpha^{m-n}-\beta^{m-n})}{\alpha-\beta}=\beta^na_{m-n}$.

If $(p)$ and $(\beta^n)$ share a common factor, then (taking ideal norms,) $p\mid v$. Hence $a_n\equiv ua_{n-1}\equiv u^{n-1}\equiv 0\pmod p$, a contradiction as $(u,p)=1$.

Hence $(a_m,a_n)\mid a_{m-n}$ and by the Euclidean algorithm we get $(a_m,a_n)\mid a_{(m,n)}$. Thus $(a_m,a_n)=a_{(m,n)}$, as desired. $\square$

Now we define $k(n)$ to be the least $k$ such that $n\mid a_k$, and we are ready for our generalisation!

Theorem. Let $\{a_n\}$ be given by $a_0=0,a_1=1$ and $a_n=ua_{n-1}+va_{n-2}$ for $n\ge 2$, where $u,v$ are coprime integers such that $u^2+4v\neq 0$. Then for an odd prime $p$ for which $k(p)$ exists,

$p^r\parallel a_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}$

Proof. If $p\mid v$, then $p\mid a_{k(p)}-va_{k(p)-2}=ua_{k(p)-1}$. By definition of $k(p)$, $p\nmid a_{k(p)-1}$. Hence $p\mid u$, which is impossible as $(u,v)=1$. Thus $p\nmid v$ and the proof of the corollary in the previous post now applies. $\square$

Filed under Algebra, Number theory

## A generalisation of ‘lifting the exponent’

Lifting the exponent is a popular result in elementary number theory. It basically says that if $\alpha,\beta\in\mathbb Z$ and $a_n=(\alpha^n-\beta^n)/(\alpha-\beta)$, then for an odd prime $p$ coprime to $\alpha,\beta$ and for $r\ge 1$,

Theorem 1. (Lifting the exponent) $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Here, as usual, $p^r\parallel x$ means that $p^r\mid x$ but $p^{r+1}\nmid x$.

We shall generalise this to general rings of algebraic integers. In the following, $K$ will denote an algebraic number field and $\mathcal O_K$ its ring of integers. Let $\alpha,\beta\in\mathcal O_K$ such that the ideals $(\alpha), (\beta)$ are coprime to $(p)$, and $a_n\in\mathbb Z\ \forall n$.

Theorem 2. $p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0$.

Proof. We proceed by induction on $n$. The base case $n=0$ is clear. Suppose that the assertion holds for $n-1$. We want to show that $p^{n+r}\parallel a_{kp^n}$, that is,

$\displaystyle p^{n+r}\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha-\beta}=a_{kp^{n-1}}\cdot\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}$

By hypothesis, $p^{n+r-1}\parallel a_{kp^{n-1}}$. So we need to show that $\displaystyle p\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}$.

Let $c=\alpha^{kp^{n-1}}, d=\beta^{kp^{n-1}}$. We want to show that $\displaystyle p\parallel\frac{c^p-d^p}{c-d}$.

Since $p\mid a_k$, we have $a_k\in (p)$. Hence $\alpha^k-\beta^k=(\alpha-\beta)a_k\in (p)$, i.e. $\alpha^k\equiv\beta^k\pmod p$. Hence $c\equiv d\pmod p$. Let $c=d+\mu p$ for some $\mu\in\mathcal O_K$. Then

$\displaystyle\frac{c^p-d^p}{c-d}=\frac{(d+\mu p)^p-d^p}{\mu p}=\frac{p\cdot d^{p-1}\mu p+\ldots}{\mu p}\equiv pd^{p-1}\pmod{p^2}.$

If this is $0$, then $(p)\mid (d)^{p-1}$, which is impossible by unique factorisation as $(p)$ and $(d)$ are coprime. $\square$

Corollary. Let $\{F_n\}$ be the Fibonacci sequence. Then

$p^r\parallel F_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}$

(Refer to this post for notation.)

Proof. Take $\alpha=\varphi=\frac{1+\sqrt 5}{2}, \beta=\bar\varphi=\frac{1-\sqrt 5}{2}$ (with $K=\mathbb Q(\sqrt 5)$ and $\mathcal O_K=\mathbb Z[\varphi]$) and let $k=k(p)$. We proceed by induction on $n$. Suppose $p^{n+r}\mid F_j$ for some $j. By hypothesis, $k(p^{n+r-1})=kp^{n-1}$ so $p^{n+r-1}\mid p^{n+r}\mid F_j\Rightarrow kp^{n-1}\mid j. Then $1\le \frac{j}{kp^{n-1}}, so $\gcd(\frac{j}{kp^{n-1}},p)=1$, i.e. $\gcd(j,kp^n)=kp^{n-1}$. Hence $\gcd(F_{kp^n},F_j)=F_{kp^{n-1}}$ which implies $p^{n+r}\mid F_{kp^{n-1}}$, a contradiction. $\square$