More polynomials

by t0rajir0u, Feb 19, 2007, 7:32 PM

Another very useful concept that could be applied in several problems I've seen.

Definition: Given some $a$ and some field (such as the rationals) $F$, then the minimal polynomial $m(x)$ of $a$ over $F[x]$ (the ring of polynomials with coefficients in $F$) is the unique monic polynomial in $F[x]$ of smallest degree such that $m(a) = 0$.

It may not be immediately obvious that the minimal polynomial is unique, but if two minimal polynomials $m(x), n(x)$ of the same degree exist then $k(x) = m(x)-n(x)$ also has $k(a) = 0$ but is of smaller degree, hence it must be $0$.

From the definition, it should also be obvious that a minimal polynomial in $F[x]$ is irreducible over $F[x]$. The minimal polynomial of a primitive $k^{th}$ root of unity is $\Phi_{k}(x)$ (see cyclotomic polynomial).

The uniqueness of the minimal polynomial is already enough to solve a MOP homework problem I saw recently.

Problem: Prove that for every irrational real $a$ there exist irrational numbers $b, b'$ such that $a+b, ab'$ are rational but $a+b', ab$ are irrational.

Solution: Consider the minimal polynomial $m(x)$ of $a$ over $\mathbb{Q}[x]$. It is not linear, since $a$ is not rational.

Case: $\text{deg }m = 2$. Let $m(x) = x^{2}+px+q = (x-a)(x-c)$ where $c$ is some irrational and $p, q$ are rational. Let $b$ be an irrational such that $-a-b$ is rational but not equal to $p$; then $ab$ cannot be rational (or else $(x-a)(x-b)$ would be another minimal polynomial). Similarly, let $b'$ be an irrational such that $ab'$ is rational but not equal to $q$; then $-a-b'$ cannot be rational.

Case: $\text{deg }m > 2$ (edit: Or $a$ is transcendental and $m$ does not exist!). This case is even easier. $b$ can be any irrational such that $-a-b$ is rational and $b'$ can be any irrational such that $ab'$ is rational, and the above construction works (or else $a$ has a minimal polynomial of degree $2$).

But we can do more!

Lemma: If $p(a) = 0$ then $m(x) | p(x)$.

Proof: Let $p(x) = m(x) q(x)+r(x)$ (division algorithm). Then $r(a) = 0$ but $r(x)$ is of degree less than $m(x)$, so $r(x) = 0$ everywhere.

This idea provides a quick proof of the Conjugate Root Theorem.

Theorem: If $p+\sqrt{q}$ is the root of a polynomial $p(x) \in \mathbb{Q}[x]$ where $p, q$ are rational and $q$ is not the square of a rational, then $p-\sqrt{q}$ is also a root of $p(x)$.

Proof: The minimal polynomial of $p+\sqrt{q}$ is the quadratic $m(x) = x^{2}-2px+(p^{2}-q)$. By the lemma, $m(x) | p(x)$, and since $p-\sqrt{q}$ is a root of $m(x)$ it must also be a root of $p(x)$.

The case $q$ negative provides the complex conjugate root theorem, which holds over the reals by a similar argument.

Practice Problem 1: Calculate the minimal polynomial of $1+\sqrt{2}+\sqrt{3}$ over the rationals. How about $1+\sqrt{2}+\sqrt{3}+\sqrt{5}$? How about

$1+\sum_{p \in \mathbb{P}, p < n }\sqrt{p}$

?

Practice Problem 2: Prove that $x^{n}-1 = \prod_{d | n}\Phi_{d}(x)$.

Edit: Practice Problem 3: Prove or disprove that the minimal polynomial of some irrational $a$ over the rationals cannot have repeated roots.

Comment

1 Comment

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
t0rajir0u wrote:
Another very useful concept that could be applied in several problems I've seen.

Definition: Given some $a$ and some field (such as the rationals) $F$, then the minimal polynomial $m(x)$ of $a$ over $F[x]$ (the ring of polynomials with coefficients in $F$) is the unique monic polynomial in $F[x]$ of smallest degree such that $m(a) = 0$.

It may not be immediately obvious that the minimal polynomial is unique, but if two minimal polynomials $m(x), n(x)$ of the same degree exist then $k(x) = m(x)-n(x)$ also has $k(a) = 0$ but is of smaller degree, hence it must be $0$.

From the definition, it should also be obvious that a minimal polynomial in $F[x]$ is irreducible over $F[x]$. The minimal polynomial of a primitive $k^{th}$ root of unity is $\Phi_{k}(x)$ (see cyclotomic polynomial).

The uniqueness of the minimal polynomial is already enough to solve a MOP homework problem I saw recently.

Problem: Prove that for every irrational real $a$ there exist irrational numbers $b, b'$ such that $a+b, ab'$ are rational but $a+b', ab$ are irrational.

Solution: Consider the minimal polynomial $m(x)$ of $a$ over $\mathbb{Q}[x]$. It is not linear, since $a$ is not rational.

Case: $\text{deg }m = 2$. Let $m(x) = x^{2}+px+q = (x-a)(x-c)$ where $c$ is some irrational and $p, q$ are rational. Let $b$ be an irrational such that $-a-b$ is rational but not equal to $p$; then $ab$ cannot be rational (or else $(x-a)(x-b)$ would be another minimal polynomial). Similarly, let $b'$ be an irrational such that $ab'$ is rational but not equal to $q$; then $-a-b'$ cannot be rational.

