Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Cohn's criterion"

(Cohn)
 
(Cohn's Criterion and Proof)
Line 1: Line 1:
−
Let <math>p</math> be a prime number, and <math>b\geq 2</math> an integer. If <math>\overline{p_np_{n-1}\cdotsp_1}</math> is the base-<math>b</math> representation of <math>p</math>, and <math>0\leq p_i<b</math>, then
+
Let <math>p</math> be a prime number, and <math>b\geq 2</math> an integer. If <math>\overline{p_np_{n-1}\cdots p_1p_0}</math> is the base-<math>b</math> representation of <math>p</math>, and <math>0\leq p_i<b</math>, then
 
<cmath>f(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+P_1x+p_0</cmath>
 
<cmath>f(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+P_1x+p_0</cmath>
 
is irreducible.
 
is irreducible.
Line 12: Line 12:
 
This means <math>g(z)>0</math> if <math>|z|\geq \frac{1+\sqrt{1+4H}}{2}</math>, so <math>|\phi|<\frac{1+\sqrt{1+4H}}{2}</math>.
 
This means <math>g(z)>0</math> if <math>|z|\geq \frac{1+\sqrt{1+4H}}{2}</math>, so <math>|\phi|<\frac{1+\sqrt{1+4H}}{2}</math>.
  
−
If <math>b\geq 3</math>, this implies <math>|b-\phi|>1</math> if <math>b\geq 3</math> and <math>f(\phi)=0</math>. Let <math>f(x)=g(x)h(x)</math>. Since <math>f(b)=p</math>, one of <math>|g(b)|</math> and <math>h(b)</math> is 1. WLOG, assume <math>g(b)=1</math>. Let <math>\phi_1, phi_2,\cdots,\phi_r</math> be the roots of <math>g(x)</math>. This means that <math>|g(b)|=|b-\phi_1||b-\phi_2|\cdots|b-\phi_r|>1</math>. Therefore, <math>f(x) is irreducible.
+
If <math>b\geq 3</math>, this implies <math>|b-\phi|>1</math> if <math>b\geq 3</math> and <math>f(\phi)=0</math>. Let <math>f(x)=g(x)h(x)</math>. Since <math>f(b)=p</math>, one of <math>|g(b)|</math> and <math>h(b)</math> is 1. WLOG, assume <math>g(b)=1</math>. Let <math>\phi_1, phi_2,\cdots,\phi_r</math> be the roots of <math>g(x)</math>. This means that <math>|g(b)|=|b-\phi_1||b-\phi_2|\cdots|b-\phi_r|>1</math>. Therefore, <math>f(x)</math> is irreducible.
  
−
If </math>b=2<math>, we will need to prove another lemma:
+
If <math>b=2</math>, we will need to prove another lemma:
  
−
All of the zeroes of </math>f(x)<math> satisfy Re </math>z>\frac{3}{2}<math>.
+
All of the zeroes of <math>f(x)</math> satisfy Re <math>z>\frac{3}{2}</math>.
  
−
Proof: If </math>n=1<math>, then the two polynomials are </math>x<math> and </math>x\pm 1<math>, both of which satisfy our constraint. For </math>n=2<math>, we get the polynomials </math>x^2<math>, </math>x^2\pm x<math>, </math>x^2\pm 1<math>, and </math>x^2\pm x\pm 1<math>, all of which satisfy the constraint. If </math>n\geq 3<math>,  
+
Proof: If <math>n=1</math>, then the two polynomials are <math>x</math> and <math>x\pm 1</math>, both of which satisfy our constraint. For <math>n=2</math>, we get the polynomials <math>x^2</math>, <math>x^2\pm x</math>, <math>x^2\pm 1</math>, and <math>x^2\pm x\pm 1</math>, all of which satisfy the constraint. If <math>n\geq 3</math>,  
 
<cmath>|\frac{f(z)}{z^n}|\geq |1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-(\frac{1}{|z|^3}+\cdots+\frac{1}{|z|^n})>|1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-\frac{1}{|z|^2(|z|-1)}</cmath>
 
<cmath>|\frac{f(z)}{z^n}|\geq |1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-(\frac{1}{|z|^3}+\cdots+\frac{1}{|z|^n})>|1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-\frac{1}{|z|^2(|z|-1)}</cmath>
  
−
If Re </math>z\geq 0<math>, we have Re </math>\frac{1}{z^2}\geq 0<math>, and then
+
If Re <math>z\geq 0</math>, we have Re <math>\frac{1}{z^2}\geq 0</math>, and then
 
<cmath>|\frac{f(z)}{z^n}|>1-\frac{1}{|z|^2(|z|-1)}</cmath>
 
<cmath>|\frac{f(z)}{z^n}|>1-\frac{1}{|z|^2(|z|-1)}</cmath>
−
For </math>|z|\geq \frac{3}{2}<math>, then </math>|z|^2(|z|-1)\geq(\frac{3}{2})^2(\frac{1}{2})=\frac{9}{8}>1<math>. Therefore, </math>z<math> is not a root of </math>f(x).
+
For <math>|z|\geq \frac{3}{2}</math>, then <math>|z|^2(|z|-1)\geq(\frac{3}{2})^2(\frac{1}{2})=\frac{9}{8}>1</math>. Therefore, <math>z</math> is not a root of <math>f(x)</math>.
  
 
However, if Re <math>z<0</math>, we have from our first lemma, that <math>|z|<\frac{1+\sqrt{5}}{2}</math>, so Re <math>z<\frac{1+\sqrt{5}}{2\sqrt{2}}<\frac{3}{2}</math>. Thus we have proved the lemma.
 
However, if Re <math>z<0</math>, we have from our first lemma, that <math>|z|<\frac{1+\sqrt{5}}{2}</math>, so Re <math>z<\frac{1+\sqrt{5}}{2\sqrt{2}}<\frac{3}{2}</math>. Thus we have proved the lemma.
  
 
To finish the proof, let <math>f(x)=g(x)h(x)</math>. Since <math>f(2)=p</math>, one of <math>g(2)</math> and <math>h(2)</math> is 1. WLOG, assume <math>g(2)=1</math>. By our lemma, <math>|z-2|>|z-1|</math>. Thus, if <math>\phi_1, \phi_2,\cdots,\phi_r</math> are the roots of <math>g(x)</math>, then <math>|g(2)|=|2-\phi_1||2-\phi_2|\cdots|2-\phi_n|>|1-\phi_1||1-\phi_2|\cdots|1-\phi_n|=|g(1)|\leq 1</math>. This is a contradiction, so <math>f(x)</math> is irreducible.
 
To finish the proof, let <math>f(x)=g(x)h(x)</math>. Since <math>f(2)=p</math>, one of <math>g(2)</math> and <math>h(2)</math> is 1. WLOG, assume <math>g(2)=1</math>. By our lemma, <math>|z-2|>|z-1|</math>. Thus, if <math>\phi_1, \phi_2,\cdots,\phi_r</math> are the roots of <math>g(x)</math>, then <math>|g(2)|=|2-\phi_1||2-\phi_2|\cdots|2-\phi_n|>|1-\phi_1||1-\phi_2|\cdots|1-\phi_n|=|g(1)|\leq 1</math>. This is a contradiction, so <math>f(x)</math> is irreducible.

Revision as of 15:19, 14 August 2018

Let $p$ be a prime number, and $b\geq 2$ an integer. If $\overline{p_np_{n-1}\cdots p_1p_0}$ is the base-$b$ representation of $p$, and $0\leq p_i<b$, then \[f(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+P_1x+p_0\] is irreducible.

Proof

The following proof is due to M. Ram Murty.

We start off with a lemma. Let $g(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\in \mathbb{Z}[x]$. Suppose $a_n\geq 1$, $a-{n-1}\geq 0$, and $|a_i|\leq H$. Then, any complex root of $f(x)$, $\phi$, has a non positive real part or satisfies $|\phi|<\frac{1+\sqrt{1+4H}}{2}$.

Proof: If $|z|>1$ and Re $z>0$, note that: \[|\frac{g(z)}{z^n}|\geq |a_n+\frac{a_{n-1}}{z}|-H(\frac{1}{|z|^2}+\cdots+\frac{1}{|z|^n})>Re(a_n+\frac{a_{n-1}}{z})-\frac{H}{|z|^2-|z|}\geq 1-\frac{H}{|z|^2-|z|}=\frac{|z|^2-|z|-H}{|z|^2-|z|}\] This means $g(z)>0$ if $|z|\geq \frac{1+\sqrt{1+4H}}{2}$, so $|\phi|<\frac{1+\sqrt{1+4H}}{2}$.

If $b\geq 3$, this implies $|b-\phi|>1$ if $b\geq 3$ and $f(\phi)=0$. Let $f(x)=g(x)h(x)$. Since $f(b)=p$, one of $|g(b)|$ and $h(b)$ is 1. WLOG, assume $g(b)=1$. Let $\phi_1, phi_2,\cdots,\phi_r$ be the roots of $g(x)$. This means that $|g(b)|=|b-\phi_1||b-\phi_2|\cdots|b-\phi_r|>1$. Therefore, $f(x)$ is irreducible.

If $b=2$, we will need to prove another lemma:

All of the zeroes of $f(x)$ satisfy Re $z>\frac{3}{2}$.

Proof: If $n=1$, then the two polynomials are $x$ and $x\pm 1$, both of which satisfy our constraint. For $n=2$, we get the polynomials $x^2$, $x^2\pm x$, $x^2\pm 1$, and $x^2\pm x\pm 1$, all of which satisfy the constraint. If $n\geq 3$, \[|\frac{f(z)}{z^n}|\geq |1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-(\frac{1}{|z|^3}+\cdots+\frac{1}{|z|^n})>|1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-\frac{1}{|z|^2(|z|-1)}\]

If Re $z\geq 0$, we have Re $\frac{1}{z^2}\geq 0$, and then \[|\frac{f(z)}{z^n}|>1-\frac{1}{|z|^2(|z|-1)}\] For $|z|\geq \frac{3}{2}$, then $|z|^2(|z|-1)\geq(\frac{3}{2})^2(\frac{1}{2})=\frac{9}{8}>1$. Therefore, $z$ is not a root of $f(x)$.

However, if Re $z<0$, we have from our first lemma, that $|z|<\frac{1+\sqrt{5}}{2}$, so Re $z<\frac{1+\sqrt{5}}{2\sqrt{2}}<\frac{3}{2}$. Thus we have proved the lemma.

To finish the proof, let $f(x)=g(x)h(x)$. Since $f(2)=p$, one of $g(2)$ and $h(2)$ is 1. WLOG, assume $g(2)=1$. By our lemma, $|z-2|>|z-1|$. Thus, if $\phi_1, \phi_2,\cdots,\phi_r$ are the roots of $g(x)$, then $|g(2)|=|2-\phi_1||2-\phi_2|\cdots|2-\phi_n|>|1-\phi_1||1-\phi_2|\cdots|1-\phi_n|=|g(1)|\leq 1$. This is a contradiction, so $f(x)$ is irreducible.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Cohn%27s_criterion&oldid=97230"