S-Crucial and Bicrucial Permutations with Respect to Squares

Ian Gent

School of Computer Science University of St Andrews St Andrews, Fife KY16 9SX

United Kingdom

ian.gent@st-andrews.ac.uk

Sergey Kitaev

School of Computer and Information Sciences

University of Strathclyde Glasgow, G1 1HX United Kingdom

sergey.kitaev@cis.strath.ac.uk

Alexander Konovalov, Steve Linton, and Peter Nightingale School of Computer Science University of St Andrews St Andrews, Fife KY16 9SX

United Kingdom

alexander.konovalov@st-andrews.ac.uk
sl4@st-andrews.ac.uk
pwn1@st-andrews.ac.uk

Abstract

A permutation is square-free if it does not contain two consecutive factors of length two or more that are order-isomorphic. A permutation is bicrucial with respect to squares if it is square-free but any extension of it to the right or to the left by any element gives a permutation that is not square-free.

Avgustinovich et al. studied bicrucial permutations with respect to squares, and they proved that there exist bicrucial permutations of lengths 8k + 1, 8k + 5, 8k + 7 for k ≥ 1. It was left as open questions whether bicrucial permutations of even length, or such permutations of length 8k + 3 exist. In this paper, we provide an encoding of orderings which allows us, using the constraint solver Minion, to show that bicrucial permutations of even length exist, and the smallest such permutations are of length 32. To show that 32 is the minimum length in question, we establish a result on left-crucial (that is, not extendable to the left) square-free permutations which begin with three elements in monotone order. Also, we show that bicrucial permutations of length 8k+3 exist for k = 2, 3 and they do not exist for k = 1.

Further, we generalize the notions of right-crucial, left-crucial, and bicrucial permutations studied in the literature in various contexts, by introducing the notion of P -crucial permutations that can be extended to the notion of P -crucial words. In S-crucial permutations, a particular case of P -crucial permutations, we deal with permutations that avoid prohibitions, but whose extensions in any position contain a prohibition. We show that S-crucial permutations exist with respect to squares, and minimal such permutations are of length 17.

Finally, using our software, we generate relevant data showing, for example, that there are 162,190,472 bicrucial square-free permutations of length 19.

1 Introduction

A factor of a word is a number of consecutive letters in the word. A word w avoids a word u if w does not contain u as a factor. Let S be a set of prohibited factors, that is, factors to be avoided. A word w over a finite alphabet A is right-crucial (resp., left-crucial) with respect to S if it avoids the prohibitions, but adjoining a new letter from A to the right (resp., left) of w gives a word that does not avoid the prohibitions. Clearly, studying right-crucial words can be turned to studying left-crucial words, and vice versa (through reversing all words in question). A word is bicrucial if it is both right- and left-crucial.

We say that a word w contains a k-th power if w contains a factor XX ⋯ X with k non-empty words X. The case k = 2 corresponds to squares in words, and their study was initiated by Axel Thue in [17] in 1906. A word w contains an abelian k-th power, if w contains a factor X_{1}X_{2} ⋯ X_{k} where X_{i} is a permutation of X_{1} for 2 ≤ i ≤ k. Paul Erdős [7] introduced the notion of abelian squares (the case of k = 2) in 1961. Right-crucial and bicrucial words with respect to squares, abelian squares, and, more generally, k-th powers and abelian k-th powers were studied in [1, 4, 6, 8, 12, 14]. These studies belong to the area of combinatorics on words.

Avgustinovich et al. [2] extended the notion of squares, as well as the notion of (right- ,bi)crucial words, from words to permutations by merging the respective notions in combinatorics on words and the theory of permutation patterns (see [13] for a comprehensive introduction to the theory); precise definitions will be given below. More studies in this direction were conducted in [3].

Avgustinovich et al. [2] showed that right-crucial permutations exist of any length larger than 6, while existence of bicrucial permutations was only shown for lengths 8k + 1, 8k + 5, 8k + 7 for k ≥ 1 (the shortest such permutation is of length 9). The question on whether there exists bicrucial permutations of even lengths and of length 8k + 3 for some k ≥ 1 was open for about three years. In this paper, we will show that bicrucial permutations of even length exist (the smallest such permutation is of length 32), and that bicrucial permutations of length 8k +3 exist for k = 2, 3 and they do not exist for k = 1. Our main tool in obtaining the results is an encoding of orderings (see Subsection 3.2) and the constraint solver Minion.

Note that what we call “right-crucial permutations” are known as “crucial permutations” in the literature. In this paper we generalize the notion of right-crucial and bicrucial permutations to P -crucial permutations with respect to a given set of prohibitions, where P is a possibly infinite set of non-negative integers. A particular example of P -crucial permutations is S-crucial (standing for Super-crucial) permutations which avoid prohibitions but extending them in any position leads to a prohibition. This notion has an obvious counter-part in the case of words. We will show that the minimum S-crucial permutation with respect to squares is of length 15 (see Section 2.4).

The paper is organized as follows. In Section 2 we discuss all objects of interest stating some known results, and our new results on them. In Section 3 we discuss software used to obtain most of our results. Finally, in Section 4 we discuss some directions for further research.

In this paper, we need the following notions. The reverse of a permutation π = π_{1}π_{2} ⋯ π_{n} is the permutation r(π) = π_{n}π_{n−1} ⋯ π_{1}, while the complement of π is the permutation c(π) = (n + 1 − π_{1})(n + 1 − π_{2}) ⋯ (n + 1 − π_{n}). For example, if π = 2134 then r(π) = 4312 and c(π) = 3421. When we say “up to symmetry” in counting problems, we mean the following. If a permutation π has been already counted as a permutation satisfying given properties, then the permutation c(π) is not to be considered. Also, in the cases when π has a given property if and only if r(π) has that property, then r(π) and c(r(π)) = r(c(π)) are not to be considered as well.

2 Objects of interest and our results

