Let $(a_1,a_2\ldots,a_n)$ and $(b_1,b_2,\ldots,b_n)$ be two permutations of arithmetic progressions of natural numbers. For which $n$ is it possible that $(a_1b_1,a_2b_2,\dots,a_nb_n)$ is an arithmetic progression?

The sequence is (trivially) an arithmetic progression when $n=1$ or $2$, and there are examples for $n=3,4,5,6$:

$n=3$: $(11,5,8), (2,3,1)$

$n=4$: $(1,11,6,16), (10,4,13,7)$

$n=5$: $(8,6,4,7,5), (4,9,19,14,24)$

$n=6$: $(7,31,19,13,37,25), (35,11,23,41,17,29)$


First, it's easy to see that real solutions can be rescaled to be rational and therefore also integer.

For $n=7$ there are no solutions.

For $n=6$ there are essentially 4 primitive integral solutions, with only one consisting of natural numbers (as requested):

$\big(-35+12(1,2,4,3,6,5)\big) \times \big(-5+2(5,6,1,2,3,4)\big) = -153+38(1,2,3,4,5,6)$

$\big(-19+6(1,2,5,6,3,4)\big) \times \big(-5+2(5,6,1,2,3,4)\big) = -81+16(1,2,3,4,5,6)$

$\big(-10+3(1,3,2,4,6,5)\big) \times \big(-3+1(3,1,2,6,4,5)\big) = -2+2(1,2,3,4,5,6)$

$\big(1+6(1,5,3,2,6,4)\big) \times \big(5+6(5,1,3,6,2,4)\big) = 149+96(1,2,3,4,5,6)$

Other sequences can be obtained by rescaling, switching $a$ and $b$, reversing the orders, and replacing permutations $a,b$ with $7-a,7-b$ while adjusting the other parameters accordingly.

Sketch of proof.

Using bold letters for permutations of of the numbers $1,2,\dots n$, we are looking for real solutions to this equation:

$(a+d{\bf u})(b+e{\bf v})=c+f(1,2,\dots n)$

that is

$(1,2,\dots n)=\frac{ab-c}{f}+\frac{bd}{f}{\bf u}+\frac{ae}{f}{\bf v}+\frac{de}{f}{\bf uv}$

Therefore, given $\bf u,v$, the coefficients $\frac{ab-c}{f},\frac{bd}{f},\frac{ae}{f},\frac{de}{f}$ can be computed by a standard linear regression with $(1,2,\dots n)$ as the dependent ($y$-)variable and intercept, $\bf u$, $\bf v$ and $\bf uv$ as the 4 independent ($x$-)variables. Once $\frac{bd}{f},\frac{ae}{f},\frac{de}{f}$ are known, then also $\frac{b}{e}$ and $\frac{a}{d}$ are, and these determine the coprime pairs $(a,d)$ and $(b,e)$, uniquely for $d,e>0$.

There are $n!-2$ possibilities for each of $\bf u$ and $\bf v$ (excluding the trivial $(1,2,\dots n)$ and $(n,n-1,\dots 1)$). Moreover we can assume ${\bf v}\ge {\bf u}$ (lexicographically) and also, obviously, that whenever $u_j<u_i$ for $j>i$ then $\bf v$ must satisfy $v_j>v_i$. Last, we want to avoid the singular cases ${\bf u}+{\bf v}=(n+1,n+1,\dots n+1)$. Given all these restrictions there are only $14777$ pairs $({\bf u},{\bf v})$ left for $n=6$ and $328790$ left for $n=7$. I produced all these pairs with simple awk scripts and ran the $14777+328790$ regressions with awk+shell+Rscript, looking for the cases where both $\frac{de}{f}\ne 0$ and $\text{r-squared}=1$. The search produced 8 hits for $n=6$, that is $4$ pairs of related solutions, and no hits for $n=7$.

I conjecture that there are no solutions for $n\ge 8$. The case $n=8$ is definitely within computational reach using the method above, but a better programmer than myself is needed for it. It would be easy to also find all the solutions for $n\le 5$, but I ran out of motivation.

  • $\begingroup$ Above, I a ruled out the singular cases with ${\bf u}=n+1-{\bf v}$. The 4-variate regression is singular in that case, but in theory a perfect fit (with one degree of freedom in the coefficients) could be achieved there too. Maybe there is a very short argument why that cannot be, but in any case I ruled it out by running the corresponding 3-variate regressions, with ${\bf intercept},{\bf u},{\bf uv}$ as $x$-variables, and no perfect fit was found for $n=6,7$. $\endgroup$ Oct 17 '18 at 7:39
  • $\begingroup$ Update: the regressions mentioned in my answer can mostly be replaced by much easier/faster computations of the ranks of the $5\times n$ matrices with rows given by $(1,1,\dots 1),(1,2,\dots n),{\bf u},{\bf v},{\bf uv}$; then for the matrices with rank < $5$ further checks are needed to rule out, or compute, the explicit examples. $\endgroup$ Oct 18 '18 at 8:12

From Yaakov's answer, take the second difference $(u_i-2u_{i+1}+u_{i+2})$ to remove (1,2,...,n) and the constant term. Then you have (n-2)x3 matrix $W=[D^2(u),D^2(v),D^2(uv)]$ that we want to have a null vector. So calculate $det(W^tW)$, and you need the determinant to be zero for a solution. I ran the calculations and got no solutions for 8 or 9. Case 9 took 5 hours on Matlab.

  • $\begingroup$ I do not see how this is an answer. This is more a comment on an other answer for me... $\endgroup$ Oct 19 '18 at 9:41
  • 1
    $\begingroup$ I had no points and couldn't comment . Sorry Andras. I also used this method to find the solutions in the OP $\endgroup$
    – Empy2
    Oct 19 '18 at 10:01

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.