Non-progressing sets

Consider the set of natural numbers N \N . Divide this set into two subsets, S 1 S_1 and S 2 S_2 , where { S 1 S 2 } = N \{ S_1 \cup S_2 \} = \N and { S 1 S 2 } = \{ S_1 \cap S_2 \} = \varnothing . Is it possible to construct S 1 S_1 and S 2 S_2 such that:

1) Neither S 1 S_1 nor S 2 S_2 contains any arithmetic progressions of any common difference and of infinite length

2) Neither S 1 S_1 nor S 2 S_2 contains any geometric progressions of any common ratio and of infinite length?

For clarification, a progression of finite length is allowed. For example, { 1 , 3 , 9 , 18... } \{1, 3, 9, 18...\} , which contains a geometric progression with common ratio 3 and length 3, is allowed. However { 2 n n N } = { 2 , 4 , 6 , . . . } \{ 2n \forall n \in \N\} = \{2, 4, 6, ... \} , which contains an arithmetic progression with common difference 2 and infinite length, is not allowed.

Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Qweros Bistoros
Aug 10, 2020

S 1 = { n N : S_1 = \{ n \in\mathbb{N} : if log 10 ( 1 + log 10 n ) \lfloor\log_{10} (1+\log_{10} n)\rfloor even } \}

S 2 = N S 1 S_2 = \mathbb{N} \setminus S_1

Julian Poon
Aug 9, 2020

Disclaimer: This is by no means a rigorous proof but just an intuition on which a proof can be built upon.

The first condition can be satisfied by having 'gaps' in both S 1 S_1 and S 2 S_2 that grow faster in size than linearly. An example of such a construction is having S 1 S_1 be the set of integers whose number of digits is odd and S 2 S_2 be the set of integers whose number of digits is even. The intuition is that for any arithmetic progression a n = a 0 + k n a_n = a_0 + kn , where k k is the common difference, there would exist an n n' such that for all n > n n > n' , the gap is larger than k k and so one of a n a_n is going to have to fall through the gap and belong to the other set.

That said, the 2nd condition can be seen similarly by noticing that for any geometric progression g n g_n , the number of prime factors counted with multiplicity follows an arithmetic progression. A construction that disallows such would satisfy the 2nd condition.

Hence the construction below satisfies both conditions:

S 1 S_1 is the set of integers whose number of prime factors, counted with multiplicity, has an even number of digits. S 2 S_2 is the set of integers whose number of prime factors, counted with multiplicity, has an odd number of digits.

Not sure but S 1 S_1 can be assigned any random natural numbers that follow the given description, which is possible because I can design an example, and S 2 = n S_2 = n ϵ \epsilon N S 1 \N - S_1

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...