TITLE: Horizontal tangent line
QUESTION [0 upvotes]: I need some verification on this problem, not sure if I did it right.
Find all points on the level surface
$$x^3 − 3x − y^2 + 4y + z^3 = 10$$
where the tangent plane is horizontal.
So I take the gradient,
$$f_x = 3x^2 -3$$
$$f_y = -2y + 4$$
So set them to $0$ and solve, getting $x = 1, x= -1, y = 2$
This is the part that confused me. I know you plug $x$ and $y$ back in to find the $z$ component, but this is the first problem I've done where I have two values for a variable. So I plugged both $x$ values in, getting $(1,2,2)$ and $(-1, 2, \sqrt[3]{4})$
Would this be correct, or am I off base?

REPLY [1 votes]: At least it seems right to me. If you take the gradient, then you get $\nabla f = (3x^2-3, -2y+4, 3z^2)$. Since the gradient is normal to surface, if tangent is horizontal, then gradient is vertical, i.e. $f_x=0$ and $f_y=0$, and you got the solution. Notice the and here, you must satisfy both condition. Your solution are ($x_1$ or $x_2$) and $y$, which means $(x_1, y)$ or(edited, sorry I didn't notice this mistake until now) $(x_2, y)$


TITLE: Variants of the change-of-variables formula
QUESTION [0 upvotes]: Consider the following change of variables formula for $f:X\rightarrow Y$, that holds for any "reasonable" $g:B\subseteq Y \rightarrow \mathbb{R}$ and $A\subseteq X$
$$ \int_B g(x)\ {\rm d}(x)=\int_Ag\bigl(f(u)\bigr)\>|J_f(u)|\>{\rm d}(u),$$where  $|J_f(u)|$ denotes the jacobian, and $f(A)=B$ and $f$ is essentially injective.
I have two questions regarding this formula:
1) What would be the most general $g$ that would pass as "reasonable" and the most general notion of integral for that the transformation formula holds ?
2) One can define that a function $f:X\rightarrow Y$ is area-preserving, if $$\mu\bigl(f^{-1}(B)\bigr)=\mu(B)\qquad\forall B\subset Y\ \tag{1}$$and then show, if $f$ is essentially injective, as it is done in this answer (to which this question is a follow-up), by using the above formula and the fact that $(1)$ is for such an $f$ equivalent to $\mu(f(A))=\mu(A)\ \forall A\subseteq X$, that $(1)$ is equivalent to $\det( J_f(u))=\pm 1$ for all $u\in A$ and all $A\subseteq X$.
Now if moreover we had $J_f(u)=+1$, then intuitively (by analogy to linear algebra) this should mean that $f$ is also orientation-preserving. But is  there is geometric definition of "orientation-preserving" other than defining by $\det (J_f(u)) =+1$ (just as there is a geometric definition of "area-preserving", different than defining "area-preserving to mean $\det( J_f(u)) =±1$), so that I could you that definition and then try to show, maybe by using the change of variables formula similar to the linke answer, that that implies $\det( J_f(u))=+1$ ?
(I'd also be thankful for a reference to books or articles, if these answer my question, to spare you from typing a lot - although I don't have anything against a complety written answer :) )

REPLY [1 votes]: As for your first question, this is an old and extensively studied problem. This depends on the kind of integral used. For example, the Kurzweil-Henstock integral has a nice multidimensional change of variable theorem (see any serious book on the Kurzweil-Henstock integral). There is also the so-called geometric integral, with nice Stokes formulae.
Notice also that it has been shown that Fubini's theorem and the change of variable theorem are in some sense contradictory each with the other: you cannot build an integral that has at the same time a "good" Fubini theorem and a "good" change of variable theorem (I think this is shown in a book of Pfeffer).
Regarding your question about orientation, I think the right question is first of all: what is orientation? the only simple way to define it seems to be, indeed, with the notion of determinant. So, I don't think there is something "bad" by defining $f$ to be "orientation preserving" using the determinant of the Jacobian. Furthermore, it seems necessary to use  the differentials of $f$ because your notion of "orientation preserving" is essential local (have you another "global" interpretation?). On the contrary, the fact that |det(J)|=1 implies area preservation is a theorem, that depends on some hypothese about $f$ (at least differentiability). So, the two things are not similar. And to answer more prosaically, I have personally never seen such a notion.


TITLE: Identity involving shifted Legendre coefficients
QUESTION [1 upvotes]: For small values of $n$ ($2\leqslant n\leqslant 5$), the coefficients $a_k = (-1)^k{n\choose k}{n+k\choose k}$ of the shifted Legendre polynomial $\tilde{P}_n(x)$ satisfy the identity $\displaystyle\sum_{k=1}^n \frac {ka_k}{(n+k)(2k+1)} = \frac{(-1)^n}{4n^2-1}.$ Does that identity hold for all $n$? If so, how might one prove it?

REPLY [3 votes]: If we write the right side of Robert's identity as
$$(-1)^n\frac{(\nu-2)(\nu-4)\cdots(\nu - 2n+2)}{(\nu+2)(\nu+4)\cdots(\nu+2n)},$$
we see that the identity is a partial fraction expansion of a proper rational function. (This is a littler simpler if we replace $\nu$ with $2\nu$.)


TITLE: Contrapositive gives more info than implication?
QUESTION [2 upvotes]: Please forgive my childish drawing, this is the quickest way I could think to express my question.
Though the truth values of an implication and its contrapositive are the same, they do not seem to give the same amount of information, as represented in my horrible little sketch by which areas of the diagram are colour defined by each relation.
Isn't this a problem in their "equivalence" if one tells you more than the other?
(It seems that the contrapositive describes a smaller set on the diagram, which I am equating to more information).

REPLY [1 votes]: The reason you think that is that you don't draw $\lnot p$ in your diagram. If you think about sets, $p\rightarrow q$ means that $p\subseteq q$. The contrapositive means that the $q^c\subseteq p^c$, the complements have the reverse relation between them.


TITLE: A Nonlinear System of Trigonometric Equations
QUESTION [2 upvotes]: folks! I am getting the following system of trigonometric equations which has come as a product of my research. But, I have tried a lot with no success, to solve this system. Can anyone help? Thank you.
Find $\theta_1$ and $\theta_2$.
$$\left(\frac{\cos\alpha_1}{\cos\theta_1}\right)^2+\left(\frac{\cos\alpha_2}{\cos\theta_2}\right)^2=A\quad(A \ \mbox{is a constant},\ A\in(0,1))\tag{1}$$
$$\frac{1}{\cos^2\alpha_1}\left(\frac{1}{\sin^4\theta_1}-1\right)=\frac{1}{\cos^2\alpha_2}\left(\frac{1}{\sin^4\theta_2}-1\right)\tag{2}
$$
Note: I know that I can reduce this to finding roots of a polynomial, but I wonder if there is an elegant method to find a solution to this problem.
Edit: The equations @DavidHolden has written are closer to the actual equations I wanted to solve. The algebraic version of the equations that I want to solve is the following
Find $x_1,x_2\quad 0\le a_1\le x_1\le 1, 0\le a_2\le x_2\le 1$ such that
$$x_1+x_2=A\quad \tag{1}$$ $$a_1\left(\frac{1}{x_1^2}-\frac{1}{(x_1-a_1)^2}\right)=a_2\left(\frac{1}{x_2^2}-\frac{1}{(x_2-a_2)^2}\right)\tag{2}$$ Note that if in the Equation(2) instead of $a_1,\ a_2$, we have $a_1^2,\ a_2^2$ multiplied then we immediately have the solution $$x_1=\frac{a_1}{a_1+a_2}A,\ x_2=\frac{a_2}{a_1+a_2}A$$
Further Edit: The Problem can be restated as below: With $0\le a_1\le x_1\le 1,\ 0\le a_2\le x_2\le 1$ find $x_1,\ x_2$ such that $x_1+x_2=A$ and $$f'(x_1,a_1)=f'(x_2,a_2)$$ where $$f(x,a)=g(x/a);\quad g(x)=\frac{1}{x(x-1)}$$

REPLY [1 votes]: although not much of a step in solving your problem, perhaps it is of use to simplify a little, so certain salient features are more clearly visible. if we set $x_i = cos^2 \; \theta_i$, and $a_i=cos^2 \alpha_i $ then the equations become:
$$\frac{a_1}{x_1} +\frac{a_2}{x_2} =A \\
\frac{a_2}{(1-x_1)^2} - \frac{a_1}{(1-x_2)^2} = a_2-a_1
$$
is this the sort of thing you meant when you mentioned reducing this to finding roots of a polynomial?


TITLE: Find the solution to the matrix optimization problem? SVD
QUESTION [0 upvotes]: $\max_{~\mathbf{X}\in \mathbb{C}^{m\times n}}~ ~~Tr(\mathbf{A}^H \mathbf{X})$
s.t. $\mathbf{X}^H \mathbf{X} = \mathbf{I}_n$, where $\mathbf{A} \in \mathbb{C}^{m\times n}$ and has full column rank.
Can we relax the = in constraint to be $\le$, and use KKT condition to solve it? On the other hand, the optimal solution seems to be related to the SVD of $\mathbf{A}$.
Update: assume the SVD of $\mathbf{A}$ to be $\mathbf{A} = \mathbf{V}\mathbf{\Sigma}\mathbf{U}^H$, then we just take $\mathbf{X}$ to be $\mathbf{X}^* = \mathbf{V}\mathbf{\Lambda}\mathbf{U}^H$, where the diagonal entries of $\mathbf{\Lambda}$ (diagonal matrix) is $\lambda_i = sign(\sigma_i)$. It can be verified that $\mathbf{X}^*$ is the optimal solution satisfying the constriant and with the optimal value to be $\sum_{i=1}^n |\sigma_i|$ (w.l.o.g., assume $n <= m$).

REPLY [1 votes]: Because $X^HX = I$, all singular values of $X$ are equal to $1$. With this inequality, we have
$$
\operatorname{tr}(A^HX) \leq \sigma_\max(X) \cdot \operatorname{tr}(\sqrt{A^HA}) = \operatorname{tr}(\sqrt{A^HA}).
$$
Thus, it suffices to find an $X$ that satisfies

$\operatorname{tr}(A^HX) = \operatorname{tr}(\sqrt{A^HA})$,
$X^HX = I$.


TITLE: Phase difference between the driver and the oscillator
QUESTION [1 upvotes]: Please could someone explain the concept in the text below for me?

In a driven oscillator, the phase of the driver and the phase
of the oscillator are not always the same. At low frequency
($\omega\ll\omega_0$) the oscillation is in phase with the driver.
At high frequency ($\omega\gg\omega_0$) the oscillation and the
driver are out of phase. The phase difference between the driver
and the oscillator is given by:
$$\phi(\omega)=\arctan\left(
\frac{-\gamma\omega}{\omega_0^2-\omega^2}\right). \tag{1.6}$$

If the oscillator is in phase with the driver at low frequency then surely this would cause the oscillator to resonate, but there should only be one frequency(the natural frequency)that can achieve resonance?
I think I am confusing things here...please help! Thanks in advance.

REPLY [0 votes]: Take a mug with a handle, and several elastic bands.  Loop one band through the handle, and join a few more on to it, and put your middle finger through the final loop.   The mug + bands acts as a resonant system and if you displace it (with your other hand) you'll see damped oscillations at the resonant frequency.
Hold your arm horizontal and move it up and down slowly in the best approximation to a sine wave you can manage. The mug will follow your hand: at low frequencies driver and oscillator are in phase, with a response factor of unity.
Now make your motion a bit faster.  The mug will still follow you but the  oscillations get bigger.  That $(\omega - \omega_0)^2$ in the denominator starts to get busy.
Keep increasing the speed gently, and you'll hit resonance and the mug will jump around all over the place. You may have to pause the experiment at this point.
Move your hand rapidly, still trying to imitate a sine wave, and you're above the resonant frequency and the response gets smaller. The faster you can wobble your hand, the smaller the response. And the mug is now out of phase with the motion of the hand.  You can see this and, what's more, you feel it: at high frequencies your hand is moving one way and the mug is moving the other.
Do try this at home! There's probably a video on YouTube, but nothing teaches you about forced oscillation phase and amplitude response like actually feeling it.


TITLE: Will ions in a solution emit radiation from an electric discharge?
QUESTION [0 upvotes]: If I pump enough current through a water solution with ions in it, will the ions in the solution emit EM radiation as the water heats up to form a "spark"/plasma? Basically trying to make an Inductively Coupled Plasma-Optical Emission Spectrometer but simplifying the plasma generation by generating it directly in the solution using high currents.

