Given $q \in \mathbb{N}$ and ${a_1, a_2, ...}$ where each $a_j \in \mathbb{N} \cup{\{0\}}$ define $A_p=$ {set of all finite sums of $\{a_1 ... a_p\}$ such that each $a_j$ will appear either $1$ or $0$ times}. There will be $2^{p}$ elements in $A_p$. Define $R_p$ as the set of remainders of elements of $A_p$ divided by q.

What is necessary and sufficient condition for ${a_1, a_2, ...}$ such that there exist $p$ for which $\{0,1...,q-1\} = R_p$

All constraints are welcome.


SMALL number theory person here.

First of all, the problem doesn't really depend on you taking the finite subsets. We may as well just call $A = \{ \sum_{n\in\mathbb{N}} \delta_n a_n : \mbox{$\delta_n\in\{0,1\}$ and all but finitely many $\delta_n$ are zero}\}$ and call $R$ the set of remainders of the elements of $A$ when divided by $q$. The problem is equivalent to asking whether $R = \{0,\dots,q-1\}$.

There are a few obvious necessary conditions, such as the fact that you must have $\gcd(q,a_1,a_2,\dots) = 1$. There are also a few sufficient conditions, such as (I believe):

$\textit{If $A_q$ is the set of remainders of $a_1,a_2,\dots$ when divided by $q$, then $|A_q \cap \{1,\dots,q-1\}| \ge \lceil{\frac q 2}\rceil$ is sufficient.}$

However, I don't think there is a nice (complete) solution to this problem. Here's why: if we let $A_q^*$ be the $\textit{multiset}$ of remainders of $a_1,a_2,\dots$ when divided by $q$, then deleting elements so that we have at most $q-1$ of each remainder, we have $|A_q^*| < q^2$. We are then asking whether (do you see why this is equivalent?), for each $0\le t\le q-1$, there is a sub-multiset of $A_q^*$ which sums to a number which is congruent to $t$ modulo $q$, and there are finitely many possibilities for such a number, as $|A_q^*| < q^2$. If you could even give an algorithm to solve this problem in polynomial time, I think you would show that the "subset sum problem" is in $P$ and be famous.

  • $\begingroup$ Thank you for the answer! This is further than I got. Because of the nature of the problem I stated $A_{p}$ instead of &A$. Unfortunately, I just found out that due to, again, nature of the problem, these all can be simplified to really easy conditions. (By using some other properties not stated here) Thanks for helping though!! $\endgroup$ – Vadim Jun 28 '16 at 21:30

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.