Are there enough additive permutations?

Question

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other structures. As a meta question, I would like to know more references or applications for additive permutations, especially applications involving combinatorial number theory. First, the basic setup.

Let $l$ be a nonegative integer, and let $k$ stand for both the set $\{t : t$ is an integer and $ \mid t \mid \leq l \}$ and the cardinality of the set $k=2l+1$. I will represent the set of permutations $S_k$ on the set $k$ by vectors indexed by $k$ in increasing order. So for $l=2$, the identity permutation $e$ is written as $\langle -2, -1 ,0 , 1, 2 \rangle$. Let me take $\pi \in S_k$ and write it as a vector, and I will write vector addition as $++$. I can then write $e ++ \pi$ as a vector in $\mathbb{R}^k$ with $i$th coordinate being $i + \pi(i)$. This vector $e ++ \pi$ is a vector with integer coordinates, and may not look anything like a vector representation of an element of $S_k$. However, sometimes it does, and when this happens, we call $\pi$ an additive permutation.

As an example when $l=1$, one has two additive permutations $\langle 1,-1, 0 \rangle$ and $\langle 0 , 1, -1 \rangle$, each of which is the negative reverse of the other ($\pi(i) = -\rho(-i)$ for all $i \in k$). Except when $l=0$, the identity permutation $e$ is not an additive permutation. Also, the fact that $\langle 1,0, -1 \rangle$ is not an additive permutation shows that this definition depends on representation: it cannot be defined as a characteristic subset of the permutation group on $k$ members.

The OEIS entry A002047 contains some references to the literature, which I am slowly absorbing. However, I don't see the answer to either of the following questions:

• 1) Given $l$, how many members of $S_k$ are additive permutations? I have not found an asymptotic formula, although the paper by Cavenagh and Wanless suggests an exponential lower bound. I have a weak upper bound which for most $l$ is slightly better than $l^{2l}$.

• 2) Using just the group operation of the symmetric group $S_k$ (so no inverse, but $k$ is finite so inverse is not needed), do the additive permutations generate $S_k$? It seems to be so for $l=0,1,2$. (It is less interesting to me but still valid to ask for $l$ large if $S_k$ is generated using $++$.)

In addition to the OEIS references, I am perusing work of D.G. Rogers, and am open to other suggestions for references. I am also looking at a related paper, but the operation $++$ there is over a finite ring, and I don't think I can use those results yet.

Gerhard "First Question On This Account" Paseman, 2015.07.10

Answer 1

I want to share a partial answer to question 1), and raise a few more questions. I found what I think is a neat and likely unoriginal bijection; I'm hoping the combinatorialists can provide a reference and perhaps use it to help with my questions above.

I decided to try a $k$ by $k$ chessboard visualization of the enumeration problem, and succeeded, sort of. I had to cut off triangular pieces of the chessboard and ask for a maximal nonattacking and covering queen placement, except that the queens were restricted in movement relative to actual queens in chess. So I shifted that set up to a hexagonal board, and invented a (name for a likely unoriginal) piece called a "jack", which is like what a rook would be for a board of hexagonal cells (from a hexagonal cell, move in one of the 6 directions perpendicular to a side of the cell, along 3 lines which I call "diagonals"), but decided it needed to be partly royal.

Let's imagine a hexagonal array with $l+1$ cells on a side, with vertex cells at the even numbers on a clock, and for orientation label the six vertex cells A,B,C,D,E, and F in clockwise fashion. (So A is at 12, B is at 2, and D is at 6 o'clock.) Now, starting with the vertex cell E and going clockwise up to A, label (just outside the board) those cells with $-l, -l+1, \ldots$ all the way up to $l$, so that the $k$ "diagonals" from upper left to lower right are labeled with the $\pi(i)$ index. Cell F will have a $0$ label for $\pi(0)$ and cell A will have a $l$ label for $\pi(l)$. In a similar fashion, we label the other diagonals from $-l$ at Cell A clockwise through $0$ for Cell B and ending with $l$ at cell C. We have labeled these with $j$- values, which will represent values being placed in position $\pi(i)$.

If we look at a cell, it belongs to exactly two of the labeled diagonals, $\pi(i)$ and $j$ say. If we were to decorate all the cells with the value $i+j$ when it is on diagonals $\pi(i)$ and $j$, we would see constant values running up and down. In particular, the line of cells from A down to D would get the value $0$, $-l$ for the cells between (and including) cell E and F, and $l$ for cells B to C.

Once we have the observation of the values being constant on the "third" (vertical) diagonal, I can now assert the bijection. Let G be a placement of $k$ jacks on this board that do not attack each other and consequently cover all cells of the board. Since I have labeled the diagonals, I will call such a G a labeled placement.

Assertion: The number of labeled placements on this $k$ board is the same as the number of additive permutations of $S_k$.

For an additive permutation $\rho \in S_k$ place a jack at cell on diagonals $\pi(\rho(j))$ and $j$ for each $j \in k$. After I have verified the details, I will call the Assertion a Proposition. However, I don't see what could go wrong, yet.

I am willing to shorten this description if someone will provide a graphic version. Now for the payoff: Referring to the third diagonal, place a jack on the 0 diagonal somewhere in one of the $k$ cells; this will leave usually $k-3$ and at most $k-2$ uncovered cells on the 1 diagonal to place another jack, so place one there. We get an upper bound of $k!!$ placements of those $l+1$ mutually nonattacking jacks, and $l!$ trivially for the remaining $l$ jacks, giving an upper bound of $k!/2^l$ for the number of additive permutations in $S_k$.

I am still working on the lower bound, but have a feeling that $l!$ or even $(l+1)!$ might be achievable with the Assertion and this picture. Now for the additional questions:

• 3) has anyone seen this bijection before, and will they please give me a reference?

• 4) has labeled placement of nonattacking jacks on a hexagonal board appeared before, hopefully with enumeration?

• 5) assuming I did not screw up and the Assertion is soon to be a Proposition, can anyone see a good lower bound (better than exponential, and hopefully factorial) for the number of additive permutations with this or any other picture?

• 6) leaving additive permutations aside, it is tempting to view the board as a representation of a three-dimensional cubical array. Is there a combinatorial advantage to such a perspective for this problem? That is, picking $k$ cubes out of an array of $l+1$ cubes on a side, does this count or represent a nice entity in finite geometry or some other field?

I suspect that a factorial lower bound would imply improvements on the current literature. I also would not mind improvements on the upper bound.

Gerhard "Likes Looking At Suggestive Pictures" Paseman, 2015.07.12