Expulsion Sets

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