User brian rushton - MathOverflow

Discrete Morse theory and chess

2013-05-04T03:44:11Z

There are many mathematical objects that are similar to groups and Cayley graphs of groups but lack homogeneity in some sense. Graphs of webpages with edges corresponding to links are one example. One long-studied example is chess. Some moves have inverses, and others do not. If we create a graph of all positions, it is certainly not homogeneous, and many methods developed for analyzing groups fail miserably (for instance, the graph is finite, so is delta-hyperbolic, but this gives no helpful information).

On the other hand, Morse theory is designed to help one study complex structures by picking out the points of greatest interest, ie the critical points. It has been used in several discrete settings such as video compression to help sort through mounds of intractable data.

My question is, has a version of discrete Morse theory been used to analyze chess? For instance, the critical points would perhaps correspond to positions with a local maximum or minimum number of moves; the absolute minima represent checkmates, the maxima represent positions with a lot of freedom.

Because chess is so well studied, I wonder if this hasn't been studied before. Does anyone know of a reference where Morse-like ideas were used to analyze chess?

How large is this "algebra" of defining graphs for Right-angled Artin groups?

2013-03-13T15:53:45Z

As part of my research, I have been trying to construct a spherical space at infinity for every right-angled artin group. I've been able to work it out for a certain class of defining graphs. I'd like to know how large this class is (I.e. does it consist of all graphs satisfying a certain invariant equation?), but I have very little graph theoretical background.

The class of graphs is invariant under disjoint union, join (connecting every vertex in one graph to every vertex in another), and the operation of identifying a single vertex in two disjoint graphs.

The "generating set" consists of all graphs not containing an induced square or an induced subgraph consisting of two triangles identified along a single edge (equivalently, it is the set of all graphs where every four-cycle bounds a tetrahedron). This set includes all trees and all graphs without 4-cycles, as well as all complete graphs.

My hope is that all or many hyperbolic 3-manifold groups virtually embed into RAAG's with such a defining graph. Some or all surface subgroups embed into such RAAG's (since any RAAG with a defining graph with an induced 5-cycle contains a surface subgroup). Thanks for your help!

Edit: I forgot to mention that RAAG's are subgroup separable iff their defining graphs have diameter at most 2 and contain no induced square.

Do quasi convex hyperbolic subgroups remain quasi convex after adding redundant generators?

2013-04-24T22:21:28Z

We know now that hyperbolic 3-manifolds virtually embed into right-angled Artin groups as quasiconvex subgroups. Also, quasiconvexity depends on the generating set.

I have been constructing a space at infinity for right-angled artin groups where the boundaries of quasiconvex hyperbolic subgroups will embed in a natural way; but to construct it, I've been forced to add all redundant generators of the form $b=a_1...a_k$, where all if the $a_i$ are distinct commuting generators in the standard generating set for the RAAG (they can also be unversed of generators). This is just adding in all 'diagonal' generators, and corresponds in free abelian groups to changing from an $L^1$ metric to an $L^{\infty}$ metric.

My question is, will this make some quasi convex subgroups no longer convex? In the $\mathbb{Z}^2$ case (generated by $a,b$), I think that the subgroup generated by $a$ is quasi convex before adding the generators $ab$, $ab^{-1}$, etc. So my final question is, will non-elementary hyperbolic quasi convex subgroups stay quasi convex after adding in these generators?

Edit: the easiest example of a non-elementary hyperbolic subgroup of a RAAG is the following: take the pentagon RAAG generated by $a,b,c,d,e$. Then the subgroup generated by $ab^{-1},bc^{-1},cd^{-1},de^{-1}$ is a two-holed torus group with standard relations.

Why isn't $\langle x,y,z|xyzx^{-1}y^{-1}z^{-1}\rangle$ a hyperbolic surface group?

2013-04-28T02:04:53Z

The group mentioned in the title, $\langle x,y,z|xyzx^{-1}y^{-1}z^{-1}=1\rangle$, is in between the torus fundamental group $\langle x,y|xyx^{-1}y^{-1}=1\rangle$ and the two-holed torus fundamental group $\langle x,y,z,w|xyzx^{-1}y^{-1}z^{-1}w^{-1}=1\rangle$.

It is not the hexagonal presentation of the torus because the homology is not the same (gluing up a hexagon with that pattern gives you two vertices instead of one, giving you only two loops in the one-skeleton, so this is not the torus group).

