Parity of a boolean function

Question

I was doing a course on Quantum Computing. There was a question in problem set. Which is given below (Question No.5)

Here the parity function is defined as(As per the instructor):
$$y_i = 1-2x_i$$ $$Parity(y) = \prod_{i=0}^{n-1} y_i$$

An example would be lets take a binary string $x = 1010110110$ the Parity function would give $1$ since even number of ones, otherwise $-1$ if odd number of ones.
Also when asking parity of functions its actually asking the parity of the bit string acquired after pluging in the all the input value of the n-bit function. For example lets take the option number 3
$$f:\{0,1^n\} \mapsto \{0,1\}$$ $$A\ constant\ function f({x}) = 1$$ Let take $n=4$, For it, all the possible input values $(x)$ a function can take are from $0$ to $15$ and for every value the functional output is $1$.
Hence a we need to calculate the parity of $1111111111111111$ (16 ones) which is $1$
Now my question is ,The option two ($2$), is it Correct? does it always give $1$ (even) as output ? According to the answers of the quiz, it is showing it is correct, but is it? I've run some test on n=4, n=5, unfortunately both are unsatisfying the answer here.
Thank you.

Answer 1

There are $2^n$ possible inputs. When the input bit strings are ordered lexicographically, the least significant bit of each string alternates between even and odd. There are an even number of possible inputs; half of them even and half of them odd.

$$Parity = 1^{2^n/2} * {(-1)}^{2^n/2} = 1$$

So the parity of this function is even. Option 2 is the same as option 1, only for a permutation of the arguments that exchange bit $j$ with the least-significant bit.

Answer 2

The parity of a Boolean function, $f$, is given by

$$Parity(f) = \prod_{\forall x \in \{0,1\}^n} 1 - 2f(x).$$

Notice that the product ranges over all $x \in \{0,1\}^n$ and that

$$\{0,1\}^n = \{0,1\}^{n-1} \times \{0,1\}.$$

It is possible to factor out one bit, $z \in \{0,1\}$, from the product so that

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\biggr({\prod_{\forall z \in \{0,1\}} 1 - 2f(y,z)}\biggr),$$

and, by expanding the innermost product,

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg),$$

in which $z$ has been substituted with ${\bf 0}$ and ${\bf 1}$.

Now for the special case where $f$ is a Boolean function that returns the least significant bit of the argument, we have that, for all $y \in \{0,1\}^{n-1}$,

$$f(y,{\bf 0}) = {\bf 0}$$ $$f(y,{\bf 1}) = {\bf 1}.$$

Substituting these into the innermost product we find that

$$\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg) \;\; = \;\; -1$$

so that the parity function becomes

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}-1 \;\; = \;\; (-1)^{2^{n-1}}$$

which shows that the function has even parity when $n>1$ and odd parity when $n=1$.

It does not matter that we chose to factor out the least-significant bit. Choosing a bit from anywhere else, $j$, in the input argument would just have given a different order of the products and, since products are commutative, we could rearrange them into exactly the form given above.