Let U denote a set closed under the commutative operation "+", meaning that if u1,u2 (not necessarily distinct) are in U, then u1 + u2 is also in U. We define an expulsion-set in U under the operation "+" as any subset A of U such that if a1,a2 are in A then a1 + a2 is NOT in A. For example, among the integers the set {3,5} is an expulsion-set under addition, because none of the integers 6=3+3, 8=3+5, 10=5+5 is in the set. Among the integers, a more natural example of an expulsion-set is the set of odd integers under addition. Among the reals, the set of negative numbers under multiplication constitutes an expulsion set. Both of these examples are maximal, because no additional elements of the background set can be adjoined while preserving the expulsion property. Another example among the integers is the set of primes under multiplication. However, this is not maximal, because we could adjoin various composites without destroying the expulsion property of the set. Given an expulsion set F of U with the operation "+", let T denote U-F, i.e., T is the complement of F in U. If this partition of the elements of U is such that the application of "+" to elements of the two subsets is as shown below F T --- --- F T F T F T then F is a special kind of an expulsion set, called a negation set. Clearly the odd integers under addition constitute a negation set, as do the negative reals under multiplication. On the other hand, the prime integers are not a negation set, because the product of a composite and a prime is not a prime. Based on these examples it might seem that an expulsion set is a negation if and only if it is maximal, but that is not the case, because while every negation is maximal, not every maximal expulsion set is a negation. For example, consider the integers congruent to +1 or -1 modulo 5 under addition. It's clear that the sum of any two such elements is congruent to -2, 0, or +2 (mod 5), so it is an expulsion set, and adjoining any number congruent to -2,0,or 2 will destroy the expulsion property, so it is maximal. However, it is not a negation set, because of sums such as 1 + 2 = -2 (mod 5). If we focus on just the maximal expulsion sets among the natural numbers under addition, we've seen that the odd numbers constitute an expulsion set, and they comprise (asymptotically) half of all the naturals. On the other hand, the integers congruent to +-1 (mod 5) comprise just 2/5 of the naturals. This raises the question: what is the most sparse maximal expulsion set among the natural numbers? If we begin with 1 and apply the greedy algorithm to generate a maximal expulsion set, i.e., if we adjoin the smallest number not already excluded at each step, then we simply arrive at the odds. To generate a sparse maximal expulsion set we need to apply an algorithm that is the opposite of greedy. At each stage, we determine the smallest number not yet excluded, but instead of adjoining that number to our set, we adjoin the SUM of that number and the highest number already in the set. This excludes the number without having to adjoin it to the set. Beginning with 1, we can apply this algorithm to give the following maximal expulsion set of natural numbers 1 4 10 17 29 44 67 91 117 148 180 215 251 288 329 371 420 471 523 576 631 687 746 806 870 935 1004 1074 1146 1221 1297 1376 1456 1538 1623 1709 1802 1896 1993 2092 2194 2300 2409 2519 2631 2753 2876 3001 3127 3255 3385 3518 3655 3796 3939 4084 4234 4387 4541 4698 4864 5032 5204 5377 5551 5729 5914 6102 6295 6490 6689 6889 7091 7294 7500 7713 7931 8157 8384 8612 8841 9072 9305 9541 9778 10020 10263 10509 10758 11015 11281 11550 11824 12101 12380 12661 12960 13261 13570 13883 ... The first differences of these numbers are as shown below: 1 3 6 7 12 15 23 24 26 31 32 35 36 37 41 42 49 51 52 53 55 56 59 60 64 65 69 70 72 75 76 79 80 82 85 86 93 94 97 99 102 106 109 110 112 122 123 125 126 128 130 133 137 141 143 145 150 153 154 157 166 168 172 173 174 178 185 188 193 195 199 200 202 203 206 213 218 226 227 228 229 231 233 236 237 242 243 246 249 257 266 269 274 277 279 281 299 301 309 313 Notice that these differences are monotonically increasing, as confirmed by the second differences shown below: 1 2 3 1 5 3 8 1 2 5 1 3 1 1 4 1 7 2 1 1 2 1 3 1 4 1 4 1 2 3 1 3 1 2 3 1 7 1 3 2 3 4 3 1 2 10 1 2 1 2 2 3 4 4 2 2 5 3 1 3 9 2 4 1 1 4 7 3 5 2 4 1 2 1 3 7 5 8 1 1 1 2 2 3 1 5 1 3 3 8 9 3 5 3 2 2 18 2 8 4 Several interesting questions about this expulsion set arise. For example, what is the asymptotic density of this set? It seems to be gradually decreasing. Also, are there infinitely many second differences equal to 1? Is there a simple proof that the first differences are always monotonic? Also, notice that there is no second difference equal to 6 in the range shown above. The first such second difference occurs at the 112th-114th terms, which are 17848 18198 18554 350 356 6 Of the first 360 terms, 17 have a second difference of 6. Why is the first appearance of 6 so late? Also, it appears that the sum of the inverses of the sparse expulsion set members converges to a value slightly above 1.572... What exactly is this value? Incidentally, as Fermat observed, no sum of two cubes is a cube, so the set of cubes {1,8,27,...} is an "expulsion set" under addition, but of course the cubes do not constitute a "maximal" expulsion set (over the integers), because it's possible to adjoin other integers to them with the result still being an expulsion set. Now, we can't adjoin 2, because 1+1=2, but we can adjoin the integer 3 to the cubes to give a larger expulsion set. This too is not maximal. We cannot adjoin 4=3+1, nor can we adjoin 5=8-3, nor 6=3+3, nor 7=8-1, nor 9=8+1, but we can adjoin 10. Continuing on is this "greedy" way, adjoining the next smallest allowable number at each step, we arrive at a maximal expulsion set containing the cubes as a subset: [1] 3 [8] 10 12 14 21 23 25 [27] 34 36 38 40 45 47 49 51 58 60 62 [64] 69 71 73 75 82 84 86... and so on. This sequence contains 176 numbers less than or equal to 1000. Clearly this is not the only maximal expulsion set containing the cubes; it is just the one that is produced by strictly applying the greedy algorithm. If we had chosen to adjoin 5 instead of 3 on the first step, and then applied the greedy algorithm thereafter, we would have produced the maximal expulsion set {1,5,8,11,14,17,20, 23,27,29,33,36,...}. Depending on our free choices, the density of the resulting sequence can vary. For example, the pure greedy algorithm gave a maximal set with 176 of the first 1000 integers, whereas if we had initially adjoined "6" to the cubes, the greedy algorithm then produces a maximal set that contains only 136 of the first 1000 integers. Even better, if we initially adjoin the integers 6, 23, and 34 to the cubes, the greedy algorithm then gives a maximal expulsion set consisting of just 108 of the first 1000 integers. What is the most sparse maximal expulsion set containing the cubes? If we initially adjoin the numbers 6, 23, 39, 112, 137, 140, and 219, we get a set that consists of just 96 of the first 1000 integers, which is just over half the size of the set given by the pure greedy algorithm. Can anyone find a set that contains fewer numbers in this range? Is there an algorithm (other than trial and error) for selecting the integers to be adjoined to the cubes in such a way as to produce the most sparse maximal expulsion set up to arbitrarily large numbers? We can also consider expulsion-sets in the context of groups. If G is any commutative group, and H is a subgroup of G, then obviously the set G-H does not contain the identity element, and so it can be partitioned into disjoint expulsion-groups, usually in multiple ways. The trivial way is just to consider each individual elements of G-H as an expulsion-group. Of course, none of these individual elements is a maximal anti-group. However, it appears that G-H can always be partitioned into disjoint *maximal* anti-groups. This is obviously true for the group of permutations of three objects, and more generally for any group of prime order. Is there a simple proof for arbitrary commutative groups?

Return to MathPages Main Menu