Logic Seminar
Linda Brown WestrickUniversity of Connecticut, Storrs
Increasing dimension s to dimension t with few changes
We show that for every s<t in [0,1], every sequence of effective dimension s can be changed on density at most H−1(t)−H−1(s) of its bits in order to obtain a sequence of effective dimension t, where H is the Shannon binary entropy function. This is the infinitary analogue of a known finite result, but passing from the finite to the infinite requires, among other techniques, a convexity argument with a puzzling dichotomy. The density bound is the best possible, and this answers a question which was left open at the time of previous presentations on this subject. Joint work with Noam Greenberg, Joe Miller and Sasha Shen.