Case: $\text{deg }m > 2$ (edit: Or $a$ is transcendental and $m$ does not exist!). This case is even easier. $b$ can be any irrational such that $-a-b$ is rational and $b'$ can be any irrational such that $ab'$ is rational, and the above construction works (or else $a$ has a minimal polynomial of degree $2$).

But we can do more!

Lemma: If $p(a) = 0$ then $m(x) | p(x)$.

Proof: Let $p(x) = m(x) q(x)+r(x)$ (division algorithm). Then $r(a) = 0$ but $r(x)$ is of degree less than $m(x)$, so $r(x) = 0$ everywhere.

This idea provides a quick proof of the Conjugate Root Theorem.

Theorem: If $p+\sqrt{q}$ is the root of a polynomial $p(x) \in \mathbb{Q}[x]$ where $p, q$ are rational and $q$ is not the square of a rational, then $p-\sqrt{q}$ is also a root of $p(x)$.

Proof: The minimal polynomial of $p+\sqrt{q}$ is the quadratic $m(x) = x^{2}-2px+(p^{2}-q)$. By the lemma, $m(x) | p(x)$, and since $p-\sqrt{q}$ is a root of $m(x)$ it must also be a root of $p(x)$.

The case $q$ negative provides the complex conjugate root theorem, which holds over the reals by a similar argument.

Practice Problem 1: Calculate the minimal polynomial of $1+\sqrt{2}+\sqrt{3}$ over the rationals. How about $1+\sqrt{2}+\sqrt{3}+\sqrt{5}$? How about

$1+\sum_{p \in \mathbb{P}, p < n }\sqrt{p}$

?

Practice Problem 2: Prove that $x^{n}-1 = \prod_{d | n}\Phi_{d}(x)$.

Edit: Practice Problem 3: Prove or disprove that the minimal polynomial of some irrational $a$ over the rationals cannot have repeated roots.

by serdeang, Mar 4, 2007, 3:37 PM

Various mathematical thoughts, ranging from problem-solving techniques to attempts to tie together related concepts.

avatar

t0rajir0u
Archives
- April 2009
New location!
A question about automata
+ March 2009
Some updates
+ February 2009
Fibonacci numbers @ HMMT
The combinatorics of basic calculus
A question and some thoughts II
+ January 2009
A question and some thoughts
Coefficients in the closed forms of linear recurrences
+ December 2008
The pretty picture post (crystals and cyclotomics)
Fun with Newton polynomials, Part III
+ November 2008
The Chinese Remainder Theorem and Lagrange Interpolation
+ October 2008
The magic of the Frobenius map
+ September 2008
Creative problem solving
A formal look at formal differentiation
+ August 2008
Transition
The title of this blog and enumerative combinatorics
Three approaches to sums of squares
+ July 2008
China Post 3: The Euclidean algorithm
China Post 2: The complex numbers
China Post 1: The problem of repeated roots
+ June 2008
Structure-preserving maps, Part II: Vector spaces
Fun with Newton Polynomials, Part II
Structure-preserving maps, Part I: Groups
+ May 2008
An "elementary" perspective on Dirichlet's theorem
Quadratic residues and cyclotomic polynomials
+ March 2008
Rational Solutions to Polynomials, Part II
Rational solutions to polynomials
+ January 2008
A generating functions approach to counting
+ December 2007
Fun with Newton polynomials
+ November 2007
A matrix derivation of Binet's formula
+ October 2007
A Digression
+ June 2007
A point to ponder
A topic from April
Post-ARML
Post-ARML
+ May 2007
A Quickie
+ April 2007
Algebra through geometry
From a college friend
From Gauss to Eisenstein
+ March 2007
It's been a long time...
+ February 2007
It's a New Day
More polynomials
Something Simple for a Change
+ January 2007
Back to Basics
Rings! Yay!
Intermezzo
+ December 2006
Oops, I sort of forgot this was here.
Complex identities
Shouts
Submit

  • orz $~~~~$

    by clarkculus, Jan 10, 2025, 4:13 PM

  • Insanely auraful

    by centslordm, Jan 1, 2025, 11:17 PM

  • Fly High :(

    by Siddharthmaybe, Oct 22, 2024, 8:34 PM

  • Dang it he is gone :(( /revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive.

    by 799786, Aug 4, 2022, 1:56 PM

  • annoying precision

    by centslordm, May 16, 2021, 7:34 PM

  • rip t0rajir0u

    by OlympusHero, Dec 5, 2020, 9:29 PM

  • Shoutbox bump xD

    by DuoDuoling0, Oct 4, 2020, 2:25 AM

  • dang hes gone :(

    by OlympusHero, Jul 28, 2020, 3:52 AM

  • First shout in July

    by smartguy888, Jul 20, 2020, 3:08 PM

  • https://artofproblemsolving.com/community/c2448

    has more.

    -πφ

    by piphi, Jun 12, 2020, 8:20 PM

  • wait hold up 310,000
    people visited this man?!?!??

    by srisainandan6, May 29, 2020, 5:16 PM

  • first shout in 2020

    by OlympusHero, Apr 4, 2020, 1:15 AM

  • in his latest post he says he moved to wordpress

    by MelonGirl, Nov 16, 2019, 2:43 AM

  • Please revive!

    by AopsUser101, Oct 30, 2019, 7:10 PM

  • first shout in october fj9odiais

    by bulbasaur., Oct 14, 2019, 1:14 AM

128 shouts
Tags
About Owner
  • Posts: 12167
  • Joined: Nov 20, 2005
Blog Stats
  • Blog created: Dec 5, 2006
  • Total entries: 48
  • Total visits: 321828
  • Total comments: 202
Search Blog
a