This Week's Finds in Mathematical Physics (Week 172)
John Baez
October 29, 2001
This Week's Finds in Mathematical Physics (Week 172)
John Baez
I recently went to a conference on "Discrete Random Geometries and
Quantum Gravity", organized by Renate Loll:
1) Discrete Random Geometries and Quantum Gravity,
http://www1.phys.uu.nl/Symposion/EUWorkshop.htm
She was one of the people who first gave me the courage to work on
quantum gravity. I'd been interested in it for a long time, but I
didn't like the string theory relied on supersymmetry and a background
metric, so I didn't know any approach that looked promising until I saw
her give a talk on loop quantum gravity at a conference in Seattle in
the early 1990s. She was interested in numerical simulation of quantum
gravity models even back then, and by now she's one of the top experts
on this subject. But it's extremely hard to get permanent positions in
quantum gravity, especially in Europe, so I was happy when she recently
got a job at the University of Utrecht. To kick off her stay there, she
threw this conference!
I like to read "Wired" magazine when I'm on long airplane trips. On my
flight to Amsterdam, I found this interesting article:
2) Wil McCarthy, Ultimate alchemy, Wired, October 2001, 150.
It's about people are using "quantum dots" to make "artificial atoms".
A quantum dot is a tiny speck of conductive material that can be used as
a potential well holding one or more electrons in a bound state. Such
bound states are a lot like atoms! However, the ones people have made
so far are about 50 times bigger than actual atoms, because they are
more loosely bound. This also means that they ionize more easily, so
they need to be kept very cold.
However, they can have more electrons than normal atoms, since they
aren't limited by the tendency of large nuclei to undergo radioactive
decay, or ultimately, somewhere around element 137, the tendency of
strong electric fields to "spark the vacuum" by creation of
particle-antiparticle pairs - a quantum field theory effect that's not
included in the bare-bones Schroedinger equation. So, someday we may
learn how the periodic table goes up to, say, element 500! I've
sometimes imagined decadent future chemists studying such elements on
the computer, just for the fun of it... but now perhaps they'll do it
with "artificial atoms".
Now, McCarthy is a science fiction writer, so he imagines more dramatic
applications of quantum dots, like "programmable matter" - a gadget
whose surface can, say, turn from lead to gold at the flick of a switch.
Personally I don't see how to get these tricks to work at room
temperature until we make artificial atoms almost as small as real ones,
which I don't see how to do without them being... atoms! But even
so, I believe there will be some cool technological applications of quantum
dots.
For more on quantum dots by experts on the subject, try these papers:
3) Marc Kastner, Artificial atoms, Physics Today 46 (1993), 24. Also
available at http://web.mit.edu/physics/people/marc_kastner.htm
4) Leo Kouwenhoven and Charles Marcus, Quantum dots, Physics World, June
1998. Also available at http://marcuslab.harvard.edu/
Unfortunately I didn't have access to these papers on my flight from Los
Angeles to Amsterdam. It takes 10 hours, so I had to read a lot more to
keep from going insane with boredom. Even the latest news about bioterrorism
and bombings was not enough to keep me entertained. (By the way, I predict
that a highly contagious virus will sweep the United States and kill
about 20,000 people within the next few months. It's called "influenza",
and that's the average number of Americans who die from it each year.
I plan to call the FBI and warn them about this.)
So, I had to hit the serious mathematical physics:
5) Terry Gannon, Monstrous moonshine and the classification of CFT,
in Conformal Field Theory: New Non-Perturbative Methods in String and
Field Theory, Yavuz Nutku, Cihan Saclioglu and Teoman Turgut, eds.,
Perseus Publishing, 2000.
This is a very pleasant 66-page review article on "monstrous moonshine",
which is what people call the relation between the Monster group and
modular forms. Someday I'll have to say a lot more about this; for now
see "week66" if you have no idea what I'm talking about. Gannon's
article is full of juicy mathematical tidbits and pieces of wisdom. He
even gives a new explanation of why the number 24 is so important
throughout mathematics and string theory. If x^2 = 1 mod n, then x does
not divide n... and 24 is the largest integer for which the converse
holds! Alas, Gannon does not explain how this relates to the other
magic properties of this number, some of which are listed in "week124".
Does anyone see the connection?
At the conference, one of my favorite talks was by Sergeui Dorogovtsev,
on "Geometry of Evolving Random Networks". A directed graph is a bunch
of nodes connected by edges with little arrows on them. A nice
example is the world-wide web, where the nodes are webpages and the
edges are links. Various people have noticed that in naturally evolving
directed graphs, the number of edges to or from a given node is
distributed roughly according to a power law. For example, on the
World-Wide Web, the number of sites having n links *to* them is roughly
proportional to
n^{-2.1}
while the number of sites having n links coming from them is roughly
proportional to
n^{-2.7}
This differs from the simple models of random graphs most studied by
mathematicians, for which these quantities often follow a Poisson
distribution. But recently people have been coming up with new models
of evolving graphs that have this power-law behavior. The trick is to
take into account the fact that "popularity is attractive". The
simplest model uses undirected graphs: keep adding new nodes one at a
time, and let the probability that your new node has an edge to any
existing node be proportional to the number of edges already attached to
the existing node. Following this rule, you'll build up a big random
graph with the power law behavior
n^{-3}
For more details see this fascinating paper:
6) Sergeui N. Dorogovtsev and J.F.F. Mendes, Evolving networks,
available at cond-mat/0106144.
I really love the chart on page 11! It shows the general structure of a
typical naturally arising large directed graph such as the World-Wide Web.
The picture is worth a thousand words, but let me try to explain it:
First, a large fraction of the nodes lie in the "giant strongly
connected component", or GSCC. This is the biggest set of nodes where
you can get between any two by following a sequence of edges and going
forwards along the arrows. For example, in 1999, the entire Web had 203
million webpages, and of these, 56 million were in the GSCC.
Even bigger than the GSCC is the "giant weakly connected component", or
GWCC. This is the set of all nodes from which you can get to the GSCC
by following a sequences of edges either forwards or backwards.
In 1999, 186 million webpages were in the GWCC. That's 91% of all
webpages!
We can also define the "giant in-component" or GIN to be the set of all
nodes from which you can get *into* the GSCC by following edges forward.
Similarly, the "giant out-component" or GOUT is the set of nodes that
you can get to by going *out of* the GSCC, following edges forward. In
1999, both the GIN and the GOUT of the Web contained about 99 million
webpages.
Besides these structures, there are also "tendrils" leading out of the
GIN and into the GOUT. More precisely, "tendrils" consist of nodes in
the GWCC but in neither the GIN nor the GOUT. In 1999, 44 million
webpages lay in these tendrils.
Finally, there are a bunch of smaller components not reachable from the
GWCC by edges pointing either forwards or backwards; in 1999 these
accounted for 17 million webpages.
Of course, the main reason I'm interested in randomly evolving graphs is
not because I surf the Web, but because I work on spin foam models of
quantum gravity. Here the nodes and edges are labelled by spins, and
instead of a probabilistic evolution rule one has a quantum-mechanical
rule. So things are pretty different, though there are tantalizing
similarities.
I gave a review of spin foam models and an introduction to the following
new papers:
7) John Baez and J. Daniel Christensen, Positivity of spin foam
amplitudes, available at gr-qc/0110044.
8) J. Daniel Christensen and Greg Egan, An efficient algorithm for the
Riemannian 10j symbols, available at gr-qc/0110045.
But in this conference there were *lots* of talks about different models
of quantum gravity involving discrete random geometries... so right now
I'll just discuss a model of this sort called the IKKT matrix model.
This was proposed in the following paper:
9) N. Ishibashi, H. Kawai, Y. Kitazawa and T. Tsuchiya, A large-N
reduced model as superstring, Nucl. Phys. B498 (1997) 467-491.
Also available as hep-th/9612115.
The idea is to provide something like a background-free formulation of
type IIB string theory. But I don't understand how that's supposed to
work yet, so my own attaction to this theory mainly comes from the fact
that it's very simple and pretty. Let me describe it to you!
I'll assume you know that the Lagrangian for Yang-Mills theory coupled
to spinors looks like this:
tr(F ^ *F) + psibar D psi
where F is the curvature of some gauge field, psi is a spinor field
transforming under some representation of the gauge group, and D is
covariant Dirac operator. If we write this out a bit more explicitly,
it's
tr((dA + [A,A]) ^ *(dA + [A,A]) + psibar^i (d_a + A_a) Gamma^a_{ij} psi^j
where A is the gauge field. But now, let's pull a trick taken from
noncommutative geometry, and replace functions on spacetime by N x N
matrices! More precisely, let A lie in the space of su(N) matrices
tensored with the Lie algebra of G tensored with R^n, where n is the
dimension of spacetime. Similarly, let psi like in the space of su(N)
matrices tensored with the Lie algebra of G tensored with
spinors... where we use some sort of spinors suitable for n-dimensional
spacetime. Then at least if we squint, the above Lagrangian becomes
tr([A_a,A_b] [A^a,A^b]) + psibar^i [A_a, Gamma^a_{ij} psi^j])
which is the Lagrangian for the IKKT model.
In short, this model is a version of Yang-Mills theory coupled to
fermions where functions on spacetime have been replaced by N x N
matrices. The idea is that as N -> infinity, this sort of theory can
reduce to one where spacetime is a manifold.... but not necessarily
just one particular manifold.
It will be no surprise to readers of "week93" and "week104" that this
model is supersymmetric when the spacetime dimension is 3, 4, 6, or 10.
The reason is that in these dimensions both vectors and spinors have a
nice description in terms of the real numbers, complex numbers,
quaternions or octonions, respectively. The 10-dimensional octonionic
version is the one that string theorists hope is related to the type IIB
superstring. In this case, we can think of both A and psi as big fat
matrices made of octonions!
There were a few different talks about the IKKT matrix model. John
Wheater gave a talk about results saying that the path integral
converges for this model in certain cases. In particular, it converges
for any simple gauge group if n = 4, 6, or 10. For more details try
this:
10) Peter Austing and John F. Wheater, Convergent Yang-Mills matrix
theories, JHEP 0104 (2001) 019. Also available as hep-th/0103159.
Bengt Petersson spoke about computer simulations of the IKKT model:
11) Z. Burda, B. Petersson, J. Tabaczek, Geometry of reduced
supersymmetric 4D Yang-Mills integrals, Nucl. Phys. B602 (2001) 399-409.
Also available as hep-lat/0012001.
Also, Graziano Vernizzi spoke on work still in progress attempting to
see the compactification of spacetime from 10 to 4 dimensions in
superstring theory as a natural consequence of a matrix model.
For more on the IKKT model, try this:
12) A. Konechny and A. Schwarz, Introduction to M(atrix) theory and
noncommutative geometry, available at hep-th/0012145.
There were a lot more talks, but on my way back home I started
reading some papers about Tarski's "high school algebra problem",
so now let me talk about that. This is more like mathematical logic
than mathematical physics... at least at first. If you follow it
through long enough, it turns out to be related to stuff like Feynman
diagrams, but I doubt I'll have the energy to go that far this week.
So:
Once upon a time, the logician Tarski posed the following question. Are
there any identities involving addition, multiplication, exponentiation
and the number 1 that don't follow from the identities we all learned in
high school? In case you forgot, these are:
x + y = y + z (x + y) + z = x + (y + z)
xy = yz (xy)z = x(yz)
1x = x
x^1 = x 1^x = 1
x(y + z) = xy + xz
x^(y + z) = x^y x^z (xy)^z = x^z y^z x^(yz) = x^(y^z)
A bit more precisely, are there equational laws in the language (+,.,^,1)
that hold for the positive natural numbers but do not follow from the
above axioms using first-order logic?
Remarkably, in 1981 it turned out the answer is YES:
13) A. J. Wilkie, On exponentiation - a solution to Tarski's
high school algebra problem, to appear in Quaderni di
Matematica. Also available at http://www.maths.ox.ac.uk/~wilkie/
Here is Wilkie's counterexample:
[(x + 1)^x (x^2 + x + 1)^x]^y [(x^3 + 1)^y (x^4 + x^2 + 1)^y]^x =
[(x + 1)^y (x^2 + x + 1)^y]^x [(x^3 + 1)^x (x^4 + x^2 + 1)^x]^y
You might enjoy showing this holds for all positive natural numbers x
and y. You can do it by induction, for example. You just can't show it
by messing around with the "high school algebra" axioms listed above.
Wilkie's original proof was rather subtle, but in 1985 Gurevic gave a
more simple-minded proof: he constructed a finite set equipped with
addition, multiplication, exponentiation and 1 satisfying the high
school algebra axioms but not Wilkie's identity. This clearly shows
that the former don't imply the latter! His counterexample had 59
elements:
14) R. Gurevic, Equational theory of positive numbers with exponentiation,
Proc. Amer. Math. Soc. 94 (1985), 135-141.
Later, various mathematicians enjoyed cutting down the number of
elements in this counterexample. As far as I can tell, the current
record-holder is Marcel Jackson, who constructed one with only 14
elements. He also showed that none exists with fewer than 8 elements:
15) Marcel G. Jackson, A note on HSI-algebras and counterexamples to
Wilkie's identity, Algebra Universalis 36 (1996), 528-535. Also available at
http://www.latrobe.edu.au/mathstats/Staff/Marcel/details/publications.html
I have no idea what these small counterexamples are good for, though
Jackson proves some nice things in the process of studying them.
More important, in my opinion, is a 1990 result of Gurevic: no finite
set of axioms is sufficient to prove all the identities involving
addition, multiplication, exponentiation and 1 that hold for the
positive natural numbers. You can find this here:
16) R. Gurevic, Equational theory of positive numbers with exponentiation
is not finitely axiomatizable, Ann. Pure. Appl. Logic 49 (1990), 1-30.
In other words, Wilkie's identity is but one of an infinite set of
logically independent axioms of this type!
But the real fun starts when we *categorify* Tarski's high school
algebra problem. This was done by Marcelo Fiore, a computer scientist
whom I met in Cambridge this summer. The idea here is to realize that
the high school identities all hold as *isomorphisms* between finite
sets if we interpret addition as disjoint union, multiplication as
Cartesian product, x^y as the set of functions from the finite set y to
the finite set x, and 1 as your favorite one-element set. The point
here that the set of natural numbers is just a dumbed-down version of
the category of finite sets, with all these arithmetic operations coming
from things we can do with finite sets. I explained this in "week121".
From this viewpoint it's very natural to include some extra axioms
involving 0, which corresponds to the empty set:
0 + x = x
0x = 0
x^0 = 1
Note that this gives 0^0 = 1, which is "correct" in that there's one
function from the empty set to the empty set. The only reason people
often formulate Tarski's problem in terms of *positive* natural numbers
is that they're afraid to say 0^0 = 1, having been scared silly by their
high school math teachers. In analysis 0^0 is a dangerous thing, but
not in the arithmetic of natural numbers. All the aforementioned
results on the high school algebra problem still hold if we include 0
and throw in the above extra axioms - except the results on smallest
possible counterexamples.
The reason why it's so nice to include 0 is that then the high school
identities correspond closely to what holds in any "biCartesian closed
category" - a good example being the category of finite sets. A
Cartesian category is one with binary products and a terminal object;
these act like "multiplication" and "1". In a Cartesian *closed*
category we also require that the operation of taking the product with
any object has a left adjoint; this gives "exponentiation". Finally,
in a biCartesian closed category we also have binary coproducts and an
initial object, which act like "addition" and "0", and we require
that products distribute over coproducts.
There are lots of examples of biCartesian closed categories: for
example, the category of finite sets, or sets, or sets on which some
group acts, or more generally presheaves on any category, or still more
generally, any topos!
Anyway, Fiore has posed and solved the following categorified version
of Tarski's high school algebra problem: are there any natural isomorphisms
in the category of finite sets between expressions built from addition,
multiplication, exponentiation, 0 and 1 that don't hold in a general
biCartesian closed category? I'm posing this a bit vaguely, so I hope
you can guess what I mean. Anyway, the answer is again YES, and a
similar sort of counterexample does this job.
To tackle this problem it's useful to consider the *free* biCartesian
closed category on some set of objects, because this has the fewest
isomorphisms. Now, the real reason I'm interested in this stuff is that
James Dolan and Toby Bartels have been thinking about various similar
categories, like the free Cartesian closed category on one object,
or the free symmetric monoidal closed category on one object, or the
free symmetric monoidal compact category on one object... and the
last-mentioned of these is closely related to the theory of Feynman
diagrams!
But alas, just as I suspected, I don't have the energy to go into this
now. So I'll stop here, hopefully leaving you more tantalized than
baffled.
-----------------------------------------------------------------------
Previous issues of "This Week's Finds" and other expository articles on
mathematics and physics, as well as some of my research papers, can be
obtained at
http://math.ucr.edu/home/baez/
For a table of contents of all the issues of This Week's Finds, try
http://math.ucr.edu/home/baez/twf.html
A simple jumping-off point to the old issues is available at
http://math.ucr.edu/home/baez/twfshort.html
If you just want the latest issue, go to
Dave Rusin
In article <9rkuu6$r2$1...@glue.ucr.edu>, John Baez <ba...@math.ucr.edu> wrote:
>A bit more precisely, are there equational laws in the language (+,.,^,1)
>that hold for the positive natural numbers but do not follow from the
>above axioms using first-order logic?
>
>Remarkably, in 1981 it turned out the answer is YES:
D00d! That is so kewl.
>[(x + 1)^x (x^2 + x + 1)^x]^y [(x^3 + 1)^y (x^4 + x^2 + 1)^y]^x =
>[(x + 1)^y (x^2 + x + 1)^y]^x [(x^3 + 1)^x (x^4 + x^2 + 1)^x]^y
This identity is true but _does_ follow from high-school axioms. You mean
[(x + 1)^x + (x^2 + x + 1)^x]^y [(x^3 + 1)^y + (x^4 + x^2 + 1)^y]^x =
[(x + 1)^y + (x^2 + x + 1)^y]^x [(x^3 + 1)^x + (x^4 + x^2 + 1)^x]^y
dave
John Baez
Dave Rusin <ru...@vesuvius.math.niu.edu> wrote:
>In article <9rkuu6$r2$1...@glue.ucr.edu>, John Baez <ba...@math.ucr.edu> wrote:
>>A bit more precisely, are there equational laws in the language (+,.,^,1)
>>that hold for the positive natural numbers but do not follow from the
>>above axioms using first-order logic?
>>
>>Remarkably, in 1981 it turned out the answer is YES:
>D00d! That is so kewl.
Yeah, ain't it?
>>[(x + 1)^x (x^2 + x + 1)^x]^y [(x^3 + 1)^y (x^4 + x^2 + 1)^y]^x =
>>[(x + 1)^y (x^2 + x + 1)^y]^x [(x^3 + 1)^x (x^4 + x^2 + 1)^x]^y
>This identity is true but _does_ follow from high-school axioms.
Whoops. >;-(
> You mean
> [(x + 1)^x + (x^2 + x + 1)^x]^y [(x^3 + 1)^y + (x^4 + x^2 + 1)^y]^x =
> [(x + 1)^y + (x^2 + x + 1)^y]^x [(x^3 + 1)^x + (x^4 + x^2 + 1)^x]^y
Yes, I did. There were also lots of other mistakes in this issue
of TWF. For example, I stated the commutative law for addition as
x + y = y + z, and the commutative law for multiplication as xy = yz. =;-0
Much more importantly, I screwed up the description of the IKKT matrix
model. I append a version where I have tried to fix these mistakes.
This also includes more stuff about my talk on spin foams - stuff I
have already posted here on s.p.r..
.....................................................................
Also available at http://math.ucr.edu/home/baez/week172.html
October 29, 2001
This Week's Finds in Mathematical Physics (Week 172)
John Baez
I recently went to a conference on "Discrete Random Geometries and
Quantum Gravity", organized by Renate Loll:
1) Discrete Random Geometries and Quantum Gravity,
http://www1.phys.uu.nl/Symposion/EUWorkshop.htm
She was one of the people who first gave me the courage to work on
quantum gravity. I'd been interested in it for a long time, but I
didn't like how string theory relied on supersymmetry and a background
n^{-2.1}
n^{-2.7}
n^{-3}
GSCC by edges pointing either forwards or backwards; in 1999 these
accounted for 17 million webpages.
Of course, the main reason I'm interested in randomly evolving graphs is
not because I surf the Web, but because I work on spin foam models of
quantum gravity. Here the nodes and edges are labelled by spins, and
instead of a probabilistic evolution rule one has a quantum-mechanical
rule. So things are pretty different, though there are tantalizing
similarities.
I gave a review of spin foam models and an introduction to the following
new papers:
7) John Baez and J. Daniel Christensen, Positivity of spin foam
amplitudes, available at gr-qc/0110044.
8) J. Daniel Christensen and Greg Egan, An efficient algorithm for the
Riemannian 10j symbols, available at gr-qc/0110045.
The Riemannian 10j symbols are a function of ten spins that serves as
the amplitude for a spin foam vertex in the Barrett-Crane model of
Riemannian quantum gravity - by which I mean the theory where we do a
real-time path integral over Riemannian metrics. This is different from
so-called "Euclidean quantum gravity", where we do an imaginary-time path
integral over Riemannian metrics. As far as I can tell, Riemannian quantum
gravity is only important insofar as it's a useful warmup for Lorentzian
quantum gravity.
In their paper, Christensen and Egan describe an algorithm that computes
the Riemannian 10j symbols using O(j^5) operations and O(j^2) space, as
well as an algorithm that uses O(j^6) operations and a constant amount
of space. This is in contrast to the most obvious methods, which use
O(j^9) operations and O(j^2) or more space. Perhaps most importantly
to the practical-minded among us, their paper includes a link to some
code in C that implements this algorithm.
In our paper, Christensen and I show that the Riemannian 10j symbols
are real, and that when they are nonzero, they are positive (resp.
negative) when the sum of the ten spins is an integer (resp. half-integer).
The proof is a nice exercise in spin network theory. We also show that
for a closed spin foam of the type appearing in the Barrett-Crane model,
the minus signs cancel when we take the product of Riemannian 10j symbols
over all the spin foam vertices. It follows that in both the original
Riemannian Barrett-Crane model, and also the modified version due to
Perez and Rovelli, the amplitudes of spin foams are *nonnegative*.
This is interesting because, as Lee Smolin has often emphasized,
it's hard to simulate spin foams on the computer unless the amplitudes
are nonnegative. Nonnegative amplitudes allows us to use ideas from
statistical mechanics, like the Metropolis algorithm. This is one reason
lattice gauge theory people prefer imaginary-time path integrals to
real-time ones. Of course, in lattice gauge theory, we can do Wick
rotation to get real physics from imaginary-time path integrals. In
quantum gravity, Wick rotation is more problematic, though Renate and
others have considered situations where it's justified. It thus comes
as a pleasant surprise to find that sometimes spin foam amplitudes are
nonnegative *without* doing Wick rotation.
Of course, so far I've only been talking about the Riemannian
Barrett-Crane model! Here the gauge group is Spin(4) = SU(2) x SU(2),
and if you examine our proof, you'll see that the positivity result
comes from the way this group "factors" into two copies of SU(2). We
can't prove positivity of spin foam amplitudes in the more physical
Lorentzian case, where the group is Spin(3,1) = SL(2,C).
However, even though we can't prove it, it may be true! Dan has
written a number of programs which compute the Lorentzian 10j symbols,
and while they are very slow and we haven't computed many values, all
the values we've computed so far seem to be positive. We include
the results we have so far in our paper.
In a paper that will come out later, "Partition function of the
Riemannian Barrett-Crane model", by Dan Christensen, Tom Halford, David
Tsang and myself, we'll discuss the qualitative behavior of various
versions of the Riemannian Barrett-Crane model. In order to write
this paper, we needed to numerically simulate the Barrett-Crane model
using the Metropolis algorithm and the efficient algorithm for Riemannian
10j symbols.
Actually, in this conference there were *lots* of talks about different
models of quantum gravity involving discrete random geometries. But
right now I'll just discuss something called the IKKT matrix model.
This was proposed in the following paper:
9) N. Ishibashi, H. Kawai, Y. Kitazawa and T. Tsuchiya, A large-N
reduced model as superstring, Nucl. Phys. B498 (1997) 467-491.
Also available as hep-th/9612115.
The idea is to provide something like a background-free formulation of
type IIB string theory. But I don't understand how that's supposed to
work yet, so my own attaction to this theory mainly comes from the fact
that it's very simple and pretty. Let me describe it to you!
I'll assume you know that the Lagrangian for SU(N) Yang-Mills theory
coupled to spinors looks like this:
tr(F ^ *F) + psibar D psi
where F is the curvature of the gauge field, psi is a spinor field
transforming under some representation of SU(N), and D is the covariant
Dirac operator. If we write this out a bit more explicitly, it's
tr((dA + [A,A]) ^ *(dA + [A,A]) + psibar^i (d_a + A_a) Gamma^a_{ij} psi^j
where A is the gauge field. But now let's assume A and psi are
constant as functions on space, and that psi transforms in the adjoint
representation of su(N)! This amounts to saying that A lies in
su(N) tensor R^n, where n is the dimension of spacetime, and that psi
lies in su(N) tensored with the space of spinors... where we use some
sort of spinors suitable for n-dimensional spacetime. Then the above
Lagrangian becomes
tr([A_a,A_b] [A^a,A^b]) + psibar^i [A_a, Gamma^a_{ij} psi^j])
which is the Lagrangian for the IKKT model.
Now the idea is that as N -> infinity, this sort of theory can
reduce to string theory on some n-dimensional spacetime manifold...
but not necessarily any fixed manifold.
It will be no surprise to readers of "week93" and "week104" that this
model is supersymmetric when the spacetime dimension is 3, 4, 6, or 10.
The reason is that in these dimensions both vectors and spinors have a
nice description in terms of the real numbers, complex numbers, quaternions
or octonions, respectively. The 10-dimensional octonionic version is the
one that string theorists hope is related to the type IIB superstring.
In this case, we can think of both A and psi as big fat matrices of
octonions!
There were a few different talks about the IKKT matrix model. John
Wheater gave a talk about results saying that the path integral
converges for this model in certain cases. In particular, it converges
if n = 4, 6, or 10. For more details try this:
10) Peter Austing and John F. Wheater, Convergent Yang-Mills matrix
theories, JHEP 0104 (2001) 019. Also available as hep-th/0103159.
Bengt Petersson spoke about computer simulations of the IKKT model:
11) Z. Burda, B. Petersson, J. Tabaczek, Geometry of reduced
supersymmetric 4D Yang-Mills integrals, Nucl. Phys. B602 (2001) 399-409.
Also available as hep-lat/0012001.
Also, Graziano Vernizzi spoke on work still in progress attempting to
see the compactification of spacetime from 10 to 4 dimensions in
superstring theory as a natural consequence of a matrix model.
For more on the IKKT model, try this:
12) A. Konechny and A. Schwarz, Introduction to M(atrix) theory and
noncommutative geometry, available at hep-th/0012145.
There were a lot more talks, but on my way back home I started
reading some papers about Tarski's "high school algebra problem",
so now let me talk about that. This is more like mathematical logic
than mathematical physics... at least at first. If you follow it
through long enough, it turns out to be related to stuff like Feynman
diagrams, but I doubt I'll have the energy to go that far this week.
So:
Once upon a time, the logician Tarski posed the following question. Are
there any identities involving addition, multiplication, exponentiation
and the number 1 that don't follow from the identities we all learned in
high school? In case you forgot, these are:
x + y = y + x (x + y) + z = x + (y + z)
xy = yx (xy)z = x(yz)
1x = x
x^1 = x 1^x = 1
x(y + z) = xy + xz
x^(y + z) = x^y x^z (xy)^z = x^z y^z x^(yz) = x^(y^z)
A bit more precisely, are there equational laws in the language (+,.,^,1)
that hold for the positive natural numbers but do not follow from the
above axioms using first-order logic?
Remarkably, in 1981 it turned out the answer is YES:
13) A. J. Wilkie, On exponentiation - a solution to Tarski's
high school algebra problem, to appear in Quaderni di
Matematica. Also available at http://www.maths.ox.ac.uk/~wilkie/
Here is Wilkie's counterexample:
[(x + 1)^x + (x^2 + x + 1)^x]^y [(x^3 + 1)^y + (x^4 + x^2 + 1)^y]^x =
[(x + 1)^y + (x^2 + x + 1)^y]^x [(x^3 + 1)^x + (x^4 + x^2 + 1)^x]^y
You might enjoy showing this holds for all positive natural numbers x
and y. You can do it by induction, for example. You just can't show it
by messing around with the "high school algebra" axioms listed above.
Wilkie's original proof was rather subtle, but in 1985 Gurevic gave a
more simple-minded proof: he constructed a finite set equipped with
addition, multiplication, exponentiation and 1 satisfying the high
school algebra axioms but not Wilkie's identity. This clearly shows
that the former don't imply the latter! His counterexample had 59
elements:
14) R. Gurevic, Equational theory of positive numbers with exponentiation,
Proc. Amer. Math. Soc. 94 (1985), 135-141.
Later, various mathematicians enjoyed cutting down the number of
elements in this counterexample. As far as I can tell, the current
record-holder is Marcel Jackson, who constructed one with only 14
elements. He also showed that none exists with fewer than 8 elements:
15) Marcel G. Jackson, A note on HSI-algebras and counterexamples to
Wilkie's identity, Algebra Universalis 36 (1996), 528-535. Also available at
http://www.latrobe.edu.au/mathstats/Staff/Marcel/details/publications.html
I have no idea what these small counterexamples are good for, though
Jackson proves some nice things in the process of studying them.
More important, in my opinion, is a 1990 result of Gurevic: no finite
set of axioms in first-order logic is sufficient to prove all the
identities involving addition, multiplication, exponentiation and 1
that hold for the positive natural numbers. You can find this here:
Michael Barr
> Also available at http://math.ucr.edu/home/baez/week172.html
>
> October 29, 2001
> This Week's Finds in Mathematical Physics (Week 172)
> John Baez
Just a couple of misstatements. Sorry John, but at least you know
someone is reading it.
> If x^2 = 1 mod n, then x does
> not divide n... and 24 is the largest integer for which the converse
> holds!
You gotta mean that if x is relatively prime to n, then x^2 = 1 mod n,
since, for example, 9 does not divide 24, but 9^2 = 9 mod 24. The
explanation is that 3 and 8 (along with 2 and 4) have that property
and they are the only prime powers that do.
>
> The reason why it's so nice to include 0 is that then the high school
> identities correspond closely to what holds in any "biCartesian closed
> category" - a good example being the category of finite sets. A
> Cartesian category is one with binary products and a terminal object;
> these act like "multiplication" and "1". In a Cartesian *closed*
> category we also require that the operation of taking the product with
> any object has a left adjoint;
That should read RIGHT adjoint. I really don't like the term
"bicartesian closed category", since there is no way of parsing it
that gives the right definition. If you pair the "bi" with
"cartesian" then it is a category with finite products and sums and
some closed structure and if you pair the "bi" with "cartesian
closed", then both the category and its opposite should be cartesian
closed and that is not true (probably not possible except unless it is
a lattice and both Heting and coHeyting). But I guess I have lost
that argument.
Michael Barr
John Jones
Thanks - I was confused by that. It prompted me to read Wilkie's paper.
And as he says in his paper, it is easy enough to see it is true for
positive numbers with all common arithmetic operations [due to
Wilkies...- "note x^3 + 1=(x^2 - x + 1)*(x+1) and
x^4 + x^2 + 1 =(x^2 - x + 1)*(x^2 + x + 1) and cancel the terms (x^2 -
x + 1)^(x*y)"...].
That this cannot be used as a proof under Tarski's scheme is because
[paraphrasing like mad] (x^2 - x + 1) is not a legal construct, having
"-" in it.
Rainer Rosenthal
John Baez <ba...@math.ucr.edu>
> Here is Wilkie's counterexample:
>
> [(x + 1)^x (x^2 + x + 1)^x]^y [(x^3 + 1)^y (x^4 + x^2 + 1)^y]^x =
> [(x + 1)^y (x^2 + x + 1)^y]^x [(x^3 + 1)^x (x^4 + x^2 + 1)^x]^y
>
Correction necessary: Four plus-signs are to be inserted.
[A^x + B^x]^y [C^y + D^y]^x =
[A^y + B^y]^x [C^x + D^x]^y
Hello John,
thank you very very much for your effort, to bring all these
highlights to the interested reader.
The correction is according to the reference, given by you:
http://www.latrobe.edu.au/mathstats/Staff/Marcel/details/HSI.pdf
Those logicians do funny work !
As far as I have understood the problem, there are models which
satisfy the HSI (High School Identities) but NOT the Wilkie identity.
As soon as you have a zero-element with proper properties *g*
you are unable to find such brain shockers.
Thanks again and many regards
Rainer Rosenthal
r.ros...@web.de
grelbr
[megasnips]
>x^(yz) = x^(y^z)
[snips]
The other two typos (that I pointed out and you corrected, but
the post I sent has neither been bounced nor appeared, must be
slow net traffic, right? sigh...) were fixed. But this one is
still right here.
Did you mean x^(yz) = (x^y)^z ?
2^(15) does not equal 2^(243).
grelbr
Toby Bartels
>I really don't like the term
>"bicartesian closed category", since there is no way of parsing it
>that gives the right definition. If you pair the "bi" with
>"cartesian" then it is a category with finite products and sums and
>some closed structure and if you pair the "bi" with "cartesian
>closed", then both the category and its opposite should be cartesian
>closed and that is not true (probably not possible except unless it is
>a lattice and both Heting and coHeyting). But I guess I have lost
>that argument.
I don't know about that; I agree with you,
and John's supposedly only writing about this
because I (and jim) have been thinking about it.
I suggest the term "Tarski high school category".
(After all, with the new math,
we all learned about the category FinSet in high school.)
-- Toby
to...@math.ucr.edu
Toby Bartels
>[A^x + B^x]^y [C^y + D^y]^x = [A^y + B^y]^x [C^x + D^x]^y
This is really a good way to think about it;
the exact way of defining A, B, C, and D is not so important.
The identity will hold (in \N) if AD = BC,
otherwise regardless of how A, B, C, and D are defined.
The expressions used by Willkie are simply the simplest
that will ensure that let AD equal BC (so that the formula holds in \N)
and yet let the formula be unprovable from the Tarski axioms.
In a Tarski high school algebra,
let u be an _exponential_unit_ if it behaves like 1 in the sense that
(x + y)^u = x^u + y^u for any x, y in the algebra.
(1 is an exponential unit in any HSA,
and it's the only exponential unit in \N,
but other HSAs have multiple exponential units.)
Then you get this general theorem:
If a, b, c, d, x, and y are in the HSA,
ad = bc, and y is a finite sum of exponential units,
then (a^x + b^x)^y (c^y + d^y)^x = (a^y + b^y)^x (c^x + d^x)^y.
The proof is by induction on the number of terms in the expression for y.
In \N, of course, *every* number is a finite sum of 1.
So here is a question:
Are there any identities that hold in \N
but are not provable from the Tarski axioms
plus the axiom that every number is a finite sum of exponential units?
I don't know the answer to this question.
-- Toby
to...@math.ucr.edu
Rainer Rosenthal
Toby Bartels <to...@math.ucr.edu> wrote
> In \N, of course, *every* number is a finite sum of 1.
> So here is a question:
> Are there any identities that hold in \N
> but are not provable from the Tarski axioms
> plus the axiom that every number is a finite sum of exponential units?
> I don't know the answer to this question.
Hello Toby,
many thanks for your detailed reply. Since all
this is not in the center of my interests but
nontheless terribly interesting (!), I just copy
these fine ideas into folders for "later use" which
may or may be not "never".
At first I was terribly perplexed by the result, since
I misunderstood it in the way you mentioned in the
end of your post: That there are identities in the
well known (*g*) |N, which cannot be deduced from
the axioms.
It's a little bit of cheating or providing problematic
problems, if one uses a system of identities including
the addition, without introducing the most interesting
element, the neutral element of addition, zero.
But for sure it's a wonderful puzzle - really.
With friendly regards,
Rainer Rosenthal
John Baez
Rainer Rosenthal <r.ros...@web.de> wrote:
>Toby Bartels <to...@math.ucr.edu> wrote
>> In \N, of course, *every* number is a finite sum of 1.
>> So here is a question:
>> Are there any identities that hold in \N
>> but are not provable from the Tarski axioms
>> plus the axiom that every number is a finite sum of exponential units?
>> I don't know the answer to this question.
Nor I, alas. Once upon a time I saw a paper on the web which
gave an infinite set of axioms that allow you to prove all the
identities involving (+,.,^,0,1) which hold in \N (the natural numbers).
However, I can't find this paper anymore, so I can't use it to
answer your question.
>It's a little bit of cheating or providing problematic
>problems, if one uses a system of identities including
>the addition, without introducing the most interesting
>element, the neutral element of addition, zero.
I don't understand what you're saying here.
First of all, the number zero is an element of \N, and
Toby is correct in saying that this element, like all the
rest, is a finite sum of copies of 1.
(How many copies? Zero! Zero is a finite number,
so Toby is right.)
Secondly, as far as I know, Wilkie's solution to the
Tarski high school algebra problem still works if we
include the axioms involving zero. In other words,
if we assume the identities
x + y = y + x (x + y) + z = x + (y + z)
xy = yx (xy)z = x(yz)
1x = x
x^1 = x 1^x = 1
x(y + z) = xy + xz
x^(y + z) = x^y x^z (xy)^z = x^z y^z x^(yz) = (x^y)^z
and also
0 + x = x
0x = 0
x^0 = 1
then we are unable to prove this identity which holds in \N:
[(x + 1)^x + (x^2 + x + 1)^x]^y [(x^3 + 1)^y + (x^4 + x^2 + 1)^y]^x =
[(x + 1)^y + (x^2 + x + 1)^y]^x [(x^3 + 1)^x + (x^4 + x^2 + 1)^x]^y
So: the point is not that we are leaving out zero. The point
is that we are leaving out subtraction - if we could use that, we
could prove this identity. But leaving out subtraction is very natural
if we're talking about \N.
Followups set to sci.math, since this ain't really physics.
Toby Bartels
Rainer Rosenthal wrote in part:
>It's a little bit of cheating or providing problematic
>problems, if one uses a system of identities including
>the addition, without introducing the most interesting
>element, the neutral element of addition, zero.
Zero has nothing to do with it.
If A is a Tarski HSA under the axioms lacking zero,
then an element 0 can just be appended to it,
with 0 + x = x + 0 = x, 0x = x0 = 0, x^0 = 1, and 0^x = 0 if x != 0.
This won't affect whether or not the Wilkie identity holds.
-- Toby
to...@math.ucr.edu