20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Probably you already now that a permutation $\pi$ (of $\{-l,\dots,l\}$) is additive if and only if $\pi^{-1}$ is additive. $\endgroup$ – Roland Bacher Jul 11 '15 at 20:32
  • $\begingroup$ @Roland, I probably did at one point. I thank you for reminding me anyway. I encourage you to remind me of other things, as I am unsure what will prove significant. Gerhard "Seeks Many Forms Of Closure" Paseman, 2015.07.11 $\endgroup$ – Gerhard Paseman Jul 11 '15 at 22:44
  • $\begingroup$ It is probably worth pointing out explicitly that these are known as $\sigma$-permutations, see A. Kotzig and P. J. Laufer, When are permutations additive?, Amer. Math. Monthly, 85 (1978), 364-365 (quoted by Neil Sloane at the OEIS link above). They are very special cases of complete mappings mod $k$, i.e. mappings $f:\Bbb{Z}_k\to\Bbb{Z}_k$ such that both $f$ and $g: x\mapsto f(x)+x$ are permutations. $\endgroup$ – Victor Protsak Oct 11 '15 at 4:55
  • $\begingroup$ @Victor, indeed in that article of Kotzig and Laufer the term $\sigma-$permutations is used. I have seen complete permutation in work of Rogers and others for a similar and related concept. I do not remember seeing $\sigma-$ permutation used elsewhere except as a direct reference to that 1978 article. Have you seen it elsewhere, and if so, where please? Gerhard "Researching Minds Want To Know" Paseman, 2015.10.10 $\endgroup$ – Gerhard Paseman Oct 11 '15 at 5:07
  • $\begingroup$ No, I am only familiar with complete mappings/permutations, which are considerably more general (everything mod $k$). $\endgroup$ – Victor Protsak Oct 11 '15 at 23:32
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It seems that one reference is arxiv.org/abs/0911.2384 on Honeycomb arrays. I would appreciate learning more, as I think question 4) still has not been answered regarding enumeration. Gerhard "Still Learning This Internet Thing" Paseman, 2015.07.12 $\endgroup$ – Gerhard Paseman Jul 13 '15 at 1:00
  • $\begingroup$ Indeed, Golomb and Taylor in dealing with a more specific construct (hexagonal arrays) have considered this bijection and related problems, and refer to an older paper. Although I would appreciate other references answering 3) or 4), I still hope for more attempts at enumeration. Gerhard "Just Asking For The World" Paseman, 2015.07.13 $\endgroup$ – Gerhard Paseman Jul 13 '15 at 17:02
  • $\begingroup$ I found the Bennett and Potts reference online, and they have effectively answered 3) and 4), except for the enumeration bit. I still think this approach deserves further reflection, but I am not first on the scene. There are connections to Costas arrays and other combinatorics to. Also, I haven't verified my "payoff" yet, so I may have to retract. Gerhard "Will Make The Computer Count" Paseman, 2015.07.14 $\endgroup$ – Gerhard Paseman Jul 14 '15 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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