We consider permutations of sets of positive integers. For example, π = 2637 is a permutation of the set {2, 3, 6, 7}. Let σ be a permutation of {1, 2, …, k}. We say that a permutation π of a set of size k forms the pattern σ if the elements of π are in the same relative order as those of σ. For example, the permutation π = 2637 forms the pattern σ = 1324, because both π and σ have their smallest and largest elements in the first and last positions, respectively, and next largest and next smallest elements in the second and third positions, respectively.

In what follows, for a permutation π = π_{1}π_{2} ⋯ π_{n} in question, we will write π[x, y] = π[s, t] to indicate that the pattern formed by the elements of π in positions x, x + 1, …, y is equal to that formed by the elements of π in position s, s + 1, …, t. In xπ′, an extension of π to the left (defined properly below), we assume x to be in position 0, while in π′y, an extension of π to the right (again, defined properly below), we assume y to be in position n + 1. For example, in the permutation π =492517638 we have π[1, 2] = π[3, 4] (because 49 and 25 form the same pattern 12) and π[4, 6] = π[7, 9] (because 517 and 638 form the same pattern 213). Where it is clear from context what π is, we may abuse notation by omitting it and writing (for example) [4, 6] = [7, 9].

We will be referring to tables showing the number of permutations satisfying various properties. These were calculated using constraint programming techniques and a constraint solver called Minion [11]. We give more detail about our approach below, in Section 3.2. For now we just mention that we report a metric of search cost called nodes. Minion (along with many other constraint solvers) performs a depth-first exploration of a rooted binary tree. The root represents the initial state and left branches represent an (exploratory) assignment of a variable. Solutions are found at leaf nodes. Minion reports the number of left branches as its node count.

2.1 Square-free permutations

We use the one-line notation to represent permutations. A factor of a permutation π is one or more consecutive elements in π. For example, 4273, 36 and 1 are factors in the permutation 5142736.

A permutation is square-free if it does not contain two consecutive factors of length two or more that are in the same relative order, that is, that are order-isomorphic. For example, the permutation 243156 is square-free, while the permutation 631425 contains the square 3142 (indeed, 31 is order isomorphic to 42). Another example of a permutation that does not avoid squares is 742563891 as it contains the squares 425638, 5638 and 563891. The number of square-free permutations of length n, for n = 1, 2, …, 18, is

\begin{matrix}1, 2, 6, 12, 34, 104, 406, 1112, 3980, 15216, 68034, 312048, 1625968, 8771376, \\ 53270068, 319218912, 2135312542, 14420106264 \end{matrix}

and this is the sequence A221989 in the On-Line Encyclopedia of Integer Sequences, OEIS [20]. See also Table 1. It is known [2] that the number of square-free permutations of length n is n^{n(1−ε_{n})} where ε_{n} → 0 when n → ∞.

n  Solutions  Nodes  Solutions  Nodes  Solutions  Nodes
Searched up to Symmetry  Searched  π = r(c(π)) Searched

up to Symmetry

3  6  11  2  4  1  2
4  12  29  3  11  0  3
5  34  90  10  33  3  9
6  104  296  26  93  0  17
7  406  1147  105  276  7  23
8  1112  3845  278  932  0  10
9  3980  14505  1011  3936  32  117
10  15216  57680  3804  14534  0  130
11  68034  256501  17065  60237  113  402
12  312048  1209914  78012  313175  0  21
13  1625968  6244642  406795  1764062  606  2913
14  8771376  34262121  2192844  8714313  0  434
15  53270068 204080489  13318687  47248481  2340  11593
16 319218912 1260657446  79804728 318506973  0  36
17 2135312542  -  533838106 2336505587  19941  107779

Table 1: Enumerating square-free permutations of length n using the constraint programming approach (cf. Section 3.2). Every number is obtained by direct computer enumeration except for n = 17 solutions, which is calculated as 4 times the number of solutions up to symmetry minus twice the number of reverse-complemented solutions. Numbers of solutions form \underline{A221989}, \underline{A238937} and \underline{A238942} in [20].

It is easy to see [2] that for a permutation π = π_{1}π_{2} ⋯ to avoid squares of length 2, there must exist i ∈ {0, 1, 2, 3} so that for every non-negative integer t, the inequalities

π_{i+4t} < π_{i+4t±1} and π_{i+4t+2} > π_{i+4t±3}  (1)

hold. Schematically, the four possible kinds of square-free permutations (according to the choice of i) are as follows:

i = 1  ... i = 0  ...
i = 3  ... i = 2  ...

where a dot represents an element in π and the order of elements represented by two nonconsecutive dots is irrelevant, whereas each pair of consecutive dots is comparable (a lower dot represents a smaller element).

For better understanding of the properties of square-free permutations, we enumerated such permutations up to symmetry. These values are presented in Table 1. These sequences were not known to the OEIS [20], and to the best of our knowledge, these results are new.

We note that solutions up to symmetry were used in Table 1 to calculate the total number of square-free permutations in the case of n = 17. The inclusion-exclusion principle is used here: each symmetrically distinct π gives four permutations through combinations of c and r, unless π = c(r(π)) (equivalently, π = r(c(π))), in which case it gives two. Also, note that the 0s in the next to the rightmost column in Table 1 follow from the zigzag structure of square-free permutations.

2.2 Right- and left-crucial permutations with respect to squares

In this subsection we define the notion of right-crucial permutations with respect to squares which was previously known [2] as crucial permutations with respect to squares.

Let π = π_{1}π_{2} ⋯ π_{n} be a permutation of length n. An extension of π by an element x ∈ {1, 2, …, n+1} in position i ∈ {0, 1, …, n} is the permutation π′_{1}π′_{2} ⋯ π′_{i}xπ′_{i+1}π′_{i+2} ⋯ π′_{n} of length n + 1, where π′_{i} = π_{i} if π_{i} < x and π′_{i} = π_{i} + 1 otherwise. In particular, the case of i = 0 is called an extension of π by x to the left and the case i = n is called an extension of π by x to the right.

