User squark - MathOverflow

Are there sampNP-intermediate problems?

2012-12-28T13:18:01Z

This questions is approximately cross-posted from theoretical computer science stackexchange

Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$. Can we generalize this to the theory of average-case complexity?

What evidence can be brought for/against the idea that any $(S, X) \in \mathsf{sampNP}$ is either in $\mathsf{sampP}$ or $\mathsf{sampNP}$-complete? Here $S$ is a language and $X$ is a distribution: a probabilistic polynomial time algorithm which generates strings of length $n$ given input $1^n$

A theorem by Shoening allows generalization of Ladner's theorem to many cases. However, it doesn't cover the current question for two reasons

The first reason is that we're considering classes of distributional problems rather than classes of languages. This feels like a technicality that can be dealt with by generalizing Shoening's theorem

The second reason is that the result crucially depends on the fact that $\mathsf{P}$ is recursively presentable. On the other hand $\mathsf{sampNP} \cap \mathsf{sampP}$ doesn't seem to be recursively presentable. For any unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$ we can recursively present distributional problems in $\mathsf{sampNP}$ for which the probability of error decreases at least as fast as $n^{-f(n)}$ however there seems to be no way of allowing the condition to hold for some $f$. This would be possible if there was a recursive enumeration of unbounded functions $f_i: \mathbb{N} \rightarrow \mathbb{N}$ s.t. for any computable unbounded function $g: \mathbb{N} \rightarrow \mathbb{N}$, there is $i$ s.t. $f_i$ grows slower than $g$. However there is no such enumeration as can be seen by a diagonalization argument

The second reason feels to me like a conceptual breakdown of Shoening's reasoning for this case

Imagliazzo's proof of Ladner's theorem fails even more spectacularly in this setting since the padding employed there yields a language whose density diminishes with superpolynomial speed and therefore is trivially in $\mathsf{sampP}$. At least this is so for natural $\mathsf{sampNP}$-complete problems since their distributions are close to uniform

SAT and Arithmetic Geometry

2012-12-06T13:43:11Z

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note though that the system is represented in non-trivial manner). The reason it is OK to consider more than one equation is because the conjunction of the conditions $f_i(x_1 ... x_n) = 0$ is equivalent to the single condition $\prod_i (f_i(x_1 ... x_n) + 1) + 1 = 0$.

This reminds of the solution of Hilbert's 10th problem, namely that it is undecidable whether a system of polynomial equations over $\mathbb{Z}$ has roots. Is there a formal relation? Can we use the undecidability over $\mathbb{Z}$ to provide clues why the problem is hard over $\mathbb{F}_2$ (that is, $P \ne NP$)? What is known about decidability and complexity for other rings? In particular, what is known about complexity over $\mathbb{F}_p$ for p prime > 2?
The system of polynomial equations defines an algebraic scheme. Is it possible to find algebro-geometric conditions on this scheme, s.t. something can be told about the complexity of SAT restricted to such schemes?
The solutions of our system of polynomial equations are the fixed points of the Frobenius endomorphism on the corresponding variety over $\bar{\mathbb{F}}_2$. There is a variant of Lefschetz's fixed-point theorem which relates the existence of such points to $l$-adic cohomology. Can this be used to provide some insight on P vs. NP?

Non-uniform complexity of the halting problem

2012-12-03T11:37:27Z

This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: http://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem

What can be said about the non-uniform circuit complexity $C(n)$ of the halting problem? Obviously it is $O(2^n)$ as any other decision problem. However I don't know any non-trivial bound.

A related measure of complexity is the time-complexity $T(n)$ with infinite advice (i.e. we allow an extra-tape in our Turing machine which carries an infinite-amount of information in the initial state). This also gives the obvious upper bound $O(2^n)$ by storing an infinite look-up table on this tape.

The two measures of complexity are related as follows. Consider $R_n$ a family of circuits solving a decision problem $S$. Then we can construct an infinite-advice program $H$ for solving $S$ by encoding $R_n$ as advice. This yields

$$T(n) = O(n C(n) \ln C(n))$$

On the other hand if we have $H$ an infinite-advice program solving $S$, we can construct the circuit $R_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so

$$C(n) = O(T(n)^2)$$

Note that if the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma_2$). To see this consider $S \subset \lbrace 0,1 \rbrace^*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q_x$: "Loop over all $p \in \lbrace 0,1 \rbrace^*$, halt if $V(x,p) = 1$". The size of $Q_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice

If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy

It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial

Finite-dimensional subgroups of circle diffeomorphism group

2011-07-08T17:37:44Z

Is there a sequence of connected finite-dimensional subgroups Gi of the circle diffeomorphism group G with the following properities:

(a) Gi is contained in Gj for i < j

(b) The union of Gi is dense in G

More rigorously "finite dimensional subgroup of circle diffeomorphism group" means a Lie group H with smooth faithful action on the circle.

In order to make sense of property (b) I have to specify a topology on G. I suspect that all reasonable topologies will yield the same answer, but for the sake of definiteness let's use the "sup-norm" topology. That is, given two diffeomorphism g1 and g2, I define the distance d(g1, g2) as

supremum over x in S1 of d(g1(x), g2(x))

Here the latter d is the usual distance on the circle. This is a metric and it induces a topology.

I suspect that the answer to my question is "no". Moreover, I suspect that there is no H as above with dimension > 3. But I might be wrong...

Module categories over symmetric/braided monoidal categories

2012-02-18T12:54:45Z

Given an algebraically closed field $k$ and a finitely generated commutative $k$-algebra $A$, all simple modules over $A$ are 1-dimensional

What is the analogous statement for symmetric monoidal $k$-linear categories?
What is the analogous statement for braided monoidal $k$-linear categories?

We can assume the category is Abelian and the product functor is right exact in both variables

I expect something of the sort "any simple (in some sense) module category is equivalent to $Vect$", although I have no idea how braided and symmetric are different in this repsect

Role of fiber functor monoidal structure in Tannakian bialgebra reconstruction

2012-02-14T21:50:18Z

Shahn Majid presents in section 9.4 of "Foundatations of Quantum Group Theory" a Tannaka-type reconstruction theorem for producing a $k$-bialgebra out of its $k$-linear monoidal category of modules $\mathcal{M}$. The theorem depends on the presense of a fiber (fogetful) functor $F: \mathcal{M} \rightarrow Vect_k$ and monoidal structure on $F$. The question is:

Is there a stronger reconstruction theorem in which $F$ carries no monoidal structure?

If not, it means there should be an example with different monoidal structures on $F$ yielding different coproducts in the bialgebra. Is there such an example?

Category of modules over a coPoisson-bialgebra

2012-02-08T14:30:05Z

Fix a ground commutative ring $k$. A coPoisson-bialgebra is a bialgebra $H$ equipped with a linear mapping $\pi:H \rightarrow H \otimes_k H$ s.t.

$\pi$ is a coLie bracket
$\pi$ is a coderivation
$\pi(ab) = \Delta(a)\pi(b)+\pi(a)\Delta(b)$

I'm mostly interested in the case of cocommutative $H$. For such $H$, coPoisson structure is morally an infinitesimal deformation away from cocommutativity (the structure needed for "coquantization" preserving bialgebra structure). Also, I'm mostly interested in the Hopf algebra case but this doesn't seem important for the question

The category of left modules over $H$ is a $k$-linear Abelian category (just because H is a $k$-algebra) equipped with a tensor product functor (due to the coproduct $\Delta$ on H). For cocommutative $H$ the tensor product is symmetric. The question is:

What additional structure(s) on this category are obtained from $\pi$?

EDIT: I think I figured out the answer in case $k$ is a field. In this case the tensor product functor is exact (rather than just right exact)

Introduce $h$ a formal parameter satisfying $h^2=0$. $\pi$ defines a "deformed" coproduct on $H[h]$ given by

$$\Delta'(a):=\Delta(a)+h\pi(a)$$

Thus the category of left $H[h]$-modules becomes a tensor category

Denote $\mathcal{M}$ our symmetric tensor category. The tensor product functor is $\otimes$ and its symmetric braiding is $b: X \otimes Y \rightarrow Y \otimes X$

We construct the Abelian category $\mathcal{M}[h]$. An object $X$ in $\mathcal{M}[h]$ is an object in $\mathcal{M}$ equipped with an endomorphism $h: X \rightarrow X$ s.t. $h^2=0$. A morphism in $\mathcal{M}[h]$ is a morphism in $\mathcal{M}$ which commutes with $h$

$\mathcal{M}[h]$ comes with the following functors of interest:

$Ker \space h: \mathcal{M}[h] \rightarrow \mathcal{M}$
$Coker \space h: \mathcal{M}[h] \rightarrow \mathcal{M}$
$i: \mathcal{M} \rightarrow \mathcal{M}[h]$ which sends $X$ to itself with $h=0$
$[h]: \mathcal{M} \rightarrow \mathcal{M}[h]$; Given $X \in \mathcal{M}$ we define $X[h]$ to be $X \oplus X$ equipped with the obvious action of $h$

The desired additional structure is:

An exact $k[h]$-linear tensor product functor $\hat{\otimes}$ on $\mathcal{M}[h]$
Tensor functor strucutre on $Coker \space h$

The antisymmetry of $\pi$ imposes the following additional condition:

Note that $i(X) \hat{\otimes} Y \cong X \otimes Coker \space h_Y$ which follows by observing that $h$ annihilates $i(X) \hat{\otimes} Y$ due to $k[h]$-linearity of $\hat{\otimes}$, applying $Coker \space h$ and using its tensor functor structure

We have the short exact sequence

$$0 \rightarrow X \xrightarrow{Ker \space h} X[h] \xrightarrow{Coker \space h} X \rightarrow 0$$

We apply $\hat{\otimes} Y[h]$ and use its exactness to get the short exact sequence

$$0 \rightarrow X \otimes Y \rightarrow X[h] \hat{\otimes} Y[h] \rightarrow X \otimes Y \rightarrow 0$$

This sequence yields an element $\epsilon(X, Y)$ of $Ext^1(X \otimes Y, X \otimes Y)$

Due to $b$, $\epsilon(X, Y)$ and $\epsilon(Y, X)$ belong to canonically isomorphic spaces. We demand

$$\epsilon(X, Y)+\epsilon(Y, X)=0$$

The problem is I need the case in which $\otimes$ is merely right exact. What currently confuses me is that in the bialgebra picture the last sequence is still exact for general $k$ but I can't prove it in the category-theoretic language

Is there an "Abelian envelope" 2-functor?

2012-02-11T21:33:40Z

I'm looking for a notion of an Abelian category $\mathcal{A}$ "generated" by a given category $\mathcal{C}$

More precisely I need something along the following lines. Denote $\mathcal{Ab}_2$ the 2-category of Abelian categories and $\mathcal{Cat}$ the 2-category of categories. We have the forgetful 2-functor $\mathcal{F}: \mathcal{Ab}_2 \rightarrow \mathcal{Cat}$. Is there an adjoint 2-functor $\mathcal{G}: \mathcal{Cat} \rightarrow \mathcal{Ab}_2$ ?

I suspect the answer is "yes" because it can be constructed along the following lines. Denote $\mathcal{Ab}$ the category of Abelian groups. For any category $\mathcal{C}$, the category $\mathcal{Hom(C, Ab)}$ is Abelian. Moreover, we have the natural functor $\mathcal{i:C \rightarrow Hom(Hom(C,Ab),Ab)}$. Thus $\mathcal{C}$ is embedded in the Abelian category $\mathcal{D:=Hom(Hom(C,Ab),Ab)}$ and we can take the Abelian category generated by $\mathcal{C}$ within $\mathcal{D}$. The result is supposed to be $\mathcal{G(C)}$

However, the only construction I managed to search up is the Karoubi envelope which generates a pseudo-Abelian category. So either my purported construction is wrong or simply not popular. Which is it?

EDIT: I realized my construction amounts to $\mathcal{G(C):=Hom(C,Ab^{op})}$. At least for small $\mathcal{C}$ this is indeed adjoint to $\mathcal{F}$, provided we interpret $\mathcal{Ab_2}$ as having right exact functors for 1-morphisms. Here $\mathcal{C}$ embeds by applying opposite Yoneda and taking the freely generated Abelian group.

Conformal transformations and harmonic analysis on the sphere

2011-11-26T21:22:15Z

Consider the $n$-dimensional sphere $S^n$. I'm especially interested in the $n=4$ case. The Hilbert space $L^2(S^n)$ can be decomposed into a direct sum of eigenspaces of the Laplacian, which are finite dimensional. I'm looking for non-isometric conformal transformations

$$f: S^n \to S^n$$

s.t. for some $\lambda, \mu > 0$ if $\psi$ is an eigenvector of the Laplacian with eigenvalue $\alpha < \lambda$ then $f(\psi)$ is a sum of eigenvectors with eigenvalues $< \mu$.

Do such $f$ exist? If so, is it possibly to classify them?

Quantum sheaves

2011-11-26T21:49:05Z

Are the following definitions known?

Consider H a Hilbert space. A "quantum topology" on H is a set Sigma of closed subspaces satisfying the following conditions:

(a) {0} and H lie in Sigma

(b) If {V_alpha} is a subset of Sigma then the closure of the sum of the V_alpha lies in Sigma

Given a quantum topology, we introduce the notion of s a "quantum sheaf of operators"

s corresponds to every V in Sigma s(V), a C*-algebra of bounded operators on V. We demand the following conditions on s:

(i) If W lies in V, A lies in s(V) and leaves W invariant, then the restriction of A to W lies in s(W)

(ii) Suppose {W_alpha} is a subset of Sigma and V is the closure of their sum. Suppose A is a bounded operator on V which leaves every W_alpha invariant. Suppose further that the restriction of A to W_alpha lies in s(W_alpha) for every alpha. Then A lies in s(V)

(iii) Suppose {W_alpha} is a subset of Sigma and V is the closure of their sum. Consider C the subalgerba of s(V) consisting of operators of the form defined by condition (ii). Then the commutant of C lies within C.

Answer by Squark for Are all quantum cellular automata invertible & representable?

2011-10-29T12:25:47Z

Niel de Beausdrap found this article. The authors (Schumacher and Werner) propose a definition of quantum cellular automata and prove they are always invertible (Corrolary 7 on p. 10). Nominally their definition is different since they use the norm-completion of the algebra $A_\Gamma$ and impose a locality condition. However, it is actually equivalent.

Their locality condition states that the image of $A_x$ has to be contained in $A_S$ for some finite S. However, if we avoid the norm completion it holds automatically since any element of the direct limit is in $A_S$ for some finite S and $A_x$ is finite dimensional.

Moreover, an endomorphism of $A_\Gamma$ is always continuous hence extends to the completion. This is because the matrix norm can be defined algebrically as the maximal |lambda| for which a*a - lambda is non-invertible.

Representability follows from their Theorem 6 on p. 10 which gives a rather explicit (modulo some complicated constraints) description of all nearest-neighbour quantum cellular automata. As discussed on p. 9 this description encodes two finite-dimensional unitary operators. These operators can be easily used to construct the operator $U$ I seek.

As discussed on p. 8 the case of non-nearest-neighbour can be easily reduced to this case

Are all quantum cellular automata invertible & representable?

2011-10-20T21:43:25Z

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition (though I probably consider it my own out of ignorance rather than originality). This definition seems very natural but immediately raises several questions which I find difficult to answer. Here I ask the two questions that seem the most fundumental. Here it goes:

Fix $V$ a complex inner product vector space of finite dimension $n$. Consider $A$ the *-algebra End($V$). Take $\Gamma = \mathbb{Z}^d$ a lattice. Define the *-algebra $A_\Gamma$ (quantum cellular automaton observables) in the following manner. Assign to each element $x$ of $\Gamma$ a copy $A_x$ of $A$. To each finite subset $S$ of $\Gamma$ we can correspond the *-algebra $A_S$ defined by

$A_S$ := Tensor product of $A_x$ over $x \in S$

For two finite subsets $S$, $R$ of $\Gamma$ with $S$ contained in $R$ we have the morphism

$i_{S,R}$: $A_S \rightarrow A_R$

obtained by tensoring with $1 \in A_y$ for all $y \in R\backslash S$. We define $A_\Gamma$ to be the direct limit of $A_S$ w.r.t. $S$.

Denote $T_\Gamma$ the group of translations of $\Gamma (Z^d)$. $T_\Gamma$ acts on $A_\Gamma$ in the obvious manner.

A quantum cellular automaton is defined to be a *-endomorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. An invertible quantum cellular automaton is defined to be a *-automorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. The 1st question is:

Are all quantum cellular automata invertible?

Any unit vector $v \in V$ defines a state

$\phi_v$: $A_\Gamma \rightarrow C$

in the following manner. Suppose $S$ is a finite subset of $\Gamma$ and for any $x \in S$, $a_x$ is an element of $A_x$. Then we have $a_S$ an element of $A_S$ (and hence of $A_\Gamma$) defined by

$a_S$ := tensor product of $a_x$ over $x \in S$

We then define

$\phi_v(a_S)$ := product of $(v, a_x v)$ over $x \in S$

It is easy to see this extends uniquely to a linear map $\phi_v$: $A_\Gamma \rightarrow C$ and that the map is a state.

Fix $v$ in $V$. We construct the Hilbert space $H_v$ in the following manner. Choose $v_1$ ... $v_n$ an orthonormal basis of $V$ s.t. $v_1 = v$. Consider maps

$\alpha: \Gamma \rightarrow {1 ... n}$

s.t. $\alpha(x) = 1$ for all $x$ except a finite set. Define $J$ to be the set of such $\alpha$. To each $\alpha \in J$ we assign the basis vector $\Psi_\alpha$ of $H_v$, thought of as

$\Psi_\alpha$ := tensor product of $v_\alpha(x)$ over $x \in \Gamma$

Thus $H_v$ is defined to be $l^2(J)$. It is easy to see that $H_v$ thus defined depends only on $v$ and not on $v_2$ ... $v_n$ i.e. that for any two choices of $v_2$ ... $v_n$, there is a canonical isomorphism between the corresponding Hilbert spaces.

There is a natural *-homomorphism

$\rho$: $A_\Gamma \rightarrow B(H_v)$

where $B(H_v)$ is the *-algebra of bounded operators on $H_v$. Thus, any unit vector $\Psi \in H_v$ defines a state

$\phi_\Psi$: $A_\Gamma \rightarrow C$

$\phi_\Psi(a) = (\Psi, \rho(a) \Psi)$

Now, fix an invertible quantum cellular automaton $f$: $A_\Gamma \rightarrow A_\Gamma$. Suppose $v$ in $V$ is s.t. $\phi_v$ is $f$-invariant. Then $f$ is called $v$-representable if there exists

$U$: $H_v \rightarrow H_v$

a unitary operator s.t. for any $\Psi \in H_v$ we have

$\phi_U \Psi = f^*(\phi_\Psi)$

It is clear that if such $U$ exists it is unique.

The 2nd question is:

Is any invertible quantum cellular automaton $v$-representable for any $v$ with $\phi_v$ $f$-invariant?

Mappings between states on *-algebras

2011-10-07T22:34:21Z

Consider finite-dimensional (for-simplicity) $\star$-algebras, that is, unital associative algebras over the complex numbers equipped with an antilinear antiautomorphism $\star$.

A state on a $\star$-algebra $A$ is a linear mapping $\psi: A \to \mathbb{C}$ satisfying

(i) $\psi(1) = 1$ [normalization]

(ii) $\psi(a^*) = \overline{\psi(a)}$ [reality]

(iii) $\psi(a^*a) \geq 0$ [positivity]

Denote $s(A)$ the set of all states on $A$.

Consider the following 2 ways to construct a mapping between states on different algebras:

(1) Consider $A$, $B$ $\star$-algebras and $f: A \to B$ a $\star$-homomorphism. Then we have $f^{-1}: s(B) \to s(A)$ defined by $f^{-1}(\psi)(a) := \psi(f(a))$.

(2) Consider $A$, $B$ $\star$-algebras and $\phi$ a state on $B$. Then we have $t_\phi: s(A) \to s(A \otimes B)$ defined by $t_\phi(\psi)(a \otimes b) = \psi(a) \phi(b)$.

Now, suppose we compose any number of mappings of the above 2 kinds. We get for any $\star$-algebras $A$, $B$, a certain class of mappings $s(A) \to s(B)$. I.e., these are mappings obtained by composing mapping of the above 2 kinds while inserting any number of intermediate algebras. Denote this set of mappings $\mathrm{Mor}(s(A), s(B))$.

Given a $\star$-algebra $A$, the positive cone of $A$ is the set of all linear combinations of elements of the form $a^*a$ with positive coefficients. Denote it $p(A)$.

Consider $A$, $B$ $\star$-algebras and $L: A \to B$ a linear mapping (not necessarily a homomorphism!) preserving 1 and $\star$. Suppose $L$ is positive in the sense that it maps $p(A)$ to $p(B)$. Then $L$ induces $L^{-1}: s(B) \to s(A)$ defined by $L^{-1}(\psi)(a) = \psi(L(a))$.

The Question:

Is $L^{-1}$ guaranteed to be in $\mathrm{Mor}(s(A), s(B))$?

Finite-dimensional subgroups of diffeomorphism groups

2011-07-09T18:03:42Z

This question is a generalization of my previous question about the circle to arbitrary manifolds.

Is there a smooth manifold M with the following property.

There exists a sequence of connected finite-dimensional subgroups Gi of M's diffeomorphism group G such that

(a) Gi is contained in Gj for i < j

(b) The union of Gi is dense in G

To remove doubt, "finite dimensional subgroup of M's diffeomorphism group" means a Lie group H with smooth faithful action on M.

The answer to my previous question established that S1 is not such a manifold. I suspect that the answer to the general question is still "no". However, the proof would have to be more sophisticated since in the case of S1 we had essentially a closed list of possible "Hs".

There is another closely related question. Fix a smooth manifold M. Consider connected Lie groups H with faithful and transitive smooth action on M. Is there an upper bound of H's dimension? For S1 the answer was "yes, 3".

Answer by Squark for projective geometry question

2011-07-09T19:00:55Z

Plane projective transformations can be viewed as linear operators in a 3D vector space V. A circle (more generally an ellipse) in the projective plane P(V) corresponds to a cone C in V. Such a cone is the vanishing locus of an indefinite quadratic form Q on V. Thus the operators we look for are operators preserving Q. In physical lingo, V is a 3D Minkowski space and the operators are Lorentz transformations. They can be described as follows. Choose a basis e1, e2, e3 for V in which Q takes canonical form

-1 0 0

0 1 0

0 0 1

One family of Q-preserving operators is the rotations you mentioned:

1 0 0

0 cos(alpha) -sin(alpha)

0 sin(alpha) cos(alpha)

Another family consists of hyperbolic rotations (in physical lingo, boosts):

cosh(theta) sinh(theta) 0

sinh(theta) cosh(theta) 0

0 0 1

Analogously, we have hyperbolic rotations in another plane:

cosh(theta) 0 sinh(theta)

0 1 0

sinh(thata) 0 cosh(theta)

We can form a product of 3 matrices, with one of each family. This will yield a general operator of the desired form. This is completely analogous to decomposition of 3D rotations into rotations around separate axes (i.e. Euler angles). Note that 3D rotations are operators preserving a definite quadratic form

A property of "Schwartz" quadratic forms

2010-12-02T11:24:52Z

Consider $K(x, y)$, $f(x)$ Schwartz functions and $g(y)$ a tempered distribution. Suppose $$K(x, y) = K(y, x)$$ Define

$$h(t) = \int f(x - t) K(x, y) g(y - t) dx dy$$

It appears to me $h(t)$ is a Schwartz function. I'd be glad if anyone can prove / disprove it.

Thx!

Some thoughts so far:

The assumption of symmetry on K is probably redundant. If we take K to be $$K(x, y) = u(x)v(y)$$ for u, v Schwartz, we get $$h(t) = [\int f(x - t)u(x)dx][\int g(y - t)v(y)dy]$$ Now, the 2nd factor is probably smooth of slow (at most polynomial) growth whereas the 1st factor is Schwartz. $h(t)$ is thus Schwartz. Linear combinations of such "factorized" kernels are dense in the entire Schwartz space, but I still don't see how to deduce the claim from this.

Lebesgue measure on Frechet space?

2010-11-28T18:38:57Z

It is well known that there are no Lebesgue measures on infinite-dimensional Banach spaces (see e.g. http://en.wikipedia.org/wiki/There_is_no_infinite-dimensional_Lebesgue_measure). However, I couldn't find anything about Lebesgue measures on infinite-dimensional Frechet spaces. The question seems very natural in the context of creating a mathematically rigorous definition of the path integral of quantum field theory.

So: 1. Can an infinite-dimensional Frechet space have a measure which is locally finite, strictly positive and translation-invariant? 2. Can a separable infinite-dimensional Frechet space have a measure which is locally finite, non-zero and translation-invariant?

The motivation for the formulations of 1+2 are that the analogous statements for Banach spaces are false. 2 is more important for me since all interesting examples as separable, as far as I can tell.

If such measures exist, I'd be glad to get some references on whatever is known about them.

Thx!

Comment by Squark

2013-01-15T19:05:25Z

"If NP is a subset of P/poly, then the polynomial hierarchy collapses to Sigma^2": This is actually an upper bound on the power of non-uniformity since it shows NP is probably not in P/poly

Comment by Squark

2012-12-28T19:54:21Z

@SamHopkins : I'm using the terminology of O. Goldreich. If your "DistP" is his "tcpP" (i.e. the analogical definition with distributions for which the probability of being in a given lexicographic interval is computable in polynomial time) then the question still makes sense for it. I'm not sure about AvgP and HeurP with which I'm not familiar. You can find the definition of sampP in the cstheory.stackexchange link where I spell it out

Comment by Squark

2012-12-06T18:03:22Z

Thank you for your answer!

Comment by Squark

2012-12-06T18:03:10Z

Thank you for your answer!

Comment by Squark

2012-12-06T18:00:56Z

Thanks a lot for your answer!

Comment by Squark

2012-12-06T17:58:37Z

Thanks a lot for your answer! I want to point out that I realize very well the distinction between decidability and computability. However, my naive intuition tells me that a problem which is close to an undecidable problem must have high complexity. For example the halting problem is undecidable whereas deciding whether a program halts in k steps is EXP-complete. Deciding whether a program halts on every output is even higher in the undecidability hierarchy (I think) whereas deciding whether a program halts on every output in k steps is NEXP-complete

Comment by Squark

2012-12-06T15:00:17Z

@Dima Pasechnik : This is obvious. I asked about complexity over finite fields and decidability for other (infinite) rings

Comment by Squark

2012-12-06T13:56:39Z

Consider an equilateral polygon. $alpha_m = (m - 2) \pi / m$, thus $m^2 alpha_m = m(m - 2) \pi$ which is unbounded

Comment by Squark

2012-12-03T18:32:11Z

Thank you for your answer!

Comment by Squark

2012-12-03T12:41:22Z

How is the question related to algebraic geometry?

Comment by Squark

2012-12-03T12:29:42Z

You probably know this but just in case: for $d < 3$, $v_b$ = 1 for any $b$

Comment by Squark

2012-02-19T20:36:53Z

You mean your Omega is a linear subspace?

Comment by Squark

2012-02-19T20:06:50Z

Thx. Can you provide a reference please?

Comment by Squark

2012-02-18T17:08:54Z

Noah you completely misunderstood my intention. Probably I need to reformulate. I am not asking about algebra objects in symmetric monoidal categories. I'm trying to categorify the statement i.e. consider module categories over symmetric monoidal categories. A module category $\mathcal{M}$ over a symmetric monoidal category $\matcal{A}$ is a category equipped with a linear (or even right exact) bifunctor $\otimes: \mathcal{A} \times \mathcal{M} \rightarrow \mathcal{M}$ satisfying the appropriate conditions

Comment by Squark

2012-02-18T17:01:27Z

This is interesting. What if I allow for quasibialgebras too?