组合数学 (Fall 2011)/Pólya's theory of counting and Graham's number: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Zabshk
(Reverted vandalism.)
 
Line 1: Line 1:
== Groups ==
{{Orphan|date=December 2010}}
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
'''Graham's number''' is a very, very big [[natural number]] that was defined by a man named Ronald Graham. Graham was solving a problem in an area of mathematics called [[Ramsey theory]]. He proved that the answer to his problem was smaller than Graham's number.
* closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
* associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.


=== Permutation groups===
Graham's number is one of the biggest numbers ever used in a [[mathematical proof]]. Even if every digit in Graham's number were written in the tiniest writing possible, it would still be too big to fit in the [[observable universe]].


==== Cycle decomposition ====
==Context==


=== Group action ===
Ramsey theory is an area of mathematics that asks questions like the following:
{{Theorem|Definition (group action)|
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}


== Burnside's Lemma ==
{{quote|<p>Suppose we draw some number of points, and connect every pair of points by a line. Some lines are blue and some are red. Can we always find 3 points for which the 3 lines connecting them are all the same color?}}


=== Orbits ===
It turns out that for this simple problem, the answer is "yes" when we have 6 or more points, no matter how the lines are colored. But when we have 5 points or fewer, we can color the lines so that the answer is "no".
Let <math>G</math> be a permutation group acting on a set <math>X</math>. Let <math>\pi\in G, x\in X</math>.
* The '''invariant set''' of <math>\pi</math>:
::<math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math>.
* The '''stabilizer''' of <math>x</math>:
::<math>G_x=\{\pi\in G\mid \pi\circ x=x\}</math>.
* The '''orbit''' of <math>x</math> under action of <math>G</math>:
::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.


We think of <math>X</math> as a set of configurations which we may count up to certain symmetry induced by the group action.
Graham's number comes from a variation on this question.


=== Counting orbits===
{{quote|<p>Once again, say we have some points, but now they are the corners of an ''n''-dimensional [[hypercube]]. They are still all connected by blue and red lines. For any 4 points, there are 6 lines connecting them. Can we find 4 points that all lie on one [[Plane (mathematics)|plane]], and the 6 lines connecting them are all the same color?}}


{{Theorem|Lemma|
By asking that the 4 points lie on a plane, we have made the problem much harder. We would like to know: for what values of ''n'' is the answer "no" (for some way of coloring the lines), and for what values of ''n'' is it "yes" (for all ways of coloring the lines)? But this problem has not been completely solved yet.
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>,
::<math>|G_x||Gx|=|G|\,</math>.
}}
{{Proof|
Recall that the orbit <math>Gx=\{\pi\circ x\mid \pi\in G\}</math>. Suppose that <math>Gx=\{x_1,x_2,\ldots,x_t\}</math>. Then there exist a set <math>P=\{\pi_1,\pi_2,\ldots,\pi_t\}</math> of permutations such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>. We construct a bijection between <math>G</math> and <math>P\times G_x</math>, which will prove the lemma.


For any <math>\pi\in G</math>, it holds that <math>\pi\circ x=x_i</math> for some <math>x_i</math>, and since <math>\pi_i\circ x=x_i</math>, we have
In 1971, Ronald Graham and B. L. Rothschild found a partial answer to this problem. They showed that for ''n''=6, the answer is "no". But when ''n'' is very large, as large as Graham's number or larger, the answer is "yes".
<math>\pi_i\circ x=\pi\circ x</math>, hence
:<math>(\pi_i^{-1}\cdot\pi)\circ x=\pi_i^{-1}\circ(\pi\circ x)=\pi_i^{-1}\circ(\pi_i\circ x)=(\pi_i^{-1}\cdot\pi_i)\circ x=e\circ x=x</math>.  
Denote that <math>\sigma=\pi_i^{-1}\cdot \pi</math>. Then
*<math>\pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi</math>, and
*<math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>.  
Therefore, each <math>\pi\in G</math> corresponds to a unique pair <math>(\pi_i,\sigma)\in P\times G_x</math>. We have a 1-1 mapping from <math>G</math> to <math>P\times G_x</math>.


For every <math>\pi_i\in P</math> and every <math>\sigma\in G_x</math>, <math>\pi=\pi_i\cdot\sigma\in G</math>. We show that this is a 1-1 mapping. Suppose that <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math> for some <math>\pi_i,\pi_j\in P</math> and <math>\sigma,\tau\in G_x</math>. Then <math>(\pi_i\cdot\sigma)\circ x=\pi_i\circ(\sigma\circ x)=\pi_i\circ x=x_i</math> and <math>(\pi_j\cdot \tau)\circ x=\pi_j\circ(\tau\circ x)=\pi_j\circ x=x_j</math>, which implies <math>x_i=x_j</math> and correspondingly <math>\pi_i=\pi_j</math>. Since <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math>, <math>\sigma=\tau</math>. Therefore, we show that the mapping is 1-1.
One of the reasons this partial answer is important is that it means that the answer is eventually "yes" for at least some large ''n''. Before 1971, we didn't know even that much.


In conclusion, there exists a bijection between <math>P\times G_x</math> and <math>G</math>. As a consequence, <math>|Gx||G_x|=|P||G_x|=|P\times G_x|=|G|</math>.
==Definition==
}}


{{Theorem|Burnside's Lemma|
Graham's number is not only too big to write down all of its digits, it is too big even to write in [[scientific notation]]. In order to be able to write it down, we have to use [[Knuth's up-arrow notation]].
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. The number of orbits, denoted <math>|X/G|</math>, is  
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
}}
{{Proof|
Let
:<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
:<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
Then a double counting gives that
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x|</math>.


Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
We will write down a [[sequence]] of numbers that we will call '''g1''', '''g2''', '''g3''', and so on. Each one will be used in an equation to find the next. '''g64 is''' Graham's number.
:<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Suppose there are <math>m</math> orbits <math>X_1,X_2,\ldots,X_m</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
:<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^m1=|G|m</math>.
Combining everything together
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|m</math>,
which gives us that the number of orbits is
:<math>m=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|</math>.
}}


==Pólya's Theory of Counting ==
First, here are some examples of up-arrows:
=== The cycle index ===


=== Pólya's enumeration formula ===
* <math>3\uparrow3</math> is 3x3x3 which equals 27. An arrow between two numbers just means the first number multiplied by itself the second number of times.
* You can think of <math>3 \uparrow \uparrow 3</math> as <math>3 \uparrow (3 \uparrow 3)</math> because two arrows between numbers A and B just means A written down a B number of times with an arrow in between each A. Because we know what single arrows are, <math>3\uparrow(3\uparrow3)</math> is 3 multiplied by itself <math>3\uparrow3</math> times and we know <math>3\uparrow3
</math> is twenty-seven. So <math>3\uparrow\uparrow3</math> is 3x3x3x3x....x3x3, in total 27 times. That equals 7625597484987.
* <math>3 \uparrow \uparrow \uparrow 3</math> is <math>3 \uparrow \uparrow (3 \uparrow \uparrow 3)</math> and we know <math>3\uparrow\uparrow3</math> is 7625597484987. So <math>3\uparrow\uparrow(3\uparrow\uparrow3)</math> is <math>3\uparrow \uparrow 7625597484987</math>. That can also be written as <math>3\uparrow(3\uparrow(3\uparrow(3\uparrow . . .(3\uparrow(3\uparrow(3\uparrow3)</math> with a total of 7625597484987 3s. This number is so huge, its digits, even written very small, could fill up the observable universe and beyond.
** Although this number may already be beyond comprehension, this is barely the start of  this giant number.
* The next step like this is <math>3 \uparrow \uparrow \uparrow \uparrow 3</math> or <math>3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)</math>. This is the number we will call '''g1'''.


=== de Bruijn's generalization===
After that, '''g2''' is equal to <math>3\uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow 3</math>; the number of arrows in this number is '''g1'''.
 
'''g3''' is equal to <math>3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3</math>, where the number of arrows is '''g2'''.
 
We keep going in this way. We stop when we define '''g64''' to be <math>3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3</math>, where the number of arrows is '''g63'''.
 
This is Graham's number.
 
==Related pages==
* [[Knuth's up-arrow notation]]
 
[[Category:Mathematics]]
[[Category:Hyperoperations]]
[[Category:Integers]]

Latest revision as of 20:06, 6 April 2017

Template:Orphan Graham's number is a very, very big natural number that was defined by a man named Ronald Graham. Graham was solving a problem in an area of mathematics called Ramsey theory. He proved that the answer to his problem was smaller than Graham's number.

Graham's number is one of the biggest numbers ever used in a mathematical proof. Even if every digit in Graham's number were written in the tiniest writing possible, it would still be too big to fit in the observable universe.

Context

Ramsey theory is an area of mathematics that asks questions like the following:

Template:Quote

It turns out that for this simple problem, the answer is "yes" when we have 6 or more points, no matter how the lines are colored. But when we have 5 points or fewer, we can color the lines so that the answer is "no".

Graham's number comes from a variation on this question.

Template:Quote

By asking that the 4 points lie on a plane, we have made the problem much harder. We would like to know: for what values of n is the answer "no" (for some way of coloring the lines), and for what values of n is it "yes" (for all ways of coloring the lines)? But this problem has not been completely solved yet.

In 1971, Ronald Graham and B. L. Rothschild found a partial answer to this problem. They showed that for n=6, the answer is "no". But when n is very large, as large as Graham's number or larger, the answer is "yes".

One of the reasons this partial answer is important is that it means that the answer is eventually "yes" for at least some large n. Before 1971, we didn't know even that much.

Definition

Graham's number is not only too big to write down all of its digits, it is too big even to write in scientific notation. In order to be able to write it down, we have to use Knuth's up-arrow notation.

We will write down a sequence of numbers that we will call g1, g2, g3, and so on. Each one will be used in an equation to find the next. g64 is Graham's number.

First, here are some examples of up-arrows:

  • [math]\displaystyle{ 3\uparrow3 }[/math] is 3x3x3 which equals 27. An arrow between two numbers just means the first number multiplied by itself the second number of times.
  • You can think of [math]\displaystyle{ 3 \uparrow \uparrow 3 }[/math] as [math]\displaystyle{ 3 \uparrow (3 \uparrow 3) }[/math] because two arrows between numbers A and B just means A written down a B number of times with an arrow in between each A. Because we know what single arrows are, [math]\displaystyle{ 3\uparrow(3\uparrow3) }[/math] is 3 multiplied by itself [math]\displaystyle{ 3\uparrow3 }[/math] times and we know [math]\displaystyle{ 3\uparrow3 }[/math] is twenty-seven. So [math]\displaystyle{ 3\uparrow\uparrow3 }[/math] is 3x3x3x3x....x3x3, in total 27 times. That equals 7625597484987.
  • [math]\displaystyle{ 3 \uparrow \uparrow \uparrow 3 }[/math] is [math]\displaystyle{ 3 \uparrow \uparrow (3 \uparrow \uparrow 3) }[/math] and we know [math]\displaystyle{ 3\uparrow\uparrow3 }[/math] is 7625597484987. So [math]\displaystyle{ 3\uparrow\uparrow(3\uparrow\uparrow3) }[/math] is [math]\displaystyle{ 3\uparrow \uparrow 7625597484987 }[/math]. That can also be written as [math]\displaystyle{ 3\uparrow(3\uparrow(3\uparrow(3\uparrow . . .(3\uparrow(3\uparrow(3\uparrow3) }[/math] with a total of 7625597484987 3s. This number is so huge, its digits, even written very small, could fill up the observable universe and beyond.
    • Although this number may already be beyond comprehension, this is barely the start of this giant number.
  • The next step like this is [math]\displaystyle{ 3 \uparrow \uparrow \uparrow \uparrow 3 }[/math] or [math]\displaystyle{ 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) }[/math]. This is the number we will call g1.

After that, g2 is equal to [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow 3 }[/math]; the number of arrows in this number is g1.

g3 is equal to [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3 }[/math], where the number of arrows is g2.

We keep going in this way. We stop when we define g64 to be [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3 }[/math], where the number of arrows is g63.

This is Graham's number.

Related pages

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Pólya%27s_theory_of_counting&oldid=7724"