Rational solutions to polynomials

by t0rajir0u, Mar 26, 2008, 1:39 AM

My apologies for not updating in quite awhile :oops: Fortunately, I've been doing a fair bit of musing these days and I think I've got material for a bit more activity than before.

The basis for today's discussion is this reasonably innocuous problem:

Problem: $ a, b, c$ are odd integers. Prove that $ ax^2 + bx + c = 0$ has no rational roots.

Method 1: Suppose $ \frac{p}{q}$ is a rational root where $ \gcd(p, q) = 1$. Then $ a \left( \frac{p}{q} \right)^2 + b \left( \frac{p}{q} \right) + c = 0 \Leftrightarrow ap^2 + bpq + cq^2 = 0$. Now, it cannot be the case that both $ p, q$ are even (and in fact RRT tells us that both $ p, q$ are odd), but if either (or both) $ p, q$ are odd then the above expression is odd; contradiction.

Method 2: $ X^2 + XY + Y^2$ has no solutions in $ \mathbb{F}_2 P^1$.

Whoa, there! What exactly have we done in Method 2? As it turns out, this is a very slick rewording of Method 1, but the concepts it introduces are deep. To explain them rigorously, we will introduce a few tools.

Definition: The homogenization of a polynomial $ f(x)$ of degree $ n$ is the polynomial $ f^{*}(X, Y) = Y^n f \left( \frac{X}{Y} \right)$.

The homogenization of a polynomial is, well, a homogeneous polynomial in two variables $ X, Y$. In other words, $ f^{*}(tX, tY) = t^n f^{*}(X, Y)$. When we homogenize our given polynomial, we see that to look for rational solutions to $ ax^2 + bx + c = 0$ is equivalent to looking for integer solutions to $ aX^2 + bXY + cY^2 = 0$, which is exactly what we did in the first solution.

Note, however, that as long as we're looking at the roots of $ f^{*}(X, Y) = 0$, homogenization means that we can identify any root $ (P, Q)$ with $ (tP, tQ)$. This motivates a very powerful idea.

Definition: The projective line $ KP^1$ over a field $ K$ is the set of equivalence classes of points $ (x, y) \in K^2, xy \neq 0$ under the equivalence relation $ (x, y) \sim (tx, ty), t \in K \neq 0$. A projective point is denoted $ (X : Y)$. (We delete the origin because it is only equivalent to itself and has no particularly useful properties.)

We were initially looking at solutions to $ f(x)$ in $ \mathbb{Q}$, and now we're looking at solutions to $ f^{*}(X, Y)$ in $ \mathbb{Q}P^1$. Note that instead of treating $ X, Y$ as two variables we are looking at the single variable $ (X : Y) \in \mathbb{Q}P^1$. (The notational change is to emphasize that what we are looking at is the ratio between the coordinates, not the coordinates themselves.)

This might be your first foray into projective geometry. Let's try to figure out more about the structure of $ P^1$. When $ Y \neq 0$, we can identify a point $ (X : Y)$ with the point $ \left( \frac{X}{Y} : 1 \right)$; this is called an affine slice of the projective line, and since $ \frac{X}{Y}$ can take on any value in $ K$ (here $ \mathbb{Q}$) it is essentially (that is, isomorphic to) $ K$ (the affine line). When $ Y = 0$, however, we have the single point $ (1 : 0)$. This is called the point at infinity and is the reason the projective line has more structure than the affine line.

One way to understand the projective line, therefore, is as the affine line with a point of infinity "glued" onto it. In fact, this viewpoint generalizes when we consider higher-dimensional projective spaces (the projective plane, for example). But enough about that. For now, the important thing is that the projective (rational) line is our new domain for understanding the rational solutions of polynomials.

This was a long way to go to restate the first basic idea of Method 1: a solution to $ ax^2 + bx + c = 0$ on the rational affine line corresponds to a solution to $ aX^2 + bXY + cY^2 = 0$ on the rational projective line.

Now we can go a step further and reduce everything $ \bmod 2$.

Since $ a, b, c \equiv 1 \bmod 2$, we are now looking at solutions to the polynomial $ X^2 + XY + Y^2 = 0$ for $ X, Y \in \mathbb{F}_2$ (the finite field with $ 2$ elements; canonically isomorphic to the integers $ \bmod 2$). But wait! Doesn't everything we've said about homogeneous polynomials still apply?

What we're actually looking at now is the projective line $ \mathbb{F}_2 P^1$ over a finite field. This line has three points: $ (1 : 1), (0 : 1), (1 : 0)$. The first two are an affine slice corresponding to $ \mathbb{F}_2$ while the last is a point at infinity.

Let's restate the second basic idea from Method 1 now: a solution to $ ax^2 + bx + c = 0$ on the rational affine line corresponds to a solution to $ X^2 + XY + Y^2 = 0$ on the projective line over $ \mathbb{F}_2$. (In fact, this correspondence is a ring homomorphism known as the reduction-modulo-$ 2$ map). We can describe this correspondence explicitly:

$ \frac{p}{q}$ corresponds to $ (1 : 1)$ if $ p, q$ are both odd.
$ \frac{p}{q}$ corresponds to $ (0 : 1)$ if $ p$ is even and $ q$ is odd.
$ \frac{p}{q}$ corresponds to $ (1 : 0)$ if $ q$ is even and $ p$ is odd.

Note that the deletion of the origin we specified in defining the projective line has a natural interpretation here: $ (0 : 0)$ corresponds to a rational number not in lowest terms, so of course it has no meaning since we can reduce it until it is in lowest terms!

It is now extremely simple to check that none of the above three points is a solution to $ X^2 + XY + Y^2 = 0$.

