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.
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.
