User james propp - MathOverflow

In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

2013-05-22T05:08:50Z

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems are equivalent (to any proof of Theorem A, prepend "Assume Theorem B", and vice versa; the objection "But the proof of Theorem A doesn't really use the assumption that Theorem B holds" seems more psychological than mathematical).

One might try to formalize the notion of equivalence by considering the lengths of proofs, saying "There is a derivation of Theorem A from Theorem B that is significantly shorter than any proof of Theorem A from scratch, and vice versa", but this too is squishy, in two distinct ways: the length of a proof depends on the formalization procedure one chooses, and "significantly shorter" is vague. Moreover, it's hard to imagine how one could work with this notion of equivalence, since the totality of all short proofs is going to be hard to get a handle on, for the usual reasons.

Can one find some sort of mathematical context (a topos, perhaps?) in which there is a rigorously defined (and not vacuously true) meaning of the equivalence between Sperner and Brouwer?

(For a recent article that discusses this equivalence and gives pointers to relevant literature, see "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" by Nyman and Su in the April 2013 issue of the American Mathematical Monthly.)

Answer by James Propp for How exactly does Schützenberger promotion relate to Striker-Williams promotion?

2013-04-30T01:32:19Z

Regarding your second question, my understanding is that there are two equivalent definitions of promotion for semistandard tableaux, one using jeu de taquin (which I don't really understand) and the other using Bender-Knuth involutions. I could say more about the latter (and will if you like), but maybe that's enough for now. One early reference for this is E. Gansner, On the equality of two plane partition correspondences, Discrete Math. 30 (1980), 121-132. (Can anyone suggest anything more recent?)

Cyclically symmetric functions

2013-03-24T12:31:28Z

Where can I learn about the invariant theory associated with actions of cyclic groups (as opposed to symmetric groups)?

E.g., do the functions $x+y+z$, $xy+yz+zx$, and $x^2y+y^2z+z^2x$ generate the ring of all cyclically-symmetric polynomials in $x$, $y$, and $z$?

Web-accessible and free references would be preferred.

Do all subtraction-free identities tropicalize?

2013-04-10T16:23:35Z

If you take a subtraction-free rational identity like $(xxx+yyy)/(x+y)+xy=xx+yy$ and replace $\times$,$/$,$+$,$1$ by $+$,$-$,min,$0$, do you always get a valid min,plus,minus identity like min(min($x+x+x,y+y+y$)$-$min($x,y$),$\:x+y$)$\ =\ $min($x+x,y+y$)?

constant averages along orbits

2012-09-30T23:25:35Z

What should one say to describe the situation in which a function $T$ from some set $X$ to itself, and a function $f$ from $X$ to some characteristic-zero field $K$, have the property that the average of $f$ over a $T$-orbit in $X$ is the same for each orbit? (I'm mostly concerned with the case in which every orbit is finite, so that the notion of average is the naive one.)

For about a year, in collaboration with Tom Roby and others, I've been studying such situations, which turn out to crop up everywhere in combinatorics. I think that the topic needs to have some appropriate (and not too unwieldy) terminology associated with it, but nothing seems to exist in the literature, so I'm left with the choice of adopting a parallel notion from an allied field or coining something new. But I don't love anything I've come up with so far.

(See http://mathoverflow.net/questions/94813/functions-whose-average-along-orbits-is-zero-or-a-constant for an earlier post of mine on this topic.)

Here are some terms I've considered using to denote "Property X" (with explanatory notes following the list):

#1. "$T$ is pseudotransitive relative to $f$"

#2. "The triple $(X,T,f)$ has the CAAO (Constant Averages Along Orbits) Property"

#3. "$f$ is CPC (Constant Plus Coboundary) relative to $T$"

#4. "The triple $(X,T,f)$ exhibits combinatorial ergodicity"

#5. "$f$ is convariant [sic] under $T$"

#6. "$f$ is mixed by $T$", "$T$ mixes $f$"

#7. "$f$ is balanced with respect to $T$"

#8. "$f$ is centered relative to $T$"

#9. "$f$ is Cesaro-constant under the action of $T$"

#10. "$f$ is $T$-constant"

#11. "$T$ and $f$ are disjoint"

I'm hoping a community wiki discussion might help me settle on some good nomenclature (or at least point me toward analogues of what I'm looking at in other fields of mathematics).

Notes:

#1. "$T$ is pseudotransitive relative to $f$"

If $X$ consists of a single $T$-orbit, then Property X holds trivially. So one might paraphrase Property X as: "The action is behaving like a transitive action even though it isn't (necessarily) one." But one problem with saying that $T$ is pseudotransitive relative to $f$ is that is doesn't suggest a companion nomenclature for what $f$ is relative to $T$ (which is important in my research). One can't say "$f$ is pseudotransitivized by $T$"!

#2. "The triple $(X,T,f)$ has the CAAO (Constant Averages Along Orbits) Property"

This has the virtue of being quite descriptive. And I think I could write both "$T$ is CAAO relative to $f$" and "$f$ is CAAO relative to $T$" without embarrassment. Moreover, CAAO works well as an acronym; that is, unlike CPC, which works only as an initialism, CAAO can be pronounced ("cow"). But the initially amusing homophony may not age well. (Whimsy can wear thin after a few decades.)

#3. "$f$ is CPC (Constant Plus Coboundary) relative to $f$"

A function $f$ has Property X relative to $T: X \rightarrow X$ if and only $f$ can be written as $f(x) = c + g(x) - g(T(x))$, where $c$ is some constant and $g$ is some (non-unique) function from $X$ to $K$. (One can also say that $f$ is cohomologous to a constant.) I'd be happier with the constant-plus-coboundary nomenclature if the $g$-functions turned out to play an important role in examples, which so far hasn't been the case. Also, I fear that the phrase "CPC phenomenon" would invite confusion with the phrases "CSP" and "cyclic sieving phenomenon", which frequently arises in the same combinatorial situations as Property X.

#4. "The triple $(X,T,f)$ exhibits combinatorial ergodicity"

I've used this one in my talks. I like it, since Boltzmann's notion of ergodicity is precisely that long-term averages are the same for all orbits (and if all orbits are finite, long-term averages are the same as orbit averages). People have sometimes objected that in dynamics and in physics, ergodicity is something that pertains to a mapping $T$, not a mapping $T$ relative to a function $f$. I've replied that the word ergodic always means relative to a set of functions (measurable functions if one is doing ergodic theory, macroscopic functions if one is doing physics), even if that relativity is left implicit. So why not make that relationship explicit, and say that what's really ergodic is a map $T$ with respect to a function or set of functions? I was happy with this for a while. But one can't say "$f$ is ergodic relative to $T$"; that stretches the metaphor too far for my taste. And I need a crisp way of referring to the functions $f$ such that $(X,T,f)$ has Property X, for some particular map $T: X \rightarrow X$.

#5. "$f$ is convariant under $T$"

Yes, I mean convariant, not covariant, which already means something else. "Convariant" is meant to be a counterpart to "invariant", since every function from $X$ to $K$ can be written as the sum of an invariant function (that is, a function $h$ satisfying $h(T(x))=h(x)$ for all $x$) and a function with Property X. Note that the invariant functions form a subspace, as do the convariant functions. So from a linear algebra perspective, it's a nice situation.

#6. "$f$ is mixed by $T$", "$T$ mixes $f$"

I like this in part because of the underlying physical intuition (we say a solution of 90% water and 10% salt had been mixed if every portion of the solution has water and salt in those same proportions; replace "portion" by "orbit" and you're fairly close to Property X). Also, one can refer to the "invariant" and "convariant" functions as being respectively "fixed" and "mixed" by $T$, which is cute (but not too cute!) and certainly succinct. Yet I worry that the ergodic theory meaning of the word "mixing", which carries connotations stronger than ergodicity, may be distracting or even confusing for some people.

#7. "$f$ is balanced with respect to $T$"

This is on the bland and vague side, but I can't completely dismiss it.

#8. "$f$ is centered relative to $T$"

Ditto.

#9. "$f$ is Cesaro-constant under the action of $T$"

Property X says that if we define $F(x)$ as the Cesaro mean of $f(x),f(T(x)),f(T(T(x))),...$, then $F$ is constant over $X$ (where the Cesaro mean of a sequence is the limit as $n$ goes to infinity of the mean of the first $n$ terms).

#10. "$f$ is $T$-constant"

This is intended as a shorthand for "$f$ is constant modulo $T$-coboundaries".

#11. "$T$ and $f$ are disjoint"

I don't know a sense (coming from some allied field) in which the word "disjoint" might be applicable to Property X, but I suspect that there might be.

Answer by James Propp for constant averages along orbits

2013-03-14T15:50:06Z

I've decided to go with the terms "homomesy" and "homomesic" (from Greek roots meaning "same middle"), suggested by my collaborator Tom Roby.

To see why I think the the concept deserves a name, check out the examples given in the slide-presentation http://jamespropp.org/mitcomb13a.pdf (which barely scratches the surface of all the examples of the phenomenon that have come to light over the past year).

To see a context in which the concept of homomesy is precisely dual to the concept of invariance, see http://jamespropp.org/Dec2012a.pdf .

Using a quadratic kernel instead of a linear kernel in the Laplace transform

2013-03-02T13:33:27Z

Suppose $f$ is a bounded continuous function on $[0,\infty)$ such that $\int_0^\infty f(t) \exp(-xt) \: dt \rightarrow 0$ as $x \rightarrow 0^+$. Does it follow that $\int_0^\infty f(t) \exp(-xt^2) \: dt \rightarrow 0$ as $x \rightarrow 0^+$? Is the reverse implication true?

I suspect that the answer is "no" in both cases, so here's my real (although vague) question: is there a notion of regularity for $f$ (along the lines of the notion of almost-periodicity) such that the two limit-assertions imply each other when $f$ is regular?

Bijective proof of Ramanujan's congruence

2013-01-17T17:00:01Z

Is there a known bijective proof of Ramanujan's congruence for the partition function modulo 5? E.g., is there a construction that for every $n$ congruent to 4 mod 5 gives a permutation of the partitions of $n$ that increases the Dyson rank of each partition by 1 mod 5?

Is pi a good random number generator?

2010-06-03T18:12:29Z

Part of what I do is study typical behavior of large combinatorial structures by looking at pseudorandom instances. But many commercially available pseudorandom number generators have known defects, which makes me wonder whether I should just use the digits (or bits) of $\pi$.

A colleague of mine says he "read somewhere" that the digits of $\pi$ don't make a good random number generator. Perhaps he's thinking of the article "A study on the randomness of the digits of $\pi$" by Shu-Ju Tu and Ephraim Fischbach. Does anyone know this article? Some of the press it got (see e.g. http://news.uns.purdue.edu/html4ever/2005/050426.Fischbach.pi.html ) made it sound like $\pi$ wasn't such a good source of randomness, but the abstract for the article itself (see http://adsabs.harvard.edu/abs/2005IJMPC..16..281T ) suggests the opposite.

Does anyone know of problems with using $\pi$ in this way? Of course if you use the digits of $\pi$ you should be careful not to re-use digits you've already used elsewhere in your experiment.

My feeling is, you should use the digits of $\pi$ for Monte Carlo simulations. If you use a commercial RNG and it leads you to publish false conclusions, you've wasted time and misled colleagues. If you use $\pi$ and it leads you to publish false conclusions, you've still wasted time and misled colleagues, but you've also found a pattern in the digits of $\pi$!

packing disks tightly in the plane

2012-12-14T03:35:21Z

Given a discrete point set $S$ in ${\bf R}^2$ with a specified base-point $p_0 \in S$, label the remaining points as $p_1, p_2, \dots$ in order of increasing distance from $p_0$ (with ties resolved indifferently), and let $d_n(S,p_0)$ be the distance between $p_0$ and $p_n$.

What is known about the infimum of $d_n(S,p_0)$ as $S$ and $p_0$ vary, if $S$ is required to have the property that no two of its points are less than 1 apart? An equivalent statement of the problem replaces each point-set with a packing of the plane by disjoint disks of radius 1/2. It would be very nice if the infimum of $d_n$ was achieved by the hexagonal packing of the plane, but my intuition says that for some $n$ this is not the case; I wonder if this is known.

Answer by James Propp for packing disks tightly in the plane

2012-12-14T21:14:53Z

There's an intuitive way to see that $d_7$ is not achieved by the hexagonal packing: put five disks (evenly spaced), rather than six, around disk 0. Now add five disks into the gaps between the first five disks. It is easy to see that disks 6 through 10 in this packing are closer to the center than disk 7 in the hexagonal packing.

multidimensional rotation terminology

2012-11-06T20:23:12Z

Given an element $g$ of the orthogonal group $O(n)$, is there a name for the subspace of $R^n$ that's fixed by $g$, and a name for the orthogonal complement of this space? (The latter is what I really want to know. I'm guessing that the former is typically called the fixed subspace, but the latter subspace is more arcane. I'm inclined to call it the equatorial subspace, but I'd rather not give it a name if it already has one, or use the term "equatorial subspace" if it already means something else.)

Conjugating the Lyness 5-cycle into a rotation of the plane

2012-10-27T17:09:42Z

The Lyness 5-cycle is the map that sends $(x,y)$ to $(y,z)$ with $z=(y+1)/x$. Leaving aside the set on which the map is not well-defined, the map is of order 5 (hence its name). Is there an algebraic map that conjugates the map to a rotation by 72 degrees?

conditional equality symbol

2011-04-07T02:42:12Z

Is there a standard notation (perhaps $A \stackrel{\leftarrow}{=} B$) meaning "in all situations where $B$ is defined, $A$ is defined and equals $B$"?

The kind of situation in which such a notation would be useful is the teaching of formulas like $$\lim_{x \rightarrow a} (f(x)-g(x)) = \lim_{x \rightarrow a} f(x) - \lim_{x \rightarrow a} g(x).$$ When I teach such formulas I take pains to teach them as theorems, with hypotheses that must be satisfied (in this case, the existence of $\lim_{x \rightarrow a} f(x)$ and $\lim_{x \rightarrow a} g(x)$) before the truth of the formula can be concluded, and I call to the students' attention the asymmetry of the situation (whenever the RHS is defined the LHS is defined and must be equal to it, but it is emphatically NOT always the case that when the LHS is defined the RHS must be defined and must be equal to it). I feel that one way to help students remember what the theorem says would be to use a variant of the equals sign when summarizing the theorem by a formula.

Has anyone introduced such a symbol? I think it would be at least as useful as the ":=" ("is defined as") symbol.

functions whose average along orbits is zero or a constant

2012-04-22T06:12:38Z

Is there some name in ergodic theory or integrable systems theory for a function whose average value on every orbit is zero? (Of course when I say "every orbit" in the context of ergodic theory I mean "modulo a set of measure zero".)

The space of $L^2$ functions with ergodic average zero is the orthocomplement of the space of invariant $L^2$ functions, under the dynamical inner product $\langle f,g \rangle = \lim_{n \rightarrow \infty} (1/n) \sum_{k=0}^{n-1} f(T^k x)\overline{g}(x)$, so it seems like a natural space for ergodic theorists to consider. And the space of functions that average to zero along orbits seems even more natural in the setting of integrable systems, where evolution laws and conserved quantities can switch places.

I'm also interested in knowing if there's a name for functions whose average value on every orbit is some orbit-independent constant. I don't want to invent terminology for such functions if satisfactory terminology already exists, and I suspect it does, though I haven't been able to find it on the web. I looked at an introductory article on cocycles and coboundaries in ergodic theory, but didn't find what I was looking for.

completeness axiom for the real numbers

2010-03-05T20:41:40Z

Do any treatises on real analysis take the following as the basic completeness axiom for the reals?

"Let $A$ and $B$ be set of real numbers such that (a) every real number is either in $A$ or in $B$; (b) no real number is in $A$ and in $B$; (c) neither $A$ nor $B$ is empty; (d) if $\alpha \in A$, and $\beta \in B$, then $\alpha < \beta$. Then there is one (and only one) real number $\gamma$ such that $\alpha \leq \gamma$ for all $\alpha \in A$, and $\gamma \leq \beta$ for all $\beta \in B$."

This appears as Theorem 1.32 in Walter Rudin's "Principles of Mathematical Analysis", and can be traced back to Dedekind's "Continuity and Irrational Numbers" (section V, subsection IV). Both Rudin and Dedekind derive this result from the construction of the reals via cuts of the rationals.

Authors who prefer to axiomatize the reals directly (instead of constructing them from the rationals) might be expected to take the above property as an axiom, but I haven't found anyone who does this. Instead, they all assume the least upper bound property as an axiom, or the nested interval property, or the convergence of Cauchy sequences.

I personally think the way to go is to take Rudin's Theorem 1.32 as an axiom (because it is simple and compelling) and then derive the least upper bound property (since it is more useful in practice than 1.32) and then get to work building up the apparatus of real analysis. But leaving aside the issue of whether this is the right way to go: have any authors taken this approach?

I should remark that the geometrical analogue of Theorem 1.32, characterizing the completeness of the line, appears to be well known to geometers (especially those interested in the foundations of geometry; see for instance Marvin Jay Greenberg's very nice article in the March 2010 issue of the Monthly).

notation for formal Laurent series

2012-07-24T22:37:13Z

I've found a few articles that write the ring of formal Laurent series in $t$ as $R((1/t))$, but what's the underlying meaning of $\cdot ((\cdot))$?

A mathematician of my acquaintance swears that $R((t))$, not $R((1/t))$, should be used to denote the ring of formal Laurent series in $t$. We can't decide who's right without knowing what $\cdot((\cdot))$ means. (We both agree that $R[[t]]$ denotes the ring of formal power series in $t$ with coefficients in $R$.)

What are some examples of "chimeras" in mathematics?

2011-04-28T18:34:56Z

The best example I can think of at the moment is Conway's surreal number system, which combines 2-adic behavior in-the-small with $\infty$-adic behavior in the large. The surreally simplest element of a subset of the positive (or negative) integers is the one closest to 0 with respect to the Archimedean norm, while the surreally simplest dyadic rational in a subinterval of (0,1) (or more generally $(n,n+1)$ for any integer $n$) is the one closest to 0 with respect to the 2-adic norm (that is, the one with the smallest denominator).

This chimericity also comes up very concretely in the theory of Hackenbush strings: the value of a string is gotten by reading the first part of the string as the unary representation of an integer and the rest of the string as the binary representation of a number between 0 and 1 and adding the two.

I'm having a hard time saying exactly what I mean by chimericity in general, but some non-examples may convey a better sense of what I don't mean by the term.

A number system consisting of the positive reals and the negative integers would be chimeric, but since it doesn't arise naturally (as far as I know), it doesn't qualify.

Likewise the continuous map from $\bf{C}$ to $\bf{C}$ that sends $x+iy$ to $x+i|y|$ is chimeric (one does not expect to see a holomorphic function and a conjugate-holomorphic function stitched together in this Frankenstein-like fashion), so this would qualify if it ever arose naturally, but I've never seen anything like it.

Non-Euclidean geometries have different behavior in the large and in the small, but the two behaviors don't seem really incompatible to me (especially since it's possible to continuously transition between non-zero curvature and zero curvature geometries).

One source of examples of chimeras could be physics, since any successful Theory Of Everything would have to look like general relativity in the large and quantum theory in the small, and this divide is notoriously difficult to bridge. But perhaps there are other mathematical chimeras with a purely mathematical genesis.

the use of parentheses to mean "I won't tell you this again"

2012-07-20T19:04:15Z

A reader of one of my drafts found fault with my use of parentheses; I put the word "bounded" in parentheses in a statement of a certain theorem, and he replied "But the statement isn't true if the assumption of boundedness is dropped!"

That reader seemed to be thinking that parentheses mark things that are in some way inessential (as is sometimes the case in non-mathematical prose). But, as I wrote to him:

Here I am using parentheses to mean "Of course the interval must be bounded! In case some of you are nodding off, I'll include the stipulation of boundedness, but I might not include it next time." I wonder if that use of parentheses has a name?

Does this use of parentheses have a name, or any sort of pedigree that might dignify it, within or beyond mathematical writing?

I have no idea how to tag this post; it's a question about the (possibly nonexistent) subfield of modern Rhetoric that is concerned with the ways mathematicians use language to communicate ideas to other mathematicians. I'll be grateful if someone will suggest appropriate tags and add them (and I'll make a note of what the tag is, in case I need it again).

solving linear equations made difficult

2012-07-17T04:13:26Z

(Note: This is a what's-in-the-literature question, not a what's-mathematically-true question, but I believe both are considered valid kinds of MathOverflow question.)

I saw this amusing derivation on the blackboard at MSRI a few months ago (I'm paraphrasing and reformatting slightly, though my attempts at formatting may not work as intended):

"Problem: Solve $x = ax + b$ for $x$.
Solution: $$x = a(ax+b) + b = a^2 x + ab + b = a(a(ax+b)+b)+b= a^3 x + a^2 b + ab + b = \cdots$$ (assuming $|a| < 1$) $$= \lim_{n \rightarrow \infty} a^n x + b \sum_{i=0}^{\infty} a^i = 0 + b/(1-a).$$ This also holds by analytic continuation for all $a \neq 1$."

Has anyone seen this before? I took a photograph of the blackboard, and I am inclined to submit it to Mathematics Magazine, but first I want to know the provenance.

Curt McMullen was in residence at MSRI at the time, and he seemed a likely culprit, but when I pointed it out to him he seemed amused, and he denied authorship, so I don't have any suspects at present.

It would be embarrassing to publish this and then receive letters saying "This argument appears almost word-for-word in Littlewood's Miscellany" (or something like that).

functions from Q to itself with derivative zero

2012-07-11T01:30:18Z

Let $f: {\bf Q} \rightarrow {\bf Q}$ be a "${\bf Q}$-differentiable" function whose "${\bf Q}$-derivative" is constantly zero; that is, for all $x \in {\bf Q}$ and all $\epsilon > 0$ in ${\bf Q}$, there exists $\delta > 0$ in ${\bf Q}$ such that for all $y \in {\bf Q}$ with $0 < |x-y| < \delta$, $|(f(y)-f(x))/(y-x)| < \epsilon$.

An example of such a function is the 2-valued function on ${\bf Q}$ that takes the value 0 or 1 according to whether $x<\pi$ or $x>\pi$.

Must $f$ be locally constant, in the sense that for all $x \in {\bf Q}$, there exists $\delta > 0$ in ${\bf Q}$ such that for all $y \in {\bf Q}$ with $|x-y| < \delta$, $f(y)=f(x)$?

I have a feeling that this is not a hard problem (and I am even afraid some of you will think that it is a homework problem!), but it actually arose from my research (see http://jamespropp.org/reverse.pdf), and after an hour of thought I still don't see the answer. In an ideal world I'd mull it over longer before posting, but since the journal to which I have submitted the paper has given me a deadline for making revisions, and the deadline is approaching, I am swallowing my pride and seeking help.

What is the difference between holonomy and monodromy?

2012-05-04T00:47:26Z

And what is the simplest example in which one is trivial and the other is not?

effective/constructive/algorithmic probability theory

2012-04-03T02:11:11Z

What sort of "alternative" probability theories are out there in which the methods of proof are inherently constructive?

I know of a number of theorems that say that if you take an infinite sequence of i.i.d. random variables of thus-and-such a kind (let's say that they're fair bits, for definiteness), and use them in a specified fashion to generate a sequence of combinatorial objects of a particular sort, and rescale those combinatorial objects in a time-dependent fashion, then the rescaled objects converge to some sort of limit object with probability 1. However, the proofs that I know are ineffective, in the sense that the proofs don't give you a way to construct any particular infinite sequence of bits such that, if you use them as described above, the convergence occurs.

Well, sort of. In each case of this situation occurring, there's a way to "cheat" by using the theorem itself to guide the choice of bits; you can just choose your bits to have the behavior that you're trying to prove. Is there some principled way to rule out such "cheating"? When it comes to cheating, I believe that "I know it when I see it", but I don't know how to formulate a precise definition of cheating that captures my intuitions.

A web search turned up a talk on "Applications of Effective Probability Theory to Martin-Lof Randomness" (http://www.loria.fr/~hoyrup/icalp_slides.pdf), which is one example of the kind of theory I mean. Are there others?

theorems equivalent to the parallel postulate

2012-03-05T02:29:11Z

Is there a good survey article listing all the theorems of Euclidean geometry that are equivalent to the parallel postulate?

enumerative meaning of natural q-Catalan numbers

2012-04-04T15:16:01Z

Define $[n]=(1-q^n)/(1-q)$ and $[n]!=[1][2][3] \cdots [n]$, so that $[2n]!/[n]![n+1]!$ is a polynomial in $q$ (the most algebraically natural $q$-analogue of the Catalan numbers); what enumerative interpretation(s) does it have, vis-a-vis the standard members of the "Catalan zoo"? I would be especially interested in answers pertaining directly to triangulations of polygons, without any intervening bijections.

probability theory for combinatorialists

2012-03-29T19:01:14Z

More than one combinator(ial?)ist has asked me to recommend a good book to learn probability from, and I never know what to say; the probability theory that I use in my research up was mostly learned piecemeal. (The stuff I learned in grad school from reading Chung and Feller hasn't been as useful, and I didn't especially enjoy those books.) Any suggestions?

Answer by James Propp for theorems equivalent to the parallel postulate

2012-03-22T08:07:21Z

Doug Chatham's answer is the best I received; see Theorem 23.7 of George E. Martin's "The Foundations of Geometry and the Non-Euclidean Plane".

Uniformizing the surcomplex unit circle

2012-03-15T23:02:10Z

Is the multiplicative Group of surcomplex numbers of modulus 1 isomorphic to the additive Group of the surreal numbers modulo the sub-Group of surreal integers? And, do Norman Alling's surreal extensions of sine and cosine (defined in section 7.5 of his book "Foundations of analysis over surreal number fields") accomplish the isomorphism?

Surreal numbers vs. non-standard analysis

2012-03-19T18:10:49Z

What is the relationship between the surreal numbers and non-standard analysis?

In particular, is there a transfer principle for surreal numbers they way there is for NSA?

A specific situation in which such a transfer principle would be useful arose in the thread http://mathoverflow.net/questions/91337/uniformizing-the-surcomplex-unit-circle ; can the surjectivity of the map $t \mapsto e^{it}$ from the reals to the complex unit circle be transferred to the surreals? Presumably, one would need a definition of the map that was in some sense first-order; what sorts of definitions count as first-order? It is not clear to me how definitions involving the two-sided bracket operation can be fit into a first-order framework.

Answer by James Propp for Are there any interesting connections between Game Theory and Algebraic Topology?

2012-03-15T22:34:23Z

In combinatorial game theory (more specifically, the theory of impartial games), the set of winning options of a winning option is the empty set, which reminds me of the fact that the boundary of the boundary of a manifold-with-boundary is empty.

Also, when one takes a disjunctive sum of two impartial games $G$ and $H$, an option of $G+H$ is of the form $G'+H$ or $G+H'$, where $G'$ is an option of $G$ and $H'$ is an option of $H$. This reminds me of the definition of a derivation: $D(fg) = (Df)g + f(Dg)$. The two examples of derivations that come to mind are differentiation of functions and, as above, the boundary operation $\partial$ applied to manifolds-with-boundary: the boundary of $M_1 \times M_2$ is $\partial M_1 \times M_2 \cup M_1 \times \partial M_2$.

I have no idea whether there's an way to cash in on this formal resemblance.

Comment by James Propp

2013-04-12T02:07:37Z

@quid: I've changed tropical-mathematics to tropical-arithmetic. Thanks for pointing out the existence of the tropical-arithmetic tag.

Comment by James Propp

2013-04-10T19:06:57Z

Colin and Will's answers are both convincing; thanks! One thing more I'd appreciate is a literature reference that I can cite if I publish something that makes use of this transfer principle. Given how straightforward the proof is (at least in hindsight), it's likely that some version of this result appears in some existing book or article.

Comment by James Propp

2013-03-24T14:47:45Z

This reference is extremely well-written, and it covers lots if examples, but the cyclic action on the variables doesn't appear to be one of them (though Theorem 1.17 comes close; it's good to know that for the dihedral action, and all other finite Coxeter group actions, things work out about as nicely as one could hope).

Comment by James Propp

2013-03-03T04:34:46Z

@Liviu: Thanks, but I am confused. What is $s$? Also, does $L_{loc}^1$ mean locally integrable in the sense of being integrable over every finite interval, or is some sort of uniformity required?

Comment by James Propp

2013-02-08T05:20:43Z

@Jerome: Oh no -- a mistake in the very first paragraph of my article! Ah well; thanks for catching this error. I will fix it once I get LaTeX properly installed on my new Mac and can create pdfs again.

Comment by James Propp

2012-12-17T16:38:53Z

Henry Cohn writes: "Graham and Sloane conjecture that minimizing the second moment about the centroid leads to hexagonal lattice excerpts (except for 4 disks, where there's a one-parameter family of optima)." See R. L. Graham and N. J. A. Sloane, "Penny-packing and two-dimensional codes", Discrete Comput. Geom. 5:1-11 (1990) (math.ucsd.edu/~ronspubs/90_01_penny_packing.pdf) and T. Chow, "Penny-packings with minimal second moment", Combinatorica 15 (2) (1995) 151-158 (18.87.0.36/~tchow/penny.pdf). This is not the question that I asked, but it's the question I should have asked!

Comment by James Propp

2012-11-04T20:23:29Z

@Ricky: I guess you're thinking that a closed interval in an ordered field could be defined as a convex subset that is topologically closed. Was that your interpretation of "closed interval"?

Comment by James Propp

2012-11-02T03:53:28Z

@Ricky: I thought that the most natural definition of "closed interval" in an ordered field was "a set consisting of all $x$ satisfying $a \leq x \leq b$ for some $a,b$", so that a closed interval has endpoints by definition. But you seem to think differently. Can you explain?

Comment by James Propp

2012-11-02T01:27:59Z

@Francois: That answers my question. Thanks!

Comment by James Propp

2012-10-29T16:33:16Z

The reference is definitely helpful, especially the explicit formulas on page 3. However, I don't know how to explicitly see the map $(x:y:z) \mapsto (x(z-y):z(x-y):xz)$ (the birational transformation that Beauville and Blanc treat) as being conjugate to the map $(x:y:z) \mapsto (xy:(y+z)z:xz)$ (the projective version of the Lyness 5-cycle map).

Comment by James Propp

2012-10-03T04:53:59Z

@Terry Tao: I think there might be a connection between Property X and the notion of disjointness in ergodic theory for maps with discrete spectrum, though I haven't been able to find a satisfactory link. E.g., let $X = R^n/Z^n$, $T(x) = x+u$ for some fixed $u$, and $f(x) = \exp(2 \pi i x \cdot v)$ for some fixed $v$. In this situation, or something like it, I think $(X,T,f)$ has Property X iff the spectra associated with $T$ and $f$ are disjoint (though I don't know what "the spectrum associated with $f$" might actually mean).

Comment by James Propp

2012-10-03T04:48:05Z

@ Anthony Quas: Yes; see #3 in my post.

Comment by James Propp

2012-07-25T02:57:41Z

I agree with Pete's comment completely. (In my earlier email correspondence with him, I confused (17) with (18), and missed the salient difference between them: in the first case the boundedness follows from the other hypotheses, and in the second it doesn't.) The "praeteritional" ("praeterite"?) use of parentheses is allowable for (17), but not for (18). Anyway, the responses I've received to this question have convinced me that in mathematical writing it's best to avoid confusion by being more explicit (e.g. "for the rest of this proof, all intervals are assumed to be bounded"). Thanks!

Comment by James Propp

2012-07-25T00:25:22Z

I've taken a closer look at the articles I mentioned in the original post, and it appears that they all are looking at formal sums in which the exponent of t is bounded from above, rather than from below. So it seems that my acquaintance was quite right about $R((1/t))$. Is it fair to say, then, that the definition of $R((x_1,x_2,…))$ is the quotient ring of $R[[x_1,x_2,…]]$?

Comment by James Propp

2012-07-24T15:46:16Z

The fit isn't perfect, but it's close enough for me.