Remark: The existence of a solution to $ X^2 + XY + Y^2 = 0$ in $ \mathbb{F}_2 P^1$ is a necessary, but not a sufficient, condition for the existence of a solution to $ ax^2 + bx + c = 0$. See http://en.wikipedia.org/wiki/Hasse_principle .

The above has been something of an introduction to the rich field of algebraic geometry. So far, we have considered the rational roots of polynomials in one variable. From here, we can consider the set of rational points on curves defined by polynomials in two variables (after homogenization, a Diophantine equation), which will be the subject of the next post and is an important aspect of the study of elliptic curves. (I need somewhere to talk about my RSI/Intel research, don't I? :) )

Practice Problem 1: Find all rational solutions to $ x^3 + y^3 = x^2 + y^2$. (Think homogenizing and dehomogenizing.)

Comment

6 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
If $ x=y$ then we have $ x^3=x^2$. If $ x=0$, then $ y=0,1$. So we have 4 trivial solutions: $ (x,y)=(0,0),(1,0),(0,1),(1,1)$.

Let $ x=a/c$ and $ y=b/c$ such that $ (a,b)=1$ where $ ab\ne 0$. (wlog $ a > b$)

The problem is then

$ a^3+b^3=c(a^2+b^2)$

$ a^2(a-c)=b^2(c-b)$

Notice that $ a>b$ means that $ a-c>b-c$...one of $ a-c$ or $ b-c$ must be negative, so that means that $ b-c$ is negative, and $ a-c$ is positive. So $ a>c>b$.

Since $ (a,b)=1$, we must have $ a^2=c-b$ and $ b^2=a-c$

Then add these to get $ a^2+b^2=a-b$. Then $ (2a-1)^2=1 - 4 b - 4 b^2>0$. It follows that $ b\in \left [\frac{1}{2}\cdot (-1 - \sqrt{2}) ,\frac{1}{2}\cdot (-1 + \sqrt{2})\right]$

Hence $ b=-1,0$. It is easy to check that there are no solutions here.

by Altheman, Mar 27, 2008, 12:01 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
There are actually an infinite number of solutions. When you put everything over a common denominator you can't assume that $ \gcd(a, b) = 1$. :)

by t0rajir0u, Mar 27, 2008, 5:13 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ha. It just hit me that that assumption was wrong in solving another problem on AoPS (it was solve $ a^2+b^2+c^2=7$ in rational numbers).

We can write $ x=\frac{ad}{c}$ and $ y=\frac{bd}{c}$

where $ (c,d)=1$, and $ (a,b)=1$ $ d,c>0$, $ a>b$

(write as any integers $ a$, $ b$, $ c$, $ d$, then if $ a$,$ b$ have common factors, put them into $ d$, if $ d$,$ c$ have any common factors, just cancel them, the sign can be absorbed into $ a$,$ b$; then by symmetry $ a>b$ ($ x=y$ we already handled that, only trivial solutions))

Then we have $ a^2(ad-c)=b^2(c-bd)$

$ a^2=c-bd$ $ b^2=ad-c$. Now easily, we have

$ c=\frac{a^3+b^3}{a-b}$ and $ d=\frac{a^2+b^2}{a-b}$.

We have that $ (c,d)=1$, so $ (c,d)=(c-ad,d)=(c-bd,d)$

$ (a^2,\frac{a^2+b^2}{a-b})=(b^2,\frac{a^2+b^2}{a-b})=1$. But if $ p|(c,d)$, then $ p|a^2$ and $ p|b^2$, which is a contradiction. Hence those are coprime.

We just need to have that $ c,d$ are integers. Note that $ c=ad-b^2$, so it suffices to show that $ d$ is an integer. $ d$ is an integer is equivalent to $ \frac{2b^2}{a-b}$ is an integer. Note that $ (a,b)=(a-b,b)=1$, so $ a-b|2$, so $ a-b=1,2$.

If $ a=b+1$, then $ (x,y)=(\frac{(b+1)(b^2+(b+1)^2)}{b^3+(b+1)^3}, \frac{(b)(b^2+(b+1)^2)}{b^3+(b+1)^3})$ where $ b$ is any integer.

If $ a=b+2$, then $ (a,b=(b,a-b)=(b,2)=1$, so $ b$ is odd, and we have

$ (x,y)=(\frac{(b+1)(b^2+(b+2)^2)}{b^3+(b+2)^3}, \frac{(b)(b^2+(b+2)^2)}{b^3+(b+2)^3})$ where $ b$ is any ODD integer.



We can verify that these values work (interesting identity?). So I think we are done.

Nice.

(what is your solution? I don't know any algebraic geometry or whatever so i have to resort to this stuff...)

by Altheman, Mar 28, 2008, 6:46 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
I'm not actually sure you caught every solution. Here's my solution, and I'll explain the motivation in the next post:

Divide out by $ x^3$ and let $ a = \frac{1}{x}, b = \frac{y}{x}$. This gives

$ 1 + b^3 = a(1 + b^2) \implies$
$ a = \frac{1 + b^3}{1 + b^2}$.

$ b$ can be an arbitrary rational number (notice that I have said nothing about integers) that uniquely determines $ a$. This gives

$ x = \frac{1}{a} = \frac{1 + b^2}{1 + b^3}$
$ y = \frac{b}{a} = \frac{b(1 + b^2)}{1 + b^3}$.

This method of presentation also has an interpretation in terms of algebraic geometry, even if the algebra is simple. :)

by t0rajir0u, Mar 29, 2008, 12:14 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hmm I recall this problem from somewhere (don't remember). I was interested in how you would solve it. Now I know :)

by n0vad3m0n, Mar 29, 2008, 11:28 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thanks for the solution!

by manjil, Aug 16, 2008, 9:39 AM

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