fourier analysis - Convolution and multiplication in time and frequency domains.

I don't have a complete answer yet, but it seems highly implausible such a thing exists. Assume there exists some map $T: mathcal{S}tomathcal{S}$ on Schwarz space such that
$(fcdot g) * h = (Tf*Th) cdot(Tg*Th)$, it is clear that $T$ cannot be a linear map (else the left and right sides scale differently when $h$ is replaced by $lambda h$).

Now say we want $T$ to map real-valued functions to real-valued ones, then we run into a bit of a problem: let $h$ be negative of the normal Gaussian. Then for any real-valued $f$, $f^2 geq 0$, so the LHS $(fcdot f) * h$ is non-positive. On the other hand, the RHS becomes $(Tf * Th)^2$ is non-negative. And we get a contradiction.

How about translation invariance? Suppose $(Tf)(x-s) = T(f(x-s))$. Now take $f$ to be some bump function with support in the unit interval. And take $g$ to be an arbitrary translate of $f$. In the case where $g = f$, we have that the left hand side does not always vanish, which implies that $(Tf*Th)$ cannot vanish identically. But when $g$ is a translate by some large (compared to 1) value, the LHS becomes 0. However, writing $f_t(x) = f(x-t)$, we have that $Tf_t*Th = Tf * Th_t$, so this implies that $(fcdot f_t)*h = (hcdot h_t)*f = 0$ for any $h$, and this is obviously nonsense. So $T$ cannot be translation invariant.

set theory - Choice function for Borel sets?

As Simon pointed out, you can't do this without some use of choice. However, you can "almost" do it: the trick is to work with codes for Borel sets instead of actual Borel sets (when you can).

Let $S subseteq mathbb{R}timesmathbb{R}$ be a universal analytic set, i.e. $S$ is analytic and for every analytic set $A subseteq mathbb{R}$ there is a $x$ such that $A = S_x = { y in mathbb{R} : (x,y) in S }$. By the Jankov–von Neumann Uniformization Theorem (which is provable in ZF), the set $S$ has a uniformizing (partial) function $f:mathbb{R}tomathbb{R}$, i.e. $mathrm{dom}(f) = { x in mathbb{R} : S_x neq varnothing }$ and ${(x,f(x)) : x in mathbb{R}} subseteq S$. Since every Borel set is analytic, this $f$ gives you what you want provided you know codes $x$ such that the $S_x$ are Borel sets you're interested in. Picking a unique code for each Borel set is a difficult task which requires some choice. However, you can invoke the Axiom of Choice once to get such a function that gives unique codes and keep working with that function until the end of time, thereby avoiding repeated uses of choice.

See, for example, Kechris's Classical Descriptive Set Theory (II.18) for details on the Jankov–von Neumann Uniformization Theorem, and many other useful uniformization theorems (Kuratowski–Ryll Nardzewski, Kondô–Novikov, etc) that can be used in a variety of contexts.

lo.logic - What are some results in mathematics that have snappy proofs using model theory?

Plane geometry is decidable. That is, we have a computable algorithm that will tell us the truth or falsity of any geometrical statement in the cartesian plane.

This is a consequence of Tarski's theorem showing that the theory of real closed fields admits elimination of quantifiers. The elimination algorithm is effective and so the theory is decidable. Thus, we have a computable procedure to determine the truth of any first order statement in the structure (R,+,.,0,1,<). The point is that all the classical concepts of plane geometry, in any finite dimension, are expressible in this language.

Personally, I find the fact that plane geometry has been proven decidable to be a profound human achievement. After all, for millennia mathematicians have struggled with geometry, and we now have developed a computable algorithm that will in principle answer any question.

I admit that I have been guilty, however, of grandiose over-statement of the situation---when I taught my first logic course at UC Berkeley, after I explained the theorem some of my students proceeded to their next class, a geometry class with Charles Pugh, and a little while later he came knocking on my door, asking what I meant by telling the students "geometry is finished!". So I was embarrassed.

Of course, the algorithm is not feasible--its double exponential time. Nevertheless, the fact that there is an algorithm at all seems amazing to me. To be sure, I am even more surprised that geometers so often seem unaware of the fact that they are studying a decidable theory.

ho.history overview - Can Fuchsian functions solve the general equation of degree n?

In the classic textbook Introduction to the Theory of Equations (Conkwright, 1941), on p. 85, the author writes that “the algebraic solution of the general equation of degree n is impossible if n is greater than four. By this we mean that it is not possible to find the exact values of the roots of every equation of degree n (n > 4) by performing upon the coefficients a finite number of additions, subtractions, multiplications, divisions, and root extractions.”

That proposition is considered proven by the Abel-Ruffini theorem of 1824, as Conkwright surely knew. Tantalizingly, though, he goes on to say – without elaborating – that “the general equation of degree n has been solved in terms of Fuchsian functions.” And there, it seems, the trail ends. A web search of about an hour has yielded nothing more than various restatements of the problem.

Two questions:

(1) Can anyone state, in a form suitable for reduction to a computer algorithm, a solution or family of solutions of the general equation of degree n (whether based on Fuchsian functions or not)?

(2) Would your solution(s) yield theoretically exact values, or only converging approximations?

This is my first post to your site, and I apologize in advance if I've overlooked answers right under my nose. These questions have, however, stumped my math department chair. (I’m on loan to him – I normally teach humanities, but I have an engineering background and I was asked to fill in for some math courses.)

ag.algebraic geometry - Exact sequence in étale cohomology related with proper birational morphism

Let f:X→Y be proper birational morphism between two quasi-projective varieties over an algebraically closed field $k$. I am particularly interested in the case where the characteristic of $k$ is positive; Y is singular, X is smooth and both X and Y are not projective.

Let D be a closed subset of Y, let E=f^-1(D) and assume that f|_XE:XE→YD is an isomorphism.

Based on results in characteristic 0 (and on results on rigid cohomology) I expect that there is a long exact sequence of étale cohomology groups

Hⁱ(Y,ℚ_l)→
Hⁱ(X,ℚ_l)⊕
Hⁱ(D,ℚ_l)→
Hⁱ(E,ℚ_l)→
Hⁱ⁺¹(Y,ℚ_l).

I hoped this exact sequence is well-known and would appear in a standard text, but I had trouble identifying such a text. I can think of a prove using Cox's étale version of tubular neighbourhoods for E in X and D in Y and you might be able to compare them using the Mayer-Vietoris sequences in étale cohomology, but such a proof seems quite involved (you need to define the image of an étale tubular nhd under a proper morphism (which seems non-trivially to me) and check that for certain exact sequences taking direct or projective limits turns out to be an exact functor.)

Before working out the details I would like to ask whether anyone knows a reference for the above sequence or knows a simpler/nicer proof.

geometry of triangulated category and D-modules theory

To me it seems as if the most conceptual way to think about this is as follows:

So the category of D-modules on a space is something like its category of flat (generalized) vector bundles.

As currently discussed for instance here on the nCafe, the way to think about this in terms of notions of space is the following:

in the oo-context, the plain overcategory of our ambient oo-tops over a space X is just this space X regarded dually in terms of the oo-topos of oo-stacks over it. This is a change of perspective (space to things on the space) that essentially does not lose information.

But then we can instead first form the overcategory and then stabilize it. This does lose information. And in fact, this turns out to form the category not of oo-stacks but of quasicoherent sheaves over $X$. These are to be thought of as a "linearization of all oo-stacks". I try to talk about that here.

So this gives a description of the original space which is a little more indirect. Now, with D-modules, it becomes yet a bit more indirect: instead of all stabilized oo-stacks, we just retain those that have a flat connection, in a way.

The original underlying space need not be fully reconstructible from this. But then one take the perspective that we are just interested in the linearized and flat situation, and take a stable oo-ocategory to be a formal dual of a possibly fictitious space.

analytic number theory - Eisenstein series and the Kronecker limit theorem

It is well known that the first Kronecker limit theorem gives the Laurent expansion of the Eisenstein series $E(z,s)$ over $SL(2,Z)$ at $s=1$; see, for example, Serge Lang's book Elliptic Curves, Section 20.4.

My question is, is there an analogous formula for the Eisenstein series over congruence subgroups? This seems a natural question and I believe that it must be hidden somewhere in the literature, but I cannot find a reference.

Any help will be appreciated. Thanks!

Remark: Thanks to Anweshi's help, we can find the following papers.

To be more precise, the above mentioned papers are

1. MR0318065 (47 #6614) Goldstein, Larry Joel, Dedekind sums for a Fuchsian group. I. Nagoya Math. J. 50 (1973), 21--47. 10D10 (10G05). [This paper gives the generalization of Kronecker's first limit formula to Eisenstein series over a Fuchsian group of the first kind at any cusp.]

MR0347739 (50 #241) Goldstein, Larry Joel, Errata for ``Dedekind sums for a Fuchsian group. I'' (Nagoya Math. J. 50 (1973), 21--47). Nagoya Math. J. 53 (1974), 235--237. 10D15 (10G05)

1. MR0347740 (50 #242) Goldstein, Larry Joel, Dedekind sums for a Fuchsian group. II. Nagoya Math. J. 53 (1974), 171--187. 10D15 (10G05). [This paper gives the generalization of Kronecker's second limit formula for "generalized Eisenstein series".]

real analysis - Can a continuous, nowhere differentiable function have specified "shape" at every point?

I'm a bit embarrassed to admit that:

a) This is a rather unmotivated question.

b) I can't remember whether or not I've asked this before, but searching doesn't seem to turn anything up so ...

Consider some "shape" function $phi: mathbf{R} to mathbf{R}$. Then given some function $f: mathbf{R} to mathbf{R}$, one can ask whether the "difference quotient",

$lim_{yto x} frac{f(y)-f(x)}{phi(y-x)}$,

exists at various points $x$. Letting $phi(x) = x$ corresponds to taking normal derivatives, and intuitively when the limit exists this means that near $x$, the function $f$ "looks like" $phi$ does near 0.

However, if the ratio $phi(x)/x$ is not bounded above or away from 0 as $xto 0$ (I'm mostly thinking of the case when it is neither, so that $phi$ is "wildly oscillating" in some sense), then anywhere the above limit exists and is nonzero, the function $f$ is necessarily non-differentiable.

My question: If $phi$ is some wildly oscillating function as described above (pick your favorite), can there be an $f$ for which this limit exists everywhere?

(Edit: I suppose I really want $phi$ and $f$ to be continuous functions.)

big list - Undergraduate Level Math Books

What are some good undergraduate level books, particularly good introductions to (Real and Complex) Analysis, Linear Algebra, Algebra or Differential/Integral Equations (but books in any undergraduate level topic would also be much appreciated)?

EDIT: More topics (Affine, Euclidian, Hyperbolic, Descriptive & Diferential Geometry, Probability and Statistics, Numerical Mathematics, Distributions and Partial Equations, Topology, Algebraic Topology, Mathematical Logic etc)

Please post only one book per answer so that people can easily vote the books up/down and we get a nice sorted list. If possible post a link to the book itself (if it is freely available online) or to its amazon or google books page.

dg.differential geometry - Special map from a manifold to GL_n(R)?

The question can be interpreted to ask, given a diffeomorphism $phi:M to N$, what topological information in its derivative, interpreted as a bundle map? If the bundle map is used carefully, the answer is that there is a lot of information. There is a principle that, in dimension $n ne 4$, there is enough information to completely tell when a homeomorphism can be improved to a diffeomorphism. That is a hard result if you are comparing PL homeomorphisms to diffeomorphisms, and a very hard result if you are comparing topological homeomorphisms to diffeomorphisms. It is easier to sketch that in principle you get important obstructions to smoothing a homeomorphism. The obstructions exist in all dimensions, the only difference being that in dimension 4 they aren't everything.

Suppose that $M$ and $N$ are smooth $n$-manifolds, or topological $n$-manifolds, or PL $n$-manifolds, and $phi$ is an equivalence. Then in all of these cases, $phi$ has a formal "derivative" that is locally a germ of a (continuous, PL, or smooth) homeomorphism. The "derivative" is a map between "tangent" bundles (which are actually most natural as microbundles) to match the germ picture, rather than ordinary fiber bundles. If you're afraid of germs (who isn't), a germ is no more than an equivalence class of local maps: Two local maps are the same if they agree on a neighborhood. The germ derivative of a map is basically a fake, tautological derivative.

On the other hand, the group $text{Diff}(n)$ of germs of diffeomorphisms that fix the origin is homotopy equivalent to the true derivative group $GL(n,mathbb{R})$, which is homotopy equivalent to the orthogonal group $O(n)$. The other two groups of germs are called $PL(n)$ and $TOP(n)$.

Now suppose, to take the best-behaved case, that $phi$ is a PL homeomorphism between two smooth manifolds $M$ and $N$ with smooth triangulations. It has a formal derivative $Dphi$ that is a map between tangent $PL(n)$ microbundles. You could ask, roughly speaking, whether you can homotop $Dphi$ to make it a true smooth derivative in the available $text{GL}(n,mathbb{R})$ bundle, or equivalently an $O(n)$ bundle. This is a necessary condition to be able to improve $phi$ itself to a diffeomorphism. The more subtle result is that it is also a sufficient condition. In this sense, the relative homotopy theory $PL(n)/O(n)$ exactly measures the non-uniqueness of smooth structures on manifolds. (I learned about this stuff from Rob Kirby, but it looks like it is covered in some form by Jacob Lurie.)

There is an older situation in which the derivative of a map gives you an obstruction to something, and it turns out to be the only obstruction. Namely, if $M$ is a smooth $n$-manifold, you can ask whether it immerses in $mathbb{R}^k$; or you could ask whether two immersions are equivalent through an isotopy of immersions. Clearly if $phi:M to mathbb{R}^k$ is an immersion, the homotopy type of the derivative $dphi$ (among maximum rank choices) is an invariant of $phi$, and clearly there is no immersion if there is no available homotopy class. The theorem of Smale and Hirsch is that these are the only obstructions to existence and equivalence of immersions, unless $M$ is closed and the dimensions $n$ and $k$ are equal. This theorem is illustrated very nicely in the math movie Outside In.

Another way to say it is that you can formaly weaken both questions by decoupling maps from their derivatives, but still get the correct answer.

higher category theory - The Yoneda Lemma for (oo,1)-categories?

Here is a (tautological) proof in the setting of quasi-categories. Let $A$ be a quasi-category. In ordinary category theory, one can describe the category of presheaves of sets over small category $C$ as the full subcategory of $Cat/C$ spanned by Grothendieck fibrations wih discrete fibers. A quasi-category version would consist to say that a presheaf over a quasi-category $A$ is a Grothendieck fibration (cartesian fibration in Lurie's terminology), whose fibers are $infty$-groupoids (this the way of being discrete in the higher setting). Such fibrations are simply the right fibrations.

More precisely, a model for the theory of presheaves (or $infty$-stacks) over $A$ is the model category of simplicial sets over $A$, in which the fibrant objects are right fibrations $Xto A$, while the cofibrations are the monomorphisms. The weak equivalences between two right fibrations over $A$ are simply the fiberwise categorical equivalence (for the different models for the theory of stacks over a quasi-category, see §5.1.1 in Lurie's book). From this point of view, the representable stacks over $A$ are the right fibrations $Xto A$ such that $X$ has a terminal object. If $a$ is an object ($0$-cell) of $A$, there is a canonical right fibration $A/a to A$ (from the general theory of joins): this is the representable stack associated to $a$. You can also construct a model of $A/a$ by taking a fibrant replacement of the map $a:Delta[0]to A$ (seen as an object of $SSet/A$). This model category has the good taste of being a simplicial model category. In particular, you have a simplicially enriched Hom, which I will denote here by $Map_A$, and which can be described as follows. If $X$ and $Y$ are two simplicial sets over $A$, there is a simplicial set $Map_A(X,Y)$ of maps from $X$ to $Y$ over $A$: if $underline{Hom}$ is the internal Hom for simplicial sets, then $Map_A(X,Y)$ is simply the fiber of the obvious map $underline{Hom}(X,Y)tounderline{Hom}(X,A)$ over the $0$-cell corresponding to the structural map $Xto A$. If $Y$ is fibrant (i.e. $Yto A$ is a right fibration), then $Map_A(X,Y)$ is a Kan complex (because it is the fiber of a right fibration, hence of a conservative inner Kan fibration), which is the mapping space of maps from $X$ to $Y$ for this model structure on $Sset/A$. $Map_A$ is a Quillen functor in two variables with value in the usual model category of simplicial sets.

If $a$ is an object of $A$, seen as a map $a: Delta[0]to A$, i.e. as an object of $SSet/A$, then for any right fibration $Fto A$, we see that $Map_A(a,F)$ is isomorphic to $F_a$, that is the fiber of the map $Fto A$ at $a$ (which is also an homotopy fiber for the Joyal model structure). Considering the weak equivalence from $a: Delta[0]to A$ to $A/ato A$, we also have a weak equivalence of Kan complexes

$$Map_A(A/a,F)overset{sim}{to}Map_A(a,F)=F_a, .$$

This gives the full Yoneda lemma.

graph theory - Why is edge-coloring less interesting than vertex-coloring?

I do not know whether edge coloring is more or less interesting than vertex coloring,
this is probably someting that could only be settled by a poll.
The chief reasons why edge coloring receives less attention than vertex coloriong would,
if I had to guess, be the third and fourth you offer.

Note though that if $X$ is $k$-regular graph, then Vizing's theorm tells us that
its edge-chromatic number is $k$ or $k+1$. If it is $k$, then $X$ has a 1-factorization --
we can partition its edges into $k$ pairwise edge-disjoint perfect matchings.
There is a very large literature on problems related to 1-factorizations.

Vertex coloring is also arguably more important in practice, since it arises in
connection with important scheduling and register allocation problems. Although many of
us are pure mathematicians and may feel no need to consider practical problems,
the influence of the ``real world'' on pure mathematics is nonetheless very strong.

tag removed - Best tablet computer for mathematics

I recently got an HP tm2 -- very affordable (compared to Thinkpads, Latitudes and motion computing slates), good specs, wacom digitizer+multitouch, 5h+ regular battery life.

Productivity is great using Xournal under linux (kubuntu, almost flawless hardware support). Xournal runs on windows, too, btw.

During a conference recently Xournal was brilliant -- infinite paper with infinite zoom, free rearranging, shape recognition etc. makes it easy to keep good notes (except that, well, it's still my handwriting...). The battery life of the tm2 lasted an entire conference day (with dimmed screen and wifi off).

You might want to check out the gottabemobile blog. It is an good source on mobile computing, with a lot of reviews on note taking software for tablet pcs and the iPad.

Generally speaking, pressure sensitive touch technology (like wacom or n-trig) gives better results for handwriting. But some iPad apps have features to compensate for that.

Being on a budget, a graphics tablet is a very good alternative for taking notes. I used to use one extensively before, especially for online whiteboards (like scriblink and dabbelboard) during phone conversations.

The difference between $l^1(G)$ and the reduced group $C^*$ algebra $C_r^*(G)$

In Q2 a couple of things are mixed up. If you consider $ell^1 G$ with the point-wise multiplication, then $ell^1 G$ is a commutative non-unital Banach algebra and the closure of the space of commutators (with respect to the multiplication which is induced by the group multiplication) is indeed a two-sided ideal. The quotient is given by $ell^1$-functions on the space of conjugacy classes.

However, if you consider $ell^1 G$ only with the multiplication coming from the group, then it is a unital (typically) non-commutative Banach algebra and the ideal generated by the commutators is larger that just the closure of the space of commutators. The quotient is $ell^1 H$, where $H$ is the abelianization of $G$.

For the reduced $C_{red}^*$-algebra, the ideal structure can be quite different compared with $ell^1 G$. For example, if $G$ is a non-abelian free group, then $C_{red}^star G$ is simple and there is only the trivial quotient. In particular, the ideal generated by the commutators is everything. However, if $G$ is amenable, the quotient by the commutator ideal can be identified with the reduced $C_{red}^star$-algebra of the abelianization of $G$.

Another way to read your question is the following: Can an element of finite order in $G$ become equal to an element of infinite order modulo commutators in $C_{red}^star G$? That is now a question about traces on group $C_{red}^*$-algebras. Equivalently, you could ask: Is there a trace on $C_{red}^star G$ which distinguishes element of finite order from those of infinite order. For many group (for example a free product of finite groups; not both $C_2$) there exists a unique trace on $C_{red}^star G$. In particular, traces cannot distinguish between non-trivial conjugacy classes.

If $G$ is amenable, the situation is different. I do not know whether the reduced $C^star$-algebra of an amenable group supports sufficiently many traces in order to distinguish conjugacy classes.

measure theory - Defined Almost Everywhere

Folland's real analysis text spends a lot of time on various basic $L^p$ inequalities including $L^p$ norms of convolutions. The material on convolutions is (I believe) in Chapter 8 which is titled ``Elements of Fourier Analysis," and the basic $L^p$ stuff is in Chapter 6. Incidentally, this is definitely not a research level question, and in fact, I would say it's a standard exercise (using HölderMinkowskiFubini) in a first course in measure theory.

co.combinatorics - Finding a cycle of fixed length in a bipartite graph

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of fixed length

Edit: There is natural refinement of this question: what happens if the graph has boundend valence, e.g. if the bipartite graph is cubic?

gr.group theory - Does a Cayley graph on a minimal symmetric set of generators determine a finite group up to isomorphism?

Let $G = Z_4$ be the cyclic group on 4 elements, generated by $S = {-1,1 }$, let $H = Z_2 times Z_2$ be the Klein four group, generated by $T = {(0,1),(1,0)}$. Then $|S| = |T|$ and both Cayley graphs are isomorphic to $C_4$, the cycle of length 4.

For $n > 2$ each even cycle $C_{2n}$ is a Cayley graph for the cyclic group $Z_{2n}$ and for the dihedral group $D_n$ of order $2n$.

Another well-known example is the graph of a cube $Q_3$ which is a Cayley graph for the abelian group $Z_4 times Z_2$ and for the dihedral group $D_4$. In the previous example the dihedral group was generated by two involutions, while in the latter case it is generated by an involution and an element of order 4.

If only generators are counted, without their inverses, the first two examples do not give matching counts.

gn.general topology - Name for a kind of topological property?

What should I call a property (P) of (open) subspaces of a space $X$ such that:

1. If $U$ satisfies (P), then so does every open subset $Vsubset U$




2. If {$U_i$} is a pairwise disjoint collection of sets satisfying (P), then
   $bigcup_i U_i$ satisfies (P). (Unable to make braces?)

My understanding is that if (P) satisfies condition 1, then (P) is called a
hereditary property.

CLARIFICATION: My main question is really: is there existing terminology for such
a property?

I will, however be happy to consider suggestions on the secondary question: if not, then what should I call it?

co.combinatorics - Regularizing graphs

In reply to your original question: You certainly can't add a constant number of vertices independent of the maximum degree -- consider the disjoint union of $K_k$ and a single vertex. This gives a linear lower bound in $Delta(G)$. (Even if you require that the graph is connected, take a 2-connected regular graph, remove an edge, and add two new pendant vertices adjacent to the endpoints of that removed edge.)

ETA: I didn't notice, but the way you edited the question makes my original answer kind of confusing. Hopefully it reads better now.

ETA^2:

With constant maximum degree you can add a constant number of vertices, although I'm not going to do any close analysis on the exact number -- it should be polynomial, and probably if you're more careful you can even make it linear or at worst quadratic in the maximum degree. Set $Delta(G) = k$, and note that we can add just edges to get at most $k$ vertices of degree less than $k$; otherwise there'd be two such non-adjacent vertices, and you could add in that edge.

Now we can add $O(k^2)$ pendant edges to make all the original vertices have degree $k$; then we can put in copies of $K_{k+1}$ with an edge removed on pairs of these new vertices. (As long as $k * |V(G)|$ is even, you can check parity to see that this is possible; if it's not, this is remedied by adding a new vertex and connecting it to a vertex which has degree < k before we do anything else.)

ag.algebraic geometry - A Galois Theory Computation

Excuse me for the specificity of this question, but this is a silly computation that's been giving me trouble for some time.

I want to explicitly realize the order 21 Frobenius group over ℂ(x), as ℂ(x,y,z) where y³=g(x) and z⁷=h(x,y). The order 21 Frobenius group is C₇⋊C₃, where the generator of C₃ acts by taking the generator of C₇ to its square. Or in other words < a,b|a³=1, b⁷=1, ba=a(b²) >. Furthermore, I want it to branch at exactly three points, two of which will have 7 preimages, each with ramification 3, and the third will have 3 points over it with ramification 7 each.

This can easily be shown to exist: Take ℙ¹ minus three points (say x=6,5,2); look at its algebraic fundamental group (=the profinite completion of < c, d, t| cdt = 1 >), and map it to the Frobenius group surjectively by c goes to a, d goes to b, and t goes to b^-1a^-1. This gives you a Galois cover of ℙ¹, with said ramification (because order(a)=3, order(b)=7, and order(b^-1a^-1)=3), and group the 21 order Frobenius group.

Of course, this construction is extremely difficult to track because of the topology involved. It would be much easier to deduce the field extension from the ramification behavior.

So: this can be broken down to two cyclic Galois extensions. The first, a ℂ(x,y), of the form y³=(x-2)²(x-6) is pretty easy to deduce (I need it to ramify at x=2 and x=6 and nowhere else -- this must be the equation up to change of variables). The second, a z⁷=h(x,y) is tricky. I want it to ramify only above x=5. There's some Abhyankar's lemma things going on here, and that makes the guesswork difficult, and my life much harder.

I should note that the distinction of the Frobenius group of order 21, and the reason that I'm at all interested in this example, is that it is the only order 21 group which isn't cyclic. Geometrically, it means that h is a function of both x and y, and not just x.

Thanks in advance.

at.algebraic topology - What is 'formal' ?

I would guess that the terminology goes back to the work of Sullivan and Quillen on rational homotopy theory. You should probably also look at the paper of Deligne-Griffiths-Morgan-Sullivan on the real homotopy theory of Kähler manifolds. Actually, I think that at least some familiarity with the DGMS paper is an important prerequisite for understanding many of Kontsevich's papers.

I am not totally sure, but I believe that the definitions are as follows:

• A differential graded algebra $(A,d)$ is called formal if it is quasi-isomorphic (in general, if we work in the category of dg algebras and not, say, the category of A-infinity algebras, we need a "zig-zag" of quasi-isomorphisms) to $H^ast(A,d)$ considered as a dg algebra with zero differential.




• A space X is called formal (over the rationals resp. the reals) if its cochain dg algebra $C^ast(X)$ (with rational resp. real coefficients) with the standard differential is a formal dg algebra.

One of the things I'm not sure about is whether in the definition we should require $H^ast(A,d)$ to be commutative; but for spaces this is not an issue since $H^ast(X)$ is always (graded-)commutative.

The DGMS paper proves that if X is a compact Kähler manifold, then the de Rham dg algebra consisting of (real, $C^infty$) differential forms on X with the standard de Rham differential is a formal dg algebra.

The phrase "the real (resp. rational) homotopy type of X is a formal consequence of the real (resp. rational) cohomology ring of X", which appears in e.g. the DGMS paper, simply means that the real (resp. rational) homotopy theory of X is determined by (and is probably explicitly and algorithmically computable from?) the cohomology ring of X. In other words, if X and Y are formal (over the rationals resp. the reals) and have isomorphic (rational resp. real) cohomology rings, then their respective (rational resp. real) homotopy theories are the same (and are explicitly computable, if we know the cohomology ring(s)?). For example, the ranks of their homotopy groups will be equal.

Actually I am not totally sure whether what I said in the last paragraph is true. I think it's true when X and Y are simply connected. I'm not sure about what happens more generally.

In the context of rational homotopy theory, I think the term "formal" is fine, for the reasons I've explained above. Perhaps in the more general context of dg algebras, the use of the term "formal" makes less sense. However, I think that it is still reasonable, for the following reasons. Let me use the more "modern" language of A-infinity algebras. In general, it is not true that a dg algebra $(A,d)$ is quasi-isomorphic to $H^ast(A,d)$ considered as a dg algebra with zero differential. However, it is a "standard" fact (Kontsevich-Soibelman call this the "homological perturbation lemma" (for example, it's buried somewhere in this paper), and you can find it in the operads literature as the "transfer theorem") that you can put an A-infinity structure on $H^ast(A,d)$ which makes $A$ and $H^ast(A,d)$ quasi-isomorphic as A-infinity algebras. The A-infinity structure manifests itself as a series of $n$-ary products satisfying various compatibilities. Intuitively at least, these $n$-ary products should be thought of as being analogous to Massey products in topology. So $H^ast(A,d)$ with this A-infinity structure does carry some "homotopy theoretic" information. In this language then, a dg algebra $(A,d)$ is formal if it is quasi-isomorphic, as an A-infinity algebra, to $H^ast(A,d)$ with all higher products zero. In other words, all of the "Massey products" vanish*, and thus the only remaining "homotopy theoretic" information is that coming from the ordinary ring structure on $H^ast(A,d)$.

---

*Don Stanley notes correctly that vanishing of Massey products is weaker than formality. However, I believe that triviality of the A-infinity structure is equivalent to formality. In the language of the DGMS paper, which does not use the A-infinity language, they say that formality is equivalent to the vanishing of Massey products "in a uniform way". I believe this uniform vanishing is the same as triviality of A-infinity structure. From the paper:

... a minimal model is a formal consequence of its cohomology ring if, and only if, all the higher order products vanish in a uniform way.

and also

[Choosing a quasi-isomorphism from a minimal dg algebra to its cohomology] is a way of saying that one may make uniform choices so that the forms representing all Massey products and higher order Massey products are exact. This is stronger than requiring each individual Massey product or higher order Massey product to vanish. The latter means that, given one such product, choices may be made to make the form representing it exact, and there may be no way to do this uniformly.

(Sorry for the proliferation of parentheses, and sorry for my lack of certainty on all of this, I have not thought about this in a while. People should definitely correct me if I'm wrong on any of this.)

nt.number theory - Special bases of number fields

Let K be a number field of degree n with a fixed embedding in the complex numbers. Let | . | be the normalized absolute value given by that embedding. (The square of the ordinary absolute value if the embedding is non-real.) Does there exist a basis x_1 , ... , x_n for K over the rationals with the following property:

| r_1 x_1 | + ... + | r_n x_n | = the maximum of | r_1 x_1 + ... + r_n x_n |_v

where | . |_v runs through the normalized archimedean absolute values of K ?

Later: As posed, the answer is no. Suppose I started with the field generated by a cube root and was unlucky enough to start with the real embedding. Then I'd be in effect trying to show ( x + y + z )^2 > x^3 + y^3 + z^3 on the positive octant. But if I was lucky enough to start with the complex embedding ...

ag.algebraic geometry - Parametric polynomial solution of a single polynomial equation

Let $P$ be a polynomial in $n$ variables with rational coefficients,
$P in {mathbb Q}[Z_1,Z_2, ldots ,Z_n]$, and consider the algebraic
set
$Z=lbrace (z_1,z_2,z_3, ldots ,z_n) in {mathbb Q}^n | P(z_1,z_2, ldots ,z_n)=0 rbrace$

If $r$ is a nonnegative
integer, $x_1,x_2, ldots ,x_r$ are variables, and $Q_1,Q_2, ldots ,Q_n$
are polynomials in $x_1,x_2, ldots ,x_r$ such that
$(Q_1(x_1, ldots ,x_r),Q_2(x_1, ldots ,x_r),ldots,Q_n(x_1, ldots ,x_r)) in Z$
for all $(x_1, ldots ,x_r) in {mathbb Q}^r$, we call $(Q_1,Q_2, ldots ,Q_n)$
a $r$-dimensional parametric solution
of the equation $P(z_1,z_2, ldots ,z_n)=0$. It is also
natural to define a maximal parametric solution as one with the largest possible $r$
(to avoid trivialties, we also impose
that there is no variable upon which none of the $Q_i$ depends. I'm not sure
that this last condition avoids all degenerate cases, but I'd like to avoid
definitions that involve advanced notions such as the dimension of an algebraic
variety ).

My questions : is the problem of computing the largest $r$ known to be undecidable in general ? What are the most general cases in which algebraic geometry allows us to compute the largest $r$ (and the associated parametric solutions) ?

ag.algebraic geometry - Intuition/Heuristic behind I/I^2 definition of Kähler differentials

Hello,

this one has always been mysterious to me. The Kähler differentials $Omega_{A/k}$ are definined, by the universal property

$$Der_k(A,M)=A-Mod(Omega_{A/k},M)$$
so for $M=A$ we get that $Omega_{A/k}$ is the cotangent space of $spec(A)$.
(or a relative version of it if k is no field).

There are two constructions of Kähler Differentials I know.
The first one is

$$Omega_{A/k}=langle df : text{relations satisfied by any derivation} rangle$$
I think I sort of understand this one, it says that the differential of a function just contains enough information to extract the derivation of the function out of it.
And this is what a section into cotangent space should be. Something that contains just enough information to pair it with a vector-field into a function.
The other construction is
$$Omega_{A/k}=I/I^2$$
Where $I$ is the Ideal of functions vanishing on the diagonal in $spec(A)times_{spec(k)} spec(A)$.

More geometrically it says
sections into cotangent space=functions vanishing on the diagonal mod higher order.
But still I don't think I understand this equality on an intuitive level. Can someone explain the heuristic behind this equality? Or maybe explain $Omega_{A/k}=I/I^2$ from another intuitive viewpoint?

big list - Interesting applications of the Pigeon-hole Principle

I think the solutions of these questions are very interesting (by using pigeon-hole principle), first question is easy, but second question is more advanced:

1) For any integer $n$, There are infinite integer numbers with digits only $0$ and $1$ where
they are divisible to $n$.

2) For any sequence $s=a_1a_2cdots a_n$, there is at least one $k$, such that $2^k$ begin with $s$.

Graphs where every two vertices have odd number of mutual neighbours

Maybe I'm missing something, but I'm not sure that the third condition actually generates what I'll call odd graphs. For example, if I let $A$ be the graph consisting of a single vertex and $B$ be the graph consisting of two isolated vertices, then clearly both $A$ and $B$ are even. However, if I form the $A-B-C$ construction with this choice of $A$ and $B$ I get a graph with an even number of vertices, which can't be odd by the proof of the cute question.

We can fix this by further insisting that each vertex of $A$ and $C$ have odd degree. I'll call such graphs oddly even. Note that a disjoint union of two oddly even graphs is still oddly even, so it really isn't necessary to have a $A-B-C$ construction, we only need a $A-B$ construction. Furthermore, it is not necessary that $B$ is an odd clique; $B$ can in fact be any odd graph.

We thus have the following theorem.

Theorem. Let $A$ be an oddly even graph and $B$ be an odd graph. Then the graph $A-B$ formed by taking $A$ and $B$ and adding all edges between $A$ and $B$ is odd.

So, I guess the answer to the question is no.

co.combinatorics - Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

This is a good question which is the subject of intensive research in mathematics and theoretical computer science. The blog (which is the serialization of a book in progress) "Analysis of Boolean Functions" by Ryan O'Donnell is a good source, and so is the Book: Lectures on noise sensitivity and percolation by Garban and Steif.

Here is some information

1) Of course, the Fourier coefficients of real functions over the discrete cube can be arbitrary. The question is therefore what restrictions apply for Boolean functions.

Boolean functions are characterized by $f^2(x)=1$ and since product translates to convolution for the Fourier transform, being Boolean is characterized by a property of the Fourier transform convolved with itself. However, this characterization by itself is not very useful.

Parseval formula asserts that for Boolean functions the sum of square of the Fourier
coefficients is 1. It also give the following formula for the variance of $f$,

$$operatorname{var}(f) = sum { hat f^2(S): S ne emptyset }$$

2) An important tool which gives much information is Bonami (or Bonami–Gross–Beckner) inequality. It asserts that for every function $f$,

