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?

Improve this question
$\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, 2020 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, 2020 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, 2020 at 1:52

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2020 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, 2020 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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