MathJax is loading, please wait
$ \newcommand{\A}{\mathcal A} \newcommand{\M}{\mathcal M} \newcommand{\calB}{\mathcal B} \newcommand{\calC}{\mathcal C} \newcommand{\calS}{\mathcal S} \newcommand{\calZ}{\mathcal Z} \newcommand{\R}{\mathbb R} \newcommand{\N}{\mathbb N} \newcommand{\E}{\mathbb E} \newcommand{\Z}{\mathbb Z} \newcommand{\e}{\epsilon} \renewcommand{\d}{\delta} \renewcommand{\o}{\otimes} \newcommand{\ds}{\displaystyle} \newcommand{\id}[1]{\mathbbm{1}_{#1}} \newcommand{\iden}{\mathbbm{1}} \def\C{\mathcal C} \newcommand{\aver}[1]{\langle #1 \rangle} \newcommand{\onevec}{\langle \boldsymbol 1|} \newcommand{\vol}{\operatorname{vol}} \newcommand{\lcm}{\operatorname{lcm}} $
Problem ContributionArnold Mathematical Journal

Received: 19 November 2017 / Accepted: 11 January 2018

Modular Periodicity of the Euler Numbers and a Sequence by Arnold
Sanjay Ramassamy Unité de Mathématiques Pures et Appliquées
École normale supérieure de Lyon
46 allé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

\begin{equation} \sum_{n=0}^{\infty} \frac{E_n}{n!} x^n = \sec x + \tan x. \end{equation} (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 [André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
\begin{equation} q=\prod_{i=1}^k p_i^{\alpha_i}, \end{equation} (2)
where $ k\geq1,$ $ p_1,\ldots,p_k$ are distinct prime numbers and $ \alpha_1,\ldots,\alpha_k$ are positive integers. Then
\begin{equation} s(q)=\max_{1 \leq i \leq k} s(p_i^{\alpha_i}) \end{equation} (3)
\begin{equation} d(q)=\lcm (d(p_1^{\alpha_1}),\ldots,d(p_k^{\alpha_k})). \end{equation} (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). [André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).

Figure 1 First five lines of the Seidel–Entringer–Arnold triangle.

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

\begin{equation} 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} \end{equation} (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).

Figure 2 First five lines of the triangle $ T$ of $ 2$-adic valuations of the Entringer numbers.

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
\begin{equation} s(2^k)=u_k. \end{equation} (6)
Furthermore$ ,$ if $ k\geq1$ and $ k\neq2,$ we have
\begin{equation} d(2^k)= 2^k. \end{equation} (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

\begin{equation} f((2,4,4,4))=(2,4,4,4,8,8,8,8) \end{equation} (8)
and
\begin{equation} 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). \end{equation} (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

[André1879] André, D.: Dé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)