User samuel reid - MathOverflow

The Riemann Zeta Function summing over the Gamma Function

2013-06-14T01:40:59Z

Has anyone studied a function of the form $$\eta(s) = \sum_{n=1}^{\infty} \frac{1}{\Gamma(n)^{s}} = \sum_{n=0}^{\infty}\frac{1}{k!^s}$$ This series is appearing in my research on the volumetric properties of infinite families of polytopes and I am not sure how to evaluate the sum, or if this is a well-known function other than the fact that $\eta(2) = I_{0}(2)$, where $I_{\nu}(x)$ is the modified Bessel function of the first kind as seen here. I am interested in evaluating this series for any $s \in (1,\infty)$. For integer values of $s$ is it equal to a generalized hypergeometric function?

EDIT: It would be sufficient for my purposes to prove that $\eta(s)$ is finite for any $s \in (0,\infty)$, any ideas?

Reducing a System of Polynomial Equations

2013-06-05T20:06:06Z

I am currently writing a program in SAGE which computes Nilpotent Orbit Varieties for an Algebraic Geometry research project and I have reduced my problem to the following:

Consider a system of polynomial equations ${f_{1},...,f_{n}}$, with each equal to zero and a function of $k$ variables, that is, $f_{i}(x_{1},...,x_{k}) = 0$, for $1 \leq i \leq n$. Is there a known algorithm or procedure (which I could program) for reducing the number of equations or number of variables to a minimal amount?

In particular, I want to reduce the runtime of my code by figuring out if I have redundancies in my equations and eliminating those redundancies (such as one equation implying that a variable is equal to zero in all of the others, which would reduce the number of equations and variables).

EDIT: I have included a snapshot of my program here: As you can see from my list of equations, we have that $x_{11}x_{12} + x_{12}x_{22} =0$ implies $x_{11} = - x_{22}$ and thus the entire system reduces to $x_{11}^2 + x_{12}x_{21} =0$. Implementing the Groebner basis command as follows in SAGE did not obtain this result.

I = equations*PolynomialRing(CC,len(varlist(n)),varlist(n))
B = I.groebner_basis()
print("The Groebner basis for I is:\n"+str(B))

where the list 'equations' is what was printed after "the closure of the nilpotent..." and the varlist(n) is a function I defined which deals with list manipulation and nothing mathematical. I was simply following the sage documentation here. So, what I need is some algorithm which in this example would give me just that my system of polynomial equations equal to zero reduces to $x_{11}^2 + x_{12}x_{21} = 0$.

Deriving Helfrich's shape equation for closed membranes

2013-06-05T21:02:12Z

I have a bunch of papers that claim that, from the equation for shape energy: $$ F = \frac{1}{2}k_c \int (c_1+c_2-c_0)^2 dA + \Delta p \int dV + \lambda \int dA$$ one can use "methods of variational calculus" to derive the following: $$\Delta p - 2\lambda H + k(2H+c_0)(2H^2-2K-c_0H)+2k\nabla^2H=0$$ But I'm having a lot of trouble tracking down the original derivation. The guy who did it first was Helfrich, and here's his and Ou-yang's paper deriving it: http://prl.aps.org/pdf/PRL/v59/i21/p2486_1 . However, they don't show an actual derivation, instead saying "the derivation will appear in a full paper by the authors" or something like that. Yet everybody cites the paper I just linked for a derivation. Does anybody know a source that can derive this, or can give me some hints to figure it out myself? To be honest I can't even figure out how to find the first variation. Thanks!

Sage or Magma Implementation of Nilpotent Orbit Varieties

2013-05-16T17:00:52Z

For a given partition $[n_{1},...,n_{k}]$ of $N \in \mathbb{N}$ there exists a corresponding nilpotent orbit variety $O_{[n_{1},...,n_{k}]}$ in $\mathfrak{gl}(N)$ which can be represented by a set of polynomial equations relating the conditions on matrices in $\mathfrak{gl}(N)^{\text{nilp}}$. I was wondering if anyone has implemented the computation of nilpotent orbit varieties in Sage or Magma, because otherwise I am going to make my own code for doing so. If you happen to know of any references, that would help!

The Area of Spherical Polygons

2012-05-23T02:19:31Z

I am interested in finding a canonical general expression for the area of a spherical polygon in $\mathbb{S}^2$ knowing the side lengths of the polygon and a bound on the internal angles (we can assume a radius of $R=1$).

For what I am researching (I will not go into the background) I need the following conditions to be satisfied:

The edge length of all spherical polygons in $\mathbb{S}^2$ is $\pi / 3$.
The spherical polygons I want to consider may or may not be convex, in fact it is necessary that I be able to compute the area of a non-convex polygon in $\mathbb{S}^2$.

I know there are multiple ways to compute the area of a spherical triangle using the spherical law of cosines, L'Huilier's theorem, or other formulas, but I want to be more general than this. The type of information I know about the internal angles of the spherical polygons is a bound in terms of the degree of the vertex considered in a spherical simplicial $2$-complex $\mathcal{K}$ in $\mathbb{S}^2$. That is, labeling $\gamma_{i}$ as an internal angle of the spherical polygon that $$ \sum\limits_{1 \leq i \leq b} \gamma_{i} = \sum\limits_{1 \leq i \leq b} (i-1)\arccos(\frac{1}{3})b_{i}$$ where $b_{i}$ denotes the number of vertices of degree $i$ in $\mathcal{K}$. The last comment about the internal angles may or may not be confusing, but I just wanted to mention that I know something about the internal angles of the spherical polygons. For an example of how difficult this problem may be, there was a large discussion here about determining the area of a spherical $4$-gon with given side length (and the answer was quite messy), so I'm hoping that some of you have ideas!

To summarize exactly what my question is, and what information I know:

