EXPONENTIAL GROWTH THEOREM: M(n) > 2^(0.3333 + 0.07558*n).

Veit Elser: This is interesting (still have to check the details). Any idea how to find the smallest n for which M(n)>n ? --well, to do that, you would want to find theorems giving upper bounds on M(n). If you had good enough lower & upper bounds you might solve this smallest-n problem, but even if not good enough for that, then its still a good thing. SIDE REMARKS: 1. my lower bound, since it was quite simple, can probably be improved. (I'm sure it is correct with some constants, although I could have screwed up the precise constants.) 2. the name "perfect union codes" sucks because the word "perfect" seems uncalled for. Just "union codes" would be a better name, albeit maybe not best. OK, so now let me try to produce an upper bound. Given 4 subsets A,B,C,D of the n-set, clearly AuB is different from CuD, because otherwise A would be a subset of CuD, which is forbidden by definition of perfect-union-code. Also note AuB differs from AuC since otherwise B would be contained in AuC. The number of set-pairs is m*(m-1)/2 where m=M(n), and they must all have unions which (i) differ and (ii) are subsets of {1,2,3,...,n} and (iii) are nonempty. Hence m*(m-1)/2 <= 2^n - 1. Hence UPPER BOUND THEOREM: M(n) < (-1/2) + 2^((n+1)/2). This also has exponential growth but the point is, it has only sqrt(2) not 2 as the growth factor. You could do a bit better by noting AuB must differ from CuD in at least 2 places... sort of... (several cases to treat) this should improve the bound, but not its growth factor.