On the existence of permutations conditioned by certain rational functions

1.   Introduction

Permutations (see, for example, [1,3]) are studied in almost every branch of mathematics and also in computer science. The number of permutations $\pi = (\pi(1), \pi(2), \ldots, \pi(n))\in \mathfrak{S}_n$ of $\{1, 2, \ldots, n\}$ is $n!$. In [4] Z.-W. Sun made several conjectures about the existence of permutations conditioned by certain rational functions. In the paper we confirm three of them by proving the following theorem.

Theorem 1. (ⅰ) For any integer $n>5$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

(ⅱ) For any integer $n>7$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

(ⅲ) For any integer $n>5$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

Since $n!$ is a huge number for large $n$, the generation of all $n!$ permutations of $n$ by computer is already a challenge [2]. For this reason (1.1)-(1.3) have only been verified for very small $n$. Our proof of Theorem 1 consists of both investigation of the mathematical properties of the rational functions and brute-force attack by computer for finding certain special permutations.

Furthermore, we can fully characterize all integer values of the "inverse difference" rational function given in the left-hand side of (1.1). We define

Since $a\in V_n$ implies $-a\in V_n$ by the reverse of permutation, we only need to study the nonnegative integer values of $V_n$. For example, $n = 5$, the value set $V_5$ contains the following nonnegative rational numbers:

We see that there are three integers $1, 2, 4$ in the above list.

Theorem 2. We have $V_3 \cap \mathbb{N} = \{2\}$, $V_5 \cap \mathbb{N} = \{1, 2, 4\}$, and for $n\not = 3, 5$,

The proofs of Theorems 1 and 2 will be given in Section 2. Notice that we are still not able to prove three other conjectures of Sun. Let us reproduce them below for interested readers.

Conjecture 3. (i) [4,Conj. 4.7(ⅱ)] For any integer $n>6$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

Also, for any integer $n>7$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

(ii) [4,Conj. 4.8(ⅱ)] For any integer $n>7$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

Motivated by (1.8), we make the following conjecture.

Conjecture 4. For any integer $n>11$, there is a permutation $\pi\in \mathfrak{S}_n$ such that

Conjecture 4 has been checked for $11<n<28$ by computer. We list below the permutations satisfying (1.9), which are found by our computer program in a highly non-trivial way.

2.   Proofs

Let $\Phi_{{\rm dif}}(\pi)$, $\Phi_{{\rm cycdif}}(\pi)$, and $\Phi_{{\rm prod}}(\pi)$ denote the three rational functions expressed in the left-hand side of (1.1), (1.2), and (1.3), respectively. The following Link lemma is useful for our construction.

Lemma 5 (Link). Let $\sigma\in \mathfrak{S}_s$ and $\tau\in \mathfrak{S}_t$ be two permutations on $\{1, 2, \ldots, s\}$ and $\{1, 2, \ldots, t\}$, respectively, such that $\sigma(s) = s, \tau(1) = 1$ and $\Phi_{{\rm dif}}(\sigma) = \Phi_{{\rm dif}}(\tau) = 0$. We define the "link" of the two permutations $\rho \in \mathfrak{S}_{s+t-1}$ by

Then, we have $\Phi_{{\rm dif}}(\rho) = 0$. Furthermore, if $\tau(t) = t$, we have $\rho(s+t-1) = s+t-1$.

Proof. Notice that in the definition of $\rho$, if we allow $k = s$ in the second case, the expression will give the same definition of $\rho(s)$ as in the first case, since $\sigma(s) = s = s-1+\tau(1)$. Hence,

Furthermore, if $\tau(t) = t$, it is easy to see that $\rho(s+t-1) = s+t-1$.

Let us write the link $\rho$ of $\sigma$ and $\tau$ by $\langle \sigma, \tau\rangle$.

Example. Take $\sigma = (1, 4, 2, 5, 3, 6)$ and $\tau = (1, 3, 2, 4)$. We verify that

We have $\rho = \langle \sigma, \tau \rangle = (1, 4, 2, 5, 3, 6, 8, 7, 9)$ and

If $\tau(t) = t$, since the link $\rho = \langle \sigma, \tau \rangle$ also satisfies the conditions $\rho(s+t-1) = s+t-1$ and $\Phi(\rho) = 0$, we can "link" again and obtain $\langle \rho, \tau \rangle = \langle \langle \sigma, \tau \rangle, \tau \rangle .$

