boofun.analysis.symmetry

Symmetry analysis for Boolean functions.

This module provides tools for analyzing symmetric properties of Boolean functions, including symmetrization, symmetric degree, and transformations to monotone form.

Key concepts: - A function is symmetric if f(x) depends only on |x| (Hamming weight) - Symmetrization: Transform any function to its symmetric version - Symmetric degree: Maximum Hamming weight with nonzero count - Shift to monotone: Find a shift that makes the function monotone (if possible)

References: - O’Donnell Chapter 4: Influences and random restrictions - Krawchouk polynomials for symmetric function analysis - Tal’s PhD library: symmetric function utilities

Functions

degree_sym(f)	Symmetric degree: largest Hamming weight with nonzero output count.
find_monotone_shift(f)	Find a shift that makes the function monotone, if one exists.
is_symmetric(f)	Check if a function is symmetric (value depends only on Hamming weight).
sens_sym(f)	Symmetric sensitivity proxy: mean Hamming weight of true inputs.
sens_sym_by_weight(f)	Compute sensitivity for each Hamming weight class.
shift_function(f, shift)	Shift a Boolean function by XORing all inputs with a constant.
symmetric_representation(f)	Get the symmetric representation of a function.
symmetrize(f)	Return counts of true outputs grouped by Hamming weight.
symmetrize_profile(f)	Return detailed profile of function values by Hamming weight.

boofun.analysis.symmetry.symmetrize(f: BooleanFunction) → np.ndarray

Return counts of true outputs grouped by Hamming weight.

For a function f: {0,1}^n → {0,1}, returns an array counts[k] where counts[k] = |{x : |x|=k and f(x)=1}|.

Parameters:

f – BooleanFunction to symmetrize

Returns:

Array of length n+1 with counts by Hamming weight

Example

>>> f = bf.AND(3)  # Returns 1 only on 111
>>> symmetrize(f)
array([0, 0, 0, 1])  # Only weight-3 has a 1

boofun.analysis.symmetry.symmetrize_profile(f: BooleanFunction) → Dict[int, Tuple[int, int]]

Return detailed profile of function values by Hamming weight.

For each weight k, returns (num_zeros, num_ones) among inputs of weight k.

Parameters:

f – BooleanFunction to analyze

Returns:

(num_zeros, num_ones)} for k = 0..n

Return type:

Dictionary {k

Example

>>> f = bf.majority(3)
>>> symmetrize_profile(f)
{0: (1, 0), 1: (3, 0), 2: (0, 3), 3: (0, 1)}

boofun.analysis.symmetry.is_symmetric(f: BooleanFunction) → bool

Check if a function is symmetric (value depends only on Hamming weight).

A function is symmetric if f(x) = f(y) whenever |x| = |y|.

Parameters:

f – BooleanFunction to check

Returns:

True if f is symmetric

Example

>>> is_symmetric(bf.AND(3))  # True: f(x)=1 iff |x|=3
True
>>> is_symmetric(bf.create([0,1,0,0]))  # False: dictator is not symmetric
False

boofun.analysis.symmetry.degree_sym(f: BooleanFunction) → int

Symmetric degree: largest Hamming weight with nonzero output count.

For symmetric functions, this equals the degree of the representing polynomial. For non-symmetric functions, this is an upper bound.

Parameters:

f – BooleanFunction to analyze

Returns:

Maximum k such that there exists x with |x|=k and f(x)=1

Note

This is O(2^n) but fast in practice for small n.

boofun.analysis.symmetry.sens_sym(f: BooleanFunction) → float

Symmetric sensitivity proxy: mean Hamming weight of true inputs.

For symmetric functions, this gives insight into where the function transitions from 0 to 1.

Parameters:

f – BooleanFunction to analyze

Returns:

Average |x| among inputs x with f(x)=1

boofun.analysis.symmetry.sens_sym_by_weight(f: BooleanFunction) → np.ndarray

Compute sensitivity for each Hamming weight class.

For weight k, computes the average sensitivity among inputs of weight k.

Parameters:

f – BooleanFunction to analyze

Returns:

Array sens[k] = average sensitivity at Hamming weight k

Note

From Tal’s library: useful for understanding sensitivity structure of symmetric and near-symmetric functions.

boofun.analysis.symmetry.shift_function(f: BooleanFunction, shift: int) → BooleanFunction

Shift a Boolean function by XORing all inputs with a constant.

Returns g where g(x) = f(x ⊕ shift).

Parameters:

• f – BooleanFunction to shift

• shift – Integer mask to XOR with inputs

Returns:

Shifted BooleanFunction

Note

From Tal’s library: useful for finding monotone shifts.

boofun.analysis.symmetry.find_monotone_shift(f: BooleanFunction) → int | None

Find a shift that makes the function monotone, if one exists.

A function g is monotone if x ≤ y (bitwise) implies g(x) ≤ g(y). This searches for a shift value s such that g(x) = f(x ⊕ s) is monotone.

Parameters:

f – BooleanFunction to analyze

Returns:

Shift value that makes f monotone, or None if no such shift exists

Note

This is exponential in n (tries all 2^n shifts) but useful for small n. From Tal’s library: shift_to_mono concept.

boofun.analysis.symmetry.symmetric_representation(f: BooleanFunction) → List[int]

Get the symmetric representation of a function.

Returns a list spec[k] ∈ {0, 1, -1} where: - spec[k] = 1 if all weight-k inputs map to 1 - spec[k] = 0 if all weight-k inputs map to 0 - spec[k] = -1 if weight-k inputs have mixed outputs (not symmetric)

Parameters:

f – BooleanFunction to analyze

Returns:

List of length n+1 with symmetric specification

Example

>>> symmetric_representation(bf.majority(3))
[0, 0, 1, 1]  # weights 0,1 → 0, weights 2,3 → 1