TITLE: Finding the voltage of an inductor in a RL series circuit
QUESTION [0 upvotes]: Here is the solution:

This assigned question is an odd one since it doesn't seem to have anything to do with phasors which is the chapter I am currently studying. I know that that the phase relationship in a RL circuit is that voltage leads current but I'm not sure why they used Pythagorean theorem.

REPLY [1 votes]: it doesn't seem to have anything to do with phasors

But it does since this is the way one adds phasors.  Assume you have two series connected circuit elements with phasor voltages that differ in phase by the angle $\phi$.
$$\vec V_1 = V_1$$
$$\vec V_2 = V_2e^{j\phi}$$
Since the voltage across the series combination is the sum of the individual phasor voltages, the magnitude of the phasor voltage sum is given by:
$$|\vec V_{sum}| = \sqrt{V^2_1 + V^2_2 + 2V_1V_2\cos\phi}$$
In the case that $\phi = 90^\circ$, as for the series connected resistor and inductor, we have
$$|\vec V_{sum}| = \sqrt{V^2_1 + V^2_2 + 2V_1V_2\cos90^\circ}= \sqrt{V^2_1 + V^2_2} $$

How do you know that they are 90 degrees out of phase?

The resistor and inductor are in series thus they have identical current
$$\vec I_R = \vec I_L =\vec I $$
The voltage across the resistor is
$$\vec V_R = R \vec I_R = R \vec I $$
and the voltage across the inductor is
$$\vec V_L = j\omega L \vec I_L =  j\omega L \vec I$$
We can express the voltage across the inductor in terms of the voltage across the resistor
$$\vec V_L = j\frac{\omega L}{R}\vec V_R = \frac{\omega L}{R}\vec V_R\, e^{j90^\circ}$$
Thus, see that the inductor voltage and resistor voltage are in quadrature - they differ in phase by $90^{\circ}$


TITLE: Prove $m=3k+1 \quad m,k \in \mathbb Z \implies m^2=3l+1 \quad m,l \in \mathbb Z$
QUESTION [4 upvotes]: Suppose we call an integer "throdd" $\iff$ $m=3k+1$ for some integer
  $k$. Prove that the square of any throdd integer is throdd.

So here is what I have so far:
$$(3k+1)^2 = 3k+1$$
$$(3k+1)(3k+1) = 3k+1$$
Am I going in the right direction?
2nd part: $(3k+1)(3k+1)= 9k^2 + 6k + 1$
$3k(3k+ 2) +1$
So im confused because $(3k +2)$ is not m and $3k(3k+2) +1$ isnt in the form of $3m+1$?

REPLY [3 votes]: HINT. You need to show that $(3k+1)^2$ can be written as $3 m +1$ for some $m$. You are real close.

REPLY [2 votes]: That's not quite right. I'll start you off.
$$m^2 = (3k+1)^2 = (3k+1)(3k+1) = 9k^2+6k+1.$$
What do you notice about the first two terms?


TITLE: Double Integral: Finding a suitable change of variables
QUESTION [0 upvotes]: Here is a question that I am trying to review:
Perform a suitable change of variables to rewrite the integral $\iint_R\ xy^2\,dA$
 where $R$ is the region bounded by the lines $x-y=2$, $x-y=-1$, $2x+3y=1$, and $2x+3y=0$. Do not evaluate the integral.
I let $u=x-y$ and $v=2x+3y$.
The jacobian did not simplify nicely. What would be a suitable change of variables?

REPLY [1 votes]: Figured it out, its actually rather easy.
Let $u=x-y$ and $v=2x+3y$
So $u = 2$ and $u = -1$ and $v = 1$ and $v=0$. These will be our bounds for our new integration.
We can write,
$3u=3x-3y$
$v=2x+3y$
Solving for x by adding together,
$3u +v=5x$ implies $x=(3u+v)/5$
We can also write,
$-2u=-2x+2y$
$v=2x+3y$
Solve for y by adding together,
$v-2u=5y$ implies $y=(v-2u)/5$
Find the jacobian $|d(x,y)/d(u,v)|$
Now we can integrate with our new bounds. Solved.


TITLE: Prove that limited increasing or decreasing successions have a limit.
QUESTION [4 upvotes]: Be $u_n$ an increasing sequence of numbers ${(u_1,u_2,u_3, \ldots)}$ such that for all $\ n$, $u_{n-1}\le u_n$
Prove that if $u_n\le a, a \in \mathbb R$, for all n then $\lim_{n\rightarrow\infty}u_n =b $ for some number $b\le a$.
I am using as definition of limit of a succession the following:
$\lim_{n\rightarrow\infty}u_n =b \Leftrightarrow  ∀\delta \gt 0, ∃p \in \mathbb N :n\gt p \Rightarrow |u_n -b|\lt \delta$

REPLY [1 votes]: This is the https://en.wikipedia.org/wiki/Monotone_convergence_theorem. Here's a copy of the proof. If you have questions you can ask in the comments:

Let $\{ a_n \}$ be such a sequence. By assumption, $\{ a_n \}$ is non-empty and bounded above. By the least upper bound property of real numbers, $c = \sup_n \{a_n\}$ exists and is finite. Now, for every $\varepsilon > 0$, there exists $N$ such that $a_N > c - \varepsilon $, since otherwise $c - \varepsilon $ is an upper bound of $\{ a_n \}$, which contradicts to the definition of $c$. Then since $\{ a_n \}$ is increasing, and $c$ is its upper bound, for every $n > N$, we have $|c - a_n| \leq |c - a_N| < \varepsilon $. Hence, by definition, the limit of $\{ a_n \}$ is $\sup_n \{a_n\}.$


TITLE: Area of curve in parametric equation
QUESTION [1 upvotes]: Given the curve defined by the parametric equations:
$$
x=7\cos{3t}\\
y=7\sin{3t}\\
0\le t\le2\pi
$$
What is the area of the region bounded by this curve?
Clearly,
$$
x^2+y^2=(7\cos{3t})^2+(7\sin{3t})^2=7^2
$$
which is a circle centered at the origin and radius 7. Therefore, the area is $\pi\cdot7^2=49\pi$.
However, it is also true that the area is
$$
A=\int{ydx}=\int_{0}^{2\pi}{y(t)x'(t)dt}=\int_{0}^{2\pi}{7\sin{3t}(-7\sin3t)3dt}=-49\int_{0}^{2\pi}{\sin^2{3t}\;3dt}=-49\cdot(3\pi)=-3(49\pi)
$$
which is the same area as before, but multiplied by $-3$.
What is answer is correct? The $3t$ in the $\sin$ and $\cos$ terms means that as $t$ goes from $0$ to $2\pi$, the circle is traversed $3$ times, right? Which would explain why the area is multiplied by 3. But what about the minus sign?

REPLY [1 votes]: Parametric curves are just screaming out to be solved in the complex plane. Consider that
$$
z=x+iy=7(\cos 3t+i\sin 3t)=7e^{i3t}\\
A=\frac{1}{2}\int\mathfrak{Im}\{z^* \dot z\}\ dt
$$
$$
z^*=7e^{-i3t}\\
\dot z=21ie^{-i3t}\\
\mathfrak{Im}\{z^* \dot z\}=147
$$
Therefore
$$A=\frac{147}{2}\int_0^{2\pi}dt=147\pi$$
Or, if we wish to avoid the ambiguity of going around the circle three times,
$$A=\frac{147}{2}\int_0^{2\pi/3}dt=49\pi$$
Easy as $\pi$.


TITLE: quantifier restrictions in natural deduction
QUESTION [1 upvotes]: Universal elimination and existential introduction are easy. But when it comes to existential elimination and universal introduction, there are some restrictions which I don't fully understand.
Let me give an example:

Show that if ∀x(P(x) → Q(x)) and ∃xQ(x) → R(y) are true, then ∀x(P(x)
  → R(y)) is true by natural deduction.

$P(t)$ --assumed
$P(t) \rightarrow Q(t)$ -- universal elimination from the first premise
$Q(t)$-- modus ponens 1,2

Now I want to make use of the second premise:

$Q(t) \rightarrow R(y)$ -- assumed

I am not sure but I think I cannot do that since the constant $t$ has been used before. Should I give it another letter and proceed like this?

$Q(w) \rightarrow R(y)$ -- assumed
$R(y)$ -- modus ponens 3, 4(can I do this?)
$R(y)$ -- existential elimination (second premise, 4, 5)
$P(t) \rightarrow R(y)$ -- implication introduction
universal introduction of 7

Can somebody please explain how to go before/after the line 4 so that existential elimination and universal generalization wouldn't be a problem?
EDIT:
After thinking and thinking I have come up with this
$\\1.\forall x(P(x)\rightarrow Q(x))$ - premise
$\\2. \exists xQ(x) \rightarrow R(y)$ -premise
$\\3.\forall zP(z)$ -assumed
$\\4.Q(a)\rightarrow R(y)$ -assumed
$\\5.P(a)\rightarrow Q(a)$ -universal\ elimination from  \1
$\\6.  P(a)$ -universal\ elimination\ from\ 3
$\\7. Q(a)$ -modus ponens\ 5,6
$\\8. R(y) $-modus ponens \ 4,7
$\\9. R(y) $-existential \ elimination \ 2,4,8
$\\10. \forall z P(z) \rightarrow R(y)$ -implication \ introduction\ 3, 9
$\\11. P(a)$ - assumed
$\\12. P(a) \rightarrow R(y) $- universal\ elimination from\ 10
$\\13. R(y) $- modus ponens\ 11,12
$\\14. P(a) \rightarrow R(y) $-implication\ introduction\ 11, 13
$\\15. \forall x(P(x) \rightarrow R(y)) $- universal introduction from\ 14
Can anybody tell me if this contains any errors?

REPLY [3 votes]: You get to Q(t) in step 3.  So, just use existential introduction to infer ∃xQ(x).  Then infer R(y) by modus ponens.  Then us conditional introduction to get to (P(t) $\rightarrow$  R(y)).
Now, note that we have no assumptions in place, only the hypotheses which you gave which we aren't going to discharge.  Neither of them contain the variable 't'.  Thus, we can use universal introduction to infer the conclusion ∀x(P(x) → R(y)).
The restriction on the universal introduction rule just says that we can't replace the letter when we have that letter in some hypothesis or assumption in effect.  But, we didn't have any such assumption or hypothesis with 't' in it in effect when we used the universal introduction rule above, and thus it works out as valid.


TITLE: Can a scalar field transform nontrivially under a local special conformal transformation?
QUESTION [2 upvotes]: Is there any way to have a scalar field that transforms non-trivially under local special conformal transformations? Just by the index structure, I can see that the possibilities are
$$\begin{align}
\delta_K \phi &= \Lambda_{K}^\mu (x) \partial_\mu \phi \,, &
\delta_K \phi &= x^\mu \Lambda_{K \mu} (x)
\end{align}$$
where the subscript $K$ represents transformation with respect to the special conformal transformation, and $\Lambda_{K\mu} (x)$ is the parameter of special conformal transformations.
Considering the Poincare and dilatation transformations of the scalar $\phi$, I can see that both the first and the second possibilities are just orbital parts of Poincare and (inhomogeneous) dilatation transformations respectively.
Am I missing something? Is there really no way to write down a scalar that transforms non-trivially under local special conformal transformations?

REPLY [1 votes]: I don't completely understand the question. How a scalar transforms is completely dictated by conformal symmetry. The transformation law is
$$K_\mu \phi(x) = \big(\Delta x_\mu + x_\mu \, x_\nu \partial_\nu -x^2 \partial_\mu \big) \phi(x)$$
or if you wish
$$\delta_K \phi(x) = a^\mu K_\mu \phi(x)$$
where $a^\mu$ are the infinitesimal parameters of the special conformal transformation. The above holds for a scalar primary of scaling dimension $\Delta$. As you know, you can also have scalar descendants, which will have more complicated transformation laws. For example, if $A_\mu$ is a vector operator, then $\partial_\mu A_\mu$ is a scalar but the transformation law will have one extra term coming from the $[K_\mu,P_\nu]$ commutator.
I hope this answers your question!


TITLE: finding value of $\sum^{10}_{i=0}\frac{1}{a_{i}}$
QUESTION [2 upvotes]: Let $a_{0},a_{1},a_{2},a_{3},\cdots \cdots a_{n}$ be a sequence of numbers satisying $(3-a_{n+1})(6+a_{n}) = 18$ and $a_{0} = 3.$ then find $\displaystyle \sum^{10}_{i=0}\frac{1}{a_{i}}$
from $18-6a_{n+1}+3a_{n}-a_{n}a_{n+1} = 18.$ So $6a_{n+1}-3a_{n}+a_{n}a_{n+1} =0$
want be able to go further, could some help me, thanks

REPLY [2 votes]: Hint
Starting from $$6a_{n+1}-3a_{n}+a_{n}a_{n+1} =0$$ divide each term by $a_{n}a_{n+1}$ to get $$\frac 6{a_n}-\frac 3{a_{n+1}}+1=0$$ Now, define $b_n=\frac 1{a_n}$ and solve.

REPLY [1 votes]: From the condition we have $$-6a_{n+1}+3a_n-a_na_{n+1}=0$$ or
$$-\frac{6}{a_n}+\frac{3}{a_{n+1}}-1=0$$ or
$$-6\left(\frac{1}{a_0}+\frac{1}{a_1}+...+\frac{1}{a_{10}}\right)+3\left(\frac{1}{a_1}+...+\frac{1}{a_{11}}\right)-11=0$$
and for the ending it remains to find a value of $a_{11}$.


TITLE: number of combinations colouring 10 eggs with 4 colours if one or 2 colours can be used at the same time
QUESTION [0 upvotes]: I started to solve this question and realised, that if I just add up all the possibilities, it is going to take a lot of time:
Here is the complete question from the textbook:

Eggs that are all of the same size and shape are painted for Easter, and we are interested in how many eggs have which colour combination. Suppose each egg is painted with either a single colour or with two different colours. Compute the number of possibilities to:
a) Paint ten eggs if four colours are available,
b) Paint four eggs if ten colours are available.

I have started this way: all the eggs can be coloured in one colour,
all the eggs can be coloured in two colours, 3 and 4.  After that: all the eggs can be coloured in 2 colours and so on.  But that seems to get a long journey.  Is there any faster possibility solving this problem?
I think, that those 2 problems are related. So solving the first is crucial for the second.
Thanks a lot.

