Last Thursday I wrote
Lemma 1: Given m>=3, let e be 1 if m is odd and 2 if m is even. For k>=1 we have
U(m, (km-1)(m-e)/2) >= (km-1)/2k = m/2 - 1/2k.
Now I have both a counterexample and a generalization!
Proof of Lemma 1: We use the multiset
(m/2 - 1/2k) * ek(m-e), m/2 * (km-2ek-1)(m-e), (m/2 + 1/2k) * ek(m-e).
Well, notice that the middle multiplicity is (k(m-2e)-1)(m-e). For m=4 (and e=2), this is negative! Indeed, taking k=1 would give U(4, 3) >= 3/2, while we already know U(4, 3) = 1. This isn't a problem for my asymptotic theorem, though, since we've already got an explicit formula for U(4, 2k+1), and it tends to 2. But I can allow a more general value of e and a plus or minus sign after "km". This gives Proposition. Take m>=3, k>=1, and e>=1 with k(m-2e)+-1>=0. If (km+-1)(m-e) is even, we have U(m, (km+-1)(m-e)/2) = (km-1)/2k = m/2 - 1/2k. If (km-1)(m-e) is odd, we have U(2m, (km+-1)(m-e)) = (km-1)/k = m - 1/k. Proof. If (km+-1)(m-e) is odd, everything goes through, but then one of the inputs to U is a half-integer, and we can just rescale by 2. So we'll assume it's even. The upper bound is a special case of the bound I just posted in my previous note. First, we have [(km+-1)(m-e)/m] = [k(m-e) +- 1 -+ e/m] = k(m-e) for "+" or k(m-e)-1 for "-". For "+" we have U(m, (km+1)(m-e)/2) <= m - ( (km+1)(m-e)/2 ) /(k(m-e)) = m - (km+1)/2k = (km-1)/2k, while for "-" we have U(m, (km-1)(m-e)/2) <= ( (km-1)(m-e)/2 ) /(k(m-e)-1 + 1) = (km-1)/2k. The proof of the lower bound is exactly the same as last week's proof, mutatis mutandi, though I'll reproduce it. We use the multiset (m/2 - 1/2k) * ek(m-e), m/2 * (k(m-2e)+-1)(m-e), (m/2 + 1/2k) * ek(m-e). It is clear that the smallest part has the desired size and that the parts can be paired up to give (km+-1)(m-e)/2 copies of m. Also, all the parts of size m/2 +- 1/2k) can be added together to give e copies of (km+-1)(m-e)/2. Finally, we have m/2 * (km-2ek+-1) + (m/2 -+ 1/2k) * ek = km^2/2 - ekm/2 +- m/2 -+ e/2 = (km+-1)(m-e)/2, so the rest of the pieces can be combined to make m-e more copies of (km+-1)(m-e)/2, and this is a valid common refinement. This proves the lower bound. QED Again, it is easy to show that the partition I give is optimal, in the sense of lexically maximizing the sorted list of sizes, once you combine as many m/2's as possible into m's. In fact, if km is odd, you can combine all of them, and the optimal partition is (m/2 - 1/2k) * ek(m-e), (m/2 + 1/2k) * ek(m-e), m * (k(m-2e)-1)(m-e)/2, while if km is even, you have to leave (m-e) of them unpaired, and the optimal partition is (m/2 - 1/2k) * ek(m-e), m/2 * (m-e), (m/2 + 1/2k) * ek(m-e), m * (k(m-2e)-2)(m-e)/2. David P. Moulton