A permutation is right-crucial with respect to squares if it is square-free but any extension of it to the right by any element gives a permutation that is not square-free. We also say that such a permutation is a right-crucial square-free permutation. For example, the permutation 2136547 is right-crucial with respect to squares. It is shown in [2] that rightcrucial permutations with respect to squares exist of any length larger than 6. All the right-crucial permutations with respect to squares of length 7 are listed below:

2136547, 2137546, 2146537, 2147536, 2156437, 2157436, 2167435,
3146527, 3147526, 3156427, 3157426, 3167425, 3246517, 3247516,
3256417, 3257416, 3267415, 3421675, 3521674, 3621574, 3721564,
4156327, 4157326, 4167325, 4256317, 4257316, 4267315, 4356217,
4357216, 4367215, 4521673, 4531672, 4532671, 4621573, 4631572,
4632571, 4721563, 4731562, 4732561, 5167324, 5267314, 5367214,
5467213, 5621473, 5631472, 5632471, 5641372, 5642371, 5721463,
5731462, 5732461, 5741362, 5742361, 6721453, 6731452, 6732451,
6741352, 6742351, 6751342, 6752341.

The number of right-crucial permutations of length n with respect to squares, for n = 7, 8, …, 17, is

60, 140, 518, 1444, 8556, 31992, 220456, 984208, 7453080, 39692800, 289981136

and this is the sequence \underline{A221990} in the OEIS [20]. See also Table 2.

n Solutions  Nodes  Solutions  Solutions  Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  0  0  0  0
5  0  0  0  0  0
6  0  0  0  0  0
7  60  262  30  0  16
8  140  658  70  0  25
9  518  2978  259  5  60
10  1444  9135  722  0  232
11  8556  44110  4278  0  46
12  31992  157334  15996  0  61
13  220456  1109525  110228  168  1841
14  984208  5008522  492104  0  845
15  7453080 46370720  3726540  0  4113
16 39692800 251929277  19846400  0  113
17 289981136 1939299692  144990568  3522  81951

Table 2: Enumerating right-crucial permutations of length n with respect to squares. In this case, π being a solution only guarantees that c(π) is, but not r(π). The solutions up to symmetry is always exactly half the total number of solutions, and that number is used in the centre column without an additional search. The first column of solutions is \underline{A221990} in [20].

The notion of a left-crucial permutation with respect to squares can be defined similarly. Namely, a permutation is left-crucial with respect to squares if it is square-free but any extension of it to the left by an element gives a permutation that is not square-free. Taking into account that the reverse of a permutation preserves the property of avoiding squares, it is equivalent to study right-crucial and left-crucial permutations (in particular, the numbers of these permutations of length n are the same for any n).

The following proposition follows directly from the zigzag structure of square-free permutations described in Subsection 2.1.

Proposition 1. If π is a left-crucial (resp., right-crucial) permutation with respect to squares, and σ = xπ′ (resp., σ = π′x) is its extension to the left (resp., right), then a prohibited square in σ is either of length 4, or of length multiple of 8.

We prove the following theorem, whose analogue for right-crucial permutations is easy to obtain by applying the reverse operation to permutations that turns, in particular, position 0 to position n.

Theorem 2. Suppose π is a left-crucial permutation with respect to squares. If extending π to the left to give π_{1} results in a square of length 16 (that is, in π_{1}[0, 7] = π_{1}[8, 15]) then there is no extension π_{2} to the left of π that results in a square of length 24 (that is, in π_{2}[0, 11] = π_{2}[12, 23]).

Proof. We have that for some extension π_{1} of π, π_{1}[0, 7] = π_{1}[8, 15], and, in particular, π[4, 7] = π[12, 15] (any subset of the former relation must have the same relative order). However, if another extension of π named π_{2} gives a square of length 24, we would have to have that π_{2}[0, 7] = π_{2}[12, 19], in particular, π[4, 7] = π[16, 19], which leads to π[12, 15] = π[16, 19], a contradiction (two consecutive factors would be equal in π, but π is squarefree).

Proposition 3. Suppose π = π_{1}π_{2} ⋯ π_{n} is a left-crucial permutation with respect to squares such that either π_{1} < π_{2} < π_{3} or π_{1} > π_{2} > π_{3}. Then among its all possible n + 1 extensions to the left, we will meet squares of at least four different lengths.

Proof. Assume that π_{1} < π_{2} < π_{3}; the other case can be considered analogously. Extending π to the left by 1 will obviously give a square S_{1} of length 4 formed by the pattern 12. Further, extending π to the left by π_{1} + 1, we get a permutation that begins with the pattern 2134, that is, with the four letters that are order-isomorphic to 2134. But then the respective square S_{2} in this extension (there is one because π is left-crucial) also begins with the pattern 2134, and thus, S_{2} is different from S_{1}. Now, extending π by π_{2} + 1, we will obtain a permutation beginning with the pattern 3124, and thus the respective square S_{3} also begins with the pattern 3124 and it is different from S_{1} and S_{2}. Finally, extending π by n + 1 will give a permutation that begins with the pattern 4123, and thus the respective square S_{4} also begins with the pattern 4123 and it is different from S_{1}, S_{2} and S_{3}.

Theorem 4. Suppose π = π_{1}π_{2} ⋯ π_{n} is a left-crucial permutation with respect to squares such that either π_{1} < π_{2} < π_{3} or π_{1} > π_{2} > π_{3}. Then the length of π, n, is at least 31.

Proof. We can assume that π_{1} < π_{2} < π_{3}; the other case can be considered analogously. By Proposition 1, possible squares are of lengths 4, 8, 16, 24, 32, etc. By Proposition 3 we have at least four different squares, and by Theorem 2 we cannot have both of 16 and 24 length squares involved. This leads us to having at least one square of length at least 32. Thus, π is of length at least 31.

2.3 Bicrucial permutations with respect to squares

In this subsection we define the notion of bicrucial permutations with respect to squares which was previously known [2] as maximal permutations with respect to squares.

A permutation is called bicrucial with respect to squares if it is both right-crucial and leftcrucial. We also call such permutations bicrucial square-free permutations. It was proved in [2] that there exist bicrucial permutations with respect to squares of odd lengths 8k +1, 8k + 5, 8k + 7 for k ≥ 1. Computer experiments show that the smallest bicrucial permutations

n  Solutions  Nodes  Solutions  Nodes  Solutions  Nodes
Searched up to Symmetry  Searched  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0  0
4  0  0  0  0  0  0
5  0  0  0  0  0  0
6  0  0  0  0  0  0
7  0  97  0  0  0  0
8  0  126  0  0  0  0
9  54  607  16  33  5  9
10  0  351  0  0  0  0
11  0  1665  0  0  0  0
12  0  1422  0  0  0  0
13  69856  298659  17548  48558  168  365
14  0  63292  0  0  0  0
15  2930016 14793584  732504  1981923  0  0
16  0  3475684  0  0  0  0
17  40654860 382563747  10165476  33999226  3522  8361
18  0  -  0  0  0  0
19  162190472  -  40547618  124608134  0  0
20  0  -  0  0  0  0
21 ≥ 1156065982  -  ≥ 578032991 ≥ 2091556603  287834  772800
22  0  -  0  0  0  0
23 ≥ 1250325828  -  ≥ 625162914 ≥ 1849967660  0  0
24  ?  -  ≥ 0 ≥ 1021275473  0  0
25  ≥ 28100262  -  ≥ 0 ≥ 991823284  14050131 32022959
26  0  -  0  43972617  0  0

Table 3: Enumerating bicrucial square-free permutations of length n. The first column of solutions is the sequence \underline{A238935} in [20]. From n = 18 on we did not run experiments for the first column, but can make deductions from the other columns. The strongest possible deductions are shown: a precise number based on the later columns where those runs completed; or ≥ to indicate that twice the number in the centre or right hand column is a lower bound; or ‘?’ to indicate that no useful deduction can be made. In the middle columns a ≥ indicates that a run was started but did not finish in the time available: therefore the given numbers are lower bounds. In two cases Minion found no solutions within its time limit, and this is indicated by ≥ 0. We used the SSAC preprocessing option and then the dom/wdeg heuristic: for more details see Subsection 3.2.

with respect to squares are of length 9, and the number of such permutations of length n, for n = 9, 10, …, 20, is

54, 0, 0, 0, 69856, 0, 2930016, 0, 40654860, 0, 162190472, 0.

See Table 3: in some cases note that direct computations were too time consuming, and these numbers were computed from the numbers of symmetrically distinct solutions. Recall that each symmetrically distinct π gives four permutations through combinations of c and r, unless π = c(r(π)) (equivalently, π = r(c(π))), in which case it gives two. An interesting point in that table is that sometimes we could not solve a problem at one size but could solve it at a larger size. While the smaller problem has fewer variables and constraints it nevertheless requires more search.

Even though there do not exist any bicrucial square-free permutations of length n = 8k+3 when k = 1, there do exist such permutations of length n = 8k + 3 for k = 2 and k = 3, for example,

143289756(14)(11)(10)(17)(19)(16)(13)(15)(18)(12)  (1)

and

312(27)(26)6(24)(25)54(11)(23)(12)8(10)(16)97(17)(21)(19)(14)(18)(20)(15)(13)(22), (2)

respectively. Thus, we have the following theorem that answers the respective question in [2].

Theorem 5. Regarding the case n = 8k + 3, there are no bicrucial square-free permutations of length 11, while such permutations of lengths 19 and 27 exist.

Proof. The theorem follows from our computer experiments that, in particular, led us to discovery of permutations (1) and (2). However, we will justify here why these permutations are not extendable to the left or to the right leaving to the Reader proving the fact that they are square-free.

• For the permutation (1), extending it to the left by any element larger than 1 will give a square of length 4 formed by the pattern 21 (that is, [0, 1] = [2, 3] in this case following the notation in the beginning of this section), while extending it to the left by 1 we obtain a square of length 16 formed by the pattern 12543786 (that is, in this case [0, 7] = [8, 15]). On the other hand, extending the permutation to the right by an element larger than 12 we obtain a square of length 4 formed by the pattern 12 (that is, in this case [17, 18] = [19, 20]), while extending it to the right by any other element we obtain a square of length 8 formed by the pattern 3421 (that is, in this case [13, 16] = [17, 20]).

• For the permutation (2), extending it to the left by any element less than 4 we obtain a square of length 4 formed by the pattern 12 (that is, in this case [0, 1] = [2, 3]), while extending the permutation to the left by any other element we obtain a square of length 8 formed by the pattern 4312 (that is, in this case [0, 3] = [4, 7]). As for extending to the right, doing so by an element less than 22 we obtain a square of length 4 formed by the pattern 21, while extending to the right by any other element we obtain a square of length 16 formed by the pattern 52463178 (that is, in this case [13, 20] = [21, 28]).

What we found to be especially striking is that bicrucial square-free permutations of even length do exist, despite what the data in Table 3 suggest. We record this result in the following theorem.

Theorem 6. Bicrucial square-free permutations of even length exist. The shortest such permutation is of length 32.

Proof. An example of a bicrucial square-free permutation of length 32 is

(28)(30)(31)(23)(22)(24)(29)(27)(19)(25)(26)(17)(13)(18)(21)(20)(14)(16)(32)879(15)(12)5(10)(11)31462.

The fact that the permutation above is proper was checked by computer. However, we demonstrate here that it is not extendable either to the left or to the right while skipping explanation why it is square-free. Indeed, extending the permutation to the right by any element > 2 we get a square of length 4 involving the pattern 12 (for example, extending to the right by 4, the rightmost four elements will be 5724, which is a square), while extending it by element 1 or 2, we will obtain [26, 29] = [30, 33] (the respective pattern is 3421). See Table 4 for squares appearing while extending the permutation to the left.

