boofun.analysis.global_hypercontractivity
Global Hypercontractivity Module
Implements concepts from Keevash, Lifshitz, Long & Minzer’s “Global hypercontractivity and its applications” (arXiv:1906.05039).
This module provides tools for analyzing Boolean functions under p-biased measures, particularly for “global” functions that don’t depend too much on any small set of coordinates.
Key concepts: - Generalized influences: I_S(f) for sets S ⊆ [n] - Global functions: Functions with small generalized influences - p-biased Fourier analysis - Sharp threshold phenomena
- Reference:
Keevash, P., Lifshitz, N., Long, E., & Minzer, D. (2019). Global hypercontractivity and its applications. arXiv:1906.05039
Functions
|
Find the critical probability p_c where μ_p(f) ≈ 0.5. |
|
Compute the generalized S-influence I_S(f) under μ_p. |
|
Compute the hypercontractivity bound for a function. |
|
Check if f has α-small generalized influences (Definition I.1.2). |
|
Compute λ(p) = E[(χ_i^p)^4], the 4th moment of a p-biased character. |
|
Estimate noise stability S_ρ(f) under the p-biased measure. |
|
Compute the p-biased character χ_S^p(x). |
|
Estimate E_μp[f(x)] via Monte Carlo sampling. |
|
Estimate Inf_i^p[f] under the p-biased measure. |
|
Estimate I^p[f] = Σ_i Inf_i^p[f] under the p-biased measure. |
|
Compute σ(p) = √(p(1-p)), the standard deviation of a p-biased bit. |
|
Compute μ_p(f) for each p in the range. |
Classes
|
Analyzer for global hypercontractivity properties. |
- boofun.analysis.global_hypercontractivity.sigma(p: float) float[source]
Compute σ(p) = √(p(1-p)), the standard deviation of a p-biased bit.
- Parameters:
p – Bias parameter in (0, 1)
- Returns:
Standard deviation σ(p)
- boofun.analysis.global_hypercontractivity.lambda_p(p: float) float[source]
Compute λ(p) = E[(χ_i^p)^4], the 4th moment of a p-biased character.
This quantity controls the failure of standard hypercontractivity for small p. For p = 1/2, λ = 3. As p → 0 or p → 1, λ → ∞.
From Section II.1 of the paper: λ = σ^{-2}((1-p)^3 + p^3)
- Parameters:
p – Bias parameter in (0, 1)
- Returns:
4th moment λ(p), or infinity if p is at boundary
- boofun.analysis.global_hypercontractivity.p_biased_character(x: ndarray, S: Set[int], p: float) float[source]
Compute the p-biased character χ_S^p(x).
χ_S^p(x) = Π_{i∈S} (x_i - p)/σ
where σ = √(p(1-p)).
- Parameters:
x – Binary input vector
S – Set of variable indices
p – Bias parameter
- Returns:
Value of χ_S^p(x)
- boofun.analysis.global_hypercontractivity.generalized_influence(f: BooleanFunction, S: Set[int], p: float = 0.5) float[source]
Compute the generalized S-influence I_S(f) under μ_p.
From Definition I.1.2 and equation (2) in the paper: I_S(f) = σ^{-2|S|} ||D_S(f)||_2^2 = σ^{-2|S|} Σ_{T⊇S} f̂(T)^2
- Parameters:
f – Boolean function to analyze
S – Set of variable indices
p – Bias parameter (default 0.5 for uniform measure)
- Returns:
Generalized S-influence
- boofun.analysis.global_hypercontractivity.is_alpha_global(f: BooleanFunction, alpha: float, max_set_size: int = 3, p: float = 0.5) Tuple[bool, Dict][source]
Check if f has α-small generalized influences (Definition I.1.2).
A function has α-small generalized influences if: I_S(f) ≤ α·E[f^2] for all S ⊆ [n]
- Parameters:
f – Boolean function to test
alpha – Threshold for generalized influences
max_set_size – Maximum |S| to check (for efficiency)
p – Bias parameter
- Returns:
max_generalized_influence: Largest I_S found
worst_set: The set S achieving the maximum
threshold: α·E[f^2]
all_influences: Dictionary of all computed I_S values
- Return type:
Tuple of (is_global, details_dict) where details_dict contains
- boofun.analysis.global_hypercontractivity.p_biased_expectation(f: BooleanFunction, p: float, samples: int = 10000) float[source]
Estimate E_μp[f(x)] via Monte Carlo sampling.
- Parameters:
f – Boolean function
p – Bias parameter
samples – Number of Monte Carlo samples
- Returns:
Estimated expectation under μ_p
- boofun.analysis.global_hypercontractivity.p_biased_influence(f: BooleanFunction, i: int, p: float, samples: int = 5000) float[source]
Estimate Inf_i^p[f] under the p-biased measure.
Inf_i^p[f] = Pr_{x~μp}[f(x) ≠ f(x^i)]
where x^i differs from x only in coordinate i.
- Parameters:
f – Boolean function
i – Variable index
p – Bias parameter
samples – Number of Monte Carlo samples
- Returns:
Estimated p-biased influence of variable i
- boofun.analysis.global_hypercontractivity.p_biased_total_influence(f: BooleanFunction, p: float, samples: int = 3000) float[source]
Estimate I^p[f] = Σ_i Inf_i^p[f] under the p-biased measure.
From equation (1) in the paper: I(f) = (p(1-p))^{-1} Σ_S |S| f̂(S)^2
- Parameters:
f – Boolean function
p – Bias parameter
samples – Number of Monte Carlo samples per variable
- Returns:
Estimated total influence under μ_p
- boofun.analysis.global_hypercontractivity.noise_stability_p_biased(f: BooleanFunction, rho: float, p: float, samples: int = 5000) float[source]
Estimate noise stability S_ρ(f) under the p-biased measure.
S_ρ(f) = E_{x~μp}[f(x)·(T_ρf)(x)]
where (T_ρf)(x) = E_{y~N_ρ(x)}[f(y)] and y is obtained by keeping each bit with probability ρ or resampling from μp.
- Parameters:
f – Boolean function
rho – Noise correlation parameter
p – Bias parameter
samples – Number of Monte Carlo samples
- Returns:
Estimated noise stability
- boofun.analysis.global_hypercontractivity.threshold_curve(f: BooleanFunction, p_range: ndarray, samples: int = 2000) ndarray[source]
Compute μ_p(f) for each p in the range.
This is useful for visualizing sharp threshold phenomena.
- Parameters:
f – Boolean function
p_range – Array of p values to evaluate
samples – Number of samples per p value
- Returns:
Array of μ_p(f) values
- boofun.analysis.global_hypercontractivity.find_critical_p(f: BooleanFunction, samples: int = 3000, tolerance: float = 0.01) float[source]
Find the critical probability p_c where μ_p(f) ≈ 0.5.
For monotone functions, this is the “threshold” of the function.
- Parameters:
f – Boolean function (should be monotone for meaningful result)
samples – Number of samples for expectation estimation
tolerance – Tolerance for binary search
- Returns:
Critical probability p_c
- boofun.analysis.global_hypercontractivity.hypercontractivity_bound(f: BooleanFunction, p: float = 0.5) Dict[source]
Compute the hypercontractivity bound for a function.
From Theorem I.1.3: If f has α-small generalized influences, then ||T_{1/5}f||_4 ≤ α^{1/4} ||f||_2
- Parameters:
f – Boolean function
p – Bias parameter
- Returns:
alpha: Maximum generalized influence / E[f^2]
bound: α^{1/4} (the hypercontractive bound)
is_global: Whether the function is global
details: Full globality check results
- Return type:
Dictionary with
- class boofun.analysis.global_hypercontractivity.GlobalHypercontractivityAnalyzer(f: BooleanFunction, p: float = 0.5)[source]
Analyzer for global hypercontractivity properties.
This class provides comprehensive analysis of Boolean functions under p-biased measures, following the framework of Keevash et al.
- __init__(f: BooleanFunction, p: float = 0.5)[source]
Initialize the analyzer.
- Parameters:
f – Boolean function to analyze
p – Default bias parameter
- is_global(alpha: float = 0.5, max_set_size: int = 3) Tuple[bool, Dict][source]
Check if the function is α-global.
- Parameters:
alpha – Threshold parameter
max_set_size – Maximum set size to check
- Returns:
Tuple of (is_global, details)
- generalized_influence(S: Set[int]) float[source]
Compute I_S(f).
- Parameters:
S – Set of variable indices
- Returns:
Generalized S-influence