User jeff burdges - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T09:22:25Z http://mathoverflow.net/feeds/user/14163 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110331/local-curvature-in-a-cayley-complex Local curvature in a Cayley complex Jeff Burdges 2012-10-22T14:21:41Z 2012-10-22T14:21:41Z <p>I'm curious about non-shperical regions in the Cayley complex of a hyperbolic group $G = &lt; X : R >$ that one might reasonably consider "curved", but I haven't found much discussion of local curvature in a Cayley complex.</p> <p>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.</p> <p>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$. </p> <p>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$.</p> <p>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$ (<a href="http://mathoverflow.net/questions/100155/second-homotopy-group-of-cayley-complex/100210#100210" rel="nofollow">previously</a>) and $C_m$ where $m$ is the reciprocal of the largest relator length are both finitely generated. </p> http://mathoverflow.net/questions/100155/second-homotopy-group-of-cayley-complex Second homotopy group of Cayley complex Jeff Burdges 2012-06-20T17:21:24Z 2012-06-21T10:02:47Z <p>Is there a good reference for information about the second homotopy group of the Cayley complex or <a href="http://en.wikipedia.org/wiki/Presentation_complex" rel="nofollow">Presentation complex</a> 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.</p> http://mathoverflow.net/questions/94213/asymptotics-of-the-number-of-required-dehn-relators-in-hyperbolic-groups Asymptotics of the number of required Dehn relators in hyperbolic groups Jeff Burdges 2012-04-16T13:59:13Z 2012-04-21T15:17:55Z <p>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. </p> <p>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$.</p> http://mathoverflow.net/questions/85012/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a/85018#85018 Answer by Jeff Burdges for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function Jeff Burdges 2012-01-06T01:03:00Z 2012-01-06T01:11:32Z <p>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$.</p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/84977/graph-of-dependencies-from-a-latex-file/85014#85014 Answer by Jeff Burdges for Graph of dependencies from a Latex file Jeff Burdges 2012-01-06T00:28:56Z 2012-01-06T00:28:56Z <p>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.</p> <p>That said, there are use cases like identifying all the backwards references. For example, you could find all backwards <code>\ref</code> commands using this perl script I call <code>earlyref.pl</code> :</p> <pre><code>#!/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); </code></pre> <p>You'll find this handles multiple filename arguments correctly because the last line resets the line number <code>\$.</code> when appropriate. </p> <p>There is considerably more you can do using scripting languages with built in regular expressions. I've written a <a href="https://github.com/burdges/chcite" rel="nofollow">chcite</a> script which changes all your \cite commands for switching between different co-authors .bib files, for example.</p> http://mathoverflow.net/questions/78300/extension-of-the-peano-axioms/78303#78303 Answer by Jeff Burdges for Extension of the Peano Axioms? Jeff Burdges 2011-10-17T02:03:33Z 2011-10-17T02:03:33Z <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/71841/cherlins-main-conjecture/76939#76939 Answer by Jeff Burdges for Cherlin's "Main Conjecture" Jeff Burdges 2011-10-01T19:58:08Z 2011-10-01T20:31:42Z <p>I think the 'status' might be described as : Pillay has shown using used Selah's work that the free group is not CM-trivial.</p> <p>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. </p> http://mathoverflow.net/questions/76857/any-approximation-algorithms-for-self-avoiding-walks Any approximation algorithms for self-avoiding walks? Jeff Burdges 2011-09-30T14:25:25Z 2011-09-30T14:25:25Z <p>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. </p> <p>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?</p> <p>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. </p> http://mathoverflow.net/questions/76279/any-nice-examples-of-small-cancellation-theory-appearing-in-applied-mathematics Any nice examples of small cancellation theory appearing in applied mathematics? Jeff Burdges 2011-09-24T18:00:50Z 2011-09-24T23:43:50Z <p>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? </p> <p>I suppose two candidates are <a href="http://en.wikipedia.org/wiki/Anshel%E2%80%93Anshel%E2%80%93Goldfeld_key_exchange" rel="nofollow">Anshel–Anshel–Goldfeld key exchange</a> and <a href="http://www.cs.ut.ee/~lipmaa/crypto/link/public/braid/index.php" rel="nofollow">braid group based cryptography</a>.</p> http://mathoverflow.net/questions/7120/too-old-for-advanced-mathematics/76290#76290 Answer by Jeff Burdges for Too old for advanced mathematics? Jeff Burdges 2011-09-24T21:10:23Z 2011-09-24T21:10:23Z <p>There is <a href="http://www.guardian.co.uk/science/2007/jun/28/medicineandhealth.medicalresearch" rel="nofollow">evidence</a> that exercising your brain help you stave off Alzheimer's disease, meaning studying mathematics, learning another languages, etc. all prolong your enjoyable lifespan! </p> <p>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.</p> <p>I'll list some other books you might find interesting however :</p> <p>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.</p> <p>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.</p> <p>Wilf's <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow">Generatingfunctionology</a> 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.</p> http://mathoverflow.net/questions/28695/what-should-we-teach-to-liberal-arts-students-who-will-take-only-one-math-course/62926#62926 Answer by Jeff Burdges for What should we teach to liberal arts students who will take only one math course? Jeff Burdges 2011-04-25T14:13:43Z 2011-04-25T14:13:43Z <p>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 <em>differential equations</em>, <em>recurrence relations</em>, <em>generating functions</em>, and <em>game theory</em>.</p> <p>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. </p> <p>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. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/61248/any-tips-on-finding-generating-functions-from-recurrence-relations-involving-mini Any tips on finding generating functions from recurrence relations involving minimization and maximization? Jeff Burdges 2011-04-11T00:10:39Z 2011-04-11T00:10:39Z <p>Any general tips on or examples of finding interesting generating functions from recurrence relations involving minimization and maximization?</p> <p>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.</p> <p>I'm most curious about interesting generating functions for recurrences involving minimization or maximization over multiple non-constant but not terribly complex terms however. </p> http://mathoverflow.net/questions/100182/bad-students-who-made-good-professionals Comment by Jeff Burdges Jeff Burdges 2012-06-20T22:19:37Z 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. http://mathoverflow.net/questions/99643/why-does-bosonic-string-theory-require-26-spacetime-dimensions Comment by Jeff Burdges Jeff Burdges 2012-06-14T21:55:29Z 2012-06-14T21:55:29Z Isn't the title also exceedingly uninformative? It should be obvious to mathematicians that a title &quot;Why 26?&quot; must refer to the number of sporadic finite simple groups. I suppose chemists might start wondering about Iron's properties or something. http://mathoverflow.net/questions/38161/heuristic-argument-that-finite-simple-groups-ought-to-be-classifiable/38404#38404 Comment by Jeff Burdges Jeff Burdges 2012-06-12T11:57:59Z 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. http://mathoverflow.net/questions/94213/asymptotics-of-the-number-of-required-dehn-relators-in-hyperbolic-groups/94222#94222 Comment by Jeff Burdges Jeff Burdges 2012-04-16T19:57:49Z 2012-04-16T19:57:49Z I hadn't even considered finite groups, but amusingly the alternating and symmetric groups might be &quot;the easiest example to bear in mind&quot; for my purposes, thanks! http://mathoverflow.net/questions/94105/why-is-counting-remaining-intervals-different-from-counting-rationals Comment by Jeff Burdges Jeff Burdges 2012-04-15T12:42:16Z 2012-04-15T12:42:16Z Yes, this sort of question is more appropriate for math.SE. http://mathoverflow.net/questions/85012/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a/85018#85018 Comment by Jeff Burdges Jeff Burdges 2012-01-06T01:38:26Z 2012-01-06T01:38:26Z Yup, cut &amp; paste error. http://mathoverflow.net/questions/81849/what-is-the-general-equation-for-this-series-pattern Comment by Jeff Burdges Jeff Burdges 2011-11-25T05:30:18Z 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 <a href="http://oeis.org/" rel="nofollow">oeis.org</a> http://mathoverflow.net/questions/761/undergraduate-level-math-books Comment by Jeff Burdges Jeff Burdges 2011-10-17T05:10:49Z 2011-10-17T05:10:49Z Ordinary Differential Equations by Garrett Birkhoff and Gian-Carlo Rota. http://mathoverflow.net/questions/77911/level-of-detail-on-a-phd-application/77998#77998 Comment by Jeff Burdges Jeff Burdges 2011-10-13T05:06:37Z 2011-10-13T05:06:37Z Amen! Ask your professors who'll understand the Australian admissions process. http://mathoverflow.net/questions/71841/cherlins-main-conjecture/76939#76939 Comment by Jeff Burdges Jeff Burdges 2011-10-04T18:13:27Z 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. http://mathoverflow.net/questions/76279/any-nice-examples-of-small-cancellation-theory-appearing-in-applied-mathematics/76287#76287 Comment by Jeff Burdges Jeff Burdges 2011-09-24T21:12:52Z 2011-09-24T21:12:52Z I'm quite familiar with that project, actually that's indirectly why I'm asking. http://mathoverflow.net/questions/61248/any-tips-on-finding-generating-functions-from-recurrence-relations-involving-mini Comment by Jeff Burdges Jeff Burdges 2011-04-12T11:41:35Z 2011-04-12T11:41:35Z Thanks Gerry! Greene has a sufficiently general example.