User qwerty1793 - MathOverflow

Knot database including text names

2010-09-24T23:47:00Z

Knots such as the 3_1 knot and the 4_1 knot are often referred to as the trefoil and figure-eight knots respectively. There are more obscure names for some of the later ones in the knot tables, for example the 6_1 knot is also know as the stevedore knot. These names are not listed on the online knot database at http://www.indiana.edu/~knotinfo/ are they listed anywhere else?

Is there an (online) database of knots that includes their (text) names.

Answer by qwerty1793 for Interesting mathematical documentaries

2013-02-15T21:49:14Z

Leys, Ghys & Alvarez have also made a video series in a similar style about dynamical systems called "Chaos". The nine chapters are all available under a Creative Commons license.

Manifolds with prescribed fundamental group and finitely many trivial homotopy groups

2012-10-12T21:42:45Z

Fix $G$, a finitely ~~generated~~ presented group.

It is known that for every $k > 3$ there is a closed $k$-manifold whose fundamental group is $G$. Similarly, there is a topological space with fundamental group $G$ and all higher homotopy groups trivial.

However, even for simple examples such as when $G \cong \mathbf{Z}_2$, such a topological space is not a manifold. It seems like the problem with these spaces really lies in the infinite constructions process adding in cells of arbitrarily high dimension. So instead if we only require the first $n$ homotopy groups to be trivial can we still work with manifolds. That is,

Is it true that for each $n > 1$ there is a closed manifold $M$ such that $\pi_1(M) \cong G$ and for $1 < i \leq n$, $\pi_i(M)$ is trivial?

Note that if we allow $M$ to be a non-compact manifold / a manifold with boundary then the answer is yes. This follows as we can always find a finite simplicial complex $X$ whose fundamental group is $G$. By correctly adding $i$-cells (for $1 < i \leq n$) we obtain a simplical complex $X'$ with $\pi_1(X') \cong G$ and for $1 < i \leq n$, $\pi_i(M)$ trivial. By embedding $X'$ in a suitably high dimensional Euclidean space and taking an closed / open regular neighbourhood we obtain $M$, a non-compact manifold / manifold with boundary with the required properties.

Assuming that the answer to the first question is yes, can we also get manifolds of almost any dimension that we like?

Determine if a matrix is unimodular

2012-09-03T08:44:36Z

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?

Generalising right-angled Artin groups

2012-06-13T09:33:19Z

An Artin group $G$ is determined by its Coxeter matrix $M$. This is a symmetric $n \times n$ matrix with entries from $\lbrace 2, 3, \ldots, \infty \rbrace$ that determine the relations between the generators of the group. If all of the entries are in $\lbrace 2, \infty \rbrace$ then we say that $G$ is a ``right-angled Artin group''.

Is there a name for an Artin group in which all of the entries of its Coxeter matrix are in $\lbrace 2, 3, \infty \rbrace$ (or alternatively $\lbrace 2, 3 \rbrace$)?

Note that, for example, all braid groups are of this type.

Does a product of matrices have eigenvalue 1

2012-05-21T10:08:38Z

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$.

For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an eigenvalue of $A$?".

As we are doing this for a large number of sequences (the naive computations when $n \sim 6$, $m \sim 16$, $k \sim 12$ take days) we can assume that any information (for example LU decomposition) wanted about $A_i$ is essentially free.

Is there a faster way to determine if 1 is an eigenvalue of $A$ than computing $A$ and checking if $\det(A - Id_k) = 0$?

Answer by qwerty1793 for Is there a table of (fibred knot) monodromies?

2011-04-19T18:00:29Z

I've produced a table of monodromies for about 40% of the hyperbolic, fibred knots listed on knotinfo. This is available at: http://surfacebundles.wordpress.com/knot-complements/

This was done by producing a triangulation of every possible surface bundle over the circle for the surfaces $S_{1,1}, \ldots, S_{5,1}$ made from a composition of $2, \ldots, 12$ or fewer Dehn twists about generators. Non-hyperbolic and non-knot complement manifolds were discarded and for each pair of isometric triangulations the short-lex later one was also discarded. Finally, for each hyperbolic, fibred knot complement listed on knotinfo, SnapPy was used to find a bundle on this list isometric to it if it existed.