$$|T_epsilon (f) |_2 le |f| _{1+epsilon^2}.$$
This implies that if $f$ has values $0$, $1$, and $-1$ and the the support of $f$ has measure $t$ then most of the Fourier spectrum of $f$ is for $S$ with $|A|> log n/10$ (say).

3) A similar reasoning gives the so called KKL's theorem. It asserts that for a Boolean function $f$ there is an index $k$ so that

$$sum { hat f^2(S): S subset [n], i in S } ge operatorname{var}(f) log n/n.$$

4) A theorem of Friedgut asserts that for a Boolean function $f$ if $sum hat f^2(S) |S|$ is bounded above by a constant $c$ then $f$ is "$epsilon$-close" to a "Junta. " A Junta is a Boolean function depending on a bounded number $C$ of variables. ($C$ is a function of $c$ and $epsilon$.)

5) A theorem by Green and Sanders from the paper Boolean functions with small spectral norm, asserts that a Boolean function all whose Fourier coefficients are bounded by $M$ is a linear combination of bounded number $(le 2^{2^{O(M^4)}}$) of characteristic functions of subspaces.

6) A result by Talagrand asserts that for a Boolean functions $f_n$ if $sum_i^nhat f_n^2({i})$ is o(1) then so is $sum_i^nhat f_n^2({i})$. An extension of this result to higher levels was given by Benjamini, Kalai and Schramm, and a sharp quantitative version by Keller and Kindler.

7) A theorem of Bourgain asserts that for a Boolean function if the decay of the Fourier coefficients squared is larger than quadratic in $|S|$, then again $f$ is approximately a Junta.

8) There is a conjecture called the Entropy influence conjecture that asserts that $sum hat f^2 (S)|S|$ is bounded from below by an absolute constant times $sum hat f^2(S) log (hat f^2(S))$.

cv.complex variables - Infinite-dimensional complex polynomial or rational Lie algebras and their pseudogroups

In studying the transformation groups generated by holomorphic vector fields V(z) d/dz on ℂ, I've noticed the (surely well-known) fact that the complex quadratic vector fields:

            {(a z² + b z + c) d/dz  |  (a,b,c) ∊ ℂ³}

form precisely the Lie algebra whose nonzero elements generate the linear fractional transformations, i.e., PSL(2,ℂ).

• Is there some underlying reason for this? (Beyond direct calculation, which provides an easy proof.)

Other than the further Lie algebras {0}, {a d/dz}, and {(a z + b) d/dz} over ℂ of trivial, constant, and linear (affine) vector fields, there seem to be no other polynomial finite-dimensional Lie algebras of vector fields on ℂ.

• Is there some easy-to-explain reason for this?

The next "simplest" such polynomial Lie algebras of vector fields on C seem to be those defined by all polynomial and all rational functions:

(*)        V_P := {P(z) d/dz  |  P(z) ∊ C[z]}   and   V_R := {R(z) d/dz  |  R(z) ∊ C(z)}.

• Contrariwise, do there exist finite-dimensional Lie algebras of vector fields on ℂ defined by rational functions -- other than the polynomial ones mentioned above?




• In case V_P and/or V_R generate well-studied (infinite-dimensional) Lie "groups" of transformations from open sets of ℂ into open sets, then what are these groups? Properly, these are pseudogroups, but perhaps they behave like Lie groups.

[Note: It's not hard to compute formulas for such transformations -- the flows -- directly from an expression for the vector field in terms of its zeroes (and poles, if any).]

• In any case, are there standard names for the Lie algebras V_P and V_R ?




• References to the above matters would also be appreciated.

Two questions on isomorphic elliptic curves

Question 1: Putting both curves in say, Legendre Normal Form (or else appealing the lefschetz principle) shows that if the two curves are isomorphic over $mathbf{C}$ then they are isomorphic over $overline{mathbf{Q}}$. Now we could say that for instance $E_2$ is an element of $H^1(G_{overline{Q}}, Isom(E_1))$ where we let $Isom(E_1)$ be the group of isomorphisms of $E_1$ as a curve over $mathbf{Q}$ (as in Silverman, to distinguish from $Aut(E_1)$, the automorphisms of $E_1$ as an Elliptic Curve over $mathbf{Q}$, that is, automorphisms fixing the identity point). However, $E_2$ is also a principle homogeneous space for a unique curve over $mathbf{Q}$ with a rational point, which of course has to be $E_2$, so the cocycle $E_2$ represents could be taken to have values in $Aut(E_1)$. Now $Aut(E_1)$ is well known to be of order 6,4 or 2 depending on whether the $j$-invariant of $E_1$ is 0, 1728 or anything else, respectively. Moreover the order of the cocycle representing $E_2$ (which we now see must divide 2, 4 or 6) must be the order of the minimal field extension $K$ over which $E_1$ is isomorphic to $E_2$. So $K$ must be degree 2,3,4 or 6 unless I've made an error somewhere.

Question 2: If you restrict your focus to just elliptic curves, yes your idea is right. If it's a quadratic extension, you have exactly 1 non-isomorphic companion. If you have a higher degree number field, you have nothing but composites of the quadratic case unless your elliptic curve has j invariant 0 or 1728.

Notice I am very explicitly using your choice of the word elliptic curve for both of these answers.

When is an algebra of commuting matrices (contained in one) generated by a single matrix?

Thanks for the answers. Just to wrap up a bit, here are a few examples.

1) Sometimes an ACM (algebra of commuting matrices) is sure to be generated by one of its members

2) Other times it has dimension too large to possibly be (embedded in) an ACM with a single generator.

3) An ACM might be generated by 2 matrices, not generated by any of its members, but embed in a larger ACM which does have a single generator.

4) An ACM might be generated by 2 matrices, not generated by any of its members, but not embed in a larger ACM which does have a single generator (even in the 3x3 case).

1) If the matrices are all normal then they can be simultaneously diagonalized. This reduces the problem to an algebra of diagonal matrices, which is easy to understand. Such an algebra is actually generated by one of its members.

2) The 5 dimensional algebra ${cal{A}}_5$ mentioned by Mariano (4x4 matrices with 2x2 blocks $left(begin{smallmatrix}0&A\0&0end{smallmatrix}right)$ has dimension too large to be generated by a single matrix. Furthermore, each member M generates only the 2 dimensional algebra of matrices $jI+kM$ so no subalgebra of dimension 3 or 4 has a single generator.

3) Consider the subalgebra ${cal{A}}_3$ of ${cal{A}}_5$ generated by $left(begin{smallmatrix}0&A\0&0end{smallmatrix}right)$ and $left(begin{smallmatrix}0&B\0&0end{smallmatrix}right)$ with A and B 2x2 invertible matrices (neither a scalar multiple of the other). As mentioned, we can't embed ${cal{A}}_3$ in a singly generated 4 dimensional subalgebra of ${cal{A}}_5$
However it also embeds in other 4 dimensional algebras.

For example a 4x4 matrix $left(begin{smallmatrix}BA^{-1}&C\0&A^{-1} Bend{smallmatrix}right)$ will generate an ACM which commutes with everything in ${cal{A}}_3$. I guess in this case it would automatically contain ${cal{A}}_3$. I certainly verified that randomly filling in the C does this in several cases. In many cases I tested one can get away with one or both of A and B having rank 1... but not always. The two 4x4 matrices made from matrices with $A=left(begin{smallmatrix}1&0\0&0end{smallmatrix}right)$ and $B=left(begin{smallmatrix}0&1\0&0end{smallmatrix}right)$ give an example of that. One can shrink this to 3x3 (in the case that the underlying ring is $mathbb{Z}_2$ as noted by Martin and missed by me), so I will:

4) The two $3 times 3$ matrices $left(begin{smallmatrix}0&1&0\0&0&0\0&0&0end{smallmatrix}right)$ and $left(begin{smallmatrix}0&0&1\0&0&0\0&0&0end{smallmatrix}right)$ generate an algebra A with eight members $left(begin{smallmatrix}a&b&c\0&a&0\0&0&aend{smallmatrix}right)$.
A is maximal but not generated by any of its members as each member generates a 2 dimensional (or smaller) subalgebra.

lie algebras - Is this an identity in Lie bialgebras?

Perhaps this will be a trivial question. For this post, everything is over your favorite field of characteristic $0$.

Definitions and notation

Recall that a Lie algebra is a vector space $mathfrak g$ along with a map $beta: mathfrak g^{wedge 2} to mathfrak g$ satisfying the Jacobi identity. One way to write the Jacobi identity is as follows: extend $beta$ to $mathfrak g^{otimes 2} to mathfrak g$ via the usual projection $mathfrak g^{otimes 2} to mathfrak g^{wedge 2}$, consider the map $beta circ (1 otimes beta): mathfrak g^{otimes 3} to mathfrak g$; then the restriction of this map to $mathfrak g^{wedge 3} subseteq mathfrak g^{otimes 3}$ vanishes. (Because $beta$ vanishes on the symmetric product $mathfrak g^{vee 2}$, the Jacobi identity is equivalent to $beta circ (1 otimes beta)$ vanishing on $mathfrak g^{vee 3}$.)

A Lie coalgebra is a vector space $mathfrak g$ with a map $delta: mathfrak g to mathfrak g^{wedge 2}$, satisfying the coJacobi identity, which asserts that the map $(delta otimes 1) circ delta: mathfrak g to mathfrak g^{wedge 3}$ vanishes. A vector space $mathfrak g$ that is both a Lie algebra (under $beta$) and a Lie coalgebra (under $delta$), is a Lie bialgebra if $beta$ and $delta$ satisfy an additional relationship. Namely, let $sigma: mathfrak g^{otimes 2} to mathfrak g^{otimes 2}$ be the usual "flip" map; then the bialgebra identity is that $delta circ beta$ and $(1 otimes beta)circ (delta otimes 1) + (beta otimes 1) circ (1 otimes delta) + (beta otimes 1) circ (1otimes sigma) circ (delta otimes 1) + (1 otimes beta) circ (sigma otimes 1) circ (1 otimes delta)$ are equal as maps $mathfrak g^{otimes 2} to mathfrak g^{otimes 2}$.

My question

In a calculation I'm doing, I'm led to consider the map $mathfrak g^{otimes 2} to mathfrak g^{vee 3}$ given by $(1 otimes beta otimes 1) circ (delta otimes delta)$. (I mean, $(1 otimes beta otimes 1) circ (delta otimes delta)$ lands in $mathfrak g^{otimes 3}$, but I want the composition with the natural projection $mathfrak g^{otimes 3} to mathfrak g^{vee 3}$.) In particular, for the calculation to come out right, I'd like for this map to vanish. Does it?

discrete geometry - Is there a dense subset of the real plane with all pairwise distances rational?

Let me answer Question 2.

Strong version: no. Consider $[0,1]$ with distance $d(x,y)=|x-y|^{1/3}$. There is no even a triple of points with rational distances - otherwise there would be a nonzero rational solution of $x^3+y^3=z^3$.

Weak version: yes. Let $(X,d)$ be the space in question. Construct sets $S_1subset S_2subsetdots$ such that each $S_k$ is a maximal $(2^{-k})$-separated net in $X$. Let $S$ be the union of these nets; then $S$ is countable and dense in $X$.

Now construct the following metric graph on $S$. For every $k$, connect every pair of points $x,yin S_k$ by an edge whose length is $(1-10^{-k})d(x,y)$ rounded down to a multiple of $10^{-2k}$. The new distance $d'$ on $S$ is the induced length distance in this graph. It is easy to see that the edges outside $S_k$ do not affect the distances in $S_k$, hence all these distances are rational (multiples of $10^{-2k}$). The new metric $d'$ on $S$ satisfies $frac12dle d'le d$, hence the completion of $(S,d')$ is the same set $X$ with an equivalent metric.

UPDATE.
Here is a more detailed description without the term "metric graph".

For each $k$, define a function $f_k:mathbb R_+tomathbb R_+$ by

$$f_k(t) = 10^{-2k}leftlfloor 10^{2k}(1-10^{-k})t rightrfloor .$$
The actual form of $f_k$ does not matter, we only need the following properties:

• $f_k$ takes only rational values with bounded denominators (by $10^{-k}$).




• Let $a_k$ and $b_k$ denote the infimum and the supremum of $f_k(t)/t$ over the set ${tge 2^{-k}}$. Then $frac12le a_kle b_kle a_{k+1}le 1$ for all $k$. (Indeed, we have $1-2cdot10^kle a_kle b_kle 1-10^k$.)

For every $x,yin S_k$, define $ell(x,y)=f_k(d(x,y))$ where $k=k(x,y)$ is the minimum number such that $x,yin S_k$. Note that

$$a_k d(x,y) le ell(x,y) le b_k d(x,y)$$
for all such pairs $x,y$, since $S_k$ is a $(2^{-k})$-separated set. For a finite sequence $x_0,x_1,dots,x_nin S$ define
$$ell(x_0,x_1,dots,x_n) = sum_{i=1}^n ell(x_{i-1},x_i) .$$
I will refer to this expression as the $ell$-length of the sequence $x_0,dots,x_n$. Define
$$d'(x,y) = inf{ ell(x_0,x_1,dots,x_n) }$$
where the infimum is taken over all finite sequences $x_0,x_1,dots,x_n$ in $S$ such that $x_0=x$ and $x_n=y$. Clearly $d'$ is a metric and $frac12dle d'le d$. It remains to show that $d'$ takes only rational values.

Lemma: If $x,yin S_k$, then $d'(x,y)$ equals the infimum of $ell$-lengths of sequences contained in $S_k$.

Proof: Consider any sequence $x_0,dots,x_n$ in $S$ such that $x_0=x$ and $y_0=y$. Remove all points that do not belong to $S_k$ from this sequence. I claim that the $ell$-length became shorter. Indeed, it suffices to prove that

$$ell(x_r,x_s) le ell(x_r,x_{r+1},dots,x_{s-1},x_s)$$
if $x_r$ and $x_s$ are in $S_k$ and the intermediate points are not. By the second property of the functions $f_k$, the left-hand side is bounded above by $b_k d(x_r,x_s)$ and every term $ell(x_i,x_{i+1})$ in the right-hand side is bounded below by $b_k d(x_i,x_{i+1})$. So it suffices to prove that
$$b_k d(x_r,x_s) le b_ksum_{i=r}^{s-1} d(x_i,x_{i+1}),$$
and this is a triangle inequality multiplied by $b_k$. Q.E.D.

All $ell$-lengths of sequences in $S_k$ are multiples of some fixed rational number (namely $10^{-2k}$). Hence $d'(x,y)$ is a multiple of the same number if $x,yin S_k$. Thus all values of $d'$ are rational.

What are natural questions to ask about an operad?

Hi Connie. Let me use your question as an excuse for an extended answer.
A pair of brief papers "Definitions: operads, algebras and modules" and
"Operads, algebras and modules", which are available at
http://www.math.uchicago.edu/~may/PAPERS/mayi.pdf
and http://www.math.uchicago.edu/~may/PAPERS/handout.pdf (# 84,85 on my website)
give several variants and reformulations of the original definition together with
some history of antecedents, a variety of algebraic and topological examples,
and the crucial relationship with monads that led me to coin the word "operad".
There is also a discussion of the relationship to homological algebra, showing
how the homological theory simplifies if you work over a field of characteristic
zero and, in contrast, how operads encode homology operations (Steenrod operations
and Dyer-Lashof operation) if you work over a field of finite characteristic. Notes
for a talk, http://www.math.uchicago.edu/~may/TALKS/SwitzerlandTalk.pdf, expand on
the last point.

The distinction of characteristic illustrates a general point. Operads are defined
in any symmetric monoidal category, and the right questions to ask depend in large
part on what category you are working in. It may make no sense at all to ask
algebraic questions of a topological operad or topological questions of an algebraic
operad. There is also a distinction to be made about questions to ask about operads
and questions to ask about their algebras. Incidentally, groups are by design not
examples of algebras over an operad: to define inverses, you need diagonals, and
operads are not intended, or rather intended not, to incorporate such structure.
The questions to ask also depend on what role your observation plays. Operads
allow a taxonomy of certain types of algebraic structures, so the question may just
be "what kind of structure am I looking at".

But you might also want to ask whether the algebras you are looking at give simpler
"approximations'' of more complicated or less accessible structures that occur "in
nature". For example, spaces $Omega^nSigma^n X$ occur in nature, but they can
very usefully be approximated by the monads $C_nX$ associated to appropriate operads.

You might also want to ask if operads can be used to define rigorously new structures
that you want to study. A very recent example arose in work of Bertrand Guillou and myself
in equivariant infinite loop space theory: there is an intuition of what a genuine
strict symmetric monoidal $G$-category should be, one that gives rise to a genuine
$G$-spectrum; the best definition we know is that such a category is an algebra
over a particular operad in $Cat$ (see http://front.math.ucdavis.edu/1207.3459).
Quite a few recent variants of the definition of an operad arose analogously.

In algebra, very simple operads prescribe very natural and previously unstudied
kinds of algebras. Loday and some of his students (I'm blanking on names) gave a number of examples.

While one can ask questions about the homotopy theory of operads in general,
using model category theory, that is perhaps my least favorite question to
ask: it rarely cuts to the heart of the applications, excepting those in higher
category theory, or so it seems to me. Model categories of algebras
over particular operas do play a major role in many applications, albeit
sometimes only implicitly.

I'll stop here, since I could go on forever.

One comment. While the Martin-Shnider-Stasheff book is a useful compendium, its treatments
of different topics are not all at the same level, and you might well prefer less
comprehensive treatments that better address your directions of interest. And people
should be warned that the definition of an operad in that book is actually incorrect: it omits a
crucial equivariance property that is of real importance in applications. For example, it plays a
key role in the proof of the Adem relations for the Steenrod and Dyer-Lashof operations.
Benoit Fresse's book "Modules over operads and functors" gives a quite different take
on operads, with a focus on modules over algebras over operads.