Transcript Open Problems Powerpoint

Stuff I Don’t Know
Unsolved Problems in Mathematics
Collatz Conjecture
• “The Simplest, Impossible Problem”
• Pick a number (positive integer)
– If it’s even, cut it in half
– If it’s odd, triple it then add one
– Repeat
• Will you eventually end up at one?
– If not, you solved a problem that has baffled
mathematicians for almost 80 years.
• “Mathematics might not be ready for such
problems” - Erdos
Collatz Conjecture
• If you picked 27, it took you 111 steps, and
you got as high as 9232, before getting to 1.
• If you picked 63,728, 127 it took you 949 steps
• Confirmed up to 2 to the 60th power
– Aka 1.1 Quintillion
– Can you confirm it for any numbers bigger than
that?
Careful with Empirical “Proofs”
Collatz Stopping Time
CST Histogram
• Math 243 fans? Who loves histograms?
• Stopping times for 1 to 100 million
Collatz Trajectory
Collatz in Reverse
Collatz Map, n = 20
Collatz Map, n = 30
Collatz Map, n = 50
Collatz Map, n = 100
Collatz Map, n = 500
Collatz Map, n = 10,000
Collatz 3D Map, n = 10,000
Collatz Fractal
xkcd’s Take on Collatz
Chromatic Number of the Plane
• Aka the Hadwiger – Nelson Problem
• Chromatic number: minimum colors needed,
to paint vertices, so no two adjascent vertices
share a color.
• Quiz?
• Quiz!
Chromatic Warm-up
Determine the Chromatic number of each of the 6 graphs below.
Chromatic Challenge
It was 3!
Chromatic Challenge II
Not 3!
Similar to 4-color theorem
• With four colors, you can color regions in any
map, without having adjacent regions the
same color
4-Color Theorem Example
Infinite Map?
• What if every point in the plane were connected
to all points a distance of one from it?
• How many colors to “color the plane”?
Not less than 4!
Not more than 7!
Open Quesitons
• So we know the chromatic number of the
plane is at least 4 and at most 7.
– So what is it?
– Nobody knows?
– I guess 4… people are good at finding
counterexamples.
• What about the chromatic number of 3
space?
– At least 6 and at most 15, but no clue which.
“Most Unsolved” Question?
• Prime numbers!
• DNA of integers, but we can’t predict them
• Arbitrarily large gaps between them, but they
never run out
• Infinitely many, but no easy way to find or
verify them
• Make up a prime question, it’s probably open.
Prime producing function
• In short, we don’t know of one.
– In 1947 Mills proved that
prime, for some A.
3n ) ú
(
ê
is always
m(n) = A
êë
úû
• Unfortunately we don’t know what A is
• We don’t even know if A is rational or irrational
• Not aesthetically pleasing to use floor function
• Bottom line is that we don’t know of any
prime producing function
– but we know there is one
– Hopefully a prettier one than the above
Random?
• Primes appear to be scattered at random.
– No (known) way to generate them
– No (known) way to (easily) tell if a number is
prime
– So are they scattered randomly?
– Is there a pattern that we’re not smart enough to
see?
• Yes
– Hypothesized by Brian Stonelake (2013)
First 100 primes
But base 10 is arbitrary.
Less Arbitrary Visual Representations
Archimedean Spiral
Less Arbitrary Visual Representations
Sack’s Spiral: Uses Archimedean Spiral
Less Arbitrary Visual Representations
- Variant of Sach’s
Spiral
- Dot size determined
by unique prime
factors
Prime producing function?
2 )
(
f (n) = 2 +1are prime.
n
•
In 1641, Fermat stated that all numbers of the form
Called Fermat primes.
– f(0) = 3. Prime.
– f(1) = 5. Prime.
– f(2) = 17. Prime.
– f(3) = 257. Prime.
– f(4) = 65,537. Prime.
• Convinced?
– Roughly 100 years later, Euler showed that f(5)= 4,294,967,297 = 641 x
6,700,417. Composite!
• Today f(4) is still the largest known Fermat prime
– We know Fermat numbers from 5 to 32 are composite
• Those are big numbers. f(9) > # atoms in universe!
– We know f(2,747,497) is composite (largest known Fermat composite)
– We don’t know if there are any more Fermat primes
• We don’t know that there aren’t infinitely many Fermat primes
• We don’t know if there are infinitely many Fermat composites
Other Open Prime Questions
• Infinitely many:
– Twin primes?
– Palindrome primes?
– Sexy primes?
– Fibbonacci primes?
– Circular primes?
– Permutable primes
– Repunit primes?
– Repunit primes in other bases?
Goldbach Conjecture
Can any even number be expressed as the sum of two primes?
Goldbach Conjecture
Number of ways two primes sum to each even integer up to 1,000
Goldbach Conjecture
Number of ways two primes sum to each even integer up to 1,000,000
Gaussian Primes
• Same idea, but extended to complex numbers.
• Turns out 2 + i and 2 – i are Gaussian prime.
– So is 3.
– What about 5?
• Not as mysterious as you might hope…
– a + bi prime iff a 2 + b 2 prime, for example
• But they look cool on a graph!
Gaussian Primes
Gaussian Primes
Gaussian Primes
• Is there a giant that could walk on Gaussian
primes to infinity?
– Nobody knows
– Best we can do is say that a giant that can’t jump 6
couldn’t do it!
– We know there are “moats” of arbitrary size around
Gaussian primes, but that doesn’t help
• Infinitely many?
– Yes. In fact, Infinitely many that are ordinary primes.
• Largest known (absolute value) is (1+ i )1,203,793 -1
– Real and imaginary parts have 181,189 digits!
Most Important Unsolved Problem
• “The non-trivial zeros of the Reimann zeta
function z ( s ), all have real part ½.”
z ( s ) = å n=1
¥
1
1 1 1 1 1 1 1 1
1
=
1+
+
+
+
+
+
+
+
+
+ ... if  ( s ) > 1
s
s
s
s
s
s
s
s
s
s
n
2 3 4 5 6 7 8 9 10
• Really the analytic continuation of the above
• Millennium Prize Problem
• True for Á( s ) < 2.4 trillion
Sieve of Erastothenes
Amazingly,
z ( s ) = å n=1
¥
1
- s -1
=
1p
(
)
å n=1 n s Õ
p
¥
!
1
1 1 1 1 1 1 1 1
1
= 1+ s + s + s + s + s + s + s + s + s + ...
s
n
2 3 4 5 6 7 8 9 10
1
1 1 1 1
1
1
1
1
1
1
z ( s ) = s + s + s + s + s + s + s + s + s + s + ...
s
2
2 4 6 8 10 12 14 16 18 20
z ( s) -
1
1 1 1 1
1
1
1
1
1
z ( s ) = 1+ s + s + s + s + s + s + s + s + s + ...
s
2
3 5 7 9 11 13 15 17 19
1ö
1 1 1 1
1
1
1
1
1
æ
çè 1- s ÷ø z ( s ) = 1+ s + s + s + s + s + s + s + s + s ...
2
3 5 7 9 11 13 15 17 19
1æ
1ö
1 1
1
1
1
1
1
1
1
1
1- s ÷ z ( s ) = s + s + s + s + s + s + s + s + s + s ...
s ç
3 è 2 ø
3 9 15 21 27 33 39 45 51 57
1ö
1æ
1ö
1 1
1
1
1
1
1
1
1
1
æ
çè 1- s ÷ø z ( s ) - s çè 1- s ÷ø z ( s ) = 1+ s + s + s + s + s + s + s + s + s + s + ...
2
3
2
5 7 11 13 17 23 25 29 31 35
1 öæ
1ö
1 1
1
1
1
1
1
1
1
1
æ
çè 1- s ÷ø çè 1- s ÷ø z ( s ) = 1+ s + s + s + s + s + s + s + s + s + s ...
2
3
5 7 11 13 17 23 25 29 31 35
æ
è
1 öæ
1 öæ
1 öæ
1 öæ
1 öæ
1 öæ
1 öæ
1 ö
1- s ÷ ç 1- s ÷ ç 1- s ÷ ç 1- s ÷ ç 1- s ÷ ç 1- s ÷ ç 1- s ÷ ... = 1
s֍
2 ø è 3 ø è 5 ø è 7 ø è 11 ø è 13 ø è 17 ø è 23 ø
-1
1
z ( s) =
= Õ (1- p - s )
-s
Õ (1- p ) p
z ( s ) ç 1-
p
Enough Algebra, Pictures Please
Last Picture
Slides available at http://webpages.sou.edu/~stonelakb/math/