# Product of arithmetic progressions

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

• 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$. Oct 17 '18 at 7:39
• 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. 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.

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