text:
\section{Introduction}

Wireless networked environments are a natural host for  a number of cyber-physical control applications, ranging from autonomous cars and drones, to the Internet-of-Things (IoT), to immersive environments such as augmented reality. It is well recognized that wireless networking is essential to realize the potential of new CPS applications, and is equally well recognized that  private and secure exchange of information are necessary and not simply desirable conditions for the CPS ecosystem to thrive. For instance, personal health data in assisted environments, car positions and trajectories, proprietary interests, all need to be protected. This paper introduces a new approach to secure communication in CPS, that aims to distort an adversary's view of a control system's states. In particular, we will show that a linear dynamical system can securely communicate its state {to a trusted party in a manner that prevents a malicious adversary eavesdropping the communication from accurately learning the state.}

Our starting observation is that information security measures (cryptographic and information theoretic secrecy), are not {well-matched} to  CPS applications as they impose unnecessary requirements, such as protecting all the raw data, and thus can cause high operational costs\footnote{Our work focuses on security against passive adversaries -- alternatively referred to in the literature as \textit{CPS Privacy}.}.
{To illustrate this, we start by comparing existing techniques for ensuring CPS privacy, namely \textit{cryptographic} and \textit{information-theoretic} techniques.
Cryptographic methods rely on computational complexity as a guarantee for the security of the underlying CPS, \textit{i.e.}, the system is secure against computationally-limited adversaries. Cryptographic methods are universal and therefore are easy to integrate in any system under consideration. However, some of their shortcomings are: 1) they do not provide guarantees against adversaries with unlimited computational power (\textit{e.g.}, quantum adversaries), 2) they utilize computationally-heavy encryption/decryption algorithms, and 3) they come at the cost of high overhead on short packet transmissions, therefore increasing delays\cite{wan2016exploiting,Zan2013KeyAA,Trappe,6521318,Alexandru2020}.
In fact, those techniques have been previously studied in the context of secure CPSs. For example, homomorphic encryption~\cite{7403296,FAROKHI2016163,7799042} and public-encryption systems~\cite{7244402} have been used to provide security of networked control systems.
Alternatively, information-theoretic methods rely on keys: they have low complexity and do not add packet overhead, but require the communicating nodes to share large keys - every communication link needs to use a shared secret key (for a one-time pad) of length equal to the entropy (effectively length) of the transmitted data\cite{shannon1949communication, TGP2018}. These costs accumulate rapidly given that large CPS applications can have dense communication patterns.

Instead, we propose a lightweight approach which provides security guarantees against computationally-capable (i.e., with unlimited computational power) adversaries, and uses small amounts of keys and low complexity operations. The main observation behind our approach is the following. Consider a general encryption scheme which uses a $K$-bit key to encrypt the states of a dynamical system. From an abstract point of view, such a scheme hides the true value of the state among a set of $2^K$ states; without knowing the value of the key, an outside observer of the encrypted state cannot resolve the ambiguity among these fake states -- we refer to this set as the {\it ambiguity set}. General encryption ({\it e.g.}, cryptographic or information-theoretic) schemes aim at increasing the size of the ambiguity set. Differently, in CPS applications, increasing the size of the ambiguity set may not be effective if all of these states are close to each other in a metric space.
To make this idea concrete, assume an adversary is trying to locate a drone in order to shoot it down with one missile in its possession. If a $K$-bit encryption scheme is used, the adversary would ideally have a set of $2^K$ possible locations for the drone -- any set of $2^K$ possible locations are equivalent from an information-theoretic security point of view. However, if all locations are in close proximity, an adversary can possibly shoot the missile and hit the target regardless of the actual location. On the other hand, a different encryption scheme which uses only $1$ bit of information, but instead carefully chooses the two possible locations to be far apart, would be more secure against such an adversary. We therefore propose a distortion measure in order to capture this idea.}

The following example illustrates the effect of maximizing distortion\footnote{Although we illustrate our approach for a specific simple example, it extends to protecting general system states.}. Consider  the following simple example of a drone's flying motion, depicted in Fig.~\ref{fig::msb}. The drone starts at any position, and  moves between adjacent points within the grid. It regularly  communicates its location  to a legitimate receiver, Bob. A passive eavesdropper, Eve, wishes to infer the drone's locations, and can perfectly overhear all the transmissions the drone makes. We assume the drone and Bob share just one bit of key, that is secret from Eve, and ask: what is the best use we can make of the key?

Using the one bit of shared key to protect the most significant bit (MSB) is not a good solution. {The} MSB can be protected by

{XORing} a one bit of {shared key with} the MSB.

As shown in Fig.~\ref{fig::msb} the adversary can discover the fake trajectory after a few time steps since this scheme leads to trajectories that do not adhere to the dynamics or environment constraints.
{In particular, the fake trajectory abruptly moves from the left end of the grid to the right end.} At this point, the adversary can learn the real trajectory by flipping back the MSB (we assume that the used scheme is known to everyone).
Similar attacks can be made if we use a one-time pad~\cite{shannon1949communication} using the same keys over time: as time progresses, more fake trajectories can be discovered and discarded.

\begin{figure}[t]
	\centering
		\includegraphics[width=2.0in]{figures/shifting_grid_gaurav.jpg}
		\caption{Example of drone motion: protection of the most significant bit.}
		\label{fig::msb}
\end{figure}

Conventional entropy measures also fail to provide insights on how to use the  key. For instance, assume we label the $64$ squares in  Fig.~\ref{fig::msb} sequentially row per row, and consider two cases: in case I, Eve learns that  the drone is in one of the neighboring squares $\{1, 2\}$, each with probability 1/2. For case II, Eve knows that the drone is in one of the squares $\{1, 64\}$, again each with probability 1/2. Both cases are equivalent from an information security perspective since in both cases Eve's uncertainty is a set of two equiprobable elements

and hence its entropy is 1. However, the security risks in both situations are different. For example, if Eve aims to take a photo of the drone, in the first case she knows where to turn her camera (squares $1$ and $2$ are close by) while in the second case, she does not (squares $1$ and $64$ are far apart).

Instead, we propose to use an Euclidean distance distortion measure: how far (in Euclidean space) is Eve's estimate from the actual location. We then propose encoding/decoding schemes which {utilize} the shared key to maximize this distance. We first consider an ``average'' distortion measure. Note that if Eve had not received any of the drone transmissions, then the best (adversarial) estimate of {the} drone's location at any given time is the center point of the confined region in Fig.~\ref{fig::msb}. Therefore, a good encryption scheme would strive to maintain Eve's estimate to be as close to the center point as possible; and we achieve the maximum possible distortion, if, after overhearing the drone's transmissions, Eve's best estimate {still remains} the center point.

The following scheme can achieve this maximum distortion by using exactly one bit of shared secret key. When encoding, the drone either sends its actual trajectory, or a ``mirrored'' version of it, depending on the value of the secret key. The mirrored trajectory is obtained by reflecting the actual trajectory across a mirroring point in space; in this example, the mirroring point is the center point {in} Fig.~\ref{fig::mirroring}. Since Eve does not know the value of the shared key, its best estimate of the drone's location - after receiving the drone's transmissions - would be the average location given the trajectory and its mirrored version, which is exactly the center point.

Our  results in Section~\ref{sec:expected} extend this idea of mirroring to more general light-weight mappings for dynamical systems in higher dimensional spaces, and theoretically analyze the performance in terms of average distortion for a larger variety of distributions (with certain symmetry conditions). We also discuss a {class of systems and controllers} for which we can always achieve the perfect distortion with just one bit of key.

	\begin{figure}[t]
		\centering
		\includegraphics[width=2.0in]{figures/Mirroring_grid.pdf}
		\caption{Example of drone motion: mirroring based scheme.}
		\label{fig::mirroring}
	\end{figure}

Next, we consider a worst-case-sense distortion-based metric. In other words, our security metric is ``in the worst case, how far is Eve's estimate from the actual location?'' That is, the adversary's distortion may be different for different time instances and different instances of the actual trajectory, and we are interested in the minimum among these. For example when the drone is near the origin, both the actual and fake trajectory are close to origin and thus the adversary knows that the drone is near the origin. In this case, the overall (expected) distortion for adversary is still maximum, but at this particular instance of time, the adversary comes very close to the actual position. In Section~\ref{sec:worst} we provide encryption schemes that are suitable for maximizing this distortion metric and show that with $3$ bits of shared key per dimension (\textit{i.e.}, $9$ for three dimensional motion), our schemes achieve near-perfect worst case distortion.
Our main contributions are as follows:

{
\noindent$\bullet$ We} define security measures that are based on assessing the distortion: in the average sense over time and over data, and in the {minimum} sense, providing worst case guarantees at any time and for any particular instances of data. \\
\noindent$\bullet$  For the expected distortion, we develop a scheme which uses exactly one bit of key and can provide maximum possible distortion {(equivalent to Eve with no observations)} in some cases. We also discuss the cases where it is not optimal and give an analytical characterization of the attained distortion. {We then discuss a class of systems and controllers for which we can always guarantee the perfect distortion with just one bit of shared key.} Since for some applications an ambiguity set of size two (corresponding to one bit of key) may not be enough, we also derive an expression of attained distortion when we use larger keys. \\

\noindent$\bullet$ For the worst case distortion, we design a scheme that uses $3$ bits {of key} per dimension and prove it achieves the {maximum possible distortion (equivalent to Eve with no observations)} when the inputs to the systems are independent from the previous states.\\
\noindent$\bullet$ {For linear control systems, we provide a relation between the distortion in inputs to the distortion in states. This is particularly useful when inputs are easier to distort and analyze compared to the states.}

\subsection{Related Work}

Secure data communication where the adversary has unlimited computational power is studied from the lens of information theory, most notably by Shannon~\cite{shannon1949communication} and Wyner~\cite{wyner1975wire}. The study of secure communication while using distortion as a measure of security is relatively new and is first studied by Yamamoto~\cite{yamamoto1988rate}, where the goal is to maximize the distortion of an eavesdropper's estimate on a message, viewed from an asymptotic (in block length) information-theoretic approach. Schieler and Cuff~\cite{schieler2014rate} later showed that, in the limit of an infinite block length $n$ code, only $\log(n)$ bits of secret keys are needed to achieve the maximum possible distortion. The idea of using finite block length (and even single-shot) distortion as a performance measure was initiated in~\cite{chiyo17}, where schemes for single shot communication were considered. It demonstrated the exponential benefits for each additional bit of shared key. The schemes examined were for single-shot sensor observations, and not for time-series data, which is the focus of our work in this paper.

Secure communication in control systems is studied in~\cite{Tsiamis2017StateSecrecyCF, TSIAMIS20178385,tanakaDirected,Malik2013,Pappas16}. Securing the system state from an adversary was explored in~\cite{Tsiamis2017StateSecrecyCF, TSIAMIS20178385}, where an asymptotic steady-state analysis was explored. In contrast our work also deals with transients and is not asymptotic. Information-theoretic security was explored in~\cite{tanakaDirected}, where the mutual information was used as a privacy measure. Security of the terminal state is considered in~\cite{Malik2013} where an adversary makes partial noisy measurement of the state trajectory.
{Securing the states of an unstable system has been considered in~\cite{wiese2018secure} where the notion of secure capacity was used to characterize the level of secrecy against an adversary connected through a wiretap channel.}
Differential privacy for control systems was explored in~\cite{Pappas16}, which uses standard statistical indistinguishability which is equally applicable to categorical (non-metric space) data; in our work, we use the estimation error of the adversary in order to quantify privacy, utilizing the fact that CPS data lies in an  Euclidean space, as argued earlier.

\subsection{Notation} For a matrix $A$, we denote by $A^\prime$ {and $A^H$} the transpose {and complex-transpose} of $A$, {respectively};
by $A^{r}$ the $r$-th power of $A$;
{$X$ and $X_a$ denote {column vectors}, and
$X_{a}^{b} = [X_a^\prime \: X_{a+1}^\prime \: \cdots \: X_b^\prime]^\prime$ for $b\geq a$ and $a,b \in \mathbb{Z}$; $f_X(x)$ denotes the probability density function of a random vector $X$};

for any random vector $Y$, we denote the mean and covariance matrices of $Y$ by $\mu_{Y}$ and $R_{Y}$ respectively, thus for example, the mean and the covariance matrix of $X_a^b$ will be denoted by $\mu_{X_a^b}$ and $R_{X_a^b}$ respectively;  by $[m]$ we denote $\{1,2,\ldots,m\}$ where $m \ \in \mathbb{Z^+}$; and by $[m_1:m_2]$ we denote $\{m_1,m_1+1,\ldots,m_2\}$ where $m_1, m_2 \ \in \mathbb{Z^+}$ and $m_2 > m_1$;
{a negative sign $(-)$ in the superscript of a function indicates the inverse of the function, \textit{i.e.}, the inverse of the functions $\alpha(x)$ and $\alpha^{(K)}(x)$ are $\alpha^-(x)$ and $\alpha^{-(K)}(x)$ respectively.}


TITLE: Number of ways to arrange people in a row with two restrictions (permutations).
QUESTION [1 upvotes]: The question is as follows:

In a group of 9 people, there are 4 Gujaratis and 5 Marwadis. Of the Gujaratis, 2 are vegetarian and the rest are non-vegetarians. Of the Marwadis, 2 are vegetarian and the rest are non-vegetarians. They have to be seated along a row. No two Marwadis wish to sit together. Furthermore, all vegetarians insist on sitting together. In how many ways can the entire group be seated?
A. $4! \cdot 5! \cdot 4!$
B. $6! \cdot 4! - 2 \cdot 4! \cdot 5!$
C. $6 \cdot 4! \cdot 5!$
D. $6 \cdot 2! \cdot 2! \cdot 2! \cdot 3!$

I have two conflicting approaches to this question. Why is my thinking incorrect?
The letter $G$ represents the Gujaratis and the letter $M$ represents the Marwadis.
$$\\$$
Approach 1
Of the 9 people, 2 Gujaratis and 2 Marwadis are vegetarians. They can be arranged in the following manner: $MGMG$. Therefore, there are $2! \cdot 2!$ ways to arrange the vegetarians.
We can think of these 4 people as one entity. There are 6 places to seat them. Therefore, there are $6!$ ways to seat them.
There are 5 people remaining, 3 Marwadis and 2 Gujaratis. We can notate them in the following way:
$$\_ \ G \ \_ \ G \_$$
There are 3 places for the Marwadis to be seated. Therefore, there are $3! \cdot 2!$ ways to seat the remaining 5 people.
Thus, there are $3! \cdot 2! \cdot 2! \cdot 2! \cdot 6!$ ways to seat all 9 people.
$$\\$$
Approach 2
The group of vegetarians can be grouped as $GMGM$ or $MGMG$. The group of vegetarians can be placed in 6 ways. There are 5 people left who can be arranged in $3! \cdot 2!$ ways. Thus, there are $3! \cdot 2! \cdot 2! \cdot 2! \cdot 6! \cdot 2$ ways to arrange all 9 people.

REPLY [1 votes]: Your first approach is correct to some extent but is missing something critical.
In this solution, the letter $G$ represents the Gujaratis and the letter $M$ represents the Marwadis.
We will first consider the second restriction - all the vegetarians (2 Gujaratis and 2 Marwadis) insist on sitting next to each other. With the first restriction in mind (no two Marwadis wish to sit next to each other), the 4 people will have to be arranged in one of two ways:

 $$MGMG \text { or } GMGM$$

There are $2!$ ways to seat the Marwadis and $2!$ to seat the remaining two Gujaratis, giving a total of $2! \cdot 2! = 4$ ways to seat all four of the vegetarians in both scenarios.
Let us now consider the group to be $MGMG$ and treat them as an individual entity which we will notate as $V$. Therefore, the vegetarians can be seated in the following ways:

 $$VMGMGM \text { or } MGVMGM \text { or } MGMGVM$$

This gives a total of 3 ways to seat the vegetarians. This leaves us with 3 Marwadis and 2 Gujaratis to be seated. The 3 Marwadis can be seated in $3!$ ways and the 2 Gujaratis can be seated in $2!$ ways.
Therefore, the number of ways to seat all 9 people in this scenario is as follows:

 $$4 \cdot 3 \cdot 3! \cdot 2! = 144$$

However, we must now consider the second option to arrange the vegetarians: $GMGM$. There are still 4 ways to seat all the vegetarians, but they have to be seated differently amongst the entire group.
The vegetarians in this scenario can be seated in the following ways:

 $$MVGMGM \text { or } MGMVGM \text { or } MGMGMV$$

This also gives us a total of 3 ways to seat the vegetarians, and the remaining Marwadis and Gujratis can also be seated in $3! \cdot 2!$ ways.
Therefore, the number of ways to seat all 9 people in this scenario is as follows:

 $$4 \cdot 3 \cdot 3! \cdot 2! = 144$$

Thus, the total number of ways to seat all 9 people is as follows:

 $$144 + 144 = 288 \ (= 6 \cdot 2! \cdot 2! \cdot 2! \cdot 3!)$$

Option D is the correct answer.
The reason why your first approach is incorrect is that you assumed the number of ways to seat the vegetarians was $6!$ when it should have just been 6 (which is the same as the sum of the ways to seat the vegetarians in the $MGMG$ and $GMGM$ scenario). Even if this was a minor typographical error, the reasoning behind why there were 6 ways to seat the vegetarians is incorrect. Since you assumed the vegetarians to be seated as $MGMG$, they could not have been placed in a scenario such as $MGM \_ MG$, where the vegetarians are to be placed in the gap. This would have violated the first restriction.
The reason why your second approach is also incorrect is that you assumed there would be twice as many ways to seat the vegetarians if both the $MGMG$ and $GMGM$ cases were considered, which is not the case. As mentioned in the paragraph above, there are not 6 ways to seat the vegetarians in each scenario; there are only 3 ways. Once again, the same mistake regarding $6!$ is made, when it should have just been $6$.
I know this solution is quite lengthy; I just want to make sure that the reasoning behind this solution is made clear. Nevertheless, I hope you found it helpful.


TITLE: Square of palindromic number
QUESTION [1 upvotes]: The other day I thought of this question:
Is it possible to find a set of palindromic numbers such that the square of them is itself palindromic? In other words:
$A = \{a : a^{2}=b$ where a,b are palindromic integers}
I'm not a mathematician so I don't really know where to begin!
Edit: Thanks to all who responded so quickly! My question now is whether is possible to find ALL possible integers that belongs to such set. Would it be possible to find a rule for that set?

REPLY [2 votes]: If you keep to the digits $0, 1,$ and $2$, and include plenty of $0$'s you can make lot of examples.
$$1002001^2 = 1004006004001$$
$$212^2 = 44944$$


TITLE: General question about finding the minimal polynomial
QUESTION [1 upvotes]: Suppose you're given a root $\alpha$ and asked to find the minimal polynomial of $\alpha$ over $F$, where $F$ is some field. The usual strategy I've seen for solving these problems is to set $x=\alpha$ and then manipulate this expression to get a polynomial $f(x)$ for which $\alpha$ is a zero. Then, it suffices to show that $f(x)$ is irreducible.
My question is whether there are cases where you will follow this procedure and get a polynomial that is not irreducible. Are there any obvious examples?

REPLY [2 votes]: It might depend on how you "manipulate this expression".
For example, if $F = \mathbb Q$ and $\alpha = \exp(2 \pi i/n)$, you might well come up with the polynomial $x^n - 1$.  But this is not irreducible: the polynomial you want is the $n$'th cyclotomic polynomial.


TITLE: Finding points of intersection which are coincident
QUESTION [2 upvotes]: I was practicing some basic math and I faced a question that I have no idea what does it requires me to do. Consider this simple function:
$$f(x) = x^2-5x-12$$
Part a and b where pretty easy. I tried to solve part C as you can see below. Unfortunately I cant imagine what has been asked in part D. What does coincident points of intersection mean? (Literally intersection means cutting each other and Coincident means on top of another AFAIK) Any help/explanation would be appreciated!
Part C:
The point at which the line through $(1,-15)$ with slope $m$ cuts the graph of $f(n)$.
$$m=f'(n)=f'(1)=-1$$
$$y-y_1 = m(n-n_1)=>y+15=-1(n-1)$$
$$ \implies y=-n+1-15$$
Part D:
The values of m such that the points of intersections found in $c$ are coincident.

REPLY [2 votes]: The slope of the tangent line to $y=2x^2-5x-12$ at $x=1$ is indeed $-1$, and when $x=1$ we have $y=-15$. However, in solving problems like C), it is best not to notice these facts, because you might be asked a similar question in which the given point is not on the curve.  Also, you were asked explicitly to find the intersection points with the curve of the general line with slope $m$ that passes through $(1,15)$, not just the line with specific slpe $m=-1$.
The line through $(1,-15)$ with slope $m$ has equation $y-(-15)=m(x-1)$, that is, $y=mx-m-15$.  We want to find the point(s) at which this line meets the curve $y=2x^2-5x-12$.
Substitute $mx-m-15$ for $y$ in the equation of the curve.  We get a quadratic equation in $x$, which turns out to be
$$2x^2-x(5+m)+(3+m)=0.$$
Solve. In principle, we use the Quadratic Formula, or complete the square. However, the problem poser has kindly chosen numbers that make the quadratic factor nicely. One root is (as we already knew) $x=1$, and the other is $x=\frac{m+3}{2}$. The two roots coincide when $m=-1$.
Remark: The problem is presumably intended as an approach to the tangent line that does not use the derivative. And indeed Fermat, among others, found tangent lines to quite a few curves by using precisely the "double root" idea, well before the work of Newton and Leibniz on the calculus.


TITLE: Solve $z^5=-32$ and draw its solutions in complex space, then describe their characteristic geometrical property.
QUESTION [0 upvotes]: I'm solving past exam questions in preparation for an Applied Mathematics course. I came to the following exercise, which poses some difficulty. If it's any indication of difficulty, the exercise is only Part 3-A of the sheet, graded for 10%

Solve the equation $z^5=-32$ and draw its solutions in complex space, then describe their characteristic geometrical property.

Is it asking to convert z to polar form, then use DeMoivres theorem as I've seen in solutions around the net? If that is the case, how can I work out the $\theta$ angle to be used?
Additionally, what does it refer to as its characteristic geometrical property?
Any answers would be extremely appreciated as they'd help to get me out of the ditch. I'm completely stalled.

REPLY [2 votes]: Let $z=\rho e^{i\theta}$. Representing $-32$ in the Argand plane you see that, in polar form, it is $-32=32e^{i\pi}$, so your equation becomes:
$$
\left(\rho e^{i\theta}\right)^5=32e^{i\pi}
$$
that gives:
$$
\rho e^{i\theta}=\left( 32e^{i\pi}\right)^{1/5}=2\left(e^{i\pi}\right)^{1/5}
$$
Now, since $e^{i\pi}=e^{i(\pi+2k\pi)}$ we have five distinct values for $\left(e^{i\pi}\right)^{1/5}$:
$$
\left(e^{i(\pi+2k\pi)}\right)^{1/5}=e^{i\pi/5+2ik\pi/5}
$$
for $k=0,1,2,3,4$ and the five complex roots of $-32$ are:
$$
z_1=2e^{i\pi/5} \quad z_2=2e^{3i\pi/5} \quad z_3=2e^{5i\pi/5}=2e^{i\pi}=-2\quad z_4=2e^{7i\pi/5} \quad z_5=2e^{9i\pi/5}
$$
In the Argand plane these points are the vertex of a regular pentagon inscribed in a circle of radius $2$ an with a vertex on $-2$.


TITLE: Finding Area of the red square
QUESTION [2 upvotes]: Calculate the area of the red square.
I m having some trouble doing it so I need some help.

REPLY [2 votes]: (with slightly different point labels)

Introduce $a$ as the radius of the big circle and $d$ as the side of the square. Take $O$ as the origin of the coordinate system with $x$ axis going to the right and $y$ axis going upwards. We have the foolowing point coordinates:
$$H(x_H, y_H)$$
Note that $x_H>y_H$. Because of symmetry:
$$G(x_G,y_G)\equiv G(y_H,x_H)$$
So the side of the square is:
$$d=\sqrt{(x_G-x_H)^2+(y_G-y_H)^2}=\sqrt{(y_H-x_H)^2+(x_H-y_H)^2}=\sqrt{2}(x_H-y_H)\tag{1}$$
Coordinates of point $I$ are:
$$I(x_I,y_I)\equiv I(x_H+d\frac{\sqrt 2}{2},y_G)\equiv I(x_H+(x_H-y_H), x_H)\equiv I(2x_H-y_H, x_H)$$
Point $H$ is on the small circle so:
$$(x_H-\frac a2)^2+y_H^2=(\frac a2)^2\tag{2}$$
Point $I$ is on the big circle so:
$$(2x_H-y_H)^2+x_H^2=a^2\tag{3}$$
So you have a system with of two equations, (2) and (3), with two unknowns $(x_H,y_H)$. The system leads to the following quartic equation for $a=7$:
$$32x_H^4-56x_H^3-343x_H^2-686x_H+2401=0$$
In theory, you can solve it by hand. I did it with Mathematica:
$$x_H=4.40864,\ \ y_H=3.38$$
Other solutions had to be discarded (two of them are complex, the third one leads to negative value of $y_H$). From (1):
$$d=1.45471$$
...which is pretty much in sync with the value obtained by measuring the length of the square in Geogebra.


TITLE: What is inductive case?
QUESTION [0 upvotes]: nines(1) =  9
nines(2) = 99
nines(3)= 999
nines(4)=  9999
⋮
Let P(n) ≡ [nines(n) + 1 = 10^n]. Prove that P(n) is true for all n ≥ 1, by mathematical induction. Use the induction schema [P(1) ∧ ∀k [P(k) → P(k + 1)]] → ∀n P(n).

What is the inductive case, ∀k [P(k) → P(k + 1)]?

I am working on this problem and i am pretty sure it is true but i do not know how the answer should look like. Can anyone help me?

REPLY [0 votes]: Let $p(n)=\sum_{k=0}^{n-1}9\cdot{10}^k$
We have $p(1) = \sum_{k=0}^09\cdot{10}^k=9\cdot10^0=9=10^1-1$
For the induction case, we assume our claim is true and attempt to show that assuming $p(k)$ implies $p(k+1)$
$$\sum_{k=0}^{n}9\cdot{10}^k=9\cdot10^n+\sum_{k=0}^{n-1}9\cdot{10}^k$$
$$=9\cdot10^n+10^n-1=10^n(9+1)-1=10^{n+1}-1 \;\;\;\square$$


text:
\section{Rotation set for fitted axiom A diffeomorphisms}\label{s.rotsetbp}

In the first part of this section we will show that rotation sets of basic pieces are \emph{rational polyhedra}, namely, convex sets of $H^1(\Sigma_g,\R)\subseteq \R^{2g}$ with finitely many extremal points that lie in $\mathbb{Q}^{2g}$. The proof of this fact is based on ideas of \cite{Zi} and \cite{Pass1}. Then we will turn to study the rotation set generated by chains of basic pieces in fitted axiom A diffeomorphisms.

For a chain $\mathcal{C}=\{\Lambda_1\prec\ldots\prec\Lambda_N\}$ of basic pieces of $f\in\mathcal{A}_0(\Sigma_g)$, define

$$\rho_{\mathcal{C}}(f) = \textrm{conv}\left(\bigcup_{i=1}^N\rho_{\Lambda_i}(f)\right) $$

The principal theorem of the section, whose proof relies on Theorem \ref{t.shadchain}, is the following.
\begin{thm}\label{t.rhorhochain}

Let $f\in\mathcal{A}_0(\Sigma_g)$ and $\mathcal{G}$ its graph of basic pieces. Then

$$\rho(f)=\bigcup_{\mathcal{C}}\rho_{\mathcal{C}}(f) $$ where $\mathcal{C}$ ranges over all maximal chains of $\mathcal{G}_f$.

\end{thm}

Together with the results about the rotation sets of basic pieces, this implies that $\rho(f)$ is a finite union of convex sets, which are rational polyhedra. We start with some definitions.

\smallskip

Let $K\subset \Sigma_g$ be an invariant compact set for $f\in\mathcal{A}_0(\Sigma_g)$, admitting a Markov partition $\mathcal{P}$. This implies that $K$ is contained in a finite union of pairwise disjoint topological disks, namely the elements of $\mathcal{P}$.
This allows us to construct a fundamental domain $D\subset\Sigma^{ab}_g$ for the abelian cover, so that every element of $\mathcal{P}$ is contained in the projection of the interior of $D$.
Thus for every $P\in\mathcal{P}$ we have that $\hat{P}:=\pi_{ab}^{-1}(P)\cap D$ is homeomorphic to $P$ through the projection $\pi_{ab}$. In this configuration we say that the fundamental domain $D$ is \emph{adapted} to $\mathcal{P}$.
We say that $\mathcal{P}$ is a \emph{rotational} Markov partition if there is a fundamental domain $D\subset\Sigma^{ab}_g$ that is adapted for both  $\mathcal{P}$ and $f^*(\mathcal{P})=\{f(P):\ P\in\mathcal{P}\}$. In other words, so that both $P$ and $f(P)$ are contained in $\pi_{ab}(\textrm{int}(D))$ for every $P\in \mathcal{P}$.

\smallskip

Consider $\mathcal{P}=\{P_1,\ldots,P_N\}$ be a rotational Markov partition for $K$ with an adapted fundamental domain $D$.  Define $\hat{P}_i:=\pi_{ab}^{-1}(P_i)\cap D$ for $i=1,\ldots,N$, and notice that there are unique
deck transformations $\mathcal{T}_i$ of $\Sigma_g^{ab}$ so that $\hat{f}(\hat{P}_i)\subset \mathcal{T}_i(D)$. Recall that the deck transformations
for this covering are given by translations by vectors in $\Z^{2g}$, so we can write $\mathcal{T}_i(x)=x+T_i,\ T_i\in\Z^{2g}$.
Hence to every $P_i\in\mathcal{P}$ (for $i=1,\ldots,N$) we can associate $T_i\in\Z^{2g}$ with $\hat{f}(\hat{P}_i)\subset D+T_i$.
From this simple fact we can obtain the following important lemma.

\begin{lemma}\label{l.moving}

In the situation above, for every $x\in K$ and every positive integer $n\geq 1$ we have that
$$ \left| \hat{f}^n(\hat{x}) - \sum_{j=0}^{n-1}T_{\xi_x(j)} \right|<\textrm{diam}(D),$$
where $\hat{x}$ is the unique point in $\pi^{-1}_{ab}(x)\cap D$ and $\xi_x$ is the itinerary function for the rotational Markov partition applied to $x$.

\end{lemma}

\begin{proof}

We proceed by induction proving the following fact: for every $n\geq 1$ we have $\hat{f}^n(\hat{x})$
in $D+\sum_{j=0}^{n-1}T_{\xi_x(j)}$. The base case $n=1$ is trivial, so assume that it holds for $n-1\in\N$. Then
$$\hat{f}^{n-1}(\hat{x})\in\left(D+\sum_{j=1}^{n-2}T_{\xi_x(j)}\right)\cap \pi^{-1}_{ab}(P_{\xi_x(n-1)})=\hat{P}_{\xi_x(n-1)}+ \sum_{j=1}^{n-2}T_{\xi_x(j)}.$$

Now, using the fact that these Deck transformations commute with the map $\hat{f}$, we have
$$\hat{f}^n(\hat{x})=\hat{f}(\hat{f}^{n-1}(\hat{x}))\in \hat{f}(\hat{P}_{\xi_x(n-1)}) + \sum_{j=1}^{n-2}T_{\xi_x(j)}\subset D+\sum_{j=1}^{n-1}T_{\xi_x(j)}.$$

\end{proof}

This clearly implies the following corollary.

\begin{cor}\label{c.rotsetsim}

Let $f\in\textrm{Homeo}_0(\Sigma_g)$, $K$ an $f$-invariant set and $\mathcal{P}$ a rotational
Markov partition of $K$. Then,

\small
$$\rho_{K}(f)=\left\{\lim_{i}\frac{\sum_{j=1}^{n_i-1} T_{\xi_{x_i}(j)}}{n_i}:\ x_i\in\pi_{\textrm{ab}}^{-1}(K)\cap D,\ n_i\nearrow +\infty\right\}$$
\normalsize

where $\xi_{x_i}$ is the itinerary of $x_i$ for the rotational Markov partition $\mathcal{P}$.

\end{cor}

From this fact we can apply the result of \cite{Zi} to conclude the following.

\begin{cor}\label{c.convbp}

