Abstract
Chang’s lemma (Duke Mathematical Journal, 2002) is a classical result in mathematics, with applications spanning across additive combinatorics, combinatorial number theory, analysis of Boolean functions, communication complexity and algorithm design. For a Boolean function f that takes values in {1, 1} let r(f) denote its Fourier rank (i.e., the dimension of the span of its Fourier support). For each positive threshold t, Chang’s lemma provides a lower bound on δ(f) := Pr[f(x) = 1] in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least 1/t. In this work we examine the tightness of Chang’s lemma with respect to the following three natural settings of the threshold:
 the Fourier sparsity of f, denoted k(f),
 the Fourier maxsuppentropy of f, denoted k'(f), defined to be the maximum value of the reciprocal of the absolute value of a nonzero Fourier coefficient,
 the Fourier maxrankentropy of f, denoted k''(f), defined to be the minimum t such that characters whose coefficients are at least 1/t in magnitude span a r(f)dimensional space. In this work we prove new lower bounds on δ(f) in terms of the above measures. One of our lower bounds, δ(f) = Ω(r(f)²/(k(f) log² k(f))), subsumes and refines the previously best known upper bound r(f) = O(√{k(f)}log k(f)) on r(f) in terms of k(f) by Sanyal (Theory of Computing, 2019). We improve upon this bound and show r(f) = O(√{k(f)δ(f)}log k(f)). Another lower bound, δ(f) = Ω(r(f)/(k''(f) log k(f))), is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of absolute values of level1 Fourier coefficients in terms of ?₂degree. We further show that Chang’s lemma for the abovementioned choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved.
Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions witnessing their tightness. All the functions we construct are modifications of the Addressing function, where we replace certain input variables by suitable functions. Our final contribution is to construct Boolean functions f for which our lower bounds asymptotically match δ(f), and for any choice of the threshold t, the lower bound obtained from Chang’s lemma is asymptotically smaller than δ(f).
Our results imply more refined deterministic oneway communication complexity upper bounds for XOR functions. Given the wideranging application of Chang’s lemma to areas like additive combinatorics, learning theory and communication complexity, we strongly feel that our refinements of Chang’s lemma will find many more applications.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.10,
author = {Chakraborty, Sourav and Mande, Nikhil S. and Mittal, Rajat and Molli, Tulasimohan and Paraashar, Manaswi and Sanyal, Swagato},
title = {{Tight Chang’sLemmaType Bounds for Boolean Functions}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {10:110:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772150},
ISSN = {18688969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15521},
URN = {urn:nbn:de:0030drops155215},
doi = {10.4230/LIPIcs.FSTTCS.2021.10},
annote = {Keywords: Analysis of Boolean functions, Chang’s lemma, Parity decision trees, Fourier dimension}
}
Keywords: 

Analysis of Boolean functions, Chang’s lemma, Parity decision trees, Fourier dimension 
Collection: 

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) 
Issue Date: 

2021 
Date of publication: 

29.11.2021 