# Which Digit-Permutations Preserve Divisibility?

This is a completely random question that just happened to come to mind recently and I was wondering if the MathSE community had anything to say about it.

Let $n > 1,b > 1$ be integers and consider the set $M_{n,b}$ of natural numbers whose base-$b$ representation has exactly $n$ digits including any leading zeros. Given a permutation $\varphi$ on $n$ letters and $m = m_1...m_n \in M_{n,b}$ define $\hat{\varphi}(m) = m_{\varphi(1)}...m_{\varphi(n)}$ so that $\hat{\varphi}$ permutes the digits of $m$ in accordance with $\varphi$.

For $k > 1$, define $$S(n,b,k) = \{\varphi \in S_n: \hat{\varphi}(m) \!\!\!\!\! \mod k = m \!\!\!\!\! \mod k \text{ for all } m \in M_{n,b}\}$$

Because $\varphi, \psi \in S(n,b,k)$ imply $$\hat{\varphi \circ \psi}(m)\!\!\!\!\! \mod k = \hat{\varphi} \circ \hat{\psi}(m) \!\!\!\!\! \mod k$$ $$= \hat{\varphi}(m) \!\!\!\!\! \mod k = m \!\!\!\!\! \mod k$$ and $S_n$ is finite, we see that $S(n,b,k)$ is a subgroup of $S_n$.

So my questions are:

• What are the properties of the groups $S(n,b,k)$?
• Are there any cases in which $S(n,b,k)$ is isomorphic to a known group?
• Have the groups $S(n,b,k)$ been studied before? If so, what are known properties?

There are some special cases in which the question can be answered quickly. For example, $$S(n, 10, 3) = S_n \text{ for all } n > 0$$ This can be seen by remembering that the remainder of $n$ divided by $3$ is the same as the remainder of the sum of the digits of $n$ divided by $3$ and noticing that permuting the digits does not change their sum. This can be generalized to the cases where $k$ divides $b-1$ and $n$ is arbitrary. I also imagine that a similar analysis will yield results for the case in which $k$ divides $b+1$ by recalling the test for divisibility by $11$.

Any thoughts?

-
S(n,b,b^i) = Sym(n-i), and it should be easy to get alternating groups. You might try finding formulas for small fixed k with b=10 also fixed, and n varying. It looks like a nice collection of permutation groups: not too complicated, and not too boring. – Jack Schmidt Jan 18 '12 at 1:13
@JackSchmidt Thanks. For what values of $n,b,k$ do you suspect alternating groups? – user12014 Jan 18 '12 at 2:33
Sorry, my mistake, and my correction even had a mistake. – Jack Schmidt Jan 18 '12 at 2:51

In case you want to test conjectures, I think this is actually correct GAP code:

PZZ := function( n, b, k )
local dom, res, hom;
dom := AsSet( Tuples( [0..b-1], n ) );
res := List( [0..k-1], i -> Filtered( dom, dig -> i =
Sum([1..n],j->dig[j]*b^(n-j) mod k ) mod k ) );
res := AsSet( List( res, i -> AsSet( List( i, dig ->
Position( dom, dig ) ) ) ) );
hom := ActionHomomorphism( SymmetricGroup(n), dom, Permuted );
return PreImage( hom, Stabilizer( Image( hom ), res, OnSetsSets ) );
end;


Modulo something weird working, you should (1) divide out gcd(b^oo,k) from k to see which digits need to be fixed, (2) check how many digits are in the fraction 1/k to see how often the pattern repeats to get the top portion of the wreath product, and (3) you can permute any digits in the same place mod the period of 1/k.

The code works by splitting the set dom of digits into equivalence classes res mod k (and then converting them into positions for better performance, and using hom to convert the symmetric group into this positions format), then the last line looks for those permutations that stabilize the equivalence relation. Obviously the method has runtime a function of bn and is exponential in n anyways (maybe in bn). However, it works pretty quickly for PZZ(7,3,5) for instance.

-
Thanks, this should be very useful. The code seems to work fine, I tested several cases which I also computed by hand. – user12014 Jan 18 '12 at 6:30

If $k$ divides $b^a -1$ for some $a$ [you need $k$ and $b$ coprime] then you can permute digits in equivalent positions modulo $a$.

If $k$ divides $b^a$ for some $a$ then you can permute digits in positions higher than $a$.

-
And for completeness, if $k$ divides $(b^a-1)b^c$ for some $a$ and $c$ then you can permute digits in equivalent positions modulo $a$ if they are all greater than $c$. – Henry Jan 18 '12 at 22:43

Since you need your permutations to fix the class modulo $k$ of all $n$-digit numbers, a necessary condition for having any permutation in $S(n,b,k)$ that sends position $i$ to position $j$ (numbering positions from the right starting with $0$) is that this holds for the number with a $1$ in position $i$ and $0$s in all other places: $$b^i\equiv b^j\pmod k.$$ Therefore partition the set $\{n-1,\ldots,2,1,0\}$ of all digit positions according to this equivalence relation. One can only permute positions within one equivalence class (but of course a permutation can do this for more than one class at a time). On the other hand the facts that the value in base $b$ of a digit string $d_{n-1}\ldots d_2d_1d_0$ is $\sum_{i=0}^{n-1}d_ib^i$ and that reduction modulo $k$ is a ring morphisms imply that every such permutation does indeed fix the class modulo $k$ of all $n$-digit numbers.

The group $S(n,b,k)$ is therefore the direct product of the symmetric groups of all these equivalence classes of positions, which is a Young subgroup of $S_n$.

-