Marcos

Posted on Friday, 17 October, 2003 - 01:57 pm:

What is the minimum

n

(if it exists), such that given a sequence of distinct naturals (

a_{n}

) (each

a_{i}

being the product of at most 2 primes and greater than 1) we can be sure that (regardless of the choice of

a_{i}

's) all sufficiently large integers can be written as

\sum a_{i} x_{i}

for some suitably chosen

x_{i}

's?

Thanks
Marcos

David Loeffler

Posted on Friday, 17 October, 2003 - 03:31 pm:

No matter what

n

is, we can take all the

a_{i}

's to have a common factor

d > 1

, and thus

\sum_{i = 1}^{n} a_{i} x_{i}

must be a multiple of

d

. (Conversely, if the

a_{i}

's are coprime, there exist

x_{i}

such that

\sum_{i = 1}^{n} x_{i} a_{i} = 1

, and we can obviously now express all integers by multiplying this through.)

David

Marcos

Posted on Friday, 17 October, 2003 - 09:02 pm:

Thanks,
I noticed the first point shortly after I posted.
For the second point what happens if we restrict ourselves to x_i > 0?

David Loeffler

Posted on Friday, 17 October, 2003 - 11:30 pm:

Still works for all sufficiently large integers. Obviously if you can do any integer between 1 and

a = \min a_{i}

, you can do everythin by adding copies of

a

; this is a finite number of cases, so there is some fixed lower bound

- M

on all the

x_{i}

's you are ever going to want to use in representing an arbitrary positive number.

Define $K = M \sum a_{i}$ . Then for any $m > K$ , we can write $m = K + m < quote / >$ . If $m < quote / > = \sum x_{i} a_{i}$ then $m = \sum (M + x_{i}) a_{i}$ and $M + x_{i} \geq 0$ .

Obviously we can sharpen this upper bound a great deal. In case $n = 2$ there is a rather neat formula that gives the size of the largest $m$ that you can't represent in this way; for $n > 2$ it gets a bit messy as you have various cases according to which subsets of the $a_{i}$ have common factors.

David

Marcos

Posted on Saturday, 18 October, 2003 - 12:15 pm:

Thanks,

I'm not sure I fully understand.

How can we be sure that $m < quote / > = \sum x_{i} a_{i}$ ?

And did you mean "this lower bound" in the last paragraph or am I more confused than I think?

Marcos

David Loeffler

Posted on Saturday, 18 October, 2003 - 06:02 pm:

OK. I'll rephrase that. There exist

x_{i}

such that

\sum x_{i} a_{i} = m < quote / >

and

x_{i} > - M

all

i

And yes, I did mean 'lower bound'!

David

Marcos

Posted on Sunday, 19 October, 2003 - 08:33 am:

Thanks I understand it now (actually it seems my problem was that -M)

Marcos

Marcos

Posted on Sunday, 19 October, 2003 - 08:38 am:

One last thing: Can I have some hints on discovering/deriving the neat formula for the n=2 case?

Marcos

David Loeffler

Posted on Sunday, 19 October, 2003 - 09:53 pm:

trial and error is often a good approach!