Left-extension by element Square length  Half of square pattern
< 29  4  12
29, 30  8  2134
31  32  (15)(12)(14)(16)768(13)(11)49(10)2135
32, 33  16  84672135

Table 4: Squares appearing while extending the permutation of length 32 to the left.

The fact that the permutation of length 32 is the shortest possible out of bicrucial squarefree permutations of even length was checked by computer. However, we provide here an argument justifying this fact.

Let π be a bicrucial permutation of even length. The key observation is that because of the zigzag structure described in Subsection 2.1, π either begins or ends with three elements in a monotonic order (either increasing or decreasing). If necessary, we can apply the reverse operation to be able to assume without loss of generality that π begins either with three increasing or three decreasing elements. But then by Theorem 4, the length of π is at least 32 (it must be even).

To see more properties of bicrucial square-free permutations, we enumerate symmetrically distinct such permutations, that is, ensuring that for each bicrucial permutation π, the permutations π, r(π), c(π) and r(c(π)) = c(r(π)) are collectively counted exactly once. The results are presented in Table 3 in the central columns. We also find the number of symmetrically distinct bicrucial square-free permutations on the set of permutations invariant under taking the composition of the reverse and complement operations, that is, the set of permutations π such that π = r(c(π)) = c(r(π)). Note that if π has this property then so does the permutation c(π): again we only count one of these permutations. These results are presented in Table 3 in the right hand columns.

Note that each symmetrically distinct bicrucial square-free permutation gives four different permutations, with the exception of permutations unchanged under the composition of taking the reverse and complement. These latter permutations give two different permutations. Once again, by the inclusion-exclusion principle, for each n, the number of bicrucial square-free permutations is four times the number in the central column of Table 3 minus twice the number in the right hand column of Table 3. This serves as a check for k = 9, 13, 15, 17 and allows us to extend the sequence \underline{A221990} in [20] for n = 19, with 4 · 40, 547, 618 = 162, 190, 472, which is recorded in Table 3. We are sometimes able to provide all solutions up to symmetry when we cannot enumerate them in full, simply because the search space is (approximately) four times smaller.

2.4 P -crucial and S-crucial permutations with respect to squares

The following notions of P -crucial and S-crucial permutations are defined for the first time in this paper. First we must define an extension of a permutation π in position i ∈ {0 … n} by symbol q. The symbol q is inserted at position i where i = 0 indicates that q is added to the left of the permutation, and i = n means q is added to the right. Each symbol in π that is < q remains the same in the extended permutation, and symbols ≥ q are increased by 1.

Given a set of non-negative integers P and a set of prohibitions Q, a permutation is called P -crucial with respect to Q, if it avoids the prohibitions but any of its extensions in position i results in a permutation containing a prohibition from Q, whenever i ∈ P. Sets P and Q can either be finite or infinite. In particular, Q can be a set of prohibited factors, for example, the set of all squares considered in this paper. If P = {0} then P -crucial permutations are just left-crucial permutations, and thus we deal with a generalisation of this notion. However, to have the most general definition, in particular, generalising the notion of right-crucial and bicrucial permutations, we allow P to be defined using the length of permutations. For example, we can say that P refers to positions 1, n − 3 and n − 2 in a permutation of length n. Similarly, right-crucial permutations correspond to the case P = {n}, while bicrucial permutations correspond to the case P = {0, n}.

S-crucial permutations are P -crucial permutations with P = {0, 1, 2, …}, that is, any extension of an S-crucial permutation in any position will lead to an occurrence of a prohibition. S in “S-crucial” stands for “Super”.

The notions of P -crucial and S-crucial permutations with respect to a given set of prohibitions can be easily extended to the case of words, which is not in the scope of this paper. Our immediate interest is in S-crucial permutations with respect to squares and in the question whether such permutations exist. It is immediate from definitions that

S-crucial permutations ⊆ bicrucial permutations = right-crucial permutations ∩ left-crucial permutations.

2.5 S-crucial permutations with respect to squares

Taking into account the double zigzag structure of square-free permutations described in Subsection 2.1, one sees that in order to test if a given square-free permutation is S-crucial or not, we only need to check what happens when extending the permutation in positions i = 0, 1, n−1, n. Indeed, inserting the new element in any other position will obviously break the double zigzag structure (no matter what the element will be) and therefore will cause the obtained permutation to contain a square. Thus, in the case of prohibited squares, Scrucial permutations accept an equivalent definition as P -crucial permutations with respect to squares, where P = {0, 1, n − 1, n} for permutations of length n.

Theorem 7. S-crucial permutations with respect to squares exist, and the shortest such permutation is of length 17. There are 1568 S-crucial permutations with respect to squares of length 17.

Proof. The following permutation of length 17 is S-crucial with respect to squares:

24315(11)(10)69(12)87(13)(17)(15)(14)(16),

which can be checked by confirming that it is square-free but all of its extensions in positions 0, 1, 16 and 17 produce squares. Our proof otherwise relies on computer experiments reported in Table 12 showing that no S-crucial permutation with respect to squares exist of length less than 17, and the total for n = 17.

P  min length # of min length  Type of permutations  Table
{0}, {n}  7  60 left- & right-crucial (Subsec. 2.2) 2
{1}, {n − 1}  7  82  6
{0, 1}, {n − 1, n}  15  54854  7
{0, n − 1}, {1, n}  7  20  8
{0, n}  9  54  bicrucial (Subsec. 2.3)  3
{1, n − 1}  7  18  9
{0, 1, n − 1}, {1, n − 1, n}  16  553428  10
{0, 1, n}, {0, n − 1, n}  17  550976  11
{0, 1, n − 1, n}  17  1568  S-crucial (Subsec. 2.5)  12

Table 5: P -crucial permutations with respect to squares.

2.6 More on P -crucial permutations with respect to squares

As is mentioned above, S-crucial permutations coincide with {0, 1, n − 1, n}-crucial permutations, because extending square-free permutations in positions different from those in the set {0, 1, n − 1, n} will automatically give a square. Thus, for any P, P -crucial permutations with respect to squares are equivalent to A-crucial permutations with respect to squares for some A ⊆ {0, 1, n − 1, n}. The case of empty A is not interesting, and thus we essentially have 15 classes to consider of P -crucial permutations with respect to squares. Moreover, because of the reverse operation, some of these 15 classes are equivalent to study. For example, as we know, studying left-crucial permutations (P = {0}) is equivalent to studying right-crucial permutations (P = {n}). In Table 5 we summarize our knowledge on P -crucial permutations with respect to squares that is based on computer experiments.

3 Generating (right-,bi)crucial permutations with respect to squares

In Subsection 3.1 we discuss our original approach to deal with square-free permutations, and in Subsection 3.2 we discuss an optimisation via encoding orderings.

3.1 An approach to generate square-free permutations

We define the left parent (resp., right parent) of a permutation π ∈ S_{n}, the set of permutations of length n, as the unique permutation in S_{n−1} order-isomorphic to the sequence of the first (resp., last) n − 1 letters of π. The left children (resp., right children) of σ ∈ S_{n−1} are all π ∈ S_{n} such that σ is a right (resp., left) parent of π.

Clearly the parents of a square-free permutation are square-free; a right-crucial permutation is one with no square-free right children and a bicrucial permutation is one with no square-free children at all.

Our construction algorithm is iterative. At each step we assume that we have a data structure representing the square-free permutations of lengths n − 2 and connecting each of them with all of its children (of length n − 1). This necessarily includes all square-free permutations of length n − 1. We now compute all the square-free permutations of length n as follows. For each square-free permutation α of length n − 2, each left child σ of α and each right child τ of α we form all permutations π which have σ as left parent and τ as right parent. There are either one or two of these. Such a π can only fail to be square-free if n is even, greater than 2, and π is a repeat of a pattern of length n/2. Any shorter repeated pattern would be contained in at least one of σ and τ. This condition can be checked efficiently. We record all π which pass this check, both as square-free permutations of length n and as children of σ and τ, thereby preparing for the next iteration. A suitable data structure for the permutations of length zero and one can be constructed “by hand” to start the process.

After this computation, we can easily read off from our data structure all the square-free permutations of length n and the right-crucial and bicrucial permutations of length n − 1.

We used the Computational Algebra system GAP [10]. The calculation can be completed up to n = 18 in a few hours on a computer with 512GB RAM. Memory, rather than time, is the main barrier to continuing. However, in order to achieve our results for longer permutations, we had to come up with a different idea of generating permutations in question, which is discussed in the following subsection.

3.2 Representing permutations in constraint programming

Constraint programming is a means of solving finite domain combinatorial problems [19]. It is the subject of much research and many fast and efficient solvers are available. In particular we use Minion, a solver developed at St Andrews [11]. As well as fast solving, it is critical that problems are modelled effectively. Modelling is the process of converting an abstract specification of a problem to a constraint satisfaction problem that can be searched effectively. To help with the modelling process we use Savile Row, an automated modelling assistant [16]. Savile Row allows us to express models in a higher level language than the input language of Minion.

The question we have in front of us is how to model permutations in a way that can be represented in a constraint solver and reasoned with effectively in the context of square-free permutations. This is an unusual application, because the properties of the permutation being used are not the normal ones. Normally in constraints one is interested in the value of each element of the permutation, and using them in some way. Here, we are interested only in the relative ordering of elements. So, we do not need to know efficiently that the permutation maps (say) 4 to 3, but we must be able to detect efficiently that the partial permutation (say) 2813 represents the same ordering as 5824 but is different from 1823. Standard representations of permutations in constraint solving are not amenable to this form of reasoning.

Therefore, we constructed a new model of permutations in constraints which is efficient for the current application. Assume that we have permutations stored in two arrays A and B (although in practice they may be two segments of the same array). The encoding idea is straightforward. An ordering is uniquely defined by the binary inequalities between elements. To exploit this we use “reification”, see, e.g., [15]. The reified value of a particular constraint is its truth value treated as a boolean: i.e., the reified value is 1 if the constraint is false and 0 if the constraint is true. We introduce a new boolean variable for the reified value of each inequality. That is, we have a variable a_{i,j} such that a_{i,j} = T ≡ A[i] < A[j]. Similarly, b_{i,j} = T ≡ B[i] < B[j]. Then we have the simple observation that the ordering of A and B with respect to < is the same if and only if a_{i,j} = b_{i,j} for all i and j. This forms the basis of our encoding of square-free permutations: stating that no adjacent parts of permutations may be the same. For cruciality constraints we state that for each possible value added at the relevant position, at least one pair of identical parts of permutations must result.

In our experiments we used Minion version 1.6. In most cases we used it with standard settings. However in two experiments we gained significant value from other settings. In Tables 3 and 12 we used a specific preprocessing option and search heuristic. The SSAC preprocessing option was given to Minion, which performs Singleton-Singleton-(generalized)Arc-Consistency before search starts. SAC (singleton arc consistency) sets each variable to each possible value in turn, and if this leads to failure we can undo this and assert the variable cannot take this value [18]. SSAC doubles this, i.e., setting each variable to each possible value and then calling SAC, removing values after failure. This is an extremely expensive preprocessing step but we found sometimes that it reduced search so much it was worthwhile.

It also combines well with the dom/wdeg heuristic available in Minion, which we used in these cases.

In all cases, if π satisfied the given property, c(π) must. To calculate numbers of solutions up to symmetry, we used one of two approaches. If c(π) is the only symmetry we can simply halve the number of solutions found in complete search, since a permutation of length > 1 is never self-complementing. In some cases r(π) is a symmetry: specifically for square-free permutations, and P-crucial permutations for P = {0, n}, {1, n − 1} or {0, 1, n − 1, n}. In these cases we excluded all but a canonical solution from each equivalence class, using the standard ‘lex leader’ approach [5]. This is efficient because of the use of specialized constraints for lexicographical ordering [9].

