User marcin kotowski - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:54:55Z http://mathoverflow.net/feeds/user/1121 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/125402/expected-rank-computable-approximations Expected rank - computable approximations Marcin Kotowski 2013-03-23T21:36:24Z 2013-03-23T23:55:56Z <p>I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).</p> <p>Computing $\mathbb{E} \ \mathrm{rk}(A)$ is usually infeasible, as rank is a rather awful function to consider or optimize etc. Are there quantities which could serve as proxies for the rank, but whose averages would be easier to compute in this setting? In other words, I'm looking for functions $f(A)$ such that $\mathbb{E}f(A)$ can be computed and $f(A)$ is a reasonable approximation to $\mathrm{rk}(A)$. An example would be $\mathrm{tr}(A)$, which would be close to the rank if the eigenvalues of $A$ are close to $1$.</p> <p>Since replacing rank with some nicer (e.g. convex) function seems to be a common approach e.g. in optimization, I'd be also interested in references.</p> http://mathoverflow.net/questions/123502/largest-number-of-k-arithmetic-progressions-without-a-k1-arithmetic-progressio Largest number of k-arithmetic progressions without a (k+1)-arithmetic progression Marcin Kotowski 2013-03-04T03:17:11Z 2013-03-04T15:56:53Z <p>Suppose $A \subseteq \{1,\dots,n\}$ does not contain any arithmetic progressions of length $k+1$. What is the largest number of $k$-term arithmetic progressions that $A$ can have? (one may also wish to put some lower or upper on the size of $A$) We can work over $\mathbb{Z}_p$ if it makes the answer any easier. The "degenerate" case $k=2$ asks for the largest size of the set without arithmetic progressions and it is known that there exist $A$'s with this property of almost linear size.</p> http://mathoverflow.net/questions/121037/bounds-on-difference-sets-of-relatively-dense-a-subseteq-1-n Bounds on difference sets of relatively dense A \subseteq {1, ..., n} Marcin Kotowski 2013-02-07T03:38:45Z 2013-02-07T16:45:44Z <p>Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta &lt; 1$? If not, can something like this hold for a "generic" $A$ (say, with high probability if $A$ is chosen at random)? What about $2A-A$ or similar sets? (as you can guess, interest in $2A-A$ comes from arithmetic progressions)</p> <p>Of course only the case $|A| = \Omega(\sqrt{n})$ is nontrivial, and perhaps we have to assume also an upper bound on $|A|$ (e.g. $|A| \leq n^{\gamma}$ for some $\gamma &lt;1$), since of course we could have $A = \{1, \dots, n\}$.</p> http://mathoverflow.net/questions/18212/spectral-properties-of-cayley-graphs Spectral properties of Cayley graphs Marcin Kotowski 2010-03-14T22:01:42Z 2012-12-27T10:12:48Z <p>Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good invariant, but maybe something interesting can still be said here?</p> <p>In the case of an infinite group, can Cayley graph be replaced by some suitable infinite-dimensional object (say, linear operator, a generalization of the graph's adjacency matrix) so that the object's spectral properties may carry some algebraic data about the group?</p> http://mathoverflow.net/questions/111017/ising-model-phase-transition-vs-rapid-mixing Ising model - phase transition vs rapid mixing Marcin Kotowski 2012-10-29T18:06:59Z 2012-10-29T18:06:59Z <p>Consider a graph $G=(V,E)$ and Ising model on that graph, i.e. configuration space is $\Omega=${$-1,+1$}$^V$ and energy of a configuration $s \in \Omega$ is given by: $H(s) = -\beta \sum_{u \sim v}s(u)s(v)$</p> <p>Consider:</p> <p>a) the phase transition between the ordered and disordered phase</p> <p>b) transition in a Markov chain simulating the dynamics (e.g. Glauber/Metropolis dynamics), from rapid mixing ($N\log N$) to exponentially slow mixing</p> <p>It is generally "known" that often phase transition as in a) is accompanied by phase transition in b) ("critical slowdown" in physics parlance). Is there any formal result capturing this knowledge (e.g. theorem of the form: physical phase transitions is equivalent to critical slowing down of the appropriate Markov chain)? Or, at least, a nonrigorous argument going beyond "this seems to hold for all systems that physicists are interested in" (proving tight results about critical points is usually difficult, so a heuristic would be OK).</p> http://mathoverflow.net/questions/108255/another-question-about-amenability-and-folner-sequences/108258#108258 Answer by Marcin Kotowski for Another question about amenability and Følner sequences Marcin Kotowski 2012-09-27T15:59:27Z 2012-09-27T15:59:27Z <p>Yes - see Lemma 5.1 of Gabor Pete's book on probability and groups: <a href="http://www.math.bme.hu/~gabor/PGG.html" rel="nofollow">http://www.math.bme.hu/~gabor/PGG.html</a> (by the way, these are excellent lecture notes)</p> http://mathoverflow.net/questions/97001/expected-values-of-traces-of-products-of-random-matrices Expected values of traces of products of random matrices Marcin Kotowski 2012-05-15T14:29:23Z 2012-09-06T04:25:41Z <p>Suppose I want to compute a quantity of the type: </p> <p>$\mathbb{E}\mathrm{tr}(AUBU^{\ast})$ </p> <p>where averaging is over Haar measure on the unitary group $\mathcal{U}(n)$ (one can of course consider higher order polynomials or other matrix ensembles etc.) and $A$, $B$ are some fixed matrices. Is there any standard technique for computing such averages? I'd guess people in random matrix theory or free probability compute such traces all the time, but I've been unable to find a reference. If it makes matters easier, I'm really interested in computing something for random projections (e.g. something of the form $\mathbb{E}\mathrm{tr}(APBP)$, where $P$ is a projection onto a random subspace), which of course reduces to computation of polynomials in $U$.</p> http://mathoverflow.net/questions/97001/expected-values-of-traces-of-products-of-random-matrices/98524#98524 Answer by Marcin Kotowski for Expected values of traces of products of random matrices Marcin Kotowski 2012-05-31T23:21:23Z 2012-05-31T23:21:23Z <p>Answering my own question, there is a closed formula for such traces, given in: <a href="http://arxiv.org/abs/math-ph/0402073" rel="nofollow">http://arxiv.org/abs/math-ph/0402073</a> (the formula involves representation theory of $S_n$ and gets ugly as $n$ gets bigger, but can be written down explicitly at least for small $n$)</p> http://mathoverflow.net/questions/89824/diophantine-elements-in-su2 Diophantine elements in SU(2) Marcin Kotowski 2012-02-29T02:39:11Z 2012-03-02T20:09:23Z <p>Following notions from [1], call a set of elements $g_1, \dots, g_k \in G = SU(2)$ Diophantine if it satisfies the following property: there exists a constant $D$ such that for every word $W_m$ of length $m$ in $g_1, \dots, g_k$, if $W_m \neq \pm e$ (identity element), then $\Vert W_m \pm e\Vert \geq D^{-m}$. It can be proved that elements with algebraic entries are Diophantine.</p> <p>Bourgain and Gambrud prove that a certain property (spectral gap) holds for $g_1, \dots g_k$ that: a) generate a free subgroup of $SU(2)$, b) are Diophantine. The first property is generic in measure. The second is not known to be generic in measure, but sets of Diophantine elements are dense in $G^k$ (since all rational-entry elements are). Does it follow that set of elements that a) generate free subgroup, b) are Diophantine, is dense in $G^{k}$?</p> <p>Maybe it's almost obvious, since the set of elements generating a free subgroup is a complement of a countable union of proper subvarieties, but somehow one must rule out the possibility that being Diophantine and freeness are "anticorrelated" (a priori, we only know that elements with algebraic elements are Diophantine, and this is a countable set). Or maybe in fact Diophantine elements form a much larger set?</p> <p>[1] Jean Bourgain, Alex Gamburd, "On the spectral gap for finitely-generated subgroups of SU(2)"</p> http://mathoverflow.net/questions/88537/mixing-time-of-unitary-brownian-motion Mixing time of unitary Brownian motion Marcin Kotowski 2012-02-15T18:43:06Z 2012-02-16T06:24:15Z <p>Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{{Id}})$ converge to the Haar measure? (the question is motivated by trying to say something about mixing times for some discrete approximations of unitary Brownian motion)</p> http://mathoverflow.net/questions/84032/short-course-suggestions-for-high-school-students/84128#84128 Answer by Marcin Kotowski for Short Course Suggestions For High School Students Marcin Kotowski 2011-12-22T23:31:26Z 2011-12-22T23:31:26Z <p>I have successfully taught a course for gifted high school students (somewhat shorter than yours, about 9 hours) devoted to the probabilistic method (based, naturally, on Alon and Spencer + some other material). I managed to cover the basics, second moment method, some random graphs, games and derandomization. With a little more time I would have squeezed in the Lovasz Local Lemma. </p> <p>There was a lot of problem solving, but I was also able to show them some more advanced techniques. In general, combinatorics seems to be a good context to introduce some nontrivial probabilistic tools (say, Chernoff-type bounds). </p> <p>Another probability-based course in the similar format was "random walks and electrical networks". Very nice topic, quite elementary^1, lots of physical intuition - and at the same time, points at the more advanced math beneath (Markov chains, spectral graph theory)</p> <p>1 - until the kids ask you "wait, how is this probability on the set of infinite trajectories defined? ;) Luckily, I managed to avoid invoking the Kolmogorov extension theorem.</p> http://mathoverflow.net/questions/4411/quantitative-versions-of-ergodic-theorem Quantitative versions of ergodic theorem Marcin Kotowski 2009-11-06T18:36:47Z 2011-11-23T00:00:02Z <p>Are there any general theorems similar to Birkhoff's ergodic theorem, but giving quantitative estimates on the rate of convergence or average time of recurrence (perhaps with additional assumptions)? Take the example of an "irrational rotation" on the unit circle - are there any estimates on the average time it takes for a point to hit a certain interval?</p> <p>I know there are such theorems for very special systems (e.g. for Markov chains we have exponential convergence) - what can be said about a "generic" ergodic system?</p> http://mathoverflow.net/questions/81295/how-to-make-a-lecture-series-useful/81394#81394 Answer by Marcin Kotowski for How to make a lecture series useful Marcin Kotowski 2011-11-20T04:43:59Z 2011-11-20T04:43:59Z <p>If possible, it might be a good idea to organize a problem session, with problems/exercises given to participants in advance (say, a day before) and the session devoted to presenting the solution. The problems needn't be difficult, but have to solve actual exercises forces you to understand the definitions and concepts in enough detail to be able to use them, not only on vague "big picture" level. I've attended schools/workshops where this idea was implemented and the feedback was overwhelmingly positive.</p> http://mathoverflow.net/questions/78233/simultaneous-diophantine-approximation-with-polynomial-bound Simultaneous diophantine approximation with polynomial bound Marcin Kotowski 2011-10-15T23:04:19Z 2011-10-15T23:13:59Z <p>For a given number $\alpha$ continued fractions expansion $(p_n, q_n)$ of $\alpha$ has the remarkable property that not only $|\alpha - \frac{p_n}{q_n}| &lt; \frac{1}{q_n^2}$, but the converse holds - if $|\alpha - \frac{p}{q}| &lt; \frac{1}{2q^2}$, then $\frac{p}{q}$ will appear in the expansion of $\alpha$.</p> <p>Is there any analogue of this fact in simultaneous Diophantine approximation with polynomial bound? More precisely, I want to think of this procedure as allowing me to recover unknown ${ \frac{p_i}{q}}$ with $q$ being exponential in $n$, from known $\alpha_i = \frac{s_i}{r}$ with $r$ only polynomial in $n$ and $|\alpha_i - \frac{p_i}{q}| &lt; \frac{1}{poly(n)}$. Is such a procedure even possible, maybe given some additional constraints? (note that doing 1-dimensional continued fractions component-by-component will not do, as it requires resources exponential in $n$ for each component)</p> <p>(motivation for the problem comes from considering an unknown $n$-dimensional rational lattice and trying to recover their vectors using some polynomial sampling procedure; I want to think of $q$ as the determinant of this lattice, which is reasonably to assume to be exponential in $n$)</p> http://mathoverflow.net/questions/76592/pointwise-bounds-for-dirichlet-kernel-over-truncated-lattice Pointwise bounds for Dirichlet kernel over truncated lattice Marcin Kotowski 2011-09-28T02:28:38Z 2011-09-28T02:28:38Z <p>In 1 dimension, a "one-sided" Dirichlet kernel $D_N(x)=\sum_{k=0}^{k=N}e^{\frac{2\pi}{N}ikx}$ has its module sharply peaked around points corresponding, roughly, to the "dual lattice" $N\cdot\mathbb{Z}$ (which area really integer points in this case).</p> <p>Now consider a lattice $\Lambda \subseteq \mathbb{Z}^2$. Let $\Lambda_N = \Lambda \cap [0,N]^2$ and a Dirichlet kernel restricted to this truncated lattice: $D_{\Lambda_N}(x)=\sum_{v \in \Lambda_N}e^{i\langle x,v\rangle}$.</p> <p>We would expect that $|D_{\Lambda_N}|$ will be peaked around points from $N\cdot\Lambda^{\ast}$, where $\Lambda^{\ast}$ is the dual lattice. However, there is no direct way to perform the summation and obtain a compact formula as in 1D case. Is there any way to estimate $|D_{\Lambda_N}(w)|$ from below, for $w \approx N\cdot\Lambda^{\ast}$? </p> http://mathoverflow.net/questions/75166/second-eigenvalue-of-suspension-of-a-graph Second eigenvalue of suspension of a graph Marcin Kotowski 2011-09-11T22:08:19Z 2011-09-12T02:51:30Z <p>Suppose I have some $d$-regular graph $G$. Let $\lambda = \max{\lambda_2(G), |\lambda_n(G)|}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of $G$, obtained by adding a new vertex $v$ and connecting $v$ to all vertices of $G$. Is it true that $\lambda(\tilde{G}) \leq \lambda(G)$? (or more generally, is it true if instead of suspending with one vertex we suspend with a clique of size $n$)</p> <p>The intuition is that $\tilde{G}$ should exhibit better mixing (hence, smaller $\lambda$), since it's easier for a random walk to get from one vertex to any other.</p> http://mathoverflow.net/questions/15973/quantum-analogue-of-wiener-process Quantum analogue of Wiener process Marcin Kotowski 2010-02-21T14:54:53Z 2011-06-27T16:23:23Z <p>The Wiener process (say, on $\mathbb{R}$) can be thought of as a scaling limit of a classical, discrete random walk. On the other hand, one can define and study <em>quantum random walks</em>, when the underlying stochastic process is governed by a unitary transform + measurement (for an excellent introduction, see <a href="http://arxiv.org/abs/quant-ph/0303081" rel="nofollow">http://arxiv.org/abs/quant-ph/0303081</a>).</p> <p>My question is - do quantum random walks have a reasonable continuous limit, something which would give a quantum analogue of the Wiener process?</p> http://mathoverflow.net/questions/52251/ising-model-on-groups Ising model on groups Marcin Kotowski 2011-01-16T18:01:42Z 2011-06-16T09:36:29Z <p>Can anything interesting be deduced about the properties of a group from the behavior of the Ising model on its Cayley graph? (i.e. existence and character of phase transitions, critical behavior) I'm not sure, though, if one should expect any general results (link between large-scale geometry and universality class, maybe?), since even very simple geometry of the group (say, $\mathbb{Z^2}$) can give highly nontrivial statistical properties. </p> http://mathoverflow.net/questions/66828/friedman-and-proof-of-hanna-neumann-conjecture Friedman and proof of Hanna Neumann Conjecture Marcin Kotowski 2011-06-03T14:48:13Z 2011-06-03T17:17:37Z <p>Two years ago, Joel Friedman submitted a paper purporting to prove the Hanna Neumann Conjecture, which eventually turned out to contain a fatal bug and was withdrawn. Quite recently, Friedman repeated his attempt at proof with paper "Sheaves on Graphs and a Proof of the Hanna Neumann Conjecture": <a href="http://arxiv.org/abs/1105.0129" rel="nofollow">http://arxiv.org/abs/1105.0129</a> . Has this attempt been verified by anyone or is still under review?</p> http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants What are the applications of immanants? Marcin Kotowski 2011-05-28T14:53:39Z 2011-05-29T17:27:18Z <p>Definitions of determinant:</p> <p>$det(A) = \sum_{\sigma \in S_n}(-1)^{\operatorname{sgn} \sigma}\prod_{i}a_{i, \sigma(i)}$</p> <p>and permanent:</p> <p>$perm(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)}$</p> <p>admit a generalization in the form of <a href="http://en.wikipedia.org/wiki/Immanant" rel="nofollow">immanant</a>:</p> <p>$Imm_{\lambda}(A) = \sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i}a_{i, \sigma(i)}$</p> <p>where $\lambda$ labels irreducible representations of $S_n$ and $\chi_{\lambda}$ is the character. Determinant and permanent are easily seen to be special cases of $Imm_{\lambda}$.</p> <p>While determinants are ubiquitous in mathematics and permanents also have many application, esp. in combinatorial problems, other kinds of immanants seem to be rarely used. Are there any problems where use of $Imm_{\lambda}$ other than $det$ and $perm$ is natural?</p> http://mathoverflow.net/questions/65894/proving-that-a-combinatorial-sequence-has-no-compact-formula Proving that a combinatorial sequence has no compact formula Marcin Kotowski 2011-05-24T19:59:33Z 2011-05-24T20:42:38Z <p>Suppose we have a sequence $a_n$ given by some combinatorial formula, e.g. involving a sum of n terms (like ${n \choose k}^{10}3^{-k}$ etc.). Sometimes it is plausible that there is no compact formula for the $a_n$, where one has to adopt a reasonable definition of "compact" (i.e. using a constant, independent of $n$, number of primitive operations). Are there any methods of proving that a certain sequence $a_n$ has no compact formula, in much the same way differential Galois theory allows one to prove that certain integrals are nonelementary? Of course this would relative the choice of "computational primitives" (factorial, ${n \choose k}$ etc.) </p> http://mathoverflow.net/questions/61234/bell-polytopes-with-nontrivial-symmetries Bell polytopes with nontrivial symmetries Marcin Kotowski 2011-04-10T18:19:40Z 2011-04-10T18:19:40Z <p>Take $N$ parties, each of which receives an input $s_i \in {1, \dots, m_i}$ and produces an output $r_i \in {1, \dots, r_i}$, possibly in a nondeterministic manner. We are interested in joint conditional probabilities of the form $p(r_1r_2\dots r_N|s_1s_2\dots s_N)$. Bell polytope is the polytope spanned by the probability distributions of the form $p(r_1r_2\dots r_N|s_1s_2\dots s_N) = \delta_{r_1, r_{1, s_1}}\dots\delta_{r_N, r_{N, s_N}}$ for all possible choices of numbers $r_{i,s_i}$ (in other words, each input $s_i$ produces a result $r_{i,s_i}$ either with probability 0 or 1, regardless of other players' inputs). Polytopes of this kind are of interest in quantum information theory.</p> <p>Every Bell polytope has a certain amount of trivial symmetries, like permutation of parties or relabelling of inputs or outputs. Is it possible to give an explicit Bell polytope with nontrivial symmetries? (e.g. transformations of the polytope into itself that takes faces to faces and is not trivial in the above sense)</p> <p>Bell polytopes in literature are usually characterized by their faces, given by sets of inequalities (Bell inequalities), which, however, usually do not have any manifest symmetry group. </p> http://mathoverflow.net/questions/51056/are-there-any-good-websites-for-hosting-discussions-of-mathematical-papers/51108#51108 Answer by Marcin Kotowski for Are there any good websites for hosting discussions of mathematical papers? Marcin Kotowski 2011-01-04T11:08:42Z 2011-01-04T11:08:42Z <p>You can try SciRate (<a href="http://scirate.com/" rel="nofollow">http://scirate.com/</a>), a site that allows you to rate and comment papers from Arxiv (it updates the list of papers automatically). It doesn't seem to be very popular, though (lack of critical mass?).</p> http://mathoverflow.net/questions/44326/most-memorable-titles/50598#50598 Answer by Marcin Kotowski for Most memorable titles Marcin Kotowski 2010-12-28T20:41:53Z 2010-12-28T20:41:53Z <p>"I know I should have taken that left turn at Albuquerque" by Gady Kozma and Ariel Yadin (<a href="http://arxiv.org/abs/1008.4258" rel="nofollow">http://arxiv.org/abs/1008.4258</a>)</p> http://mathoverflow.net/questions/49054/rainbow-matchings-in-random-graphs Rainbow matchings (in random graphs) Marcin Kotowski 2010-12-11T16:23:35Z 2010-12-13T02:55:35Z <p>Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) for a random bipartite graph (e.g. that for $k$ colors and more than $f(k,n)$ edges we get a rainbow matching with $p \rightarrow 1$)? </p> <p>In the noncolored case, Hall's theorem makes proving this kind of results relatively simple, since we are interested in the non-existence of "no matching possible" witness (i.e. a subset that violates Hall condition) and we can use union bound to bound the probability from above (for $A_k$ = "k-th subset is a witness" give bound to $\mathbb{P}(\cup A_k)$). However, there is no simple condition of this kind equivalent to the existence of a rainbow matching. </p> http://mathoverflow.net/questions/49082/individual-mathematical-objects-whose-study-amounts-to-a-subdiscipline/49142#49142 Answer by Marcin Kotowski for Individual mathematical objects whose study amounts to a (sub)discipline? Marcin Kotowski 2010-12-12T14:00:01Z 2010-12-12T14:00:01Z <p>The Erdos-Renyi random graph model $G(n,p)$ - a single, concrete model that more or less created the field of random graph theory and is still studied. </p> http://mathoverflow.net/questions/47585/random-rotations-in-so3-and-free-group Random rotations in SO(3) and free group Marcin Kotowski 2010-11-28T13:17:16Z 2010-11-28T17:35:05Z <p>Is it true that two random (w.r.t. Haar measure) rotations in $SO(3)$ generate a free group?</p> http://mathoverflow.net/questions/46030/regularity-of-asymptotic-cones Regularity of asymptotic cones Marcin Kotowski 2010-11-14T10:11:56Z 2010-11-15T00:07:22Z <p>Are there any general conditions guaranteeing that the asymptotic cone of a group/graph is "regular" in some sense? E.g. for $\mathbb{Z}^d$ we get $\mathbb{R}^d$ as the asymptotic cone, which is even a manifold, but for general groups we only get a metric space without additional structure. Does knowing that asymptotic cone is regular (e.g. a manifold) imply any properties of the original group?</p> http://mathoverflow.net/questions/45182/asymptotics-for-forbidden-subwords Asymptotics for forbidden subwords Marcin Kotowski 2010-11-07T17:06:44Z 2010-11-08T19:58:39Z <p>Fix an alphabet $A$ and consider words of length $n$ over $A$. Fix a set $B$ of $k$ forbidden subwords (subword is not necessarily connected, i.e. $abb$ is a subword of $abcb$). Can anything be said about the asymptotics of number of permissible words (i.e. words that don't containt any word from $B$ as a subword)? (a particular case - what if $n=k^{1+\epsilon}$ and we let $k \rightarrow \infty$?)</p> http://mathoverflow.net/questions/43537/property-t-and-subgroups-of-finite-index Property (T) and subgroups of finite index Marcin Kotowski 2010-10-25T16:09:42Z 2010-10-25T22:25:00Z <p>Suppose $G$ is a discrete group and $H \leq G$ a subgroup of finite index. If $H$ has Kazhdan property (T), does it follow that $G$ has property (T)? (I've read somewhere that (T) is preserved by exact sequences, so if $N$ is normal and $G/N$ is finite, then the fact above holds ; here, however, we do not assume $H$ to be normal)</p> http://mathoverflow.net/questions/125402/expected-rank-computable-approximations Comment by Marcin Kotowski Marcin Kotowski 2013-03-23T23:09:09Z 2013-03-23T23:09:09Z I edited that part of the question. http://mathoverflow.net/questions/123502/largest-number-of-k-arithmetic-progressions-without-a-k1-arithmetic-progressio Comment by Marcin Kotowski Marcin Kotowski 2013-03-04T17:25:06Z 2013-03-04T17:25:06Z Nb. for graphs (i.e. asking for the maximal number of $l$-cliques a graph can contain before it contains a $k$-clique) there are explicit bounds. http://mathoverflow.net/questions/123502/largest-number-of-k-arithmetic-progressions-without-a-k1-arithmetic-progressio/123540#123540 Comment by Marcin Kotowski Marcin Kotowski 2013-03-04T16:23:59Z 2013-03-04T16:23:59Z I upvote the answer, but the conclusion &quot;any subset B⊂A with positive relative density has a k-long arithmetic progression.&quot; seems too weak to say anything about the <i>number</i> of such k-progressions in the whole set. http://mathoverflow.net/questions/121260/isometric-embeddings-of-cayley-graphs-in-nice-spaces Comment by Marcin Kotowski Marcin Kotowski 2013-02-09T02:38:51Z 2013-02-09T02:38:51Z For embedding groups into Euclidean spaces, try googling &quot;hilbert compression exponents&quot;. But then again, this is very far from isometry, since in this theory you can get, at best, only Lipschitz embeddings. The requirement of embeddings being isometries, rather than some weaker classes of maps, seems very stringent. Is that really what you want? http://mathoverflow.net/questions/121037/bounds-on-difference-sets-of-relatively-dense-a-subseteq-1-n Comment by Marcin Kotowski Marcin Kotowski 2013-02-07T15:28:03Z 2013-02-07T15:28:03Z @Anthony: do you have a reference? (although it shouldn't be too difficult to compute $\mathbb{E}|A-A|$ directly) http://mathoverflow.net/questions/121037/bounds-on-difference-sets-of-relatively-dense-a-subseteq-1-n Comment by Marcin Kotowski Marcin Kotowski 2013-02-07T15:24:47Z 2013-02-07T15:24:47Z @Seva: maybe you still can get something for |A| between n^alpha and n^gamma for some alpha, gamma &lt; 1 (edited to clarify). http://mathoverflow.net/questions/111019/convergence-of-random-variables-and-almost-sure-convergence Comment by Marcin Kotowski Marcin Kotowski 2012-10-29T19:51:35Z 2012-10-29T19:51:35Z I think this question would be more suitable on Math.SE. http://mathoverflow.net/questions/103325/continuous-analogue-of-log-sum-inequality Comment by Marcin Kotowski Marcin Kotowski 2012-07-27T16:15:50Z 2012-07-27T16:15:50Z Where is the question? It seems you already have a proof, and you only need people to verify it? http://mathoverflow.net/questions/97001/expected-values-of-traces-of-products-of-random-matrices Comment by Marcin Kotowski Marcin Kotowski 2012-05-15T17:17:22Z 2012-05-15T17:17:22Z @Mikael: can this observation be generalized to higher order polynomials (e.g. $AUBU^{\ast}CUDU^{\ast}$)? In that case, we can't put E inside the trace for both terms UXU^{\\ast} only by linearity. http://mathoverflow.net/questions/97001/expected-values-of-traces-of-products-of-random-matrices Comment by Marcin Kotowski Marcin Kotowski 2012-05-15T15:40:35Z 2012-05-15T15:40:35Z @IR: yes, edited for clarity. http://mathoverflow.net/questions/89880/bounding-sum-of-first-singular-values-squared-for-kronecker-sum-of-traceless-matr/89888#89888 Comment by Marcin Kotowski Marcin Kotowski 2012-02-29T19:06:50Z 2012-02-29T19:06:50Z @Suvrit: I guess your A and B are $3 \times 3$ matrices, not $4 \times 4$. http://mathoverflow.net/questions/88133/quantum-dynamics-on-varieties-and-salmon-prizes Comment by Marcin Kotowski Marcin Kotowski 2012-02-12T00:35:03Z 2012-02-12T00:35:03Z In short, the question would be much better if OP cut all the hype about STEM, lions, \$100,000 rewards, scalable quantum computing etc. and left the underlying mathematical question clear and well defined (in particular, it should be obvious why the question is not trivial). http://mathoverflow.net/questions/88133/quantum-dynamics-on-varieties-and-salmon-prizes Comment by Marcin Kotowski Marcin Kotowski 2012-02-12T00:31:57Z 2012-02-12T00:31:57Z @Andres Calcedo: the question is simply difficult to comprehend - it either reduces to a trivial linear algebraic fact (see Theo's answer) or involves some unspecified &quot;algebraic constraints&quot; which are not at all clear from the question. Plus, a lot of &quot;background&quot; (thermodynamics, quantum varieties, talk about pullbacks) makes it even more muddled, the relation to quantum computing is completely opaque (even for me, who does research in quantum computing), and frankly speaking, sentences with &quot;STEM&quot; being every other word don't seem to hep. http://mathoverflow.net/questions/9218/probabilistic-proofs-of-analytic-facts/10312#10312 Comment by Marcin Kotowski Marcin Kotowski 2012-02-08T01:23:57Z 2012-02-08T01:23:57Z None of the results in the (excellent) paper you reference are ven remotely analytic. http://mathoverflow.net/questions/9218/probabilistic-proofs-of-analytic-facts/9256#9256 Comment by Marcin Kotowski Marcin Kotowski 2012-02-08T01:23:06Z 2012-02-08T01:23:06Z How is this an analytic fact?