User jeff burdges - MathOverflow

Local curvature in a Cayley complex

2012-10-22T14:21:41Z

I'm curious about non-shperical regions in the Cayley complex of a hyperbolic group $G = < X : R >$ that one might reasonably consider "curved", but I haven't found much discussion of local curvature in a Cayley complex.

We could for-example look for curvature in the sense of the presentation's isoparametric inequality by asking what bubble-like regions determine the constant as follows.

We regard $\pi_2$ as a $\def\Z{\mathbb{Z}}\Z[G]$-submodule of $\Z[G]^R$ in the usual way. Let $|\cdot|$ denote the $l^1$-norm on $\Z[G]^R$ or $\Z[G]^X$. So $|\cdot|$ assigns an area to an element in $\Z[G]^R$ or a length to an element of $\Z[G]^X$. Also, let $\partial$ denote the Fox derivative sending elements of $\Z[G]^R$ to their boundary in $\Z[G]^X$. So $\pi_2 = \textrm{ker}\ \partial$.

Let $C_k$ denote the set of diagrams in $\Z[G]^R$ such that the minimum area obtainable by adding an element of $\pi_2$ remains larger than $k$ times its boundary length. $$ C_k = \{ x \in \Z[G]^R : |x+y| > k |\partial x| \ \ \forall x \in \pi_2 \} $$ $C_k$ is not a group under the module addition, but it's closed under both multiplication by $\Z[G]$, aka translation, as well as addition with elements of $\pi_2$. There are of course many elements of $C_k$ whose sum remains inside $C_k$ though; in particular $\pi_2$ is contained inside $C_k$ for all $k$.

I'm curious whether these $C_k$ are finitely generated with respect to the module addition and multiplication by $\Z[G]$, as well as whether $C_k = \pi_2$ for $k > n$ for some $n$. It's worth noting that finite generation up to $\Z[G]$ holds for both $C_\infty = \pi_2$ (previously) and $C_m$ where $m$ is the reciprocal of the largest relator length are both finitely generated.

Second homotopy group of Cayley complex

2012-06-20T17:21:24Z

Is there a good reference for information about the second homotopy group of the Cayley complex or Presentation complex of a finitely presented group, especially a hyperbolic group? I'm looking for an argument that the second homotopy group of the Cayley complex of a hyperbolic group $G$ is finitely generated as a $G$-module in particular, but I'd welcome other interesting starting points around the second homotopy group of the Cayley complex too.

Asymptotics of the number of required Dehn relators in hyperbolic groups

2012-04-16T13:59:13Z

If $G = \langle X | R \rangle$ is a $\delta$-hyperbolic group presentation, then Dehn's algorithm provides a linear time solution to the word problem, but the linear constant is horribly exponential in $\delta$ since the Dehn presentation consists of all words of length $8 \delta$ equal to the identity.

Are there any known lower bounds on the number of relators required to make Dehn's algorithm solve the word problem? In other words, does anyone know a family of groups for which the required number of Dehn relators is exponential in either the size of the original group's presentation or the original groups $\delta$.

Answer by Jeff Burdges for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function

2012-01-06T01:03:00Z

We have $\sum_x (y_x - ax-b)^2 = \sum_x y_x^2 - 2a \sum_x x y_x - 2b \sum_x y_x + \sum_x (ax+b)^2$ so the only term requiring $O(n)$ time per shift is $\sum_x x y_x$ because an easy $O(1)$ time trick handles the other terms involving $y_x$.

In this term, you can decrement $x$ in $O(1)$ time too because $\sum_x (x-1) y_x = \sum_x x y_x - \sum_x y_x$, heck you must store $\sum_x y_x$ anyways. After that, you could simply employ the same obvious $O(1)$ time slide trick you used for $\sum_x y_x^2$ and $\sum_x y_x$.

In fact, you need not do anything too special if terms slide off when $x=0$, i.e. you initially added $k y_x$ and subtracted off one $y_x$ per round.

Answer by Jeff Burdges for Graph of dependencies from a Latex file

2012-01-06T00:28:56Z

As a rule, you cannot depend upon math papers making every dependency explicit, meaning you cannot extract nearly so much information from this directed graph as you imagine. In addition, there isn't any reason this graph should be acyclic since forward references frequently get used in outlines and motivational text.

That said, there are use cases like identifying all the backwards references. For example, you could find all backwards \ref commands using this perl script I call earlyref.pl :

#!/usr/bin/perl -n
BEGIN {  %labels = ();  }
while (/\\(label|ref)\{([A-Za-z0-9_]+)\}/g) {
    if ($1 eq "label") {  $labels{$2} = 1;  next;  }
    next if ($labels{$2});
    print "Early \\ref{$2} on line $. in $ARGV"
}
close if eof(ARGV);

You'll find this handles multiple filename arguments correctly because the last line resets the line number $. when appropriate.

There is considerably more you can do using scripting languages with built in regular expressions. I've written a chcite script which changes all your \cite commands for switching between different co-authors .bib files, for example.

Answer by Jeff Burdges for Extension of the Peano Axioms?

2011-10-17T02:03:33Z

Peano's axioms are categorical if you take the second order formulation, i.e. no non-standard models. If you replace the second order axiom by a first order axiom scheme, they cease being categorical by the compactness theorem, as Francois stated. If you embed the second order version into a first-order model of set they, they remain categorical relative to the set theory, but the set theory itself has non-standard models.

Non-standard models are useful because they help us formalize some features of infinitary processes, i.e. non-standard analysis, geometric group theory, etc. In practice, model theorists would usually have way more structure than simply Peano's axioms, such as a real closed field or hyperbolic group.

Answer by Jeff Burdges for Cherlin's "Main Conjecture"

2011-10-01T19:58:08Z

I think the 'status' might be described as : Pillay has shown using used Selah's work that the free group is not CM-trivial.

All known counterexamples to Zilber's conjecture are CM-trivial. A non-abelian simple group of finite Morley rank is not CM-trivial. We therefore suspect that the current methods based upon Hrushovski's counterexamples cannot produce even an infinite rank counterexample who is a simple group.

Any approximation algorithms for self-avoiding walks?

2011-09-30T14:25:25Z

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge vw with probability 1-p(vw). In other words, I'm trying to understand the probability that a self-avoiding walk goes from v to w. I cannot simply look at powers of the weighted adjacency matrix because this includes cycles.

I've gleaned from the self-avoiding walks literature that computing this probability should be NP-complete, although maybe I've miss-understood something there. Approximation algorithms might exist however. Anyone seen one?

I could imagine some recent-path-dependent ring-like object that when used in the adjacency matrix power operation eliminates counting short cycles. If the probabilities were low enough, this might produce a reasonable approximation with sane running time, although other properties of the graph might enter into the picture too.

Any nice examples of small cancellation theory appearing in applied mathematics?

2011-09-24T18:00:50Z

Are there any nice discussions of applications of small cancellation theory, or other cases of the word problem, in applied mathematics or algorithms for seemingly non-group theoretic problems?

I suppose two candidates are Anshel–Anshel–Goldfeld key exchange and braid group based cryptography.

Answer by Jeff Burdges for Too old for advanced mathematics?

2011-09-24T21:10:23Z

There is evidence that exercising your brain help you stave off Alzheimer's disease, meaning studying mathematics, learning another languages, etc. all prolong your enjoyable lifespan!

There should be several good books on the mathematics of sound encoding/compression, as well as the mathematics of music itself, but I cannot recommend anything in particular.

I'll list some other books you might find interesting however :

Another nice elementary differential equations text is Boyce and DiPrima. Ordinary Differential Equations by Garrett Birkhoff and Gian-Carlo Rota is slightly more advanced. Folland's Introduction to Partial Differential Equations is a nice light introduction to the more advanced stuff that mathematicians working in PDE worry about.

If you're curious about Stochastic Differential Equations, Baxter and Rennie's Financial Calculus: An Introduction to Derivative Pricing gives a wonderfully simple, but fairly correct treatment of the Black-Scholes pricing formula. I'm afraid it doesn't talk about the Black-Scholes PDE though, which is basically the heat equation evolving backwards in time, but the stochastic calculous is enjoyable on it's own, and fairly elementary.

Wilf's Generatingfunctionology is a wonderful introduction to Generating Functions, which anyone reading mathematics solely for enjoyment should briefly delve into. You might also be interested in Introduction to the Theory of Computation by Sipser, or even Algorithm Design by Kleinberg and Tardos.

Answer by Jeff Burdges for What should we teach to liberal arts students who will take only one math course?

2011-04-25T14:13:43Z

There are nice options if your university's students all took calculous in high school. In that case, you might try some light weight mixture of elementary differential equations, recurrence relations, generating functions, and game theory.

You start out by explaining how differential equations arise in various branches of science. You next introduce recurrence relations explaining the distinction between discrete and continuous mathematics, indicating how they arise in science and game theory. You then remind them about Taylor series and introduce the method of generating functions, showing that differential equations are used in solving discrete problems too.

In this way, you could provide a cohesive course that builds upon itself like mathematics is want to do, requires computational homeworks, seriously discusses the notion of infinity, touches upon numerous applied topics, and shows how mathematics can be simultaneously convergent, surprising, and useful by introducing generating functions.

If they're very quick, there is considerable flexibility for discussing algorithm running times and P != NP, or Dirichlet series generating functions and the Riemann Zeta function, or whatever.

You'd want to verify that elementary differential equations and Taylor series are still part of the AP Calculous AB syllabus, as well as the percentage of incoming students who've had that course. You should however suppress anything that requires multi-variable calculous that only falls under the AP Calculous BC syllabus, which presumably few student's took.

Any tips on finding generating functions from recurrence relations involving minimization and maximization?

2011-04-11T00:10:39Z

Any general tips on or examples of finding interesting generating functions from recurrence relations involving minimization and maximization?

I'd imagine the case with one term of a minimization or maximization being constant is already interesting, presumably that covers pricing American style options, although no solution has jumped out at me yet.

I'm most curious about interesting generating functions for recurrences involving minimization or maximization over multiple non-constant but not terribly complex terms however.

Comment by Jeff Burdges

2012-06-20T22:19:37Z

There are an awful lot of motivational issues around graduate studies and professional research. A brilliant but lazy student can kick themselves into gear when faced with interesting challenges, ala Einstein and Hawking. An clever and energetic student can lose their motivation when doing real research too. If mathematics received more grant money, we'd create laboratories that extracted good research from these people who lose their self direction.

Comment by Jeff Burdges

2012-06-14T21:55:29Z

Isn't the title also exceedingly uninformative? It should be obvious to mathematicians that a title "Why 26?" must refer to the number of sporadic finite simple groups. I suppose chemists might start wondering about Iron's properties or something.

Comment by Jeff Burdges

2012-06-12T11:57:59Z

Isn't the ultra product of the alternating groups definably simple but not simple? There is a deep result of Boris Zilber's that definable simplicity implies simplicity for groups of finite Morley rank, which suggests those simple groups might be classifiable.

Comment by Jeff Burdges

2012-04-16T19:57:49Z

I hadn't even considered finite groups, but amusingly the alternating and symmetric groups might be "the easiest example to bear in mind" for my purposes, thanks!

Comment by Jeff Burdges

2012-04-15T12:42:16Z

Yes, this sort of question is more appropriate for math.SE.

Comment by Jeff Burdges

2012-01-06T01:38:26Z

Yup, cut & paste error.

Comment by Jeff Burdges

2011-11-25T05:30:18Z

I'd agree this questions is off topic but it's worth reminding people about the Encyclopedia of Integer Sequences at oeis.org

Comment by Jeff Burdges

2011-10-17T05:10:49Z

Ordinary Differential Equations by Garrett Birkhoff and Gian-Carlo Rota.

Comment by Jeff Burdges

2011-10-13T05:06:37Z

Amen! Ask your professors who'll understand the Australian admissions process.

Comment by Jeff Burdges

2011-10-04T18:13:27Z

I meant merely that the free group strongly resembles a counterexample nothing more, i.e. stable, non-CM-trivial, etc. There have actually been attempts to build counterexamples inspired by Selah's work, but none got very far.

Comment by Jeff Burdges

2011-09-24T21:12:52Z

I'm quite familiar with that project, actually that's indirectly why I'm asking.

Comment by Jeff Burdges

2011-04-12T11:41:35Z

Thanks Gerry! Greene has a sufficiently general example.