We have not reported run-times in detail, but as an example, the n = 17 run in Table 3 required 54,858 cpu seconds, just under 15.25 cpu hours. This is a rate of just under 7,000 nodes per second. A key advantage of constraint programming is the massively reduced RAM requirements compared to Section 3.1. Because of this we are able to solve much larger problems: for example in Table 12 we are able to settle all questions for n = 22 and one for n = 26, compared to a maximum of n = 18 with the earlier approach.

4 Open questions and some conjectures

It would be interesting to find the missing (exact) solutions in Tables 3 and 12. Also, we would like to state the following conjectures.

Conjecture 8. There exist bicrucial permutations with respect to squares of length 8k + 3 for k ≥ 2.

Conjecture 9. There exist arbitrary long bicrucial square-free permutations of even length.

If Conjecture 9 is true, it is interesting to know whether such permutations exist for each even length greater than 30.

Conjecture 10. There exist arbitrary long S-crucial permutations with respect to squares.

Table 12 gives our empirical investigations into this question. While there were no Scrucial permutations of length 18, 19, 20 or 22, we did find (at least) 144,586 symmetrically distinct solutions at n = 21.

Finally, a general program of research here is the study of classes of P -crucial permutations with respect to a given set of prohibitions S (different from squares considered in this paper). One can study such objects in the way we study, say, right-crucial and bicrucial permutations, that is, to try to classify lengths for which respective P -crucial permutations exist, or at least to try to show that arbitrary long such permutations exist. Also, considering words instead of permutations for various (natural) sets P and S is yet another interesting research direction.

5 Acknowledgments

We are extremely grateful to Chris Jefferson for suggesting that square-free permutations may be appropriate for solution using constraint programming. We also grateful to the anonymous referees for a number of useful suggestions. This research is supported in part by EPSRC grants EP/G055181/1 and EP/H004092/1, for which we are very grateful.

A Additional results

n Solutions  Nodes  Solutions  Solutions  Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  6  0  0  5
5  0  10  0  0  7
6  0  15  0  0  13
7  82  351  41  3  28
8  272  1862  136  0  25
9  766  5955  383  0  112
10  3788  19687  1894  0  248
11  14096  75932  7048  58  617
12  74568  322940  37284  0  61
13  281232  1358128  140616  0  2894
14  2026184  7636544  1013092  0  848
15  9430962 42623572  4715481  961  13787
16 79497550 400446913  39748775  0  113
17 422657308 2274985904  211328654  28 101644

Table 6: Results for {1} and {n − 1}-crucial permutations. Node counts from former.

In this appendix we include full tables of results for all forms of cruciality not given in full detail in the main part of the paper. These tables are referred to in the main text by Table 5. The tables in this Appendix take one of two forms. As mentioned in the main text, for some sets P we have that if π is P -crucial then it is guaranteed that r(π) is also. In these cases a separate run is required to identify the number of symmetrically distinct solutions. Tables 9 and 12 are of this form. Where reversal symmetry is not guaranteed (the remaining tables), the tables are different in two ways. First, no separate run is necessary to count symmetrically distinct solutions: the total is always half the total number of solutions. Second, the table can be computed in one of two ways. For example, Table 6 shows numbers of {1}- and {n−1}-crucial permutations. While it is guaranteed that the number of solutions of each type is the same, the number of nodes searched may be different depending on which type was run. For precision, we indicate in each table which node count we are reporting. For example, in Table 6 we give node counts for {1}-crucial permutations. The choice of which case is reported is arbitrary.

n Solutions  Nodes  Solutions  Solutions  Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  0  0  0  0
5  0  0  0  0  0
6  0  0  0  0  0
7  0  102  0  0  16
8  0  161  0  0  25
9  0  244  0  0  34
10  0  351  0  0  232
11  0  485  0  0  46
12  0  649  0  0  61
13  0  846  0  0  122
14  0  1079  0  0  845
15  54854 1020814  27427  0  4113
16  722114 24479482  361057  0  113
17 5144632 118675744  2572316  28  53501

Table 7: Results for {0, 1} and {n − 1, n}-crucial permutations. Node counts from former.

n Solutions Nodes Solutions Solutions Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  0  0  0  0
5  0  0  0  0  0
6  0  0  0  0  0
7  20  111  10  0  16
8  96  530  48  0  25
9  0  1266  0  0  39
10  1444  7815  722  0  232
11  0  1294  0  0  46
12  10080  66223  5040  0  61
13  0  98871  0  0  1135
14  0  351920  0  0  845
15  2988 1883376  1494  0  4113
16 25781024 160519095  12890512  0  113
17 2138998 294150147  1069499  28  56458

Table 8: Results for {0, n − 1} and {1, n}-crucial permutations. Node counts from latter.

n Solutions  Nodes  Solutions  Nodes  Solutions  Nodes
Searched up to Symmetry Searched  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0  0
4  0  6  0  3  0  3
5  0  10  0  3  0  3
6  0  15  0  6  0  6
7  18  225  6  68  3  12
8  0  1385  0  347  0  10
9  0  4677  0  1288  0  52
10  0  13971  0  2936  0  130
11  8972  64562  2272  16749  58  294
12  0  199164  0  64118  0  21
13  281232  1216051  70308  371785  0  1403
14  0  3754582  0 1312833  0  434
15 3094458 32430311  774095 7744341  961  6828
16 1194800 257503934  298700 67920867  0  36
17 6056996 1714652389  1514263 524235669  28  52973

Table 9: Results for {1, n − 1}-crucial permutations.

n Solutions  Nodes  Solutions  Solutions  Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  0  0  0  0
5  0  0  0  0  0
6  0  0  0  0  0
7  0  102  0  0  16
8  0  161  0  0  25
9  0  244  0  0  34
10  0  351  0  0  232
11  0  485  0  0  46
12  0  649  0  0  61
13  0  846  0  0  122
14  0  1079  0  0  845
15  0  841776  0  0  4113
16  553428 23833969  276714  0  113
17  5424 107571076  2712  28  53437

Table 10: Results for {0, 1, n − 1} and {1, n − 1, n}-crucial permutations. Node counts from former.

n Solutions  Nodes  Solutions  Solutions  Nodes
Searched up to Symmetry  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0
4  0  0  0  0  0
5  0  0  0  0  0
6  0  0  0  0  0
7  0  83  0  0  16
8  0  126  0  0  25
9  0  479  0  0  43
10  0  351  0  0  232
11  0  1665  0  0  46
12  0  1422  0  0  61
13  0  110752  0  0  1243
14  0  63292  0  0  845
15  0 7381558  0  0  4113
16  0 3471394  0  0  113
17  550976 282598708  275488  28  56784

Table 11: Results for {0, 1, n} and {0, n − 1, n}-crucial permutations. Node counts from latter.

n Solutions  Nodes  Solutions  Nodes  Solutions  Nodes
Searched up to Symmetry Searched  π = r(c(π)) Searched

up to Symmetry

3  0  0  0  0  0  0
4  0  0  0  0  0  0
5  0  0  0  0  0  0
6  0  0  0  0  0  0
7  0  0  0  0  0  0
8  0  0  0  0  0  0
9  0  0  0  0  0  0
10  0  0  0  0  0  0
11  0  0  0  0  0  0
12  0  0  0  0  0  0
13  0  0  0  0  0  0
14  0  0  0  0  0  0
15  0  0  0  0  0  0
16  0  0  0  0  0  0
17  1568 9214495  406  823  28  55
18  0  0  0  0  0  0
19  0 17819710  0  0  0  0
20  0  0  0  0  0  0
21 ≥ 289172 timeout  ≥ 144586 ≥ 5795227  timeout
22  0  0  0  0  0  0
23  timeout  timeout  0  0
24  timeout  timeout  0  0
25  timeout  timeout  timeout
26  timeout  timeout  0  0

Table 12: Results for {0, 1, n−1, n}-crucial permutations (also called S-crucial permutations in the main text). A timed out run is one which failed to find any solutions before 6 hours cpu time were used on our machine. Note that problems do not get monotonically harder, presumably because some sizes, e.g., 22, are intrinsically easier to search than other sizes. Interestingly, no solutions were found for 21 in regular search. However, because 144,586 were found up to symmetry before the timeout: all of these and their complements are S-crucial permutations so we obtain the lower bound given in the first column. These experiments were run with SSAC preprocessing and dom/wdeg heuristic.

References

[1] S. Avgustinovich, A. Glen, B. V. Halldórsson, and S. Kitaev, On shortest crucial words avoiding abelian powers, Discr. Appl. Math. 158 (2010), 605–607.

[2] S. Avgustinovich, S. Kitaev, A. Pyatkin, and A. Valyuzhenich, On square-free permutations, J. Autom., Lang. and Combin. 16 (2011) 1, 3–10.

[3] S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Crucial and bicrucial permutations with respect to arithmetic monotone patterns, Siberian Elect. Math. Reports 9 (2012), 660–671.

[4] E. M. Bullock, Improved bounds on the length of maximal abelian square-free words, Elect. J. Combin. 11(1) (2004), #R17.

[5] J. M. Crawford, M. L. Ginsberg, E. M. Luks, and A. Roy, Symmetry-breaking predicates for search problems, Principles of Knowledge Representation and Reasoning - KR (1996), 148–159.

[6] L. J. Cummings and M. Mays, A one–sided Zimin construction, Elect. J. Combin. 8 (2001), #R27.

[7] P. Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254.

[8] A. Evdokimov and S. Kitaev, Crucial words and the complexity of some extremal problems for sets of prohibited words, J. Combin. Theory Ser. A 105/2 (2004), 273–289.

[9] A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh, Propagation algorithms for lexicographic ordering constraints, Artif. Intell. 170 (2006) 10, 803–834.

[10] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.7.2 ; 2013,

http://www.gap-system.org.

[11] I. P. Gent, C. Jefferson, and I. Miguel, Minion: A fast scalable constraint solver, in Proceedings of the 17th European Conference on Artificial Intelligence – ECAI 2006, Frontiers in Artificial Intelligence and Applications, Vol. 141, 2006, pp. 98–102.

[12] A. Glen, B. V. Halldórsson, and S. Kitaev, Crucial abelian k-power-free words, Discr. Math. and Theoret. Comp. Sci. 12 (2010) 5, 83–96.

[13] S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011.

[14] M. Korn, Maximal abelian square-free words of short length, J. Combin. Theory Ser. A 102 (2003), 207–211.

[15] C. Jefferson, N. C. A. Moore, P. Nightingale, and K. E. Petrie, Implementing logical connectives in constraint programming, Artif. Intell. 174 (2010) 16–17, 1407–1429.

[16] P. Nightingale, Ö. Akgün, I. P. Gent, C. Jefferson, and I. Miguel, Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination, in Principles and Practice of Constraint Programming – CP 2014, Lecture Notes in Comput. Sci., Vol. 8656, 2014, pp. 590–605.

[17] A. Thue. Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 139–158.

[18] P. Prosser, K. Stergiou, and T. Walsh, Singleton consistencies, in Principles and Practice of Constraint Programming – CP 2000, Lecture Notes in Comput. Sci., Vol. 1894, 2000, pp. 353–368.

[19] F. Rossi, P. van Beek, and T. Walsh, eds., Handbook of Constraint Programming, Elsevier, 2006.

[20] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 68R15. Keywords: crucial permutation, bicrucial permutation, square, P -crucial permutation, Scrucial permutation.

(Concerned with sequences \underline{A221989}, \underline{A221990}, \underline{A238935}, \underline{A238937}, and \underline{A238942}.)

Received January 30 2015; revised version received April 12 2015; May 22 2015; June 2 2015. Published in Journal of Integer Sequences, June 3 2015.

Return to Journal of Integer Sequences home page.