# A necessary and sufficient condition for $(x_1,…,x_n)$ to be a permutation of $(1,…,n)$

Is there an easy proof of the following statement?

$$\forall$$ $$n>0 \in \mathbb N$$, $$\exists$$ $$a\geq0 \in \mathbb N$$ such that for any set of integers $$(x_1,...,x_n)$$ and $$1\leq x_i \leq n$$:

$$(x_1,\dotsc,x_n)$$ is a permutation of $$(1,\dotsc,n)$$ if and only if:
$$(x_1+a)\dotsb(x_n+a)=(1+a)\dotsb(n+a)$$.

I checked the property for $$n=1,2,\dotsc,9$$ and got the (minimal) values $$a=0,0,0,1,2,5,6,9,10$$.

If the property is true, what can we say about the function $$a(n)$$?

• I don't think there is an a. In particular, a =10 does not work for n=9 because 16*18=12*24. Do you mean something else? (Now I see x_I less than n. I still think this will fail for n large enough.) Gerhard "Factorization Is Perhaps Too Weak?" Paseman, 2019.07.16. – Gerhard Paseman Jul 16 at 21:54
• For $n=9$ is there an other solution than $(1,2,...,9)$ to the equation $(10+x_1)...(10+x_9)=11.12....19$ ? – JPF Jul 16 at 22:05
• If you put [0], 0, 0, 1, 2, 5, 6, 9, 10 into oeis.org it spits out A065890 Number of composites less than the n-th prime (I skipped the first zero). Does that work for bigger $n$ as well? – quarague Jul 17 at 7:32
• @quarague : I'm not sure A065890 works. Here is $a=(0,0,0,1,2,5,6,9,10,16,18,27,...)$ – JPF Jul 17 at 11:50
• @JPF: I took a liberty to add this sequence as A309242 (currently in draft form). – Max Alekseyev Jul 17 at 21:29

Let $$p_1, \dots, p_n$$ be distinct prime numbers each greater than $$n$$. By the Chinese remainder theorem, there exists an $$a$$ such that $$a + i$$ is divisible by $$p_i$$ for $$1 \le i \le n$$. Since $$p_i > n$$, it follows that if $$1 \le j \le n$$ and $$p_i$$ divides $$a + j$$ then $$i = j$$. In particular, if $$(x_1, \dots, x_n)$$ lie in this range and $$\prod_{i=1}^n (a + x_i) = \prod_{i=1}^n (a + i)$$ then for each $$i$$ the product is divisible by $$p_i$$ so there is some $$j$$ such that $$x_j = i$$. Thus it's a permutation.

This proves existence but I'd expect the value of $$a$$ you get this way to be far from optimal.

• neat! nice proof! – JPF Jul 17 at 22:58

Start by thinking about $$\prod_{k=1}^n (x_k+\alpha)$$ as the polynomial $$f_{x_1,\dots,x_n}(\alpha)$$ in $$a$$ with roots at $$-x_1$$,...,$$-x_n$$. Then the equality of polynomials $$f_{x_1,\dots,x_n}(\alpha)=f_{1,2,\dots,n}(\alpha) \ (=:\sum_{k=0}^n c_k\alpha^k)\quad\tag{1}$$ holds iff $$x_1,...,x_n$$ is a permutation of $$1,2,...,n$$. Now, in order to answer the 1st question it suffices to find a value $$a$$ of $$\alpha$$ so that the equality of values of these polynomials at $$a$$ implies (1). That such $$a$$ exists follows from a standard argument involving thinking of a $$\sum_{k=0}^n b_k a^k$$, with $$a>\max_k b_k$$ as a number in base $$a$$. Thus, it suffices to choose $$a>\max_k c_k$$, with $$c_k$$ as in (1).

EDIT2: more precisely, $$a$$ must be bigger than any coefficient of $$f_{x_1,\dots,x_n}$$, which are bounded from above by the maximum of the coefficients of $$f_{n,n,\dots,n}(x)=(x+n)^n$$, i.e. a function of $$n$$ alone. E.g. it suffices to take $$a\geq f_{n,n,\dots,n}(1)=(n+1)^n$$.

EDIT: As pointed out my Max Alekseyev in the comment, $$c_k$$ are Stirling numbers of the first kind, and $$\max_k c_k$$ is given by A065048(n). There is no explicit formula known for the latter.

