Why Is The Number of Boolean Subfunctions Based on a Min and Not a Product?

Question

In Stasys Jukna's book "Boolean Function Complexity", he states that for an n variable Boolean function, the number of distinct subfunctions on $Y$ variables (meaning $Y$ variables have not been assigned to constants), is the minimum of $2^{n-|Y|}$ and $2^{2^{|Y|}}$. The first number is the number of ways constants could be assigned to all variables not in $Y$, and the second number is the number of Boolean functions on $Y$ variables. My question is why is the number of distinct subfunctions the minimum of these two numbers, and not their product, as it seems to me for each configuration of constants for variables not in $Y$, each boolean function on $Y$ could be applied.

Answer 1

In this context, a subfunction is a function $f(X_Y)$. The number of it is related to the sensitivity of the function on the other fixed variables $X_{\overline{Y}}$. For example, in $IP_n$, the sensitivity is low; while in CNF or DNF, it can be high. Anyways, here's how I believe he got this:

$\leq2^{2^{|Y|}}$: since the subfunction is a function of $X_Y$, the number of which is $2^{2^{|Y|}}$.

$\leq2^{|\overline{Y}|}$: each assignment to variables in $X_{\overline{Y}}$ may create at most a distinct subfunction (high sensitivity), and there are $2^{|\overline{Y}|}$ of assignments.

Answer 2

Case 1: 2$^n$$^-$$^m$ > 2$^{2^m}$. So, as we go on setting n-m variables to constants, at each setting we get a subfunction with a truth-table of size 2$^m$. It is some part of the original truth-table of size 2$^n$. So, by setting n-m variables to constants, we cannot get more distinct subfunctions out from the original truth-table than 2$^{2^m}$. So, the number of distinct subfunctions of $f$ on Y in this case is upper-bounded by 2$^{2^m}$.

Example: Let us imagine a function on 32 variables. There are 2$^{32}$ rows in the truth-table. Let Y = $\{x_1, x_2\}$. There are 16 different functions on 2 variables and 2$^{30}$ ways to set variables {x$_3$,...x$_{32}$} to constants. As we go on and realize all possible settings to constants, we will not be able to exceed the limit of 16 different codomains.

Case 2: 2$^n$$^-$$^m$ < 2$^{2^m}$. As we go on setting n-m variables to constants, at each setting we get a subfunction with a truth-table of size 2$^m$. But since there are less variables to set to constants than there are different functions on m variables, not all of the 2$^{2^m}$ functions will be realized. So, the number of distinct subfunctions of $f$ on Y in this case is upper-bounded by 2$^n$$^-$$^m$.

Example: Let us imagine a function on 3 variables. There are 2$^{3}$ rows in the truth-table. Let Y = $\{x_1, x_2\}$. There are 16 different functions on 2 variables and 2$^{1}$ ways to set the variable {x$_3$} to a constant. As we go on and realize 2 possible settings to constants, we are not able to realize all 16 possible different codomains. We will just realize 2 codomains, and whether they are distinct or not depends on how $f$ was originally defined.