As Sam points out, there is no canonical choice of generating set for $\mathop{Mod}(S_{g,1})$ so I used the Humphries generating set in each case. However, the monodromies obtained are the short lex earliest for each knot with respect to this generating set and the ordering of the generators shown at the bottom of the page. This ordering was chosen to minimise the running time; a different ordering can run several orders of magnitude slower.

I should point out that these results don't show the millions of knot complements that were also found but that don't (yet) appear on the knot tables. This simply comes from the fact that my tables are ordered by monodromy length whereas knotinfo's is ordered by crossing number.

Fixed points of Group Endomorphisms

2011-02-24T00:08:53Z

Suppose $G$ is a finitely presented group with generators $a_1, \ldots, a_n$. Suppose $f \colon G \to G$ is a group endomorphism specified by defining $f(a_1), \ldots, f(a_n)$. As expected, we define a fixed point of $f$ to be any element $g \in G$ such that $f(g) = g$ and, as $f(\mathop{id}) = \mathop{id}$, we say that $\mathop{id}$ is the trivial fixed point.

For example, let $G = \langle a | \rangle$ and $f$ and $g$ be defined by $f(a) = \mathop{id}$ and $g(a) = a^2$. Note in both cases $f$ and $g$ have no non-trivial fixed points and for this particular group we can determine that an endomorphism $f$ has a non-trivial fixed point if and only if $f(a) = a$.

For what groups is it possible to determine whether or not any given endomorphism has a non-trivial fixed point?

I am particularly interested in the question of:

Is $\langle a, b, c | \rangle$ such a group?

Lower bound on number of tetrahedra needed to triangulate a knot complement

2010-11-15T20:18:32Z

Following along a similar line to the question asked here: http://mathoverflow.net/questions/38082/is-there-an-explicit-bound-on-the-number-of-tetrahedra-needed-to-triangulate-a-hy

Let $K$ be a (hyperbolic) knot in $S^3$. Let $n$ be the minimal number of crossings of any diagram of $K$ and let $M = S^3 \backslash K$ be its complement. By Moise’s theorem the 3-manifold $M$ can be triangulated by tetrahedra. But is there any known bound on the number of tetrahedra needed to triangulate $M$ as a function of $n$? I am particularly interested in any known lower bounds, but upper bounds would also be interesting.

pseudo-Anosov maps on surfaces with boundary

2010-10-25T23:07:58Z

In "Automorphisms of Surfaces after Nielsen & Thurston" by Casson & Bleiler (on pages 75 - 80) they discuss classifying automorphisms of a surface. They show that, if $S$ is a closed orientable surface, $f \colon S \to S$ an automorphism and $c$ is a geodesic 1-submanifold of $S$ such that $f(c) \simeq c$ then $f$ is reducible map.

Suppose $S = T^2 \sharp D^2 \sharp D^2$ (the twice punctured torus) and $\delta$ is a loop around one of the boundary components. Then $\delta$ is non-trivial in $H_1(S, \mathbb{Z})$ but $\forall [\phi] \in \mathcal{MCG}(S)$, $\phi(\delta) \simeq \delta$ or $\phi(\phi(\delta)) \simeq \delta$. Hence this statement doesn't hold for $S$.

Is there a similar result for $S$ (or indeed general surfaces with 2 or more boundary components)?

Does constructing non-measurable sets require the axiom of choice?

2010-10-14T21:30:29Z

The classic example of a non-measurable set is described by wikipedia. However, this particular construction is reliant on the axiom of choice; in order to choose representatives of $\mathbb{R} /\mathbb{Q}$.

"Since each element intersects [0,1], we can use the axiom of choice to choose a set containing exactly one representative out of each element of R / Q."

Is it possible to construct a non-measurable set (in $\mathbb{R}$ for example) without requiring the A.o.C.?

Finding generalised Lyndon words

2010-10-02T19:24:41Z

Let $\Sigma = \lbrace a_1, \ldots, a_n, A_1, \ldots A_n \rbrace$ (where $A_i = a_i^{-1}$) and $\prec$ be a total ordering on $\Sigma$.

Let $\Sigma^*$ be the set of all words (generated by the alphabet $\Sigma$) and $\prec^*$ be the total ordering on $\Sigma^*$ induced by $\prec$ (dictionary / lexicographical ordering).

Let $G$ be a finitely presented group which acts on $\Sigma^*$.

For $w \in \Sigma^*$, let $[w]$ denote the equivalence class of words under $G$ (i.e. $[w] = \text{Orb}_G(w)$).

