On the sensitivity of cyclically-invariant Boolean functions

In this paper we construct a cyclically invariant Boolean function whose sensitivity is Θ(n¹3/). This result answers nvo previously published questions. Turtin (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Ω(√n). Kenyon and Kutin (2004) asked whether for a "nice" function the product of 0-sensitivity and 1-sensitivity is Ω(n). Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is Ω;(n¹3/). We also prove that for this class of functions the largest possible gap between sensitivity and block sensitivity is quadratic.