You are given a number $E$ which tells you how many edges a spherical polygon $C$ in $\mathbb{S}^2$ has (all edges have length $\pi /3$ and $C$ is not necessarily convex). Determine the area of $C$ (or a function for the area of $C$).

That is, I want to find the analogue in spherical geometry to the equations in Euclidean geometry which tell you the area of a regular polygon of a given number of sides. If such a general expression does not exist, I would be interested in the case for $E=5,E=6,...,E\approx20$.

Asymptotics of the Number of Non-Isomorphic Equivalence Relations and the Number of Non-Isomorphic Relations

2013-04-10T15:33:11Z

The number of non-isomorphic equivalence relations on a set of $n$ elements is the partition function $$p(n) =\frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} \sum_{h=1}^{k} \delta_{\gcd(h,k),1} \text{exp}\left(\pi i \sum_{j=1}^{k-1} \frac{j}{k}\left(\frac{hj}{k} - \left\lfloor \frac{hj}{k} \right\rfloor - \frac{1}{2}\right) - \frac{2\pi i h n}{k} \right) \sqrt{k} \frac{d}{dn}\left[ \frac{\sinh\left(\frac{\pi}{k} \sqrt{\frac{2}{3}(n - \frac{1}{24})}\right)}{\sqrt{n - \frac{1}{24}}} \right]$$ The Hardy-Ramanujan asymptotic formula states that $$p(n) \sim \frac{1}{4\sqrt{3}n}e^{\pi \sqrt{2n/3}}$$

By this answer (I would appreciate any reference to an actual derivation of this formula) the number of non-isomorphic relations on a set of $n$ elements is

$$a(n) = \sum_{1s_{1} + 2s_{2} + \cdot\cdot\cdot =n} \left(2^{\sum_{i,j \geq 1} \gcd(i,j)s_{i}s_{j}} \bigg/ \prod_{k=1} k^{s_{k}}s_{k}!\right)$$

I have no idea about the asymptotics of $a(n)$, but if you know of a reference that would be amazing. My question is whether anyone has researched, or if you have any idea about, whether or not $$\frac{p(n)}{a(n)} \sim 0$$ I conjecture that it is asymptotic to zero, but I have no idea how to prove it.

Does the Hardy-Ramanujan Asymptotic Formula Partition Sets or Integers?

2013-04-10T09:49:20Z

From "Models and Games" by Jouko Vaananen (Cambridge studies in advanced mathematics), I quote

The Hardy-Ramanujan asymptotic formula says that the number of equivalence relations on a fixed set of $n$ elements is asymptotically $$\frac{1}{4\sqrt{3}n}e^{\pi\sqrt{2n/3}}$$ So this is also an asymptotic upper bound for the number of non-isomorphic equivalence relations on a universe of $n$ elements.

I am very confused by this as I thought that the Hardy-Ramanujan asymptotic formula was asymptotic to the partition function $p(n)$ which says how many times you can write $n$ as a sum of positive integers, not the number of partitions of a set of $n$ elements. Is this book incorrect or am I missing something about the connection between equivalence relations and the partition function?

On the Combinatorial Classification of Modal Kripke Frames

2013-04-09T22:21:48Z

