About the problem

Given a Boolean function \(f\), it is known that the sensitivity of \(f\), denoted \(s(f)\), is at least the square root of its degree, denoted \(\deg(f)\), and that this bound is tight.

The upper bound is less clear. It is known that \(s(f) \le \bigl(\deg(f)\bigr)^2\), with recent work improving this by a constant \(< 1 (\approx 0.83)\). There is also an explicit construction with \(s(f) = \bigl( \deg(f) \bigr)^{\log(6)/\log(3)}\). Here the exponent is \(\approx 1.63\).

The goal of this problem is to find a novel construction that improves on this bound.

Read more here.

Prompt

Construct a multilinear, integer-coefficient function P, on n variables, with 1 < n ≤ 100, with degree deg(P) > 1, that is Boolean on the cube, i.e., P(x) = 0 or 1 for all x in {0,1 }^n, and that has

|P(0, ..., 0) - P(1, 0, ..., 0)| + |P(0, ..., 0) - P(0, 1, 0, ..., 0)| + ... + |P(0, ..., 0) - P(0, ..., 0, 1)| = deg(P)^a

for some a > log(6)/log(3).

Provide your answer as an expression using variables like x1, x2, etc. For operators use +, -, and *. You may also use parentheses. Example: x1 + x2 + x3 - (x1*x2 + x1*x3 + x2*x3) + x1*x2*x3