REPLY [3 votes]: If there are $c$ actual colors available there are $c_*:=c+{c\choose2}$ distinguishable ways to color an egg with one or two colors. Given $n$ eggs we then have to find the number of nonnegative integer $c_*$-tuples $\bigl(x_k\bigr)_{1\leq k\leq c_*}$ satisfying
$$x_1+x_2+\ldots+ x_{c_*}=n\ .$$
This is a stars and bars problem.


TITLE: Do we distinguish two singular simplices if they have different vertex orders?
QUESTION [2 upvotes]: We define a $\textbf{singular $n$-simplex}$ in $X$ to be a continuous map $\sigma:\Delta^n\to X$ where $\Delta^n$ is the standard $n$-simplex. Now, as an example, Let $X$ be a singleton $\{p\}$. Then is the number of $1$-simplices in $X$ one or two? I think it could be one because there is only one continuous map on $\Delta^1$ into $X$. But since $\Delta^1$ has two orders $[v_0,v_1]$ and $[v_1,v_0]$, I think the answer could be two (namely, $[v_0,v_1]\to X$ and $[v_1,v_0]\to X$).

REPLY [6 votes]: This is an interesting question.
You got two answers conforming that there is only one continuous map on $\Delta^1$ into $X$, and of course this is correct. The standard $n$-simplex $\Delta^n$ is a topological space and nothing else, therefore the continuous maps living on $\Delta^n$ do not depend on a vertex ordering.
But if we consider the complete singular complex $C_*(X) = (C_n(X), \partial_n )$  of $X$, we see that the boundaries $\partial_n : C_n(X) \to C_{n-1}(X)$ depend on a particular vertex ordering of  $\Delta^n$. In fact, the standard $n$-simplex is the convex hull of the $n+1$ standard basis vectors $e^{n+1}_0,\ldots, e^{n+1}_n$ of $\mathbb R^{n+1}$. The indices $i = 0,\ldots,n$ give a natural vertex ordering of  $\Delta^n$. This allows to define $n+1$ face-emdeddings $\delta_i : \Delta^{n-1} \to  \Delta^n$, $i = 0,\ldots,n$, by mapping $e^n_j$ to $e^{n+1}_j$ for $i < j$ and to $e^{n+1}_{j+1}$ for $j  \ge i$. Then we define
$$\partial_n(\sigma) = \sum_{i=0}^n (-1)^i \sigma \delta_i .$$
You see that the face-emdeddings $\delta_i$ do depend on the vertex ordering. One could consider "ordered singular simplices" in form of pairs $(\sigma : \Delta^n \to X, o_n)$ with a vertex ordering $o_n$ of $\Delta^n$. This can be described in form of a sequence $e^{n+1}_{i_0},\ldots, e^{n+1}_{i_n}$. Any such ordering induces the following vertex ordering $\partial o_n$ of $\Delta^{n-1}$: Letting $i_k = n$, we take $e^n_{i_0}, \ldots, e^n_{i_{k-1}},e^n_{i_{k+1}},\ldots e^n_{i_n}$. Moreover, one could define face embeddings $ (\Delta^{n-1},\partial o_n) \to (\Delta^n, o_n)$ which depend on $o_n$. This would produce a variant of the singular complex. I am not going to further explore this construction, but I am sure that the resulting homology groups agree with the usual singular homology groups.
In other words: You get a more complicated construction, but do not have a benefit.


TITLE: Electrostatics- Attraction between a negatively charged balloon and a plastic bottle
QUESTION [0 upvotes]: Let's say there is a negatively charged balloon. There is also a neutrally charged plastic bottle. You know that since the plastic bottle is an insulator, polarization occurs. Is it true that since the positive protons in the plastic bottle get closer so it gets attracted towards the balloon?

REPLY [1 votes]: No. Polarization of charges only occurs in conductors. to charge and insulator you need to rub to bodies .a.k.a charging by friction. it is true that atoms of plastics bottle will remain fix but there will a very little change of arrangement of nucleus and electrons. this rearrangement will happen when the atoms of plastic bottle are remain fixed


TITLE: Is the Avogadro's constant equal to one?
QUESTION [17 upvotes]: Question: Is the Avogadro's constant equal to one?
I was tasked with creating a presentation on Avogadro's work, and this is the first time I actually got introduced to the mole and to Avogadro's constant. And, to be honest, it doesn't make any mathematical sense to me.
1 mole = 6.022 * 10^23
Avogadro's constant = 6.022 * 10^23 * mole^(-1)

What?
This hole field seems very redundant. There are four names for the same thing! Since when is a number considered to be a measurement unit anyway?!

