1 this week I learned - 2025-W10

#update
parents:: this week I learned
daily note:: 2025-03-09
2025-W10

free probability reading group

This past week and the week before that, I gave the first two talks this semester's free probability reading group with folks in math and CS here at MIT. Being pretty much a noob to start, I've learned a lot! (One thing I learned is that having to give a talk makes for more effective learning)

Some themes:

Lecture notes: my free probability lecture notes

sofic groups, non-local games, expansion, (and maybe some free probability)

Alex Lubotzky is here at MIT for a few months.

One cool thing: non-local game for non-hyperlinear group

A theme here is that by proving hardness for a particular decision problem about the quantum value of non-local games can be used to exhibit separations of the form "there is an infinite dimensional object for which there is no sequence of finite objects which converges to it."

And really, this separation is a consequence of separating hyperplane theorem! You can view a non-local game as a vector that you're optimizing. And you have two sets to optimize along: one is, say for instance in tsirelson's problem, the set of correlations which comes from a finite tensor product strategy, and the other is the set of correlations from an infinite commuting operator strategy. Since we have a set of algorithms, one of which always gives a lower bound on the finite strategy value (and is guaranteed to eventually converge to the actual value), and one of which always gives an upper bound on the commuting strategy value (and is guaranteed to eventually converge as well), if these two values were to always be the same, then for any game, it should be decidable, say, whether or not it has an $\epsilon$ close to perfect (tensor product) strategy or not, for any $\epsilon$.
MIP*=RE exhibits games for which it's undecidable to approximate the tensor product value of the game! Following the previous chain of arguments backwards, this means there must be some game for which the tensor product value and the commuting operator value are different!

What does this have to do with finitely generated groups? Well, it turns out that showing RE hardness of the problem of determining whether a linear constraint system (quantum) has a perfect quantum strategy would imply that there is a non-hyperlinear group (and in particular, a non sofic group), which would have implications to several open questions in group theory! Amazing. (this is from paddockSatisfiabilityProblemsAlgebras2025)

To learn more about

Another cool thing: expansion as a barrier to "niceness" of groups

amenable groups are a particular class of "nice" groups. Originally defined by von Neumann in response to the banach-tarski-paradox (if your allowed operations form an amenable group, then you can't have a paradox), these are groups on which you can assign a left-invariant measure. Or, intuitively, groups for which it makes sense to talk about "what fraction of the group is a particular set?"

A non-example of this is the free group on $d>1$ generators. While a positive example is the integers $\bZ$.

Another characterization of amenable groups is the existence of what's called a folner sequence $(F_n)_{n\in \bN}$ which satisfies that for every finite set $K\subset \Gamma$ and $\delta > 0$, there's an $n$ for which
$$\forall g\in K, \frac{|gF_n\Delta F_n|}{|F_n|}\leq \delta$$
That is, $F_n$ has small "boundary" w.r.t. $K$.

Indeed, this might be starting to sound like something like a "small cut" in the language of expansion and graphs.

Questions: