0
$\begingroup$

Given a set of integer multiples of $a$ and $b$, $ak_1,..,ak_m, b\ell_1,...,b\ell_m$, what is the maximum number of finite sums of the multiples you can create such that no sum of all multiples of $a$ or all multiples of $b$ can be created from the sums by a finite number of sums or differences? For example. Given $ak_1, ak_2, b\ell_1, b\ell_2$ if our set of finite sums contains

$\{ak_1 + ak_2 + b\ell_1\}$

then what is the maximum number of other sums we can add to this set such that each sum contains any multiple no more than once, and we can't recover $a$ or $b$ by any finite number of sums or differences of elements of the set.

For example we can add to the singleton set above, the element $ak_1 + b\ell_1 + b\ell_2$, then there's no way to recover $a$ yet, but if we added an $ak_1 + ak_2 + b\ell_2$ to the set to total $3$ elements, then it's easily observed we can arrive at a multiple of $a$ several different ways by summing or differencing the elements. How does the maximum number of elements such that you can't solve for a multiple of $a$ or $b$, scale with $m$ and $n$?

Here's another example. Let the multiples be given by $a_1,a_2,a_3, b_1,b_2$ in the obvious way. If we start with

$$\{a_1 + a_2 + b_1\}$$

we can add to the set $$ a_1 + b_2, \\ a_1+a_3+b_3$$

and I don't think we can add any more and not have a solution to $a$ and $b$.

$\endgroup$
  • $\begingroup$ This is really hard to understand. Let me know how I can clarify. $\endgroup$ – Shine On You Crazy Diamond Aug 29 '13 at 7:16
0
$\begingroup$

In the worst case, the sums of multiples of $b$ never sum to a multiple of $a$, so we'll need the sum of $b_i$'s to be zero. Then the problem becomes finding a maximal linearly independent set of vectors in the space $\text{Span}((b_1,0,...), (0,b_2,...), (0,0,b_3,...))$ which is of course $m$ in the worst case. So we would choose $\text{min}(m,n)$. I wonder what would happen if we say that the sums are modulo $n = ab$ which is what I need.

$\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.