User erik davis - MathOverflow

On a schoolchild puzzle of V.I. Arnold (re: toric varieties)

2011-01-20T06:20:58Z

When reading the interview with Vladimir Arnold in the April 1997 edition of the Notices, I came across the following anecdote.

Many Russian families have the tradition of giving hundreds of such problems to their children, and mine was no exception. The first real mathematical experience I had was when our schoolteacher I. V. Morozkin gave us the following problem: Two old women started at sunrise and each walked at a constant velocity. One went from A to B and the other from B to A. They met at noon and, continuing with no stop, arrived respectively at B at 4 p.m. and at A at 9 p.m. At what time was the sunrise on this day?

I spent a whole day thinking on this oldie, and the solution (based on what is now called scaling arguments, dimensional analysis, or toric variety theory, depending on your taste) came as a revelation.

I found the solution in a rather straightfoward fashion, but I was curious as to the parenthetic remark. So, can anybody tell me (as a total outsider to algebraic geometry), what does this problem have to do with toric varieties?

Probabilistic Proofs of Analytic Facts

2009-12-18T01:04:49Z

What are some interesting examples of probabilistic reasoning to establish results that would traditionally be considered analysis? What I mean by "probabilistic reasoning" is that the approach should be motivated by the sort of intuition one gains from a study of probability, e.g. games, information, behavior of random walks and other processes. This is very vague, but hopefully some of you will know what I mean (and perhaps have a better description for what this intuition is).

I'll give one example that comes to mind, which I found quite inspiring when I worked through the details. Every Lipschitz function (in this case, $[0,1] \to \mathbb{R}$) is absolutely continuous, and thus is differentiable almost everywhere. We can use a probabilistic argument to actually construct a version of its derivative. One begins by considering the standard dyadic decompositions of [0,1), which gives us for each natural n a partition of [0,1) into $2^{n-1}$ half-open intervals of width $1/{2^{n-1}}$. We define a filtration by letting $\mathcal{F}_n$ be the sigma-algebra generated by the disjoint sets in our nth dyadic decomposition. So e.g. $\mathcal{F}_2$ is generated by ${[0,1/2), [1/2,1)}$. We can then define a sequence of random variables $Y_n(x) = 2^n (f(r_n(x)) - f(l_n(x))$ where $l_n(x)$ and $r_n(x)$ are defined to be the left and right endpoints of whatever interval contains x in our nth dyadic decomposition (for $x \in [0,1)$). So basically we are approximating the derivative. The sequence $Y_n$ is in fact a martingale with respect to $\mathcal{F}_n$, and the Lipschitz condition on $f$ makes this a bounded martingale. So the martingale convergence theorem applies and we have that $Y_n$ converges almost everywhere to some $Y$. Straightforward computations yield that we indeed have $f(b) - f(a) = \int_a^b Y$.

What I really like about this is that once you get the idea, the rest sort of works itself out. When I came across the result it was the first time I had thought of dyadic decompositions as generating a filtration, but it seems like a really natural idea. It seems much more structured than just the vague idea of "approximation", since e.g. the martingale condition controls the sort of refinement the next approximating term must yield over its predecessor. And although we could have achieved the same result easily by a traditional argument, I find it interesting to see from multiple points of view. So that's really my goal here.

Answer by Erik Davis for Dimension Leaps

2009-11-14T07:17:41Z

Here's a fun little example that I thought was neat... it's quite simple but tends to go against most people's geometric instinct.

We consider the cube $[-2,2]^d$ in $\mathbb{R}^d$. At the points with all coordinates equal to 1 or -1 (e.g. in $\mathbb{R}^3$, points like (1,1,1), (1,-1,-1), etc) we put unit balls. We define the "central ball" $B_d$ to be the largest ball centered at the origin that does not intersect the interior of any of the other balls we have placed. You can easily visualize this in the case $d=2$, just think of the square $[-2,2]^2$, draw 4 unit discs, one centered in each quadrant, and then $B_d$ is the little disc in the center that is big enough to just hit the boundary of these 4 balls. The question is, what is the asymptotic relationship (as d goes to infinity) between the volume of $B_d$ and the volume of $[-2,2]^d$?