Let $\text{First}_G(w)$ be the first element of $[w]$ under the total ordering $\prec^*$ (i.e. $\text{First}_G(w)$ is the unique element of $[w]$ s.t. $\forall v \in [w] \backslash \lbrace \text{First}_G(w) \rbrace$, $\text{First}_G(w) \prec^* v$). The naive way to determine $\text{First}_G(w)$ is to first generate $[w]$ and then determine the 'first' element of this set, however in general $[w]$ may be an infinite set.

In the case when $G = \langle \Sigma^* | \rangle$ and $g \in G$ acts on $\Sigma^*$ by $g :w \mapsto gwg^{-1}$, $[w]$ is the set of cyclic permutations of $w$ and $\text{First}_G(w)$ is the unique Lyndon word in $[w]$. In this particular case, duval's algorithm will determine $\text{First}_G(w)$ without having to generate all of $[w]$.

Is there an algorithm for determining $\text{First}_G(w)$ without first determining all the elements of $[w]$ for a general group $G$ acting on $\Sigma^*$?

Or alternatively

Is there a $\Sigma$ and $G$ such that $\forall n$, $\exists w \in \Sigma^*$ such that there is no sequence $g_1, g_2, \ldots g_m \in G$ such that $(g_m \circ \cdots \circ g_1)(w) = \text{First}_G(w)$ and $\forall p < m$, $\text{length}((g_p \circ \cdots \circ g_1)(w)) - \text{length}(w) < n$?

i.e. For any bound $n$ there is a word $w$ that must be made more than $n$ letters longer during any sequence of group actions that take it to it's 'first' word.

Simplifying triangulations of 3-manifolds

2010-08-31T12:56:24Z

Throughout, by finite triangulation I mean a triangulation consisting of a finite number of triangles.

Suppose $T$ and $T'$ are finite triangulations of a 3-manifold $M$. We will say that $T'$ is simpler than $T$ iff $T'$ consists of the same number or fewer triangles than $T$ and that $T'$ is a simplest triangulation of $M$ iff $\forall$ triangulation $T$ of $M$, $T'$ is simpler than $T$.

Note: If a 3-manifold $M$ has a finite triangulations, then clearly it has a simplest triangulation.

By a theorem of Pachner (Theorem A.1.1. in 'The geometry of dynamical triangulations') any two triangulations of a manifold can be transformed from one to another by a finite number of stellar subdivisions. As we are only dealing with 3-manifolds, there are only 4 stellar subdivisions; known as the $1 \to 4$, $2 \to 3$, $3 \to 2$ and $4 \to 1$ moves as described in http://at.yorku.ca/t/a/i/c/45.pdf and hereafter called the Pancher moves. So clearly, there exists a finite sequence of Pancher moves from any finite triangulaiton $T$ of $M$ to $T'$, a simplest triangulation of $M$.

If $T$ is a finite triangulation of $M$, does the greedy algorithm of just applying as many $4 \to 1$ and $3 \to 2$ Pancher moves to $T$ as possible always result in a simplest triangulation of $M$?

Or alternatively,

Is there a finite triangulation $T$ of a 3-manifold $M$ such that repeatedly applying only the $4 \to 1$ and $3 \to 2$ Pancher moves does not eventually result in a simplest triangulation of $M$?

Minimum number of contractions needed to obtain a particular invariant set

2010-07-17T22:47:07Z

Consider the Koch curve $G \subseteq \mathbb{R}^2$. Clearly $G$ is the invariant set (IS) of the iterated function system (IFS) $\lbrace \phi_1, \phi_2, \phi_3, \phi_4 \rbrace$. Where (not wanting to jump between $\mathbb{R}^2$ and $\mathbb{C}$ but doing so for ease):

$\phi_1(x) = \frac{1}{3} x$, $\phi_2(x) = \frac{1}{3} (x \exp(\frac{i \pi}{3}) + 1)$, $\phi_3(x) = \frac{1}{3} (x \exp(-\frac{i \pi}{3}) + 1 + \exp(\frac{i \pi}{3}))$, $\phi_4(x) = \frac{1}{3} (x + 2)$

However can we do better? i.e. can we find an IFS consisting of fewer contractions such that its IS is $G$?

In this case, yes. The IFS $\lbrace \psi_1, \psi_2 \rbrace$ also has $G$ as its IS where:

