User łukasz grabowski - MathOverflow

Algebraicity of the "outer" boundary of the Mandelbrot set

2013-03-11T10:32:08Z

Let $M$ be the Mandelbrot set and let $\lambda\in M, \mu\in \mathbb C$ be algebraic numbers. Let $t_{\lambda,\mu}$ be defined as $$ t_{\lambda,\mu} = \sup \lbrace t\in \mathbb R\colon \lambda +t\mu \in M\rbrace. $$

Question: Is $t_{\lambda,\mu}$ an algebraic number?

(If it's any easier - I'm also interested in the case when $\lambda$ and $\mu$ are both Gaussian rationals.)

pointwise ergodic theorem and mean sojourn time

2013-02-08T11:20:29Z

Originally posted on Maths StackExchange, but repositing here because of getting no answer there. Not a research question really - I'm just confused by implications between various ergodic theorems. So I'll happily close the question if deemed inappropriate.

Let $G$ be a group and let $F_i$ be a sequence of finite subsets of $G$. Suppose $G$ acts on a probability measure space $(X,\mu)$ in a measure preserving way, and suppose that this action is ergodic.

Let us say that $F_i$ satisfies pointwise ergodic theorem iff for almost all $x\in X$, and all $f\in L^1(X)$ we have that the limit of $$ \frac{1}{|F_i|} \sum_{g\in F_i} f(g.x) $$ exists and is equal to $\int_X f\, d\mu$.

Let us say that $F_i$ satisfies mean sojourn time theorem iff for every measurable $U\subset X$ and almost every $x\in X$ we have that the limit of $$ \frac{1}{|F_i|} |\lbrace g\in F_i\colon g.x \in U\rbrace | $$ exists and is equal to $\mu(U)$.

Question 1: It is easy to see that if $F_i$ satisfies pointwise ergodic theorem then it also satisfies mean sojourn time theorem. Is it also the other way around?

A reference would be most appreciated (I imagine that the answer in the general case is the same as in the case when $G$ is the infinite cyclic group, so a reference for the latter case would also be fine.)

A related question:

Question 2: Is there a proof of the mean sojourn theorem for say $\mathbb Z$ which doesn't use the pointwise ergodic theorem?

Are amenable groups topologizable?

2012-11-27T18:42:34Z

I've learned about the notion of topologizability from "On topologizable and non-topologizable groups" by Klyachko, Olshanskii and Osin (http://arxiv.org/abs/1210.7895) - a discrete group $G$ is topologizable iff there exists a topology on $G$ which makes it into a Hausdorff non-discrete topological group.

Main question: Is every infinite amenable group topologizable?

Main motivation for this question is that perhaps naively non-topologizability seemed to me such a strange property that I hoped it could be used to show existence of non-sofic groups.

Question: Is there an infinite non-topologizable sofic group?

After failing to prove that sofic groups are topologizable I thought it would be still interesting to prove that infinite "elementary sofic" groups are topologizable. Elementary sofic groups are for the purpose of this discussion the class of "groups which are provably sofic by current methods", i.e. it contains all amenable groups, is closed under taking free products amalgamated over amenable groups, extensions with sofic kernel and amenable quotient, /any other results which are in the literature/, and with the property that if G is residually elementary sofic then G is elementary sofic.

Question: Is there an infinite non-topologizable elementary sofic group?

Unfortunately my plan to answer the above question negatively failed at step 1, and hence the Main question.

Answer by Łukasz Grabowski for What recent discoveries have amateur mathematicians made?

2010-10-30T20:47:30Z

Greg Egan. He's a very renowned science fiction writer who holds a bachelor degree in mathematics. He wrote, as a coauthor, 2 articles which were published in peer-reviewed journals, one of them is with John Baez. The first one was written when he was approximately 40 years old.

There's also more eccentric example of Andrew Beal, which is much more known in the world of poker. He made however one minor conjecture in number theory for whose proof or disproof he offers $100,000.

And there's also a list on wikipedia which might be worth going through.

"Uncertainty principle" for self-adjoint operators in a finite von Neumann algebra

2012-03-20T17:37:54Z

Let $M\subset B(\mathcal H)$ be a finite von Neumann algebra of bounded operators on a Hilbert space $\mathcal H$., let $P\in M$ be a self-adjoint operator with a pure-point spectrum (for example a projection), and let $T\in M$ be another self-adjoint operator.

The question will be formulated in the case of $P$ being a projection. Let $\mathcal H_0$ and $\mathcal H_1$ be the eigenspaces of $P$.

Question: Is there a well-studied condition on $P$ and $T$ which would imply that there exists $\epsilon$ such that whenever $U\subset \mathcal H$ is a "generalized eigenspace" of $T$ (i.e. the image of a spectral projection of $T$) then there exists $u\in U$ of norm $1$ such that $u=h_1+h_2$, $h_1\in \mathcal H_1$, $h_2\in \mathcal H_2$, and the norm of $h_2$ is at least $\epsilon$?

