6
$\begingroup$

Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can form an orthonormal basis for Boolean functions?

If not, why not?

$\endgroup$
3
  • 3
    $\begingroup$ A useful keyword: an orthonormal basis of Boolean functions in $n$ variables is essentially the same thing as an Hadamard matrix of order $2^n$. (The standard basis of “parity functions” corresponds to the Sylvester/Walsh matrix.) $\endgroup$ – Emil Jeřábek Apr 10 '20 at 13:21
  • 1
    $\begingroup$ What @EmilJeřábek wrote and the answer by Mahdi assume that OP is looking for an orthonormal basis of the vector space of (real valued) functions on $\{-1, +1\}$ such that the basis functions themselves are boolean. Is this what the question is asking? Are the basis functions required to be boolean? $\endgroup$ – Sasho Nikolov Apr 11 '20 at 13:52
  • 3
    $\begingroup$ If the basis is not required to be Boolean, the question would be trivial: simply take any orthonormal basis for the vector space $\mathbb{R}^{2^n}$. $\endgroup$ – Mahdi Cheraghchi Apr 12 '20 at 1:52
8
$\begingroup$

I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.

$\endgroup$
2
  • $\begingroup$ Mahdi (or anyone else who is able), I would love to see (links to) concrete examples or relevant references. $\endgroup$ – tigercub97 Apr 10 '20 at 23:08
  • 2
    $\begingroup$ You can just arrange any orthonormal basis as a $2^n \times 2^n$ matrix (one row per basis function, one column per evaluation point). This is an orthonormal matrix with (normalized) +1/-1 entries, and any such matrix is called a Hadamard matrix (as Emil also pointed out). Parities create Hadamard matrices, but there are other non-parity Hadamard matrices in some cases, such as Paley's construction above. $\endgroup$ – Mahdi Cheraghchi Apr 11 '20 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.