Let $N\in\mathbb{N}$, $[N] = \{0,\dots,N-1\}$. There are $2^N$ subsets of $[N]$, so $N$ bits are enough to define a subset $S\subseteq[N]$, e.g. by Ackermann encoding.
On the other side each $S\subseteq[N]$ can be defined by a Diophantine equation $\phi_S(k,a_k,\dots, a_1, a_0)$:
$n \in S \leftrightarrow (a_k n^k + \dots + a_1 n^1)\mod N = a_0$
How can some numbers $K, A_K, \dots, A_0$ be choosen, such that every subset $S\subseteq[N]$ has a Diophantine equation $\phi(k,a_k,\dots a_0)$ defining it with
- $k \leq K$
- $a_i < 2^{A_i}$
Let $\Phi(K,A_K,\dots,A_0)$ be the set of all Diophantine equations fullfilling these conditions.
It is obvious that $\Sigma A_i $ has to be $\geq N$ while otherwise not all of the $2^N$ subsets could be defined.
So the question is more precisely:
What are the minimal numbers $K,M$ such that there are $A_K,\dots,A_0$ with $\Sigma A_i = M$ and $\Phi(K,A_K,\dots,A_0)$ defines all subsets of $[N]$?
Might $M$ be as small as $N$? If not so: how can I determine it?
For a given minimal $M$, may there be more than one $(K,A_K,\dots,A_0)$ with $\Sigma A_i = M$ such that $\Phi(K,A_K,\dots,A_0)$ defines all subsets of $[N]$?