Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: How to check whether an infinite set is closed under addition?

• To: mathgroup at smc.vnet.net
• Subject: [mg124364] Re: How to check whether an infinite set is closed under addition?
• From: Mobius ReX <aoirex at gmail.com>
• Date: Tue, 17 Jan 2012 03:35:17 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <201201150951.EAA19688@smc.vnet.net> <C9FCBB38-0E20-478B-97BC-BD57313E080F@mimuw.edu.pl>

Dear Andrzej,

That's very cool.
Just one minor fix when Length[base]==2,

test2Q[base_List] :=
 If[Length[base] > 2,
  Complement[
    Select[Total[Subsets[Most[base], {2}], {2}], # <= Last[base] &],
    base] == {}, True]

Previously I used FindInstance to test if there is any integer
solution to all of the equations of n_i
Sum[a_i*n_i ,{i,1,g}]=a_k for any a_k  in A

I verified that your code has better performance than mine. Great Thanks.

Best regards,
Rex


On Mon, Jan 16, 2012 at 3:09 AM, Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote:
>
> On 16 Jan 2012, at 08:50, Andrzej Kozlowski wrote:
>
>>
>> On 16 Jan 2012, at 02:07, Mobius ReX wrote:
>>
>>> Sorry the condition of a set A to be closed under addition should be
>>> `Sum[a_i*n_i ,{i,1,g}] =E2=88=88 A` for any non-negative integer `n_i`, =C2 and a_i =E2=88=88 A.
>>>
>>> On Sun, Jan 15, 2012 at 5:04 PM, Mobius ReX <aoirex at gmail.com> wrote:
>>>> Sorry the condition of a set A to be closed under addition should be
>>>> `a_i*n + a_j*m =E2=88=88 A` for any positive integers `n` and `m` for any a_i =E2=88=88 A.
>>
>>
>> Of course you are right. Essentially you =C2 can use the previous code but you need to add to the base all the multiples of each element of the base that are less than the largest element of the base. In other words, I think the following should work:
>>
>> closedQ[base_List] :=
>> Module[{b = Union[Flatten[Table[# i, {i, Last[base]/#}] & /@ base]]},
>> =C2  Complement[
>> =C2  =C2 Select[Total[Subsets[Most[b], {2}], {2}], # <= Last[base]&],
>> =C2  =C2 base] == {}]
>>
>>
>> For example:
>>
>> closedQ[{2, 3, 5, 8}]
>>
>> False
>>
>> Andrzej
>>
>> closedQ[{2, 3, 4, 5, 6, 7, 8}]
>>
>> True
>>
>> I am again assuming that the base is sorted.
>>
>> Andrzej
>
>
> Actually, this is not the most efficient way to do this. In fact it is better to combine two tests. The first checks if the base has the property that if a is an element then n a is also an element of the base (as long as n a is less than the last element of the base).
>
> This can be checked as follows:
>
>
> test1Q[base_] :=
> =C2 Module[{b = Flatten[Table[# i, {i, Last[base]/#}] & /@ base]},
> =C2 Complement[b, base] == {}]
>
> The second test is the original one:
>
> test2Q[base_List] :=
> =C2 Complement[
> =C2  Select[Total[Subsets[Most[base], {2}], {2}], # <= Last[base] &],
> =C2  base] == {}
>
> Now we define closedQ:
>
> closedQ[base_List] := test1Q[base] && test2Q[base]
>
> Again:
>
> closedQ[{2, 3, 5, 8}]
>
> False
>
> closedQ[{2, 3, 4, 5, 6, 7, 8}]
>
> True
>
>
> This ought to be faster than my previous version since it does not perform the same checks twice (as the old version does).
>
> Andrzej

• References:
  • How to check whether an infinite set is closed under addition?
    • From: Rex <aoirex@gmail.com>