Function Families and Growth Analysis

This guide covers how to work with function families - parameterized collections of Boolean functions that grow with n.

What is a Function Family?

A function family is a sequence of Boolean functions indexed by the number of variables n:

Majority_n: Returns 1 if more than half of inputs are 1
Parity_n: XOR of all inputs
Tribes_{k,n}: OR of k groups, each an AND of n/k variables
AND_n / OR_n: All inputs must be 1 / at least one input must be 1

Studying how properties change as n grows reveals asymptotic behavior and theoretical bounds.

Built-in Families

from boofun.families import (
    MajorityFamily,
    ParityFamily,
    TribesFamily,
    ANDFamily,
    ORFamily,
    DictatorFamily,
    ThresholdFamily,
    LTFFamily,
    RecursiveMajority3Family,
)

# Generate a specific instance
maj = MajorityFamily()
f_5 = maj.generate(5)  # Majority on 5 variables
f_7 = maj(7)           # Shorthand

# Generate multiple
functions = maj.generate_range([3, 5, 7, 9, 11])

Family Metadata

Each family has metadata about its properties:

maj = MajorityFamily()
meta = maj.metadata

print(meta.name)           # "Majority"
print(meta.description)    # "MAJ_n(x) = 1 if Σx_i > n/2"
print(meta.asymptotics)    # Known theoretical formulas
print(meta.universal_properties)  # ["monotone", "symmetric", "balanced"]

Theoretical Values

Get theoretical predictions for properties:

# Total influence of Majority_n ≈ √(2/π) · √n
theory = maj.theoretical_value('total_influence', n=15)
print(f"I[MAJ_15] ≈ {theory:.4f}")  # ≈ 3.09

Tracking Growth

The GrowthTracker observes properties as n increases:

from boofun.families import GrowthTracker, MajorityFamily

# Create tracker
maj = MajorityFamily()
tracker = GrowthTracker(maj)

# Mark properties to track
tracker.mark('total_influence')
tracker.mark('noise_stability', rho=0.9)
tracker.mark('expectation')
tracker.mark('variance')

# Observe over range of n
results = tracker.observe(n_values=[3, 5, 7, 9, 11, 13, 15])

# Get summary
print(tracker.summary())

Available Markers

from boofun.families import PropertyMarker

# Built-in markers
tracker.mark('total_influence')
tracker.mark('influences')              # All variable influences
tracker.mark('influence_0')             # Specific variable
tracker.mark('noise_stability', rho=0.5)
tracker.mark('fourier_degree')
tracker.mark('spectral_concentration', k=2)
tracker.mark('expectation')
tracker.mark('variance')
tracker.mark('sensitivity')
tracker.mark('block_sensitivity')
tracker.mark('is_monotone')             # Boolean properties

# Custom marker
tracker.mark('custom',
    compute_fn=lambda f: f.sparsity(),
    description="Fourier sparsity")

Visualization

Single Family Growth

from boofun.visualization.growth_plots import GrowthVisualizer

viz = GrowthVisualizer()

# Plot with theoretical comparison
fig, ax = viz.plot_growth(
    tracker,
    'total_influence',
    show_theory=True,
    log_y=False
)

Family Comparison

Compare multiple families on the same property:

from boofun.families import MajorityFamily, ParityFamily, ANDFamily

# Track each family
families = {
    'Majority': MajorityFamily(),
    'Parity': ParityFamily(),
    'AND': ANDFamily(),
}

trackers = {}
for name, family in families.items():
    tracker = GrowthTracker(family)
    tracker.mark('total_influence')
    tracker.observe(n_values=list(range(3, 12)))
    trackers[name] = tracker

# Compare
viz = GrowthVisualizer()
fig = viz.plot_family_comparison(
    trackers,
    'total_influence',
    log_y=True,
    title="Total Influence: Parity vs Majority vs AND"
)

Convergence Rate

Analyze how a property converges to its asymptotic value:

fig = viz.plot_convergence_rate(
    tracker,
    'total_influence',
    reference='sqrt_n'  # Divide by √n to see constant factor
)

Custom Families

From a Generator Function

from boofun.families import FunctionFamily, FamilyMetadata
import boofun as bf

class MyCustomFamily(FunctionFamily):
    @property
    def metadata(self):
        return FamilyMetadata(
            name="MyFunction",
            description="Custom function family",
            asymptotics={
                'total_influence': lambda n: n * 0.5,
            },
            universal_properties=['balanced'],
        )

    def generate(self, n, **kwargs):
        # Your custom logic
        return bf.majority(n) ^ bf.parity(n)

Inductive Families

Define families recursively:

from boofun.families import InductiveFamily

class RecursiveFamily(InductiveFamily):
    def __init__(self):
        super().__init__(
            name="Recursive",
            base_cases={1: bf.dictator(1, 0)},
            step_size=1
        )

    def step(self, f_prev, n, n_prev):
        # Extend from n-1 to n variables
        return f_prev.extend(n, fill=0)

Weight Pattern LTFs

LTF families with custom weight patterns:

from boofun.families import LTFFamily

# Geometric weights: w_i = 0.5^i
geometric = LTFFamily.geometric(ratio=0.5)

# Harmonic weights: w_i = 1/(i+1)
harmonic = LTFFamily.harmonic()

# Power-law weights: w_i = (n-i)^2
power = LTFFamily.power_law(power=2.0)

# Custom pattern
custom = LTFFamily(
    weight_pattern=lambda i, n: 1.0 / (i + 1)**0.5,
    name="SqrtHarmonic"
)

Theoretical Bounds

The library includes known asymptotic formulas:

Family	Total Influence	Max Influence	Noise Stability
Majority_n	√(2/π) · √n	√(2/(πn))	(1/2) + (1/π)arcsin(ρ)
Parity_n	n	1	ρ^n
AND_n	n · 2^{-(n-1)}	2^{-(n-1)}	-
Tribes	O(log n)	O(log n / n)	-
Dictator	1	1	ρ

Access these via:

maj = MajorityFamily()
print(maj.metadata.asymptotics)

Quick Growth Plot

For quick exploration:

from boofun.visualization.growth_plots import quick_growth_plot

# One-liner visualization
fig = quick_growth_plot(
    'majority',
    properties=['total_influence', 'expectation'],
    n_values=[3, 5, 7, 9, 11, 13]
)