The Theorem Thread

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

The Theorem Thread

Postby quintopia » Wed Feb 18, 2009 8:24 pm UTC

ITT we post theorems that are both interesting and have short, easy proofs. I'll start with one most people already know, but I'd like to come back here and actually learn something new and interesting. Yes, you have to prove the proof is easy by posting the proof as well.

FACT: For a graph on n vertices and e edges and no 3-connected subgraphs, the following formula holds: #connected components-#cycles=n-e

PROOF: By induction on number of edges.
Base Case: If there are no edges, then there are n connected components and no cycles. n-0=n-e is true, since e=0.
Assume the theorem holds when there are e edges, we want to show it holds for e+1 edges. You can create any graph with e+1 edges by adding an edge to some graph with e edges. Let's pick some such graph on e edges and say it has k connected components and c cycles.

Case 1: The edge (u,v) you add connects two different connected components. Then you have not added a cycle, or else there already was a path from u to v, and hence you have not connected two different connected components. Thus, in the e edge graph we had k-c=n-e, and in the k+1 edge graph, you have subtracted 1 from both sides, so the equality must still hold.

Case 1: The edge (u,v) you add connects two vertices in the same connected component. Then you have increased the number of cycles because u and v already had a path between them. Moreover, you've increased the number of cycles by at most one because we assumed there are no 3-connected subgraphs in the new graph, so there was exactly one path between u and v before. But once again, we've gone from k-c=n-e to k-(c+1)=k-c-1=n-e-1=n-(e+1), so equality still holds.

Q.E.D.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: The Theorem Thread

Postby antonfire » Wed Feb 18, 2009 9:11 pm UTC

The average number of ways to represent an positive integer as a sum of two squares is [imath]\pi[/imath].

More precisely, if s(n) is the number of pairs of integers (a,b) such that a2+b2=n, then
[math]\lim_{N\rightarrow \infty} \frac 1 N \sum_{k=0}^{N-1} s(n) = \pi[/math]


Proof: [imath]\sum_{k=0}^{N-1} s(n)[/imath] is the number of lattice points (a,b) such that a2+b2 < N, which are the lattice points in a circle of radius [imath]R = \sqrt N[/imath] centered at the origin. This is within [imath]o(R)[/imath] of the area of the circle (see below), so [imath]\sum_{k=0}^{N-1} s(n) = \pi R^2 + o(R)= \pi N + o(N^{1/2})[/imath], so
[math]\frac{1}{N}\sum_{k=0}^{N-1} s(n) = \pi + o(N^{-1/2})[/math]


The only annoying bit is showing that the number of lattice points in a circle is pretty close to its area, which I personally am willing to take for granted, but I'll include the argument here for completeness.

Say there are k lattice points in a circle of radius R. If a point is inside a circle of radius R, then the unit square centered on it is contained in a circle of radius [imath]R + \sqrt 2[/imath]. So, [imath]k\leq \pi (R+\sqrt 2)^2 = \pi R^2 +2\sqrt 2 R + 2[/imath]. If the unit square centered at a point intersects a circle of radius [imath]R-\sqrt 2[/imath], then that point is inside the circle of radius R, so [imath]k \geq \pi(R-\sqrt 2)^2 = \pi R^2 - 2\sqrt2 R +2[/imath]. So for sufficiently large R, [imath]k = \pi R^2 + o(R)[/imath].
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: The Theorem Thread

Postby Token » Wed Feb 18, 2009 9:20 pm UTC

in b4 truly marvellous proofs which this margin is too small to contain

EDIT: OK, I'll give you a theorem. It's a pretty damn well known one, but I very much like the simplicity of the proof.

The Fundamental Theorem of Algebra
[imath]\forall[/imath] non-constant [imath]f \in \mathbb{C}[x][/imath], [imath]\exists z_0 \in \mathbb{C}[/imath] such that [imath]f(z_0)=0[/imath].

Proof.
Let [imath]f(z)=a_nz^n+b_{n-1}z^{n-1}+\ldots+a_1z+a_0[/imath]. Then [imath]|f(z)| \geq |z|^n|a^n+\frac{a^n}{z}+\ldots+\frac{a_0}{z^n}| \to \infty[/imath] as [imath]|z| \to \infty[/imath].
So [imath]\exists \rho \in \mathbb{R}^+[/imath] such that [imath]|z|> \rho \Rightarrow |f(z)|>|f(0)|[/imath].
Now [imath]\overline{B_\rho(0)}[/imath], the closed ball of radius [imath]\rho[/imath] about 0, is a compact set, so [imath]|f|[/imath] attains a minimum on it, say at [imath]z_0[/imath], [imath]f(z_0)=b_0[/imath].
By definition of [imath]\rho[/imath], this is a minimum for the whole of [imath]\mathbb{C}[/imath].
Define [imath]g(z)=f(z+z_0)=a_nz^n+b_{n-1}z^{n-1}+\ldots+b_1z+b_0[/imath], so [imath]g[/imath] attains its minimum [imath]b_0[/imath] at [imath]z=0[/imath].
Assume for contradiction that [imath]|b_0|>0[/imath]. So [imath]\exists \alpha \in \mathbb{R}[/imath] such that [imath]e^{i\alpha}b_0 = |b_0|>0[/imath].
So [imath]e^{i\alpha}g(z)=c_nz^n+c_{n-1}z^{n-1}+\ldots+c_kz+|b_0|[/imath], where [imath]c_n=e^{i\alpha}b_n[/imath], and [imath]k\geq 1[/imath] is minimal such that [imath]b_k \neq 0[/imath].
Then [imath]e^{i\alpha}g(re^{i\beta})=|b_0|+c_kr^ke^{ik\beta}+r^{k+1}(\ldots)[/imath]. Choose [imath]\beta[/imath] such that [imath]c_ke^{ik\beta} = -|c_k|<0[/imath].
Then [imath]e^{i\alpha}g(re^{i\beta})=|b_0|-|c_k|r^k+r^{k+1}(\ldots)[/imath].
So for [imath]r[/imath] small enough, [imath]|g(re^{i\beta}|<|b_0|[/imath], contradicting minimality of [imath]|b_0|[/imath].
Hence our assumption was incorrect, and so [imath]b_0=0=f(z_0)[/imath]. QED.
Last edited by Token on Thu Feb 19, 2009 12:09 am UTC, edited 1 time in total.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
Something Awesome
Posts: 47
Joined: Sun May 18, 2008 10:53 pm UTC
Location: NY

Re: The Theorem Thread

Postby Something Awesome » Wed Feb 18, 2009 10:56 pm UTC

Here's a cute one I've seen around:

Theorem: For all [imath]n \in \mathbb{N}, n > 2[/imath], the [imath]n^{th}[/imath] root of 2 is irrational.

Proof. Suppose not; let [imath]2^{1/n} = p/q[/imath] for some integers [imath]p,q[/imath] with [imath]q \neq 0[/imath]. Then we have
[math]\begin{align}2 = \frac{p^n}{q^n}\\
2q^n = p^n\\
q^n + q^n = p^n,\\
\end{align}[/math]

contradicting Fermat's Last Theorem. [imath]Q.E.D.[/imath]

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: The Theorem Thread

Postby stephentyrone » Wed Feb 18, 2009 11:43 pm UTC

I am the only one who thinks that involving the entirety of the real numbers to state (or prove) the fundamental theorem of algebra is massive overkill? The constructive formulation is so much more beautiful.

What do you mean? The fundamental theorem of algebra is fundamentally a theorem of analysis; we should expect that its truth depends delicately on the properties of the complex numbers since it is clearly not true over most other fields.


The point is that you don't need to require the entirety of the complex numbers to formulate the theorem. It's more minimally (and to my mind, naturally), stated in terms of roots that exists in some computable extension of the field from which the coefficients are taken. Why should one need to bring in transcendental numbers just to be able to talk about the roots of polynomials over the integers, for example?

There's a reasonably nice discussion of this in the first chapter of:

http://books.google.com/books?id=L19ZVu ... lt#PPA6,M1

The actual statement of the theorem is on page 8.
Last edited by stephentyrone on Thu Feb 19, 2009 12:37 am UTC, edited 3 times in total.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: The Theorem Thread

Postby t0rajir0u » Thu Feb 19, 2009 12:01 am UTC

What do you mean? The fundamental theorem of algebra is fundamentally a theorem of analysis; we should expect that its truth depends delicately on the properties of the complex numbers since it is clearly not true over most other fields.

Theorem (Erdos): The Ramsey number [imath]R(n, n)[/imath] satisfies [imath]R(n, n) \ge 2^{ n/2 }.[/imath]

Proof: For some large unspecified [imath]v[/imath], color [imath]K_v[/imath] randomly as follows: each edge is red or blue with equal probability. The probability that any collection of [imath]n[/imath] vertices is monochromatic is [imath]2^{1- {n \choose 2} }[/imath], hence the expected number of monochromatic subgraphs is (by linearity of expectation)
[math]2^{1 - {n \choose 2}} {v \choose n}.[/math]
If this number is less than [imath]1[/imath], then it is possible for no monochromatic subgraph of size [imath]n[/imath] to exist, and it is not too hard to show that this occurs when [imath]v = 2^{n/2}.[/imath]

Now, I like this proof for several reasons: it is quite short, it was the first instance of the probabilistic method in combinatorics, and despite the simplicity of the argument this bound has not been significantly improved.

The Pathological Case
Posts: 18
Joined: Thu Jan 15, 2009 4:33 am UTC

Re: The Theorem Thread

Postby The Pathological Case » Thu Feb 19, 2009 6:56 pm UTC

Theorem
There does not exist a function [imath]f: R \rightarrow R[/imath] such that [imath]f(f(x)) = x^2 - 1[/imath] for all [imath]x \in R[/imath]

Try for yourself first!

Hint 1(probably not too helpful):

Spoiler:
I'm cheating, because the generalization of the result makes the proof very clear.


Hint 2:
Spoiler:
If [imath]x^2 - 1[/imath] was replaced by [imath](x^2 - 1)^2 - 1[/imath], existence would be assured. What's the crucial difference between these polynomials? Try graphing along with the line [imath]y = x[/imath].


Proof:
Spoiler:
Let [imath]g(x) = x^2 - 1[/imath] and note the following:

1) [imath]g[/imath] has two fixed points at [imath]\phi_1 = (1 + \sqrt{5})/2[/imath] and [imath]\phi_2 = (1 - \sqrt{5})/2[/imath].
2) [imath]g(g(x)) = x[/imath] has 4 solutions, two of which are [imath]\phi_1, \phi_2[/imath] and the other two, {0, -1}, forming the unique period-2 cycle of g. (That is, [imath]g(0) = -1[/imath] and [imath]g(-1) = 0[/imath]).

