TITLE: Uniform continuity of functions on open interval
QUESTION [1 upvotes]: Which  of the following functions/is uniformly continuous on the interval (0,1)?

$$J(x)=\frac{1}{x}$$
$$J(x) = x \sin \frac{1}{x}$$
$$J(x) = \sin \frac{1}{x}$$
$$J(x)=\frac{\sin x}{x}$$

I think second and fourth option are correct, since interval is open, and both functions converges to $0$ as $x$ approaches infinity. Am I right?

REPLY [1 votes]: I'll try to formalize this idea of "convergent at the boundaries $\Rightarrow$ uniformly continuous".
For the second function : $\lim_{x \to 0} J(x) = 0$.
Let $J' : [0,1] \to \mathbb{R} ; x \mapsto \begin{cases} \frac{\sin(x)}{x} &&\text{if }x>0 \\ 0 &&\text{if } x=0 \end{cases}$.
This function is continous on a closed interval of $\mathbb{R}$. Thus it is uniformly continous (Heine Theorem). So $J$, which is its restriction to $(0,1]$, is uniformly continuous.


TITLE: Given the $x$ and $z$ components of a vector in $\mathbb{R}^3,$ and the angle it makes with plane $xz,$ how can I find the magnitude?
QUESTION [0 upvotes]: The vector  $\textbf V$  has components  $5.4 i + y j + 5.3 k$ .  If  V  makes an angle with the $xz$-plane of $55.7$ degrees, what is its magnitude $| V |$?

That's the specific question I am working on, however I would like the steps explained so I understand the concept for future use. I am a $1$st year university student, so if possible, limit your formulas to the dot product (like $\textbf{V} \bullet \textbf{i} = |\textbf{V}| |\textbf{i}| \cos{x}$) and the simpler formulas since I'm still learning many concepts and it might fly over my head otherwise.
Currently, I am under the impression that taking the dot-product formula is what I need to be doing, but the major hangup for me is figuring out how the plane and angle need to be applied to solve the problem.

REPLY [0 votes]: Expanding on what Will Jagy said, taking 34.3 degrees to be theta,
$v ⃗⋅j ̂=|v ⃗ ||j ̂ |  cosθ
$
$v ⃗⋅j ̂= v_y = y$
and j is a unit vector, with a magnitude of 1,
so $y = |v ⃗|cosθ$
expanding that,
$y= \sqrt{y^2 + 5.4^2 + 5.3^2 }  cosθ$
$y^2 = (y^2 + 57.25)  cos^2 θ$
$y^2 − y^2  cos^2 θ = 57.25 cos^2 θ$
$y^2 (1-cos^2 θ)$ = $57.25 cos^2 θ$
$y^2 (sin^2 θ)$ = $57.25 cos^2 θ$
$y^2 = \frac {57.25 cos^2 θ}{sin^2 θ} $
$y^2 = \frac {52.25}{tan^2 θ} $
$y =  \frac {\sqrt{52.25}}{tan θ} $
Now that we have y, factor the formula $y = |v|cosθ$ into
$ \frac {y} {cosθ} = |v ⃗| $
Since $y \approx 11.09$ and $ \theta = 34.3^∘ $
$ |v ⃗| \approx 13.43 $
Hopefully all that made sense. I'm still learning how the math works (both mathematically and how to write it here), so if there's a better way to do this I'll accept any help (though, knowing how math is taught there very well may be a better way that I just haven't been taught yet).


TITLE: Error multiplying permutations in cycle notation
QUESTION [0 upvotes]: Can someone tell me where this calculation goes wrong?
I get (2 3 4)(1 2 3 4 5 6)^-1 = (1 6 5 2).
My book and Mathematica get (1 6 5 4).
I have read several explanations of how to multiply permutations in cycle notation and have
worked dozens of examples successfully, but I always get this one wrong.
(2 3 4)(1 2 3 4 5 6)^-1 = (2 3 4)(6 5 4 3 2 1) = (2 3 4)(1 6 5 4 3 2)
1 -> 6 then 6 is unchanged  giving  (1 6
6 -> 5 then 5 in unchanged  giving  (1 6 5
5 -> 4 then 4 -> 2          giving  (1 6 5 2
2 -> 1 then 1 is unchanged  completing the cycle  giving (1 6 5 2).

REPLY [1 votes]: It appears that you are multiplying permutations right-to-left, but your book (and Mathematica) are multiplying permutations left-to-right. Both conventions (left-to-right and right-to-left) are in common use, so it's important to know which one a particular author is using when reading.

REPLY [1 votes]: You are multiplying from right to left. Your book and Mathematica are multiplying left to right.


TITLE: Understanding equation for force acting on stones skipping over water
QUESTION [4 upvotes]: I think I have a decent conceptual understanding of the forces at work when stones are skipped over water.  My question pertains to this equation,
$$
F = C_L\rho U^2S\sin({\alpha + \beta})
$$
which appears without derivation in Water-skipping stones and spheres (Tadd Truscott, Jesse Belden and Randy Hurd, Physics Today, December 2014, page 70), where

$C_L$ is the coefficient of lift, given as 1/2 for a disk
$F$ is the force
$\rho$ is the density of the water
$U$ is the impact velocity
$S$ is the wetted area
$\alpha$ is instantaneous attack angle
$\beta$ is the instantaneous course angle

The article also contains a useful image.
I suppose my question comes down to the final sine factor.  I suspect deriving this equation comes somehow from the lift co-efficient formula:
$$
L = \frac12 \rho^2 v^2 A C_L.
$$
Here is my barrage of questions

Where does the sine factor come from?
Why doesn't the fact that the stone experiences different
densities above and below change the equation?
Why does an equation that deals with a single fluid apply to this
situation at the boundary of two fluid?

REPLY [1 votes]: 1) The $\sin$ term appears to be resolving the velocity of the water relative to the face of the disk. $U$ is the just the speed, it's necessary to determine what part of that velocity will produce force on the object.  It might help to visualize extreme cases, setting $\alpha$ and $\beta$ to 0, $\pi /2$ etc. For $\alpha = \beta =0$ you have a perfectly level stone sliding across the surface of the water (no lift). For $\alpha = 0$ and $\beta = \pi/2$ you have a level stone falling straight down (pure lift).
2/3) As @MonkeysUncle notes, the forces due to air are negligible in this case.  The aero/hydrodynamic forces scale linearly with the density of the fluids. So the forces due to air ($\rho = 1.27 \,~\text{kg/m^3}$) will be about 0.1 % as large as those due to water ($\rho = 1000\, ~\text{kg/m^3}$).


TITLE: contravariant and covariant vectors and their orthogonality in Euclidean space
QUESTION [3 upvotes]: I am reading this paper Sigma Coordinate - Contravariance and covariance and I understand how covariant and contravariant vectors are defined mathematically  Covariance and Contravariance and I had some questions regarding how the authors are using those definitions for testing orthogonality. The problem domain is in the Euclidean space and Cartesian axes. I have curvilinear coordinates and I can define  a set of covariant and contravariant basis vectors and they form a set of mutually orthonormal basis vectors defined by the Kronecker delta.
Now one of the axes is no longer orthogonal to the other two and this is the sigma coordinate as defined in that paper.

$\sigma_z$ = H. z-h/H-h where H is model top and h = h(x,y)

Is it always the case when you have a non orthgonal coordinate surface the basis vectors that are orthogonal to each other will transform in a covariant manner and the non orthogonal basis vector will transform in a contravariant manner ?
If not can someone explain what this text means

In a $\sigma$-coordinate, the
  horizontal covariant basis vectors and the vertical contravariant
  basis vectors vary in the horizontal and vertical,
  respectively, while the covariant and contravariant basis
  vectors are non-orthogonal when the height and slope of
  terrain do not equal zero

REPLY [2 votes]: "Contraction-orthogonality" of covariant and contravariant basis
Contravariant vectors or just "vectors" are defined as elements of the tangent space at a given point. In practice, they are defined with respect to a coordinate-vector basis $\mathbf{e}_{(i)}$, where $\mathbf{e}_{(i)}$ is the vector tangent to the $i$-th coordinate line. Then they are given, as per usual, as a linear combination of the basis vectors (Einstein summation assumed henceforth)
$$\mathbf{v} = v^i \mathbf{e}_{(i)}$$
Covariant vectors or "1-forms", on the other hand, are more abstract objects which are defined exclusively through their action on contravariant vectors. For instance, a 1-form acting on a (contravariant vector) will return a number
$$\mathbf{\alpha}(\mathbf{v}) = C,\,C \in \mathbb{R}$$
Another requirement on the 1-form $\alpha$ is that its action is linear, that is for any vectors $\mathbf{v},\,\mathbf{w}$ and any two constant $D$, $E$ $$\alpha(D \mathbf{v} + E \mathbf{w}) = D \alpha(\mathbf{v}) + E \alpha(\mathbf{w})$$
This actually means we can completely reconstruct its action from the components
$\alpha_i \equiv \alpha(\mathbf{e}_{(i)})$ because then thanks to the linearity (verify this yourself)
$$\alpha(\mathbf{v}) = \alpha_i v^i$$
Alternatively, you can define $\alpha_i$ as components with respect to a covariant basis
$\alpha = \alpha_i \epsilon^{(i)}$ where $\epsilon^{(i)}$ is defined by the property
$$\epsilon^{(i)}(\mathbf{e}_{(j)}) = \delta^i_j$$
That is, the "contraction-orthogonality" of covariant and contravariant bases has nothing to do with a geometrical definition of distance or angles (AKA the metric).

Raising and lowering indices
Now consider a space where we actually have a metric $g_{ij}$, abstractly we can define it as
$$\mathbf{g}(\mathbf{v},\mathbf{w})=C,\,C \in \mathbb{R}$$
where we again require linearity. Now consider the form $\kappa$ defined by
$\kappa(\mathbf{w}) \equiv \mathbf{g}(\mathbf{u},\mathbf{w})$
for some vector $\mathbf{u}$. $\kappa$ is a full-fledged form as defined above, its components can be shown to be
$$\kappa_i = g_{ij} u^j$$
physicist know this as "index lowering". We assume that the metric is non-degenerate which means that $u \leftrightarrow \kappa$ is a one-to-one relation and we can find an inverse $\mathbf{g}^{-1}$. The components of the inverse metric are usually denoted as $g^{ij}$ where $g_{ij} g^{jk} = \delta^i_k$ is a defining property. The "index-raising" from forms to vectors is then defined by
$$w^i = \beta_j g^{ij}$$
In fact, this operation is so common in metric geometry that physicists (especially relativists) simply say that it is "the same object with indices up or down", i.e.
$$\kappa_i = v^j g_{ij} \equiv v_i$$
and
$$w^i = \beta_j g^{ij} \equiv \beta^i$$

Non-orthogonal bases
We can take the contravariant basis vectors and check whether they are orthogonal by taking simply
$$\mathbf{g}(\mathbf{e}_{(i)},\mathbf{e}_{(j)}) =?$$
or the covariant basis
$$\mathbf{g}^{-1}(\mathbf{\epsilon}^{(i)},\mathbf{\epsilon}^{(j)}) =?$$
In this sense, covariant and contravariant basis vectors can be orthogonal or non-orthogonal.
I am slightly uncomfortable with the way the article above "mixes" the covariant and contravariant vectors together. Trying to assess whether $\mathbf{e}_{(i)}$ and $\epsilon^{(j)}$ are orthogonal does not make a lot of sense because they are simply different geometrical objects. (If you try to raise/lower an index on either of them via the metric and then using the metric to dot-product the result, you will get orthogonality trivially from definitory properties of the bases and the metric/inverse metric cited above. You can easily verify that yourself.)


TITLE: Sequence such that $a_{k-1}+a_k=a_{k+1}$ and $a_k>0$ for all $k\in\mathbb{Z}$
QUESTION [1 upvotes]: Does there exist a bi-infinite sequence (for every integer $n$ there exist an $a_n$ item in the sequence) with positive real items, such that for every integer $k$, $a_{k-1}+a_k=a_{k+1}$?
I know it is easy if every item is an integer. But we only know that every item is positive and real. So I believe there doesn't exist. How can I prove it?

REPLY [3 votes]: There is such a sequence: $$a_n=a\,\varphi^n$$ with some real $a>0$ for every integer $n$, where $$\varphi=\frac{1+\sqrt{5}}2,$$ because $\varphi^2=\varphi+1$, and multiplying by $a\,\varphi^{k-1}$, you immediately get $a_{k+1}=a_{k-1}+a_k$.

REPLY [3 votes]: By the general theory of linear recurrences, a sequence satisfies the recurrence $a_{k-1}+a_k=a_{k+1}$ iff it is of the form $a_n=bs^n+ct^n$ for some $b,c\in\mathbb{R}$, where $s=\frac{1+\sqrt{5}}{2}$ and $t=\frac{1-\sqrt{5}}{2}$ are the solutions of the equation $x^2=x+1$.  So your question is just whether there exist $b,c\in\mathbb{R}$ such that $bs^n+ct^n>0$ for all $n\in\mathbb{Z}$.
The answer is yes: if $c=0$ and $b>0$, then the sequence $a_n=bs^n$ is always positive, since $s$ is positive.
(On the other hand, these are the only examples.  If $c\neq 0$, then when $n$ is very negative, $s^n$ is close to $0$ since $s>1$, while $t^n$ is very large and alternates in sign based on the parity of $n$ since $-1<t<0$.  So, choosing $n$ to be sufficiently negative and of the correct parity according to the sign of $c$, $bs^n+ct^n$ will be negative.)

REPLY [2 votes]: If you choose $x$ as the positive root of $x^2-x-1=0$ then $a_n=x^n$ will do since $x^{n+1}=x^n+x^{n-1}$ and the terms are positive even for negative exponent.


TITLE: How would I go about solving this probability question?
QUESTION [0 upvotes]: I am currently in year 10 studying GCSE higher maths. My once issue with maths is probability. I have an exam tomorrow and am currently revising by going through past papers, I saw this question and wasn't sure how I'd solve it. Does anyone have an idea?
A school has 400 boys and 500 girls.
The probability that a boy is vegetarian is 0.1
The probability that a girl is vegetarian is 0.2
Estimate the total number of vegetarians in the school.

REPLY [1 votes]: Estimated number of boy vegetarians is $400 \cdot 0.1=40$.
Estimated number of girl vegetarians is $500 \cdot 0.2=100$.
Both sums up to $140$.


TITLE: Methods to find the value of $\int_0^{2\pi} \frac{dt}{z+e^{it}}$
QUESTION [1 upvotes]: Given $z \in \mathbb{C}$, with $|z|\neq1$, what are the classic methods to determine the value of:
$$\int_0^{2\pi} \dfrac{dt}{z+e^{it}}$$
I thought of rewriting the integral with only real integrands but it seems very tedious. I am not asking necessarily for an answer but I would like to know how can I approach this kind of integral in order to be quite efficient.
I never saw contour integration, so I am not going to use it in any case. But if you have a solution that involves this concept, I would be glad to read it anyway.

REPLY [0 votes]: Consider the mean value theorem for harmonic functions:
$$f\left( z \right)=\frac{1}{2\pi }\int\limits_{0}^{2\pi }{f\left( z+{{e}^{it}} \right)dt}\Rightarrow \int\limits_{0}^{2\pi }{\frac{1}{z+{{e}^{it}}}dt}=\frac{2\pi }{z}$$
This is true for all z where f is analytic in a unit circle centred at z. For example this is true for all z with $\operatorname{Re}\left( z \right)>1$ etc.


TITLE: Direction of Induced Electric Field in a coaxial cable?
QUESTION [0 upvotes]: I was working through Griffith's book when I came across this problem:
An alternating current, of the form $I(t) = I_0cos(\omega t) $ flows down a long straight wire, and returns (loops back) along a coaxial cylindrical conducting tube of radius $R$.
What is the direction of the induced electric field? I think it should be radial by symmetry, but the answer seems to indicate that it is axial; and I'm having trouble working out the reasoning behind this.

REPLY [1 votes]: How about this:
Think about a loop around the central wire, but inside the outer conductor, with its surface defining a plane perpendicular to the wire. Ampere's law tells us the induced magnetic field curls around the central wire. [Even if there were a time-dependent radial E-field it would not produce any displacement current through the loop.]
Having established that there must be a time-dependent B-field in the $\phi$ direction (cylindrical polar coordinates with the z-axis along the wire), then from Faraday's law, the curl of the E-field must also be in the $\phi$ direction. But if the curl of E is in the $\phi$ direction then the E-field itself must be in the z-direction along the axis of the wire.


TITLE: Nakano semipositivity
QUESTION [2 upvotes]: Let $X$ be a compact Kaehler manifold.
What is a good, possibly algebraic-geometric, way to think to Nakano semipositivity of holomorphic vector bundles on $X$?
Is the trivial line bundle $\mathcal{O}_X$ Nakano semi-positive as a vector bundle?

REPLY [5 votes]: I would say more properly that nowadays it is not known any satisfactory algebraic description or characterization of the concept of Nakano's positivity for a hermitian vector bundle.
I would like also to add some precisions to Sándor's answer.
First, the positivity in the sense of Nakano is a good notion to obtain vanishing theorems for vector bundles. For instance, we have the following result due to Nakano
Theorem (Nakano, 1955). Let $X$ be a compact connected Kähler manifold of dimension $n$ and $E\to X$ a hermitian vector bundle. Then

if $E\ge_{\text{Nak}}0$, strictly in one point, $H^{n,q}(X,E)=0$, for $q\ge 1$;
if $E\le_{\text{Nak}}0$, strictly in one point, $H^{p,0}(X,E)=0$, for $p<n$.

On the other hand, Nakano's positivity is not well-behaved with respect to taking duals: we have that $E$ is Griffiths positive if and only if $E^*$ is Griffiths negative, but if we take $H\to\mathbb P^n$ to be the vector bundle of rank $n$ defined by
$$
0\to\mathcal O(-1)\to\underline{\mathbb C}^{n+1}\to H\to 0,
$$
where $\underline{\mathbb C}^{n+1}$ si the trivial vector bundle over $\mathbb P^n$ with fiber $\mathbb C^{n+1}$, then $H$ is Griffiths (semi)positive and $H^*$ is Nakano (semi)negative but $H$ is neither Nakano (semi)positive nor Nakano (semi)negative.
If we look to short exact sequences of vector bundles
$$
0\to S\to E\to Q\to 0,
$$
then the Nakano's negativity of $E$ implies the Nakano's negativity of $S$, but nothing can be said about the Nakano's positivity of $Q$ when $E$ is Nakano positive (the desired property holds if we look instead to Griffiths' positivity).
Of course Nakano's positivity implies the Griffiths' one; the following "partial converse" is due to Demailly and Skoda:
Theorem (Demailly-Skoda, 1979). For any hermitian vector bundle $E$, $E>_{\text{Grif}}0$ implies $E\otimes\det E>_{\text{Nak}}0$.


TITLE: Black Holes and Diagrams of Different Coordinate Systems
QUESTION [1 upvotes]: In General Relativity by Woodhouse there are the three following diagrams in Chapter 9 about Black Holes. Despite a (very brief) description of these diagrams in the book itself, I am struggling to understand what they exactly correspond to? Does anyone have good way of looking at how these diagrams help convey a) the properties of the particular coordinate system and b) a understanding of how black holes work in the particular coordinate system being looked at.

REPLY [3 votes]: The radial null geodesics for the Schwarzschild metric have the form
$$
t \pm [r + 2 m \ln (r - 2m)] = k \tag{1}
$$
where $k$ is a constant. This is a plot for different values of $k$

The plots you showed are just an attempt to represent these geodesics in three spatial coordinates. Unfortunately that cannot be done trivially, so instead Woodhouse decided to ignore one of the coordinates and draw Eq. (1) in the other two. You can do that by setting $x = r\cos\phi$ and $y = r \sin\phi$ for $0\leq \phi \leq 2\pi$. Or equivalently by rotating the curves in the figure above around the $t$ axis. This is an example for $k = 1$

This is just a fancy extension of the first figure above, but it is completely unnecessary, since the problem has spherical symmetry, and adding an extra coordinate just adds to the noise without any benefit.


TITLE: Relation between $H^i_I(-)$ and $H^i_J(-)$ when $I\subset J$
QUESTION [1 upvotes]: What is the relation between $H^i_I(-)$ and $H^i_J(-)$ (cohomological functors) when $I\subset J$ are ideals of a (local) noetherian ring?

REPLY [0 votes]: There's a map between them, and these do fit into a long exact sequence together.  This is explained in the book on local cohomology by Hartshorne, see Lemma 1.8:  You can even download this book if your institution has access...
I will sketch it briefly.
Let $V(I) = Y \supseteq Z = V(J)$ and set $W = V(I) \setminus V(J) = Y \setminus Z$, this $W$ is only locally closed in $\text{Spec} R$.
We define $H^i_W(\bullet)$ to be the right derived functors of $\Gamma_W(\bullet)$.  Here $\Gamma_W(M)$ for any $R$-module $M$ is defined to be the set of elements of $M$ which are zero in $M_{p}$ for all $p \in (\text{Spec }R) \setminus W$.
With this notation, for any $R$-module $M$ we have a long exact sequence
$$
... \to H^i_Z(M) \to H^i_Y(M) \to H^i_W(M) \to H^{i+1}_Z(M) \to ...
$$
Note $H^i_Z(M) = H^i_J(M)$ and $H^i_Y(M) = H^i_I(M)$.
I doubt this gives you much information unless $Y$ and $Z$ have some special relationship.
There are related things you can do too.  If for example $Y = Z \cup X$ where $X$ is some other closed subset of $\text{Spec }R$, there's another long exact sequence but this is a special case.  Can you tell me what $Y$ and $Z$ are in your case?


TITLE: A question about diagonalizable linear operator
QUESTION [1 upvotes]: Suppose $T$ is a diagonalizable linear operator on a finite dimensional vector space $V$. Prove $V$ is T-cyclic subspace of itself iff every characteristic subspace of it is one-dimensional.

It means there's a $v\in V$ such that $V=\operatorname{span}\langle v,T(v),T^2(v),\dots,T^k(v)\rangle$. How should I proceed?

REPLY [2 votes]: Write every $T^mv$ in the diagonal basis. This gives a matrix of coefficients. The vector $v$ is cyclic for $T$ if and only if this matrix is non-singular. The form of the matrix should ring a bell.


TITLE: Why are light waves sinusoidal?
QUESTION [0 upvotes]: We know that light is an electromagnetic wave which follows the wave equation. We write the wave as
$$f(x, t) = A\sin(kx - \omega t + \phi ),$$
which is sinusoidal. So my question is why can't it be a square wave or any other wave form which follows the wave equation?

REPLY [3 votes]: Who says that it can't? Monochromatic light is sinusoidal in time (but it can be non-sinusoidal in space, like e.g. Bessel waves in a cylindrical waveguide, or inverse-square decays for spherical waves), simply because that's how we define monochromaticity, but not all light is monochromatic. Add monochromatic beams together, each with a different colour, and you'll get non-sinusoidal waveforms; add enough of them and you'll be able to reproduce any arbitrary temporal waveform.
Light waveforms come in all shapes and sizes. In introductory texts we focus on sinusoidal solutions because they are easy to analyze, and because they are useful tools to study more complicated situations, but that is all that's going on.


text:
\section{Numerical examples}

In this part, the behavior of the proposed reconstruction method is illustrated for the approximation of the solutions of a parameter dependent transport problem and the wave equation.

\subsection{Scalar transport equation}