The following proposition is a slightly stronger version of Theorem 1(ⅰ) for the rational function $\Phi_{{\rm dif}}$.

Proposition 6. For any integer $n>5$, there is a permutation $\pi\in \mathfrak{S}_n$ such that $\pi(1) = 1, \pi(n) = n$, and $\Phi_{{\rm dif}}(\pi) = 0$.

Proof. Let

and $\tau = \sigma_1 = (1, 3, 2, 4)$. We have $\Phi_{{\rm dif}}(\sigma_j) = 0$ for $j = 0, 1, 2$, and $\tau(1) = 1, \tau(4) = 4$. By repeated application of the link algorithm, we obtain the following three families of permutations:

of length

Hence we have constructed one permutation $\pi\in \mathfrak{S}_n$ for each $n>5$ such that $\Phi_{{\rm dif}}(\pi) = 0$ and $\pi(1) = 1$ and $\pi(n) = n$.

The following proposition is another enhanced version of Theorem 1(ⅰ) for $\Phi_{{\rm dif}}$, which is crucial for proving Theorem 1(ⅱ) for $\Phi_{{\rm cycdif}}$. The difference between Propositions 6 and 7 lies in the value of $\pi(n)$.

Proposition 7. For any integer $n>7$, there is a permutation $\pi\in \mathfrak{S}_n$ such that $\pi(1) = 1, \pi(n) = n-1$ and $\Phi_{{\rm dif}}(\pi) = 0$.

Proof. Let

We have $\alpha_j(1) = 1$, $\alpha_j(j) = j-1$, and $\Phi_{{\rm dif}}(\alpha_j) = 0$ for $j = 8, 9, \ldots, 12$. The proposition is true for $j = 8, 9, \ldots, 12$. For $n\geq 13$ and $k = n-7\geq 6$, take the permutation $\sigma\in \mathfrak{S}_{k}$ obtained in Proposition 6, i.e., $\sigma(1) = 1, \sigma(k) = k, \Phi_{{\rm dif}}(\sigma) = 0$. Then, the link $\rho = \langle \sigma, \alpha_8\rangle$ satisfies $\rho(1) = 1, \rho(n) = n-1$ and $\Phi_{{\rm dif}}(\rho) = 0$. For example, for $n = 13$ and $k = 6$,

Hence, the proposition is true for any $n>7$.

Now we are ready to prove part (ⅱ) of Theorem 1 for the rational function $\Phi_{{\rm cycdif}}$.

Proof of Theorem 1(ii). If $n = 2k$ is even, we can easily check that the permutation

which is obtained by the concatenation of the increasing permutation of $\mathfrak{S}_k$ and the decreasing permutation of $\{j \mid k+1\leq j\leq 2k\}$, satisfies

The odd case is more complicated. First, we define

We have $\Phi_{{\rm cycdif}}(\beta_j) = 0$ for $j = 9, 11, 13$. Next, for $n = 2k+1\geq 15$, i.e., $k\geq 7$ and $m = k+1\geq 8$, by Propositions 6 and 7, there exist two permutations $\sigma\in \mathfrak{S}_{k}$ and $\sigma\in \mathfrak{S}_{m}$ such that

(ⅰ) $\sigma(1) = 1$, $\sigma(k) = k$, and $\Phi_{{\rm dif}}(\sigma) = 0$;

(ⅱ) $\tau(1) = 1$, $\tau(m) = m-1$, and $\Phi_{{\rm dif}}(\tau) = 0$.

Let $\tau'$ be the permutation of $\{j\mid k+1\leq j \leq 2k+1\}$ obtained by adding $k$ in the reverse of $\tau$:

Notice that the first and last elements of $\tau'$ are $k+\tau(m) = 2k$ and $k+\tau(1) = k+1$, respectively. Let $\rho$ be the concatenation of $\sigma$ and $\tau'$. We can verity that $\Phi_{{\rm dif}}(\tau') = -\Phi_{{\rm dif}}(\tau) = 0$ and

For example, for $n = 15$, $k = 7$ and $m = 8$, we have $\sigma = (1, 3, 2, 4, 6, 5, 7)$ and $\tau = (1, 2, 4, 8, 6, 5, 3, 7)$, so that $\tau' = (14, 10, 12, 13, 15, 11, 9, 8 )$. Our final permutation $\rho$ is the concatenation of $\sigma$ and $\tau'$:

We can check that $\Phi_{{\rm cycdif}}(\rho) = 0$.

To prove part (ⅲ) of Theorem 1 concerning the rational function $\Phi_{{\rm prod}}$, we need the following lemma. Also, it is much more convenient to describe the construction in the increasing binary trees model (see, for example, [3,p. 51], [1,p. 143]).

Lemma 8 (Insertion). Let $\sigma = \sigma(1)\sigma(2)\cdots\sigma(n-1)\in \mathfrak{S}_{n-1}$ be a permutation and $\tau\in \mathfrak{S}_n$ be the permutation obtained by insertion of the letter $n$ into $\sigma$:

Then, $\Phi_{{\rm prod}}(\sigma) = \Phi_{{\rm prod}}(\tau)$ if and only if $\sigma(j)+\sigma(j+1) = n$.

Proof. We have

Hence, $\Phi_{{\rm prod}}(\sigma) = \Phi_{{\rm prod}}(\tau)$ if and only if

i.e., $\sigma(j)+\sigma(j+1) = n$.

Now we use the insertion lemma to prove part (ⅲ) of our main theorem.

Proof of Theorem 1(iii). Let

We verify that $\Phi_{{\rm prod}}(\delta_j) = 1$ for $j = 6, 7, 8$. By insertion lemma, we define $\sigma_9$ by inserting the letter $9$ between $2$ and $7$ in $\sigma_8$:

Next, we insert $10$ in $\sigma_9$ between $6$ and $4$:

For the insertion of $11$, we have two possible positions, namely, between $(2, 9)$ and $(3, 8)$. We choose the position $(2, 9)$ and define

The crucial idea is to show that this kind of insertion can be repeatedly applied as many times as we want, starting from $\sigma_8$. Thus, we obtain the desired permutation $\sigma_n\in \mathfrak{S}_n$ for each $n\geq 8$. To understand the general pattern, we take a rather big example with $n = 32$. Our permutation $\delta_{32}$ is as follows:

which can be represented by the increasing binary tree (see, for example, [3,p. 51], [1,p. 143]) in Figure 1. We see that the nodes of the form $2k+1, 4k+2, 8k, 8k+4$ all appear in the tree structure. Hence, the insertion can be repeatedly applied to reach each $\delta_{n}$ for $n\geq 8$.

As proved in Theorem 1, for any integer $n>5$, there is a permutation $\pi\in \mathfrak{S}_n$ such that $\Phi_{{\rm dif}} (\pi) = 0$. For a permutation $\pi$, the value of $\Phi_{{\rm dif}}(\pi)$ is, a priori, a rational number. Theorem 2 provides a full characterization of the integer values of the rational function $\Phi_{{\rm dif}}$.

Proof of Theorem 2. In fact, we need to prove a stronger statement by replacing each $V_n$ in the theorem by

It is easy to see that $n-1\in V_n'$ by taking the identity permutation $(1, 2, \ldots n)$. Also, the maximal value of $\Phi_{{\rm dif}}(\pi)$ is $n-1$, so that $m\not\in V_n$ for $m\geq n$. We can check by computer for all $n\leq 6$. If $n\geq 7$, we prove by induction on $n$. First, $0\in V_n'$ by Proposition 6. Next, for $1\leq m \leq n-3$, by the induction hypothesis, there is a permutation $\tau\in \mathfrak{S}_{n-1}$ such that $\tau(n-1) = n-1$ and $\Phi_{{\rm dif}}(\tau) = m-1$. We define

We verify that $\Phi_{{\rm dif}}(\pi) = 1 + \Phi_{{\rm dif}}(\tau) = m$. Finally, for each $\sigma\in \mathfrak{S}_n$ which is not the identity permutation, we see that there exists at least one negative term in the summation (1.1). Hence $\Phi_{{\rm dif}}(\sigma)<n-2$, and $n-2\not\in V_n$.

For $n = 1, 2, \ldots$ and $k = 0, 1, \ldots, n-1$, let $\eta(n, k)$ be the number of permutations $\pi\in \mathfrak{S}_n$ satisfying

We list the first values of $\eta(n, k)$ in the following table.