Proof by contradiction: suppose there exists a function [imath]f[/imath] such that [imath]f(f(x)) = g(x)[/imath].

If [imath]f(0) = 0[/imath], we have [imath]-1 = g(0) = f(f(0)) = f(0) = 0[/imath], a contradiction. Thus [imath]f(0) \neq 0[/imath].

If [imath]f(0) = -1[/imath] we have [imath]g(-1) = g(g(0)) = g(f(f(0))) = g(f(-1)) = f(g(-1)) = f(0) = -1[/imath], a contradiction. Thus [imath]f(0) \neq -1[/imath].

By analogous arguments, [imath]f(-1) \neq -1[/imath] and [imath]f(-1) \neq 0[/imath]. Further, it is clear [imath]f(0) \neq f(-1)[/imath], or else [imath]g(0) = g(-1)[/imath].

Let [imath]a = f(0)[/imath] and [imath]b = f(-1)[/imath]. We have shown thus far that [imath]a, b[/imath] are distinct and not in {0, -1}

Now, g(a) = g(f(0)) = f(g(0)) = f(-1) = b and g(b) = g(f(-1)) = f(g(-1)) = f(0) = a. So {[imath]a[/imath], [imath]b[/imath]} form a period-2 cycle of [imath]g[/imath] distinct from {0, -1}. But we already established that {0, -1} is the only period-2 cycle of [imath]g[/imath]: contradiction.

Therefore no such function [imath]f[/imath] exists.

This is one of my favorite proofs, as it establishes the nonexistence of a function merely in terms of its behavior at two points, whereas the condition [imath]f(f(x)) = x^2 - 1[/imath] lures people into considering global behavior and getting sidetracked into proofs for the differentiable or continuous cases.
"Now I shall have less distraction"
--Leonhard Euler, on losing sight in his right eye

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: The Theorem Thread

Postby t0rajir0u » Thu Feb 19, 2009 10:29 pm UTC

stephentyrone wrote:The point is that you don't need to require the entirety of the complex numbers to formulate the theorem.

The FTA as it's usually stated is precisely a statement about the entirety of the complex numbers: it states that [imath]\mathbb{C}[/imath] is algebraically closed. So I'm still not sure what you mean. (One could go so far as to say that it is the stronger statement that [imath]\mathbb{R}[/imath] has a unique (up to isomorphism) algebraic closure, which is clearly not true of, say, the [imath]p[/imath]-adics.)

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: The Theorem Thread

Postby GreedyAlgorithm » Fri Feb 20, 2009 4:29 pm UTC

A polyhedron must have a pair of faces with the same number of edges.

