$Paz^T = Q$, so $P$ and $Q$ can be zero only simultaneously: but in this case, the rank of $W^{[\sigma]}$ makes $\Pi$ be zero, so the kernel has dimension 1. (In an actual calculation, a failure of the computed kernel to have dimension 1 proves that $\sigma$ must be increased.) From this, we obtain a parametrized candidate solution $Q/P$. Cramer's rules applied to a selection of $\rho^{[\sigma]} + 1$ columns of $W_a^{[\sigma]}$ including the last one show that $P$ is independent of $a$ and $Q$ is linear in $a$.

We continue as in the Riccati case: all candidates have to be checked against degree bounds and exact evaluation to 0 of the linear Mahler equation, and false solutions require to increase $\sigma$.

Experimentally, the algorithm above seems to behave better than our Algorithm 9 in (CDDM 2018). It would thus be of interest to analyze its complexity.

# Part IV: Implementation and application

## 10. Benchmark

### 10.1. Implementation

To test the examples listed in §10.2, we used Dumas's package dcfun<fnref n="5" />. This contains an implementation of Algorithms 1, 3, and 4, and the needed parts of (CDDM 2018) in the computer-algebra system Maple. It calls Singular's routine for primary decomposition (see below).

The implementation of Algorithms 1 and 3 corresponds to their specification, but the implementation of Algorithm 4 has limitations, which have however no impact on the validity of the treatment of examples in §10.3, as we now explain.

