Transcript (0, 0, 0) and (1, 1, 1).

North-East Students’ Summer Training
on Basic Science
NESST-BASE
Bose Institute, Mayapuri, Darjeeling
June 2, 2007
Mathematics,
an Attractive Science
Michel Waldschmidt
Université P. et M. Curie Paris VI
Centre International de Mathématiques Pures et Appliquées
CIMPA
http://www.math.jussieu.fr/~miw/
L’explosion
des
Mathématiques
http://smf.emath.fr/Publicati
on/
ExplosionDesMathematique
s/ Presentation.html
Explosion of Mathematics
•
•
•
•
•
Weather forecast
Cell phones
Cryptography
Control theory
From DNA to knot theory
• Air transportation
• Internet: modelisation of
traffic
• Communication without
errors
• Reconstruction of surfaces
for images
Société Mathématique de France
Société de Mathématiques Appliquées et Industrielles
Aim:
To illustrate with a few examples the
usefulness of some mathematical theories
which were developed only for theoretical
purposes
Unexpected interactions between pure
research and the real world .
Interactions between physics and
mathematics
• Classical mechanics
• Non-Euclidean geometry:
Bolyai, Lobachevsky, Poincaré, Einstein
• String theory
• Global theory of particles and their
interactions: geometry in 11 dimensions?
Eugene Wigner:
« The unreasonable effectiveness
of mathematics in the natural
sciences »
Communications in Pure and Applied Mathematics,
vol. 13, No. I (February 1960)
Dynamical systems
Three body problems
(Henri Poincaré)
Chaos theory (Edward Lorentz):
the butterfly effect:
Due to nonlinearities in weather processes, a
butterfly flapping its wings in Tahiti can, in
theory, produce a tornado in Kansas.
Weather forecast
Probabilistic model for the climate
Stochastic partial differential equations
Statistics
Weather forecast
• Mathematical models are required for
describing and understanding the processes
of meteorology, in order to analyze and
understand the mechanisms of the climate.
• Some processes in meteorology are
chaotic, but there is a hope to perform
reliable climatic forecast.
Knot theory in
algebraic topology
• Classification of knots, search of invariants
• Surgical operations
Knot theory and molecular
biology
• The topology of DNA
molecule has an action on its
biological action.
• The surgical operations
introduced in algebraic
topology have biochemical
equivalents which are realized
by topoisomerases.
Finite fields and coding theory
• Solving algebraic equations
with radicals: Finite fields theory
Evariste Galois (1811-1832)
• Construction of regular polygons with rule
and compass
• Group theory
Error Correcting Codes
Data Transmission
•
•
•
•
•
Telephone
CD or DVD
Image transmission
Sending information through the Internet
Radio control of satellites
Olympus Mons on
Mars Planet
Image from
Mariner 2 in 1971.
Sphere packing
The kissing number is 12
Sphere Packing
• Kepler Problem: maximal density of a
packing of identical sphères :
p /  18= 0.740 480 49…
Conjectured in 1611.
Proved in 1999 by Thomas Hales.
• Connections with crystallography.
Codes and Geometry
• 1949 Golay (specialist of radars): efficient
code
• Eruptions on Io (Jupiter’s volcanic moon)
• 1963 John Leech: uses Golay’s ideas for
sphere packing in dimension 24 classification of finite simple groups
Data transmission
French-German war of 1870, siege of
Paris
Flying pigeons : first crusade - siege of Tyr,
Sultan of Damascus
Data transmission
• James C. Maxwell
(1831-1879)
• Electromagnetism
Cell Phones
Information Theory
Transmission by Hertz waves
Algorithmic, combinatoric optimization,
numerical treatment of signals, error correcting
codes.
How to distribute frequencies among users.
Data Transmission
Transmission
Source
Receiver
Language Theory
• Alphabet - for instance {0,1}
• Letters (or bits): 0 and 1
• Words (octets - example 0 1 0 1 0 1 0 0)
ASCII
American Standard Code for Information
Interchange
Letters
A:
B:
…
octet
01000001
01000010
…
Coding
transmission
Source
Coded
Text
Coded
Text
Receiver
Error correcting codes
Applications of
error correcting codes
•
Transmitions by satellites
•
Compact discs
•
Cellular phones
Codes and Maths
•
Algebra
(discrete mathematics finite
fields, linear algebra,…)
•
Geometry
•
Probability and statistics
Coding
transmission
Source
Coded
Text
Coded
Text
Receiver
Coding
transmission
Source
Coded
Text
Coded
Text
Noise
Receiver
Principle of coding theory :
only certain words are permitted (code =
dictionary of allowed words).
The « useful » letters carry the information,
the other ones (control bits) allow detecting
errors.
Detecting one error
• Send twice the same
message
Code words
(two letters)
00
11
2 code words on 4=22
(1 useful letter of 2)
Rate: 1/2
Correcting an error
• Send the same
message three times
Code words
(three letters)
000
111
2 code words of 8=23
(1 useful letter of 3)
Rate: 1/3
• Correct
•
•
and
•
•
•
0 0 1 as 0 0 0
0 1 0 as 0 0 0
1 0 0 as 0 0 0
1 1 0 as 1 1 1
1 0 1 as 1 1 1
0 1 1 as 1 1 1
Principle of coding correcting one error:
Two distinct code words have at least
three distinct letters
Detecting one error (again)
Code words (three letters):
000
011
101
110
Parity bit : (x y z) with z=x+y.
4=22=2 code words of 8=23
2
(2 useful letters of 3).
Rate: 2/3
Code words Non code words
0
0
1
1
0
1
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
0
1
Two distinct code words have at least
two distinct letters.
Correcting one error (again)
Words of 7 letters
Code words: (16=24 on 128=27 )
(a b c d e f g)
with
e=a+b+d
f=a+c+d
g=a+b+c
Rate: 4/7
How to compute e , f , g , from a , b , c , d.
e=a+b+d
d
b
a
c
g=a+b+c
f=a+c+d
16 code words of 7 letters
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
0
1
1
0
0
1
Two distinct code words have at least three distinct letters
1
1
0
0
0
0
1
1
Listening to a CD
• On a CD as well as on a computer, each
sound is coded by a sequence of 0’s and 1’s,
grouped in octets
• Further octets are added which detect and
correct small mistakes.
Coding the sound on a CD
Using a finite field with 256 elements, it is
possible to correct 2 errors in each word of
32 octets with 4 control octets for 28
information octets.
A CD of high quality may have more
than 500 000 errors!
• 1 second of radio signal = 1 411 200 bits.
• The mathematical theory of error correcting codes provides
more reliability and at the same time decreases the cost. It
is used also for data transmission via the internet or
satellites
Informations was sent to the earth using an
error correcting code which corrected 7 bits
on 32.
In each group of 32 bits, 26 are control bits
and the 6 others contain the information.
Voyager 1 and 2 (1977)
• Journey: Cape Canaveral, Jupiter, Saturn,
Uranus, Neptune.
• Sent information by means of a binary code
which corrected 3 errors on words of length
24.
Mariner spacecraft 9 (1979)
• Sent black and white photographs of Mars
• Grid of 600 by 600, each pixel being
assigned one of 64 brightness levels
• Reed-Muller code with 64 words of 32
letters, minimal distance 16, correcting 7
errors, rate 3/16
Voyager (1979-81)
• Color photos of Jupiter and Saturn
• Golay code with 4096=212 words of 24
letters, minimal distance 8, corrects 3 errors,
rate 1/2.
• 1998: lost of control of Soho satellite
recovered thanks to double correction by
turbo code.
The binary code of
Hamming and Shannon (1948)
It is a linear code (the sum of two code
words is a code word) and the 16 balls of
radius 1 with centers in the code words
cover all the space of the 128 binary words
of length 7
(each word has 7 neighbors (7+1)16= 256).
The Hat Problem
• A team of three people in a room with
black/white hats on their head (hat colors
chosen at random). Each of them sees the
color on the hat of the others but not on his
own. They do not communicate.
• Everyone writes on a piece of paper the
color he guesses for his own hat:
black/white/abstain
• The team wins if at least one of the three
people does not abstain, and everyone who
did not abstain guesses correctly the color
of his hat.
• Simple strategy: they agree that two of
them abstain and the other guesses.
Probability of winning: 1/2.
• Is it possible to do better?
• Hint:
Improve the probability by using the
available information: each member of the
team knows the two other colors.
• Better strategy: if a member sees two
different colors, he abstains. If he sees the
same color twice, he guesses that his hat has
the other color.
Wins!
Loses!
Winning:
Losing:
• The team wins exactly when the three hats
do not have all the same color, that is in 6
cases of a total of 8
• Probability of winning: 3/4.
• Are there better strategies?
Answer: NO!
• Are there other strategies giving the same
probability 3/4?
Answer: YES!
Tails and Ends
• Throw a coin three consecutive times
• There are 8 possible sequences of results:
(0,0,0), (0,0,1), (0,1,0), (0,1,1),
(1,0,0), (1,0,1), (1,1,0), (1,1,1).
If you bet (0,1,0), you have :
• All three correct results for (0,1,0).
• Exactly two correct results if the sequence
is either
(0,1,1), (0,0,0) or (1,1,0),
• Exactly one correct result if the sequence is
either
(0,0,1), (1,1,1) or (1,0,0),
• No correct result at all for (1,0,1).
Whatever the sequence is, among 8
possibilities,
each bet
is winning in exactly 1 case
has exactly two correct results in 3 cases
has exactly one correct result in 3 cases
has no correct result at all in only 1 case
• Goal: To be sure of having at least two
correct results
• Clearly, one bet is not sufficient
• Are two bets sufficient?
Recall that there are 8 possible results,
and that each bet has at least two correct
results in 4 cases.
Answer: YES,
two bets suffice!
For instance bet
(0,0,0) and (1,1,1)
Whatever the result is, one of the two digits
0 and 1
occurs more than once.
Hence one (and only one) of the two bets
has at least two correct results.
Other solutions:
• Select any two bets with all three different
digits, say
0 0 1 and 1 1 0
The result either is one of these, or else has
just one common digit with one of these
and two common digits with the other.
• Come back with
(0,0,0) and (1,1,1)
The 8 sequences of three digits
0
and 1
split into two groups:
those with two or three 0’s
and
those with two or three 1’s
Hamming Distance
between two words:
= number of places where the two words
do not have the same letter
Examples:
(0,0,1) and (0,0,0) have distance 1
(1,0,1) and (1,1,0) have distance 2
(0,0,1) and (1,1,0) have distance 3
Richard W. Hamming (1915-1998)
Hamming Distance
• Recall that the Hamming distance between two words is
the number of places where letters differ.
• A code detects n errors iff the Hamming distance between
two distinct code words is at least 2n.
• It corrects n errors iff the Hamming distance between two
distinct code words is at least 2n+1.
• The set of eight elements splits into two
balls
• The centers are (0,0,0) and (1,1,1)
• Each of the two balls consists of elements
at distance at most 1 from the center
Back to the Hat Problem
• Replace white by 0 and black by 1
hence the distribution of colors becomes a
word of three letters on the alphabet {0 , 1}
• Consider the centers of the balls (0,0,0) and
(1,1,1).
• The team bets that the distribution of colors
is not one of the two centers.
Assume the distribution of hats does not
correspond to one of the centers
(0, 0, 0) and (1, 1, 1).
Then:
• One color occurs exactly twice (the word has both digits 0
and 1).
• Exactly one member of the team sees twice the same color:
this corresponds to 0 0 in case he sees two white hats, 1 1
in case he sees two black hats.
• Hence he knows the center of the ball: (0, 0, 0) in the first
case, (1, 1, 1) in the second case.
• He bets the missing digit does not yield the center.
• The two others see two different colors, hence
they do not know the center of the ball. They
abstain.
• Therefore the team win when the distribution of
colors does not correspond to the centers of the
balls.
• this is why the team win in 6 cases.
• Now if the word corresponding to the distribution
of the hats is one of the centers, all members of the
team bet the wrong answer!
• They lose in 2 cases.
Another strategy:
• Select two words with mutual distance 3
= two words with three distinct letters, say
(0,0,1) and (1,1,0)
• For each of them, consider the ball of
elements at distance at most 1
(0,0,0)
(0,0,1)
(1,0,1)
(1,1,1)
(0,1,1)
(1,1,0)
(0,1,0)
(1,0,0)
• The team bets that the distribution of colors
is not one of the two centers (0,0,1), (1,1,0)
.
• A word not in the center has exactly one
letter distinct from the center of its ball, and
two letters different from the other center.
Assume the word corresponding to the
distribution of the hats is not a center.
Then:
• Exactly one member of the team knows the center
of the ball. He bets the distribution does not
correspond to the center.
• The others do not know the center of the ball.
They abstain.
• Hence the team win.
The Hat Problem with 7 people
• The team bets that the distribution of the
hats does not correspond to the 16 elements
of the Hamming code
• Loses in 16 cases (they all fail)
• Wins in 128-16=112 cases (one bets
correctly, the 6 others abstain)
• Probability of winning: 112/128=7/8
Tossing a coin 7 times
• There are 128 possible results
• Each bet is a word of 7 letters on the
alphabet {0, 1}
• How many bets do you need if you want to
guarantee at least 6 correct results?
• Each of the 16 code words has 7 neighbors
(at distance 1), hence the ball of which it is
the center has 8 elements.
• Each of the 128 words is in exactly one of
these balls.
• Make 16 bets corresponding to the 16 code
words: then, whatever the result is, exactly
one of your bets will have at least 6
correct answers.
The price of financial options
• Probability theory yields a modelisation of
random processes. The prices of stocks
traded on stock exchanges fluctuate like the
Brownian motion.
• Optimal stochastic control involves ideas
which previously occurred in physics and
geometry (deformation of surfaces).
How to control a complex world
• Managing distribution in an electricity network,
studying the vibrations of a bridge, the flow of air
around an airplane require tools from the
mathematical theory of control (differential
equations, partial derivatives equations) .
• The optimization of trajectories of satellites rely
on optimal control, numerical analysis, scientific
calculus,…
Optimization
•
•
•
•
•
Industry manufacturing, costs
reducing, decreasing production
time, …
Production of fabrics, shoes :
minimizing waste, …
Petroleum Industry : how to
find the proper hydrocarbon
mixtures, …
Aero dynamism (planes,
cars,…).
Aerospace industry : optimal
trajectory of an interplanetary
spaceflight, …
Mathematics involved in
optimization
• Algebra (linear and
bilinear algebra,…)
• Analysis (differential
calculus, numerical
analysis, …)
• Probability theory.
Optimal path
How to go from O to F
a
O
A
c
b C
x
d
y
D
z
t
E
a=f(x1,…,xn)
B
F
Trees and graphs
A company wants to find the best
way (less expensive, fastest)
for trucks which receive goods
and deliver them at many
different places.
Applications of graph theory
• Electric circuits
• How to rationalize the production
methods, to improve the
organization of a company.
• How to manage the car traffic or the
metro network.
• Informatics and algorithmic
• Buildings and public works
• Internet, cell phones
http://smf.emath.fr/Publicati
on/
ExplosionDesMathematique
s/ Presentation.html