Problem ContributionArnold Mathematical Journal

Received: 19 November 2017 / Accepted: 11 January 2018

Modular Periodicity of the Euler Numbers and a Sequence by Arnold
Unité de Mathématiques Pures et Appliquées
École normale supérieure de Lyon
46 allée d'Italie, 69364, Lyon Cedex 07, France
sanjay.ramassamy@ens-lyon.fr
###### Abstract
For any positive integer $q$, the sequence of the Euler up/down numbers reduced modulo $q$ was proved to be ultimately periodic by Knuth and Buckholtz. Based on computer simulations, we state for each value of $q$ precise conjectures for the minimal period and for the position at which the sequence starts being periodic. When $q$ is a power of $2$, a sequence defined by Arnold appears, and we formulate a conjecture for a simple computation of this sequence.
###### Keywords
Euler numbers, Entringer numbers, Modular periodicity

## 1. Introduction

The sequence of Euler up/down numbers $(E_n)_{n\geq0}$ is the sequence with exponential generating series

 $$\sum_{n=0}^{\infty} \frac{E_n}{n!} x^n = \sec x + \tan x.$$ (1)
It is referenced as sequence A000111 in the On-Line Encyclopedia of Integer Sequences (Sloane [Sloane2017]) and its first terms are \begin{eqnarray*} 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765,\ldots \end{eqnarray*} The numbers $E_n$ were shown by [André1879] to count up/down permutations on $n$ elements (see Sect. 3). [Knuth and Buckholtz1967] proved that for any integer $q\geq1$, the sequence $(E_n \mod q)_{n\geq 0}$ is ultimately periodic. For any $q \geq 1$ we define:
• $s(q)$ to be the minimum number of terms one needs to delete from the sequence $(E_n \mod q)_{n \geq 0}$ to make it periodic;
• $d(q)$ to be the smallest period of the sequence $(E_n \mod q)_{n \geq s(q)}$.
For example, the sequence $(E_n \mod 3)$ starts with \begin{eqnarray*} 1,1,1,2,2,1,1,2,2,1,1,2,2,\ldots \end{eqnarray*} so one might expect to have $s(3)=1$ and $d(3)=4$. Clearly $s(1)=0$ and $d(1)=1$. In the remainder of this paper, we formulate precise conjectures for the values of $s(q)$ and $d(q)$ for any $q\geq2$. Organisation of the paper In Sect. 2 we reduce the problem to the case when $q$ is a prime power and we conjecture the values of $s(q)$ and $d(q)$ when $q$ is an odd prime power. In Sect. 3 we conjecture the values of $s(q)$ and $d(q)$ when $q$ is a power of $2$, after having introduced the Entringer numbers and a sequence defined by Arnold describing the $2$-adic valuation of the Entringer numbers. In Sect. 4, we provide a simple construction which conjecturally yields the Arnold sequence.

## 2. Case When $q$ is Not a Power of $2$

The following lemma implies that it suffices to know the values of $s(q)$ and $d(q)$ when $q$ is a prime power in order to know the values of $s(q)$ and $d(q)$ for any $q \geq 2$.

###### Lemma 1.
Fix $q \geq 2$ and write its prime number decomposition as
 $$q=\prod_{i=1}^k p_i^{\alpha_i},$$ (2)
where $k\geq1,$ $p_1,\ldots,p_k$ are distinct prime numbers and $\alpha_1,\ldots,\alpha_k$ are positive integers. Then
 $$s(q)=\max_{1 \leq i \leq k} s(p_i^{\alpha_i})$$ (3)
 $$d(q)=\lcm (d(p_1^{\alpha_1}),\ldots,d(p_k^{\alpha_k})).$$ (4)

The proof is elementary and uses the Chinese remainder theorem.

When $q$ is an odd prime power, [Knuth and Buckholtz1967] found the following:

###### Theorem 2.
([Knuth and Buckholtz1967]) Let $p$ be an odd prime number.
1. (1) If $p \equiv 1 \mod 4,$ then \begin{eqnarray*} d(p)=p-1. \end{eqnarray*}
2. (2) If $p \equiv 3 \mod 4,$ then \begin{eqnarray*} d(p)=2p-2. \end{eqnarray*}
3. (3) For any $k\geq1,$ \begin{eqnarray*} s(p^k)\leq k. \end{eqnarray*}
4. (4) For any $k\geq 2,$ \begin{eqnarray*} d(p^k) | p^{k-1} d(p). \end{eqnarray*}

We conjecture the following for the exact values of $s(q)$ and $d(q)$ when $q$ is an odd prime power:

###### Conjecture 1.
Let $p$ be an odd prime number.
1. (1) For any $k\geq1,$ \begin{eqnarray*} s(p^k)=k. \end{eqnarray*}
2. (2) For any $k\geq 2,$ \begin{eqnarray*} d(p^k)=p^{k-1} d(p). \end{eqnarray*}

Conjecture 1 is supported by Mathematica simulations done for all odd prime powers $q< 1000$.

## 3. Entringer Numbers and Case When $q$ is a Power of $2$

Formulating a conjecture analogous to Conjecture 1 for powers of $2$ requires to define, following [Arnold1991], a sequence describing the behavior of the $2$-adic valuation of the Entringer numbers.

### 3.1. The Seidel–Entringer–Arnold Triangle

The Entringer numbers are a refined version of the Euler numbers, enumerating some subsets of up/down permutations. For any $n\geq0$, a permutation $\sigma\in\calS_n$ is called up/down if for any $2\leq i \leq n$, we have $\sigma(i-1)< \sigma(i)$ (resp. $\sigma(i-1)> \sigma(i)$) if $i$ is even (resp. $i$ is odd). [André1879] showed that the number of up/down permutations on $n$ elements is $E_n$. For any $1 \leq i \leq n$, the Entringer number $e_{n,i}$ is defined to be the number of up/down permutations $\sigma\in\calS_n$ such that $\sigma(n)=i$. The Entringer numbers are usually displayed in a triangular array called the Seidel–Entringer–Arnold triangle, where the numbers $(e_{n,i})_{1 \leq i\leq n}$ appear from left to right on the $n$-th line (see Fig. 1).

The Entringer numbers can be computed using the following recurrence formula (see for example [Stanley2012]). For any $n\geq2$ and for any $1\leq i \leq n$, we have

 $$e_{n,i}= \begin{cases} \sum_{j< i} e_{n-1,j} &\text{if n is even} \\ \sum_{j\geq i} e_{n-1,j} &\text{if n is odd}. \end{cases}$$ (5)

### 3.2. Arnold's Sequence

Replacing each entry of the Seidel–Entringer–Arnold triangle by its $2$-adic valuation, we obtain an infinite triangle denoted by $T$ (see Fig. 2).

We read this triangle $T$ diagonal by diagonal, with diagonals parallel to the left boundary. For any $i\geq1$, denote by $D_i$ the $i$-th diagonal of the triangle $T$ parallel to the left boundary. For example $D_1$ starts with $0,\infty,0,\infty,0,\ldots$ For any $i\geq1$, denote by $m_i$ the minimum entry of diagonal $D_i$. [Arnold1991] observed that the further away one moves from the left boundary, the higher the $2$-adic valuation of the Entringer numbers becomes. In particular, he observed (without proof) that the sequence $(m_i)_{i\geq1}$ was weakly increasing to infinity. He defined the following sequence: for any $k \geq 1$, \begin{eqnarray*} u_k:=\max \left\{i\geq1 | m_i < k \right\}. \end{eqnarray*} In other words, $u_k$ is the number of diagonals containing at least one entry that is not zero modulo $2^k$. The sequence $(u_k)_{k\geq1}$ is referenced as the sequence A108039 in the On-Line Encyclopedia of Integer Sequences ([Sloane2017]) and its first few terms are given in Table 1.

Table 1 The first few values of $u_k$ .
 $k$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 $u_k$ 2 4 4 4 8 8 8 8 10 12 12 16 16 16 16 16 18 20 BorderB

Note that the first few terms given by Arnold were incorrect, because the entry $4$ appeared four times, whereas it should be appearing only three times. We also remark that we cannot define any sequence analogous to $(u_k)$ when studying the $p$-adic valuations of the Entringer numbers for odd primes $p$. Indeed, the $p$-adic valuation $0$ seems to appear in diagonals of arbitrarily high index.