Although algorithms for computing Hermite-Padé approximants allow algebraic coefficients, no implementation was available in Maple beyond rational number coefficients. For step (C)(h)(2) in Algorithm 4, we have therefore used the Maple command `MahlerSystem` in the package `MatrixPolynomialAlgebra` that is restricted to coefficients in $\mathbb{Q}$, thus forcing $\mathbb{K} = \mathbb{Q}$, and limiting the search for rational solutions of $(R)$ to series in $\bar{\mathbb{Q}}(x^{1/*})$ with leading coefficient $\lambda$ in $\mathbb{Q}$. In principle, this allows the implementation to find solutions corresponding to $\lambda \in \Lambda \cap \mathbb{Q}$ (recall (3.8)), but in practice, all of our examples have $\Lambda \subseteq \mathbb{Q}$.

Although algorithms for computing primary decompositions allow the search for decompositions over the algebraic closure of $\mathbb{K}$, implicitly making algebraic extensions as needed along their process, Maple's command `PrimeDecomposition` in the package `PolynomialIdeals` limits the algebraic numbers used to an algebraic field specified as part of the input. To the best of our knowledge, the only general implementation is available in the computer-algebra system Singular, as the command `absPrimdecGTZ`. The Maple implementation of Algorithm 4 transparently calls Singular at its step (C)(h)(6)(γ).

<footnote n="5">⁵available from https://mathexp.eu/dumas/dcfun/</footnote>
## 10.2. Examples

To validate and exemplify our theory, we propose two kinds of examples. The first consists of generating functions of automatic sequences or more generally of sequences satisfying a linear recurrence with constant coefficients of the divide-and-conquer type. The second kind is provided by lclms (least common left multiples) of operators vanishing on simple expressions, like rational or power functions. In the subsequent tables and discussions, all examples are referred to by self-explanatory pseudonyms, like Baum_Sweet for the equation appearing in Example 1.1(2) and Rudin_Shapiro for the first one below.

### 10.2.1. Generating functions of automatic sequences and like sequences

**Example 10.1.** The Rudin-Shapiro sequence $(a_n)_{n \in \mathbb{N}}$ is the automatic sequence defined by $a_n = (-1)^{e_n}$ where $e_n$ is the number of (possibly overlapping) blocks 11 in the binary representation of $n$ (OEIS, A020985). It is characterized by the recurrence relations

$$a_0 = 1, \quad a_{2n} = a_n, \quad a_{2n+1} = (-1)^n a_n,$$

hence its generating function satisfies the Mahler equation

$$2xM^2y - (x-1)My - y = 0 \quad (b=2). \qquad (\text{Rudin\_Shapiro})$$

**Example 10.2.** Let us consider again the Stern-Brocot sequence that was defined in Example 1.1(3). We will re-obtain the well-known fact that its generating function is the Mahler hypergeometric function

$$y(x) = x \prod_{k \ge 0} (1 + x^{2^k} + x^{2^{k+1}}) = \sum_{n \ge 1} a_n x^n \in \mathbb{Z}[[x]],$$

which is obviously a solution of $L_2y(x) = xy(x) - (1+x+x^2)y(x^2) = 0$ with $b=2$.

To this end, we follow a method implicit in (Christol, Kamae, Mendès France, and Rauzy 1980) that was detailed in (Allouche 1987). Write $y_1(x) = y(x)$ and introduce $y_2(x) = \sum_{n \in \mathbb{N}} a_{2n+1}x^n$, to obtain

$$Y(x) = A(x)Y(x^2) \quad \text{for} \quad Y(x) = \begin{pmatrix} y_1(x) \\ y_2(x) \end{pmatrix}, \quad A(x) = \begin{pmatrix} 1 & x \\ 1-x & 1+2x \end{pmatrix}.$$

After introducing the Mahler operator for the radix $b=2$, we get $Y = A(MY)$, next $Y = A(MA)(M^2Y)$, hence, after setting $R = (1,0)$,

$$y_1 = RA(MA)(M^2Y), \quad My_1 = R(MA)(M^2Y), \quad M^2y_1 = R(M^2Y).$$

Because the row vectors $RA(MA)$, $R(MA)$, $R$ are linearly dependent over $\overline{\mathbb{Q}}(x)$, there is an operator $L'_2$ of order 2 canceling $y_1$. Performing the procedure using
Maple, we readily obtain it in explicit form, so that the generating series $y(x)$ is a solution of

$$L_2'y(x) = xy(x) - (1 + x + 2x^2)y(x^2) + (1 + x^2 + x^4)y(x^4) = 0. \quad (\text{Stern_Brocot_b2})$$

Both Algorithm 3 and Algorithm 4 compute the hypergeometric solutions of $L'_2$, to prove that the only ones are multiples of $y(x)$. Correspondingly, one can also verify the relation $L'_2 = (1 - M)L_2$.

Because $y(x)$ is as solution of a linear Mahler equation for radix $b = 2$, for any $k \ge 2$, it is also a solution of a linear Mahler equation for radix $b^k$ that one can make explicit. This gives rise to related operators: an annihilating operator of the generating function $y(x)$, of order 2 for radix $b = 4$, is

$$L'_4 = (1 + x + 2x^2)(1 + x + x^2)^2(1 - x + x^2)^2(1 - x^2 + x^4)^2(1 - x^4 + x^8)M^2 - c_1(x)M + x^3(1 + x^4 + 2x^8) \quad (b = 4) \quad (\text{Stern_Brocot_b4})$$

with

$$c_1(x) = \sum_{n=0}^{14} a_{n+1}x^n = 1 + x + 2x^2 + x^3 + 3x^4 + 2x^5 + 3x^6 + x^7 + 4x^8 + 3x^9 + 5x^{10} + 2x^{11} + 5x^{12} + 3x^{13} + 4x^{14}.$$

As well, $y(x)$ is Mahler hypergeometric with respect to radix $b = 4$, as reflected by the factorization $L'_4 = ((2x^2 + x + 1)M - (2x^8 + x^4 + 1))L_4$ for

$$L_4 = (x^2 + x + 1)(x^4 + x^2 + 1)M - x^3 \quad (b = 4).$$

**Example 10.3** (Missing digit in ternary expansion). The sequence 0, 1, 3, 4, ... of nonnegative integers whose ternary expansion does not contain the digit 2 (OEIS, A005836) has a generating function $y(x) = x+3x^2+4x^3+9x^4+10x^5+...$ annihilated by the operator

$$L = x - (1 + 3x + 4x^2)M + 3(1 + x^2)^2 M^2 \quad (b = 2). \quad (\text{no_2s_in_3_exp})$$

Using either of our algorithms, we find that $L$ admits the unique right-hand factor $M - 1/(3(1+x))$, corresponding to hypergeometric series solutions of $L$ that are scalar multiples of $(\ln x)^{\log_2(1/3)}/(1-x)$. This proves that the generating series $y(x)$ is not hypergeometric.

**Example 10.4.** Inspired by (Dilcher and Stolarsky 2007, Prop. 5.1), we consider the formal power series $F(x) \in \mathbb{Z}[[x]]$ that is a solution of

$$x^4 M^2 y(x) - (1 + x + x^2) M y(x) + y(x) = 0 \quad (b = 4), \quad y(0) = 1. \quad (\text{Dilcher_Stolarsky})$$
**Example 10.5.** Katz and Linden (2022, §3.1) define a sequence $(A_t(x))_{t \in \mathbb{N}}$ whose generating function $y(w, x) = \sum_{t \ge 0} A_t(x)w^t$ satisfies an order 4 and degree 14 equation $Ly = 0$ with respect to $x$ with $b = 2$ and

$$ 
\begin{aligned}
L = & -x(x+1)(8x^4w^2 + 4x^2w - x^2 + 2w - 1) \\
& -x(8w^3x^7 - 8w^3x^6 + 8w^3x^5 + 8w^3x^4 - 4w^2x^5 - 4x^4w^2 - wx^5 \\
& - 2w^2x^3 - 3wx^4 + 2w^2x^2 - 4wx^3 + x^4 + 2w^2x - 4x^2w \\
& + x^3 + 2w^2 - 3wx + x^2 - w + x)M \\
& + x^2w(16w^3x^8 + 8w^2x^8 + 32w^3x^5 + 4wx^7 + 16w^3x^4 - x^7 + 12x^4w^2 \\
& - 4wx^5 - x^6 + 16w^2x^3 - 4wx^4 + x^5 + 16w^2x^2 + x^4 + 8w^2x - x^3 \\
& + 4w^2 - x^2 - x - 1)M^2 \\
& + 2x^4w^2(-8w^2x^{10} - 4wx^9 + 32w^3x^6 - 2wx^8 + x^9 + x^8 - 4wx^4 - 8wx^3 \\
& - 8x^2w + 2x^3 - 4wx + 2x^2 - 2w + x + 1)M^3 \\
& - 8x^{12}w^3(8w^2x^2 + 4wx + 2w - x - 1)M^4.
\end{aligned} 
\quad (\text{Katz\_Linden}) $$

The theory we developed in the previous sections made the hypothesis that $K$ is a computable subfield of $\mathbb{C}$ mostly in order to reuse results from our previous article. However, the theory easily adapts to equations that depend rationally on auxiliary parameters, and our implementation is able to deal with this example as well.

**Example 10.6 (Parities and ternary expansion).** The operator of order 4 and degree 258 of Example 1.5 has been our running example in Examples 8.15, 8.25, 8.29, and 8.30. We call it **Adamczewski_Faverjon** in our tables. In roughly one second, Algorithm 4 finds that the only rational solutions to the Riccati Mahler equation are

$$ \frac{1}{1-x-x^2}, \quad \frac{1}{1+x-x^2}, \quad \frac{g_1+g_2x^3}{g_1+g_2x} \quad \frac{1}{1+x^2+x^4}. $$

(Algorithm 3 has an equivalent output in over 70 minutes.) This corresponds to the hypergeometric solutions of $L$ that were given as (1.1) to deduce that none of the $y_i$ of Example 1.1(4) is hypergeometric.

### 10.2.2. Operators related to criteria of differential transcendence

The criteria to be discussed in §11 will lead us to solve the auxiliary Riccati equation (11.2) beside the equations (R), a.k.a. (11.1), for operators of order $r = 2$. We thus introduced problems named **dft_⟨p⟩** where $p$ ranges over relevant problems already listed in §10.2.1.

### 10.2.3. Cooked-up examples

**Example 10.7 (Annihilator related to rational functions).** We produced two examples as lclms of three first-order operators in $\mathbb{Q}[x]⟨M⟩$, thus forcing the Riccati equation to have known rational solutions. In both cases, the Riccati
equation has an isolated rational solution plus a family parametrized by a projective line. However, by adjusting a coefficient, we forced the number $m$ of distinct $\lambda$ in the logarithmic parts of solutions of (L) to be either 1 or 2. These examples are named `lclm_3rat_\langle m\rangle\log`.

For more involved examples, we started with a first operator $L_1$ defined as the lclm of $q$ first-order operators, which we then tweaked into an operator $L_2$ by discarding monomials above some line of a given slope $s$ in the lower Newton polygon of $L_1$ (Definition 3.4). In this way, we predict the same dimensions of series solutions, but we expect to lose their hypergeometric nature. After taking the lclm of $L_1$ and $L_2$, we obtain the operators for our examples `lclm_\langle q\rangle\text{rat_trunc_sl}\langle s\rangle`. In particular, the operator in Example 8.35 is the one for example `lclm_2rat_trunc_sl1` in the tables. The corresponding $L_1$ is of order 2 with all its solutions rational.

**Example 10.8 (Annihilator of power functions).** For various pairs $(b, q)$ given by a radix $b \le 5$ and some positive integer $q \le 5$, we considered some operator $L_{b,q} \in \mathbb{Q}[x]\langle M\rangle$ annihilating the $q$ powers $x^{1/1}, x^{1/2}, \dots, x^{1/q}$. The corresponding example is called `lclm_\langle q\rangle\text{pow_b}\langle b\rangle` in the tables. To obtain the operator $L_{b,q}$, we considered the lclm of binomial annihilators for the relevant $x^{1/i}$, which, to ensure no ramification in these operators, need not be of order 1. As an example, for $(b, q) = (3, 4)$, we used the annihilators $B_i$ of $x^{1/i}$ given as

$$B_1 = M - x^2, \quad B_2 = M - x, \quad B_3 = M^2 - x^2 M, \quad B_4 = M^2 - x^2.$$

Their lclm $L_{3,4}$ has order $r = 6$ and degree $d = 727$.

**Example 10.9 (Random equations).** To test the robustness of the Hermite-Padé approach, we considered random operators constructed as follows. Given a radix $b \in \{2, 3\}$ and some degree parameter $\delta$, we first draw random $A, B$, and $C$, each of the form $VM - U$ for dense polynomials $U$ and $V$ of degree $\delta$ in $x$ having integer coefficients in the range $[-1000, 1000]$. Let $\delta'$ be the degree in $x$ of $C' := \text{lclm}(A, B)$, normalized to have no denominator. Then, the operator $\tilde{C} := C' + x^{\delta'}(M^2 + M + 1)$ has the same dimension of series solutions and series solutions with the same possible valuations as $C'$, but no more hypergeometric solutions. Then, our random operator is chosen to be $L := \text{lclm}(C, \tilde{C})$. It has a hypergeometric solution, and the Riccati Mahler equation admits the rational function $U/V$ corresponding to $C$ as a rational solution. These are the examples `rmo_b_\delta` in the tables, for $b = 2, 3$ and $\delta = 1, \dots, 5$.

### 10.3. Discussion of the timings

We have executed our algorithms on the operators of §10.2 on a Dell Precision Mobile 7550 with i9 processor and 64 GB of RAM, running under an up-to-date Archlinux system. For reproducibility of the timings, we have put the processor in a state where thermal status and number of concurrent jobs has no influence,<fnref n="6" />

<footnote n="6">⁶Using the “performance cpufreq governor” and forbidding any adaptive cpu overclocking, a.k.a. cpu “turbo mode” avoids variations of timings up to a factor of 2.</footnote>
<table><caption>Table 2: Comparison of both variants of our Mahlerian analogue of Petkovšek's method given by Algorithms 1 and 3 for the search of rational solutions, with $L = Q$. See Table 3 for the meaning of columns. All times measured in seconds.</caption><thead><tr><th>example</th><th>br</th><th>d</th><th>var</th><th>tpl</th><th>anc</th><th>cfs</th><th>pol</th><th>#&#x0304;</th><th>tot</th></tr></thead><tbody><tr><td rowspan="2">Baum_Sweet</td><td rowspan="2">22</td><td rowspan="2">1</td><td>BP</td><td>1</td><td>0.04</td><td>0.00</td><td>0.01</td><td>0</td><td>0.06</td></tr><tr><td>IP</td><td>1</td><td>0.04</td><td>0.00</td><td>0.02</td><td>0</td><td>0.07</td></tr><tr><td rowspan="2">Rudin_Shapiro</td><td rowspan="2">22</td><td rowspan="2">1</td><td>BP</td><td>2</td><td>0.04</td><td>0.00</td><td>0.01</td><td>0</td><td>0.07</td></tr><tr><td>IP</td><td>1</td><td>0.00</td><td>0.00</td><td>0.02</td><td>0</td><td>0.08</td></tr><tr><td rowspan="2">no_2s_in_3_exp</td><td rowspan="2">22</td><td rowspan="2">4</td><td>BP</td><td>6</td><td>0.06</td><td>0.01</td><td>0.03</td><td>2</td><td>0.11</td></tr><tr><td>IP</td><td>4</td><td>0.01</td><td>0.00</td><td>0.04</td><td>2</td><td>0.12</td></tr><tr><td rowspan="2">Stern_Brocot_b2</td><td rowspan="2">22</td><td rowspan="2">4</td><td>BP</td><td>4</td><td>0.08</td><td>0.01</td><td>0.02</td><td>2</td><td>0.13</td></tr><tr><td>IP</td><td>2</td><td>0.01</td><td>0.00</td><td>0.03</td><td>1</td><td>0.12</td></tr><tr><td rowspan="2">Stern_Brocot_b4</td><td rowspan="2">42</td><td rowspan="2">26</td><td>BP</td><td>57</td><td>19</td><td>2.2</td><td>1.3</td><td>2</td><td>23</td></tr><tr><td>IP</td><td>30</td><td>4.7</td><td>0.00</td><td>0.53</td><td>1</td><td>5.4</td></tr><tr><td rowspan="2">Dilcher_Stolarsky</td><td rowspan="2">42</td><td rowspan="2">4</td><td>BP</td><td>3</td><td>0.06</td><td>0.01</td><td>0.02</td><td>0</td><td>0.11</td></tr><tr><td>IP</td><td>1</td><td>0.01</td><td>0.00</td><td>0.02</td><td>0</td><td>0.09</td></tr><tr><td rowspan="2">Katz_Linden</td><td rowspan="2">24</td><td rowspan="2">14</td><td>BP</td><td>54</td><td>4.2</td><td>1.1</td><td>12</td><td>0</td><td>17</td></tr><tr><td>IP</td><td>8</td><td>0.45</td><td>0.00</td><td>1.5</td><td>0</td><td>2.1</td></tr><tr><td rowspan="2">Adamczewski_Faverjon</td><td rowspan="2">34</td><td rowspan="2">258</td><td>BP</td><td>168</td><td>1307</td><td>275</td><td>20792</td><td>12</td><td>22412</td></tr><tr><td>IP</td><td>92</td><td>67</td><td>0.00</td><td>475</td><td>11</td><td>3</td><td>543</td></tr><tr><td rowspan="2">lclm_3rat_1log</td><td rowspan="2">33</td><td rowspan="2">121</td><td>BP</td><td>1628</td><td>1693</td><td>222</td><td>7754</td><td>21</td><td>9702</td></tr><tr><td>IP</td><td>116</td><td>62</td><td>0.00</td><td>140</td><td>5</td><td>2</td><td>203</td></tr><tr><td rowspan="2">lclm_3rat_2log</td><td rowspan="2">33</td><td rowspan="2">122</td><td>BP</td><td>1598</td><td>1438</td><td>184</td><td>7762</td><td>21</td><td>9411</td></tr><tr><td>IP</td><td>116</td><td>67</td><td>0.00</td><td>147</td><td>5</td><td>2</td><td>215</td></tr><tr><td rowspan="2">lclm_2rat_trunc_sl0</td><td rowspan="2">24</td><td rowspan="2">56</td><td>BP</td><td>1580</td><td>3339</td><td>391</td><td>1432</td><td>19</td><td>5263</td></tr><tr><td>IP</td><td>653</td><td>270</td><td>0.00</td><td>219</td><td>14</td><td>2</td><td>490</td></tr><tr><td rowspan="2">lclm_2rat_trunc_sl1</td><td rowspan="2">24</td><td rowspan="2">61</td><td>BP</td><td>2069</td><td>7463</td><td>1052</td><td>2595</td><td>9</td><td>11346</td></tr><tr><td>IP</td><td>915</td><td>468</td><td>0.00</td><td>358</td><td>8</td><td>2</td><td>828</td></tr><tr><td rowspan="2">dft_Baum_Sweet</td><td rowspan="2">42</td><td rowspan="2">6</td><td>BP</td><td>5</td><td>0.08</td><td>0.02</td><td>0.06</td><td>0</td><td>0.18</td></tr><tr><td>IP</td><td>1</td><td>0.01</td><td>0.00</td><td>0.03</td><td>0</td><td>0.10</td></tr><tr><td rowspan="2">dft_Rudin_Shapiro</td><td rowspan="2">42</td><td rowspan="2">7</td><td>BP</td><td>941</td><td>83</td><td>13</td><td>18</td><td>0</td><td>152</td></tr><tr><td>IP</td><td>81</td><td>3.0</td><td>0.00</td><td>2.3</td><td>0</td><td>5.8</td></tr><tr><td rowspan="2">dft_Stern_Brocot_b2</td><td rowspan="2">42</td><td rowspan="2">24</td><td>BP</td><td>50</td><td>12</td><td>1.0</td><td>0.87</td><td>2</td><td>15</td></tr><tr><td>IP</td><td>21</td><td>2.2</td><td>0.00</td><td>0.57</td><td>1</td><td>3.0</td></tr><tr><td rowspan="2">dft_no_2s_in_3_exp</td><td rowspan="2">42</td><td rowspan="2">20</td><td>BP</td><td>98</td><td>23</td><td>2.6</td><td>1.7</td><td>2</td><td>29</td></tr><tr><td>IP</td><td>80</td><td>8.1</td><td>0.00</td><td>1.3</td><td>2</td><td>9.6</td></tr><tr><td rowspan="2">dft_Dilcher_Stolarsky</td><td rowspan="2">16</td><td rowspan="2">50</td><td>BP</td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td><td></td></tr><tr><td>IP</td><td>2025</td><td>1064</td><td>0.00</td><td>2158</td><td>0</td><td>3382</td><td></td></tr><tr><td rowspan="2">dft_Stern_Brocot_b4</td><td rowspan="2">16</td><td rowspan="2">2348</td><td>BP</td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td><td></td></tr><tr><td>IP</td><td>1528</td><td>26096</td><td>0.00</td><td>3481</td><td>1</td><td>29670</td><td></td></tr></tbody></table>

effectively fixing the cpu frequency to 2.4 GHz, and run all examples one after another. We killed any example above either 12 hours of calculation or 60 GB of used memory.

Table 2 compares both variants of our Mahlerian analogue of Petkovšek's
• ‘var’ stands for the used variant, ‘BP’ (basic) or ‘IP’ (improved).

• ‘tpl’ counts the triples (B, A, ζ) considered (and dealt with) by the loops.

• ‘anc’ is the sum over (B, A) of the times to compute the ancillary operators $\tilde{L}$.

• ‘cfs’ is, in the basic variant, the sum over (B, A) of the times to compute the sets $Z(\tilde{L})$ of coefficients $\zeta$ in solutions $u$; it reduces to the single calculation of $Z(L)$ in the improved variant.

• ‘pol’ is the sum over (B, A, $\zeta$) of the times to solve for the polynomials $C$.

• ‘#’ is the cumulative count over (B, A, $\zeta$) of obtained parametrized solutions $u$, with possible redundancy.

• ‘$\tilde{\#$}$’ counts the number of parametrizations of solutions $u$ retained after removing repeated and embedded parametrizations.

• ‘tot’ is the total time of the ramified rational solving.

<caption>Table 3: Meaning of the columns in Table 2.</caption>

method. It shows the speedup of the improved Algorithm 3, which uses the various prunings and optimizations discussed in §7, over the basic Algorithm 1. All those calculations were obtained for the simpler case of the field $L = \mathbb{Q}$. The reduction of the number of triples $(B, A, \zeta)$ considered by the algorithms (typically by a factor in the range 2–10 in our list of examples) induces part of the speedup. In addition, we observe that computing the ancillary operators $\tilde{L}$ (see (6.8)) and the corresponding sets $Z(\tilde{L})$ (see Definition 6.2) takes a significant part of the time in some of the runs of the basic variant (more than half of the total time in cases like Stern_Brocot_b4 and dft_Rudin_Shapiro), and this time is saved by the improved variant. For computations of nonnegligible times, the overall speedup is typically of a few units or dozens of units. Because we do not expect any direct impact of the nature of the field $L \subseteq \mathbb{K}$ on the applicability of the pruning rules to avoid redundant pairs (see §7.2), we speculate that similar significant improvements would also occur for calculations with a more general number field $L$.

An example will suggest that Algorithms 1 and 3 are slower if we consider $L = \mathbb{Q}$ instead of $L = \mathbb{Q}$, because the introduction of absolute factorizations of the polynomials $\ell_0$ and $\ell_r$ induces more factors and exponentially more divisors $(A, B)$ to test. To this end, we consider Stern_Brocot_b4. When we change $L = \mathbb{Q}$ to $L = \mathbb{Q}$, the ramification bound (6.1), which generally could increase, is unchanged: $q_{\mathbb{Q}} = q_{\mathbb{Q}} = 1$. However, the number of factors of $\ell_0 = (2x^8 + x^4 + 1)x^3$ increases from 4 to 11 (when counted with multiplicities), and that of $\ell_2 = (2x^2+x+1)(x^8-x^4+1)(x^2+x+1)^2(x^2-x+1)^2(x^4-x^2+1)^2$ from 8 to 26, so that the number of pairs $(A, B)$ to be potentially tested is changed from $2 \cdot 4 \cdot 2 \cdot 2 \cdot 3 \cdot 3 = 864$ to $2^8 \cdot 4 \cdot 2^2 \cdot 2^8 \cdot 3^2 \cdot 3^2 \cdot 3^4 = 6879707136$: even if the filtering coprimality condition makes the count of pairs effectively leading
<table><caption>Table 4: Comparison of the improved Mahler analogue of Petkovšek's method (Algorithm 3, with $L = Q$) and the Hermite-Padé approach (Algorithm 4, over $\overline{Q}$). See Table 5 for the meaning of columns. All times measured in seconds.</caption><thead><tr><th rowspan="2">example</th><th rowspan="2">br</th><th rowspan="2">d</th><th colspan="2">IP</th><th colspan="6">HP</th></tr><tr><th>tot</th><th>fst</th><th>dim</th><th>σ</th><th>rfn</th><th>syz</th><th>sng</th><th>tot</th></tr></thead><tbody><tr><td>Baum_Sweet</td><td>22</td><td>1</td><td>0.07</td><td>0.07</td><td>(1,1)</td><td>(6,6)</td><td>0.03</td><td>0.03</td><td>-</td><td>0.13</td></tr><tr><td>Rudin_Shapiro</td><td>22</td><td>1</td><td>0.08</td><td>0.07</td><td>(1,0)</td><td>(6,-)</td><td>0.02</td><td>0.01</td><td>-</td><td>0.10</td></tr><tr><td>no_2s_in_3_exp</td><td>22</td><td>4</td><td>0.12</td><td>0.08</td><td>(1,1)</td><td>(33,9)</td><td>0.03</td><td>0.08</td><td>-</td><td>0.21</td></tr><tr><td>Stern_Brocot_b2</td><td>22</td><td>4</td><td>0.12</td><td>0.07</td><td>(1)</td><td>(21)</td><td>0.01</td><td>0.02</td><td>-</td><td>0.12</td></tr><tr><td>Stern_Brocot_b4</td><td>42</td><td>26</td><td>5.4</td><td>0.08</td><td>(1)</td><td>(63)</td><td>0.02</td><td>0.11</td><td>-</td><td>0.22</td></tr><tr><td>Dilcher_Stolarsky</td><td>42</td><td>4</td><td>0.09</td><td>0.07</td><td>(2)</td><td>(27)</td><td>0.04</td><td>0.08</td><td>0.02</td><td>0.23</td></tr><tr><td>Katz_Linden</td><td>24</td><td>14</td><td>2.1</td><td>0.12</td><td>(0,1,0,0)</td><td>(-,69,-,-)</td><td>0.06</td><td>0.39</td><td>-</td><td>0.57</td></tr><tr><td>Adamczewski_Faverjon</td><td>34</td><td>258</td><td>543</td><td>0.16</td><td>(4)</td><td>(163)</td><td>0.32</td><td>1.8</td><td>0.05</td><td>2.4</td></tr><tr><td>lclm_3rat_1log</td><td>33</td><td>121</td><td>203</td><td>0.08</td><td>(3)</td><td>(140)</td><td>0.16</td><td>2.5</td><td>0.03</td><td>2.9</td></tr><tr><td>lclm_3rat_2log</td><td>33</td><td>122</td><td>215</td><td>0.09</td><td>(2,1)</td><td>(88,52)</td><td>0.07</td><td>0.51</td><td>-</td><td>0.71</td></tr><tr><td>lclm_2rat_trunc_sl0</td><td>24</td><td>56</td><td>490</td><td>0.11</td><td>(4)</td><td>(294)</td><td>2.6</td><td>12</td><td>0.05</td><td>14</td></tr><tr><td>lclm_2rat_trunc_sl1</td><td>24</td><td>61</td><td>828</td><td>0.12</td><td>(4)</td><td>(519)</td><td>13</td><td>104</td><td>0.05</td><td>117</td></tr><tr><td>lclm_3rat_trunc_sl1</td><td>35</td><td>1260</td><td>&gt;12 hr</td><td>0.49</td><td>(3,2)</td><td>(574,268)</td><td>11</td><td>51</td><td>0.07</td><td>63</td></tr><tr><td>lclm_4pow_b2</td><td>27</td><td>107</td><td>25351</td><td>0.20</td><td>(1,4)</td><td>(429,739)</td><td>0.16</td><td>2.4</td><td>-</td><td>2.8</td></tr><tr><td>lclm_4pow_b3</td><td>36</td><td>727</td><td>&gt;12 hr</td><td>0.56</td><td>(1,4)</td><td>(108,174)</td><td>0.47</td><td>0.64</td><td>-</td><td>1.7</td></tr><tr><td>lclm_4pow_b4</td><td>45</td><td>989</td><td>&gt;12 hr</td><td>0.23</td><td>(4)</td><td>(223)</td><td>0.40</td><td>0.59</td><td>-</td><td>1.4</td></tr><tr><td>lclm_4pow_b5</td><td>55</td><td>3103</td><td>&gt;12 hr</td><td>2.0</td><td>(1,4)</td><td>(44,289)</td><td>2.8</td><td>0.94</td><td>-</td><td>5.9</td></tr><tr><td>lclm_5pow_b4</td><td>47</td><td>17270</td><td>&gt;60 GB</td><td>39</td><td>(1,5)</td><td>(274,1326)</td><td>64</td><td>6.5</td><td>-</td><td>115</td></tr><tr><td>dft_Baum_Sweet</td><td>42</td><td>6</td><td>0.10</td><td>0.08</td><td>(2)</td><td>(77)</td><td>0.06</td><td>0.18</td><td>0.02</td><td>0.37</td></tr><tr><td>dft_Rudin_Shapiro</td><td>42</td><td>7</td><td>5.8</td><td>0.06</td><td>(1,0)</td><td>(88,-)</td><td>0.03</td><td>0.15</td><td>-</td><td>0.25</td></tr><tr><td>dft_Stern_Brocot_b2</td><td>42</td><td>24</td><td>3.0</td><td>0.09</td><td>(1)</td><td>(59)</td><td>0.03</td><td>0.10</td><td>-</td><td>0.22</td></tr><tr><td>dft_no_2s_in_3_exp</td><td>42</td><td>20</td><td>9.6</td><td>0.09</td><td>(1,1)</td><td>(85,33)</td><td>0.07</td><td>0.84</td><td>-</td><td>1.0</td></tr><tr><td>dft_Dilcher_Stolarsky</td><td>162</td><td>50</td><td>3382</td><td>0.10</td><td>(2)</td><td>(666)</td><td>0.25</td><td>3.7</td><td>-</td><td>4.1</td></tr><tr><td>dft_Stern_Brocot_b4</td><td>162</td><td>348</td><td>29670</td><td>0.13</td><td>(1)</td><td>(239)</td><td>0.14</td><td>2.0</td><td>-</td><td>2.4</td></tr><tr><td>rmo_2_1</td><td>23</td><td>19</td><td>5.3</td><td>0.07</td><td>(3)</td><td>(263)</td><td>1.1</td><td>23853</td><td>0.03</td><td>23854</td></tr><tr><td>rmo_3_1</td><td>33</td><td>37</td><td>14</td><td>0.07</td><td>(3)</td><td>(133)</td><td>0.22</td><td>1166</td><td>0.03</td><td>1167</td></tr><tr><td>rmo_2_2</td><td>23</td><td>44</td><td>15</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_3_2</td><td>33</td><td>82</td><td>39</td><td>0.08</td><td>(3)</td><td>(247)</td><td>2.6</td><td>11031</td><td>0.03</td><td>11034</td></tr><tr><td>rmo_2_3</td><td>23</td><td>69</td><td>26</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_3_3</td><td>33</td><td>127</td><td>70</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_2_4</td><td>23</td><td>94</td><td>41</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_3_4</td><td>33</td><td>172</td><td>109</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_2_5</td><td>23</td><td>119</td><td>58</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr><tr><td>rmo_3_5</td><td>33</td><td>217</td><td>166</td><td></td><td></td><td></td><td></td><td></td><td></td><td>&gt;12 hr</td></tr></tbody></table>

to a calculation be smaller (that is, the value 57 of 'tpl' is smaller than 864), we expect that many more pairs are used over $\overline{Q}$.

Table 4 compares the improved Mahler analogue of Petkovšek's method by Algorithm 3 over $L = Q$ with the Hermite-Padé approach by Algorithm 4 (which by design is necessarily over $\overline{Q}$). Even though Algorithm 4 computes a more complete solution set, it is by far the faster algorithm, at least if we
* 'tot' is the total time for ramified rational solving using the improved Mahler analogue of Petkovšek's approach (IP) or the Hermite-Padé approach (HP).

* 'fst' is the time for a first series computation, sufficient to determine the dimensions of series-solutions spaces behind the various logarithmic parts in solutions, provided in the column 'dim'.

* 'dim' is a list, indexed by the $\lambda \in \Lambda$, of the dimension of series appearing in front of $(\ln x)^{\log_b \lambda}$ in solutions.

* 'σ' is a list with same indexing of the last value of $\sigma$ used to find the hypergeometric series solutions of $L_\lambda$ (or '-' when the dimension for $\lambda$ is 0).

* 'rfn' is the cumulative time over $\lambda$ for all refined series computations up to the corresponding final approximation orders in 'σ'.

* 'syz' is the total time for computing minimal bases.

* 'sng' is the cumulative time over $\lambda$ for all prime decompositions computed by calling Singular, or '-' if no prime decomposition was needed for the operator $L$.

<caption>Table 5: Meaning of the columns in Table 4.</caption>

exclude the special examples $rmo\_b\_\delta$. Recognizing and extracting the subset of solutions in $\mathbb{Q}$ from the complete solution set in $\overline{\mathbb{Q}}$ could be done easily, so solving the Riccati equation over $\mathbb{L} = \mathbb{Q}$ reduces to solving it over $\mathbb{L} = \overline{\mathbb{Q}}$: this makes Algorithm 4 be the better algorithm. For longer calculations, speedups of Algorithm 4 over Algorithm 3 can be very high (e.g., Adamczewski_Faverjon, dft_Dilcher_Stolarsky, dft_Stern_Brocot_b4).

Examples $rmo\_b\_\delta$ were constructed in Example 10.9 to have solutions in $\mathbb{Q}(x)$ and show a situation where Algorithm 4 fails: for example, for $rmo\_3\_3$, the polynomials $\ell_0$ and $\ell_3$ have few factors but factors of large degrees; specifically, they have the following factorization patterns:

$$ \ell_0 = x^{10}(x^3 + \dots)(x^{21} + \dots)(x^{93} + \dots), \quad \ell_3 = (x^{27} + \dots)(x^{31} + \dots)(x^{69} + \dots). $$

This makes Algorithms 1 and 3 iterate over few pairs $(A, B)$. In contrast, even if the degree bound (equations (5.1) and (5.2)) and the induced $\sigma$ needed in Algorithm 4 are not too large, of the order of a few hundreds, the sequences of coefficients of the series solutions are not automatic (see §10.2.1) and involve very large numbers, which dramatically slows down the calculation.

## 11. Differential transcendence of Mahler functions

This section shows an application of algorithms for solving the Riccati Mahler equation for its solutions that are rational functions. It uses such algorithms as a black box and is otherwise completely independent from the rest of the text.

Mahler equations originate in number theory, where they were introduced by Mahler as he developed his eponymous method to construct new transcendental
numbers; see (Adamczewski 2017) for a recent survey. Consider again the linear
Mahler equation (L), this time with $K = \mathbb{Q}$, as well as some series solution
$f \in \overline{\mathbb{Q}}[[x]]$. It is classical (Nishioka 1996) that $f$ has a positive radius of
convergence, that it can be extended to a meromorphic function on the open
unit disk, and that except if it is rational, it has a natural boundary on the unit
circle and is therefore transcendental.

Concerning values of $f$, Philippon (2015) proved that for all $\alpha \in \overline{\mathbb{Q}}$ satisfying $|\alpha| < 1$ and such that $\alpha^{b^N}$ does not intersect the zero set of $\ell_0\ell_r$, the algebraic relations between $f(\alpha), \dots, f(\alpha^{b^{r-1}})$ over $\overline{\mathbb{Q}}$ are specialization to $x = \alpha$ of algebraic relations between the functions $f, \dots, M^{r-1}f$ over $\overline{\mathbb{Q}}(x)$. Therefore, if the latter functions have no algebraic relations, their values at most algebraic points are algebraically independent. As similar statement is known as the Hermite–Lindermann theorem, which states that for any nonzero algebraic number $\alpha$, the value $\exp(\alpha)$ of the exponential function is transcendental, and of its generalization to $E$-functions; see (Beukers 2006) for a modern treatment.

Let $\partial$ denote the derivation with respect to $x$. The algebraic relations between $f(\alpha), \dots, \partial^n f(\alpha)$ can be studied by the same approach, at least for convenient $\alpha \in \overline{\mathbb{Q}}$ (Adamczewski, Dreyfus, and Hardouin 2021, Theorem 1.5). The result is that such relations come from specializations of algebraic relations between $f$ and its derivatives.

The question of algebraic relations between values therefore motivates the question of determining whether $f$ is differentially transcendental (Definition 11.1) and more generally whether $f$ and its iterates under $M$ are differentially algebraically independent. Several results based on difference Galois theory have been developed, leading to effective criteria. We summarize this now.

**Definition 11.1.** Let $f, f_1, \dots, f_m$ be series in $\overline{\mathbb{Q}}[[x]]$.

We say that $f$ is differentially algebraic when there exist $n \in \mathbb{N}$ and a nonzero $P \in \overline{\mathbb{Q}}[x][X_0, \dots, X_n]$ such that $P(f, \partial f, \dots, \partial^n f) = 0$. We say that $f$ is differentially transcendental otherwise.

We say that $(f_1, \dots, f_m)$ is differentially algebraically dependent when there
$\exists n \in \mathbb{N}$ and a nonzero $P \in \overline{\mathbb{Q}}[x] [(X_{i,j})_{1 \le i \le m, 0 \le j \le n}]$ such that

$$
P(f_1, \partial f_1, \dots, \partial^n f_1, \dots, f_m, \partial f_m, \dots, \partial^n f_m) = 0.
$$

We say that $(f_1, \dots, f_m)$ is differentially algebraically independent *otherwise*.

Let $G$ denote the difference Galois group of (L). This is an algebraic group. In
a way that reinforces the dichotomy between rational and transcendental solutions
of (L), Dreyfus, Hardouin, and Roques (2018) proved that if $G$ contains $SL_r(\overline{\mathbb{Q}})$,
which implies that (L) has no nonzero rational solutions, then the nonzero
series solutions are differentially transcendental<fnref n="7" /> (not just transcendental). More
recently, Adamczewski, Dreyfus, and Hardouin (2021) proved that a solution $f$

<footnote n="7">⁷In Dreyfus, Hardouin, and Roques (2018), the series have coefficients in $\mathbb{C}$ but everything remains correct if we replace $\mathbb{C}$ by the algebraically closed field $\overline{\mathbb{Q}}$.</footnote>
is differentially transcendental unless it is a rational function $f \in \bar{\mathbb{Q}}(x)$. Thus, to prove the differential transcendence of $f$, it is sufficient to check that it is not rational. To this end, our Algorithm 9 in (CDDM 2018), or for that matter our new development in §9.2, can be used.

Concerning the differentially algebraic independence of the $M^i f$ for a Mahler function $f$ that solves (L), the best we can expect is that $(f, \dots, M^{r-1} f)$ is differentially algebraically independent, since by (L), the functions $f, \dots, M^r f$ are linearly dependent over $\bar{\mathbb{Q}}(x)$. Dreyfus, Hardouin, and Roques (2018) also proved that if (i) the difference Galois group of (L) contains $SL_r(\bar{\mathbb{Q}})$ and (ii) $\ell_0/\ell_r$, which up to sign is the determinant of the companion matrix of $L$, is a monomial, then $f, \dots, M^{r-1} f$ are differentially algebraically independent. Arreche and Singer (2017, paragraph just after the proof of Theorem 5.2)<fnref n="8" /> later explained how the assumption on $\ell_0/\ell_r$ can be avoided.

For general $r$, the previous criteria based on testing the inclusion of $SL_r(\bar{\mathbb{Q}})$ into $G$ are not practical: although an algorithm exists for computing the difference Galois group (Feng 2018), it is too theoretical to work in practice. When $r = 2$, an efficient, specialized criterion for the inclusion can be formulated in terms of solutions of Riccati equations. This is provided by the following theorem, whose proof is implicit in (Roques 2018).

**Theorem 11.2** (Roques (2018, §6)). For $r = 2$, assume the existence of a nonzero solution $f \in \bar{\mathbb{Q}}[[x]]$ of (L). Assume further the condition $\ell_1 \neq 0$. Then, the difference Galois group of (L) contains $SL_2(\bar{\mathbb{Q}})$ if and only if neither of the equations

$$ \ell_2 u M u + \ell_1 u + \ell_0 = 0, \quad (11.1) $$

$$ u M^2 u + \left( M^2 \left( \frac{\ell_0}{\ell_1} \right) - M \left( \frac{\ell_1}{\ell_2} \right) + \frac{\ell_2}{\ell_1} M \left( \frac{\ell_0}{\ell_2} \right) \right) u + \frac{\ell_2 \ell_0 M \ell_0}{\ell_1^2 M \ell_1} = 0 \quad (11.2) $$

has any solution in $\bar{\mathbb{Q}}(x^{1/*})$.

*Proof.* Again, let $G$ denote the difference Galois group of (L), and let $G^0$ be the connected component of the identity in $G$. Lemma 40 in (Roques 2018) shows that (11.1) has no solution if and only if $G$ is irreducible. Theorem 42 in the same reference, where our $\ell_1$ is denoted $a$, then shows that, if (11.1) has no solution and $\ell_1 \neq 0$, then (11.2) has no solution if and only if $G$ is not imprimitive. By (Roques 2018, Theorem 4), which is a direct transposition of (van der Put and Singer 1997, Prop. 1.20), $G/G^0$ is finite and cyclic<fnref n="9" />. The classical classification of algebraic groups then finishes the proof. $\square$

*Remark 11.3.* The condition on $\ell_1$ is no major restriction: if $\ell_1 = 0$, (L) is first-order with respect to the Mahler operator with respect to the radix $b^2$, and

<footnote n="8">⁸We are indebted to an anonymous reviewer for pointing us to (Arreche and Singer 2017). This allowed us to prove the algebraic independence of $f$ and $Mf$ for all six natural examples considered in the article, instead of just three as in our earlier draft.</footnote>

<footnote n="9">⁹In both references, “cyclic” means “finite and cyclic”.</footnote>
the rationality of $f$ can be studied directly. It is also worth mentioning that (11.2) can be viewed as a Riccati equation in radix $b^2$.

The Galoisian criterion in (Arreche and Singer 2017) and the previous theorem straightforwardly combine into the following corollary.

**Corollary 11.4.** For $r = 2$, assume the existence of a nonzero solution $f \in \bar{\mathbb{Q}}[[x]]$ of (L). Assume further the condition $\ell_1 \neq 0$ and that (11.1) and (11.2) have no solutions in $\bar{\mathbb{Q}}(x^{1/*})$. Then, $f$ and $Mf$ are differentially algebraically independent, and in particular $f$ is differentially transcendental.

We tested our implementation on the six equations of order $r = 2$ appearing in Example 1.1 or in §10.2: Baum_Sweet, Rudin_Shapiro, Stern_Brocot_b2, Stern_Brocot_b4, no_2s_in_3_exp, and Dilcher_Stolarsky. Algorithm 4 established that the hypothesis of Corollary 11.4 is satisfied for all six in a total of 8.4 seconds: a total of 1.0 seconds for (11.1); a total of 8.3 seconds for (11.2). In the worst case, solving of (11.2) takes 18 times as long as the solving of (11.1). We also executed Algorithm 3, which could also handle all six equations, in much more time (9.4 hours in total). The application of Corollary 11.4 therefore proves the differential algebraic independence of $\{f, Mf\}$ in the six cases.

For the examples Baum_Sweet and Rudin_Shapiro, we recover the results of differential algebraic independence obtained by Dreyfus, Hardouin, and Roques (2018) when they combined their criterion with the determination of the difference Galois groups of those examples by Roques (2018). To the best of our knowledge, the results for the other examples are new and were not easily accessible by hand calculations: for instance, the degree $d = 50$ and the radix $b = 16$ of the equation (11.2) for the example Dilcher_Stolarsky would lead to arduous calculations.

## Acknowledgements

We would like to express our sincere gratitude to the reviewers for their constructive feedback and valuable suggestions, which have greatly contributed to improving the presentation and clarity of this article.

## References

Abramov, Sergei A., Peter Paule, and Marko Petkovšek (1998). “q-Hypergeometric solutions of q-difference equations”. In: Discrete Math. Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics 180.1, pp. 3–22. DOI: 10.1016/S0012-365X(97)00106-4.

Abramov, Sergei A. and Marko Petkovšek (1995). “Finding all q-hypergeometric solutions of q-difference equations”. In: Proc. of FPSAC’95.

Adamczewski, Boris (2017). “Mahler’s method”. In: Doc. Math. Extra Vol. Mahler Selecta, pp. 95–122. DOI: 10.25537/dm.2019.SB-95-122.
Adamczewski, Boris, Thomas Dreyfus, and Charlotte Hardouin (2021). “Hyper-
transcendence and linear difference equations”. In: *J. Amer. Math. Soc.* 34.2,
pp. 475–503. DOI: 10.1090/jams/960.

Adamczewski, Boris and Colin Faverjon (2017). “Méthode de Mahler : relations linéaires, transcendance et applications aux nombres automatiques”. In: *Proc. Lond. Math. Soc. (3)* 115.1, pp. 55–90. DOI: 10.1112/plms.12038.

Allouche, Jean-Paul (1987). “Automates finis en théorie des nombres”. In: *Expo-
sition. Math.* 5.3, pp. 239–266.

Allouche, Jean-Paul and Jeffrey Shallit (1992). “The ring of k-regular sequences”. In: *Theoret. Comput. Sci.* 98.2, pp. 163–197.

Arreche, Carlos E. and Michael F. Singer (2017). “Galois groups for integrable and projectively integrable linear difference equations”. In: *J. Algebra* 480, pp. 423–449. DOI: 10.1016/j.jalgebra.2017.02.032.

Becker, Thomas and Volker Weispfenning (1993). *Gröbner Bases*. Springer New York. DOI: 10.1007/978-1-4612-0913-3.

Beckermann, Bernhard and George Labahn (1994). “A uniform approach for the fast computation of matrix-type Padé approximants”. In: *SIAM J. Matrix Anal. Appl.* 15.3, pp. 804–823. DOI: 10.1137/s0895479892230031.

— (2000). “Fraction-free computation of matrix rational interpolants and matrix GCDs”. In: *SIAM J. Matrix Anal. Appl.* 22.1, pp. 114–144. DOI: 10.1137/s0895479897326912.

Beke, Emanuel (1894). “Die Irreducibilität der homogenen linearen Differential-
gleichungen”. In: *Mathematische Annalen* 45.2, pp. 278–294.

Bell, Jason P. and Michael Coons (2017). “Transcendence tests for Mahler
functions”. In: *Proc. Amer. Math. Soc.* 145.3, pp. 1061–1070.

Bendixson, Ivar (1892). “Sur les équations différentielles linéaires homogènes”. In: *Öfversigt af Kongliga Vetenskaps-Akademiens Förhandlingar* 49, pp. 91–105.

Beukers, F. (2006). “A refined version of the Siegel-Shidlovskii theorem”. In: *Ann. of Math. (2)* 163.1, pp. 369–379. DOI: 10.4007/annals.2006.163.369.

Bostan, Alin, Tanguy Rivoal, and Bruno Salvy (2024). “Minimization of differen-
tial equations and algebraic values of E-functions”. In: *Math. Comp.* 93.347,
pp. 1427–1472. DOI: 10.1090/mcom/3912.

Bronstein, Manuel and Thom Mulders (n.d. [1999?]). *Rational heuristics for rational solutions of Riccati equations*. URL: https://citeseerx.ist.psu.edu/pdf/3ef0af0b941a70cb2b68cd6bf2ec93b3c0859cc8.

Bronstein, Manuel and Marko Petkovšek (1993). *On Ore rings, linear operators and factorisation*. Tech. rep. ETH Zurich, p. 19. DOI: 10.3929/ETHZ-A-000915149.

Christol, Gilles, Tetalo Kamae, Michel Mendès France, and Gérard Rauzy (1980). “Suites algébriques, automates et substitutions”. In: *Bull. Soc. Math. France* 108.4, pp. 401–419.

Chyzak, Frédéric, Thomas Dreyfus, Philippe Dumas, and Marc Mezzarobba
(2018). “Computing solutions of linear Mahler equations”. In: *Math. Comp.*
87.314, pp. 2977–3021.
Cluzeau, Thomas and Mark Van Hoeij (2004). "A modular algorithm for computing the exponential solutions of a linear differential operator". In: *J. Symbolic Comput.* 38.3, pp. 1043–1076.

Cohn, Richard M. (1965). *Difference algebra*. Vol. 17. Interscience tracts in pure and applied mathematics. John Wiley and Sons.

Cox, David A., John Little, and Donal O'Shea (May 13, 2015). *Ideals, Varieties, and Algorithms*. Springer-Verlag. URL: https://www.ebook.de/de/product/23693438/david_a_cox_john_little_donal_o_shea_ideals_varieties_and_algorithms.html.

Decker, Wolfram, Gert-Martin Greuel, and Gerhard Pfister (1999). "Primary Decomposition: Algorithms and Comparisons". In: *Algorithmic Algebra and Number Theory*. Ed. by B. Heinrich Matzat, Gert-Martin Greuel, and Gerhard Hiss. Springer, pp. 187–220. DOI: 10.1007/978-3-642-59932-3_10.

Derksen, Harm (1994). *An algorithm to compute generalized Padé-Hermite forms*. Report 9403. Dept. of Math., Catholic University Nijmegen.

Dilcher, Karl and Kenneth B Stolarsky (2007). "A polynomial analogue to the Stern sequence". In: *Internat. J. Number Theory* 3.01, pp. 85–103.

Dreyfus, Thomas, Charlotte Hardouin, and Julien Roques (2018). "Hypertranscendence of solutions of Mahler equations". In: *J. Eur. Math. Soc.* 20, pp. 2209–2238.

Dumas, Philippe (1993). "Récurrences maHLériennes, suites automatiques, études asymptotiques". PhD thesis. Université Bordeaux I.

Fabry, Eugène (1885). "Sur les intégrales des équations différentielles linéaires à coefficients rationnels". PhD thesis. Faculté des sciences de Paris. URL: http://patrimoine.sorbonne-universite.fr/idur1/1/3199.

Faverjon, C. and J. Roques (2024). "Hahn series and Mahler equations: algorithmic aspects". In: *J. Lond. Math. Soc. (2)* 110.1, Paper No. e12945, 60. DOI: 10.1112/jlms.12945.

Faverjon, Colin and Marina Poulet (2022). "An algorithm to recognize regular singular Mahler systems". In: *Math. Comp.* 91.338, pp. 2905–2928. DOI: 10.1090/mcom/3758.

Feng, Ruyong (2018). "On the computation of the Galois group of linear difference equations". In: *Math. Comp.* 87.310, pp. 941–965. DOI: 10.1090/mcom/3232.

Gianni, Patrizia, Barry Trager, and Gail Zacharias (1988). "Gröbner bases and primary decomposition of polynomial ideals". In: *J. Symb. Comput.* 6.2, pp. 149–167. DOI: https://doi.org/10.1016/S0747-7171(88)80040-3.

Gosper, R. William (1978). "Decision procedure for indefinite hypergeometric summation". In: *Proc. Natl. Acad. Sci. USA* 75.1, pp. 40–42. DOI: 10.1073/pnas.75.1.40.

Hendriks, Peter A. (1997). "An algorithm for computing a standard form for second-order linear *q*-difference equations". In: *J. Pure Appl. Algebra* 117-118, pp. 331–352. DOI: 10.1016/s0022-4049(97)00017-0.

— (1998). "An algorithm determining the difference Galois group of second order linear difference equations". In: *J. Symb. Comput.* 26.4, pp. 445–461. DOI: 10.1006/jsco.1998.0223.
Ibarra, Oscar H., Shlomo Moran, and Roger Hui (1982). "A generalization of the fast LUP matrix decomposition algorithm and applications". In: *J. Algorithms* 3.1, pp. 45–56. DOI: 10.1016/0196-6774(82)90007-4.

Katz, Daniel J. and Courtney M. van der Linden (2022). "Peak sidelobe level and peak crosscorrelation of Golay–Rudin–Shapiro sequences". In: *IEEE Transactions on Information Theory* 68.5, pp. 3455–3473. DOI: 10.1109/TIT.2021.3135564.

Mahler, K. (1968). "Perfect systems". In: *Compositio Math*. 19.2, pp. 95–166.

Markoff, André (1891). "Sur la théorie des équations différentielles linéaires". In: *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Paris* 113, pp. 790–791.

Neiger, Vincent (2016). "Bases of relations in one or several variables: fast algorithms and applications". PhD thesis. École normale supérieure de Lyon, France. URL: https://tel.archives-ouvertes.fr/tel-01431413.

Nishioka, Kumiko (1996). *Mahler functions and transcendence*. Vol. 1631. Lecture Notes in Mathematics. Springer Verlag, Berlin, pp. viii+185.

NIST (2010). *Digital Library of Mathematical Functions*. Ed. by F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain. Release 1.1.4. URL: http://dlmf.nist.gov/.

OEIS Foundation Inc. (2021). *The On-Line Encyclopedia of Integer Sequences*. URL: http://oeis.org.

Petkovšek, Marko (1992). "Hypergeometric solutions of linear recurrences with polynomial coefficients". In: *J. Symb. Comput*. 14, pp. 243–264.

Pflügel, Eckhard (1997). "An algorithm for computing exponential solutions of first order linear differential systems". In: *Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC'97*. ACM Press, pp. 164–171. DOI: 10.1145/258726.258773.

Philippon, Patrice (2015). "Groupes de Galois et nombres automatiques". In: *J. London Math. Soc*. 92.3, pp. 596–614.

van der Put, Marius and Michael F. Singer (1997). *Galois theory of difference equations*. Springer.

— (2003). *Galois theory of linear differential equations*. Vol. 328. Grundlehren der mathematischen Wissenschaften. Springer. URL: http://www4.ncsu.edu/~singer/papers/dbook2.ps.

Roques, Julien (2018). "On the algebraic relations between Mahler functions". In: *Trans. Amer. Math. Soc*. 370.1, pp. 321–355.

— (2023). "Frobenius method for Mahler equations". In: *J. Math. Soc. Japan*, pp. 1–40. DOI: 10.2969/jmsj/89258925.

Singer, Michael F. (2016). "Algebraic and algorithmic aspects of linear difference equations". In: *Galois theories of linear difference equations: an introduction* (Santa Marta, Columbia). Ed. by Charlotte Hardouin, Jacques Sauloy, and Michael F. Singer. Vol. 211. Mathematical Surveys and Monographs. Proceedings of a CIMPA research school. American Mathematical Society, pp. 1–41. DOI: https://doi.org/10.1090/surv/211.
van Hoeij, Mark (1999). "Finite singularities and hypergeometric solutions of linear recurrence equations". In: *J. Pure Appl. Algebra* 139.1, pp. 109–131.
DOI: 10.1016/S0022-4049(99)00008-0.

Wibmer, Michael (2013). *Algebraic Difference Equations*. Lecture notes. URL: https://drive.google.com/open?id=1KmEURssrRQm_L6EE35XY568XcQqwVLuR.

Zariski, Oscar and Pierre Samuel (1958). *Commutative algebra, Volume I*. The University Series in Higher Mathematics. With the cooperation of I. S. Cohen. D. Van Nostrand Co., Inc., Princeton, New Jersey, pp. xi+329.