REPLY [22 votes]: Yes, Avogadro's constant is a redundant artifact from the era in the history of chemistry in which people didn't know how many atoms there were in a macroscopic amount of a material and it is indeed legitimate to set Avogadro's constant equal to one and abandon the awkward obsolete unit "mole" along the way. This $N_A=1$ is equivalent to
$$ 1\,\,{\rm mole} = 6.023\times 10^{23} \text{molecules or atoms} $$
and the text "molecules or atoms" is usually omitted because they're formally dimensionless quantities and one doesn't earn much by considering "one molecule" to be a unit (because its number is integer and everyone may easily agree about the size of the unit). We may use the displayed formula above to replace "mole" (or its power) in any equation by the particular constant (or its power) in the same way as we may replace the word "dozen" by 12 everywhere (hat tip: Mark Eichenlaub). We can only do so today because we know how many atoms there are in macroscopic objects; people haven't had this knowledge from the beginning which made the usage of a special unit "mole" justified. But today, the particular magnitude of "one mole" is an obsolete artifact of social conventions that may be eliminated from science.
Setting $N_A=1$ is spiritually the same as the choice of natural units which have $c=1$ (helpful in relativity), $\hbar=1$ (helpful in any quantum theory), $G=1$ or $8\pi G=1$ (helpful in general relativity or quantum gravity), $k=1$ (helpful in discussions of thermodynamics and statistical physics: entropy may be converted to information and temperature may be converted to energy), $\mu_0=4\pi$ (vacuum permeability, a similar choice was done by Gauss in his CGSM units and with some powers of ten, it was inherited by the SI system as well: $4\pi$ is there because people didn't use the rationalized formulae yet) and others. See this article for the treatment of all these universal constants and the possible elimination of the independent units:

http://motls.blogspot.com/2012/04/lets-fix-value-of-plancks-constant.html

In every single case in this list, the right comment is that people used to use different units for quantities that were the same or convertible from a deeper physical viewpoint. (Heat and energy were another example that was unified before the 20th century began. Joule discovered the heat/energy equivalence which is why we usually don't use calories for heat anymore; we use joules both for heat and energy to celebrate him and the conversion factor that used to be a complicated number is one.) In particular, they were counting the number of molecules not in "units" but in "moles" where one mole turned out to be a very particular large number of molecules.
Setting the most universal constants to one requires one to use "coherent units" for previously independent physical quantities but it's worth doing so because the fundamental equations simplify: the universal constants may be dropped. It's still true that if you use a general unit such as "one mole" for the amount (which is useful e.g. because you often want the number of moles to be a reasonable number comparable to one, while the number of molecules is unreasonably large), you have to use a complicated numerical value of $N_A$.
One additional terminological comment: the quantity that can be set to one and whose units are inverse moles is called the Avogadro constant, while the term "Avogadro's number" is obsolete and contains the numerical value of the Avogadro constant in the SI units. The Avogadro constant can be set to one; Avogadro's number, being dimensionless and different from one, obviously can't. Also, the inverse of Avogadro's number is the atomic mass unit in grams, with the units of grams removed. It's important to realize that the actual quantities, the atomic mass unit (with a unit of mass) and the Avogadro constant are not inverse to each other at all, having totally different units (when it comes both to grams and moles). Moreover, the basic unit of mass in the SI system is really 1 kilogram, not 1 gram, although multiples and fractions are constructed as if 1 gram were the basic unit.

REPLY [3 votes]: Avogadro's number has some historical backgrund, and you can find that in Luboš Motl's answer.  I will explain here, why I think it is still useful today, even it is completely superfluous.
You want to calculate mass of the gas.
$$m = N m_1$$
Mass of gas is number of particles $N$ times mass of one particle $m_1$.  Nice, so what is the problem?  Problem is that first number is absurdly large and the second is absurdly small.  So you define some large number, Avogadro number and you do the following:
$$m = N m_1 = \frac{N}{N_A} (N_A m_1) = n M$$
Now you have product of two reasonable numbers, $n=\frac{N}{N_A}$ is number of moles and $M = N_A m_1$ is molar mass, that is mass of one mole of particles.  This funny unit mole is there just for accounting, so you won't forget that moles must in the end cancel out.
Actually Avogadro's number does not exist as a natural constant at all.  It is essentially
$$N_A = \frac{10^{-3} \text{kg}}{m_P}$$
where ${m_P}$ is mass of proton, which is real natural constant.  Such definition is very handy, because it insures that all those numbers in periodic table of elements that represent molar mass of atoms are nice round numbers (e.g. Carbon 12, Oxygen 16, meaning that the mass of one carbon atom is 12 proton masses and the mass of one oxygen atom is 16 proton masses).
And thanks all who down-voted me without a comment.  Which only proves you have no arguments!

REPLY [2 votes]: Yes it's a little odd to have a unit of 'amount'. At least in English, it might make more sense in other languages
The second line is really "Avogadro's constant = 6.022 * 10^23 * items/mole"


text:
\section{Hyperviscosity-based Stabilization}
\label{sec:robust_hyp}

As mentioned previously, the RBF-FD differentiation matrices corresponding to the discretized gradient operator (and occasionally even the Laplacian operator) can contain eigenvalues with positive real parts. Such eigenvalues can cause spurious growth in the numerical solutions of advection-diffusion equations. Our approach to ameliorating this issue is to add a small vanishing amount of artificial hyperviscosity to the model. This transforms Equation 1 to
\begin{align}
\frac{\partial c}{\partial t} &= -\vu \cdot \nabla c + \nu \Delta c + \gamma \Delta^k c,
\label{eq:adr_hyp}
\end{align}
where $\gamma \Delta^k c$ is the artificial hyperviscosity term. This approach has been used in conjunction with explicit time-stepping in convective PDEs~\cite{FlyerNS,FoL11,BarnettPHS,FlyerLehto2012}. Our goals in this section are twofold: first, to present expressions for $\gamma$ and $k$, and second, to discuss the spatial approximation of the hyperviscosity term in the context of the RBF-FD method. We proceed by first deriving expressions for $\gamma$ in the advection-dominated regime, in the diffusion-dominated regime, then for the case where the two processes co-exist.

\subsection{Selecting $\gamma$ in the advection-dominated regime ($\nu \to 0$)}
\label{sec:gamma_1}

As mentioned in Section \ref{sec:intro}, the literature on modern RBF-FD methods gives a prescription for $\gamma$. In~\cite{FlyerNS,BarnettPHS}, for instance, Flyer et al. set this parameter to $\gamma = (-1)^{1-k} 2^{-6} h^{2k-1}$, where $k$ is the power of the Laplacian. We will show with our analysis that this formula is a special case of a much more general formula.

Assume for now a simplified 1D version of \eqref{eq:ad} where $\nu = 0$. This reduces it to the advection equation
\begin{align}
\frac{\partial c}{\partial t} + u\frac{\partial c}{\partial x} = 0.
\end{align}
Assume that $c$ is a plane wave of the form $c(x,t) = \hat{c}(t) e^{i\hat{k}x}$, where $\hat{k}$ is the wave number. The above equation should simply translate the plane wave to the right at a speed $u$. Unfortunately, the problem lies in the approximation of $\frac{\partial}{\partial x}$. In general, an RBF-FD discretization will instead result in our solving the \emph{auxiliary} equation
\begin{align}
\frac{\partial c}{\partial t} + u \frac{\tilde{\partial c}}{\partial x} = 0,
\end{align}
where $\frac{\tilde{\partial c}}{\partial x}$ is an \emph{auxiliary} differential operator that introduces a new term $\ep \hat{k}^q$ into the right hand side of the above equation so that we have
\begin{align}
\frac{\partial c}{\partial t} + u i \hat{k} \hat{c}(t) e^{i\hat{k}x} = u \ep \hat{k}^q \hat{c}(t) e^{i\hat{k}x},
\end{align}
where $\ep \geq 0$ causes \emph{growth} in $c$, and $q \in \mathbb{R}$. In general, $\ep$ and $q$ are unknown \emph{a priori}, but are functions of the node set and basis functions used; see~\cite{Platte2006} for a discussion on the relationships between eigenvalues of differential operators, RBFs, and node sets. We assume in this work that an upper-bound for $\ep$ is the real part of the spurious eigenvalue with the largest real part. In the RBF-FD context, we wish to add some amount of artificial hyperviscosity to stabilize the auxiliary PDE, giving us
\begin{align}
\frac{\partial c}{\partial t} + u \frac{\tilde{\partial} c}{\partial x}=  \gamma \frac{\partial^{2k} c}{\partial x^{2k}},k \in \mathbb{N}.
\label{eq:a_hyp_1D_aux}
\end{align}
We will now derive expressions for $\gamma$ that \emph{cancel} out the spurious growth mode $\ep \hat{k}^q$.

\subsubsection{Time-stepping with explicit RK methods}
\label{sec:hyp_exp}

Our goal in this section is to derive a hyperviscosity formulation for explicit RK methods. We first examine the forward Euler discretization as this is instructive. Discretizing \eqref{eq:a_hyp_1D_aux} using the Forward Euler scheme, we obtain
\begin{align}
c^{n+1} - c^{n} + \Delta t u\frac{\tilde{\partial} c^n}{\partial x} = \Delta t\gamma \frac{\partial^{2k} c^n}{\partial x^{2k}},
\end{align}
where the superscripts indicate time levels. Now, akin to Von Neumann analysis, assume that $c^{n+1} = Gc^n$, where $G$ is some growth factor. For time stability, we require that $|G|\leq 1$. Substituting the plane wave definition of $c^n$, we obtain
\begin{align}
G \hat{c}(t_n) e^{i\hat{k}x} = \hat{c}(t_n) e^{i\hat{k}x} -\Delta t u \hat{c}(t_n)e^{i\hat{k}x} \lf(i\hat{k} -  \ep \hat{k}^q\rt) + \Delta t \gamma i^{2k} \hat{k}^{2k} \hat{c}(t_n)e^{i\hat{k}x}.
\end{align}
This simplifies to
\begin{align}
G&= \lf(1 - \Delta t u i\hat{k} \rt) + \lf(u\Delta t \ep \hat{k}^q + \Delta t \gamma i^{2k} \hat{k}^{2k} \rt).
\label{eq:paren}
\end{align}
Even in the absence of the spurious growth term $u\Delta t \ep \hat{k}^q $, we have $|G|> 1$ due to the first parenthetical term, implying that forward Euler is always unstable on the semi-discrete advection equation. This is because its stability region does not include the imaginary axis. This motivates the use of other Runge-Kutta (RK) methods that contain the imaginary axis. In general, $G(z)$ is a polynomial for all explicit RK methods. For example, for forward Euler, we have
\begin{align}
G(z) & = 1 + z,
\end{align}
while for the classical fourth-order RK method (RK4) we have
\begin{align}
G(z) & = 1 + z + \frac{1}{2} z^2 + \frac{1}{6}z^3 + \frac{1}{24}z^4,
\end{align}
where $z = -u \Delta t (i\hat{k} - \ep \hat{k}^q) + \Delta t \gamma i^{2k} \hat{k}^{2k}$. Requiring $|G(z)| \leq 1$ allows us to compute $\gamma$ for all RK methods.  We demonstrate the calculation of $\gamma$ for RK4. First, partition $z = -u \Delta t (i\hat{k} - \ep \hat{k}^q) + \Delta t \gamma i^{2k} \hat{k}^{2k}$ as $z = z_1 + z_2$, where
\begin{align}
z_1 = -u \Delta t i \hat{k}, \ z_2 = u \Delta t \ep \hat{k}^q + \Delta t \gamma i^{2k} \hat{k}^{2k}.
\end{align}
In this form, it is clear that $z_1$ arises naturally from the advection equation, while $z_2$ arises from both the spurious growth mode and the hyperviscosity term. Substituting $z = z_1 + z_2$ into the expression for $G(z)$ for RK4, we obtain
\begin{align}
G(z) = 1 + z_1 + z_2 + \frac{1}{2}\lf(z_1 + z_2\rt)^2 + \frac{1}{6}\lf(z_1 + z_2\rt)^3 + \frac{1}{24} \lf(z_1 + z_2\rt)^4.
\end{align}
Now, partition $G(z)$ as $G(z) = G_1 (z_1) + G_2(z_1,z_2)$, where
\begin{align}
G_1(z_1) &= 1 + z_1 + \frac{1}{2} z_1^2 + \frac{1}{6}z_1^3 + \frac{1}{24}z_1^4, \\
G_2(z_1,z_2) &= z_2\lf[\frac{{z_1}^3}{6} + \frac{{z_1}^2}{2} + z_1 + 1 + z_2\left(\frac{{z_1}^2}{4} + \frac{z_1}{2} + \frac{1}{2}\right) + z_2^2\left(\frac{z_1}{6} + \frac{1}{6}\right) + \frac{z_2^3}{24}\rt].
\end{align}
In the absence of growth and hyperviscosity terms, stability would require $|G_1(z)| \leq 1$. If $|G(z)|\leq 1$ and $|G_1(z_1)|\leq 1$, it follows that we require $G_2(z_1,z_2) \leq 0$. Since $G_2$ may not even be real, the easiest way to compute $\gamma$ in practice is to enforce $G_2(z_1,z_2) = 0$. In other words, we require that
\begin{align}
z_2\lf[\frac{{z_1}^3}{6} + \frac{{z_1}^2}{2} + z_1 + 1 + z_2\left(\frac{{z_1}^2}{4} + \frac{z_1}{2} + \frac{1}{2}\right) + z_2^2\left(\frac{z_1}{6} + \frac{1}{6}\right) + \frac{z_2^3}{24}\rt] &= 0. \label{eq:long_rk4}
\end{align}
To satisfy this, we set $z_2 = 0$, \emph{i.e.},
\begin{align}
u \Delta t \ep \hat{k}^q + \Delta t \gamma i^{2k} \hat{k}^{2k} = 0.
\label{eq:temp}
\end{align}
Solving \eqref{eq:temp} for $\gamma$, we get
\begin{align}
\gamma = (-1)^{1-k} \hat{k}^{q-2k}u\ep,
\end{align}
The same expression for $\gamma$ is obtained in the case of all explicit RK methods (not shown). The factor $\ep$, which is the spurious growth mode, can be estimated numerically. We also know that the maximum wavenumber $\hat{k}$ that can be resolved on a regular grid of cell width $h$ is $2h^{-1}$ (for any spatial dimension $d$). Substituting $2h^{-1}$ in place of $\hat{k}$ gives us
\begin{align}
\gamma = (-1)^{1-k}  2^{q-2k} h^{2k-q}u \ep.
\label{eq:gamma_exp}
\end{align}
Note that the above expression for $\gamma$ has an explicit dependence on the velocity $u$, the largest real part $\ep$, and the growth exponent $q$. Further, the formula contains a factor of $2^{q-2k}$, much like the $2^{-6}$ factor that appears in~\cite{FlyerNS,BarnettPHS}. We defer a discussion on $q$ to a later section.

\subsubsection{Time-stepping with explicit multistep methods}

We next calculate $\gamma$ for the case of explicit multistep methods. To illustrate the procedure, consider the Adams-Bashforth formula of order 2 (AB2)~\cite{Ascher97} applied to the generic ODE
\begin{align}
\frac{\partial c}{\partial t} = \mu c.
\end{align}
The AB2 discretization of this ODE is
\begin{align}
c^{n+1} = c^n + \frac{3}{2}\Delta t \mu c^n - \frac{1}{2}\Delta t \mu c^{n-1}.
\end{align}
Now, let $c^{n-1} = \hat{c}\lf(t_{n-1}\rt) e^{i\hat{k}x}$ so that $c^n = G c^{n-1}$ and $c^{n+1} = G^2 c^{n-1}$,where $G$ is the growth factor as before.  Substituting these equations into the AB2 scheme, we obtain the following quadratic equation for the growth factor $G$:
\begin{align}
G^2 - G\lf(1 + \frac{3}{2}\Delta t \mu\rt) + \frac{1}{2} \Delta t \mu = 0.
\label{eq:gf_ab2_1}
\end{align}
If AB2 is applied to \eqref{eq:a_hyp_1D_aux}, it follows from \eqref{eq:gf_ab2_1} that
\begin{align}
G^2 - G\lf(1 + \frac{3}{2}z_1 + \frac{3}{2} z_2\rt) + \frac{1}{2}z1 + \frac{1}{2} z_2 = 0,
\end{align}
where $z_1 = -u\Delta t i \hat{k}$ and $z_2 = u \Delta t \ep \hat{k}^q + \Delta t \gamma i^{2k} \hat{k}^{2k}$. This equation can be rewritten as
\begin{align}
\underbrace{G^2 - G\lf(1 + \frac{3}{2}z_1\rt) + \frac{1}{2}z_1}_{t_1} + \underbrace{z_2\lf(\frac{1}{2} - \frac{3}{2}G \rt)}_{t_2} = 0.
\end{align}
The term $t_1$ is free of spurious growth (and hyperviscosity), and is the term obtained by applying the AB2 method to the advection equation. If $t_2=0$ and a stability criterion on the term $u \Delta t \hat{k}$ is met, we have $|G|\leq 1$. A straightforward way to obtain an expression for $\gamma$ is therefore to require $t_2$ to vanish entirely. More specifically, we require
\begin{align}
z_2\lf(\frac{1}{2} - \frac{3}{2}G\rt) = 0.
\end{align}
Since $G$ may take on a wide range of values despite the constraint $|G|\leq 1$, the only way to guarantee the above equality is to require $z_2 = 0$. This gives us
\begin{align}
u\Delta t \ep \hat{k}^q + \Delta t \gamma i^{2k} \hat{k}^{2k} = 0,
\end{align}
which yields
\begin{align}
\gamma &= (-1)^{1-k} 2^{q-2k} h^{2k-q} u \ep,
\end{align}
which is identical to the formula for $\gamma$ in the RK4 case. This analysis is easily done for all explicit multistep methods, and even for the explicit parts of IMEX multistep methods. For an example of the latter, consider the explicit/extrapolated BDF4 method (the explicit part of the IMEX-BDF4/SBDF4 method~\cite{Ascher97}) applied to the same ODE:
\begin{align}
\frac{\frac{25}{12}c^{n+1} - 4c^n + 3c^{n-1} - \frac{4}{3}c^{n-2} + \frac{1}{4}c^{n-3}}{\Delta t} = \mu\lf(4 c^n - 6c^{n-1} + 4c^{n-2} - c^{n-3}\rt).
\end{align}
The corresponding equation for $G(z)$ is now quartic:
\begin{align}
G^4 - \frac{48}{25}G^3(1 + z) + \frac{36}{25} G^2 (1 + 2z) - \frac{16}{25}G(1 + 3z) + \frac{3}{25}(1 + 4z) = 0.
\end{align}
Writing $z = z_1 + z_2$ as before and splitting the equation into two terms $t_1(z_1)$ and $t_2(z_2,G)$ yields
\begin{align}
t_1 &= G^4 - \frac{48}{25}G^3(1 + z_1) + \frac{36}{25} G^2 (1 + 2z_1) - \frac{16}{25}G(1 + 3z_1) + \frac{3}{25}(1 + 4z_1), \\
t_2 &= z_2\lf(-\frac{48}{25}G^3 + \frac{72}{25}G^2 - \frac{48}{25}G + \frac{12}{25} \rt), \\
t_1 &+ t_2 = 0.
\end{align}
To have $t_2 = 0$ for stability, we again require $z_2 = 0$. This yields the same expression for $\gamma$ as in the AB2 and RK4 cases. As an aside, note that it is possible to obtain either $G_2 = 0$ in the RK case or $t_2 = 0$ in the multistep case if the term $z_1$ or the growth factor $G$ satisfies certain constraints (in addition to the CFL constraint). However, these cases are very rare and obtained only when $\Delta t$, $h$, and $\ep$ take on specific values.

\subsection{Selecting $\gamma$ in the diffusion-dominated regimed ($u \to 0$)}
\label{sec:gamma_2}

Another important limit is the diffusive regime where $\nu$ dominates over $u$. Current RBF-FD methods are not guaranteed to produce purely negative real eigenvalues when approximating the Laplacian $\Delta$. While a mild spread along the imaginary axis is acceptable for parabolic problems, eigenvalues with positive real parts are undesirable as they would cause spurious solution growth. To calculate the amount of hyperviscosity-based stabilization required to counter this growth, we use the same approach as in Section \ref{sec:gamma_1}, and define the auxiliary 1D PDE
\begin{align}
\frac{\partial c}{\partial t} = \nu \frac{\tilde{\partial}^2 c}{\partial x^2} + \gamma \frac{\partial^{2k}c}{\partial x^{2k}}, k \in \mathbb{N},
\label{eq:diff_hyp}
\end{align}
where the operator $\frac{\tilde{\partial}^2} {\partial x^2}$ acting on a plane wave produces the correct decay mode as well as a spurious growth mode, so that if $c(x,t) = \hat{c}(t) e^{i\hat{k}x}$, $\frac{\tilde{\partial}^2 c}{\partial x^2} = \lf(-\hat{k}^2 + \eta \hat{k}^q\rt) \hat{c}(t) e^{i\hat{k}x}$, where $\eta \geq 0$ is responsible for the spurious growth. We now discretize \eqref{eq:diff_hyp} in time using the second-order backward difference formula (BDF2) (which is A-stable)~\cite{Ascher97}, obtaining
\begin{align}
\frac{3c^{n+1} - 4c^n + c^{n-1}}{2\Delta t} = \nu \frac{\tilde{\partial}^2 c^{n+1}} {\partial x^2} + \gamma \frac{\partial^{2k}}{\partial x^{2k}} c^{n+1},
\end{align}
for which the growth factor $G$ satisfies
\begin{align}
\lf(1 - \frac{2}{3}\Delta t \mu\rt)G^2 -\frac{4}{3}G + \frac{1}{3} = 0,
\label{eq:visc_hyp_1}
\end{align}
where $\mu = \nu\lf(-\hat{k}^2 + \eta \hat{k}^q\rt) + \gamma i^{2k} \hat{k}^{2k}$. Collecting all diffusion terms into term $t_1$, and spurious growth and hyperviscosity terms in term $t_2$gives:
\begin{align}
&t_1 = \lf(1 + \frac{2}{3}\Delta t \hat{k}^2\rt)G^2 - \frac{4}{3}G + \frac{1}{3}, \ t_2 = -\frac{2}{3}\Delta t \lf(\nu\eta \hat{k}^q + \gamma i^{2k} \hat{k}^{2k}\rt), \\
&t_1 + t_2 =0.
\end{align}
For stability, we require that $t_2 = 0$. This gives:
\begin{align}
\nu\eta \hat{k}^q &+ \gamma i^{2k} \hat{k}^{2k} = 0, \\
\implies \gamma &= (-1)^{1-k} 2^{q-2k} h^{2k-q} \nu \eta.
\label{eq:gamma_visc_1}
\end{align}
If we had lumped the diffusion term into term $t_2$, we would have obtained an expression for $\gamma$ that accounts for the stabilization afforded by natural diffusion. We do not take this approach in this article.

\subsection{Selecting $\gamma$ for coexisting advection and diffusion ($u\neq 0$, $\nu \neq 0$)}
\label{sec:gamma_3}

Having examined both the advective and diffusive limits for reasonable choices of time integrators, we now consider the important case where both advection and diffusion may contribute significantly to the transport process. In this scenario, it is common to treat the diffusion term implicitly in time, and the advection term explicitly. Consequently, it is reasonable (in terms of computational efficiency) to also treat the hyperviscosity term implicitly in time. The relevant auxiliary PDE with hyperviscosity is now
\begin{align}
\frac{\partial c}{\partial t} + u \frac{\tilde{\partial} c}{\partial x}=  \nu \frac{\tilde{\partial}^2 c}{\partial x^2} + \gamma \frac{\partial^{2k}}{\partial x^{2k}}.
\label{eq:ad_1d}
\end{align}
For plane waves, this yields the ODE
\begin{align}
\frac{\partial c}{\partial t} = \mu_1 c + \mu_2 c,
\label{eq:ode2}
\end{align}
where
\begin{align}
\mu_1 = -u i\hat{k} + u\ep\hat{k}^{q_1}, \ \mu_2 = \nu\lf(-\hat{k}^2 + \eta \hat{k}^{q_2}\rt) + \gamma i^{2k} \hat{k}^{2k},
\end{align}
where $q_1$ and $q_2$ are the growth exponents for the approximate gradient and laplacian respectively. To keep our analysis simple, we discretize \eqref{eq:ode2} using the IMEX-BDF2 or SBDF2 method~\cite{Ascher97}; however, our technique carries over to higher order SBDF methods. The SBDF2 discretization is given by
\begin{align}
\frac{3c^{n+1} - 4c^n + c^{n-1}}{2\Delta t} = 2\mu_1 c^n - \mu_1 c^{n-1} + \mu_2 c^{n+1}.
\end{align}
Substituting in a plane wave expression yields the following equation for the growth factor $G$:
\begin{align}
\lf(1 - \frac{2}{3}\mu_2 \Delta t\rt) G^2 - \frac{4}{3}G\lf(1 + \Delta t \mu_1\rt) + \frac{1}{3}\lf(1 + 2 \Delta t \mu_1\rt) = 0.
\end{align}
Collecting advection and diffusion terms into the term $t_1$, and spurious growth and hyperviscosity terms into the term $t_2$, we obtain
\begin{align}
t_1 &= \lf(1 + \frac{2}{3}\nu\hat{k}^2 \Delta t\rt) G^2 - \frac{4}{3}G\lf(1 - \Delta t u i \hat{k} \rt) + \frac{1}{3}\lf(1 - 2 \Delta t u i \hat{k}\rt), \\
t_2 &= -\frac{2}{3}\Delta t G^2 \lf(\nu\eta\hat{k}^{q_2} + \gamma i^{2k} \hat{k}^{2k}\rt) + \frac{2}{3}\Delta t u \ep \hat{k}^{q_1} \lf(1 - 2G\rt), \\
t_1 &+ t_2 = 0.
\end{align}
As before, we require that $t_2 = 0$, \emph{i.e.},
\begin{align}
-G^2 \lf(\nu\eta\hat{k}^{q_2} + \gamma i^{2k} \hat{k}^{2k}\rt) + u \ep \hat{k}^{q_1} \lf(1 - 2G\rt) = 0.
\end{align}
Now, let $\gamma = \gamma_1 + \gamma_2$. Then, we have
\begin{align}
-G^2 \lf(\nu\eta\hat{k}^{q_2} + \gamma_1 i^{2k} \hat{k}^{2k} + \gamma_2 i^{2k} \hat{k}^{2k}\rt) + u \ep \hat{k}^{q_1} \lf(1 - 2G\rt) = 0.
\end{align}
We can select $\gamma_2$ to cancel out the growth term $\eta \hat{k}^{q_2}$, giving us
\begin{align}
\gamma_2 = (-1)^{1-k} 2^{q_2 - 2k} h^{2k - q_2} \eta \nu,
\end{align}
and leaving us with
\begin{align}
-G^2 \gamma_1 i^{2k} \hat{k}^{2k} + u \ep \hat{k}^{q_1} \lf(1 - 2G\rt) = 0.
\end{align}
Dividing the above equation by the non-zero quantity $-\gamma_1 i^{2k} \hat{k}^{2k}$, we get the quadratic equation
\begin{align}
G^2  + \frac{u \ep \hat{k}^{q_1}}{\gamma_1 i^{2k} \hat{k}^{2k}} \lf(2G-1\rt) = 0.
\end{align}
The roots of this equation are given by
\begin{align}
G = -\frac{u \ep \hat{k}^{q_1}}{\gamma_1 i^{2k} \hat{k}^{2k}} \pm \frac{1}{\gamma_1 i^{2k} \hat{k}^{2k}}\sqrt{\lf(u \ep \hat{k}^{q_1}\rt)\lf(u \ep \hat{k}^{q_1} + \gamma_1 i^{2k} \hat{k}^{2k}\rt)}.
\end{align}
Stability requires that $|G|\leq 1$. This can be achieved if
\begin{align}
u \ep \hat{k}^{q_1} + \gamma_1 i^{2k} \hat{k}^{2k} = 0,
\end{align}
which gives
\begin{align}
\gamma_1 = (-1)^{1-k} 2^{q_1 - 2k} h^{2k - q_1} u \ep.
\end{align}
Finally, since $\gamma = \gamma_1 + \gamma_2$, we have
\begin{align}
\gamma &= (-1)^{1-k} 2^{q_1 - 2k} h^{2k - q_1} u \ep + (-1)^{1-k} 2^{q_2 - 2k} h^{2k - q_2} \eta \nu.
\end{align}
From the analysis, it is clear that the hyperviscosity for spurious growth in advection and diffusion is \emph{additive} under the assumptions of our model. This expression naturally encodes the other cases seen so far. For instance, in the limit $\nu \to 0$, we recover \eqref{eq:gamma_exp}, while in the limit $u \to 0$, we recover \eqref{eq:gamma_visc_1}. The expressions for $\gamma$, though derived using a 1D model, generalize straightforwardly to higher dimensions by replacing $u$ with $\|\vu\|_{\infty}$ (the maximum pointwise spatial velocity or an estimate thereof).

In this article, our simulation results are expressed in terms of the \emph{Peclet number}, which is given $\rm{Pe} = \frac{uL^*}{\nu}$, where $L^*$ is some characteristic length scale. To get a higher Peclet number, one can either fix $\nu$ and make $u$ larger, or fix $u$ and make $\nu$ smaller. The former case is interesting as it magnifies the effect of the spurious eigenvalue $\ep$, while the latter serves to reduce any stabilizing diffusion. In Section \ref{sec:results}, we focus on the case of increasing $u$ for fixed $\nu$, as this is a more effective test of our hyperviscosity formulation. However, we have observed that our hyperviscosity formulation is extremely robust and stable in the scenario of decreasing $\nu$ as well; this can be seen in Section \ref{sec:application}. In both these sections, we demonstrate that it is perfectly safe to use \eqref{eq:gamma_exp} for $\gamma$ in the context of IMEX multistep methods.

\subsection{Estimating growth exponents ($q_1$ and $q_2$)}
\label{sec:models}

Thus far, our growth models have only included a \emph{generic} spurious growth term of the form $\ep \hat{k}^q_1$ or $\eta \hat{k}^q_2$. To the best of our knowledge, the literature lacks any theoretical estimates for $q_1$ or $q_2$ on any given node set. Our goal in this section is to give a simple and cost-effective \emph{numerical} procedure for computing these values on a given node set. Without loss of generality, we proceed with a description of this procedure on a 1D node set. Let $X = \{ x_j\}_{j=1}^N$ be a set of nodes on which we obtain the discrete RBF-FD differentiation matrix $G^x$ that approximates $\frac{\partial}{\partial x}$ in the advection term. Our goal now is to estimate $q_1$ for the matrix $G^x$; the procedure for $q_2$ is identical. Consider the function $f(x) = e^{i\hat{k}x}$. Its derivative is given exactly by $g(x) = i \hat{k} e^{i\hat{k}x}$. Then, define
\begin{align}
\uf = \lf.f(x)\rt|_{X},\ \ \ug = \lf.g(x)\rt|_{X} = i\hat{k}\uf,
\end{align}
where $\uf,\ug$ are vectors with $N$ entries. On the other hand, the \emph{approximate} derivative of $f(x)$ on the node set $X$ is given by
\begin{align}
\tilde{\ug} = G^x \uf.
\end{align}
According to our growth model, we know that $G^x$ is represented by the auxiliary differential operator $\frac{\tilde{\partial}}{\partial x}$. Consequently, ignoring truncation errors in $G^x$, the growth model gives
\begin{align}
\tilde{\ug} = \lf(i\hat{k} - \ep \hat{k}^{q_1}\rt) \uf.
\end{align}
This allows us to write
\begin{align}
\| \ug - \tilde{\ug}\| &= \ep \hat{k}^{q_1} \|\uf\|.
\end{align}
In the scenario with spurious growth modes, we know that $\ep \|\uf\| \neq 0$. Dividing by $\ep \|\uf\|$ and reversing the sides of the equation for clarity, we get
\begin{align}
\hat{k}^{q_1}  &= \frac{\| \ug - \tilde{\ug}\|}{\ep \|\uf\|}, \\
\implies q_1 &=\frac{\ln\lf(\| \ug- \tilde{\ug}\|\rt) - \ln\lf(\ep \|\uf\|\rt)}{\ln\hat{k}}.
\end{align}
As we remarked when deriving $\gamma$, the largest wavenumber $\hat{k}$ that can be represented on a grid of cell width $h$ is $2h^{-1}$. Thus, in the above formula for $q_1$, we use $\hat{k} = 2h^{-1}$, where $h$ is taken to be $h = N^{-1/d}$. To fully extend the above definition of $q_1$ to dimension $d>1$, we need only change the definition of $f(x)$ to be a product of exponentials in each spatial variable. The above procedure is repeated for each of the gradient differentiation matrices $G^x$,$G^y$, and $G^z$, and the largest $q_1$ value of the three is used. While any function $f(x)$ could have been chosen in principle, the use of plane waves allows a direct comparison to our growth model and an easy evaluation on any node set. In addition, to compute $q_2$, we use $g(x) = -\hat{k}^2 e^{i\hat{k}x}$ as our reference derivative function and $\tilde{\ug} =  \lf(-\hat{k}^2 + \eta\hat{k}^{q_2}\rt) \uf$, but the above formula remains the same (with $\eta$ in place of $\ep$). In practice though, since $\eta \approx 0$ and we use implicit time-stepping, it is typically unnecessary to compute $q_2$.

To complete the above discussion, we note that $\ep$ and $\eta$ must be estimated to find $q_1$ and $q_2$. These factors correspond naturally to the real part of the eigenvalue with the largest real part. If a loose tolerance is used in the eigenvalue computation (as is done in this article), the estimates for $q_1$ and $q_2$ are likely to be an approximation as well. Note also that our definition allows $q_1$ and $q_2$ to be negative, though in practice we have observed that $q_1$ and $q_2$ are typically between $0$ and $1$. The approach detailed in this section \emph{eliminates} all free parameters from the expression for $\gamma$ for the cost of $d$ sparse matrix-vector multiplications for estimating $q$, and a few sparse matrix-vector multiplications for estimating $\ep$. In contrast, expressions for $\gamma$ in the literature contain factors that must be tuned to achieve stability~\cite{FlyerNS,FlyerLehto2012}. If theoretical developments should ever give \emph{a priori} estimates for $\ep$ and $\eta$, these can be substituted directly into the formula for $\gamma$.

\subsection{Spurious modes in the hyperviscosity operator}
\label{sec:hyp_growth}

Our analysis, for convenience, has neglected the fact that an RBF-FD approximation to the operator $\Delta^k$ may itself contain spurious eigenvalues that cause undesirable growth or decay (so that they always produce spurious growth when we consider $\gamma \Delta^k$ since $\textit{sign}(\gamma) = (-1)^{1-k}$). It is reasonable to wonder how the expression for $\gamma$ would change if one factored in this additional spurious mode. Fortunately, our analysis technique from the previous sections is perfectly amenable to this case as well. Let $\frac{\tilde{\partial}^{2k}}{\partial x^{2k}}$ be the \emph{auxiliary} hyperviscosity operator, defined by its action on plane waves:
\begin{align}
\frac{\tilde{\partial}^{2k} e^{i\hat{k}x}}{\partial x^{2k}} = \lf( i^{2k} \hat{k}^{2k} \pm \tau \hat{k}^{q_3}\rt) e^{i\hat{k}x},
\end{align}
where $\tau\geq 0$, but the spurious term has the opposite sign of the eigenvalues of the operator $\frac{\partial^{2k}}{\partial x^{2k}}$. Without loss of generality, we rederive $\gamma$ for explicit RK4 for this new scenario. Using our previous notation of $G(z)$ to represent the growth factor, splitting $z = z_1 + z_2$, where $z_1$ contains the advection term, and $z_2$ contains \emph{all} spurious growth terms, we again require $z_2 = 0$ to obtain stability. This yields the condition
\begin{align}
u\Delta t \ep \hat{k}^{q_1} + \Delta t \gamma \lf(i^{2k} \hat{k}^{2k} \pm \tau \hat{k}^{q_3}\rt) = 0,
\end{align}
where the symbols have their usual meanings. Re-arranging, we get
\begin{align}
\gamma &= -\frac{u \ep \hat{k}^{q_1}}{i^{2k} \hat{k}^{2k} \pm \tau \hat{k}^{q_3}},\\
\implies \gamma &= \frac{(-1)^{1-k} u \ep 2^{q_1-2k} h^{2k - q_1}}{1 \pm (-1)^k \tau 2^{q_3 - 2k} h^{2k-q_3}},
\end{align}
for $\hat{k} = 2h^{-1}$. Since the $\tau$ term is scaled by the typically very small value of $2^{q_3 - 2k}h^{2k-q_3}$, we find for the experiments in this article that it is safe to neglect the effect of any spurious modes in the RBF-FD approximation to the $\Delta^k$ operator when computing $\gamma$.

\subsection{Selecting $k$}
\label{sec:k}

We next turn to the selection $k$, the power of the Laplacian in the term $\gamma \Delta^k$. It has already been observed in the RBF-FD literature that $k$ must be increased as the stencil size $n$ is increased~\cite{FlyerLehto2012}. However, the formula presented in~\cite{FlyerLehto2012} was heuristic and was fine-tuned to the node sets on the sphere. In more modern RBF-FD formulas on Euclidean domains~\cite{FlyerNS}, this approach appears to have been tested and discarded as unnecessary. However, in our experiments, we found that it was indeed necessary to scale $k$ with $n$ on scattered nodes in domains with irregular boundaries.

We adopt an approach based on the spectral methods literature. Specifically, examining Ma's work on the Chebyshev-Legendre super viscosity method~\cite{MaSSV1,MaSSV2}, we see in Remark 2 below (5.21) that the order $k$ ($s$ in their notation) of the spectral superviscosity must scale as
\begin{align}
k \leq O(\ln N),
\end{align}
where $N$ is the total number of points. Our recipe for $k$ uses a modified version of this scaling law. Bearing in mind that an FD method reproduces a spectral method as the stencil size $n \to N$, this prompts us to select
\begin{align}
k = \lf\lfloor 1.5 \ln n\rt\rfloor.
\label{eq:k}
\end{align}
This formula has the effect of increasing $k$ with $n$ (as desired). The actual constant in front of the $\ln n$ term does not appear to have a great impact on accuracy. \revone{While the logarithmic scaling may arise naturally as a consequence of the non-uniform resolution of Chebyshev-Legendre spectral methods, it has benefits when used with RBF-FD approximations also. First, the law \eqref{eq:k} is easy to compute and requires no fine tuning. Second, it serves to increase $k$ slowly with $n$. This slow increase ensures that the stencil sizes and polynomial degrees needed for approximating $\Delta^k$ also grow only slowly with $n$. Together, the formulas for $\gamma$ and $k$ give us a hyperviscosity operator that produces the correct damping behavior in the $n \to N$ limit, \emph{and} vanishes in the $h \to 0$ limit, all without any free parameters.}

\subsection{RBF approximations to the hyperviscosity operator}
\label{sec:rbf_hyp}

As in the case of the other terms in \eqref{eq:adr_hyp}, we approximate the hyperviscosity term with PHS RBFs augmented with polynomials. First, the PHS RBF used for hyperviscosity must have sufficient smoothness so as to be able to apply the operator $\Delta^k$ to it. We use the PHS RBF
\begin{align}
\phi_{hyp}(r) = r^{2k+1},
\end{align}
which is the PHS RBF of minimal smoothness required. It follows that, $\Delta^k \phi_{hyp}(r) = C r$, where $C$ is a known constant involving $k$ and the spatial dimension $d$. This follows from repeated application of the formula for the Laplacian of a radial function in $d$-dimensions: $\Delta r^m = m(m - d + 2)r^{m-2}$.

In addition to selecting the PHS RBF, we must also select the polynomial degree $\ell_{hyp}$ for approximating the hyperviscosity operator. Our approach here is very simple. For a PHS RBF of degree $2k+1$, the minimal polynomial degree required to prove unisolvency of the RBF interpolant is $k$~\cite{Fasshauer:2007}. We thus pick $\ell_{hyp} = k$. The observant reader may be concerned: after all, for even a first-order approximation of the operator $\Delta^k$, it would seem that $\ell_{hyp} = 2k$ is the correct choice. However, this ignores the fact that the operator in question is $\gamma \Delta^k$. Since $\gamma = O\lf(h^{2k-q}\rt)$ where we typically have $q = O(1)$, the scaling with $\gamma$ makes our approximation to this operator very high-order. When computing overlapped RBF-FD weights for the operator $\Delta^k$, the choice of $\ell_{hyp} = k$ also zeros out the derivatives of polynomial terms upto degree $\ell$, which in our case is \emph{all} terms.

The different parameters and basis function choices for our RBF-FD methods are summarized in Table \ref{tab:params}.
\begin{table}[h!]
\centering
\begin{tabular}{ccc} \toprule
		Parameter & Meaning & Value \\ \midrule
		$\ell$ & Polynomial degree for non-hyperviscosity terms & $\xi + \theta - 1$ \\
		$m$ & PHS degree & $\ell$ if $\ell$ is odd, $\ell - 1$ if $\ell$ is even \\
		$M$ & Number of polynomial terms & ${\ell + d \choose d}$ \\
		$n$ & Stencil size & $2M + \lf \lfloor \ln(2M)\rt\rfloor$\\
		$\delta$ & Overlap parameter &  0.7 if $\ell \leq 3$, 0.5 if $4 \leq \ell < 6$, 0.3 if $\ell \geq 6$\\
		$k$ & Order of hyperviscosity & $\lf\lfloor 1.5 \ln n\rt\rfloor$ \\
		$\gamma$ & Magnitude of hyperviscosity & $(-1)^{1-k} 2^{q_1-2k} h^{2k-q_1} \|\vu\|_{\infty} \ep + (-1)^{1-k} 2^{q_2-2k} h^{2k-q_2} \nu \eta$ \\
		$\phi_{hyp}(r)$ & PHS RBF for hyperviscosity & $r^{2k+1}$ \\
		$\ell_{hyp}(r)$ & Polynomial degree for hyperviscosity & $k$\\
		$n_{hyp}$ & Stencil size for hyperviscosity & $2 {\ell_{hyp} + d \choose d} + 1$\\ \bottomrule
\end{tabular}
\caption{Table of parameters based on desired approximation order $\xi$, differential operator order $\theta$, node spacing $h$, velocity $\vu$, diffusion coefficient $\nu$, and dimension $d$.}
\label{tab:params}
\end{table}

config: arxiv


TITLE: There are 6 same apples and 8 same oranges. How many non-empty subset can be formed from those two kinds of fruits?
QUESTION [1 upvotes]: I thought it is $2^{14} - 1$ but I am not so sure. I think it is not a kind of multiplication principle, that is, $6 \cdot 8 = 48$, because in the context, the 6 apples are the same as well as the oranges.
Please help.

REPLY [3 votes]: Each of your subsets $U_{a,o}$ is completely determined with number of apples $a$ and number
of oranges $o$ (it's not important which apples/oranges are in the set, because they are the same). Set $U_{a,o}$ is not empty iff $\max \{a,o\}>0$. You can choose $0\leq a \leq 6$ apples
and $0\leq o \leq 8$ oranges. The set $U_{0,0}$ is empty, so the answer is
$$(6+1)\cdot (8+1) -1 = 62\text{.}$$


text:
\section{Proof of Main Theorem}
In this section, we give the proof of Theorem \ref{thm:algcycles}. The key idea is to give, for each unramified $[b]\in B(G,\upsilon)$, a factor $H_{[b]}(x)$ of the Hecke polynomial which kills the irreducible components of $p-\Isog\otimes\kappa$ which are $[b]$-dense.
\subsection{Constructing $H_{[b]}$}
\label{section:constructionHb}
Our first observation is that the factors of $H_{G,X}$ are closely related to unramified elements in $B(G,\upsilon)$. In particular, we observe that the unramified elements $p^\tau$ are exactly the elements which are $\sigma$-conjugate to $p^\lambda$ for some $\lambda\in \Omega(\overline{\bbQ}_p)\upsilon$.

Hence, for an unramified $\sigma$-conjugacy class $[b]$=$[p^\tau]$ which we fix for the rest of the section, consider the set
\begin{equation*}
    \mathbb{MV}(\tau)=\{\lambda\in \Omega(\overline{\bbQ}_p)\upsilon:\lambda\in\tau+(\sigma-1)X_*(T)\}.
\end{equation*}
We let $m$ be the smallest positive integer such that $\sigma^{nm}$ fixes every element in this set. Choose $\lambda$ in $\mathbb{MV}(\tau)$ such that $\sigma^{ni}(\lambda)\neq \lambda$ for any $i<m$.

Moreover, since $\tau$ is $\sigma$-conjugate to $\lambda$, it is also $\sigma$-conjugate to $\beta:=\sigma^{-1}(\lambda)$ which is a Weyl conjugate of $\mu^{-1}$. We also observe that $\sigma^{ni}(\beta)\neq \beta$ for any $i<m$.

Let $Z$ be the galois orbit of $\Omega(\overline{\bbQ}_p)\mu^{-1}$ containing $\beta$. We assume that $\bar{\beta}$ is dominant, otherwise we replace $\beta$ with conjugate in $\Omega(\bbQ_p)$, which has the same properties. Then applying Proposition \ref{prop:factorHecke}, we see that $H_{G,X}(x)$ has a factor of the form
\begin{equation}
\label{eqn:heckepoly1}
    H'_{[b]}(x):=x^m-p^{nm\langle\rho,\mu-\beta\rangle }\tilde{\beta},
\end{equation}
where $\tilde{\beta}=\sum_{i=1}^{nm}\sigma(\beta)$. However, we only know that this factorization holds over the larger Hecke algebra $\calH(M_{\tilde{\beta}}(\bbQ_p)//M_{\tilde{\beta},c})$, and so \emph{a priori}, we do not have a factorization in $\bbQ[p-\Isog\otimes\kappa]$. However, we can consider the product of all the Weyl conjugates of $H'_{[b]}(x)$, which we will denote by $H_{[b]}(x)$. $H_{[b]}(x)$ is defined in $\calH(G)(x)$. For notational simplicity, we let $M:=M_{\tilde{\beta}}$ be the standard Levi subgroup centralizing the cocharacter $\tilde{\beta}$. $M$ also centralizes the Newton cocharacter $\nu([b])$.

\begin{proposition}
\label{prop:Hbkillsfactors}
  Let $C$ be a geometric irreducible component of $p-\Isog\otimes\kappa$ which is $[b]$-dense. Then we have
  \begin{equation*}
    H_{[b]}(\Frob)\cdot C=0.
  \end{equation*}
\end{proposition}
\begin{proof}
Since $\dot{\calS}^G_M(H_{[b]})$ factorizes in $\calH(M)(x)$, and has a factor $H'_{[b]}$, from the compatibility with $\dot{\calS}^G_M$ in Theorem \ref{thm:parabolicred}, we see that $H_{[b]}(\Frob)\cdot C$ has a factor $H'_{[b]}(\Frob)\cdot C$, and we know that $H_{[b]}'(\Frob)\cdot C=0$, also from theorem \ref{thm:parabolicred}.
\end{proof}
\subsection{Key vanishing result}
Using the previous results, we can now show the following theorem.
\begin{theorem}
\label{thm:keyvanishing}
 For any unramified $[b]\in B(G,\upsilon)$, let $H_{G,X}^{\succeq [b]}(x)$ be the polynomial with coefficients in $\mathbb{Q}[p-\Isog\otimes\kappa]$ given as the image of $H_{G,X}(x)$ under $\mathrm{res}^{\succeq [b]}\circ h$. Then
 \begin{equation*}
     H_{G,X}^{\succeq [b]}(\Frob)=0,
 \end{equation*}
 where $\Frob$ is the Frobenius section of $p-\Isog\otimes\kappa$.
\end{theorem}
\begin{proof}
  We show this by induction on $[b]$, under the reverse of the partial order in $B(G,\upsilon)$. We already know this holds on the $\mu$-ordinary locus, so suppose that for all $[b']\succ[b]$, the analogous result is true. Note that by an inclusion-exclusion principle sum, this implies that $H^{\succ[b]}_{G,X}(\Frob)=0$, where $H^{\succ[b]}_{G,X}(\Frob)$ is the sum of all $[b']$-dense terms, where $[b']\succ[b]$.

 We know that $H^{\succeq [b]}_{G,X}(\Frob)$ admits a factorisation
  \begin{equation*}
      H^{\succeq [b]}_{G,X}(\Frob)=H_{[b]}(\Frob)P(\Frob)
  \end{equation*}
  for some $P(\Frob)$, all of whose irreducible components are $[b']$-dense for $[b']\succeq [b]$. Moreover, $H_{[b]}(\Frob)$ is $\mu$-ordinary dense. Consider the difference
  \begin{equation*}
      H^{\succeq [b]}_{G,X}(\Frob)-H^{\succ[b]}_{G,X}(\Frob)=H_{[b]}(\Frob)P(\Frob)-H_{[b]}(\Frob)P'(\Frob)
  \end{equation*}
where $P'(\Frob)$ is the restriction to the $[b']$-dense irreducible components of $P(\Frob)$, for $[b']\succ [b]$. Then $P(\Frob)-P'(\Frob)\in \mathbb{Q}[p-\Isog\otimes\kappa]$ must be $[b]$-dense, by definition. Hence, we have
  \begin{equation*}
      H^{\succeq [b]}_{G,X}(\Frob)-H^{\succ[b]}_{G,X}(\Frob)=H_{[b]}(\Frob)\cdot C,
  \end{equation*}
  for some $[b]$-dense $C$. Applying Proposition \ref{prop:Hbkillsfactors} above, we can conclude that $H^{\succeq [b]}_{G,X}(\Frob)-H^{\succ[b]}_{G,X}(\Frob)=0$, and hence
  \begin{equation*}
      H^{\succeq [b]}_{G,X}(\Frob)=0.
  \end{equation*}
\end{proof}

Theorem \ref{thm:keyvanishing} clearly implies Theorem \ref{thm:algcycles}, since we have the vanishing result for all unramified $[b]$ in $B(G,\upsilon)$.
\subsection{Passage to cohomology}
\label{subsubsection:7.2}
We record here the method to get from the congruence relation on the level of algebraic cycles (Theorem \ref{thm:algcycles}) to the congruence relation on \'{e}tale cohomology (Theorem \ref{mainthm}).

We first note that by the main result of \cite{KMP19}, there exists a smooth projective toroidal compactification of $\sS_{K}(G,X)$, and hence by proper base change there is a canonical $\mathrm{Gal}_{E}$-equivariant isomorphism
\begin{equation}
\label{eqn:7.3}
    H^i_{\mathrm{\acute{e}t}}(\Sh_K(G,X)_{\bar{E}},\bbQ_l)\xlongrightarrow{\sim}H^i_{\mathrm{\acute{e}t}}(\sS_K(G,X)_{\bar{\kappa}},\bbQ_l).
\end{equation}
Moreover, the action of $\calH(G(\bbQ_p)//K_p,\bbQ)$ on the left naturally extends to an action on the right. Given any algebraic cycle $C$ in $\bbQ[p-\Isog\otimes\kappa]$, we see that the image of $C$ under the map
\begin{equation*}
    p-\Isog\otimes\kappa\xrightarrow{s,t} \sS_K(G,X)_\kappa \times \sS_K(G,X)_\kappa
\end{equation*}
defines a correspondence on $\sS_K(G,X)_\kappa$, with an induced action on cohomology. Since the congruence relation holds in $\bbQ[p-\Isog\otimes\kappa]$, it also holds in the ring of algebraic correspondences $\mathrm{Corr}(\sS_K(G,X)_\kappa,\sS_K(G,X)_\kappa)$. We thus have the relation on $H^i_{\mathrm{\acute{e}t}}(\sS_K(G,X)_{\bar{\kappa}},\bbQ_l)$, and thus, via the isomorphism above, the congruence relation on $H^i_{\mathrm{\acute{e}t}}(\Sh_K(G,X)_{\bar{E}},\bbQ_l)$. This in fact holds with $\bbQ_l$ replaced by any \'{e}tale sheaf $\mathcal{V}$ over $\sS_K(G,X)$, since we have a similar isomorphism as in \eqref{eqn:7.3} with $\bbQ_l$ replaced with $\mathcal{V}$, see \cite[Thm. 6.7]{LS18}. A similar argument holds for compactly supported cohomology $H^i_{\mathrm{\acute{e}t,c}}(\Sh_K(G,X)_{\bar{E}},\mathcal{V})$.

In the case of intersection cohomology of the Baily-Borel compactification, we know, also from \cite{KMP19}, that there is a projective normal model $\sS^{\mathrm{min}}_K(G,X)$ over $O_{E,(v)}$ of the Baily-Borel compactification of $\Sh_K(G,X)$. Moreover, here we can apply \cite[Thm. 6.7]{LS18} as well, and we have an isomorphism of \'{e}tale intersection cohomology groups
\begin{equation*}
\mathbf{IH}^i(X_{\bar{E}},\overline{\bbQ}_l)\xrightarrow{\sim}\mathbf{IH}^i(X_{\bar{\kappa}},\overline{\bbQ}_l).
\end{equation*}
The same result also holds if we replace the intersection complex of $\Sh_K(G,X)$ with the sheaf $(j_{!,*}(\mathcal{V}[n]))[-n]$, where $j:\Sh_K(G,X)\hookrightarrow \Sh^{BB}_K(G,X)$, $n=\dim\Sh_K(G,X)$, and $\mathcal{V}$ is an automorphic $\lambda$-adic sheaf.

Since $\sS_K(G,X)_\kappa$ is open and dense in $\sS^{\mathrm{min}}_K(G,X)_\kappa$, we are reduced to showing that the congruence relation in $\mathrm{Corr}(\sS_K(G,X)_\kappa,\sS_K(G,X)_\kappa)$ implies, after taking closure of algebraic cycles, the congruence relation in $\mathrm{Corr}(\sS^{\mathrm{min}}_K(G,X)_\kappa,\sS^{\mathrm{min}}_K(G,X)_\kappa)$. To see this, let $C\subset \Sh_K(G,X)\times\Sh_K(G,X)$ be an algebraic correspondence corresponding to the action of some double coset $1_{K_pgK_p}\in \calH(G(\bbQ_p)//K_p,\bbQ)$, and $\mathscr{C}$ the closure of $C$ in $\sS^{\mathrm{min}}_K(G,X)\times \sS^{\mathrm{min}}_K(G,X)$. The boundary components $\sS^{\mathrm{min}}_K(G,X)\backslash \sS_K(G,X)$ consists of (flat integral models of) Hermitian symmetric domains, and over $E$, the induced left action of $g\in G(\mathbb{A}_f)$ on the boundary gives a finite correspondence on the boundary. Thus, if we let $\mathscr{C}'$ be the restriction of $\mathscr{C}$ to $\sS_K(G,X)\times\sS_K(G,X)$, we observe that $\mathscr{C}\backslash\mathscr{C'}$ is of dimension strictly less than $\dim \sS_K(G,X)$, since this is true over the generic fiber. Hence, we see that $\mathscr{C}'_\kappa$ is dense in $\mathscr{C}_\kappa$. Thus, taking closure allows us to conclude that we have the congruence relation in $\mathrm{Corr}(\sS^{\mathrm{min}}_K(G,X)_\kappa,\sS^{\mathrm{min}}_K(G,X)_\kappa)$, as desired.


text:
\begin{document}
\bibliographystyle{plain}

\maketitle

\begin{abstract}
We give two results for computing doubly-twisted conjugacy relations
in free groups with respect to homomorphisms $\phi$ and $\psi$ such
that certain remnant words from $\phi$ are longer than the images of
generators under $\psi$.

Our first result is a remnant inequality condition which implies that
two words $u$ and $v$ are not doubly-twisted conjugate. Further we
show that if $\psi$ is given and $\phi$, $u$, and $v$ are chosen at
random, then the probability that $u$ and $v$ are not doubly-twisted
conjugate is 1. In the particular case of singly-twisted conjugacy,
this means that if $\phi$, $u$, and $v$ are chosen at random, then $u$
and $v$ are not in the same singly-twisted conjugacy class with probability 1.

Our second result generalizes Kim's ``bounded solution length''. We
give an algorithm for deciding doubly-twisted conjugacy relations in the
case where $\phi$ and $\psi$ satisfy a similar remnant inequality. In
the particular case of singly-twisted conjugacy, our algorithm
suffices to decide any twisted conjugacy relation if $\phi$ has
remnant words of length at least 2.

As a consequence of our generic properties we give an elementary proof
of a recent result of Martino, Turner, and Ventura, that
computes the densities of injective and surjective homomorphisms
from one free group to another. We further compute the expected value of the density of the image of a homomorphism.
\end{abstract}

\section{Introduction}
Let $G$ and $H$ be finitely generated free groups, and $\phi, \psi: G
\to H$ be homomorphisms. The group $H$ is partitioned into the set of
\emph{doubly-twisted conjugacy} classes as follows: $u, v \in H$ are in the
same class (we write $[u] = [v]$) if and only if there is some $z\in G$
with
\[ u = \phi(z) v \psi(z)^{-1}. \]

Our principal motivation for studying doubly-twisted conjugacy is Nielsen
coincidence theory (see \cite{gonc05} for a survey), the study of
the coincidence set of a pair of mappings and the minimization of this
set while the mappings are changed by homotopies. Our focus on free
groups is motivated specifically by the problem of computing \emph{Nielsen
classes} of coincidence points for pairs of mappings $f, g: X \to Y$,
where $X$ and $Y$ are compact surfaces with boundary.

A necessary condition for two coincidence points to be combined by a
homotopy (thus reducing the total number of coincidence points) is
that they belong to the same Nielsen class. (Much
of this theory is a direct generalization of similar techniques in
fixed point theory, see \cite{jian83}.) The number of ``essential''
Nielsen classes is called the Nielsen number, and is a lower bound for
the minimal number of coincidence points when $f$ and $g$ are allowed
to vary by homotopies.

On surfaces with boundary, deciding when two coincidence points are in the
same Nielsen class is equivalent to solving a natural doubly-twisted
conjugacy problem in the fundamental groups, using the induced
homomorphisms given by the pair of mappings.
Thus the Nielsen classes of coincidence points correspond to
twisted conjugacy classes in $\pi_1(Y)$.

The problem of computing doubly-twisted conjugacy classes in free groups is
nontrivial, even in the singly-twisted case which arises in fixed
point theory, where $\phi$ is an endomorphism and $\psi$ is the
identity. An algorithm for the singly-twisted conjugacy decision
problem where $\phi$ is an automorphism is given in \cite{bmmv06}.
Few techniques for computing doubly-twisted conjugacy in free groups are
available. A generally applicable technique using abelian and
nilpotent quotients is given in \cite{stae07b}, but is it is hard to
predict when it will be sucessful. A technique is given in
\cite{stae09b} which can often show
that two words are in different doubly-twisted conjugacy classes, but
the hypotheses on the homomorphisms are quite strong.

Our methods are based on the combinatorial \emph{remnant} condition
for homomorphisms. Informally, a homomorphism $\phi$ has remnant if the
images under $\phi$ of generators have limited cancellation when
multiplied together. The noncancelling parts are called the remnant
subwords.

If $\phi, \psi: G \to H$ are
homomorphisms and $u,v \in H$ are words, we consider the remnant subwords
of $\phi$ which remain uncancelled even after making products with the
words $u$ and $v$ themselves. If, in each generator $a$, this remnant
subword is of length greater than or equal to the length of
$\psi(a)$, then $u$ and $v$ are in different doubly-twisted conjugacy
classes. This is shown in Section \ref{densitysection}.

In Section \ref{mtvsection} we present some improvements
to recent work of Martino, Turner, and Ventura in
\cite{mtv08} concerning the density of injective and surjective
homomorphisms of free groups. Their paper shows that, when the rank of
$H$ is greater than 1, a homomorphism chosen at random will be
injective but not surjective with probability 1. We give a new and
more elementary proof of this theorem, and strengthen the result
concerning surjectivity by showing that the expected value of the
density of the image subgroup of a random
homomorphism is 0. We also treat the case when the rank of $H$ is 1.

In Section \ref{bslsection} we consider only the traditional remnant
subword (without making products with $u$ and $v$). If this subword of
$\phi(a)$ is of
length strictly greater than the length of $\psi(a)$ for each
generator $a$, then we give an algorithm to decide whether or not $u$
and $v$ are in different doubly-twisted conjugacy classes. This result
is a generalization of Kim's ``bounded solution
length'' technique in \cite{kim07}, and
was developed independently for singly-twisted conjugacy by Hart,
Heath, and Keppelmann in \cite{hhk09}.

In Sections \ref{densitysection} and \ref{bslsection} we show that,
given a homomorphism $\psi$, the remnant inequality used in that
section will hold with probability 1 when $\phi$
is chosen at random. This implies in Section \ref{densitysection} that
if $\psi$ is fixed and $\phi$, $u$, and $v$ are all chosen at random,
then $[u] \neq [v]$ with probability 1. In Section \ref{bslsection} we show that
if $\psi$ is fixed and $\phi$ is chosen at random, then there is an
algorithm to decide whether or not $[u] = [v]$ for any words $u$ and $v$.

The techniques and algorithms described in this paper have been
implemented for the computational algebra system GAP
\cite{gap}. Source code and a user-friendly web based version are
available for experimentation at the author's website.

The author would like to thank Robert F. Brown, Marlin Eby, and Philip
Heath for helpful comments on this paper, and Armando Martino for
bringing the reference \cite{mtv08} to our attention.

\section{Generic remnant properties}\label{reviewsection}
Wagner, in \cite{wagn99}, defined the remnant condition for
free group endomorphisms which would become a key tool for several
later techniques for computation of the Nielsen number in fixed point
theory (the special case where $\psi$ is the identity) for certain
mappings on surfaces with boundary. Extensions of Wagner's technique
have been made in \cite{hk07} and \cite{kim07}, and for Nielsen
periodic point theory in \cite{hhk08}.

Wagner's definition of remnant extends to homomorphisms (not necessarily
endomorphisms) of free groups as follows. Throughout, for a word $w
\in H$, the reduced word length of $w$ is denoted $|w|$.

\begin{defn}\label{remnantdef}
Let $H$ be a free group, and $t = (h_1, \dots, h_n)$ a tuple of words
of $h$. We say that $t$ \emph{has remnant} when, for each $i$, there
is a nontrivial subword of $h_i$ which does not cancel in any product
of the form
\[ h_j^{\alpha_j} h_i h_k^{\beta_k} \]
where $j,k \in \{1, \dots, n\}$, with $\alpha_l, \beta_l \in \{ -1, 0,
1 \}$ for $l\neq i$ and $\alpha_i, \beta_i \in \{ 0, 1\}$. Each such
noncanceling subword is called the remnant of $h_i$, denoted $\Rem_t
h_i$.

The statement that a set of elements has remnant is closely related to
the statement that it be Nielsen reduced (see e.g.\ \cite{ls77}).

If $G$ has generators $a_1, \dots, a_n$, and $\phi: G \to H$ is
a homomorphism, then we say that $\phi$ \emph{has remnant} if the
tuple $(\phi(a_1), \dots, \phi(a_n))$ has remnant in the above
sense. In this case, the remnant of $\phi(a_i)$ is denoted $\Rem_\phi
a_i$.

If $\phi$ has remnant, the \emph{remnant length} of $\phi$ is the
minimum length of $|\Rem_\phi a_i|$ for any $i$.
\end{defn}

Throughout this paper, the remnant condition is used
typically as follows: we will have a homomorphism $\phi: G \to H$ and some
element $z\in G$ with reduced form $z = a_{j_1}^{\eta_1} \dots
a_{j_k}^{\eta_k}$. When $\phi$ has remnant, writing
$X_i = \phi(a_{j_i})^{\eta_i}$, we have the reduced product
\[ \phi(z) = X_1 \dots X_k = R_1 \dots R_k, \]
where $R_i$ is the subword of $X_i$ which does not cancel in the
product $X_1 \dots X_k$. Since $\phi$ has remnant, the right hand side
will be fully reduced and $(\Rem_\phi a_i)^{\eta_i}$ will be a subword
of $R_i$ for all $i$.

Use of the asymptotic density in the context of doubly-twisted
conjugacy was presented in \cite{stae09b}. We will quote the relevant
terms and results here.

For a free group $G$ and a natural number $p$, let $G_p$ be the subset
of all words of length at most $p$. The \emph{asymptotic density} (or simply
\emph{density}) of a subset $S\subset G$ is defined as
\[ D(S) = \lim_{p \to \infty} \frac{|S \cap G_p|}{|G_p|}, \]
where $|\cdot|$ denotes the cardinality. The set $S$ is said to be
\emph{generic} if $D(S) = 1$.

Similarly, if $S \subset G^l$ is a set of $l$-tuples of
elements of $G$, the asymptotic density of $S$ is defined as
\[ D(S) = \lim_{p \to \infty} \frac{|S \cap (G_p)^l|}{|(G_p)^l|}, \]
and $S$ is called \emph{generic} if $D(S) = 1$.

A homomorphism on the free groups $G \to H$ with $G = \langle a_1,
\dots, a_n\rangle$
is equivalent combinatorially to an $n$-tuple of elements of $G$
(the $n$ elements are the words $\phi(a_1), \dots, \phi(a_n)$). Thus
the asymptotic density of a set of
homorphisms can be defined in the same sense as above, viewing the set of
homomorphisms as a collection of $n$-tuples.

A theorem of Robert F.\ Brown in \cite{wagn99} established that
``most'' endomorphisms have remnant. This is strengthened and made
more specific in \cite{stae09b} as the following:
\begin{lem}\label{genericlem}
Let $G$ and $H$ be free groups with the rank of $H$ greater than 1. Then
for any natural number $l$, the set of homomorphisms
  $\phi:G \to H$ with remnant length at least $l$ is generic.
\end{lem}

\section{The density of non-conjugate pairs}\label{densitysection}
Given a homomorphism $\phi: G \to H$ and two elements $u,v \in H$,
there is a natural homomorphism $\phi * u * v: G * \Z * \Z \to H$,
(where $*$ denotes the free product) defined as follows: let $G =
\langle a_1, \dots, a_n \rangle$,
write $b_1$ as the generator of the first $\Z$ factor, and $b_2$ as
the generator of the second $\Z$ factor. We then define $\phi*u*v$ on
each factor by
\[ \phi*g*h : \begin{array}{rcl}
a_i &\mapsto &\phi(a_i) \\
b_1 &\mapsto &u \\
b_2 &\mapsto &v \end{array} \]

The basic idea of the present theorem is inspired by the nice proof of
Wagner's theorem given in \cite{kim07}.

\begin{thm}\label{classdist}
Let the rank of $H$ be greater than 1, let $\phi, \psi: G \to H$ be
homomorphisms, and let $u, v \in H$. Let $\bar \phi = \phi * u *
v$. If $\bar \phi$ has remnant with
\[ |\Rem_{\bar \phi} a| \ge |\psi(a)| \]
for all generators $a\in G$, then $[u]\neq [v]$.
\end{thm}

\begin{proof}
For the sake of a contradiction we assume that $[u]=[v]$, and so there
is some $z \in G$ with
\begin{equation}\label{twistconj}
\psi(z) = u^{-1} \phi(z) v.
\end{equation}
Express $z$ as the reduced word
\[ z = a_{j_i}^{\eta_i} \dots a_{j_k}^{\eta_k}, \]
where $a_{j_i}$ are generators of $G$ and $\eta_i \in \{-1, 1\}$, and
write the images of the generators as the reduced words $X_i = \phi(a_{j_i}^{\eta_i})$ and $Y_i = \psi(a_{j_i}^{\eta_i})$.

We first write
\[ u^{-1}\phi(z)v = u^{-1}X_1 \dots X_kv = R_u R_1 \dots R_k R_v, \]
where the right hand side is reduced, $R_i$ is the subword of
$X_i$ which does not cancel in the above, and $R_u$ and $R_v$ are the
subwords of $u^{-1}$ and $v$ which do not cancel in the above. Because
$\bar \phi$ has remnant, we know that $R_u$ and $R_v$ are nontrivial,
and $R_i$ contains $(\Rem_{\bar\phi} a_{j_i})^{\eta_i}$ as a subword.

Then we have
\begin{align*}
|u^{-1}\phi(z) v| &= |R_u| + |R_v| + \sum_{i=1}^{k} |R_i| \\
&\ge |R_u| + |R_v| + \sum_{i=1}^{k} |\Rem_{\bar\phi}
a_{j_i}| \\
&> \sum_{i=1}^{k} |\Rem_{\bar\phi} a_{j_i}| \ge \sum_{i=1}^k |Y_i|
\ge |\psi(z)|,
\end{align*}
and the strict inequality contradicts \eqref{twistconj}.
\end{proof}

The above theorem is similar to the result of \cite{stae09b} that
$[u]\neq [v]$ when $\phi * \psi * (uv^{-1})$ has remnant.
The fact that we require no
remnant condition of $\psi$ allows our result, unlike that of
\cite{stae09b}, to be specialized to the case of singly-twisted
conjugacy:
\begin{cor}
For an endomorphism $\phi: G\to G$, let $[u]$ denote the singly-twisted conjugacy class of $u$.

If $\phi * u * v$ has remnant, then $[u] \neq [v]$.
\end{cor}

We now note that Theorem \ref{classdist} will generically apply for a
particular $\psi$ when $\phi$, $u$, and $v$ are chosen at random. This
result is a strengthening of the final Theorem of \cite{stae09b}
using different methods.

\begin{thm}\label{generictriple}
Let the rank of $H$ be greater than 1, and let $\psi: G \to H$ be any
homomorphism. Then (again letting $[u]$ denote the doubly-twisted
conjugacy class with respect to $\phi$ and $\psi$) the set
\[ S = \{ (\phi, u, v) \mid [u] \neq [v] \} \]
is generic.
\end{thm}
\begin{proof}
Letting $n$ be the number of generators of $G$, we may view a triple
$(\phi, u, v)$ as a $(n+2)$-tuple of elments of $H$ (since a choice of
$\phi$ is combinatorially equivalent to a choice of the $n$ image
words in $H$). Thus we view $S$ as a subset of the cartesian product
$H^{n+2}$.

Let $k$ be the maximum length of any $|\psi(a_i)|$. Then by Theorem \ref{classdist} we have
\begin{align*}
S &= \{ t = (\phi(a_1), \dots, \phi(a_n), u, v) \mid [u] \neq [v] \}
\supset \{ t \in H^{n+2} \mid t \text{ has remnant length at least $k$} \} \\
&= \{ \rho: F_{n+2} \to H \mid \rho \text{ has remnant length at least
  $k$} \}
\end{align*}
and by Lemma \ref{genericlem} this set is generic.
\end{proof}

Since $\psi$ above is allowed to be any homomorphism, the special
cases where $\psi$ is the identity homomorphism and the trivial
homomorphism give:

\begin{cor}\label{triplecor}
Let $G$ and $H$ be free groups with the rank of $H$ greater than 1.
\begin{itemize}
\item If $G=H$ and $[u]$ denotes the singly-twisted conjugacy class of $u
\in G$ with respect to an endomorphism $\phi:G \to G$, then the set
\[ \{ (\phi, u, v) \mid [u] \neq [v] \} \]
is generic.
\item For homomorphisms $\phi: G \to H$, the set
\[ \{ (\phi, u, v) \mid uv^{-1} \not\in \phi(G) \} \]
is generic.
\end{itemize}
\end{cor}
\begin{proof}
The first statement follows directly from Theorem \ref{generictriple}
letting $\psi$ be the identity. For the second statement, let $\psi$
be the trivial homomorphism. Then $[u]=[v]$ if and only if $u =
\phi(z)v$, which is to say that $uv^{-1} \in \phi(G)$.
\end{proof}

\section{The densities of injections and surjections}\label{mtvsection}
From the second statement of Corollary \ref{triplecor}, together with
Lemma \ref{genericlem}, we obtain an alternative (and easier) proof of
a recent result by Martino, Turner, and Ventura in \cite{mtv08}
concerning the densities of injective and surjective homomorphisms of
free groups. The preprint \cite{mtv08} addresses only the second
statement below:
\begin{thm}\label{mtvthm}
Given free groups $G$ and $H$, let
$\Epi(G,H)$ and $\Mono(G,H)$ be the sets of all surjective and
injective homomorphisms $G \to H$, respectively.

\begin{enumerate}
\item \label{one1} If the rank of $H$ is 1 and the rank of $G$ is
$n>1$, then
\[ D(\Epi(G,H)) = \frac{1}{\zeta(n)}, \quad D(\Mono(G,H))
= 0, \]
where $\zeta(n)$ is the Reimann zeta function. (Note that $\zeta(n)
\to 1$ as $n \to \infty$.)
\item \label{other} If the ranks of $G$ and $H$ are both 1, or the rank
  of $H$ is greater than 1, then
\[ D(\Epi(G,H)) = 0, \quad D(\Mono(G,H)) = 1. \]
\end{enumerate}
\end{thm}
\begin{proof}
Let $G$ have generators $a_1, \dots, a_n$.

Statement \ref{one1} concerns homomorphisms $G \to \Z$, each of which
is equivalent to a choice of $n$ integers (where $n>1$). Let a
homomorphism $\phi$ be given by integers $m_1, \dots, m_n$.
Then $\phi$ is never injective: if $\phi(a_1) = m_1$ and
$\phi(a_2) = m_2$, then $\phi(a_1^{m_2}) = m_1m_2 =
\phi(a_2^{m_1})$. Thus $\Mono(G,H)$ is empty, and so $D(\Mono(G,H)) =
0$.

The homomorphism
$\phi$ is surjective if and only if there are integers $k_1, \dots,
k_n$ with
\[ k_1m_1 + \dots + k_nm_n = 1. \]
This in turn is equivalent to requiring that $\gcd(m_1, \dots, m_n)=1$,
since the gcd is the smallest positive integer which is an integral
linear combination of $m_1, \dots,
m_n$. It is known that the probability (in the appropriate asymptotic
sense) of $n$ randomly chosen integers being coprime is $1/\zeta(n)$,
see \cite{nyma72}. Thus $D(\Epi(G,H)) = 1/\zeta(n)$.

Now we prove statement \ref{other}, first in the case where the ranks
of $G$ and $H$ are both 1.
We may consider both $G$ and $H$ to be the
integers $\Z$. In this case, a homomorphism is equivalent to a choice
of a single integer (the degree of the homomorphism). The homomorphism
will be surjective if and only if the degree is $\pm 1$, and will be
injective if and only if the degree is nonzero. The desired densities
follow.

Now we prove the case where the rank of $H$ is greater than 1. We
first note that any homomorphism $\phi: G \to H$ with remnant is
injective: If some $\phi$ with remnant were not injective, then there
would be words $x, y \in G$ with
\[ \phi(x)\phi(y)^{-1} = 1. \]
But writing the above in terms of generators will show that the above
product cannot cancel, since the remnants will remain. Since the
homomorphisms with remnant have density 1 by Lemma \ref{genericlem}, we
have $D(\Mono(G,H)) = 1$.

The statement concerning $\Epi(G,H)$ is implied by the second
statement of Corollary \ref{triplecor}.
Let $S$ be the set of triples $(\phi, u, v)$ with $uv^{-1} \not \in
\phi(G)$, and Corollary \ref{triplecor} says that $D(S) = 1$. Let $T$ be
the set of non-surjective homomorphisms $G \to H$. Certainly $S$ is a
subset of $T \times H \times H$, and it is easy to check that $D(A
\times H) = D(A)$ for any set $A$. Thus we have
\[
D(\Epi(G,H)) = 1 - D(T) = 1 - D(T \times H \times H) \le 1-D(S) = 0.
\]
\end{proof}

The second statement of Corollary \ref{triplecor} suggests that a much
stronger statement concerning surjective homomorphisms may be
possible. In the case where $H$ has rank greater than 1, we have shown
that the image set $\phi(G)$ is a proper subset of $H$ with probability
1. We wish to give a more specific measure of the generic size of the
subset $\phi(G) \subset H$.

Let $\ED(G,H)$ be the \emph{expected value} of $D(\phi(G))$, which we define
as follows:
\[ \ED(G,H) = \lim_{p \to \infty} \frac{1}{|H_p|^n} \sum_{\phi \in
  (H_p)^n} D(\phi(G)), \]
where $n$ is the number of generators of $G$, so we regard a
homomorphism $\phi:G \to H$ as an element of $H^n$.

This expected value is related to $D(\Epi(G,H))$ as follows: a
surjection $\phi$ has $D(\phi(G)) = 1$, and so, letting $E_p =
\Epi(G,H) \cap (H_p)^n$, we have
\[
\ED(G,H) \ge \lim_{p \to \infty} \frac{1}{|H_p|^n} \sum_{\phi \in
  E_p} 1 = \lim_{p \to \infty} \frac{|E_p|}{|H_p|^n} =
D(\Epi(G,H)).
\]

Thus Theorem \ref{mtvthm} shows that if $H$ has rank 1 and the rank of
$G$ is $n>1$, then $\ED(G,H) \ge 1/\zeta(n)$. Theorem \ref{mtvthm}
gives no information in the case where $H$ has rank greater than 1,
since it would only imply that $\ED(G,H) \ge 0$, which is already clear.
Our goal for the remainder of the section is to compute the precise
value of $\ED(G,H)$. We rely on a lemma which estimates $D(\phi(G))$ when
$\phi$ has remnant.

\begin{lem}\label{poslem}
Let $\phi:G \to H$ be a homomorphism with remnant length $l$, and let
$n>1$ be the number of generators of $H$. Then
\[ D(\phi(G)) \le 16n(2n-1)^{\lceil l/2 \rceil}. \]
\end{lem}
\begin{proof}
If $\phi$ does not have remnant, then $l = 0$ and the statement to be
proved is $D(\phi(G)) \le 16n$, which is always the case. Thus we
assume that $\phi$ has remnant, and so $l>0$.

If $w \in \phi(G)$, then there is some $z$ with $w\phi(z) = 1$.
Thus if $w \in \phi(G)$, then $\phi * w$ does not have
remnant. Letting
\[ S = \{ w \mid \phi * w \text{ does not have remnant}\},  \]
we have $\phi(G) \subset S$. We will give an upper bound on $D(S)$,
which will imply an upper bound on $D(\phi(G))$.

Let $G$ have generators $a_1, \dots, a_n$, and let $u_i$ and $v_i$ be
the subwords of $\phi(a_i)$ respectively ``before'' and ``after'' the
remnant subword. That is, we can write $\phi(a_i)$ as
\[ \phi(a_i) = u_i r_i v_i, \]
where $r_i = \Rem_\phi a_i$, and the product $u_i r_i v_i$ is reduced
(allowing perhaps $u_i$ and $v_i$ to be trivial). Write $r_i =
s_it_i$, where $|s_i|$ and $|t_i|$ are at most $\lceil |r_i|/2 \rceil
\ge \lceil l/2 \rceil$. For brevity below, write $k = \lceil l/2 \rceil$.

In order for $\phi * w$ to have no remnant, some initial
subword of $w$ or $w^{-1}$ must equal one of the words $u_is_i$ or
$(t_iv_i)^{-1}$, or some terminal subword of $w$ or $w^{-1}$ must equal
$(u_is_i)^{-1}$ or $t_iv_i$. (Note that all of these words have length
greater than $k$.)

If $x$ is a word of length $m<p$, the number of words $w$ of length $p$
having $x$ as the initial subword is $(2n-1)^{p-m}$, since the first
$m$ letters of $w$ are fixed, and the remaining $p-m$ letters can be
any letter of $H$ except the inverse of the previous.
Thus the number of
words $w$ having $u_is_i$ as the initial subword is
$(2n-1)^{p-|u_is_i|} \le (2n-1)^{p-k}$. Similarly the number of words $w$ of
length $p$ having $(t_iv_i)^{-1}$ as the initial subword is at most
$(2n-1)^{p-k}$, and the number of words $w$ having $(u_is_i)^{-1}$ as the
terminal subword and the number of words $w$ having $t_iv_i$ as the
terminal subword are at most $(2n-1)^{p-k}$. Since there are $n$ possible
values for $i$, and we must allow for words $w^{-1}$ with each of the
above 4 constraints, we have
\[ |S \cap H_p| \le 8n(2n-1)^{p-k}, \]
and thus
\begin{equation}\label{Sdensity}
D(S) \le \lim_{p \to \infty} 8n\frac{(2n-1)^{p-k}}{|H_p|}
\end{equation}

For $i>0$, the number of words of length exactly $i$ is $2n(2n-1)^{i-1}$,
since the first letter can be any letter of $H$, while each subsequent
letter can be anything but the inverse of the previous. Summing gives
the formula
\[
|H_p| = 1 + \sum_{i=1}^p 2n(2n-1)^{i-1} = \frac{n(2n-1)^p - 1}{n-1}
\]
and thus we have
\[
\frac{(2n-1)^{p-k}}{|H_p|} = \frac{(n-1)(2n-1)^{p-k}}{n(2n-1)^p - 1}
\le 2 \frac{(n-1)(2n-1)^{p-k}}{n(2n-1)^p} \le 2(2n-1)^{-k}.
\]

Then \eqref{Sdensity} becomes
\[ D(S) \le 16n(2n-1)^{-k}, \]
and the fact that $\phi(G) \subset S$ gives the desired result.
\end{proof}

We now make the computation of the expected value.
\begin{thm}\label{edthm}
Let $G$ and $H$ be free groups.
\begin{enumerate}
\item If the rank of $H$ is 1 and the rank of $G$ is $n>1$, then
\[ \ED(G,H) = \frac{\zeta(n+1)}{\zeta(n)} \]
\item If the ranks of $G$ and $H$ are both 1, or if the rank of $H$ is
  greater than 1, then
\[ \ED(G,H) = 0. \]
\end{enumerate}
\end{thm}
\begin{proof}
We begin with the first statement, which concerns homomorphisms $G \to
\Z$, each of which is equivalent to a choice of $n$ integers (with
$n>1$). If $\phi$ is given by the tuple of integers $\vt = (m_1, \dots,
m_n)$, then $\phi(G)$ is equal to the set $d\Z$, the integer multiples
of $d$, where $d = \gcd(\vt)$. This set has density
$1/\gcd(\vt)$. Thus we have:
\[ \ED(G,\Z) = \lim_{p \to \infty} \frac{1}{|H_p|^n} \sum_{
  \vt \in (H_p)^n} \frac{1}{\gcd(\vt)} \]

Thus $\ED(G,\Z)$ is equal to the expected value of the reciprocal of
the $\gcd$ function when applied to $n$ arguments. A standard
rearrangement expresses this expected value as a series:
\begin{align*}
\ED(G,\Z) &= \lim_{p \to \infty} \frac{1}{|H_p|^n} \sum_{\vt
\in (H_p)^n} \frac{1}{\gcd(\vt)} \\
&= \lim_{p \to \infty} \frac{1}{|H_p|^n} \sum_{d = 1}^p \frac{1}{d}
|\{ \vt \in (H_p)^n \mid \gcd(\vt) = d \}| \\
&= \sum_{d=1}^\infty \frac1d \lim_{p \to \infty}
\frac{1}{|H_p|^n} |\{ \vt \in (H_p)^n \mid
\gcd(\vt) = d\}|,
\end{align*}
where the exchanging of the limit and the sum is valid provided that
the inner limit exists and is finite. The inner limit can be interpreted as
the probability (in the appropriate asymptotic
sense) that a random $n$-tuple has gcd equal to $d$.
This probability
is known to be equal to $d^{-n}/\zeta(n)$ (see equation 5.1 of
\cite{cs87}). This gives
\[ \ED(G,\Z) = \sum_{d=1}^\infty \frac{d^{-1-n}}{\zeta(n)} =
\frac{1}{\zeta(n)} \sum_{d=1}^{\infty} \frac{1}{d^{n+1}} =
\frac{\zeta(n+1)}{\zeta(n)} \]
where the last equality is the definition of $\zeta(n+1)$.

Now we prove the second statement. First we treat the case where $G$
and $H$ are rank 1. Then we will write $G =H=\Z$, and a homomorphism
$\phi:\Z \to \Z$ is equivalent to a single integer (the degree of
$\phi$). Writing $\phi \in \Z$ as this integer, we have
\[ \ED(\Z,\Z) = \lim_{p \to \infty} \frac{1}{2p+1} \sum_{\phi = -p}^p
D(\phi(\Z)). \]

If $\phi$ is the homomorphism given by multiplication by $k$, then the
image $\phi(\Z)$ is the set $k\Z = \{kn \mid n \in \Z \}$, which has
density $1/|k|$. Thus the above becomes
\[ \ED(\Z,\Z) = \lim_{p \to \infty} \frac{1}{2p+1} 2\sum_{k=1}^p
\frac{1}{k}. \]
(We have dropped the $k=0$ term, since the image of the trivial
homomorphism has density 0.) It is routine to verify that the above
limit exists and equals 0.

Now we prove the case where the rank of $H$ is greater than 1.
Let $R_l$ be the set of all homomorphisms $\phi:G \to H$ with remnant
length at least $l$. By Lemma \ref{genericlem} this set is generic.

Let $n$ be the rank of $G$, and let $l$ be any natural number. Then,
using Lemma \ref{poslem}, we have
\begin{align*}
\ED(G,H) &= \lim_{p \to \infty} \frac{1}{|H_p|^n} \left( \sum_{\phi \in
  R_l \cap (H_p)^n} D(\phi(G)) + \sum_{\phi \in (H_p)^n - R_l}
D(\phi(G)) \right) \\
&\le \lim_{p \to \infty} \frac{1}{|H_p|^n} \left( \sum_{\phi \in R_l
  \cap (H_p)^n} 16n(2n-1)^{-\lceil l/2 \rceil} + \sum_{\phi \in (H_p)^n
  - R_l} 1 \right) \\
&= \lim_{p \to \infty} 16n(2n-1)^{-\lceil l/2 \rceil} \frac{|R_l \cap
  (H_p)^n|}{|H_p|^n} + \frac{|(H_p)^n - R_l|}{|H_p|^n}
\end{align*}
In the limit as $p \to \infty$, the first fraction converges to the
density of $R_l$, which is 1, and the second converges to the density
of its complement, which is 0. Thus we have
\[ \ED(G,H) \le 16n(2n-1)^{-\lceil l/2 \rceil}, \]
and since $l$ is any natural number, we have $\ED(G,H) = 0$.
\end{proof}

\section{Bounded solution length}\label{bslsection}
In this section we show that a remnant inequality similar to the one
in Theorem \ref{classdist} implies an algorithm for deciding
doubly-twisted conjugacy relations.

\begin{defn}
Given homomorphisms
$\phi, \psi: G \to H$ and a pair of group elements $u,v \in H$, we say
that the pair $(u,v)$ has \emph{bounded solution length} (or \BSL) if
there is some $k>0$ such that the equation $u =\phi(z)v\psi(z)^{-1}$
is satisfied (if at all) only if $|z|\le k$. The smallest such $k$ is
called the \emph{solution bound} (or \SB) for $(u, v)$.
\end{defn}

Our casting of the \BSL\ condition generalizes
the concept for singly-twisted conjugacy of the same name in
\cite{kim07}, where $G=H$ and $\psi$ is assumed to be the identity
homomorphism. (Kim works in the setting where the words $u$ and $v$ are
always taken to be ``Wagner tails'' of $\phi$ which are not
indirectly related in Wagner's algorithm. We omit this distinction
so that the \BSL\ condition can be defined without any reference to the
set of Wagner tails.)

Our main theorem in this section is that if $\phi$ and $\psi$ satisfy
a remnant condition similar to the condition in Theorem
\ref{classdist} then any pair $(u,v)$ will have \BSL\ with a
predictable solution bound. This implies an algorithm for deciding
doubly-twisted conjugacy relations between any elements.

The following theorem was independently proved in the setting of
singly-twisted conjugacy by Hart, Heath, and Keppelmann in
\cite{hhk09} using essentially the same argument. Their solution bound
was better than the one initially discovered by this author, and has
been incorporated into the proof below.

\begin{thm} \label{bsl}
Let $\phi, \psi: G \to H$ be homomorphisms, such that
\[ |\Rem_\phi a_i| > |\psi(a_i)| \]
for each generator $a_i\in G$. Let $l = \min_i(|\Rem_\phi a_i| -
|\psi(a_i)|)$.  Then any pair $(u,v)$ has \BSL, with solution bound
\[ \SB \le \frac{|u| + |v|}{l}. \]
\end{thm}
\begin{proof}
Let $u, v \in H$, and let $z \in G$ be a word of length $k$. To show
that $(u,v)$ has \BSL, we will show that for $k$ sufficiently
large, we have $\psi(z) \neq u^{-1} \phi(z) v$.

As in the proof of Theorem \ref{classdist}, write $z$ as the reduced
word $z = a_{j_1}^{\eta_1} \dots a_{j_k}^{\eta_k}$, where each $a_j$
is a generator of $G$ and each $\eta_i = \pm 1$. Let $X_i =
\phi(a_{j_i}^{\eta_i})$ and $Y_i = \psi(a_{j_i}^{\eta_i})$, then we
have
\[ u^{-1} \phi(z) v = u^{-1} X_1 \dots X_k v. \]
Since $\phi$ has remnant, we can use notation as in the proof of
Theorem \ref{classdist} (though this time not worrying about $u^{-1}$
and $v$) to write this product as
\[
u^{-1} \phi(z) v = u^{-1} R_1 \dots R_k v,
\]
where each $R_i$ is a subword of $X_i$ with $|R_i| \ge
|\Rem_\phi a_{j_i}|$, and no cancellation occurs in any $R_i R_{i+1}$.

Now we will show that $\psi(z) \neq u^{-1} \phi(z) v$ by showing that
these two words are of different lengths for sufficiently large $k$. We have
\begin{align*}
|u^{-1}\phi(z)v| - |\psi(z)| &= |u^{-1} R_{1} \dots R_{k} v|
- |Y_1 \dots Y_k| \\
&\ge |R_{1} \dots R_{k}| - |u| - |v| - |Y_1 \dots Y_k| \\
&=  - |u| - |v| + \left(\sum_{i=1}^k |R_i|\right) - |Y_1 \dots Y_k| \\
&\ge -|u| - |v| + \sum_{i=1}^k \left( |R_i| - |Y_i| \right) \\
&\ge -|u| - |v| + \sum_{i=1}^k \left( |\Rem_\phi a_{j_i}| - |Y_i| \right) .
\end{align*}
By the hypothesis to our theorem, we know that $|\Rem_\phi a| - |\psi(a)|
\ge l$ for every generator $a \in G$. Therefore the above inequalies give
\[ |u^{-1}\phi(z)v| - |\psi(z)| \ge kl - |u| - |v|, \]
and we can choose $k$ sufficiently large so that $|u^{-1} \phi(z) v| -
|\psi(z)|$ is greater than zero. In particular it suffices to choose
\[ k > \frac{|u| + |v|}{l} \]
which is the desired solution bound.
\end{proof}

Theorem \ref{bsl} implies (subject to the remnant hypotheses)
that, given any elements $u, v \in H$, we can algorithmically
determine whether or not $[u] = [v]$:
check for equality of $u = \phi(z) v \psi(z)^{-1}$ where $z$ ranges
over all elements of $G$ with $|z|\le \frac{|u| + |v|}l$.
\begin{exl}
Let us consider the pair of homomorphisms on the free group with two
generators:
\[
\phi: \begin{array}{rcl}
a &\mapsto & baba^2 \\
b &\mapsto & a^2b^{-1}ab^3 \end{array}
\quad
\psi: \begin{array}{rcl}
a &\mapsto & b^{-2} \\
b &\mapsto & a \end{array}
\]
We will compare the two classes $[bab]$ and $[b^4a^2]$. (Neither
Theorem \ref{classdist} nor the result of \cite{stae09b} will suffice
to make the comparison.) It is easy to verify that the hypotheses of
Theorem \ref{bsl} are satisfied with $l=3$. Thus, if there is some $z$ with
\[ \psi(z) = bab \phi(z) (b^4a^2)^{-1}, \]
then it must be the case that $|z| \le \frac{|bab|+|b^4a^2|}{3} = 3$.

It suffices to check all elements $z$ of length at most 3 in the above
equation. Such a check is performed easily by computer, and reveals
that no element $z$ of length at most 3 satisfies the equation. Thus
$[bab] \neq [b^4a^2]$.
\end{exl}

This gives new and useful
algebraic decision algorithms, even in the cases where $\psi$ is taken
to be the identity or the trivial homomorphism:
\begin{cor}\label{decisioncor}
Let $G$ and $H$ be finitely generated free groups.
\begin{enumerate}
\item (Doubly-twisted version) If $\phi, \psi: G \to H$ are homomorphisms
  with $|\Rem_\phi a| > |\psi(a)|$ for every generator $a \in G$, then
  there is an algorithm to decide whether or not there is some $z$ with
\[ u = \phi(z) v \psi(z)^{-1} \]
for any $u, v \in H$.
\item (Singly-twisted version) If $\phi: G \to G$ is a homomorphism with
  $|\Rem_\phi a| > 1$ for every generator $a \in G$, then there is an
  algorithm to decide whether or not there is some $z$ with
\[ v = \phi(z) u z^{-1} \]
for any $u,v  \in H$. (This same algorithm is obtained independently by
Hart, Heath, and Keppelmann in \cite{hhk09}.)
\item ($\psi = 1$ version) If $\phi: G \to H$ is a homomorphism with
  remnant, then there is an algorithm to decide whether or not
\[ w \in \phi(G) \]
for any $w \in H$.
\end{enumerate}
\end{cor}
The third statement is obtained from the first by letting $\psi$ be the trivial
homomorphism, $v$ the trivial element, and $u=w$.

We note that in Theorem \ref{bsl}, the statement that $(u,v)$
has \BSL\ over any finite set is a direct generalization of Kim's
Theorem 4.7 of \cite{kim07}. If we let $\psi$ be the identity
homomorphism, then our hypothesis is that, for all
generators $a \in G$, we have $|\Rem_\phi(a)|
> |a| = 1$, which is to say that $|\Rem_\phi(a)| \ge 2$. This is
precisely the hypothesis used in Kim's Theorem 4.7 to show
that any pair of Wagner tails has \BSL. Kim's focus on the set of Wagner tails allows
his solution bound to be more specific than ours (Kim shows
that $\SB \le 4$ in all cases).

We conclude by noting that for a particular choice of homomorphism
$\psi$, the remnant hypothesis for Theorem \ref{bsl} is
satisfied for generic $\phi$. Letting $l$ be the maximum length of
$\psi(a)$ for any generator $a \in G$, Lemma \ref{genericlem}
shows that
\[ \{ \phi \mid |\Rem_\phi a| > |\psi(a)| \text{ for any generator $a
  \in G$}\} \]
is generic.


TITLE: Homeomorphism between $\mathbb{S}^1/(x\sim -x)$ and $\mathbb{S}^1$
QUESTION [1 upvotes]: I was reading this paper by Kim A. Frøyshov about the real projective plane and in part of the proof to show that it is homeomorphic to $\mathbb{S}^1$ they first showed it was homeomorphic to $\mathbb{S}^1/(x\sim-x)$. That part I understood but then they show that $\mathbb{S}^1/(x\sim-x)$ is homeomorphic to $\mathbb{S}^1$ by taking:
$$\mathbb{S}^1=\{z\in\mathbb{C}:\|z\|=1\}$$
And then taking the map:
$$f:\mathbb{S}^1\rightarrow \mathbb{S}^1/(x\sim-x),\space f(z)=z^2$$
They then claim that since $\mathbb{S}^1/(x\sim-x)$ is compact, and that $\mathbb{S}^1$ is Hausdorf that $f$ is a homeomorphism. This part I have trouble with, how can $f$ be a homeomorphism if it is not injective? What am I missing? I see that it is continuous and surjective but where do they get injectivity from?

REPLY [0 votes]: $\mathbb{RP}^1=\mathbb{R}\cup \{\infty \}$,so we can imagine $S^1$ is homeomorphic to $\mathbb{RP}^1$ by projection.
I hope this will help you think about it.