boofun.analysis.fkn

FKN Theorem and related results about functions close to dictators.

The FKN (Friedgut-Kalai-Naor) Theorem states that Boolean functions with small total influence are close to dictator functions or constants.

References: - Friedgut, Kalai, Naor: “Boolean Functions whose Fourier Transform is

Concentrated on the First Two Levels” (2002)

• O’Donnell: “Analysis of Boolean Functions” Chapter 2

Functions

analyze_dictator_proximity(f)	Comprehensive analysis of how close f is to dictator functions.
closest_dictator(f)	Find the dictator (or negated dictator) closest to f.
distance_to_dictator(f, i)	Compute distance of f to the i-th dictator function.
distance_to_negated_dictator(f, i)	Compute distance of f to the negated i-th dictator: 1 - x_i.
fkn_theorem_bound(f)	Apply the FKN Theorem to bound distance to dictators.
is_close_to_dictator(f[, epsilon])	Check if f is ε-close to some dictator function.
spectral_gap(f)	Compute the spectral gap: 1 - max_i |f̂({i})|.

boofun.analysis.fkn.distance_to_dictator(f: BooleanFunction, i: int) → float

Compute distance of f to the i-th dictator function.

Distance = Pr[f(x) ≠ x_i] = (1 - f̂({i})) / 2

Parameters:

• f – Boolean function

• i – Variable index

Returns:

Fraction of inputs where f differs from dictator on x_i

boofun.analysis.fkn.distance_to_negated_dictator(f: BooleanFunction, i: int) → float

Compute distance of f to the negated i-th dictator: 1 - x_i.

Parameters:

• f – Boolean function

• i – Variable index

Returns:

Fraction of inputs where f differs from NOT(x_i)

boofun.analysis.fkn.closest_dictator(f: BooleanFunction) → Tuple[int, float, bool]

Find the dictator (or negated dictator) closest to f.

Returns:

Tuple of (variable_index, distance, is_negated)

Example

>>> f = bf.majority(3)
>>> idx, dist, neg = closest_dictator(f)
>>> print(f"Closest to {'NOT ' if neg else ''}x_{idx}, distance={dist}")

boofun.analysis.fkn.fkn_theorem_bound(f: BooleanFunction) → Dict[str, Any]

Apply the FKN Theorem to bound distance to dictators.

FKN Theorem: Let f: {-1,1}^n → {-1,1} with E[f] = 0 (balanced). Then:

dist(f, dictators) ≤ O(I[f])

More precisely, if W^{≤1}[f] = 1 - ε (most weight on degree ≤1), then f is O(ε)-close to a dictator or constant.

Returns:

• ‘total_influence’: I[f]

• ’degree_1_weight’: W^{=1}[f] (weight on degree 1)

• ’low_degree_weight’: W^{≤1}[f]

• ’fkn_bound’: Upper bound on distance to dictator

• ’closest_dictator’: (var, distance, is_negated)

• ’is_close_to_dictator’: Boolean

Return type:

Dict with

boofun.analysis.fkn.is_close_to_dictator(f: BooleanFunction, epsilon: float = 0.1) → bool

Check if f is ε-close to some dictator function.

Parameters:

• f – Boolean function

• epsilon – Distance threshold

Returns:

True if f is within epsilon of some dictator

boofun.analysis.fkn.spectral_gap(f: BooleanFunction) → float

Compute the spectral gap: 1 - max_i |f̂({i})|.

Small spectral gap → close to dictator. Large spectral gap → far from all dictators.

Returns:

Spectral gap value in [0, 1]

boofun.analysis.fkn.analyze_dictator_proximity(f: BooleanFunction) → Dict[str, Any]

Comprehensive analysis of how close f is to dictator functions.

Returns:

Dict with detailed proximity analysis including FKN bounds, spectral information, and recommendations.