Let $f\in\textrm{Homeo}_0(\Sigma_g)$, and $K$ an $f$-invariant set that admits a rotational
Markov partition $\mathcal{P}$. Then $\rho_K(f)$ is a polyhedron of $\R^{2g}$ with vertices
in $\mathbb{Q}^{2g}$, each of which is realized by a periodic orbit.

\end{cor}

We now turn to study the rotation set generated by chains of basic pieces of fitted axiom A diffeomorphisms. Given a chain $\mathcal{C}=\{\Lambda_1\prec\cdots\prec\Lambda_N\}$
of $f\in\mathcal{A}_0(\Sigma_g)$ define

$$\rho_{\mathcal{C}}(f) = \textrm{conv}\left(\bigcup_{i=1}^N\rho_{\Lambda_i}(f)\right) $$

 the \emph{rotation set of the chain}. Our goal is to prove the following result:

\begin{prop}\label{p.convchain}

Let $\mathcal{C}=\{\Lambda_{1}\prec\cdots\prec\Lambda_N\}$ be a chain of basic pieces of $f\in\mathcal{A}_0(\Sigma_g)$.
Then $\rho_{\mathcal{C}}(f)$ is a rational polyhedron contained in the rotation set $\rho(f)$.

\end{prop}

\smallskip

By Corollary \ref{c.convbp} we know that $\rho_{\mathcal{C}}(f)$ is a rational polyhedron in $\R^{2g}$ so we only need to prove the inclusion $\rho_{\mathcal{C}}(f)\subset \rho(f)$.

Denote $E_i=\{v_{i,1},\ldots,v_{i,m_i}\}$ the set of extremal points of $\rho_{\Lambda_i}(f)$ for $i=1,\ldots,N$ and recall from Corollary \ref{c.convbp} that the elements of $E_i\subseteq\mathbb{Q}^{2g}$ are realized by periodic orbits in $\Lambda_i$. We introduce the set of indices  $J=\{(i,j):i=1,\ldots,N,\ j=1,\ldots,m_i\}$ which we consider lexicographically ordered. We also consider the sequence $\mathcal{S}=(\Lambda_{i,j}=\Lambda_i:(i,j)\in J)$, which has underlying chain $\mathcal{C}$ and repeats $m_i$ times the piece $\Lambda_i$.

Take $\epsilon_0>0$ given by Theorem \ref{t.shadchain} for the sequence $\mathcal{S}$, and $\mathcal{P}_1,\ldots,\mathcal{P}_N$ rotational Markov partitions of $\Lambda_1,\ldots,\Lambda_N$ respectively, satisfying $d_{\mathcal{P}_i}<\epsilon_0$. Consider also $n_0$ given by Theorem \ref{t.shadchain} for the sequence $\mathcal{S}$ and the partitions $\mathcal{P}_{i,j}=\mathcal{P}_i$. For $i=1,\ldots,N$ consider the sub-shift $\Sigma_{A_i}$ given by $\mathcal{P}_i$ and for each $(i,j)\in J$ take $w_{i,j}$ the periodic word of the sub-shift $\Sigma_{A_i}$ associated to the periodic orbit in $\Lambda_i$ realizing $v_{i,j}$.

Given $X=(k_{i,j})\in \N^J$ we can choose $(p_{i,j})\in \mathbb{N}^J$ so that shifting $w_{i,j}^{k_{i,j}}$ by $p_{i,j}$ we obtain a $n_0$-spaced word sequence of the form
$$w(X)=((w_{i,j})^{k_{i,j}}_{p_{i,j}}:(i,j)\in J).$$

Note that the lexicographic order on $J$ gives the order of this sequence.
There are many possible choices for $(p_{i,j})$ that lead to different word sequences as above. To determine $w(X)$ uniquely, we choose $(p_{i,j})$ with $p_{1,1}=0$ and so that the gaps between the domains of the words $(w_{i,j})^{k_{i,j}}_{p_{i,j}}$ have length $n_0+1$.

As a consequence of Theorem \ref{t.shadchain} we have the following.

\smallskip

\begin{lemma}\label{l.prevrotsetchain}

In the situation above, for any $X\in\N^J$ the word sequence $w(X)$ is shadowed.

\end{lemma}

The goal now is to compute the rotation vectors generated by points shadowing the word sequences involved in Lemma \ref{l.prevrotsetchain}. So take $X\in\N^J$ and $x\in\Sigma_g$ that shadows $w(X)$. We consider $$n= \sum_{(i,j)\in J} k_{i,j}|w_{i,j}| + (n_0+1)(|J|-1)$$ which is the number of iterations needed for $x$ to complete the shadowing of $w(X)$, recalling that $|J|-1$ is the number of gaps between the domains of the words of $w(X)$ and $n_0+1$ is the length of those gaps. We remark that both $x$ and $n$ depend on $X$, while $N_0 := (n_0+1)(|J|-1)$ is constant.

Let $\hat{x}$ be the lift of $x$ to a fundamental domain $D\subset\Sigma_g^{ab}$, which is adapted for all the partitions $\mathcal{P}_i$ and $f^*(\mathcal{P}_i)$ for $i=1,\ldots,N$. Then Lemma \ref{l.moving}, together with a telescopic argument, gives us the estimation
$$\left| \hat{f}^n(\hat{x}) - \sum_{(i,j)\in J} k_{i,j}|w_{i,j}|v_{i,j} \right| < \delta_f N_0 + \textrm{diam}(D)|J|$$

where $$\delta_f = \sup\{|\hat{f}(y)-y|:y\in\Sigma_g^{ab}\}$$ Notice that $\delta_f<\infty$ since $\hat{f}$ is a lift of a map that is isotopic to the identity.

Now we fix $t_{i,j}\in[0,1]$ for $(i,j)\in J$ with $\sum_{(i,j)\in J} t_{i,j}=1$. It is clear that we can take $X\to\infty$ (meaning, each coordinate goes to $\infty$) along a sequence that makes $\frac{k_{i,j}|w_{i,j}|}{n}\to t_{i,j}$. So we get that

$$\lim_{X\to\infty}\frac{\hat{f}^n(\hat{x})}{n} = \lim_{X\to\infty}  \sum_{(i,j)\in J} \frac{k_{i,j}|w_{i,j}|}{n}v_{i,j} = \sum_{(i,j)\in J} t_{i,j}v_{i,j}. $$

Thus we find that any convex combination of the points in $E_1\cup\cdots\cup E_N$ is obtained as a limit in the definition of rotation set, concluding that $\rho_{\mathcal{C}}(f)\subset \rho(f)$ and proving Proposition \ref{p.convchain}.

\medskip

Thus, we obtained that for $f\in\mathcal{A}_0(\Sigma_g)$ we have

\begin{equation}\label{e.1inc}
\bigcup_{\mathcal{C}}\rho_{\mathcal{C}}(f)\subset\rho(f)
\end{equation}
where $\mathcal{C}$ ranges over all chains of $\mathcal{G}_f$. Clearly we obtain the same result considering only the maximal chains.

Note that the sets appearing in the union in \ref{e.1inc} are rational polyhedra in $\R^{2g}$. In what follows we prove the complementary inclusion, in order to obtain Theorem \ref{t.rhorhochain}. We start with two preliminary results.

\begin{lemma}\label{l.entornos1}

Let $\Lambda_1,\ldots,\Lambda_N$ be the basic pieces of $f\in\mathcal{A}_0(\Sigma_g)$. There exists a family of pairwise disjoint neighbourhoods $V_1,\ldots,V_N$ of $\Lambda_1,\ldots,\Lambda_N$ respectively, so that
whenever $f^n(V_i)\cap V_j\neq \emptyset$ for some $n\in\N$, we have $\Lambda_i\prec\Lambda_j$.

\end{lemma}

\begin{proof}

We start by considering, for each basic piece $\Lambda_i$, the neighbourhood $V'_i$ given by item (2) of Proposition \ref{p.propfaxa}. Thus whenever $\Lambda_i\not\prec \Lambda_j$ we have that $W^u(\Lambda_i,f):=\bigcup_{x\in\Lambda_i}W^u(x,f)$ does not meet $V'_j$. Further, as $\textrm{cl}(W^u(\Lambda_i,f))$ is an attractor (by item (3) of Proposition \ref{p.propfaxa}), we can consider a forward-invariant neighbourhood $S_{i,j}$ which we can assume does not meet $V'_j$. Let
$$S_i=\bigcap_{j:\ \Lambda_i\not\prec\Lambda_j}S_{i,j}$$
and consider $V_i=V'_i\cap S_i$ for $i=1,\ldots,N$. These neighbourhoods satisfy the statement: Let $i_0,j_0\in\{1,\ldots,N\}$ so that $f^n(V_{i_0})\cap V_{j_0}\neq\emptyset$ for some positive integer $n$. Then $f^n(S_{i_0})\cap V'_{j_0}\neq\emptyset$, so $\Lambda_{i_0}\prec \Lambda_{j_0}$.

\end{proof}

We remark that the neighbourhoods $V_1,\ldots,V_N$ in Lemma \ref{l.entornos1} can be taken arbitrarily small. In the following lemma we make some further observations about these neighbourhoods. We use the notation $$\mathcal{O}(x,f):=\{f^n(x):n\in\Z \}$$  for the orbit of $x$ under $f$.

\begin{lemma}\label{l.saltos2}

Let $\Lambda_1,\ldots,\Lambda_N$ be the basic pieces of $f\in\mathcal{A}_0(\Sigma_g)$, and $V_1,\ldots,V_N$ a family of neighborhoods of these basic pieces as in Lemma \ref{l.entornos1}.
Then
\begin{enumerate}
\item there exists a positive constant $\kappa\in\N$ so that for every $x\in\Sigma_g$ $$\left|\mathcal{O}(x,f)\cap \left(\Sigma_g\setminus \bigcup_{i=1}^N V_i\right)\right|<\kappa.$$

\item If $f^{n_1}(x)\in V_{i_1}$ and $f^{n_2}(x)\in V_{i_2}$ with $n_1<n_2$, then $\Lambda_{i_1}\preceq \Lambda_{i_2}.$

\end{enumerate}
\end{lemma}

\begin{proof}

It is a general fact for a map in a compact metric space that given any neighbourhood of the non-wandering set, the iterations of any point which are contained in the complement of that neighbourhood is uniformly bounded, which implies the first fact. The second fact is straightforward from Lemma \ref{l.entornos1}.
\end{proof}

For the rest of this section we take $f\in\mathcal{A}_0(\Sigma_g)$, consider $\Lambda_1,\ldots,\Lambda_N$ its basic pieces and let $V_1,\ldots,V_N$ be the family of neighbourhoods given in Lemma \ref{l.entornos1}. Since we can take these neighbourhoods arbitrarily small, we may assume that the components of $V_i$  form a rotational Markov partition $\mathcal{P}_i$ of $\Lambda_i$, for $i=1,\ldots,N$. The following is a consequence of the shadowing lemma for hyperbolic pieces.

\begin{lemma}\label{l.saltos3} In the situation above, consider $x\in\Sigma_g$ and $i\in\{1,\ldots,N\}$ so that $f^j(x)\in V_i$ for all $j\in I=\{a,\ldots,a+m\}$. Then there exists $x'\in\Lambda_i$ so that $f^j(x)$ and $f^j(x')$ belong to the same element of $\mathcal{P}_i$ for every $j\in I$.
\end{lemma}

We fix $\kappa$ as in Lemma \ref{l.saltos2} for the neighbourhoods $V_1,\ldots,V_N$ under consideration. Then Lemma \ref{l.saltos2} implies the following.

\begin{cor}\label{l.entornos3} In the context above, for every $x\in\Sigma_g$ and every $n\in\N$ we have a unique sequence of intervals $I_1,\ldots,I_r\subset \{0,\ldots,n\}$, and a sequence of basic pieces $\Lambda_{i_1},\ldots,\Lambda_{i_r}$, so that

\begin{enumerate}
\item $\max I_{s}<\min I_{s+1}$ for $s=1,\ldots,r-1$,
\item $\left|\{0,\ldots,n\}\setminus\bigcup_{s=1}^r I_s\right|<\kappa$,
\item $f^j(x)\in V_{i_s}$ for $j\in I_s$, $s=1,\ldots,r$, and the intervals $I_s$ are maximal among those with this property,
\item $\Lambda_{i_1}\preceq\cdots\preceq\Lambda_{i_r}$.

\end{enumerate}

\end{cor}

Notice that both the number of intervals (i.e. $r$) and their lengths are dependent on $x$ and $n$. However, due to (2) and the maximality condition in (3), we have that $r$ is bounded by $\kappa+1$ plus the maximum length of a chain (observe that (4) allows for repetition of basic pieces). Denote $\mathcal{S}(x,n)=(\Lambda_{i_1}\preceq\cdots\preceq\Lambda_{i_r})$ the sequence of basic pieces given in Corollary \ref{l.entornos3}, and by $\mathcal{C}(x,n)$ its underlying chain.

We are now ready to conclude that $\rho(f)\subset\bigcup_{\mathcal{C}}\rho_{\mathcal{C}}(f)$ which, together with Proposition \ref{p.convchain}, implies Theorem \ref{t.rhorhochain}. To do so, take an arbitrary $v\in\rho(f)$ and write it as $$v=\lim_k\frac{\hat{f}^{n_k}(x_k)-x_k}{n_k}$$ where $n_k\nearrow\infty$ and $x_k\in\Sigma_g^{ab}$. Let $y_k=\pi_{ab}(x_k)$, and notice that $\mathcal{S}(y_k,n_k)$ varies in a finite set, since its length is bounded. Thus, up to taking a sub-sequence we may assume that $\mathcal{S}(y_k,n_k)$ is constant and denote it by $\mathcal{S}=\mathcal{S}(y_k,n_k)=(\Lambda_{i_1}\preceq\cdots\preceq\Lambda_{i_r})$. We will show that $v\in\rho_{\mathcal{C}}(f)$ where $\mathcal{C}=\mathcal{C}(y_k,n_k)$ is the underlying chain of $\mathcal{S}$.

For each $k\in\N$ let $I^{(k)}_1,\ldots,I^{(k)}_r$ be the intervals in $\{0,\ldots,n_k\}$ obtained applying Corollary \ref{l.entornos3} to $y_k$ and $n_k$. As noted in the paragraph above, $r$ is constant, but the intervals themselves depend on $k$ and they cover $\{0,\ldots,n_k\}$ up to at most $\kappa$ elements. Denote $I^{(k)}_s=\{a^{(k)}_s,\ldots,b^{(k)}_s\}$ for $s=1,\ldots,r$, and also set $b^{(k)}_0=0$ and $a^{(k)}_{r+1}=n_k$. Then we have $$0=b^{(k)}_0\leq a^{(k)}_1\leq b^{(k)}_1 < a^{(k)}_2 \leq b^{(k)}_2 < \cdots < a^{(k)}_r\leq b^{(k)}_r \leq a^{(k)}_{r+1} = n_k $$ $$\sum_{s=0}^r (a^{(k)}_{s+1}-b^{(k)}_s) \leq \kappa $$ and $f^j(y_k)\in V_{i_s}$ whenever $a^{(k)}_s\leq j \leq b^{(k)}_s$. In order to avoid heavy notation we will write $a_i=a^{(k)}_i$ and $b_i=b^{(k)}_i$, omitting the explicit dependence on $k$ until we need to focus on it.

Next we expand $\hat{f}^{n_k}(x_k)-x_k$ as a telescopic sum
$$\hat{f}^{n_k}(x_k)-x_k = (\hat{f}^{a_{r+1}}(x_k) - \hat{f}^{b_r}(x_k)) + (\hat{f}^{b_r}(x_k) - \hat{f}^{a_r}(x_k))+\cdots +  (\hat{f}^{a_1}(x_k)-\hat{f}^{b_0}(x_k)) $$
which allows us to obtain the bound
$$\left| (\hat{f}^{n_k}(x_k) - x_k) - \sum_{s=1}^r (\hat{f}^{b_s}(x_k)-\hat{f}^{a_s}(x_k)) \right| \leq \kappa\delta_f $$ where we recall that $\delta_f = \sup\{|\hat{f}(y)-y|:y\in\Sigma_g^{ab}\}$.
Now we consider $y^s_k\in\Lambda_{i_s}$ for $s=1,\ldots,r$, given by applying Lemma \ref{l.saltos3} to $y_k$ for each $i_s$.  Thus $f^j(y_k)$ and $f^j(y^s_k)$ are in the same element of $\mathcal{P}_{i_s}$ whenever $a_s\leq j \leq b_s$. Let $x^s_k$ be the lift of $y^s_k$ such that $\hat{f}^{a_s}(x^s_k)$ is in the same fundamental domain as $\hat{f}^{a_s}(x_k)$. Equivalently, we may require that $\hat{f}^{a_s}(x^s_k)$ is in the same component of $\pi_{ab}^{-1}(V_{i_s})$ as $\hat{f}^{a_s}(x_k)$.

Since $\mathcal{P}_{i_s}$ is a rotational Markov partition, we get that $\hat{f}^{b_s}(x^s_k)$ is in the same fundamental domain as  $\hat{f}^{b_s}(x_k)$, using a similar argument to that of Lemma \ref{l.moving}. Thus $$\left| (\hat{f}^{b_s}(x_k)-\hat{f}^{a_s}(x_k)) - (\hat{f}^{b_s}(x^s_k)-\hat{f}^{a_s}(x^s_k))  \right|\leq 2\, \textrm{diam}(D)$$ where we recall that $\pi_{ab}(x^s_k)\in\Lambda_{i_s}$.

Combining the two previous bounds, we may conclude that $$v=\lim_k \frac{1}{n_k} \sum_{s=1}^r (\hat{f}^{b_s}(x_k)-\hat{f}^{a_s}(x_k)) = \lim_k \frac{1}{n_k}\sum_{s=1}^r (\hat{f}^{b_s}(x^s_k)-\hat{f}^{a_s}(x^s_k)) $$ which we will write as $$v = \lim_k \sum_{s=1}^r \frac{b_s-a_s}{n_k}\cdot
\frac{\hat{f}^{b_s}(x^s_k)-\hat{f}^{a_s}(x^s_k)}{b_s-a_s} $$

As we study the limit as $k\to+\infty$, it is convenient to recall explicitly the dependence on $k$ of $a_s=a^{(k)}_s$ and $b_s=b^{(k)}_s$. Recalling their definition and point (2) in Corollary \ref{l.entornos3}, it is clear that $$\sum_{s=1}^r \frac{b^{(k)}_s-a^{(k)}_s}{n_k} \to 1  \mbox{ and } \frac{b^{(k)}_s-a^{(k)}_s}{n_k}\in [0,1].$$ Passing to an appropriate sub-sequence in $k$ we may assume convergence: $$\frac{b^{(k)}_s-a^{(k)}_s}{n_k}\to t_s  \mbox{ for } t_s\in [0,1] \mbox{ with } \sum_{s=1}^r t_s = 1, \mbox{ and also }$$
$$  \lim_k\frac{\hat{f}^{b^{(k)}_s}(x^s_k)-\hat{f}^{a^{(k)}_s}(x^s_k)}{b^{(k)}_s-a^{(k)}_s} = v_s \mbox{ for } v_s \in \rho_{\Lambda_{i_s}}(f)  $$
Therefore we get $v = \sum_{s=1}^r t_sv_s \in \rho_{\mathcal{C}}(f) = \textrm{conv}(\rho_{\Lambda_{i_1}}(f),\ldots,\rho_{\Lambda_{i_r}}(f)) $, as desired. This concludes the proof of Theorem \ref{t.rhorhochain}.

config: arxiv