The answer is that $m(B_d)/m([-2,2]^d)$ goes to infinity! Most people will try to visualize this problem in $\mathbb{R}^2$ or $\mathbb{R}^3$ to get an intuition for the behavior, and just implicitly assume that $B_d$ is contained within $[-2,2]^d$. And it certainly is in those low dimensional cases. But when you actually compute the radius of $B_d$, you see that it's $\sqrt{d}-1$, and so $B_d$ is not even contained in in $[-2,2]^d$ for $d > 9$.

Answer by Erik Davis for Yet another 'roadmap' style request- a second bite of the cherry

2010-06-26T02:45:52Z

I'll just reiterate what Justin Curry said with a bit of personal anecdote.

Making yourself known to a tenured professor who can write you a strong recommendation is probably enough to get you a PhD position somewhere (in the US, UK or Europe).

This is basically how I got into a PhD program (with a fellowship, even!). My undergraduate GPA was 2.7, and although I did well in some of the more serious math classes, my transcripts were bad enough that I imagined I could get outright rejected from many places without much other consideration. I had done no research either. So I stuck around for an extra year, took some graduate classes, and most importantly got to know a few professors pretty well. It was mainly a matter of me making an effort to interact in class, and to go to office hours and ask questions. I don't mean questions like "I'm stuck on the homework, can you help?" but rather on strengthening results, or related ideas, something I'd read, etc. I also had gotten to know one professor via independent study.

As an undergraduate I had always been hesitant to talk to professors outside of class mainly because I felt that whenever I had a question, I just hadn't tried hard enough to answer it myself. Reasonable or not, that sort of attitude will not get anyone's attention, and you will miss out on a lot of ideas if you just try to learn everything by yourself. So talk to people, and don't be afraid of not knowing something. If you're smart enough to do a PhD and are putting in a legitimate effort, the professor will pick up on it. And they will have something to say about you in a letter beyond simply "_ took my class and got an A."

My advice: find a professor at a local university who is doing stuff that you are interested in. Go talk to them and see if you can meet with them once every week or two weeks for an independent study course. I've found that most seem to be fairly receptive to the idea. It's important to make two points: first, that you are serious about doing math, and second, that you are mathematically mature enough to handle independent study without being too much of a burden (in terms of time spent) on the professor. From what you wrote I imagine you are fine on both counts.

Answer by Erik Davis for What is an explicit example of a sequence converging to two different points?

2010-05-12T02:59:04Z

An easy, non-silly example (that is perhaps more appealing than the Zariski topology to a student at the level of someone asking this question) is simply to consider the space of real-valued integrable functions on $[0,1]$ with the pseudo-norm $\|f\| = \int_0^1 |f|$. The topology generated by the balls is not Hausdorff, an explicit example of a sequence converging to two points is simply the constant sequence $f_n = 0$, which converges both to the constant $0$ function as well as the function $f(x) = 0$ for $x \in [0,1)$, $f(1) = 1$.

While simply considered as a topological space, this really doesn't present any issues, because we may easily quotient to get a Hausdorff space. But while this is trivial from a topological perspective, and we don't lose any information about behavior in the psuedo-norm by quotienting to get a norm, quotienting like that is really quite a violent act as far as pointwise behavior is concerned. We now have to worry about things like sets of measure 0 piling up (on uncountable families) or, likewise, the stark realization that via our a.e. equivalence we improve the behavior of one topology (going from a pseudo-norm to a norm) at the expense of destroying another (from pointwise convergence to a.e. convergence we have abandoned the realm of topology altogether. A.e. convergence does not generally come from a topology!)

Answer by Erik Davis for Motivation for strong law of large numbers

2010-03-24T08:15:51Z

I think it is worth noting that even if real world systems are fundamentally finite (in which case the distinction between WLLN and SLLN gets a bit philosophical), history has shown that it is extremely useful to approximate the discrete with the continuous. Thus we consider limit theorems to approximate statistics of large samples, we consider continuous distributions to approximate complicated finite distributions, and we consider continuous stochastic processes in order to approximate finite ones (e.g. Donsker's invariance principle).

The examples of sequences that converge in probability but not a.s. might seem a bit contrived, but then again most engineers seem to allow such philosophical absurdities as "let $X_n$ be an infinite sequence of coin tosses". In this regard, maybe it is best to phrase the distinction between convergence a.s. and convergence in probability in terms that seem more qualitative and less analytic. For example, imagine you were presented a sequence of gambles, and you must take either all of them or none of them. There is a very significant distinction between knowing that your wealth converges a.s. to some deterministic value vs knowing that it converges in probability (to that same value). In the former case, you expect in almost all states of the world that if you play the game that your wealth eventually stabilizes. However, in the case of convergence in probability you could go bankrupt infinitely often. Yikes!

Answer by Erik Davis for A geometric interpretation of independence?

2010-02-26T05:49:13Z

This is a pretty trivial observation, but in that space the criteria for independence is that $(p\circ X, q \circ Y) = (p \circ X,1)(1,q \circ Y)$ for all measurable indicator functions $p,q : \mathbb{R} \to \mathbb{R}$ (or to abstract just slightly from the underlying space, $pp = p$ and $qq = q$ where multiplication is pointwise). I can't see any analogies to geometry from this form, but it seems clear that there is a fundamental difference from the sort of hilbert space geometry that you mentioned, since we are quantifying over a whole class of external objects (the indicator functions).

Answer by Erik Davis for Probabilistic Proofs of Analytic Facts

2009-12-18T10:21:28Z

I'm not sure how kosher it is for me to answer my question, but since there had been several comments about my original post I did not want to make any major edits to it. I've posed this question to my probability professor and he mentioned his favorite, from the paper "Triple points: from non-Brownian filtrations to harmonic measures." by Tsirelson. It's pretty far over my head, but it claims to have a probabilistic proof of (I'm quoting the description)

A conjecture by C. Bishop (1991) about harmonic measures for three arbitrary (not just regular) non-intersecting domains in Rn. Roughly speaking, trilateral contact is always rare harmonically (though not topologically).

This seems like it goes hand in hand with some of the above comments, where basically knowledge of things like hitting probabilities of brownian motion and similar things for other processes can assist in understanding the fine properties of various domains, useful to people in PDE and harmonic analysis.

Answer by Erik Davis for Ways to Synthesize Topics in Linear Algebra

2009-11-20T07:26:34Z

One of the tough things about linear algebra is that it is just so damn useful for so many people that courses end up having a lot of compromises. And because of its pervasiveness, there are several good perspectives from which one should view the material.

For example, it's one of the first math courses to really teach algorithmic thinking. It's amazing to me just how much of elementary linear algebra you can prove just with Gaussian elimination. Various modifications of the classical algorithm are used to solve some heavy duty real world problems. Another example (although not so pervasive as Gaussian elimination) is the Gram-Schmidt process.

But I understand completely where you are coming from. Linear algebra is not just a set of tools to compute certain things -- it's a whole new way of thinking. To me, linear algebra makes a lot of sense when you think of it as capturing some basic ideas of geometry. Given an inner product, you have some very natural notions -- spheres, lines, hyperplanes, ellipsoids, etc. Linear transformations can be naturally thought of as geometric operations -- shears, rotations, inversions, etc. Some of the structure theorems for linear transformations have a geometric interpretation. One interpretation of the spectral theorem is if you have a symmetric operator A on a finite dimensional real vector space then this gives you a quadratic form f(t) = <t,At>. This function, restricted to the unit sphere, takes on a maximum value f(p) for some p, and it turns out that p is an eigenvector of A with eigenvalue f(p) (which is in fact the largest eigenvalue). You can get the next eigenvalue/eigenvector pair by considering the same maximization problem restricted to the orthogonal complement of f(p), and then keep repeating this, etc. This really blew my mind the first time I saw it, I'm pretty sure it's in Lang's Linear Algebra book. Another example of geometry coming in is the SVD... given any linear transformation, the image of a unit sphere under this transformation is an ellipsoid, and the lengths of the principal semi-axes are the singular values. Check wikipedia for the rest.

As for your remark about linear functionals, I'll chime in and say that one can naturally think of them as somehow measuring something. For example, the Riemann integral over some fixed set is a linear functional (on the vector space of riemann integrable functions). For a slightly different example, the Riesz representation theorem says that in any Hilbert space (complete inner product space. In finite dimensions, real or complex vector space have such a structure) a linear functional is of the form f(x) = <x,y> for some vector y, and intuitively you can imagine this as measuring (up to some scalar) the magnitude of vectors in the direction of y.

Answer by Erik Davis for Which mathematicians have influenced you the most?

2009-11-15T19:06:53Z

Gian-Carlo Rota. I really wish I could pinpoint the moment that I came across some of his work, but I can't. And I've only just begun graduate work so it's impossible to be really honest about what sort of impact he has had on me... only time can tell.

But nonetheless, his writings are truly inspiring. It's tough to describe the wonder they have given me. Rota began as a functional analyst (PhD under Jacob Schwartz, of the Dunford & Schwartz fame) and moved over to algebraic combinatorics in the 1960s. One of his first papers that has stuck in my mind is "The Number of Partitions of a Set" in which he applies the techniques of the so-called 'umbral calculus' (which he also worked to rigorously formulate) to beautifully establish some combinatorial results. He's credited as setting the field of algebraic combinatorics on solid ground via his seminal papers On the Foundations of Combinatorial Theory. But it's not just the technical results -- his writing is just plain fun to read.

Given my personal interests, I really appreciate that although Rota did so much work in combinatorics he always seemed to lean back towards his roots in functional analysis & probability. In fact, his goal to find the true nature of classical results in analysis and probability led him to a great deal of good work in combinatorics, e.g. his work on the Rota-Baxter algebra inspired by his ambition to understand "the algebra of indefinite integration", and his work on the foundations of probability with the ambition to understand the middle ground between the discrete and the continuous. Moreso than most people he is willing to put his position out there and speak about mathematics rather than just speak mathematics. A great example of this is his book "Indiscrete Thoughts" -- definitely worth reading. You may not agree with many things he says but it's wonderful to be allowed a glimpse into the mind of a man such as Rota.

Answer by Erik Davis for Reading for finite Fourier Analysis

2009-11-15T18:13:09Z

Although this question has been answered, I'd like to chime in that if you have any interest in probability it might be worth checking out Harmonic Analysis on Finite Groups by Ceccherini-Silberstein, Scarabotti, and Tolli. It does cover the basic techniques of fourier analysis on finite abelian groups and delves into some representation theory in the nonabelian case. The goal is perhaps slightly different from the other books... this book has in mind the development of these tools for the study of random walks on finite groups and other finite markov chains.

Here's a simple example problem that I find both interesting and compelling. Imagine you have a deck of cards, with some deterministic initial configuration. We define an elementary shuffle to be the result of you independently selecting two cards from the deck (with uniform probability measure on the cards) and then swapping them. How many elementary shuffles will it take to make the deck "sufficiently random"? It's clear that if you only perform one elementary shuffle the distribution on the set of possible decks (all 52! of them) is not at all uniform, since you have at most changed 2 cards in your initial configuration. But it seems intuitively true that if you do enough elementary shuffles then the distribution on the set of possible decks should approach uniformity (i.e. in the variation norm). But how long does it take? This problem was solved by Persi Diaconis (and someone else whose name escapes me) using tools of representation theory. It's much simpler in the case where your group is abelian, in which case fourier analysis is good enough.

Btw, the most interesting thing to me (as someone with a curiosity for probability) is not just the quantitative estimates that can be achieved using these tools, but the fact that there is the so called "cutoff" phenomena. That is, not all elementary shuffles are made equal; there's a threshold of a certain number of elementary shuffles at which point the next few shuffles have a much greater impact on the variation distance from the uniform distribution than the preceding shuffles. In essence, if you do a few shuffles you randomize some, but you hit a certain point where a few more are going really going to be doing all the work. Weird! Search google for "cutoff phenomenon" and the first link gives some discussion of this (sadly, I don't have enough points to include two hyperlinks in a post)

Anyways, the book is worth looking at. If only the first chapter.

How should one approach tropical mathematics?

2009-11-05T08:04:53Z

Let me preface this by saying that my background is pretty meagre (i.e. solid undergrad). However, a few months ago I came across this paper which presented an idea that struck me as really remarkable. One can develop a theory of analysis of functions taking values in an idempotent semiring (e.g. the max+ algebra), which happens to be naturally suited towards some traditionally nonlinear problems. Under this formulation (specialized to the case of max+), the integral of a good function corresponds to the supremum, the Fourier transform roughly corresponds to the Legendre transform (!), and it seems that one can develop a theory of "linear" (e.g. in terms of the max+ operations) PDE analogous to the traditional linear theory (!!). For example, the HJB equation is a nonlinear first order PDE, but linear in the max+ sense of the word. This all blew my mind, but after trying to read a few more papers on the subject I decided to put it on the back burner for later thought.

Then, a few days ago I was reading something written by Gian-Carlo Rota in which he makes a remark about developing an "algebra" for multisets. I guess distributive lattices model the "algebra" of sets well enough (in fact there is Birkhoff's theorem), but the quantitative aspect of multisets make this seem inappropriate. So just playing around a bit, I realize that if one models multisets on elements in X by functions from X to the nonnegative integers (the multiplicity), then multiset union corresponds to pointwise addition and multiset intersection corresponds to pointwise min. The min+ algebra on the nonnegative integers! Perhaps this points in the direction of why I think of tropical mathematics as something of interest to people in algebraic combinatorics (maybe this generalization is wrong).

Ok, sorry for that ramble. Essentially, I have 2 questions. First, aside from references to "dequantization", how should I envision the role of tropical mathematics? My lack of background makes it hard for me to get an idea of what is going on here (especially on the geometry side of things), but it seems like there are some big ideas lurking around.

Second, if I wanted to learn more about this stuff, what would be the best route to take? What expository papers should I look at / save for later? It's a bit intimidating that it seems like one needs background in algebraic geometry before one can seriously approach such ideas, but maybe that's just the way it is.

Comment by Erik Davis

2010-10-30T17:21:56Z

Do you not have enough reputation IRL to ask your professor or a classmate?

Comment by Erik Davis

2010-06-29T05:59:36Z

That was what I was suggesting, although in my case I was enrolled as a student.

Comment by Erik Davis

2010-05-03T21:56:49Z

Although these comments are months old, I'd like to chime in anyways and say that a lot of the criticisms people have about Rudin's choice of topics sort of disappear when you take his books together as a 3 volume course. With that in mind, his choice for chapter 2 of his R&C Analysis, which presents the Riesz theorem as the way to construct measures, makes sense, because in his undergrad book he already spent a chapter building lebesgue measure on R^1. Likewise, his choices in Functional Analysis are justified by the chapters on Banach, Hilbert space, & Banach algebras in his R&C Analysis.

Comment by Erik Davis

2010-04-15T01:01:16Z

Bill, would you mind elaborating? As someone not particularly familiar with either field, I can imagine that by combinatorics being "discrete functional analysis" you mean e.g. generating function methods, or perhaps the general ambition of associating some sort of linear operator to combinatorial objects (e.g. adjacency matrix). But what do you mean by functional analysis being applied combinatorics.

Comment by Erik Davis

2009-12-18T10:42:21Z

This looks excellent! Thanks!

Comment by Erik Davis

2009-12-18T03:11:10Z

Yes, this probably was not the best choice of example. And it's not so much that the result is technically difficult or unexpected (I don't think the weierstrass approximation theorem is surprising to anyone either), but rather I just liked the construction involved.

Comment by Erik Davis

2009-12-18T01:15:15Z

Yes, I have a vague feeling for that but I didn't speak of it only because I am not familiar with most of the actual technical results along that line. But it certainly would be a great example.

Comment by Erik Davis

2009-11-23T03:28:38Z

re: Fomenko, you're thinking of Shiryaev's "Probability"