Its Cayley graph can be realized as an infinite tiling of hexagons, each of which meet six to a vertex.

Such a tiling can be embedded in the hyperbolic plane, making the Cayley graph quasi-isometric to hyperbolic space, which means that the group is delta hyperbolic with a circle at infinity, implying that the group is Fuchsian, by the work of Gabai and others.

So it has a finite index surface subgroup. But this group is a subgroup of the RAAG with defining graph the diamond graph, I.e. $F_2\times F_2$. This can be seen by letting $a,b$ generate the first free group, $c,d$ generate the second subgroup, and letting $x=ab^{-1},y=bc^{-1}$, and $z=cd^{-1}$.

*Edit:*I meant to say that $a,c$ generate the first group and $b,d$ generate the second.\

So this implies that the diamond graph contains a hyperbolic subgroup. But in all the RAAG references, they say that RAAG's contain surface subgroups if they contain 5-cycles. So why does it seem as if a four-cycle (the diamond graph) contains a surface subgroup?

Untwisting Heegaard diagrams

2013-04-17T21:18:51Z

Most Heegaard diagrams contain many rectangles, for instance from loops that circle around one of the handle disks. You can always `twist' a Heegaard diagram to get more and more rectangles (as in page 5 of this paper). Can one reverse this process to eliminate rectangles?

My real question is, is there a systematic way of constructing Heegaard diagrams without rectangles?

I am interested in Heegaard diagrams without prismatic circuits of length $\leq 4$; in particular, such diagrams can have no rectangles. I'm interested to know how common such Heegaard diagrams are, so I'm asking this question as a first step.

Great mathematics books by pre-modern authors

2013-04-19T02:44:27Z

Last summer, I read Euclid's Elements, and it was an eye-opening experience; I had assumed that three thousand years' difference would make the notation incomprehensible and the reasoning alien, but his proofs were beautiful; I had never experienced synthetic geometry (at least since middle school), and it was very enjoyable, especially his 3-dimensional geometry and the classification of platonic solids.

The experience made me realize that older math books could be worthwhile to study; for instance, I've heard that Euler wrote some incredibly popular calculus books, and that others (like Maclaurin and L'Hopital) wrote popular textbooks.

What math books from before 1900 (or from the beginnings of newer areas like topology and category theory) have you read and enjoyed? Are there any you would recommend?

Would a closed universe with special relativity violate causality? Does the universe have to be simply connected?

2013-04-02T16:06:42Z

This question may be more appropriate for physics.stackexchange.com, but it would be helpful to get feedback from experts in Minkowski geometry.

The classic twin paradox is a false thought experiment trying to disprove special relativity. Special relativity says that an observer at rest watching a passerby at a high velocity will see the other person's clocks running slower. However, relativity also says there is no preferred frame of uniform motion, so the passerby sees the clock of the original observer running slow. So if a twin leaves the earth at a high speed and returns, leaving her sister on earth the whole time, both should find the other younger, a contradiction.

This is resolved in flat, open spacetime by the fact that the passenger twin must accelerate to leave and return, and acceleration is a preferred frame in the sense that the laws of physics are different for an accelerating person.

Now, though, imagine a closed universe (I.e. one with closed geodesics). In this universe, two objects in relative uniform motion will encounter each other repeatedly. Even if a twin must accelerate to get into uniform motion, she will pass her sister on earth over and over again if she keeps on a fixed closed geodesic. Now both frames are equivalent, and so time is slower for both observers. Thus, past and future are not well-defined, and causality is violated.

Is there something wrong with this reasoning? Is there any way to handle special relativity and a closed universe so the above paradox does not happen?

Edit: For geometrists, I'm really asking if the invariant quadratic form becomes poorly-behaved if we take a quotient of $\mathbb{E}^{3,1}$ by a proper action of a subgroup of the Lorenz group.

Edit: By closed universe, I meant a universe compact in space dimensions for some observer. By a poorly behaved quadratic form, I was just thinking of how proper time is the root of the quadratic form for events with time like separation, so any paradox with proper time is an inconsistency with the quadratic form.

Answer by Brian Rushton for How large is this "algebra" of defining graphs for Right-angled Artin groups?

2013-03-28T02:09:12Z

This is not a complete answer, but after tlking to some people at a comference about this, the only virtual embeddings we could think of explicitly are related to reflection groups.

Andreev's theorem (or Rivin's extension) characterizes right-angled hyperbolic polyhedra; in particular, they have trivalent boundary graphs (I think that the only other characteristic they have is that they lack prismatic circuits of size less than four). The reflection group is a right angled coxeter group whose defining graph is the dual graph of the polyhedron's boundary graph. There is a finite orbifold cover that is a manifold, and so these manifolds virtually embed into these right angled coxeter groups (one of the comments mentioned this kind of embedding).

Since the defining graphs are dual to trivalent graphs, they consist of triangulations of surfaces, which contain nothing but diamonds.

For my research, RACG's and RAAG's have identical subdivision rules, so diamonds may be more common than I thought.

How does hyperbolicity of space time affect our lives?

2013-03-15T03:33:34Z

My main research has been in hyperbolic geometry and geometric group theory. I always thought that the only real "application" of my work was that the universe is a 3-manifold.

But recently I found out that hyperbolic 3-space arises in a natural way from relativity: according to the work of Einstein and others, there is a (3,1) quadratic form on space-time that is invariant under transformations. In the Riemannian pseudometric obtained from this form, the "sphere" of radius -1 is a hyperboloid; the pseudo metric on this hyperboloid (or on one branch of it) becomes a real metric, making it a copy of hyperbolic 3-space.

I found this very exciting, because it meant that my research applied to real life. But now, I've had difficulty seeing exactly how it applies. The physical interpretation of the hyperboloid is that it is the set of all points in spacetime that an observer starting at the origin can reach in one unit of their own, "proper" time. It is difficult to imagine the physical meaning of the hyperbolic metric.

That leads into my question. What are the physical meanings of the basic tools of hyperbolic geometry? For nstance, what does the thin triangles condition say about spacetime? Do the existence of closed hyperbolic 3-manifolds imply the existence of spacetime universes with bounded space coordinates? Thanks for your help!

Covering maps in real life that can be demonstrated to students

2012-12-06T01:57:41Z

Edit: I've really enjoyed everyone's examples (especially the pictures!), but I was mostly looking for a general theorem. For instance, a similar statement to mine is, Can the mapping cylinder of every finite-sheeted covering map of a finite graph be embedded in $\mathbb{R}^3$? This is the level of generality I'd be most interested in. On second thought, and after reading the comments, I think a community wiki list of interesting examples (like those below) would be more helpful to other instructors. If you have any more, please post them!

I recently taught my students about covering maps of topological spaces, using the classic example of the real line winding onto to the circle. This covering map can be exhibited in real life (well, not all of it, but a representative chunk). All other covering maps of the circle really can be exhibited with string. Other things that can be exhibited include winding the upper half plane onto the punctured plane, although this is equivalent to the real line covering the circle.

After some thought, it seems that some graph coverings (like a double cover of the figure eight) can be realized in real life, while it seems that nontrivial surface coverings cannot be exhibited unless the circle has boundary. My question is,

What is the class of covering maps of graphs or two-dimensional CW-complexes that can be realized in 3-space, i.e. so that there is a homotopy of the covering space in $\mathbb{R}^3$ onto the base space which is an isotopy for $0\leq t< 1$ and is the covering map for $t=1$?

(This is my working definition of "real life homotopy", since we allow things to touch but not pass through each other. There may be a better definition.)

Topology, the board game

2013-03-13T00:35:48Z

Edit: I am reposting this question fom math.stackexchange.com; there may be some professors here who have more experience teaching topology.

This is a math education question that I've been thinking of when taking and teaching topology.

For a few years now I've had an idea for a board game that could help teach students topology. However, I've had trouble working out the specifics, and wondered if the community would be able to help. Of course, this may be closed for being off topic, but if so, I'll post a link where we could continue the conversation elsewhere for those interested.

Setup: Basically like battleship. The playing board would be squares of transparent paper (or chessboards, go boards, etc.).

Players secretly place markers (which are circles) indicating where gardens are (or mines, etc.) on their paper, hidden from the other player.
A card is then flipped over selecting a topology.
Players then send five agents to the other player's board; the agents are points. If the points are placed directly in the garden, the player gets his opponents garden. If not, each agent has the option of moving (in a topological path) or of setting off a bomb. Bombs explode to form an open set; any agents or gardens caught in the bomb perish (so you may have to sacrifice your agents). Players describe the shape of the bomb, and their opponent tells them if they've hit the hidden gardens.
At the end of the round, players gain one point for each garden they possess and lose two points for each agent lost.

Possible topologies include:

-Discrete topology: Bombs can take any shape, but agents cannot move.

-Indiscrete topology: Agents can move anywhere, but the only possible bomb is a total nuke.

-Finite complement topology: Agents can still move anywhere, but bombs can miss the agents.

-Dictionary order: Most interesting if agents aren't allowed to move through each other.

-Product topology: Each direction is one of discrete/indiscrete/finite complement/standard

-Metric topology: In metric topology, we require bombs to be formed of metric balls. Then we have the standard metric, the square metric, etc.

-Torus topology: Identify opposing edges (could do other surfaces, use orientation perhaps)

-Subspace topology: Players place an overlay on their boards marking out a subset (like topologist's sine curve, etc.) and then flip over another topology to combine with the overlay.

Now, I think this could be made more interesting. Possible variants could include that agents don't find gardens when placed in them until they do a "search" which means they can detect gardens in a compact connected set containing them (but the test only detects if there is at least one garden, so if the only compact set in the whole space is the space itself, the test is always positive).

I'm sure you all could think of many improvements and better rules. I think this could really help people learning topology for the first time. I would have loved to had it for my students this last semester. What ideas do you have to incorporate other parts of topology (like connectedness or algebraic topology) and how could scoring and set up be improved? In other words, how could this be made playable with real strategies? I don't want this to end up like Quidditch. Thanks, and happy Boxing Day!

Edit: I forgot to mention, I don't know whether it would be better to do analog (paper and pen) or discrete (pegs on a go board).

The human body's random number generator

2012-12-22T16:58:53Z

Edit: Steve and Tom have provided a great answer and a great comment about related topics that I think provide a good place to start reading. For now, though, I will leave the question open in case someone can provide a fuller answer in the future. End Edit.

I remember learning in microbiology that the human body generates antibodies using a random process so that an enormous variety of antibodies can be produced with a simple genetic code.

Now that I'm trying to learn more about random processes, I find this more interesting than I used to. Has anyone developed a mathematical model for how the genetic code generates these random antibodies? Clearly, we'd like the process to be ergodic, so that as many antibody varieties as possible can be produced. The main reason that I'm interested is because there are so many ways that random and pseudo-random numbers are generated, and it would interesting to see what the body "thinks" is a good random antibody generator.

I did a quick google search, finding links such as this paper, but they seem to assume that antibodies are generated randomly without explaining the mechanism.

So, does anyone know if there is a mathematical model for the process that generates random antibodies?

And, Merry Christmas!

Answer by Brian Rushton for Proofs that inspire and teach

2012-12-29T03:47:41Z

I feel that many of the proofs in Munkres' Topology are like this; some people might say he takes too much time and goes into too much detail. But his exposition of the proof that all subgroups of free groups are free takes an entire chapter, is well organized, and leaves with the feeling that "I could do that". The same is true for many of his lemma/theorems leading up to the Jordan Curve theorem, as well of his proof of Urysohn's lemma and the Tychonoff theorem.

Answer by Brian Rushton for Relating the angle between two vectors to max and min eigenvalues

2012-12-26T01:47:58Z

This is only a partial, heuristic answer, but if you let $A$ be the square root of $\sigma$, then $\cos(\omega)$ is equal to $\frac{\alpha' \alpha}{\sqrt{\alpha' A^{-1}\alpha}\sqrt{\alpha' A\alpha}}$. If we let $\alpha$ be a unit vector, the top will always be one, and the bottom will be how much $A^{-1}$ expands $\alpha$ (which is at most the inverse of the smallest eigenvalue) times how much $A$ expands $\alpha$ (which is at most the largest eigenvalue). Just feeling it out, you probably want to add the minimum and maximum eigenvectors together since it will help make each factor in the denominator small.

Geometrically, though, the formula makes a lot of sense. If the matrix is diagonalized, we are just expanding or contracting along each axis. Imagine a 2-d version of this problem, with the x-axis expanding and the y-axis contracting (or x expanding faster than y, etc.) If we take $\alpha$ to be along either axis, its image under the transformation points in the same direction. Putting the vector exactly between the two (at a 45 degree angle) maximizes the amount that it bends away from y and towards x.

In higher dimensions, we can do the same trick along each pair of axes, but it is maximized when the two axes are as different as possible.

Note: to other readers, the OP is trying to minimize the angle between a vector and its image under a fixed positive-definite symmetric matrix.

Answer by Brian Rushton for Intuitive pictures in characteristic p

2012-12-22T04:15:53Z

This is not nearly as nice an example as the others, but I always imagined the line in characteristic five geometry as a countable set of points that glow like blue Christmas tree lights vaguely in the shape of a narrow paraboloid, with 0 at the vertex, with 1, 2,3, and 4 at the next "height", with the quadratic "irrationals" next, etc. although the makes it seem like each field of order $p^n$ contains the field of order $p^{n-1}$. Like in Carnahan's answer, I imagine the Frobenius automorphism shuffling around everything in each fixed ring. Finally, I imagine the Zariski topology as a glowy light filling in the paraboloid representing the forces that each point exerts on all others; it's constant everywhere, as in the Zariski topology, there's no real sense of distance.

More complicated varieties I imagine as a double cone with glowy lights (two Christmas trees!) or as the paraboloid distortedt to have self-intersections in some of the lights. something like the galactic gravity simulation or spherical pendulum in this website

The PDE $u_t=u_{xx}-u_{yy}$: The simplest linear second-order PDE that isn't elliptic, parabolic, or hyperbolic.

2012-12-08T16:18:01Z

I know that there have been several questions on here and stackexchange about linear PDE's which don't fall into the standard classification, but I had a more focused question which I haven't seen answered. The PDE $u_t=u_{xx}-u_{yy}$ (or, equivalently, $u_t=u_{xy}$), is the simplest linear second-order PDE that is not elliptic, parabolic, or hyperbolic. Its time-invariant solutions are solutions to the one-dimensional wave equation.

My question is,

How does this PDE compare to the standard parabolic and hyperbolic PDE's in the following categories:

Fundamental solution: is there an integral solution which is a convolution with a fundamental solution?
Smoothness: are solutions infinitely smooth or does the smoothness depend on boundary conditions?
Propagation speed: infinite or finite?

I only recently read Evan's PDE book, and the only question I really took a crack at was the first. I looked for a solution involving exponentials in t, but I couldn't find one. I am interested in this question purely from a classification standpoint. Thanks!

Edit: As the comments below indicate, there can be no general solution with arbitrary initial conditions analogous to that for parabolic or hyperbolic equations. Also, solutions need not be infinitely smooth. Since this answer was pieced together from the comments, I'm making this community wiki, in case anyone would like to add to it later.

Answer by Brian Rushton for Journals and other sources with "easy reading" papers ?

2012-12-04T02:44:22Z

One enjoyable math article I read recently was Erica Klarreich's exposition of the virtual fibering conjecture. I would highly recommend this and other articles at this link to the Simons Foundation website. They use great diagrams and good analogies without shying away from difficult subjects.

Horrible sets and blowups in Hubbard's Teichmuller theory

2012-11-13T03:30:51Z

Edit: I can rephrase this question this way: When blowing up every point in the $x$-axis in $\mathbb{C}^2$ by means of an inverse limit of finite blowups, how can anything be 'left over'? The horrible set described by Hubbard must consist of points on the axis that are not blown up, but every point on the axis is blown up on the way to the inverse limit, since the index set is a directed set. It's not like the inverse limit only considers finitely many blowups at a time; every point in the inverse limit lives in every blowup. Why is there a horrible set?

Original Question:

I've had this question for some time. In Hubbard's Teichmuller theory book, on page 9, he describes an ugly complex 2-manifold that is not second countable. He constructs it by taking $\mathbb{C}^2$ and blowing up every point along the axis $\mathbb{C} \times 0$. More specifically, he considers all blowups of finitely many points along this axis, and takes their inverse limit under the natural projection maps from one blowup to another which has a strictly smaller subset of blowup points. He notes that there is a natural map $p$ from the blown-up space to $\mathbb{C}^2$.

He denotes $p^{-1}(\mathbb{C} \times 0)$ by $Y$ and claims that $Y$ consists of one copy of projective space for each point of the complex line plus a 'horrible set'. Here's my question:

Where does the horrible set come from?

Because every point in the inverse limit is given by $a=\mathop{\Pi} \limits_{\alpha \in J} a_\alpha \in \mathop{\Pi} \limits_{\alpha \in J} X_\alpha$ with $p_{\alpha\beta}(a_\alpha)=a_\beta$ whenever $\alpha<\beta$ (here the $X_\alpha$ are all the blowups with partial order given by inclusion of the blow up points and the p maps are the natural projections). So, any point in the inverse limit has a coordinate $a_0$ in the non-blown up space $X_0=\mathbb{C}^2$ (the minimal element in the ordering). There is an $\alpha$ corresponding to the blowup of the point $a_0$, and in $X_\alpha$, we must have that $a_\alpha$ is some element of the copy of projective space created in the blowup. This means that our point is in the 'nice' set, and not in the horrible set. So where does the horrible set come from?

Example as written in Hubbard

A 2-dimensional complex manifold that is not second countable

We will describe a connected complex manifold of dimension 2 that is not second countable. This manifold is a close analog of Example 1.3.1 [which was the classic non-second countable surface], but the elementary "cut and past" approach used there doesn't work so well in higher dimensions, so we will instead use a description in terms of blow-ups. (For blow-ups, see Hatshorne, Shafarevich; see page 30 of Thurston's Three-Dimensional Geometry and Topology for an informal introduction. But readers who don't know about blow-ups can skip this example; it has no further applications in this book).

In $\mathbb{C}^2$, we will blow up every point of $\mathbb{C}\times${0}. More specifically, for any finite subset $Z\subset \mathbb{C}$, we denote by $$\widetilde{\mathbb{C}_Z^2}$$

the blow-up of $\mathbb{C}^2$ at all the points of $Z$, and set $X:=\mathop{\lim}\limits_{\mathop{\leftarrow}\limits_Z} \widetilde{\mathbb{C}_Z^2}$, where the finite subsets are partially ordered by inclusion. (For inverse limits, see Hatcher). There is a natural map $p:\widetilde{\mathbb{C}_Z^2} \rightarrow \mathbb{C}^2$.

This space $X$ is not a manifold, the inverse image $Y:=p^{-1}(\mathbb{C}\times${0}) consists of the disjoint union $Y_1$ of uncountable many copies $\mathbb{P}^1_z$ of $\mathbb{P}^1$, one for every $z\in \mathbb{C}$, and some horrible set $Y_2=Y-Y_1$. The set $Y_2$ is not closed; it accumulates on exactly one point of each $\mathbb{P}_z^1$, namely, the point corresponding to the horizontal direction through $z$.

Examples where adding complexity made a problem simpler

2012-11-24T23:08:39Z

I can think of a few situations in math where a problem becomes easier or an object becomes simpler when some complexity is added. Examples:

$S^n$ is never contractible, but $S^{\infty}$ is.
The vanishing viscosity method of PDE's.
Higher-dimensional topology as opposed to low-dimensional topology (in some specific cases)
Singular homology as opposed to simplicial homology
Cube complexes as opposed to 3-manifolds

etc.

What other examples are there where a more complex object is simpler to analyze than a 'simpler' object? I realize that you could say that if it is easier to analyze, then it is less complex, so let me restate it this way:

What examples are there where one object seems much more complicated than another, but in fact has a simpler structure?

I've been thinking about things like the Ising model for magnetic phase changes and also about Navier-Stokes; perhaps the simplifications used to derive them make them harder to analyze in the end.

Answer by Brian Rushton for Non-rigorous reasoning in rigorous mathematics

2012-12-01T00:16:44Z

I feel that almost all of math is this way. One specific example is the Riemann mapping theorem for annuli (which is equivalent to the standard Riemann mapping theorem). Riemann is said to have conceived of the idea by imagining current flowing from the inside of an annulus to the outside. The current flows and equipotentials would form an orthogonal set of coordinates which could be "stretched out" to form a perfect cylinder. Riemann's first proof of this theorem was shown to have an error, but he reportedly commented that it didn't matter, because he knew the theorem was true anyway. (Most of this comes from Jim Cannon's paper The Combinatorial Riemann Mapping Theorem).

Answer by Brian Rushton for A consequence of convexity

2012-11-29T13:32:51Z

You can use the triangle inequality to solve this by looking at each coordinate separately.

$F(x_0,y_0)-F(x_2,y_2)=F(x_0,y_0)-F(x_2,y_0)+F(x_2,y_0)-F(x_2,y_2)$ $\leq M_1(F(x_0,y_0)-F(x_1,y_0))+M_2(F(x_2,y_0)-F(x_2,y_1))$. Replacing $F(x_1,y_0)$ with $F(x_1,y_1)$ only increases the right side, and replacing both $x_2$'s on the far right side with $x_0$ only makes the right hand side larger by convexity. Finally, replace the last $x_0$ that we just added with $x_1$ without ncreasing the right hand side. This gives us $F(x_0,y_0)-F(x_2,y_2)\leq M(F(x_0,y_0)-F(x_1,y_1))$, where $M$ is $2\max(\frac{x_2-x_0}{x_1-x_0},\frac{y_2-y_0}{y_1-y_0})$. $M$ can also be the sum instead of the max, in which case we can drop the 2.

Edit: This argument doesn't work without additional assumptions; see the comments.

Answer by Brian Rushton for Application for Morse-Smale systems

2012-11-27T17:03:36Z

I know this is an older question, but since it may interest some, here are some papers about Morse-Smale theory applications:

This paper describes applications of Morse-Smale theory to sensor networks. It has great pictures, and describes how Morse-Smale theory allows one to avoid slow points in computer computations, among other benefits.
This paper describes applications of Morse-Smale theory to video segmentation. In part, it says,

In computer vision, detail has been often identi- fied with scale, and so-called scale-space approaches have achieved simplification by blurring. However, blurring obliterates small detail together with the boundaries of large regions. A more discriminating treatment of scale would instead eliminate small detail while keeping large parts crisply delineated. In this paper, we propose a representation of video that captures structure and affords flexible control of detail, without sacrificing crispness. Specifically, we represent structure through the so-called Morse- Smale complex of a scalar function f(x,y,t) associated with the video data, and we obtain a hierarchy of increasingly simple complexes through the process of topological simplification.

This thesis also describes how Morse-Smale theory can be used to simplify data storage.

All of these papers have references to other papers doing similar things. It seems like Morse-Smale theory has very practical applications to real-world issues!

The main ideas in these papers seem to be that having transverse stable and unstable manifolds gives a nice cell structure or helps us find saddle points more easily.

Answer by Brian Rushton for Can you see smoothness of the boundary of a convex body from its shadow?

2012-11-26T15:56:14Z

According to this article, in the case $d=3$, the boundary in the projection need not be $C^2$ even if the original boundary is $C^\infty$. This seems to leave open the $C^1$ case, though.

Eigenvalues of nonnegative integer matrices

2012-11-12T20:15:01Z

Edit I realized that the key piece of information that I need is question 1, and so I'd like to rephrase this post:

What are the possible eigenvalues of nonnegative integer matrices?

Any answer to this question would be appreciated and checkmarked.

Original Question:

My question is related to this question about integer nonnegative matrices but goes in a slightly different direction. Like the previous poster, my question comes from solving linear recursions (specifically, computing the discrete modulus of a product finite subdivision rule acting on a grid).

Given $A$ a square matrix with nonnegative integer entries and $v$ a column vector of the same dimension, we can use the Jordan canonical form to get a closed expression for $A^n(v)$. If we sum the entries of $A^n(v)$, we get a function of the form $f(n)=a_1 P_1(n)\lambda_1^n+...+a_kP_k\lambda_k$, where the $\lambda$'s are the distinct eigenvalues and each $P_i$ is a monic polynomial in $n$.

My question is, what are the possible values for the $a_i$ and the $\lambda_i$? In particular:

Can the $\lambda_i$ be any algebraic integer?
Can the $a_i$ be non-integers?
(My real question): Given an algebraic integer $\lambda$, can we construct two matrices $A_1$ and $A_2$ such that the ratio of their associated polynomials $\frac{f_1(n)}{f_2(n)}$ (where, as above, $f_i(n)$ is the sum of the entries of $A_1^n v$) has limit $\lambda$? The limit of such a fraction will be 0 unless the 'largest terms' of each polynomial have the same magnitude; my worry is that it would be impossible to get some algebraic integers in this way because they have Galois conjugates of equal or larger size. But it seems that the column vector $v$ might allow one to 'cancel out' unwanted eigenvalues. Is this possible? Is it even possible to get $\sqrt{3}$ in this way?

Thank you for your help! The first two questions seem like they would be easily answerable by experts in matrix theory, but google searches have led to nothing. I appreciate in advance your help.

An example of $f_1(n)$

Let $A=\left[ \begin{array}{cc} 1 & 2 \\ 0 & 2 \end{array} \right]$. It can be diagonalized as $A=\left[ \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right] \left[ \begin{array}{cc} 1 & -2 \\ 0 & 1 \end{array} \right]$. Now, let $v = \left[ \begin{array}{c} 2 \\ 3 \end{array} \right] $.

Then $A^{n} v= \left[ \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{cc} 1 & 0 \\ 0 & 2^{n} \end{array} \right] \left[ \begin{array}{cc} 1 & -2 \\ 0 & 1 \end{array} \right] \left[ \begin{array}{c} 2 \\ 3 \end{array} \right] = \left[ \begin{array}{cc} 1 & 2^{n+1} -2 \\ 0 & 2^{n} \end{array} \right] \left[ \begin{array}{c} 2 \\ 3 \end{array} \right] = \left[ \begin{array}{c} 3(2^{n+1})-4 \\ 3(2^{n}) \end{array} \right]$ . Adding all the entries of this matrix together, we see that the growth function $f(n)$ is $3(2^{n+1} + 2^{n})-4=9(2^{n})-4$.

Answer by Brian Rushton for Beautiful examples of arc-like continua

2012-11-14T04:12:19Z

Have you tried solenoids? Solenoids certainly seem like they would satisfy your definition. Also, Antoine's necklace is another likely candidate.

Edit: Sorry, I didn't realize you required it to be connected. Solenoids still work, but Antoine's necklace is out.

Comment by Brian Rushton

2013-05-04T20:33:12Z

Does this mean the Oiled-Macaroni constant is a renormalized feta function? Mmm... Greek food...

Comment by Brian Rushton

2013-04-29T18:10:20Z

That's true! But, looking at it again, I think it's too argumentative and subjective, so I'm deleting it.

Comment by Brian Rushton

2013-04-29T17:47:42Z

Great answer, and thanks for the comments from everyone! My embedding of $G$ was a typo, which I've corrected above. It seems like any such group with an odd number of generators in the same pattern will be a surface with a point identified, right?

Comment by Brian Rushton

2013-04-25T00:55:19Z

Great answer! I am indeed assuming number one. Your example answers the question. It seems to me that quasiconvexity will only be preserved if the subgroup is already generated by diagonal elements. Thanks for the care and time you took in your response! I had never heard of many of these equivalent conditions.

Comment by Brian Rushton

2013-04-19T01:59:56Z

@Scott Taylor: That paper is very interesting; thanks! I am really just interested in knowing more about combinatorial properties of Heegaard diagrams, so that paper is great.

Comment by Brian Rushton

2013-04-02T20:52:18Z

Thanks you, this answers my question completely (especially the linked article!).

Comment by Brian Rushton

2013-03-13T20:32:18Z

Thanks, Benjamin; I found this article almost immediately after reading your comment: arxiv.org/pdf/0909.4719v1.pdf. It's a good starting point!

Comment by Brian Rushton

2012-12-30T03:51:51Z

It's the second edition, very last chapter (or second to last). He shows that every covering space of a graph is a graph, and that all graphs have free groups as a fundamental group. I never went through it in class, and it is really short, but I read it this summer and liked it.

Comment by Brian Rushton

2012-12-29T21:42:37Z

What happens if you scale the numbers between 30 and 42, or some ther set? Do a and b change significantly?

Comment by Brian Rushton

2012-12-28T14:11:43Z

Although, I think we are applying the inverse of the matrix, so as we apply the matrix to the vector in (6) that is close to the bigger eigenvector, it gets shrunk in that direction and stretched in the other, making it twist a lot and apparently maximizing the angle.

Comment by Brian Rushton

2012-12-28T14:10:14Z

Equation 6 says that the vector whichs gets twisted the most is a weighted sum of the eigenvectors corresponding to the biggest eigenvalue and to the smallest. So, I was incorrect above; the vector that is 45 degrees between the two is not best; instead, you use a weighted sum (eq. 6) that is a little closer to the bigger eigenvector.

Comment by Brian Rushton

2012-12-22T20:27:41Z

I have to confess, after I wrote my previous comment, I realized that I accidentally voted to close while checking the previous vote to close. I didn't have enough reputation for this before. Sorry for my mess-up!

Comment by Brian Rushton

2012-12-22T19:33:44Z

I agree with those voting to close that this may not be the most appropriate forum for this question. Can anyone a suggest a better place to ask this?

Comment by Brian Rushton

2012-12-22T14:36:46Z

I came to it myself, but I think it's based on the Red Book of Varieties' picture of $\mathbb{Z}$[x].

Comment by Brian Rushton

2012-12-17T19:12:25Z

What about math that was once useful but now useless? Like all of the tricks engineers had to use to multiply using slide rules...