Spoiler:
Each face must have at least 3 edges. Since no two edges of a face are shared by the same other face, each face must have at most F-1 faces, for a polyhedron with F faces. So each face has between 3 and F-1 faces, and there are at most F-1-3+1=F-3 < F possible numbers of edges, but F faces. Pigeons FTW.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: The Theorem Thread

Postby Cycle » Fri Feb 20, 2009 4:45 pm UTC

Wait, huh? I thought every field has a unique algebraic closure. Anyways, "R has a unique algebraic closure" isn't equivalent. Neither is "there exists the algebraic numbers". The statement is "C contains the algebraic numbers" works, I guess. That's why every proof of it uses either the topology of C, or the algebraic properties of R. In fact, in the spirit of the thread:

proof: suppose p(z) is a monic degree n polynomial without roots. Then [imath]p(r e^{it}), r \in \mathbb{R}^+ , t \in S^1[/imath] is a homotopy to a constant loop, in [imath]\mathbb{C} \setminus 0[/imath]. Fix r very large, say bigger than 10(|a0|+...+|an-1|). It's clear that p(r eit) is homotopic to the map rneint by the homotopy zn + s(an-1zn-1+...+a0), where 0<s<1. So, our curve, p(r eit) is equal to both 0 (homotopy class of a constant) and n (homotopy class of zn) in [imath]\pi_1(\mathbb{C} \setminus 0)[/imath]. Thus, n=0.
Last edited by Cycle on Fri Feb 20, 2009 4:50 pm UTC, edited 1 time in total.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: The Theorem Thread

Postby Macbi » Fri Feb 20, 2009 4:49 pm UTC

GreedyAlgorithm wrote:A polyhedron must have a pair of faces with the same number of edges.

Spoiler:
Each face must have at least 3 edges. Since no two edges of a face are shared by the same other face, each face must have at most F-1 faces, for a polyhedron with F faces. So each face has between 3 and F-1 faces, and there are at most F-1-3+1=F-3 < F possible numbers of edges, but F faces. Pigeons FTW.
That, is awesome. It also has an obvious colorrary that there is a pair of vertecies with the same number of edges.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: The Theorem Thread

Postby t0rajir0u » Fri Feb 20, 2009 5:40 pm UTC

Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.

Nope. The p-adic rationals have infinitely many non-isomorphic algebraic closures.

Cycle wrote:The statement is "C contains the algebraic numbers" works, I guess.

This is much weaker than the statement that [imath]\mathbb{C}[/imath] is itself algebraically closed; compare to the statement "[imath]\mathbb{C}[x][/imath] contains the algebraic numbers."

User avatar
Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: The Theorem Thread

Postby Cycle » Fri Feb 20, 2009 6:01 pm UTC

t0rajir0u wrote:
Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.

Nope. The p-adic rationals have infinitely many non-isomorphic algebraic closures.


I'm pretty sure you mean algebraic extensions.

t0rajir0u wrote:
Cycle wrote:The statement is "C contains the algebraic numbers" works, I guess.

This is much weaker than the statement that [imath]\mathbb{C}[/imath] is itself algebraically closed; compare to the statement "[imath]\mathbb{C}[x][/imath] contains the algebraic numbers."


That's true. Or, as a subfield of C, A(e), where A is the algebraics. x2-e has no root.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: The Theorem Thread

Postby Token » Fri Feb 20, 2009 6:10 pm UTC

Cycle wrote:
t0rajir0u wrote:
Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.

Nope. The p-adic rationals have infinitely many non-isomorphic algebraic closures.


I'm pretty sure you mean algebraic extensions.

Probably. Assuming the axiom of choice, any two algebraic closures of a field K are K-isomorphic.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: The Theorem Thread

Postby Blatm » Fri Apr 17, 2009 4:51 pm UTC

Theorem: The ratio of even numbers in Pascal's triangle to the number of odd numbers in Pascal's triangle tends to 1 as the size of the triangle grows.

Proof (it's pretty easy):
Spoiler:
Plot the triangle mod 2. You get something analogous to the Sierpenski triangle, and you can apply the same reasoning that you would use to show that the area is 0.


Unfortunately, I can't think of a very nice way to state the proof.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: The Theorem Thread

Postby t0rajir0u » Fri Apr 17, 2009 6:26 pm UTC

Lucas' theorem. As the number of binary digits increases, it becomes increasingly unlikely that each term in the statement of Lucas' theorem is odd, which can be made precise by choosing a uniform distribution the numbers with at most [imath]d[/imath] binary digits and picking each digit independently.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests