TITLE: What is the visual explanation and intuition behind the "asymptotic equivalence" and the "order of growth" (BigTheta and Tilde notations)?
QUESTION [0 upvotes]: I'm trying to grasp the essence of asymptotic equivalence and the order of growth definitions and meaning, but it's already taking too much time. Let's start with the tilde notation. From Wikipedia:
$$
{
f(x) \sim g(x) \quad (as \quad x \to \infty)
}
$$
if and only if:
$$
{
\lim_{n\to\infty} \frac{f(x)}{g(x)} = 1
}
$$
So, if we take the following functions as an example:
$$ \bbox[yellow]
{
f(x) = x^2 + x \cdot \log_2 x
\qquad (1)
}
$$
and
$$ \bbox[yellow]
{
g(x) = x^2
\qquad (2)
}
$$
and plot them for x=0..10:

they doesn't seem identical here. But then, if we draw for x=0..10000:

they became almost identical. Clearly, it works as x approaches infinity. But why?
In contrast, if we use $g(x) = x^3$ instead, the limit will be equal to 0, which means, that this pair of functions isn't asymptotically equivalent.
But how does it work? Why functions are asymptotically identical if and only if
$
{
\lim_{n\to\infty} \frac{f(x)}{g(x)} = 1
}
$ .
Why can we trust this definition? Is there a visual explanation of it?

REPLY [0 votes]: Though I'm very grateful for the previous answer and still believe it's better than this one, I'll post it because it may add value to this question. I'm still surprised why I haven't thought about it immediately.
The main goal of the tilde notation is to show whether two functions are similar or not. What "similar" mean? Let's start with two numbers and equality. Two numbers are equal to each other if and only if their quotient is equal to 1 (let's omit division by 0). Now, a function just maps numbers from a domain to a codomain. So, we can say, that two functions are equal when each value of one function divided by each value of another function is equal to 1 at any given point in their domain. We can write it as:
$$
\frac{f(x)}{g(x)} = 1 , \qquad x=(-\infty, \infty)
$$
But instead of telling that our functions are equal (which is pretty useless on its own), our goal is to tell whether two functions are similar. Now, what "similar" means? It means that a ratio of values of functions are "almost equal" to 1. How can we tell that values of two functions are "almost equal" to 1? Do we have any mathematical mechanism to answer this question?
Yes, limits. It has a strict definition, that can help us answer the question: "how close can a function can be to a specific value" with the answer: "as close as we need it to be" (in terms of sigma and epsilon notion). Let's review a definition of a limit:
$$
\lim_{x \to c} f(x) = L
$$
which means: "we can set f(x) as close as we want to L by making x sufficiently close to C" (credits to KhanAcademy).
Now we can extrapolate the definition of a limit to "similar" functions. Which is:
$$
\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1
$$
In terms of a limit definition, it's: "we can set f(x)/g(x) as close as we want to 1 by making x sufficiently close to infinity".
Why we only care about $x \to \infty$? Because we consider not only how "similar" two functions are, but also their order of growth (which means at x close to $\infty$).
We can visualize it as:

where we can clearly see that the closer two "similar" functions get to infinity, the closer f(x)/g(x) became to 1 because |f(x) - g(x)| became smaller and smaller (or "not to shrink to zero as long as it is small relative to g(x)").
Update 1: fix the incorrect statement about |f(x) - g(x)| being smaller and smaller in the last sentence by quoting from another answer (because it's not always true).


TITLE: Let $f:[a,b]\to \mathbb{R}$ be Riemann integrable. Let $g:[-b,-a]\to \mathbb{R}$ be defined by $g(x):=f(-x)$. Show that $g$ is Riemann integrable
QUESTION [1 upvotes]: Let $a<b$ $f:[a,b]\to \mathbb{R}$ be Riemann integrable. Let $g:[-b,-a]\to \mathbb{R}$ be defined by $g(x):=f(-x)$. Show that $g$ is Riemann integrable with $\int_{[-b,-a]}g=\int_{[a,b]} f$

I wanted to use change of variables but the statement I have from the text says $\phi$ must be monotone increasing:

Let $[a,b]$ be a closed interval and let $\phi:[a,b]\to [\phi(a),\phi(b)]$ be a differentiable monotone increasing function such that $\phi'$ is Riemann integrable. Let $f:[\phi(a),\phi(b)]\to \mathbb{R}$ be Riemann integrable. Then $(f\circ \phi) \phi':[a,b]\to \mathbb{R}$ is Riemann integrable on $[a,b]$ and $\int_{[a,b]} (f\circ \phi)\phi'=\int_{[\phi(a),\phi(b)]} f$

So I wanted to just prove that $\underline\int_{[a,b]} f\leq \int_{[-b,-a]}g\leq \overline\int_{[a,b]} f$
I know that given a partition $P$ of $[a,b]$ I can use $\phi(x)=-x$ to construct a partition of $[-b,-a]$ as $Q\{J\in P:\phi(J)\}$.
But I'm not sure exactly what to do from here. I'm assuming there must be some way to use the theorem given that I'm not seeing or I'm supposed to prove that the change of variables still works for monotone decreasing $\phi$.

REPLY [0 votes]: If for each partition $P$ of $[a,b]$ of size $n$ you can find a partition $Q$ on $[-b,-a]$ of size $m$ so that $$\sum_{i=1}^{n-1} (\sup_{x\in[x_i,x_{i+1}]}f(x))(x_{i+1}-x_i) = \sum_{j=1}^{m-1} (\sup_{x\in[y_j,y_{j+1}]}g(x))(y_{j+1}-y_j) $$
Then $\overline{\int_a^b} f = \overline{\int_{-b}^{-a}}g$. The same argument will show that   $\underline{\int_a^b} f = \underline{\int_{-b}^{-a}}g$.


TITLE: Understanding the theorem 13 of the paper of A.V.Arhangel'skii in 2000
QUESTION [1 upvotes]: The Theorem 13 is from the paper: Sharp bases and weakly uniform bases versus point-countable bases. I cannot understand that which said:" we only need to add the family $\mathcal{B}_1$ the family of all open one-point sets of $Z$." Also I don't know why the  author command the cardinality of the space $Z$ is $\le \aleph_1$
What I've tried:  I think the family $\mathcal{B}_1$ is already the point-countable base of $Z$. For points of $X$, which is the set of alll isolated of $Z$, family $\mathcal{B}_1$ is point-countable; and notice that family $\mathcal{B}_1$ is also two-countable base of $Z$, so by the lemma 14, family $\mathcal{B}_1$ is point-countable at every non-isolated points of $Z$.
Could somebody help me?

REPLY [2 votes]: For my own benefit I’m going to recapitulate the early part of the argument, filling in a couple of details and making a couple of small corrections.
$\mathscr{B}$ is a $2$-countable base for $Z$, and $X$ is the set of isolated points of $Z$. $\mathscr{U}=\{V\cap X:V\in\mathscr{B}\}$. From Lemma $12$ we have a function $f:\mathscr{U}\to X$ such that $\mathscr{U}_1=\{U\setminus f(U):U\in\mathscr{U}\}$ is point-countable. The definition of $\mathscr{B}_1$ is slightly incorrect; it should be
$$\mathscr{B}_1=\left\{V\setminus\{f(V\cap X)\}:V\in\mathscr{B}\right\}\;,$$
where $f(\varnothing)$ is some object not in $Z$. This clearly is a base at each point of $Z\setminus X$. There is a typo in the argument that $\mathscr{B}_1$ is point-countable at each point of $X$: the reference should be to Lemma $12$, and the point is that if $W\in\mathscr{B}_1$ and $W\cap X\ne\varnothing$, then $W\in\mathscr{U}_1$. That $\mathscr{B}_1$ is point-countable at each point of $Z\setminus X$ does indeed follow from Lemma $14$.
The reason that we need to replace $\mathscr{B}_1$ by $\mathscr{B}_1\cup\big\{\{x\}:x\in X\big\}$ to get a point-countable base for $Z$ is that if $x\in X$, any base for $Z$ must include the set $\{x\}$, but there is no guarantee that $\{x\}\in\mathscr{B}_1$. In fact, $\{x\}\in\mathscr{B}_1$ iff there is a $y\in X\setminus\{x\}$ such that $\{x,y\}\in\mathscr{B}$ and $f\big(\{x,y\}\big)=y$. In other words, $\mathscr{B}_1$ is point-countable, and it’s a base at every point of $Z\setminus X$, but it may not even cover $X$, let alone be a base at every point of $X$. Adding the singletons of isolated points makes it a base for the whole space and doesn’t destroy point-countability.


TITLE: Proving an operator is compact exercise
QUESTION [0 upvotes]: Suppose $(a_{ij})_{i,j\in \mathbb N}$ satisfy $\sum_{i,j}|a_{ij}|^2<\infty$ and define $A:\ell ^2 \rightarrow \ell ^2$ by $(Ax)_i)=\sum _j a_{ij}x_j$. I need to prove $A$ is compact.
Unfortunately, I really have not idea what to do here. I don't see how playing around with the $\ell^2$ norm will be of any use. On the other hand, using $\|\cdot\|_2\leq \|\cdot\|_1$ only gives me $\|Ax_n-Ax_m\|_2\leq \sum _{ij}|a_{ij}||x_j|$ which doesn't seem to help either. I'm pretty sure I'm not supposed to use this equality anyway, but I don't even have intuition for why the operator should be compact. (My strategy was to take a bounded sequence $x_k$ from the unit ball and show its image has a convergent subsequence.)

REPLY [0 votes]: You have to understand what $A$ looks like. It acts as an infinite matrix $(a_{ij})_{i,j=1}^{\infty}$ on your elements of $\ell^2$. Since $\ell^2$ is a Hilbert space you know that $A$ is compact if it is a limit of finite-rank operators. You can show that $A$ is the limit of $P_nAP_n$ where $P_n$ is the projection on the span of the first $n$ standard basis vectors.


TITLE: Does effective theory have the same meaning in particle and condensed matter physics
QUESTION [4 upvotes]: I have a naive question about the meaning of effective theory in particle physics and condensed matter physics.
In particle physics, from what I know, the effective theory comes from the Wilsonian renormalization. We start from a theory with a fundamental cutoff $\Lambda$, e.g. Planck scale, and consider a smaller cutoff $\Lambda'$, e.g. LHC scale, $\Lambda'<\Lambda$. The Lagrangian then reshuffle into an infinity series including all possible powers of fields. The theory with $\Lambda'$ cutoff is called effective theory (possibly only a few leading terms)
In condensed matter theory, I heard the effective theory means neglect some details, like the BCS theory.
Roughly speaking, "the effective" in both fields has similar meaning, that we ignore something ($>\Lambda'$ in particle physics or uninteresting detail in condensend matter).
My question is, strictly speaking, does the two "effective" in particle and condensed physics have the same meaning? Can we start from QED, lower the cutoff, lead to BCS theory? (perhaps such crazy attempt will never work out...) or any deeper connection than heuristic similarities?

REPLY [6 votes]: Yes, the term "effective action" has the same meaning in particle physics and condensed matter physics. After all, the discovery of the concepts of the Renormalization Group by Ken Wilson and others was being done simultaneously in both disciplines and the exchange of ideas was fruitful in both directions.
On the other hand, what the effective theories actually are depends on the context i.e. on the disciplines, too. In particle physics, people study effective actions for excitations of the vacuum – most of the environment is the vacuum. That's why any effective action is still a relativistic theory. On the other hand, condensed matter physics studies dynamics in a different environment or medium – various solids – so the Lorentz symmetry is spontaneously broken and one obtains non-relativistic effective field theories.
But the Cooper pairs in the BCS theory are exactly analogous to hadrons in particle physics – two examples of degrees of freedom in an effective theory that is valid beneath an energy scale but ignores some detailed phenomena that are only seen with high energies (per excitation).
In particle physics, the quantity deciding about the scale is roughly speaking $|p_\mu|$ – in the $c=1$ units, it doesn't matter which component of the energy-momentum we consider. In condensed matter physics, one must distinguish them because they don't obey $E\sim pc$ in general due to the breaking of relativity by the environment. The usual quantity deciding about the scale is the energy, not the momentum.
One must also be ready for different conventions. In condensed matter physics, they use the opposite sign of the beta-function for running couplings, for example, as they imagine the flow to go in the opposite direction. This is a purely sociological difference, much like the difference between mostly-plus and mostly-minus metric tensors.


TITLE: Two children -- probability one is a boy given the other is a boy: conflicting answers
QUESTION [0 upvotes]: Suppose a family has two children. The probability of a child being a boy is $1/2$, independent of the other. If we are given that one child is a boy, what is the probability the other is a boy as well.
I would calculate the probability as follows:
$$P(\text{two boys | at least one boy)} = \dfrac{P(\text{two boys)}}{P(\text{at least one boy})}.$$
Now, the probability of having two boys is clearly $1/4$. The bit that troubles me is the probability of having one boy. I see two ways to tackle this:

Suppose we count the children as (child 1, child 2). Then there are four possibilities: (boy, girl), (girl, boy), (boy, boy), (girl, girl). Then $P(\text{at least one boy})= 3/4$.
On the other hand, suppose I count the children not in order, but like {child 1, child 2}. Then there are $4-1$ possibilities: {boy, girl} = {girl, boy}, {boy, boy}, {girl, girl}. Hence $P(\text{at least one boy})= 2/3$

These give different answers... What should I do?

REPLY [3 votes]: Order is important, you can also relate two child as elder child and younger child, so lets call it {elder, younger}.
Now, the problem we are facing is weather to consider {boy,girl} and {girl,boy} as same or not. Off-course if we consider it as an ordered pair so they are different. If we would have considered it as just a collection or set then they are same.
Also it is important that the events of sample space to be equally likely. So, Considering as ordered pair makes the events of sample space equally likely, where as if we would have considered as set or collection than the {boy, girl} as set would be twice as likely to happen then the other events in sample space.
Or u can see it as, if the first child is boy/girl still it can fall in {boy, girl} set, and only after the child 2 it is in {boy, girl} set with 50% chance. For other sets like {boy, boy} the chance if 25%.
So it is about sample space with equally likely events.

REPLY [3 votes]: For visualization, you are assuming that 'the event has been made' and there are 2 people with boy and girl being equally likely. Then, the simple equations hold: $$P(\text{two boys}) = 1/4$$ and $$P(\text{at least one boy})= 3/4$$.
Now it is revealed that one of those is a boy, but you don't know which one. This leaves you with three out of four possibilities: (boy, girl), (girl, boy), (boy, boy).
Only one of them is "desirable", so the chance is 1/3, which could also be computed as you suggested:
 $$\dfrac{P(\text{two boys)}}{P(\text{at least one boy})} = 1/3$$.
Your 2nd option doesn't hold, since you merged two different outcomes into one (as we said, we don't know which one is a boy). (If you knew which one is a boy, then you'd only care about the other one being a boy and the probability would simply be $1/2$.)


TITLE: Proving Big O as lim f(n)/g(n) = 0
QUESTION [2 upvotes]: We have to prove that if $lim_{(n\rightarrow\infty)} \frac{f(n)}{g(n)} = 0$, then $f(n)$ is $O(g(n))$ but $g(n)$ is not $O(f(n))$.
I understand that because the limit is 0, then it can be said that $f(n) << g(n)$ (asymptotically smaller) but how would I go about proving this properly?

REPLY [0 votes]: The big O notation means that you can construct an equation from a certain set, that would grow as fast or faster than the function you are comparing.
So O(g(n)) means the set of functions that look like a*g(n), where "a" can be anything, especially a large enough constant.
So for instance, $f(n)= 99,998n^3+1000n$ is considered $O(n^3)$ because I can take the "$n^3$" part and pick a big enough constant so that it bounds the function.
One function that you could arbitrarily pick is $z(n)=99,999n^3$ and this function will be higher than $f(n)$. Of course, you could also pick $z(n)= n^{999}$, which would also bound it, but that's not the tightest, lowest order function that you can find. Therefore, $z(n)= n^{999}$ is not considered a big O bound for $f(n)$.
One way to prove that a function is smaller than another is through division and take the limit. If the answer tends to infinity, then you know the numerator grows faster than the denominator. If the answer tends to 0, then you know that whatever is in the denominator bounds the function on top.
If you were given $g(n)$, then if you can find a function $f(n)$ and a constant "a"
$$\frac{g(n)}{a*f(n)}= 0$$
as n approaches infinity, then you just proved that $g(n)$ belongs to $O(f(n))$


TITLE: A little question about the existence theorem of Nash equilibrium in game theory
QUESTION [0 upvotes]: Recently when I started reading Nash's paper, I found a little question about the linearity of payoff functions. Is it an assumption? Or did I miss some idea about the payoff function and its extension with my lack of basic knowledge?
Here is the original paper, and the problem is on page 287, line 8.
http://www.jstor.org/discover/10.2307/1969529?uid=3739216&uid=2134&uid=2&uid=70&uid=4&sid=21103378096701

REPLY [1 votes]: That line only states that there is a unique extension of the payoffs to profiles of mixed strategies that is linear. This extension is then used in the definition of equilibrium points. So implicitly, Nash is using expected utility as the underlying decision theory.


TITLE: Showing that a polynomial is a unit in a quotientring
QUESTION [1 upvotes]: In this exercise I have a polynomial ring over a finite field $F_2$:$(F_2[X],+,*)$ There is then given an ideal : I $=<X^3+X+1>$.
I am then trying to show that $X^2+X+1 + I$ is a unit in $F_2[X]/I$ by using the extended Euclidean algorithm on $X^3+X+1$ and $X^2+X+1$.
I tried using this algorithm and then got that  $(X^3+X+1)*r(X)+(X^2+X+1)*s(X)=gcd(X^3+X+1,X^2+X+1) => (X^3+X+1)*(X+1)+(X^2+X+1)*X^2=1$
I can't really figure out if this is right, and if it is what I am suppose to do from here to show that the given expression is an unit.

REPLY [2 votes]: You have already found the inverse, it is: $X^2 + I$.
You know that:
$(X^3 + X + 1)(X + 1) + (X^2 + X + 1)X^2 = [X^4 + X^3 + X^2 + (X+X) + 1] + [X^4 + X^3 + X^2]$
Now in $F_2[X]$, for any element, we have $f(x) + f(x) = (1 + 1)(f(x)) = 0(f(x)) = 0$.
So in the product above, we continue:
$[X^4 + X^3 + X^2 + (X+X) + 1] + [X^4 + X^3 + X^2] = [X^4 + X^3 + X^2 + 1] + [X^4 + X^3 + X^2]$
$= (X^4 + X^4) + (X^3 + X^3) + (X^2 + X^2) + 1 = 0 + 0 + 0 + 1 = 1$.
This shows your gcd calculation is correct.
Now take your calculation mod $I$:
$[(X^3 + X + 1) + I][(X + 1) + I] + [((X^2 + X + 1) + I][X^2 + I] = 1 + I$
$[0 + I][(X + 1) + I] + [((X^2 + X + 1) + I][X^2 + I] = 1 + I$
($(X^3 + X + 1) + I = 0 + I = I$, because $X^3 + X + 1$ is in $I$).
$[0 + I] + [((X^2 + X + 1) + I][X^2 + I] = 1 + I$
(because $0 + I = I$ is an ideal, and "absorbs" anything we multiply it by)
$[((X^2 + X + 1) + I][X^2 + I] = 1 + I$
(since $0 + I = I$ is the additive identity of the quotient ring, and we can omit it in any sum).
This last equation shows explicitly that $(X^2 + X + 1) + I$ is indeed a unit.


TITLE: question about convergence series
QUESTION [1 upvotes]: I'm not sure I understand why $$\sum_{n=1}^{\infty}\frac{1}{\sqrt{n}}(4pq)^n<\infty $$ when $$p\ne0.5 , p+q=1$$
I know that $\sum_{i=1}^{\infty}\frac{1}{\sqrt{n}}=\infty$
But why when we have $\frac{1}{\sqrt{n}}$ multiple a number that is smaller than 1, we get a  convergence series?

REPLY [3 votes]: Note that $4 p q < 1$ (Why?). Let $4 pq = a < 1$. We then have
$$\sum_{k=1}^{\infty} \dfrac{a^k}{\sqrt{k}} < \sum_{k=1}^{\infty} a^k = \dfrac{a}{1-a} < \infty$$
The series you have is the polylogarithm function, $\text{Li}_{1/2}(a)$.


TITLE: Operation that returns a unique result for each unordered set of numbers
QUESTION [2 upvotes]: What operation $f$ can I apply to any two numbers $a$ & $b$, such that $$f(a,b) = f(b,a)$$
where $f(a,b)$ is unique for any combination of a & b in the set of whole numbers?
P.S. I'm really not sure what tag to use here, I'd appreciate someone adding the correct one.
A word on why:
I have a database table with two columns $a$ and $b$.
I'd like to ensure that there are no duplicate rows in my table.
However, I don't care about the order of $a$ and $b$.
a | b
--+--
1 | 2
2 | 1

Is effectively a duplicate.

REPLY [2 votes]: One could use
$$ f(a, b) = 2^{2a + 1} + 2^{2b + 1}. $$
It is easy to see that $f$ satisfies $f(a, b) = f(b, a)$.
Note that $2^{2x + 1} > 0$ for all $x \in \mathbb Z$ and also (letting $x = \max \{a, b\}$) we have
$$2^{2x + 1} < f(a, b) \leq 2 \cdot 2^{2x + 1}.$$
To prove that $f$ has your uniqueness condition, we consider cases depending on two pairs $(a, b)$ and $(c, d)$ (where without loss of generality the first number in the pair is the larger one) of whole numbers:

$a = c, b \neq d$ or $a \neq c, b = d$: Should be clear from the definition of $f$.
$a \neq c, b \neq d$. Then by symmetry (one could exchange the pairs) we may assume $a < c$ and hence
$$
\begin{align*}
f(a, b)
&= 2^{2a + 1} + 2^{2b + 1} \\
&\leq 2 \cdot 2^{2a + 1} \\
&< 2^{2(a + 1) + 1} \\
&\leq 2^{2c + 1} \\
&\leq f(c, d).
\end{align*}
$$
In particular, this means $f(a, b) \neq f(c, d)$.

It follows that $f$ is a function satisfying your conditions :)


TITLE: Invariant distribution of a Markov chain - joint probability
QUESTION [0 upvotes]: I have found the following invariant distribution $\pi$, invariant w.r.t. my transition probability matrix: $$P = \begin{bmatrix}
0.8 & 0.2 \\ 0.5 & 0.5
\end{bmatrix}$$
$\pi = [0.7142857, 0.2857143]$
I now want to know - given that the initial state is drawn at random from $\pi$ - what is the joint probability that $X_{t} = 1$ and $X_{t+1} = 1$. Is it right to say that it is 0.7142857? Or am I not understanding what the meaning of invariant distribution is?
I also read that the joint ($X_t, X_{t+1}$) has to do with $X_{t}$ ~ $\pi$  and $X_{t+1}$|$X_{t}$ ~ $P$, but not sure of how to use this information.

REPLY [0 votes]: $P(X_t=1,X_{t+1}=1)=P(X_{t+1}=1|X_t=1)P(X_t=1)=(0.8)(0.7142857)$ (assuming that your states are named $1$ and $2$). The distribution of $X_t$ is $\pi$ for all $t$ but $P(X_{t+1}=1|X_t=1)$ is given by the transition matrix.


TITLE: Is there a $1-1$ map of the interior of the $n$-simplex to $\mathbb{R}^n$?
QUESTION [1 upvotes]: I'm looking for a simple $1-1$ map from the interior of the standard $n$-simplex that covers $\mathbb{R}^n$. Any suggestions?

REPLY [1 votes]: I can tell you how to construct one.  Whether it is simple enough is for you to determine.  Position the simplex with the origin of $\Bbb R^n$ at its center.  Now scale every open radial segment in the simplex to $(0,\infty)$ by your favorite bijection.  In whatever direction you choose, let the distance from the origin to the simplex be $d$.  Take the point that is $r$ from the origin in the simplex and map it to the point that is$\frac 1{1-\frac rd}$ from the origin in $\Bbb R^n$.  The complicated part is coming up with $d$ given an angle of interest.


text:
Since Whitehead's original  work \cite{Whi36a,Whi36}, a number of authors have refined Whitehead's Algorithm and applied it
to related algebraic questions. Section I.4 of the book of Lyndon and
Schupp \cite{LynSch77} gives a version of Whitehead's Algorithm and
some of the classical applications.

More recently, Stallings \cite{Sta99} and Stong \cite{Sto97} gave
3--manifold versions of Whitehead's Algorithm. In each of these papers
the aim was to show that a version of Whitehead's Algorithm could be
used to determine if, given a finite list of words $(w_1,\dots w_k)$
in $F$, there is a free splitting of $F$ such that every $w_i$ is
conjugate into one of the free factors. Stallings calls this
``algebraically separable''. This algebraic question is
then shown to be equivalent to a geometric question about whether or
not a collection of curves in a handlebody has a property that
Stallings calls ``geometrically separable'' and Stong calls ``disk-busting''.

In this section we
review Whitehead's Algorithm. Our language is similar to that of
Stallings and Stong, except that our group actions are on the left and
path concatenations are on the right, while they use the opposite convention.

\subsection{Whitehead Graphs}
Let $w\in F$ be a cyclically reduced word. Let
$\mathcal{B}=\{a_1,\dots, a_n\}$ be a free basis of $F$.
The \emph{Whitehead Graph of $w$ with respect to $\mathcal{B}$}, $\Wh_\mathcal{B}(*)\{w\}$, is the graph
with $2n$ vertices labeled $a_1,\dots, a_n, \bar{a}_1,\dots \bar{a}_n$, and an edge between vertices $v$ and $v'$ for \emph{each}
occurrence of $\bar{v}v'$ in $w$ (as a cyclic word).
The graph depends on the choice of $\mathcal{B}$, and, of course, on
$w$, but we will write $\Wh(*)$ when these are clear.

\begin{remark}
  At present the $(*)$ may be ignored; it will be explained in the next section.
\end{remark}

For example, if $F=\left<a,b\right>$ Figures~\ref{fig:Wh(a)}-\ref{fig:1Wh(a2ba2B2)} show some Whitehead Graphs.

\begin{figure}[ht]
\begin{minipage}[b]{0.45\textwidth}
\labellist \small
\pinlabel $b$ [bl] at 87 164
\pinlabel $\bar{b}$ [tl] at 87 3
\pinlabel $a$ [tl] at 165 83
\pinlabel $\bar{a}$ [tr] at 4 83
\endlabellist
  \centering
  \includegraphics[height=\figstandardheight]{Pictures/Wha}
  \caption{  $\Wh(*)\{a\}$}
\label{fig:Wh(a)}
\end{minipage}
\hfill
\begin{minipage}[b]{0.45\textwidth}
\labellist \small
\pinlabel $b$ [bl] at 87 164
\pinlabel $\bar{b}$ [tl] at 87 3
\pinlabel $a$ [tl] at 165 83
\pinlabel $\bar{a}$ [tr] at 4 83
\endlabellist
  \centering
  \includegraphics[height=\figstandardheight]{Pictures/Whab2}
  \label{fig:ab2}
  \caption{  $\Wh(*)\{ab^2\}$}
\end{minipage}

\bigskip \bigskip
\begin{minipage}[b]{0.45\textwidth}
\labellist \small
\pinlabel $b$ [bl] at 87 164
\pinlabel $\bar{b}$ [tl] at 87 3
\pinlabel $a$ [tl] at 165 83
\pinlabel $\bar{a}$ [tr] at 4 83
\endlabellist
  \centering
    \includegraphics[height=\figstandardheight]{Pictures/WhabAB}
  \caption{  $\Wh(*)\{ab\bar{a}\bar{b}\}$}
  \label{fig:Wh(abAB)}
\end{minipage}
\hfill
\begin{minipage}[b]{0.45\textwidth}
\labellist \small
\pinlabel $b$ [bl] at 87 164
\pinlabel $\bar{b}$ [tl] at 87 3
\pinlabel $a$ [tl] at 165 83
\pinlabel $\bar{a}$ [tr] at 4 83
\endlabellist
  \centering
\includegraphics[height=\figstandardheight]{Pictures/wha2ba2B2}
  \caption{$\Wh(*)\{a^2ba^2\bar{b}^2\}$}
  \label{fig:1Wh(a2ba2B2)}
\end{minipage}
\end{figure}

Notice that $\Wh(*)\{a\}$ is disconnected; the vertices $b$ and $\bar{b}$
are isolated.

$\Wh(*)\{ab^2\}$ is connected but becomes disconnect if
the vertex $b$ (or $\bar{b}$) is deleted;
$b$ and $\bar{b}$ are \emph{cut vertices}.

$\Wh(*)\{ab\bar{a}\bar{b}\}$ is connected and has no cut
vertices.

$\Wh(*)\{a^2ba^2\bar{b}^2\}$ is also connected with no cut vertices,
and has multiple edges between vertices $a$ and $\bar{a}$.

More generally, one can make a Whitehead graph representing  finitely
many words $w_1,\dots, w_m$.
We call this Whitehead graph $\Wh(*)\{w_1,\dots ,w_m\}$ or
$\Wh(*)\{\mathcal{L}\}$, where $\mathcal{L}$ is the line pattern generated by
$\{w_1,\dots , w_m\}$.

\subsection{Whitehead Automorphisms}
Let $\phi$ be an automorphism of $F$.
Applying $\phi$ changes the Whitehead graph
$\Wh_\mathcal{B}(*)\{w_1,\dots , w_m\}$ to the Whitehead graph
$\Wh_\mathcal {B}(*)\{[\phi(w_1)],\dots , [\phi(w_m)]\}$, where  $[\phi(w_i)]$
means choose a cyclically reduced word in the conjugacy class of $\phi(w_i)$.

An automorphism that permutes $\mathcal{B}$ or swaps a generator with
its inverse gives an isomorphic Whitehead graph.

\begin{definition}\label{definition:whaut}
A \emph{Whitehead automorphism} is an automorphism of the following
form:
Pick $x\in \mathcal{B}\cup\bar{\mathcal{B}}$, a generator or the
inverse of a generator.
Pick $Z\subset \mathcal{B}\cup\bar{\mathcal{B}}$ such that $x\in Z$
and $\bar{x}\notin Z$.

  Define an automorphism $\phi_{x,Z}$ by defining $\phi_{x,Z}(x)=x$ and for
the rest of the generators $y\in\mathcal{B}$:
\[\phi_{x,Z}(y)=
\begin{cases}
  y & \text{ if } y\notin Z\text{ and }\bar{y}\notin Z\\
  xy & \text{ if } y\in Z\text{ and }\bar{y}\notin Z\\
  y\bar{x} & \text{ if } y\notin Z\text{ and }\bar{y}\in Z\\
  xy\bar{x} & \text{ if } y\in Z\text{ and }\bar{y}\in Z\\
\end{cases}
\]
\end{definition}

We say that the automorphism $\phi_{x,Z}$ is the \emph{Whitehead
automorphism that pushes $Z$ through $x$}.

To visualize what is happening, consider the rose with one vertex and
one oriented loop for each element of $\mathcal{B}$. The fundamental group is $F$.
The Whitehead automorphism $\phi_{x,Z}$ is the automorphism of the
fundamental group induced by the homotopy equivalence that pushes
one or both ends of the $y$--loop around the $x$--loop according to whether
$y$ or $\bar{y}$ or both are in $Z$, or leaves the $y$--loop alone if
neither $y$ nor $\bar{y}$ are in $Z$. See also \fullref{sec:whautrevisit}.

Define the \emph{complexity} of the collection $w_1,\dots,
w_n$ to be the number of edges of $\Wh(*)\{w_1,\dots, w_m\}$.
This is equivalent to the sum of the lengths of the $w_i$, and also  half the sum of the valences of the
vertices.

Comparing $\Wh_\mathcal{B}(*)\{w_1,\dots , w_m\}$ to
$\Wh_\mathcal {B}(*)\{[\phi_{x,Z}(w_1)],\dots , [\phi_{x,Z}(w_m)]\}$
we see that the valences of vertices other than $x$ and $\bar{x}$ do
not change.
The new valence of $x$ and $\bar{x}$ is equal to the number of edges
that go between $Z$ and $Z^c$.
Thus, the Whitehead automorphism reduces the complexity of the
Whitehead graph exactly when there are fewer
edges joining $Z$ and $Z^c$ than the valence of $x$.

\begin{reftheorem}
  $\Aut(F)$ is generated by:
  \begin{enumerate}
  \item exchanges of a generator with its inverse
\item permutations of the generators
\item Whitehead automorphisms
  \end{enumerate}
\end{reftheorem}
  This is clear since this set of automorphisms contains the Nielsen
  generators for $\Aut(F)$ \cite{Nie24}.

Whitehead's Algorithm is as follows:
First, check if any Whitehead automorphisms reduce
the complexity of the Whitehead graph. Repeat. Once you have reduced
to minimal complexity, there are only finitely many graphs to
consider. Build a graph with one vertex for each possible Whitehead
graph with the given complexity, and an edge between two vertices if
one of the given generators of the automorphism groups takes one graph
to the other. One can then show that the desired automorphism exists
if and only if the reduced Whitehead graphs for the two lists of words
lie in the same connected component of this graph.

If $\{w_1,\dots , w_m\}$ is a subset of a free basis then the minimal
complexity Whitehead graph should have  $m$ disjoint edges.

If there is a free splitting $F=F'*F''$ with every $w_i$ in $F'$ or
$F''$ then the minimal complexity Whitehead graph should be disconnected.

The presence of a cut vertex in the Whitehead graph indicates that the
graph is not reduced. If $x$ is a cut vertex, let $Z$ be the union of
$\{x\}$ and the vertices
of a connected component
of $\Wh(*)\{\mathcal{L}\}\setminus \{x\}$ not containing $\bar{x}$.
The Whitehead automorphism $\phi_{x,Z}$ reduces complexity.

One application of Whitehead's Algorithm is that a word $w$ is an
element of a free basis of $F=F_n$ if and only if the minimal complexity
Whitehead graph for $w$ consists of a single edge and $2(n-1)$
isolated vertices.

More generally, the \emph{width} of an element $w$ is the rank of the
smallest free factor of $F$ containing $w$. The minimal complexity
Whitehead graph for an element of width $m$ in $F=F_n$ consists of
$2(n-m)$ isolated vertices and a connected graph without cut vertices
on the remaining vertices.

\endinput

config: arxiv


TITLE: Mayer-Vietoris sequence in homology with local coefficients
QUESTION [6 upvotes]: Background. I'm trying to compute some homology groups using a Mayer-Vietoris argument, but I really need local coefficients.
Question 1. What does the Mayer-Vietoris sequence look like when using local coefficients?
Consider an open cover $X = U \cup V$ with inclusion maps
$$\begin{array}{ccccc}
& & U \cap V & &\\
& i \swarrow & & \searrow j &\\
U & & & & V\\
& k \searrow & & \swarrow l &\\
& & X & &\\
\end{array}$$
and a coefficient module $M$ on $X$. (Assume all four spaces are path-connected if needed.) I believe that the Mayer-Vietoris sequence takes the form
$$\ldots \to H_n(U \cap V; (ki)^*M) \to H_n(U;k^* M) \oplus H_n(V;l^*M) \to H_n(X;M) \to$$
$$\to H_{n-1}(U \cap V; (ki)^*M) \to \ldots$$
where $k^*M$ denotes the restriction of $M$ to $U$ along the inclusion $k \colon U \to X$. Is that correct?
Question 2. Are there good references for homology with local coefficients, and in particular the Mayer-Vietoris sequence in that context?
Sections 5.3 and 5.4 of Lecture Notes in Algebraic Topology by J. Davis and P. Kirk are a good start, especially Theorem 5.13 and the remark afterwards.
Question 3. Are there good references that treat local coefficients as functors from the fundamental groupoid $\Pi_1(X) \to Ab$ and describe homology with local coefficients in that context?
I wouldn't mind reducing the problem to the case of path-connected spaces, but I feel like the argument would be cleaner without such reductions or choices of basepoints.

REPLY [7 votes]: Whitehead's "Elements of Homotopy Theory", in particular chapter VI, seems to have everything you ask for. (Note that the Mayer-Vietoris sequence is a formal consequence of excision and the long exact sequence of a pair; see section 2.3 of Hatcher's book).


TITLE: Absolute value of limit can be taken outside
QUESTION [0 upvotes]: We have a sequence of functions $f_n$ that converge to $f$.
As part of a proof I am writing, if I can prove that
$$|f(x) - f(y)| = \lim_{n \to \infty}|f_n(x) - f_n(y)|$$
then I am done. Proving this requires me to show that
$$|\lim (f_n(x) - f_n(y)) | = \lim |f_n(x) - f_n(y)|$$
and I'm not sure how I can do that. I found this answer limit of absolute value of something equals absolute value of limit of something? which says it exists by 'continuity of absolute value' although I am not sure how that justifies it. Could someone elaborate?

REPLY [1 votes]: We note that if $x_n \to x$ and $g$ is continuous, then:
$$
\lim_{n \to \infty} g(x_n) = g\left(\lim_{x \to \infty} x_n\right)
$$
i.e. the limit and the function can be interchanged. The absolute value function $x \mapsto |x|$ is continuous. Therefore, in your case we have:
\begin{align*}
|f(x) - f(y)| &= \left|\left(\lim_{n \to \infty} f_n(x)\right) - \left(\lim_{n \to \infty} f_n(y)\right)\right| \\
&= \left|\lim_{n \to \infty} (f_n(x) - f_n(y))\right| \\
&= \lim_{n \to \infty} |f_n(x) - f_n(y)|
\end{align*}