$\psi_1(x) = \frac{1}{\sqrt{3}} x \exp(-\frac{5 i \pi}{6}) + \frac{1}{3} (1 + \exp(\frac{i \pi}{3}))$, $\psi_2(x) = \frac{1}{\sqrt{3}} x \exp(\frac{5 i \pi}{6}) + 1$

And as we know that an IFS consisting of a single contraction has a single point as its IS, we know that this is the best that we can do.

But what about in general?

If $G \subseteq \mathbb{R}^n$ is the IS of the IFS $\lbrace \phi_1, \phi_2, \ldots, \phi_m \rbrace$ when can we tell if there exists an IFS with $G$ as its IS and consisting of strictly less than $m$ contractions?

As a specific example: how about the Sierpinski gasket / carpet? Can we do better that the obvious 3 / 8 construction IFS?

Answer by qwerty1793 for How to write Matlab's dot operators in mathematical expressions?

2010-07-19T18:18:52Z

Your matrix $B$ is the Hadamard product of $A$ and $A$ which uses the notation $B = A \circ A$. However I don't know of any others, particularly for expressing $y$.

See: http://en.wikipedia.org/wiki/Matrix_multiplication#Hadamard_product

Choosing lines and points in D^2

2010-07-15T01:00:37Z

I recently heard of a game between two players "Line" and "Point" and wanted to look for more information on it. However, without knowing the name of it (if it has one) finding more information is hard, has anyone heard of it? Is there a winning strategy for one of the players?

The game is as follows, it is played on the unit disk $D^2$ in $\mathbb{R}^2$ with the point $p_0 = (0,0)$ marked to begin with. Play alternates between L and P (starting with L) and on turn $n$ they do the following:

L chooses a new line $l_n$ through point $p_{n-1}$ and then P chooses a new point $p_n$ on line $l_n$ inside $D^2$.

This forms a sequence of points $(p_n)_{n = 1}^\infty$ in $D^2$. L wins if this sequence converges to a point in $D^2$, P wins if it does not.

As far as I can tell P has a winning strategy, but I my formal proof for this is a sketch at best.

The Worst Possible Winner

2010-07-11T22:59:00Z

First a little background. In racing it is possible for a player to win a tournament without winning a single race, however, how bad can a tournament winner actually be? Can a player win a tournament without even doing better than coming third? Or even fourth? Obviously this depends on the scoring method used for awarding points for each race.

More formally, suppose $p$ players, named $\alpha_1, \alpha_2, \ldots, \alpha_p$, play a game consisting of $n$ races (with no possibility of ties for a position).

Suppse that player $\alpha_i$ finishes race $j$ in position $\beta_{i,j} \in \lbrace 1, 2, \ldots p \rbrace$ (with $\beta_{i,j} = 1$ being the best possible result for player $\alpha_i$). And that for each race the points scored by a player are given by a non-negative, strictly decreasing function called a scoring function $f : \lbrace 1,2, \ldots, p \rbrace \to \mathbb{N}$, i.e. the player coming first receives $f(1)$ points, the player coming second receives $f(2)$ points and the player coming last receives $f(p)$ points.

Let $\text{score}(\alpha_i) = \sum_{j = 1}^{n} f(\beta_{i,j})$ be the total score obtained by player $\alpha_i$.

Let $\text{best}(\alpha_i) = \min_{1 \leq j \leq n} \lbrace \beta_{i,j} \rbrace$, be the best position that player $\alpha_i$ came in.

We say that player $\alpha_i$ is a winner iff $\forall j \in \lbrace 1, 2, \ldots, p \rbrace$ $\text{score}(\alpha_i) \geq \text{score}(\alpha_j)$, note there may be more than one winner of a game.

Given a particular choice of scoring function $f$, if $\alpha_i$ is a winner what is the maximum value $\text{best}(\alpha_i)$ can possibly be?

Or alternatively:

For what $k \in \lbrace 1, 2, \ldots, p \rbrace$, is there a choice of scoring function $f$ such that it is possible for $\alpha_i$ to be a winner and $\text{best}(\alpha_i) \geq k$?

If the general case is too hard, how about when $f(x) = p + 1 - x$?

Root Finding for Raytracing (Ray and Meta-Ball Intersection)

2010-06-30T18:14:15Z

The motivation behind this is to find the points of intersection between a ray and a level set of a potential function $g$, built in terms of a basic potential function $f$ (the building is explained later). This is a problem in ray tracing where the level set is known as a meta-ball. Normally, the basic potential function $f$ is of the form $\exp(-x)$ or $1/x^n$ where $n \geq 1$ and the the problem is solved by finding the roots of a (generally high order) polynomial by a numerical method. However my question is:

Is there an alternative basic potential function $f$ such that the points of intersection between a ray and a level set of $g$ can always be found explicitly and without requiring numerical methods?

More formally:

Let $f \colon \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0} $ be continuous, we say that $f$ is a basic potential function iff:

1) $f$ is non-zero

2) $f$ is strictly decreasing

3) $\lim_{x \to \infty} f(x) = 0$

Let $f$ be a basic potential function, $c_1, \ldots, c_n \in \mathbb{R}^3$ and $a_1, \ldots a_n \in \mathbb{R}$, then we build the potential function $g \colon \mathbb{R}^3 \to \mathbb{R}$ in the following way:

$$g(x) = \sum_{i=1}^n a_i f(\left| x - c_i \right|)$$

Let $k \in \mathbb{R}$ then $S = g^{-1}(k)$ is our level set (meta-ball).

We describe a ray $R$ as a pair $(o, d) \in \mathbb{R}^3 \times S^3$, where $o$ is the origin of the ray and $d$ is the direction in which it is 'pointing'. Using this we may see that finding the points in $R \cap S$ is equivalent to solving $$h(t) = g(o + td) = k$$ (with $t \geq 0$)

Traditionally in ray tracing, the choice of basic potential function $f$ would mean that this could be solved by numerical methods, but is there a basic potential function $f$ such that the solutions of $h(t) = k$ can always be found explicitly (or an alternative way of finding the points in $R \cap S$ without requiring numerical methods)?

Determining a lower bound on the Hausdorff dimension of a set

2010-03-03T20:35:03Z

Does anyone know of a good method for finding a lower bound of the Hausdorff dimension of a set $G$?

The only method I could find is to find an $\alpha$ -Hölder function $f \colon G \to H$ then $\dim_H(G) \geq \alpha \dim_H(\operatorname{im}(f))$ . Choosing $f$ cleverly will mean that $\operatorname{im}(f)$ will be a set whose Hausdorff dimension is already known (or at least a lower bound for it is known).

Easy to find roots

2010-06-20T13:14:00Z

Is there a smooth function $f:\mathbb{R} \to \mathbb{R}_{\geq 0}$ such that:

1) $\lim_{x \to \infty} = \lim_{x \to -\infty} = 0$

2) $\forall x > 0$, $f'(x) < 0$

3) $\forall x < 0$, $f'(x) > 0$

4) $\forall a_1, \ldots, a_n \in \mathbb{R}, K \in \mathbb{R}_{\geq 0}$ the roots of $g(x) = (\sum_{i=1}^n f(x - a_i)) - K$ are "easy to find" (i.e. have an explicit formula in terms of $a_i$ and $K$ for each of them).

My initial guesses were $f(x) = \frac{1}{x^2+1}$ and $f(x) = \exp(-x^2)$ but both fail on part 4.

Microwaving Cubes

2010-05-09T23:03:51Z

First a little background. Mircowaves do not heat uniformly. To help overcome this, your 'food' is rotated, however this is not usually sufficient to produce a totally uniform heating. Informally, the question is when can we find a way of moving our 'food' in order to heat it uniformly throughout?

Let $f : \mathbb{R}^n \to R$ be our heat function. Let $I^n = [-0.5,0.5] \times \cdots \times [-0.5,0.5]$ be the unit n-dimensional cube centered at the origin, this will be our 'food'. Let $\gamma : [0,1] \to \mathbb{R}^n \times SO(n)$ be a map specifying a path along which to translate and rotate $I^n$. If $x \in I^n$ then let $h(x)$ denote the total 'heat absorbed' by $x$ as it travels along $\gamma$. Note if $\gamma(t) = (\gamma_1(t), \gamma_2(t))$ then $h(x) = \int_0^1 f(\gamma_2(t)(x) + \gamma_1(t)) dt$.

We will call a curve $\gamma$ uniformly heated iff $\forall x,y \in I^n$, $h(x) = h(y)$.

How sufficiently 'nice' must our heat function $f$ be in order to guarantee that there exists a uniformly heated curve? Do these requirements change if we consider a different 'food' to heat? For example, if we heat $I^m \times 0^{n-m}$ in $\mathbb{R}^n$.

