1
$\begingroup$

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ such that we always have $\pi(S) \ne \pi(S')$. For example, we can define $a_i = 2^i$. This function satisfies the property because for each $A \subseteq N$, $\pi(A)$ uniquely represents an integer written in base 2. However, in this function $a_i$ is bounded above by $\mathcal{O}(2^n)$. I am looking for a function such that $|a_i|$ and $\frac{1}{|a_i|}$ are bounded above by a polynomial. As an example that does not satisfy this last condition we can consider $a_i = 2^{i-n}$. It would be great to know different functions that satisfy this property. I will try to proof the uniqueness myself (if it is not so difficult!), so please let me know if you are aware of such functions.

$\endgroup$
  • 2
    $\begingroup$ You can choose $n$ random numbers between $0$ and $1$, and almost surely all sums will be different. If you want an explicit example, you can take $a_i = \pi^i/\lceil \pi^i \rceil$. $\endgroup$ – Yuval Filmus Oct 25 '18 at 4:09
  • $\begingroup$ I'm not writing any answer, you can go ahead. $\endgroup$ – Yuval Filmus Oct 25 '18 at 5:32
3
$\begingroup$

There are many functions that satisfy your condition. Here are a few.

  1. $a_i=1+c^{-i}$, for some constant $c\ge 2$.
  2. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer between 1 and $p_i-1$.
  3. $a_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=e$ or $\alpha=0.110001000000000000000001\cdots$, an Liouville number. (Yuval's method)
  4. $a_i=c_1b_i+c_0$, where $b_i>0$ is such a function and $c_1, c_0$ are positive constant.
  5. One can choose random numbers between a positive constant $c_0$ and 1, which should satisfy the requirement with probability one. The issue then is how to select/implement a random number generator and detect the outliers, which may or may not be trivial. (Yuval's method)

For the first three methods, the constant 1 can be replaced by some kind of polynomial of $n$. For example, a nonzero polynomial of $n$ with nonnegative integer coefficients.

These functions should get you going. If you find more ways, you can update this answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.