Two Berkeley grad students, Pablo Solis and Andrew Critch, just organised a “20 questions seminar”. The premise is pretty simple — everyone gets 2 minutes to ask a question they’d like an answer to, and we spend any remaining time (and tea afterwards) talking about them.
I wasn’t sure beforehand whether or not it was going to work out, but ended up pretty pleased I came. We didn’t quite make it to 20 questions (13 that I counted); they appear below. There’s also apparently going to be a wiki page for the seminar. The questions range from easy to weird to awesome. I left out one or two for various reasons, and my apologies for the lame TeX. Decide for yourself which you like, and feel free to give answers — if there’s good discussion here I’ll advertise that at next week’s “20 questions”.
1 Scott:
in R^2, you can tile the plane with hexagons. However any closed trivalent graph has a face that’s smaller than a hexagon. You can tile R^3 with vertex-truncated octahedrons. Say we have a “generic” closed finite cell-complex (every edge has 3 incident faces, every vertex has 4 incident edges). Is there something “smaller” than a vertex-truncated octahedron (or the other polytopes that give generic tilings)?
2 Critch:
Is there a space with trivial homology, non trivial homotopy?
(Anton: isn’t there a result that say that first nontrivial homology and homotopy agree?)
4 Yael:
Out(G) = Aut(G)/Inn(G). Is there a nice description of cosets, beyond that they’re cosets?
5 Mike:
X a banach space, f:X->R convex.
If X is infinite dimenionsal, what extra conditions guarantee that f is continuous?
6 Darsh:
Take a triangle in R^2 with coordinates at rational points. Can we find the smallest denominator point in the interior? (Take the lcm of the denominators of the coordinates.)
(Hint: you can do the 1-d version using continued fractions.)
7 Jakob
Take a “sparse” (every vertex has reasonably small degree) graph. Consider a maximal independent set for the graph (a maximal set of disconnected vertices). Can we make a new graph, with vertices the set, and whatever edges we like, that is as topologically similar to the original graph as possible?
8 Andrew:
What’s the deal with algebraic geometry? Just kidding!
Consider the sequence x0=0, x1=1, x_{n+2} = a x_{n+1} + b x_n, generalizing the Fibonacci sequence. Fix p a prime. If k is minimal so p|x_k and p|x_l implies k|l, then v_p(x_nk) = v_p(x_k) + v_p(n). (Here v_p(z) is the power of p dividing z.) Is there some framework that makes this sort of result obvious? Andrew only knows strange proofs.
9 Anton:
Take I=[0,1), the half open interval. Do there exist topological spaces X and Y, with X and Y not homeomorphic, but XxI and YxI are homeomorphic?
E.g., if instead I=[0,1], the closed interval, you can take X=mickey mouse=disc with two discs removed, Y=cross-eyed frog=disk with two linked bands glued on the boundary.
10 Pablo:
x^x^x^x … converges if x \in [e^{-1}, e^{1/e}], e.g. with x=\sqrt{2}, this converges to 2. Given a sequence (a_i), when does the “power tower sequence” converge?
13 Andrew again:
Can you define the set of all primes with a first-order theory?
Given a first-order theory, let S(T)={|M| | M is a finite model of T}.
You can get all prime powers with the field axioms. Is there some T so S(T)={primes}.
14 Yuhao:
Let A be an abelian category, that might not have enough injectives? Can you embed into another abelian category with enough injectives? Is there a universal way?
e.g. finite abelian groups embeds into Z-modules
e.g. coherent sheaves embeds into quasi-coherent sheaves
(Anton: the Freyd embedding theorem says every abelian category embeds in Z-mod. But this doesn’t help universality.)
Secret Blogging Seminar 
2. I also wondered this as a graduate student and eventually found out that the answer is, “Yes, certainly.” They are called acyclic spaces. Probably the easiest example is a punctured Poincare sphere.
The first nontrivial homology group (with integer coefficients) is the abelianization of the fundamental group. So an acyclic space has a perfect fundamental group.
As is frequently the case in topology, everything comes down to the fundamental group. It is not too hard to show, using the Hurewicz theorem, that a simply connected acyclic CW-complex is
contractible.
8 Let r and s be the roots of
. Then 
is 
.
For the purposes of this question, think of
and 
as living in the algebraic closure of 
.
is minimal such that 
. Expanding 
as a 
-adically convergent power series in 
should imply the result in question, and many similar ones.
The integer
1. The answer is no, not even when you look at the facets of a convex simple 4-polytope with small-diameter facets. A convenient example is the Cartesian product of two convex polygons.
To achieve small-diameter facets, it is convenient to dualize to simplicial polytopes. Then the above example is the join of two polygons. The point then is that whatever examples you find, you stick two together at a facet. You stick any number together in a tree pattern, and the result can be made convex. Some of the vertex types stay the same, while others get more complicated.
Maybe there is a way to replace “smaller” by “more primitive” in the convex case. Certainly it cannot mean fewer than the number of sides of a truncated octahedron.
1 Since this isn’t a precise question, I don’t have a precise answer. But why should I let that stop me?
Two thoughts: (a) Would you consider the 120-cell a counter-example to what you are asking for? All of its faces are dodecahedra.
(b) I expect you want to ask your cell complex to be a 3-sphere, just as you wanted your graph in the two dimensional example to be embedded in a 2-sphere. (It is possible to tile a genus 3 curve with heptagons.) But there is an important difference between the 2-sphere and the 3-sphere: the 2-sphere has Euler characteristic 2, greater than the 2-torus, while the 3-sphere and 3-torus have the same Euler characteristic, namely 0. Since the bit with the hexagons can be thought of as a discrete analogue of the Gauss-Bonnet theorem, I would expect it to work differently in the 3 dimensional case.
[i]Would you consider the 120-cell a counter-example to what you are asking for? All of its faces are dodecahedra.[/i]
It’s more of an example than a counterexample, because dodecahedra have fewer facets (12) than truncated octahedra (14).
I wasn’t sure what was meant by “smaller” (which is why I considered the question to be vague.)
I wonder, could you tile the
-sphere with truncated octahedra, at least topologically? Here is what I am thinking: take the tiling of space by truncated octahedra and quotient by a lattice, giving a 
-torus. Cut this 
-torus along an embedded 
-torus, made up of faces of the tesselation. The two pieces are solid 
-dimensional torii, whose boundaries are each a 
-torus. Now, re-glue the two pieces back together after twisting by an autmorphism of the 
-torus. Can I get a 
-sphere?
14. If the abelian category is small enough, e.g. all the objects are finite length, then you can embed it into its own Ind category, and the latter has enough injectives.
e.g.: torsion Z-modules are the inductive limits of finite abelian groups, and in fact the category of torsion Z-modules is equivalent to the Ind category of finite abelian groups. (And to get injective resolutions of finite abelian groups, you only need torsion Z-modules.)
quasi-e.g.: on a reasonable scheme (maybe Noetherian is enough) any quasicoherent sheaf is an inductive limit of coherent sheaves. On the other hand, coherent sheaves are not finite length, so this doesn’t quite fit into the above framework. Nevertheless, this example illustrates a general principal, of which the precise statement above is an illustration, which is that to get enough injectives, you have to allow certain inductive limits to exist.
You can’t tile the 3-sphere by truncated octahedra, if the truncated octahedra fit together in the same way as they do in \R^3. Why? Because then \R^3 would be a covering space of S^3. This is a way to finesse what was the Euler characteristic argument in 2 dimensions.
What if there is no restriction on how you glue the truncated octahedra? Then yes you can do it, in many ways. You can take the tiling in \R^3 and cut out any topological ball of tiles, and then double it. But this is a cheap solution that also works in 2 dimensions.
So in order to have a surviving question, you need some restriction on the tiling, but not so much of a restriction that the tiling is locally standard. The typical reasonable restriction would still yield a non-positively curved metric on S^3, which would still yield (even without Perelman) the contradiction that its universal cover is \R^3.
9. X = an open ball, Y = a closed ball.
If you want X and Y to be compact (and metrizable, say), then I can’t think of any such X and Y that are manifolds. Part of the question is to what extent is a manifold with boundary determined by its interior. Many compact manifolds are.
13. I seem to recall that a set of numbers is definable by a purely existential first-order theory iff that set of numbers is in NP. This would mean that the answer is yes since PRIMES is clearly in NP.
However, I may be misremembering – it might be that you need arbitrary first-order quantifiers and a single existential second order quantifier in order to get arbitrary NP sets.
The wikipedia page on Descriptive Complexity confirms that it’s in fact an existential second-order quantifier that’s needed for NP. It also lists various classes of theories and the complexity classes that they correspond to. So the question would be to find the simplest complexity class that PRIMES falls into (I don’t know if anything better than P is known). I don’t know much about the class AC0 that they state corresponds to first-order definability – it looks like a remarkably restricted class, but I suppose it recognizes prime powers, which seems amazing to me!
The restriction I was considering (and which I thought the problem was asking for) was that the tiling be simple. In other words, in a neighborhood of any vertex, there must be 4 incoming edges, 6 two planes and 4 solid bodies. This seemed like the natural analogue of the condition that our graph be trivalent in the 2-dimensional case.
I see that this could be messed up by twisting torii, but I could also imagine that it might not be. I don’t see why it should be impossible to make a 3-sphere this way.
Re 13: According to Fagin, the subsets of
which are describable as orders of FO theories are precisely the NE sets, nondeterministic exponential time. (The exponential is because it only takes 
bits to describe an 
-element set.) That class clearly includes PRIMES.
I don’t see how to reconcile this with what Kenny is saying. Help!
An explicit solution to 13: A finite set
has prime order if and only if it can be equipped with the structures 
such that (a) 
is a field (b) 
is a total order and (c) if 
, then 
.
David: If the tiling is simple, then it is locally standard. Proof: There is only one way to glue together two truncated octahedra along a square face, the standard way. There are two ways to glue them together along a hexagonal face, but if you glue them the non-standard way, then you get three pairs of adjacent squares and three pairs of adjacent hexagons, so that you can’t complete the six edges.
Let’s say that instead of tiling S^3, we are tiling a mystery manifold M.
Again, if the tiling is locally standard, it yields a covering map from \R^3 with the standard tiling by truncated octahedra to M with its locally standard tiling. The map is constructed by induction: First send some cell of \R^3 to some cell of M, then send neighbors to neighbors, then continue. This map is a covering space! Thus the universal covering space of M is \R^3, which means that M isn’t S^3.
A similar but fancier way to argue things is to note that the tiling of M gives it a locally Euclidean metric. M is thus a Euclidean manifold, i.e., finitely covered by a 3-torus.
Yes, you are right. Thanks for bearing with me.
I guess that, when I heard the question, I was looking for an answer like the following: There is some function
, defined on combinatorial types of simple 
-polytopes. For any 
-dimensional manifold 
, given a decomposition 
into simple 
-polytopes, 
is a toplogical invariant of 
. And 
.
In the two dimensional case, we can take $\latex \sigma$ of an
-gon to be 
.
It seems to me that we still don't know whether such a function exists in three dimensions.
Just a random aside on 14: although the category C of quasi-coherent O_X-modules has enough injectives, this is a slightly misleading fact. One of the most useful consequences of having enough injectives is being able to define derived functors, yet, for an object F of C, the cohomology groups H^i(X,F) are defined by viewing F as a sheaf of abelian groups, not as a quasi-coherent O_X-module. If X is an affine scheme, then it is relatively straightforward to prove that the functor F -> H^0(X,F) is exact on C. It not an easy consequence of this fact, however, that H^i(X,F) = 0 for all quasi-coherent F when i > 0. (If X is Notherian, then one can use the “trick” that an injective quasi-coherent O_X-module G is flasque (and hence acyclic) as a sheaf of abelian groups, but this approach doesn’t work in general.)
There is some function
, defined on combinatorial types of simple 3-polytopes. For any 3-dimensional manifold M, given a decomposition 
into simple 3-polytopes, 
is a topological invariant of M. And 
.
Let’s just start with a function \sigma on types of 3-polytopes and then worry about properties. If the sum is a topological invariant, then I suspect that that by itself makes the answer proportional to Euler characteristic, which is zero in odd dimensions.
Now without requiring anything of the sum, you could ask whether the minimum of \sigma for a simple tiling of S^3 is less than what it is for the model tiling of \R^3. Well there is a cheap way to do this. You could make \sigma(truncated octahedron) = 1 and \sigma(any other simple polyhedron) = 0.
So okay, let’s ask for some other restriction on \sigma to make things more reasonable. One restriction is that \sigma is finite-to-1, so that \sigma works as a complexity function on polyhedra. But my original example rules out any such \sigma with the desired property on S^3.
Nonetheless I think that there are interesting choices of \sigma that do give you some interesting exclusions.
Hi David,
On reading some of that Fagin manuscript I see that the statement I had been remembering was talking about generalized spectra while the statement you cite talks about spectra. A spectrum is the set of natural numbers that are the cardinalities of models of some theory in the empty language, while a generalized spectrum is the set of finite structures in a given language that are the models of some theory in that language. For any first-order theory, by doing second-order existential quantifications on all the function and relation symbols in the language, you can show that the set of cardinalities of its models is a spectrum. Generalized spectra are in NP, while spectra are NE. (I suspect that the conversion between the two comes about because we are effectively representing natural numbers in unary, rather than in binary, which gives an exponential conversion factor.)
13. This was fun! The answer is yes, but it took me quite a while to see it. Start with the field axioms and add a binary relation < with axioms saying that (1) it is a total order, (2) 0 is the smallest element, (3) if an element x has some element that is (strictly) larger than it, then the smallest such element is precisely x+1.
A model for these axioms is a finite field, say of characteristic p, with a total order which is forced to start 0 < 1 < … < p-1. Now, if the field doesn’t have exactly p elements, there is some other element t, larger than p-1. Then axiom (3) forces 0 to be the element following p-1 in the order which contradicts (1) –since 0 was already smaller than p-1.
(By the way, if Andrew Critch reads this: I’m sorry I missed you when you came to Toronto this summer! It would’ve been great to talk.)
I hadn’t read the comments before, to avoid spoilers. If I had I would’ve noticed David Speyer had already given basically the same solution I gave to problem 13 (slightly simpler, in fact). Feel free to delete my two comments.
For 13, let L be the language with no non-logical symbols and let s_n be the L-sentence which says that there are exactly n elements, let T = {~s_n : n not prime}.
s_n by the way will be:
(\exists x_1 … x_n) [(\wedge _{i \neq j} x_i \neq x_j) \wedge (\forall y)[(\wedge _i x_i \neq y) -> (y \neq y)]]
5. I’m going to take the lazy way out on this question, and just quote a paper: “A convex functional on a convex domain of a topological vector space is continuous if it is bounded above in an open subset, and then it becomes locally uniformly continuous”. The author cites Bourbaki. I’m not sure if that totally answers the question or not.
4. The only way that I can think of that a description of cosets of G/H might be “nice” is if H is a complemented subgroup. Which in the normal case is the same as saying that G is a semidirect product.
In some important cases, Inn(G) is complemented by Out(G) in Aut(G). For instance, if G is compact and semisimple, then you can let Out(G) be the group of Dynkin diagram automorphisms.
If G = A_n so that Aut(G) = S_n with n ≥ 6, then Inn(G) is complemented, but in more than one way. There is more than one conjugacy class of odd involutions.
In some other cases, I don’t think that Inn(G) is complemented. For instance, suppose that G is the group generated by translations in \R^n and by scalar multiplication. Then the automorphism group is GL(n,\R) semidirect \R^n, while Out(G) is PGL(n,\R). I think that Aut(G)/Inn(G) doesn’t split.
When G=A_6, Inn(G) is not complemented.
As far as I can tell, Out(G) is very hard to control when G is anything but very straightforward. For example, if G is finite and simple, then Out(G) is solvable (Schreier’s conjecture), but this proof comes from enumeration rather than intrinsic structural knowledge.
Yes, I meant n > 6 for my remark. A_6 must be close to the smallest example of the point.
For 13, re Amit’s 22 – that construction shows that in fact every set of natural numbers is defined in the relevant way. I suppose the interesting question is whether the set of primes (or whatever set you’re interested in) can be defined by finitely many axioms (and thus by one axiom) instead of infinitely many. The sketch of the proof of Fagin’s theorem that I saw in the .pdf linked to by David Speyer above seems to assume that there are only finitely many axioms, since of course model checking can only be done in polynomial time if there are only finitely many axioms.
Thanks a lot for the answers, folks! I’m copying some of this over to the 20 questions wiki (If anyone objects, let me know):
http://scratchpad.wikia.com/wiki/20qs
The wiki will be updated after the seminar each Thursday afternoon with a fresh batch of questions for anyone interested :)
Cheers,
Critch
It might be more conducive to discussion to post the questions here.
Other secret bloggers: should I ask Andrew Critch to write a guest post with the next set of questions, or just have him post new questions in this comment thread? It seems people liked the questions, but I don’t want to clog up the blog.
Personally, I’m inclined to start a new post this week, and see how it goes.
I vote for guest post. I enjoyed reading the last one!
Definitely a guest post! I think this would be a great weekly feature.
Yeah, I don’t think blogclog is a serious danger at the present moment.
Yeah, more posts is more better. Though I swear as soon as this extended Haagerup paper gets on the arxiv I’ll put up some blog posts.