Fourier Analysis on finite Abelian groups and its Applications

A Boolean-valued function is a map from a domain D to a range of cardinality two, such as {−1, +1}, or {0, 1}. These functions play a central role in theoretical computer science, additive combinatorics, and several other areas. When the domain D is equipped with an algebraic structure, particularly that of a finite Abelian group, Boolean-valued functions become especially important for studying algorithms and complexity. Such settings allow us to investigate the Fourier analysis of Boolean functions, examine the structure of their Fourier spectra, and understand the behavior of their Fourier coefficients.

Most prior work has focused on the case D=Z_2^n, the space of binary strings of length n. A natural question is whether these results extend to Boolean-valued functions defined over arbitrary finite Abelian groups. This talk will address several problems that we have generalized to this broader setting.

Granularity: The Fourier sparsity s_f of f is the number of nonzero Fourier coefficients. When s_f is small, what can be said about the magnitude of the Fourier coefficients? Gopalan et al. (2011) showed that for Boolean functions on Z_2^n, every nonzero Fourier coefficient has absolute value at least 1/s_f.

Upper bounds on Fourier dimension: The Fourier dimension r_f is the dimension of the Fourier support of f. Sanyal (2019) proved that r_f = O(\sqrt{s_f} log s_f ). This was improved by Chakraborty et al. (2020), who showed that r_f = O(\sqrt{s_f \delta_f} log s_f ), where \delta_f = Pr_x[f(x) = −1]. These results demonstrate that Boolean functions with small sparsity cannot have arbitrarily large Fourier dimension. Improved bounds for Chang's lemma and Cohen's idempotent theorem have also been obtained in the Z_2^n setting.

 

Page 1 of 2.... 

 

 

 

 

 

Linear Isomorphism Testing: The linear isomorphism testing problem for Boolean functions over Z_2^n is also an important area of study. For A \in Z_2^n×n, let f ◦ A : Z_2^n → {−1, 1} be the function f ◦A(x) = f(Ax) for all x ∈ Z_2^n. The Linear Isomorphism Distance between f : Z_2^n → {−1, 1} and g : Z_2^n → {−1, 1} is defined as dist_{Z_2^n}(f, g) = min_{A\in Z_2^{n×n}: A is non-singular} \delta(f ◦A, g). Assume that f and g satisfy the promise that either dist_{Z_2^n}(f, g)=0 or dist_{Z_2^n}(f, g) \geq \epsilon, the question of Linear Isomorphism testing is that of deciding which is the case. 

 

Additional investigations include the approximate degree of Boolean functions, the Fourier–Entropy Influence (FEI) conjecture, and related topics. A key challenge in extending results from Z_2^n to arbitrary finite Abelian groups is that general Abelian groups are not vector spaces, and their Fourier coefficients are complex numbers. Consequently, many structural properties used in the Z_2^n setting break down, making such generalizations nontrivial. The talk will highlight these challenges and discuss the main obstacles to developing analogous results over finite Abelian groups.