### 3.3. Case When $q$ is a Power of $2$

Using the sequence $(u_k)_{k\geq1}$, we formulate the following conjecture for $s(q)$ and $d(q)$ when $q$ is a power of $2$:

###### Conjecture 2.
For any $k\geq 1,$ we have
 $$s(2^k)=u_k.$$ (6)
Furthermore$,$ if $k\geq1$ and $k\neq2,$ we have
 $$d(2^k)= 2^k.$$ (7)
Finally$,$ we have $d(4)=2$.

Numerical simulations performed on Mathematica for $k\leq 12$ support Conjecture 2.

## 4. Construction of Arnold's Sequence

In this section we provide a construction which conjecturally yields Arnold's sequence $(u_k)_{k\geq1}$.

We denote by $\Z_+$ the set of nonnegative integers and we denote by \begin{eqnarray*} S:=\bigsqcup_{d\geq1}\Z_+^d \end{eqnarray*} the set of all finite sequences of nonnegative integers. We define a map $f\colon S\rightarrow S$, which maps each $\Z_+^d$ to $\Z_+^{2d}$, as follows. Fix $\underline{x}=(x_1,\ldots,x_d)\in S$. If all the $x_i$'s are equal to $x_d$, we set \begin{eqnarray*} f(\underline{x})=(x_d,\ldots,x_d,2x_d,\ldots,2x_d), \end{eqnarray*} where $x_d$ and $2x_d$ both appear $d$ times on the right-hand side. Otherwise, define \begin{eqnarray*} s:=\max \left\{ 1 \leq i \leq d-1 | x_i \neq x_d \right\} \end{eqnarray*} and set \begin{eqnarray*} f(\underline{x})=(x_1,\ldots,x_d,x_1+x_d,\ldots,x_{s-1}+x_d,2x_d,\ldots,2x_d), \end{eqnarray*} where $2x_d$ appears $d-s+1$ times on the right-hand side. For example, we have

 $$f((2,4,4,4))=(2,4,4,4,8,8,8,8)$$ (8)
and
 $$f((2,4,4,4,8,8,8,8))=(2,4,4,4,8,8,8,8,10,12,12,16,16,16,16,16).$$ (9)
By iterating this function $f$ indefinitely, one produces an infinite sequence:
###### Lemma 3.
Fix $d\geq1$ and $\underline{x}\in\Z_+^d$. There exists a unique $($infinite$)$ sequence $(X_k)_{k\geq 1}$ such that for any $k\geq1$ and for any $n\geq \log_2 (k/d),$ $X_k$ is the $k$-th term of the finite sequence $f^n(\underline{x})$.

This infinite sequence is called the $f$- transform of $\underline{x}$. The lemma follows from the observation that for any $\ell\geq1$ and for any $\underline{y}\in \Z_+^\ell$, $\underline{y}$ and $f(\underline{y})$ have the same first $\ell$ terms.

We can now formulate a conjecture about the construction of the sequence $(u_k)_{k\geq1}$:

###### Conjecture 3.
Arnold's sequence $(u_k)_{k\geq1}$ is the $f$-transform of the quadruple $(2,4,4,4)$.

Conjecture 3 is supported by the estimation on Mathematica of $u_k$ for every $k\leq 512$.

###### Acknowledgements.
The author acknowledges the support of the Fondation Simone et Cino Del Duca.

## References

[André1879] André, D.: Développements de sec x et de tang x. C.R. Acad. Sci. Paris 88 , 965–967 (1879)
[Arnold1991] Arnold, V.I.: Bernoulli–Euler updown numbers associated with function singularities, their combinatorics and arithmetics. Duke Math. J 63 (2), 537–555 (1991)
[Knuth and Buckholtz1967] Knuth, D.E., Buckholtz, T.J.: Computation of tangent, Euler, and Bernoulli numbers. Math. Comput. 21 (100), 663–688 (1967)
[Sloane2017] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences (2017). . Accessed 13 July 2017
[Stanley2012] Stanley, R.P.: Enumerative Combinatorics, vol 1. Cambridge Studies in Advanced Mathematics, vol. 49, 2nd edn. Cambridge University Press, Cambridge (2012)