Dependence of the derivative of a pseudo-Boolean function on its variables

Question

I am going through Pseudo-Boolean optimization by Boros et al. In the section 2, the paper introduces the idea of derivative and residual of a peudo-Boolean function.

It is claimed that both $\Delta_i(\overrightarrow{X})$ and $\Theta_i(\overrightarrow{X})$ are independent of $x_i$. I do not understand how $\Theta_i(\overrightarrow{X})$ is independent of $X_i$. Both terms of $\Theta_i(\overrightarrow{X})$ take / has $x_i$ as input.

So, how is $\Theta_i(\overrightarrow{X})$ independent of $x_i$?

Answer 1

The function $\Delta_i(\mathbf{x})$ is clearly independent of $x_i$ since there is no this variable in the formula defining this function. To show that $\Theta_i(\mathbf{x})$ is independent of $x_i$ let $\mathbf{x}^0_i = (x_1, \dots, x_{i-1}, 0, x_{i + 1}, \dots, x_n)$, same for $\mathbf{x}^1_i$. You need to check that $\Theta_i(\mathbf{x}^0_i) = \Theta_i(\mathbf{x}^1_i).$ But we have $$ \Theta_i(\mathbf{x}^1_i) = f(\mathbf{x}^1_i) - 1\cdot \Delta_i(\mathbf{x}^1_i) = f(\mathbf{x}^1_i) - (f(\mathbf{x}^1_i) - f(\mathbf{x}^0_i)) = f(\mathbf{x}^0_i) = f(\mathbf{x}^0_i) - 0\cdot \Delta_i(\mathbf{x}^0_i) = \Theta_i(\mathbf{x}^0_i). $$