We have that S5 modal logic is characterized by the modal axioms $K$, $M$ (reflexive), $4$ (transitive), and $B$ (symmetric). That is, an equivalence relation on a set of possible world (which can be thought of as a digraph if you don't like Kripke semantics) generates S5 modal logic. There is a result of Hardy and Ramanujan which states that the number of equivalence classes of a fixed set of $n$ elements is asymptotically: $$\frac{1}{4\sqrt{3}n}e^{\pi \sqrt{2/3}\sqrt{n}}$$

So, we can asymptotically upper bound the number of distinct Kripke frames with $n$ possible world that generate S5 modal logic by the Hardy-Ramanujan number. There are other modal logics that are characterized by similar axioms, for example, consider a Kripke frame which satisfies antisymmetry, antireflexivity, and transitivity. Then there are some number of distinct Kripke frames with strict partial orderings. Are there any bounds asymptotically on the number of strict partial orderings on a set with $n$ elements similar to the Hardy-Ramanujan number? In general, given any property which can be satisfied in a frame by a modal axiom, do corresponding asymptotic bounds exist on how many Kripke frames can satisfy that modal axiom of size $n$? If not, I would be interested in writing a paper about this topic and would appreciate any references to asymptotic bounds on the number of relations of a certain type on a set of size n.

How are Modal Logic and Graph Theory related?

2013-02-03T18:26:18Z

I am currently taking a graduate logic course on Modal Logic and I can't help notice that there are a certain class of graphs characterized by the modal axioms such as (4) $\Box p \rightarrow \Box \Box p$, (5) $\Diamond p \rightarrow \Box \Diamond p$, or (B) $p \rightarrow \Box \Diamond p$ which can characterize frames as being transitive, Euclidean, and symmetric, respectively. In general, I notice many similarities between the models used in Modal Logic and the graphs in Graph Theory and I'm wondering if anyone knows if there are applications of Modal Logic to Graph Theory, or if one subject might be a special case of the other?

In any case, if anyone has studied this before or knows of any references on the interplay between Modal Logic and Graph Theory I would be very interested to read about it, and if it has not been studied before then I would be interested of any ideas regarding what open research problems could be stated to tackle the correspondence between these two topics. (A category theory perspective on this interplay would also be very interesting)

Is Guillou-Quisquater existentially unforgeable against adaptive message attack under a random oracle model?

2013-02-22T21:38:41Z

First of all, the Guillou-Quisquater digital signature scheme is:

Note everything is $\bmod n$. Message is denoted by $m$.

Private key: $s$

Public key: Hash function $H$, $e$, $L=s^e\bmod n$

To sign: Alice chooses random $r$. Computes $c=H(m||x)$ with $x=r^e\bmod n$; $y=r\cdot s^c\bmod n$; send Bob $x$ and $y$.

To verify: Bob computes $c=H(m||x)$ and accept if $y^e \equiv x\cdot L^c\pmod n$.

I'm wondering what the strongest known security of this is, in particular the question in the title. If not, what's the best research that's been done on this scheme?

I've scoured the internet for such a proof, but I can't find anything. I was also told by my supervisor that if I could find such a proof for El Gamal it might be easily adaptable, so that would also be much appreciated. Thanks!

Kissing Number of Spheres in Non-Euclidean Geometry

2013-03-01T08:04:38Z

There has been much work done on the kissing number problem (of determining the greatest number of congruent spheres which can touch a single sphere in a packing) in Euclidean space for dimensions $1$ to $24$ and even some asymptotic work. My question is whether or not the kissing number problem has been studied in Non-Euclidean geometries such as the other seven Thurston Geometries $\mathbb{S}^2 \times \mathbb{R}, \mathbb{H}^2 \times \mathbb{R}, \mathbb{S}^3, \mathbb{H}^3, \widetilde{SL_{2}(\mathbb{R})}$, Nilgeometry, or Solvgeometry.

Any references or ideas about this topic would be very interesting!

Computing the Volume of Closed 3-Manifolds and the Geometrization Conjecture

2013-02-26T19:49:40Z

My question is whether or not if I generalize Theorem 2(i) of "Contact Graphs of Unit Sphere Packings Revisited" [2012] by K. Bezdek and S. Reid (arXiv link) which states

The number of touching triplets (resp., quadruples) in an arbitrary packing of $n \geq 3$ (resp., $n \geq 4$) unit balls in $\mathbb{E}^3$ is at most $\frac{25}{3}n$ (resp., $\frac{11}{4}n$).

by replacing $\mathbb{E}^3$ by any of the other Thurston Geometries $\mathbb{S}^2 \times \mathbb{R}, \mathbb{H}^2 \times \mathbb{R}, \mathbb{S}^3, \mathbb{H}^3, \widetilde{SL_{2}(\mathbb{R})}$, Nilgeometry, or Solvgeometry, if I can use the Geometrization Conjecture to say something about the volume of closed 3-manifolds.

A succint statement of the Geometrization Conjecture for my purposes would be that for any closed 3-manifold $\mathcal{M}$ there exists a decomposition (I think it is called the JSJ-torus decomposition, denoted by $\otimes$) of $\mathcal{M}$ into prime 3-manifolds $\mathcal{N}_{i}$ (such a decomposition exists due to the Geometrization Conjecture recently proved by G. Perelman and neatly presented in "Completion of the Proof of the Geometrization Conjecture" [2008] by John Morgan and Gang Tian)

$$\mathcal{M} = \bigotimes_{i=1}^{n} \mathcal{N}_{i}$$

where each $\mathcal{N}_{i}$ admits one of the eight Thurston Geometries

$\mathbb{S}^2 \times \mathbb{R}, \mathbb{H}^2 \times \mathbb{R}, \mathbb{E}^3, \mathbb{S}^3, \mathbb{H}^3, \widetilde{SL_{2}(\mathbb{R})}$, Nilgeometry, or Solvgeometry.

and is of a finite volume.

My idea now is that the volume of each prime 3-manifold which $\mathcal{M}$ was decomposed into can have it's volume approximated by determining the maximum number of regular 3-simplices in a simplicial 3-complex $\mathcal{K}_{i}$ which can be embedded into the $i$-th prime 3-manifold in the decomposition. Then,

$$\text{vol}\left(\mathcal{M}\right) > \sum_{i=1}^{n} \text{vol}(\mathcal{K}_{i})$$

With a generalization of Theorem 2(i) to each of the Thurston Geometries, then I would be able to compute this bound by multiplying the maximum number of unit balls I can fit in the space by the volume of the unit ball and dividing by the optimal known packing density (note that a regular 3-simplex corresponds to a touching quadruple of spheres, which is why Theorem 2(i) would be useful). Does this general outline make sense? I don't know a lot about the decomposition of manifolds or the volume of manifolds, so any feedback on the idea or references would be appreciated. In particular, my question is:

If I do all of the work to get a version of Theorem 2(i) in each Thurston Geometry, can I use the Geometrization Conjecture for studying (in this example, I was thinking volume computation of 3-manifolds) some interesting properties of 3-manifolds?

Adjoint of Pushout as Modal Operators in Internal Logic

2013-02-11T16:07:38Z

Regarding the internalization of mathematics to a particular category as in the nLab article: Internal Logic, there is a peculiar table mentioned in the section on Categorical Semantics in which there is a corresponding category-theoretic construction to the regular logical operators in a theory. In particular, $\wedge$ corresponds to a pullback of a cospan, $\top$ corresponds to the top element (A itself), $\wedge$ corresponds to union, $\bot$ corresponds to the bottom element (strict initial object), $\Rightarrow$ corresponds to the Heyting implication, $\exists$ corresponds to the left adjoint to a pullback (I'm not sure which pullback in particular?), and $\forall$ corresponds to the right adjoint to a pullback (what pullback is this also?).

Would it be possible to define the modal operators of $\Box$ and $\Diamond$ as the right adjoint of a pushout (similarly to how $\forall$ is the right adjoint to a pullback) and the left adjoint of a pushout (similarly to how $\exists$ is the left adjoint to a pullback), respectively? Or, if this does not work, could it be possible to define modal operators in internal logic using some other category theoretic construction?

Completeness of a Theory from the Categorical Viewpoint

2013-02-11T06:46:12Z

I am interested in a more specific reference or explanation of "the categorical view" explained in the article http://ncatlab.org/nlab/show/theory#CategoricalView. In particular, I am interested in trying to prove full completeness for a geometric model of multiplicative linear logic and I want to use a category theoretic approach in order to do so. So, when it is mentioned that

Models of a theory $\mathcal{T}$ are identified with functors $$C_{\mathcal{T}} \rightarrow \textbf{Set}$$ that preserve some (typically property-like) structures on $C_{\mathcal{T}}$, such as certain classes of colimits or limits, pertinent to the logic at hand, where $C_{\mathcal{T}}$ is the syntactic category of terms for the theory $\mathcal{T}$.

I interpret that as being that for a particular model of a theory, I want to define a functor which can be identified with that theory (in my case, the geometric model of multiplicative linear logic). Yet, I am unsure as to how I would know what properties I want it to preserve on $C_{\mathcal{T}}$.

Furthermore, the article mentions that a completeness theorem would be the statement that

the canonical map $$C_{\mathcal{T}} \rightarrow \prod_{\text{models in $\textbf{Set}$}} \textbf{Set}$$ is a full faithful embedding.

In this context, how would I prove completeness for one model of the theory, or does only refer to completeness of a theory in all possible models of that theory? In particular, a proof of the full completeness of multiplicative linear logic was given by Samson Abramsky and Radha Jagadeesan in "Games and Full Completeness for Multiplicative Linear Logic (1994)" Does this mean that completeness is proved for multiplicative linear logic in general, or just for the game-theoretic model defined in the paper?

To summarize, my questions are as follows:

1) Given a language for a signature (in the syntactic view of a theory), how do I define a functor $C_{\mathcal{T}} \rightarrow \textbf{Set}$ which can be identified with this theory?

2) In the categorical view, is completeness of a theory defined over all models for that theory, or can we prove completeness for a specific model of that theory. If the later holds, what exactly do I need to prove is a full faithful embedding?

The First Homology Group of Configuration Space and Knot Theory

2012-12-01T03:09:17Z

Let $\pi_{1}: \text{Top}^* \rightarrow \text{Grp}$ denote the fundamental group functor and let $H_{1}: \text{Top}^* \rightarrow \text{Grp}$ denote the first homology group functor. We can then define a natural transformation $\eta: \pi_{1} \rightarrow H_{1}$ with a component $\eta_{X}: \pi_{1}(X) \rightarrow H_{1}(X)$. We define the configuration space on $n$ points by, $$C_{\hat{n}}(\mathbb{R}) = \{(z_{1},...,z_{n}) \in \mathbb{R}^n \; | \; z_{i} \neq z_{j}\}$$ and the unordered configuration space on $n$ points by $C_{n}(\mathbb{R}) = C_{\hat{n}}(\mathbb{R}) \big/ \Sigma_{n}$, where $\Sigma_{n}$ is the symmetric group. We then have for $\vec{p} \in C_{\hat{n}}(\mathbb{R})$ that $\pi_{1}(C_{\hat{n}}(\mathbb{R}),\vec{p}) \cong PB_{n}$ and $\pi_{1}(C_{n}(\mathbb{R}),\tau(\vec{p})) \cong B_{n}$, where $\tau : C_{\hat{n}}(\mathbb{R}) \rightarrow C_{n}(\mathbb{R})$ is the orbit space projection, $PB_{n}$ is the pure braid group on $n$-strands, and $B_{n}$ is the braid group on $n$-strands.

Consider the components of the natural transformation between the fundamental group functor and the first homology group functor given by,

$$\eta_{C_{\hat{n}}(\mathbb{R})} : \pi_{1}(C_{\hat{n}}(\mathbb{R})) \rightarrow H_{1}(C_{\hat{n}}(\mathbb{R}))$$ $$\eta_{C_{n}(\mathbb{R})} : \pi_{1}(C_{n}(\mathbb{R})) \rightarrow H_{1}(C_{n}(\mathbb{R}))$$

What objects in $\text{Grp}$ will these components of $\eta: \pi_{1} \rightarrow H_{1}$ associate with $PB_{n}$ and $B_{n}$, and how do they relate to $C_{\hat{n}}(\mathbb{R})$ and $C_{n}(\mathbb{R})$?

I am interested in this question because I am wondering if $H_{1}(C_{\hat{n}}(\mathbb{R}))$ and $H_{1}(C_{n}(\mathbb{R}))$ have any unnoticed connections to knot theory since every knot is the closure of a braid.

Answer by Samuel Reid for Beginning reference for configuration spaces

2012-09-10T06:29:33Z

The configuration space of $n$ points in a topological space $X$ is usually defined to be,

$$C_{\hat{n}}(X) = {(z_{1},...,z_{n}) \in X^{n} \; | \; z_{i} \neq z_{j} \; \text{if} \; i\neq j }$$

A theorem which may be enlightening to your intuitive understanding of $C_{\hat{n}}(X)$ would be the following:

$$C_{\hat{n}}([0,1]) = \coprod_{i=1}^{n!} \Delta_{i}^{n}$$

Where $\coprod$ denotes disjoint union, and $\Delta_{i}^{n}$ denotes the $i^{th}$ copy of the $n$-simplex $\Delta^{n}$. We see that there are $n!$ $\Delta^{n}$'s because the symmetric group (which has order $n!$) acts freely on $C_{\hat{n}}(X)$, permuting the coordinates in each $\vec{z}=(z_{1},...,z_{n}) \in C_{\hat{n}}(X)$.

In fact, we can define the orbit space $C_{n}(X) := C_{\hat{n}}(X) / \Sigma_{n}$ as configuration space modded out by the symmetric group on $n$ elements $\Sigma_{n}$. Then it can be shown that $$\pi_{1}(C_{\hat{n}},\vec{p}) = PB_{n}, \; \text{and} \; \pi_{1}(C_{n},\tau(\vec{p})) = B_{n}$$ Where, $\tau: C_{\hat{n}}(X) \rightarrow C_{n}(X)$ is an $n!$-sheeted covering map called the orbit space projection, and $PB_{n}$ and $B_{n}$ are the pure braid group and braid group on $n$ strands, respectively.

