The Theorem Thread
Moderators: gmalivuk, Moderators General, Prelates
The Theorem Thread
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 3connected subgraphs, the following formula holds: #connected components#cycles=ne
PROOF: By induction on number of edges.
Base Case: If there are no edges, then there are n connected components and no cycles. n0=ne 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 kc=ne, 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 3connected subgraphs in the new graph, so there was exactly one path between u and v before. But once again, we've gone from kc=ne to k(c+1)=kc1=ne1=n(e+1), so equality still holds.
Q.E.D.
FACT: For a graph on n vertices and e edges and no 3connected subgraphs, the following formula holds: #connected components#cycles=ne
PROOF: By induction on number of edges.
Base Case: If there are no edges, then there are n connected components and no cycles. n0=ne 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 kc=ne, 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 3connected subgraphs in the new graph, so there was exactly one path between u and v before. But once again, we've gone from kc=ne to k(c+1)=kc1=ne1=n(e+1), so equality still holds.
Q.E.D.
Re: The Theorem Thread
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 a^{2}+b^{2}=n, then
[math]\lim_{N\rightarrow \infty} \frac 1 N \sum_{k=0}^{N1} s(n) = \pi[/math]
Proof: [imath]\sum_{k=0}^{N1} s(n)[/imath] is the number of lattice points (a,b) such that a^{2}+b^{2} < 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}^{N1} s(n) = \pi R^2 + o(R)= \pi N + o(N^{1/2})[/imath], so
[math]\frac{1}{N}\sum_{k=0}^{N1} 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].
More precisely, if s(n) is the number of pairs of integers (a,b) such that a^{2}+b^{2}=n, then
[math]\lim_{N\rightarrow \infty} \frac 1 N \sum_{k=0}^{N1} s(n) = \pi[/math]
Proof: [imath]\sum_{k=0}^{N1} s(n)[/imath] is the number of lattice points (a,b) such that a^{2}+b^{2} < 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}^{N1} s(n) = \pi R^2 + o(R)= \pi N + o(N^{1/2})[/imath], so
[math]\frac{1}{N}\sum_{k=0}^{N1} 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?
Re: The Theorem Thread
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] nonconstant [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_{n1}z^{n1}+\ldots+a_1z+a_0[/imath]. Then [imath]f(z) \geq z^na^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_{n1}z^{n1}+\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_{n1}z^{n1}+\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_0c_kr^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.
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] nonconstant [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_{n1}z^{n1}+\ldots+a_1z+a_0[/imath]. Then [imath]f(z) \geq z^na^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_{n1}z^{n1}+\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_{n1}z^{n1}+\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_0c_kr^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.
 Something Awesome
 Posts: 47
 Joined: Sun May 18, 2008 10:53 pm UTC
 Location: NY
Re: The Theorem Thread
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]
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]

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
Re: The Theorem Thread
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.
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.
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.
Re: The Theorem Thread
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.
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.

 Posts: 18
 Joined: Thu Jan 15, 2009 4:33 am UTC
Re: The Theorem Thread
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):
Hint 2:
Proof:
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:
Hint 2:
Spoiler:
Proof:
Spoiler:
"Now I shall have less distraction"
Leonhard Euler, on losing sight in his right eye
Leonhard Euler, on losing sight in his right eye
Re: The Theorem Thread
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.)

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
Re: The Theorem Thread
A polyhedron must have a pair of faces with the same number of edges.
Spoiler:
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
Re: The Theorem Thread
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(a_{0}+...+a_{n1}). It's clear that p(r e^{it}) is homotopic to the map r^{n}e^{int} by the homotopy z^{n} + s(a_{n1}z^{n1}+...+a_{0}), where 0<s<1. So, our curve, p(r e^{it}) is equal to both 0 (homotopy class of a constant) and n (homotopy class of z^{n}) in [imath]\pi_1(\mathbb{C} \setminus 0)[/imath]. Thus, n=0.
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(a_{0}+...+a_{n1}). It's clear that p(r e^{it}) is homotopic to the map r^{n}e^{int} by the homotopy z^{n} + s(a_{n1}z^{n1}+...+a_{0}), where 0<s<1. So, our curve, p(r e^{it}) is equal to both 0 (homotopy class of a constant) and n (homotopy class of z^{n}) 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.
Re: The Theorem Thread
That, is awesome. It also has an obvious colorrary that there is a pair of vertecies with the same number of edges.GreedyAlgorithm wrote:A polyhedron must have a pair of faces with the same number of edges.Spoiler:
 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.
Re: The Theorem Thread
Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.
Nope. The padic rationals have infinitely many nonisomorphic 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."
Re: The Theorem Thread
t0rajir0u wrote:Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.
Nope. The padic rationals have infinitely many nonisomorphic 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. x^{2}e has no root.
Re: The Theorem Thread
Cycle wrote:t0rajir0u wrote:Cycle wrote:Wait, huh? I thought every field has a unique algebraic closure.
Nope. The padic rationals have infinitely many nonisomorphic 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 Kisomorphic.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Re: The Theorem Thread
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):
Unfortunately, I can't think of a very nice way to state the proof.
Proof (it's pretty easy):
Spoiler:
Unfortunately, I can't think of a very nice way to state the proof.
Re: The Theorem Thread
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.
Who is online
Users browsing this forum: No registered users and 14 guests