Finding out the minimal $$a$$ for each $$n$$ appears to be a much harder problem.

• $\max_k c_k =~$A065048(n). – Max Alekseyev Jul 17 at 11:48
• Btw, we can bound $$n!=c_0~\leq~ \max_k c_k ~\leq~ f_{1,\dots,n}(1) = (n+1)!.$$ – Max Alekseyev Jul 17 at 12:43
• @Dima Pasechnik: it took me a while to really understand it, but that's a smart proof using only polynomials properties! Now, the questions of the minimal value of a and why $a_n$ is increasing (conjecture) remain open. – JPF Jul 21 at 17:39
• @Dima Pasechnik: your proof holds in the same way for $(1+x_1a)(1+x_2a)\cdots(1+x_na)=(1+a)(1+2a)\cdots(1+na)$ The sequence of a for $n\geq 2$ is $a=(1,1,1,2,2,3,4,4,4,6,6,6,6,9,9,9,10,10,10,10,12)$ – JPF Jul 23 at 22:14
• @JPF - are you saying that $a$ will be the same for any $n>1$ ? – Dima Pasechnik Jul 25 at 8:09

UPDATE at the end I conjecture an upper bound $$a(n) \leq \lfloor (\frac{n-1}{2})^2 \rfloor$$ which satisfies a stronger property.

• Consider instead cases of $$\prod_1^k(x_i+a)= \prod_1^k(y_i+a) \tag{*}$$ where the multisets $$\{x_1,\cdots ,x_k\}$$ and $$\{y_1,\cdots ,y_k\}$$ are disjoint. I'll assume the elements are listed in increasing order. To stick to the OP, add the requirement that the $$y_i$$ are distinct. For example, $$a(5)\geq 2$$ because there are counter-examples to $$a=0$$ and $$a=1.$$ $$(2+0)(2+0)(3+0)(2+0)(5+0)=(1+0)(2+0)(3+0)(4+0)(5+0)$$ $$(2+1)(2+1)(3+1)(3+1)(4+1)=(1+1)(2+1)(3+1)(4+1)(5+1)$$ Cancel out common factors to to see that sources of these counter-examples are $$1\cdot 4=2 \cdot 2$$ and $$2 \cdot 6=3 \cdot 4.$$ In the other direction, one can pad an example of $$(*)$$ by changing the right-hand side to $$\prod_1^n(i+a)$$ and adding on the left the same new factors. Here $$n$$ could be $$\max(x_k,y_k)$$ or anything larger.

• The final remark exhibits that $$a(n)$$ is non-decreasing.
• Of the values reported so far the larger ones are somewhat close . $$a(14)=33 \lt 42=\lfloor (\frac{13}2)^2\rfloor$$

$$a(15)=45 \lt 49$$ Here is a potential conjecture. It is false. I mention it only because the counter-examples are lovely.

Suppose that the value of $$\prod_{i=1}^n (a + x_i) -\prod_{i=1}^n (a + y_i)$$ is independent of $$a$$. Does that mean that the shared value is $$0$$ and $$x_i=y_i?$$

The answer is no because of ideal solutions to the Prouhet-Tarry-Escott problem. For example $$2^k+3^k+7^k=1^k+5^k+6^k$$ for $$k=0,1,2.$$ This explains the observation that $$(2+a)(3+a)(7+a)=42+41a+12a^2+a^3$$ $$(1+a)(5+a)(6+a)=30+41a+12a^2+a^3$$ so the two always differ by $$12.$$

The OP is to find the first $$a$$ which satisfies the condition.

for any set of integers $$(x_1,...,x_n)$$ and $$1\leq x_i \leq n$$:
$$(x_1,\dotsc,x_n)$$ is a permutation of $$(1,\dotsc,n)$$ if and only if:
$$(x_1+a)\dotsb(x_n+a)=(1+a)\dotsb(n+a)$$.

I will instead seek the last $$a$$ which fails the property. This (plus $$1$$) is then an upper-bound on $$a(n).$$

I will conjecture that for fixed $$n,$$ this last bad $$a$$ is at most $$(\frac{n-1}{2})^2.$$ My justification is sketchy and would probably benefit from classical inequalities.

By my comments above, given $$n$$, a particular $$a$$ is bad if there is $$k$$-member subset of $$\{a+1,\cdots ,a+n\}$$ and a disjoint multiset of $$k$$ elements from the same set which have the same product.

I think that the extreme case is $$k=2$$ with $$a+1=s^2$$ and $$n=2s+1$$ so $$a+n=(s+1)^2$$

Then $$s^2\cdot (s+1)^2=(s^2+s)\cdot (s^2+s).$$

Here are plots showing that $$a=18$$ and $$a=45$$ are good for $$n=11$$ at least as far as $$k=2.$$

The first shows that there are no solutions of $$18\cdot 29=u \cdot v$$ with $$19 \leq u,v \leq 28$$ The hyperbola $$xy=19\cdot 28$$ (on this interval) snakes through the lattice points without hitting any of them. That isn't surprising given that $$19$$ is prime.

The second shows the hyperbola $$xy=45\cdot 56.$$ Along the diagonal are the lattice points $$(x,101-x).$$ The diagonal below is the closest lattice points. But the hyperbola stays above that closest diagonal.Hence there are no solutions of $$u \cdot v=2520$$ in that range other than the endpoints.

The $$a$$ chosen for these is larger than needed but it makes the plot easier to see.

In the cases mentioned above such as $$25\cdot 36=30 \cdot 30$$ , the hyperbola is tangent to the lower diagonal and the contact point is a lattice point.

I'll suffice to end this sketch by saying, without justification, that for larger $$k$$ the surface $$x_1x_2\cdots x_k=y_1y_2\cdots y_k$$ lies below the hyperplane $$x_1+x_2+\cdots +x_k=y_1+y_2+\cdots + y_k$$ which is rich in lattice points. If the numbers are large enough then that surface stays close enough to the hyperplane that it never touches the parallel hyperplane of nearest lattice points. It seems as if “large enough” decreases with $$k$$. A study of the known bad a values might make that clear. Do any of the known counter examples use more than $$k=2?$$

The exact value of $$a(n)$$ in the OP depends on the distribution of fairly composite integers in certain intervals of length $$n.$$ That is not very predictable.However I think the simplifications here might make the searches easier. The values reported so far seem close to the bound.

• The conjecture fails for $n=21$, where the smallest suitable $a$ is $108 > (\frac{21-1}2)^2$. – Max Alekseyev Jul 18 at 18:18

Not a solution but too long for a comment.

I wrote a octave/matlab program (below) that until n=9 loops over all n-element multisets with integers from 1 to n writes down the polynomial equation and computes the largest root. This gives an upper bound to the sequence. However this upper bound seems to be far off. Hence the problem can not be solved purely algebraically.

for n=2:8;
n

%sets of all integer vectors of length m whos entries sum to n-1
A=cell(n,n+1);

for i=1:n+1
A{1,i}=i-1;
end

for i=2:n
for j=1:n+1
A{i,j}=zeros(0,i);
for k=0:j-1
A{i,j}=[A{i,j};k*ones(size(A{i-1,j-k},1),1) A{i-1,j-k}];
end
end
end

Ann=A{end,end};

%remove the 1,2,...,n set
is=all(Ann==1,2);
Ann(is,:)=[];

%computations of zeros

%standard polynomial (a+1)...(a+n)
p0=1;
for i=1:n
p0=conv(p0,[1 i]);
end

%loop through all combinations

%tolerance
tol=1e-8;

%maximal real root
amax=-inf;

%corresponding sets
s=zeros(0,n);

%corresponding polynomials
ps=zeros(0,n+1);

for i=1:size(Ann,1)

%create polynomial
p=1;

for j=1:n
for k=1:Ann(i,j)
p=conv(p,[1 j]);
end
end

pdiff=p-p0;

a=roots(pdiff(2:end));

%maximal real roots
a=max(a(abs(imag(a))<tol));

if a>amax+tol
amax=a;
ps=pdiff;
s=Ann(i,:);
elseif abs(a-amax)<tol
ps=[ps;pdiff];
s=[s;Ann(i,:)];

end

end

amax
ps
s
end

• I don't think "hence the problem cannot be solved purely algebraically" follows. – LSpice Jul 17 at 19:25