2
$\begingroup$

Given positive integer $n$, we are looking for a set of $n$ positive integers $a_i$.

The following linear integer program must have only the trivial integer solution of all ones.

  • $0 \le x_i \le \frac{n}{2}$
  • $\sum x_i = n$
  • $\sum a_i x_i = \sum a_i$

One exponential example is to take $a_i=C^i$.

We experimented with an integer programming solver and couldn't find small solutions, possibly because of the law of small numbers. To our surprise taking $n=30$ and random numbers in the range $[2^{29},2^{30}]$ gave non-trivial solutions.

Q1 How small can $\max a_i$ be in terms of $n$? Can we get $\exp(o(n))$?

Q2 If $\max a_i$ is polynomial in $n$, what bound can we get for the number of solutions of the integer program?

Improve this question
$\endgroup$
7
  • $\begingroup$ Up to $n=7$ it's possible to check exhaustively and find $(1, 2)$, $(1,2,3)$, $(1,2,3,5)$, $(1,2,3,5,8)$, $(1,5,6,17,25,27)$, $(2,10,12,34,50,54,55)$. For $n=8$ I have $\max a_i \ge 75$ and will continue searching, but am not optimistic of finding a definitive answer. $\endgroup$
    – Peter Taylor
    Commented Aug 9, 2022 at 14:14
  • $\begingroup$ @PeterTaylor Thanks. How do you search? Bruteforce or ILP solver? I think I can strengthen n/2 to n/4 or even smaller bound, will edit the question. $\endgroup$
    – joro
    Commented Aug 9, 2022 at 14:52
  • 1
    $\begingroup$ Exhaustive search, but it's not quite brute force for $n \ge 6$. There's a useful optimisation from noting that the solution set $A$ must satisfy $|A + A| = \frac{n(n+1)}{2}$ (and probably higher order constraints, so maybe worth tagging additive-combinatorics). Python code. $\endgroup$
    – Peter Taylor
    Commented Aug 9, 2022 at 15:24
  • $\begingroup$ Actually, I think there must be a bug in my code. The minimal solution should have $a_1 = 1$. $\endgroup$
    – Peter Taylor
    Commented Aug 9, 2022 at 15:48
  • $\begingroup$ @PeterTaylor Thanks. I think for $n$ so small it is very difficult to distinguish polynomial from exponential. I am trying opportunistic approach: generate candidate $a_i$ and run integer program solver, but deciding more than one solution is not very feasible. $\endgroup$
    – joro
    Commented Aug 9, 2022 at 16:08

1 Answer 1

Reset to default
1
$\begingroup$

The answer to the first question is negative.

Let $A$ denote the set of weights $\{a_i\}$. Strengthen the first constraint to $0 \le x_i \le 2$.

If we have two different subsets $S_1, S_2 \subset A$ of the same cardinality, their sums must be different, since otherwise we can assign $$x_i = \begin{cases} 2 & \textrm{if } a_i \in S_1 \setminus S_2 \\ 0 & \textrm{if } a_i \in S_2 \setminus S_1 \\ 1 & \textrm{otherwise}\end{cases}$$ to get a second solution to the program.

Therefore the $\binom{n}{\lfloor n/2 \rfloor}$ subsets of half of the weights (rounded down) must all have different (positive integer) sums, so that one of those subsets must have weight at least the number of subsets, and the sum of all of the weights must be at least $\binom{n}{\lfloor n/2 \rfloor} + \binom{\lceil n/2 \rceil + 1}{2} = \Theta(n^{-1/2} 2^n)$.

Thus $\max a_i \in \Omega(n^{-3/2} 2^n)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I have some doubts about your proof, since you don't use $\sum x_i=n$. If we have $a_1+a_2+a_3=a_4 + a_5$ setting $x_1=x_2=x_3=2,x_4=x_5=0$ we have $\sum x_i=6 \ne 5$. I think the following is explicit counterexample to your claim, what is solution with {0,1,2} to: a_i=[1, 5, 25, 11, 20] $\endgroup$
    – joro
    Commented Aug 11, 2022 at 4:20
  • $\begingroup$ @joro, I think you're overlooking "of the same cardinality" in the description of $S_1, S_2$. (And on reflection I should say explicitly that $S_1 \neq S_2$). Feel free to edit if you have a clearer way to rephrase that. $\endgroup$
    – Peter Taylor
    Commented Aug 11, 2022 at 7:30
  • $\begingroup$ Indeed, you are right, missed that, sorry. $\endgroup$
    – joro
    Commented Aug 11, 2022 at 8:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .