# solution to unique representation problem that is less than exponential order

Given $$0< n \in \mathbb{N}$$ and $$x_1,\cdots ,x_n \in \mathbb{Z}$$ such that $$x_i for all $$i.

Let $$y_i \in \{x_1,\cdots,x_n\}$$ for all $$1\leq i\leq n$$ such that $$y_i \leq y_j$$ for all $$i.

So the meaning is $$y_i$$ (are not necessarily different) for examples : $$y_1=y_2 =x_1$$.

Find $$x_1,\cdots,x_n$$ such that :

1. $$\sum \limits_{i=1}^{n} y_i = k \sum \limits_{i=1}^{n} x_i$$ for $$k\in \mathbb{Z}$$ iff $$k=1$$ and $$y_i=x_i$$

2. $$|x_i| \leq poly(n)$$ or $$|x_i| \leq quasi-poly(n)$$ or even $$|x_i| \leq sub-exp(n)$$ but not $$|x_i| \leq exp(n)$$

the first condition is the main idea i am looking for, the second condition is to omit "simple" exponential solution for instance $$x_i = n^{i}+ n^{n+1}$$

Is there such $$x_1,...,x_n$$ that satisfies these $$2$$ conditions ?

Examples :

1. $$x_1=1,x_2=2,x_3=3,x_4=4$$ is not valid solution for $$n=4$$ because $$y_1=y_2 = 1$$ and $$y_3=y_4=4$$ and so $$y_1+y_2+y_3+y_4 = x_1+x_2+x_3+x_4$$ but for instance $$y_2\not= x_2$$

2. $$x_1 = 5,x_2=10,x_3=15,x_4= 90$$ and let $$y_1=y_2=y_3 =y_4 = 90$$ and so $$y_1+y_2+y_3+y_4 = 3(x_1+x_2 +x_3+x_4)$$ and $$y_1 \not=x_1$$ so this is also not valid solution for $$n=4$$

3. $$x_1 = 1,x_2= 2,x_3 = 4,x_4 =8$$ does satisfy the first condition but if the method for finding such numbers $$x_1,..., x_n$$ is of exponential order then the second condition is violated.

Edit : if we have $$x_1,...,x_n \in \mathbb{N_{>0}}$$ then we can make a new set of numbers $$X_1,...,X_n$$ such that $$X_i = x_i+ x_n$$ and so $$n X_n > X_1+...+X_n> n X_1>0$$ and that $$\frac{n X_n}{n X_1} = \frac{X_n}{X_1} = \frac{2x_n}{x_n+x_1} < \frac{2x_n}{x_n+1} < \frac{2x_n}{x_n} =2$$ thus the ratio between the biggest of the summation and the smallest of the summation is $$>0$$ and $$<2$$ so in this case $$k$$ can only be $$1$$.

thus the question is reduced to find $$X_1,...,X_n$$ such that $$Y_i \in \{X_1,...,X_N\}$$ such that $$X_i < X_j$$ and $$Y_i\leq Y_j$$ for every $$i and $$a_i \in \{0,1,...,n\}$$ and if $$\sum \limits_{i} a_i Y_i = \sum \limits_{i} X_i$$ and $$\sum \limits_{i} a_i=n$$ then $$a_i = 1$$ for all $$i$$ and $$Y_i =X_i$$ ?

The first condition can’t be satisfied by any $$x_1, \dotsc, x_n$$ that has two size-$$\lfloor n/2\rfloor$$ subsets $$A, B$$ with the same sum, because one can take $$x_1, \dotsc, x_n$$, remove the elements of $$A$$, insert the elements of $$B$$ (in sorted order), and get $$y_1, \dotsc, y_n$$ such that $$\sum x_i = \sum y_i$$. (For example, $$x_1, …, x_7 = 1, 2, 3, 10, 16, 19, 22$$ doesn’t work because $$1 + 10 + 16 = 2 + 3 + 22$$ and we can take $$y_1, …, y_7 = 2, 2, 3, 3, 19, 22, 22$$.)
Therefore, the $$\binom{n}{\lfloor n/2\rfloor}$$ sums of the size-$$\lfloor n/2\rfloor$$ subsets of $$\{x_1, \dotsc, x_n\}$$ must all be distinct integers. So at least one of these sums must have absolute value at least $$\frac12\left(\binom{n}{\lfloor n/2\rfloor} - 1\right)$$, which means one of the $$|x_i|$$ must be at least $$\frac{1}{2\lfloor n/2\rfloor}\left(\binom{n}{\lfloor n/2\rfloor} - 1\right) = Θ(2^n n^{-3/2})$$, which is exponential in $$n$$.