which is a contradiction. Therefore there exists a unique $n(a,b) \in [0, n^*]$ such that $b_{n(a,b)} \in [a, b]$ and $\beta(b_{n(a,b)}) > b$. If we had $w([a, b]) \neq b_{n(a,b)}$, then since $\beta([a, b] \setminus \{w([a, b])\}) \subseteq [a, b]$, we would have $\beta(b_{n(a,b)}) \in [a, b]$, which contradicts $\beta(b_{n(a,b)}) > b$. Therefore $w([a, b]) = b_{n(a,b)}$.

**Subcase (2.2).** Suppose $\exists n \in [n^* + 1, l] : b_n \in [a, b]$ and $\beta(b_n) < a$. Let's show that there is a unique such $n$. Suppose that $n_1 > n_2$ both satisfy the condition. Since, $n_2 > n_1$, we have $n_2 - 1 \ge n_1$ and $n_2 \ge n^* + 2$, and since $(b_n)_{n \in \mathbb{N}}$ is strictly increasing, we have

$$a > \beta(b_{n_2}) \ge b_{n_2-1} \ge b_{n_1} \ge a,$$

which is a contradiction. Therefore there exists a unique $n'(a,b) \in [n^* + 1, l]$ such that $b_{n'(a,b)} \in [a, b]$ and $\beta(b_{n'(a,b)}) > b$. If we had $w([a, b]) \neq b_{n'(a,b)}$, then since $\beta([a, b] \setminus \{w([a, b])\}) \subseteq [a, b]$, we would have $\beta(b_{n'(a,b)}) \in [a, b]$, which contradicts $\beta(b_{n'(a,b)}) > b$. Therefore $w([a, b]) = b_{n'(a,b)}$.

Let's show that subcases 2.1 and 2.1 are disjoint. Suppose the contrary. Then

$$a > \beta(b_{n'(a,b)}) \ge b_{n'(a,b)-1} > \beta(b_{n'(a,b)-1}) \ge b_{n'(a,b)-2} > \dots \\ > \beta(b_{n^*+2}) \ge b_{n^*+1} \ge \beta(b_{n^*}) > b_{n^*} \ge \beta(b_{n^*-1}) > \dots > \beta(b_{n(a,b)}) > b,$$

which is a contradiction.

**Subcase (2.3).** Suppose $\forall n \in [0, n^*] : (b_n \in [a, b] \Rightarrow \beta(b_n) \le b)$ and $\forall n \in [n^* + 1, l] : (b_n \in [a, b] \Rightarrow \beta(b_n) \ge a)$. There is no additional constraint in this subcase, we can choose $w([a, b])$ arbitrarily from $[a, b]$.

**Conversely.** If $l \ge 0$, $\{b_n\}_{n \in [0, l]}$ is a strictly increasing sequence, $\beta : \mathbb{N} \to \mathbb{N}$ is a function such that $\mathbb{N} \setminus \{b_n\}_{n \in [0, l]}$ are the fixed points of $\beta$, $n^* \in [-1, l-1]$, $\forall m \le n^* : b_m < \beta(b_m) \le b_{m+1}$, $\beta(b_{n^*+1}) < b_{n^*+1}$, $\forall m \in [n^* + 2, l] : b_{m-1} \le \beta(b_m) < b_m$, and

$$w = \begin{cases} \text{Int}_{\omega,*}(\mathbb{N}) & \to \mathbb{N} \\ [a, b] & \mapsto b_{n(a,b)} \text{ if } \exists n \in [0, n^*] : b_n \in [a, b] \text{ and } \beta(b_n) > b \\ [a, b] & \mapsto b_{n'(a,b)} \text{ if } \exists n \in [n^* + 1, l] : b_n \in [a, b] \text{ and } \beta(b_n) < a, \\ [a, b] & \mapsto \text{any element of } [a, b] \text{ otherwise} \end{cases}$$

then $\forall a \le b \in [a, b] : \beta([a, b] \setminus \{w([a, b])\}) \subseteq [a, b]$. Indeed, let $a \le b \in \mathbb{N}$. Because of the uniqueness properties of $b_{n(a,b)}$ and $b_{n'(a,b)}$ (when they exist) and the disjointness of subcases 2.1 and 2.2, any $x \in [a, b] \setminus \{w([a, b])\}$ is either a fixed point (in which case $\beta(x) = x \in [a, b]$), or satisfies $x = b_n$ with $n \in [0, n^*]$ and $\beta(b_n) \le b$, in which case, since $b_n < \beta(b_n)$, we have $a \le x = b_n < \beta(b_n) = \beta(x) \le b$, or satisfies $x = b_n$ with $n \ge n^* + 1$ and $\beta(b_n) \ge a$, in which case, since $\beta(b_n) < b_n$, we have $a \le \beta(b_n) = \beta(x) < b_n = x \le b$.
**Case (3).** Suppose $\forall m \le n^* : b_m < \beta(b_m) \le b_{m+1}$ and $\beta(b_{n^*+1}) > b_{n^*+2}$. By assertion 4.4, we have $\forall m \ge n^* + 2 : b_{m-1} \le \beta(b_m) < b_m$. Then the treatment from now on is analogous to case 2 (since we haven't used the conditions $\beta(b_{n^*+1}) < b_{n^*+1}$ or $\beta(b_{n^*+1}) > b_{n^*+2}$) with the same necessary and sufficient form of the function $w$. $\square$

Requiring that for such functions, $\beta(w(\llbracket a, b \rrbracket)) \notin \llbracket a, b \rrbracket$ for all $a \le b \in \mathbb{N}$, leads to

**Corollary 4.5.1.** Let $\beta : \mathbb{N} \to \mathbb{N}$ and $w : \mathrm{Int}_{\omega,*}(\mathbb{N}) \to \mathbb{N}$ be two functions such that

$$ \forall \llbracket a, b \rrbracket \in \mathrm{Int}_{\omega,*}(\mathbb{N}) : \quad w(\llbracket a, b \rrbracket) \in \llbracket a, b \rrbracket \\ \text{and } \beta(\llbracket a, b \rrbracket \setminus \{w(\llbracket a, b \rrbracket)\}) \subseteq \llbracket a, b \rrbracket \text{ and } \beta(w(\llbracket a, b \rrbracket)) \notin \llbracket a, b \rrbracket. $$

Then either

**Case (1).** $\beta : \begin{cases} \mathbb{N} \to \mathbb{N} \\ n \mapsto n+1 \end{cases}$ and $w : \begin{cases} \mathrm{Int}_{\omega,*}(\mathbb{N}) \to \mathbb{N} \\ \llbracket a, b \rrbracket \mapsto b \end{cases}$

**Case (2).** There exists $n^* \ne u \in \mathbb{N}$ such that $\beta : \begin{cases} \mathbb{N} \to \mathbb{N} \\ n \mapsto n+1 \text{ for } n < n^* \\ n^* \mapsto u \\ n \mapsto n-1 \text{ for } n > n^* \end{cases}$ and

$$ w : \begin{cases} \mathrm{Int}_{\omega,*}(\mathbb{N}) \to \mathbb{N} \\ \llbracket a, b \rrbracket \mapsto b \text{ if } b \in \llbracket 0, n^* \rrbracket. \\ \llbracket a, b \rrbracket \mapsto a \text{ if } a \ge n^* + 1 \end{cases}. $$

*Démonstration.* Notice that for all $a \in \mathbb{N}$, $\beta(w(\llbracket a, a \rrbracket)) \notin \llbracket a, a \rrbracket$ implies that $\beta(a) \ne a$, and so the sequence of non-fixed points of $\beta$ in strictly increasing order is $\{b_n\}_{n \in \mathbb{N}} = \{n\}_{n \in \mathbb{N}}$. We can then apply proposition 4.5.2. $\square$

# 4.6 Functions with a maximal number of finite invariant supersets

## 4.6.1 Solution to the general problem

**Proposition 4.6.1.** Let $\alpha : I \to I$ and $G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I)$. Then the following conditions are equivalent

$$ 1. \forall I^* \in \mathcal{P}_{\omega,*}(I) : I^* \subseteq G(I^*) \text{ and } \alpha(G(I^*)) \subseteq G(I^*). $$
2. The orbits of $\alpha$ are finite and there exists $H : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I)$ such that

$$ \forall I^* \in \mathcal{P}_{\omega,*}(I) : G(I^*) = \bigcup_{a \in I^* \cup H(I^*)} \mathcal{O}_{\alpha}^{+}(a). $$

Démonstration. (1) ⇒ (2). Let $a \in I$. We have $\alpha(a) \in G(\{a\})$ since $a \in G(\{a\})$ and $\alpha(G(\{a\})) \subseteq G(\{a\})$. By immediate induction, we have $\mathcal{O}_{\alpha}^{+}(a) \subseteq G(\{a\})$. Since $G(\{a\})$ is finite, this implies that $\mathcal{O}_{\alpha}^{+}(a)$ is finite. Therefore the orbits of $\alpha$ are finite. Furthermore, let $H(I^*) = G(I^*)$ for all $I^* \in \mathcal{P}_{\omega,*}(I)$. Let $I^* \in \mathcal{P}_{\omega,*}(I)$. We have $I^* \cup H(I^*) = I^* \cup G(I^*) = G(I^*)$. Let $a \in G(I^*)$. We have $\alpha(a) \in G(I^*)$ since $a \in G(I^*)$ and $\alpha(G(I^*)) \subseteq G(I^*)$. By immediate induction, we have $\mathcal{O}_{\alpha}^{+}(a) \subseteq G(I^*)$. Therefore $\bigcup_{a \in G(I^*)} \mathcal{O}_{\alpha}^{+}(a) \subseteq G(I^*)$. The reverse inclusion is obvious since $a \in \mathcal{O}_{\alpha}^{+}(a)$ for all $a \in G(I^*)$.

(2) ⇒ (1). Let $I^* \in \mathcal{P}_{\omega,*}(I)$. To show that $I^* \subseteq G(I^*)$, let $a \in I^*$. We have $a \in \mathcal{O}_{\alpha}^{+}(a) \subseteq G(I^*)$. Therefore $I^* \subseteq G(I^*)$. To show that $\alpha(G(I^*)) \subseteq G(I^*)$, let $a \in G(I^*)$. We have

$$ \alpha(a) \in \alpha \left( \bigcup_{a \in I^* \cup H(I^*)} \mathcal{O}_{\alpha}^{+}(a) \right) = \bigcup_{a \in I^* \cup H(I^*)} \alpha \left( \mathcal{O}_{\alpha}^{+}(a) \right) \subseteq \bigcup_{a \in I^* \cup H(I^*)} \mathcal{O}_{\alpha}^{+}(a). $$

Therefore $\alpha(G(I^*)) \subseteq G(I^*)$. $\square$

<figure><img src="image_8.png" /></figure>

### 4.6.2 Solution to a more constrained problem in $\mathbb{N}$

The following proposition gives a characterization of the functions $\alpha : \mathbb{N} \to \mathbb{N}$ and $G : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathcal{P}_{\omega,*}(\mathbb{N})$ that satisfy the conditions of proposition 4.6.1, plus the additional hypothesis that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : \max(G(I^*)) \in \alpha(I^*)$.

**Proposition 4.6.2.** Let $\alpha : \mathbb{N} \to \mathbb{N}$ and $G : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathcal{P}_{\omega,*}(\mathbb{N})$ such that

$$ \forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : I^* \subseteq G(I^*), \alpha(G(I^*)) \subseteq G(I^*) \text{ and } \max(G(I^*)) \in \alpha(I^*). $$

Then $\alpha$ admits an infinite number of fixed points, and letting this sequence be $\{b_n\}_{n \in \mathbb{N}}$ in strictly increasing order, there exists a function $j : \mathbb{N} \to \mathbb{N}$ such that

$$ \forall a \in \mathbb{N} : \alpha(a) = b_{j(a)} $$

and

$$ \forall a \in \mathbb{N} : j(a) = n \text{ if } \exists n \in \mathbb{N} : a = b_n $$

$$ j(a) \geq r(a) \text{ if } a \notin \{b_n\}_{n \in \mathbb{N}} $$

where $r(a) := \min\{n \in \mathbb{N} : b_n > a\}$, and there exists a function $H : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathcal{P}_{\omega}(\mathbb{N})$ such that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : G(I^*) = \bigcup_{a \in I^* \cup H(I^*)} \{a, \alpha(a)\}$ and
∀I* ∈ P<sub>ω,*</sub>(N) : ∃a ∈ I* : ∀x ∈ H(I*) : j(x) ≤ j(a). Conversely, any such α and G are valid solutions.

**Démonstration. Direct implication.** First, let's show that

$$ \forall n \in \mathbb{N} : \alpha(\alpha(n)) = \alpha(n) \geq n \qquad (4.5) $$

We have ∀n ∈ N : max(G({n})) ∈ α({n}), so α(n) = max(G({n})) ∈ G({n}). Let n ∈ N. We have α(α(n)) ∈ G({n} since α(n) ∈ G({n}) (we use the hypothesis α(G(I*)) ⊆ G(I*) for I* = {n}), and so α(α(n)) ≤ α(n) since α(n) = max(G({n})). Moreover, we have n ∈ {n} ⊆ G({n}), and so n ≤ max(G({n})) = α(n). Replacing n by α(n), we have ∀n ∈ N : α(α(n)) ≥ α(n).

Therefore ∀n ∈ N : α(α(n)) = α(n) ≥ n, and so assertion 4.5 holds.

Notice that if α is injective, then by assertion 4.5 we have ∀n ∈ N : α(n) = n, and α is the identity function. Otherwise, α admits a sequence of fixed points {α(n)}_{n∈N} tending to infinity since ∀n ∈ N : α(n) ≥ n. Let {b_n}_{n∈N} be the sequence of all fixed points of α in strictly increasing order. Let b_{-1} = -1 and extend α by setting α(-1) = -1. Then ∀n ∈ N ∪ {-1} : ∀m ∈ [b_n+1, b_{n+1}-1] : ∃k ≥ n+1 : α(m) = b_k since α(m) is a fixed point and α(m) ≥ m > b_n. Moreover, we have r(m) ≤ n+1 since b_{n+1} > m, and so r(m) ≤ k. Therefore we can set j(m) = n if m = b_n and j(m) = k if m ∈ [b_n+1, b_{n+1}-1] for some n ∈ N ∪ {-1}.

Moreover, from proposition 4.6.1, there exists a function H : P<sub>ω,*</sub>(N) → P<sub>ω</sub>(N) such that ∀I* ∈ P<sub>ω,*</sub>(N) : G(I*) = ⋃<sub>a∈I*∪H(I*)</sub> O<sub>α</sub><sup>+</sup>(a) = ⋃<sub>a∈I*∪H(I*)</sub> {a, α(a)}. It's easy to show that the condition ∀I* ∈ P<sub>ω,*</sub>(N) : max(G(I*)) ∈ α(I*) means that ∀I* ∈ P<sub>ω,*</sub>(N) : ∃a ∈ I* : ∀x ∈ H(I*) : j(x) ≤ j(a).

**Conversely.** Given a function α : N → N which admits an infinite number of fixed points {b_n}_{n∈N} in strictly increasing order, such that there exists a function j : N → N such that

$$ \forall a \in \mathbb{N} : \alpha(a) = b_{j(a)} $$

and

$$ \forall a \in \mathbb{N} : j(a) = n \text{ if } \exists n \in \mathbb{N} : a = b_n $$

$$ j(a) \geq r(a) \text{ if } a \notin \{b_n\}_{n \in \mathbb{N}} $$

where r(a) := min{n ∈ N : b_n > a}, and such that there exists a function H : P<sub>ω,*</sub>(N) → P<sub>ω</sub>(N) such that ∀I* ∈ P<sub>ω,*</sub>(N) : G(I*) = ⋃<sub>a∈I*∪H(I*)</sub> {a, α(a)} and ∀I* ∈ P<sub>ω,*</sub>(N) : ∃a ∈ I* : ∀x ∈ H(I*) : j(x) ≤ j(a), then it's easy to check that ∀I* ∈ P<sub>ω,*</sub>(N) : α(G(I*)) ⊆ G(I*) and max(G(I*)) ∈ α(I*). □
**Remark 4.6.1.** If $\alpha$ is assumed to be bijective, then we can also use proposition 4.7.7 to deduce $\alpha = \mathrm{Id}$. Indeed, suppose that $\alpha : \mathbb{N} \to \mathbb{N}$ and $G : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathcal{P}_{\omega,*}(\mathbb{N})$ are such that

$$ \forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : I^* \subseteq G(I^*), \alpha(G(I^*)) \subseteq G(I^*) \text{ and } \max(G(I^*)) \in \alpha(I^*), $$

and let $\beta : \begin{cases} \mathbb{N} \to \mathbb{N} \\ n \mapsto n+1 \end{cases}$, $\phi = \beta \circ \alpha$, and for all $I^* \in \mathcal{P}_{\omega,*}(\mathbb{N})$, $u(I^*) \in I^*$ such that $\alpha(u(I^*)) = \max(G(I^*))$.

Then since $P_2(\phi, G, u)$ is true and $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : \exists a \in G(I^*) : |\mathcal{O}_{\beta}^+(a)| = +\infty$, we have $\alpha = \mathrm{Id}$.

In the following proposition, we require furthermore that $G : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathrm{Int}_{\omega,*}(\mathbb{N})$.

**Proposition 4.6.3.** Let $\alpha : \mathbb{N} \to \mathbb{N}$ and $G : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathrm{Int}_{\omega,*}(\mathbb{N})$ such that

$$ \forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : I^* \subseteq G(I^*), \alpha(G(I^*)) \subseteq G(I^*) \text{ and } \max(G(I^*)) \in \alpha(I^*). $$

Then $\alpha$ admits an infinite number of fixed points, and if this sequence is $\{b_n\}_{n \in \mathbb{N}}$ in strictly increasing order, there exists a function $j : \mathbb{N} \to \mathbb{N}$ such that

$$ \forall a \in \mathbb{N} : \alpha(a) = b_{j(a)}, $$

$$ \forall a \in \mathbb{N} : j(a) = n \text{ if } \exists n \in \mathbb{N} : a = b_n $$

$$ j(a) = r(a) \text{ if } a > b_0 \text{ and } a \notin \{b_n\}_{n \in \mathbb{N}} $$

where $r(a) := \min\{n \in \mathbb{N} : b_n > a\}$, and

$$ j(0) \geq j(1) \cdots \geq j(b_0 - 1), $$

and there exists a function $u : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathbb{N}$ such that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : G(I^*) = [u(I^*), \max\{\alpha(a)\}_{a \in I^*}]$, and

$$ \forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : u^*(I^*) := \min\{n \le b_0 : \max\{\alpha(a)\}_{a \in I^*} \ge \alpha(n)\} \le u(I^*) \le \min(I^*), $$

Conversely, any such $\alpha$ and $G$ are valid solutions.

**Démonstration. Direct implication.** $\alpha$ and $G$ satisfy of course all the previous properties of proposition 4.6.2.

For all $I^* \in \mathcal{P}_{\omega,*}(\mathbb{N})$, we let $[u(I^*), v(I^*)] := G(I^*)$. Assume by way of contradiction that $v(I^*) \ne \max\{\alpha(a)\}_{a \in I^*}$. We have $\forall a \in I^* \subseteq G(I^*) : \alpha(a) \le v(I^*)$, so $\max\{\alpha(a)\}_{a \in I^*} \le v(I^*)$. Since $v(I^*) \ne \max\{\alpha(a)\}_{a \in I^*}$, we have
$\max\{\alpha(a)\}_{a \in I^*} < v(I^*)$ which is a contradiction since $v(I^*) = \max(G(I^*)) \in \alpha(I^*)$. So $v(I^*) = \max\{\alpha(a)\}_{a \in I^*}$.

Applying this to $I^* = \{b_n, b_{n+1}\}$ for $n \in \mathbb{N}$ gives $G(\{b_n, b_{n+1}\}) = [u(\{b_n, b_{n+1}\}), b_{n+1}]$ where $u(\{b_n, b_{n+1}\}) \le b_n$, and so $\forall x \in [b_n, b_{n+1}] : \alpha(x) \le b_{n+1}$ since $G(I^*)$ is preserved by $\alpha$. Hence $\forall x \in ]b_n, b_{n+1}] : \alpha(x) = b_{n+1}$ (since $j(x) \ge n+1$ by proposition 4.6.2).

Applying it for $I^* = \{x\}$ for $x \in [0, b_0[$ gives $G(I^*) = [u(\{x\}), \alpha(x)]$ where $u(\{x\}) \le x$. Since $\alpha(x)$ is a fixed point, we have $\alpha(x) \ge b_0$. Therefore, $\forall y \in [a, b_0[: \alpha(y) \le \alpha(x)$ since $G(I^*)$ is preserved by $\alpha$. So $\alpha(0) \ge \alpha(1) \ge \alpha(b_0 - 1)$, which is equivalent to $j(0) \ge j(1) \ge \dots \ge j(b_0 - 1)$. Moreover, for all $I^* \in \mathcal{P}_{\omega,*}(\mathbb{N})$, we have $u(I^*) \le \min(I^*)$ since $I^* \subseteq G(I^*)$.

Furthermore, for all $I^* \in \mathcal{P}_{\omega,*}(\mathbb{N})$, the set $\{n \le b_0 : \max\{\alpha(a)\}_{a \in I^*} \ge \alpha(n)\}$ is non-empty (it contains $b_0$), and letting $u^*(I^*) := \min\{n \le b_0 : \max\{\alpha(a)\}_{a \in I^*} \ge \alpha(n)\}$, we have necessarily $u(I^*) \ge u^*(I^*)$. Indeed, if $u(I^*) > b_0$, the inequality is obvious. Otherwise, it is true since $\alpha(u(I^*)) \in G(I^*)$ (since $\alpha(G(I^*)) \subseteq G(I^*)$ and $u(I^*) \in G(I^*)$), and therefore $\alpha(u(I^*)) \le \max(G(I^*)) = \max\{\alpha(a)\}_{a \in I^*}$.

**Conversely.** Given a function $\alpha : \mathbb{N} \to \mathbb{N}$ which admits an infinite number of fixed points $\{b_n\}_{n \in \mathbb{N}}$ in strictly increasing order, such that there exists a function $j : \mathbb{N} \to \mathbb{N}$ such that

$$ \forall a \in \mathbb{N} : \alpha(a) = b_{j(a)} $$

and

$$ \forall a \in \mathbb{N} : j(a) = n \text{ if } \exists n \in \mathbb{N} : a = b_n $$

$$ j(a) = r(a) \text{ if } a > b_0 \text{ and } a \notin \{b_n\}_{n \in \mathbb{N}} $$

where $r(a) := \min\{n \in \mathbb{N} : b_n > a\}$, and

$$ j(0) \ge j(1) \ge \dots \ge j(b_0 - 1), $$

and such that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : G(I^*) = [u(I^*), \max\{\alpha(a)\}_{a \in I^*}]$, where $u : \mathcal{P}_{\omega,*}(\mathbb{N}) \to \mathbb{N}$ is a function such that

$\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : u^*(I^*) := \min\{n \le b_0 : \max\{\alpha(a)\}_{a \in I^*} \ge \alpha(n)\} \le u(I^*) \le \min(I^*)$, then it's clear that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : \max(G(I^*)) \in \alpha(I^*)$. To check that $\forall I^* \in \mathcal{P}_{\omega,*}(\mathbb{N}) : \alpha(G(I^*)) \subseteq G(I^*)$, we take $I^* \in \mathcal{P}_{\omega,*}(\mathbb{N})$ and $x \in G(I^*)$, and distinguish between the cases $x \ge b_0$ and $x < b_0$. In the first case, since $x \le \max\{\alpha(a)\}_{a \in I^*}$, $\max\{\alpha(a)\}_{a \in I^*}$ is a fixed point, and $x \ge b_0$, then it follows that $u(I^*) \le x \le \alpha(x) \le \max\{\alpha(a)\}_{a \in I^*}$. In the second case, we have $u^*(I^*) \le u(I^*) \le x < b_0$, therefore $\alpha(x) \le \alpha(u^*(I^*)) \le \max\{\alpha(a)\}_{a \in I^*}$ since $\alpha$ is non-increasing on $[0, b_0 - 1]$ and by the definition of $u^*(I^*)$. Moreover, since $\alpha(x)$ is a fixed point, it is obvious that $\alpha(x) \ge b_0 > x \ge u(I^*)$. Therefore we are done in both cases and it follows that $\alpha(G(I^*)) \subseteq G(I^*)$. $\square$
## 4.7 Functions with a maximal number of finite internally-1-quasi-invariant supersets

Below, we define two similar predicates (in the sense of propositions depending on mathematical objects) that model the property of direct image preservation by $\phi: I \to I$ of finite supersets of finite subsets of $I$, up to one element, denoted by $P_1(\phi, G, u)$ and $P_2(\phi, G, u)$. We will be concerned with these predicates in the following three subsections.

**Definition 4.7.1.** We say that a 3-tuple $(\phi: I \to I, G: P_{\omega,*}(I) \to P_{\omega,*}(I), u: P_{\omega,*}(I) \to I)$ satisfies property $P_1(\phi, G, u)$ if

$$ \forall I^* \in P_{\omega,*}(I) : u(I^*) \in G(I^*), I^* \subseteq G(I^*) \text{ and } \phi(G(I^*) \setminus \{u(I^*)\}) \subseteq G(I^*). $$

**Definition 4.7.2.** We say that a 3-tuple $(\phi: I \to I, G: P_{\omega,*}(I) \to P_{\omega,*}(I), u: P_{\omega,*}(I) \to I)$ satisfies property $P_2(\phi, G, u)$ if

$$ \forall I^* \in P_{\omega,*}(I) : u(I^*) \in I^*, I^* \subseteq G(I^*) \text{ and } \phi(G(I^*) \setminus \{u(I^*)\}) \subseteq G(I^*). $$

The following simple lemma is often used (without mention) in the paper.

**Lemma 4.7.1.** Let $I$ be an infinite set and $(\phi: I \to I, G: P_{\omega,*}(I) \to P_{\omega,*}(I), u: P_{\omega,*}(I) \to I)$ a 3-tuple satisfying $P_1(\phi, G, u)$. Then we have

$$ \forall I^* \in P_{\omega,*}(I) : (|O_{\phi}^{+}(u(I^*))| = \infty \Rightarrow \phi(u(I^*)) \notin G(I^*) \text{ and } \phi(u(I^*)) \notin I^*). $$

*Démonstration.* Let $I^* \in P_{\omega,*}(I)$ such that $|O_{\phi}^{+}(u(I^*))| = \infty$. From lemma 4.3.1, $u(I^*)$, $\phi(u(I^*)$, $\phi^2(u(I^*))$, $\dots$ must be distinct. In particular, $\forall n \ge 1$, $\phi^n(u(I^*)) \ne u(I^*)$. Thus we have $\phi(u(I^*)) \notin G(I^*)$ (otherwise we would have $O_{\phi}^{+}(u(I^*)) \subseteq G(I^*)$ which is impossible since $G(I^*)$ is finite and $|O_{\phi}^{+}(u(I^*))| = \infty$). Since $I^* \subseteq G(I^*)$, this implies that $\phi(u(I^*)) \notin I^*$. $\square$

We also have

**Lemma 4.7.2.** Let $I$ be an infinite set and $(\phi: I \to I, G: P_{\omega,*}(I) \to P_{\omega,*}(I), u: P_{\omega,*}(I) \to I)$ a 3-tuple satisfying $P_2(\phi, G, u)$. Then we have

$$ (\forall I^* \in P_{\omega,*}(I) : |O_{\phi}^{+}(u(I^*))| = \infty) \Rightarrow (\forall b \in I : \forall m \in \mathbb{N} : u(\{b, \dots, \phi^m(b)\} = \phi^m(b)). $$

*Démonstration.* Suppose that $\forall I^* \in P_{\omega,*}(I) : |O_{\phi}^{+}(u(I^*))| = \infty$. Let $b \in I$ and $m \in \mathbb{N}$. Since we should have $u(\{b, \dots, \phi^m(b)\}) \in \{b, \dots, \phi^m(b)\}$ and $\phi(u(\{b, \dots, \phi^m(b)\})) \notin \{b, \dots, \phi^m(b)\}$ by lemma 4.7.1, we have necessarily $u(\{b, \dots, \phi^m(b)\}) = \phi^m(b)$. $\square$
### 4.7.1 Solution to problem $P_1(\phi, G, u)$

We first prove the following structural proposition.

**Proposition 4.7.1.** Let $I$ be an infinite set and $\beta: I \to I$.

Let $G: \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I)$ and $v: \mathcal{P}_{\omega,*}(I) \to I$. Then

$P_1(\beta, G, v) \Leftrightarrow$ there exist three functions $H, \bar{H}, \tilde{H}: \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I)$ such that for all $I^* \in \mathcal{P}_{\omega,*}(I)$, $I^* \subseteq H(I^*) \cup \bar{H}(I^*) \cup \tilde{H}(I^*)$, $H(I^*) \subseteq \{a \in I: |\mathcal{O}_{\beta}^+(a)| = +\infty\}$, $\bar{H}(I^*)$, $\tilde{H}(I^*) \subseteq \{a \in I: |\mathcal{O}_{\beta}^+(a)| < +\infty\}$, and

(a) $\exists z \in G(I^*) : |\mathcal{O}_{\beta}^+(z)| = +\infty$ and

$$ 
\left\{ 
\begin{array}{l}
H(I^*) \neq \emptyset \\
\bar{H}(I^*) = \emptyset \\
G(I^*) = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^+(a)) \cup (\bigcup_{a \in H(I^*)} \{a, \beta(a), \beta^2(a), \dots, \xi_{\beta}(H(I^*))\}) \\
v(I^*) = \xi_{\beta}(H(I^*))
\end{array}
\right. 
$$

or

(b) $\forall a \in G(I^*) : |\mathcal{O}_{\beta}^+(a)| < +\infty$ and

$$ 
\left\{ 
\begin{array}{l}
H(I^*) = \emptyset \\
\bar{H}(I^*) \neq \emptyset \\
G(I^*) = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^+(a)) \cup (\bigcup_{a \in \bar{H}(I^*)} \{a, \beta(a), \beta^2(a), \dots, v(I^*)\})
\end{array}
\right. 
$$

**Démonstration.** ($\Rightarrow$) : Suppose $P_1(\beta, G, v)$.

Let

$$ H: \left\{ \begin{array}{l} \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I) \\ I^* \mapsto \{a \in G(I^*) : |\mathcal{O}_{\beta}^+(a)| = +\infty\} \end{array} \right. , $$

$$ \bar{H} : \left\{ \begin{array}{l} \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I) \\ I^* \mapsto \{a \in G(I^*) : |\mathcal{O}_{\beta}^+(a)| < +\infty \text{ and } v(I^*) \in \mathcal{O}_{\beta}^+(a)\} \end{array} \right. $$

and

$$ \tilde{H} : \left\{ \begin{array}{l} \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I) \\ I^* \mapsto \{a \in G(I^*) : |\mathcal{O}_{\beta}^+(a)| < +\infty \text{ and } v(I^*) \notin \mathcal{O}_{\beta}^+(a)\} \end{array} \right. . $$

Let $I^* \in \mathcal{P}_{\omega,*}(I)$. We have $G(I^*) = H(I^*) \cup \bar{H}(I^*) \cup \tilde{H}(I^*)$. Therefore $I^* \subseteq H(I^*) \cup \bar{H}(I^*) \cup \tilde{H}(I^*)$.

(a) Suppose that $\exists z \in G(I^*) : |\mathcal{O}_{\beta}^+(z)| = +\infty$. So $H(I^*) \neq \emptyset$.

Let's show that $v(I^*) = \xi_{\beta}(H(I^*))$. Assume by way of contradiction that $\exists b \in H(I^*) : v(I^*) \notin \mathcal{O}_{\beta}^+(b)$. Then we must have $\mathcal{O}_{\beta}^+(b) \subseteq G(I^*)$,
which is impossible since $|\mathcal{O}_{\beta}^{+}(b)| = +\infty$ and $G(I^*)$ is finite. So $v(I^*) \in \bigcap_{b \in H(I^*)} \mathcal{O}_{\beta}^{+}(b) = \mathcal{O}_{\beta}^{+}(\xi_{\beta}(H(I^*))$. In particular, $|\mathcal{O}_{\beta}^{+}(v(I^*))| = +\infty$ and so $v(I^*) \in H(I^*)$. So there exist $m, n \in \mathbb{N}$ such that $v(I^*) = \beta^m(\xi_{\beta}(H(I^*))$ and $\xi_{\beta}(H(I^*)) = \beta^n(v(I^*))$. This can only work if $m = n = 0$ due to lemma 4.3.1 and therefore $v(I^*) = \xi_{\beta}(H(I^*))$.

Now we must have $\overline{H}(I^*) = \emptyset$ (otherwise there exists $a' \in G(I^*)$ such that $|\mathcal{O}_{\beta}^{+}(a')| < +\infty$ and $v(I^*) = \xi_{\beta}(H(I^*)) \in \mathcal{O}_{\beta}^{+}(z) \cap \mathcal{O}_{\beta}^{+}(a') = \emptyset$ by lemma 4.3.8, a contradiction).

Let's show that $G(I^*) = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^{+}(a)) \cup (\bigcup_{a \in H(I^*)} \{a, \beta(a), \beta^2(a), \dots, \xi_{\beta}(H(I^*))\})$. $P_1(\beta, G, v)$ shows that the inclusion $\supseteq$ is true. Conversely, let $a \in G(I^*)$. We have either $a \in H(I^*)$ or $a \in \tilde{H}(I^*)$. Therefore the inclusion $\subseteq$ is also true.

(b) Suppose that $\forall a \in G(I^*) : |\mathcal{O}_{\beta}^{+}(a)| < +\infty$. So $H(I^*) = \emptyset$ and $\overline{H}(I^*) \neq \emptyset$.

Let's show that $G(I^*) = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^{+}(a)) \cup (\bigcup_{a \in \overline{H}(I^*)} \{a, \beta(a), \beta^2(a), \dots, v(I^*)\})$. $P_1(\beta, G, v)$ shows that the inclusion $\supseteq$ is true. Conversely, let $a \in G(I^*)$. We have $a \in \tilde{H}(I^*)$ or $a \in \overline{H}(I^*)$ and so the inclusion $\subseteq$ is true.

(c) : Suppose that $H, \overline{H}$ and $\tilde{H}$ exist with the desired properties. Let $I^* \in \mathcal{P}_{\omega,*}(I)$.

(a) If $\exists z \in G(I^*) : |\mathcal{O}_{\beta}^{+}(z)| = +\infty$, then $\overline{H}(I^*) = \emptyset$ and so $G(I^*) \supseteq \tilde{H}(I^*) \cup H(I^*) \supseteq I^*$ using the hypotheses. Moreover, we have clearly $v(I^*) \in G(I^*)$ and $\beta(G(I^*) \setminus \{v(I^*)\}) \subseteq G(I^*)$.

(b) If $\forall a \in G(I^*) : |\mathcal{O}_{\beta}^{+}(a)| < +\infty$, we have $H(I^*) = \emptyset$ and we can check similarly that $P_1(\beta, G, v)$ is true. $\square$

The following proposition characterizes the existential problem $\exists G \exists v : P_1(\beta, G, v)$ to $\tilde{P}(\beta)$ in terms of $\tilde{P}(\beta)$.

**Proposition 4.7.2.** Let $I$ be an infinite set and $\beta : I \to I$. Then

$$ (\exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : \exists v : \mathcal{P}_{\omega,*}(I) \to I : P_1(\beta, G, v)) \Leftrightarrow \tilde{P}(\beta). $$

Démonstration. (⇒) : Let $a, b \in I$ such that $|\mathcal{O}_{\beta}^{+}(a)| = |\mathcal{O}_{\beta}^{+}(b)| = +\infty$. Assume by way of contradiction that $\mathcal{O}_{\beta}^{+}(a) \cap \mathcal{O}_{\beta}^{+}(b) = \emptyset$. So $a \neq b$. Let $I^* = \{a, b\}$. Let $G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I)$ and $v : \mathcal{P}_{\omega,*}(I) \to I$ such that $P_1(\beta, G, v)$. Suppose by way of contradiction that $v(I^*) \in \mathcal{O}_{\beta}^{+}(a)$. Then $v(I^*) \notin \mathcal{O}_{\beta}^{+}(b)$ since $\mathcal{O}_{\beta}^{+}(a) \cap \mathcal{O}_{\beta}^{+}(b) = \emptyset$. Using the hypothesis, we obtain $\mathcal{O}_{\beta}^{+}(b) \subseteq G(I^*)$ which is impossible since $G(I^*)$ is finite and $\mathcal{O}_{\beta}^{+}(b)$ is infinite. Therefore $v(I^*) \notin \mathcal{O}_{\beta}^{+}(a)$. But this is also impossible for the same reason. So we must have $\mathcal{O}_{\beta}^{+}(a) \cap \mathcal{O}_{\beta}^{+}(b) \neq \emptyset$.

(c) : Suppose that $\tilde{P}(\beta)$ is true. Let

$$ H : \begin{cases} \mathcal{P}_{\omega,*}(I) & \to \mathcal{P}_{\omega}(I) \\ I^* & \mapsto \{a \in I^* : |\mathcal{O}_{\beta}^{+}(a)| = +\infty\} \end{cases}, $$
$$ \tilde{H} : \left\{ \begin{array}{ll} \mathcal{P}_{\omega,*}(I) & \rightarrow \mathcal{P}_{\omega}(I) \\ I^* & \mapsto \{a \in I^* : |\mathcal{O}_{\beta}^{+}(a)| < +\infty\} \end{array} \right. , $$

$$ G : \left\{ \begin{array}{ll} \mathcal{P}_{\omega,*}(I) & \rightarrow \mathcal{P}_{\omega,*}(I) \\ I^* & \mapsto (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^{+}(a)) \cup (\bigcup_{a \in H(I^*)} \{a, \beta(a), \beta^2(a), \dots, \xi_{\beta}(H(I^*))\}) \end{array} \right. , $$

and

$$ v : \left\{ \begin{array}{ll} \mathcal{P}_{\omega,*}(I) & \rightarrow I \\ I^* & \mapsto \xi_{\beta}(H(I^*)) \text{ if } H(I^*) \neq \emptyset \\ I^* & \mapsto \text{an arbitrary element of } I^* \text{ otherwise} \end{array} \right. , $$

where we used the fact $\mathcal{P}_{\omega,*}(\{a \in I : |\mathcal{O}_{\beta}^{+}(a)| = +\infty\}) \subseteq D_{\beta}$ (see lemma 4.3.9). Then $P_1(\beta, G, v)$ holds. $\square$

### 4.7.2 Solution to problem $P_2(\phi, G, u)$

Proposition 4.7.1 implies, trivially, the following characterization of $P_2(\phi, G, u)$. It is not known to the authors if $P_2(\phi, G, u)$ admits a simpler description.

**Proposition 4.7.3.** Let $I$ be an infinite set and $\beta : I \to I$.

Let $G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I)$ and $v : \mathcal{P}_{\omega,*}(I) \to I$. Then

$P_2(\beta, G, v) \Leftrightarrow$ there exist three functions $H, \overline{H}, \tilde{H} : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega}(I)$ such that for all $I^* \in \mathcal{P}_{\omega,*}(I)$, $I^* \subseteq H(I^*) \cup \overline{H}(I^*) \cup \tilde{H}(I^*)$, $H(I^*) \subseteq \{a \in I : |\mathcal{O}_{\beta}^{+}(a)| = +\infty\}$, $\overline{H}(I^*)$, $\tilde{H}(I^*) \subseteq \{a \in I : |\mathcal{O}_{\beta}^{+}(a)| < +\infty\}$, and

(a) $\exists z \in G(I^*) : |\mathcal{O}_{\beta}^{+}(z)| = +\infty$ and

$$ \left\{ \begin{array}{ll} H(I^*) & \neq \emptyset \\ \overline{H}(I^*) & = \emptyset \\ G(I^*) & = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^{+}(a)) \cup (\bigcup_{a \in H(I^*)} \{a, \beta(a), \beta^2(a), \dots, \xi_{\beta}(H(I^*))\}) \\ v(I^*) & = \xi_{\beta}(H(I^*)) \in I^* \end{array} \right. $$

or

(b) $\forall a \in G(I^*) : |\mathcal{O}_{\beta}^{+}(a)| < +\infty$ and

$$ \left\{ \begin{array}{ll} H(I^*) & = \emptyset \\ \overline{H}(I^*) & \neq \emptyset \\ G(I^*) & = (\bigcup_{a \in \tilde{H}(I^*)} \mathcal{O}_{\beta}^{+}(a)) \cup (\bigcup_{a \in \overline{H}(I^*)} \{a, \beta(a), \beta^2(a), \dots, v(I^*)\}) \\ v(I^*) & \in I^* \end{array} \right. . $$

In what follows, we direct our attention to the existential problem $\exists G \exists u : P_2(\phi, G, u)$, which we try to characterize in terms of a condition on $\phi$. To achieve that, let's first prove
**Proposition 4.7.4.** Let $I$ be an infinite set and $\beta : I \to I$. Then, if $D_\beta = \mathcal{P}_{\omega,*}(I)$ and $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \xi_\beta(I^*) \in I^*$, then $(\exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : \exists v : \mathcal{P}_{\omega,*}(I) \to I : P_2(\beta, G, v))$.

*Démonstration.* Suppose that $D_\beta = \mathcal{P}_{\omega,*}(I)$ and $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \xi_\beta(I^*) \in I^*$. Then, by lemma 4.3.8, and using the previous notations of proposition 4.7.2, we have $\forall I^* \in \mathcal{P}_{\omega,*}(I) : H(I^*) \in \{I^*, \emptyset\}$ and so $v(I^*) \in I^*$. Therefore, there exist $G$ and $v$ with the desired properties. $\square$

**Definition 4.7.3.** Let $I$ be a set and $\phi : I \to I$. We define the partial order $\leq_{\phi}$ on $I$ by : $a \leq_{\phi} b \Leftrightarrow b \in \mathcal{O}_{\phi}^{+}(a)$.

The following proposition characterizes, under the condition that all the orbits of $\phi$ are infinite, the existential problem $\exists G \exists u : P_2(\phi, G, u)$ in terms of the orbital structure of $\phi$.

**Proposition 4.7.5.** Let $I$ be an infinite set, $\phi : I \to I$ such that $(\forall a \in I) : \mathcal{O}_{\phi}^{+}(a)$ is infinite.

Then the following conditions are equivalent :

1. $\exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : \exists u : \mathcal{P}_{\omega,*}(I) \to I : P_2(\phi, G, u)$.

2. $\forall I^* \in \mathcal{P}_{\omega,*}(I) : (\bigcap_{a \in I^*} \mathcal{O}_{\phi}^{+}(a)) \cap I^* \neq \emptyset$,

3. $D_{\phi} = \mathcal{P}_{\omega,*}(I)$ and $\forall I^* \in \mathcal{P}_{\omega,*}(I) : (\bigcap_{a \in I^*} \mathcal{O}_{\phi}^{+}(a)) \cap I^* = \{\xi_{\phi}(I^*)\}$.

4. $D_{\phi} = \mathcal{P}_{\omega,*}(I)$ and $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \xi_{\phi}(I^*) \in I^*$,

5. $\forall n \in \mathbb{N}^* : \forall (a_1, \dots, a_n) \in I^n \text{ which are distinct : } \exists d \in [1, n] : \exists (m_1, \dots, m_n) \in \mathbb{N}^n \text{ with } m_d = 0 : \forall i \in [1, n] : a_d = \phi^{m_i}(a_i)$.

6. $\forall (a, b) \in I^2$ with $a \neq b$, $(\exists n \in \mathbb{N} : a = \phi^n(b))$ or $(\exists n \in \mathbb{N} : b = \phi^n(a))$.

7. $\leq_{\phi}$ is a total order on $I$.

*Démonstration.* (1) $\Rightarrow$ (2) : Let $I^* \in \mathcal{P}_{\omega,*}(I)$. We have from proposition 4.7.1 that $u(I^*) = \xi_\phi(H(I^*)) \in \bigcap_{a \in H(I^*)} \mathcal{O}_\phi^+(a) = \bigcap_{a \in G(I^*)} \mathcal{O}_\phi^+(a) \subseteq \bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)$, where we used the fact that here we have necessarily $H(I^*) = G(I^*) \supseteq I^*$. Moreover, we have $u(I^*) \in I^*$. So $(\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)) \cap I^* \neq \emptyset$.

(2) $\Rightarrow$ (3) : Let $I^* \in \mathcal{P}_{\omega,*}(I)$. Since $\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a) \neq \emptyset$, then $I^* \in D_\phi$. Let $x \in (\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)) \cap I^*$. Since $x \in \bigcap_{a \in I^*} \mathcal{O}_\phi^+(a) = \mathcal{O}_\phi^+(\xi_\phi(I^*))$ by lemma 4.3.6 and $\xi_\phi(I^*) = \phi^{m_x} \xi_\phi^{(I^*)}(x)$ because $x \in I^*$ (see definition 4.3.1), then $\exists n \geq m_x^{\xi_\phi(I^*)} : x = \phi^n(x)$. Since $\{x, \phi(x), \phi^2(x), \dots\}$ are distinct (see lemma 4.3.1), we have necessarily $n = 0$ and so $m_x^{\xi_\phi(I^*)} = 0$. This implies $\xi_\phi(I^*) = \phi^{m_x} \xi_\phi^{(I^*)}(x) = x \in I^*$. Since this is true for all $x \in (\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)) \cap I^*$, we have $(\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)) \cap I^* = \{\xi_\phi(I^*)\}$.
(3) ⇒ (4) : This is clear.

(4) ⇒ (1) : This is proposition 4.7.4.

(4) ⇒ (5) : Let $n \in \mathbb{N}^*$ and let $a_1, \cdots, a_n$ be distinct elements of $I$. Applying (4) to $I^* = \{a_1, \cdots, a_n\}$ gives $\xi_\phi(I^*) \in I^*$ which is the content of (5).

(5) ⇒ (2) : Let $I^* \in \mathcal{P}_{\omega,*}(I)$. Write $I^*$ as $\{a_1, \cdots, a_n\}$ where $n$ is the cardinality of $I^*$. From (5), we have $a_d \in (\bigcap_{a \in I^*} \mathcal{O}_\phi^+(a)) \cap I^*$, and so this last set is not empty.

(5) ⇒ (6) : This is clear.

(6) ⇒ (5) : Let $n \in \mathbb{N}^*$ and let $a_1, \cdots, a_n$ be distinct elements of $I$. Assume by way of contradiction that $\forall d \in [1, n] : \exists l(d) \in [1, n] \setminus \{d\} : a_d \notin \mathcal{O}_\phi^+(a_{l(d)})$. By (6), this implies that $\forall d \in [1, n] : a_{l(d)} \in \mathcal{O}_\phi^+(a_d)$. Besides, we have necessarily $\exists d \in [1, n] : \exists e \in \mathbb{N}^* : l^e(d) = d$. Otherwise, we would have $\forall d \in [1, n] : \forall e \in \mathbb{N}^* : l^e(d) \neq d$, which implies that $\forall \tilde{d} \in [1, n] : \{\tilde{d}, l(\tilde{d}), l^2(\tilde{d}), \cdots\}$ are distinct. This is impossible since this infinite set is included in $[1, n]$. Therefore, $\exists (n_1, \cdots, n_e) \in \mathbb{N}^* : a_d = a_{l^e(d)} = \phi^{n_e}(a_{l^{e-1}(d)}) = \phi^{n_e}(\phi^{n_{e-1}}(a_{l^{e-2}(d)})) = \cdots = \phi^{\sum_{i=1}^e n_i}(a_d)$. Since $\mathcal{O}_\phi^+(a_d)$ is infinite, we have by lemma 4.3.1 that $\forall i \in [1, e] : n_i = 0$, which implies in particular that $a_{l(d)} = a_d$, a contradiction. Therefore we have the result.

(6) ⇔ (7) : This is just the definition of a total order. □

From this proposition, the following corollary characterizing the existential problem $\exists G \exists u : P_2(\phi, G, u)$ with no additional assumption can be easily derived.

**Corollary 4.7.1.** Let $I$ be an infinite set and $\phi : I \to I$. Denote by $I_\phi^{\text{inf}}$ (resp. $I_\phi^{\text{fin}}$) the subsets of $I$ consisting of the elements which have an infinite (resp. finite) orbit under $\phi$. Notice that $I_\phi^{\text{inf}}$ and $I_\phi^{\text{fin}}$ are both invariant under $\phi$ and that $\{I_\phi^{\text{inf}}, I_\phi^{\text{fin}}\}$ is a partition of $I$. Then the following conditions are equivalent :

1. $\exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : \exists u : \mathcal{P}_{\omega,*}(I) \to I : P_2(\phi, G, u)$.

2. $(\preceq_\phi)_{|I_\phi^{\text{inf}}}$ is a total order on $I_\phi^{\text{inf}}$.

**Lemma 4.7.3.** Let $I$ be a set and $\phi : I \to I$.

Suppose that $\exists a \in I : \mathcal{O}_\phi^+(a) = I$.

Then $\preceq_\phi$ is a total order on $I$.

*Démonstration.* Let $x, y \in I$. We can write $x = \phi^n(a)$ and $y = \phi^m(a)$ for $m, n \in \mathbb{N}$. If $m \le n$, we have $y \preceq_\phi x$. Otherwise we have $x \preceq_\phi y$. Hence $\preceq_\phi$ is a total order. □

The following proposition is a supplement to proposition 4.7.5 where we also suppose the existence of a cofinite orbit.
**Proposition 4.7.6.** Let $I$ be an infinite set and $\phi: I \to I$ such that $\forall a \in I: O_{\phi}^{+}(a)$ is infinite. Then we have

$$ (\exists \tilde{a} \in I : O_{\phi}^{+}(\tilde{a}) \text{ is cofinite}) $$

$$ \text{and } (\exists u : \mathcal{P}_{\omega,*}(I) \to I : \exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : P_2(\phi, G, u)) $$

$$ \Leftrightarrow (\exists \tilde{a} \in I : O_{\phi}^{+}(\tilde{a}) \text{ is cofinite}) \text{ and } (\leq_{\phi} \text{ is a total order on } I) $$

$$ \Leftrightarrow \exists \alpha : (\mathbb{N}, \leq) \to (I, \leq_{\phi}) \text{ such that } \alpha \text{ is an increasing bijection} $$

$$ \Leftrightarrow \exists \tilde{a} \in I : O_{\phi}^{+}(\tilde{a}) = I. $$

**Démonstration.** Suppose that $\exists \tilde{a} \in I : O_{\phi}^{+}(\tilde{a}) = I$. Let $\alpha = \begin{cases} \mathbb{N} & \to I \\ n & \mapsto \phi^{n}(\tilde{a}) \end{cases}$. Clearly, $\alpha$ is increasing. It is injective by lemma 4.3.1. It is surjective by the hypothesis. Conversely, suppose that there is such an increasing bijection $\alpha$ from $\mathbb{N}$ to $I$. For all $n \in \mathbb{N}$, we have $\alpha(n+1) = \phi(\alpha(n))$. Indeed, since $\alpha$ is increasing, we have $\exists l(n) \in \mathbb{N}: \alpha(n+1) = \phi^{l(n)}(\alpha(n))$. Suppose by way of contradiction that $l(n) \neq 1$. If $l(n) = 0$, we would have $\alpha(n+1) = \alpha(n)$, contradicting the injectivity of $\alpha$. If $l(n) \geq 2$, let $m \in \mathbb{N}$ such that $\alpha(m) = \phi(\alpha(n))$. If $m \geq n+1$, then $\alpha(n+1) \leq_{\phi} \alpha(m)$, and so $\phi(\alpha(n)) = \alpha(m) \in O_{\phi}^{+}(\alpha(n+1)) = O_{\phi}^{+}(\phi^{l(n)}(\alpha(n)))$. This implies $\exists u \in \mathbb{N}: \phi(\alpha(n)) = \phi^{l(n)-1+u}(\phi(\alpha(n)))$ where $l(n)-1+u \geq 1$, contradicting lemma 4.3.1. If $m \leq n$, then $\alpha(m) \leq_{\phi} \alpha(n)$, and so $\alpha(n) \in O_{\phi}^{+}(\alpha(m)) = O_{\phi}^{+}(\phi(\alpha(n)))$. This implies $\exists u \in \mathbb{N}: \alpha(n) = \phi^{u+1}(\alpha(n))$ where $u+1 \geq 1$, contradicting again lemma 4.3.1. Hence $l(n) = 1$ and the relation $\alpha(n+1) = \phi(\alpha(n))$ is proved. Now consider $\tilde{a} = \alpha(0)$. Then clearly $O_{\phi}^{+}(\tilde{a}) = \alpha(\mathbb{N}) = I$. This establishes the equivalence of the last two statements.

Using lemma 4.7.3, the last statement clearly implies the second. Let's prove that the second one implies the last one. Using lemma 4.3.5, we have that all the orbits of $\phi$ are cofinite. Let $b \in I$ such that $|I \setminus O_{\phi}^{+}(b)|$ is minimal. Suppose by way of contradiction that $O_{\phi}^{+}(b) \neq I$ and let $c \in I \setminus O_{\phi}^{+}(b)$. Since $\leq_{\phi}$ is a total order, we have necessarily $b \in O_{\phi}^{+}(c)$. Specifically, we have $\exists n \geq 1: b = \phi^{n}(c)$. Since $c, \phi(c), \phi^{2}(c), \dots$ are distinct by lemma 4.3.1, we have, thus, $|I \setminus O_{\phi}^{+}(c)| < |I \setminus O_{\phi}^{+}(b)|$ which is a contradiction. Hence $O_{\phi}^{+}(b) = I$.

The first and second statements are equivalent by corollary 4.3.3 and proposition 4.7.5. $\square$

Note that we can also prove explicitly that

$$ \exists a \in I : O_{\phi}^{+}(a) = I \Rightarrow (\exists u : \mathcal{P}_{\omega,*}(I) \to I : \exists G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I) : P_2(\phi, G, u)). $$
Indeed, suppose $\exists a \in I : \mathcal{O}_{\phi}^{+}(a) = I$ and define

$$ n : \begin{cases} \mathcal{P}_{\omega,*}(I) & \to \mathbb{N} \\ I^* & \mapsto \max\{n \in \mathbb{N} : \phi^n(a) \in I^*\} \end{cases} $$

which is well-defined because $\{a, \phi(a), \phi^2(a), \dots\}$ are distinct (lemma 4.3.1) and let

$$ u : \begin{cases} \mathcal{P}_{\omega,*}(I) & \to I \\ I^* & \mapsto \phi^{n(I^*)}(a) \end{cases} $$

and

$$ G : \begin{cases} \mathcal{P}_{\omega,*}(I) & \to \mathcal{P}_{\omega,*}(I) \\ I^* & \mapsto \{a, \phi(a), \dots, \phi^{n(I^*)}(a)\} \end{cases}. $$

Then $u$ and $G$ clearly satisfy the requirements.

Remark 4.7.1. There are many maps $\phi : \mathbb{N} \to \mathbb{N}$ such that $\exists a \in \mathbb{N} : \mathcal{O}_{\phi}^{+}(a) = \mathbb{N}$ (not just the successor function). They are conjugated to the successor function and can be found by choosing a bijection $\alpha : \mathbb{N} \to \mathbb{N}$ and setting $\phi = \alpha \circ \text{succ} \circ \alpha^{-1}$. For example, there is the function

$$ \left\{ \begin{array}{ll} \mathbb{N} & \to \mathbb{N}^* \\ 0 & \mapsto 2 \\ 2i + 1 & \mapsto 2i + 4 \text{ for all } i \in \mathbb{N} \\ 2i + 2 & \mapsto 2i + 1 \text{ for all } i \in \mathbb{N} \end{array} \right. $$

### 4.7.3 An indivisibility property for 3-tuples $(\phi, G, u)$ satisfying $P_2(\phi, G, u)$

3-tuples $(\phi : I \to I, G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I), u : \mathcal{P}_{\omega,*}(I) \to I)$ satisfying $P_2(\phi, G, u)$ enjoy the following indivisibility property with respect to composition of maps $\beta : I \to I$ satisfying $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \exists a \in G(I^*) : |\mathcal{O}_{\beta}^{+}(a)| = +\infty$ with bijective maps $\alpha : I \to I$ satisfying $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \alpha(G(I^*)) \subseteq G(I^*)$.

**Proposition 4.7.7.** Let $I$ be a set and $(\phi : I \to I, G : \mathcal{P}_{\omega,*}(I) \to \mathcal{P}_{\omega,*}(I), u : \mathcal{P}_{\omega,*}(I) \to I)$ a 3-tuple satisfying $P_2(\phi, G, u)$.

Then if $\phi = \beta \circ \alpha$ where $\beta : I \to I$ is a map satisfying $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \exists a \in G(I^*) : |\mathcal{O}_{\beta}^{+}(a)| = +\infty$ and $\alpha : I \to I$ is a bijective map such that $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \alpha(G(I^*)) \subseteq G(I^*)$, then $\alpha = \text{id}$ and $\beta = \phi$.

*Démonstration.* First, notice that for all $I^* \in \mathcal{P}_{\omega,*}(I)$, $\alpha$ bijective and $\alpha(G(I^*)) \subseteq G(I^*)$ implies that $\alpha$ induces a bijection on $G(I^*)$.
Let $v = \begin{cases} \mathcal{P}_{\omega,*}(I) & \to I \\ I^* & \mapsto \alpha(u(I^*)) \in G(I^*) \end{cases}$. Let $I^* \in \mathcal{P}_{\omega,*}(I)$. Since $\alpha$ induces a bijection on $G(I^*)$, it is easily seen that $\beta(G(I^*) \setminus \{v(I^*)\}) \subseteq G(I^*)$. Since $\exists a \in G(I^*) : |\mathcal{O}_\beta^+(a)| = +\infty$, it follows from proposition 4.7.1 that $v(I^*) = \xi_\beta(H(I^*))$, where we have used the notation of that proposition. Specifying this relation for $I^* = \{b\}$, one has $\alpha(b) = \alpha(u(\{b\})) = v(\{b\}) = \xi_\beta(H(\{b\}))$ for all $b \in I$.

Since $\forall I^* \in \mathcal{P}_{\omega,*}(I) : \alpha(G(I^*)) \subseteq G(I^*)$, we have $\forall b \in I : \alpha(b) \in \alpha(G(\{b\})) \subseteq G(\{b\})$, and by induction $\mathcal{O}_\alpha^+(b) \subseteq G(\{b\})$. Since $G(\{b\})$ is finite and $\alpha$ is bijective, we have from lemma 4.3.1 $\exists n_b \ge 1 : \alpha^{n_b}(b) = b$. This implies in particular that $\mathcal{O}_\beta^+(b) = \mathcal{O}_\beta^+(\alpha^{n_b}(b)) = \mathcal{O}_\beta^+(\xi_\beta(H(\{\alpha^{n_b-1}(b)\}))) = \bigcap_{c \in H(\{\alpha^{n_b-1}(b)\})} \mathcal{O}_\beta^+(c)$ is an orbit arising as a finite intersection of infinite orbits. Thus it is infinite, which is true for all $b \in I$.

Now let $b \in I$. We have $|\mathcal{O}_\beta^+(b)| = |\mathcal{O}_\beta^+(\alpha(b))| = +\infty$. Let $I^* = H(\{\alpha(b)\})$. Since $\alpha(b) \in I^*$, we have $\xi_\beta(I^*) \in \mathcal{O}_\beta^+(\alpha(b))$. Hence $\alpha(\alpha(b)) = \xi_\beta(I^*) \in \mathcal{O}_\beta^+(\alpha(b))$. So $\forall b \in I : \exists k_b \in \mathbb{N} : \alpha(\alpha(b)) = \beta^{k_b}(\alpha(b))$. We have $\forall b \in I : \alpha(\alpha(b))) = \beta^{k_{\alpha(b)}}(\alpha(\alpha(b))) = \beta^{k_{\alpha(b)}+k_b}(\alpha(a))$. In general, $\forall b \in I : \forall n \ge 1 : \alpha^n(b) \in \mathcal{O}_\beta^+(\alpha(b))$. Let $b \in I$ and choose $n = n_{\alpha(b)} \ge 1$. Then $\alpha(b) = \alpha^{n_{\alpha(b)}}(\alpha(b)) \in \mathcal{O}_\beta^+(\alpha(\alpha(b)))$, and so $\exists m \in \mathbb{N} : \alpha(b) = \beta^m(\alpha(\alpha(b)))$. We saw previously that $\alpha(\alpha(b)) \in \mathcal{O}_\beta^+(\alpha(b))$, so $\exists l \in \mathbb{N} : \alpha(b) = \beta^l(\alpha(b))$. Combining the two results, we have $\alpha(b) = \beta^{m+l}(\alpha(b))$ and so $m = l = 0$ since $|\mathcal{O}_\beta^+(\alpha(b))| = +\infty$. In turn, this implies that $\alpha(\alpha(b)) = \alpha(b)$ and so $\alpha(b) = b$ since $\alpha$ is a bijection.

Hence $\alpha = \mathrm{id}$ and $\beta = \phi$. $\square$

## Acknowledgement

The first author is financially supported by the *Centre National pour la Recherche Scientifique et Technique* of Morocco.

**Nizar El Idrissi.**

Laboratoire : Equations aux dérivées partielles, Algèbre et Géométrie spectrales.
Département de mathématiques, faculté des sciences, université Ibn Tofail, 14000 Kénitra.
*E-mail address : nizar.elidrissi@uit.ac.ma*

**Pr. Samir Kabbaj.**

Laboratoire : Equations aux dérivées partielles, Algèbre et Géométrie spectrales.
Département de mathématiques, faculté des sciences, université Ibn Tofail, 14000 Kénitra.
*E-mail address : samir.kabbaj@uit.ac.ma*
Bibliographie

[1] D. Agrawal. The complete structure of linear and nonlinear deformations of frames on a Hilbert space. Master's thesis, 2016.

[2] D. Agrawal and J. Knisley. Fiber bundles and Parseval frames, 2015. [arxiv:1512.03989].

[3] M. Alaeiyan and B. Razzaghmanieshi. Permutation groups with bounded movement having maximum orbits. *Proc. Indian Acad. Sci. (Math. Sci.),* **122(2)**:175–179, 2012.

[4] M. Alaeiyan and S. Yoshiara. Permutation groups of minimal movement. *Arch. Math.*, **85(3)**:211–226, 2005.

[5] S.T. Ali, J.P. Antoine, and J.P. Gazeau. Square integrability of group representations on homogeneous spaces. i. reproducing triples and frames. *Annales de l'I. H. P, section A*, **55(4)**:829–855, 1991.

[6] S.T. Ali, J.P. Antoine, and J.P. Gazeau. Continuous frames in Hilbert space. *Annals of physics*, **222(1)**:1–37, 1993.

[7] A. Askarizadeh and M.A. Dehghan. G-frames as special frames. *Turk. J. Math.*, **37**:60–70, 2013.

[8] R. Balan, P.G. Casazza, C. Heil, and Z. Landau. Density, overcompleteness, and localization of frames. I. Theory. *Journal of Fourier Analysis and Applications*, **12(2)**:105–143, 2006.

[9] R. Balan, P.G. Casazza, C. Heil, and Z. Landau. Density, overcompleteness, and localization of frames. II. Gabor systems. *Journal of Fourier Analysis and Applications*, **12(3)**:307–344, 2006.

[10] P. Balazs, J.P. Antoine, and Anna Grybos. Weighted and controlled frames. *Int. J. Wavelets Multiresolut. Inf. Process.*, **8(1)**:109–132, 2010.

[11] E. Bardelli and A.C.G. Mennucci. Probability measures on infinite-dimensional Stiefel manifolds. *Journal of Geometric Mechanics*, **9(3)**:291–316, 2017.

[12] M. Bownik. Connectivity and density in the set of framelets. *Mathematical Research Letters*, **14(2)**:285–293, 2017.
[13] L. Brailovsky. Structure of quasi-invariant sets. *Arch. Math.*, 59(4):322-326, 1992.

[14] L. Brailovsky, D.V. Pasechenik, and C.E. Praeger. Subsets close to invariant subsets for group actions. *Proceedings of the American Mathematical Society*, 123(8):2283-2295, 1995.

[15] M. Brin and G. Stuck. *Introduction to Dynamical Systems*. Cambridge University Press, 2002.

[16] J. Cahill, D. Mixon, and N. Strawn. Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames. *SIAM Journal on Applied Algebra and Geometry*, 1(1):38-72, 2017.

[17] P.G. Casazza. The art of frame theory. *Taiwanese Journal of Mathematics*, 4(2):129-201, 2000.

[18] P.G. Casazza, D. Han, and D.R. Larson. Frames for Banach spaces. *Contemporary Mathematics*, 247:149-182, 1999.

[19] P.G. Casazza and G. Kutyniok. *Finite frames, theory and applications*. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, 2013.

[20] O. Christensen. *An Introduction to Frames and Riesz Bases*. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, second edition, 2016.

[21] O. Christensen, B. Deng, and C. Heil. Density of Gabor frames. *Applied and Computational Harmonic Analysis*, 7(3):292-304, 1999.

[22] O. Christensen and M. Hasannasab. Frame properties of systems arising via iterated actions of operators. *Applied and Computational Harmonic Analysis*, 46(3):664-673, 2019.

[23] I. Daubechies, A. Grossmann, and Y. Meyer. Painless nonorthogonal expansions. *J. Math. Phys.*, 27(5):1271-1283, 1986.

[24] B.A. Davey and H.A. Priestley. *Introduction to Lattices and Order*. Cambridge University Press, second edition, 2002.

[25] M. Dellnitz and O. Junge. On the approximation of complicated dynamical behavior. *SIAM Journal on Numerical Analysis*, 36(2):491-515, 1999.

[26] R.J. Duffin and A.C. Schaeffer. A class of nonharmonic Fourier series. *Transactions of the American Mathematical Society*, 72(2):341-366, 1952.

[27] K. Dykema and N. Strawn. Manifold structure of spaces of spherical tight frames. *Int. J. Pure Appl. Math.*, 28(2):217-256, 2006.

[28] M. Frank and D.R. Larson. Frames in Hilbert C*-modules and C*-algebras. *Journal of Operator Theory*, 48(2):273-314, 2002.

[29] G. Froyland and M. Dellnitz. Detecting and locating near-optimal almost-invariant sets and cycles. *SIAM Journal on Scientific Computing*, 24(6):1839-1863, 2003.
[30] G. Froyland and K. Padberg. Almost-invariant sets and invariant manifolds connecting probabilistic and geometric descriptions of coherent structures in flows. *Physica D: Nonlinear Phenomena*, 238(16):1507-1523, 2009.

[31] D. Gabor. Theory of communications. *Jour. Inst. Elec. Eng. (London)*, 93(3):429-457, 1946.

[32] G. Garrigos, E. Hernandez, H. Šikić, F. Soria, G. Weiss, and E. Wilson. Connectivity in the set of Tight Frame Wavelets (TFW). *Glasnik matematički*, 38(1):75-98, 2003.

[33] L. Hamilton and A. Moitra. The Paulsen problem made simple. *Isr. J. Math.*, 246(1):299-313, 2021.

[34] D. Han and D.R. Larson. On the orthogonality of frames and the density and connectivity of wavelet frames. *Acta Applicandae Mathematicae*, 107(1-3):211-222, 2009.

[35] P. Harms and A.C.G. Mennucci. Geodesics in infinite dimensional Stiefel and Grassmann manifolds. *Comptes Rendus Mathematique*, 350(15-16):773-776, 2012.

[36] A. Hatcher. *Algebraic topology*. Cambridge University Press, 2005.

[37] C. Heil. History and evolution of the density theorem for Gabor frames. *Journal of Fourier Analysis and Applications*, 13(2):113-166, 2007.

[38] C. Heil, J. Ramanathan, and P. Topiwala. Linear independence of time-frequency translates. *Proceedings of the American Mathematical Society*, 124(9):2787-2795, 1996.

[39] O. Henkel. Sphere-packing bounds in the Grassmann and Stiefel manifolds. *IEEE Transactions on Information Theory*, 51(10):3445-3456, 2005.

[40] W. Hodges. *A Shorter Model Theory*. Cambridge University Press, 2017.

[41] R.B. Holmes and V.I. Paulsen. Optimal frames for erasures. *Linear Algebra and its Applications*, 377:31-51, 2004.

[42] D. Husemoller. *Fibre Bundles*. Springer-Verlag, third edition, 1994.

[43] N. El Idrissi and S. Kabbaj. Functions with a maximal number of finite invariant or internally-1-quasi-invariant sets or supersets. *To appear in Boletim da Sociedade Paranaense de Matematica*.

[44] N. El Idrissi and S. Kabbaj. Independence, infinite dimension, and operators. *Moroccan Journal of Pure and Applied Analysis*, 9(1):86-96, 2023.

[45] N. El Idrissi, S. Kabbaj, and B. Moalige. Path-connectedness and topological closure of some sets related to the non-compact stiefel manifold. *Proyecciones (Antofagasta, On line)*, 42(3):571-597, 2023.
[46] I.M. James. *The topology of Stiefel manifolds*. Cambridge University Press, 1976.

[47] V. Jurdjevic, I. Markina, and F.S. Leite. Extremal curves on Stiefel and Grassmann manifolds. *J. Geom. Anal.*, 30(4):3948–3978, 2020.

[48] A. Katok and B. Hasselblatt. *Introduction to the modern theory of dynamical systems*. Cambridge University Press, 1995.

[49] A. Kharazishvili. On some applications of almost invariant sets. *Bulletin of TICMI*, 23(2):115–124, 2019.

[50] P.S. Kim and Y. Kim. Certain groups with bounded movement having the maximal number of orbits. *Journal of Algebra*, 252(1):74–83, 2002.

[51] D. Labate and E. Wilson. Connectivity in the set of Gabor frames. *Applied and Computational Harmonic Analysis*, 18(1):123–136, 2005.

[52] J.S. Moghaddam, A. Najati, and Y. Khedmati. Fibonacci representations of sequences in Hilbert spaces. *U.P.B. Sci. Bull., Series A*, 83(1):99–112, 2021.

[53] T. Needham and C. Shonkwiler. Symplectic geometry and connectivity of spaces of frames. *Advances in Computational Mathematics*, 47(1:5), 2021.

[54] A. Petrosyan, H. Tran, and C. Webster. Reconstruction of jointly sparse vectors via manifold optimization. *Applied Numerical Mathematics*, 144:140–150, 2019.

[55] C.E. Praeger. On permutation groups with bounded movement. *Journal of Algebra*, 144(2):436–442, 1991.

[56] G. Schmidt and T. Ströhlein. *Relations and Graphs: Discrete Mathematics for Computer Scientists*. Springer Science & Business Media, 2012.

[57] D.M. Speegle. The s-elementary wavelets are path-connected. *Proc. Amer. Math. Soc.*, 127(1):223–233, 1999.

[58] E. Stiefel. Richtungsfelder und Fernparallelismus in n-dimensionalen Mannigfaltigkeiten. *Comm. Math. Helv.*, 8(4):305–353, 1935-1936.

[59] N. Strawn. Geometry and constructions of finite frames. Master's thesis, 2007.

[60] N. Strawn. Finite frame varieties: nonsingular points, tangent spaces, and explicit local parameterizations. *J. Fourier Anal. Appl.*, 17(5):821–853, 2011.

[61] N. Strawn. *Geometric structures and optimization on spaces of finite frames*. PhD thesis, 2011.

[62] W. Sun. G-frames and g-Riesz bases. *J. Math. Anal. Appl*, 322(1):437–452, 2006.

[63] M.A. Sustik, J.A. Tropp, I.S. Dhillon, and R.W.(Jr.) Heath. On the existence of equiangular tight frames. *Linear Algebra and its applications*, 426(2-3):619–635, 2007.
[64] S.I. Trapasso. Almost diagonalization of pseudodifferential operators. In P. Boggiatto, E. Cordero, M. de Gosson, H. G. Feichtinger, F. Nicola, A. Oliaro, and A. Tobacco, editors, *Landscapes of Time-Frequency Analysis*, chapter 14, pages 323–342. Birkhäuser, 2019.

[65] A. Uschmajew. Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations. *Numer. Math.*, 115:309–331, 2010.

[66] S.F.D. Waldron. *An introduction to finite tight frames*. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, 2018.

[67] K. Yang, Y. Shi, and Z. Ding. Generalized low-rank optimization for topological cooperation in ultra-dense networks. *IEEE Transactions on Wireless Communications*, 18(5):2539–2552, 2019.
Résumé (250 mots Max) :

Cette thèse a pour objet l'étude de quelques aspects de l'espace des repères, de l'indépendance et des ensembles quasi-invariants. Dans la première partie, nous démontrons deux résultats sur la connexité par arcs et l'adhérence (respectivement) de quelques ensembles reliés à la variété de Stiefel non compacte (espace des repères), et nous illustrons le dernier résultat par quelques exemples. Dans la deuxième partie, nous prouvons quelques généralisations d'un résultat garantissant l'équivalence entre l'indépendance linéaire et la dimension infinie d'une suite infinie de vecteurs décalés par un opérateur linéaire. Dans la troisième partie, nous décrivons les fonctions admettant un nombre maximal d'ensembles ou de sur-ensembles finis invariants ou intérieurement-1-quasi-invariants.

Abstract (250 words Max) :

This thesis deals with some aspects of the frame space, of independence, and of quasi-invariant sets. In the first part, we prove two results on the path-connectedness and topological closure (respectively) of some sets related to the non-compact Stiefel manifold (frame space), and we illustrate the latter with some examples. In the second part, we prove some generalizations of a result guaranteeing the equivalence between the linear independence and infinite dimension of an infinite sequence of vectors shifted by a linear operator. In the third part, we describe the functions admitting a maximal number of finite invariant or internally-1-quasi-invariant sets or supersets.