What's the maximum number of sums of $ak_1,..,ak_m, b\ell_1,...,b\ell_m$ needed to solve for $a$ or $b$?

38 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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.