# A property related to permutations with coprime adjacent values

Sequence A76220 of OEIS enumerates (up to $$n=25$$) the number $$a_n$$ of permutations $$\sigma$$ of $$\lbrace 1,\ldots,n\rbrace$$ such that $$\sigma(i)$$ and $$\sigma(i+1)$$ are coprime for $$i=1,\ldots,n-1$$.

All these numbers are obviously even for $$n>1$$.

All these numbers are divisible by $$3$$ for $$n\geq 3$$.

All these numbers are divisible by $$9$$ for $$n\geq 5$$.

All these numbers are divisible by $$5$$ for $$n\geq 17$$.

Such a number $$a_n$$ is divisible by $$k!$$ if there are $$k-1$$ primes larger than $$n/2$$ and smaller than $$n$$ (the images of $$1$$ and of these primes in any permutation contributing to $$a_n$$ can be arbitrarily permuted).

The above examples suggest however better divisibility properties, suggesting the following problem:

Given an integer $$n$$, what is the maximal number $$k=k(n)\leq n$$ such that for every permutation $$\sigma$$ of $$\lbrace 1,\ldots,n\rbrace$$ there exists a set $$\lbrace a_1,\ldots,a_k\rbrace$$ of $$k$$ elements in $$\lbrace 1,\ldots,n\rbrace$$ with $$\sigma(a_i)$$ coprime to $$\sigma(a_j\pm 1)$$ for all $$i$$ and $$j$$ (with $$a_j-1$$ or $$a_j+1$$ outside $$\lbrace 1,\ldots,n\rbrace$$ dropped)?

Can one say something meaningful on the asymptotics of $$k(n)$$ (e.g., has it sublinear growth)?

Observation: We can of course assume that $$a_1,\ldots,a_k$$ contains the preimage of $$1$$ and of all primes larger than $$n/2$$ in $$\lbrace 1,\ldots,n\rbrace$$.

• Notice tht you can also permute pairs of the form $(p,2p)$ where $n/3<p\leq n/2$, and so on. Doesn't this improve divisibility? Oct 24, 2022 at 16:43
• BTW, do you want the property to be satisfied for all permutations, or only for those enumerated by A76220? Oct 24, 2022 at 16:48
• @IlyaBogdanov No you can not permute $p$ and $2p$ in general: $p$ can have even neighbours! Oct 24, 2022 at 17:23
• Reply to the second question of Ilya Bogdanov: One can consider both problems but it is perhaps more natural to define $k(n)$ with respect to all permutations. Oct 24, 2022 at 17:25
• Sorry for being unclear; in the first comment I meant a permutation of $p$'s and, simultaneously, the same permutation of $2p$'s, such as $p\leftrightarrow q$ and $2p\leftrightarrow 2q$. Oct 25, 2022 at 5:50

Define $$k(\sigma)$$ as the maximal $$k$$ satisfying the requirements for that single permutation $$\sigma$$. Then even $$\max_{\sigma\in S_n}k(\sigma)$$ is sublinear in $$n$$.
Consider a graph on $$[n]$$, where edges are pairs of coprime numbers. A desired set $$\{a_1,\dots,a_k\}$$ corresponds to a complete bipartite subgraph with parts $$V_1=\{\sigma(a_i)\colon i\in[k]\}$$ and $$V_2=\{\sigma(a_i\pm1)\colon i\in[k]\}$$ (not exactly so; see below). The cardinalities of both parts are linear in $$k$$.
This means that the set $$\mathbb P_n=\mathbb P\cap[n]$$ is split into two parts, $$Q_1$$ and $$Q_2$$, such that the prime divisors of elements in $$V_i$$ are all in $$Q_i$$/. Minimal of such parts has a sublinear in $$n$$ cardinality.
Indeed, fix some number $$D$$ which is large but much smaller than $$n$$, and consider the intersections $$\mathbb P_i'=\mathbb P_i'\cap [D]$$. Then $$\frac{|V_i|}n\leq \prod_{p\in\mathbb P_i'}\left(1-\frac1p\right)(1+o(1)).$$ Since one of the two products is small, the claim follows.
Correction. The statement about complete bipartite graph is not completely true in the case when $$a_i\pm1$$ equals some $$a_j$$. In this case, we put such $$\sigma(a_i)$$ into only one part of the bipartite graph, so that the sizes of the parts differ by a factor of at most 2; then both sizes are still linear in $$k$$.
• Ilya, there is only one product (involving only factors smaller than $1$) on the right side of your inequality. Oct 25, 2022 at 7:14
• Sorry, I forgot to divide by $n$; now corrected. There are two products: for $V_1$ and for $V_2$; their product is small, so one of them is also small. Oct 25, 2022 at 9:15