In particular (EDIT: the previous version had a weeker ergodicity assumption, in which case the answer is negative, by the answer of Steven Deprez below)

Question: If a discrete group $\Gamma$ acts freely and in a measure preserving way on a probablity measure space $X$, each element of $\Gamma$ acts ergodically, $M=L^\infty(X) \rtimes \Gamma$, $P$ is the characteristic function of some subset of $X$ of positive measure, and $T = \sum_{\gamma\in \Gamma} f_\gamma \gamma$, where $f_\gamma$ are real-valued positive functions on $X$ such that $\sum f_\gamma=1$; do $T$ and $P$ fulfill the property from the question?

algorithms for comparing two simplicial complexes

2011-12-14T12:50:01Z

Given a set $A$ of subsets of ${1, \ldots n}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and gluing is induced by containment of subsets)

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$?)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone. Please note that the size of the input can be exponential in $n$.

In principle $A$ and $B$ might consist of $2^n$ subsets, so this is a lower bound for the problem, because the algorithm needs to read the input.

On the other hand the trivial algorithm of checking each permutation takes at most $\mathcal O(2^n\cdot n!)$ steps.

3-SAT and a matrix of linear forms representing a non-degenerate matrix

2011-12-07T18:11:27Z

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.

As before, let $k$ be a field with $p$ elements. Consider the following computational problem.

Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

Problem: Is there an assignment of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

On the one hand, we have a trivial algorithm of checking all the possible assignments for $X_{ij}$, and for each such assignment checking by Gauss elimination whether the resulting matrix is invertible. This takes time bounded by a polynomial in $p^{n^2}$.

On the other hand, Emil Jeřábek showed previously that we can encode a 3-SAT instance consisting of $n$ clauses into a $3n\times 3n$ matrix of linear forms which is invertibe iff the 3-SAT instance is satisfiable. Assuming exponential time hypothesis this gives a lower bound on the problem above of the form $O(2^{\delta n})$ for some $\delta>0$.

Question 1 Is there an algorithm for the problem above, whose execution time is bounded by a polynomial in $p^{n^\alpha}$ for $\alpha <2$?

Question 2 Is there a natural number $k$ such that one can encode a 3-SAT instance with $n^\beta$ clauses into a problem as above for a $kn\times kn$ matrix, for $\beta>1$?

determining if a matrix of linear forms represents a non-degenerate matrix

2011-12-06T17:40:24Z

Let $k$ be a field with $p$ elements. Consider the following computational problem

Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

Problem: Is there an assignement of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

${}$

Question: What is known about algorithms for this problem?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

The naive algorithm of checking each assignment of the variables $X_{ij}$ takes time bounded by a polynomial in $p^{n^2}$. I'd be interested to know if there is an improvement to polynomial in $p^n$ (or better).

EDIT: Below Emil Jeřábek shows that the problem is NP-complete, but the reduction from 3-SAT is done in such a way that it still could be that there is an improvement to $p^n$ without proving anything unexpected about 3-SAT.

EDIT: The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved below by Emil Jeřábek.

EDIT: I've decided to ask a more specific follow-up question.

Answer by Łukasz Grabowski for expected number of overlapping edges from k cycles in a graph

2011-12-04T21:04:41Z

For simplicity of notation assume that the tree is $3$-regular (apart from the boundary) and that in your question we assume that we are interested only in those pairs of edges whose ends are all different.

Let $a$ and $b$ be two vertices in $\mathcal T$, not in the boundary. Let $p$ be the path joining them. Taking $p$ out leaves $4$ connected components. Denote $\mathcal T_a^1, \mathcal T_a^2$ the connected comopnents which touch the vertex $a$ and similarly for $b$. Then the number of pairs of edges such that their cycles intersect each other precisely in $p$ is $$ F(p):=(|\mathcal T_a^1|\cdot |\mathcal T_b^1|\cdot|\mathcal T_a^2|\cdot |\mathcal T_b^2|)^2, $$ because either [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^1$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^2$] or [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^2$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^1$].

So to get the probability that the intersection is of length exactly $k$, you need to sum-up $F(p)$ over all paths $p$ of length $k$ which don't touch the boundary, and divide it by the number of all pairs of edges which is $\frac{1}{8}\cdot n(n-1)(n-2)(n-3)$ (because we assume the edges have disjoint ends.)

Rokhlin lemma for arbitrary infinite groups.

2011-11-10T11:13:23Z

Let $G$ be an at most countable discrete group acting freely on a standard probability measure space $X$ in a measure preserving way.

It is well known that if $G$ is a finite group then this action admits a fundamental domain. As pointed out by Andreas below, by Rokhlin lemma, if $G$ contains an element of infinite order we can find an $(\varepsilon, N)$-fundamentalish domain $U$, where the latter is defined as follows:

Call a set $U\subset X$ an $(\varepsilon, N)$-fundamentalish domain iff there exist $N$ elements $g_1, \ldots, g_N$ of $G$ such that the sets $g_i(U)$ are pairwise disjoint and the measure of their union is at least $1-\varepsilon$.

Question: If $G$ is an infinite group, $N_0$ is a natural number, $\varepsilon_0$ is a positive real number, does there exist an $(\varepsilon, N)$-fundamentalish domain with $\varepsilon<\varepsilon_0$ and $N>N_0$?

For example when the action is profinite and "transitive on each level", then clearly answer is positive: there exist $(0,N)$-fundamentalish domains for arbitrary large $N$.

Presentations of PSL(2, Z/p^n)

2011-10-26T21:34:26Z

As is well known, the group $PSL(2,\mathbb Z)$ is isomorphic to the free product $C_2 \ast C_3$ of cyclic groups of order $2$ and $3$. Call the generators of the cyclic groups $S$ and $T$.

Problem: Given a prime number $p$ and a natural number $n$, write a presentation of the quotient $PSL(2, \mathbb Z/p^n\mathbb Z)$ with the images of $S$ and $T$ as generators.

presentations of Sp(n, Z) and cocycles.

2011-10-24T16:40:06Z

Question: where can I find explicit presentations of the group $Sp(n, \mathbb Z)$, for small $n$?

It is known that $Sp(n, \mathbb Z)$ admits a $2$-cocycle $h$ with values in $\mathbb Z/2\mathbb Z$ which I'd like to view in the following way. If we fix a presentation with relations forming a set $R$, then $h$ is a function $R \to \mathbb Z/2\mathbb Z$ (which fulfils some condition).

Question: where can I find an explicit description of this cocycle, in the form of what values does it take on elements of some presentation?

Proability of a word being fulfilled in the symmetric group

2011-10-19T09:34:26Z

Let $S_n$ be the symmetric group on $n$ letters, let $g\in S_n$ be a fixed element of order, say, roughly $n^2$ (e.g. two large disjoint cycles of coprime length), let $w(a,b)$ be a reduced word in letters $a$, $b$, $a^{-1}$, $b^{-1}$.

Question: What is the number of those $h\in S_n$ such that $w(g,h)=1$?

I'm interested in all kinds of information (e.g. asymptotic behaviour when $n\to \infty$, restrictions on $w$, what if order of $g$ is significantly different,...).

Which Turing machines accept the language of trivial words in a finitely presented group?

2011-05-27T12:23:35Z

Let $G$ be a finitely presented group with generators $g_1, g_1^{-1},\ldots, g_n, g_n^{-1}$. Let $L(G)$ be the language of all those words in $g_1, \ldots, g_n$ which represent the trivial element of $G$. It's well known that there exists a Turing machine $T$ which accepts $L(G)$ (it doesn't necessary always stop).

Conversely, given an alphabet $A$ consisting of symbols $g_1, g_1^{-1}, \ldots, g_n, g_n^{-1}$, and a language $L$ on $A$ accepted by a Turing machine $T$ it's easy to give neccesary and sufficient conditions on $L$ so that for some group $G$ we have $L=L(G)$. Namely $L$ should be closed under (1) concatanation (2) reductions and additions of the terms $g_ig_i^{-1}$ and $g_i^{-1}g_i$, (3) "conjugation" i.e. given $w\in L$ the words $gwg^{-1}$ and $g^{-1}wg$ are also in $L$.

Question 1. Is there a set of conditions on a Turing machine $T$ which assures that the language $L(T)$ accepted by $T$ fulfills the conditions (1)-(3) above?

For the purpose of this question "a set of conditions" means an algorithm which always stops, which takes as the input a Turing machine $T$, and if $L(T)$ fulfills (1)-(3) then the algorithm returns YES (if it returns NO then it can be either way).

Of course I'm interested in algorithms which output YES on a possibly big set of Turing machines.

Question 2. Is there an algorithm as above which returns YES exactly on the set of those machines $T$ such that $L(T)$ fulfills conditions (1)-(3).

"double" semidirect product

2011-07-06T14:46:22Z

Let $A$, $B$ and $C$ be discrete countable groups. Let $\alpha$ be an action of $A$ on $B$ and let $\beta$ be an action of $B$ on $C$.

Question Does there always exist a group $G$ which has $A$, $B$ and $C$ as subgroups and such that the group generated by $A$ and $B$ is $A\ltimes B$ and the group generated by $B$ and $C$ is $B\ltimes C$?

One obvious situation when such a group $G$ exists is when the action $\beta$ extends to an action of $A\ltimes B$. Then we can take $G=(A\ltimes B)\ltimes C$. But I'm interested in situations when $\beta$ doesn't extend.

For example take $A$ to be the infinite cyclic group with generator $t$, $B$ to be the free group on infinitely many generators indexed by $\mathbb Z$ (denote the generators by $g_n, n\in \mathbb Z$), and $C$ to be the rational numbers. Let $g_n$ act on $C$ by multiplication by $n$ if $n\neq 0$ and by identity for $n=0$, and let $t$ act on $B$ by sending $g_n$ to $g_{n+1}$.

Question In this specific situation does there exist $G$ as above?

Decomposition of a dynamical system into ergodic componenents

2010-11-02T16:39:00Z

Quick version of the question. Let $(X, \mu)$ be a probability measure space and let $Z$, the group of integers, act on $X$ in a measure preserving way. How can I decompose $X$ into ergodic componenets? More precisely, can $X$ be equivariantly decomposed into a countable union of subspaces $U_i$, each of which is isomorphic to a product $A_i\times B_i$, such that action on $U_i$ is a product of an ergodic action on $A_i$ and the trivial action on $B_i$?

One can ask the same question also for groups other than integers.

My motivation

I'm currently learning basics of ergodic theory. More precisely, I'm interested in the notion of cost. Let me recall it for group actions: Let a countable discrete group $G$ act on a probability measure space $(X,\mu)$ in a free and probability measure preserving (pmp) manner. Call the action $\rho$. Let $\mathcal R(\rho)$ be the equivalence realtion on $X$ given by $\rho$ (i.e. two points of $X$ are equivalent iff there's a group element which sends one point to the other). Let $F=(U_i,g_i)_{i=1}^\infty$ be a countable family of pairs, where each $U_i$ is a measurable set, and each $g_i$ is an element of $G$. Let $\mathcal R(F)$ be the equivalence relation on $X$ generated by the relation $x \sim y$ iff for some $i$ we have $x\in U_i$ and $\rho(g_i)(x)=y$. Define $$ cost(F) = \sum \mu(U_i), $$ and let cost of the action $\rho$ be the infimum of numbers $cost(F)$ over all families $F$ such that $\mathcal R(F) = \mathcal R(\rho)$, perhaps after restricting both relations to subsets of measure $1$.

Theorem. Let $\rho$ be a free pmp action of $\mathbb Z \times H$, where $H$ is any countable group. Then $cost(\rho)=1$

Suppose first that restriction of the action $\rho$ to $\mathbb Z$ is ergodic. Fix $\varepsilon$. Then for the family $F$ choose pairs $(X, t), (A_1, h_1), (A_2,h_2) \ldots $, where $t$ is a generator of $\mathbb Z$, $h_i$ is an enumeration of elements of $H$, and $A_i$ is any set such that $\mu(A_i)= \frac{\varepsilon}{2^i}$.

Clearly $cost(F) \le 1 + \varepsilon$, so it's enough to see that $\mathcal R(F) = \mathcal R(\rho)$. Take a point $x$ of $X$ and fix $h_i\in H$. We're gonna show that, with probability $1$, $x$ is in relation with $\rho(h_i)(x)$. By the ergodic theorem, since we assume action of $\mathbb Z$ is ergodic, with probability $1$ for some $j$ we have $\rho(t^j)(x)\in A_i$, so we have $x \sim \rho(t^j)(x) \sim \rho(h_it^j)(x) \sim \rho(h_i)(x)$.

When I heard the argument it wasn't even mentioned that we assume that restricion to $\mathbb Z$ is ergodic. Intuitively it's clear what to do - choose $A_i$ more cleverly, "perpendicular to ergodic components of $\mathbb Z$".

Question. Which theorem from ergodic theory allows to make this choice of $A_i$ "perpendicular to ergodic components" precise?

Answer by Łukasz Grabowski for Decomposition of a dynamical system into ergodic componenents

2011-07-05T17:23:32Z

This is the answer Damien Gaboriau told me to the question from "my motivation" section. We can assume that the measure space is the interval $X=[0,1]$. Suppose we have a measured equivalence relation on $X$ whose equivalence classes are infinite countable. We want to show there exists a meaurable subset of $X$ of arbitrary small measure which intersects almost all equivalence classes.

Note that the map $x\mapsto I(x)=$ "infimum of the class of $x$" is measurable, so for almost all points $x$ the point $I(x)$ is not in the class of $x$, because otherwise we would have a measurable selector which is impossible. So assume for simplicity that $I(x)$ is never in the class of $x$. Then consider the family of sets $B_\epsilon$ for $\epsilon\in \mathbb R_+$. $B_\epsilon$ is the union $$ \bigcup_{x\in X} B(I(x), \epsilon)\cap E(x), $$ where $B(a,b)$ is the ball with center $a$ and radius $b$, and $E(x)$ is the equivalence class of $x$. The sets $B_\epsilon$ are a descending family with trivial intersection, so they have arbitrary small measures, but each of them intersects all classes.

Answer by Łukasz Grabowski for Extending a bi-invariant metric from a set of generators to the whole group.

2011-06-11T14:38:02Z

No, it's not always possible. Take $G$ to be the cyclic group of order $20$, let $g$ be its generator. Let $S =$ { $g,g^3,g^{17},g^{19}$ }. Define $d$ on $S$ by putting $d(g,g^3)=2$ and all the other distances equal to $1$.

Now, the pair $(g,g^3)$ is not in the same "$(S\times S)$-orbit" as $(g^{17},g^{19})$, and therefore the above defines a bi-invariant metric on $S$, but it is in the same $G\times G$-orbit, so it cannot be extended to a bi-invariant metric on $S$.

word problem in free Burnside groups (and other torsion groups)

2011-06-02T10:58:58Z

Question 1. Is it known that for some free Burnside groups the word problem is undecidable?

Provided that the answer is negative, what about the following easier question.

Question 2. Is there a known example of a finitely generated (and preferably finitely presented) group $G$ and an integer $k$ such that all elements of $G$ have order at most $k$ and the word problem in $G$ is undecidable?

"topological" conjugacy of group automorphisms

2011-05-11T14:37:34Z

In the paper "Orbit Equivalence and Topological Conjugacy of Affine Actions on Compact Abelian Groups", S. Bhattacharya shows (Theorem 3) the following:

Theorem. Given two actions $\alpha$ and $\beta$ of a discrete group $\Gamma$ on a compact connected metrizable abelian group $K$ by continuous group automorphisms the following are equivalent:

there exists a homeomorphism $F\colon K \to K$ such that $\alpha_\gamma= F\beta_\gamma F^{-1}$ for every $\gamma\in \Gamma$.

there exists a continuous group automorphism $F\colon K \to K$ such that $\alpha_\gamma = F\beta_\gamma F^{-1}$ for every $\gamma \in \Gamma$.

By passing to the Pontryagin dual this becomes a statement about discrete countable torsion-free abelian groups. My question concerns the generalization to non-abelian groups.

Question. Given two actions $\alpha$ and $\beta$ of a discrete group $\Gamma$ on a discrete countable torsion-free group $G$ by group automorphisms, are the following equivalent?

there exists an automorphism of the reduced $C^*$-algebra of $G$ which conjugates the actions induced by $\alpha$ and $\beta$

there exists an automorphism of $G$ which conjugates $\alpha$ and $\beta$.

This question is also interesting when we restrict the attention fo $\Gamma = \mathbb Z$ (i.e. to pairs of automorphisms.)

Example of a non-normal infinite index subgroup of a non-amenable group with certain properties.

2011-03-23T15:54:24Z

This is an improved version of my previous question, where I forgot to put one of the assumptions.

Question. Let $G$ be a finitely generated non-amenable discrete group, and $H$ be a subgroup of $G$ of infinite index, such that no finite-index subgroup of $H$ is normal in $G$. Can it happen that the index of the normalizer $N(H)$ of $H$ in $G$ is finite, and the Schreier graph of $G/H$ has subexponential growth?

If the answer is yes, I would very much like to see an example. It would be especially nice if $G$ could be taken to be a property $(T)$ group.

I hope I got everything right this time, but if the question is very easy then please point out the example in the comments, so that I can improve the question without starting a new thread.

The motivation for the question is that out of such an example one can construct an ergodic, faithful, non-free action of a non-amenable group whose equivalence relation is amenable. (Most likely such examples have been known before.)

EDIT: There's not enough space in the comments to answer Jesse's question below so I answer it here. I haven't thought the construction exactly through, but it should work like this: the Borel space is $X:=${0,1}${}^{G/H}$, and the action is induced by action of $G$ on $G/H$. There's a theorem (of Kaimanovich?) which says that if there is a graphing of a relation such that each component is of subexponential growth then the relation is amenable. In our case connected components are Schreier graphs so our relation is amenable, no matter what measure we put on the Borel space.

The measure is not the product measure. In $G/H$ we have (disjoint) images $C_i$ of $[G:N(H)]$ cosets of $N(H)$. Call $C_i$ "cosets" as well. The measure is supported on those sequences which are non-zero on at most one of the cosets $C_i$. So as a measure space $X$ is the union of $[G:N(H)]$ spaces {0,1}${}^{C_i}$. On each of these subspaces of $X$ the measure is defined to be the product measure normalized by $\frac{1}{[G:N(H)]}$.

The action is not essentially free, because H stabilizes {0,1}${}^C_0$, where $C_0$ is the trivial coset of $N(H)$.

I'm not sure about faithfulness, if I find a good argument why it's faithful I'll add it here. Also, I don't see anymore why I wanted $H$ to have no finite index subgroups which are normal in $G$, although it seemed important to us when we discussed it couple of days ago...

amenable equivalence relation generated by an action of a non-amenable group

2011-03-23T16:30:16Z

Question. Give a (possibly elementary) example of a probability measure preserving action $\rho\colon G \curvearrowright X$ of a finitely-generated discrete group $G$ on a standard borel space $X$ with a probability measure, such that

the equivalence relation generated by $\rho$ is ergodic and amenable,

the action $\rho$ is faithful,

the group $G$ is non-amenable.

A friend of mine asked me this question couple of days ago, which led us to another question, but perhaps there is an easier way to provide an example.

Example of an infinite index subgroup of a non-amenable group whose normalizer is of non-zero finite index, and such that the Schreier graph is of subexponential growth

2011-03-22T11:06:49Z

EDIT: In this question I forgot to put one of the assumptions, and the question was easier than it should be. Here is the revised question. Please vote to close this question as it is no longer relevant.

Question. Let $G$ be a finitely generated non-amenable discrete group, and $H$ be a subgroup of $G$ of infinite index. Can it happen that the index of the normalizer $N(H)$ of $H$ in $G$ is finite greater than $1$, and the Schreier graph of $G/H$ has subexponential growth?

If the answer is yes, I would very much like to see an example. It would be especially nice if $G$ could be taken to be a property $(T)$ group.

Is this number already known to be transcendental? Is there a survey about up-to-date trascendence results?

2011-02-14T11:10:49Z

Is the number $\sum_{n=1}^\infty \frac{1}{2^{n^2}}$ known to be transcendental?

Is there a survey with up-to-date transcendence results?

Is every bounded representation of Z unitarisable when all sets are measurable?

2011-01-25T14:02:26Z

For the purpuse of this question, a group is amenable iff there exists a Foelner sequence.

Dixmier unitarisability problem asks whether a (countable discrete) group G is amenable iff every bounded representation of G on a Hilbert space is unitarisable.

The problem is currently not solved, but at least argument "=>" is not very difficult: let G be amenable and let $\rho\colon G \curvearrowright H$ be a bounded representation. We need to make a new scalar product on $H$ for which $\rho$ is unitary, and such that vectors of norm one in the old product have norms bounded from above in the new product (so that the identity mapping on $H$ is continuous) and bounded from below in the new product (so that $H$ with the new product is complete).

Let $F$ be a mean on $G$. For a pair of vectors $v,w$ consider a function $f_{vw}$ on $G$: $g \mapsto \langle gv, gw \rangle$, define the new scalar product as $\langle v, w \rangle_{new} := F(f_{vw})$. It's easy to check that this new product has the desired properties.

But in the proof we used axiom of choice, because we use the mean on $G$. I tried to figure out a proof which uses less than a full or almost full axiom of choice, but so far I failed.

Question. Is the above implication true in a set of axioms in which also the statement "every subset of R is measurable" is true?

Maybe it's easier to answer this question specifically for the infinite cyclic group Z. Note that Z is amenable, according to our definition of amenability, in Zermelo-Fraenkel set theory.

Even if the anser is no, I'd be interested to learn about the proof of the above fact which uses less than Boolean prime ideal theorem (AFAIU using only BPIM is easy, because to prove existence of a mean one uses Banach-Aleoglu theorem, which uses Tychonoff theorem for Hasudorff space, which, according to wikipedia, uses only BPIM)

Which categorical (coproduct-like) operation captures integration of measures?

2011-01-08T18:31:44Z

Suppose we have a measure space $(X,a)$, a measurable space $Y$ and for every $x\in X$ we have a measure $b_x$ on $Y$. Suppose that $(Z,c)$ is a measure space such that as a measurable space $Z=X\times Y$ and the measure $c$ is the integral of measures $b_x$ with respect to the measure $a$.

I have a vague intuition that $(Z,c)$ is a coproduct of the family $(Y,b_x)$ along $(X, a)$

Question: Is there a category of measure spaces and a categorical construction in it which captures this intuition?

One could ask a similar question about a category of Hilbert spaces and integrals of Hilbert spaces over measure spaces, and preferably the "categorical construction" in question should also answer this problem.

The categorical construction in question should preferably be similar to coproduct, and it would be very nice if it actually was a coproduct in some category.

On the other hand, maybe my vague intuition is wrong, and comments on that would also be appreciated.

Answer by Łukasz Grabowski for Graph properties: definability and decidability

2011-01-10T13:49:03Z

I, like gowers in the comments, don't think it is a question which have anything to do with graphs in particular, as soon as you define graph property to be something recognizable by a Turing machine.

Indeed you can enumerate graphs by natural numbers (for example by enumerating the possible adjacency matrices) Then the set of graphs having a given property in your sense is precisely a recursive set of natural numbers.

Now, for every recursively enumerable set A of natural numbers there exists a polynomial p such that $$ x \in A \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0), $$ which, afaiu, is a kind of a definition in a logical language you're after.

Answer by Łukasz Grabowski for Construction of a maximal ideal

2011-01-02T23:23:01Z

This is an expansion of the comment of Qiaochu Yuan.

As mentioned in the comments there can be no "constructive" description. However, maybe you'll find this (tautological) construction useful: take any sequence $m_n$, $n=1,2,\ldots$ of real points which diverges to infinity. Choose an ultrafilter $U$, and define $M$ to be the set of those functions $f$ for which there exists an element $K$ of $U$ (so in particular $K$ is a subset of natural numbers) such that $f(m_k)=0$ for $k\in K$.

It's obvious that $M$ contains your set $I$ and that it is closed under multiplication by elements of $R$. That it is additively closed follows from the fact that $U$ is a filter, and that it is maximal follows from the fact that $U$ is an ultrafilter.

So $M$ is "as explicit" as $U$ is. In particular all functions which vanish on all but finitely many points of the sequence $m_n$ are in $M$.

Also, you can take your favourite explicit filter $U'$ and define the ideal $M'$ as above, and have a non-maximal but explicit ideal which contains $I$.

Answer by Łukasz Grabowski for Properties of a non-sofic group

2010-10-30T21:30:32Z

Sofic groups fulfill determinant conjecture.

This implies in particular that there exists a natural constant $c$ such that given a matrix $M$ over the integral group ring of a given sofic group $G$, we have that $$ |tr_{vN} \exp(-cM) - \dim_{vN}\ker M| < \frac{1}{3}. $$

This can be used to show that some problems about the group are decidable. Suppose a group $G$ is torsion-free, has decidable word problem, fulfills Atiyah conjecture, and is sofic. Then there is an algortihm which decides whether a given matrix $M$ over the integral group ring has non-trivial kernel, as an operator on $[l^2(G)]^{\dim M}$.

Indeed, given $M$ it's easy to bound its $l^2$ norm and based on this to decide how many terms in $tr_{vN}\exp(-cM)$ have to be computed in order to be less than $\frac{1}{6}$ from the actual value of $tr_{vN} \exp(-cM)$. Call this approximation $a$ (it can be computed since the word problem is decidable). Now, because $G$ is torsion free and fulfills Atiyah conjecture, we know that $\dim_{vN}\ker M$ is an integer, and it's equal to $0$ iff $M$ has trivial kernel. So $M$ kas trivial kernel if and only if $a<\frac{1}{2}$

Similar algorithm works if a group has bounded torsion, since $\frac{1}{3}$ in the first equation can be exchanged with any postivie real number. I seem to have read that there exist Tarski monsters with decidable word problem. That means that in principle :-) one could try to show that there's no such algorithm for these Tarski monsters and arrive at the conclusion that either these monsters are non-sofic or they don't fulfill Atiyah conjecture.

Given two linear operators A and B over a finite field, is there a third operator C whose kernel is the intersection of kernels of A and B?

2010-10-29T12:10:51Z

Let $V$ be a finite dimensional linear space over a finite field $k$. Let $A$ and $B$ be two endomorphisms of $V$.

Question 1. Is there an endomorphism $C$ of $V$, which is expressed in terms of some "natural operations" on $A$ and $B$, and whose kernel is the intersection of kernels of $A$ and $B$?

By "natural operations" I mean some analogue of the recipe which works over complex numbers: choose a scalar product on $V$ and take $C:= A^{\ast}A + B^{\ast}B$. Indeed, $A^{\ast}A$ is a positive operator whose kernel is the same as the one of $A$, same for $B^{\ast}B$, and kernel of a sum of two positive operators is the intersection of kernels of the summands.

Actually, slightly less would serve my purpuses. Suppose that there is a chosen basis of $V$, and we fix one of the vectors from this basis. Call this vector $v$. Suppose $A$ is an endomorphism of $V$.

Question 2. Is there an endomorphism $C$ of $V$, which is expressed in terms of some "natural operations" on $A$, and whose kernel consists of those vectors of kernel of $A$ whose coefficient of $v$ in the chosen basis of $V$ is $0$?

Comment by Łukasz Grabowski

2013-03-12T17:36:29Z

I clearly wrote that $\lambda$ and $\mu$ are assumed to be algebraic numbers

Comment by Łukasz Grabowski

2013-03-11T17:37:15Z

(the reason I asked my question for $M$ and not H's butterfly is I'm fairly sure this hasn't been studied for the H's butterfly, and I hoped perhaps it has been studied for $M$)

Comment by Łukasz Grabowski

2013-03-11T17:30:02Z

@Will, if you look at the Hofstadter's butterfly en.wikipedia.org/wiki/… and identify the vertical axis there with the interval [-i,i] and take $\lambda = iq$, where $q\in Q$ then $t_{\lambda,1}\in \bar{Q}$ (it's a trivial observation.) So it seems sensible to ask whether for the butterfly the function e.g. $x\mapsto t_{ix,1}$ maps $\bar{Q}$ to $\bar{Q}$. One definition of H's butterfly is as the parameters for which the orbit of 1 is bounded in a certain dyn. system defined by a linear recursion with non-const. coeff., so it's not too far away from $M$.

Comment by Łukasz Grabowski

2013-03-11T15:27:49Z

@Gerald, I don't know how to do this example. My initial intuition, however, is that there should be some relatively simple description of $t_{\la,\mu}$: if we first look at very large $t$, where the orbit of $0$ is unbounded, then we go to smaller and smaller $t$, suddenly the orbit becomes bounded. I thought this critical parameter should have some relatively easy relation to the polynomial which we iterate (e.g. being a critical point of some function, etc.) Then again, one could phrase a similarly sounding naive intuition about why should the whole Mandelbrot set be a "simple object"...

Comment by Łukasz Grabowski

2013-03-11T13:22:39Z

Thanks for you reply - however if $M$ is the unit disk, then certainly $t$ would be algebraic - the point in question would be in the intersection of two (real) curves $x^2+y^2 =1$ and a line $y=ax+b$, where $a$ and $b$ are algebraic numbers depending on $\mu$ and $\lambda$. So as it stands for the moment, I still think my question makes sense.

Comment by Łukasz Grabowski

2013-02-08T14:30:01Z

Hi Vaughn, could you please elaborate more? I don't see how the fact that you can approximate $f$ by continuos functions is enough.

Comment by Łukasz Grabowski

2012-12-09T22:45:39Z

I essentially stopped thinking about this, because I don't know how to proceed, but I thought I'd share one idea which at one point I thought was hopeful: G acts on a certain metric space X by isometries - namely fix a mean m on G and define X to be the set of subsets of G up to sets of mean 0. The metric on X is d(A,B) = m(A-B \cup B-A). There are various topologies on Isom(X) but I failed to prove any of them gives a Hausdorff non-discrete topology on G.

Comment by Łukasz Grabowski

2012-12-03T18:12:32Z

@Simone: AFAI understand, Bohr compactif'n B(G) is in particular compact, so by Peter-Weyl thm if G embeds in B(G) then G is res. linear, and so by Malcev thm if it is fin. generated then it is res. finite. So to produce example of an amenable group G which doesn't embed into B(G) take a fin. generated simple amenable group, or easier take a fin.gen. solvable non-res. finite group (e.g. BS(1,n)). Taking a simple group is more convincing though, because the image in B(G) is trivial, whereas if the image in B(G) is infinite one could still hope for inducing a (Hausdorff) topology on G somehow...

Comment by Łukasz Grabowski

2012-11-28T00:19:54Z

@Ben: you can use profinite topology, e.g. fix a prime number $p$; then integer $n$ is "near" to $0$ if large power of $p$ divides $n$. Other way to topologize integers is - take the action of integers $Z$ on the circle such that the generator $t$ of $Z$ acts by irrational rotation, and define $t^k$ to be "close" to the identity element iff $t^k$ is a rotation by a "small" angle. This is special case of "find an infinite cyclic subggroup of a compact group and induce the topology"

Comment by Łukasz Grabowski

2012-03-23T17:31:52Z

thanks for this example; I've added additional assumption of every element acting ergodically

Comment by Łukasz Grabowski

2011-12-15T00:26:48Z

due to 1), it's not what you want, but it's stronger than 3), so maybe is of some interest to you: mathoverflow.net/questions/52169/… (You could maybe try to modify this example by adding additional edges in one of the graphs and see whether "they are mapped to edges" in the other graph by the provided matrix...)

Comment by Łukasz Grabowski

2011-12-14T18:40:12Z

@Colin: do you know anything has been done since about the problem described in the paragraph 7.1?

Comment by Łukasz Grabowski

2011-12-14T17:30:53Z

Max: yes, exactly.

Comment by Łukasz Grabowski

2011-12-14T15:22:32Z

I've confused myself because for a long while I've tried to embed instances of graph isomorphism which are bigger than $n$-vertices into the problem so that one could conditionally prove lower bounds better than $2^n$ (conditionally - i.e. assuming that Luks algorithm is optimal). This would be tricky, however, because by the upper bound, one can't hope to embed such instances of size $n^{1+\eps}$ for any $\eps>0$ (without improving on Luks algorithm)

Comment by Łukasz Grabowski

2011-12-14T15:13:24Z

Yes, you're right.