MathDB
ICMC 2018/19 Round 2, Problem 4

Source: Imperial College Mathematics Competition 2018/19 - Round 2

August 7, 2020
college contestsfunction

Problem Statement

Let f:{0,1}n→{0,1}⊆Rf:\{0, 1\}^n \to \{0, 1\} \subseteq \mathbb{R} be a function. Call such a function a Boolean function. Let ∧\wedge denote the component-wise multiplication in {0,1}n\{0,1\}^n. For example, for n=4n = 4, (0,0,1,1)∧(0,1,0,1)=(0,0,0,1).(0,0,1,1) \wedge (0,1,0,1) = (0,0,0,1).
Let S={i1,i2,…,ik}⊆{1,2,…,n}S = \left\{i_1,i_2,\ldots ,i_k\right\} \subseteq \left\{1,2,\ldots ,n\right\}. ff is called the oligarchy function over SS if f(x)=xi1,xi2,…,xik  (with the usual multiplication),f (x) = x_{i_1},x_{i_2},\ldots,x_{i_k}\ \text{ (with the usual multiplication),}
where xix_i denotes the ii-th component of xx. By convention, ff is called the oligarchy function over ∅\emptyset if ff is constantly 1.
(i) Suppose ff is not constantly zero. Show that ff is an oligarchy function if and only if ff satisfies f(x∧y)=f(x)f(y), ∀x,y∈{0,1}n.f(x\wedge y)=f(x)f(y),\ \forall x,y\in\left\{0,1\right\}^n. Let YY be a uniformly distributed random variable over {0,1}n\left\{0, 1\right\}^n. Let TT be an operator that maps Boolean functions to functions {0,1}n→R\left\{0, 1\right\}^n\to\mathbb{R}, such that
(Tf)(x)=EY(f(x∧Y)), ∀x∈{0,1}n(Tf)(x)=E_Y(f(x\wedge Y)),\ \forall x\in\left\{0,1\right\}^n
where EY()E_Y() denotes the expectation over YY. ff is called an eigenfunction of TT if ∃λ∈R\{0}\exists\lambda\in\mathbb{R}\backslash\left\{0\right\} such that (Tf)(x)=λf(x), ∀x∈{0,1}n(Tf)(x)=\lambda f(x),\ \forall x\in\left\{0,1\right\}^n
(ii) Prove that ff is an eigenfunction of TT if and only if ff is an oligarchy function.
Back to ProblemsView on AoPS