Consider a one-dimensional domain $\Omega = (-L,L)$, with $L=10$m, in which the scalar transport equation \eqref{eq:syscons} with a linear flux function holds, supplemented with periodic boundary conditions and the following initial condition
$$
u^0(x)=\left\{\begin{split}
& u_L \quad \text{if } - \frac{L}{3}\leq x \leq \frac{L}{3}, \\
& u_H \quad \text{otherwise,}
\end{split}\right.
$$
where $u_L = -1$ and $u_H = 1$ denote initial low and high values. The wavespeed $a(\mu)$ depends on the parameter $\mu \in [0,1]$ through the affine function $a(\mu)=\alpha \mu + \beta$. Here $\alpha, \beta$ are two constants whose values are here set at $5$ and $2$ respectively. \\

In what follows, we perform some comparison between the reconstructed approximation $\Vphi_i^k(\mu)$ provided by the RTA method, from given snapshots $\Vu^k(\mu_i)$ computed with the upwind scheme, to approximate the FV solution $\Vu^k(\mu)$ for a target value of the parameter $\mu \in \Pc$. The mesh consists here of $N=250$ cells, and the maximum CFL number is set at $0.8$ for $\mu=1$. The RTA solution is here reconstructed from a snapshot obtained for $\mu_i=0.4$. Figure \ref{transportSolution} shows a comparison between RTA and FV approximation computed for a parameter value $\mu=0.8$ at different times.  It can be observed  that the two approximations coincide. Moreover, the RTA solution does not exhibit any oscillating behavior, nor tends to depart more from the FV reference solution with time.
\begin{figure}[H]
\subfigure[$t=7.22 \times 10^{-1}$ s.]{\label{transport1}
\includegraphics[width=0.33\textwidth]{figures/transport1.pdf}
}
\subfigure[$t=2.16 \times 10^{-1}$ s.]{\label{transport1}
\includegraphics[width=0.33\textwidth]{figures/transport2.pdf}
}
\subfigure[$t=8.14 \times 10^{-1}$ s.]{\label{transport1}
\includegraphics[width=0.33\textwidth]{figures/transport3.pdf}
}
\caption{Comparison of RTA approximation computed from a snapshot obtained $\mu_i=0.4$ with the FV approximation computed for $\mu=0.8$ at different times. }
\label{transportSolution}
\end{figure}

To study the convergence of the RTA,  let us consider both absolute and relative error in discrete $L^1$ norm between $\Vphi_i^k(\mu)$ and $\Vu^k(\mu) $, at time $t^k$, given respectively by
$$
e_a^k(\mu, \mu_i)= \Delta x \sum_{j=1}^N |\phi_{i,j}^k(\mu) - u_j^k(\mu) |  \text{ and }  e_r^k(\mu, \mu_i) =  \dfrac{ \sum_{j=1}^N |\phi_{i,j}^k(\mu) - u_j^k(\mu) |  }{\sum_{j=1}^N |u_{j}^k(\mu)|}.$$
Figure \ref{L1convCurves} shows both absolute and relative $L^1$ errors computed for different instances of the parameter $\mu$. Here, the reconstructed approximation, provided by the RTA method, is computed from a snapshot given for $\mu_i=0.65$. In accordance with theoretical results of Section \ref{sec:error}, the method converges since the approximation error decreases  with $\Delta x$. Moreover, the observed convergence rates are of the order of $1/2$ corresponding to those of the FV scheme for the approximation of discontinuous solutions, see \cite[Section 8.7]{Leveque2002}.  In that particular case, the projection error arising in Equation \eqref{eq:erreur_approximation} is negligible compared to the one of the FV scheme. The different constants and rates observed at the final time depend on $|\mu-\mu_i|$ as well as on the fractional part $\{k(\nu - \nu_i)\}$. This last observation motivates the interest of a selective procedure, as discussed in Remark  \ref{rk:dico}, for selecting the best snapshot in a pre-computed dictionary to minimize the approximation error.

\begin{figure}[H]
\begin{center}
\includegraphics[width=0.8\textwidth]{figures/L1convCurves.pdf}
\end{center}
\caption{Convergence curves of $L^1$ absolute and relative errors computed for different values of the parameter $\mu$.}
\label{L1convCurves}
\end{figure}
Figures \ref{timeL1convCurvesMui} and \ref{timeL1convCurvesMeshes} show time evolution of the $L^1$ relative error superposed for different mesh sizes and  values of the parameter $\mu$. First, it can be observed on the two figures that the error remains globally of the same order of magnitude in time for a given mesh and parameter value, and do not increase exponentially. Indeed, contrary to time stepping algorithms, the proposed RTA method only requires the snapshots $\Vu^k(\mu_i)$ at current time $t^k$. In consequence, the approximation errors do not accumulate with time iteration. Second, it can be seen in Figure \ref{timeL1convCurvesMui} that error curves associated with the different instances of the parameter may cross in time. One possible explication of this observation is that the error is related to the fractional part $\{k(\nu-\nu_i)\}$ which depends on both $\mu, \mu_i$ and $k$. In particular, when the snapshots are aligned with the mesh at the instant $t^k$ one could expect a smallest error.

Finally, as the mesh is refined, Figure \ref{timeL1convCurvesMeshes} shows that the error decreases monotonically as observed in Figure \ref{L1convCurves}.

\begin{figure}[H]
\begin{center}
\includegraphics[width=1.0\textwidth]{figures/L1timeRelErrorMeshesMui.pdf}
\end{center}
\caption{Time evolution of the $L^1$ relative error computed for different meshes and superposed for different values of the parameter $\mu$.}
\label{timeL1convCurvesMui}
\end{figure}
\begin{figure}[H]
\begin{center}
\includegraphics[width=1.0\textwidth]{figures/L1timeRelErrorMuiMeshes.pdf}
\end{center}
\caption{Time evolution of the $L^1$ relative error computed for different instances of the parameter $\mu$, superposed for different  meshes.}
\label{timeL1convCurvesMeshes}
\end{figure}

\subsection{System of linear conservation laws}

We conclude this section, with some numerical experiment on multiple transport parameter-dependent problem.

\subsubsection{Linear elastodynamics}

Consider a bar, whose elastodynamic response in the isothermal and linearized geometrical framework is governed by the system of conservation laws \eqref{eq:syscons}, particularized with the following conserved variables $u : \Omega \times I \to \RR^2$ and flux $f : \RR^2 \to \RR^2$ given by
$$
u = \left(\begin{matrix}
 \sigma \\
 v
\end{matrix} \right) \quad \text{ and } \quad f(u) = \left( \begin{matrix}
 -E v \\
 - \frac{\sigma}{\rho}
\end{matrix}
 \right),
$$
where $\sigma : \Omega \times I \to \RR$ and $v : \Omega \times I \to \RR$ denote the Cauchy stress and the velocity respectively.  Moreover, $E$ and $\rho$ are two constants, corresponding to the Young modulus and the mass density respectively. This system of equations is also supplemented with periodic boundary conditions and given initial condition $u^0$. The above system can be set into a characteristic form \cite{Toro2013} which is given through the decoupled system of two equations
\begin{equation}
\label{decouple}
\begin{array}{rcl}
\dfrac{\partial w_1}{\partial t} + c \dfrac{\partial w_1}{\partial x} &=& 0, \\[0.2cm]
\dfrac{\partial w_2}{\partial t} -c \dfrac{\partial w_2}{\partial x} &=&0,
\end{array}
 \qquad \text{ on } \Omega \times I.
\end{equation}
where $c=\sqrt{E/\rho}$ is the elastic celerity of the bar. The vector $w = (w_1,w_2)^T$  contains the characteristic variables $w_l : \Omega \times I \to \RR$ which satisfy $u = R w$ with

 $R \in \RR^{2 \times 2}$ the matrix of right eigenvectors of the jacobian matrix of the flux $f$ defined as
\begin{equation}\label{eigenvectors}
R = \left(\begin{matrix}
\rho c & - \rho c \\
1 & 1
\end{matrix}
\right).
\end{equation}

In what follows, the elastic celerity $c(\mu)=\sqrt{E(\mu)/\rho}$ depends on the parameter $\mu \in \Pc$, through the Young modulus $E(\mu)$.
We consider the problem of computing an approximation of the FV solution of this elastodynamic problem for a target value $\mu$. To that goal, the RTA method is considered for approximating the FV solution of each independent characteristic equation. First, at each time $t^k$, provided snapshots $\mathbf{u}^k(\mu_i) \in \RR^N \times \RR^2$, the corresponding FV approximations of characteristic quantities $\mathbf{w}^k(\mu_i)  \in \RR^N \times \RR^2$ are  computed as
\begin{equation}
\mathbf{w}^k(\mu_i) = \mathbf{u}^k(\mu_i) R^{-T}.
\end{equation}
Next, the reconstructed approximations computed by the RTA method are
\begin{equation}
{\Vphi}_{i,l}^k (\mu)= {\cal K}(k (\nu-\nu_i)) \boldsymbol{w}_{l}^k(\mu_i), \quad l=1,2
\end{equation}
where $\boldsymbol{w}_{l}^k(\mu_i) \in \RR^N$ are the columns of $\mathbf{w}^k(\mu_i)$. Here ${\Vphi}_{l,i}^k (\mu) \in \RR^N$ stands for the RTA reconstruction from $\boldsymbol{w}_{l}^k(\mu_i)$. Finally, the numerical approximation of the conservative variables $u$ for the value $\mu$ are obtained by recombining the reconstructed approximations of characteristic variables ${\Vphi}_{i,l}^k (\mu), l=1,2$, using the matrix $R$
\begin{equation}
\label{eq:rebuilt}
\VPhi_{i,l}^k (\mu) = \sum_{m=1}^2 R_{lm} {\Vphi}_{i,m}^k (\mu)
\end{equation}
where $\VPhi_{i,l}^k (\mu) \in \RR^N$ consists of the approximations for the translated stresses ($l=1$) and for the velocity ($l=2$) respectively.

\subsubsection{Results}

For the following simulations, the Young modulus $E(\mu)$ depends on $\mu\in [0,1]$ through $E(\mu)=c_0 \mu + c_1$, with $c_0,c_1$ being two constants set at $19\times 10^{10}$ Pa and $10^{11}$ Pa respectively. The mass density is set at $7800$ kg.m$^{-3}$. The bar is initially free of any stresses $\sigma^0 =0$. Riemann-type initial conditions are prescribed on the velocity field so that  $v^0=1$m.s$^{-1}$ in the first half of the medium $x \in [-L,0)$, and $v^0=0$ in the second half $x \in (0,L]$, so that compression first occurs at the middle of the computational domain.

Figure \ref{w_elastoSolution} shows some superposed plots of the approximations of the characteristic variables  $w_l(\mu) = \frac 12 (\mp \frac{\sigma (\mu) }{\rho c(\mu) } + v(\mu))$, $l=1,2$ computed with the RTA  method and the FV scheme for $\mu=0.8$, as well as the snapshot consisting of a FV approximation obtained with $\mu=0.05$. The mesh consists of $250$ cells, and the maximum $CFL$ number is set at $0.8$ for $\mu=1$. It can be observed a very good agreement on both characteristic variables between RTA and FV approximation for the instance value $\mu=0.8$. As the time increases, the space shift between the snapshot and the RTA solution also significantly increases, showing that the CFL-like condition $\Delta a(\mu,\mu_i)t^k \leq \Delta x$ of remark \ref{CFLlike} is not satisfied.\\

\begin{figure}[H]
\begin{center}
\subfigure[$t=1.29 \times 10^{-3}$ s.]{\label{w_elasto1}
\includegraphics[height=0.3\textheight]{figures/w_elasto1.pdf}
}
\subfigure[$t=3.88 \times 10^{-3}$ s.]{\label{w_elasto2}
\includegraphics[width=0.3\textheight]{figures/w_elasto2.pdf}
} \\
\subfigure[$t=9.06 \times 10^{-3}$ s.]{\label{w_elasto3}
\includegraphics[width=0.3\textheight]{figures/w_elasto3.pdf}
}
\subfigure[$t=1.29 \times 10^{-2}$ s.]{\label{w_elasto4}
\includegraphics[width=0.3\textheight]{figures/w_elasto4.pdf}
}
\end{center}
\caption{Comparison of the characteristic variables $w_l(\mu)$, $l=1,2$ : approximations computed with RTA, from a snapshot obtained for $\mu=0.05$, and FV for $\mu=0.8$ at different times. }
\label{w_elastoSolution}
\end{figure}

Finally, Figure \ref{elastoSolution} shows the rebuilt conserved variables obtained with RTA and FV approximations computed for the parameter value $\mu=0.8$ at different times using Equation \eqref{eq:rebuilt}. The two solutions are again in very good agreement for any times.

\begin{figure}[H]
\begin{center}
\subfigure[$t=1.29 \times 10^{-3}$ s.]{\label{elasto1}
\includegraphics[height=0.3\textheight]{figures/elasto1.pdf}
}
\subfigure[$t=3.88 \times 10^{-3}$ s.]{\label{elasto2}
\includegraphics[width=0.3\textheight]{figures/elasto2.pdf}
} \\
\subfigure[$t=9.06 \times 10^{-3}$ s.]{\label{elasto3}
\includegraphics[width=0.3\textheight]{figures/elasto3.pdf}
}
\subfigure[$t=1.29 \times 10^{-2}$ s.]{\label{elasto4}
\includegraphics[width=0.3\textheight]{figures/elasto4.pdf}
}
\end{center}
\caption{Comparison of stress and velocity fields : approximations computed with RTA, from a snapshot obtained for $\mu=0.05$, and FV for $\mu=0.8$ at different times. }
\label{elastoSolution}
\end{figure}

config: arxiv


TITLE: A Graph-Theory Related Question
QUESTION [9 upvotes]: Let $n$ be a positive integer and partition a grid of $4n$ by $4n$ unit squares into $4n^2$ squares of sidelength $2$. (The squares with sidelength $2$ have all of their sides on the gridlines of the $4n$ by $4n$ grid.) What's the minimum number of unit squares that can be shaded such that every square of sidelength $2$ has at least one shaded square, and there exists a path between any two shaded squares going from shaded squares to adjacent shaded squares? (Two squares are adjacent of they share a side.)
I think the answer is $6n^2-2$. I got it by partitioning the $4n$ by $4n$ unit squares into $n^2$ squares of sidelength $4$, shading in the four center unit squares of each sidelength $4$ square (so that every square with sidelength $2$ has at least one shaded square), and connecting the shaded squares to another. There are $4n^2$ center unit squares, and a connection between any two groups of center squares requires two squares. There are $n^2$ groups of center squares, so for the shaded squares to be connected, we need at least $n^2-1$ connections. (Similar to how a connected graph on $n$ vertices needs at least $n-1$ edges.) Each connection is two squares, so we need to shade an additional $2(n^2-1)$ squares. Adding this to $4n^2$ gives $6n^2-2$.
This is by no means a proof. There are of course valid configurations in which some square with sidelength $4$ does not have the center $4$ squares shaded in. Could someone help me prove that $6n^2-2$ is the minimum? Thanks.

REPLY [2 votes]: Let $p$ be a path consisting of $m$ shaded unit squares (where every two adjacent shaded squares share a side). Define a binary string $B_p=b_0b_1b_2\dots b_m$, where $b_0b_1=10$ and for $i>1$, $b_i=1$ iff the $i$th square in $p$ belongs to a previously unseen 2x2 square. Clearly, the number of ones in $B_p$ equals the number of 2x2 squares visited by $p$.
It can be shown that every substring of length 6 of $B_p$ contains at most 4 ones. Furthermore, the maximum number of ones in $B_p$ is:

if $m\equiv 0\pmod{6}$, then $\frac{4m+6}6$ ones
if $m\equiv 1\pmod{6}$, then $\frac{4m+2}6$ ones
if $m\equiv 2\pmod{6}$, then $\frac{4m+4}6$ ones
if $m\equiv 3\pmod{6}$, then $\frac{4m+6}6$ ones
if $m\equiv 4\pmod{6}$, then $\frac{4m+8}6$ ones
if $m\equiv 5\pmod{6}$, then $\frac{4m+4}6$ ones

To visit $4n^2$ 2x2 squares, path $p$ must contain $m\geq \frac{6\cdot 4n^2 - 8}{4}=6n^2-2$ shaded squares.
It remains to consider a case when the shaded squares form not a path but a tree, which I believe can be done similarly.


text:
\begin{document}

\begin{abstract}

Suppose that a finitely generated group~$G$ acts by isometries on a $\delta$-hyperbolic space, with at least one element acting loxodromically. Suppose that the elements of~$G$ have a normal form such that the language of normal forms can be recognized by a finite state automaton. Suppose also that a certain compatibility condition linking the automatic and the $\delta$-hyperbolic structures is satisfied. Then we prove that in the ``ball'' consisting of elements of~$G$ whose normal form is of length at most~$l$, the proportion of  elements which act loxodromically is bounded away from zero, as $l$ tends to infinity.
We present several applications of this result, including the genericity of pseudo-Anosov braids.
\end{abstract}

\maketitle

\section{Introduction}

For several decades, it was an unproven, but widely believed slogan that ``generic elements of the mapping class groups of surfaces are pseudo-Anosov''. Here the word ``generic'' admits several different interpretations. For one of the possible interpretations, this slogan has recently been proven in a very satisfactory way.
Indeed, A.~Sisto~\cite{SistoGeneric}, inspired by previous work of J.~Maher \cite{Maher}, proved that the element obtained by a long random walk in the Cayley graph of the mapping class group of a surface tends to be pseudo-Anosov, with a probability which tends to~$1$ exponentially quickly as the length of the walk tends to infinity. (See also~\cite{Rivin} for a completely different approach.)
Actually, Sisto works in a far more general context: if a finitely generated, non-elementary group acts on a $\delta$-hyperbolic space, then the probability that the element obtained by a random walk in the group acts non-loxodromically

decays exponentially quickly with the length of the walk. In the special case of the mapping class group acting on the curve complex of the surface, this implies the original slogan.

In the present paper, we use a different notion of genericity. For us, a generic element is not obtained by a long random walk, but it is picked randomly with uniform probability among the elements in a large ``ball'' centered on the identity element in the Cayley graph of the group. Almost nothing was known about the genericity (in this sense) of pseudo-Anosov elements until the paper \cite{CarusoGeneric1} by S.~Caruso.

Caruso's result states that in the braid group~$B_n$, equipped with Garside's generators, the proportion of elements in the ball of radius~$l>1$ in the Cayley graph which are \emph{rigid} and pseudo-Anosov is bounded below by a strictly positive constant (independently of~$l$). The word ``rigid'' will be defined below -- for the moment we just point out that the proportion of rigid elements does definitely \emph{not} tend to~$1$ as $l$~tends to infinity.

In the present paper we generalize Caruso's result to a much larger framework. Here is a rough statement of our main result -- for a detailed and more general statement see Theorem~\ref{T:main} and Proposition~\ref{P:rigid}.
\smallskip

{\bf Theorem} \ \,{\sl Consider a finitely generated group~$G$ which acts on a $\delta$-hyperbolic space~$X$, with at least one element acting loxodromically. Suppose that~$G$ satisfies a certain weak automaticity condition, and also a certain compatibility condition linking the automatic and the $\delta$-hyperbolic structures. Then, among the elements of~$G$ whose automatic normal form is of length at most~$l$, the proportion of those which are rigid and act loxodromically is bounded below by a positive constant. Moreover, these rigid loxodromic elements have the property that their axis in~$X$ passes uniformly close to a pre-defined base point of~$X$.}
\smallskip

We present several applications of this result.
\marg{Referee: The author should also state explicitly whether or not the results
hold for Gromov hyperbolic groups, and compare and contrast his
approach with that of Calegari and Fujiwara (for example in "Combable
functions, quasimorphisms, and the central limit theorem" and "Stable
commutator length in word hyperbolic groups") who also make use of
automatic structures on groups.}
Firstly, we show that a positive proportion of elements of~$\mathrm{PSL}(2,\mathbb Z)$ act on the Farey graph in a loxodromic fashion -- this is already well known, but a nice illustration of our proof techniques.
Secondly, we show that
the above result holds for word-hyperbolic groups, acting on their own Cayley graphs.
Thirdly, we explain why there is hope that Theorem~\ref{T:main} can be applied in the realm of relatively hyperbolic groups, acting on their coned-off Cayley graphs.
Fourthly, we study the action of the braid group~$B_n$ on the so-called  ``additional length complex''. We prove that generic elements act in a loxodromic manner, and hence are pseudo-Anosov. We also re-prove Caruso's result.
Finally, we look at the fundamental groups of compact, non-positively curved cubical complexes and their action on the associated contact graphs. We prove that, under mild hypotheses, a positive proportion of elements acts loxodromically.

\section{Statement of the main result}

Throughout this paper, we will be interested in the properties of generic elements of a monoid~$G$. We always suppose that each element $g$ of~$G$ has a preferred representative word $g=g_1\cdot\ldots\cdot g_k$, called the \emph{normal form} of the element. The letters $g_i$ must belong to some finite set~$\mathcal S$ of arrows of a category~$\hat G$ which contains the monoid~$G$ as a sub-category: $G\subset \hat G$. (We recall that a monoid is a category with only one object.)

We also suppose that the language of normal forms of elements of~$G$ is recognized by a deterministic finite state automaton (FSA).
We recall briefly what this means: we have a finite graph, whose vertices are called the \emph{states} of the automaton, and whose edges are oriented and labelled by elements of~$\mathcal S$. From each state there is exactly one exiting edge for every element of~$\mathcal S$.
There is a unique \emph{start state} -- we shall assume that the start state is not the target of any arrow. There's also a unique \emph{fail state} -- all edges exiting the fail state immediately loop back to it.

Some of the states (possibly all except the fail state) are labelled as \emph{accept states}.
A word over the alphabet~$\mathcal S$ is \emph{recognized} or \emph{accepted} by the automaton if the path in the automaton beginning at the start state and following the edge labels of the word ends in an accept state.
For an introduction to the theory of finite state automata, the reader can consult \cite[Chapter~1]{ECHLPT} or~\cite{NeumannShapiro}.

\begin{remark}
(1) For many examples we are interested in,

the equality $\hat G=G$ holds. Moreover, often $G$ and $\hat G$ are actually \emph{groups}.
In that case, the normal form is simply a unique preferred writing of each element of the group~$G$ as a product of the generators $\mathcal S$ of~$G$. However, our more general setup is often useful, and comes at no extra cost.

(2) It may happen that there are pairs of elements $g_1, g_2$ of $\mathcal S$ such that $g_1g_2$ is not well-defined in~$\hat G$ -- this occurs if the category~$\hat G$ has more than one object and if the target object of~$g_1$ does not coincide with the source object of~$g_2$.  However, such a string $g_1g_2$ cannot appear in any word recognized by our FSA --  it is necessarily sent to the fail state.
\end{remark}

We say a word~$w$ over the alphabet~$\mathcal S$ is \emph{rigid} if the word $w^n$ (the word repeated $n$ times) is accepted by the automaton for all positive integers~$n$.
For instance, this is the case if the words $w$ and $w^2$ are both accepted, and if the paths traced out in the automaton by the two words end in the same state. We say an element $g$ of~$G$ is \emph{rigid} if the normal form word representing it is rigid, i.e.\ if the normal form of~$g^n$ is equal to the normal form of~$g$, repeated $n$~times. In the past, rigid elements have only been defined for Garside groups \cite{BGGMrigid}, but the preceding definition is just an obvious generalization.

If $A$ is the transition matrix of the automaton (ignoring the start- and fail state), then the $(i,j)$th entry of $A^l$ counts the number of words of length~$l$ starting at the $i$th and ending at the $j$th state. This makes it possible to use Perron-Frobenius theory to asymptotically count words~\cite{BrouwerHaemers,Varga}.

We say a finite state automaton is \emph{recurrent} if there is some integer~$l$ such that there is a path of length exactly~$l$ from from any state (other than the start state or fail state) to itself and to any other of those states. In terms of matrices, this means that $A^l$ is a matrix with all entries strictly positive -- this property is very useful in Perron-Frobenius theory.
The automata which we are interested in in practice (related to mapping class groups, for instance) are unfortunately not always recurrent; nevertheless the reader should keep the recurrent case in mind, because it is simpler while already containing the key of the argument.

For the purposes of this paper we introduce another notation (which is unnecessary if the automaton under consideration is recurrent). We consider the set of states which can be reached from all non-fail states of the automaton. This set of states, together with the edges connecting them, will be called the \emph{accessible sub-automaton}, and its states the \emph{accessible states}.

Note that the accessible sub-automaton may be empty, but when it is not, then paths can enter, but never leave it.
We shall say a FSA is \emph{dominated} by its accessible sub-automaton if the sub-automaton is non-empty, recurrent,
and if the exponential growth rate of the number of words readable in its accessible sub-automaton is strictly larger than that of the original automaton, with the sub-automaton removed.

\begin{definition}
We say that $G$~satisfies the \emph{automatic normal form hypothesis} if every element of~$G$ has a unique preferred word over the alphabet~$\mathcal S$ representing it, and if the language of preferred representatives (normal forms) is recognized by a deterministic finite state automaton (FSA) with the following properties~:
\begin{itemize}
\item the automaton must be dominated by its accessible sub-automaton, and
\item there is at least one word $w_{\rm rigid}$ such that both $w_{\rm rigid}$ and $w_{\rm rigid}^2$ are accepted by the automaton, where the paths traced out in the automaton by the two words both end in the same accept state~$E$. Moreover, this state~$E$ has to lie in the accessible sub-automaton.
\end{itemize}
\end{definition}

Note that the automatic normal form hypothesis does not require any kind of the fellow traveller conditions familiar from automatic or combable groups. It is really a fairly mild hypothesis, as the following examples illustrate.

\begin{example}\label{E:RecurrentANFH}
The automatic normal form hypothesis is satisfied for instance if the language of normal forms is recognized by a FSA which is recurrent and which moreover contains an accept state~$V$ and a letter $g\in\mathcal S$ such that the two arrows labelled~$g$ exiting from $V$ and from the start state end in the same, non-fail state. Indeed, under these hypotheses, the accessible sub-automaton is the whole automaton (except start- and fail state), and any word traced out in the FSA which starts with the letter~$g$ and ends in the state~$V$, can play the role of the word $w_{\rm rigid}$.
\end{example}

\begin{example}\label{E:B_n^+}
We consider $G=B_n^+$, the positive braid monoid, equipped with Garside's generating set~$\mathcal S$ of nontrivial positive permutation braids, which has $n!-1$ elements. We set $\hat G=G$, and construct a FSA which has one start state, one fail state, and $n!-1$ other states, which are labelled by the $n!-1$ generators, and which are all accept states. In this automaton, every edge is labelled by one of the $n!-1$ non-trivial positive permutation braids, and an edge labelled $g$ either terminates in the state labelled $g$ or in the fail state. The automaton is constructed so as to encode the left-weighting condition of the Garside normal form, see \cite{ElrifaiMorton}.
The accessible sub-automaton of this automaton contains $n!-2$ states, corresponding to all positive permutation braids other than $1$ and~$\Delta$.

As proven in~\cite{CarusoGeneric1}, it is recurrent with~$l=5$. The normal form of any rigid braid can play the role of the word~$w_{\rm rigid}$. Thus the automatic normal form hypothesis is satisfied in this case.
\end{example}

\begin{example}\label{E:pi_1(CAT(0))}
Let $Y$ be a non-positively curved (locally CAT(0)) cubical complex, and let $b$ be one of its vertices. Let $G=\pi_1(Y,b)$ be its fundamental group, with base point in~$b$. Let $\hat G$ be the fundamental groupoid of $Y$, where the set of base points equals the set of vertices of~$Y$ -- so $G$ is a sub-group of the groupoid~$\hat G$. Let $\mathcal S$ be the set of all oriented diagonal paths across all cubes; thus every $n$-dimensional cube in~$Y$ gives rise to $2^n$ elements of~$\mathcal S$.
It was shown by Niblo and Reeves~\cite{NibloReeves} that the fundamental groupoid (and hence also the fundamental group~$G$) is bi-automatic. Their normal form for elements of~$\hat G$ uses the alphabet~$\mathcal S$, and is left-greedy: every hyperplane is traversed as early as possible. This normal form can be recognized by a FSA, which has a start state, one state for every element of~$\mathcal S$, and a fail state.
An edge labelled $g\in\mathcal S$ can lead either to the state labelled~$g$, or to the fail state. States labelled by paths which end in the base point~$b$ are accept states. If this FSA happens to be recurrent, then the automatic normal form hypothesis is satisfied, by the criterion in Example~\ref{E:RecurrentANFH}.\marg{I hope that argument is detailed enough.}

Depending on the nature of the complex~$Y$, the FSA may or may not be  recurrent. For instance, if $Y$ is the standard torus constructed from one vertex, two edges and one square, then the associated FSA is \emph{not} recurrent: a horizontal edge path can only be followed by another horizontal edge path in the same direction, and nothing else. By contrast, Figures~2 and~3 of \cite{CrispWiest1} give decompositions of closed surfaces~$S$, with $\chi(S)<0$, as non-positively curved cube complexes; the finite state automata associated to these cubings can be checked to be recurrent. This concludes Example~\ref{E:pi_1(CAT(0))}.
\end{example}

\begin{notation}
For an integer $l$, we denote $B(l)$ be the set of elements of $G$ whose normal form is of length at most~$l$. Warning: since the normal form words need not be geodesics in the Cayley graph, this set does not necessarily coincide with the ball of radius~$l$ and center $1_G$ in the Cayley graph of~$G$.
\end{notation}
\medskip

Now we suppose\marg{I think it's not necessary to explain what it means for a category to act on the left on a set.} that~$\hat G$ acts on the left by isometries on a $\delta$-hyperbolic complex~$X$ (which need not be proper). Let~$P$ be a point of~$X$ -- we think of it as a base point, and it is fixed once and for all. Then we define $c=\max_{g\in\mathcal S}d_X(P,g.P)$. (It is philosophically satisfying, but of no mathematical importance, to choose~$P$ so as to make~$c$ as small as possible.) Now if $x_1x_2x_3\ldots$ is a word in the alphabet~$\mathcal S$ which is well-defined in~$\hat G$, then any two successive points in the sequence $P$, $x_1.P$, $x_1x_2.P$, $x_1x_2x_3.P, \ldots$ in~$X$ are at distance at most~$c$.

We shall need a compatibility condition between the automatic and the hyperbolic structures:

\begin{definition}
Suppose a category~$\hat G$ acts on on a $\delta$-hyperbolic complex $(X,P)$, and that the sub-monoid $G\subset \hat G$ satisfies the automatic normal form hypothesis.
\marg{Don't really need the full automatic normal form hypothesis in the definition -- it would suffice to talk about a family of words over an alphabet $\mathcal S$ which acts on $X$. But it's easier to write this way.}
We say that the \emph{geodesic words hypothesis} is satisfied if there exists a constant $R\geqslant 0$ such that for every
normal form word $x_1x_2x_3\ldots$, and for every $i,j\in\N$ with $0\leqslant i<j$, the sequence of points
$$x_1x_2\ldots x_i.P, \ \ x_1x_2\ldots x_{i+1}.P, \ \ldots\ldots \ , x_1x_2\ldots x_j.P$$
stays in the $R$-neighbourhood of every geodesic connecting its end-points.
\end{definition}

\begin{remark}
(a) The geodesic words hypothesis is actually equivalent\marg{Reference for this equivalence?} to the condition that the family of paths
$$\{(P, \ x_1.P, \ x_1x_2.P, \ x_1x_2x_3.P,  \dots) | \ x_1x_2x_3\ldots \textrm{ a word recognized by the FSA} \}$$
forms a uniform family of unparameterized quasi-geodesics in $X$. However, we shall not use this equivalent point of view.

(b) The geodesic words hypothesis is a \emph{shadowing} condition: we require that the ``shadows'' of normal form words to~$X$ are unparametrized quasi-geodesics. For work on related conditions, in the context of mapping class groups and $Out(F_n)$, see~\cite{LRT}, and the references cited in the introduction of that paper.
\end{remark}

We recall the classification of isometries of $\delta$-hyperbolic spaces: an isometry~$\phi$ of~$X$ acts \emph{elliptically} if the orbit $P$, $\phi(P)$, $\phi(\phi(P))$, $\phi(\phi(\phi(P))),\ldots$ in~$X$ is bounded. It acts \emph{parabolically} if the orbit is unbounded but $\lim_{n\to\infty}\frac{1}{n}\cdot d_X(P, \phi^n(P))= 0$. In this case, the sequence of points $P$, $\phi(P)$, $\phi^2(P),\ldots$ of $X$, is \emph{not} a quasi-geodesic in~$X$: the point $\phi^n(P)$ gets arbitrarily far away from any geodesic connecting $P$ and~$\phi^{2n}(P)$; moreover,  the isometry of $X$ given by the action of~$\phi$ has a unique fixed point on~$\partial X$.
Finally, $\phi$ acts \emph{loxodromically} (or \emph{hyperbolically}) if $\lim_{n\to\infty}\frac{1}{n}\cdot d_X(P, \phi^n(P))$ exists and is positive. In this case, the orbit of~$P$ under $\langle \phi\rangle$ is a quasi-geodesic, and the isometry of $X$ given by the action of $\phi$ has two fixed points on~$\partial X$. For a proof that any element belongs to exactly on of these three classes see \cite[Section 9]{CDP} (which requires $X$ to be proper, but the proof does not use this hypothesis). See also~\cite[Section 3]{CCMT}.

\begin{notation}
Suppose a category~$\hat G$ acts on a $\delta$-hyperbolic space, and that the sub-monoid~$G$ satisfies the automatic normal form hypothesis. We say that \emph{there are interesting loxodromic actions} if  there exists a loop in the accessible sub-automaton such that the product of elements of~$\mathcal S$ read along this loop acts loxodromically on $X$. This is for instance the case if there are rigid elements which act loxodromically.
\end{notation}

We are now ready to state our main result.

\begin{theorem}\label{T:main}
Let $G$ be a monoid and $\hat G$ a category with $G\subset \hat G$, and with~$\hat G$ acting on a $\delta$-hyperbolic complex~$X$. Suppose that the automatic normal form hypothesis and the geodesic words hypothesis are satisfied. Suppose further that there are interesting loxodromic actions. Then
$$
\liminf_{l\to\infty} \frac{\#\{\textrm{elements of }B(l)\textrm{ which are rigid and act loxodromically on }X\}}{\#B(l)} > 0.
$$
\end{theorem}

We remark that the proportion of rigid elements does definitely \emph{not} tend to~1 as $l$ tends to infinity -- in this sense, Theorem~\ref{T:main} cannot be improved upon. Being rigid is a very interesting property, in that it has remarkable dynamical consequences. Very roughly speaking, for a rigid element, the guts of the action happen close to the base point:

\begin{proposition}\label{P:rigid}
Suppose the hypotheses of Theorem~\ref{T:main} are satisfied.
\marg{Again, I don't really need the full automatic normal form hypothesis.}
Let $P$ be the base point of~$X$, and let $R$ be the constant appearing in the geodesic words hypothesis. Let $g$ be a rigid element of~$G$.
\begin{itemize}
\item $g$ cannot act parabolically on~$X$.
\item If $g$ acts elliptically, then $d_X(P,g^n.P)\leqslant 3R$ for all~$n$.
\item If $g$ acts loxodromically, and if $a\subset X$ is a geodesic axis, then the base point~$P$ is at distance at most~$R$ from~$a$.
\end{itemize}
\end{proposition}

\begin{openproblems}
\begin{enumerate}
\item It should be possible to use Theorem~\ref{T:main} in order to study the proportion of pseudo-Anosov elements in all mapping class groups. We recall that a mapping class is pseudo-Anosov if and only if it acts loxodromically on the curve complex of the surface. It seems likely that any mapping class group, equipped with any reasonable normal form recognized by a FSA, satisfies the geodesic words hypothesis. One tool for checking the geodesic words hypothesis could be the fact~\cite{MM4} that train track splitting sequences give rise to unparametrized quasi-geodesics in the curve complex -- see also~\cite{MasMoshSchl}.

\item Apply the theorem in other contexts, for instance of $Out(F_n)$ acting on the free factor complex $\mathcal{FF}_n$. We recall that in this setup, an element acts loxodromically if and only if it is iwip.
\item Prove the stronger result that the proportion of elements of~$G$ which act loxodromically actually tends to~$1$ (we have only proven that its $\liminf$ is positive). One possible strategy for doing so involves constructing a ``blocking element'' in~$G$, analogue to the blocking braids of~\cite{CarusoWiestGeneric2}.

\item Strengthen the statements by proving that the translation distance in~$X$ of the action of generic elements with normal forms of length~$l$ is bounded below by a linear function in~$l$ (c.f.\ \cite{MaherLin}).

\item Another possible strengthening would be the genericity not only of loxodromic, but even of  contracting actions, in the sense of Sisto~\cite{SistoGeneric}.
\end{enumerate}
\end{openproblems}

\section{Proofs}

\begin{proof}[Proof of Theorem~\ref{T:main}]
Throughout the proof, our strategy for counting \emph{elements} of~$G$ with various properties will be to count \emph{normal form words} representing elements with the same properties.

The first step of the argument is to prove that  the proportion of elements which are rigid is bounded away from zero.

\begin{lemma}\label{L:RigidNotRare}
$$
\liminf_{l\to\infty} \frac{\#\{\textrm{rigid words of length }l\textrm{ recognized by the FSA}\}}{\phantom{rigi}\#\{\textrm{words of length }l\textrm{ recognized by the FSA}\}} > 0.$$
\end{lemma}

\begin{proof} We recall that there is, by hypothesis, a path in the automaton, starting at the start state and ending at some accept state $E$ in the accessible sub-automaton, tracing out a word $w_{\rm rigid}$ in the automaton such that the path along the word~$w_{\rm rigid}^2$ ends in the same state~$E$. In particular, the word $w_{\rm rigid}$ is rigid.
\marg{I think this explanation is sufficiently detailed.}
Since the automaton is dominated by the accessible sub-automaton, we have
$$
\liminf_{l\to\infty} \frac{\#\{\textrm{words of length }l\textrm{ with prefix }w_{\rm rigid},\textrm{ recognized by the FSA}\}}{\phantom{}\#\{\textrm{words of length }l\textrm{ recognized by the FSA}\}} > 0.$$

Next we observe that, for any word~$w_\circlearrowleft$ read out along a loop starting and ending in the state~$E$, the word $w_{\rm rigid}w_\circlearrowleft$ is also rigid. Let us denote the by~$k$ the length of the word~$w_{\rm rigid}$. Now, among the paths of length $l-k$ in the automaton (in fact in the accessible sub-automaton) which start at the state~$E$, the proportion of those which also end at~$E$ tends to some positive number as $l$~tends to~$\infty$ -- for a proof of this fact, see for instance \cite[Lemma 3.5(i) and (ii)]{CarusoGeneric1}.

In summary, among the words of length~$l$, there is a positive proportion which starts with the word~$w_{\rm rigid}$, and among those, there is a positive proportion of words which end at the state $E$. Since all these words are rigid, the lemma is proven.
\end{proof}

We now turn to the second step of the proof of Theorem~\ref{T:main}, namely proving that among the rigid elements constructed in the previous step, the proportion of loxodromically acting ones tends to 1. (Actually, the convergence happens exponentially quickly, but we will not use or prove this.)

Let $w$ be a word in normal form which is rigid -- this means that the word $w^n$ is also in normal form for all positive integers~$n$, and thus that the geodesic words hypothesis applies to all~$w^n$. We will prove that this imposes serious restrictions on how the element of~$G$ represented by~$w$ can act on~$X$.

\begin{lemma}\label{L:NonPaObvious}
Let~$w$ be a rigid word in normal form. Then $w$ cannot act parabolically; moreover, if it acts elliptically, then it does not contain any subword whose action moves the base point~$P$ by more than~$5R$. (Here $R$ is the constant appearing in the geodesic words hypothesis.)
\end{lemma}

\begin{proof}
The rigid element represented by $w$ cannot act \emph{parabolically} on~$X$, because if it did, then the infinite sequence of points $P$, $w.P$, $ww.P$, $www.P, \ldots$ would not lie uniformly close to a geodesic ray, as required by the geodesic words hypothesis.

Next, we look at the case where the rigid element $w$ acts \emph{elliptically}. We denote $D=d_X(P,w.P)$. Since $w$ acts by isometries, we have $d_X(w^k.P,w^{k+1}.P)=D$ for all integers~$k$.

{\bf Claim A } We claim that $D\leqslant 3R$.

In order to prove Claim A, we suppose, for a contradiction, that $D=3R+\epsilon$, for some positive integer~$\epsilon$. Since $w$ acts elliptically, the orbit $P$, $w.P$, $ww.P$, $www.P, \ldots$ is bounded -- let $\rho$ be its diameter. Now we choose an integer~$N$ so large that $\frac{\rho}{N}<\epsilon$.
By the geodesic words hypothesis, the geodesic from~$P$ to~$w^N.P$ contains all points $w^i.P$, for $0\leqslant i\leqslant N$, in its $R$-neighbourhood. In particular, for every point $w^i.P$ there is a point $v_i$ on this geodesic with $d_X(w^i.P, v_i)\leqslant R$. We now have the~$N$ points $\nu_1,\ldots,\nu_N$ on a geodesic of length at most~$\rho$, so there is a pair of indices $(i,j)$ with $0\leqslant i<j\leqslant N$ such that $d_X(v_i, v_j)\leqslant \frac{\rho}{N}<\epsilon$. This implies that $d_X(w^i.P, w^j.P)<2R+\epsilon$. Hence the point $w^{i+1}.P$, which lies at distance exactly $3R+\epsilon$ from $w^i.P$, cannot lie in the $R$-neighbourhood of a geodesic segment from $w^i.P$ to $w^j.P$. This contradicts the geodesic words hypothesis, and the claim is proven.

We have just seen that a rigid element~$w$ which acts elliptically cannot move the base point very far: $d_X(P,w.P)\leqslant 3R$. In fact, neither can any subword of~$w$:

{\bf Claim B } If $w=x_1x_2x_3\ldots$ is rigid, we claim that any subword $x_i x_{i+1}\ldots x_{j-1} x_j$ satisfies
$$
d_X(P, x_i x_{i+1}\ldots x_{j-1} x_j.P)\leqslant 5R
$$

In order to prove this claim, we observe that $x_1\ldots x_{i-1}.P$ and $x_1\ldots x_j.P$ each lie $R$-close to some point of a geodesic from~$P$ to~$w.P$. Since this geodesic is only of length at most $3R$, we obtain
$$
d_X(x_1\ldots x_{i-1}.P, x_1\ldots x_j.P)\leqslant R+3R+R=5R
$$
Since $x_1\ldots x_{i-1}$ acts by an isometry on~$X$, we deduce that $d_X(P, x_i\ldots x_j.P)\leqslant 5R$, also. The proof of Claim B and of Lemma~\ref{L:NonPaObvious} is complete.
\end{proof}

We observe that words whose action displaces the base point by more than $5R$ do actually exist (by the hypothesis that there are \emph{loops} in the accessible sub-automaton which act loxodromically). Let $w_{\rm far}$ be one such word.

Now we recall that we have a distinguished rigid word $w_{\rm rigid}$ recognized by the automaton, whose length we denote~$k$ and which is read in the automaton along a path which ends in an accessible accept state which we denote~$E$.
As seen in the proof of Lemma~\ref{L:RigidNotRare}, there is a non-negligible proportion of elements of length~$l$ which are recognized by the automaton and which are of the form $w_{\rm rigid}w_\circlearrowleft$, where the word~$w_\circlearrowleft$ is read along a loop of length $l-k$ based at the state~$E$. In particular, these words $w_{\rm rigid}w_\circlearrowleft$ are rigid. Now, we have seen in Lemma~\ref{L:NonPaObvious} that these words are guaranteed to act loxodromically if they contain a subword $w_{\rm far}$ which moves the base point by more than $5R$.

Among the words of length~$l-k$ which can be read along loops based at~$E$ in the accessible sub-automaton,  the proportion of those that do not contain the subword~$w_{\rm far}$ tends to~$0$ as $l$ tends to infinity. For a proof of this statement, see Lemma 3.5(iii) of~\cite{CarusoGeneric1}. (In fact, this convergence is exponentially fast.)

In summary, the proportion of rigid, loxodromically acting words among all recognized words of length equal to~$l$ is bounded away from~$0$. The very last step is to deduce that the same holds among all recognized words of length \emph{less than or} equal to~$l$. The proof of Theorem~\ref{T:main} is now complete.
\end{proof}

\begin{remark}\label{R:SphereBall}
For later reference, we point out that we started by proving the analogue of Theorem~\ref{T:main} for the \emph{sphere} consisting of elements whose normal form is of length equal to~$l$, and deduced the result for the \emph{balls} $B(l)$ from that.
\end{remark}

\begin{proof}[Proof of Proposition~\ref{P:rigid}]
All the work for this proof has already be done in the proof of Theorem~\ref{T:main}. Lemma~\ref{L:NonPaObvious} tells us that~$g$ cannot act parabolically, and elliptically acting elements cannot move the base point by more than~$5R$. Claim~A gives the stronger bound of~$3R$. For the loxodromic case, the geodesic words hypothesis implies that, for all positive integers~$k$, the point $g^k.P$ lies $R$-close to any geodesic from $P$ to~$g^{2k}.P$.
\marg{Is it clear that this implies that $P$ is $R$-close to the axis?}
Thus $P$ lies $R$-close to any geodesic from $g^{-k}.P$ to~$g^k.P$.
\end{proof}

\section{Examples}

In this section we study four examples: the group $PSL(2,\mathbb Z)$ acting on the Farey graph, braid groups acting on the additional length complex, relatively hyperbolic groups acting on their associated $\delta$-hyperbolic space, and of  fundamental groups of compact, locally CAT(0) cubical complexes acting on the contact graph.

\subsection{$\mathrm{PSL}(2,\mathbb Z)$ acting on the Farey graph}

As a warm-up exercise, we will look at the group $\mathrm{PSL}(2,\mathbb Z)$, acting on the Farey graph. One motivation for this study is that $\mathrm{SL}(2,\mathbb Z)$ is the mapping class group of the once-punctured torus, which acts on its curve complex, the Farey graph -- see \cite[Section 1.5]{MM2}. Saying that a matrix $M$ in $\mathrm{SL}(2,\mathbb Z)$ acts loxodromically is equivalent to saying that~$M$, seen as a homeomorphism of the once-punctured torus, is of pseudo-Anosov type.

In this framework, Theorem~\ref{T:main} does not contain any new information, since the full genericity (in the sense of this paper) of pseudo-Anosov elements has been known for a long time. A proof of this fact is in~\cite[Theorem 18]{Rivin}, and the closely related case of the 3-strand braid group is treated very explicitly in~\cite{AK}. However, our aim here is to illustrate the proof of Theorem~\ref{T:main}

The group $\mathrm{PSL}(2,\mathbb Z)$ has a presentation
$$\langle \ A,B \ | \ ABA=BAB, (ABA)^2=1\ \rangle, \text{ \ where \ } A=\begin{pmatrix}
1 & 1 \\
0 & 1 \\
\end{pmatrix}, \ \ \
B=\begin{pmatrix}
1 & 0 \\
-1 & 1 \\
\end{pmatrix}.$$
We shall outline the proof of the following special case of Theorem~\ref{T:main}:

\begin{proposition}
Let $B(l)\subset \mathrm{PSL}(2,\mathbb Z)$ be the vertices of the ball of radius~$l$ with center~$1$ in the Cayley graph of $\mathrm{PSL}(2,\mathbb Z)$ with generators $A^{\pm 1}$, $B^{\pm 1}$.  Among the elements of~$B(l)$,  we look at the proportion of those which act loxodromically on the Farey graph, and whose axis in the Farey graph passes at distance~1 from the point~$P=0=\frac{0}{1}$. Then the $\liminf_{l\to\infty}$ of this proportion is strictly positive.
\end{proposition}

\begin{proof}
We have to check that the hypotheses of Theorem~\ref{T:main} are satisfied with~$R=1$ and with geodesic normal form words.
One can check that any element of $\mathrm{PSL}(2,\mathbb Z)$ except $ABA$ and $\overline A\overline B\overline A$ has a unique representative word not containing the subwords $ABA$, $\overline A\overline B\overline A$, $BAB$, $\overline B\overline A \overline B$, $AB\overline A$, $BA\overline B$, $\overline A\overline B A$ and $\overline B\overline A B$. The automaton describing this language is shown in Figure~\ref{F:automaton}. Note that the words in this normal form are in fact geodesics in the Cayley graph.

\begin{figure}[htb]
\centering

\input{SL2Zautomaton2.pdf_tex}
\caption{A finite state automaton for $\mathrm{PSL}(2,\mathbb Z)$. All states (except the start state) are accept states. The states are named after the last two letters read. The symbol $X_{\neg A}$ means ``any letter but $A$, or no letter''. The bottom part of the picture shows the accessible sub-automaton. The top part shows (shaded grey) the non-accessible states, and how they are connected to the accessible states. Not shown here is the fail state and the arrows leading to it.}
\label{F:automaton}\end{figure}

One can then write down the adjacency matrix~$M$ of the accessible sub-automaton -- this is an $8\times 8$ matrix. According to Perron-Frobenius theory, there is a unique eigenvalue $\lambda$ of $M$ of maximal modulus. This~$\lambda$ is then real and has a one-dimensional eigenspace. In the present  case, it turns out that $\lambda=\sqrt{2}+1$ (the ``silver ratio'').

We see that several words can play the role of the word $w_{\rm rigid}$, we choose $w_{\rm rigid}=B$. (Another possible choice would have been $w_{\rm rigid}=A\overline B$.)

In Lemma~\ref{L:RigidNotRare} we saw that the proportion of rigid words among all words of length~$l$ is bounded away from zero. In order to prove this, we showed that even the subset consisting of the words that start with the subword $w_{\rm rigid}$ and trace a path in the automaton that terminates in the same state as~$w_{\rm rigid}$ has non-vanishing frequency. For the present example, one can explicitly calculate this proportion, using the adjacency matrix~$M$. One finds that  among all elements of length~$l$, the proportion of words starting with the letter~$B$ is~$\frac{1}{4}$, and among those, the proportion of words that end in the state $X_{\neg A} B$ tends to $\frac{\lambda}{4\lambda+4}=\frac{1}{4\sqrt{2}}$. This yields a (not at all sharp) lower bound of $\frac{1}{16\sqrt{2}}$ on the limit of the proportion of rigid words.

In order to study the proportion of loxodromically acting words among the rigid ones, we equip the Farey graph with the base point~$P=0=\frac{0}{1}$. Then the geodesic words hypothesis is satisfied with $R=1$, i.e.\ the orbit of~$P$ under the action of a normal form word traces out a path which stays at distance~1 from any geodesic connecting its end-points.
Now by Claim~B, the normal form of any rigid element which does not act loxodromically cannot contain any subword that moves the base point by more than five. However, interesting loxodromic actions exist -- for instance given by the word $A\overline B$ -- and the action of $(A\overline B)^6$ moves the base point by a distance of 6. The proportion, among rigid (or indeed any) words of length~$l$, of words which do not contain the subword $(A\overline B)^6$ tends to zero as $l$~tends to infinity.
\end{proof}

\subsection{Word-hyperbolic groups acting on their Cayley graphs}

Let~$G$ be an infinite word-hyperbolic group equipped with some fixed, finite generating set~$\mathcal S$. Let $X$ be the Cayley graph of~$G$ with respect to~$\mathcal S$; it is $\delta$-hyperbolic. As the base point of~$X$ we take~$1_G$, the neutral element of~$G$. The group acts on~$X$, on the left, by isometries. Elements of finite order act elliptically, and elements of infinite order act loxodromically~\cite[Chapter~8]{GhysDeLaHarpe}.

We wish to prove that a positive proportion of elements, in the sense of Theorem~\ref{T:main}, act loxodromically. Unfortunately, it seems hard to apply Theorem~\ref{T:main} directly, as the automatic normal form hypothesis does not hold in sufficient generality. However, in the framework of hyperbolic groups we have other techniques at our disposal which will allow us, in Proposition~\ref{P:MainHyperbolic}, to prove an analogue of Theorem~\ref{T:main}, under a very mild technical condition.

We consider the language $\mathcal L$ of words with letters in~$\mathcal S^{\pm 1}$ such that every subword of length $10\delta$ is a geodesic in~$X$.
In other words, the language $\mathcal L$ is defined by the fact that a finite number of subwords, namely the non-geodesics of length at most $10\delta$, are banned.

The technical hypothesis on the pair $(G,\mathcal S)$ that we need is that for any pair of words $(w_1,w_3)$ in $(\mathcal L, \mathcal L)$, there exists a word $w_2$ in~$\mathcal L$ such that the composite word $w_1w_2w_3$ also belongs to~$\mathcal L$.
(We conjecture that this hypothesis is satisfied for any hyperbolic group with any set of generators.)

\begin{proposition}\label{P:MainHyperbolic}
Suppose $G$ is a group, equipped with a finite generating set~$\mathcal S$, whose Cayley graph~$X$ is $\delta$-hyperbolic. Suppose also that the above technical hypothesis on the pair $(G,\mathcal S)$ is satisfied. Then there exist constants $D,R$ with the following properties: for every element $g$ of~$G$ with $d_X(1_G,g) \geqslant 10\delta$, there exists an element~$\tilde g$ with $d_X(g,\tilde{g})\leqslant D$

which acts loxodromically on~$X$ (i.e.\ is torsion free), and whose loxodromic axis in~$X$ passes within distance~$R$ from the basepoint $1_G$.
\end{proposition}

\begin{proof}

For every pair of words $(w_1,w_3)$, both of length $10\delta$ and belonging to~$\mathcal L$, we choose a word $w_2$ as in the technical hypothesis, where this $w_2$ should be chosen as short as possible. Let $D$ be the length of the longest word $w_2$ thus obtained.

Now for any element $g$ of~$G$ at distance at least $10\delta$ from the identity element. Let $w$ be a geodesic representative of~$g$, let $w_1$ consist of the last $10\delta$ letters of $w$, and let $w_3$ consist of the first $10\delta$ letters.
With $w_2$ the word promised by the technical hypothesis, let $\tilde g$ be the element represented by the word $w w_2$. We observe that $d_X(g,\tilde g)\leqslant D$, and that any power of the word $w w_2$ representing $\tilde g$ belongs to the language~$\mathcal L$.

Now we recall a classical fact about hyperbolic group due to Canary -- see \cite[Theorem 3.11]{ABCFLMSS}:  words in~$\mathcal L$ represent $(12,7\delta)$-quasigeodesics in~$X$.

Let us denote $x(i)$, for $i\in\mathbb N$, the point of the Cayley graph~$X$ represented by the prefix of length~$i$ of the word $w w_2 w w_2 w\ldots$ Similarly, for $i<0$, we let $x(i)$ be the prefix of length~$i$ of $w_2^{-1} w^{-1} w_2^{-1} w^{-1}\ldots$.
Then the path $(x(i))_{i\in\mathbb Z}$ is a $(12,7\delta)$-quasigeodesic in~$X$ which contains the bi-infinite sequence points $\ldots, \tilde g^{-2}, \tilde g^{-1},1,\tilde g, \tilde g^2,\ldots$, i.e.\ the orbit of the base point of~$X$ under the action of $\langle\tilde g\rangle$.

Thus the element $\tilde g$ acts loxodromically. Moreover, the axis of this action is a geodesic connecting the same pair of points on~$\partial X$ as the quasigeodesic $(x(i))_{i\in\mathbb Z}$.
Since in a $\delta$-hyperbolic space, any $(12,7\delta)$-quasigeodesic stays at some universally bounded distance~$R$ from any geodesic connecting the same pair of points \cite[Chapter 5]{GhysDeLaHarpe}\marg{This reference talks about finite geodesics. Reference for the infinite case?}, any axis of~$\tilde g$ passes at distance~$R$ from the base vertex~$1_G$ of~$X$.
\end{proof}

\subsection{Relatively hyperbolic groups}

The geodesic words hypothesis of Theorem~\ref{T:main} is often very difficult to verify -- for instance, we do not know if it holds in the case of braid groups (with the Garside normal form) acting on the curve complex of a punctured disk.  The aim of this short section is to point out that there is one large and interesting class of groups acting on $\delta$-hyperbolic spaces where this hypothesis holds automatically.

Let $G$ be a group, equipped with a finite generating set~$S$, that is relatively hyperbolic, in the strong sense, with respect to the finite collection of subgroups $\mathcal H=\{H_1,\ldots,H_m\}$. We recall what this means. Firstly, the Cayley graph of~$G$ with respect to~$S$, with every translate of every~$H_i$ coned off, is required to be a $\delta$-hyperbolic space. We denote this quotient space by $Cayley(G,S\cup\mathcal H)$. Secondly, the couple $(G,\mathcal H)$ must satisfy the so-called bounded coset penetration property. (This is Farb's definition~\cite{Farb}, for a list of equivalent definitions see~\cite{GrovesManning}).

\begin{proposition}
Suppose that $G$ is a finitely generated group (generating set~$S$), which is (strongly) relatively hyperbolic, with respect to the collection~$\mathcal H$ of subgroups, so that $G$ acts on the $\delta$-hyperbolic complex $Cayley(G,S\cup\mathcal H)$. Suppose further that~$G$ satisfies the automatic normal form hypothesis, and that the automatic normal forms are \emph{geodesics} in the Cayley graph $Cayley(G,S)$. Then the geodesic words hypothesis is satisfied.
\end{proposition}

\begin{proof} This is an immediate consequence of Proposition~8.25 and Theorem~A.1 in~\cite{DrutuSapir}. \end{proof}

\subsection{Braid groups acting on the additional length complex}

An important class of automatic groups, admitting algorithms for the word- and conjugacy problem which are very fast in practice and relatively easy to program are the so-called \emph{Garside groups}. For a gentle introduction to these groups see~\cite[Section 1]{BGGMrigid}, and for much more complete accounts see~\cite{DehornoyGarside,GarsideFoundations}.
The classical examples of such groups are Artin-Tits groups of spherical type, and in particular braid groups~\cite{BrieskornSaito,BessisDual,ElrifaiMorton,ECHLPT}.

It was proved in~\cite{CalvezWiest} that every Garside group~$G$ acts on a $\delta$-hyperbolic space $\mathcal C_{AL}(G)$ in such a way that the shadow of words in automatic normal form on $\mathcal C_{AL}(G)$ is an un-parametrized quasi-geodesic. More precisely, it is shown that the geodesic words hypothesis is satisfied with~$R=39$.

In the case $G=B_n$, the braid group on $n$ strands equipped with its classical Garside structure, the complex~$\mathcal C_{AL}(B_n)$ is of infinite diameter. Moreover, periodic and reducible  braids act elliptically, and there exists a positive, rigid pseudo-Anosov braid which acts loxodromically, so there are interesting loxodromic actions. (It is currently unknown whether all pA braids act loxodromically, and indeed whether the additional length complex is quasi-isometric to the curve complex.)

\begin{notation}
We denote $\hat B(l)$ the ball with radius~$l$ and center~1 in the Cayley graph of~$B_n$, with  Garside's set of generators.
\end{notation}

Most of the following result was already known from S.~Caruso's paper~\cite{CarusoGeneric1}:

\begin{proposition}\label{P:Caruso}
Among the elements in the ball~$\hat B(l)$, the $\liminf_{l\to\infty}$ of the proportion of elements which act loxodromically on $\mathcal C_{AL}(B_n)$ (and thus are pseudo-Anosov), and whose axis in~$\mathcal C_{AL}(B_n)$ passes at distance at most 39 from the base point~$1_G$, is strictly positive.
\end{proposition}

\begin{proof}
Let us first restrict our attention to the positive braid monoid~$B_n^+$. As seen in Example~\ref{E:B_n^+}, the automatic normal form hypothesis is satisfied in~$B_n^+$.
Also, we saw in the preceding discussion that the other hypotheses of Theorem~\ref{T:main} are satisfied. Applying Theorem~\ref{T:main} and Remark~\ref{R:SphereBall}, we obtain the desired result (Proposition~\ref{P:Caruso}), with one exception: we do not obtain a statement about the balls $\hat B(l)$ of radius~$l$, but instead about the ``sphere segment'' of \emph{positive} braids whose Garside normal form is of length \emph{exactly} equal to~$l$. Let us denote this sphere segment by~$S(l)$.

In order to deduce the analogue result for $\hat B(l)$, we recall first that in~$B_n^+$, like in all Garside monoids, words in Garside normal form represent geodesics in the Cayley graph~\cite{CharneyMeier}. More generally, the ball~$\hat B(l)$ consists precisely of braids

which can be written as a product $\Delta^{-k}\cdot x$, where $k\in \{0,1,\ldots,l\}$ and $x\in S(l)$; moreover, this writing, when it exists, is unique. Now for every braid $x$, the braids $\Delta^{-2} x, \Delta^{-4} x,\ldots$ all have the same Nielsen-Thurston type, and the same action on~$\mathcal C_{AL}(B_n)$, as~$x$.

Thus if we compare the proportions, in~$\hat B(l)$ and in~$S(l)$, of elements which act loxodromically and with axis passing close to the base point, we see that the proportion in~$\hat B(l)$ is equal to at least half the proportion in~$S(l)$.
\end{proof}

Actually, we can also give a new proof of the main result from~\cite{CarusoWiestGeneric2}. It is a small, but significant variation of the original proof. The statement of the result is as follows:

\begin{proposition}\label{P:CarusoW}
Among the elements in the ball $\hat B(l)$

the proportion of elements which act loxodromically on $\mathcal C_{AL}(B_n)$ tends to 1 exponentially quickly as $l\to\infty$.
\end{proposition}

\begin{proof}
The new ingredients that we shall use are the action of $B_n$ on~$\mathcal C_{AL}(B_n)$, and Lemma~\ref{L:NonPaObvious} from the present paper. By contrast, we will avoid using results from~\cite{GonzalezMenesesWiest2}.

Throughout this proof, by ``generic elements'' we mean ``a proportion of elements which tends to 1 exponentially quickly''. As seen in~\cite{CarusoWiestGeneric2}, generic elements of~$B_n^+$ have a so-called \emph{non-intrusive conjugation} to a rigid element. Moreover, the middle fifth of this conjugated element, which has not been touched by the conjugation, contains generically any given braid as a subbraid -- for instance a braid whose action moves the base point of $\mathcal C_{AL}(B_n)$ by more than $5\cdot R=195$. By Lemma~\ref{L:NonPaObvious}, these generic elements act loxodromically on~$\mathcal C_{AL}(B_n)$. This completes the proof of Proposition~\ref{P:CarusoW}.

In other words, we can use literally the same proof as the proof of Theorem~5.1 in~\cite{CarusoWiestGeneric2}, with one exception: Lemma 5.2 of~\cite{CarusoWiestGeneric2} uses the fact that a rigid braid whose normal form contains one of two very particular subwords (called $\gamma_1$ and $\gamma_2$ in~\cite{CarusoGeneric1}) must be pseudo-Anosov. Instead, we now use the fact that a rigid braid whose normal form contains another subword, namely one whose action moves the base point of $\mathcal C_{AL}(B_n)$ by more than~$195$, must be pseudo-Anosov.
\end{proof}

What is the significant advantage of our new proofs of Propositions~\ref{P:Caruso} and~\ref{P:CarusoW}? The proofs which were given in~\cite{CarusoGeneric1} and~\cite{CarusoWiestGeneric2} both relied heavily on a result of~\cite{GonzalezMenesesWiest2} (Theorem 5.16), which is very specific to braid groups. It states that if a rigid braid is reducible, then its reducibility is obvious (there is a round or ``almost round'' reducing curve).

In our current proof, this result is no longer used; instead, our Claim~A plays a similar r\^ole.
(Similarly, our Claim~B can be thought of as an analogue of the theorem of Bernadete-Guttierez-Nitecki~\cite{BGN,CalvezDual}.)
We believe that our new proof of the genericity of pseudo-Anosov braids can be generalized so as to apply to many other groups, e.g.\  to Artin-Tits groups of spherical type.

\subsection{Fundamental groups of locally-CAT(0) cubical complexes acting on the contact graph}

In this section we consider a locally finite, non-positively curved (or ``locally CAT(0)'') cubical complex~$Y$, equipped with a base point~$b$. We shall look at the fundamental group $\pi_1(Y,b)$. For instance, $Y$ could be the the defining complex, the so-called Salvetti complex, of a right-angled Artin group $A=\pi_1(Y)$, which has one $n$-cube for every $n$-tuple of pairwise commuting generators.

We have already studied this general setup in Example~\ref{E:pi_1(CAT(0))}. There we saw that the associated finite state automaton may or may not be recurrent, but if it is, then the automatic normal form hypothesis is satisfied.

The universal cover of~$Y$ is a CAT(0) cubical complex~$\widetilde Y$.
Now  the fundamental group $G=\pi_1(Y)$ acts on~$\widetilde Y$ by deck-transformations, but unfortunately, if we want the fundamental \emph{groupoid} of $Y$, which in Example~\ref{E:pi_1(CAT(0))} was called~$\hat G$, to act on~$\widetilde Y$, we must assume that~$Y$ has only a single vertex.
In order to circumvent this problem, we use the following trick.

We define $Y'$ to be the cubical complex obtained from the complex~$Y$ by identifying all its vertices. This new complex~$Y'$ is still locally CAT(0), as Gromov's link condition in still satisfied. If~$Y$ has $v$ vertices, then the universal cover $\widetilde {Y'}$ consists of infinitely many copies of~$\widetilde Y$, glued together in a tree-like fashion, so that at each vertex, $v$~copies of~$\widetilde Y$ meet.
Any choice of a base point~$\tilde b$ of~$\widetilde {Y'}$ covering the vertex of~$Y'$ induces a choice of a distinguished copy of $\widetilde Y$ in~$\widetilde {Y'}$, which we call~$\widetilde Y_*$: it consists of the set of end-points of lifts, starting at~$\tilde b$, of paths in~$Y$ starting at~$b$.

The natural glueing map $Y\to Y'$ induces an \emph{injective} group homomorphism $\pi_1(Y)\hookrightarrow \pi_1(Y')$. It even induces an injective groupoid homomorphism from the fundamental groupoid~$\hat G$ of~$Y$ to the fundamental group $\pi_1(Y')$.
Therefore, we obtain an action of the groupoid~$\hat G$ on the universal cover $\widetilde {Y'}$ of~$Y'$ by deck-transformations.
The action of an element~$g\in\hat G$ on~$\widetilde {Y'}$ preserves the distinguished copy $\widetilde Y_*$ of~$\widetilde Y$ if and only if $g\in G$, i.e. if the path in~$Y$ representing~$g$ terminates in the base point~$b$, not some other vertex. Nevertheless, for any $g\in \hat G$, the vertex $g.\tilde b$ of~$\widetilde {Y'}$ lies in $\widetilde Y_*$.

Now we recall some definitions and  results due to Hagen~\cite{Hagen13,Hagen14}, see also~\cite{BehrstockHagenSisto} for a nice overview. The \emph{contact graph} $\mathcal C\widetilde Y$ of~$\widetilde Y$ is the graph having one vertex for every hyperplane of~$\widetilde Y$, and two vertices are connected by an edge if the corresponding hyperplanes are not separated by a third hyperplane (in other words, if they intersect or osculate). It was proven by Hagen that the contact graph is always connected and $\delta$-hyperbolic -- in fact, it is quasi-isometric to a tree. In particular, there are no parabolic isometries of~$\mathcal C\widetilde Y$, only elliptic and loxodromic ones. (See \cite[Theorem~2.8]{BehrstockHagenSisto} for more detailed descriptions of each of these two cases.)

Similarly, we have a contact graph~$\mathcal C\widetilde {Y'}$, and the distinguished copy $\widetilde Y_*$ of $\widetilde Y$ in $\widetilde {Y'}$ gives rise to a distinguished copy $\mathcal C\widetilde Y_*$ of $\mathcal C\widetilde Y$ in $\mathcal C\widetilde {Y'}$. The fundamental groupoid~$\hat G$ of~$Y$ acts on~$\mathcal C\widetilde {Y'}$ by graph isomorphisms, and an element $g$ of~$\hat G$ preserves the subset~$\mathcal C\widetilde Y$ if and only if~$g\in G=\pi_1(Y)$.

\begin{proposition}
Suppose $Y$ is a non-positively curved cubical complex such that, firstly, the associated finite-state automaton is recurrent, and secondly, the contact graph~$\mathcal C\widetilde Y$ is of infinite diameter. Let~$B(l)$ be the set of elements of~$\pi_1(Y)$ which can be written as a product of at most~$l$ elements of~$\mathcal S$ (at most~$l$ cube diagonals). Then the $\liminf_{l\to\infty}$ of the proportion of elements of~$B(l)$ which act loxodromically on~$\mathcal C\widetilde Y$ and whose axis passes at distance $R=3$ from the base point  is strictly positive.
\end{proposition}

\begin{proof}
The action of an element $g\in\pi_1(Y)$ on~$\mathcal C\widetilde {Y'}$ is loxodromic if and only if its action on~$\mathcal C\widetilde Y$ is loxodromic. Thus for the rest of the proof we shall study the action of~$\pi_1(Y)$ on~$\mathcal C\widetilde {Y'}$ (rather than on~$\mathcal C\widetilde Y$), and the proportion of elements which act loxodromically.
We have already seen in Example~\ref{E:pi_1(CAT(0))} that the automatic normal form hypothesis of Theorem~\ref{T:main} is verified. We still have to prove the geodesic words hypothesis, and the hypothesis that interesting loxodromic actions exist.

First we define a base point in~$\mathcal C\widetilde {Y'}$. In fact, we shall not be very interested in choosing a base \emph{point}, but a base \emph{simplex} $\mathcal P$ in~$\mathcal C\widetilde {Y'}$, i.e.\ a finite collection of points which are all at distance one from each other. By definition, the vertices of our base simplex are those corresponding to all hyperplanes in~$\widetilde {Y'}$ that are adjacent to the base point~$\tilde b$. (As a base point of~$\mathcal C\widetilde Y$ one can then choose any vertex of~$\mathcal P$ belonging to~$\mathcal C\widetilde Y$.)

Now let~$\gamma$ be an element of~$\pi_1(Y)$, and let $\gamma=\gamma_1\cdot\ldots\cdot\gamma_k$ be a shortest possible decomposition of~$\gamma$ as a product of our generators~$\mathcal S$ of~$\hat G$ -- for instance the normal form of~$\gamma$.
The trace of the base simplex~$\mathcal P$ under the normal form of~$\gamma$, i.e.\ the sequence of simplices $1.\mathcal P$, $\gamma_1.\mathcal P$, $\gamma_1\gamma_2.\mathcal P,\ldots,\gamma.\mathcal P$, has the following property:
each of the simplices contains at least one vertex\marg{explain more?} which represents a hyperplane separating $\tilde b$ and~$\gamma.\tilde b$, and conversely every such hyperplane appears as a vertex of at least one of the simplices.
Thus the trace of the base simplex under the action of $\gamma_1 \gamma_2\gamma_3\ldots$ and the set of hyperplanes separating $\tilde b$ and $\gamma.\tilde b$ are at Hausdorff distance~1 in~$\mathcal C\widetilde {Y'}$.

This implies that, if $\gamma=\gamma_1\cdot\ldots\cdot\gamma_k$ and $\gamma=\gamma'_1\cdot\ldots\cdot \gamma'_k$ are two different representatives of the same minimal length, then the traces of the base simplex under these two words are at Hausdorff distance at most~2 in~$\mathcal C\widetilde {Y'}$.
However, according to Theorem~A(2) of~\cite{BehrstockHagenSisto}, there is such a word for which the trace of the base simplex is at Hausdorff distance~1 from a \emph{geodesic} in~$\mathcal C\widetilde {Y'}$.
In summary, the trace of the base simplex under the action of the normal form word representing~$\gamma$ stays at Hausdorff distance~3 from a geodesic in~$\mathcal C \widetilde {Y'}$ between points of~$\mathcal P$ and $\gamma.\mathcal P$.

By exactly the same argument, we have more generally that the sequence of simplices $\gamma_1\cdot\ldots\cdot \gamma_i.\mathcal P$, $\ldots$, $\gamma_1\cdot\ldots\cdot\gamma_j.\mathcal P$ in~$\mathcal C \widetilde {Y'}$ (for $1\leqslant i<j\leqslant k$) is uniformly close to a geodesic between points of $\gamma_1\cdot\ldots\cdot \gamma_i.\mathcal P$ and $\gamma_1\cdot\ldots\cdot\gamma_j.\mathcal P$.
We can conclude that the geodesic words hypothesis is satisfied with~$R=3$.

Now we need to check the hypothesis that interesting loxodromic actions exist. By Lemma~\ref{L:NonPaObvious} it suffices to construct a word with letters in~$\mathcal S$ which
is read along
a \emph{loop} in the finite state automaton
and whose action moves the base-simplex~$\mathcal P$ by
more than $5\cdot R$, i.e.\ by more than 15.

Here is a way to perform this construction: since the automaton is recurrent, we can choose a finite family of words over the alphabet~$\mathcal S$, one for every ordered pair of states, tracing out a path in the FSA from the first state to the second.
Since we chose only finitely many such words, there exists some~$\delta>0$ such that all the words move~$\mathcal P$ by at most~$\delta$.
Now take an element~$\gamma$ of~$\pi_1(Y)$ whose action action moves~$\mathcal P$ by at least~$5\cdot R+\delta$ -- this exists, since~$\mathcal C\widetilde{Y'}$ is of infinite diameter. Let $w_1$ be the normal form word representing~$\gamma$.
Let $S_1$ be the state of the automaton reached from the start state after reading the first letter of~$w_1$, and let $S_2$ be the state attained after reading the whole word~$w_1$. Let $w_2$ be the word from our finite family that allows us to move from $S_2$ to~$S_1$. Finally, let $w$ be the word obtained by removing the first letter from the concatenated word $w_1w_2$. This word~$w$ traces out a loop in the automaton which passes through the states $S_1$ and~$S_2$, and it still moves the base simplex by at least~$5\cdot R$.
\end{proof}

{\bf Acknowledgements } I thank the following people for helpful remarks and conversations: Sandrine Caruso, Matthieu Calvez, Vincent Guirardel, Alessandro Sisto, Camille Horbez, Saul Schleimer, Thierry Coulbois, Lee Mosher, Alexandre Martin, Hamish Short, Serge Cantat, Christophe Dupont.
This research was supported by the grant ANR LAM (ANR-10-JCJC-0110).


TITLE: Zsigmondy's Theorem Generalization
QUESTION [3 upvotes]: Zsigmondy's Theorem states that if $a>b>0$ are coprime integers then for any integer $n\geq 1$ there is a prime $p$ that divides $a^n-b^n$ and does not divide $a^k-b^k$ for any positive integer $k<n$ with the exceptions $n=a-b=1$, $n=2$ and $a+b$ is a power of $2$, and $n=6, a=2, b=1$. This also works if we replace $a^n-b^n$ with $a^n+b^n$.
I was wondering if there are any generalizations of this in the following direction: let $u,v,a,b\in \mathbb{Z}$ such that $a>b>0$, $u,v\neq 0$ such that $\gcd(ua, vb)=1$. Is it the case that (with finitely many or trivial exceptions) for any $n\geq 1$ there is a prime $p$ such that $p$ divides $ua^n+vb^n$ but $p$ does not divide $ua^k+vb^k$ for any $k<n$?
Thank you!

REPLY [2 votes]: Given an integer sequence $(s_n)_{n \in \mathbb{N}}$, a prime number $p$ is said to be a primitive divisor of the $n$th term $s_n$ if $p$ divides $s_n$, but $p$ does not divide any $s_m$, with $m < n$.
Thus Zsigmondy's Theorem determines all the terms of the sequence $(a^n - b^n)_{n \in \mathbb{N}}$ (and $(a^n + b^n)_{n \in \mathbb{N}}$) that do not have a primitive divisor. This has been generalized to Lucas and Lehmer sequences, see "Yu. Bilu, G. Hanrot and P.M. Voutier, Existence of Primitive Divisors of Lucas and Lehmer Numbers" (https://hal.inria.fr/inria-00072867/document).
Unfortunately, characterizing the terms without primitive divisors of more general linear recurrences, like $(ua^n + vb^n)_{n \in \mathbb{N}}$, seems currently out of reach.


TITLE: How many parameter-free definable subsets are there of the structure $(\mathbb{R}, *)$?
QUESTION [1 upvotes]: This is related to a question where I asked how many subsets of $\mathbb{R}$ are parameter-free definable in the structure $(\mathbb{R}, +)$. Now, I am asking how many subsets of $\mathbb{R}$ are parameter-free definable in $(\mathbb{R}, *)$. I believe there are only 32 of them. Is this correct?

REPLY [4 votes]: A good first step, which is almost always easier, is to count automorphism orbits. (Note that this is also how the answer to your previous question went.)
In the structure $(\mathbb{R};*)$, this is easy to do: the orbits are exactly $\{0\}$, $\{1\}$, $\{-1\}$, $\mathbb{R}_{>0}\setminus\{1\}$, and $\mathbb{R}_{<0}\setminus\{-1\}$. Checking that the latter two are in fact orbits is a bit annoying, but it's not hard. My suggestion is to first think about the orbits of the structure $(\mathbb{R};+)$, which is isomorphic to $(\mathbb{R}_{>0};*)$ and is easier to think about.
This means that there are exactly $32$ automorphism-closed subsets of $(\mathbb{R};*)$. Since every parameter-freely-definable set is automorphism-closed, this gives an upper bound for the OP; it's easy to check that in fact each of the five orbits above (and hence each automorphism-closed set) is parameter-freely definable, so we're done.