Note that in $\mathbb{R}^1$, as $SO(1) = 1$, if $f$ is a strictly monotonic function then there cannot exist any uniformly heated curves as (assuming wlog $f$ is increasing) $h(-0.5) < h(0.5)$.

Following curves on S^n

2010-03-11T18:59:37Z

Suppose $V$ is a no-where zero vector field on $S^n$ ($n$ odd). Let $p \in S^n$. Let $\gamma_p$ be the unique curve on $S^n$ through $p$ and tangential to $V$ everywhere along it. Is it true that $\gamma_p$ is a closed curve $\forall p \in S^n$? If so, is it true that the length of $\gamma_p$ must be finite?

Alternatively, is it possible to find a curve $\gamma$ on $S^n$ of infinate length such that the tangent vectors of $\gamma$ can be extended to form a continuous, no-where zero tangential vector field of $S^n$?

What do you call the product of a circle and an annulus?

2010-01-10T10:23:20Z

What would you call the product of an annulus and $S^1$ (a 'thickened' torus like 3-manifold)?

More generally, is there an archive or list online of names assigned to various (non-standard) manifolds by people? Or a set convention by which to name them?

Is \mathbb{C}^{n \times n} algebraically closed?

2010-02-01T10:23:50Z

Inspite of the fact that $C^{n \times n}$ is not a field, is it still possible to talk about it being 'algebraically closed' in the sense that $\forall f \in \mathbb{C}^{n \times n}[x]$ does $\exists A \in \mathbb{C}^{n \times n}$ such that $f(A) = 0$? If so, then is it 'algebraically closed'?

Are there any other non-field sets that this idea can be extended to?

Rank(A) and other algorithms as a polynomial

2010-01-18T20:04:29Z

If $A = (\alpha_{ij}) \in \mathbb{C}^{nxm}$ we have simple algorithms by which to determine $\mathrm{rank}(A)$. However, is there a polynomial $f \in \mathbb{C}[\alpha_{ij}]$ where $f \colon \mathbb{C}^{nxm} \to \mathbb{N}$ such that $f(A) = \mathrm{rank}(A)$?

In general, is it possible to determine if a particular algorithm may be expressed as a polynomial or other more general function?

Answer by qwerty1793 for Archaeogenetics

2010-01-18T00:14:13Z

I'm not sure what you mean by 'starts with a population formed by two empty sets'.

However, assuming you start with an initial population $P = \left\lbrace A_1, \ldots, A_n \right\rbrace$ where each individual $A_i = \left\lbrace a_{i1}, \ldots, a_{i{n_i}} \right\rbrace $.

Let $|A_i|$ be the complexity (number of genes?) of individual $A_i$, i.e. $|A_1| = |\left\lbrace a_11, a_12, a_13 \right\rbrace | = 3$, and $|P| = 1/n \sum_{i=1}^n |A_i|$ be the average complexity of all of the individuals in the population. Let $P'$ be this population after applying the 'killing' operation and $P''$ be this population after applying the 'recombination' operation. Then, after some basic algebra / logic, we see that

$E(|P'|) = |P|$ and $E(|P''|) = |P|$ too. Hence conversely, if $P_0$ was our initial population and $P_t$ is our population after $t$ applications of either the 'killing' operation or the 'recombination' operation, then

$E(|P_0|) = |P_t|$.

Not also that, as 'killing' removes one member of the population and 'recombination' adds one, we may model the total population as a random walk and so, for example, determine an expected initial population size based on current population and number of generations (off the top of my head it's also another invarient and so expected inital population = final population, although this needs checking.)

There are almost certainly other invarients.

On the more abstract side:

Call a population $P$ in which $\forall i,j$, $A_i \cap A_j = \emptyset$ pure.

Note:

Applying 'killing' to a pure population gives a pure population.
Applying 'killing' to a non-pure population MAY give a pure population.
Applying 'recombination' to a pure population gives a non-pure population.
Applying 'recombination' to a non-pure population gives a non-pure population.

As the probability of them being the same is 0, wlog we may assume all 'genes' of all individuals are unique - i.e. the inital population is pure. This gives us a 2 state system that models the population, passing between the pure and non-pure states by these 2 operations. As generations pass I would expect the population to become 'more non-pure' as the probability of the application of a killing operation reverting it to a pure population reduces. This should give us a method by which to determine an expected value for the number of itterations that have occured by measuring the 'purity' of the population.

Comment by qwerty1793

2013-02-28T22:52:17Z

Thanks for the suggestion. Just to let you know you can actually skip the volume filtering, Dr. Weeks built it directly into the snappea kernel! Line 90 of isometry.c defines "CRUDE_VOLUME_EPSILON" to be 0.01. Later, around line 140, when testing if two manifolds are isometric if they differ by more than this amount the entire calculation is aborted and the function returns "not isometric".

Comment by qwerty1793

2013-01-11T14:53:01Z

A torus requires at least three chart maps.

Comment by qwerty1793

2012-10-14T10:45:18Z

Sorry, despite my efforts to make sure I wrote "finitely presented" I ended up writing finitely generated. I'll edit the question.

Comment by qwerty1793

2012-09-28T06:00:29Z

Yes, all knots have unknotting number less than $\lfloor n/2 \rfloor$. Suppose that making $k > \lfloor n/2 \rfloor$ crossing flips results in the unknot, then you can check that flipping all unflipped crossings instead also does. This clearly requires $\leq \lfloor n/2 \rfloor$ flips and so the unknotting number is at most $\lfloor n/2 \rfloor$. An equivalent bound also holds for unlinking links.

Comment by qwerty1793

2012-09-04T09:43:41Z

In fact, thanks to LU decomposition, computing the determinant is at least as fast as computing a matrix product. So we can compute the determinant exactly in $O(n^{2.376}). See en.wikipedia.org/wiki/…. Similarly, in Storjohann's paper "Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices" he shows a similar inequality. That is, for an integer square matrix, computing its SNF is at least as fast as computing a matrix product.

Comment by qwerty1793

2012-09-03T09:22:28Z

Sorry I misread the answers paper, their definition of unimodular used in Theorem 1 is more general to cover non-square matrices. I'll edit the question and remove the reference.

Comment by qwerty1793

2012-06-14T11:19:49Z

Thanks, small type refers to the {2,3} case, correct? Is there a similar name for the {2,3,\infty} case?

Comment by qwerty1793

2012-05-21T13:18:24Z

Correct, you could also think of my problem as "produce a list of all sequences i_1, ..., i_k such that 1 is an eigenvalue of A_i_1 ... A_i_k". Currently I just consider each sequence in turn, compute the product and check if 1 is an eigenvalue or not by computing a determinant. Sorry for the confusion.

Comment by qwerty1793

2012-05-21T12:20:08Z

Yes the spectrum is easy to compute (this is even easier as I just want to know if 1 is in the spectrum or not) but is there a faster way to do this than the naive computation. As I'm doing this repeatedly for various sequences is there anyway to reuse some of the information I find out about one sequence to determine some information about another 'similar' sequence?

Comment by qwerty1793

2011-05-27T09:45:19Z

As the conjecture is stated, False as $\forall N$, $T^N(2^{N+1}) = 2 \neq 1$ but I doubt I'll get \$500 for stating that.

Comment by qwerty1793

2011-04-19T19:53:05Z

Yes, a capital letter represent the inverse twist. Non-hyperbolic ones had to be discarded as SnapPy really struggles to determine if two non-hyperbolic triangulations are isometric or not. I don't think that it is incapable of doing it, but I've always had it return "RuntimeError: SnapPea failed to determine whether the manifolds are isometric." - even for the trefoil knot.

Comment by qwerty1793

2010-11-15T23:05:27Z

Did you mean to say "where $$L^p$^* \cong L^q"?

Comment by qwerty1793

2010-11-15T22:58:55Z

Yes Ryan you are correct, by number of crossings of a knot K I mean the minimal number of crossings of ANY diagram of K. I'll change the question to reflect this.

Comment by qwerty1793

2010-10-25T23:28:04Z

Not quite, f is reducible iff f is homotopic to an automorphism g which leaves invariant an essential 1-submanifold. Their remark says that it is equivalent to say that there exists a geodesic 1-submanifold which is isotopic to its image under f.

Comment by qwerty1793

2010-09-25T00:13:54Z

Sorry, I was looking for a large table listing the knots and their alternate names similar to the information / format provided by knotinfo. I see katlas.org has alternate names listed on the individual pages of knots but the "take home database" doesn't seem to include this.