11
$\begingroup$

Motivation. My eldest son thinks the following procedure is a "perfect shuffle" for a deck of cards: Take the first card, put the second on top of it, put the 3rd below cards 2 and 1, put the 4th on top of the growing stack, the 5th below, etc.

General formulation. Let $S_k$ be the group of permutations $\pi:\{1,\ldots,k\} \to \{1,\ldots,k\}$ for any positive integer $k$. The shuffle described above can be viewed as an element of $S_{2n}$ (we work with an even number of cards). We define the "perfect shuffle" permutation $\newcommand{\s}{\text{sh}}\s_n:\{1,\ldots,2n\}\to\{1,\ldots,2n\}$ by

  • $1\mapsto n+1$,
  • $2k\mapsto n+1-k$ for $k\in\{1,\ldots,n\}$, and
  • $2k+1\mapsto n+1+k$ for $k\in \{1,\ldots,n-1\}$.

For instance, for $n=4$, the cards numbered $1,2,\ldots, 8$ get mixed to $8,6,4,2,1,3,5,7$. The order of $\text{sh}_4\in S_8$ is $4$. It turns out that the order of $\s_n$, denoted by $\text{ord}(\s_n)$ behaves quite interestingly. It appears that $\text{ord}(\s_{n}) \leq 2n$ for all $n$ (I haven't proved this), and for instance we get $\text{ord}(\s_7) = 14$ and $\text{ord}(\s_8) = 5$.

I am generally interested in the behaviour of $\text{ord}(\s_{n})$, but here is a concrete question.

We define the upper density $\mu^+(A)$ for $A\subseteq \mathbb{N}$ by $$\mu^+(A) = \lim\sup_{n\to\infty}\frac{\big|A\cap \{1,\ldots,n\}\big|}{n+1}.$$

Question. Let $M = \{n\in\mathbb{N}: \text{ord}(\s_n) = 2n\}$. What is $\mu^+(M)$?

$\endgroup$
6
  • 8
    $\begingroup$ oeis.org/A019567 $\endgroup$ May 15 at 7:32
  • 3
    $\begingroup$ That answers question 2, because we have $2^{\operatorname{ord}(\text{sh}_n)} + 1 \ge 4n + 1$, so $\operatorname{ord}(\text{sh}_n) \ge 2 + \lg n$. $\endgroup$ May 15 at 7:40
  • $\begingroup$ Thanks @PeterTaylor, will remove question 2 $\endgroup$ May 15 at 8:21
  • 7
    $\begingroup$ Congratulations to your son's rediscovery of a shuffle that Monge wrote a paper about in 1773 according to p 107 in W.W. Rouse Ball's book $\endgroup$ May 15 at 9:31
  • 3
    $\begingroup$ Thanks @ChrisWuthrich -- my son just found an inconsistency in ${\sf (ZF)}$ and will publish it before going back to afternoon school $\endgroup$ May 15 at 13:04

1 Answer 1

14
$\begingroup$

The alternate characterization given in OEIS that Peter Taylor linked to in the comments may be used to answer this question.

This number is the least $m$ such that $2^m$ is congruent to $\pm 1$ modulo $\mathbb Z/(4n+1)$. In other words, it is the order of the element $2$ in the group $(\mathbb Z/4n+1)^\times/ (\pm 1)$. The order of the element divides the order of this group which is $\phi(4n+1) /2 \leq 2n$, with equality obtained only if $\phi(4n+1) = 4n$, i.e. only if $4n+1$ is prime.

So the order is at most $2n$ and equals $2n$ only for $n$ with $4n+1$ primes (but not for all such $n$), which is a set of upper density zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.