REPLY [0 votes]: If you "pump current" through water you will generate $H_{2}$ and $O_{2}$ gas through a process called electrolysis.  The two gases form at different locations, one near the cathode and one near the anode (I can never remember which).  If you were to create a spark near the $O_{2}$ side, you would likely cause a rapid combustion of said $O_{2}$ (assuming it's not completely pure $O_{2}$, which won't combust).
If you ramp up the current enough, the bigger issue initially will be heat.  You could dump MAs of current into the water and cause it to flash boil (or chemically split into $H_{2}$ and $O_{2}$, don't recall which is energetically favorable here).  Without a huge electrical potential, you would then cease to conduct the current as water vapor is not very conductive (well, pure water is an insulator as well).  I have no idea if it's possible to drive this quickly enough to cause a stable plasma without multiple other mechanical problems obstructing your goal (e.g., in principle you can dump as much current as you want into the system, but that doesn't mean the enclosure or current-carrying materials will handle it).
In summary, I am not sure ionizing water in this way is the most efficient method for generating plasmas in situ.  It would take a rather large amount of energy just to disassociate the $H_{2}O$ compound and then another large amount of energy to disassociate the $H_{2}$ and $O_{2}$, then even more energy to ionize the monatomic $H$ and $O$.  All of this would need to be done before the molecules could recombine.


TITLE: Tangents of Rectangular hyperbola
QUESTION [1 upvotes]: P,Q,R are points on a rectangular hyperbola, and PQ perpendicular to PR. Prove that the tangent at P is perpendicular to QR.

REPLY [1 votes]: Using parametric points, let P$(t_1)$,Q$(t_2)$ and R$(t_3)$ are the required points.
Slope of PQ is $-\frac{1}{t_1t_2}$ and of PR is $-\frac{1}{t_1t_3}$
Given that $-\frac{1}{t_1t_2}$=$t_1t_3$, $\because$ PQ $\perp$ PR
$t_1^2t_3t_2=-1$ $\implies$ $t_1^2=-\frac{1}{t_3t_2}$ $\cdots$(1)
Slope of tangent at P is $-\frac{1}{t_1^2}$ ($m_1$) and slope of QR is $-\frac{1}{t_2t_3}$ ($m_2$)
Now, we have to prove that $m_2$=-$\frac{1}{m_1}$, Tangent at P is $\perp$ to QR.
$t_1^2=-\frac{1}{t_3t_2}$
Which is true!


TITLE: Random points in sphere with probability p(r)
QUESTION [2 upvotes]: How to pick random uniformly distributed points in a sphere has been asked before. The difference is that I don't want uniform distribution, rather I would like the number density to scale by $r^{-1}$.
The only method I can think of is to generate random x, y and z coordinates, reject those that are outside the sphere and then do another test. For simplicity I chose to distribute points between radius 1 and the sphere's radius R, with these values I calculated a probability function $p(r)=\frac{1}{\rm{ln}(R)r}$. The test was that I generated another random number and rejected the point if that number was larger than p(r). However I don't know if this is correct, and I'm hoping for a better idea since it was very slow for large R.

REPLY [0 votes]: If you look at the accepted answer for the post you linked, you see that the direction is generated by sampling from a multivariate normal distribution, and then the radius is chosen according to the desired distribution. In your case, you don't need to define a minimal radius $R_0 > 0$ because when you multiply the scaling factor $1/r$ for probability of the radius by the surface area of the sphere $\Theta(r^2)$ you get $\Theta(r)$, and so you have $P(r \leq R) \propto \int_{0}^R (1/r)r^2 dr = \Theta(R^2)$ where you have a maximum radius $R_{max}$. This gives you your cdf (cumulative distribution function ) of $f(R) = P(r \leq R) = R^2/R_{max}^2$ for sampling the radius. The inverse of the cumulative distribution function is $g(X) = R_{max} \sqrt{X}$. If you sample a uniform random variable $X$ from $[0,1]$ and compute $r = g(X)$, this gives you the desired distribution on the radius $r$ that has cumulative distribution function $f(R)$.  See http://en.wikipedia.org/wiki/Inverse_transform_sampling for an explanation on inverse transform sampling.


TITLE: What is the technical difference between a formal and informal power series?
QUESTION [4 upvotes]: In my lecture notes the professor wrote that $$e^x = \Sigma \frac{x^k}{k!}$$
is a formal power series because we can plug in whatever we want in $x$ and both side will equate
This is an obvious conclusion, I wonder what he means by formal power series and when is a power series considered informal.

REPLY [1 votes]: An expression of the form $a_0+a_1x+a_2x^2+a_3x^3+ \cdots$, where the $a_n$ are arbitrary real (or complex) numbers, might not have a meaningful value except in the very limited case $x=0$ (when of course it equals $a_0$). For example, consider $\sum_{n=0}^\infty n!x^n.$ nevertheless, one can perform formal algebraic operations on such series, such as addition and multiplication, to produce other such series, by the same rules that apply for series that converge for a nontrivial range of the $x$ variable. These formal series cannot be regarded as functions, like the series for (e.g.) e$^x$. However, they can be given a meaningful mathematical definition as sequences: $\sum_{n=0}^\infty a_nx^n$ is identified with the sequence $(a_0,a_1,...)$, and addition and multiplication are performed on these sequences just as for power series. Thus $$(a_n)_{n\in\Bbb N}+(b_n)_{n\in\Bbb N}=(a_n+b_n)_{n\in\Bbb N}$$ and $$(a_n)_{n\in\Bbb N}(b_n)_{n\in\Bbb N}=\left( \sum_{j=0}^na_jb_{n-j}\right)_{\!n\in\Bbb N}.$$


TITLE: Recursive relationships for ternary strings
QUESTION [1 upvotes]: If one were to have a ternary string with no repetition of consecutive $0$'s or $1$'s how would you define the recursive relation?
The first way I tried to solve was to assume $2$ was the last digit where we could have $a_{n-1}$ possible combinations due to no restrictions. For $1$ we can only have $01$ or $02$ and likewise for $0$ we can have $10$ or $20$ so the total strings possible for both is $4a_{n-2}$. I thought we would add it up to get $a_n= a_{n-1}+ 4a_{n-2}$.
This is the wrong answer and the other way I thought of solving it was to take into account that there can be any two possible last digit numbers for this to work for any possible $a_{n-1}$ string scenarios not including the $22$ combo which would be $a_{n-2}$. This gives the correct answer to be $a_n= 2a_{n-1}+a_{n-2}$. I was just wondering why my first reasoning doesn't match the second one. Thanks for your time Varun G.

REPLY [0 votes]: Let $A_n$ be the set of strings in $\{0,1,2\}^n$ not having $00$ or $11$ as substrings of consecutive characters, and $a_n=|A_n|$. Every element of $A_n$ is given by the concatenation of $2$ with an element of $A_{n-1}$, or by a concatenation of $02,12$ with an element of $A_{n-2}$, or by a concatenation of $012,102$ with an element of $A_{n-3}$, or by a concatenation of $0102,1012$ with an element of $A_{n-4}$ and so on. This gives:
$$ a_0=1,\quad a_1 =3,\quad a_2=7,\qquad a_{n}=a_{n-1}+2a_{n-2}+2a_{n-3}+\ldots+2a_{1}+2a_0+2.$$
Now, by induction, it is easy to check that:
$$ a_{n+1} = 2a_n + a_{n-1} $$
so $a_n$ is given by the following OEIS entry.

REPLY [0 votes]: If the last digit of a good $n$-digit string $\sigma$ is $2$, the string can indeed be an extension of any good string of length $n-1$. The problem is with your analysis of the other two cases.
If the last digit is $1$, there are two cases: either $\sigma$ ends in $21$, in which case the first $n-2$ digits can be any good string, or it ends in $01$. If it ends in $01$, it must end in $201$ or $101$ (assuming that $n\ge 3$, of course). If it ends in $201$, the first $n-3$ digits can be any good string. If it ends in $101$, however, and $n\ge 4$, then it must end in $2101$ or $0101$. Clearly we can keep going.
If you pursue this reasoning to the end, you’ll find that when the last digit is $1$ you have
$$a_{n-2}+a_{n-3}+\ldots+a_0+1\tag{1}$$
strings, where the last term counts the unique string of length $n$ that alternates $0$ and $1$ and ends in $1$. Essentially the same reasoning tells you that $(1)$ also counts the good strings of length $n$ ending in $0$, so you get the recurrence
$$a_n=a_{n-1}+2\left(1+\sum_{k=0}^{n-2}a_k\right)\;.$$
This isn’t terribly nice, but you can use it to get the second-order recurrence that your second approach gave you. First note that
$$a_{n-1}=a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\;.$$
Thus,
$$\begin{align*}
a_n&=a_{n-1}+2\left(1+\sum_{k=0}^{n-2}a_k\right)\\
&=a_{n-1}+2a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\\
&=a_{n-1}+a_{n-2}+\left(a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\right)\\
&=a_{n-1}+a_{n-2}+a_{n-1}\\
&=2a_{n-1}+a_{n-2}\;.
\end{align*}$$


TITLE: Longest path on directed acyclic graph when the weight is defined on the pair of edges
QUESTION [2 upvotes]: Given a directed acyclic graph $G=(V,E)$ with a source node $s$ and a sink node $t$, and we have a weight function that is defined on $E\times E$, $f:E\times E\to R^{+}$. We want to find a $s$-$t$ path $P$ that maximizes the sum $\sum_{\forall e_i,e_j\in P} f(e_i,e_j)$.
Does this problem have a polynomial solution?

REPLY [2 votes]: The quadratic shortest path problem (QSSP) can be reduced to the problem. Because QSSP is NP-hard [1], the problem in the question has no polynomial-time solution unless P = NP.
To remove the restriction of the acyclicity of the graph, we can use the standard technique of using $V \times \{0,\dots,|V|\}$ as the new vertex space where the integer in a pair represents the length of the current path, so an edge $(u,v)$ is converted to $((u,k), (v,k+1))$.
Furthermore, by adding edges $((t,k), (t,k+1))$ corresponding a loop at the destination, we ensure all paths have the same path length.
To convert the minimization problem to the maximization problem, let $W$ be a number larger than all weights and then convert weights as $W - f(e_1,e_2)$. Because all paths have the same length in the new graph, the ordering of the solutions is exactly reversed.

[1] Rostami, Borzou, et al. "On the quadratic shortest path problem." International Symposium on Experimental Algorithms. Springer, Cham, 2015. https://hal.inria.fr/hal-01251438/file/QSPPaperHal.pdf.


TITLE: Easy condition on a matrix $A$ such that $Au\geq 0$ for all vectors $u\geq 0$
QUESTION [2 upvotes]: A rather easy question, but my brain stopped working. I have a matrix $A$ that depends on various parameters in a non-trivial way. What would be a simple-to-check conditions on $A$ so that $Au\geq 0$ for any vector $u\geq 0$?

REPLY [4 votes]: A necessary and sufficient condition is that all entries of $A$ are $\ge 0$.


TITLE: Counting binary strings of length $n$ that contain no two adjacent blocks of 1s of the same length?
QUESTION [9 upvotes]: Is it possible to count exactly the number of binary strings of length $n$ that contain no two adjacent blocks of 1s of the same length? More precisely, if we represent the string as $0^{x_1}1^{y_1}0^{x_2}1^{y_2}\cdots 0^{x_{k-1}}1^{y_{k-1}}0^{x_k}$ where all $x_i,y_i \geq 1$ (except perhaps $x_1$ and $x_k$ which might be zero if the string starts or ends with a block of 1's), we should count a string as valid if $y_i\neq y_{i+1}$ for every $1\leq i \leq k-2$.
Positive examples : 1101011 (block sizes are 2-1-2), 00011001011 (block sizes are 2-1-2), 1001100011101 (block sizes are 1-2-3-1)
Negative examples : 1100011 (block sizes are 2-2), 0001010011 (block sizes are 1-1-2), 1101011011 (block sizes are 2-1-2-2)
The sequence for the first $16$ integers $n$ is:  2, 4, 7, 13, 24, 45, 83, 154, 285, 528, 979, 1815, 3364, 6235, 11555, 21414. For $n=3$, only the string 101 is invalid, whereas for $n=4$, the invalid strings are 1010, 0101 and 1001.

REPLY [2 votes]: I am gonna attempt to complement RobPratt's proposed approach involving inclusion exclusion and stars and bars and be that person who posts a horribly long formula.
Consider $$A_{n,k,r}=\left |\left \{0^{l_1}1^{k_1}\cdots 0^{l_r}1^{k_r}0^{l_{r+1}}\in \{0,1\}^n: k_i>0,k_i\neq k_{i+1}, \sum _{i=1}^rk_i=k \text{ and for $i\neq 1,r+1,$ }l_i>0\right \}\right |.$$ Our desired result will be $$A_n=\sum _{k=0}^n\sum _{r=0}^nA_{n,k,r}.$$
Notice that we can, by the multiplication principle, express $A_{n,k,r}$ as
$$A_{n,k,r}=|B_{n,k,r}|\times |C_{k,r}|,$$
where $$B_{n,k,r}=\left \{(l_1,\cdots ,l_{r+1})\in \left (\mathbb{Z}^{\geq 0}\right )^{r+1}:\sum l_i=n-k, l_i>0 \text{ for $1<i<r+1$}\right \}$$
represents the way to place the $0'$s and $$C_{k,r}=\{(k_1,\cdots ,k_r)\in \left (\mathbb{Z}^{> 0}\right )^{r}:\sum k_i=k,k_i\neq k_{i+1}\}.$$
represents the way to place the 1's.
By stars and bars we get that  $|B_{n,k,r}|=\binom{n-k-(r-1)+(r+1)-1}{(r+1)-1}=\binom{n-k+1}{r}.$ Now, consider the following set $C_{k,r,x}=\{(k_1,\cdots k_r)\in C_{k,r}:k_x=k_{x+1}\}$ which carries the words with at least one consecutive chunk of 1's of the same size(at index $x$). To illustrate the next step, notice that $|C_{k,r,x}|=\sum _{t=1}^{\lfloor k/2\rfloor}\binom{k-2t-1}{r-2-1},$ for any $1\leq x<r$ by assuming the summands at position $x$ and $x+1$ are the same, this value is given by $t.$
We can then express $$C_{k,r}=\binom{k-1}{r-1}-\sum _{\ell =1}^{r-1}(-1)^{\ell -1}\sum _{X\in \binom{[r-1]}{\ell}}\left | \bigcap_{x\in X} C_{k,r,x}\right |,$$
but now the problem starts again because we need to know how many chunks of elements(consecutive) are in the set $X$ for us to be able to know how many summands are equal. When we know this, we can use stars and bars.  Call thr number of chunks $s$ and call the size of $i-$th chunk $\ell _i.$ Notice that we want $\ell _i>0$ and $\sum \ell _i=\ell.$ We then associate a number $t_i$ to be the number in the summand of all elements in the $i-$th chunk (for a total contribution of $(\ell _i+1)t_i$ to the whole sum). We get then that
$$C_{k,r}=\sum _{\ell =0}^{r-1}(-1)^{\ell}\sum _{s = 0}^{\ell}\sum _{\substack{ \ell_1+\cdots +\ell_s=\ell \\ \ell _i,t_i>0}}\binom{r-1-\ell -(s-1)+(s+1)-1}{s+1-1}\binom{k-\left (\sum _{i=1}^s(l_i+1)t_i\right )-1}{r-(\ell+s)-1}.$$
Putting all this together we get
$$A_{n}=\sum _{k=0}^n\sum _{r=0}^n\binom{n-k+1}{r}\sum _{\ell =0}^{r-1}(-1)^{\ell}\sum _{s = 0}^{\ell}\sum _{\substack{ \ell_1+\ell_2+\cdots +\ell_s=\ell \\ \ell _i,t_i>0}}\binom{r-\ell}{s}\binom{k-\left (\sum _{i=1}^s(l_i+1)t_i\right )-1}{r-(\ell+s)-1}.$$
In this formula,by the combinatorial interpretation, treat $\binom{-1}{-1}=1.$
Using sage I get the sequence $2,4,7,13,24,45,83,154,\dots.$
For the moment I do not see any way to make this less painful.

Another approach that might yield to something. Construct the DFA associated with that language (fix the maximal number of chunks to be $n$ and the maximum number of $1's$ in each chunk to be $k.$) The DFA looks like an $k\times n$ array and consider the Chomsky-Schutzenberger technique One has to solve a system of $k(n-k)$ equations and then try to take the limit as $n,k$ go to $\infty.$ The system to solve in variables $R_{i,j}\in \mathbb{Q}[[x]]$ looks like
$$R_{i,j}=\begin{cases}xR_{i,j+1}+xR_{j,0}+[i\neq j] & \text{If }j>0\\
xR_{i,1}+xR_{i,0}+1 & \text{If }j=0.\end{cases}$$


TITLE: Period of a set of primes
QUESTION [4 upvotes]: Let $S$ be a set of primes. We call a positive integer $n$ a period of $S$ if $p\in S$ implies $q\in S$ for all primes $q$ with $q\equiv p\mod n$. Show that if $n_1$, $n_2$ are periods of $S$, then $\gcd(n_1,n_2)$ is a period of $S$.
The problem in this exercise is that the "base set" is the set of primes. Within all integers, you could simply use the Bézout identity.
I'm interested in a solution as elementary as possible. However, I guess something like Dirichlet's theorem on arithmetic progressions is needed.

REPLY [1 votes]: To show that $n = \gcd(n_1,n_2)$ is a period of $S$, let $p\in S$ be a prime
and $q$ be a second prime with $p\equiv q\mod n$. We have to show that $q\in S$.
If both numbers $n_1$ and $n_2$ are divisible by $p$, then $p\mid n$ and therefore $p\mid q$. Since $p$ and $q$ are prime, we get $q = p\in S$.
Otherwise, without loss of generality, $n_1$ is coprime to $p$. By Dirichlet, the set $p + n_1\mathbb{Z}$ containes infinitely many primes. So there is a prime $p'\equiv p\mod n_1$ such that $n_2$ is not divisible by $p$.
Since $n_1$ is a period of $S$, we have $p\in S \iff p'\in S$.
Furthermore, $p'\equiv q\mod n$.
So we may replace $p$ by $p'$.
In the same way, if $n_1$ and $n_2$ are both divisible by $q$, then $q = p\in S$. Otherwise, we may replace $q$ by a prime $q'$ such that neither $n_1$ nor $n_2$ are divisible by $q'$.
After the replacements, we got the additional preconditions $\gcd(p,n_1) = \gcd(p,n_2) = \gcd(q,n_1) = \gcd(q,n_2) = 1$.
Since $p\equiv q\mod \gcd(n_1,n_2)$, the system of congruence equations
\begin{align*}
r & \equiv p\pmod{n_1} \\
r & \equiv q\pmod{n_2}
\end{align*}
has the solution set $x + \operatorname{lcm}(n_1,n_2)\mathbb{Z}$ with some $x\in\mathbb{Z}$.
Assume there is a prime $d$ dividing both $x$ and $\operatorname{lcm}(n_1,n_2)$.
Without loss of generality, $d$ divides $n_1$ (otherwise, interchange the role of $n_1$ and $n_2$). From $x\equiv p\mod n_1$ we get $x = p + kn_1$ with $k\in\mathbb{Z}$. So $d$ is a divisor of $x - kn_1 = p$. Since $d$ and $p$ are prime, we get $d = p$ which contradicts $p\nmid n_1$.
So $x$ and $\operatorname{lcm}(n_1,n_2)$ are coprime. Now By Dirichlet, the solution set $x + \operatorname{lcm}(n_1,n_2)\mathbb{Z}$ containes a prime $r$.
From $p\in S$ and $r\equiv p\mod n_1$ and the precondition that $n_1$ is a period of $S$, it follows that $r\in S$.
Finally, from $r\equiv q\mod n_2$ and $n_2$ a period of $S$ we get $q\in S$.


TITLE: Sum of a dyadic sequence satisfying $\delta\omega_\lambda \leq \omega_{2\lambda}\leq \kappa\omega_\lambda$ with $1<\delta<\kappa$
QUESTION [4 upvotes]: I was reading the proof of a lemma and I found something that seemed to be a "trivial inequality" but I haven't been able to prove it, so I was wondering if anyone has a good answer for it.
Lets fix two real numbers $1<\delta<\kappa$. Now, consider a sequence $(\omega_{\lambda})_{\lambda}\subset\mathbb{R}_+$ with $\lambda$ running over the integer dyadic numbers and where $\mathbb{R}_+=(0,+\infty)$. Suposse that $(\omega_\lambda)_\lambda$ satisfies the following inequalities: $$
\delta\omega_\lambda \leq \omega_{2\lambda}\leq \kappa\omega_\lambda.
$$
Then, there exists a constant $c>0$ such that $$
\sum_{\mu\geq \lambda/8}\omega_\mu^{-1}\leq c\omega_{\lambda}^{-1}.
$$
Here, notation $\sum_\lambda \omega_\lambda$ means $\sum_{n=0}^{+\infty}\omega_{2^n}$. I think it should be a silly trick using power series but I am getting confuse since I am not very used to dyadic stuffs.

REPLY [4 votes]: As Steven Stadnicki suggested in the comments, if 'integer dyadics' means numbers of the form $2^n$, we can rewrite the problem with $\mu_i := \omega_{2^i}$. The assumption is now :
$$\forall i \geq 0, \quad \delta \mu_i \leq \mu_{i+1} \leq \kappa \mu_i$$
We want to prove that there exists $c > 0$ such that :
$$\forall n \geq 0,\quad \sum_{i \geq ~\max(n - 3, 0) } \frac1{\mu_i} \leq c \frac1{\mu_n}$$
First, we can suppose $n \geq 3$ because for $0 \leq n \leq 2$ the inequality is true with $c_1 = \mu_2 \times (\sum_{i \geq 0 } \frac1{\mu_i})$.
Heuristically, $\mu_i$ should behave as a geometric sequence. Remember that, to compute the sum $\sum_{i \geq n} q^i$ (with $0 < q < 1$) we use a telescopic sum :
$$\sum_{i \geq n} q^i (1 - q) = \sum_{i \geq n} q^i - q^{i+1} =  q^n $$
In fact, we can do the same with our problem :
$$\sum_{i \geq n-3} \frac1{\mu_i} (1 - \frac1{\delta}) = \sum_{i \geq n-3} \frac1{\mu_i} - \frac1{\mu_i \delta} \leq  \sum_{i \geq n-3} \frac1{\mu_i} - \frac1{\mu_{i+1}} = \frac1{\mu_{n-3}} \leq \kappa^3 \frac1{\mu_{n}} $$
We used the assumption in the two inequalities.
We conclude by taking $c = \max(c_1, \frac{\kappa^3}{(1 - \frac1{\delta})})$


TITLE: Reference frame and conservation of energy
QUESTION [1 upvotes]: Say spaceship $\alpha$ burns a portion of its fuel to leave planet A and is cruising through space at 10 m/s relative to the surface from which it launched. Spaceship $\alpha$ is being observed by spaceship $\beta$, which launched from planet B. The relative velocities of the two planets are such that spaceship $\alpha$ is moving at 50 m/s relative to planet B.
Spaceship $\alpha$ plans to increase its speed by burning some amount of fuel (which is converted completely to kinetic energy), and it communicates its intentions to spaceship $\beta$. Astronauts on each ship use conservation of energy to predict the change in velocity of the ship after the fuel is burned, with
$$\frac{1}{2}m v_2^2 = \frac{1}{2}m v_1^2 + E_{burn}$$
and
$$\Delta v = v_2 - v_1$$
The chemical potential of the fuel burned shouldn't be affected by the observer's reference frame. However, astronauts on spaceship $\alpha$ consider their initial velocity to be 10 m/s, but from the perspective of astronauts on spaceship $\beta$ who launched from planet B, it is 50 m/s. This will cause the astronauts to calculate different values for $\Delta v$.
Clearly, $\Delta v$ won't depend on reference frame. What, then, is the criteria for selecting $v_1$ such that the correct $\Delta v$ is calculated? With the spaceship flying through space, choosing planet A to have zero velocity seems as arbitrary as choosing planet B.

REPLY [2 votes]: When you burn the fuel it releases an energy $E_\text{burn}$, but your mistake is to assume that this all goes into the kinetic energy of the ship.
Rocket fuel works by accelerating itsef relative to the ship and leaving the ship at high velocity as exhaust gases. Momentum is conserved so when the fuel goes one way the ship goes the other way. The energy $E_\text{burn}$ is divided between the kinetic energy of the ship and the kinetic energy of the exhaust gas:
$$ E_\text{burn} = \Delta E_\text{ship} + \Delta E_\text{exhaust} $$
As you change reference frames you change the velocities, and hence the kinetic energies, of both the ship and the exhaust gas. The individual values of $\Delta E_\text{ship}$ and $\Delta E_\text{exhaust}$ will be different for different observers, however when you add together the change in the two kinetic energies it always adds up to the energy released by the fuel regardless of what observer is doing the calculation.


TITLE: Number of elements of order 2 in $D_n/Z(D_n)$
QUESTION [2 upvotes]: This exercise in supplimentry exercises for chapter 9 to 11 of contemporary Abstract algebra book by Gallian

Let $n=2m$, where $m$ is odd. How many elements of order $2$ does the
group $D_n/Z(D_n)$ have?

Answer of this exercise given ( in "selected answer" section) is: $m$
elements

Author used the notation $D_n$  (everywhere in book) to represent Dihedral group of order $2n$. But according to me, if we use this notation(by author) then given answer is wrong!
(According to me, if we use the notation $D_{2m}$ for Dihedral group of order $2m$ then answer is true! that is we consider the group $D_{2m}$ Dihedral group of order $2m$; where $m$ is odd  then number of elements of order $2$ in $D_{2m}/Z(D_{2m})$ is $m$ is true! )
Is, am I correct? Please help.

REPLY [0 votes]: n=2m and m is odd, here Z(D_n) consists of two elements that is {R_0,R_180} and since m is odd then no other elements such R_90,R_270 can exist in Z(D_n)
And since the reflection are distinct then the no of elements of order 2 is just n/3=m.


text:
\begin{document}

\maketitle

\begin{abstract}
We consider Mahler functions $f(z)$ which solve the functional equation
$f(z) = \frac{A(z)}{B(z)} f(z^d)$ where $\frac{A(z)}{B(z)}\in \QQ(z)$ and
$d\ge 2$ is integer. We prove that for any integer $b$ with $|b|\ge 2$
either $f(b)$ is rational or its irrationality exponent is rational. We
also compute the exact value of the irrationality exponent for $f(b)$ as
soon as the continued fraction for the corresponding Mahler function is
known. This improves the result of Bugeaud, Han, Wei and
Yao~\cite{bhwy_2016} where only an upper bound for the irrationality
exponent was provided.

\end{abstract}

\section{Introduction}

Consider a Laurent series $f(z)\in\QQ((z^{-1}))$. It is called a {\it Mahler
function} if for any $z$ inside the disc of convergence of $f$ it satisfies
the equation of the form
$$
\sum_{i=0}^n P_i(z)f(z^{d^i})=Q(z)
$$
for some integers $n\ge 1, d\ge 2$, and polynomials $P_0,\ldots, P_n, Q\in
\FF[z]$ with $P_0P_n\neq 0$. The values $f(b)$ for integers $b$ inside the
disc of convergence of $f$ are called {\em Mahler numbers}. In this paper we
investigate the following question:

\begin{problem}\label{probc}
Find the set $\LLL_M$ of irrationality exponents of irrational Mahler
numbers.
\end{problem}

Sometimes we will call the set $\LLL_M$ \emph{the spectrum} of irrationality
exponents of Mahler numbers. Recall that the irrationality exponent of a real
number $\xi$ is the supremum of real numbers $\mu$ such that the inequality
$$
\left|\xi - \frac{p}{q}\right|<q^{-\mu}
$$
has infinitely many rational solutions $p/q$. This is one of the most
important approximational properties of real numbers indicating how well
$\xi$ is approached by rationals. Note that by the classical Dirichlet
approximation theorem we always have $\mu(\xi)\ge 2$.

Similar questions have been recently risen by several authors. In 2008,
Bugeaud~\cite{bugeaud_2008} proved that for any rational $\omega$ there are
infinitely many automatic numbers with the irrationality exponent equal to
$\omega$. It is well known \cite{becker_1994} that automatic numbers are also
Mahler, therefore Bugeaud's result straightforwardly implies that $\LLL_M$
contains all rational numbers not smaller than two. Later in 2009,
Adamczewski and Rivoal~\cite{adamczewski_rivoal_2009} commented on that
result with the following problem:

\begin{problem}\label{proba}
Is it true or not that the irrationality exponent of an automatic number is
always a rational number?
\end{problem}

Bugeaud, Krieger and Shallit~\cite{bgs_2011} extended the question to the set
of morphic numbers. In particular, they show that the spectrum of
irrationality exponents of morphic numbers, on top of $\QQ$, contains every
Perron number $\omega\ge 2$. Recall that a Perron number is a positive real
algebraic integer, which is greater in absolute value than all of its
conjugates. With respect to this result the following problem was posed:

\begin{problem}\label{probb}
Determine the set of irrationality exponents of morphic numbers. In
particular, is it true that the irrationality exponent of a morphic number is
always algebraic?
\end{problem}

In some sources~\cite{gwz_2016}, Problems~\ref{proba} and~\ref{probb} were
referred as conjectures.

In this paper we restrict our research to Mahler functions $f(z)$ which solve
the following functional equation
\begin{equation}\label{def_feq}
f(z) = \frac{A(z)}{B(z)} f(z^d),\qquad A,B\in\QQ[z],\; B\neq 0.
\end{equation}

\begin{theorem}\label{th2}
Let $f(z)\in \QQ((z^{-1}))$ be a solution of~\eqref{def_feq} and $b\in\ZZ$ be
inside the disk of convergence of $f(z)$. Assume that
$A(b^{d^m})B(b^{d^m})\neq 0$ for all $m\in\ZZ_{\ge 0}$ and $f(b)$ is
irrational. Then the irrationality exponent of $f(b)$ is a rational number.
\end{theorem}

In other words, Theorem~\ref{th2} shows that Mahler numbers $f(b)$ for
solutions of~\eqref{def_feq} do not give any extra contribution to the
spectrum $\LLL_M$ on top of the numbers constructed by Bugeaud.

The key ingredient in the proof of Theorem~\ref{th2} is that $\mu(f(b))$ can
be computed from the information on the continued fraction of the Laurent
series $f(z)$. This phenomenon was observed by Guo, Wu and
Wen~\cite{gww_2014} and then developed by Bugeaud, Han, Wen and
Yao~\cite{bhwy_2016}. They computed the upper bound of the irrationality
exponent of $f(b)$ depending on the distribution of non-zero Hankel
determinants. In this paper we make their result much stronger by computing
the precise value of $\mu(f(b))$.

Recall that a Laurent series $f(z)\in \QQ((z^{-1}))$ admits the continued
fraction expansion
$$
f(z) = [a_0(z), a_1(z), \ldots, a_k(z),\ldots],
$$
where $a_i\in \QQ[z]$. It is finite if and only if $f(z)$ is a rational
function. As in the case of real numbers, we call the rational function
$[a_0(z), a_1(z), \ldots, a_n(z)] = \frac{p_k(z)}{q_k(z)}$ {\it $n$th
convergent of $f$}. Assuming that $p_k$ and $q_k$ are coprime, denote by
$d_k$ the degree of the denominator $q_k$.

\begin{theorem}\label{th1}
Let $f(z)\in \QQ((z^{-1}))$ be a Laurent series which solves~\eqref{def_feq}
and is not a rational function. Let $b\in \ZZ$ with $|b|\ge 2$ be inside the
disk of convergence of $f$ such that $A(b^{d^m})B(b^{d^m}) \neq 0$ for any
$m\in\ZZ_{\ge 0}$. Then the irrationality exponent of $f(b)$ equals
\begin{equation}\label{th1_eq}
\mu(f(b)) = 1 + \limsup_{k\to\infty}\frac{d_{k+1}}{d_k}.
\end{equation}
\end{theorem}

Unfortunately, Theorem~\ref{th1} does not always allow to compute $\mu(f(b))$
based only on the knowledge of polynomials $A$ and $B$ because the
formula~\eqref{th1_eq} requires knowledge of the whole continued fraction of
$f$ which is usually a difficult task. However in many cases, as soon as we
know that $\mu(f(b))>2$ we can compute the precise value of the irrationality
exponent of $f(b)$ after computing only finitely many convergents of $f$. We
demonstrate the method by computing the irrationality exponents of all Mahler
numbers from~\cite{badziahin_2017} for which we know that $\mu(f(b))>2$.

\begin{theorem}\label{th3}
Let $q_{\va} = g_{a_1,a_2}(z)\in \ZZ((z^{-1}))$ solve the equation
\begin{equation}\label{th3_eq}
g_\va (z) = (z^2 +a_1z + a_2) g_\va(z^3);\quad a_1,a_2\in\ZZ.
\end{equation}
Then for any integer $b$, $|b|\ge 2$ we have
\begin{itemize}
\item[(a)] for any $s\in \ZZ$ if $f_{s,s^2}(b)$ is irrational then
    $\mu(f_{s,s^2}(b))=3$;
\item[(b)] for any $s\in \ZZ$ if $f_{s^3,-s^2(s^2+1)}(b)$ is irrational
    then $\mu(f_{s^3,-s^2(s^2+1)}(b))=3$;
\item[(a)] if $f_{\pm2,1}(b)$ is irrational then
    $\mu(f_{\pm2,1}(b))=\frac{12}{5}$.
\end{itemize}

\end{theorem}

\section{Useful estimate of irrationality exponent}

The following proposition is a modification of Lemma~4.1
from~\cite{adamczewski_rivoal_2009} which we will need in our proofs. But it
may be of independent interest.

\begin{proposition}\label{prop1}
Let $\alpha\in\RR$. Assume that there exist two sequences
$(\frac{p_n}{q_n})_{n\in \NN}\in\QQ$ and $(\frac{p'_n}{q'_n})_{n\in
\NN}\in\QQ$ of rational approximations to $\alpha$ and three sequences
$\theta_n$, $\delta_n$ and $\tau_n$ of real numbers with $\theta_n\ge 1,
\delta_n> 0$, $\tau_n>0$ such that
\begin{itemize}
\item{(a)} $q'_n\ll q_n^{\theta_n}$;
\item{(b)} $\displaystyle \left|\alpha-\frac{p_n}{q_n}\right| \asymp
    q_n^{-1-\delta_n}$;\quad $\displaystyle
    \left|\alpha-\frac{p'_n}{q'_n}\right| \asymp (q'_n)^{-1-\tau_n}$;
\item{(c)} $(q'_n)^{\tau_n}\gg q_{n+1}^{\delta_{n+1}}$, \quad and\quad
    $q_n^{\delta_n}\to\infty$ as $n\to\infty$.

\end{itemize}
for all $n\in\NN$. Then we have that
\begin{equation}\label{prop1_eq1}
\mu(\alpha) \le \limsup_{n\to\infty} \max\left
\{1+\frac{\theta_n}{\delta_n}, \frac{(1+\tau_n)\theta_n}{\delta_n}\right\}.
\end{equation}
\end{proposition}

The immediate corollary of this proposition is that if the sequences
$\theta_n$ and $\delta_n$ satisfy $\theta_n/\delta_n \to 1$ as $n\to\infty$
and $\tau_n\ge 1$ then the sequence of approximations $p'_n/q'_n$ to $\alpha$
is nearly optimal, i.e. $$\mu(\alpha) = \limsup_{n\to \infty} (1+\tau_n).$$

\begin{proof}
Denote by $c$ the implied constant from Condition~(b), i.e. the constant
which satisfies the inequality
\begin{equation}\label{prop1_eq2}
\left|\alpha-\frac{p'_n}{q'_n}\right| \le c(q'_n)^{-1-\tau_n}
\end{equation}
for all $n\in\NN$. Let $p/q$ be a rational number where the denominator $q$
is large enough. We choose the minimal integer $n$ such that $2cq\le
(q'_n)^{\tau_n}$. Condition~(c) guarantees that such $n$ exists. Then, by the
choice of $n$ and Condition~(c), we have that $q\gg q_n^{\delta_n}$. By the
triangle inequality we have
$$
\left|\alpha-\frac{p}{q}\right| \ge \left|\frac{p}{q}-\frac{p'_n}{q'_n}\right| - \left|\alpha-\frac{p'_n}{q'_n}\right|.
$$
Now we have two possibilities:

\noindent{\bf (1)} The case $p/q\neq p'_n/q'_n$. Then $|p/q - p'_n/q'_n| \ge
(qq'_n)^{-1}$ and from~\eqref{prop1_eq2} we get that $|\alpha - p/q|\ge
(2qq'_n)^{-1}$. We then apply Condition~(a) to get
$$
\left|\alpha - \frac{p}{q}\right| \gg \frac{1}{q q_n^{\theta_n}} \gg \frac{1}{q^{1+\frac{\theta_n}{\delta_n}}}.
$$

\noindent{\bf (2)} The case $p/q= p'_n/q'_n$. Then we have
$$
\left|\alpha - \frac{p}{q}\right| = \left|\alpha - \frac{p'_n}{q'_n}\right|\gg (q'_n)^{-1-\tau_n}\gg q^{-(1+\tau_n)\frac{\theta_n}{\delta_n}}.
$$

To conclude the proof of the proposition, consider some number $\mu$ strictly
bigger than the right hand side in~\eqref{prop1_eq1}. Then there exists
$n_0\in \NN$ such that $\mu> 1+\theta_n/\delta_n$ and $\mu >
(1+\tau_n)\theta_n/\delta_n$ for all $n\ge n_0$. Choose $n_1\ge n_0$ such
that for $n\le n_0$ we have $(q'_n)^{\tau_n} < (q'_{n_1})^{\tau_{n_1}}$. Then
for any $p/q$ with $2cq>(q'_{n_1})^{\tau_{n_1}}$ we have that
$$
\left|\alpha - \frac{p}{q}\right| \gg q^{-\mu}
$$
and hence $\mu(\alpha)\le \mu$.
\end{proof}

\section{Irrationality exponent of $f$}

For convenience, denote the leading coefficients of $A$ and $B$ from
equation~\eqref{def_feq} by $\alpha$ and $\beta$, and denote the degrees of
$A$ and $B$ by $r_a$ and $r_b$ respectively.

Consider the sequence $(p_k(z)/q_k(z))_{k\in \ZZ_{\ge 0}}$ of the convergents
of $f$. Denote the degrees of $q_k$ by $d_k$. Then, by the standard property
of convergents, we have
\begin{equation}\label{eq_qfp}
q_k(z) f(z) - p_k(z) = \sum_{i=d_{k+1}}^\infty c_{k,i}z^{-i},
\end{equation}
where $c_{k,j}$ are some real coefficients, and $c_{k,d_{k+1}}$ is always
nonzero.

{\textsc{Proof of Theorem~\ref{th1}}.} By substituting $z^d$ instead of $z$
in equation~\eqref{eq_qfp} and then using the functional
relation~\eqref{def_feq} for $f(z^d)$ we get that:
\begin{equation}\label{eq_pqk1}
B(z)q_k(z^d) f(z) - A(z)p_k(z^d) = A(z) \sum_{i=d_{k+1}}^\infty c_{k,i}z^{-di}.
\end{equation}
By repeating this procedure $m$ times we get the following equation:
\begin{equation}\label{eq_pqkm}
q_{k,m}(z) f(z) - p_{k,m}(z) = U(z) \sum_{i=d_{k+1}}^\infty c_{k,i}z^{-d^mi},
\end{equation}
where
\begin{equation}\label{eq_defpqkm}
q_{k,m}(z) = \prod_{t=0}^{m-1} B(z^{d^t}) q_k(z^{d^m}),\quad p_{k,m}(z) =\prod_{t=0}^{m-1} A(z^{d^t}) p_k(z^{d^m}),
\quad U(z) = \prod_{t=0}^{m-1} A(z^{d^t}).
\end{equation}

\begin{lemma}\label{lem4}
Let $b\in \RR$ with $|b|>1$ be inside the disc of convergence of $f$. Assume
that for all $t\in \ZZ_{\ge 0}$, $A(b^{d^t}) B(b^{d^t})\neq 0$. Then, for $m$
large enough, one has:
\begin{equation}\label{lem4_eq}
|q_{k,m}(b)| \asymp \beta^m |b|^{d^m\left(\frac{r_b}{d-1} + d_k\right)}, \quad\mbox{and}\quad
|q_{k,m}(b) f(b) - p_{k,m}(b)| \asymp \alpha^m |b|^{d^m\left(\frac{r_a}{d-1} - d_{k+1}\right)}.
\end{equation}
Here, the constants inside the ``$\asymp$'' signs may depend on $A$, $B$, and
$k$, but do not depend on $m$.
\end{lemma}

\begin{proof}
Since $b$ is inside the disc of convergence of $f$, it is also inside the
disc of convergence of
$$
z^{d_{k+1}} (q_k(z) f(z) - p_k(z)) = \sum_{i=0}^\infty c_{k,i+d_{k+1}}
z^{-i}.
$$
By letting $z$ to infinity we see that the right hand side tends to
$c_{k,d_{k+1}}\asymp 1$. This leads us to the following expression, as $m$ is
large enough,
\begin{equation}\label{eq10}
\left|\sum_{i=d_{k+1}}^\infty c_{k,i}b^{-d^m i}\right| \asymp |b|^{-d^m d_{k+1}}.
\end{equation}

Next, notice that
$$
\prod_{t=0}^{\infty} \frac{A(z^{d^t})}{\alpha z^{d^tr_a}} = \prod_{t=0}^{\infty} P_A(z^{-d^t}),
$$
where $P_A(z)$ is a polynomial with $P(0) = 1$. One can check that the disc
of convergence for this infinite product is $|z|>1$. Moreover, since
$A(b^{d^t})\neq 0$ for all $t\in \ZZ$, we have that the product
$$
\prod_{t=0}^{m-1} \frac{A(b^{d^t})}{\alpha b^{d^tr_a}}
$$
converges to a nonzero element as $m\to \infty$. This means that,
$$
\left|\prod_{t=0}^{m-1} \frac{A(b^{d^t})}{\alpha b^{d^tr_a}}\right| \asymp 1
$$
and
\begin{equation}\label{eq11}
\left|\prod_{t=0}^{m-1} A(b^{d^t})\right| \asymp |\alpha|^m |b|^{(1+d+\ldots +d^{m-1})r_a} \asymp |\alpha|^m |b|^{\frac{d^m}{d-1}r_a}.
\end{equation}
By analogous argumenat we get the same estimate for the product over
$B(b^{d^t})$.

The last ingredient of the proof is that for $m$ large enough,
$|q_k(b^{d^m})| \asymp |b|^{d^m d_k}$. Now,
\eqref{eq_pqkm},~\eqref{eq_defpqkm},~\eqref{eq10} and~\eqref{eq11} give us:
$$
|q_{k,m}(b)| = \left|\prod_{t=0}^{m-1} B(b^{d^t}) q_k(b^{d^m})\right| \asymp |\beta|^m |b|^{d^m\left(\frac{r_b}{d-1} + d_k\right)}
$$
and
$$
|q_{k,m}(b) f(b) - p_{k,m}(b)| = \left|\prod_{t=0}^{m-1} A(b^{d^t}) \sum_{i=d_{k+1}}^\infty c_{k,i}b^{-d^mi}\right|\asymp |\alpha|^m |b|^{d^m\left(\frac{r_a}{d-1} - d_{k+1}\right)}.
$$
\end{proof}

As an immediate corollary of~\eqref{lem4_eq} we have that
\begin{equation}\label{eq_qkm_o}
|q_{k,m}(b)| = b^{d^m\left(d_k + \frac{r_b}{d-1} + o(1)\right)}
\end{equation}
and
\begin{equation}\label{eq_approx_o}
|q_{k,m}(b) f(b) - p_{k,m}(b)| = b^{-d^m\left(d_{k+1} - \frac{r_a}{d-1}
+o(1)\right)}.
\end{equation}
Since the sequence $d_k$ tends to infinity with $k$, for any $\epsilon>0$ one
can choose $k=k(\epsilon)$ such that
$$
\epsilon d_k > \max\left\{\frac{r_a}{d-1}+1, \frac{r_b}{d-1}+1\right\}.
$$
For that $k$ we can choose $m$ big enough ($m>m_0(k)$) so that the absolute
values of $o(1)$ in~\eqref{eq_qkm_o} and~\eqref{eq_approx_o} are smaller than
1/2. Then we have
\begin{equation}\label{eq_approx_eps}
q_{k,m}(b)^{-\frac{d_{k+1} (1+\epsilon)}{d_k (1-\epsilon)}} < |q_{k,m}(b) f(b) - p_{k,m}(b)| < q_{k,m}(b)^{-\frac{d_{k+1} (1-\epsilon)}{d_k (1+\epsilon)}}.
\end{equation}
Since, by letting $k\to\infty$, we can make $\epsilon$ as small as possible,
we immediately have $\mu(f(b)) \ge 1+ \limsup \frac{d_{k+1}}{d_k}$. For
convenience, let us denote that ratio $d_{k+1}/d_k$ by $\delta_k$ and define
$$
\rho:=\limsup \frac{d_{k+1}}{d_k}.
$$

\subsection{Upper bound for $\mu(f(b))$}

For a given $k_0\in\NN$ define $K = K(k_0)\in\NN$ as the minimal possible
value such that
\begin{equation}\label{ineq_bigk}
d_{K+1}> d\cdot d_{k_0+1}-r_a+d+1.
\end{equation}
Consider any $k$ in the range $k_0\le k<K$ and consider an arbitrary $m>
M=M(k_0):=\max\{m_0(k_0), m_0(k_0+1), \ldots, m_0(K)\}$, so that the
equation~\eqref{eq_approx_eps} is satisfied for all values $k$ between
$k_0$ and $K$. Equation~\eqref{eq_approx_eps} yields to
\begin{equation}\label{eq_epskm}
\left|f(b) -\frac{p_{k,m}(b)}{q_{k,m}(b)}\right| \asymp q_{k,m}^{ -1 - \left(\frac{d_{k+1}}{d_k} +\epsilon_{k,m}\right)},
\end{equation}
where $\sup_{k_0\le k<K,\; m\ge M} |\epsilon_{k,m}|$ tends to zero as $k_0$
tends to infinity.

Now we construct sequences $P_n/Q_n$ and $P'_n/Q'_n$ for
Proposition~\ref{prop1} in the following way:
$$
\frac{P_1}{Q_1} := \frac{p_{k_0,M}(b)}{q_{k_0,M}(b)},\; \frac{P_2}{Q_2} := \frac{p_{k_0+1,M}(b)}{q_{k_0+1,M}(b)},\ldots,\; \frac{P_{K-k_0}}{Q_{K-k_0}} := \frac{p_{K-1,M}(b)}{q_{K-1,M}(b)};
$$
$$
\frac{P'_1}{Q'_1} := \frac{p_{k_0+1,M}(b)}{q_{k_0+1,M}(b)},\; \frac{P'_2}{Q'_2} := \frac{p_{k_0+2,M}(b)}{q_{k_0+2,M}(b)},\ldots,\; \frac{P'_{K-k_0}}{Q'_{K-k_0}} := \frac{p_{K,M}(b)}{q_{K,M}(b)}.
$$
Then we continue defining the sequences by increasing the index $M$. That is,
for any $u\in\ZZ_{\ge0}$ and any $v\in \{1,\ldots, K-k_0\}$ we define
$$
\frac{P_{u(K-k_0)+v}}{Q_{u(K-k_0)+v}} := \frac{p_{k_0+v-1,M+u}(b)}{q_{k_0+v-1,M+u}(b)};\quad  \frac{P'_{u(K-k_0)+v}}{Q'_{u(K-k_0)+v}} := \frac{p_{k_0+v,M+u}(b)}{q_{k_0+v,M+u}(b)}\ .
$$
From~\eqref{eq_epskm} one can see that the following sequences
$(\delta_n)_{n\in\NN}$ and $(\tau_n)_{n\in\NN}$ satisfy Condition~(b) of
Proposition~\ref{prop1}:
$$
\delta_{u(K-k_0)+v}:= \frac{d_{k_0+v}}{d_{k_0+v-1}} +\epsilon_{k_0+v-1, M+u};\quad \tau_{u(K-k_0)+v}:= \frac{d_{k_0+v+1}}{d_{k_0+v}} +\epsilon_{k_0+v, M+u}.
$$

Let us define a sequence $(\theta_n)_{n\in\NN}$ so that Condition~(a) is
satisfied. By~\eqref{eq_qkm_o} we have that for any $k\in\{k_0,\ldots, K\}$
and for any $m>M$,
$$
|q_{k+1,m} (b)| = |q_{k,m}(b)|^{\frac{d_{k+1}+r_b/(d-1)+o(1)}{d_k+r_b/(d-1)+o(1)}} = |q_{k,m}(b)| ^{\frac{d_{k+1}}{d_k}+\epsilon^*_{k,m}},
$$
where, as for $\epsilon_{k,m}$, $\sup_{k_0\le k<K,\; m\ge M}
|\epsilon^*_{k,m}|\to 0$ as $k_0$ tends to infinity. The last equation
suggests the following formula for $\theta_n$:
$$
\theta_{u(K-k_0)+v} := \frac{d_{k_0+v}}{d_{k_0+v-1}} +\epsilon^*_{k_0+v-1, M+u}.
$$

It remains to verify Condition~(c). The limit $Q_n^{\delta_n}\to\infty$ is
obvious. Because of Condition~(b), the equation $(Q'_n)^{\tau_n} \gg
Q_{n+1}^{\delta_{n+1}}$ is equivalent to:
\begin{equation}\label{cond_qqdash}
|Q'_n f(b) - P'_n| \ll |Q_{n+1} f(b) - P_{n+1}|.
\end{equation}

By definition, we have that for any $u\in \ZZ_{\ge 0}$ and $v\in \{1,\ldots
K-k_0-1\}$, $Q'_{u(K-k_0)+v} = Q_{u(K-k_0)+v+1}$ and $P'_{u(K-k_0)+v} =
P_{u(K-k_0)+v+1}$ and both sides of~\eqref{cond_qqdash} coincide for
$n=u(K-k_0)+v$. Therefore it only remains to verify~\eqref{cond_qqdash} for
$n=(u+1)(K-k_0)$. From the estimate~\eqref{eq_approx_o} and equations
$Q'_{(u+1)(K-k_0)} = q_{K,M+u}(b)$, $Q_{(u+1)(K-k_0)+1} = q_{k_0, M+u+1}(b)$
we have
$$
\begin{aligned}
|q_{K,M+u}(b)f(b) - p_{K,M+u}(b)| &=
b^{-d^{m+u}\left(d_{K+1}-\frac{r_a}{d-1}+o(1)\right)} \\
\stackrel{\eqref{ineq_bigk}}<b^{-d^{m+u+1}\left(d_{k_0+1}-\frac{r_a}{d-1}+o(1)\right)} &= |q_{k_0,M+u+1}(b)f(b) -
p_{k_0,M+u+1}(b)|.
\end{aligned}
$$

After all conditions of Proposition~\ref{prop1} are checked, we apply it to
get
$$
\mu(f(b)) \le \limsup_{u\to\infty} \max_{k_0\le v<K} \left\{1+ \frac{\theta_{u(K-k_0)+v}}{\delta_{u(K-k_0)+v}}, (1+\tau_{u(K-k_0)+v})\frac{\theta_{u(K-k_0)+v}}{\delta_{u(K-k_0)+v}}\right\}.
$$
Notice that by construction, $\theta_n/\delta_n$ tends to one as $k_0$ tends
to infinity. Also, as $k_0$ tends to infinity, we have that
$$
\tau_{u(K-k_0)+v} \to \frac{d_{k_0+v+1}}{d_{k_0+v}}.
$$
for all $u\ge 0$ and $v$ between $k_0$ and $K$. This leads to the upper bound
$$
\mu(f(b))\le \limsup_{n\to\infty} \left\{1 + \frac{d_{n+1}}{d_n}\right\},
$$
which now coincides with the lower bound for $\mu(f(b))$. That proves
Theorem~\ref{th1}. \endproof

\section{Gaps in the set of values $d_k$}

Theorem~\ref{th1} suggests that in order to compute the irrationality
exponent of a Mahler number $f(b)$, we need to consider large gaps in the
sequence $(d_k)_{k\in \NN}$ of degrees of the denominators of the convergents
of $f(z)$.

Define by $\Phi$ the set of all values $d_k$:
$$
\Phi = \Phi(f) := \{d_k\;:\; k\in \NN\}.
$$
We say that $[u,v]$ is {\it a gap in $\Phi$ of size $r>0$} if $u$ and $v$ are
elements of $\Phi$, $r = v-u$ and no elements $w$ with $u<w<v$ are in $\Phi$.
For the gap $[u,v]$ in $\Phi$ we say that $p_u(z)/q_u(z)$ is {\it gap's
convergent} if $p_u(z)/q_u(z)$ is a convergent of $f$ and $\deg(q_u) = u$.

In further discussion we always assume that the value $b\in \NN$ satisfies
the conditions of Theorem~\ref{th1}. It implies that if all gaps in $\Phi$
are of size at most $\frac{r_a+r_b}{d-1}$ then $\mu(f(b))=2$. Indeed, we have
$$
\mu(f(b)) = 1+ \limsup_{\mbox{\scriptsize gaps }[u,v]\mbox{\scriptsize \;of }\Phi\;} \frac{v}{u}\le \lim_{u\to\infty}1+\frac{u + \frac{r_a+r_b}{d-1}}{u} = 2.
$$
Therefore in order to compute the irrationality exponent of $f(b)$ it is
sufficient to consider gaps in $\Phi$ of a bigger size than
$\frac{r_a+r_b}{d-1}$. We call such gaps big. We introduce a partial order on
the set of big gaps. We say that $[u,v]\prec [u',v']$ if there exists
$m\in\NN$ such that
$$
\frac{p_{u'}(z)}{q_{u'}(z)} = \prod_{t=0}^{m-1} \frac{A(z^{d^t})}{B(z^{d^t})} \cdot \frac{p_u(z^{d^m})}{q_u(z^{d^m})}.
$$
This definition is justified by the following lemma.
\begin{lemma}
Let $[u,v]$ be a big gap in $\Phi$. Then the fraction
$$
\frac{A(z)p_u(z^d)}{B(z)q_u(z^d)}
$$
is a convergent of $f$. Moreover, the gap in $\Phi$, which corresponds to
this convergent, has size bigger than $v-u$.
\end{lemma}
\begin{proof}
Denote by $C(z)$ the polynomial $\gcd(A(z)p_u(z^d), B(z)q_u(z^d))$ and let
$r_c:= \deg(C)$. From~\eqref{eq_pqk1} we have that
\begin{equation}\label{eq_approx_pqu}
\left|\left|\frac{B(z) q_u(z^d)}{C(z)} f(z) - \frac{A(z) p_u(z^d)}{C(z)}\right|\right| = r_a - r_c - dv.
\end{equation}
Here, $||g||$ denotes the biggest degree of $z$ with non-zero coefficient in
Laurent series $g$. We have that $\frac{B(z) q_u(z^d)}{C(z)}$ and $\frac{A(z)
p_u(z^d)}{C(z)}$ are coprime and moreover,
\begin{equation}\label{eq_qnp1}
\deg\left( \frac{B(z) q_u(z^d)}{C(z)} \right) = r_b + du-r_c < dv + r_c -r_a.
\end{equation}
The last inequality is true because for big gaps we have $v-u>
\frac{r_a+r_b}{d-1}$. Hence
$$
\frac{A(z) p_u(z^d)}{C(z)} \big/ \frac{B(z) q_u(z^d)}{C(z)}
$$
is a convergent of $f$ and the size of its corresponding gap is
$$
(dv+r_c-r_a) - (r_b+du-r_c) = 2r_c + d(v-u) - r_a - r_b > v-u.
$$
\end{proof}

We say that a big gap $[u,v]$ in $\Phi$ is {\it primitive} if there are no
other big gaps $[u',v']$ in $\Phi$ such that $[u',v']\prec [u,v]$. A
primitive gap $[u,v]$ generates the ordered sequence of big gaps
$$
[u,v] = [u_0,v_0] \prec [u_1,v_1]\prec [u_2,v_2]\prec\cdots
$$
such that
\begin{equation}\label{eq21}
\frac{p_{u_{n+1}}(z)}{q_{u_{n+1}}(z)} = \frac{A(z) p_{u_n}(z^d)}{C(z)} \big/ \frac{B(z) q_{u_n}(z^d)}{C(z)}.
\end{equation}
Then the formula~\eqref{th1_eq} for $\mu(f(b))$ from Theorem~\ref{th1} can be
rewritten as follows:
\begin{equation}\label{eq_mufb_prim}
\mu(f(b)) = 1+\sup_{[u_0,v_0]\mbox{\scriptsize\ is primitive}} \left\{ \limsup_{i\to\infty}\frac{v_{n_i}}{u_{n_i}}\right\} \cup\{1\}.
\end{equation}

\begin{lemma}\label{lem6}
The size of a primitive gap in $\Phi$ does not exceed
$\frac{2d-1}{d-1}(r_a+r_b)$.
\end{lemma}

\begin{proof}
Suppose the contrary: the size of a primitive gap $[u,v]$ in $\Phi$ is bigger
than $\frac{2d-1}{d-1}(r_a+r_b)$. Let $w$ be the biggest integer such that
$dw<v-r_b$ (i.e. $w = \lfloor\frac{v-r_b-1}{d}\rfloor$).

Assume that $w$ lies inside a big gap $[s,t]$ in $\Phi$, that is, $s\le w<t$.
Then, by~\eqref{eq_approx_pqu} and~\eqref{eq_qnp1} the gap, associated with
the convergent
$$
\frac{A(z)p_s(z^d)}{B(z)q_s(z^d)},
$$
contains $[ds+r_b, dt-r_a]$. Obviously, $ds+r_b<v$ and $dt-r_a\ge v-r_b-r_a
>u$. Therefore this gap intersects with $[u,v]$ and hence it must coincide with $[u,v]$.
We get $[s,t]\prec[u,v]$, which is a contradiction.

We then deduct that $w$ does not lie inside a big gap. In other words, there
is an element $s\in\Phi$ with $0\le w-s\le \frac{r_a+r_b}{d-1}$. Consider the
fraction
$$
\frac{p(z)}{q(z)} = \frac{A(z)p_s(z^d)}{B(z)q_s(z^d)}.
$$
Then by~\eqref{eq_pqk1}, we have $\|q(z) f(z) - p(z)\| \le r_a - d(s+1)$,
which is strictly smaller than $-u$. Indeed,
$$
d(s+1)-r_a\ge d\left( w- \frac{r_a+r_b}{d-1} +1\right) -r_a > v-r_a-r_b -\frac{d}{d-1}(r_a+r_b)\ge u.
$$

Divide $q$ by $q_u$ with the remainder: $q(z) = a(z) q_u(z) + r(z)$ and write
$p(z) = a(z) p_u(z) + c(z)$. Then we have
$$
||a(z) q_u(z) f(z) - a(z) p_u(z) || = \deg(a) -v.
$$
Obviously, the degree of $q$ is $r_b+ds$ which is strictly smaller than $v$
and therefore $\deg(a) - v < v-u - v = -u$.

Assume that $r\neq 0$. Since the convergents of $f$ are the best approximants
to $f$ and $\deg(r)<\deg(q_u)$, we have
$$
||r(z)f(z) - c(z)|| \ge ||q_{u'} (z) f(z) - p_{u'}(z)|| = -u,
$$
where $p_{u'}/q_{u'}$ is the convergent of $f$ which precedes $p_u/q_u$. The
last two estimates imply
$$
||q(z) f(z) - p(z) || = ||r(z)f(z) - c(z)|| \ge -u,
$$
which contradicts the condition $r\neq 0$. Hence we get that $r = 0$ and
$p/q$ coincides with $p_u/q_u$. This together with~\eqref{eq_approx_pqu}
and~\eqref{eq_qnp1} implies that $u = ds+r_b-r_c$ and $v = dt+r_c-r_a$ where
$r_c = \deg(\gcd(A(z)p_u(z^d), B(z)q_u(z^d)))$. Since polynomials $p_u(z^d)$
and $q_u(z^d)$ are coprime, $r_c\le r_a+r_b$. Finally,
$$
v-u \le d(t-s)+2r_c - r_a-r_b \le \frac{2d-1}{d-1} (r_a+r_b).
$$

\end{proof}

\begin{lemma}\label{lem7}
Assume that $(d-1)u>r_a$. Then
\begin{equation}\label{lem7_ineq}
\frac{v - \frac{r_a}{d-1}}{u + \frac{r_b}{d-1}}\le \limsup_{n\to\infty} \left\{\frac{v_n}{u_n}\right\} \le \frac{v + \frac{r_b}{d-1}}{u - \frac{r_a}{d-1}}.
\end{equation}
\end{lemma}

\begin{proof}
From equations~\eqref{eq_approx_pqu} and~\eqref{eq_qnp1} we have that
\begin{equation}\label{form_un}
\begin{array}{l}
u_{n+1} = du_n+r_b - r_{c,n};\\
v_{n+1} = dv_n-r_a+r_{c,n},
\end{array}
\end{equation}
where
\begin{equation}\label{def_rcn}
r_{c,n} = \deg\gcd(A(z) p_{u_n}(z^d), B(z) q_{u_n}(z^d))
\end{equation}
and it is not bigger than $r_a+r_b$. This implies
$$
\frac{dv_n-r_a}{du_n+r_b}\le\frac{v_{n+1}}{u_{n+1}}\le \frac{dv_n+r_b}{du_n-r_a}.
$$
By iterating this inequality $n$ times we get
$$
\frac{d^nv-(1+d+\ldots +d^{n-1})r_a}{d^nu+(1+d+\ldots +d^{n-1})r_b} \le \frac{v_n}{u_n}\le \frac{d^nv+(1+d+\ldots +d^{n-1})r_b}{d^nu-(1+d+\ldots +d^{n-1})r_a}.
$$
Taking limits as $n\to\infty$ yields~\eqref{lem7_ineq}.
\end{proof}

Lemmata~\ref{lem6} and~\ref{lem7} together imply that only finitely many
primitive gaps may contribute to the supremum in~\eqref{eq_mufb_prim}.
Indeed, consider all primitive gaps $[u,v]$ in $\Phi$ with
$u>\frac{r_a}{d-1}$. By Lemma~\ref{lem6}, their sizes are bounded. Therefore
we can choose the primitive gap $[u_0,v_0]$ in $\Phi$ with the biggest
possible size $S$ such that $u_0$ is smallest possible among all primitive
gaps in $\Phi$ of this size. Then, by Lemma~\ref{lem7}, a primitive gap
$[u,v]$ in $\Phi$ can only contribute to the limsup in~\eqref{eq_mufb_prim}
if
$$
\frac{u+S+\frac{r_b}{d-1}}{u-\frac{r_a}{d-1}} > \frac{v_0-\frac{r_a}{d-1}}{u_0+\frac{r_b}{d-1}}.
$$
Since $v_0-u_0>\frac{r_a+r_b}{d-1}$, the right hand side of the inequality is
bigger than one and therefore it gives us an upper bound for $u$. Denote this
bound by $l_u$. We deduct that only $[u,v]$ with $u\le l_u$ can contribute to
the limsup in~\eqref{eq_mufb_prim} and there are obviously finitely many of
them.

Now to complete the proof of Theorem~\ref{th2}, we need to show that for any
primitive gap $[u,v]$ in $\Phi$ we have that $\liminf_{n\to\infty} v_n/u_n$
is a rational number. The most misterious term in the
formulae~\eqref{form_un} is $r_{c,n}$. In the next section we prove the
following proposition which is a key to the proof of Theorem~\ref{th2}.

\begin{proposition}\label{prop2}
The sequence $(r_{c,n})_{n\in\NN}$ is eventually periodic.
\end{proposition}

We end this section by showing how Proposition~\ref{prop2} implies
Theorem~\ref{th2}. Let the sequence $(r_{c,n})_{n\in\NN}$ be periodic,
starting from the index $n_0$ and with the period length $P$, i.e.
$r_{c,n_0+i} = r_{n_0+P+i}$ for every $i\in\ZZ_{\ge 0}$. Denote by $R$ the
following value:
$$
R:= d^{P-1}r_{c,n_0}+\ldots + dr_{c,n_0+P-2}+r_{c,n_0+P-1}.
$$

By applying the formulae~\eqref{form_un} for $u_{n_0}, v_{n_0}, u_{n_0+1},
v_{n_0+1},$... up to $u_{n_0+P}, v_{n_0+P}$, we get
$$
u_{n_0+P} = d^Pu_{n_0} + r_b(1+d+\cdots+d^{P-1})-R,\;\; v_{n_0+P} = d^Pv_{n_0} -r_a(1+d+\cdots+d^{P-1})+R.
$$
Define
$$
r_u:= r_b(1+d+\cdots+d^{P-1})-R,\quad\mbox{and}\quad r_v:=r_a(1+d+\cdots+d^{P-1})-R.
$$
Then we get
$$
\lim_{k\to\infty} \frac{u_{n_0+kP}}{v_{n_0+kP}} = \lim_{k\to\infty}\frac{d^{kP}u_{n_0} + (1+d^P+d^{2P}+d^{(k-1)P})r_u}{d^{kP}v_{n_0} - (1+d^P+d^{2P}+d^{(k-1)P})r_v} = \frac{u_{n_0} + \frac{r_u}{d^P-1}}{v_{n_0} - \frac{r_v}{d^P-1}},
$$
which is a rational number. By analogous arguments, the limits of
$u_{n_0+1+kP}/v_{n_0+1+kP}, \ldots$, $u_{n_0+(k+1)P-1}/v_{n_0+(k+1)P-1}$ as
$k\to\infty$ are all rational numbers. Therefore $\limsup_{n\to\infty}
v_n/u_n$, as the maximum of the limits above, is a rational number. This
finishes the proof of Theorem~\ref{th2}.

\section{Proof of Proposition~\ref{prop2}}

We split each of the polynomials $A,B,p_{u_m}$ and $q_{u_m}$ ($m\in\ZZ_{\ge
0}$) into the product of three factors: cyclotomic, non-cyclotomic and the
power of $z$. For example, $A(z) = A_c(z)\cdot A_n(z)\cdot A_0(z)$, where all
roots of $A_c(z)$ are roots of unity, $A_0(z)$ is a power of $z$ and none of
the roots of $A_n(z)$ is either zero or a root of unity. The polynomials
$B_c, B_n, B_0, p_{c,u_m}, p_{n,u_m}, p_{0,u_m}, q_{c,u_m}, q_{n,u_m}$ and
$q_{0,u_m}$ are defined in the same way. Obviously,
$$
\gcd(A_c(z)p_{c,u_m}(z^d), B_n(z) q_{n,u_m}(z^d)) = \gcd(A_n(z)p_{n,u_m}(z^d), B_c(z) q_{c,u_m}(z^d)) = \mathrm{const},
$$
and therefore we can split $r_{c,m}$ into the sum of three parts: $r_{c,m} =
r_{c,c,m}+r_{n,c,m}+r_{0,c,m}$. The first term is the degree of the
cyclotomic part of the gcd in~\eqref{def_rcn}, the second one is the degree
of the non-cyclotomic part of it and the third one is generated by the powers
of $z$ presented in the $\gcd$. We will consider each term separately.

\subsection{Non-cyclotomic term}

\begin{lemma}\label{lem8}
Let $C,D\in \ZZ[x]$ be such that none of their roots is a root of unity. Then
there exists $m_0\in\NN$ such that for all $m>m_0$,
$$
\gcd(C(z), D(z^{d^m})) = \mathrm{const}.
$$
\end{lemma}

\begin{proof}
Assume the contrary. Then there exists a root $\alpha$ of $C$ such that
$z-\alpha$ divides $D(z^{d^m})$ for infinitely many values $m$. Hence there
exists a root $\beta$ of $D$ such that
$$
\beta = \alpha^{d^{m_1}} = \alpha^{d^{m_2}}
$$
for some positive integers $m_1\neq m_2$. But the latter is only possible if
$\alpha$ is a root of unity or zero --- a contradiction.
\end{proof}

\begin{lemma}\label{lem99}
The sequence $(r_{n,c,m})_{m\in\NN}$ is eventually periodic.
\end{lemma}

\begin{proof}
From Lemma~\ref{lem8} fix $m_0$ so that
$$
\gcd(A_n(z), B_n(z^{d^m})q_{n,u}(z^{d^m})) = \gcd(B_n(z), A_n(z^{d^m})p_{n,u}(z^{d^m})) = \mathrm{const}
$$
for all $m\ge m_0$. Write the non-cyclotomic part of the convergent
$p_{u_m}/q_{u_m}$ in the following form:
$$
\frac{p_{n,u_m}}{q_{n,u_m}} = \frac{\prod_{t=0}^{m-1} A^*_{t,m}(z) p^*_m(z)}{\prod_{t=0}^{m-1}B^*_{t,m}(z) q^*_m(z)},
$$
where the numerator and denominator of the right hand side are coprime;
$A^*_{t,m}(z) \mid A(z^{d^t})$, $B^*_{t,m}(z)\mid B(z^{d^t})$, $p^*_m(z) \mid
p_n(z^{d^m})$ and $q^*_m(z) \mid q_n(z^{d^m})$; the leading coefficients of
$A_{t,m}^*(z), B^*_{t,m}(z), p_m^*(z), q_m^*(z)$ coincide with those of
$A(z), B(z), p_{n}(z)$ and $q_{n}(z)$ respectively. Then for $m>m_0$ the
degree $r_{n,c,m}$ of
$$
\gcd(A_n(z) p_{n,u_{m+1}}(z^d), B_n(z) q_{n,u_{m+1}}(z^d))
$$
as well as the polynomials $A^*_{t,m+1}, B^*_{t,m+1}$, $t\in\{0,\ldots,
m_0\}$, depend entirely on the polynomials $A^*_{0,m}$, $A^*_{1,m}, \ldots$,
$A^*_{m_0,m}$ and $B^*_{0,m}, \ldots, B^*_{m_0,m}$. But there are finitely
many such combinations. Therefore one can find $m_2>m_1>m_0$ such that
$A^*_{0,m_1} = A^*_{0,m_2}$, \ldots, $A^*_{m_0,m_1} = A^*_{m_0,m_2}$ and
$B^*_{0,m_1} = B^*_{0,m_2}$, \ldots, $B^*_{m_0,m_1} = B^*_{m_0,m_2}$. Then we
get $r_{n,c,m_1} = r_{n,c,m_2}, r_{n,c,m_1+1} = r_{n,c,m_2+1}$, etc. Hence
the sequence of $(r_{c,n,m})_{m\in \NN}$ is eventually periodic.
\end{proof}

\subsection{Powers of $z$}

We write
$$
A_0(z) = z^{s_a};\quad B_0(z)=z^{s_b};\quad p_{0,u}(z) = z^{s_p}\quad\mbox{and}\quad q_{0,u}(z) = z^{s_q}.
$$
Since $A$ and $B$ are coprime and $p_u$ and $q_u$ are coprime, we have that
at least one value of $s_a, s_b$ and at least one of $s_p, s_q$ is zero. If
we have $s_a = s_p=0$ (or $s_b=s_q=0$) then, by~\eqref{eq21}, the powers of
$z$ of all numerators (denominators) are zero and hence
$(r_{0,c,m})_{m\in\ZZ_{ge 0}}$ is the zero sequence.

Now without loss of generality assume that $s_a>0, s_q>0, s_b=s_p=0$. Denote
by $s_{p,m}$ and $s_{q,m}$ the maximal powers of $z$ of $p_{u_m}$ and
$q_{u_m}$ respectively. Notice that, if for some $m_0\in\NN$ the value
$s_{q,m_0}$ is zero then, as before, the sequence $r_{0,c,m}$ becomes zero
for all $m\ge m_0$. On the other hand, if $s_{q,m}$ is positive for all
$m\in\ZZ_{\ge 0}$ then the power of $z$ of $q_{u_m}(z^d)$ is always bigger
than that of $A(z)$, which follows that $r_{0,c,m}$ equals $s_a$ for all
$m\in\ZZ_{\ge 0}$.

In all cases we have that the sequence $(r_{0,c,m})_{m\in\ZZ_{\ge 0}}$ is
eventually periodic.

\subsection{Cyclotomic term}

Note that each of the polynomials $A_c, B_c, p_{c,u}, q_{c,u}$ is a (possibly
empty) product of cyclotomic polynomials $\Phi_n(z)$. We start by
investigating the structure of polynomials $\Phi_n(z^d)$ as $d$ changes. That
requires some notation. Given $n\in \NN$, the radical of $n$ is the product
of all prime divisors of $n$, i.e.:
$$
\rad(n):= \prod_{{p\in \PP}\atop{p\mid n}} p.
$$
For two positive integers $n$ and $m$, by $r(n,m)$ we denote the biggest
divisor of $n$ which is coprime with $m$, and $s(n,m):=n/r(n,m)$.

\begin{lemma}\label{lem9}
Let $n,d$ be two positive integers. The polynomial $\Phi_n(z^d)$ is a product
of cyclotomic polynomials. More precisely,
$$
\Phi_n(z^d) = \prod_{r\mid r(d,n)} \Phi_{rns(d,n)}(z).
$$
\end{lemma}

\begin{proof}
All the roots of $\Phi_n(z)$ are of the form $\xi_n^i$, where $\xi_n$ is
$n$-th primitive root of unity, $0\le i<n$ and $\gcd(i,n)=1$. Therefore the
roots $\xi$ of $\Phi_n(z^d)$ are the solutions of the equation $\xi^d =
\xi_n^i$, which can be written as
$$
\xi_{nd}^i \cdot \xi_d^j = \xi_{nd}^{nj+i},
$$
where $0\le j<d$. The values $nj+i$ run through the set $\NNN$ of all numbers
between zero and $nd$, which are coprime with $n$. Split this set into
subsets
$$
\NNN_t:=\{x\in\NNN\;:\; \gcd(d,x)=t\}.
$$
Obviously, they are non-empty only if $t\mid d$ and $\gcd(t,n)=1$. These two
conditions are equivalent to $t\mid r(d,n)$. Denote by $r$ the fraction
$r(d,n)/t$. Notice that for any $x\in\NNN_t$ one has $\xi_{nd}^x =
\xi_{nd/t}^{x/t}$ where $x/t$ is coprime with $nd/t$. Finally, write $nd/t =
rns(d,n)$, so the numbers $\xi_{nd}^x$ are the roots of the polynomial
$\Phi_{rns(d,n)}(z)$ and $\Phi_{rns(d,n)}(z)\mid \Phi_n(z^d)$.
\end{proof}

Write the polynomial $A_c(z)$ as the product:
$$
A_c(z) = \prod_{{r\in\NN}\atop{\gcd(d,r)=1}} A_{r,c}(z),
$$
where $A_{r,c}(z)$ is the product of all $\Phi_n(z)$ such that $\Phi_n(z)\mid
A_c(z)$ and $r(n,d)=r$. Other polynomials $B_{r,c}(z), p_{r,c,u_m}(z),
q_{r,c,u_m}(z)$ are defined analogously. Clearly, among all values $r$ with
$\gcd(r,d)=1$ only finitely many polynomials $A_{r,c}(z)$ have positive
degree.

One of the outcomes of Lemma~\ref{lem9} is that for any $n$ and $m$ in $\NN$
every cyclotomic divisor $\Phi_k(z)$ of $\Phi_n(z^{d^m})$ has $r(k,d) =
r(n,d)$. Therefore we can split $r_{c,c,m}$ into the sum:
$$
r_{c,c,m} = \sum_{{r\in\NN}\atop{\gcd(d,r)=1}} r_{r,c,c,m},
$$
where
$$
r_{r,c,c,m} = \gcd(A_{r,c}(z)p_{r,c,u_m}(z^d), B_{r,c}(z)q_{r,c,u_m}(z^d)).
$$
Only finitely many of the sequences $(r_{r,c,c,m})_{m\in\NN}$ are non-zero.

It remains to show that every non-zero sequence $(r_{r,c,c,m})_{m\in\NN}$ is
eventually periodic.

{\bf Case 1.} Assume that among the divisors of $A_{r,c}, B_{r,c}, p_{r,c,u},
q_{r,c,u}$ there are no polynomials $\Phi_r(z)$. From Lemma~\ref{lem9} we
know that all divisors $\Phi_k(z)$ of $\Phi_n(z^{d^m})$ satisfy $n
s(d,n)^m\mid k$. Consider a divisor $\Phi_n(z)$ of one of the polynomials
$A_{r,c}, B_{r,c}, p_{r,c,u}, q_{r,c,u}$. Since $n\neq r$, and $r(n,d)=r$, we
have $s(d,n)>1$ and therefore, as $m$ tends to infinity, all divisors
$\Phi_k(z)$ of $\Phi_n(z^{d^m})$ satisfy $k\to\infty$. Therefore there exists
$m_0$ such that for $m>m_0$
$$
\gcd(A_{r,c}(z), \Phi_n(z^{d^m})) = \gcd(B_{r,c}(z), \Phi_n(z^{d^m})) = \mathrm{const}.
$$
Then the proof of Proposition in this case is analogous to that of
Lemma~\ref{lem99}.

Before considering the other cases, we need more notation and lemma. Given
two polynomials $f(z),g(z)\in\ZZ[z]$ with $\deg(f)>0$ denote by $\sigma(f,g)$
the maximal power of $f$ which divides $g$, i.e.
$$
\sigma(f,g):=\max\{n\in\ZZ_{\ge 0}\;:\; (f(z))^n\mid g(z)\}.
$$

\begin{lemma}\label{lem11}
For any $f(z)\in\ZZ[z]$ and any $k\in \NN$ there exists a constant $c =
c(f,k)$ such that for any $m\in\NN$, $\sigma(\Phi_k(z), f(z^{d^m})) <c$.
\end{lemma}

\begin{proof}
We write $k = rs$ where $r = r(k,d)$ is coprime with $d$ and the radical of
$s$ divides the one of $d$. Split $f$ as a product $f = f_r\cdot g$, where
all the roots of $g$ are either not roots of unity or they are roots of unity
of degree $k'$ with $r(k',d)\neq r$. The function $f_r$ is defined as
follows:
$$
f_r(z) = \prod_{\rad(s_i)\,\mid\, \rad(d)} (\Phi_{rs_i}(z))^{\alpha(s_i)}.
$$
Then $g(z^{d^m})$ is always coprime with $\Phi_k(z)$ and $\sigma(\Phi_k(z),
f(z^{d^m})) = \sigma(\Phi_k(z), f_r(z^{d^m}))$.

We finish the proof of the lemma by  induction on $s$. For $s=1$,
Lemma~\ref{lem9} implies that $$\sigma(\Phi_r(z), f_r(z^{d^m})) =
\sigma(\Phi_r(z), (\Phi_r(z^{d^m}))^{\alpha(1)}) = \alpha(1).$$ Now, consider
$S\in \NN$ with $\rad(S)\mid \rad(d)$. Assume that the statement of the lemma
is satisfied for all $s<S$ with $\rad(s)\mid d$, i.e. for any such $s$ there
exists a constant $c(s)$ such that $\sigma(\Phi_{rs}(z), f_r(z^{d^m}))\le
c(s)$. Now we prove the statement for $S$. Lemma~\ref{lem9} implies that
$$
\sigma(\Phi_{rS}(z), f_r(s^{d^m}))\le \sigma(\Phi_{rS}(z), (\Phi_{rS}(z^{d^m}))^{\alpha(S)}) + \!\!\!\!\sum_{s\mid S,\; s<S}\!\!\!\! \sigma(\Phi_{rs}(z),f_r(z^{d^{m-1}})) \le \alpha(S)+\!\!\!\!\sum_{s\mid S,\; s<S}\!\!\! c(s).
$$
Since the right hand side does not depend on $m$, the proof is finished.
\end{proof}

{\bf Case 2.} Assume that $\Phi_r(z)$ divides $p_{r,c,u}(z)$ and
$$\gcd(\Phi_r(z), A_{r,c}(z)) = \gcd(\Phi_r(z), B_{r,c}(z)) =
\mathrm{const}.$$

Note that the case $\Phi_r(z)\mid q_{r,c,u}(z)$ can be dealt analogously: we
just swap $A_{r,c}$ with $B_{r,c}$ and $p_{r,c,u}$ with $q_{r,c,u}$.

Write $A_{r,c}(z)$ and $B_{r,c}(z)$ as
$$
A_{r,c}(z) = \prod_{i=1}^n \Phi_{rs_i}(z),\quad B_{r,c}(z) = \prod_{i=n+1}^{n+n^*} \Phi_{rs_i}(z).
$$
Let $\SSS$ be the set of all positive integers $s$ which divide one of the
values $s_i$, $1\le i\le n+n^*$, i.e.
$$
\SSS:=\{s\in\NN\;:\; \exists i\in\{1,\ldots, n+n^*\},\; s\mid s_i\}.
$$

Recall that $p_{r,c,u_{m+1}}/q_{r,c,u_{m+1}}$ can be written in the form
$$
\frac{p_{r,c,u_{m+1}}(z)}{q_{r,c,u_{m+1}}(z)} = \frac{A_{r,c}(z)p_{r,c,u_m}(z^d)}{B_{r,c}(z)q_{r,c,u_m}(z^d)}.

$$
Then the value $r_{r,c,c,m+1}$ is completely determined by two tuples
$\Sigma_{p,m}$ and $\Sigma_{q,m}$ which are defined as follows:
$$
\Sigma_{p,m}:=(\sigma_{\zeta_1,m}, \ldots, \sigma_{\zeta_N,m}),\quad\mbox{where}\; N=\#\SSS,\; \zeta_1,\ldots, \zeta_n\in\SSS,\;\sigma_{\zeta,m}:=\sigma(\Phi_{r\zeta}(z),p_{r,c,u_m}(z^d))
$$
and $\Sigma_{q,m}$ is defined analogously with $p_{r,c,u_m}$ replaced by
$q_{r,c,u_m}$. By Lemma~\ref{lem9}, we have that $\Sigma_{p,m+1}$ and
$\Sigma_{q,m+1}$ are also determined by $\Sigma_{p,m}$ and $\Sigma_{q,m}$
respectively.

It remains to show that all terms of $\Sigma_{p,m}$ and $\Sigma_{q,m}$ are
bounded by a constant independent of $m$. That in turn will imply that there
are only finitely many different values for $(\Sigma_{p,m}, \Sigma_{q,m})$
and there exist $m_1<m_2$ such that $\Sigma_{p,m_1} = \Sigma_{p,m_2},
\Sigma_{q,m_1} = \Sigma_{q,m_2}$, hence the sequence
$(r_{r,c,c,m})_{m\in\NN}$ is eventually periodic end the proof of
Proposition~\ref{prop2} is completed for this case.

Write the part $p_{r,c,u_m}/q_{r,c,u_m}$ of the convergent $p_{u_m}/q_{u_m}$
in the following form:
$$
\frac{p_{r,c,u_m}(z)}{q_{r,c,u_m}(z)} = \frac{\prod_{t=0}^{m-1} A^*_{t,m}(z) p^*_m(z)}{\prod_{t=0}^{m-1}B^*_{t,m}(z) q^*_m(z)},
$$
where the numerator and the denominator of the right hand side are coprime
and $A^*_{t,m}(z) \mid A_{r,c}(z^{d^t})$, $B^*_{t,m}(z)\mid
B_{r,c}(z^{d^t})$, $p^*_m(z) \mid p_{r,c,u}(z^{d^m})$ and $q^*_m(z) \mid
q_{r,c,u}(z^{d^m})$.

Since none of $A_{r,c}(z)$ and $B_{r,c}(z)$ are divisible by $\Phi_{r}(z)$ we
have that there exists $m_0\in\NN$ such that for all $m>m_0$, the polynomials
$A_{r,c}(z^{d^m})$ and $B_{r,c}(z^{d^m})$ are coprime with both $A_{r,c}(z)$
and $B_{r,c}(z)$. Therefore for each term $\sigma_{\zeta,m}$ of
$\Sigma_{p,m}$ we have
$$
\sigma_{\zeta,m} = \sum_{t=0}^{m_0} \sigma(\Phi_{r\zeta}(z), A^*_{t,m} (z^d)) + \sigma(\Phi_{r\zeta}(z), p^*_m(z^d)).
$$
By Lemma~\ref{lem11}, the right hand side is always bounded by some constant
independent of $m$. By analogous arguments, the same is true for all terms
$\sigma_{\zeta,m}$ of $\Sigma_{q,m}$.

{\bf Case 3.} Assume that $\Phi_r(z)$ divides $A_{r,c}(z)$. Then, since
$A_{r,c}(z)$ and $B_{r,c}(z)$ are coprime, we have that $\Phi_r(z)$ does not
divide $B_{r,c}(z)$.

Note that the case $\Phi_r(z)\mid B_{r,c}(z)$ can be handled analogously. We
just swap $A_{r,c}$ with $B_{r,c}$ and $p_{r,c,u}$ with $q_{r,c,u}$.
Therefore Case~3 is the last one which needs to be investigated.

\begin{lemma}\label{lem12}
For any $n\in\NN$ with $r(n,d) = r$ there exists $m\in\NN$ such that
$\Phi_n(z)\mid \Phi_r(z^{d^m})$.
\end{lemma}

\begin{proof}
We write $n$ as a product $n = rs$ and prove the lemma by induction on $s$.
For $s=1$ the statement is straightforward. Consider $S$ such that
$\rad(S)\mid \rad(d)$. Assume that the statement is true for all $s<S$ with
$\rad(s)\mid \rad(d)$ and prove it for $S$. Write the prime factorisations of
$S$ and $d$ in the following way:
$$
S = p_1^{\beta_1}\cdots p_k^{\beta_k}p_{k+1}^{\beta_{k+1}}\cdots p_{k+l}^{\beta_{k+l}};\quad d = p_1^{\alpha_1}\cdots p_{k+l}^{\alpha_{k+l}},
$$
where $\beta_1<\alpha_1,\ldots, \beta_k<\alpha_k$ and $\beta_{k+1}\ge
\alpha_{k+1}>0,\ldots, \beta_{k+l}\ge\alpha_{k+l}>0$. Then, by
Lemma~\ref{lem9}, one has that $\Phi_S(z)$ divides $\Phi_s(z^d)$ for $s =
p_{k+1}^{\beta_{k+1}-\alpha_{k+1}}\cdots p_{k+l}^{\beta_{k+l}-\alpha_{k+l}}$.
By induction assumption, we have that there exists $m$ such that
$\Phi_s(z)\mid \Phi_r(z^{d^m})$. Therefore, $\Phi_S(z)\mid
\Phi_r(z^{d^{m+1}})$.
\end{proof}

Similarly to Case~2, define the set $\SSS$ and the following tuple:
$$
\Sigma_{q,m}:=(\sigma_{\zeta_1,m}, \ldots, \sigma_{\zeta_N,m}),\quad\mbox{where}\; N=\#\SSS,\;\; \zeta_1,\ldots, \zeta_n\in\SSS\;\mbox{and}
$$
$$
\sigma_{\zeta,m}:=\sigma\left(\Phi_{r\zeta}(z),\prod_{t=0}^{m-1}B_{r,c}(z^{d^t})\cdot
q_{r,c,u}(z^{d^m})\right).
$$
As in Case~2, we have that all terms in $\Sigma_{q,m}$ are bounded by a
constant, which is independent of $m$. On the other hand, by
Lemma~\ref{lem9}, every polynomial $A_{r,c}(z^{d^t})$ is divisible by
$\Phi_r(z)$ and therefore
$$
\sigma\left(\Phi_{r}(z),\prod_{t=0}^{m-1}A_{r,c}(z^{d^t})\right)\ge m.
$$
In view of Lemma~\ref{lem12}, there exists $m_0$ big enough, so that for any
$\zeta\in\SSS$ and $m\ge m_0$ the value
$$
\sigma\left(\Phi_{r\sigma}(z),\prod_{t=0}^{m-1}A_{r,c}(z^{d^t})\cdot
p_{r,c,u}(z^{d^m})\right)
$$
is bigger than every term in $\Sigma_{q,m}$. That implies that for every
$m>m_0$ every polynomial $(\Phi_{r\zeta}(z))^{\sigma_{\zeta,m}}$ cancels out
in the expression
$$
\frac{p_{r,c,u_m}(z)}{q_{r,c,u_m}(z)} = \frac{\prod_{t=0}^{m-1} A_{r,c}(z^{d^t}) p_{r,c,u}(z^{d^m})}{\prod_{t=0}^{m-1}B_{r,c}(z^{d^t}) q_{r,c,u}(z^{d^m})}.
$$
Hence for $m\ge m_0$ the polynomial $q_{r,c,u_m}(z^d)$ is coprime with
$A_{r,c}(z)$, $B_{r,c}(z)$ divides $p_{r,c,u_m}(z^d)$ and therefore the value
$r_{r,c,c,m}$ is equal to $r_b$. Again we have that the sequence
$(r_{r,c,c,m})_{m\in\NN}$ is eventually periodic.

To finish the proof of Proposition~\ref{prop2} we observe that the sequence
$r_{c,m}$ is the sum of finitely many eventually periodic sequences and hence
is eventually periodic itself. \endproof

\section{Application: $d=3$, infinite products of quadratic polynomials}

Consider the set of Mahler functions $g_\va(z) = g_{a_1,a_2} (z)$ which
satisfy the equation
$$
g_\va (z) = (z^2 +a_1z + a_2) q_\va(z^3);\quad a_1,a_2\in\ZZ.
$$
Such functions and their corresponding Mahler numbers were considered
in~\cite{badziahin_2017} and it was conjectured that, given $b\in\ZZ$ with
$|b|\ge 2$, if $g_\vu(b)\not \in\QQ$ then $\mu(g_\va(b))=2$ for all
$\va\in\ZZ^2$, except the following three families:
\begin{itemize}
\item[(a)] $\va = (s,s^2)$, $s\in\ZZ$;
\item[(b)] $\va = (s^3, -s^2(s^2+1))$, $s\in\ZZ$;
\item[(c)] $\va = (\pm2,1)$.
\end{itemize}

In~\cite[Theorem 9]{badziahin_2017} the lower bounds for the irrationality
exponents of $g_\va(b)$ for those families is provided. Here we demonstrate
how Theorem~\ref{th1} together with Lemmata~\ref{lem6} and~\ref{lem7} can be
used to show that lower bounds in~\cite{badziahin_2017} are sharp.

\medskip
\noindent{\bf Family (a).} Let $\va = (s,s^2)$. Simple calculations reveal
that the first convergent of $g_\va(z)$ is $1/(z-s)$ and
$$
(z-s)g_\va(z) - 1 = (s-s^3)z^{-3}+\ldots
$$
Therefore for $s^3-s\neq 0$ we have that $\Phi(g_\va)$ contains a primitive
gap $[1,3]$ of size 2. Note that $z^{3^m}-s$ is always coprime with the
polynomial $z^2 + sz+s^2$. Indeed, each root $z_0$ of the latter quadratic
polynomial satisfies $|z_0|^3 = |s|^3$, so $|z_0|^{3^m} = |s|^{3^m} > |s|$ as
soon as $|s|\ge 2$. But the last condition is equivalent to $s\neq \pm 1,0$
which in turn is equivalent to $s^3 - s\neq0$.

We thus have that the numerator and the denominator of
$$
\frac{\prod_{t=0}^{m-1} (z^{2\cdot 3^t} + sz^{3^t}+s^2)}{z^{3^m} - s}
$$
are always coprime. Therefore the all values $r_{c,m}$ equal zero and
equations~\eqref{form_un} imply that for the gaps $[u_n,v_n]$ generated by
$[1,3]$ we have
$$
\frac{v_{n+1}}{u_{n+1}} = \frac{3v_n -2}{3u_n}
$$
and therefore
$$
\liminf_{n\to \infty}\frac{v_n}{u_n} = \frac{v_0 - \frac{2}{2}}{u_0 + \frac{0}{2}} = 2.
$$

From Lemma~\ref{lem6} we know that the size of any primitive gap in
$\Phi(g_\va)$ does not exceed 5. Therefore, by Lemma~\ref{lem7}, only gaps
with
$$
2<\frac{v}{u-1}\le \frac{u+5}{u-1}
$$
may contribute to the irrationality exponent of $g_\va(b)$. The last
inequality is equivalent to $u<7$. It remains to note that $\Phi(g_\va) =
\{1,3,7,\ldots\}$ where the gap $[3,7]$ is not primitive and is generated by
$[1,3]$. Hence there are no other primitive gaps $[u,v]$ with $u<7$ and
Theorem~\ref{th1} implies:

\smallskip\noindent{\it Let $\va = (s,s^2)\in\ZZ^2$ with $s^3+s\neq 0$. If $|b|\ge 2$, $b\in\ZZ$ and $g_\va(b)\not\in\QQ$ then
$\mu(g_\va(b)) = 3$.}

For the remaining values of $s$ we have:
$$
g_{0,0}(z) = \frac{1}{z};\quad g_{1,1}(z) = \frac{1}{z-1};\quad g_{-1,1}(z) = \frac{1}{z+1}.
$$
The function $g_\va$ is then rational, and therefore $g_\va(b)\in\QQ$.

\medskip{\bf Family (b).} Let $\va = (s^3,-s^2(s^2+1))$. In this case we
compute
$$
\frac{p_2(z)}{q_2(z)} = \frac{z+s(s^2+1)}{z^2+sz+s^2}
$$
and
$$
q_2(z) g_\va(z) - p_2(z) = -(s^6+s^4+s^2)z^{-5} + \ldots
$$
Therefore for $s^6+s^4+s^2\neq 0$ we have that $\Phi(g_\va)$ contains the
primitive gap $[2,5]$ of size 3. One can easily check that $z^2 + s^3z -
s^2(s^2+1)= (z-s)(z+(s^3+s))$. On the other hand, all roots of $z^{2\cdot
3^m} + sz^{3^m} + s^2$ for $s\neq 0$ are not real. Therefore the fraction
$$
\frac{\prod_{t=0}^{m-1} (z^{2\cdot 3^t} + s^3z^{3^t}-s^2(s^2+1))p_2(z^{3^m})}{q_2(z^{3^m})}
$$
is always in its reduced form, i.e. every term of $r_{c,m}$ is zero. This
yields to
$$
\liminf_{n\to \infty}\frac{v_n}{u_n} = \frac{v_0 - \frac{2}{2}}{u_0 + \frac{0}{2}} = 2.
$$

As for the collection~(a), we need to check that $\Phi(g_\va)$ does not
contain any other primitive gap $[u,v]$ with $u<7$ which is obvious
(by~\eqref{form_un}, we have the big gaps $[2,5]$ and $[6,13]$ in
$\Phi(g_\va)$. There is no more space for big gaps with $u<7$). Therefore we
finally get:

\smallskip\noindent{\it Let $\va = (s^3,-s^2(s^2+1))$ with $s\in \ZZ, s^6+s^4+s^2\neq 0$. If $|b|\ge 2$, $b\in\ZZ$ and $g_\va(b)\not\in \QQ$ then
$\mu(g_\va(b)) = 3$.}

Finally notice that the equation $s^6+s^4+s^2=0$ has only one integer
solution: $s=0$. But $g_{0,0}(z)$ has already been considered in Family~(a)
and is equal to $1/z$.

\medskip\noindent{\bf Family (c).} Let $\va = (2,1)$. The case $\va =
(-2,1)$ is considered analogously and is left to the reader. One can check
that $1,2,3,4$ and $5$ belong to $\Phi(g_\va)$. Direct computation shows that
$[5,8]$ is the primitive gap in $\Phi(g_\va)$ and the corresponding fifth
convergent of $g_\va$ is
$$
p_5(z) = z^4+z^3+2z^2+4\;\mbox{and}\; q_5(z) = z^5-z^4+z^3-z^2+z-1 =
(z-1)(z^2+z+1)(z^2-z+1).
$$
In other words, $q_5(z) = \Phi_1(z)\Phi_3(z)\Phi_6(z)$. Lemma~\ref{lem9}
implies that all cyclotomic divisors of $q_5(z^{3^m})$ are either of the form
$\Phi_{3r}(z)$ with some integer $r$ or $\Phi_1(z)$. Hence $q_5(z^{3^m})$ is
always coprime with $z^2+2z+1 = \Phi_2(z)^2$, i.e. the fraction
$$
\frac{\prod_{t=0}^{m-1} (z^{2\cdot 3^t} + 2z^{3^t}+1)p_5(z^{3^m})}{q_5(z^{3^m})}
$$
is always in its reduced form and every term of $r_{c,m}$ is zero. This
yields to
$$
\liminf_{n\to\infty} \frac{v_n}{u_n} = \frac{v_0-1}{u_0} = \frac75.
$$

Now from Lemma~\ref{lem6} we know that the size of any primitive gap in
$\Phi(g_\va)$ does not exceed 5. Therefore, by Lemma~\ref{lem7}, only gaps
with
$$
\frac75<\frac{v}{u-1}\le \frac{u+5}{u-1}
$$
may contribute to the irrationality exponent of $g_\va(b)$. The last
inequality is equivalent to $u<16$. It remains to show that all integers from
8 to 15 belong to $\Phi(g_\va)$. This for example can be done
(see,~\cite[Corollary 1]{badziahin_2017} for justification) by checking that
the corresponding Hankel determinants
$$
H_n:= \det (c_{i+j-1})_{i,j\in\{1,\ldots, n\}},\quad n=8,\ldots 15
$$
are not zero, where $c_i$ are the coefficients of the series $g_\va$:
$$
g_\va(z) = \sum_{i=1}^\infty c_i z^{-i}.
$$

Finally we have:
\smallskip\noindent{\it Let $\va = (\pm 2,1)$. If $|b|\ge 2$, $b\in\ZZ$ then
$\mu(g_\va(b)) = \frac{12}{5}$.}

config: arxiv


TITLE: Order-preserving map of regressive functions on $\omega_1$
QUESTION [13 upvotes]: I posted the following question in March 2014 on MO. It did receive some attention, but the answer there remains incomplete. It was motivated by some paracompactness-type properties as discussed at the end, but the question is purely order-theoretic, about $\omega_1$.
Let $\omega_1$ be the first uncountable ordinal,
same as the set of all countable ordinals.
Let $\mathcal F$ be the set of all functions
$f:\omega_1\to\omega_1$ that
are:
(a) regressive i.e. $f(\alpha) < \alpha$ for all $0 < \alpha < \omega_1$,
and
(b) non-decreasing (same as $\le$-order-preserving),
i.e.,
if $0\le\alpha \leq \beta<\omega_1$ then $f(\alpha)\leq f(\beta)$ .
Define a partial order $\sqsubseteq$ on $\mathcal F$ by $f \sqsubseteq g$ if
$f(\alpha) \leq g(\alpha)$ for all $\alpha < \omega_1$.
Let $\mathcal K$ be the subset of $\mathcal F$, consisting of functions with
a finite range.
Formally $\mathcal K=\{f\in\mathcal F: |\{f(\alpha):\alpha<\omega_1\}|<\aleph_0\}$.
Question:
Is there a $\sqsubseteq$-order-preserving map
(same as a $\sqsubseteq$-non-decreasing map)
$\psi : \mathcal F \to \mathcal K$, i.e if $f \sqsubseteq g$
then $\psi(f) \sqsubseteq \psi(g)$, and with
the additional property that $\psi(f) \sqsupseteq f$ for all $f\in \mathcal F$ ?
Let me summarize some comments made at MO, clarifying certain partial answers.
Partial answer (A). Since every $f\in\mathcal F$ is regressive and non-decreasing, it must be eventually constant and reach its maximal value $\mu_f=\max\{f(\alpha):\alpha < \omega_1\}$. One is tempted to define $\psi(f)(\alpha)=\mu_f$ for all $\alpha$. The problem is that this is not regressive: We have $\psi(f)(\alpha)<\alpha$ only when $\alpha>\mu_f$, but I insist that $\psi(f)(\alpha)<\alpha$ whenever $0<\alpha<\omega_1$.
Partial answer (B). If we drop the requirement that $\psi$ be a $\sqsubseteq$-non-decreasing map then the answer by @NoahS at MO works, as well as one of my comments there, which  I include below. As above let $\mu_f=\max\{f(\alpha):\alpha < \omega_1\}$ and let $\gamma_f=\min\{\alpha:f(\alpha)=\mu_f\}$. (Then $f(\alpha)=\mu_f$ for $\alpha\ge\gamma_f$, and $f(\alpha)<\mu_f$ for $\alpha<\gamma_f$. Usually $\mu_f<\gamma_f$ unless $\mu_f=0=\gamma_f$.)
Let $\alpha_{0,f}=\mu_f$. If $\mu_f\ge1$ then let $\alpha_{1,f}=f(\alpha_{0,f})<\alpha_{0,f}$. There is a non-negative integer $n_f$ such that $\alpha_{k+1,f}=f(\alpha_{k,f})<\alpha_{k,f}$ for $k<n_f$, and $\alpha_{n_f,f}=0$. Define $\psi(f)$ as follows. If $\alpha>\alpha_{0,f}$ then let $\psi(f)(\alpha)=\alpha_{0,f}=\mu_f$. If $\alpha_{k+1,f}<\alpha\le\alpha_{k,f}$ then let $\psi(f)(\alpha)=\alpha_{k+1,f}$. (Formally also $\psi(f)(0)=0$, but in general each function in $\mathcal F$ being regressive must take value $0$ at $1$, and being non-decreasing must take value $0$ at $0$ as well.) Then $\psi(f)\in\mathcal K$ and $\psi(f)\sqsupseteq f$.
So partial answer (A) above achieves that $\psi(f)$ has a finite range, and
$\psi(f) \sqsubseteq \psi(g)$ whenever $f \sqsubseteq g$, and also $\psi(f) \sqsupseteq f$. It almost achieves that $\psi(f)$ is regressive, but not quite, and it follows that $\psi(f)$ is not in $\mathcal K$ unless $\mu_f=0$. (One could perhaps say that $\psi(f)$ is "regressive on a tail" only, which might in a different context be good enough, but the requirement in my question is that $\psi(f)(\alpha)<\alpha$ whenever $0<\alpha<\omega_1$.) On the other hand, partial answer $B$ achieves that
$\psi(f)\in\mathcal K$ (in particular both that $\psi(f)$ is regressive and has a finite range), and $\psi(f) \sqsupseteq f$ for all $f\in \mathcal F$, but not necessarily that $\psi(f) \sqsubseteq \psi(g)$ whenever $f\sqsubseteq g$. It is not clear to me if we could achieve all conditions simultaneously. Edit. Following a comment (on MO), let me clarify why in partial answer $B$ we need not have $\psi(f) \sqsubseteq \psi(g)$ whenever $f\sqsubseteq g$. Fix any ordinals $0<\beta<\delta<\nu<\omega_1$. Let $f(\alpha)=g(\alpha)=0$ if $0\le\alpha<\nu$. Let $f(\alpha)=\beta$ and $g(\alpha)=\delta$ if $\alpha\ge\nu$.
Clearly $f\sqsubseteq g$.
Then $\psi(f)(\alpha)=\beta$ if $\alpha>\beta$, and
$\psi(f)(\alpha)=0$ if $0\le\alpha\le\beta$
(where $\psi$ is as in partial answer $B$).
While $\psi(g)(\alpha)=\delta$ if $\alpha>\delta$, and
$\psi(g)(\alpha)=0$ if $0\le\alpha\le\delta$. In particular, if $\beta<\alpha\le\delta$ then $\psi(g)(\alpha)=0<\beta=\psi(f)(\alpha)$,
so $\psi(f)\not\sqsubseteq \psi(g)$.
If I were to make a guess, I would say the answer is no.
This question is an order-theoretic restatement of a question from general topology that a co-author and I considered: Whether $\omega_1$ has a monotone interior-preserving open operator $r$, that is, if $\mathcal U$ is any open cover of $\omega_1$, with the order topology, then $r(\mathcal U)$ is an interior-preserving open refinement that covers $\omega_1$, and if $\mathcal U$ refines $\mathcal V$ then $r(\mathcal U)$ refines $r(\mathcal V)$. As usual we would write $\mathcal U\preceq \mathcal V$ if $\mathcal U$ refines $\mathcal V$. In this context $f$ is intended to encode an open cover $\mathcal U(f)=\{0\}\cup\{(f(\alpha),\alpha]:\alpha<\omega_1\}$. Note that if $f\sqsubseteq g$ then $\mathcal U(g)\preceq \mathcal U(f)$.
Update Oct 19, 2018 (and May 21, 2019):
This question has now been published in a journal.
It is Question 3.2 in the following paper:
Serdica Math. J. 44 (2018) (dedicated to the memory
of Professor Stoyan Nedev (1942−2015))
ON MONOTONE ORTHOCOMPACTNESS
S.G. Popvassilev, J.E. Porter
Here is a temporary link from the editors:
http://www.math.bas.bg/serdica/2018/2018-177-186.pdf
(Update as of August 21, 2020.)
This question has been answered in the negative by Gary Gruenhage. I will post a complete answer some time in the future. Here is a sketch of the proof. The existence of an order-preserving map $\psi$ as in the question is equivalent to $\omega_1$ being monotonically orthocompact via open refinements, abbrevaited MO$_o$ (this is Theorem 3.1 in the paper, a link to which is enclosed at the end of this question). What Gary proved is that MO$_o$ implies a certain property called (A$_o$) (defined in terms of certain neignborhoods), and that $\omega_1$ does not have this property (A$_o$).
(Update April 25, 2021.)
I am about to publish an answer here with details of Gary Gruenhage's proof (thus answering the above question is the negative).
Thank you!

REPLY [0 votes]: The answer to the above question is no (there is no such mapping $\psi$).
The question asked above is an order-theoretic restatement of a question from general topology:
Question. Does $\omega_1$ (with its usual order topology) have a monotone interior-preserving open operator $r$ (defined below)?
Definition. A topological space $X$ in monotonically orthocompact via open refinements (abbreviated MO$_o$) if it has a monotone interior preserving open operator $r$, that is:
(i) if $\mathcal U$ is any open cover then $r(\mathcal U)$ is an interior-preserving open refinement (that covers $X$), and
(ii) if $\mathcal U$ refines $\mathcal V$ then $r(\mathcal U)$ refines $r(\mathcal V)$.
The operator $r$ will also be called an MO$_o$ operator (for $X$).
The proof that the two questions are equivalent is
in Theorem 3.1 in the following paper:
ON MONOTONE ORTHOCOMPACTNESS
S.G. Popvassilev, J.E. Porter
Serdica Math. J. 44 (2018) (dedicated to the memory
of Professor Stoyan Nedev (1942−2015))
http://www.math.bas.bg/serdica/2018/2018-177-186.pdf
As the above paper seems to be reliably available online, I will only include here a negative answer (due to Gary Gruenhage) of the topological version. Namely:
Theorem. $\omega_1$ is not MO$_o$.
This result is included in the following paper.
MONOTONE  ORTHOCOMPACTNESS  AND  PROPERTY  (A$_o$)
Gary Gruenhage, Strashimir G. Popvassilev, and John E. Porter
(accepted for publication in the journal Topology Proceedings)
The proof consists of two steps (both due to Gary Gruenhage):
(1) Every regular Hausdorff MO$_o$ space has property (A$_o$) (defined below), and
(2) $\omega_1$ does not have property (A$_o$).
I just copy these results from our paper and paste them here.
Definition 2.1. Let (A$_o$) be the following property (of a topological space $X$):
One can assign to each pair $(x,U)$, where $U$ is open and $x \in U$, an open set
$V(x,U)$ such that
(1) $x\in V(x,U)\subset U$ ;
(2) whenever $y\in \bigcap_{\alpha<\kappa} V(x_\alpha, U_\alpha)$, there is $A \subset \kappa$ such that $y \in
    \textrm{Int}(\bigcap_{\beta \in A}U_\beta)$ and for each $\alpha \in \kappa$ there is $\beta \in A$ with
$V(x_\alpha, U_\alpha) \subset U_\beta$.
Theorem 2.2. For a regular Hausdorff space $X$, MO$_o$  implies property (A$_o$).
Proof.
Let $r$ be an MO$_o$ operator for $X$. Let $U$ be open and $x \in U$. Choose open $W(x,U)$ with $x \in W(x,U)
\subset \overline{W(x,U)} \subset U$, and let $$\mathcal{O}_{x,U} = \{U, X \setminus \overline{W(x,U)}\}.$$
Then choose
$P(x,U) \in r(\mathcal{O}_{x,U})$ such that $x \in P(x,U)$ and let $V(x,U)= W(x,U) \cap P(x,U)$.
Suppose $y \in \bigcap_{\alpha<\kappa} V(x_\alpha, U_\alpha)$. Let $\mathcal{O}^*= \bigcup_{\alpha<\kappa}
\mathcal{O}_{x_\alpha, U_\alpha}$. For each $Q \in r(\mathcal{O}^*)$ with $y \in Q$, there is $O \in \mathcal{O}^*$ with
$Q \subset O$. Since $y \in V(x_\alpha, U_\alpha) \subset W(x_\alpha, U_\alpha)$ for all $\alpha$, it must be that
$O=U_\alpha$ for some $\alpha$. Choose such an $\alpha$ and denote it $\alpha(Q)$. So $Q \subset U_{\alpha(Q)}$. Finally let
$$A=\{\alpha(Q): y \in Q \in r(\mathcal{O}^*)\}.$$
We claim that
(1) $y \in \textrm{Int}(\bigcap_{\beta \in A}U_\beta)$ and
(2) for each $\alpha \in \kappa$ there is $\beta \in A$ with $V(x_\alpha, U_\alpha) \subset U_\beta.$
Note that (1) holds because each $U_\beta$ for $\beta \in A$ contains some $Q$ with $y \in Q \in r(\mathcal{O}^*)$, and
$r(\mathcal{O}^*)$ is interior preserving.
To see (2), suppose $\alpha <\kappa$. Note that
$\mathcal{O}_{x_\alpha, U_\alpha}$ refines $\mathcal{O}^*$
and so $r(\mathcal{O}_{x_\alpha,U_\alpha})$ refines $r(\mathcal{O}^*)$. Hence $P(x_\alpha,U_\alpha) \subset Q$ for some
$Q \in r(\mathcal{O}^*).$ Note that $y \in Q$ because $y \in V(x_\alpha, U_\alpha) \subset P(x_\alpha,U_\alpha).$
So now we have $$V(x_\alpha, U_\alpha) \subset P(x_\alpha, U_\alpha) \subset
 Q \subset U_{\alpha(Q)},$$ and (2) follows.
(End of proof of Theorem 2.2.}
Theorem 3.1. Let $S$ be a stationary subset of a regular uncountable cardinal $\kappa$. Then $S$ does not have property (A$_o$) (and hence is not MO$_o$; in particular $\omega_1$ is not MO$_o$).
Proof. Suppose by way of contradiction that the operator $V$ witnesses (A$_o$). Let $\alpha_0=0$. For each $x \in S$, $x>1$, we may assume
$V(x, (\alpha_0+1,x]) =(\beta_x, x]$ for some $0<\beta_x < x$. By the pressing down lemma, there is $\alpha_1 > \alpha_0$ such that
$\beta_x = \alpha_1$ for $\kappa$-many $x$ in $S$.
Similarly, there is $\alpha_2> \alpha_1$ such that $V(x, (\alpha_1 +1,x]) =(\alpha_2, x]$  for $\kappa$-many $x$. And so on.
Continue in this way to define a strictly increasing
$\kappa$-sequence $\alpha_\gamma$, $\gamma<\kappa$, of elements of
$\kappa$ such that
(i) $\forall \gamma<\kappa ( |\{x>\alpha_\gamma: V(x, (\alpha_\gamma+1,x])=(\alpha_{\gamma+1},x]\}|=\kappa$);
(ii) if $\beta$ is a limit, then $\alpha_\beta=\sup\{\alpha_\gamma: \gamma<\beta\}$.
Then $\gamma\mapsto \alpha_\gamma$ is an increasing continuous mapping of $\kappa $ onto a club subset of $\kappa$; this is also the
case if $\gamma$ is restricted to limit ordinals. It follows that there is some $\delta$ in $S$ such that $\delta=\alpha_\beta$ for
some limit ordinal $\beta$. Then $\delta=\sup\{\alpha_\gamma:
\gamma <\beta\}.$
Now we may inductively choose a strictly increasing sequence $x_\gamma$, $\gamma<\beta$, in $S$ such that
$x_0 > \delta$ and $V(x_\gamma, (\alpha_\gamma+1, x_\gamma]) = (\alpha_{\gamma+1}, x_\gamma]$.
For $\gamma<\beta$, let $U_\gamma = (\alpha_\gamma +1, x_\gamma]$ and $V_\gamma= (\alpha_{\gamma+1}, x_\gamma]$. Then $V(x_\gamma,
U_\gamma) = V_\gamma$.
Note that $\delta$ is in every $V_\gamma$ for $\gamma < \beta$.
Since $V$ witnesses property (A$_o$), there is a subset $A$ of  $\beta$ such that
(I) $\delta \in \textrm{Int}(\bigcap_{\gamma \in A}U_\gamma)$, and (II) for each $\gamma \in \beta$ there is $\eta \in A$ with
$V_\gamma \subset U_\eta$.
Since the $\alpha_\gamma$'s increase to $\alpha_\beta=\delta$, for (I) to hold the set $A$ cannot be cofinal in $\beta$. But since
the $x_\gamma$'s are strictly increasing, $A$ must be cofinal in $\beta$ for (II) to hold, so we have a contradiction.
(End of proof or Theorem 3.1)