boofun.families

Boolean Function Families - Parameterized families that grow with n.

This module provides tools for: 1. Defining function families (Majority_n, Tribes_{k,n}, LTF families) 2. Tracking properties as n grows 3. Visualizing asymptotic behavior

Key Concepts: - FunctionFamily: A parameterized family f_n for varying n - GrowthTracker: Observes and records properties as n increases - Marker: A property to track (influences, noise stability, etc.) - Theoretical bounds: Known asymptotic formulas for comparison

Usage:

from boofun.families import MajorityFamily, GrowthTracker

# Create a family maj = MajorityFamily()

# Track properties tracker = GrowthTracker(maj) tracker.mark(“total_influence”) tracker.mark(“noise_stability”, rho=0.5)

# Observe growth results = tracker.observe(n_values=[5, 7, 9, 11, 13, 15])

# Plot with theoretical comparison tracker.plot(“total_influence”, show_theory=True)

class boofun.families.FunctionFamily

Abstract base class for Boolean function families.

A function family is a parameterized collection f_n indexed by n. Examples: Majority_n, Parity_n, Tribes_{k,n}

Subclasses must implement: - generate(n) -> BooleanFunction - metadata property

Optional overrides: - theoretical_value(property_name, n) -> theoretical prediction

abstractmethod generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

abstract property metadata: FamilyMetadata

Return metadata about this family.

validate_n(n: int) → bool

Check if n is valid for this family.

theoretical_value(property_name: str, n: int, **kwargs) → float | None

Get theoretical/asymptotic value for a property.

Parameters:

• property_name – Name of the property (e.g., “total_influence”)

• n – Number of variables

• **kwargs – Additional parameters (e.g., rho for noise stability)

Returns:

Theoretical value if known, None otherwise

generate_range(n_values: List[int], **kwargs) → Dict[int, BooleanFunction]

Generate functions for a range of n values.

Parameters:

• n_values – List of n values to generate

• **kwargs – Additional parameters

Returns:

Dictionary mapping n -> BooleanFunction

class boofun.families.InductiveFamily(name: str = 'InductiveFamily', base_cases: Dict[int, BooleanFunction] | None = None, step_function: Callable | None = None, step_size: int = 1)

A function family defined inductively/recursively.

The user provides: - base_case(n) -> BooleanFunction for small n - step(f_prev, n) -> how to extend from n-1 to n variables

This is useful for functions defined by their structure: - “Add a new variable with weight w_n” - “Apply a recursive construction”

Example

# Define Majority inductively class InductiveMajority(InductiveFamily):

def base_case(self, n):

if n == 1:

return bf.dictator(1, 0) # 1 variable, dictator on var 0

return None

def step(self, f_prev, n, n_prev):

# Majority_n from Majority_{n-1} # Requires knowing the recursive structure …

__init__(name: str = 'InductiveFamily', base_cases: Dict[int, BooleanFunction] | None = None, step_function: Callable | None = None, step_size: int = 1)

Initialize an inductive family.

Parameters:

• name – Family name

• base_cases – Dictionary of {n: BooleanFunction} for base cases

• step_function – Function (f_prev, n) -> f_n

• step_size – Number of variables added per step (default 1)

property metadata: FamilyMetadata

Return metadata about this family.

base_case(n: int) → BooleanFunction | None

Get base case for n, if it exists.

Override this in subclasses or provide base_cases dict.

step(f_prev: BooleanFunction, n: int, n_prev: int) → BooleanFunction

Generate f_n from f_{n_prev}.

Override this in subclasses or provide step_function.

Parameters:

• f_prev – Function at previous step

• n – Target number of variables

• n_prev – Previous number of variables

Returns:

Function with n variables

generate(n: int, **kwargs) → BooleanFunction

Generate function for n variables using induction.

clear_cache()

Clear the cached functions.

class boofun.families.MajorityFamily

Majority function family: MAJ_n(x) = 1 if Σx_i > n/2.

Well-known asymptotics: - Total influence: I[MAJ_n] ≈ √(2/π) · √n ≈ 0.798√n - Each influence: Inf_i[MAJ_n] ≈ √(2/(πn)) - Noise stability: Stab_ρ[MAJ_n] → (1/2) + (1/π)arcsin(ρ) - Fourier degree: n (but most weight on lower degrees)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

validate_n(n: int) → bool

Check if n is valid for this family.

class boofun.families.ParityFamily

Parity/XOR function family: XOR_n(x) = Σx_i mod 2.

Parity is the “opposite” of Majority in many ways: - NOT an LTF (not linearly separable) - All Fourier weight on a single coefficient - Maximum noise sensitivity

Asymptotics: - Total influence: I[XOR_n] = n (each variable is pivotal always) - Noise stability: Stab_ρ[XOR_n] = ρ^n → 0 for ρ < 1 - Fourier: f̂(S) = 1 only for S = [n], else 0

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.TribesFamily

Tribes function family: Balanced DNF with k tribes of size s.

Standard choice: s = log(n) - log(log(n)) for k = n/s tribes. This achieves Pr[TRIBES = 1] ≈ 1/2.

Asymptotics: - Total influence: I[TRIBES] ≈ log(n)/n · n = log(n) - Each influence: Inf_i[TRIBES] ≈ log(n)/n - Noise stability: Complex, depends on parameters

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, k: int | None = None, w: int | None = None, **kwargs) → BooleanFunction

Generate tribes function.

Parameters:

• n – Total number of variables

• k – Number of tribes (optional, auto-computed if not provided)

• w – Width of each tribe (optional, auto-computed if not provided)

Note: bf.tribes(tribe_size, total_vars) so we call bf.tribes(w, n)

class boofun.families.ThresholdFamily(k_function: Callable[[int], int] | None = None)

Threshold function family: THR_k(x) = 1 if Σx_i ≥ k.

This is a symmetric LTF (uniform weights).

Special cases: - k = 1: OR function - k = n: AND function - k = (n+1)/2: Majority (for odd n)

__init__(k_function: Callable[[int], int] | None = None)

Initialize threshold family.

Parameters:

k_function – Function n -> k specifying threshold for each n. Default: k = n//2 + 1 (majority-like)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, k: int | None = None, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.ANDFamily

AND function family: AND_n(x) = 1 iff all x_i = 1.

Extreme threshold function (k = n).

Asymptotics: - Total influence: I[AND_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[AND_n] = 2^{-(n-1)} - Pr[AND_n = 1] = 2^{-n}

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.ORFamily

OR function family: OR_n(x) = 1 iff at least one x_i = 1.

Extreme threshold function (k = 1). Dual of AND: OR_n(x) = ¬AND_n(¬x).

Asymptotics: - Total influence: I[OR_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[OR_n] = 2^{-(n-1)} - Pr[OR_n = 1] = 1 - 2^{-n}

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.DictatorFamily(variable: int = 0)

Dictator function family: DICT_i(x) = x_i.

The “simplest” Boolean function - just returns one variable.

Asymptotics: - Total influence: I[DICT] = 1 (only one influential variable) - Inf_i[DICT] = 1, Inf_j[DICT] = 0 for j ≠ i - Noise stability: Stab_ρ[DICT] = ρ

__init__(variable: int = 0)

Initialize dictator family.

Parameters:

variable – Which variable to use (default: 0)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.LTFFamily(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')

General LTF (Linear Threshold Function) family.

LTF_w(x) = sign(w₁x₁ + … + wₙxₙ - θ)

This is a more flexible version of WeightPatternFamily with additional convenience methods.

__init__(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')

Initialize LTF family.

Parameters:

• weight_pattern – Function (i, n) -> weight of variable i

• threshold_pattern – Function n -> threshold

• name – Family name

property metadata: FamilyMetadata

Return metadata about this family.

classmethod uniform(name: str = 'UniformLTF') → LTFFamily

Create LTF with uniform weights (= Majority).

classmethod geometric(ratio: float = 0.5, name: str = 'GeometricLTF') → LTFFamily

Create LTF with geometrically decaying weights.

classmethod harmonic(name: str = 'HarmonicLTF') → LTFFamily

Create LTF with harmonic weights 1/(i+1).

classmethod power_law(power: float = 2.0, name: str = 'PowerLTF') → LTFFamily

Create LTF with power-law weights.

class boofun.families.GrowthTracker(family: FunctionFamily)

Track properties of a function family as n grows.

Usage:

tracker = GrowthTracker(MajorityFamily()) tracker.mark(“total_influence”) tracker.mark(“noise_stability”, rho=0.5)

results = tracker.observe([5, 7, 9, 11, 13, 15]) tracker.plot(“total_influence”, show_theory=True)

__init__(family: FunctionFamily)

Initialize tracker for a function family.

Parameters:

family – The function family to track

mark(property_name: str, **kwargs) → GrowthTracker

Add a property to track.

Parameters:

• property_name – Built-in property name or “custom”

• **kwargs – Parameters for the marker

Returns:

self (for chaining)

Built-in properties:

• “total_influence”

• “influences” or “influence_i” (with variable=i)

• “noise_stability” (with rho=0.5)

• “fourier_degree”

• “spectral_concentration” (with k=degree)

• “expectation”

• “variance”

• “is_<property>” (e.g., “is_monotone”, “is_balanced”)

• “sensitivity”

• “block_sensitivity”

observe(n_values: List[int] | None = None, n_range: range | None = None, n_min: int = 3, n_max: int = 15, step: int = 2, verbose: bool = False) → Dict[str, TrackingResult]

Observe the family over a range of n values.

Parameters:

• n_values – Explicit list of n values

• n_range – Range object for n values

• n_min – Parameters for default range

• n_max – Parameters for default range

• step – Parameters for default range

• verbose – Print progress

Returns:

Dictionary mapping marker name -> TrackingResult

get_result(marker_name: str) → TrackingResult | None

Get tracking result for a specific marker.

plot(marker_name: str, show_theory: bool = True, log_scale: bool = False, ax=None, **plot_kwargs)

Plot a tracked property vs n.

Parameters:

• marker_name – Which marker to plot

• show_theory – Show theoretical prediction line

• log_scale – Use log scale for y-axis

• ax – Matplotlib axes (creates new figure if None)

• **plot_kwargs – Additional arguments for plt.plot

Returns:

Matplotlib axes

plot_all(show_theory: bool = True, figsize: Tuple[int, int] = (15, 4))

Plot all tracked markers in subplots.

summary() → str

Generate text summary of tracking results.

clear()

Clear all tracking data.

class boofun.families.Marker(name: str, compute_fn: ~typing.Callable[[BooleanFunction], ~typing.Any], marker_type: ~boofun.families.tracker.MarkerType = MarkerType.SCALAR, description: str = '', theoretical_fn: ~typing.Callable[[int], ~typing.Any] | None = None, params: ~typing.Dict[str, ~typing.Any] = <factory>)

A property to track as n grows.

name

Identifier for this marker

Type:

str

compute_fn

Function(BooleanFunction) -> value

Type:

Callable[[BooleanFunction], Any]

marker_type

Type of the value

Type:

boofun.families.tracker.MarkerType

description

Human-readable description

Type:

str

theoretical_fn

Optional function(n) -> theoretical value

Type:

Callable[[int], Any] | None

params

Additional parameters for computation

Type:

Dict[str, Any]

name: str

compute_fn: Callable[[BooleanFunction], Any]

marker_type: MarkerType = 'scalar'

description: str = ''

theoretical_fn: Callable[[int], Any] | None = None

params: Dict[str, Any]

compute(f: BooleanFunction) → Any

Compute the marked value for a function.

theoretical(n: int) → Any | None

Get theoretical value if available.

__init__(name: str, compute_fn: ~typing.Callable[[BooleanFunction], ~typing.Any], marker_type: ~boofun.families.tracker.MarkerType = MarkerType.SCALAR, description: str = '', theoretical_fn: ~typing.Callable[[int], ~typing.Any] | None = None, params: ~typing.Dict[str, ~typing.Any] = <factory>) → None

class boofun.families.PropertyMarker

Factory for common property markers.

static total_influence(theoretical: Callable[[int], float] | None = None) → Marker

Track total influence I[f].

static influences(variable: int | None = None) → Marker

Track variable influences.

static noise_stability(rho: float = 0.5, theoretical: Callable[[int, float], float] | None = None) → Marker

Track noise stability Stab_ρ[f].

static fourier_degree() → Marker

Track Fourier degree.

static spectral_concentration(k: int) → Marker

Track weight on coefficients of degree ≤ k.

static expectation() → Marker

Track E[f] = f̂(∅).

static variance() → Marker

Track Var[f] = 1 - f̂(∅)².

static is_property(property_name: str) → Marker

Track whether a property holds.

static sensitivity() → Marker

Track sensitivity s(f).

static block_sensitivity() → Marker

Track block sensitivity bs(f).

static custom(name: str, compute_fn: Callable[[BooleanFunction], Any], marker_type: MarkerType = MarkerType.SCALAR, description: str = '', theoretical_fn: Callable[[int], Any] | None = None) → Marker

Create a custom marker.

class boofun.families.TheoreticalBounds

Collection of theoretical bounds and asymptotic formulas.

These are from O’Donnell’s book and other sources.

static majority_total_influence(n: int) → float

Total influence of Majority_n.

I[MAJ_n] = √(2/π) · √n + O(1/√n)

static parity_total_influence(n: int) → float

Total influence of Parity_n = n.

static and_total_influence(n: int) → float

Total influence of AND_n = n · 2^{-(n-1)}.

static tribes_total_influence(n: int, w: int | None = None) → float

Total influence of Tribes.

For standard balanced Tribes: I[TRIBES_n] ≈ log(n)

static majority_noise_stability(rho: float) → float

Noise stability of Majority (Sheppard’s formula).

Stab_ρ[MAJ_n] → (1/2) + (1/π)·arcsin(ρ) as n → ∞

static parity_noise_stability(n: int, rho: float) → float

Noise stability of Parity.

Stab_ρ[XOR_n] = ρ^n → 0 for ρ < 1

static dictator_noise_stability(rho: float) → float

Noise stability of Dictator.

Stab_ρ[DICT] = ρ

static and_noise_stability(n: int, rho: float) → float

Noise stability of AND.

Stab_ρ[AND_n] = Pr[AND(x) = AND(y)] where y = ρ-correlated with x

static majority_influence_i(n: int, i: int = 0) → float

Influence of variable i in Majority_n.

By symmetry: Inf_i[MAJ_n] = √(2/(πn)) for all i

static parity_influence_i(n: int, i: int = 0) → float

Each variable has influence 1 in Parity.

static and_influence_i(n: int, i: int = 0) → float

Influence of each variable in AND_n = 2^{-(n-1)}.

static poincare_lower_bound(variance: float) → float

Poincaré inequality: Var[f] ≤ I[f]

So I[f] ≥ Var[f]

static kkl_lower_bound(n: int, variance: float) → float

KKL Theorem: max_i Inf_i[f] ≥ Var[f] · c·log(n)/n

For balanced f: max Inf_i ≥ Ω(log(n)/n)

static friedgut_junta_bound(total_influence: float, epsilon: float) → float

Friedgut’s Junta Theorem.

If I[f] ≤ k, then f is ε-close to a 2^{O(k/ε)}-junta.

Returns the junta size bound.

static decision_tree_fourier_support(depth: int) → int

Decision tree of depth d has at most 4^d non-zero Fourier coefficients.

static decision_tree_spectral_norm(size: int) → float

Decision tree of size s has Σ|f̂(S)| ≤ s.

static mansour_spectral_concentration(depth: int, epsilon: float) → int

Mansour’s Theorem: DNF of depth d has (1-ε) of Fourier weight on O(1/ε^2 · 2^{O(d)}) coefficients.

static ltf_total_influence(n: int, regularity: float = 0.0) → float

Total influence of an LTF.

For regular LTFs (τ small): I[f] ≈ √(2/π)·√n For irregular (τ → 1): I[f] → 1

static ltf_noise_stability(rho: float, regularity: float = 0.0) → float

Noise stability of LTF.

Regular LTFs: Stab_ρ → (1/2) + (1/π)arcsin(ρ) Dictator (τ=1): Stab_ρ = ρ

static sensitivity_vs_block_sensitivity(s: float) → float

Sensitivity Theorem (Huang 2019): bs(f) ≤ s(f)^4

Returns upper bound on block sensitivity.

static certificate_vs_sensitivity(s: float) → float

C(f) ≤ s(f) · bs(f) ≤ s(f)^5

static degree_vs_sensitivity(s: float) → float

deg(f) ≤ s(f)^2 (from Sensitivity Theorem)

classmethod get_bounds_for_family(family_name: str) → Dict[str, Callable]

Get all applicable theoretical bounds for a named family.

Returns dictionary of {property_name: bound_function}

Modules

base	Base classes for Boolean function families.
builtins	Built-in function families with known asymptotic behavior.
theoretical	Theoretical bounds and asymptotic formulas for Boolean function properties.
tracker	Growth tracking for Boolean function families.