If this sounds interesting to you, then I suggest you read the following paper:

Configuration Spaces and Braid Groups by Fred Cohen and Jonathan Pakianathan

Is there a security analysis of the GQ digital signature scheme?

2012-07-17T21:11:10Z

I'm doing summer cryptography research and I am have been looking for a security analysis of the Guillou-Quisquater (GQ) digital signature scheme, but I have been unable to find one.

Since this is not a very common digital signature scheme I will mention the protocol.

GQ: Public: $n,e,I$ has function $H$, where $I \equiv S^{e} \mod n$

Private: $s$

Signature: $(x,y)$ where $x \equiv r^{e} \mod n, c=h(m,x)$, and $y \equiv rS^{c} \mod n$

To verify: Check that $y^{e} \equiv x I^{h(m,x)} \mod n$ (this works because $y^{e} \equiv (rS^{c})^{e} \equiv r^{e}S^{ce} \equiv xI^{c}$)

Any references to papers in which this could be found would be very helpful. Thank you!

Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

2012-05-16T00:03:22Z

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the subject) and I am in the dark on what I think should be a very simple point. I apologize if the question is too elementary for MO.

For reasons I won't get into, I am needing to give a bound for the number of spherical $2$-simplexes which can occur among $n$-points in $\mathbb{S}^2$, as this will tell me how many exposed faces of a simplicial $3$-complex there are among a certain subset of $n$-points in $\mathbb{E}^3$. I am at a point in a Lemma where I am needing to generalize the following claim about graphs in the plane, to simplicial $2$-complexes (graphs) in $\mathbb{S}^2$.

I cite from Pach and Agarwal's Combinatorial Geometry: "The internal angle of a simple closed polygon $C$ which bounds a graph $G$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$."

Does anyone know a proof of this fact, or have a simple explanation of it so that I can have a hope of generalizing it to "the internal angle of a simple closed spherical polygon which bounds a simplicial $2$-complex at a vertex of degree $d$ is at least [something] in $\mathbb{S}^2$".

Thank you, I appreciate any responses.

EDIT: Due to Joseph O'Rourke's comment I will quote a larger passage from the book so that there is more context.

The properties of a graph $G$ are being discussed and the following is mentioned:

The outer face of $G$ is bounded by a simple closed polygon $C$. Let $b$ and $b_{d}$ denote the total number of vertices of this polygon and the number of those vertices that have degree $d$ in $G$, respsectively. Clearly, $b = b_{2} + b_{3} + b_{4} + b_{5}$. The internal angle of $C$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$, and the sum of these angles is $(b-2)\pi$. Hence, $b_{2} + 2b_{3} + 3b_{4} + 4b_{5} \leq 3b-6$.

My interpretation of this is that we look at the boundary of our graph $G$, and note that it is a closed polygon. The angles of this polygon at a particular vertex (namely, one of degree $d$ in the graph $G$) is the "the internal angle of $C$ at a vertex of degree $d$"

EDIT 2: I apologize, there seems to be more background that I need to mention in order for this to make sense. As mentioned in my comment directed towards Will Jagy, the following condition is to hold for our graph $G$ in the plane. Consider a set $P$ of $n$ points with minimum distance 1, and connect two elements of $P$ by a segment if and only if their distance is exactly 1. Thus, we obtain a graph $G$ embedded in the plane. For my case, I want to consider a set $P \subseteq \mathbb{S}^2$ of $n$ points with minimum distance $\frac{\pi}{3}$, and connect two elements of $P$ by a great arc if and only if their distance is exactly $\frac{\pi}{3}$.

Hopefully that was the last edit, but I will reiterate exactly what my question is.

Where does the condition come from in $\mathbb{E}^2$ that, "the internal angle of $C$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$". Can a similar condition be generalized to my case on $\mathbb{S}^2$?

Surface Eversions: Generalizing from Sphere and Torus Eversions

2012-05-11T19:43:37Z

In 1958, Smale proved that a $2$-sphere can be "turned inside out", and throughout the 60s, 70s, and 80s, explicit constructions such as Thurston Corrugations, and Minimax eversions were developed to visualize this sphere eversion. I just encountered a recent youtube video: Torus Eversion, which depicts the eversion of a torus. My general question is then this,

Is there a characterization, by Euler characteristic, genus, or some other topological invariant, for which surfaces have eversions?

If not a characterization of all such surfaces which have eversions, is there a finite list of surfaces which can be everted?

Generalizing the circle packing theorem to 3-dimensions

2012-05-07T17:58:24Z

The circle packing theorem (Koebe–Andreev–Thurston theorem) states that every finite planar graph is the nerve of some disk packing in the plane, where the nerve of a packing $P$ is a graph $G=(V,E)$, where there is an edge $(u,w) \in E(G)$ when $\partial P_{u} \cap \partial P_{w} \neq \varnothing$, for disks $P_{u},P_{w} \in P$.

More succintly, for every connected simple planar graph $G$ there is a circle packing in the plane whose intersection graph is (isomorphic to) $G$.

I am interested in the possibility of extending this result to dimension three, where we would be considering a homogeneous connected simplicial $3$-complex as the nerve of a sphere packing $P$.

Has there been any research done to suggest that such a theorem exists in three dimensions, or a counterexample that this is not the case?

How would generalizing simplicial sets affect $(\infty,1)$-functors between $(\infty,1)$-categories?

2012-03-14T19:52:42Z

The simplex category $\Delta$ is defined as the category of (non-empty) finite ordinals and order preserving maps. Furthermore, a simplicial set $X$ is defined as a contravariant functor $X: \Delta \rightarrow \text{Set}$.

I am interested in the possibility of generalizing the notion of a simplicial set by considering the category of infinite ordinals $\mathcal{O}$, if such a thing exists, and then defining an $\infty$-simplicial set as $X^{\infty}: \mathcal{O} \rightarrow \text{Set*}$, where $\text{Set*}$ is the appropriate adjustment of the category of small sets $\text{Set}$ such that mapping from objects in the category of infinite ordinals will still satisfy contravariance.

Assuming such a generalization exists, how does this affect the geometric definition of an $(\infty,1)$-category? Is there no longer a capturing of the geometric model desired from simplicial sets or can something more general than an $(\infty,1)$-category be defined? It would also be interesting to see how this would change $(\infty,1)$-functors between simplicial to sets to some other type of functor between $X^{\infty}$ sets. What would natural transformations look like, if they could still be defined properly?

EDIT: I asked this question to a graduate student who is doing work in $\infty$-categories, and he said that you would not get the same geometric model you want by quasicategories if you allowed infinite ordinals. Does this make sense to anyone? He said, that by taking the geometric realization "you probably wouldn't get anything back", but I don't really know what to make of that.

EDIT 2: This question has really been interesting me, and I can't find anything on it in Lurie's Higher Topos Theory or any other literature I have looked through. It seems like any time an author introduces the idea of a simplicial set to aid in defining quasicategories they don't think about possible variations on the simplex category that might change the entire construction they are making into something completely different. Let me know if you want a more specific question to answer!

How many models of Peano arithmetic are isomorphic to the standard model and how many models of Peano arithmetic are non-standard?

2012-03-24T19:21:15Z

I am currently writing a paper on non-standard models of Peano arithmetic and I am having trouble finding references or information that discuss the relative sizes of how many models of Peano arithmetic there are in the standard and the non-standard cases.

I see it quoted all over the place that, "It is familiar that there are continuum-many pairwise non-isomorphic countable models of $\mathsf{PA}$". From this I take it that there are $\mathcal{c}$-many ($\aleph$-many) non-standard models of Peano arithmetic. Where can I find a proof of this fact? How many models of Peano arithmetic are there that are isomorphic to the standard model?

Thank you!

Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$

2012-03-20T07:43:33Z

Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this sequence of regular godel numbers using a super godel number, to get $$2^{g_{0}} \cdot 3^{g_{1}} \cdot 5^{g_{2}} \cdot ... \cdot \pi_{n}^{g_{n}}$$ where $\pi_{n}$ is the $n+1$-th prime number. Then, define $Prf(m,n)$ to hold just if $m$ is the super godel number of a sequence of wffs that is a $\mathsf{PA}$ proof (Peano Arithmetic) of the closed wff with regular godel number $n$.

I am working on a much wider question to do with Rosser provability, but I am stuck inside of a fifth subproof, where I simply need to show that from $Prf(k,\ulcorner \neg \urcorner \star \ulcorner 0 =1 \urcorner) \wedge Prf(c,\ulcorner 0=1 \urcorner)$, that I can prove $c \neq k$, where $m \star n$ is the standard concatenation function. Here is the start of my attempt, although I am certain there is a very simple way!

Assume $c=k$. Further assume that $(\ulcorner \neg \urcorner \star \ulcorner 0=1 \urcorner)=(\ulcorner 0=1 \urcorner)$. Then, $$2^{1} \cdot 3^{21} \cdot 5^{15} \cdot 7^{23} \cdot 11^{21} = 2^{21} \cdot 3^{15} \cdot 5^{23} \cdot 7^{21}$$ by the standard godel coding of, $\neg: 1, 0: 21, =:15,S:23$, where $S$ is the successor function. This contradicts the fundamental theorem of arithmetic, so $(\ulcorner \neg \urcorner \star \ulcorner 0=1 \urcorner) \neq (\ulcorner 0=1 \urcorner)$.

Here is where I am stuck. I know previously in the proof that $Prf(k,\ulcorner \neg \urcorner \star \ulcorner 0 =1 \urcorner)$ and $Prf(c,\ulcorner 0=1 \urcorner)$, so how can I derive a contradiction to conclude that $c \neq k$?

Any help is greatly appreciated and if necessary I can explain more of the background problem, but I am certain that this part of the proof can be solved independently without relying on anything else other than simple logic and the definitions I have provided. I suspect that it has something to do with the uniqueness of the super godel number; namely, that there does not exist a number $n$ which is the super godel number of both $\ulcorner \neg \urcorner \star \ulcorner \varphi \urcorner$ and $\ulcorner \varphi \urcorner$. Yet I cannot represent my intuition formally!

Answer by Samuel Reid for Background for classic forcing

2012-03-17T22:47:40Z

There is an article by Timothy Chow that gives background motivation and eases you in to forcing called "A beginner's guide to forcing"; it is of an expository nature, but there is still technical detail.

Another article I would recommend would be "A cheerful introduction to forcing and the Continuum Hypothesis" by Kenny Easwaran; it is more technical than the first paper I linked but still very accesible to anyone with basic experience with Set Theory and Model Theory.

Explicit tetrahedralizations of closed 3-manifolds and connections between convex polytopes and hyperbolic knot complements

2012-01-20T02:55:23Z

There are three consistent ways to glue opposite faces of a dodecahedron to get a closed 3-manifold. With a $\frac{1}{10}$ twist we receive the Poincaré dodecahedral space, with a $\frac{3}{10}$ twist we receive the Seifert-Weber space, and with a $\frac{5}{10}$ twist we receive the 3-dimensional real projective space. I've been using the CurvedSpaces software for visualizing these manifolds and coming from a Convex Geometry perspective I have some questions that I thought I would pass by here before I spent more time researching it if the idea is complete garbage.

It was explained to me that as a Corollary of Moise's Theorem there must exist a tetrahedralization of any orientable closed 3-manifold. I am interested in what an explicit tetrahedralization of some closed 3-manifold would look like, especially for the three manifolds mentioned above that are generated by gluing opposite faces of the dodecahedron. The reason why I am interested in this, is that I want to have a concrete understanding of a small class of examples for which I can investigate the explicit tetrahedra which tessellate the manifold. With a deeper understanding and some explicit examples I was hoping to work on classifying hyperbolic knot complements by the convex polytopes that tessellate them. So, my question is the following:

Question:

What do explicit tetrahedralizations of closed 3-manifolds look like? In particular, for the Poincaré dodecahedral space, the Seifert-Weber space or any hyperbolic knot complements. How can I determine the explicit vertex coordinates of the tetrahedra that tetrahedralize the manifold?

I've come up with a method for determining "Intermediary Polytopes" given two distinct polytopes, and a string of conjectures relating to how these intermediary polytopes may tetrahedralize certain manifolds, but I need some sort of explicit vertex positions in order for some of the machinery I have constructed to work.

If anyone has done research on this in the past I will accept a reference to a paper as an answer, otherwise I would like an actual answer to my question if it not too vague. If it is too vague, please ask questions in the comments and I can sharpen my question in response.

Under what conditions does $\mathcal{M} \vDash \mathsf{PA}$ and $\mathcal{K} \vDash \mathsf{PA}$ such that $\mathcal{M} \ncong \mathcal{K}$?

2012-03-11T20:25:59Z

I'm currently learning some introductory model theory from Marker's "Model Theory: An Introduction", Kaye's "Models of Peano Arithmetic", and Hodges' "Model Theory", and I am confused by the Wikipedia article on Peano Arithmetic. I am interested in the question I posed in the title and this article is really confusing me.

It states there that,

A model of the Peano axioms is a triple $(\mathbb{N}, 0, S)$, where $\mathbb{N}$ an infinite set, $0 \in \mathbb{N}$ and $S : \mathbb{N} \rightarrow \mathbb{N}$ satisfies the axioms. Dedekind proved in his 1888 book, What are numbers and what should they do (German: Was sind und was sollen die Zahlen) that any two models of the Peano axioms (including the second-order induction axiom) are isomorphic. In particular, given two models $(\mathbb{N}_A, 0_A, S_A)$ and $(\mathbb{N}_B, 0_B, S_B)$ of the Peano axioms, there is a unique homomorphism $f : \mathbb{N}_A \rightarrow \mathbb{N}_B$ satisfying, $$f(0_A)=0_B$$ and $$f(S_{A}(n))=S_{B}(f(n))$$ and it is a bijection.

Doesn't Tennenbaums theorem, and the existence of non-standard models, show that not all models of peano arithmetic are isomorphic? If this is the case, then what result did Dedekind actually prove and does anyone know where I can find a reference to the theorem he proved or a proof of it?

Moise's Theorem and the Fundamental Domain of a $3$-Manifold

2012-03-09T19:42:51Z

I'm currently researching the relationship between Moise's Theorem (Every closed $3$-manifold has a triangulation) and other properties of manifolds. In particular, I'm trying to learn about the fundamental domain of a manifold and I want to know where I can find a formal definition online (or a reference to a popular book that would be in most university libraries, the one book that I heard does have it is "A textbook of topology" by Seifert, but my university does not have the book).

Let $\mathcal{M}$ be a topological space satisfying the conditions to be a topological $n$-manifold (locally euclidean, Hausdorff, second countable). From what I understand, if we have some group action $G(\phi)$ on $\mathcal{M}$, then the fundamental domain of $\mathcal{M}$ is some set of points from $\mathcal{M}$ such that the orbits of that set of points covers all of $\mathcal{M}$ (let me know if this is incorrect).

In the context of closed $3$-manifolds, I also want to have that $\mathcal{M}$ has a maximal smooth atlas $\mathcal{A}$ (for every two coordinate charts in the domain of $\mathcal{M}$, the transition map between these charts is a diffeomorphism). Given that Moise's Theorem permits that there is an essentially unique piece-wise linear structure, how can I learn about the correlation between this linear structure and the fundamental domain of $\mathcal{M}$? I can't come up with any connections, but for motivations to do with Theoretical Physics, I suspect that the structure guaranteed by Moise's Theorem and the fundamental domain are related (I won't digress).

Essentially, my question is two-fold:

1) Where can I find a reference that discusses (In some technical detail) the fundamental domain of a manifold, and maybe in particular a $3$-manifold?

2) Is there any connection between Moise's Theorem for $3$-manifolds and the fundamental domain of a $3$-manifold? That is to say, can some technique such barycentric subdivison or something else generate one from the other? I'm looking for something of that flavour.

Reference Request: Non-Standard Models of PA

2012-03-02T00:32:10Z

I am attempting to write an expository paper on non-standard models of PA that is accesible to students taking an introductory graduate course in mathematical logic (covering Godel's incompleteness theorems, the diagonalization lemma, models, etc.). In this paper I want to give an explanation of some results such as Tennanbaum's Theorem (there does not exist a countable recursive model of PA that is not isomorphic to the standard model). By, "give an explanation of", I mean to actually work through an explanation of the proof, some of the techniques involved, and the general overlap between techniques used in the proofs of Tennanbaum's theorem, some theorems proven by Rosser on extensions of PA, Robinson's overspill lemma, etc. (Note: I want to avoid digressing into an explanation of forcing if possible).

My question is, what books or online resources do you know of that would be useful for me? That is, do you happen to know of surveys of these topics that are around on arXiv or JSTOR? I have been digging through the mathematical logic section of arXiv for papers and I found a few that are useful, but I thought that some mathematicians/logicians on MO might know of some papers that give a just survey of the introductory results regarding non-standard models of PA.

Thank you!

Answer by Samuel Reid for What is the metamathematical interpretation of knot diagrams?

2012-01-30T06:06:29Z

It seems that you may trust algebra more as a solid foundation for how to describe a mathematical object, so you may be interested in the classification of knot diagrams by knot polynomials, such as the Jones Polynomial.

Additionally, you can note by Alexander's Theorem that every knot can be created by the closure of some braid. Since braids can be defined by a braid group "word", we can describe a particular knot diagram by a word in this language. For example, if we have $\sigma_{1} \sigma_{2}^{-1} \sigma_{1} \sigma_{1} \sigma_{2}$, then it describes some knot diagram and is easier to work with algebraically.

These are, to my understanding, two common approaches to employing the power of algebra to analyze knots by converting knot diagrams into some algebraic representation.

3-manifold theorem reference request or proof

2012-01-18T04:23:48Z

The following is a theorem of which I have great interest in but cannot find anything about on the internet,

Every 3-manifold of finite volume comes from identifying sides of some polyhedron

I'm fairly certain that "identifying sides of some polyhedron" may be a simplification of the technical terminology. I believe it is just referring to gluing faces of polyhedron to form closed 3-manifolds. Such examples are given by the Seifert-Weber space, the Poincare homology sphere, the 3-dimensional real projective space, the $\frac{1}{2}$ twist cube space, etc. I'm assuming the proof is based off of Moise's theorem and proceeds as follows,

Let $M$ be an arbitrary closed 3-manifold. By Moise's theorem we have that $M$ can be tetrahedralized, so we let $T$ be the tetrahedralization of $M$ consisting of tetrahedrons $t_{1},...,t_{n}$. Pick an arbitrary tetrahedra $t_{1}$ of $T$ and proceed to glue $t_{2}$ to $t_{1}$, forming a new polyhedron $P_{2}$, and then glue $t_{3}$ to $P_{2}$ resulting in $P_{3}$, and so on. After all tetrahedra $t_{1},...,t_{n}$ have been glued, we have some resulting polyhedron $P_{n}$. From here, then somehow show that $P_{n}$ can be glued to $M$?

Any references to papers, expository writing, a proof of, or even the formal statement and name of this theorem would be greatly appreciated!

Comment by Samuel Reid

2013-06-15T05:10:03Z

Thanks! I can't believe I didn't see that, too much geometry dulls the mind I suppose.

Comment by Samuel Reid

2013-06-06T00:17:02Z

@Alexander Woo: I'm not sure how term order would affect this and give me a grobner basis of $ x_{11}^2 + x_{12} x_{21}=0 $. Care to expand upon your idea?

Comment by Samuel Reid

2013-06-05T21:24:12Z

@Abhinav Kumar: I already tried using the Grobner basis command built into SAGE but it did not compute what I wanted. I will add an edit to my question including this example. I am interested in any alternative techniques to computing a Grobner basis.

Comment by Samuel Reid

2013-05-17T19:10:38Z

@Victor Protsak: What do you mean by "Macaulay seems more likely to have something of this kind." Any references you could point me to?

Comment by Samuel Reid

2013-04-12T08:45:08Z

@Martin Rubey: Ok thanks! :)

Comment by Samuel Reid

2013-04-12T01:15:39Z

@Martin Rubey: Are you referring to the formula for $a(n)$?

Comment by Samuel Reid

2013-03-02T20:51:35Z

@Henry Cohn: I did not notice the comment about the kissing number in nilgeometry before, thank you for pointing that out! I am already collaborating with Szirmai, so I will ask him about it. It's good to hear that there is interest in this idea, I will send you a message in the future if I end up writing a paper on this topic!

Comment by Samuel Reid

2013-03-01T16:43:28Z

@Henry Cohn: I have seen Szirmai's paper regarding packing density in the Thurston Geometries and although it is interesting, does not refer to the kissing number problem. It seems to be unstudied in the more obscure of the Thurston Geometries, so I think I will work on research regarding this topic! The point of my question was to find out if it had been done before, and if not, then I have free range to solve an interesting problem.

Comment by Samuel Reid

2013-02-26T19:58:24Z

You should try posting this question on math.stackexchange.com, as this is not a research level question.

Comment by Samuel Reid

2013-02-22T21:48:16Z

It's been up there for a day and hasn't got much activity, so I thought I'd ask it here, too.

Comment by Samuel Reid

2013-02-11T16:54:22Z

@Wouter Stekelenburg: I'm confused about how you could "give that name to either $\exists$ or $\forall$ and have your modalities being the pullback." If this is the case, then I would be interested in defining this as I think there are interesting properties that you could prove given that you can category-theoretically describe the modal operators of a theory. Do you have a more thorough description of this, or a reference that I can look at? It's not that your answer is unsatisfactory, but I don't fully understand it and want to find out where you know this from.

Comment by Samuel Reid

2013-02-11T07:11:09Z

@David Roberts: Thank you for the response, it seems that when you are initially learning about these topics that you end up asking the wrong questions due to a lack of understanding. If you are willing to give an explanation of how to construct the syntactic category, I would love to read it!

Comment by Samuel Reid

2013-02-06T17:16:33Z

@Peter LeFanu Lumsdaine: Your comment is very interesting to me and I can't find many references on the topic you alluded to. Have you thought of anything I could look up regarding this? Possibly a survey article, or at least a journal article which defines the words you are using in the context of modal logic? Thanks

Comment by Samuel Reid

2012-12-01T20:40:50Z

@Richard Kent, $C_{n}([0,1]) = \Delta^{n}$ and $C_{\hat{n}}([0,1]) = \coprod_{i=1}^{n!} \Delta^{n}$.

Comment by Samuel Reid

2012-09-02T17:16:40Z

Vote to close... this question should be tried over at math.stackexchange.com