## Tata Institute of Fundamental Research

### Identifying some necessary conditions for a function to be Boolean

##### STCS Student Seminar
 Speaker: Nikhil Mande (Georgetown University, Washington, D.C.) Organiser: Neha Sangwan Date: Saturday, 15 Aug 2020, 11:00 to 12:00 Venue:

Abstract: Every Boolean function $f : \mathbb{F}_2^n \to \{-1, 1\}$ has a unique Fourier representation, that is, $f = \sum_{\alpha \in \mathbb{F}_2^n}\hat{f}(\alpha)\chi_{\alpha}$. One can obtain the following identities using elementary techniques.
1) Parseval's identity: $\sum_{\alpha \in \mathbb{F}_2^n}\hat{f}(\alpha)^2 = 1$.
2) For all $\gamma \neq 0^n$, we have $\sum_{(\alpha_1, \alpha_2) \in \mathbb{F}_2^n \times \mathbb{F}_2^n : \alpha_1+\alpha_2=\gamma}\hat{f}(\alpha_1)\hat{f}(\alpha_2)=0$. Henceforth, we refer to these conditions as Titsworth's conditions.
Let $\mathcal{S}$ denote the Fourier support of $f$, that is, the set of elements of $\mathbb{F}_2^n$ that have non-zero Fourier coefficients. Titsworth's conditions can be seen to imply that for every pair $(\alpha_1, \alpha_2)$ of elements in $\mathcal{S}$, there must exist at least one other pair $(\beta_1, \beta_2)$ of elements in $\mathcal{S}$ such that $\alpha_1 \oplus \alpha_2 = \beta_1 \oplus \beta_2$. We investigate whether this condition in itself is sufficient for $\mathcal{S}$ to be the Fourier support of a Boolean function.