Transcript 09-05_Travis_Hoppe_slides

Irrelevant Topics
in Physics Part III
What is Irrelevant?
• Questions the tools we use in physics so
indiscriminately
• Relax assumptions
• Enjoy physics outside the
confines of our ‘research’.
Today's Topics
• Cardinality of Infinity
– Cantor’s crazy continuum counting
• Negative Probabilities
– An homage to lateral thinking
• A Solution to Graph Isomorphism
– What train-hopping hobos can teach us
Absolute beginnings
• Reconsider the absolute value |x|
– For physicists
| L |2
-> distance
| A | x  x  x
2
1
2
2
3
3
– More than one type of norm
L1,L2,L3,L_infinty ...
– For Set Theorists -> counting, known as the
cardinality of the set

Absolute Examples
• Simple for finite sets
|{1, 7,8,10} | 4
|{}| 0
|{' dog ', ' cat ', fish '}| 3
|{1, 7,8,10} ||{' dog ', ' cat ', fish '} |

Absolute Infinity
• What about infinite sets?
|{ } ||{natural numbers} | ?
• Only comparisons can be made now
• Sets are equal, iff they can be put in a oneto-one correspondence with each other

Absolute Natural
• Even numbers have the same cardinality
as the natural numbers
2 1
|{
2
} ||{ } | 0
42
63
84
• Holds for all infinite partitions of the
natural numbers (odds, divisible by 13,
primes, etc...)

Absolute Rational
• Rational numbers also have the same
cardinality as the natural numbers!
| { } ||{ } |
Omit the repeats to get
the sequence

These sets are known as countable
Absolute (un)Real
• Do all infinite sets have the same cardinality? NO!
There are more reals then rationals!
0
|{ } ||{ } | 2
 1
?
• Any subset of the real numbers ie. [0,1] can be put
in correspondence with any other subset, or even
the entire line.
• The [=?] above is known as the continuum
hypothesis, which can neither be proved or
disproved when assuming the axiom of choice

Absolute (un)Real
• Proof by contradiction, assume a mapping
exists, for example take:
1  .47382474...
2  .12030249...
3  .24985283...
4  .85472378...
Each real on the right is infinite, and the
length of this list is also infinite.
Take a diagonal of the list:
.4297.....
Add one to each of the numbers (mod 10)
.5308....
This new number is NOT on the list above, as it differs from the first digit
for the first number, second digit for the second number, etc...

Absolute Crazy
• The cardinality of the square is equal to a line
segment.
2
|{
} ||{ } |
• Higher order cardinalities exists by taking
multisets, ie. The set of all sets:
multiset ({1, 2,3})  {{},{1},{2},{3},{1, 2},
{1, 3},{2,3},{1, 2,3}}

Absolute Irrelevant
• Does this have an impact on physics?
– Sets of higher order then the real numbers have
never found use in physics.
– However, the language of quantum mechanics uses
discrete (quanta of energy, spin, ...) and continuous
variables (position, momenta, ...).

Negative Probabilities
• Relax the assumption that each
probability must be positive, however still
enforce that the sum of all events must be
unity.
• Consider a concrete example of a roulette
wheel with two conditions:
Feynman’s Roulette
A (.7)
B (.3)
1
0.3
-0.4
2
0.6
1.2
3
0.1
0.2
• The table is known to have two states,
A,B and separate probabilities for each of
the numbers coming up.
Feynman’s Roulette
A (.7)
B (.3)
1
0.3
-0.4
2
0.6
1.2
3
0.1
0.2
p1  (0.7)(0.3)  (0.3)(0.4)  0.09
p2  (0.7)(0.6)  (0.3)(1.2)  0.78
p3  (0.7)(0.1)  (0.3)(0.2)  0.13
Negative Probabilities
• Possible that the direct states of the
system are not observable, that is:
P( p1 | pB ) 
P( p1
pB )
P ( pB )
(0.3)(0.4)

 0.4
0.3
Negative Probabilities
• Why not rearrange the calculation or
theory so probabilities are positive in all
intermediate states?
– The accountant who subtracts all payments
before adding in the profits (intermediate
sum can be negative).
– Nothing mathematically wrong with working
with negative probabilities.
Hobos on a Train
• From Wikipedia:
• Hobo is a term that refers to
a subculture of wandering
homeless people, particularly
those who make a habit of
hopping freight trains
Hobosumptions
• Assume that occasionally, when a hobo
wakes up, he is unsure of his current
location.
• As a survival instinct, he has memorized
all the train schedules for each country.
• Wine has degraded his memory, and he
only remembers the connections.
Hobomaps
• It is crucial when picking up a
train schedule, no matter what
country, to determine the lay of the land.
Notes from the Ivory Towers
• A mathematician would call the hobo-map an
undirected, unlabeled simple graph, where the
process for determining two graphs are the
‘same’ is known as graph isomorphism.
• Computationally, graph isomorphism is
curious, it belongs to NP but it is not known to
have a polynomial solution (P) nor is it NPcomplete.
Invariants
• An invariant is a graph property that
can (possibly) show two graphs
different.
• Examples: number of nodes, degree
sequence, number of edges, etc...
• Graphs with different invariants are not
isomorphic; the converse is NOT true in
general
Hoppe’s Invariant
• I propose an invariant which I think is
also unique, that is, no two nonisomorphic graphs share the same
invariant (working on this part).
• Moreover, the invariant is computable
in polynomial time.
Adjacency Matrix
A {0,1} symmetric matrix with 1 if nodes
i,j are joined by an edge
Generating functions
This matrix has nice properties. Raised to
a power n the element i,j tells you the
number of trips starting at i and ending
at j of length n.
n
[ A ]ij
A generating function can be found that
gives all the terms:
fij ( z ) 
det([ I  zA]ij )
det( I  zA)
Big-Oh! Notation
det([ I  zA]ij )
This step is assumed to
be a polynomial time fij ( z ) 
det( I  zA)
operation. Finding the
det. of matrix can be doing using LU
decomposition O(x^3) by dividing and
multiplying rows. When the matrix elements
themselves are polynomials, the number of
operations is surely increased, but (seems to
be) bounded by polynomial time.
Symmetric Nodes
Once each polynomial is found, it encodes
all the powers of A into it by taking
higher terms of z. If two nodes share the
property:
fii ( z )  f jj ( z )
We will call them symmetric.
The unordered set is a graph
invariant:
{ fii ( z ), i  1..n}
ex. Symmetric Nodes
1 4 z  z  3 z  2 z
2
3
4
6
1 z  7 z  3 z  8 z  z
2
3
f ii ( z )
 (1  3 z 2  3 z 3  18 z 4  30 z 5  O  z 6 )
4
Hobomorphism
The question then is: { fii ( z ), i  1..n}
Does this set uniquely define a graph? Ie.
Can one produce a graph simply by
knowing how many walks of length n
lead back home for all n and for all
nodes?
If so, the graph isomorphism problem has
a polynomial time solution.
Hobos and YOU
Why graph isomorphism?
Computationally an unsolved problem
Chemical structure evaluation
Symmetric groups for coupled JosephsonJunction systems (cf. Sam Kennerly)
Discrete mathematics: generalized knights
tours, Rubik’s Cube solutions, etc...
Solid state lattice structures
Ability to successfully navigate train schedules